[dpdk-dev] rte_hash thread safe

[dpdk-dev] rte_hash thread safe

[Brijesh Singh]

Hello,

I  want to use DPDK's rte_hash library to keep track of tcp flows. The
lookups will be done by multiple threads but inserts will be done only
on one thread.

As per the documentation rte_hash library has thread safe lookups. Key
/data inserts should be done on single thread, since those operations
are not thread safe. Is this documentation still correct?

The lookup code compares the key and returns the data if the key
matches, this doesn't look like thread safe. Am I missing something?

_rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,

                                        hash_sig_t sig, void **data)

{



…

                        if (rte_hash_cmp_eq(key, k->key, h) == 0) {

                                if (data != NULL)

                                        *data = k->pdata;

}

Regards,
Brijesh

Re: [dpdk-dev] rte_hash thread safe

[Brijesh Singh]

A gentle reminder,

I am curious to know if/how rte_hash is thread safe for lookups.It is
not obvious to me how following code is thread safe:

_rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,

                                        hash_sig_t sig, void **data)

{



…

                        if (rte_hash_cmp_eq(key, k->key, h) == 0) {

                                if (data != NULL)

                                        *data = k->pdata;

}

a key could be deleted and another key inserted in its slot while the
lookup is happening. For example, in the following sequence of events:
The slot has Key1,V1
Lookup Thread T1 compares the input key to Key1 and it matches. The
thread gets context switched out
Thread T2 deletes Key1.
Thread T2 inserts Key2 with value V2.
T1 reads the data from the slot and returns V2. This is incorrect.


Regards,
Brijesh

On Wed, Apr 11, 2018 at 9:12 PM, Brijesh Singh
<brijesh.s.singh@gmail.com> wrote:
> Hello,
>
> I  want to use DPDK's rte_hash library to keep track of tcp flows. The
> lookups will be done by multiple threads but inserts will be done only
> on one thread.
>
> As per the documentation rte_hash library has thread safe lookups. Key
> /data inserts should be done on single thread, since those operations
> are not thread safe. Is this documentation still correct?
>
> The lookup code compares the key and returns the data if the key
> matches, this doesn't look like thread safe. Am I missing something?
>
> _rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
>
>                                         hash_sig_t sig, void **data)
>
> {
>
>
>
> …
>
>                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
>
>                                 if (data != NULL)
>
>                                         *data = k->pdata;
>
> }
>
> Regards,
> Brijesh

Re: [dpdk-dev] rte_hash thread safe

[Stephen Hemminger]

On Mon, 23 Apr 2018 12:40:41 -0700
Brijesh Singh <brijesh.s.singh@gmail.com> wrote:

> A gentle reminder,
> 
> I am curious to know if/how rte_hash is thread safe for lookups.It is
> not obvious to me how following code is thread safe:
> 
> _rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
> 
>                                         hash_sig_t sig, void **data)
> 
> {
> 
> 
> 
> …
> 
>                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
> 
>                                 if (data != NULL)
> 
>                                         *data = k->pdata;
> 
> }
> 
> a key could be deleted and another key inserted in its slot while the
> lookup is happening. For example, in the following sequence of events:
> The slot has Key1,V1
> Lookup Thread T1 compares the input key to Key1 and it matches. The
> thread gets context switched out
> Thread T2 deletes Key1.
> Thread T2 inserts Key2 with value V2.
> T1 reads the data from the slot and returns V2. This is incorrect.
> 
> 
> Regards,
> Brijesh
> 
> On Wed, Apr 11, 2018 at 9:12 PM, Brijesh Singh
> <brijesh.s.singh@gmail.com> wrote:
> > Hello,
> >
> > I  want to use DPDK's rte_hash library to keep track of tcp flows. The
> > lookups will be done by multiple threads but inserts will be done only
> > on one thread.
> >
> > As per the documentation rte_hash library has thread safe lookups. Key
> > /data inserts should be done on single thread, since those operations
> > are not thread safe. Is this documentation still correct?
> >
> > The lookup code compares the key and returns the data if the key
> > matches, this doesn't look like thread safe. Am I missing something?
> >
> > _rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
> >
> >                                         hash_sig_t sig, void **data)
> >
> > {
> >
> >
> >
> > …
> >
> >                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
> >
> >                                 if (data != NULL)
> >
> >                                         *data = k->pdata;
> >
> > }
> >
> > Regards,
> > Brijesh  

