[PATCH net] ipv4: fib_trie: prevent speculative out-of-bounds child access

[PATCH net] ipv4: fib_trie: prevent speculative out-of-bounds child access

[Daniël Trujillo via B4 Relay]

From: Daniël Trujillo <datrujillo@nvidia.com>

fib_table_lookup() checks the child index against the bounds before
passing it to get_child_rcu().

The index is derived from the lookup key, which in turn is derived from
flp->daddr. A userspace process can therefore influence the index by
triggering lookups for chosen destination IPv4 addresses.

If this bounds check is mispredicted as in-bounds, an out-of-bounds index
can be transiently passed to get_child_rcu(). The value loaded beyond the
child array is then treated as a node pointer. The next loop iteration
dereferences that transient pointer through get_cindex(), causing a
page-table walk whose cache footprint can leak (parts of) the pointer.

Sanitize the index with array_index_nospec() before accessing the child
array.

Fixes: 9f9e636d4f89 ("fib_trie: Optimize fib_table_lookup to avoid wasting time on loops/variables")
Cc: stable@vger.kernel.org
Signed-off-by: Daniël Trujillo <datrujillo@nvidia.com>
---
 net/ipv4/fib_trie.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 248514dce0cd..bd8a368c5502 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -61,6 +61,7 @@
 #include <linux/export.h>
 #include <linux/vmalloc.h>
 #include <linux/notifier.h>
+#include <linux/nospec.h>
 #include <net/net_namespace.h>
 #include <net/inet_dscp.h>
 #include <net/ip.h>
@@ -1474,6 +1475,7 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
 			cindex = index;
 		}
 
+		index = array_index_nospec(index, 1ul << n->bits);
 		n = get_child_rcu(n, index);
 		if (unlikely(!n))
 			goto backtrace;

---
base-commit: 37f12441f557468a56c1e27790413aa78c82afa2
change-id: 20261008-fib-trie-nospec-5c76028c8e7c

Best regards,
--  
Daniël Trujillo <datrujillo@nvidia.com>

Re: [PATCH net] ipv4: fib_trie: prevent speculative out-of-bounds child access

[netdev-bot+sinfo]

Hi!

This is an automated message. This series looks like a fix, but its
commit messages seem to be missing some information:

 - How the issue was discovered, e.g. hit in production, hit during
   development, syzbot report, manual code inspection, LLM or static
   analysis tool scan.

 - Whether the issue was actually triggered, or is only theoretical
   (e.g. found by code inspection). If it was triggered please include
   the symptoms, like the stack trace or error messages.

Please do not repost the series just to address the above. Instead,
reply to this email with the missing information, so that reviewers
can take it into account. If the series needs another revision for
other reasons, please include the information in the commit messages
then.

The evaluation is done by an LLM so it may be wrong, if you think
that is the case please reply and explain.

Re: [PATCH net] ipv4: fib_trie: prevent speculative out-of-bounds child access

[Eric Dumazet]

Le ven. 9 oct. 2026 à 00:10, Daniël Trujillo via B4 Relay
<devnull+datrujillo.nvidia.com@kernel.org> a écrit :
>
> From: Daniël Trujillo <datrujillo@nvidia.com>
>
> fib_table_lookup() checks the child index against the bounds before
> passing it to get_child_rcu().
>
> The index is derived from the lookup key, which in turn is derived from
> flp->daddr. A userspace process can therefore influence the index by
> triggering lookups for chosen destination IPv4 addresses.
>
> If this bounds check is mispredicted as in-bounds, an out-of-bounds index
> can be transiently passed to get_child_rcu(). The value loaded beyond the
> child array is then treated as a node pointer. The next loop iteration
> dereferences that transient pointer through get_cindex(), causing a
> page-table walk whose cache footprint can leak (parts of) the pointer.

Has this been demonstrated, or is it the output of a static tool ?

key, pos and bits all live in the first 8 bytes of struct key_vector,
so the bound can not be made slow relative to the index by evicting
a cache line. The conditional branch should resolve a couple of cycles
after the out-of-bounds load is issued, before a dependent dereference
can start.

For a patch targeting net and stable, in the IPv4 lookup fast path,
we would like the changelog to say what was actually observed.

>
> Sanitize the index with array_index_nospec() before accessing the child
> array.
>
> Fixes: 9f9e636d4f89 ("fib_trie: Optimize fib_table_lookup to avoid wasting time on loops/variables")
> Cc: stable@vger.kernel.org
> Signed-off-by: Daniël Trujillo <datrujillo@nvidia.com>
> ---
>  net/ipv4/fib_trie.c | 2 ++
>  1 file changed, 2 insertions(+)
>
> diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
> index 248514dce0cd..bd8a368c5502 100644
> --- a/net/ipv4/fib_trie.c
> +++ b/net/ipv4/fib_trie.c
> @@ -61,6 +61,7 @@
>  #include <linux/export.h>
>  #include <linux/vmalloc.h>
>  #include <linux/notifier.h>
> +#include <linux/nospec.h>
>  #include <net/net_namespace.h>
>  #include <net/inet_dscp.h>
>  #include <net/ip.h>
> @@ -1474,6 +1475,7 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
>                         cindex = index;
>                 }
>
> +               index = array_index_nospec(index, 1ul << n->bits);
>                 n = get_child_rcu(n, index);
>                 if (unlikely(!n))
>                         goto backtrace;


This is not complete.

cindex has been set from the unclamped index just above. If the
(!n) branch is predicted taken under the same mispredicted bounds
check, the backtrace path does :

cindex &= cindex - 1;
cptr = &pn->tnode[cindex];
...
n = rcu_dereference(*cptr);

