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 prefixes
;
147 unsigned int nodesizes
[MAX_STAT_DEPTH
];
152 #ifdef CONFIG_IP_FIB_TRIE_STATS
153 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
,
160 static struct node
*resize(struct trie
*t
, struct tnode
*tn
);
161 static struct tnode
*inflate(struct trie
*t
, struct tnode
*tn
);
162 static struct tnode
*halve(struct trie
*t
, struct tnode
*tn
);
163 static void tnode_free(struct tnode
*tn
);
165 static struct kmem_cache
*fn_alias_kmem __read_mostly
;
166 static struct kmem_cache
*trie_leaf_kmem __read_mostly
;
168 static inline struct tnode
*node_parent(struct node
*node
)
170 return (struct tnode
*)(node
->parent
& ~NODE_TYPE_MASK
);
173 static inline struct tnode
*node_parent_rcu(struct node
*node
)
175 struct tnode
*ret
= node_parent(node
);
177 return rcu_dereference(ret
);
180 static inline void node_set_parent(struct node
*node
, struct tnode
*ptr
)
182 rcu_assign_pointer(node
->parent
,
183 (unsigned long)ptr
| NODE_TYPE(node
));
186 static inline struct node
*tnode_get_child(struct tnode
*tn
, unsigned int i
)
188 BUG_ON(i
>= 1U << tn
->bits
);
193 static inline struct node
*tnode_get_child_rcu(struct tnode
*tn
, unsigned int i
)
195 struct node
*ret
= tnode_get_child(tn
, i
);
197 return rcu_dereference(ret
);
200 static inline int tnode_child_length(const struct tnode
*tn
)
202 return 1 << tn
->bits
;
205 static inline t_key
mask_pfx(t_key k
, unsigned short l
)
207 return (l
== 0) ? 0 : k
>> (KEYLENGTH
-l
) << (KEYLENGTH
-l
);
210 static inline t_key
tkey_extract_bits(t_key a
, int offset
, int bits
)
212 if (offset
< KEYLENGTH
)
213 return ((t_key
)(a
<< offset
)) >> (KEYLENGTH
- bits
);
218 static inline int tkey_equals(t_key a
, t_key b
)
223 static inline int tkey_sub_equals(t_key a
, int offset
, int bits
, t_key b
)
225 if (bits
== 0 || offset
>= KEYLENGTH
)
227 bits
= bits
> KEYLENGTH
? KEYLENGTH
: bits
;
228 return ((a
^ b
) << offset
) >> (KEYLENGTH
- bits
) == 0;
231 static inline int tkey_mismatch(t_key a
, int offset
, t_key b
)
238 while ((diff
<< i
) >> (KEYLENGTH
-1) == 0)
244 To understand this stuff, an understanding of keys and all their bits is
245 necessary. Every node in the trie has a key associated with it, but not
246 all of the bits in that key are significant.
248 Consider a node 'n' and its parent 'tp'.
250 If n is a leaf, every bit in its key is significant. Its presence is
251 necessitated by path compression, since during a tree traversal (when
252 searching for a leaf - unless we are doing an insertion) we will completely
253 ignore all skipped bits we encounter. Thus we need to verify, at the end of
254 a potentially successful search, that we have indeed been walking the
257 Note that we can never "miss" the correct key in the tree if present by
258 following the wrong path. Path compression ensures that segments of the key
259 that are the same for all keys with a given prefix are skipped, but the
260 skipped part *is* identical for each node in the subtrie below the skipped
261 bit! trie_insert() in this implementation takes care of that - note the
262 call to tkey_sub_equals() in trie_insert().
264 if n is an internal node - a 'tnode' here, the various parts of its key
265 have many different meanings.
268 _________________________________________________________________
269 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
270 -----------------------------------------------------------------
271 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
273 _________________________________________________________________
274 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
275 -----------------------------------------------------------------
276 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
283 First, let's just ignore the bits that come before the parent tp, that is
284 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
285 not use them for anything.
287 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
288 index into the parent's child array. That is, they will be used to find
289 'n' among tp's children.
291 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
294 All the bits we have seen so far are significant to the node n. The rest
295 of the bits are really not needed or indeed known in n->key.
297 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
298 n's child array, and will of course be different for each child.
301 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
306 static inline void check_tnode(const struct tnode
*tn
)
308 WARN_ON(tn
&& tn
->pos
+tn
->bits
> 32);
311 static const int halve_threshold
= 25;
312 static const int inflate_threshold
= 50;
313 static const int halve_threshold_root
= 8;
314 static const int inflate_threshold_root
= 15;
317 static void __alias_free_mem(struct rcu_head
*head
)
319 struct fib_alias
*fa
= container_of(head
, struct fib_alias
, rcu
);
320 kmem_cache_free(fn_alias_kmem
, fa
);
323 static inline void alias_free_mem_rcu(struct fib_alias
*fa
)
325 call_rcu(&fa
->rcu
, __alias_free_mem
);
328 static void __leaf_free_rcu(struct rcu_head
*head
)
330 struct leaf
*l
= container_of(head
, struct leaf
, rcu
);
331 kmem_cache_free(trie_leaf_kmem
, l
);
334 static void __leaf_info_free_rcu(struct rcu_head
*head
)
336 kfree(container_of(head
, struct leaf_info
, rcu
));
339 static inline void free_leaf_info(struct leaf_info
*leaf
)
341 call_rcu(&leaf
->rcu
, __leaf_info_free_rcu
);
344 static struct tnode
*tnode_alloc(size_t size
)
348 if (size
<= PAGE_SIZE
)
349 return kzalloc(size
, GFP_KERNEL
);
351 pages
= alloc_pages(GFP_KERNEL
|__GFP_ZERO
, get_order(size
));
355 return page_address(pages
);
358 static void __tnode_free_rcu(struct rcu_head
*head
)
360 struct tnode
*tn
= container_of(head
, struct tnode
, rcu
);
361 size_t size
= sizeof(struct tnode
) +
362 (sizeof(struct node
*) << tn
->bits
);
364 if (size
<= PAGE_SIZE
)
367 free_pages((unsigned long)tn
, get_order(size
));
370 static inline void tnode_free(struct tnode
*tn
)
373 struct leaf
*l
= (struct leaf
*) tn
;
374 call_rcu_bh(&l
->rcu
, __leaf_free_rcu
);
376 call_rcu(&tn
->rcu
, __tnode_free_rcu
);
379 static struct leaf
*leaf_new(void)
381 struct leaf
*l
= kmem_cache_alloc(trie_leaf_kmem
, GFP_KERNEL
);
384 INIT_HLIST_HEAD(&l
->list
);
389 static struct leaf_info
*leaf_info_new(int plen
)
391 struct leaf_info
*li
= kmalloc(sizeof(struct leaf_info
), GFP_KERNEL
);
394 INIT_LIST_HEAD(&li
->falh
);
399 static struct tnode
*tnode_new(t_key key
, int pos
, int bits
)
401 size_t sz
= sizeof(struct tnode
) + (sizeof(struct node
*) << bits
);
402 struct tnode
*tn
= tnode_alloc(sz
);
405 tn
->parent
= T_TNODE
;
409 tn
->full_children
= 0;
410 tn
->empty_children
= 1<<bits
;
413 pr_debug("AT %p s=%u %lu\n", tn
, (unsigned int) sizeof(struct tnode
),
414 (unsigned long) (sizeof(struct node
) << bits
));
419 * Check whether a tnode 'n' is "full", i.e. it is an internal node
420 * and no bits are skipped. See discussion in dyntree paper p. 6
423 static inline int tnode_full(const struct tnode
*tn
, const struct node
*n
)
425 if (n
== NULL
|| IS_LEAF(n
))
428 return ((struct tnode
*) n
)->pos
== tn
->pos
+ tn
->bits
;
431 static inline void put_child(struct trie
*t
, struct tnode
*tn
, int i
,
434 tnode_put_child_reorg(tn
, i
, n
, -1);
438 * Add a child at position i overwriting the old value.
439 * Update the value of full_children and empty_children.
442 static void tnode_put_child_reorg(struct tnode
*tn
, int i
, struct node
*n
,
445 struct node
*chi
= tn
->child
[i
];
448 BUG_ON(i
>= 1<<tn
->bits
);
450 /* update emptyChildren */
451 if (n
== NULL
&& chi
!= NULL
)
452 tn
->empty_children
++;
453 else if (n
!= NULL
&& chi
== NULL
)
454 tn
->empty_children
--;
456 /* update fullChildren */
458 wasfull
= tnode_full(tn
, chi
);
460 isfull
= tnode_full(tn
, n
);
461 if (wasfull
&& !isfull
)
463 else if (!wasfull
&& isfull
)
467 node_set_parent(n
, tn
);
469 rcu_assign_pointer(tn
->child
[i
], n
);
472 static struct node
*resize(struct trie
*t
, struct tnode
*tn
)
476 struct tnode
*old_tn
;
477 int inflate_threshold_use
;
478 int halve_threshold_use
;
484 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
485 tn
, inflate_threshold
, halve_threshold
);
488 if (tn
->empty_children
== tnode_child_length(tn
)) {
493 if (tn
->empty_children
== tnode_child_length(tn
) - 1)
494 for (i
= 0; i
< tnode_child_length(tn
); i
++) {
501 /* compress one level */
502 node_set_parent(n
, NULL
);
507 * Double as long as the resulting node has a number of
508 * nonempty nodes that are above the threshold.
512 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
513 * the Helsinki University of Technology and Matti Tikkanen of Nokia
514 * Telecommunications, page 6:
515 * "A node is doubled if the ratio of non-empty children to all
516 * children in the *doubled* node is at least 'high'."
518 * 'high' in this instance is the variable 'inflate_threshold'. It
519 * is expressed as a percentage, so we multiply it with
520 * tnode_child_length() and instead of multiplying by 2 (since the
521 * child array will be doubled by inflate()) and multiplying
522 * the left-hand side by 100 (to handle the percentage thing) we
523 * multiply the left-hand side by 50.
525 * The left-hand side may look a bit weird: tnode_child_length(tn)
526 * - tn->empty_children is of course the number of non-null children
527 * in the current node. tn->full_children is the number of "full"
528 * children, that is non-null tnodes with a skip value of 0.
529 * All of those will be doubled in the resulting inflated tnode, so
530 * we just count them one extra time here.
532 * A clearer way to write this would be:
534 * to_be_doubled = tn->full_children;
535 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
538 * new_child_length = tnode_child_length(tn) * 2;
540 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
542 * if (new_fill_factor >= inflate_threshold)
544 * ...and so on, tho it would mess up the while () loop.
547 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
551 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
552 * inflate_threshold * new_child_length
554 * expand not_to_be_doubled and to_be_doubled, and shorten:
555 * 100 * (tnode_child_length(tn) - tn->empty_children +
556 * tn->full_children) >= inflate_threshold * new_child_length
558 * expand new_child_length:
559 * 100 * (tnode_child_length(tn) - tn->empty_children +
560 * tn->full_children) >=
561 * inflate_threshold * tnode_child_length(tn) * 2
564 * 50 * (tn->full_children + tnode_child_length(tn) -
565 * tn->empty_children) >= inflate_threshold *
566 * tnode_child_length(tn)
572 /* Keep root node larger */
575 inflate_threshold_use
= inflate_threshold_root
;
577 inflate_threshold_use
= inflate_threshold
;
581 while ((tn
->full_children
> 0 && max_resize
-- &&
582 50 * (tn
->full_children
+ tnode_child_length(tn
)
583 - tn
->empty_children
)
584 >= inflate_threshold_use
* tnode_child_length(tn
))) {
591 #ifdef CONFIG_IP_FIB_TRIE_STATS
592 t
->stats
.resize_node_skipped
++;
598 if (max_resize
< 0) {
600 pr_warning("Fix inflate_threshold_root."
601 " Now=%d size=%d bits\n",
602 inflate_threshold_root
, tn
->bits
);
604 pr_warning("Fix inflate_threshold."
605 " Now=%d size=%d bits\n",
606 inflate_threshold
, tn
->bits
);
612 * Halve as long as the number of empty children in this
613 * node is above threshold.
617 /* Keep root node larger */
620 halve_threshold_use
= halve_threshold_root
;
622 halve_threshold_use
= halve_threshold
;
626 while (tn
->bits
> 1 && max_resize
-- &&
627 100 * (tnode_child_length(tn
) - tn
->empty_children
) <
628 halve_threshold_use
* tnode_child_length(tn
)) {
634 #ifdef CONFIG_IP_FIB_TRIE_STATS
635 t
->stats
.resize_node_skipped
++;
641 if (max_resize
< 0) {
643 pr_warning("Fix halve_threshold_root."
644 " Now=%d size=%d bits\n",
645 halve_threshold_root
, tn
->bits
);
647 pr_warning("Fix halve_threshold."
648 " Now=%d size=%d bits\n",
649 halve_threshold
, tn
->bits
);
652 /* Only one child remains */
653 if (tn
->empty_children
== tnode_child_length(tn
) - 1)
654 for (i
= 0; i
< tnode_child_length(tn
); i
++) {
661 /* compress one level */
663 node_set_parent(n
, NULL
);
668 return (struct node
*) tn
;
671 static struct tnode
*inflate(struct trie
*t
, struct tnode
*tn
)
673 struct tnode
*oldtnode
= tn
;
674 int olen
= tnode_child_length(tn
);
677 pr_debug("In inflate\n");
679 tn
= tnode_new(oldtnode
->key
, oldtnode
->pos
, oldtnode
->bits
+ 1);
682 return ERR_PTR(-ENOMEM
);
685 * Preallocate and store tnodes before the actual work so we
686 * don't get into an inconsistent state if memory allocation
687 * fails. In case of failure we return the oldnode and inflate
688 * of tnode is ignored.
691 for (i
= 0; i
< olen
; i
++) {
694 inode
= (struct tnode
*) tnode_get_child(oldtnode
, i
);
697 inode
->pos
== oldtnode
->pos
+ oldtnode
->bits
&&
699 struct tnode
*left
, *right
;
700 t_key m
= ~0U << (KEYLENGTH
- 1) >> inode
->pos
;
702 left
= tnode_new(inode
->key
&(~m
), inode
->pos
+ 1,
707 right
= tnode_new(inode
->key
|m
, inode
->pos
+ 1,
715 put_child(t
, tn
, 2*i
, (struct node
*) left
);
716 put_child(t
, tn
, 2*i
+1, (struct node
*) right
);
720 for (i
= 0; i
< olen
; i
++) {
722 struct node
*node
= tnode_get_child(oldtnode
, i
);
723 struct tnode
*left
, *right
;
730 /* A leaf or an internal node with skipped bits */
732 if (IS_LEAF(node
) || ((struct tnode
*) node
)->pos
>
733 tn
->pos
+ tn
->bits
- 1) {
734 if (tkey_extract_bits(node
->key
,
735 oldtnode
->pos
+ oldtnode
->bits
,
737 put_child(t
, tn
, 2*i
, node
);
739 put_child(t
, tn
, 2*i
+1, node
);
743 /* An internal node with two children */
744 inode
= (struct tnode
*) node
;
746 if (inode
->bits
== 1) {
747 put_child(t
, tn
, 2*i
, inode
->child
[0]);
748 put_child(t
, tn
, 2*i
+1, inode
->child
[1]);
754 /* An internal node with more than two children */
756 /* We will replace this node 'inode' with two new
757 * ones, 'left' and 'right', each with half of the
758 * original children. The two new nodes will have
759 * a position one bit further down the key and this
760 * means that the "significant" part of their keys
761 * (see the discussion near the top of this file)
762 * will differ by one bit, which will be "0" in
763 * left's key and "1" in right's key. Since we are
764 * moving the key position by one step, the bit that
765 * we are moving away from - the bit at position
766 * (inode->pos) - is the one that will differ between
767 * left and right. So... we synthesize that bit in the
769 * The mask 'm' below will be a single "one" bit at
770 * the position (inode->pos)
773 /* Use the old key, but set the new significant
777 left
= (struct tnode
*) tnode_get_child(tn
, 2*i
);
778 put_child(t
, tn
, 2*i
, NULL
);
782 right
= (struct tnode
*) tnode_get_child(tn
, 2*i
+1);
783 put_child(t
, tn
, 2*i
+1, NULL
);
787 size
= tnode_child_length(left
);
788 for (j
= 0; j
< size
; j
++) {
789 put_child(t
, left
, j
, inode
->child
[j
]);
790 put_child(t
, right
, j
, inode
->child
[j
+ size
]);
792 put_child(t
, tn
, 2*i
, resize(t
, left
));
793 put_child(t
, tn
, 2*i
+1, resize(t
, right
));
797 tnode_free(oldtnode
);
801 int size
= tnode_child_length(tn
);
804 for (j
= 0; j
< size
; j
++)
806 tnode_free((struct tnode
*)tn
->child
[j
]);
810 return ERR_PTR(-ENOMEM
);
814 static struct tnode
*halve(struct trie
*t
, struct tnode
*tn
)
816 struct tnode
*oldtnode
= tn
;
817 struct node
*left
, *right
;
819 int olen
= tnode_child_length(tn
);
821 pr_debug("In halve\n");
823 tn
= tnode_new(oldtnode
->key
, oldtnode
->pos
, oldtnode
->bits
- 1);
826 return ERR_PTR(-ENOMEM
);
829 * Preallocate and store tnodes before the actual work so we
830 * don't get into an inconsistent state if memory allocation
831 * fails. In case of failure we return the oldnode and halve
832 * of tnode is ignored.
835 for (i
= 0; i
< olen
; i
+= 2) {
836 left
= tnode_get_child(oldtnode
, i
);
837 right
= tnode_get_child(oldtnode
, i
+1);
839 /* Two nonempty children */
843 newn
= tnode_new(left
->key
, tn
->pos
+ tn
->bits
, 1);
848 put_child(t
, tn
, i
/2, (struct node
*)newn
);
853 for (i
= 0; i
< olen
; i
+= 2) {
854 struct tnode
*newBinNode
;
856 left
= tnode_get_child(oldtnode
, i
);
857 right
= tnode_get_child(oldtnode
, i
+1);
859 /* At least one of the children is empty */
861 if (right
== NULL
) /* Both are empty */
863 put_child(t
, tn
, i
/2, right
);
868 put_child(t
, tn
, i
/2, left
);
872 /* Two nonempty children */
873 newBinNode
= (struct tnode
*) tnode_get_child(tn
, i
/2);
874 put_child(t
, tn
, i
/2, NULL
);
875 put_child(t
, newBinNode
, 0, left
);
876 put_child(t
, newBinNode
, 1, right
);
877 put_child(t
, tn
, i
/2, resize(t
, newBinNode
));
879 tnode_free(oldtnode
);
883 int size
= tnode_child_length(tn
);
886 for (j
= 0; j
< size
; j
++)
888 tnode_free((struct tnode
*)tn
->child
[j
]);
892 return ERR_PTR(-ENOMEM
);
896 /* readside must use rcu_read_lock currently dump routines
897 via get_fa_head and dump */
899 static struct leaf_info
*find_leaf_info(struct leaf
*l
, int plen
)
901 struct hlist_head
*head
= &l
->list
;
902 struct hlist_node
*node
;
903 struct leaf_info
*li
;
905 hlist_for_each_entry_rcu(li
, node
, head
, hlist
)
906 if (li
->plen
== plen
)
912 static inline struct list_head
*get_fa_head(struct leaf
*l
, int plen
)
914 struct leaf_info
*li
= find_leaf_info(l
, plen
);
922 static void insert_leaf_info(struct hlist_head
*head
, struct leaf_info
*new)
924 struct leaf_info
*li
= NULL
, *last
= NULL
;
925 struct hlist_node
*node
;
927 if (hlist_empty(head
)) {
928 hlist_add_head_rcu(&new->hlist
, head
);
930 hlist_for_each_entry(li
, node
, head
, hlist
) {
931 if (new->plen
> li
->plen
)
937 hlist_add_after_rcu(&last
->hlist
, &new->hlist
);
939 hlist_add_before_rcu(&new->hlist
, &li
->hlist
);
943 /* rcu_read_lock needs to be hold by caller from readside */
946 fib_find_node(struct trie
*t
, u32 key
)
953 n
= rcu_dereference(t
->trie
);
955 while (n
!= NULL
&& NODE_TYPE(n
) == T_TNODE
) {
956 tn
= (struct tnode
*) n
;
960 if (tkey_sub_equals(tn
->key
, pos
, tn
->pos
-pos
, key
)) {
961 pos
= tn
->pos
+ tn
->bits
;
962 n
= tnode_get_child_rcu(tn
,
963 tkey_extract_bits(key
,
969 /* Case we have found a leaf. Compare prefixes */
971 if (n
!= NULL
&& IS_LEAF(n
) && tkey_equals(key
, n
->key
))
972 return (struct leaf
*)n
;
977 static struct node
*trie_rebalance(struct trie
*t
, struct tnode
*tn
)
980 t_key cindex
, key
= tn
->key
;
983 while (tn
!= NULL
&& (tp
= node_parent((struct node
*)tn
)) != NULL
) {
984 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
985 wasfull
= tnode_full(tp
, tnode_get_child(tp
, cindex
));
986 tn
= (struct tnode
*) resize(t
, (struct tnode
*)tn
);
988 tnode_put_child_reorg((struct tnode
*)tp
, cindex
,
989 (struct node
*)tn
, wasfull
);
991 tp
= node_parent((struct node
*) tn
);
997 /* Handle last (top) tnode */
999 tn
= (struct tnode
*)resize(t
, (struct tnode
*)tn
);
1001 return (struct node
*)tn
;
1004 /* only used from updater-side */
1006 static struct list_head
*fib_insert_node(struct trie
*t
, u32 key
, int plen
)
1009 struct tnode
*tp
= NULL
, *tn
= NULL
;
1013 struct list_head
*fa_head
= NULL
;
1014 struct leaf_info
*li
;
1020 /* If we point to NULL, stop. Either the tree is empty and we should
1021 * just put a new leaf in if, or we have reached an empty child slot,
1022 * and we should just put our new leaf in that.
1023 * If we point to a T_TNODE, check if it matches our key. Note that
1024 * a T_TNODE might be skipping any number of bits - its 'pos' need
1025 * not be the parent's 'pos'+'bits'!
1027 * If it does match the current key, get pos/bits from it, extract
1028 * the index from our key, push the T_TNODE and walk the tree.
1030 * If it doesn't, we have to replace it with a new T_TNODE.
1032 * If we point to a T_LEAF, it might or might not have the same key
1033 * as we do. If it does, just change the value, update the T_LEAF's
1034 * value, and return it.
1035 * If it doesn't, we need to replace it with a T_TNODE.
1038 while (n
!= NULL
&& NODE_TYPE(n
) == T_TNODE
) {
1039 tn
= (struct tnode
*) n
;
1043 if (tkey_sub_equals(tn
->key
, pos
, tn
->pos
-pos
, key
)) {
1045 pos
= tn
->pos
+ tn
->bits
;
1046 n
= tnode_get_child(tn
,
1047 tkey_extract_bits(key
,
1051 BUG_ON(n
&& node_parent(n
) != tn
);
1057 * n ----> NULL, LEAF or TNODE
1059 * tp is n's (parent) ----> NULL or TNODE
1062 BUG_ON(tp
&& IS_LEAF(tp
));
1064 /* Case 1: n is a leaf. Compare prefixes */
1066 if (n
!= NULL
&& IS_LEAF(n
) && tkey_equals(key
, n
->key
)) {
1067 l
= (struct leaf
*) n
;
1068 li
= leaf_info_new(plen
);
1073 fa_head
= &li
->falh
;
1074 insert_leaf_info(&l
->list
, li
);
1083 li
= leaf_info_new(plen
);
1086 tnode_free((struct tnode
*) l
);
1090 fa_head
= &li
->falh
;
1091 insert_leaf_info(&l
->list
, li
);
1093 if (t
->trie
&& n
== NULL
) {
1094 /* Case 2: n is NULL, and will just insert a new leaf */
1096 node_set_parent((struct node
*)l
, tp
);
1098 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1099 put_child(t
, (struct tnode
*)tp
, cindex
, (struct node
*)l
);
1101 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1103 * Add a new tnode here
1104 * first tnode need some special handling
1108 pos
= tp
->pos
+tp
->bits
;
1113 newpos
= tkey_mismatch(key
, pos
, n
->key
);
1114 tn
= tnode_new(n
->key
, newpos
, 1);
1117 tn
= tnode_new(key
, newpos
, 1); /* First tnode */
1122 tnode_free((struct tnode
*) l
);
1126 node_set_parent((struct node
*)tn
, tp
);
1128 missbit
= tkey_extract_bits(key
, newpos
, 1);
1129 put_child(t
, tn
, missbit
, (struct node
*)l
);
1130 put_child(t
, tn
, 1-missbit
, n
);
1133 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1134 put_child(t
, (struct tnode
*)tp
, cindex
,
1137 rcu_assign_pointer(t
->trie
, (struct node
*)tn
);
1142 if (tp
&& tp
->pos
+ tp
->bits
> 32)
1143 pr_warning("fib_trie"
1144 " tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1145 tp
, tp
->pos
, tp
->bits
, key
, plen
);
1147 /* Rebalance the trie */
1149 rcu_assign_pointer(t
->trie
, trie_rebalance(t
, tp
));
1155 * Caller must hold RTNL.
1157 static int fn_trie_insert(struct fib_table
*tb
, struct fib_config
*cfg
)
1159 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1160 struct fib_alias
*fa
, *new_fa
;
1161 struct list_head
*fa_head
= NULL
;
1162 struct fib_info
*fi
;
1163 int plen
= cfg
->fc_dst_len
;
1164 u8 tos
= cfg
->fc_tos
;
1172 key
= ntohl(cfg
->fc_dst
);
1174 pr_debug("Insert table=%u %08x/%d\n", tb
->tb_id
, key
, plen
);
1176 mask
= ntohl(inet_make_mask(plen
));
1183 fi
= fib_create_info(cfg
);
1189 l
= fib_find_node(t
, key
);
1193 fa_head
= get_fa_head(l
, plen
);
1194 fa
= fib_find_alias(fa_head
, tos
, fi
->fib_priority
);
1197 /* Now fa, if non-NULL, points to the first fib alias
1198 * with the same keys [prefix,tos,priority], if such key already
1199 * exists or to the node before which we will insert new one.
1201 * If fa is NULL, we will need to allocate a new one and
1202 * insert to the head of f.
1204 * If f is NULL, no fib node matched the destination key
1205 * and we need to allocate a new one of those as well.
1208 if (fa
&& fa
->fa_tos
== tos
&&
1209 fa
->fa_info
->fib_priority
== fi
->fib_priority
) {
1210 struct fib_alias
*fa_first
, *fa_match
;
1213 if (cfg
->fc_nlflags
& NLM_F_EXCL
)
1217 * 1. Find exact match for type, scope, fib_info to avoid
1219 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1223 fa
= list_entry(fa
->fa_list
.prev
, struct fib_alias
, fa_list
);
1224 list_for_each_entry_continue(fa
, fa_head
, fa_list
) {
1225 if (fa
->fa_tos
!= tos
)
1227 if (fa
->fa_info
->fib_priority
!= fi
->fib_priority
)
1229 if (fa
->fa_type
== cfg
->fc_type
&&
1230 fa
->fa_scope
== cfg
->fc_scope
&&
1231 fa
->fa_info
== fi
) {
1237 if (cfg
->fc_nlflags
& NLM_F_REPLACE
) {
1238 struct fib_info
*fi_drop
;
1248 new_fa
= kmem_cache_alloc(fn_alias_kmem
, GFP_KERNEL
);
1252 fi_drop
= fa
->fa_info
;
1253 new_fa
->fa_tos
= fa
->fa_tos
;
1254 new_fa
->fa_info
= fi
;
1255 new_fa
->fa_type
= cfg
->fc_type
;
1256 new_fa
->fa_scope
= cfg
->fc_scope
;
1257 state
= fa
->fa_state
;
1258 new_fa
->fa_state
= state
& ~FA_S_ACCESSED
;
1260 list_replace_rcu(&fa
->fa_list
, &new_fa
->fa_list
);
1261 alias_free_mem_rcu(fa
);
1263 fib_release_info(fi_drop
);
1264 if (state
& FA_S_ACCESSED
)
1266 rtmsg_fib(RTM_NEWROUTE
, htonl(key
), new_fa
, plen
,
1267 tb
->tb_id
, &cfg
->fc_nlinfo
, NLM_F_REPLACE
);
1271 /* Error if we find a perfect match which
1272 * uses the same scope, type, and nexthop
1278 if (!(cfg
->fc_nlflags
& NLM_F_APPEND
))
1282 if (!(cfg
->fc_nlflags
& NLM_F_CREATE
))
1286 new_fa
= kmem_cache_alloc(fn_alias_kmem
, GFP_KERNEL
);
1290 new_fa
->fa_info
= fi
;
1291 new_fa
->fa_tos
= tos
;
1292 new_fa
->fa_type
= cfg
->fc_type
;
1293 new_fa
->fa_scope
= cfg
->fc_scope
;
1294 new_fa
->fa_state
= 0;
1296 * Insert new entry to the list.
1300 fa_head
= fib_insert_node(t
, key
, plen
);
1301 if (unlikely(!fa_head
)) {
1303 goto out_free_new_fa
;
1307 list_add_tail_rcu(&new_fa
->fa_list
,
1308 (fa
? &fa
->fa_list
: fa_head
));
1311 rtmsg_fib(RTM_NEWROUTE
, htonl(key
), new_fa
, plen
, tb
->tb_id
,
1312 &cfg
->fc_nlinfo
, 0);
1317 kmem_cache_free(fn_alias_kmem
, new_fa
);
1319 fib_release_info(fi
);
1324 /* should be called with rcu_read_lock */
1325 static int check_leaf(struct trie
*t
, struct leaf
*l
,
1326 t_key key
, const struct flowi
*flp
,
1327 struct fib_result
*res
)
1329 struct leaf_info
*li
;
1330 struct hlist_head
*hhead
= &l
->list
;
1331 struct hlist_node
*node
;
1333 hlist_for_each_entry_rcu(li
, node
, hhead
, hlist
) {
1335 int plen
= li
->plen
;
1336 __be32 mask
= inet_make_mask(plen
);
1338 if (l
->key
!= (key
& ntohl(mask
)))
1341 err
= fib_semantic_match(&li
->falh
, flp
, res
,
1342 htonl(l
->key
), mask
, plen
);
1344 #ifdef CONFIG_IP_FIB_TRIE_STATS
1346 t
->stats
.semantic_match_passed
++;
1348 t
->stats
.semantic_match_miss
++;
1357 static int fn_trie_lookup(struct fib_table
*tb
, const struct flowi
*flp
,
1358 struct fib_result
*res
)
1360 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1365 t_key key
= ntohl(flp
->fl4_dst
);
1368 int current_prefix_length
= KEYLENGTH
;
1370 t_key node_prefix
, key_prefix
, pref_mismatch
;
1375 n
= rcu_dereference(t
->trie
);
1379 #ifdef CONFIG_IP_FIB_TRIE_STATS
1385 plen
= check_leaf(t
, (struct leaf
*)n
, key
, flp
, res
);
1392 pn
= (struct tnode
*) n
;
1400 cindex
= tkey_extract_bits(mask_pfx(key
, current_prefix_length
),
1403 n
= tnode_get_child(pn
, cindex
);
1406 #ifdef CONFIG_IP_FIB_TRIE_STATS
1407 t
->stats
.null_node_hit
++;
1413 plen
= check_leaf(t
, (struct leaf
*)n
, key
, flp
, res
);
1421 cn
= (struct tnode
*)n
;
1424 * It's a tnode, and we can do some extra checks here if we
1425 * like, to avoid descending into a dead-end branch.
1426 * This tnode is in the parent's child array at index
1427 * key[p_pos..p_pos+p_bits] but potentially with some bits
1428 * chopped off, so in reality the index may be just a
1429 * subprefix, padded with zero at the end.
1430 * We can also take a look at any skipped bits in this
1431 * tnode - everything up to p_pos is supposed to be ok,
1432 * and the non-chopped bits of the index (se previous
1433 * paragraph) are also guaranteed ok, but the rest is
1434 * considered unknown.
1436 * The skipped bits are key[pos+bits..cn->pos].
1439 /* If current_prefix_length < pos+bits, we are already doing
1440 * actual prefix matching, which means everything from
1441 * pos+(bits-chopped_off) onward must be zero along some
1442 * branch of this subtree - otherwise there is *no* valid
1443 * prefix present. Here we can only check the skipped
1444 * bits. Remember, since we have already indexed into the
1445 * parent's child array, we know that the bits we chopped of
1449 /* NOTA BENE: Checking only skipped bits
1450 for the new node here */
1452 if (current_prefix_length
< pos
+bits
) {
1453 if (tkey_extract_bits(cn
->key
, current_prefix_length
,
1454 cn
->pos
- current_prefix_length
)
1460 * If chopped_off=0, the index is fully validated and we
1461 * only need to look at the skipped bits for this, the new,
1462 * tnode. What we actually want to do is to find out if
1463 * these skipped bits match our key perfectly, or if we will
1464 * have to count on finding a matching prefix further down,
1465 * because if we do, we would like to have some way of
1466 * verifying the existence of such a prefix at this point.
1469 /* The only thing we can do at this point is to verify that
1470 * any such matching prefix can indeed be a prefix to our
1471 * key, and if the bits in the node we are inspecting that
1472 * do not match our key are not ZERO, this cannot be true.
1473 * Thus, find out where there is a mismatch (before cn->pos)
1474 * and verify that all the mismatching bits are zero in the
1479 * Note: We aren't very concerned about the piece of
1480 * the key that precede pn->pos+pn->bits, since these
1481 * have already been checked. The bits after cn->pos
1482 * aren't checked since these are by definition
1483 * "unknown" at this point. Thus, what we want to see
1484 * is if we are about to enter the "prefix matching"
1485 * state, and in that case verify that the skipped
1486 * bits that will prevail throughout this subtree are
1487 * zero, as they have to be if we are to find a
1491 node_prefix
= mask_pfx(cn
->key
, cn
->pos
);
1492 key_prefix
= mask_pfx(key
, cn
->pos
);
1493 pref_mismatch
= key_prefix
^node_prefix
;
1497 * In short: If skipped bits in this node do not match
1498 * the search key, enter the "prefix matching"
1501 if (pref_mismatch
) {
1502 while (!(pref_mismatch
& (1<<(KEYLENGTH
-1)))) {
1504 pref_mismatch
= pref_mismatch
<< 1;
1506 key_prefix
= tkey_extract_bits(cn
->key
, mp
, cn
->pos
-mp
);
1508 if (key_prefix
!= 0)
1511 if (current_prefix_length
>= cn
->pos
)
1512 current_prefix_length
= mp
;
1515 pn
= (struct tnode
*)n
; /* Descend */
1522 /* As zero don't change the child key (cindex) */
1523 while ((chopped_off
<= pn
->bits
)
1524 && !(cindex
& (1<<(chopped_off
-1))))
1527 /* Decrease current_... with bits chopped off */
1528 if (current_prefix_length
> pn
->pos
+ pn
->bits
- chopped_off
)
1529 current_prefix_length
= pn
->pos
+ pn
->bits
1533 * Either we do the actual chop off according or if we have
1534 * chopped off all bits in this tnode walk up to our parent.
1537 if (chopped_off
<= pn
->bits
) {
1538 cindex
&= ~(1 << (chopped_off
-1));
1540 struct tnode
*parent
= node_parent((struct node
*) pn
);
1544 /* Get Child's index */
1545 cindex
= tkey_extract_bits(pn
->key
, parent
->pos
, parent
->bits
);
1549 #ifdef CONFIG_IP_FIB_TRIE_STATS
1550 t
->stats
.backtrack
++;
1563 * Remove the leaf and return parent.
1565 static void trie_leaf_remove(struct trie
*t
, struct leaf
*l
)
1567 struct tnode
*tp
= node_parent((struct node
*) l
);
1569 pr_debug("entering trie_leaf_remove(%p)\n", l
);
1572 t_key cindex
= tkey_extract_bits(l
->key
, tp
->pos
, tp
->bits
);
1573 put_child(t
, (struct tnode
*)tp
, cindex
, NULL
);
1574 rcu_assign_pointer(t
->trie
, trie_rebalance(t
, tp
));
1576 rcu_assign_pointer(t
->trie
, NULL
);
1578 tnode_free((struct tnode
*) l
);
1582 * Caller must hold RTNL.
1584 static int fn_trie_delete(struct fib_table
*tb
, struct fib_config
*cfg
)
1586 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1588 int plen
= cfg
->fc_dst_len
;
1589 u8 tos
= cfg
->fc_tos
;
1590 struct fib_alias
*fa
, *fa_to_delete
;
1591 struct list_head
*fa_head
;
1593 struct leaf_info
*li
;
1598 key
= ntohl(cfg
->fc_dst
);
1599 mask
= ntohl(inet_make_mask(plen
));
1605 l
= fib_find_node(t
, key
);
1610 fa_head
= get_fa_head(l
, plen
);
1611 fa
= fib_find_alias(fa_head
, tos
, 0);
1616 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key
, plen
, tos
, t
);
1618 fa_to_delete
= NULL
;
1619 fa
= list_entry(fa
->fa_list
.prev
, struct fib_alias
, fa_list
);
1620 list_for_each_entry_continue(fa
, fa_head
, fa_list
) {
1621 struct fib_info
*fi
= fa
->fa_info
;
1623 if (fa
->fa_tos
!= tos
)
1626 if ((!cfg
->fc_type
|| fa
->fa_type
== cfg
->fc_type
) &&
1627 (cfg
->fc_scope
== RT_SCOPE_NOWHERE
||
1628 fa
->fa_scope
== cfg
->fc_scope
) &&
1629 (!cfg
->fc_protocol
||
1630 fi
->fib_protocol
== cfg
->fc_protocol
) &&
1631 fib_nh_match(cfg
, fi
) == 0) {
1641 rtmsg_fib(RTM_DELROUTE
, htonl(key
), fa
, plen
, tb
->tb_id
,
1642 &cfg
->fc_nlinfo
, 0);
1644 l
= fib_find_node(t
, key
);
1645 li
= find_leaf_info(l
, plen
);
1647 list_del_rcu(&fa
->fa_list
);
1649 if (list_empty(fa_head
)) {
1650 hlist_del_rcu(&li
->hlist
);
1654 if (hlist_empty(&l
->list
))
1655 trie_leaf_remove(t
, l
);
1657 if (fa
->fa_state
& FA_S_ACCESSED
)
1660 fib_release_info(fa
->fa_info
);
1661 alias_free_mem_rcu(fa
);
1665 static int trie_flush_list(struct trie
*t
, struct list_head
*head
)
1667 struct fib_alias
*fa
, *fa_node
;
1670 list_for_each_entry_safe(fa
, fa_node
, head
, fa_list
) {
1671 struct fib_info
*fi
= fa
->fa_info
;
1673 if (fi
&& (fi
->fib_flags
& RTNH_F_DEAD
)) {
1674 list_del_rcu(&fa
->fa_list
);
1675 fib_release_info(fa
->fa_info
);
1676 alias_free_mem_rcu(fa
);
1683 static int trie_flush_leaf(struct trie
*t
, struct leaf
*l
)
1686 struct hlist_head
*lih
= &l
->list
;
1687 struct hlist_node
*node
, *tmp
;
1688 struct leaf_info
*li
= NULL
;
1690 hlist_for_each_entry_safe(li
, node
, tmp
, lih
, hlist
) {
1691 found
+= trie_flush_list(t
, &li
->falh
);
1693 if (list_empty(&li
->falh
)) {
1694 hlist_del_rcu(&li
->hlist
);
1702 * Scan for the next right leaf starting at node p->child[idx]
1703 * Since we have back pointer, no recursion necessary.
1705 static struct leaf
*leaf_walk_rcu(struct tnode
*p
, struct node
*c
)
1711 idx
= tkey_extract_bits(c
->key
, p
->pos
, p
->bits
) + 1;
1715 while (idx
< 1u << p
->bits
) {
1716 c
= tnode_get_child_rcu(p
, idx
++);
1721 prefetch(p
->child
[idx
]);
1722 return (struct leaf
*) c
;
1725 /* Rescan start scanning in new node */
1726 p
= (struct tnode
*) c
;
1730 /* Node empty, walk back up to parent */
1731 c
= (struct node
*) p
;
1732 } while ( (p
= node_parent_rcu(c
)) != NULL
);
1734 return NULL
; /* Root of trie */
1737 static struct leaf
*trie_firstleaf(struct trie
*t
)
1739 struct tnode
*n
= (struct tnode
*) rcu_dereference(t
->trie
);
1744 if (IS_LEAF(n
)) /* trie is just a leaf */
1745 return (struct leaf
*) n
;
1747 return leaf_walk_rcu(n
, NULL
);
1750 static struct leaf
*trie_nextleaf(struct leaf
*l
)
1752 struct node
*c
= (struct node
*) l
;
1753 struct tnode
*p
= node_parent(c
);
1756 return NULL
; /* trie with just one leaf */
1758 return leaf_walk_rcu(p
, c
);
1762 * Caller must hold RTNL.
1764 static int fn_trie_flush(struct fib_table
*tb
)
1766 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1767 struct leaf
*l
, *ll
= NULL
;
1770 for (l
= trie_firstleaf(t
); l
; l
= trie_nextleaf(l
)) {
1771 found
+= trie_flush_leaf(t
, l
);
1773 if (ll
&& hlist_empty(&ll
->list
))
1774 trie_leaf_remove(t
, ll
);
1778 if (ll
&& hlist_empty(&ll
->list
))
1779 trie_leaf_remove(t
, ll
);
1781 pr_debug("trie_flush found=%d\n", found
);
1785 static void fn_trie_select_default(struct fib_table
*tb
,
1786 const struct flowi
*flp
,
1787 struct fib_result
*res
)
1789 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1790 int order
, last_idx
;
1791 struct fib_info
*fi
= NULL
;
1792 struct fib_info
*last_resort
;
1793 struct fib_alias
*fa
= NULL
;
1794 struct list_head
*fa_head
;
1803 l
= fib_find_node(t
, 0);
1807 fa_head
= get_fa_head(l
, 0);
1811 if (list_empty(fa_head
))
1814 list_for_each_entry_rcu(fa
, fa_head
, fa_list
) {
1815 struct fib_info
*next_fi
= fa
->fa_info
;
1817 if (fa
->fa_scope
!= res
->scope
||
1818 fa
->fa_type
!= RTN_UNICAST
)
1821 if (next_fi
->fib_priority
> res
->fi
->fib_priority
)
1823 if (!next_fi
->fib_nh
[0].nh_gw
||
1824 next_fi
->fib_nh
[0].nh_scope
!= RT_SCOPE_LINK
)
1826 fa
->fa_state
|= FA_S_ACCESSED
;
1829 if (next_fi
!= res
->fi
)
1831 } else if (!fib_detect_death(fi
, order
, &last_resort
,
1832 &last_idx
, tb
->tb_default
)) {
1833 fib_result_assign(res
, fi
);
1834 tb
->tb_default
= order
;
1840 if (order
<= 0 || fi
== NULL
) {
1841 tb
->tb_default
= -1;
1845 if (!fib_detect_death(fi
, order
, &last_resort
, &last_idx
,
1847 fib_result_assign(res
, fi
);
1848 tb
->tb_default
= order
;
1852 fib_result_assign(res
, last_resort
);
1853 tb
->tb_default
= last_idx
;
1858 static int fn_trie_dump_fa(t_key key
, int plen
, struct list_head
*fah
,
1859 struct fib_table
*tb
,
1860 struct sk_buff
*skb
, struct netlink_callback
*cb
)
1863 struct fib_alias
*fa
;
1864 __be32 xkey
= htonl(key
);
1869 /* rcu_read_lock is hold by caller */
1871 list_for_each_entry_rcu(fa
, fah
, fa_list
) {
1877 if (fib_dump_info(skb
, NETLINK_CB(cb
->skb
).pid
,
1886 fa
->fa_info
, NLM_F_MULTI
) < 0) {
1896 static int fn_trie_dump_leaf(struct leaf
*l
, struct fib_table
*tb
,
1897 struct sk_buff
*skb
, struct netlink_callback
*cb
)
1899 struct leaf_info
*li
;
1900 struct hlist_node
*node
;
1906 /* rcu_read_lock is hold by caller */
1907 hlist_for_each_entry_rcu(li
, node
, &l
->list
, hlist
) {
1916 if (list_empty(&li
->falh
))
1919 if (fn_trie_dump_fa(l
->key
, li
->plen
, &li
->falh
, tb
, skb
, cb
) < 0) {
1930 static int fn_trie_dump(struct fib_table
*tb
, struct sk_buff
*skb
,
1931 struct netlink_callback
*cb
)
1934 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1935 t_key key
= cb
->args
[2];
1938 /* Dump starting at last key.
1939 * Note: 0.0.0.0/0 (ie default) is first key.
1942 l
= trie_firstleaf(t
);
1944 l
= fib_find_node(t
, key
);
1946 /* The table changed during the dump, rather than
1947 * giving partial data, just make application retry.
1955 cb
->args
[2] = l
->key
;
1956 if (fn_trie_dump_leaf(l
, tb
, skb
, cb
) < 0) {
1961 l
= trie_nextleaf(l
);
1962 memset(&cb
->args
[3], 0,
1963 sizeof(cb
->args
) - 3*sizeof(cb
->args
[0]));
1970 void __init
fib_hash_init(void)
1972 fn_alias_kmem
= kmem_cache_create("ip_fib_alias",
1973 sizeof(struct fib_alias
),
1974 0, SLAB_PANIC
, NULL
);
1976 trie_leaf_kmem
= kmem_cache_create("ip_fib_trie",
1977 max(sizeof(struct leaf
),
1978 sizeof(struct leaf_info
)),
1979 0, SLAB_PANIC
, NULL
);
1983 /* Fix more generic FIB names for init later */
1984 struct fib_table
*fib_hash_table(u32 id
)
1986 struct fib_table
*tb
;
1989 tb
= kmalloc(sizeof(struct fib_table
) + sizeof(struct trie
),
1995 tb
->tb_default
= -1;
1996 tb
->tb_lookup
= fn_trie_lookup
;
1997 tb
->tb_insert
= fn_trie_insert
;
1998 tb
->tb_delete
= fn_trie_delete
;
1999 tb
->tb_flush
= fn_trie_flush
;
2000 tb
->tb_select_default
= fn_trie_select_default
;
2001 tb
->tb_dump
= fn_trie_dump
;
2003 t
= (struct trie
*) tb
->tb_data
;
2004 memset(t
, 0, sizeof(*t
));
2006 if (id
== RT_TABLE_LOCAL
)
2007 pr_info("IPv4 FIB: Using LC-trie version %s\n", VERSION
);
2012 #ifdef CONFIG_PROC_FS
2013 /* Depth first Trie walk iterator */
2014 struct fib_trie_iter
{
2015 struct seq_net_private p
;
2016 struct trie
*trie_local
, *trie_main
;
2017 struct tnode
*tnode
;
2023 static struct node
*fib_trie_get_next(struct fib_trie_iter
*iter
)
2025 struct tnode
*tn
= iter
->tnode
;
2026 unsigned cindex
= iter
->index
;
2029 /* A single entry routing table */
2033 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2034 iter
->tnode
, iter
->index
, iter
->depth
);
2036 while (cindex
< (1<<tn
->bits
)) {
2037 struct node
*n
= tnode_get_child_rcu(tn
, cindex
);
2042 iter
->index
= cindex
+ 1;
2044 /* push down one level */
2045 iter
->tnode
= (struct tnode
*) n
;
2055 /* Current node exhausted, pop back up */
2056 p
= node_parent_rcu((struct node
*)tn
);
2058 cindex
= tkey_extract_bits(tn
->key
, p
->pos
, p
->bits
)+1;
2068 static struct node
*fib_trie_get_first(struct fib_trie_iter
*iter
,
2076 n
= rcu_dereference(t
->trie
);
2083 iter
->tnode
= (struct tnode
*) n
;
2098 static void trie_collect_stats(struct trie
*t
, struct trie_stat
*s
)
2101 struct fib_trie_iter iter
;
2103 memset(s
, 0, sizeof(*s
));
2106 for (n
= fib_trie_get_first(&iter
, t
); n
;
2107 n
= fib_trie_get_next(&iter
)) {
2109 struct leaf
*l
= (struct leaf
*)n
;
2110 struct leaf_info
*li
;
2111 struct hlist_node
*tmp
;
2114 s
->totdepth
+= iter
.depth
;
2115 if (iter
.depth
> s
->maxdepth
)
2116 s
->maxdepth
= iter
.depth
;
2118 hlist_for_each_entry_rcu(li
, tmp
, &l
->list
, hlist
)
2121 const struct tnode
*tn
= (const struct tnode
*) n
;
2125 if (tn
->bits
< MAX_STAT_DEPTH
)
2126 s
->nodesizes
[tn
->bits
]++;
2128 for (i
= 0; i
< (1<<tn
->bits
); i
++)
2137 * This outputs /proc/net/fib_triestats
2139 static void trie_show_stats(struct seq_file
*seq
, struct trie_stat
*stat
)
2141 unsigned i
, max
, pointers
, bytes
, avdepth
;
2144 avdepth
= stat
->totdepth
*100 / stat
->leaves
;
2148 seq_printf(seq
, "\tAver depth: %u.%02d\n",
2149 avdepth
/ 100, avdepth
% 100);
2150 seq_printf(seq
, "\tMax depth: %u\n", stat
->maxdepth
);
2152 seq_printf(seq
, "\tLeaves: %u\n", stat
->leaves
);
2153 bytes
= sizeof(struct leaf
) * stat
->leaves
;
2155 seq_printf(seq
, "\tPrefixes: %u\n", stat
->prefixes
);
2156 bytes
+= sizeof(struct leaf_info
) * stat
->prefixes
;
2158 seq_printf(seq
, "\tInternal nodes: %u\n\t", stat
->tnodes
);
2159 bytes
+= sizeof(struct tnode
) * stat
->tnodes
;
2161 max
= MAX_STAT_DEPTH
;
2162 while (max
> 0 && stat
->nodesizes
[max
-1] == 0)
2166 for (i
= 1; i
<= max
; i
++)
2167 if (stat
->nodesizes
[i
] != 0) {
2168 seq_printf(seq
, " %u: %u", i
, stat
->nodesizes
[i
]);
2169 pointers
+= (1<<i
) * stat
->nodesizes
[i
];
2171 seq_putc(seq
, '\n');
2172 seq_printf(seq
, "\tPointers: %u\n", pointers
);
2174 bytes
+= sizeof(struct node
*) * pointers
;
2175 seq_printf(seq
, "Null ptrs: %u\n", stat
->nullpointers
);
2176 seq_printf(seq
, "Total size: %u kB\n", (bytes
+ 1023) / 1024);
2179 #ifdef CONFIG_IP_FIB_TRIE_STATS
2180 static void trie_show_usage(struct seq_file
*seq
,
2181 const struct trie_use_stats
*stats
)
2183 seq_printf(seq
, "\nCounters:\n---------\n");
2184 seq_printf(seq
, "gets = %u\n", stats
->gets
);
2185 seq_printf(seq
, "backtracks = %u\n", stats
->backtrack
);
2186 seq_printf(seq
, "semantic match passed = %u\n",
2187 stats
->semantic_match_passed
);
2188 seq_printf(seq
, "semantic match miss = %u\n",
2189 stats
->semantic_match_miss
);
2190 seq_printf(seq
, "null node hit= %u\n", stats
->null_node_hit
);
2191 seq_printf(seq
, "skipped node resize = %u\n\n",
2192 stats
->resize_node_skipped
);
2194 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2196 static void fib_trie_show(struct seq_file
*seq
, const char *name
,
2199 struct trie_stat stat
;
2201 trie_collect_stats(trie
, &stat
);
2202 seq_printf(seq
, "%s:\n", name
);
2203 trie_show_stats(seq
, &stat
);
2204 #ifdef CONFIG_IP_FIB_TRIE_STATS
2205 trie_show_usage(seq
, &trie
->stats
);
2209 static int fib_triestat_seq_show(struct seq_file
*seq
, void *v
)
2211 struct net
*net
= (struct net
*)seq
->private;
2212 struct fib_table
*tb
;
2215 "Basic info: size of leaf:"
2216 " %Zd bytes, size of tnode: %Zd bytes.\n",
2217 sizeof(struct leaf
), sizeof(struct tnode
));
2219 tb
= fib_get_table(net
, RT_TABLE_LOCAL
);
2221 fib_trie_show(seq
, "Local", (struct trie
*) tb
->tb_data
);
2223 tb
= fib_get_table(net
, RT_TABLE_MAIN
);
2225 fib_trie_show(seq
, "Main", (struct trie
*) tb
->tb_data
);
2230 static int fib_triestat_seq_open(struct inode
*inode
, struct file
*file
)
2235 net
= get_proc_net(inode
);
2238 err
= single_open(file
, fib_triestat_seq_show
, net
);
2246 static int fib_triestat_seq_release(struct inode
*ino
, struct file
*f
)
2248 struct seq_file
*seq
= f
->private_data
;
2249 put_net(seq
->private);
2250 return single_release(ino
, f
);
2253 static const struct file_operations fib_triestat_fops
= {
2254 .owner
= THIS_MODULE
,
2255 .open
= fib_triestat_seq_open
,
2257 .llseek
= seq_lseek
,
2258 .release
= fib_triestat_seq_release
,
2261 static struct node
*fib_trie_get_idx(struct fib_trie_iter
*iter
,
2267 for (n
= fib_trie_get_first(iter
, iter
->trie_local
);
2268 n
; ++idx
, n
= fib_trie_get_next(iter
)) {
2273 for (n
= fib_trie_get_first(iter
, iter
->trie_main
);
2274 n
; ++idx
, n
= fib_trie_get_next(iter
)) {
2281 static void *fib_trie_seq_start(struct seq_file
*seq
, loff_t
*pos
)
2284 struct fib_trie_iter
*iter
= seq
->private;
2285 struct fib_table
*tb
;
2287 if (!iter
->trie_local
) {
2288 tb
= fib_get_table(iter
->p
.net
, RT_TABLE_LOCAL
);
2290 iter
->trie_local
= (struct trie
*) tb
->tb_data
;
2292 if (!iter
->trie_main
) {
2293 tb
= fib_get_table(iter
->p
.net
, RT_TABLE_MAIN
);
2295 iter
->trie_main
= (struct trie
*) tb
->tb_data
;
2299 return SEQ_START_TOKEN
;
2300 return fib_trie_get_idx(iter
, *pos
- 1);
2303 static void *fib_trie_seq_next(struct seq_file
*seq
, void *v
, loff_t
*pos
)
2305 struct fib_trie_iter
*iter
= seq
->private;
2309 if (v
== SEQ_START_TOKEN
)
2310 return fib_trie_get_idx(iter
, 0);
2312 v
= fib_trie_get_next(iter
);
2317 /* continue scan in next trie */
2318 if (iter
->trie
== iter
->trie_local
)
2319 return fib_trie_get_first(iter
, iter
->trie_main
);
2324 static void fib_trie_seq_stop(struct seq_file
*seq
, void *v
)
2330 static void seq_indent(struct seq_file
*seq
, int n
)
2332 while (n
-- > 0) seq_puts(seq
, " ");
2335 static inline const char *rtn_scope(char *buf
, size_t len
, enum rt_scope_t s
)
2338 case RT_SCOPE_UNIVERSE
: return "universe";
2339 case RT_SCOPE_SITE
: return "site";
2340 case RT_SCOPE_LINK
: return "link";
2341 case RT_SCOPE_HOST
: return "host";
2342 case RT_SCOPE_NOWHERE
: return "nowhere";
2344 snprintf(buf
, len
, "scope=%d", s
);
2349 static const char *rtn_type_names
[__RTN_MAX
] = {
2350 [RTN_UNSPEC
] = "UNSPEC",
2351 [RTN_UNICAST
] = "UNICAST",
2352 [RTN_LOCAL
] = "LOCAL",
2353 [RTN_BROADCAST
] = "BROADCAST",
2354 [RTN_ANYCAST
] = "ANYCAST",
2355 [RTN_MULTICAST
] = "MULTICAST",
2356 [RTN_BLACKHOLE
] = "BLACKHOLE",
2357 [RTN_UNREACHABLE
] = "UNREACHABLE",
2358 [RTN_PROHIBIT
] = "PROHIBIT",
2359 [RTN_THROW
] = "THROW",
2361 [RTN_XRESOLVE
] = "XRESOLVE",
2364 static inline const char *rtn_type(char *buf
, size_t len
, unsigned t
)
2366 if (t
< __RTN_MAX
&& rtn_type_names
[t
])
2367 return rtn_type_names
[t
];
2368 snprintf(buf
, len
, "type %u", t
);
2372 /* Pretty print the trie */
2373 static int fib_trie_seq_show(struct seq_file
*seq
, void *v
)
2375 const struct fib_trie_iter
*iter
= seq
->private;
2378 if (v
== SEQ_START_TOKEN
)
2381 if (!node_parent_rcu(n
)) {
2382 if (iter
->trie
== iter
->trie_local
)
2383 seq_puts(seq
, "<local>:\n");
2385 seq_puts(seq
, "<main>:\n");
2389 struct tnode
*tn
= (struct tnode
*) n
;
2390 __be32 prf
= htonl(mask_pfx(tn
->key
, tn
->pos
));
2392 seq_indent(seq
, iter
->depth
-1);
2393 seq_printf(seq
, " +-- %d.%d.%d.%d/%d %d %d %d\n",
2394 NIPQUAD(prf
), tn
->pos
, tn
->bits
, tn
->full_children
,
2395 tn
->empty_children
);
2398 struct leaf
*l
= (struct leaf
*) n
;
2399 struct leaf_info
*li
;
2400 struct hlist_node
*node
;
2401 __be32 val
= htonl(l
->key
);
2403 seq_indent(seq
, iter
->depth
);
2404 seq_printf(seq
, " |-- %d.%d.%d.%d\n", NIPQUAD(val
));
2406 hlist_for_each_entry_rcu(li
, node
, &l
->list
, hlist
) {
2407 struct fib_alias
*fa
;
2409 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
2410 char buf1
[32], buf2
[32];
2412 seq_indent(seq
, iter
->depth
+1);
2413 seq_printf(seq
, " /%d %s %s", li
->plen
,
2414 rtn_scope(buf1
, sizeof(buf1
),
2416 rtn_type(buf2
, sizeof(buf2
),
2419 seq_printf(seq
, "tos =%d\n",
2421 seq_putc(seq
, '\n');
2429 static const struct seq_operations fib_trie_seq_ops
= {
2430 .start
= fib_trie_seq_start
,
2431 .next
= fib_trie_seq_next
,
2432 .stop
= fib_trie_seq_stop
,
2433 .show
= fib_trie_seq_show
,
2436 static int fib_trie_seq_open(struct inode
*inode
, struct file
*file
)
2438 return seq_open_net(inode
, file
, &fib_trie_seq_ops
,
2439 sizeof(struct fib_trie_iter
));
2442 static const struct file_operations fib_trie_fops
= {
2443 .owner
= THIS_MODULE
,
2444 .open
= fib_trie_seq_open
,
2446 .llseek
= seq_lseek
,
2447 .release
= seq_release_net
,
2450 static unsigned fib_flag_trans(int type
, __be32 mask
, const struct fib_info
*fi
)
2452 static unsigned type2flags
[RTN_MAX
+ 1] = {
2453 [7] = RTF_REJECT
, [8] = RTF_REJECT
,
2455 unsigned flags
= type2flags
[type
];
2457 if (fi
&& fi
->fib_nh
->nh_gw
)
2458 flags
|= RTF_GATEWAY
;
2459 if (mask
== htonl(0xFFFFFFFF))
2466 * This outputs /proc/net/route.
2467 * The format of the file is not supposed to be changed
2468 * and needs to be same as fib_hash output to avoid breaking
2471 static int fib_route_seq_show(struct seq_file
*seq
, void *v
)
2473 const struct fib_trie_iter
*iter
= seq
->private;
2475 struct leaf_info
*li
;
2476 struct hlist_node
*node
;
2478 if (v
== SEQ_START_TOKEN
) {
2479 seq_printf(seq
, "%-127s\n", "Iface\tDestination\tGateway "
2480 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2485 if (iter
->trie
== iter
->trie_local
)
2491 hlist_for_each_entry_rcu(li
, node
, &l
->list
, hlist
) {
2492 struct fib_alias
*fa
;
2493 __be32 mask
, prefix
;
2495 mask
= inet_make_mask(li
->plen
);
2496 prefix
= htonl(l
->key
);
2498 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
2499 const struct fib_info
*fi
= fa
->fa_info
;
2500 unsigned flags
= fib_flag_trans(fa
->fa_type
, mask
, fi
);
2503 if (fa
->fa_type
== RTN_BROADCAST
2504 || fa
->fa_type
== RTN_MULTICAST
)
2508 snprintf(bf
, sizeof(bf
),
2509 "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2510 fi
->fib_dev
? fi
->fib_dev
->name
: "*",
2512 fi
->fib_nh
->nh_gw
, flags
, 0, 0,
2516 fi
->fib_advmss
+ 40 : 0),
2520 snprintf(bf
, sizeof(bf
),
2521 "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2522 prefix
, 0, flags
, 0, 0, 0,
2525 seq_printf(seq
, "%-127s\n", bf
);
2532 static const struct seq_operations fib_route_seq_ops
= {
2533 .start
= fib_trie_seq_start
,
2534 .next
= fib_trie_seq_next
,
2535 .stop
= fib_trie_seq_stop
,
2536 .show
= fib_route_seq_show
,
2539 static int fib_route_seq_open(struct inode
*inode
, struct file
*file
)
2541 return seq_open_net(inode
, file
, &fib_route_seq_ops
,
2542 sizeof(struct fib_trie_iter
));
2545 static const struct file_operations fib_route_fops
= {
2546 .owner
= THIS_MODULE
,
2547 .open
= fib_route_seq_open
,
2549 .llseek
= seq_lseek
,
2550 .release
= seq_release_net
,
2553 int __net_init
fib_proc_init(struct net
*net
)
2555 if (!proc_net_fops_create(net
, "fib_trie", S_IRUGO
, &fib_trie_fops
))
2558 if (!proc_net_fops_create(net
, "fib_triestat", S_IRUGO
,
2559 &fib_triestat_fops
))
2562 if (!proc_net_fops_create(net
, "route", S_IRUGO
, &fib_route_fops
))
2568 proc_net_remove(net
, "fib_triestat");
2570 proc_net_remove(net
, "fib_trie");
2575 void __net_exit
fib_proc_exit(struct net
*net
)
2577 proc_net_remove(net
, "fib_trie");
2578 proc_net_remove(net
, "fib_triestat");
2579 proc_net_remove(net
, "route");
2582 #endif /* CONFIG_PROC_FS */