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 <linux/bitops.h>
55 #include <linux/types.h>
56 #include <linux/kernel.h>
58 #include <linux/string.h>
59 #include <linux/socket.h>
60 #include <linux/sockios.h>
61 #include <linux/errno.h>
63 #include <linux/inet.h>
64 #include <linux/inetdevice.h>
65 #include <linux/netdevice.h>
66 #include <linux/if_arp.h>
67 #include <linux/proc_fs.h>
68 #include <linux/rcupdate.h>
69 #include <linux/skbuff.h>
70 #include <linux/netlink.h>
71 #include <linux/init.h>
72 #include <linux/list.h>
73 #include <linux/slab.h>
74 #include <linux/export.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
;
113 u32 mask_plen
; /* ntohl(inet_make_mask(plen)) */
114 struct list_head falh
;
119 unsigned long parent
;
121 unsigned char pos
; /* 2log(KEYLENGTH) bits needed */
122 unsigned char bits
; /* 2log(KEYLENGTH) bits needed */
123 unsigned int full_children
; /* KEYLENGTH bits needed */
124 unsigned int empty_children
; /* KEYLENGTH bits needed */
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 tnode_put_child_reorg(struct tnode
*tn
, int i
, struct rt_trie_node
*n
,
162 static struct rt_trie_node
*resize(struct trie
*t
, struct tnode
*tn
);
163 static struct tnode
*inflate(struct trie
*t
, struct tnode
*tn
);
164 static struct tnode
*halve(struct trie
*t
, struct tnode
*tn
);
165 /* tnodes to free after resize(); protected by RTNL */
166 static struct tnode
*tnode_free_head
;
167 static size_t tnode_free_size
;
170 * synchronize_rcu after call_rcu for that many pages; it should be especially
171 * useful before resizing the root node with PREEMPT_NONE configs; the value was
172 * obtained experimentally, aiming to avoid visible slowdown.
174 static const int sync_pages
= 128;
176 static struct kmem_cache
*fn_alias_kmem __read_mostly
;
177 static struct kmem_cache
*trie_leaf_kmem __read_mostly
;
180 * caller must hold RTNL
182 static inline struct tnode
*node_parent(const struct rt_trie_node
*node
)
184 unsigned long parent
;
186 parent
= rcu_dereference_index_check(node
->parent
, lockdep_rtnl_is_held());
188 return (struct tnode
*)(parent
& ~NODE_TYPE_MASK
);
192 * caller must hold RCU read lock or RTNL
194 static inline struct tnode
*node_parent_rcu(const struct rt_trie_node
*node
)
196 unsigned long parent
;
198 parent
= rcu_dereference_index_check(node
->parent
, rcu_read_lock_held() ||
199 lockdep_rtnl_is_held());
201 return (struct tnode
*)(parent
& ~NODE_TYPE_MASK
);
204 /* Same as rcu_assign_pointer
205 * but that macro() assumes that value is a pointer.
207 static inline void node_set_parent(struct rt_trie_node
*node
, struct tnode
*ptr
)
210 node
->parent
= (unsigned long)ptr
| NODE_TYPE(node
);
214 * caller must hold RTNL
216 static inline struct rt_trie_node
*tnode_get_child(const struct tnode
*tn
, unsigned int i
)
218 BUG_ON(i
>= 1U << tn
->bits
);
220 return rtnl_dereference(tn
->child
[i
]);
224 * caller must hold RCU read lock or RTNL
226 static inline struct rt_trie_node
*tnode_get_child_rcu(const struct tnode
*tn
, unsigned int i
)
228 BUG_ON(i
>= 1U << tn
->bits
);
230 return rcu_dereference_rtnl(tn
->child
[i
]);
233 static inline int tnode_child_length(const struct tnode
*tn
)
235 return 1 << tn
->bits
;
238 static inline t_key
mask_pfx(t_key k
, unsigned int l
)
240 return (l
== 0) ? 0 : k
>> (KEYLENGTH
-l
) << (KEYLENGTH
-l
);
243 static inline t_key
tkey_extract_bits(t_key a
, unsigned int offset
, unsigned int bits
)
245 if (offset
< KEYLENGTH
)
246 return ((t_key
)(a
<< offset
)) >> (KEYLENGTH
- bits
);
251 static inline int tkey_equals(t_key a
, t_key b
)
256 static inline int tkey_sub_equals(t_key a
, int offset
, int bits
, t_key b
)
258 if (bits
== 0 || offset
>= KEYLENGTH
)
260 bits
= bits
> KEYLENGTH
? KEYLENGTH
: bits
;
261 return ((a
^ b
) << offset
) >> (KEYLENGTH
- bits
) == 0;
264 static inline int tkey_mismatch(t_key a
, int offset
, t_key b
)
271 while ((diff
<< i
) >> (KEYLENGTH
-1) == 0)
277 To understand this stuff, an understanding of keys and all their bits is
278 necessary. Every node in the trie has a key associated with it, but not
279 all of the bits in that key are significant.
281 Consider a node 'n' and its parent 'tp'.
283 If n is a leaf, every bit in its key is significant. Its presence is
284 necessitated by path compression, since during a tree traversal (when
285 searching for a leaf - unless we are doing an insertion) we will completely
286 ignore all skipped bits we encounter. Thus we need to verify, at the end of
287 a potentially successful search, that we have indeed been walking the
290 Note that we can never "miss" the correct key in the tree if present by
291 following the wrong path. Path compression ensures that segments of the key
292 that are the same for all keys with a given prefix are skipped, but the
293 skipped part *is* identical for each node in the subtrie below the skipped
294 bit! trie_insert() in this implementation takes care of that - note the
295 call to tkey_sub_equals() in trie_insert().
297 if n is an internal node - a 'tnode' here, the various parts of its key
298 have many different meanings.
301 _________________________________________________________________
302 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
303 -----------------------------------------------------------------
304 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
306 _________________________________________________________________
307 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
308 -----------------------------------------------------------------
309 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
316 First, let's just ignore the bits that come before the parent tp, that is
317 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
318 not use them for anything.
320 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
321 index into the parent's child array. That is, they will be used to find
322 'n' among tp's children.
324 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
327 All the bits we have seen so far are significant to the node n. The rest
328 of the bits are really not needed or indeed known in n->key.
330 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
331 n's child array, and will of course be different for each child.
334 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
339 static inline void check_tnode(const struct tnode
*tn
)
341 WARN_ON(tn
&& tn
->pos
+tn
->bits
> 32);
344 static const int halve_threshold
= 25;
345 static const int inflate_threshold
= 50;
346 static const int halve_threshold_root
= 15;
347 static const int inflate_threshold_root
= 30;
349 static void __alias_free_mem(struct rcu_head
*head
)
351 struct fib_alias
*fa
= container_of(head
, struct fib_alias
, rcu
);
352 kmem_cache_free(fn_alias_kmem
, fa
);
355 static inline void alias_free_mem_rcu(struct fib_alias
*fa
)
357 call_rcu(&fa
->rcu
, __alias_free_mem
);
360 static void __leaf_free_rcu(struct rcu_head
*head
)
362 struct leaf
*l
= container_of(head
, struct leaf
, rcu
);
363 kmem_cache_free(trie_leaf_kmem
, l
);
366 static inline void free_leaf(struct leaf
*l
)
368 call_rcu(&l
->rcu
, __leaf_free_rcu
);
371 static inline void free_leaf_info(struct leaf_info
*leaf
)
373 kfree_rcu(leaf
, rcu
);
376 static struct tnode
*tnode_alloc(size_t size
)
378 if (size
<= PAGE_SIZE
)
379 return kzalloc(size
, GFP_KERNEL
);
381 return vzalloc(size
);
384 static void __tnode_free_rcu(struct rcu_head
*head
)
386 struct tnode
*tn
= container_of(head
, struct tnode
, rcu
);
387 size_t size
= sizeof(struct tnode
) +
388 (sizeof(struct rt_trie_node
*) << tn
->bits
);
390 if (size
<= PAGE_SIZE
)
396 static inline void tnode_free(struct tnode
*tn
)
399 free_leaf((struct leaf
*) tn
);
401 call_rcu(&tn
->rcu
, __tnode_free_rcu
);
404 static void tnode_free_safe(struct tnode
*tn
)
407 tn
->tnode_free
= tnode_free_head
;
408 tnode_free_head
= tn
;
409 tnode_free_size
+= sizeof(struct tnode
) +
410 (sizeof(struct rt_trie_node
*) << tn
->bits
);
413 static void tnode_free_flush(void)
417 while ((tn
= tnode_free_head
)) {
418 tnode_free_head
= tn
->tnode_free
;
419 tn
->tnode_free
= NULL
;
423 if (tnode_free_size
>= PAGE_SIZE
* sync_pages
) {
429 static struct leaf
*leaf_new(void)
431 struct leaf
*l
= kmem_cache_alloc(trie_leaf_kmem
, GFP_KERNEL
);
434 INIT_HLIST_HEAD(&l
->list
);
439 static struct leaf_info
*leaf_info_new(int plen
)
441 struct leaf_info
*li
= kmalloc(sizeof(struct leaf_info
), GFP_KERNEL
);
444 li
->mask_plen
= ntohl(inet_make_mask(plen
));
445 INIT_LIST_HEAD(&li
->falh
);
450 static struct tnode
*tnode_new(t_key key
, int pos
, int bits
)
452 size_t sz
= sizeof(struct tnode
) + (sizeof(struct rt_trie_node
*) << bits
);
453 struct tnode
*tn
= tnode_alloc(sz
);
456 tn
->parent
= T_TNODE
;
460 tn
->full_children
= 0;
461 tn
->empty_children
= 1<<bits
;
464 pr_debug("AT %p s=%zu %zu\n", tn
, sizeof(struct tnode
),
465 sizeof(struct rt_trie_node
*) << bits
);
470 * Check whether a tnode 'n' is "full", i.e. it is an internal node
471 * and no bits are skipped. See discussion in dyntree paper p. 6
474 static inline int tnode_full(const struct tnode
*tn
, const struct rt_trie_node
*n
)
476 if (n
== NULL
|| IS_LEAF(n
))
479 return ((struct tnode
*) n
)->pos
== tn
->pos
+ tn
->bits
;
482 static inline void put_child(struct tnode
*tn
, int i
,
483 struct rt_trie_node
*n
)
485 tnode_put_child_reorg(tn
, i
, n
, -1);
489 * Add a child at position i overwriting the old value.
490 * Update the value of full_children and empty_children.
493 static void tnode_put_child_reorg(struct tnode
*tn
, int i
, struct rt_trie_node
*n
,
496 struct rt_trie_node
*chi
= rtnl_dereference(tn
->child
[i
]);
499 BUG_ON(i
>= 1<<tn
->bits
);
501 /* update emptyChildren */
502 if (n
== NULL
&& chi
!= NULL
)
503 tn
->empty_children
++;
504 else if (n
!= NULL
&& chi
== NULL
)
505 tn
->empty_children
--;
507 /* update fullChildren */
509 wasfull
= tnode_full(tn
, chi
);
511 isfull
= tnode_full(tn
, n
);
512 if (wasfull
&& !isfull
)
514 else if (!wasfull
&& isfull
)
518 node_set_parent(n
, tn
);
520 rcu_assign_pointer(tn
->child
[i
], n
);
524 static struct rt_trie_node
*resize(struct trie
*t
, struct tnode
*tn
)
527 struct tnode
*old_tn
;
528 int inflate_threshold_use
;
529 int halve_threshold_use
;
535 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
536 tn
, inflate_threshold
, halve_threshold
);
539 if (tn
->empty_children
== tnode_child_length(tn
)) {
544 if (tn
->empty_children
== tnode_child_length(tn
) - 1)
547 * Double as long as the resulting node has a number of
548 * nonempty nodes that are above the threshold.
552 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
553 * the Helsinki University of Technology and Matti Tikkanen of Nokia
554 * Telecommunications, page 6:
555 * "A node is doubled if the ratio of non-empty children to all
556 * children in the *doubled* node is at least 'high'."
558 * 'high' in this instance is the variable 'inflate_threshold'. It
559 * is expressed as a percentage, so we multiply it with
560 * tnode_child_length() and instead of multiplying by 2 (since the
561 * child array will be doubled by inflate()) and multiplying
562 * the left-hand side by 100 (to handle the percentage thing) we
563 * multiply the left-hand side by 50.
565 * The left-hand side may look a bit weird: tnode_child_length(tn)
566 * - tn->empty_children is of course the number of non-null children
567 * in the current node. tn->full_children is the number of "full"
568 * children, that is non-null tnodes with a skip value of 0.
569 * All of those will be doubled in the resulting inflated tnode, so
570 * we just count them one extra time here.
572 * A clearer way to write this would be:
574 * to_be_doubled = tn->full_children;
575 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
578 * new_child_length = tnode_child_length(tn) * 2;
580 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
582 * if (new_fill_factor >= inflate_threshold)
584 * ...and so on, tho it would mess up the while () loop.
587 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
591 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
592 * inflate_threshold * new_child_length
594 * expand not_to_be_doubled and to_be_doubled, and shorten:
595 * 100 * (tnode_child_length(tn) - tn->empty_children +
596 * tn->full_children) >= inflate_threshold * new_child_length
598 * expand new_child_length:
599 * 100 * (tnode_child_length(tn) - tn->empty_children +
600 * tn->full_children) >=
601 * inflate_threshold * tnode_child_length(tn) * 2
604 * 50 * (tn->full_children + tnode_child_length(tn) -
605 * tn->empty_children) >= inflate_threshold *
606 * tnode_child_length(tn)
612 /* Keep root node larger */
614 if (!node_parent((struct rt_trie_node
*)tn
)) {
615 inflate_threshold_use
= inflate_threshold_root
;
616 halve_threshold_use
= halve_threshold_root
;
618 inflate_threshold_use
= inflate_threshold
;
619 halve_threshold_use
= halve_threshold
;
623 while ((tn
->full_children
> 0 && max_work
-- &&
624 50 * (tn
->full_children
+ tnode_child_length(tn
)
625 - tn
->empty_children
)
626 >= inflate_threshold_use
* tnode_child_length(tn
))) {
633 #ifdef CONFIG_IP_FIB_TRIE_STATS
634 t
->stats
.resize_node_skipped
++;
642 /* Return if at least one inflate is run */
643 if (max_work
!= MAX_WORK
)
644 return (struct rt_trie_node
*) tn
;
647 * Halve as long as the number of empty children in this
648 * node is above threshold.
652 while (tn
->bits
> 1 && max_work
-- &&
653 100 * (tnode_child_length(tn
) - tn
->empty_children
) <
654 halve_threshold_use
* tnode_child_length(tn
)) {
660 #ifdef CONFIG_IP_FIB_TRIE_STATS
661 t
->stats
.resize_node_skipped
++;
668 /* Only one child remains */
669 if (tn
->empty_children
== tnode_child_length(tn
) - 1) {
671 for (i
= 0; i
< tnode_child_length(tn
); i
++) {
672 struct rt_trie_node
*n
;
674 n
= rtnl_dereference(tn
->child
[i
]);
678 /* compress one level */
680 node_set_parent(n
, NULL
);
685 return (struct rt_trie_node
*) tn
;
689 static void tnode_clean_free(struct tnode
*tn
)
692 struct tnode
*tofree
;
694 for (i
= 0; i
< tnode_child_length(tn
); i
++) {
695 tofree
= (struct tnode
*)rtnl_dereference(tn
->child
[i
]);
702 static struct tnode
*inflate(struct trie
*t
, struct tnode
*tn
)
704 struct tnode
*oldtnode
= tn
;
705 int olen
= tnode_child_length(tn
);
708 pr_debug("In inflate\n");
710 tn
= tnode_new(oldtnode
->key
, oldtnode
->pos
, oldtnode
->bits
+ 1);
713 return ERR_PTR(-ENOMEM
);
716 * Preallocate and store tnodes before the actual work so we
717 * don't get into an inconsistent state if memory allocation
718 * fails. In case of failure we return the oldnode and inflate
719 * of tnode is ignored.
722 for (i
= 0; i
< olen
; i
++) {
725 inode
= (struct tnode
*) tnode_get_child(oldtnode
, i
);
728 inode
->pos
== oldtnode
->pos
+ oldtnode
->bits
&&
730 struct tnode
*left
, *right
;
731 t_key m
= ~0U << (KEYLENGTH
- 1) >> inode
->pos
;
733 left
= tnode_new(inode
->key
&(~m
), inode
->pos
+ 1,
738 right
= tnode_new(inode
->key
|m
, inode
->pos
+ 1,
746 put_child(tn
, 2*i
, (struct rt_trie_node
*) left
);
747 put_child(tn
, 2*i
+1, (struct rt_trie_node
*) right
);
751 for (i
= 0; i
< olen
; i
++) {
753 struct rt_trie_node
*node
= tnode_get_child(oldtnode
, i
);
754 struct tnode
*left
, *right
;
761 /* A leaf or an internal node with skipped bits */
763 if (IS_LEAF(node
) || ((struct tnode
*) node
)->pos
>
764 tn
->pos
+ tn
->bits
- 1) {
766 tkey_extract_bits(node
->key
, oldtnode
->pos
, oldtnode
->bits
+ 1),
771 /* An internal node with two children */
772 inode
= (struct tnode
*) node
;
774 if (inode
->bits
== 1) {
775 put_child(tn
, 2*i
, rtnl_dereference(inode
->child
[0]));
776 put_child(tn
, 2*i
+1, rtnl_dereference(inode
->child
[1]));
778 tnode_free_safe(inode
);
782 /* An internal node with more than two children */
784 /* We will replace this node 'inode' with two new
785 * ones, 'left' and 'right', each with half of the
786 * original children. The two new nodes will have
787 * a position one bit further down the key and this
788 * means that the "significant" part of their keys
789 * (see the discussion near the top of this file)
790 * will differ by one bit, which will be "0" in
791 * left's key and "1" in right's key. Since we are
792 * moving the key position by one step, the bit that
793 * we are moving away from - the bit at position
794 * (inode->pos) - is the one that will differ between
795 * left and right. So... we synthesize that bit in the
797 * The mask 'm' below will be a single "one" bit at
798 * the position (inode->pos)
801 /* Use the old key, but set the new significant
805 left
= (struct tnode
*) tnode_get_child(tn
, 2*i
);
806 put_child(tn
, 2*i
, NULL
);
810 right
= (struct tnode
*) tnode_get_child(tn
, 2*i
+1);
811 put_child(tn
, 2*i
+1, NULL
);
815 size
= tnode_child_length(left
);
816 for (j
= 0; j
< size
; j
++) {
817 put_child(left
, j
, rtnl_dereference(inode
->child
[j
]));
818 put_child(right
, j
, rtnl_dereference(inode
->child
[j
+ size
]));
820 put_child(tn
, 2*i
, resize(t
, left
));
821 put_child(tn
, 2*i
+1, resize(t
, right
));
823 tnode_free_safe(inode
);
825 tnode_free_safe(oldtnode
);
828 tnode_clean_free(tn
);
829 return ERR_PTR(-ENOMEM
);
832 static struct tnode
*halve(struct trie
*t
, struct tnode
*tn
)
834 struct tnode
*oldtnode
= tn
;
835 struct rt_trie_node
*left
, *right
;
837 int olen
= tnode_child_length(tn
);
839 pr_debug("In halve\n");
841 tn
= tnode_new(oldtnode
->key
, oldtnode
->pos
, oldtnode
->bits
- 1);
844 return ERR_PTR(-ENOMEM
);
847 * Preallocate and store tnodes before the actual work so we
848 * don't get into an inconsistent state if memory allocation
849 * fails. In case of failure we return the oldnode and halve
850 * of tnode is ignored.
853 for (i
= 0; i
< olen
; i
+= 2) {
854 left
= tnode_get_child(oldtnode
, i
);
855 right
= tnode_get_child(oldtnode
, i
+1);
857 /* Two nonempty children */
861 newn
= tnode_new(left
->key
, tn
->pos
+ tn
->bits
, 1);
866 put_child(tn
, i
/2, (struct rt_trie_node
*)newn
);
871 for (i
= 0; i
< olen
; i
+= 2) {
872 struct tnode
*newBinNode
;
874 left
= tnode_get_child(oldtnode
, i
);
875 right
= tnode_get_child(oldtnode
, i
+1);
877 /* At least one of the children is empty */
879 if (right
== NULL
) /* Both are empty */
881 put_child(tn
, i
/2, right
);
886 put_child(tn
, i
/2, left
);
890 /* Two nonempty children */
891 newBinNode
= (struct tnode
*) tnode_get_child(tn
, i
/2);
892 put_child(tn
, i
/2, NULL
);
893 put_child(newBinNode
, 0, left
);
894 put_child(newBinNode
, 1, right
);
895 put_child(tn
, i
/2, resize(t
, newBinNode
));
897 tnode_free_safe(oldtnode
);
900 tnode_clean_free(tn
);
901 return ERR_PTR(-ENOMEM
);
904 /* readside must use rcu_read_lock currently dump routines
905 via get_fa_head and dump */
907 static struct leaf_info
*find_leaf_info(struct leaf
*l
, int plen
)
909 struct hlist_head
*head
= &l
->list
;
910 struct leaf_info
*li
;
912 hlist_for_each_entry_rcu(li
, head
, hlist
)
913 if (li
->plen
== plen
)
919 static inline struct list_head
*get_fa_head(struct leaf
*l
, int plen
)
921 struct leaf_info
*li
= find_leaf_info(l
, plen
);
929 static void insert_leaf_info(struct hlist_head
*head
, struct leaf_info
*new)
931 struct leaf_info
*li
= NULL
, *last
= NULL
;
933 if (hlist_empty(head
)) {
934 hlist_add_head_rcu(&new->hlist
, head
);
936 hlist_for_each_entry(li
, head
, hlist
) {
937 if (new->plen
> li
->plen
)
943 hlist_add_after_rcu(&last
->hlist
, &new->hlist
);
945 hlist_add_before_rcu(&new->hlist
, &li
->hlist
);
949 /* rcu_read_lock needs to be hold by caller from readside */
952 fib_find_node(struct trie
*t
, u32 key
)
956 struct rt_trie_node
*n
;
959 n
= rcu_dereference_rtnl(t
->trie
);
961 while (n
!= NULL
&& NODE_TYPE(n
) == T_TNODE
) {
962 tn
= (struct tnode
*) n
;
966 if (tkey_sub_equals(tn
->key
, pos
, tn
->pos
-pos
, key
)) {
967 pos
= tn
->pos
+ tn
->bits
;
968 n
= tnode_get_child_rcu(tn
,
969 tkey_extract_bits(key
,
975 /* Case we have found a leaf. Compare prefixes */
977 if (n
!= NULL
&& IS_LEAF(n
) && tkey_equals(key
, n
->key
))
978 return (struct leaf
*)n
;
983 static void trie_rebalance(struct trie
*t
, struct tnode
*tn
)
991 while (tn
!= NULL
&& (tp
= node_parent((struct rt_trie_node
*)tn
)) != NULL
) {
992 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
993 wasfull
= tnode_full(tp
, tnode_get_child(tp
, cindex
));
994 tn
= (struct tnode
*)resize(t
, tn
);
996 tnode_put_child_reorg(tp
, cindex
,
997 (struct rt_trie_node
*)tn
, wasfull
);
999 tp
= node_parent((struct rt_trie_node
*) tn
);
1001 rcu_assign_pointer(t
->trie
, (struct rt_trie_node
*)tn
);
1009 /* Handle last (top) tnode */
1011 tn
= (struct tnode
*)resize(t
, tn
);
1013 rcu_assign_pointer(t
->trie
, (struct rt_trie_node
*)tn
);
1017 /* only used from updater-side */
1019 static struct list_head
*fib_insert_node(struct trie
*t
, u32 key
, int plen
)
1022 struct tnode
*tp
= NULL
, *tn
= NULL
;
1023 struct rt_trie_node
*n
;
1026 struct list_head
*fa_head
= NULL
;
1027 struct leaf_info
*li
;
1031 n
= rtnl_dereference(t
->trie
);
1033 /* If we point to NULL, stop. Either the tree is empty and we should
1034 * just put a new leaf in if, or we have reached an empty child slot,
1035 * and we should just put our new leaf in that.
1036 * If we point to a T_TNODE, check if it matches our key. Note that
1037 * a T_TNODE might be skipping any number of bits - its 'pos' need
1038 * not be the parent's 'pos'+'bits'!
1040 * If it does match the current key, get pos/bits from it, extract
1041 * the index from our key, push the T_TNODE and walk the tree.
1043 * If it doesn't, we have to replace it with a new T_TNODE.
1045 * If we point to a T_LEAF, it might or might not have the same key
1046 * as we do. If it does, just change the value, update the T_LEAF's
1047 * value, and return it.
1048 * If it doesn't, we need to replace it with a T_TNODE.
1051 while (n
!= NULL
&& NODE_TYPE(n
) == T_TNODE
) {
1052 tn
= (struct tnode
*) n
;
1056 if (tkey_sub_equals(tn
->key
, pos
, tn
->pos
-pos
, key
)) {
1058 pos
= tn
->pos
+ tn
->bits
;
1059 n
= tnode_get_child(tn
,
1060 tkey_extract_bits(key
,
1064 BUG_ON(n
&& node_parent(n
) != tn
);
1070 * n ----> NULL, LEAF or TNODE
1072 * tp is n's (parent) ----> NULL or TNODE
1075 BUG_ON(tp
&& IS_LEAF(tp
));
1077 /* Case 1: n is a leaf. Compare prefixes */
1079 if (n
!= NULL
&& IS_LEAF(n
) && tkey_equals(key
, n
->key
)) {
1080 l
= (struct leaf
*) n
;
1081 li
= leaf_info_new(plen
);
1086 fa_head
= &li
->falh
;
1087 insert_leaf_info(&l
->list
, li
);
1096 li
= leaf_info_new(plen
);
1103 fa_head
= &li
->falh
;
1104 insert_leaf_info(&l
->list
, li
);
1106 if (t
->trie
&& n
== NULL
) {
1107 /* Case 2: n is NULL, and will just insert a new leaf */
1109 node_set_parent((struct rt_trie_node
*)l
, tp
);
1111 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1112 put_child(tp
, cindex
, (struct rt_trie_node
*)l
);
1114 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1116 * Add a new tnode here
1117 * first tnode need some special handling
1121 pos
= tp
? tp
->pos
+tp
->bits
: 0;
1122 newpos
= tkey_mismatch(key
, pos
, n
->key
);
1123 tn
= tnode_new(n
->key
, newpos
, 1);
1126 tn
= tnode_new(key
, newpos
, 1); /* First tnode */
1135 node_set_parent((struct rt_trie_node
*)tn
, tp
);
1137 missbit
= tkey_extract_bits(key
, newpos
, 1);
1138 put_child(tn
, missbit
, (struct rt_trie_node
*)l
);
1139 put_child(tn
, 1-missbit
, n
);
1142 cindex
= tkey_extract_bits(key
, tp
->pos
, tp
->bits
);
1143 put_child(tp
, cindex
, (struct rt_trie_node
*)tn
);
1145 rcu_assign_pointer(t
->trie
, (struct rt_trie_node
*)tn
);
1150 if (tp
&& tp
->pos
+ tp
->bits
> 32)
1151 pr_warn("fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1152 tp
, tp
->pos
, tp
->bits
, key
, plen
);
1154 /* Rebalance the trie */
1156 trie_rebalance(t
, tp
);
1162 * Caller must hold RTNL.
1164 int fib_table_insert(struct fib_table
*tb
, struct fib_config
*cfg
)
1166 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1167 struct fib_alias
*fa
, *new_fa
;
1168 struct list_head
*fa_head
= NULL
;
1169 struct fib_info
*fi
;
1170 int plen
= cfg
->fc_dst_len
;
1171 u8 tos
= cfg
->fc_tos
;
1179 key
= ntohl(cfg
->fc_dst
);
1181 pr_debug("Insert table=%u %08x/%d\n", tb
->tb_id
, key
, plen
);
1183 mask
= ntohl(inet_make_mask(plen
));
1190 fi
= fib_create_info(cfg
);
1196 l
= fib_find_node(t
, key
);
1200 fa_head
= get_fa_head(l
, plen
);
1201 fa
= fib_find_alias(fa_head
, tos
, fi
->fib_priority
);
1204 /* Now fa, if non-NULL, points to the first fib alias
1205 * with the same keys [prefix,tos,priority], if such key already
1206 * exists or to the node before which we will insert new one.
1208 * If fa is NULL, we will need to allocate a new one and
1209 * insert to the head of f.
1211 * If f is NULL, no fib node matched the destination key
1212 * and we need to allocate a new one of those as well.
1215 if (fa
&& fa
->fa_tos
== tos
&&
1216 fa
->fa_info
->fib_priority
== fi
->fib_priority
) {
1217 struct fib_alias
*fa_first
, *fa_match
;
1220 if (cfg
->fc_nlflags
& NLM_F_EXCL
)
1224 * 1. Find exact match for type, scope, fib_info to avoid
1226 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1230 fa
= list_entry(fa
->fa_list
.prev
, struct fib_alias
, fa_list
);
1231 list_for_each_entry_continue(fa
, fa_head
, fa_list
) {
1232 if (fa
->fa_tos
!= tos
)
1234 if (fa
->fa_info
->fib_priority
!= fi
->fib_priority
)
1236 if (fa
->fa_type
== cfg
->fc_type
&&
1237 fa
->fa_info
== fi
) {
1243 if (cfg
->fc_nlflags
& NLM_F_REPLACE
) {
1244 struct fib_info
*fi_drop
;
1254 new_fa
= kmem_cache_alloc(fn_alias_kmem
, GFP_KERNEL
);
1258 fi_drop
= fa
->fa_info
;
1259 new_fa
->fa_tos
= fa
->fa_tos
;
1260 new_fa
->fa_info
= fi
;
1261 new_fa
->fa_type
= cfg
->fc_type
;
1262 state
= fa
->fa_state
;
1263 new_fa
->fa_state
= state
& ~FA_S_ACCESSED
;
1265 list_replace_rcu(&fa
->fa_list
, &new_fa
->fa_list
);
1266 alias_free_mem_rcu(fa
);
1268 fib_release_info(fi_drop
);
1269 if (state
& FA_S_ACCESSED
)
1270 rt_cache_flush(cfg
->fc_nlinfo
.nl_net
);
1271 rtmsg_fib(RTM_NEWROUTE
, htonl(key
), new_fa
, plen
,
1272 tb
->tb_id
, &cfg
->fc_nlinfo
, NLM_F_REPLACE
);
1276 /* Error if we find a perfect match which
1277 * uses the same scope, type, and nexthop
1283 if (!(cfg
->fc_nlflags
& NLM_F_APPEND
))
1287 if (!(cfg
->fc_nlflags
& NLM_F_CREATE
))
1291 new_fa
= kmem_cache_alloc(fn_alias_kmem
, GFP_KERNEL
);
1295 new_fa
->fa_info
= fi
;
1296 new_fa
->fa_tos
= tos
;
1297 new_fa
->fa_type
= cfg
->fc_type
;
1298 new_fa
->fa_state
= 0;
1300 * Insert new entry to the list.
1304 fa_head
= fib_insert_node(t
, key
, plen
);
1305 if (unlikely(!fa_head
)) {
1307 goto out_free_new_fa
;
1312 tb
->tb_num_default
++;
1314 list_add_tail_rcu(&new_fa
->fa_list
,
1315 (fa
? &fa
->fa_list
: fa_head
));
1317 rt_cache_flush(cfg
->fc_nlinfo
.nl_net
);
1318 rtmsg_fib(RTM_NEWROUTE
, htonl(key
), new_fa
, plen
, tb
->tb_id
,
1319 &cfg
->fc_nlinfo
, 0);
1324 kmem_cache_free(fn_alias_kmem
, new_fa
);
1326 fib_release_info(fi
);
1331 /* should be called with rcu_read_lock */
1332 static int check_leaf(struct fib_table
*tb
, struct trie
*t
, struct leaf
*l
,
1333 t_key key
, const struct flowi4
*flp
,
1334 struct fib_result
*res
, int fib_flags
)
1336 struct leaf_info
*li
;
1337 struct hlist_head
*hhead
= &l
->list
;
1339 hlist_for_each_entry_rcu(li
, hhead
, hlist
) {
1340 struct fib_alias
*fa
;
1342 if (l
->key
!= (key
& li
->mask_plen
))
1345 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
1346 struct fib_info
*fi
= fa
->fa_info
;
1349 if (fa
->fa_tos
&& fa
->fa_tos
!= flp
->flowi4_tos
)
1353 if (fa
->fa_info
->fib_scope
< flp
->flowi4_scope
)
1355 fib_alias_accessed(fa
);
1356 err
= fib_props
[fa
->fa_type
].error
;
1358 #ifdef CONFIG_IP_FIB_TRIE_STATS
1359 t
->stats
.semantic_match_passed
++;
1363 if (fi
->fib_flags
& RTNH_F_DEAD
)
1365 for (nhsel
= 0; nhsel
< fi
->fib_nhs
; nhsel
++) {
1366 const struct fib_nh
*nh
= &fi
->fib_nh
[nhsel
];
1368 if (nh
->nh_flags
& RTNH_F_DEAD
)
1370 if (flp
->flowi4_oif
&& flp
->flowi4_oif
!= nh
->nh_oif
)
1373 #ifdef CONFIG_IP_FIB_TRIE_STATS
1374 t
->stats
.semantic_match_passed
++;
1376 res
->prefixlen
= li
->plen
;
1377 res
->nh_sel
= nhsel
;
1378 res
->type
= fa
->fa_type
;
1379 res
->scope
= fa
->fa_info
->fib_scope
;
1382 res
->fa_head
= &li
->falh
;
1383 if (!(fib_flags
& FIB_LOOKUP_NOREF
))
1384 atomic_inc(&fi
->fib_clntref
);
1389 #ifdef CONFIG_IP_FIB_TRIE_STATS
1390 t
->stats
.semantic_match_miss
++;
1397 int fib_table_lookup(struct fib_table
*tb
, const struct flowi4
*flp
,
1398 struct fib_result
*res
, int fib_flags
)
1400 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1402 struct rt_trie_node
*n
;
1404 unsigned int pos
, bits
;
1405 t_key key
= ntohl(flp
->daddr
);
1406 unsigned int chopped_off
;
1408 unsigned int current_prefix_length
= KEYLENGTH
;
1410 t_key pref_mismatch
;
1414 n
= rcu_dereference(t
->trie
);
1418 #ifdef CONFIG_IP_FIB_TRIE_STATS
1424 ret
= check_leaf(tb
, t
, (struct leaf
*)n
, key
, flp
, res
, fib_flags
);
1428 pn
= (struct tnode
*) n
;
1436 cindex
= tkey_extract_bits(mask_pfx(key
, current_prefix_length
),
1439 n
= tnode_get_child_rcu(pn
, cindex
);
1442 #ifdef CONFIG_IP_FIB_TRIE_STATS
1443 t
->stats
.null_node_hit
++;
1449 ret
= check_leaf(tb
, t
, (struct leaf
*)n
, key
, flp
, res
, fib_flags
);
1455 cn
= (struct tnode
*)n
;
1458 * It's a tnode, and we can do some extra checks here if we
1459 * like, to avoid descending into a dead-end branch.
1460 * This tnode is in the parent's child array at index
1461 * key[p_pos..p_pos+p_bits] but potentially with some bits
1462 * chopped off, so in reality the index may be just a
1463 * subprefix, padded with zero at the end.
1464 * We can also take a look at any skipped bits in this
1465 * tnode - everything up to p_pos is supposed to be ok,
1466 * and the non-chopped bits of the index (se previous
1467 * paragraph) are also guaranteed ok, but the rest is
1468 * considered unknown.
1470 * The skipped bits are key[pos+bits..cn->pos].
1473 /* If current_prefix_length < pos+bits, we are already doing
1474 * actual prefix matching, which means everything from
1475 * pos+(bits-chopped_off) onward must be zero along some
1476 * branch of this subtree - otherwise there is *no* valid
1477 * prefix present. Here we can only check the skipped
1478 * bits. Remember, since we have already indexed into the
1479 * parent's child array, we know that the bits we chopped of
1483 /* NOTA BENE: Checking only skipped bits
1484 for the new node here */
1486 if (current_prefix_length
< pos
+bits
) {
1487 if (tkey_extract_bits(cn
->key
, current_prefix_length
,
1488 cn
->pos
- current_prefix_length
)
1494 * If chopped_off=0, the index is fully validated and we
1495 * only need to look at the skipped bits for this, the new,
1496 * tnode. What we actually want to do is to find out if
1497 * these skipped bits match our key perfectly, or if we will
1498 * have to count on finding a matching prefix further down,
1499 * because if we do, we would like to have some way of
1500 * verifying the existence of such a prefix at this point.
1503 /* The only thing we can do at this point is to verify that
1504 * any such matching prefix can indeed be a prefix to our
1505 * key, and if the bits in the node we are inspecting that
1506 * do not match our key are not ZERO, this cannot be true.
1507 * Thus, find out where there is a mismatch (before cn->pos)
1508 * and verify that all the mismatching bits are zero in the
1513 * Note: We aren't very concerned about the piece of
1514 * the key that precede pn->pos+pn->bits, since these
1515 * have already been checked. The bits after cn->pos
1516 * aren't checked since these are by definition
1517 * "unknown" at this point. Thus, what we want to see
1518 * is if we are about to enter the "prefix matching"
1519 * state, and in that case verify that the skipped
1520 * bits that will prevail throughout this subtree are
1521 * zero, as they have to be if we are to find a
1525 pref_mismatch
= mask_pfx(cn
->key
^ key
, cn
->pos
);
1528 * In short: If skipped bits in this node do not match
1529 * the search key, enter the "prefix matching"
1532 if (pref_mismatch
) {
1533 /* fls(x) = __fls(x) + 1 */
1534 int mp
= KEYLENGTH
- __fls(pref_mismatch
) - 1;
1536 if (tkey_extract_bits(cn
->key
, mp
, cn
->pos
- mp
) != 0)
1539 if (current_prefix_length
>= cn
->pos
)
1540 current_prefix_length
= mp
;
1543 pn
= (struct tnode
*)n
; /* Descend */
1550 /* As zero don't change the child key (cindex) */
1551 while ((chopped_off
<= pn
->bits
)
1552 && !(cindex
& (1<<(chopped_off
-1))))
1555 /* Decrease current_... with bits chopped off */
1556 if (current_prefix_length
> pn
->pos
+ pn
->bits
- chopped_off
)
1557 current_prefix_length
= pn
->pos
+ pn
->bits
1561 * Either we do the actual chop off according or if we have
1562 * chopped off all bits in this tnode walk up to our parent.
1565 if (chopped_off
<= pn
->bits
) {
1566 cindex
&= ~(1 << (chopped_off
-1));
1568 struct tnode
*parent
= node_parent_rcu((struct rt_trie_node
*) pn
);
1572 /* Get Child's index */
1573 cindex
= tkey_extract_bits(pn
->key
, parent
->pos
, parent
->bits
);
1577 #ifdef CONFIG_IP_FIB_TRIE_STATS
1578 t
->stats
.backtrack
++;
1589 EXPORT_SYMBOL_GPL(fib_table_lookup
);
1592 * Remove the leaf and return parent.
1594 static void trie_leaf_remove(struct trie
*t
, struct leaf
*l
)
1596 struct tnode
*tp
= node_parent((struct rt_trie_node
*) l
);
1598 pr_debug("entering trie_leaf_remove(%p)\n", l
);
1601 t_key cindex
= tkey_extract_bits(l
->key
, tp
->pos
, tp
->bits
);
1602 put_child(tp
, cindex
, NULL
);
1603 trie_rebalance(t
, tp
);
1605 RCU_INIT_POINTER(t
->trie
, NULL
);
1611 * Caller must hold RTNL.
1613 int fib_table_delete(struct fib_table
*tb
, struct fib_config
*cfg
)
1615 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1617 int plen
= cfg
->fc_dst_len
;
1618 u8 tos
= cfg
->fc_tos
;
1619 struct fib_alias
*fa
, *fa_to_delete
;
1620 struct list_head
*fa_head
;
1622 struct leaf_info
*li
;
1627 key
= ntohl(cfg
->fc_dst
);
1628 mask
= ntohl(inet_make_mask(plen
));
1634 l
= fib_find_node(t
, key
);
1639 li
= find_leaf_info(l
, plen
);
1644 fa_head
= &li
->falh
;
1645 fa
= fib_find_alias(fa_head
, tos
, 0);
1650 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key
, plen
, tos
, t
);
1652 fa_to_delete
= NULL
;
1653 fa
= list_entry(fa
->fa_list
.prev
, struct fib_alias
, fa_list
);
1654 list_for_each_entry_continue(fa
, fa_head
, fa_list
) {
1655 struct fib_info
*fi
= fa
->fa_info
;
1657 if (fa
->fa_tos
!= tos
)
1660 if ((!cfg
->fc_type
|| fa
->fa_type
== cfg
->fc_type
) &&
1661 (cfg
->fc_scope
== RT_SCOPE_NOWHERE
||
1662 fa
->fa_info
->fib_scope
== cfg
->fc_scope
) &&
1663 (!cfg
->fc_prefsrc
||
1664 fi
->fib_prefsrc
== cfg
->fc_prefsrc
) &&
1665 (!cfg
->fc_protocol
||
1666 fi
->fib_protocol
== cfg
->fc_protocol
) &&
1667 fib_nh_match(cfg
, fi
) == 0) {
1677 rtmsg_fib(RTM_DELROUTE
, htonl(key
), fa
, plen
, tb
->tb_id
,
1678 &cfg
->fc_nlinfo
, 0);
1680 list_del_rcu(&fa
->fa_list
);
1683 tb
->tb_num_default
--;
1685 if (list_empty(fa_head
)) {
1686 hlist_del_rcu(&li
->hlist
);
1690 if (hlist_empty(&l
->list
))
1691 trie_leaf_remove(t
, l
);
1693 if (fa
->fa_state
& FA_S_ACCESSED
)
1694 rt_cache_flush(cfg
->fc_nlinfo
.nl_net
);
1696 fib_release_info(fa
->fa_info
);
1697 alias_free_mem_rcu(fa
);
1701 static int trie_flush_list(struct list_head
*head
)
1703 struct fib_alias
*fa
, *fa_node
;
1706 list_for_each_entry_safe(fa
, fa_node
, head
, fa_list
) {
1707 struct fib_info
*fi
= fa
->fa_info
;
1709 if (fi
&& (fi
->fib_flags
& RTNH_F_DEAD
)) {
1710 list_del_rcu(&fa
->fa_list
);
1711 fib_release_info(fa
->fa_info
);
1712 alias_free_mem_rcu(fa
);
1719 static int trie_flush_leaf(struct leaf
*l
)
1722 struct hlist_head
*lih
= &l
->list
;
1723 struct hlist_node
*tmp
;
1724 struct leaf_info
*li
= NULL
;
1726 hlist_for_each_entry_safe(li
, tmp
, lih
, hlist
) {
1727 found
+= trie_flush_list(&li
->falh
);
1729 if (list_empty(&li
->falh
)) {
1730 hlist_del_rcu(&li
->hlist
);
1738 * Scan for the next right leaf starting at node p->child[idx]
1739 * Since we have back pointer, no recursion necessary.
1741 static struct leaf
*leaf_walk_rcu(struct tnode
*p
, struct rt_trie_node
*c
)
1747 idx
= tkey_extract_bits(c
->key
, p
->pos
, p
->bits
) + 1;
1751 while (idx
< 1u << p
->bits
) {
1752 c
= tnode_get_child_rcu(p
, idx
++);
1757 return (struct leaf
*) c
;
1759 /* Rescan start scanning in new node */
1760 p
= (struct tnode
*) c
;
1764 /* Node empty, walk back up to parent */
1765 c
= (struct rt_trie_node
*) p
;
1766 } while ((p
= node_parent_rcu(c
)) != NULL
);
1768 return NULL
; /* Root of trie */
1771 static struct leaf
*trie_firstleaf(struct trie
*t
)
1773 struct tnode
*n
= (struct tnode
*)rcu_dereference_rtnl(t
->trie
);
1778 if (IS_LEAF(n
)) /* trie is just a leaf */
1779 return (struct leaf
*) n
;
1781 return leaf_walk_rcu(n
, NULL
);
1784 static struct leaf
*trie_nextleaf(struct leaf
*l
)
1786 struct rt_trie_node
*c
= (struct rt_trie_node
*) l
;
1787 struct tnode
*p
= node_parent_rcu(c
);
1790 return NULL
; /* trie with just one leaf */
1792 return leaf_walk_rcu(p
, c
);
1795 static struct leaf
*trie_leafindex(struct trie
*t
, int index
)
1797 struct leaf
*l
= trie_firstleaf(t
);
1799 while (l
&& index
-- > 0)
1800 l
= trie_nextleaf(l
);
1807 * Caller must hold RTNL.
1809 int fib_table_flush(struct fib_table
*tb
)
1811 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1812 struct leaf
*l
, *ll
= NULL
;
1815 for (l
= trie_firstleaf(t
); l
; l
= trie_nextleaf(l
)) {
1816 found
+= trie_flush_leaf(l
);
1818 if (ll
&& hlist_empty(&ll
->list
))
1819 trie_leaf_remove(t
, ll
);
1823 if (ll
&& hlist_empty(&ll
->list
))
1824 trie_leaf_remove(t
, ll
);
1826 pr_debug("trie_flush found=%d\n", found
);
1830 void fib_free_table(struct fib_table
*tb
)
1835 static int fn_trie_dump_fa(t_key key
, int plen
, struct list_head
*fah
,
1836 struct fib_table
*tb
,
1837 struct sk_buff
*skb
, struct netlink_callback
*cb
)
1840 struct fib_alias
*fa
;
1841 __be32 xkey
= htonl(key
);
1846 /* rcu_read_lock is hold by caller */
1848 list_for_each_entry_rcu(fa
, fah
, fa_list
) {
1854 if (fib_dump_info(skb
, NETLINK_CB(cb
->skb
).portid
,
1862 fa
->fa_info
, NLM_F_MULTI
) < 0) {
1872 static int fn_trie_dump_leaf(struct leaf
*l
, struct fib_table
*tb
,
1873 struct sk_buff
*skb
, struct netlink_callback
*cb
)
1875 struct leaf_info
*li
;
1881 /* rcu_read_lock is hold by caller */
1882 hlist_for_each_entry_rcu(li
, &l
->list
, hlist
) {
1891 if (list_empty(&li
->falh
))
1894 if (fn_trie_dump_fa(l
->key
, li
->plen
, &li
->falh
, tb
, skb
, cb
) < 0) {
1905 int fib_table_dump(struct fib_table
*tb
, struct sk_buff
*skb
,
1906 struct netlink_callback
*cb
)
1909 struct trie
*t
= (struct trie
*) tb
->tb_data
;
1910 t_key key
= cb
->args
[2];
1911 int count
= cb
->args
[3];
1914 /* Dump starting at last key.
1915 * Note: 0.0.0.0/0 (ie default) is first key.
1918 l
= trie_firstleaf(t
);
1920 /* Normally, continue from last key, but if that is missing
1921 * fallback to using slow rescan
1923 l
= fib_find_node(t
, key
);
1925 l
= trie_leafindex(t
, count
);
1929 cb
->args
[2] = l
->key
;
1930 if (fn_trie_dump_leaf(l
, tb
, skb
, cb
) < 0) {
1931 cb
->args
[3] = count
;
1937 l
= trie_nextleaf(l
);
1938 memset(&cb
->args
[4], 0,
1939 sizeof(cb
->args
) - 4*sizeof(cb
->args
[0]));
1941 cb
->args
[3] = count
;
1947 void __init
fib_trie_init(void)
1949 fn_alias_kmem
= kmem_cache_create("ip_fib_alias",
1950 sizeof(struct fib_alias
),
1951 0, SLAB_PANIC
, NULL
);
1953 trie_leaf_kmem
= kmem_cache_create("ip_fib_trie",
1954 max(sizeof(struct leaf
),
1955 sizeof(struct leaf_info
)),
1956 0, SLAB_PANIC
, NULL
);
1960 struct fib_table
*fib_trie_table(u32 id
)
1962 struct fib_table
*tb
;
1965 tb
= kmalloc(sizeof(struct fib_table
) + sizeof(struct trie
),
1971 tb
->tb_default
= -1;
1972 tb
->tb_num_default
= 0;
1974 t
= (struct trie
*) tb
->tb_data
;
1975 memset(t
, 0, sizeof(*t
));
1980 #ifdef CONFIG_PROC_FS
1981 /* Depth first Trie walk iterator */
1982 struct fib_trie_iter
{
1983 struct seq_net_private p
;
1984 struct fib_table
*tb
;
1985 struct tnode
*tnode
;
1990 static struct rt_trie_node
*fib_trie_get_next(struct fib_trie_iter
*iter
)
1992 struct tnode
*tn
= iter
->tnode
;
1993 unsigned int cindex
= iter
->index
;
1996 /* A single entry routing table */
2000 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2001 iter
->tnode
, iter
->index
, iter
->depth
);
2003 while (cindex
< (1<<tn
->bits
)) {
2004 struct rt_trie_node
*n
= tnode_get_child_rcu(tn
, cindex
);
2009 iter
->index
= cindex
+ 1;
2011 /* push down one level */
2012 iter
->tnode
= (struct tnode
*) n
;
2022 /* Current node exhausted, pop back up */
2023 p
= node_parent_rcu((struct rt_trie_node
*)tn
);
2025 cindex
= tkey_extract_bits(tn
->key
, p
->pos
, p
->bits
)+1;
2035 static struct rt_trie_node
*fib_trie_get_first(struct fib_trie_iter
*iter
,
2038 struct rt_trie_node
*n
;
2043 n
= rcu_dereference(t
->trie
);
2048 iter
->tnode
= (struct tnode
*) n
;
2060 static void trie_collect_stats(struct trie
*t
, struct trie_stat
*s
)
2062 struct rt_trie_node
*n
;
2063 struct fib_trie_iter iter
;
2065 memset(s
, 0, sizeof(*s
));
2068 for (n
= fib_trie_get_first(&iter
, t
); n
; n
= fib_trie_get_next(&iter
)) {
2070 struct leaf
*l
= (struct leaf
*)n
;
2071 struct leaf_info
*li
;
2074 s
->totdepth
+= iter
.depth
;
2075 if (iter
.depth
> s
->maxdepth
)
2076 s
->maxdepth
= iter
.depth
;
2078 hlist_for_each_entry_rcu(li
, &l
->list
, hlist
)
2081 const struct tnode
*tn
= (const struct tnode
*) n
;
2085 if (tn
->bits
< MAX_STAT_DEPTH
)
2086 s
->nodesizes
[tn
->bits
]++;
2088 for (i
= 0; i
< (1<<tn
->bits
); i
++)
2097 * This outputs /proc/net/fib_triestats
2099 static void trie_show_stats(struct seq_file
*seq
, struct trie_stat
*stat
)
2101 unsigned int i
, max
, pointers
, bytes
, avdepth
;
2104 avdepth
= stat
->totdepth
*100 / stat
->leaves
;
2108 seq_printf(seq
, "\tAver depth: %u.%02d\n",
2109 avdepth
/ 100, avdepth
% 100);
2110 seq_printf(seq
, "\tMax depth: %u\n", stat
->maxdepth
);
2112 seq_printf(seq
, "\tLeaves: %u\n", stat
->leaves
);
2113 bytes
= sizeof(struct leaf
) * stat
->leaves
;
2115 seq_printf(seq
, "\tPrefixes: %u\n", stat
->prefixes
);
2116 bytes
+= sizeof(struct leaf_info
) * stat
->prefixes
;
2118 seq_printf(seq
, "\tInternal nodes: %u\n\t", stat
->tnodes
);
2119 bytes
+= sizeof(struct tnode
) * stat
->tnodes
;
2121 max
= MAX_STAT_DEPTH
;
2122 while (max
> 0 && stat
->nodesizes
[max
-1] == 0)
2126 for (i
= 1; i
< max
; i
++)
2127 if (stat
->nodesizes
[i
] != 0) {
2128 seq_printf(seq
, " %u: %u", i
, stat
->nodesizes
[i
]);
2129 pointers
+= (1<<i
) * stat
->nodesizes
[i
];
2131 seq_putc(seq
, '\n');
2132 seq_printf(seq
, "\tPointers: %u\n", pointers
);
2134 bytes
+= sizeof(struct rt_trie_node
*) * pointers
;
2135 seq_printf(seq
, "Null ptrs: %u\n", stat
->nullpointers
);
2136 seq_printf(seq
, "Total size: %u kB\n", (bytes
+ 1023) / 1024);
2139 #ifdef CONFIG_IP_FIB_TRIE_STATS
2140 static void trie_show_usage(struct seq_file
*seq
,
2141 const struct trie_use_stats
*stats
)
2143 seq_printf(seq
, "\nCounters:\n---------\n");
2144 seq_printf(seq
, "gets = %u\n", stats
->gets
);
2145 seq_printf(seq
, "backtracks = %u\n", stats
->backtrack
);
2146 seq_printf(seq
, "semantic match passed = %u\n",
2147 stats
->semantic_match_passed
);
2148 seq_printf(seq
, "semantic match miss = %u\n",
2149 stats
->semantic_match_miss
);
2150 seq_printf(seq
, "null node hit= %u\n", stats
->null_node_hit
);
2151 seq_printf(seq
, "skipped node resize = %u\n\n",
2152 stats
->resize_node_skipped
);
2154 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2156 static void fib_table_print(struct seq_file
*seq
, struct fib_table
*tb
)
2158 if (tb
->tb_id
== RT_TABLE_LOCAL
)
2159 seq_puts(seq
, "Local:\n");
2160 else if (tb
->tb_id
== RT_TABLE_MAIN
)
2161 seq_puts(seq
, "Main:\n");
2163 seq_printf(seq
, "Id %d:\n", tb
->tb_id
);
2167 static int fib_triestat_seq_show(struct seq_file
*seq
, void *v
)
2169 struct net
*net
= (struct net
*)seq
->private;
2173 "Basic info: size of leaf:"
2174 " %Zd bytes, size of tnode: %Zd bytes.\n",
2175 sizeof(struct leaf
), sizeof(struct tnode
));
2177 for (h
= 0; h
< FIB_TABLE_HASHSZ
; h
++) {
2178 struct hlist_head
*head
= &net
->ipv4
.fib_table_hash
[h
];
2179 struct fib_table
*tb
;
2181 hlist_for_each_entry_rcu(tb
, head
, tb_hlist
) {
2182 struct trie
*t
= (struct trie
*) tb
->tb_data
;
2183 struct trie_stat stat
;
2188 fib_table_print(seq
, tb
);
2190 trie_collect_stats(t
, &stat
);
2191 trie_show_stats(seq
, &stat
);
2192 #ifdef CONFIG_IP_FIB_TRIE_STATS
2193 trie_show_usage(seq
, &t
->stats
);
2201 static int fib_triestat_seq_open(struct inode
*inode
, struct file
*file
)
2203 return single_open_net(inode
, file
, fib_triestat_seq_show
);
2206 static const struct file_operations fib_triestat_fops
= {
2207 .owner
= THIS_MODULE
,
2208 .open
= fib_triestat_seq_open
,
2210 .llseek
= seq_lseek
,
2211 .release
= single_release_net
,
2214 static struct rt_trie_node
*fib_trie_get_idx(struct seq_file
*seq
, loff_t pos
)
2216 struct fib_trie_iter
*iter
= seq
->private;
2217 struct net
*net
= seq_file_net(seq
);
2221 for (h
= 0; h
< FIB_TABLE_HASHSZ
; h
++) {
2222 struct hlist_head
*head
= &net
->ipv4
.fib_table_hash
[h
];
2223 struct fib_table
*tb
;
2225 hlist_for_each_entry_rcu(tb
, head
, tb_hlist
) {
2226 struct rt_trie_node
*n
;
2228 for (n
= fib_trie_get_first(iter
,
2229 (struct trie
*) tb
->tb_data
);
2230 n
; n
= fib_trie_get_next(iter
))
2241 static void *fib_trie_seq_start(struct seq_file
*seq
, loff_t
*pos
)
2245 return fib_trie_get_idx(seq
, *pos
);
2248 static void *fib_trie_seq_next(struct seq_file
*seq
, void *v
, loff_t
*pos
)
2250 struct fib_trie_iter
*iter
= seq
->private;
2251 struct net
*net
= seq_file_net(seq
);
2252 struct fib_table
*tb
= iter
->tb
;
2253 struct hlist_node
*tb_node
;
2255 struct rt_trie_node
*n
;
2258 /* next node in same table */
2259 n
= fib_trie_get_next(iter
);
2263 /* walk rest of this hash chain */
2264 h
= tb
->tb_id
& (FIB_TABLE_HASHSZ
- 1);
2265 while ((tb_node
= rcu_dereference(hlist_next_rcu(&tb
->tb_hlist
)))) {
2266 tb
= hlist_entry(tb_node
, struct fib_table
, tb_hlist
);
2267 n
= fib_trie_get_first(iter
, (struct trie
*) tb
->tb_data
);
2272 /* new hash chain */
2273 while (++h
< FIB_TABLE_HASHSZ
) {
2274 struct hlist_head
*head
= &net
->ipv4
.fib_table_hash
[h
];
2275 hlist_for_each_entry_rcu(tb
, head
, tb_hlist
) {
2276 n
= fib_trie_get_first(iter
, (struct trie
*) tb
->tb_data
);
2288 static void fib_trie_seq_stop(struct seq_file
*seq
, void *v
)
2294 static void seq_indent(struct seq_file
*seq
, int n
)
2300 static inline const char *rtn_scope(char *buf
, size_t len
, enum rt_scope_t s
)
2303 case RT_SCOPE_UNIVERSE
: return "universe";
2304 case RT_SCOPE_SITE
: return "site";
2305 case RT_SCOPE_LINK
: return "link";
2306 case RT_SCOPE_HOST
: return "host";
2307 case RT_SCOPE_NOWHERE
: return "nowhere";
2309 snprintf(buf
, len
, "scope=%d", s
);
2314 static const char *const rtn_type_names
[__RTN_MAX
] = {
2315 [RTN_UNSPEC
] = "UNSPEC",
2316 [RTN_UNICAST
] = "UNICAST",
2317 [RTN_LOCAL
] = "LOCAL",
2318 [RTN_BROADCAST
] = "BROADCAST",
2319 [RTN_ANYCAST
] = "ANYCAST",
2320 [RTN_MULTICAST
] = "MULTICAST",
2321 [RTN_BLACKHOLE
] = "BLACKHOLE",
2322 [RTN_UNREACHABLE
] = "UNREACHABLE",
2323 [RTN_PROHIBIT
] = "PROHIBIT",
2324 [RTN_THROW
] = "THROW",
2326 [RTN_XRESOLVE
] = "XRESOLVE",
2329 static inline const char *rtn_type(char *buf
, size_t len
, unsigned int t
)
2331 if (t
< __RTN_MAX
&& rtn_type_names
[t
])
2332 return rtn_type_names
[t
];
2333 snprintf(buf
, len
, "type %u", t
);
2337 /* Pretty print the trie */
2338 static int fib_trie_seq_show(struct seq_file
*seq
, void *v
)
2340 const struct fib_trie_iter
*iter
= seq
->private;
2341 struct rt_trie_node
*n
= v
;
2343 if (!node_parent_rcu(n
))
2344 fib_table_print(seq
, iter
->tb
);
2347 struct tnode
*tn
= (struct tnode
*) n
;
2348 __be32 prf
= htonl(mask_pfx(tn
->key
, tn
->pos
));
2350 seq_indent(seq
, iter
->depth
-1);
2351 seq_printf(seq
, " +-- %pI4/%d %d %d %d\n",
2352 &prf
, tn
->pos
, tn
->bits
, tn
->full_children
,
2353 tn
->empty_children
);
2356 struct leaf
*l
= (struct leaf
*) n
;
2357 struct leaf_info
*li
;
2358 __be32 val
= htonl(l
->key
);
2360 seq_indent(seq
, iter
->depth
);
2361 seq_printf(seq
, " |-- %pI4\n", &val
);
2363 hlist_for_each_entry_rcu(li
, &l
->list
, hlist
) {
2364 struct fib_alias
*fa
;
2366 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
2367 char buf1
[32], buf2
[32];
2369 seq_indent(seq
, iter
->depth
+1);
2370 seq_printf(seq
, " /%d %s %s", li
->plen
,
2371 rtn_scope(buf1
, sizeof(buf1
),
2372 fa
->fa_info
->fib_scope
),
2373 rtn_type(buf2
, sizeof(buf2
),
2376 seq_printf(seq
, " tos=%d", fa
->fa_tos
);
2377 seq_putc(seq
, '\n');
2385 static const struct seq_operations fib_trie_seq_ops
= {
2386 .start
= fib_trie_seq_start
,
2387 .next
= fib_trie_seq_next
,
2388 .stop
= fib_trie_seq_stop
,
2389 .show
= fib_trie_seq_show
,
2392 static int fib_trie_seq_open(struct inode
*inode
, struct file
*file
)
2394 return seq_open_net(inode
, file
, &fib_trie_seq_ops
,
2395 sizeof(struct fib_trie_iter
));
2398 static const struct file_operations fib_trie_fops
= {
2399 .owner
= THIS_MODULE
,
2400 .open
= fib_trie_seq_open
,
2402 .llseek
= seq_lseek
,
2403 .release
= seq_release_net
,
2406 struct fib_route_iter
{
2407 struct seq_net_private p
;
2408 struct trie
*main_trie
;
2413 static struct leaf
*fib_route_get_idx(struct fib_route_iter
*iter
, loff_t pos
)
2415 struct leaf
*l
= NULL
;
2416 struct trie
*t
= iter
->main_trie
;
2418 /* use cache location of last found key */
2419 if (iter
->pos
> 0 && pos
>= iter
->pos
&& (l
= fib_find_node(t
, iter
->key
)))
2423 l
= trie_firstleaf(t
);
2426 while (l
&& pos
-- > 0) {
2428 l
= trie_nextleaf(l
);
2432 iter
->key
= pos
; /* remember it */
2434 iter
->pos
= 0; /* forget it */
2439 static void *fib_route_seq_start(struct seq_file
*seq
, loff_t
*pos
)
2442 struct fib_route_iter
*iter
= seq
->private;
2443 struct fib_table
*tb
;
2446 tb
= fib_get_table(seq_file_net(seq
), RT_TABLE_MAIN
);
2450 iter
->main_trie
= (struct trie
*) tb
->tb_data
;
2452 return SEQ_START_TOKEN
;
2454 return fib_route_get_idx(iter
, *pos
- 1);
2457 static void *fib_route_seq_next(struct seq_file
*seq
, void *v
, loff_t
*pos
)
2459 struct fib_route_iter
*iter
= seq
->private;
2463 if (v
== SEQ_START_TOKEN
) {
2465 l
= trie_firstleaf(iter
->main_trie
);
2468 l
= trie_nextleaf(l
);
2478 static void fib_route_seq_stop(struct seq_file
*seq
, void *v
)
2484 static unsigned int fib_flag_trans(int type
, __be32 mask
, const struct fib_info
*fi
)
2486 unsigned int flags
= 0;
2488 if (type
== RTN_UNREACHABLE
|| type
== RTN_PROHIBIT
)
2490 if (fi
&& fi
->fib_nh
->nh_gw
)
2491 flags
|= RTF_GATEWAY
;
2492 if (mask
== htonl(0xFFFFFFFF))
2499 * This outputs /proc/net/route.
2500 * The format of the file is not supposed to be changed
2501 * and needs to be same as fib_hash output to avoid breaking
2504 static int fib_route_seq_show(struct seq_file
*seq
, void *v
)
2507 struct leaf_info
*li
;
2509 if (v
== SEQ_START_TOKEN
) {
2510 seq_printf(seq
, "%-127s\n", "Iface\tDestination\tGateway "
2511 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2516 hlist_for_each_entry_rcu(li
, &l
->list
, hlist
) {
2517 struct fib_alias
*fa
;
2518 __be32 mask
, prefix
;
2520 mask
= inet_make_mask(li
->plen
);
2521 prefix
= htonl(l
->key
);
2523 list_for_each_entry_rcu(fa
, &li
->falh
, fa_list
) {
2524 const struct fib_info
*fi
= fa
->fa_info
;
2525 unsigned int flags
= fib_flag_trans(fa
->fa_type
, mask
, fi
);
2527 if (fa
->fa_type
== RTN_BROADCAST
2528 || fa
->fa_type
== RTN_MULTICAST
)
2531 seq_setwidth(seq
, 127);
2535 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2536 "%d\t%08X\t%d\t%u\t%u",
2537 fi
->fib_dev
? fi
->fib_dev
->name
: "*",
2539 fi
->fib_nh
->nh_gw
, flags
, 0, 0,
2543 fi
->fib_advmss
+ 40 : 0),
2548 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2549 "%d\t%08X\t%d\t%u\t%u",
2550 prefix
, 0, flags
, 0, 0, 0,
2560 static const struct seq_operations fib_route_seq_ops
= {
2561 .start
= fib_route_seq_start
,
2562 .next
= fib_route_seq_next
,
2563 .stop
= fib_route_seq_stop
,
2564 .show
= fib_route_seq_show
,
2567 static int fib_route_seq_open(struct inode
*inode
, struct file
*file
)
2569 return seq_open_net(inode
, file
, &fib_route_seq_ops
,
2570 sizeof(struct fib_route_iter
));
2573 static const struct file_operations fib_route_fops
= {
2574 .owner
= THIS_MODULE
,
2575 .open
= fib_route_seq_open
,
2577 .llseek
= seq_lseek
,
2578 .release
= seq_release_net
,
2581 int __net_init
fib_proc_init(struct net
*net
)
2583 if (!proc_create("fib_trie", S_IRUGO
, net
->proc_net
, &fib_trie_fops
))
2586 if (!proc_create("fib_triestat", S_IRUGO
, net
->proc_net
,
2587 &fib_triestat_fops
))
2590 if (!proc_create("route", S_IRUGO
, net
->proc_net
, &fib_route_fops
))
2596 remove_proc_entry("fib_triestat", net
->proc_net
);
2598 remove_proc_entry("fib_trie", net
->proc_net
);
2603 void __net_exit
fib_proc_exit(struct net
*net
)
2605 remove_proc_entry("fib_trie", net
->proc_net
);
2606 remove_proc_entry("fib_triestat", net
->proc_net
);
2607 remove_proc_entry("route", net
->proc_net
);
2610 #endif /* CONFIG_PROC_FS */