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 tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
164 static struct rt_trie_node *resize(struct trie *t, struct tnode *tn);
165 static struct tnode *inflate(struct trie *t, struct tnode *tn);
166 static struct tnode *halve(struct trie *t, struct tnode *tn);
167 /* tnodes to free after resize(); protected by RTNL */
168 static struct tnode *tnode_free_head;
169 static size_t tnode_free_size;
172 * synchronize_rcu after call_rcu for that many pages; it should be especially
173 * useful before resizing the root node with PREEMPT_NONE configs; the value was
174 * obtained experimentally, aiming to avoid visible slowdown.
176 static const int sync_pages = 128;
178 static struct kmem_cache *fn_alias_kmem __read_mostly;
179 static struct kmem_cache *trie_leaf_kmem __read_mostly;
182 * caller must hold RTNL
184 static inline struct tnode *node_parent(const struct rt_trie_node *node)
186 unsigned long parent;
188 parent = rcu_dereference_index_check(node->parent, lockdep_rtnl_is_held());
190 return (struct tnode *)(parent & ~NODE_TYPE_MASK);
194 * caller must hold RCU read lock or RTNL
196 static inline struct tnode *node_parent_rcu(const struct rt_trie_node *node)
198 unsigned long parent;
200 parent = rcu_dereference_index_check(node->parent, rcu_read_lock_held() ||
201 lockdep_rtnl_is_held());
203 return (struct tnode *)(parent & ~NODE_TYPE_MASK);
206 /* Same as rcu_assign_pointer
207 * but that macro() assumes that value is a pointer.
209 static inline void node_set_parent(struct rt_trie_node *node, struct tnode *ptr)
212 node->parent = (unsigned long)ptr | NODE_TYPE(node);
216 * caller must hold RTNL
218 static inline struct rt_trie_node *tnode_get_child(const struct tnode *tn, unsigned int i)
220 BUG_ON(i >= 1U << tn->bits);
222 return rtnl_dereference(tn->child[i]);
226 * caller must hold RCU read lock or RTNL
228 static inline struct rt_trie_node *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
230 BUG_ON(i >= 1U << tn->bits);
232 return rcu_dereference_rtnl(tn->child[i]);
235 static inline int tnode_child_length(const struct tnode *tn)
237 return 1 << tn->bits;
240 static inline t_key mask_pfx(t_key k, unsigned int l)
242 return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
245 static inline t_key tkey_extract_bits(t_key a, unsigned int offset, unsigned int bits)
247 if (offset < KEYLENGTH)
248 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
253 static inline int tkey_equals(t_key a, t_key b)
258 static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
260 if (bits == 0 || offset >= KEYLENGTH)
262 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
263 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
266 static inline int tkey_mismatch(t_key a, int offset, t_key b)
273 while ((diff << i) >> (KEYLENGTH-1) == 0)
279 To understand this stuff, an understanding of keys and all their bits is
280 necessary. Every node in the trie has a key associated with it, but not
281 all of the bits in that key are significant.
283 Consider a node 'n' and its parent 'tp'.
285 If n is a leaf, every bit in its key is significant. Its presence is
286 necessitated by path compression, since during a tree traversal (when
287 searching for a leaf - unless we are doing an insertion) we will completely
288 ignore all skipped bits we encounter. Thus we need to verify, at the end of
289 a potentially successful search, that we have indeed been walking the
292 Note that we can never "miss" the correct key in the tree if present by
293 following the wrong path. Path compression ensures that segments of the key
294 that are the same for all keys with a given prefix are skipped, but the
295 skipped part *is* identical for each node in the subtrie below the skipped
296 bit! trie_insert() in this implementation takes care of that - note the
297 call to tkey_sub_equals() in trie_insert().
299 if n is an internal node - a 'tnode' here, the various parts of its key
300 have many different meanings.
303 _________________________________________________________________
304 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
305 -----------------------------------------------------------------
306 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
308 _________________________________________________________________
309 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
310 -----------------------------------------------------------------
311 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
318 First, let's just ignore the bits that come before the parent tp, that is
319 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
320 not use them for anything.
322 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
323 index into the parent's child array. That is, they will be used to find
324 'n' among tp's children.
326 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
329 All the bits we have seen so far are significant to the node n. The rest
330 of the bits are really not needed or indeed known in n->key.
332 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
333 n's child array, and will of course be different for each child.
336 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
341 static inline void check_tnode(const struct tnode *tn)
343 WARN_ON(tn && tn->pos+tn->bits > 32);
346 static const int halve_threshold = 25;
347 static const int inflate_threshold = 50;
348 static const int halve_threshold_root = 15;
349 static const int inflate_threshold_root = 30;
351 static void __alias_free_mem(struct rcu_head *head)
353 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
354 kmem_cache_free(fn_alias_kmem, fa);
357 static inline void alias_free_mem_rcu(struct fib_alias *fa)
359 call_rcu(&fa->rcu, __alias_free_mem);
362 static void __leaf_free_rcu(struct rcu_head *head)
364 struct leaf *l = container_of(head, struct leaf, rcu);
365 kmem_cache_free(trie_leaf_kmem, l);
368 static inline void free_leaf(struct leaf *l)
370 call_rcu(&l->rcu, __leaf_free_rcu);
373 static inline void free_leaf_info(struct leaf_info *leaf)
375 kfree_rcu(leaf, rcu);
378 static struct tnode *tnode_alloc(size_t size)
380 if (size <= PAGE_SIZE)
381 return kzalloc(size, GFP_KERNEL);
383 return vzalloc(size);
386 static void __tnode_vfree(struct work_struct *arg)
388 struct tnode *tn = container_of(arg, struct tnode, work);
392 static void __tnode_free_rcu(struct rcu_head *head)
394 struct tnode *tn = container_of(head, struct tnode, rcu);
395 size_t size = sizeof(struct tnode) +
396 (sizeof(struct rt_trie_node *) << tn->bits);
398 if (size <= PAGE_SIZE)
401 INIT_WORK(&tn->work, __tnode_vfree);
402 schedule_work(&tn->work);
406 static inline void tnode_free(struct tnode *tn)
409 free_leaf((struct leaf *) tn);
411 call_rcu(&tn->rcu, __tnode_free_rcu);
414 static void tnode_free_safe(struct tnode *tn)
417 tn->tnode_free = tnode_free_head;
418 tnode_free_head = tn;
419 tnode_free_size += sizeof(struct tnode) +
420 (sizeof(struct rt_trie_node *) << tn->bits);
423 static void tnode_free_flush(void)
427 while ((tn = tnode_free_head)) {
428 tnode_free_head = tn->tnode_free;
429 tn->tnode_free = NULL;
433 if (tnode_free_size >= PAGE_SIZE * sync_pages) {
439 static struct leaf *leaf_new(void)
441 struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
444 INIT_HLIST_HEAD(&l->list);
449 static struct leaf_info *leaf_info_new(int plen)
451 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
454 li->mask_plen = ntohl(inet_make_mask(plen));
455 INIT_LIST_HEAD(&li->falh);
460 static struct tnode *tnode_new(t_key key, int pos, int bits)
462 size_t sz = sizeof(struct tnode) + (sizeof(struct rt_trie_node *) << bits);
463 struct tnode *tn = tnode_alloc(sz);
466 tn->parent = T_TNODE;
470 tn->full_children = 0;
471 tn->empty_children = 1<<bits;
474 pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode),
475 sizeof(struct rt_trie_node *) << bits);
480 * Check whether a tnode 'n' is "full", i.e. it is an internal node
481 * and no bits are skipped. See discussion in dyntree paper p. 6
484 static inline int tnode_full(const struct tnode *tn, const struct rt_trie_node *n)
486 if (n == NULL || IS_LEAF(n))
489 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
492 static inline void put_child(struct tnode *tn, int i,
493 struct rt_trie_node *n)
495 tnode_put_child_reorg(tn, i, n, -1);
499 * Add a child at position i overwriting the old value.
500 * Update the value of full_children and empty_children.
503 static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
506 struct rt_trie_node *chi = rtnl_dereference(tn->child[i]);
509 BUG_ON(i >= 1<<tn->bits);
511 /* update emptyChildren */
512 if (n == NULL && chi != NULL)
513 tn->empty_children++;
514 else if (n != NULL && chi == NULL)
515 tn->empty_children--;
517 /* update fullChildren */
519 wasfull = tnode_full(tn, chi);
521 isfull = tnode_full(tn, n);
522 if (wasfull && !isfull)
524 else if (!wasfull && isfull)
528 node_set_parent(n, tn);
530 rcu_assign_pointer(tn->child[i], n);
534 static struct rt_trie_node *resize(struct trie *t, struct tnode *tn)
537 struct tnode *old_tn;
538 int inflate_threshold_use;
539 int halve_threshold_use;
545 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
546 tn, inflate_threshold, halve_threshold);
549 if (tn->empty_children == tnode_child_length(tn)) {
554 if (tn->empty_children == tnode_child_length(tn) - 1)
557 * Double as long as the resulting node has a number of
558 * nonempty nodes that are above the threshold.
562 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
563 * the Helsinki University of Technology and Matti Tikkanen of Nokia
564 * Telecommunications, page 6:
565 * "A node is doubled if the ratio of non-empty children to all
566 * children in the *doubled* node is at least 'high'."
568 * 'high' in this instance is the variable 'inflate_threshold'. It
569 * is expressed as a percentage, so we multiply it with
570 * tnode_child_length() and instead of multiplying by 2 (since the
571 * child array will be doubled by inflate()) and multiplying
572 * the left-hand side by 100 (to handle the percentage thing) we
573 * multiply the left-hand side by 50.
575 * The left-hand side may look a bit weird: tnode_child_length(tn)
576 * - tn->empty_children is of course the number of non-null children
577 * in the current node. tn->full_children is the number of "full"
578 * children, that is non-null tnodes with a skip value of 0.
579 * All of those will be doubled in the resulting inflated tnode, so
580 * we just count them one extra time here.
582 * A clearer way to write this would be:
584 * to_be_doubled = tn->full_children;
585 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
588 * new_child_length = tnode_child_length(tn) * 2;
590 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
592 * if (new_fill_factor >= inflate_threshold)
594 * ...and so on, tho it would mess up the while () loop.
597 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
601 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
602 * inflate_threshold * new_child_length
604 * expand not_to_be_doubled and to_be_doubled, and shorten:
605 * 100 * (tnode_child_length(tn) - tn->empty_children +
606 * tn->full_children) >= inflate_threshold * new_child_length
608 * expand new_child_length:
609 * 100 * (tnode_child_length(tn) - tn->empty_children +
610 * tn->full_children) >=
611 * inflate_threshold * tnode_child_length(tn) * 2
614 * 50 * (tn->full_children + tnode_child_length(tn) -
615 * tn->empty_children) >= inflate_threshold *
616 * tnode_child_length(tn)
622 /* Keep root node larger */
624 if (!node_parent((struct rt_trie_node *)tn)) {
625 inflate_threshold_use = inflate_threshold_root;
626 halve_threshold_use = halve_threshold_root;
628 inflate_threshold_use = inflate_threshold;
629 halve_threshold_use = halve_threshold;
633 while ((tn->full_children > 0 && max_work-- &&
634 50 * (tn->full_children + tnode_child_length(tn)
635 - tn->empty_children)
636 >= inflate_threshold_use * tnode_child_length(tn))) {
643 #ifdef CONFIG_IP_FIB_TRIE_STATS
644 t->stats.resize_node_skipped++;
652 /* Return if at least one inflate is run */
653 if (max_work != MAX_WORK)
654 return (struct rt_trie_node *) tn;
657 * Halve as long as the number of empty children in this
658 * node is above threshold.
662 while (tn->bits > 1 && max_work-- &&
663 100 * (tnode_child_length(tn) - tn->empty_children) <
664 halve_threshold_use * tnode_child_length(tn)) {
670 #ifdef CONFIG_IP_FIB_TRIE_STATS
671 t->stats.resize_node_skipped++;
678 /* Only one child remains */
679 if (tn->empty_children == tnode_child_length(tn) - 1) {
681 for (i = 0; i < tnode_child_length(tn); i++) {
682 struct rt_trie_node *n;
684 n = rtnl_dereference(tn->child[i]);
688 /* compress one level */
690 node_set_parent(n, NULL);
695 return (struct rt_trie_node *) tn;
699 static void tnode_clean_free(struct tnode *tn)
702 struct tnode *tofree;
704 for (i = 0; i < tnode_child_length(tn); i++) {
705 tofree = (struct tnode *)rtnl_dereference(tn->child[i]);
712 static struct tnode *inflate(struct trie *t, struct tnode *tn)
714 struct tnode *oldtnode = tn;
715 int olen = tnode_child_length(tn);
718 pr_debug("In inflate\n");
720 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
723 return ERR_PTR(-ENOMEM);
726 * Preallocate and store tnodes before the actual work so we
727 * don't get into an inconsistent state if memory allocation
728 * fails. In case of failure we return the oldnode and inflate
729 * of tnode is ignored.
732 for (i = 0; i < olen; i++) {
735 inode = (struct tnode *) tnode_get_child(oldtnode, i);
738 inode->pos == oldtnode->pos + oldtnode->bits &&
740 struct tnode *left, *right;
741 t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
743 left = tnode_new(inode->key&(~m), inode->pos + 1,
748 right = tnode_new(inode->key|m, inode->pos + 1,
756 put_child(tn, 2*i, (struct rt_trie_node *) left);
757 put_child(tn, 2*i+1, (struct rt_trie_node *) right);
761 for (i = 0; i < olen; i++) {
763 struct rt_trie_node *node = tnode_get_child(oldtnode, i);
764 struct tnode *left, *right;
771 /* A leaf or an internal node with skipped bits */
773 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
774 tn->pos + tn->bits - 1) {
775 if (tkey_extract_bits(node->key,
776 oldtnode->pos + oldtnode->bits,
778 put_child(tn, 2*i, node);
780 put_child(tn, 2*i+1, node);
784 /* An internal node with two children */
785 inode = (struct tnode *) node;
787 if (inode->bits == 1) {
788 put_child(tn, 2*i, rtnl_dereference(inode->child[0]));
789 put_child(tn, 2*i+1, rtnl_dereference(inode->child[1]));
791 tnode_free_safe(inode);
795 /* An internal node with more than two children */
797 /* We will replace this node 'inode' with two new
798 * ones, 'left' and 'right', each with half of the
799 * original children. The two new nodes will have
800 * a position one bit further down the key and this
801 * means that the "significant" part of their keys
802 * (see the discussion near the top of this file)
803 * will differ by one bit, which will be "0" in
804 * left's key and "1" in right's key. Since we are
805 * moving the key position by one step, the bit that
806 * we are moving away from - the bit at position
807 * (inode->pos) - is the one that will differ between
808 * left and right. So... we synthesize that bit in the
810 * The mask 'm' below will be a single "one" bit at
811 * the position (inode->pos)
814 /* Use the old key, but set the new significant
818 left = (struct tnode *) tnode_get_child(tn, 2*i);
819 put_child(tn, 2*i, NULL);
823 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
824 put_child(tn, 2*i+1, NULL);
828 size = tnode_child_length(left);
829 for (j = 0; j < size; j++) {
830 put_child(left, j, rtnl_dereference(inode->child[j]));
831 put_child(right, j, rtnl_dereference(inode->child[j + size]));
833 put_child(tn, 2*i, resize(t, left));
834 put_child(tn, 2*i+1, resize(t, right));
836 tnode_free_safe(inode);
838 tnode_free_safe(oldtnode);
841 tnode_clean_free(tn);
842 return ERR_PTR(-ENOMEM);
845 static struct tnode *halve(struct trie *t, struct tnode *tn)
847 struct tnode *oldtnode = tn;
848 struct rt_trie_node *left, *right;
850 int olen = tnode_child_length(tn);
852 pr_debug("In halve\n");
854 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
857 return ERR_PTR(-ENOMEM);
860 * Preallocate and store tnodes before the actual work so we
861 * don't get into an inconsistent state if memory allocation
862 * fails. In case of failure we return the oldnode and halve
863 * of tnode is ignored.
866 for (i = 0; i < olen; i += 2) {
867 left = tnode_get_child(oldtnode, i);
868 right = tnode_get_child(oldtnode, i+1);
870 /* Two nonempty children */
874 newn = tnode_new(left->key, tn->pos + tn->bits, 1);
879 put_child(tn, i/2, (struct rt_trie_node *)newn);
884 for (i = 0; i < olen; i += 2) {
885 struct tnode *newBinNode;
887 left = tnode_get_child(oldtnode, i);
888 right = tnode_get_child(oldtnode, i+1);
890 /* At least one of the children is empty */
892 if (right == NULL) /* Both are empty */
894 put_child(tn, i/2, right);
899 put_child(tn, i/2, left);
903 /* Two nonempty children */
904 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
905 put_child(tn, i/2, NULL);
906 put_child(newBinNode, 0, left);
907 put_child(newBinNode, 1, right);
908 put_child(tn, i/2, resize(t, newBinNode));
910 tnode_free_safe(oldtnode);
913 tnode_clean_free(tn);
914 return ERR_PTR(-ENOMEM);
917 /* readside must use rcu_read_lock currently dump routines
918 via get_fa_head and dump */
920 static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
922 struct hlist_head *head = &l->list;
923 struct leaf_info *li;
925 hlist_for_each_entry_rcu(li, head, hlist)
926 if (li->plen == plen)
932 static inline struct list_head *get_fa_head(struct leaf *l, int plen)
934 struct leaf_info *li = find_leaf_info(l, plen);
942 static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
944 struct leaf_info *li = NULL, *last = NULL;
946 if (hlist_empty(head)) {
947 hlist_add_head_rcu(&new->hlist, head);
949 hlist_for_each_entry(li, head, hlist) {
950 if (new->plen > li->plen)
956 hlist_add_after_rcu(&last->hlist, &new->hlist);
958 hlist_add_before_rcu(&new->hlist, &li->hlist);
962 /* rcu_read_lock needs to be hold by caller from readside */
965 fib_find_node(struct trie *t, u32 key)
969 struct rt_trie_node *n;
972 n = rcu_dereference_rtnl(t->trie);
974 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
975 tn = (struct tnode *) n;
979 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
980 pos = tn->pos + tn->bits;
981 n = tnode_get_child_rcu(tn,
982 tkey_extract_bits(key,
988 /* Case we have found a leaf. Compare prefixes */
990 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
991 return (struct leaf *)n;
996 static void trie_rebalance(struct trie *t, struct tnode *tn)
1004 while (tn != NULL && (tp = node_parent((struct rt_trie_node *)tn)) != NULL) {
1005 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1006 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
1007 tn = (struct tnode *)resize(t, tn);
1009 tnode_put_child_reorg(tp, cindex,
1010 (struct rt_trie_node *)tn, wasfull);
1012 tp = node_parent((struct rt_trie_node *) tn);
1014 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1022 /* Handle last (top) tnode */
1024 tn = (struct tnode *)resize(t, tn);
1026 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1030 /* only used from updater-side */
1032 static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
1035 struct tnode *tp = NULL, *tn = NULL;
1036 struct rt_trie_node *n;
1039 struct list_head *fa_head = NULL;
1040 struct leaf_info *li;
1044 n = rtnl_dereference(t->trie);
1046 /* If we point to NULL, stop. Either the tree is empty and we should
1047 * just put a new leaf in if, or we have reached an empty child slot,
1048 * and we should just put our new leaf in that.
1049 * If we point to a T_TNODE, check if it matches our key. Note that
1050 * a T_TNODE might be skipping any number of bits - its 'pos' need
1051 * not be the parent's 'pos'+'bits'!
1053 * If it does match the current key, get pos/bits from it, extract
1054 * the index from our key, push the T_TNODE and walk the tree.
1056 * If it doesn't, we have to replace it with a new T_TNODE.
1058 * If we point to a T_LEAF, it might or might not have the same key
1059 * as we do. If it does, just change the value, update the T_LEAF's
1060 * value, and return it.
1061 * If it doesn't, we need to replace it with a T_TNODE.
1064 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1065 tn = (struct tnode *) n;
1069 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1071 pos = tn->pos + tn->bits;
1072 n = tnode_get_child(tn,
1073 tkey_extract_bits(key,
1077 BUG_ON(n && node_parent(n) != tn);
1083 * n ----> NULL, LEAF or TNODE
1085 * tp is n's (parent) ----> NULL or TNODE
1088 BUG_ON(tp && IS_LEAF(tp));
1090 /* Case 1: n is a leaf. Compare prefixes */
1092 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1093 l = (struct leaf *) n;
1094 li = leaf_info_new(plen);
1099 fa_head = &li->falh;
1100 insert_leaf_info(&l->list, li);
1109 li = leaf_info_new(plen);
1116 fa_head = &li->falh;
1117 insert_leaf_info(&l->list, li);
1119 if (t->trie && n == NULL) {
1120 /* Case 2: n is NULL, and will just insert a new leaf */
1122 node_set_parent((struct rt_trie_node *)l, tp);
1124 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1125 put_child(tp, cindex, (struct rt_trie_node *)l);
1127 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1129 * Add a new tnode here
1130 * first tnode need some special handling
1134 pos = tp->pos+tp->bits;
1139 newpos = tkey_mismatch(key, pos, n->key);
1140 tn = tnode_new(n->key, newpos, 1);
1143 tn = tnode_new(key, newpos, 1); /* First tnode */
1152 node_set_parent((struct rt_trie_node *)tn, tp);
1154 missbit = tkey_extract_bits(key, newpos, 1);
1155 put_child(tn, missbit, (struct rt_trie_node *)l);
1156 put_child(tn, 1-missbit, n);
1159 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1160 put_child(tp, cindex, (struct rt_trie_node *)tn);
1162 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1167 if (tp && tp->pos + tp->bits > 32)
1168 pr_warn("fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1169 tp, tp->pos, tp->bits, key, plen);
1171 /* Rebalance the trie */
1173 trie_rebalance(t, tp);
1179 * Caller must hold RTNL.
1181 int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
1183 struct trie *t = (struct trie *) tb->tb_data;
1184 struct fib_alias *fa, *new_fa;
1185 struct list_head *fa_head = NULL;
1186 struct fib_info *fi;
1187 int plen = cfg->fc_dst_len;
1188 u8 tos = cfg->fc_tos;
1196 key = ntohl(cfg->fc_dst);
1198 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1200 mask = ntohl(inet_make_mask(plen));
1207 fi = fib_create_info(cfg);
1213 l = fib_find_node(t, key);
1217 fa_head = get_fa_head(l, plen);
1218 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1221 /* Now fa, if non-NULL, points to the first fib alias
1222 * with the same keys [prefix,tos,priority], if such key already
1223 * exists or to the node before which we will insert new one.
1225 * If fa is NULL, we will need to allocate a new one and
1226 * insert to the head of f.
1228 * If f is NULL, no fib node matched the destination key
1229 * and we need to allocate a new one of those as well.
1232 if (fa && fa->fa_tos == tos &&
1233 fa->fa_info->fib_priority == fi->fib_priority) {
1234 struct fib_alias *fa_first, *fa_match;
1237 if (cfg->fc_nlflags & NLM_F_EXCL)
1241 * 1. Find exact match for type, scope, fib_info to avoid
1243 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1247 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1248 list_for_each_entry_continue(fa, fa_head, fa_list) {
1249 if (fa->fa_tos != tos)
1251 if (fa->fa_info->fib_priority != fi->fib_priority)
1253 if (fa->fa_type == cfg->fc_type &&
1254 fa->fa_info == fi) {
1260 if (cfg->fc_nlflags & NLM_F_REPLACE) {
1261 struct fib_info *fi_drop;
1271 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1275 fi_drop = fa->fa_info;
1276 new_fa->fa_tos = fa->fa_tos;
1277 new_fa->fa_info = fi;
1278 new_fa->fa_type = cfg->fc_type;
1279 state = fa->fa_state;
1280 new_fa->fa_state = state & ~FA_S_ACCESSED;
1282 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1283 alias_free_mem_rcu(fa);
1285 fib_release_info(fi_drop);
1286 if (state & FA_S_ACCESSED)
1287 rt_cache_flush(cfg->fc_nlinfo.nl_net);
1288 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1289 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1293 /* Error if we find a perfect match which
1294 * uses the same scope, type, and nexthop
1300 if (!(cfg->fc_nlflags & NLM_F_APPEND))
1304 if (!(cfg->fc_nlflags & NLM_F_CREATE))
1308 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1312 new_fa->fa_info = fi;
1313 new_fa->fa_tos = tos;
1314 new_fa->fa_type = cfg->fc_type;
1315 new_fa->fa_state = 0;
1317 * Insert new entry to the list.
1321 fa_head = fib_insert_node(t, key, plen);
1322 if (unlikely(!fa_head)) {
1324 goto out_free_new_fa;
1329 tb->tb_num_default++;
1331 list_add_tail_rcu(&new_fa->fa_list,
1332 (fa ? &fa->fa_list : fa_head));
1334 rt_cache_flush(cfg->fc_nlinfo.nl_net);
1335 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1336 &cfg->fc_nlinfo, 0);
1341 kmem_cache_free(fn_alias_kmem, new_fa);
1343 fib_release_info(fi);
1348 /* should be called with rcu_read_lock */
1349 static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
1350 t_key key, const struct flowi4 *flp,
1351 struct fib_result *res, int fib_flags)
1353 struct leaf_info *li;
1354 struct hlist_head *hhead = &l->list;
1356 hlist_for_each_entry_rcu(li, hhead, hlist) {
1357 struct fib_alias *fa;
1359 if (l->key != (key & li->mask_plen))
1362 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
1363 struct fib_info *fi = fa->fa_info;
1366 if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1370 if (fa->fa_info->fib_scope < flp->flowi4_scope)
1372 fib_alias_accessed(fa);
1373 err = fib_props[fa->fa_type].error;
1375 #ifdef CONFIG_IP_FIB_TRIE_STATS
1376 t->stats.semantic_match_passed++;
1380 if (fi->fib_flags & RTNH_F_DEAD)
1382 for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
1383 const struct fib_nh *nh = &fi->fib_nh[nhsel];
1385 if (nh->nh_flags & RTNH_F_DEAD)
1387 if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
1390 #ifdef CONFIG_IP_FIB_TRIE_STATS
1391 t->stats.semantic_match_passed++;
1393 res->prefixlen = li->plen;
1394 res->nh_sel = nhsel;
1395 res->type = fa->fa_type;
1396 res->scope = fa->fa_info->fib_scope;
1399 res->fa_head = &li->falh;
1400 if (!(fib_flags & FIB_LOOKUP_NOREF))
1401 atomic_inc(&fi->fib_clntref);
1406 #ifdef CONFIG_IP_FIB_TRIE_STATS
1407 t->stats.semantic_match_miss++;
1414 int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
1415 struct fib_result *res, int fib_flags)
1417 struct trie *t = (struct trie *) tb->tb_data;
1419 struct rt_trie_node *n;
1421 unsigned int pos, bits;
1422 t_key key = ntohl(flp->daddr);
1423 unsigned int chopped_off;
1425 unsigned int current_prefix_length = KEYLENGTH;
1427 t_key pref_mismatch;
1431 n = rcu_dereference(t->trie);
1435 #ifdef CONFIG_IP_FIB_TRIE_STATS
1441 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1445 pn = (struct tnode *) n;
1453 cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1456 n = tnode_get_child_rcu(pn, cindex);
1459 #ifdef CONFIG_IP_FIB_TRIE_STATS
1460 t->stats.null_node_hit++;
1466 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1472 cn = (struct tnode *)n;
1475 * It's a tnode, and we can do some extra checks here if we
1476 * like, to avoid descending into a dead-end branch.
1477 * This tnode is in the parent's child array at index
1478 * key[p_pos..p_pos+p_bits] but potentially with some bits
1479 * chopped off, so in reality the index may be just a
1480 * subprefix, padded with zero at the end.
1481 * We can also take a look at any skipped bits in this
1482 * tnode - everything up to p_pos is supposed to be ok,
1483 * and the non-chopped bits of the index (se previous
1484 * paragraph) are also guaranteed ok, but the rest is
1485 * considered unknown.
1487 * The skipped bits are key[pos+bits..cn->pos].
1490 /* If current_prefix_length < pos+bits, we are already doing
1491 * actual prefix matching, which means everything from
1492 * pos+(bits-chopped_off) onward must be zero along some
1493 * branch of this subtree - otherwise there is *no* valid
1494 * prefix present. Here we can only check the skipped
1495 * bits. Remember, since we have already indexed into the
1496 * parent's child array, we know that the bits we chopped of
1500 /* NOTA BENE: Checking only skipped bits
1501 for the new node here */
1503 if (current_prefix_length < pos+bits) {
1504 if (tkey_extract_bits(cn->key, current_prefix_length,
1505 cn->pos - current_prefix_length)
1511 * If chopped_off=0, the index is fully validated and we
1512 * only need to look at the skipped bits for this, the new,
1513 * tnode. What we actually want to do is to find out if
1514 * these skipped bits match our key perfectly, or if we will
1515 * have to count on finding a matching prefix further down,
1516 * because if we do, we would like to have some way of
1517 * verifying the existence of such a prefix at this point.
1520 /* The only thing we can do at this point is to verify that
1521 * any such matching prefix can indeed be a prefix to our
1522 * key, and if the bits in the node we are inspecting that
1523 * do not match our key are not ZERO, this cannot be true.
1524 * Thus, find out where there is a mismatch (before cn->pos)
1525 * and verify that all the mismatching bits are zero in the
1530 * Note: We aren't very concerned about the piece of
1531 * the key that precede pn->pos+pn->bits, since these
1532 * have already been checked. The bits after cn->pos
1533 * aren't checked since these are by definition
1534 * "unknown" at this point. Thus, what we want to see
1535 * is if we are about to enter the "prefix matching"
1536 * state, and in that case verify that the skipped
1537 * bits that will prevail throughout this subtree are
1538 * zero, as they have to be if we are to find a
1542 pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
1545 * In short: If skipped bits in this node do not match
1546 * the search key, enter the "prefix matching"
1549 if (pref_mismatch) {
1550 /* fls(x) = __fls(x) + 1 */
1551 int mp = KEYLENGTH - __fls(pref_mismatch) - 1;
1553 if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
1556 if (current_prefix_length >= cn->pos)
1557 current_prefix_length = mp;
1560 pn = (struct tnode *)n; /* Descend */
1567 /* As zero don't change the child key (cindex) */
1568 while ((chopped_off <= pn->bits)
1569 && !(cindex & (1<<(chopped_off-1))))
1572 /* Decrease current_... with bits chopped off */
1573 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1574 current_prefix_length = pn->pos + pn->bits
1578 * Either we do the actual chop off according or if we have
1579 * chopped off all bits in this tnode walk up to our parent.
1582 if (chopped_off <= pn->bits) {
1583 cindex &= ~(1 << (chopped_off-1));
1585 struct tnode *parent = node_parent_rcu((struct rt_trie_node *) pn);
1589 /* Get Child's index */
1590 cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1594 #ifdef CONFIG_IP_FIB_TRIE_STATS
1595 t->stats.backtrack++;
1606 EXPORT_SYMBOL_GPL(fib_table_lookup);
1609 * Remove the leaf and return parent.
1611 static void trie_leaf_remove(struct trie *t, struct leaf *l)
1613 struct tnode *tp = node_parent((struct rt_trie_node *) l);
1615 pr_debug("entering trie_leaf_remove(%p)\n", l);
1618 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1619 put_child(tp, cindex, NULL);
1620 trie_rebalance(t, tp);
1622 RCU_INIT_POINTER(t->trie, NULL);
1628 * Caller must hold RTNL.
1630 int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
1632 struct trie *t = (struct trie *) tb->tb_data;
1634 int plen = cfg->fc_dst_len;
1635 u8 tos = cfg->fc_tos;
1636 struct fib_alias *fa, *fa_to_delete;
1637 struct list_head *fa_head;
1639 struct leaf_info *li;
1644 key = ntohl(cfg->fc_dst);
1645 mask = ntohl(inet_make_mask(plen));
1651 l = fib_find_node(t, key);
1656 li = find_leaf_info(l, plen);
1661 fa_head = &li->falh;
1662 fa = fib_find_alias(fa_head, tos, 0);
1667 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1669 fa_to_delete = NULL;
1670 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1671 list_for_each_entry_continue(fa, fa_head, fa_list) {
1672 struct fib_info *fi = fa->fa_info;
1674 if (fa->fa_tos != tos)
1677 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1678 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1679 fa->fa_info->fib_scope == cfg->fc_scope) &&
1680 (!cfg->fc_prefsrc ||
1681 fi->fib_prefsrc == cfg->fc_prefsrc) &&
1682 (!cfg->fc_protocol ||
1683 fi->fib_protocol == cfg->fc_protocol) &&
1684 fib_nh_match(cfg, fi) == 0) {
1694 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1695 &cfg->fc_nlinfo, 0);
1697 list_del_rcu(&fa->fa_list);
1700 tb->tb_num_default--;
1702 if (list_empty(fa_head)) {
1703 hlist_del_rcu(&li->hlist);
1707 if (hlist_empty(&l->list))
1708 trie_leaf_remove(t, l);
1710 if (fa->fa_state & FA_S_ACCESSED)
1711 rt_cache_flush(cfg->fc_nlinfo.nl_net);
1713 fib_release_info(fa->fa_info);
1714 alias_free_mem_rcu(fa);
1718 static int trie_flush_list(struct list_head *head)
1720 struct fib_alias *fa, *fa_node;
1723 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1724 struct fib_info *fi = fa->fa_info;
1726 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1727 list_del_rcu(&fa->fa_list);
1728 fib_release_info(fa->fa_info);
1729 alias_free_mem_rcu(fa);
1736 static int trie_flush_leaf(struct leaf *l)
1739 struct hlist_head *lih = &l->list;
1740 struct hlist_node *tmp;
1741 struct leaf_info *li = NULL;
1743 hlist_for_each_entry_safe(li, tmp, lih, hlist) {
1744 found += trie_flush_list(&li->falh);
1746 if (list_empty(&li->falh)) {
1747 hlist_del_rcu(&li->hlist);
1755 * Scan for the next right leaf starting at node p->child[idx]
1756 * Since we have back pointer, no recursion necessary.
1758 static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1764 idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1768 while (idx < 1u << p->bits) {
1769 c = tnode_get_child_rcu(p, idx++);
1774 prefetch(rcu_dereference_rtnl(p->child[idx]));
1775 return (struct leaf *) c;
1778 /* Rescan start scanning in new node */
1779 p = (struct tnode *) c;
1783 /* Node empty, walk back up to parent */
1784 c = (struct rt_trie_node *) p;
1785 } while ((p = node_parent_rcu(c)) != NULL);
1787 return NULL; /* Root of trie */
1790 static struct leaf *trie_firstleaf(struct trie *t)
1792 struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
1797 if (IS_LEAF(n)) /* trie is just a leaf */
1798 return (struct leaf *) n;
1800 return leaf_walk_rcu(n, NULL);
1803 static struct leaf *trie_nextleaf(struct leaf *l)
1805 struct rt_trie_node *c = (struct rt_trie_node *) l;
1806 struct tnode *p = node_parent_rcu(c);
1809 return NULL; /* trie with just one leaf */
1811 return leaf_walk_rcu(p, c);
1814 static struct leaf *trie_leafindex(struct trie *t, int index)
1816 struct leaf *l = trie_firstleaf(t);
1818 while (l && index-- > 0)
1819 l = trie_nextleaf(l);
1826 * Caller must hold RTNL.
1828 int fib_table_flush(struct fib_table *tb)
1830 struct trie *t = (struct trie *) tb->tb_data;
1831 struct leaf *l, *ll = NULL;
1834 for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1835 found += trie_flush_leaf(l);
1837 if (ll && hlist_empty(&ll->list))
1838 trie_leaf_remove(t, ll);
1842 if (ll && hlist_empty(&ll->list))
1843 trie_leaf_remove(t, ll);
1845 pr_debug("trie_flush found=%d\n", found);
1849 void fib_free_table(struct fib_table *tb)
1854 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1855 struct fib_table *tb,
1856 struct sk_buff *skb, struct netlink_callback *cb)
1859 struct fib_alias *fa;
1860 __be32 xkey = htonl(key);
1865 /* rcu_read_lock is hold by caller */
1867 list_for_each_entry_rcu(fa, fah, fa_list) {
1873 if (fib_dump_info(skb, NETLINK_CB(cb->skb).portid,
1881 fa->fa_info, NLM_F_MULTI) < 0) {
1891 static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1892 struct sk_buff *skb, struct netlink_callback *cb)
1894 struct leaf_info *li;
1900 /* rcu_read_lock is hold by caller */
1901 hlist_for_each_entry_rcu(li, &l->list, hlist) {
1910 if (list_empty(&li->falh))
1913 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1924 int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
1925 struct netlink_callback *cb)
1928 struct trie *t = (struct trie *) tb->tb_data;
1929 t_key key = cb->args[2];
1930 int count = cb->args[3];
1933 /* Dump starting at last key.
1934 * Note: 0.0.0.0/0 (ie default) is first key.
1937 l = trie_firstleaf(t);
1939 /* Normally, continue from last key, but if that is missing
1940 * fallback to using slow rescan
1942 l = fib_find_node(t, key);
1944 l = trie_leafindex(t, count);
1948 cb->args[2] = l->key;
1949 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1950 cb->args[3] = count;
1956 l = trie_nextleaf(l);
1957 memset(&cb->args[4], 0,
1958 sizeof(cb->args) - 4*sizeof(cb->args[0]));
1960 cb->args[3] = count;
1966 void __init fib_trie_init(void)
1968 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1969 sizeof(struct fib_alias),
1970 0, SLAB_PANIC, NULL);
1972 trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1973 max(sizeof(struct leaf),
1974 sizeof(struct leaf_info)),
1975 0, SLAB_PANIC, NULL);
1979 struct fib_table *fib_trie_table(u32 id)
1981 struct fib_table *tb;
1984 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1990 tb->tb_default = -1;
1991 tb->tb_num_default = 0;
1993 t = (struct trie *) tb->tb_data;
1994 memset(t, 0, sizeof(*t));
1999 #ifdef CONFIG_PROC_FS
2000 /* Depth first Trie walk iterator */
2001 struct fib_trie_iter {
2002 struct seq_net_private p;
2003 struct fib_table *tb;
2004 struct tnode *tnode;
2009 static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
2011 struct tnode *tn = iter->tnode;
2012 unsigned int cindex = iter->index;
2015 /* A single entry routing table */
2019 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2020 iter->tnode, iter->index, iter->depth);
2022 while (cindex < (1<<tn->bits)) {
2023 struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
2028 iter->index = cindex + 1;
2030 /* push down one level */
2031 iter->tnode = (struct tnode *) n;
2041 /* Current node exhausted, pop back up */
2042 p = node_parent_rcu((struct rt_trie_node *)tn);
2044 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2054 static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
2057 struct rt_trie_node *n;
2062 n = rcu_dereference(t->trie);
2067 iter->tnode = (struct tnode *) n;
2079 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2081 struct rt_trie_node *n;
2082 struct fib_trie_iter iter;
2084 memset(s, 0, sizeof(*s));
2087 for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2089 struct leaf *l = (struct leaf *)n;
2090 struct leaf_info *li;
2093 s->totdepth += iter.depth;
2094 if (iter.depth > s->maxdepth)
2095 s->maxdepth = iter.depth;
2097 hlist_for_each_entry_rcu(li, &l->list, hlist)
2100 const struct tnode *tn = (const struct tnode *) n;
2104 if (tn->bits < MAX_STAT_DEPTH)
2105 s->nodesizes[tn->bits]++;
2107 for (i = 0; i < (1<<tn->bits); i++)
2116 * This outputs /proc/net/fib_triestats
2118 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2120 unsigned int i, max, pointers, bytes, avdepth;
2123 avdepth = stat->totdepth*100 / stat->leaves;
2127 seq_printf(seq, "\tAver depth: %u.%02d\n",
2128 avdepth / 100, avdepth % 100);
2129 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
2131 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
2132 bytes = sizeof(struct leaf) * stat->leaves;
2134 seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes);
2135 bytes += sizeof(struct leaf_info) * stat->prefixes;
2137 seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2138 bytes += sizeof(struct tnode) * stat->tnodes;
2140 max = MAX_STAT_DEPTH;
2141 while (max > 0 && stat->nodesizes[max-1] == 0)
2145 for (i = 1; i <= max; i++)
2146 if (stat->nodesizes[i] != 0) {
2147 seq_printf(seq, " %u: %u", i, stat->nodesizes[i]);
2148 pointers += (1<<i) * stat->nodesizes[i];
2150 seq_putc(seq, '\n');
2151 seq_printf(seq, "\tPointers: %u\n", pointers);
2153 bytes += sizeof(struct rt_trie_node *) * pointers;
2154 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2155 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
2158 #ifdef CONFIG_IP_FIB_TRIE_STATS
2159 static void trie_show_usage(struct seq_file *seq,
2160 const struct trie_use_stats *stats)
2162 seq_printf(seq, "\nCounters:\n---------\n");
2163 seq_printf(seq, "gets = %u\n", stats->gets);
2164 seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2165 seq_printf(seq, "semantic match passed = %u\n",
2166 stats->semantic_match_passed);
2167 seq_printf(seq, "semantic match miss = %u\n",
2168 stats->semantic_match_miss);
2169 seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2170 seq_printf(seq, "skipped node resize = %u\n\n",
2171 stats->resize_node_skipped);
2173 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2175 static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2177 if (tb->tb_id == RT_TABLE_LOCAL)
2178 seq_puts(seq, "Local:\n");
2179 else if (tb->tb_id == RT_TABLE_MAIN)
2180 seq_puts(seq, "Main:\n");
2182 seq_printf(seq, "Id %d:\n", tb->tb_id);
2186 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2188 struct net *net = (struct net *)seq->private;
2192 "Basic info: size of leaf:"
2193 " %Zd bytes, size of tnode: %Zd bytes.\n",
2194 sizeof(struct leaf), sizeof(struct tnode));
2196 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2197 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2198 struct fib_table *tb;
2200 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2201 struct trie *t = (struct trie *) tb->tb_data;
2202 struct trie_stat stat;
2207 fib_table_print(seq, tb);
2209 trie_collect_stats(t, &stat);
2210 trie_show_stats(seq, &stat);
2211 #ifdef CONFIG_IP_FIB_TRIE_STATS
2212 trie_show_usage(seq, &t->stats);
2220 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2222 return single_open_net(inode, file, fib_triestat_seq_show);
2225 static const struct file_operations fib_triestat_fops = {
2226 .owner = THIS_MODULE,
2227 .open = fib_triestat_seq_open,
2229 .llseek = seq_lseek,
2230 .release = single_release_net,
2233 static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2235 struct fib_trie_iter *iter = seq->private;
2236 struct net *net = seq_file_net(seq);
2240 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2241 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2242 struct fib_table *tb;
2244 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2245 struct rt_trie_node *n;
2247 for (n = fib_trie_get_first(iter,
2248 (struct trie *) tb->tb_data);
2249 n; n = fib_trie_get_next(iter))
2260 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2264 return fib_trie_get_idx(seq, *pos);
2267 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2269 struct fib_trie_iter *iter = seq->private;
2270 struct net *net = seq_file_net(seq);
2271 struct fib_table *tb = iter->tb;
2272 struct hlist_node *tb_node;
2274 struct rt_trie_node *n;
2277 /* next node in same table */
2278 n = fib_trie_get_next(iter);
2282 /* walk rest of this hash chain */
2283 h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2284 while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2285 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2286 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2291 /* new hash chain */
2292 while (++h < FIB_TABLE_HASHSZ) {
2293 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2294 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2295 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2307 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2313 static void seq_indent(struct seq_file *seq, int n)
2319 static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2322 case RT_SCOPE_UNIVERSE: return "universe";
2323 case RT_SCOPE_SITE: return "site";
2324 case RT_SCOPE_LINK: return "link";
2325 case RT_SCOPE_HOST: return "host";
2326 case RT_SCOPE_NOWHERE: return "nowhere";
2328 snprintf(buf, len, "scope=%d", s);
2333 static const char *const rtn_type_names[__RTN_MAX] = {
2334 [RTN_UNSPEC] = "UNSPEC",
2335 [RTN_UNICAST] = "UNICAST",
2336 [RTN_LOCAL] = "LOCAL",
2337 [RTN_BROADCAST] = "BROADCAST",
2338 [RTN_ANYCAST] = "ANYCAST",
2339 [RTN_MULTICAST] = "MULTICAST",
2340 [RTN_BLACKHOLE] = "BLACKHOLE",
2341 [RTN_UNREACHABLE] = "UNREACHABLE",
2342 [RTN_PROHIBIT] = "PROHIBIT",
2343 [RTN_THROW] = "THROW",
2345 [RTN_XRESOLVE] = "XRESOLVE",
2348 static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2350 if (t < __RTN_MAX && rtn_type_names[t])
2351 return rtn_type_names[t];
2352 snprintf(buf, len, "type %u", t);
2356 /* Pretty print the trie */
2357 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2359 const struct fib_trie_iter *iter = seq->private;
2360 struct rt_trie_node *n = v;
2362 if (!node_parent_rcu(n))
2363 fib_table_print(seq, iter->tb);
2366 struct tnode *tn = (struct tnode *) n;
2367 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2369 seq_indent(seq, iter->depth-1);
2370 seq_printf(seq, " +-- %pI4/%d %d %d %d\n",
2371 &prf, tn->pos, tn->bits, tn->full_children,
2372 tn->empty_children);
2375 struct leaf *l = (struct leaf *) n;
2376 struct leaf_info *li;
2377 __be32 val = htonl(l->key);
2379 seq_indent(seq, iter->depth);
2380 seq_printf(seq, " |-- %pI4\n", &val);
2382 hlist_for_each_entry_rcu(li, &l->list, hlist) {
2383 struct fib_alias *fa;
2385 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2386 char buf1[32], buf2[32];
2388 seq_indent(seq, iter->depth+1);
2389 seq_printf(seq, " /%d %s %s", li->plen,
2390 rtn_scope(buf1, sizeof(buf1),
2391 fa->fa_info->fib_scope),
2392 rtn_type(buf2, sizeof(buf2),
2395 seq_printf(seq, " tos=%d", fa->fa_tos);
2396 seq_putc(seq, '\n');
2404 static const struct seq_operations fib_trie_seq_ops = {
2405 .start = fib_trie_seq_start,
2406 .next = fib_trie_seq_next,
2407 .stop = fib_trie_seq_stop,
2408 .show = fib_trie_seq_show,
2411 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2413 return seq_open_net(inode, file, &fib_trie_seq_ops,
2414 sizeof(struct fib_trie_iter));
2417 static const struct file_operations fib_trie_fops = {
2418 .owner = THIS_MODULE,
2419 .open = fib_trie_seq_open,
2421 .llseek = seq_lseek,
2422 .release = seq_release_net,
2425 struct fib_route_iter {
2426 struct seq_net_private p;
2427 struct trie *main_trie;
2432 static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2434 struct leaf *l = NULL;
2435 struct trie *t = iter->main_trie;
2437 /* use cache location of last found key */
2438 if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2442 l = trie_firstleaf(t);
2445 while (l && pos-- > 0) {
2447 l = trie_nextleaf(l);
2451 iter->key = pos; /* remember it */
2453 iter->pos = 0; /* forget it */
2458 static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2461 struct fib_route_iter *iter = seq->private;
2462 struct fib_table *tb;
2465 tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2469 iter->main_trie = (struct trie *) tb->tb_data;
2471 return SEQ_START_TOKEN;
2473 return fib_route_get_idx(iter, *pos - 1);
2476 static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2478 struct fib_route_iter *iter = seq->private;
2482 if (v == SEQ_START_TOKEN) {
2484 l = trie_firstleaf(iter->main_trie);
2487 l = trie_nextleaf(l);
2497 static void fib_route_seq_stop(struct seq_file *seq, void *v)
2503 static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2505 unsigned int flags = 0;
2507 if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
2509 if (fi && fi->fib_nh->nh_gw)
2510 flags |= RTF_GATEWAY;
2511 if (mask == htonl(0xFFFFFFFF))
2518 * This outputs /proc/net/route.
2519 * The format of the file is not supposed to be changed
2520 * and needs to be same as fib_hash output to avoid breaking
2523 static int fib_route_seq_show(struct seq_file *seq, void *v)
2526 struct leaf_info *li;
2528 if (v == SEQ_START_TOKEN) {
2529 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2530 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2535 hlist_for_each_entry_rcu(li, &l->list, hlist) {
2536 struct fib_alias *fa;
2537 __be32 mask, prefix;
2539 mask = inet_make_mask(li->plen);
2540 prefix = htonl(l->key);
2542 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2543 const struct fib_info *fi = fa->fa_info;
2544 unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2547 if (fa->fa_type == RTN_BROADCAST
2548 || fa->fa_type == RTN_MULTICAST)
2553 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2554 "%d\t%08X\t%d\t%u\t%u%n",
2555 fi->fib_dev ? fi->fib_dev->name : "*",
2557 fi->fib_nh->nh_gw, flags, 0, 0,
2561 fi->fib_advmss + 40 : 0),
2563 fi->fib_rtt >> 3, &len);
2566 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2567 "%d\t%08X\t%d\t%u\t%u%n",
2568 prefix, 0, flags, 0, 0, 0,
2569 mask, 0, 0, 0, &len);
2571 seq_printf(seq, "%*s\n", 127 - len, "");
2578 static const struct seq_operations fib_route_seq_ops = {
2579 .start = fib_route_seq_start,
2580 .next = fib_route_seq_next,
2581 .stop = fib_route_seq_stop,
2582 .show = fib_route_seq_show,
2585 static int fib_route_seq_open(struct inode *inode, struct file *file)
2587 return seq_open_net(inode, file, &fib_route_seq_ops,
2588 sizeof(struct fib_route_iter));
2591 static const struct file_operations fib_route_fops = {
2592 .owner = THIS_MODULE,
2593 .open = fib_route_seq_open,
2595 .llseek = seq_lseek,
2596 .release = seq_release_net,
2599 int __net_init fib_proc_init(struct net *net)
2601 if (!proc_create("fib_trie", S_IRUGO, net->proc_net, &fib_trie_fops))
2604 if (!proc_create("fib_triestat", S_IRUGO, net->proc_net,
2605 &fib_triestat_fops))
2608 if (!proc_create("route", S_IRUGO, net->proc_net, &fib_route_fops))
2614 remove_proc_entry("fib_triestat", net->proc_net);
2616 remove_proc_entry("fib_trie", net->proc_net);
2621 void __net_exit fib_proc_exit(struct net *net)
2623 remove_proc_entry("fib_trie", net->proc_net);
2624 remove_proc_entry("fib_triestat", net->proc_net);
2625 remove_proc_entry("route", net->proc_net);
2628 #endif /* CONFIG_PROC_FS */