[v4,0/8] Add read-write concurrency to rte_hash library

  This patch set adds the read-write concurrency support in rte_hash.
A new flag value is added to indicate if read-write concurrency is needed
during creation time. Test cases are implemented to do functional and
performance tests.

The new concurrency model is based on rte_rwlock. When Intel TSX is
available and the users indicate to use it, the TM version of the
rte_rwlock will be called. Both multi-writer and read-write concurrency
are protected by the rte_rwlock instead of the x86 specific RTM
instructions, so the x86 specific header rte_cuckoo_hash_x86.h is removed
and the code is infused into the main .c file.

A new rte_hash_count API is proposed to count how many keys are inserted
into the hash table.

v3->v4:
1. Change commit message titles as Pablo suggested. (Pablo)
2. hash: remove unnecessary changes in commit 4. (Pablo)
3. test: remove unnecessary double blank lines. (Pablo)
4. Add Pablo's ack in commit message.

v2->v3:
1. hash: Concurrency bug fix: after beginning cuckoo path moving,
the last empty slot needs to be verified again in case other writers
raced into this slot and occupy it. A new commit is added to do this
bug fix since it applies to master head as well.
2. hash: Concurrency bug fix: if cuckoo path is detected to be invalid,
the current slot needs to be emptied since it is duplicated to its
target bucket.
3. hash: "const" is used for types in multiple locations. (Pablo)
4. hash: rte_malloc used for readwriter lock used wrong align
argument. Similar fix applies to master head so a new commit is
created. (Pablo)
5. hash: ring size calculation fix is moved to front. (Pablo)
6. hash: search-and-remove function is refactored to be more aligned
with other search function. (Pablo)
7. test: using jhash in functional test for read-write concurrency.
It is because jhash with sequential keys incur more cuckoo path.
8. Multiple coding style, typo, commit message fixes. (Pablo)

v1->v2:
1. Split each commit into two commits for easier review (Pablo).
2. Add more comments in various places (Pablo).
3. hash: In key insertion function, move duplicated key checking to
earlier location and protect it using locks. Checking duplicated key
should happen first and data updates should be protected.
4. hash: In lookup bulk function, put signature comparison in lock,
since writers could happen between signature match on two buckets.
5. hash: Add write locks to reset function as well to protect resets.
5. test: Fix 32-bit compilation error in read-write test (Pablo).
6. test: Check total physical core count in read-write test. Don't
test with thread count that larger than physical core count.
7. Other minor fixes such as typos (Pablo).


Yipeng Wang (8):
  hash: fix multiwriter lock memory allocation
  hash: fix a multi-writer race condition
  hash: fix key slot size accuracy
  hash: make duplicated code into functions
  hash: add read and write concurrency support
  test: add tests in hash table perf test
  test: add test case for read write concurrency
  hash: add new API function to query the key count

 lib/librte_hash/meson.build           |   1 -
 lib/librte_hash/rte_cuckoo_hash.c     | 701 +++++++++++++++++++++-------------
 lib/librte_hash/rte_cuckoo_hash.h     |  18 +-
 lib/librte_hash/rte_cuckoo_hash_x86.h | 164 --------
 lib/librte_hash/rte_hash.h            |  14 +
 lib/librte_hash/rte_hash_version.map  |   8 +
 test/test/Makefile                    |   1 +
 test/test/test_hash.c                 |  12 +
 test/test/test_hash_multiwriter.c     |   9 +
 test/test/test_hash_perf.c            |  36 +-
 test/test/test_hash_readwrite.c       | 637 ++++++++++++++++++++++++++++++
 11 files changed, 1156 insertions(+), 445 deletions(-)
 delete mode 100644 lib/librte_hash/rte_cuckoo_hash_x86.h
 create mode 100644 test/test/test_hash_readwrite.c
  

Hi Yipeng/Pablo,
	Apologies for my delayed comments

