rte_member.h File Reference

#include <stdint.h>
#include <rte_common.h>
#include <rte_config.h>
#include <rte_jhash.h>

Go to the source code of this file.

Data Structures
struct	rte_member_parameters

Macros
#define	RTE_MEMBER_NO_MATCH   0
#define	RTE_MEMBER_ENTRIES_MAX   (1 << 30)
#define	RTE_MEMBER_LOOKUP_BULK_MAX   64
#define	RTE_MEMBER_BUCKET_ENTRIES   16
#define	RTE_MEMBER_NAMESIZE   32

Typedefs
typedef uint16_t	member_set_t

Enumerations
enum	rte_member_setsum_type { RTE_MEMBER_TYPE_HT = 0, RTE_MEMBER_TYPE_VBF }

Functions
struct rte_member_setsum *	rte_member_find_existing (const char *name)
struct rte_member_setsum *	rte_member_create (const struct rte_member_parameters *params)
int	rte_member_lookup (const struct rte_member_setsum *setsum, const void *key, member_set_t *set_id)
int	rte_member_lookup_bulk (const struct rte_member_setsum *setsum, const void **keys, uint32_t num_keys, member_set_t *set_ids)
int	rte_member_lookup_multi (const struct rte_member_setsum *setsum, const void *key, uint32_t max_match_per_key, member_set_t *set_id)
int	rte_member_lookup_multi_bulk (const struct rte_member_setsum *setsum, const void **keys, uint32_t num_keys, uint32_t max_match_per_key, uint32_t *match_count, member_set_t *set_ids)
int	rte_member_add (const struct rte_member_setsum *setsum, const void *key, member_set_t set_id)
void	rte_member_free (struct rte_member_setsum *setsum)
void	rte_member_reset (const struct rte_member_setsum *setsum)
int	rte_member_delete (const struct rte_member_setsum *setsum, const void *key, member_set_t set_id)

Detailed Description

RTE Membership Library

The Membership Library is an extension and generalization of a traditional filter (for example Bloom Filter and cuckoo filter) structure that has multiple usages in a variety of workloads and applications. The library is used to test if a key belongs to certain sets. Two types of such "set-summary" structures are implemented: hash-table based (HT) and vector bloom filter (vBF). For HT setsummary, two subtypes or modes are available, cache and non-cache modes. The table below summarize some properties of the different implementations.

Warning

EXPERIMENTAL: this API may change without prior notice

Definition in file rte_member.h.

Macro Definition Documentation

#define RTE_MEMBER_NO_MATCH   0

Invalid set ID used to mean no match found.

Definition at line 60 of file rte_member.h.

#define RTE_MEMBER_ENTRIES_MAX   (1 << 30)

Maximum size of hash table that can be created.

Definition at line 62 of file rte_member.h.

#define RTE_MEMBER_LOOKUP_BULK_MAX   64

Maximum number of keys that can be searched as a bulk

Definition at line 64 of file rte_member.h.

#define RTE_MEMBER_BUCKET_ENTRIES   16

Entry count per bucket in hash table based mode.

Definition at line 66 of file rte_member.h.

#define RTE_MEMBER_NAMESIZE   32

Maximum number of characters in setsum name.

Definition at line 68 of file rte_member.h.

Typedef Documentation

typedef uint16_t member_set_t

The set ID type that stored internally in hash table based set summary.

Definition at line 58 of file rte_member.h.

Enumeration Type Documentation

enum rte_member_setsum_type

Warning

EXPERIMENTAL: this API may change without prior notice

Define different set summary types

Enumerator
RTE_MEMBER_TYPE_HT	Hash table based set summary.
RTE_MEMBER_TYPE_VBF	Vector of bloom filters.

Definition at line 105 of file rte_member.h.

Function Documentation

struct rte_member_setsum* rte_member_find_existing

(

const char *

name

)

Warning

EXPERIMENTAL: this API may change without prior notice

Find an existing set-summary and return a pointer to it.

Parameters

name	Name of the set-summary.

Returns

Pointer to the set-summary or NULL if object not found with rte_errno set appropriately. Possible rte_errno values include:

• ENOENT - value not available for return

struct rte_member_setsum* rte_member_create

(

const struct rte_member_parameters *

params

)

Warning

EXPERIMENTAL: this API may change without prior notice

Create set-summary (SS).

Parameters

params

Parameters to initialize the setsummary.

Returns

Return the pointer to the setsummary. Return value is NULL if the creation failed.

int rte_member_lookup	(	const struct rte_member_setsum *	setsum,
		const void *	key,
		member_set_t *	set_id
	)

Warning

EXPERIMENTAL: this API may change without prior notice

Lookup key in set-summary (SS). Single key lookup and return as soon as the first match found

Parameters

setsum	Pointer of a setsummary.
key	Pointer of the key to be looked up.
set_id	Output the set id matches the key.

Returns

Return 1 for found a match and 0 for not found a match.

