From: Robert Sanford <[email protected]>
The trie keeps the index of an entry in the tbl8 array, the tbl8 group
number times 256 plus one address byte, in 32-bit variables in several
places. This breaks large tables in two steps.
In build_common_root(), the index returned by get_idx() was stored in
an int. Once the tbl8 group number reaches 2^23, the value goes negative
and is sign-extended when converted to the uint64_t index passed to
get_tbl_p_by_idx(), which yields a bogus table pointer. With random /128
routes and 4-byte next hops, adding routes crashes with SIGSEGV in
install_to_dp() after about 640,000 routes.
>From tbl8 group 2^24 on, the index no longer fits in 32 bits:
get_idx() computes it in 64 bits but returns a uint32_t, and
get_tbl_val_by_idx() and get_tbl_pos() take a uint32_t. The truncated
index points 2^24 groups too low, so routes are written into the wrong
tbl8 group and the add still returns 0. In a test with 1,360,000 random
/128 routes (17.6M tbl8 groups), every route added after tbl8 group 2^24
was allocated returned the default next hop on lookup, and deleting all
routes left 853,337 tbl8 groups allocated.
Use uint64_t for the tbl8 entry indexes in get_idx(),
build_common_root(), install_to_dp(), get_tbl_val_by_idx(),
get_tbl_pos() and get_psd_idx(). Keep a separate signed tbl8_idx for
the tbl8_alloc() result, which is negative on error, and cast it to
uint64_t before shifting it left, in build_common_root() and in
write_edge(). The shift was done in int, which can overflow before the
result is widened.
The tbl8 group number itself stays an int, as returned by tbl8_alloc().
trie_create() already limits num_tbl8 to 2^31 - 1 with 4-byte next
hops, and to 2^15 - 1 with 2-byte next hops, which cannot reach either
problem above.
With this change, the same test passes: every lookup returns the right
next hop, and no tbl8 group is left after deleting all routes.
Fixes: c3e12e0f0354 ("fib: add dataplane algorithm for IPv6")
Cc: [email protected]
Signed-off-by: Robert Sanford <[email protected]>
---
v3:
- Also widen the indexes in get_idx(), get_tbl_val_by_idx(),
get_tbl_pos(), get_psd_idx() and install_to_dp(), so tables with
2^24 or more tbl8 groups work too (suggested by Vladimir Medvedkin).
- Change the title, since the fix now covers more than the sign conversion.
- Rebase on 26.11-rc2.
v2: use a 12-character sha in the Fixes tag.
lib/fib/trie.c | 23 ++++++++++++-----------
lib/fib/trie.h | 8 ++++----
2 files changed, 16 insertions(+), 15 deletions(-)
diff --git a/lib/fib/trie.c b/lib/fib/trie.c
index 9ede1a5bf7..4346789972 100644
--- a/lib/fib/trie.c
+++ b/lib/fib/trie.c
@@ -257,8 +257,8 @@ tbl8_recycle(struct rte_trie_tbl *dp, void *par, uint64_t
tbl8_idx)
}
#define BYTE_SIZE 8
-static inline uint32_t
-get_idx(const struct rte_ipv6_addr *ip, uint32_t prev_idx, int bytes, int
first_byte)
+static inline uint64_t
+get_idx(const struct rte_ipv6_addr *ip, uint64_t prev_idx, int bytes, int
first_byte)
{
int i;
uint32_t idx = 0;
@@ -319,7 +319,8 @@ build_common_root(struct rte_trie_tbl *dp, const struct
rte_ipv6_addr *ip,
void *tbl_ptr = NULL;
uint64_t *cur_tbl;
uint64_t val;
- int i, j, idx, prev_idx = 0;
+ uint64_t idx, prev_idx = 0;
+ int i, j, tbl8_idx;
cur_tbl = dp->tbl24;
for (i = 3, j = 0; i <= common_bytes; i++) {
@@ -327,12 +328,12 @@ build_common_root(struct rte_trie_tbl *dp, const struct
rte_ipv6_addr *ip,
val = get_tbl_val_by_idx(cur_tbl, idx, dp->nh_sz);
tbl_ptr = get_tbl_p_by_idx(cur_tbl, idx, dp->nh_sz);
if ((val & TRIE_EXT_ENT) != TRIE_EXT_ENT) {
- idx = tbl8_alloc(dp, val);
- if (unlikely(idx < 0))
- return idx;
- write_to_dp(tbl_ptr, (idx << 1) |
+ tbl8_idx = tbl8_alloc(dp, val);
+ if (unlikely(tbl8_idx < 0))
+ return tbl8_idx;
+ write_to_dp(tbl_ptr, ((uint64_t)tbl8_idx << 1) |
TRIE_EXT_ENT, dp->nh_sz, 1);
- prev_idx = idx;
+ prev_idx = (uint64_t)tbl8_idx;
} else
prev_idx = val >> 1;
@@ -361,7 +362,7 @@ write_edge(struct rte_trie_tbl *dp, const uint8_t *ip_part,
uint64_t next_hop,
tbl8_idx = tbl8_alloc(dp, val);
if (tbl8_idx < 0)
return tbl8_idx;
- val = (tbl8_idx << 1)|TRIE_EXT_ENT;
+ val = ((uint64_t)tbl8_idx << 1) | TRIE_EXT_ENT;
}
p = get_tbl_p_by_idx(dp->tbl8, (tbl8_idx *
TRIE_TBL8_GRP_NUM_ENT) + *ip_part, dp->nh_sz);
@@ -448,8 +449,8 @@ install_to_dp(struct rte_trie_tbl *dp, const struct
rte_ipv6_addr *ledge,
uint8_t first_byte_idx = (common_bytes < 3) ? 0 : common_bytes;
uint8_t first_idx_len = (common_bytes < 3) ? 3 : 1;
- uint32_t left_idx = get_idx(ledge, 0, first_idx_len, first_byte_idx);
- uint32_t right_idx = get_idx(&redge, 0, first_idx_len, first_byte_idx);
+ uint64_t left_idx = get_idx(ledge, 0, first_idx_len, first_byte_idx);
+ uint64_t right_idx = get_idx(&redge, 0, first_idx_len, first_byte_idx);
ent = get_tbl_p_by_idx(common_root_tbl, left_idx, dp->nh_sz);
ret = write_edge(dp, &ledge->a[first_tbl8_byte + !(common_bytes < 3)],
diff --git a/lib/fib/trie.h b/lib/fib/trie.h
index c34cc2c057..e0f53e0c47 100644
--- a/lib/fib/trie.h
+++ b/lib/fib/trie.h
@@ -80,19 +80,19 @@ lookup_msk(uint8_t nh_sz)
}
static inline uint8_t
-get_psd_idx(uint32_t val, uint8_t nh_sz)
+get_psd_idx(uint64_t val, uint8_t nh_sz)
{
return val & ((1 << (3 - nh_sz)) - 1);
}
-static inline uint32_t
-get_tbl_pos(uint32_t val, uint8_t nh_sz)
+static inline uint64_t
+get_tbl_pos(uint64_t val, uint8_t nh_sz)
{
return val >> (3 - nh_sz);
}
static inline uint64_t
-get_tbl_val_by_idx(uint64_t *tbl, uint32_t idx, uint8_t nh_sz)
+get_tbl_val_by_idx(uint64_t *tbl, uint64_t idx, uint8_t nh_sz)
{
return ((tbl[get_tbl_pos(idx, nh_sz)] >> (get_psd_idx(idx, nh_sz) *
bits_in_nh(nh_sz))) & lookup_msk(nh_sz));
--
2.34.1