The best way to handle this is to do some kind of Read Copy Update.
Unfortunately, this is not possible in scope of DPDK since it requires
cooperation from application threads.

If you need thread safe hash table, my recommendation would be to
skip the DPDK hash library and use userspace RCU instead:
  http://liburcu.org/

Note: URCU is LGPL versus BSD licensed. But then any non trivial
Linux application needs to use LGPL libraries already.

Re: [dpdk-dev] rte_hash thread safe

[Jim Murphy]

Has anyone seen performance data comparing rte_hash (perhaps with r/w
locks) versus URCU hash?


On Mon, Apr 23, 2018 at 4:50 PM, Stephen Hemminger <
stephen@networkplumber.org> wrote:

> On Mon, 23 Apr 2018 12:40:41 -0700
> Brijesh Singh <brijesh.s.singh@gmail.com> wrote:
>
> > A gentle reminder,
> >
> > I am curious to know if/how rte_hash is thread safe for lookups.It is
> > not obvious to me how following code is thread safe:
> >
> > _rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
> >
> >                                         hash_sig_t sig, void **data)
> >
> > {
> >
> >
> >
> > …
> >
> >                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
> >
> >                                 if (data != NULL)
> >
> >                                         *data = k->pdata;
> >
> > }
> >
> > a key could be deleted and another key inserted in its slot while the
> > lookup is happening. For example, in the following sequence of events:
> > The slot has Key1,V1
> > Lookup Thread T1 compares the input key to Key1 and it matches. The
> > thread gets context switched out
> > Thread T2 deletes Key1.
> > Thread T2 inserts Key2 with value V2.
> > T1 reads the data from the slot and returns V2. This is incorrect.
> >
> >
> > Regards,
> > Brijesh
> >
> > On Wed, Apr 11, 2018 at 9:12 PM, Brijesh Singh
> > <brijesh.s.singh@gmail.com> wrote:
> > > Hello,
> > >
> > > I  want to use DPDK's rte_hash library to keep track of tcp flows. The
> > > lookups will be done by multiple threads but inserts will be done only
> > > on one thread.
> > >
> > > As per the documentation rte_hash library has thread safe lookups. Key
> > > /data inserts should be done on single thread, since those operations
> > > are not thread safe. Is this documentation still correct?
> > >
> > > The lookup code compares the key and returns the data if the key
> > > matches, this doesn't look like thread safe. Am I missing something?
> > >
> > > _rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
> > >
> > >                                         hash_sig_t sig, void **data)
> > >
> > > {
> > >
> > >
> > >
> > > …
> > >
> > >                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
> > >
> > >                                 if (data != NULL)
> > >
> > >                                         *data = k->pdata;
> > >
> > > }
> > >
> > > Regards,
> > > Brijesh
>
> The best way to handle this is to do some kind of Read Copy Update.
> Unfortunately, this is not possible in scope of DPDK since it requires
> cooperation from application threads.
>
> If you need thread safe hash table, my recommendation would be to
> skip the DPDK hash library and use userspace RCU instead:
>   http://liburcu.org/
>
> Note: URCU is LGPL versus BSD licensed. But then any non trivial
> Linux application needs to use LGPL libraries already.
>

Re: [dpdk-dev] rte_hash thread safe

[Stephen Hemminger]

On Mon, 23 Apr 2018 17:21:15 -0700
Jim Murphy <jmurphy@arista.com> wrote:

