DPDK  18.11.11
rte_fbk_hash.h
Go to the documentation of this file.
1 /* SPDX-License-Identifier: BSD-3-Clause
2  * Copyright(c) 2010-2014 Intel Corporation
3  */
4 
5 #ifndef _RTE_FBK_HASH_H_
6 #define _RTE_FBK_HASH_H_
7 
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 
28 #include <rte_config.h>
29 #include <rte_hash_crc.h>
30 #include <rte_jhash.h>
31 
32 #ifndef RTE_FBK_HASH_INIT_VAL_DEFAULT
33 
34 #define RTE_FBK_HASH_INIT_VAL_DEFAULT 0xFFFFFFFF
35 #endif
36 
38 #define RTE_FBK_HASH_ENTRIES_MAX (1 << 20)
39 
41 #define RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX 256
42 
44 #define RTE_FBK_HASH_NAMESIZE 32
45 
47 typedef uint32_t (*rte_fbk_hash_fn)(uint32_t key, uint32_t init_val);
48 
51  const char *name;
52  uint32_t entries;
53  uint32_t entries_per_bucket;
54  int socket_id;
56  uint32_t init_val;
57 };
58 
61  uint64_t whole_entry;
62  struct {
63  uint16_t is_entry;
64  uint16_t value;
65  uint32_t key;
66  } entry;
67 };
68 
69 
73  uint32_t entries;
74  uint32_t entries_per_bucket;
75  uint32_t used_entries;
76  uint32_t bucket_mask;
77  uint32_t bucket_shift;
79  uint32_t init_val;
83 };
84 
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 
118 static inline int
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 
163 static inline int
165  uint32_t key, uint16_t value)
166 {
168  key, value, rte_fbk_hash_get_bucket(ht, key));
169 }
170 
185 static inline int
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 
228 static inline int
230 {
232  key, rte_fbk_hash_get_bucket(ht, key));
233 }
234 
248 static inline int
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 
278 static inline int
279 rte_fbk_hash_lookup(const struct rte_fbk_hash_table *ht, uint32_t key)
280 {
282  key, rte_fbk_hash_get_bucket(ht, key));
283 }
284 
292 static inline void
294 {
295  memset(ht->t, 0, sizeof(ht->t[0]) * ht->entries);
296  ht->used_entries = 0;
297 }
298 
307 static inline double
309 {
310  return (double)ht->used_entries / (double)ht->entries;
311 }
312 
326 
344 struct rte_fbk_hash_table * \
345 rte_fbk_hash_create(const struct rte_fbk_hash_params *params);
346 
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_ */
uint16_t is_entry
Definition: rte_fbk_hash.h:63
union rte_fbk_hash_entry t[]
Definition: rte_fbk_hash.h:82
uint32_t used_entries
Definition: rte_fbk_hash.h:75
Definition: rte_fbk_hash.h:60
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:119
static int rte_fbk_hash_delete_key(struct rte_fbk_hash_table *ht, uint32_t key)
Definition: rte_fbk_hash.h:229
rte_fbk_hash_fn hash_func
Definition: rte_fbk_hash.h:55
static double rte_fbk_hash_get_load_factor(struct rte_fbk_hash_table *ht)
Definition: rte_fbk_hash.h:308
uint32_t(* rte_fbk_hash_fn)(uint32_t key, uint32_t init_val)
Definition: rte_fbk_hash.h:47
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:293
struct rte_fbk_hash_entry::@156 entry
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:249
uint32_t entries_per_bucket
Definition: rte_fbk_hash.h:53
static uint32_t rte_fbk_hash_get_bucket(const struct rte_fbk_hash_table *ht, uint32_t key)
Definition: rte_fbk_hash.h:96
const char * name
Definition: rte_fbk_hash.h:51
uint32_t key
Definition: rte_fbk_hash.h:65
uint32_t entries_per_bucket
Definition: rte_fbk_hash.h:74
static int rte_fbk_hash_add_key(struct rte_fbk_hash_table *ht, uint32_t key, uint16_t value)
Definition: rte_fbk_hash.h:164
static int rte_fbk_hash_lookup(const struct rte_fbk_hash_table *ht, uint32_t key)
Definition: rte_fbk_hash.h:279
uint32_t bucket_mask
Definition: rte_fbk_hash.h:76
uint64_t whole_entry
Definition: rte_fbk_hash.h:61
char name[RTE_FBK_HASH_NAMESIZE]
Definition: rte_fbk_hash.h:72
uint16_t value
Definition: rte_fbk_hash.h:64
struct rte_fbk_hash_table * rte_fbk_hash_create(const struct rte_fbk_hash_params *params)
#define RTE_FBK_HASH_NAMESIZE
Definition: rte_fbk_hash.h:44
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:186
uint32_t bucket_shift
Definition: rte_fbk_hash.h:77
struct rte_fbk_hash_table * rte_fbk_hash_find_existing(const char *name)
rte_fbk_hash_fn hash_func
Definition: rte_fbk_hash.h:78