From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga04.intel.com (mga04.intel.com [192.55.52.120]) by dpdk.org (Postfix) with ESMTP id 019C4558D for ; Wed, 9 Nov 2016 18:21:21 +0100 (CET) Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by fmsmga104.fm.intel.com with ESMTP; 09 Nov 2016 09:21:05 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.31,614,1473145200"; d="scan'208";a="1082916046" Received: from sie-lab-214-036.ir.intel.com (HELO silpixa00394365.ir.intel.com) ([10.237.214.36]) by fmsmga002.fm.intel.com with ESMTP; 09 Nov 2016 09:21:04 -0800 From: Pablo de Lara To: stable@dpdk.org Cc: yuanhan.liu@linux.intel.com, Pablo de Lara Date: Wed, 9 Nov 2016 17:22:03 +0000 Message-Id: <1478712124-14090-1-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 2.7.4 Subject: [dpdk-stable] [PATCH 1/2] hash: fix unlimited cuckoo path X-BeenThere: stable@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches for stable branches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 09 Nov 2016 17:21:23 -0000 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 --- 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 26e54f6..53363ed 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -408,6 +408,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; @@ -444,11 +445,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]); /* @@ -458,6 +461,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]->signatures[ret].alt = bkt->signatures[i].current; next_bkt[i]->signatures[ret].current = bkt->signatures[i].alt; diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index 6c76700..9625fff 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -138,6 +138,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 -- 2.7.4