> Has anyone seen performance data comparing rte_hash (perhaps with r/w
> locks) versus URCU hash?
> 
> 
> On Mon, Apr 23, 2018 at 4:50 PM, Stephen Hemminger <
> stephen@networkplumber.org> wrote:  
> 
> > On Mon, 23 Apr 2018 12:40:41 -0700
> > Brijesh Singh <brijesh.s.singh@gmail.com> wrote:
> >  
> > > A gentle reminder,
> > >
> > > I am curious to know if/how rte_hash is thread safe for lookups.It is
> > > not obvious to me how following code is thread safe:
> > >
> > > _rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
> > >
> > >                                         hash_sig_t sig, void **data)
> > >
> > > {
> > >
> > >
> > >
> > > …
> > >
> > >                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
> > >
> > >                                 if (data != NULL)
> > >
> > >                                         *data = k->pdata;
> > >
> > > }
> > >
> > > a key could be deleted and another key inserted in its slot while the
> > > lookup is happening. For example, in the following sequence of events:
> > > The slot has Key1,V1
> > > Lookup Thread T1 compares the input key to Key1 and it matches. The
> > > thread gets context switched out
> > > Thread T2 deletes Key1.
> > > Thread T2 inserts Key2 with value V2.
> > > T1 reads the data from the slot and returns V2. This is incorrect.
> > >
> > >
> > > Regards,
> > > Brijesh
> > >
> > > On Wed, Apr 11, 2018 at 9:12 PM, Brijesh Singh
> > > <brijesh.s.singh@gmail.com> wrote:  
> > > > Hello,
> > > >
> > > > I  want to use DPDK's rte_hash library to keep track of tcp flows. The
> > > > lookups will be done by multiple threads but inserts will be done only
> > > > on one thread.
> > > >
> > > > As per the documentation rte_hash library has thread safe lookups. Key
> > > > /data inserts should be done on single thread, since those operations
> > > > are not thread safe. Is this documentation still correct?
> > > >
> > > > The lookup code compares the key and returns the data if the key
> > > > matches, this doesn't look like thread safe. Am I missing something?
> > > >
> > > > _rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
> > > >
> > > >                                         hash_sig_t sig, void **data)
> > > >
> > > > {
> > > >
> > > >
> > > >
> > > > …
> > > >
> > > >                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
> > > >
> > > >                                 if (data != NULL)
> > > >
> > > >                                         *data = k->pdata;
> > > >
> > > > }
> > > >
> > > > Regards,
> > > > Brijesh  
> >
> > The best way to handle this is to do some kind of Read Copy Update.
> > Unfortunately, this is not possible in scope of DPDK since it requires
> > cooperation from application threads.
> >
> > If you need thread safe hash table, my recommendation would be to
> > skip the DPDK hash library and use userspace RCU instead:
> >   http://liburcu.org/
> >
> > Note: URCU is LGPL versus BSD licensed. But then any non trivial
> > Linux application needs to use LGPL libraries already.
> >  

No. But R/W locks are really slow. Look at one of Paul Mc Kenney's many RCU
talks and papers.

Re: [dpdk-dev] rte_hash thread safe

[Jim Murphy]

Anecdotally I've heard that the urcu hash implementation is slower than
rte_hash based on pure lookup performance. Has anyone considered adding RCU
hooks into rte_hash?


On Mon, Apr 23, 2018 at 5:30 PM, Stephen Hemminger <
stephen@networkplumber.org> wrote:

> On Mon, 23 Apr 2018 17:21:15 -0700
> Jim Murphy <jmurphy@arista.com> wrote:
>
> > Has anyone seen performance data comparing rte_hash (perhaps with r/w
> > locks) versus URCU hash?
> >
> >
> > On Mon, Apr 23, 2018 at 4:50 PM, Stephen Hemminger <
> > stephen@networkplumber.org> wrote:
> >
> > > On Mon, 23 Apr 2018 12:40:41 -0700
> > > Brijesh Singh <brijesh.s.singh@gmail.com> wrote:
> > >
> > > > A gentle reminder,
> > > >
> > > > I am curious to know if/how rte_hash is thread safe for lookups.It is
> > > > not obvious to me how following code is thread safe:
> > > >
> > > > _rte_hash_lookup_with_hash(const struct rte_hash *h, const void
> *key,
> > > >
> > > >                                         hash_sig_t sig, void **data)
> > > >
> > > > {
> > > >
> > > >
> > > >
> > > > …
> > > >
> > > >                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
> > > >
> > > >                                 if (data != NULL)
> > > >
> > > >                                         *data = k->pdata;
> > > >
> > > > }
> > > >
> > > > a key could be deleted and another key inserted in its slot while the
> > > > lookup is happening. For example, in the following sequence of
> events:
> > > > The slot has Key1,V1
> > > > Lookup Thread T1 compares the input key to Key1 and it matches. The
> > > > thread gets context switched out
> > > > Thread T2 deletes Key1.
> > > > Thread T2 inserts Key2 with value V2.
> > > > T1 reads the data from the slot and returns V2. This is incorrect.
> > > >
> > > >
> > > > Regards,
> > > > Brijesh
> > > >
> > > > On Wed, Apr 11, 2018 at 9:12 PM, Brijesh Singh
> > > > <brijesh.s.singh@gmail.com> wrote:
> > > > > Hello,
> > > > >
> > > > > I  want to use DPDK's rte_hash library to keep track of tcp flows.
> The
> > > > > lookups will be done by multiple threads but inserts will be done
> only
> > > > > on one thread.
> > > > >
> > > > > As per the documentation rte_hash library has thread safe lookups.
> Key
> > > > > /data inserts should be done on single thread, since those
> operations
> > > > > are not thread safe. Is this documentation still correct?
> > > > >
> > > > > The lookup code compares the key and returns the data if the key
> > > > > matches, this doesn't look like thread safe. Am I missing
> something?
> > > > >
> > > > > _rte_hash_lookup_with_hash(const struct rte_hash *h, const void
> *key,
> > > > >
> > > > >                                         hash_sig_t sig, void
> **data)
> > > > >
> > > > > {
> > > > >
> > > > >
> > > > >
> > > > > …
> > > > >
> > > > >                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
> > > > >
> > > > >                                 if (data != NULL)
> > > > >
> > > > >                                         *data = k->pdata;
> > > > >
> > > > > }
> > > > >
> > > > > Regards,
> > > > > Brijesh
> > >
> > > The best way to handle this is to do some kind of Read Copy Update.
> > > Unfortunately, this is not possible in scope of DPDK since it requires
> > > cooperation from application threads.
> > >
> > > If you need thread safe hash table, my recommendation would be to
> > > skip the DPDK hash library and use userspace RCU instead:
> > >   http://liburcu.org/
> > >
> > > Note: URCU is LGPL versus BSD licensed. But then any non trivial
> > > Linux application needs to use LGPL libraries already.
> > >
>
> No. But R/W locks are really slow. Look at one of Paul Mc Kenney's many RCU
> talks and papers.
>

