[PATCH ipsec-next 0/4] xfrm: speed up policy insertions

[PATCH ipsec-next 0/4] xfrm: speed up policy insertions

[Florian Westphal]

Policy insertions do not scale well, due to both a lienar list walk
to find the insertion spot and another list walk to set the 'pos' value
(a tie-breaker to detect which policy is older when there is ambiguity
 as to which one should be matched).

First patch gets rid of the second list walk on insert.
Rest of the patches get rid of the insertion walk.

This list walk was only needed because when I moved the policy db
implementation to rbtree I retained the old insertion method for the
sake of XFRM_MIGRATE.

Switching that to tree-based lookup avoids the need for the full
list search.

After this, insertion of a policy is largely independent of the number
of pre-existing policies as long as they do not share the same source/
destination networks.

Note that this is compile tested only as I did not find any
tests for XFRM_MIGRATE.

Florian Westphal (4):
  selftests: add xfrm policy insertion speed test script
  xfrm: policy: don't iterate inexact policies twice at insert time
  xfrm: switch migrate to xfrm_policy_lookup_bytype
  xfrm: policy: remove remaining use of inexact list

 include/net/xfrm.h                            |   1 -
 net/xfrm/xfrm_policy.c                        | 201 ++++++++----------
 tools/testing/selftests/net/Makefile          |   2 +-
 .../selftests/net/xfrm_policy_add_speed.sh    |  83 ++++++++
 4 files changed, 175 insertions(+), 112 deletions(-)
 create mode 100755 tools/testing/selftests/net/xfrm_policy_add_speed.sh

-- 
2.44.2

[PATCH ipsec-next 1/4] selftests: add xfrm policy insertion speed test script

[Florian Westphal]

Nothing special, just test how long insertion of x policies takes.
This should ideally show linear insertion speeds.

Do not run this by default, it has little value, but it can be useful to
check for insertion speed chahnges when altering the xfrm policy db
implementation.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 tools/testing/selftests/net/Makefile          |  2 +-
 .../selftests/net/xfrm_policy_add_speed.sh    | 83 +++++++++++++++++++
 2 files changed, 84 insertions(+), 1 deletion(-)
 create mode 100755 tools/testing/selftests/net/xfrm_policy_add_speed.sh

diff --git a/tools/testing/selftests/net/Makefile b/tools/testing/selftests/net/Makefile
index 8eaffd7a641c..e127a80ff713 100644
--- a/tools/testing/selftests/net/Makefile
+++ b/tools/testing/selftests/net/Makefile
@@ -56,7 +56,7 @@ TEST_PROGS += ip_local_port_range.sh
 TEST_PROGS += rps_default_mask.sh
 TEST_PROGS += big_tcp.sh
 TEST_PROGS += netns-sysctl.sh
-TEST_PROGS_EXTENDED := toeplitz_client.sh toeplitz.sh
+TEST_PROGS_EXTENDED := toeplitz_client.sh toeplitz.sh xfrm_policy_add_speed.sh
 TEST_GEN_FILES =  socket nettest
 TEST_GEN_FILES += psock_fanout psock_tpacket msg_zerocopy reuseport_addr_any
 TEST_GEN_FILES += tcp_mmap tcp_inq psock_snd txring_overwrite