int rte_member_lookup_bulk	(	const struct rte_member_setsum *	setsum,
		const void **	keys,
		uint32_t	num_keys,
		member_set_t *	set_ids
	)

Warning

EXPERIMENTAL: this API may change without prior notice

Lookup bulk of keys in set-summary (SS). Each key lookup returns as soon as the first match found

Parameters

setsum	Pointer of a setsummary.
keys	Pointer of the bulk of keys to be looked up.
num_keys	Number of keys that will be lookup.
set_ids	Output set ids for all the keys to this array. User should preallocate array that can contain all results, which size is the num_keys.

Returns

The number of keys that found a match.

int rte_member_lookup_multi	(	const struct rte_member_setsum *	setsum,
		const void *	key,
		uint32_t	max_match_per_key,
		member_set_t *	set_id
	)

Warning

EXPERIMENTAL: this API may change without prior notice

Lookup a key in set-summary (SS) for multiple matches. The key lookup will find all matched entries (multiple match). Note that for cache mode of HT, each key can have at most one match. This is because keys with same signature that maps to same bucket will overwrite each other. So multi-match lookup should be used for vBF and non-cache HT.

Parameters

setsum	Pointer of a set-summary.
key	Pointer of the key that to be looked up.
max_match_per_key	User specified maximum number of matches for each key. The function returns as soon as this number of matches found for the key.
set_id	Output set ids for all the matches of the key. User needs to preallocate the array that can contain max_match_per_key number of results.

Returns

The number of matches that found for the key. For cache mode HT set-summary, the number should be at most 1.

int rte_member_lookup_multi_bulk	(	const struct rte_member_setsum *	setsum,
		const void **	keys,
		uint32_t	num_keys,
		uint32_t	max_match_per_key,
		uint32_t *	match_count,
		member_set_t *	set_ids
	)

Warning

EXPERIMENTAL: this API may change without prior notice

Lookup a bulk of keys in set-summary (SS) for multiple matches each key. Each key lookup will find all matched entries (multiple match). Note that for cache mode HT, each key can have at most one match. So multi-match function is mainly used for vBF and non-cache mode HT.

Parameters

setsum	Pointer of a setsummary.
keys	Pointer of the keys to be looked up.
num_keys	The number of keys that will be lookup.
max_match_per_key	The possible maximum number of matches for each key.
match_count	Output the number of matches for each key in an array.
set_ids	Return set ids for all the matches of all keys. Users pass in a preallocated 2D array with first dimension as key index and second dimension as match index. For example set_ids[bulk_size][max_match_per_key]

Returns

The number of keys that found one or more matches in the set-summary.

int rte_member_add	(	const struct rte_member_setsum *	setsum,
		const void *	key,
		member_set_t	set_id
	)

Warning

EXPERIMENTAL: this API may change without prior notice

Insert key into set-summary (SS).

Parameters

setsum	Pointer of a set-summary.
key	Pointer of the key to be added.
set_id	The set id associated with the key that needs to be added. Different mode supports different set_id ranges. 0 cannot be used as set_id since RTE_MEMBER_NO_MATCH by default is set as 0. For HT mode, the set_id has range as [1, 0x7FFF], MSB is reserved. For vBF mode the set id is limited by the num_set parameter when create the set-summary.

Returns

HT (cache mode) and vBF should never fail unless the set_id is not in the valid range. In such case -EINVAL is returned. For HT (non-cache mode) it could fail with -ENOSPC error code when table is full. For success it returns different values for different modes to provide extra information for users. Return 0 for HT (cache mode) if the add does not cause eviction, return 1 otherwise. Return 0 for non-cache mode if success, -ENOSPC for full, and 1 if cuckoo eviction happens. Always returns 0 for vBF mode.

void rte_member_free

(

struct rte_member_setsum *

setsum

)

Warning

EXPERIMENTAL: this API may change without prior notice

De-allocate memory used by set-summary.

Parameters

setsum

Pointer to the set summary.

void rte_member_reset

(

const struct rte_member_setsum *

setsum

)

Warning

EXPERIMENTAL: this API may change without prior notice

Reset the set-summary tables. E.g. reset bits to be 0 in BF, reset set_id in each entry to be RTE_MEMBER_NO_MATCH in HT based SS.

Parameters

setsum

Pointer to the set-summary.

int rte_member_delete	(	const struct rte_member_setsum *	setsum,
		const void *	key,
		member_set_t	set_id
	)

Warning

EXPERIMENTAL: this API may change without prior notice

Delete items from the set-summary. Note that vBF does not support deletion in current implementation. For vBF, error code of -EINVAL will be returned.

Parameters

setsum	Pointer to the set-summary.
key	Pointer of the key to be deleted.
set_id	For HT mode, we need both key and its corresponding set_id to properly delete the key. Without set_id, we may delete other keys with the same signature.

Returns

If no entry found to delete, an error code of -ENOENT could be returned.