DPDK patches and discussions
 help / color / mirror / Atom feed
* [dpdk-dev] rte_hash thread safe
@ 2018-04-12  4:12 Brijesh Singh
  2018-04-23 19:40 ` Brijesh Singh
  2018-05-24 17:35 ` Wang, Yipeng1
  0 siblings, 2 replies; 17+ messages in thread
From: Brijesh Singh @ 2018-04-12  4:12 UTC (permalink / raw)
  To: dev

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

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [dpdk-dev] rte_hash thread safe
  2018-04-12  4:12 [dpdk-dev] rte_hash thread safe Brijesh Singh
@ 2018-04-23 19:40 ` Brijesh Singh
  2018-04-23 23:50   ` Stephen Hemminger
  2018-04-24  6:12   ` Honnappa Nagarahalli
  2018-05-24 17:35 ` Wang, Yipeng1
  1 sibling, 2 replies; 17+ messages in thread
From: Brijesh Singh @ 2018-04-23 19:40 UTC (permalink / raw)
  To: dev

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

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [dpdk-dev] rte_hash thread safe
  2018-04-23 19:40 ` Brijesh Singh
@ 2018-04-23 23:50   ` Stephen Hemminger
  2018-04-24  0:21     ` Jim Murphy
  2018-04-24  6:12   ` Honnappa Nagarahalli
  1 sibling, 1 reply; 17+ messages in thread
From: Stephen Hemminger @ 2018-04-23 23:50 UTC (permalink / raw)
  To: Brijesh Singh; +Cc: dev

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.

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [dpdk-dev] rte_hash thread safe
  2018-04-23 23:50   ` Stephen Hemminger
@ 2018-04-24  0:21     ` Jim Murphy
  2018-04-24  0:30       ` Stephen Hemminger
  0 siblings, 1 reply; 17+ messages in thread
From: Jim Murphy @ 2018-04-24  0:21 UTC (permalink / raw)
  To: Stephen Hemminger; +Cc: Brijesh Singh, dev

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.
>

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [dpdk-dev] rte_hash thread safe
  2018-04-24  0:21     ` Jim Murphy
@ 2018-04-24  0:30       ` Stephen Hemminger
  2018-04-24  0:48         ` Jim Murphy
  0 siblings, 1 reply; 17+ messages in thread
From: Stephen Hemminger @ 2018-04-24  0:30 UTC (permalink / raw)
  To: Jim Murphy; +Cc: Brijesh Singh, dev

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.

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [dpdk-dev] rte_hash thread safe
  2018-04-24  0:30       ` Stephen Hemminger
@ 2018-04-24  0:48         ` Jim Murphy
  2018-04-24  1:14           ` Stephen Hemminger
  2018-04-24  3:48           ` Jerin Jacob
  0 siblings, 2 replies; 17+ messages in thread
From: Jim Murphy @ 2018-04-24  0:48 UTC (permalink / raw)
  To: Stephen Hemminger; +Cc: Brijesh Singh, dev

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.
>

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [dpdk-dev] rte_hash thread safe
  2018-04-24  0:48         ` Jim Murphy
@ 2018-04-24  1:14           ` Stephen Hemminger
  2018-04-24  2:13             ` Jim Murphy
  2018-04-24 15:04             ` Brijesh Singh
  2018-04-24  3:48           ` Jerin Jacob
  1 sibling, 2 replies; 17+ messages in thread
From: Stephen Hemminger @ 2018-04-24  1:14 UTC (permalink / raw)
  To: Jim Murphy; +Cc: Brijesh Singh, dev

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.

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [dpdk-dev] rte_hash thread safe
  2018-04-24  1:14           ` Stephen Hemminger
@ 2018-04-24  2:13             ` Jim Murphy
  2018-04-24  6:36               ` Honnappa Nagarahalli
  2018-04-24 15:04             ` Brijesh Singh
  1 sibling, 1 reply; 17+ messages in thread
From: Jim Murphy @ 2018-04-24  2:13 UTC (permalink / raw)
  To: Stephen Hemminger; +Cc: Brijesh Singh, dev

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.
>

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [dpdk-dev] rte_hash thread safe
  2018-04-24  0:48         ` Jim Murphy
  2018-04-24  1:14           ` Stephen Hemminger
@ 2018-04-24  3:48           ` Jerin Jacob
  2018-04-24  5:02             ` Stephen Hemminger
  1 sibling, 1 reply; 17+ messages in thread
From: Jerin Jacob @ 2018-04-24  3:48 UTC (permalink / raw)
  To: Jim Murphy; +Cc: Stephen Hemminger, Brijesh Singh, dev

-----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.
> >

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [dpdk-dev] rte_hash thread safe
  2018-04-24  3:48           ` Jerin Jacob
