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): lib/librte_table: Fix empty bucket removal during entry deletion in rte_table_hash_ext lib/librte_table: Fix checking extended buckets in unoptimized case lib/librte_table: Fix incorrect t->data_size_shl initialization lib/librte_table: Fix pointer calculations at initialization lib/librte_table/rte_table_hash_ext.c | 13 ++++++------- 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 ++++---- lib/librte_table/rte_table_hash_lru.c | 7 +++---- 5 files changed, 17 insertions(+), 19 deletions(-) -- 1.9.1 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.
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. 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++] -- 1.9.1 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.
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. 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; -- 1.9.1 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.
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. 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; -- 1.9.1 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.
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. 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; -- 1.9.1 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.
Acked by: Cristian.Dumitrescu <cristian.dumitrescu at intel.com> -----Original Message----- From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Balazs Nemeth Sent: Thursday, September 11, 2014 6:47 PM To: dev@dpdk.org Cc: Nemeth, Balazs Subject: [dpdk-dev] [PATCH 0/4] lib/librte_table: Fix bugs occuring in corner cases 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): lib/librte_table: Fix empty bucket removal during entry deletion in rte_table_hash_ext lib/librte_table: Fix checking extended buckets in unoptimized case lib/librte_table: Fix incorrect t->data_size_shl initialization lib/librte_table: Fix pointer calculations at initialization lib/librte_table/rte_table_hash_ext.c | 13 ++++++------- 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 ++++---- lib/librte_table/rte_table_hash_lru.c | 7 +++---- 5 files changed, 17 insertions(+), 19 deletions(-) -- 1.9.1 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. -------------------------------------------------------------- Intel Shannon Limited Registered in Ireland Registered Office: Collinstown Industrial Park, Leixlip, County Kildare Registered Number: 308263 Business address: Dromore House, East Park, Shannon, Co. Clare 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.
I take the opportunity of this patchset to talk about commit formatting.
2014-09-11 19:47, Balazs Nemeth:
> 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.
I need you resend this patchset without confidential disclaimer.
Since Cristian acked the serie, you should add
"Acked by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>"
while re-sending it.
About formatting, titles should start with "table: " (like previous commits
for this lib), and first word is never uppercased.
Thanks
--
Thomas