-----Original Message-----
From: Yipeng Wang <yipeng1.wang@intel.com> 
Sent: Monday, July 9, 2018 5:45 AM
To: pablo.de.lara.guarch@intel.com
Cc: dev@dpdk.org; yipeng1.wang@intel.com; bruce.richardson@intel.com; Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>; vguvva@caviumnetworks.com; brijesh.s.singh@gmail.com
Subject: [PATCH v4 0/8] Add read-write concurrency to rte_hash library

This patch set adds the read-write concurrency support in rte_hash.
A new flag value is added to indicate if read-write concurrency is needed during creation time. Test cases are implemented to do functional and performance tests.

The new concurrency model is based on rte_rwlock. When Intel TSX is available and the users indicate to use it, the TM version of the rte_rwlock will be called. Both multi-writer and read-write concurrency are protected by the rte_rwlock instead of the x86 specific RTM instructions, so the x86 specific header rte_cuckoo_hash_x86.h is removed and the code is infused into the main .c file.

IMO, at a high-level, there are two use cases for the rte_hash library:
1) Writers are on control plane and data plane are readers
2) Writers and readers are on data plane

This distinction is required as in the case of 1) writers are pre-emptible. If I consider platforms without TSX (I do not know how Intel TSX works), the rte_rwlock implementation is blocking. A writer on the control plane can take the lock and get pre-empted. Since rte_rwlock is used for read-write concurrency, it will block the readers (on the data plane) for an extended duration. I think, support for RCU is required to solve this issue.

A new rte_hash_count API is proposed to count how many keys are inserted into the hash table.

v3->v4:
1. Change commit message titles as Pablo suggested. (Pablo) 2. hash: remove unnecessary changes in commit 4. (Pablo) 3. test: remove unnecessary double blank lines. (Pablo) 4. Add Pablo's ack in commit message.

v2->v3:
1. hash: Concurrency bug fix: after beginning cuckoo path moving, the last empty slot needs to be verified again in case other writers raced into this slot and occupy it. A new commit is added to do this bug fix since it applies to master head as well.
2. hash: Concurrency bug fix: if cuckoo path is detected to be invalid, the current slot needs to be emptied since it is duplicated to its target bucket.
3. hash: "const" is used for types in multiple locations. (Pablo) 4. hash: rte_malloc used for readwriter lock used wrong align argument. Similar fix applies to master head so a new commit is created. (Pablo) 5. hash: ring size calculation fix is moved to front. (Pablo) 6. hash: search-and-remove function is refactored to be more aligned with other search function. (Pablo) 7. test: using jhash in functional test for read-write concurrency.
It is because jhash with sequential keys incur more cuckoo path.
8. Multiple coding style, typo, commit message fixes. (Pablo)

v1->v2:
1. Split each commit into two commits for easier review (Pablo).
2. Add more comments in various places (Pablo).
3. hash: In key insertion function, move duplicated key checking to earlier location and protect it using locks. Checking duplicated key should happen first and data updates should be protected.
4. hash: In lookup bulk function, put signature comparison in lock, since writers could happen between signature match on two buckets.
5. hash: Add write locks to reset function as well to protect resets.
5. test: Fix 32-bit compilation error in read-write test (Pablo).
6. test: Check total physical core count in read-write test. Don't test with thread count that larger than physical core count.
7. Other minor fixes such as typos (Pablo).


Yipeng Wang (8):
  hash: fix multiwriter lock memory allocation
  hash: fix a multi-writer race condition
  hash: fix key slot size accuracy
  hash: make duplicated code into functions
  hash: add read and write concurrency support
  test: add tests in hash table perf test
  test: add test case for read write concurrency
  hash: add new API function to query the key count

 lib/librte_hash/meson.build           |   1 -
 lib/librte_hash/rte_cuckoo_hash.c     | 701 +++++++++++++++++++++-------------
 lib/librte_hash/rte_cuckoo_hash.h     |  18 +-
 lib/librte_hash/rte_cuckoo_hash_x86.h | 164 --------
 lib/librte_hash/rte_hash.h            |  14 +
 lib/librte_hash/rte_hash_version.map  |   8 +
 test/test/Makefile                    |   1 +
 test/test/test_hash.c                 |  12 +
 test/test/test_hash_multiwriter.c     |   9 +
 test/test/test_hash_perf.c            |  36 +-
 test/test/test_hash_readwrite.c       | 637 ++++++++++++++++++++++++++++++
 11 files changed, 1156 insertions(+), 445 deletions(-)  delete mode 100644 lib/librte_hash/rte_cuckoo_hash_x86.h
 create mode 100644 test/test/test_hash_readwrite.c

