108 #ifndef __included_flowhash_template_h__ 109 #define __included_flowhash_template_h__ 115 #ifndef FLOWHASH_TYPE 116 #error FLOWHASH_TYPE not defined 119 #define _fv(a,b) a##b 120 #define __fv(a,b) _fv(a,b) 121 #define FV(a) __fv(a,FLOWHASH_TYPE) 123 #define _fvt(a,b) a##b##_t 124 #define __fvt(a,b) _fvt(a,b) 125 #define FVT(a) __fvt(a,FLOWHASH_TYPE) 128 #ifndef __included_flowhash_common__ 130 #define FLOWHASH_INVALID_ENTRY_INDEX 0 132 #define FLOWHASH_ENTRIES_PER_BUCKETS_LOG 4 133 #define FLOWHASH_ENTRIES_PER_BUCKETS (1 << FLOWHASH_ENTRIES_PER_BUCKETS_LOG) 186 }
FVT(flowhash_entry);
188 typedef struct FVT(__flowhash_struct) {
193 u32 free_buckets_indices[0];
218 FVT(flowhash_entry) entries[0];
222 #ifndef __included_flowhash_common__ 223 #define __included_flowhash_common__ 228 #define flowhash_is_overflow(ei) \ 229 ((ei) == FLOWHASH_INVALID_ENTRY_INDEX) 238 #define flowhash_foreach_entry(h, ei) \ 240 ei < (h)->total_entries; \ 249 #define flowhash_foreach_valid_entry(h, ei, now) \ 250 flowhash_foreach_entry(h, ei) \ 251 if (((now) <= (h)->entries[ei].timeout)) 256 #define flowhash_timeout(h, ei) (h)->entries[ei].timeout 261 #define flowhash_is_timeouted(h, ei, time_now) \ 262 ((time_now) > flowhash_timeout(h, ei)) 267 #define flowhash_key(h, ei) (&(h)->entries[ei].key) 272 #define flowhash_value(h, ei) (&(h)->entries[ei].value) 277 #define flowhash_memory_size(h) clib_mem_size((h)->mem) 282 #define flowhash_is_valid_entry_index(h, ei) (ei < (h)->total_entries) 292 if (*fixed_entries < FLOWHASH_ENTRIES_PER_BUCKETS)
298 *fixed_entries |= *fixed_entries >> 16;
299 *fixed_entries |= *fixed_entries >> 8;
300 *fixed_entries |= *fixed_entries >> 4;
301 *fixed_entries |= *fixed_entries >> 2;
302 *fixed_entries |= *fixed_entries >> 1;
305 if (*collision_buckets != 0)
310 *collision_buckets -= 1;
311 *collision_buckets |= *collision_buckets >> 16;
312 *collision_buckets |= *collision_buckets >> 8;
313 *collision_buckets |= *collision_buckets >> 4;
314 *collision_buckets |= *collision_buckets >> 2;
315 *collision_buckets |= *collision_buckets >> 1;
316 *collision_buckets += 1;
327 #define flowhash_prefetch(h, hash) \ 328 CLIB_PREFETCH (&(h)->entries[((hash) & (h)->fixed_entries_mask) + 1], \ 329 sizeof((h)->entries[0]), LOAD) 366 entries = 1 + fixed_entries +
368 size =
sizeof(*h) +
sizeof(h->entries[0]) * entries +
377 clib_memset(h->entries, 0,
sizeof(h->entries[0]) * entries);
380 h->free_buckets_indices[-
i] =
388 h->entries[
i].timeout = 0;
392 h->fixed_entries_mask = fixed_entries - 1;
395 h->not_enough_buckets_counter = 0;
396 h->collision_lookup_counter = 0;
397 h->garbage_collection_counter = 0;
413 FV(__flowhash_get_chained) (
FVT(flowhash) *
h,
FVT(flowhash_lkey) *k,
445 *ei = (hash & h->fixed_entries_mask) + 1;
450 (h->entries[*ei].chained_entry_index ==
457 FV(__flowhash_get_chained)(
h, k, hash, time_now, ei);
463 FV(__flowhash_get_chained) (
FVT(flowhash) *
h,
FVT(flowhash_lkey) *k,
466 h->collision_lookup_counter++;
471 if (h->free_buckets_position == 0)
474 h->not_enough_buckets_counter++;
484 h->entries[*ei].chained_entry_index =
485 h->free_buckets_indices[h->free_buckets_position];
488 h->entries[h->free_buckets_indices[h->free_buckets_position]].
489 chained_entry_index = *ei;
492 h->free_buckets_position++;
496 u32 bi0 = h->entries[*ei].chained_entry_index +
499 bi1 = (bi0 & (FLOWHASH_ENTRIES_PER_BUCKETS - 1)) ? bi1 :
504 CLIB_PREFETCH(&h->entries[bi1], sizeof (h->entries[0]), READ);
518 if (h->entries[*ei].timeout >= time_now)
521 *ei = (time_now > h->entries[bi0].timeout) ? bi0 : *ei;
522 *ei = (time_now > h->entries[bi1].timeout) ? bi1 : *ei;
530 u32 *freed_index,
u32 *freed_len)
540 ei = 2 + h->fixed_entries_mask +
541 ((h->gc_counter + 2) & h->collision_buckets_mask) *
543 CLIB_PREFETCH(&h->entries[ei], sizeof (h->entries[0]), READ);
546 ei = 2 + h->fixed_entries_mask +
547 ((h->gc_counter + 1) & h->collision_buckets_mask) *
555 ei = 2 + h->fixed_entries_mask +
556 ((h->gc_counter) & h->collision_buckets_mask) *
564 if (time_now <= h->entries[ei + i].timeout)
580 h->free_buckets_position--;
582 h->entries[h->entries[ei].chained_entry_index].chained_entry_index =
587 h->free_buckets_indices[h->free_buckets_position] = ei;
589 h->garbage_collection_counter++;
#define FLOWHASH_ENTRIES_PER_BUCKETS
#define CLIB_CACHE_LINE_ALIGN_MARK(mark)
static_always_inline void FV() flowhash_free(FVT(flowhash) *h)
Free the flow hash memory.
h garbage_collection_counter
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
static_always_inline u32 FV() flowhash_hash(FVT(flowhash_lkey) *k)
Hash a lookup key into a 32 bit integer.
#define FLOWHASH_ENTRIES_PER_BUCKETS_LOG
flowhash_validate_sizes & fixed_entries
#define static_always_inline
h collision_lookup_counter
static void flowhash_validate_sizes(u32 *fixed_entries, u32 *collision_buckets)
Adjust, if necessary, provided parameters such as being valid flowhash sizes.
#define flowhash_foreach_valid_entry(h, ei, now)
Iterate over all currently valid entries.
#define CLIB_PREFETCH(addr, size, type)
static_always_inline void FV() flowhash_cpy_key(FVT(flowhash_skey) *dst, FVT(flowhash_lkey) *src)
Copy a lookup key into a destination stored key.
static_always_inline void FV() flowhash_gc(FVT(flowhash) *h, u32 time_now, u32 *freed_index, u32 *freed_len)
static_always_inline u8 FV() flowhash_cmp_key(FVT(flowhash_skey) *a, FVT(flowhash_lkey) *b)
Compare a stored key with a lookup key.
#define FLOWHASH_INVALID_ENTRY_INDEX
static_always_inline u32 collision_buckets
static void clib_mem_free(void *p)
static_always_inline u32 FV() flowhash_elts(FVT(flowhash) *h, u32 time_now)
h not_enough_buckets_counter
static void * clib_mem_alloc_aligned(uword size, uword align)
#define CLIB_CACHE_LINE_BYTES
static_always_inline void FV() flowhash_get(FVT(flowhash) *h, FVT(flowhash_lkey) *k, u32 hash, u32 time_now, u32 *ei)
Retrieves an entry index corresponding to a provided key and its hash.
#define flowhash_value(h, ei)
Get the value from the entry index, casted to the provided type.