Hi Yipeng/Pablo,
Apologies for my delayed comments
-----Original Message-----
From: Yipeng Wang <[email protected]>
Sent: Monday, July 9, 2018 5:45 AM
To: [email protected]
Cc: [email protected]; [email protected]; [email protected]; Honnappa
Nagarahalli <[email protected]>; [email protected];
[email protected]
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
