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 __percpu *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 this_cpu_inc(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 this_cpu_inc(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_behind_rcu(&new->hlist, &last->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);
1151 if (tp && tp->pos + tp->bits > 32)
1152 pr_warn("fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1153 tp, tp->pos, tp->bits, key, plen);
1155 /* Rebalance the trie */
1157 trie_rebalance(t, tp);
1163 * Caller must hold RTNL.
1165 int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
1167 struct trie *t = (struct trie *) tb->tb_data;
1168 struct fib_alias *fa, *new_fa;
1169 struct list_head *fa_head = NULL;
1170 struct fib_info *fi;
1171 int plen = cfg->fc_dst_len;
1172 u8 tos = cfg->fc_tos;
1180 key = ntohl(cfg->fc_dst);
1182 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1184 mask = ntohl(inet_make_mask(plen));
1191 fi = fib_create_info(cfg);
1197 l = fib_find_node(t, key);
1201 fa_head = get_fa_head(l, plen);
1202 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1205 /* Now fa, if non-NULL, points to the first fib alias
1206 * with the same keys [prefix,tos,priority], if such key already
1207 * exists or to the node before which we will insert new one.
1209 * If fa is NULL, we will need to allocate a new one and
1210 * insert to the head of f.
1212 * If f is NULL, no fib node matched the destination key
1213 * and we need to allocate a new one of those as well.
1216 if (fa && fa->fa_tos == tos &&
1217 fa->fa_info->fib_priority == fi->fib_priority) {
1218 struct fib_alias *fa_first, *fa_match;
1221 if (cfg->fc_nlflags & NLM_F_EXCL)
1225 * 1. Find exact match for type, scope, fib_info to avoid
1227 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1231 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1232 list_for_each_entry_continue(fa, fa_head, fa_list) {
1233 if (fa->fa_tos != tos)
1235 if (fa->fa_info->fib_priority != fi->fib_priority)
1237 if (fa->fa_type == cfg->fc_type &&
1238 fa->fa_info == fi) {
1244 if (cfg->fc_nlflags & NLM_F_REPLACE) {
1245 struct fib_info *fi_drop;
1255 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1259 fi_drop = fa->fa_info;
1260 new_fa->fa_tos = fa->fa_tos;
1261 new_fa->fa_info = fi;
1262 new_fa->fa_type = cfg->fc_type;
1263 state = fa->fa_state;
1264 new_fa->fa_state = state & ~FA_S_ACCESSED;
1266 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1267 alias_free_mem_rcu(fa);
1269 fib_release_info(fi_drop);
1270 if (state & FA_S_ACCESSED)
1271 rt_cache_flush(cfg->fc_nlinfo.nl_net);
1272 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1273 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1277 /* Error if we find a perfect match which
1278 * uses the same scope, type, and nexthop
1284 if (!(cfg->fc_nlflags & NLM_F_APPEND))
1288 if (!(cfg->fc_nlflags & NLM_F_CREATE))
1292 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1296 new_fa->fa_info = fi;
1297 new_fa->fa_tos = tos;
1298 new_fa->fa_type = cfg->fc_type;
1299 new_fa->fa_state = 0;
1301 * Insert new entry to the list.
1305 fa_head = fib_insert_node(t, key, plen);
1306 if (unlikely(!fa_head)) {
1308 goto out_free_new_fa;
1313 tb->tb_num_default++;
1315 list_add_tail_rcu(&new_fa->fa_list,
1316 (fa ? &fa->fa_list : fa_head));
1318 rt_cache_flush(cfg->fc_nlinfo.nl_net);
1319 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1320 &cfg->fc_nlinfo, 0);
1325 kmem_cache_free(fn_alias_kmem, new_fa);
1327 fib_release_info(fi);
1332 /* should be called with rcu_read_lock */
1333 static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
1334 t_key key, const struct flowi4 *flp,
1335 struct fib_result *res, int fib_flags)
1337 struct leaf_info *li;
1338 struct hlist_head *hhead = &l->list;
1340 hlist_for_each_entry_rcu(li, hhead, hlist) {
1341 struct fib_alias *fa;
1343 if (l->key != (key & li->mask_plen))
1346 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
1347 struct fib_info *fi = fa->fa_info;
1350 if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1354 if (fa->fa_info->fib_scope < flp->flowi4_scope)
1356 fib_alias_accessed(fa);
1357 err = fib_props[fa->fa_type].error;
1359 #ifdef CONFIG_IP_FIB_TRIE_STATS
1360 this_cpu_inc(t->stats->semantic_match_passed);
1364 if (fi->fib_flags & RTNH_F_DEAD)
1366 for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
1367 const struct fib_nh *nh = &fi->fib_nh[nhsel];
1369 if (nh->nh_flags & RTNH_F_DEAD)
1371 if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
1374 #ifdef CONFIG_IP_FIB_TRIE_STATS
1375 this_cpu_inc(t->stats->semantic_match_passed);
1377 res->prefixlen = li->plen;
1378 res->nh_sel = nhsel;
1379 res->type = fa->fa_type;
1380 res->scope = fa->fa_info->fib_scope;
1383 res->fa_head = &li->falh;
1384 if (!(fib_flags & FIB_LOOKUP_NOREF))
1385 atomic_inc(&fi->fib_clntref);
1390 #ifdef CONFIG_IP_FIB_TRIE_STATS
1391 this_cpu_inc(t->stats->semantic_match_miss);
1398 int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
1399 struct fib_result *res, int fib_flags)
1401 struct trie *t = (struct trie *) tb->tb_data;
1402 #ifdef CONFIG_IP_FIB_TRIE_STATS
1403 struct trie_use_stats __percpu *stats = t->stats;
1406 struct rt_trie_node *n;
1408 unsigned int pos, bits;
1409 t_key key = ntohl(flp->daddr);
1410 unsigned int chopped_off;
1412 unsigned int current_prefix_length = KEYLENGTH;
1414 t_key pref_mismatch;
1418 n = rcu_dereference(t->trie);
1422 #ifdef CONFIG_IP_FIB_TRIE_STATS
1423 this_cpu_inc(stats->gets);
1428 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1432 pn = (struct tnode *) n;
1440 cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1443 n = tnode_get_child_rcu(pn, cindex);
1446 #ifdef CONFIG_IP_FIB_TRIE_STATS
1447 this_cpu_inc(stats->null_node_hit);
1453 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1459 cn = (struct tnode *)n;
1462 * It's a tnode, and we can do some extra checks here if we
1463 * like, to avoid descending into a dead-end branch.
1464 * This tnode is in the parent's child array at index
1465 * key[p_pos..p_pos+p_bits] but potentially with some bits
1466 * chopped off, so in reality the index may be just a
1467 * subprefix, padded with zero at the end.
1468 * We can also take a look at any skipped bits in this
1469 * tnode - everything up to p_pos is supposed to be ok,
1470 * and the non-chopped bits of the index (se previous
1471 * paragraph) are also guaranteed ok, but the rest is
1472 * considered unknown.
1474 * The skipped bits are key[pos+bits..cn->pos].
1477 /* If current_prefix_length < pos+bits, we are already doing
1478 * actual prefix matching, which means everything from
1479 * pos+(bits-chopped_off) onward must be zero along some
1480 * branch of this subtree - otherwise there is *no* valid
1481 * prefix present. Here we can only check the skipped
1482 * bits. Remember, since we have already indexed into the
1483 * parent's child array, we know that the bits we chopped of
1487 /* NOTA BENE: Checking only skipped bits
1488 for the new node here */
1490 if (current_prefix_length < pos+bits) {
1491 if (tkey_extract_bits(cn->key, current_prefix_length,
1492 cn->pos - current_prefix_length)
1498 * If chopped_off=0, the index is fully validated and we
1499 * only need to look at the skipped bits for this, the new,
1500 * tnode. What we actually want to do is to find out if
1501 * these skipped bits match our key perfectly, or if we will
1502 * have to count on finding a matching prefix further down,
1503 * because if we do, we would like to have some way of
1504 * verifying the existence of such a prefix at this point.
1507 /* The only thing we can do at this point is to verify that
1508 * any such matching prefix can indeed be a prefix to our
1509 * key, and if the bits in the node we are inspecting that
1510 * do not match our key are not ZERO, this cannot be true.
1511 * Thus, find out where there is a mismatch (before cn->pos)
1512 * and verify that all the mismatching bits are zero in the
1517 * Note: We aren't very concerned about the piece of
1518 * the key that precede pn->pos+pn->bits, since these
1519 * have already been checked. The bits after cn->pos
1520 * aren't checked since these are by definition
1521 * "unknown" at this point. Thus, what we want to see
1522 * is if we are about to enter the "prefix matching"
1523 * state, and in that case verify that the skipped
1524 * bits that will prevail throughout this subtree are
1525 * zero, as they have to be if we are to find a
1529 pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
1532 * In short: If skipped bits in this node do not match
1533 * the search key, enter the "prefix matching"
1536 if (pref_mismatch) {
1537 /* fls(x) = __fls(x) + 1 */
1538 int mp = KEYLENGTH - __fls(pref_mismatch) - 1;
1540 if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
1543 if (current_prefix_length >= cn->pos)
1544 current_prefix_length = mp;
1547 pn = (struct tnode *)n; /* Descend */
1554 /* As zero don't change the child key (cindex) */
1555 while ((chopped_off <= pn->bits)
1556 && !(cindex & (1<<(chopped_off-1))))
1559 /* Decrease current_... with bits chopped off */
1560 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1561 current_prefix_length = pn->pos + pn->bits
1565 * Either we do the actual chop off according or if we have
1566 * chopped off all bits in this tnode walk up to our parent.
1569 if (chopped_off <= pn->bits) {
1570 cindex &= ~(1 << (chopped_off-1));
1572 struct tnode *parent = node_parent_rcu((struct rt_trie_node *) pn);
1576 /* Get Child's index */
1577 cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1581 #ifdef CONFIG_IP_FIB_TRIE_STATS
1582 this_cpu_inc(stats->backtrack);
1593 EXPORT_SYMBOL_GPL(fib_table_lookup);
1596 * Remove the leaf and return parent.
1598 static void trie_leaf_remove(struct trie *t, struct leaf *l)
1600 struct tnode *tp = node_parent((struct rt_trie_node *) l);
1602 pr_debug("entering trie_leaf_remove(%p)\n", l);
1605 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1606 put_child(tp, cindex, NULL);
1607 trie_rebalance(t, tp);
1609 RCU_INIT_POINTER(t->trie, NULL);
1615 * Caller must hold RTNL.
1617 int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
1619 struct trie *t = (struct trie *) tb->tb_data;
1621 int plen = cfg->fc_dst_len;
1622 u8 tos = cfg->fc_tos;
1623 struct fib_alias *fa, *fa_to_delete;
1624 struct list_head *fa_head;
1626 struct leaf_info *li;
1631 key = ntohl(cfg->fc_dst);
1632 mask = ntohl(inet_make_mask(plen));
1638 l = fib_find_node(t, key);
1643 li = find_leaf_info(l, plen);
1648 fa_head = &li->falh;
1649 fa = fib_find_alias(fa_head, tos, 0);
1654 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1656 fa_to_delete = NULL;
1657 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1658 list_for_each_entry_continue(fa, fa_head, fa_list) {
1659 struct fib_info *fi = fa->fa_info;
1661 if (fa->fa_tos != tos)
1664 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1665 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1666 fa->fa_info->fib_scope == cfg->fc_scope) &&
1667 (!cfg->fc_prefsrc ||
1668 fi->fib_prefsrc == cfg->fc_prefsrc) &&
1669 (!cfg->fc_protocol ||
1670 fi->fib_protocol == cfg->fc_protocol) &&
1671 fib_nh_match(cfg, fi) == 0) {
1681 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1682 &cfg->fc_nlinfo, 0);
1684 list_del_rcu(&fa->fa_list);
1687 tb->tb_num_default--;
1689 if (list_empty(fa_head)) {
1690 hlist_del_rcu(&li->hlist);
1694 if (hlist_empty(&l->list))
1695 trie_leaf_remove(t, l);
1697 if (fa->fa_state & FA_S_ACCESSED)
1698 rt_cache_flush(cfg->fc_nlinfo.nl_net);
1700 fib_release_info(fa->fa_info);
1701 alias_free_mem_rcu(fa);
1705 static int trie_flush_list(struct list_head *head)
1707 struct fib_alias *fa, *fa_node;
1710 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1711 struct fib_info *fi = fa->fa_info;
1713 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1714 list_del_rcu(&fa->fa_list);
1715 fib_release_info(fa->fa_info);
1716 alias_free_mem_rcu(fa);
1723 static int trie_flush_leaf(struct leaf *l)
1726 struct hlist_head *lih = &l->list;
1727 struct hlist_node *tmp;
1728 struct leaf_info *li = NULL;
1730 hlist_for_each_entry_safe(li, tmp, lih, hlist) {
1731 found += trie_flush_list(&li->falh);
1733 if (list_empty(&li->falh)) {
1734 hlist_del_rcu(&li->hlist);
1742 * Scan for the next right leaf starting at node p->child[idx]
1743 * Since we have back pointer, no recursion necessary.
1745 static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1751 idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1755 while (idx < 1u << p->bits) {
1756 c = tnode_get_child_rcu(p, idx++);
1761 return (struct leaf *) c;
1763 /* Rescan start scanning in new node */
1764 p = (struct tnode *) c;
1768 /* Node empty, walk back up to parent */
1769 c = (struct rt_trie_node *) p;
1770 } while ((p = node_parent_rcu(c)) != NULL);
1772 return NULL; /* Root of trie */
1775 static struct leaf *trie_firstleaf(struct trie *t)
1777 struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
1782 if (IS_LEAF(n)) /* trie is just a leaf */
1783 return (struct leaf *) n;
1785 return leaf_walk_rcu(n, NULL);
1788 static struct leaf *trie_nextleaf(struct leaf *l)
1790 struct rt_trie_node *c = (struct rt_trie_node *) l;
1791 struct tnode *p = node_parent_rcu(c);
1794 return NULL; /* trie with just one leaf */
1796 return leaf_walk_rcu(p, c);
1799 static struct leaf *trie_leafindex(struct trie *t, int index)
1801 struct leaf *l = trie_firstleaf(t);
1803 while (l && index-- > 0)
1804 l = trie_nextleaf(l);
1811 * Caller must hold RTNL.
1813 int fib_table_flush(struct fib_table *tb)
1815 struct trie *t = (struct trie *) tb->tb_data;
1816 struct leaf *l, *ll = NULL;
1819 for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1820 found += trie_flush_leaf(l);
1822 if (ll && hlist_empty(&ll->list))
1823 trie_leaf_remove(t, ll);
1827 if (ll && hlist_empty(&ll->list))
1828 trie_leaf_remove(t, ll);
1830 pr_debug("trie_flush found=%d\n", found);
1834 void fib_free_table(struct fib_table *tb)
1836 #ifdef CONFIG_IP_FIB_TRIE_STATS
1837 struct trie *t = (struct trie *)tb->tb_data;
1839 free_percpu(t->stats);
1840 #endif /* CONFIG_IP_FIB_TRIE_STATS */
1844 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1845 struct fib_table *tb,
1846 struct sk_buff *skb, struct netlink_callback *cb)
1849 struct fib_alias *fa;
1850 __be32 xkey = htonl(key);
1855 /* rcu_read_lock is hold by caller */
1857 list_for_each_entry_rcu(fa, fah, fa_list) {
1863 if (fib_dump_info(skb, NETLINK_CB(cb->skb).portid,
1871 fa->fa_info, NLM_F_MULTI) < 0) {
1881 static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1882 struct sk_buff *skb, struct netlink_callback *cb)
1884 struct leaf_info *li;
1890 /* rcu_read_lock is hold by caller */
1891 hlist_for_each_entry_rcu(li, &l->list, hlist) {
1900 if (list_empty(&li->falh))
1903 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1914 int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
1915 struct netlink_callback *cb)
1918 struct trie *t = (struct trie *) tb->tb_data;
1919 t_key key = cb->args[2];
1920 int count = cb->args[3];
1923 /* Dump starting at last key.
1924 * Note: 0.0.0.0/0 (ie default) is first key.
1927 l = trie_firstleaf(t);
1929 /* Normally, continue from last key, but if that is missing
1930 * fallback to using slow rescan
1932 l = fib_find_node(t, key);
1934 l = trie_leafindex(t, count);
1938 cb->args[2] = l->key;
1939 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1940 cb->args[3] = count;
1946 l = trie_nextleaf(l);
1947 memset(&cb->args[4], 0,
1948 sizeof(cb->args) - 4*sizeof(cb->args[0]));
1950 cb->args[3] = count;
1956 void __init fib_trie_init(void)
1958 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1959 sizeof(struct fib_alias),
1960 0, SLAB_PANIC, NULL);
1962 trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1963 max(sizeof(struct leaf),
1964 sizeof(struct leaf_info)),
1965 0, SLAB_PANIC, NULL);
1969 struct fib_table *fib_trie_table(u32 id)
1971 struct fib_table *tb;
1974 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1980 tb->tb_default = -1;
1981 tb->tb_num_default = 0;
1983 t = (struct trie *) tb->tb_data;
1984 RCU_INIT_POINTER(t->trie, NULL);
1985 #ifdef CONFIG_IP_FIB_TRIE_STATS
1986 t->stats = alloc_percpu(struct trie_use_stats);
1996 #ifdef CONFIG_PROC_FS
1997 /* Depth first Trie walk iterator */
1998 struct fib_trie_iter {
1999 struct seq_net_private p;
2000 struct fib_table *tb;
2001 struct tnode *tnode;
2006 static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
2008 struct tnode *tn = iter->tnode;
2009 unsigned int cindex = iter->index;
2012 /* A single entry routing table */
2016 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2017 iter->tnode, iter->index, iter->depth);
2019 while (cindex < (1<<tn->bits)) {
2020 struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
2025 iter->index = cindex + 1;
2027 /* push down one level */
2028 iter->tnode = (struct tnode *) n;
2038 /* Current node exhausted, pop back up */
2039 p = node_parent_rcu((struct rt_trie_node *)tn);
2041 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2051 static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
2054 struct rt_trie_node *n;
2059 n = rcu_dereference(t->trie);
2064 iter->tnode = (struct tnode *) n;
2076 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2078 struct rt_trie_node *n;
2079 struct fib_trie_iter iter;
2081 memset(s, 0, sizeof(*s));
2084 for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2086 struct leaf *l = (struct leaf *)n;
2087 struct leaf_info *li;
2090 s->totdepth += iter.depth;
2091 if (iter.depth > s->maxdepth)
2092 s->maxdepth = iter.depth;
2094 hlist_for_each_entry_rcu(li, &l->list, hlist)
2097 const struct tnode *tn = (const struct tnode *) n;
2101 if (tn->bits < MAX_STAT_DEPTH)
2102 s->nodesizes[tn->bits]++;
2104 for (i = 0; i < (1<<tn->bits); i++)
2113 * This outputs /proc/net/fib_triestats
2115 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2117 unsigned int i, max, pointers, bytes, avdepth;
2120 avdepth = stat->totdepth*100 / stat->leaves;
2124 seq_printf(seq, "\tAver depth: %u.%02d\n",
2125 avdepth / 100, avdepth % 100);
2126 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
2128 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
2129 bytes = sizeof(struct leaf) * stat->leaves;
2131 seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes);
2132 bytes += sizeof(struct leaf_info) * stat->prefixes;
2134 seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2135 bytes += sizeof(struct tnode) * stat->tnodes;
2137 max = MAX_STAT_DEPTH;
2138 while (max > 0 && stat->nodesizes[max-1] == 0)
2142 for (i = 1; i < max; i++)
2143 if (stat->nodesizes[i] != 0) {
2144 seq_printf(seq, " %u: %u", i, stat->nodesizes[i]);
2145 pointers += (1<<i) * stat->nodesizes[i];
2147 seq_putc(seq, '\n');
2148 seq_printf(seq, "\tPointers: %u\n", pointers);
2150 bytes += sizeof(struct rt_trie_node *) * pointers;
2151 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2152 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
2155 #ifdef CONFIG_IP_FIB_TRIE_STATS
2156 static void trie_show_usage(struct seq_file *seq,
2157 const struct trie_use_stats __percpu *stats)
2159 struct trie_use_stats s = { 0 };
2162 /* loop through all of the CPUs and gather up the stats */
2163 for_each_possible_cpu(cpu) {
2164 const struct trie_use_stats *pcpu = per_cpu_ptr(stats, cpu);
2166 s.gets += pcpu->gets;
2167 s.backtrack += pcpu->backtrack;
2168 s.semantic_match_passed += pcpu->semantic_match_passed;
2169 s.semantic_match_miss += pcpu->semantic_match_miss;
2170 s.null_node_hit += pcpu->null_node_hit;
2171 s.resize_node_skipped += pcpu->resize_node_skipped;
2174 seq_printf(seq, "\nCounters:\n---------\n");
2175 seq_printf(seq, "gets = %u\n", s.gets);
2176 seq_printf(seq, "backtracks = %u\n", s.backtrack);
2177 seq_printf(seq, "semantic match passed = %u\n",
2178 s.semantic_match_passed);
2179 seq_printf(seq, "semantic match miss = %u\n", s.semantic_match_miss);
2180 seq_printf(seq, "null node hit= %u\n", s.null_node_hit);
2181 seq_printf(seq, "skipped node resize = %u\n\n", s.resize_node_skipped);
2183 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2185 static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2187 if (tb->tb_id == RT_TABLE_LOCAL)
2188 seq_puts(seq, "Local:\n");
2189 else if (tb->tb_id == RT_TABLE_MAIN)
2190 seq_puts(seq, "Main:\n");
2192 seq_printf(seq, "Id %d:\n", tb->tb_id);
2196 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2198 struct net *net = (struct net *)seq->private;
2202 "Basic info: size of leaf:"
2203 " %Zd bytes, size of tnode: %Zd bytes.\n",
2204 sizeof(struct leaf), sizeof(struct tnode));
2206 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2207 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2208 struct fib_table *tb;
2210 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2211 struct trie *t = (struct trie *) tb->tb_data;
2212 struct trie_stat stat;
2217 fib_table_print(seq, tb);
2219 trie_collect_stats(t, &stat);
2220 trie_show_stats(seq, &stat);
2221 #ifdef CONFIG_IP_FIB_TRIE_STATS
2222 trie_show_usage(seq, t->stats);
2230 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2232 return single_open_net(inode, file, fib_triestat_seq_show);
2235 static const struct file_operations fib_triestat_fops = {
2236 .owner = THIS_MODULE,
2237 .open = fib_triestat_seq_open,
2239 .llseek = seq_lseek,
2240 .release = single_release_net,
2243 static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2245 struct fib_trie_iter *iter = seq->private;
2246 struct net *net = seq_file_net(seq);
2250 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2251 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2252 struct fib_table *tb;
2254 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2255 struct rt_trie_node *n;
2257 for (n = fib_trie_get_first(iter,
2258 (struct trie *) tb->tb_data);
2259 n; n = fib_trie_get_next(iter))
2270 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2274 return fib_trie_get_idx(seq, *pos);
2277 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2279 struct fib_trie_iter *iter = seq->private;
2280 struct net *net = seq_file_net(seq);
2281 struct fib_table *tb = iter->tb;
2282 struct hlist_node *tb_node;
2284 struct rt_trie_node *n;
2287 /* next node in same table */
2288 n = fib_trie_get_next(iter);
2292 /* walk rest of this hash chain */
2293 h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2294 while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2295 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2296 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2301 /* new hash chain */
2302 while (++h < FIB_TABLE_HASHSZ) {
2303 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2304 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2305 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2317 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2323 static void seq_indent(struct seq_file *seq, int n)
2329 static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2332 case RT_SCOPE_UNIVERSE: return "universe";
2333 case RT_SCOPE_SITE: return "site";
2334 case RT_SCOPE_LINK: return "link";
2335 case RT_SCOPE_HOST: return "host";
2336 case RT_SCOPE_NOWHERE: return "nowhere";
2338 snprintf(buf, len, "scope=%d", s);
2343 static const char *const rtn_type_names[__RTN_MAX] = {
2344 [RTN_UNSPEC] = "UNSPEC",
2345 [RTN_UNICAST] = "UNICAST",
2346 [RTN_LOCAL] = "LOCAL",
2347 [RTN_BROADCAST] = "BROADCAST",
2348 [RTN_ANYCAST] = "ANYCAST",
2349 [RTN_MULTICAST] = "MULTICAST",
2350 [RTN_BLACKHOLE] = "BLACKHOLE",
2351 [RTN_UNREACHABLE] = "UNREACHABLE",
2352 [RTN_PROHIBIT] = "PROHIBIT",
2353 [RTN_THROW] = "THROW",
2355 [RTN_XRESOLVE] = "XRESOLVE",
2358 static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2360 if (t < __RTN_MAX && rtn_type_names[t])
2361 return rtn_type_names[t];
2362 snprintf(buf, len, "type %u", t);
2366 /* Pretty print the trie */
2367 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2369 const struct fib_trie_iter *iter = seq->private;
2370 struct rt_trie_node *n = v;
2372 if (!node_parent_rcu(n))
2373 fib_table_print(seq, iter->tb);
2376 struct tnode *tn = (struct tnode *) n;
2377 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2379 seq_indent(seq, iter->depth-1);
2380 seq_printf(seq, " +-- %pI4/%d %d %d %d\n",
2381 &prf, tn->pos, tn->bits, tn->full_children,
2382 tn->empty_children);
2385 struct leaf *l = (struct leaf *) n;
2386 struct leaf_info *li;
2387 __be32 val = htonl(l->key);
2389 seq_indent(seq, iter->depth);
2390 seq_printf(seq, " |-- %pI4\n", &val);
2392 hlist_for_each_entry_rcu(li, &l->list, hlist) {
2393 struct fib_alias *fa;
2395 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2396 char buf1[32], buf2[32];
2398 seq_indent(seq, iter->depth+1);
2399 seq_printf(seq, " /%d %s %s", li->plen,
2400 rtn_scope(buf1, sizeof(buf1),
2401 fa->fa_info->fib_scope),
2402 rtn_type(buf2, sizeof(buf2),
2405 seq_printf(seq, " tos=%d", fa->fa_tos);
2406 seq_putc(seq, '\n');
2414 static const struct seq_operations fib_trie_seq_ops = {
2415 .start = fib_trie_seq_start,
2416 .next = fib_trie_seq_next,
2417 .stop = fib_trie_seq_stop,
2418 .show = fib_trie_seq_show,
2421 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2423 return seq_open_net(inode, file, &fib_trie_seq_ops,
2424 sizeof(struct fib_trie_iter));
2427 static const struct file_operations fib_trie_fops = {
2428 .owner = THIS_MODULE,
2429 .open = fib_trie_seq_open,
2431 .llseek = seq_lseek,
2432 .release = seq_release_net,
2435 struct fib_route_iter {
2436 struct seq_net_private p;
2437 struct trie *main_trie;
2442 static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2444 struct leaf *l = NULL;
2445 struct trie *t = iter->main_trie;
2447 /* use cache location of last found key */
2448 if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2452 l = trie_firstleaf(t);
2455 while (l && pos-- > 0) {
2457 l = trie_nextleaf(l);
2461 iter->key = pos; /* remember it */
2463 iter->pos = 0; /* forget it */
2468 static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2471 struct fib_route_iter *iter = seq->private;
2472 struct fib_table *tb;
2475 tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2479 iter->main_trie = (struct trie *) tb->tb_data;
2481 return SEQ_START_TOKEN;
2483 return fib_route_get_idx(iter, *pos - 1);
2486 static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2488 struct fib_route_iter *iter = seq->private;
2492 if (v == SEQ_START_TOKEN) {
2494 l = trie_firstleaf(iter->main_trie);
2497 l = trie_nextleaf(l);
2507 static void fib_route_seq_stop(struct seq_file *seq, void *v)
2513 static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2515 unsigned int flags = 0;
2517 if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
2519 if (fi && fi->fib_nh->nh_gw)
2520 flags |= RTF_GATEWAY;
2521 if (mask == htonl(0xFFFFFFFF))
2528 * This outputs /proc/net/route.
2529 * The format of the file is not supposed to be changed
2530 * and needs to be same as fib_hash output to avoid breaking
2533 static int fib_route_seq_show(struct seq_file *seq, void *v)
2536 struct leaf_info *li;
2538 if (v == SEQ_START_TOKEN) {
2539 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2540 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2545 hlist_for_each_entry_rcu(li, &l->list, hlist) {
2546 struct fib_alias *fa;
2547 __be32 mask, prefix;
2549 mask = inet_make_mask(li->plen);
2550 prefix = htonl(l->key);
2552 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2553 const struct fib_info *fi = fa->fa_info;
2554 unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2556 if (fa->fa_type == RTN_BROADCAST
2557 || fa->fa_type == RTN_MULTICAST)
2560 seq_setwidth(seq, 127);
2564 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2565 "%d\t%08X\t%d\t%u\t%u",
2566 fi->fib_dev ? fi->fib_dev->name : "*",
2568 fi->fib_nh->nh_gw, flags, 0, 0,
2572 fi->fib_advmss + 40 : 0),
2577 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2578 "%d\t%08X\t%d\t%u\t%u",
2579 prefix, 0, flags, 0, 0, 0,
2589 static const struct seq_operations fib_route_seq_ops = {
2590 .start = fib_route_seq_start,
2591 .next = fib_route_seq_next,
2592 .stop = fib_route_seq_stop,
2593 .show = fib_route_seq_show,
2596 static int fib_route_seq_open(struct inode *inode, struct file *file)
2598 return seq_open_net(inode, file, &fib_route_seq_ops,
2599 sizeof(struct fib_route_iter));
2602 static const struct file_operations fib_route_fops = {
2603 .owner = THIS_MODULE,
2604 .open = fib_route_seq_open,
2606 .llseek = seq_lseek,
2607 .release = seq_release_net,
2610 int __net_init fib_proc_init(struct net *net)
2612 if (!proc_create("fib_trie", S_IRUGO, net->proc_net, &fib_trie_fops))
2615 if (!proc_create("fib_triestat", S_IRUGO, net->proc_net,
2616 &fib_triestat_fops))
2619 if (!proc_create("route", S_IRUGO, net->proc_net, &fib_route_fops))
2625 remove_proc_entry("fib_triestat", net->proc_net);
2627 remove_proc_entry("fib_trie", net->proc_net);
2632 void __net_exit fib_proc_exit(struct net *net)
2634 remove_proc_entry("fib_trie", net->proc_net);
2635 remove_proc_entry("fib_triestat", net->proc_net);
2636 remove_proc_entry("route", net->proc_net);
2639 #endif /* CONFIG_PROC_FS */