[net PATCH 0/2] IPv4 FIB suffix length fixes

[net PATCH 0/2] IPv4 FIB suffix length fixes

[Alexander Duyck]

In reviewing the patch from Robert Shearman and looking over the code I
realized there were a few different bugs we were still carrying in the IPv4
FIB lookup code.

These two patches are based off of Robert's original patch, but take things
one step further by splitting them up to address two additional issues I
found.

So first have Robert's original patch which was addressing the fact that
us calling update_suffix in resize is expensive when it is called per add.
To address that I incorporated the core bit of the patch which was us
dropping the update_suffix call from resize.

The first patch in the series does a rename and fix on the push_suffix and
pull_suffix code.  Specifically we drop the need to pass a leaf and
secondly we fix things so we pull the suffix as long as the value of the
suffix in the node is dropping.

The second patch addresses the original issue reported as well as
optimizing the code for the fact that update_suffix is only really meant to
go through and clean things up when we are decreasing a suffix.  I had
originally added code for it to somehow cause an increase, but if we push
the suffix when a new leaf is added we only ever have to handle pulling
down the suffix with update_suffix so I updated the code to reflect that.

As far as side effects the only ones I think that will be obvious should be
the fact that some routes may be able to be found earlier since before we
relied on resize to update the suffix lengths, and now we are updating them
before we add or remove the leaf.

---

Alexander Duyck (2):
      ipv4: Drop leaf from suffix pull/push functions
      ipv4: Drop suffix update from resize code


 net/ipv4/fib_trie.c |   68 ++++++++++++++++++++++++++-------------------------
 1 file changed, 35 insertions(+), 33 deletions(-)

[net PATCH 1/2] ipv4: Drop leaf from suffix pull/push functions

[Alexander Duyck]

It wasn't necessary to pass a leaf in when doing the suffix updates so just
drop it.  Instead just pass the suffix and work with that.

Since we dropped the leaf there is no need to include that in the name so
the names are updated to node_push_suffix and node_pull_suffix.

Finally I noticed that the logic for pulling the suffix length back
actually had some issues.  Specifically it would stop prematurely if there
was a longer suffix, but it was not as long as the original suffix.  I
updated the code to address that in node_pull_suffix.

Fixes: 5405afd1a306 ("fib_trie: Add tracking value for suffix length")
Suggested-by: Robert Shearman <rshearma@brocade.com>
Signed-off-by: Alexander Duyck <alexander.h.duyck@intel.com>
---
 net/ipv4/fib_trie.c |   26 ++++++++++++++------------
 1 file changed, 14 insertions(+), 12 deletions(-)

diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index e2ffc2a..c5cd226 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -892,22 +892,24 @@ static struct key_vector *resize(struct trie *t, struct key_vector *tn)
 	return tp;
 }
 
