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 <asm/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>
77 #include <net/protocol.h>
78 #include <net/route.h>
81 #include <net/ip_fib.h>
82 #include "fib_lookup.h"
84 #undef CONFIG_IP_FIB_TRIE_STATS
85 #define MAX_STAT_DEPTH 32
87 #define KEYLENGTH (8*sizeof(t_key))
88 #define MASK_PFX(k, l) (((l)==0)?0:(k >> (KEYLENGTH-l)) << (KEYLENGTH-l))
89 #define TKEY_GET_MASK(offset, bits) (((bits)==0)?0:((t_key)(-1) << (KEYLENGTH - bits) >> offset))
91 typedef unsigned int t_key
;
95 #define NODE_TYPE_MASK 0x1UL
96 #define NODE_PARENT(node) \
97 ((struct tnode *)rcu_dereference(((node)->parent & ~NODE_TYPE_MASK)))
99 #define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
101 #define NODE_SET_PARENT(node, ptr) \
102 rcu_assign_pointer((node)->parent, \
103 ((unsigned long)(ptr)) | NODE_TYPE(node))
105 #define IS_TNODE(n) (!(n->parent & T_LEAF))
106 #define IS_LEAF(n) (n->parent & T_LEAF)
110 unsigned long parent
;
115 unsigned long parent
;
116 struct hlist_head list
;
121 struct hlist_node hlist
;
124 struct list_head falh
;
129 unsigned long parent
;
130 unsigned short pos
:5; /* 2log(KEYLENGTH) bits needed */
131 unsigned short bits
:5; /* 2log(KEYLENGTH) bits needed */
132 unsigned short full_children
; /* KEYLENGTH bits needed */
133 unsigned short empty_children
; /* KEYLENGTH bits needed */
135 struct node
*child
[0];
138 #ifdef CONFIG_IP_FIB_TRIE_STATS
139 struct trie_use_stats
{
141 unsigned int backtrack
;
142 unsigned int semantic_match_passed
;
143 unsigned int semantic_match_miss
;
144 unsigned int null_node_hit
;
145 unsigned int resize_node_skipped
;
150 unsigned int totdepth
;
151 unsigned int maxdepth
;
154 unsigned int nullpointers
;
155 unsigned int nodesizes
[MAX_STAT_DEPTH
];
160 #ifdef CONFIG_IP_FIB_TRIE_STATS
161 struct trie_use_stats stats
;
164 unsigned int revision
;
167 static void put_child(struct trie
*t
, struct tnode
*tn
, int i
, struct node
*n
);
168 static void tnode_put_child_reorg(struct tnode
*tn
, int i
, struct node
*n
, int wasfull
);
169 static struct node
*resize(struct trie
*t
, struct tnode
*tn
);
170 static struct tnode
*inflate(struct trie
*t
, struct tnode
*tn
);
171 static struct tnode
*halve(struct trie
*t
, struct tnode
*tn
);
172 static void tnode_free(struct tnode
*tn
);
174 static struct kmem_cache
*fn_alias_kmem __read_mostly
;
175 static struct trie
*trie_local
= NULL
, *trie_main
= NULL
;
178 /* rcu_read_lock needs to be hold by caller from readside */
180 static inline struct node
*tnode_get_child(struct tnode
*tn
, int i
)
182 BUG_ON(i
>= 1 << tn
->bits
);
184 return rcu_dereference(tn
->child
[i
]);
187 static inline int tnode_child_length(const struct tnode
*tn
)
189 return 1 << tn
->bits
;
192 static inline t_key
tkey_extract_bits(t_key a
, int offset
, int bits
)
194 if (offset
< KEYLENGTH
)
195 return ((t_key
)(a
<< offset
)) >> (KEYLENGTH
- bits
);
200 static inline int tkey_equals(t_key a
, t_key b
)
205 static inline int tkey_sub_equals(t_key a
, int offset
, int bits
, t_key b
)
207 if (bits
== 0 || offset
>= KEYLENGTH
)
209 bits
= bits
> KEYLENGTH
? KEYLENGTH
: bits
;
210 return ((a
^ b
) << offset
) >> (KEYLENGTH
- bits
) == 0;
213 static inline int tkey_mismatch(t_key a
, int offset
, t_key b
)
220 while ((diff
<< i
) >> (KEYLENGTH
-1) == 0)
226 To understand this stuff, an understanding of keys and all their bits is
227 necessary. Every node in the trie has a key associated with it, but not
228 all of the bits in that key are significant.
230 Consider a node 'n' and its parent 'tp'.
232 If n is a leaf, every bit in its key is significant. Its presence is
233 necessitated by path compression, since during a tree traversal (when
234 searching for a leaf - unless we are doing an insertion) we will completely
235 ignore all skipped bits we encounter. Thus we need to verify, at the end of
236 a potentially successful search, that we have indeed been walking the
239 Note that we can never "miss" the correct key in the tree if present by
240 following the wrong path. Path compression ensures that segments of the key
241 that are the same for all keys with a given prefix are skipped, but the
242 skipped part *is* identical for each node in the subtrie below the skipped
243 bit! trie_insert() in this implementation takes care of that - note the
244 call to tkey_sub_equals() in trie_insert().
246 if n is an internal node - a 'tnode' here, the various parts of its key
247 have many different meanings.
250 _________________________________________________________________
251 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
252 -----------------------------------------------------------------
253 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
255 _________________________________________________________________
256 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
257 -----------------------------------------------------------------
258 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
265 First, let's just ignore the bits that come before the parent tp, that is
266 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
267 not use them for anything.
269 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
270 index into the parent's child array. That is, they will be used to find
271 'n' among tp's children.
273 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
276 All the bits we have seen so far are significant to the node n. The rest
277 of the bits are really not needed or indeed known in n->key.
279 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
280 n's child array, and will of course be different for each child.
283 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
288 static inline void check_tnode(const struct tnode
*tn
)
290 WARN_ON(tn
&& tn
->pos
+tn
->bits
> 32);
293 static int halve_threshold
= 25;
294 static int inflate_threshold
= 50;
295 static int halve_threshold_root
= 8;
296 static int inflate_threshold_root
= 15;
299 static void __alias_free_mem(struct rcu_head
*head
)
301 struct fib_alias
*fa
= container_of(head
, struct fib_alias
, rcu
);
302 kmem_cache_free(fn_alias_kmem
, fa
);
305 static inline void alias_free_mem_rcu(struct fib_alias
*fa
)
307 call_rcu(&fa
->rcu
, __alias_free_mem
);
310 static void __leaf_free_rcu(struct rcu_head
*head
)
312 kfree(container_of(head
, struct leaf
, rcu
));
315 static void __leaf_info_free_rcu(struct rcu_head
*head
)
317 kfree(container_of(head
, struct leaf_info
, rcu
));
320 static inline void free_leaf_info(struct leaf_info
*leaf
)
322 call_rcu(&leaf
->rcu
, __leaf_info_free_rcu
);
325 static struct tnode
*tnode_alloc(unsigned int size
)
329 if (size
<= PAGE_SIZE
)
330 return kcalloc(size
, 1, GFP_KERNEL
);
332 pages
= alloc_pages(GFP_KERNEL
|__GFP_ZERO
, get_order(size
));
336 return page_address(pages
);
339 static void __tnode_free_rcu(struct rcu_head
*head
)
341 struct tnode
*tn
= container_of(head
, struct tnode
, rcu
);
342 unsigned int size
= sizeof(struct tnode
) +
343 (1 << tn
->bits
) * sizeof(struct node
*);
345 if (size
<= PAGE_SIZE
)
348 free_pages((unsigned long)tn
, get_order(size
));
351 static inline void tnode_free(struct tnode
*tn
)
354 struct leaf
*l
= (struct leaf
*) tn
;
355 call_rcu_bh(&l
->rcu
, __leaf_free_rcu
);
357 call_rcu(&tn
->rcu
, __tnode_free_rcu
);
360 static struct leaf
*leaf_new(void)
362 struct leaf
*l
= kmalloc(sizeof(struct leaf
), GFP_KERNEL
);
365 INIT_HLIST_HEAD(&l
->list
);
370 static struct leaf_info
*leaf_info_new(int plen
)
372 struct leaf_info
*li
= kmalloc(sizeof(struct leaf_info
), GFP_KERNEL
);
375 INIT_LIST_HEAD(&li
->falh
);
380 static struct tnode
* tnode_new(t_key key
, int pos
, int bits
)
382 int nchildren
= 1<<bits
;
383 int sz
= sizeof(struct tnode
) + nchildren
* sizeof(struct node
*);
384 struct tnode
*tn
= tnode_alloc(sz
);
388 tn
->parent
= T_TNODE
;
392 tn
->full_children
= 0;
393 tn
->empty_children
= 1<<bits
;
396 pr_debug("AT %p s=%u %u\n", tn
, (unsigned int) sizeof(struct tnode
),
397 (unsigned int) (sizeof(struct node
) * 1<<bits
));
402 * Check whether a tnode 'n' is "full", i.e. it is an internal node
403 * and no bits are skipped. See discussion in dyntree paper p. 6
406 static inline int tnode_full(const struct tnode
*tn
, const struct node
*n
)
408 if (n
== NULL
|| IS_LEAF(n
))
411 return ((struct tnode
*) n
)->pos
== tn
->pos
+ tn
->bits
;
414 static inline void put_child(struct trie
*t
, struct tnode
*tn
, int i
, struct node
*n
)
416 tnode_put_child_reorg(tn
, i
, n
, -1);
420 * Add a child at position i overwriting the old value.
421 * Update the value of full_children and empty_children.
424 static void tnode_put_child_reorg(struct tnode
*tn
, int i
, struct node
*n
, int wasfull
)
426 struct node
*chi
= tn
->child
[i
];
429 BUG_ON(i
>= 1<<tn
->bits
);
432 /* update emptyChildren */
433 if (n
== NULL
&& chi
!= NULL
)
434 tn
->empty_children
++;
435 else if (n
!= NULL
&& chi
== NULL
)
436 tn
->empty_children
--;
438 /* update fullChildren */
440 wasfull
= tnode_full(tn
, chi
);
442 isfull
= tnode_full(tn
, n
);
443 if (wasfull
&& !isfull
)
445 else if (!wasfull
&& isfull
)
449 NODE_SET_PARENT(n
, tn
);
451 rcu_assign_pointer(tn
->child
[i
], n
);
454 static struct node
*resize(struct trie
*t
, struct tnode
*tn
)
458 struct tnode
*old_tn
;
459 int inflate_threshold_use
;
460 int halve_threshold_use
;
466 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
467 tn
, inflate_threshold
, halve_threshold
);
470 if (tn
->empty_children
== tnode_child_length(tn
)) {
475 if (tn
->empty_children
== tnode_child_length(tn
) - 1)
476 for (i
= 0; i
< tnode_child_length(tn
); i
++) {
483 /* compress one level */
484 NODE_SET_PARENT(n
, NULL
);
489 * Double as long as the resulting node has a number of
490 * nonempty nodes that are above the threshold.
494 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
495 * the Helsinki University of Technology and Matti Tikkanen of Nokia
496 * Telecommunications, page 6:
497 * "A node is doubled if the ratio of non-empty children to all
498 * children in the *doubled* node is at least 'high'."
500 * 'high' in this instance is the variable 'inflate_threshold'. It
501 * is expressed as a percentage, so we multiply it with
502 * tnode_child_length() and instead of multiplying by 2 (since the
503 * child array will be doubled by inflate()) and multiplying
504 * the left-hand side by 100 (to handle the percentage thing) we
505 * multiply the left-hand side by 50.
507 * The left-hand side may look a bit weird: tnode_child_length(tn)
508 * - tn->empty_children is of course the number of non-null children
509 * in the current node. tn->full_children is the number of "full"
510 * children, that is non-null tnodes with a skip value of 0.
511 * All of those will be doubled in the resulting inflated tnode, so
512 * we just count them one extra time here.
514 * A clearer way to write this would be:
516 * to_be_doubled = tn->full_children;
517 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
520 * new_child_length = tnode_child_length(tn) * 2;
522 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
524 * if (new_fill_factor >= inflate_threshold)
526 * ...and so on, tho it would mess up the while () loop.
529 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
533 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
534 * inflate_threshold * new_child_length
536 * expand not_to_be_doubled and to_be_doubled, and shorten:
537 * 100 * (tnode_child_length(tn) - tn->empty_children +
538 * tn->full_children) >= inflate_threshold * new_child_length
540 * expand new_child_length:
541 * 100 * (tnode_child_length(tn) - tn->empty_children +
542 * tn->full_children) >=
543 * inflate_threshold * tnode_child_length(tn) * 2
546 * 50 * (tn->full_children + tnode_child_length(tn) -
547 * tn->empty_children) >= inflate_threshold *
548 * tnode_child_length(tn)
554 /* Keep root node larger */
557 inflate_threshold_use
= inflate_threshold_root
;
559 inflate_threshold_use
= inflate_threshold
;
563 while ((tn
->full_children
> 0 && max_resize
-- &&
564 50 * (tn
->full_children
+ tnode_child_length(tn
) - tn
->empty_children
) >=
565 inflate_threshold_use
* tnode_child_length(tn
))) {
571 #ifdef CONFIG_IP_FIB_TRIE_STATS
572 t
->stats
.resize_node_skipped
++;
578 if (max_resize
< 0) {
580 printk(KERN_WARNING
"Fix inflate_threshold_root. Now=%d size=%d bits\n",
581 inflate_threshold_root
, tn
->bits
);
583 printk(KERN_WARNING
"Fix inflate_threshold. Now=%d size=%d bits\n",
584 inflate_threshold
, tn
->bits
);
590 * Halve as long as the number of empty children in this
591 * node is above threshold.
595 /* Keep root node larger */
598 halve_threshold_use
= halve_threshold_root
;
600 halve_threshold_use
= halve_threshold
;
604 while (tn
->bits
> 1 && max_resize
-- &&
605 100 * (tnode_child_length(tn
) - tn
->empty_children
) <
606 halve_threshold_use
* tnode_child_length(tn
)) {
612 #ifdef CONFIG_IP_FIB_TRIE_STATS
613 t
->stats
.resize_node_skipped
++;
619 if (max_resize
< 0) {
621 printk(KERN_WARNING
"Fix halve_threshold_root. Now=%d size=%d bits\n",
622 halve_threshold_root
, tn
->bits
);
624 printk(KERN_WARNING
"Fix halve_threshold. Now=%d size=%d bits\n",
625 halve_threshold
, tn
->bits
);
628 /* Only one child remains */
629 if (tn
->empty_children
== tnode_child_length(tn
) - 1)
630 for (i
= 0; i
< tnode_child_length(tn
); i
++) {
637 /* compress one level */
639 NODE_SET_PARENT(n
, NULL
);
644 return (struct node
*) tn
;
647 static struct tnode
*inflate(struct trie
*t
, struct tnode
*tn
)
650 struct tnode
*oldtnode
= tn
;
651 int olen
= tnode_child_length(tn
);
654 pr_debug("In inflate\n");
656 tn
= tnode_new(oldtnode
->key
, oldtnode
->pos
, oldtnode
->bits
+ 1);
659 return ERR_PTR(-ENOMEM
);
662 * Preallocate and store tnodes before the actual work so we
663 * don't get into an inconsistent state if memory allocation
664 * fails. In case of failure we return the oldnode and inflate
665 * of tnode is ignored.
668 for (i
= 0; i
< olen
; i
++) {
669 struct tnode
*inode
= (struct tnode
*) tnode_get_child(oldtnode
, i
);
673 inode
->pos
== oldtnode
->pos
+ oldtnode
->bits
&&
675 struct tnode
*left
, *right
;
676 t_key m
= TKEY_GET_MASK(inode
->pos
, 1);
678 left
= tnode_new(inode
->key
&(~m
), inode
->pos
+ 1,
683 right
= tnode_new(inode
->key
|m
, inode
->pos
+ 1,
691 put_child(t
, tn
, 2*i
, (struct node
*) left
);
692 put_child(t
, tn
, 2*i
+1, (struct node
*) right
);
696 for (i
= 0; i
< olen
; i
++) {
697 struct node
*node
= tnode_get_child(oldtnode
, i
);
698 struct tnode
*left
, *right
;
705 /* A leaf or an internal node with skipped bits */
707 if (IS_LEAF(node
) || ((struct tnode
*) node
)->pos
>
708 tn
->pos
+ tn
->bits
- 1) {
709 if (tkey_extract_bits(node
->key
, oldtnode
->pos
+ oldtnode
->bits
,
711 put_child(t
, tn
, 2*i
, node
);
713 put_child(t
, tn
, 2*i
+1, node
);
717 /* An internal node with two children */
718 inode
= (struct tnode
*) node
;
720 if (inode
->bits
== 1) {
721 put_child(t
, tn
, 2*i
, inode
->child
[0]);
722 put_child(t
, tn
, 2*i
+1, inode
->child
[1]);
728 /* An internal node with more than two children */
730 /* We will replace this node 'inode' with two new
731 * ones, 'left' and 'right', each with half of the
732 * original children. The two new nodes will have
733 * a position one bit further down the key and this
734 * means that the "significant" part of their keys
735 * (see the discussion near the top of this file)
736 * will differ by one bit, which will be "0" in
737 * left's key and "1" in right's key. Since we are
738 * moving the key position by one step, the bit that
739 * we are moving away from - the bit at position
740 * (inode->pos) - is the one that will differ between
741 * left and right. So... we synthesize that bit in the
743 * The mask 'm' below will be a single "one" bit at
744 * the position (inode->pos)
747 /* Use the old key, but set the new significant
751 left
= (struct tnode
*) tnode_get_child(tn
, 2*i
);
752 put_child(t
, tn
, 2*i
, NULL
);
756 right
= (struct tnode
*) tnode_get_child(tn
, 2*i
+1);
757 put_child(t
, tn
, 2*i
+1, NULL
);
761 size
= tnode_child_length(left
);
762 for (j
= 0; j
< size
; j
++) {
763 put_child(t
, left
, j
, inode
->child
[j
]);
764 put_child(t
, right
, j
, inode
->child
[j
+ size
]);
766 put_child(t
, tn
, 2*i
, resize(t
, left
));
767 put_child(t
, tn
, 2*i
+1, resize(t
, right
));
771 tnode_free(oldtnode
);
775 int size
= tnode_child_length(tn
);
778 for (j
= 0; j
< size
; j
++)
780 tnode_free((struct tnode
*)tn
->child
[j
]);
784 return ERR_PTR(-ENOMEM
);
788 static struct tnode
*halve(struct trie
*t
, struct tnode
*tn
)
790 struct tnode
*oldtnode
= tn
;
791 struct node
*left
, *right
;
793 int olen
= tnode_child_length(tn
);
795 pr_debug("In halve\n");
797 tn
= tnode_new(oldtnode
->key
, oldtnode
->pos
, oldtnode
->bits
- 1);
800 return ERR_PTR(-ENOMEM
);
803 * Preallocate and store tnodes before the actual work so we
804 * don't get into an inconsistent state if memory allocation
805 * fails. In case of failure we return the oldnode and halve
806 * of tnode is ignored.
809 for (i
= 0; i
< olen
; i
+= 2) {
810 left
= tnode_get_child(oldtnode
, i
);
811 right
= tnode_get_child(oldtnode
, i
+1);
813 /* Two nonempty children */
817 newn
= tnode_new(left
->key
, tn
->pos
+ tn
->bits
, 1);
822 put_child(t
, tn
, i
/2, (struct node
*)newn
);
827 for (i
= 0; i
< olen
; i
+= 2) {
828 struct tnode
*newBinNode
;
830 left
= tnode_get_child(oldtnode
, i
);
831 right
= tnode_get_child(oldtnode
, i
+1);
833 /* At least one of the children is empty */
835 if (right
== NULL
) /* Both are empty */
837 put_child(t
, tn
, i
/2, right
);
842 put_child(t
, tn
, i
/2, left
);
846 /* Two nonempty children */
847 newBinNode
= (struct tnode
*) tnode_get_child(tn
, i
/2);
848 put_child(t
, tn
, i
/2, NULL
);
849 put_child(t
, newBinNode
, 0, left
);
850 put_child(t
, newBinNode
, 1, right
);
851 put_child(t
, tn
, i
/2, resize(t
, newBinNode
));
853 tnode_free(oldtnode
);
857 int size
= tnode_child_length(tn
);
860 for (j
= 0; j
< size
; j
++)
862 tnode_free((struct tnode
*)tn
->child
[j
]);
866 return ERR_PTR(-ENOMEM
);
870 static void trie_init(struct trie
*t
)
876 rcu_assign_pointer(t
->trie
, NULL
);
878 #ifdef CONFIG_IP_FIB_TRIE_STATS
879 memset(&t
->stats
, 0, sizeof(struct trie_use_stats
));
883 /* readside must use rcu_read_lock currently dump routines
884 via get_fa_head and dump */
886 static struct leaf_info
*find_leaf_info(struct leaf
*l
, int plen
)
888 struct hlist_head
*head
= &l
->list
;
889 struct hlist_node
*node
;
890 struct leaf_info
*li
;
892 hlist_for_each_entry_rcu(li
, node
, head
, hlist
)
893 if (li
->plen
== plen
)
899 static inline struct list_head
* get_fa_head(struct leaf
*l
, int plen
)
901 struct leaf_info
*li
= find_leaf_info(l
, plen
);
909 static void insert_leaf_info(struct hlist_head
*head
, struct leaf_info
*new)
911 struct leaf_info
*li
= NULL
, *last
= NULL
;
912 struct hlist_node
*node
;
914 if (hlist_empty(head
)) {
915 hlist_add_head_rcu(&new->hlist
, head
);
917 hlist_for_each_entry(li
, node
, head
, hlist
) {
918 if (new->plen
> li
->plen
)
924 hlist_add_after_rcu(&last
->hlist
, &new->hlist
);
926 hlist_add_before_rcu(&new->hlist
, &li
->hlist
);
930 /* rcu_read_lock needs to be hold by caller from readside */
933 fib_find_node(struct trie
*t
, u32 key
)
940 n
= rcu_dereference(t
->trie
);
942 while (n
!= NULL
&& NODE_TYPE(n
) == T_TNODE
) {
943 tn
= (struct tnode
*) n
;
947 if (tkey_sub_equals(tn
->key
, pos
, tn
->pos
-pos
, key
)) {
948 pos
= tn
->pos
+ tn
->bits
;
949 n
= tnode_get_child(tn
, tkey_extract_bits(key
, tn
->pos
, tn
->bits
));
953 /* Case we have found a leaf. Compare prefixes */
955 if (n
!= NULL
&& IS_LEAF(n
) && tkey_equals(key
, n
->key
))
956 return (struct leaf
*)n
;
961 static struct node
*trie_rebalance(struct trie
*t
, struct tnode
*tn
)
965 struct tnode
*tp
= NULL
;
969 while (tn
!= NULL
&& NODE_PARENT(tn
) != NULL
) {
971 tp
= NODE_PARENT(tn
);
972 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
973 wasfull
= tnode_full(tp
, tnode_get_child(tp
, cindex
));
974 tn
= (struct tnode
*) resize (t
, (struct tnode
*)tn
);
975 tnode_put_child_reorg((struct tnode
*)tp
, cindex
,(struct node
*)tn
, wasfull
);
977 if (!NODE_PARENT(tn
))
980 tn
= NODE_PARENT(tn
);
982 /* Handle last (top) tnode */
984 tn
= (struct tnode
*) resize(t
, (struct tnode
*)tn
);
986 return (struct node
*) tn
;
989 /* only used from updater-side */
991 static struct list_head
*
992 fib_insert_node(struct trie
*t
, int *err
, u32 key
, int plen
)
995 struct tnode
*tp
= NULL
, *tn
= NULL
;
999 struct list_head
*fa_head
= NULL
;
1000 struct leaf_info
*li
;
1006 /* If we point to NULL, stop. Either the tree is empty and we should
1007 * just put a new leaf in if, or we have reached an empty child slot,
1008 * and we should just put our new leaf in that.
1009 * If we point to a T_TNODE, check if it matches our key. Note that
1010 * a T_TNODE might be skipping any number of bits - its 'pos' need
1011 * not be the parent's 'pos'+'bits'!
1013 * If it does match the current key, get pos/bits from it, extract
1014 * the index from our key, push the T_TNODE and walk the tree.
1016 * If it doesn't, we have to replace it with a new T_TNODE.
1018 * If we point to a T_LEAF, it might or might not have the same key
1019 * as we do. If it does, just change the value, update the T_LEAF's
1020 * value, and return it.
1021 * If it doesn't, we need to replace it with a T_TNODE.
1024 while (n
!= NULL
&& NODE_TYPE(n
) == T_TNODE
) {
1025 tn
= (struct tnode
*) n
;
1029 if (tkey_sub_equals(tn
->key
, pos
, tn
->pos
-pos
, key
)) {
1031 pos
= tn
->pos
+ tn
->bits
;
1032 n
= tnode_get_child(tn
, tkey_extract_bits(key
, tn
->pos
, tn
->bits
));
1034 BUG_ON(n
&& NODE_PARENT(n
) != tn
);
1040 * n ----> NULL, LEAF or TNODE
1042 * tp is n's (parent) ----> NULL or TNODE
1045 BUG_ON(tp
&& IS_LEAF(tp
));
1047 /* Case 1: n is a leaf. Compare prefixes */
1049 if (n
!= NULL
&& IS_LEAF(n
) && tkey_equals(key
, n
->key
)) {
1050 struct leaf
*l
= (struct leaf
*) n
;
1052 li
= leaf_info_new(plen
);
1059 fa_head
= &li
->falh
;
1060 insert_leaf_info(&l
->list
, li
);
1072 li
= leaf_info_new(plen
);
1075 tnode_free((struct tnode
*) l
);
1080 fa_head
= &li
->falh
;
1081 insert_leaf_info(&l
->list
, li
);
1083 if (t
->trie
&& n
== NULL
) {
1084 /* Case 2: n is NULL, and will just insert a new leaf */
1086 NODE_SET_PARENT(l
, tp
);
1088 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1089 put_child(t
, (struct tnode
*)tp
, cindex
, (struct node
*)l
);
1091 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1093 * Add a new tnode here
1094 * first tnode need some special handling
1098 pos
= tp
->pos
+tp
->bits
;
1103 newpos
= tkey_mismatch(key
, pos
, n
->key
);
1104 tn
= tnode_new(n
->key
, newpos
, 1);
1107 tn
= tnode_new(key
, newpos
, 1); /* First tnode */
1112 tnode_free((struct tnode
*) l
);
1117 NODE_SET_PARENT(tn
, tp
);
1119 missbit
= tkey_extract_bits(key
, newpos
, 1);
1120 put_child(t
, tn
, missbit
, (struct node
*)l
);
1121 put_child(t
, tn
, 1-missbit
, n
);
1124 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1125 put_child(t
, (struct tnode
*)tp
, cindex
, (struct node
*)tn
);
1127 rcu_assign_pointer(t
->trie
, (struct node
*)tn
); /* First tnode */
1132 if (tp
&& tp
->pos
+ tp
->bits
> 32)
1133 printk(KERN_WARNING
"fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1134 tp
, tp
->pos
, tp
->bits
, key
, plen
);
1136 /* Rebalance the trie */
1138 rcu_assign_pointer(t
->trie
, trie_rebalance(t
, tp
));
1146 * Caller must hold RTNL.
1148 static int fn_trie_insert(struct fib_table
*tb
, struct fib_config
*cfg
)
1150 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1151 struct fib_alias
*fa
, *new_fa
;
1152 struct list_head
*fa_head
= NULL
;
1153 struct fib_info
*fi
;
1154 int plen
= cfg
->fc_dst_len
;
1155 u8 tos
= cfg
->fc_tos
;
1163 key
= ntohl(cfg
->fc_dst
);
1165 pr_debug("Insert table=%u %08x/%d\n", tb
->tb_id
, key
, plen
);
1167 mask
= ntohl(inet_make_mask(plen
));
1174 fi
= fib_create_info(cfg
);
1180 l
= fib_find_node(t
, key
);
1184 fa_head
= get_fa_head(l
, plen
);
1185 fa
= fib_find_alias(fa_head
, tos
, fi
->fib_priority
);
1188 /* Now fa, if non-NULL, points to the first fib alias
1189 * with the same keys [prefix,tos,priority], if such key already
1190 * exists or to the node before which we will insert new one.
1192 * If fa is NULL, we will need to allocate a new one and
1193 * insert to the head of f.
1195 * If f is NULL, no fib node matched the destination key
1196 * and we need to allocate a new one of those as well.
1199 if (fa
&& fa
->fa_info
->fib_priority
== fi
->fib_priority
) {
1200 struct fib_alias
*fa_orig
;
1203 if (cfg
->fc_nlflags
& NLM_F_EXCL
)
1206 if (cfg
->fc_nlflags
& NLM_F_REPLACE
) {
1207 struct fib_info
*fi_drop
;
1211 new_fa
= kmem_cache_alloc(fn_alias_kmem
, GFP_KERNEL
);
1215 fi_drop
= fa
->fa_info
;
1216 new_fa
->fa_tos
= fa
->fa_tos
;
1217 new_fa
->fa_info
= fi
;
1218 new_fa
->fa_type
= cfg
->fc_type
;
1219 new_fa
->fa_scope
= cfg
->fc_scope
;
1220 state
= fa
->fa_state
;
1221 new_fa
->fa_state
&= ~FA_S_ACCESSED
;
1223 list_replace_rcu(&fa
->fa_list
, &new_fa
->fa_list
);
1224 alias_free_mem_rcu(fa
);
1226 fib_release_info(fi_drop
);
1227 if (state
& FA_S_ACCESSED
)
1229 rtmsg_fib(RTM_NEWROUTE
, htonl(key
), new_fa
, plen
,
1230 tb
->tb_id
, &cfg
->fc_nlinfo
, NLM_F_REPLACE
);
1234 /* Error if we find a perfect match which
1235 * uses the same scope, type, and nexthop
1239 list_for_each_entry(fa
, fa_orig
->fa_list
.prev
, fa_list
) {
1240 if (fa
->fa_tos
!= tos
)
1242 if (fa
->fa_info
->fib_priority
!= fi
->fib_priority
)
1244 if (fa
->fa_type
== cfg
->fc_type
&&
1245 fa
->fa_scope
== cfg
->fc_scope
&&
1246 fa
->fa_info
== fi
) {
1250 if (!(cfg
->fc_nlflags
& NLM_F_APPEND
))
1254 if (!(cfg
->fc_nlflags
& NLM_F_CREATE
))
1258 new_fa
= kmem_cache_alloc(fn_alias_kmem
, GFP_KERNEL
);
1262 new_fa
->fa_info
= fi
;
1263 new_fa
->fa_tos
= tos
;
1264 new_fa
->fa_type
= cfg
->fc_type
;
1265 new_fa
->fa_scope
= cfg
->fc_scope
;
1266 new_fa
->fa_state
= 0;
1268 * Insert new entry to the list.
1273 fa_head
= fib_insert_node(t
, &err
, key
, plen
);
1275 goto out_free_new_fa
;
1278 list_add_tail_rcu(&new_fa
->fa_list
,
1279 (fa
? &fa
->fa_list
: fa_head
));
1282 rtmsg_fib(RTM_NEWROUTE
, htonl(key
), new_fa
, plen
, tb
->tb_id
,
1283 &cfg
->fc_nlinfo
, 0);
1288 kmem_cache_free(fn_alias_kmem
, new_fa
);
1290 fib_release_info(fi
);
1296 /* should be called with rcu_read_lock */
1297 static inline int check_leaf(struct trie
*t
, struct leaf
*l
,
1298 t_key key
, int *plen
, const struct flowi
*flp
,
1299 struct fib_result
*res
)
1303 struct leaf_info
*li
;
1304 struct hlist_head
*hhead
= &l
->list
;
1305 struct hlist_node
*node
;
1307 hlist_for_each_entry_rcu(li
, node
, hhead
, hlist
) {
1309 mask
= inet_make_mask(i
);
1310 if (l
->key
!= (key
& ntohl(mask
)))
1313 if ((err
= fib_semantic_match(&li
->falh
, flp
, res
, htonl(l
->key
), mask
, i
)) <= 0) {
1315 #ifdef CONFIG_IP_FIB_TRIE_STATS
1316 t
->stats
.semantic_match_passed
++;
1320 #ifdef CONFIG_IP_FIB_TRIE_STATS
1321 t
->stats
.semantic_match_miss
++;
1328 fn_trie_lookup(struct fib_table
*tb
, const struct flowi
*flp
, struct fib_result
*res
)
1330 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1335 t_key key
= ntohl(flp
->fl4_dst
);
1338 int current_prefix_length
= KEYLENGTH
;
1340 t_key node_prefix
, key_prefix
, pref_mismatch
;
1345 n
= rcu_dereference(t
->trie
);
1349 #ifdef CONFIG_IP_FIB_TRIE_STATS
1355 if ((ret
= check_leaf(t
, (struct leaf
*)n
, key
, &plen
, flp
, res
)) <= 0)
1359 pn
= (struct tnode
*) n
;
1367 cindex
= tkey_extract_bits(MASK_PFX(key
, current_prefix_length
), pos
, bits
);
1369 n
= tnode_get_child(pn
, cindex
);
1372 #ifdef CONFIG_IP_FIB_TRIE_STATS
1373 t
->stats
.null_node_hit
++;
1379 if ((ret
= check_leaf(t
, (struct leaf
*)n
, key
, &plen
, flp
, res
)) <= 0)
1387 cn
= (struct tnode
*)n
;
1390 * It's a tnode, and we can do some extra checks here if we
1391 * like, to avoid descending into a dead-end branch.
1392 * This tnode is in the parent's child array at index
1393 * key[p_pos..p_pos+p_bits] but potentially with some bits
1394 * chopped off, so in reality the index may be just a
1395 * subprefix, padded with zero at the end.
1396 * We can also take a look at any skipped bits in this
1397 * tnode - everything up to p_pos is supposed to be ok,
1398 * and the non-chopped bits of the index (se previous
1399 * paragraph) are also guaranteed ok, but the rest is
1400 * considered unknown.
1402 * The skipped bits are key[pos+bits..cn->pos].
1405 /* If current_prefix_length < pos+bits, we are already doing
1406 * actual prefix matching, which means everything from
1407 * pos+(bits-chopped_off) onward must be zero along some
1408 * branch of this subtree - otherwise there is *no* valid
1409 * prefix present. Here we can only check the skipped
1410 * bits. Remember, since we have already indexed into the
1411 * parent's child array, we know that the bits we chopped of
1415 /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */
1417 if (current_prefix_length
< pos
+bits
) {
1418 if (tkey_extract_bits(cn
->key
, current_prefix_length
,
1419 cn
->pos
- current_prefix_length
) != 0 ||
1425 * If chopped_off=0, the index is fully validated and we
1426 * only need to look at the skipped bits for this, the new,
1427 * tnode. What we actually want to do is to find out if
1428 * these skipped bits match our key perfectly, or if we will
1429 * have to count on finding a matching prefix further down,
1430 * because if we do, we would like to have some way of
1431 * verifying the existence of such a prefix at this point.
1434 /* The only thing we can do at this point is to verify that
1435 * any such matching prefix can indeed be a prefix to our
1436 * key, and if the bits in the node we are inspecting that
1437 * do not match our key are not ZERO, this cannot be true.
1438 * Thus, find out where there is a mismatch (before cn->pos)
1439 * and verify that all the mismatching bits are zero in the
1443 /* Note: We aren't very concerned about the piece of the key
1444 * that precede pn->pos+pn->bits, since these have already been
1445 * checked. The bits after cn->pos aren't checked since these are
1446 * by definition "unknown" at this point. Thus, what we want to
1447 * see is if we are about to enter the "prefix matching" state,
1448 * and in that case verify that the skipped bits that will prevail
1449 * throughout this subtree are zero, as they have to be if we are
1450 * to find a matching prefix.
1453 node_prefix
= MASK_PFX(cn
->key
, cn
->pos
);
1454 key_prefix
= MASK_PFX(key
, cn
->pos
);
1455 pref_mismatch
= key_prefix
^node_prefix
;
1458 /* In short: If skipped bits in this node do not match the search
1459 * key, enter the "prefix matching" state.directly.
1461 if (pref_mismatch
) {
1462 while (!(pref_mismatch
& (1<<(KEYLENGTH
-1)))) {
1464 pref_mismatch
= pref_mismatch
<<1;
1466 key_prefix
= tkey_extract_bits(cn
->key
, mp
, cn
->pos
-mp
);
1468 if (key_prefix
!= 0)
1471 if (current_prefix_length
>= cn
->pos
)
1472 current_prefix_length
= mp
;
1475 pn
= (struct tnode
*)n
; /* Descend */
1482 /* As zero don't change the child key (cindex) */
1483 while ((chopped_off
<= pn
->bits
) && !(cindex
& (1<<(chopped_off
-1))))
1486 /* Decrease current_... with bits chopped off */
1487 if (current_prefix_length
> pn
->pos
+ pn
->bits
- chopped_off
)
1488 current_prefix_length
= pn
->pos
+ pn
->bits
- chopped_off
;
1491 * Either we do the actual chop off according or if we have
1492 * chopped off all bits in this tnode walk up to our parent.
1495 if (chopped_off
<= pn
->bits
) {
1496 cindex
&= ~(1 << (chopped_off
-1));
1498 if (NODE_PARENT(pn
) == NULL
)
1501 /* Get Child's index */
1502 cindex
= tkey_extract_bits(pn
->key
, NODE_PARENT(pn
)->pos
, NODE_PARENT(pn
)->bits
);
1503 pn
= NODE_PARENT(pn
);
1506 #ifdef CONFIG_IP_FIB_TRIE_STATS
1507 t
->stats
.backtrack
++;
1519 /* only called from updater side */
1520 static int trie_leaf_remove(struct trie
*t
, t_key key
)
1523 struct tnode
*tp
= NULL
;
1524 struct node
*n
= t
->trie
;
1527 pr_debug("entering trie_leaf_remove(%p)\n", n
);
1529 /* Note that in the case skipped bits, those bits are *not* checked!
1530 * When we finish this, we will have NULL or a T_LEAF, and the
1531 * T_LEAF may or may not match our key.
1534 while (n
!= NULL
&& IS_TNODE(n
)) {
1535 struct tnode
*tn
= (struct tnode
*) n
;
1537 n
= tnode_get_child(tn
,tkey_extract_bits(key
, tn
->pos
, tn
->bits
));
1539 BUG_ON(n
&& NODE_PARENT(n
) != tn
);
1541 l
= (struct leaf
*) n
;
1543 if (!n
|| !tkey_equals(l
->key
, key
))
1548 * Remove the leaf and rebalance the tree
1554 tp
= NODE_PARENT(n
);
1555 tnode_free((struct tnode
*) n
);
1558 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1559 put_child(t
, (struct tnode
*)tp
, cindex
, NULL
);
1560 rcu_assign_pointer(t
->trie
, trie_rebalance(t
, tp
));
1562 rcu_assign_pointer(t
->trie
, NULL
);
1568 * Caller must hold RTNL.
1570 static int fn_trie_delete(struct fib_table
*tb
, struct fib_config
*cfg
)
1572 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1574 int plen
= cfg
->fc_dst_len
;
1575 u8 tos
= cfg
->fc_tos
;
1576 struct fib_alias
*fa
, *fa_to_delete
;
1577 struct list_head
*fa_head
;
1579 struct leaf_info
*li
;
1584 key
= ntohl(cfg
->fc_dst
);
1585 mask
= ntohl(inet_make_mask(plen
));
1591 l
= fib_find_node(t
, key
);
1596 fa_head
= get_fa_head(l
, plen
);
1597 fa
= fib_find_alias(fa_head
, tos
, 0);
1602 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key
, plen
, tos
, t
);
1604 fa_to_delete
= NULL
;
1605 fa_head
= fa
->fa_list
.prev
;
1607 list_for_each_entry(fa
, fa_head
, fa_list
) {
1608 struct fib_info
*fi
= fa
->fa_info
;
1610 if (fa
->fa_tos
!= tos
)
1613 if ((!cfg
->fc_type
|| fa
->fa_type
== cfg
->fc_type
) &&
1614 (cfg
->fc_scope
== RT_SCOPE_NOWHERE
||
1615 fa
->fa_scope
== cfg
->fc_scope
) &&
1616 (!cfg
->fc_protocol
||
1617 fi
->fib_protocol
== cfg
->fc_protocol
) &&
1618 fib_nh_match(cfg
, fi
) == 0) {
1628 rtmsg_fib(RTM_DELROUTE
, htonl(key
), fa
, plen
, tb
->tb_id
,
1629 &cfg
->fc_nlinfo
, 0);
1631 l
= fib_find_node(t
, key
);
1632 li
= find_leaf_info(l
, plen
);
1634 list_del_rcu(&fa
->fa_list
);
1636 if (list_empty(fa_head
)) {
1637 hlist_del_rcu(&li
->hlist
);
1641 if (hlist_empty(&l
->list
))
1642 trie_leaf_remove(t
, key
);
1644 if (fa
->fa_state
& FA_S_ACCESSED
)
1647 fib_release_info(fa
->fa_info
);
1648 alias_free_mem_rcu(fa
);
1652 static int trie_flush_list(struct trie
*t
, struct list_head
*head
)
1654 struct fib_alias
*fa
, *fa_node
;
1657 list_for_each_entry_safe(fa
, fa_node
, head
, fa_list
) {
1658 struct fib_info
*fi
= fa
->fa_info
;
1660 if (fi
&& (fi
->fib_flags
& RTNH_F_DEAD
)) {
1661 list_del_rcu(&fa
->fa_list
);
1662 fib_release_info(fa
->fa_info
);
1663 alias_free_mem_rcu(fa
);
1670 static int trie_flush_leaf(struct trie
*t
, struct leaf
*l
)
1673 struct hlist_head
*lih
= &l
->list
;
1674 struct hlist_node
*node
, *tmp
;
1675 struct leaf_info
*li
= NULL
;
1677 hlist_for_each_entry_safe(li
, node
, tmp
, lih
, hlist
) {
1678 found
+= trie_flush_list(t
, &li
->falh
);
1680 if (list_empty(&li
->falh
)) {
1681 hlist_del_rcu(&li
->hlist
);
1688 /* rcu_read_lock needs to be hold by caller from readside */
1690 static struct leaf
*nextleaf(struct trie
*t
, struct leaf
*thisleaf
)
1692 struct node
*c
= (struct node
*) thisleaf
;
1695 struct node
*trie
= rcu_dereference(t
->trie
);
1701 if (IS_LEAF(trie
)) /* trie w. just a leaf */
1702 return (struct leaf
*) trie
;
1704 p
= (struct tnode
*) trie
; /* Start */
1706 p
= (struct tnode
*) NODE_PARENT(c
);
1711 /* Find the next child of the parent */
1713 pos
= 1 + tkey_extract_bits(c
->key
, p
->pos
, p
->bits
);
1717 last
= 1 << p
->bits
;
1718 for (idx
= pos
; idx
< last
; idx
++) {
1719 c
= rcu_dereference(p
->child
[idx
]);
1724 /* Decend if tnode */
1725 while (IS_TNODE(c
)) {
1726 p
= (struct tnode
*) c
;
1729 /* Rightmost non-NULL branch */
1730 if (p
&& IS_TNODE(p
))
1731 while (!(c
= rcu_dereference(p
->child
[idx
]))
1732 && idx
< (1<<p
->bits
)) idx
++;
1734 /* Done with this tnode? */
1735 if (idx
>= (1 << p
->bits
) || !c
)
1738 return (struct leaf
*) c
;
1741 /* No more children go up one step */
1742 c
= (struct node
*) p
;
1743 p
= (struct tnode
*) NODE_PARENT(p
);
1745 return NULL
; /* Ready. Root of trie */
1749 * Caller must hold RTNL.
1751 static int fn_trie_flush(struct fib_table
*tb
)
1753 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1754 struct leaf
*ll
= NULL
, *l
= NULL
;
1759 for (h
= 0; (l
= nextleaf(t
, l
)) != NULL
; h
++) {
1760 found
+= trie_flush_leaf(t
, l
);
1762 if (ll
&& hlist_empty(&ll
->list
))
1763 trie_leaf_remove(t
, ll
->key
);
1767 if (ll
&& hlist_empty(&ll
->list
))
1768 trie_leaf_remove(t
, ll
->key
);
1770 pr_debug("trie_flush found=%d\n", found
);
1775 fn_trie_select_default(struct fib_table
*tb
, const struct flowi
*flp
, struct fib_result
*res
)
1777 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1778 int order
, last_idx
;
1779 struct fib_info
*fi
= NULL
;
1780 struct fib_info
*last_resort
;
1781 struct fib_alias
*fa
= NULL
;
1782 struct list_head
*fa_head
;
1791 l
= fib_find_node(t
, 0);
1795 fa_head
= get_fa_head(l
, 0);
1799 if (list_empty(fa_head
))
1802 list_for_each_entry_rcu(fa
, fa_head
, fa_list
) {
1803 struct fib_info
*next_fi
= fa
->fa_info
;
1805 if (fa
->fa_scope
!= res
->scope
||
1806 fa
->fa_type
!= RTN_UNICAST
)
1809 if (next_fi
->fib_priority
> res
->fi
->fib_priority
)
1811 if (!next_fi
->fib_nh
[0].nh_gw
||
1812 next_fi
->fib_nh
[0].nh_scope
!= RT_SCOPE_LINK
)
1814 fa
->fa_state
|= FA_S_ACCESSED
;
1817 if (next_fi
!= res
->fi
)
1819 } else if (!fib_detect_death(fi
, order
, &last_resort
,
1820 &last_idx
, &tb
->tb_default
)) {
1821 fib_result_assign(res
, fi
);
1822 tb
->tb_default
= order
;
1828 if (order
<= 0 || fi
== NULL
) {
1829 tb
->tb_default
= -1;
1833 if (!fib_detect_death(fi
, order
, &last_resort
, &last_idx
, &tb
->tb_default
)) {
1834 fib_result_assign(res
, fi
);
1835 tb
->tb_default
= order
;
1839 fib_result_assign(res
, last_resort
);
1840 tb
->tb_default
= last_idx
;
1845 static int fn_trie_dump_fa(t_key key
, int plen
, struct list_head
*fah
, struct fib_table
*tb
,
1846 struct sk_buff
*skb
, struct netlink_callback
*cb
)
1849 struct fib_alias
*fa
;
1851 __be32 xkey
= htonl(key
);
1856 /* rcu_read_lock is hold by caller */
1858 list_for_each_entry_rcu(fa
, fah
, fa_list
) {
1863 BUG_ON(!fa
->fa_info
);
1865 if (fib_dump_info(skb
, NETLINK_CB(cb
->skb
).pid
,
1874 fa
->fa_info
, 0) < 0) {
1884 static int fn_trie_dump_plen(struct trie
*t
, int plen
, struct fib_table
*tb
, struct sk_buff
*skb
,
1885 struct netlink_callback
*cb
)
1888 struct list_head
*fa_head
;
1889 struct leaf
*l
= NULL
;
1893 for (h
= 0; (l
= nextleaf(t
, l
)) != NULL
; h
++) {
1897 memset(&cb
->args
[4], 0,
1898 sizeof(cb
->args
) - 4*sizeof(cb
->args
[0]));
1900 fa_head
= get_fa_head(l
, plen
);
1905 if (list_empty(fa_head
))
1908 if (fn_trie_dump_fa(l
->key
, plen
, fa_head
, tb
, skb
, cb
)<0) {
1917 static int fn_trie_dump(struct fib_table
*tb
, struct sk_buff
*skb
, struct netlink_callback
*cb
)
1920 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1925 for (m
= 0; m
<= 32; m
++) {
1929 memset(&cb
->args
[3], 0,
1930 sizeof(cb
->args
) - 3*sizeof(cb
->args
[0]));
1932 if (fn_trie_dump_plen(t
, 32-m
, tb
, skb
, cb
)<0) {
1945 /* Fix more generic FIB names for init later */
1947 #ifdef CONFIG_IP_MULTIPLE_TABLES
1948 struct fib_table
* fib_hash_init(u32 id
)
1950 struct fib_table
* __init
fib_hash_init(u32 id
)
1953 struct fib_table
*tb
;
1956 if (fn_alias_kmem
== NULL
)
1957 fn_alias_kmem
= kmem_cache_create("ip_fib_alias",
1958 sizeof(struct fib_alias
),
1959 0, SLAB_HWCACHE_ALIGN
,
1962 tb
= kmalloc(sizeof(struct fib_table
) + sizeof(struct trie
),
1968 tb
->tb_default
= -1;
1969 tb
->tb_lookup
= fn_trie_lookup
;
1970 tb
->tb_insert
= fn_trie_insert
;
1971 tb
->tb_delete
= fn_trie_delete
;
1972 tb
->tb_flush
= fn_trie_flush
;
1973 tb
->tb_select_default
= fn_trie_select_default
;
1974 tb
->tb_dump
= fn_trie_dump
;
1975 memset(tb
->tb_data
, 0, sizeof(struct trie
));
1977 t
= (struct trie
*) tb
->tb_data
;
1981 if (id
== RT_TABLE_LOCAL
)
1983 else if (id
== RT_TABLE_MAIN
)
1986 if (id
== RT_TABLE_LOCAL
)
1987 printk(KERN_INFO
"IPv4 FIB: Using LC-trie version %s\n", VERSION
);
1992 #ifdef CONFIG_PROC_FS
1993 /* Depth first Trie walk iterator */
1994 struct fib_trie_iter
{
1995 struct tnode
*tnode
;
2001 static struct node
*fib_trie_get_next(struct fib_trie_iter
*iter
)
2003 struct tnode
*tn
= iter
->tnode
;
2004 unsigned cindex
= iter
->index
;
2007 /* A single entry routing table */
2011 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2012 iter
->tnode
, iter
->index
, iter
->depth
);
2014 while (cindex
< (1<<tn
->bits
)) {
2015 struct node
*n
= tnode_get_child(tn
, cindex
);
2020 iter
->index
= cindex
+ 1;
2022 /* push down one level */
2023 iter
->tnode
= (struct tnode
*) n
;
2033 /* Current node exhausted, pop back up */
2034 p
= NODE_PARENT(tn
);
2036 cindex
= tkey_extract_bits(tn
->key
, p
->pos
, p
->bits
)+1;
2046 static struct node
*fib_trie_get_first(struct fib_trie_iter
*iter
,
2054 n
= rcu_dereference(t
->trie
);
2061 iter
->tnode
= (struct tnode
*) n
;
2076 static void trie_collect_stats(struct trie
*t
, struct trie_stat
*s
)
2079 struct fib_trie_iter iter
;
2081 memset(s
, 0, sizeof(*s
));
2084 for (n
= fib_trie_get_first(&iter
, t
); n
;
2085 n
= fib_trie_get_next(&iter
)) {
2088 s
->totdepth
+= iter
.depth
;
2089 if (iter
.depth
> s
->maxdepth
)
2090 s
->maxdepth
= iter
.depth
;
2092 const struct tnode
*tn
= (const struct tnode
*) n
;
2096 if (tn
->bits
< MAX_STAT_DEPTH
)
2097 s
->nodesizes
[tn
->bits
]++;
2099 for (i
= 0; i
< (1<<tn
->bits
); i
++)
2108 * This outputs /proc/net/fib_triestats
2110 static void trie_show_stats(struct seq_file
*seq
, struct trie_stat
*stat
)
2112 unsigned i
, max
, pointers
, bytes
, avdepth
;
2115 avdepth
= stat
->totdepth
*100 / stat
->leaves
;
2119 seq_printf(seq
, "\tAver depth: %d.%02d\n", avdepth
/ 100, avdepth
% 100 );
2120 seq_printf(seq
, "\tMax depth: %u\n", stat
->maxdepth
);
2122 seq_printf(seq
, "\tLeaves: %u\n", stat
->leaves
);
2124 bytes
= sizeof(struct leaf
) * stat
->leaves
;
2125 seq_printf(seq
, "\tInternal nodes: %d\n\t", stat
->tnodes
);
2126 bytes
+= sizeof(struct tnode
) * stat
->tnodes
;
2128 max
= MAX_STAT_DEPTH
;
2129 while (max
> 0 && stat
->nodesizes
[max
-1] == 0)
2133 for (i
= 1; i
<= max
; i
++)
2134 if (stat
->nodesizes
[i
] != 0) {
2135 seq_printf(seq
, " %d: %d", i
, stat
->nodesizes
[i
]);
2136 pointers
+= (1<<i
) * stat
->nodesizes
[i
];
2138 seq_putc(seq
, '\n');
2139 seq_printf(seq
, "\tPointers: %d\n", pointers
);
2141 bytes
+= sizeof(struct node
*) * pointers
;
2142 seq_printf(seq
, "Null ptrs: %d\n", stat
->nullpointers
);
2143 seq_printf(seq
, "Total size: %d kB\n", (bytes
+ 1023) / 1024);
2145 #ifdef CONFIG_IP_FIB_TRIE_STATS
2146 seq_printf(seq
, "Counters:\n---------\n");
2147 seq_printf(seq
,"gets = %d\n", t
->stats
.gets
);
2148 seq_printf(seq
,"backtracks = %d\n", t
->stats
.backtrack
);
2149 seq_printf(seq
,"semantic match passed = %d\n", t
->stats
.semantic_match_passed
);
2150 seq_printf(seq
,"semantic match miss = %d\n", t
->stats
.semantic_match_miss
);
2151 seq_printf(seq
,"null node hit= %d\n", t
->stats
.null_node_hit
);
2152 seq_printf(seq
,"skipped node resize = %d\n", t
->stats
.resize_node_skipped
);
2154 memset(&(t
->stats
), 0, sizeof(t
->stats
));
2156 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2159 static int fib_triestat_seq_show(struct seq_file
*seq
, void *v
)
2161 struct trie_stat
*stat
;
2163 stat
= kmalloc(sizeof(*stat
), GFP_KERNEL
);
2167 seq_printf(seq
, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
2168 sizeof(struct leaf
), sizeof(struct tnode
));
2171 seq_printf(seq
, "Local:\n");
2172 trie_collect_stats(trie_local
, stat
);
2173 trie_show_stats(seq
, stat
);
2177 seq_printf(seq
, "Main:\n");
2178 trie_collect_stats(trie_main
, stat
);
2179 trie_show_stats(seq
, stat
);
2186 static int fib_triestat_seq_open(struct inode
*inode
, struct file
*file
)
2188 return single_open(file
, fib_triestat_seq_show
, NULL
);
2191 static const struct file_operations fib_triestat_fops
= {
2192 .owner
= THIS_MODULE
,
2193 .open
= fib_triestat_seq_open
,
2195 .llseek
= seq_lseek
,
2196 .release
= single_release
,
2199 static struct node
*fib_trie_get_idx(struct fib_trie_iter
*iter
,
2205 for (n
= fib_trie_get_first(iter
, trie_local
);
2206 n
; ++idx
, n
= fib_trie_get_next(iter
)) {
2211 for (n
= fib_trie_get_first(iter
, trie_main
);
2212 n
; ++idx
, n
= fib_trie_get_next(iter
)) {
2219 static void *fib_trie_seq_start(struct seq_file
*seq
, loff_t
*pos
)
2223 return SEQ_START_TOKEN
;
2224 return fib_trie_get_idx(seq
->private, *pos
- 1);
2227 static void *fib_trie_seq_next(struct seq_file
*seq
, void *v
, loff_t
*pos
)
2229 struct fib_trie_iter
*iter
= seq
->private;
2233 if (v
== SEQ_START_TOKEN
)
2234 return fib_trie_get_idx(iter
, 0);
2236 v
= fib_trie_get_next(iter
);
2241 /* continue scan in next trie */
2242 if (iter
->trie
== trie_local
)
2243 return fib_trie_get_first(iter
, trie_main
);
2248 static void fib_trie_seq_stop(struct seq_file
*seq
, void *v
)
2253 static void seq_indent(struct seq_file
*seq
, int n
)
2255 while (n
-- > 0) seq_puts(seq
, " ");
2258 static inline const char *rtn_scope(enum rt_scope_t s
)
2260 static char buf
[32];
2263 case RT_SCOPE_UNIVERSE
: return "universe";
2264 case RT_SCOPE_SITE
: return "site";
2265 case RT_SCOPE_LINK
: return "link";
2266 case RT_SCOPE_HOST
: return "host";
2267 case RT_SCOPE_NOWHERE
: return "nowhere";
2269 snprintf(buf
, sizeof(buf
), "scope=%d", s
);
2274 static const char *rtn_type_names
[__RTN_MAX
] = {
2275 [RTN_UNSPEC
] = "UNSPEC",
2276 [RTN_UNICAST
] = "UNICAST",
2277 [RTN_LOCAL
] = "LOCAL",
2278 [RTN_BROADCAST
] = "BROADCAST",
2279 [RTN_ANYCAST
] = "ANYCAST",
2280 [RTN_MULTICAST
] = "MULTICAST",
2281 [RTN_BLACKHOLE
] = "BLACKHOLE",
2282 [RTN_UNREACHABLE
] = "UNREACHABLE",
2283 [RTN_PROHIBIT
] = "PROHIBIT",
2284 [RTN_THROW
] = "THROW",
2286 [RTN_XRESOLVE
] = "XRESOLVE",
2289 static inline const char *rtn_type(unsigned t
)
2291 static char buf
[32];
2293 if (t
< __RTN_MAX
&& rtn_type_names
[t
])
2294 return rtn_type_names
[t
];
2295 snprintf(buf
, sizeof(buf
), "type %d", t
);
2299 /* Pretty print the trie */
2300 static int fib_trie_seq_show(struct seq_file
*seq
, void *v
)
2302 const struct fib_trie_iter
*iter
= seq
->private;
2305 if (v
== SEQ_START_TOKEN
)
2308 if (!NODE_PARENT(n
)) {
2309 if (iter
->trie
== trie_local
)
2310 seq_puts(seq
, "<local>:\n");
2312 seq_puts(seq
, "<main>:\n");
2316 struct tnode
*tn
= (struct tnode
*) n
;
2317 __be32 prf
= htonl(MASK_PFX(tn
->key
, tn
->pos
));
2319 seq_indent(seq
, iter
->depth
-1);
2320 seq_printf(seq
, " +-- %d.%d.%d.%d/%d %d %d %d\n",
2321 NIPQUAD(prf
), tn
->pos
, tn
->bits
, tn
->full_children
,
2322 tn
->empty_children
);
2325 struct leaf
*l
= (struct leaf
*) n
;
2327 __be32 val
= htonl(l
->key
);
2329 seq_indent(seq
, iter
->depth
);
2330 seq_printf(seq
, " |-- %d.%d.%d.%d\n", NIPQUAD(val
));
2331 for (i
= 32; i
>= 0; i
--) {
2332 struct leaf_info
*li
= find_leaf_info(l
, i
);
2334 struct fib_alias
*fa
;
2335 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
2336 seq_indent(seq
, iter
->depth
+1);
2337 seq_printf(seq
, " /%d %s %s", i
,
2338 rtn_scope(fa
->fa_scope
),
2339 rtn_type(fa
->fa_type
));
2341 seq_printf(seq
, "tos =%d\n",
2343 seq_putc(seq
, '\n');
2352 static const struct seq_operations fib_trie_seq_ops
= {
2353 .start
= fib_trie_seq_start
,
2354 .next
= fib_trie_seq_next
,
2355 .stop
= fib_trie_seq_stop
,
2356 .show
= fib_trie_seq_show
,
2359 static int fib_trie_seq_open(struct inode
*inode
, struct file
*file
)
2361 struct seq_file
*seq
;
2363 struct fib_trie_iter
*s
= kmalloc(sizeof(*s
), GFP_KERNEL
);
2368 rc
= seq_open(file
, &fib_trie_seq_ops
);
2372 seq
= file
->private_data
;
2374 memset(s
, 0, sizeof(*s
));
2382 static const struct file_operations fib_trie_fops
= {
2383 .owner
= THIS_MODULE
,
2384 .open
= fib_trie_seq_open
,
2386 .llseek
= seq_lseek
,
2387 .release
= seq_release_private
,
2390 static unsigned fib_flag_trans(int type
, __be32 mask
, const struct fib_info
*fi
)
2392 static unsigned type2flags
[RTN_MAX
+ 1] = {
2393 [7] = RTF_REJECT
, [8] = RTF_REJECT
,
2395 unsigned flags
= type2flags
[type
];
2397 if (fi
&& fi
->fib_nh
->nh_gw
)
2398 flags
|= RTF_GATEWAY
;
2399 if (mask
== htonl(0xFFFFFFFF))
2406 * This outputs /proc/net/route.
2407 * The format of the file is not supposed to be changed
2408 * and needs to be same as fib_hash output to avoid breaking
2411 static int fib_route_seq_show(struct seq_file
*seq
, void *v
)
2413 const struct fib_trie_iter
*iter
= seq
->private;
2418 if (v
== SEQ_START_TOKEN
) {
2419 seq_printf(seq
, "%-127s\n", "Iface\tDestination\tGateway "
2420 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2425 if (iter
->trie
== trie_local
)
2430 for (i
=32; i
>=0; i
--) {
2431 struct leaf_info
*li
= find_leaf_info(l
, i
);
2432 struct fib_alias
*fa
;
2433 __be32 mask
, prefix
;
2438 mask
= inet_make_mask(li
->plen
);
2439 prefix
= htonl(l
->key
);
2441 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
2442 const struct fib_info
*fi
= fa
->fa_info
;
2443 unsigned flags
= fib_flag_trans(fa
->fa_type
, mask
, fi
);
2445 if (fa
->fa_type
== RTN_BROADCAST
2446 || fa
->fa_type
== RTN_MULTICAST
)
2450 snprintf(bf
, sizeof(bf
),
2451 "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2452 fi
->fib_dev
? fi
->fib_dev
->name
: "*",
2454 fi
->fib_nh
->nh_gw
, flags
, 0, 0,
2457 (fi
->fib_advmss
? fi
->fib_advmss
+ 40 : 0),
2461 snprintf(bf
, sizeof(bf
),
2462 "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2463 prefix
, 0, flags
, 0, 0, 0,
2466 seq_printf(seq
, "%-127s\n", bf
);
2473 static const struct seq_operations fib_route_seq_ops
= {
2474 .start
= fib_trie_seq_start
,
2475 .next
= fib_trie_seq_next
,
2476 .stop
= fib_trie_seq_stop
,
2477 .show
= fib_route_seq_show
,
2480 static int fib_route_seq_open(struct inode
*inode
, struct file
*file
)
2482 struct seq_file
*seq
;
2484 struct fib_trie_iter
*s
= kmalloc(sizeof(*s
), GFP_KERNEL
);
2489 rc
= seq_open(file
, &fib_route_seq_ops
);
2493 seq
= file
->private_data
;
2495 memset(s
, 0, sizeof(*s
));
2503 static const struct file_operations fib_route_fops
= {
2504 .owner
= THIS_MODULE
,
2505 .open
= fib_route_seq_open
,
2507 .llseek
= seq_lseek
,
2508 .release
= seq_release_private
,
2511 int __init
fib_proc_init(void)
2513 if (!proc_net_fops_create("fib_trie", S_IRUGO
, &fib_trie_fops
))
2516 if (!proc_net_fops_create("fib_triestat", S_IRUGO
, &fib_triestat_fops
))
2519 if (!proc_net_fops_create("route", S_IRUGO
, &fib_route_fops
))
2525 proc_net_remove("fib_triestat");
2527 proc_net_remove("fib_trie");
2532 void __init
fib_proc_exit(void)
2534 proc_net_remove("fib_trie");
2535 proc_net_remove("fib_triestat");
2536 proc_net_remove("route");
2539 #endif /* CONFIG_PROC_FS */