> > 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]>
> Acked-by: Vladimir Medvedkin <[email protected]>
Applied, thanks.
