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

Yipeng Wang yipeng1.wang at intel.com
Fri Jul 6 21:46:38 CEST 2018


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.


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 bug
  hash: fix to have more accurate key slot size
  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     | 705 +++++++++++++++++++++-------------
 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       | 646 +++++++++++++++++++++++++++++++
 11 files changed, 1167 insertions(+), 447 deletions(-)
 delete mode 100644 lib/librte_hash/rte_cuckoo_hash_x86.h
 create mode 100644 test/test/test_hash_readwrite.c

-- 
2.7.4



More information about the dev mailing list