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