Hi Vladimir,
I didn't look at actual implementation (yet), just some
compatibility comments.
> K32V64 hash is a hash table that supports 32 bit keys and 64 bit values.
> This table is hash function agnostic so user must provide
> precalculated hash signature for add/delete/lookup operations.
>
> Signed-off-by: Vladimir Medvedkin <vladimir.medved...@intel.com>
> ---
> diff --git a/lib/librte_hash/rte_k32v64_hash.h
> b/lib/librte_hash/rte_k32v64_hash.h
> new file mode 100644
> index 0000000..d25660c
> --- /dev/null
> +++ b/lib/librte_hash/rte_k32v64_hash.h
> @@ -0,0 +1,214 @@
> +/* SPDX-License-Identifier: BSD-3-Clause
> + * Copyright(c) 2020 Intel Corporation
> + */
> +
> +#ifndef _RTE_K32V64_HASH_H_
> +#define _RTE_K32V64_HASH_H_
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +#include <rte_compat.h>
> +#include <rte_atomic.h>
> +#include <rte_mempool.h>
> +
> +#include <immintrin.h>
How that supposed to compile on non-X86 box?
> +
> +#define RTE_K32V64_HASH_NAMESIZE 32
> +#define RTE_K32V64_KEYS_PER_BUCKET 4
> +#define RTE_K32V64_WRITE_IN_PROGRESS 1
> +
> +struct rte_k32v64_hash_params {
> + const char *name;
> + uint32_t entries;
> + int socket_id;
> +};
> +
> +struct rte_k32v64_ext_ent {
> + SLIST_ENTRY(rte_k32v64_ext_ent) next;
> + uint32_t key;
> + uint64_t val;
> +};
> +
> +struct rte_k32v64_hash_bucket {
> + uint32_t key[RTE_K32V64_KEYS_PER_BUCKET];
> + uint64_t val[RTE_K32V64_KEYS_PER_BUCKET];
> + uint8_t key_mask;
> + rte_atomic32_t cnt;
> + SLIST_HEAD(rte_k32v64_list_head, rte_k32v64_ext_ent) head;
> +} __rte_cache_aligned;
> +
> +struct rte_k32v64_hash_table {
> + char name[RTE_K32V64_HASH_NAMESIZE]; /**< Name of the hash. */
> + uint32_t nb_ent;
> + uint32_t nb_ext_ent;
> + uint32_t max_ent;
> + uint32_t bucket_msk;
> + struct rte_mempool *ext_ent_pool;
> + __extension__ struct rte_k32v64_hash_bucket t[0];
> +};
> +
> +static inline int
> +cmp_keys(struct rte_k32v64_hash_bucket *bucket, uint32_t key,
> + uint64_t *val)
> +{
> + int i;
> +
> + for (i = 0; i < RTE_K32V64_KEYS_PER_BUCKET; i++) {
> + if ((key == bucket->key[i]) &&
> + (bucket->key_mask & (1 << i))) {
> + *val = bucket->val[i];
> + return 1;
> + }
> + }
> +
> + return 0;
> +}
> +
> +#ifdef __AVX512VL__
> +static inline int
> +cmp_keys_vec(struct rte_k32v64_hash_bucket *bucket, uint32_t key,
> + uint64_t *val)
> +{
> + __m128i keys, srch_key;
> + __mmask8 msk;
> +
> + keys = _mm_load_si128((void *)bucket);
> + srch_key = _mm_set1_epi32(key);
> +
> + msk = _mm_mask_cmpeq_epi32_mask(bucket->key_mask, keys, srch_key);
What if you'll run it on IA cpu without avx512 support?
Think you need there some run-time selection to decide which function to use,
depending on the underlying HW.
> + if (msk) {
> + *val = bucket->val[__builtin_ctz(msk)];
> + return 1;
> + }
> +
> + return 0;
> +}
> +#endif
> +
> +static inline int
> +rte_k32v64_hash_lookup(struct rte_k32v64_hash_table *table, uint32_t key,
> + uint32_t hash, uint64_t *value)
> +{
> + uint64_t val = 0;
> + struct rte_k32v64_ext_ent *ent;
> + int32_t cnt;
> + int i __rte_unused, found = 0;
> + uint32_t bucket = hash & table->bucket_msk;
> +
> + do {
> + do
> + cnt = rte_atomic32_read(&table->t[bucket].cnt);
> + while (unlikely(cnt & RTE_K32V64_WRITE_IN_PROGRESS));
> +
> +#ifdef __AVX512VL__
> + found = cmp_keys_vec(&table->t[bucket], key, &val);
> +#else
> + found = cmp_keys(&table->t[bucket], key, &val);
> +#endif
> + if (unlikely((found == 0) &&
> + (!SLIST_EMPTY(&table->t[bucket].head)))) {
> + SLIST_FOREACH(ent, &table->t[bucket].head, next) {
> + if (ent->key == key) {
> + val = ent->val;
> + found = 1;
> + break;
> + }
> + }
> + }
> +
> + } while (unlikely(cnt != rte_atomic32_read(&table->t[bucket].cnt)));
> +
> + if (found == 1) {
> + *value = val;
> + return 0;
> + } else
> + return -ENOENT;
> +}
> +
> +/**
> + * Add a key to an existing hash table with hash value.
> + * This operation is not multi-thread safe
> + * and should only be called from one thread.
> + *
> + * @param ht
> + * Hash table to add the key to.
> + * @param key
> + * Key to add to the hash table.
> + * @param value
> + * Value to associate with key.
> + * @param hash
> + * Hash value associated with key.
> + * @return
> + * 0 if ok, or negative value on error.
> + */
> +__rte_experimental
> +int
> +rte_k32v64_hash_add(struct rte_k32v64_hash_table *table, uint32_t key,
> + uint32_t hash, uint64_t value);
> +
> +/**
> + * Remove a key with a given hash value from an existing hash table.
> + * This operation is not multi-thread
> + * safe and should only be called from one thread.
> + *
> + * @param ht
> + * Hash table to remove the key from.
> + * @param key
> + * Key to remove from the hash table.
> + * @param hash
> + * hash value associated with key.
> + * @return
> + * 0 if ok, or negative value on error.
> + */
> +__rte_experimental
> +int
> +rte_k32v64_hash_delete(struct rte_k32v64_hash_table *table, uint32_t key,
> + uint32_t hash);
> +
> +
> +/**
> + * Performs a lookup for an existing hash table, and returns a pointer to
> + * the table if found.
> + *
> + * @param name
> + * Name of the hash table to find
> + *
> + * @return
> + * pointer to hash table structure or NULL on error with rte_errno
> + * set appropriately.
> + */
> +__rte_experimental
> +struct rte_k32v64_hash_table *
> +rte_k32v64_hash_find_existing(const char *name);
> +
> +/**
> + * Create a new hash table for use with four byte keys.
> + *
> + * @param params
> + * Parameters used in creation of hash table.
> + *
> + * @return
> + * Pointer to hash table structure that is used in future hash table
> + * operations, or NULL on error with rte_errno set appropriately.
> + */
> +__rte_experimental
> +struct rte_k32v64_hash_table *
> +rte_k32v64_hash_create(const struct rte_k32v64_hash_params *params);
> +
> +/**
> + * Free all memory used by a hash table.
> + *
> + * @param table
> + * Hash table to deallocate.
> + */
> +__rte_experimental
> +void
> +rte_k32v64_hash_free(struct rte_k32v64_hash_table *table);
> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif /* _RTE_K32V64_HASH_H_ */
> --
> 2.7.4
