2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version
5 * 2 of the License, or (at your option) any later version.
7 * Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
8 * & Swedish University of Agricultural Sciences.
10 * Jens Laas <jens.laas@data.slu.se> Swedish University of
11 * Agricultural Sciences.
13 * Hans Liss <hans.liss@its.uu.se> Uppsala Universitet
15 * This work is based on the LPC-trie which is originally described in:
17 * An experimental study of compression methods for dynamic tries
18 * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
19 * http://www.csc.kth.se/~snilsson/software/dyntrie2/
22 * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
23 * IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999
26 * Code from fib_hash has been reused which includes the following header:
29 * INET An implementation of the TCP/IP protocol suite for the LINUX
30 * operating system. INET is implemented using the BSD Socket
31 * interface as the means of communication with the user level.
33 * IPv4 FIB: lookup engine and maintenance routines.
36 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
38 * This program is free software; you can redistribute it and/or
39 * modify it under the terms of the GNU General Public License
40 * as published by the Free Software Foundation; either version
41 * 2 of the License, or (at your option) any later version.
43 * Substantial contributions to this work comes from:
45 * David S. Miller, <davem@davemloft.net>
46 * Stephen Hemminger <shemminger@osdl.org>
47 * Paul E. McKenney <paulmck@us.ibm.com>
48 * Patrick McHardy <kaber@trash.net>
51 #define VERSION "0.409"
53 #include <asm/uaccess.h>
54 #include <linux/bitops.h>
55 #include <linux/types.h>
56 #include <linux/kernel.h>
58 #include <linux/string.h>
59 #include <linux/socket.h>
60 #include <linux/sockios.h>
61 #include <linux/errno.h>
63 #include <linux/inet.h>
64 #include <linux/inetdevice.h>
65 #include <linux/netdevice.h>
66 #include <linux/if_arp.h>
67 #include <linux/proc_fs.h>
68 #include <linux/rcupdate.h>
69 #include <linux/skbuff.h>
70 #include <linux/netlink.h>
71 #include <linux/init.h>
72 #include <linux/list.h>
73 #include <linux/slab.h>
74 #include <linux/prefetch.h>
75 #include <linux/export.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;
114 u32 mask_plen; /* ntohl(inet_make_mask(plen)) */
115 struct list_head falh;
120 unsigned long parent;
122 unsigned char pos; /* 2log(KEYLENGTH) bits needed */
123 unsigned char bits; /* 2log(KEYLENGTH) bits needed */
124 unsigned int full_children; /* KEYLENGTH bits needed */
125 unsigned int empty_children; /* KEYLENGTH bits needed */
128 struct work_struct work;
129 struct tnode *tnode_free;
131 struct rt_trie_node __rcu *child[0];
134 #ifdef CONFIG_IP_FIB_TRIE_STATS
135 struct trie_use_stats {
137 unsigned int backtrack;
138 unsigned int semantic_match_passed;
139 unsigned int semantic_match_miss;
140 unsigned int null_node_hit;
141 unsigned int resize_node_skipped;
146 unsigned int totdepth;
147 unsigned int maxdepth;
150 unsigned int nullpointers;
151 unsigned int prefixes;
152 unsigned int nodesizes[MAX_STAT_DEPTH];
156 struct rt_trie_node __rcu *trie;
157 #ifdef CONFIG_IP_FIB_TRIE_STATS
158 struct trie_use_stats stats;
162 static void put_child(struct trie *t, struct tnode *tn, int i, struct rt_trie_node *n);
163 static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
165 static struct rt_trie_node *resize(struct trie *t, struct tnode *tn);
166 static struct tnode *inflate(struct trie *t, struct tnode *tn);
167 static struct tnode *halve(struct trie *t, struct tnode *tn);
168 /* tnodes to free after resize(); protected by RTNL */
169 static struct tnode *tnode_free_head;
170 static size_t tnode_free_size;
173 * synchronize_rcu after call_rcu for that many pages; it should be especially
174 * useful before resizing the root node with PREEMPT_NONE configs; the value was
175 * obtained experimentally, aiming to avoid visible slowdown.
177 static const int sync_pages = 128;
179 static struct kmem_cache *fn_alias_kmem __read_mostly;
180 static struct kmem_cache *trie_leaf_kmem __read_mostly;
183 * caller must hold RTNL
185 static inline struct tnode *node_parent(const struct rt_trie_node *node)
187 unsigned long parent;
189 parent = rcu_dereference_index_check(node->parent, lockdep_rtnl_is_held());
191 return (struct tnode *)(parent & ~NODE_TYPE_MASK);
195 * caller must hold RCU read lock or RTNL
197 static inline struct tnode *node_parent_rcu(const struct rt_trie_node *node)
199 unsigned long parent;
201 parent = rcu_dereference_index_check(node->parent, rcu_read_lock_held() ||
202 lockdep_rtnl_is_held());
204 return (struct tnode *)(parent & ~NODE_TYPE_MASK);
207 /* Same as rcu_assign_pointer
208 * but that macro() assumes that value is a pointer.
210 static inline void node_set_parent(struct rt_trie_node *node, struct tnode *ptr)
213 node->parent = (unsigned long)ptr | NODE_TYPE(node);
217 * caller must hold RTNL
219 static inline struct rt_trie_node *tnode_get_child(const struct tnode *tn, unsigned int i)
221 BUG_ON(i >= 1U << tn->bits);
223 return rtnl_dereference(tn->child[i]);
227 * caller must hold RCU read lock or RTNL
229 static inline struct rt_trie_node *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
231 BUG_ON(i >= 1U << tn->bits);
233 return rcu_dereference_rtnl(tn->child[i]);
236 static inline int tnode_child_length(const struct tnode *tn)
238 return 1 << tn->bits;
241 static inline t_key mask_pfx(t_key k, unsigned int l)
243 return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
246 static inline t_key tkey_extract_bits(t_key a, unsigned int offset, unsigned int bits)
248 if (offset < KEYLENGTH)
249 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
254 static inline int tkey_equals(t_key a, t_key b)
259 static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
261 if (bits == 0 || offset >= KEYLENGTH)
263 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
264 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
267 static inline int tkey_mismatch(t_key a, int offset, t_key b)
274 while ((diff << i) >> (KEYLENGTH-1) == 0)
280 To understand this stuff, an understanding of keys and all their bits is
281 necessary. Every node in the trie has a key associated with it, but not
282 all of the bits in that key are significant.
284 Consider a node 'n' and its parent 'tp'.
286 If n is a leaf, every bit in its key is significant. Its presence is
287 necessitated by path compression, since during a tree traversal (when
288 searching for a leaf - unless we are doing an insertion) we will completely
289 ignore all skipped bits we encounter. Thus we need to verify, at the end of
290 a potentially successful search, that we have indeed been walking the
293 Note that we can never "miss" the correct key in the tree if present by
294 following the wrong path. Path compression ensures that segments of the key
295 that are the same for all keys with a given prefix are skipped, but the
296 skipped part *is* identical for each node in the subtrie below the skipped
297 bit! trie_insert() in this implementation takes care of that - note the
298 call to tkey_sub_equals() in trie_insert().
300 if n is an internal node - a 'tnode' here, the various parts of its key
301 have many different meanings.
304 _________________________________________________________________
305 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
306 -----------------------------------------------------------------
307 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
309 _________________________________________________________________
310 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
311 -----------------------------------------------------------------
312 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
319 First, let's just ignore the bits that come before the parent tp, that is
320 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
321 not use them for anything.
323 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
324 index into the parent's child array. That is, they will be used to find
325 'n' among tp's children.
327 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
330 All the bits we have seen so far are significant to the node n. The rest
331 of the bits are really not needed or indeed known in n->key.
333 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
334 n's child array, and will of course be different for each child.
337 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
342 static inline void check_tnode(const struct tnode *tn)
344 WARN_ON(tn && tn->pos+tn->bits > 32);
347 static const int halve_threshold = 25;
348 static const int inflate_threshold = 50;
349 static const int halve_threshold_root = 15;
350 static const int inflate_threshold_root = 30;
352 static void __alias_free_mem(struct rcu_head *head)
354 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
355 kmem_cache_free(fn_alias_kmem, fa);
358 static inline void alias_free_mem_rcu(struct fib_alias *fa)
360 call_rcu(&fa->rcu, __alias_free_mem);
363 static void __leaf_free_rcu(struct rcu_head *head)
365 struct leaf *l = container_of(head, struct leaf, rcu);
366 kmem_cache_free(trie_leaf_kmem, l);
369 static inline void free_leaf(struct leaf *l)
371 call_rcu_bh(&l->rcu, __leaf_free_rcu);
374 static inline void free_leaf_info(struct leaf_info *leaf)
376 kfree_rcu(leaf, rcu);
379 static struct tnode *tnode_alloc(size_t size)
381 if (size <= PAGE_SIZE)
382 return kzalloc(size, GFP_KERNEL);
384 return vzalloc(size);
387 static void __tnode_vfree(struct work_struct *arg)
389 struct tnode *tn = container_of(arg, struct tnode, work);
393 static void __tnode_free_rcu(struct rcu_head *head)
395 struct tnode *tn = container_of(head, struct tnode, rcu);
396 size_t size = sizeof(struct tnode) +
397 (sizeof(struct rt_trie_node *) << tn->bits);
399 if (size <= PAGE_SIZE)
402 INIT_WORK(&tn->work, __tnode_vfree);
403 schedule_work(&tn->work);
407 static inline void tnode_free(struct tnode *tn)
410 free_leaf((struct leaf *) tn);
412 call_rcu(&tn->rcu, __tnode_free_rcu);
415 static void tnode_free_safe(struct tnode *tn)
418 tn->tnode_free = tnode_free_head;
419 tnode_free_head = tn;
420 tnode_free_size += sizeof(struct tnode) +
421 (sizeof(struct rt_trie_node *) << tn->bits);
424 static void tnode_free_flush(void)
428 while ((tn = tnode_free_head)) {
429 tnode_free_head = tn->tnode_free;
430 tn->tnode_free = NULL;
434 if (tnode_free_size >= PAGE_SIZE * sync_pages) {
440 static struct leaf *leaf_new(void)
442 struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
445 INIT_HLIST_HEAD(&l->list);
450 static struct leaf_info *leaf_info_new(int plen)
452 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
455 li->mask_plen = ntohl(inet_make_mask(plen));
456 INIT_LIST_HEAD(&li->falh);
461 static struct tnode *tnode_new(t_key key, int pos, int bits)
463 size_t sz = sizeof(struct tnode) + (sizeof(struct rt_trie_node *) << bits);
464 struct tnode *tn = tnode_alloc(sz);
467 tn->parent = T_TNODE;
471 tn->full_children = 0;
472 tn->empty_children = 1<<bits;
475 pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode),
476 sizeof(struct rt_trie_node) << bits);
481 * Check whether a tnode 'n' is "full", i.e. it is an internal node
482 * and no bits are skipped. See discussion in dyntree paper p. 6
485 static inline int tnode_full(const struct tnode *tn, const struct rt_trie_node *n)
487 if (n == NULL || IS_LEAF(n))
490 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
493 static inline void put_child(struct trie *t, struct tnode *tn, int i,
494 struct rt_trie_node *n)
496 tnode_put_child_reorg(tn, i, n, -1);
500 * Add a child at position i overwriting the old value.
501 * Update the value of full_children and empty_children.
504 static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
507 struct rt_trie_node *chi = rtnl_dereference(tn->child[i]);
510 BUG_ON(i >= 1<<tn->bits);
512 /* update emptyChildren */
513 if (n == NULL && chi != NULL)
514 tn->empty_children++;
515 else if (n != NULL && chi == NULL)
516 tn->empty_children--;
518 /* update fullChildren */
520 wasfull = tnode_full(tn, chi);
522 isfull = tnode_full(tn, n);
523 if (wasfull && !isfull)
525 else if (!wasfull && isfull)
529 node_set_parent(n, tn);
531 rcu_assign_pointer(tn->child[i], n);
535 static struct rt_trie_node *resize(struct trie *t, struct tnode *tn)
538 struct tnode *old_tn;
539 int inflate_threshold_use;
540 int halve_threshold_use;
546 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
547 tn, inflate_threshold, halve_threshold);
550 if (tn->empty_children == tnode_child_length(tn)) {
555 if (tn->empty_children == tnode_child_length(tn) - 1)
558 * Double as long as the resulting node has a number of
559 * nonempty nodes that are above the threshold.
563 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
564 * the Helsinki University of Technology and Matti Tikkanen of Nokia
565 * Telecommunications, page 6:
566 * "A node is doubled if the ratio of non-empty children to all
567 * children in the *doubled* node is at least 'high'."
569 * 'high' in this instance is the variable 'inflate_threshold'. It
570 * is expressed as a percentage, so we multiply it with
571 * tnode_child_length() and instead of multiplying by 2 (since the
572 * child array will be doubled by inflate()) and multiplying
573 * the left-hand side by 100 (to handle the percentage thing) we
574 * multiply the left-hand side by 50.
576 * The left-hand side may look a bit weird: tnode_child_length(tn)
577 * - tn->empty_children is of course the number of non-null children
578 * in the current node. tn->full_children is the number of "full"
579 * children, that is non-null tnodes with a skip value of 0.
580 * All of those will be doubled in the resulting inflated tnode, so
581 * we just count them one extra time here.
583 * A clearer way to write this would be:
585 * to_be_doubled = tn->full_children;
586 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
589 * new_child_length = tnode_child_length(tn) * 2;
591 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
593 * if (new_fill_factor >= inflate_threshold)
595 * ...and so on, tho it would mess up the while () loop.
598 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
602 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
603 * inflate_threshold * new_child_length
605 * expand not_to_be_doubled and to_be_doubled, and shorten:
606 * 100 * (tnode_child_length(tn) - tn->empty_children +
607 * tn->full_children) >= inflate_threshold * new_child_length
609 * expand new_child_length:
610 * 100 * (tnode_child_length(tn) - tn->empty_children +
611 * tn->full_children) >=
612 * inflate_threshold * tnode_child_length(tn) * 2
615 * 50 * (tn->full_children + tnode_child_length(tn) -
616 * tn->empty_children) >= inflate_threshold *
617 * tnode_child_length(tn)
623 /* Keep root node larger */
625 if (!node_parent((struct rt_trie_node *)tn)) {
626 inflate_threshold_use = inflate_threshold_root;
627 halve_threshold_use = halve_threshold_root;
629 inflate_threshold_use = inflate_threshold;
630 halve_threshold_use = halve_threshold;
634 while ((tn->full_children > 0 && max_work-- &&
635 50 * (tn->full_children + tnode_child_length(tn)
636 - tn->empty_children)
637 >= inflate_threshold_use * tnode_child_length(tn))) {
644 #ifdef CONFIG_IP_FIB_TRIE_STATS
645 t->stats.resize_node_skipped++;
653 /* Return if at least one inflate is run */
654 if (max_work != MAX_WORK)
655 return (struct rt_trie_node *) tn;
658 * Halve as long as the number of empty children in this
659 * node is above threshold.
663 while (tn->bits > 1 && max_work-- &&
664 100 * (tnode_child_length(tn) - tn->empty_children) <
665 halve_threshold_use * tnode_child_length(tn)) {
671 #ifdef CONFIG_IP_FIB_TRIE_STATS
672 t->stats.resize_node_skipped++;
679 /* Only one child remains */
680 if (tn->empty_children == tnode_child_length(tn) - 1) {
682 for (i = 0; i < tnode_child_length(tn); i++) {
683 struct rt_trie_node *n;
685 n = rtnl_dereference(tn->child[i]);
689 /* compress one level */
691 node_set_parent(n, NULL);
696 return (struct rt_trie_node *) tn;
700 static void tnode_clean_free(struct tnode *tn)
703 struct tnode *tofree;
705 for (i = 0; i < tnode_child_length(tn); i++) {
706 tofree = (struct tnode *)rtnl_dereference(tn->child[i]);
713 static struct tnode *inflate(struct trie *t, struct tnode *tn)
715 struct tnode *oldtnode = tn;
716 int olen = tnode_child_length(tn);
719 pr_debug("In inflate\n");
721 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
724 return ERR_PTR(-ENOMEM);
727 * Preallocate and store tnodes before the actual work so we
728 * don't get into an inconsistent state if memory allocation
729 * fails. In case of failure we return the oldnode and inflate
730 * of tnode is ignored.
733 for (i = 0; i < olen; i++) {
736 inode = (struct tnode *) tnode_get_child(oldtnode, i);
739 inode->pos == oldtnode->pos + oldtnode->bits &&
741 struct tnode *left, *right;
742 t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
744 left = tnode_new(inode->key&(~m), inode->pos + 1,
749 right = tnode_new(inode->key|m, inode->pos + 1,
757 put_child(t, tn, 2*i, (struct rt_trie_node *) left);
758 put_child(t, tn, 2*i+1, (struct rt_trie_node *) right);
762 for (i = 0; i < olen; i++) {
764 struct rt_trie_node *node = tnode_get_child(oldtnode, i);
765 struct tnode *left, *right;
772 /* A leaf or an internal node with skipped bits */
774 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
775 tn->pos + tn->bits - 1) {
776 if (tkey_extract_bits(node->key,
777 oldtnode->pos + oldtnode->bits,
779 put_child(t, tn, 2*i, node);
781 put_child(t, tn, 2*i+1, node);
785 /* An internal node with two children */
786 inode = (struct tnode *) node;
788 if (inode->bits == 1) {
789 put_child(t, tn, 2*i, rtnl_dereference(inode->child[0]));
790 put_child(t, tn, 2*i+1, rtnl_dereference(inode->child[1]));
792 tnode_free_safe(inode);
796 /* An internal node with more than two children */
798 /* We will replace this node 'inode' with two new
799 * ones, 'left' and 'right', each with half of the
800 * original children. The two new nodes will have
801 * a position one bit further down the key and this
802 * means that the "significant" part of their keys
803 * (see the discussion near the top of this file)
804 * will differ by one bit, which will be "0" in
805 * left's key and "1" in right's key. Since we are
806 * moving the key position by one step, the bit that
807 * we are moving away from - the bit at position
808 * (inode->pos) - is the one that will differ between
809 * left and right. So... we synthesize that bit in the
811 * The mask 'm' below will be a single "one" bit at
812 * the position (inode->pos)
815 /* Use the old key, but set the new significant
819 left = (struct tnode *) tnode_get_child(tn, 2*i);
820 put_child(t, tn, 2*i, NULL);
824 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
825 put_child(t, tn, 2*i+1, NULL);
829 size = tnode_child_length(left);
830 for (j = 0; j < size; j++) {
831 put_child(t, left, j, rtnl_dereference(inode->child[j]));
832 put_child(t, right, j, rtnl_dereference(inode->child[j + size]));
834 put_child(t, tn, 2*i, resize(t, left));
835 put_child(t, tn, 2*i+1, resize(t, right));
837 tnode_free_safe(inode);
839 tnode_free_safe(oldtnode);
842 tnode_clean_free(tn);
843 return ERR_PTR(-ENOMEM);
846 static struct tnode *halve(struct trie *t, struct tnode *tn)
848 struct tnode *oldtnode = tn;
849 struct rt_trie_node *left, *right;
851 int olen = tnode_child_length(tn);
853 pr_debug("In halve\n");
855 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
858 return ERR_PTR(-ENOMEM);
861 * Preallocate and store tnodes before the actual work so we
862 * don't get into an inconsistent state if memory allocation
863 * fails. In case of failure we return the oldnode and halve
864 * of tnode is ignored.
867 for (i = 0; i < olen; i += 2) {
868 left = tnode_get_child(oldtnode, i);
869 right = tnode_get_child(oldtnode, i+1);
871 /* Two nonempty children */
875 newn = tnode_new(left->key, tn->pos + tn->bits, 1);
880 put_child(t, tn, i/2, (struct rt_trie_node *)newn);
885 for (i = 0; i < olen; i += 2) {
886 struct tnode *newBinNode;
888 left = tnode_get_child(oldtnode, i);
889 right = tnode_get_child(oldtnode, i+1);
891 /* At least one of the children is empty */
893 if (right == NULL) /* Both are empty */
895 put_child(t, tn, i/2, right);
900 put_child(t, tn, i/2, left);
904 /* Two nonempty children */
905 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
906 put_child(t, tn, i/2, NULL);
907 put_child(t, newBinNode, 0, left);
908 put_child(t, newBinNode, 1, right);
909 put_child(t, tn, i/2, resize(t, newBinNode));
911 tnode_free_safe(oldtnode);
914 tnode_clean_free(tn);
915 return ERR_PTR(-ENOMEM);
918 /* readside must use rcu_read_lock currently dump routines
919 via get_fa_head and dump */
921 static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
923 struct hlist_head *head = &l->list;
924 struct hlist_node *node;
925 struct leaf_info *li;
927 hlist_for_each_entry_rcu(li, node, head, hlist)
928 if (li->plen == plen)
934 static inline struct list_head *get_fa_head(struct leaf *l, int plen)
936 struct leaf_info *li = find_leaf_info(l, plen);
944 static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
946 struct leaf_info *li = NULL, *last = NULL;
947 struct hlist_node *node;
949 if (hlist_empty(head)) {
950 hlist_add_head_rcu(&new->hlist, head);
952 hlist_for_each_entry(li, node, head, hlist) {
953 if (new->plen > li->plen)
959 hlist_add_after_rcu(&last->hlist, &new->hlist);
961 hlist_add_before_rcu(&new->hlist, &li->hlist);
965 /* rcu_read_lock needs to be hold by caller from readside */
968 fib_find_node(struct trie *t, u32 key)
972 struct rt_trie_node *n;
975 n = rcu_dereference_rtnl(t->trie);
977 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
978 tn = (struct tnode *) n;
982 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
983 pos = tn->pos + tn->bits;
984 n = tnode_get_child_rcu(tn,
985 tkey_extract_bits(key,
991 /* Case we have found a leaf. Compare prefixes */
993 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
994 return (struct leaf *)n;
999 static void trie_rebalance(struct trie *t, struct tnode *tn)
1007 while (tn != NULL && (tp = node_parent((struct rt_trie_node *)tn)) != NULL) {
1008 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1009 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
1010 tn = (struct tnode *) resize(t, (struct tnode *)tn);
1012 tnode_put_child_reorg((struct tnode *)tp, cindex,
1013 (struct rt_trie_node *)tn, wasfull);
1015 tp = node_parent((struct rt_trie_node *) tn);
1017 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1025 /* Handle last (top) tnode */
1027 tn = (struct tnode *)resize(t, (struct tnode *)tn);
1029 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1033 /* only used from updater-side */
1035 static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
1038 struct tnode *tp = NULL, *tn = NULL;
1039 struct rt_trie_node *n;
1042 struct list_head *fa_head = NULL;
1043 struct leaf_info *li;
1047 n = rtnl_dereference(t->trie);
1049 /* If we point to NULL, stop. Either the tree is empty and we should
1050 * just put a new leaf in if, or we have reached an empty child slot,
1051 * and we should just put our new leaf in that.
1052 * If we point to a T_TNODE, check if it matches our key. Note that
1053 * a T_TNODE might be skipping any number of bits - its 'pos' need
1054 * not be the parent's 'pos'+'bits'!
1056 * If it does match the current key, get pos/bits from it, extract
1057 * the index from our key, push the T_TNODE and walk the tree.
1059 * If it doesn't, we have to replace it with a new T_TNODE.
1061 * If we point to a T_LEAF, it might or might not have the same key
1062 * as we do. If it does, just change the value, update the T_LEAF's
1063 * value, and return it.
1064 * If it doesn't, we need to replace it with a T_TNODE.
1067 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1068 tn = (struct tnode *) n;
1072 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1074 pos = tn->pos + tn->bits;
1075 n = tnode_get_child(tn,
1076 tkey_extract_bits(key,
1080 BUG_ON(n && node_parent(n) != tn);
1086 * n ----> NULL, LEAF or TNODE
1088 * tp is n's (parent) ----> NULL or TNODE
1091 BUG_ON(tp && IS_LEAF(tp));
1093 /* Case 1: n is a leaf. Compare prefixes */
1095 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1096 l = (struct leaf *) n;
1097 li = leaf_info_new(plen);
1102 fa_head = &li->falh;
1103 insert_leaf_info(&l->list, li);
1112 li = leaf_info_new(plen);
1119 fa_head = &li->falh;
1120 insert_leaf_info(&l->list, li);
1122 if (t->trie && n == NULL) {
1123 /* Case 2: n is NULL, and will just insert a new leaf */
1125 node_set_parent((struct rt_trie_node *)l, tp);
1127 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1128 put_child(t, (struct tnode *)tp, cindex, (struct rt_trie_node *)l);
1130 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1132 * Add a new tnode here
1133 * first tnode need some special handling
1137 pos = tp->pos+tp->bits;
1142 newpos = tkey_mismatch(key, pos, n->key);
1143 tn = tnode_new(n->key, newpos, 1);
1146 tn = tnode_new(key, newpos, 1); /* First tnode */
1155 node_set_parent((struct rt_trie_node *)tn, tp);
1157 missbit = tkey_extract_bits(key, newpos, 1);
1158 put_child(t, tn, missbit, (struct rt_trie_node *)l);
1159 put_child(t, tn, 1-missbit, n);
1162 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1163 put_child(t, (struct tnode *)tp, cindex,
1164 (struct rt_trie_node *)tn);
1166 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1171 if (tp && tp->pos + tp->bits > 32)
1172 pr_warn("fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1173 tp, tp->pos, tp->bits, key, plen);
1175 /* Rebalance the trie */
1177 trie_rebalance(t, tp);
1183 * Caller must hold RTNL.
1185 int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
1187 struct trie *t = (struct trie *) tb->tb_data;
1188 struct fib_alias *fa, *new_fa;
1189 struct list_head *fa_head = NULL;
1190 struct fib_info *fi;
1191 int plen = cfg->fc_dst_len;
1192 u8 tos = cfg->fc_tos;
1200 key = ntohl(cfg->fc_dst);
1202 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1204 mask = ntohl(inet_make_mask(plen));
1211 fi = fib_create_info(cfg);
1217 l = fib_find_node(t, key);
1221 fa_head = get_fa_head(l, plen);
1222 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1225 /* Now fa, if non-NULL, points to the first fib alias
1226 * with the same keys [prefix,tos,priority], if such key already
1227 * exists or to the node before which we will insert new one.
1229 * If fa is NULL, we will need to allocate a new one and
1230 * insert to the head of f.
1232 * If f is NULL, no fib node matched the destination key
1233 * and we need to allocate a new one of those as well.
1236 if (fa && fa->fa_tos == tos &&
1237 fa->fa_info->fib_priority == fi->fib_priority) {
1238 struct fib_alias *fa_first, *fa_match;
1241 if (cfg->fc_nlflags & NLM_F_EXCL)
1245 * 1. Find exact match for type, scope, fib_info to avoid
1247 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1251 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1252 list_for_each_entry_continue(fa, fa_head, fa_list) {
1253 if (fa->fa_tos != tos)
1255 if (fa->fa_info->fib_priority != fi->fib_priority)
1257 if (fa->fa_type == cfg->fc_type &&
1258 fa->fa_info == fi) {
1264 if (cfg->fc_nlflags & NLM_F_REPLACE) {
1265 struct fib_info *fi_drop;
1275 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1279 fi_drop = fa->fa_info;
1280 new_fa->fa_tos = fa->fa_tos;
1281 new_fa->fa_info = fi;
1282 new_fa->fa_type = cfg->fc_type;
1283 state = fa->fa_state;
1284 new_fa->fa_state = state & ~FA_S_ACCESSED;
1286 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1287 alias_free_mem_rcu(fa);
1289 fib_release_info(fi_drop);
1290 if (state & FA_S_ACCESSED)
1291 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1292 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1293 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1297 /* Error if we find a perfect match which
1298 * uses the same scope, type, and nexthop
1304 if (!(cfg->fc_nlflags & NLM_F_APPEND))
1308 if (!(cfg->fc_nlflags & NLM_F_CREATE))
1312 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1316 new_fa->fa_info = fi;
1317 new_fa->fa_tos = tos;
1318 new_fa->fa_type = cfg->fc_type;
1319 new_fa->fa_state = 0;
1321 * Insert new entry to the list.
1325 fa_head = fib_insert_node(t, key, plen);
1326 if (unlikely(!fa_head)) {
1328 goto out_free_new_fa;
1333 tb->tb_num_default++;
1335 list_add_tail_rcu(&new_fa->fa_list,
1336 (fa ? &fa->fa_list : fa_head));
1338 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1339 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1340 &cfg->fc_nlinfo, 0);
1345 kmem_cache_free(fn_alias_kmem, new_fa);
1347 fib_release_info(fi);
1352 /* should be called with rcu_read_lock */
1353 static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
1354 t_key key, const struct flowi4 *flp,
1355 struct fib_result *res, int fib_flags)
1357 struct leaf_info *li;
1358 struct hlist_head *hhead = &l->list;
1359 struct hlist_node *node;
1361 hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1362 struct fib_alias *fa;
1364 if (l->key != (key & li->mask_plen))
1367 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
1368 struct fib_info *fi = fa->fa_info;
1371 if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1375 if (fa->fa_info->fib_scope < flp->flowi4_scope)
1377 fib_alias_accessed(fa);
1378 err = fib_props[fa->fa_type].error;
1380 #ifdef CONFIG_IP_FIB_TRIE_STATS
1381 t->stats.semantic_match_passed++;
1385 if (fi->fib_flags & RTNH_F_DEAD)
1387 for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
1388 const struct fib_nh *nh = &fi->fib_nh[nhsel];
1390 if (nh->nh_flags & RTNH_F_DEAD)
1392 if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
1395 #ifdef CONFIG_IP_FIB_TRIE_STATS
1396 t->stats.semantic_match_passed++;
1398 res->prefixlen = li->plen;
1399 res->nh_sel = nhsel;
1400 res->type = fa->fa_type;
1401 res->scope = fa->fa_info->fib_scope;
1404 res->fa_head = &li->falh;
1405 if (!(fib_flags & FIB_LOOKUP_NOREF))
1406 atomic_inc(&fi->fib_clntref);
1411 #ifdef CONFIG_IP_FIB_TRIE_STATS
1412 t->stats.semantic_match_miss++;
1419 int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
1420 struct fib_result *res, int fib_flags)
1422 struct trie *t = (struct trie *) tb->tb_data;
1424 struct rt_trie_node *n;
1426 unsigned int pos, bits;
1427 t_key key = ntohl(flp->daddr);
1428 unsigned int chopped_off;
1430 unsigned int current_prefix_length = KEYLENGTH;
1432 t_key pref_mismatch;
1436 n = rcu_dereference(t->trie);
1440 #ifdef CONFIG_IP_FIB_TRIE_STATS
1446 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1450 pn = (struct tnode *) n;
1458 cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1461 n = tnode_get_child_rcu(pn, cindex);
1464 #ifdef CONFIG_IP_FIB_TRIE_STATS
1465 t->stats.null_node_hit++;
1471 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1477 cn = (struct tnode *)n;
1480 * It's a tnode, and we can do some extra checks here if we
1481 * like, to avoid descending into a dead-end branch.
1482 * This tnode is in the parent's child array at index
1483 * key[p_pos..p_pos+p_bits] but potentially with some bits
1484 * chopped off, so in reality the index may be just a
1485 * subprefix, padded with zero at the end.
1486 * We can also take a look at any skipped bits in this
1487 * tnode - everything up to p_pos is supposed to be ok,
1488 * and the non-chopped bits of the index (se previous
1489 * paragraph) are also guaranteed ok, but the rest is
1490 * considered unknown.
1492 * The skipped bits are key[pos+bits..cn->pos].
1495 /* If current_prefix_length < pos+bits, we are already doing
1496 * actual prefix matching, which means everything from
1497 * pos+(bits-chopped_off) onward must be zero along some
1498 * branch of this subtree - otherwise there is *no* valid
1499 * prefix present. Here we can only check the skipped
1500 * bits. Remember, since we have already indexed into the
1501 * parent's child array, we know that the bits we chopped of
1505 /* NOTA BENE: Checking only skipped bits
1506 for the new node here */
1508 if (current_prefix_length < pos+bits) {
1509 if (tkey_extract_bits(cn->key, current_prefix_length,
1510 cn->pos - current_prefix_length)
1516 * If chopped_off=0, the index is fully validated and we
1517 * only need to look at the skipped bits for this, the new,
1518 * tnode. What we actually want to do is to find out if
1519 * these skipped bits match our key perfectly, or if we will
1520 * have to count on finding a matching prefix further down,
1521 * because if we do, we would like to have some way of
1522 * verifying the existence of such a prefix at this point.
1525 /* The only thing we can do at this point is to verify that
1526 * any such matching prefix can indeed be a prefix to our
1527 * key, and if the bits in the node we are inspecting that
1528 * do not match our key are not ZERO, this cannot be true.
1529 * Thus, find out where there is a mismatch (before cn->pos)
1530 * and verify that all the mismatching bits are zero in the
1535 * Note: We aren't very concerned about the piece of
1536 * the key that precede pn->pos+pn->bits, since these
1537 * have already been checked. The bits after cn->pos
1538 * aren't checked since these are by definition
1539 * "unknown" at this point. Thus, what we want to see
1540 * is if we are about to enter the "prefix matching"
1541 * state, and in that case verify that the skipped
1542 * bits that will prevail throughout this subtree are
1543 * zero, as they have to be if we are to find a
1547 pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
1550 * In short: If skipped bits in this node do not match
1551 * the search key, enter the "prefix matching"
1554 if (pref_mismatch) {
1555 int mp = KEYLENGTH - fls(pref_mismatch);
1557 if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
1560 if (current_prefix_length >= cn->pos)
1561 current_prefix_length = mp;
1564 pn = (struct tnode *)n; /* Descend */
1571 /* As zero don't change the child key (cindex) */
1572 while ((chopped_off <= pn->bits)
1573 && !(cindex & (1<<(chopped_off-1))))
1576 /* Decrease current_... with bits chopped off */
1577 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1578 current_prefix_length = pn->pos + pn->bits
1582 * Either we do the actual chop off according or if we have
1583 * chopped off all bits in this tnode walk up to our parent.
1586 if (chopped_off <= pn->bits) {
1587 cindex &= ~(1 << (chopped_off-1));
1589 struct tnode *parent = node_parent_rcu((struct rt_trie_node *) pn);
1593 /* Get Child's index */
1594 cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1598 #ifdef CONFIG_IP_FIB_TRIE_STATS
1599 t->stats.backtrack++;
1610 EXPORT_SYMBOL_GPL(fib_table_lookup);
1613 * Remove the leaf and return parent.
1615 static void trie_leaf_remove(struct trie *t, struct leaf *l)
1617 struct tnode *tp = node_parent((struct rt_trie_node *) l);
1619 pr_debug("entering trie_leaf_remove(%p)\n", l);
1622 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1623 put_child(t, (struct tnode *)tp, cindex, NULL);
1624 trie_rebalance(t, tp);
1626 RCU_INIT_POINTER(t->trie, NULL);
1632 * Caller must hold RTNL.
1634 int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
1636 struct trie *t = (struct trie *) tb->tb_data;
1638 int plen = cfg->fc_dst_len;
1639 u8 tos = cfg->fc_tos;
1640 struct fib_alias *fa, *fa_to_delete;
1641 struct list_head *fa_head;
1643 struct leaf_info *li;
1648 key = ntohl(cfg->fc_dst);
1649 mask = ntohl(inet_make_mask(plen));
1655 l = fib_find_node(t, key);
1660 fa_head = get_fa_head(l, plen);
1661 fa = fib_find_alias(fa_head, tos, 0);
1666 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1668 fa_to_delete = NULL;
1669 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1670 list_for_each_entry_continue(fa, fa_head, fa_list) {
1671 struct fib_info *fi = fa->fa_info;
1673 if (fa->fa_tos != tos)
1676 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1677 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1678 fa->fa_info->fib_scope == cfg->fc_scope) &&
1679 (!cfg->fc_prefsrc ||
1680 fi->fib_prefsrc == cfg->fc_prefsrc) &&
1681 (!cfg->fc_protocol ||
1682 fi->fib_protocol == cfg->fc_protocol) &&
1683 fib_nh_match(cfg, fi) == 0) {
1693 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1694 &cfg->fc_nlinfo, 0);
1696 l = fib_find_node(t, key);
1697 li = find_leaf_info(l, plen);
1699 list_del_rcu(&fa->fa_list);
1702 tb->tb_num_default--;
1704 if (list_empty(fa_head)) {
1705 hlist_del_rcu(&li->hlist);
1709 if (hlist_empty(&l->list))
1710 trie_leaf_remove(t, l);
1712 if (fa->fa_state & FA_S_ACCESSED)
1713 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1715 fib_release_info(fa->fa_info);
1716 alias_free_mem_rcu(fa);
1720 static int trie_flush_list(struct list_head *head)
1722 struct fib_alias *fa, *fa_node;
1725 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1726 struct fib_info *fi = fa->fa_info;
1728 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1729 list_del_rcu(&fa->fa_list);
1730 fib_release_info(fa->fa_info);
1731 alias_free_mem_rcu(fa);
1738 static int trie_flush_leaf(struct leaf *l)
1741 struct hlist_head *lih = &l->list;
1742 struct hlist_node *node, *tmp;
1743 struct leaf_info *li = NULL;
1745 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
1746 found += trie_flush_list(&li->falh);
1748 if (list_empty(&li->falh)) {
1749 hlist_del_rcu(&li->hlist);
1757 * Scan for the next right leaf starting at node p->child[idx]
1758 * Since we have back pointer, no recursion necessary.
1760 static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1766 idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1770 while (idx < 1u << p->bits) {
1771 c = tnode_get_child_rcu(p, idx++);
1776 prefetch(rcu_dereference_rtnl(p->child[idx]));
1777 return (struct leaf *) c;
1780 /* Rescan start scanning in new node */
1781 p = (struct tnode *) c;
1785 /* Node empty, walk back up to parent */
1786 c = (struct rt_trie_node *) p;
1787 } while ((p = node_parent_rcu(c)) != NULL);
1789 return NULL; /* Root of trie */
1792 static struct leaf *trie_firstleaf(struct trie *t)
1794 struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
1799 if (IS_LEAF(n)) /* trie is just a leaf */
1800 return (struct leaf *) n;
1802 return leaf_walk_rcu(n, NULL);
1805 static struct leaf *trie_nextleaf(struct leaf *l)
1807 struct rt_trie_node *c = (struct rt_trie_node *) l;
1808 struct tnode *p = node_parent_rcu(c);
1811 return NULL; /* trie with just one leaf */
1813 return leaf_walk_rcu(p, c);
1816 static struct leaf *trie_leafindex(struct trie *t, int index)
1818 struct leaf *l = trie_firstleaf(t);
1820 while (l && index-- > 0)
1821 l = trie_nextleaf(l);
1828 * Caller must hold RTNL.
1830 int fib_table_flush(struct fib_table *tb)
1832 struct trie *t = (struct trie *) tb->tb_data;
1833 struct leaf *l, *ll = NULL;
1836 for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1837 found += trie_flush_leaf(l);
1839 if (ll && hlist_empty(&ll->list))
1840 trie_leaf_remove(t, ll);
1844 if (ll && hlist_empty(&ll->list))
1845 trie_leaf_remove(t, ll);
1847 pr_debug("trie_flush found=%d\n", found);
1851 void fib_free_table(struct fib_table *tb)
1856 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1857 struct fib_table *tb,
1858 struct sk_buff *skb, struct netlink_callback *cb)
1861 struct fib_alias *fa;
1862 __be32 xkey = htonl(key);
1867 /* rcu_read_lock is hold by caller */
1869 list_for_each_entry_rcu(fa, fah, fa_list) {
1875 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1883 fa->fa_info, NLM_F_MULTI) < 0) {
1893 static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1894 struct sk_buff *skb, struct netlink_callback *cb)
1896 struct leaf_info *li;
1897 struct hlist_node *node;
1903 /* rcu_read_lock is hold by caller */
1904 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
1913 if (list_empty(&li->falh))
1916 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1927 int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
1928 struct netlink_callback *cb)
1931 struct trie *t = (struct trie *) tb->tb_data;
1932 t_key key = cb->args[2];
1933 int count = cb->args[3];
1936 /* Dump starting at last key.
1937 * Note: 0.0.0.0/0 (ie default) is first key.
1940 l = trie_firstleaf(t);
1942 /* Normally, continue from last key, but if that is missing
1943 * fallback to using slow rescan
1945 l = fib_find_node(t, key);
1947 l = trie_leafindex(t, count);
1951 cb->args[2] = l->key;
1952 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1953 cb->args[3] = count;
1959 l = trie_nextleaf(l);
1960 memset(&cb->args[4], 0,
1961 sizeof(cb->args) - 4*sizeof(cb->args[0]));
1963 cb->args[3] = count;
1969 void __init fib_trie_init(void)
1971 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1972 sizeof(struct fib_alias),
1973 0, SLAB_PANIC, NULL);
1975 trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1976 max(sizeof(struct leaf),
1977 sizeof(struct leaf_info)),
1978 0, SLAB_PANIC, NULL);
1982 struct fib_table *fib_trie_table(u32 id)
1984 struct fib_table *tb;
1987 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1993 tb->tb_default = -1;
1994 tb->tb_num_default = 0;
1996 t = (struct trie *) tb->tb_data;
1997 memset(t, 0, sizeof(*t));
2002 #ifdef CONFIG_PROC_FS
2003 /* Depth first Trie walk iterator */
2004 struct fib_trie_iter {
2005 struct seq_net_private p;
2006 struct fib_table *tb;
2007 struct tnode *tnode;
2012 static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
2014 struct tnode *tn = iter->tnode;
2015 unsigned int cindex = iter->index;
2018 /* A single entry routing table */
2022 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2023 iter->tnode, iter->index, iter->depth);
2025 while (cindex < (1<<tn->bits)) {
2026 struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
2031 iter->index = cindex + 1;
2033 /* push down one level */
2034 iter->tnode = (struct tnode *) n;
2044 /* Current node exhausted, pop back up */
2045 p = node_parent_rcu((struct rt_trie_node *)tn);
2047 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2057 static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
2060 struct rt_trie_node *n;
2065 n = rcu_dereference(t->trie);
2070 iter->tnode = (struct tnode *) n;
2082 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2084 struct rt_trie_node *n;
2085 struct fib_trie_iter iter;
2087 memset(s, 0, sizeof(*s));
2090 for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2092 struct leaf *l = (struct leaf *)n;
2093 struct leaf_info *li;
2094 struct hlist_node *tmp;
2097 s->totdepth += iter.depth;
2098 if (iter.depth > s->maxdepth)
2099 s->maxdepth = iter.depth;
2101 hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
2104 const struct tnode *tn = (const struct tnode *) n;
2108 if (tn->bits < MAX_STAT_DEPTH)
2109 s->nodesizes[tn->bits]++;
2111 for (i = 0; i < (1<<tn->bits); i++)
2120 * This outputs /proc/net/fib_triestats
2122 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2124 unsigned int i, max, pointers, bytes, avdepth;
2127 avdepth = stat->totdepth*100 / stat->leaves;
2131 seq_printf(seq, "\tAver depth: %u.%02d\n",
2132 avdepth / 100, avdepth % 100);
2133 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
2135 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
2136 bytes = sizeof(struct leaf) * stat->leaves;
2138 seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes);
2139 bytes += sizeof(struct leaf_info) * stat->prefixes;
2141 seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2142 bytes += sizeof(struct tnode) * stat->tnodes;
2144 max = MAX_STAT_DEPTH;
2145 while (max > 0 && stat->nodesizes[max-1] == 0)
2149 for (i = 1; i <= max; i++)
2150 if (stat->nodesizes[i] != 0) {
2151 seq_printf(seq, " %u: %u", i, stat->nodesizes[i]);
2152 pointers += (1<<i) * stat->nodesizes[i];
2154 seq_putc(seq, '\n');
2155 seq_printf(seq, "\tPointers: %u\n", pointers);
2157 bytes += sizeof(struct rt_trie_node *) * pointers;
2158 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2159 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
2162 #ifdef CONFIG_IP_FIB_TRIE_STATS
2163 static void trie_show_usage(struct seq_file *seq,
2164 const struct trie_use_stats *stats)
2166 seq_printf(seq, "\nCounters:\n---------\n");
2167 seq_printf(seq, "gets = %u\n", stats->gets);
2168 seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2169 seq_printf(seq, "semantic match passed = %u\n",
2170 stats->semantic_match_passed);
2171 seq_printf(seq, "semantic match miss = %u\n",
2172 stats->semantic_match_miss);
2173 seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2174 seq_printf(seq, "skipped node resize = %u\n\n",
2175 stats->resize_node_skipped);
2177 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2179 static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2181 if (tb->tb_id == RT_TABLE_LOCAL)
2182 seq_puts(seq, "Local:\n");
2183 else if (tb->tb_id == RT_TABLE_MAIN)
2184 seq_puts(seq, "Main:\n");
2186 seq_printf(seq, "Id %d:\n", tb->tb_id);
2190 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2192 struct net *net = (struct net *)seq->private;
2196 "Basic info: size of leaf:"
2197 " %Zd bytes, size of tnode: %Zd bytes.\n",
2198 sizeof(struct leaf), sizeof(struct tnode));
2200 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2201 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2202 struct hlist_node *node;
2203 struct fib_table *tb;
2205 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2206 struct trie *t = (struct trie *) tb->tb_data;
2207 struct trie_stat stat;
2212 fib_table_print(seq, tb);
2214 trie_collect_stats(t, &stat);
2215 trie_show_stats(seq, &stat);
2216 #ifdef CONFIG_IP_FIB_TRIE_STATS
2217 trie_show_usage(seq, &t->stats);
2225 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2227 return single_open_net(inode, file, fib_triestat_seq_show);
2230 static const struct file_operations fib_triestat_fops = {
2231 .owner = THIS_MODULE,
2232 .open = fib_triestat_seq_open,
2234 .llseek = seq_lseek,
2235 .release = single_release_net,
2238 static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2240 struct fib_trie_iter *iter = seq->private;
2241 struct net *net = seq_file_net(seq);
2245 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2246 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2247 struct hlist_node *node;
2248 struct fib_table *tb;
2250 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2251 struct rt_trie_node *n;
2253 for (n = fib_trie_get_first(iter,
2254 (struct trie *) tb->tb_data);
2255 n; n = fib_trie_get_next(iter))
2266 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2270 return fib_trie_get_idx(seq, *pos);
2273 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2275 struct fib_trie_iter *iter = seq->private;
2276 struct net *net = seq_file_net(seq);
2277 struct fib_table *tb = iter->tb;
2278 struct hlist_node *tb_node;
2280 struct rt_trie_node *n;
2283 /* next node in same table */
2284 n = fib_trie_get_next(iter);
2288 /* walk rest of this hash chain */
2289 h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2290 while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2291 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2292 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2297 /* new hash chain */
2298 while (++h < FIB_TABLE_HASHSZ) {
2299 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2300 hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) {
2301 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2313 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2319 static void seq_indent(struct seq_file *seq, int n)
2325 static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2328 case RT_SCOPE_UNIVERSE: return "universe";
2329 case RT_SCOPE_SITE: return "site";
2330 case RT_SCOPE_LINK: return "link";
2331 case RT_SCOPE_HOST: return "host";
2332 case RT_SCOPE_NOWHERE: return "nowhere";
2334 snprintf(buf, len, "scope=%d", s);
2339 static const char *const rtn_type_names[__RTN_MAX] = {
2340 [RTN_UNSPEC] = "UNSPEC",
2341 [RTN_UNICAST] = "UNICAST",
2342 [RTN_LOCAL] = "LOCAL",
2343 [RTN_BROADCAST] = "BROADCAST",
2344 [RTN_ANYCAST] = "ANYCAST",
2345 [RTN_MULTICAST] = "MULTICAST",
2346 [RTN_BLACKHOLE] = "BLACKHOLE",
2347 [RTN_UNREACHABLE] = "UNREACHABLE",
2348 [RTN_PROHIBIT] = "PROHIBIT",
2349 [RTN_THROW] = "THROW",
2351 [RTN_XRESOLVE] = "XRESOLVE",
2354 static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2356 if (t < __RTN_MAX && rtn_type_names[t])
2357 return rtn_type_names[t];
2358 snprintf(buf, len, "type %u", t);
2362 /* Pretty print the trie */
2363 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2365 const struct fib_trie_iter *iter = seq->private;
2366 struct rt_trie_node *n = v;
2368 if (!node_parent_rcu(n))
2369 fib_table_print(seq, iter->tb);
2372 struct tnode *tn = (struct tnode *) n;
2373 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2375 seq_indent(seq, iter->depth-1);
2376 seq_printf(seq, " +-- %pI4/%d %d %d %d\n",
2377 &prf, tn->pos, tn->bits, tn->full_children,
2378 tn->empty_children);
2381 struct leaf *l = (struct leaf *) n;
2382 struct leaf_info *li;
2383 struct hlist_node *node;
2384 __be32 val = htonl(l->key);
2386 seq_indent(seq, iter->depth);
2387 seq_printf(seq, " |-- %pI4\n", &val);
2389 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2390 struct fib_alias *fa;
2392 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2393 char buf1[32], buf2[32];
2395 seq_indent(seq, iter->depth+1);
2396 seq_printf(seq, " /%d %s %s", li->plen,
2397 rtn_scope(buf1, sizeof(buf1),
2398 fa->fa_info->fib_scope),
2399 rtn_type(buf2, sizeof(buf2),
2402 seq_printf(seq, " tos=%d", fa->fa_tos);
2403 seq_putc(seq, '\n');
2411 static const struct seq_operations fib_trie_seq_ops = {
2412 .start = fib_trie_seq_start,
2413 .next = fib_trie_seq_next,
2414 .stop = fib_trie_seq_stop,
2415 .show = fib_trie_seq_show,
2418 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2420 return seq_open_net(inode, file, &fib_trie_seq_ops,
2421 sizeof(struct fib_trie_iter));
2424 static const struct file_operations fib_trie_fops = {
2425 .owner = THIS_MODULE,
2426 .open = fib_trie_seq_open,
2428 .llseek = seq_lseek,
2429 .release = seq_release_net,
2432 struct fib_route_iter {
2433 struct seq_net_private p;
2434 struct trie *main_trie;
2439 static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2441 struct leaf *l = NULL;
2442 struct trie *t = iter->main_trie;
2444 /* use cache location of last found key */
2445 if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2449 l = trie_firstleaf(t);
2452 while (l && pos-- > 0) {
2454 l = trie_nextleaf(l);
2458 iter->key = pos; /* remember it */
2460 iter->pos = 0; /* forget it */
2465 static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2468 struct fib_route_iter *iter = seq->private;
2469 struct fib_table *tb;
2472 tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2476 iter->main_trie = (struct trie *) tb->tb_data;
2478 return SEQ_START_TOKEN;
2480 return fib_route_get_idx(iter, *pos - 1);
2483 static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2485 struct fib_route_iter *iter = seq->private;
2489 if (v == SEQ_START_TOKEN) {
2491 l = trie_firstleaf(iter->main_trie);
2494 l = trie_nextleaf(l);
2504 static void fib_route_seq_stop(struct seq_file *seq, void *v)
2510 static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2512 unsigned int flags = 0;
2514 if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
2516 if (fi && fi->fib_nh->nh_gw)
2517 flags |= RTF_GATEWAY;
2518 if (mask == htonl(0xFFFFFFFF))
2525 * This outputs /proc/net/route.
2526 * The format of the file is not supposed to be changed
2527 * and needs to be same as fib_hash output to avoid breaking
2530 static int fib_route_seq_show(struct seq_file *seq, void *v)
2533 struct leaf_info *li;
2534 struct hlist_node *node;
2536 if (v == SEQ_START_TOKEN) {
2537 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2538 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2543 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2544 struct fib_alias *fa;
2545 __be32 mask, prefix;
2547 mask = inet_make_mask(li->plen);
2548 prefix = htonl(l->key);
2550 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2551 const struct fib_info *fi = fa->fa_info;
2552 unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2555 if (fa->fa_type == RTN_BROADCAST
2556 || fa->fa_type == RTN_MULTICAST)
2561 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2562 "%d\t%08X\t%d\t%u\t%u%n",
2563 fi->fib_dev ? fi->fib_dev->name : "*",
2565 fi->fib_nh->nh_gw, flags, 0, 0,
2569 fi->fib_advmss + 40 : 0),
2571 fi->fib_rtt >> 3, &len);
2574 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2575 "%d\t%08X\t%d\t%u\t%u%n",
2576 prefix, 0, flags, 0, 0, 0,
2577 mask, 0, 0, 0, &len);
2579 seq_printf(seq, "%*s\n", 127 - len, "");
2586 static const struct seq_operations fib_route_seq_ops = {
2587 .start = fib_route_seq_start,
2588 .next = fib_route_seq_next,
2589 .stop = fib_route_seq_stop,
2590 .show = fib_route_seq_show,
2593 static int fib_route_seq_open(struct inode *inode, struct file *file)
2595 return seq_open_net(inode, file, &fib_route_seq_ops,
2596 sizeof(struct fib_route_iter));
2599 static const struct file_operations fib_route_fops = {
2600 .owner = THIS_MODULE,
2601 .open = fib_route_seq_open,
2603 .llseek = seq_lseek,
2604 .release = seq_release_net,
2607 int __net_init fib_proc_init(struct net *net)
2609 if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
2612 if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
2613 &fib_triestat_fops))
2616 if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
2622 proc_net_remove(net, "fib_triestat");
2624 proc_net_remove(net, "fib_trie");
2629 void __net_exit fib_proc_exit(struct net *net)
2631 proc_net_remove(net, "fib_trie");
2632 proc_net_remove(net, "fib_triestat");
2633 proc_net_remove(net, "route");
2636 #endif /* CONFIG_PROC_FS */