diff mbox series

[v2,2/3] hash: add predictable RSS implementation

Message ID 1617738643-258635-3-git-send-email-vladimir.medvedkin@intel.com (mailing list archive)
State New
Delegated to: David Marchand
Headers show
Series Predictable RSS feature | expand

Checks

Context Check Description
ci/checkpatch warning coding style issues

Commit Message

Vladimir Medvedkin April 6, 2021, 7:50 p.m. UTC
This patch implements predictable RSS functionality.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 lib/librte_hash/rte_thash.c | 577 ++++++++++++++++++++++++++++++++++++++++++--
 lib/librte_hash/rte_thash.h |  42 ++++
 lib/librte_hash/version.map |   1 +
 3 files changed, 602 insertions(+), 18 deletions(-)

Comments

Ananyev, Konstantin April 7, 2021, 12:53 p.m. UTC | #1
Hi Vladimir,

Few comments below, mostly minor.
One generic one - doc seems missing.
With that in place:
Acked-by: Konstantin Ananyev <konstantin.ananyev@intel.com>

> 
> This patch implements predictable RSS functionality.
> 
> Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
> ---
>  lib/librte_hash/rte_thash.c | 577 ++++++++++++++++++++++++++++++++++++++++++--
>  lib/librte_hash/rte_thash.h |  42 ++++
>  lib/librte_hash/version.map |   1 +
>  3 files changed, 602 insertions(+), 18 deletions(-)
> 
> diff --git a/lib/librte_hash/rte_thash.c b/lib/librte_hash/rte_thash.c
> index 79e8724..cc60ada 100644
> --- a/lib/librte_hash/rte_thash.c
> +++ b/lib/librte_hash/rte_thash.c
> @@ -12,6 +12,45 @@
>  #include <rte_malloc.h>
> 
>  #define THASH_NAME_LEN		64
> +#define TOEPLITZ_HASH_LEN	32
> +
> +#define	RETA_SZ_MIN	2U
> +#define	RETA_SZ_MAX	16U

Should these RETA_SZ defines be in public header?
So user can know what are allowed values?

