DPDK  16.11.11
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 #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>
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 
70 #define RTE_FBK_HASH_INIT_VAL_DEFAULT 0xFFFFFFFF
71 #endif
72 
74 #define RTE_FBK_HASH_ENTRIES_MAX (1 << 20)
75 
77 #define RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX 256
78 
80 #define RTE_FBK_HASH_NAMESIZE 32
81 
83 typedef uint32_t (*rte_fbk_hash_fn)(uint32_t key, uint32_t init_val);
84 
87  const char *name;
88  uint32_t entries;
89  uint32_t entries_per_bucket;
90  int socket_id;
92  uint32_t init_val;
93 };
94 
97  uint64_t whole_entry;
98  struct {
99  uint16_t is_entry;
100  uint16_t value;
101  uint32_t key;
102  } entry;
103 };
104 
105 
109  uint32_t entries;
111  uint32_t used_entries;
112  uint32_t bucket_mask;
113  uint32_t bucket_shift;
115  uint32_t init_val;
119 };
120 
131 static inline uint32_t
132 rte_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 
154 static inline int
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 
199 static inline int
201  uint32_t key, uint16_t value)
202 {
204  key, value, rte_fbk_hash_get_bucket(ht, key));
205 }
206 
221 static inline int
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 
264 static inline int
266 {
268  key, rte_fbk_hash_get_bucket(ht, key));
269 }
270 
284 static inline int
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 
314 static inline int
315 rte_fbk_hash_lookup(const struct rte_fbk_hash_table *ht, uint32_t key)
316 {
318  key, rte_fbk_hash_get_bucket(ht, key));
319 }
320 
328 static inline void
330 {
331  memset(ht->t, 0, sizeof(ht->t[0]) * ht->entries);
332  ht->used_entries = 0;
333 }
334 
343 static inline double
345 {
346  return (double)ht->used_entries / (double)ht->entries;
347 }
348 
362 
380 struct rte_fbk_hash_table * \
381 rte_fbk_hash_create(const struct rte_fbk_hash_params *params);
382 
390 void rte_fbk_hash_free(struct rte_fbk_hash_table *ht);
391 
392 #ifdef __cplusplus
393 }
394 #endif
395 
396 #endif /* _RTE_FBK_HASH_H_ */
uint16_t is_entry
Definition: rte_fbk_hash.h:99
union rte_fbk_hash_entry t[]
Definition: rte_fbk_hash.h:118
Definition: rte_fbk_hash.h:96
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:155
static int rte_fbk_hash_delete_key(struct rte_fbk_hash_table *ht, uint32_t key)
Definition: rte_fbk_hash.h:265
rte_fbk_hash_fn hash_func
Definition: rte_fbk_hash.h:91
static double rte_fbk_hash_get_load_factor(struct rte_fbk_hash_table *ht)
Definition: rte_fbk_hash.h:344
uint32_t(* rte_fbk_hash_fn)(uint32_t key, uint32_t init_val)
Definition: rte_fbk_hash.h:83
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:329
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:285
uint32_t entries_per_bucket
Definition: rte_fbk_hash.h:89
static uint32_t rte_fbk_hash_get_bucket(const struct rte_fbk_hash_table *ht, uint32_t key)
Definition: rte_fbk_hash.h:132
const char * name
Definition: rte_fbk_hash.h:87
uint32_t key
Definition: rte_fbk_hash.h:101
uint32_t entries_per_bucket
Definition: rte_fbk_hash.h:110
static int rte_fbk_hash_add_key(struct rte_fbk_hash_table *ht, uint32_t key, uint16_t value)
Definition: rte_fbk_hash.h:200
static int rte_fbk_hash_lookup(const struct rte_fbk_hash_table *ht, uint32_t key)
Definition: rte_fbk_hash.h:315
uint64_t whole_entry
Definition: rte_fbk_hash.h:97
char name[RTE_FBK_HASH_NAMESIZE]
Definition: rte_fbk_hash.h:108
struct rte_fbk_hash_entry::@54 entry
uint16_t value
Definition: rte_fbk_hash.h:100
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:80
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:222
struct rte_fbk_hash_table * rte_fbk_hash_find_existing(const char *name)
rte_fbk_hash_fn hash_func
Definition: rte_fbk_hash.h:114