@ 2018-04-24  5:02             ` Stephen Hemminger
  0 siblings, 0 replies; 17+ messages in thread
From: Stephen Hemminger @ 2018-04-24  5:02 UTC (permalink / raw)
  To: Jerin Jacob; +Cc: Jim Murphy, Brijesh Singh, dev

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. 

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [dpdk-dev] rte_hash thread safe
  2018-04-23 19:40 ` Brijesh Singh
  2018-04-23 23:50   ` Stephen Hemminger
@ 2018-04-24  6:12   ` Honnappa Nagarahalli
  2018-04-24 11:03     ` Ananyev, Konstantin
  1 sibling, 1 reply; 17+ messages in thread
From: Honnappa Nagarahalli @ 2018-04-24  6:12 UTC (permalink / raw)
  To: Brijesh Singh, dev; +Cc: nd


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

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [dpdk-dev] rte_hash thread safe
  2018-04-24  2:13             ` Jim Murphy
@ 2018-04-24  6:36               ` Honnappa Nagarahalli
  0 siblings, 0 replies; 17+ messages in thread
From: Honnappa Nagarahalli @ 2018-04-24  6:36 UTC (permalink / raw)
  To: Jim Murphy, Stephen Hemminger; +Cc: Brijesh Singh, dev, nd

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.
>

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [dpdk-dev] rte_hash thread safe
  2018-04-24  6:12   ` Honnappa Nagarahalli
@ 2018-04-24 11:03     ` Ananyev, Konstantin
  2018-04-24 11:07       ` Bruce Richardson
  0 siblings, 1 reply; 17+ messages in thread
From: Ananyev, Konstantin @ 2018-04-24 11:03 UTC (permalink / raw)
  To: Honnappa Nagarahalli, Brijesh Singh, dev; +Cc: nd



> 
> 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

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [dpdk-dev] rte_hash thread safe
  2018-04-24 11:03     ` Ananyev, Konstantin
@ 2018-04-24 11:07       ` Bruce Richardson
  0 siblings, 0 replies; 17+ messages in thread
From: Bruce Richardson @ 2018-04-24 11:07 UTC (permalink / raw)
  To: Ananyev, Konstantin; +Cc: Honnappa Nagarahalli, Brijesh Singh, dev, nd

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

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [dpdk-dev] rte_hash thread safe
  2018-04-24  1:14           ` Stephen Hemminger
  2018-04-24  2:13             ` Jim Murphy
@ 2018-04-24 15:04             ` Brijesh Singh
  2018-04-25  6:45               ` Shyam Shrivastav
  1 sibling, 1 reply; 17+ messages in thread
From: Brijesh Singh @ 2018-04-24 15:04 UTC (permalink / raw)
  To: Stephen Hemminger; +Cc: Jim Murphy, dev

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.

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [dpdk-dev] rte_hash thread safe
  2018-04-24 15:04             ` Brijesh Singh
@ 2018-04-25  6:45               ` Shyam Shrivastav
  0 siblings, 0 replies; 17+ messages in thread
From: Shyam Shrivastav @ 2018-04-25  6:45 UTC (permalink / raw)
  To: Brijesh Singh; +Cc: Stephen Hemminger, Jim Murphy, dev

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.
>

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [dpdk-dev] rte_hash thread safe
  2018-04-12  4:12 [dpdk-dev] rte_hash thread safe Brijesh Singh
  2018-04-23 19:40 ` Brijesh Singh
@ 2018-05-24 17:35 ` Wang, Yipeng1
  1 sibling, 0 replies; 17+ messages in thread
From: Wang, Yipeng1 @ 2018-05-24 17:35 UTC (permalink / raw)
  To: Brijesh Singh, dev, De Lara Guarch, Pablo
  Cc: stephen, nd, Honnappa.Nagarahalli, Ananyev, Konstantin, Tai,
	Charlie, Gobriel, Sameh, Wang, Ren, jmurphy

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

^ permalink raw reply	[flat|nested] 17+ messages in thread

end of thread, other threads:[~2018-05-24 17:35 UTC | newest]

Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-04-12  4:12 [dpdk-dev] rte_hash thread safe Brijesh Singh
2018-04-23 19:40 ` Brijesh Singh
2018-04-23 23:50   ` Stephen Hemminger
2018-04-24  0:21     ` Jim Murphy
2018-04-24  0:30       ` Stephen Hemminger
2018-04-24  0:48         ` Jim Murphy
2018-04-24  1:14           ` Stephen Hemminger
2018-04-24  2:13             ` Jim Murphy
2018-04-24  6:36               ` Honnappa Nagarahalli
2018-04-24 15:04             ` Brijesh Singh
2018-04-25  6:45               ` Shyam Shrivastav
2018-04-24  3:48           ` Jerin Jacob
2018-04-24  5:02             ` Stephen Hemminger
2018-04-24  6:12   ` Honnappa Nagarahalli
2018-04-24 11:03     ` Ananyev, Konstantin
2018-04-24 11:07       ` Bruce Richardson
2018-05-24 17:35 ` Wang, Yipeng1

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).