1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2017 Intel Corporation
5 #ifndef __INCLUDE_RTE_TABLE_HASH_H__
6 #define __INCLUDE_RTE_TABLE_HASH_H__
16 * These tables use the exact match criterion to uniquely associate data to
20 * 1. Entry add strategy on bucket full:
21 * a. Least Recently Used (LRU): One of the existing keys in the bucket is
22 * deleted and the new key is added in its place. The number of keys in
23 * each bucket never grows bigger than 4. The logic to pick the key to
24 * be dropped from the bucket is LRU. The hash table lookup operation
25 * maintains the order in which the keys in the same bucket are hit, so
26 * every time a key is hit, it becomes the new Most Recently Used (MRU)
27 * key, i.e. the most unlikely candidate for drop. When a key is added
28 * to the bucket, it also becomes the new MRU key. When a key needs to
29 * be picked and dropped, the most likely candidate for drop, i.e. the
30 * current LRU key, is always picked. The LRU logic requires maintaining
31 * specific data structures per each bucket. Use-cases: flow cache, etc.
32 * b. Extendible bucket (ext): The bucket is extended with space for 4 more
33 * keys. This is done by allocating additional memory at table init time,
34 * which is used to create a pool of free keys (the size of this pool is
35 * configurable and always a multiple of 4). On key add operation, the
36 * allocation of a group of 4 keys only happens successfully within the
37 * limit of free keys, otherwise the key add operation fails. On key
38 * delete operation, a group of 4 keys is freed back to the pool of free
39 * keys when the key to be deleted is the only key that was used within
40 * its group of 4 keys at that time. On key lookup operation, if the
41 * current bucket is in extended state and a match is not found in the
42 * first group of 4 keys, the search continues beyond the first group of
43 * 4 keys, potentially until all keys in this bucket are examined. The
44 * extendible bucket logic requires maintaining specific data structures
45 * per table and per each bucket. Use-cases: flow table, etc.
47 * a. Configurable key size
48 * b. Single key size (8-byte, 16-byte or 32-byte key size)
53 #include "rte_table.h"
56 typedef uint64_t (*rte_table_hash_op_hash)(
62 /** Hash table parameters */
63 struct rte_table_hash_params {
67 /** Key size (number of bytes) */
70 /** Byte offset within packet meta-data where the key is located */
79 /** Number of buckets */
83 rte_table_hash_op_hash f_hash;
85 /** Seed value for the hash function */
89 /** Extendible bucket hash table operations */
90 extern struct rte_table_ops rte_table_hash_ext_ops;
91 extern struct rte_table_ops rte_table_hash_key8_ext_ops;
92 extern struct rte_table_ops rte_table_hash_key16_ext_ops;
93 extern struct rte_table_ops rte_table_hash_key32_ext_ops;
95 /** LRU hash table operations */
96 extern struct rte_table_ops rte_table_hash_lru_ops;
98 extern struct rte_table_ops rte_table_hash_key8_lru_ops;
99 extern struct rte_table_ops rte_table_hash_key16_lru_ops;
100 extern struct rte_table_ops rte_table_hash_key32_lru_ops;
102 /** Cuckoo hash table operations */
103 extern struct rte_table_ops rte_table_hash_cuckoo_ops;