and the result is dereferenced at the top of step 2
(prefix_mismatch(key, n), n->slen, n->pos).

This is the same pattern you describe : one out-of-bounds load, then
a dereference of the loaded value.

The clamp needs to be done before cindex is recorded, and can stay
after the IS_LEAF() test so that leaf hits do not pay for it :

@@ -1465,7 +1466,9 @@ int fib_table_lookup(struct fib_table *tb, const
struct flowi4 *flp,
  /* we have found a leaf. Prefixes have already been compared */
  if (IS_LEAF(n))
  goto found;

+ index = array_index_nospec(index, 1ul << n->bits);
+
  /* only record pn and cindex if we are going to be chopping
  * bits later.  Otherwise we are just wasting cycles.
  */

Also, fib_find_node() has the exact same construct (same bounds check,
then get_child_rcu(n, index) on the next iteration), and is called
with a user provided key from fib_table_insert() and fib_table_delete().
RTM_NEWROUTE / RTM_DELROUTE only need CAP_NET_ADMIN in the netns owner
user namespace. This runs under RTNL, there is no performance concern
there.

Please also take a look at leaf_walk_rcu() (cindex >> pn->bits), and
say in the changelog why it is or is not affected.

>
> ---
> base-commit: 37f12441f557468a56c1e27790413aa78c82afa2
> change-id: 20261008-fib-trie-nospec-5c76028c8e7c
>
> Best regards,
> --
> Daniël Trujillo <datrujillo@nvidia.com>
>
>

Re: [PATCH net] ipv4: fib_trie: prevent speculative out-of-bounds child access

[Daniel Trujillo]

On Fri, Oct 09, 2026 at 12:25:43AM +0200, Eric Dumazet wrote:
> Le ven. 9 oct. 2026 à 00:10, Daniël Trujillo via B4 Relay
> <devnull+datrujillo.nvidia.com@kernel.org> a écrit :
> >
> > From: Daniël Trujillo <datrujillo@nvidia.com>
> >
> > fib_table_lookup() checks the child index against the bounds before
> > passing it to get_child_rcu().
> >
> > The index is derived from the lookup key, which in turn is derived from
> > flp->daddr. A userspace process can therefore influence the index by
> > triggering lookups for chosen destination IPv4 addresses.
> >
> > If this bounds check is mispredicted as in-bounds, an out-of-bounds index
> > can be transiently passed to get_child_rcu(). The value loaded beyond the
> > child array is then treated as a node pointer. The next loop iteration
> > dereferences that transient pointer through get_cindex(), causing a
> > page-table walk whose cache footprint can leak (parts of) the pointer.
> 
> Has this been demonstrated, or is it the output of a static tool ?
> 
> key, pos and bits all live in the first 8 bytes of struct key_vector,
> so the bound can not be made slow relative to the index by evicting
> a cache line. The conditional branch should resolve a couple of cycles
> after the out-of-bounds load is issued, before a dependent dereference
> can start.
> 
> For a patch targeting net and stable, in the IPv4 lookup fast path,
> we would like the changelog to say what was actually observed.

This was not the output of a static analysis tool. The gadget was found
during Spectre-v1 research, and its exploitability was assessed using a
test harness for potential gadgets.

Leakage was demonstrated using instrumentation that delays branch
resolution through a CLFLUSH before the mispredicted branch. In that
setup, a userspace-controlled IPv4 lookup key was able to transiently
load out-of-bounds memory. The transient use of the loaded value as a
pointer caused a data-dependent cache footprint that was recoverable
from userspace using Prime+Probe. Adding
array_index_nospec() removed the observed signal.

Simply evicting the cache line before the lookup is indeed not
sufficient to widen the speculation window naturally, since
get_cindex(key, n) brings n->bits into the cache. An attacker would
therefore need to delay branch resolution some other way, for example
through a precisely timed eviction after get_cindex(key, n), or by
otherwise creating contention that delays branch resolution. I have not
demonstrated this end-to-end without instrumentation.

> This is not complete.
> 
> cindex has been set from the unclamped index just above. If the
> (!n) branch is predicted taken under the same mispredicted bounds
> check, the backtrace path does :
> 
> cindex &= cindex - 1;
> cptr = &pn->tnode[cindex];
> ...
> n = rcu_dereference(*cptr);
> 
> and the result is dereferenced at the top of step 2
> (prefix_mismatch(key, n), n->slen, n->pos).
> 
> This is the same pattern you describe : one out-of-bounds load, then
> a dereference of the loaded value.
> 
> The clamp needs to be done before cindex is recorded, and can stay
> after the IS_LEAF() test so that leaf hits do not pay for it :
> 
> @@ -1465,7 +1466,9 @@ int fib_table_lookup(struct fib_table *tb, const
> struct flowi4 *flp,
>   /* we have found a leaf. Prefixes have already been compared */
>   if (IS_LEAF(n))
>   goto found;
> 
> + index = array_index_nospec(index, 1ul << n->bits);
> +
>   /* only record pn and cindex if we are going to be chopping
>   * bits later.  Otherwise we are just wasting cycles.
>   */

Thanks for pointing this out. I will send a v2 after the 24h wait that
moves array_index_nospec() before cindex is set.

> Also, fib_find_node() has the exact same construct (same bounds check,
> then get_child_rcu(n, index) on the next iteration), and is called
> with a user provided key from fib_table_insert() and fib_table_delete().
> RTM_NEWROUTE / RTM_DELROUTE only need CAP_NET_ADMIN in the netns owner
> user namespace. This runs under RTNL, there is no performance concern
> there.
> 
> Please also take a look at leaf_walk_rcu() (cindex >> pn->bits), and
> say in the changelog why it is or is not affected.

Will do and address both in v2.