Re: [dpdk-dev] [PATCH v4 1/4] hash: add kv hash library

[Medvedkin, Vladimir]

Hi Konstantin,

Thanks for the review. See below


On 23/06/2020 16:44, Ananyev, Konstantin wrote:

Hi Vladimir,

--- /dev/null
+++ b/lib/librte_hash/k32v64_hash.c
@@ -0,0 +1,277 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2020 Intel Corporation
+ */
+
+#include <string.h>
+
+#include <rte_errno.h>
+#include <rte_malloc.h>
+#include <rte_memory.h>
+
+#include "k32v64_hash.h"
+
+static inline int
+k32v64_hash_lookup(struct k32v64_hash_table *table, uint32_t key,
+uint32_t hash, uint64_t *value)
+{
+return __k32v64_hash_lookup(table, key, hash, value, __kv_cmp_keys);
+}
+
+static int
+k32v64_hash_bulk_lookup(struct rte_kv_hash_table *ht, void *keys_p,
+uint32_t *hashes, void *values_p, unsigned int n)
+{
+struct k32v64_hash_table *table = (struct k32v64_hash_table *)ht;
+uint32_t *keys = keys_p;
+uint64_t *values = values_p;
+int ret, cnt = 0;
+unsigned int i;
+
+if (unlikely((table == NULL) || (keys == NULL) || (hashes == NULL) ||
+(values == NULL)))
+return -EINVAL;
+
+for (i = 0; i < n; i++) {
+ret = k32v64_hash_lookup(table, keys[i], hashes[i],
+&values[i]);
+if (ret == 0)
+cnt++;
+}
+return cnt;
+}
+
+#ifdef CC_AVX512VL_SUPPORT
+int
+k32v64_hash_bulk_lookup_avx512vl(struct rte_kv_hash_table *ht,
+void *keys_p, uint32_t *hashes, void *values_p, unsigned int n);
+#endif
+
+static rte_kv_hash_bulk_lookup_t
+get_lookup_bulk_fn(void)
+{
+#ifdef CC_AVX512VL_SUPPORT
+if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512VL))
+return k32v64_hash_bulk_lookup_avx512vl;
+#endif
+return k32v64_hash_bulk_lookup;
+}
+
+static int
+k32v64_hash_add(struct k32v64_hash_table *table, uint32_t key,
+uint32_t hash, uint64_t value, uint64_t *old_value, int *found)
+{
+uint32_t bucket;
+int i, idx, ret;
+uint8_t msk;
+struct k32v64_ext_ent *tmp, *ent, *prev = NULL;
+
+if (table == NULL)
+return -EINVAL;
+
+bucket = hash & table->bucket_msk;
+/* Search key in table. Update value if exists */
+for (i = 0; i < K32V64_KEYS_PER_BUCKET; i++) {
+if ((key == table->t[bucket].key[i]) &&
+(table->t[bucket].key_mask & (1 << i))) {
+*old_value = table->t[bucket].val[i];
+*found = 1;
+__atomic_fetch_add(&table->t[bucket].cnt, 1,
+__ATOMIC_ACQUIRE);
+table->t[bucket].val[i] = value;
+__atomic_fetch_add(&table->t[bucket].cnt, 1,
+__ATOMIC_RELEASE);
+return 0;
+}
+}
+
+if (!SLIST_EMPTY(&table->t[bucket].head)) {
+SLIST_FOREACH(ent, &table->t[bucket].head, next) {
+if (ent->key == key) {
+*old_value = ent->val;
+*found = 1;
+__atomic_fetch_add(&table->t[bucket].cnt, 1,
+__ATOMIC_ACQUIRE);
+ent->val = value;
+__atomic_fetch_add(&table->t[bucket].cnt, 1,
+__ATOMIC_RELEASE);
+return 0;
+}
+}
+}
+
+msk = ~table->t[bucket].key_mask & VALID_KEY_MSK;
+if (msk) {
+idx = __builtin_ctz(msk);
+table->t[bucket].key[idx] = key;
+table->t[bucket].val[idx] = value;
+__atomic_or_fetch(&table->t[bucket].key_mask, 1 << idx,
+__ATOMIC_RELEASE);

I think this case also has to guarded with table->t[bucket].cnt updates.

Agree, will change it.

+table->nb_ent++;
+*found = 0;
+return 0;
+}
+
+ret = rte_mempool_get(table->ext_ent_pool, (void **)&ent);
+if (ret < 0)
+return ret;
+
+SLIST_NEXT(ent, next) = NULL;
+ent->key = key;
+ent->val = value;
+rte_smp_wmb();

__atomic_thread_fence(__ATOMIC_RELEASE);
?

Sure, looks like I missed it, will fix

+SLIST_FOREACH(tmp, &table->t[bucket].head, next)
+prev = tmp;
+
+if (prev == NULL)
+SLIST_INSERT_HEAD(&table->t[bucket].head, ent, next);
+else
+SLIST_INSERT_AFTER(prev, ent, next);
+
+table->nb_ent++;
+table->nb_ext_ent++;
+*found = 0;
+return 0;
+}
+
+static int
+k32v64_hash_delete(struct k32v64_hash_table *table, uint32_t key,
+uint32_t hash, uint64_t *old_value)
+{
+uint32_t bucket;
+int i;
+struct k32v64_ext_ent *ent;
+
+if (table == NULL)
+return -EINVAL;
+
+bucket = hash & table->bucket_msk;
+
+for (i = 0; i < K32V64_KEYS_PER_BUCKET; i++) {
+if ((key == table->t[bucket].key[i]) &&
+(table->t[bucket].key_mask & (1 << i))) {
+*old_value = table->t[bucket].val[i];
+ent = SLIST_FIRST(&table->t[bucket].head);
+if (ent) {
+__atomic_fetch_add(&table->t[bucket].cnt, 1,
+__ATOMIC_ACQUIRE);
+table->t[bucket].key[i] = ent->key;
+table->t[bucket].val[i] = ent->val;
+SLIST_REMOVE_HEAD(&table->t[bucket].head, next);
+__atomic_fetch_add(&table->t[bucket].cnt, 1,
+__ATOMIC_RELEASE);
+table->nb_ext_ent--;
+} else
+__atomic_and_fetch(&table->t[bucket].key_mask,
+~(1 << i), __ATOMIC_RELEASE);

Same thought as above - safer to guard this mask update with cnt update.

Agree

+if (ent)
+rte_mempool_put(table->ext_ent_pool, ent);

Can't this 'if(ent)' be merged with previous 'if (ent) {...}' above?

Yes, will merge

+table->nb_ent--;
+return 0;
+}
+}
+
+SLIST_FOREACH(ent, &table->t[bucket].head, next)
+if (ent->key == key)
+break;
+
+if (ent == NULL)
+return -ENOENT;
+
+*old_value = ent->val;
+
+__atomic_fetch_add(&table->t[bucket].cnt, 1, __ATOMIC_ACQUIRE);
+SLIST_REMOVE(&table->t[bucket].head, ent, k32v64_ext_ent, next);
+__atomic_fetch_add(&table->t[bucket].cnt, 1, __ATOMIC_RELEASE);
+rte_mempool_put(table->ext_ent_pool, ent);
+
+table->nb_ext_ent--;
+table->nb_ent--;
+
+return 0;
+}
+

--
Regards,
Vladimir