FD.io VPP  v16.09
Vector Packet Processing
lbhash.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2012 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 /**
17  * vppinfra already includes tons of different hash tables.
18  * MagLev flow table is a bit different. It has to be very efficient
19  * for both writing and reading operations. But it does not need to
20  * be 100% reliable (write can fail). It also needs to recycle
21  * old entries in a lazy way.
22  *
23  * This hash table is the most dummy hash table you can do.
24  * Fixed total size, fixed bucket size.
25  * Advantage is that it could be very efficient (maybe).
26  *
27  */
28 
29 #ifndef LB_PLUGIN_LB_LBHASH_H_
30 #define LB_PLUGIN_LB_LBHASH_H_
31 
32 #include <vnet/vnet.h>
33 
34 #define LBHASH_ENTRY_PER_BUCKET_LOG2 2
35 #define LBHASH_ENTRY_PER_BUCKET (1 << LBHASH_ENTRY_PER_BUCKET_LOG2)
36 #define LBHASH_ENTRY_PER_BUCKET_MASK (LBHASH_ENTRY_PER_BUCKET - 1)
37 
38 typedef struct {
39  u64 key[5];
43 
44 typedef struct {
47  lb_hash_entry_t entries[];
48 } lb_hash_t;
49 
50 #define lb_hash_nbuckets(h) (((h)->buckets_mask >> LBHASH_ENTRY_PER_BUCKET_LOG2) + 1)
51 #define lb_hash_size(h) ((h)->buckets_mask + LBHASH_ENTRY_PER_BUCKET)
52 
53 #define lb_hash_foreach_entry(h, e) \
54  for (e = (h)->entries; e < h->entries + lb_hash_size(h); e++)
55 
56 #define lb_hash_foreach_valid_entry(h, e, now) \
57  lb_hash_foreach_entry(h, e) \
58  if (!clib_u32_loop_gt((now), (e)->last_seen + (h)->timeout))
59 
61 lb_hash_t *lb_hash_alloc(u32 buckets, u32 timeout)
62 {
63  if ((!is_pow2(buckets)) ||
64  ((buckets << LBHASH_ENTRY_PER_BUCKET_LOG2) == 0))
65  return NULL;
66 
67  // Allocate 1 more bucket for prefetch
68  u32 size = sizeof(lb_hash_t) + ((buckets << LBHASH_ENTRY_PER_BUCKET_LOG2) + 1)* sizeof(lb_hash_entry_t);
69  u8 *mem = 0;
70  lb_hash_t *h;
72  h = (lb_hash_t *)mem;
73  h->buckets_mask = (buckets - 1) << LBHASH_ENTRY_PER_BUCKET_LOG2;
74  h->timeout = timeout;
75  return h;
76 }
77 
80 {
81  vec_free(h);
82 }
83 
84 #if __SSE4_2__
86 u32 lb_hash_crc_u32(u32 data, u32 value)
87 {
88  __asm__ volatile( "crc32l %[data], %[value];"
89  : [value] "+r" (value)
90  : [data] "rm" (data));
91  return value;
92 }
93 
95 u32 lb_hash_hash(u64 k[5])
96 {
97  u32 * dp = (u32 *) k;
98  u32 value = 0;
99 
100  value = lb_hash_crc_u32 (dp[0], value);
101  value = lb_hash_crc_u32 (dp[1], value);
102  value = lb_hash_crc_u32 (dp[2], value);
103  value = lb_hash_crc_u32 (dp[3], value);
104  value = lb_hash_crc_u32 (dp[4], value);
105  value = lb_hash_crc_u32 (dp[5], value);
106  value = lb_hash_crc_u32 (dp[6], value);
107  value = lb_hash_crc_u32 (dp[7], value);
108  value = lb_hash_crc_u32 (dp[8], value);
109  value = lb_hash_crc_u32 (dp[9], value);
110  return value;
111 }
112 #else
115 {
116  u64 tmp = k[0] ^ k[1] ^ k[2] ^ k[3] ^ k[4];
117  return (u32)clib_xxhash (tmp);
118 }
119 #endif
120 
121 
122 
124 void lb_hash_get(lb_hash_t *h, u64 k[5], u32 hash, u32 time_now, u32 *available_index, u32 *value)
125 {
126  lb_hash_entry_t *e = &h->entries[hash & h->buckets_mask];
127  u32 i;
128  *value = ~0;
129  *available_index = ~0;
130  CLIB_PREFETCH (&(e[1]), sizeof(lb_hash_entry_t), STORE);
131  for (i=0; i<LBHASH_ENTRY_PER_BUCKET; i++) {
132  CLIB_PREFETCH (&(e[i+2]), sizeof(lb_hash_entry_t), STORE); //+2 somehow performs best
133  u64 cmp =
134  (e[i].key[0] ^ k[0]) |
135  (e[i].key[1] ^ k[1]) |
136  (e[i].key[2] ^ k[2]) |
137  (e[i].key[3] ^ k[3]) |
138  (e[i].key[4] ^ k[4]);
139 
140  u8 timeouted = clib_u32_loop_gt(time_now, e[i].last_seen + h->timeout);
141 
142  *value = (cmp || timeouted)?*value:e[i].value;
143  e[i].last_seen = (cmp || timeouted)?e[i].last_seen:time_now;
144  *available_index = (timeouted && (*available_index == ~0))?(&e[i] - h->entries):*available_index;
145 
146  if (!cmp)
147  return;
148  }
149 }
150 
153 {
154  return h->entries[available_index].value;
155 }
156 
158 u32 lb_hash_put(lb_hash_t *h, u64 k[5], u32 value, u32 available_index, u32 time_now)
159 {
160  lb_hash_entry_t *e = &h->entries[available_index];
161  e->key[0] = k[0];
162  e->key[1] = k[1];
163  e->key[2] = k[2];
164  e->key[3] = k[3];
165  e->key[4] = k[4];
166  e->value = value;
167  e->last_seen = time_now;
168  return 0;
169 }
170 
173 {
174  u32 tot = 0;
175  lb_hash_entry_t *e;
176  lb_hash_foreach_valid_entry(h, e, time_now) {
177  tot++;
178  }
179  return tot;
180 }
181 
182 #endif /* LB_PLUGIN_LB_LBHASH_H_ */
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
#define LBHASH_ENTRY_PER_BUCKET
Definition: lbhash.h:35
#define NULL
Definition: clib.h:55
static_always_inline lb_hash_t * lb_hash_alloc(u32 buckets, u32 timeout)
Definition: lbhash.h:61
#define clib_u32_loop_gt(a, b)
32 bits integer comparison for running values.
Definition: util.h:38
static u64 clib_xxhash(u64 key)
Definition: xxhash.h:58
static_always_inline u32 lb_hash_put(lb_hash_t *h, u64 k[5], u32 value, u32 available_index, u32 time_now)
Definition: lbhash.h:158
u32 buckets_mask
Definition: lbhash.h:45
u32 timeout
Definition: lbhash.h:46
#define static_always_inline
Definition: clib.h:85
lb_hash_entry_t entries[]
Definition: lbhash.h:47
u64 key[5]
Definition: lbhash.h:39
unsigned long u64
Definition: types.h:89
#define lb_hash_foreach_valid_entry(h, e, now)
Definition: lbhash.h:56
Definition: lbhash.h:38
u32 value
Definition: lbhash.h:40
static_always_inline void lb_hash_get(lb_hash_t *h, u64 k[5], u32 hash, u32 time_now, u32 *available_index, u32 *value)
Definition: lbhash.h:124
#define vec_alloc_aligned(V, N, A)
Allocate space for N more elements (no header, given alignment)
Definition: vec.h:248
#define CLIB_PREFETCH(addr, size, type)
Definition: cache.h:82
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:300
static_always_inline u32 lb_hash_available_value(lb_hash_t *h, u32 available_index)
Definition: lbhash.h:152
static_always_inline void lb_hash_free(lb_hash_t *h)
Definition: lbhash.h:79
unsigned int u32
Definition: types.h:88
u32 size
Definition: vhost-user.h:77
static uword is_pow2(uword x)
Definition: clib.h:266
static_always_inline u32 lb_hash_hash(u64 k[5])
Definition: lbhash.h:114
u32 last_seen
Definition: lbhash.h:41
unsigned char u8
Definition: types.h:56
#define LBHASH_ENTRY_PER_BUCKET_LOG2
vppinfra already includes tons of different hash tables.
Definition: lbhash.h:34
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:67
static_always_inline u32 lb_hash_elts(lb_hash_t *h, u32 time_now)
Definition: lbhash.h:172