[PATCH ipsec 0/7] xfrm: policy: fix various bugs

[PATCH ipsec 0/7] xfrm: policy: fix various bugs

[Florian Westphal]

This series addresses various bugs, mostly fallout from the recent
rcu tree work. One is a fix for an older bug coming from the initial
rcu conversion.

There were several xfrm policy related syzbot bugs recently, but
so far only one of them has a reproducer (addressed by patch #4).

As I provided ample rope for syzbot to hang itself with, there is
some chance that this and the other fixes also resolve the KASAN
and UAF syzbot xfrm reports reported in the last couple of days.

My plan is to wait until these patches are applied, and then tell syzbot
for all the open reports that the last patch 'fixes this'.

AFAIU that will make syzbot report the problem again in case it can still
trigger similar splats with these fixes in place.

Florian Westphal (7):
      selftests: xfrm: add block rules with adjacent/overlapping subnets
      xfrm: policy: use hlist rcu variants on inexact insert, part 2
      xfrm: policy: increment xfrm_hash_generation on hash rebuild
      xfrm: policy: delete inexact policies from inexact list on hash rebuild
      xfrm: policy: fix reinsertion on node merge
      selftests: xfrm: alter htresh to trigger move of policies to hash table
      xfrm: policy: fix infinite loop when merging src-nodes

 net/xfrm/xfrm_policy.c                     |   58 +++++-----
 tools/testing/selftests/net/xfrm_policy.sh |  153 ++++++++++++++++++++++++-----
 2 files changed, 160 insertions(+), 51 deletions(-)

[PATCH ipsec 1/7] selftests: xfrm: add block rules with adjacent/overlapping subnets

[Florian Westphal]

The existing script lacks a policy pattern that triggers 'tree node
merges' in the kernel.

Consider adding policy affecting following subnet:
pol1: dst 10.0.0.0/22
pol2: dst 10.0.0.0/23 # adds to existing 10.0.0.0/22 node

-> no problems here.  But now, lets consider reverse order:
pol1: dst 10.0.0.0/24
pol2: dst 10.0.0.0/23 # CANNOT add to existing node

When second policy gets added, the kernel must check that the new node
("10.0.0.0/23") doesn't overlap with any existing subnet.

Example:
dst 10.0.0.0/24
dst 10.0.0.1/24
dst 10.0.0.0/23

When the third policy gets added, the kernel must replace the nodes for
the 10.0.0.0/24 and 10.0.0.1/24 policies with a single one and must merge
all the subtrees/lists stored in those nodes into the new node.

The existing test cases only have overlaps with a single node, so no
merging takes place (we can always remove the 'old' node and replace
it with the new subnet prefix).

Add a few 'block policies' in a pattern that triggers this, with a priority
that will make kernel prefer the 'esp' rules.

Make sure the 'tunnel ping' tests still pass after they have been added.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 tools/testing/selftests/net/xfrm_policy.sh | 109 +++++++++++++++++----
 1 file changed, 91 insertions(+), 18 deletions(-)

diff --git a/tools/testing/selftests/net/xfrm_policy.sh b/tools/testing/selftests/net/xfrm_policy.sh
index 8db35b99457c..b5a1b565a7e6 100755
--- a/tools/testing/selftests/net/xfrm_policy.sh
+++ b/tools/testing/selftests/net/xfrm_policy.sh
@@ -46,6 +46,58 @@ do_esp() {
     ip -net $ns xfrm policy add src $rnet dst $lnet dir fwd tmpl src $remote dst $me proto esp mode tunnel priority 100 action allow
 }
 
+# add policies with different netmasks, to make sure kernel carries
+# the policies contained within new netmask over when search tree is
+# re-built.
+# peer netns that are supposed to be encapsulated via esp have addresses
+# in the 10.0.1.0/24 and 10.0.2.0/24 subnets, respectively.
+#
+# Adding a policy for '10.0.1.0/23' will make it necessary to
+# alter the prefix of 10.0.1.0 subnet.
+# In case new prefix overlaps with existing node, the node and all
+# policies it carries need to be merged with the existing one(s).
+#
+# Do that here.
+do_overlap()
+{
+    local ns=$1
+
+    # adds new nodes to tree (neither network exists yet in policy database).
+    ip -net $ns xfrm policy add src 10.1.0.0/24 dst 10.0.0.0/24 dir fwd priority 200 action block
+
+    # adds a new node in the 10.0.0.0/24 tree (dst node exists).
+    ip -net $ns xfrm policy add src 10.2.0.0/24 dst 10.0.0.0/24 dir fwd priority 200 action block
+
+    # adds a 10.2.0.0/24 node, but for different dst.
+    ip -net $ns xfrm policy add src 10.2.0.0/24 dst 10.0.1.0/24 dir fwd priority 200 action block
+
+    # dst now overlaps with the 10.0.1.0/24 ESP policy in fwd.
+    # kernel must 'promote' existing one (10.0.0.0/24) to 10.0.0.0/23.
+    # But 10.0.0.0/23 also includes existing 10.0.1.0/24, so that node
+    # also has to be merged too, including source-sorted subtrees.
+    # old:
+    # 10.0.0.0/24 (node 1 in dst tree of the bin)
+    #    10.1.0.0/24 (node in src tree of dst node 1)
+    #    10.2.0.0/24 (node in src tree of dst node 1)
+    # 10.0.1.0/24 (node 2 in dst tree of the bin)
+    #    10.0.2.0/24 (node in src tree of dst node 2)
+    #    10.2.0.0/24 (node in src tree of dst node 2)
+    #
+    # The next 'policy add' adds dst '10.0.0.0/23', which means
+    # that dst node 1 and dst node 2 have to be merged including
+    # the sub-tree.  As no duplicates are allowed, policies in
+    # the two '10.0.2.0/24' are also merged.
+    #
+    # after the 'add', internal search tree should look like this:
+    # 10.0.0.0/23 (node in dst tree of bin)
+    #     10.0.2.0/24 (node in src tree of dst node)
+    #     10.1.0.0/24 (node in src tree of dst node)
+    #     10.2.0.0/24 (node in src tree of dst node)
+    #
+    # 10.0.0.0/24 and 10.0.1.0/24 nodes have been merged as 10.0.0.0/23.
+    ip -net $ns xfrm policy add src 10.1.0.0/24 dst 10.0.0.0/23 dir fwd priority 200 action block
+}
+
 do_esp_policy_get_check() {
     local ns=$1
     local lnet=$2
@@ -160,6 +212,41 @@ check_xfrm() {
 	return $lret
 }
 
+check_exceptions()
+{
+	logpostfix="$1"
+	local lret=0
+
+	# ping to .254 should be excluded from the tunnel (exception is in place).
+	check_xfrm 0 254
+	if [ $? -ne 0 ]; then
+		echo "FAIL: expected ping to .254 to fail ($logpostfix)"
+		lret=1
+	else
+		echo "PASS: ping to .254 bypassed ipsec tunnel ($logpostfix)"
+	fi
+
+	# ping to .253 should use use ipsec due to direct policy exception.
+	check_xfrm 1 253
+	if [ $? -ne 0 ]; then
+		echo "FAIL: expected ping to .253 to use ipsec tunnel ($logpostfix)"
+		lret=1
+	else
+		echo "PASS: direct policy matches ($logpostfix)"
+	fi
+
+	# ping to .2 should use ipsec.
+	check_xfrm 1 2
+	if [ $? -ne 0 ]; then
+		echo "FAIL: expected ping to .2 to use ipsec tunnel ($logpostfix)"
+		lret=1
+	else
+		echo "PASS: policy matches ($logpostfix)"
+	fi
+
+	return $lret
+}
+
 #check for needed privileges
 if [ "$(id -u)" -ne 0 ];then
 	echo "SKIP: Need root privileges"
@@ -270,31 +357,17 @@ do_exception ns4 10.0.3.10 10.0.3.1 10.0.1.253 10.0.1.240/28
 do_exception ns3 dead:3::1 dead:3::10 dead:2::fd  dead:2:f0::/96
 do_exception ns4 dead:3::10 dead:3::1 dead:1::fd  dead:1:f0::/96
 
-# ping to .254 should now be excluded from the tunnel
-check_xfrm 0 254
+check_exceptions "exceptions"
 if [ $? -ne 0 ]; then
-	echo "FAIL: expected ping to .254 to fail"
 	ret=1
-else
-	echo "PASS: ping to .254 bypassed ipsec tunnel"
 fi
 
-# ping to .253 should use use ipsec due to direct policy exception.
-check_xfrm 1 253
-if [ $? -ne 0 ]; then
-	echo "FAIL: expected ping to .253 to use ipsec tunnel"
-	ret=1
-else
-	echo "PASS: direct policy matches"
-fi
+# insert block policies with adjacent/overlapping netmasks
+do_overlap ns3
 
-# ping to .2 should use ipsec.
-check_xfrm 1 2
+check_exceptions "exceptions and block policies"
 if [ $? -ne 0 ]; then
-	echo "FAIL: expected ping to .2 to use ipsec tunnel"
 	ret=1
-else
-	echo "PASS: policy matches"
 fi
 
 for i in 1 2 3 4;do ip netns del ns$i;done
-- 
2.19.2

[PATCH ipsec 2/7] xfrm: policy: use hlist rcu variants on inexact insert, part 2

[Florian Westphal]

This function was modeled on the 'exact' insert one, which did not use
the rcu variant either.

When I fixed the 'exact' insert I forgot to propagate this to my
development tree, so the inexact variant retained the bug.

Fixes: 9cf545ebd591d ("xfrm: policy: store inexact policies in a tree ordered by destination address")
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 934492bad8e0..628b389af2ba 100644
--- a/net/xfrm/xfrm_policy.c
+++ b/net/xfrm/xfrm_policy.c
@@ -856,9 +856,9 @@ static void xfrm_policy_inexact_list_reinsert(struct net *net,
 		}
 
 		if (newpos)
-			hlist_add_behind(&policy->bydst, newpos);
+			hlist_add_behind_rcu(&policy->bydst, newpos);
 		else
-			hlist_add_head(&policy->bydst, &n->hhead);
+			hlist_add_head_rcu(&policy->bydst, &n->hhead);
 
 		/* paranoia checks follow.
 		 * Check that the reinserted policy matches at least
-- 
2.19.2

[PATCH ipsec 3/7] xfrm: policy: increment xfrm_hash_generation on hash rebuild

[Florian Westphal]

Hash rebuild will re-set all the inexact entries, then re-insert them.
Lookups that can occur in parallel will therefore not find any policies.

This was safe when lookups were still guarded by rwlock.
After rcu-ification, lookups check the hash_generation seqcount to detect
when a hash resize takes place.  Hash rebuild missed the needed increment.

Hash resizes and hash rebuilds cannot occur in parallel (both acquire
hash_resize_mutex), so just increment xfrm_hash_generation, like resize.

Fixes: a7c44247f704e3 ("xfrm: policy: make xfrm_policy_lookup_bytype lockless")
Signed-off-by: Florian Westphal <fw@strlen.de>
---
 net/xfrm/xfrm_policy.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/net/xfrm/xfrm_policy.c b/net/xfrm/xfrm_policy.c
index 628b389af2ba..d8fba27a4bfb 100644
--- a/net/xfrm/xfrm_policy.c
+++ b/net/xfrm/xfrm_policy.c
@@ -1235,6 +1235,7 @@ static void xfrm_hash_rebuild(struct work_struct *work)
 	} while (read_seqretry(&net->xfrm.policy_hthresh.lock, seq));
 
 	spin_lock_bh(&net->xfrm.xfrm_policy_lock);
+	write_seqcount_begin(&xfrm_policy_hash_generation);
 
 	/* make sure that we can insert the indirect policies again before
 	 * we start with destructive action.
@@ -1334,6 +1335,7 @@ static void xfrm_hash_rebuild(struct work_struct *work)
 
 out_unlock:
 	__xfrm_policy_inexact_flush(net);
+	write_seqcount_end(&xfrm_policy_hash_generation);
 	spin_unlock_bh(&net->xfrm.xfrm_policy_lock);
 
 	mutex_unlock(&hash_resize_mutex);
-- 
2.19.2

[PATCH ipsec 4/7] xfrm: policy: delete inexact policies from inexact list on hash rebuild

[Florian Westphal]

An xfrm hash rebuild has to reset the inexact policy list before the
policies get re-inserted: A change of hash thresholds will result in
policies to get moved from inexact tree to the policy hash table.

If the thresholds are increased again later, they get moved from hash
table to inexact tree.

We must unlink all policies from the inexact tree before re-insertion.

Otherwise 'migrate' may find policies that are in main hash table a
second time, when it searches the inexact lists.

Furthermore, re-insertion without deletion can cause elements ->next to
point back to itself, causing soft lockups or double-frees.

Reported-by: syzbot+9d971dd21eb26567036b@syzkaller.appspotmail.com
Fixes: 9cf545ebd591da ("xfrm: policy: store inexact policies in a tree ordered by destination address")
Signed-off-by: Florian Westphal <fw@strlen.de>
---
 net/xfrm/xfrm_policy.c | 23 ++++++++++-------------
 1 file changed, 10 insertions(+), 13 deletions(-)

diff --git a/net/xfrm/xfrm_policy.c b/net/xfrm/xfrm_policy.c
index d8fba27a4bfb..24dfd1e47cf0 100644
--- a/net/xfrm/xfrm_policy.c
+++ b/net/xfrm/xfrm_policy.c
@@ -680,16 +680,6 @@ static void xfrm_hash_resize(struct work_struct *work)
 	mutex_unlock(&hash_resize_mutex);
 }
 
-static void xfrm_hash_reset_inexact_table(struct net *net)
-{
-	struct xfrm_pol_inexact_bin *b;
-
-	lockdep_assert_held(&net->xfrm.xfrm_policy_lock);
-
-	list_for_each_entry(b, &net->xfrm.inexact_bins, inexact_bins)
-		INIT_HLIST_HEAD(&b->hhead);
-}
-
 /* Make sure *pol can be inserted into fastbin.
  * Useful to check that later insert requests will be sucessful
  * (provided xfrm_policy_lock is held throughout).
@@ -1279,10 +1269,14 @@ static void xfrm_hash_rebuild(struct work_struct *work)
 	}
 
 	/* reset the bydst and inexact table in all directions */
-	xfrm_hash_reset_inexact_table(net);
-
 	for (dir = 0; dir < XFRM_POLICY_MAX; dir++) {
-		INIT_HLIST_HEAD(&net->xfrm.policy_inexact[dir]);
+		struct hlist_node *n;
+
+		hlist_for_each_entry_safe(policy, n,
+					  &net->xfrm.policy_inexact[dir],
+					  bydst_inexact_list)
+			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--)
@@ -1314,6 +1308,9 @@ static void xfrm_hash_rebuild(struct work_struct *work)
 		newpos = NULL;
 		chain = policy_hash_bysel(net, &policy->selector,
 					  policy->family, dir);
+
+		hlist_del_rcu(&policy->bydst);
+
 		if (!chain) {
 			void *p = xfrm_policy_inexact_insert(policy, dir, 0);
 
-- 
2.19.2

[PATCH ipsec 5/7] xfrm: policy: fix reinsertion on node merge

[Florian Westphal]

"newpos" has wrong scope.  It must be NULL on each iteration of the loop.
Otherwise, when policy is to be inserted at the start, we would instead
insert at point found by the previous loop-iteration instead.

Also, we need to unlink the policy before we reinsert it to the new node,
else we can get next-points-to-self loops.

Because policies are only ordered by priority it is irrelevant which policy
is "more recent" except when two policies have same priority.
(the more recent one is placed after the older one).

In these cases, we can use the ->pos id number to know which one is the
'older': the higher the id, the more recent the policy.

So we only need to unlink all policies from the node that is about to be
removed, and insert them to the replacement node.

Fixes: 9cf545ebd591da ("xfrm: policy: store inexact policies in a tree ordered by destination address")
Signed-off-by: Florian Westphal <fw@strlen.de>
---
 net/xfrm/xfrm_policy.c | 14 ++++++++------
 1 file changed, 8 insertions(+), 6 deletions(-)

diff --git a/net/xfrm/xfrm_policy.c b/net/xfrm/xfrm_policy.c
index 24dfd1e47cf0..e691683223ee 100644
--- a/net/xfrm/xfrm_policy.c
+++ b/net/xfrm/xfrm_policy.c
@@ -823,13 +823,13 @@ static void xfrm_policy_inexact_list_reinsert(struct net *net,
 					      u16 family)
 {
 	unsigned int matched_s, matched_d;
-	struct hlist_node *newpos = NULL;
 	struct xfrm_policy *policy, *p;
 
 	matched_s = 0;
 	matched_d = 0;
 
 	list_for_each_entry_reverse(policy, &net->xfrm.policy_all, walk.all) {
+		struct hlist_node *newpos = NULL;
 		bool matches_s, matches_d;
 
 		if (!policy->bydst_reinsert)
@@ -839,7 +839,10 @@ static void xfrm_policy_inexact_list_reinsert(struct net *net,
 
 		policy->bydst_reinsert = false;
 		hlist_for_each_entry(p, &n->hhead, bydst) {
-			if (policy->priority >= p->priority)
+			if (policy->priority > p->priority)
+				newpos = &p->bydst;
+			else if (policy->priority == p->priority &&
+				 policy->pos > p->pos)
 				newpos = &p->bydst;
 			else
 				break;
@@ -955,12 +958,11 @@ static void xfrm_policy_inexact_node_merge(struct net *net,
 						  family);
 	}
 
-	hlist_for_each_entry(tmp, &v->hhead, bydst)
-		tmp->bydst_reinsert = true;
-	hlist_for_each_entry(tmp, &n->hhead, bydst)
+	hlist_for_each_entry(tmp, &v->hhead, bydst) {
 		tmp->bydst_reinsert = true;
+		hlist_del_rcu(&tmp->bydst);
+	}
 
-	INIT_HLIST_HEAD(&n->hhead);
 	xfrm_policy_inexact_list_reinsert(net, n, family);
 }
 
-- 
2.19.2

[PATCH ipsec 6/7] selftests: xfrm: alter htresh to trigger move of policies to hash table

[Florian Westphal]

... and back to inexact tree.
Repeat ping test after each htresh change: lookup results must not change.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 tools/testing/selftests/net/xfrm_policy.sh | 44 ++++++++++++++++++++--
 1 file changed, 40 insertions(+), 4 deletions(-)

diff --git a/tools/testing/selftests/net/xfrm_policy.sh b/tools/testing/selftests/net/xfrm_policy.sh
index b5a1b565a7e6..8ce54600d4d1 100755
--- a/tools/testing/selftests/net/xfrm_policy.sh
+++ b/tools/testing/selftests/net/xfrm_policy.sh
@@ -28,6 +28,19 @@ KEY_AES=0x0123456789abcdef0123456789012345
 SPI1=0x1
 SPI2=0x2
 
+do_esp_policy() {
+    local ns=$1
+    local me=$2
+    local remote=$3
+    local lnet=$4
+    local rnet=$5
+
+    # to encrypt packets as they go out (includes forwarded packets that need encapsulation)
+    ip -net $ns xfrm policy add src $lnet dst $rnet dir out tmpl src $me dst $remote proto esp mode tunnel priority 100 action allow
+    # to fwd decrypted packets after esp processing:
+    ip -net $ns xfrm policy add src $rnet dst $lnet dir fwd tmpl src $remote dst $me proto esp mode tunnel priority 100 action allow
+}
+
 do_esp() {
     local ns=$1
     local me=$2
@@ -40,10 +53,7 @@ do_esp() {
     ip -net $ns xfrm state add src $remote dst $me proto esp spi $spi_in  enc aes $KEY_AES  auth sha1 $KEY_SHA  mode tunnel sel src $rnet dst $lnet
     ip -net $ns xfrm state add src $me  dst $remote proto esp spi $spi_out enc aes $KEY_AES auth sha1 $KEY_SHA mode tunnel sel src $lnet dst $rnet
 
-    # to encrypt packets as they go out (includes forwarded packets that need encapsulation)
-    ip -net $ns xfrm policy add src $lnet dst $rnet dir out tmpl src $me dst $remote proto esp mode tunnel priority 100 action allow
-    # to fwd decrypted packets after esp processing:
-    ip -net $ns xfrm policy add src $rnet dst $lnet dir fwd tmpl src $remote dst $me proto esp mode tunnel priority 100 action allow
+    do_esp_policy $ns $me $remote $lnet $rnet
 }
 
 # add policies with different netmasks, to make sure kernel carries
@@ -370,6 +380,32 @@ if [ $? -ne 0 ]; then
 	ret=1
 fi
 
+for n in ns3 ns4;do
+	ip -net $n xfrm policy set hthresh4 28 24 hthresh6 126 125
+	sleep $((RANDOM%5))
+done
+
+check_exceptions "exceptions and block policies after hresh changes"
+
+# full flush of policy db, check everything gets freed incl. internal meta data
+ip -net ns3 xfrm policy flush
+
+do_esp_policy ns3 10.0.3.1 10.0.3.10 10.0.1.0/24 10.0.2.0/24
+do_exception ns3 10.0.3.1 10.0.3.10 10.0.2.253 10.0.2.240/28
+
+# move inexact policies to hash table
+ip -net ns3 xfrm policy set hthresh4 16 16
+
+sleep $((RANDOM%5))
+check_exceptions "exceptions and block policies after hthresh change in ns3"
+
+# restore original hthresh settings -- move policies back to tables
+for n in ns3 ns4;do
+	ip -net $n xfrm policy set hthresh4 32 32 hthresh6 128 128
+	sleep $((RANDOM%5))
+done
+check_exceptions "exceptions and block policies after hresh change to normal"
+
 for i in 1 2 3 4;do ip netns del ns$i;done
 
 exit $ret
-- 
2.19.2

[PATCH ipsec 7/7] xfrm: policy: fix infinite loop when merging src-nodes

[Florian Westphal]

With very small change to test script we can trigger softlockup due to
bogus assignment of 'p' (policy to be examined) on restart.

Previously the two to-be-merged nodes had same address/prefixlength pair,
so no erase/reinsert was necessary, we only had to append the list from
node a to b.

If prefix lengths are different, the node has to be deleted and re-inserted
into the tree, with the updated prefix length.  This was broken; due to
bogus update to 'p' this loops forever.

Add a 'restart' label and use that instead.

While at it, don't perform the unneeded reinserts of the policies that
are already sorted into the 'new' node.

A previous patch in this series made xfrm_policy_inexact_list_reinsert()
use the relative position indicator to sort policies according to age in
case priorities are identical.

Fixes: 6ac098b2a9d30 ("xfrm: policy: add 2nd-level saddr trees for inexact policies")
Signed-off-by: Florian Westphal <fw@strlen.de>
---
 net/xfrm/xfrm_policy.c                     | 15 +++++++--------
 tools/testing/selftests/net/xfrm_policy.sh |  4 ++--
 2 files changed, 9 insertions(+), 10 deletions(-)

diff --git a/net/xfrm/xfrm_policy.c b/net/xfrm/xfrm_policy.c
index e691683223ee..8cfd75b62396 100644
--- a/net/xfrm/xfrm_policy.c
+++ b/net/xfrm/xfrm_policy.c
@@ -886,12 +886,13 @@ static void xfrm_policy_inexact_node_reinsert(struct net *net,
 					      struct rb_root *new,
 					      u16 family)
 {
-	struct rb_node **p, *parent = NULL;
 	struct xfrm_pol_inexact_node *node;
+	struct rb_node **p, *parent;
 
 	/* we should not have another subtree here */
 	WARN_ON_ONCE(!RB_EMPTY_ROOT(&n->root));
-
+restart:
+	parent = NULL;
 	p = &new->rb_node;
 	while (*p) {
 		u8 prefixlen;
@@ -911,12 +912,11 @@ static void xfrm_policy_inexact_node_reinsert(struct net *net,
 		} else {
 			struct xfrm_policy *tmp;
 
-			hlist_for_each_entry(tmp, &node->hhead, bydst)
-				tmp->bydst_reinsert = true;
-			hlist_for_each_entry(tmp, &n->hhead, bydst)
+			hlist_for_each_entry(tmp, &n->hhead, bydst) {
 				tmp->bydst_reinsert = true;
+				hlist_del_rcu(&tmp->bydst);
+			}
 
-			INIT_HLIST_HEAD(&node->hhead);
 			xfrm_policy_inexact_list_reinsert(net, node, family);
 
 			if (node->prefixlen == n->prefixlen) {
@@ -928,8 +928,7 @@ static void xfrm_policy_inexact_node_reinsert(struct net *net,
 			kfree_rcu(n, rcu);
 			n = node;
 			n->prefixlen = prefixlen;
-			*p = new->rb_node;
-			parent = NULL;
+			goto restart;
 		}
 	}
 
diff --git a/tools/testing/selftests/net/xfrm_policy.sh b/tools/testing/selftests/net/xfrm_policy.sh
index 8ce54600d4d1..71d7fdc513c1 100755
--- a/tools/testing/selftests/net/xfrm_policy.sh
+++ b/tools/testing/selftests/net/xfrm_policy.sh
@@ -78,8 +78,8 @@ do_overlap()
     # adds a new node in the 10.0.0.0/24 tree (dst node exists).
     ip -net $ns xfrm policy add src 10.2.0.0/24 dst 10.0.0.0/24 dir fwd priority 200 action block
 
-    # adds a 10.2.0.0/24 node, but for different dst.
-    ip -net $ns xfrm policy add src 10.2.0.0/24 dst 10.0.1.0/24 dir fwd priority 200 action block
+    # adds a 10.2.0.0/23 node, but for different dst.
+    ip -net $ns xfrm policy add src 10.2.0.0/23 dst 10.0.1.0/24 dir fwd priority 200 action block
 
     # dst now overlaps with the 10.0.1.0/24 ESP policy in fwd.
     # kernel must 'promote' existing one (10.0.0.0/24) to 10.0.0.0/23.
-- 
2.19.2

Re: [PATCH ipsec 4/7] xfrm: policy: delete inexact policies from inexact list on hash rebuild

[Cong Wang]

On Fri, Jan 4, 2019 at 5:19 AM Florian Westphal <fw@strlen.de> wrote:
>
> An xfrm hash rebuild has to reset the inexact policy list before the
> policies get re-inserted: A change of hash thresholds will result in
> policies to get moved from inexact tree to the policy hash table.
>
> If the thresholds are increased again later, they get moved from hash
> table to inexact tree.
>
> We must unlink all policies from the inexact tree before re-insertion.
>
> Otherwise 'migrate' may find policies that are in main hash table a
> second time, when it searches the inexact lists.
>
> Furthermore, re-insertion without deletion can cause elements ->next to
> point back to itself, causing soft lockups or double-frees.
>
> Reported-by: syzbot+9d971dd21eb26567036b@syzkaller.appspotmail.com
> Fixes: 9cf545ebd591da ("xfrm: policy: store inexact policies in a tree ordered by destination address")
> Signed-off-by: Florian Westphal <fw@strlen.de>
> ---
>  net/xfrm/xfrm_policy.c | 23 ++++++++++-------------
>  1 file changed, 10 insertions(+), 13 deletions(-)
>
> diff --git a/net/xfrm/xfrm_policy.c b/net/xfrm/xfrm_policy.c
> index d8fba27a4bfb..24dfd1e47cf0 100644
> --- a/net/xfrm/xfrm_policy.c
> +++ b/net/xfrm/xfrm_policy.c
> @@ -680,16 +680,6 @@ static void xfrm_hash_resize(struct work_struct *work)
>         mutex_unlock(&hash_resize_mutex);
>  }
>
> -static void xfrm_hash_reset_inexact_table(struct net *net)
> -{
> -       struct xfrm_pol_inexact_bin *b;
> -
> -       lockdep_assert_held(&net->xfrm.xfrm_policy_lock);
> -
> -       list_for_each_entry(b, &net->xfrm.inexact_bins, inexact_bins)
> -               INIT_HLIST_HEAD(&b->hhead);
> -}
> -
>  /* Make sure *pol can be inserted into fastbin.
>   * Useful to check that later insert requests will be sucessful
>   * (provided xfrm_policy_lock is held throughout).
> @@ -1279,10 +1269,14 @@ static void xfrm_hash_rebuild(struct work_struct *work)
>         }
>
>         /* reset the bydst and inexact table in all directions */


Does this comment need to update?


> -       xfrm_hash_reset_inexact_table(net);
> -
>         for (dir = 0; dir < XFRM_POLICY_MAX; dir++) {
> -               INIT_HLIST_HEAD(&net->xfrm.policy_inexact[dir]);
> +               struct hlist_node *n;
> +
> +               hlist_for_each_entry_safe(policy, n,
> +                                         &net->xfrm.policy_inexact[dir],
> +                                         bydst_inexact_list)
> +                       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--)
> @@ -1314,6 +1308,9 @@ static void xfrm_hash_rebuild(struct work_struct *work)
>                 newpos = NULL;
>                 chain = policy_hash_bysel(net, &policy->selector,
>                                           policy->family, dir);
> +
> +               hlist_del_rcu(&policy->bydst);


Need to test hlist_unhashed()?


> +
>                 if (!chain) {
>                         void *p = xfrm_policy_inexact_insert(policy, dir, 0);
>
> --
> 2.19.2
>

Re: [PATCH ipsec 5/7] xfrm: policy: fix reinsertion on node merge

[Cong Wang]

On Fri, Jan 4, 2019 at 5:19 AM Florian Westphal <fw@strlen.de> wrote:
>
> "newpos" has wrong scope.  It must be NULL on each iteration of the loop.
> Otherwise, when policy is to be inserted at the start, we would instead
> insert at point found by the previous loop-iteration instead.
>
> Also, we need to unlink the policy before we reinsert it to the new node,
> else we can get next-points-to-self loops.
>
> Because policies are only ordered by priority it is irrelevant which policy
> is "more recent" except when two policies have same priority.
> (the more recent one is placed after the older one).
>
> In these cases, we can use the ->pos id number to know which one is the
> 'older': the higher the id, the more recent the policy.
>
> So we only need to unlink all policies from the node that is about to be
> removed, and insert them to the replacement node.
>
> Fixes: 9cf545ebd591da ("xfrm: policy: store inexact policies in a tree ordered by destination address")
> Signed-off-by: Florian Westphal <fw@strlen.de>
> ---
>  net/xfrm/xfrm_policy.c | 14 ++++++++------
>  1 file changed, 8 insertions(+), 6 deletions(-)
>
> diff --git a/net/xfrm/xfrm_policy.c b/net/xfrm/xfrm_policy.c
> index 24dfd1e47cf0..e691683223ee 100644
> --- a/net/xfrm/xfrm_policy.c
> +++ b/net/xfrm/xfrm_policy.c
> @@ -823,13 +823,13 @@ static void xfrm_policy_inexact_list_reinsert(struct net *net,
>                                               u16 family)
>  {
>         unsigned int matched_s, matched_d;
> -       struct hlist_node *newpos = NULL;
>         struct xfrm_policy *policy, *p;
>
>         matched_s = 0;
>         matched_d = 0;
>
>         list_for_each_entry_reverse(policy, &net->xfrm.policy_all, walk.all) {
> +               struct hlist_node *newpos = NULL;
>                 bool matches_s, matches_d;
>
>                 if (!policy->bydst_reinsert)
> @@ -839,7 +839,10 @@ static void xfrm_policy_inexact_list_reinsert(struct net *net,
>
>                 policy->bydst_reinsert = false;
>                 hlist_for_each_entry(p, &n->hhead, bydst) {
> -                       if (policy->priority >= p->priority)
> +                       if (policy->priority > p->priority)
> +                               newpos = &p->bydst;
> +                       else if (policy->priority == p->priority &&
> +                                policy->pos > p->pos)
>                                 newpos = &p->bydst;
>                         else
>                                 break;
> @@ -955,12 +958,11 @@ static void xfrm_policy_inexact_node_merge(struct net *net,
>                                                   family);
>         }
>
> -       hlist_for_each_entry(tmp, &v->hhead, bydst)
> -               tmp->bydst_reinsert = true;
> -       hlist_for_each_entry(tmp, &n->hhead, bydst)
> +       hlist_for_each_entry(tmp, &v->hhead, bydst) {


hlist_for_each_entry_safe()?


>                 tmp->bydst_reinsert = true;
> +               hlist_del_rcu(&tmp->bydst);
> +       }
>
> -       INIT_HLIST_HEAD(&n->hhead);
>         xfrm_policy_inexact_list_reinsert(net, n, family);
>  }
>
> --
> 2.19.2
>

Re: [PATCH ipsec 7/7] xfrm: policy: fix infinite loop when merging src-nodes

[Cong Wang]

On Fri, Jan 4, 2019 at 5:19 AM Florian Westphal <fw@strlen.de> wrote:
>
> With very small change to test script we can trigger softlockup due to
> bogus assignment of 'p' (policy to be examined) on restart.
>
> Previously the two to-be-merged nodes had same address/prefixlength pair,
> so no erase/reinsert was necessary, we only had to append the list from
> node a to b.
>
> If prefix lengths are different, the node has to be deleted and re-inserted
> into the tree, with the updated prefix length.  This was broken; due to
> bogus update to 'p' this loops forever.
>
> Add a 'restart' label and use that instead.
>
> While at it, don't perform the unneeded reinserts of the policies that
> are already sorted into the 'new' node.
>
> A previous patch in this series made xfrm_policy_inexact_list_reinsert()
> use the relative position indicator to sort policies according to age in
> case priorities are identical.
>
> Fixes: 6ac098b2a9d30 ("xfrm: policy: add 2nd-level saddr trees for inexact policies")
> Signed-off-by: Florian Westphal <fw@strlen.de>
> ---
>  net/xfrm/xfrm_policy.c                     | 15 +++++++--------
>  tools/testing/selftests/net/xfrm_policy.sh |  4 ++--
>  2 files changed, 9 insertions(+), 10 deletions(-)
>
> diff --git a/net/xfrm/xfrm_policy.c b/net/xfrm/xfrm_policy.c
> index e691683223ee..8cfd75b62396 100644
> --- a/net/xfrm/xfrm_policy.c
> +++ b/net/xfrm/xfrm_policy.c
> @@ -886,12 +886,13 @@ static void xfrm_policy_inexact_node_reinsert(struct net *net,
>                                               struct rb_root *new,
>                                               u16 family)
>  {
> -       struct rb_node **p, *parent = NULL;
>         struct xfrm_pol_inexact_node *node;
> +       struct rb_node **p, *parent;
>
>         /* we should not have another subtree here */
>         WARN_ON_ONCE(!RB_EMPTY_ROOT(&n->root));
> -
> +restart:
> +       parent = NULL;
>         p = &new->rb_node;
>         while (*p) {
>                 u8 prefixlen;
> @@ -911,12 +912,11 @@ static void xfrm_policy_inexact_node_reinsert(struct net *net,
>                 } else {
>                         struct xfrm_policy *tmp;
>
> -                       hlist_for_each_entry(tmp, &node->hhead, bydst)
> -                               tmp->bydst_reinsert = true;
> -                       hlist_for_each_entry(tmp, &n->hhead, bydst)
> +                       hlist_for_each_entry(tmp, &n->hhead, bydst) {


hlist_for_each_entry_safe()?


>                                 tmp->bydst_reinsert = true;
> +                               hlist_del_rcu(&tmp->bydst);
> +                       }
>
> -                       INIT_HLIST_HEAD(&node->hhead);
>                         xfrm_policy_inexact_list_reinsert(net, node, family);
>
>                         if (node->prefixlen == n->prefixlen) {
> @@ -928,8 +928,7 @@ static void xfrm_policy_inexact_node_reinsert(struct net *net,
>                         kfree_rcu(n, rcu);
>                         n = node;
>                         n->prefixlen = prefixlen;
> -                       *p = new->rb_node;
> -                       parent = NULL;
> +                       goto restart;
>                 }
>         }
>
> diff --git a/tools/testing/selftests/net/xfrm_policy.sh b/tools/testing/selftests/net/xfrm_policy.sh
> index 8ce54600d4d1..71d7fdc513c1 100755
> --- a/tools/testing/selftests/net/xfrm_policy.sh
> +++ b/tools/testing/selftests/net/xfrm_policy.sh
> @@ -78,8 +78,8 @@ do_overlap()
>      # adds a new node in the 10.0.0.0/24 tree (dst node exists).
>      ip -net $ns xfrm policy add src 10.2.0.0/24 dst 10.0.0.0/24 dir fwd priority 200 action block
>
> -    # adds a 10.2.0.0/24 node, but for different dst.
> -    ip -net $ns xfrm policy add src 10.2.0.0/24 dst 10.0.1.0/24 dir fwd priority 200 action block
> +    # adds a 10.2.0.0/23 node, but for different dst.
> +    ip -net $ns xfrm policy add src 10.2.0.0/23 dst 10.0.1.0/24 dir fwd priority 200 action block
>
>      # dst now overlaps with the 10.0.1.0/24 ESP policy in fwd.
>      # kernel must 'promote' existing one (10.0.0.0/24) to 10.0.0.0/23.
> --
> 2.19.2
>

Re: [PATCH ipsec 4/7] xfrm: policy: delete inexact policies from inexact list on hash rebuild

[Florian Westphal]

Cong Wang <xiyou.wangcong@gmail.com> wrote:
> On Fri, Jan 4, 2019 at 5:19 AM Florian Westphal <fw@strlen.de> wrote:
> >
> > An xfrm hash rebuild has to reset the inexact policy list before the
> > policies get re-inserted: A change of hash thresholds will result in
> > policies to get moved from inexact tree to the policy hash table.
> >
> > If the thresholds are increased again later, they get moved from hash
> > table to inexact tree.
> >
> > We must unlink all policies from the inexact tree before re-insertion.
> >
> > Otherwise 'migrate' may find policies that are in main hash table a
> > second time, when it searches the inexact lists.
> >
> > Furthermore, re-insertion without deletion can cause elements ->next to
> > point back to itself, causing soft lockups or double-frees.
> >
> > Reported-by: syzbot+9d971dd21eb26567036b@syzkaller.appspotmail.com
> > Fixes: 9cf545ebd591da ("xfrm: policy: store inexact policies in a tree ordered by destination address")
> > Signed-off-by: Florian Westphal <fw@strlen.de>
> > ---
> >  net/xfrm/xfrm_policy.c | 23 ++++++++++-------------
> >  1 file changed, 10 insertions(+), 13 deletions(-)
> >
> > diff --git a/net/xfrm/xfrm_policy.c b/net/xfrm/xfrm_policy.c
> > index d8fba27a4bfb..24dfd1e47cf0 100644
> > --- a/net/xfrm/xfrm_policy.c
> > +++ b/net/xfrm/xfrm_policy.c
> > @@ -680,16 +680,6 @@ static void xfrm_hash_resize(struct work_struct *work)
> >         mutex_unlock(&hash_resize_mutex);
> >  }
> >
> > -static void xfrm_hash_reset_inexact_table(struct net *net)
> > -{
> > -       struct xfrm_pol_inexact_bin *b;
> > -
> > -       lockdep_assert_held(&net->xfrm.xfrm_policy_lock);
> > -
> > -       list_for_each_entry(b, &net->xfrm.inexact_bins, inexact_bins)
> > -               INIT_HLIST_HEAD(&b->hhead);
> > -}
> > -
> >  /* Make sure *pol can be inserted into fastbin.
> >   * Useful to check that later insert requests will be sucessful
> >   * (provided xfrm_policy_lock is held throughout).
> > @@ -1279,10 +1269,14 @@ static void xfrm_hash_rebuild(struct work_struct *work)
> >         }
> >
> >         /* reset the bydst and inexact table in all directions */
> 
> 
> Does this comment need to update?

I don't think so, it predates my changes and we still reset the
inexact trees.

What would you suggest the comment should read?
 
> > +               hlist_del_rcu(&policy->bydst);
> 
> 
> Need to test hlist_unhashed()?

No, all policies are in a hlist, either via the exact hash table or
an inexact tree list.

Also, the _rcu version leaves entry in undefined state so hlist_unhashed
doesn't return true.

Re: [PATCH ipsec 5/7] xfrm: policy: fix reinsertion on node merge

[Florian Westphal]

Cong Wang <xiyou.wangcong@gmail.com> wrote:
> > -       hlist_for_each_entry(tmp, &v->hhead, bydst)
> > -               tmp->bydst_reinsert = true;
> > -       hlist_for_each_entry(tmp, &n->hhead, bydst)
> > +       hlist_for_each_entry(tmp, &v->hhead, bydst) {
> 
> 
> hlist_for_each_entry_safe()?

Good question.  Its not necessary from a technical point of view
because tmp isn't free'd and hlist_del_rcu leaves tmp->next alone.

But perhaps its still better to use _safe variant.

I'll let Steffen decide.

Re: [PATCH ipsec 7/7] xfrm: policy: fix infinite loop when merging src-nodes

[Florian Westphal]

Cong Wang <xiyou.wangcong@gmail.com> wrote:
> > -                       hlist_for_each_entry(tmp, &node->hhead, bydst)
> > -                               tmp->bydst_reinsert = true;
> > -                       hlist_for_each_entry(tmp, &n->hhead, bydst)
> > +                       hlist_for_each_entry(tmp, &n->hhead, bydst) {
> 
> 
> hlist_for_each_entry_safe()?

Could be used instead indeed, but its not required.

Steffen, just let me know your preference. If you think that

hlist_for_each_entry(...)
   hlist_del_rcu(&tmp->bydst);

... looks unsafe then i can respin this with _safe version.

Re: [PATCH ipsec 7/7] xfrm: policy: fix infinite loop when merging src-nodes

[Steffen Klassert]

On Sat, Jan 05, 2019 at 10:59:08AM +0100, Florian Westphal wrote:
> Cong Wang <xiyou.wangcong@gmail.com> wrote:
> > > -                       hlist_for_each_entry(tmp, &node->hhead, bydst)
> > > -                               tmp->bydst_reinsert = true;
> > > -                       hlist_for_each_entry(tmp, &n->hhead, bydst)
> > > +                       hlist_for_each_entry(tmp, &n->hhead, bydst) {
> > 
> > 
> > hlist_for_each_entry_safe()?
> 
> Could be used instead indeed, but its not required.
> 
> Steffen, just let me know your preference.

I tend to apply the patchset as is after
some testing.

Re: [PATCH ipsec 0/7] xfrm: policy: fix various bugs

[Steffen Klassert]

On Fri, Jan 04, 2019 at 02:16:58PM +0100, Florian Westphal wrote:
> This series addresses various bugs, mostly fallout from the recent
> rcu tree work. One is a fix for an older bug coming from the initial
> rcu conversion.
> 
> There were several xfrm policy related syzbot bugs recently, but
> so far only one of them has a reproducer (addressed by patch #4).
> 
> As I provided ample rope for syzbot to hang itself with, there is
> some chance that this and the other fixes also resolve the KASAN
> and UAF syzbot xfrm reports reported in the last couple of days.
> 
> My plan is to wait until these patches are applied, and then tell syzbot
> for all the open reports that the last patch 'fixes this'.
> 
> AFAIU that will make syzbot report the problem again in case it can still
> trigger similar splats with these fixes in place.
> 
> Florian Westphal (7):
>       selftests: xfrm: add block rules with adjacent/overlapping subnets
>       xfrm: policy: use hlist rcu variants on inexact insert, part 2
>       xfrm: policy: increment xfrm_hash_generation on hash rebuild
>       xfrm: policy: delete inexact policies from inexact list on hash rebuild
>       xfrm: policy: fix reinsertion on node merge
>       selftests: xfrm: alter htresh to trigger move of policies to hash table
>       xfrm: policy: fix infinite loop when merging src-nodes

All applied, thanks a lot Florian!