[dpdk-dev] [PATCH 0/4] table: fix bugs occuring in corner cases

[dpdk-dev] [PATCH 0/4] table: fix bugs occuring in corner cases

[Balazs Nemeth]

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

 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(-)

-- 
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.

[dpdk-dev] [PATCH 1/4] table: fix empty bucket removal during entry deletion in rte_table_hash_ext

[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
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.

[dpdk-dev] [PATCH 2/4] table: fix checking extended buckets in unoptimized case

[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
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.

[dpdk-dev] [PATCH 3/4] table: fix incorrect t->data_size_shl initialization

[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
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.

[dpdk-dev] [PATCH 4/4] table: fix pointer calculations at initialization

[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.

Re: [dpdk-dev] [PATCH 1/4] table: fix empty bucket removal during entry deletion in rte_table_hash_ext

[Neil Horman]

On Thu, Sep 25, 2014 at 03:24:35PM +0000, Balazs Nemeth wrote:
> 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++]
Acked-by: Neil Horman <nhorman@tuxdriver.com>

> --
> 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.
> 
> 

[dpdk-dev] [PATCH 2/4] table: fix checking extended buckets in unoptimized case

[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