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.
7 * Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
8 * & Swedish University of Agricultural Sciences.
10 * Jens Laas <jens.laas@data.slu.se> Swedish University of
11 * Agricultural Sciences.
13 * Hans Liss <hans.liss@its.uu.se> Uppsala Universitet
15 * This work is based on the LPC-trie which is originally descibed in:
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/
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
25 * Version: $Id: fib_trie.c,v 1.3 2005/06/08 14:20:01 robert Exp $
28 * Code from fib_hash has been reused which includes the following header:
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.
35 * IPv4 FIB: lookup engine and maintenance routines.
38 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
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.
45 * Substantial contributions to this work comes from:
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>
53 #define VERSION "0.408"
55 #include <asm/uaccess.h>
56 #include <asm/system.h>
57 #include <linux/bitops.h>
58 #include <linux/types.h>
59 #include <linux/kernel.h>
61 #include <linux/string.h>
62 #include <linux/socket.h>
63 #include <linux/sockios.h>
64 #include <linux/errno.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/net_namespace.h>
78 #include <net/protocol.h>
79 #include <net/route.h>
82 #include <net/ip_fib.h>
83 #include "fib_lookup.h"
85 #define MAX_STAT_DEPTH 32
87 #define KEYLENGTH (8*sizeof(t_key))
89 typedef unsigned int t_key
;
93 #define NODE_TYPE_MASK 0x1UL
94 #define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
96 #define IS_TNODE(n) (!(n->parent & T_LEAF))
97 #define IS_LEAF(n) (n->parent & T_LEAF)
100 unsigned long parent
;
105 unsigned long parent
;
107 struct hlist_head list
;
112 struct hlist_node hlist
;
115 struct list_head falh
;
119 unsigned long parent
;
121 unsigned char pos
; /* 2log(KEYLENGTH) bits needed */
122 unsigned char bits
; /* 2log(KEYLENGTH) bits needed */
123 unsigned int full_children
; /* KEYLENGTH bits needed */
124 unsigned int empty_children
; /* KEYLENGTH bits needed */
126 struct node
*child
[0];
129 #ifdef CONFIG_IP_FIB_TRIE_STATS
130 struct trie_use_stats
{
132 unsigned int backtrack
;
133 unsigned int semantic_match_passed
;
134 unsigned int semantic_match_miss
;
135 unsigned int null_node_hit
;
136 unsigned int resize_node_skipped
;
141 unsigned int totdepth
;
142 unsigned int maxdepth
;
145 unsigned int nullpointers
;
146 unsigned int nodesizes
[MAX_STAT_DEPTH
];
151 #ifdef CONFIG_IP_FIB_TRIE_STATS
152 struct trie_use_stats stats
;
157 static void put_child(struct trie
*t
, struct tnode
*tn
, int i
, struct node
*n
);
158 static void tnode_put_child_reorg(struct tnode
*tn
, int i
, struct node
*n
, int wasfull
);
159 static struct node
*resize(struct trie
*t
, struct tnode
*tn
);
160 static struct tnode
*inflate(struct trie
*t
, struct tnode
*tn
);
161 static struct tnode
*halve(struct trie
*t
, struct tnode
*tn
);
162 static void tnode_free(struct tnode
*tn
);
164 static struct kmem_cache
*fn_alias_kmem __read_mostly
;
166 static inline struct tnode
*node_parent(struct node
*node
)
170 ret
= (struct tnode
*)(node
->parent
& ~NODE_TYPE_MASK
);
171 return rcu_dereference(ret
);
174 static inline void node_set_parent(struct node
*node
, struct tnode
*ptr
)
176 rcu_assign_pointer(node
->parent
,
177 (unsigned long)ptr
| NODE_TYPE(node
));
180 /* rcu_read_lock needs to be hold by caller from readside */
182 static inline struct node
*tnode_get_child(struct tnode
*tn
, int i
)
184 BUG_ON(i
>= 1 << tn
->bits
);
186 return rcu_dereference(tn
->child
[i
]);
189 static inline int tnode_child_length(const struct tnode
*tn
)
191 return 1 << tn
->bits
;
194 static inline t_key
mask_pfx(t_key k
, unsigned short l
)
196 return (l
== 0) ? 0 : k
>> (KEYLENGTH
-l
) << (KEYLENGTH
-l
);
199 static inline t_key
tkey_extract_bits(t_key a
, int offset
, int bits
)
201 if (offset
< KEYLENGTH
)
202 return ((t_key
)(a
<< offset
)) >> (KEYLENGTH
- bits
);
207 static inline int tkey_equals(t_key a
, t_key b
)
212 static inline int tkey_sub_equals(t_key a
, int offset
, int bits
, t_key b
)
214 if (bits
== 0 || offset
>= KEYLENGTH
)
216 bits
= bits
> KEYLENGTH
? KEYLENGTH
: bits
;
217 return ((a
^ b
) << offset
) >> (KEYLENGTH
- bits
) == 0;
220 static inline int tkey_mismatch(t_key a
, int offset
, t_key b
)
227 while ((diff
<< i
) >> (KEYLENGTH
-1) == 0)
233 To understand this stuff, an understanding of keys and all their bits is
234 necessary. Every node in the trie has a key associated with it, but not
235 all of the bits in that key are significant.
237 Consider a node 'n' and its parent 'tp'.
239 If n is a leaf, every bit in its key is significant. Its presence is
240 necessitated by path compression, since during a tree traversal (when
241 searching for a leaf - unless we are doing an insertion) we will completely
242 ignore all skipped bits we encounter. Thus we need to verify, at the end of
243 a potentially successful search, that we have indeed been walking the
246 Note that we can never "miss" the correct key in the tree if present by
247 following the wrong path. Path compression ensures that segments of the key
248 that are the same for all keys with a given prefix are skipped, but the
249 skipped part *is* identical for each node in the subtrie below the skipped
250 bit! trie_insert() in this implementation takes care of that - note the
251 call to tkey_sub_equals() in trie_insert().
253 if n is an internal node - a 'tnode' here, the various parts of its key
254 have many different meanings.
257 _________________________________________________________________
258 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
259 -----------------------------------------------------------------
260 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
262 _________________________________________________________________
263 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
264 -----------------------------------------------------------------
265 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
272 First, let's just ignore the bits that come before the parent tp, that is
273 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
274 not use them for anything.
276 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
277 index into the parent's child array. That is, they will be used to find
278 'n' among tp's children.
280 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
283 All the bits we have seen so far are significant to the node n. The rest
284 of the bits are really not needed or indeed known in n->key.
286 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
287 n's child array, and will of course be different for each child.
290 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
295 static inline void check_tnode(const struct tnode
*tn
)
297 WARN_ON(tn
&& tn
->pos
+tn
->bits
> 32);
300 static const int halve_threshold
= 25;
301 static const int inflate_threshold
= 50;
302 static const int halve_threshold_root
= 8;
303 static const int inflate_threshold_root
= 15;
306 static void __alias_free_mem(struct rcu_head
*head
)
308 struct fib_alias
*fa
= container_of(head
, struct fib_alias
, rcu
);
309 kmem_cache_free(fn_alias_kmem
, fa
);
312 static inline void alias_free_mem_rcu(struct fib_alias
*fa
)
314 call_rcu(&fa
->rcu
, __alias_free_mem
);
317 static void __leaf_free_rcu(struct rcu_head
*head
)
319 kfree(container_of(head
, struct leaf
, rcu
));
322 static void __leaf_info_free_rcu(struct rcu_head
*head
)
324 kfree(container_of(head
, struct leaf_info
, rcu
));
327 static inline void free_leaf_info(struct leaf_info
*leaf
)
329 call_rcu(&leaf
->rcu
, __leaf_info_free_rcu
);
332 static struct tnode
*tnode_alloc(size_t size
)
336 if (size
<= PAGE_SIZE
)
337 return kzalloc(size
, GFP_KERNEL
);
339 pages
= alloc_pages(GFP_KERNEL
|__GFP_ZERO
, get_order(size
));
343 return page_address(pages
);
346 static void __tnode_free_rcu(struct rcu_head
*head
)
348 struct tnode
*tn
= container_of(head
, struct tnode
, rcu
);
349 size_t size
= sizeof(struct tnode
) +
350 (sizeof(struct node
*) << tn
->bits
);
352 if (size
<= PAGE_SIZE
)
355 free_pages((unsigned long)tn
, get_order(size
));
358 static inline void tnode_free(struct tnode
*tn
)
361 struct leaf
*l
= (struct leaf
*) tn
;
362 call_rcu_bh(&l
->rcu
, __leaf_free_rcu
);
364 call_rcu(&tn
->rcu
, __tnode_free_rcu
);
367 static struct leaf
*leaf_new(void)
369 struct leaf
*l
= kmalloc(sizeof(struct leaf
), GFP_KERNEL
);
372 INIT_HLIST_HEAD(&l
->list
);
377 static struct leaf_info
*leaf_info_new(int plen
)
379 struct leaf_info
*li
= kmalloc(sizeof(struct leaf_info
), GFP_KERNEL
);
382 INIT_LIST_HEAD(&li
->falh
);
387 static struct tnode
* tnode_new(t_key key
, int pos
, int bits
)
389 size_t sz
= sizeof(struct tnode
) + (sizeof(struct node
*) << bits
);
390 struct tnode
*tn
= tnode_alloc(sz
);
393 tn
->parent
= T_TNODE
;
397 tn
->full_children
= 0;
398 tn
->empty_children
= 1<<bits
;
401 pr_debug("AT %p s=%u %lu\n", tn
, (unsigned int) sizeof(struct tnode
),
402 (unsigned long) (sizeof(struct node
) << bits
));
407 * Check whether a tnode 'n' is "full", i.e. it is an internal node
408 * and no bits are skipped. See discussion in dyntree paper p. 6
411 static inline int tnode_full(const struct tnode
*tn
, const struct node
*n
)
413 if (n
== NULL
|| IS_LEAF(n
))
416 return ((struct tnode
*) n
)->pos
== tn
->pos
+ tn
->bits
;
419 static inline void put_child(struct trie
*t
, struct tnode
*tn
, int i
, struct node
*n
)
421 tnode_put_child_reorg(tn
, i
, n
, -1);
425 * Add a child at position i overwriting the old value.
426 * Update the value of full_children and empty_children.
429 static void tnode_put_child_reorg(struct tnode
*tn
, int i
, struct node
*n
, int wasfull
)
431 struct node
*chi
= tn
->child
[i
];
434 BUG_ON(i
>= 1<<tn
->bits
);
437 /* update emptyChildren */
438 if (n
== NULL
&& chi
!= NULL
)
439 tn
->empty_children
++;
440 else if (n
!= NULL
&& chi
== NULL
)
441 tn
->empty_children
--;
443 /* update fullChildren */
445 wasfull
= tnode_full(tn
, chi
);
447 isfull
= tnode_full(tn
, n
);
448 if (wasfull
&& !isfull
)
450 else if (!wasfull
&& isfull
)
454 node_set_parent(n
, tn
);
456 rcu_assign_pointer(tn
->child
[i
], n
);
459 static struct node
*resize(struct trie
*t
, struct tnode
*tn
)
463 struct tnode
*old_tn
;
464 int inflate_threshold_use
;
465 int halve_threshold_use
;
471 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
472 tn
, inflate_threshold
, halve_threshold
);
475 if (tn
->empty_children
== tnode_child_length(tn
)) {
480 if (tn
->empty_children
== tnode_child_length(tn
) - 1)
481 for (i
= 0; i
< tnode_child_length(tn
); i
++) {
488 /* compress one level */
489 node_set_parent(n
, NULL
);
494 * Double as long as the resulting node has a number of
495 * nonempty nodes that are above the threshold.
499 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
500 * the Helsinki University of Technology and Matti Tikkanen of Nokia
501 * Telecommunications, page 6:
502 * "A node is doubled if the ratio of non-empty children to all
503 * children in the *doubled* node is at least 'high'."
505 * 'high' in this instance is the variable 'inflate_threshold'. It
506 * is expressed as a percentage, so we multiply it with
507 * tnode_child_length() and instead of multiplying by 2 (since the
508 * child array will be doubled by inflate()) and multiplying
509 * the left-hand side by 100 (to handle the percentage thing) we
510 * multiply the left-hand side by 50.
512 * The left-hand side may look a bit weird: tnode_child_length(tn)
513 * - tn->empty_children is of course the number of non-null children
514 * in the current node. tn->full_children is the number of "full"
515 * children, that is non-null tnodes with a skip value of 0.
516 * All of those will be doubled in the resulting inflated tnode, so
517 * we just count them one extra time here.
519 * A clearer way to write this would be:
521 * to_be_doubled = tn->full_children;
522 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
525 * new_child_length = tnode_child_length(tn) * 2;
527 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
529 * if (new_fill_factor >= inflate_threshold)
531 * ...and so on, tho it would mess up the while () loop.
534 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
538 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
539 * inflate_threshold * new_child_length
541 * expand not_to_be_doubled and to_be_doubled, and shorten:
542 * 100 * (tnode_child_length(tn) - tn->empty_children +
543 * tn->full_children) >= inflate_threshold * new_child_length
545 * expand new_child_length:
546 * 100 * (tnode_child_length(tn) - tn->empty_children +
547 * tn->full_children) >=
548 * inflate_threshold * tnode_child_length(tn) * 2
551 * 50 * (tn->full_children + tnode_child_length(tn) -
552 * tn->empty_children) >= inflate_threshold *
553 * tnode_child_length(tn)
559 /* Keep root node larger */
562 inflate_threshold_use
= inflate_threshold_root
;
564 inflate_threshold_use
= inflate_threshold
;
568 while ((tn
->full_children
> 0 && max_resize
-- &&
569 50 * (tn
->full_children
+ tnode_child_length(tn
) - tn
->empty_children
) >=
570 inflate_threshold_use
* tnode_child_length(tn
))) {
576 #ifdef CONFIG_IP_FIB_TRIE_STATS
577 t
->stats
.resize_node_skipped
++;
583 if (max_resize
< 0) {
585 printk(KERN_WARNING
"Fix inflate_threshold_root. Now=%d size=%d bits\n",
586 inflate_threshold_root
, tn
->bits
);
588 printk(KERN_WARNING
"Fix inflate_threshold. Now=%d size=%d bits\n",
589 inflate_threshold
, tn
->bits
);
595 * Halve as long as the number of empty children in this
596 * node is above threshold.
600 /* Keep root node larger */
603 halve_threshold_use
= halve_threshold_root
;
605 halve_threshold_use
= halve_threshold
;
609 while (tn
->bits
> 1 && max_resize
-- &&
610 100 * (tnode_child_length(tn
) - tn
->empty_children
) <
611 halve_threshold_use
* tnode_child_length(tn
)) {
617 #ifdef CONFIG_IP_FIB_TRIE_STATS
618 t
->stats
.resize_node_skipped
++;
624 if (max_resize
< 0) {
626 printk(KERN_WARNING
"Fix halve_threshold_root. Now=%d size=%d bits\n",
627 halve_threshold_root
, tn
->bits
);
629 printk(KERN_WARNING
"Fix halve_threshold. Now=%d size=%d bits\n",
630 halve_threshold
, tn
->bits
);
633 /* Only one child remains */
634 if (tn
->empty_children
== tnode_child_length(tn
) - 1)
635 for (i
= 0; i
< tnode_child_length(tn
); i
++) {
642 /* compress one level */
644 node_set_parent(n
, NULL
);
649 return (struct node
*) tn
;
652 static struct tnode
*inflate(struct trie
*t
, struct tnode
*tn
)
654 struct tnode
*oldtnode
= tn
;
655 int olen
= tnode_child_length(tn
);
658 pr_debug("In inflate\n");
660 tn
= tnode_new(oldtnode
->key
, oldtnode
->pos
, oldtnode
->bits
+ 1);
663 return ERR_PTR(-ENOMEM
);
666 * Preallocate and store tnodes before the actual work so we
667 * don't get into an inconsistent state if memory allocation
668 * fails. In case of failure we return the oldnode and inflate
669 * of tnode is ignored.
672 for (i
= 0; i
< olen
; i
++) {
673 struct tnode
*inode
= (struct tnode
*) tnode_get_child(oldtnode
, i
);
677 inode
->pos
== oldtnode
->pos
+ oldtnode
->bits
&&
679 struct tnode
*left
, *right
;
680 t_key m
= ~0U << (KEYLENGTH
- 1) >> inode
->pos
;
682 left
= tnode_new(inode
->key
&(~m
), inode
->pos
+ 1,
687 right
= tnode_new(inode
->key
|m
, inode
->pos
+ 1,
695 put_child(t
, tn
, 2*i
, (struct node
*) left
);
696 put_child(t
, tn
, 2*i
+1, (struct node
*) right
);
700 for (i
= 0; i
< olen
; i
++) {
702 struct node
*node
= tnode_get_child(oldtnode
, i
);
703 struct tnode
*left
, *right
;
710 /* A leaf or an internal node with skipped bits */
712 if (IS_LEAF(node
) || ((struct tnode
*) node
)->pos
>
713 tn
->pos
+ tn
->bits
- 1) {
714 if (tkey_extract_bits(node
->key
, oldtnode
->pos
+ oldtnode
->bits
,
716 put_child(t
, tn
, 2*i
, node
);
718 put_child(t
, tn
, 2*i
+1, node
);
722 /* An internal node with two children */
723 inode
= (struct tnode
*) node
;
725 if (inode
->bits
== 1) {
726 put_child(t
, tn
, 2*i
, inode
->child
[0]);
727 put_child(t
, tn
, 2*i
+1, inode
->child
[1]);
733 /* An internal node with more than two children */
735 /* We will replace this node 'inode' with two new
736 * ones, 'left' and 'right', each with half of the
737 * original children. The two new nodes will have
738 * a position one bit further down the key and this
739 * means that the "significant" part of their keys
740 * (see the discussion near the top of this file)
741 * will differ by one bit, which will be "0" in
742 * left's key and "1" in right's key. Since we are
743 * moving the key position by one step, the bit that
744 * we are moving away from - the bit at position
745 * (inode->pos) - is the one that will differ between
746 * left and right. So... we synthesize that bit in the
748 * The mask 'm' below will be a single "one" bit at
749 * the position (inode->pos)
752 /* Use the old key, but set the new significant
756 left
= (struct tnode
*) tnode_get_child(tn
, 2*i
);
757 put_child(t
, tn
, 2*i
, NULL
);
761 right
= (struct tnode
*) tnode_get_child(tn
, 2*i
+1);
762 put_child(t
, tn
, 2*i
+1, NULL
);
766 size
= tnode_child_length(left
);
767 for (j
= 0; j
< size
; j
++) {
768 put_child(t
, left
, j
, inode
->child
[j
]);
769 put_child(t
, right
, j
, inode
->child
[j
+ size
]);
771 put_child(t
, tn
, 2*i
, resize(t
, left
));
772 put_child(t
, tn
, 2*i
+1, resize(t
, right
));
776 tnode_free(oldtnode
);
780 int size
= tnode_child_length(tn
);
783 for (j
= 0; j
< size
; j
++)
785 tnode_free((struct tnode
*)tn
->child
[j
]);
789 return ERR_PTR(-ENOMEM
);
793 static struct tnode
*halve(struct trie
*t
, struct tnode
*tn
)
795 struct tnode
*oldtnode
= tn
;
796 struct node
*left
, *right
;
798 int olen
= tnode_child_length(tn
);
800 pr_debug("In halve\n");
802 tn
= tnode_new(oldtnode
->key
, oldtnode
->pos
, oldtnode
->bits
- 1);
805 return ERR_PTR(-ENOMEM
);
808 * Preallocate and store tnodes before the actual work so we
809 * don't get into an inconsistent state if memory allocation
810 * fails. In case of failure we return the oldnode and halve
811 * of tnode is ignored.
814 for (i
= 0; i
< olen
; i
+= 2) {
815 left
= tnode_get_child(oldtnode
, i
);
816 right
= tnode_get_child(oldtnode
, i
+1);
818 /* Two nonempty children */
822 newn
= tnode_new(left
->key
, tn
->pos
+ tn
->bits
, 1);
827 put_child(t
, tn
, i
/2, (struct node
*)newn
);
832 for (i
= 0; i
< olen
; i
+= 2) {
833 struct tnode
*newBinNode
;
835 left
= tnode_get_child(oldtnode
, i
);
836 right
= tnode_get_child(oldtnode
, i
+1);
838 /* At least one of the children is empty */
840 if (right
== NULL
) /* Both are empty */
842 put_child(t
, tn
, i
/2, right
);
847 put_child(t
, tn
, i
/2, left
);
851 /* Two nonempty children */
852 newBinNode
= (struct tnode
*) tnode_get_child(tn
, i
/2);
853 put_child(t
, tn
, i
/2, NULL
);
854 put_child(t
, newBinNode
, 0, left
);
855 put_child(t
, newBinNode
, 1, right
);
856 put_child(t
, tn
, i
/2, resize(t
, newBinNode
));
858 tnode_free(oldtnode
);
862 int size
= tnode_child_length(tn
);
865 for (j
= 0; j
< size
; j
++)
867 tnode_free((struct tnode
*)tn
->child
[j
]);
871 return ERR_PTR(-ENOMEM
);
875 /* readside must use rcu_read_lock currently dump routines
876 via get_fa_head and dump */
878 static struct leaf_info
*find_leaf_info(struct leaf
*l
, int plen
)
880 struct hlist_head
*head
= &l
->list
;
881 struct hlist_node
*node
;
882 struct leaf_info
*li
;
884 hlist_for_each_entry_rcu(li
, node
, head
, hlist
)
885 if (li
->plen
== plen
)
891 static inline struct list_head
* get_fa_head(struct leaf
*l
, int plen
)
893 struct leaf_info
*li
= find_leaf_info(l
, plen
);
901 static void insert_leaf_info(struct hlist_head
*head
, struct leaf_info
*new)
903 struct leaf_info
*li
= NULL
, *last
= NULL
;
904 struct hlist_node
*node
;
906 if (hlist_empty(head
)) {
907 hlist_add_head_rcu(&new->hlist
, head
);
909 hlist_for_each_entry(li
, node
, head
, hlist
) {
910 if (new->plen
> li
->plen
)
916 hlist_add_after_rcu(&last
->hlist
, &new->hlist
);
918 hlist_add_before_rcu(&new->hlist
, &li
->hlist
);
922 /* rcu_read_lock needs to be hold by caller from readside */
925 fib_find_node(struct trie
*t
, u32 key
)
932 n
= rcu_dereference(t
->trie
);
934 while (n
!= NULL
&& NODE_TYPE(n
) == T_TNODE
) {
935 tn
= (struct tnode
*) n
;
939 if (tkey_sub_equals(tn
->key
, pos
, tn
->pos
-pos
, key
)) {
940 pos
= tn
->pos
+ tn
->bits
;
941 n
= tnode_get_child(tn
, tkey_extract_bits(key
, tn
->pos
, tn
->bits
));
945 /* Case we have found a leaf. Compare prefixes */
947 if (n
!= NULL
&& IS_LEAF(n
) && tkey_equals(key
, n
->key
))
948 return (struct leaf
*)n
;
953 static struct node
*trie_rebalance(struct trie
*t
, struct tnode
*tn
)
956 t_key cindex
, key
= tn
->key
;
959 while (tn
!= NULL
&& (tp
= node_parent((struct node
*)tn
)) != NULL
) {
960 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
961 wasfull
= tnode_full(tp
, tnode_get_child(tp
, cindex
));
962 tn
= (struct tnode
*) resize (t
, (struct tnode
*)tn
);
963 tnode_put_child_reorg((struct tnode
*)tp
, cindex
,(struct node
*)tn
, wasfull
);
965 tp
= node_parent((struct node
*) tn
);
971 /* Handle last (top) tnode */
973 tn
= (struct tnode
*) resize(t
, (struct tnode
*)tn
);
975 return (struct node
*) tn
;
978 /* only used from updater-side */
980 static struct list_head
*fib_insert_node(struct trie
*t
, u32 key
, int plen
)
983 struct tnode
*tp
= NULL
, *tn
= NULL
;
987 struct list_head
*fa_head
= NULL
;
988 struct leaf_info
*li
;
994 /* If we point to NULL, stop. Either the tree is empty and we should
995 * just put a new leaf in if, or we have reached an empty child slot,
996 * and we should just put our new leaf in that.
997 * If we point to a T_TNODE, check if it matches our key. Note that
998 * a T_TNODE might be skipping any number of bits - its 'pos' need
999 * not be the parent's 'pos'+'bits'!
1001 * If it does match the current key, get pos/bits from it, extract
1002 * the index from our key, push the T_TNODE and walk the tree.
1004 * If it doesn't, we have to replace it with a new T_TNODE.
1006 * If we point to a T_LEAF, it might or might not have the same key
1007 * as we do. If it does, just change the value, update the T_LEAF's
1008 * value, and return it.
1009 * If it doesn't, we need to replace it with a T_TNODE.
1012 while (n
!= NULL
&& NODE_TYPE(n
) == T_TNODE
) {
1013 tn
= (struct tnode
*) n
;
1017 if (tkey_sub_equals(tn
->key
, pos
, tn
->pos
-pos
, key
)) {
1019 pos
= tn
->pos
+ tn
->bits
;
1020 n
= tnode_get_child(tn
, tkey_extract_bits(key
, tn
->pos
, tn
->bits
));
1022 BUG_ON(n
&& node_parent(n
) != tn
);
1028 * n ----> NULL, LEAF or TNODE
1030 * tp is n's (parent) ----> NULL or TNODE
1033 BUG_ON(tp
&& IS_LEAF(tp
));
1035 /* Case 1: n is a leaf. Compare prefixes */
1037 if (n
!= NULL
&& IS_LEAF(n
) && tkey_equals(key
, n
->key
)) {
1038 l
= (struct leaf
*) n
;
1039 li
= leaf_info_new(plen
);
1044 fa_head
= &li
->falh
;
1045 insert_leaf_info(&l
->list
, li
);
1055 li
= leaf_info_new(plen
);
1058 tnode_free((struct tnode
*) l
);
1062 fa_head
= &li
->falh
;
1063 insert_leaf_info(&l
->list
, li
);
1065 if (t
->trie
&& n
== NULL
) {
1066 /* Case 2: n is NULL, and will just insert a new leaf */
1068 node_set_parent((struct node
*)l
, tp
);
1070 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1071 put_child(t
, (struct tnode
*)tp
, cindex
, (struct node
*)l
);
1073 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1075 * Add a new tnode here
1076 * first tnode need some special handling
1080 pos
= tp
->pos
+tp
->bits
;
1085 newpos
= tkey_mismatch(key
, pos
, n
->key
);
1086 tn
= tnode_new(n
->key
, newpos
, 1);
1089 tn
= tnode_new(key
, newpos
, 1); /* First tnode */
1094 tnode_free((struct tnode
*) l
);
1098 node_set_parent((struct node
*)tn
, tp
);
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
);
1105 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1106 put_child(t
, (struct tnode
*)tp
, cindex
, (struct node
*)tn
);
1108 rcu_assign_pointer(t
->trie
, (struct node
*)tn
); /* First tnode */
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
);
1117 /* Rebalance the trie */
1119 rcu_assign_pointer(t
->trie
, trie_rebalance(t
, tp
));
1125 * Caller must hold RTNL.
1127 static int fn_trie_insert(struct fib_table
*tb
, struct fib_config
*cfg
)
1129 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1130 struct fib_alias
*fa
, *new_fa
;
1131 struct list_head
*fa_head
= NULL
;
1132 struct fib_info
*fi
;
1133 int plen
= cfg
->fc_dst_len
;
1134 u8 tos
= cfg
->fc_tos
;
1142 key
= ntohl(cfg
->fc_dst
);
1144 pr_debug("Insert table=%u %08x/%d\n", tb
->tb_id
, key
, plen
);
1146 mask
= ntohl(inet_make_mask(plen
));
1153 fi
= fib_create_info(cfg
);
1159 l
= fib_find_node(t
, key
);
1163 fa_head
= get_fa_head(l
, plen
);
1164 fa
= fib_find_alias(fa_head
, tos
, fi
->fib_priority
);
1167 /* Now fa, if non-NULL, points to the first fib alias
1168 * with the same keys [prefix,tos,priority], if such key already
1169 * exists or to the node before which we will insert new one.
1171 * If fa is NULL, we will need to allocate a new one and
1172 * insert to the head of f.
1174 * If f is NULL, no fib node matched the destination key
1175 * and we need to allocate a new one of those as well.
1178 if (fa
&& fa
->fa_info
->fib_priority
== fi
->fib_priority
) {
1179 struct fib_alias
*fa_orig
;
1182 if (cfg
->fc_nlflags
& NLM_F_EXCL
)
1185 if (cfg
->fc_nlflags
& NLM_F_REPLACE
) {
1186 struct fib_info
*fi_drop
;
1189 if (fi
->fib_treeref
> 1)
1193 new_fa
= kmem_cache_alloc(fn_alias_kmem
, GFP_KERNEL
);
1197 fi_drop
= fa
->fa_info
;
1198 new_fa
->fa_tos
= fa
->fa_tos
;
1199 new_fa
->fa_info
= fi
;
1200 new_fa
->fa_type
= cfg
->fc_type
;
1201 new_fa
->fa_scope
= cfg
->fc_scope
;
1202 state
= fa
->fa_state
;
1203 new_fa
->fa_state
&= ~FA_S_ACCESSED
;
1205 list_replace_rcu(&fa
->fa_list
, &new_fa
->fa_list
);
1206 alias_free_mem_rcu(fa
);
1208 fib_release_info(fi_drop
);
1209 if (state
& FA_S_ACCESSED
)
1211 rtmsg_fib(RTM_NEWROUTE
, htonl(key
), new_fa
, plen
,
1212 tb
->tb_id
, &cfg
->fc_nlinfo
, NLM_F_REPLACE
);
1216 /* Error if we find a perfect match which
1217 * uses the same scope, type, and nexthop
1221 list_for_each_entry(fa
, fa_orig
->fa_list
.prev
, fa_list
) {
1222 if (fa
->fa_tos
!= tos
)
1224 if (fa
->fa_info
->fib_priority
!= fi
->fib_priority
)
1226 if (fa
->fa_type
== cfg
->fc_type
&&
1227 fa
->fa_scope
== cfg
->fc_scope
&&
1228 fa
->fa_info
== fi
) {
1232 if (!(cfg
->fc_nlflags
& NLM_F_APPEND
))
1236 if (!(cfg
->fc_nlflags
& NLM_F_CREATE
))
1240 new_fa
= kmem_cache_alloc(fn_alias_kmem
, GFP_KERNEL
);
1244 new_fa
->fa_info
= fi
;
1245 new_fa
->fa_tos
= tos
;
1246 new_fa
->fa_type
= cfg
->fc_type
;
1247 new_fa
->fa_scope
= cfg
->fc_scope
;
1248 new_fa
->fa_state
= 0;
1250 * Insert new entry to the list.
1254 fa_head
= fib_insert_node(t
, key
, plen
);
1255 if (unlikely(!fa_head
)) {
1257 goto out_free_new_fa
;
1261 list_add_tail_rcu(&new_fa
->fa_list
,
1262 (fa
? &fa
->fa_list
: fa_head
));
1265 rtmsg_fib(RTM_NEWROUTE
, htonl(key
), new_fa
, plen
, tb
->tb_id
,
1266 &cfg
->fc_nlinfo
, 0);
1271 kmem_cache_free(fn_alias_kmem
, new_fa
);
1273 fib_release_info(fi
);
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
)
1286 struct leaf_info
*li
;
1287 struct hlist_head
*hhead
= &l
->list
;
1288 struct hlist_node
*node
;
1290 hlist_for_each_entry_rcu(li
, node
, hhead
, hlist
) {
1292 mask
= inet_make_mask(i
);
1293 if (l
->key
!= (key
& ntohl(mask
)))
1296 if ((err
= fib_semantic_match(&li
->falh
, flp
, res
, htonl(l
->key
), mask
, i
)) <= 0) {
1298 #ifdef CONFIG_IP_FIB_TRIE_STATS
1299 t
->stats
.semantic_match_passed
++;
1303 #ifdef CONFIG_IP_FIB_TRIE_STATS
1304 t
->stats
.semantic_match_miss
++;
1311 fn_trie_lookup(struct fib_table
*tb
, const struct flowi
*flp
, struct fib_result
*res
)
1313 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1318 t_key key
= ntohl(flp
->fl4_dst
);
1321 int current_prefix_length
= KEYLENGTH
;
1323 t_key node_prefix
, key_prefix
, pref_mismatch
;
1328 n
= rcu_dereference(t
->trie
);
1332 #ifdef CONFIG_IP_FIB_TRIE_STATS
1338 if ((ret
= check_leaf(t
, (struct leaf
*)n
, key
, &plen
, flp
, res
)) <= 0)
1342 pn
= (struct tnode
*) n
;
1350 cindex
= tkey_extract_bits(mask_pfx(key
, current_prefix_length
),
1353 n
= tnode_get_child(pn
, cindex
);
1356 #ifdef CONFIG_IP_FIB_TRIE_STATS
1357 t
->stats
.null_node_hit
++;
1363 if ((ret
= check_leaf(t
, (struct leaf
*)n
, key
, &plen
, flp
, res
)) <= 0)
1371 cn
= (struct tnode
*)n
;
1374 * It's a tnode, and we can do some extra checks here if we
1375 * like, to avoid descending into a dead-end branch.
1376 * This tnode is in the parent's child array at index
1377 * key[p_pos..p_pos+p_bits] but potentially with some bits
1378 * chopped off, so in reality the index may be just a
1379 * subprefix, padded with zero at the end.
1380 * We can also take a look at any skipped bits in this
1381 * tnode - everything up to p_pos is supposed to be ok,
1382 * and the non-chopped bits of the index (se previous
1383 * paragraph) are also guaranteed ok, but the rest is
1384 * considered unknown.
1386 * The skipped bits are key[pos+bits..cn->pos].
1389 /* If current_prefix_length < pos+bits, we are already doing
1390 * actual prefix matching, which means everything from
1391 * pos+(bits-chopped_off) onward must be zero along some
1392 * branch of this subtree - otherwise there is *no* valid
1393 * prefix present. Here we can only check the skipped
1394 * bits. Remember, since we have already indexed into the
1395 * parent's child array, we know that the bits we chopped of
1399 /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */
1401 if (current_prefix_length
< pos
+bits
) {
1402 if (tkey_extract_bits(cn
->key
, current_prefix_length
,
1403 cn
->pos
- current_prefix_length
) != 0 ||
1409 * If chopped_off=0, the index is fully validated and we
1410 * only need to look at the skipped bits for this, the new,
1411 * tnode. What we actually want to do is to find out if
1412 * these skipped bits match our key perfectly, or if we will
1413 * have to count on finding a matching prefix further down,
1414 * because if we do, we would like to have some way of
1415 * verifying the existence of such a prefix at this point.
1418 /* The only thing we can do at this point is to verify that
1419 * any such matching prefix can indeed be a prefix to our
1420 * key, and if the bits in the node we are inspecting that
1421 * do not match our key are not ZERO, this cannot be true.
1422 * Thus, find out where there is a mismatch (before cn->pos)
1423 * and verify that all the mismatching bits are zero in the
1427 /* Note: We aren't very concerned about the piece of the key
1428 * that precede pn->pos+pn->bits, since these have already been
1429 * checked. The bits after cn->pos aren't checked since these are
1430 * by definition "unknown" at this point. Thus, what we want to
1431 * see is if we are about to enter the "prefix matching" state,
1432 * and in that case verify that the skipped bits that will prevail
1433 * throughout this subtree are zero, as they have to be if we are
1434 * to find a matching prefix.
1437 node_prefix
= mask_pfx(cn
->key
, cn
->pos
);
1438 key_prefix
= mask_pfx(key
, cn
->pos
);
1439 pref_mismatch
= key_prefix
^node_prefix
;
1442 /* In short: If skipped bits in this node do not match the search
1443 * key, enter the "prefix matching" state.directly.
1445 if (pref_mismatch
) {
1446 while (!(pref_mismatch
& (1<<(KEYLENGTH
-1)))) {
1448 pref_mismatch
= pref_mismatch
<<1;
1450 key_prefix
= tkey_extract_bits(cn
->key
, mp
, cn
->pos
-mp
);
1452 if (key_prefix
!= 0)
1455 if (current_prefix_length
>= cn
->pos
)
1456 current_prefix_length
= mp
;
1459 pn
= (struct tnode
*)n
; /* Descend */
1466 /* As zero don't change the child key (cindex) */
1467 while ((chopped_off
<= pn
->bits
) && !(cindex
& (1<<(chopped_off
-1))))
1470 /* Decrease current_... with bits chopped off */
1471 if (current_prefix_length
> pn
->pos
+ pn
->bits
- chopped_off
)
1472 current_prefix_length
= pn
->pos
+ pn
->bits
- chopped_off
;
1475 * Either we do the actual chop off according or if we have
1476 * chopped off all bits in this tnode walk up to our parent.
1479 if (chopped_off
<= pn
->bits
) {
1480 cindex
&= ~(1 << (chopped_off
-1));
1482 struct tnode
*parent
= node_parent((struct node
*) pn
);
1486 /* Get Child's index */
1487 cindex
= tkey_extract_bits(pn
->key
, parent
->pos
, parent
->bits
);
1491 #ifdef CONFIG_IP_FIB_TRIE_STATS
1492 t
->stats
.backtrack
++;
1504 /* only called from updater side */
1505 static int trie_leaf_remove(struct trie
*t
, t_key key
)
1508 struct tnode
*tp
= NULL
;
1509 struct node
*n
= t
->trie
;
1512 pr_debug("entering trie_leaf_remove(%p)\n", n
);
1514 /* Note that in the case skipped bits, those bits are *not* checked!
1515 * When we finish this, we will have NULL or a T_LEAF, and the
1516 * T_LEAF may or may not match our key.
1519 while (n
!= NULL
&& IS_TNODE(n
)) {
1520 struct tnode
*tn
= (struct tnode
*) n
;
1522 n
= tnode_get_child(tn
,tkey_extract_bits(key
, tn
->pos
, tn
->bits
));
1524 BUG_ON(n
&& node_parent(n
) != tn
);
1526 l
= (struct leaf
*) n
;
1528 if (!n
|| !tkey_equals(l
->key
, key
))
1533 * Remove the leaf and rebalance the tree
1538 tp
= node_parent(n
);
1539 tnode_free((struct tnode
*) n
);
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
));
1546 rcu_assign_pointer(t
->trie
, NULL
);
1552 * Caller must hold RTNL.
1554 static int fn_trie_delete(struct fib_table
*tb
, struct fib_config
*cfg
)
1556 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1558 int plen
= cfg
->fc_dst_len
;
1559 u8 tos
= cfg
->fc_tos
;
1560 struct fib_alias
*fa
, *fa_to_delete
;
1561 struct list_head
*fa_head
;
1563 struct leaf_info
*li
;
1568 key
= ntohl(cfg
->fc_dst
);
1569 mask
= ntohl(inet_make_mask(plen
));
1575 l
= fib_find_node(t
, key
);
1580 fa_head
= get_fa_head(l
, plen
);
1581 fa
= fib_find_alias(fa_head
, tos
, 0);
1586 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key
, plen
, tos
, t
);
1588 fa_to_delete
= NULL
;
1589 fa_head
= fa
->fa_list
.prev
;
1591 list_for_each_entry(fa
, fa_head
, fa_list
) {
1592 struct fib_info
*fi
= fa
->fa_info
;
1594 if (fa
->fa_tos
!= tos
)
1597 if ((!cfg
->fc_type
|| fa
->fa_type
== cfg
->fc_type
) &&
1598 (cfg
->fc_scope
== RT_SCOPE_NOWHERE
||
1599 fa
->fa_scope
== cfg
->fc_scope
) &&
1600 (!cfg
->fc_protocol
||
1601 fi
->fib_protocol
== cfg
->fc_protocol
) &&
1602 fib_nh_match(cfg
, fi
) == 0) {
1612 rtmsg_fib(RTM_DELROUTE
, htonl(key
), fa
, plen
, tb
->tb_id
,
1613 &cfg
->fc_nlinfo
, 0);
1615 l
= fib_find_node(t
, key
);
1616 li
= find_leaf_info(l
, plen
);
1618 list_del_rcu(&fa
->fa_list
);
1620 if (list_empty(fa_head
)) {
1621 hlist_del_rcu(&li
->hlist
);
1625 if (hlist_empty(&l
->list
))
1626 trie_leaf_remove(t
, key
);
1628 if (fa
->fa_state
& FA_S_ACCESSED
)
1631 fib_release_info(fa
->fa_info
);
1632 alias_free_mem_rcu(fa
);
1636 static int trie_flush_list(struct trie
*t
, struct list_head
*head
)
1638 struct fib_alias
*fa
, *fa_node
;
1641 list_for_each_entry_safe(fa
, fa_node
, head
, fa_list
) {
1642 struct fib_info
*fi
= fa
->fa_info
;
1644 if (fi
&& (fi
->fib_flags
& RTNH_F_DEAD
)) {
1645 list_del_rcu(&fa
->fa_list
);
1646 fib_release_info(fa
->fa_info
);
1647 alias_free_mem_rcu(fa
);
1654 static int trie_flush_leaf(struct trie
*t
, struct leaf
*l
)
1657 struct hlist_head
*lih
= &l
->list
;
1658 struct hlist_node
*node
, *tmp
;
1659 struct leaf_info
*li
= NULL
;
1661 hlist_for_each_entry_safe(li
, node
, tmp
, lih
, hlist
) {
1662 found
+= trie_flush_list(t
, &li
->falh
);
1664 if (list_empty(&li
->falh
)) {
1665 hlist_del_rcu(&li
->hlist
);
1672 /* rcu_read_lock needs to be hold by caller from readside */
1674 static struct leaf
*nextleaf(struct trie
*t
, struct leaf
*thisleaf
)
1676 struct node
*c
= (struct node
*) thisleaf
;
1679 struct node
*trie
= rcu_dereference(t
->trie
);
1685 if (IS_LEAF(trie
)) /* trie w. just a leaf */
1686 return (struct leaf
*) trie
;
1688 p
= (struct tnode
*) trie
; /* Start */
1695 /* Find the next child of the parent */
1697 pos
= 1 + tkey_extract_bits(c
->key
, p
->pos
, p
->bits
);
1701 last
= 1 << p
->bits
;
1702 for (idx
= pos
; idx
< last
; idx
++) {
1703 c
= rcu_dereference(p
->child
[idx
]);
1708 /* Decend if tnode */
1709 while (IS_TNODE(c
)) {
1710 p
= (struct tnode
*) c
;
1713 /* Rightmost non-NULL branch */
1714 if (p
&& IS_TNODE(p
))
1715 while (!(c
= rcu_dereference(p
->child
[idx
]))
1716 && idx
< (1<<p
->bits
)) idx
++;
1718 /* Done with this tnode? */
1719 if (idx
>= (1 << p
->bits
) || !c
)
1722 return (struct leaf
*) c
;
1725 /* No more children go up one step */
1726 c
= (struct node
*) p
;
1729 return NULL
; /* Ready. Root of trie */
1733 * Caller must hold RTNL.
1735 static int fn_trie_flush(struct fib_table
*tb
)
1737 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1738 struct leaf
*ll
= NULL
, *l
= NULL
;
1741 for (h
= 0; (l
= nextleaf(t
, l
)) != NULL
; h
++) {
1742 found
+= trie_flush_leaf(t
, l
);
1744 if (ll
&& hlist_empty(&ll
->list
))
1745 trie_leaf_remove(t
, ll
->key
);
1749 if (ll
&& hlist_empty(&ll
->list
))
1750 trie_leaf_remove(t
, ll
->key
);
1752 pr_debug("trie_flush found=%d\n", found
);
1757 fn_trie_select_default(struct fib_table
*tb
, const struct flowi
*flp
, struct fib_result
*res
)
1759 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1760 int order
, last_idx
;
1761 struct fib_info
*fi
= NULL
;
1762 struct fib_info
*last_resort
;
1763 struct fib_alias
*fa
= NULL
;
1764 struct list_head
*fa_head
;
1773 l
= fib_find_node(t
, 0);
1777 fa_head
= get_fa_head(l
, 0);
1781 if (list_empty(fa_head
))
1784 list_for_each_entry_rcu(fa
, fa_head
, fa_list
) {
1785 struct fib_info
*next_fi
= fa
->fa_info
;
1787 if (fa
->fa_scope
!= res
->scope
||
1788 fa
->fa_type
!= RTN_UNICAST
)
1791 if (next_fi
->fib_priority
> res
->fi
->fib_priority
)
1793 if (!next_fi
->fib_nh
[0].nh_gw
||
1794 next_fi
->fib_nh
[0].nh_scope
!= RT_SCOPE_LINK
)
1796 fa
->fa_state
|= FA_S_ACCESSED
;
1799 if (next_fi
!= res
->fi
)
1801 } else if (!fib_detect_death(fi
, order
, &last_resort
,
1802 &last_idx
, tb
->tb_default
)) {
1803 fib_result_assign(res
, fi
);
1804 tb
->tb_default
= order
;
1810 if (order
<= 0 || fi
== NULL
) {
1811 tb
->tb_default
= -1;
1815 if (!fib_detect_death(fi
, order
, &last_resort
, &last_idx
,
1817 fib_result_assign(res
, fi
);
1818 tb
->tb_default
= order
;
1822 fib_result_assign(res
, last_resort
);
1823 tb
->tb_default
= last_idx
;
1828 static int fn_trie_dump_fa(t_key key
, int plen
, struct list_head
*fah
, struct fib_table
*tb
,
1829 struct sk_buff
*skb
, struct netlink_callback
*cb
)
1832 struct fib_alias
*fa
;
1834 __be32 xkey
= htonl(key
);
1839 /* rcu_read_lock is hold by caller */
1841 list_for_each_entry_rcu(fa
, fah
, fa_list
) {
1846 BUG_ON(!fa
->fa_info
);
1848 if (fib_dump_info(skb
, NETLINK_CB(cb
->skb
).pid
,
1857 fa
->fa_info
, 0) < 0) {
1867 static int fn_trie_dump_plen(struct trie
*t
, int plen
, struct fib_table
*tb
, struct sk_buff
*skb
,
1868 struct netlink_callback
*cb
)
1871 struct list_head
*fa_head
;
1872 struct leaf
*l
= NULL
;
1876 for (h
= 0; (l
= nextleaf(t
, l
)) != NULL
; h
++) {
1880 memset(&cb
->args
[4], 0,
1881 sizeof(cb
->args
) - 4*sizeof(cb
->args
[0]));
1883 fa_head
= get_fa_head(l
, plen
);
1888 if (list_empty(fa_head
))
1891 if (fn_trie_dump_fa(l
->key
, plen
, fa_head
, tb
, skb
, cb
)<0) {
1900 static int fn_trie_dump(struct fib_table
*tb
, struct sk_buff
*skb
, struct netlink_callback
*cb
)
1903 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1908 for (m
= 0; m
<= 32; m
++) {
1912 memset(&cb
->args
[3], 0,
1913 sizeof(cb
->args
) - 3*sizeof(cb
->args
[0]));
1915 if (fn_trie_dump_plen(t
, 32-m
, tb
, skb
, cb
)<0) {
1928 /* Fix more generic FIB names for init later */
1930 struct fib_table
*fib_hash_init(u32 id
)
1932 struct fib_table
*tb
;
1935 if (fn_alias_kmem
== NULL
)
1936 fn_alias_kmem
= kmem_cache_create("ip_fib_alias",
1937 sizeof(struct fib_alias
),
1938 0, SLAB_HWCACHE_ALIGN
,
1941 tb
= kmalloc(sizeof(struct fib_table
) + sizeof(struct trie
),
1947 tb
->tb_default
= -1;
1948 tb
->tb_lookup
= fn_trie_lookup
;
1949 tb
->tb_insert
= fn_trie_insert
;
1950 tb
->tb_delete
= fn_trie_delete
;
1951 tb
->tb_flush
= fn_trie_flush
;
1952 tb
->tb_select_default
= fn_trie_select_default
;
1953 tb
->tb_dump
= fn_trie_dump
;
1955 t
= (struct trie
*) tb
->tb_data
;
1956 memset(t
, 0, sizeof(*t
));
1958 if (id
== RT_TABLE_LOCAL
)
1959 printk(KERN_INFO
"IPv4 FIB: Using LC-trie version %s\n", VERSION
);
1964 #ifdef CONFIG_PROC_FS
1965 /* Depth first Trie walk iterator */
1966 struct fib_trie_iter
{
1967 struct seq_net_private p
;
1968 struct trie
*trie_local
, *trie_main
;
1969 struct tnode
*tnode
;
1975 static struct node
*fib_trie_get_next(struct fib_trie_iter
*iter
)
1977 struct tnode
*tn
= iter
->tnode
;
1978 unsigned cindex
= iter
->index
;
1981 /* A single entry routing table */
1985 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
1986 iter
->tnode
, iter
->index
, iter
->depth
);
1988 while (cindex
< (1<<tn
->bits
)) {
1989 struct node
*n
= tnode_get_child(tn
, cindex
);
1994 iter
->index
= cindex
+ 1;
1996 /* push down one level */
1997 iter
->tnode
= (struct tnode
*) n
;
2007 /* Current node exhausted, pop back up */
2008 p
= node_parent((struct node
*)tn
);
2010 cindex
= tkey_extract_bits(tn
->key
, p
->pos
, p
->bits
)+1;
2020 static struct node
*fib_trie_get_first(struct fib_trie_iter
*iter
,
2028 n
= rcu_dereference(t
->trie
);
2035 iter
->tnode
= (struct tnode
*) n
;
2050 static void trie_collect_stats(struct trie
*t
, struct trie_stat
*s
)
2053 struct fib_trie_iter iter
;
2055 memset(s
, 0, sizeof(*s
));
2058 for (n
= fib_trie_get_first(&iter
, t
); n
;
2059 n
= fib_trie_get_next(&iter
)) {
2062 s
->totdepth
+= iter
.depth
;
2063 if (iter
.depth
> s
->maxdepth
)
2064 s
->maxdepth
= iter
.depth
;
2066 const struct tnode
*tn
= (const struct tnode
*) n
;
2070 if (tn
->bits
< MAX_STAT_DEPTH
)
2071 s
->nodesizes
[tn
->bits
]++;
2073 for (i
= 0; i
< (1<<tn
->bits
); i
++)
2082 * This outputs /proc/net/fib_triestats
2084 static void trie_show_stats(struct seq_file
*seq
, struct trie_stat
*stat
)
2086 unsigned i
, max
, pointers
, bytes
, avdepth
;
2089 avdepth
= stat
->totdepth
*100 / stat
->leaves
;
2093 seq_printf(seq
, "\tAver depth: %u.%02d\n", avdepth
/ 100, avdepth
% 100 );
2094 seq_printf(seq
, "\tMax depth: %u\n", stat
->maxdepth
);
2096 seq_printf(seq
, "\tLeaves: %u\n", stat
->leaves
);
2098 bytes
= sizeof(struct leaf
) * stat
->leaves
;
2099 seq_printf(seq
, "\tInternal nodes: %u\n\t", stat
->tnodes
);
2100 bytes
+= sizeof(struct tnode
) * stat
->tnodes
;
2102 max
= MAX_STAT_DEPTH
;
2103 while (max
> 0 && stat
->nodesizes
[max
-1] == 0)
2107 for (i
= 1; i
<= max
; i
++)
2108 if (stat
->nodesizes
[i
] != 0) {
2109 seq_printf(seq
, " %u: %u", i
, stat
->nodesizes
[i
]);
2110 pointers
+= (1<<i
) * stat
->nodesizes
[i
];
2112 seq_putc(seq
, '\n');
2113 seq_printf(seq
, "\tPointers: %u\n", pointers
);
2115 bytes
+= sizeof(struct node
*) * pointers
;
2116 seq_printf(seq
, "Null ptrs: %u\n", stat
->nullpointers
);
2117 seq_printf(seq
, "Total size: %u kB\n", (bytes
+ 1023) / 1024);
2120 #ifdef CONFIG_IP_FIB_TRIE_STATS
2121 static void trie_show_usage(struct seq_file
*seq
,
2122 const struct trie_use_stats
*stats
)
2124 seq_printf(seq
, "\nCounters:\n---------\n");
2125 seq_printf(seq
,"gets = %u\n", stats
->gets
);
2126 seq_printf(seq
,"backtracks = %u\n", stats
->backtrack
);
2127 seq_printf(seq
,"semantic match passed = %u\n", stats
->semantic_match_passed
);
2128 seq_printf(seq
,"semantic match miss = %u\n", stats
->semantic_match_miss
);
2129 seq_printf(seq
,"null node hit= %u\n", stats
->null_node_hit
);
2130 seq_printf(seq
,"skipped node resize = %u\n\n", stats
->resize_node_skipped
);
2132 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2135 static int fib_triestat_seq_show(struct seq_file
*seq
, void *v
)
2137 struct net
*net
= (struct net
*)seq
->private;
2138 struct trie
*trie_local
, *trie_main
;
2139 struct trie_stat
*stat
;
2140 struct fib_table
*tb
;
2143 tb
= fib_get_table(net
, RT_TABLE_LOCAL
);
2145 trie_local
= (struct trie
*) tb
->tb_data
;
2148 tb
= fib_get_table(net
, RT_TABLE_MAIN
);
2150 trie_main
= (struct trie
*) tb
->tb_data
;
2153 stat
= kmalloc(sizeof(*stat
), GFP_KERNEL
);
2157 seq_printf(seq
, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
2158 sizeof(struct leaf
), sizeof(struct tnode
));
2161 seq_printf(seq
, "Local:\n");
2162 trie_collect_stats(trie_local
, stat
);
2163 trie_show_stats(seq
, stat
);
2164 #ifdef CONFIG_IP_FIB_TRIE_STATS
2165 trie_show_usage(seq
, &trie_local
->stats
);
2170 seq_printf(seq
, "Main:\n");
2171 trie_collect_stats(trie_main
, stat
);
2172 trie_show_stats(seq
, stat
);
2173 #ifdef CONFIG_IP_FIB_TRIE_STATS
2174 trie_show_usage(seq
, &trie_main
->stats
);
2182 static int fib_triestat_seq_open(struct inode
*inode
, struct file
*file
)
2187 net
= get_proc_net(inode
);
2190 err
= single_open(file
, fib_triestat_seq_show
, net
);
2198 static int fib_triestat_seq_release(struct inode
*ino
, struct file
*f
)
2200 struct seq_file
*seq
= f
->private_data
;
2201 put_net(seq
->private);
2202 return single_release(ino
, f
);
2205 static const struct file_operations fib_triestat_fops
= {
2206 .owner
= THIS_MODULE
,
2207 .open
= fib_triestat_seq_open
,
2209 .llseek
= seq_lseek
,
2210 .release
= fib_triestat_seq_release
,
2213 static struct node
*fib_trie_get_idx(struct fib_trie_iter
*iter
,
2219 for (n
= fib_trie_get_first(iter
, iter
->trie_local
);
2220 n
; ++idx
, n
= fib_trie_get_next(iter
)) {
2225 for (n
= fib_trie_get_first(iter
, iter
->trie_main
);
2226 n
; ++idx
, n
= fib_trie_get_next(iter
)) {
2233 static void *fib_trie_seq_start(struct seq_file
*seq
, loff_t
*pos
)
2236 struct fib_trie_iter
*iter
= seq
->private;
2237 struct fib_table
*tb
;
2239 if (!iter
->trie_local
) {
2240 tb
= fib_get_table(iter
->p
.net
, RT_TABLE_LOCAL
);
2242 iter
->trie_local
= (struct trie
*) tb
->tb_data
;
2244 if (!iter
->trie_main
) {
2245 tb
= fib_get_table(iter
->p
.net
, RT_TABLE_MAIN
);
2247 iter
->trie_main
= (struct trie
*) tb
->tb_data
;
2251 return SEQ_START_TOKEN
;
2252 return fib_trie_get_idx(iter
, *pos
- 1);
2255 static void *fib_trie_seq_next(struct seq_file
*seq
, void *v
, loff_t
*pos
)
2257 struct fib_trie_iter
*iter
= seq
->private;
2261 if (v
== SEQ_START_TOKEN
)
2262 return fib_trie_get_idx(iter
, 0);
2264 v
= fib_trie_get_next(iter
);
2269 /* continue scan in next trie */
2270 if (iter
->trie
== iter
->trie_local
)
2271 return fib_trie_get_first(iter
, iter
->trie_main
);
2276 static void fib_trie_seq_stop(struct seq_file
*seq
, void *v
)
2282 static void seq_indent(struct seq_file
*seq
, int n
)
2284 while (n
-- > 0) seq_puts(seq
, " ");
2287 static inline const char *rtn_scope(enum rt_scope_t s
)
2289 static char buf
[32];
2292 case RT_SCOPE_UNIVERSE
: return "universe";
2293 case RT_SCOPE_SITE
: return "site";
2294 case RT_SCOPE_LINK
: return "link";
2295 case RT_SCOPE_HOST
: return "host";
2296 case RT_SCOPE_NOWHERE
: return "nowhere";
2298 snprintf(buf
, sizeof(buf
), "scope=%d", s
);
2303 static const char *rtn_type_names
[__RTN_MAX
] = {
2304 [RTN_UNSPEC
] = "UNSPEC",
2305 [RTN_UNICAST
] = "UNICAST",
2306 [RTN_LOCAL
] = "LOCAL",
2307 [RTN_BROADCAST
] = "BROADCAST",
2308 [RTN_ANYCAST
] = "ANYCAST",
2309 [RTN_MULTICAST
] = "MULTICAST",
2310 [RTN_BLACKHOLE
] = "BLACKHOLE",
2311 [RTN_UNREACHABLE
] = "UNREACHABLE",
2312 [RTN_PROHIBIT
] = "PROHIBIT",
2313 [RTN_THROW
] = "THROW",
2315 [RTN_XRESOLVE
] = "XRESOLVE",
2318 static inline const char *rtn_type(unsigned t
)
2320 static char buf
[32];
2322 if (t
< __RTN_MAX
&& rtn_type_names
[t
])
2323 return rtn_type_names
[t
];
2324 snprintf(buf
, sizeof(buf
), "type %u", t
);
2328 /* Pretty print the trie */
2329 static int fib_trie_seq_show(struct seq_file
*seq
, void *v
)
2331 const struct fib_trie_iter
*iter
= seq
->private;
2334 if (v
== SEQ_START_TOKEN
)
2337 if (!node_parent(n
)) {
2338 if (iter
->trie
== iter
->trie_local
)
2339 seq_puts(seq
, "<local>:\n");
2341 seq_puts(seq
, "<main>:\n");
2345 struct tnode
*tn
= (struct tnode
*) n
;
2346 __be32 prf
= htonl(mask_pfx(tn
->key
, tn
->pos
));
2348 seq_indent(seq
, iter
->depth
-1);
2349 seq_printf(seq
, " +-- %d.%d.%d.%d/%d %d %d %d\n",
2350 NIPQUAD(prf
), tn
->pos
, tn
->bits
, tn
->full_children
,
2351 tn
->empty_children
);
2354 struct leaf
*l
= (struct leaf
*) n
;
2356 __be32 val
= htonl(l
->key
);
2358 seq_indent(seq
, iter
->depth
);
2359 seq_printf(seq
, " |-- %d.%d.%d.%d\n", NIPQUAD(val
));
2360 for (i
= 32; i
>= 0; i
--) {
2361 struct leaf_info
*li
= find_leaf_info(l
, i
);
2363 struct fib_alias
*fa
;
2364 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
2365 seq_indent(seq
, iter
->depth
+1);
2366 seq_printf(seq
, " /%d %s %s", i
,
2367 rtn_scope(fa
->fa_scope
),
2368 rtn_type(fa
->fa_type
));
2370 seq_printf(seq
, "tos =%d\n",
2372 seq_putc(seq
, '\n');
2381 static const struct seq_operations fib_trie_seq_ops
= {
2382 .start
= fib_trie_seq_start
,
2383 .next
= fib_trie_seq_next
,
2384 .stop
= fib_trie_seq_stop
,
2385 .show
= fib_trie_seq_show
,
2388 static int fib_trie_seq_open(struct inode
*inode
, struct file
*file
)
2390 return seq_open_net(inode
, file
, &fib_trie_seq_ops
,
2391 sizeof(struct fib_trie_iter
));
2394 static const struct file_operations fib_trie_fops
= {
2395 .owner
= THIS_MODULE
,
2396 .open
= fib_trie_seq_open
,
2398 .llseek
= seq_lseek
,
2399 .release
= seq_release_net
,
2402 static unsigned fib_flag_trans(int type
, __be32 mask
, const struct fib_info
*fi
)
2404 static unsigned type2flags
[RTN_MAX
+ 1] = {
2405 [7] = RTF_REJECT
, [8] = RTF_REJECT
,
2407 unsigned flags
= type2flags
[type
];
2409 if (fi
&& fi
->fib_nh
->nh_gw
)
2410 flags
|= RTF_GATEWAY
;
2411 if (mask
== htonl(0xFFFFFFFF))
2418 * This outputs /proc/net/route.
2419 * The format of the file is not supposed to be changed
2420 * and needs to be same as fib_hash output to avoid breaking
2423 static int fib_route_seq_show(struct seq_file
*seq
, void *v
)
2425 const struct fib_trie_iter
*iter
= seq
->private;
2430 if (v
== SEQ_START_TOKEN
) {
2431 seq_printf(seq
, "%-127s\n", "Iface\tDestination\tGateway "
2432 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2437 if (iter
->trie
== iter
->trie_local
)
2442 for (i
=32; i
>=0; i
--) {
2443 struct leaf_info
*li
= find_leaf_info(l
, i
);
2444 struct fib_alias
*fa
;
2445 __be32 mask
, prefix
;
2450 mask
= inet_make_mask(li
->plen
);
2451 prefix
= htonl(l
->key
);
2453 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
2454 const struct fib_info
*fi
= fa
->fa_info
;
2455 unsigned flags
= fib_flag_trans(fa
->fa_type
, mask
, fi
);
2457 if (fa
->fa_type
== RTN_BROADCAST
2458 || fa
->fa_type
== RTN_MULTICAST
)
2462 snprintf(bf
, sizeof(bf
),
2463 "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2464 fi
->fib_dev
? fi
->fib_dev
->name
: "*",
2466 fi
->fib_nh
->nh_gw
, flags
, 0, 0,
2469 (fi
->fib_advmss
? fi
->fib_advmss
+ 40 : 0),
2473 snprintf(bf
, sizeof(bf
),
2474 "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2475 prefix
, 0, flags
, 0, 0, 0,
2478 seq_printf(seq
, "%-127s\n", bf
);
2485 static const struct seq_operations fib_route_seq_ops
= {
2486 .start
= fib_trie_seq_start
,
2487 .next
= fib_trie_seq_next
,
2488 .stop
= fib_trie_seq_stop
,
2489 .show
= fib_route_seq_show
,
2492 static int fib_route_seq_open(struct inode
*inode
, struct file
*file
)
2494 return seq_open_net(inode
, file
, &fib_route_seq_ops
,
2495 sizeof(struct fib_trie_iter
));
2498 static const struct file_operations fib_route_fops
= {
2499 .owner
= THIS_MODULE
,
2500 .open
= fib_route_seq_open
,
2502 .llseek
= seq_lseek
,
2503 .release
= seq_release_net
,
2506 int __net_init
fib_proc_init(struct net
*net
)
2508 if (!proc_net_fops_create(net
, "fib_trie", S_IRUGO
, &fib_trie_fops
))
2511 if (!proc_net_fops_create(net
, "fib_triestat", S_IRUGO
,
2512 &fib_triestat_fops
))
2515 if (!proc_net_fops_create(net
, "route", S_IRUGO
, &fib_route_fops
))
2521 proc_net_remove(net
, "fib_triestat");
2523 proc_net_remove(net
, "fib_trie");
2528 void __net_exit
fib_proc_exit(struct net
*net
)
2530 proc_net_remove(net
, "fib_trie");
2531 proc_net_remove(net
, "fib_triestat");
2532 proc_net_remove(net
, "route");
2535 #endif /* CONFIG_PROC_FS */