kernel: update kernel 3.18 to version 3.18.23
[openwrt/staging/chunkeey.git] / target / linux / generic / patches-3.18 / 080-01-fib_trie-Fix-trie-balancing-issue-if-new-node-pushes.patch
1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
2 Date: Wed, 10 Dec 2014 21:49:22 -0800
3 Subject: [PATCH] fib_trie: Fix trie balancing issue if new node pushes down
4 existing node
5
6 This patch addresses an issue with the level compression of the fib_trie.
7 Specifically in the case of adding a new leaf that triggers a new node to
8 be added that takes the place of the old node. The result is a trie where
9 the 1 child tnode is on one side and one leaf is on the other which gives
10 you a very deep trie. Below is the script I used to generate a trie on
11 dummy0 with a 10.X.X.X family of addresses.
12
13 ip link add type dummy
14 ipval=184549374
15 bit=2
16 for i in `seq 1 23`
17 do
18 ifconfig dummy0:$bit $ipval/8
19 ipval=`expr $ipval - $bit`
20 bit=`expr $bit \* 2`
21 done
22 cat /proc/net/fib_triestat
23
24 Running the script before the patch:
25
26 Local:
27 Aver depth: 10.82
28 Max depth: 23
29 Leaves: 29
30 Prefixes: 30
31 Internal nodes: 27
32 1: 26 2: 1
33 Pointers: 56
34 Null ptrs: 1
35 Total size: 5 kB
36
37 After applying the patch and repeating:
38
39 Local:
40 Aver depth: 4.72
41 Max depth: 9
42 Leaves: 29
43 Prefixes: 30
44 Internal nodes: 12
45 1: 3 2: 2 3: 7
46 Pointers: 70
47 Null ptrs: 30
48 Total size: 4 kB
49
50 What this fix does is start the rebalance at the newly created tnode
51 instead of at the parent tnode. This way if there is a gap between the
52 parent and the new node it doesn't prevent the new tnode from being
53 coalesced with any pre-existing nodes that may have been pushed into one
54 of the new nodes child branches.
55
56 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
57 Signed-off-by: David S. Miller <davem@davemloft.net>
58 ---
59
60 --- a/net/ipv4/fib_trie.c
61 +++ b/net/ipv4/fib_trie.c
62 @@ -1143,8 +1143,9 @@ static struct list_head *fib_insert_node
63 put_child(tp, cindex, (struct rt_trie_node *)tn);
64 } else {
65 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
66 - tp = tn;
67 }
68 +
69 + tp = tn;
70 }
71
72 if (tp && tp->pos + tp->bits > 32)