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
26 * Code from fib_hash has been reused which includes the following header:
29 * INET An implementation of the TCP/IP protocol suite for the LINUX
30 * operating system. INET is implemented using the BSD Socket
31 * interface as the means of communication with the user level.
33 * IPv4 FIB: lookup engine and maintenance routines.
36 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
38 * This program is free software; you can redistribute it and/or
39 * modify it under the terms of the GNU General Public License
40 * as published by the Free Software Foundation; either version
41 * 2 of the License, or (at your option) any later version.
43 * Substantial contributions to this work comes from:
45 * David S. Miller, <davem@davemloft.net>
46 * Stephen Hemminger <shemminger@osdl.org>
47 * Paul E. McKenney <paulmck@us.ibm.com>
48 * Patrick McHardy <kaber@trash.net>
51 #define VERSION "0.409"
53 #include <asm/uaccess.h>
54 #include <asm/system.h>
55 #include <linux/bitops.h>
56 #include <linux/types.h>
57 #include <linux/kernel.h>
59 #include <linux/string.h>
60 #include <linux/socket.h>
61 #include <linux/sockios.h>
62 #include <linux/errno.h>
64 #include <linux/inet.h>
65 #include <linux/inetdevice.h>
66 #include <linux/netdevice.h>
67 #include <linux/if_arp.h>
68 #include <linux/proc_fs.h>
69 #include <linux/rcupdate.h>
70 #include <linux/skbuff.h>
71 #include <linux/netlink.h>
72 #include <linux/init.h>
73 #include <linux/list.h>
74 #include <linux/slab.h>
75 #include <net/net_namespace.h>
77 #include <net/protocol.h>
78 #include <net/route.h>
81 #include <net/ip_fib.h>
82 #include "fib_lookup.h"
84 #define MAX_STAT_DEPTH 32
86 #define KEYLENGTH (8*sizeof(t_key))
88 typedef unsigned int t_key
;
92 #define NODE_TYPE_MASK 0x1UL
93 #define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
95 #define IS_TNODE(n) (!(n->parent & T_LEAF))
96 #define IS_LEAF(n) (n->parent & T_LEAF)
104 unsigned long parent
;
106 struct hlist_head list
;
111 struct hlist_node hlist
;
114 struct list_head falh
;
118 unsigned long parent
;
120 unsigned char pos
; /* 2log(KEYLENGTH) bits needed */
121 unsigned char bits
; /* 2log(KEYLENGTH) bits needed */
122 unsigned int full_children
; /* KEYLENGTH bits needed */
123 unsigned int empty_children
; /* KEYLENGTH bits needed */
126 struct work_struct work
;
127 struct tnode
*tnode_free
;
129 struct node
*child
[0];
132 #ifdef CONFIG_IP_FIB_TRIE_STATS
133 struct trie_use_stats
{
135 unsigned int backtrack
;
136 unsigned int semantic_match_passed
;
137 unsigned int semantic_match_miss
;
138 unsigned int null_node_hit
;
139 unsigned int resize_node_skipped
;
144 unsigned int totdepth
;
145 unsigned int maxdepth
;
148 unsigned int nullpointers
;
149 unsigned int prefixes
;
150 unsigned int nodesizes
[MAX_STAT_DEPTH
];
155 #ifdef CONFIG_IP_FIB_TRIE_STATS
156 struct trie_use_stats stats
;
160 static void put_child(struct trie
*t
, struct tnode
*tn
, int i
, struct node
*n
);
161 static void tnode_put_child_reorg(struct tnode
*tn
, int i
, struct node
*n
,
163 static struct node
*resize(struct trie
*t
, struct tnode
*tn
);
164 static struct tnode
*inflate(struct trie
*t
, struct tnode
*tn
);
165 static struct tnode
*halve(struct trie
*t
, struct tnode
*tn
);
166 /* tnodes to free after resize(); protected by RTNL */
167 static struct tnode
*tnode_free_head
;
168 static size_t tnode_free_size
;
171 * synchronize_rcu after call_rcu for that many pages; it should be especially
172 * useful before resizing the root node with PREEMPT_NONE configs; the value was
173 * obtained experimentally, aiming to avoid visible slowdown.
175 static const int sync_pages
= 128;
177 static struct kmem_cache
*fn_alias_kmem __read_mostly
;
178 static struct kmem_cache
*trie_leaf_kmem __read_mostly
;
180 static inline struct tnode
*node_parent(struct node
*node
)
182 return (struct tnode
*)(node
->parent
& ~NODE_TYPE_MASK
);
185 static inline struct tnode
*node_parent_rcu(struct node
*node
)
187 struct tnode
*ret
= node_parent(node
);
189 return rcu_dereference_check(ret
,
190 rcu_read_lock_held() ||
191 lockdep_rtnl_is_held());
194 /* Same as rcu_assign_pointer
195 * but that macro() assumes that value is a pointer.
197 static inline void node_set_parent(struct node
*node
, struct tnode
*ptr
)
200 node
->parent
= (unsigned long)ptr
| NODE_TYPE(node
);
203 static inline struct node
*tnode_get_child(struct tnode
*tn
, unsigned int i
)
205 BUG_ON(i
>= 1U << tn
->bits
);
210 static inline struct node
*tnode_get_child_rcu(struct tnode
*tn
, unsigned int i
)
212 struct node
*ret
= tnode_get_child(tn
, i
);
214 return rcu_dereference_check(ret
,
215 rcu_read_lock_held() ||
216 lockdep_rtnl_is_held());
219 static inline int tnode_child_length(const struct tnode
*tn
)
221 return 1 << tn
->bits
;
224 static inline t_key
mask_pfx(t_key k
, unsigned short l
)
226 return (l
== 0) ? 0 : k
>> (KEYLENGTH
-l
) << (KEYLENGTH
-l
);
229 static inline t_key
tkey_extract_bits(t_key a
, int offset
, int bits
)
231 if (offset
< KEYLENGTH
)
232 return ((t_key
)(a
<< offset
)) >> (KEYLENGTH
- bits
);
237 static inline int tkey_equals(t_key a
, t_key b
)
242 static inline int tkey_sub_equals(t_key a
, int offset
, int bits
, t_key b
)
244 if (bits
== 0 || offset
>= KEYLENGTH
)
246 bits
= bits
> KEYLENGTH
? KEYLENGTH
: bits
;
247 return ((a
^ b
) << offset
) >> (KEYLENGTH
- bits
) == 0;
250 static inline int tkey_mismatch(t_key a
, int offset
, t_key b
)
257 while ((diff
<< i
) >> (KEYLENGTH
-1) == 0)
263 To understand this stuff, an understanding of keys and all their bits is
264 necessary. Every node in the trie has a key associated with it, but not
265 all of the bits in that key are significant.
267 Consider a node 'n' and its parent 'tp'.
269 If n is a leaf, every bit in its key is significant. Its presence is
270 necessitated by path compression, since during a tree traversal (when
271 searching for a leaf - unless we are doing an insertion) we will completely
272 ignore all skipped bits we encounter. Thus we need to verify, at the end of
273 a potentially successful search, that we have indeed been walking the
276 Note that we can never "miss" the correct key in the tree if present by
277 following the wrong path. Path compression ensures that segments of the key
278 that are the same for all keys with a given prefix are skipped, but the
279 skipped part *is* identical for each node in the subtrie below the skipped
280 bit! trie_insert() in this implementation takes care of that - note the
281 call to tkey_sub_equals() in trie_insert().
283 if n is an internal node - a 'tnode' here, the various parts of its key
284 have many different meanings.
287 _________________________________________________________________
288 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
289 -----------------------------------------------------------------
290 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
292 _________________________________________________________________
293 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
294 -----------------------------------------------------------------
295 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
302 First, let's just ignore the bits that come before the parent tp, that is
303 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
304 not use them for anything.
306 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
307 index into the parent's child array. That is, they will be used to find
308 'n' among tp's children.
310 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
313 All the bits we have seen so far are significant to the node n. The rest
314 of the bits are really not needed or indeed known in n->key.
316 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
317 n's child array, and will of course be different for each child.
320 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
325 static inline void check_tnode(const struct tnode
*tn
)
327 WARN_ON(tn
&& tn
->pos
+tn
->bits
> 32);
330 static const int halve_threshold
= 25;
331 static const int inflate_threshold
= 50;
332 static const int halve_threshold_root
= 15;
333 static const int inflate_threshold_root
= 30;
335 static void __alias_free_mem(struct rcu_head
*head
)
337 struct fib_alias
*fa
= container_of(head
, struct fib_alias
, rcu
);
338 kmem_cache_free(fn_alias_kmem
, fa
);
341 static inline void alias_free_mem_rcu(struct fib_alias
*fa
)
343 call_rcu(&fa
->rcu
, __alias_free_mem
);
346 static void __leaf_free_rcu(struct rcu_head
*head
)
348 struct leaf
*l
= container_of(head
, struct leaf
, rcu
);
349 kmem_cache_free(trie_leaf_kmem
, l
);
352 static inline void free_leaf(struct leaf
*l
)
354 call_rcu_bh(&l
->rcu
, __leaf_free_rcu
);
357 static void __leaf_info_free_rcu(struct rcu_head
*head
)
359 kfree(container_of(head
, struct leaf_info
, rcu
));
362 static inline void free_leaf_info(struct leaf_info
*leaf
)
364 call_rcu(&leaf
->rcu
, __leaf_info_free_rcu
);
367 static struct tnode
*tnode_alloc(size_t size
)
369 if (size
<= PAGE_SIZE
)
370 return kzalloc(size
, GFP_KERNEL
);
372 return __vmalloc(size
, GFP_KERNEL
| __GFP_ZERO
, PAGE_KERNEL
);
375 static void __tnode_vfree(struct work_struct
*arg
)
377 struct tnode
*tn
= container_of(arg
, struct tnode
, work
);
381 static void __tnode_free_rcu(struct rcu_head
*head
)
383 struct tnode
*tn
= container_of(head
, struct tnode
, rcu
);
384 size_t size
= sizeof(struct tnode
) +
385 (sizeof(struct node
*) << tn
->bits
);
387 if (size
<= PAGE_SIZE
)
390 INIT_WORK(&tn
->work
, __tnode_vfree
);
391 schedule_work(&tn
->work
);
395 static inline void tnode_free(struct tnode
*tn
)
398 free_leaf((struct leaf
*) tn
);
400 call_rcu(&tn
->rcu
, __tnode_free_rcu
);
403 static void tnode_free_safe(struct tnode
*tn
)
406 tn
->tnode_free
= tnode_free_head
;
407 tnode_free_head
= tn
;
408 tnode_free_size
+= sizeof(struct tnode
) +
409 (sizeof(struct node
*) << tn
->bits
);
412 static void tnode_free_flush(void)
416 while ((tn
= tnode_free_head
)) {
417 tnode_free_head
= tn
->tnode_free
;
418 tn
->tnode_free
= NULL
;
422 if (tnode_free_size
>= PAGE_SIZE
* sync_pages
) {
428 static struct leaf
*leaf_new(void)
430 struct leaf
*l
= kmem_cache_alloc(trie_leaf_kmem
, GFP_KERNEL
);
433 INIT_HLIST_HEAD(&l
->list
);
438 static struct leaf_info
*leaf_info_new(int plen
)
440 struct leaf_info
*li
= kmalloc(sizeof(struct leaf_info
), GFP_KERNEL
);
443 INIT_LIST_HEAD(&li
->falh
);
448 static struct tnode
*tnode_new(t_key key
, int pos
, int bits
)
450 size_t sz
= sizeof(struct tnode
) + (sizeof(struct node
*) << bits
);
451 struct tnode
*tn
= tnode_alloc(sz
);
454 tn
->parent
= T_TNODE
;
458 tn
->full_children
= 0;
459 tn
->empty_children
= 1<<bits
;
462 pr_debug("AT %p s=%u %lu\n", tn
, (unsigned int) sizeof(struct tnode
),
463 (unsigned long) (sizeof(struct node
) << bits
));
468 * Check whether a tnode 'n' is "full", i.e. it is an internal node
469 * and no bits are skipped. See discussion in dyntree paper p. 6
472 static inline int tnode_full(const struct tnode
*tn
, const struct node
*n
)
474 if (n
== NULL
|| IS_LEAF(n
))
477 return ((struct tnode
*) n
)->pos
== tn
->pos
+ tn
->bits
;
480 static inline void put_child(struct trie
*t
, struct tnode
*tn
, int i
,
483 tnode_put_child_reorg(tn
, i
, n
, -1);
487 * Add a child at position i overwriting the old value.
488 * Update the value of full_children and empty_children.
491 static void tnode_put_child_reorg(struct tnode
*tn
, int i
, struct node
*n
,
494 struct node
*chi
= tn
->child
[i
];
497 BUG_ON(i
>= 1<<tn
->bits
);
499 /* update emptyChildren */
500 if (n
== NULL
&& chi
!= NULL
)
501 tn
->empty_children
++;
502 else if (n
!= NULL
&& chi
== NULL
)
503 tn
->empty_children
--;
505 /* update fullChildren */
507 wasfull
= tnode_full(tn
, chi
);
509 isfull
= tnode_full(tn
, n
);
510 if (wasfull
&& !isfull
)
512 else if (!wasfull
&& isfull
)
516 node_set_parent(n
, tn
);
518 rcu_assign_pointer(tn
->child
[i
], n
);
522 static struct node
*resize(struct trie
*t
, struct tnode
*tn
)
525 struct tnode
*old_tn
;
526 int inflate_threshold_use
;
527 int halve_threshold_use
;
533 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
534 tn
, inflate_threshold
, halve_threshold
);
537 if (tn
->empty_children
== tnode_child_length(tn
)) {
542 if (tn
->empty_children
== tnode_child_length(tn
) - 1)
545 * Double as long as the resulting node has a number of
546 * nonempty nodes that are above the threshold.
550 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
551 * the Helsinki University of Technology and Matti Tikkanen of Nokia
552 * Telecommunications, page 6:
553 * "A node is doubled if the ratio of non-empty children to all
554 * children in the *doubled* node is at least 'high'."
556 * 'high' in this instance is the variable 'inflate_threshold'. It
557 * is expressed as a percentage, so we multiply it with
558 * tnode_child_length() and instead of multiplying by 2 (since the
559 * child array will be doubled by inflate()) and multiplying
560 * the left-hand side by 100 (to handle the percentage thing) we
561 * multiply the left-hand side by 50.
563 * The left-hand side may look a bit weird: tnode_child_length(tn)
564 * - tn->empty_children is of course the number of non-null children
565 * in the current node. tn->full_children is the number of "full"
566 * children, that is non-null tnodes with a skip value of 0.
567 * All of those will be doubled in the resulting inflated tnode, so
568 * we just count them one extra time here.
570 * A clearer way to write this would be:
572 * to_be_doubled = tn->full_children;
573 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
576 * new_child_length = tnode_child_length(tn) * 2;
578 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
580 * if (new_fill_factor >= inflate_threshold)
582 * ...and so on, tho it would mess up the while () loop.
585 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
589 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
590 * inflate_threshold * new_child_length
592 * expand not_to_be_doubled and to_be_doubled, and shorten:
593 * 100 * (tnode_child_length(tn) - tn->empty_children +
594 * tn->full_children) >= inflate_threshold * new_child_length
596 * expand new_child_length:
597 * 100 * (tnode_child_length(tn) - tn->empty_children +
598 * tn->full_children) >=
599 * inflate_threshold * tnode_child_length(tn) * 2
602 * 50 * (tn->full_children + tnode_child_length(tn) -
603 * tn->empty_children) >= inflate_threshold *
604 * tnode_child_length(tn)
610 /* Keep root node larger */
612 if (!node_parent((struct node
*) tn
)) {
613 inflate_threshold_use
= inflate_threshold_root
;
614 halve_threshold_use
= halve_threshold_root
;
617 inflate_threshold_use
= inflate_threshold
;
618 halve_threshold_use
= halve_threshold
;
622 while ((tn
->full_children
> 0 && max_work
-- &&
623 50 * (tn
->full_children
+ tnode_child_length(tn
)
624 - tn
->empty_children
)
625 >= inflate_threshold_use
* tnode_child_length(tn
))) {
632 #ifdef CONFIG_IP_FIB_TRIE_STATS
633 t
->stats
.resize_node_skipped
++;
641 /* Return if at least one inflate is run */
642 if( max_work
!= MAX_WORK
)
643 return (struct node
*) tn
;
646 * Halve as long as the number of empty children in this
647 * node is above threshold.
651 while (tn
->bits
> 1 && max_work
-- &&
652 100 * (tnode_child_length(tn
) - tn
->empty_children
) <
653 halve_threshold_use
* tnode_child_length(tn
)) {
659 #ifdef CONFIG_IP_FIB_TRIE_STATS
660 t
->stats
.resize_node_skipped
++;
667 /* Only one child remains */
668 if (tn
->empty_children
== tnode_child_length(tn
) - 1) {
670 for (i
= 0; i
< tnode_child_length(tn
); i
++) {
677 /* compress one level */
679 node_set_parent(n
, NULL
);
684 return (struct node
*) tn
;
687 static struct tnode
*inflate(struct trie
*t
, struct tnode
*tn
)
689 struct tnode
*oldtnode
= tn
;
690 int olen
= tnode_child_length(tn
);
693 pr_debug("In inflate\n");
695 tn
= tnode_new(oldtnode
->key
, oldtnode
->pos
, oldtnode
->bits
+ 1);
698 return ERR_PTR(-ENOMEM
);
701 * Preallocate and store tnodes before the actual work so we
702 * don't get into an inconsistent state if memory allocation
703 * fails. In case of failure we return the oldnode and inflate
704 * of tnode is ignored.
707 for (i
= 0; i
< olen
; i
++) {
710 inode
= (struct tnode
*) tnode_get_child(oldtnode
, i
);
713 inode
->pos
== oldtnode
->pos
+ oldtnode
->bits
&&
715 struct tnode
*left
, *right
;
716 t_key m
= ~0U << (KEYLENGTH
- 1) >> inode
->pos
;
718 left
= tnode_new(inode
->key
&(~m
), inode
->pos
+ 1,
723 right
= tnode_new(inode
->key
|m
, inode
->pos
+ 1,
731 put_child(t
, tn
, 2*i
, (struct node
*) left
);
732 put_child(t
, tn
, 2*i
+1, (struct node
*) right
);
736 for (i
= 0; i
< olen
; i
++) {
738 struct node
*node
= tnode_get_child(oldtnode
, i
);
739 struct tnode
*left
, *right
;
746 /* A leaf or an internal node with skipped bits */
748 if (IS_LEAF(node
) || ((struct tnode
*) node
)->pos
>
749 tn
->pos
+ tn
->bits
- 1) {
750 if (tkey_extract_bits(node
->key
,
751 oldtnode
->pos
+ oldtnode
->bits
,
753 put_child(t
, tn
, 2*i
, node
);
755 put_child(t
, tn
, 2*i
+1, node
);
759 /* An internal node with two children */
760 inode
= (struct tnode
*) node
;
762 if (inode
->bits
== 1) {
763 put_child(t
, tn
, 2*i
, inode
->child
[0]);
764 put_child(t
, tn
, 2*i
+1, inode
->child
[1]);
766 tnode_free_safe(inode
);
770 /* An internal node with more than two children */
772 /* We will replace this node 'inode' with two new
773 * ones, 'left' and 'right', each with half of the
774 * original children. The two new nodes will have
775 * a position one bit further down the key and this
776 * means that the "significant" part of their keys
777 * (see the discussion near the top of this file)
778 * will differ by one bit, which will be "0" in
779 * left's key and "1" in right's key. Since we are
780 * moving the key position by one step, the bit that
781 * we are moving away from - the bit at position
782 * (inode->pos) - is the one that will differ between
783 * left and right. So... we synthesize that bit in the
785 * The mask 'm' below will be a single "one" bit at
786 * the position (inode->pos)
789 /* Use the old key, but set the new significant
793 left
= (struct tnode
*) tnode_get_child(tn
, 2*i
);
794 put_child(t
, tn
, 2*i
, NULL
);
798 right
= (struct tnode
*) tnode_get_child(tn
, 2*i
+1);
799 put_child(t
, tn
, 2*i
+1, NULL
);
803 size
= tnode_child_length(left
);
804 for (j
= 0; j
< size
; j
++) {
805 put_child(t
, left
, j
, inode
->child
[j
]);
806 put_child(t
, right
, j
, inode
->child
[j
+ size
]);
808 put_child(t
, tn
, 2*i
, resize(t
, left
));
809 put_child(t
, tn
, 2*i
+1, resize(t
, right
));
811 tnode_free_safe(inode
);
813 tnode_free_safe(oldtnode
);
817 int size
= tnode_child_length(tn
);
820 for (j
= 0; j
< size
; j
++)
822 tnode_free((struct tnode
*)tn
->child
[j
]);
826 return ERR_PTR(-ENOMEM
);
830 static struct tnode
*halve(struct trie
*t
, struct tnode
*tn
)
832 struct tnode
*oldtnode
= tn
;
833 struct node
*left
, *right
;
835 int olen
= tnode_child_length(tn
);
837 pr_debug("In halve\n");
839 tn
= tnode_new(oldtnode
->key
, oldtnode
->pos
, oldtnode
->bits
- 1);
842 return ERR_PTR(-ENOMEM
);
845 * Preallocate and store tnodes before the actual work so we
846 * don't get into an inconsistent state if memory allocation
847 * fails. In case of failure we return the oldnode and halve
848 * of tnode is ignored.
851 for (i
= 0; i
< olen
; i
+= 2) {
852 left
= tnode_get_child(oldtnode
, i
);
853 right
= tnode_get_child(oldtnode
, i
+1);
855 /* Two nonempty children */
859 newn
= tnode_new(left
->key
, tn
->pos
+ tn
->bits
, 1);
864 put_child(t
, tn
, i
/2, (struct node
*)newn
);
869 for (i
= 0; i
< olen
; i
+= 2) {
870 struct tnode
*newBinNode
;
872 left
= tnode_get_child(oldtnode
, i
);
873 right
= tnode_get_child(oldtnode
, i
+1);
875 /* At least one of the children is empty */
877 if (right
== NULL
) /* Both are empty */
879 put_child(t
, tn
, i
/2, right
);
884 put_child(t
, tn
, i
/2, left
);
888 /* Two nonempty children */
889 newBinNode
= (struct tnode
*) tnode_get_child(tn
, i
/2);
890 put_child(t
, tn
, i
/2, NULL
);
891 put_child(t
, newBinNode
, 0, left
);
892 put_child(t
, newBinNode
, 1, right
);
893 put_child(t
, tn
, i
/2, resize(t
, newBinNode
));
895 tnode_free_safe(oldtnode
);
899 int size
= tnode_child_length(tn
);
902 for (j
= 0; j
< size
; j
++)
904 tnode_free((struct tnode
*)tn
->child
[j
]);
908 return ERR_PTR(-ENOMEM
);
912 /* readside must use rcu_read_lock currently dump routines
913 via get_fa_head and dump */
915 static struct leaf_info
*find_leaf_info(struct leaf
*l
, int plen
)
917 struct hlist_head
*head
= &l
->list
;
918 struct hlist_node
*node
;
919 struct leaf_info
*li
;
921 hlist_for_each_entry_rcu(li
, node
, head
, hlist
)
922 if (li
->plen
== plen
)
928 static inline struct list_head
*get_fa_head(struct leaf
*l
, int plen
)
930 struct leaf_info
*li
= find_leaf_info(l
, plen
);
938 static void insert_leaf_info(struct hlist_head
*head
, struct leaf_info
*new)
940 struct leaf_info
*li
= NULL
, *last
= NULL
;
941 struct hlist_node
*node
;
943 if (hlist_empty(head
)) {
944 hlist_add_head_rcu(&new->hlist
, head
);
946 hlist_for_each_entry(li
, node
, head
, hlist
) {
947 if (new->plen
> li
->plen
)
953 hlist_add_after_rcu(&last
->hlist
, &new->hlist
);
955 hlist_add_before_rcu(&new->hlist
, &li
->hlist
);
959 /* rcu_read_lock needs to be hold by caller from readside */
962 fib_find_node(struct trie
*t
, u32 key
)
969 n
= rcu_dereference_check(t
->trie
,
970 rcu_read_lock_held() ||
971 lockdep_rtnl_is_held());
973 while (n
!= NULL
&& NODE_TYPE(n
) == T_TNODE
) {
974 tn
= (struct tnode
*) n
;
978 if (tkey_sub_equals(tn
->key
, pos
, tn
->pos
-pos
, key
)) {
979 pos
= tn
->pos
+ tn
->bits
;
980 n
= tnode_get_child_rcu(tn
,
981 tkey_extract_bits(key
,
987 /* Case we have found a leaf. Compare prefixes */
989 if (n
!= NULL
&& IS_LEAF(n
) && tkey_equals(key
, n
->key
))
990 return (struct leaf
*)n
;
995 static void trie_rebalance(struct trie
*t
, struct tnode
*tn
)
1003 while (tn
!= NULL
&& (tp
= node_parent((struct node
*)tn
)) != NULL
) {
1004 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1005 wasfull
= tnode_full(tp
, tnode_get_child(tp
, cindex
));
1006 tn
= (struct tnode
*) resize(t
, (struct tnode
*)tn
);
1008 tnode_put_child_reorg((struct tnode
*)tp
, cindex
,
1009 (struct node
*)tn
, wasfull
);
1011 tp
= node_parent((struct node
*) tn
);
1013 rcu_assign_pointer(t
->trie
, (struct node
*)tn
);
1021 /* Handle last (top) tnode */
1023 tn
= (struct tnode
*)resize(t
, (struct tnode
*)tn
);
1025 rcu_assign_pointer(t
->trie
, (struct node
*)tn
);
1029 /* only used from updater-side */
1031 static struct list_head
*fib_insert_node(struct trie
*t
, u32 key
, int plen
)
1034 struct tnode
*tp
= NULL
, *tn
= NULL
;
1038 struct list_head
*fa_head
= NULL
;
1039 struct leaf_info
*li
;
1045 /* If we point to NULL, stop. Either the tree is empty and we should
1046 * just put a new leaf in if, or we have reached an empty child slot,
1047 * and we should just put our new leaf in that.
1048 * If we point to a T_TNODE, check if it matches our key. Note that
1049 * a T_TNODE might be skipping any number of bits - its 'pos' need
1050 * not be the parent's 'pos'+'bits'!
1052 * If it does match the current key, get pos/bits from it, extract
1053 * the index from our key, push the T_TNODE and walk the tree.
1055 * If it doesn't, we have to replace it with a new T_TNODE.
1057 * If we point to a T_LEAF, it might or might not have the same key
1058 * as we do. If it does, just change the value, update the T_LEAF's
1059 * value, and return it.
1060 * If it doesn't, we need to replace it with a T_TNODE.
1063 while (n
!= NULL
&& NODE_TYPE(n
) == T_TNODE
) {
1064 tn
= (struct tnode
*) n
;
1068 if (tkey_sub_equals(tn
->key
, pos
, tn
->pos
-pos
, key
)) {
1070 pos
= tn
->pos
+ tn
->bits
;
1071 n
= tnode_get_child(tn
,
1072 tkey_extract_bits(key
,
1076 BUG_ON(n
&& node_parent(n
) != tn
);
1082 * n ----> NULL, LEAF or TNODE
1084 * tp is n's (parent) ----> NULL or TNODE
1087 BUG_ON(tp
&& IS_LEAF(tp
));
1089 /* Case 1: n is a leaf. Compare prefixes */
1091 if (n
!= NULL
&& IS_LEAF(n
) && tkey_equals(key
, n
->key
)) {
1092 l
= (struct leaf
*) n
;
1093 li
= leaf_info_new(plen
);
1098 fa_head
= &li
->falh
;
1099 insert_leaf_info(&l
->list
, li
);
1108 li
= leaf_info_new(plen
);
1115 fa_head
= &li
->falh
;
1116 insert_leaf_info(&l
->list
, li
);
1118 if (t
->trie
&& n
== NULL
) {
1119 /* Case 2: n is NULL, and will just insert a new leaf */
1121 node_set_parent((struct node
*)l
, tp
);
1123 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1124 put_child(t
, (struct tnode
*)tp
, cindex
, (struct node
*)l
);
1126 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1128 * Add a new tnode here
1129 * first tnode need some special handling
1133 pos
= tp
->pos
+tp
->bits
;
1138 newpos
= tkey_mismatch(key
, pos
, n
->key
);
1139 tn
= tnode_new(n
->key
, newpos
, 1);
1142 tn
= tnode_new(key
, newpos
, 1); /* First tnode */
1151 node_set_parent((struct node
*)tn
, tp
);
1153 missbit
= tkey_extract_bits(key
, newpos
, 1);
1154 put_child(t
, tn
, missbit
, (struct node
*)l
);
1155 put_child(t
, tn
, 1-missbit
, n
);
1158 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1159 put_child(t
, (struct tnode
*)tp
, cindex
,
1162 rcu_assign_pointer(t
->trie
, (struct node
*)tn
);
1167 if (tp
&& tp
->pos
+ tp
->bits
> 32)
1168 pr_warning("fib_trie"
1169 " tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1170 tp
, tp
->pos
, tp
->bits
, key
, plen
);
1172 /* Rebalance the trie */
1174 trie_rebalance(t
, tp
);
1180 * Caller must hold RTNL.
1182 int fib_table_insert(struct fib_table
*tb
, struct fib_config
*cfg
)
1184 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1185 struct fib_alias
*fa
, *new_fa
;
1186 struct list_head
*fa_head
= NULL
;
1187 struct fib_info
*fi
;
1188 int plen
= cfg
->fc_dst_len
;
1189 u8 tos
= cfg
->fc_tos
;
1197 key
= ntohl(cfg
->fc_dst
);
1199 pr_debug("Insert table=%u %08x/%d\n", tb
->tb_id
, key
, plen
);
1201 mask
= ntohl(inet_make_mask(plen
));
1208 fi
= fib_create_info(cfg
);
1214 l
= fib_find_node(t
, key
);
1218 fa_head
= get_fa_head(l
, plen
);
1219 fa
= fib_find_alias(fa_head
, tos
, fi
->fib_priority
);
1222 /* Now fa, if non-NULL, points to the first fib alias
1223 * with the same keys [prefix,tos,priority], if such key already
1224 * exists or to the node before which we will insert new one.
1226 * If fa is NULL, we will need to allocate a new one and
1227 * insert to the head of f.
1229 * If f is NULL, no fib node matched the destination key
1230 * and we need to allocate a new one of those as well.
1233 if (fa
&& fa
->fa_tos
== tos
&&
1234 fa
->fa_info
->fib_priority
== fi
->fib_priority
) {
1235 struct fib_alias
*fa_first
, *fa_match
;
1238 if (cfg
->fc_nlflags
& NLM_F_EXCL
)
1242 * 1. Find exact match for type, scope, fib_info to avoid
1244 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1248 fa
= list_entry(fa
->fa_list
.prev
, struct fib_alias
, fa_list
);
1249 list_for_each_entry_continue(fa
, fa_head
, fa_list
) {
1250 if (fa
->fa_tos
!= tos
)
1252 if (fa
->fa_info
->fib_priority
!= fi
->fib_priority
)
1254 if (fa
->fa_type
== cfg
->fc_type
&&
1255 fa
->fa_scope
== cfg
->fc_scope
&&
1256 fa
->fa_info
== fi
) {
1262 if (cfg
->fc_nlflags
& NLM_F_REPLACE
) {
1263 struct fib_info
*fi_drop
;
1273 new_fa
= kmem_cache_alloc(fn_alias_kmem
, GFP_KERNEL
);
1277 fi_drop
= fa
->fa_info
;
1278 new_fa
->fa_tos
= fa
->fa_tos
;
1279 new_fa
->fa_info
= fi
;
1280 new_fa
->fa_type
= cfg
->fc_type
;
1281 new_fa
->fa_scope
= cfg
->fc_scope
;
1282 state
= fa
->fa_state
;
1283 new_fa
->fa_state
= state
& ~FA_S_ACCESSED
;
1285 list_replace_rcu(&fa
->fa_list
, &new_fa
->fa_list
);
1286 alias_free_mem_rcu(fa
);
1288 fib_release_info(fi_drop
);
1289 if (state
& FA_S_ACCESSED
)
1290 rt_cache_flush(cfg
->fc_nlinfo
.nl_net
, -1);
1291 rtmsg_fib(RTM_NEWROUTE
, htonl(key
), new_fa
, plen
,
1292 tb
->tb_id
, &cfg
->fc_nlinfo
, NLM_F_REPLACE
);
1296 /* Error if we find a perfect match which
1297 * uses the same scope, type, and nexthop
1303 if (!(cfg
->fc_nlflags
& NLM_F_APPEND
))
1307 if (!(cfg
->fc_nlflags
& NLM_F_CREATE
))
1311 new_fa
= kmem_cache_alloc(fn_alias_kmem
, GFP_KERNEL
);
1315 new_fa
->fa_info
= fi
;
1316 new_fa
->fa_tos
= tos
;
1317 new_fa
->fa_type
= cfg
->fc_type
;
1318 new_fa
->fa_scope
= cfg
->fc_scope
;
1319 new_fa
->fa_state
= 0;
1321 * Insert new entry to the list.
1325 fa_head
= fib_insert_node(t
, key
, plen
);
1326 if (unlikely(!fa_head
)) {
1328 goto out_free_new_fa
;
1332 list_add_tail_rcu(&new_fa
->fa_list
,
1333 (fa
? &fa
->fa_list
: fa_head
));
1335 rt_cache_flush(cfg
->fc_nlinfo
.nl_net
, -1);
1336 rtmsg_fib(RTM_NEWROUTE
, htonl(key
), new_fa
, plen
, tb
->tb_id
,
1337 &cfg
->fc_nlinfo
, 0);
1342 kmem_cache_free(fn_alias_kmem
, new_fa
);
1344 fib_release_info(fi
);
1349 /* should be called with rcu_read_lock */
1350 static int check_leaf(struct trie
*t
, struct leaf
*l
,
1351 t_key key
, const struct flowi
*flp
,
1352 struct fib_result
*res
)
1354 struct leaf_info
*li
;
1355 struct hlist_head
*hhead
= &l
->list
;
1356 struct hlist_node
*node
;
1358 hlist_for_each_entry_rcu(li
, node
, hhead
, hlist
) {
1360 int plen
= li
->plen
;
1361 __be32 mask
= inet_make_mask(plen
);
1363 if (l
->key
!= (key
& ntohl(mask
)))
1366 err
= fib_semantic_match(&li
->falh
, flp
, res
, plen
);
1368 #ifdef CONFIG_IP_FIB_TRIE_STATS
1370 t
->stats
.semantic_match_passed
++;
1372 t
->stats
.semantic_match_miss
++;
1381 int fib_table_lookup(struct fib_table
*tb
, const struct flowi
*flp
,
1382 struct fib_result
*res
)
1384 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1389 t_key key
= ntohl(flp
->fl4_dst
);
1392 int current_prefix_length
= KEYLENGTH
;
1394 t_key node_prefix
, key_prefix
, pref_mismatch
;
1399 n
= rcu_dereference(t
->trie
);
1403 #ifdef CONFIG_IP_FIB_TRIE_STATS
1409 ret
= check_leaf(t
, (struct leaf
*)n
, key
, flp
, res
);
1413 pn
= (struct tnode
*) n
;
1421 cindex
= tkey_extract_bits(mask_pfx(key
, current_prefix_length
),
1424 n
= tnode_get_child_rcu(pn
, cindex
);
1427 #ifdef CONFIG_IP_FIB_TRIE_STATS
1428 t
->stats
.null_node_hit
++;
1434 ret
= check_leaf(t
, (struct leaf
*)n
, key
, flp
, res
);
1440 cn
= (struct tnode
*)n
;
1443 * It's a tnode, and we can do some extra checks here if we
1444 * like, to avoid descending into a dead-end branch.
1445 * This tnode is in the parent's child array at index
1446 * key[p_pos..p_pos+p_bits] but potentially with some bits
1447 * chopped off, so in reality the index may be just a
1448 * subprefix, padded with zero at the end.
1449 * We can also take a look at any skipped bits in this
1450 * tnode - everything up to p_pos is supposed to be ok,
1451 * and the non-chopped bits of the index (se previous
1452 * paragraph) are also guaranteed ok, but the rest is
1453 * considered unknown.
1455 * The skipped bits are key[pos+bits..cn->pos].
1458 /* If current_prefix_length < pos+bits, we are already doing
1459 * actual prefix matching, which means everything from
1460 * pos+(bits-chopped_off) onward must be zero along some
1461 * branch of this subtree - otherwise there is *no* valid
1462 * prefix present. Here we can only check the skipped
1463 * bits. Remember, since we have already indexed into the
1464 * parent's child array, we know that the bits we chopped of
1468 /* NOTA BENE: Checking only skipped bits
1469 for the new node here */
1471 if (current_prefix_length
< pos
+bits
) {
1472 if (tkey_extract_bits(cn
->key
, current_prefix_length
,
1473 cn
->pos
- current_prefix_length
)
1479 * If chopped_off=0, the index is fully validated and we
1480 * only need to look at the skipped bits for this, the new,
1481 * tnode. What we actually want to do is to find out if
1482 * these skipped bits match our key perfectly, or if we will
1483 * have to count on finding a matching prefix further down,
1484 * because if we do, we would like to have some way of
1485 * verifying the existence of such a prefix at this point.
1488 /* The only thing we can do at this point is to verify that
1489 * any such matching prefix can indeed be a prefix to our
1490 * key, and if the bits in the node we are inspecting that
1491 * do not match our key are not ZERO, this cannot be true.
1492 * Thus, find out where there is a mismatch (before cn->pos)
1493 * and verify that all the mismatching bits are zero in the
1498 * Note: We aren't very concerned about the piece of
1499 * the key that precede pn->pos+pn->bits, since these
1500 * have already been checked. The bits after cn->pos
1501 * aren't checked since these are by definition
1502 * "unknown" at this point. Thus, what we want to see
1503 * is if we are about to enter the "prefix matching"
1504 * state, and in that case verify that the skipped
1505 * bits that will prevail throughout this subtree are
1506 * zero, as they have to be if we are to find a
1510 node_prefix
= mask_pfx(cn
->key
, cn
->pos
);
1511 key_prefix
= mask_pfx(key
, cn
->pos
);
1512 pref_mismatch
= key_prefix
^node_prefix
;
1516 * In short: If skipped bits in this node do not match
1517 * the search key, enter the "prefix matching"
1520 if (pref_mismatch
) {
1521 while (!(pref_mismatch
& (1<<(KEYLENGTH
-1)))) {
1523 pref_mismatch
= pref_mismatch
<< 1;
1525 key_prefix
= tkey_extract_bits(cn
->key
, mp
, cn
->pos
-mp
);
1527 if (key_prefix
!= 0)
1530 if (current_prefix_length
>= cn
->pos
)
1531 current_prefix_length
= mp
;
1534 pn
= (struct tnode
*)n
; /* Descend */
1541 /* As zero don't change the child key (cindex) */
1542 while ((chopped_off
<= pn
->bits
)
1543 && !(cindex
& (1<<(chopped_off
-1))))
1546 /* Decrease current_... with bits chopped off */
1547 if (current_prefix_length
> pn
->pos
+ pn
->bits
- chopped_off
)
1548 current_prefix_length
= pn
->pos
+ pn
->bits
1552 * Either we do the actual chop off according or if we have
1553 * chopped off all bits in this tnode walk up to our parent.
1556 if (chopped_off
<= pn
->bits
) {
1557 cindex
&= ~(1 << (chopped_off
-1));
1559 struct tnode
*parent
= node_parent_rcu((struct node
*) pn
);
1563 /* Get Child's index */
1564 cindex
= tkey_extract_bits(pn
->key
, parent
->pos
, parent
->bits
);
1568 #ifdef CONFIG_IP_FIB_TRIE_STATS
1569 t
->stats
.backtrack
++;
1582 * Remove the leaf and return parent.
1584 static void trie_leaf_remove(struct trie
*t
, struct leaf
*l
)
1586 struct tnode
*tp
= node_parent((struct node
*) l
);
1588 pr_debug("entering trie_leaf_remove(%p)\n", l
);
1591 t_key cindex
= tkey_extract_bits(l
->key
, tp
->pos
, tp
->bits
);
1592 put_child(t
, (struct tnode
*)tp
, cindex
, NULL
);
1593 trie_rebalance(t
, tp
);
1595 rcu_assign_pointer(t
->trie
, NULL
);
1601 * Caller must hold RTNL.
1603 int fib_table_delete(struct fib_table
*tb
, struct fib_config
*cfg
)
1605 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1607 int plen
= cfg
->fc_dst_len
;
1608 u8 tos
= cfg
->fc_tos
;
1609 struct fib_alias
*fa
, *fa_to_delete
;
1610 struct list_head
*fa_head
;
1612 struct leaf_info
*li
;
1617 key
= ntohl(cfg
->fc_dst
);
1618 mask
= ntohl(inet_make_mask(plen
));
1624 l
= fib_find_node(t
, key
);
1629 fa_head
= get_fa_head(l
, plen
);
1630 fa
= fib_find_alias(fa_head
, tos
, 0);
1635 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key
, plen
, tos
, t
);
1637 fa_to_delete
= NULL
;
1638 fa
= list_entry(fa
->fa_list
.prev
, struct fib_alias
, fa_list
);
1639 list_for_each_entry_continue(fa
, fa_head
, fa_list
) {
1640 struct fib_info
*fi
= fa
->fa_info
;
1642 if (fa
->fa_tos
!= tos
)
1645 if ((!cfg
->fc_type
|| fa
->fa_type
== cfg
->fc_type
) &&
1646 (cfg
->fc_scope
== RT_SCOPE_NOWHERE
||
1647 fa
->fa_scope
== cfg
->fc_scope
) &&
1648 (!cfg
->fc_protocol
||
1649 fi
->fib_protocol
== cfg
->fc_protocol
) &&
1650 fib_nh_match(cfg
, fi
) == 0) {
1660 rtmsg_fib(RTM_DELROUTE
, htonl(key
), fa
, plen
, tb
->tb_id
,
1661 &cfg
->fc_nlinfo
, 0);
1663 l
= fib_find_node(t
, key
);
1664 li
= find_leaf_info(l
, plen
);
1666 list_del_rcu(&fa
->fa_list
);
1668 if (list_empty(fa_head
)) {
1669 hlist_del_rcu(&li
->hlist
);
1673 if (hlist_empty(&l
->list
))
1674 trie_leaf_remove(t
, l
);
1676 if (fa
->fa_state
& FA_S_ACCESSED
)
1677 rt_cache_flush(cfg
->fc_nlinfo
.nl_net
, -1);
1679 fib_release_info(fa
->fa_info
);
1680 alias_free_mem_rcu(fa
);
1684 static int trie_flush_list(struct list_head
*head
)
1686 struct fib_alias
*fa
, *fa_node
;
1689 list_for_each_entry_safe(fa
, fa_node
, head
, fa_list
) {
1690 struct fib_info
*fi
= fa
->fa_info
;
1692 if (fi
&& (fi
->fib_flags
& RTNH_F_DEAD
)) {
1693 list_del_rcu(&fa
->fa_list
);
1694 fib_release_info(fa
->fa_info
);
1695 alias_free_mem_rcu(fa
);
1702 static int trie_flush_leaf(struct leaf
*l
)
1705 struct hlist_head
*lih
= &l
->list
;
1706 struct hlist_node
*node
, *tmp
;
1707 struct leaf_info
*li
= NULL
;
1709 hlist_for_each_entry_safe(li
, node
, tmp
, lih
, hlist
) {
1710 found
+= trie_flush_list(&li
->falh
);
1712 if (list_empty(&li
->falh
)) {
1713 hlist_del_rcu(&li
->hlist
);
1721 * Scan for the next right leaf starting at node p->child[idx]
1722 * Since we have back pointer, no recursion necessary.
1724 static struct leaf
*leaf_walk_rcu(struct tnode
*p
, struct node
*c
)
1730 idx
= tkey_extract_bits(c
->key
, p
->pos
, p
->bits
) + 1;
1734 while (idx
< 1u << p
->bits
) {
1735 c
= tnode_get_child_rcu(p
, idx
++);
1740 prefetch(p
->child
[idx
]);
1741 return (struct leaf
*) c
;
1744 /* Rescan start scanning in new node */
1745 p
= (struct tnode
*) c
;
1749 /* Node empty, walk back up to parent */
1750 c
= (struct node
*) p
;
1751 } while ( (p
= node_parent_rcu(c
)) != NULL
);
1753 return NULL
; /* Root of trie */
1756 static struct leaf
*trie_firstleaf(struct trie
*t
)
1758 struct tnode
*n
= (struct tnode
*) rcu_dereference_check(t
->trie
,
1759 rcu_read_lock_held() ||
1760 lockdep_rtnl_is_held());
1765 if (IS_LEAF(n
)) /* trie is just a leaf */
1766 return (struct leaf
*) n
;
1768 return leaf_walk_rcu(n
, NULL
);
1771 static struct leaf
*trie_nextleaf(struct leaf
*l
)
1773 struct node
*c
= (struct node
*) l
;
1774 struct tnode
*p
= node_parent_rcu(c
);
1777 return NULL
; /* trie with just one leaf */
1779 return leaf_walk_rcu(p
, c
);
1782 static struct leaf
*trie_leafindex(struct trie
*t
, int index
)
1784 struct leaf
*l
= trie_firstleaf(t
);
1786 while (l
&& index
-- > 0)
1787 l
= trie_nextleaf(l
);
1794 * Caller must hold RTNL.
1796 int fib_table_flush(struct fib_table
*tb
)
1798 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1799 struct leaf
*l
, *ll
= NULL
;
1802 for (l
= trie_firstleaf(t
); l
; l
= trie_nextleaf(l
)) {
1803 found
+= trie_flush_leaf(l
);
1805 if (ll
&& hlist_empty(&ll
->list
))
1806 trie_leaf_remove(t
, ll
);
1810 if (ll
&& hlist_empty(&ll
->list
))
1811 trie_leaf_remove(t
, ll
);
1813 pr_debug("trie_flush found=%d\n", found
);
1817 void fib_table_select_default(struct fib_table
*tb
,
1818 const struct flowi
*flp
,
1819 struct fib_result
*res
)
1821 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1822 int order
, last_idx
;
1823 struct fib_info
*fi
= NULL
;
1824 struct fib_info
*last_resort
;
1825 struct fib_alias
*fa
= NULL
;
1826 struct list_head
*fa_head
;
1835 l
= fib_find_node(t
, 0);
1839 fa_head
= get_fa_head(l
, 0);
1843 if (list_empty(fa_head
))
1846 list_for_each_entry_rcu(fa
, fa_head
, fa_list
) {
1847 struct fib_info
*next_fi
= fa
->fa_info
;
1849 if (fa
->fa_scope
!= res
->scope
||
1850 fa
->fa_type
!= RTN_UNICAST
)
1853 if (next_fi
->fib_priority
> res
->fi
->fib_priority
)
1855 if (!next_fi
->fib_nh
[0].nh_gw
||
1856 next_fi
->fib_nh
[0].nh_scope
!= RT_SCOPE_LINK
)
1858 fa
->fa_state
|= FA_S_ACCESSED
;
1861 if (next_fi
!= res
->fi
)
1863 } else if (!fib_detect_death(fi
, order
, &last_resort
,
1864 &last_idx
, tb
->tb_default
)) {
1865 fib_result_assign(res
, fi
);
1866 tb
->tb_default
= order
;
1872 if (order
<= 0 || fi
== NULL
) {
1873 tb
->tb_default
= -1;
1877 if (!fib_detect_death(fi
, order
, &last_resort
, &last_idx
,
1879 fib_result_assign(res
, fi
);
1880 tb
->tb_default
= order
;
1884 fib_result_assign(res
, last_resort
);
1885 tb
->tb_default
= last_idx
;
1890 static int fn_trie_dump_fa(t_key key
, int plen
, struct list_head
*fah
,
1891 struct fib_table
*tb
,
1892 struct sk_buff
*skb
, struct netlink_callback
*cb
)
1895 struct fib_alias
*fa
;
1896 __be32 xkey
= htonl(key
);
1901 /* rcu_read_lock is hold by caller */
1903 list_for_each_entry_rcu(fa
, fah
, fa_list
) {
1909 if (fib_dump_info(skb
, NETLINK_CB(cb
->skb
).pid
,
1918 fa
->fa_info
, NLM_F_MULTI
) < 0) {
1928 static int fn_trie_dump_leaf(struct leaf
*l
, struct fib_table
*tb
,
1929 struct sk_buff
*skb
, struct netlink_callback
*cb
)
1931 struct leaf_info
*li
;
1932 struct hlist_node
*node
;
1938 /* rcu_read_lock is hold by caller */
1939 hlist_for_each_entry_rcu(li
, node
, &l
->list
, hlist
) {
1948 if (list_empty(&li
->falh
))
1951 if (fn_trie_dump_fa(l
->key
, li
->plen
, &li
->falh
, tb
, skb
, cb
) < 0) {
1962 int fib_table_dump(struct fib_table
*tb
, struct sk_buff
*skb
,
1963 struct netlink_callback
*cb
)
1966 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1967 t_key key
= cb
->args
[2];
1968 int count
= cb
->args
[3];
1971 /* Dump starting at last key.
1972 * Note: 0.0.0.0/0 (ie default) is first key.
1975 l
= trie_firstleaf(t
);
1977 /* Normally, continue from last key, but if that is missing
1978 * fallback to using slow rescan
1980 l
= fib_find_node(t
, key
);
1982 l
= trie_leafindex(t
, count
);
1986 cb
->args
[2] = l
->key
;
1987 if (fn_trie_dump_leaf(l
, tb
, skb
, cb
) < 0) {
1988 cb
->args
[3] = count
;
1994 l
= trie_nextleaf(l
);
1995 memset(&cb
->args
[4], 0,
1996 sizeof(cb
->args
) - 4*sizeof(cb
->args
[0]));
1998 cb
->args
[3] = count
;
2004 void __init
fib_hash_init(void)
2006 fn_alias_kmem
= kmem_cache_create("ip_fib_alias",
2007 sizeof(struct fib_alias
),
2008 0, SLAB_PANIC
, NULL
);
2010 trie_leaf_kmem
= kmem_cache_create("ip_fib_trie",
2011 max(sizeof(struct leaf
),
2012 sizeof(struct leaf_info
)),
2013 0, SLAB_PANIC
, NULL
);
2017 /* Fix more generic FIB names for init later */
2018 struct fib_table
*fib_hash_table(u32 id
)
2020 struct fib_table
*tb
;
2023 tb
= kmalloc(sizeof(struct fib_table
) + sizeof(struct trie
),
2029 tb
->tb_default
= -1;
2031 t
= (struct trie
*) tb
->tb_data
;
2032 memset(t
, 0, sizeof(*t
));
2034 if (id
== RT_TABLE_LOCAL
)
2035 pr_info("IPv4 FIB: Using LC-trie version %s\n", VERSION
);
2040 #ifdef CONFIG_PROC_FS
2041 /* Depth first Trie walk iterator */
2042 struct fib_trie_iter
{
2043 struct seq_net_private p
;
2044 struct fib_table
*tb
;
2045 struct tnode
*tnode
;
2050 static struct node
*fib_trie_get_next(struct fib_trie_iter
*iter
)
2052 struct tnode
*tn
= iter
->tnode
;
2053 unsigned cindex
= iter
->index
;
2056 /* A single entry routing table */
2060 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2061 iter
->tnode
, iter
->index
, iter
->depth
);
2063 while (cindex
< (1<<tn
->bits
)) {
2064 struct node
*n
= tnode_get_child_rcu(tn
, cindex
);
2069 iter
->index
= cindex
+ 1;
2071 /* push down one level */
2072 iter
->tnode
= (struct tnode
*) n
;
2082 /* Current node exhausted, pop back up */
2083 p
= node_parent_rcu((struct node
*)tn
);
2085 cindex
= tkey_extract_bits(tn
->key
, p
->pos
, p
->bits
)+1;
2095 static struct node
*fib_trie_get_first(struct fib_trie_iter
*iter
,
2103 n
= rcu_dereference(t
->trie
);
2108 iter
->tnode
= (struct tnode
*) n
;
2120 static void trie_collect_stats(struct trie
*t
, struct trie_stat
*s
)
2123 struct fib_trie_iter iter
;
2125 memset(s
, 0, sizeof(*s
));
2128 for (n
= fib_trie_get_first(&iter
, t
); n
; n
= fib_trie_get_next(&iter
)) {
2130 struct leaf
*l
= (struct leaf
*)n
;
2131 struct leaf_info
*li
;
2132 struct hlist_node
*tmp
;
2135 s
->totdepth
+= iter
.depth
;
2136 if (iter
.depth
> s
->maxdepth
)
2137 s
->maxdepth
= iter
.depth
;
2139 hlist_for_each_entry_rcu(li
, tmp
, &l
->list
, hlist
)
2142 const struct tnode
*tn
= (const struct tnode
*) n
;
2146 if (tn
->bits
< MAX_STAT_DEPTH
)
2147 s
->nodesizes
[tn
->bits
]++;
2149 for (i
= 0; i
< (1<<tn
->bits
); i
++)
2158 * This outputs /proc/net/fib_triestats
2160 static void trie_show_stats(struct seq_file
*seq
, struct trie_stat
*stat
)
2162 unsigned i
, max
, pointers
, bytes
, avdepth
;
2165 avdepth
= stat
->totdepth
*100 / stat
->leaves
;
2169 seq_printf(seq
, "\tAver depth: %u.%02d\n",
2170 avdepth
/ 100, avdepth
% 100);
2171 seq_printf(seq
, "\tMax depth: %u\n", stat
->maxdepth
);
2173 seq_printf(seq
, "\tLeaves: %u\n", stat
->leaves
);
2174 bytes
= sizeof(struct leaf
) * stat
->leaves
;
2176 seq_printf(seq
, "\tPrefixes: %u\n", stat
->prefixes
);
2177 bytes
+= sizeof(struct leaf_info
) * stat
->prefixes
;
2179 seq_printf(seq
, "\tInternal nodes: %u\n\t", stat
->tnodes
);
2180 bytes
+= sizeof(struct tnode
) * stat
->tnodes
;
2182 max
= MAX_STAT_DEPTH
;
2183 while (max
> 0 && stat
->nodesizes
[max
-1] == 0)
2187 for (i
= 1; i
<= max
; i
++)
2188 if (stat
->nodesizes
[i
] != 0) {
2189 seq_printf(seq
, " %u: %u", i
, stat
->nodesizes
[i
]);
2190 pointers
+= (1<<i
) * stat
->nodesizes
[i
];
2192 seq_putc(seq
, '\n');
2193 seq_printf(seq
, "\tPointers: %u\n", pointers
);
2195 bytes
+= sizeof(struct node
*) * pointers
;
2196 seq_printf(seq
, "Null ptrs: %u\n", stat
->nullpointers
);
2197 seq_printf(seq
, "Total size: %u kB\n", (bytes
+ 1023) / 1024);
2200 #ifdef CONFIG_IP_FIB_TRIE_STATS
2201 static void trie_show_usage(struct seq_file
*seq
,
2202 const struct trie_use_stats
*stats
)
2204 seq_printf(seq
, "\nCounters:\n---------\n");
2205 seq_printf(seq
, "gets = %u\n", stats
->gets
);
2206 seq_printf(seq
, "backtracks = %u\n", stats
->backtrack
);
2207 seq_printf(seq
, "semantic match passed = %u\n",
2208 stats
->semantic_match_passed
);
2209 seq_printf(seq
, "semantic match miss = %u\n",
2210 stats
->semantic_match_miss
);
2211 seq_printf(seq
, "null node hit= %u\n", stats
->null_node_hit
);
2212 seq_printf(seq
, "skipped node resize = %u\n\n",
2213 stats
->resize_node_skipped
);
2215 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2217 static void fib_table_print(struct seq_file
*seq
, struct fib_table
*tb
)
2219 if (tb
->tb_id
== RT_TABLE_LOCAL
)
2220 seq_puts(seq
, "Local:\n");
2221 else if (tb
->tb_id
== RT_TABLE_MAIN
)
2222 seq_puts(seq
, "Main:\n");
2224 seq_printf(seq
, "Id %d:\n", tb
->tb_id
);
2228 static int fib_triestat_seq_show(struct seq_file
*seq
, void *v
)
2230 struct net
*net
= (struct net
*)seq
->private;
2234 "Basic info: size of leaf:"
2235 " %Zd bytes, size of tnode: %Zd bytes.\n",
2236 sizeof(struct leaf
), sizeof(struct tnode
));
2238 for (h
= 0; h
< FIB_TABLE_HASHSZ
; h
++) {
2239 struct hlist_head
*head
= &net
->ipv4
.fib_table_hash
[h
];
2240 struct hlist_node
*node
;
2241 struct fib_table
*tb
;
2243 hlist_for_each_entry_rcu(tb
, node
, head
, tb_hlist
) {
2244 struct trie
*t
= (struct trie
*) tb
->tb_data
;
2245 struct trie_stat stat
;
2250 fib_table_print(seq
, tb
);
2252 trie_collect_stats(t
, &stat
);
2253 trie_show_stats(seq
, &stat
);
2254 #ifdef CONFIG_IP_FIB_TRIE_STATS
2255 trie_show_usage(seq
, &t
->stats
);
2263 static int fib_triestat_seq_open(struct inode
*inode
, struct file
*file
)
2265 return single_open_net(inode
, file
, fib_triestat_seq_show
);
2268 static const struct file_operations fib_triestat_fops
= {
2269 .owner
= THIS_MODULE
,
2270 .open
= fib_triestat_seq_open
,
2272 .llseek
= seq_lseek
,
2273 .release
= single_release_net
,
2276 static struct node
*fib_trie_get_idx(struct seq_file
*seq
, loff_t pos
)
2278 struct fib_trie_iter
*iter
= seq
->private;
2279 struct net
*net
= seq_file_net(seq
);
2283 for (h
= 0; h
< FIB_TABLE_HASHSZ
; h
++) {
2284 struct hlist_head
*head
= &net
->ipv4
.fib_table_hash
[h
];
2285 struct hlist_node
*node
;
2286 struct fib_table
*tb
;
2288 hlist_for_each_entry_rcu(tb
, node
, head
, tb_hlist
) {
2291 for (n
= fib_trie_get_first(iter
,
2292 (struct trie
*) tb
->tb_data
);
2293 n
; n
= fib_trie_get_next(iter
))
2304 static void *fib_trie_seq_start(struct seq_file
*seq
, loff_t
*pos
)
2308 return fib_trie_get_idx(seq
, *pos
);
2311 static void *fib_trie_seq_next(struct seq_file
*seq
, void *v
, loff_t
*pos
)
2313 struct fib_trie_iter
*iter
= seq
->private;
2314 struct net
*net
= seq_file_net(seq
);
2315 struct fib_table
*tb
= iter
->tb
;
2316 struct hlist_node
*tb_node
;
2321 /* next node in same table */
2322 n
= fib_trie_get_next(iter
);
2326 /* walk rest of this hash chain */
2327 h
= tb
->tb_id
& (FIB_TABLE_HASHSZ
- 1);
2328 while ( (tb_node
= rcu_dereference(tb
->tb_hlist
.next
)) ) {
2329 tb
= hlist_entry(tb_node
, struct fib_table
, tb_hlist
);
2330 n
= fib_trie_get_first(iter
, (struct trie
*) tb
->tb_data
);
2335 /* new hash chain */
2336 while (++h
< FIB_TABLE_HASHSZ
) {
2337 struct hlist_head
*head
= &net
->ipv4
.fib_table_hash
[h
];
2338 hlist_for_each_entry_rcu(tb
, tb_node
, head
, tb_hlist
) {
2339 n
= fib_trie_get_first(iter
, (struct trie
*) tb
->tb_data
);
2351 static void fib_trie_seq_stop(struct seq_file
*seq
, void *v
)
2357 static void seq_indent(struct seq_file
*seq
, int n
)
2359 while (n
-- > 0) seq_puts(seq
, " ");
2362 static inline const char *rtn_scope(char *buf
, size_t len
, enum rt_scope_t s
)
2365 case RT_SCOPE_UNIVERSE
: return "universe";
2366 case RT_SCOPE_SITE
: return "site";
2367 case RT_SCOPE_LINK
: return "link";
2368 case RT_SCOPE_HOST
: return "host";
2369 case RT_SCOPE_NOWHERE
: return "nowhere";
2371 snprintf(buf
, len
, "scope=%d", s
);
2376 static const char *const rtn_type_names
[__RTN_MAX
] = {
2377 [RTN_UNSPEC
] = "UNSPEC",
2378 [RTN_UNICAST
] = "UNICAST",
2379 [RTN_LOCAL
] = "LOCAL",
2380 [RTN_BROADCAST
] = "BROADCAST",
2381 [RTN_ANYCAST
] = "ANYCAST",
2382 [RTN_MULTICAST
] = "MULTICAST",
2383 [RTN_BLACKHOLE
] = "BLACKHOLE",
2384 [RTN_UNREACHABLE
] = "UNREACHABLE",
2385 [RTN_PROHIBIT
] = "PROHIBIT",
2386 [RTN_THROW
] = "THROW",
2388 [RTN_XRESOLVE
] = "XRESOLVE",
2391 static inline const char *rtn_type(char *buf
, size_t len
, unsigned t
)
2393 if (t
< __RTN_MAX
&& rtn_type_names
[t
])
2394 return rtn_type_names
[t
];
2395 snprintf(buf
, len
, "type %u", t
);
2399 /* Pretty print the trie */
2400 static int fib_trie_seq_show(struct seq_file
*seq
, void *v
)
2402 const struct fib_trie_iter
*iter
= seq
->private;
2405 if (!node_parent_rcu(n
))
2406 fib_table_print(seq
, iter
->tb
);
2409 struct tnode
*tn
= (struct tnode
*) n
;
2410 __be32 prf
= htonl(mask_pfx(tn
->key
, tn
->pos
));
2412 seq_indent(seq
, iter
->depth
-1);
2413 seq_printf(seq
, " +-- %pI4/%d %d %d %d\n",
2414 &prf
, tn
->pos
, tn
->bits
, tn
->full_children
,
2415 tn
->empty_children
);
2418 struct leaf
*l
= (struct leaf
*) n
;
2419 struct leaf_info
*li
;
2420 struct hlist_node
*node
;
2421 __be32 val
= htonl(l
->key
);
2423 seq_indent(seq
, iter
->depth
);
2424 seq_printf(seq
, " |-- %pI4\n", &val
);
2426 hlist_for_each_entry_rcu(li
, node
, &l
->list
, hlist
) {
2427 struct fib_alias
*fa
;
2429 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
2430 char buf1
[32], buf2
[32];
2432 seq_indent(seq
, iter
->depth
+1);
2433 seq_printf(seq
, " /%d %s %s", li
->plen
,
2434 rtn_scope(buf1
, sizeof(buf1
),
2436 rtn_type(buf2
, sizeof(buf2
),
2439 seq_printf(seq
, " tos=%d", fa
->fa_tos
);
2440 seq_putc(seq
, '\n');
2448 static const struct seq_operations fib_trie_seq_ops
= {
2449 .start
= fib_trie_seq_start
,
2450 .next
= fib_trie_seq_next
,
2451 .stop
= fib_trie_seq_stop
,
2452 .show
= fib_trie_seq_show
,
2455 static int fib_trie_seq_open(struct inode
*inode
, struct file
*file
)
2457 return seq_open_net(inode
, file
, &fib_trie_seq_ops
,
2458 sizeof(struct fib_trie_iter
));
2461 static const struct file_operations fib_trie_fops
= {
2462 .owner
= THIS_MODULE
,
2463 .open
= fib_trie_seq_open
,
2465 .llseek
= seq_lseek
,
2466 .release
= seq_release_net
,
2469 struct fib_route_iter
{
2470 struct seq_net_private p
;
2471 struct trie
*main_trie
;
2476 static struct leaf
*fib_route_get_idx(struct fib_route_iter
*iter
, loff_t pos
)
2478 struct leaf
*l
= NULL
;
2479 struct trie
*t
= iter
->main_trie
;
2481 /* use cache location of last found key */
2482 if (iter
->pos
> 0 && pos
>= iter
->pos
&& (l
= fib_find_node(t
, iter
->key
)))
2486 l
= trie_firstleaf(t
);
2489 while (l
&& pos
-- > 0) {
2491 l
= trie_nextleaf(l
);
2495 iter
->key
= pos
; /* remember it */
2497 iter
->pos
= 0; /* forget it */
2502 static void *fib_route_seq_start(struct seq_file
*seq
, loff_t
*pos
)
2505 struct fib_route_iter
*iter
= seq
->private;
2506 struct fib_table
*tb
;
2509 tb
= fib_get_table(seq_file_net(seq
), RT_TABLE_MAIN
);
2513 iter
->main_trie
= (struct trie
*) tb
->tb_data
;
2515 return SEQ_START_TOKEN
;
2517 return fib_route_get_idx(iter
, *pos
- 1);
2520 static void *fib_route_seq_next(struct seq_file
*seq
, void *v
, loff_t
*pos
)
2522 struct fib_route_iter
*iter
= seq
->private;
2526 if (v
== SEQ_START_TOKEN
) {
2528 l
= trie_firstleaf(iter
->main_trie
);
2531 l
= trie_nextleaf(l
);
2541 static void fib_route_seq_stop(struct seq_file
*seq
, void *v
)
2547 static unsigned fib_flag_trans(int type
, __be32 mask
, const struct fib_info
*fi
)
2549 static unsigned type2flags
[RTN_MAX
+ 1] = {
2550 [7] = RTF_REJECT
, [8] = RTF_REJECT
,
2552 unsigned flags
= type2flags
[type
];
2554 if (fi
&& fi
->fib_nh
->nh_gw
)
2555 flags
|= RTF_GATEWAY
;
2556 if (mask
== htonl(0xFFFFFFFF))
2563 * This outputs /proc/net/route.
2564 * The format of the file is not supposed to be changed
2565 * and needs to be same as fib_hash output to avoid breaking
2568 static int fib_route_seq_show(struct seq_file
*seq
, void *v
)
2571 struct leaf_info
*li
;
2572 struct hlist_node
*node
;
2574 if (v
== SEQ_START_TOKEN
) {
2575 seq_printf(seq
, "%-127s\n", "Iface\tDestination\tGateway "
2576 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2581 hlist_for_each_entry_rcu(li
, node
, &l
->list
, hlist
) {
2582 struct fib_alias
*fa
;
2583 __be32 mask
, prefix
;
2585 mask
= inet_make_mask(li
->plen
);
2586 prefix
= htonl(l
->key
);
2588 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
2589 const struct fib_info
*fi
= fa
->fa_info
;
2590 unsigned flags
= fib_flag_trans(fa
->fa_type
, mask
, fi
);
2593 if (fa
->fa_type
== RTN_BROADCAST
2594 || fa
->fa_type
== RTN_MULTICAST
)
2599 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2600 "%d\t%08X\t%d\t%u\t%u%n",
2601 fi
->fib_dev
? fi
->fib_dev
->name
: "*",
2603 fi
->fib_nh
->nh_gw
, flags
, 0, 0,
2607 fi
->fib_advmss
+ 40 : 0),
2609 fi
->fib_rtt
>> 3, &len
);
2612 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2613 "%d\t%08X\t%d\t%u\t%u%n",
2614 prefix
, 0, flags
, 0, 0, 0,
2615 mask
, 0, 0, 0, &len
);
2617 seq_printf(seq
, "%*s\n", 127 - len
, "");
2624 static const struct seq_operations fib_route_seq_ops
= {
2625 .start
= fib_route_seq_start
,
2626 .next
= fib_route_seq_next
,
2627 .stop
= fib_route_seq_stop
,
2628 .show
= fib_route_seq_show
,
2631 static int fib_route_seq_open(struct inode
*inode
, struct file
*file
)
2633 return seq_open_net(inode
, file
, &fib_route_seq_ops
,
2634 sizeof(struct fib_route_iter
));
2637 static const struct file_operations fib_route_fops
= {
2638 .owner
= THIS_MODULE
,
2639 .open
= fib_route_seq_open
,
2641 .llseek
= seq_lseek
,
2642 .release
= seq_release_net
,
2645 int __net_init
fib_proc_init(struct net
*net
)
2647 if (!proc_net_fops_create(net
, "fib_trie", S_IRUGO
, &fib_trie_fops
))
2650 if (!proc_net_fops_create(net
, "fib_triestat", S_IRUGO
,
2651 &fib_triestat_fops
))
2654 if (!proc_net_fops_create(net
, "route", S_IRUGO
, &fib_route_fops
))
2660 proc_net_remove(net
, "fib_triestat");
2662 proc_net_remove(net
, "fib_trie");
2667 void __net_exit
fib_proc_exit(struct net
*net
)
2669 proc_net_remove(net
, "fib_trie");
2670 proc_net_remove(net
, "fib_triestat");
2671 proc_net_remove(net
, "route");
2674 #endif /* CONFIG_PROC_FS */