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, tn);
1012 tnode_put_child_reorg(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, 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, 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, tp, cindex, (struct rt_trie_node *)tn);
1165 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1170 if (tp && tp->pos + tp->bits > 32)
1171 pr_warn("fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1172 tp, tp->pos, tp->bits, key, plen);
1174 /* Rebalance the trie */
1176 trie_rebalance(t, tp);
1182 * Caller must hold RTNL.
1184 int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
1186 struct trie *t = (struct trie *) tb->tb_data;
1187 struct fib_alias *fa, *new_fa;
1188 struct list_head *fa_head = NULL;
1189 struct fib_info *fi;
1190 int plen = cfg->fc_dst_len;
1191 u8 tos = cfg->fc_tos;
1199 key = ntohl(cfg->fc_dst);
1201 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1203 mask = ntohl(inet_make_mask(plen));
1210 fi = fib_create_info(cfg);
1216 l = fib_find_node(t, key);
1220 fa_head = get_fa_head(l, plen);
1221 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1224 /* Now fa, if non-NULL, points to the first fib alias
1225 * with the same keys [prefix,tos,priority], if such key already
1226 * exists or to the node before which we will insert new one.
1228 * If fa is NULL, we will need to allocate a new one and
1229 * insert to the head of f.
1231 * If f is NULL, no fib node matched the destination key
1232 * and we need to allocate a new one of those as well.
1235 if (fa && fa->fa_tos == tos &&
1236 fa->fa_info->fib_priority == fi->fib_priority) {
1237 struct fib_alias *fa_first, *fa_match;
1240 if (cfg->fc_nlflags & NLM_F_EXCL)
1244 * 1. Find exact match for type, scope, fib_info to avoid
1246 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1250 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1251 list_for_each_entry_continue(fa, fa_head, fa_list) {
1252 if (fa->fa_tos != tos)
1254 if (fa->fa_info->fib_priority != fi->fib_priority)
1256 if (fa->fa_type == cfg->fc_type &&
1257 fa->fa_info == fi) {
1263 if (cfg->fc_nlflags & NLM_F_REPLACE) {
1264 struct fib_info *fi_drop;
1274 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1278 fi_drop = fa->fa_info;
1279 new_fa->fa_tos = fa->fa_tos;
1280 new_fa->fa_info = fi;
1281 new_fa->fa_type = cfg->fc_type;
1282 state = fa->fa_state;
1283 new_fa->fa_state = state & ~FA_S_ACCESSED;
1285 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1286 alias_free_mem_rcu(fa);
1288 fib_release_info(fi_drop);
1289 if (state & FA_S_ACCESSED)
1290 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1291 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1292 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1296 /* Error if we find a perfect match which
1297 * uses the same scope, type, and nexthop
1303 if (!(cfg->fc_nlflags & NLM_F_APPEND))
1307 if (!(cfg->fc_nlflags & NLM_F_CREATE))
1311 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1315 new_fa->fa_info = fi;
1316 new_fa->fa_tos = tos;
1317 new_fa->fa_type = cfg->fc_type;
1318 new_fa->fa_state = 0;
1320 * Insert new entry to the list.
1324 fa_head = fib_insert_node(t, key, plen);
1325 if (unlikely(!fa_head)) {
1327 goto out_free_new_fa;
1332 tb->tb_num_default++;
1334 list_add_tail_rcu(&new_fa->fa_list,
1335 (fa ? &fa->fa_list : fa_head));
1337 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1338 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1339 &cfg->fc_nlinfo, 0);
1344 kmem_cache_free(fn_alias_kmem, new_fa);
1346 fib_release_info(fi);
1351 /* should be called with rcu_read_lock */
1352 static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
1353 t_key key, const struct flowi4 *flp,
1354 struct fib_result *res, int fib_flags)
1356 struct leaf_info *li;
1357 struct hlist_head *hhead = &l->list;
1358 struct hlist_node *node;
1360 hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1361 struct fib_alias *fa;
1363 if (l->key != (key & li->mask_plen))
1366 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
1367 struct fib_info *fi = fa->fa_info;
1370 if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1374 if (fa->fa_info->fib_scope < flp->flowi4_scope)
1376 fib_alias_accessed(fa);
1377 err = fib_props[fa->fa_type].error;
1379 #ifdef CONFIG_IP_FIB_TRIE_STATS
1380 t->stats.semantic_match_passed++;
1384 if (fi->fib_flags & RTNH_F_DEAD)
1386 for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
1387 const struct fib_nh *nh = &fi->fib_nh[nhsel];
1389 if (nh->nh_flags & RTNH_F_DEAD)
1391 if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
1394 #ifdef CONFIG_IP_FIB_TRIE_STATS
1395 t->stats.semantic_match_passed++;
1397 res->prefixlen = li->plen;
1398 res->nh_sel = nhsel;
1399 res->type = fa->fa_type;
1400 res->scope = fa->fa_info->fib_scope;
1403 res->fa_head = &li->falh;
1404 if (!(fib_flags & FIB_LOOKUP_NOREF))
1405 atomic_inc(&fi->fib_clntref);
1410 #ifdef CONFIG_IP_FIB_TRIE_STATS
1411 t->stats.semantic_match_miss++;
1418 int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
1419 struct fib_result *res, int fib_flags)
1421 struct trie *t = (struct trie *) tb->tb_data;
1423 struct rt_trie_node *n;
1425 unsigned int pos, bits;
1426 t_key key = ntohl(flp->daddr);
1427 unsigned int chopped_off;
1429 unsigned int current_prefix_length = KEYLENGTH;
1431 t_key pref_mismatch;
1435 n = rcu_dereference(t->trie);
1439 #ifdef CONFIG_IP_FIB_TRIE_STATS
1445 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1449 pn = (struct tnode *) n;
1457 cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1460 n = tnode_get_child_rcu(pn, cindex);
1463 #ifdef CONFIG_IP_FIB_TRIE_STATS
1464 t->stats.null_node_hit++;
1470 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1476 cn = (struct tnode *)n;
1479 * It's a tnode, and we can do some extra checks here if we
1480 * like, to avoid descending into a dead-end branch.
1481 * This tnode is in the parent's child array at index
1482 * key[p_pos..p_pos+p_bits] but potentially with some bits
1483 * chopped off, so in reality the index may be just a
1484 * subprefix, padded with zero at the end.
1485 * We can also take a look at any skipped bits in this
1486 * tnode - everything up to p_pos is supposed to be ok,
1487 * and the non-chopped bits of the index (se previous
1488 * paragraph) are also guaranteed ok, but the rest is
1489 * considered unknown.
1491 * The skipped bits are key[pos+bits..cn->pos].
1494 /* If current_prefix_length < pos+bits, we are already doing
1495 * actual prefix matching, which means everything from
1496 * pos+(bits-chopped_off) onward must be zero along some
1497 * branch of this subtree - otherwise there is *no* valid
1498 * prefix present. Here we can only check the skipped
1499 * bits. Remember, since we have already indexed into the
1500 * parent's child array, we know that the bits we chopped of
1504 /* NOTA BENE: Checking only skipped bits
1505 for the new node here */
1507 if (current_prefix_length < pos+bits) {
1508 if (tkey_extract_bits(cn->key, current_prefix_length,
1509 cn->pos - current_prefix_length)
1515 * If chopped_off=0, the index is fully validated and we
1516 * only need to look at the skipped bits for this, the new,
1517 * tnode. What we actually want to do is to find out if
1518 * these skipped bits match our key perfectly, or if we will
1519 * have to count on finding a matching prefix further down,
1520 * because if we do, we would like to have some way of
1521 * verifying the existence of such a prefix at this point.
1524 /* The only thing we can do at this point is to verify that
1525 * any such matching prefix can indeed be a prefix to our
1526 * key, and if the bits in the node we are inspecting that
1527 * do not match our key are not ZERO, this cannot be true.
1528 * Thus, find out where there is a mismatch (before cn->pos)
1529 * and verify that all the mismatching bits are zero in the
1534 * Note: We aren't very concerned about the piece of
1535 * the key that precede pn->pos+pn->bits, since these
1536 * have already been checked. The bits after cn->pos
1537 * aren't checked since these are by definition
1538 * "unknown" at this point. Thus, what we want to see
1539 * is if we are about to enter the "prefix matching"
1540 * state, and in that case verify that the skipped
1541 * bits that will prevail throughout this subtree are
1542 * zero, as they have to be if we are to find a
1546 pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
1549 * In short: If skipped bits in this node do not match
1550 * the search key, enter the "prefix matching"
1553 if (pref_mismatch) {
1554 int mp = KEYLENGTH - fls(pref_mismatch);
1556 if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
1559 if (current_prefix_length >= cn->pos)
1560 current_prefix_length = mp;
1563 pn = (struct tnode *)n; /* Descend */
1570 /* As zero don't change the child key (cindex) */
1571 while ((chopped_off <= pn->bits)
1572 && !(cindex & (1<<(chopped_off-1))))
1575 /* Decrease current_... with bits chopped off */
1576 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1577 current_prefix_length = pn->pos + pn->bits
1581 * Either we do the actual chop off according or if we have
1582 * chopped off all bits in this tnode walk up to our parent.
1585 if (chopped_off <= pn->bits) {
1586 cindex &= ~(1 << (chopped_off-1));
1588 struct tnode *parent = node_parent_rcu((struct rt_trie_node *) pn);
1592 /* Get Child's index */
1593 cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1597 #ifdef CONFIG_IP_FIB_TRIE_STATS
1598 t->stats.backtrack++;
1609 EXPORT_SYMBOL_GPL(fib_table_lookup);
1612 * Remove the leaf and return parent.
1614 static void trie_leaf_remove(struct trie *t, struct leaf *l)
1616 struct tnode *tp = node_parent((struct rt_trie_node *) l);
1618 pr_debug("entering trie_leaf_remove(%p)\n", l);
1621 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1622 put_child(t, tp, cindex, NULL);
1623 trie_rebalance(t, tp);
1625 RCU_INIT_POINTER(t->trie, NULL);
1631 * Caller must hold RTNL.
1633 int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
1635 struct trie *t = (struct trie *) tb->tb_data;
1637 int plen = cfg->fc_dst_len;
1638 u8 tos = cfg->fc_tos;
1639 struct fib_alias *fa, *fa_to_delete;
1640 struct list_head *fa_head;
1642 struct leaf_info *li;
1647 key = ntohl(cfg->fc_dst);
1648 mask = ntohl(inet_make_mask(plen));
1654 l = fib_find_node(t, key);
1659 fa_head = get_fa_head(l, plen);
1660 fa = fib_find_alias(fa_head, tos, 0);
1665 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1667 fa_to_delete = NULL;
1668 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1669 list_for_each_entry_continue(fa, fa_head, fa_list) {
1670 struct fib_info *fi = fa->fa_info;
1672 if (fa->fa_tos != tos)
1675 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1676 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1677 fa->fa_info->fib_scope == cfg->fc_scope) &&
1678 (!cfg->fc_prefsrc ||
1679 fi->fib_prefsrc == cfg->fc_prefsrc) &&
1680 (!cfg->fc_protocol ||
1681 fi->fib_protocol == cfg->fc_protocol) &&
1682 fib_nh_match(cfg, fi) == 0) {
1692 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1693 &cfg->fc_nlinfo, 0);
1695 l = fib_find_node(t, key);
1696 li = find_leaf_info(l, plen);
1698 list_del_rcu(&fa->fa_list);
1701 tb->tb_num_default--;
1703 if (list_empty(fa_head)) {
1704 hlist_del_rcu(&li->hlist);
1708 if (hlist_empty(&l->list))
1709 trie_leaf_remove(t, l);
1711 if (fa->fa_state & FA_S_ACCESSED)
1712 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1714 fib_release_info(fa->fa_info);
1715 alias_free_mem_rcu(fa);
1719 static int trie_flush_list(struct list_head *head)
1721 struct fib_alias *fa, *fa_node;
1724 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1725 struct fib_info *fi = fa->fa_info;
1727 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1728 list_del_rcu(&fa->fa_list);
1729 fib_release_info(fa->fa_info);
1730 alias_free_mem_rcu(fa);
1737 static int trie_flush_leaf(struct leaf *l)
1740 struct hlist_head *lih = &l->list;
1741 struct hlist_node *node, *tmp;
1742 struct leaf_info *li = NULL;
1744 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
1745 found += trie_flush_list(&li->falh);
1747 if (list_empty(&li->falh)) {
1748 hlist_del_rcu(&li->hlist);
1756 * Scan for the next right leaf starting at node p->child[idx]
1757 * Since we have back pointer, no recursion necessary.
1759 static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1765 idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1769 while (idx < 1u << p->bits) {
1770 c = tnode_get_child_rcu(p, idx++);
1775 prefetch(rcu_dereference_rtnl(p->child[idx]));
1776 return (struct leaf *) c;
1779 /* Rescan start scanning in new node */
1780 p = (struct tnode *) c;
1784 /* Node empty, walk back up to parent */
1785 c = (struct rt_trie_node *) p;
1786 } while ((p = node_parent_rcu(c)) != NULL);
1788 return NULL; /* Root of trie */
1791 static struct leaf *trie_firstleaf(struct trie *t)
1793 struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
1798 if (IS_LEAF(n)) /* trie is just a leaf */
1799 return (struct leaf *) n;
1801 return leaf_walk_rcu(n, NULL);
1804 static struct leaf *trie_nextleaf(struct leaf *l)
1806 struct rt_trie_node *c = (struct rt_trie_node *) l;
1807 struct tnode *p = node_parent_rcu(c);
1810 return NULL; /* trie with just one leaf */
1812 return leaf_walk_rcu(p, c);
1815 static struct leaf *trie_leafindex(struct trie *t, int index)
1817 struct leaf *l = trie_firstleaf(t);
1819 while (l && index-- > 0)
1820 l = trie_nextleaf(l);
1827 * Caller must hold RTNL.
1829 int fib_table_flush(struct fib_table *tb)
1831 struct trie *t = (struct trie *) tb->tb_data;
1832 struct leaf *l, *ll = NULL;
1835 for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1836 found += trie_flush_leaf(l);
1838 if (ll && hlist_empty(&ll->list))
1839 trie_leaf_remove(t, ll);
1843 if (ll && hlist_empty(&ll->list))
1844 trie_leaf_remove(t, ll);
1846 pr_debug("trie_flush found=%d\n", found);
1850 void fib_free_table(struct fib_table *tb)
1855 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1856 struct fib_table *tb,
1857 struct sk_buff *skb, struct netlink_callback *cb)
1860 struct fib_alias *fa;
1861 __be32 xkey = htonl(key);
1866 /* rcu_read_lock is hold by caller */
1868 list_for_each_entry_rcu(fa, fah, fa_list) {
1874 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1882 fa->fa_info, NLM_F_MULTI) < 0) {
1892 static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1893 struct sk_buff *skb, struct netlink_callback *cb)
1895 struct leaf_info *li;
1896 struct hlist_node *node;
1902 /* rcu_read_lock is hold by caller */
1903 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
1912 if (list_empty(&li->falh))
1915 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1926 int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
1927 struct netlink_callback *cb)
1930 struct trie *t = (struct trie *) tb->tb_data;
1931 t_key key = cb->args[2];
1932 int count = cb->args[3];
1935 /* Dump starting at last key.
1936 * Note: 0.0.0.0/0 (ie default) is first key.
1939 l = trie_firstleaf(t);
1941 /* Normally, continue from last key, but if that is missing
1942 * fallback to using slow rescan
1944 l = fib_find_node(t, key);
1946 l = trie_leafindex(t, count);
1950 cb->args[2] = l->key;
1951 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1952 cb->args[3] = count;
1958 l = trie_nextleaf(l);
1959 memset(&cb->args[4], 0,
1960 sizeof(cb->args) - 4*sizeof(cb->args[0]));
1962 cb->args[3] = count;
1968 void __init fib_trie_init(void)
1970 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1971 sizeof(struct fib_alias),
1972 0, SLAB_PANIC, NULL);
1974 trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1975 max(sizeof(struct leaf),
1976 sizeof(struct leaf_info)),
1977 0, SLAB_PANIC, NULL);
1981 struct fib_table *fib_trie_table(u32 id)
1983 struct fib_table *tb;
1986 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1992 tb->tb_default = -1;
1993 tb->tb_num_default = 0;
1995 t = (struct trie *) tb->tb_data;
1996 memset(t, 0, sizeof(*t));
2001 #ifdef CONFIG_PROC_FS
2002 /* Depth first Trie walk iterator */
2003 struct fib_trie_iter {
2004 struct seq_net_private p;
2005 struct fib_table *tb;
2006 struct tnode *tnode;
2011 static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
2013 struct tnode *tn = iter->tnode;
2014 unsigned int cindex = iter->index;
2017 /* A single entry routing table */
2021 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2022 iter->tnode, iter->index, iter->depth);
2024 while (cindex < (1<<tn->bits)) {
2025 struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
2030 iter->index = cindex + 1;
2032 /* push down one level */
2033 iter->tnode = (struct tnode *) n;
2043 /* Current node exhausted, pop back up */
2044 p = node_parent_rcu((struct rt_trie_node *)tn);
2046 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2056 static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
2059 struct rt_trie_node *n;
2064 n = rcu_dereference(t->trie);
2069 iter->tnode = (struct tnode *) n;
2081 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2083 struct rt_trie_node *n;
2084 struct fib_trie_iter iter;
2086 memset(s, 0, sizeof(*s));
2089 for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2091 struct leaf *l = (struct leaf *)n;
2092 struct leaf_info *li;
2093 struct hlist_node *tmp;
2096 s->totdepth += iter.depth;
2097 if (iter.depth > s->maxdepth)
2098 s->maxdepth = iter.depth;
2100 hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
2103 const struct tnode *tn = (const struct tnode *) n;
2107 if (tn->bits < MAX_STAT_DEPTH)
2108 s->nodesizes[tn->bits]++;
2110 for (i = 0; i < (1<<tn->bits); i++)
2119 * This outputs /proc/net/fib_triestats
2121 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2123 unsigned int i, max, pointers, bytes, avdepth;
2126 avdepth = stat->totdepth*100 / stat->leaves;
2130 seq_printf(seq, "\tAver depth: %u.%02d\n",
2131 avdepth / 100, avdepth % 100);
2132 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
2134 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
2135 bytes = sizeof(struct leaf) * stat->leaves;
2137 seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes);
2138 bytes += sizeof(struct leaf_info) * stat->prefixes;
2140 seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2141 bytes += sizeof(struct tnode) * stat->tnodes;
2143 max = MAX_STAT_DEPTH;
2144 while (max > 0 && stat->nodesizes[max-1] == 0)
2148 for (i = 1; i <= max; i++)
2149 if (stat->nodesizes[i] != 0) {
2150 seq_printf(seq, " %u: %u", i, stat->nodesizes[i]);
2151 pointers += (1<<i) * stat->nodesizes[i];
2153 seq_putc(seq, '\n');
2154 seq_printf(seq, "\tPointers: %u\n", pointers);
2156 bytes += sizeof(struct rt_trie_node *) * pointers;
2157 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2158 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
2161 #ifdef CONFIG_IP_FIB_TRIE_STATS
2162 static void trie_show_usage(struct seq_file *seq,
2163 const struct trie_use_stats *stats)
2165 seq_printf(seq, "\nCounters:\n---------\n");
2166 seq_printf(seq, "gets = %u\n", stats->gets);
2167 seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2168 seq_printf(seq, "semantic match passed = %u\n",
2169 stats->semantic_match_passed);
2170 seq_printf(seq, "semantic match miss = %u\n",
2171 stats->semantic_match_miss);
2172 seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2173 seq_printf(seq, "skipped node resize = %u\n\n",
2174 stats->resize_node_skipped);
2176 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2178 static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2180 if (tb->tb_id == RT_TABLE_LOCAL)
2181 seq_puts(seq, "Local:\n");
2182 else if (tb->tb_id == RT_TABLE_MAIN)
2183 seq_puts(seq, "Main:\n");
2185 seq_printf(seq, "Id %d:\n", tb->tb_id);
2189 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2191 struct net *net = (struct net *)seq->private;
2195 "Basic info: size of leaf:"
2196 " %Zd bytes, size of tnode: %Zd bytes.\n",
2197 sizeof(struct leaf), sizeof(struct tnode));
2199 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2200 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2201 struct hlist_node *node;
2202 struct fib_table *tb;
2204 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2205 struct trie *t = (struct trie *) tb->tb_data;
2206 struct trie_stat stat;
2211 fib_table_print(seq, tb);
2213 trie_collect_stats(t, &stat);
2214 trie_show_stats(seq, &stat);
2215 #ifdef CONFIG_IP_FIB_TRIE_STATS
2216 trie_show_usage(seq, &t->stats);
2224 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2226 return single_open_net(inode, file, fib_triestat_seq_show);
2229 static const struct file_operations fib_triestat_fops = {
2230 .owner = THIS_MODULE,
2231 .open = fib_triestat_seq_open,
2233 .llseek = seq_lseek,
2234 .release = single_release_net,
2237 static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2239 struct fib_trie_iter *iter = seq->private;
2240 struct net *net = seq_file_net(seq);
2244 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2245 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2246 struct hlist_node *node;
2247 struct fib_table *tb;
2249 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2250 struct rt_trie_node *n;
2252 for (n = fib_trie_get_first(iter,
2253 (struct trie *) tb->tb_data);
2254 n; n = fib_trie_get_next(iter))
2265 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2269 return fib_trie_get_idx(seq, *pos);
2272 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2274 struct fib_trie_iter *iter = seq->private;
2275 struct net *net = seq_file_net(seq);
2276 struct fib_table *tb = iter->tb;
2277 struct hlist_node *tb_node;
2279 struct rt_trie_node *n;
2282 /* next node in same table */
2283 n = fib_trie_get_next(iter);
2287 /* walk rest of this hash chain */
2288 h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2289 while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2290 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2291 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2296 /* new hash chain */
2297 while (++h < FIB_TABLE_HASHSZ) {
2298 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2299 hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) {
2300 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2312 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2318 static void seq_indent(struct seq_file *seq, int n)
2324 static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2327 case RT_SCOPE_UNIVERSE: return "universe";
2328 case RT_SCOPE_SITE: return "site";
2329 case RT_SCOPE_LINK: return "link";
2330 case RT_SCOPE_HOST: return "host";
2331 case RT_SCOPE_NOWHERE: return "nowhere";
2333 snprintf(buf, len, "scope=%d", s);
2338 static const char *const rtn_type_names[__RTN_MAX] = {
2339 [RTN_UNSPEC] = "UNSPEC",
2340 [RTN_UNICAST] = "UNICAST",
2341 [RTN_LOCAL] = "LOCAL",
2342 [RTN_BROADCAST] = "BROADCAST",
2343 [RTN_ANYCAST] = "ANYCAST",
2344 [RTN_MULTICAST] = "MULTICAST",
2345 [RTN_BLACKHOLE] = "BLACKHOLE",
2346 [RTN_UNREACHABLE] = "UNREACHABLE",
2347 [RTN_PROHIBIT] = "PROHIBIT",
2348 [RTN_THROW] = "THROW",
2350 [RTN_XRESOLVE] = "XRESOLVE",
2353 static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2355 if (t < __RTN_MAX && rtn_type_names[t])
2356 return rtn_type_names[t];
2357 snprintf(buf, len, "type %u", t);
2361 /* Pretty print the trie */
2362 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2364 const struct fib_trie_iter *iter = seq->private;
2365 struct rt_trie_node *n = v;
2367 if (!node_parent_rcu(n))
2368 fib_table_print(seq, iter->tb);
2371 struct tnode *tn = (struct tnode *) n;
2372 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2374 seq_indent(seq, iter->depth-1);
2375 seq_printf(seq, " +-- %pI4/%d %d %d %d\n",
2376 &prf, tn->pos, tn->bits, tn->full_children,
2377 tn->empty_children);
2380 struct leaf *l = (struct leaf *) n;
2381 struct leaf_info *li;
2382 struct hlist_node *node;
2383 __be32 val = htonl(l->key);
2385 seq_indent(seq, iter->depth);
2386 seq_printf(seq, " |-- %pI4\n", &val);
2388 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2389 struct fib_alias *fa;
2391 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2392 char buf1[32], buf2[32];
2394 seq_indent(seq, iter->depth+1);
2395 seq_printf(seq, " /%d %s %s", li->plen,
2396 rtn_scope(buf1, sizeof(buf1),
2397 fa->fa_info->fib_scope),
2398 rtn_type(buf2, sizeof(buf2),
2401 seq_printf(seq, " tos=%d", fa->fa_tos);
2402 seq_putc(seq, '\n');
2410 static const struct seq_operations fib_trie_seq_ops = {
2411 .start = fib_trie_seq_start,
2412 .next = fib_trie_seq_next,
2413 .stop = fib_trie_seq_stop,
2414 .show = fib_trie_seq_show,
2417 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2419 return seq_open_net(inode, file, &fib_trie_seq_ops,
2420 sizeof(struct fib_trie_iter));
2423 static const struct file_operations fib_trie_fops = {
2424 .owner = THIS_MODULE,
2425 .open = fib_trie_seq_open,
2427 .llseek = seq_lseek,
2428 .release = seq_release_net,
2431 struct fib_route_iter {
2432 struct seq_net_private p;
2433 struct trie *main_trie;
2438 static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2440 struct leaf *l = NULL;
2441 struct trie *t = iter->main_trie;
2443 /* use cache location of last found key */
2444 if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2448 l = trie_firstleaf(t);
2451 while (l && pos-- > 0) {
2453 l = trie_nextleaf(l);
2457 iter->key = pos; /* remember it */
2459 iter->pos = 0; /* forget it */
2464 static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2467 struct fib_route_iter *iter = seq->private;
2468 struct fib_table *tb;
2471 tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2475 iter->main_trie = (struct trie *) tb->tb_data;
2477 return SEQ_START_TOKEN;
2479 return fib_route_get_idx(iter, *pos - 1);
2482 static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2484 struct fib_route_iter *iter = seq->private;
2488 if (v == SEQ_START_TOKEN) {
2490 l = trie_firstleaf(iter->main_trie);
2493 l = trie_nextleaf(l);
2503 static void fib_route_seq_stop(struct seq_file *seq, void *v)
2509 static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2511 unsigned int flags = 0;
2513 if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
2515 if (fi && fi->fib_nh->nh_gw)
2516 flags |= RTF_GATEWAY;
2517 if (mask == htonl(0xFFFFFFFF))
2524 * This outputs /proc/net/route.
2525 * The format of the file is not supposed to be changed
2526 * and needs to be same as fib_hash output to avoid breaking
2529 static int fib_route_seq_show(struct seq_file *seq, void *v)
2532 struct leaf_info *li;
2533 struct hlist_node *node;
2535 if (v == SEQ_START_TOKEN) {
2536 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2537 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2542 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2543 struct fib_alias *fa;
2544 __be32 mask, prefix;
2546 mask = inet_make_mask(li->plen);
2547 prefix = htonl(l->key);
2549 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2550 const struct fib_info *fi = fa->fa_info;
2551 unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2554 if (fa->fa_type == RTN_BROADCAST
2555 || fa->fa_type == RTN_MULTICAST)
2560 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2561 "%d\t%08X\t%d\t%u\t%u%n",
2562 fi->fib_dev ? fi->fib_dev->name : "*",
2564 fi->fib_nh->nh_gw, flags, 0, 0,
2568 fi->fib_advmss + 40 : 0),
2570 fi->fib_rtt >> 3, &len);
2573 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2574 "%d\t%08X\t%d\t%u\t%u%n",
2575 prefix, 0, flags, 0, 0, 0,
2576 mask, 0, 0, 0, &len);
2578 seq_printf(seq, "%*s\n", 127 - len, "");
2585 static const struct seq_operations fib_route_seq_ops = {
2586 .start = fib_route_seq_start,
2587 .next = fib_route_seq_next,
2588 .stop = fib_route_seq_stop,
2589 .show = fib_route_seq_show,
2592 static int fib_route_seq_open(struct inode *inode, struct file *file)
2594 return seq_open_net(inode, file, &fib_route_seq_ops,
2595 sizeof(struct fib_route_iter));
2598 static const struct file_operations fib_route_fops = {
2599 .owner = THIS_MODULE,
2600 .open = fib_route_seq_open,
2602 .llseek = seq_lseek,
2603 .release = seq_release_net,
2606 int __net_init fib_proc_init(struct net *net)
2608 if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
2611 if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
2612 &fib_triestat_fops))
2615 if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
2621 proc_net_remove(net, "fib_triestat");
2623 proc_net_remove(net, "fib_trie");
2628 void __net_exit fib_proc_exit(struct net *net)
2630 proc_net_remove(net, "fib_trie");
2631 proc_net_remove(net, "fib_triestat");
2632 proc_net_remove(net, "route");
2635 #endif /* CONFIG_PROC_FS */