FD.io VPP  v18.04-17-g3a0d853
Vector Packet Processing
flowhash_template.h File Reference
+ Include dependency graph for flowhash_template.h:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  FVT
 One flow hash entry used for both direct buckets and collision buckets. More...
 

Macros

#define FV(a)   __fv(a,FLOWHASH_TYPE)
 
#define FVT(a)   __fvt(a,FLOWHASH_TYPE)
 
#define FLOWHASH_INVALID_ENTRY_INDEX   0
 
#define FLOWHASH_ENTRIES_PER_BUCKETS_LOG   4
 
#define FLOWHASH_ENTRIES_PER_BUCKETS   (1 << FLOWHASH_ENTRIES_PER_BUCKETS_LOG)
 
#define flowhash_is_overflow(ei)   ((ei) == FLOWHASH_INVALID_ENTRY_INDEX)
 Test whether a returned entry index corresponds to an overflow event. More...
 
#define flowhash_foreach_entry(h, ei)
 Iterate over all entries in the hash table. More...
 
#define flowhash_foreach_valid_entry(h, ei, now)
 Iterate over all currently valid entries. More...
 
#define flowhash_timeout(h, ei)   (h)->entries[ei].timeout
 Timeout variable from a given entry. More...
 
#define flowhash_is_timeouted(h, ei, time_now)   ((time_now) > flowhash_timeout(h, ei))
 Indicates whether the entry is being used. More...
 
#define flowhash_key(h, ei)   (&(h)->entries[ei].key)
 Get the key from the entry index, casted to the provided type. More...
 
#define flowhash_value(h, ei)   (&(h)->entries[ei].value)
 Get the value from the entry index, casted to the provided type. More...
 
#define flowhash_memory_size(h)   clib_mem_size((h)->mem)
 Get the number of octets allocated to this structure. More...
 
#define flowhash_is_valid_entry_index(h, ei)   (ei < (h)->total_entries)
 Test whether the entry index is in hash table boundaries. More...
 
#define flowhash_prefetch(h, hash)
 Prefetch the the hash entry bucket. More...
 

Functions

static_always_inline u8 FV() flowhash_cmp_key (FVT(flowhash_skey)*a, FVT(flowhash_lkey)*b)
 Compare a stored key with a lookup key. More...
 
static_always_inline u32 FV() flowhash_hash (FVT(flowhash_lkey)*k)
 Hash a lookup key into a 32 bit integer. More...
 
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. More...
 
struct FVT (__flowhash_struct)
 
 FVT (flowhash)*FV(flowhash_alloc)(u32 fixed_entries
 Allocate a flowhash structure. More...
 
static void flowhash_validate_sizes (u32 *fixed_entries, u32 *collision_buckets)
 Adjust, if necessary, provided parameters such as being valid flowhash sizes. More...
 
 for (i=1;i<=collision_buckets;i++)
 
 for (i=0;i< entries;i++)
 
static_always_inline void FV() flowhash_free (FVT(flowhash)*h)
 Free the flow hash memory. More...
 
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. More...
 
static_always_inline void FV() flowhash_gc (FVT(flowhash)*h, u32 time_now)
 
static_always_inline u32 FV() flowhash_elts (FVT(flowhash)*h, u32 time_now)
 

Variables

static_always_inline u32 collision_buckets
 
u32 size
 
void * mem = clib_mem_alloc_aligned(size, CLIB_CACHE_LINE_BYTES)
 
u32 entries
 
flowhash_validate_sizesfixed_entries
 
 h = mem + collision_buckets * sizeof(h->free_buckets_indices[0])
 
int i
 
h free_buckets_position = -collision_buckets
 
h fixed_entries_mask = fixed_entries - 1
 
h collision_buckets_mask = collision_buckets - 1
 
h total_entries = entries
 
h not_enough_buckets_counter = 0
 
h collision_lookup_counter = 0
 
h garbage_collection_counter = 0
 
h gc_counter = 0
 

Macro Definition Documentation

#define FLOWHASH_ENTRIES_PER_BUCKETS   (1 << FLOWHASH_ENTRIES_PER_BUCKETS_LOG)

Definition at line 133 of file flowhash_template.h.

#define FLOWHASH_ENTRIES_PER_BUCKETS_LOG   4

Definition at line 132 of file flowhash_template.h.

#define flowhash_foreach_entry (   h,
  ei 
)
Value:
for (ei = 1; \
ei < (h)->total_entries; \
ei++)
h total_entries

