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