> +#define RETA_SZ_IN_RANGE(reta_sz)	((reta_sz >= RETA_SZ_MIN) && \
> +					(reta_sz <= RETA_SZ_MAX))
> +
> +TAILQ_HEAD(rte_thash_list, rte_tailq_entry);
> +static struct rte_tailq_elem rte_thash_tailq = {
> +	.name = "RTE_THASH",
> +};
> +EAL_REGISTER_TAILQ(rte_thash_tailq)
> +
> +/**
> + * Table of some irreducible polinomials over GF(2).
> + * For lfsr they are reperesented in BE bit order, and
> + * x^0 is masked out.
> + * For example, poly x^5 + x^2 + 1 will be represented
> + * as (101001b & 11111b) = 01001b = 0x9
> + */
> +static const uint32_t irreducible_poly_table[][4] = {
> +	{0, 0, 0, 0},	/** < degree 0 */
> +	{1, 1, 1, 1},	/** < degree 1 */
> +	{0x3, 0x3, 0x3, 0x3},	/** < degree 2 and so on... */
> +	{0x5, 0x3, 0x5, 0x3},
> +	{0x9, 0x3, 0x9, 0x3},
> +	{0x9, 0x1b, 0xf, 0x5},
> +	{0x21, 0x33, 0x1b, 0x2d},
> +	{0x41, 0x11, 0x71, 0x9},
> +	{0x71, 0xa9, 0xf5, 0x8d},
> +	{0x21, 0xd1, 0x69, 0x1d9},
> +	{0x81, 0x2c1, 0x3b1, 0x185},
> +	{0x201, 0x541, 0x341, 0x461},
> +	{0x941, 0x609, 0xe19, 0x45d},
> +	{0x1601, 0x1f51, 0x1171, 0x359},
> +	{0x2141, 0x2111, 0x2db1, 0x2109},
> +	{0x4001, 0x801, 0x101, 0x7301},
> +	{0x7781, 0xa011, 0x4211, 0x86d9},
> +};
> 
>  struct thash_lfsr {
>  	uint32_t	ref_cnt;
> @@ -31,8 +70,10 @@ struct rte_thash_subtuple_helper {
>  	char	name[THASH_NAME_LEN];	/** < Name of subtuple configuration */
>  	LIST_ENTRY(rte_thash_subtuple_helper)	next;
>  	struct thash_lfsr	*lfsr;
> -	uint32_t	offset;		/** < Offset in bits of the subtuple */
> -	uint32_t	len;		/** < Length in bits of the subtuple */
> +	uint32_t	offset;		/** < Offset of the m-sequence */
> +	uint32_t	len;		/** < Length of the m-sequence */
> +	uint32_t	tuple_offset;	/** < Offset in bits of the subtuple */
> +	uint32_t	tuple_len;	/** < Length in bits of the subtuple */
>  	uint32_t	lsb_msk;	/** < (1 << reta_sz_log) - 1 */
>  	__extension__ uint32_t	compl_table[0] __rte_cache_aligned;
>  	/** < Complimentary table */
> @@ -48,49 +89,549 @@ struct rte_thash_ctx {
>  	uint8_t		hash_key[0];
>  };
> 
> +static inline uint32_t
> +get_bit_lfsr(struct thash_lfsr *lfsr)
> +{
> +	uint32_t bit, ret;
> +
> +	/*
> +	 * masking the TAP bits defined by the polynomial and
> +	 * calculating parity
> +	 */
> +	bit = __builtin_popcount(lfsr->state & lfsr->poly) & 0x1;
> +	ret = lfsr->state & 0x1;
> +	lfsr->state = ((lfsr->state >> 1) | (bit << (lfsr->deg - 1))) &
> +		((1 << lfsr->deg) - 1);
> +
> +	lfsr->bits_cnt++;
> +	return ret;
> +}
> +
> +static inline uint32_t
> +get_rev_bit_lfsr(struct thash_lfsr *lfsr)
> +{
> +	uint32_t bit, ret;
> +
> +	bit = __builtin_popcount(lfsr->rev_state & lfsr->rev_poly) & 0x1;
> +	ret = lfsr->rev_state & (1 << (lfsr->deg - 1));
> +	lfsr->rev_state = ((lfsr->rev_state << 1) | bit) &
> +		((1 << lfsr->deg) - 1);
> +
> +	lfsr->bits_cnt++;
> +	return ret;
> +}
> +
> +static inline uint32_t
> +thash_get_rand_poly(uint32_t poly_degree)
> +{
> +	return irreducible_poly_table[poly_degree][rte_rand() %
> +		RTE_DIM(irreducible_poly_table[poly_degree])];
> +}
> +
> +static struct thash_lfsr *
> +alloc_lfsr(struct rte_thash_ctx *ctx)
> +{
> +	struct thash_lfsr *lfsr;
> +	uint32_t i;
> +
> +	if (ctx == NULL)
> +		return NULL;
> +
> +	lfsr = rte_zmalloc(NULL, sizeof(struct thash_lfsr), 0);
> +	if (lfsr == NULL)
> +		return NULL;
> +
> +	lfsr->deg = ctx->reta_sz_log;
> +	lfsr->poly = thash_get_rand_poly(lfsr->deg);
> +	do {
> +		lfsr->state = rte_rand() & ((1 << lfsr->deg) - 1);
> +	} while (lfsr->state == 0);
> +	/* init reverse order polynomial */
> +	lfsr->rev_poly = (lfsr->poly >> 1) | (1 << (lfsr->deg - 1));
> +	/* init proper rev_state*/
> +	lfsr->rev_state = lfsr->state;
> +	for (i = 0; i <= lfsr->deg; i++)
> +		get_rev_bit_lfsr(lfsr);
> +
> +	/* clear bits_cnt after rev_state was inited */
> +	lfsr->bits_cnt = 0;
> +	lfsr->ref_cnt = 1;
> +
> +	return lfsr;
> +}
> +
> +static void
> +attach_lfsr(struct rte_thash_subtuple_helper *h, struct thash_lfsr *lfsr)
> +{
> +	lfsr->ref_cnt++;
> +	h->lfsr = lfsr;
> +}
> +
> +static void
> +free_lfsr(struct thash_lfsr *lfsr)
> +{
> +	lfsr->ref_cnt--;
> +	if (lfsr->ref_cnt == 0)
> +		rte_free(lfsr);
> +}
> +
>  struct rte_thash_ctx *
> -rte_thash_init_ctx(const char *name __rte_unused,
> -	uint32_t key_len __rte_unused, uint32_t reta_sz __rte_unused,
> -	uint8_t *key __rte_unused, uint32_t flags __rte_unused)
> +rte_thash_init_ctx(const char *name, uint32_t key_len, uint32_t reta_sz,
> +	uint8_t *key, uint32_t flags)
>  {
> +	struct rte_thash_ctx *ctx;
> +	struct rte_tailq_entry *te;
> +	struct rte_thash_list *thash_list;
> +	uint32_t i;

Empty line is  missing.

> +	if ((name == NULL) || (key_len == 0) || !RETA_SZ_IN_RANGE(reta_sz)) {
> +		rte_errno = EINVAL;
> +		return NULL;
> +	}
> +
> +	thash_list = RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list);
> +
> +	rte_mcfg_tailq_write_lock();
> +
> +	/* guarantee there's no existing */
> +	TAILQ_FOREACH(te, thash_list, next) {
> +		ctx = (struct rte_thash_ctx *)te->data;
> +		if (strncmp(name, ctx->name, sizeof(ctx->name)) == 0)
> +			break;
> +	}
> +	ctx = NULL;
> +	if (te != NULL) {
> +		rte_errno = EEXIST;
> +		goto exit;
> +	}
> +
> +	/* allocate tailq entry */
> +	te = rte_zmalloc("THASH_TAILQ_ENTRY", sizeof(*te), 0);
> +	if (te == NULL) {
> +		RTE_LOG(ERR, HASH,
> +			"Can not allocate tailq entry for thash context %s\n",
> +			name);
> +		rte_errno = ENOMEM;
> +		goto exit;
> +	}
> +
> +	ctx = rte_zmalloc(NULL, sizeof(struct rte_thash_ctx) + key_len, 0);
> +	if (ctx == NULL) {
> +		RTE_LOG(ERR, HASH, "thash ctx %s memory allocation failed\n",
> +			name);
> +		rte_errno = ENOMEM;
> +		goto free_te;
> +	}
> +
> +	rte_strlcpy(ctx->name, name, sizeof(ctx->name));
> +	ctx->key_len = key_len;
> +	ctx->reta_sz_log = reta_sz;
> +	LIST_INIT(&ctx->head);
> +	ctx->flags = flags;
> +
> +	if (key)
> +		rte_memcpy(ctx->hash_key, key, key_len);
> +	else {
> +		for (i = 0; i < key_len; i++)
> +			ctx->hash_key[i] = rte_rand();
> +	}
> +
> +	te->data = (void *)ctx;
> +	TAILQ_INSERT_TAIL(thash_list, te, next);
> +
> +	rte_mcfg_tailq_write_unlock();
> +
> +	return ctx;
> +free_te:
> +	rte_free(te);
> +exit:
> +	rte_mcfg_tailq_write_unlock();
>  	return NULL;
>  }
> 
>  struct rte_thash_ctx *
> -rte_thash_find_existing(const char *name __rte_unused)
> +rte_thash_find_existing(const char *name)
>  {
> -	return NULL;
> +	struct rte_thash_ctx *ctx;
> +	struct rte_tailq_entry *te;
> +	struct rte_thash_list *thash_list;
> +
> +	thash_list = RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list);
> +
> +	rte_mcfg_tailq_read_lock();
> +	TAILQ_FOREACH(te, thash_list, next) {
> +		ctx = (struct rte_thash_ctx *)te->data;
> +		if (strncmp(name, ctx->name, sizeof(ctx->name)) == 0)
> +			break;
> +	}
> +
> +	rte_mcfg_tailq_read_unlock();
> +
> +	if (te == NULL) {
> +		rte_errno = ENOENT;
> +		return NULL;
> +	}
> +
> +	return ctx;
>  }
> 
>  void
> -rte_thash_free_ctx(struct rte_thash_ctx *ctx __rte_unused)
> +rte_thash_free_ctx(struct rte_thash_ctx *ctx)
>  {
> +	struct rte_tailq_entry *te;
> +	struct rte_thash_list *thash_list;
> +	struct rte_thash_subtuple_helper *ent, *tmp;
> +
> +	if (ctx == NULL)
> +		return;
> +
> +	thash_list = RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list);
> +	rte_mcfg_tailq_write_lock();
> +	TAILQ_FOREACH(te, thash_list, next) {
> +		if (te->data == (void *)ctx)
> +			break;
> +	}
> +
> +	if (te != NULL)
> +		TAILQ_REMOVE(thash_list, te, next);
> +
> +	rte_mcfg_tailq_write_unlock();
> +	ent = LIST_FIRST(&(ctx->head));
> +	while (ent) {
> +		free_lfsr(ent->lfsr);
> +		tmp = ent;
> +		ent = LIST_NEXT(ent, next);
> +		LIST_REMOVE(tmp, next);
> +		rte_free(tmp);
> +	}
> +
> +	rte_free(ctx);
> +	rte_free(te);
> +}
> +
> +static inline void
> +set_bit(uint8_t *ptr, uint32_t bit, uint32_t pos)
> +{
> +	uint32_t byte_idx = pos >> 3;

Just as a nit to be consistent with the line below:
pos / CHAR_BIT; 

> +	uint32_t bit_idx = (CHAR_BIT - 1) - (pos & (CHAR_BIT - 1));
> +	uint8_t tmp;
> +
> +	tmp = ptr[byte_idx];
> +	tmp &= ~(1 << bit_idx);
> +	tmp |= bit << bit_idx;
> +	ptr[byte_idx] = tmp;
> +}
> +
> +/**
> + * writes m-sequence to the hash_key for range [start, end]
> + * (i.e. including start and end positions)
> + */
> +static int
> +generate_subkey(struct rte_thash_ctx *ctx, struct thash_lfsr *lfsr,
> +	uint32_t start, uint32_t end)
> +{
> +	uint32_t i;
> +	uint32_t req_bits = (start < end) ? (end - start) : (start - end);
> +	req_bits++; /* due to incuding end */
> +
> +	/* check if lfsr overflow period of the m-sequence */
> +	if (((lfsr->bits_cnt + req_bits) > (1ULL << lfsr->deg) - 1) &&
> +			((ctx->flags & RTE_THASH_IGNORE_PERIOD_OVERFLOW) !=
> +			RTE_THASH_IGNORE_PERIOD_OVERFLOW))
> +		return -ENOSPC;
> +
> +	if (start < end) {
> +		/* original direction (from left to right)*/
> +		for (i = start; i <= end; i++)
> +			set_bit(ctx->hash_key, get_bit_lfsr(lfsr), i);
> +
> +	} else {
> +		/* reverse direction (from right to left) */
> +		for (i = end; i >= start; i--)
> +			set_bit(ctx->hash_key, get_rev_bit_lfsr(lfsr), i);
> +	}
> +
> +	return 0;
> +}
> +
> +static inline uint32_t
> +get_subvalue(struct rte_thash_ctx *ctx, uint32_t offset)
> +{
> +	uint32_t *tmp, val;
> +
> +	tmp = (uint32_t *)(&ctx->hash_key[offset >> 3]);
> +	val = rte_be_to_cpu_32(*tmp);
> +	val >>= (TOEPLITZ_HASH_LEN - ((offset & (CHAR_BIT - 1)) +
> +		ctx->reta_sz_log));
> +
> +	return val & ((1 << ctx->reta_sz_log) - 1);
> +}
> +
> +static inline void
> +generate_compliment_table(struct rte_thash_ctx *ctx,
> +	struct rte_thash_subtuple_helper *h)
> +{
> +	int i, j, k;
> +	uint32_t val;
> +	uint32_t start;
> +
> +	start = h->offset + h->len - (2 * ctx->reta_sz_log - 1);
> +
> +	for (i = 1; i < (1 << ctx->reta_sz_log); i++) {
> +		val = 0;
> +		for (j = i; j; j &= (j - 1)) {
> +			k = rte_bsf32(j);
> +			val ^= get_subvalue(ctx, start - k +
> +				ctx->reta_sz_log - 1);
> +		}
> +		h->compl_table[val] = i;
> +	}
> +}
> +
> +static inline int
> +insert_before(struct rte_thash_ctx *ctx,
> +	struct rte_thash_subtuple_helper *ent,
> +	struct rte_thash_subtuple_helper *cur_ent,
> +	struct rte_thash_subtuple_helper *next_ent,
> +	uint32_t start, uint32_t end, uint32_t range_end)
> +{
> +	int ret;
> +
> +	if (end < cur_ent->offset) {
> +		ent->lfsr = alloc_lfsr(ctx);
> +		if (ent->lfsr == NULL) {
> +			rte_free(ent);
> +			return -ENOMEM;
> +		}
> +		/* generate nonoverlapping range [start, end) */
> +		ret = generate_subkey(ctx, ent->lfsr, start, end - 1);
> +		if (ret != 0) {
> +			free_lfsr(ent->lfsr);
> +			rte_free(ent);
> +			return ret;
> +		}
> +	} else if ((next_ent != NULL) && (end > next_ent->offset)) {
> +		rte_free(ent);
> +		return -ENOSPC;
> +	}
> +	attach_lfsr(ent, cur_ent->lfsr);
> +
> +	/**
> +	 * generate partially overlapping range
> +	 * [start, cur_ent->start) in reverse order
> +	 */
> +	ret = generate_subkey(ctx, ent->lfsr, cur_ent->offset - 1, start);
> +	if (ret != 0) {
> +		free_lfsr(ent->lfsr);
> +		rte_free(ent);
> +		return ret;
> +	}
> +
> +	if (end > range_end) {
> +		/**
> +		 * generate partially overlapping range
> +		 * (range_end, end)
> +		 */
> +		ret = generate_subkey(ctx, ent->lfsr, range_end, end - 1);
> +		if (ret != 0) {
> +			free_lfsr(ent->lfsr);
> +			rte_free(ent);
> +			return ret;
> +		}
> +	}
> +
> +	LIST_INSERT_BEFORE(cur_ent, ent, next);
> +	generate_compliment_table(ctx, ent);
> +	ctx->subtuples_nb++;
> +	return 0;
> +}
> +
> +static inline int
> +insert_after(struct rte_thash_ctx *ctx,
> +	struct rte_thash_subtuple_helper *ent,
> +	struct rte_thash_subtuple_helper *cur_ent,
> +	struct rte_thash_subtuple_helper *next_ent,
> +	struct rte_thash_subtuple_helper *prev_ent,
> +	uint32_t end, uint32_t range_end)
> +{
> +	int ret;
> +
> +	if ((next_ent != NULL) && (end > next_ent->offset)) {
> +		rte_free(ent);
> +		return -EEXIST;
> +	}
> +
> +	attach_lfsr(ent, cur_ent->lfsr);
> +	if (end > range_end) {
> +		/**
> +		 * generate partially overlapping range
> +		 * (range_end, end)
> +		 */
> +		ret = generate_subkey(ctx, ent->lfsr, range_end, end - 1);
> +		if (ret != 0) {
> +			free_lfsr(ent->lfsr);
> +			rte_free(ent);
> +			return ret;
> +		}
> +	}
> +
> +	LIST_INSERT_AFTER(prev_ent, ent, next);
> +	generate_compliment_table(ctx, ent);
> +	ctx->subtuples_nb++;
> +
> +	return 0;
>  }
> 
>  int
> -rte_thash_add_helper(struct rte_thash_ctx *ctx __rte_unused,
> -	const char *name __rte_unused, uint32_t len __rte_unused,
> -	uint32_t offset __rte_unused)
> +rte_thash_add_helper(struct rte_thash_ctx *ctx, const char *name, uint32_t len,
> +	uint32_t offset)
>  {
> +	struct rte_thash_subtuple_helper *ent, *cur_ent, *prev_ent, *next_ent;
> +	uint32_t start, end;
> +	int ret;
> +
> +	if ((ctx == NULL) || (name == NULL) || (len < ctx->reta_sz_log) ||
> +			((offset + len + TOEPLITZ_HASH_LEN - 1) >
> +			ctx->key_len * CHAR_BIT))
> +		return -EINVAL;
> +
> +	/* Check for existing name*/
> +	LIST_FOREACH(cur_ent, &ctx->head, next) {
> +		if (strncmp(name, cur_ent->name, sizeof(cur_ent->name)) == 0)
> +			return -EEXIST;
> +	}
> +
> +	end = offset + len + TOEPLITZ_HASH_LEN - 1;
> +	start = ((ctx->flags & RTE_THASH_MINIMAL_SEQ) ==
> +		RTE_THASH_MINIMAL_SEQ) ? (end - (2 * ctx->reta_sz_log - 1)) :
> +		offset;
> +
> +	ent = rte_zmalloc(NULL, sizeof(struct rte_thash_subtuple_helper) +
> +		sizeof(uint32_t) * (1 << ctx->reta_sz_log), 0);

Helper can be used by data-path code (via rte_thash_get_compliment()) right?
Then might be better to align it at cache-line. 

> +	if (ent == NULL)
> +		return -ENOMEM;
> +
> +	rte_strlcpy(ent->name, name, sizeof(ent->name));
> +	ent->offset = start;
> +	ent->len = end - start;
> +	ent->tuple_offset = offset;
> +	ent->tuple_len = len;
> +	ent->lsb_msk = (1 << ctx->reta_sz_log) - 1;
> +
> +	cur_ent = LIST_FIRST(&ctx->head);
> +	while (cur_ent) {
> +		uint32_t range_end = cur_ent->offset + cur_ent->len;
> +		next_ent = LIST_NEXT(cur_ent, next);
> +		prev_ent = cur_ent;
> +		/* Iterate through overlapping ranges */
> +		while ((next_ent != NULL) && (next_ent->offset < range_end)) {
> +			range_end = RTE_MAX(next_ent->offset + next_ent->len,
> +				range_end);
> +			if (start > next_ent->offset)
> +				prev_ent = next_ent;
> +
> +			next_ent = LIST_NEXT(next_ent, next);
> +		}
> +
> +		if (start < cur_ent->offset)
> +			return insert_before(ctx, ent, cur_ent, next_ent,
> +				start, end, range_end);
> +		else if (start < range_end)
> +			return insert_after(ctx, ent, cur_ent, next_ent,
> +				prev_ent, end, range_end);
> +
> +		cur_ent = next_ent;
> +		continue;
> +	}
> +
> +	ent->lfsr = alloc_lfsr(ctx);
> +	if (ent->lfsr == NULL) {
> +		rte_free(ent);
> +		return -ENOMEM;
> +	}
> +
> +	/* generate nonoverlapping range [start, end) */
> +	ret = generate_subkey(ctx, ent->lfsr, start, end - 1);
> +	if (ret != 0) {
> +		free_lfsr(ent->lfsr);
> +		rte_free(ent);
> +		return ret;
> +	}
> +	if (LIST_EMPTY(&ctx->head)) {
> +		LIST_INSERT_HEAD(&ctx->head, ent, next);
> +	} else {
> +		LIST_FOREACH(next_ent, &ctx->head, next)
> +			prev_ent = next_ent;
> +
> +		LIST_INSERT_AFTER(prev_ent, ent, next);
> +	}
> +	generate_compliment_table(ctx, ent);
> +	ctx->subtuples_nb++;
> +
>  	return 0;
>  }
> 
>  struct rte_thash_subtuple_helper *
> -rte_thash_get_helper(struct rte_thash_ctx *ctx __rte_unused,
> -	const char *name __rte_unused)
> +rte_thash_get_helper(struct rte_thash_ctx *ctx, const char *name)
>  {
> +	struct rte_thash_subtuple_helper *ent;
> +
> +	if ((ctx == NULL) || (name == NULL))
> +		return NULL;
> +
> +	LIST_FOREACH(ent, &ctx->head, next) {
> +		if (strncmp(name, ent->name, sizeof(ent->name)) == 0)
> +			return ent;
> +	}
> +
>  	return NULL;
>  }
> 
>  uint32_t
> -rte_thash_get_compliment(struct rte_thash_subtuple_helper *h __rte_unused,
> -	uint32_t hash __rte_unused, uint32_t desired_hash __rte_unused)
> +rte_thash_get_compliment(struct rte_thash_subtuple_helper *h,
> +	uint32_t hash, uint32_t desired_hash)
>  {
> -	return 0;
> +	return h->compl_table[(hash ^ desired_hash) & h->lsb_msk];
>  }

