29 #ifndef LB_PLUGIN_LB_LBHASH_H_ 30 #define LB_PLUGIN_LB_LBHASH_H_ 35 #if defined (__SSE4_2__) 36 #include <immintrin.h> 42 #define LBHASH_ENTRY_PER_BUCKET 4 44 #define LB_HASH_DO_NOT_USE_SSE_BUCKETS 0 64 #define lb_hash_nbuckets(h) (((h)->buckets_mask) + 1) 65 #define lb_hash_size(h) ((h)->buckets_mask + LBHASH_ENTRY_PER_BUCKET) 67 #define lb_hash_foreach_bucket(h, bucket) \ 68 for (bucket = (h)->buckets; \ 69 bucket < (h)->buckets + lb_hash_nbuckets(h); \ 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++) 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])) 114 u32 *available_index,
u32 *found_value)
118 *available_index = ~0;
119 #if __SSE4_2__ && LB_HASH_DO_NOT_USE_SSE_BUCKETS == 0 120 u32 bitmask, found_index;
124 mask = _mm_cmpgt_epi32(_mm_loadu_si128 ((__m128i *) bucket->
timeout),
125 _mm_set1_epi32 (time_now));
127 bitmask = (~_mm_movemask_epi8(mask)) & 0xffff;
129 *available_index = (bitmask)?__builtin_ctz(bitmask)/4:*available_index;
132 mask = _mm_and_si128(mask,
134 _mm_loadu_si128 ((__m128i *) bucket->
hash),
135 _mm_set1_epi32 (hash)));
139 mask = _mm_and_si128(mask,
141 _mm_loadu_si128 ((__m128i *) bucket->
vip),
142 _mm_set1_epi32 (vip)));
145 bitmask = _mm_movemask_epi8(mask);
147 found_index = (bitmask)?__builtin_ctzll(bitmask)/4:0;
149 *found_value = (bitmask)?bucket->
value[found_index]:*found_value;
155 u8 cmp = (bucket->
hash[
i] == hash && bucket->
vip[
i] == vip);
157 *found_value = (cmp || timeouted)?*found_value:bucket->
value[i];
159 *available_index = (timeouted && (*available_index == ~0))?
i:*available_index;
175 u32 available_index,
u32 time_now)
178 bucket->
hash[available_index] = hash;
179 bucket->
value[available_index] = value;
181 bucket->
vip[available_index] = vip;
#define lb_hash_foreach_valid_entry(h, bucket, i, now)
#define CLIB_CACHE_LINE_ALIGN_MARK(mark)
#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)
#define clib_u32_loop_gt(a, b)
32 bits integer comparison for running values.
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_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 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)