edf3b0997e0195bee3c098e5a6d005833d249850
[linux-3.10.git] / net / ipv4 / fib_trie.c
1 /*
2  *   This program is free software; you can redistribute it and/or
3  *   modify it under the terms of the GNU General Public License
4  *   as published by the Free Software Foundation; either version
5  *   2 of the License, or (at your option) any later version.
6  *
7  *   Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
8  *     & Swedish University of Agricultural Sciences.
9  *
10  *   Jens Laas <jens.laas@data.slu.se> Swedish University of
11  *     Agricultural Sciences.
12  *
13  *   Hans Liss <hans.liss@its.uu.se>  Uppsala Universitet
14  *
15  * This work is based on the LPC-trie which is originally descibed in:
16  *
17  * An experimental study of compression methods for dynamic tries
18  * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
19  * http://www.csc.kth.se/~snilsson/software/dyntrie2/
20  *
21  *
22  * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
23  * IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999
24  *
25  *
26  * Code from fib_hash has been reused which includes the following header:
27  *
28  *
29  * INET         An implementation of the TCP/IP protocol suite for the LINUX
30  *              operating system.  INET is implemented using the  BSD Socket
31  *              interface as the means of communication with the user level.
32  *
33  *              IPv4 FIB: lookup engine and maintenance routines.
34  *
35  *
36  * Authors:     Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
37  *
38  *              This program is free software; you can redistribute it and/or
39  *              modify it under the terms of the GNU General Public License
40  *              as published by the Free Software Foundation; either version
41  *              2 of the License, or (at your option) any later version.
42  *
43  * Substantial contributions to this work comes from:
44  *
45  *              David S. Miller, <davem@davemloft.net>
46  *              Stephen Hemminger <shemminger@osdl.org>
47  *              Paul E. McKenney <paulmck@us.ibm.com>
48  *              Patrick McHardy <kaber@trash.net>
49  */
50
51 #define VERSION "0.409"
52
53 #include <asm/uaccess.h>
54 #include <asm/system.h>
55 #include <linux/bitops.h>
56 #include <linux/types.h>
57 #include <linux/kernel.h>
58 #include <linux/mm.h>
59 #include <linux/string.h>
60 #include <linux/socket.h>
61 #include <linux/sockios.h>
62 #include <linux/errno.h>
63 #include <linux/in.h>
64 #include <linux/inet.h>
65 #include <linux/inetdevice.h>
66 #include <linux/netdevice.h>
67 #include <linux/if_arp.h>
68 #include <linux/proc_fs.h>
69 #include <linux/rcupdate.h>
70 #include <linux/skbuff.h>
71 #include <linux/netlink.h>
72 #include <linux/init.h>
73 #include <linux/list.h>
74 #include <linux/slab.h>
75 #include <net/net_namespace.h>
76 #include <net/ip.h>
77 #include <net/protocol.h>
78 #include <net/route.h>
79 #include <net/tcp.h>
80 #include <net/sock.h>
81 #include <net/ip_fib.h>
82 #include "fib_lookup.h"
83
84 #define MAX_STAT_DEPTH 32
85
86 #define KEYLENGTH (8*sizeof(t_key))
87
88 typedef unsigned int t_key;
89
90 #define T_TNODE 0
91 #define T_LEAF  1
92 #define NODE_TYPE_MASK  0x1UL
93 #define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
94
95 #define IS_TNODE(n) (!(n->parent & T_LEAF))
96 #define IS_LEAF(n) (n->parent & T_LEAF)
97
98 struct rt_trie_node {
99         unsigned long parent;
100         t_key key;
101 };
102
103 struct leaf {
104         unsigned long parent;
105         t_key key;
106         struct hlist_head list;
107         struct rcu_head rcu;
108 };
109
110 struct leaf_info {
111         struct hlist_node hlist;
112         struct rcu_head rcu;
113         int plen;
114         struct list_head falh;
115 };
116
117 struct tnode {
118         unsigned long parent;
119         t_key key;
120         unsigned char pos;              /* 2log(KEYLENGTH) bits needed */
121         unsigned char bits;             /* 2log(KEYLENGTH) bits needed */
122         unsigned int full_children;     /* KEYLENGTH bits needed */
123         unsigned int empty_children;    /* KEYLENGTH bits needed */
124         union {
125                 struct rcu_head rcu;
126                 struct work_struct work;
127                 struct tnode *tnode_free;
128         };
129         struct rt_trie_node *child[0];
130 };
131
132 #ifdef CONFIG_IP_FIB_TRIE_STATS
133 struct trie_use_stats {
134         unsigned int gets;
135         unsigned int backtrack;
136         unsigned int semantic_match_passed;
137         unsigned int semantic_match_miss;
138         unsigned int null_node_hit;
139         unsigned int resize_node_skipped;
140 };
141 #endif
142
143 struct trie_stat {
144         unsigned int totdepth;
145         unsigned int maxdepth;
146         unsigned int tnodes;
147         unsigned int leaves;
148         unsigned int nullpointers;
149         unsigned int prefixes;
150         unsigned int nodesizes[MAX_STAT_DEPTH];
151 };
152
153 struct trie {
154         struct rt_trie_node *trie;
155 #ifdef CONFIG_IP_FIB_TRIE_STATS
156         struct trie_use_stats stats;
157 #endif
158 };
159
160 static void put_child(struct trie *t, struct tnode *tn, int i, struct rt_trie_node *n);
161 static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
162                                   int wasfull);
163 static struct rt_trie_node *resize(struct trie *t, struct tnode *tn);
164 static struct tnode *inflate(struct trie *t, struct tnode *tn);
165 static struct tnode *halve(struct trie *t, struct tnode *tn);
166 /* tnodes to free after resize(); protected by RTNL */
167 static struct tnode *tnode_free_head;
168 static size_t tnode_free_size;
169
170 /*
171  * synchronize_rcu after call_rcu for that many pages; it should be especially
172  * useful before resizing the root node with PREEMPT_NONE configs; the value was
173  * obtained experimentally, aiming to avoid visible slowdown.
174  */
175 static const int sync_pages = 128;
176
177 static struct kmem_cache *fn_alias_kmem __read_mostly;
178 static struct kmem_cache *trie_leaf_kmem __read_mostly;
179
180 static inline struct tnode *node_parent(struct rt_trie_node *node)
181 {
182         return (struct tnode *)(node->parent & ~NODE_TYPE_MASK);
183 }
184
185 static inline struct tnode *node_parent_rcu(struct rt_trie_node *node)
186 {
187         struct tnode *ret = node_parent(node);
188
189         return rcu_dereference_rtnl(ret);
190 }
191
192 /* Same as rcu_assign_pointer
193  * but that macro() assumes that value is a pointer.
194  */
195 static inline void node_set_parent(struct rt_trie_node *node, struct tnode *ptr)
196 {
197         smp_wmb();
198         node->parent = (unsigned long)ptr | NODE_TYPE(node);
199 }
200
201 static inline struct rt_trie_node *tnode_get_child(struct tnode *tn, unsigned int i)
202 {
203         BUG_ON(i >= 1U << tn->bits);
204
205         return tn->child[i];
206 }
207
208 static inline struct rt_trie_node *tnode_get_child_rcu(struct tnode *tn, unsigned int i)
209 {
210         struct rt_trie_node *ret = tnode_get_child(tn, i);
211
212         return rcu_dereference_rtnl(ret);
213 }
214
215 static inline int tnode_child_length(const struct tnode *tn)
216 {
217         return 1 << tn->bits;
218 }
219
220 static inline t_key mask_pfx(t_key k, unsigned int l)
221 {
222         return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
223 }
224
225 static inline t_key tkey_extract_bits(t_key a, unsigned int offset, unsigned int bits)
226 {
227         if (offset < KEYLENGTH)
228                 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
229         else
230                 return 0;
231 }
232
233 static inline int tkey_equals(t_key a, t_key b)
234 {
235         return a == b;
236 }
237
238 static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
239 {
240         if (bits == 0 || offset >= KEYLENGTH)
241                 return 1;
242         bits = bits > KEYLENGTH ? KEYLENGTH : bits;
243         return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
244 }
245
246 static inline int tkey_mismatch(t_key a, int offset, t_key b)
247 {
248         t_key diff = a ^ b;
249         int i = offset;
250
251         if (!diff)
252                 return 0;
253         while ((diff << i) >> (KEYLENGTH-1) == 0)
254                 i++;
255         return i;
256 }
257
258 /*
259   To understand this stuff, an understanding of keys and all their bits is
260   necessary. Every node in the trie has a key associated with it, but not
261   all of the bits in that key are significant.
262
263   Consider a node 'n' and its parent 'tp'.
264
265   If n is a leaf, every bit in its key is significant. Its presence is
266   necessitated by path compression, since during a tree traversal (when
267   searching for a leaf - unless we are doing an insertion) we will completely
268   ignore all skipped bits we encounter. Thus we need to verify, at the end of
269   a potentially successful search, that we have indeed been walking the
270   correct key path.
271
272   Note that we can never "miss" the correct key in the tree if present by
273   following the wrong path. Path compression ensures that segments of the key
274   that are the same for all keys with a given prefix are skipped, but the
275   skipped part *is* identical for each node in the subtrie below the skipped
276   bit! trie_insert() in this implementation takes care of that - note the
277   call to tkey_sub_equals() in trie_insert().
278
279   if n is an internal node - a 'tnode' here, the various parts of its key
280   have many different meanings.
281
282   Example:
283   _________________________________________________________________
284   | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
285   -----------------------------------------------------------------
286     0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
287
288   _________________________________________________________________
289   | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
290   -----------------------------------------------------------------
291    16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31
292
293   tp->pos = 7
294   tp->bits = 3
295   n->pos = 15
296   n->bits = 4
297
298   First, let's just ignore the bits that come before the parent tp, that is
299   the bits from 0 to (tp->pos-1). They are *known* but at this point we do
300   not use them for anything.
301
302   The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
303   index into the parent's child array. That is, they will be used to find
304   'n' among tp's children.
305
306   The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
307   for the node n.
308
309   All the bits we have seen so far are significant to the node n. The rest
310   of the bits are really not needed or indeed known in n->key.
311
312   The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
313   n's child array, and will of course be different for each child.
314
315
316   The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
317   at this point.
318
319 */
320
321 static inline void check_tnode(const struct tnode *tn)
322 {
323         WARN_ON(tn && tn->pos+tn->bits > 32);
324 }
325
326 static const int halve_threshold = 25;
327 static const int inflate_threshold = 50;
328 static const int halve_threshold_root = 15;
329 static const int inflate_threshold_root = 30;
330
331 static void __alias_free_mem(struct rcu_head *head)
332 {
333         struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
334         kmem_cache_free(fn_alias_kmem, fa);
335 }
336
337 static inline void alias_free_mem_rcu(struct fib_alias *fa)
338 {
339         call_rcu(&fa->rcu, __alias_free_mem);
340 }
341
342 static void __leaf_free_rcu(struct rcu_head *head)
343 {
344         struct leaf *l = container_of(head, struct leaf, rcu);
345         kmem_cache_free(trie_leaf_kmem, l);
346 }
347
348 static inline void free_leaf(struct leaf *l)
349 {
350         call_rcu_bh(&l->rcu, __leaf_free_rcu);
351 }
352
353 static void __leaf_info_free_rcu(struct rcu_head *head)
354 {
355         kfree(container_of(head, struct leaf_info, rcu));
356 }
357
358 static inline void free_leaf_info(struct leaf_info *leaf)
359 {
360         call_rcu(&leaf->rcu, __leaf_info_free_rcu);
361 }
362
363 static struct tnode *tnode_alloc(size_t size)
364 {
365         if (size <= PAGE_SIZE)
366                 return kzalloc(size, GFP_KERNEL);
367         else
368                 return vzalloc(size);
369 }
370
371 static void __tnode_vfree(struct work_struct *arg)
372 {
373         struct tnode *tn = container_of(arg, struct tnode, work);
374         vfree(tn);
375 }
376
377 static void __tnode_free_rcu(struct rcu_head *head)
378 {
379         struct tnode *tn = container_of(head, struct tnode, rcu);
380         size_t size = sizeof(struct tnode) +
381                       (sizeof(struct rt_trie_node *) << tn->bits);
382
383         if (size <= PAGE_SIZE)
384                 kfree(tn);
385         else {
386                 INIT_WORK(&tn->work, __tnode_vfree);
387                 schedule_work(&tn->work);
388         }
389 }
390
391 static inline void tnode_free(struct tnode *tn)
392 {
393         if (IS_LEAF(tn))
394                 free_leaf((struct leaf *) tn);
395         else
396                 call_rcu(&tn->rcu, __tnode_free_rcu);
397 }
398
399 static void tnode_free_safe(struct tnode *tn)
400 {
401         BUG_ON(IS_LEAF(tn));
402         tn->tnode_free = tnode_free_head;
403         tnode_free_head = tn;
404         tnode_free_size += sizeof(struct tnode) +
405                            (sizeof(struct rt_trie_node *) << tn->bits);
406 }
407
408 static void tnode_free_flush(void)
409 {
410         struct tnode *tn;
411
412         while ((tn = tnode_free_head)) {
413                 tnode_free_head = tn->tnode_free;
414                 tn->tnode_free = NULL;
415                 tnode_free(tn);
416         }
417
418         if (tnode_free_size >= PAGE_SIZE * sync_pages) {
419                 tnode_free_size = 0;
420                 synchronize_rcu();
421         }
422 }
423
424 static struct leaf *leaf_new(void)
425 {
426         struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
427         if (l) {
428                 l->parent = T_LEAF;
429                 INIT_HLIST_HEAD(&l->list);
430         }
431         return l;
432 }
433
434 static struct leaf_info *leaf_info_new(int plen)
435 {
436         struct leaf_info *li = kmalloc(sizeof(struct leaf_info),  GFP_KERNEL);
437         if (li) {
438                 li->plen = plen;
439                 INIT_LIST_HEAD(&li->falh);
440         }
441         return li;
442 }
443
444 static struct tnode *tnode_new(t_key key, int pos, int bits)
445 {
446         size_t sz = sizeof(struct tnode) + (sizeof(struct rt_trie_node *) << bits);
447         struct tnode *tn = tnode_alloc(sz);
448
449         if (tn) {
450                 tn->parent = T_TNODE;
451                 tn->pos = pos;
452                 tn->bits = bits;
453                 tn->key = key;
454                 tn->full_children = 0;
455                 tn->empty_children = 1<<bits;
456         }
457
458         pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode),
459                  sizeof(struct rt_trie_node) << bits);
460         return tn;
461 }
462
463 /*
464  * Check whether a tnode 'n' is "full", i.e. it is an internal node
465  * and no bits are skipped. See discussion in dyntree paper p. 6
466  */
467
468 static inline int tnode_full(const struct tnode *tn, const struct rt_trie_node *n)
469 {
470         if (n == NULL || IS_LEAF(n))
471                 return 0;
472
473         return ((struct tnode *) n)->pos == tn->pos + tn->bits;
474 }
475
476 static inline void put_child(struct trie *t, struct tnode *tn, int i,
477                              struct rt_trie_node *n)
478 {
479         tnode_put_child_reorg(tn, i, n, -1);
480 }
481
482  /*
483   * Add a child at position i overwriting the old value.
484   * Update the value of full_children and empty_children.
485   */
486
487 static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
488                                   int wasfull)
489 {
490         struct rt_trie_node *chi = tn->child[i];
491         int isfull;
492
493         BUG_ON(i >= 1<<tn->bits);
494
495         /* update emptyChildren */
496         if (n == NULL && chi != NULL)
497                 tn->empty_children++;
498         else if (n != NULL && chi == NULL)
499                 tn->empty_children--;
500
501         /* update fullChildren */
502         if (wasfull == -1)
503                 wasfull = tnode_full(tn, chi);
504
505         isfull = tnode_full(tn, n);
506         if (wasfull && !isfull)
507                 tn->full_children--;
508         else if (!wasfull && isfull)
509                 tn->full_children++;
510
511         if (n)
512                 node_set_parent(n, tn);
513
514         rcu_assign_pointer(tn->child[i], n);
515 }
516
517 #define MAX_WORK 10
518 static struct rt_trie_node *resize(struct trie *t, struct tnode *tn)
519 {
520         int i;
521         struct tnode *old_tn;
522         int inflate_threshold_use;
523         int halve_threshold_use;
524         int max_work;
525
526         if (!tn)
527                 return NULL;
528
529         pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
530                  tn, inflate_threshold, halve_threshold);
531
532         /* No children */
533         if (tn->empty_children == tnode_child_length(tn)) {
534                 tnode_free_safe(tn);
535                 return NULL;
536         }
537         /* One child */
538         if (tn->empty_children == tnode_child_length(tn) - 1)
539                 goto one_child;
540         /*
541          * Double as long as the resulting node has a number of
542          * nonempty nodes that are above the threshold.
543          */
544
545         /*
546          * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
547          * the Helsinki University of Technology and Matti Tikkanen of Nokia
548          * Telecommunications, page 6:
549          * "A node is doubled if the ratio of non-empty children to all
550          * children in the *doubled* node is at least 'high'."
551          *
552          * 'high' in this instance is the variable 'inflate_threshold'. It
553          * is expressed as a percentage, so we multiply it with
554          * tnode_child_length() and instead of multiplying by 2 (since the
555          * child array will be doubled by inflate()) and multiplying
556          * the left-hand side by 100 (to handle the percentage thing) we
557          * multiply the left-hand side by 50.
558          *
559          * The left-hand side may look a bit weird: tnode_child_length(tn)
560          * - tn->empty_children is of course the number of non-null children
561          * in the current node. tn->full_children is the number of "full"
562          * children, that is non-null tnodes with a skip value of 0.
563          * All of those will be doubled in the resulting inflated tnode, so
564          * we just count them one extra time here.
565          *
566          * A clearer way to write this would be:
567          *
568          * to_be_doubled = tn->full_children;
569          * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
570          *     tn->full_children;
571          *
572          * new_child_length = tnode_child_length(tn) * 2;
573          *
574          * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
575          *      new_child_length;
576          * if (new_fill_factor >= inflate_threshold)
577          *
578          * ...and so on, tho it would mess up the while () loop.
579          *
580          * anyway,
581          * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
582          *      inflate_threshold
583          *
584          * avoid a division:
585          * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
586          *      inflate_threshold * new_child_length
587          *
588          * expand not_to_be_doubled and to_be_doubled, and shorten:
589          * 100 * (tnode_child_length(tn) - tn->empty_children +
590          *    tn->full_children) >= inflate_threshold * new_child_length
591          *
592          * expand new_child_length:
593          * 100 * (tnode_child_length(tn) - tn->empty_children +
594          *    tn->full_children) >=
595          *      inflate_threshold * tnode_child_length(tn) * 2
596          *
597          * shorten again:
598          * 50 * (tn->full_children + tnode_child_length(tn) -
599          *    tn->empty_children) >= inflate_threshold *
600          *    tnode_child_length(tn)
601          *
602          */
603
604         check_tnode(tn);
605
606         /* Keep root node larger  */
607
608         if (!node_parent((struct rt_trie_node *)tn)) {
609                 inflate_threshold_use = inflate_threshold_root;
610                 halve_threshold_use = halve_threshold_root;
611         } else {
612                 inflate_threshold_use = inflate_threshold;
613                 halve_threshold_use = halve_threshold;
614         }
615
616         max_work = MAX_WORK;
617         while ((tn->full_children > 0 &&  max_work-- &&
618                 50 * (tn->full_children + tnode_child_length(tn)
619                       - tn->empty_children)
620                 >= inflate_threshold_use * tnode_child_length(tn))) {
621
622                 old_tn = tn;
623                 tn = inflate(t, tn);
624
625                 if (IS_ERR(tn)) {
626                         tn = old_tn;
627 #ifdef CONFIG_IP_FIB_TRIE_STATS
628                         t->stats.resize_node_skipped++;
629 #endif
630                         break;
631                 }
632         }
633
634         check_tnode(tn);
635
636         /* Return if at least one inflate is run */
637         if (max_work != MAX_WORK)
638                 return (struct rt_trie_node *) tn;
639
640         /*
641          * Halve as long as the number of empty children in this
642          * node is above threshold.
643          */
644
645         max_work = MAX_WORK;
646         while (tn->bits > 1 &&  max_work-- &&
647                100 * (tnode_child_length(tn) - tn->empty_children) <
648                halve_threshold_use * tnode_child_length(tn)) {
649
650                 old_tn = tn;
651                 tn = halve(t, tn);
652                 if (IS_ERR(tn)) {
653                         tn = old_tn;
654 #ifdef CONFIG_IP_FIB_TRIE_STATS
655                         t->stats.resize_node_skipped++;
656 #endif
657                         break;
658                 }
659         }
660
661
662         /* Only one child remains */
663         if (tn->empty_children == tnode_child_length(tn) - 1) {
664 one_child:
665                 for (i = 0; i < tnode_child_length(tn); i++) {
666                         struct rt_trie_node *n;
667
668                         n = tn->child[i];
669                         if (!n)
670                                 continue;
671
672                         /* compress one level */
673
674                         node_set_parent(n, NULL);
675                         tnode_free_safe(tn);
676                         return n;
677                 }
678         }
679         return (struct rt_trie_node *) tn;
680 }
681
682 static struct tnode *inflate(struct trie *t, struct tnode *tn)
683 {
684         struct tnode *oldtnode = tn;
685         int olen = tnode_child_length(tn);
686         int i;
687
688         pr_debug("In inflate\n");
689
690         tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
691
692         if (!tn)
693                 return ERR_PTR(-ENOMEM);
694
695         /*
696          * Preallocate and store tnodes before the actual work so we
697          * don't get into an inconsistent state if memory allocation
698          * fails. In case of failure we return the oldnode and  inflate
699          * of tnode is ignored.
700          */
701
702         for (i = 0; i < olen; i++) {
703                 struct tnode *inode;
704
705                 inode = (struct tnode *) tnode_get_child(oldtnode, i);
706                 if (inode &&
707                     IS_TNODE(inode) &&
708                     inode->pos == oldtnode->pos + oldtnode->bits &&
709                     inode->bits > 1) {
710                         struct tnode *left, *right;
711                         t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
712
713                         left = tnode_new(inode->key&(~m), inode->pos + 1,
714                                          inode->bits - 1);
715                         if (!left)
716                                 goto nomem;
717
718                         right = tnode_new(inode->key|m, inode->pos + 1,
719                                           inode->bits - 1);
720
721                         if (!right) {
722                                 tnode_free(left);
723                                 goto nomem;
724                         }
725
726                         put_child(t, tn, 2*i, (struct rt_trie_node *) left);
727                         put_child(t, tn, 2*i+1, (struct rt_trie_node *) right);
728                 }
729         }
730
731         for (i = 0; i < olen; i++) {
732                 struct tnode *inode;
733                 struct rt_trie_node *node = tnode_get_child(oldtnode, i);
734                 struct tnode *left, *right;
735                 int size, j;
736
737                 /* An empty child */
738                 if (node == NULL)
739                         continue;
740
741                 /* A leaf or an internal node with skipped bits */
742
743                 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
744                    tn->pos + tn->bits - 1) {
745                         if (tkey_extract_bits(node->key,
746                                               oldtnode->pos + oldtnode->bits,
747                                               1) == 0)
748                                 put_child(t, tn, 2*i, node);
749                         else
750                                 put_child(t, tn, 2*i+1, node);
751                         continue;
752                 }
753
754                 /* An internal node with two children */
755                 inode = (struct tnode *) node;
756
757                 if (inode->bits == 1) {
758                         put_child(t, tn, 2*i, inode->child[0]);
759                         put_child(t, tn, 2*i+1, inode->child[1]);
760
761                         tnode_free_safe(inode);
762                         continue;
763                 }
764
765                 /* An internal node with more than two children */
766
767                 /* We will replace this node 'inode' with two new
768                  * ones, 'left' and 'right', each with half of the
769                  * original children. The two new nodes will have
770                  * a position one bit further down the key and this
771                  * means that the "significant" part of their keys
772                  * (see the discussion near the top of this file)
773                  * will differ by one bit, which will be "0" in
774                  * left's key and "1" in right's key. Since we are
775                  * moving the key position by one step, the bit that
776                  * we are moving away from - the bit at position
777                  * (inode->pos) - is the one that will differ between
778                  * left and right. So... we synthesize that bit in the
779                  * two  new keys.
780                  * The mask 'm' below will be a single "one" bit at
781                  * the position (inode->pos)
782                  */
783
784                 /* Use the old key, but set the new significant
785                  *   bit to zero.
786                  */
787
788                 left = (struct tnode *) tnode_get_child(tn, 2*i);
789                 put_child(t, tn, 2*i, NULL);
790
791                 BUG_ON(!left);
792
793                 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
794                 put_child(t, tn, 2*i+1, NULL);
795
796                 BUG_ON(!right);
797
798                 size = tnode_child_length(left);
799                 for (j = 0; j < size; j++) {
800                         put_child(t, left, j, inode->child[j]);
801                         put_child(t, right, j, inode->child[j + size]);
802                 }
803                 put_child(t, tn, 2*i, resize(t, left));
804                 put_child(t, tn, 2*i+1, resize(t, right));
805
806                 tnode_free_safe(inode);
807         }
808         tnode_free_safe(oldtnode);
809         return tn;
810 nomem:
811         {
812                 int size = tnode_child_length(tn);
813                 int j;
814
815                 for (j = 0; j < size; j++)
816                         if (tn->child[j])
817                                 tnode_free((struct tnode *)tn->child[j]);
818
819                 tnode_free(tn);
820
821                 return ERR_PTR(-ENOMEM);
822         }
823 }
824
825 static struct tnode *halve(struct trie *t, struct tnode *tn)
826 {
827         struct tnode *oldtnode = tn;
828         struct rt_trie_node *left, *right;
829         int i;
830         int olen = tnode_child_length(tn);
831
832         pr_debug("In halve\n");
833
834         tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
835
836         if (!tn)
837                 return ERR_PTR(-ENOMEM);
838
839         /*
840          * Preallocate and store tnodes before the actual work so we
841          * don't get into an inconsistent state if memory allocation
842          * fails. In case of failure we return the oldnode and halve
843          * of tnode is ignored.
844          */
845
846         for (i = 0; i < olen; i += 2) {
847                 left = tnode_get_child(oldtnode, i);
848                 right = tnode_get_child(oldtnode, i+1);
849
850                 /* Two nonempty children */
851                 if (left && right) {
852                         struct tnode *newn;
853
854                         newn = tnode_new(left->key, tn->pos + tn->bits, 1);
855
856                         if (!newn)
857                                 goto nomem;
858
859                         put_child(t, tn, i/2, (struct rt_trie_node *)newn);
860                 }
861
862         }
863
864         for (i = 0; i < olen; i += 2) {
865                 struct tnode *newBinNode;
866
867                 left = tnode_get_child(oldtnode, i);
868                 right = tnode_get_child(oldtnode, i+1);
869
870                 /* At least one of the children is empty */
871                 if (left == NULL) {
872                         if (right == NULL)    /* Both are empty */
873                                 continue;
874                         put_child(t, tn, i/2, right);
875                         continue;
876                 }
877
878                 if (right == NULL) {
879                         put_child(t, tn, i/2, left);
880                         continue;
881                 }
882
883                 /* Two nonempty children */
884                 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
885                 put_child(t, tn, i/2, NULL);
886                 put_child(t, newBinNode, 0, left);
887                 put_child(t, newBinNode, 1, right);
888                 put_child(t, tn, i/2, resize(t, newBinNode));
889         }
890         tnode_free_safe(oldtnode);
891         return tn;
892 nomem:
893         {
894                 int size = tnode_child_length(tn);
895                 int j;
896
897                 for (j = 0; j < size; j++)
898                         if (tn->child[j])
899                                 tnode_free((struct tnode *)tn->child[j]);
900
901                 tnode_free(tn);
902
903                 return ERR_PTR(-ENOMEM);
904         }
905 }
906
907 /* readside must use rcu_read_lock currently dump routines
908  via get_fa_head and dump */
909
910 static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
911 {
912         struct hlist_head *head = &l->list;
913         struct hlist_node *node;
914         struct leaf_info *li;
915
916         hlist_for_each_entry_rcu(li, node, head, hlist)
917                 if (li->plen == plen)
918                         return li;
919
920         return NULL;
921 }
922
923 static inline struct list_head *get_fa_head(struct leaf *l, int plen)
924 {
925         struct leaf_info *li = find_leaf_info(l, plen);
926
927         if (!li)
928                 return NULL;
929
930         return &li->falh;
931 }
932
933 static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
934 {
935         struct leaf_info *li = NULL, *last = NULL;
936         struct hlist_node *node;
937
938         if (hlist_empty(head)) {
939                 hlist_add_head_rcu(&new->hlist, head);
940         } else {
941                 hlist_for_each_entry(li, node, head, hlist) {
942                         if (new->plen > li->plen)
943                                 break;
944
945                         last = li;
946                 }
947                 if (last)
948                         hlist_add_after_rcu(&last->hlist, &new->hlist);
949                 else
950                         hlist_add_before_rcu(&new->hlist, &li->hlist);
951         }
952 }
953
954 /* rcu_read_lock needs to be hold by caller from readside */
955
956 static struct leaf *
957 fib_find_node(struct trie *t, u32 key)
958 {
959         int pos;
960         struct tnode *tn;
961         struct rt_trie_node *n;
962
963         pos = 0;
964         n = rcu_dereference_rtnl(t->trie);
965
966         while (n != NULL &&  NODE_TYPE(n) == T_TNODE) {
967                 tn = (struct tnode *) n;
968
969                 check_tnode(tn);
970
971                 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
972                         pos = tn->pos + tn->bits;
973                         n = tnode_get_child_rcu(tn,
974                                                 tkey_extract_bits(key,
975                                                                   tn->pos,
976                                                                   tn->bits));
977                 } else
978                         break;
979         }
980         /* Case we have found a leaf. Compare prefixes */
981
982         if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
983                 return (struct leaf *)n;
984
985         return NULL;
986 }
987
988 static void trie_rebalance(struct trie *t, struct tnode *tn)
989 {
990         int wasfull;
991         t_key cindex, key;
992         struct tnode *tp;
993
994         key = tn->key;
995
996         while (tn != NULL && (tp = node_parent((struct rt_trie_node *)tn)) != NULL) {
997                 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
998                 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
999                 tn = (struct tnode *) resize(t, (struct tnode *)tn);
1000
1001                 tnode_put_child_reorg((struct tnode *)tp, cindex,
1002                                       (struct rt_trie_node *)tn, wasfull);
1003
1004                 tp = node_parent((struct rt_trie_node *) tn);
1005                 if (!tp)
1006                         rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1007
1008                 tnode_free_flush();
1009                 if (!tp)
1010                         break;
1011                 tn = tp;
1012         }
1013
1014         /* Handle last (top) tnode */
1015         if (IS_TNODE(tn))
1016                 tn = (struct tnode *)resize(t, (struct tnode *)tn);
1017
1018         rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1019         tnode_free_flush();
1020 }
1021
1022 /* only used from updater-side */
1023
1024 static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
1025 {
1026         int pos, newpos;
1027         struct tnode *tp = NULL, *tn = NULL;
1028         struct rt_trie_node *n;
1029         struct leaf *l;
1030         int missbit;
1031         struct list_head *fa_head = NULL;
1032         struct leaf_info *li;
1033         t_key cindex;
1034
1035         pos = 0;
1036         n = t->trie;
1037
1038         /* If we point to NULL, stop. Either the tree is empty and we should
1039          * just put a new leaf in if, or we have reached an empty child slot,
1040          * and we should just put our new leaf in that.
1041          * If we point to a T_TNODE, check if it matches our key. Note that
1042          * a T_TNODE might be skipping any number of bits - its 'pos' need
1043          * not be the parent's 'pos'+'bits'!
1044          *
1045          * If it does match the current key, get pos/bits from it, extract
1046          * the index from our key, push the T_TNODE and walk the tree.
1047          *
1048          * If it doesn't, we have to replace it with a new T_TNODE.
1049          *
1050          * If we point to a T_LEAF, it might or might not have the same key
1051          * as we do. If it does, just change the value, update the T_LEAF's
1052          * value, and return it.
1053          * If it doesn't, we need to replace it with a T_TNODE.
1054          */
1055
1056         while (n != NULL &&  NODE_TYPE(n) == T_TNODE) {
1057                 tn = (struct tnode *) n;
1058
1059                 check_tnode(tn);
1060
1061                 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1062                         tp = tn;
1063                         pos = tn->pos + tn->bits;
1064                         n = tnode_get_child(tn,
1065                                             tkey_extract_bits(key,
1066                                                               tn->pos,
1067                                                               tn->bits));
1068
1069                         BUG_ON(n && node_parent(n) != tn);
1070                 } else
1071                         break;
1072         }
1073
1074         /*
1075          * n  ----> NULL, LEAF or TNODE
1076          *
1077          * tp is n's (parent) ----> NULL or TNODE
1078          */
1079
1080         BUG_ON(tp && IS_LEAF(tp));
1081
1082         /* Case 1: n is a leaf. Compare prefixes */
1083
1084         if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1085                 l = (struct leaf *) n;
1086                 li = leaf_info_new(plen);
1087
1088                 if (!li)
1089                         return NULL;
1090
1091                 fa_head = &li->falh;
1092                 insert_leaf_info(&l->list, li);
1093                 goto done;
1094         }
1095         l = leaf_new();
1096
1097         if (!l)
1098                 return NULL;
1099
1100         l->key = key;
1101         li = leaf_info_new(plen);
1102
1103         if (!li) {
1104                 free_leaf(l);
1105                 return NULL;
1106         }
1107
1108         fa_head = &li->falh;
1109         insert_leaf_info(&l->list, li);
1110
1111         if (t->trie && n == NULL) {
1112                 /* Case 2: n is NULL, and will just insert a new leaf */
1113
1114                 node_set_parent((struct rt_trie_node *)l, tp);
1115
1116                 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1117                 put_child(t, (struct tnode *)tp, cindex, (struct rt_trie_node *)l);
1118         } else {
1119                 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1120                 /*
1121                  *  Add a new tnode here
1122                  *  first tnode need some special handling
1123                  */
1124
1125                 if (tp)
1126                         pos = tp->pos+tp->bits;
1127                 else
1128                         pos = 0;
1129
1130                 if (n) {
1131                         newpos = tkey_mismatch(key, pos, n->key);
1132                         tn = tnode_new(n->key, newpos, 1);
1133                 } else {
1134                         newpos = 0;
1135                         tn = tnode_new(key, newpos, 1); /* First tnode */
1136                 }
1137
1138                 if (!tn) {
1139                         free_leaf_info(li);
1140                         free_leaf(l);
1141                         return NULL;
1142                 }
1143
1144                 node_set_parent((struct rt_trie_node *)tn, tp);
1145
1146                 missbit = tkey_extract_bits(key, newpos, 1);
1147                 put_child(t, tn, missbit, (struct rt_trie_node *)l);
1148                 put_child(t, tn, 1-missbit, n);
1149
1150                 if (tp) {
1151                         cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1152                         put_child(t, (struct tnode *)tp, cindex,
1153                                   (struct rt_trie_node *)tn);
1154                 } else {
1155                         rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1156                         tp = tn;
1157                 }
1158         }
1159
1160         if (tp && tp->pos + tp->bits > 32)
1161                 pr_warning("fib_trie"
1162                            " tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1163                            tp, tp->pos, tp->bits, key, plen);
1164
1165         /* Rebalance the trie */
1166
1167         trie_rebalance(t, tp);
1168 done:
1169         return fa_head;
1170 }
1171
1172 /*
1173  * Caller must hold RTNL.
1174  */
1175 int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
1176 {
1177         struct trie *t = (struct trie *) tb->tb_data;
1178         struct fib_alias *fa, *new_fa;
1179         struct list_head *fa_head = NULL;
1180         struct fib_info *fi;
1181         int plen = cfg->fc_dst_len;
1182         u8 tos = cfg->fc_tos;
1183         u32 key, mask;
1184         int err;
1185         struct leaf *l;
1186
1187         if (plen > 32)
1188                 return -EINVAL;
1189
1190         key = ntohl(cfg->fc_dst);
1191
1192         pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1193
1194         mask = ntohl(inet_make_mask(plen));
1195
1196         if (key & ~mask)
1197                 return -EINVAL;
1198
1199         key = key & mask;
1200
1201         fi = fib_create_info(cfg);
1202         if (IS_ERR(fi)) {
1203                 err = PTR_ERR(fi);
1204                 goto err;
1205         }
1206
1207         l = fib_find_node(t, key);
1208         fa = NULL;
1209
1210         if (l) {
1211                 fa_head = get_fa_head(l, plen);
1212                 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1213         }
1214
1215         /* Now fa, if non-NULL, points to the first fib alias
1216          * with the same keys [prefix,tos,priority], if such key already
1217          * exists or to the node before which we will insert new one.
1218          *
1219          * If fa is NULL, we will need to allocate a new one and
1220          * insert to the head of f.
1221          *
1222          * If f is NULL, no fib node matched the destination key
1223          * and we need to allocate a new one of those as well.
1224          */
1225
1226         if (fa && fa->fa_tos == tos &&
1227             fa->fa_info->fib_priority == fi->fib_priority) {
1228                 struct fib_alias *fa_first, *fa_match;
1229
1230                 err = -EEXIST;
1231                 if (cfg->fc_nlflags & NLM_F_EXCL)
1232                         goto out;
1233
1234                 /* We have 2 goals:
1235                  * 1. Find exact match for type, scope, fib_info to avoid
1236                  * duplicate routes
1237                  * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1238                  */
1239                 fa_match = NULL;
1240                 fa_first = fa;
1241                 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1242                 list_for_each_entry_continue(fa, fa_head, fa_list) {
1243                         if (fa->fa_tos != tos)
1244                                 break;
1245                         if (fa->fa_info->fib_priority != fi->fib_priority)
1246                                 break;
1247                         if (fa->fa_type == cfg->fc_type &&
1248                             fa->fa_scope == cfg->fc_scope &&
1249                             fa->fa_info == fi) {
1250                                 fa_match = fa;
1251                                 break;
1252                         }
1253                 }
1254
1255                 if (cfg->fc_nlflags & NLM_F_REPLACE) {
1256                         struct fib_info *fi_drop;
1257                         u8 state;
1258
1259                         fa = fa_first;
1260                         if (fa_match) {
1261                                 if (fa == fa_match)
1262                                         err = 0;
1263                                 goto out;
1264                         }
1265                         err = -ENOBUFS;
1266                         new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1267                         if (new_fa == NULL)
1268                                 goto out;
1269
1270                         fi_drop = fa->fa_info;
1271                         new_fa->fa_tos = fa->fa_tos;
1272                         new_fa->fa_info = fi;
1273                         new_fa->fa_type = cfg->fc_type;
1274                         new_fa->fa_scope = cfg->fc_scope;
1275                         state = fa->fa_state;
1276                         new_fa->fa_state = state & ~FA_S_ACCESSED;
1277
1278                         list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1279                         alias_free_mem_rcu(fa);
1280
1281                         fib_release_info(fi_drop);
1282                         if (state & FA_S_ACCESSED)
1283                                 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1284                         rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1285                                 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1286
1287                         goto succeeded;
1288                 }
1289                 /* Error if we find a perfect match which
1290                  * uses the same scope, type, and nexthop
1291                  * information.
1292                  */
1293                 if (fa_match)
1294                         goto out;
1295
1296                 if (!(cfg->fc_nlflags & NLM_F_APPEND))
1297                         fa = fa_first;
1298         }
1299         err = -ENOENT;
1300         if (!(cfg->fc_nlflags & NLM_F_CREATE))
1301                 goto out;
1302
1303         err = -ENOBUFS;
1304         new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1305         if (new_fa == NULL)
1306                 goto out;
1307
1308         new_fa->fa_info = fi;
1309         new_fa->fa_tos = tos;
1310         new_fa->fa_type = cfg->fc_type;
1311         new_fa->fa_scope = cfg->fc_scope;
1312         new_fa->fa_state = 0;
1313         /*
1314          * Insert new entry to the list.
1315          */
1316
1317         if (!fa_head) {
1318                 fa_head = fib_insert_node(t, key, plen);
1319                 if (unlikely(!fa_head)) {
1320                         err = -ENOMEM;
1321                         goto out_free_new_fa;
1322                 }
1323         }
1324
1325         list_add_tail_rcu(&new_fa->fa_list,
1326                           (fa ? &fa->fa_list : fa_head));
1327
1328         rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1329         rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1330                   &cfg->fc_nlinfo, 0);
1331 succeeded:
1332         return 0;
1333
1334 out_free_new_fa:
1335         kmem_cache_free(fn_alias_kmem, new_fa);
1336 out:
1337         fib_release_info(fi);
1338 err:
1339         return err;
1340 }
1341
1342 /* should be called with rcu_read_lock */
1343 static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
1344                       t_key key,  const struct flowi *flp,
1345                       struct fib_result *res, int fib_flags)
1346 {
1347         struct leaf_info *li;
1348         struct hlist_head *hhead = &l->list;
1349         struct hlist_node *node;
1350
1351         hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1352                 int err;
1353                 int plen = li->plen;
1354                 __be32 mask = inet_make_mask(plen);
1355
1356                 if (l->key != (key & ntohl(mask)))
1357                         continue;
1358
1359                 err = fib_semantic_match(tb, &li->falh, flp, res, plen, fib_flags);
1360
1361 #ifdef CONFIG_IP_FIB_TRIE_STATS
1362                 if (err <= 0)
1363                         t->stats.semantic_match_passed++;
1364                 else
1365                         t->stats.semantic_match_miss++;
1366 #endif
1367                 if (err <= 0)
1368                         return err;
1369         }
1370
1371         return 1;
1372 }
1373
1374 int fib_table_lookup(struct fib_table *tb, const struct flowi *flp,
1375                      struct fib_result *res, int fib_flags)
1376 {
1377         struct trie *t = (struct trie *) tb->tb_data;
1378         int ret;
1379         struct rt_trie_node *n;
1380         struct tnode *pn;
1381         unsigned int pos, bits;
1382         t_key key = ntohl(flp->fl4_dst);
1383         unsigned int chopped_off;
1384         t_key cindex = 0;
1385         unsigned int current_prefix_length = KEYLENGTH;
1386         struct tnode *cn;
1387         t_key pref_mismatch;
1388
1389         rcu_read_lock();
1390
1391         n = rcu_dereference(t->trie);
1392         if (!n)
1393                 goto failed;
1394
1395 #ifdef CONFIG_IP_FIB_TRIE_STATS
1396         t->stats.gets++;
1397 #endif
1398
1399         /* Just a leaf? */
1400         if (IS_LEAF(n)) {
1401                 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1402                 goto found;
1403         }
1404
1405         pn = (struct tnode *) n;
1406         chopped_off = 0;
1407
1408         while (pn) {
1409                 pos = pn->pos;
1410                 bits = pn->bits;
1411
1412                 if (!chopped_off)
1413                         cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1414                                                    pos, bits);
1415
1416                 n = tnode_get_child_rcu(pn, cindex);
1417
1418                 if (n == NULL) {
1419 #ifdef CONFIG_IP_FIB_TRIE_STATS
1420                         t->stats.null_node_hit++;
1421 #endif
1422                         goto backtrace;
1423                 }
1424
1425                 if (IS_LEAF(n)) {
1426                         ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1427                         if (ret > 0)
1428                                 goto backtrace;
1429                         goto found;
1430                 }
1431
1432                 cn = (struct tnode *)n;
1433
1434                 /*
1435                  * It's a tnode, and we can do some extra checks here if we
1436                  * like, to avoid descending into a dead-end branch.
1437                  * This tnode is in the parent's child array at index
1438                  * key[p_pos..p_pos+p_bits] but potentially with some bits
1439                  * chopped off, so in reality the index may be just a
1440                  * subprefix, padded with zero at the end.
1441                  * We can also take a look at any skipped bits in this
1442                  * tnode - everything up to p_pos is supposed to be ok,
1443                  * and the non-chopped bits of the index (se previous
1444                  * paragraph) are also guaranteed ok, but the rest is
1445                  * considered unknown.
1446                  *
1447                  * The skipped bits are key[pos+bits..cn->pos].
1448                  */
1449
1450                 /* If current_prefix_length < pos+bits, we are already doing
1451                  * actual prefix  matching, which means everything from
1452                  * pos+(bits-chopped_off) onward must be zero along some
1453                  * branch of this subtree - otherwise there is *no* valid
1454                  * prefix present. Here we can only check the skipped
1455                  * bits. Remember, since we have already indexed into the
1456                  * parent's child array, we know that the bits we chopped of
1457                  * *are* zero.
1458                  */
1459
1460                 /* NOTA BENE: Checking only skipped bits
1461                    for the new node here */
1462
1463                 if (current_prefix_length < pos+bits) {
1464                         if (tkey_extract_bits(cn->key, current_prefix_length,
1465                                                 cn->pos - current_prefix_length)
1466                             || !(cn->child[0]))
1467                                 goto backtrace;
1468                 }
1469
1470                 /*
1471                  * If chopped_off=0, the index is fully validated and we
1472                  * only need to look at the skipped bits for this, the new,
1473                  * tnode. What we actually want to do is to find out if
1474                  * these skipped bits match our key perfectly, or if we will
1475                  * have to count on finding a matching prefix further down,
1476                  * because if we do, we would like to have some way of
1477                  * verifying the existence of such a prefix at this point.
1478                  */
1479
1480                 /* The only thing we can do at this point is to verify that
1481                  * any such matching prefix can indeed be a prefix to our
1482                  * key, and if the bits in the node we are inspecting that
1483                  * do not match our key are not ZERO, this cannot be true.
1484                  * Thus, find out where there is a mismatch (before cn->pos)
1485                  * and verify that all the mismatching bits are zero in the
1486                  * new tnode's key.
1487                  */
1488
1489                 /*
1490                  * Note: We aren't very concerned about the piece of
1491                  * the key that precede pn->pos+pn->bits, since these
1492                  * have already been checked. The bits after cn->pos
1493                  * aren't checked since these are by definition
1494                  * "unknown" at this point. Thus, what we want to see
1495                  * is if we are about to enter the "prefix matching"
1496                  * state, and in that case verify that the skipped
1497                  * bits that will prevail throughout this subtree are
1498                  * zero, as they have to be if we are to find a
1499                  * matching prefix.
1500                  */
1501
1502                 pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
1503
1504                 /*
1505                  * In short: If skipped bits in this node do not match
1506                  * the search key, enter the "prefix matching"
1507                  * state.directly.
1508                  */
1509                 if (pref_mismatch) {
1510                         int mp = KEYLENGTH - fls(pref_mismatch);
1511
1512                         if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
1513                                 goto backtrace;
1514
1515                         if (current_prefix_length >= cn->pos)
1516                                 current_prefix_length = mp;
1517                 }
1518
1519                 pn = (struct tnode *)n; /* Descend */
1520                 chopped_off = 0;
1521                 continue;
1522
1523 backtrace:
1524                 chopped_off++;
1525
1526                 /* As zero don't change the child key (cindex) */
1527                 while ((chopped_off <= pn->bits)
1528                        && !(cindex & (1<<(chopped_off-1))))
1529                         chopped_off++;
1530
1531                 /* Decrease current_... with bits chopped off */
1532                 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1533                         current_prefix_length = pn->pos + pn->bits
1534                                 - chopped_off;
1535
1536                 /*
1537                  * Either we do the actual chop off according or if we have
1538                  * chopped off all bits in this tnode walk up to our parent.
1539                  */
1540
1541                 if (chopped_off <= pn->bits) {
1542                         cindex &= ~(1 << (chopped_off-1));
1543                 } else {
1544                         struct tnode *parent = node_parent_rcu((struct rt_trie_node *) pn);
1545                         if (!parent)
1546                                 goto failed;
1547
1548                         /* Get Child's index */
1549                         cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1550                         pn = parent;
1551                         chopped_off = 0;
1552
1553 #ifdef CONFIG_IP_FIB_TRIE_STATS
1554                         t->stats.backtrack++;
1555 #endif
1556                         goto backtrace;
1557                 }
1558         }
1559 failed:
1560         ret = 1;
1561 found:
1562         rcu_read_unlock();
1563         return ret;
1564 }
1565
1566 /*
1567  * Remove the leaf and return parent.
1568  */
1569 static void trie_leaf_remove(struct trie *t, struct leaf *l)
1570 {
1571         struct tnode *tp = node_parent((struct rt_trie_node *) l);
1572
1573         pr_debug("entering trie_leaf_remove(%p)\n", l);
1574
1575         if (tp) {
1576                 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1577                 put_child(t, (struct tnode *)tp, cindex, NULL);
1578                 trie_rebalance(t, tp);
1579         } else
1580                 rcu_assign_pointer(t->trie, NULL);
1581
1582         free_leaf(l);
1583 }
1584
1585 /*
1586  * Caller must hold RTNL.
1587  */
1588 int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
1589 {
1590         struct trie *t = (struct trie *) tb->tb_data;
1591         u32 key, mask;
1592         int plen = cfg->fc_dst_len;
1593         u8 tos = cfg->fc_tos;
1594         struct fib_alias *fa, *fa_to_delete;
1595         struct list_head *fa_head;
1596         struct leaf *l;
1597         struct leaf_info *li;
1598
1599         if (plen > 32)
1600                 return -EINVAL;
1601
1602         key = ntohl(cfg->fc_dst);
1603         mask = ntohl(inet_make_mask(plen));
1604
1605         if (key & ~mask)
1606                 return -EINVAL;
1607
1608         key = key & mask;
1609         l = fib_find_node(t, key);
1610
1611         if (!l)
1612                 return -ESRCH;
1613
1614         fa_head = get_fa_head(l, plen);
1615         fa = fib_find_alias(fa_head, tos, 0);
1616
1617         if (!fa)
1618                 return -ESRCH;
1619
1620         pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1621
1622         fa_to_delete = NULL;
1623         fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1624         list_for_each_entry_continue(fa, fa_head, fa_list) {
1625                 struct fib_info *fi = fa->fa_info;
1626
1627                 if (fa->fa_tos != tos)
1628                         break;
1629
1630                 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1631                     (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1632                      fa->fa_scope == cfg->fc_scope) &&
1633                     (!cfg->fc_protocol ||
1634                      fi->fib_protocol == cfg->fc_protocol) &&
1635                     fib_nh_match(cfg, fi) == 0) {
1636                         fa_to_delete = fa;
1637                         break;
1638                 }
1639         }
1640
1641         if (!fa_to_delete)
1642                 return -ESRCH;
1643
1644         fa = fa_to_delete;
1645         rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1646                   &cfg->fc_nlinfo, 0);
1647
1648         l = fib_find_node(t, key);
1649         li = find_leaf_info(l, plen);
1650
1651         list_del_rcu(&fa->fa_list);
1652
1653         if (list_empty(fa_head)) {
1654                 hlist_del_rcu(&li->hlist);
1655                 free_leaf_info(li);
1656         }
1657
1658         if (hlist_empty(&l->list))
1659                 trie_leaf_remove(t, l);
1660
1661         if (fa->fa_state & FA_S_ACCESSED)
1662                 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1663
1664         fib_release_info(fa->fa_info);
1665         alias_free_mem_rcu(fa);
1666         return 0;
1667 }
1668
1669 static int trie_flush_list(struct list_head *head)
1670 {
1671         struct fib_alias *fa, *fa_node;
1672         int found = 0;
1673
1674         list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1675                 struct fib_info *fi = fa->fa_info;
1676
1677                 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1678                         list_del_rcu(&fa->fa_list);
1679                         fib_release_info(fa->fa_info);
1680                         alias_free_mem_rcu(fa);
1681                         found++;
1682                 }
1683         }
1684         return found;
1685 }
1686
1687 static int trie_flush_leaf(struct leaf *l)
1688 {
1689         int found = 0;
1690         struct hlist_head *lih = &l->list;
1691         struct hlist_node *node, *tmp;
1692         struct leaf_info *li = NULL;
1693
1694         hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
1695                 found += trie_flush_list(&li->falh);
1696
1697                 if (list_empty(&li->falh)) {
1698                         hlist_del_rcu(&li->hlist);
1699                         free_leaf_info(li);
1700                 }
1701         }
1702         return found;
1703 }
1704
1705 /*
1706  * Scan for the next right leaf starting at node p->child[idx]
1707  * Since we have back pointer, no recursion necessary.
1708  */
1709 static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1710 {
1711         do {
1712                 t_key idx;
1713
1714                 if (c)
1715                         idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1716                 else
1717                         idx = 0;
1718
1719                 while (idx < 1u << p->bits) {
1720                         c = tnode_get_child_rcu(p, idx++);
1721                         if (!c)
1722                                 continue;
1723
1724                         if (IS_LEAF(c)) {
1725                                 prefetch(p->child[idx]);
1726                                 return (struct leaf *) c;
1727                         }
1728
1729                         /* Rescan start scanning in new node */
1730                         p = (struct tnode *) c;
1731                         idx = 0;
1732                 }
1733
1734                 /* Node empty, walk back up to parent */
1735                 c = (struct rt_trie_node *) p;
1736         } while ((p = node_parent_rcu(c)) != NULL);
1737
1738         return NULL; /* Root of trie */
1739 }
1740
1741 static struct leaf *trie_firstleaf(struct trie *t)
1742 {
1743         struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
1744
1745         if (!n)
1746                 return NULL;
1747
1748         if (IS_LEAF(n))          /* trie is just a leaf */
1749                 return (struct leaf *) n;
1750
1751         return leaf_walk_rcu(n, NULL);
1752 }
1753
1754 static struct leaf *trie_nextleaf(struct leaf *l)
1755 {
1756         struct rt_trie_node *c = (struct rt_trie_node *) l;
1757         struct tnode *p = node_parent_rcu(c);
1758
1759         if (!p)
1760                 return NULL;    /* trie with just one leaf */
1761
1762         return leaf_walk_rcu(p, c);
1763 }
1764
1765 static struct leaf *trie_leafindex(struct trie *t, int index)
1766 {
1767         struct leaf *l = trie_firstleaf(t);
1768
1769         while (l && index-- > 0)
1770                 l = trie_nextleaf(l);
1771
1772         return l;
1773 }
1774
1775
1776 /*
1777  * Caller must hold RTNL.
1778  */
1779 int fib_table_flush(struct fib_table *tb)
1780 {
1781         struct trie *t = (struct trie *) tb->tb_data;
1782         struct leaf *l, *ll = NULL;
1783         int found = 0;
1784
1785         for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1786                 found += trie_flush_leaf(l);
1787
1788                 if (ll && hlist_empty(&ll->list))
1789                         trie_leaf_remove(t, ll);
1790                 ll = l;
1791         }
1792
1793         if (ll && hlist_empty(&ll->list))
1794                 trie_leaf_remove(t, ll);
1795
1796         pr_debug("trie_flush found=%d\n", found);
1797         return found;
1798 }
1799
1800 void fib_free_table(struct fib_table *tb)
1801 {
1802         kfree(tb);
1803 }
1804
1805 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1806                            struct fib_table *tb,
1807                            struct sk_buff *skb, struct netlink_callback *cb)
1808 {
1809         int i, s_i;
1810         struct fib_alias *fa;
1811         __be32 xkey = htonl(key);
1812
1813         s_i = cb->args[5];
1814         i = 0;
1815
1816         /* rcu_read_lock is hold by caller */
1817
1818         list_for_each_entry_rcu(fa, fah, fa_list) {
1819                 if (i < s_i) {
1820                         i++;
1821                         continue;
1822                 }
1823
1824                 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1825                                   cb->nlh->nlmsg_seq,
1826                                   RTM_NEWROUTE,
1827                                   tb->tb_id,
1828                                   fa->fa_type,
1829                                   fa->fa_scope,
1830                                   xkey,
1831                                   plen,
1832                                   fa->fa_tos,
1833                                   fa->fa_info, NLM_F_MULTI) < 0) {
1834                         cb->args[5] = i;
1835                         return -1;
1836                 }
1837                 i++;
1838         }
1839         cb->args[5] = i;
1840         return skb->len;
1841 }
1842
1843 static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1844                         struct sk_buff *skb, struct netlink_callback *cb)
1845 {
1846         struct leaf_info *li;
1847         struct hlist_node *node;
1848         int i, s_i;
1849
1850         s_i = cb->args[4];
1851         i = 0;
1852
1853         /* rcu_read_lock is hold by caller */
1854         hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
1855                 if (i < s_i) {
1856                         i++;
1857                         continue;
1858                 }
1859
1860                 if (i > s_i)
1861                         cb->args[5] = 0;
1862
1863                 if (list_empty(&li->falh))
1864                         continue;
1865
1866                 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1867                         cb->args[4] = i;
1868                         return -1;
1869                 }
1870                 i++;
1871         }
1872
1873         cb->args[4] = i;
1874         return skb->len;
1875 }
1876
1877 int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
1878                    struct netlink_callback *cb)
1879 {
1880         struct leaf *l;
1881         struct trie *t = (struct trie *) tb->tb_data;
1882         t_key key = cb->args[2];
1883         int count = cb->args[3];
1884
1885         rcu_read_lock();
1886         /* Dump starting at last key.
1887          * Note: 0.0.0.0/0 (ie default) is first key.
1888          */
1889         if (count == 0)
1890                 l = trie_firstleaf(t);
1891         else {
1892                 /* Normally, continue from last key, but if that is missing
1893                  * fallback to using slow rescan
1894                  */
1895                 l = fib_find_node(t, key);
1896                 if (!l)
1897                         l = trie_leafindex(t, count);
1898         }
1899
1900         while (l) {
1901                 cb->args[2] = l->key;
1902                 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1903                         cb->args[3] = count;
1904                         rcu_read_unlock();
1905                         return -1;
1906                 }
1907
1908                 ++count;
1909                 l = trie_nextleaf(l);
1910                 memset(&cb->args[4], 0,
1911                        sizeof(cb->args) - 4*sizeof(cb->args[0]));
1912         }
1913         cb->args[3] = count;
1914         rcu_read_unlock();
1915
1916         return skb->len;
1917 }
1918
1919 void __init fib_trie_init(void)
1920 {
1921         fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1922                                           sizeof(struct fib_alias),
1923                                           0, SLAB_PANIC, NULL);
1924
1925         trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1926                                            max(sizeof(struct leaf),
1927                                                sizeof(struct leaf_info)),
1928                                            0, SLAB_PANIC, NULL);
1929 }
1930
1931
1932 struct fib_table *fib_trie_table(u32 id)
1933 {
1934         struct fib_table *tb;
1935         struct trie *t;
1936
1937         tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1938                      GFP_KERNEL);
1939         if (tb == NULL)
1940                 return NULL;
1941
1942         tb->tb_id = id;
1943         tb->tb_default = -1;
1944
1945         t = (struct trie *) tb->tb_data;
1946         memset(t, 0, sizeof(*t));
1947
1948         if (id == RT_TABLE_LOCAL)
1949                 pr_info("IPv4 FIB: Using LC-trie version %s\n", VERSION);
1950
1951         return tb;
1952 }
1953
1954 #ifdef CONFIG_PROC_FS
1955 /* Depth first Trie walk iterator */
1956 struct fib_trie_iter {
1957         struct seq_net_private p;
1958         struct fib_table *tb;
1959         struct tnode *tnode;
1960         unsigned int index;
1961         unsigned int depth;
1962 };
1963
1964 static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
1965 {
1966         struct tnode *tn = iter->tnode;
1967         unsigned int cindex = iter->index;
1968         struct tnode *p;
1969
1970         /* A single entry routing table */
1971         if (!tn)
1972                 return NULL;
1973
1974         pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
1975                  iter->tnode, iter->index, iter->depth);
1976 rescan:
1977         while (cindex < (1<<tn->bits)) {
1978                 struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
1979
1980                 if (n) {
1981                         if (IS_LEAF(n)) {
1982                                 iter->tnode = tn;
1983                                 iter->index = cindex + 1;
1984                         } else {
1985                                 /* push down one level */
1986                                 iter->tnode = (struct tnode *) n;
1987                                 iter->index = 0;
1988                                 ++iter->depth;
1989                         }
1990                         return n;
1991                 }
1992
1993                 ++cindex;
1994         }
1995
1996         /* Current node exhausted, pop back up */
1997         p = node_parent_rcu((struct rt_trie_node *)tn);
1998         if (p) {
1999                 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2000                 tn = p;
2001                 --iter->depth;
2002                 goto rescan;
2003         }
2004
2005         /* got root? */
2006         return NULL;
2007 }
2008
2009 static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
2010                                        struct trie *t)
2011 {
2012         struct rt_trie_node *n;
2013
2014         if (!t)
2015                 return NULL;
2016
2017         n = rcu_dereference(t->trie);
2018         if (!n)
2019                 return NULL;
2020
2021         if (IS_TNODE(n)) {
2022                 iter->tnode = (struct tnode *) n;
2023                 iter->index = 0;
2024                 iter->depth = 1;
2025         } else {
2026                 iter->tnode = NULL;
2027                 iter->index = 0;
2028                 iter->depth = 0;
2029         }
2030
2031         return n;
2032 }
2033
2034 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2035 {
2036         struct rt_trie_node *n;
2037         struct fib_trie_iter iter;
2038
2039         memset(s, 0, sizeof(*s));
2040
2041         rcu_read_lock();
2042         for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2043                 if (IS_LEAF(n)) {
2044                         struct leaf *l = (struct leaf *)n;
2045                         struct leaf_info *li;
2046                         struct hlist_node *tmp;
2047
2048                         s->leaves++;
2049                         s->totdepth += iter.depth;
2050                         if (iter.depth > s->maxdepth)
2051                                 s->maxdepth = iter.depth;
2052
2053                         hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
2054                                 ++s->prefixes;
2055                 } else {
2056                         const struct tnode *tn = (const struct tnode *) n;
2057                         int i;
2058
2059                         s->tnodes++;
2060                         if (tn->bits < MAX_STAT_DEPTH)
2061                                 s->nodesizes[tn->bits]++;
2062
2063                         for (i = 0; i < (1<<tn->bits); i++)
2064                                 if (!tn->child[i])
2065                                         s->nullpointers++;
2066                 }
2067         }
2068         rcu_read_unlock();
2069 }
2070
2071 /*
2072  *      This outputs /proc/net/fib_triestats
2073  */
2074 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2075 {
2076         unsigned int i, max, pointers, bytes, avdepth;
2077
2078         if (stat->leaves)
2079                 avdepth = stat->totdepth*100 / stat->leaves;
2080         else
2081                 avdepth = 0;
2082
2083         seq_printf(seq, "\tAver depth:     %u.%02d\n",
2084                    avdepth / 100, avdepth % 100);
2085         seq_printf(seq, "\tMax depth:      %u\n", stat->maxdepth);
2086
2087         seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
2088         bytes = sizeof(struct leaf) * stat->leaves;
2089
2090         seq_printf(seq, "\tPrefixes:       %u\n", stat->prefixes);
2091         bytes += sizeof(struct leaf_info) * stat->prefixes;
2092
2093         seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2094         bytes += sizeof(struct tnode) * stat->tnodes;
2095
2096         max = MAX_STAT_DEPTH;
2097         while (max > 0 && stat->nodesizes[max-1] == 0)
2098                 max--;
2099
2100         pointers = 0;
2101         for (i = 1; i <= max; i++)
2102                 if (stat->nodesizes[i] != 0) {
2103                         seq_printf(seq, "  %u: %u",  i, stat->nodesizes[i]);
2104                         pointers += (1<<i) * stat->nodesizes[i];
2105                 }
2106         seq_putc(seq, '\n');
2107         seq_printf(seq, "\tPointers: %u\n", pointers);
2108
2109         bytes += sizeof(struct rt_trie_node *) * pointers;
2110         seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2111         seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
2112 }
2113
2114 #ifdef CONFIG_IP_FIB_TRIE_STATS
2115 static void trie_show_usage(struct seq_file *seq,
2116                             const struct trie_use_stats *stats)
2117 {
2118         seq_printf(seq, "\nCounters:\n---------\n");
2119         seq_printf(seq, "gets = %u\n", stats->gets);
2120         seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2121         seq_printf(seq, "semantic match passed = %u\n",
2122                    stats->semantic_match_passed);
2123         seq_printf(seq, "semantic match miss = %u\n",
2124                    stats->semantic_match_miss);
2125         seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2126         seq_printf(seq, "skipped node resize = %u\n\n",
2127                    stats->resize_node_skipped);
2128 }
2129 #endif /*  CONFIG_IP_FIB_TRIE_STATS */
2130
2131 static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2132 {
2133         if (tb->tb_id == RT_TABLE_LOCAL)
2134                 seq_puts(seq, "Local:\n");
2135         else if (tb->tb_id == RT_TABLE_MAIN)
2136                 seq_puts(seq, "Main:\n");
2137         else
2138                 seq_printf(seq, "Id %d:\n", tb->tb_id);
2139 }
2140
2141
2142 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2143 {
2144         struct net *net = (struct net *)seq->private;
2145         unsigned int h;
2146
2147         seq_printf(seq,
2148                    "Basic info: size of leaf:"
2149                    " %Zd bytes, size of tnode: %Zd bytes.\n",
2150                    sizeof(struct leaf), sizeof(struct tnode));
2151
2152         for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2153                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2154                 struct hlist_node *node;
2155                 struct fib_table *tb;
2156
2157                 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2158                         struct trie *t = (struct trie *) tb->tb_data;
2159                         struct trie_stat stat;
2160
2161                         if (!t)
2162                                 continue;
2163
2164                         fib_table_print(seq, tb);
2165
2166                         trie_collect_stats(t, &stat);
2167                         trie_show_stats(seq, &stat);
2168 #ifdef CONFIG_IP_FIB_TRIE_STATS
2169                         trie_show_usage(seq, &t->stats);
2170 #endif
2171                 }
2172         }
2173
2174         return 0;
2175 }
2176
2177 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2178 {
2179         return single_open_net(inode, file, fib_triestat_seq_show);
2180 }
2181
2182 static const struct file_operations fib_triestat_fops = {
2183         .owner  = THIS_MODULE,
2184         .open   = fib_triestat_seq_open,
2185         .read   = seq_read,
2186         .llseek = seq_lseek,
2187         .release = single_release_net,
2188 };
2189
2190 static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2191 {
2192         struct fib_trie_iter *iter = seq->private;
2193         struct net *net = seq_file_net(seq);
2194         loff_t idx = 0;
2195         unsigned int h;
2196
2197         for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2198                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2199                 struct hlist_node *node;
2200                 struct fib_table *tb;
2201
2202                 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2203                         struct rt_trie_node *n;
2204
2205                         for (n = fib_trie_get_first(iter,
2206                                                     (struct trie *) tb->tb_data);
2207                              n; n = fib_trie_get_next(iter))
2208                                 if (pos == idx++) {
2209                                         iter->tb = tb;
2210                                         return n;
2211                                 }
2212                 }
2213         }
2214
2215         return NULL;
2216 }
2217
2218 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2219         __acquires(RCU)
2220 {
2221         rcu_read_lock();
2222         return fib_trie_get_idx(seq, *pos);
2223 }
2224
2225 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2226 {
2227         struct fib_trie_iter *iter = seq->private;
2228         struct net *net = seq_file_net(seq);
2229         struct fib_table *tb = iter->tb;
2230         struct hlist_node *tb_node;
2231         unsigned int h;
2232         struct rt_trie_node *n;
2233
2234         ++*pos;
2235         /* next node in same table */
2236         n = fib_trie_get_next(iter);
2237         if (n)
2238                 return n;
2239
2240         /* walk rest of this hash chain */
2241         h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2242         while ( (tb_node = rcu_dereference(tb->tb_hlist.next)) ) {
2243                 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2244                 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2245                 if (n)
2246                         goto found;
2247         }
2248
2249         /* new hash chain */
2250         while (++h < FIB_TABLE_HASHSZ) {
2251                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2252                 hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) {
2253                         n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2254                         if (n)
2255                                 goto found;
2256                 }
2257         }
2258         return NULL;
2259
2260 found:
2261         iter->tb = tb;
2262         return n;
2263 }
2264
2265 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2266         __releases(RCU)
2267 {
2268         rcu_read_unlock();
2269 }
2270
2271 static void seq_indent(struct seq_file *seq, int n)
2272 {
2273         while (n-- > 0)
2274                 seq_puts(seq, "   ");
2275 }
2276
2277 static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2278 {
2279         switch (s) {
2280         case RT_SCOPE_UNIVERSE: return "universe";
2281         case RT_SCOPE_SITE:     return "site";
2282         case RT_SCOPE_LINK:     return "link";
2283         case RT_SCOPE_HOST:     return "host";
2284         case RT_SCOPE_NOWHERE:  return "nowhere";
2285         default:
2286                 snprintf(buf, len, "scope=%d", s);
2287                 return buf;
2288         }
2289 }
2290
2291 static const char *const rtn_type_names[__RTN_MAX] = {
2292         [RTN_UNSPEC] = "UNSPEC",
2293         [RTN_UNICAST] = "UNICAST",
2294         [RTN_LOCAL] = "LOCAL",
2295         [RTN_BROADCAST] = "BROADCAST",
2296         [RTN_ANYCAST] = "ANYCAST",
2297         [RTN_MULTICAST] = "MULTICAST",
2298         [RTN_BLACKHOLE] = "BLACKHOLE",
2299         [RTN_UNREACHABLE] = "UNREACHABLE",
2300         [RTN_PROHIBIT] = "PROHIBIT",
2301         [RTN_THROW] = "THROW",
2302         [RTN_NAT] = "NAT",
2303         [RTN_XRESOLVE] = "XRESOLVE",
2304 };
2305
2306 static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2307 {
2308         if (t < __RTN_MAX && rtn_type_names[t])
2309                 return rtn_type_names[t];
2310         snprintf(buf, len, "type %u", t);
2311         return buf;
2312 }
2313
2314 /* Pretty print the trie */
2315 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2316 {
2317         const struct fib_trie_iter *iter = seq->private;
2318         struct rt_trie_node *n = v;
2319
2320         if (!node_parent_rcu(n))
2321                 fib_table_print(seq, iter->tb);
2322
2323         if (IS_TNODE(n)) {
2324                 struct tnode *tn = (struct tnode *) n;
2325                 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2326
2327                 seq_indent(seq, iter->depth-1);
2328                 seq_printf(seq, "  +-- %pI4/%d %d %d %d\n",
2329                            &prf, tn->pos, tn->bits, tn->full_children,
2330                            tn->empty_children);
2331
2332         } else {
2333                 struct leaf *l = (struct leaf *) n;
2334                 struct leaf_info *li;
2335                 struct hlist_node *node;
2336                 __be32 val = htonl(l->key);
2337
2338                 seq_indent(seq, iter->depth);
2339                 seq_printf(seq, "  |-- %pI4\n", &val);
2340
2341                 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2342                         struct fib_alias *fa;
2343
2344                         list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2345                                 char buf1[32], buf2[32];
2346
2347                                 seq_indent(seq, iter->depth+1);
2348                                 seq_printf(seq, "  /%d %s %s", li->plen,
2349                                            rtn_scope(buf1, sizeof(buf1),
2350                                                      fa->fa_scope),
2351                                            rtn_type(buf2, sizeof(buf2),
2352                                                     fa->fa_type));
2353                                 if (fa->fa_tos)
2354                                         seq_printf(seq, " tos=%d", fa->fa_tos);
2355                                 seq_putc(seq, '\n');
2356                         }
2357                 }
2358         }
2359
2360         return 0;
2361 }
2362
2363 static const struct seq_operations fib_trie_seq_ops = {
2364         .start  = fib_trie_seq_start,
2365         .next   = fib_trie_seq_next,
2366         .stop   = fib_trie_seq_stop,
2367         .show   = fib_trie_seq_show,
2368 };
2369
2370 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2371 {
2372         return seq_open_net(inode, file, &fib_trie_seq_ops,
2373                             sizeof(struct fib_trie_iter));
2374 }
2375
2376 static const struct file_operations fib_trie_fops = {
2377         .owner  = THIS_MODULE,
2378         .open   = fib_trie_seq_open,
2379         .read   = seq_read,
2380         .llseek = seq_lseek,
2381         .release = seq_release_net,
2382 };
2383
2384 struct fib_route_iter {
2385         struct seq_net_private p;
2386         struct trie *main_trie;
2387         loff_t  pos;
2388         t_key   key;
2389 };
2390
2391 static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2392 {
2393         struct leaf *l = NULL;
2394         struct trie *t = iter->main_trie;
2395
2396         /* use cache location of last found key */
2397         if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2398                 pos -= iter->pos;
2399         else {
2400                 iter->pos = 0;
2401                 l = trie_firstleaf(t);
2402         }
2403
2404         while (l && pos-- > 0) {
2405                 iter->pos++;
2406                 l = trie_nextleaf(l);
2407         }
2408
2409         if (l)
2410                 iter->key = pos;        /* remember it */
2411         else
2412                 iter->pos = 0;          /* forget it */
2413
2414         return l;
2415 }
2416
2417 static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2418         __acquires(RCU)
2419 {
2420         struct fib_route_iter *iter = seq->private;
2421         struct fib_table *tb;
2422
2423         rcu_read_lock();
2424         tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2425         if (!tb)
2426                 return NULL;
2427
2428         iter->main_trie = (struct trie *) tb->tb_data;
2429         if (*pos == 0)
2430                 return SEQ_START_TOKEN;
2431         else
2432                 return fib_route_get_idx(iter, *pos - 1);
2433 }
2434
2435 static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2436 {
2437         struct fib_route_iter *iter = seq->private;
2438         struct leaf *l = v;
2439
2440         ++*pos;
2441         if (v == SEQ_START_TOKEN) {
2442                 iter->pos = 0;
2443                 l = trie_firstleaf(iter->main_trie);
2444         } else {
2445                 iter->pos++;
2446                 l = trie_nextleaf(l);
2447         }
2448
2449         if (l)
2450                 iter->key = l->key;
2451         else
2452                 iter->pos = 0;
2453         return l;
2454 }
2455
2456 static void fib_route_seq_stop(struct seq_file *seq, void *v)
2457         __releases(RCU)
2458 {
2459         rcu_read_unlock();
2460 }
2461
2462 static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2463 {
2464         unsigned int flags = 0;
2465
2466         if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
2467                 flags = RTF_REJECT;
2468         if (fi && fi->fib_nh->nh_gw)
2469                 flags |= RTF_GATEWAY;
2470         if (mask == htonl(0xFFFFFFFF))
2471                 flags |= RTF_HOST;
2472         flags |= RTF_UP;
2473         return flags;
2474 }
2475
2476 /*
2477  *      This outputs /proc/net/route.
2478  *      The format of the file is not supposed to be changed
2479  *      and needs to be same as fib_hash output to avoid breaking
2480  *      legacy utilities
2481  */
2482 static int fib_route_seq_show(struct seq_file *seq, void *v)
2483 {
2484         struct leaf *l = v;
2485         struct leaf_info *li;
2486         struct hlist_node *node;
2487
2488         if (v == SEQ_START_TOKEN) {
2489                 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2490                            "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2491                            "\tWindow\tIRTT");
2492                 return 0;
2493         }
2494
2495         hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2496                 struct fib_alias *fa;
2497                 __be32 mask, prefix;
2498
2499                 mask = inet_make_mask(li->plen);
2500                 prefix = htonl(l->key);
2501
2502                 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2503                         const struct fib_info *fi = fa->fa_info;
2504                         unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2505                         int len;
2506
2507                         if (fa->fa_type == RTN_BROADCAST
2508                             || fa->fa_type == RTN_MULTICAST)
2509                                 continue;
2510
2511                         if (fi)
2512                                 seq_printf(seq,
2513                                          "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2514                                          "%d\t%08X\t%d\t%u\t%u%n",
2515                                          fi->fib_dev ? fi->fib_dev->name : "*",
2516                                          prefix,
2517                                          fi->fib_nh->nh_gw, flags, 0, 0,
2518                                          fi->fib_priority,
2519                                          mask,
2520                                          (fi->fib_advmss ?
2521                                           fi->fib_advmss + 40 : 0),
2522                                          fi->fib_window,
2523                                          fi->fib_rtt >> 3, &len);
2524                         else
2525                                 seq_printf(seq,
2526                                          "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2527                                          "%d\t%08X\t%d\t%u\t%u%n",
2528                                          prefix, 0, flags, 0, 0, 0,
2529                                          mask, 0, 0, 0, &len);
2530
2531                         seq_printf(seq, "%*s\n", 127 - len, "");
2532                 }
2533         }
2534
2535         return 0;
2536 }
2537
2538 static const struct seq_operations fib_route_seq_ops = {
2539         .start  = fib_route_seq_start,
2540         .next   = fib_route_seq_next,
2541         .stop   = fib_route_seq_stop,
2542         .show   = fib_route_seq_show,
2543 };
2544
2545 static int fib_route_seq_open(struct inode *inode, struct file *file)
2546 {
2547         return seq_open_net(inode, file, &fib_route_seq_ops,
2548                             sizeof(struct fib_route_iter));
2549 }
2550
2551 static const struct file_operations fib_route_fops = {
2552         .owner  = THIS_MODULE,
2553         .open   = fib_route_seq_open,
2554         .read   = seq_read,
2555         .llseek = seq_lseek,
2556         .release = seq_release_net,
2557 };
2558
2559 int __net_init fib_proc_init(struct net *net)
2560 {
2561         if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
2562                 goto out1;
2563
2564         if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
2565                                   &fib_triestat_fops))
2566                 goto out2;
2567
2568         if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
2569                 goto out3;
2570
2571         return 0;
2572
2573 out3:
2574         proc_net_remove(net, "fib_triestat");
2575 out2:
2576         proc_net_remove(net, "fib_trie");
2577 out1:
2578         return -ENOMEM;
2579 }
2580
2581 void __net_exit fib_proc_exit(struct net *net)
2582 {
2583         proc_net_remove(net, "fib_trie");
2584         proc_net_remove(net, "fib_triestat");
2585         proc_net_remove(net, "route");
2586 }
2587
2588 #endif /* CONFIG_PROC_FS */