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 */
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];
152 #ifdef CONFIG_IP_FIB_TRIE_STATS
153 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;
165 static struct kmem_cache *trie_leaf_kmem __read_mostly;
167 static inline struct tnode *node_parent(struct node *node)
169 return (struct tnode *)(node->parent & ~NODE_TYPE_MASK);
172 static inline struct tnode *node_parent_rcu(struct node *node)
174 struct tnode *ret = node_parent(node);
176 return rcu_dereference(ret);
179 static inline void node_set_parent(struct node *node, struct tnode *ptr)
181 rcu_assign_pointer(node->parent,
182 (unsigned long)ptr | NODE_TYPE(node));
185 static inline struct node *tnode_get_child(struct tnode *tn, unsigned int i)
187 BUG_ON(i >= 1U << tn->bits);
192 static inline struct node *tnode_get_child_rcu(struct tnode *tn, unsigned int i)
194 struct node *ret = tnode_get_child(tn, i);
196 return rcu_dereference(ret);
199 static inline int tnode_child_length(const struct tnode *tn)
201 return 1 << tn->bits;
204 static inline t_key mask_pfx(t_key k, unsigned short l)
206 return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
209 static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
211 if (offset < KEYLENGTH)
212 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
217 static inline int tkey_equals(t_key a, t_key b)
222 static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
224 if (bits == 0 || offset >= KEYLENGTH)
226 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
227 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
230 static inline int tkey_mismatch(t_key a, int offset, t_key b)
237 while ((diff << i) >> (KEYLENGTH-1) == 0)
243 To understand this stuff, an understanding of keys and all their bits is
244 necessary. Every node in the trie has a key associated with it, but not
245 all of the bits in that key are significant.
247 Consider a node 'n' and its parent 'tp'.
249 If n is a leaf, every bit in its key is significant. Its presence is
250 necessitated by path compression, since during a tree traversal (when
251 searching for a leaf - unless we are doing an insertion) we will completely
252 ignore all skipped bits we encounter. Thus we need to verify, at the end of
253 a potentially successful search, that we have indeed been walking the
256 Note that we can never "miss" the correct key in the tree if present by
257 following the wrong path. Path compression ensures that segments of the key
258 that are the same for all keys with a given prefix are skipped, but the
259 skipped part *is* identical for each node in the subtrie below the skipped
260 bit! trie_insert() in this implementation takes care of that - note the
261 call to tkey_sub_equals() in trie_insert().
263 if n is an internal node - a 'tnode' here, the various parts of its key
264 have many different meanings.
267 _________________________________________________________________
268 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
269 -----------------------------------------------------------------
270 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
272 _________________________________________________________________
273 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
274 -----------------------------------------------------------------
275 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
282 First, let's just ignore the bits that come before the parent tp, that is
283 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
284 not use them for anything.
286 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
287 index into the parent's child array. That is, they will be used to find
288 'n' among tp's children.
290 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
293 All the bits we have seen so far are significant to the node n. The rest
294 of the bits are really not needed or indeed known in n->key.
296 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
297 n's child array, and will of course be different for each child.
300 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
305 static inline void check_tnode(const struct tnode *tn)
307 WARN_ON(tn && tn->pos+tn->bits > 32);
310 static const int halve_threshold = 25;
311 static const int inflate_threshold = 50;
312 static const int halve_threshold_root = 8;
313 static const int inflate_threshold_root = 15;
316 static void __alias_free_mem(struct rcu_head *head)
318 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
319 kmem_cache_free(fn_alias_kmem, fa);
322 static inline void alias_free_mem_rcu(struct fib_alias *fa)
324 call_rcu(&fa->rcu, __alias_free_mem);
327 static void __leaf_free_rcu(struct rcu_head *head)
329 struct leaf *l = container_of(head, struct leaf, rcu);
330 kmem_cache_free(trie_leaf_kmem, l);
333 static void __leaf_info_free_rcu(struct rcu_head *head)
335 kfree(container_of(head, struct leaf_info, rcu));
338 static inline void free_leaf_info(struct leaf_info *leaf)
340 call_rcu(&leaf->rcu, __leaf_info_free_rcu);
343 static struct tnode *tnode_alloc(size_t size)
347 if (size <= PAGE_SIZE)
348 return kzalloc(size, GFP_KERNEL);
350 pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size));
354 return page_address(pages);
357 static void __tnode_free_rcu(struct rcu_head *head)
359 struct tnode *tn = container_of(head, struct tnode, rcu);
360 size_t size = sizeof(struct tnode) +
361 (sizeof(struct node *) << tn->bits);
363 if (size <= PAGE_SIZE)
366 free_pages((unsigned long)tn, get_order(size));
369 static inline void tnode_free(struct tnode *tn)
372 struct leaf *l = (struct leaf *) tn;
373 call_rcu_bh(&l->rcu, __leaf_free_rcu);
375 call_rcu(&tn->rcu, __tnode_free_rcu);
378 static struct leaf *leaf_new(void)
380 struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
383 INIT_HLIST_HEAD(&l->list);
388 static struct leaf_info *leaf_info_new(int plen)
390 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
393 INIT_LIST_HEAD(&li->falh);
398 static struct tnode* tnode_new(t_key key, int pos, int bits)
400 size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits);
401 struct tnode *tn = tnode_alloc(sz);
404 tn->parent = T_TNODE;
408 tn->full_children = 0;
409 tn->empty_children = 1<<bits;
412 pr_debug("AT %p s=%u %lu\n", tn, (unsigned int) sizeof(struct tnode),
413 (unsigned long) (sizeof(struct node) << bits));
418 * Check whether a tnode 'n' is "full", i.e. it is an internal node
419 * and no bits are skipped. See discussion in dyntree paper p. 6
422 static inline int tnode_full(const struct tnode *tn, const struct node *n)
424 if (n == NULL || IS_LEAF(n))
427 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
430 static inline void put_child(struct trie *t, struct tnode *tn, int i, struct node *n)
432 tnode_put_child_reorg(tn, i, n, -1);
436 * Add a child at position i overwriting the old value.
437 * Update the value of full_children and empty_children.
440 static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull)
442 struct node *chi = tn->child[i];
445 BUG_ON(i >= 1<<tn->bits);
448 /* update emptyChildren */
449 if (n == NULL && chi != NULL)
450 tn->empty_children++;
451 else if (n != NULL && chi == NULL)
452 tn->empty_children--;
454 /* update fullChildren */
456 wasfull = tnode_full(tn, chi);
458 isfull = tnode_full(tn, n);
459 if (wasfull && !isfull)
461 else if (!wasfull && isfull)
465 node_set_parent(n, tn);
467 rcu_assign_pointer(tn->child[i], n);
470 static struct node *resize(struct trie *t, struct tnode *tn)
474 struct tnode *old_tn;
475 int inflate_threshold_use;
476 int halve_threshold_use;
482 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
483 tn, inflate_threshold, halve_threshold);
486 if (tn->empty_children == tnode_child_length(tn)) {
491 if (tn->empty_children == tnode_child_length(tn) - 1)
492 for (i = 0; i < tnode_child_length(tn); i++) {
499 /* compress one level */
500 node_set_parent(n, NULL);
505 * Double as long as the resulting node has a number of
506 * nonempty nodes that are above the threshold.
510 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
511 * the Helsinki University of Technology and Matti Tikkanen of Nokia
512 * Telecommunications, page 6:
513 * "A node is doubled if the ratio of non-empty children to all
514 * children in the *doubled* node is at least 'high'."
516 * 'high' in this instance is the variable 'inflate_threshold'. It
517 * is expressed as a percentage, so we multiply it with
518 * tnode_child_length() and instead of multiplying by 2 (since the
519 * child array will be doubled by inflate()) and multiplying
520 * the left-hand side by 100 (to handle the percentage thing) we
521 * multiply the left-hand side by 50.
523 * The left-hand side may look a bit weird: tnode_child_length(tn)
524 * - tn->empty_children is of course the number of non-null children
525 * in the current node. tn->full_children is the number of "full"
526 * children, that is non-null tnodes with a skip value of 0.
527 * All of those will be doubled in the resulting inflated tnode, so
528 * we just count them one extra time here.
530 * A clearer way to write this would be:
532 * to_be_doubled = tn->full_children;
533 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
536 * new_child_length = tnode_child_length(tn) * 2;
538 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
540 * if (new_fill_factor >= inflate_threshold)
542 * ...and so on, tho it would mess up the while () loop.
545 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
549 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
550 * inflate_threshold * new_child_length
552 * expand not_to_be_doubled and to_be_doubled, and shorten:
553 * 100 * (tnode_child_length(tn) - tn->empty_children +
554 * tn->full_children) >= inflate_threshold * new_child_length
556 * expand new_child_length:
557 * 100 * (tnode_child_length(tn) - tn->empty_children +
558 * tn->full_children) >=
559 * inflate_threshold * tnode_child_length(tn) * 2
562 * 50 * (tn->full_children + tnode_child_length(tn) -
563 * tn->empty_children) >= inflate_threshold *
564 * tnode_child_length(tn)
570 /* Keep root node larger */
573 inflate_threshold_use = inflate_threshold_root;
575 inflate_threshold_use = inflate_threshold;
579 while ((tn->full_children > 0 && max_resize-- &&
580 50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >=
581 inflate_threshold_use * tnode_child_length(tn))) {
587 #ifdef CONFIG_IP_FIB_TRIE_STATS
588 t->stats.resize_node_skipped++;
594 if (max_resize < 0) {
596 printk(KERN_WARNING "Fix inflate_threshold_root. Now=%d size=%d bits\n",
597 inflate_threshold_root, tn->bits);
599 printk(KERN_WARNING "Fix inflate_threshold. Now=%d size=%d bits\n",
600 inflate_threshold, tn->bits);
606 * Halve as long as the number of empty children in this
607 * node is above threshold.
611 /* Keep root node larger */
614 halve_threshold_use = halve_threshold_root;
616 halve_threshold_use = halve_threshold;
620 while (tn->bits > 1 && max_resize-- &&
621 100 * (tnode_child_length(tn) - tn->empty_children) <
622 halve_threshold_use * tnode_child_length(tn)) {
628 #ifdef CONFIG_IP_FIB_TRIE_STATS
629 t->stats.resize_node_skipped++;
635 if (max_resize < 0) {
637 printk(KERN_WARNING "Fix halve_threshold_root. Now=%d size=%d bits\n",
638 halve_threshold_root, tn->bits);
640 printk(KERN_WARNING "Fix halve_threshold. Now=%d size=%d bits\n",
641 halve_threshold, tn->bits);
644 /* Only one child remains */
645 if (tn->empty_children == tnode_child_length(tn) - 1)
646 for (i = 0; i < tnode_child_length(tn); i++) {
653 /* compress one level */
655 node_set_parent(n, NULL);
660 return (struct node *) tn;
663 static struct tnode *inflate(struct trie *t, struct tnode *tn)
665 struct tnode *oldtnode = tn;
666 int olen = tnode_child_length(tn);
669 pr_debug("In inflate\n");
671 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
674 return ERR_PTR(-ENOMEM);
677 * Preallocate and store tnodes before the actual work so we
678 * don't get into an inconsistent state if memory allocation
679 * fails. In case of failure we return the oldnode and inflate
680 * of tnode is ignored.
683 for (i = 0; i < olen; i++) {
684 struct tnode *inode = (struct tnode *) tnode_get_child(oldtnode, i);
688 inode->pos == oldtnode->pos + oldtnode->bits &&
690 struct tnode *left, *right;
691 t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
693 left = tnode_new(inode->key&(~m), inode->pos + 1,
698 right = tnode_new(inode->key|m, inode->pos + 1,
706 put_child(t, tn, 2*i, (struct node *) left);
707 put_child(t, tn, 2*i+1, (struct node *) right);
711 for (i = 0; i < olen; i++) {
713 struct node *node = tnode_get_child(oldtnode, i);
714 struct tnode *left, *right;
721 /* A leaf or an internal node with skipped bits */
723 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
724 tn->pos + tn->bits - 1) {
725 if (tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits,
727 put_child(t, tn, 2*i, node);
729 put_child(t, tn, 2*i+1, node);
733 /* An internal node with two children */
734 inode = (struct tnode *) node;
736 if (inode->bits == 1) {
737 put_child(t, tn, 2*i, inode->child[0]);
738 put_child(t, tn, 2*i+1, inode->child[1]);
744 /* An internal node with more than two children */
746 /* We will replace this node 'inode' with two new
747 * ones, 'left' and 'right', each with half of the
748 * original children. The two new nodes will have
749 * a position one bit further down the key and this
750 * means that the "significant" part of their keys
751 * (see the discussion near the top of this file)
752 * will differ by one bit, which will be "0" in
753 * left's key and "1" in right's key. Since we are
754 * moving the key position by one step, the bit that
755 * we are moving away from - the bit at position
756 * (inode->pos) - is the one that will differ between
757 * left and right. So... we synthesize that bit in the
759 * The mask 'm' below will be a single "one" bit at
760 * the position (inode->pos)
763 /* Use the old key, but set the new significant
767 left = (struct tnode *) tnode_get_child(tn, 2*i);
768 put_child(t, tn, 2*i, NULL);
772 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
773 put_child(t, tn, 2*i+1, NULL);
777 size = tnode_child_length(left);
778 for (j = 0; j < size; j++) {
779 put_child(t, left, j, inode->child[j]);
780 put_child(t, right, j, inode->child[j + size]);
782 put_child(t, tn, 2*i, resize(t, left));
783 put_child(t, tn, 2*i+1, resize(t, right));
787 tnode_free(oldtnode);
791 int size = tnode_child_length(tn);
794 for (j = 0; j < size; j++)
796 tnode_free((struct tnode *)tn->child[j]);
800 return ERR_PTR(-ENOMEM);
804 static struct tnode *halve(struct trie *t, struct tnode *tn)
806 struct tnode *oldtnode = tn;
807 struct node *left, *right;
809 int olen = tnode_child_length(tn);
811 pr_debug("In halve\n");
813 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
816 return ERR_PTR(-ENOMEM);
819 * Preallocate and store tnodes before the actual work so we
820 * don't get into an inconsistent state if memory allocation
821 * fails. In case of failure we return the oldnode and halve
822 * of tnode is ignored.
825 for (i = 0; i < olen; i += 2) {
826 left = tnode_get_child(oldtnode, i);
827 right = tnode_get_child(oldtnode, i+1);
829 /* Two nonempty children */
833 newn = tnode_new(left->key, tn->pos + tn->bits, 1);
838 put_child(t, tn, i/2, (struct node *)newn);
843 for (i = 0; i < olen; i += 2) {
844 struct tnode *newBinNode;
846 left = tnode_get_child(oldtnode, i);
847 right = tnode_get_child(oldtnode, i+1);
849 /* At least one of the children is empty */
851 if (right == NULL) /* Both are empty */
853 put_child(t, tn, i/2, right);
858 put_child(t, tn, i/2, left);
862 /* Two nonempty children */
863 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
864 put_child(t, tn, i/2, NULL);
865 put_child(t, newBinNode, 0, left);
866 put_child(t, newBinNode, 1, right);
867 put_child(t, tn, i/2, resize(t, newBinNode));
869 tnode_free(oldtnode);
873 int size = tnode_child_length(tn);
876 for (j = 0; j < size; j++)
878 tnode_free((struct tnode *)tn->child[j]);
882 return ERR_PTR(-ENOMEM);
886 /* readside must use rcu_read_lock currently dump routines
887 via get_fa_head and dump */
889 static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
891 struct hlist_head *head = &l->list;
892 struct hlist_node *node;
893 struct leaf_info *li;
895 hlist_for_each_entry_rcu(li, node, head, hlist)
896 if (li->plen == plen)
902 static inline struct list_head * get_fa_head(struct leaf *l, int plen)
904 struct leaf_info *li = find_leaf_info(l, plen);
912 static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
914 struct leaf_info *li = NULL, *last = NULL;
915 struct hlist_node *node;
917 if (hlist_empty(head)) {
918 hlist_add_head_rcu(&new->hlist, head);
920 hlist_for_each_entry(li, node, head, hlist) {
921 if (new->plen > li->plen)
927 hlist_add_after_rcu(&last->hlist, &new->hlist);
929 hlist_add_before_rcu(&new->hlist, &li->hlist);
933 /* rcu_read_lock needs to be hold by caller from readside */
936 fib_find_node(struct trie *t, u32 key)
943 n = rcu_dereference(t->trie);
945 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
946 tn = (struct tnode *) n;
950 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
951 pos = tn->pos + tn->bits;
952 n = tnode_get_child_rcu(tn, tkey_extract_bits(key, tn->pos, tn->bits));
956 /* Case we have found a leaf. Compare prefixes */
958 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
959 return (struct leaf *)n;
964 static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
967 t_key cindex, key = tn->key;
970 while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) {
971 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
972 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
973 tn = (struct tnode *) resize (t, (struct tnode *)tn);
974 tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull);
976 tp = node_parent((struct node *) tn);
982 /* Handle last (top) tnode */
984 tn = (struct tnode*) resize(t, (struct tnode *)tn);
986 return (struct node*) tn;
989 /* only used from updater-side */
991 static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
994 struct tnode *tp = NULL, *tn = NULL;
998 struct list_head *fa_head = NULL;
999 struct leaf_info *li;
1005 /* If we point to NULL, stop. Either the tree is empty and we should
1006 * just put a new leaf in if, or we have reached an empty child slot,
1007 * and we should just put our new leaf in that.
1008 * If we point to a T_TNODE, check if it matches our key. Note that
1009 * a T_TNODE might be skipping any number of bits - its 'pos' need
1010 * not be the parent's 'pos'+'bits'!
1012 * If it does match the current key, get pos/bits from it, extract
1013 * the index from our key, push the T_TNODE and walk the tree.
1015 * If it doesn't, we have to replace it with a new T_TNODE.
1017 * If we point to a T_LEAF, it might or might not have the same key
1018 * as we do. If it does, just change the value, update the T_LEAF's
1019 * value, and return it.
1020 * If it doesn't, we need to replace it with a T_TNODE.
1023 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1024 tn = (struct tnode *) n;
1028 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1030 pos = tn->pos + tn->bits;
1031 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
1033 BUG_ON(n && node_parent(n) != tn);
1039 * n ----> NULL, LEAF or TNODE
1041 * tp is n's (parent) ----> NULL or TNODE
1044 BUG_ON(tp && IS_LEAF(tp));
1046 /* Case 1: n is a leaf. Compare prefixes */
1048 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1049 l = (struct leaf *) n;
1050 li = leaf_info_new(plen);
1055 fa_head = &li->falh;
1056 insert_leaf_info(&l->list, li);
1065 li = leaf_info_new(plen);
1068 tnode_free((struct tnode *) l);
1072 fa_head = &li->falh;
1073 insert_leaf_info(&l->list, li);
1075 if (t->trie && n == NULL) {
1076 /* Case 2: n is NULL, and will just insert a new leaf */
1078 node_set_parent((struct node *)l, tp);
1080 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1081 put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
1083 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1085 * Add a new tnode here
1086 * first tnode need some special handling
1090 pos = tp->pos+tp->bits;
1095 newpos = tkey_mismatch(key, pos, n->key);
1096 tn = tnode_new(n->key, newpos, 1);
1099 tn = tnode_new(key, newpos, 1); /* First tnode */
1104 tnode_free((struct tnode *) l);
1108 node_set_parent((struct node *)tn, tp);
1110 missbit = tkey_extract_bits(key, newpos, 1);
1111 put_child(t, tn, missbit, (struct node *)l);
1112 put_child(t, tn, 1-missbit, n);
1115 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1116 put_child(t, (struct tnode *)tp, cindex, (struct node *)tn);
1118 rcu_assign_pointer(t->trie, (struct node *)tn); /* First tnode */
1123 if (tp && tp->pos + tp->bits > 32)
1124 printk(KERN_WARNING "fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1125 tp, tp->pos, tp->bits, key, plen);
1127 /* Rebalance the trie */
1129 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
1135 * Caller must hold RTNL.
1137 static int fn_trie_insert(struct fib_table *tb, struct fib_config *cfg)
1139 struct trie *t = (struct trie *) tb->tb_data;
1140 struct fib_alias *fa, *new_fa;
1141 struct list_head *fa_head = NULL;
1142 struct fib_info *fi;
1143 int plen = cfg->fc_dst_len;
1144 u8 tos = cfg->fc_tos;
1152 key = ntohl(cfg->fc_dst);
1154 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1156 mask = ntohl(inet_make_mask(plen));
1163 fi = fib_create_info(cfg);
1169 l = fib_find_node(t, key);
1173 fa_head = get_fa_head(l, plen);
1174 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1177 /* Now fa, if non-NULL, points to the first fib alias
1178 * with the same keys [prefix,tos,priority], if such key already
1179 * exists or to the node before which we will insert new one.
1181 * If fa is NULL, we will need to allocate a new one and
1182 * insert to the head of f.
1184 * If f is NULL, no fib node matched the destination key
1185 * and we need to allocate a new one of those as well.
1188 if (fa && fa->fa_info->fib_priority == fi->fib_priority) {
1189 struct fib_alias *fa_orig;
1192 if (cfg->fc_nlflags & NLM_F_EXCL)
1195 if (cfg->fc_nlflags & NLM_F_REPLACE) {
1196 struct fib_info *fi_drop;
1199 if (fi->fib_treeref > 1)
1203 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1207 fi_drop = fa->fa_info;
1208 new_fa->fa_tos = fa->fa_tos;
1209 new_fa->fa_info = fi;
1210 new_fa->fa_type = cfg->fc_type;
1211 new_fa->fa_scope = cfg->fc_scope;
1212 state = fa->fa_state;
1213 new_fa->fa_state &= ~FA_S_ACCESSED;
1215 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1216 alias_free_mem_rcu(fa);
1218 fib_release_info(fi_drop);
1219 if (state & FA_S_ACCESSED)
1221 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1222 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1226 /* Error if we find a perfect match which
1227 * uses the same scope, type, and nexthop
1231 list_for_each_entry(fa, fa_orig->fa_list.prev, fa_list) {
1232 if (fa->fa_tos != tos)
1234 if (fa->fa_info->fib_priority != fi->fib_priority)
1236 if (fa->fa_type == cfg->fc_type &&
1237 fa->fa_scope == cfg->fc_scope &&
1238 fa->fa_info == fi) {
1242 if (!(cfg->fc_nlflags & NLM_F_APPEND))
1246 if (!(cfg->fc_nlflags & NLM_F_CREATE))
1250 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1254 new_fa->fa_info = fi;
1255 new_fa->fa_tos = tos;
1256 new_fa->fa_type = cfg->fc_type;
1257 new_fa->fa_scope = cfg->fc_scope;
1258 new_fa->fa_state = 0;
1260 * Insert new entry to the list.
1264 fa_head = fib_insert_node(t, key, plen);
1265 if (unlikely(!fa_head)) {
1267 goto out_free_new_fa;
1271 list_add_tail_rcu(&new_fa->fa_list,
1272 (fa ? &fa->fa_list : fa_head));
1277 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1278 &cfg->fc_nlinfo, 0);
1283 kmem_cache_free(fn_alias_kmem, new_fa);
1285 fib_release_info(fi);
1291 /* should be called with rcu_read_lock */
1292 static inline int check_leaf(struct trie *t, struct leaf *l,
1293 t_key key, int *plen, const struct flowi *flp,
1294 struct fib_result *res)
1298 struct leaf_info *li;
1299 struct hlist_head *hhead = &l->list;
1300 struct hlist_node *node;
1302 hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1304 mask = inet_make_mask(i);
1305 if (l->key != (key & ntohl(mask)))
1308 if ((err = fib_semantic_match(&li->falh, flp, res, htonl(l->key), mask, i)) <= 0) {
1310 #ifdef CONFIG_IP_FIB_TRIE_STATS
1311 t->stats.semantic_match_passed++;
1315 #ifdef CONFIG_IP_FIB_TRIE_STATS
1316 t->stats.semantic_match_miss++;
1323 fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
1325 struct trie *t = (struct trie *) tb->tb_data;
1330 t_key key = ntohl(flp->fl4_dst);
1333 int current_prefix_length = KEYLENGTH;
1335 t_key node_prefix, key_prefix, pref_mismatch;
1340 n = rcu_dereference(t->trie);
1344 #ifdef CONFIG_IP_FIB_TRIE_STATS
1350 if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
1354 pn = (struct tnode *) n;
1362 cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1365 n = tnode_get_child(pn, cindex);
1368 #ifdef CONFIG_IP_FIB_TRIE_STATS
1369 t->stats.null_node_hit++;
1375 if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
1383 cn = (struct tnode *)n;
1386 * It's a tnode, and we can do some extra checks here if we
1387 * like, to avoid descending into a dead-end branch.
1388 * This tnode is in the parent's child array at index
1389 * key[p_pos..p_pos+p_bits] but potentially with some bits
1390 * chopped off, so in reality the index may be just a
1391 * subprefix, padded with zero at the end.
1392 * We can also take a look at any skipped bits in this
1393 * tnode - everything up to p_pos is supposed to be ok,
1394 * and the non-chopped bits of the index (se previous
1395 * paragraph) are also guaranteed ok, but the rest is
1396 * considered unknown.
1398 * The skipped bits are key[pos+bits..cn->pos].
1401 /* If current_prefix_length < pos+bits, we are already doing
1402 * actual prefix matching, which means everything from
1403 * pos+(bits-chopped_off) onward must be zero along some
1404 * branch of this subtree - otherwise there is *no* valid
1405 * prefix present. Here we can only check the skipped
1406 * bits. Remember, since we have already indexed into the
1407 * parent's child array, we know that the bits we chopped of
1411 /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */
1413 if (current_prefix_length < pos+bits) {
1414 if (tkey_extract_bits(cn->key, current_prefix_length,
1415 cn->pos - current_prefix_length) != 0 ||
1421 * If chopped_off=0, the index is fully validated and we
1422 * only need to look at the skipped bits for this, the new,
1423 * tnode. What we actually want to do is to find out if
1424 * these skipped bits match our key perfectly, or if we will
1425 * have to count on finding a matching prefix further down,
1426 * because if we do, we would like to have some way of
1427 * verifying the existence of such a prefix at this point.
1430 /* The only thing we can do at this point is to verify that
1431 * any such matching prefix can indeed be a prefix to our
1432 * key, and if the bits in the node we are inspecting that
1433 * do not match our key are not ZERO, this cannot be true.
1434 * Thus, find out where there is a mismatch (before cn->pos)
1435 * and verify that all the mismatching bits are zero in the
1439 /* Note: We aren't very concerned about the piece of the key
1440 * that precede pn->pos+pn->bits, since these have already been
1441 * checked. The bits after cn->pos aren't checked since these are
1442 * by definition "unknown" at this point. Thus, what we want to
1443 * see is if we are about to enter the "prefix matching" state,
1444 * and in that case verify that the skipped bits that will prevail
1445 * throughout this subtree are zero, as they have to be if we are
1446 * to find a matching prefix.
1449 node_prefix = mask_pfx(cn->key, cn->pos);
1450 key_prefix = mask_pfx(key, cn->pos);
1451 pref_mismatch = key_prefix^node_prefix;
1454 /* In short: If skipped bits in this node do not match the search
1455 * key, enter the "prefix matching" state.directly.
1457 if (pref_mismatch) {
1458 while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
1460 pref_mismatch = pref_mismatch <<1;
1462 key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);
1464 if (key_prefix != 0)
1467 if (current_prefix_length >= cn->pos)
1468 current_prefix_length = mp;
1471 pn = (struct tnode *)n; /* Descend */
1478 /* As zero don't change the child key (cindex) */
1479 while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1))))
1482 /* Decrease current_... with bits chopped off */
1483 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1484 current_prefix_length = pn->pos + pn->bits - chopped_off;
1487 * Either we do the actual chop off according or if we have
1488 * chopped off all bits in this tnode walk up to our parent.
1491 if (chopped_off <= pn->bits) {
1492 cindex &= ~(1 << (chopped_off-1));
1494 struct tnode *parent = node_parent((struct node *) pn);
1498 /* Get Child's index */
1499 cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1503 #ifdef CONFIG_IP_FIB_TRIE_STATS
1504 t->stats.backtrack++;
1516 /* only called from updater side */
1517 static int trie_leaf_remove(struct trie *t, t_key key)
1520 struct tnode *tp = NULL;
1521 struct node *n = t->trie;
1524 pr_debug("entering trie_leaf_remove(%p)\n", n);
1526 /* Note that in the case skipped bits, those bits are *not* checked!
1527 * When we finish this, we will have NULL or a T_LEAF, and the
1528 * T_LEAF may or may not match our key.
1531 while (n != NULL && IS_TNODE(n)) {
1532 struct tnode *tn = (struct tnode *) n;
1534 n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits));
1536 BUG_ON(n && node_parent(n) != tn);
1538 l = (struct leaf *) n;
1540 if (!n || !tkey_equals(l->key, key))
1545 * Remove the leaf and rebalance the tree
1550 tp = node_parent(n);
1551 tnode_free((struct tnode *) n);
1554 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1555 put_child(t, (struct tnode *)tp, cindex, NULL);
1556 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
1558 rcu_assign_pointer(t->trie, NULL);
1564 * Caller must hold RTNL.
1566 static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
1568 struct trie *t = (struct trie *) tb->tb_data;
1570 int plen = cfg->fc_dst_len;
1571 u8 tos = cfg->fc_tos;
1572 struct fib_alias *fa, *fa_to_delete;
1573 struct list_head *fa_head;
1575 struct leaf_info *li;
1580 key = ntohl(cfg->fc_dst);
1581 mask = ntohl(inet_make_mask(plen));
1587 l = fib_find_node(t, key);
1592 fa_head = get_fa_head(l, plen);
1593 fa = fib_find_alias(fa_head, tos, 0);
1598 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1600 fa_to_delete = NULL;
1601 fa_head = fa->fa_list.prev;
1603 list_for_each_entry(fa, fa_head, fa_list) {
1604 struct fib_info *fi = fa->fa_info;
1606 if (fa->fa_tos != tos)
1609 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1610 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1611 fa->fa_scope == cfg->fc_scope) &&
1612 (!cfg->fc_protocol ||
1613 fi->fib_protocol == cfg->fc_protocol) &&
1614 fib_nh_match(cfg, fi) == 0) {
1624 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1625 &cfg->fc_nlinfo, 0);
1627 l = fib_find_node(t, key);
1628 li = find_leaf_info(l, plen);
1630 list_del_rcu(&fa->fa_list);
1632 if (list_empty(fa_head)) {
1633 hlist_del_rcu(&li->hlist);
1637 if (hlist_empty(&l->list))
1638 trie_leaf_remove(t, key);
1640 if (fa->fa_state & FA_S_ACCESSED)
1643 fib_release_info(fa->fa_info);
1644 alias_free_mem_rcu(fa);
1648 static int trie_flush_list(struct trie *t, struct list_head *head)
1650 struct fib_alias *fa, *fa_node;
1653 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1654 struct fib_info *fi = fa->fa_info;
1656 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1657 list_del_rcu(&fa->fa_list);
1658 fib_release_info(fa->fa_info);
1659 alias_free_mem_rcu(fa);
1666 static int trie_flush_leaf(struct trie *t, struct leaf *l)
1669 struct hlist_head *lih = &l->list;
1670 struct hlist_node *node, *tmp;
1671 struct leaf_info *li = NULL;
1673 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
1674 found += trie_flush_list(t, &li->falh);
1676 if (list_empty(&li->falh)) {
1677 hlist_del_rcu(&li->hlist);
1684 /* rcu_read_lock needs to be hold by caller from readside */
1686 static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
1688 struct node *c = (struct node *) thisleaf;
1691 struct node *trie = rcu_dereference(t->trie);
1697 if (IS_LEAF(trie)) /* trie w. just a leaf */
1698 return (struct leaf *) trie;
1700 p = (struct tnode*) trie; /* Start */
1702 p = node_parent_rcu(c);
1707 /* Find the next child of the parent */
1709 pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits);
1713 last = 1 << p->bits;
1714 for (idx = pos; idx < last ; idx++) {
1715 c = rcu_dereference(p->child[idx]);
1720 /* Decend if tnode */
1721 while (IS_TNODE(c)) {
1722 p = (struct tnode *) c;
1725 /* Rightmost non-NULL branch */
1726 if (p && IS_TNODE(p))
1727 while (!(c = rcu_dereference(p->child[idx]))
1728 && idx < (1<<p->bits)) idx++;
1730 /* Done with this tnode? */
1731 if (idx >= (1 << p->bits) || !c)
1734 return (struct leaf *) c;
1737 /* No more children go up one step */
1738 c = (struct node *) p;
1739 p = node_parent_rcu(c);
1741 return NULL; /* Ready. Root of trie */
1745 * Caller must hold RTNL.
1747 static int fn_trie_flush(struct fib_table *tb)
1749 struct trie *t = (struct trie *) tb->tb_data;
1750 struct leaf *ll = NULL, *l = NULL;
1753 for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1754 found += trie_flush_leaf(t, l);
1756 if (ll && hlist_empty(&ll->list))
1757 trie_leaf_remove(t, ll->key);
1761 if (ll && hlist_empty(&ll->list))
1762 trie_leaf_remove(t, ll->key);
1764 pr_debug("trie_flush found=%d\n", found);
1769 fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
1771 struct trie *t = (struct trie *) tb->tb_data;
1772 int order, last_idx;
1773 struct fib_info *fi = NULL;
1774 struct fib_info *last_resort;
1775 struct fib_alias *fa = NULL;
1776 struct list_head *fa_head;
1785 l = fib_find_node(t, 0);
1789 fa_head = get_fa_head(l, 0);
1793 if (list_empty(fa_head))
1796 list_for_each_entry_rcu(fa, fa_head, fa_list) {
1797 struct fib_info *next_fi = fa->fa_info;
1799 if (fa->fa_scope != res->scope ||
1800 fa->fa_type != RTN_UNICAST)
1803 if (next_fi->fib_priority > res->fi->fib_priority)
1805 if (!next_fi->fib_nh[0].nh_gw ||
1806 next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
1808 fa->fa_state |= FA_S_ACCESSED;
1811 if (next_fi != res->fi)
1813 } else if (!fib_detect_death(fi, order, &last_resort,
1814 &last_idx, tb->tb_default)) {
1815 fib_result_assign(res, fi);
1816 tb->tb_default = order;
1822 if (order <= 0 || fi == NULL) {
1823 tb->tb_default = -1;
1827 if (!fib_detect_death(fi, order, &last_resort, &last_idx,
1829 fib_result_assign(res, fi);
1830 tb->tb_default = order;
1834 fib_result_assign(res, last_resort);
1835 tb->tb_default = last_idx;
1840 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fib_table *tb,
1841 struct sk_buff *skb, struct netlink_callback *cb)
1844 struct fib_alias *fa;
1846 __be32 xkey = htonl(key);
1851 /* rcu_read_lock is hold by caller */
1853 list_for_each_entry_rcu(fa, fah, fa_list) {
1858 BUG_ON(!fa->fa_info);
1860 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1869 fa->fa_info, 0) < 0) {
1879 static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb,
1880 struct netlink_callback *cb)
1883 struct list_head *fa_head;
1884 struct leaf *l = NULL;
1888 for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1892 memset(&cb->args[4], 0,
1893 sizeof(cb->args) - 4*sizeof(cb->args[0]));
1895 fa_head = get_fa_head(l, plen);
1900 if (list_empty(fa_head))
1903 if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
1912 static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlink_callback *cb)
1915 struct trie *t = (struct trie *) tb->tb_data;
1920 for (m = 0; m <= 32; m++) {
1924 memset(&cb->args[3], 0,
1925 sizeof(cb->args) - 3*sizeof(cb->args[0]));
1927 if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) {
1940 void __init fib_hash_init(void)
1942 fn_alias_kmem = kmem_cache_create("ip_fib_alias", sizeof(struct fib_alias),
1943 0, SLAB_PANIC, NULL);
1945 trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1946 max(sizeof(struct leaf),
1947 sizeof(struct leaf_info)),
1948 0, SLAB_PANIC, NULL);
1952 /* Fix more generic FIB names for init later */
1953 struct fib_table *fib_hash_table(u32 id)
1955 struct fib_table *tb;
1958 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1964 tb->tb_default = -1;
1965 tb->tb_lookup = fn_trie_lookup;
1966 tb->tb_insert = fn_trie_insert;
1967 tb->tb_delete = fn_trie_delete;
1968 tb->tb_flush = fn_trie_flush;
1969 tb->tb_select_default = fn_trie_select_default;
1970 tb->tb_dump = fn_trie_dump;
1972 t = (struct trie *) tb->tb_data;
1973 memset(t, 0, sizeof(*t));
1975 if (id == RT_TABLE_LOCAL)
1976 printk(KERN_INFO "IPv4 FIB: Using LC-trie version %s\n", VERSION);
1981 #ifdef CONFIG_PROC_FS
1982 /* Depth first Trie walk iterator */
1983 struct fib_trie_iter {
1984 struct seq_net_private p;
1985 struct trie *trie_local, *trie_main;
1986 struct tnode *tnode;
1992 static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
1994 struct tnode *tn = iter->tnode;
1995 unsigned cindex = iter->index;
1998 /* A single entry routing table */
2002 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2003 iter->tnode, iter->index, iter->depth);
2005 while (cindex < (1<<tn->bits)) {
2006 struct node *n = tnode_get_child_rcu(tn, cindex);
2011 iter->index = cindex + 1;
2013 /* push down one level */
2014 iter->tnode = (struct tnode *) n;
2024 /* Current node exhausted, pop back up */
2025 p = node_parent_rcu((struct node *)tn);
2027 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2037 static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
2045 n = rcu_dereference(t->trie);
2052 iter->tnode = (struct tnode *) n;
2067 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2070 struct fib_trie_iter iter;
2072 memset(s, 0, sizeof(*s));
2075 for (n = fib_trie_get_first(&iter, t); n;
2076 n = fib_trie_get_next(&iter)) {
2079 s->totdepth += iter.depth;
2080 if (iter.depth > s->maxdepth)
2081 s->maxdepth = iter.depth;
2083 const struct tnode *tn = (const struct tnode *) n;
2087 if (tn->bits < MAX_STAT_DEPTH)
2088 s->nodesizes[tn->bits]++;
2090 for (i = 0; i < (1<<tn->bits); i++)
2099 * This outputs /proc/net/fib_triestats
2101 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2103 unsigned i, max, pointers, bytes, avdepth;
2106 avdepth = stat->totdepth*100 / stat->leaves;
2110 seq_printf(seq, "\tAver depth: %u.%02d\n", avdepth / 100, avdepth % 100 );
2111 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
2113 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
2115 bytes = sizeof(struct leaf) * stat->leaves;
2116 seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2117 bytes += sizeof(struct tnode) * stat->tnodes;
2119 max = MAX_STAT_DEPTH;
2120 while (max > 0 && stat->nodesizes[max-1] == 0)
2124 for (i = 1; i <= max; i++)
2125 if (stat->nodesizes[i] != 0) {
2126 seq_printf(seq, " %u: %u", i, stat->nodesizes[i]);
2127 pointers += (1<<i) * stat->nodesizes[i];
2129 seq_putc(seq, '\n');
2130 seq_printf(seq, "\tPointers: %u\n", pointers);
2132 bytes += sizeof(struct node *) * pointers;
2133 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2134 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
2137 #ifdef CONFIG_IP_FIB_TRIE_STATS
2138 static void trie_show_usage(struct seq_file *seq,
2139 const struct trie_use_stats *stats)
2141 seq_printf(seq, "\nCounters:\n---------\n");
2142 seq_printf(seq,"gets = %u\n", stats->gets);
2143 seq_printf(seq,"backtracks = %u\n", stats->backtrack);
2144 seq_printf(seq,"semantic match passed = %u\n", stats->semantic_match_passed);
2145 seq_printf(seq,"semantic match miss = %u\n", stats->semantic_match_miss);
2146 seq_printf(seq,"null node hit= %u\n", stats->null_node_hit);
2147 seq_printf(seq,"skipped node resize = %u\n\n", stats->resize_node_skipped);
2149 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2151 static void fib_trie_show(struct seq_file *seq, const char *name, struct trie *trie)
2153 struct trie_stat stat;
2155 seq_printf(seq, "%s: %d\n", name, trie->size);
2156 trie_collect_stats(trie, &stat);
2157 trie_show_stats(seq, &stat);
2158 #ifdef CONFIG_IP_FIB_TRIE_STATS
2159 trie_show_usage(seq, &trie->stats);
2163 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2165 struct net *net = (struct net *)seq->private;
2166 struct fib_table *tb;
2169 "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
2170 sizeof(struct leaf), sizeof(struct tnode));
2172 tb = fib_get_table(net, RT_TABLE_LOCAL);
2174 fib_trie_show(seq, "Local", (struct trie *) tb->tb_data);
2176 tb = fib_get_table(net, RT_TABLE_MAIN);
2178 fib_trie_show(seq, "Main", (struct trie *) tb->tb_data);
2183 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2188 net = get_proc_net(inode);
2191 err = single_open(file, fib_triestat_seq_show, net);
2199 static int fib_triestat_seq_release(struct inode *ino, struct file *f)
2201 struct seq_file *seq = f->private_data;
2202 put_net(seq->private);
2203 return single_release(ino, f);
2206 static const struct file_operations fib_triestat_fops = {
2207 .owner = THIS_MODULE,
2208 .open = fib_triestat_seq_open,
2210 .llseek = seq_lseek,
2211 .release = fib_triestat_seq_release,
2214 static struct node *fib_trie_get_idx(struct fib_trie_iter *iter,
2220 for (n = fib_trie_get_first(iter, iter->trie_local);
2221 n; ++idx, n = fib_trie_get_next(iter)) {
2226 for (n = fib_trie_get_first(iter, iter->trie_main);
2227 n; ++idx, n = fib_trie_get_next(iter)) {
2234 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2237 struct fib_trie_iter *iter = seq->private;
2238 struct fib_table *tb;
2240 if (!iter->trie_local) {
2241 tb = fib_get_table(iter->p.net, RT_TABLE_LOCAL);
2243 iter->trie_local = (struct trie *) tb->tb_data;
2245 if (!iter->trie_main) {
2246 tb = fib_get_table(iter->p.net, RT_TABLE_MAIN);
2248 iter->trie_main = (struct trie *) tb->tb_data;
2252 return SEQ_START_TOKEN;
2253 return fib_trie_get_idx(iter, *pos - 1);
2256 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2258 struct fib_trie_iter *iter = seq->private;
2262 if (v == SEQ_START_TOKEN)
2263 return fib_trie_get_idx(iter, 0);
2265 v = fib_trie_get_next(iter);
2270 /* continue scan in next trie */
2271 if (iter->trie == iter->trie_local)
2272 return fib_trie_get_first(iter, iter->trie_main);
2277 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(char *buf, size_t len, enum rt_scope_t s)
2291 case RT_SCOPE_UNIVERSE: return "universe";
2292 case RT_SCOPE_SITE: return "site";
2293 case RT_SCOPE_LINK: return "link";
2294 case RT_SCOPE_HOST: return "host";
2295 case RT_SCOPE_NOWHERE: return "nowhere";
2297 snprintf(buf, len, "scope=%d", s);
2302 static const char *rtn_type_names[__RTN_MAX] = {
2303 [RTN_UNSPEC] = "UNSPEC",
2304 [RTN_UNICAST] = "UNICAST",
2305 [RTN_LOCAL] = "LOCAL",
2306 [RTN_BROADCAST] = "BROADCAST",
2307 [RTN_ANYCAST] = "ANYCAST",
2308 [RTN_MULTICAST] = "MULTICAST",
2309 [RTN_BLACKHOLE] = "BLACKHOLE",
2310 [RTN_UNREACHABLE] = "UNREACHABLE",
2311 [RTN_PROHIBIT] = "PROHIBIT",
2312 [RTN_THROW] = "THROW",
2314 [RTN_XRESOLVE] = "XRESOLVE",
2317 static inline const char *rtn_type(char *buf, size_t len, unsigned t)
2319 if (t < __RTN_MAX && rtn_type_names[t])
2320 return rtn_type_names[t];
2321 snprintf(buf, len, "type %u", t);
2325 /* Pretty print the trie */
2326 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2328 const struct fib_trie_iter *iter = seq->private;
2331 if (v == SEQ_START_TOKEN)
2334 if (!node_parent_rcu(n)) {
2335 if (iter->trie == iter->trie_local)
2336 seq_puts(seq, "<local>:\n");
2338 seq_puts(seq, "<main>:\n");
2342 struct tnode *tn = (struct tnode *) n;
2343 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2345 seq_indent(seq, iter->depth-1);
2346 seq_printf(seq, " +-- %d.%d.%d.%d/%d %d %d %d\n",
2347 NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
2348 tn->empty_children);
2351 struct leaf *l = (struct leaf *) n;
2353 __be32 val = htonl(l->key);
2355 seq_indent(seq, iter->depth);
2356 seq_printf(seq, " |-- %d.%d.%d.%d\n", NIPQUAD(val));
2357 for (i = 32; i >= 0; i--) {
2358 struct leaf_info *li = find_leaf_info(l, i);
2361 struct fib_alias *fa;
2363 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2364 char buf1[32], buf2[32];
2366 seq_indent(seq, iter->depth+1);
2367 seq_printf(seq, " /%d %s %s", i,
2368 rtn_scope(buf1, sizeof(buf1),
2370 rtn_type(buf2, sizeof(buf2),
2373 seq_printf(seq, "tos =%d\n",
2375 seq_putc(seq, '\n');
2384 static const struct seq_operations fib_trie_seq_ops = {
2385 .start = fib_trie_seq_start,
2386 .next = fib_trie_seq_next,
2387 .stop = fib_trie_seq_stop,
2388 .show = fib_trie_seq_show,
2391 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2393 return seq_open_net(inode, file, &fib_trie_seq_ops,
2394 sizeof(struct fib_trie_iter));
2397 static const struct file_operations fib_trie_fops = {
2398 .owner = THIS_MODULE,
2399 .open = fib_trie_seq_open,
2401 .llseek = seq_lseek,
2402 .release = seq_release_net,
2405 static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2407 static unsigned type2flags[RTN_MAX + 1] = {
2408 [7] = RTF_REJECT, [8] = RTF_REJECT,
2410 unsigned flags = type2flags[type];
2412 if (fi && fi->fib_nh->nh_gw)
2413 flags |= RTF_GATEWAY;
2414 if (mask == htonl(0xFFFFFFFF))
2421 * This outputs /proc/net/route.
2422 * The format of the file is not supposed to be changed
2423 * and needs to be same as fib_hash output to avoid breaking
2426 static int fib_route_seq_show(struct seq_file *seq, void *v)
2428 const struct fib_trie_iter *iter = seq->private;
2433 if (v == SEQ_START_TOKEN) {
2434 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2435 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2440 if (iter->trie == iter->trie_local)
2445 for (i=32; i>=0; i--) {
2446 struct leaf_info *li = find_leaf_info(l, i);
2447 struct fib_alias *fa;
2448 __be32 mask, prefix;
2453 mask = inet_make_mask(li->plen);
2454 prefix = htonl(l->key);
2456 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2457 const struct fib_info *fi = fa->fa_info;
2458 unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2460 if (fa->fa_type == RTN_BROADCAST
2461 || fa->fa_type == RTN_MULTICAST)
2465 snprintf(bf, sizeof(bf),
2466 "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2467 fi->fib_dev ? fi->fib_dev->name : "*",
2469 fi->fib_nh->nh_gw, flags, 0, 0,
2472 (fi->fib_advmss ? fi->fib_advmss + 40 : 0),
2476 snprintf(bf, sizeof(bf),
2477 "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2478 prefix, 0, flags, 0, 0, 0,
2481 seq_printf(seq, "%-127s\n", bf);
2488 static const struct seq_operations fib_route_seq_ops = {
2489 .start = fib_trie_seq_start,
2490 .next = fib_trie_seq_next,
2491 .stop = fib_trie_seq_stop,
2492 .show = fib_route_seq_show,
2495 static int fib_route_seq_open(struct inode *inode, struct file *file)
2497 return seq_open_net(inode, file, &fib_route_seq_ops,
2498 sizeof(struct fib_trie_iter));
2501 static const struct file_operations fib_route_fops = {
2502 .owner = THIS_MODULE,
2503 .open = fib_route_seq_open,
2505 .llseek = seq_lseek,
2506 .release = seq_release_net,
2509 int __net_init fib_proc_init(struct net *net)
2511 if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
2514 if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
2515 &fib_triestat_fops))
2518 if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
2524 proc_net_remove(net, "fib_triestat");
2526 proc_net_remove(net, "fib_trie");
2531 void __net_exit fib_proc_exit(struct net *net)
2533 proc_net_remove(net, "fib_trie");
2534 proc_net_remove(net, "fib_triestat");
2535 proc_net_remove(net, "route");
2538 #endif /* CONFIG_PROC_FS */