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