]>
Commit | Line | Data |
---|---|---|
9f95a23c TL |
1 | /* SPDX-License-Identifier: BSD-3-Clause |
2 | * Copyright(c) 2010-2014 Intel Corporation | |
7c673cae FG |
3 | */ |
4 | ||
5 | #ifndef _RTE_FBK_HASH_H_ | |
6 | #define _RTE_FBK_HASH_H_ | |
7 | ||
8 | /** | |
9 | * @file | |
10 | * | |
11 | * This is a hash table implementation for four byte keys (fbk). | |
12 | * | |
13 | * Note that the return value of the add function should always be checked as, | |
14 | * if a bucket is full, the key is not added even if there is space in other | |
15 | * buckets. This keeps the lookup function very simple and therefore fast. | |
16 | */ | |
17 | ||
18 | #include <stdint.h> | |
19 | #include <errno.h> | |
20 | #include <sys/queue.h> | |
21 | ||
22 | #ifdef __cplusplus | |
23 | extern "C" { | |
24 | #endif | |
25 | ||
26 | #include <string.h> | |
27 | ||
9f95a23c | 28 | #include <rte_config.h> |
7c673cae | 29 | #include <rte_hash_crc.h> |
7c673cae | 30 | #include <rte_jhash.h> |
7c673cae FG |
31 | |
32 | #ifndef RTE_FBK_HASH_INIT_VAL_DEFAULT | |
33 | /** Initialising value used when calculating hash. */ | |
34 | #define RTE_FBK_HASH_INIT_VAL_DEFAULT 0xFFFFFFFF | |
35 | #endif | |
36 | ||
37 | /** The maximum number of entries in the hash table that is supported. */ | |
38 | #define RTE_FBK_HASH_ENTRIES_MAX (1 << 20) | |
39 | ||
40 | /** The maximum number of entries in each bucket that is supported. */ | |
41 | #define RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX 256 | |
42 | ||
43 | /** Maximum size of string for naming the hash. */ | |
44 | #define RTE_FBK_HASH_NAMESIZE 32 | |
45 | ||
46 | /** Type of function that can be used for calculating the hash value. */ | |
47 | typedef uint32_t (*rte_fbk_hash_fn)(uint32_t key, uint32_t init_val); | |
48 | ||
49 | /** Parameters used when creating four-byte key hash table. */ | |
50 | struct rte_fbk_hash_params { | |
51 | const char *name; /**< Name of the hash table. */ | |
52 | uint32_t entries; /**< Total number of entries. */ | |
53 | uint32_t entries_per_bucket; /**< Number of entries in a bucket. */ | |
54 | int socket_id; /**< Socket to allocate memory on. */ | |
55 | rte_fbk_hash_fn hash_func; /**< The hash function. */ | |
56 | uint32_t init_val; /**< For initialising hash function. */ | |
57 | }; | |
58 | ||
59 | /** Individual entry in the four-byte key hash table. */ | |
60 | union rte_fbk_hash_entry { | |
61 | uint64_t whole_entry; /**< For accessing entire entry. */ | |
62 | struct { | |
63 | uint16_t is_entry; /**< Non-zero if entry is active. */ | |
64 | uint16_t value; /**< Value returned by lookup. */ | |
65 | uint32_t key; /**< Key used to find value. */ | |
66 | } entry; /**< For accessing each entry part. */ | |
67 | }; | |
68 | ||
69 | ||
70 | /** The four-byte key hash table structure. */ | |
71 | struct rte_fbk_hash_table { | |
72 | char name[RTE_FBK_HASH_NAMESIZE]; /**< Name of the hash. */ | |
73 | uint32_t entries; /**< Total number of entries. */ | |
74 | uint32_t entries_per_bucket; /**< Number of entries in a bucket. */ | |
75 | uint32_t used_entries; /**< How many entries are used. */ | |
76 | uint32_t bucket_mask; /**< To find which bucket the key is in. */ | |
77 | uint32_t bucket_shift; /**< Convert bucket to table offset. */ | |
78 | rte_fbk_hash_fn hash_func; /**< The hash function. */ | |
79 | uint32_t init_val; /**< For initialising hash function. */ | |
80 | ||
81 | /** A flat table of all buckets. */ | |
82 | union rte_fbk_hash_entry t[]; | |
83 | }; | |
84 | ||
85 | /** | |
86 | * Find the offset into hash table of the bucket containing a particular key. | |
87 | * | |
88 | * @param ht | |
89 | * Pointer to hash table. | |
90 | * @param key | |
91 | * Key to calculate bucket for. | |
92 | * @return | |
93 | * Offset into hash table. | |
94 | */ | |
95 | static inline uint32_t | |
96 | rte_fbk_hash_get_bucket(const struct rte_fbk_hash_table *ht, uint32_t key) | |
97 | { | |
98 | return (ht->hash_func(key, ht->init_val) & ht->bucket_mask) << | |
99 | ht->bucket_shift; | |
100 | } | |
101 | ||
102 | /** | |
103 | * Add a key to an existing hash table with bucket id. | |
104 | * This operation is not multi-thread safe | |
105 | * and should only be called from one thread. | |
106 | * | |
107 | * @param ht | |
108 | * Hash table to add the key to. | |
109 | * @param key | |
110 | * Key to add to the hash table. | |
111 | * @param value | |
112 | * Value to associate with key. | |
113 | * @param bucket | |
114 | * Bucket to associate with key. | |
115 | * @return | |
116 | * 0 if ok, or negative value on error. | |
117 | */ | |
118 | static inline int | |
119 | rte_fbk_hash_add_key_with_bucket(struct rte_fbk_hash_table *ht, | |
120 | uint32_t key, uint16_t value, uint32_t bucket) | |
121 | { | |
122 | /* | |
123 | * The writing of a new value to the hash table is done as a single | |
124 | * 64bit operation. This should help prevent individual entries being | |
125 | * corrupted due to race conditions, but it's still possible to | |
126 | * overwrite entries that have just been made valid. | |
127 | */ | |
128 | const uint64_t new_entry = ((uint64_t)(key) << 32) | | |
129 | ((uint64_t)(value) << 16) | | |
130 | 1; /* 1 = is_entry bit. */ | |
131 | uint32_t i; | |
132 | ||
133 | for (i = 0; i < ht->entries_per_bucket; i++) { | |
134 | /* Set entry if unused. */ | |
135 | if (! ht->t[bucket + i].entry.is_entry) { | |
136 | ht->t[bucket + i].whole_entry = new_entry; | |
137 | ht->used_entries++; | |
138 | return 0; | |
139 | } | |
140 | /* Change value if key already exists. */ | |
141 | if (ht->t[bucket + i].entry.key == key) { | |
142 | ht->t[bucket + i].entry.value = value; | |
143 | return 0; | |
144 | } | |
145 | } | |
146 | ||
147 | return -ENOSPC; /* No space in bucket. */ | |
148 | } | |
149 | ||
150 | /** | |
151 | * Add a key to an existing hash table. This operation is not multi-thread safe | |
152 | * and should only be called from one thread. | |
153 | * | |
154 | * @param ht | |
155 | * Hash table to add the key to. | |
156 | * @param key | |
157 | * Key to add to the hash table. | |
158 | * @param value | |
159 | * Value to associate with key. | |
160 | * @return | |
161 | * 0 if ok, or negative value on error. | |
162 | */ | |
163 | static inline int | |
164 | rte_fbk_hash_add_key(struct rte_fbk_hash_table *ht, | |
165 | uint32_t key, uint16_t value) | |
166 | { | |
167 | return rte_fbk_hash_add_key_with_bucket(ht, | |
168 | key, value, rte_fbk_hash_get_bucket(ht, key)); | |
169 | } | |
170 | ||
171 | /** | |
172 | * Remove a key with a given bucket id from an existing hash table. | |
173 | * This operation is not multi-thread | |
174 | * safe and should only be called from one thread. | |
175 | * | |
176 | * @param ht | |
177 | * Hash table to remove the key from. | |
178 | * @param key | |
179 | * Key to remove from the hash table. | |
180 | * @param bucket | |
181 | * Bucket id associate with key. | |
182 | * @return | |
183 | * 0 if ok, or negative value on error. | |
184 | */ | |
185 | static inline int | |
186 | rte_fbk_hash_delete_key_with_bucket(struct rte_fbk_hash_table *ht, | |
187 | uint32_t key, uint32_t bucket) | |
188 | { | |
189 | uint32_t last_entry = ht->entries_per_bucket - 1; | |
190 | uint32_t i, j; | |
191 | ||
192 | for (i = 0; i < ht->entries_per_bucket; i++) { | |
193 | if (ht->t[bucket + i].entry.key == key) { | |
194 | /* Find last key in bucket. */ | |
195 | for (j = ht->entries_per_bucket - 1; j > i; j-- ) { | |
196 | if (! ht->t[bucket + j].entry.is_entry) { | |
197 | last_entry = j - 1; | |
198 | } | |
199 | } | |
200 | /* | |
201 | * Move the last key to the deleted key's position, and | |
202 | * delete the last key. lastEntry and i may be same but | |
203 | * it doesn't matter. | |
204 | */ | |
205 | ht->t[bucket + i].whole_entry = | |
206 | ht->t[bucket + last_entry].whole_entry; | |
207 | ht->t[bucket + last_entry].whole_entry = 0; | |
208 | ||
209 | ht->used_entries--; | |
210 | return 0; | |
211 | } | |
212 | } | |
213 | ||
214 | return -ENOENT; /* Key didn't exist. */ | |
215 | } | |
216 | ||
217 | /** | |
218 | * Remove a key from an existing hash table. This operation is not multi-thread | |
219 | * safe and should only be called from one thread. | |
220 | * | |
221 | * @param ht | |
222 | * Hash table to remove the key from. | |
223 | * @param key | |
224 | * Key to remove from the hash table. | |
225 | * @return | |
226 | * 0 if ok, or negative value on error. | |
227 | */ | |
228 | static inline int | |
229 | rte_fbk_hash_delete_key(struct rte_fbk_hash_table *ht, uint32_t key) | |
230 | { | |
231 | return rte_fbk_hash_delete_key_with_bucket(ht, | |
232 | key, rte_fbk_hash_get_bucket(ht, key)); | |
233 | } | |
234 | ||
235 | /** | |
236 | * Find a key in the hash table with a given bucketid. | |
237 | * This operation is multi-thread safe. | |
238 | * | |
239 | * @param ht | |
240 | * Hash table to look in. | |
241 | * @param key | |
242 | * Key to find. | |
243 | * @param bucket | |
244 | * Bucket associate to the key. | |
245 | * @return | |
246 | * The value that was associated with the key, or negative value on error. | |
247 | */ | |
248 | static inline int | |
249 | rte_fbk_hash_lookup_with_bucket(const struct rte_fbk_hash_table *ht, | |
250 | uint32_t key, uint32_t bucket) | |
251 | { | |
252 | union rte_fbk_hash_entry current_entry; | |
253 | uint32_t i; | |
254 | ||
255 | for (i = 0; i < ht->entries_per_bucket; i++) { | |
256 | /* Single read of entry, which should be atomic. */ | |
257 | current_entry.whole_entry = ht->t[bucket + i].whole_entry; | |
258 | if (! current_entry.entry.is_entry) { | |
259 | return -ENOENT; /* Error once we hit an empty field. */ | |
260 | } | |
261 | if (current_entry.entry.key == key) { | |
262 | return current_entry.entry.value; | |
263 | } | |
264 | } | |
265 | return -ENOENT; /* Key didn't exist. */ | |
266 | } | |
267 | ||
268 | /** | |
269 | * Find a key in the hash table. This operation is multi-thread safe. | |
270 | * | |
271 | * @param ht | |
272 | * Hash table to look in. | |
273 | * @param key | |
274 | * Key to find. | |
275 | * @return | |
276 | * The value that was associated with the key, or negative value on error. | |
277 | */ | |
278 | static inline int | |
279 | rte_fbk_hash_lookup(const struct rte_fbk_hash_table *ht, uint32_t key) | |
280 | { | |
281 | return rte_fbk_hash_lookup_with_bucket(ht, | |
282 | key, rte_fbk_hash_get_bucket(ht, key)); | |
283 | } | |
284 | ||
285 | /** | |
286 | * Delete all entries in a hash table. This operation is not multi-thread | |
287 | * safe and should only be called from one thread. | |
288 | * | |
289 | * @param ht | |
290 | * Hash table to delete entries in. | |
291 | */ | |
292 | static inline void | |
293 | rte_fbk_hash_clear_all(struct rte_fbk_hash_table *ht) | |
294 | { | |
295 | memset(ht->t, 0, sizeof(ht->t[0]) * ht->entries); | |
296 | ht->used_entries = 0; | |
297 | } | |
298 | ||
299 | /** | |
300 | * Find what fraction of entries are being used. | |
301 | * | |
302 | * @param ht | |
303 | * Hash table to find how many entries are being used in. | |
304 | * @return | |
305 | * Load factor of the hash table, or negative value on error. | |
306 | */ | |
307 | static inline double | |
308 | rte_fbk_hash_get_load_factor(struct rte_fbk_hash_table *ht) | |
309 | { | |
310 | return (double)ht->used_entries / (double)ht->entries; | |
311 | } | |
312 | ||
313 | /** | |
314 | * Performs a lookup for an existing hash table, and returns a pointer to | |
315 | * the table if found. | |
316 | * | |
317 | * @param name | |
318 | * Name of the hash table to find | |
319 | * | |
320 | * @return | |
321 | * pointer to hash table structure or NULL on error with rte_errno | |
322 | * set appropriately. Possible rte_errno values include: | |
323 | * - ENOENT - required entry not available to return. | |
324 | */ | |
325 | struct rte_fbk_hash_table *rte_fbk_hash_find_existing(const char *name); | |
326 | ||
327 | /** | |
328 | * Create a new hash table for use with four byte keys. | |
329 | * | |
330 | * @param params | |
331 | * Parameters used in creation of hash table. | |
332 | * | |
333 | * @return | |
334 | * Pointer to hash table structure that is used in future hash table | |
335 | * operations, or NULL on error with rte_errno set appropriately. | |
336 | * Possible rte_errno error values include: | |
337 | * - E_RTE_NO_CONFIG - function could not get pointer to rte_config structure | |
338 | * - E_RTE_SECONDARY - function was called from a secondary process instance | |
339 | * - EINVAL - invalid parameter value passed to function | |
340 | * - ENOSPC - the maximum number of memzones has already been allocated | |
341 | * - EEXIST - a memzone with the same name already exists | |
342 | * - ENOMEM - no appropriate memory area found in which to create memzone | |
343 | */ | |
344 | struct rte_fbk_hash_table * \ | |
345 | rte_fbk_hash_create(const struct rte_fbk_hash_params *params); | |
346 | ||
347 | /** | |
348 | * Free all memory used by a hash table. | |
349 | * Has no effect on hash tables allocated in memory zones | |
350 | * | |
351 | * @param ht | |
352 | * Hash table to deallocate. | |
353 | */ | |
354 | void rte_fbk_hash_free(struct rte_fbk_hash_table *ht); | |
355 | ||
356 | #ifdef __cplusplus | |
357 | } | |
358 | #endif | |
359 | ||
360 | #endif /* _RTE_FBK_HASH_H_ */ |