From 243e93a5046ff61658a0f5905ded49634c5ab205 Mon Sep 17 00:00:00 2001 From: Pablo de Lara Date: Wed, 12 Oct 2016 01:50:13 +0100 Subject: [PATCH] hash: fix unlimited cuckoo path 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 3324b179e3..51db006a96 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 c00aafad7c..1b8ffed8ed 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 -- 2.20.1