acl: fix 32-bit match for range field

ACL build phase for range fields that are bigger then
16 bits might generate wrong trie.
For more details please refer to:
https://bugs.dpdk.org/show_bug.cgi?id=307

Bugzilla ID: 307
Fixes: dc276b5780c2 ("acl: new library")
Cc: stable@dpdk.org
Reported-by: Ido Goshen <ido@cgstowernetworks.com>
Signed-off-by: Konstantin Ananyev <konstantin.ananyev@intel.com>

diff --git a/lib/librte_acl/acl_bld.c b/lib/librte_acl/acl_bld.c
index b06bbe9..d1f920b 100644 (file)
--- a/lib/librte_acl/acl_bld.c
+++ b/lib/librte_acl/acl_bld.c
@@ -778,9 +778,8 @@ acl_build_reset(struct rte_acl_ctx *ctx)
 }
 
 static void
-acl_gen_range(struct acl_build_context *context,
-       const uint8_t *hi, const uint8_t *lo, int size, int level,
-       struct rte_acl_node *root, struct rte_acl_node *end)
+acl_gen_full_range(struct acl_build_context *context, struct rte_acl_node *root,
+       struct rte_acl_node *end, int size, int level)
 {
        struct rte_acl_node *node, *prev;
        uint32_t n;
@@ -788,10 +787,71 @@ acl_gen_range(struct acl_build_context *context,
        prev = root;
        for (n = size - 1; n > 0; n--) {
                node = acl_alloc_node(context, level++);
-               acl_add_ptr_range(context, prev, node, lo[n], hi[n]);
+               acl_add_ptr_range(context, prev, node, 0, UINT8_MAX);
                prev = node;
        }
-       acl_add_ptr_range(context, prev, end, lo[0], hi[0]);
+       acl_add_ptr_range(context, prev, end, 0, UINT8_MAX);
+}
+
+static void
+acl_gen_range_mdl(struct acl_build_context *context, struct rte_acl_node *root,
+       struct rte_acl_node *end, uint8_t lo, uint8_t hi, int size, int level)
+{
+       struct rte_acl_node *node;
+
+       node = acl_alloc_node(context, level++);
+       acl_add_ptr_range(context, root, node, lo, hi);
+       acl_gen_full_range(context, node, end, size - 1, level);
+}
+
+static void
+acl_gen_range_low(struct acl_build_context *context, struct rte_acl_node *root,
+       struct rte_acl_node *end, const uint8_t *lo, int size, int level)
+{
+       struct rte_acl_node *node;
+       uint32_t n;
+
+       n = size - 1;
+       if (n == 0) {
+               acl_add_ptr_range(context, root, end, lo[0], UINT8_MAX);
+               return;
+       }
+
+       node = acl_alloc_node(context, level++);
+       acl_add_ptr_range(context, root, node, lo[n], lo[n]);
+
+       /* generate lower-bound sub-trie */
+       acl_gen_range_low(context, node, end, lo, n, level);
+
+       /* generate middle sub-trie */
+       if (n > 1 && lo[n - 1] != UINT8_MAX)
+               acl_gen_range_mdl(context, node, end, lo[n - 1] + 1, UINT8_MAX,
+                       n, level);
+}
+
+static void
+acl_gen_range_high(struct acl_build_context *context, struct rte_acl_node *root,
+       struct rte_acl_node *end, const uint8_t *hi, int size, int level)
+{
+       struct rte_acl_node *node;
+       uint32_t n;
+
+       n = size - 1;
+       if (n == 0) {
+               acl_add_ptr_range(context, root, end, 0, hi[0]);
+               return;
+       }
+
+       node = acl_alloc_node(context, level++);
+       acl_add_ptr_range(context, root, node, hi[n], hi[n]);
+
+       /* generate upper-bound sub-trie */
+       acl_gen_range_high(context, node, end, hi, n, level);
+
+       /* generate middle sub-trie */
+       if (n > 1 && hi[n - 1] != 0)
+               acl_gen_range_mdl(context, node, end, 0, hi[n - 1] - 1,
+                       n, level);
 }
 
 static struct rte_acl_node *
@@ -799,52 +859,56 @@ acl_gen_range_trie(struct acl_build_context *context,
        const void *min, const void *max,
        int size, int level, struct rte_acl_node **pend)
 {
-       int32_t n;
-       struct rte_acl_node *root;
-       const uint8_t *lo = min;
-       const uint8_t *hi = max;
+       int32_t k, n;
+       uint8_t hi_ff, lo_00;
+       struct rte_acl_node *node, *prev, *root;
+       const uint8_t *lo;
+       const uint8_t *hi;
+
+       lo = min;
+       hi = max;
 
-       *pend = acl_alloc_node(context, level+size);
+       *pend = acl_alloc_node(context, level + size);
        root = acl_alloc_node(context, level++);
+       prev = root;
 
-       if (lo[size - 1] == hi[size - 1]) {
-               acl_gen_range(context, hi, lo, size, level, root, *pend);
-       } else {
-               uint8_t limit_lo[64];
-               uint8_t limit_hi[64];
-               uint8_t hi_ff = UINT8_MAX;
-               uint8_t lo_00 = 0;
+       /* build common sub-trie till possible */
+       for (n = size - 1; n > 0 && lo[n] == hi[n]; n--) {
+               node = acl_alloc_node(context, level++);
+               acl_add_ptr_range(context, prev, node, lo[n], hi[n]);
+               prev = node;
+       }
 
-               memset(limit_lo, 0, RTE_DIM(limit_lo));
-               memset(limit_hi, UINT8_MAX, RTE_DIM(limit_hi));
+       /* no branch needed, just one sub-trie */
+       if (n == 0) {
+               acl_add_ptr_range(context, prev, *pend, lo[0], hi[0]);
+               return root;
+       }
 
-               for (n = size - 2; n >= 0; n--) {
-                       hi_ff = (uint8_t)(hi_ff & hi[n]);
-                       lo_00 = (uint8_t)(lo_00 | lo[n]);
-               }
+       /* gather information about divirgent paths */
+       lo_00 = 0;
+       hi_ff = UINT8_MAX;
+       for (k = n - 1; k >= 0; k--) {
+               hi_ff &= hi[k];
+               lo_00 |= lo[k];
+       }
 
-               if (hi_ff != UINT8_MAX) {
-                       limit_lo[size - 1] = hi[size - 1];
-                       acl_gen_range(context, hi, limit_lo, size, level,
-                               root, *pend);
-               }
+       /* generate left (lower-bound) sub-trie */
+       if (lo_00 != 0)
+               acl_gen_range_low(context, prev, *pend, lo, n + 1, level);
 
-               if (lo_00 != 0) {
-                       limit_hi[size - 1] = lo[size - 1];
-                       acl_gen_range(context, limit_hi, lo, size, level,
-                               root, *pend);
-               }
+       /* generate right (upper-bound) sub-trie */
+       if (hi_ff != UINT8_MAX)
+               acl_gen_range_high(context, prev, *pend, hi, n + 1, level);
 
-               if (hi[size - 1] - lo[size - 1] > 1 ||
-                               lo_00 == 0 ||
-                               hi_ff == UINT8_MAX) {
-                       limit_lo[size-1] = (uint8_t)(lo[size-1] + (lo_00 != 0));
-                       limit_hi[size-1] = (uint8_t)(hi[size-1] -
-                               (hi_ff != UINT8_MAX));
-                       acl_gen_range(context, limit_hi, limit_lo, size,
-                               level, root, *pend);
-               }
+       /* generate sub-trie in the middle */
+       if (lo[n] + 1 != hi[n] || lo_00 == 0 || hi_ff == UINT8_MAX) {
+               lo_00 = lo[n] + (lo_00 != 0);
+               hi_ff = hi[n] - (hi_ff != UINT8_MAX);
+               acl_gen_range_mdl(context, prev, *pend, lo_00, hi_ff,
+                       n + 1, level);
        }
+
        return root;
 }