TCP-AO implementation stores Master Key Tuples (MKTs) in an unsorted
doubly-linked list (ao_info->head) and inserts new keys at the head.
When looking up a key, __tcp_ao_do_lookup() walks this list and returns
the first match it finds.

Because the list is unsorted, a newer, less-specific key can shadow an
older, more-specific key if it happens to be inserted later. This leads
to incorrect key selection in two scenarios:

1. VRF Shadowing: A wildcard VRF key (not bound to an interface) added
   after a VRF-specific key will shadow the VRF-specific key for traffic
   arriving on that VRF.
2. Prefix Shadowing: A less-specific prefix key (e.g., /24) added after
   a more-specific prefix key (e.g., /32) will shadow the more-specific
   key during outbound connection establishment.

Unlike TCP MD5, which walks the entire list and evaluates the "best
match" using better_md5_match(), TCP-AO expects the list order to
determine precedence.

Fix this by implementing sorted insertion in tcp_ao_link_mkt(). Keys
are inserted in descending order of specificity:
  - VRF-bound keys take precedence over unbound keys.
  - Longer prefix matches (LPM) take precedence over shorter ones.

This preserves the performance of the lockless RX lookup path (early
return on first match) while ensuring correct precedence.

Fixes: 4954f17ddefc ("net/tcp: Introduce TCP_AO setsockopt()s")
Signed-off-by: Eric Dumazet <edumazet@google.com>
Assisted-by: Gemini:gemini-3.1-pro
---
 net/ipv4/tcp_ao.c | 27 ++++++++++++++++++++++++++-
 1 file changed, 26 insertions(+), 1 deletion(-)

diff --git a/net/ipv4/tcp_ao.c b/net/ipv4/tcp_ao.c
index 2f69bcecae78a677f33033a2d30e09a8ff858ad8..2d10fb1dd4cf87cc79ef5b5ead80eb3048218250 100644
--- a/net/ipv4/tcp_ao.c
+++ b/net/ipv4/tcp_ao.c

@@ -341,9 +341,34 @@ static struct tcp_ao_info *tcp_ao_alloc_info(gfp_t flags)
 	return ao;
 }
 
+static bool tcp_ao_key_is_more_specific(const struct tcp_ao_key *a,
+					const struct tcp_ao_key *b)
+{
+	bool a_vrf = !!(a->keyflags & TCP_AO_KEYF_IFINDEX);
+	bool b_vrf = !!(b->keyflags & TCP_AO_KEYF_IFINDEX);
+
+	if (a_vrf != b_vrf)
+		return a_vrf; /* VRF-bound is more specific */
+
+	return a->prefixlen > b->prefixlen; /* Longer prefix is more specific */
+}
+
 static void tcp_ao_link_mkt(struct tcp_ao_info *ao, struct tcp_ao_key *mkt)
 {
-	hlist_add_head_rcu(&mkt->node, &ao->head);
+	struct tcp_ao_key *pos;
+	struct hlist_node *last = NULL;
+
+	hlist_for_each_entry(pos, &ao->head, node) {
+		if (tcp_ao_key_is_more_specific(mkt, pos)) {
+			hlist_add_before_rcu(&mkt->node, &pos->node);
+			return;
+		}
+		last = &pos->node;
+	}
+	if (last)
+		hlist_add_behind_rcu(&mkt->node, last);
+	else
+		hlist_add_head_rcu(&mkt->node, &ao->head);
 }
 
 static struct tcp_ao_key *tcp_ao_copy_key(struct sock *sk,

-- 
2.55.0.rc0.799.gd6f94ed593-goog