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.csc.kth.se/~snilsson/software/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 rt_trie_node __rcu
*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
];
154 struct rt_trie_node __rcu
*trie
;
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 rt_trie_node
*n
);
161 static void tnode_put_child_reorg(struct tnode
*tn
, int i
, struct rt_trie_node
*n
,
163 static struct rt_trie_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
;
181 * caller must hold RTNL
183 static inline struct tnode
*node_parent(const struct rt_trie_node
*node
)
185 unsigned long parent
;
187 parent
= rcu_dereference_index_check(node
->parent
, lockdep_rtnl_is_held());
189 return (struct tnode
*)(parent
& ~NODE_TYPE_MASK
);
193 * caller must hold RCU read lock or RTNL
195 static inline struct tnode
*node_parent_rcu(const struct rt_trie_node
*node
)
197 unsigned long parent
;
199 parent
= rcu_dereference_index_check(node
->parent
, rcu_read_lock_held() ||
200 lockdep_rtnl_is_held());
202 return (struct tnode
*)(parent
& ~NODE_TYPE_MASK
);
205 /* Same as rcu_assign_pointer
206 * but that macro() assumes that value is a pointer.
208 static inline void node_set_parent(struct rt_trie_node
*node
, struct tnode
*ptr
)
211 node
->parent
= (unsigned long)ptr
| NODE_TYPE(node
);
215 * caller must hold RTNL
217 static inline struct rt_trie_node
*tnode_get_child(const struct tnode
*tn
, unsigned int i
)
219 BUG_ON(i
>= 1U << tn
->bits
);
221 return rtnl_dereference(tn
->child
[i
]);
225 * caller must hold RCU read lock or RTNL
227 static inline struct rt_trie_node
*tnode_get_child_rcu(const struct tnode
*tn
, unsigned int i
)
229 BUG_ON(i
>= 1U << tn
->bits
);
231 return rcu_dereference_rtnl(tn
->child
[i
]);
234 static inline int tnode_child_length(const struct tnode
*tn
)
236 return 1 << tn
->bits
;
239 static inline t_key
mask_pfx(t_key k
, unsigned int l
)
241 return (l
== 0) ? 0 : k
>> (KEYLENGTH
-l
) << (KEYLENGTH
-l
);
244 static inline t_key
tkey_extract_bits(t_key a
, unsigned int offset
, unsigned int bits
)
246 if (offset
< KEYLENGTH
)
247 return ((t_key
)(a
<< offset
)) >> (KEYLENGTH
- bits
);
252 static inline int tkey_equals(t_key a
, t_key b
)
257 static inline int tkey_sub_equals(t_key a
, int offset
, int bits
, t_key b
)
259 if (bits
== 0 || offset
>= KEYLENGTH
)
261 bits
= bits
> KEYLENGTH
? KEYLENGTH
: bits
;
262 return ((a
^ b
) << offset
) >> (KEYLENGTH
- bits
) == 0;
265 static inline int tkey_mismatch(t_key a
, int offset
, t_key b
)
272 while ((diff
<< i
) >> (KEYLENGTH
-1) == 0)
278 To understand this stuff, an understanding of keys and all their bits is
279 necessary. Every node in the trie has a key associated with it, but not
280 all of the bits in that key are significant.
282 Consider a node 'n' and its parent 'tp'.
284 If n is a leaf, every bit in its key is significant. Its presence is
285 necessitated by path compression, since during a tree traversal (when
286 searching for a leaf - unless we are doing an insertion) we will completely
287 ignore all skipped bits we encounter. Thus we need to verify, at the end of
288 a potentially successful search, that we have indeed been walking the
291 Note that we can never "miss" the correct key in the tree if present by
292 following the wrong path. Path compression ensures that segments of the key
293 that are the same for all keys with a given prefix are skipped, but the
294 skipped part *is* identical for each node in the subtrie below the skipped
295 bit! trie_insert() in this implementation takes care of that - note the
296 call to tkey_sub_equals() in trie_insert().
298 if n is an internal node - a 'tnode' here, the various parts of its key
299 have many different meanings.
302 _________________________________________________________________
303 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
304 -----------------------------------------------------------------
305 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
307 _________________________________________________________________
308 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
309 -----------------------------------------------------------------
310 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
317 First, let's just ignore the bits that come before the parent tp, that is
318 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
319 not use them for anything.
321 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
322 index into the parent's child array. That is, they will be used to find
323 'n' among tp's children.
325 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
328 All the bits we have seen so far are significant to the node n. The rest
329 of the bits are really not needed or indeed known in n->key.
331 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
332 n's child array, and will of course be different for each child.
335 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
340 static inline void check_tnode(const struct tnode
*tn
)
342 WARN_ON(tn
&& tn
->pos
+tn
->bits
> 32);
345 static const int halve_threshold
= 25;
346 static const int inflate_threshold
= 50;
347 static const int halve_threshold_root
= 15;
348 static const int inflate_threshold_root
= 30;
350 static void __alias_free_mem(struct rcu_head
*head
)
352 struct fib_alias
*fa
= container_of(head
, struct fib_alias
, rcu
);
353 kmem_cache_free(fn_alias_kmem
, fa
);
356 static inline void alias_free_mem_rcu(struct fib_alias
*fa
)
358 call_rcu(&fa
->rcu
, __alias_free_mem
);
361 static void __leaf_free_rcu(struct rcu_head
*head
)
363 struct leaf
*l
= container_of(head
, struct leaf
, rcu
);
364 kmem_cache_free(trie_leaf_kmem
, l
);
367 static inline void free_leaf(struct leaf
*l
)
369 call_rcu_bh(&l
->rcu
, __leaf_free_rcu
);
372 static void __leaf_info_free_rcu(struct rcu_head
*head
)
374 kfree(container_of(head
, struct leaf_info
, rcu
));
377 static inline void free_leaf_info(struct leaf_info
*leaf
)
379 call_rcu(&leaf
->rcu
, __leaf_info_free_rcu
);
382 static struct tnode
*tnode_alloc(size_t size
)
384 if (size
<= PAGE_SIZE
)
385 return kzalloc(size
, GFP_KERNEL
);
387 return vzalloc(size
);
390 static void __tnode_vfree(struct work_struct
*arg
)
392 struct tnode
*tn
= container_of(arg
, struct tnode
, work
);
396 static void __tnode_free_rcu(struct rcu_head
*head
)
398 struct tnode
*tn
= container_of(head
, struct tnode
, rcu
);
399 size_t size
= sizeof(struct tnode
) +
400 (sizeof(struct rt_trie_node
*) << tn
->bits
);
402 if (size
<= PAGE_SIZE
)
405 INIT_WORK(&tn
->work
, __tnode_vfree
);
406 schedule_work(&tn
->work
);
410 static inline void tnode_free(struct tnode
*tn
)
413 free_leaf((struct leaf
*) tn
);
415 call_rcu(&tn
->rcu
, __tnode_free_rcu
);
418 static void tnode_free_safe(struct tnode
*tn
)
421 tn
->tnode_free
= tnode_free_head
;
422 tnode_free_head
= tn
;
423 tnode_free_size
+= sizeof(struct tnode
) +
424 (sizeof(struct rt_trie_node
*) << tn
->bits
);
427 static void tnode_free_flush(void)
431 while ((tn
= tnode_free_head
)) {
432 tnode_free_head
= tn
->tnode_free
;
433 tn
->tnode_free
= NULL
;
437 if (tnode_free_size
>= PAGE_SIZE
* sync_pages
) {
443 static struct leaf
*leaf_new(void)
445 struct leaf
*l
= kmem_cache_alloc(trie_leaf_kmem
, GFP_KERNEL
);
448 INIT_HLIST_HEAD(&l
->list
);
453 static struct leaf_info
*leaf_info_new(int plen
)
455 struct leaf_info
*li
= kmalloc(sizeof(struct leaf_info
), GFP_KERNEL
);
458 INIT_LIST_HEAD(&li
->falh
);
463 static struct tnode
*tnode_new(t_key key
, int pos
, int bits
)
465 size_t sz
= sizeof(struct tnode
) + (sizeof(struct rt_trie_node
*) << bits
);
466 struct tnode
*tn
= tnode_alloc(sz
);
469 tn
->parent
= T_TNODE
;
473 tn
->full_children
= 0;
474 tn
->empty_children
= 1<<bits
;
477 pr_debug("AT %p s=%zu %zu\n", tn
, sizeof(struct tnode
),
478 sizeof(struct rt_trie_node
) << bits
);
483 * Check whether a tnode 'n' is "full", i.e. it is an internal node
484 * and no bits are skipped. See discussion in dyntree paper p. 6
487 static inline int tnode_full(const struct tnode
*tn
, const struct rt_trie_node
*n
)
489 if (n
== NULL
|| IS_LEAF(n
))
492 return ((struct tnode
*) n
)->pos
== tn
->pos
+ tn
->bits
;
495 static inline void put_child(struct trie
*t
, struct tnode
*tn
, int i
,
496 struct rt_trie_node
*n
)
498 tnode_put_child_reorg(tn
, i
, n
, -1);
502 * Add a child at position i overwriting the old value.
503 * Update the value of full_children and empty_children.
506 static void tnode_put_child_reorg(struct tnode
*tn
, int i
, struct rt_trie_node
*n
,
509 struct rt_trie_node
*chi
= rtnl_dereference(tn
->child
[i
]);
512 BUG_ON(i
>= 1<<tn
->bits
);
514 /* update emptyChildren */
515 if (n
== NULL
&& chi
!= NULL
)
516 tn
->empty_children
++;
517 else if (n
!= NULL
&& chi
== NULL
)
518 tn
->empty_children
--;
520 /* update fullChildren */
522 wasfull
= tnode_full(tn
, chi
);
524 isfull
= tnode_full(tn
, n
);
525 if (wasfull
&& !isfull
)
527 else if (!wasfull
&& isfull
)
531 node_set_parent(n
, tn
);
533 rcu_assign_pointer(tn
->child
[i
], n
);
537 static struct rt_trie_node
*resize(struct trie
*t
, struct tnode
*tn
)
540 struct tnode
*old_tn
;
541 int inflate_threshold_use
;
542 int halve_threshold_use
;
548 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
549 tn
, inflate_threshold
, halve_threshold
);
552 if (tn
->empty_children
== tnode_child_length(tn
)) {
557 if (tn
->empty_children
== tnode_child_length(tn
) - 1)
560 * Double as long as the resulting node has a number of
561 * nonempty nodes that are above the threshold.
565 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
566 * the Helsinki University of Technology and Matti Tikkanen of Nokia
567 * Telecommunications, page 6:
568 * "A node is doubled if the ratio of non-empty children to all
569 * children in the *doubled* node is at least 'high'."
571 * 'high' in this instance is the variable 'inflate_threshold'. It
572 * is expressed as a percentage, so we multiply it with
573 * tnode_child_length() and instead of multiplying by 2 (since the
574 * child array will be doubled by inflate()) and multiplying
575 * the left-hand side by 100 (to handle the percentage thing) we
576 * multiply the left-hand side by 50.
578 * The left-hand side may look a bit weird: tnode_child_length(tn)
579 * - tn->empty_children is of course the number of non-null children
580 * in the current node. tn->full_children is the number of "full"
581 * children, that is non-null tnodes with a skip value of 0.
582 * All of those will be doubled in the resulting inflated tnode, so
583 * we just count them one extra time here.
585 * A clearer way to write this would be:
587 * to_be_doubled = tn->full_children;
588 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
591 * new_child_length = tnode_child_length(tn) * 2;
593 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
595 * if (new_fill_factor >= inflate_threshold)
597 * ...and so on, tho it would mess up the while () loop.
600 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
604 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
605 * inflate_threshold * new_child_length
607 * expand not_to_be_doubled and to_be_doubled, and shorten:
608 * 100 * (tnode_child_length(tn) - tn->empty_children +
609 * tn->full_children) >= inflate_threshold * new_child_length
611 * expand new_child_length:
612 * 100 * (tnode_child_length(tn) - tn->empty_children +
613 * tn->full_children) >=
614 * inflate_threshold * tnode_child_length(tn) * 2
617 * 50 * (tn->full_children + tnode_child_length(tn) -
618 * tn->empty_children) >= inflate_threshold *
619 * tnode_child_length(tn)
625 /* Keep root node larger */
627 if (!node_parent((struct rt_trie_node
*)tn
)) {
628 inflate_threshold_use
= inflate_threshold_root
;
629 halve_threshold_use
= halve_threshold_root
;
631 inflate_threshold_use
= inflate_threshold
;
632 halve_threshold_use
= halve_threshold
;
636 while ((tn
->full_children
> 0 && max_work
-- &&
637 50 * (tn
->full_children
+ tnode_child_length(tn
)
638 - tn
->empty_children
)
639 >= inflate_threshold_use
* tnode_child_length(tn
))) {
646 #ifdef CONFIG_IP_FIB_TRIE_STATS
647 t
->stats
.resize_node_skipped
++;
655 /* Return if at least one inflate is run */
656 if (max_work
!= MAX_WORK
)
657 return (struct rt_trie_node
*) tn
;
660 * Halve as long as the number of empty children in this
661 * node is above threshold.
665 while (tn
->bits
> 1 && max_work
-- &&
666 100 * (tnode_child_length(tn
) - tn
->empty_children
) <
667 halve_threshold_use
* tnode_child_length(tn
)) {
673 #ifdef CONFIG_IP_FIB_TRIE_STATS
674 t
->stats
.resize_node_skipped
++;
681 /* Only one child remains */
682 if (tn
->empty_children
== tnode_child_length(tn
) - 1) {
684 for (i
= 0; i
< tnode_child_length(tn
); i
++) {
685 struct rt_trie_node
*n
;
687 n
= rtnl_dereference(tn
->child
[i
]);
691 /* compress one level */
693 node_set_parent(n
, NULL
);
698 return (struct rt_trie_node
*) tn
;
702 static void tnode_clean_free(struct tnode
*tn
)
705 struct tnode
*tofree
;
707 for (i
= 0; i
< tnode_child_length(tn
); i
++) {
708 tofree
= (struct tnode
*)rtnl_dereference(tn
->child
[i
]);
715 static struct tnode
*inflate(struct trie
*t
, struct tnode
*tn
)
717 struct tnode
*oldtnode
= tn
;
718 int olen
= tnode_child_length(tn
);
721 pr_debug("In inflate\n");
723 tn
= tnode_new(oldtnode
->key
, oldtnode
->pos
, oldtnode
->bits
+ 1);
726 return ERR_PTR(-ENOMEM
);
729 * Preallocate and store tnodes before the actual work so we
730 * don't get into an inconsistent state if memory allocation
731 * fails. In case of failure we return the oldnode and inflate
732 * of tnode is ignored.
735 for (i
= 0; i
< olen
; i
++) {
738 inode
= (struct tnode
*) tnode_get_child(oldtnode
, i
);
741 inode
->pos
== oldtnode
->pos
+ oldtnode
->bits
&&
743 struct tnode
*left
, *right
;
744 t_key m
= ~0U << (KEYLENGTH
- 1) >> inode
->pos
;
746 left
= tnode_new(inode
->key
&(~m
), inode
->pos
+ 1,
751 right
= tnode_new(inode
->key
|m
, inode
->pos
+ 1,
759 put_child(t
, tn
, 2*i
, (struct rt_trie_node
*) left
);
760 put_child(t
, tn
, 2*i
+1, (struct rt_trie_node
*) right
);
764 for (i
= 0; i
< olen
; i
++) {
766 struct rt_trie_node
*node
= tnode_get_child(oldtnode
, i
);
767 struct tnode
*left
, *right
;
774 /* A leaf or an internal node with skipped bits */
776 if (IS_LEAF(node
) || ((struct tnode
*) node
)->pos
>
777 tn
->pos
+ tn
->bits
- 1) {
778 if (tkey_extract_bits(node
->key
,
779 oldtnode
->pos
+ oldtnode
->bits
,
781 put_child(t
, tn
, 2*i
, node
);
783 put_child(t
, tn
, 2*i
+1, node
);
787 /* An internal node with two children */
788 inode
= (struct tnode
*) node
;
790 if (inode
->bits
== 1) {
791 put_child(t
, tn
, 2*i
, rtnl_dereference(inode
->child
[0]));
792 put_child(t
, tn
, 2*i
+1, rtnl_dereference(inode
->child
[1]));
794 tnode_free_safe(inode
);
798 /* An internal node with more than two children */
800 /* We will replace this node 'inode' with two new
801 * ones, 'left' and 'right', each with half of the
802 * original children. The two new nodes will have
803 * a position one bit further down the key and this
804 * means that the "significant" part of their keys
805 * (see the discussion near the top of this file)
806 * will differ by one bit, which will be "0" in
807 * left's key and "1" in right's key. Since we are
808 * moving the key position by one step, the bit that
809 * we are moving away from - the bit at position
810 * (inode->pos) - is the one that will differ between
811 * left and right. So... we synthesize that bit in the
813 * The mask 'm' below will be a single "one" bit at
814 * the position (inode->pos)
817 /* Use the old key, but set the new significant
821 left
= (struct tnode
*) tnode_get_child(tn
, 2*i
);
822 put_child(t
, tn
, 2*i
, NULL
);
826 right
= (struct tnode
*) tnode_get_child(tn
, 2*i
+1);
827 put_child(t
, tn
, 2*i
+1, NULL
);
831 size
= tnode_child_length(left
);
832 for (j
= 0; j
< size
; j
++) {
833 put_child(t
, left
, j
, rtnl_dereference(inode
->child
[j
]));
834 put_child(t
, right
, j
, rtnl_dereference(inode
->child
[j
+ size
]));
836 put_child(t
, tn
, 2*i
, resize(t
, left
));
837 put_child(t
, tn
, 2*i
+1, resize(t
, right
));
839 tnode_free_safe(inode
);
841 tnode_free_safe(oldtnode
);
844 tnode_clean_free(tn
);
845 return ERR_PTR(-ENOMEM
);
848 static struct tnode
*halve(struct trie
*t
, struct tnode
*tn
)
850 struct tnode
*oldtnode
= tn
;
851 struct rt_trie_node
*left
, *right
;
853 int olen
= tnode_child_length(tn
);
855 pr_debug("In halve\n");
857 tn
= tnode_new(oldtnode
->key
, oldtnode
->pos
, oldtnode
->bits
- 1);
860 return ERR_PTR(-ENOMEM
);
863 * Preallocate and store tnodes before the actual work so we
864 * don't get into an inconsistent state if memory allocation
865 * fails. In case of failure we return the oldnode and halve
866 * of tnode is ignored.
869 for (i
= 0; i
< olen
; i
+= 2) {
870 left
= tnode_get_child(oldtnode
, i
);
871 right
= tnode_get_child(oldtnode
, i
+1);
873 /* Two nonempty children */
877 newn
= tnode_new(left
->key
, tn
->pos
+ tn
->bits
, 1);
882 put_child(t
, tn
, i
/2, (struct rt_trie_node
*)newn
);
887 for (i
= 0; i
< olen
; i
+= 2) {
888 struct tnode
*newBinNode
;
890 left
= tnode_get_child(oldtnode
, i
);
891 right
= tnode_get_child(oldtnode
, i
+1);
893 /* At least one of the children is empty */
895 if (right
== NULL
) /* Both are empty */
897 put_child(t
, tn
, i
/2, right
);
902 put_child(t
, tn
, i
/2, left
);
906 /* Two nonempty children */
907 newBinNode
= (struct tnode
*) tnode_get_child(tn
, i
/2);
908 put_child(t
, tn
, i
/2, NULL
);
909 put_child(t
, newBinNode
, 0, left
);
910 put_child(t
, newBinNode
, 1, right
);
911 put_child(t
, tn
, i
/2, resize(t
, newBinNode
));
913 tnode_free_safe(oldtnode
);
916 tnode_clean_free(tn
);
917 return ERR_PTR(-ENOMEM
);
920 /* readside must use rcu_read_lock currently dump routines
921 via get_fa_head and dump */
923 static struct leaf_info
*find_leaf_info(struct leaf
*l
, int plen
)
925 struct hlist_head
*head
= &l
->list
;
926 struct hlist_node
*node
;
927 struct leaf_info
*li
;
929 hlist_for_each_entry_rcu(li
, node
, head
, hlist
)
930 if (li
->plen
== plen
)
936 static inline struct list_head
*get_fa_head(struct leaf
*l
, int plen
)
938 struct leaf_info
*li
= find_leaf_info(l
, plen
);
946 static void insert_leaf_info(struct hlist_head
*head
, struct leaf_info
*new)
948 struct leaf_info
*li
= NULL
, *last
= NULL
;
949 struct hlist_node
*node
;
951 if (hlist_empty(head
)) {
952 hlist_add_head_rcu(&new->hlist
, head
);
954 hlist_for_each_entry(li
, node
, head
, hlist
) {
955 if (new->plen
> li
->plen
)
961 hlist_add_after_rcu(&last
->hlist
, &new->hlist
);
963 hlist_add_before_rcu(&new->hlist
, &li
->hlist
);
967 /* rcu_read_lock needs to be hold by caller from readside */
970 fib_find_node(struct trie
*t
, u32 key
)
974 struct rt_trie_node
*n
;
977 n
= rcu_dereference_rtnl(t
->trie
);
979 while (n
!= NULL
&& NODE_TYPE(n
) == T_TNODE
) {
980 tn
= (struct tnode
*) n
;
984 if (tkey_sub_equals(tn
->key
, pos
, tn
->pos
-pos
, key
)) {
985 pos
= tn
->pos
+ tn
->bits
;
986 n
= tnode_get_child_rcu(tn
,
987 tkey_extract_bits(key
,
993 /* Case we have found a leaf. Compare prefixes */
995 if (n
!= NULL
&& IS_LEAF(n
) && tkey_equals(key
, n
->key
))
996 return (struct leaf
*)n
;
1001 static void trie_rebalance(struct trie
*t
, struct tnode
*tn
)
1009 while (tn
!= NULL
&& (tp
= node_parent((struct rt_trie_node
*)tn
)) != NULL
) {
1010 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1011 wasfull
= tnode_full(tp
, tnode_get_child(tp
, cindex
));
1012 tn
= (struct tnode
*) resize(t
, (struct tnode
*)tn
);
1014 tnode_put_child_reorg((struct tnode
*)tp
, cindex
,
1015 (struct rt_trie_node
*)tn
, wasfull
);
1017 tp
= node_parent((struct rt_trie_node
*) tn
);
1019 rcu_assign_pointer(t
->trie
, (struct rt_trie_node
*)tn
);
1027 /* Handle last (top) tnode */
1029 tn
= (struct tnode
*)resize(t
, (struct tnode
*)tn
);
1031 rcu_assign_pointer(t
->trie
, (struct rt_trie_node
*)tn
);
1035 /* only used from updater-side */
1037 static struct list_head
*fib_insert_node(struct trie
*t
, u32 key
, int plen
)
1040 struct tnode
*tp
= NULL
, *tn
= NULL
;
1041 struct rt_trie_node
*n
;
1044 struct list_head
*fa_head
= NULL
;
1045 struct leaf_info
*li
;
1049 n
= rtnl_dereference(t
->trie
);
1051 /* If we point to NULL, stop. Either the tree is empty and we should
1052 * just put a new leaf in if, or we have reached an empty child slot,
1053 * and we should just put our new leaf in that.
1054 * If we point to a T_TNODE, check if it matches our key. Note that
1055 * a T_TNODE might be skipping any number of bits - its 'pos' need
1056 * not be the parent's 'pos'+'bits'!
1058 * If it does match the current key, get pos/bits from it, extract
1059 * the index from our key, push the T_TNODE and walk the tree.
1061 * If it doesn't, we have to replace it with a new T_TNODE.
1063 * If we point to a T_LEAF, it might or might not have the same key
1064 * as we do. If it does, just change the value, update the T_LEAF's
1065 * value, and return it.
1066 * If it doesn't, we need to replace it with a T_TNODE.
1069 while (n
!= NULL
&& NODE_TYPE(n
) == T_TNODE
) {
1070 tn
= (struct tnode
*) n
;
1074 if (tkey_sub_equals(tn
->key
, pos
, tn
->pos
-pos
, key
)) {
1076 pos
= tn
->pos
+ tn
->bits
;
1077 n
= tnode_get_child(tn
,
1078 tkey_extract_bits(key
,
1082 BUG_ON(n
&& node_parent(n
) != tn
);
1088 * n ----> NULL, LEAF or TNODE
1090 * tp is n's (parent) ----> NULL or TNODE
1093 BUG_ON(tp
&& IS_LEAF(tp
));
1095 /* Case 1: n is a leaf. Compare prefixes */
1097 if (n
!= NULL
&& IS_LEAF(n
) && tkey_equals(key
, n
->key
)) {
1098 l
= (struct leaf
*) n
;
1099 li
= leaf_info_new(plen
);
1104 fa_head
= &li
->falh
;
1105 insert_leaf_info(&l
->list
, li
);
1114 li
= leaf_info_new(plen
);
1121 fa_head
= &li
->falh
;
1122 insert_leaf_info(&l
->list
, li
);
1124 if (t
->trie
&& n
== NULL
) {
1125 /* Case 2: n is NULL, and will just insert a new leaf */
1127 node_set_parent((struct rt_trie_node
*)l
, tp
);
1129 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1130 put_child(t
, (struct tnode
*)tp
, cindex
, (struct rt_trie_node
*)l
);
1132 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1134 * Add a new tnode here
1135 * first tnode need some special handling
1139 pos
= tp
->pos
+tp
->bits
;
1144 newpos
= tkey_mismatch(key
, pos
, n
->key
);
1145 tn
= tnode_new(n
->key
, newpos
, 1);
1148 tn
= tnode_new(key
, newpos
, 1); /* First tnode */
1157 node_set_parent((struct rt_trie_node
*)tn
, tp
);
1159 missbit
= tkey_extract_bits(key
, newpos
, 1);
1160 put_child(t
, tn
, missbit
, (struct rt_trie_node
*)l
);
1161 put_child(t
, tn
, 1-missbit
, n
);
1164 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1165 put_child(t
, (struct tnode
*)tp
, cindex
,
1166 (struct rt_trie_node
*)tn
);
1168 rcu_assign_pointer(t
->trie
, (struct rt_trie_node
*)tn
);
1173 if (tp
&& tp
->pos
+ tp
->bits
> 32)
1174 pr_warning("fib_trie"
1175 " tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1176 tp
, tp
->pos
, tp
->bits
, key
, plen
);
1178 /* Rebalance the trie */
1180 trie_rebalance(t
, tp
);
1186 * Caller must hold RTNL.
1188 int fib_table_insert(struct fib_table
*tb
, struct fib_config
*cfg
)
1190 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1191 struct fib_alias
*fa
, *new_fa
;
1192 struct list_head
*fa_head
= NULL
;
1193 struct fib_info
*fi
;
1194 int plen
= cfg
->fc_dst_len
;
1195 u8 tos
= cfg
->fc_tos
;
1203 key
= ntohl(cfg
->fc_dst
);
1205 pr_debug("Insert table=%u %08x/%d\n", tb
->tb_id
, key
, plen
);
1207 mask
= ntohl(inet_make_mask(plen
));
1214 fi
= fib_create_info(cfg
);
1220 l
= fib_find_node(t
, key
);
1224 fa_head
= get_fa_head(l
, plen
);
1225 fa
= fib_find_alias(fa_head
, tos
, fi
->fib_priority
);
1228 /* Now fa, if non-NULL, points to the first fib alias
1229 * with the same keys [prefix,tos,priority], if such key already
1230 * exists or to the node before which we will insert new one.
1232 * If fa is NULL, we will need to allocate a new one and
1233 * insert to the head of f.
1235 * If f is NULL, no fib node matched the destination key
1236 * and we need to allocate a new one of those as well.
1239 if (fa
&& fa
->fa_tos
== tos
&&
1240 fa
->fa_info
->fib_priority
== fi
->fib_priority
) {
1241 struct fib_alias
*fa_first
, *fa_match
;
1244 if (cfg
->fc_nlflags
& NLM_F_EXCL
)
1248 * 1. Find exact match for type, scope, fib_info to avoid
1250 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1254 fa
= list_entry(fa
->fa_list
.prev
, struct fib_alias
, fa_list
);
1255 list_for_each_entry_continue(fa
, fa_head
, fa_list
) {
1256 if (fa
->fa_tos
!= tos
)
1258 if (fa
->fa_info
->fib_priority
!= fi
->fib_priority
)
1260 if (fa
->fa_type
== cfg
->fc_type
&&
1261 fa
->fa_info
== fi
) {
1267 if (cfg
->fc_nlflags
& NLM_F_REPLACE
) {
1268 struct fib_info
*fi_drop
;
1278 new_fa
= kmem_cache_alloc(fn_alias_kmem
, GFP_KERNEL
);
1282 fi_drop
= fa
->fa_info
;
1283 new_fa
->fa_tos
= fa
->fa_tos
;
1284 new_fa
->fa_info
= fi
;
1285 new_fa
->fa_type
= cfg
->fc_type
;
1286 state
= fa
->fa_state
;
1287 new_fa
->fa_state
= state
& ~FA_S_ACCESSED
;
1289 list_replace_rcu(&fa
->fa_list
, &new_fa
->fa_list
);
1290 alias_free_mem_rcu(fa
);
1292 fib_release_info(fi_drop
);
1293 if (state
& FA_S_ACCESSED
)
1294 rt_cache_flush(cfg
->fc_nlinfo
.nl_net
, -1);
1295 rtmsg_fib(RTM_NEWROUTE
, htonl(key
), new_fa
, plen
,
1296 tb
->tb_id
, &cfg
->fc_nlinfo
, NLM_F_REPLACE
);
1300 /* Error if we find a perfect match which
1301 * uses the same scope, type, and nexthop
1307 if (!(cfg
->fc_nlflags
& NLM_F_APPEND
))
1311 if (!(cfg
->fc_nlflags
& NLM_F_CREATE
))
1315 new_fa
= kmem_cache_alloc(fn_alias_kmem
, GFP_KERNEL
);
1319 new_fa
->fa_info
= fi
;
1320 new_fa
->fa_tos
= tos
;
1321 new_fa
->fa_type
= cfg
->fc_type
;
1322 new_fa
->fa_state
= 0;
1324 * Insert new entry to the list.
1328 fa_head
= fib_insert_node(t
, key
, plen
);
1329 if (unlikely(!fa_head
)) {
1331 goto out_free_new_fa
;
1335 list_add_tail_rcu(&new_fa
->fa_list
,
1336 (fa
? &fa
->fa_list
: fa_head
));
1338 rt_cache_flush(cfg
->fc_nlinfo
.nl_net
, -1);
1339 rtmsg_fib(RTM_NEWROUTE
, htonl(key
), new_fa
, plen
, tb
->tb_id
,
1340 &cfg
->fc_nlinfo
, 0);
1345 kmem_cache_free(fn_alias_kmem
, new_fa
);
1347 fib_release_info(fi
);
1352 /* should be called with rcu_read_lock */
1353 static int check_leaf(struct fib_table
*tb
, struct trie
*t
, struct leaf
*l
,
1354 t_key key
, const struct flowi4
*flp
,
1355 struct fib_result
*res
, int fib_flags
)
1357 struct leaf_info
*li
;
1358 struct hlist_head
*hhead
= &l
->list
;
1359 struct hlist_node
*node
;
1361 hlist_for_each_entry_rcu(li
, node
, hhead
, hlist
) {
1362 struct fib_alias
*fa
;
1363 int plen
= li
->plen
;
1364 __be32 mask
= inet_make_mask(plen
);
1366 if (l
->key
!= (key
& ntohl(mask
)))
1369 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
1370 struct fib_info
*fi
= fa
->fa_info
;
1373 if (fa
->fa_tos
&& fa
->fa_tos
!= flp
->flowi4_tos
)
1375 if (fa
->fa_info
->fib_scope
< flp
->flowi4_scope
)
1377 fib_alias_accessed(fa
);
1378 err
= fib_props
[fa
->fa_type
].error
;
1380 #ifdef CONFIG_IP_FIB_TRIE_STATS
1381 t
->stats
.semantic_match_passed
++;
1385 if (fi
->fib_flags
& RTNH_F_DEAD
)
1387 for (nhsel
= 0; nhsel
< fi
->fib_nhs
; nhsel
++) {
1388 const struct fib_nh
*nh
= &fi
->fib_nh
[nhsel
];
1390 if (nh
->nh_flags
& RTNH_F_DEAD
)
1392 if (flp
->flowi4_oif
&& flp
->flowi4_oif
!= nh
->nh_oif
)
1395 #ifdef CONFIG_IP_FIB_TRIE_STATS
1396 t
->stats
.semantic_match_passed
++;
1398 res
->prefixlen
= plen
;
1399 res
->nh_sel
= nhsel
;
1400 res
->type
= fa
->fa_type
;
1401 res
->scope
= fa
->fa_info
->fib_scope
;
1404 res
->fa_head
= &li
->falh
;
1405 if (!(fib_flags
& FIB_LOOKUP_NOREF
))
1406 atomic_inc(&res
->fi
->fib_clntref
);
1411 #ifdef CONFIG_IP_FIB_TRIE_STATS
1412 t
->stats
.semantic_match_miss
++;
1419 int fib_table_lookup(struct fib_table
*tb
, const struct flowi4
*flp
,
1420 struct fib_result
*res
, int fib_flags
)
1422 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1424 struct rt_trie_node
*n
;
1426 unsigned int pos
, bits
;
1427 t_key key
= ntohl(flp
->daddr
);
1428 unsigned int chopped_off
;
1430 unsigned int current_prefix_length
= KEYLENGTH
;
1432 t_key pref_mismatch
;
1436 n
= rcu_dereference(t
->trie
);
1440 #ifdef CONFIG_IP_FIB_TRIE_STATS
1446 ret
= check_leaf(tb
, t
, (struct leaf
*)n
, key
, flp
, res
, fib_flags
);
1450 pn
= (struct tnode
*) n
;
1458 cindex
= tkey_extract_bits(mask_pfx(key
, current_prefix_length
),
1461 n
= tnode_get_child_rcu(pn
, cindex
);
1464 #ifdef CONFIG_IP_FIB_TRIE_STATS
1465 t
->stats
.null_node_hit
++;
1471 ret
= check_leaf(tb
, t
, (struct leaf
*)n
, key
, flp
, res
, fib_flags
);
1477 cn
= (struct tnode
*)n
;
1480 * It's a tnode, and we can do some extra checks here if we
1481 * like, to avoid descending into a dead-end branch.
1482 * This tnode is in the parent's child array at index
1483 * key[p_pos..p_pos+p_bits] but potentially with some bits
1484 * chopped off, so in reality the index may be just a
1485 * subprefix, padded with zero at the end.
1486 * We can also take a look at any skipped bits in this
1487 * tnode - everything up to p_pos is supposed to be ok,
1488 * and the non-chopped bits of the index (se previous
1489 * paragraph) are also guaranteed ok, but the rest is
1490 * considered unknown.
1492 * The skipped bits are key[pos+bits..cn->pos].
1495 /* If current_prefix_length < pos+bits, we are already doing
1496 * actual prefix matching, which means everything from
1497 * pos+(bits-chopped_off) onward must be zero along some
1498 * branch of this subtree - otherwise there is *no* valid
1499 * prefix present. Here we can only check the skipped
1500 * bits. Remember, since we have already indexed into the
1501 * parent's child array, we know that the bits we chopped of
1505 /* NOTA BENE: Checking only skipped bits
1506 for the new node here */
1508 if (current_prefix_length
< pos
+bits
) {
1509 if (tkey_extract_bits(cn
->key
, current_prefix_length
,
1510 cn
->pos
- current_prefix_length
)
1516 * If chopped_off=0, the index is fully validated and we
1517 * only need to look at the skipped bits for this, the new,
1518 * tnode. What we actually want to do is to find out if
1519 * these skipped bits match our key perfectly, or if we will
1520 * have to count on finding a matching prefix further down,
1521 * because if we do, we would like to have some way of
1522 * verifying the existence of such a prefix at this point.
1525 /* The only thing we can do at this point is to verify that
1526 * any such matching prefix can indeed be a prefix to our
1527 * key, and if the bits in the node we are inspecting that
1528 * do not match our key are not ZERO, this cannot be true.
1529 * Thus, find out where there is a mismatch (before cn->pos)
1530 * and verify that all the mismatching bits are zero in the
1535 * Note: We aren't very concerned about the piece of
1536 * the key that precede pn->pos+pn->bits, since these
1537 * have already been checked. The bits after cn->pos
1538 * aren't checked since these are by definition
1539 * "unknown" at this point. Thus, what we want to see
1540 * is if we are about to enter the "prefix matching"
1541 * state, and in that case verify that the skipped
1542 * bits that will prevail throughout this subtree are
1543 * zero, as they have to be if we are to find a
1547 pref_mismatch
= mask_pfx(cn
->key
^ key
, cn
->pos
);
1550 * In short: If skipped bits in this node do not match
1551 * the search key, enter the "prefix matching"
1554 if (pref_mismatch
) {
1555 int mp
= KEYLENGTH
- fls(pref_mismatch
);
1557 if (tkey_extract_bits(cn
->key
, mp
, cn
->pos
- mp
) != 0)
1560 if (current_prefix_length
>= cn
->pos
)
1561 current_prefix_length
= mp
;
1564 pn
= (struct tnode
*)n
; /* Descend */
1571 /* As zero don't change the child key (cindex) */
1572 while ((chopped_off
<= pn
->bits
)
1573 && !(cindex
& (1<<(chopped_off
-1))))
1576 /* Decrease current_... with bits chopped off */
1577 if (current_prefix_length
> pn
->pos
+ pn
->bits
- chopped_off
)
1578 current_prefix_length
= pn
->pos
+ pn
->bits
1582 * Either we do the actual chop off according or if we have
1583 * chopped off all bits in this tnode walk up to our parent.
1586 if (chopped_off
<= pn
->bits
) {
1587 cindex
&= ~(1 << (chopped_off
-1));
1589 struct tnode
*parent
= node_parent_rcu((struct rt_trie_node
*) pn
);
1593 /* Get Child's index */
1594 cindex
= tkey_extract_bits(pn
->key
, parent
->pos
, parent
->bits
);
1598 #ifdef CONFIG_IP_FIB_TRIE_STATS
1599 t
->stats
.backtrack
++;
1612 * Remove the leaf and return parent.
1614 static void trie_leaf_remove(struct trie
*t
, struct leaf
*l
)
1616 struct tnode
*tp
= node_parent((struct rt_trie_node
*) l
);
1618 pr_debug("entering trie_leaf_remove(%p)\n", l
);
1621 t_key cindex
= tkey_extract_bits(l
->key
, tp
->pos
, tp
->bits
);
1622 put_child(t
, (struct tnode
*)tp
, cindex
, NULL
);
1623 trie_rebalance(t
, tp
);
1625 rcu_assign_pointer(t
->trie
, NULL
);
1631 * Caller must hold RTNL.
1633 int fib_table_delete(struct fib_table
*tb
, struct fib_config
*cfg
)
1635 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1637 int plen
= cfg
->fc_dst_len
;
1638 u8 tos
= cfg
->fc_tos
;
1639 struct fib_alias
*fa
, *fa_to_delete
;
1640 struct list_head
*fa_head
;
1642 struct leaf_info
*li
;
1647 key
= ntohl(cfg
->fc_dst
);
1648 mask
= ntohl(inet_make_mask(plen
));
1654 l
= fib_find_node(t
, key
);
1659 fa_head
= get_fa_head(l
, plen
);
1660 fa
= fib_find_alias(fa_head
, tos
, 0);
1665 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key
, plen
, tos
, t
);
1667 fa_to_delete
= NULL
;
1668 fa
= list_entry(fa
->fa_list
.prev
, struct fib_alias
, fa_list
);
1669 list_for_each_entry_continue(fa
, fa_head
, fa_list
) {
1670 struct fib_info
*fi
= fa
->fa_info
;
1672 if (fa
->fa_tos
!= tos
)
1675 if ((!cfg
->fc_type
|| fa
->fa_type
== cfg
->fc_type
) &&
1676 (cfg
->fc_scope
== RT_SCOPE_NOWHERE
||
1677 fa
->fa_info
->fib_scope
== cfg
->fc_scope
) &&
1678 (!cfg
->fc_prefsrc
||
1679 fi
->fib_prefsrc
== cfg
->fc_prefsrc
) &&
1680 (!cfg
->fc_protocol
||
1681 fi
->fib_protocol
== cfg
->fc_protocol
) &&
1682 fib_nh_match(cfg
, fi
) == 0) {
1692 rtmsg_fib(RTM_DELROUTE
, htonl(key
), fa
, plen
, tb
->tb_id
,
1693 &cfg
->fc_nlinfo
, 0);
1695 l
= fib_find_node(t
, key
);
1696 li
= find_leaf_info(l
, plen
);
1698 list_del_rcu(&fa
->fa_list
);
1700 if (list_empty(fa_head
)) {
1701 hlist_del_rcu(&li
->hlist
);
1705 if (hlist_empty(&l
->list
))
1706 trie_leaf_remove(t
, l
);
1708 if (fa
->fa_state
& FA_S_ACCESSED
)
1709 rt_cache_flush(cfg
->fc_nlinfo
.nl_net
, -1);
1711 fib_release_info(fa
->fa_info
);
1712 alias_free_mem_rcu(fa
);
1716 static int trie_flush_list(struct list_head
*head
)
1718 struct fib_alias
*fa
, *fa_node
;
1721 list_for_each_entry_safe(fa
, fa_node
, head
, fa_list
) {
1722 struct fib_info
*fi
= fa
->fa_info
;
1724 if (fi
&& (fi
->fib_flags
& RTNH_F_DEAD
)) {
1725 list_del_rcu(&fa
->fa_list
);
1726 fib_release_info(fa
->fa_info
);
1727 alias_free_mem_rcu(fa
);
1734 static int trie_flush_leaf(struct leaf
*l
)
1737 struct hlist_head
*lih
= &l
->list
;
1738 struct hlist_node
*node
, *tmp
;
1739 struct leaf_info
*li
= NULL
;
1741 hlist_for_each_entry_safe(li
, node
, tmp
, lih
, hlist
) {
1742 found
+= trie_flush_list(&li
->falh
);
1744 if (list_empty(&li
->falh
)) {
1745 hlist_del_rcu(&li
->hlist
);
1753 * Scan for the next right leaf starting at node p->child[idx]
1754 * Since we have back pointer, no recursion necessary.
1756 static struct leaf
*leaf_walk_rcu(struct tnode
*p
, struct rt_trie_node
*c
)
1762 idx
= tkey_extract_bits(c
->key
, p
->pos
, p
->bits
) + 1;
1766 while (idx
< 1u << p
->bits
) {
1767 c
= tnode_get_child_rcu(p
, idx
++);
1772 prefetch(rcu_dereference_rtnl(p
->child
[idx
]));
1773 return (struct leaf
*) c
;
1776 /* Rescan start scanning in new node */
1777 p
= (struct tnode
*) c
;
1781 /* Node empty, walk back up to parent */
1782 c
= (struct rt_trie_node
*) p
;
1783 } while ((p
= node_parent_rcu(c
)) != NULL
);
1785 return NULL
; /* Root of trie */
1788 static struct leaf
*trie_firstleaf(struct trie
*t
)
1790 struct tnode
*n
= (struct tnode
*)rcu_dereference_rtnl(t
->trie
);
1795 if (IS_LEAF(n
)) /* trie is just a leaf */
1796 return (struct leaf
*) n
;
1798 return leaf_walk_rcu(n
, NULL
);
1801 static struct leaf
*trie_nextleaf(struct leaf
*l
)
1803 struct rt_trie_node
*c
= (struct rt_trie_node
*) l
;
1804 struct tnode
*p
= node_parent_rcu(c
);
1807 return NULL
; /* trie with just one leaf */
1809 return leaf_walk_rcu(p
, c
);
1812 static struct leaf
*trie_leafindex(struct trie
*t
, int index
)
1814 struct leaf
*l
= trie_firstleaf(t
);
1816 while (l
&& index
-- > 0)
1817 l
= trie_nextleaf(l
);
1824 * Caller must hold RTNL.
1826 int fib_table_flush(struct fib_table
*tb
)
1828 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1829 struct leaf
*l
, *ll
= NULL
;
1832 for (l
= trie_firstleaf(t
); l
; l
= trie_nextleaf(l
)) {
1833 found
+= trie_flush_leaf(l
);
1835 if (ll
&& hlist_empty(&ll
->list
))
1836 trie_leaf_remove(t
, ll
);
1840 if (ll
&& hlist_empty(&ll
->list
))
1841 trie_leaf_remove(t
, ll
);
1843 pr_debug("trie_flush found=%d\n", found
);
1847 void fib_free_table(struct fib_table
*tb
)
1852 static int fn_trie_dump_fa(t_key key
, int plen
, struct list_head
*fah
,
1853 struct fib_table
*tb
,
1854 struct sk_buff
*skb
, struct netlink_callback
*cb
)
1857 struct fib_alias
*fa
;
1858 __be32 xkey
= htonl(key
);
1863 /* rcu_read_lock is hold by caller */
1865 list_for_each_entry_rcu(fa
, fah
, fa_list
) {
1871 if (fib_dump_info(skb
, NETLINK_CB(cb
->skb
).pid
,
1879 fa
->fa_info
, NLM_F_MULTI
) < 0) {
1889 static int fn_trie_dump_leaf(struct leaf
*l
, struct fib_table
*tb
,
1890 struct sk_buff
*skb
, struct netlink_callback
*cb
)
1892 struct leaf_info
*li
;
1893 struct hlist_node
*node
;
1899 /* rcu_read_lock is hold by caller */
1900 hlist_for_each_entry_rcu(li
, node
, &l
->list
, hlist
) {
1909 if (list_empty(&li
->falh
))
1912 if (fn_trie_dump_fa(l
->key
, li
->plen
, &li
->falh
, tb
, skb
, cb
) < 0) {
1923 int fib_table_dump(struct fib_table
*tb
, struct sk_buff
*skb
,
1924 struct netlink_callback
*cb
)
1927 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1928 t_key key
= cb
->args
[2];
1929 int count
= cb
->args
[3];
1932 /* Dump starting at last key.
1933 * Note: 0.0.0.0/0 (ie default) is first key.
1936 l
= trie_firstleaf(t
);
1938 /* Normally, continue from last key, but if that is missing
1939 * fallback to using slow rescan
1941 l
= fib_find_node(t
, key
);
1943 l
= trie_leafindex(t
, count
);
1947 cb
->args
[2] = l
->key
;
1948 if (fn_trie_dump_leaf(l
, tb
, skb
, cb
) < 0) {
1949 cb
->args
[3] = count
;
1955 l
= trie_nextleaf(l
);
1956 memset(&cb
->args
[4], 0,
1957 sizeof(cb
->args
) - 4*sizeof(cb
->args
[0]));
1959 cb
->args
[3] = count
;
1965 void __init
fib_trie_init(void)
1967 fn_alias_kmem
= kmem_cache_create("ip_fib_alias",
1968 sizeof(struct fib_alias
),
1969 0, SLAB_PANIC
, NULL
);
1971 trie_leaf_kmem
= kmem_cache_create("ip_fib_trie",
1972 max(sizeof(struct leaf
),
1973 sizeof(struct leaf_info
)),
1974 0, SLAB_PANIC
, NULL
);
1978 struct fib_table
*fib_trie_table(u32 id
)
1980 struct fib_table
*tb
;
1983 tb
= kmalloc(sizeof(struct fib_table
) + sizeof(struct trie
),
1989 tb
->tb_default
= -1;
1991 t
= (struct trie
*) tb
->tb_data
;
1992 memset(t
, 0, sizeof(*t
));
1994 if (id
== RT_TABLE_LOCAL
)
1995 pr_info("IPv4 FIB: Using LC-trie version %s\n", VERSION
);
2000 #ifdef CONFIG_PROC_FS
2001 /* Depth first Trie walk iterator */
2002 struct fib_trie_iter
{
2003 struct seq_net_private p
;
2004 struct fib_table
*tb
;
2005 struct tnode
*tnode
;
2010 static struct rt_trie_node
*fib_trie_get_next(struct fib_trie_iter
*iter
)
2012 struct tnode
*tn
= iter
->tnode
;
2013 unsigned int cindex
= iter
->index
;
2016 /* A single entry routing table */
2020 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2021 iter
->tnode
, iter
->index
, iter
->depth
);
2023 while (cindex
< (1<<tn
->bits
)) {
2024 struct rt_trie_node
*n
= tnode_get_child_rcu(tn
, cindex
);
2029 iter
->index
= cindex
+ 1;
2031 /* push down one level */
2032 iter
->tnode
= (struct tnode
*) n
;
2042 /* Current node exhausted, pop back up */
2043 p
= node_parent_rcu((struct rt_trie_node
*)tn
);
2045 cindex
= tkey_extract_bits(tn
->key
, p
->pos
, p
->bits
)+1;
2055 static struct rt_trie_node
*fib_trie_get_first(struct fib_trie_iter
*iter
,
2058 struct rt_trie_node
*n
;
2063 n
= rcu_dereference(t
->trie
);
2068 iter
->tnode
= (struct tnode
*) n
;
2080 static void trie_collect_stats(struct trie
*t
, struct trie_stat
*s
)
2082 struct rt_trie_node
*n
;
2083 struct fib_trie_iter iter
;
2085 memset(s
, 0, sizeof(*s
));
2088 for (n
= fib_trie_get_first(&iter
, t
); n
; n
= fib_trie_get_next(&iter
)) {
2090 struct leaf
*l
= (struct leaf
*)n
;
2091 struct leaf_info
*li
;
2092 struct hlist_node
*tmp
;
2095 s
->totdepth
+= iter
.depth
;
2096 if (iter
.depth
> s
->maxdepth
)
2097 s
->maxdepth
= iter
.depth
;
2099 hlist_for_each_entry_rcu(li
, tmp
, &l
->list
, hlist
)
2102 const struct tnode
*tn
= (const struct tnode
*) n
;
2106 if (tn
->bits
< MAX_STAT_DEPTH
)
2107 s
->nodesizes
[tn
->bits
]++;
2109 for (i
= 0; i
< (1<<tn
->bits
); i
++)
2118 * This outputs /proc/net/fib_triestats
2120 static void trie_show_stats(struct seq_file
*seq
, struct trie_stat
*stat
)
2122 unsigned int i
, max
, pointers
, bytes
, avdepth
;
2125 avdepth
= stat
->totdepth
*100 / stat
->leaves
;
2129 seq_printf(seq
, "\tAver depth: %u.%02d\n",
2130 avdepth
/ 100, avdepth
% 100);
2131 seq_printf(seq
, "\tMax depth: %u\n", stat
->maxdepth
);
2133 seq_printf(seq
, "\tLeaves: %u\n", stat
->leaves
);
2134 bytes
= sizeof(struct leaf
) * stat
->leaves
;
2136 seq_printf(seq
, "\tPrefixes: %u\n", stat
->prefixes
);
2137 bytes
+= sizeof(struct leaf_info
) * stat
->prefixes
;
2139 seq_printf(seq
, "\tInternal nodes: %u\n\t", stat
->tnodes
);
2140 bytes
+= sizeof(struct tnode
) * stat
->tnodes
;
2142 max
= MAX_STAT_DEPTH
;
2143 while (max
> 0 && stat
->nodesizes
[max
-1] == 0)
2147 for (i
= 1; i
<= max
; i
++)
2148 if (stat
->nodesizes
[i
] != 0) {
2149 seq_printf(seq
, " %u: %u", i
, stat
->nodesizes
[i
]);
2150 pointers
+= (1<<i
) * stat
->nodesizes
[i
];
2152 seq_putc(seq
, '\n');
2153 seq_printf(seq
, "\tPointers: %u\n", pointers
);
2155 bytes
+= sizeof(struct rt_trie_node
*) * pointers
;
2156 seq_printf(seq
, "Null ptrs: %u\n", stat
->nullpointers
);
2157 seq_printf(seq
, "Total size: %u kB\n", (bytes
+ 1023) / 1024);
2160 #ifdef CONFIG_IP_FIB_TRIE_STATS
2161 static void trie_show_usage(struct seq_file
*seq
,
2162 const struct trie_use_stats
*stats
)
2164 seq_printf(seq
, "\nCounters:\n---------\n");
2165 seq_printf(seq
, "gets = %u\n", stats
->gets
);
2166 seq_printf(seq
, "backtracks = %u\n", stats
->backtrack
);
2167 seq_printf(seq
, "semantic match passed = %u\n",
2168 stats
->semantic_match_passed
);
2169 seq_printf(seq
, "semantic match miss = %u\n",
2170 stats
->semantic_match_miss
);
2171 seq_printf(seq
, "null node hit= %u\n", stats
->null_node_hit
);
2172 seq_printf(seq
, "skipped node resize = %u\n\n",
2173 stats
->resize_node_skipped
);
2175 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2177 static void fib_table_print(struct seq_file
*seq
, struct fib_table
*tb
)
2179 if (tb
->tb_id
== RT_TABLE_LOCAL
)
2180 seq_puts(seq
, "Local:\n");
2181 else if (tb
->tb_id
== RT_TABLE_MAIN
)
2182 seq_puts(seq
, "Main:\n");
2184 seq_printf(seq
, "Id %d:\n", tb
->tb_id
);
2188 static int fib_triestat_seq_show(struct seq_file
*seq
, void *v
)
2190 struct net
*net
= (struct net
*)seq
->private;
2194 "Basic info: size of leaf:"
2195 " %Zd bytes, size of tnode: %Zd bytes.\n",
2196 sizeof(struct leaf
), sizeof(struct tnode
));
2198 for (h
= 0; h
< FIB_TABLE_HASHSZ
; h
++) {
2199 struct hlist_head
*head
= &net
->ipv4
.fib_table_hash
[h
];
2200 struct hlist_node
*node
;
2201 struct fib_table
*tb
;
2203 hlist_for_each_entry_rcu(tb
, node
, head
, tb_hlist
) {
2204 struct trie
*t
= (struct trie
*) tb
->tb_data
;
2205 struct trie_stat stat
;
2210 fib_table_print(seq
, tb
);
2212 trie_collect_stats(t
, &stat
);
2213 trie_show_stats(seq
, &stat
);
2214 #ifdef CONFIG_IP_FIB_TRIE_STATS
2215 trie_show_usage(seq
, &t
->stats
);
2223 static int fib_triestat_seq_open(struct inode
*inode
, struct file
*file
)
2225 return single_open_net(inode
, file
, fib_triestat_seq_show
);
2228 static const struct file_operations fib_triestat_fops
= {
2229 .owner
= THIS_MODULE
,
2230 .open
= fib_triestat_seq_open
,
2232 .llseek
= seq_lseek
,
2233 .release
= single_release_net
,
2236 static struct rt_trie_node
*fib_trie_get_idx(struct seq_file
*seq
, loff_t pos
)
2238 struct fib_trie_iter
*iter
= seq
->private;
2239 struct net
*net
= seq_file_net(seq
);
2243 for (h
= 0; h
< FIB_TABLE_HASHSZ
; h
++) {
2244 struct hlist_head
*head
= &net
->ipv4
.fib_table_hash
[h
];
2245 struct hlist_node
*node
;
2246 struct fib_table
*tb
;
2248 hlist_for_each_entry_rcu(tb
, node
, head
, tb_hlist
) {
2249 struct rt_trie_node
*n
;
2251 for (n
= fib_trie_get_first(iter
,
2252 (struct trie
*) tb
->tb_data
);
2253 n
; n
= fib_trie_get_next(iter
))
2264 static void *fib_trie_seq_start(struct seq_file
*seq
, loff_t
*pos
)
2268 return fib_trie_get_idx(seq
, *pos
);
2271 static void *fib_trie_seq_next(struct seq_file
*seq
, void *v
, loff_t
*pos
)
2273 struct fib_trie_iter
*iter
= seq
->private;
2274 struct net
*net
= seq_file_net(seq
);
2275 struct fib_table
*tb
= iter
->tb
;
2276 struct hlist_node
*tb_node
;
2278 struct rt_trie_node
*n
;
2281 /* next node in same table */
2282 n
= fib_trie_get_next(iter
);
2286 /* walk rest of this hash chain */
2287 h
= tb
->tb_id
& (FIB_TABLE_HASHSZ
- 1);
2288 while ((tb_node
= rcu_dereference(hlist_next_rcu(&tb
->tb_hlist
)))) {
2289 tb
= hlist_entry(tb_node
, struct fib_table
, tb_hlist
);
2290 n
= fib_trie_get_first(iter
, (struct trie
*) tb
->tb_data
);
2295 /* new hash chain */
2296 while (++h
< FIB_TABLE_HASHSZ
) {
2297 struct hlist_head
*head
= &net
->ipv4
.fib_table_hash
[h
];
2298 hlist_for_each_entry_rcu(tb
, tb_node
, head
, tb_hlist
) {
2299 n
= fib_trie_get_first(iter
, (struct trie
*) tb
->tb_data
);
2311 static void fib_trie_seq_stop(struct seq_file
*seq
, void *v
)
2317 static void seq_indent(struct seq_file
*seq
, int n
)
2323 static inline const char *rtn_scope(char *buf
, size_t len
, enum rt_scope_t s
)
2326 case RT_SCOPE_UNIVERSE
: return "universe";
2327 case RT_SCOPE_SITE
: return "site";
2328 case RT_SCOPE_LINK
: return "link";
2329 case RT_SCOPE_HOST
: return "host";
2330 case RT_SCOPE_NOWHERE
: return "nowhere";
2332 snprintf(buf
, len
, "scope=%d", s
);
2337 static const char *const rtn_type_names
[__RTN_MAX
] = {
2338 [RTN_UNSPEC
] = "UNSPEC",
2339 [RTN_UNICAST
] = "UNICAST",
2340 [RTN_LOCAL
] = "LOCAL",
2341 [RTN_BROADCAST
] = "BROADCAST",
2342 [RTN_ANYCAST
] = "ANYCAST",
2343 [RTN_MULTICAST
] = "MULTICAST",
2344 [RTN_BLACKHOLE
] = "BLACKHOLE",
2345 [RTN_UNREACHABLE
] = "UNREACHABLE",
2346 [RTN_PROHIBIT
] = "PROHIBIT",
2347 [RTN_THROW
] = "THROW",
2349 [RTN_XRESOLVE
] = "XRESOLVE",
2352 static inline const char *rtn_type(char *buf
, size_t len
, unsigned int t
)
2354 if (t
< __RTN_MAX
&& rtn_type_names
[t
])
2355 return rtn_type_names
[t
];
2356 snprintf(buf
, len
, "type %u", t
);
2360 /* Pretty print the trie */
2361 static int fib_trie_seq_show(struct seq_file
*seq
, void *v
)
2363 const struct fib_trie_iter
*iter
= seq
->private;
2364 struct rt_trie_node
*n
= v
;
2366 if (!node_parent_rcu(n
))
2367 fib_table_print(seq
, iter
->tb
);
2370 struct tnode
*tn
= (struct tnode
*) n
;
2371 __be32 prf
= htonl(mask_pfx(tn
->key
, tn
->pos
));
2373 seq_indent(seq
, iter
->depth
-1);
2374 seq_printf(seq
, " +-- %pI4/%d %d %d %d\n",
2375 &prf
, tn
->pos
, tn
->bits
, tn
->full_children
,
2376 tn
->empty_children
);
2379 struct leaf
*l
= (struct leaf
*) n
;
2380 struct leaf_info
*li
;
2381 struct hlist_node
*node
;
2382 __be32 val
= htonl(l
->key
);
2384 seq_indent(seq
, iter
->depth
);
2385 seq_printf(seq
, " |-- %pI4\n", &val
);
2387 hlist_for_each_entry_rcu(li
, node
, &l
->list
, hlist
) {
2388 struct fib_alias
*fa
;
2390 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
2391 char buf1
[32], buf2
[32];
2393 seq_indent(seq
, iter
->depth
+1);
2394 seq_printf(seq
, " /%d %s %s", li
->plen
,
2395 rtn_scope(buf1
, sizeof(buf1
),
2396 fa
->fa_info
->fib_scope
),
2397 rtn_type(buf2
, sizeof(buf2
),
2400 seq_printf(seq
, " tos=%d", fa
->fa_tos
);
2401 seq_putc(seq
, '\n');
2409 static const struct seq_operations fib_trie_seq_ops
= {
2410 .start
= fib_trie_seq_start
,
2411 .next
= fib_trie_seq_next
,
2412 .stop
= fib_trie_seq_stop
,
2413 .show
= fib_trie_seq_show
,
2416 static int fib_trie_seq_open(struct inode
*inode
, struct file
*file
)
2418 return seq_open_net(inode
, file
, &fib_trie_seq_ops
,
2419 sizeof(struct fib_trie_iter
));
2422 static const struct file_operations fib_trie_fops
= {
2423 .owner
= THIS_MODULE
,
2424 .open
= fib_trie_seq_open
,
2426 .llseek
= seq_lseek
,
2427 .release
= seq_release_net
,
2430 struct fib_route_iter
{
2431 struct seq_net_private p
;
2432 struct trie
*main_trie
;
2437 static struct leaf
*fib_route_get_idx(struct fib_route_iter
*iter
, loff_t pos
)
2439 struct leaf
*l
= NULL
;
2440 struct trie
*t
= iter
->main_trie
;
2442 /* use cache location of last found key */
2443 if (iter
->pos
> 0 && pos
>= iter
->pos
&& (l
= fib_find_node(t
, iter
->key
)))
2447 l
= trie_firstleaf(t
);
2450 while (l
&& pos
-- > 0) {
2452 l
= trie_nextleaf(l
);
2456 iter
->key
= pos
; /* remember it */
2458 iter
->pos
= 0; /* forget it */
2463 static void *fib_route_seq_start(struct seq_file
*seq
, loff_t
*pos
)
2466 struct fib_route_iter
*iter
= seq
->private;
2467 struct fib_table
*tb
;
2470 tb
= fib_get_table(seq_file_net(seq
), RT_TABLE_MAIN
);
2474 iter
->main_trie
= (struct trie
*) tb
->tb_data
;
2476 return SEQ_START_TOKEN
;
2478 return fib_route_get_idx(iter
, *pos
- 1);
2481 static void *fib_route_seq_next(struct seq_file
*seq
, void *v
, loff_t
*pos
)
2483 struct fib_route_iter
*iter
= seq
->private;
2487 if (v
== SEQ_START_TOKEN
) {
2489 l
= trie_firstleaf(iter
->main_trie
);
2492 l
= trie_nextleaf(l
);
2502 static void fib_route_seq_stop(struct seq_file
*seq
, void *v
)
2508 static unsigned int fib_flag_trans(int type
, __be32 mask
, const struct fib_info
*fi
)
2510 unsigned int flags
= 0;
2512 if (type
== RTN_UNREACHABLE
|| type
== RTN_PROHIBIT
)
2514 if (fi
&& fi
->fib_nh
->nh_gw
)
2515 flags
|= RTF_GATEWAY
;
2516 if (mask
== htonl(0xFFFFFFFF))
2523 * This outputs /proc/net/route.
2524 * The format of the file is not supposed to be changed
2525 * and needs to be same as fib_hash output to avoid breaking
2528 static int fib_route_seq_show(struct seq_file
*seq
, void *v
)
2531 struct leaf_info
*li
;
2532 struct hlist_node
*node
;
2534 if (v
== SEQ_START_TOKEN
) {
2535 seq_printf(seq
, "%-127s\n", "Iface\tDestination\tGateway "
2536 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2541 hlist_for_each_entry_rcu(li
, node
, &l
->list
, hlist
) {
2542 struct fib_alias
*fa
;
2543 __be32 mask
, prefix
;
2545 mask
= inet_make_mask(li
->plen
);
2546 prefix
= htonl(l
->key
);
2548 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
2549 const struct fib_info
*fi
= fa
->fa_info
;
2550 unsigned int flags
= fib_flag_trans(fa
->fa_type
, mask
, fi
);
2553 if (fa
->fa_type
== RTN_BROADCAST
2554 || fa
->fa_type
== RTN_MULTICAST
)
2559 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2560 "%d\t%08X\t%d\t%u\t%u%n",
2561 fi
->fib_dev
? fi
->fib_dev
->name
: "*",
2563 fi
->fib_nh
->nh_gw
, flags
, 0, 0,
2567 fi
->fib_advmss
+ 40 : 0),
2569 fi
->fib_rtt
>> 3, &len
);
2572 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2573 "%d\t%08X\t%d\t%u\t%u%n",
2574 prefix
, 0, flags
, 0, 0, 0,
2575 mask
, 0, 0, 0, &len
);
2577 seq_printf(seq
, "%*s\n", 127 - len
, "");
2584 static const struct seq_operations fib_route_seq_ops
= {
2585 .start
= fib_route_seq_start
,
2586 .next
= fib_route_seq_next
,
2587 .stop
= fib_route_seq_stop
,
2588 .show
= fib_route_seq_show
,
2591 static int fib_route_seq_open(struct inode
*inode
, struct file
*file
)
2593 return seq_open_net(inode
, file
, &fib_route_seq_ops
,
2594 sizeof(struct fib_route_iter
));
2597 static const struct file_operations fib_route_fops
= {
2598 .owner
= THIS_MODULE
,
2599 .open
= fib_route_seq_open
,
2601 .llseek
= seq_lseek
,
2602 .release
= seq_release_net
,
2605 int __net_init
fib_proc_init(struct net
*net
)
2607 if (!proc_net_fops_create(net
, "fib_trie", S_IRUGO
, &fib_trie_fops
))
2610 if (!proc_net_fops_create(net
, "fib_triestat", S_IRUGO
,
2611 &fib_triestat_fops
))
2614 if (!proc_net_fops_create(net
, "route", S_IRUGO
, &fib_route_fops
))
2620 proc_net_remove(net
, "fib_triestat");
2622 proc_net_remove(net
, "fib_trie");
2627 void __net_exit
fib_proc_exit(struct net
*net
)
2629 proc_net_remove(net
, "fib_trie");
2630 proc_net_remove(net
, "fib_triestat");
2631 proc_net_remove(net
, "route");
2634 #endif /* CONFIG_PROC_FS */