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