Re: [dpdk-dev] rte_hash thread safe

[Stephen Hemminger]

On Mon, 23 Apr 2018 17:48:50 -0700
Jim Murphy <jmurphy@arista.com> wrote:

> Anecdotally I've heard that the urcu hash implementation is slower than
> rte_hash based on pure lookup performance. Has anyone considered adding RCU
> hooks into rte_hash?


Not really possible with DPDK (as I said earlier) because DPDK does not have concept
of thread quiescent period to allow for safe deletion.  You could manually use RCU
concepts of RCU and RTE hash; it would require using userspace RCU primitives
inside DPDK.  This would cause a dependency that would prevent that from ever
being merged upstream due to license conflict; but since DPDK is liberal BSD
license you are free to do it and maintain it on your own.

Re: [dpdk-dev] rte_hash thread safe

[Jim Murphy]

Right, the threads using the DPDK libraries must do the right RCU stuff,
declare quiescent, etc.

I mentioned hooks to address the licensing issue. So for places in rte_hash
were synchronization must be done a no-op function could be called but
users could replace that function with one of their choosing.

Thanks,

Jim




On Mon, Apr 23, 2018 at 6:14 PM, Stephen Hemminger <
stephen@networkplumber.org> wrote:

> On Mon, 23 Apr 2018 17:48:50 -0700
> Jim Murphy <jmurphy@arista.com> wrote:
>
> > Anecdotally I've heard that the urcu hash implementation is slower than
> > rte_hash based on pure lookup performance. Has anyone considered adding
> RCU
> > hooks into rte_hash?
>
>
> Not really possible with DPDK (as I said earlier) because DPDK does not
> have concept
> of thread quiescent period to allow for safe deletion.  You could manually
> use RCU
> concepts of RCU and RTE hash; it would require using userspace RCU
> primitives
> inside DPDK.  This would cause a dependency that would prevent that from
> ever
> being merged upstream due to license conflict; but since DPDK is liberal
> BSD
> license you are free to do it and maintain it on your own.
>

Re: [dpdk-dev] rte_hash thread safe

[Honnappa Nagarahalli]

Another idea would be to keep the synchronization at the thread level and let the application handle RCU. This will keep the cost down if the application has multiple tables requiring RCU. It will also allow the application to use its own methods to declare end of quiescent period.

However, the rte_hash library has to support this. There needs to be a distinction between deleting an entry and freeing the memory (or returning the entry to the free pool) associated with the entry. Freeing of the memory needs to happen after the quiescent period.

