FD.io VPP  v18.01.1-37-g7ea3975
Vector Packet Processing
kphash.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2017 Intel 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 KP_PLUGIN_KP_KPHASH_H_
30 #define KP_PLUGIN_KP_KPHASH_H_
31 
32 #include <vnet/vnet.h>
33 #include <vppinfra/xxhash.h>
34 #include <vppinfra/crc32.h>
35 
36 /*
37  * @brief Number of entries per bucket.
38  */
39 #define KPHASH_ENTRY_PER_BUCKET 4
40 
41 #define KP_HASH_DO_NOT_USE_SSE_BUCKETS 0
42 
43 /**
44  * 32 bits integer comparison for running values.
45  * 1 > 0 is true. But 1 > 0xffffffff also is.
46  */
47 #define clib_u32_loop_gt(a, b) (((u32)(a)) - ((u32)(b)) < 0x7fffffff)
48 
49 /*
50  * @brief One bucket contains 4 entries.
51  * Each bucket takes one 64B cache line in memory.
52  */
53 typedef struct {
54  CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
60 
61 typedef struct {
64  kp_hash_bucket_t buckets[];
65 } kp_hash_t;
66 
67 #define kp_hash_nbuckets(h) (((h)->buckets_mask) + 1)
68 #define kp_hash_size(h) ((h)->buckets_mask + KPHASH_ENTRY_PER_BUCKET)
69 
70 #define kp_hash_foreach_bucket(h, bucket) \
71  for (bucket = (h)->buckets; \
72  bucket < (h)->buckets + kp_hash_nbuckets(h); \
73  bucket++)
74 
75 #define kp_hash_foreach_entry(h, bucket, i) \
76  kp_hash_foreach_bucket(h, bucket) \
77  for (i = 0; i < KPHASH_ENTRY_PER_BUCKET; i++)
78 
79 #define kp_hash_foreach_valid_entry(h, bucket, i, now) \
80  kp_hash_foreach_entry(h, bucket, i) \
81  if (!clib_u32_loop_gt((now), bucket->timeout[i]))
82 
84 kp_hash_t *kp_hash_alloc(u32 buckets, u32 timeout)
85 {
86  if (!is_pow2(buckets))
87  return NULL;
88 
89  // Allocate 1 more bucket for prefetch
90  u32 size = ((u64)&((kp_hash_t *)(0))->buckets[0]) +
91  sizeof(kp_hash_bucket_t) * (buckets + 1);
92  u8 *mem = 0;
93  kp_hash_t *h;
95  h = (kp_hash_t *)mem;
96  h->buckets_mask = (buckets - 1);
97  h->timeout = timeout;
98  return h;
99 }
100 
103 {
104  u8 *mem = (u8 *)h;
105  vec_free(mem);
106 }
107 
109 u32 kp_hash_hash(u64 k0, u64 k1, u64 k2, u64 k3, u64 k4)
110 {
111 #ifdef clib_crc32c_uses_intrinsics
112  u64 key[5];
113  key[0] = k0;
114  key[1] = k1;
115  key[2] = k2;
116  key[3] = k3;
117  key[4] = k4;
118  return clib_crc32c ((u8 *) key, 40);
119 #else
120  u64 tmp = k0 ^ k1 ^ k2 ^ k3 ^ k4;
121  return (u32)clib_xxhash (tmp);
122 #endif
123 }
124 
127 {
128  kp_hash_bucket_t *bucket = &ht->buckets[hash & ht->buckets_mask];
129  CLIB_PREFETCH(bucket, sizeof(*bucket), READ);
130 }
131 
133 void kp_hash_get(kp_hash_t *ht, u32 hash, u32 vip, u32 time_now,
134  u32 *available_index, u32 *found_value)
135 {
136  kp_hash_bucket_t *bucket = &ht->buckets[hash & ht->buckets_mask];
137  *found_value = ~0;
138  *available_index = ~0;
139 #if __SSE4_2__ && KP_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 < KPHASH_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 kp_hash_available_value(kp_hash_t *h, u32 hash, u32 available_index)
189 {
190  return h->buckets[hash & h->buckets_mask].value[available_index];
191 }
192 
194 void kp_hash_put(kp_hash_t *h, u32 hash, u32 value, u32 vip,
195  u32 available_index, u32 time_now)
196 {
197  kp_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  kp_hash_bucket_t *bucket;
209  u32 i;
210  kp_hash_foreach_valid_entry(h, bucket, i, time_now) {
211  tot++;
212  }
213  return tot;
214 }
215 
216 #endif /* KP_PLUGIN_KP_KPHASH_H_ */
#define KPHASH_ENTRY_PER_BUCKET
vppinfra already includes tons of different hash tables.
Definition: kphash.h:39
#define CLIB_CACHE_LINE_ALIGN_MARK(mark)
Definition: cache.h:68
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:337
u32 buckets_mask
Definition: kphash.h:62
#define NULL
Definition: clib.h:55
static u64 clib_xxhash(u64 key)
Definition: xxhash.h:58
u32 timeout[KPHASH_ENTRY_PER_BUCKET]
Definition: kphash.h:56
#define static_always_inline
Definition: clib.h:93
unsigned long u64
Definition: types.h:89
static_always_inline void kp_hash_free(kp_hash_t *h)
Definition: kphash.h:102
static_always_inline kp_hash_t * kp_hash_alloc(u32 buckets, u32 timeout)
Definition: kphash.h:84
#define kp_hash_foreach_valid_entry(h, bucket, i, now)
Definition: kphash.h:79
#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 kp_hash_prefetch_bucket(kp_hash_t *ht, u32 hash)
Definition: kphash.h:126
#define clib_u32_loop_gt(a, b)
32 bits integer comparison for running values.
Definition: kphash.h:47
static_always_inline void kp_hash_put(kp_hash_t *h, u32 hash, u32 value, u32 vip, u32 available_index, u32 time_now)
Definition: kphash.h:194
#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 u32 kp_hash_elts(kp_hash_t *h, u32 time_now)
Definition: kphash.h:205
u32 vip[KPHASH_ENTRY_PER_BUCKET]
Definition: kphash.h:57
static_always_inline u32 kp_hash_available_value(kp_hash_t *h, u32 hash, u32 available_index)
Definition: kphash.h:188
#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
u32 value[KPHASH_ENTRY_PER_BUCKET]
Definition: kphash.h:58
static_always_inline void kp_hash_get(kp_hash_t *ht, u32 hash, u32 vip, u32 time_now, u32 *available_index, u32 *found_value)
Definition: kphash.h:133
unsigned char u8
Definition: types.h:56
u32 timeout
Definition: kphash.h:63
static_always_inline u32 kp_hash_hash(u64 k0, u64 k1, u64 k2, u64 k3, u64 k4)
Definition: kphash.h:109
kp_hash_bucket_t buckets[]
Definition: kphash.h:64
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:67
u32 hash[KPHASH_ENTRY_PER_BUCKET]
Definition: kphash.h:55