Iterate over all entries in the hash table.

Iterate over all entries in the hash table, not including the first invalid entry (at index 0), but including all chained hash collision buckets.

Definition at line 238 of file flowhash_template.h.

#define flowhash_foreach_valid_entry (   h,
  ei,
  now 
)
Value:
if (((now) <= (h)->entries[ei].timeout))
#define flowhash_foreach_entry(h, ei)
Iterate over all entries in the hash table.
u32 entries

Iterate over all currently valid entries.

Iterate over all entries in the hash table which timeout value is greater or equal to the current time.

Definition at line 249 of file flowhash_template.h.

#define FLOWHASH_INVALID_ENTRY_INDEX   0

Definition at line 130 of file flowhash_template.h.

#define flowhash_is_overflow (   ei)    ((ei) == FLOWHASH_INVALID_ENTRY_INDEX)

Test whether a returned entry index corresponds to an overflow event.

Definition at line 228 of file flowhash_template.h.

#define flowhash_is_timeouted (   h,
  ei,
  time_now 
)    ((time_now) > flowhash_timeout(h, ei))

Indicates whether the entry is being used.

Definition at line 261 of file flowhash_template.h.

#define flowhash_is_valid_entry_index (   h,
  ei 
)    (ei < (h)->total_entries)

Test whether the entry index is in hash table boundaries.

Definition at line 282 of file flowhash_template.h.

#define flowhash_key (   h,
  ei 
)    (&(h)->entries[ei].key)

Get the key from the entry index, casted to the provided type.

Definition at line 267 of file flowhash_template.h.

#define flowhash_memory_size (   h)    clib_mem_size((h)->mem)

Get the number of octets allocated to this structure.

Definition at line 277 of file flowhash_template.h.

#define flowhash_prefetch (   h,
  hash 
)
Value:
CLIB_PREFETCH (&(h)->entries[((hash) & (h)->fixed_entries_mask) + 1], \
sizeof((h)->entries[0]), LOAD)
#define CLIB_PREFETCH(addr, size, type)
Definition: cache.h:74
h fixed_entries_mask
u32 entries

Prefetch the the hash entry bucket.

This should be performed approximately 200-300 cycles before lookup if the table is located in RAM. Or 30-40 cycles before lookup in case the table is located in L3.

Definition at line 327 of file flowhash_template.h.

#define flowhash_timeout (   h,
  ei 
)    (h)->entries[ei].timeout

Timeout variable from a given entry.

Definition at line 256 of file flowhash_template.h.

#define flowhash_value (   h,
  ei 
)    (&(h)->entries[ei].value)

Get the value from the entry index, casted to the provided type.

Definition at line 272 of file flowhash_template.h.

#define FV (   a)    __fv(a,FLOWHASH_TYPE)

Definition at line 121 of file flowhash_template.h.

#define FVT (   a)    __fvt(a,FLOWHASH_TYPE)

Definition at line 125 of file flowhash_template.h.

Function Documentation

static_always_inline u8 FV() flowhash_cmp_key ( FVT(flowhash_skey)*  a,
FVT(flowhash_lkey)*  b 
)

Compare a stored key with a lookup key.

This function must be defined to use this template. It must return 0 when the two keys are identical, and a different value otherwise.

+ Here is the caller graph for this function:

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.

This function must be defined to use this template. It must modify the dst key such that a later call to flowhash_cmp_key with the same arguments would return 0.

+ Here is the caller graph for this function:

static_always_inline u32 FV() flowhash_elts ( FVT(flowhash)*  h,
u32  time_now 
)

Definition at line 586 of file flowhash_template.h.

static_always_inline void FV() flowhash_free ( FVT(flowhash)*  h)

Free the flow hash memory.

Definition at line 406 of file flowhash_template.h.

+ Here is the call graph for this function:

static_always_inline void FV() flowhash_gc ( FVT(flowhash)*  h,
u32  time_now 
)

Definition at line 528 of file flowhash_template.h.

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.

