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