FD.io VPP  v18.04-17-g3a0d853
Vector Packet Processing
bihash_doc.h File Reference

Bounded-index extensible hashing. More...

Go to the source code of this file.

Data Structures

struct  clib_bihash_value
 template key/value backing page structure More...
 
struct  clib_bihash_t
 A bounded index extensible hash table. More...
 

Typedefs

typedef struct clib_bihash_value offset
 template key/value backing page structure More...
 

Functions

static void * clib_bihash_get_value (clib_bihash *h, uword offset)
 Get pointer to value page given its clib mheap offset. More...
 
static uword clib_bihash_get_offset (clib_bihash *h, void *v)
 Get clib mheap offset given a pointer. More...
 
void clib_bihash_init (clib_bihash *h, char *name, u32 nbuckets, uword memory_size)
 initialize a bounded index extensible hash table More...
 
void clib_bihash_free (clib_bihash *h)
 Destroy a bounded index extensible hash table. More...
 
int clib_bihash_add_del (clib_bihash *h, clib_bihash_kv *add_v, int is_add)
 Add or delete a (key,value) pair from a bi-hash table. More...
 
int clib_bihash_search_inline_with_hash (clib_bihash *h, u64 hash, clib_bihash_kv *in_out_kv)
 Search a bi-hash table, use supplied hash code. More...
 
int clib_bihash_search_inline (clib_bihash *h, clib_bihash_kv *in_out_kv)
 Search a bi-hash table. More...
 
void clib_bihash_prefetch_bucket (clib_bihash *h, u64 hash)
 Prefetch a bi-hash bucket given a hash code. More...
 
void clib_bihash_prefetch_data (clib_bihash *h, u64 hash)
 Prefetch bi-hash (key,value) data given a hash code. More...
 
int clib_bihash_search_inline_2 (clib_bihash *h, clib_bihash_kv *search_key, clib_bihash_kv *valuep)
 Search a bi-hash table. More...
 
void clib_bihash_foreach_key_value_pair (clib_bihash *h, void *callback, void *arg)
 Visit active (key,value) pairs in a bi-hash table. More...
 

Variables

u8 pad [3]
 log2 (size of the packing page block) More...
 
u8 log2_pages
 
u64 as_u64
 
 clib_bihash_bucket_t
 

Detailed Description

Bounded-index extensible hashing.

The basic algorithm performs thread-safe constant-time lookups in the face of a rational number of hash collisions. The computed hash code h(k) must have reasonable statistics with respect to the key space. It won't do to have h(k) = 0 or 1, for all values of k.

Each bucket in the power-of-two bucket array contains the index (in a private vppinfra memory heap) of the "backing store" for the bucket, as well as a size field. The size field (log2_pages) corresponds to 1, 2, 4, ... contiguous "pages" containing the (key,value) pairs in the bucket.

When a single page fills, we allocate two contiguous pages. We recompute h(k) for each (key,value) pair, using an additional bit to deal the (key, value) pairs into the "top" and "bottom" pages.

At lookup time, we compute h(k), using lg(bucket-array-size) to pick the bucket. We read the bucket to find the base of the backing pages. We use an additional log2_pages' worth of bits from h(k) to compute the offset of the page which will contain the (key,value) pair we're trying to find.

Definition in file bihash_doc.h.

Typedef Documentation

typedef struct clib_bihash_value offset

template key/value backing page structure

bihash bucket structure backing page offset in the clib memory heap

Function Documentation

int clib_bihash_add_del ( clib_bihash *  h,
clib_bihash_kv *  add_v,
int  is_add 
)

Add or delete a (key,value) pair from a bi-hash table.

Parameters
h- the bi-hash table to search
add_v- the (key,value) pair to add
is_add- add=1, delete=0
Returns
0 on success, < 0 on error
Note
This function will replace an existing (key,value) pair if the new key matches an existing key

+ Here is the caller graph for this function:

void clib_bihash_foreach_key_value_pair ( clib_bihash *  h,
void *  callback,
void *  arg 
)

Visit active (key,value) pairs in a bi-hash table.

Parameters
h- the bi-hash table to search
callback- function to call with each active (key,value) pair
arg- arbitrary second argument passed to the callback function First argument is the (key,value) pair to visit
Note
Trying to supply a proper function prototype for the callback function appears to be a fool's errand.

+ Here is the caller graph for this function:

void clib_bihash_free ( clib_bihash *  h)

Destroy a bounded index extensible hash table.

Parameters
h- the bi-hash table to free

+ Here is the caller graph for this function:

static uword clib_bihash_get_offset ( clib_bihash *  h,
void *  v 
)
inlinestatic

Get clib mheap offset given a pointer.

static void* clib_bihash_get_value ( clib_bihash *  h,
uword  offset 
)
inlinestatic

Get pointer to value page given its clib mheap offset.

+ Here is the caller graph for this function:

void clib_bihash_init ( clib_bihash *  h,
char *  name,
u32  nbuckets,
uword  memory_size 
)

initialize a bounded index extensible hash table

Parameters
h- the bi-hash table to initialize
name- name of the hash table
nbuckets- the number of buckets, will be rounded up to a power of two
memory_size- clib mheap size, in bytes

+ Here is the caller graph for this function:

void clib_bihash_prefetch_bucket ( clib_bihash *  h,
u64  hash 
)

Prefetch a bi-hash bucket given a hash code.

Parameters
h- the bi-hash table to search
hash- the hash code
Note
see also clib_bihash_hash to compute the code
void clib_bihash_prefetch_data ( clib_bihash *  h,
u64  hash 
)

Prefetch bi-hash (key,value) data given a hash code.

Parameters
h- the bi-hash table to search
hash- the hash code
Note
assumes that the bucket has been prefetched, see clib_bihash_prefetch_bucket
int clib_bihash_search_inline ( clib_bihash *  h,
clib_bihash_kv *  in_out_kv 
)

Search a bi-hash table.

Parameters
h- the bi-hash table to search
in_out_kv- (key,value) pair containing the search key
Returns
0 on success (with in_out_kv set), < 0 on error

+ Here is the caller graph for this function:

int clib_bihash_search_inline_2 ( clib_bihash *  h,
clib_bihash_kv *  search_key,
clib_bihash_kv *  valuep 
)

Search a bi-hash table.

Parameters
h- the bi-hash table to search
search_key- (key,value) pair containing the search key
valuep- (key,value) set to search result
Returns
0 on success (with valuep set), < 0 on error
Note
used in situations where key modification is not desired

+ Here is the caller graph for this function:

int clib_bihash_search_inline_with_hash ( clib_bihash *  h,
u64  hash,
clib_bihash_kv *  in_out_kv 
)

Search a bi-hash table, use supplied hash code.

Parameters
h- the bi-hash table to search
hash- the hash code
in_out_kv- (key,value) pair containing the search key
Returns
0 on success (with in_out_kv set), < 0 on error

Variable Documentation

u64 as_u64

Definition at line 63 of file bihash_doc.h.

clib_bihash_bucket_t

Definition at line 65 of file bihash_doc.h.

u8 log2_pages

Definition at line 62 of file bihash_doc.h.

u8 pad[3]

log2 (size of the packing page block)

Definition at line 61 of file bihash_doc.h.