Would it make sense to add another-one for multi values:
rte_thash_get_compliment(uint32_t hash, const uint32_t desired_hashes[], uint32_t adj_hash[], uint32_t num);
So user can get adjustment values for multiple queues at once? 

> 
>  const uint8_t *
> -rte_thash_get_key(struct rte_thash_ctx *ctx __rte_unused)
> +rte_thash_get_key(struct rte_thash_ctx *ctx)
>  {
> -	return NULL;
> +	return ctx->hash_key;
> +}
> +
> +static inline void
> +xor_bit(uint8_t *ptr, uint32_t bit, uint32_t pos)
> +{
> +	uint32_t byte_idx = pos >> 3;
> +	uint32_t bit_idx = (CHAR_BIT - 1) - (pos & (CHAR_BIT - 1));
> +	uint8_t tmp;
> +
> +	tmp = ptr[byte_idx];
> +	tmp ^= bit << bit_idx;
> +	ptr[byte_idx] = tmp;
> +}
> +
> +int
> +rte_thash_adjust_tuple(struct rte_thash_subtuple_helper *h,
> +	uint8_t *orig_tuple, uint32_t adj_bits,
> +	rte_thash_check_tuple_t fn, void *userdata)
> +{
> +	unsigned i;
> +
> +	if ((h == NULL) || (orig_tuple == NULL))
> +		return -EINVAL;
> +
> +	adj_bits &= h->lsb_msk;
> +	/* Hint: LSB of adj_bits corresponds to offset + len bit of tuple */
> +	for (i = 0; i < sizeof(uint32_t) * CHAR_BIT; i++) {
> +		uint8_t bit = (adj_bits >> i) & 0x1;
> +		if (bit)
> +			xor_bit(orig_tuple, bit,
> +				h->tuple_offset + h->tuple_len - 1 - i);
> +	}
> +
> +	if (fn != NULL)
> +		return (fn(userdata, orig_tuple)) ? 0 : -EEXIST;
> +
> +	return 0;
>  }

Not sure is there much point to have a callback that is called only once.
Might be better to rework the function in a way that user to provide 2 callbacks -
one to generate new value, second to check.
Something like that:

int
rte_thash_gen_tuple(struct rte_thash_subtuple_helper *h,
	uint8_t *tuple, uint32_t desired_hash,
	int (*cb_gen_tuple)(uint8_t *, void *),
	int (*cb_check_tuple)(const uint8_t *, void *),
	void *userdata) 
{
	do {
		rc = cb_gen_tuple(tuple, userdata);
		if (rc != 0)
			return rc;
		hash = rte_softrss(tuple, ...);
		adj = rte_thash_get_compliment(h, hash, desired_hash);
		update_tuple(tuple, adj, ...);
		rc = cb_check_tuple(tuple, userdata); 
	} while(rc != 0);

             return rc;
}

