2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version
5 * 2 of the License, or (at your option) any later version.
7 * Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
8 * & Swedish University of Agricultural Sciences.
10 * Jens Laas <jens.laas@data.slu.se> Swedish University of
11 * Agricultural Sciences.
13 * Hans Liss <hans.liss@its.uu.se> Uppsala Universitet
15 * This work is based on the LPC-trie which is originally descibed in:
17 * An experimental study of compression methods for dynamic tries
18 * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
19 * http://www.nada.kth.se/~snilsson/public/papers/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
25 * Version: $Id: fib_trie.c,v 1.3 2005/06/08 14:20:01 robert Exp $
28 * Code from fib_hash has been reused which includes the following header:
31 * INET An implementation of the TCP/IP protocol suite for the LINUX
32 * operating system. INET is implemented using the BSD Socket
33 * interface as the means of communication with the user level.
35 * IPv4 FIB: lookup engine and maintenance routines.
38 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
40 * This program is free software; you can redistribute it and/or
41 * modify it under the terms of the GNU General Public License
42 * as published by the Free Software Foundation; either version
43 * 2 of the License, or (at your option) any later version.
45 * Substantial contributions to this work comes from:
47 * David S. Miller, <davem@davemloft.net>
48 * Stephen Hemminger <shemminger@osdl.org>
49 * Paul E. McKenney <paulmck@us.ibm.com>
50 * Patrick McHardy <kaber@trash.net>
53 #define VERSION "0.408"
55 #include <asm/uaccess.h>
56 #include <asm/system.h>
57 #include <linux/bitops.h>
58 #include <linux/types.h>
59 #include <linux/kernel.h>
61 #include <linux/string.h>
62 #include <linux/socket.h>
63 #include <linux/sockios.h>
64 #include <linux/errno.h>
66 #include <linux/inet.h>
67 #include <linux/inetdevice.h>
68 #include <linux/netdevice.h>
69 #include <linux/if_arp.h>
70 #include <linux/proc_fs.h>
71 #include <linux/rcupdate.h>
72 #include <linux/skbuff.h>
73 #include <linux/netlink.h>
74 #include <linux/init.h>
75 #include <linux/list.h>
76 #include <net/net_namespace.h>
78 #include <net/protocol.h>
79 #include <net/route.h>
82 #include <net/ip_fib.h>
83 #include "fib_lookup.h"
85 #define MAX_STAT_DEPTH 32
87 #define KEYLENGTH (8*sizeof(t_key))
89 typedef unsigned int t_key;
93 #define NODE_TYPE_MASK 0x1UL
94 #define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
96 #define IS_TNODE(n) (!(n->parent & T_LEAF))
97 #define IS_LEAF(n) (n->parent & T_LEAF)
100 unsigned long parent;
105 unsigned long parent;
107 struct hlist_head list;
112 struct hlist_node hlist;
115 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 work_struct work;
129 struct node *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];
155 #ifdef CONFIG_IP_FIB_TRIE_STATS
156 struct trie_use_stats stats;
160 static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
161 static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
163 static struct node *resize(struct trie *t, struct tnode *tn);
164 static struct tnode *inflate(struct trie *t, struct tnode *tn);
165 static struct tnode *halve(struct trie *t, struct tnode *tn);
166 static void tnode_free(struct tnode *tn);
168 static struct kmem_cache *fn_alias_kmem __read_mostly;
169 static struct kmem_cache *trie_leaf_kmem __read_mostly;
171 static inline struct tnode *node_parent(struct node *node)
173 return (struct tnode *)(node->parent & ~NODE_TYPE_MASK);
176 static inline struct tnode *node_parent_rcu(struct node *node)
178 struct tnode *ret = node_parent(node);
180 return rcu_dereference(ret);
183 /* Same as rcu_assign_pointer
184 * but that macro() assumes that value is a pointer.
186 static inline void node_set_parent(struct node *node, struct tnode *ptr)
189 node->parent = (unsigned long)ptr | NODE_TYPE(node);
192 static inline struct node *tnode_get_child(struct tnode *tn, unsigned int i)
194 BUG_ON(i >= 1U << tn->bits);
199 static inline struct node *tnode_get_child_rcu(struct tnode *tn, unsigned int i)
201 struct node *ret = tnode_get_child(tn, i);
203 return rcu_dereference(ret);
206 static inline int tnode_child_length(const struct tnode *tn)
208 return 1 << tn->bits;
211 static inline t_key mask_pfx(t_key k, unsigned short l)
213 return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
216 static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
218 if (offset < KEYLENGTH)
219 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
224 static inline int tkey_equals(t_key a, t_key b)
229 static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
231 if (bits == 0 || offset >= KEYLENGTH)
233 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
234 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
237 static inline int tkey_mismatch(t_key a, int offset, t_key b)
244 while ((diff << i) >> (KEYLENGTH-1) == 0)
250 To understand this stuff, an understanding of keys and all their bits is
251 necessary. Every node in the trie has a key associated with it, but not
252 all of the bits in that key are significant.
254 Consider a node 'n' and its parent 'tp'.
256 If n is a leaf, every bit in its key is significant. Its presence is
257 necessitated by path compression, since during a tree traversal (when
258 searching for a leaf - unless we are doing an insertion) we will completely
259 ignore all skipped bits we encounter. Thus we need to verify, at the end of
260 a potentially successful search, that we have indeed been walking the
263 Note that we can never "miss" the correct key in the tree if present by
264 following the wrong path. Path compression ensures that segments of the key
265 that are the same for all keys with a given prefix are skipped, but the
266 skipped part *is* identical for each node in the subtrie below the skipped
267 bit! trie_insert() in this implementation takes care of that - note the
268 call to tkey_sub_equals() in trie_insert().
270 if n is an internal node - a 'tnode' here, the various parts of its key
271 have many different meanings.
274 _________________________________________________________________
275 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
276 -----------------------------------------------------------------
277 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
279 _________________________________________________________________
280 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
281 -----------------------------------------------------------------
282 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
289 First, let's just ignore the bits that come before the parent tp, that is
290 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
291 not use them for anything.
293 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
294 index into the parent's child array. That is, they will be used to find
295 'n' among tp's children.
297 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
300 All the bits we have seen so far are significant to the node n. The rest
301 of the bits are really not needed or indeed known in n->key.
303 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
304 n's child array, and will of course be different for each child.
307 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
312 static inline void check_tnode(const struct tnode *tn)
314 WARN_ON(tn && tn->pos+tn->bits > 32);
317 static const int halve_threshold = 25;
318 static const int inflate_threshold = 50;
319 static const int halve_threshold_root = 8;
320 static const int inflate_threshold_root = 15;
323 static void __alias_free_mem(struct rcu_head *head)
325 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
326 kmem_cache_free(fn_alias_kmem, fa);
329 static inline void alias_free_mem_rcu(struct fib_alias *fa)
331 call_rcu(&fa->rcu, __alias_free_mem);
334 static void __leaf_free_rcu(struct rcu_head *head)
336 struct leaf *l = container_of(head, struct leaf, rcu);
337 kmem_cache_free(trie_leaf_kmem, l);
340 static void __leaf_info_free_rcu(struct rcu_head *head)
342 kfree(container_of(head, struct leaf_info, rcu));
345 static inline void free_leaf_info(struct leaf_info *leaf)
347 call_rcu(&leaf->rcu, __leaf_info_free_rcu);
350 static struct tnode *tnode_alloc(size_t size)
352 if (size <= PAGE_SIZE)
353 return kzalloc(size, GFP_KERNEL);
355 return __vmalloc(size, GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL);
358 static void __tnode_vfree(struct work_struct *arg)
360 struct tnode *tn = container_of(arg, struct tnode, work);
364 static void __tnode_free_rcu(struct rcu_head *head)
366 struct tnode *tn = container_of(head, struct tnode, rcu);
367 size_t size = sizeof(struct tnode) +
368 (sizeof(struct node *) << tn->bits);
370 if (size <= PAGE_SIZE)
373 INIT_WORK(&tn->work, __tnode_vfree);
374 schedule_work(&tn->work);
378 static inline void tnode_free(struct tnode *tn)
381 struct leaf *l = (struct leaf *) tn;
382 call_rcu_bh(&l->rcu, __leaf_free_rcu);
384 call_rcu(&tn->rcu, __tnode_free_rcu);
387 static struct leaf *leaf_new(void)
389 struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
392 INIT_HLIST_HEAD(&l->list);
397 static struct leaf_info *leaf_info_new(int plen)
399 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
402 INIT_LIST_HEAD(&li->falh);
407 static struct tnode *tnode_new(t_key key, int pos, int bits)
409 size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits);
410 struct tnode *tn = tnode_alloc(sz);
413 tn->parent = T_TNODE;
417 tn->full_children = 0;
418 tn->empty_children = 1<<bits;
421 pr_debug("AT %p s=%u %lu\n", tn, (unsigned int) sizeof(struct tnode),
422 (unsigned long) (sizeof(struct node) << bits));
427 * Check whether a tnode 'n' is "full", i.e. it is an internal node
428 * and no bits are skipped. See discussion in dyntree paper p. 6
431 static inline int tnode_full(const struct tnode *tn, const struct node *n)
433 if (n == NULL || IS_LEAF(n))
436 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
439 static inline void put_child(struct trie *t, struct tnode *tn, int i,
442 tnode_put_child_reorg(tn, i, n, -1);
446 * Add a child at position i overwriting the old value.
447 * Update the value of full_children and empty_children.
450 static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
453 struct node *chi = tn->child[i];
456 BUG_ON(i >= 1<<tn->bits);
458 /* update emptyChildren */
459 if (n == NULL && chi != NULL)
460 tn->empty_children++;
461 else if (n != NULL && chi == NULL)
462 tn->empty_children--;
464 /* update fullChildren */
466 wasfull = tnode_full(tn, chi);
468 isfull = tnode_full(tn, n);
469 if (wasfull && !isfull)
471 else if (!wasfull && isfull)
475 node_set_parent(n, tn);
477 rcu_assign_pointer(tn->child[i], n);
480 static struct node *resize(struct trie *t, struct tnode *tn)
484 struct tnode *old_tn;
485 int inflate_threshold_use;
486 int halve_threshold_use;
492 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
493 tn, inflate_threshold, halve_threshold);
496 if (tn->empty_children == tnode_child_length(tn)) {
501 if (tn->empty_children == tnode_child_length(tn) - 1)
502 for (i = 0; i < tnode_child_length(tn); i++) {
509 /* compress one level */
510 node_set_parent(n, NULL);
515 * Double as long as the resulting node has a number of
516 * nonempty nodes that are above the threshold.
520 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
521 * the Helsinki University of Technology and Matti Tikkanen of Nokia
522 * Telecommunications, page 6:
523 * "A node is doubled if the ratio of non-empty children to all
524 * children in the *doubled* node is at least 'high'."
526 * 'high' in this instance is the variable 'inflate_threshold'. It
527 * is expressed as a percentage, so we multiply it with
528 * tnode_child_length() and instead of multiplying by 2 (since the
529 * child array will be doubled by inflate()) and multiplying
530 * the left-hand side by 100 (to handle the percentage thing) we
531 * multiply the left-hand side by 50.
533 * The left-hand side may look a bit weird: tnode_child_length(tn)
534 * - tn->empty_children is of course the number of non-null children
535 * in the current node. tn->full_children is the number of "full"
536 * children, that is non-null tnodes with a skip value of 0.
537 * All of those will be doubled in the resulting inflated tnode, so
538 * we just count them one extra time here.
540 * A clearer way to write this would be:
542 * to_be_doubled = tn->full_children;
543 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
546 * new_child_length = tnode_child_length(tn) * 2;
548 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
550 * if (new_fill_factor >= inflate_threshold)
552 * ...and so on, tho it would mess up the while () loop.
555 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
559 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
560 * inflate_threshold * new_child_length
562 * expand not_to_be_doubled and to_be_doubled, and shorten:
563 * 100 * (tnode_child_length(tn) - tn->empty_children +
564 * tn->full_children) >= inflate_threshold * new_child_length
566 * expand new_child_length:
567 * 100 * (tnode_child_length(tn) - tn->empty_children +
568 * tn->full_children) >=
569 * inflate_threshold * tnode_child_length(tn) * 2
572 * 50 * (tn->full_children + tnode_child_length(tn) -
573 * tn->empty_children) >= inflate_threshold *
574 * tnode_child_length(tn)
580 /* Keep root node larger */
583 inflate_threshold_use = inflate_threshold_root;
585 inflate_threshold_use = inflate_threshold;
589 while ((tn->full_children > 0 && max_resize-- &&
590 50 * (tn->full_children + tnode_child_length(tn)
591 - tn->empty_children)
592 >= inflate_threshold_use * tnode_child_length(tn))) {
599 #ifdef CONFIG_IP_FIB_TRIE_STATS
600 t->stats.resize_node_skipped++;
606 if (max_resize < 0) {
608 pr_warning("Fix inflate_threshold_root."
609 " Now=%d size=%d bits\n",
610 inflate_threshold_root, tn->bits);
612 pr_warning("Fix inflate_threshold."
613 " Now=%d size=%d bits\n",
614 inflate_threshold, tn->bits);
620 * Halve as long as the number of empty children in this
621 * node is above threshold.
625 /* Keep root node larger */
628 halve_threshold_use = halve_threshold_root;
630 halve_threshold_use = halve_threshold;
634 while (tn->bits > 1 && max_resize-- &&
635 100 * (tnode_child_length(tn) - tn->empty_children) <
636 halve_threshold_use * tnode_child_length(tn)) {
642 #ifdef CONFIG_IP_FIB_TRIE_STATS
643 t->stats.resize_node_skipped++;
649 if (max_resize < 0) {
651 pr_warning("Fix halve_threshold_root."
652 " Now=%d size=%d bits\n",
653 halve_threshold_root, tn->bits);
655 pr_warning("Fix halve_threshold."
656 " Now=%d size=%d bits\n",
657 halve_threshold, tn->bits);
660 /* Only one child remains */
661 if (tn->empty_children == tnode_child_length(tn) - 1)
662 for (i = 0; i < tnode_child_length(tn); i++) {
669 /* compress one level */
671 node_set_parent(n, NULL);
676 return (struct node *) tn;
679 static struct tnode *inflate(struct trie *t, struct tnode *tn)
681 struct tnode *oldtnode = tn;
682 int olen = tnode_child_length(tn);
685 pr_debug("In inflate\n");
687 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
690 return ERR_PTR(-ENOMEM);
693 * Preallocate and store tnodes before the actual work so we
694 * don't get into an inconsistent state if memory allocation
695 * fails. In case of failure we return the oldnode and inflate
696 * of tnode is ignored.
699 for (i = 0; i < olen; i++) {
702 inode = (struct tnode *) tnode_get_child(oldtnode, i);
705 inode->pos == oldtnode->pos + oldtnode->bits &&
707 struct tnode *left, *right;
708 t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
710 left = tnode_new(inode->key&(~m), inode->pos + 1,
715 right = tnode_new(inode->key|m, inode->pos + 1,
723 put_child(t, tn, 2*i, (struct node *) left);
724 put_child(t, tn, 2*i+1, (struct node *) right);
728 for (i = 0; i < olen; i++) {
730 struct node *node = tnode_get_child(oldtnode, i);
731 struct tnode *left, *right;
738 /* A leaf or an internal node with skipped bits */
740 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
741 tn->pos + tn->bits - 1) {
742 if (tkey_extract_bits(node->key,
743 oldtnode->pos + oldtnode->bits,
745 put_child(t, tn, 2*i, node);
747 put_child(t, tn, 2*i+1, node);
751 /* An internal node with two children */
752 inode = (struct tnode *) node;
754 if (inode->bits == 1) {
755 put_child(t, tn, 2*i, inode->child[0]);
756 put_child(t, tn, 2*i+1, inode->child[1]);
762 /* An internal node with more than two children */
764 /* We will replace this node 'inode' with two new
765 * ones, 'left' and 'right', each with half of the
766 * original children. The two new nodes will have
767 * a position one bit further down the key and this
768 * means that the "significant" part of their keys
769 * (see the discussion near the top of this file)
770 * will differ by one bit, which will be "0" in
771 * left's key and "1" in right's key. Since we are
772 * moving the key position by one step, the bit that
773 * we are moving away from - the bit at position
774 * (inode->pos) - is the one that will differ between
775 * left and right. So... we synthesize that bit in the
777 * The mask 'm' below will be a single "one" bit at
778 * the position (inode->pos)
781 /* Use the old key, but set the new significant
785 left = (struct tnode *) tnode_get_child(tn, 2*i);
786 put_child(t, tn, 2*i, NULL);
790 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
791 put_child(t, tn, 2*i+1, NULL);
795 size = tnode_child_length(left);
796 for (j = 0; j < size; j++) {
797 put_child(t, left, j, inode->child[j]);
798 put_child(t, right, j, inode->child[j + size]);
800 put_child(t, tn, 2*i, resize(t, left));
801 put_child(t, tn, 2*i+1, resize(t, right));
805 tnode_free(oldtnode);
809 int size = tnode_child_length(tn);
812 for (j = 0; j < size; j++)
814 tnode_free((struct tnode *)tn->child[j]);
818 return ERR_PTR(-ENOMEM);
822 static struct tnode *halve(struct trie *t, struct tnode *tn)
824 struct tnode *oldtnode = tn;
825 struct node *left, *right;
827 int olen = tnode_child_length(tn);
829 pr_debug("In halve\n");
831 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
834 return ERR_PTR(-ENOMEM);
837 * Preallocate and store tnodes before the actual work so we
838 * don't get into an inconsistent state if memory allocation
839 * fails. In case of failure we return the oldnode and halve
840 * of tnode is ignored.
843 for (i = 0; i < olen; i += 2) {
844 left = tnode_get_child(oldtnode, i);
845 right = tnode_get_child(oldtnode, i+1);
847 /* Two nonempty children */
851 newn = tnode_new(left->key, tn->pos + tn->bits, 1);
856 put_child(t, tn, i/2, (struct node *)newn);
861 for (i = 0; i < olen; i += 2) {
862 struct tnode *newBinNode;
864 left = tnode_get_child(oldtnode, i);
865 right = tnode_get_child(oldtnode, i+1);
867 /* At least one of the children is empty */
869 if (right == NULL) /* Both are empty */
871 put_child(t, tn, i/2, right);
876 put_child(t, tn, i/2, left);
880 /* Two nonempty children */
881 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
882 put_child(t, tn, i/2, NULL);
883 put_child(t, newBinNode, 0, left);
884 put_child(t, newBinNode, 1, right);
885 put_child(t, tn, i/2, resize(t, newBinNode));
887 tnode_free(oldtnode);
891 int size = tnode_child_length(tn);
894 for (j = 0; j < size; j++)
896 tnode_free((struct tnode *)tn->child[j]);
900 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 hlist_node *node;
911 struct leaf_info *li;
913 hlist_for_each_entry_rcu(li, node, head, hlist)
914 if (li->plen == plen)
920 static inline struct list_head *get_fa_head(struct leaf *l, int plen)
922 struct leaf_info *li = find_leaf_info(l, plen);
930 static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
932 struct leaf_info *li = NULL, *last = NULL;
933 struct hlist_node *node;
935 if (hlist_empty(head)) {
936 hlist_add_head_rcu(&new->hlist, head);
938 hlist_for_each_entry(li, node, head, hlist) {
939 if (new->plen > li->plen)
945 hlist_add_after_rcu(&last->hlist, &new->hlist);
947 hlist_add_before_rcu(&new->hlist, &li->hlist);
951 /* rcu_read_lock needs to be hold by caller from readside */
954 fib_find_node(struct trie *t, u32 key)
961 n = rcu_dereference(t->trie);
963 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
964 tn = (struct tnode *) n;
968 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
969 pos = tn->pos + tn->bits;
970 n = tnode_get_child_rcu(tn,
971 tkey_extract_bits(key,
977 /* Case we have found a leaf. Compare prefixes */
979 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
980 return (struct leaf *)n;
985 static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
988 t_key cindex, key = tn->key;
991 while (tn != NULL && (tp = node_parent((struct 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, (struct tnode *)tn);
996 tnode_put_child_reorg((struct tnode *)tp, cindex,
997 (struct node *)tn, wasfull);
999 tp = node_parent((struct node *) tn);
1005 /* Handle last (top) tnode */
1007 tn = (struct tnode *)resize(t, (struct tnode *)tn);
1009 return (struct node *)tn;
1012 /* only used from updater-side */
1014 static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
1017 struct tnode *tp = NULL, *tn = NULL;
1021 struct list_head *fa_head = NULL;
1022 struct leaf_info *li;
1028 /* If we point to NULL, stop. Either the tree is empty and we should
1029 * just put a new leaf in if, or we have reached an empty child slot,
1030 * and we should just put our new leaf in that.
1031 * If we point to a T_TNODE, check if it matches our key. Note that
1032 * a T_TNODE might be skipping any number of bits - its 'pos' need
1033 * not be the parent's 'pos'+'bits'!
1035 * If it does match the current key, get pos/bits from it, extract
1036 * the index from our key, push the T_TNODE and walk the tree.
1038 * If it doesn't, we have to replace it with a new T_TNODE.
1040 * If we point to a T_LEAF, it might or might not have the same key
1041 * as we do. If it does, just change the value, update the T_LEAF's
1042 * value, and return it.
1043 * If it doesn't, we need to replace it with a T_TNODE.
1046 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1047 tn = (struct tnode *) n;
1051 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1053 pos = tn->pos + tn->bits;
1054 n = tnode_get_child(tn,
1055 tkey_extract_bits(key,
1059 BUG_ON(n && node_parent(n) != tn);
1065 * n ----> NULL, LEAF or TNODE
1067 * tp is n's (parent) ----> NULL or TNODE
1070 BUG_ON(tp && IS_LEAF(tp));
1072 /* Case 1: n is a leaf. Compare prefixes */
1074 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1075 l = (struct leaf *) n;
1076 li = leaf_info_new(plen);
1081 fa_head = &li->falh;
1082 insert_leaf_info(&l->list, li);
1091 li = leaf_info_new(plen);
1094 tnode_free((struct tnode *) l);
1098 fa_head = &li->falh;
1099 insert_leaf_info(&l->list, li);
1101 if (t->trie && n == NULL) {
1102 /* Case 2: n is NULL, and will just insert a new leaf */
1104 node_set_parent((struct node *)l, tp);
1106 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1107 put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
1109 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1111 * Add a new tnode here
1112 * first tnode need some special handling
1116 pos = tp->pos+tp->bits;
1121 newpos = tkey_mismatch(key, pos, n->key);
1122 tn = tnode_new(n->key, newpos, 1);
1125 tn = tnode_new(key, newpos, 1); /* First tnode */
1130 tnode_free((struct tnode *) l);
1134 node_set_parent((struct node *)tn, tp);
1136 missbit = tkey_extract_bits(key, newpos, 1);
1137 put_child(t, tn, missbit, (struct node *)l);
1138 put_child(t, tn, 1-missbit, n);
1141 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1142 put_child(t, (struct tnode *)tp, cindex,
1145 rcu_assign_pointer(t->trie, (struct node *)tn);
1150 if (tp && tp->pos + tp->bits > 32)
1151 pr_warning("fib_trie"
1152 " tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1153 tp, tp->pos, tp->bits, key, plen);
1155 /* Rebalance the trie */
1157 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
1163 * Caller must hold RTNL.
1165 static int fn_trie_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_scope == cfg->fc_scope &&
1239 fa->fa_info == fi) {
1245 if (cfg->fc_nlflags & NLM_F_REPLACE) {
1246 struct fib_info *fi_drop;
1256 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1260 fi_drop = fa->fa_info;
1261 new_fa->fa_tos = fa->fa_tos;
1262 new_fa->fa_info = fi;
1263 new_fa->fa_type = cfg->fc_type;
1264 new_fa->fa_scope = cfg->fc_scope;
1265 state = fa->fa_state;
1266 new_fa->fa_state = state & ~FA_S_ACCESSED;
1268 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1269 alias_free_mem_rcu(fa);
1271 fib_release_info(fi_drop);
1272 if (state & FA_S_ACCESSED)
1274 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1275 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1279 /* Error if we find a perfect match which
1280 * uses the same scope, type, and nexthop
1286 if (!(cfg->fc_nlflags & NLM_F_APPEND))
1290 if (!(cfg->fc_nlflags & NLM_F_CREATE))
1294 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1298 new_fa->fa_info = fi;
1299 new_fa->fa_tos = tos;
1300 new_fa->fa_type = cfg->fc_type;
1301 new_fa->fa_scope = cfg->fc_scope;
1302 new_fa->fa_state = 0;
1304 * Insert new entry to the list.
1308 fa_head = fib_insert_node(t, key, plen);
1309 if (unlikely(!fa_head)) {
1311 goto out_free_new_fa;
1315 list_add_tail_rcu(&new_fa->fa_list,
1316 (fa ? &fa->fa_list : fa_head));
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 trie *t, struct leaf *l,
1334 t_key key, const struct flowi *flp,
1335 struct fib_result *res)
1337 struct leaf_info *li;
1338 struct hlist_head *hhead = &l->list;
1339 struct hlist_node *node;
1341 hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1343 int plen = li->plen;
1344 __be32 mask = inet_make_mask(plen);
1346 if (l->key != (key & ntohl(mask)))
1349 err = fib_semantic_match(&li->falh, flp, res,
1350 htonl(l->key), mask, plen);
1352 #ifdef CONFIG_IP_FIB_TRIE_STATS
1354 t->stats.semantic_match_passed++;
1356 t->stats.semantic_match_miss++;
1365 static int fn_trie_lookup(struct fib_table *tb, const struct flowi *flp,
1366 struct fib_result *res)
1368 struct trie *t = (struct trie *) tb->tb_data;
1373 t_key key = ntohl(flp->fl4_dst);
1376 int current_prefix_length = KEYLENGTH;
1378 t_key node_prefix, key_prefix, pref_mismatch;
1383 n = rcu_dereference(t->trie);
1387 #ifdef CONFIG_IP_FIB_TRIE_STATS
1393 plen = check_leaf(t, (struct leaf *)n, key, flp, res);
1400 pn = (struct tnode *) n;
1408 cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1411 n = tnode_get_child(pn, cindex);
1414 #ifdef CONFIG_IP_FIB_TRIE_STATS
1415 t->stats.null_node_hit++;
1421 plen = check_leaf(t, (struct leaf *)n, key, flp, res);
1429 cn = (struct tnode *)n;
1432 * It's a tnode, and we can do some extra checks here if we
1433 * like, to avoid descending into a dead-end branch.
1434 * This tnode is in the parent's child array at index
1435 * key[p_pos..p_pos+p_bits] but potentially with some bits
1436 * chopped off, so in reality the index may be just a
1437 * subprefix, padded with zero at the end.
1438 * We can also take a look at any skipped bits in this
1439 * tnode - everything up to p_pos is supposed to be ok,
1440 * and the non-chopped bits of the index (se previous
1441 * paragraph) are also guaranteed ok, but the rest is
1442 * considered unknown.
1444 * The skipped bits are key[pos+bits..cn->pos].
1447 /* If current_prefix_length < pos+bits, we are already doing
1448 * actual prefix matching, which means everything from
1449 * pos+(bits-chopped_off) onward must be zero along some
1450 * branch of this subtree - otherwise there is *no* valid
1451 * prefix present. Here we can only check the skipped
1452 * bits. Remember, since we have already indexed into the
1453 * parent's child array, we know that the bits we chopped of
1457 /* NOTA BENE: Checking only skipped bits
1458 for the new node here */
1460 if (current_prefix_length < pos+bits) {
1461 if (tkey_extract_bits(cn->key, current_prefix_length,
1462 cn->pos - current_prefix_length)
1468 * If chopped_off=0, the index is fully validated and we
1469 * only need to look at the skipped bits for this, the new,
1470 * tnode. What we actually want to do is to find out if
1471 * these skipped bits match our key perfectly, or if we will
1472 * have to count on finding a matching prefix further down,
1473 * because if we do, we would like to have some way of
1474 * verifying the existence of such a prefix at this point.
1477 /* The only thing we can do at this point is to verify that
1478 * any such matching prefix can indeed be a prefix to our
1479 * key, and if the bits in the node we are inspecting that
1480 * do not match our key are not ZERO, this cannot be true.
1481 * Thus, find out where there is a mismatch (before cn->pos)
1482 * and verify that all the mismatching bits are zero in the
1487 * Note: We aren't very concerned about the piece of
1488 * the key that precede pn->pos+pn->bits, since these
1489 * have already been checked. The bits after cn->pos
1490 * aren't checked since these are by definition
1491 * "unknown" at this point. Thus, what we want to see
1492 * is if we are about to enter the "prefix matching"
1493 * state, and in that case verify that the skipped
1494 * bits that will prevail throughout this subtree are
1495 * zero, as they have to be if we are to find a
1499 node_prefix = mask_pfx(cn->key, cn->pos);
1500 key_prefix = mask_pfx(key, cn->pos);
1501 pref_mismatch = key_prefix^node_prefix;
1505 * In short: If skipped bits in this node do not match
1506 * the search key, enter the "prefix matching"
1509 if (pref_mismatch) {
1510 while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
1512 pref_mismatch = pref_mismatch << 1;
1514 key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);
1516 if (key_prefix != 0)
1519 if (current_prefix_length >= cn->pos)
1520 current_prefix_length = mp;
1523 pn = (struct tnode *)n; /* Descend */
1530 /* As zero don't change the child key (cindex) */
1531 while ((chopped_off <= pn->bits)
1532 && !(cindex & (1<<(chopped_off-1))))
1535 /* Decrease current_... with bits chopped off */
1536 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1537 current_prefix_length = pn->pos + pn->bits
1541 * Either we do the actual chop off according or if we have
1542 * chopped off all bits in this tnode walk up to our parent.
1545 if (chopped_off <= pn->bits) {
1546 cindex &= ~(1 << (chopped_off-1));
1548 struct tnode *parent = node_parent((struct node *) pn);
1552 /* Get Child's index */
1553 cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1557 #ifdef CONFIG_IP_FIB_TRIE_STATS
1558 t->stats.backtrack++;
1571 * Remove the leaf and return parent.
1573 static void trie_leaf_remove(struct trie *t, struct leaf *l)
1575 struct tnode *tp = node_parent((struct node *) l);
1577 pr_debug("entering trie_leaf_remove(%p)\n", l);
1580 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1581 put_child(t, (struct tnode *)tp, cindex, NULL);
1582 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
1584 rcu_assign_pointer(t->trie, NULL);
1586 tnode_free((struct tnode *) l);
1590 * Caller must hold RTNL.
1592 static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
1594 struct trie *t = (struct trie *) tb->tb_data;
1596 int plen = cfg->fc_dst_len;
1597 u8 tos = cfg->fc_tos;
1598 struct fib_alias *fa, *fa_to_delete;
1599 struct list_head *fa_head;
1601 struct leaf_info *li;
1606 key = ntohl(cfg->fc_dst);
1607 mask = ntohl(inet_make_mask(plen));
1613 l = fib_find_node(t, key);
1618 fa_head = get_fa_head(l, plen);
1619 fa = fib_find_alias(fa_head, tos, 0);
1624 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1626 fa_to_delete = NULL;
1627 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1628 list_for_each_entry_continue(fa, fa_head, fa_list) {
1629 struct fib_info *fi = fa->fa_info;
1631 if (fa->fa_tos != tos)
1634 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1635 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1636 fa->fa_scope == cfg->fc_scope) &&
1637 (!cfg->fc_protocol ||
1638 fi->fib_protocol == cfg->fc_protocol) &&
1639 fib_nh_match(cfg, fi) == 0) {
1649 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1650 &cfg->fc_nlinfo, 0);
1652 l = fib_find_node(t, key);
1653 li = find_leaf_info(l, plen);
1655 list_del_rcu(&fa->fa_list);
1657 if (list_empty(fa_head)) {
1658 hlist_del_rcu(&li->hlist);
1662 if (hlist_empty(&l->list))
1663 trie_leaf_remove(t, l);
1665 if (fa->fa_state & FA_S_ACCESSED)
1668 fib_release_info(fa->fa_info);
1669 alias_free_mem_rcu(fa);
1673 static int trie_flush_list(struct list_head *head)
1675 struct fib_alias *fa, *fa_node;
1678 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1679 struct fib_info *fi = fa->fa_info;
1681 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1682 list_del_rcu(&fa->fa_list);
1683 fib_release_info(fa->fa_info);
1684 alias_free_mem_rcu(fa);
1691 static int trie_flush_leaf(struct leaf *l)
1694 struct hlist_head *lih = &l->list;
1695 struct hlist_node *node, *tmp;
1696 struct leaf_info *li = NULL;
1698 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
1699 found += trie_flush_list(&li->falh);
1701 if (list_empty(&li->falh)) {
1702 hlist_del_rcu(&li->hlist);
1710 * Scan for the next right leaf starting at node p->child[idx]
1711 * Since we have back pointer, no recursion necessary.
1713 static struct leaf *leaf_walk_rcu(struct tnode *p, struct node *c)
1719 idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1723 while (idx < 1u << p->bits) {
1724 c = tnode_get_child_rcu(p, idx++);
1729 prefetch(p->child[idx]);
1730 return (struct leaf *) c;
1733 /* Rescan start scanning in new node */
1734 p = (struct tnode *) c;
1738 /* Node empty, walk back up to parent */
1739 c = (struct node *) p;
1740 } while ( (p = node_parent_rcu(c)) != NULL);
1742 return NULL; /* Root of trie */
1745 static struct leaf *trie_firstleaf(struct trie *t)
1747 struct tnode *n = (struct tnode *) rcu_dereference(t->trie);
1752 if (IS_LEAF(n)) /* trie is just a leaf */
1753 return (struct leaf *) n;
1755 return leaf_walk_rcu(n, NULL);
1758 static struct leaf *trie_nextleaf(struct leaf *l)
1760 struct node *c = (struct node *) l;
1761 struct tnode *p = node_parent(c);
1764 return NULL; /* trie with just one leaf */
1766 return leaf_walk_rcu(p, c);
1769 static struct leaf *trie_leafindex(struct trie *t, int index)
1771 struct leaf *l = trie_firstleaf(t);
1773 while (l && index-- > 0)
1774 l = trie_nextleaf(l);
1781 * Caller must hold RTNL.
1783 static int fn_trie_flush(struct fib_table *tb)
1785 struct trie *t = (struct trie *) tb->tb_data;
1786 struct leaf *l, *ll = NULL;
1789 for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1790 found += trie_flush_leaf(l);
1792 if (ll && hlist_empty(&ll->list))
1793 trie_leaf_remove(t, ll);
1797 if (ll && hlist_empty(&ll->list))
1798 trie_leaf_remove(t, ll);
1800 pr_debug("trie_flush found=%d\n", found);
1804 static void fn_trie_select_default(struct fib_table *tb,
1805 const struct flowi *flp,
1806 struct fib_result *res)
1808 struct trie *t = (struct trie *) tb->tb_data;
1809 int order, last_idx;
1810 struct fib_info *fi = NULL;
1811 struct fib_info *last_resort;
1812 struct fib_alias *fa = NULL;
1813 struct list_head *fa_head;
1822 l = fib_find_node(t, 0);
1826 fa_head = get_fa_head(l, 0);
1830 if (list_empty(fa_head))
1833 list_for_each_entry_rcu(fa, fa_head, fa_list) {
1834 struct fib_info *next_fi = fa->fa_info;
1836 if (fa->fa_scope != res->scope ||
1837 fa->fa_type != RTN_UNICAST)
1840 if (next_fi->fib_priority > res->fi->fib_priority)
1842 if (!next_fi->fib_nh[0].nh_gw ||
1843 next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
1845 fa->fa_state |= FA_S_ACCESSED;
1848 if (next_fi != res->fi)
1850 } else if (!fib_detect_death(fi, order, &last_resort,
1851 &last_idx, tb->tb_default)) {
1852 fib_result_assign(res, fi);
1853 tb->tb_default = order;
1859 if (order <= 0 || fi == NULL) {
1860 tb->tb_default = -1;
1864 if (!fib_detect_death(fi, order, &last_resort, &last_idx,
1866 fib_result_assign(res, fi);
1867 tb->tb_default = order;
1871 fib_result_assign(res, last_resort);
1872 tb->tb_default = last_idx;
1877 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1878 struct fib_table *tb,
1879 struct sk_buff *skb, struct netlink_callback *cb)
1882 struct fib_alias *fa;
1883 __be32 xkey = htonl(key);
1888 /* rcu_read_lock is hold by caller */
1890 list_for_each_entry_rcu(fa, fah, fa_list) {
1896 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1905 fa->fa_info, NLM_F_MULTI) < 0) {
1915 static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1916 struct sk_buff *skb, struct netlink_callback *cb)
1918 struct leaf_info *li;
1919 struct hlist_node *node;
1925 /* rcu_read_lock is hold by caller */
1926 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
1935 if (list_empty(&li->falh))
1938 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1949 static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb,
1950 struct netlink_callback *cb)
1953 struct trie *t = (struct trie *) tb->tb_data;
1954 t_key key = cb->args[2];
1955 int count = cb->args[3];
1958 /* Dump starting at last key.
1959 * Note: 0.0.0.0/0 (ie default) is first key.
1962 l = trie_firstleaf(t);
1964 /* Normally, continue from last key, but if that is missing
1965 * fallback to using slow rescan
1967 l = fib_find_node(t, key);
1969 l = trie_leafindex(t, count);
1973 cb->args[2] = l->key;
1974 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1975 cb->args[3] = count;
1981 l = trie_nextleaf(l);
1982 memset(&cb->args[4], 0,
1983 sizeof(cb->args) - 4*sizeof(cb->args[0]));
1985 cb->args[3] = count;
1991 void __init fib_hash_init(void)
1993 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1994 sizeof(struct fib_alias),
1995 0, SLAB_PANIC, NULL);
1997 trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1998 max(sizeof(struct leaf),
1999 sizeof(struct leaf_info)),
2000 0, SLAB_PANIC, NULL);
2004 /* Fix more generic FIB names for init later */
2005 struct fib_table *fib_hash_table(u32 id)
2007 struct fib_table *tb;
2010 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
2016 tb->tb_default = -1;
2017 tb->tb_lookup = fn_trie_lookup;
2018 tb->tb_insert = fn_trie_insert;
2019 tb->tb_delete = fn_trie_delete;
2020 tb->tb_flush = fn_trie_flush;
2021 tb->tb_select_default = fn_trie_select_default;
2022 tb->tb_dump = fn_trie_dump;
2024 t = (struct trie *) tb->tb_data;
2025 memset(t, 0, sizeof(*t));
2027 if (id == RT_TABLE_LOCAL)
2028 pr_info("IPv4 FIB: Using LC-trie version %s\n", VERSION);
2033 #ifdef CONFIG_PROC_FS
2034 /* Depth first Trie walk iterator */
2035 struct fib_trie_iter {
2036 struct seq_net_private p;
2037 struct fib_table *tb;
2038 struct tnode *tnode;
2043 static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
2045 struct tnode *tn = iter->tnode;
2046 unsigned cindex = iter->index;
2049 /* A single entry routing table */
2053 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2054 iter->tnode, iter->index, iter->depth);
2056 while (cindex < (1<<tn->bits)) {
2057 struct node *n = tnode_get_child_rcu(tn, cindex);
2062 iter->index = cindex + 1;
2064 /* push down one level */
2065 iter->tnode = (struct tnode *) n;
2075 /* Current node exhausted, pop back up */
2076 p = node_parent_rcu((struct node *)tn);
2078 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2088 static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
2096 n = rcu_dereference(t->trie);
2101 iter->tnode = (struct tnode *) n;
2113 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2116 struct fib_trie_iter iter;
2118 memset(s, 0, sizeof(*s));
2121 for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2123 struct leaf *l = (struct leaf *)n;
2124 struct leaf_info *li;
2125 struct hlist_node *tmp;
2128 s->totdepth += iter.depth;
2129 if (iter.depth > s->maxdepth)
2130 s->maxdepth = iter.depth;
2132 hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
2135 const struct tnode *tn = (const struct tnode *) n;
2139 if (tn->bits < MAX_STAT_DEPTH)
2140 s->nodesizes[tn->bits]++;
2142 for (i = 0; i < (1<<tn->bits); i++)
2151 * This outputs /proc/net/fib_triestats
2153 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2155 unsigned i, max, pointers, bytes, avdepth;
2158 avdepth = stat->totdepth*100 / stat->leaves;
2162 seq_printf(seq, "\tAver depth: %u.%02d\n",
2163 avdepth / 100, avdepth % 100);
2164 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
2166 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
2167 bytes = sizeof(struct leaf) * stat->leaves;
2169 seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes);
2170 bytes += sizeof(struct leaf_info) * stat->prefixes;
2172 seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2173 bytes += sizeof(struct tnode) * stat->tnodes;
2175 max = MAX_STAT_DEPTH;
2176 while (max > 0 && stat->nodesizes[max-1] == 0)
2180 for (i = 1; i <= max; i++)
2181 if (stat->nodesizes[i] != 0) {
2182 seq_printf(seq, " %u: %u", i, stat->nodesizes[i]);
2183 pointers += (1<<i) * stat->nodesizes[i];
2185 seq_putc(seq, '\n');
2186 seq_printf(seq, "\tPointers: %u\n", pointers);
2188 bytes += sizeof(struct node *) * pointers;
2189 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2190 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
2193 #ifdef CONFIG_IP_FIB_TRIE_STATS
2194 static void trie_show_usage(struct seq_file *seq,
2195 const struct trie_use_stats *stats)
2197 seq_printf(seq, "\nCounters:\n---------\n");
2198 seq_printf(seq, "gets = %u\n", stats->gets);
2199 seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2200 seq_printf(seq, "semantic match passed = %u\n",
2201 stats->semantic_match_passed);
2202 seq_printf(seq, "semantic match miss = %u\n",
2203 stats->semantic_match_miss);
2204 seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2205 seq_printf(seq, "skipped node resize = %u\n\n",
2206 stats->resize_node_skipped);
2208 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2210 static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2212 if (tb->tb_id == RT_TABLE_LOCAL)
2213 seq_puts(seq, "Local:\n");
2214 else if (tb->tb_id == RT_TABLE_MAIN)
2215 seq_puts(seq, "Main:\n");
2217 seq_printf(seq, "Id %d:\n", tb->tb_id);
2221 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2223 struct net *net = (struct net *)seq->private;
2227 "Basic info: size of leaf:"
2228 " %Zd bytes, size of tnode: %Zd bytes.\n",
2229 sizeof(struct leaf), sizeof(struct tnode));
2231 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2232 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2233 struct hlist_node *node;
2234 struct fib_table *tb;
2236 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2237 struct trie *t = (struct trie *) tb->tb_data;
2238 struct trie_stat stat;
2243 fib_table_print(seq, tb);
2245 trie_collect_stats(t, &stat);
2246 trie_show_stats(seq, &stat);
2247 #ifdef CONFIG_IP_FIB_TRIE_STATS
2248 trie_show_usage(seq, &t->stats);
2256 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2261 net = get_proc_net(inode);
2264 err = single_open(file, fib_triestat_seq_show, net);
2272 static int fib_triestat_seq_release(struct inode *ino, struct file *f)
2274 struct seq_file *seq = f->private_data;
2275 put_net(seq->private);
2276 return single_release(ino, f);
2279 static const struct file_operations fib_triestat_fops = {
2280 .owner = THIS_MODULE,
2281 .open = fib_triestat_seq_open,
2283 .llseek = seq_lseek,
2284 .release = fib_triestat_seq_release,
2287 static struct node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2289 struct fib_trie_iter *iter = seq->private;
2290 struct net *net = seq_file_net(seq);
2294 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2295 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2296 struct hlist_node *node;
2297 struct fib_table *tb;
2299 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2302 for (n = fib_trie_get_first(iter,
2303 (struct trie *) tb->tb_data);
2304 n; n = fib_trie_get_next(iter))
2315 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2319 return fib_trie_get_idx(seq, *pos);
2322 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2324 struct fib_trie_iter *iter = seq->private;
2325 struct net *net = seq_file_net(seq);
2326 struct fib_table *tb = iter->tb;
2327 struct hlist_node *tb_node;
2332 /* next node in same table */
2333 n = fib_trie_get_next(iter);
2337 /* walk rest of this hash chain */
2338 h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2339 while ( (tb_node = rcu_dereference(tb->tb_hlist.next)) ) {
2340 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2341 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2346 /* new hash chain */
2347 while (++h < FIB_TABLE_HASHSZ) {
2348 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2349 hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) {
2350 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2362 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2368 static void seq_indent(struct seq_file *seq, int n)
2370 while (n-- > 0) seq_puts(seq, " ");
2373 static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2376 case RT_SCOPE_UNIVERSE: return "universe";
2377 case RT_SCOPE_SITE: return "site";
2378 case RT_SCOPE_LINK: return "link";
2379 case RT_SCOPE_HOST: return "host";
2380 case RT_SCOPE_NOWHERE: return "nowhere";
2382 snprintf(buf, len, "scope=%d", s);
2387 static const char *rtn_type_names[__RTN_MAX] = {
2388 [RTN_UNSPEC] = "UNSPEC",
2389 [RTN_UNICAST] = "UNICAST",
2390 [RTN_LOCAL] = "LOCAL",
2391 [RTN_BROADCAST] = "BROADCAST",
2392 [RTN_ANYCAST] = "ANYCAST",
2393 [RTN_MULTICAST] = "MULTICAST",
2394 [RTN_BLACKHOLE] = "BLACKHOLE",
2395 [RTN_UNREACHABLE] = "UNREACHABLE",
2396 [RTN_PROHIBIT] = "PROHIBIT",
2397 [RTN_THROW] = "THROW",
2399 [RTN_XRESOLVE] = "XRESOLVE",
2402 static inline const char *rtn_type(char *buf, size_t len, unsigned t)
2404 if (t < __RTN_MAX && rtn_type_names[t])
2405 return rtn_type_names[t];
2406 snprintf(buf, len, "type %u", t);
2410 /* Pretty print the trie */
2411 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2413 const struct fib_trie_iter *iter = seq->private;
2416 if (!node_parent_rcu(n))
2417 fib_table_print(seq, iter->tb);
2420 struct tnode *tn = (struct tnode *) n;
2421 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2423 seq_indent(seq, iter->depth-1);
2424 seq_printf(seq, " +-- %d.%d.%d.%d/%d %d %d %d\n",
2425 NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
2426 tn->empty_children);
2429 struct leaf *l = (struct leaf *) n;
2430 struct leaf_info *li;
2431 struct hlist_node *node;
2432 __be32 val = htonl(l->key);
2434 seq_indent(seq, iter->depth);
2435 seq_printf(seq, " |-- %d.%d.%d.%d\n", NIPQUAD(val));
2437 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2438 struct fib_alias *fa;
2440 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2441 char buf1[32], buf2[32];
2443 seq_indent(seq, iter->depth+1);
2444 seq_printf(seq, " /%d %s %s", li->plen,
2445 rtn_scope(buf1, sizeof(buf1),
2447 rtn_type(buf2, sizeof(buf2),
2450 seq_printf(seq, " tos=%d", fa->fa_tos);
2451 seq_putc(seq, '\n');
2459 static const struct seq_operations fib_trie_seq_ops = {
2460 .start = fib_trie_seq_start,
2461 .next = fib_trie_seq_next,
2462 .stop = fib_trie_seq_stop,
2463 .show = fib_trie_seq_show,
2466 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2468 return seq_open_net(inode, file, &fib_trie_seq_ops,
2469 sizeof(struct fib_trie_iter));
2472 static const struct file_operations fib_trie_fops = {
2473 .owner = THIS_MODULE,
2474 .open = fib_trie_seq_open,
2476 .llseek = seq_lseek,
2477 .release = seq_release_net,
2480 struct fib_route_iter {
2481 struct seq_net_private p;
2482 struct trie *main_trie;
2487 static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2489 struct leaf *l = NULL;
2490 struct trie *t = iter->main_trie;
2492 /* use cache location of last found key */
2493 if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2497 l = trie_firstleaf(t);
2500 while (l && pos-- > 0) {
2502 l = trie_nextleaf(l);
2506 iter->key = pos; /* remember it */
2508 iter->pos = 0; /* forget it */
2513 static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2516 struct fib_route_iter *iter = seq->private;
2517 struct fib_table *tb;
2520 tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2524 iter->main_trie = (struct trie *) tb->tb_data;
2526 return SEQ_START_TOKEN;
2528 return fib_route_get_idx(iter, *pos - 1);
2531 static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2533 struct fib_route_iter *iter = seq->private;
2537 if (v == SEQ_START_TOKEN) {
2539 l = trie_firstleaf(iter->main_trie);
2542 l = trie_nextleaf(l);
2552 static void fib_route_seq_stop(struct seq_file *seq, void *v)
2558 static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2560 static unsigned type2flags[RTN_MAX + 1] = {
2561 [7] = RTF_REJECT, [8] = RTF_REJECT,
2563 unsigned flags = type2flags[type];
2565 if (fi && fi->fib_nh->nh_gw)
2566 flags |= RTF_GATEWAY;
2567 if (mask == htonl(0xFFFFFFFF))
2574 * This outputs /proc/net/route.
2575 * The format of the file is not supposed to be changed
2576 * and needs to be same as fib_hash output to avoid breaking
2579 static int fib_route_seq_show(struct seq_file *seq, void *v)
2582 struct leaf_info *li;
2583 struct hlist_node *node;
2585 if (v == SEQ_START_TOKEN) {
2586 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2587 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2592 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2593 struct fib_alias *fa;
2594 __be32 mask, prefix;
2596 mask = inet_make_mask(li->plen);
2597 prefix = htonl(l->key);
2599 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2600 const struct fib_info *fi = fa->fa_info;
2601 unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2604 if (fa->fa_type == RTN_BROADCAST
2605 || fa->fa_type == RTN_MULTICAST)
2609 snprintf(bf, sizeof(bf),
2610 "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2611 fi->fib_dev ? fi->fib_dev->name : "*",
2613 fi->fib_nh->nh_gw, flags, 0, 0,
2617 fi->fib_advmss + 40 : 0),
2621 snprintf(bf, sizeof(bf),
2622 "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2623 prefix, 0, flags, 0, 0, 0,
2626 seq_printf(seq, "%-127s\n", bf);
2633 static const struct seq_operations fib_route_seq_ops = {
2634 .start = fib_route_seq_start,
2635 .next = fib_route_seq_next,
2636 .stop = fib_route_seq_stop,
2637 .show = fib_route_seq_show,
2640 static int fib_route_seq_open(struct inode *inode, struct file *file)
2642 return seq_open_net(inode, file, &fib_route_seq_ops,
2643 sizeof(struct fib_route_iter));
2646 static const struct file_operations fib_route_fops = {
2647 .owner = THIS_MODULE,
2648 .open = fib_route_seq_open,
2650 .llseek = seq_lseek,
2651 .release = seq_release_net,
2654 int __net_init fib_proc_init(struct net *net)
2656 if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
2659 if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
2660 &fib_triestat_fops))
2663 if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
2669 proc_net_remove(net, "fib_triestat");
2671 proc_net_remove(net, "fib_trie");
2676 void __net_exit fib_proc_exit(struct net *net)
2678 proc_net_remove(net, "fib_trie");
2679 proc_net_remove(net, "fib_triestat");
2680 proc_net_remove(net, "route");
2683 #endif /* CONFIG_PROC_FS */