--
2.7.4
  

Hi, Honnappa,

Thanks for the comment.

RCU can handle one of the currency issue (key deletion while lookup) that has been discussed before, but we think it is not easy for RCU-alone to
protect reader from cuckoo path displacement. Also, RCU solution requires user interaction.

We agree that the current rwlock does not support preemptable writer. But a more advanced rwlock with priority could be
implemented in the future into the rwlock library.

Thanks
Yipeng

>-----Original Message-----
>From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
>Sent: Tuesday, July 10, 2018 11:00 AM
>To: Wang, Yipeng1 <yipeng1.wang@intel.com>; De Lara Guarch, Pablo <pablo.de.lara.guarch@intel.com>
>Cc: dev@dpdk.org; Richardson, Bruce <bruce.richardson@intel.com>; vguvva@caviumnetworks.com; brijesh.s.singh@gmail.com; nd
><nd@arm.com>
>Subject: RE: [PATCH v4 0/8] Add read-write concurrency to rte_hash library
>
>Hi Yipeng/Pablo,
>	Apologies for my delayed comments
>
>-----Original Message-----
>From: Yipeng Wang <yipeng1.wang@intel.com>
>Sent: Monday, July 9, 2018 5:45 AM
>To: pablo.de.lara.guarch@intel.com
>Cc: dev@dpdk.org; yipeng1.wang@intel.com; bruce.richardson@intel.com; Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>;
>vguvva@caviumnetworks.com; brijesh.s.singh@gmail.com
>Subject: [PATCH v4 0/8] Add read-write concurrency to rte_hash library
>
>This patch set adds the read-write concurrency support in rte_hash.
>A new flag value is added to indicate if read-write concurrency is needed during creation time. Test cases are implemented to do
>functional and performance tests.
>
>The new concurrency model is based on rte_rwlock. When Intel TSX is available and the users indicate to use it, the TM version of the
>rte_rwlock will be called. Both multi-writer and read-write concurrency are protected by the rte_rwlock instead of the x86 specific
>RTM instructions, so the x86 specific header rte_cuckoo_hash_x86.h is removed and the code is infused into the main .c file.
>
>IMO, at a high-level, there are two use cases for the rte_hash library:
>1) Writers are on control plane and data plane are readers
>2) Writers and readers are on data plane
>
>This distinction is required as in the case of 1) writers are pre-emptible. If I consider platforms without TSX (I do not know how Intel
>TSX works), the rte_rwlock implementation is blocking. A writer on the control plane can take the lock and get pre-empted. Since
>rte_rwlock is used for read-write concurrency, it will block the readers (on the data plane) for an extended duration. I think, support
>for RCU is required to solve this issue.
>
>
  

Hi Yipeng,
	I agree with you on RCU. It solves only part of the problem and requires application involvement. Use of atomics is required to solve few more problems.

Not solving the preemptible writer issue will change the behavior for existing applications, is that ok?

I will submit a RFC with my ideas.

Thank you,
Honnappa

-----Original Message-----
From: Wang, Yipeng1 <yipeng1.wang@intel.com> 
Sent: Wednesday, July 11, 2018 8:31 PM
To: Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>; De Lara Guarch, Pablo <pablo.de.lara.guarch@intel.com>
Cc: dev@dpdk.org; Richardson, Bruce <bruce.richardson@intel.com>; vguvva@caviumnetworks.com; brijesh.s.singh@gmail.com; nd <nd@arm.com>; Tai, Charlie <charlie.tai@intel.com>; Wang, Ren <ren.wang@intel.com>; Gobriel, Sameh <sameh.gobriel@intel.com>
Subject: RE: [PATCH v4 0/8] Add read-write concurrency to rte_hash library

