From patchwork Fri Oct 16 17:38:56 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dharmik Thakkar X-Patchwork-Id: 81163 X-Patchwork-Delegate: david.marchand@redhat.com Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id A2488A04DB; Fri, 16 Oct 2020 19:40:32 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id D641AC936; Fri, 16 Oct 2020 19:39:20 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by dpdk.org (Postfix) with ESMTP id 75C36C918 for ; Fri, 16 Oct 2020 19:39:16 +0200 (CEST) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id ED41213D5; Fri, 16 Oct 2020 10:39:15 -0700 (PDT) Received: from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com [10.118.12.95]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id E15303F719; Fri, 16 Oct 2020 10:39:10 -0700 (PDT) From: Dharmik Thakkar To: Yipeng Wang , Sameh Gobriel , Bruce Richardson , Ray Kinsella , Neil Horman Cc: dev@dpdk.org, nd@arm.com, Dharmik Thakkar Date: Fri, 16 Oct 2020 12:38:56 -0500 Message-Id: <20201016173858.1134-2-dharmik.thakkar@arm.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20201016173858.1134-1-dharmik.thakkar@arm.com> References: <20200819040537.1792-1-dharmik.thakkar@arm.com> <20201016173858.1134-1-dharmik.thakkar@arm.com> Subject: [dpdk-dev] [PATCH v3 1/3] lib/hash: integrate RCU QSBR X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Currently, users have to use external RCU mechanisms to free resources when using lock free hash algorithm. Integrate RCU QSBR process to make it easier for the applications to use lock free algorithm. Refer to RCU documentation to understand various aspects of integrating RCU library into other libraries. Suggested-by: Honnappa Nagarahalli Signed-off-by: Dharmik Thakkar Reviewed-by: Ruifeng Wang Acked-by: Ray Kinsella --- doc/guides/prog_guide/hash_lib.rst | 11 +- lib/librte_hash/meson.build | 1 + lib/librte_hash/rte_cuckoo_hash.c | 300 +++++++++++++++++++++------ lib/librte_hash/rte_cuckoo_hash.h | 8 + lib/librte_hash/rte_hash.h | 77 ++++++- lib/librte_hash/rte_hash_version.map | 2 +- 6 files changed, 324 insertions(+), 75 deletions(-) diff --git a/doc/guides/prog_guide/hash_lib.rst b/doc/guides/prog_guide/hash_lib.rst index d06c7de2ead1..63e183ed1f08 100644 --- a/doc/guides/prog_guide/hash_lib.rst +++ b/doc/guides/prog_guide/hash_lib.rst @@ -102,6 +102,9 @@ For concurrent writes, and concurrent reads and writes the following flag values * If the 'do not free on delete' (RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL) flag is set, the position of the entry in the hash table is not freed upon calling delete(). This flag is enabled by default when the lock free read/write concurrency flag is set. The application should free the position after all the readers have stopped referencing the position. Where required, the application can make use of RCU mechanisms to determine when the readers have stopped referencing the position. + RCU QSBR process is integrated within the Hash library for safe freeing of the position. Application has certain responsibilities while using this feature. + Please refer to resource reclamation framework of :ref:`RCU library ` for more details. + Extendable Bucket Functionality support ---------------------------------------- @@ -109,8 +112,8 @@ An extra flag is used to enable this functionality (flag is not set by default). in the very unlikely case due to excessive hash collisions that a key has failed to be inserted, the hash table bucket is extended with a linked list to insert these failed keys. This feature is important for the workloads (e.g. telco workloads) that need to insert up to 100% of the hash table size and can't tolerate any key insertion failure (even if very few). -Please note that with the 'lock free read/write concurrency' flag enabled, users need to call 'rte_hash_free_key_with_position' API in order to free the empty buckets and -deleted keys, to maintain the 100% capacity guarantee. +Please note that with the 'lock free read/write concurrency' flag enabled, users need to call 'rte_hash_free_key_with_position' API or configure integrated RCU QSBR +(or use external RCU mechanisms) in order to free the empty buckets and deleted keys, to maintain the 100% capacity guarantee. Implementation Details (non Extendable Bucket Case) --------------------------------------------------- @@ -172,7 +175,7 @@ Example of deletion: Similar to lookup, the key is searched in its primary and secondary buckets. If the key is found, the entry is marked as empty. If the hash table was configured with 'no free on delete' or 'lock free read/write concurrency', the position of the key is not freed. It is the responsibility of the user to free the position after -readers are not referencing the position anymore. +readers are not referencing the position anymore. User can configure integrated RCU QSBR or use external RCU mechanisms to safely free the position on delete Implementation Details (with Extendable Bucket) @@ -286,6 +289,8 @@ The flow table operations on the application side are described below: * Free flow: Free flow key position. If 'no free on delete' or 'lock-free read/write concurrency' flags are set, wait till the readers are not referencing the position returned during add/delete flow and then free the position. RCU mechanisms can be used to find out when the readers are not referencing the position anymore. + RCU QSBR process is integrated within the Hash library for safe freeing of the position. Application has certain responsibilities while using this feature. + Please refer to resource reclamation framework of :ref:`RCU library ` for more details. * Lookup flow: Lookup for the flow key in the hash. If the returned position is valid (flow lookup hit), use the returned position to access the flow entry in the flow table. diff --git a/lib/librte_hash/meson.build b/lib/librte_hash/meson.build index 6ab46ae9d768..0977a63fd279 100644 --- a/lib/librte_hash/meson.build +++ b/lib/librte_hash/meson.build @@ -10,3 +10,4 @@ headers = files('rte_crc_arm64.h', sources = files('rte_cuckoo_hash.c', 'rte_fbk_hash.c') deps += ['ring'] +deps += ['rcu'] diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index aad0c965be5e..30ee5c806029 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -52,6 +52,11 @@ static struct rte_tailq_elem rte_hash_tailq = { }; EAL_REGISTER_TAILQ(rte_hash_tailq) +struct __rte_hash_rcu_dq_entry { + uint32_t key_idx; + uint32_t ext_bkt_idx; /**< Extended bkt index */ +}; + struct rte_hash * rte_hash_find_existing(const char *name) { @@ -210,7 +215,10 @@ rte_hash_create(const struct rte_hash_parameters *params) if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) { readwrite_concur_lf_support = 1; - /* Enable not freeing internal memory/index on delete */ + /* Enable not freeing internal memory/index on delete. + * If internal RCU is enabled, freeing of internal memory/index + * is done on delete + */ no_free_on_del = 1; } @@ -505,6 +513,10 @@ rte_hash_free(struct rte_hash *h) rte_mcfg_tailq_write_unlock(); + /* RCU clean up. */ + if (h->dq) + rte_rcu_qsbr_dq_delete(h->dq); + if (h->use_local_cache) rte_free(h->local_free_slots); if (h->writer_takes_lock) @@ -607,11 +619,21 @@ void rte_hash_reset(struct rte_hash *h) { uint32_t tot_ring_cnt, i; + unsigned int pending; if (h == NULL) return; __hash_rw_writer_lock(h); + + /* RCU QSBR clean up. */ + if (h->dq) { + /* Reclaim all the resources */ + rte_rcu_qsbr_dq_reclaim(h->dq, ~0, NULL, &pending, NULL); + if (pending != 0) + RTE_LOG(ERR, HASH, "RCU reclaim all resources failed\n"); + } + memset(h->buckets, 0, h->num_buckets * sizeof(struct rte_hash_bucket)); memset(h->key_store, 0, h->key_entry_size * (h->entries + 1)); *h->tbl_chng_cnt = 0; @@ -952,6 +974,37 @@ rte_hash_cuckoo_make_space_mw(const struct rte_hash *h, return -ENOSPC; } +static inline uint32_t +alloc_slot(const struct rte_hash *h, struct lcore_cache *cached_free_slots) +{ + unsigned int n_slots; + uint32_t slot_id; + if (h->use_local_cache) { + /* Try to get a free slot from the local cache */ + if (cached_free_slots->len == 0) { + /* Need to get another burst of free slots from global ring */ + n_slots = rte_ring_mc_dequeue_burst_elem(h->free_slots, + cached_free_slots->objs, + sizeof(uint32_t), + LCORE_CACHE_SIZE, NULL); + if (n_slots == 0) + return EMPTY_SLOT; + + cached_free_slots->len += n_slots; + } + + /* Get a free slot from the local cache */ + cached_free_slots->len--; + slot_id = cached_free_slots->objs[cached_free_slots->len]; + } else { + if (rte_ring_sc_dequeue_elem(h->free_slots, &slot_id, + sizeof(uint32_t)) != 0) + return EMPTY_SLOT; + } + + return slot_id; +} + static inline int32_t __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig, void *data) @@ -963,7 +1016,6 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, uint32_t ext_bkt_id = 0; uint32_t slot_id; int ret; - unsigned n_slots; unsigned lcore_id; unsigned int i; struct lcore_cache *cached_free_slots = NULL; @@ -1001,28 +1053,20 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, if (h->use_local_cache) { lcore_id = rte_lcore_id(); cached_free_slots = &h->local_free_slots[lcore_id]; - /* Try to get a free slot from the local cache */ - if (cached_free_slots->len == 0) { - /* Need to get another burst of free slots from global ring */ - n_slots = rte_ring_mc_dequeue_burst_elem(h->free_slots, - cached_free_slots->objs, - sizeof(uint32_t), - LCORE_CACHE_SIZE, NULL); - if (n_slots == 0) { - return -ENOSPC; - } - - cached_free_slots->len += n_slots; + } + slot_id = alloc_slot(h, cached_free_slots); + if (slot_id == EMPTY_SLOT) { + if (h->dq) { + __hash_rw_writer_lock(h); + ret = rte_rcu_qsbr_dq_reclaim(h->dq, + h->hash_rcu_cfg->max_reclaim_size, + NULL, NULL, NULL); + __hash_rw_writer_unlock(h); + if (ret == 0) + slot_id = alloc_slot(h, cached_free_slots); } - - /* Get a free slot from the local cache */ - cached_free_slots->len--; - slot_id = cached_free_slots->objs[cached_free_slots->len]; - } else { - if (rte_ring_sc_dequeue_elem(h->free_slots, &slot_id, - sizeof(uint32_t)) != 0) { + if (slot_id == EMPTY_SLOT) return -ENOSPC; - } } new_k = RTE_PTR_ADD(keys, slot_id * h->key_entry_size); @@ -1118,8 +1162,19 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, if (rte_ring_sc_dequeue_elem(h->free_ext_bkts, &ext_bkt_id, sizeof(uint32_t)) != 0 || ext_bkt_id == 0) { - ret = -ENOSPC; - goto failure; + if (h->dq) { + if (rte_rcu_qsbr_dq_reclaim(h->dq, + h->hash_rcu_cfg->max_reclaim_size, + NULL, NULL, NULL) == 0) { + rte_ring_sc_dequeue_elem(h->free_ext_bkts, + &ext_bkt_id, + sizeof(uint32_t)); + } + } + if (ext_bkt_id == 0) { + ret = -ENOSPC; + goto failure; + } } /* Use the first location of the new bucket */ @@ -1395,12 +1450,12 @@ rte_hash_lookup_data(const struct rte_hash *h, const void *key, void **data) return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), data); } -static inline void -remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i) +static int +free_slot(const struct rte_hash *h, uint32_t slot_id) { unsigned lcore_id, n_slots; struct lcore_cache *cached_free_slots; - + /* Return key indexes to free slot ring */ if (h->use_local_cache) { lcore_id = rte_lcore_id(); cached_free_slots = &h->local_free_slots[lcore_id]; @@ -1411,18 +1466,127 @@ remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i) cached_free_slots->objs, sizeof(uint32_t), LCORE_CACHE_SIZE, NULL); - ERR_IF_TRUE((n_slots == 0), - "%s: could not enqueue free slots in global ring\n", - __func__); + RETURN_IF_TRUE((n_slots == 0), -EFAULT); cached_free_slots->len -= n_slots; } - /* Put index of new free slot in cache. */ - cached_free_slots->objs[cached_free_slots->len] = - bkt->key_idx[i]; - cached_free_slots->len++; + } + + enqueue_slot_back(h, cached_free_slots, slot_id); + return 0; +} + +static void +__hash_rcu_qsbr_free_resource(void *p, void *e, unsigned int n) +{ + void *key_data = NULL; + int ret; + struct rte_hash_key *keys, *k; + struct rte_hash *h = (struct rte_hash *)p; + struct __rte_hash_rcu_dq_entry rcu_dq_entry = + *((struct __rte_hash_rcu_dq_entry *)e); + + RTE_SET_USED(n); + keys = h->key_store; + + k = (struct rte_hash_key *) ((char *)keys + + rcu_dq_entry.key_idx * h->key_entry_size); + key_data = k->pdata; + if (h->hash_rcu_cfg->free_key_data_func) + h->hash_rcu_cfg->free_key_data_func(h->hash_rcu_cfg->key_data_ptr, + key_data); + + if (h->ext_table_support && rcu_dq_entry.ext_bkt_idx != EMPTY_SLOT) + /* Recycle empty ext bkt to free list. */ + rte_ring_sp_enqueue_elem(h->free_ext_bkts, + &rcu_dq_entry.ext_bkt_idx, sizeof(uint32_t)); + + /* Return key indexes to free slot ring */ + ret = free_slot(h, rcu_dq_entry.key_idx); + if (ret < 0) { + RTE_LOG(ERR, HASH, + "%s: could not enqueue free slots in global ring\n", + __func__); + } +} + +int +rte_hash_rcu_qsbr_add(struct rte_hash *h, + struct rte_hash_rcu_config *cfg) +{ + struct rte_rcu_qsbr_dq_parameters params = {0}; + char rcu_dq_name[RTE_RCU_QSBR_DQ_NAMESIZE]; + struct rte_hash_rcu_config *hash_rcu_cfg = NULL; + + const uint32_t total_entries = h->use_local_cache ? + h->entries + (RTE_MAX_LCORE - 1) * (LCORE_CACHE_SIZE - 1) + 1 + : h->entries + 1; + + if ((h == NULL) || cfg == NULL || cfg->v == NULL) { + rte_errno = EINVAL; + return 1; + } + + if (h->hash_rcu_cfg) { + rte_errno = EEXIST; + return 1; + } + + hash_rcu_cfg = rte_zmalloc(NULL, sizeof(struct rte_hash_rcu_config), 0); + if (hash_rcu_cfg == NULL) { + RTE_LOG(ERR, HASH, "memory allocation failed\n"); + return 1; + } + + if (cfg->mode == RTE_HASH_QSBR_MODE_SYNC) { + /* No other things to do. */ + } else if (cfg->mode == RTE_HASH_QSBR_MODE_DQ) { + /* Init QSBR defer queue. */ + snprintf(rcu_dq_name, sizeof(rcu_dq_name), + "HASH_RCU_%s", h->name); + params.name = rcu_dq_name; + params.size = cfg->dq_size; + if (params.size == 0) + params.size = total_entries; + params.trigger_reclaim_limit = cfg->trigger_reclaim_limit; + if (params.max_reclaim_size == 0) + params.max_reclaim_size = RTE_HASH_RCU_DQ_RECLAIM_MAX; + params.esize = sizeof(struct __rte_hash_rcu_dq_entry); + params.free_fn = __hash_rcu_qsbr_free_resource; + params.p = h; + params.v = cfg->v; + h->dq = rte_rcu_qsbr_dq_create(¶ms); + if (h->dq == NULL) { + rte_free(hash_rcu_cfg); + RTE_LOG(ERR, HASH, "HASH defer queue creation failed\n"); + return 1; + } } else { - rte_ring_sp_enqueue_elem(h->free_slots, - &bkt->key_idx[i], sizeof(uint32_t)); + rte_free(hash_rcu_cfg); + rte_errno = EINVAL; + return 1; + } + + hash_rcu_cfg->v = cfg->v; + hash_rcu_cfg->mode = cfg->mode; + hash_rcu_cfg->dq_size = params.size; + hash_rcu_cfg->trigger_reclaim_limit = params.trigger_reclaim_limit; + hash_rcu_cfg->max_reclaim_size = params.max_reclaim_size; + hash_rcu_cfg->free_key_data_func = cfg->free_key_data_func; + hash_rcu_cfg->key_data_ptr = cfg->key_data_ptr; + + h->hash_rcu_cfg = hash_rcu_cfg; + + return 0; +} + +static inline void +remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i) +{ + int ret = free_slot(h, bkt->key_idx[i]); + if (ret < 0) { + RTE_LOG(ERR, HASH, + "%s: could not enqueue free slots in global ring\n", + __func__); } } @@ -1521,6 +1685,8 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, int pos; int32_t ret, i; uint16_t short_sig; + uint32_t index = EMPTY_SLOT; + struct __rte_hash_rcu_dq_entry rcu_dq_entry; short_sig = get_short_sig(sig); prim_bucket_idx = get_prim_bucket_index(h, sig); @@ -1555,10 +1721,9 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, /* Search last bucket to see if empty to be recycled */ return_bkt: - if (!last_bkt) { - __hash_rw_writer_unlock(h); - return ret; - } + if (!last_bkt) + goto return_key; + while (last_bkt->next) { prev_bkt = last_bkt; last_bkt = last_bkt->next; @@ -1571,11 +1736,11 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, /* found empty bucket and recycle */ if (i == RTE_HASH_BUCKET_ENTRIES) { prev_bkt->next = NULL; - uint32_t index = last_bkt - h->buckets_ext + 1; + index = last_bkt - h->buckets_ext + 1; /* Recycle the empty bkt if * no_free_on_del is disabled. */ - if (h->no_free_on_del) + if (h->no_free_on_del) { /* Store index of an empty ext bkt to be recycled * on calling rte_hash_del_xxx APIs. * When lock free read-write concurrency is enabled, @@ -1583,12 +1748,34 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, * immediately (as readers might be using it still). * Hence freeing of the ext bkt is piggy-backed to * freeing of the key index. + * If using external RCU, store this index in an array. */ - h->ext_bkt_to_free[ret] = index; - else + if (h->hash_rcu_cfg == NULL) + h->ext_bkt_to_free[ret] = index; + } else rte_ring_sp_enqueue_elem(h->free_ext_bkts, &index, sizeof(uint32_t)); } + +return_key: + /* Using internal RCU QSBR */ + if (h->hash_rcu_cfg) { + /* Key index where key is stored, adding the first dummy index */ + rcu_dq_entry.key_idx = ret + 1; + rcu_dq_entry.ext_bkt_idx = index; + if (h->dq == NULL) { + /* Wait for quiescent state change if using + * RTE_HASH_QSBR_MODE_SYNC + */ + rte_rcu_qsbr_synchronize(h->hash_rcu_cfg->v, + RTE_QSBR_THRID_INVALID); + __hash_rcu_qsbr_free_resource((void *)((uintptr_t)h), + &rcu_dq_entry, 1); + } else if (h->dq) + /* Push into QSBR FIFO if using RTE_HASH_QSBR_MODE_DQ */ + if (rte_rcu_qsbr_dq_enqueue(h->dq, &rcu_dq_entry) != 0) + RTE_LOG(ERR, HASH, "Failed to push QSBR FIFO\n"); + } __hash_rw_writer_unlock(h); return ret; } @@ -1637,8 +1824,6 @@ rte_hash_free_key_with_position(const struct rte_hash *h, RETURN_IF_TRUE(((h == NULL) || (key_idx == EMPTY_SLOT)), -EINVAL); - unsigned int lcore_id, n_slots; - struct lcore_cache *cached_free_slots; const uint32_t total_entries = h->use_local_cache ? h->entries + (RTE_MAX_LCORE - 1) * (LCORE_CACHE_SIZE - 1) + 1 : h->entries + 1; @@ -1656,28 +1841,9 @@ rte_hash_free_key_with_position(const struct rte_hash *h, } } - if (h->use_local_cache) { - lcore_id = rte_lcore_id(); - cached_free_slots = &h->local_free_slots[lcore_id]; - /* Cache full, need to free it. */ - if (cached_free_slots->len == LCORE_CACHE_SIZE) { - /* Need to enqueue the free slots in global ring. */ - n_slots = rte_ring_mp_enqueue_burst_elem(h->free_slots, - cached_free_slots->objs, - sizeof(uint32_t), - LCORE_CACHE_SIZE, NULL); - RETURN_IF_TRUE((n_slots == 0), -EFAULT); - cached_free_slots->len -= n_slots; - } - /* Put index of new free slot in cache. */ - cached_free_slots->objs[cached_free_slots->len] = key_idx; - cached_free_slots->len++; - } else { - rte_ring_sp_enqueue_elem(h->free_slots, &key_idx, - sizeof(uint32_t)); - } + /* Enqueue slot to cache/ring of free slots. */ + return free_slot(h, key_idx); - return 0; } static inline void diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index 345de6bf9cfd..85be49d3bbe7 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -168,6 +168,11 @@ struct rte_hash { struct lcore_cache *local_free_slots; /**< Local cache per lcore, storing some indexes of the free slots */ + /* RCU config */ + struct rte_hash_rcu_config *hash_rcu_cfg; + /**< HASH RCU QSBR configuration structure */ + struct rte_rcu_qsbr_dq *dq; /**< RCU QSBR defer queue. */ + /* Fields used in lookup */ uint32_t key_len __rte_cache_aligned; @@ -230,4 +235,7 @@ struct queue_node { int prev_slot; /* Parent(slot) in search path */ }; +/** @internal Default RCU defer queue entries to reclaim in one go. */ +#define RTE_HASH_RCU_DQ_RECLAIM_MAX 16 + #endif diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index bff40251bc98..3d28f177f14a 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -15,6 +15,7 @@ #include #include +#include #ifdef __cplusplus extern "C" { @@ -45,7 +46,8 @@ extern "C" { /** Flag to disable freeing of key index on hash delete. * Refer to rte_hash_del_xxx APIs for more details. * This is enabled by default when RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF - * is enabled. + * is enabled. However, if internal RCU is enabled, freeing of internal + * memory/index is done on delete */ #define RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL 0x10 @@ -67,6 +69,13 @@ typedef uint32_t (*rte_hash_function)(const void *key, uint32_t key_len, /** Type of function used to compare the hash key. */ typedef int (*rte_hash_cmp_eq_t)(const void *key1, const void *key2, size_t key_len); +/** + * Type of function used to free data stored in the key. + * Required when using internal RCU to allow application to free key-data once + * the key is returned to the the ring of free key-slots. + */ +typedef void (*rte_hash_free_key_data)(void *p, void *key_data); + /** * Parameters used when creating the hash table. */ @@ -81,6 +90,39 @@ struct rte_hash_parameters { uint8_t extra_flag; /**< Indicate if additional parameters are present. */ }; +/** RCU reclamation modes */ +enum rte_hash_qsbr_mode { + /** Create defer queue for reclaim. */ + RTE_HASH_QSBR_MODE_DQ = 0, + /** Use blocking mode reclaim. No defer queue created. */ + RTE_HASH_QSBR_MODE_SYNC +}; + +/** HASH RCU QSBR configuration structure. */ +struct rte_hash_rcu_config { + struct rte_rcu_qsbr *v; /**< RCU QSBR variable. */ + enum rte_hash_qsbr_mode mode; + /**< Mode of RCU QSBR. RTE_HASH_QSBR_MODE_xxx + * '0' for default: create defer queue for reclaim. + */ + uint32_t dq_size; + /**< RCU defer queue size. + * default: total hash table entries. + */ + uint32_t trigger_reclaim_limit; /**< Threshold to trigger auto reclaim. */ + uint32_t max_reclaim_size; + /**< Max entries to reclaim in one go. + * default: RTE_HASH_RCU_DQ_RECLAIM_MAX. + */ + void *key_data_ptr; + /**< Pointer passed to the free function. Typically, this is the + * pointer to the data structure to which the resource to free + * (key-data) belongs. This can be NULL. + */ + rte_hash_free_key_data free_key_data_func; + /**< Function to call to free the resource (key-data). */ +}; + /** @internal A hash table structure. */ struct rte_hash; @@ -287,7 +329,8 @@ rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t * Thread safety can be enabled by setting flag during * table creation. * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL or - * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled, + * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled and + * internal RCU is NOT enabled, * the key index returned by rte_hash_add_key_xxx APIs will not be * freed by this API. rte_hash_free_key_with_position API must be called * additionally to free the index associated with the key. @@ -316,7 +359,8 @@ rte_hash_del_key(const struct rte_hash *h, const void *key); * Thread safety can be enabled by setting flag during * table creation. * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL or - * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled, + * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled and + * internal RCU is NOT enabled, * the key index returned by rte_hash_add_key_xxx APIs will not be * freed by this API. rte_hash_free_key_with_position API must be called * additionally to free the index associated with the key. @@ -370,7 +414,8 @@ rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position, * only be called from one thread by default. Thread safety * can be enabled by setting flag during table creation. * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL or - * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled, + * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled and + * internal RCU is NOT enabled, * the key index returned by rte_hash_del_key_xxx APIs must be freed * using this API. This API should be called after all the readers * have stopped referencing the entry corresponding to this key. @@ -625,6 +670,30 @@ rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, */ int32_t rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next); + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * Associate RCU QSBR variable with an Hash object. + * This API should be called to enable the integrated RCU QSBR support and + * should be called immediately after creating the Hash object. + * + * @param h + * the hash object to add RCU QSBR + * @param cfg + * RCU QSBR configuration + * @return + * On success - 0 + * On error - 1 with error code set in rte_errno. + * Possible rte_errno codes are: + * - EINVAL - invalid pointer + * - EEXIST - already added QSBR + * - ENOMEM - memory allocation failure + */ +__rte_experimental +int rte_hash_rcu_qsbr_add(struct rte_hash *h, + struct rte_hash_rcu_config *cfg); #ifdef __cplusplus } #endif diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map index c0db81014ff9..c6d73080f478 100644 --- a/lib/librte_hash/rte_hash_version.map +++ b/lib/librte_hash/rte_hash_version.map @@ -36,5 +36,5 @@ EXPERIMENTAL { rte_hash_lookup_with_hash_bulk; rte_hash_lookup_with_hash_bulk_data; rte_hash_max_key_id; - + rte_hash_rcu_qsbr_add; }; From patchwork Fri Oct 16 17:38:57 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dharmik Thakkar X-Patchwork-Id: 81162 X-Patchwork-Delegate: david.marchand@redhat.com Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 8E4C1A04DB; Fri, 16 Oct 2020 19:40:14 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 2C4E6C92A; Fri, 16 Oct 2020 19:39:19 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by dpdk.org (Postfix) with ESMTP id 9D9A7C902 for ; Fri, 16 Oct 2020 19:39:12 +0200 (CEST) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 10E4C1424; Fri, 16 Oct 2020 10:39:11 -0700 (PDT) Received: from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com [10.118.12.95]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 07F953F802; Fri, 16 Oct 2020 10:39:11 -0700 (PDT) From: Dharmik Thakkar To: Yipeng Wang , Sameh Gobriel , Bruce Richardson Cc: dev@dpdk.org, nd@arm.com, Dharmik Thakkar Date: Fri, 16 Oct 2020 12:38:57 -0500 Message-Id: <20201016173858.1134-3-dharmik.thakkar@arm.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20201016173858.1134-1-dharmik.thakkar@arm.com> References: <20200819040537.1792-1-dharmik.thakkar@arm.com> <20201016173858.1134-1-dharmik.thakkar@arm.com> Subject: [dpdk-dev] [PATCH v3 2/3] test/hash: replace rte atomic with C11 atomic APIs X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Replace rte_atomic APIs with C11 atomic APIs in test_hash_readwrite_lf_perf.c Signed-off-by: Dharmik Thakkar Reviewed-by: Ruifeng Wang --- app/test/test_hash_readwrite_lf_perf.c | 89 +++++++++++--------------- 1 file changed, 36 insertions(+), 53 deletions(-) diff --git a/app/test/test_hash_readwrite_lf_perf.c b/app/test/test_hash_readwrite_lf_perf.c index 889799865c7b..328fa5116f65 100644 --- a/app/test/test_hash_readwrite_lf_perf.c +++ b/app/test/test_hash_readwrite_lf_perf.c @@ -82,8 +82,8 @@ static struct { struct rte_hash *h; } tbl_rwc_test_param; -static rte_atomic64_t gread_cycles; -static rte_atomic64_t greads; +static uint64_t gread_cycles; +static uint64_t greads; static volatile uint8_t writer_done; @@ -645,8 +645,8 @@ test_rwc_reader(__rte_unused void *arg) } while (!writer_done); cycles = rte_rdtsc_precise() - begin; - rte_atomic64_add(&gread_cycles, cycles); - rte_atomic64_add(&greads, read_cnt*loop_cnt); + __atomic_fetch_add(&gread_cycles, cycles, __ATOMIC_RELAXED); + __atomic_fetch_add(&greads, read_cnt*loop_cnt, __ATOMIC_RELAXED); return 0; } @@ -703,9 +703,6 @@ test_hash_add_no_ks_lookup_hit(struct rwc_perf *rwc_perf_results, int rwc_lf, uint8_t write_type = WRITE_NO_KEY_SHIFT; uint8_t read_type = READ_PASS_NO_KEY_SHIFTS; - rte_atomic64_init(&greads); - rte_atomic64_init(&gread_cycles); - if (init_params(rwc_lf, use_jhash, htm, ext_bkt) != 0) goto err; printf("\nTest: Hash add - no key-shifts, read - hit\n"); @@ -721,8 +718,8 @@ test_hash_add_no_ks_lookup_hit(struct rwc_perf *rwc_perf_results, int rwc_lf, printf("\nNumber of readers: %u\n", rwc_core_cnt[n]); - rte_atomic64_clear(&greads); - rte_atomic64_clear(&gread_cycles); + __atomic_store_n(&greads, 0, __ATOMIC_RELAXED); + __atomic_store_n(&gread_cycles, 0, __ATOMIC_RELAXED); rte_hash_reset(tbl_rwc_test_param.h); writer_done = 0; @@ -739,8 +736,8 @@ test_hash_add_no_ks_lookup_hit(struct rwc_perf *rwc_perf_results, int rwc_lf, goto err; unsigned long long cycles_per_lookup = - rte_atomic64_read(&gread_cycles) / - rte_atomic64_read(&greads); + __atomic_load_n(&gread_cycles, __ATOMIC_RELAXED) + / __atomic_load_n(&greads, __ATOMIC_RELAXED); rwc_perf_results->w_no_ks_r_hit[m][n] = cycles_per_lookup; printf("Cycles per lookup: %llu\n", cycles_per_lookup); @@ -773,9 +770,6 @@ test_hash_add_no_ks_lookup_miss(struct rwc_perf *rwc_perf_results, int rwc_lf, uint8_t read_type = READ_FAIL; int ret; - rte_atomic64_init(&greads); - rte_atomic64_init(&gread_cycles); - if (init_params(rwc_lf, use_jhash, htm, ext_bkt) != 0) goto err; printf("\nTest: Hash add - no key-shifts, Hash lookup - miss\n"); @@ -791,8 +785,8 @@ test_hash_add_no_ks_lookup_miss(struct rwc_perf *rwc_perf_results, int rwc_lf, printf("\nNumber of readers: %u\n", rwc_core_cnt[n]); - rte_atomic64_clear(&greads); - rte_atomic64_clear(&gread_cycles); + __atomic_store_n(&greads, 0, __ATOMIC_RELAXED); + __atomic_store_n(&gread_cycles, 0, __ATOMIC_RELAXED); rte_hash_reset(tbl_rwc_test_param.h); writer_done = 0; @@ -811,8 +805,8 @@ test_hash_add_no_ks_lookup_miss(struct rwc_perf *rwc_perf_results, int rwc_lf, goto err; unsigned long long cycles_per_lookup = - rte_atomic64_read(&gread_cycles) / - rte_atomic64_read(&greads); + __atomic_load_n(&gread_cycles, __ATOMIC_RELAXED) + / __atomic_load_n(&greads, __ATOMIC_RELAXED); rwc_perf_results->w_no_ks_r_miss[m][n] = cycles_per_lookup; printf("Cycles per lookup: %llu\n", cycles_per_lookup); @@ -845,9 +839,6 @@ test_hash_add_ks_lookup_hit_non_sp(struct rwc_perf *rwc_perf_results, uint8_t write_type; uint8_t read_type = READ_PASS_NON_SHIFT_PATH; - rte_atomic64_init(&greads); - rte_atomic64_init(&gread_cycles); - if (init_params(rwc_lf, use_jhash, htm, ext_bkt) != 0) goto err; printf("\nTest: Hash add - key shift, Hash lookup - hit" @@ -864,8 +855,8 @@ test_hash_add_ks_lookup_hit_non_sp(struct rwc_perf *rwc_perf_results, printf("\nNumber of readers: %u\n", rwc_core_cnt[n]); - rte_atomic64_clear(&greads); - rte_atomic64_clear(&gread_cycles); + __atomic_store_n(&greads, 0, __ATOMIC_RELAXED); + __atomic_store_n(&gread_cycles, 0, __ATOMIC_RELAXED); rte_hash_reset(tbl_rwc_test_param.h); writer_done = 0; @@ -887,8 +878,8 @@ test_hash_add_ks_lookup_hit_non_sp(struct rwc_perf *rwc_perf_results, goto err; unsigned long long cycles_per_lookup = - rte_atomic64_read(&gread_cycles) / - rte_atomic64_read(&greads); + __atomic_load_n(&gread_cycles, __ATOMIC_RELAXED) + / __atomic_load_n(&greads, __ATOMIC_RELAXED); rwc_perf_results->w_ks_r_hit_nsp[m][n] = cycles_per_lookup; printf("Cycles per lookup: %llu\n", cycles_per_lookup); @@ -921,9 +912,6 @@ test_hash_add_ks_lookup_hit_sp(struct rwc_perf *rwc_perf_results, int rwc_lf, uint8_t write_type; uint8_t read_type = READ_PASS_SHIFT_PATH; - rte_atomic64_init(&greads); - rte_atomic64_init(&gread_cycles); - if (init_params(rwc_lf, use_jhash, htm, ext_bkt) != 0) goto err; printf("\nTest: Hash add - key shift, Hash lookup - hit (shift-path)" @@ -940,8 +928,9 @@ test_hash_add_ks_lookup_hit_sp(struct rwc_perf *rwc_perf_results, int rwc_lf, goto finish; printf("\nNumber of readers: %u\n", rwc_core_cnt[n]); - rte_atomic64_clear(&greads); - rte_atomic64_clear(&gread_cycles); + + __atomic_store_n(&greads, 0, __ATOMIC_RELAXED); + __atomic_store_n(&gread_cycles, 0, __ATOMIC_RELAXED); rte_hash_reset(tbl_rwc_test_param.h); writer_done = 0; @@ -963,8 +952,8 @@ test_hash_add_ks_lookup_hit_sp(struct rwc_perf *rwc_perf_results, int rwc_lf, goto err; unsigned long long cycles_per_lookup = - rte_atomic64_read(&gread_cycles) / - rte_atomic64_read(&greads); + __atomic_load_n(&gread_cycles, __ATOMIC_RELAXED) + / __atomic_load_n(&greads, __ATOMIC_RELAXED); rwc_perf_results->w_ks_r_hit_sp[m][n] = cycles_per_lookup; printf("Cycles per lookup: %llu\n", cycles_per_lookup); @@ -997,9 +986,6 @@ test_hash_add_ks_lookup_miss(struct rwc_perf *rwc_perf_results, int rwc_lf, int uint8_t write_type; uint8_t read_type = READ_FAIL; - rte_atomic64_init(&greads); - rte_atomic64_init(&gread_cycles); - if (init_params(rwc_lf, use_jhash, htm, ext_bkt) != 0) goto err; printf("\nTest: Hash add - key shift, Hash lookup - miss\n"); @@ -1015,8 +1001,8 @@ test_hash_add_ks_lookup_miss(struct rwc_perf *rwc_perf_results, int rwc_lf, int printf("\nNumber of readers: %u\n", rwc_core_cnt[n]); - rte_atomic64_clear(&greads); - rte_atomic64_clear(&gread_cycles); + __atomic_store_n(&greads, 0, __ATOMIC_RELAXED); + __atomic_store_n(&gread_cycles, 0, __ATOMIC_RELAXED); rte_hash_reset(tbl_rwc_test_param.h); writer_done = 0; @@ -1038,8 +1024,8 @@ test_hash_add_ks_lookup_miss(struct rwc_perf *rwc_perf_results, int rwc_lf, int goto err; unsigned long long cycles_per_lookup = - rte_atomic64_read(&gread_cycles) / - rte_atomic64_read(&greads); + __atomic_load_n(&gread_cycles, __ATOMIC_RELAXED) + / __atomic_load_n(&greads, __ATOMIC_RELAXED); rwc_perf_results->w_ks_r_miss[m][n] = cycles_per_lookup; printf("Cycles per lookup: %llu\n", cycles_per_lookup); } @@ -1071,9 +1057,6 @@ test_hash_multi_add_lookup(struct rwc_perf *rwc_perf_results, int rwc_lf, uint8_t write_type; uint8_t read_type = READ_PASS_SHIFT_PATH; - rte_atomic64_init(&greads); - rte_atomic64_init(&gread_cycles); - if (init_params(rwc_lf, use_jhash, htm, ext_bkt) != 0) goto err; printf("\nTest: Multi-add-lookup\n"); @@ -1098,8 +1081,9 @@ test_hash_multi_add_lookup(struct rwc_perf *rwc_perf_results, int rwc_lf, printf("\nNumber of readers: %u\n", rwc_core_cnt[n]); - rte_atomic64_clear(&greads); - rte_atomic64_clear(&gread_cycles); + __atomic_store_n(&greads, 0, __ATOMIC_RELAXED); + __atomic_store_n(&gread_cycles, 0, + __ATOMIC_RELAXED); rte_hash_reset(tbl_rwc_test_param.h); writer_done = 0; @@ -1138,8 +1122,10 @@ test_hash_multi_add_lookup(struct rwc_perf *rwc_perf_results, int rwc_lf, goto err; unsigned long long cycles_per_lookup = - rte_atomic64_read(&gread_cycles) - / rte_atomic64_read(&greads); + __atomic_load_n(&gread_cycles, + __ATOMIC_RELAXED) / + __atomic_load_n(&greads, + __ATOMIC_RELAXED); rwc_perf_results->multi_rw[m][k][n] = cycles_per_lookup; printf("Cycles per lookup: %llu\n", @@ -1172,9 +1158,6 @@ test_hash_add_ks_lookup_hit_extbkt(struct rwc_perf *rwc_perf_results, uint8_t write_type; uint8_t read_type = READ_PASS_KEY_SHIFTS_EXTBKT; - rte_atomic64_init(&greads); - rte_atomic64_init(&gread_cycles); - if (init_params(rwc_lf, use_jhash, htm, ext_bkt) != 0) goto err; printf("\nTest: Hash add - key-shifts, read - hit (ext_bkt)\n"); @@ -1190,8 +1173,8 @@ test_hash_add_ks_lookup_hit_extbkt(struct rwc_perf *rwc_perf_results, printf("\nNumber of readers: %u\n", rwc_core_cnt[n]); - rte_atomic64_clear(&greads); - rte_atomic64_clear(&gread_cycles); + __atomic_store_n(&greads, 0, __ATOMIC_RELAXED); + __atomic_store_n(&gread_cycles, 0, __ATOMIC_RELAXED); rte_hash_reset(tbl_rwc_test_param.h); write_type = WRITE_NO_KEY_SHIFT; @@ -1222,8 +1205,8 @@ test_hash_add_ks_lookup_hit_extbkt(struct rwc_perf *rwc_perf_results, goto err; unsigned long long cycles_per_lookup = - rte_atomic64_read(&gread_cycles) / - rte_atomic64_read(&greads); + __atomic_load_n(&gread_cycles, __ATOMIC_RELAXED) + / __atomic_load_n(&greads, __ATOMIC_RELAXED); rwc_perf_results->w_ks_r_hit_extbkt[m][n] = cycles_per_lookup; printf("Cycles per lookup: %llu\n", cycles_per_lookup); From patchwork Fri Oct 16 17:38:58 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dharmik Thakkar X-Patchwork-Id: 81161 X-Patchwork-Delegate: david.marchand@redhat.com Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 65163A04DB; Fri, 16 Oct 2020 19:39:45 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 0B3ECC910; Fri, 16 Oct 2020 19:39:16 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by dpdk.org (Postfix) with ESMTP id AF305C904 for ; Fri, 16 Oct 2020 19:39:12 +0200 (CEST) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 2C5F1143D; Fri, 16 Oct 2020 10:39:11 -0700 (PDT) Received: from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com [10.118.12.95]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 20F3A3F802; Fri, 16 Oct 2020 10:39:11 -0700 (PDT) From: Dharmik Thakkar To: Yipeng Wang , Sameh Gobriel , Bruce Richardson Cc: dev@dpdk.org, nd@arm.com, Dharmik Thakkar Date: Fri, 16 Oct 2020 12:38:58 -0500 Message-Id: <20201016173858.1134-4-dharmik.thakkar@arm.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20201016173858.1134-1-dharmik.thakkar@arm.com> References: <20200819040537.1792-1-dharmik.thakkar@arm.com> <20201016173858.1134-1-dharmik.thakkar@arm.com> Subject: [dpdk-dev] [PATCH v3 3/3] test/hash: add tests for integrated RCU QSBR X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Add functional and performance tests for the integrated RCU QSBR. Suggested-by: Honnappa Nagarahalli Signed-off-by: Dharmik Thakkar Reviewed-by: Ruifeng Wang --- app/test/test_hash.c | 390 ++++++++++++++++++++++++- app/test/test_hash_readwrite_lf_perf.c | 171 ++++++++++- 2 files changed, 557 insertions(+), 4 deletions(-) diff --git a/app/test/test_hash.c b/app/test/test_hash.c index 990a1815f893..22b47b3e7728 100644 --- a/app/test/test_hash.c +++ b/app/test/test_hash.c @@ -52,7 +52,7 @@ static uint32_t hashtest_key_lens[] = {0, 2, 4, 5, 6, 7, 8, 10, 11, 15, 16, 21, } \ } while(0) -#define RETURN_IF_ERROR_FBK(cond, str, ...) do { \ +#define RETURN_IF_ERROR_FBK(cond, str, ...) do { \ if (cond) { \ printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \ if (handle) rte_fbk_hash_free(handle); \ @@ -60,6 +60,20 @@ static uint32_t hashtest_key_lens[] = {0, 2, 4, 5, 6, 7, 8, 10, 11, 15, 16, 21, } \ } while(0) +#define RETURN_IF_ERROR_RCU_QSBR(cond, str, ...) do { \ + if (cond) { \ + printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \ + if (rcu_cfg.mode == RTE_HASH_QSBR_MODE_SYNC) { \ + writer_done = 1; \ + /* Wait until reader exited. */ \ + rte_eal_mp_wait_lcore(); \ + } \ + if (g_handle) rte_hash_free(g_handle); \ + if (g_qsv) rte_free(g_qsv); \ + return -1; \ + } \ +} while(0) + /* 5-tuple key type */ struct flow_key { uint32_t ip_src; @@ -1801,6 +1815,365 @@ test_hash_add_delete_jhash_3word(void) return ret; } +static struct rte_hash *g_handle; +static struct rte_rcu_qsbr *g_qsv; +static volatile uint8_t writer_done; +struct flow_key g_rand_keys[9]; +/* + * rte_hash_rcu_qsbr_add positive and negative tests. + * - Add RCU QSBR variable to Hash + * - Add another RCU QSBR variable to Hash + * - Check returns + */ +static int +test_hash_rcu_qsbr_add(void) +{ + size_t sz; + struct rte_rcu_qsbr *qsv2 = NULL; + int32_t status; + struct rte_hash_rcu_config rcu_cfg = {0}; + + struct rte_hash_parameters params; + + printf("\n# Running RCU QSBR add tests\n"); + memcpy(¶ms, &ut_params, sizeof(params)); + params.name = "test_hash_rcu_qsbr_add"; + params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF | + RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD; + g_handle = rte_hash_create(¶ms); + RETURN_IF_ERROR_RCU_QSBR(g_handle == NULL, "Hash creation failed"); + + /* Create RCU QSBR variable */ + sz = rte_rcu_qsbr_get_memsize(RTE_MAX_LCORE); + g_qsv = (struct rte_rcu_qsbr *)rte_zmalloc_socket(NULL, sz, + RTE_CACHE_LINE_SIZE, SOCKET_ID_ANY); + RETURN_IF_ERROR_RCU_QSBR(g_qsv == NULL, + "RCU QSBR variable creation failed"); + + status = rte_rcu_qsbr_init(g_qsv, RTE_MAX_LCORE); + RETURN_IF_ERROR_RCU_QSBR(status != 0, + "RCU QSBR variable initialization failed"); + + rcu_cfg.v = g_qsv; + /* Invalid QSBR mode */ + rcu_cfg.mode = 2; + status = rte_hash_rcu_qsbr_add(g_handle, &rcu_cfg); + RETURN_IF_ERROR_RCU_QSBR(status == 0, "Invalid QSBR mode test failed"); + + rcu_cfg.mode = RTE_HASH_QSBR_MODE_DQ; + /* Attach RCU QSBR to hash table */ + status = rte_hash_rcu_qsbr_add(g_handle, &rcu_cfg); + RETURN_IF_ERROR_RCU_QSBR(status != 0, + "Attach RCU QSBR to hash table failed"); + + /* Create and attach another RCU QSBR to hash table */ + qsv2 = (struct rte_rcu_qsbr *)rte_zmalloc_socket(NULL, sz, + RTE_CACHE_LINE_SIZE, SOCKET_ID_ANY); + RETURN_IF_ERROR_RCU_QSBR(qsv2 == NULL, + "RCU QSBR variable creation failed"); + + rcu_cfg.v = qsv2; + rcu_cfg.mode = RTE_HASH_QSBR_MODE_SYNC; + status = rte_hash_rcu_qsbr_add(g_handle, &rcu_cfg); + rte_free(qsv2); + RETURN_IF_ERROR_RCU_QSBR(status == 0, + "Attach RCU QSBR to hash table succeeded where failure" + " is expected"); + + rte_hash_free(g_handle); + rte_free(g_qsv); + + return 0; +} + +/* + * rte_hash_rcu_qsbr_add DQ mode functional test. + * Reader and writer are in the same thread in this test. + * - Create hash which supports maximum 8 (9 if ext bkt is enabled) entries + * - Add RCU QSBR variable to hash + * - Add 8 hash entries and fill the bucket + * - If ext bkt is enabled, add 1 extra entry that is available in the ext bkt + * - Register a reader thread (not a real thread) + * - Reader lookup existing entry + * - Writer deletes the entry + * - Reader lookup the entry + * - Writer re-add the entry (no available free index) + * - Reader report quiescent state and unregister + * - Writer re-add the entry + * - Reader lookup the entry + */ +static int +test_hash_rcu_qsbr_dq_mode(uint8_t ext_bkt) +{ + uint32_t total_entries = (ext_bkt == 0) ? 8 : 9; + + uint8_t hash_extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF; + + if (ext_bkt) + hash_extra_flag |= RTE_HASH_EXTRA_FLAGS_EXT_TABLE; + + struct rte_hash_parameters params_pseudo_hash = { + .name = "test_hash_rcu_qsbr_dq_mode", + .entries = total_entries, + .key_len = sizeof(struct flow_key), /* 13 */ + .hash_func = pseudo_hash, + .hash_func_init_val = 0, + .socket_id = 0, + .extra_flag = hash_extra_flag, + }; + int pos[total_entries]; + int expected_pos[total_entries]; + unsigned i; + size_t sz; + int32_t status; + struct rte_hash_rcu_config rcu_cfg = {0}; + + g_qsv = NULL; + g_handle = NULL; + + for (i = 0; i < total_entries; i++) { + g_rand_keys[i].port_dst = i; + g_rand_keys[i].port_src = i+1; + } + + if (ext_bkt) + printf("\n# Running RCU QSBR DQ mode functional test with" + " ext bkt\n"); + else + printf("\n# Running RCU QSBR DQ mode functional test\n"); + + g_handle = rte_hash_create(¶ms_pseudo_hash); + RETURN_IF_ERROR_RCU_QSBR(g_handle == NULL, "Hash creation failed"); + + /* Create RCU QSBR variable */ + sz = rte_rcu_qsbr_get_memsize(RTE_MAX_LCORE); + g_qsv = (struct rte_rcu_qsbr *)rte_zmalloc_socket(NULL, sz, + RTE_CACHE_LINE_SIZE, SOCKET_ID_ANY); + RETURN_IF_ERROR_RCU_QSBR(g_qsv == NULL, + "RCU QSBR variable creation failed"); + + status = rte_rcu_qsbr_init(g_qsv, RTE_MAX_LCORE); + RETURN_IF_ERROR_RCU_QSBR(status != 0, + "RCU QSBR variable initialization failed"); + + rcu_cfg.v = g_qsv; + rcu_cfg.mode = RTE_HASH_QSBR_MODE_DQ; + /* Attach RCU QSBR to hash table */ + status = rte_hash_rcu_qsbr_add(g_handle, &rcu_cfg); + RETURN_IF_ERROR_RCU_QSBR(status != 0, + "Attach RCU QSBR to hash table failed"); + + /* Fill bucket */ + for (i = 0; i < total_entries; i++) { + pos[i] = rte_hash_add_key(g_handle, &g_rand_keys[i]); + print_key_info("Add", &g_rand_keys[i], pos[i]); + RETURN_IF_ERROR_RCU_QSBR(pos[i] < 0, + "failed to add key (pos[%u]=%d)", i, + pos[i]); + expected_pos[i] = pos[i]; + } + + /* Register pseudo reader */ + status = rte_rcu_qsbr_thread_register(g_qsv, 0); + RETURN_IF_ERROR_RCU_QSBR(status != 0, + "RCU QSBR thread registration failed"); + rte_rcu_qsbr_thread_online(g_qsv, 0); + + /* Lookup */ + pos[0] = rte_hash_lookup(g_handle, &g_rand_keys[0]); + print_key_info("Lkp", &g_rand_keys[0], pos[0]); + RETURN_IF_ERROR_RCU_QSBR(pos[0] != expected_pos[0], + "failed to find correct key (pos[%u]=%d)", 0, + pos[0]); + + /* Writer update */ + pos[0] = rte_hash_del_key(g_handle, &g_rand_keys[0]); + print_key_info("Del", &g_rand_keys[0], pos[0]); + RETURN_IF_ERROR_RCU_QSBR(pos[0] != expected_pos[0], + "failed to del correct key (pos[%u]=%d)", 0, + pos[0]); + + /* Lookup */ + pos[0] = rte_hash_lookup(g_handle, &g_rand_keys[0]); + print_key_info("Lkp", &g_rand_keys[0], pos[0]); + RETURN_IF_ERROR_RCU_QSBR(pos[0] != -ENOENT, + "found deleted key (pos[%u]=%d)", 0, pos[0]); + + /* Fill bucket */ + pos[0] = rte_hash_add_key(g_handle, &g_rand_keys[0]); + print_key_info("Add", &g_rand_keys[0], pos[0]); + RETURN_IF_ERROR_RCU_QSBR(pos[0] != -ENOSPC, + "Added key successfully (pos[%u]=%d)", 0, pos[0]); + + /* Reader quiescent */ + rte_rcu_qsbr_quiescent(g_qsv, 0); + + /* Fill bucket */ + pos[0] = rte_hash_add_key(g_handle, &g_rand_keys[0]); + print_key_info("Add", &g_rand_keys[0], pos[0]); + RETURN_IF_ERROR_RCU_QSBR(pos[0] < 0, + "failed to add key (pos[%u]=%d)", 0, pos[0]); + expected_pos[0] = pos[0]; + + rte_rcu_qsbr_thread_offline(g_qsv, 0); + (void)rte_rcu_qsbr_thread_unregister(g_qsv, 0); + + /* Lookup */ + pos[0] = rte_hash_lookup(g_handle, &g_rand_keys[0]); + print_key_info("Lkp", &g_rand_keys[0], pos[0]); + RETURN_IF_ERROR_RCU_QSBR(pos[0] != expected_pos[0], + "failed to find correct key (pos[%u]=%d)", 0, + pos[0]); + + rte_hash_free(g_handle); + rte_free(g_qsv); + return 0; + +} + +/* Report quiescent state interval every 1024 lookups. Larger critical + * sections in reader will result in writer polling multiple times. + */ +#define QSBR_REPORTING_INTERVAL 1024 +#define WRITER_ITERATIONS 512 + +/* + * Reader thread using rte_hash data structure with RCU. + */ +static int +test_hash_rcu_qsbr_reader(void *arg) +{ + int i; + + RTE_SET_USED(arg); + /* Register this thread to report quiescent state */ + (void)rte_rcu_qsbr_thread_register(g_qsv, 0); + rte_rcu_qsbr_thread_online(g_qsv, 0); + + do { + for (i = 0; i < QSBR_REPORTING_INTERVAL; i++) + rte_hash_lookup(g_handle, &g_rand_keys[0]); + + /* Update quiescent state */ + rte_rcu_qsbr_quiescent(g_qsv, 0); + } while (!writer_done); + + rte_rcu_qsbr_thread_offline(g_qsv, 0); + (void)rte_rcu_qsbr_thread_unregister(g_qsv, 0); + + return 0; +} + +/* + * rte_hash_rcu_qsbr_add sync mode functional test. + * 1 Reader and 1 writer. They cannot be in the same thread in this test. + * - Create hash which supports maximum 8 (9 if ext bkt is enabled) entries + * - Add RCU QSBR variable to hash + * - Register a reader thread. Reader keeps looking up a specific key. + * - Writer keeps adding and deleting a specific key. + */ +static int +test_hash_rcu_qsbr_sync_mode(uint8_t ext_bkt) +{ + uint32_t total_entries = (ext_bkt == 0) ? 8 : 9; + + uint8_t hash_extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF; + + if (ext_bkt) + hash_extra_flag |= RTE_HASH_EXTRA_FLAGS_EXT_TABLE; + + struct rte_hash_parameters params_pseudo_hash = { + .name = "test_hash_rcu_qsbr_sync_mode", + .entries = total_entries, + .key_len = sizeof(struct flow_key), /* 13 */ + .hash_func = pseudo_hash, + .hash_func_init_val = 0, + .socket_id = 0, + .extra_flag = hash_extra_flag, + }; + int pos[total_entries]; + int expected_pos[total_entries]; + unsigned i; + size_t sz; + int32_t status; + struct rte_hash_rcu_config rcu_cfg = {0}; + + g_qsv = NULL; + g_handle = NULL; + + for (i = 0; i < total_entries; i++) { + g_rand_keys[i].port_dst = i; + g_rand_keys[i].port_src = i+1; + } + + if (ext_bkt) + printf("\n# Running RCU QSBR sync mode functional test with" + " ext bkt\n"); + else + printf("\n# Running RCU QSBR sync mode functional test\n"); + + g_handle = rte_hash_create(¶ms_pseudo_hash); + RETURN_IF_ERROR_RCU_QSBR(g_handle == NULL, "Hash creation failed"); + + /* Create RCU QSBR variable */ + sz = rte_rcu_qsbr_get_memsize(RTE_MAX_LCORE); + g_qsv = (struct rte_rcu_qsbr *)rte_zmalloc_socket(NULL, sz, + RTE_CACHE_LINE_SIZE, SOCKET_ID_ANY); + RETURN_IF_ERROR_RCU_QSBR(g_qsv == NULL, + "RCU QSBR variable creation failed"); + + status = rte_rcu_qsbr_init(g_qsv, RTE_MAX_LCORE); + RETURN_IF_ERROR_RCU_QSBR(status != 0, + "RCU QSBR variable initialization failed"); + + rcu_cfg.v = g_qsv; + rcu_cfg.mode = RTE_HASH_QSBR_MODE_SYNC; + /* Attach RCU QSBR to hash table */ + status = rte_hash_rcu_qsbr_add(g_handle, &rcu_cfg); + RETURN_IF_ERROR_RCU_QSBR(status != 0, + "Attach RCU QSBR to hash table failed"); + + /* Launch reader thread */ + rte_eal_remote_launch(test_hash_rcu_qsbr_reader, NULL, + rte_get_next_lcore(-1, 1, 0)); + + /* Fill bucket */ + for (i = 0; i < total_entries; i++) { + pos[i] = rte_hash_add_key(g_handle, &g_rand_keys[i]); + print_key_info("Add", &g_rand_keys[i], pos[i]); + RETURN_IF_ERROR_RCU_QSBR(pos[i] < 0, + "failed to add key (pos[%u]=%d)", i, pos[i]); + expected_pos[i] = pos[i]; + } + writer_done = 0; + + /* Writer Update */ + for (i = 0; i < WRITER_ITERATIONS; i++) { + expected_pos[0] = pos[0]; + pos[0] = rte_hash_del_key(g_handle, &g_rand_keys[0]); + print_key_info("Del", &g_rand_keys[0], status); + RETURN_IF_ERROR_RCU_QSBR(pos[0] != expected_pos[0], + "failed to del correct key (pos[%u]=%d)" + , 0, pos[0]); + + pos[0] = rte_hash_add_key(g_handle, &g_rand_keys[0]); + print_key_info("Add", &g_rand_keys[0], pos[0]); + RETURN_IF_ERROR_RCU_QSBR(pos[0] < 0, + "failed to add key (pos[%u]=%d)", 0, + pos[0]); + } + + writer_done = 1; + /* Wait until reader exited. */ + rte_eal_mp_wait_lcore(); + + rte_hash_free(g_handle); + rte_free(g_qsv); + + return 0; + +} + /* * Do all unit and performance tests. */ @@ -1862,6 +2235,21 @@ test_hash(void) if (test_crc32_hash_alg_equiv() < 0) return -1; + if (test_hash_rcu_qsbr_add() < 0) + return -1; + + if (test_hash_rcu_qsbr_dq_mode(0) < 0) + return -1; + + if (test_hash_rcu_qsbr_dq_mode(1) < 0) + return -1; + + if (test_hash_rcu_qsbr_sync_mode(0) < 0) + return -1; + + if (test_hash_rcu_qsbr_sync_mode(1) < 0) + return -1; + return 0; } diff --git a/app/test/test_hash_readwrite_lf_perf.c b/app/test/test_hash_readwrite_lf_perf.c index 328fa5116f65..3c278ee97c23 100644 --- a/app/test/test_hash_readwrite_lf_perf.c +++ b/app/test/test_hash_readwrite_lf_perf.c @@ -13,6 +13,7 @@ #include #include #include +#include #include "test.h" @@ -48,6 +49,9 @@ #define WRITE_EXT_BKT 2 #define NUM_TEST 3 + +#define QSBR_REPORTING_INTERVAL 1024 + static unsigned int rwc_core_cnt[NUM_TEST] = {1, 2, 4}; struct rwc_perf { @@ -58,6 +62,7 @@ struct rwc_perf { uint32_t w_ks_r_miss[2][NUM_TEST]; uint32_t multi_rw[NUM_TEST - 1][2][NUM_TEST]; uint32_t w_ks_r_hit_extbkt[2][NUM_TEST]; + uint32_t writer_add_del[NUM_TEST]; }; static struct rwc_perf rwc_lf_results, rwc_non_lf_results; @@ -84,6 +89,8 @@ static struct { static uint64_t gread_cycles; static uint64_t greads; +static uint64_t gwrite_cycles; +static uint64_t gwrites; static volatile uint8_t writer_done; @@ -1044,7 +1051,7 @@ test_hash_add_ks_lookup_miss(struct rwc_perf *rwc_perf_results, int rwc_lf, int /* * Test lookup perf for multi-writer: * Reader(s) lookup keys present in the table and likely on the shift-path while - * Writers add keys causing key-shiftsi. + * Writers add keys causing key-shifts. * Writers are running in parallel, on different data plane cores. */ static int @@ -1223,6 +1230,163 @@ test_hash_add_ks_lookup_hit_extbkt(struct rwc_perf *rwc_perf_results, return -1; } +static struct rte_rcu_qsbr *rv; + +/* + * Reader thread using rte_hash data structure with RCU + */ +static int +test_hash_rcu_qsbr_reader(void *arg) +{ + unsigned int i, j; + uint32_t num_keys = tbl_rwc_test_param.count_keys_no_ks + - QSBR_REPORTING_INTERVAL; + uint32_t *keys = tbl_rwc_test_param.keys_no_ks; + uint32_t lcore_id = rte_lcore_id(); + RTE_SET_USED(arg); + + (void)rte_rcu_qsbr_thread_register(rv, lcore_id); + rte_rcu_qsbr_thread_online(rv, lcore_id); + do { + for (i = 0; i < num_keys; i += j) { + for (j = 0; j < QSBR_REPORTING_INTERVAL; j++) + rte_hash_lookup(tbl_rwc_test_param.h, + keys + i + j); + /* Update quiescent state counter */ + rte_rcu_qsbr_quiescent(rv, lcore_id); + } + } while (!writer_done); + rte_rcu_qsbr_thread_offline(rv, lcore_id); + (void)rte_rcu_qsbr_thread_unregister(rv, lcore_id); + + return 0; +} + +/* + * Writer thread using rte_hash data structure with RCU + */ +static int +test_hash_rcu_qsbr_writer(void *arg) +{ + uint32_t i, offset; + uint64_t begin, cycles; + uint8_t pos_core = (uint32_t)((uintptr_t)arg); + offset = pos_core * tbl_rwc_test_param.single_insert; + + begin = rte_rdtsc_precise(); + for (i = offset; i < offset + tbl_rwc_test_param.single_insert; i++) { + /* Delete element from the shared data structure */ + rte_hash_del_key(tbl_rwc_test_param.h, + tbl_rwc_test_param.keys_no_ks + i); + rte_hash_add_key(tbl_rwc_test_param.h, + tbl_rwc_test_param.keys_no_ks + i); + } + cycles = rte_rdtsc_precise() - begin; + __atomic_fetch_add(&gwrite_cycles, cycles, __ATOMIC_RELAXED); + __atomic_fetch_add(&gwrites, tbl_rwc_test_param.single_insert, + __ATOMIC_RELAXED); + return 0; +} + +/* + * Writer perf test with RCU QSBR in DQ mode: + * Writer(s) delete and add keys in the table. + * Readers lookup keys in the hash table + */ +static int +test_hash_rcu_qsbr_writer_perf(struct rwc_perf *rwc_perf_results, int rwc_lf, + int htm, int ext_bkt) +{ + unsigned int n; + uint64_t i; + uint8_t write_type; + int use_jhash = 0; + struct rte_hash_rcu_config rcu_config = {0}; + uint32_t sz; + uint8_t pos_core; + + printf("\nTest: Writer perf with integrated RCU\n"); + + if (init_params(rwc_lf, use_jhash, htm, ext_bkt) != 0) + goto err; + + sz = rte_rcu_qsbr_get_memsize(RTE_MAX_LCORE); + rv = (struct rte_rcu_qsbr *)rte_zmalloc(NULL, sz, RTE_CACHE_LINE_SIZE); + rcu_config.v = rv; + + if (rte_hash_rcu_qsbr_add(tbl_rwc_test_param.h, &rcu_config) < 0) { + printf("RCU init in hash failed\n"); + goto err; + } + + for (n = 0; n < NUM_TEST; n++) { + unsigned int tot_lcore = rte_lcore_count(); + if (tot_lcore < rwc_core_cnt[n] + 3) + goto finish; + + /* Calculate keys added by each writer */ + tbl_rwc_test_param.single_insert = + tbl_rwc_test_param.count_keys_no_ks / + rwc_core_cnt[n]; + printf("\nNumber of writers: %u\n", rwc_core_cnt[n]); + + __atomic_store_n(&gwrites, 0, __ATOMIC_RELAXED); + __atomic_store_n(&gwrite_cycles, 0, __ATOMIC_RELAXED); + + rte_hash_reset(tbl_rwc_test_param.h); + rte_rcu_qsbr_init(rv, RTE_MAX_LCORE); + + write_type = WRITE_NO_KEY_SHIFT; + if (write_keys(write_type) < 0) + goto err; + write_type = WRITE_KEY_SHIFT; + if (write_keys(write_type) < 0) + goto err; + + /* Launch 2 readers */ + for (i = 1; i <= 2; i++) + rte_eal_remote_launch(test_hash_rcu_qsbr_reader, NULL, + enabled_core_ids[i]); + pos_core = 0; + /* Launch writer(s) */ + for (; i <= rwc_core_cnt[n] + 2; i++) { + rte_eal_remote_launch(test_hash_rcu_qsbr_writer, + (void *)(uintptr_t)pos_core, + enabled_core_ids[i]); + pos_core++; + } + + /* Wait for writers to complete */ + for (i = 3; i <= rwc_core_cnt[n] + 2; i++) + rte_eal_wait_lcore(enabled_core_ids[i]); + + writer_done = 1; + + /* Wait for readers to complete */ + rte_eal_mp_wait_lcore(); + + unsigned long long cycles_per_write_operation = + __atomic_load_n(&gwrite_cycles, __ATOMIC_RELAXED) / + __atomic_load_n(&gwrites, __ATOMIC_RELAXED); + rwc_perf_results->writer_add_del[n] + = cycles_per_write_operation; + printf("Cycles per write operation: %llu\n", + cycles_per_write_operation); + } + +finish: + rte_hash_free(tbl_rwc_test_param.h); + rte_free(rv); + return 0; + +err: + writer_done = 1; + rte_eal_mp_wait_lcore(); + rte_hash_free(tbl_rwc_test_param.h); + rte_free(rv); + return -1; +} + static int test_hash_readwrite_lf_perf_main(void) { @@ -1235,7 +1399,6 @@ test_hash_readwrite_lf_perf_main(void) int rwc_lf = 0; int htm; int ext_bkt = 0; - if (rte_lcore_count() < 2) { printf("Not enough cores for hash_readwrite_lf_perf_autotest, expecting at least 2\n"); return TEST_SKIPPED; @@ -1255,7 +1418,6 @@ test_hash_readwrite_lf_perf_main(void) return -1; if (get_enabled_cores_list() != 0) return -1; - if (RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) { rwc_lf = 1; ext_bkt = 1; @@ -1282,6 +1444,9 @@ test_hash_readwrite_lf_perf_main(void) if (test_hash_add_ks_lookup_hit_extbkt(&rwc_lf_results, rwc_lf, htm, ext_bkt) < 0) return -1; + if (test_hash_rcu_qsbr_writer_perf(&rwc_lf_results, rwc_lf, + htm, ext_bkt) < 0) + return -1; } printf("\nTest lookup with read-write concurrency lock free support" " disabled\n");