Hi Vladimir,
On Wed, Oct 14, 2026 at 8:39 PM Vladimir Medvedkin
<[email protected]> wrote:
>
> This series adds multi-VRF support to the IPv4 FIB, allowing a single FIB
> instance to host multiple isolated routing tables.
>
> Today a FIB instance is a single routing table, so an application serving
> several VRFs needs one FIB per VRF. In a burst oriented datapath packets of
> one burst can belong to different VRFs, and the application either does
> per-packet lookups in different FIBs or regroups the burst by VRF before
> the lookup. Both are expensive. With this series all the VRFs live in one
> FIB, the bulk lookup takes a VRF ID per address, and the existing API
> operates on VRF 0.
>
> v1 replicated the 16M entry tbl24 per VRF. That kept the lookup on par with
> the single VRF case, but memory grew linearly with the number of VRFs,
> which was the main concern raised on v1. v2 resolves the issue by adding
> of two dataplane algorithms with different memory/lookup trade-offs.
>
> DIR8-16-8 is a new three level variant of DIR-24-8 with 8, 16 and 8 bit
> strides. Only the 256 entry root table (2 KB) is replicated per VRF; the
> tbl16 and tbl8 groups come from pools shared by all the VRFs, so memory
> follows the routes actually installed rather than the number of VRFs. The
> cost is an extra memory access for prefixes longer than /8.
>
> DIR-24-8 gets multi-VRF support by resolving the VRF after the longest
> prefix match, along the lines Konstantin suggested on v1. Instead of a
> vector of next hops per prefix, a single tbl24_8 shared by all the VRFs
> returns an internal prefix ID, and a hash table keyed by {VRF, prefix ID}
> returns the next hop, a miss meaning the VRF default next hop. The aim is
> to resolve the VRF with a single memory access, so buckets hold 8 records
> and there is no probing beyond the bucket.
>
> Such a table only works if the control path can keep buckets from
> overflowing while the hash stays cheap on the datapath. Since the prefix
> ID is internal, the library can pick it so that the records of a prefix
> land in buckets with free room. Collisions are chosen deliberately, so they
> are not a security concern, but finding them has to be cheap. Toeplitz was
> the first candidate: its structure is well studied and the thash library
> already knows how to find collisions, but it is only fast with GFNI. CRC
> has the same linear properties, is trivially inverted and is hardware
> accelerated on x86 and Arm, so CRC32C is used. Linearity also places the
> buckets of one prefix in different VRFs at fixed XOR offsets from each
> other, so a candidate prefix ID is checked for all the VRFs referencing
> the prefix at once, and these records never share a bucket. If a bucket
> fills up anyway, a prefix already in it is renumbered to make room.
>
> The price of the shared table is paid on the control path: a route in one
> VRF needs a record for every more specific prefix installed below it by
> other VRFs. Default routes are excluded, they map onto the per-VRF default
> next hop.
>
> The two algorithms target different deployments. DIR8-16-8 fits a limited
> number of VRFs (tens to hundreds) carrying large tables, up to a BGP full
> view each. The hash based DIR-24-8 fits one large VRF alongside hundreds
> or thousands of small ones.
>
> test-fib gets a VRF mode, including a profile with a full view in VRF 0 and
> smaller VRFs made of random subsets of it. The first three patches are fixes
> found along the way and are independent of the rest.
>
> Not done yet:
> - IPv6. The VRF bookkeeping of the hash based scheme is address family
> agnostic and is meant to be reused by TRIE.
> - RCU support for multi-VRF DIR-24-8.
>
> Vladimir Medvedkin (7):
> fib: fix return value of a nexthop update
> app/test-fib: fix lookup of the last burst
> app/test-fib: fix size of the tables for large counts
> fib: add DIR8-16-8 algorithm
> fib: add multi-VRF support
> fib: split DIR24-8 table update from the FIB wrapper
> fib: add hash based VRF support for DIR24-8
>
> app/test-fib/main.c | 673 ++++++++++---
> app/test/test_fib.c | 1001 ++++++++++++++++++-
> app/test/test_fib_perf.c | 440 +++------
> app/test/test_fib_routes.h | 282 ++++++
> doc/guides/prog_guide/fib_lib.rst | 66 ++
> doc/guides/rel_notes/release_26_11.rst | 21 +
> lib/fib/dir24_8.c | 34 +-
> lib/fib/dir24_8.h | 43 +-
> lib/fib/dir24_8_avx512.c | 18 +-
> lib/fib/dir24_8_avx512.h | 32 +-
> lib/fib/dir24_8_rvv.c | 3 +-
> lib/fib/dir24_8_rvv.h | 16 +-
> lib/fib/dir24_8_vrf.c | 290 ++++++
> lib/fib/dir24_8_vrf.h | 60 ++
> lib/fib/dir8_16_8.c | 665 +++++++++++++
> lib/fib/dir8_16_8.h | 192 ++++
> lib/fib/dir8_16_8_avx512.c | 183 ++++
> lib/fib/dir8_16_8_avx512.h | 24 +
> lib/fib/fib_vrf.c | 1256 ++++++++++++++++++++++++
> lib/fib/fib_vrf.h | 277 ++++++
> lib/fib/fib_vrf_avx512.c | 142 +++
> lib/fib/meson.build | 22 +-
> lib/fib/rte_fib.c | 249 ++++-
> lib/fib/rte_fib.h | 127 ++-
> 24 files changed, 5593 insertions(+), 523 deletions(-)
> create mode 100644 app/test/test_fib_routes.h
> create mode 100644 lib/fib/dir24_8_vrf.c
> create mode 100644 lib/fib/dir24_8_vrf.h
> create mode 100644 lib/fib/dir8_16_8.c
> create mode 100644 lib/fib/dir8_16_8.h
> create mode 100644 lib/fib/dir8_16_8_avx512.c
> create mode 100644 lib/fib/dir8_16_8_avx512.h
> create mode 100644 lib/fib/fib_vrf.c
> create mode 100644 lib/fib/fib_vrf.h
> create mode 100644 lib/fib/fib_vrf_avx512.c
>
> --
> 2.43.0
>
Thanks for the v2. It addresses the large TBL24 memory footprint of
v1, but I think several of my original concerns remain.
DIR8-16-8 is essentially a three-level lookup with an additional
memory access for prefixes longer than /8. While the TBL16 and TBL8
pools are shared across VRFs, their capacities still have to be
provisioned upfront. There is also a 2 KB root table per configured
VRF, plus a 512 KB TBL16 group for each /8 a VRF uses. A full-view VRF
has routes longer than /8 in most /8s, so it needs a TBL16 group for
most of them: close to the memory of a TBL24, with one more lookup
level.
More importantly, the design still relies on dense VRF IDs in the
range [0, max_vrfs), with a separate RIB per VRF. Each RIB is created
upfront in rte_fib_create() with the same max_routes capacity, which
still means substantial memory overhead for deployments with one
full-view VRF and hundreds of small or empty ones.
The hash-based DIR24-8 avoids the extra trie level, but at the cost of
considerably more control-plane complexity: prefix IDs, bucket
placement constraints, prefix renumbering, and additional records for
overlapping prefixes across VRFs. RCU support is also still missing in
this mode, and renumbering looks hard to combine with it: old hash
entries would have to stay visible to concurrent readers until a grace
period has elapsed, which temporarily increases bucket occupancy.
IPv6 remains unsupported, and neither approach provides a shared
resource pool across IPv4 and IPv6 FIBs.
I would like to suggest an alternative that keeps one FIB per VRF and
still provides the mixed-VRF bulk lookup this series is after. The
idea is a small group object holding what the FIBs have in common
(type, flags, next hop size), which a FIB joins at creation:
grp = rte_fib_group_create(&grp_conf);
conf.group = grp;
fib = rte_fib_create(name, socket_id, &conf);
rte_fib_group_lookup_bulk(grp, dps, ips, next_hops, n);
dps[i] would be the rte_fib_get_dp() pointer of the FIB to use for ips[i].
On v1 you objected that allocating one TBL24 per VRF on demand would
add an indirection layer to the lookup. This would avoid it: in
DIR24-8 the TBL24 is embedded in the dataplane struct, so it sits at a
fixed offset from the pointer passed by the caller. There is no table
of pointers to go through: the TBL24 access needs no additional level
of indirection, and the existing single-FIB path is untouched.
Compared to your API, your "fib" becomes the group and your "vrf"
becomes a FIB, identified by a pointer instead of a dense index. FIBs
are created on demand, each with its own RIB size, and nothing is
allocated for VRFs that do not exist. The same idea should apply to
the IPv6 trie, which embeds its TBL24 the same way.
This does not reduce the per-VRF TBL24 by itself; that is where a
compact algorithm such as DIR8-16-8, used as a regular single-VRF
backend, would fit. It is also independent of my TBL8 pool RFC, which
addresses the sizing of num_tbl8.
What do you think?
Regards,
Maxime