-----Original Message-----
From: dev <dev-bounces@dpdk.org> On Behalf Of Jim Murphy
Sent: Monday, April 23, 2018 9:13 PM
To: Stephen Hemminger <stephen@networkplumber.org>
Cc: Brijesh Singh <brijesh.s.singh@gmail.com>; dev@dpdk.org
Subject: Re: [dpdk-dev] rte_hash thread safe

Right, the threads using the DPDK libraries must do the right RCU stuff, declare quiescent, etc.

I mentioned hooks to address the licensing issue. So for places in rte_hash were synchronization must be done a no-op function could be called but users could replace that function with one of their choosing.

Thanks,

Jim




On Mon, Apr 23, 2018 at 6:14 PM, Stephen Hemminger < stephen@networkplumber.org> wrote:

> On Mon, 23 Apr 2018 17:48:50 -0700
> Jim Murphy <jmurphy@arista.com> wrote:
>
> > Anecdotally I've heard that the urcu hash implementation is slower 
> > than rte_hash based on pure lookup performance. Has anyone 
> > considered adding
> RCU
> > hooks into rte_hash?
>
>
> Not really possible with DPDK (as I said earlier) because DPDK does 
> not have concept of thread quiescent period to allow for safe 
> deletion.  You could manually use RCU concepts of RCU and RTE hash; it 
> would require using userspace RCU primitives inside DPDK.  This would 
> cause a dependency that would prevent that from ever being merged 
> upstream due to license conflict; but since DPDK is liberal BSD 
> license you are free to do it and maintain it on your own.
>

Re: [dpdk-dev] rte_hash thread safe

[Brijesh Singh]

Thank you all for explaining. My updates are  uncommon; Adding concept
of quiescent threads should be worst case  loss of 1 full burst cpu
cycles on the threads. This should be acceptable infrequent delay in
packet processing.

I need data on performance of librcu lookups under infrequent updates,
if the difference is not significant on x86, I will use librcu.


On Mon, Apr 23, 2018 at 6:14 PM, Stephen Hemminger
<stephen@networkplumber.org> wrote:
> On Mon, 23 Apr 2018 17:48:50 -0700
> Jim Murphy <jmurphy@arista.com> wrote:
>
>> Anecdotally I've heard that the urcu hash implementation is slower than
>> rte_hash based on pure lookup performance. Has anyone considered adding RCU
>> hooks into rte_hash?
>
>
> Not really possible with DPDK (as I said earlier) because DPDK does not have concept
> of thread quiescent period to allow for safe deletion.  You could manually use RCU
> concepts of RCU and RTE hash; it would require using userspace RCU primitives
> inside DPDK.  This would cause a dependency that would prevent that from ever
> being merged upstream due to license conflict; but since DPDK is liberal BSD
> license you are free to do it and maintain it on your own.

Re: [dpdk-dev] rte_hash thread safe

[Shyam Shrivastav]

You can look at hash table support under librte_table, we are using it for
tcp stateful  and syncache table (16 bytes key), supports optimized burst
look ups, pretty good performance at line rate with up to half a billion
entries in syn cache lru table and 33 million in flows ext table.
However these tables are pre-allocated and not thread safe (tradeoff with
performance), we use per core tables if running multicore ....
*I thank all creators/contributors involved, it definitely been huge help
in my project *


On Tue, Apr 24, 2018 at 8:34 PM, Brijesh Singh <brijesh.s.singh@gmail.com>
wrote:

> Thank you all for explaining. My updates are  uncommon; Adding concept
> of quiescent threads should be worst case  loss of 1 full burst cpu
> cycles on the threads. This should be acceptable infrequent delay in
> packet processing.
>
> I need data on performance of librcu lookups under infrequent updates,
> if the difference is not significant on x86, I will use librcu.
>
>
> On Mon, Apr 23, 2018 at 6:14 PM, Stephen Hemminger
> <stephen@networkplumber.org> wrote:
> > On Mon, 23 Apr 2018 17:48:50 -0700
> > Jim Murphy <jmurphy@arista.com> wrote:
> >
> >> Anecdotally I've heard that the urcu hash implementation is slower than
> >> rte_hash based on pure lookup performance. Has anyone considered adding
> RCU
> >> hooks into rte_hash?
> >
> >
> > Not really possible with DPDK (as I said earlier) because DPDK does not
> have concept
> > of thread quiescent period to allow for safe deletion.  You could
> manually use RCU
> > concepts of RCU and RTE hash; it would require using userspace RCU
> primitives
> > inside DPDK.  This would cause a dependency that would prevent that from
> ever
> > being merged upstream due to license conflict; but since DPDK is liberal
> BSD
> > license you are free to do it and maintain it on your own.
>

