hashtb.h File Reference

#include <stdint.h>
#include <vppinfra/bihash_8_8.h>
#include <vppinfra/bihash_24_8.h>
#include "params.h"
#include "parser.h"
#include "error.h"

Include dependency graph for hashtb.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	hicn_hash_key_t
struct	hicn_hashtb_s

Macros
#define	TRUE   1
#define	FALSE   0
#define	HICN_HASH_INVALID_IDX   ~0
#define	HICN_HASH_WALK_CTX_INITIAL   (~((u64) 0))
#define	NODE_IDX_FROM_NODE(p, h)   (u32) ((p) - ((h)->ht_nodes))
#define	HICN_HASH_KEY_BYTES   20
#define	HICN_HASHTB_KEY_RATIO   8
#define	HICN_HASH_NODE_APP_DATA_SIZE   64
#define	HICN_HASH_NODE_FLAGS_DEFAULT   0x00
#define	HICN_HASH_NODE_CS_FLAGS   0x01
#define	HICN_HASH_NODE_OVERFLOW_BUCKET   0x02
#define	HICN_HASH_ENTRY_FLAGS_DEFAULT   0x00
#define	HICN_HASH_ENTRY_FLAG_CS_ENTRY   0x01
#define	HICN_HASH_ENTRY_FLAG_OVERFLOW   0x04
#define	HICN_HASH_ENTRY_FLAG_DELETED   0x08
#define	HICN_HASH_ENTRY_FLAG_FAST_TIMEOUT   0x10
#define	HICN_HASHTB_BUCKET_ENTRIES   5
#define	HICN_HASHTB_FILL_FACTOR   4
#define	HICN_HASHTB_MIN_ENTRIES   (1 << 4)
#define	HICN_HASHTB_MAX_ENTRIES   (1 << 24)
#define	HICN_HASHTB_MIN_BUCKETS   (1 << 10)
#define	HICN_HASHTB_FLAGS_DEFAULT   0x00
#define	HICN_HASHTB_FLAG_USE_SEVEN   0x04
#define	HICN_HASHTB_FLAG_KEY_FMT_PFX   0x08
#define	HICN_HASHTB_FLAG_KEY_FMT_NAME   0x10
#define	HICN_HASHTB_MAX_NAME_COMPS   HICN_PARAM_FIB_ENTRY_PFX_COMPS_MAX

Typedefs
typedef struct hicn_hashtb_s	hicn_hashtb_t
typedef struct hicn_hashtb_s *	hicn_hashtb_h

Functions
struct	__attribute__ ((packed)) hicn_hash_node_s
	Structure representing a face. It containes the fields shared among all the types of faces as well it leaves some space for storing additional information specific to each type. More...
	STATIC_ASSERT (sizeof(index_t)<=4, "sizeof index_t is greater than 4B")
int	hicn_hashtb_alloc (hicn_hashtb_h *ph, u32 max_elems, size_t app_data_size)
int	hicn_hashtb_free (hicn_hashtb_h *ph)
u64	hicn_hashtb_hash_bytestring (const u8 *key, u32 keylen)
always_inline hicn_hash_entry_t *	hicn_hashtb_get_entry (hicn_hashtb_h h, u32 entry_idx, u32 bucket_id, u8 bucket_overflow)
always_inline u64	hicn_hashtb_hash_name (const u8 *key, u16 keylen)
void	hicn_hashtb_init_node (hicn_hashtb_h h, hicn_hash_node_t *node, const u8 *key, u32 keylen)
int	hicn_hashtb_insert (hicn_hashtb_h h, hicn_hash_node_t *node, hicn_hash_entry_t **hash_entry, u64 hash, u32 *node_id, index_t *dpo_ctx_id, u8 *vft_id, u8 *is_cs, u8 *hash_entry_id, u32 *bucket_id, u8 *bucket_is_overflow)
int	hicn_hashtb_lookup_node (hicn_hashtb_h h, const u8 *key, u32 keylen, u64 hashval, u8 is_data, u32 *node_id, index_t *dpo_ctx_id, u8 *vft_id, u8 *is_cs, u8 *hash_entry_id, u32 *bucket_id, u8 *bucket_is_overflow)
int	hicn_hashtb_lookup_node_ex (hicn_hashtb_h h, const u8 *key, u32 keylen, u64 hashval, u8 is_data, int include_deleted_p, u32 *node_id, index_t *dpo_ctx_id, u8 *vft_id, u8 *is_cs, u8 *hash_entry_id, u32 *bucket_id, u8 *bucket_is_overflow)
int	hicn_node_compare (const u8 *key, u32 keylen, hicn_hash_node_t *node)
	Compares the key in the node with the given key. More...
