DPDK  17.11.10
rte_fbk_hash.h
Go to the documentation of this file.
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 
47 #include <stdint.h>
48 #include <errno.h>
49 #include <sys/queue.h>
50 
51 #ifdef __cplusplus
52 extern "C" {
53 #endif
54 
55 #include <string.h>
56 
57 #include <rte_config.h>
58 #ifndef RTE_FBK_HASH_FUNC_DEFAULT
59 #if defined(RTE_ARCH_X86) || defined(RTE_MACHINE_CPUFLAG_CRC32)
60 #include <rte_hash_crc.h>
62 #define RTE_FBK_HASH_FUNC_DEFAULT rte_hash_crc_4byte
63 #else
64 #include <rte_jhash.h>
65 #define RTE_FBK_HASH_FUNC_DEFAULT rte_jhash_1word
66 #endif
67 #endif
68 
69 #ifndef RTE_FBK_HASH_INIT_VAL_DEFAULT
70 
71 #define RTE_FBK_HASH_INIT_VAL_DEFAULT 0xFFFFFFFF
72 #endif
73 
75 #define RTE_FBK_HASH_ENTRIES_MAX (1 << 20)
76 
78 #define RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX 256
79 
81 #define RTE_FBK_HASH_NAMESIZE 32
82 
84 typedef uint32_t (*rte_fbk_hash_fn)(uint32_t key, uint32_t init_val);
85 
88  const char *name;
89  uint32_t entries;
90  uint32_t entries_per_bucket;
91  int socket_id;
93  uint32_t init_val;
94 };
95 
98  uint64_t whole_entry;
99  struct {
100  uint16_t is_entry;
101  uint16_t value;
102  uint32_t key;
103  } entry;
104 };
105 
106 
110  uint32_t entries;
112  uint32_t used_entries;
113  uint32_t bucket_mask;
114  uint32_t bucket_shift;
116  uint32_t init_val;
120 };
121 
132 static inline uint32_t
133 rte_fbk_hash_get_bucket(const struct rte_fbk_hash_table *ht, uint32_t key)
134 {
135  return (ht->hash_func(key, ht->init_val) & ht->bucket_mask) <<
136  ht->bucket_shift;
137 }
138 
155 static inline int
157  uint32_t key, uint16_t value, uint32_t bucket)
158 {
159  /*
160  * The writing of a new value to the hash table is done as a single
161  * 64bit operation. This should help prevent individual entries being
162  * corrupted due to race conditions, but it's still possible to
163  * overwrite entries that have just been made valid.
164  */
165  const uint64_t new_entry = ((uint64_t)(key) << 32) |
166  ((uint64_t)(value) << 16) |
167  1; /* 1 = is_entry bit. */
168  uint32_t i;
169 
170  for (i = 0; i < ht->entries_per_bucket; i++) {
171  /* Set entry if unused. */
172  if (! ht->t[bucket + i].entry.is_entry) {
173  ht->t[bucket + i].whole_entry = new_entry;
174  ht->used_entries++;
175  return 0;
176  }
177  /* Change value if key already exists. */
178  if (ht->t[bucket + i].entry.key == key) {
179  ht->t[bucket + i].entry.value = value;
180  return 0;
181  }
182  }
183 
184  return -ENOSPC; /* No space in bucket. */
185 }
186 
200 static inline int
202  uint32_t key, uint16_t value)
203 {
205  key, value, rte_fbk_hash_get_bucket(ht, key));
206 }
207 
222 static inline int
224  uint32_t key, uint32_t bucket)
225 {
226  uint32_t last_entry = ht->entries_per_bucket - 1;
227  uint32_t i, j;
228 
229  for (i = 0; i < ht->entries_per_bucket; i++) {
230  if (ht->t[bucket + i].entry.key == key) {
231  /* Find last key in bucket. */
232  for (j = ht->entries_per_bucket - 1; j > i; j-- ) {
233  if (! ht->t[bucket + j].entry.is_entry) {
234  last_entry = j - 1;
235  }
236  }
237  /*
238  * Move the last key to the deleted key's position, and
239  * delete the last key. lastEntry and i may be same but
240  * it doesn't matter.
241  */
242  ht->t[bucket + i].whole_entry =
243  ht->t[bucket + last_entry].whole_entry;
244  ht->t[bucket + last_entry].whole_entry = 0;
245 
246  ht->used_entries--;
247  return 0;
248  }
249  }
250 
251  return -ENOENT; /* Key didn't exist. */
252 }
253 
265 static inline int
267 {
269  key, rte_fbk_hash_get_bucket(ht, key));
270 }
271 
285 static inline int
287  uint32_t key, uint32_t bucket)
288 {
289  union rte_fbk_hash_entry current_entry;
290  uint32_t i;
291 
292  for (i = 0; i < ht->entries_per_bucket; i++) {
293  /* Single read of entry, which should be atomic. */
294  current_entry.whole_entry = ht->t[bucket + i].whole_entry;
295  if (! current_entry.entry.is_entry) {
296  return -ENOENT; /* Error once we hit an empty field. */
297  }
298  if (current_entry.entry.key == key) {
299  return current_entry.entry.value;
300  }
301  }
302  return -ENOENT; /* Key didn't exist. */
303 }
304 
315 static inline int
316 rte_fbk_hash_lookup(const struct rte_fbk_hash_table *ht, uint32_t key)
317 {
319  key, rte_fbk_hash_get_bucket(ht, key));
320 }
321 
329 static inline void
331 {
332  memset(ht->t, 0, sizeof(ht->t[0]) * ht->entries);
333  ht->used_entries = 0;
334 }
335 
344 static inline double
346 {
347  return (double)ht->used_entries / (double)ht->entries;
348 }
349 
363 
381 struct rte_fbk_hash_table * \
382 rte_fbk_hash_create(const struct rte_fbk_hash_params *params);
383 
391 void rte_fbk_hash_free(struct rte_fbk_hash_table *ht);
392 
393 #ifdef __cplusplus
394 }
395 #endif
396 
397 #endif /* _RTE_FBK_HASH_H_ */
uint16_t is_entry
Definition: rte_fbk_hash.h:100
union rte_fbk_hash_entry t[]
Definition: rte_fbk_hash.h:119
Definition: rte_fbk_hash.h:97
static int rte_fbk_hash_add_key_with_bucket(struct rte_fbk_hash_table *ht, uint32_t key, uint16_t value, uint32_t bucket)
Definition: rte_fbk_hash.h:156
static int rte_fbk_hash_delete_key(struct rte_fbk_hash_table *ht, uint32_t key)
Definition: rte_fbk_hash.h:266
rte_fbk_hash_fn hash_func
Definition: rte_fbk_hash.h:92
static double rte_fbk_hash_get_load_factor(struct rte_fbk_hash_table *ht)
Definition: rte_fbk_hash.h:345
uint32_t(* rte_fbk_hash_fn)(uint32_t key, uint32_t init_val)
Definition: rte_fbk_hash.h:84
void rte_fbk_hash_free(struct rte_fbk_hash_table *ht)
static void rte_fbk_hash_clear_all(struct rte_fbk_hash_table *ht)
Definition: rte_fbk_hash.h:330
static int rte_fbk_hash_lookup_with_bucket(const struct rte_fbk_hash_table *ht, uint32_t key, uint32_t bucket)
Definition: rte_fbk_hash.h:286
uint32_t entries_per_bucket
Definition: rte_fbk_hash.h:90
static uint32_t rte_fbk_hash_get_bucket(const struct rte_fbk_hash_table *ht, uint32_t key)
Definition: rte_fbk_hash.h:133
const char * name
Definition: rte_fbk_hash.h:88
uint32_t key
Definition: rte_fbk_hash.h:102
uint32_t entries_per_bucket
Definition: rte_fbk_hash.h:111
static int rte_fbk_hash_add_key(struct rte_fbk_hash_table *ht, uint32_t key, uint16_t value)
Definition: rte_fbk_hash.h:201
static int rte_fbk_hash_lookup(const struct rte_fbk_hash_table *ht, uint32_t key)
Definition: rte_fbk_hash.h:316
uint64_t whole_entry
Definition: rte_fbk_hash.h:98
char name[RTE_FBK_HASH_NAMESIZE]
Definition: rte_fbk_hash.h:109
uint16_t value
Definition: rte_fbk_hash.h:101
struct rte_fbk_hash_table * rte_fbk_hash_create(const struct rte_fbk_hash_params *params)
struct rte_fbk_hash_entry::@97 entry
#define RTE_FBK_HASH_NAMESIZE
Definition: rte_fbk_hash.h:81
static int rte_fbk_hash_delete_key_with_bucket(struct rte_fbk_hash_table *ht, uint32_t key, uint32_t bucket)
Definition: rte_fbk_hash.h:223
struct rte_fbk_hash_table * rte_fbk_hash_find_existing(const char *name)
rte_fbk_hash_fn hash_func
Definition: rte_fbk_hash.h:115