path: root/lib/librte_hash/rte_cuckoo_hash.h
diff options
authorHonnappa Nagarahalli <>2018-10-26 00:37:32 -0500
committerThomas Monjalon <>2018-10-26 12:50:43 +0200
commite605a1d36ca7ee9182c43d1ec912eeb90cc7fd64 (patch)
tree13c5e5ec7616a0015b073843765e65da9418dbe6 /lib/librte_hash/rte_cuckoo_hash.h
parentdbdbc4a2e9c4b67247ef2f6556debe7522b5d2e4 (diff)
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 <> Reviewed-by: Gavin Hu <> Reviewed-by: Ola Liljedahl <> Reviewed-by: Steve Capper <> Reviewed-by: Yipeng Wang <> Acked-by: Bruce Richardson <>
Diffstat (limited to 'lib/librte_hash/rte_cuckoo_hash.h')
1 files changed, 5 insertions, 0 deletions
diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h
index 601b2ce..5dfbbc4 100644
--- a/lib/librte_hash/rte_cuckoo_hash.h
+++ b/lib/librte_hash/rte_cuckoo_hash.h
@@ -1,5 +1,6 @@
/* SPDX-License-Identifier: BSD-3-Clause
* Copyright(c) 2016 Intel Corporation
+ * Copyright(c) 2018 Arm Limited
/* rte_cuckoo_hash.h
@@ -174,6 +175,8 @@ struct rte_hash {
* free the key index associated with the deleted entry.
* This flag is enabled by default.
+ uint8_t readwrite_concur_lf_support;
+ /**< If read-write concurrency lock free support is enabled */
uint8_t writer_takes_lock;
/**< Indicates if the writer threads need to take lock */
rte_hash_function hash_func; /**< Function used to calculate hash. */
@@ -196,6 +199,8 @@ struct rte_hash {
rte_rwlock_t *readwrite_lock; /**< Read-write lock thread-safety. */
struct rte_hash_bucket *buckets_ext; /**< Extra buckets array */
struct rte_ring *free_ext_bkts; /**< Ring of indexes of free buckets */
+ uint32_t *tbl_chng_cnt;
+ /**< Indicates if the hash table changed from last read. */
} __rte_cache_aligned;
struct queue_node {