* [dpdk-dev] [PATCH 1/4] table: fix empty bucket removal during entry deletion in rte_table_hash_ext
2014-09-26 9:37 [dpdk-dev] [PATCH 0/4] table: fix bugs occuring in corner cases Balazs Nemeth
@ 2014-09-26 9:37 ` Balazs Nemeth
2014-09-26 9:37 ` [dpdk-dev] [PATCH 2/4] table: fix checking extended buckets in unoptimized case Balazs Nemeth
` (3 subsequent siblings)
4 siblings, 0 replies; 7+ messages in thread
From: Balazs Nemeth @ 2014-09-26 9:37 UTC (permalink / raw)
To: dev; +Cc: Balazs Nemeth
When an entry is deleted from an extensible rte_table_hash, the bucket
that stored the entry can become empty. If this is the case, the
bucket needs to be removed from the chain of buckets.
During removal of the bucket, the chain should be updated first. If
the bucket that will be removed is cleared first, the chain is broken
and the information to update the chain is lost.
Acked-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Balazs Nemeth <balazs.nemeth@intel.com>
---
lib/librte_table/rte_table_hash_ext.c | 6 +++---
1 file changed, 3 insertions(+), 3 deletions(-)
diff --git a/lib/librte_table/rte_table_hash_ext.c b/lib/librte_table/rte_table_hash_ext.c
index 6e26d98..17c16cd 100644
--- a/lib/librte_table/rte_table_hash_ext.c
+++ b/lib/librte_table/rte_table_hash_ext.c
@@ -408,12 +408,12 @@ void *entry)
if ((bkt_prev != NULL) &&
(bkt->sig[0] == 0) && (bkt->sig[1] == 0) &&
(bkt->sig[2] == 0) && (bkt->sig[3] == 0)) {
- /* Clear bucket */
- memset(bkt, 0, sizeof(struct bucket));
-
/* Unchain bucket */
BUCKET_NEXT_COPY(bkt_prev, bkt);
+ /* Clear bucket */
+ memset(bkt, 0, sizeof(struct bucket));
+
/* Free bucket back to buckets ext */
bkt_index = bkt - t->buckets_ext;
t->bkt_ext_stack[t->bkt_ext_stack_tos++]
--
2.1.0
^ permalink raw reply [flat|nested] 7+ messages in thread* [dpdk-dev] [PATCH 2/4] table: fix checking extended buckets in unoptimized case
2014-09-26 9:37 [dpdk-dev] [PATCH 0/4] table: fix bugs occuring in corner cases Balazs Nemeth
2014-09-26 9:37 ` [dpdk-dev] [PATCH 1/4] table: fix empty bucket removal during entry deletion in rte_table_hash_ext Balazs Nemeth
@ 2014-09-26 9:37 ` Balazs Nemeth
2014-09-26 9:37 ` [dpdk-dev] [PATCH 3/4] table: fix incorrect t->data_size_shl initialization Balazs Nemeth
` (2 subsequent siblings)
4 siblings, 0 replies; 7+ messages in thread
From: Balazs Nemeth @ 2014-09-26 9:37 UTC (permalink / raw)
To: dev; +Cc: Balazs Nemeth
If a key is not found in a bucket and the bucket has been extended,
the extended buckets also have to checked for potentially matching
keys. The extended buckets are checked at the end of the lookup. In
most cases, this logic is skipped as it is uncommon to have buckets in
an extended state.
In case the lookup is performed with less than 5 packets, an
unoptimized version is run instead (the optimized version requires at
least 5 packets). The extended buckets should also be checked in this
case instead of simply ignoring the extended buckets.
Acked-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Balazs Nemeth <balazs.nemeth@intel.com>
---
lib/librte_table/rte_table_hash_key16.c | 4 ++--
lib/librte_table/rte_table_hash_key32.c | 4 ++--
lib/librte_table/rte_table_hash_key8.c | 8 ++++----
3 files changed, 8 insertions(+), 8 deletions(-)
diff --git a/lib/librte_table/rte_table_hash_key16.c b/lib/librte_table/rte_table_hash_key16.c
index f5ec87d..f78db77 100644
--- a/lib/librte_table/rte_table_hash_key16.c
+++ b/lib/librte_table/rte_table_hash_key16.c
@@ -968,8 +968,7 @@ rte_table_hash_lookup_key16_ext(
buckets, keys, f);
}
- *lookup_hit_mask = pkts_mask_out;
- return 0;
+ goto grind_next_buckets;
}
/*
@@ -1060,6 +1059,7 @@ rte_table_hash_lookup_key16_ext(
bucket20, bucket21, pkts_mask_out, entries,
buckets_mask, buckets, keys, f);
+grind_next_buckets:
/* Grind next buckets */
for ( ; buckets_mask; ) {
uint64_t buckets_mask_next = 0;
diff --git a/lib/librte_table/rte_table_hash_key32.c b/lib/librte_table/rte_table_hash_key32.c
index e8f4812..10e281d 100644
--- a/lib/librte_table/rte_table_hash_key32.c
+++ b/lib/librte_table/rte_table_hash_key32.c
@@ -988,8 +988,7 @@ rte_table_hash_lookup_key32_ext(
keys, f);
}
- *lookup_hit_mask = pkts_mask_out;
- return 0;
+ goto grind_next_buckets;
}
/*
@@ -1080,6 +1079,7 @@ rte_table_hash_lookup_key32_ext(
bucket20, bucket21, pkts_mask_out, entries,
buckets_mask, buckets, keys, f);
+grind_next_buckets:
/* Grind next buckets */
for ( ; buckets_mask; ) {
uint64_t buckets_mask_next = 0;
diff --git a/lib/librte_table/rte_table_hash_key8.c b/lib/librte_table/rte_table_hash_key8.c
index d60c96e..606805d 100644
--- a/lib/librte_table/rte_table_hash_key8.c
+++ b/lib/librte_table/rte_table_hash_key8.c
@@ -1104,8 +1104,7 @@ rte_table_hash_lookup_key8_ext(
keys, f);
}
- *lookup_hit_mask = pkts_mask_out;
- return 0;
+ goto grind_next_buckets;
}
/*
@@ -1196,6 +1195,7 @@ rte_table_hash_lookup_key8_ext(
bucket20, bucket21, pkts_mask_out, entries,
buckets_mask, buckets, keys, f);
+grind_next_buckets:
/* Grind next buckets */
for ( ; buckets_mask; ) {
uint64_t buckets_mask_next = 0;
@@ -1250,8 +1250,7 @@ rte_table_hash_lookup_key8_ext_dosig(
buckets, keys, f);
}
- *lookup_hit_mask = pkts_mask_out;
- return 0;
+ goto grind_next_buckets;
}
/*
@@ -1342,6 +1341,7 @@ rte_table_hash_lookup_key8_ext_dosig(
bucket20, bucket21, pkts_mask_out, entries,
buckets_mask, buckets, keys, f);
+grind_next_buckets:
/* Grind next buckets */
for ( ; buckets_mask; ) {
uint64_t buckets_mask_next = 0;
--
2.1.0
^ permalink raw reply [flat|nested] 7+ messages in thread* [dpdk-dev] [PATCH 3/4] table: fix incorrect t->data_size_shl initialization
2014-09-26 9:37 [dpdk-dev] [PATCH 0/4] table: fix bugs occuring in corner cases Balazs Nemeth
2014-09-26 9:37 ` [dpdk-dev] [PATCH 1/4] table: fix empty bucket removal during entry deletion in rte_table_hash_ext Balazs Nemeth
2014-09-26 9:37 ` [dpdk-dev] [PATCH 2/4] table: fix checking extended buckets in unoptimized case Balazs Nemeth
@ 2014-09-26 9:37 ` Balazs Nemeth
2014-09-26 9:37 ` [dpdk-dev] [PATCH 4/4] table: fix pointer calculations at initialization Balazs Nemeth
2014-11-24 15:43 ` [dpdk-dev] [PATCH 0/4] table: fix bugs occuring in corner cases Thomas Monjalon
4 siblings, 0 replies; 7+ messages in thread
From: Balazs Nemeth @ 2014-09-26 9:37 UTC (permalink / raw)
To: dev; +Cc: Balazs Nemeth
During initialization of rte_hash_table_ext and rte_hash_table_lru,
t->data_size_shl is calculated. This member contains the number of
bits to shift left during calculation of the location of entries in
the hash table. To determine the number of bits to shift left, the
size of the entry (as provided to the rte_table_hash_ext_create and
rte_table_hash_lru_create) has to be used instead of the size of the
key.
Acked-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Balazs Nemeth <balazs.nemeth@intel.com>
---
lib/librte_table/rte_table_hash_ext.c | 2 +-
lib/librte_table/rte_table_hash_lru.c | 2 +-
2 files changed, 2 insertions(+), 2 deletions(-)
diff --git a/lib/librte_table/rte_table_hash_ext.c b/lib/librte_table/rte_table_hash_ext.c
index 17c16cd..fb3e6d2 100644
--- a/lib/librte_table/rte_table_hash_ext.c
+++ b/lib/librte_table/rte_table_hash_ext.c
@@ -221,7 +221,7 @@ rte_table_hash_ext_create(void *params, int socket_id, uint32_t entry_size)
/* Internal */
t->bucket_mask = t->n_buckets - 1;
t->key_size_shl = __builtin_ctzl(p->key_size);
- t->data_size_shl = __builtin_ctzl(p->key_size);
+ t->data_size_shl = __builtin_ctzl(entry_size);
/* Tables */
table_meta_offset = 0;
diff --git a/lib/librte_table/rte_table_hash_lru.c b/lib/librte_table/rte_table_hash_lru.c
index d1a4984..bf92e81 100644
--- a/lib/librte_table/rte_table_hash_lru.c
+++ b/lib/librte_table/rte_table_hash_lru.c
@@ -192,7 +192,7 @@ rte_table_hash_lru_create(void *params, int socket_id, uint32_t entry_size)
/* Internal */
t->bucket_mask = t->n_buckets - 1;
t->key_size_shl = __builtin_ctzl(p->key_size);
- t->data_size_shl = __builtin_ctzl(p->key_size);
+ t->data_size_shl = __builtin_ctzl(entry_size);
/* Tables */
table_meta_offset = 0;
--
2.1.0
^ permalink raw reply [flat|nested] 7+ messages in thread
* [dpdk-dev] [PATCH 4/4] table: fix pointer calculations at initialization
2014-09-26 9:37 [dpdk-dev] [PATCH 0/4] table: fix bugs occuring in corner cases Balazs Nemeth
` (2 preceding siblings ...)
2014-09-26 9:37 ` [dpdk-dev] [PATCH 3/4] table: fix incorrect t->data_size_shl initialization Balazs Nemeth
@ 2014-09-26 9:37 ` Balazs Nemeth
2014-11-24 15:43 ` [dpdk-dev] [PATCH 0/4] table: fix bugs occuring in corner cases Thomas Monjalon
4 siblings, 0 replies; 7+ messages in thread
From: Balazs Nemeth @ 2014-09-26 9:37 UTC (permalink / raw)
To: dev; +Cc: Balazs Nemeth
During initialization of rte_table_hash_ext and rte_table_hash_lru, a
contiguous region of memory is allocated to store meta data, buckets,
extended buckets, keys, stack of keys, stack of extended buckets and
data entries. The size of each region depends on the hash table
configuration.
The address of each region is calculated using offsets relative to the
beginning of the memory region. Without this patch, the offsets
contain the size of the table meta data (sizeof(struct
rte_table_hash)). These addresses are stored in pointers which are
used when entries are added or deleted and lookups are performed.
Instead of adding these offsets to the address of the beginning of the
memory region, they are added to the address of the end of the meta
data (= address of the beginning of the memory region + sizeof(struct
rte_table_hash)). The resulting addresses are off by sizeof(struct
rte_table_hash) bytes. As a consequence, memory past the allocated
region can be accessed by the add, delete and lookup operations.
This patch corrects the address calculation by not including the size
of the meta data in the offsets.
Acked-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Balazs Nemeth <balazs.nemeth@intel.com>
---
lib/librte_table/rte_table_hash_ext.c | 5 ++---
lib/librte_table/rte_table_hash_lru.c | 5 ++---
2 files changed, 4 insertions(+), 6 deletions(-)
diff --git a/lib/librte_table/rte_table_hash_ext.c b/lib/librte_table/rte_table_hash_ext.c
index fb3e6d2..467f48a 100644
--- a/lib/librte_table/rte_table_hash_ext.c
+++ b/lib/librte_table/rte_table_hash_ext.c
@@ -170,7 +170,7 @@ rte_table_hash_ext_create(void *params, int socket_id, uint32_t entry_size)
struct rte_table_hash_ext_params *p =
(struct rte_table_hash_ext_params *) params;
struct rte_table_hash *t;
- uint32_t total_size, table_meta_sz, table_meta_offset;
+ uint32_t total_size, table_meta_sz;
uint32_t bucket_sz, bucket_ext_sz, key_sz;
uint32_t key_stack_sz, bkt_ext_stack_sz, data_sz;
uint32_t bucket_offset, bucket_ext_offset, key_offset;
@@ -224,8 +224,7 @@ rte_table_hash_ext_create(void *params, int socket_id, uint32_t entry_size)
t->data_size_shl = __builtin_ctzl(entry_size);
/* Tables */
- table_meta_offset = 0;
- bucket_offset = table_meta_offset + table_meta_sz;
+ bucket_offset = 0;
bucket_ext_offset = bucket_offset + bucket_sz;
key_offset = bucket_ext_offset + bucket_ext_sz;
key_stack_offset = key_offset + key_sz;
diff --git a/lib/librte_table/rte_table_hash_lru.c b/lib/librte_table/rte_table_hash_lru.c
index bf92e81..f94c0a2 100644
--- a/lib/librte_table/rte_table_hash_lru.c
+++ b/lib/librte_table/rte_table_hash_lru.c
@@ -147,7 +147,7 @@ rte_table_hash_lru_create(void *params, int socket_id, uint32_t entry_size)
struct rte_table_hash_lru_params *p =
(struct rte_table_hash_lru_params *) params;
struct rte_table_hash *t;
- uint32_t total_size, table_meta_sz, table_meta_offset;
+ uint32_t total_size, table_meta_sz;
uint32_t bucket_sz, key_sz, key_stack_sz, data_sz;
uint32_t bucket_offset, key_offset, key_stack_offset, data_offset;
uint32_t i;
@@ -195,8 +195,7 @@ rte_table_hash_lru_create(void *params, int socket_id, uint32_t entry_size)
t->data_size_shl = __builtin_ctzl(entry_size);
/* Tables */
- table_meta_offset = 0;
- bucket_offset = table_meta_offset + table_meta_sz;
+ bucket_offset = 0;
key_offset = bucket_offset + bucket_sz;
key_stack_offset = key_offset + key_sz;
data_offset = key_stack_offset + key_stack_sz;
--
2.1.0
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [dpdk-dev] [PATCH 0/4] table: fix bugs occuring in corner cases
2014-09-26 9:37 [dpdk-dev] [PATCH 0/4] table: fix bugs occuring in corner cases Balazs Nemeth
` (3 preceding siblings ...)
2014-09-26 9:37 ` [dpdk-dev] [PATCH 4/4] table: fix pointer calculations at initialization Balazs Nemeth
@ 2014-11-24 15:43 ` Thomas Monjalon
4 siblings, 0 replies; 7+ messages in thread
From: Thomas Monjalon @ 2014-11-24 15:43 UTC (permalink / raw)
To: Balazs Nemeth; +Cc: dev
> This set of patches fixes bugs in the packet framework. Some of the
> bugs occur in corner cases (i.e. when a lookup is performed on a few
> packets or when buckets are in extended states) while others can cause
> memory to be accessed beyond what is reserved during initialization
> time.
>
> Balazs Nemeth (4):
> table: fix empty bucket removal during entry deletion in
> rte_table_hash_ext
> table: fix checking extended buckets in unoptimized case
> table: fix incorrect t->data_size_shl initialization
> table: fix pointer calculations at initialization
Applied
Thanks
--
Thomas
^ permalink raw reply [flat|nested] 7+ messages in thread
* [dpdk-dev] [PATCH 4/4] table: fix pointer calculations at initialization
2014-09-25 15:24 Balazs Nemeth
@ 2014-09-25 15:24 ` Balazs Nemeth
0 siblings, 0 replies; 7+ messages in thread
From: Balazs Nemeth @ 2014-09-25 15:24 UTC (permalink / raw)
To: dev; +Cc: Balazs Nemeth
During initialization of rte_table_hash_ext and rte_table_hash_lru, a
contiguous region of memory is allocated to store meta data, buckets,
extended buckets, keys, stack of keys, stack of extended buckets and
data entries. The size of each region depends on the hash table
configuration.
The address of each region is calculated using offsets relative to the
beginning of the memory region. Without this patch, the offsets
contain the size of the table meta data (sizeof(struct
rte_table_hash)). These addresses are stored in pointers which are
used when entries are added or deleted and lookups are performed.
Instead of adding these offsets to the address of the beginning of the
memory region, they are added to the address of the end of the meta
data (= address of the beginning of the memory region + sizeof(struct
rte_table_hash)). The resulting addresses are off by sizeof(struct
rte_table_hash) bytes. As a consequence, memory past the allocated
region can be accessed by the add, delete and lookup operations.
This patch corrects the address calculation by not including the size
of the meta data in the offsets.
Acked-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Balazs Nemeth <balazs.nemeth@intel.com>
---
lib/librte_table/rte_table_hash_ext.c | 5 ++---
lib/librte_table/rte_table_hash_lru.c | 5 ++---
2 files changed, 4 insertions(+), 6 deletions(-)
diff --git a/lib/librte_table/rte_table_hash_ext.c b/lib/librte_table/rte_table_hash_ext.c
index fb3e6d2..467f48a 100644
--- a/lib/librte_table/rte_table_hash_ext.c
+++ b/lib/librte_table/rte_table_hash_ext.c
@@ -170,7 +170,7 @@ rte_table_hash_ext_create(void *params, int socket_id, uint32_t entry_size)
struct rte_table_hash_ext_params *p =
(struct rte_table_hash_ext_params *) params;
struct rte_table_hash *t;
- uint32_t total_size, table_meta_sz, table_meta_offset;
+ uint32_t total_size, table_meta_sz;
uint32_t bucket_sz, bucket_ext_sz, key_sz;
uint32_t key_stack_sz, bkt_ext_stack_sz, data_sz;
uint32_t bucket_offset, bucket_ext_offset, key_offset;
@@ -224,8 +224,7 @@ rte_table_hash_ext_create(void *params, int socket_id, uint32_t entry_size)
t->data_size_shl = __builtin_ctzl(entry_size);
/* Tables */
- table_meta_offset = 0;
- bucket_offset = table_meta_offset + table_meta_sz;
+ bucket_offset = 0;
bucket_ext_offset = bucket_offset + bucket_sz;
key_offset = bucket_ext_offset + bucket_ext_sz;
key_stack_offset = key_offset + key_sz;
diff --git a/lib/librte_table/rte_table_hash_lru.c b/lib/librte_table/rte_table_hash_lru.c
index bf92e81..f94c0a2 100644
--- a/lib/librte_table/rte_table_hash_lru.c
+++ b/lib/librte_table/rte_table_hash_lru.c
@@ -147,7 +147,7 @@ rte_table_hash_lru_create(void *params, int socket_id, uint32_t entry_size)
struct rte_table_hash_lru_params *p =
(struct rte_table_hash_lru_params *) params;
struct rte_table_hash *t;
- uint32_t total_size, table_meta_sz, table_meta_offset;
+ uint32_t total_size, table_meta_sz;
uint32_t bucket_sz, key_sz, key_stack_sz, data_sz;
uint32_t bucket_offset, key_offset, key_stack_offset, data_offset;
uint32_t i;
@@ -195,8 +195,7 @@ rte_table_hash_lru_create(void *params, int socket_id, uint32_t entry_size)
t->data_size_shl = __builtin_ctzl(entry_size);
/* Tables */
- table_meta_offset = 0;
- bucket_offset = table_meta_offset + table_meta_sz;
+ bucket_offset = 0;
key_offset = bucket_offset + bucket_sz;
key_stack_offset = key_offset + key_sz;
data_offset = key_stack_offset + key_stack_sz;
--
2.1.0
Intel Corporation NV/SA
Kings Square, Veldkant 31
2550 Kontich
RPM (Bruxelles) 0415.497.718.
Citibank, Brussels, account 570/1031255/09
This e-mail and any attachments may contain confidential material for the sole use of the intended recipient(s). Any review or distribution by others is strictly prohibited. If you are not the intended recipient, please contact the sender and delete all copies.
^ permalink raw reply [flat|nested] 7+ messages in thread