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.407"
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
= 15;
296 static int inflate_threshold_root
= 25;
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
;
465 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
466 tn
, inflate_threshold
, halve_threshold
);
469 if (tn
->empty_children
== tnode_child_length(tn
)) {
474 if (tn
->empty_children
== tnode_child_length(tn
) - 1)
475 for (i
= 0; i
< tnode_child_length(tn
); i
++) {
482 /* compress one level */
483 NODE_SET_PARENT(n
, NULL
);
488 * Double as long as the resulting node has a number of
489 * nonempty nodes that are above the threshold.
493 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
494 * the Helsinki University of Technology and Matti Tikkanen of Nokia
495 * Telecommunications, page 6:
496 * "A node is doubled if the ratio of non-empty children to all
497 * children in the *doubled* node is at least 'high'."
499 * 'high' in this instance is the variable 'inflate_threshold'. It
500 * is expressed as a percentage, so we multiply it with
501 * tnode_child_length() and instead of multiplying by 2 (since the
502 * child array will be doubled by inflate()) and multiplying
503 * the left-hand side by 100 (to handle the percentage thing) we
504 * multiply the left-hand side by 50.
506 * The left-hand side may look a bit weird: tnode_child_length(tn)
507 * - tn->empty_children is of course the number of non-null children
508 * in the current node. tn->full_children is the number of "full"
509 * children, that is non-null tnodes with a skip value of 0.
510 * All of those will be doubled in the resulting inflated tnode, so
511 * we just count them one extra time here.
513 * A clearer way to write this would be:
515 * to_be_doubled = tn->full_children;
516 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
519 * new_child_length = tnode_child_length(tn) * 2;
521 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
523 * if (new_fill_factor >= inflate_threshold)
525 * ...and so on, tho it would mess up the while () loop.
528 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
532 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
533 * inflate_threshold * new_child_length
535 * expand not_to_be_doubled and to_be_doubled, and shorten:
536 * 100 * (tnode_child_length(tn) - tn->empty_children +
537 * tn->full_children) >= inflate_threshold * new_child_length
539 * expand new_child_length:
540 * 100 * (tnode_child_length(tn) - tn->empty_children +
541 * tn->full_children) >=
542 * inflate_threshold * tnode_child_length(tn) * 2
545 * 50 * (tn->full_children + tnode_child_length(tn) -
546 * tn->empty_children) >= inflate_threshold *
547 * tnode_child_length(tn)
553 /* Keep root node larger */
556 inflate_threshold_use
= inflate_threshold_root
;
558 inflate_threshold_use
= inflate_threshold
;
561 while ((tn
->full_children
> 0 &&
562 50 * (tn
->full_children
+ tnode_child_length(tn
) - tn
->empty_children
) >=
563 inflate_threshold_use
* tnode_child_length(tn
))) {
569 #ifdef CONFIG_IP_FIB_TRIE_STATS
570 t
->stats
.resize_node_skipped
++;
579 * Halve as long as the number of empty children in this
580 * node is above threshold.
584 /* Keep root node larger */
587 halve_threshold_use
= halve_threshold_root
;
589 halve_threshold_use
= halve_threshold
;
592 while (tn
->bits
> 1 &&
593 100 * (tnode_child_length(tn
) - tn
->empty_children
) <
594 halve_threshold_use
* tnode_child_length(tn
)) {
600 #ifdef CONFIG_IP_FIB_TRIE_STATS
601 t
->stats
.resize_node_skipped
++;
608 /* Only one child remains */
609 if (tn
->empty_children
== tnode_child_length(tn
) - 1)
610 for (i
= 0; i
< tnode_child_length(tn
); i
++) {
617 /* compress one level */
619 NODE_SET_PARENT(n
, NULL
);
624 return (struct node
*) tn
;
627 static struct tnode
*inflate(struct trie
*t
, struct tnode
*tn
)
630 struct tnode
*oldtnode
= tn
;
631 int olen
= tnode_child_length(tn
);
634 pr_debug("In inflate\n");
636 tn
= tnode_new(oldtnode
->key
, oldtnode
->pos
, oldtnode
->bits
+ 1);
639 return ERR_PTR(-ENOMEM
);
642 * Preallocate and store tnodes before the actual work so we
643 * don't get into an inconsistent state if memory allocation
644 * fails. In case of failure we return the oldnode and inflate
645 * of tnode is ignored.
648 for (i
= 0; i
< olen
; i
++) {
649 struct tnode
*inode
= (struct tnode
*) tnode_get_child(oldtnode
, i
);
653 inode
->pos
== oldtnode
->pos
+ oldtnode
->bits
&&
655 struct tnode
*left
, *right
;
656 t_key m
= TKEY_GET_MASK(inode
->pos
, 1);
658 left
= tnode_new(inode
->key
&(~m
), inode
->pos
+ 1,
663 right
= tnode_new(inode
->key
|m
, inode
->pos
+ 1,
671 put_child(t
, tn
, 2*i
, (struct node
*) left
);
672 put_child(t
, tn
, 2*i
+1, (struct node
*) right
);
676 for (i
= 0; i
< olen
; i
++) {
677 struct node
*node
= tnode_get_child(oldtnode
, i
);
678 struct tnode
*left
, *right
;
685 /* A leaf or an internal node with skipped bits */
687 if (IS_LEAF(node
) || ((struct tnode
*) node
)->pos
>
688 tn
->pos
+ tn
->bits
- 1) {
689 if (tkey_extract_bits(node
->key
, oldtnode
->pos
+ oldtnode
->bits
,
691 put_child(t
, tn
, 2*i
, node
);
693 put_child(t
, tn
, 2*i
+1, node
);
697 /* An internal node with two children */
698 inode
= (struct tnode
*) node
;
700 if (inode
->bits
== 1) {
701 put_child(t
, tn
, 2*i
, inode
->child
[0]);
702 put_child(t
, tn
, 2*i
+1, inode
->child
[1]);
708 /* An internal node with more than two children */
710 /* We will replace this node 'inode' with two new
711 * ones, 'left' and 'right', each with half of the
712 * original children. The two new nodes will have
713 * a position one bit further down the key and this
714 * means that the "significant" part of their keys
715 * (see the discussion near the top of this file)
716 * will differ by one bit, which will be "0" in
717 * left's key and "1" in right's key. Since we are
718 * moving the key position by one step, the bit that
719 * we are moving away from - the bit at position
720 * (inode->pos) - is the one that will differ between
721 * left and right. So... we synthesize that bit in the
723 * The mask 'm' below will be a single "one" bit at
724 * the position (inode->pos)
727 /* Use the old key, but set the new significant
731 left
= (struct tnode
*) tnode_get_child(tn
, 2*i
);
732 put_child(t
, tn
, 2*i
, NULL
);
736 right
= (struct tnode
*) tnode_get_child(tn
, 2*i
+1);
737 put_child(t
, tn
, 2*i
+1, NULL
);
741 size
= tnode_child_length(left
);
742 for (j
= 0; j
< size
; j
++) {
743 put_child(t
, left
, j
, inode
->child
[j
]);
744 put_child(t
, right
, j
, inode
->child
[j
+ size
]);
746 put_child(t
, tn
, 2*i
, resize(t
, left
));
747 put_child(t
, tn
, 2*i
+1, resize(t
, right
));
751 tnode_free(oldtnode
);
755 int size
= tnode_child_length(tn
);
758 for (j
= 0; j
< size
; j
++)
760 tnode_free((struct tnode
*)tn
->child
[j
]);
764 return ERR_PTR(-ENOMEM
);
768 static struct tnode
*halve(struct trie
*t
, struct tnode
*tn
)
770 struct tnode
*oldtnode
= tn
;
771 struct node
*left
, *right
;
773 int olen
= tnode_child_length(tn
);
775 pr_debug("In halve\n");
777 tn
= tnode_new(oldtnode
->key
, oldtnode
->pos
, oldtnode
->bits
- 1);
780 return ERR_PTR(-ENOMEM
);
783 * Preallocate and store tnodes before the actual work so we
784 * don't get into an inconsistent state if memory allocation
785 * fails. In case of failure we return the oldnode and halve
786 * of tnode is ignored.
789 for (i
= 0; i
< olen
; i
+= 2) {
790 left
= tnode_get_child(oldtnode
, i
);
791 right
= tnode_get_child(oldtnode
, i
+1);
793 /* Two nonempty children */
797 newn
= tnode_new(left
->key
, tn
->pos
+ tn
->bits
, 1);
802 put_child(t
, tn
, i
/2, (struct node
*)newn
);
807 for (i
= 0; i
< olen
; i
+= 2) {
808 struct tnode
*newBinNode
;
810 left
= tnode_get_child(oldtnode
, i
);
811 right
= tnode_get_child(oldtnode
, i
+1);
813 /* At least one of the children is empty */
815 if (right
== NULL
) /* Both are empty */
817 put_child(t
, tn
, i
/2, right
);
822 put_child(t
, tn
, i
/2, left
);
826 /* Two nonempty children */
827 newBinNode
= (struct tnode
*) tnode_get_child(tn
, i
/2);
828 put_child(t
, tn
, i
/2, NULL
);
829 put_child(t
, newBinNode
, 0, left
);
830 put_child(t
, newBinNode
, 1, right
);
831 put_child(t
, tn
, i
/2, resize(t
, newBinNode
));
833 tnode_free(oldtnode
);
837 int size
= tnode_child_length(tn
);
840 for (j
= 0; j
< size
; j
++)
842 tnode_free((struct tnode
*)tn
->child
[j
]);
846 return ERR_PTR(-ENOMEM
);
850 static void trie_init(struct trie
*t
)
856 rcu_assign_pointer(t
->trie
, NULL
);
858 #ifdef CONFIG_IP_FIB_TRIE_STATS
859 memset(&t
->stats
, 0, sizeof(struct trie_use_stats
));
863 /* readside must use rcu_read_lock currently dump routines
864 via get_fa_head and dump */
866 static struct leaf_info
*find_leaf_info(struct leaf
*l
, int plen
)
868 struct hlist_head
*head
= &l
->list
;
869 struct hlist_node
*node
;
870 struct leaf_info
*li
;
872 hlist_for_each_entry_rcu(li
, node
, head
, hlist
)
873 if (li
->plen
== plen
)
879 static inline struct list_head
* get_fa_head(struct leaf
*l
, int plen
)
881 struct leaf_info
*li
= find_leaf_info(l
, plen
);
889 static void insert_leaf_info(struct hlist_head
*head
, struct leaf_info
*new)
891 struct leaf_info
*li
= NULL
, *last
= NULL
;
892 struct hlist_node
*node
;
894 if (hlist_empty(head
)) {
895 hlist_add_head_rcu(&new->hlist
, head
);
897 hlist_for_each_entry(li
, node
, head
, hlist
) {
898 if (new->plen
> li
->plen
)
904 hlist_add_after_rcu(&last
->hlist
, &new->hlist
);
906 hlist_add_before_rcu(&new->hlist
, &li
->hlist
);
910 /* rcu_read_lock needs to be hold by caller from readside */
913 fib_find_node(struct trie
*t
, u32 key
)
920 n
= rcu_dereference(t
->trie
);
922 while (n
!= NULL
&& NODE_TYPE(n
) == T_TNODE
) {
923 tn
= (struct tnode
*) n
;
927 if (tkey_sub_equals(tn
->key
, pos
, tn
->pos
-pos
, key
)) {
928 pos
= tn
->pos
+ tn
->bits
;
929 n
= tnode_get_child(tn
, tkey_extract_bits(key
, tn
->pos
, tn
->bits
));
933 /* Case we have found a leaf. Compare prefixes */
935 if (n
!= NULL
&& IS_LEAF(n
) && tkey_equals(key
, n
->key
))
936 return (struct leaf
*)n
;
941 static struct node
*trie_rebalance(struct trie
*t
, struct tnode
*tn
)
945 struct tnode
*tp
= NULL
;
949 while (tn
!= NULL
&& NODE_PARENT(tn
) != NULL
) {
951 tp
= NODE_PARENT(tn
);
952 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
953 wasfull
= tnode_full(tp
, tnode_get_child(tp
, cindex
));
954 tn
= (struct tnode
*) resize (t
, (struct tnode
*)tn
);
955 tnode_put_child_reorg((struct tnode
*)tp
, cindex
,(struct node
*)tn
, wasfull
);
957 if (!NODE_PARENT(tn
))
960 tn
= NODE_PARENT(tn
);
962 /* Handle last (top) tnode */
964 tn
= (struct tnode
*) resize(t
, (struct tnode
*)tn
);
966 return (struct node
*) tn
;
969 /* only used from updater-side */
971 static struct list_head
*
972 fib_insert_node(struct trie
*t
, int *err
, u32 key
, int plen
)
975 struct tnode
*tp
= NULL
, *tn
= NULL
;
979 struct list_head
*fa_head
= NULL
;
980 struct leaf_info
*li
;
986 /* If we point to NULL, stop. Either the tree is empty and we should
987 * just put a new leaf in if, or we have reached an empty child slot,
988 * and we should just put our new leaf in that.
989 * If we point to a T_TNODE, check if it matches our key. Note that
990 * a T_TNODE might be skipping any number of bits - its 'pos' need
991 * not be the parent's 'pos'+'bits'!
993 * If it does match the current key, get pos/bits from it, extract
994 * the index from our key, push the T_TNODE and walk the tree.
996 * If it doesn't, we have to replace it with a new T_TNODE.
998 * If we point to a T_LEAF, it might or might not have the same key
999 * as we do. If it does, just change the value, update the T_LEAF's
1000 * value, and return it.
1001 * If it doesn't, we need to replace it with a T_TNODE.
1004 while (n
!= NULL
&& NODE_TYPE(n
) == T_TNODE
) {
1005 tn
= (struct tnode
*) n
;
1009 if (tkey_sub_equals(tn
->key
, pos
, tn
->pos
-pos
, key
)) {
1011 pos
= tn
->pos
+ tn
->bits
;
1012 n
= tnode_get_child(tn
, tkey_extract_bits(key
, tn
->pos
, tn
->bits
));
1014 BUG_ON(n
&& NODE_PARENT(n
) != tn
);
1020 * n ----> NULL, LEAF or TNODE
1022 * tp is n's (parent) ----> NULL or TNODE
1025 BUG_ON(tp
&& IS_LEAF(tp
));
1027 /* Case 1: n is a leaf. Compare prefixes */
1029 if (n
!= NULL
&& IS_LEAF(n
) && tkey_equals(key
, n
->key
)) {
1030 struct leaf
*l
= (struct leaf
*) n
;
1032 li
= leaf_info_new(plen
);
1039 fa_head
= &li
->falh
;
1040 insert_leaf_info(&l
->list
, li
);
1052 li
= leaf_info_new(plen
);
1055 tnode_free((struct tnode
*) l
);
1060 fa_head
= &li
->falh
;
1061 insert_leaf_info(&l
->list
, li
);
1063 if (t
->trie
&& n
== NULL
) {
1064 /* Case 2: n is NULL, and will just insert a new leaf */
1066 NODE_SET_PARENT(l
, tp
);
1068 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1069 put_child(t
, (struct tnode
*)tp
, cindex
, (struct node
*)l
);
1071 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1073 * Add a new tnode here
1074 * first tnode need some special handling
1078 pos
= tp
->pos
+tp
->bits
;
1083 newpos
= tkey_mismatch(key
, pos
, n
->key
);
1084 tn
= tnode_new(n
->key
, newpos
, 1);
1087 tn
= tnode_new(key
, newpos
, 1); /* First tnode */
1092 tnode_free((struct tnode
*) l
);
1097 NODE_SET_PARENT(tn
, tp
);
1099 missbit
= tkey_extract_bits(key
, newpos
, 1);
1100 put_child(t
, tn
, missbit
, (struct node
*)l
);
1101 put_child(t
, tn
, 1-missbit
, n
);
1104 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1105 put_child(t
, (struct tnode
*)tp
, cindex
, (struct node
*)tn
);
1107 rcu_assign_pointer(t
->trie
, (struct node
*)tn
); /* First tnode */
1112 if (tp
&& tp
->pos
+ tp
->bits
> 32)
1113 printk(KERN_WARNING
"fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1114 tp
, tp
->pos
, tp
->bits
, key
, plen
);
1116 /* Rebalance the trie */
1118 rcu_assign_pointer(t
->trie
, trie_rebalance(t
, tp
));
1126 * Caller must hold RTNL.
1128 static int fn_trie_insert(struct fib_table
*tb
, struct fib_config
*cfg
)
1130 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1131 struct fib_alias
*fa
, *new_fa
;
1132 struct list_head
*fa_head
= NULL
;
1133 struct fib_info
*fi
;
1134 int plen
= cfg
->fc_dst_len
;
1135 u8 tos
= cfg
->fc_tos
;
1143 key
= ntohl(cfg
->fc_dst
);
1145 pr_debug("Insert table=%u %08x/%d\n", tb
->tb_id
, key
, plen
);
1147 mask
= ntohl(inet_make_mask(plen
));
1154 fi
= fib_create_info(cfg
);
1160 l
= fib_find_node(t
, key
);
1164 fa_head
= get_fa_head(l
, plen
);
1165 fa
= fib_find_alias(fa_head
, tos
, fi
->fib_priority
);
1168 /* Now fa, if non-NULL, points to the first fib alias
1169 * with the same keys [prefix,tos,priority], if such key already
1170 * exists or to the node before which we will insert new one.
1172 * If fa is NULL, we will need to allocate a new one and
1173 * insert to the head of f.
1175 * If f is NULL, no fib node matched the destination key
1176 * and we need to allocate a new one of those as well.
1179 if (fa
&& fa
->fa_info
->fib_priority
== fi
->fib_priority
) {
1180 struct fib_alias
*fa_orig
;
1183 if (cfg
->fc_nlflags
& NLM_F_EXCL
)
1186 if (cfg
->fc_nlflags
& NLM_F_REPLACE
) {
1187 struct fib_info
*fi_drop
;
1191 new_fa
= kmem_cache_alloc(fn_alias_kmem
, GFP_KERNEL
);
1195 fi_drop
= fa
->fa_info
;
1196 new_fa
->fa_tos
= fa
->fa_tos
;
1197 new_fa
->fa_info
= fi
;
1198 new_fa
->fa_type
= cfg
->fc_type
;
1199 new_fa
->fa_scope
= cfg
->fc_scope
;
1200 state
= fa
->fa_state
;
1201 new_fa
->fa_state
&= ~FA_S_ACCESSED
;
1203 list_replace_rcu(&fa
->fa_list
, &new_fa
->fa_list
);
1204 alias_free_mem_rcu(fa
);
1206 fib_release_info(fi_drop
);
1207 if (state
& FA_S_ACCESSED
)
1212 /* Error if we find a perfect match which
1213 * uses the same scope, type, and nexthop
1217 list_for_each_entry(fa
, fa_orig
->fa_list
.prev
, fa_list
) {
1218 if (fa
->fa_tos
!= tos
)
1220 if (fa
->fa_info
->fib_priority
!= fi
->fib_priority
)
1222 if (fa
->fa_type
== cfg
->fc_type
&&
1223 fa
->fa_scope
== cfg
->fc_scope
&&
1224 fa
->fa_info
== fi
) {
1228 if (!(cfg
->fc_nlflags
& NLM_F_APPEND
))
1232 if (!(cfg
->fc_nlflags
& NLM_F_CREATE
))
1236 new_fa
= kmem_cache_alloc(fn_alias_kmem
, GFP_KERNEL
);
1240 new_fa
->fa_info
= fi
;
1241 new_fa
->fa_tos
= tos
;
1242 new_fa
->fa_type
= cfg
->fc_type
;
1243 new_fa
->fa_scope
= cfg
->fc_scope
;
1244 new_fa
->fa_state
= 0;
1246 * Insert new entry to the list.
1251 fa_head
= fib_insert_node(t
, &err
, key
, plen
);
1253 goto out_free_new_fa
;
1256 list_add_tail_rcu(&new_fa
->fa_list
,
1257 (fa
? &fa
->fa_list
: fa_head
));
1260 rtmsg_fib(RTM_NEWROUTE
, htonl(key
), new_fa
, plen
, tb
->tb_id
,
1266 kmem_cache_free(fn_alias_kmem
, new_fa
);
1268 fib_release_info(fi
);
1274 /* should be called with rcu_read_lock */
1275 static inline int check_leaf(struct trie
*t
, struct leaf
*l
,
1276 t_key key
, int *plen
, const struct flowi
*flp
,
1277 struct fib_result
*res
)
1281 struct leaf_info
*li
;
1282 struct hlist_head
*hhead
= &l
->list
;
1283 struct hlist_node
*node
;
1285 hlist_for_each_entry_rcu(li
, node
, hhead
, hlist
) {
1287 mask
= inet_make_mask(i
);
1288 if (l
->key
!= (key
& ntohl(mask
)))
1291 if ((err
= fib_semantic_match(&li
->falh
, flp
, res
, htonl(l
->key
), mask
, i
)) <= 0) {
1293 #ifdef CONFIG_IP_FIB_TRIE_STATS
1294 t
->stats
.semantic_match_passed
++;
1298 #ifdef CONFIG_IP_FIB_TRIE_STATS
1299 t
->stats
.semantic_match_miss
++;
1306 fn_trie_lookup(struct fib_table
*tb
, const struct flowi
*flp
, struct fib_result
*res
)
1308 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1313 t_key key
= ntohl(flp
->fl4_dst
);
1316 int current_prefix_length
= KEYLENGTH
;
1318 t_key node_prefix
, key_prefix
, pref_mismatch
;
1323 n
= rcu_dereference(t
->trie
);
1327 #ifdef CONFIG_IP_FIB_TRIE_STATS
1333 if ((ret
= check_leaf(t
, (struct leaf
*)n
, key
, &plen
, flp
, res
)) <= 0)
1337 pn
= (struct tnode
*) n
;
1345 cindex
= tkey_extract_bits(MASK_PFX(key
, current_prefix_length
), pos
, bits
);
1347 n
= tnode_get_child(pn
, cindex
);
1350 #ifdef CONFIG_IP_FIB_TRIE_STATS
1351 t
->stats
.null_node_hit
++;
1357 if ((ret
= check_leaf(t
, (struct leaf
*)n
, key
, &plen
, flp
, res
)) <= 0)
1365 cn
= (struct tnode
*)n
;
1368 * It's a tnode, and we can do some extra checks here if we
1369 * like, to avoid descending into a dead-end branch.
1370 * This tnode is in the parent's child array at index
1371 * key[p_pos..p_pos+p_bits] but potentially with some bits
1372 * chopped off, so in reality the index may be just a
1373 * subprefix, padded with zero at the end.
1374 * We can also take a look at any skipped bits in this
1375 * tnode - everything up to p_pos is supposed to be ok,
1376 * and the non-chopped bits of the index (se previous
1377 * paragraph) are also guaranteed ok, but the rest is
1378 * considered unknown.
1380 * The skipped bits are key[pos+bits..cn->pos].
1383 /* If current_prefix_length < pos+bits, we are already doing
1384 * actual prefix matching, which means everything from
1385 * pos+(bits-chopped_off) onward must be zero along some
1386 * branch of this subtree - otherwise there is *no* valid
1387 * prefix present. Here we can only check the skipped
1388 * bits. Remember, since we have already indexed into the
1389 * parent's child array, we know that the bits we chopped of
1393 /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */
1395 if (current_prefix_length
< pos
+bits
) {
1396 if (tkey_extract_bits(cn
->key
, current_prefix_length
,
1397 cn
->pos
- current_prefix_length
) != 0 ||
1403 * If chopped_off=0, the index is fully validated and we
1404 * only need to look at the skipped bits for this, the new,
1405 * tnode. What we actually want to do is to find out if
1406 * these skipped bits match our key perfectly, or if we will
1407 * have to count on finding a matching prefix further down,
1408 * because if we do, we would like to have some way of
1409 * verifying the existence of such a prefix at this point.
1412 /* The only thing we can do at this point is to verify that
1413 * any such matching prefix can indeed be a prefix to our
1414 * key, and if the bits in the node we are inspecting that
1415 * do not match our key are not ZERO, this cannot be true.
1416 * Thus, find out where there is a mismatch (before cn->pos)
1417 * and verify that all the mismatching bits are zero in the
1421 /* Note: We aren't very concerned about the piece of the key
1422 * that precede pn->pos+pn->bits, since these have already been
1423 * checked. The bits after cn->pos aren't checked since these are
1424 * by definition "unknown" at this point. Thus, what we want to
1425 * see is if we are about to enter the "prefix matching" state,
1426 * and in that case verify that the skipped bits that will prevail
1427 * throughout this subtree are zero, as they have to be if we are
1428 * to find a matching prefix.
1431 node_prefix
= MASK_PFX(cn
->key
, cn
->pos
);
1432 key_prefix
= MASK_PFX(key
, cn
->pos
);
1433 pref_mismatch
= key_prefix
^node_prefix
;
1436 /* In short: If skipped bits in this node do not match the search
1437 * key, enter the "prefix matching" state.directly.
1439 if (pref_mismatch
) {
1440 while (!(pref_mismatch
& (1<<(KEYLENGTH
-1)))) {
1442 pref_mismatch
= pref_mismatch
<<1;
1444 key_prefix
= tkey_extract_bits(cn
->key
, mp
, cn
->pos
-mp
);
1446 if (key_prefix
!= 0)
1449 if (current_prefix_length
>= cn
->pos
)
1450 current_prefix_length
= mp
;
1453 pn
= (struct tnode
*)n
; /* Descend */
1460 /* As zero don't change the child key (cindex) */
1461 while ((chopped_off
<= pn
->bits
) && !(cindex
& (1<<(chopped_off
-1))))
1464 /* Decrease current_... with bits chopped off */
1465 if (current_prefix_length
> pn
->pos
+ pn
->bits
- chopped_off
)
1466 current_prefix_length
= pn
->pos
+ pn
->bits
- chopped_off
;
1469 * Either we do the actual chop off according or if we have
1470 * chopped off all bits in this tnode walk up to our parent.
1473 if (chopped_off
<= pn
->bits
) {
1474 cindex
&= ~(1 << (chopped_off
-1));
1476 if (NODE_PARENT(pn
) == NULL
)
1479 /* Get Child's index */
1480 cindex
= tkey_extract_bits(pn
->key
, NODE_PARENT(pn
)->pos
, NODE_PARENT(pn
)->bits
);
1481 pn
= NODE_PARENT(pn
);
1484 #ifdef CONFIG_IP_FIB_TRIE_STATS
1485 t
->stats
.backtrack
++;
1497 /* only called from updater side */
1498 static int trie_leaf_remove(struct trie
*t
, t_key key
)
1501 struct tnode
*tp
= NULL
;
1502 struct node
*n
= t
->trie
;
1505 pr_debug("entering trie_leaf_remove(%p)\n", n
);
1507 /* Note that in the case skipped bits, those bits are *not* checked!
1508 * When we finish this, we will have NULL or a T_LEAF, and the
1509 * T_LEAF may or may not match our key.
1512 while (n
!= NULL
&& IS_TNODE(n
)) {
1513 struct tnode
*tn
= (struct tnode
*) n
;
1515 n
= tnode_get_child(tn
,tkey_extract_bits(key
, tn
->pos
, tn
->bits
));
1517 BUG_ON(n
&& NODE_PARENT(n
) != tn
);
1519 l
= (struct leaf
*) n
;
1521 if (!n
|| !tkey_equals(l
->key
, key
))
1526 * Remove the leaf and rebalance the tree
1532 tp
= NODE_PARENT(n
);
1533 tnode_free((struct tnode
*) n
);
1536 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1537 put_child(t
, (struct tnode
*)tp
, cindex
, NULL
);
1538 rcu_assign_pointer(t
->trie
, trie_rebalance(t
, tp
));
1540 rcu_assign_pointer(t
->trie
, NULL
);
1546 * Caller must hold RTNL.
1548 static int fn_trie_delete(struct fib_table
*tb
, struct fib_config
*cfg
)
1550 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1552 int plen
= cfg
->fc_dst_len
;
1553 u8 tos
= cfg
->fc_tos
;
1554 struct fib_alias
*fa
, *fa_to_delete
;
1555 struct list_head
*fa_head
;
1557 struct leaf_info
*li
;
1562 key
= ntohl(cfg
->fc_dst
);
1563 mask
= ntohl(inet_make_mask(plen
));
1569 l
= fib_find_node(t
, key
);
1574 fa_head
= get_fa_head(l
, plen
);
1575 fa
= fib_find_alias(fa_head
, tos
, 0);
1580 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key
, plen
, tos
, t
);
1582 fa_to_delete
= NULL
;
1583 fa_head
= fa
->fa_list
.prev
;
1585 list_for_each_entry(fa
, fa_head
, fa_list
) {
1586 struct fib_info
*fi
= fa
->fa_info
;
1588 if (fa
->fa_tos
!= tos
)
1591 if ((!cfg
->fc_type
|| fa
->fa_type
== cfg
->fc_type
) &&
1592 (cfg
->fc_scope
== RT_SCOPE_NOWHERE
||
1593 fa
->fa_scope
== cfg
->fc_scope
) &&
1594 (!cfg
->fc_protocol
||
1595 fi
->fib_protocol
== cfg
->fc_protocol
) &&
1596 fib_nh_match(cfg
, fi
) == 0) {
1606 rtmsg_fib(RTM_DELROUTE
, htonl(key
), fa
, plen
, tb
->tb_id
,
1609 l
= fib_find_node(t
, key
);
1610 li
= find_leaf_info(l
, plen
);
1612 list_del_rcu(&fa
->fa_list
);
1614 if (list_empty(fa_head
)) {
1615 hlist_del_rcu(&li
->hlist
);
1619 if (hlist_empty(&l
->list
))
1620 trie_leaf_remove(t
, key
);
1622 if (fa
->fa_state
& FA_S_ACCESSED
)
1625 fib_release_info(fa
->fa_info
);
1626 alias_free_mem_rcu(fa
);
1630 static int trie_flush_list(struct trie
*t
, struct list_head
*head
)
1632 struct fib_alias
*fa
, *fa_node
;
1635 list_for_each_entry_safe(fa
, fa_node
, head
, fa_list
) {
1636 struct fib_info
*fi
= fa
->fa_info
;
1638 if (fi
&& (fi
->fib_flags
& RTNH_F_DEAD
)) {
1639 list_del_rcu(&fa
->fa_list
);
1640 fib_release_info(fa
->fa_info
);
1641 alias_free_mem_rcu(fa
);
1648 static int trie_flush_leaf(struct trie
*t
, struct leaf
*l
)
1651 struct hlist_head
*lih
= &l
->list
;
1652 struct hlist_node
*node
, *tmp
;
1653 struct leaf_info
*li
= NULL
;
1655 hlist_for_each_entry_safe(li
, node
, tmp
, lih
, hlist
) {
1656 found
+= trie_flush_list(t
, &li
->falh
);
1658 if (list_empty(&li
->falh
)) {
1659 hlist_del_rcu(&li
->hlist
);
1666 /* rcu_read_lock needs to be hold by caller from readside */
1668 static struct leaf
*nextleaf(struct trie
*t
, struct leaf
*thisleaf
)
1670 struct node
*c
= (struct node
*) thisleaf
;
1673 struct node
*trie
= rcu_dereference(t
->trie
);
1679 if (IS_LEAF(trie
)) /* trie w. just a leaf */
1680 return (struct leaf
*) trie
;
1682 p
= (struct tnode
*) trie
; /* Start */
1684 p
= (struct tnode
*) NODE_PARENT(c
);
1689 /* Find the next child of the parent */
1691 pos
= 1 + tkey_extract_bits(c
->key
, p
->pos
, p
->bits
);
1695 last
= 1 << p
->bits
;
1696 for (idx
= pos
; idx
< last
; idx
++) {
1697 c
= rcu_dereference(p
->child
[idx
]);
1702 /* Decend if tnode */
1703 while (IS_TNODE(c
)) {
1704 p
= (struct tnode
*) c
;
1707 /* Rightmost non-NULL branch */
1708 if (p
&& IS_TNODE(p
))
1709 while (!(c
= rcu_dereference(p
->child
[idx
]))
1710 && idx
< (1<<p
->bits
)) idx
++;
1712 /* Done with this tnode? */
1713 if (idx
>= (1 << p
->bits
) || !c
)
1716 return (struct leaf
*) c
;
1719 /* No more children go up one step */
1720 c
= (struct node
*) p
;
1721 p
= (struct tnode
*) NODE_PARENT(p
);
1723 return NULL
; /* Ready. Root of trie */
1727 * Caller must hold RTNL.
1729 static int fn_trie_flush(struct fib_table
*tb
)
1731 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1732 struct leaf
*ll
= NULL
, *l
= NULL
;
1737 for (h
= 0; (l
= nextleaf(t
, l
)) != NULL
; h
++) {
1738 found
+= trie_flush_leaf(t
, l
);
1740 if (ll
&& hlist_empty(&ll
->list
))
1741 trie_leaf_remove(t
, ll
->key
);
1745 if (ll
&& hlist_empty(&ll
->list
))
1746 trie_leaf_remove(t
, ll
->key
);
1748 pr_debug("trie_flush found=%d\n", found
);
1752 static int trie_last_dflt
= -1;
1755 fn_trie_select_default(struct fib_table
*tb
, const struct flowi
*flp
, struct fib_result
*res
)
1757 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1758 int order
, last_idx
;
1759 struct fib_info
*fi
= NULL
;
1760 struct fib_info
*last_resort
;
1761 struct fib_alias
*fa
= NULL
;
1762 struct list_head
*fa_head
;
1771 l
= fib_find_node(t
, 0);
1775 fa_head
= get_fa_head(l
, 0);
1779 if (list_empty(fa_head
))
1782 list_for_each_entry_rcu(fa
, fa_head
, fa_list
) {
1783 struct fib_info
*next_fi
= fa
->fa_info
;
1785 if (fa
->fa_scope
!= res
->scope
||
1786 fa
->fa_type
!= RTN_UNICAST
)
1789 if (next_fi
->fib_priority
> res
->fi
->fib_priority
)
1791 if (!next_fi
->fib_nh
[0].nh_gw
||
1792 next_fi
->fib_nh
[0].nh_scope
!= RT_SCOPE_LINK
)
1794 fa
->fa_state
|= FA_S_ACCESSED
;
1797 if (next_fi
!= res
->fi
)
1799 } else if (!fib_detect_death(fi
, order
, &last_resort
,
1800 &last_idx
, &trie_last_dflt
)) {
1802 fib_info_put(res
->fi
);
1804 atomic_inc(&fi
->fib_clntref
);
1805 trie_last_dflt
= order
;
1811 if (order
<= 0 || fi
== NULL
) {
1812 trie_last_dflt
= -1;
1816 if (!fib_detect_death(fi
, order
, &last_resort
, &last_idx
, &trie_last_dflt
)) {
1818 fib_info_put(res
->fi
);
1820 atomic_inc(&fi
->fib_clntref
);
1821 trie_last_dflt
= order
;
1824 if (last_idx
>= 0) {
1826 fib_info_put(res
->fi
);
1827 res
->fi
= last_resort
;
1829 atomic_inc(&last_resort
->fib_clntref
);
1831 trie_last_dflt
= last_idx
;
1836 static int fn_trie_dump_fa(t_key key
, int plen
, struct list_head
*fah
, struct fib_table
*tb
,
1837 struct sk_buff
*skb
, struct netlink_callback
*cb
)
1840 struct fib_alias
*fa
;
1842 __be32 xkey
= htonl(key
);
1847 /* rcu_read_lock is hold by caller */
1849 list_for_each_entry_rcu(fa
, fah
, fa_list
) {
1854 BUG_ON(!fa
->fa_info
);
1856 if (fib_dump_info(skb
, NETLINK_CB(cb
->skb
).pid
,
1865 fa
->fa_info
, 0) < 0) {
1875 static int fn_trie_dump_plen(struct trie
*t
, int plen
, struct fib_table
*tb
, struct sk_buff
*skb
,
1876 struct netlink_callback
*cb
)
1879 struct list_head
*fa_head
;
1880 struct leaf
*l
= NULL
;
1884 for (h
= 0; (l
= nextleaf(t
, l
)) != NULL
; h
++) {
1888 memset(&cb
->args
[4], 0,
1889 sizeof(cb
->args
) - 4*sizeof(cb
->args
[0]));
1891 fa_head
= get_fa_head(l
, plen
);
1896 if (list_empty(fa_head
))
1899 if (fn_trie_dump_fa(l
->key
, plen
, fa_head
, tb
, skb
, cb
)<0) {
1908 static int fn_trie_dump(struct fib_table
*tb
, struct sk_buff
*skb
, struct netlink_callback
*cb
)
1911 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1916 for (m
= 0; m
<= 32; m
++) {
1920 memset(&cb
->args
[3], 0,
1921 sizeof(cb
->args
) - 3*sizeof(cb
->args
[0]));
1923 if (fn_trie_dump_plen(t
, 32-m
, tb
, skb
, cb
)<0) {
1936 /* Fix more generic FIB names for init later */
1938 #ifdef CONFIG_IP_MULTIPLE_TABLES
1939 struct fib_table
* fib_hash_init(u32 id
)
1941 struct fib_table
* __init
fib_hash_init(u32 id
)
1944 struct fib_table
*tb
;
1947 if (fn_alias_kmem
== NULL
)
1948 fn_alias_kmem
= kmem_cache_create("ip_fib_alias",
1949 sizeof(struct fib_alias
),
1950 0, SLAB_HWCACHE_ALIGN
,
1953 tb
= kmalloc(sizeof(struct fib_table
) + sizeof(struct trie
),
1959 tb
->tb_lookup
= fn_trie_lookup
;
1960 tb
->tb_insert
= fn_trie_insert
;
1961 tb
->tb_delete
= fn_trie_delete
;
1962 tb
->tb_flush
= fn_trie_flush
;
1963 tb
->tb_select_default
= fn_trie_select_default
;
1964 tb
->tb_dump
= fn_trie_dump
;
1965 memset(tb
->tb_data
, 0, sizeof(struct trie
));
1967 t
= (struct trie
*) tb
->tb_data
;
1971 if (id
== RT_TABLE_LOCAL
)
1973 else if (id
== RT_TABLE_MAIN
)
1976 if (id
== RT_TABLE_LOCAL
)
1977 printk(KERN_INFO
"IPv4 FIB: Using LC-trie version %s\n", VERSION
);
1982 #ifdef CONFIG_PROC_FS
1983 /* Depth first Trie walk iterator */
1984 struct fib_trie_iter
{
1985 struct tnode
*tnode
;
1991 static struct node
*fib_trie_get_next(struct fib_trie_iter
*iter
)
1993 struct tnode
*tn
= iter
->tnode
;
1994 unsigned cindex
= iter
->index
;
1997 /* A single entry routing table */
2001 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2002 iter
->tnode
, iter
->index
, iter
->depth
);
2004 while (cindex
< (1<<tn
->bits
)) {
2005 struct node
*n
= tnode_get_child(tn
, cindex
);
2010 iter
->index
= cindex
+ 1;
2012 /* push down one level */
2013 iter
->tnode
= (struct tnode
*) n
;
2023 /* Current node exhausted, pop back up */
2024 p
= NODE_PARENT(tn
);
2026 cindex
= tkey_extract_bits(tn
->key
, p
->pos
, p
->bits
)+1;
2036 static struct node
*fib_trie_get_first(struct fib_trie_iter
*iter
,
2044 n
= rcu_dereference(t
->trie
);
2051 iter
->tnode
= (struct tnode
*) n
;
2066 static void trie_collect_stats(struct trie
*t
, struct trie_stat
*s
)
2069 struct fib_trie_iter iter
;
2071 memset(s
, 0, sizeof(*s
));
2074 for (n
= fib_trie_get_first(&iter
, t
); n
;
2075 n
= fib_trie_get_next(&iter
)) {
2078 s
->totdepth
+= iter
.depth
;
2079 if (iter
.depth
> s
->maxdepth
)
2080 s
->maxdepth
= iter
.depth
;
2082 const struct tnode
*tn
= (const struct tnode
*) n
;
2086 if (tn
->bits
< MAX_STAT_DEPTH
)
2087 s
->nodesizes
[tn
->bits
]++;
2089 for (i
= 0; i
< (1<<tn
->bits
); i
++)
2098 * This outputs /proc/net/fib_triestats
2100 static void trie_show_stats(struct seq_file
*seq
, struct trie_stat
*stat
)
2102 unsigned i
, max
, pointers
, bytes
, avdepth
;
2105 avdepth
= stat
->totdepth
*100 / stat
->leaves
;
2109 seq_printf(seq
, "\tAver depth: %d.%02d\n", avdepth
/ 100, avdepth
% 100 );
2110 seq_printf(seq
, "\tMax depth: %u\n", stat
->maxdepth
);
2112 seq_printf(seq
, "\tLeaves: %u\n", stat
->leaves
);
2114 bytes
= sizeof(struct leaf
) * stat
->leaves
;
2115 seq_printf(seq
, "\tInternal nodes: %d\n\t", stat
->tnodes
);
2116 bytes
+= sizeof(struct tnode
) * stat
->tnodes
;
2118 max
= MAX_STAT_DEPTH
;
2119 while (max
> 0 && stat
->nodesizes
[max
-1] == 0)
2123 for (i
= 1; i
<= max
; i
++)
2124 if (stat
->nodesizes
[i
] != 0) {
2125 seq_printf(seq
, " %d: %d", i
, stat
->nodesizes
[i
]);
2126 pointers
+= (1<<i
) * stat
->nodesizes
[i
];
2128 seq_putc(seq
, '\n');
2129 seq_printf(seq
, "\tPointers: %d\n", pointers
);
2131 bytes
+= sizeof(struct node
*) * pointers
;
2132 seq_printf(seq
, "Null ptrs: %d\n", stat
->nullpointers
);
2133 seq_printf(seq
, "Total size: %d kB\n", (bytes
+ 1023) / 1024);
2135 #ifdef CONFIG_IP_FIB_TRIE_STATS
2136 seq_printf(seq
, "Counters:\n---------\n");
2137 seq_printf(seq
,"gets = %d\n", t
->stats
.gets
);
2138 seq_printf(seq
,"backtracks = %d\n", t
->stats
.backtrack
);
2139 seq_printf(seq
,"semantic match passed = %d\n", t
->stats
.semantic_match_passed
);
2140 seq_printf(seq
,"semantic match miss = %d\n", t
->stats
.semantic_match_miss
);
2141 seq_printf(seq
,"null node hit= %d\n", t
->stats
.null_node_hit
);
2142 seq_printf(seq
,"skipped node resize = %d\n", t
->stats
.resize_node_skipped
);
2144 memset(&(t
->stats
), 0, sizeof(t
->stats
));
2146 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2149 static int fib_triestat_seq_show(struct seq_file
*seq
, void *v
)
2151 struct trie_stat
*stat
;
2153 stat
= kmalloc(sizeof(*stat
), GFP_KERNEL
);
2157 seq_printf(seq
, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
2158 sizeof(struct leaf
), sizeof(struct tnode
));
2161 seq_printf(seq
, "Local:\n");
2162 trie_collect_stats(trie_local
, stat
);
2163 trie_show_stats(seq
, stat
);
2167 seq_printf(seq
, "Main:\n");
2168 trie_collect_stats(trie_main
, stat
);
2169 trie_show_stats(seq
, stat
);
2176 static int fib_triestat_seq_open(struct inode
*inode
, struct file
*file
)
2178 return single_open(file
, fib_triestat_seq_show
, NULL
);
2181 static const struct file_operations fib_triestat_fops
= {
2182 .owner
= THIS_MODULE
,
2183 .open
= fib_triestat_seq_open
,
2185 .llseek
= seq_lseek
,
2186 .release
= single_release
,
2189 static struct node
*fib_trie_get_idx(struct fib_trie_iter
*iter
,
2195 for (n
= fib_trie_get_first(iter
, trie_local
);
2196 n
; ++idx
, n
= fib_trie_get_next(iter
)) {
2201 for (n
= fib_trie_get_first(iter
, trie_main
);
2202 n
; ++idx
, n
= fib_trie_get_next(iter
)) {
2209 static void *fib_trie_seq_start(struct seq_file
*seq
, loff_t
*pos
)
2213 return SEQ_START_TOKEN
;
2214 return fib_trie_get_idx(seq
->private, *pos
- 1);
2217 static void *fib_trie_seq_next(struct seq_file
*seq
, void *v
, loff_t
*pos
)
2219 struct fib_trie_iter
*iter
= seq
->private;
2223 if (v
== SEQ_START_TOKEN
)
2224 return fib_trie_get_idx(iter
, 0);
2226 v
= fib_trie_get_next(iter
);
2231 /* continue scan in next trie */
2232 if (iter
->trie
== trie_local
)
2233 return fib_trie_get_first(iter
, trie_main
);
2238 static void fib_trie_seq_stop(struct seq_file
*seq
, void *v
)
2243 static void seq_indent(struct seq_file
*seq
, int n
)
2245 while (n
-- > 0) seq_puts(seq
, " ");
2248 static inline const char *rtn_scope(enum rt_scope_t s
)
2250 static char buf
[32];
2253 case RT_SCOPE_UNIVERSE
: return "universe";
2254 case RT_SCOPE_SITE
: return "site";
2255 case RT_SCOPE_LINK
: return "link";
2256 case RT_SCOPE_HOST
: return "host";
2257 case RT_SCOPE_NOWHERE
: return "nowhere";
2259 snprintf(buf
, sizeof(buf
), "scope=%d", s
);
2264 static const char *rtn_type_names
[__RTN_MAX
] = {
2265 [RTN_UNSPEC
] = "UNSPEC",
2266 [RTN_UNICAST
] = "UNICAST",
2267 [RTN_LOCAL
] = "LOCAL",
2268 [RTN_BROADCAST
] = "BROADCAST",
2269 [RTN_ANYCAST
] = "ANYCAST",
2270 [RTN_MULTICAST
] = "MULTICAST",
2271 [RTN_BLACKHOLE
] = "BLACKHOLE",
2272 [RTN_UNREACHABLE
] = "UNREACHABLE",
2273 [RTN_PROHIBIT
] = "PROHIBIT",
2274 [RTN_THROW
] = "THROW",
2276 [RTN_XRESOLVE
] = "XRESOLVE",
2279 static inline const char *rtn_type(unsigned t
)
2281 static char buf
[32];
2283 if (t
< __RTN_MAX
&& rtn_type_names
[t
])
2284 return rtn_type_names
[t
];
2285 snprintf(buf
, sizeof(buf
), "type %d", t
);
2289 /* Pretty print the trie */
2290 static int fib_trie_seq_show(struct seq_file
*seq
, void *v
)
2292 const struct fib_trie_iter
*iter
= seq
->private;
2295 if (v
== SEQ_START_TOKEN
)
2298 if (!NODE_PARENT(n
)) {
2299 if (iter
->trie
== trie_local
)
2300 seq_puts(seq
, "<local>:\n");
2302 seq_puts(seq
, "<main>:\n");
2306 struct tnode
*tn
= (struct tnode
*) n
;
2307 __be32 prf
= htonl(MASK_PFX(tn
->key
, tn
->pos
));
2309 seq_indent(seq
, iter
->depth
-1);
2310 seq_printf(seq
, " +-- %d.%d.%d.%d/%d %d %d %d\n",
2311 NIPQUAD(prf
), tn
->pos
, tn
->bits
, tn
->full_children
,
2312 tn
->empty_children
);
2315 struct leaf
*l
= (struct leaf
*) n
;
2317 __be32 val
= htonl(l
->key
);
2319 seq_indent(seq
, iter
->depth
);
2320 seq_printf(seq
, " |-- %d.%d.%d.%d\n", NIPQUAD(val
));
2321 for (i
= 32; i
>= 0; i
--) {
2322 struct leaf_info
*li
= find_leaf_info(l
, i
);
2324 struct fib_alias
*fa
;
2325 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
2326 seq_indent(seq
, iter
->depth
+1);
2327 seq_printf(seq
, " /%d %s %s", i
,
2328 rtn_scope(fa
->fa_scope
),
2329 rtn_type(fa
->fa_type
));
2331 seq_printf(seq
, "tos =%d\n",
2333 seq_putc(seq
, '\n');
2342 static const struct seq_operations fib_trie_seq_ops
= {
2343 .start
= fib_trie_seq_start
,
2344 .next
= fib_trie_seq_next
,
2345 .stop
= fib_trie_seq_stop
,
2346 .show
= fib_trie_seq_show
,
2349 static int fib_trie_seq_open(struct inode
*inode
, struct file
*file
)
2351 struct seq_file
*seq
;
2353 struct fib_trie_iter
*s
= kmalloc(sizeof(*s
), GFP_KERNEL
);
2358 rc
= seq_open(file
, &fib_trie_seq_ops
);
2362 seq
= file
->private_data
;
2364 memset(s
, 0, sizeof(*s
));
2372 static const struct file_operations fib_trie_fops
= {
2373 .owner
= THIS_MODULE
,
2374 .open
= fib_trie_seq_open
,
2376 .llseek
= seq_lseek
,
2377 .release
= seq_release_private
,
2380 static unsigned fib_flag_trans(int type
, __be32 mask
, const struct fib_info
*fi
)
2382 static unsigned type2flags
[RTN_MAX
+ 1] = {
2383 [7] = RTF_REJECT
, [8] = RTF_REJECT
,
2385 unsigned flags
= type2flags
[type
];
2387 if (fi
&& fi
->fib_nh
->nh_gw
)
2388 flags
|= RTF_GATEWAY
;
2389 if (mask
== htonl(0xFFFFFFFF))
2396 * This outputs /proc/net/route.
2397 * The format of the file is not supposed to be changed
2398 * and needs to be same as fib_hash output to avoid breaking
2401 static int fib_route_seq_show(struct seq_file
*seq
, void *v
)
2403 const struct fib_trie_iter
*iter
= seq
->private;
2408 if (v
== SEQ_START_TOKEN
) {
2409 seq_printf(seq
, "%-127s\n", "Iface\tDestination\tGateway "
2410 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2415 if (iter
->trie
== trie_local
)
2420 for (i
=32; i
>=0; i
--) {
2421 struct leaf_info
*li
= find_leaf_info(l
, i
);
2422 struct fib_alias
*fa
;
2423 __be32 mask
, prefix
;
2428 mask
= inet_make_mask(li
->plen
);
2429 prefix
= htonl(l
->key
);
2431 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
2432 const struct fib_info
*fi
= fa
->fa_info
;
2433 unsigned flags
= fib_flag_trans(fa
->fa_type
, mask
, fi
);
2435 if (fa
->fa_type
== RTN_BROADCAST
2436 || fa
->fa_type
== RTN_MULTICAST
)
2440 snprintf(bf
, sizeof(bf
),
2441 "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2442 fi
->fib_dev
? fi
->fib_dev
->name
: "*",
2444 fi
->fib_nh
->nh_gw
, flags
, 0, 0,
2447 (fi
->fib_advmss
? fi
->fib_advmss
+ 40 : 0),
2451 snprintf(bf
, sizeof(bf
),
2452 "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2453 prefix
, 0, flags
, 0, 0, 0,
2456 seq_printf(seq
, "%-127s\n", bf
);
2463 static const struct seq_operations fib_route_seq_ops
= {
2464 .start
= fib_trie_seq_start
,
2465 .next
= fib_trie_seq_next
,
2466 .stop
= fib_trie_seq_stop
,
2467 .show
= fib_route_seq_show
,
2470 static int fib_route_seq_open(struct inode
*inode
, struct file
*file
)
2472 struct seq_file
*seq
;
2474 struct fib_trie_iter
*s
= kmalloc(sizeof(*s
), GFP_KERNEL
);
2479 rc
= seq_open(file
, &fib_route_seq_ops
);
2483 seq
= file
->private_data
;
2485 memset(s
, 0, sizeof(*s
));
2493 static const struct file_operations fib_route_fops
= {
2494 .owner
= THIS_MODULE
,
2495 .open
= fib_route_seq_open
,
2497 .llseek
= seq_lseek
,
2498 .release
= seq_release_private
,
2501 int __init
fib_proc_init(void)
2503 if (!proc_net_fops_create("fib_trie", S_IRUGO
, &fib_trie_fops
))
2506 if (!proc_net_fops_create("fib_triestat", S_IRUGO
, &fib_triestat_fops
))
2509 if (!proc_net_fops_create("route", S_IRUGO
, &fib_route_fops
))
2515 proc_net_remove("fib_triestat");
2517 proc_net_remove("fib_trie");
2522 void __init
fib_proc_exit(void)
2524 proc_net_remove("fib_trie");
2525 proc_net_remove("fib_triestat");
2526 proc_net_remove("route");
2529 #endif /* CONFIG_PROC_FS */