> diff --git a/lib/librte_hash/rte_thash.h b/lib/librte_hash/rte_thash.h
> index 38a641b..fd67931 100644
> --- a/lib/librte_hash/rte_thash.h
> +++ b/lib/librte_hash/rte_thash.h
> @@ -360,6 +360,48 @@ __rte_experimental
>  const uint8_t *
>  rte_thash_get_key(struct rte_thash_ctx *ctx);
> 
> +/**
> + * Function prototype for the rte_thash_adjust_tuple
> + * to check if adjusted tuple could be used.
> + * Generally it is some kind of lookup function to check
> + * if adjusted tuple is already in use.
> + *
> + * @param userdata
> + *  Pointer to the userdata. It could be a pointer to the
> + *  table with used tuples to search.
> + * @param tuple
> + *  Pointer to the tuple to check
> + *
> + * @return
> + *  1 on success
> + *  0 otherwise
> + */
> +typedef int (*rte_thash_check_tuple_t)(void *userdata, uint8_t *tuple);
> +
> +/**
> + * Adjust tuple with complimentary bits.
> + *
> + * @param h
> + *  Pointer to the helper struct
> + * @param orig_tuple
> + *  Pointer to the tuple to be adjusted
> + * @param adj_bits
> + *  Valure returned by rte_thash_get_compliment
> + * @param fn
> + *  Callback function to check adjusted tuple. Could be NULL
> + * @param userdata
> + *  Pointer to the userdata to be passed to fn(). Could be NULL
> + *
> + * @return
> + *  0 on success
> + *  negative otherwise
> + */
> +__rte_experimental
> +int
> +rte_thash_adjust_tuple(struct rte_thash_subtuple_helper *h,
> +	uint8_t *orig_tuple, uint32_t adj_bits,
> +	rte_thash_check_tuple_t fn, void *userdata);
> +
>  #ifdef __cplusplus
>  }
>  #endif
> diff --git a/lib/librte_hash/version.map b/lib/librte_hash/version.map
> index 93cb230..a992a1e 100644
> --- a/lib/librte_hash/version.map
> +++ b/lib/librte_hash/version.map
> @@ -32,6 +32,7 @@ DPDK_21 {
>  EXPERIMENTAL {
>  	global:
> 
> +	rte_thash_adjust_tuple;
>  	rte_hash_free_key_with_position;
>  	rte_hash_lookup_with_hash_bulk;
>  	rte_hash_lookup_with_hash_bulk_data;
> --
> 2.7.4
Wang, Yipeng1 April 10, 2021, 12:10 a.m. UTC | #2
> -----Original Message-----
> From: Medvedkin, Vladimir <vladimir.medvedkin@intel.com>
> Sent: Tuesday, April 6, 2021 12:51 PM
> To: dev@dpdk.org
> Cc: Ananyev, Konstantin <konstantin.ananyev@intel.com>; Chilikin, Andrey
> <andrey.chilikin@intel.com>; Kinsella, Ray <ray.kinsella@intel.com>; Wang,
> Yipeng1 <yipeng1.wang@intel.com>; Gobriel, Sameh
> <sameh.gobriel@intel.com>; Richardson, Bruce
> <bruce.richardson@intel.com>
> Subject: [PATCH v2 2/3] hash: add predictable RSS implementation
> 
> This patch implements predictable RSS functionality.
> 
> Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
> ---
>  lib/librte_hash/rte_thash.c | 577
> ++++++++++++++++++++++++++++++++++++++++++--
>  lib/librte_hash/rte_thash.h |  42 ++++
>  lib/librte_hash/version.map |   1 +
>  3 files changed, 602 insertions(+), 18 deletions(-)
> 
> diff --git a/lib/librte_hash/rte_thash.c b/lib/librte_hash/rte_thash.c index
> 79e8724..cc60ada 100644
> --- a/lib/librte_hash/rte_thash.c
> +++ b/lib/librte_hash/rte_thash.c
> @@ -12,6 +12,45 @@
>  #include <rte_malloc.h>
> 
>  #define THASH_NAME_LEN		64
> +#define TOEPLITZ_HASH_LEN	32
> +
> +#define	RETA_SZ_MIN	2U
> +#define	RETA_SZ_MAX	16U
> +#define RETA_SZ_IN_RANGE(reta_sz)	((reta_sz >= RETA_SZ_MIN)
> && \
> +					(reta_sz <= RETA_SZ_MAX))
> +
> +TAILQ_HEAD(rte_thash_list, rte_tailq_entry); static struct
> +rte_tailq_elem rte_thash_tailq = {
> +	.name = "RTE_THASH",
> +};
> +EAL_REGISTER_TAILQ(rte_thash_tailq)
> +
> +/**
> + * Table of some irreducible polinomials over GF(2).
> + * For lfsr they are reperesented in BE bit order, and
> + * x^0 is masked out.
> + * For example, poly x^5 + x^2 + 1 will be represented
> + * as (101001b & 11111b) = 01001b = 0x9  */ static const uint32_t
> +irreducible_poly_table[][4] = {
> +	{0, 0, 0, 0},	/** < degree 0 */
> +	{1, 1, 1, 1},	/** < degree 1 */
> +	{0x3, 0x3, 0x3, 0x3},	/** < degree 2 and so on... */
> +	{0x5, 0x3, 0x5, 0x3},
> +	{0x9, 0x3, 0x9, 0x3},
> +	{0x9, 0x1b, 0xf, 0x5},
> +	{0x21, 0x33, 0x1b, 0x2d},
> +	{0x41, 0x11, 0x71, 0x9},
> +	{0x71, 0xa9, 0xf5, 0x8d},
> +	{0x21, 0xd1, 0x69, 0x1d9},
> +	{0x81, 0x2c1, 0x3b1, 0x185},
> +	{0x201, 0x541, 0x341, 0x461},
> +	{0x941, 0x609, 0xe19, 0x45d},
> +	{0x1601, 0x1f51, 0x1171, 0x359},
> +	{0x2141, 0x2111, 0x2db1, 0x2109},
> +	{0x4001, 0x801, 0x101, 0x7301},
> +	{0x7781, 0xa011, 0x4211, 0x86d9},
> +};
> 
>  struct thash_lfsr {
>  	uint32_t	ref_cnt;
> @@ -31,8 +70,10 @@ struct rte_thash_subtuple_helper {
>  	char	name[THASH_NAME_LEN];	/** < Name of subtuple
> configuration */
>  	LIST_ENTRY(rte_thash_subtuple_helper)	next;
>  	struct thash_lfsr	*lfsr;
> -	uint32_t	offset;		/** < Offset in bits of the subtuple */
> -	uint32_t	len;		/** < Length in bits of the subtuple
> */
> +	uint32_t	offset;		/** < Offset of the m-sequence */
> +	uint32_t	len;		/** < Length of the m-sequence */
> +	uint32_t	tuple_offset;	/** < Offset in bits of the subtuple */
> +	uint32_t	tuple_len;	/** < Length in bits of the subtuple
> */
>  	uint32_t	lsb_msk;	/** < (1 << reta_sz_log) - 1 */
>  	__extension__ uint32_t	compl_table[0] __rte_cache_aligned;
>  	/** < Complimentary table */
> @@ -48,49 +89,549 @@ struct rte_thash_ctx {
>  	uint8_t		hash_key[0];
>  };
> 
> +static inline uint32_t
> +get_bit_lfsr(struct thash_lfsr *lfsr)
> +{
> +	uint32_t bit, ret;
> +
> +	/*
> +	 * masking the TAP bits defined by the polynomial and
> +	 * calculating parity
> +	 */
> +	bit = __builtin_popcount(lfsr->state & lfsr->poly) & 0x1;
> +	ret = lfsr->state & 0x1;
> +	lfsr->state = ((lfsr->state >> 1) | (bit << (lfsr->deg - 1))) &
> +		((1 << lfsr->deg) - 1);
> +
> +	lfsr->bits_cnt++;
> +	return ret;
> +}
> +
> +static inline uint32_t
> +get_rev_bit_lfsr(struct thash_lfsr *lfsr) {
> +	uint32_t bit, ret;
> +
> +	bit = __builtin_popcount(lfsr->rev_state & lfsr->rev_poly) & 0x1;
> +	ret = lfsr->rev_state & (1 << (lfsr->deg - 1));
> +	lfsr->rev_state = ((lfsr->rev_state << 1) | bit) &
> +		((1 << lfsr->deg) - 1);
> +
> +	lfsr->bits_cnt++;
> +	return ret;
> +}
> +
> +static inline uint32_t
> +thash_get_rand_poly(uint32_t poly_degree) {
> +	return irreducible_poly_table[poly_degree][rte_rand() %
> +		RTE_DIM(irreducible_poly_table[poly_degree])];
> +}
> +
> +static struct thash_lfsr *
> +alloc_lfsr(struct rte_thash_ctx *ctx)
> +{
> +	struct thash_lfsr *lfsr;
> +	uint32_t i;
> +
> +	if (ctx == NULL)
> +		return NULL;
> +
> +	lfsr = rte_zmalloc(NULL, sizeof(struct thash_lfsr), 0);
> +	if (lfsr == NULL)
> +		return NULL;
> +
> +	lfsr->deg = ctx->reta_sz_log;
> +	lfsr->poly = thash_get_rand_poly(lfsr->deg);
> +	do {
> +		lfsr->state = rte_rand() & ((1 << lfsr->deg) - 1);
> +	} while (lfsr->state == 0);
> +	/* init reverse order polynomial */
> +	lfsr->rev_poly = (lfsr->poly >> 1) | (1 << (lfsr->deg - 1));
> +	/* init proper rev_state*/
> +	lfsr->rev_state = lfsr->state;
> +	for (i = 0; i <= lfsr->deg; i++)
> +		get_rev_bit_lfsr(lfsr);
> +
> +	/* clear bits_cnt after rev_state was inited */
> +	lfsr->bits_cnt = 0;
> +	lfsr->ref_cnt = 1;
> +
> +	return lfsr;
> +}
> +
> +static void
> +attach_lfsr(struct rte_thash_subtuple_helper *h, struct thash_lfsr
> +*lfsr) {
> +	lfsr->ref_cnt++;
> +	h->lfsr = lfsr;
> +}
> +
> +static void
> +free_lfsr(struct thash_lfsr *lfsr)
> +{
> +	lfsr->ref_cnt--;
> +	if (lfsr->ref_cnt == 0)
> +		rte_free(lfsr);
> +}
> +
>  struct rte_thash_ctx *
> -rte_thash_init_ctx(const char *name __rte_unused,
> -	uint32_t key_len __rte_unused, uint32_t reta_sz __rte_unused,
> -	uint8_t *key __rte_unused, uint32_t flags __rte_unused)
> +rte_thash_init_ctx(const char *name, uint32_t key_len, uint32_t reta_sz,
> +	uint8_t *key, uint32_t flags)
>  {
> +	struct rte_thash_ctx *ctx;
> +	struct rte_tailq_entry *te;
> +	struct rte_thash_list *thash_list;
> +	uint32_t i;
> +	if ((name == NULL) || (key_len == 0)
> || !RETA_SZ_IN_RANGE(reta_sz)) {
> +		rte_errno = EINVAL;
> +		return NULL;
> +	}
> +
> +	thash_list = RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list);
> +
> +	rte_mcfg_tailq_write_lock();
> +
> +	/* guarantee there's no existing */
> +	TAILQ_FOREACH(te, thash_list, next) {
> +		ctx = (struct rte_thash_ctx *)te->data;
> +		if (strncmp(name, ctx->name, sizeof(ctx->name)) == 0)
> +			break;
> +	}
> +	ctx = NULL;
> +	if (te != NULL) {
> +		rte_errno = EEXIST;
> +		goto exit;
> +	}
> +
> +	/* allocate tailq entry */
> +	te = rte_zmalloc("THASH_TAILQ_ENTRY", sizeof(*te), 0);
> +	if (te == NULL) {
> +		RTE_LOG(ERR, HASH,
> +			"Can not allocate tailq entry for thash context %s\n",
> +			name);
> +		rte_errno = ENOMEM;
> +		goto exit;
> +	}
> +
> +	ctx = rte_zmalloc(NULL, sizeof(struct rte_thash_ctx) + key_len, 0);
> +	if (ctx == NULL) {
> +		RTE_LOG(ERR, HASH, "thash ctx %s memory allocation
> failed\n",
> +			name);
> +		rte_errno = ENOMEM;
> +		goto free_te;
> +	}
> +
> +	rte_strlcpy(ctx->name, name, sizeof(ctx->name));
> +	ctx->key_len = key_len;
> +	ctx->reta_sz_log = reta_sz;
> +	LIST_INIT(&ctx->head);
> +	ctx->flags = flags;
> +
> +	if (key)
> +		rte_memcpy(ctx->hash_key, key, key_len);
> +	else {
> +		for (i = 0; i < key_len; i++)
> +			ctx->hash_key[i] = rte_rand();
> +	}
> +
> +	te->data = (void *)ctx;
> +	TAILQ_INSERT_TAIL(thash_list, te, next);
> +
> +	rte_mcfg_tailq_write_unlock();
> +
> +	return ctx;
> +free_te:
> +	rte_free(te);
> +exit:
> +	rte_mcfg_tailq_write_unlock();
>  	return NULL;
>  }
> 
>  struct rte_thash_ctx *
> -rte_thash_find_existing(const char *name __rte_unused)
> +rte_thash_find_existing(const char *name)
>  {
> -	return NULL;
> +	struct rte_thash_ctx *ctx;
> +	struct rte_tailq_entry *te;
> +	struct rte_thash_list *thash_list;
> +
> +	thash_list = RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list);
> +
> +	rte_mcfg_tailq_read_lock();
> +	TAILQ_FOREACH(te, thash_list, next) {
> +		ctx = (struct rte_thash_ctx *)te->data;
> +		if (strncmp(name, ctx->name, sizeof(ctx->name)) == 0)
> +			break;
> +	}
> +
> +	rte_mcfg_tailq_read_unlock();
> +
> +	if (te == NULL) {
> +		rte_errno = ENOENT;
> +		return NULL;
> +	}
> +
> +	return ctx;
>  }
> 
>  void
> -rte_thash_free_ctx(struct rte_thash_ctx *ctx __rte_unused)
> +rte_thash_free_ctx(struct rte_thash_ctx *ctx)
>  {
> +	struct rte_tailq_entry *te;
> +	struct rte_thash_list *thash_list;
> +	struct rte_thash_subtuple_helper *ent, *tmp;
> +
> +	if (ctx == NULL)
> +		return;
> +
> +	thash_list = RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list);
> +	rte_mcfg_tailq_write_lock();
> +	TAILQ_FOREACH(te, thash_list, next) {
> +		if (te->data == (void *)ctx)
> +			break;
> +	}
> +
> +	if (te != NULL)
> +		TAILQ_REMOVE(thash_list, te, next);
> +
> +	rte_mcfg_tailq_write_unlock();
> +	ent = LIST_FIRST(&(ctx->head));
> +	while (ent) {
> +		free_lfsr(ent->lfsr);
> +		tmp = ent;
> +		ent = LIST_NEXT(ent, next);
> +		LIST_REMOVE(tmp, next);
> +		rte_free(tmp);
> +	}
> +
> +	rte_free(ctx);
> +	rte_free(te);
> +}
> +
> +static inline void
> +set_bit(uint8_t *ptr, uint32_t bit, uint32_t pos) {
> +	uint32_t byte_idx = pos >> 3;
> +	uint32_t bit_idx = (CHAR_BIT - 1) - (pos & (CHAR_BIT - 1));
> +	uint8_t tmp;
> +
> +	tmp = ptr[byte_idx];
> +	tmp &= ~(1 << bit_idx);
> +	tmp |= bit << bit_idx;
> +	ptr[byte_idx] = tmp;
> +}
> +
> +/**
> + * writes m-sequence to the hash_key for range [start, end]
> + * (i.e. including start and end positions)  */ static int
> +generate_subkey(struct rte_thash_ctx *ctx, struct thash_lfsr *lfsr,
> +	uint32_t start, uint32_t end)
> +{
> +	uint32_t i;
> +	uint32_t req_bits = (start < end) ? (end - start) : (start - end);
> +	req_bits++; /* due to incuding end */
> +
> +	/* check if lfsr overflow period of the m-sequence */
> +	if (((lfsr->bits_cnt + req_bits) > (1ULL << lfsr->deg) - 1) &&
> +			((ctx->flags &
> RTE_THASH_IGNORE_PERIOD_OVERFLOW) !=
> +			RTE_THASH_IGNORE_PERIOD_OVERFLOW))
> +		return -ENOSPC;
[Wang, Yipeng] 
If nospace, should one increase lfsr->deg? Or if it is already the highest deg you predefined then what to do?
Maybe a log msg could help user with more information on the solutions.
> +
> +	if (start < end) {
> +		/* original direction (from left to right)*/
> +		for (i = start; i <= end; i++)
> +			set_bit(ctx->hash_key, get_bit_lfsr(lfsr), i);
> +
> +	} else {
> +		/* reverse direction (from right to left) */
> +		for (i = end; i >= start; i--)
> +			set_bit(ctx->hash_key, get_rev_bit_lfsr(lfsr), i);
> +	}
> +
> +	return 0;
> +}
> +
> +static inline uint32_t
> +get_subvalue(struct rte_thash_ctx *ctx, uint32_t offset) {
> +	uint32_t *tmp, val;
> +
> +	tmp = (uint32_t *)(&ctx->hash_key[offset >> 3]);
> +	val = rte_be_to_cpu_32(*tmp);
> +	val >>= (TOEPLITZ_HASH_LEN - ((offset & (CHAR_BIT - 1)) +
> +		ctx->reta_sz_log));
> +
> +	return val & ((1 << ctx->reta_sz_log) - 1); }
> +
> +static inline void
> +generate_compliment_table(struct rte_thash_ctx *ctx,
> +	struct rte_thash_subtuple_helper *h)
> +{
> +	int i, j, k;
> +	uint32_t val;
> +	uint32_t start;
> +
> +	start = h->offset + h->len - (2 * ctx->reta_sz_log - 1);
> +
> +	for (i = 1; i < (1 << ctx->reta_sz_log); i++) {
> +		val = 0;
> +		for (j = i; j; j &= (j - 1)) {
> +			k = rte_bsf32(j);
> +			val ^= get_subvalue(ctx, start - k +
> +				ctx->reta_sz_log - 1);
> +		}
> +		h->compl_table[val] = i;
> +	}
> +}
> +
> +static inline int
> +insert_before(struct rte_thash_ctx *ctx,
> +	struct rte_thash_subtuple_helper *ent,
> +	struct rte_thash_subtuple_helper *cur_ent,
> +	struct rte_thash_subtuple_helper *next_ent,
> +	uint32_t start, uint32_t end, uint32_t range_end) {
> +	int ret;
> +
> +	if (end < cur_ent->offset) {
> +		ent->lfsr = alloc_lfsr(ctx);
> +		if (ent->lfsr == NULL) {
> +			rte_free(ent);
> +			return -ENOMEM;
> +		}
> +		/* generate nonoverlapping range [start, end) */
> +		ret = generate_subkey(ctx, ent->lfsr, start, end - 1);
> +		if (ret != 0) {
> +			free_lfsr(ent->lfsr);
> +			rte_free(ent);
> +			return ret;
> +		}
> +	} else if ((next_ent != NULL) && (end > next_ent->offset)) {
> +		rte_free(ent);
> +		return -ENOSPC;
> +	}
> +	attach_lfsr(ent, cur_ent->lfsr);
> +
> +	/**
> +	 * generate partially overlapping range
> +	 * [start, cur_ent->start) in reverse order
> +	 */
> +	ret = generate_subkey(ctx, ent->lfsr, cur_ent->offset - 1, start);
> +	if (ret != 0) {
> +		free_lfsr(ent->lfsr);
> +		rte_free(ent);
> +		return ret;
> +	}
> +
> +	if (end > range_end) {
> +		/**
> +		 * generate partially overlapping range
> +		 * (range_end, end)
> +		 */
> +		ret = generate_subkey(ctx, ent->lfsr, range_end, end - 1);
> +		if (ret != 0) {
> +			free_lfsr(ent->lfsr);
> +			rte_free(ent);
> +			return ret;
> +		}
> +	}
> +
> +	LIST_INSERT_BEFORE(cur_ent, ent, next);
> +	generate_compliment_table(ctx, ent);
> +	ctx->subtuples_nb++;
> +	return 0;
> +}
> +
> +static inline int
> +insert_after(struct rte_thash_ctx *ctx,
> +	struct rte_thash_subtuple_helper *ent,
> +	struct rte_thash_subtuple_helper *cur_ent,
> +	struct rte_thash_subtuple_helper *next_ent,
> +	struct rte_thash_subtuple_helper *prev_ent,
> +	uint32_t end, uint32_t range_end)
> +{
> +	int ret;
> +
> +	if ((next_ent != NULL) && (end > next_ent->offset)) {
> +		rte_free(ent);
> +		return -EEXIST;
> +	}
> +
> +	attach_lfsr(ent, cur_ent->lfsr);
> +	if (end > range_end) {
> +		/**
> +		 * generate partially overlapping range
> +		 * (range_end, end)
> +		 */
> +		ret = generate_subkey(ctx, ent->lfsr, range_end, end - 1);
> +		if (ret != 0) {
> +			free_lfsr(ent->lfsr);
> +			rte_free(ent);
> +			return ret;
> +		}
> +	}
> +
> +	LIST_INSERT_AFTER(prev_ent, ent, next);
> +	generate_compliment_table(ctx, ent);
> +	ctx->subtuples_nb++;
> +
> +	return 0;
>  }
> 
>  int
> -rte_thash_add_helper(struct rte_thash_ctx *ctx __rte_unused,
> -	const char *name __rte_unused, uint32_t len __rte_unused,
> -	uint32_t offset __rte_unused)
> +rte_thash_add_helper(struct rte_thash_ctx *ctx, const char *name,
> uint32_t len,
> +	uint32_t offset)
>  {
> +	struct rte_thash_subtuple_helper *ent, *cur_ent, *prev_ent,
> *next_ent;
> +	uint32_t start, end;
> +	int ret;
> +
> +	if ((ctx == NULL) || (name == NULL) || (len < ctx->reta_sz_log) ||
> +			((offset + len + TOEPLITZ_HASH_LEN - 1) >
> +			ctx->key_len * CHAR_BIT))
> +		return -EINVAL;
> +
> +	/* Check for existing name*/
> +	LIST_FOREACH(cur_ent, &ctx->head, next) {
> +		if (strncmp(name, cur_ent->name, sizeof(cur_ent->name))
> == 0)
> +			return -EEXIST;
> +	}
> +
> +	end = offset + len + TOEPLITZ_HASH_LEN - 1;
> +	start = ((ctx->flags & RTE_THASH_MINIMAL_SEQ) ==
> +		RTE_THASH_MINIMAL_SEQ) ? (end - (2 * ctx->reta_sz_log -
> 1)) :
> +		offset;
> +
> +	ent = rte_zmalloc(NULL, sizeof(struct rte_thash_subtuple_helper) +
> +		sizeof(uint32_t) * (1 << ctx->reta_sz_log), 0);
> +	if (ent == NULL)
> +		return -ENOMEM;
> +
> +	rte_strlcpy(ent->name, name, sizeof(ent->name));
> +	ent->offset = start;
> +	ent->len = end - start;
> +	ent->tuple_offset = offset;
> +	ent->tuple_len = len;
> +	ent->lsb_msk = (1 << ctx->reta_sz_log) - 1;
> +
> +	cur_ent = LIST_FIRST(&ctx->head);
> +	while (cur_ent) {
> +		uint32_t range_end = cur_ent->offset + cur_ent->len;
> +		next_ent = LIST_NEXT(cur_ent, next);
> +		prev_ent = cur_ent;
> +		/* Iterate through overlapping ranges */
> +		while ((next_ent != NULL) && (next_ent->offset <
> range_end)) {
> +			range_end = RTE_MAX(next_ent->offset +
> next_ent->len,
> +				range_end);
> +			if (start > next_ent->offset)
> +				prev_ent = next_ent;
> +
> +			next_ent = LIST_NEXT(next_ent, next);
> +		}
> +
> +		if (start < cur_ent->offset)
> +			return insert_before(ctx, ent, cur_ent, next_ent,
> +				start, end, range_end);
> +		else if (start < range_end)
> +			return insert_after(ctx, ent, cur_ent, next_ent,
> +				prev_ent, end, range_end);
> +
> +		cur_ent = next_ent;
> +		continue;
> +	}
> +
> +	ent->lfsr = alloc_lfsr(ctx);
> +	if (ent->lfsr == NULL) {
> +		rte_free(ent);
> +		return -ENOMEM;
> +	}
> +
> +	/* generate nonoverlapping range [start, end) */
> +	ret = generate_subkey(ctx, ent->lfsr, start, end - 1);
> +	if (ret != 0) {
> +		free_lfsr(ent->lfsr);
> +		rte_free(ent);
> +		return ret;
> +	}
> +	if (LIST_EMPTY(&ctx->head)) {
> +		LIST_INSERT_HEAD(&ctx->head, ent, next);
> +	} else {
> +		LIST_FOREACH(next_ent, &ctx->head, next)
> +			prev_ent = next_ent;
> +
> +		LIST_INSERT_AFTER(prev_ent, ent, next);
> +	}
> +	generate_compliment_table(ctx, ent);
> +	ctx->subtuples_nb++;
> +
>  	return 0;
>  }
> 
>  struct rte_thash_subtuple_helper *
> -rte_thash_get_helper(struct rte_thash_ctx *ctx __rte_unused,
> -	const char *name __rte_unused)
> +rte_thash_get_helper(struct rte_thash_ctx *ctx, const char *name)
>  {
> +	struct rte_thash_subtuple_helper *ent;
> +
> +	if ((ctx == NULL) || (name == NULL))
> +		return NULL;
> +
> +	LIST_FOREACH(ent, &ctx->head, next) {
> +		if (strncmp(name, ent->name, sizeof(ent->name)) == 0)
> +			return ent;
> +	}
> +
>  	return NULL;
>  }
> 
>  uint32_t
> -rte_thash_get_compliment(struct rte_thash_subtuple_helper *h
> __rte_unused,
> -	uint32_t hash __rte_unused, uint32_t desired_hash __rte_unused)
> +rte_thash_get_compliment(struct rte_thash_subtuple_helper *h,
> +	uint32_t hash, uint32_t desired_hash)
>  {
> -	return 0;
> +	return h->compl_table[(hash ^ desired_hash) & h->lsb_msk];
>  }
> 
>  const uint8_t *
> -rte_thash_get_key(struct rte_thash_ctx *ctx __rte_unused)
> +rte_thash_get_key(struct rte_thash_ctx *ctx)
>  {
> -	return NULL;
> +	return ctx->hash_key;
> +}
> +
> +static inline void
> +xor_bit(uint8_t *ptr, uint32_t bit, uint32_t pos) {
> +	uint32_t byte_idx = pos >> 3;
> +	uint32_t bit_idx = (CHAR_BIT - 1) - (pos & (CHAR_BIT - 1));
> +	uint8_t tmp;
> +
> +	tmp = ptr[byte_idx];
> +	tmp ^= bit << bit_idx;
> +	ptr[byte_idx] = tmp;
> +}
> +
> +int
> +rte_thash_adjust_tuple(struct rte_thash_subtuple_helper *h,
> +	uint8_t *orig_tuple, uint32_t adj_bits,
> +	rte_thash_check_tuple_t fn, void *userdata) {
> +	unsigned i;
> +
> +	if ((h == NULL) || (orig_tuple == NULL))
> +		return -EINVAL;
> +
> +	adj_bits &= h->lsb_msk;
> +	/* Hint: LSB of adj_bits corresponds to offset + len bit of tuple */
> +	for (i = 0; i < sizeof(uint32_t) * CHAR_BIT; i++) {
> +		uint8_t bit = (adj_bits >> i) & 0x1;
> +		if (bit)
> +			xor_bit(orig_tuple, bit,
> +				h->tuple_offset + h->tuple_len - 1 - i);
> +	}
> +
> +	if (fn != NULL)
> +		return (fn(userdata, orig_tuple)) ? 0 : -EEXIST;
> +
> +	return 0;
>  }
> diff --git a/lib/librte_hash/rte_thash.h b/lib/librte_hash/rte_thash.h index
> 38a641b..fd67931 100644
> --- a/lib/librte_hash/rte_thash.h
> +++ b/lib/librte_hash/rte_thash.h
> @@ -360,6 +360,48 @@ __rte_experimental
>  const uint8_t *
>  rte_thash_get_key(struct rte_thash_ctx *ctx);
> 
> +/**
> + * Function prototype for the rte_thash_adjust_tuple
> + * to check if adjusted tuple could be used.
> + * Generally it is some kind of lookup function to check
> + * if adjusted tuple is already in use.
> + *
> + * @param userdata
> + *  Pointer to the userdata. It could be a pointer to the
> + *  table with used tuples to search.
> + * @param tuple
> + *  Pointer to the tuple to check
> + *
> + * @return
> + *  1 on success
> + *  0 otherwise
> + */
> +typedef int (*rte_thash_check_tuple_t)(void *userdata, uint8_t *tuple);
> +
> +/**
> + * Adjust tuple with complimentary bits.
> + *
[Wang, Yipeng] 
More explanation for this API is needed.
My understanding is that user should call this function in a loop, until
the above callback function returns success thus this function succeeds.
BTW, why not put this API in the first API commit?

> + * @param h
> + *  Pointer to the helper struct
> + * @param orig_tuple
> + *  Pointer to the tuple to be adjusted
> + * @param adj_bits
> + *  Valure returned by rte_thash_get_compliment
[Wang, Yipeng] typo. *value
> + * @param fn
> + *  Callback function to check adjusted tuple. Could be NULL
> + * @param userdata
> + *  Pointer to the userdata to be passed to fn(). Could be NULL
> + *
> + * @return
> + *  0 on success
> + *  negative otherwise
> + */
> +__rte_experimental
> +int
> +rte_thash_adjust_tuple(struct rte_thash_subtuple_helper *h,
> +	uint8_t *orig_tuple, uint32_t adj_bits,
> +	rte_thash_check_tuple_t fn, void *userdata);
> +
>  #ifdef __cplusplus
>  }
>  #endif
> diff --git a/lib/librte_hash/version.map b/lib/librte_hash/version.map index
> 93cb230..a992a1e 100644
> --- a/lib/librte_hash/version.map
> +++ b/lib/librte_hash/version.map
> @@ -32,6 +32,7 @@ DPDK_21 {
>  EXPERIMENTAL {
>  	global:
> 
> +	rte_thash_adjust_tuple;
>  	rte_hash_free_key_with_position;
>  	rte_hash_lookup_with_hash_bulk;
>  	rte_hash_lookup_with_hash_bulk_data;
> --
> 2.7.4
diff mbox series

Patch

diff --git a/lib/librte_hash/rte_thash.c b/lib/librte_hash/rte_thash.c
index 79e8724..cc60ada 100644
--- a/lib/librte_hash/rte_thash.c
+++ b/lib/librte_hash/rte_thash.c
@@ -12,6 +12,45 @@ 
 #include <rte_malloc.h>
 
 #define THASH_NAME_LEN		64
+#define TOEPLITZ_HASH_LEN	32
+
+#define	RETA_SZ_MIN	2U
+#define	RETA_SZ_MAX	16U
+#define RETA_SZ_IN_RANGE(reta_sz)	((reta_sz >= RETA_SZ_MIN) && \
+					(reta_sz <= RETA_SZ_MAX))
+
+TAILQ_HEAD(rte_thash_list, rte_tailq_entry);
+static struct rte_tailq_elem rte_thash_tailq = {
+	.name = "RTE_THASH",
+};
+EAL_REGISTER_TAILQ(rte_thash_tailq)
+
+/**
+ * Table of some irreducible polinomials over GF(2).
+ * For lfsr they are reperesented in BE bit order, and
+ * x^0 is masked out.
+ * For example, poly x^5 + x^2 + 1 will be represented
+ * as (101001b & 11111b) = 01001b = 0x9
+ */
+static const uint32_t irreducible_poly_table[][4] = {
+	{0, 0, 0, 0},	/** < degree 0 */
+	{1, 1, 1, 1},	/** < degree 1 */
+	{0x3, 0x3, 0x3, 0x3},	/** < degree 2 and so on... */
+	{0x5, 0x3, 0x5, 0x3},
+	{0x9, 0x3, 0x9, 0x3},
+	{0x9, 0x1b, 0xf, 0x5},
+	{0x21, 0x33, 0x1b, 0x2d},
+	{0x41, 0x11, 0x71, 0x9},
+	{0x71, 0xa9, 0xf5, 0x8d},
+	{0x21, 0xd1, 0x69, 0x1d9},
+	{0x81, 0x2c1, 0x3b1, 0x185},
+	{0x201, 0x541, 0x341, 0x461},
+	{0x941, 0x609, 0xe19, 0x45d},
+	{0x1601, 0x1f51, 0x1171, 0x359},
+	{0x2141, 0x2111, 0x2db1, 0x2109},
+	{0x4001, 0x801, 0x101, 0x7301},
+	{0x7781, 0xa011, 0x4211, 0x86d9},
+};
 
 struct thash_lfsr {
 	uint32_t	ref_cnt;
@@ -31,8 +70,10 @@  struct rte_thash_subtuple_helper {
 	char	name[THASH_NAME_LEN];	/** < Name of subtuple configuration */
 	LIST_ENTRY(rte_thash_subtuple_helper)	next;
 	struct thash_lfsr	*lfsr;
-	uint32_t	offset;		/** < Offset in bits of the subtuple */
-	uint32_t	len;		/** < Length in bits of the subtuple */
+	uint32_t	offset;		/** < Offset of the m-sequence */
+	uint32_t	len;		/** < Length of the m-sequence */
+	uint32_t	tuple_offset;	/** < Offset in bits of the subtuple */
+	uint32_t	tuple_len;	/** < Length in bits of the subtuple */
 	uint32_t	lsb_msk;	/** < (1 << reta_sz_log) - 1 */
 	__extension__ uint32_t	compl_table[0] __rte_cache_aligned;
 	/** < Complimentary table */
@@ -48,49 +89,549 @@  struct rte_thash_ctx {
 	uint8_t		hash_key[0];
 };
 
+static inline uint32_t
+get_bit_lfsr(struct thash_lfsr *lfsr)
+{
+	uint32_t bit, ret;
+
+	/*
+	 * masking the TAP bits defined by the polynomial and
+	 * calculating parity
+	 */
+	bit = __builtin_popcount(lfsr->state & lfsr->poly) & 0x1;
+	ret = lfsr->state & 0x1;
+	lfsr->state = ((lfsr->state >> 1) | (bit << (lfsr->deg - 1))) &
+		((1 << lfsr->deg) - 1);
+
+	lfsr->bits_cnt++;
+	return ret;
+}
+
+static inline uint32_t
+get_rev_bit_lfsr(struct thash_lfsr *lfsr)
+{
+	uint32_t bit, ret;
+
+	bit = __builtin_popcount(lfsr->rev_state & lfsr->rev_poly) & 0x1;
+	ret = lfsr->rev_state & (1 << (lfsr->deg - 1));
+	lfsr->rev_state = ((lfsr->rev_state << 1) | bit) &
+		((1 << lfsr->deg) - 1);
+
+	lfsr->bits_cnt++;
+	return ret;
+}
+
+static inline uint32_t
+thash_get_rand_poly(uint32_t poly_degree)
+{
+	return irreducible_poly_table[poly_degree][rte_rand() %
+		RTE_DIM(irreducible_poly_table[poly_degree])];
+}
+
+static struct thash_lfsr *
+alloc_lfsr(struct rte_thash_ctx *ctx)
+{
+	struct thash_lfsr *lfsr;
+	uint32_t i;
+
+	if (ctx == NULL)
+		return NULL;
+
+	lfsr = rte_zmalloc(NULL, sizeof(struct thash_lfsr), 0);
+	if (lfsr == NULL)
+		return NULL;
+
+	lfsr->deg = ctx->reta_sz_log;
+	lfsr->poly = thash_get_rand_poly(lfsr->deg);
+	do {
+		lfsr->state = rte_rand() & ((1 << lfsr->deg) - 1);
+	} while (lfsr->state == 0);
+	/* init reverse order polynomial */
+	lfsr->rev_poly = (lfsr->poly >> 1) | (1 << (lfsr->deg - 1));
+	/* init proper rev_state*/
+	lfsr->rev_state = lfsr->state;
+	for (i = 0; i <= lfsr->deg; i++)
+		get_rev_bit_lfsr(lfsr);
+
+	/* clear bits_cnt after rev_state was inited */
+	lfsr->bits_cnt = 0;
+	lfsr->ref_cnt = 1;
+
+	return lfsr;
+}
+
+static void
+attach_lfsr(struct rte_thash_subtuple_helper *h, struct thash_lfsr *lfsr)
+{
+	lfsr->ref_cnt++;
+	h->lfsr = lfsr;
+}
+
+static void
+free_lfsr(struct thash_lfsr *lfsr)
+{
+	lfsr->ref_cnt--;
+	if (lfsr->ref_cnt == 0)
+		rte_free(lfsr);
+}
+
 struct rte_thash_ctx *
-rte_thash_init_ctx(const char *name __rte_unused,
-	uint32_t key_len __rte_unused, uint32_t reta_sz __rte_unused,
-	uint8_t *key __rte_unused, uint32_t flags __rte_unused)
+rte_thash_init_ctx(const char *name, uint32_t key_len, uint32_t reta_sz,
+	uint8_t *key, uint32_t flags)
 {
+	struct rte_thash_ctx *ctx;
+	struct rte_tailq_entry *te;
+	struct rte_thash_list *thash_list;
+	uint32_t i;
+	if ((name == NULL) || (key_len == 0) || !RETA_SZ_IN_RANGE(reta_sz)) {
+		rte_errno = EINVAL;
+		return NULL;
+	}
+
+	thash_list = RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list);
+
+	rte_mcfg_tailq_write_lock();
+
+	/* guarantee there's no existing */
+	TAILQ_FOREACH(te, thash_list, next) {
+		ctx = (struct rte_thash_ctx *)te->data;
+		if (strncmp(name, ctx->name, sizeof(ctx->name)) == 0)
+			break;
+	}
+	ctx = NULL;
+	if (te != NULL) {
+		rte_errno = EEXIST;
+		goto exit;
+	}
+
+	/* allocate tailq entry */
+	te = rte_zmalloc("THASH_TAILQ_ENTRY", sizeof(*te), 0);
+	if (te == NULL) {
+		RTE_LOG(ERR, HASH,
+			"Can not allocate tailq entry for thash context %s\n",
+			name);
+		rte_errno = ENOMEM;
+		goto exit;
+	}
+
+	ctx = rte_zmalloc(NULL, sizeof(struct rte_thash_ctx) + key_len, 0);
+	if (ctx == NULL) {
+		RTE_LOG(ERR, HASH, "thash ctx %s memory allocation failed\n",
+			name);
+		rte_errno = ENOMEM;
+		goto free_te;
+	}
+
+	rte_strlcpy(ctx->name, name, sizeof(ctx->name));
+	ctx->key_len = key_len;
+	ctx->reta_sz_log = reta_sz;
+	LIST_INIT(&ctx->head);
+	ctx->flags = flags;
+
+	if (key)
+		rte_memcpy(ctx->hash_key, key, key_len);
+	else {
+		for (i = 0; i < key_len; i++)
+			ctx->hash_key[i] = rte_rand();
+	}
+
+	te->data = (void *)ctx;
+	TAILQ_INSERT_TAIL(thash_list, te, next);
+
+	rte_mcfg_tailq_write_unlock();
+
+	return ctx;
+free_te:
+	rte_free(te);
+exit:
+	rte_mcfg_tailq_write_unlock();
 	return NULL;
 }
 
 struct rte_thash_ctx *
-rte_thash_find_existing(const char *name __rte_unused)
+rte_thash_find_existing(const char *name)
 {
-	return NULL;
+	struct rte_thash_ctx *ctx;
+	struct rte_tailq_entry *te;
+	struct rte_thash_list *thash_list;
+
+	thash_list = RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list);
+
+	rte_mcfg_tailq_read_lock();
+	TAILQ_FOREACH(te, thash_list, next) {
+		ctx = (struct rte_thash_ctx *)te->data;
+		if (strncmp(name, ctx->name, sizeof(ctx->name)) == 0)
+			break;
+	}
+
+	rte_mcfg_tailq_read_unlock();
+
+	if (te == NULL) {
+		rte_errno = ENOENT;
+		return NULL;
+	}
+
+	return ctx;
 }
 
 void
-rte_thash_free_ctx(struct rte_thash_ctx *ctx __rte_unused)
+rte_thash_free_ctx(struct rte_thash_ctx *ctx)
 {
+	struct rte_tailq_entry *te;
+	struct rte_thash_list *thash_list;
+	struct rte_thash_subtuple_helper *ent, *tmp;
+
+	if (ctx == NULL)
+		return;
+
+	thash_list = RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list);
+	rte_mcfg_tailq_write_lock();
+	TAILQ_FOREACH(te, thash_list, next) {
+		if (te->data == (void *)ctx)
+			break;
+	}
+
+	if (te != NULL)
+		TAILQ_REMOVE(thash_list, te, next);
+
+	rte_mcfg_tailq_write_unlock();
+	ent = LIST_FIRST(&(ctx->head));
+	while (ent) {
+		free_lfsr(ent->lfsr);
+		tmp = ent;
+		ent = LIST_NEXT(ent, next);
+		LIST_REMOVE(tmp, next);
+		rte_free(tmp);
+	}
+
+	rte_free(ctx);
+	rte_free(te);
+}
+
+static inline void
+set_bit(uint8_t *ptr, uint32_t bit, uint32_t pos)
+{
+	uint32_t byte_idx = pos >> 3;
+	uint32_t bit_idx = (CHAR_BIT - 1) - (pos & (CHAR_BIT - 1));
+	uint8_t tmp;
+
+	tmp = ptr[byte_idx];
+	tmp &= ~(1 << bit_idx);
+	tmp |= bit << bit_idx;
+	ptr[byte_idx] = tmp;
+}
+
+/**
+ * writes m-sequence to the hash_key for range [start, end]
+ * (i.e. including start and end positions)
+ */
+static int
+generate_subkey(struct rte_thash_ctx *ctx, struct thash_lfsr *lfsr,
+	uint32_t start, uint32_t end)
+{
+	uint32_t i;
+	uint32_t req_bits = (start < end) ? (end - start) : (start - end);
+	req_bits++; /* due to incuding end */
+
+	/* check if lfsr overflow period of the m-sequence */
+	if (((lfsr->bits_cnt + req_bits) > (1ULL << lfsr->deg) - 1) &&
+			((ctx->flags & RTE_THASH_IGNORE_PERIOD_OVERFLOW) !=
+			RTE_THASH_IGNORE_PERIOD_OVERFLOW))
+		return -ENOSPC;
+
+	if (start < end) {
+		/* original direction (from left to right)*/
+		for (i = start; i <= end; i++)
+			set_bit(ctx->hash_key, get_bit_lfsr(lfsr), i);
+
+	} else {
+		/* reverse direction (from right to left) */
+		for (i = end; i >= start; i--)
+			set_bit(ctx->hash_key, get_rev_bit_lfsr(lfsr), i);
+	}
+
+	return 0;
+}
+
+static inline uint32_t
+get_subvalue(struct rte_thash_ctx *ctx, uint32_t offset)
+{
+	uint32_t *tmp, val;
+
+	tmp = (uint32_t *)(&ctx->hash_key[offset >> 3]);
+	val = rte_be_to_cpu_32(*tmp);
+	val >>= (TOEPLITZ_HASH_LEN - ((offset & (CHAR_BIT - 1)) +
+		ctx->reta_sz_log));
+
+	return val & ((1 << ctx->reta_sz_log) - 1);
+}
+
+static inline void
+generate_compliment_table(struct rte_thash_ctx *ctx,
+	struct rte_thash_subtuple_helper *h)
+{
+	int i, j, k;
+	uint32_t val;
+	uint32_t start;
+
+	start = h->offset + h->len - (2 * ctx->reta_sz_log - 1);
+
+	for (i = 1; i < (1 << ctx->reta_sz_log); i++) {
+		val = 0;
+		for (j = i; j; j &= (j - 1)) {
+			k = rte_bsf32(j);
+			val ^= get_subvalue(ctx, start - k +
+				ctx->reta_sz_log - 1);
+		}
+		h->compl_table[val] = i;
+	}
+}
+
+static inline int
+insert_before(struct rte_thash_ctx *ctx,
+	struct rte_thash_subtuple_helper *ent,
+	struct rte_thash_subtuple_helper *cur_ent,
+	struct rte_thash_subtuple_helper *next_ent,
+	uint32_t start, uint32_t end, uint32_t range_end)
+{
+	int ret;
+
+	if (end < cur_ent->offset) {
+		ent->lfsr = alloc_lfsr(ctx);
+		if (ent->lfsr == NULL) {
+			rte_free(ent);
+			return -ENOMEM;
+		}
+		/* generate nonoverlapping range [start, end) */
+		ret = generate_subkey(ctx, ent->lfsr, start, end - 1);
+		if (ret != 0) {
+			free_lfsr(ent->lfsr);
+			rte_free(ent);
+			return ret;
+		}
+	} else if ((next_ent != NULL) && (end > next_ent->offset)) {
+		rte_free(ent);
+		return -ENOSPC;
+	}
+	attach_lfsr(ent, cur_ent->lfsr);
+
+	/**
+	 * generate partially overlapping range
+	 * [start, cur_ent->start) in reverse order
+	 */
+	ret = generate_subkey(ctx, ent->lfsr, cur_ent->offset - 1, start);
+	if (ret != 0) {
+		free_lfsr(ent->lfsr);
+		rte_free(ent);
+		return ret;
+	}
+
+	if (end > range_end) {
+		/**
+		 * generate partially overlapping range
+		 * (range_end, end)
+		 */
+		ret = generate_subkey(ctx, ent->lfsr, range_end, end - 1);
+		if (ret != 0) {
+			free_lfsr(ent->lfsr);
+			rte_free(ent);
+			return ret;
+		}
+	}
+
+	LIST_INSERT_BEFORE(cur_ent, ent, next);
+	generate_compliment_table(ctx, ent);
+	ctx->subtuples_nb++;
+	return 0;
+}
+
+static inline int
+insert_after(struct rte_thash_ctx *ctx,
+	struct rte_thash_subtuple_helper *ent,
+	struct rte_thash_subtuple_helper *cur_ent,
+	struct rte_thash_subtuple_helper *next_ent,
+	struct rte_thash_subtuple_helper *prev_ent,
+	uint32_t end, uint32_t range_end)
+{
+	int ret;
+
+	if ((next_ent != NULL) && (end > next_ent->offset)) {
+		rte_free(ent);
+		return -EEXIST;
+	}
+
+	attach_lfsr(ent, cur_ent->lfsr);
+	if (end > range_end) {
+		/**
+		 * generate partially overlapping range
+		 * (range_end, end)
+		 */
+		ret = generate_subkey(ctx, ent->lfsr, range_end, end - 1);
+		if (ret != 0) {
+			free_lfsr(ent->lfsr);
+			rte_free(ent);
+			return ret;
+		}
+	}
+
+	LIST_INSERT_AFTER(prev_ent, ent, next);
+	generate_compliment_table(ctx, ent);
+	ctx->subtuples_nb++;
+
+	return 0;
 }
 
 int
