Include dependency graph for flowhash_template.h:

This graph shows which files directly or indirectly include 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...

	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

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++)

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:

flowhash_foreach_entry(h, ei) \

if (((now) <= (h)->entries[ei].timeout))

flowhash_foreach_entry

#define flowhash_foreach_entry(h, ei)

Iterate over all entries in the hash table.

Definition: flowhash_template.h:238

entries

u32 entries

Definition: flowhash_template.h:362

h

Definition: flowhash_template.h:372

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)

CLIB_PREFETCH

#define CLIB_PREFETCH(addr, size, type)

Definition: cache.h:79

fixed_entries_mask

h fixed_entries_mask

Definition: flowhash_template.h:392

entries

u32 entries

Definition: flowhash_template.h:362

h

Definition: flowhash_template.h:372

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 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.

Here is the call graph for this function:

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.

Parameters

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.

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 442 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_buckets; i++ )

Definition at line 378 of file flowhash_template.h.

Here is the caller graph for this function:

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.

Parameters

[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%