void	hicn_hashtb_remove_node (hicn_hashtb_h h, hicn_hash_node_t *node, u64 hashval)
void	hicn_hashtb_delete (hicn_hashtb_h h, hicn_hash_node_t **pnode, u64 hashval)
void	hicn_hashtb_init_entry (hicn_hash_entry_t *entry, u32 nodeidx, u64 hashval, u32 locks)
void	hicn_hashtb_free_node (hicn_hashtb_h h, hicn_hash_node_t *node)
int	hicn_hashtb_next_node (hicn_hashtb_h h, hicn_hash_node_t **pnode, u64 *ctx)
int	hicn_hashtb_key_to_str (hicn_hashtb_h h, const hicn_hash_node_t *node, char *buf, int bufsize, int must_fit)
always_inline int	hicn_hashtb_fullhash (const u8 *name, u16 namelen, u64 *name_hash)

Variables
	hicn_hash_node_t
	hicn_hash_entry_t
	hicn_hash_bucket_t
u32	ht_node_data_offset_aligned

Detailed Description

Lookup is finding a hashtable record whose name matches the name being looked up. Most of the lookup work is based on the hash value of the two names. Note that the intel cache line size is 64 bytes, and some platforms load in 2 cache lines together.

• first step is to match a record at the bucket/slot level (htab has an array of htbucket_t/htbc_elmt, where each bucket has 7 slots to hold indices for entries.) Matching at this level implies
  • the hashes of the lookup name and the record map to the same bucket
  • the high 32 bits of the hashes (slot bce_hash_msb32s) match. Read cost (on the hash table size, i.e. ignoring reading the name being looked up):
    • First step normally requires 1 cache line load to pull in the 64-byte htbucket_t with the 7 element slot table holding the hash_msb32s.
    • In the event (hopefully rare for a hash table with appropriate number of buckets) that more than 7 elements hash to the same bucket, lookup may well need to look not only at the static htbc_elmt_t but at the chain of dynamically allocated htbc_elmt_t's linked to the static htbc_elmt_t, where each of these holds slot entries for additional elements.
    • Before reaching that point, it is initially required to read in the hash table record fields (ht_bucket_buf, htnode buf, etc) holding pointers to the arrays, but these cache lines are common to all lookups so will likely already be in the cache.
• second step is to match at the record level (htnode/htkb level) once a slot-level match happens. Matching at this level implies the following match
  • the hash values (the full 64 bits vs. bucket+32 msb, above).
  • the name which, on the hash table side, is stored as a list of htkb_t (key buffers).

Some hashtables (for which rare false positives are tolerable) store hash values but no keys. (In ISM NDN forwarder, this was used for dcm_dpf: data cache manager's dataplane filter, where speed was critical and very rare false positives would be detected in the full dcm check.) - No key buffers are used (or even allocated at hash table creation).

Function Documentation

__attribute__()

struct __attribute__

(

(packed)

)

Structure representing a face. It containes the fields shared among all the types of faces as well it leaves some space for storing additional information specific to each type.

Key definition for the mhash table. An face is uniquely identified by ip address, the interface id and a dpo pointing to the next node in the vlib graph. The ip address can correspond to the remote ip address of the next hicn hop, or to the local address of the receiving interface. The former is used to retrieve the incoming face when an interest is received, the latter when the arring packet is a data. If the face is a regular face In case of iface, the following structure can be filled in different ways:

• dpo equal to DPO_INVALID when the iface is a regular hICN iface
• in case of udp_tunnel dpo = { .dpoi_index = tunnel_id, .dpoi_type = DPO_FIRST, //We don't need the type, we leave it invalid .dpoi_proto = DPO_PROTO_IP4 or DPO_PROTO_IP6, .dpoi_next_node = HICN6_IFACE_OUTPUT_NEXT_UDP4_ENCAP or HICN6_IFACE_OUTPUT_NEXT_UDP6_ENCAP or HICN4_IFACE_OUTPUT_NEXT_UDP4_ENCAP or HICN4_IFACE_OUTPUT_NEXT_UDP6_ENCAP }

hicn_node_compare()

int hicn_node_compare	(	const u8 *	key,
		u32	keylen,
		hicn_hash_node_t *	node
	)

Compares the key in the node with the given key.

This function allows to split the hash verification from the comparison of the entire key. Useful to exploit prefertching.

Returns

1 if equals, 0 otherwise