[PATCH v3] fib6: fix overflow of tbl8 indexes

[Medvedkin, Vladimir]

Acked-by: Vladimir Medvedkin <vladimir.medvedkin at intel.com>

On 11/3/2026 12:49 AM, Robert Sanford wrote:
> From: Robert Sanford <rsanford at akamai.com>
>
> 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: stable at dpdk.org
>
> Signed-off-by: Robert Sanford <rsanford at akamai.com>
> ---
> 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));

-- 
Regards,
Vladimir