[RFC PATCH v2 0/7] VRF support in FIB library

Vladimir Medvedkin medvedkinv at gmail.com
Sun Nov 22 16:27:53 CET 2026


Hi Maxime,

пт, 13 нояб. 2026 г. в 00:22, Maxime Leroy <maxime at leroys.fr>:

> Hi Vladimir,
>
> On Wed, Oct 14, 2026 at 8:39 PM Vladimir Medvedkin
> <vladimir.medvedkin at intel.com> 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)


I still don't understand why this is a problem


> , 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.
>

Correct, and I'm going to fix this issue by making a shared rib_node pool
across all RIBs


>
> 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.
>

I don't think this is a big problem. The internal implementation already
has RCU support.


>
> IPv6 remains unsupported, and neither approach provides a shared
> resource pool across IPv4 and IPv6 FIBs.
>

Yes, IPv6 support is not included in this RFC, as I mentioned in the cover
letter, although there is preliminary support in the internal
implementation. At the moment I don't see any strong reason to share
resource pools across address families.


>
> 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?
>

This series is not just about mixed-VRF bulk lookup, this series is about
internal representations and algorithms. V1 was mostly about API and there
was reasonable criticism regarding memory consumption. Here this issue was
addressed with increased internal complexity.

I'm not sure this implementation would avoid indirection layer, it just
moves it to the lookup function as dps argument.
Your suggestion does not solve the memory consumption issue with many small
VRFs. I also doubt it would have a reasonable performance.


>
> Regards,
>
> Maxime
>


-- 
Regards,
Vladimir
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mails.dpdk.org/archives/dev/attachments/20261122/fd6522d8/attachment-0001.htm>


More information about the dev mailing list