From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 95C253772 for ; Tue, 15 Nov 2016 09:54:31 +0100 (CET) Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by orsmga102.jf.intel.com with ESMTP; 15 Nov 2016 00:54:21 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.31,641,1473145200"; d="scan'208";a="786581510" Received: from yliu-dev.sh.intel.com (HELO yliu-dev) ([10.239.67.162]) by FMSMGA003.fm.intel.com with ESMTP; 15 Nov 2016 00:54:19 -0800 Date: Tue, 15 Nov 2016 16:55:09 +0800 From: Yuanhan Liu To: Pablo de Lara Cc: stable@dpdk.org Message-ID: <20161115085509.GB5048@yliu-dev.sh.intel.com> References: <1478712124-14090-1-git-send-email-pablo.de.lara.guarch@intel.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1478712124-14090-1-git-send-email-pablo.de.lara.guarch@intel.com> User-Agent: Mutt/1.5.23 (2014-03-12) Subject: Re: [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: Tue, 15 Nov 2016 08:54:32 -0000 Both are applied to dpdk stable branch 16.07. Thanks. --yliu On Wed, Nov 09, 2016 at 05:22:03PM +0000, Pablo de Lara wrote: > 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