Re: [dpdk-dev] rte_hash thread safe

[Jerin Jacob]

-----Original Message-----
> Date: Mon, 23 Apr 2018 17:48:50 -0700
> From: Jim Murphy <jmurphy@arista.com>
> To: Stephen Hemminger <stephen@networkplumber.org>
> Cc: Brijesh Singh <brijesh.s.singh@gmail.com>, dev@dpdk.org
> Subject: Re: [dpdk-dev] rte_hash thread safe
> 
> Anecdotally I've heard that the urcu hash implementation is slower than
> rte_hash based on pure lookup performance. Has anyone considered adding RCU
> hooks into rte_hash?


For one of our internal project on arm64, we did try rte_hash vs URCU hash.
Based on our results URCU lookup was much better. By default, URCU
library does not allocate the memory from huge page, But it has some
plugin based scheme to override the memory allocation scheme to choose
hugepage using DPDK backend.


> 
> 
> On Mon, Apr 23, 2018 at 5:30 PM, Stephen Hemminger <
> stephen@networkplumber.org> wrote:
> 
> > On Mon, 23 Apr 2018 17:21:15 -0700
> > Jim Murphy <jmurphy@arista.com> wrote:
> >
> > > Has anyone seen performance data comparing rte_hash (perhaps with r/w
> > > locks) versus URCU hash?
> > >
> > >
> > > On Mon, Apr 23, 2018 at 4:50 PM, Stephen Hemminger <
> > > stephen@networkplumber.org> wrote:
> > >
> > > > On Mon, 23 Apr 2018 12:40:41 -0700
> > > > Brijesh Singh <brijesh.s.singh@gmail.com> wrote:
> > > >
> > > > > A gentle reminder,
> > > > >
> > > > > I am curious to know if/how rte_hash is thread safe for lookups.It is
> > > > > not obvious to me how following code is thread safe:
> > > > >
> > > > > _rte_hash_lookup_with_hash(const struct rte_hash *h, const void
> > *key,
> > > > >
> > > > >                                         hash_sig_t sig, void **data)
> > > > >
> > > > > {
> > > > >
> > > > >
> > > > >
> > > > > …
> > > > >
> > > > >                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
> > > > >
> > > > >                                 if (data != NULL)
> > > > >
> > > > >                                         *data = k->pdata;
> > > > >
> > > > > }
> > > > >
> > > > > a key could be deleted and another key inserted in its slot while the
> > > > > lookup is happening. For example, in the following sequence of
> > events:
> > > > > The slot has Key1,V1
> > > > > Lookup Thread T1 compares the input key to Key1 and it matches. The
> > > > > thread gets context switched out
> > > > > Thread T2 deletes Key1.
> > > > > Thread T2 inserts Key2 with value V2.
> > > > > T1 reads the data from the slot and returns V2. This is incorrect.
> > > > >
> > > > >
> > > > > Regards,
> > > > > Brijesh
> > > > >
> > > > > On Wed, Apr 11, 2018 at 9:12 PM, Brijesh Singh
> > > > > <brijesh.s.singh@gmail.com> wrote:
> > > > > > Hello,
> > > > > >
> > > > > > I  want to use DPDK's rte_hash library to keep track of tcp flows.
> > The
> > > > > > lookups will be done by multiple threads but inserts will be done
> > only
> > > > > > on one thread.
> > > > > >
> > > > > > As per the documentation rte_hash library has thread safe lookups.
> > Key
> > > > > > /data inserts should be done on single thread, since those
> > operations
> > > > > > are not thread safe. Is this documentation still correct?
> > > > > >
> > > > > > The lookup code compares the key and returns the data if the key
> > > > > > matches, this doesn't look like thread safe. Am I missing
> > something?
> > > > > >
> > > > > > _rte_hash_lookup_with_hash(const struct rte_hash *h, const void
> > *key,
> > > > > >
> > > > > >                                         hash_sig_t sig, void
> > **data)
> > > > > >
> > > > > > {
> > > > > >
> > > > > >
> > > > > >
> > > > > > …
> > > > > >
> > > > > >                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
> > > > > >
> > > > > >                                 if (data != NULL)
> > > > > >
> > > > > >                                         *data = k->pdata;
> > > > > >
> > > > > > }
> > > > > >
> > > > > > Regards,
> > > > > > Brijesh
> > > >
> > > > The best way to handle this is to do some kind of Read Copy Update.
> > > > Unfortunately, this is not possible in scope of DPDK since it requires
> > > > cooperation from application threads.
> > > >
> > > > If you need thread safe hash table, my recommendation would be to
> > > > skip the DPDK hash library and use userspace RCU instead:
> > > >   http://liburcu.org/
> > > >
> > > > Note: URCU is LGPL versus BSD licensed. But then any non trivial
> > > > Linux application needs to use LGPL libraries already.
> > > >
> >
> > No. But R/W locks are really slow. Look at one of Paul Mc Kenney's many RCU
> > talks and papers.
> >

