29 #ifndef LB_PLUGIN_LB_LBHASH_H_ 30 #define LB_PLUGIN_LB_LBHASH_H_ 34 #if defined (__SSE4_2__) 35 #include <immintrin.h> 41 #define LBHASH_ENTRY_PER_BUCKET 4 43 #define LB_HASH_DO_NOT_USE_SSE_BUCKETS 0 63 #define lb_hash_nbuckets(h) (((h)->buckets_mask) + 1) 64 #define lb_hash_size(h) ((h)->buckets_mask + LBHASH_ENTRY_PER_BUCKET) 66 #define lb_hash_foreach_bucket(h, bucket) \ 67 for (bucket = (h)->buckets; \ 68 bucket < (h)->buckets + lb_hash_nbuckets(h); \ 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++) 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])) 104 #if defined(clib_crc32c_uses_intrinsics) && !defined (__i386__) 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);
120 u64 tmp = k0 ^ k1 ^ k2 ^ k3 ^ k4;
134 u32 *available_index,
u32 *found_value)
138 *available_index = ~0;
139 #if __SSE4_2__ && LB_HASH_DO_NOT_USE_SSE_BUCKETS == 0 140 u32 bitmask, found_index;
144 mask = _mm_cmpgt_epi32(_mm_loadu_si128 ((__m128i *) bucket->
timeout),
145 _mm_set1_epi32 (time_now));
147 bitmask = (~_mm_movemask_epi8(mask)) & 0xffff;
149 *available_index = (bitmask)?__builtin_ctz(bitmask)/4:*available_index;
152 mask = _mm_and_si128(mask,
154 _mm_loadu_si128 ((__m128i *) bucket->
hash),
155 _mm_set1_epi32 (hash)));
159 mask = _mm_and_si128(mask,
161 _mm_loadu_si128 ((__m128i *) bucket->
vip),
162 _mm_set1_epi32 (vip)));
165 bitmask = _mm_movemask_epi8(mask);
167 found_index = (bitmask)?__builtin_ctzll(bitmask)/4:0;
169 *found_value = (bitmask)?bucket->
value[found_index]:*found_value;
175 u8 cmp = (bucket->
hash[
i] == hash && bucket->
vip[
i] == vip);
177 *found_value = (cmp || timeouted)?*found_value:bucket->
value[i];
179 *available_index = (timeouted && (*available_index == ~0))?i:*available_index;
195 u32 available_index,
u32 time_now)
198 bucket->
hash[available_index] = hash;
199 bucket->
value[available_index] = value;
201 bucket->
vip[available_index] = vip;
#define lb_hash_foreach_valid_entry(h, bucket, i, now)
#define CLIB_CACHE_LINE_ALIGN_MARK(mark)
sll srl srl sll sra u16x4 i
#define LBHASH_ENTRY_PER_BUCKET
vppinfra already includes tons of different hash tables.
static_always_inline lb_hash_t * lb_hash_alloc(u32 buckets, u32 timeout)
static u64 clib_xxhash(u64 key)
static_always_inline u32 lb_hash_available_value(lb_hash_t *h, u32 hash, u32 available_index)
u32 vip[LBHASH_ENTRY_PER_BUCKET]
#define static_always_inline
u32 timeout[LBHASH_ENTRY_PER_BUCKET]
u32 value[LBHASH_ENTRY_PER_BUCKET]
lb_hash_bucket_t buckets[]
#define vec_alloc_aligned(V, N, A)
Allocate space for N more elements (no header, given alignment)
static_always_inline void lb_hash_prefetch_bucket(lb_hash_t *ht, u32 hash)
#define clib_u32_loop_gt(a, b)
32 bits integer comparison for running values.
#define CLIB_PREFETCH(addr, size, type)
#define vec_free(V)
Free vector's memory (no header).
static_always_inline void lb_hash_free(lb_hash_t *h)
static uword is_pow2(uword x)
u32 hash[LBHASH_ENTRY_PER_BUCKET]
#define CLIB_CACHE_LINE_BYTES
static_always_inline void lb_hash_get(lb_hash_t *ht, u32 hash, u32 vip, u32 time_now, u32 *available_index, u32 *found_value)
static_always_inline u32 lb_hash_hash(u64 k0, u64 k1, u64 k2, u64 k3, u64 k4)
static_always_inline void lb_hash_put(lb_hash_t *h, u32 hash, u32 value, u32 vip, u32 available_index, u32 time_now)
static_always_inline u32 lb_hash_elts(lb_hash_t *h, u32 time_now)