4 * Copyright(c) 2010-2016 Intel Corporation. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of Intel Corporation nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 #ifndef __INCLUDE_RTE_TABLE_HASH_H__
35 #define __INCLUDE_RTE_TABLE_HASH_H__
45 * These tables use the exact match criterion to uniquely associate data to
48 * Use-cases: Flow classification table, Address Resolution Protocol (ARP) table
51 * 1. Entry add strategy on bucket full:
52 * a. Least Recently Used (LRU): One of the existing keys in the bucket is
53 * deleted and the new key is added in its place. The number of keys in
54 * each bucket never grows bigger than 4. The logic to pick the key to
55 * be dropped from the bucket is LRU. The hash table lookup operation
56 * maintains the order in which the keys in the same bucket are hit, so
57 * every time a key is hit, it becomes the new Most Recently Used (MRU)
58 * key, i.e. the most unlikely candidate for drop. When a key is added
59 * to the bucket, it also becomes the new MRU key. When a key needs to
60 * be picked and dropped, the most likely candidate for drop, i.e. the
61 * current LRU key, is always picked. The LRU logic requires maintaining
62 * specific data structures per each bucket.
63 * b. Extendible bucket (ext): The bucket is extended with space for 4 more
64 * keys. This is done by allocating additional memory at table init time,
65 * which is used to create a pool of free keys (the size of this pool is
66 * configurable and always a multiple of 4). On key add operation, the
67 * allocation of a group of 4 keys only happens successfully within the
68 * limit of free keys, otherwise the key add operation fails. On key
69 * delete operation, a group of 4 keys is freed back to the pool of free
70 * keys when the key to be deleted is the only key that was used within
71 * its group of 4 keys at that time. On key lookup operation, if the
72 * current bucket is in extended state and a match is not found in the
73 * first group of 4 keys, the search continues beyond the first group of
74 * 4 keys, potentially until all keys in this bucket are examined. The
75 * extendible bucket logic requires maintaining specific data structures
76 * per table and per each bucket.
77 * 2. Key signature computation:
78 * a. Pre-computed key signature: The key lookup operation is split between
79 * two CPU cores. The first CPU core (typically the CPU core performing
80 * packet RX) extracts the key from the input packet, computes the key
81 * signature and saves both the key and the key signature in the packet
82 * buffer as packet meta-data. The second CPU core reads both the key and
83 * the key signature from the packet meta-data and performs the bucket
84 * search step of the key lookup operation.
85 * b. Key signature computed on lookup (do-sig): The same CPU core reads
86 * the key from the packet meta-data, uses it to compute the key
87 * signature and also performs the bucket search step of the key lookup
90 * a. Configurable key size
91 * b. Single key size (8-byte, 16-byte or 32-byte key size)
96 #include "rte_table.h"
99 typedef uint64_t (*rte_table_hash_op_hash)(
105 * Hash tables with configurable key size
108 /** Extendible bucket hash table parameters */
109 struct rte_table_hash_ext_params {
110 /** Key size (number of bytes) */
113 /** Maximum number of keys */
116 /** Number of hash table buckets. Each bucket stores up to 4 keys. */
119 /** Number of hash table bucket extensions. Each bucket extension has
120 space for 4 keys and each bucket can have 0, 1 or more extensions. */
121 uint32_t n_buckets_ext;
124 rte_table_hash_op_hash f_hash;
126 /** Seed value for the hash function */
129 /** Byte offset within packet meta-data where the 4-byte key signature
130 is located. Valid for pre-computed key signature tables, ignored for
132 uint32_t signature_offset;
134 /** Byte offset within packet meta-data where the key is located */
138 /** Extendible bucket hash table operations for pre-computed key signature */
139 extern struct rte_table_ops rte_table_hash_ext_ops;
141 /** Extendible bucket hash table operations for key signature computed on
143 extern struct rte_table_ops rte_table_hash_ext_dosig_ops;
145 /** LRU hash table parameters */
146 struct rte_table_hash_lru_params {
147 /** Key size (number of bytes) */
150 /** Maximum number of keys */
153 /** Number of hash table buckets. Each bucket stores up to 4 keys. */
157 rte_table_hash_op_hash f_hash;
159 /** Seed value for the hash function */
162 /** Byte offset within packet meta-data where the 4-byte key signature
163 is located. Valid for pre-computed key signature tables, ignored for
165 uint32_t signature_offset;
167 /** Byte offset within packet meta-data where the key is located */
171 /** LRU hash table operations for pre-computed key signature */
172 extern struct rte_table_ops rte_table_hash_lru_ops;
174 /** LRU hash table operations for key signature computed on lookup ("do-sig") */
175 extern struct rte_table_ops rte_table_hash_lru_dosig_ops;
178 * 8-byte key hash tables
181 /** LRU hash table parameters */
182 struct rte_table_hash_key8_lru_params {
183 /** Maximum number of entries (and keys) in the table */
187 rte_table_hash_op_hash f_hash;
189 /** Seed for the hash function */
192 /** Byte offset within packet meta-data where the 4-byte key signature
193 is located. Valid for pre-computed key signature tables, ignored for
195 uint32_t signature_offset;
197 /** Byte offset within packet meta-data where the key is located */
200 /** Bit-mask to be AND-ed to the key on lookup */
204 extern struct rte_table_ops rte_table_hash_key8_lru_ops;
206 /** Extendible bucket hash table parameters */
207 struct rte_table_hash_key8_ext_params {
208 /** Maximum number of entries (and keys) in the table */
211 /** Number of entries (and keys) for hash table bucket extensions. Each
212 bucket is extended in increments of 4 keys. */
213 uint32_t n_entries_ext;
216 rte_table_hash_op_hash f_hash;
218 /** Seed for the hash function */
221 /** Byte offset within packet meta-data where the 4-byte key signature
222 is located. Valid for pre-computed key signature tables, ignored for
224 uint32_t signature_offset;
226 /** Byte offset within packet meta-data where the key is located */
229 /** Bit-mask to be AND-ed to the key on lookup */
233 extern struct rte_table_ops rte_table_hash_key8_ext_ops;
236 * 16-byte key hash tables
239 /** LRU hash table parameters */
240 struct rte_table_hash_key16_lru_params {
241 /** Maximum number of entries (and keys) in the table */
245 rte_table_hash_op_hash f_hash;
247 /** Seed for the hash function */
250 /** Byte offset within packet meta-data where the 4-byte key signature
251 is located. Valid for pre-computed key signature tables, ignored for
253 uint32_t signature_offset;
255 /** Byte offset within packet meta-data where the key is located */
258 /** Bit-mask to be AND-ed to the key on lookup */
262 /** LRU hash table operations for pre-computed key signature */
263 extern struct rte_table_ops rte_table_hash_key16_lru_ops;
265 /** LRU hash table operations for key signature computed on lookup
267 extern struct rte_table_ops rte_table_hash_key16_lru_dosig_ops;
269 /** Extendible bucket hash table parameters */
270 struct rte_table_hash_key16_ext_params {
271 /** Maximum number of entries (and keys) in the table */
274 /** Number of entries (and keys) for hash table bucket extensions. Each
275 bucket is extended in increments of 4 keys. */
276 uint32_t n_entries_ext;
279 rte_table_hash_op_hash f_hash;
281 /** Seed for the hash function */
284 /** Byte offset within packet meta-data where the 4-byte key signature
285 is located. Valid for pre-computed key signature tables, ignored for
287 uint32_t signature_offset;
289 /** Byte offset within packet meta-data where the key is located */
292 /** Bit-mask to be AND-ed to the key on lookup */
296 /** Extendible bucket operations for pre-computed key signature */
297 extern struct rte_table_ops rte_table_hash_key16_ext_ops;
299 /** Extendible bucket hash table operations for key signature computed on
301 extern struct rte_table_ops rte_table_hash_key16_ext_dosig_ops;
304 * 32-byte key hash tables
307 /** LRU hash table parameters */
308 struct rte_table_hash_key32_lru_params {
309 /** Maximum number of entries (and keys) in the table */
313 rte_table_hash_op_hash f_hash;
315 /** Seed for the hash function */
318 /** Byte offset within packet meta-data where the 4-byte key signature
319 is located. Valid for pre-computed key signature tables, ignored for
321 uint32_t signature_offset;
323 /** Byte offset within packet meta-data where the key is located */
327 /** LRU hash table operations for pre-computed key signature */
328 extern struct rte_table_ops rte_table_hash_key32_lru_ops;
330 /** Extendible bucket hash table parameters */
331 struct rte_table_hash_key32_ext_params {
332 /** Maximum number of entries (and keys) in the table */
335 /** Number of entries (and keys) for hash table bucket extensions. Each
336 bucket is extended in increments of 4 keys. */
337 uint32_t n_entries_ext;
340 rte_table_hash_op_hash f_hash;
342 /** Seed for the hash function */
345 /** Byte offset within packet meta-data where the 4-byte key signature
346 is located. Valid for pre-computed key signature tables, ignored for
348 uint32_t signature_offset;
350 /** Byte offset within packet meta-data where the key is located */
354 /** Extendible bucket hash table operations */
355 extern struct rte_table_ops rte_table_hash_key32_ext_ops;
357 /** Cuckoo hash table parameters */
358 struct rte_table_hash_cuckoo_params {
359 /** Key size (number of bytes */
362 /** Maximum number of hash table entries */
365 /** Hash function used to calculate hash */
366 rte_table_hash_op_hash f_hash;
368 /** Seed value or Init value used by f_hash */
371 /** Byte offset within packet meta-data where the 4-byte key signature
372 is located. Valid for pre-computed key signature tables, ignored for
374 uint32_t signature_offset;
376 /** Byte offset within packet meta-data where the key is located */
379 /** Hash table name */
383 /** Cuckoo hash table operations */
384 extern struct rte_table_ops rte_table_hash_cuckoo_dosig_ops;