Re: [dpdk-dev] rte_hash thread safe

[Stephen Hemminger]

On Tue, 24 Apr 2018 09:18:54 +0530
Jerin Jacob <jerin.jacob@caviumnetworks.com> wrote:

> -----Original Message-----
> > Date: Mon, 23 Apr 2018 17:48:50 -0700
> > From: Jim Murphy <jmurphy@arista.com>
> > To: Stephen Hemminger <stephen@networkplumber.org>
> > Cc: Brijesh Singh <brijesh.s.singh@gmail.com>, dev@dpdk.org
> > Subject: Re: [dpdk-dev] rte_hash thread safe
> > 
> > Anecdotally I've heard that the urcu hash implementation is slower than
> > rte_hash based on pure lookup performance. Has anyone considered adding RCU
> > hooks into rte_hash?  
> 
> 
> For one of our internal project on arm64, we did try rte_hash vs URCU hash.
> Based on our results URCU lookup was much better. By default, URCU
> library does not allocate the memory from huge page, But it has some
> plugin based scheme to override the memory allocation scheme to choose
> hugepage using DPDK backend.
> 

Also URCU hash table can be dynamically resized. With DPDK the application
has to guess at the number of hash heads which makes for bad behavior under
small and large workloads. 

Re: [dpdk-dev] rte_hash thread safe

[Honnappa Nagarahalli]

A gentle reminder,

I am curious to know if/how rte_hash is thread safe for lookups.It is not obvious to me how following code is thread safe:

_rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,

                                        hash_sig_t sig, void **data)

{



…

                        if (rte_hash_cmp_eq(key, k->key, h) == 0) {

                                if (data != NULL)

                                        *data = k->pdata;

}

a key could be deleted and another key inserted in its slot while the lookup is happening. For example, in the following sequence of events:
The slot has Key1,V1
Lookup Thread T1 compares the input key to Key1 and it matches. The thread gets context switched out Thread T2 deletes Key1.
Thread T2 inserts Key2 with value V2.
T1 reads the data from the slot and returns V2. This is incorrect.

If T1 is a worker/data plane thread, which is supposed to be pinned to the CPU, is it required to consider the case of T1 getting pre-empted?

However, this case can exist with T1 not getting pre-empted. i.e. Key1 can get deleted by thread T2 while T1 is doing the comparison. 

In this case, 'k' is a memory pointer pointing to an array element. The memory itself is not freed. The code will still return the data associated with Key1 - assuming Key2 belongs to a different slot ID. But, it is possible that 'data' may not be valid anymore since it is owned by the application.


Regards,
Brijesh

On Wed, Apr 11, 2018 at 9:12 PM, Brijesh Singh <brijesh.s.singh@gmail.com> wrote:
> Hello,
>
> I  want to use DPDK's rte_hash library to keep track of tcp flows. The 
> lookups will be done by multiple threads but inserts will be done only 
> on one thread.
>
> As per the documentation rte_hash library has thread safe lookups. Key 
> /data inserts should be done on single thread, since those operations 
> are not thread safe. Is this documentation still correct?
>
> The lookup code compares the key and returns the data if the key 
> matches, this doesn't look like thread safe. Am I missing something?
>
> _rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
>
>                                         hash_sig_t sig, void **data)
>
> {
>
>
>
> …
>
>                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
>
>                                 if (data != NULL)
>
>                                         *data = k->pdata;
>
> }
>
> Regards,
> Brijesh

Re: [dpdk-dev] rte_hash thread safe

[Ananyev, Konstantin]

