X-Git-Url: http://git.droids-corp.org/?a=blobdiff_plain;f=lib%2Flibrte_table%2Frte_table_hash.h;h=61a0eed6c5af8035b2b256e22b9ecd86dd7e0079;hb=a8cdfc69c84b7740646368a46bbd3d4d6ddf97b0;hp=57505a6f714f1981f8acf0605aea6815583382bb;hpb=5a80bf0ae61356479cb90b3cfe0b9ac6a712af80;p=dpdk.git diff --git a/lib/librte_table/rte_table_hash.h b/lib/librte_table/rte_table_hash.h index 57505a6f71..61a0eed6c5 100644 --- a/lib/librte_table/rte_table_hash.h +++ b/lib/librte_table/rte_table_hash.h @@ -1,34 +1,5 @@ -/*- - * BSD LICENSE - * - * Copyright(c) 2010-2016 Intel Corporation. All rights reserved. - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in - * the documentation and/or other materials provided with the - * distribution. - * * Neither the name of Intel Corporation nor the names of its - * contributors may be used to endorse or promote products derived - * from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2010-2017 Intel Corporation */ #ifndef __INCLUDE_RTE_TABLE_HASH_H__ @@ -45,8 +16,6 @@ extern "C" { * These tables use the exact match criterion to uniquely associate data to * lookup keys. * - * Use-cases: Flow classification table, Address Resolution Protocol (ARP) table - * * Hash table types: * 1. Entry add strategy on bucket full: * a. Least Recently Used (LRU): One of the existing keys in the bucket is @@ -59,8 +28,8 @@ extern "C" { * to the bucket, it also becomes the new MRU key. When a key needs to * be picked and dropped, the most likely candidate for drop, i.e. the * current LRU key, is always picked. The LRU logic requires maintaining - * specific data structures per each bucket. - * b. Extendible bucket (ext): The bucket is extended with space for 4 more + * specific data structures per each bucket. Use-cases: flow cache, etc. + * b. Extendable bucket (ext): The bucket is extended with space for 4 more * keys. This is done by allocating additional memory at table init time, * which is used to create a pool of free keys (the size of this pool is * configurable and always a multiple of 4). On key add operation, the @@ -72,21 +41,9 @@ extern "C" { * current bucket is in extended state and a match is not found in the * first group of 4 keys, the search continues beyond the first group of * 4 keys, potentially until all keys in this bucket are examined. The - * extendible bucket logic requires maintaining specific data structures - * per table and per each bucket. - * 2. Key signature computation: - * a. Pre-computed key signature: The key lookup operation is split between - * two CPU cores. The first CPU core (typically the CPU core performing - * packet RX) extracts the key from the input packet, computes the key - * signature and saves both the key and the key signature in the packet - * buffer as packet meta-data. The second CPU core reads both the key and - * the key signature from the packet meta-data and performs the bucket - * search step of the key lookup operation. - * b. Key signature computed on lookup (do-sig): The same CPU core reads - * the key from the packet meta-data, uses it to compute the key - * signature and also performs the bucket search step of the key lookup - * operation. - * 3. Key size: + * extendable bucket logic requires maintaining specific data structures + * per table and per each bucket. Use-cases: flow table, etc. + * 2. Key size: * a. Configurable key size * b. Single key size (8-byte, 16-byte or 32-byte key size) * @@ -98,59 +55,28 @@ extern "C" { /** Hash function */ typedef uint64_t (*rte_table_hash_op_hash)( void *key, + void *key_mask, uint32_t key_size, uint64_t seed); -/** - * Hash tables with configurable key size - * - */ -/** Extendible bucket hash table parameters */ -struct rte_table_hash_ext_params { +/** Hash table parameters */ +struct rte_table_hash_params { + /** Name */ + const char *name; + /** Key size (number of bytes) */ uint32_t key_size; - /** Maximum number of keys */ - uint32_t n_keys; - - /** Number of hash table buckets. Each bucket stores up to 4 keys. */ - uint32_t n_buckets; - - /** Number of hash table bucket extensions. Each bucket extension has - space for 4 keys and each bucket can have 0, 1 or more extensions. */ - uint32_t n_buckets_ext; - - /** Hash function */ - rte_table_hash_op_hash f_hash; - - /** Seed value for the hash function */ - uint64_t seed; - - /** Byte offset within packet meta-data where the 4-byte key signature - is located. Valid for pre-computed key signature tables, ignored for - do-sig tables. */ - uint32_t signature_offset; - /** Byte offset within packet meta-data where the key is located */ uint32_t key_offset; -}; - -/** Extendible bucket hash table operations for pre-computed key signature */ -extern struct rte_table_ops rte_table_hash_ext_ops; - -/** Extendible bucket hash table operations for key signature computed on - lookup ("do-sig") */ -extern struct rte_table_ops rte_table_hash_ext_dosig_ops; -/** LRU hash table parameters */ -struct rte_table_hash_lru_params { - /** Key size (number of bytes) */ - uint32_t key_size; + /** Key mask */ + uint8_t *key_mask; - /** Maximum number of keys */ + /** Number of keys */ uint32_t n_keys; - /** Number of hash table buckets. Each bucket stores up to 4 keys. */ + /** Number of buckets */ uint32_t n_buckets; /** Hash function */ @@ -158,239 +84,20 @@ struct rte_table_hash_lru_params { /** Seed value for the hash function */ uint64_t seed; - - /** Byte offset within packet meta-data where the 4-byte key signature - is located. Valid for pre-computed key signature tables, ignored for - do-sig tables. */ - uint32_t signature_offset; - - /** Byte offset within packet meta-data where the key is located */ - uint32_t key_offset; -}; - -/** LRU hash table operations for pre-computed key signature */ -extern struct rte_table_ops rte_table_hash_lru_ops; - -/** LRU hash table operations for key signature computed on lookup ("do-sig") */ -extern struct rte_table_ops rte_table_hash_lru_dosig_ops; - -/** - * 8-byte key hash tables - * - */ -/** LRU hash table parameters */ -struct rte_table_hash_key8_lru_params { - /** Maximum number of entries (and keys) in the table */ - uint32_t n_entries; - - /** Hash function */ - rte_table_hash_op_hash f_hash; - - /** Seed for the hash function */ - uint64_t seed; - - /** Byte offset within packet meta-data where the 4-byte key signature - is located. Valid for pre-computed key signature tables, ignored for - do-sig tables. */ - uint32_t signature_offset; - - /** Byte offset within packet meta-data where the key is located */ - uint32_t key_offset; - - /** Bit-mask to be AND-ed to the key on lookup */ - uint8_t *key_mask; -}; - -/** LRU hash table operations for pre-computed key signature */ -extern struct rte_table_ops rte_table_hash_key8_lru_ops; - -/** LRU hash table operations for key signature computed on lookup ("do-sig") */ -extern struct rte_table_ops rte_table_hash_key8_lru_dosig_ops; - -/** Extendible bucket hash table parameters */ -struct rte_table_hash_key8_ext_params { - /** Maximum number of entries (and keys) in the table */ - uint32_t n_entries; - - /** Number of entries (and keys) for hash table bucket extensions. Each - bucket is extended in increments of 4 keys. */ - uint32_t n_entries_ext; - - /** Hash function */ - rte_table_hash_op_hash f_hash; - - /** Seed for the hash function */ - uint64_t seed; - - /** Byte offset within packet meta-data where the 4-byte key signature - is located. Valid for pre-computed key signature tables, ignored for - do-sig tables. */ - uint32_t signature_offset; - - /** Byte offset within packet meta-data where the key is located */ - uint32_t key_offset; - - /** Bit-mask to be AND-ed to the key on lookup */ - uint8_t *key_mask; }; -/** Extendible bucket hash table operations for pre-computed key signature */ +/** Extendable bucket hash table operations */ +extern struct rte_table_ops rte_table_hash_ext_ops; extern struct rte_table_ops rte_table_hash_key8_ext_ops; - -/** Extendible bucket hash table operations for key signature computed on - lookup ("do-sig") */ -extern struct rte_table_ops rte_table_hash_key8_ext_dosig_ops; - -/** - * 16-byte key hash tables - * - */ -/** LRU hash table parameters */ -struct rte_table_hash_key16_lru_params { - /** Maximum number of entries (and keys) in the table */ - uint32_t n_entries; - - /** Hash function */ - rte_table_hash_op_hash f_hash; - - /** Seed for the hash function */ - uint64_t seed; - - /** Byte offset within packet meta-data where the 4-byte key signature - is located. Valid for pre-computed key signature tables, ignored for - do-sig tables. */ - uint32_t signature_offset; - - /** Byte offset within packet meta-data where the key is located */ - uint32_t key_offset; - - /** Bit-mask to be AND-ed to the key on lookup */ - uint8_t *key_mask; -}; - -/** LRU hash table operations for pre-computed key signature */ -extern struct rte_table_ops rte_table_hash_key16_lru_ops; - -/** LRU hash table operations for key signature computed on lookup - ("do-sig") */ -extern struct rte_table_ops rte_table_hash_key16_lru_dosig_ops; - -/** Extendible bucket hash table parameters */ -struct rte_table_hash_key16_ext_params { - /** Maximum number of entries (and keys) in the table */ - uint32_t n_entries; - - /** Number of entries (and keys) for hash table bucket extensions. Each - bucket is extended in increments of 4 keys. */ - uint32_t n_entries_ext; - - /** Hash function */ - rte_table_hash_op_hash f_hash; - - /** Seed for the hash function */ - uint64_t seed; - - /** Byte offset within packet meta-data where the 4-byte key signature - is located. Valid for pre-computed key signature tables, ignored for - do-sig tables. */ - uint32_t signature_offset; - - /** Byte offset within packet meta-data where the key is located */ - uint32_t key_offset; - - /** Bit-mask to be AND-ed to the key on lookup */ - uint8_t *key_mask; -}; - -/** Extendible bucket operations for pre-computed key signature */ extern struct rte_table_ops rte_table_hash_key16_ext_ops; - -/** Extendible bucket hash table operations for key signature computed on - lookup ("do-sig") */ -extern struct rte_table_ops rte_table_hash_key16_ext_dosig_ops; - -/** - * 32-byte key hash tables - * - */ -/** LRU hash table parameters */ -struct rte_table_hash_key32_lru_params { - /** Maximum number of entries (and keys) in the table */ - uint32_t n_entries; - - /** Hash function */ - rte_table_hash_op_hash f_hash; - - /** Seed for the hash function */ - uint64_t seed; - - /** Byte offset within packet meta-data where the 4-byte key signature - is located. Valid for pre-computed key signature tables, ignored for - do-sig tables. */ - uint32_t signature_offset; - - /** Byte offset within packet meta-data where the key is located */ - uint32_t key_offset; -}; - -/** LRU hash table operations for pre-computed key signature */ -extern struct rte_table_ops rte_table_hash_key32_lru_ops; - -/** Extendible bucket hash table parameters */ -struct rte_table_hash_key32_ext_params { - /** Maximum number of entries (and keys) in the table */ - uint32_t n_entries; - - /** Number of entries (and keys) for hash table bucket extensions. Each - bucket is extended in increments of 4 keys. */ - uint32_t n_entries_ext; - - /** Hash function */ - rte_table_hash_op_hash f_hash; - - /** Seed for the hash function */ - uint64_t seed; - - /** Byte offset within packet meta-data where the 4-byte key signature - is located. Valid for pre-computed key signature tables, ignored for - do-sig tables. */ - uint32_t signature_offset; - - /** Byte offset within packet meta-data where the key is located */ - uint32_t key_offset; -}; - -/** Extendible bucket hash table operations */ extern struct rte_table_ops rte_table_hash_key32_ext_ops; -/** Cuckoo hash table parameters */ -struct rte_table_hash_cuckoo_params { - /** Key size (number of bytes */ - uint32_t key_size; - - /** Maximum number of hash table entries */ - uint32_t n_keys; - - /** Hash function used to calculate hash */ - rte_table_hash_op_hash f_hash; - - /** Seed value or Init value used by f_hash */ - uint32_t seed; - - /** Byte offset within packet meta-data where the 4-byte key signature - is located. Valid for pre-computed key signature tables, ignored for - do-sig tables. */ - uint32_t signature_offset; - - /** Byte offset within packet meta-data where the key is located */ - uint32_t key_offset; - - /** Hash table name */ - const char *name; -}; +/** LRU hash table operations */ +extern struct rte_table_ops rte_table_hash_lru_ops; -/** Cuckoo hash table operations */ -extern struct rte_table_ops rte_table_hash_cuckoo_dosig_ops; +extern struct rte_table_ops rte_table_hash_key8_lru_ops; +extern struct rte_table_ops rte_table_hash_key16_lru_ops; +extern struct rte_table_ops rte_table_hash_key32_lru_ops; #ifdef __cplusplus }