[RFC] ipv6: preserving route lookup provenance in dst caches

Hi,

While fixing an ovpn IPv6 dst-cache bug, I found what appears to be a
more general race between IPv6 route lookup and cache publication.
Following a suggestion from Sabrina during review, I would like to get
feedback on the intended FIB6 serial-number model and on a possible
kernel-wide fix before attempting a fairly invasive refactoring.

The race
========

For routes without their own rt6_info::sernum, rt6_get_cookie returns
the current fn_sernum of the fib6_node associated with the route's
fib6_info. Persistent caches generally obtain a dst first and sample
this cookie later when publishing it.

This permits the following sequence:

  CPU0                                  CPU1
  ----                                  ----
  ip6_dst_lookup_flow()
    returns Dold

                                        add a more-specific route (for example a blackhole /128)
                                        stamp the affected node and its parents C0 -> C1

  rt6_get_cookie(Dold)
    reads C1 from Dold->from's node

  publish (Dold, C1)

The next dst_check(Dold, C1) compares C1 with the same node's current
fn_sernum, accepts Dold and can continue bypassing the more-specific
route indefinitely. This is different from the normal bounded case in
which one packet uses the result of a lookup concurrent with a FIB
update because the stale result has been paired with a newer validation
token and preserved for future packets.

I reproduced this in ovpn by inserting a delay after
ip6_dst_lookup_flow, adding a more-specific IPv6 blackhole route in the
window and then letting dst_cache_set_ip6 sample the cookie. The cached
route continued to bypass the blackhole.

ovpn can avoid the problem locally by bracketing its lookup with
rt_genid_ipv6 reads and not populating the cache if the generation
changes, as implemented in [1]. However, the same late rt6_get_cookie
pattern exists in several persistent caches, including socket TX and RX
caches, XFRM route/path cookies, dst_cache users, SCTP, flowtable, IPVS
and RXE. Fixing every user independently would also leave future users
exposed.

Proposed model
==============

The cookie is a property of the lookup which selected a dst, rather than
a property that can safely be recovered from a shared dst at some later
time. I'd therefore suggest making cache-producing route lookups return
the pair explicitly, for example:

  struct dst_lookup_result {
          struct dst_entry *dst;
          u32 cookie;
  };

Pointer-only APIs could remain as wrappers for one-shot users which do
not persist the result.

For FIB6 policy lookup, the result would be constructed approximately as
follows:

  gen0 = rt_genid_ipv6(net);
  smp_rmb();

  dst = fib6_rule_lookup(..., gen0);
  cookie = rt6_get_cookie(dst_rt6_info(dst));

  smp_rmb();
  gen1 = rt_genid_ipv6(net);

  result.dst = dst;
  result.cookie = gen0 == gen1 ? cookie : gen0;

The result remains usable for the current packet when the generation
changes. Returning gen0 as the cache cookie makes the result fail later
equality validation, unless the selected node's serial is gen0.

The latter case should also be safe, provided the following writer-side
contract holds:

  1. a routing-visible update is published before its serial is
     allocated and stamped;
  2. node serials are not overwritten with an older allocation;
  3. every invalidation represented by fn_sernum uses a freshly
     allocated serial.

rt_genid_ipv6 reads the same fib6_sernum counter from which node serials
are allocated. Therefore, if a node still has serial gen0, any update
represented by gen0 was visible before the lookup. A relevant later
update must stamp the node with a different serial and make the cached
result fail validation. An unrelated update can conservatively make the
result miss, but it cannot bless a stale route.

Writer-side prerequisites
=========================

Two current paths appear incompatible with that contract.

First, fib6_flush_trees allocates one serial before walking all IPv6
tables, while __fib6_clean_all locks the tables one at a time. A writer
can stamp a not-yet-walked table with a newer serial, after which
fib6_clean_node overwrites it with the older flush serial. For example:

  flush allocates 10 and starts walking table A
  route insertion in table B allocates and stamps 11
  flush reaches table B and overwrites 11 with 10

That regression could revalidate a result carrying fallback cookie 10.
One possible fix would be to allocate the flush serial after acquiring
each table lock, so no writer for that table can allocate a newer serial
before the walk stamps it. This also avoids introducing wrap-aware
serial ordering.

Second, ip6_link_failure writes -1 directly into fn_sernum for a default
route. I think this should instead take the appropriate table lock on
this failure path and perform a normal fresh node/ancestor serial
update.

Routes with rt6_info::sernum
============================

Routes with a nonzero rt6_info::sernum need special handling because
ip6_dst_check currently ignores the supplied cookie and validates them
against the global generation. The pre-lookup generation would need to
be used when obtaining or materializing these per-CPU routes, and
validation should also require the route serial to match the lookup
cookie.

Propagating the result
======================

The pair would have to follow whichever dst ultimately wins through the
higher-level IPv6 APIs, including source-address selection, a possible
second output lookup and optimistic-DAD route replacement. Persistent
caches would store the supplied cookie instead of calling rt6_get_cookie
after the lookup.

XFRM would propagate lookup results through bundle construction, pairing
cached route and path pointers with their cookies instead of sampling
those cookies after the fact.

Two skb handoff points need separate handling.

TCP and UDP obtain an input dst from the skb but sample its cookie only
later when installing sk_rx_dst. A fresh coherent lookup at cache
installation appears less invasive than adding the cookie to every skb.
The sk_rx_dst pointer, cookie and (for TCP) ingress ifindex also form a
logical cache entry and could be published together as an immutable RCU
object.

Flowtable has a similar skb handoff point for the observed direction,
while the opposite direction already comes from a fresh nf_route lookup.
Performing a fresh route lookup for the observed direction at flow
installation would avoid adding provenance storage to struct sk_buff.

Questions
=========

1. Is this race already known, or is there an invariant that makes late
   cookie sampling harmless here? The number of users following this
   pattern makes me wonder whether I have missed some intended
   semantics.

2. Does the proposed approach, including the (dst, cookie) result and
   the implementation details outlined above, look sound, or is there a
   simpler way to preserve route lookup provenance across these users?

I have not started implementing this larger design yet. I wanted to
check the model and expected scope first, rather than produce a large
series based on assumptions that are currently not documented.

[1] https://lore.kernel.org/openvpn-devel/25d830e082b03afb4615aaeed6e0dc1d1370ecbc.1785308184.git.ralf@mandelbit.com/

Thanks,

-- 
Ralf Lici
Mandelbit Srl