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 described 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 inline void free_leaf_info(struct leaf_info
*leaf
)
374 kfree_rcu(leaf
, rcu
);
377 static struct tnode
*tnode_alloc(size_t size
)
379 if (size
<= PAGE_SIZE
)
380 return kzalloc(size
, GFP_KERNEL
);
382 return vzalloc(size
);
385 static void __tnode_vfree(struct work_struct
*arg
)
387 struct tnode
*tn
= container_of(arg
, struct tnode
, work
);
391 static void __tnode_free_rcu(struct rcu_head
*head
)
393 struct tnode
*tn
= container_of(head
, struct tnode
, rcu
);
394 size_t size
= sizeof(struct tnode
) +
395 (sizeof(struct rt_trie_node
*) << tn
->bits
);
397 if (size
<= PAGE_SIZE
)
400 INIT_WORK(&tn
->work
, __tnode_vfree
);
401 schedule_work(&tn
->work
);
405 static inline void tnode_free(struct tnode
*tn
)
408 free_leaf((struct leaf
*) tn
);
410 call_rcu(&tn
->rcu
, __tnode_free_rcu
);
413 static void tnode_free_safe(struct tnode
*tn
)
416 tn
->tnode_free
= tnode_free_head
;
417 tnode_free_head
= tn
;
418 tnode_free_size
+= sizeof(struct tnode
) +
419 (sizeof(struct rt_trie_node
*) << tn
->bits
);
422 static void tnode_free_flush(void)
426 while ((tn
= tnode_free_head
)) {
427 tnode_free_head
= tn
->tnode_free
;
428 tn
->tnode_free
= NULL
;
432 if (tnode_free_size
>= PAGE_SIZE
* sync_pages
) {
438 static struct leaf
*leaf_new(void)
440 struct leaf
*l
= kmem_cache_alloc(trie_leaf_kmem
, GFP_KERNEL
);
443 INIT_HLIST_HEAD(&l
->list
);
448 static struct leaf_info
*leaf_info_new(int plen
)
450 struct leaf_info
*li
= kmalloc(sizeof(struct leaf_info
), GFP_KERNEL
);
453 INIT_LIST_HEAD(&li
->falh
);
458 static struct tnode
*tnode_new(t_key key
, int pos
, int bits
)
460 size_t sz
= sizeof(struct tnode
) + (sizeof(struct rt_trie_node
*) << bits
);
461 struct tnode
*tn
= tnode_alloc(sz
);
464 tn
->parent
= T_TNODE
;
468 tn
->full_children
= 0;
469 tn
->empty_children
= 1<<bits
;
472 pr_debug("AT %p s=%zu %zu\n", tn
, sizeof(struct tnode
),
473 sizeof(struct rt_trie_node
) << bits
);
478 * Check whether a tnode 'n' is "full", i.e. it is an internal node
479 * and no bits are skipped. See discussion in dyntree paper p. 6
482 static inline int tnode_full(const struct tnode
*tn
, const struct rt_trie_node
*n
)
484 if (n
== NULL
|| IS_LEAF(n
))
487 return ((struct tnode
*) n
)->pos
== tn
->pos
+ tn
->bits
;
490 static inline void put_child(struct trie
*t
, struct tnode
*tn
, int i
,
491 struct rt_trie_node
*n
)
493 tnode_put_child_reorg(tn
, i
, n
, -1);
497 * Add a child at position i overwriting the old value.
498 * Update the value of full_children and empty_children.
501 static void tnode_put_child_reorg(struct tnode
*tn
, int i
, struct rt_trie_node
*n
,
504 struct rt_trie_node
*chi
= rtnl_dereference(tn
->child
[i
]);
507 BUG_ON(i
>= 1<<tn
->bits
);
509 /* update emptyChildren */
510 if (n
== NULL
&& chi
!= NULL
)
511 tn
->empty_children
++;
512 else if (n
!= NULL
&& chi
== NULL
)
513 tn
->empty_children
--;
515 /* update fullChildren */
517 wasfull
= tnode_full(tn
, chi
);
519 isfull
= tnode_full(tn
, n
);
520 if (wasfull
&& !isfull
)
522 else if (!wasfull
&& isfull
)
526 node_set_parent(n
, tn
);
528 rcu_assign_pointer(tn
->child
[i
], n
);
532 static struct rt_trie_node
*resize(struct trie
*t
, struct tnode
*tn
)
535 struct tnode
*old_tn
;
536 int inflate_threshold_use
;
537 int halve_threshold_use
;
543 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
544 tn
, inflate_threshold
, halve_threshold
);
547 if (tn
->empty_children
== tnode_child_length(tn
)) {
552 if (tn
->empty_children
== tnode_child_length(tn
) - 1)
555 * Double as long as the resulting node has a number of
556 * nonempty nodes that are above the threshold.
560 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
561 * the Helsinki University of Technology and Matti Tikkanen of Nokia
562 * Telecommunications, page 6:
563 * "A node is doubled if the ratio of non-empty children to all
564 * children in the *doubled* node is at least 'high'."
566 * 'high' in this instance is the variable 'inflate_threshold'. It
567 * is expressed as a percentage, so we multiply it with
568 * tnode_child_length() and instead of multiplying by 2 (since the
569 * child array will be doubled by inflate()) and multiplying
570 * the left-hand side by 100 (to handle the percentage thing) we
571 * multiply the left-hand side by 50.
573 * The left-hand side may look a bit weird: tnode_child_length(tn)
574 * - tn->empty_children is of course the number of non-null children
575 * in the current node. tn->full_children is the number of "full"
576 * children, that is non-null tnodes with a skip value of 0.
577 * All of those will be doubled in the resulting inflated tnode, so
578 * we just count them one extra time here.
580 * A clearer way to write this would be:
582 * to_be_doubled = tn->full_children;
583 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
586 * new_child_length = tnode_child_length(tn) * 2;
588 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
590 * if (new_fill_factor >= inflate_threshold)
592 * ...and so on, tho it would mess up the while () loop.
595 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
599 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
600 * inflate_threshold * new_child_length
602 * expand not_to_be_doubled and to_be_doubled, and shorten:
603 * 100 * (tnode_child_length(tn) - tn->empty_children +
604 * tn->full_children) >= inflate_threshold * new_child_length
606 * expand new_child_length:
607 * 100 * (tnode_child_length(tn) - tn->empty_children +
608 * tn->full_children) >=
609 * inflate_threshold * tnode_child_length(tn) * 2
612 * 50 * (tn->full_children + tnode_child_length(tn) -
613 * tn->empty_children) >= inflate_threshold *
614 * tnode_child_length(tn)
620 /* Keep root node larger */
622 if (!node_parent((struct rt_trie_node
*)tn
)) {
623 inflate_threshold_use
= inflate_threshold_root
;
624 halve_threshold_use
= halve_threshold_root
;
626 inflate_threshold_use
= inflate_threshold
;
627 halve_threshold_use
= halve_threshold
;
631 while ((tn
->full_children
> 0 && max_work
-- &&
632 50 * (tn
->full_children
+ tnode_child_length(tn
)
633 - tn
->empty_children
)
634 >= inflate_threshold_use
* tnode_child_length(tn
))) {
641 #ifdef CONFIG_IP_FIB_TRIE_STATS
642 t
->stats
.resize_node_skipped
++;
650 /* Return if at least one inflate is run */
651 if (max_work
!= MAX_WORK
)
652 return (struct rt_trie_node
*) tn
;
655 * Halve as long as the number of empty children in this
656 * node is above threshold.
660 while (tn
->bits
> 1 && max_work
-- &&
661 100 * (tnode_child_length(tn
) - tn
->empty_children
) <
662 halve_threshold_use
* tnode_child_length(tn
)) {
668 #ifdef CONFIG_IP_FIB_TRIE_STATS
669 t
->stats
.resize_node_skipped
++;
676 /* Only one child remains */
677 if (tn
->empty_children
== tnode_child_length(tn
) - 1) {
679 for (i
= 0; i
< tnode_child_length(tn
); i
++) {
680 struct rt_trie_node
*n
;
682 n
= rtnl_dereference(tn
->child
[i
]);
686 /* compress one level */
688 node_set_parent(n
, NULL
);
693 return (struct rt_trie_node
*) tn
;
697 static void tnode_clean_free(struct tnode
*tn
)
700 struct tnode
*tofree
;
702 for (i
= 0; i
< tnode_child_length(tn
); i
++) {
703 tofree
= (struct tnode
*)rtnl_dereference(tn
->child
[i
]);
710 static struct tnode
*inflate(struct trie
*t
, struct tnode
*tn
)
712 struct tnode
*oldtnode
= tn
;
713 int olen
= tnode_child_length(tn
);
716 pr_debug("In inflate\n");
718 tn
= tnode_new(oldtnode
->key
, oldtnode
->pos
, oldtnode
->bits
+ 1);
721 return ERR_PTR(-ENOMEM
);
724 * Preallocate and store tnodes before the actual work so we
725 * don't get into an inconsistent state if memory allocation
726 * fails. In case of failure we return the oldnode and inflate
727 * of tnode is ignored.
730 for (i
= 0; i
< olen
; i
++) {
733 inode
= (struct tnode
*) tnode_get_child(oldtnode
, i
);
736 inode
->pos
== oldtnode
->pos
+ oldtnode
->bits
&&
738 struct tnode
*left
, *right
;
739 t_key m
= ~0U << (KEYLENGTH
- 1) >> inode
->pos
;
741 left
= tnode_new(inode
->key
&(~m
), inode
->pos
+ 1,
746 right
= tnode_new(inode
->key
|m
, inode
->pos
+ 1,
754 put_child(t
, tn
, 2*i
, (struct rt_trie_node
*) left
);
755 put_child(t
, tn
, 2*i
+1, (struct rt_trie_node
*) right
);
759 for (i
= 0; i
< olen
; i
++) {
761 struct rt_trie_node
*node
= tnode_get_child(oldtnode
, i
);
762 struct tnode
*left
, *right
;
769 /* A leaf or an internal node with skipped bits */
771 if (IS_LEAF(node
) || ((struct tnode
*) node
)->pos
>
772 tn
->pos
+ tn
->bits
- 1) {
773 if (tkey_extract_bits(node
->key
,
774 oldtnode
->pos
+ oldtnode
->bits
,
776 put_child(t
, tn
, 2*i
, node
);
778 put_child(t
, tn
, 2*i
+1, node
);
782 /* An internal node with two children */
783 inode
= (struct tnode
*) node
;
785 if (inode
->bits
== 1) {
786 put_child(t
, tn
, 2*i
, rtnl_dereference(inode
->child
[0]));
787 put_child(t
, tn
, 2*i
+1, rtnl_dereference(inode
->child
[1]));
789 tnode_free_safe(inode
);
793 /* An internal node with more than two children */
795 /* We will replace this node 'inode' with two new
796 * ones, 'left' and 'right', each with half of the
797 * original children. The two new nodes will have
798 * a position one bit further down the key and this
799 * means that the "significant" part of their keys
800 * (see the discussion near the top of this file)
801 * will differ by one bit, which will be "0" in
802 * left's key and "1" in right's key. Since we are
803 * moving the key position by one step, the bit that
804 * we are moving away from - the bit at position
805 * (inode->pos) - is the one that will differ between
806 * left and right. So... we synthesize that bit in the
808 * The mask 'm' below will be a single "one" bit at
809 * the position (inode->pos)
812 /* Use the old key, but set the new significant
816 left
= (struct tnode
*) tnode_get_child(tn
, 2*i
);
817 put_child(t
, tn
, 2*i
, NULL
);
821 right
= (struct tnode
*) tnode_get_child(tn
, 2*i
+1);
822 put_child(t
, tn
, 2*i
+1, NULL
);
826 size
= tnode_child_length(left
);
827 for (j
= 0; j
< size
; j
++) {
828 put_child(t
, left
, j
, rtnl_dereference(inode
->child
[j
]));
829 put_child(t
, right
, j
, rtnl_dereference(inode
->child
[j
+ size
]));
831 put_child(t
, tn
, 2*i
, resize(t
, left
));
832 put_child(t
, tn
, 2*i
+1, resize(t
, right
));
834 tnode_free_safe(inode
);
836 tnode_free_safe(oldtnode
);
839 tnode_clean_free(tn
);
840 return ERR_PTR(-ENOMEM
);
843 static struct tnode
*halve(struct trie
*t
, struct tnode
*tn
)
845 struct tnode
*oldtnode
= tn
;
846 struct rt_trie_node
*left
, *right
;
848 int olen
= tnode_child_length(tn
);
850 pr_debug("In halve\n");
852 tn
= tnode_new(oldtnode
->key
, oldtnode
->pos
, oldtnode
->bits
- 1);
855 return ERR_PTR(-ENOMEM
);
858 * Preallocate and store tnodes before the actual work so we
859 * don't get into an inconsistent state if memory allocation
860 * fails. In case of failure we return the oldnode and halve
861 * of tnode is ignored.
864 for (i
= 0; i
< olen
; i
+= 2) {
865 left
= tnode_get_child(oldtnode
, i
);
866 right
= tnode_get_child(oldtnode
, i
+1);
868 /* Two nonempty children */
872 newn
= tnode_new(left
->key
, tn
->pos
+ tn
->bits
, 1);
877 put_child(t
, tn
, i
/2, (struct rt_trie_node
*)newn
);
882 for (i
= 0; i
< olen
; i
+= 2) {
883 struct tnode
*newBinNode
;
885 left
= tnode_get_child(oldtnode
, i
);
886 right
= tnode_get_child(oldtnode
, i
+1);
888 /* At least one of the children is empty */
890 if (right
== NULL
) /* Both are empty */
892 put_child(t
, tn
, i
/2, right
);
897 put_child(t
, tn
, i
/2, left
);
901 /* Two nonempty children */
902 newBinNode
= (struct tnode
*) tnode_get_child(tn
, i
/2);
903 put_child(t
, tn
, i
/2, NULL
);
904 put_child(t
, newBinNode
, 0, left
);
905 put_child(t
, newBinNode
, 1, right
);
906 put_child(t
, tn
, i
/2, resize(t
, newBinNode
));
908 tnode_free_safe(oldtnode
);
911 tnode_clean_free(tn
);
912 return ERR_PTR(-ENOMEM
);
915 /* readside must use rcu_read_lock currently dump routines
916 via get_fa_head and dump */
918 static struct leaf_info
*find_leaf_info(struct leaf
*l
, int plen
)
920 struct hlist_head
*head
= &l
->list
;
921 struct hlist_node
*node
;
922 struct leaf_info
*li
;
924 hlist_for_each_entry_rcu(li
, node
, head
, hlist
)
925 if (li
->plen
== plen
)
931 static inline struct list_head
*get_fa_head(struct leaf
*l
, int plen
)
933 struct leaf_info
*li
= find_leaf_info(l
, plen
);
941 static void insert_leaf_info(struct hlist_head
*head
, struct leaf_info
*new)
943 struct leaf_info
*li
= NULL
, *last
= NULL
;
944 struct hlist_node
*node
;
946 if (hlist_empty(head
)) {
947 hlist_add_head_rcu(&new->hlist
, head
);
949 hlist_for_each_entry(li
, node
, head
, hlist
) {
950 if (new->plen
> li
->plen
)
956 hlist_add_after_rcu(&last
->hlist
, &new->hlist
);
958 hlist_add_before_rcu(&new->hlist
, &li
->hlist
);
962 /* rcu_read_lock needs to be hold by caller from readside */
965 fib_find_node(struct trie
*t
, u32 key
)
969 struct rt_trie_node
*n
;
972 n
= rcu_dereference_rtnl(t
->trie
);
974 while (n
!= NULL
&& NODE_TYPE(n
) == T_TNODE
) {
975 tn
= (struct tnode
*) n
;
979 if (tkey_sub_equals(tn
->key
, pos
, tn
->pos
-pos
, key
)) {
980 pos
= tn
->pos
+ tn
->bits
;
981 n
= tnode_get_child_rcu(tn
,
982 tkey_extract_bits(key
,
988 /* Case we have found a leaf. Compare prefixes */
990 if (n
!= NULL
&& IS_LEAF(n
) && tkey_equals(key
, n
->key
))
991 return (struct leaf
*)n
;
996 static void trie_rebalance(struct trie
*t
, struct tnode
*tn
)
1004 while (tn
!= NULL
&& (tp
= node_parent((struct rt_trie_node
*)tn
)) != NULL
) {
1005 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1006 wasfull
= tnode_full(tp
, tnode_get_child(tp
, cindex
));
1007 tn
= (struct tnode
*) resize(t
, (struct tnode
*)tn
);
1009 tnode_put_child_reorg((struct tnode
*)tp
, cindex
,
1010 (struct rt_trie_node
*)tn
, wasfull
);
1012 tp
= node_parent((struct rt_trie_node
*) tn
);
1014 rcu_assign_pointer(t
->trie
, (struct rt_trie_node
*)tn
);
1022 /* Handle last (top) tnode */
1024 tn
= (struct tnode
*)resize(t
, (struct tnode
*)tn
);
1026 rcu_assign_pointer(t
->trie
, (struct rt_trie_node
*)tn
);
1030 /* only used from updater-side */
1032 static struct list_head
*fib_insert_node(struct trie
*t
, u32 key
, int plen
)
1035 struct tnode
*tp
= NULL
, *tn
= NULL
;
1036 struct rt_trie_node
*n
;
1039 struct list_head
*fa_head
= NULL
;
1040 struct leaf_info
*li
;
1044 n
= rtnl_dereference(t
->trie
);
1046 /* If we point to NULL, stop. Either the tree is empty and we should
1047 * just put a new leaf in if, or we have reached an empty child slot,
1048 * and we should just put our new leaf in that.
1049 * If we point to a T_TNODE, check if it matches our key. Note that
1050 * a T_TNODE might be skipping any number of bits - its 'pos' need
1051 * not be the parent's 'pos'+'bits'!
1053 * If it does match the current key, get pos/bits from it, extract
1054 * the index from our key, push the T_TNODE and walk the tree.
1056 * If it doesn't, we have to replace it with a new T_TNODE.
1058 * If we point to a T_LEAF, it might or might not have the same key
1059 * as we do. If it does, just change the value, update the T_LEAF's
1060 * value, and return it.
1061 * If it doesn't, we need to replace it with a T_TNODE.
1064 while (n
!= NULL
&& NODE_TYPE(n
) == T_TNODE
) {
1065 tn
= (struct tnode
*) n
;
1069 if (tkey_sub_equals(tn
->key
, pos
, tn
->pos
-pos
, key
)) {
1071 pos
= tn
->pos
+ tn
->bits
;
1072 n
= tnode_get_child(tn
,
1073 tkey_extract_bits(key
,
1077 BUG_ON(n
&& node_parent(n
) != tn
);
1083 * n ----> NULL, LEAF or TNODE
1085 * tp is n's (parent) ----> NULL or TNODE
1088 BUG_ON(tp
&& IS_LEAF(tp
));
1090 /* Case 1: n is a leaf. Compare prefixes */
1092 if (n
!= NULL
&& IS_LEAF(n
) && tkey_equals(key
, n
->key
)) {
1093 l
= (struct leaf
*) n
;
1094 li
= leaf_info_new(plen
);
1099 fa_head
= &li
->falh
;
1100 insert_leaf_info(&l
->list
, li
);
1109 li
= leaf_info_new(plen
);
1116 fa_head
= &li
->falh
;
1117 insert_leaf_info(&l
->list
, li
);
1119 if (t
->trie
&& n
== NULL
) {
1120 /* Case 2: n is NULL, and will just insert a new leaf */
1122 node_set_parent((struct rt_trie_node
*)l
, tp
);
1124 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1125 put_child(t
, (struct tnode
*)tp
, cindex
, (struct rt_trie_node
*)l
);
1127 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1129 * Add a new tnode here
1130 * first tnode need some special handling
1134 pos
= tp
->pos
+tp
->bits
;
1139 newpos
= tkey_mismatch(key
, pos
, n
->key
);
1140 tn
= tnode_new(n
->key
, newpos
, 1);
1143 tn
= tnode_new(key
, newpos
, 1); /* First tnode */
1152 node_set_parent((struct rt_trie_node
*)tn
, tp
);
1154 missbit
= tkey_extract_bits(key
, newpos
, 1);
1155 put_child(t
, tn
, missbit
, (struct rt_trie_node
*)l
);
1156 put_child(t
, tn
, 1-missbit
, n
);
1159 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1160 put_child(t
, (struct tnode
*)tp
, cindex
,
1161 (struct rt_trie_node
*)tn
);
1163 rcu_assign_pointer(t
->trie
, (struct rt_trie_node
*)tn
);
1168 if (tp
&& tp
->pos
+ tp
->bits
> 32)
1169 pr_warning("fib_trie"
1170 " tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1171 tp
, tp
->pos
, tp
->bits
, key
, plen
);
1173 /* Rebalance the trie */
1175 trie_rebalance(t
, tp
);
1181 * Caller must hold RTNL.
1183 int fib_table_insert(struct fib_table
*tb
, struct fib_config
*cfg
)
1185 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1186 struct fib_alias
*fa
, *new_fa
;
1187 struct list_head
*fa_head
= NULL
;
1188 struct fib_info
*fi
;
1189 int plen
= cfg
->fc_dst_len
;
1190 u8 tos
= cfg
->fc_tos
;
1198 key
= ntohl(cfg
->fc_dst
);
1200 pr_debug("Insert table=%u %08x/%d\n", tb
->tb_id
, key
, plen
);
1202 mask
= ntohl(inet_make_mask(plen
));
1209 fi
= fib_create_info(cfg
);
1215 l
= fib_find_node(t
, key
);
1219 fa_head
= get_fa_head(l
, plen
);
1220 fa
= fib_find_alias(fa_head
, tos
, fi
->fib_priority
);
1223 /* Now fa, if non-NULL, points to the first fib alias
1224 * with the same keys [prefix,tos,priority], if such key already
1225 * exists or to the node before which we will insert new one.
1227 * If fa is NULL, we will need to allocate a new one and
1228 * insert to the head of f.
1230 * If f is NULL, no fib node matched the destination key
1231 * and we need to allocate a new one of those as well.
1234 if (fa
&& fa
->fa_tos
== tos
&&
1235 fa
->fa_info
->fib_priority
== fi
->fib_priority
) {
1236 struct fib_alias
*fa_first
, *fa_match
;
1239 if (cfg
->fc_nlflags
& NLM_F_EXCL
)
1243 * 1. Find exact match for type, scope, fib_info to avoid
1245 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1249 fa
= list_entry(fa
->fa_list
.prev
, struct fib_alias
, fa_list
);
1250 list_for_each_entry_continue(fa
, fa_head
, fa_list
) {
1251 if (fa
->fa_tos
!= tos
)
1253 if (fa
->fa_info
->fib_priority
!= fi
->fib_priority
)
1255 if (fa
->fa_type
== cfg
->fc_type
&&
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 state
= fa
->fa_state
;
1282 new_fa
->fa_state
= state
& ~FA_S_ACCESSED
;
1284 list_replace_rcu(&fa
->fa_list
, &new_fa
->fa_list
);
1285 alias_free_mem_rcu(fa
);
1287 fib_release_info(fi_drop
);
1288 if (state
& FA_S_ACCESSED
)
1289 rt_cache_flush(cfg
->fc_nlinfo
.nl_net
, -1);
1290 rtmsg_fib(RTM_NEWROUTE
, htonl(key
), new_fa
, plen
,
1291 tb
->tb_id
, &cfg
->fc_nlinfo
, NLM_F_REPLACE
);
1295 /* Error if we find a perfect match which
1296 * uses the same scope, type, and nexthop
1302 if (!(cfg
->fc_nlflags
& NLM_F_APPEND
))
1306 if (!(cfg
->fc_nlflags
& NLM_F_CREATE
))
1310 new_fa
= kmem_cache_alloc(fn_alias_kmem
, GFP_KERNEL
);
1314 new_fa
->fa_info
= fi
;
1315 new_fa
->fa_tos
= tos
;
1316 new_fa
->fa_type
= cfg
->fc_type
;
1317 new_fa
->fa_state
= 0;
1319 * Insert new entry to the list.
1323 fa_head
= fib_insert_node(t
, key
, plen
);
1324 if (unlikely(!fa_head
)) {
1326 goto out_free_new_fa
;
1331 tb
->tb_num_default
++;
1333 list_add_tail_rcu(&new_fa
->fa_list
,
1334 (fa
? &fa
->fa_list
: fa_head
));
1336 rt_cache_flush(cfg
->fc_nlinfo
.nl_net
, -1);
1337 rtmsg_fib(RTM_NEWROUTE
, htonl(key
), new_fa
, plen
, tb
->tb_id
,
1338 &cfg
->fc_nlinfo
, 0);
1343 kmem_cache_free(fn_alias_kmem
, new_fa
);
1345 fib_release_info(fi
);
1350 /* should be called with rcu_read_lock */
1351 static int check_leaf(struct fib_table
*tb
, struct trie
*t
, struct leaf
*l
,
1352 t_key key
, const struct flowi4
*flp
,
1353 struct fib_result
*res
, int fib_flags
)
1355 struct leaf_info
*li
;
1356 struct hlist_head
*hhead
= &l
->list
;
1357 struct hlist_node
*node
;
1359 hlist_for_each_entry_rcu(li
, node
, hhead
, hlist
) {
1360 struct fib_alias
*fa
;
1361 int plen
= li
->plen
;
1362 __be32 mask
= inet_make_mask(plen
);
1364 if (l
->key
!= (key
& ntohl(mask
)))
1367 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
1368 struct fib_info
*fi
= fa
->fa_info
;
1371 if (fa
->fa_tos
&& fa
->fa_tos
!= flp
->flowi4_tos
)
1373 if (fa
->fa_info
->fib_scope
< flp
->flowi4_scope
)
1375 fib_alias_accessed(fa
);
1376 err
= fib_props
[fa
->fa_type
].error
;
1378 #ifdef CONFIG_IP_FIB_TRIE_STATS
1379 t
->stats
.semantic_match_passed
++;
1383 if (fi
->fib_flags
& RTNH_F_DEAD
)
1385 for (nhsel
= 0; nhsel
< fi
->fib_nhs
; nhsel
++) {
1386 const struct fib_nh
*nh
= &fi
->fib_nh
[nhsel
];
1388 if (nh
->nh_flags
& RTNH_F_DEAD
)
1390 if (flp
->flowi4_oif
&& flp
->flowi4_oif
!= nh
->nh_oif
)
1393 #ifdef CONFIG_IP_FIB_TRIE_STATS
1394 t
->stats
.semantic_match_passed
++;
1396 res
->prefixlen
= plen
;
1397 res
->nh_sel
= nhsel
;
1398 res
->type
= fa
->fa_type
;
1399 res
->scope
= fa
->fa_info
->fib_scope
;
1402 res
->fa_head
= &li
->falh
;
1403 if (!(fib_flags
& FIB_LOOKUP_NOREF
))
1404 atomic_inc(&res
->fi
->fib_clntref
);
1409 #ifdef CONFIG_IP_FIB_TRIE_STATS
1410 t
->stats
.semantic_match_miss
++;
1417 int fib_table_lookup(struct fib_table
*tb
, const struct flowi4
*flp
,
1418 struct fib_result
*res
, int fib_flags
)
1420 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1422 struct rt_trie_node
*n
;
1424 unsigned int pos
, bits
;
1425 t_key key
= ntohl(flp
->daddr
);
1426 unsigned int chopped_off
;
1428 unsigned int current_prefix_length
= KEYLENGTH
;
1430 t_key pref_mismatch
;
1434 n
= rcu_dereference(t
->trie
);
1438 #ifdef CONFIG_IP_FIB_TRIE_STATS
1444 ret
= check_leaf(tb
, t
, (struct leaf
*)n
, key
, flp
, res
, fib_flags
);
1448 pn
= (struct tnode
*) n
;
1456 cindex
= tkey_extract_bits(mask_pfx(key
, current_prefix_length
),
1459 n
= tnode_get_child_rcu(pn
, cindex
);
1462 #ifdef CONFIG_IP_FIB_TRIE_STATS
1463 t
->stats
.null_node_hit
++;
1469 ret
= check_leaf(tb
, t
, (struct leaf
*)n
, key
, flp
, res
, fib_flags
);
1475 cn
= (struct tnode
*)n
;
1478 * It's a tnode, and we can do some extra checks here if we
1479 * like, to avoid descending into a dead-end branch.
1480 * This tnode is in the parent's child array at index
1481 * key[p_pos..p_pos+p_bits] but potentially with some bits
1482 * chopped off, so in reality the index may be just a
1483 * subprefix, padded with zero at the end.
1484 * We can also take a look at any skipped bits in this
1485 * tnode - everything up to p_pos is supposed to be ok,
1486 * and the non-chopped bits of the index (se previous
1487 * paragraph) are also guaranteed ok, but the rest is
1488 * considered unknown.
1490 * The skipped bits are key[pos+bits..cn->pos].
1493 /* If current_prefix_length < pos+bits, we are already doing
1494 * actual prefix matching, which means everything from
1495 * pos+(bits-chopped_off) onward must be zero along some
1496 * branch of this subtree - otherwise there is *no* valid
1497 * prefix present. Here we can only check the skipped
1498 * bits. Remember, since we have already indexed into the
1499 * parent's child array, we know that the bits we chopped of
1503 /* NOTA BENE: Checking only skipped bits
1504 for the new node here */
1506 if (current_prefix_length
< pos
+bits
) {
1507 if (tkey_extract_bits(cn
->key
, current_prefix_length
,
1508 cn
->pos
- current_prefix_length
)
1514 * If chopped_off=0, the index is fully validated and we
1515 * only need to look at the skipped bits for this, the new,
1516 * tnode. What we actually want to do is to find out if
1517 * these skipped bits match our key perfectly, or if we will
1518 * have to count on finding a matching prefix further down,
1519 * because if we do, we would like to have some way of
1520 * verifying the existence of such a prefix at this point.
1523 /* The only thing we can do at this point is to verify that
1524 * any such matching prefix can indeed be a prefix to our
1525 * key, and if the bits in the node we are inspecting that
1526 * do not match our key are not ZERO, this cannot be true.
1527 * Thus, find out where there is a mismatch (before cn->pos)
1528 * and verify that all the mismatching bits are zero in the
1533 * Note: We aren't very concerned about the piece of
1534 * the key that precede pn->pos+pn->bits, since these
1535 * have already been checked. The bits after cn->pos
1536 * aren't checked since these are by definition
1537 * "unknown" at this point. Thus, what we want to see
1538 * is if we are about to enter the "prefix matching"
1539 * state, and in that case verify that the skipped
1540 * bits that will prevail throughout this subtree are
1541 * zero, as they have to be if we are to find a
1545 pref_mismatch
= mask_pfx(cn
->key
^ key
, cn
->pos
);
1548 * In short: If skipped bits in this node do not match
1549 * the search key, enter the "prefix matching"
1552 if (pref_mismatch
) {
1553 int mp
= KEYLENGTH
- fls(pref_mismatch
);
1555 if (tkey_extract_bits(cn
->key
, mp
, cn
->pos
- mp
) != 0)
1558 if (current_prefix_length
>= cn
->pos
)
1559 current_prefix_length
= mp
;
1562 pn
= (struct tnode
*)n
; /* Descend */
1569 /* As zero don't change the child key (cindex) */
1570 while ((chopped_off
<= pn
->bits
)
1571 && !(cindex
& (1<<(chopped_off
-1))))
1574 /* Decrease current_... with bits chopped off */
1575 if (current_prefix_length
> pn
->pos
+ pn
->bits
- chopped_off
)
1576 current_prefix_length
= pn
->pos
+ pn
->bits
1580 * Either we do the actual chop off according or if we have
1581 * chopped off all bits in this tnode walk up to our parent.
1584 if (chopped_off
<= pn
->bits
) {
1585 cindex
&= ~(1 << (chopped_off
-1));
1587 struct tnode
*parent
= node_parent_rcu((struct rt_trie_node
*) pn
);
1591 /* Get Child's index */
1592 cindex
= tkey_extract_bits(pn
->key
, parent
->pos
, parent
->bits
);
1596 #ifdef CONFIG_IP_FIB_TRIE_STATS
1597 t
->stats
.backtrack
++;
1610 * Remove the leaf and return parent.
1612 static void trie_leaf_remove(struct trie
*t
, struct leaf
*l
)
1614 struct tnode
*tp
= node_parent((struct rt_trie_node
*) l
);
1616 pr_debug("entering trie_leaf_remove(%p)\n", l
);
1619 t_key cindex
= tkey_extract_bits(l
->key
, tp
->pos
, tp
->bits
);
1620 put_child(t
, (struct tnode
*)tp
, cindex
, NULL
);
1621 trie_rebalance(t
, tp
);
1623 rcu_assign_pointer(t
->trie
, NULL
);
1629 * Caller must hold RTNL.
1631 int fib_table_delete(struct fib_table
*tb
, struct fib_config
*cfg
)
1633 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1635 int plen
= cfg
->fc_dst_len
;
1636 u8 tos
= cfg
->fc_tos
;
1637 struct fib_alias
*fa
, *fa_to_delete
;
1638 struct list_head
*fa_head
;
1640 struct leaf_info
*li
;
1645 key
= ntohl(cfg
->fc_dst
);
1646 mask
= ntohl(inet_make_mask(plen
));
1652 l
= fib_find_node(t
, key
);
1657 fa_head
= get_fa_head(l
, plen
);
1658 fa
= fib_find_alias(fa_head
, tos
, 0);
1663 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key
, plen
, tos
, t
);
1665 fa_to_delete
= NULL
;
1666 fa
= list_entry(fa
->fa_list
.prev
, struct fib_alias
, fa_list
);
1667 list_for_each_entry_continue(fa
, fa_head
, fa_list
) {
1668 struct fib_info
*fi
= fa
->fa_info
;
1670 if (fa
->fa_tos
!= tos
)
1673 if ((!cfg
->fc_type
|| fa
->fa_type
== cfg
->fc_type
) &&
1674 (cfg
->fc_scope
== RT_SCOPE_NOWHERE
||
1675 fa
->fa_info
->fib_scope
== cfg
->fc_scope
) &&
1676 (!cfg
->fc_prefsrc
||
1677 fi
->fib_prefsrc
== cfg
->fc_prefsrc
) &&
1678 (!cfg
->fc_protocol
||
1679 fi
->fib_protocol
== cfg
->fc_protocol
) &&
1680 fib_nh_match(cfg
, fi
) == 0) {
1690 rtmsg_fib(RTM_DELROUTE
, htonl(key
), fa
, plen
, tb
->tb_id
,
1691 &cfg
->fc_nlinfo
, 0);
1693 l
= fib_find_node(t
, key
);
1694 li
= find_leaf_info(l
, plen
);
1696 list_del_rcu(&fa
->fa_list
);
1699 tb
->tb_num_default
--;
1701 if (list_empty(fa_head
)) {
1702 hlist_del_rcu(&li
->hlist
);
1706 if (hlist_empty(&l
->list
))
1707 trie_leaf_remove(t
, l
);
1709 if (fa
->fa_state
& FA_S_ACCESSED
)
1710 rt_cache_flush(cfg
->fc_nlinfo
.nl_net
, -1);
1712 fib_release_info(fa
->fa_info
);
1713 alias_free_mem_rcu(fa
);
1717 static int trie_flush_list(struct list_head
*head
)
1719 struct fib_alias
*fa
, *fa_node
;
1722 list_for_each_entry_safe(fa
, fa_node
, head
, fa_list
) {
1723 struct fib_info
*fi
= fa
->fa_info
;
1725 if (fi
&& (fi
->fib_flags
& RTNH_F_DEAD
)) {
1726 list_del_rcu(&fa
->fa_list
);
1727 fib_release_info(fa
->fa_info
);
1728 alias_free_mem_rcu(fa
);
1735 static int trie_flush_leaf(struct leaf
*l
)
1738 struct hlist_head
*lih
= &l
->list
;
1739 struct hlist_node
*node
, *tmp
;
1740 struct leaf_info
*li
= NULL
;
1742 hlist_for_each_entry_safe(li
, node
, tmp
, lih
, hlist
) {
1743 found
+= trie_flush_list(&li
->falh
);
1745 if (list_empty(&li
->falh
)) {
1746 hlist_del_rcu(&li
->hlist
);
1754 * Scan for the next right leaf starting at node p->child[idx]
1755 * Since we have back pointer, no recursion necessary.
1757 static struct leaf
*leaf_walk_rcu(struct tnode
*p
, struct rt_trie_node
*c
)
1763 idx
= tkey_extract_bits(c
->key
, p
->pos
, p
->bits
) + 1;
1767 while (idx
< 1u << p
->bits
) {
1768 c
= tnode_get_child_rcu(p
, idx
++);
1773 prefetch(rcu_dereference_rtnl(p
->child
[idx
]));
1774 return (struct leaf
*) c
;
1777 /* Rescan start scanning in new node */
1778 p
= (struct tnode
*) c
;
1782 /* Node empty, walk back up to parent */
1783 c
= (struct rt_trie_node
*) p
;
1784 } while ((p
= node_parent_rcu(c
)) != NULL
);
1786 return NULL
; /* Root of trie */
1789 static struct leaf
*trie_firstleaf(struct trie
*t
)
1791 struct tnode
*n
= (struct tnode
*)rcu_dereference_rtnl(t
->trie
);
1796 if (IS_LEAF(n
)) /* trie is just a leaf */
1797 return (struct leaf
*) n
;
1799 return leaf_walk_rcu(n
, NULL
);
1802 static struct leaf
*trie_nextleaf(struct leaf
*l
)
1804 struct rt_trie_node
*c
= (struct rt_trie_node
*) l
;
1805 struct tnode
*p
= node_parent_rcu(c
);
1808 return NULL
; /* trie with just one leaf */
1810 return leaf_walk_rcu(p
, c
);
1813 static struct leaf
*trie_leafindex(struct trie
*t
, int index
)
1815 struct leaf
*l
= trie_firstleaf(t
);
1817 while (l
&& index
-- > 0)
1818 l
= trie_nextleaf(l
);
1825 * Caller must hold RTNL.
1827 int fib_table_flush(struct fib_table
*tb
)
1829 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1830 struct leaf
*l
, *ll
= NULL
;
1833 for (l
= trie_firstleaf(t
); l
; l
= trie_nextleaf(l
)) {
1834 found
+= trie_flush_leaf(l
);
1836 if (ll
&& hlist_empty(&ll
->list
))
1837 trie_leaf_remove(t
, ll
);
1841 if (ll
&& hlist_empty(&ll
->list
))
1842 trie_leaf_remove(t
, ll
);
1844 pr_debug("trie_flush found=%d\n", found
);
1848 void fib_free_table(struct fib_table
*tb
)
1853 static int fn_trie_dump_fa(t_key key
, int plen
, struct list_head
*fah
,
1854 struct fib_table
*tb
,
1855 struct sk_buff
*skb
, struct netlink_callback
*cb
)
1858 struct fib_alias
*fa
;
1859 __be32 xkey
= htonl(key
);
1864 /* rcu_read_lock is hold by caller */
1866 list_for_each_entry_rcu(fa
, fah
, fa_list
) {
1872 if (fib_dump_info(skb
, NETLINK_CB(cb
->skb
).pid
,
1880 fa
->fa_info
, NLM_F_MULTI
) < 0) {
1890 static int fn_trie_dump_leaf(struct leaf
*l
, struct fib_table
*tb
,
1891 struct sk_buff
*skb
, struct netlink_callback
*cb
)
1893 struct leaf_info
*li
;
1894 struct hlist_node
*node
;
1900 /* rcu_read_lock is hold by caller */
1901 hlist_for_each_entry_rcu(li
, node
, &l
->list
, hlist
) {
1910 if (list_empty(&li
->falh
))
1913 if (fn_trie_dump_fa(l
->key
, li
->plen
, &li
->falh
, tb
, skb
, cb
) < 0) {
1924 int fib_table_dump(struct fib_table
*tb
, struct sk_buff
*skb
,
1925 struct netlink_callback
*cb
)
1928 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1929 t_key key
= cb
->args
[2];
1930 int count
= cb
->args
[3];
1933 /* Dump starting at last key.
1934 * Note: 0.0.0.0/0 (ie default) is first key.
1937 l
= trie_firstleaf(t
);
1939 /* Normally, continue from last key, but if that is missing
1940 * fallback to using slow rescan
1942 l
= fib_find_node(t
, key
);
1944 l
= trie_leafindex(t
, count
);
1948 cb
->args
[2] = l
->key
;
1949 if (fn_trie_dump_leaf(l
, tb
, skb
, cb
) < 0) {
1950 cb
->args
[3] = count
;
1956 l
= trie_nextleaf(l
);
1957 memset(&cb
->args
[4], 0,
1958 sizeof(cb
->args
) - 4*sizeof(cb
->args
[0]));
1960 cb
->args
[3] = count
;
1966 void __init
fib_trie_init(void)
1968 fn_alias_kmem
= kmem_cache_create("ip_fib_alias",
1969 sizeof(struct fib_alias
),
1970 0, SLAB_PANIC
, NULL
);
1972 trie_leaf_kmem
= kmem_cache_create("ip_fib_trie",
1973 max(sizeof(struct leaf
),
1974 sizeof(struct leaf_info
)),
1975 0, SLAB_PANIC
, NULL
);
1979 struct fib_table
*fib_trie_table(u32 id
)
1981 struct fib_table
*tb
;
1984 tb
= kmalloc(sizeof(struct fib_table
) + sizeof(struct trie
),
1990 tb
->tb_default
= -1;
1991 tb
->tb_num_default
= 0;
1993 t
= (struct trie
*) tb
->tb_data
;
1994 memset(t
, 0, sizeof(*t
));
1999 #ifdef CONFIG_PROC_FS
2000 /* Depth first Trie walk iterator */
2001 struct fib_trie_iter
{
2002 struct seq_net_private p
;
2003 struct fib_table
*tb
;
2004 struct tnode
*tnode
;
2009 static struct rt_trie_node
*fib_trie_get_next(struct fib_trie_iter
*iter
)
2011 struct tnode
*tn
= iter
->tnode
;
2012 unsigned int cindex
= iter
->index
;
2015 /* A single entry routing table */
2019 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2020 iter
->tnode
, iter
->index
, iter
->depth
);
2022 while (cindex
< (1<<tn
->bits
)) {
2023 struct rt_trie_node
*n
= tnode_get_child_rcu(tn
, cindex
);
2028 iter
->index
= cindex
+ 1;
2030 /* push down one level */
2031 iter
->tnode
= (struct tnode
*) n
;
2041 /* Current node exhausted, pop back up */
2042 p
= node_parent_rcu((struct rt_trie_node
*)tn
);
2044 cindex
= tkey_extract_bits(tn
->key
, p
->pos
, p
->bits
)+1;
2054 static struct rt_trie_node
*fib_trie_get_first(struct fib_trie_iter
*iter
,
2057 struct rt_trie_node
*n
;
2062 n
= rcu_dereference(t
->trie
);
2067 iter
->tnode
= (struct tnode
*) n
;
2079 static void trie_collect_stats(struct trie
*t
, struct trie_stat
*s
)
2081 struct rt_trie_node
*n
;
2082 struct fib_trie_iter iter
;
2084 memset(s
, 0, sizeof(*s
));
2087 for (n
= fib_trie_get_first(&iter
, t
); n
; n
= fib_trie_get_next(&iter
)) {
2089 struct leaf
*l
= (struct leaf
*)n
;
2090 struct leaf_info
*li
;
2091 struct hlist_node
*tmp
;
2094 s
->totdepth
+= iter
.depth
;
2095 if (iter
.depth
> s
->maxdepth
)
2096 s
->maxdepth
= iter
.depth
;
2098 hlist_for_each_entry_rcu(li
, tmp
, &l
->list
, hlist
)
2101 const struct tnode
*tn
= (const struct tnode
*) n
;
2105 if (tn
->bits
< MAX_STAT_DEPTH
)
2106 s
->nodesizes
[tn
->bits
]++;
2108 for (i
= 0; i
< (1<<tn
->bits
); i
++)
2117 * This outputs /proc/net/fib_triestats
2119 static void trie_show_stats(struct seq_file
*seq
, struct trie_stat
*stat
)
2121 unsigned int i
, max
, pointers
, bytes
, avdepth
;
2124 avdepth
= stat
->totdepth
*100 / stat
->leaves
;
2128 seq_printf(seq
, "\tAver depth: %u.%02d\n",
2129 avdepth
/ 100, avdepth
% 100);
2130 seq_printf(seq
, "\tMax depth: %u\n", stat
->maxdepth
);
2132 seq_printf(seq
, "\tLeaves: %u\n", stat
->leaves
);
2133 bytes
= sizeof(struct leaf
) * stat
->leaves
;
2135 seq_printf(seq
, "\tPrefixes: %u\n", stat
->prefixes
);
2136 bytes
+= sizeof(struct leaf_info
) * stat
->prefixes
;
2138 seq_printf(seq
, "\tInternal nodes: %u\n\t", stat
->tnodes
);
2139 bytes
+= sizeof(struct tnode
) * stat
->tnodes
;
2141 max
= MAX_STAT_DEPTH
;
2142 while (max
> 0 && stat
->nodesizes
[max
-1] == 0)
2146 for (i
= 1; i
<= max
; i
++)
2147 if (stat
->nodesizes
[i
] != 0) {
2148 seq_printf(seq
, " %u: %u", i
, stat
->nodesizes
[i
]);
2149 pointers
+= (1<<i
) * stat
->nodesizes
[i
];
2151 seq_putc(seq
, '\n');
2152 seq_printf(seq
, "\tPointers: %u\n", pointers
);
2154 bytes
+= sizeof(struct rt_trie_node
*) * pointers
;
2155 seq_printf(seq
, "Null ptrs: %u\n", stat
->nullpointers
);
2156 seq_printf(seq
, "Total size: %u kB\n", (bytes
+ 1023) / 1024);
2159 #ifdef CONFIG_IP_FIB_TRIE_STATS
2160 static void trie_show_usage(struct seq_file
*seq
,
2161 const struct trie_use_stats
*stats
)
2163 seq_printf(seq
, "\nCounters:\n---------\n");
2164 seq_printf(seq
, "gets = %u\n", stats
->gets
);
2165 seq_printf(seq
, "backtracks = %u\n", stats
->backtrack
);
2166 seq_printf(seq
, "semantic match passed = %u\n",
2167 stats
->semantic_match_passed
);
2168 seq_printf(seq
, "semantic match miss = %u\n",
2169 stats
->semantic_match_miss
);
2170 seq_printf(seq
, "null node hit= %u\n", stats
->null_node_hit
);
2171 seq_printf(seq
, "skipped node resize = %u\n\n",
2172 stats
->resize_node_skipped
);
2174 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2176 static void fib_table_print(struct seq_file
*seq
, struct fib_table
*tb
)
2178 if (tb
->tb_id
== RT_TABLE_LOCAL
)
2179 seq_puts(seq
, "Local:\n");
2180 else if (tb
->tb_id
== RT_TABLE_MAIN
)
2181 seq_puts(seq
, "Main:\n");
2183 seq_printf(seq
, "Id %d:\n", tb
->tb_id
);
2187 static int fib_triestat_seq_show(struct seq_file
*seq
, void *v
)
2189 struct net
*net
= (struct net
*)seq
->private;
2193 "Basic info: size of leaf:"
2194 " %Zd bytes, size of tnode: %Zd bytes.\n",
2195 sizeof(struct leaf
), sizeof(struct tnode
));
2197 for (h
= 0; h
< FIB_TABLE_HASHSZ
; h
++) {
2198 struct hlist_head
*head
= &net
->ipv4
.fib_table_hash
[h
];
2199 struct hlist_node
*node
;
2200 struct fib_table
*tb
;
2202 hlist_for_each_entry_rcu(tb
, node
, head
, tb_hlist
) {
2203 struct trie
*t
= (struct trie
*) tb
->tb_data
;
2204 struct trie_stat stat
;
2209 fib_table_print(seq
, tb
);
2211 trie_collect_stats(t
, &stat
);
2212 trie_show_stats(seq
, &stat
);
2213 #ifdef CONFIG_IP_FIB_TRIE_STATS
2214 trie_show_usage(seq
, &t
->stats
);
2222 static int fib_triestat_seq_open(struct inode
*inode
, struct file
*file
)
2224 return single_open_net(inode
, file
, fib_triestat_seq_show
);
2227 static const struct file_operations fib_triestat_fops
= {
2228 .owner
= THIS_MODULE
,
2229 .open
= fib_triestat_seq_open
,
2231 .llseek
= seq_lseek
,
2232 .release
= single_release_net
,
2235 static struct rt_trie_node
*fib_trie_get_idx(struct seq_file
*seq
, loff_t pos
)
2237 struct fib_trie_iter
*iter
= seq
->private;
2238 struct net
*net
= seq_file_net(seq
);
2242 for (h
= 0; h
< FIB_TABLE_HASHSZ
; h
++) {
2243 struct hlist_head
*head
= &net
->ipv4
.fib_table_hash
[h
];
2244 struct hlist_node
*node
;
2245 struct fib_table
*tb
;
2247 hlist_for_each_entry_rcu(tb
, node
, head
, tb_hlist
) {
2248 struct rt_trie_node
*n
;
2250 for (n
= fib_trie_get_first(iter
,
2251 (struct trie
*) tb
->tb_data
);
2252 n
; n
= fib_trie_get_next(iter
))
2263 static void *fib_trie_seq_start(struct seq_file
*seq
, loff_t
*pos
)
2267 return fib_trie_get_idx(seq
, *pos
);
2270 static void *fib_trie_seq_next(struct seq_file
*seq
, void *v
, loff_t
*pos
)
2272 struct fib_trie_iter
*iter
= seq
->private;
2273 struct net
*net
= seq_file_net(seq
);
2274 struct fib_table
*tb
= iter
->tb
;
2275 struct hlist_node
*tb_node
;
2277 struct rt_trie_node
*n
;
2280 /* next node in same table */
2281 n
= fib_trie_get_next(iter
);
2285 /* walk rest of this hash chain */
2286 h
= tb
->tb_id
& (FIB_TABLE_HASHSZ
- 1);
2287 while ((tb_node
= rcu_dereference(hlist_next_rcu(&tb
->tb_hlist
)))) {
2288 tb
= hlist_entry(tb_node
, struct fib_table
, tb_hlist
);
2289 n
= fib_trie_get_first(iter
, (struct trie
*) tb
->tb_data
);
2294 /* new hash chain */
2295 while (++h
< FIB_TABLE_HASHSZ
) {
2296 struct hlist_head
*head
= &net
->ipv4
.fib_table_hash
[h
];
2297 hlist_for_each_entry_rcu(tb
, tb_node
, head
, tb_hlist
) {
2298 n
= fib_trie_get_first(iter
, (struct trie
*) tb
->tb_data
);
2310 static void fib_trie_seq_stop(struct seq_file
*seq
, void *v
)
2316 static void seq_indent(struct seq_file
*seq
, int n
)
2322 static inline const char *rtn_scope(char *buf
, size_t len
, enum rt_scope_t s
)
2325 case RT_SCOPE_UNIVERSE
: return "universe";
2326 case RT_SCOPE_SITE
: return "site";
2327 case RT_SCOPE_LINK
: return "link";
2328 case RT_SCOPE_HOST
: return "host";
2329 case RT_SCOPE_NOWHERE
: return "nowhere";
2331 snprintf(buf
, len
, "scope=%d", s
);
2336 static const char *const rtn_type_names
[__RTN_MAX
] = {
2337 [RTN_UNSPEC
] = "UNSPEC",
2338 [RTN_UNICAST
] = "UNICAST",
2339 [RTN_LOCAL
] = "LOCAL",
2340 [RTN_BROADCAST
] = "BROADCAST",
2341 [RTN_ANYCAST
] = "ANYCAST",
2342 [RTN_MULTICAST
] = "MULTICAST",
2343 [RTN_BLACKHOLE
] = "BLACKHOLE",
2344 [RTN_UNREACHABLE
] = "UNREACHABLE",
2345 [RTN_PROHIBIT
] = "PROHIBIT",
2346 [RTN_THROW
] = "THROW",
2348 [RTN_XRESOLVE
] = "XRESOLVE",
2351 static inline const char *rtn_type(char *buf
, size_t len
, unsigned int t
)
2353 if (t
< __RTN_MAX
&& rtn_type_names
[t
])
2354 return rtn_type_names
[t
];
2355 snprintf(buf
, len
, "type %u", t
);
2359 /* Pretty print the trie */
2360 static int fib_trie_seq_show(struct seq_file
*seq
, void *v
)
2362 const struct fib_trie_iter
*iter
= seq
->private;
2363 struct rt_trie_node
*n
= v
;
2365 if (!node_parent_rcu(n
))
2366 fib_table_print(seq
, iter
->tb
);
2369 struct tnode
*tn
= (struct tnode
*) n
;
2370 __be32 prf
= htonl(mask_pfx(tn
->key
, tn
->pos
));
2372 seq_indent(seq
, iter
->depth
-1);
2373 seq_printf(seq
, " +-- %pI4/%d %d %d %d\n",
2374 &prf
, tn
->pos
, tn
->bits
, tn
->full_children
,
2375 tn
->empty_children
);
2378 struct leaf
*l
= (struct leaf
*) n
;
2379 struct leaf_info
*li
;
2380 struct hlist_node
*node
;
2381 __be32 val
= htonl(l
->key
);
2383 seq_indent(seq
, iter
->depth
);
2384 seq_printf(seq
, " |-- %pI4\n", &val
);
2386 hlist_for_each_entry_rcu(li
, node
, &l
->list
, hlist
) {
2387 struct fib_alias
*fa
;
2389 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
2390 char buf1
[32], buf2
[32];
2392 seq_indent(seq
, iter
->depth
+1);
2393 seq_printf(seq
, " /%d %s %s", li
->plen
,
2394 rtn_scope(buf1
, sizeof(buf1
),
2395 fa
->fa_info
->fib_scope
),
2396 rtn_type(buf2
, sizeof(buf2
),
2399 seq_printf(seq
, " tos=%d", fa
->fa_tos
);
2400 seq_putc(seq
, '\n');
2408 static const struct seq_operations fib_trie_seq_ops
= {
2409 .start
= fib_trie_seq_start
,
2410 .next
= fib_trie_seq_next
,
2411 .stop
= fib_trie_seq_stop
,
2412 .show
= fib_trie_seq_show
,
2415 static int fib_trie_seq_open(struct inode
*inode
, struct file
*file
)
2417 return seq_open_net(inode
, file
, &fib_trie_seq_ops
,
2418 sizeof(struct fib_trie_iter
));
2421 static const struct file_operations fib_trie_fops
= {
2422 .owner
= THIS_MODULE
,
2423 .open
= fib_trie_seq_open
,
2425 .llseek
= seq_lseek
,
2426 .release
= seq_release_net
,
2429 struct fib_route_iter
{
2430 struct seq_net_private p
;
2431 struct trie
*main_trie
;
2436 static struct leaf
*fib_route_get_idx(struct fib_route_iter
*iter
, loff_t pos
)
2438 struct leaf
*l
= NULL
;
2439 struct trie
*t
= iter
->main_trie
;
2441 /* use cache location of last found key */
2442 if (iter
->pos
> 0 && pos
>= iter
->pos
&& (l
= fib_find_node(t
, iter
->key
)))
2446 l
= trie_firstleaf(t
);
2449 while (l
&& pos
-- > 0) {
2451 l
= trie_nextleaf(l
);
2455 iter
->key
= pos
; /* remember it */
2457 iter
->pos
= 0; /* forget it */
2462 static void *fib_route_seq_start(struct seq_file
*seq
, loff_t
*pos
)
2465 struct fib_route_iter
*iter
= seq
->private;
2466 struct fib_table
*tb
;
2469 tb
= fib_get_table(seq_file_net(seq
), RT_TABLE_MAIN
);
2473 iter
->main_trie
= (struct trie
*) tb
->tb_data
;
2475 return SEQ_START_TOKEN
;
2477 return fib_route_get_idx(iter
, *pos
- 1);
2480 static void *fib_route_seq_next(struct seq_file
*seq
, void *v
, loff_t
*pos
)
2482 struct fib_route_iter
*iter
= seq
->private;
2486 if (v
== SEQ_START_TOKEN
) {
2488 l
= trie_firstleaf(iter
->main_trie
);
2491 l
= trie_nextleaf(l
);
2501 static void fib_route_seq_stop(struct seq_file
*seq
, void *v
)
2507 static unsigned int fib_flag_trans(int type
, __be32 mask
, const struct fib_info
*fi
)
2509 unsigned int flags
= 0;
2511 if (type
== RTN_UNREACHABLE
|| type
== RTN_PROHIBIT
)
2513 if (fi
&& fi
->fib_nh
->nh_gw
)
2514 flags
|= RTF_GATEWAY
;
2515 if (mask
== htonl(0xFFFFFFFF))
2522 * This outputs /proc/net/route.
2523 * The format of the file is not supposed to be changed
2524 * and needs to be same as fib_hash output to avoid breaking
2527 static int fib_route_seq_show(struct seq_file
*seq
, void *v
)
2530 struct leaf_info
*li
;
2531 struct hlist_node
*node
;
2533 if (v
== SEQ_START_TOKEN
) {
2534 seq_printf(seq
, "%-127s\n", "Iface\tDestination\tGateway "
2535 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2540 hlist_for_each_entry_rcu(li
, node
, &l
->list
, hlist
) {
2541 struct fib_alias
*fa
;
2542 __be32 mask
, prefix
;
2544 mask
= inet_make_mask(li
->plen
);
2545 prefix
= htonl(l
->key
);
2547 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
2548 const struct fib_info
*fi
= fa
->fa_info
;
2549 unsigned int flags
= fib_flag_trans(fa
->fa_type
, mask
, fi
);
2552 if (fa
->fa_type
== RTN_BROADCAST
2553 || fa
->fa_type
== RTN_MULTICAST
)
2558 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2559 "%d\t%08X\t%d\t%u\t%u%n",
2560 fi
->fib_dev
? fi
->fib_dev
->name
: "*",
2562 fi
->fib_nh
->nh_gw
, flags
, 0, 0,
2566 fi
->fib_advmss
+ 40 : 0),
2568 fi
->fib_rtt
>> 3, &len
);
2571 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2572 "%d\t%08X\t%d\t%u\t%u%n",
2573 prefix
, 0, flags
, 0, 0, 0,
2574 mask
, 0, 0, 0, &len
);
2576 seq_printf(seq
, "%*s\n", 127 - len
, "");
2583 static const struct seq_operations fib_route_seq_ops
= {
2584 .start
= fib_route_seq_start
,
2585 .next
= fib_route_seq_next
,
2586 .stop
= fib_route_seq_stop
,
2587 .show
= fib_route_seq_show
,
2590 static int fib_route_seq_open(struct inode
*inode
, struct file
*file
)
2592 return seq_open_net(inode
, file
, &fib_route_seq_ops
,
2593 sizeof(struct fib_route_iter
));
2596 static const struct file_operations fib_route_fops
= {
2597 .owner
= THIS_MODULE
,
2598 .open
= fib_route_seq_open
,
2600 .llseek
= seq_lseek
,
2601 .release
= seq_release_net
,
2604 int __net_init
fib_proc_init(struct net
*net
)
2606 if (!proc_net_fops_create(net
, "fib_trie", S_IRUGO
, &fib_trie_fops
))
2609 if (!proc_net_fops_create(net
, "fib_triestat", S_IRUGO
,
2610 &fib_triestat_fops
))
2613 if (!proc_net_fops_create(net
, "route", S_IRUGO
, &fib_route_fops
))
2619 proc_net_remove(net
, "fib_triestat");
2621 proc_net_remove(net
, "fib_trie");
2626 void __net_exit
fib_proc_exit(struct net
*net
)
2628 proc_net_remove(net
, "fib_trie");
2629 proc_net_remove(net
, "fib_triestat");
2630 proc_net_remove(net
, "route");
2633 #endif /* CONFIG_PROC_FS */