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

Message ID 1530906406-289697-1-git-send-email-yipeng1.wang@intel.com (mailing list archive)
Series Add read-write concurrency to rte_hash library |


Wang, Yipeng1 July 6, 2018, 7:46 p.m. UTC
  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.

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)

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