-rte_thash_add_helper(struct rte_thash_ctx *ctx __rte_unused,
-	const char *name __rte_unused, uint32_t len __rte_unused,
-	uint32_t offset __rte_unused)
+rte_thash_add_helper(struct rte_thash_ctx *ctx, const char *name, uint32_t len,
+	uint32_t offset)
 {
+	struct rte_thash_subtuple_helper *ent, *cur_ent, *prev_ent, *next_ent;
+	uint32_t start, end;
+	int ret;
+
+	if ((ctx == NULL) || (name == NULL) || (len < ctx->reta_sz_log) ||
+			((offset + len + TOEPLITZ_HASH_LEN - 1) >
+			ctx->key_len * CHAR_BIT))
+		return -EINVAL;
+
+	/* Check for existing name*/
+	LIST_FOREACH(cur_ent, &ctx->head, next) {
+		if (strncmp(name, cur_ent->name, sizeof(cur_ent->name)) == 0)
+			return -EEXIST;
+	}
+
+	end = offset + len + TOEPLITZ_HASH_LEN - 1;
+	start = ((ctx->flags & RTE_THASH_MINIMAL_SEQ) ==
+		RTE_THASH_MINIMAL_SEQ) ? (end - (2 * ctx->reta_sz_log - 1)) :
+		offset;
+
+	ent = rte_zmalloc(NULL, sizeof(struct rte_thash_subtuple_helper) +
+		sizeof(uint32_t) * (1 << ctx->reta_sz_log), 0);
+	if (ent == NULL)
+		return -ENOMEM;
+
+	rte_strlcpy(ent->name, name, sizeof(ent->name));
+	ent->offset = start;
+	ent->len = end - start;
+	ent->tuple_offset = offset;
+	ent->tuple_len = len;
+	ent->lsb_msk = (1 << ctx->reta_sz_log) - 1;
+
+	cur_ent = LIST_FIRST(&ctx->head);
+	while (cur_ent) {
+		uint32_t range_end = cur_ent->offset + cur_ent->len;
+		next_ent = LIST_NEXT(cur_ent, next);
+		prev_ent = cur_ent;
+		/* Iterate through overlapping ranges */
+		while ((next_ent != NULL) && (next_ent->offset < range_end)) {
+			range_end = RTE_MAX(next_ent->offset + next_ent->len,
+				range_end);
+			if (start > next_ent->offset)
+				prev_ent = next_ent;
+
+			next_ent = LIST_NEXT(next_ent, next);
+		}
+
+		if (start < cur_ent->offset)
+			return insert_before(ctx, ent, cur_ent, next_ent,
+				start, end, range_end);
+		else if (start < range_end)
+			return insert_after(ctx, ent, cur_ent, next_ent,
+				prev_ent, end, range_end);
+
+		cur_ent = next_ent;
+		continue;
+	}
+
+	ent->lfsr = alloc_lfsr(ctx);
+	if (ent->lfsr == NULL) {
+		rte_free(ent);
+		return -ENOMEM;
+	}
+
+	/* generate nonoverlapping range [start, end) */
+	ret = generate_subkey(ctx, ent->lfsr, start, end - 1);
+	if (ret != 0) {
+		free_lfsr(ent->lfsr);
+		rte_free(ent);
+		return ret;
+	}
+	if (LIST_EMPTY(&ctx->head)) {
+		LIST_INSERT_HEAD(&ctx->head, ent, next);
+	} else {
+		LIST_FOREACH(next_ent, &ctx->head, next)
+			prev_ent = next_ent;
+
+		LIST_INSERT_AFTER(prev_ent, ent, next);
+	}
+	generate_compliment_table(ctx, ent);
+	ctx->subtuples_nb++;
+
 	return 0;
 }
 
 struct rte_thash_subtuple_helper *
