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