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)
101 unsigned long parent;
106 unsigned long parent;
107 struct hlist_head list;
112 struct hlist_node hlist;
115 struct list_head falh;
120 unsigned long parent;
121 unsigned short pos:5; /* 2log(KEYLENGTH) bits needed */
122 unsigned short bits:5; /* 2log(KEYLENGTH) bits needed */
123 unsigned short full_children; /* KEYLENGTH bits needed */
124 unsigned short empty_children; /* KEYLENGTH bits needed */
126 struct node *child[0];
129 #ifdef CONFIG_IP_FIB_TRIE_STATS
130 struct trie_use_stats {
132 unsigned int backtrack;
133 unsigned int semantic_match_passed;
134 unsigned int semantic_match_miss;
135 unsigned int null_node_hit;
136 unsigned int resize_node_skipped;
141 unsigned int totdepth;
142 unsigned int maxdepth;
145 unsigned int nullpointers;
146 unsigned int nodesizes[MAX_STAT_DEPTH];
151 #ifdef CONFIG_IP_FIB_TRIE_STATS
152 struct trie_use_stats stats;
157 static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
158 static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull);
159 static struct node *resize(struct trie *t, struct tnode *tn);
160 static struct tnode *inflate(struct trie *t, struct tnode *tn);
161 static struct tnode *halve(struct trie *t, struct tnode *tn);
162 static void tnode_free(struct tnode *tn);
164 static struct kmem_cache *fn_alias_kmem __read_mostly;
166 static inline struct tnode *node_parent(struct node *node)
170 ret = (struct tnode *)(node->parent & ~NODE_TYPE_MASK);
171 return rcu_dereference(ret);
174 static inline void node_set_parent(struct node *node, struct tnode *ptr)
176 rcu_assign_pointer(node->parent,
177 (unsigned long)ptr | NODE_TYPE(node));
180 /* rcu_read_lock needs to be hold by caller from readside */
182 static inline struct node *tnode_get_child(struct tnode *tn, int i)
184 BUG_ON(i >= 1 << tn->bits);
186 return rcu_dereference(tn->child[i]);
189 static inline int tnode_child_length(const struct tnode *tn)
191 return 1 << tn->bits;
194 static inline t_key mask_pfx(t_key k, unsigned short l)
196 return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
199 static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
201 if (offset < KEYLENGTH)
202 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
207 static inline int tkey_equals(t_key a, t_key b)
212 static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
214 if (bits == 0 || offset >= KEYLENGTH)
216 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
217 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
220 static inline int tkey_mismatch(t_key a, int offset, t_key b)
227 while ((diff << i) >> (KEYLENGTH-1) == 0)
233 To understand this stuff, an understanding of keys and all their bits is
234 necessary. Every node in the trie has a key associated with it, but not
235 all of the bits in that key are significant.
237 Consider a node 'n' and its parent 'tp'.
239 If n is a leaf, every bit in its key is significant. Its presence is
240 necessitated by path compression, since during a tree traversal (when
241 searching for a leaf - unless we are doing an insertion) we will completely
242 ignore all skipped bits we encounter. Thus we need to verify, at the end of
243 a potentially successful search, that we have indeed been walking the
246 Note that we can never "miss" the correct key in the tree if present by
247 following the wrong path. Path compression ensures that segments of the key
248 that are the same for all keys with a given prefix are skipped, but the
249 skipped part *is* identical for each node in the subtrie below the skipped
250 bit! trie_insert() in this implementation takes care of that - note the
251 call to tkey_sub_equals() in trie_insert().
253 if n is an internal node - a 'tnode' here, the various parts of its key
254 have many different meanings.
257 _________________________________________________________________
258 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
259 -----------------------------------------------------------------
260 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
262 _________________________________________________________________
263 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
264 -----------------------------------------------------------------
265 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
272 First, let's just ignore the bits that come before the parent tp, that is
273 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
274 not use them for anything.
276 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
277 index into the parent's child array. That is, they will be used to find
278 'n' among tp's children.
280 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
283 All the bits we have seen so far are significant to the node n. The rest
284 of the bits are really not needed or indeed known in n->key.
286 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
287 n's child array, and will of course be different for each child.
290 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
295 static inline void check_tnode(const struct tnode *tn)
297 WARN_ON(tn && tn->pos+tn->bits > 32);
300 static const int halve_threshold = 25;
301 static const int inflate_threshold = 50;
302 static const int halve_threshold_root = 8;
303 static const int inflate_threshold_root = 15;
306 static void __alias_free_mem(struct rcu_head *head)
308 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
309 kmem_cache_free(fn_alias_kmem, fa);
312 static inline void alias_free_mem_rcu(struct fib_alias *fa)
314 call_rcu(&fa->rcu, __alias_free_mem);
317 static void __leaf_free_rcu(struct rcu_head *head)
319 kfree(container_of(head, struct leaf, rcu));
322 static void __leaf_info_free_rcu(struct rcu_head *head)
324 kfree(container_of(head, struct leaf_info, rcu));
327 static inline void free_leaf_info(struct leaf_info *leaf)
329 call_rcu(&leaf->rcu, __leaf_info_free_rcu);
332 static struct tnode *tnode_alloc(unsigned int size)
336 if (size <= PAGE_SIZE)
337 return kcalloc(size, 1, GFP_KERNEL);
339 pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size));
343 return page_address(pages);
346 static void __tnode_free_rcu(struct rcu_head *head)
348 struct tnode *tn = container_of(head, struct tnode, rcu);
349 unsigned int size = sizeof(struct tnode) +
350 (1 << tn->bits) * sizeof(struct node *);
352 if (size <= PAGE_SIZE)
355 free_pages((unsigned long)tn, get_order(size));
358 static inline void tnode_free(struct tnode *tn)
361 struct leaf *l = (struct leaf *) tn;
362 call_rcu_bh(&l->rcu, __leaf_free_rcu);
364 call_rcu(&tn->rcu, __tnode_free_rcu);
367 static struct leaf *leaf_new(void)
369 struct leaf *l = kmalloc(sizeof(struct leaf), GFP_KERNEL);
372 INIT_HLIST_HEAD(&l->list);
377 static struct leaf_info *leaf_info_new(int plen)
379 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
382 INIT_LIST_HEAD(&li->falh);
387 static struct tnode* tnode_new(t_key key, int pos, int bits)
389 int nchildren = 1<<bits;
390 int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *);
391 struct tnode *tn = tnode_alloc(sz);
395 tn->parent = T_TNODE;
399 tn->full_children = 0;
400 tn->empty_children = 1<<bits;
403 pr_debug("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode),
404 (unsigned int) (sizeof(struct node) * 1<<bits));
409 * Check whether a tnode 'n' is "full", i.e. it is an internal node
410 * and no bits are skipped. See discussion in dyntree paper p. 6
413 static inline int tnode_full(const struct tnode *tn, const struct node *n)
415 if (n == NULL || IS_LEAF(n))
418 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
421 static inline void put_child(struct trie *t, struct tnode *tn, int i, struct node *n)
423 tnode_put_child_reorg(tn, i, n, -1);
427 * Add a child at position i overwriting the old value.
428 * Update the value of full_children and empty_children.
431 static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull)
433 struct node *chi = tn->child[i];
436 BUG_ON(i >= 1<<tn->bits);
439 /* update emptyChildren */
440 if (n == NULL && chi != NULL)
441 tn->empty_children++;
442 else if (n != NULL && chi == NULL)
443 tn->empty_children--;
445 /* update fullChildren */
447 wasfull = tnode_full(tn, chi);
449 isfull = tnode_full(tn, n);
450 if (wasfull && !isfull)
452 else if (!wasfull && isfull)
456 node_set_parent(n, tn);
458 rcu_assign_pointer(tn->child[i], n);
461 static struct node *resize(struct trie *t, struct tnode *tn)
465 struct tnode *old_tn;
466 int inflate_threshold_use;
467 int halve_threshold_use;
473 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
474 tn, inflate_threshold, halve_threshold);
477 if (tn->empty_children == tnode_child_length(tn)) {
482 if (tn->empty_children == tnode_child_length(tn) - 1)
483 for (i = 0; i < tnode_child_length(tn); i++) {
490 /* compress one level */
491 node_set_parent(n, NULL);
496 * Double as long as the resulting node has a number of
497 * nonempty nodes that are above the threshold.
501 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
502 * the Helsinki University of Technology and Matti Tikkanen of Nokia
503 * Telecommunications, page 6:
504 * "A node is doubled if the ratio of non-empty children to all
505 * children in the *doubled* node is at least 'high'."
507 * 'high' in this instance is the variable 'inflate_threshold'. It
508 * is expressed as a percentage, so we multiply it with
509 * tnode_child_length() and instead of multiplying by 2 (since the
510 * child array will be doubled by inflate()) and multiplying
511 * the left-hand side by 100 (to handle the percentage thing) we
512 * multiply the left-hand side by 50.
514 * The left-hand side may look a bit weird: tnode_child_length(tn)
515 * - tn->empty_children is of course the number of non-null children
516 * in the current node. tn->full_children is the number of "full"
517 * children, that is non-null tnodes with a skip value of 0.
518 * All of those will be doubled in the resulting inflated tnode, so
519 * we just count them one extra time here.
521 * A clearer way to write this would be:
523 * to_be_doubled = tn->full_children;
524 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
527 * new_child_length = tnode_child_length(tn) * 2;
529 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
531 * if (new_fill_factor >= inflate_threshold)
533 * ...and so on, tho it would mess up the while () loop.
536 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
540 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
541 * inflate_threshold * new_child_length
543 * expand not_to_be_doubled and to_be_doubled, and shorten:
544 * 100 * (tnode_child_length(tn) - tn->empty_children +
545 * tn->full_children) >= inflate_threshold * new_child_length
547 * expand new_child_length:
548 * 100 * (tnode_child_length(tn) - tn->empty_children +
549 * tn->full_children) >=
550 * inflate_threshold * tnode_child_length(tn) * 2
553 * 50 * (tn->full_children + tnode_child_length(tn) -
554 * tn->empty_children) >= inflate_threshold *
555 * tnode_child_length(tn)
561 /* Keep root node larger */
564 inflate_threshold_use = inflate_threshold_root;
566 inflate_threshold_use = inflate_threshold;
570 while ((tn->full_children > 0 && max_resize-- &&
571 50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >=
572 inflate_threshold_use * tnode_child_length(tn))) {
578 #ifdef CONFIG_IP_FIB_TRIE_STATS
579 t->stats.resize_node_skipped++;
585 if (max_resize < 0) {
587 printk(KERN_WARNING "Fix inflate_threshold_root. Now=%d size=%d bits\n",
588 inflate_threshold_root, tn->bits);
590 printk(KERN_WARNING "Fix inflate_threshold. Now=%d size=%d bits\n",
591 inflate_threshold, tn->bits);
597 * Halve as long as the number of empty children in this
598 * node is above threshold.
602 /* Keep root node larger */
605 halve_threshold_use = halve_threshold_root;
607 halve_threshold_use = halve_threshold;
611 while (tn->bits > 1 && max_resize-- &&
612 100 * (tnode_child_length(tn) - tn->empty_children) <
613 halve_threshold_use * tnode_child_length(tn)) {
619 #ifdef CONFIG_IP_FIB_TRIE_STATS
620 t->stats.resize_node_skipped++;
626 if (max_resize < 0) {
628 printk(KERN_WARNING "Fix halve_threshold_root. Now=%d size=%d bits\n",
629 halve_threshold_root, tn->bits);
631 printk(KERN_WARNING "Fix halve_threshold. Now=%d size=%d bits\n",
632 halve_threshold, tn->bits);
635 /* Only one child remains */
636 if (tn->empty_children == tnode_child_length(tn) - 1)
637 for (i = 0; i < tnode_child_length(tn); i++) {
644 /* compress one level */
646 node_set_parent(n, NULL);
651 return (struct node *) tn;
654 static struct tnode *inflate(struct trie *t, struct tnode *tn)
657 struct tnode *oldtnode = tn;
658 int olen = tnode_child_length(tn);
661 pr_debug("In inflate\n");
663 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
666 return ERR_PTR(-ENOMEM);
669 * Preallocate and store tnodes before the actual work so we
670 * don't get into an inconsistent state if memory allocation
671 * fails. In case of failure we return the oldnode and inflate
672 * of tnode is ignored.
675 for (i = 0; i < olen; i++) {
676 struct tnode *inode = (struct tnode *) tnode_get_child(oldtnode, i);
680 inode->pos == oldtnode->pos + oldtnode->bits &&
682 struct tnode *left, *right;
683 t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
685 left = tnode_new(inode->key&(~m), inode->pos + 1,
690 right = tnode_new(inode->key|m, inode->pos + 1,
698 put_child(t, tn, 2*i, (struct node *) left);
699 put_child(t, tn, 2*i+1, (struct node *) right);
703 for (i = 0; i < olen; i++) {
704 struct node *node = tnode_get_child(oldtnode, i);
705 struct tnode *left, *right;
712 /* A leaf or an internal node with skipped bits */
714 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
715 tn->pos + tn->bits - 1) {
716 if (tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits,
718 put_child(t, tn, 2*i, node);
720 put_child(t, tn, 2*i+1, node);
724 /* An internal node with two children */
725 inode = (struct tnode *) node;
727 if (inode->bits == 1) {
728 put_child(t, tn, 2*i, inode->child[0]);
729 put_child(t, tn, 2*i+1, inode->child[1]);
735 /* An internal node with more than two children */
737 /* We will replace this node 'inode' with two new
738 * ones, 'left' and 'right', each with half of the
739 * original children. The two new nodes will have
740 * a position one bit further down the key and this
741 * means that the "significant" part of their keys
742 * (see the discussion near the top of this file)
743 * will differ by one bit, which will be "0" in
744 * left's key and "1" in right's key. Since we are
745 * moving the key position by one step, the bit that
746 * we are moving away from - the bit at position
747 * (inode->pos) - is the one that will differ between
748 * left and right. So... we synthesize that bit in the
750 * The mask 'm' below will be a single "one" bit at
751 * the position (inode->pos)
754 /* Use the old key, but set the new significant
758 left = (struct tnode *) tnode_get_child(tn, 2*i);
759 put_child(t, tn, 2*i, NULL);
763 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
764 put_child(t, tn, 2*i+1, NULL);
768 size = tnode_child_length(left);
769 for (j = 0; j < size; j++) {
770 put_child(t, left, j, inode->child[j]);
771 put_child(t, right, j, inode->child[j + size]);
773 put_child(t, tn, 2*i, resize(t, left));
774 put_child(t, tn, 2*i+1, resize(t, right));
778 tnode_free(oldtnode);
782 int size = tnode_child_length(tn);
785 for (j = 0; j < size; j++)
787 tnode_free((struct tnode *)tn->child[j]);
791 return ERR_PTR(-ENOMEM);
795 static struct tnode *halve(struct trie *t, struct tnode *tn)
797 struct tnode *oldtnode = tn;
798 struct node *left, *right;
800 int olen = tnode_child_length(tn);
802 pr_debug("In halve\n");
804 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
807 return ERR_PTR(-ENOMEM);
810 * Preallocate and store tnodes before the actual work so we
811 * don't get into an inconsistent state if memory allocation
812 * fails. In case of failure we return the oldnode and halve
813 * of tnode is ignored.
816 for (i = 0; i < olen; i += 2) {
817 left = tnode_get_child(oldtnode, i);
818 right = tnode_get_child(oldtnode, i+1);
820 /* Two nonempty children */
824 newn = tnode_new(left->key, tn->pos + tn->bits, 1);
829 put_child(t, tn, i/2, (struct node *)newn);
834 for (i = 0; i < olen; i += 2) {
835 struct tnode *newBinNode;
837 left = tnode_get_child(oldtnode, i);
838 right = tnode_get_child(oldtnode, i+1);
840 /* At least one of the children is empty */
842 if (right == NULL) /* Both are empty */
844 put_child(t, tn, i/2, right);
849 put_child(t, tn, i/2, left);
853 /* Two nonempty children */
854 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
855 put_child(t, tn, i/2, NULL);
856 put_child(t, newBinNode, 0, left);
857 put_child(t, newBinNode, 1, right);
858 put_child(t, tn, i/2, resize(t, newBinNode));
860 tnode_free(oldtnode);
864 int size = tnode_child_length(tn);
867 for (j = 0; j < size; j++)
869 tnode_free((struct tnode *)tn->child[j]);
873 return ERR_PTR(-ENOMEM);
877 /* readside must use rcu_read_lock currently dump routines
878 via get_fa_head and dump */
880 static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
882 struct hlist_head *head = &l->list;
883 struct hlist_node *node;
884 struct leaf_info *li;
886 hlist_for_each_entry_rcu(li, node, head, hlist)
887 if (li->plen == plen)
893 static inline struct list_head * get_fa_head(struct leaf *l, int plen)
895 struct leaf_info *li = find_leaf_info(l, plen);
903 static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
905 struct leaf_info *li = NULL, *last = NULL;
906 struct hlist_node *node;
908 if (hlist_empty(head)) {
909 hlist_add_head_rcu(&new->hlist, head);
911 hlist_for_each_entry(li, node, head, hlist) {
912 if (new->plen > li->plen)
918 hlist_add_after_rcu(&last->hlist, &new->hlist);
920 hlist_add_before_rcu(&new->hlist, &li->hlist);
924 /* rcu_read_lock needs to be hold by caller from readside */
927 fib_find_node(struct trie *t, u32 key)
934 n = rcu_dereference(t->trie);
936 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
937 tn = (struct tnode *) n;
941 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
942 pos = tn->pos + tn->bits;
943 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
947 /* Case we have found a leaf. Compare prefixes */
949 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
950 return (struct leaf *)n;
955 static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
958 t_key cindex, key = tn->key;
961 while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) {
962 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
963 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
964 tn = (struct tnode *) resize (t, (struct tnode *)tn);
965 tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull);
967 tp = node_parent((struct node *) tn);
973 /* Handle last (top) tnode */
975 tn = (struct tnode*) resize(t, (struct tnode *)tn);
977 return (struct node*) tn;
980 /* only used from updater-side */
982 static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
985 struct tnode *tp = NULL, *tn = NULL;
989 struct list_head *fa_head = NULL;
990 struct leaf_info *li;
996 /* If we point to NULL, stop. Either the tree is empty and we should
997 * just put a new leaf in if, or we have reached an empty child slot,
998 * and we should just put our new leaf in that.
999 * If we point to a T_TNODE, check if it matches our key. Note that
1000 * a T_TNODE might be skipping any number of bits - its 'pos' need
1001 * not be the parent's 'pos'+'bits'!
1003 * If it does match the current key, get pos/bits from it, extract
1004 * the index from our key, push the T_TNODE and walk the tree.
1006 * If it doesn't, we have to replace it with a new T_TNODE.
1008 * If we point to a T_LEAF, it might or might not have the same key
1009 * as we do. If it does, just change the value, update the T_LEAF's
1010 * value, and return it.
1011 * If it doesn't, we need to replace it with a T_TNODE.
1014 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1015 tn = (struct tnode *) n;
1019 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1021 pos = tn->pos + tn->bits;
1022 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
1024 BUG_ON(n && node_parent(n) != tn);
1030 * n ----> NULL, LEAF or TNODE
1032 * tp is n's (parent) ----> NULL or TNODE
1035 BUG_ON(tp && IS_LEAF(tp));
1037 /* Case 1: n is a leaf. Compare prefixes */
1039 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1040 struct leaf *l = (struct leaf *) n;
1042 li = leaf_info_new(plen);
1047 fa_head = &li->falh;
1048 insert_leaf_info(&l->list, li);
1058 li = leaf_info_new(plen);
1061 tnode_free((struct tnode *) l);
1065 fa_head = &li->falh;
1066 insert_leaf_info(&l->list, li);
1068 if (t->trie && n == NULL) {
1069 /* Case 2: n is NULL, and will just insert a new leaf */
1071 node_set_parent((struct node *)l, tp);
1073 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1074 put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
1076 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1078 * Add a new tnode here
1079 * first tnode need some special handling
1083 pos = tp->pos+tp->bits;
1088 newpos = tkey_mismatch(key, pos, n->key);
1089 tn = tnode_new(n->key, newpos, 1);
1092 tn = tnode_new(key, newpos, 1); /* First tnode */
1097 tnode_free((struct tnode *) l);
1101 node_set_parent((struct node *)tn, tp);
1103 missbit = tkey_extract_bits(key, newpos, 1);
1104 put_child(t, tn, missbit, (struct node *)l);
1105 put_child(t, tn, 1-missbit, n);
1108 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1109 put_child(t, (struct tnode *)tp, cindex, (struct node *)tn);
1111 rcu_assign_pointer(t->trie, (struct node *)tn); /* First tnode */
1116 if (tp && tp->pos + tp->bits > 32)
1117 printk(KERN_WARNING "fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1118 tp, tp->pos, tp->bits, key, plen);
1120 /* Rebalance the trie */
1122 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
1128 * Caller must hold RTNL.
1130 static int fn_trie_insert(struct fib_table *tb, struct fib_config *cfg)
1132 struct trie *t = (struct trie *) tb->tb_data;
1133 struct fib_alias *fa, *new_fa;
1134 struct list_head *fa_head = NULL;
1135 struct fib_info *fi;
1136 int plen = cfg->fc_dst_len;
1137 u8 tos = cfg->fc_tos;
1145 key = ntohl(cfg->fc_dst);
1147 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1149 mask = ntohl(inet_make_mask(plen));
1156 fi = fib_create_info(cfg);
1162 l = fib_find_node(t, key);
1166 fa_head = get_fa_head(l, plen);
1167 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1170 /* Now fa, if non-NULL, points to the first fib alias
1171 * with the same keys [prefix,tos,priority], if such key already
1172 * exists or to the node before which we will insert new one.
1174 * If fa is NULL, we will need to allocate a new one and
1175 * insert to the head of f.
1177 * If f is NULL, no fib node matched the destination key
1178 * and we need to allocate a new one of those as well.
1181 if (fa && fa->fa_info->fib_priority == fi->fib_priority) {
1182 struct fib_alias *fa_orig;
1185 if (cfg->fc_nlflags & NLM_F_EXCL)
1188 if (cfg->fc_nlflags & NLM_F_REPLACE) {
1189 struct fib_info *fi_drop;
1192 if (fi->fib_treeref > 1)
1196 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1200 fi_drop = fa->fa_info;
1201 new_fa->fa_tos = fa->fa_tos;
1202 new_fa->fa_info = fi;
1203 new_fa->fa_type = cfg->fc_type;
1204 new_fa->fa_scope = cfg->fc_scope;
1205 state = fa->fa_state;
1206 new_fa->fa_state &= ~FA_S_ACCESSED;
1208 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1209 alias_free_mem_rcu(fa);
1211 fib_release_info(fi_drop);
1212 if (state & FA_S_ACCESSED)
1214 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1215 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1219 /* Error if we find a perfect match which
1220 * uses the same scope, type, and nexthop
1224 list_for_each_entry(fa, fa_orig->fa_list.prev, fa_list) {
1225 if (fa->fa_tos != tos)
1227 if (fa->fa_info->fib_priority != fi->fib_priority)
1229 if (fa->fa_type == cfg->fc_type &&
1230 fa->fa_scope == cfg->fc_scope &&
1231 fa->fa_info == fi) {
1235 if (!(cfg->fc_nlflags & NLM_F_APPEND))
1239 if (!(cfg->fc_nlflags & NLM_F_CREATE))
1243 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1247 new_fa->fa_info = fi;
1248 new_fa->fa_tos = tos;
1249 new_fa->fa_type = cfg->fc_type;
1250 new_fa->fa_scope = cfg->fc_scope;
1251 new_fa->fa_state = 0;
1253 * Insert new entry to the list.
1257 fa_head = fib_insert_node(t, key, plen);
1258 if (unlikely(!fa_head)) {
1260 goto out_free_new_fa;
1264 list_add_tail_rcu(&new_fa->fa_list,
1265 (fa ? &fa->fa_list : fa_head));
1268 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1269 &cfg->fc_nlinfo, 0);
1274 kmem_cache_free(fn_alias_kmem, new_fa);
1276 fib_release_info(fi);
1282 /* should be called with rcu_read_lock */
1283 static inline int check_leaf(struct trie *t, struct leaf *l,
1284 t_key key, int *plen, const struct flowi *flp,
1285 struct fib_result *res)
1289 struct leaf_info *li;
1290 struct hlist_head *hhead = &l->list;
1291 struct hlist_node *node;
1293 hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1295 mask = inet_make_mask(i);
1296 if (l->key != (key & ntohl(mask)))
1299 if ((err = fib_semantic_match(&li->falh, flp, res, htonl(l->key), mask, i)) <= 0) {
1301 #ifdef CONFIG_IP_FIB_TRIE_STATS
1302 t->stats.semantic_match_passed++;
1306 #ifdef CONFIG_IP_FIB_TRIE_STATS
1307 t->stats.semantic_match_miss++;
1314 fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
1316 struct trie *t = (struct trie *) tb->tb_data;
1321 t_key key = ntohl(flp->fl4_dst);
1324 int current_prefix_length = KEYLENGTH;
1326 t_key node_prefix, key_prefix, pref_mismatch;
1331 n = rcu_dereference(t->trie);
1335 #ifdef CONFIG_IP_FIB_TRIE_STATS
1341 if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
1345 pn = (struct tnode *) n;
1353 cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1356 n = tnode_get_child(pn, cindex);
1359 #ifdef CONFIG_IP_FIB_TRIE_STATS
1360 t->stats.null_node_hit++;
1366 if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
1374 cn = (struct tnode *)n;
1377 * It's a tnode, and we can do some extra checks here if we
1378 * like, to avoid descending into a dead-end branch.
1379 * This tnode is in the parent's child array at index
1380 * key[p_pos..p_pos+p_bits] but potentially with some bits
1381 * chopped off, so in reality the index may be just a
1382 * subprefix, padded with zero at the end.
1383 * We can also take a look at any skipped bits in this
1384 * tnode - everything up to p_pos is supposed to be ok,
1385 * and the non-chopped bits of the index (se previous
1386 * paragraph) are also guaranteed ok, but the rest is
1387 * considered unknown.
1389 * The skipped bits are key[pos+bits..cn->pos].
1392 /* If current_prefix_length < pos+bits, we are already doing
1393 * actual prefix matching, which means everything from
1394 * pos+(bits-chopped_off) onward must be zero along some
1395 * branch of this subtree - otherwise there is *no* valid
1396 * prefix present. Here we can only check the skipped
1397 * bits. Remember, since we have already indexed into the
1398 * parent's child array, we know that the bits we chopped of
1402 /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */
1404 if (current_prefix_length < pos+bits) {
1405 if (tkey_extract_bits(cn->key, current_prefix_length,
1406 cn->pos - current_prefix_length) != 0 ||
1412 * If chopped_off=0, the index is fully validated and we
1413 * only need to look at the skipped bits for this, the new,
1414 * tnode. What we actually want to do is to find out if
1415 * these skipped bits match our key perfectly, or if we will
1416 * have to count on finding a matching prefix further down,
1417 * because if we do, we would like to have some way of
1418 * verifying the existence of such a prefix at this point.
1421 /* The only thing we can do at this point is to verify that
1422 * any such matching prefix can indeed be a prefix to our
1423 * key, and if the bits in the node we are inspecting that
1424 * do not match our key are not ZERO, this cannot be true.
1425 * Thus, find out where there is a mismatch (before cn->pos)
1426 * and verify that all the mismatching bits are zero in the
1430 /* Note: We aren't very concerned about the piece of the key
1431 * that precede pn->pos+pn->bits, since these have already been
1432 * checked. The bits after cn->pos aren't checked since these are
1433 * by definition "unknown" at this point. Thus, what we want to
1434 * see is if we are about to enter the "prefix matching" state,
1435 * and in that case verify that the skipped bits that will prevail
1436 * throughout this subtree are zero, as they have to be if we are
1437 * to find a matching prefix.
1440 node_prefix = mask_pfx(cn->key, cn->pos);
1441 key_prefix = mask_pfx(key, cn->pos);
1442 pref_mismatch = key_prefix^node_prefix;
1445 /* In short: If skipped bits in this node do not match the search
1446 * key, enter the "prefix matching" state.directly.
1448 if (pref_mismatch) {
1449 while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
1451 pref_mismatch = pref_mismatch <<1;
1453 key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);
1455 if (key_prefix != 0)
1458 if (current_prefix_length >= cn->pos)
1459 current_prefix_length = mp;
1462 pn = (struct tnode *)n; /* Descend */
1469 /* As zero don't change the child key (cindex) */
1470 while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1))))
1473 /* Decrease current_... with bits chopped off */
1474 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1475 current_prefix_length = pn->pos + pn->bits - chopped_off;
1478 * Either we do the actual chop off according or if we have
1479 * chopped off all bits in this tnode walk up to our parent.
1482 if (chopped_off <= pn->bits) {
1483 cindex &= ~(1 << (chopped_off-1));
1485 struct tnode *parent = node_parent((struct node *) pn);
1489 /* Get Child's index */
1490 cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1494 #ifdef CONFIG_IP_FIB_TRIE_STATS
1495 t->stats.backtrack++;
1507 /* only called from updater side */
1508 static int trie_leaf_remove(struct trie *t, t_key key)
1511 struct tnode *tp = NULL;
1512 struct node *n = t->trie;
1515 pr_debug("entering trie_leaf_remove(%p)\n", n);
1517 /* Note that in the case skipped bits, those bits are *not* checked!
1518 * When we finish this, we will have NULL or a T_LEAF, and the
1519 * T_LEAF may or may not match our key.
1522 while (n != NULL && IS_TNODE(n)) {
1523 struct tnode *tn = (struct tnode *) n;
1525 n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits));
1527 BUG_ON(n && node_parent(n) != tn);
1529 l = (struct leaf *) n;
1531 if (!n || !tkey_equals(l->key, key))
1536 * Remove the leaf and rebalance the tree
1541 tp = node_parent(n);
1542 tnode_free((struct tnode *) n);
1545 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1546 put_child(t, (struct tnode *)tp, cindex, NULL);
1547 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
1549 rcu_assign_pointer(t->trie, NULL);
1555 * Caller must hold RTNL.
1557 static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
1559 struct trie *t = (struct trie *) tb->tb_data;
1561 int plen = cfg->fc_dst_len;
1562 u8 tos = cfg->fc_tos;
1563 struct fib_alias *fa, *fa_to_delete;
1564 struct list_head *fa_head;
1566 struct leaf_info *li;
1571 key = ntohl(cfg->fc_dst);
1572 mask = ntohl(inet_make_mask(plen));
1578 l = fib_find_node(t, key);
1583 fa_head = get_fa_head(l, plen);
1584 fa = fib_find_alias(fa_head, tos, 0);
1589 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1591 fa_to_delete = NULL;
1592 fa_head = fa->fa_list.prev;
1594 list_for_each_entry(fa, fa_head, fa_list) {
1595 struct fib_info *fi = fa->fa_info;
1597 if (fa->fa_tos != tos)
1600 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1601 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1602 fa->fa_scope == cfg->fc_scope) &&
1603 (!cfg->fc_protocol ||
1604 fi->fib_protocol == cfg->fc_protocol) &&
1605 fib_nh_match(cfg, fi) == 0) {
1615 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1616 &cfg->fc_nlinfo, 0);
1618 l = fib_find_node(t, key);
1619 li = find_leaf_info(l, plen);
1621 list_del_rcu(&fa->fa_list);
1623 if (list_empty(fa_head)) {
1624 hlist_del_rcu(&li->hlist);
1628 if (hlist_empty(&l->list))
1629 trie_leaf_remove(t, key);
1631 if (fa->fa_state & FA_S_ACCESSED)
1634 fib_release_info(fa->fa_info);
1635 alias_free_mem_rcu(fa);
1639 static int trie_flush_list(struct trie *t, struct list_head *head)
1641 struct fib_alias *fa, *fa_node;
1644 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1645 struct fib_info *fi = fa->fa_info;
1647 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1648 list_del_rcu(&fa->fa_list);
1649 fib_release_info(fa->fa_info);
1650 alias_free_mem_rcu(fa);
1657 static int trie_flush_leaf(struct trie *t, struct leaf *l)
1660 struct hlist_head *lih = &l->list;
1661 struct hlist_node *node, *tmp;
1662 struct leaf_info *li = NULL;
1664 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
1665 found += trie_flush_list(t, &li->falh);
1667 if (list_empty(&li->falh)) {
1668 hlist_del_rcu(&li->hlist);
1675 /* rcu_read_lock needs to be hold by caller from readside */
1677 static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
1679 struct node *c = (struct node *) thisleaf;
1682 struct node *trie = rcu_dereference(t->trie);
1688 if (IS_LEAF(trie)) /* trie w. just a leaf */
1689 return (struct leaf *) trie;
1691 p = (struct tnode*) trie; /* Start */
1698 /* Find the next child of the parent */
1700 pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits);
1704 last = 1 << p->bits;
1705 for (idx = pos; idx < last ; idx++) {
1706 c = rcu_dereference(p->child[idx]);
1711 /* Decend if tnode */
1712 while (IS_TNODE(c)) {
1713 p = (struct tnode *) c;
1716 /* Rightmost non-NULL branch */
1717 if (p && IS_TNODE(p))
1718 while (!(c = rcu_dereference(p->child[idx]))
1719 && idx < (1<<p->bits)) idx++;
1721 /* Done with this tnode? */
1722 if (idx >= (1 << p->bits) || !c)
1725 return (struct leaf *) c;
1728 /* No more children go up one step */
1729 c = (struct node *) p;
1732 return NULL; /* Ready. Root of trie */
1736 * Caller must hold RTNL.
1738 static int fn_trie_flush(struct fib_table *tb)
1740 struct trie *t = (struct trie *) tb->tb_data;
1741 struct leaf *ll = NULL, *l = NULL;
1744 for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1745 found += trie_flush_leaf(t, l);
1747 if (ll && hlist_empty(&ll->list))
1748 trie_leaf_remove(t, ll->key);
1752 if (ll && hlist_empty(&ll->list))
1753 trie_leaf_remove(t, ll->key);
1755 pr_debug("trie_flush found=%d\n", found);
1760 fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
1762 struct trie *t = (struct trie *) tb->tb_data;
1763 int order, last_idx;
1764 struct fib_info *fi = NULL;
1765 struct fib_info *last_resort;
1766 struct fib_alias *fa = NULL;
1767 struct list_head *fa_head;
1776 l = fib_find_node(t, 0);
1780 fa_head = get_fa_head(l, 0);
1784 if (list_empty(fa_head))
1787 list_for_each_entry_rcu(fa, fa_head, fa_list) {
1788 struct fib_info *next_fi = fa->fa_info;
1790 if (fa->fa_scope != res->scope ||
1791 fa->fa_type != RTN_UNICAST)
1794 if (next_fi->fib_priority > res->fi->fib_priority)
1796 if (!next_fi->fib_nh[0].nh_gw ||
1797 next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
1799 fa->fa_state |= FA_S_ACCESSED;
1802 if (next_fi != res->fi)
1804 } else if (!fib_detect_death(fi, order, &last_resort,
1805 &last_idx, tb->tb_default)) {
1806 fib_result_assign(res, fi);
1807 tb->tb_default = order;
1813 if (order <= 0 || fi == NULL) {
1814 tb->tb_default = -1;
1818 if (!fib_detect_death(fi, order, &last_resort, &last_idx,
1820 fib_result_assign(res, fi);
1821 tb->tb_default = order;
1825 fib_result_assign(res, last_resort);
1826 tb->tb_default = last_idx;
1831 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fib_table *tb,
1832 struct sk_buff *skb, struct netlink_callback *cb)
1835 struct fib_alias *fa;
1837 __be32 xkey = htonl(key);
1842 /* rcu_read_lock is hold by caller */
1844 list_for_each_entry_rcu(fa, fah, fa_list) {
1849 BUG_ON(!fa->fa_info);
1851 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1860 fa->fa_info, 0) < 0) {
1870 static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb,
1871 struct netlink_callback *cb)
1874 struct list_head *fa_head;
1875 struct leaf *l = NULL;
1879 for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1883 memset(&cb->args[4], 0,
1884 sizeof(cb->args) - 4*sizeof(cb->args[0]));
1886 fa_head = get_fa_head(l, plen);
1891 if (list_empty(fa_head))
1894 if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
1903 static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlink_callback *cb)
1906 struct trie *t = (struct trie *) tb->tb_data;
1911 for (m = 0; m <= 32; m++) {
1915 memset(&cb->args[3], 0,
1916 sizeof(cb->args) - 3*sizeof(cb->args[0]));
1918 if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) {
1931 /* Fix more generic FIB names for init later */
1933 struct fib_table *fib_hash_init(u32 id)
1935 struct fib_table *tb;
1938 if (fn_alias_kmem == NULL)
1939 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1940 sizeof(struct fib_alias),
1941 0, SLAB_HWCACHE_ALIGN,
1944 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1950 tb->tb_default = -1;
1951 tb->tb_lookup = fn_trie_lookup;
1952 tb->tb_insert = fn_trie_insert;
1953 tb->tb_delete = fn_trie_delete;
1954 tb->tb_flush = fn_trie_flush;
1955 tb->tb_select_default = fn_trie_select_default;
1956 tb->tb_dump = fn_trie_dump;
1958 t = (struct trie *) tb->tb_data;
1959 memset(t, 0, sizeof(*t));
1961 if (id == RT_TABLE_LOCAL)
1962 printk(KERN_INFO "IPv4 FIB: Using LC-trie version %s\n", VERSION);
1967 #ifdef CONFIG_PROC_FS
1968 /* Depth first Trie walk iterator */
1969 struct fib_trie_iter {
1970 struct seq_net_private p;
1971 struct trie *trie_local, *trie_main;
1972 struct tnode *tnode;
1978 static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
1980 struct tnode *tn = iter->tnode;
1981 unsigned cindex = iter->index;
1984 /* A single entry routing table */
1988 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
1989 iter->tnode, iter->index, iter->depth);
1991 while (cindex < (1<<tn->bits)) {
1992 struct node *n = tnode_get_child(tn, cindex);
1997 iter->index = cindex + 1;
1999 /* push down one level */
2000 iter->tnode = (struct tnode *) n;
2010 /* Current node exhausted, pop back up */
2011 p = node_parent((struct node *)tn);
2013 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2023 static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
2031 n = rcu_dereference(t->trie);
2038 iter->tnode = (struct tnode *) n;
2053 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2056 struct fib_trie_iter iter;
2058 memset(s, 0, sizeof(*s));
2061 for (n = fib_trie_get_first(&iter, t); n;
2062 n = fib_trie_get_next(&iter)) {
2065 s->totdepth += iter.depth;
2066 if (iter.depth > s->maxdepth)
2067 s->maxdepth = iter.depth;
2069 const struct tnode *tn = (const struct tnode *) n;
2073 if (tn->bits < MAX_STAT_DEPTH)
2074 s->nodesizes[tn->bits]++;
2076 for (i = 0; i < (1<<tn->bits); i++)
2085 * This outputs /proc/net/fib_triestats
2087 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2089 unsigned i, max, pointers, bytes, avdepth;
2092 avdepth = stat->totdepth*100 / stat->leaves;
2096 seq_printf(seq, "\tAver depth: %u.%02d\n", avdepth / 100, avdepth % 100 );
2097 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
2099 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
2101 bytes = sizeof(struct leaf) * stat->leaves;
2102 seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2103 bytes += sizeof(struct tnode) * stat->tnodes;
2105 max = MAX_STAT_DEPTH;
2106 while (max > 0 && stat->nodesizes[max-1] == 0)
2110 for (i = 1; i <= max; i++)
2111 if (stat->nodesizes[i] != 0) {
2112 seq_printf(seq, " %u: %u", i, stat->nodesizes[i]);
2113 pointers += (1<<i) * stat->nodesizes[i];
2115 seq_putc(seq, '\n');
2116 seq_printf(seq, "\tPointers: %u\n", pointers);
2118 bytes += sizeof(struct node *) * pointers;
2119 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2120 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
2123 #ifdef CONFIG_IP_FIB_TRIE_STATS
2124 static void trie_show_usage(struct seq_file *seq,
2125 const struct trie_use_stats *stats)
2127 seq_printf(seq, "\nCounters:\n---------\n");
2128 seq_printf(seq,"gets = %u\n", stats->gets);
2129 seq_printf(seq,"backtracks = %u\n", stats->backtrack);
2130 seq_printf(seq,"semantic match passed = %u\n", stats->semantic_match_passed);
2131 seq_printf(seq,"semantic match miss = %u\n", stats->semantic_match_miss);
2132 seq_printf(seq,"null node hit= %u\n", stats->null_node_hit);
2133 seq_printf(seq,"skipped node resize = %u\n\n", stats->resize_node_skipped);
2135 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2138 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2140 struct net *net = (struct net *)seq->private;
2141 struct trie *trie_local, *trie_main;
2142 struct trie_stat *stat;
2143 struct fib_table *tb;
2146 tb = fib_get_table(net, RT_TABLE_LOCAL);
2148 trie_local = (struct trie *) tb->tb_data;
2151 tb = fib_get_table(net, RT_TABLE_MAIN);
2153 trie_main = (struct trie *) tb->tb_data;
2156 stat = kmalloc(sizeof(*stat), GFP_KERNEL);
2160 seq_printf(seq, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
2161 sizeof(struct leaf), sizeof(struct tnode));
2164 seq_printf(seq, "Local:\n");
2165 trie_collect_stats(trie_local, stat);
2166 trie_show_stats(seq, stat);
2167 #ifdef CONFIG_IP_FIB_TRIE_STATS
2168 trie_show_usage(seq, &trie_local->stats);
2173 seq_printf(seq, "Main:\n");
2174 trie_collect_stats(trie_main, stat);
2175 trie_show_stats(seq, stat);
2176 #ifdef CONFIG_IP_FIB_TRIE_STATS
2177 trie_show_usage(seq, &trie_main->stats);
2185 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2190 net = get_proc_net(inode);
2193 err = single_open(file, fib_triestat_seq_show, net);
2201 static int fib_triestat_seq_release(struct inode *ino, struct file *f)
2203 struct seq_file *seq = f->private_data;
2204 put_net(seq->private);
2205 return single_release(ino, f);
2208 static const struct file_operations fib_triestat_fops = {
2209 .owner = THIS_MODULE,
2210 .open = fib_triestat_seq_open,
2212 .llseek = seq_lseek,
2213 .release = fib_triestat_seq_release,
2216 static struct node *fib_trie_get_idx(struct fib_trie_iter *iter,
2222 for (n = fib_trie_get_first(iter, iter->trie_local);
2223 n; ++idx, n = fib_trie_get_next(iter)) {
2228 for (n = fib_trie_get_first(iter, iter->trie_main);
2229 n; ++idx, n = fib_trie_get_next(iter)) {
2236 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2238 struct fib_trie_iter *iter = seq->private;
2239 struct fib_table *tb;
2241 if (!iter->trie_local) {
2242 tb = fib_get_table(iter->p.net, RT_TABLE_LOCAL);
2244 iter->trie_local = (struct trie *) tb->tb_data;
2246 if (!iter->trie_main) {
2247 tb = fib_get_table(iter->p.net, RT_TABLE_MAIN);
2249 iter->trie_main = (struct trie *) tb->tb_data;
2253 return SEQ_START_TOKEN;
2254 return fib_trie_get_idx(iter, *pos - 1);
2257 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2259 struct fib_trie_iter *iter = seq->private;
2263 if (v == SEQ_START_TOKEN)
2264 return fib_trie_get_idx(iter, 0);
2266 v = fib_trie_get_next(iter);
2271 /* continue scan in next trie */
2272 if (iter->trie == iter->trie_local)
2273 return fib_trie_get_first(iter, iter->trie_main);
2278 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2283 static void seq_indent(struct seq_file *seq, int n)
2285 while (n-- > 0) seq_puts(seq, " ");
2288 static inline const char *rtn_scope(enum rt_scope_t s)
2290 static char buf[32];
2293 case RT_SCOPE_UNIVERSE: return "universe";
2294 case RT_SCOPE_SITE: return "site";
2295 case RT_SCOPE_LINK: return "link";
2296 case RT_SCOPE_HOST: return "host";
2297 case RT_SCOPE_NOWHERE: return "nowhere";
2299 snprintf(buf, sizeof(buf), "scope=%d", s);
2304 static const char *rtn_type_names[__RTN_MAX] = {
2305 [RTN_UNSPEC] = "UNSPEC",
2306 [RTN_UNICAST] = "UNICAST",
2307 [RTN_LOCAL] = "LOCAL",
2308 [RTN_BROADCAST] = "BROADCAST",
2309 [RTN_ANYCAST] = "ANYCAST",
2310 [RTN_MULTICAST] = "MULTICAST",
2311 [RTN_BLACKHOLE] = "BLACKHOLE",
2312 [RTN_UNREACHABLE] = "UNREACHABLE",
2313 [RTN_PROHIBIT] = "PROHIBIT",
2314 [RTN_THROW] = "THROW",
2316 [RTN_XRESOLVE] = "XRESOLVE",
2319 static inline const char *rtn_type(unsigned t)
2321 static char buf[32];
2323 if (t < __RTN_MAX && rtn_type_names[t])
2324 return rtn_type_names[t];
2325 snprintf(buf, sizeof(buf), "type %u", t);
2329 /* Pretty print the trie */
2330 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2332 const struct fib_trie_iter *iter = seq->private;
2335 if (v == SEQ_START_TOKEN)
2338 if (!node_parent(n)) {
2339 if (iter->trie == iter->trie_local)
2340 seq_puts(seq, "<local>:\n");
2342 seq_puts(seq, "<main>:\n");
2346 struct tnode *tn = (struct tnode *) n;
2347 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2349 seq_indent(seq, iter->depth-1);
2350 seq_printf(seq, " +-- %d.%d.%d.%d/%d %d %d %d\n",
2351 NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
2352 tn->empty_children);
2355 struct leaf *l = (struct leaf *) n;
2357 __be32 val = htonl(l->key);
2359 seq_indent(seq, iter->depth);
2360 seq_printf(seq, " |-- %d.%d.%d.%d\n", NIPQUAD(val));
2361 for (i = 32; i >= 0; i--) {
2362 struct leaf_info *li = find_leaf_info(l, i);
2364 struct fib_alias *fa;
2365 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2366 seq_indent(seq, iter->depth+1);
2367 seq_printf(seq, " /%d %s %s", i,
2368 rtn_scope(fa->fa_scope),
2369 rtn_type(fa->fa_type));
2371 seq_printf(seq, "tos =%d\n",
2373 seq_putc(seq, '\n');
2382 static const struct seq_operations fib_trie_seq_ops = {
2383 .start = fib_trie_seq_start,
2384 .next = fib_trie_seq_next,
2385 .stop = fib_trie_seq_stop,
2386 .show = fib_trie_seq_show,
2389 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2391 return seq_open_net(inode, file, &fib_trie_seq_ops,
2392 sizeof(struct fib_trie_iter));
2395 static const struct file_operations fib_trie_fops = {
2396 .owner = THIS_MODULE,
2397 .open = fib_trie_seq_open,
2399 .llseek = seq_lseek,
2400 .release = seq_release_net,
2403 static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2405 static unsigned type2flags[RTN_MAX + 1] = {
2406 [7] = RTF_REJECT, [8] = RTF_REJECT,
2408 unsigned flags = type2flags[type];
2410 if (fi && fi->fib_nh->nh_gw)
2411 flags |= RTF_GATEWAY;
2412 if (mask == htonl(0xFFFFFFFF))
2419 * This outputs /proc/net/route.
2420 * The format of the file is not supposed to be changed
2421 * and needs to be same as fib_hash output to avoid breaking
2424 static int fib_route_seq_show(struct seq_file *seq, void *v)
2426 const struct fib_trie_iter *iter = seq->private;
2431 if (v == SEQ_START_TOKEN) {
2432 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2433 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2438 if (iter->trie == iter->trie_local)
2443 for (i=32; i>=0; i--) {
2444 struct leaf_info *li = find_leaf_info(l, i);
2445 struct fib_alias *fa;
2446 __be32 mask, prefix;
2451 mask = inet_make_mask(li->plen);
2452 prefix = htonl(l->key);
2454 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2455 const struct fib_info *fi = fa->fa_info;
2456 unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2458 if (fa->fa_type == RTN_BROADCAST
2459 || fa->fa_type == RTN_MULTICAST)
2463 snprintf(bf, sizeof(bf),
2464 "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2465 fi->fib_dev ? fi->fib_dev->name : "*",
2467 fi->fib_nh->nh_gw, flags, 0, 0,
2470 (fi->fib_advmss ? fi->fib_advmss + 40 : 0),
2474 snprintf(bf, sizeof(bf),
2475 "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2476 prefix, 0, flags, 0, 0, 0,
2479 seq_printf(seq, "%-127s\n", bf);
2486 static const struct seq_operations fib_route_seq_ops = {
2487 .start = fib_trie_seq_start,
2488 .next = fib_trie_seq_next,
2489 .stop = fib_trie_seq_stop,
2490 .show = fib_route_seq_show,
2493 static int fib_route_seq_open(struct inode *inode, struct file *file)
2495 return seq_open_net(inode, file, &fib_route_seq_ops,
2496 sizeof(struct fib_trie_iter));
2499 static const struct file_operations fib_route_fops = {
2500 .owner = THIS_MODULE,
2501 .open = fib_route_seq_open,
2503 .llseek = seq_lseek,
2504 .release = seq_release_net,
2507 int __net_init fib_proc_init(struct net *net)
2509 if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
2512 if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
2513 &fib_triestat_fops))
2516 if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
2522 proc_net_remove(net, "fib_triestat");
2524 proc_net_remove(net, "fib_trie");
2529 void __net_exit fib_proc_exit(struct net *net)
2531 proc_net_remove(net, "fib_trie");
2532 proc_net_remove(net, "fib_triestat");
2533 proc_net_remove(net, "route");
2536 #endif /* CONFIG_PROC_FS */