-rte_thash_get_helper(struct rte_thash_ctx *ctx __rte_unused,
-	const char *name __rte_unused)
+rte_thash_get_helper(struct rte_thash_ctx *ctx, const char *name)
 {
+	struct rte_thash_subtuple_helper *ent;
+
+	if ((ctx == NULL) || (name == NULL))
+		return NULL;
+
+	LIST_FOREACH(ent, &ctx->head, next) {
+		if (strncmp(name, ent->name, sizeof(ent->name)) == 0)
+			return ent;
+	}
+
 	return NULL;
 }
 
 uint32_t
-rte_thash_get_compliment(struct rte_thash_subtuple_helper *h __rte_unused,
-	uint32_t hash __rte_unused, uint32_t desired_hash __rte_unused)
+rte_thash_get_compliment(struct rte_thash_subtuple_helper *h,
+	uint32_t hash, uint32_t desired_hash)
 {
-	return 0;
+	return h->compl_table[(hash ^ desired_hash) & h->lsb_msk];
 }
 
 const uint8_t *
-rte_thash_get_key(struct rte_thash_ctx *ctx __rte_unused)
+rte_thash_get_key(struct rte_thash_ctx *ctx)
 {
-	return NULL;
+	return ctx->hash_key;
+}
+
+static inline void
+xor_bit(uint8_t *ptr, uint32_t bit, uint32_t pos)
+{
+	uint32_t byte_idx = pos >> 3;
+	uint32_t bit_idx = (CHAR_BIT - 1) - (pos & (CHAR_BIT - 1));
+	uint8_t tmp;
+
+	tmp = ptr[byte_idx];
+	tmp ^= bit << bit_idx;
+	ptr[byte_idx] = tmp;
+}
+
+int
+rte_thash_adjust_tuple(struct rte_thash_subtuple_helper *h,
+	uint8_t *orig_tuple, uint32_t adj_bits,
+	rte_thash_check_tuple_t fn, void *userdata)
+{
+	unsigned i;
+
+	if ((h == NULL) || (orig_tuple == NULL))
+		return -EINVAL;
+
+	adj_bits &= h->lsb_msk;
+	/* Hint: LSB of adj_bits corresponds to offset + len bit of tuple */
+	for (i = 0; i < sizeof(uint32_t) * CHAR_BIT; i++) {
+		uint8_t bit = (adj_bits >> i) & 0x1;
+		if (bit)
+			xor_bit(orig_tuple, bit,
+				h->tuple_offset + h->tuple_len - 1 - i);
+	}
+
+	if (fn != NULL)
+		return (fn(userdata, orig_tuple)) ? 0 : -EEXIST;
+
+	return 0;
 }