-static void leaf_pull_suffix(struct key_vector *tp, struct key_vector *l)
+static void node_pull_suffix(struct key_vector *tn, unsigned char slen)
 {
-	while ((tp->slen > tp->pos) && (tp->slen > l->slen)) {
-		if (update_suffix(tp) > l->slen)
+	unsigned char node_slen = tn->slen;
+
+	while ((node_slen > tn->pos) && (node_slen > slen)) {
+		slen = update_suffix(tn);
+		if (node_slen == slen)
 			break;
-		tp = node_parent(tp);
+
+		tn = node_parent(tn);
+		node_slen = tn->slen;
 	}
 }
 
-static void leaf_push_suffix(struct key_vector *tn, struct key_vector *l)
+static void node_push_suffix(struct key_vector *tn, unsigned char slen)
 {
-	/* if this is a new leaf then tn will be NULL and we can sort
-	 * out parent suffix lengths as a part of trie_rebalance
-	 */
-	while (tn->slen < l->slen) {
-		tn->slen = l->slen;
+	while (tn->slen < slen) {
+		tn->slen = slen;
 		tn = node_parent(tn);
 	}
 }
@@ -1069,7 +1071,7 @@ static int fib_insert_alias(struct trie *t, struct key_vector *tp,
 	/* if we added to the tail node then we need to update slen */
 	if (l->slen < new->fa_slen) {
 		l->slen = new->fa_slen;
-		leaf_push_suffix(tp, l);
+		node_push_suffix(tp, new->fa_slen);
 	}
 
 	return 0;
@@ -1482,7 +1484,7 @@ static void fib_remove_alias(struct trie *t, struct key_vector *tp,
 
 	/* update the trie with the latest suffix length */
 	l->slen = fa->fa_slen;
-	leaf_pull_suffix(tp, l);
+	node_pull_suffix(tp, fa->fa_slen);
 }
 
 /* Caller must hold RTNL. */

[net PATCH 2/2] ipv4: Drop suffix update from resize code

[Alexander Duyck]

It has been reported that update_suffix can be expensive when it is called
on a large node in which most of the suffix lengths are the same.  The time
required to add 200K entries had increased from around 3 seconds to almost
49 seconds.

In order to address this we need to move the code for updating the suffix
out of resize and instead just have it handled in the cases where we are
pushing a node that increases the suffix length, or will decrease the
suffix length.

Fixes: 5405afd1a306 ("fib_trie: Add tracking value for suffix length")
Reported-by: Robert Shearman <rshearma@brocade.com>
Signed-off-by: Alexander Duyck <alexander.h.duyck@intel.com>
---
 net/ipv4/fib_trie.c |   42 +++++++++++++++++++++---------------------
 1 file changed, 21 insertions(+), 21 deletions(-)

diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index c5cd226..2cfa9f4 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -681,6 +681,13 @@ static unsigned char update_suffix(struct key_vector *tn)
 {
 	unsigned char slen = tn->pos;
 	unsigned long stride, i;
+	unsigned char slen_max;
+
+	/* only vector 0 can have a suffix length greater than or equal to
+	 * tn->pos + tn->bits, the second highest node will have a suffix
+	 * length at most of tn->pos + tn->bits - 1
+	 */
+	slen_max = min_t(unsigned char, tn->pos + tn->bits - 1, tn->slen);
 
 	/* search though the list of children looking for nodes that might
 	 * have a suffix greater than the one we currently have.  This is
@@ -698,12 +705,8 @@ static unsigned char update_suffix(struct key_vector *tn)
 		slen = n->slen;
 		i &= ~(stride - 1);
 
-		/* if slen covers all but the last bit we can stop here
-		 * there will be nothing longer than that since only node
-		 * 0 and 1 << (bits - 1) could have that as their suffix
-		 * length.
-		 */
-		if ((slen + 1) >= (tn->pos + tn->bits))
+		/* stop searching if we have hit the maximum possible value */
+		if (slen >= slen_max)
 			break;
 	}
 
@@ -875,21 +878,7 @@ static struct key_vector *resize(struct trie *t, struct key_vector *tn)
 		return collapse(t, tn);
 
 	/* update parent in case halve failed */
-	tp = node_parent(tn);
-
-	/* Return if at least one deflate was run */
-	if (max_work != MAX_WORK)
-		return tp;
-
-	/* push the suffix length to the parent node */
-	if (tn->slen > tn->pos) {
-		unsigned char slen = update_suffix(tn);
-
-		if (slen > tp->slen)
-			tp->slen = slen;
-	}
-
-	return tp;
+	return node_parent(tn);
 }
 
 static void node_pull_suffix(struct key_vector *tn, unsigned char slen)
@@ -1030,6 +1019,7 @@ static int fib_insert_node(struct trie *t, struct key_vector *tp,
 	}
 
 	/* Case 3: n is NULL, and will just insert a new leaf */
+	node_push_suffix(tp, new->fa_slen);
 	NODE_INIT_PARENT(l, tp);
 	put_child_root(tp, key, l);
 	trie_rebalance(t, tp);
@@ -1472,6 +1462,8 @@ static void fib_remove_alias(struct trie *t, struct key_vector *tp,
 	 * out parent suffix lengths as a part of trie_rebalance
 	 */
 	if (hlist_empty(&l->leaf)) {
+		if (tp->slen == l->slen)
+			node_pull_suffix(tp, tp->pos);
 		put_child_root(tp, l->key, NULL);
 		node_free(l);
 		trie_rebalance(t, tp);
@@ -1753,6 +1745,10 @@ void fib_table_flush_external(struct fib_table *tb)
 			if (IS_TRIE(pn))
 				break;
 
+			/* update the suffix to address pulled leaves */
+			if (pn->slen > pn->pos)
+				update_suffix(pn);
+
 			/* resize completed node */
 			pn = resize(t, pn);
 			cindex = get_index(pkey, pn);
@@ -1828,6 +1824,10 @@ int fib_table_flush(struct fib_table *tb)
 			if (IS_TRIE(pn))
 				break;
 
+			/* update the suffix to address pulled leaves */
+			if (pn->slen > pn->pos)
+				update_suffix(pn);
+
 			/* resize completed node */
 			pn = resize(t, pn);
 			cindex = get_index(pkey, pn);

Re: [net PATCH 1/2] ipv4: Drop leaf from suffix pull/push functions

[Robert Shearman]

On 01/12/16 12:27, Alexander Duyck wrote:
> It wasn't necessary to pass a leaf in when doing the suffix updates so just
> drop it.  Instead just pass the suffix and work with that.
>
> Since we dropped the leaf there is no need to include that in the name so
> the names are updated to node_push_suffix and node_pull_suffix.
>
> Finally I noticed that the logic for pulling the suffix length back
> actually had some issues.  Specifically it would stop prematurely if there
> was a longer suffix, but it was not as long as the original suffix.  I
> updated the code to address that in node_pull_suffix.
>
> Fixes: 5405afd1a306 ("fib_trie: Add tracking value for suffix length")
> Suggested-by: Robert Shearman <rshearma@brocade.com>
> Signed-off-by: Alexander Duyck <alexander.h.duyck@intel.com>

This addresses an issue in the current code whereby when a fib alias is 
removed from a leaf when there are other aliases remaining then the 
suffix length may not be updated in the conditions described above. This 
is because fib_remove_alias doesn't call trie_rebalance (or resize) in 
this case, as there's no need since no nodes have been added/removed.

This can be reproduced with this structure of the fib trie and by adding 
and then deleting 10.37.96.0/19:

         +-- 10.37.0.0/16 4 1 8 suffix/19
            |-- 10.37.0.0
               /24 universe UNICAST
            |-- 10.37.32.0
               /24 universe UNICAST
            |-- 10.37.64.0
               /20 universe UNICAST
            |-- 10.37.95.0
               /24 universe UNICAST
            +-- 10.37.96.0/20 2 1 2 suffix/21
               +-- 10.37.96.0/22 2 1 2 suffix/24
                  +-- 10.37.96.0/24 2 1 2 suffix/24
                     |-- 10.37.96.0
                        /32 link BROADCAST
                        /24 link UNICAST
                     +-- 10.37.96.192/26 2 0 2 suffix/28
                        |-- 10.37.96.204
                           /32 host LOCAL
                        |-- 10.37.96.255
                           /32 link BROADCAST
                  |-- 10.37.98.0
                     /25 universe UNICAST
               |-- 10.37.104.0
                  /21 universe UNICAST
            +-- 10.37.112.0/23 2 0 2 suffix/24
               |-- 10.37.112.0
                  /24 universe UNICAST
               |-- 10.37.113.0
                  /24 universe UNICAST
            |-- 10.37.223.0
               /24 universe UNICAST
            |-- 10.37.224.0
               /24 universe UNICAST

I've verified that with the fix included here that the suffix length on 
the 10.37.0.0/16 node now gets updated correctly to be /20.

Reviewed-by: Robert Shearman <rshearma@brocade.com>
Tested-by: Robert Shearman <rshearma@brocade.com>

Thanks,
Rob

Re: [net PATCH 2/2] ipv4: Drop suffix update from resize code

[Robert Shearman]

On 01/12/16 12:27, Alexander Duyck wrote:
> It has been reported that update_suffix can be expensive when it is called
> on a large node in which most of the suffix lengths are the same.  The time
> required to add 200K entries had increased from around 3 seconds to almost
> 49 seconds.
>
> In order to address this we need to move the code for updating the suffix
> out of resize and instead just have it handled in the cases where we are
> pushing a node that increases the suffix length, or will decrease the
> suffix length.
>
> Fixes: 5405afd1a306 ("fib_trie: Add tracking value for suffix length")
> Reported-by: Robert Shearman <rshearma@brocade.com>
> Signed-off-by: Alexander Duyck <alexander.h.duyck@intel.com>

$ time sudo ip route restore < ~/allroutes
RTNETLINK answers: File exists
RTNETLINK answers: File exists
RTNETLINK answers: File exists
RTNETLINK answers: File exists

real	0m4.026s
user	0m0.156s
sys	0m2.500s
$ time sudo ip route flush via 110.110.110.2

real	0m5.423s
user	0m0.064s
sys	0m1.096s

This reduces the time taken to both add and delete the 200k routes back 
down to levels comparable before commit 5405afd1a306. The changes look 
good to me too. Nicely done Alex!

Reviewed-by: Robert Shearman <rshearma@brocade.com>
Tested-by: Robert Shearman <rshearma@brocade.com>

Thanks,
Rob

Re: [net PATCH 2/2] ipv4: Drop suffix update from resize code

[David Miller]

From: Robert Shearman <rshearma@brocade.com>
Date: Mon, 5 Dec 2016 15:05:18 +0000

> On 01/12/16 12:27, Alexander Duyck wrote:
>> It has been reported that update_suffix can be expensive when it is
>> called
>> on a large node in which most of the suffix lengths are the same.  The
>> time
>> required to add 200K entries had increased from around 3 seconds to
>> almost
>> 49 seconds.
>>
>> In order to address this we need to move the code for updating the
>> suffix
>> out of resize and instead just have it handled in the cases where we
>> are
>> pushing a node that increases the suffix length, or will decrease the
>> suffix length.
>>
>> Fixes: 5405afd1a306 ("fib_trie: Add tracking value for suffix length")
>> Reported-by: Robert Shearman <rshearma@brocade.com>
>> Signed-off-by: Alexander Duyck <alexander.h.duyck@intel.com>
> 
> $ time sudo ip route restore < ~/allroutes
> RTNETLINK answers: File exists
> RTNETLINK answers: File exists
> RTNETLINK answers: File exists
> RTNETLINK answers: File exists

What are these errors all about?

Re: [net PATCH 2/2] ipv4: Drop suffix update from resize code

[Duyck, Alexander H]

On Mon, 2016-12-05 at 12:28 -0500, David Miller wrote:
> From: Robert Shearman <rshearma@brocade.com>
> Date: Mon, 5 Dec 2016 15:05:18 +0000
> 
> > 
> > On 01/12/16 12:27, Alexander Duyck wrote:
> > > 
> > > It has been reported that update_suffix can be expensive when it is
> > > called
> > > on a large node in which most of the suffix lengths are the same.  The
> > > time
> > > required to add 200K entries had increased from around 3 seconds to
> > > almost
> > > 49 seconds.
> > > 
> > > In order to address this we need to move the code for updating the
> > > suffix
> > > out of resize and instead just have it handled in the cases where we
> > > are
> > > pushing a node that increases the suffix length, or will decrease the
> > > suffix length.
> > > 
> > > Fixes: 5405afd1a306 ("fib_trie: Add tracking value for suffix length")
> > > Reported-by: Robert Shearman <rshearma@brocade.com>
> > > Signed-off-by: Alexander Duyck <alexander.h.duyck@intel.com>
> > 
> > $ time sudo ip route restore < ~/allroutes
> > RTNETLINK answers: File exists
> > RTNETLINK answers: File exists
> > RTNETLINK answers: File exists
> > RTNETLINK answers: File exists
> 
> What are these errors all about?

I think it is the fact that he is trying to restore "all routes" and
some of the routes already exist such as those associated with his
default network interface.

- Alex

Re: [net PATCH 0/2] IPv4 FIB suffix length fixes

[David Miller]

From: Alexander Duyck <alexander.h.duyck@intel.com>
Date: Thu, 01 Dec 2016 07:27:47 -0500

> In reviewing the patch from Robert Shearman and looking over the code I
> realized there were a few different bugs we were still carrying in the IPv4
> FIB lookup code.
> 
> These two patches are based off of Robert's original patch, but take things
> one step further by splitting them up to address two additional issues I
> found.
> 
> So first have Robert's original patch which was addressing the fact that
> us calling update_suffix in resize is expensive when it is called per add.
> To address that I incorporated the core bit of the patch which was us
> dropping the update_suffix call from resize.
> 
> The first patch in the series does a rename and fix on the push_suffix and
> pull_suffix code.  Specifically we drop the need to pass a leaf and
> secondly we fix things so we pull the suffix as long as the value of the
> suffix in the node is dropping.
> 
> The second patch addresses the original issue reported as well as
> optimizing the code for the fact that update_suffix is only really meant to
> go through and clean things up when we are decreasing a suffix.  I had
> originally added code for it to somehow cause an increase, but if we push
> the suffix when a new leaf is added we only ever have to handle pulling
> down the suffix with update_suffix so I updated the code to reflect that.
> 
> As far as side effects the only ones I think that will be obvious should be
> the fact that some routes may be able to be found earlier since before we
> relied on resize to update the suffix lengths, and now we are updating them
> before we add or remove the leaf.

Series applied and queued up for -stable, thanks Alex.

Re: [net PATCH 2/2] ipv4: Drop suffix update from resize code

[Robert Shearman]

On 05/12/16 17:28, David Miller wrote:
> From: Robert Shearman <rshearma@brocade.com>
> Date: Mon, 5 Dec 2016 15:05:18 +0000
>
>> On 01/12/16 12:27, Alexander Duyck wrote:
>>> It has been reported that update_suffix can be expensive when it is
>>> called
>>> on a large node in which most of the suffix lengths are the same.  The
>>> time
>>> required to add 200K entries had increased from around 3 seconds to
>>> almost
>>> 49 seconds.
>>>
>>> In order to address this we need to move the code for updating the
>>> suffix
>>> out of resize and instead just have it handled in the cases where we
>>> are
>>> pushing a node that increases the suffix length, or will decrease the
>>> suffix length.
>>>
>>> Fixes: 5405afd1a306 ("fib_trie: Add tracking value for suffix length")
>>> Reported-by: Robert Shearman <rshearma@brocade.com>
>>> Signed-off-by: Alexander Duyck <alexander.h.duyck@intel.com>
>>
>> $ time sudo ip route restore < ~/allroutes
>> RTNETLINK answers: File exists
>> RTNETLINK answers: File exists
>> RTNETLINK answers: File exists
>> RTNETLINK answers: File exists
>
> What are these errors all about?

These are just routes that are already added by the system but are 
present in the dump:

$ ip route showdump < ~/allroutes | grep -v 110.110.110.2
default via 192.168.100.1 dev eth0  proto static  metric 1024
10.37.96.0/20 dev eth2  proto kernel  scope link  src 10.37.96.204
110.110.110.0/24 dev eth1  proto kernel  scope link  src 110.110.110.1
192.168.100.0/24 dev eth0  proto kernel  scope link  src 192.168.100.153

So the errors are expected and are seen both with and without these patches.

Thanks,
Rob