From patchwork Fri Oct 12 06:31:53 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 148717 Delivered-To: patch@linaro.org Received: by 2002:a2e:8595:0:0:0:0:0 with SMTP id b21-v6csp368132lji; Thu, 11 Oct 2018 23:32:28 -0700 (PDT) X-Google-Smtp-Source: ACcGV63Xlk2vEPnWcm6uHnHkv0oNKQIa6wRlT7Oxs3qdisPvRsmsGHsujQEl0WBeis+o2OHDlSrM X-Received: by 2002:a50:ba89:: with SMTP id x9-v6mr914718ede.191.1539325948147; Thu, 11 Oct 2018 23:32:28 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1539325948; cv=none; d=google.com; s=arc-20160816; b=D1HbICE9hYvekBwhBfppyGCwT8j9URQilVIbWjGXdXIn1wfpkqco9+leqfm/XH0bN1 KoRxd9Yi8CNHwZtvQy2ekFc44WF2+Tj7TppVl5rP/3ZSv3vP9M6fyxId7FIUHxoh6Ffv 1WwMMYeCQeBiepmxIbn1J3+khNw4MwT+ZqI7IRDFMHKNSpaqzng32Mojcs+x0QFRG03a 5KMRRenmIfXxGSJALsXfbngHVNcDIPj92t5ByiuGb45d9rDR/Wvx5GTJKpacfu1ILQvx lge2BpgPyx5RQoJ+X+W+A5jjys07j5BTtgKNzl33csyAf6ZdfS0VFvR0vK2t6B9uG5Uk /1MA== 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=CTibyfiQL2TMWTZVLgFTxWKuLQtM+EEjwgMbfrP8Li4=; b=pB0qIN9zMm99E+wBH/J05AerzIqe0Nh1F/wEZ2KWkeMjI5pke1sDHfmoagvGGlwmF2 4gpVNcmeei+P7ezszCsDimnLKehH2tVtSKHCVISLJfura8+jioKJBR1Jd9IuNLeoeAu/ UUvdw2y+5Bt0H9ByA6fXuSmvCe54nTQ296iSoalFCMCp45e1ovJ/Xsj9pySjbrScT0oF foMYijix7qAvHY71/06TiN8XXaXdUuj0+mgQo+RHkzbjHEuLh0BncdUlAkc6w8xsdVZC SzYYpRtkZKiQCo/n+HjMbVZsYDijbJ0+epx0lqDE7QEo2PSY7Letn4V8AREgmyCmOEJz YLiQ== 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 k8-v6si409974ejg.208.2018.10.11.23.32.27; Thu, 11 Oct 2018 23:32:28 -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 AC9361B110; Fri, 12 Oct 2018 08:32:14 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id D1E776833 for ; Fri, 12 Oct 2018 08:32:09 +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 4601F15BF; Thu, 11 Oct 2018 23:32:09 -0700 (PDT) Received: from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com [10.118.12.190]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id D401E3F5B3; Thu, 11 Oct 2018 23:32:08 -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: Fri, 12 Oct 2018 01:31:53 -0500 Message-Id: <1539325918-125438-3-git-send-email-honnappa.nagarahalli@arm.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1539325918-125438-1-git-send-email-honnappa.nagarahalli@arm.com> References: <1539325918-125438-1-git-send-email-honnappa.nagarahalli@arm.com> Subject: [dpdk-dev] [PATCH v3 2/7] hash: support do not recycle 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 the element 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 recycled till the application completes using the index. RTE_HASH_EXTRA_FLAGS_RECYCLE_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 --- lib/librte_hash/rte_cuckoo_hash.c | 50 +++++++++++++- lib/librte_hash/rte_cuckoo_hash.h | 8 +++ lib/librte_hash/rte_hash.h | 40 +++++++++++ test/test/test_hash.c | 140 +++++++++++++++++++++++++++++++++++++- 4 files changed, 234 insertions(+), 4 deletions(-) -- 2.7.4 Reviewed-by: Yipeng Wang diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 7bbe9e9..8de0de3 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 recycle_on_del = 1; 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_RECYCLE_ON_DEL) + recycle_on_del = 0; + /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */ if (multi_writer_support) /* @@ -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->recycle_on_del = recycle_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->multi_writer_support) { 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; + /* Do not free the key store element if + * recycle_on_del is disabled. + */ + if (h->recycle_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->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 1137651..5225402 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -166,6 +166,14 @@ 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 recycle_on_del; + /**< If internal memory/key-store entry should be + * freed on calling the rte_hash_del_xxx APIs. + * If this is set, rte_hash_free_key_with_position must be + * called to free the internal memory 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..3e5d336 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 internal memory/indices on hash delete. + * Refer to rte_hash_del_xxx APIs for more details. + */ +#define RTE_HASH_EXTRA_FLAGS_RECYCLE_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_RECYCLE_ON_DEL is enabled, + * the hash library's internal memory/index will not be freed by this + * API. rte_hash_free_key_with_position API must be called additionally + * to free the internal memory/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_RECYCLE_ON_DEL is enabled, + * the hash library's internal memory/index will not be freed by this + * API. rte_hash_free_key_with_position API must be called additionally + * to free the internal memory/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 hash library's internal memory/index 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_RECYCLE_ON_DEL is enabled, + * the hash library's internal memory/index must be freed using this API + * 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..19131e9 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_RECYCLE_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_RECYCLE_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_RECYCLE_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)