> 
> A gentle reminder,
> 
> I am curious to know if/how rte_hash is thread safe for lookups.It is not obvious to me how following code is thread safe:

I don't think it is really thread-safe: you can't do lookup and add/delete simultaneously from different threads.
Some extra synchronization would be needed.
Konstantin

> 
> _rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
> 
>                                         hash_sig_t sig, void **data)
> 
> {
> 
> 
> 
> …
> 
>                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
> 
>                                 if (data != NULL)
> 
>                                         *data = k->pdata;
> 
> }
> 
> a key could be deleted and another key inserted in its slot while the lookup is happening. For example, in the following sequence of events:
> The slot has Key1,V1
> Lookup Thread T1 compares the input key to Key1 and it matches. The thread gets context switched out Thread T2 deletes Key1.
> Thread T2 inserts Key2 with value V2.
> T1 reads the data from the slot and returns V2. This is incorrect.
> 
> If T1 is a worker/data plane thread, which is supposed to be pinned to the CPU, is it required to consider the case of T1 getting pre-empted?
> 
> However, this case can exist with T1 not getting pre-empted. i.e. Key1 can get deleted by thread T2 while T1 is doing the comparison.
> 
> In this case, 'k' is a memory pointer pointing to an array element. The memory itself is not freed. The code will still return the data
> associated with Key1 - assuming Key2 belongs to a different slot ID. But, it is possible that 'data' may not be valid anymore since it is owned
> by the application.
> 
> 
> Regards,
> Brijesh
> 
> On Wed, Apr 11, 2018 at 9:12 PM, Brijesh Singh <brijesh.s.singh@gmail.com> wrote:
> > Hello,
> >
> > I  want to use DPDK's rte_hash library to keep track of tcp flows. The
> > lookups will be done by multiple threads but inserts will be done only
> > on one thread.
> >
> > As per the documentation rte_hash library has thread safe lookups. Key
> > /data inserts should be done on single thread, since those operations
> > are not thread safe. Is this documentation still correct?
> >
> > The lookup code compares the key and returns the data if the key
> > matches, this doesn't look like thread safe. Am I missing something?
> >
> > _rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
> >
> >                                         hash_sig_t sig, void **data)
> >
> > {
> >
> >
> >
> > …
> >
> >                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
> >
> >                                 if (data != NULL)
> >
> >                                         *data = k->pdata;
> >
> > }
> >
> > Regards,
> > Brijesh

Re: [dpdk-dev] rte_hash thread safe

[Bruce Richardson]

On Tue, Apr 24, 2018 at 11:03:42AM +0000, Ananyev, Konstantin wrote:
> 
> 
> > 
> > A gentle reminder,
> > 
> > I am curious to know if/how rte_hash is thread safe for lookups.It is not obvious to me how following code is thread safe:
> 
> I don't think it is really thread-safe: you can't do lookup and add/delete simultaneously from different threads.
> Some extra synchronization would be needed.
> Konstantin
> 
This notice may be a left-over from older versions. I believe in the past,
the hash library used to be safe to have add/delete and lookup in parallel,
but it certainly appears to be no longer the case.

/Bruce

Re: [dpdk-dev] rte_hash thread safe

[Wang, Yipeng1]

Hi, Brijesh and all,

Thanks for bringing this up. We actually have a read-write concurrency support patch coming in a couple of weeks for rte_hash aiming this release.  More changes are on the way for future releases. :)

Thanks
Yipeng 

>-----Original Message-----
>From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Brijesh Singh
>Sent: Wednesday, April 11, 2018 9:12 PM
>To: dev@dpdk.org
>Subject: [dpdk-dev] rte_hash thread safe
>
>Hello,
>
>I  want to use DPDK's rte_hash library to keep track of tcp flows. The
>lookups will be done by multiple threads but inserts will be done only
>on one thread.
>
>As per the documentation rte_hash library has thread safe lookups. Key
>/data inserts should be done on single thread, since those operations
>are not thread safe. Is this documentation still correct?
>
>The lookup code compares the key and returns the data if the key
>matches, this doesn't look like thread safe. Am I missing something?
>
>_rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
>
>                                        hash_sig_t sig, void **data)
>
>{
>
>
>
>…
>
>                        if (rte_hash_cmp_eq(key, k->key, h) == 0) {
>
>                                if (data != NULL)
>
>                                        *data = k->pdata;
>
>}
>
>Regards,
>Brijesh