Parameters
hThe hash table pointer.
k[in]A pointer to the key value.
hash[in]The hash of the key.
time_now[in]The current time.
ei[out]A pointer set to the found entry index.

This function always sets ei value to a valid entry index which can then be used to access the stored value as well as get or set its associated timeout. The key stored in the returned entry is always set to the provided key.

In case the provided key is not found, and no entry could be created (either because there is no hash collision bucket available or the candidate entries in the collision bucket were already used), ei is set to the special value FLOWHASH_INVALID_ENTRY_INDEX (which can be tested with the flowhash_is_overflow macro).

The timeout value is never modified during a lookup.

  • Use the flowhash_is_timeouted macro to test whether the returned entry was already valid, or is proposed for insertion.
  • Use the flowhash_timeout macro to get and set the entry timeout value.

Definition at line 441 of file flowhash_template.h.

+ Here is the call graph for this function:

static_always_inline u32 FV() flowhash_hash ( FVT(flowhash_lkey)*  k)

Hash a lookup key into a 32 bit integer.

This function must be defined to use this template. It must provides close to 32 bits of entropy distributed amongst all 32 bits of the provided value. Keys that are equal must have the same hash.

static void flowhash_validate_sizes ( u32 fixed_entries,
u32 collision_buckets 
)
static

Adjust, if necessary, provided parameters such as being valid flowhash sizes.

Definition at line 289 of file flowhash_template.h.

for ( i  = 1; i <= collision_bucketsi++)

Definition at line 377 of file flowhash_template.h.

+ Here is the caller graph for this function:

for ( )

Definition at line 384 of file flowhash_template.h.

struct FVT ( __flowhash_struct  )

Definition at line 188 of file flowhash_template.h.

static_always_inline FVT ( flowhash  )

Allocate a flowhash structure.

Parameters
[in]fixed_entriesThe number of fixed entries in the hash table.
[in]chained_bucketsThe number of chained buckets.

fixed_entries and chained_buckets parameters may not be used as is but modified in order to fit requirements.

Since the flowhash does not support dynamic resizing, it is fairly important to choose the parameters carefully. In particular the performance gain from using this structure comes from an efficient lookup in the absence of hash collision. As a rule of thumbs, if the number of active entries (flows) is M, there should be about 16*M fixed entries, and M/16 collision buckets. Which represents 17*M allocated entries.

For example: M = 2^20 total_size ~= 1GiB collision ~= 3% M = 2^18 total_size ~= 250MiB collision ~= 3% M = 2^10 total_size ~= 1MiB collision ~= 6%

Variable Documentation

static_always_inline u32 collision_buckets
Initial value:
{
FVT(flowhash) *h
#define FVT(a)

Definition at line 358 of file flowhash_template.h.

h collision_buckets_mask = collision_buckets - 1

Definition at line 392 of file flowhash_template.h.

h collision_lookup_counter = 0

Definition at line 395 of file flowhash_template.h.

entries
Initial value:
#define FLOWHASH_ENTRIES_PER_BUCKETS
flowhash_validate_sizes & fixed_entries
static_always_inline u32 collision_buckets

Definition at line 362 of file flowhash_template.h.

flowhash_validate_sizes& fixed_entries

Definition at line 364 of file flowhash_template.h.

h fixed_entries_mask = fixed_entries - 1

Definition at line 391 of file flowhash_template.h.

h free_buckets_position = -collision_buckets

Definition at line 390 of file flowhash_template.h.

h garbage_collection_counter = 0

Definition at line 396 of file flowhash_template.h.

h gc_counter = 0

Definition at line 397 of file flowhash_template.h.

return h = mem + collision_buckets * sizeof(h->free_buckets_indices[0])

Definition at line 372 of file flowhash_template.h.

int i

Definition at line 376 of file flowhash_template.h.

h not_enough_buckets_counter = 0

Definition at line 394 of file flowhash_template.h.

u32 size
Initial value:
= sizeof(*h) + sizeof(h->entries[0]) * entries +
sizeof(h->free_buckets_indices[0]) * collision_buckets
static_always_inline u32 collision_buckets
u32 entries

Definition at line 360 of file flowhash_template.h.

h total_entries = entries

Definition at line 393 of file flowhash_template.h.