diff --git a/tools/testing/selftests/net/xfrm_policy_add_speed.sh b/tools/testing/selftests/net/xfrm_policy_add_speed.sh
new file mode 100755
index 000000000000..2fab29d3cb91
--- /dev/null
+++ b/tools/testing/selftests/net/xfrm_policy_add_speed.sh
@@ -0,0 +1,83 @@
+#!/bin/bash
+# SPDX-License-Identifier: GPL-2.0
+#
+source lib.sh
+
+timeout=4m
+ret=0
+tmp=$(mktemp)
+cleanup() {
+	cleanup_all_ns
+	rm -f "$tmp"
+}
+
+trap cleanup EXIT
+
+maxpolicies=100000
+[ "$KSFT_MACHINE_SLOW" = "yes" ] && maxpolicies=10000
+
+do_dummies4() {
+	local dir="$1"
+	local max="$2"
+
+	local policies
+	local pfx
+	pfx=30
+	policies=0
+
+	ip netns exec "$ns" ip xfrm policy flush
+
+	for i in $(seq 1 100);do
+		local s
+		local d
+		for j in $(seq 1 255);do
+			s=$((i+0))
+			d=$((i+100))
+
+			for a in $(seq 1 8 255); do
+				policies=$((policies+1))
+				[ "$policies" -gt "$max" ] && return
+				echo xfrm policy add src 10.$s.$j.0/30 dst 10.$d.$j.$a/$pfx dir $dir action block
+			done
+			for a in $(seq 1 8 255); do
+				policies=$((policies+1))
+				[ "$policies" -gt "$max" ] && return
+				echo xfrm policy add src 10.$s.$j.$a/30 dst 10.$d.$j.0/$pfx dir $dir action block
+			done
+		done
+	done
+}
+
+setup_ns ns
+
+do_bench()
+{
+	local max="$1"
+
+	start=$(date +%s%3N)
+	do_dummies4 "out" "$max" > "$tmp"
+	if ! timeout "$timeout" ip netns exec "$ns" ip -batch "$tmp";then
+		echo "WARNING: policy insertion cancelled after $timeout"
+		ret=1
+	fi
+	stop=$(date +%s%3N)
+
+	result=$((stop-start))
+
+	policies=$(wc -l < "$tmp")
+	printf "Inserted %-06s policies in $result ms\n" $policies
+
+	have=$(ip netns exec "$ns" ip xfrm policy show | grep "action block" | wc -l)
+	if [ "$have" -ne "$policies" ]; then
+		echo "WARNING: mismatch, have $have policies, expected $policies"
+		ret=1
+	fi
+}
+
+p=100
+while [ $p -le "$maxpolicies" ]; do
+	do_bench "$p"
+	p="${p}0"
+done
+
+exit $ret
-- 
2.44.2

[PATCH ipsec-next 2/4] xfrm: policy: don't iterate inexact policies twice at insert time

[Florian Westphal]

Since commit
6be3b0db6db8 ("xfrm: policy: add inexact policy search tree infrastructure")
policy lookup no longer walks a list but has a set of candidate lists.

This set has to be searched for the best match.
In case there are several matches, the priority wins.

If the priority is also the same, then the historic behaviour with
a single list was to return the first match (first-in-list).

With introduction of serval lists, this doesn't work and a new
'pos' member was added that reflects the xfrm_policy structs position
in the list.

This value is not exported to userspace and it does not need to be
the 'position in the list', it just needs to make sure that
a->pos < b->pos means that a was added to the lists more recently
than b.

This re-walk is expensive when many inexact policies are in use.

Speed this up: when appending the policy to the end of the walker list,
then just take the ->pos value of the last entry made and add 1.

Add a slowpath version to prevent overflow, if we'd assign UINT_MAX
then iterate the entire list and fix the ordering.

While this speeds up insertion considerably finding the insertion spot
in the inexact list still requires a partial list walk.

This is addressed in followup patches.

Before:
./xfrm_policy_add_speed.sh
Inserted 1000   policies in 72 ms
Inserted 10000  policies in 1540 ms
Inserted 100000 policies in 334780 ms

After:
Inserted 1000   policies in 68 ms
Inserted 10000  policies in 1137 ms
Inserted 100000 policies in 157307 ms

Reported-by: Noel Kuntze <noel@familie-kuntze.de>
Cc: Tobias Brunner <tobias@strongswan.org>
Signed-off-by: Florian Westphal <fw@strlen.de>
---
 net/xfrm/xfrm_policy.c | 59 +++++++++++++++++++++++++++++++++++++-----
 1 file changed, 53 insertions(+), 6 deletions(-)

