FD.io VPP
v20.05.1-5-g09f167997
Vector Packet Processing
|
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... | |
clib_memset (h->entries, 0, sizeof(h->entries[0]) *entries) | |
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, u32 *freed_index, u32 *freed_len) |
static_always_inline u32 FV() | flowhash_elts (FVT(flowhash) *h, u32 time_now) |
Variables | |
static_always_inline u32 | collision_buckets |
uword | size |
void * | mem = clib_mem_alloc_aligned(size, CLIB_CACHE_LINE_BYTES) |
u32 | entries |
flowhash_validate_sizes & | fixed_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 |
#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 | |||
) |
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 | |||
) |
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.
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 | |||
) |
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.
Timeout variable from a given entry.
Definition at line 256 of file flowhash_template.h.
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.
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.
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.
static_always_inline u32 FV() flowhash_elts | ( | FVT(flowhash) * | h, |
u32 | time_now | ||
) |
Definition at line 597 of file flowhash_template.h.
static_always_inline void FV() flowhash_free | ( | FVT(flowhash) * | h | ) |
Free the flow hash memory.
Definition at line 407 of file flowhash_template.h.
static_always_inline void FV() flowhash_gc | ( | FVT(flowhash) * | h, |
u32 | time_now, | ||
u32 * | freed_index, | ||
u32 * | freed_len | ||
) |
Definition at line 529 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.
h | The 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.
Definition at line 442 of file flowhash_template.h.
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.
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_buckets; i++ | ) |
for | ( | ) |
Definition at line 385 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.
[in] | fixed_entries | The number of fixed entries in the hash table. |
[in] | chained_buckets | The 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%
static_always_inline u32 collision_buckets |
Definition at line 358 of file flowhash_template.h.
h collision_buckets_mask = collision_buckets - 1 |
Definition at line 393 of file flowhash_template.h.
h collision_lookup_counter = 0 |
Definition at line 396 of file flowhash_template.h.
entries |
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 392 of file flowhash_template.h.
h free_buckets_position = -collision_buckets |
Definition at line 391 of file flowhash_template.h.
h garbage_collection_counter = 0 |
Definition at line 397 of file flowhash_template.h.
h gc_counter = 0 |
Definition at line 398 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.
Definition at line 361 of file flowhash_template.h.
h not_enough_buckets_counter = 0 |
Definition at line 395 of file flowhash_template.h.
size |
Definition at line 360 of file flowhash_template.h.
Definition at line 394 of file flowhash_template.h.