diff options
Diffstat (limited to 'lib/librte_table/rte_table_hash.h')
| -rw-r--r-- | lib/librte_table/rte_table_hash.h | 370 |
1 files changed, 370 insertions, 0 deletions
diff --git a/lib/librte_table/rte_table_hash.h b/lib/librte_table/rte_table_hash.h new file mode 100644 index 00000000..9d17516a --- /dev/null +++ b/lib/librte_table/rte_table_hash.h @@ -0,0 +1,370 @@ +/*- + * BSD LICENSE + * + * Copyright(c) 2010-2014 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. + */ + +#ifndef __INCLUDE_RTE_TABLE_HASH_H__ +#define __INCLUDE_RTE_TABLE_HASH_H__ + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * @file + * RTE Table Hash + * + * 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 + * deleted and the new key is added in its place. The number of keys in + * each bucket never grows bigger than 4. The logic to pick the key to + * be dropped from the bucket is LRU. The hash table lookup operation + * maintains the order in which the keys in the same bucket are hit, so + * every time a key is hit, it becomes the new Most Recently Used (MRU) + * key, i.e. the most unlikely candidate for drop. When a key is added + * 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 + * 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 + * allocation of a group of 4 keys only happens successfully within the + * limit of free keys, otherwise the key add operation fails. On key + * delete operation, a group of 4 keys is freed back to the pool of free + * keys when the key to be deleted is the only key that was used within + * its group of 4 keys at that time. On key lookup operation, if the + * 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: + * a. Configurable key size + * b. Single key size (8-byte, 16-byte or 32-byte key size) + * + ***/ +#include <stdint.h> + +#include "rte_table.h" + +/** Hash function */ +typedef uint64_t (*rte_table_hash_op_hash)( + void *key, + uint32_t key_size, + uint64_t seed); + +/** + * Hash tables with configurable key size + * + */ +/** Extendible bucket hash table parameters */ +struct rte_table_hash_ext_params { + /** 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; + + /** Maximum number of keys */ + uint32_t n_keys; + + /** Number of hash table buckets. Each bucket stores up to 4 keys. */ + uint32_t n_buckets; + + /** 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; +}; + +/** 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 */ +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; + +#ifdef __cplusplus +} +#endif + +#endif |