diff --git a/net/xfrm/xfrm_policy.c b/net/xfrm/xfrm_policy.c
index c56c61b0c12e..423d1eb24f31 100644
--- a/net/xfrm/xfrm_policy.c
+++ b/net/xfrm/xfrm_policy.c
@@ -1237,6 +1237,17 @@ xfrm_policy_inexact_insert(struct xfrm_policy *policy, u8 dir, int excl)
 	return delpol;
 }
 
+static bool xfrm_policy_is_dead_or_sk(const struct xfrm_policy *policy)
+{
+	int dir;
+
+	if (policy->walk.dead)
+		return true;
+
+	dir = xfrm_policy_id2dir(policy->index);
+	return dir >= XFRM_POLICY_MAX;
+}
+
 static void xfrm_hash_rebuild(struct work_struct *work)
 {
 	struct net *net = container_of(work, struct net,
@@ -1524,7 +1535,6 @@ static void xfrm_policy_insert_inexact_list(struct hlist_head *chain,
 {
 	struct xfrm_policy *pol, *delpol = NULL;
 	struct hlist_node *newpos = NULL;
-	int i = 0;
 
 	hlist_for_each_entry(pol, chain, bydst_inexact_list) {
 		if (pol->type == policy->type &&
@@ -1548,11 +1558,6 @@ static void xfrm_policy_insert_inexact_list(struct hlist_head *chain,
 		hlist_add_behind_rcu(&policy->bydst_inexact_list, newpos);
 	else
 		hlist_add_head_rcu(&policy->bydst_inexact_list, chain);
-
-	hlist_for_each_entry(pol, chain, bydst_inexact_list) {
-		pol->pos = i;
-		i++;
-	}
 }
 
 static struct xfrm_policy *xfrm_policy_insert_list(struct hlist_head *chain,
@@ -2294,10 +2299,52 @@ static struct xfrm_policy *xfrm_sk_policy_lookup(const struct sock *sk, int dir,
 	return pol;
 }
 
+static u32 xfrm_gen_pos_slow(struct net *net)
+{
+	struct xfrm_policy *policy;
+	u32 i = 0;
+
+	/* oldest entry is last in list */
+	list_for_each_entry_reverse(policy, &net->xfrm.policy_all, walk.all) {
+		if (!xfrm_policy_is_dead_or_sk(policy))
+			policy->pos = ++i;
+	}
+
+	return i;
+}
+
+static u32 xfrm_gen_pos(struct net *net)
+{
+	const struct xfrm_policy *policy;
+	u32 i = 0;
+
+	/* most recently added policy is at the head of the list */
+	list_for_each_entry(policy, &net->xfrm.policy_all, walk.all) {
+		if (xfrm_policy_is_dead_or_sk(policy))
+			continue;
+
+		if (policy->pos == UINT_MAX)
+			return xfrm_gen_pos_slow(net);
+
+		i = policy->pos + 1;
+		break;
+	}
+
+	return i;
+}
+
 static void __xfrm_policy_link(struct xfrm_policy *pol, int dir)
 {
 	struct net *net = xp_net(pol);
 
+	switch (dir) {
+	case XFRM_POLICY_IN:
+	case XFRM_POLICY_FWD:
+	case XFRM_POLICY_OUT:
+		pol->pos = xfrm_gen_pos(net);
+		break;
+	}
+
 	list_add(&pol->walk.all, &net->xfrm.policy_all);
 	net->xfrm.policy_count[dir]++;
 	xfrm_pol_hold(pol);
-- 
2.44.2

[PATCH ipsec-next 3/4] xfrm: switch migrate to xfrm_policy_lookup_bytype

[Florian Westphal]

XFRM_MIGRATE still uses the old lookup method:
first check the bydst hash table, then search the list of all the other
policies.

Switch MIGRATE to use the same lookup function as the packetpath.

This is done to remove the last remaining users of the pernet
xfrm.policy_inexact lists with the intent of removing this list.

After this patch, policies are still added to the list on insertion
and they are rehashed as-needed but no single API makes use of these
anymore.

This change is compile tested only.

Cc: Tobias Brunner <tobias@strongswan.org>
Signed-off-by: Florian Westphal <fw@strlen.de>
---
 net/xfrm/xfrm_policy.c | 106 +++++++++++++++--------------------------
 1 file changed, 39 insertions(+), 67 deletions(-)

diff --git a/net/xfrm/xfrm_policy.c b/net/xfrm/xfrm_policy.c
index 423d1eb24f31..d2feee60bb62 100644
--- a/net/xfrm/xfrm_policy.c
+++ b/net/xfrm/xfrm_policy.c
@@ -1252,13 +1252,10 @@ static void xfrm_hash_rebuild(struct work_struct *work)
 {
 	struct net *net = container_of(work, struct net,
 				       xfrm.policy_hthresh.work);
-	unsigned int hmask;
 	struct xfrm_policy *pol;
 	struct xfrm_policy *policy;
 	struct hlist_head *chain;
-	struct hlist_head *odst;
 	struct hlist_node *newpos;
-	int i;
 	int dir;
 	unsigned seq;
 	u8 lbits4, rbits4, lbits6, rbits6;
@@ -1322,23 +1319,7 @@ static void xfrm_hash_rebuild(struct work_struct *work)
 			goto out_unlock;
 	}
 
-	/* reset the bydst and inexact table in all directions */
 	for (dir = 0; dir < XFRM_POLICY_MAX; dir++) {
-		struct hlist_node *n;
-
-		hlist_for_each_entry_safe(policy, n,
-					  &net->xfrm.policy_inexact[dir],
-					  bydst_inexact_list) {
-			hlist_del_rcu(&policy->bydst);
-			hlist_del_init(&policy->bydst_inexact_list);
-		}
-
-		hmask = net->xfrm.policy_bydst[dir].hmask;
-		odst = net->xfrm.policy_bydst[dir].table;
-		for (i = hmask; i >= 0; i--) {
-			hlist_for_each_entry_safe(policy, n, odst + i, bydst)
-				hlist_del_rcu(&policy->bydst);
-		}
 		if ((dir & XFRM_POLICY_MASK) == XFRM_POLICY_OUT) {
 			/* dir out => dst = remote, src = local */
 			net->xfrm.policy_bydst[dir].dbits4 = rbits4;
@@ -1363,6 +1344,10 @@ static void xfrm_hash_rebuild(struct work_struct *work)
 			/* skip socket policies */
 			continue;
 		}
+
+		hlist_del_rcu(&policy->bydst);
+		hlist_del_init(&policy->bydst_inexact_list);
+
 		newpos = NULL;
 		chain = policy_hash_bysel(net, &policy->selector,
 					  policy->family, dir);
@@ -4484,63 +4469,50 @@ EXPORT_SYMBOL_GPL(xfrm_audit_policy_delete);
 #endif
 
 #ifdef CONFIG_XFRM_MIGRATE
-static bool xfrm_migrate_selector_match(const struct xfrm_selector *sel_cmp,
-					const struct xfrm_selector *sel_tgt)
-{
-	if (sel_cmp->proto == IPSEC_ULPROTO_ANY) {
-		if (sel_tgt->family == sel_cmp->family &&
-		    xfrm_addr_equal(&sel_tgt->daddr, &sel_cmp->daddr,
-				    sel_cmp->family) &&
-		    xfrm_addr_equal(&sel_tgt->saddr, &sel_cmp->saddr,
-				    sel_cmp->family) &&
-		    sel_tgt->prefixlen_d == sel_cmp->prefixlen_d &&
-		    sel_tgt->prefixlen_s == sel_cmp->prefixlen_s) {
-			return true;
-		}
-	} else {
-		if (memcmp(sel_tgt, sel_cmp, sizeof(*sel_tgt)) == 0) {
-			return true;
-		}
-	}
-	return false;
-}
-
 static struct xfrm_policy *xfrm_migrate_policy_find(const struct xfrm_selector *sel,
 						    u8 dir, u8 type, struct net *net, u32 if_id)
 {
 	struct xfrm_policy *pol, *ret = NULL;
-	struct hlist_head *chain;
-	u32 priority = ~0U;
+	struct flowi fl;
 
-	spin_lock_bh(&net->xfrm.xfrm_policy_lock);
-	chain = policy_hash_direct(net, &sel->daddr, &sel->saddr, sel->family, dir);
-	hlist_for_each_entry(pol, chain, bydst) {
-		if ((if_id == 0 || pol->if_id == if_id) &&
-		    xfrm_migrate_selector_match(sel, &pol->selector) &&
-		    pol->type == type) {
-			ret = pol;
-			priority = ret->priority;
-			break;
-		}
-	}
-	chain = &net->xfrm.policy_inexact[dir];
-	hlist_for_each_entry(pol, chain, bydst_inexact_list) {
-		if ((pol->priority >= priority) && ret)
-			break;
+	memset(&fl, 0, sizeof(fl));
 
-		if ((if_id == 0 || pol->if_id == if_id) &&
-		    xfrm_migrate_selector_match(sel, &pol->selector) &&
-		    pol->type == type) {
-			ret = pol;
+	fl.flowi_proto = sel->proto;
+
+	switch (sel->family) {
+	case AF_INET:
+		fl.u.ip4.saddr = sel->saddr.a4;
+		fl.u.ip4.daddr = sel->daddr.a4;
+		if (sel->proto == IPSEC_ULPROTO_ANY)
 			break;
-		}
+		fl.u.flowi4_oif = sel->ifindex;
+		fl.u.ip4.fl4_sport = sel->sport;
+		fl.u.ip4.fl4_dport = sel->dport;
+		break;
+	case AF_INET6:
+		fl.u.ip6.saddr = sel->saddr.in6;
+		fl.u.ip6.daddr = sel->daddr.in6;
+		if (sel->proto == IPSEC_ULPROTO_ANY)
+			break;
+		fl.u.flowi6_oif = sel->ifindex;
+		fl.u.ip6.fl4_sport = sel->sport;
+		fl.u.ip6.fl4_dport = sel->dport;
+		break;
+	default:
+		return ERR_PTR(-EAFNOSUPPORT);
 	}
 
-	xfrm_pol_hold(ret);
+	rcu_read_lock();
 
-	spin_unlock_bh(&net->xfrm.xfrm_policy_lock);
+	pol = xfrm_policy_lookup_bytype(net, type, &fl, sel->family, dir, if_id);
+	if (IS_ERR_OR_NULL(pol))
+		goto out_unlock;
 
-	return ret;
+	if (!xfrm_pol_hold_rcu(ret))
+		pol = NULL;
+out_unlock:
+	rcu_read_unlock();
+	return pol;
 }
 
 static int migrate_tmpl_match(const struct xfrm_migrate *m, const struct xfrm_tmpl *t)
@@ -4677,9 +4649,9 @@ int xfrm_migrate(const struct xfrm_selector *sel, u8 dir, u8 type,
 
 	/* Stage 1 - find policy */
 	pol = xfrm_migrate_policy_find(sel, dir, type, net, if_id);
-	if (!pol) {
+	if (IS_ERR_OR_NULL(pol)) {
 		NL_SET_ERR_MSG(extack, "Target policy not found");
-		err = -ENOENT;
+		err = IS_ERR(pol) ? PTR_ERR(pol) : -ENOENT;
 		goto out;
 	}
 
-- 
2.44.2

Re: [PATCH ipsec-next 3/4] xfrm: switch migrate to xfrm_policy_lookup_bytype

[Julian Wiedmann]

Hi Florian,

On 22.08.24 16:04, Florian Westphal wrote:
> XFRM_MIGRATE still uses the old lookup method:
> first check the bydst hash table, then search the list of all the other
> policies.
> 
> Switch MIGRATE to use the same lookup function as the packetpath.
> 
> This is done to remove the last remaining users of the pernet
> xfrm.policy_inexact lists with the intent of removing this list.
> 
> After this patch, policies are still added to the list on insertion
> and they are rehashed as-needed but no single API makes use of these
> anymore.
> 
> This change is compile tested only.
> 

[...]

>  
> -	spin_unlock_bh(&net->xfrm.xfrm_policy_lock);
> +	pol = xfrm_policy_lookup_bytype(net, type, &fl, sel->family, dir, if_id);
> +	if (IS_ERR_OR_NULL(pol))
> +		goto out_unlock;
>  
> -	return ret;
> +	if (!xfrm_pol_hold_rcu(ret))

Coverity spotted that ^^^ needs a s/ret/pol fix-up:

>    CID 1599386:  Null pointer dereferences  (FORWARD_NULL)
>    Passing null pointer "ret" to "xfrm_pol_hold_rcu", which dereferences it.


> +		pol = NULL;
> +out_unlock:
> +	rcu_read_unlock();
> +	return pol;
>  }
>  

[PATCH ipsec-next] xfrm: policy: fix null dereference

[Florian Westphal]

Julian Wiedmann says:
> +     if (!xfrm_pol_hold_rcu(ret))

Coverity spotted that ^^^ needs a s/ret/pol fix-up:

> CID 1599386:  Null pointer dereferences  (FORWARD_NULL)
> Passing null pointer "ret" to "xfrm_pol_hold_rcu", which dereferences it.

Ditch the bogus 'ret' variable.

Fixes: 563d5ca93e88 ("xfrm: switch migrate to xfrm_policy_lookup_bytype")
Reported-by: Julian Wiedmann <jwiedmann.dev@gmail.com>
Closes: https://lore.kernel.org/netdev/06dc2499-c095-4bd4-aee3-a1d0e3ec87c4@gmail.com/
Signed-off-by: Florian Westphal <fw@strlen.de>
---
 net/xfrm/xfrm_policy.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/net/xfrm/xfrm_policy.c b/net/xfrm/xfrm_policy.c
index 6336baa8a93c..31c14457fdaf 100644
--- a/net/xfrm/xfrm_policy.c
+++ b/net/xfrm/xfrm_policy.c
@@ -4429,7 +4429,7 @@ EXPORT_SYMBOL_GPL(xfrm_audit_policy_delete);
 static struct xfrm_policy *xfrm_migrate_policy_find(const struct xfrm_selector *sel,
 						    u8 dir, u8 type, struct net *net, u32 if_id)
 {
-	struct xfrm_policy *pol, *ret = NULL;
+	struct xfrm_policy *pol;
 	struct flowi fl;
 
 	memset(&fl, 0, sizeof(fl));
@@ -4465,7 +4465,7 @@ static struct xfrm_policy *xfrm_migrate_policy_find(const struct xfrm_selector *
 	if (IS_ERR_OR_NULL(pol))
 		goto out_unlock;
 
-	if (!xfrm_pol_hold_rcu(ret))
+	if (!xfrm_pol_hold_rcu(pol))
 		pol = NULL;
 out_unlock:
 	rcu_read_unlock();
-- 
2.44.2

Re: [PATCH ipsec-next] xfrm: policy: fix null dereference

[Simon Horman]

On Fri, Aug 30, 2024 at 04:39:10PM +0200, Florian Westphal wrote:
> Julian Wiedmann says:
> > +     if (!xfrm_pol_hold_rcu(ret))
> 
> Coverity spotted that ^^^ needs a s/ret/pol fix-up:
> 
> > CID 1599386:  Null pointer dereferences  (FORWARD_NULL)
> > Passing null pointer "ret" to "xfrm_pol_hold_rcu", which dereferences it.
> 
> Ditch the bogus 'ret' variable.
> 
> Fixes: 563d5ca93e88 ("xfrm: switch migrate to xfrm_policy_lookup_bytype")
> Reported-by: Julian Wiedmann <jwiedmann.dev@gmail.com>
> Closes: https://lore.kernel.org/netdev/06dc2499-c095-4bd4-aee3-a1d0e3ec87c4@gmail.com/
> Signed-off-by: Florian Westphal <fw@strlen.de>

Reviewed-by: Simon Horman <horms@kernel.org>

Re: [PATCH ipsec-next] xfrm: policy: fix null dereference

[Steffen Klassert]

On Fri, Aug 30, 2024 at 04:39:10PM +0200, Florian Westphal wrote:
> Julian Wiedmann says:
> > +     if (!xfrm_pol_hold_rcu(ret))
> 
> Coverity spotted that ^^^ needs a s/ret/pol fix-up:
> 
> > CID 1599386:  Null pointer dereferences  (FORWARD_NULL)
> > Passing null pointer "ret" to "xfrm_pol_hold_rcu", which dereferences it.
> 
> Ditch the bogus 'ret' variable.
> 
> Fixes: 563d5ca93e88 ("xfrm: switch migrate to xfrm_policy_lookup_bytype")
> Reported-by: Julian Wiedmann <jwiedmann.dev@gmail.com>
> Closes: https://lore.kernel.org/netdev/06dc2499-c095-4bd4-aee3-a1d0e3ec87c4@gmail.com/
> Signed-off-by: Florian Westphal <fw@strlen.de>

Now appiled to ipsec-next, thanks!

[PATCH ipsec-next 4/4] xfrm: policy: remove remaining use of inexact list

[Florian Westphal]

No consumers anymore, remove it.  After this, insertion of policies
no longer require list walk of all inexact policies but only those
that are reachable via the candidate sets.

This gives almost linear insertion speeds provided the inserted
policies are for non-overlapping networks.

Before:
Inserted 1000   policies in 70 ms
Inserted 10000  policies in 1155 ms
Inserted 100000 policies in 216848 ms

After:
Inserted 1000   policies in 56 ms
Inserted 10000  policies in 478 ms
Inserted 100000 policies in 4580 ms

Insertion of 1m entries takes about ~40s after this change
on my test vm.

Cc: Noel Kuntze <noel@familie-kuntze.de>
Cc: Tobias Brunner <tobias@strongswan.org>
Signed-off-by: Florian Westphal <fw@strlen.de>
---
 include/net/xfrm.h     |  1 -
 net/xfrm/xfrm_policy.c | 38 --------------------------------------
 2 files changed, 39 deletions(-)

diff --git a/include/net/xfrm.h b/include/net/xfrm.h
index 54cef89f6c1e..101715064707 100644
--- a/include/net/xfrm.h
+++ b/include/net/xfrm.h
@@ -555,7 +555,6 @@ struct xfrm_policy {
 	u16			family;
 	struct xfrm_sec_ctx	*security;
 	struct xfrm_tmpl       	xfrm_vec[XFRM_MAX_DEPTH];
-	struct hlist_node	bydst_inexact_list;
 	struct rcu_head		rcu;
 
 	struct xfrm_dev_offload xdo;
diff --git a/net/xfrm/xfrm_policy.c b/net/xfrm/xfrm_policy.c
index d2feee60bb62..b79ac453ea37 100644
--- a/net/xfrm/xfrm_policy.c
+++ b/net/xfrm/xfrm_policy.c
@@ -196,8 +196,6 @@ xfrm_policy_inexact_lookup_rcu(struct net *net,
 static struct xfrm_policy *
 xfrm_policy_insert_list(struct hlist_head *chain, struct xfrm_policy *policy,
 			bool excl);
-static void xfrm_policy_insert_inexact_list(struct hlist_head *chain,
-					    struct xfrm_policy *policy);
 
 static bool
 xfrm_policy_find_inexact_candidates(struct xfrm_pol_inexact_candidates *cand,
@@ -410,7 +408,6 @@ struct xfrm_policy *xfrm_policy_alloc(struct net *net, gfp_t gfp)
 	if (policy) {
 		write_pnet(&policy->xp_net, net);
 		INIT_LIST_HEAD(&policy->walk.all);
-		INIT_HLIST_NODE(&policy->bydst_inexact_list);
 		INIT_HLIST_NODE(&policy->bydst);
 		INIT_HLIST_NODE(&policy->byidx);
 		rwlock_init(&policy->lock);
@@ -1228,9 +1225,6 @@ xfrm_policy_inexact_insert(struct xfrm_policy *policy, u8 dir, int excl)
 		return ERR_PTR(-EEXIST);
 	}
 
-	chain = &net->xfrm.policy_inexact[dir];
-	xfrm_policy_insert_inexact_list(chain, policy);
-
 	if (delpol)
 		__xfrm_policy_inexact_prune_bin(bin, false);
 
@@ -1346,7 +1340,6 @@ static void xfrm_hash_rebuild(struct work_struct *work)
 		}
 
 		hlist_del_rcu(&policy->bydst);
-		hlist_del_init(&policy->bydst_inexact_list);
 
 		newpos = NULL;
 		chain = policy_hash_bysel(net, &policy->selector,
@@ -1515,36 +1508,6 @@ static const struct rhashtable_params xfrm_pol_inexact_params = {
 	.automatic_shrinking	= true,
 };
 
-static void xfrm_policy_insert_inexact_list(struct hlist_head *chain,
-					    struct xfrm_policy *policy)
-{
-	struct xfrm_policy *pol, *delpol = NULL;
-	struct hlist_node *newpos = NULL;
-
-	hlist_for_each_entry(pol, chain, bydst_inexact_list) {
-		if (pol->type == policy->type &&
-		    pol->if_id == policy->if_id &&
-		    !selector_cmp(&pol->selector, &policy->selector) &&
-		    xfrm_policy_mark_match(&policy->mark, pol) &&
-		    xfrm_sec_ctx_match(pol->security, policy->security) &&
-		    !WARN_ON(delpol)) {
-			delpol = pol;
-			if (policy->priority > pol->priority)
-				continue;
-		} else if (policy->priority >= pol->priority) {
-			newpos = &pol->bydst_inexact_list;
-			continue;
-		}
-		if (delpol)
-			break;
-	}
-
-	if (newpos && policy->xdo.type != XFRM_DEV_OFFLOAD_PACKET)
-		hlist_add_behind_rcu(&policy->bydst_inexact_list, newpos);
-	else
-		hlist_add_head_rcu(&policy->bydst_inexact_list, chain);
-}
-
 static struct xfrm_policy *xfrm_policy_insert_list(struct hlist_head *chain,
 						   struct xfrm_policy *policy,
 						   bool excl)
@@ -2346,7 +2309,6 @@ static struct xfrm_policy *__xfrm_policy_unlink(struct xfrm_policy *pol,
 	/* Socket policies are not hashed. */
 	if (!hlist_unhashed(&pol->bydst)) {
 		hlist_del_rcu(&pol->bydst);
-		hlist_del_init(&pol->bydst_inexact_list);
 		hlist_del(&pol->byidx);
 	}
 
-- 
2.44.2

Re: [PATCH ipsec-next 0/4] xfrm: speed up policy insertions

[Steffen Klassert]

On Thu, Aug 22, 2024 at 03:04:28PM +0200, Florian Westphal wrote:
> Policy insertions do not scale well, due to both a lienar list walk
> to find the insertion spot and another list walk to set the 'pos' value
> (a tie-breaker to detect which policy is older when there is ambiguity
>  as to which one should be matched).
> 
> First patch gets rid of the second list walk on insert.
> Rest of the patches get rid of the insertion walk.
> 
> This list walk was only needed because when I moved the policy db
> implementation to rbtree I retained the old insertion method for the
> sake of XFRM_MIGRATE.
> 
> Switching that to tree-based lookup avoids the need for the full
> list search.
> 
> After this, insertion of a policy is largely independent of the number
> of pre-existing policies as long as they do not share the same source/
> destination networks.
> 
> Note that this is compile tested only as I did not find any
> tests for XFRM_MIGRATE.
> 
> Florian Westphal (4):
>   selftests: add xfrm policy insertion speed test script
>   xfrm: policy: don't iterate inexact policies twice at insert time
>   xfrm: switch migrate to xfrm_policy_lookup_bytype
>   xfrm: policy: remove remaining use of inexact list

Applied, thanks a lot Florian!