FD.io VPP  v18.04-17-g3a0d853
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 #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 = ((u64)&((lb_hash_t *)(0))->buckets[0]) +
88  sizeof(lb_hash_bucket_t) * (buckets + 1);
89  u8 *mem = 0;
90  lb_hash_t *h;
92  h = (lb_hash_t *)mem;
93  h->buckets_mask = (buckets - 1);
94  h->timeout = timeout;
95  return h;
96 }
97 
100 {
101  u8 *mem = (u8 *)h;
102  vec_free(mem);
103 }
104 
107 {
108  lb_hash_bucket_t *bucket = &ht->buckets[hash & ht->buckets_mask];
109  CLIB_PREFETCH(bucket, sizeof(*bucket), READ);
110 }
111 
113 void lb_hash_get(lb_hash_t *ht, u32 hash, u32 vip, u32 time_now,
114  u32 *available_index, u32 *found_value)
115 {
116  lb_hash_bucket_t *bucket = &ht->buckets[hash & ht->buckets_mask];
117  *found_value = ~0;
118  *available_index = ~0;
119 #if __SSE4_2__ && LB_HASH_DO_NOT_USE_SSE_BUCKETS == 0
120  u32 bitmask, found_index;
121  __m128i mask;
122 
123  // mask[*] = timeout[*] > now
124  mask = _mm_cmpgt_epi32(_mm_loadu_si128 ((__m128i *) bucket->timeout),
125  _mm_set1_epi32 (time_now));
126  // bitmask[*] = now <= timeout[*/4]
127  bitmask = (~_mm_movemask_epi8(mask)) & 0xffff;
128  // Get first index with now <= timeout[*], if any.
129  *available_index = (bitmask)?__builtin_ctz(bitmask)/4:*available_index;
130 
131  // mask[*] = (timeout[*] > now) && (hash[*] == hash)
132  mask = _mm_and_si128(mask,
133  _mm_cmpeq_epi32(
134  _mm_loadu_si128 ((__m128i *) bucket->hash),
135  _mm_set1_epi32 (hash)));
136 
137  // Load the array of vip values
138  // mask[*] = (timeout[*] > now) && (hash[*] == hash) && (vip[*] == vip)
139  mask = _mm_and_si128(mask,
140  _mm_cmpeq_epi32(
141  _mm_loadu_si128 ((__m128i *) bucket->vip),
142  _mm_set1_epi32 (vip)));
143 
144  // mask[*] = (timeout[*x4] > now) && (hash[*x4] == hash) && (vip[*x4] == vip)
145  bitmask = _mm_movemask_epi8(mask);
146  // Get first index, if any
147  found_index = (bitmask)?__builtin_ctzll(bitmask)/4:0;
148  ASSERT(found_index < 4);
149  *found_value = (bitmask)?bucket->value[found_index]:*found_value;
150  bucket->timeout[found_index] =
151  (bitmask)?time_now + ht->timeout:bucket->timeout[found_index];
152 #else
153  u32 i;
154  for (i = 0; i < LBHASH_ENTRY_PER_BUCKET; i++) {
155  u8 cmp = (bucket->hash[i] == hash && bucket->vip[i] == vip);
156  u8 timeouted = clib_u32_loop_gt(time_now, bucket->timeout[i]);
157  *found_value = (cmp || timeouted)?*found_value:bucket->value[i];
158  bucket->timeout[i] = (cmp || timeouted)?time_now + ht->timeout:bucket->timeout[i];
159  *available_index = (timeouted && (*available_index == ~0))?i:*available_index;
160 
161  if (!cmp)
162  return;
163  }
164 #endif
165 }
166 
168 u32 lb_hash_available_value(lb_hash_t *h, u32 hash, u32 available_index)
169 {
170  return h->buckets[hash & h->buckets_mask].value[available_index];
171 }
172 
174 void lb_hash_put(lb_hash_t *h, u32 hash, u32 value, u32 vip,
175  u32 available_index, u32 time_now)
176 {
177  lb_hash_bucket_t *bucket = &h->buckets[hash & h->buckets_mask];
178  bucket->hash[available_index] = hash;
179  bucket->value[available_index] = value;
180  bucket->timeout[available_index] = time_now + h->timeout;
181  bucket->vip[available_index] = vip;
182 }
183 
186 {
187  u32 tot = 0;
188  lb_hash_bucket_t *bucket;
189  u32 i;
190  lb_hash_foreach_valid_entry(h, bucket, i, time_now) {
191  tot++;
192  }
193  return tot;
194 }
195 
196 #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
#define NULL
Definition: clib.h:55
static_always_inline lb_hash_t * lb_hash_alloc(u32 buckets, u32 timeout)
Definition: lbhash.h:81
int i
static_always_inline u32 lb_hash_available_value(lb_hash_t *h, u32 hash, u32 available_index)
Definition: lbhash.h:168
u32 vip[LBHASH_ENTRY_PER_BUCKET]
Definition: lbhash.h:54
u32 buckets_mask
Definition: lbhash.h:59
u32 timeout
Definition: lbhash.h:60
#define static_always_inline
Definition: clib.h:93
unsigned long u64
Definition: types.h:89
u32 timeout[LBHASH_ENTRY_PER_BUCKET]
Definition: lbhash.h:53
u32 size
u32 value[LBHASH_ENTRY_PER_BUCKET]
Definition: lbhash.h:55
lb_hash_bucket_t buckets[]
Definition: lbhash.h:61
#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:106
#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:74
#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:99
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
static uword is_pow2(uword x)
Definition: clib.h:280
unsigned char u8
Definition: types.h:56
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:113
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:174
static_always_inline u32 lb_hash_elts(lb_hash_t *h, u32 time_now)
Definition: lbhash.h:185