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