From patchwork Wed Oct 24 01:32:23 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 149473 Delivered-To: patch@linaro.org Received: by 2002:a2e:299d:0:0:0:0:0 with SMTP id p29-v6csp1400832ljp; Tue, 23 Oct 2018 18:33:03 -0700 (PDT) X-Google-Smtp-Source: AJdET5dhOsQmMQuW1ZNqCsOmfD4TACX6OrfQZ9s77yk2hs+sl94ldLQHp6NhsoGZHsVN9AK8Yj4b X-Received: by 2002:a5d:4c84:: with SMTP id z4-v6mr572813wrs.75.1540344783459; Tue, 23 Oct 2018 18:33:03 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1540344783; cv=none; d=google.com; s=arc-20160816; b=umAX75xNRerjBG9s30OrzZOXIYrfIGzsZTXWRkcEKd9H8STwjoGn2uaw1FcuCHWZtJ bt01LVpfgl0XEgHAPnzqn8ZI+Rd92DA63yGO/6RHqn8JF/YUdBZ3kr0vNGbqzuOneFCC tkX8ItIujOK9YuCLcK8DZ7nQq2eJ72nIGZrW52OlLE1NuSnxNeAwaSVjWoQDvYAnxGtM SgxINLJScLbzdDngkh5FHoTAUs0IUy0M2C5Kx3lGXicx7pNAzb8mhljhGGyT+nLffln3 DET5uvdIVi3GBjblIMdyao23okDFsP64eldRvA38mfiYqSMD1PaFocQtNr1tmyLmYl0L VyXQ== 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=+lQ2vkZBKg9cIiuJ2z/cpoHDMtcM3YRf1LZ5OTcsY2E=; b=yh57AJarc0hbeqNfQzjIWKo/YSOdeZkvn5+R/DZJe9Rs3znJySnJhUjd1PdiSMN1rG oxRW1aWd8nHwRTlZ8Cq4mAokybUhqLQ5BCAIEVOZJ874WSFwKc9V6ZE7m/cUHyU1gbOG wmPvcX7VLdCfrnZUrKwh7d43vlT91NfO8F9xvfyE17YhJooCTAdkfR3Fjb/IQbcfVVAn Ku8/TROHYrJN/g3NG6cSDRsZo7+uj0R0Vomhx618hX6HTqFo6UQyLFf0SOB05fPL6LGp 1iKRvlO2puj227t+dpBUrNzcxArYVGqA47r+ESB0fwa+HYEzK7DoL1JXAVQfJCqTjvQ7 f3+A== 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 u3-v6si2470720wrr.364.2018.10.23.18.33.03; Tue, 23 Oct 2018 18:33:03 -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 000F17CEB; Wed, 24 Oct 2018 03:32:44 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id 773005B2A for ; Wed, 24 Oct 2018 03:32:39 +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 A091D15AB; Tue, 23 Oct 2018 18:32:38 -0700 (PDT) Received: from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com [10.118.14.139]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 324F93F627; Tue, 23 Oct 2018 18:32:38 -0700 (PDT) From: Honnappa Nagarahalli To: bruce.richardson@intel.com, pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org, yipeng1.wang@intel.com, honnappa.nagarahalli@arm.com, dharmik.thakkar@arm.com, gavin.hu@arm.com, nd@arm.com Date: Tue, 23 Oct 2018 20:32:23 -0500 Message-Id: <1540344746-29045-3-git-send-email-honnappa.nagarahalli@arm.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1540344746-29045-1-git-send-email-honnappa.nagarahalli@arm.com> References: <1540344746-29045-1-git-send-email-honnappa.nagarahalli@arm.com> Subject: [dpdk-dev] [PATCH v6 2/5] hash: support do not free on delete 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" rte_hash_lookup_xxx APIs return the index of slot in the key store. Application(reader) can use that index to reference other data structures in its scope. Because of this, the index should not be freed till the application completes using the index. RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL is introduced to support this. When this flag is enabled rte_hash_del_xxx APIs do not free the key-store index/internal memory associated with the deleted entry. The new API rte_hash_free_key_with_position should be called to free the key-store index/internal memory after calling rte_hash_del_xxx APIs. Suggested-by: Yipeng Wang Signed-off-by: Honnappa Nagarahalli Reviewed-by: Gavin Hu Reviewed-by: Yipeng Wang Acked-by: Bruce Richardson --- lib/librte_hash/rte_cuckoo_hash.c | 50 +++++++++++++- lib/librte_hash/rte_cuckoo_hash.h | 6 ++ lib/librte_hash/rte_hash.h | 40 +++++++++++ test/test/test_hash.c | 140 +++++++++++++++++++++++++++++++++++++- 4 files changed, 232 insertions(+), 4 deletions(-) -- 2.7.4 diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 3539a10..e087393 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -140,6 +140,7 @@ rte_hash_create(const struct rte_hash_parameters *params) unsigned int ext_table_support = 0; unsigned int readwrite_concur_support = 0; unsigned int writer_takes_lock = 0; + unsigned int no_free_on_del = 0; rte_hash_function default_hash_func = (rte_hash_function)rte_jhash; @@ -176,6 +177,9 @@ rte_hash_create(const struct rte_hash_parameters *params) if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE) ext_table_support = 1; + if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL) + no_free_on_del = 1; + /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */ if (use_local_cache) /* @@ -359,6 +363,7 @@ rte_hash_create(const struct rte_hash_parameters *params) h->readwrite_concur_support = readwrite_concur_support; h->ext_table_support = ext_table_support; h->writer_takes_lock = writer_takes_lock; + h->no_free_on_del = no_free_on_del; #if defined(RTE_ARCH_X86) if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_SSE2)) @@ -1121,7 +1126,6 @@ remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i) unsigned lcore_id, n_slots; struct lcore_cache *cached_free_slots; - bkt->sig_current[i] = NULL_SIGNATURE; if (h->use_local_cache) { lcore_id = rte_lcore_id(); cached_free_slots = &h->local_free_slots[lcore_id]; @@ -1183,7 +1187,12 @@ search_and_remove(const struct rte_hash *h, const void *key, k = (struct rte_hash_key *) ((char *)keys + bkt->key_idx[i] * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { - remove_entry(h, bkt, i); + bkt->sig_current[i] = NULL_SIGNATURE; + /* Free the key store index if + * no_free_on_del is disabled. + */ + if (!h->no_free_on_del) + remove_entry(h, bkt, i); /* Return index where key is stored, * subtracting the first dummy index @@ -1301,6 +1310,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->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(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 8c522ac..ff95181 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -168,6 +168,12 @@ struct rte_hash { uint8_t readwrite_concur_support; /**< If read-write concurrency support is enabled */ uint8_t ext_table_support; /**< Enable extendable bucket table */ + uint8_t no_free_on_del; + /**< If key index should be freed on calling rte_hash_del_xxx APIs. + * If this is set, rte_hash_free_key_with_position must be called to + * free the key index associated with the deleted entry. + * This flag is enabled by default. + */ uint8_t writer_takes_lock; /**< Indicates if the writer threads need to take lock */ rte_hash_function hash_func; /**< Function used to calculate hash. */ diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index 6ace64e..dfa542b 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 @@ -40,6 +42,11 @@ extern "C" { /** Flag to indicate the extendabe bucket table feature should be used */ #define RTE_HASH_EXTRA_FLAGS_EXT_TABLE 0x08 +/** Flag to disable freeing of key index on hash delete. + * Refer to rte_hash_del_xxx APIs for more details. + */ +#define RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL 0x10 + /** * The type of hash value of a key. * It should be a value of at least 32bit with fully random pattern. @@ -236,6 +243,10 @@ rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t * and should 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 is 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. * * @param h * Hash table to remove the key from. @@ -257,6 +268,10 @@ 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 RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL is 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. * * @param h * Hash table to remove the key from. @@ -296,6 +311,31 @@ 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 a hash key in the hash table 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 RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL is enabled, + * this API must be called, with the key index returned by rte_hash_add_key_xxx + * APIs, after the key is deleted using rte_hash_del_key_xxx APIs. + * This API does not validate if the key is already freed. + * + * @param h + * Hash table to free 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/test/test/test_hash.c b/test/test/test_hash.c index 815c734..6d06eb2 100644 --- a/test/test/test_hash.c +++ b/test/test/test_hash.c @@ -260,6 +260,13 @@ static void run_hash_func_tests(void) * - lookup (hit) * - delete * - lookup (miss) + * + * Repeat the test case when 'free on delete' is disabled. + * - add + * - lookup (hit) + * - delete + * - lookup (miss) + * - free */ static int test_add_delete(void) { @@ -295,10 +302,12 @@ static int test_add_delete(void) /* repeat test with precomputed hash functions */ hash_sig_t hash_value; - int pos1, expectedPos1; + int pos1, expectedPos1, delPos1; + ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL; handle = rte_hash_create(&ut_params); RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + ut_params.extra_flag = 0; hash_value = rte_hash_hash(handle, &keys[0]); pos1 = rte_hash_add_key_with_hash(handle, &keys[0], hash_value); @@ -315,12 +324,18 @@ static int test_add_delete(void) print_key_info("Del", &keys[0], pos1); RETURN_IF_ERROR(pos1 != expectedPos1, "failed to delete key (pos1=%d)", pos1); + delPos1 = pos1; pos1 = rte_hash_lookup_with_hash(handle, &keys[0], hash_value); print_key_info("Lkp", &keys[0], pos1); RETURN_IF_ERROR(pos1 != -ENOENT, "fail: found key after deleting! (pos1=%d)", pos1); + pos1 = rte_hash_free_key_with_position(handle, delPos1); + print_key_info("Free", &keys[0], delPos1); + RETURN_IF_ERROR(pos1 != 0, + "failed to free key (pos1=%d)", delPos1); + rte_hash_free(handle); return 0; @@ -391,6 +406,84 @@ static int test_add_update_delete(void) } /* + * Sequence of operations for a single key with 'disable free on del' set: + * - delete: miss + * - add + * - lookup: hit + * - add: update + * - lookup: hit (updated data) + * - delete: hit + * - delete: miss + * - lookup: miss + * - free: hit + * - lookup: miss + */ +static int test_add_update_delete_free(void) +{ + struct rte_hash *handle; + int pos0, expectedPos0, delPos0, result; + + ut_params.name = "test2"; + ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL; + handle = rte_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + ut_params.extra_flag = 0; + + pos0 = rte_hash_del_key(handle, &keys[0]); + print_key_info("Del", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != -ENOENT, + "fail: found non-existent key (pos0=%d)", pos0); + + pos0 = rte_hash_add_key(handle, &keys[0]); + print_key_info("Add", &keys[0], pos0); + RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0); + expectedPos0 = pos0; + + pos0 = rte_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expectedPos0, + "failed to find key (pos0=%d)", pos0); + + pos0 = rte_hash_add_key(handle, &keys[0]); + print_key_info("Add", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expectedPos0, + "failed to re-add key (pos0=%d)", pos0); + + pos0 = rte_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expectedPos0, + "failed to find key (pos0=%d)", pos0); + + delPos0 = rte_hash_del_key(handle, &keys[0]); + print_key_info("Del", &keys[0], delPos0); + RETURN_IF_ERROR(delPos0 != expectedPos0, + "failed to delete key (pos0=%d)", delPos0); + + pos0 = rte_hash_del_key(handle, &keys[0]); + print_key_info("Del", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != -ENOENT, + "fail: deleted already deleted key (pos0=%d)", pos0); + + pos0 = rte_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != -ENOENT, + "fail: found key after deleting! (pos0=%d)", pos0); + + result = rte_hash_free_key_with_position(handle, delPos0); + print_key_info("Free", &keys[0], delPos0); + RETURN_IF_ERROR(result != 0, + "failed to free key (pos1=%d)", delPos0); + + pos0 = rte_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != -ENOENT, + "fail: found key after deleting! (pos0=%d)", pos0); + + rte_hash_free(handle); + return 0; +} + +/* * Sequence of operations for retrieving a key with its position * * - create table @@ -399,11 +492,20 @@ static int test_add_update_delete(void) * - delete key * - try to get the deleted key: miss * + * Repeat the test case when 'free on delete' is disabled. + * - create table + * - add key + * - get the key with its position: hit + * - delete key + * - try to get the deleted key: hit + * - free key + * - try to get the deleted key: miss + * */ static int test_hash_get_key_with_position(void) { struct rte_hash *handle = NULL; - int pos, expectedPos, result; + int pos, expectedPos, delPos, result; void *key; ut_params.name = "hash_get_key_w_pos"; @@ -427,6 +529,38 @@ static int test_hash_get_key_with_position(void) RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved"); rte_hash_free(handle); + + ut_params.name = "hash_get_key_w_pos"; + ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL; + handle = rte_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + ut_params.extra_flag = 0; + + pos = rte_hash_add_key(handle, &keys[0]); + print_key_info("Add", &keys[0], pos); + RETURN_IF_ERROR(pos < 0, "failed to add key (pos0=%d)", pos); + expectedPos = pos; + + result = rte_hash_get_key_with_position(handle, pos, &key); + RETURN_IF_ERROR(result != 0, "error retrieving a key"); + + delPos = rte_hash_del_key(handle, &keys[0]); + print_key_info("Del", &keys[0], delPos); + RETURN_IF_ERROR(delPos != expectedPos, + "failed to delete key (pos0=%d)", delPos); + + result = rte_hash_get_key_with_position(handle, delPos, &key); + RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved"); + + result = rte_hash_free_key_with_position(handle, delPos); + print_key_info("Free", &keys[0], delPos); + RETURN_IF_ERROR(result != 0, + "failed to free key (pos1=%d)", delPos); + + result = rte_hash_get_key_with_position(handle, delPos, &key); + RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved"); + + rte_hash_free(handle); return 0; } @@ -1609,6 +1743,8 @@ test_hash(void) return -1; if (test_add_update_delete() < 0) return -1; + if (test_add_update_delete_free() < 0) + return -1; if (test_five_keys() < 0) return -1; if (test_full_bucket() < 0)