[PATCH v2 1/5] rib: fix undefined behavior in bit test

[Robert Sanford]

From: Robert Sanford <rsanford at akamai.com>

The tree walk in rte_rib.c tests the bit below a node's depth with
1 << (31 - depth). For a node at depth 0, which exists for a default
route or for a common parent of routes in both halves of the address
space, that is 1 << 31 on a signed int, which is undefined behavior.
UBSan reports:

  rte_rib.c:82:18: runtime error: left shift of 1 by 31 places
  cannot be represented in type 'int'

and the same at lines 311 and 343. No existing unit test adds a
depth-0 route, so this was not caught before. The new test/fib
wraparound test in this series does.

Use an unsigned constant in all four bit tests. The shift count is
between 0 and 31 at each of them.

Fixes: 5a5793a5ffa2 ("rib: add RIB library")
Cc: stable at dpdk.org

Signed-off-by: Robert Sanford <rsanford at akamai.com>
---
v2: new patch in this series.

 lib/rib/rte_rib.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/lib/rib/rte_rib.c b/lib/rib/rte_rib.c
index 046db131ca..43d5ab1498 100644
--- a/lib/rib/rte_rib.c
+++ b/lib/rib/rte_rib.c
@@ -79,7 +79,7 @@ get_nxt_node(struct rte_rib_node *node, uint32_t ip)
 {
 	if (node->depth == RIB_MAXDEPTH)
 		return NULL;
-	return (ip & (1 << (31 - node->depth))) ? node->right : node->left;
+	return (ip & (1U << (31 - node->depth))) ? node->right : node->left;
 }
 
 static struct rte_rib_node *
@@ -308,7 +308,7 @@ rte_rib_insert(struct rte_rib *rib, uint32_t ip, uint8_t depth)
 		if ((d >= depth) || !is_covered(ip, (*tmp)->ip, d))
 			break;
 		prev = *tmp;
-		tmp = (ip & (1 << (31 - d))) ? &(*tmp)->right : &(*tmp)->left;
+		tmp = (ip & (1U << (31 - d))) ? &(*tmp)->right : &(*tmp)->left;
 	}
 	/* closest node found, new_node should be inserted in the middle */
 	common_depth = RTE_MIN(depth, (*tmp)->depth);
@@ -319,7 +319,7 @@ rte_rib_insert(struct rte_rib *rib, uint32_t ip, uint8_t depth)
 	common_prefix = ip & rte_rib_depth_to_mask(common_depth);
 	if ((common_prefix == ip) && (common_depth == depth)) {
 		/* insert as a parent */
-		if ((*tmp)->ip & (1 << (31 - depth)))
+		if ((*tmp)->ip & (1U << (31 - depth)))
 			new_node->right = *tmp;
 		else
 			new_node->left = *tmp;
@@ -340,7 +340,7 @@ rte_rib_insert(struct rte_rib *rib, uint32_t ip, uint8_t depth)
 		common_node->parent = (*tmp)->parent;
 		new_node->parent = common_node;
 		(*tmp)->parent = common_node;
-		if ((new_node->ip & (1 << (31 - common_depth))) == 0) {
+		if ((new_node->ip & (1U << (31 - common_depth))) == 0) {
 			common_node->left = new_node;
 			common_node->right = *tmp;
 		} else {
-- 
2.34.1