From patchwork Thu Sep 6 17:12:18 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 146119 Delivered-To: patch@linaro.org Received: by 2002:a2e:1648:0:0:0:0:0 with SMTP id 8-v6csp126797ljw; Thu, 6 Sep 2018 10:13:14 -0700 (PDT) X-Google-Smtp-Source: ANB0VdYDGwYqEw5Qiba/Z68AHp2b9nyM3Nvj8+rOhSJghp6pg/rSMIqkYTMLNyRo+CvALgVlYI7Y X-Received: by 2002:adf:ac6a:: with SMTP id v97-v6mr2957067wrc.7.1536253994506; Thu, 06 Sep 2018 10:13:14 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1536253994; cv=none; d=google.com; s=arc-20160816; b=Y0e8Qv/glZFK94OdI3yB+3H65EBxtD++7nJd0+ZQiisLbpQJIcBrMiv9XMoB/drcGY RUWYMrcVbj/FvvqEk64fqi0sq7fsIJPRg0AUsiHjTgoW6/6zen9gsNr3Zwi0D0yPZT3o msisuXnGqc85i5cVLtz47Vc9J3fA7CffvIYuLQxBIwbO+6MAs6dXi5CJfk6gOxs9GU2D DUkW219ozMS747n+PnhwH7ktpgog+DbheSeKds9Bp8IwsbvJruerR6rhC6zKojMPHum4 k3Nr8ftpO9VYXiwY8ImLeha7Ncu4AZ7wyHbI30ybiMGLKVT8HdTB/HerNupCi2xrp3wQ KkrA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:subject:references:in-reply-to :message-id:date:cc:to:from; bh=W6QeF1oK53CUIL7vtGza9tYGYNnJKGlNz4hKUAthlVk=; b=QJfr9LRyD8WEs2W47MK3swfGj9zhIOVo5Z7SH6n//a6J2fU9xLEM/eIwCS4UP6Bngf F729rTmY8QgOGfXqiXCXdeReDWbM7vTgqPrFRSdm0ufGelXpcIQmfJoOvpNxOzx4TAXA nazBDxjFh92JRH/XeHbOv4Qh3FvhjleZB9Wfpr1mBrVu/jC/4wDYhYYEffgeF5fsSjpg 5u93PyQlS0Wc4Abt7SA9/SXaHZ0Jw/GOz6VrA4CXUoz2e2OaiI80i7MpFRFucJO7l8S/ ry7dvxORdXZWKZlIttgey6NptGiToCNcVQJCb62T0YsCKf8GtpwcPeE9aZ0hFGVk933B 3wdg== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) smtp.mailfrom=dev-bounces@dpdk.org Return-Path: Received: from dpdk.org (dpdk.org. [92.243.14.124]) by mx.google.com with ESMTP id d12-v6si5482405wrn.105.2018.09.06.10.13.14; Thu, 06 Sep 2018 10:13:14 -0700 (PDT) Received-SPF: pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) client-ip=92.243.14.124; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) smtp.mailfrom=dev-bounces@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id BD344532C; Thu, 6 Sep 2018 19:12:37 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id CB1DE4CBB for ; Thu, 6 Sep 2018 19:12:35 +0200 (CEST) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 490FD7A9; Thu, 6 Sep 2018 10:12:35 -0700 (PDT) Received: from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com [10.118.12.164]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id CE8D63F557; Thu, 6 Sep 2018 10:12:34 -0700 (PDT) From: Honnappa Nagarahalli To: bruce.richardson@intel.com, pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org, honnappa.nagarahalli@dpdk.org, gavin.hu@arm.com, steve.capper@arm.com, ola.liljedahl@arm.com, nd@arm.com, Honnappa Nagarahalli Date: Thu, 6 Sep 2018 12:12:18 -0500 Message-Id: <1536253938-192391-5-git-send-email-honnappa.nagarahalli@arm.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1536253938-192391-1-git-send-email-honnappa.nagarahalli@arm.com> References: <1536253938-192391-1-git-send-email-honnappa.nagarahalli@arm.com> Subject: [dpdk-dev] [PATCH 4/4] hash: enable lock-free reader-writer concurrency 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 the flag to enable reader-writer concurrency during run time. The rte_hash_del_xxx APIs do not free the keystore element when this flag is enabled. Hence a new API, rte_hash_free_key_with_position, to free the key store element is added. Signed-off-by: Honnappa Nagarahalli Reviewed-by: Gavin Hu Reviewed-by: Ola Liljedahl Reviewed-by: Steve Capper --- lib/librte_hash/rte_cuckoo_hash.c | 105 ++++++++++++++++++++++++++--------- lib/librte_hash/rte_cuckoo_hash.h | 2 + lib/librte_hash/rte_hash.h | 55 ++++++++++++++++++ lib/librte_hash/rte_hash_version.map | 7 +++ 4 files changed, 142 insertions(+), 27 deletions(-) -- 2.7.4 diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 1e4a8d4..bf51a73 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -93,6 +93,7 @@ rte_hash_create(const struct rte_hash_parameters *params) unsigned i; unsigned int hw_trans_mem_support = 0, multi_writer_support = 0; unsigned int readwrite_concur_support = 0; + unsigned int readwrite_concur_lf_support = 0; rte_hash_function default_hash_func = (rte_hash_function)rte_jhash; @@ -124,6 +125,9 @@ rte_hash_create(const struct rte_hash_parameters *params) multi_writer_support = 1; } + if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) + readwrite_concur_lf_support = 1; + /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */ if (multi_writer_support) /* @@ -272,6 +276,7 @@ rte_hash_create(const struct rte_hash_parameters *params) h->hw_trans_mem_support = hw_trans_mem_support; h->multi_writer_support = multi_writer_support; h->readwrite_concur_support = readwrite_concur_support; + h->readwrite_concur_lf_support = readwrite_concur_lf_support; #if defined(RTE_ARCH_X86) if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2)) @@ -647,19 +652,21 @@ rte_hash_cuckoo_move_insert_mw(struct rte_hash *h, return -1; } - /* Inform the previous move. The current move need - * not be informed now as the current bucket entry - * is present in both primary and secondary. - * Since there is one writer, load acquires on - * tbl_chng_cnt are not required. - */ - __atomic_store_n(&h->tbl_chng_cnt, - h->tbl_chng_cnt + 1, - __ATOMIC_RELEASE); - /* The stores to sig_alt and sig_current should not - * move above the store to tbl_chng_cnt. - */ - __atomic_thread_fence(__ATOMIC_RELEASE); + if (h->readwrite_concur_lf_support) { + /* Inform the previous move. The current move need + * not be informed now as the current bucket entry + * is present in both primary and secondary. + * Since there is one writer, load acquires on + * tbl_chng_cnt are not required. + */ + __atomic_store_n(&h->tbl_chng_cnt, + h->tbl_chng_cnt + 1, + __ATOMIC_RELEASE); + /* The stores to sig_alt and sig_current should not + * move above the store to tbl_chng_cnt. + */ + __atomic_thread_fence(__ATOMIC_RELEASE); + } /* Need to swap current/alt sig to allow later * Cuckoo insert to move elements back to its @@ -679,19 +686,21 @@ rte_hash_cuckoo_move_insert_mw(struct rte_hash *h, curr_bkt = curr_node->bkt; } - /* Inform the previous move. The current move need - * not be informed now as the current bucket entry - * is present in both primary and secondary. - * Since there is one writer, load acquires on - * tbl_chng_cnt are not required. - */ - __atomic_store_n(&h->tbl_chng_cnt, - h->tbl_chng_cnt + 1, - __ATOMIC_RELEASE); - /* The stores to sig_alt and sig_current should not - * move above the store to tbl_chng_cnt. - */ - __atomic_thread_fence(__ATOMIC_RELEASE); + if (h->readwrite_concur_lf_support) { + /* Inform the previous move. The current move need + * not be informed now as the current bucket entry + * is present in both primary and secondary. + * Since there is one writer, load acquires on + * tbl_chng_cnt are not required. + */ + __atomic_store_n(&h->tbl_chng_cnt, + h->tbl_chng_cnt + 1, + __ATOMIC_RELEASE); + /* The stores to sig_alt and sig_current should not + * move above the store to tbl_chng_cnt. + */ + __atomic_thread_fence(__ATOMIC_RELEASE); + } curr_bkt->sig_current[curr_slot] = sig; curr_bkt->sig_alt[curr_slot] = alt_hash; @@ -1090,7 +1099,12 @@ search_and_remove(const struct rte_hash *h, const void *key, k = (struct rte_hash_key *) ((char *)keys + key_idx * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { - remove_entry(h, bkt, i); + /* Do not free the key store element if + * lock-free concurrency is enabled as + * readers might still be using it. + */ + if (!h->readwrite_concur_lf_support) + remove_entry(h, bkt, i); __atomic_store_n(&bkt->key_idx[i], EMPTY_SLOT, @@ -1177,6 +1191,43 @@ rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position, return 0; } +int __rte_experimental +rte_hash_free_key_with_position(const struct rte_hash *h, + const int32_t position) +{ + RETURN_IF_TRUE(((h == NULL) || (position == EMPTY_SLOT)), -EINVAL); + + unsigned int lcore_id, n_slots; + struct lcore_cache *cached_free_slots; + const int32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES; + + /* Out of bounds */ + if (position >= total_entries) + return -EINVAL; + + if (h->multi_writer_support) { + 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(h->free_slots, + cached_free_slots->objs, + LCORE_CACHE_SIZE, NULL); + cached_free_slots->len -= n_slots; + } + /* Put index of new free slot in cache. */ + cached_free_slots->objs[cached_free_slots->len] = + (void *)((uintptr_t)position); + cached_free_slots->len++; + } else { + rte_ring_sp_enqueue(h->free_slots, + (void *)((uintptr_t)position)); + } + + return 0; +} + static inline void compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches, const struct rte_hash_bucket *prim_bkt, diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index 5ce864c..08d67b8 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -168,6 +168,8 @@ struct rte_hash { /**< If multi-writer support is enabled. */ uint8_t readwrite_concur_support; /**< If read-write concurrency support is enabled */ + uint8_t readwrite_concur_lf_support; + /**< If read-write concurrency lock free support is enabled */ rte_hash_function hash_func; /**< Function used to calculate hash. */ uint32_t hash_func_init_val; /**< Init value used by hash_func. */ rte_hash_cmp_eq_t rte_hash_custom_cmp_eq; diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index 05e024b..7d7372e 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -14,6 +14,8 @@ #include #include +#include + #ifdef __cplusplus extern "C" { #endif @@ -37,6 +39,9 @@ extern "C" { /** Flag to support reader writer concurrency */ #define RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY 0x04 +/** Flag to support lock free reader writer concurrency */ +#define RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF 0x08 + /** Signature of key that is stored internally. */ typedef uint32_t hash_sig_t; @@ -143,6 +148,11 @@ rte_hash_count(const struct rte_hash *h); * and should only be called from one thread by default. * Thread safety can be enabled by setting flag during * table creation. + * When lock free reader writer concurrency is enabled, + * if this API is called to update an existing entry, + * the application should free any memory allocated for + * previous 'data' only after all the readers have stopped + * using previous 'data'. * * @param h * Hash table to add the key to. @@ -165,6 +175,11 @@ rte_hash_add_key_data(struct rte_hash *h, const void *key, void *data); * and should only be called from one thread by default. * Thread safety can be enabled by setting flag during * table creation. + * When lock free reader writer concurrency is enabled, + * if this API is called to update an existing entry, + * the application should free any memory allocated for + * previous 'data' only after all the readers have stopped + * using previous 'data'. * * @param h * Hash table to add the key to. @@ -230,6 +245,12 @@ rte_hash_add_key_with_hash(struct rte_hash *h, const void *key, hash_sig_t sig); * and should only be called from one thread by default. * Thread safety can be enabled by setting flag during * table creation. + * If lock free reader writer concurrency is enabled, + * the hash library's internal memory for the deleted + * key is not freed. It should be freed by calling + * rte_hash_free_key_with_position API after all + * the readers have stopped using the hash entry + * corresponding to this key. * * @param h * Hash table to remove the key from. @@ -241,6 +262,8 @@ rte_hash_add_key_with_hash(struct rte_hash *h, const void *key, hash_sig_t sig); * - A positive value that can be used by the caller as an offset into an * array of user data. This value is unique for this key, and is the same * value that was returned when the key was added. + * When lock free concurrency is enabled, this value should be used + * while calling the rte_hash_free_key_with_position API. */ int32_t rte_hash_del_key(const struct rte_hash *h, const void *key); @@ -251,6 +274,12 @@ rte_hash_del_key(const struct rte_hash *h, const void *key); * and should only be called from one thread by default. * Thread safety can be enabled by setting flag during * table creation. + * If lock free reader writer concurrency is enabled, + * the hash library's internal memory for the deleted + * key is not freed. It should be freed by calling + * rte_hash_free_key_with_position API after all + * the readers have stopped using the hash entry + * corresponding to this key. * * @param h * Hash table to remove the key from. @@ -264,6 +293,8 @@ rte_hash_del_key(const struct rte_hash *h, const void *key); * - A positive value that can be used by the caller as an offset into an * array of user data. This value is unique for this key, and is the same * value that was returned when the key was added. + * When lock free concurrency is enabled, this value should be used + * while calling the rte_hash_free_key_with_position API. */ int32_t rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig); @@ -290,6 +321,30 @@ rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position, void **key); /** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * Free hash library's internal memory given the position + * of the key. This operation is not multi-thread safe and should + * only be called from one thread by default. Thread safety + * can be enabled by setting flag during table creation. + * If lock free reader writer concurrency is enabled, + * the hash library's internal memory must be freed using this API + * after the key is deleted using rte_hash_del_key_xxx API. + * + * @param h + * Hash table to get the key from. + * @param position + * Position returned when the key was deleted. + * @return + * - 0 if freed successfully + * - -EINVAL if the parameters are invalid. + */ +int __rte_experimental +rte_hash_free_key_with_position(const struct rte_hash *h, + const int32_t position); + +/** * Find a key-value pair in the hash table. * This operation is multi-thread safe with regarding to other lookup threads. * Read-write concurrency can be enabled by setting flag during diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map index e216ac8..734ae28 100644 --- a/lib/librte_hash/rte_hash_version.map +++ b/lib/librte_hash/rte_hash_version.map @@ -53,3 +53,10 @@ DPDK_18.08 { rte_hash_count; } DPDK_16.07; + +EXPERIMENTAL { + global: + + rte_hash_free_key_with_position; + +};