2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version
5 * 2 of the License, or (at your option) any later version.
7 * Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
8 * & Swedish University of Agricultural Sciences.
10 * Jens Laas <jens.laas@data.slu.se> Swedish University of
11 * Agricultural Sciences.
13 * Hans Liss <hans.liss@its.uu.se> Uppsala Universitet
15 * This work is based on the LPC-trie which is originally described in:
17 * An experimental study of compression methods for dynamic tries
18 * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
19 * http://www.csc.kth.se/~snilsson/software/dyntrie2/
22 * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
23 * IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999
26 * Code from fib_hash has been reused which includes the following header:
29 * INET An implementation of the TCP/IP protocol suite for the LINUX
30 * operating system. INET is implemented using the BSD Socket
31 * interface as the means of communication with the user level.
33 * IPv4 FIB: lookup engine and maintenance routines.
36 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
38 * This program is free software; you can redistribute it and/or
39 * modify it under the terms of the GNU General Public License
40 * as published by the Free Software Foundation; either version
41 * 2 of the License, or (at your option) any later version.
43 * Substantial contributions to this work comes from:
45 * David S. Miller, <davem@davemloft.net>
46 * Stephen Hemminger <shemminger@osdl.org>
47 * Paul E. McKenney <paulmck@us.ibm.com>
48 * Patrick McHardy <kaber@trash.net>
51 #define VERSION "0.409"
53 #include <asm/uaccess.h>
54 #include <asm/system.h>
55 #include <linux/bitops.h>
56 #include <linux/types.h>
57 #include <linux/kernel.h>
59 #include <linux/string.h>
60 #include <linux/socket.h>
61 #include <linux/sockios.h>
62 #include <linux/errno.h>
64 #include <linux/inet.h>
65 #include <linux/inetdevice.h>
66 #include <linux/netdevice.h>
67 #include <linux/if_arp.h>
68 #include <linux/proc_fs.h>
69 #include <linux/rcupdate.h>
70 #include <linux/skbuff.h>
71 #include <linux/netlink.h>
72 #include <linux/init.h>
73 #include <linux/list.h>
74 #include <linux/slab.h>
75 #include <linux/prefetch.h>
76 #include <linux/export.h>
77 #include <net/net_namespace.h>
79 #include <net/protocol.h>
80 #include <net/route.h>
83 #include <net/ip_fib.h>
84 #include "fib_lookup.h"
86 #define MAX_STAT_DEPTH 32
88 #define KEYLENGTH (8*sizeof(t_key))
90 typedef unsigned int t_key;
94 #define NODE_TYPE_MASK 0x1UL
95 #define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
97 #define IS_TNODE(n) (!(n->parent & T_LEAF))
98 #define IS_LEAF(n) (n->parent & T_LEAF)
100 struct rt_trie_node {
101 unsigned long parent;
106 unsigned long parent;
108 struct hlist_head list;
113 struct hlist_node hlist;
115 u32 mask_plen; /* ntohl(inet_make_mask(plen)) */
116 struct list_head falh;
121 unsigned long parent;
123 unsigned char pos; /* 2log(KEYLENGTH) bits needed */
124 unsigned char bits; /* 2log(KEYLENGTH) bits needed */
125 unsigned int full_children; /* KEYLENGTH bits needed */
126 unsigned int empty_children; /* KEYLENGTH bits needed */
129 struct work_struct work;
130 struct tnode *tnode_free;
132 struct rt_trie_node __rcu *child[0];
135 #ifdef CONFIG_IP_FIB_TRIE_STATS
136 struct trie_use_stats {
138 unsigned int backtrack;
139 unsigned int semantic_match_passed;
140 unsigned int semantic_match_miss;
141 unsigned int null_node_hit;
142 unsigned int resize_node_skipped;
147 unsigned int totdepth;
148 unsigned int maxdepth;
151 unsigned int nullpointers;
152 unsigned int prefixes;
153 unsigned int nodesizes[MAX_STAT_DEPTH];
157 struct rt_trie_node __rcu *trie;
158 #ifdef CONFIG_IP_FIB_TRIE_STATS
159 struct trie_use_stats stats;
163 static void put_child(struct trie *t, struct tnode *tn, int i, struct rt_trie_node *n);
164 static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
166 static struct rt_trie_node *resize(struct trie *t, struct tnode *tn);
167 static struct tnode *inflate(struct trie *t, struct tnode *tn);
168 static struct tnode *halve(struct trie *t, struct tnode *tn);
169 /* tnodes to free after resize(); protected by RTNL */
170 static struct tnode *tnode_free_head;
171 static size_t tnode_free_size;
174 * synchronize_rcu after call_rcu for that many pages; it should be especially
175 * useful before resizing the root node with PREEMPT_NONE configs; the value was
176 * obtained experimentally, aiming to avoid visible slowdown.
178 static const int sync_pages = 128;
180 static struct kmem_cache *fn_alias_kmem __read_mostly;
181 static struct kmem_cache *trie_leaf_kmem __read_mostly;
184 * caller must hold RTNL
186 static inline struct tnode *node_parent(const struct rt_trie_node *node)
188 unsigned long parent;
190 parent = rcu_dereference_index_check(node->parent, lockdep_rtnl_is_held());
192 return (struct tnode *)(parent & ~NODE_TYPE_MASK);
196 * caller must hold RCU read lock or RTNL
198 static inline struct tnode *node_parent_rcu(const struct rt_trie_node *node)
200 unsigned long parent;
202 parent = rcu_dereference_index_check(node->parent, rcu_read_lock_held() ||
203 lockdep_rtnl_is_held());
205 return (struct tnode *)(parent & ~NODE_TYPE_MASK);
208 /* Same as rcu_assign_pointer
209 * but that macro() assumes that value is a pointer.
211 static inline void node_set_parent(struct rt_trie_node *node, struct tnode *ptr)
214 node->parent = (unsigned long)ptr | NODE_TYPE(node);
218 * caller must hold RTNL
220 static inline struct rt_trie_node *tnode_get_child(const struct tnode *tn, unsigned int i)
222 BUG_ON(i >= 1U << tn->bits);
224 return rtnl_dereference(tn->child[i]);
228 * caller must hold RCU read lock or RTNL
230 static inline struct rt_trie_node *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
232 BUG_ON(i >= 1U << tn->bits);
234 return rcu_dereference_rtnl(tn->child[i]);
237 static inline int tnode_child_length(const struct tnode *tn)
239 return 1 << tn->bits;
242 static inline t_key mask_pfx(t_key k, unsigned int l)
244 return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
247 static inline t_key tkey_extract_bits(t_key a, unsigned int offset, unsigned int bits)
249 if (offset < KEYLENGTH)
250 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
255 static inline int tkey_equals(t_key a, t_key b)
260 static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
262 if (bits == 0 || offset >= KEYLENGTH)
264 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
265 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
268 static inline int tkey_mismatch(t_key a, int offset, t_key b)
275 while ((diff << i) >> (KEYLENGTH-1) == 0)
281 To understand this stuff, an understanding of keys and all their bits is
282 necessary. Every node in the trie has a key associated with it, but not
283 all of the bits in that key are significant.
285 Consider a node 'n' and its parent 'tp'.
287 If n is a leaf, every bit in its key is significant. Its presence is
288 necessitated by path compression, since during a tree traversal (when
289 searching for a leaf - unless we are doing an insertion) we will completely
290 ignore all skipped bits we encounter. Thus we need to verify, at the end of
291 a potentially successful search, that we have indeed been walking the
294 Note that we can never "miss" the correct key in the tree if present by
295 following the wrong path. Path compression ensures that segments of the key
296 that are the same for all keys with a given prefix are skipped, but the
297 skipped part *is* identical for each node in the subtrie below the skipped
298 bit! trie_insert() in this implementation takes care of that - note the
299 call to tkey_sub_equals() in trie_insert().
301 if n is an internal node - a 'tnode' here, the various parts of its key
302 have many different meanings.
305 _________________________________________________________________
306 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
307 -----------------------------------------------------------------
308 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
310 _________________________________________________________________
311 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
312 -----------------------------------------------------------------
313 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
320 First, let's just ignore the bits that come before the parent tp, that is
321 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
322 not use them for anything.
324 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
325 index into the parent's child array. That is, they will be used to find
326 'n' among tp's children.
328 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
331 All the bits we have seen so far are significant to the node n. The rest
332 of the bits are really not needed or indeed known in n->key.
334 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
335 n's child array, and will of course be different for each child.
338 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
343 static inline void check_tnode(const struct tnode *tn)
345 WARN_ON(tn && tn->pos+tn->bits > 32);
348 static const int halve_threshold = 25;
349 static const int inflate_threshold = 50;
350 static const int halve_threshold_root = 15;
351 static const int inflate_threshold_root = 30;
353 static void __alias_free_mem(struct rcu_head *head)
355 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
356 kmem_cache_free(fn_alias_kmem, fa);
359 static inline void alias_free_mem_rcu(struct fib_alias *fa)
361 call_rcu(&fa->rcu, __alias_free_mem);
364 static void __leaf_free_rcu(struct rcu_head *head)
366 struct leaf *l = container_of(head, struct leaf, rcu);
367 kmem_cache_free(trie_leaf_kmem, l);
370 static inline void free_leaf(struct leaf *l)
372 call_rcu_bh(&l->rcu, __leaf_free_rcu);
375 static inline void free_leaf_info(struct leaf_info *leaf)
377 kfree_rcu(leaf, rcu);
380 static struct tnode *tnode_alloc(size_t size)
382 if (size <= PAGE_SIZE)
383 return kzalloc(size, GFP_KERNEL);
385 return vzalloc(size);
388 static void __tnode_vfree(struct work_struct *arg)
390 struct tnode *tn = container_of(arg, struct tnode, work);
394 static void __tnode_free_rcu(struct rcu_head *head)
396 struct tnode *tn = container_of(head, struct tnode, rcu);
397 size_t size = sizeof(struct tnode) +
398 (sizeof(struct rt_trie_node *) << tn->bits);
400 if (size <= PAGE_SIZE)
403 INIT_WORK(&tn->work, __tnode_vfree);
404 schedule_work(&tn->work);
408 static inline void tnode_free(struct tnode *tn)
411 free_leaf((struct leaf *) tn);
413 call_rcu(&tn->rcu, __tnode_free_rcu);
416 static void tnode_free_safe(struct tnode *tn)
419 tn->tnode_free = tnode_free_head;
420 tnode_free_head = tn;
421 tnode_free_size += sizeof(struct tnode) +
422 (sizeof(struct rt_trie_node *) << tn->bits);
425 static void tnode_free_flush(void)
429 while ((tn = tnode_free_head)) {
430 tnode_free_head = tn->tnode_free;
431 tn->tnode_free = NULL;
435 if (tnode_free_size >= PAGE_SIZE * sync_pages) {
441 static struct leaf *leaf_new(void)
443 struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
446 INIT_HLIST_HEAD(&l->list);
451 static struct leaf_info *leaf_info_new(int plen)
453 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
456 li->mask_plen = ntohl(inet_make_mask(plen));
457 INIT_LIST_HEAD(&li->falh);
462 static struct tnode *tnode_new(t_key key, int pos, int bits)
464 size_t sz = sizeof(struct tnode) + (sizeof(struct rt_trie_node *) << bits);
465 struct tnode *tn = tnode_alloc(sz);
468 tn->parent = T_TNODE;
472 tn->full_children = 0;
473 tn->empty_children = 1<<bits;
476 pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode),
477 sizeof(struct rt_trie_node) << bits);
482 * Check whether a tnode 'n' is "full", i.e. it is an internal node
483 * and no bits are skipped. See discussion in dyntree paper p. 6
486 static inline int tnode_full(const struct tnode *tn, const struct rt_trie_node *n)
488 if (n == NULL || IS_LEAF(n))
491 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
494 static inline void put_child(struct trie *t, struct tnode *tn, int i,
495 struct rt_trie_node *n)
497 tnode_put_child_reorg(tn, i, n, -1);
501 * Add a child at position i overwriting the old value.
502 * Update the value of full_children and empty_children.
505 static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
508 struct rt_trie_node *chi = rtnl_dereference(tn->child[i]);
511 BUG_ON(i >= 1<<tn->bits);
513 /* update emptyChildren */
514 if (n == NULL && chi != NULL)
515 tn->empty_children++;
516 else if (n != NULL && chi == NULL)
517 tn->empty_children--;
519 /* update fullChildren */
521 wasfull = tnode_full(tn, chi);
523 isfull = tnode_full(tn, n);
524 if (wasfull && !isfull)
526 else if (!wasfull && isfull)
530 node_set_parent(n, tn);
532 rcu_assign_pointer(tn->child[i], n);
536 static struct rt_trie_node *resize(struct trie *t, struct tnode *tn)
539 struct tnode *old_tn;
540 int inflate_threshold_use;
541 int halve_threshold_use;
547 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
548 tn, inflate_threshold, halve_threshold);
551 if (tn->empty_children == tnode_child_length(tn)) {
556 if (tn->empty_children == tnode_child_length(tn) - 1)
559 * Double as long as the resulting node has a number of
560 * nonempty nodes that are above the threshold.
564 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
565 * the Helsinki University of Technology and Matti Tikkanen of Nokia
566 * Telecommunications, page 6:
567 * "A node is doubled if the ratio of non-empty children to all
568 * children in the *doubled* node is at least 'high'."
570 * 'high' in this instance is the variable 'inflate_threshold'. It
571 * is expressed as a percentage, so we multiply it with
572 * tnode_child_length() and instead of multiplying by 2 (since the
573 * child array will be doubled by inflate()) and multiplying
574 * the left-hand side by 100 (to handle the percentage thing) we
575 * multiply the left-hand side by 50.
577 * The left-hand side may look a bit weird: tnode_child_length(tn)
578 * - tn->empty_children is of course the number of non-null children
579 * in the current node. tn->full_children is the number of "full"
580 * children, that is non-null tnodes with a skip value of 0.
581 * All of those will be doubled in the resulting inflated tnode, so
582 * we just count them one extra time here.
584 * A clearer way to write this would be:
586 * to_be_doubled = tn->full_children;
587 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
590 * new_child_length = tnode_child_length(tn) * 2;
592 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
594 * if (new_fill_factor >= inflate_threshold)
596 * ...and so on, tho it would mess up the while () loop.
599 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
603 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
604 * inflate_threshold * new_child_length
606 * expand not_to_be_doubled and to_be_doubled, and shorten:
607 * 100 * (tnode_child_length(tn) - tn->empty_children +
608 * tn->full_children) >= inflate_threshold * new_child_length
610 * expand new_child_length:
611 * 100 * (tnode_child_length(tn) - tn->empty_children +
612 * tn->full_children) >=
613 * inflate_threshold * tnode_child_length(tn) * 2
616 * 50 * (tn->full_children + tnode_child_length(tn) -
617 * tn->empty_children) >= inflate_threshold *
618 * tnode_child_length(tn)
624 /* Keep root node larger */
626 if (!node_parent((struct rt_trie_node *)tn)) {
627 inflate_threshold_use = inflate_threshold_root;
628 halve_threshold_use = halve_threshold_root;
630 inflate_threshold_use = inflate_threshold;
631 halve_threshold_use = halve_threshold;
635 while ((tn->full_children > 0 && max_work-- &&
636 50 * (tn->full_children + tnode_child_length(tn)
637 - tn->empty_children)
638 >= inflate_threshold_use * tnode_child_length(tn))) {
645 #ifdef CONFIG_IP_FIB_TRIE_STATS
646 t->stats.resize_node_skipped++;
654 /* Return if at least one inflate is run */
655 if (max_work != MAX_WORK)
656 return (struct rt_trie_node *) tn;
659 * Halve as long as the number of empty children in this
660 * node is above threshold.
664 while (tn->bits > 1 && max_work-- &&
665 100 * (tnode_child_length(tn) - tn->empty_children) <
666 halve_threshold_use * tnode_child_length(tn)) {
672 #ifdef CONFIG_IP_FIB_TRIE_STATS
673 t->stats.resize_node_skipped++;
680 /* Only one child remains */
681 if (tn->empty_children == tnode_child_length(tn) - 1) {
683 for (i = 0; i < tnode_child_length(tn); i++) {
684 struct rt_trie_node *n;
686 n = rtnl_dereference(tn->child[i]);
690 /* compress one level */
692 node_set_parent(n, NULL);
697 return (struct rt_trie_node *) tn;
701 static void tnode_clean_free(struct tnode *tn)
704 struct tnode *tofree;
706 for (i = 0; i < tnode_child_length(tn); i++) {
707 tofree = (struct tnode *)rtnl_dereference(tn->child[i]);
714 static struct tnode *inflate(struct trie *t, struct tnode *tn)
716 struct tnode *oldtnode = tn;
717 int olen = tnode_child_length(tn);
720 pr_debug("In inflate\n");
722 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
725 return ERR_PTR(-ENOMEM);
728 * Preallocate and store tnodes before the actual work so we
729 * don't get into an inconsistent state if memory allocation
730 * fails. In case of failure we return the oldnode and inflate
731 * of tnode is ignored.
734 for (i = 0; i < olen; i++) {
737 inode = (struct tnode *) tnode_get_child(oldtnode, i);
740 inode->pos == oldtnode->pos + oldtnode->bits &&
742 struct tnode *left, *right;
743 t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
745 left = tnode_new(inode->key&(~m), inode->pos + 1,
750 right = tnode_new(inode->key|m, inode->pos + 1,
758 put_child(t, tn, 2*i, (struct rt_trie_node *) left);
759 put_child(t, tn, 2*i+1, (struct rt_trie_node *) right);
763 for (i = 0; i < olen; i++) {
765 struct rt_trie_node *node = tnode_get_child(oldtnode, i);
766 struct tnode *left, *right;
773 /* A leaf or an internal node with skipped bits */
775 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
776 tn->pos + tn->bits - 1) {
777 if (tkey_extract_bits(node->key,
778 oldtnode->pos + oldtnode->bits,
780 put_child(t, tn, 2*i, node);
782 put_child(t, tn, 2*i+1, node);
786 /* An internal node with two children */
787 inode = (struct tnode *) node;
789 if (inode->bits == 1) {
790 put_child(t, tn, 2*i, rtnl_dereference(inode->child[0]));
791 put_child(t, tn, 2*i+1, rtnl_dereference(inode->child[1]));
793 tnode_free_safe(inode);
797 /* An internal node with more than two children */
799 /* We will replace this node 'inode' with two new
800 * ones, 'left' and 'right', each with half of the
801 * original children. The two new nodes will have
802 * a position one bit further down the key and this
803 * means that the "significant" part of their keys
804 * (see the discussion near the top of this file)
805 * will differ by one bit, which will be "0" in
806 * left's key and "1" in right's key. Since we are
807 * moving the key position by one step, the bit that
808 * we are moving away from - the bit at position
809 * (inode->pos) - is the one that will differ between
810 * left and right. So... we synthesize that bit in the
812 * The mask 'm' below will be a single "one" bit at
813 * the position (inode->pos)
816 /* Use the old key, but set the new significant
820 left = (struct tnode *) tnode_get_child(tn, 2*i);
821 put_child(t, tn, 2*i, NULL);
825 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
826 put_child(t, tn, 2*i+1, NULL);
830 size = tnode_child_length(left);
831 for (j = 0; j < size; j++) {
832 put_child(t, left, j, rtnl_dereference(inode->child[j]));
833 put_child(t, right, j, rtnl_dereference(inode->child[j + size]));
835 put_child(t, tn, 2*i, resize(t, left));
836 put_child(t, tn, 2*i+1, resize(t, right));
838 tnode_free_safe(inode);
840 tnode_free_safe(oldtnode);
843 tnode_clean_free(tn);
844 return ERR_PTR(-ENOMEM);
847 static struct tnode *halve(struct trie *t, struct tnode *tn)
849 struct tnode *oldtnode = tn;
850 struct rt_trie_node *left, *right;
852 int olen = tnode_child_length(tn);
854 pr_debug("In halve\n");
856 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
859 return ERR_PTR(-ENOMEM);
862 * Preallocate and store tnodes before the actual work so we
863 * don't get into an inconsistent state if memory allocation
864 * fails. In case of failure we return the oldnode and halve
865 * of tnode is ignored.
868 for (i = 0; i < olen; i += 2) {
869 left = tnode_get_child(oldtnode, i);
870 right = tnode_get_child(oldtnode, i+1);
872 /* Two nonempty children */
876 newn = tnode_new(left->key, tn->pos + tn->bits, 1);
881 put_child(t, tn, i/2, (struct rt_trie_node *)newn);
886 for (i = 0; i < olen; i += 2) {
887 struct tnode *newBinNode;
889 left = tnode_get_child(oldtnode, i);
890 right = tnode_get_child(oldtnode, i+1);
892 /* At least one of the children is empty */
894 if (right == NULL) /* Both are empty */
896 put_child(t, tn, i/2, right);
901 put_child(t, tn, i/2, left);
905 /* Two nonempty children */
906 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
907 put_child(t, tn, i/2, NULL);
908 put_child(t, newBinNode, 0, left);
909 put_child(t, newBinNode, 1, right);
910 put_child(t, tn, i/2, resize(t, newBinNode));
912 tnode_free_safe(oldtnode);
915 tnode_clean_free(tn);
916 return ERR_PTR(-ENOMEM);
919 /* readside must use rcu_read_lock currently dump routines
920 via get_fa_head and dump */
922 static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
924 struct hlist_head *head = &l->list;
925 struct hlist_node *node;
926 struct leaf_info *li;
928 hlist_for_each_entry_rcu(li, node, head, hlist)
929 if (li->plen == plen)
935 static inline struct list_head *get_fa_head(struct leaf *l, int plen)
937 struct leaf_info *li = find_leaf_info(l, plen);
945 static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
947 struct leaf_info *li = NULL, *last = NULL;
948 struct hlist_node *node;
950 if (hlist_empty(head)) {
951 hlist_add_head_rcu(&new->hlist, head);
953 hlist_for_each_entry(li, node, head, hlist) {
954 if (new->plen > li->plen)
960 hlist_add_after_rcu(&last->hlist, &new->hlist);
962 hlist_add_before_rcu(&new->hlist, &li->hlist);
966 /* rcu_read_lock needs to be hold by caller from readside */
969 fib_find_node(struct trie *t, u32 key)
973 struct rt_trie_node *n;
976 n = rcu_dereference_rtnl(t->trie);
978 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
979 tn = (struct tnode *) n;
983 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
984 pos = tn->pos + tn->bits;
985 n = tnode_get_child_rcu(tn,
986 tkey_extract_bits(key,
992 /* Case we have found a leaf. Compare prefixes */
994 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
995 return (struct leaf *)n;
1000 static void trie_rebalance(struct trie *t, struct tnode *tn)
1008 while (tn != NULL && (tp = node_parent((struct rt_trie_node *)tn)) != NULL) {
1009 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1010 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
1011 tn = (struct tnode *) resize(t, (struct tnode *)tn);
1013 tnode_put_child_reorg((struct tnode *)tp, cindex,
1014 (struct rt_trie_node *)tn, wasfull);
1016 tp = node_parent((struct rt_trie_node *) tn);
1018 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1026 /* Handle last (top) tnode */
1028 tn = (struct tnode *)resize(t, (struct tnode *)tn);
1030 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1034 /* only used from updater-side */
1036 static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
1039 struct tnode *tp = NULL, *tn = NULL;
1040 struct rt_trie_node *n;
1043 struct list_head *fa_head = NULL;
1044 struct leaf_info *li;
1048 n = rtnl_dereference(t->trie);
1050 /* If we point to NULL, stop. Either the tree is empty and we should
1051 * just put a new leaf in if, or we have reached an empty child slot,
1052 * and we should just put our new leaf in that.
1053 * If we point to a T_TNODE, check if it matches our key. Note that
1054 * a T_TNODE might be skipping any number of bits - its 'pos' need
1055 * not be the parent's 'pos'+'bits'!
1057 * If it does match the current key, get pos/bits from it, extract
1058 * the index from our key, push the T_TNODE and walk the tree.
1060 * If it doesn't, we have to replace it with a new T_TNODE.
1062 * If we point to a T_LEAF, it might or might not have the same key
1063 * as we do. If it does, just change the value, update the T_LEAF's
1064 * value, and return it.
1065 * If it doesn't, we need to replace it with a T_TNODE.
1068 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1069 tn = (struct tnode *) n;
1073 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1075 pos = tn->pos + tn->bits;
1076 n = tnode_get_child(tn,
1077 tkey_extract_bits(key,
1081 BUG_ON(n && node_parent(n) != tn);
1087 * n ----> NULL, LEAF or TNODE
1089 * tp is n's (parent) ----> NULL or TNODE
1092 BUG_ON(tp && IS_LEAF(tp));
1094 /* Case 1: n is a leaf. Compare prefixes */
1096 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1097 l = (struct leaf *) n;
1098 li = leaf_info_new(plen);
1103 fa_head = &li->falh;
1104 insert_leaf_info(&l->list, li);
1113 li = leaf_info_new(plen);
1120 fa_head = &li->falh;
1121 insert_leaf_info(&l->list, li);
1123 if (t->trie && n == NULL) {
1124 /* Case 2: n is NULL, and will just insert a new leaf */
1126 node_set_parent((struct rt_trie_node *)l, tp);
1128 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1129 put_child(t, (struct tnode *)tp, cindex, (struct rt_trie_node *)l);
1131 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1133 * Add a new tnode here
1134 * first tnode need some special handling
1138 pos = tp->pos+tp->bits;
1143 newpos = tkey_mismatch(key, pos, n->key);
1144 tn = tnode_new(n->key, newpos, 1);
1147 tn = tnode_new(key, newpos, 1); /* First tnode */
1156 node_set_parent((struct rt_trie_node *)tn, tp);
1158 missbit = tkey_extract_bits(key, newpos, 1);
1159 put_child(t, tn, missbit, (struct rt_trie_node *)l);
1160 put_child(t, tn, 1-missbit, n);
1163 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1164 put_child(t, (struct tnode *)tp, cindex,
1165 (struct rt_trie_node *)tn);
1167 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1172 if (tp && tp->pos + tp->bits > 32)
1173 pr_warning("fib_trie"
1174 " tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1175 tp, tp->pos, tp->bits, key, plen);
1177 /* Rebalance the trie */
1179 trie_rebalance(t, tp);
1185 * Caller must hold RTNL.
1187 int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
1189 struct trie *t = (struct trie *) tb->tb_data;
1190 struct fib_alias *fa, *new_fa;
1191 struct list_head *fa_head = NULL;
1192 struct fib_info *fi;
1193 int plen = cfg->fc_dst_len;
1194 u8 tos = cfg->fc_tos;
1202 key = ntohl(cfg->fc_dst);
1204 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1206 mask = ntohl(inet_make_mask(plen));
1213 fi = fib_create_info(cfg);
1219 l = fib_find_node(t, key);
1223 fa_head = get_fa_head(l, plen);
1224 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1227 /* Now fa, if non-NULL, points to the first fib alias
1228 * with the same keys [prefix,tos,priority], if such key already
1229 * exists or to the node before which we will insert new one.
1231 * If fa is NULL, we will need to allocate a new one and
1232 * insert to the head of f.
1234 * If f is NULL, no fib node matched the destination key
1235 * and we need to allocate a new one of those as well.
1238 if (fa && fa->fa_tos == tos &&
1239 fa->fa_info->fib_priority == fi->fib_priority) {
1240 struct fib_alias *fa_first, *fa_match;
1243 if (cfg->fc_nlflags & NLM_F_EXCL)
1247 * 1. Find exact match for type, scope, fib_info to avoid
1249 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1253 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1254 list_for_each_entry_continue(fa, fa_head, fa_list) {
1255 if (fa->fa_tos != tos)
1257 if (fa->fa_info->fib_priority != fi->fib_priority)
1259 if (fa->fa_type == cfg->fc_type &&
1260 fa->fa_info == fi) {
1266 if (cfg->fc_nlflags & NLM_F_REPLACE) {
1267 struct fib_info *fi_drop;
1277 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1281 fi_drop = fa->fa_info;
1282 new_fa->fa_tos = fa->fa_tos;
1283 new_fa->fa_info = fi;
1284 new_fa->fa_type = cfg->fc_type;
1285 state = fa->fa_state;
1286 new_fa->fa_state = state & ~FA_S_ACCESSED;
1288 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1289 alias_free_mem_rcu(fa);
1291 fib_release_info(fi_drop);
1292 if (state & FA_S_ACCESSED)
1293 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1294 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1295 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1299 /* Error if we find a perfect match which
1300 * uses the same scope, type, and nexthop
1306 if (!(cfg->fc_nlflags & NLM_F_APPEND))
1310 if (!(cfg->fc_nlflags & NLM_F_CREATE))
1314 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1318 new_fa->fa_info = fi;
1319 new_fa->fa_tos = tos;
1320 new_fa->fa_type = cfg->fc_type;
1321 new_fa->fa_state = 0;
1323 * Insert new entry to the list.
1327 fa_head = fib_insert_node(t, key, plen);
1328 if (unlikely(!fa_head)) {
1330 goto out_free_new_fa;
1335 tb->tb_num_default++;
1337 list_add_tail_rcu(&new_fa->fa_list,
1338 (fa ? &fa->fa_list : fa_head));
1340 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1341 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1342 &cfg->fc_nlinfo, 0);
1347 kmem_cache_free(fn_alias_kmem, new_fa);
1349 fib_release_info(fi);
1354 /* should be called with rcu_read_lock */
1355 static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
1356 t_key key, const struct flowi4 *flp,
1357 struct fib_result *res, int fib_flags)
1359 struct leaf_info *li;
1360 struct hlist_head *hhead = &l->list;
1361 struct hlist_node *node;
1363 hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1364 struct fib_alias *fa;
1366 if (l->key != (key & li->mask_plen))
1369 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
1370 struct fib_info *fi = fa->fa_info;
1373 if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1377 if (fa->fa_info->fib_scope < flp->flowi4_scope)
1379 fib_alias_accessed(fa);
1380 err = fib_props[fa->fa_type].error;
1382 #ifdef CONFIG_IP_FIB_TRIE_STATS
1383 t->stats.semantic_match_passed++;
1387 if (fi->fib_flags & RTNH_F_DEAD)
1389 for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
1390 const struct fib_nh *nh = &fi->fib_nh[nhsel];
1392 if (nh->nh_flags & RTNH_F_DEAD)
1394 if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
1397 #ifdef CONFIG_IP_FIB_TRIE_STATS
1398 t->stats.semantic_match_passed++;
1400 res->prefixlen = li->plen;
1401 res->nh_sel = nhsel;
1402 res->type = fa->fa_type;
1403 res->scope = fa->fa_info->fib_scope;
1406 res->fa_head = &li->falh;
1407 if (!(fib_flags & FIB_LOOKUP_NOREF))
1408 atomic_inc(&fi->fib_clntref);
1413 #ifdef CONFIG_IP_FIB_TRIE_STATS
1414 t->stats.semantic_match_miss++;
1421 int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
1422 struct fib_result *res, int fib_flags)
1424 struct trie *t = (struct trie *) tb->tb_data;
1426 struct rt_trie_node *n;
1428 unsigned int pos, bits;
1429 t_key key = ntohl(flp->daddr);
1430 unsigned int chopped_off;
1432 unsigned int current_prefix_length = KEYLENGTH;
1434 t_key pref_mismatch;
1438 n = rcu_dereference(t->trie);
1442 #ifdef CONFIG_IP_FIB_TRIE_STATS
1448 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1452 pn = (struct tnode *) n;
1460 cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1463 n = tnode_get_child_rcu(pn, cindex);
1466 #ifdef CONFIG_IP_FIB_TRIE_STATS
1467 t->stats.null_node_hit++;
1473 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1479 cn = (struct tnode *)n;
1482 * It's a tnode, and we can do some extra checks here if we
1483 * like, to avoid descending into a dead-end branch.
1484 * This tnode is in the parent's child array at index
1485 * key[p_pos..p_pos+p_bits] but potentially with some bits
1486 * chopped off, so in reality the index may be just a
1487 * subprefix, padded with zero at the end.
1488 * We can also take a look at any skipped bits in this
1489 * tnode - everything up to p_pos is supposed to be ok,
1490 * and the non-chopped bits of the index (se previous
1491 * paragraph) are also guaranteed ok, but the rest is
1492 * considered unknown.
1494 * The skipped bits are key[pos+bits..cn->pos].
1497 /* If current_prefix_length < pos+bits, we are already doing
1498 * actual prefix matching, which means everything from
1499 * pos+(bits-chopped_off) onward must be zero along some
1500 * branch of this subtree - otherwise there is *no* valid
1501 * prefix present. Here we can only check the skipped
1502 * bits. Remember, since we have already indexed into the
1503 * parent's child array, we know that the bits we chopped of
1507 /* NOTA BENE: Checking only skipped bits
1508 for the new node here */
1510 if (current_prefix_length < pos+bits) {
1511 if (tkey_extract_bits(cn->key, current_prefix_length,
1512 cn->pos - current_prefix_length)
1518 * If chopped_off=0, the index is fully validated and we
1519 * only need to look at the skipped bits for this, the new,
1520 * tnode. What we actually want to do is to find out if
1521 * these skipped bits match our key perfectly, or if we will
1522 * have to count on finding a matching prefix further down,
1523 * because if we do, we would like to have some way of
1524 * verifying the existence of such a prefix at this point.
1527 /* The only thing we can do at this point is to verify that
1528 * any such matching prefix can indeed be a prefix to our
1529 * key, and if the bits in the node we are inspecting that
1530 * do not match our key are not ZERO, this cannot be true.
1531 * Thus, find out where there is a mismatch (before cn->pos)
1532 * and verify that all the mismatching bits are zero in the
1537 * Note: We aren't very concerned about the piece of
1538 * the key that precede pn->pos+pn->bits, since these
1539 * have already been checked. The bits after cn->pos
1540 * aren't checked since these are by definition
1541 * "unknown" at this point. Thus, what we want to see
1542 * is if we are about to enter the "prefix matching"
1543 * state, and in that case verify that the skipped
1544 * bits that will prevail throughout this subtree are
1545 * zero, as they have to be if we are to find a
1549 pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
1552 * In short: If skipped bits in this node do not match
1553 * the search key, enter the "prefix matching"
1556 if (pref_mismatch) {
1557 int mp = KEYLENGTH - fls(pref_mismatch);
1559 if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
1562 if (current_prefix_length >= cn->pos)
1563 current_prefix_length = mp;
1566 pn = (struct tnode *)n; /* Descend */
1573 /* As zero don't change the child key (cindex) */
1574 while ((chopped_off <= pn->bits)
1575 && !(cindex & (1<<(chopped_off-1))))
1578 /* Decrease current_... with bits chopped off */
1579 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1580 current_prefix_length = pn->pos + pn->bits
1584 * Either we do the actual chop off according or if we have
1585 * chopped off all bits in this tnode walk up to our parent.
1588 if (chopped_off <= pn->bits) {
1589 cindex &= ~(1 << (chopped_off-1));
1591 struct tnode *parent = node_parent_rcu((struct rt_trie_node *) pn);
1595 /* Get Child's index */
1596 cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1600 #ifdef CONFIG_IP_FIB_TRIE_STATS
1601 t->stats.backtrack++;
1614 * Remove the leaf and return parent.
1616 static void trie_leaf_remove(struct trie *t, struct leaf *l)
1618 struct tnode *tp = node_parent((struct rt_trie_node *) l);
1620 pr_debug("entering trie_leaf_remove(%p)\n", l);
1623 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1624 put_child(t, (struct tnode *)tp, cindex, NULL);
1625 trie_rebalance(t, tp);
1627 RCU_INIT_POINTER(t->trie, NULL);
1633 * Caller must hold RTNL.
1635 int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
1637 struct trie *t = (struct trie *) tb->tb_data;
1639 int plen = cfg->fc_dst_len;
1640 u8 tos = cfg->fc_tos;
1641 struct fib_alias *fa, *fa_to_delete;
1642 struct list_head *fa_head;
1644 struct leaf_info *li;
1649 key = ntohl(cfg->fc_dst);
1650 mask = ntohl(inet_make_mask(plen));
1656 l = fib_find_node(t, key);
1661 fa_head = get_fa_head(l, plen);
1662 fa = fib_find_alias(fa_head, tos, 0);
1667 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1669 fa_to_delete = NULL;
1670 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1671 list_for_each_entry_continue(fa, fa_head, fa_list) {
1672 struct fib_info *fi = fa->fa_info;
1674 if (fa->fa_tos != tos)
1677 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1678 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1679 fa->fa_info->fib_scope == cfg->fc_scope) &&
1680 (!cfg->fc_prefsrc ||
1681 fi->fib_prefsrc == cfg->fc_prefsrc) &&
1682 (!cfg->fc_protocol ||
1683 fi->fib_protocol == cfg->fc_protocol) &&
1684 fib_nh_match(cfg, fi) == 0) {
1694 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1695 &cfg->fc_nlinfo, 0);
1697 l = fib_find_node(t, key);
1698 li = find_leaf_info(l, plen);
1700 list_del_rcu(&fa->fa_list);
1703 tb->tb_num_default--;
1705 if (list_empty(fa_head)) {
1706 hlist_del_rcu(&li->hlist);
1710 if (hlist_empty(&l->list))
1711 trie_leaf_remove(t, l);
1713 if (fa->fa_state & FA_S_ACCESSED)
1714 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1716 fib_release_info(fa->fa_info);
1717 alias_free_mem_rcu(fa);
1721 static int trie_flush_list(struct list_head *head)
1723 struct fib_alias *fa, *fa_node;
1726 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1727 struct fib_info *fi = fa->fa_info;
1729 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1730 list_del_rcu(&fa->fa_list);
1731 fib_release_info(fa->fa_info);
1732 alias_free_mem_rcu(fa);
1739 static int trie_flush_leaf(struct leaf *l)
1742 struct hlist_head *lih = &l->list;
1743 struct hlist_node *node, *tmp;
1744 struct leaf_info *li = NULL;
1746 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
1747 found += trie_flush_list(&li->falh);
1749 if (list_empty(&li->falh)) {
1750 hlist_del_rcu(&li->hlist);
1758 * Scan for the next right leaf starting at node p->child[idx]
1759 * Since we have back pointer, no recursion necessary.
1761 static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1767 idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1771 while (idx < 1u << p->bits) {
1772 c = tnode_get_child_rcu(p, idx++);
1777 prefetch(rcu_dereference_rtnl(p->child[idx]));
1778 return (struct leaf *) c;
1781 /* Rescan start scanning in new node */
1782 p = (struct tnode *) c;
1786 /* Node empty, walk back up to parent */
1787 c = (struct rt_trie_node *) p;
1788 } while ((p = node_parent_rcu(c)) != NULL);
1790 return NULL; /* Root of trie */
1793 static struct leaf *trie_firstleaf(struct trie *t)
1795 struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
1800 if (IS_LEAF(n)) /* trie is just a leaf */
1801 return (struct leaf *) n;
1803 return leaf_walk_rcu(n, NULL);
1806 static struct leaf *trie_nextleaf(struct leaf *l)
1808 struct rt_trie_node *c = (struct rt_trie_node *) l;
1809 struct tnode *p = node_parent_rcu(c);
1812 return NULL; /* trie with just one leaf */
1814 return leaf_walk_rcu(p, c);
1817 static struct leaf *trie_leafindex(struct trie *t, int index)
1819 struct leaf *l = trie_firstleaf(t);
1821 while (l && index-- > 0)
1822 l = trie_nextleaf(l);
1829 * Caller must hold RTNL.
1831 int fib_table_flush(struct fib_table *tb)
1833 struct trie *t = (struct trie *) tb->tb_data;
1834 struct leaf *l, *ll = NULL;
1837 for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1838 found += trie_flush_leaf(l);
1840 if (ll && hlist_empty(&ll->list))
1841 trie_leaf_remove(t, ll);
1845 if (ll && hlist_empty(&ll->list))
1846 trie_leaf_remove(t, ll);
1848 pr_debug("trie_flush found=%d\n", found);
1852 void fib_free_table(struct fib_table *tb)
1857 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1858 struct fib_table *tb,
1859 struct sk_buff *skb, struct netlink_callback *cb)
1862 struct fib_alias *fa;
1863 __be32 xkey = htonl(key);
1868 /* rcu_read_lock is hold by caller */
1870 list_for_each_entry_rcu(fa, fah, fa_list) {
1876 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1884 fa->fa_info, NLM_F_MULTI) < 0) {
1894 static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1895 struct sk_buff *skb, struct netlink_callback *cb)
1897 struct leaf_info *li;
1898 struct hlist_node *node;
1904 /* rcu_read_lock is hold by caller */
1905 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
1914 if (list_empty(&li->falh))
1917 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1928 int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
1929 struct netlink_callback *cb)
1932 struct trie *t = (struct trie *) tb->tb_data;
1933 t_key key = cb->args[2];
1934 int count = cb->args[3];
1937 /* Dump starting at last key.
1938 * Note: 0.0.0.0/0 (ie default) is first key.
1941 l = trie_firstleaf(t);
1943 /* Normally, continue from last key, but if that is missing
1944 * fallback to using slow rescan
1946 l = fib_find_node(t, key);
1948 l = trie_leafindex(t, count);
1952 cb->args[2] = l->key;
1953 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1954 cb->args[3] = count;
1960 l = trie_nextleaf(l);
1961 memset(&cb->args[4], 0,
1962 sizeof(cb->args) - 4*sizeof(cb->args[0]));
1964 cb->args[3] = count;
1970 void __init fib_trie_init(void)
1972 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1973 sizeof(struct fib_alias),
1974 0, SLAB_PANIC, NULL);
1976 trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1977 max(sizeof(struct leaf),
1978 sizeof(struct leaf_info)),
1979 0, SLAB_PANIC, NULL);
1983 struct fib_table *fib_trie_table(u32 id)
1985 struct fib_table *tb;
1988 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1994 tb->tb_default = -1;
1995 tb->tb_num_default = 0;
1997 t = (struct trie *) tb->tb_data;
1998 memset(t, 0, sizeof(*t));
2003 #ifdef CONFIG_PROC_FS
2004 /* Depth first Trie walk iterator */
2005 struct fib_trie_iter {
2006 struct seq_net_private p;
2007 struct fib_table *tb;
2008 struct tnode *tnode;
2013 static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
2015 struct tnode *tn = iter->tnode;
2016 unsigned int cindex = iter->index;
2019 /* A single entry routing table */
2023 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2024 iter->tnode, iter->index, iter->depth);
2026 while (cindex < (1<<tn->bits)) {
2027 struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
2032 iter->index = cindex + 1;
2034 /* push down one level */
2035 iter->tnode = (struct tnode *) n;
2045 /* Current node exhausted, pop back up */
2046 p = node_parent_rcu((struct rt_trie_node *)tn);
2048 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2058 static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
2061 struct rt_trie_node *n;
2066 n = rcu_dereference(t->trie);
2071 iter->tnode = (struct tnode *) n;
2083 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2085 struct rt_trie_node *n;
2086 struct fib_trie_iter iter;
2088 memset(s, 0, sizeof(*s));
2091 for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2093 struct leaf *l = (struct leaf *)n;
2094 struct leaf_info *li;
2095 struct hlist_node *tmp;
2098 s->totdepth += iter.depth;
2099 if (iter.depth > s->maxdepth)
2100 s->maxdepth = iter.depth;
2102 hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
2105 const struct tnode *tn = (const struct tnode *) n;
2109 if (tn->bits < MAX_STAT_DEPTH)
2110 s->nodesizes[tn->bits]++;
2112 for (i = 0; i < (1<<tn->bits); i++)
2121 * This outputs /proc/net/fib_triestats
2123 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2125 unsigned int i, max, pointers, bytes, avdepth;
2128 avdepth = stat->totdepth*100 / stat->leaves;
2132 seq_printf(seq, "\tAver depth: %u.%02d\n",
2133 avdepth / 100, avdepth % 100);
2134 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
2136 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
2137 bytes = sizeof(struct leaf) * stat->leaves;
2139 seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes);
2140 bytes += sizeof(struct leaf_info) * stat->prefixes;
2142 seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2143 bytes += sizeof(struct tnode) * stat->tnodes;
2145 max = MAX_STAT_DEPTH;
2146 while (max > 0 && stat->nodesizes[max-1] == 0)
2150 for (i = 1; i <= max; i++)
2151 if (stat->nodesizes[i] != 0) {
2152 seq_printf(seq, " %u: %u", i, stat->nodesizes[i]);
2153 pointers += (1<<i) * stat->nodesizes[i];
2155 seq_putc(seq, '\n');
2156 seq_printf(seq, "\tPointers: %u\n", pointers);
2158 bytes += sizeof(struct rt_trie_node *) * pointers;
2159 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2160 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
2163 #ifdef CONFIG_IP_FIB_TRIE_STATS
2164 static void trie_show_usage(struct seq_file *seq,
2165 const struct trie_use_stats *stats)
2167 seq_printf(seq, "\nCounters:\n---------\n");
2168 seq_printf(seq, "gets = %u\n", stats->gets);
2169 seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2170 seq_printf(seq, "semantic match passed = %u\n",
2171 stats->semantic_match_passed);
2172 seq_printf(seq, "semantic match miss = %u\n",
2173 stats->semantic_match_miss);
2174 seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2175 seq_printf(seq, "skipped node resize = %u\n\n",
2176 stats->resize_node_skipped);
2178 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2180 static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2182 if (tb->tb_id == RT_TABLE_LOCAL)
2183 seq_puts(seq, "Local:\n");
2184 else if (tb->tb_id == RT_TABLE_MAIN)
2185 seq_puts(seq, "Main:\n");
2187 seq_printf(seq, "Id %d:\n", tb->tb_id);
2191 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2193 struct net *net = (struct net *)seq->private;
2197 "Basic info: size of leaf:"
2198 " %Zd bytes, size of tnode: %Zd bytes.\n",
2199 sizeof(struct leaf), sizeof(struct tnode));
2201 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2202 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2203 struct hlist_node *node;
2204 struct fib_table *tb;
2206 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2207 struct trie *t = (struct trie *) tb->tb_data;
2208 struct trie_stat stat;
2213 fib_table_print(seq, tb);
2215 trie_collect_stats(t, &stat);
2216 trie_show_stats(seq, &stat);
2217 #ifdef CONFIG_IP_FIB_TRIE_STATS
2218 trie_show_usage(seq, &t->stats);
2226 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2228 return single_open_net(inode, file, fib_triestat_seq_show);
2231 static const struct file_operations fib_triestat_fops = {
2232 .owner = THIS_MODULE,
2233 .open = fib_triestat_seq_open,
2235 .llseek = seq_lseek,
2236 .release = single_release_net,
2239 static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2241 struct fib_trie_iter *iter = seq->private;
2242 struct net *net = seq_file_net(seq);
2246 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2247 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2248 struct hlist_node *node;
2249 struct fib_table *tb;
2251 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2252 struct rt_trie_node *n;
2254 for (n = fib_trie_get_first(iter,
2255 (struct trie *) tb->tb_data);
2256 n; n = fib_trie_get_next(iter))
2267 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2271 return fib_trie_get_idx(seq, *pos);
2274 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2276 struct fib_trie_iter *iter = seq->private;
2277 struct net *net = seq_file_net(seq);
2278 struct fib_table *tb = iter->tb;
2279 struct hlist_node *tb_node;
2281 struct rt_trie_node *n;
2284 /* next node in same table */
2285 n = fib_trie_get_next(iter);
2289 /* walk rest of this hash chain */
2290 h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2291 while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2292 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2293 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2298 /* new hash chain */
2299 while (++h < FIB_TABLE_HASHSZ) {
2300 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2301 hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) {
2302 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2314 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2320 static void seq_indent(struct seq_file *seq, int n)
2326 static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2329 case RT_SCOPE_UNIVERSE: return "universe";
2330 case RT_SCOPE_SITE: return "site";
2331 case RT_SCOPE_LINK: return "link";
2332 case RT_SCOPE_HOST: return "host";
2333 case RT_SCOPE_NOWHERE: return "nowhere";
2335 snprintf(buf, len, "scope=%d", s);
2340 static const char *const rtn_type_names[__RTN_MAX] = {
2341 [RTN_UNSPEC] = "UNSPEC",
2342 [RTN_UNICAST] = "UNICAST",
2343 [RTN_LOCAL] = "LOCAL",
2344 [RTN_BROADCAST] = "BROADCAST",
2345 [RTN_ANYCAST] = "ANYCAST",
2346 [RTN_MULTICAST] = "MULTICAST",
2347 [RTN_BLACKHOLE] = "BLACKHOLE",
2348 [RTN_UNREACHABLE] = "UNREACHABLE",
2349 [RTN_PROHIBIT] = "PROHIBIT",
2350 [RTN_THROW] = "THROW",
2352 [RTN_XRESOLVE] = "XRESOLVE",
2355 static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2357 if (t < __RTN_MAX && rtn_type_names[t])
2358 return rtn_type_names[t];
2359 snprintf(buf, len, "type %u", t);
2363 /* Pretty print the trie */
2364 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2366 const struct fib_trie_iter *iter = seq->private;
2367 struct rt_trie_node *n = v;
2369 if (!node_parent_rcu(n))
2370 fib_table_print(seq, iter->tb);
2373 struct tnode *tn = (struct tnode *) n;
2374 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2376 seq_indent(seq, iter->depth-1);
2377 seq_printf(seq, " +-- %pI4/%d %d %d %d\n",
2378 &prf, tn->pos, tn->bits, tn->full_children,
2379 tn->empty_children);
2382 struct leaf *l = (struct leaf *) n;
2383 struct leaf_info *li;
2384 struct hlist_node *node;
2385 __be32 val = htonl(l->key);
2387 seq_indent(seq, iter->depth);
2388 seq_printf(seq, " |-- %pI4\n", &val);
2390 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2391 struct fib_alias *fa;
2393 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2394 char buf1[32], buf2[32];
2396 seq_indent(seq, iter->depth+1);
2397 seq_printf(seq, " /%d %s %s", li->plen,
2398 rtn_scope(buf1, sizeof(buf1),
2399 fa->fa_info->fib_scope),
2400 rtn_type(buf2, sizeof(buf2),
2403 seq_printf(seq, " tos=%d", fa->fa_tos);
2404 seq_putc(seq, '\n');
2412 static const struct seq_operations fib_trie_seq_ops = {
2413 .start = fib_trie_seq_start,
2414 .next = fib_trie_seq_next,
2415 .stop = fib_trie_seq_stop,
2416 .show = fib_trie_seq_show,
2419 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2421 return seq_open_net(inode, file, &fib_trie_seq_ops,
2422 sizeof(struct fib_trie_iter));
2425 static const struct file_operations fib_trie_fops = {
2426 .owner = THIS_MODULE,
2427 .open = fib_trie_seq_open,
2429 .llseek = seq_lseek,
2430 .release = seq_release_net,
2433 struct fib_route_iter {
2434 struct seq_net_private p;
2435 struct trie *main_trie;
2440 static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2442 struct leaf *l = NULL;
2443 struct trie *t = iter->main_trie;
2445 /* use cache location of last found key */
2446 if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2450 l = trie_firstleaf(t);
2453 while (l && pos-- > 0) {
2455 l = trie_nextleaf(l);
2459 iter->key = pos; /* remember it */
2461 iter->pos = 0; /* forget it */
2466 static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2469 struct fib_route_iter *iter = seq->private;
2470 struct fib_table *tb;
2473 tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2477 iter->main_trie = (struct trie *) tb->tb_data;
2479 return SEQ_START_TOKEN;
2481 return fib_route_get_idx(iter, *pos - 1);
2484 static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2486 struct fib_route_iter *iter = seq->private;
2490 if (v == SEQ_START_TOKEN) {
2492 l = trie_firstleaf(iter->main_trie);
2495 l = trie_nextleaf(l);
2505 static void fib_route_seq_stop(struct seq_file *seq, void *v)
2511 static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2513 unsigned int flags = 0;
2515 if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
2517 if (fi && fi->fib_nh->nh_gw)
2518 flags |= RTF_GATEWAY;
2519 if (mask == htonl(0xFFFFFFFF))
2526 * This outputs /proc/net/route.
2527 * The format of the file is not supposed to be changed
2528 * and needs to be same as fib_hash output to avoid breaking
2531 static int fib_route_seq_show(struct seq_file *seq, void *v)
2534 struct leaf_info *li;
2535 struct hlist_node *node;
2537 if (v == SEQ_START_TOKEN) {
2538 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2539 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2544 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2545 struct fib_alias *fa;
2546 __be32 mask, prefix;
2548 mask = inet_make_mask(li->plen);
2549 prefix = htonl(l->key);
2551 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2552 const struct fib_info *fi = fa->fa_info;
2553 unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2556 if (fa->fa_type == RTN_BROADCAST
2557 || fa->fa_type == RTN_MULTICAST)
2562 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2563 "%d\t%08X\t%d\t%u\t%u%n",
2564 fi->fib_dev ? fi->fib_dev->name : "*",
2566 fi->fib_nh->nh_gw, flags, 0, 0,
2570 fi->fib_advmss + 40 : 0),
2572 fi->fib_rtt >> 3, &len);
2575 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2576 "%d\t%08X\t%d\t%u\t%u%n",
2577 prefix, 0, flags, 0, 0, 0,
2578 mask, 0, 0, 0, &len);
2580 seq_printf(seq, "%*s\n", 127 - len, "");
2587 static const struct seq_operations fib_route_seq_ops = {
2588 .start = fib_route_seq_start,
2589 .next = fib_route_seq_next,
2590 .stop = fib_route_seq_stop,
2591 .show = fib_route_seq_show,
2594 static int fib_route_seq_open(struct inode *inode, struct file *file)
2596 return seq_open_net(inode, file, &fib_route_seq_ops,
2597 sizeof(struct fib_route_iter));
2600 static const struct file_operations fib_route_fops = {
2601 .owner = THIS_MODULE,
2602 .open = fib_route_seq_open,
2604 .llseek = seq_lseek,
2605 .release = seq_release_net,
2608 int __net_init fib_proc_init(struct net *net)
2610 if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
2613 if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
2614 &fib_triestat_fops))
2617 if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
2623 proc_net_remove(net, "fib_triestat");
2625 proc_net_remove(net, "fib_trie");
2630 void __net_exit fib_proc_exit(struct net *net)
2632 proc_net_remove(net, "fib_trie");
2633 proc_net_remove(net, "fib_triestat");
2634 proc_net_remove(net, "route");
2637 #endif /* CONFIG_PROC_FS */