Hi, Honnappa,

Thanks for the comment.

RCU can handle one of the currency issue (key deletion while lookup) that has been discussed before, but we think it is not easy for RCU-alone to protect reader from cuckoo path displacement. Also, RCU solution requires user interaction.

We agree that the current rwlock does not support preemptable writer. But a more advanced rwlock with priority could be implemented in the future into the rwlock library.

Thanks
Yipeng

>-----Original Message-----
>From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
>Sent: Tuesday, July 10, 2018 11:00 AM
>To: Wang, Yipeng1 <yipeng1.wang@intel.com>; De Lara Guarch, Pablo 
><pablo.de.lara.guarch@intel.com>
>Cc: dev@dpdk.org; Richardson, Bruce <bruce.richardson@intel.com>; 
>vguvva@caviumnetworks.com; brijesh.s.singh@gmail.com; nd <nd@arm.com>
>Subject: RE: [PATCH v4 0/8] Add read-write concurrency to rte_hash 
>library
>
>Hi Yipeng/Pablo,
>	Apologies for my delayed comments
>
>-----Original Message-----
>From: Yipeng Wang <yipeng1.wang@intel.com>
>Sent: Monday, July 9, 2018 5:45 AM
>To: pablo.de.lara.guarch@intel.com
>Cc: dev@dpdk.org; yipeng1.wang@intel.com; bruce.richardson@intel.com; 
>Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>; 
>vguvva@caviumnetworks.com; brijesh.s.singh@gmail.com
>Subject: [PATCH v4 0/8] Add read-write concurrency to rte_hash library
>
>This patch set adds the read-write concurrency support in rte_hash.
>A new flag value is added to indicate if read-write concurrency is 
>needed during creation time. Test cases are implemented to do functional and performance tests.
>
>The new concurrency model is based on rte_rwlock. When Intel TSX is 
>available and the users indicate to use it, the TM version of the 
>rte_rwlock will be called. Both multi-writer and read-write concurrency are protected by the rte_rwlock instead of the x86 specific RTM instructions, so the x86 specific header rte_cuckoo_hash_x86.h is removed and the code is infused into the main .c file.
>
>IMO, at a high-level, there are two use cases for the rte_hash library:
>1) Writers are on control plane and data plane are readers
>2) Writers and readers are on data plane
>
>This distinction is required as in the case of 1) writers are 
>pre-emptible. If I consider platforms without TSX (I do not know how 
>Intel TSX works), the rte_rwlock implementation is blocking. A writer 
>on the control plane can take the lock and get pre-empted. Since rte_rwlock is used for read-write concurrency, it will block the readers (on the data plane) for an extended duration. I think, support for RCU is required to solve this issue.
>
>
  

Hi, 

I guess your proposal is to let the user application to handle all the concurrency using RCU and locks. That could be complementary
and orthogonal to our current implementation. User could choose to do this way if TSX is not available, and if they want more control over the
concurrency implementations. A new flag value could be added to allow this mode.

Please copy us when sending out the RFC, we will be happy to review it.

