Re: [dpdk-dev] [PATCH v4 0/8] Add read-write concurrency to rte_hash library

[Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>]

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