diff --git a/lib/librte_hash/rte_thash.h b/lib/librte_hash/rte_thash.h
index 38a641b..fd67931 100644
--- a/lib/librte_hash/rte_thash.h
+++ b/lib/librte_hash/rte_thash.h
@@ -360,6 +360,48 @@  __rte_experimental
 const uint8_t *
 rte_thash_get_key(struct rte_thash_ctx *ctx);
 
+/**
+ * Function prototype for the rte_thash_adjust_tuple
+ * to check if adjusted tuple could be used.
+ * Generally it is some kind of lookup function to check
+ * if adjusted tuple is already in use.
+ *
+ * @param userdata
+ *  Pointer to the userdata. It could be a pointer to the
+ *  table with used tuples to search.
+ * @param tuple
+ *  Pointer to the tuple to check
+ *
+ * @return
+ *  1 on success
+ *  0 otherwise
+ */
+typedef int (*rte_thash_check_tuple_t)(void *userdata, uint8_t *tuple);
+
+/**
+ * Adjust tuple with complimentary bits.
+ *
+ * @param h
+ *  Pointer to the helper struct
+ * @param orig_tuple
+ *  Pointer to the tuple to be adjusted
+ * @param adj_bits
+ *  Valure returned by rte_thash_get_compliment
+ * @param fn
+ *  Callback function to check adjusted tuple. Could be NULL
+ * @param userdata
+ *  Pointer to the userdata to be passed to fn(). Could be NULL
+ *
+ * @return
+ *  0 on success
+ *  negative otherwise
+ */
+__rte_experimental
+int
+rte_thash_adjust_tuple(struct rte_thash_subtuple_helper *h,
+	uint8_t *orig_tuple, uint32_t adj_bits,
+	rte_thash_check_tuple_t fn, void *userdata);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/librte_hash/version.map b/lib/librte_hash/version.map
index 93cb230..a992a1e 100644
--- a/lib/librte_hash/version.map
+++ b/lib/librte_hash/version.map
@@ -32,6 +32,7 @@  DPDK_21 {
 EXPERIMENTAL {
 	global:
 
+	rte_thash_adjust_tuple;
 	rte_hash_free_key_with_position;
 	rte_hash_lookup_with_hash_bulk;
 	rte_hash_lookup_with_hash_bulk_data;