3c53d6ada5e403dad57ec8c86532bd6a70e0cc67
[dpdk.git] / lib / librte_table / rte_table_hash.h
1 /*-
2  *   BSD LICENSE
3  *
4  *   Copyright(c) 2010-2016 Intel Corporation. All rights reserved.
5  *   All rights reserved.
6  *
7  *   Redistribution and use in source and binary forms, with or without
8  *   modification, are permitted provided that the following conditions
9  *   are met:
10  *
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
16  *       distribution.
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.
20  *
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.
32  */
33
34 #ifndef __INCLUDE_RTE_TABLE_HASH_H__
35 #define __INCLUDE_RTE_TABLE_HASH_H__
36
37 #ifdef __cplusplus
38 extern "C" {
39 #endif
40
41 /**
42  * @file
43  * RTE Table Hash
44  *
45  * These tables use the exact match criterion to uniquely associate data to
46  * lookup keys.
47  *
48  * Use-cases: Flow classification table, Address Resolution Protocol (ARP) table
49  *
50  * Hash table types:
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
88  *        operation.
89  * 3. Key size:
90  *     a. Configurable key size
91  *     b. Single key size (8-byte, 16-byte or 32-byte key size)
92  *
93  ***/
94 #include <stdint.h>
95
96 #include "rte_table.h"
97
98 /** Hash function */
99 typedef uint64_t (*rte_table_hash_op_hash)(
100         void *key,
101         void *key_mask,
102         uint32_t key_size,
103         uint64_t seed);
104
105 /** Hash table parameters */
106 struct rte_table_hash_params {
107         /** Name */
108         const char *name;
109
110         /** Key size (number of bytes) */
111         uint32_t key_size;
112
113         /** Byte offset within packet meta-data where the key is located */
114         uint32_t key_offset;
115
116         /** Key mask */
117         uint8_t *key_mask;
118
119         /** Number of keys */
120         uint32_t n_keys;
121
122         /** Number of buckets */
123         uint32_t n_buckets;
124
125         /** Hash function */
126         rte_table_hash_op_hash f_hash;
127
128         /** Seed value for the hash function */
129         uint64_t seed;
130 };
131
132 extern struct rte_table_ops rte_table_hash_ext_ops;
133
134 extern struct rte_table_ops rte_table_hash_lru_ops;
135
136 extern struct rte_table_ops rte_table_hash_key8_lru_ops;
137
138 extern struct rte_table_ops rte_table_hash_key8_ext_ops;
139
140 extern struct rte_table_ops rte_table_hash_key16_lru_ops;
141
142 extern struct rte_table_ops rte_table_hash_key16_ext_ops;
143
144 extern struct rte_table_ops rte_table_hash_key32_lru_ops;
145
146 extern struct rte_table_ops rte_table_hash_key32_ext_ops;
147
148 extern struct rte_table_ops rte_table_hash_cuckoo_ops;
149
150 #ifdef __cplusplus
151 }
152 #endif
153
154 #endif