target/linux/generic/pending-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)