FD.io VPP  v18.01.1-37-g7ea3975
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 #if defined (__SSE4_2__)
35 #include <immintrin.h>
36 #endif
37 
38 /*
39  * @brief Number of entries per bucket.
40  */
41 #define LBHASH_ENTRY_PER_BUCKET 4
42 
43 #define LB_HASH_DO_NOT_USE_SSE_BUCKETS 0
44 
45 /*
46  * @brief One bucket contains 4 entries.
47  * Each bucket takes one 64B cache line in memory.
48  */
49 typedef struct {
50  CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
56 
57 typedef struct {
60  lb_hash_bucket_t buckets[];
61 } lb_hash_t;
62 
63 #define lb_hash_nbuckets(h) (((h)->buckets_mask) + 1)
64 #define lb_hash_size(h) ((h)->buckets_mask + LBHASH_ENTRY_PER_BUCKET)
65 
66 #define lb_hash_foreach_bucket(h, bucket) \
67  for (bucket = (h)->buckets; \
68  bucket < (h)->buckets + lb_hash_nbuckets(h); \
69  bucket++)
70 
71 #define lb_hash_foreach_entry(h, bucket, i) \
72  lb_hash_foreach_bucket(h, bucket) \
73  for (i = 0; i < LBHASH_ENTRY_PER_BUCKET; i++)
74 
75 #define lb_hash_foreach_valid_entry(h, bucket, i, now) \
76  lb_hash_foreach_entry(h, bucket, i) \
77  if (!clib_u32_loop_gt((now), bucket->timeout[i]))
78 
80 lb_hash_t *lb_hash_alloc(u32 buckets, u32 timeout)
81 {
82  if (!is_pow2(buckets))
83  return NULL;
84 
85  // Allocate 1 more bucket for prefetch
86  u32 size = ((u64)&((lb_hash_t *)(0))->buckets[0]) +
87  sizeof(lb_hash_bucket_t) * (buckets + 1);
88  u8 *mem = 0;
89  lb_hash_t *h;
91  h = (lb_hash_t *)mem;
92  h->buckets_mask = (buckets - 1);
93  h->timeout = timeout;
94  return h;
95 }
96 
99 {
100  u8 *mem = (u8 *)h;
101  vec_free(mem);
102 }
103 
104 #if defined(clib_crc32c_uses_intrinsics) && !defined (__i386__)
106 u32 lb_hash_hash(u64 k0, u64 k1, u64 k2, u64 k3, u64 k4)
107 {
108  u64 val = 0;
109  val = crc32_u64(val, k0);
110  val = crc32_u64(val, k1);
111  val = crc32_u64(val, k2);
112  val = crc32_u64(val, k3);
113  val = crc32_u64(val, k4);
114  return (u32) val;
115 }
116 #else
118 u32 lb_hash_hash(u64 k0, u64 k1, u64 k2, u64 k3, u64 k4)
119 {
120  u64 tmp = k0 ^ k1 ^ k2 ^ k3 ^ k4;
121  return (u32)clib_xxhash (tmp);
122 }
123 #endif
124 
127 {
128  lb_hash_bucket_t *bucket = &ht->buckets[hash & ht->buckets_mask];
129  CLIB_PREFETCH(bucket, sizeof(*bucket), READ);
130 }
131 
133 void lb_hash_get(lb_hash_t *ht, u32 hash, u32 vip, u32 time_now,
134  u32 *available_index, u32 *found_value)
135 {
136  lb_hash_bucket_t *bucket = &ht->buckets[hash & ht->buckets_mask];
137  *found_value = ~0;
138  *available_index = ~0;
139 #if __SSE4_2__ && LB_HASH_DO_NOT_USE_SSE_BUCKETS == 0
140  u32 bitmask, found_index;
141  __m128i mask;
142 
143  // mask[*] = timeout[*] > now
144  mask = _mm_cmpgt_epi32(_mm_loadu_si128 ((__m128i *) bucket->timeout),
145  _mm_set1_epi32 (time_now));
146  // bitmask[*] = now <= timeout[*/4]
147  bitmask = (~_mm_movemask_epi8(mask)) & 0xffff;
148  // Get first index with now <= timeout[*], if any.
149  *available_index = (bitmask)?__builtin_ctz(bitmask)/4:*available_index;
150 
151  // mask[*] = (timeout[*] > now) && (hash[*] == hash)
152  mask = _mm_and_si128(mask,
153  _mm_cmpeq_epi32(
154  _mm_loadu_si128 ((__m128i *) bucket->hash),
155  _mm_set1_epi32 (hash)));
156 
157  // Load the array of vip values
158  // mask[*] = (timeout[*] > now) && (hash[*] == hash) && (vip[*] == vip)
159  mask = _mm_and_si128(mask,
160  _mm_cmpeq_epi32(
161  _mm_loadu_si128 ((__m128i *) bucket->vip),
162  _mm_set1_epi32 (vip)));
163 
164  // mask[*] = (timeout[*x4] > now) && (hash[*x4] == hash) && (vip[*x4] == vip)
165  bitmask = _mm_movemask_epi8(mask);
166  // Get first index, if any
167  found_index = (bitmask)?__builtin_ctzll(bitmask)/4:0;
168  ASSERT(found_index < 4);
169  *found_value = (bitmask)?bucket->value[found_index]:*found_value;
170  bucket->timeout[found_index] =
171  (bitmask)?time_now + ht->timeout:bucket->timeout[found_index];
172 #else
173  u32 i;
174  for (i = 0; i < LBHASH_ENTRY_PER_BUCKET; i++) {
175  u8 cmp = (bucket->hash[i] == hash && bucket->vip[i] == vip);
176  u8 timeouted = clib_u32_loop_gt(time_now, bucket->timeout[i]);
177  *found_value = (cmp || timeouted)?*found_value:bucket->value[i];
178  bucket->timeout[i] = (cmp || timeouted)?time_now + ht->timeout:bucket->timeout[i];
179  *available_index = (timeouted && (*available_index == ~0))?i:*available_index;
180 
181  if (!cmp)
182  return;
183  }
184 #endif
185 }
186 
188 u32 lb_hash_available_value(lb_hash_t *h, u32 hash, u32 available_index)
189 {
190  return h->buckets[hash & h->buckets_mask].value[available_index];
191 }
192 
194 void lb_hash_put(lb_hash_t *h, u32 hash, u32 value, u32 vip,
195  u32 available_index, u32 time_now)
196 {
197  lb_hash_bucket_t *bucket = &h->buckets[hash & h->buckets_mask];
198  bucket->hash[available_index] = hash;
199  bucket->value[available_index] = value;
200  bucket->timeout[available_index] = time_now + h->timeout;
201  bucket->vip[available_index] = vip;
202 }
203 
206 {
207  u32 tot = 0;
208  lb_hash_bucket_t *bucket;
209  u32 i;
210  lb_hash_foreach_valid_entry(h, bucket, i, time_now) {
211  tot++;
212  }
213  return tot;
214 }
215 
216 #endif /* LB_PLUGIN_LB_LBHASH_H_ */
#define lb_hash_foreach_valid_entry(h, bucket, i, now)
Definition: lbhash.h:75
#define CLIB_CACHE_LINE_ALIGN_MARK(mark)
Definition: cache.h:68
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:337
#define LBHASH_ENTRY_PER_BUCKET
vppinfra already includes tons of different hash tables.
Definition: lbhash.h:41
#define NULL
Definition: clib.h:55
static_always_inline lb_hash_t * lb_hash_alloc(u32 buckets, u32 timeout)
Definition: lbhash.h:80
static u64 clib_xxhash(u64 key)
Definition: xxhash.h:58
static_always_inline u32 lb_hash_available_value(lb_hash_t *h, u32 hash, u32 available_index)
Definition: lbhash.h:188
u32 vip[LBHASH_ENTRY_PER_BUCKET]
Definition: lbhash.h:53
u32 buckets_mask
Definition: lbhash.h:58
u32 timeout
Definition: lbhash.h:59
#define static_always_inline
Definition: clib.h:93
unsigned long u64
Definition: types.h:89
u32 timeout[LBHASH_ENTRY_PER_BUCKET]
Definition: lbhash.h:52
u32 value[LBHASH_ENTRY_PER_BUCKET]
Definition: lbhash.h:54
lb_hash_bucket_t buckets[]
Definition: lbhash.h:60
#define vec_alloc_aligned(V, N, A)
Allocate space for N more elements (no header, given alignment)
Definition: vec.h:284
static_always_inline void lb_hash_prefetch_bucket(lb_hash_t *ht, u32 hash)
Definition: lbhash.h:126
#define clib_u32_loop_gt(a, b)
32 bits integer comparison for running values.
Definition: kphash.h:47
#define CLIB_PREFETCH(addr, size, type)
Definition: cache.h:82
vec_header_t h
Definition: buffer.c:282
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:336
static_always_inline void lb_hash_free(lb_hash_t *h)
Definition: lbhash.h:98
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
u64 size
Definition: vhost-user.h:76
static uword is_pow2(uword x)
Definition: clib.h:280
unsigned char u8
Definition: types.h:56
u32 hash[LBHASH_ENTRY_PER_BUCKET]
Definition: lbhash.h:51
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:67
static_always_inline void lb_hash_get(lb_hash_t *ht, u32 hash, u32 vip, u32 time_now, u32 *available_index, u32 *found_value)
Definition: lbhash.h:133
static_always_inline u32 lb_hash_hash(u64 k0, u64 k1, u64 k2, u64 k3, u64 k4)
Definition: lbhash.h:118
static_always_inline void lb_hash_put(lb_hash_t *h, u32 hash, u32 value, u32 vip, u32 available_index, u32 time_now)
Definition: lbhash.h:194
static_always_inline u32 lb_hash_elts(lb_hash_t *h, u32 time_now)
Definition: lbhash.h:205