hash: add lock-free r/w concurrency
authorHonnappa Nagarahalli <honnappa.nagarahalli@arm.com>
Fri, 26 Oct 2018 05:37:32 +0000 (00:37 -0500)
committerThomas Monjalon <thomas@monjalon.net>
Fri, 26 Oct 2018 10:50:43 +0000 (12:50 +0200)
commite605a1d36ca7ee9182c43d1ec912eeb90cc7fd64
tree13c5e5ec7616a0015b073843765e65da9418dbe6
parentdbdbc4a2e9c4b67247ef2f6556debe7522b5d2e4
hash: add lock-free r/w concurrency

Add lock-free read-write concurrency. This is achieved by the
following changes.

1) Add memory ordering to avoid race conditions. The only race
condition that can occur is -  using the key store element
before the key write is completed. Hence, while inserting the element
the release memory order is used. Any other race condition is caught
by the key comparison. Memory orderings are added only where needed.
For ex: reads in the writer's context do not need memory ordering
as there is a single writer.

key_idx in the bucket entry and pdata in the key store element are
used for synchronisation. key_idx is used to release an inserted
entry in the bucket to the reader. Use of pdata for synchronisation
is required due to updation of an existing entry where-in only
the pdata is updated without updating key_idx.

2) Reader-writer concurrency issue, caused by moving the keys
to their alternative locations during key insert, is solved
by introducing a global counter(tbl_chng_cnt) indicating a
change in table.

3) Add the flag to enable reader-writer concurrency during
run time.

Signed-off-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>
Reviewed-by: Gavin Hu <gavin.hu@arm.com>
Reviewed-by: Ola Liljedahl <ola.liljedahl@arm.com>
Reviewed-by: Steve Capper <steve.capper@arm.com>
Reviewed-by: Yipeng Wang <yipeng1.wang@intel.com>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
doc/guides/prog_guide/hash_lib.rst
doc/guides/rel_notes/release_18_11.rst
lib/librte_hash/rte_cuckoo_hash.c
lib/librte_hash/rte_cuckoo_hash.h
lib/librte_hash/rte_hash.h