From patchwork Wed Oct 12 00:50:13 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "De Lara Guarch, Pablo" X-Patchwork-Id: 16496 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [IPv6:::1]) by dpdk.org (Postfix) with ESMTP id 142636CD0; Wed, 12 Oct 2016 02:49:02 +0200 (CEST) Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by dpdk.org (Postfix) with ESMTP id 3CBF06CCE for ; Wed, 12 Oct 2016 02:49:00 +0200 (CEST) Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by fmsmga103.fm.intel.com with ESMTP; 11 Oct 2016 17:48:59 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.31,479,1473145200"; d="scan'208";a="771554701" Received: from sie-lab-214-036.ir.intel.com (HELO silpixa00394365.ir.intel.com) ([10.237.214.36]) by FMSMGA003.fm.intel.com with ESMTP; 11 Oct 2016 17:48:58 -0700 From: Pablo de Lara To: dev@dpdk.org Cc: bruce.richardson@intel.com, Pablo de Lara Date: Wed, 12 Oct 2016 01:50:13 +0100 Message-Id: <1476233413-12788-1-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1476232972-12564-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1476232972-12564-1-git-send-email-pablo.de.lara.guarch@intel.com> Subject: [dpdk-dev] [PATCH v2] hash: fix unlimited cuckoo path X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" When trying to insert a new entry, if its target bucket is full, the alternative location (bucket) of one of the entries is checked, to try to find an empty slot, with make_space_bucket. This function is called every time a new bucket is checked, recursively. To avoid having a very long insert operation (and to avoid filling up the stack), a limit in the number of pushes is introduced. Fixes: 48a399119619 ("hash: replace with cuckoo hash implementation") Signed-off-by: Pablo de Lara --- Changes in v2: - Included Fixes line lib/librte_hash/rte_cuckoo_hash.c | 6 +++++- lib/librte_hash/rte_cuckoo_hash.h | 2 ++ 2 files changed, 7 insertions(+), 1 deletion(-) diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 3324b17..51db006 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -419,6 +419,7 @@ rte_hash_reset(struct rte_hash *h) static inline int make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt) { + static unsigned int nr_pushes; unsigned i, j; int ret; uint32_t next_bucket_idx; @@ -455,11 +456,13 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt) break; /* All entries have been pushed, so entry cannot be added */ - if (i == RTE_HASH_BUCKET_ENTRIES) + if (i == RTE_HASH_BUCKET_ENTRIES || nr_pushes > RTE_HASH_MAX_PUSHES) return -ENOSPC; /* Set flag to indicate that this entry is going to be pushed */ bkt->flag[i] = 1; + + nr_pushes++; /* Need room in alternative bucket to insert the pushed entry */ ret = make_space_bucket(h, next_bkt[i]); /* @@ -469,6 +472,7 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt) * or return error */ bkt->flag[i] = 0; + nr_pushes = 0; if (ret >= 0) { next_bkt[i]->sig_alt[ret] = bkt->sig_current[i]; next_bkt[i]->sig_current[ret] = bkt->sig_alt[i]; diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index c00aafa..1b8ffed 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -140,6 +140,8 @@ enum add_key_case { #define LCORE_CACHE_SIZE 64 +#define RTE_HASH_MAX_PUSHES 100 + #define RTE_HASH_BFS_QUEUE_MAX_LEN 1000 #define RTE_XABORT_CUCKOO_PATH_INVALIDED 0x4