From: "Ananyev, Konstantin" <konstantin.ananyev@intel.com>
To: "Medvedkin, Vladimir" <vladimir.medvedkin@intel.com>,
"dev@dpdk.org" <dev@dpdk.org>
Cc: "Wang, Yipeng1" <yipeng1.wang@intel.com>,
"Gobriel, Sameh" <sameh.gobriel@intel.com>,
"Richardson, Bruce" <bruce.richardson@intel.com>
Subject: Re: [dpdk-dev] [PATCH v4 1/4] hash: add kv hash library
Date: Tue, 23 Jun 2020 23:06:41 +0000 [thread overview]
Message-ID: <BYAPR11MB33014FD472ADD15D1675902E9A940@BYAPR11MB3301.namprd11.prod.outlook.com> (raw)
In-Reply-To: <BYAPR11MB3301CB9C0DA68A8F6C1DB2E49A940@BYAPR11MB3301.namprd11.prod.outlook.com>
> 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;
As a nit - this formal parameter checking better to do in public function
(rte_kv_hash_bulk_lookup) before de-refencing table and calling actual lookup().
Same story for modify() - formal parameter checking can be done at the top of public function.
BTW, why to unite add/delete into modify(), if internally you have 2 different functions
(for add/delete) anyway?
> > +
> > + 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);
After another thought - atomic add is probably an overkill here.
Something like:
void update_start(struct k32v64_hash_bucket *bkt)
{
bkt->cnt++;
__atomic_thread_fence(__ATOMIC_ACQ_REL);
}
void update_finish(struct k32v64_hash_bucket *bkt)
{
__atomic_thread_fence(__ATOMIC_ACQ_REL);
bkt->cnt++;
}
I think should be sufficient here.
> > + 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.
>
> > + 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);
> ?
>
> > + 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.
>
> > + if (ent)
> > + rte_mempool_put(table->ext_ent_pool, ent);
>
> Can't this 'if(ent)' be merged with previous 'if (ent) {...}' above?
>
> > + 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;
> > +}
> > +
next prev parent reply other threads:[~2020-06-23 23:06 UTC|newest]
Thread overview: 56+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-03-16 13:38 [dpdk-dev] [PATCH 0/3] add new Double Word Key hash table Vladimir Medvedkin
2020-03-16 13:38 ` [dpdk-dev] [PATCH 1/3] hash: add dwk hash library Vladimir Medvedkin
2020-03-16 13:38 ` [dpdk-dev] [PATCH 2/3] test: add dwk hash autotests Vladimir Medvedkin
2020-03-16 13:38 ` [dpdk-dev] [PATCH 3/3] test: add dwk perf tests Vladimir Medvedkin
2020-03-16 14:39 ` [dpdk-dev] [PATCH 0/3] add new Double Word Key hash table Morten Brørup
2020-03-16 18:27 ` Medvedkin, Vladimir
2020-03-16 19:32 ` Stephen Hemminger
2020-03-17 19:52 ` Wang, Yipeng1
2020-03-26 17:28 ` Medvedkin, Vladimir
2020-03-31 19:55 ` Thomas Monjalon
2020-03-31 21:17 ` Honnappa Nagarahalli
2020-04-01 18:37 ` Medvedkin, Vladimir
2020-04-01 18:28 ` Medvedkin, Vladimir
2020-03-16 19:33 ` Morten Brørup
2020-04-08 18:19 ` [dpdk-dev] [PATCH v2 0/4] add new k32v64 " Vladimir Medvedkin
2020-04-15 18:17 ` [dpdk-dev] [PATCH v3 " Vladimir Medvedkin
2020-04-15 18:51 ` Mattias Rönnblom
2020-04-16 10:18 ` Medvedkin, Vladimir
2020-04-16 11:40 ` Mattias Rönnblom
2020-04-17 0:21 ` Wang, Yipeng1
2020-04-23 16:19 ` Ananyev, Konstantin
2020-05-08 20:08 ` Medvedkin, Vladimir
2020-04-16 9:39 ` Thomas Monjalon
2020-04-16 14:02 ` Medvedkin, Vladimir
2020-04-16 14:38 ` Thomas Monjalon
2020-05-08 19:58 ` [dpdk-dev] [PATCH v4 0/4] add new kv " Vladimir Medvedkin
2020-06-16 16:37 ` Thomas Monjalon
2021-03-24 21:28 ` Thomas Monjalon
2021-03-25 12:03 ` Medvedkin, Vladimir
2023-06-12 16:11 ` Stephen Hemminger
2020-05-08 19:58 ` [dpdk-dev] [PATCH v4 1/4] hash: add kv hash library Vladimir Medvedkin
2020-06-23 15:44 ` Ananyev, Konstantin
2020-06-23 23:06 ` Ananyev, Konstantin [this message]
2020-06-25 19:56 ` Medvedkin, Vladimir
2020-06-25 19:49 ` Medvedkin, Vladimir
2020-06-24 1:19 ` Wang, Yipeng1
2020-06-25 20:26 ` Medvedkin, Vladimir
2020-06-25 4:27 ` Honnappa Nagarahalli
2020-05-08 19:58 ` [dpdk-dev] [PATCH v4 2/4] hash: add documentation for " Vladimir Medvedkin
2020-05-08 19:58 ` [dpdk-dev] [PATCH v4 3/4] test: add kv hash autotests Vladimir Medvedkin
2020-05-08 19:58 ` [dpdk-dev] [PATCH v4 4/4] test: add kv perf tests Vladimir Medvedkin
2020-04-15 18:17 ` [dpdk-dev] [PATCH v3 1/4] hash: add k32v64 hash library Vladimir Medvedkin
2020-04-15 18:59 ` Mattias Rönnblom
2020-04-16 10:23 ` Medvedkin, Vladimir
2020-04-23 13:31 ` Ananyev, Konstantin
2020-05-08 20:14 ` Medvedkin, Vladimir
2020-04-29 21:29 ` Honnappa Nagarahalli
2020-05-08 20:38 ` Medvedkin, Vladimir
2020-04-15 18:17 ` [dpdk-dev] [PATCH v3 2/4] hash: add documentation for " Vladimir Medvedkin
2020-04-15 18:17 ` [dpdk-dev] [PATCH v3 3/4] test: add k32v64 hash autotests Vladimir Medvedkin
2020-04-15 18:17 ` [dpdk-dev] [PATCH v3 4/4] test: add k32v64 perf tests Vladimir Medvedkin
2020-04-08 18:19 ` [dpdk-dev] [PATCH v2 1/4] hash: add k32v64 hash library Vladimir Medvedkin
2020-04-08 23:23 ` Ananyev, Konstantin
2020-04-08 18:19 ` [dpdk-dev] [PATCH v2 2/4] hash: add documentation for " Vladimir Medvedkin
2020-04-08 18:19 ` [dpdk-dev] [PATCH v2 3/4] test: add k32v64 hash autotests Vladimir Medvedkin
2020-04-08 18:19 ` [dpdk-dev] [PATCH v2 4/4] test: add k32v64 perf tests Vladimir Medvedkin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=BYAPR11MB33014FD472ADD15D1675902E9A940@BYAPR11MB3301.namprd11.prod.outlook.com \
--to=konstantin.ananyev@intel.com \
--cc=bruce.richardson@intel.com \
--cc=dev@dpdk.org \
--cc=sameh.gobriel@intel.com \
--cc=vladimir.medvedkin@intel.com \
--cc=yipeng1.wang@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).