From patchwork Mon Apr 27 03:41:05 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Lilijun (Jerry)" X-Patchwork-Id: 69356 X-Patchwork-Delegate: thomas@monjalon.net 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 A1565A00BE; Mon, 27 Apr 2020 05:41:24 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id D00FA1C01E; Mon, 27 Apr 2020 05:41:22 +0200 (CEST) Received: from huawei.com (szxga03-in.huawei.com [45.249.212.189]) by dpdk.org (Postfix) with ESMTP id 892E21BFB6; Mon, 27 Apr 2020 05:41:19 +0200 (CEST) Received: from DGGEML402-HUB.china.huawei.com (unknown [172.30.72.55]) by Forcepoint Email with ESMTP id C7710F859A97EDDB0D87; Mon, 27 Apr 2020 11:41:16 +0800 (CST) Received: from DGGEML424-HUB.china.huawei.com (10.1.199.41) by DGGEML402-HUB.china.huawei.com (10.3.17.38) with Microsoft SMTP Server (TLS) id 14.3.487.0; Mon, 27 Apr 2020 11:41:16 +0800 Received: from DGGEML529-MBX.china.huawei.com ([169.254.6.203]) by dggeml424-hub.china.huawei.com ([10.1.199.41]) with mapi id 14.03.0487.000; Mon, 27 Apr 2020 11:41:06 +0800 From: "Lilijun (Jerry)" To: "'dev@dpdk.org'" CC: wangyunjian , xudingke , "'stable@dpdk.org'" Thread-Topic: [dpdk-dev] [PATCH] lib/librte_hash: avoid iterate bugs with delete keys. Thread-Index: AdYcRaxOBIK0iMKdQzaoWZN1CFUPDQ== Date: Mon, 27 Apr 2020 03:41:05 +0000 Message-ID: <40280F65B1B0B44E8089ED31C01616EBA49922F6@dggeml529-mbx.china.huawei.com> Accept-Language: zh-CN, en-US Content-Language: zh-CN X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.173.251.98] MIME-Version: 1.0 X-CFilter-Loop: Reflected Subject: [dpdk-dev] [PATCH] lib/librte_hash: avoid iterate bugs with delete keys. 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" From 0faea722b82ffe30adfa55d5ea4ad3a23ed30d4e Mon Sep 17 00:00:00 2001 From: Yunjian Wang Date: Mon, 27 Apr 2020 11:12:25 +0800 Subject: [PATCH] lib/librte_hash: avoid iterate bugs with delete keys. The keys idx are stored in rte_hash main and extend bucket key slots. We iterate every no empty Keys in h->buckets and h->buckets_ext from start to last. When deleting keys the function __rte_hash_compact_ll() may move last_bkt's key to previous bucket in order to compact extend bucket list. If the previous bucket has been iterated, the moved key may be missed for users. Then those missed keys are leaked and rte_hash table can't be cleanup. So we add a new API rte_hash_del_key_fixed() used in iterate loop to avoid this bugs. Signed-off-by: Lilijun Signed-off-by: Yunjian Wang --- lib/librte_hash/rte_cuckoo_hash.c | 19 +++++++++++++----- lib/librte_hash/rte_hash.h | 30 ++++++++++++++++++++++++++++ lib/librte_hash/rte_hash_version.map | 1 + 3 files changed, 45 insertions(+), 5 deletions(-) diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 38767a8a1..1b6f84759 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -1491,7 +1491,7 @@ search_and_remove(const struct rte_hash *h, const void *key, static inline int32_t __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, - hash_sig_t sig) + hash_sig_t sig, uint8_t compact) { uint32_t prim_bucket_idx, sec_bucket_idx; struct rte_hash_bucket *prim_bkt, *sec_bkt, *prev_bkt, *last_bkt; @@ -1509,7 +1509,8 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, /* look for key in primary bucket */ ret = search_and_remove(h, key, prim_bkt, short_sig, &pos); if (ret != -1) { - __rte_hash_compact_ll(h, prim_bkt, pos); + if (compact) + __rte_hash_compact_ll(h, prim_bkt, pos); last_bkt = prim_bkt->next; prev_bkt = prim_bkt; goto return_bkt; @@ -1521,7 +1522,8 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, FOR_EACH_BUCKET(cur_bkt, sec_bkt) { ret = search_and_remove(h, key, cur_bkt, short_sig, &pos); if (ret != -1) { - __rte_hash_compact_ll(h, cur_bkt, pos); + if (compact) + __rte_hash_compact_ll(h, cur_bkt, pos); last_bkt = sec_bkt->next; prev_bkt = sec_bkt; goto return_bkt; @@ -1576,14 +1578,21 @@ rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig) { RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); - return __rte_hash_del_key_with_hash(h, key, sig); + return __rte_hash_del_key_with_hash(h, key, sig, 1); } int32_t rte_hash_del_key(const struct rte_hash *h, const void *key) { RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); - return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key)); + return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key), 1); +} + +int32_t +rte_hash_del_key_fixed(const struct rte_hash *h, const void *key) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key), 0); } int diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index bff40251b..1bea33809 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -309,6 +309,36 @@ rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t int32_t rte_hash_del_key(const struct rte_hash *h, const void *key); +/** + * Remove a key without compact ext bucket list from an existing hash table. + * 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 or + * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF 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. + * rte_hash_free_key_with_position API should be called after all + * the readers have stopped referencing the entry corresponding to + * this key. RCU mechanisms could be used to determine such a state. + * + * @param h + * Hash table to remove the key from. + * @param key + * Key to remove from the hash table. + * @return + * - -EINVAL if the parameters are invalid. + * - -ENOENT if the key is not found. + * - 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. + */ +__rte_experimental +int32_t +rte_hash_del_key_fixed(const struct rte_hash *h, const void *key); + /** * Remove a key from an existing hash table. * This operation is not multi-thread safe diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map index c2a909443..11a7f9b61 100644 --- a/lib/librte_hash/rte_hash_version.map +++ b/lib/librte_hash/rte_hash_version.map @@ -36,5 +36,6 @@ EXPERIMENTAL { rte_hash_lookup_with_hash_bulk; rte_hash_lookup_with_hash_bulk_data; rte_hash_max_key_id; + rte_hash_del_key_fixed; };