>-----Original Message-----
>From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
>Sent: Wednesday, July 11, 2018 7:36 PM
>To: Wang, Yipeng1 <yipeng1.wang@intel.com>; De Lara Guarch, Pablo <pablo.de.lara.guarch@intel.com>
>Cc: dev@dpdk.org; Richardson, Bruce <bruce.richardson@intel.com>; vguvva@caviumnetworks.com; brijesh.s.singh@gmail.com; nd
><nd@arm.com>; Tai, Charlie <charlie.tai@intel.com>; Wang, Ren <ren.wang@intel.com>; Gobriel, Sameh <sameh.gobriel@intel.com>
>Subject: RE: [PATCH v4 0/8] Add read-write concurrency to rte_hash library
>
>Hi Yipeng,
>	I agree with you on RCU. It solves only part of the problem and requires application involvement. Use of atomics is required to
>solve few more problems.
>
>Not solving the preemptible writer issue will change the behavior for existing applications, is that ok?
>
>I will submit a RFC with my ideas.
>
>Thank you,
>Honnappa
>
>-----Original Message-----
>From: Wang, Yipeng1 <yipeng1.wang@intel.com>
>Sent: Wednesday, July 11, 2018 8:31 PM
>To: Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>; De Lara Guarch, Pablo <pablo.de.lara.guarch@intel.com>
>Cc: dev@dpdk.org; Richardson, Bruce <bruce.richardson@intel.com>; vguvva@caviumnetworks.com; brijesh.s.singh@gmail.com; nd
><nd@arm.com>; Tai, Charlie <charlie.tai@intel.com>; Wang, Ren <ren.wang@intel.com>; Gobriel, Sameh <sameh.gobriel@intel.com>
>Subject: RE: [PATCH v4 0/8] Add read-write concurrency to rte_hash library
>
>Hi, Honnappa,
>
>Thanks for the comment.
>
>RCU can handle one of the currency issue (key deletion while lookup) that has been discussed before, but we think it is not easy for
>RCU-alone to protect reader from cuckoo path displacement. Also, RCU solution requires user interaction.
>
>We agree that the current rwlock does not support preemptable writer. But a more advanced rwlock with priority could be
>implemented in the future into the rwlock library.
>
>Thanks
>Yipeng
>
>>-----Original Message-----
>>From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
>>Sent: Tuesday, July 10, 2018 11:00 AM
>>To: Wang, Yipeng1 <yipeng1.wang@intel.com>; De Lara Guarch, Pablo
>><pablo.de.lara.guarch@intel.com>
>>Cc: dev@dpdk.org; Richardson, Bruce <bruce.richardson@intel.com>;
>>vguvva@caviumnetworks.com; brijesh.s.singh@gmail.com; nd <nd@arm.com>
>>Subject: RE: [PATCH v4 0/8] Add read-write concurrency to rte_hash
>>library
>>
>>Hi Yipeng/Pablo,
>>	Apologies for my delayed comments
>>
>>-----Original Message-----
>>From: Yipeng Wang <yipeng1.wang@intel.com>
>>Sent: Monday, July 9, 2018 5:45 AM
>>To: pablo.de.lara.guarch@intel.com
>>Cc: dev@dpdk.org; yipeng1.wang@intel.com; bruce.richardson@intel.com;
>>Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>;
>>vguvva@caviumnetworks.com; brijesh.s.singh@gmail.com
>>Subject: [PATCH v4 0/8] Add read-write concurrency to rte_hash library
>>
>>This patch set adds the read-write concurrency support in rte_hash.
>>A new flag value is added to indicate if read-write concurrency is
>>needed during creation time. Test cases are implemented to do functional and performance tests.
>>
>>The new concurrency model is based on rte_rwlock. When Intel TSX is
>>available and the users indicate to use it, the TM version of the
>>rte_rwlock will be called. Both multi-writer and read-write concurrency are protected by the rte_rwlock instead of the x86 specific
>RTM instructions, so the x86 specific header rte_cuckoo_hash_x86.h is removed and the code is infused into the main .c file.
>>
>>IMO, at a high-level, there are two use cases for the rte_hash library:
>>1) Writers are on control plane and data plane are readers
>>2) Writers and readers are on data plane
>>
>>This distinction is required as in the case of 1) writers are
>>pre-emptible. If I consider platforms without TSX (I do not know how
>>Intel TSX works), the rte_rwlock implementation is blocking. A writer
>>on the control plane can take the lock and get pre-empted. Since rte_rwlock is used for read-write concurrency, it will block the
>readers (on the data plane) for an extended duration. I think, support for RCU is required to solve this issue.
>>
>>