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