Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next-2.6
[linux-2.6/linux-acpi-2.6/ibm-acpi-2.6.git] / net / ipv4 / fib_trie.c
blobc779ce96e5b577e757fd5f1e69d417359ff30a40
1 /*
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 <asm/system.h>
55 #include <linux/bitops.h>
56 #include <linux/types.h>
57 #include <linux/kernel.h>
58 #include <linux/mm.h>
59 #include <linux/string.h>
60 #include <linux/socket.h>
61 #include <linux/sockios.h>
62 #include <linux/errno.h>
63 #include <linux/in.h>
64 #include <linux/inet.h>
65 #include <linux/inetdevice.h>
66 #include <linux/netdevice.h>
67 #include <linux/if_arp.h>
68 #include <linux/proc_fs.h>
69 #include <linux/rcupdate.h>
70 #include <linux/skbuff.h>
71 #include <linux/netlink.h>
72 #include <linux/init.h>
73 #include <linux/list.h>
74 #include <linux/slab.h>
75 #include <net/net_namespace.h>
76 #include <net/ip.h>
77 #include <net/protocol.h>
78 #include <net/route.h>
79 #include <net/tcp.h>
80 #include <net/sock.h>
81 #include <net/ip_fib.h>
82 #include "fib_lookup.h"
84 #define MAX_STAT_DEPTH 32
86 #define KEYLENGTH (8*sizeof(t_key))
88 typedef unsigned int t_key;
90 #define T_TNODE 0
91 #define T_LEAF 1
92 #define NODE_TYPE_MASK 0x1UL
93 #define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
95 #define IS_TNODE(n) (!(n->parent & T_LEAF))
96 #define IS_LEAF(n) (n->parent & T_LEAF)
98 struct rt_trie_node {
99 unsigned long parent;
100 t_key key;
103 struct leaf {
104 unsigned long parent;
105 t_key key;
106 struct hlist_head list;
107 struct rcu_head rcu;
110 struct leaf_info {
111 struct hlist_node hlist;
112 struct rcu_head rcu;
113 int plen;
114 struct list_head falh;
117 struct tnode {
118 unsigned long parent;
119 t_key key;
120 unsigned char pos; /* 2log(KEYLENGTH) bits needed */
121 unsigned char bits; /* 2log(KEYLENGTH) bits needed */
122 unsigned int full_children; /* KEYLENGTH bits needed */
123 unsigned int empty_children; /* KEYLENGTH bits needed */
124 union {
125 struct rcu_head rcu;
126 struct work_struct work;
127 struct tnode *tnode_free;
129 struct rt_trie_node __rcu *child[0];
132 #ifdef CONFIG_IP_FIB_TRIE_STATS
133 struct trie_use_stats {
134 unsigned int gets;
135 unsigned int backtrack;
136 unsigned int semantic_match_passed;
137 unsigned int semantic_match_miss;
138 unsigned int null_node_hit;
139 unsigned int resize_node_skipped;
141 #endif
143 struct trie_stat {
144 unsigned int totdepth;
145 unsigned int maxdepth;
146 unsigned int tnodes;
147 unsigned int leaves;
148 unsigned int nullpointers;
149 unsigned int prefixes;
150 unsigned int nodesizes[MAX_STAT_DEPTH];
153 struct trie {
154 struct rt_trie_node __rcu *trie;
155 #ifdef CONFIG_IP_FIB_TRIE_STATS
156 struct trie_use_stats stats;
157 #endif
160 static void put_child(struct trie *t, struct tnode *tn, int i, struct rt_trie_node *n);
161 static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
162 int wasfull);
163 static struct rt_trie_node *resize(struct trie *t, struct tnode *tn);
164 static struct tnode *inflate(struct trie *t, struct tnode *tn);
165 static struct tnode *halve(struct trie *t, struct tnode *tn);
166 /* tnodes to free after resize(); protected by RTNL */
167 static struct tnode *tnode_free_head;
168 static size_t tnode_free_size;
171 * synchronize_rcu after call_rcu for that many pages; it should be especially
172 * useful before resizing the root node with PREEMPT_NONE configs; the value was
173 * obtained experimentally, aiming to avoid visible slowdown.
175 static const int sync_pages = 128;
177 static struct kmem_cache *fn_alias_kmem __read_mostly;
178 static struct kmem_cache *trie_leaf_kmem __read_mostly;
181 * caller must hold RTNL
183 static inline struct tnode *node_parent(const struct rt_trie_node *node)
185 unsigned long parent;
187 parent = rcu_dereference_index_check(node->parent, lockdep_rtnl_is_held());
189 return (struct tnode *)(parent & ~NODE_TYPE_MASK);
193 * caller must hold RCU read lock or RTNL
195 static inline struct tnode *node_parent_rcu(const struct rt_trie_node *node)
197 unsigned long parent;
199 parent = rcu_dereference_index_check(node->parent, rcu_read_lock_held() ||
200 lockdep_rtnl_is_held());
202 return (struct tnode *)(parent & ~NODE_TYPE_MASK);
205 /* Same as rcu_assign_pointer
206 * but that macro() assumes that value is a pointer.
208 static inline void node_set_parent(struct rt_trie_node *node, struct tnode *ptr)
210 smp_wmb();
211 node->parent = (unsigned long)ptr | NODE_TYPE(node);
215 * caller must hold RTNL
217 static inline struct rt_trie_node *tnode_get_child(const struct tnode *tn, unsigned int i)
219 BUG_ON(i >= 1U << tn->bits);
221 return rtnl_dereference(tn->child[i]);
225 * caller must hold RCU read lock or RTNL
227 static inline struct rt_trie_node *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
229 BUG_ON(i >= 1U << tn->bits);
231 return rcu_dereference_rtnl(tn->child[i]);
234 static inline int tnode_child_length(const struct tnode *tn)
236 return 1 << tn->bits;
239 static inline t_key mask_pfx(t_key k, unsigned int l)
241 return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
244 static inline t_key tkey_extract_bits(t_key a, unsigned int offset, unsigned int bits)
246 if (offset < KEYLENGTH)
247 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
248 else
249 return 0;
252 static inline int tkey_equals(t_key a, t_key b)
254 return a == b;
257 static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
259 if (bits == 0 || offset >= KEYLENGTH)
260 return 1;
261 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
262 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
265 static inline int tkey_mismatch(t_key a, int offset, t_key b)
267 t_key diff = a ^ b;
268 int i = offset;
270 if (!diff)
271 return 0;
272 while ((diff << i) >> (KEYLENGTH-1) == 0)
273 i++;
274 return i;
278 To understand this stuff, an understanding of keys and all their bits is
279 necessary. Every node in the trie has a key associated with it, but not
280 all of the bits in that key are significant.
282 Consider a node 'n' and its parent 'tp'.
284 If n is a leaf, every bit in its key is significant. Its presence is
285 necessitated by path compression, since during a tree traversal (when
286 searching for a leaf - unless we are doing an insertion) we will completely
287 ignore all skipped bits we encounter. Thus we need to verify, at the end of
288 a potentially successful search, that we have indeed been walking the
289 correct key path.
291 Note that we can never "miss" the correct key in the tree if present by
292 following the wrong path. Path compression ensures that segments of the key
293 that are the same for all keys with a given prefix are skipped, but the
294 skipped part *is* identical for each node in the subtrie below the skipped
295 bit! trie_insert() in this implementation takes care of that - note the
296 call to tkey_sub_equals() in trie_insert().
298 if n is an internal node - a 'tnode' here, the various parts of its key
299 have many different meanings.
301 Example:
302 _________________________________________________________________
303 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
304 -----------------------------------------------------------------
305 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
307 _________________________________________________________________
308 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
309 -----------------------------------------------------------------
310 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
312 tp->pos = 7
313 tp->bits = 3
314 n->pos = 15
315 n->bits = 4
317 First, let's just ignore the bits that come before the parent tp, that is
318 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
319 not use them for anything.
321 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
322 index into the parent's child array. That is, they will be used to find
323 'n' among tp's children.
325 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
326 for the node n.
328 All the bits we have seen so far are significant to the node n. The rest
329 of the bits are really not needed or indeed known in n->key.
331 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
332 n's child array, and will of course be different for each child.
335 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
336 at this point.
340 static inline void check_tnode(const struct tnode *tn)
342 WARN_ON(tn && tn->pos+tn->bits > 32);
345 static const int halve_threshold = 25;
346 static const int inflate_threshold = 50;
347 static const int halve_threshold_root = 15;
348 static const int inflate_threshold_root = 30;
350 static void __alias_free_mem(struct rcu_head *head)
352 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
353 kmem_cache_free(fn_alias_kmem, fa);
356 static inline void alias_free_mem_rcu(struct fib_alias *fa)
358 call_rcu(&fa->rcu, __alias_free_mem);
361 static void __leaf_free_rcu(struct rcu_head *head)
363 struct leaf *l = container_of(head, struct leaf, rcu);
364 kmem_cache_free(trie_leaf_kmem, l);
367 static inline void free_leaf(struct leaf *l)
369 call_rcu_bh(&l->rcu, __leaf_free_rcu);
372 static inline void free_leaf_info(struct leaf_info *leaf)
374 kfree_rcu(leaf, rcu);
377 static struct tnode *tnode_alloc(size_t size)
379 if (size <= PAGE_SIZE)
380 return kzalloc(size, GFP_KERNEL);
381 else
382 return vzalloc(size);
385 static void __tnode_vfree(struct work_struct *arg)
387 struct tnode *tn = container_of(arg, struct tnode, work);
388 vfree(tn);
391 static void __tnode_free_rcu(struct rcu_head *head)
393 struct tnode *tn = container_of(head, struct tnode, rcu);
394 size_t size = sizeof(struct tnode) +
395 (sizeof(struct rt_trie_node *) << tn->bits);
397 if (size <= PAGE_SIZE)
398 kfree(tn);
399 else {
400 INIT_WORK(&tn->work, __tnode_vfree);
401 schedule_work(&tn->work);
405 static inline void tnode_free(struct tnode *tn)
407 if (IS_LEAF(tn))
408 free_leaf((struct leaf *) tn);
409 else
410 call_rcu(&tn->rcu, __tnode_free_rcu);
413 static void tnode_free_safe(struct tnode *tn)
415 BUG_ON(IS_LEAF(tn));
416 tn->tnode_free = tnode_free_head;
417 tnode_free_head = tn;
418 tnode_free_size += sizeof(struct tnode) +
419 (sizeof(struct rt_trie_node *) << tn->bits);
422 static void tnode_free_flush(void)
424 struct tnode *tn;
426 while ((tn = tnode_free_head)) {
427 tnode_free_head = tn->tnode_free;
428 tn->tnode_free = NULL;
429 tnode_free(tn);
432 if (tnode_free_size >= PAGE_SIZE * sync_pages) {
433 tnode_free_size = 0;
434 synchronize_rcu();
438 static struct leaf *leaf_new(void)
440 struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
441 if (l) {
442 l->parent = T_LEAF;
443 INIT_HLIST_HEAD(&l->list);
445 return l;
448 static struct leaf_info *leaf_info_new(int plen)
450 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
451 if (li) {
452 li->plen = plen;
453 INIT_LIST_HEAD(&li->falh);
455 return li;
458 static struct tnode *tnode_new(t_key key, int pos, int bits)
460 size_t sz = sizeof(struct tnode) + (sizeof(struct rt_trie_node *) << bits);
461 struct tnode *tn = tnode_alloc(sz);
463 if (tn) {
464 tn->parent = T_TNODE;
465 tn->pos = pos;
466 tn->bits = bits;
467 tn->key = key;
468 tn->full_children = 0;
469 tn->empty_children = 1<<bits;
472 pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode),
473 sizeof(struct rt_trie_node) << bits);
474 return tn;
478 * Check whether a tnode 'n' is "full", i.e. it is an internal node
479 * and no bits are skipped. See discussion in dyntree paper p. 6
482 static inline int tnode_full(const struct tnode *tn, const struct rt_trie_node *n)
484 if (n == NULL || IS_LEAF(n))
485 return 0;
487 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
490 static inline void put_child(struct trie *t, struct tnode *tn, int i,
491 struct rt_trie_node *n)
493 tnode_put_child_reorg(tn, i, n, -1);
497 * Add a child at position i overwriting the old value.
498 * Update the value of full_children and empty_children.
501 static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
502 int wasfull)
504 struct rt_trie_node *chi = rtnl_dereference(tn->child[i]);
505 int isfull;
507 BUG_ON(i >= 1<<tn->bits);
509 /* update emptyChildren */
510 if (n == NULL && chi != NULL)
511 tn->empty_children++;
512 else if (n != NULL && chi == NULL)
513 tn->empty_children--;
515 /* update fullChildren */
516 if (wasfull == -1)
517 wasfull = tnode_full(tn, chi);
519 isfull = tnode_full(tn, n);
520 if (wasfull && !isfull)
521 tn->full_children--;
522 else if (!wasfull && isfull)
523 tn->full_children++;
525 if (n)
526 node_set_parent(n, tn);
528 rcu_assign_pointer(tn->child[i], n);
531 #define MAX_WORK 10
532 static struct rt_trie_node *resize(struct trie *t, struct tnode *tn)
534 int i;
535 struct tnode *old_tn;
536 int inflate_threshold_use;
537 int halve_threshold_use;
538 int max_work;
540 if (!tn)
541 return NULL;
543 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
544 tn, inflate_threshold, halve_threshold);
546 /* No children */
547 if (tn->empty_children == tnode_child_length(tn)) {
548 tnode_free_safe(tn);
549 return NULL;
551 /* One child */
552 if (tn->empty_children == tnode_child_length(tn) - 1)
553 goto one_child;
555 * Double as long as the resulting node has a number of
556 * nonempty nodes that are above the threshold.
560 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
561 * the Helsinki University of Technology and Matti Tikkanen of Nokia
562 * Telecommunications, page 6:
563 * "A node is doubled if the ratio of non-empty children to all
564 * children in the *doubled* node is at least 'high'."
566 * 'high' in this instance is the variable 'inflate_threshold'. It
567 * is expressed as a percentage, so we multiply it with
568 * tnode_child_length() and instead of multiplying by 2 (since the
569 * child array will be doubled by inflate()) and multiplying
570 * the left-hand side by 100 (to handle the percentage thing) we
571 * multiply the left-hand side by 50.
573 * The left-hand side may look a bit weird: tnode_child_length(tn)
574 * - tn->empty_children is of course the number of non-null children
575 * in the current node. tn->full_children is the number of "full"
576 * children, that is non-null tnodes with a skip value of 0.
577 * All of those will be doubled in the resulting inflated tnode, so
578 * we just count them one extra time here.
580 * A clearer way to write this would be:
582 * to_be_doubled = tn->full_children;
583 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
584 * tn->full_children;
586 * new_child_length = tnode_child_length(tn) * 2;
588 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
589 * new_child_length;
590 * if (new_fill_factor >= inflate_threshold)
592 * ...and so on, tho it would mess up the while () loop.
594 * anyway,
595 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
596 * inflate_threshold
598 * avoid a division:
599 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
600 * inflate_threshold * new_child_length
602 * expand not_to_be_doubled and to_be_doubled, and shorten:
603 * 100 * (tnode_child_length(tn) - tn->empty_children +
604 * tn->full_children) >= inflate_threshold * new_child_length
606 * expand new_child_length:
607 * 100 * (tnode_child_length(tn) - tn->empty_children +
608 * tn->full_children) >=
609 * inflate_threshold * tnode_child_length(tn) * 2
611 * shorten again:
612 * 50 * (tn->full_children + tnode_child_length(tn) -
613 * tn->empty_children) >= inflate_threshold *
614 * tnode_child_length(tn)
618 check_tnode(tn);
620 /* Keep root node larger */
622 if (!node_parent((struct rt_trie_node *)tn)) {
623 inflate_threshold_use = inflate_threshold_root;
624 halve_threshold_use = halve_threshold_root;
625 } else {
626 inflate_threshold_use = inflate_threshold;
627 halve_threshold_use = halve_threshold;
630 max_work = MAX_WORK;
631 while ((tn->full_children > 0 && max_work-- &&
632 50 * (tn->full_children + tnode_child_length(tn)
633 - tn->empty_children)
634 >= inflate_threshold_use * tnode_child_length(tn))) {
636 old_tn = tn;
637 tn = inflate(t, tn);
639 if (IS_ERR(tn)) {
640 tn = old_tn;
641 #ifdef CONFIG_IP_FIB_TRIE_STATS
642 t->stats.resize_node_skipped++;
643 #endif
644 break;
648 check_tnode(tn);
650 /* Return if at least one inflate is run */
651 if (max_work != MAX_WORK)
652 return (struct rt_trie_node *) tn;
655 * Halve as long as the number of empty children in this
656 * node is above threshold.
659 max_work = MAX_WORK;
660 while (tn->bits > 1 && max_work-- &&
661 100 * (tnode_child_length(tn) - tn->empty_children) <
662 halve_threshold_use * tnode_child_length(tn)) {
664 old_tn = tn;
665 tn = halve(t, tn);
666 if (IS_ERR(tn)) {
667 tn = old_tn;
668 #ifdef CONFIG_IP_FIB_TRIE_STATS
669 t->stats.resize_node_skipped++;
670 #endif
671 break;
676 /* Only one child remains */
677 if (tn->empty_children == tnode_child_length(tn) - 1) {
678 one_child:
679 for (i = 0; i < tnode_child_length(tn); i++) {
680 struct rt_trie_node *n;
682 n = rtnl_dereference(tn->child[i]);
683 if (!n)
684 continue;
686 /* compress one level */
688 node_set_parent(n, NULL);
689 tnode_free_safe(tn);
690 return n;
693 return (struct rt_trie_node *) tn;
697 static void tnode_clean_free(struct tnode *tn)
699 int i;
700 struct tnode *tofree;
702 for (i = 0; i < tnode_child_length(tn); i++) {
703 tofree = (struct tnode *)rtnl_dereference(tn->child[i]);
704 if (tofree)
705 tnode_free(tofree);
707 tnode_free(tn);
710 static struct tnode *inflate(struct trie *t, struct tnode *tn)
712 struct tnode *oldtnode = tn;
713 int olen = tnode_child_length(tn);
714 int i;
716 pr_debug("In inflate\n");
718 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
720 if (!tn)
721 return ERR_PTR(-ENOMEM);
724 * Preallocate and store tnodes before the actual work so we
725 * don't get into an inconsistent state if memory allocation
726 * fails. In case of failure we return the oldnode and inflate
727 * of tnode is ignored.
730 for (i = 0; i < olen; i++) {
731 struct tnode *inode;
733 inode = (struct tnode *) tnode_get_child(oldtnode, i);
734 if (inode &&
735 IS_TNODE(inode) &&
736 inode->pos == oldtnode->pos + oldtnode->bits &&
737 inode->bits > 1) {
738 struct tnode *left, *right;
739 t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
741 left = tnode_new(inode->key&(~m), inode->pos + 1,
742 inode->bits - 1);
743 if (!left)
744 goto nomem;
746 right = tnode_new(inode->key|m, inode->pos + 1,
747 inode->bits - 1);
749 if (!right) {
750 tnode_free(left);
751 goto nomem;
754 put_child(t, tn, 2*i, (struct rt_trie_node *) left);
755 put_child(t, tn, 2*i+1, (struct rt_trie_node *) right);
759 for (i = 0; i < olen; i++) {
760 struct tnode *inode;
761 struct rt_trie_node *node = tnode_get_child(oldtnode, i);
762 struct tnode *left, *right;
763 int size, j;
765 /* An empty child */
766 if (node == NULL)
767 continue;
769 /* A leaf or an internal node with skipped bits */
771 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
772 tn->pos + tn->bits - 1) {
773 if (tkey_extract_bits(node->key,
774 oldtnode->pos + oldtnode->bits,
775 1) == 0)
776 put_child(t, tn, 2*i, node);
777 else
778 put_child(t, tn, 2*i+1, node);
779 continue;
782 /* An internal node with two children */
783 inode = (struct tnode *) node;
785 if (inode->bits == 1) {
786 put_child(t, tn, 2*i, rtnl_dereference(inode->child[0]));
787 put_child(t, tn, 2*i+1, rtnl_dereference(inode->child[1]));
789 tnode_free_safe(inode);
790 continue;
793 /* An internal node with more than two children */
795 /* We will replace this node 'inode' with two new
796 * ones, 'left' and 'right', each with half of the
797 * original children. The two new nodes will have
798 * a position one bit further down the key and this
799 * means that the "significant" part of their keys
800 * (see the discussion near the top of this file)
801 * will differ by one bit, which will be "0" in
802 * left's key and "1" in right's key. Since we are
803 * moving the key position by one step, the bit that
804 * we are moving away from - the bit at position
805 * (inode->pos) - is the one that will differ between
806 * left and right. So... we synthesize that bit in the
807 * two new keys.
808 * The mask 'm' below will be a single "one" bit at
809 * the position (inode->pos)
812 /* Use the old key, but set the new significant
813 * bit to zero.
816 left = (struct tnode *) tnode_get_child(tn, 2*i);
817 put_child(t, tn, 2*i, NULL);
819 BUG_ON(!left);
821 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
822 put_child(t, tn, 2*i+1, NULL);
824 BUG_ON(!right);
826 size = tnode_child_length(left);
827 for (j = 0; j < size; j++) {
828 put_child(t, left, j, rtnl_dereference(inode->child[j]));
829 put_child(t, right, j, rtnl_dereference(inode->child[j + size]));
831 put_child(t, tn, 2*i, resize(t, left));
832 put_child(t, tn, 2*i+1, resize(t, right));
834 tnode_free_safe(inode);
836 tnode_free_safe(oldtnode);
837 return tn;
838 nomem:
839 tnode_clean_free(tn);
840 return ERR_PTR(-ENOMEM);
843 static struct tnode *halve(struct trie *t, struct tnode *tn)
845 struct tnode *oldtnode = tn;
846 struct rt_trie_node *left, *right;
847 int i;
848 int olen = tnode_child_length(tn);
850 pr_debug("In halve\n");
852 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
854 if (!tn)
855 return ERR_PTR(-ENOMEM);
858 * Preallocate and store tnodes before the actual work so we
859 * don't get into an inconsistent state if memory allocation
860 * fails. In case of failure we return the oldnode and halve
861 * of tnode is ignored.
864 for (i = 0; i < olen; i += 2) {
865 left = tnode_get_child(oldtnode, i);
866 right = tnode_get_child(oldtnode, i+1);
868 /* Two nonempty children */
869 if (left && right) {
870 struct tnode *newn;
872 newn = tnode_new(left->key, tn->pos + tn->bits, 1);
874 if (!newn)
875 goto nomem;
877 put_child(t, tn, i/2, (struct rt_trie_node *)newn);
882 for (i = 0; i < olen; i += 2) {
883 struct tnode *newBinNode;
885 left = tnode_get_child(oldtnode, i);
886 right = tnode_get_child(oldtnode, i+1);
888 /* At least one of the children is empty */
889 if (left == NULL) {
890 if (right == NULL) /* Both are empty */
891 continue;
892 put_child(t, tn, i/2, right);
893 continue;
896 if (right == NULL) {
897 put_child(t, tn, i/2, left);
898 continue;
901 /* Two nonempty children */
902 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
903 put_child(t, tn, i/2, NULL);
904 put_child(t, newBinNode, 0, left);
905 put_child(t, newBinNode, 1, right);
906 put_child(t, tn, i/2, resize(t, newBinNode));
908 tnode_free_safe(oldtnode);
909 return tn;
910 nomem:
911 tnode_clean_free(tn);
912 return ERR_PTR(-ENOMEM);
915 /* readside must use rcu_read_lock currently dump routines
916 via get_fa_head and dump */
918 static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
920 struct hlist_head *head = &l->list;
921 struct hlist_node *node;
922 struct leaf_info *li;
924 hlist_for_each_entry_rcu(li, node, head, hlist)
925 if (li->plen == plen)
926 return li;
928 return NULL;
931 static inline struct list_head *get_fa_head(struct leaf *l, int plen)
933 struct leaf_info *li = find_leaf_info(l, plen);
935 if (!li)
936 return NULL;
938 return &li->falh;
941 static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
943 struct leaf_info *li = NULL, *last = NULL;
944 struct hlist_node *node;
946 if (hlist_empty(head)) {
947 hlist_add_head_rcu(&new->hlist, head);
948 } else {
949 hlist_for_each_entry(li, node, head, hlist) {
950 if (new->plen > li->plen)
951 break;
953 last = li;
955 if (last)
956 hlist_add_after_rcu(&last->hlist, &new->hlist);
957 else
958 hlist_add_before_rcu(&new->hlist, &li->hlist);
962 /* rcu_read_lock needs to be hold by caller from readside */
964 static struct leaf *
965 fib_find_node(struct trie *t, u32 key)
967 int pos;
968 struct tnode *tn;
969 struct rt_trie_node *n;
971 pos = 0;
972 n = rcu_dereference_rtnl(t->trie);
974 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
975 tn = (struct tnode *) n;
977 check_tnode(tn);
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,
983 tn->pos,
984 tn->bits));
985 } else
986 break;
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;
993 return NULL;
996 static void trie_rebalance(struct trie *t, struct tnode *tn)
998 int wasfull;
999 t_key cindex, key;
1000 struct tnode *tp;
1002 key = tn->key;
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, (struct tnode *)tn);
1009 tnode_put_child_reorg((struct tnode *)tp, cindex,
1010 (struct rt_trie_node *)tn, wasfull);
1012 tp = node_parent((struct rt_trie_node *) tn);
1013 if (!tp)
1014 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1016 tnode_free_flush();
1017 if (!tp)
1018 break;
1019 tn = tp;
1022 /* Handle last (top) tnode */
1023 if (IS_TNODE(tn))
1024 tn = (struct tnode *)resize(t, (struct tnode *)tn);
1026 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1027 tnode_free_flush();
1030 /* only used from updater-side */
1032 static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
1034 int pos, newpos;
1035 struct tnode *tp = NULL, *tn = NULL;
1036 struct rt_trie_node *n;
1037 struct leaf *l;
1038 int missbit;
1039 struct list_head *fa_head = NULL;
1040 struct leaf_info *li;
1041 t_key cindex;
1043 pos = 0;
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;
1067 check_tnode(tn);
1069 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1070 tp = tn;
1071 pos = tn->pos + tn->bits;
1072 n = tnode_get_child(tn,
1073 tkey_extract_bits(key,
1074 tn->pos,
1075 tn->bits));
1077 BUG_ON(n && node_parent(n) != tn);
1078 } else
1079 break;
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);
1096 if (!li)
1097 return NULL;
1099 fa_head = &li->falh;
1100 insert_leaf_info(&l->list, li);
1101 goto done;
1103 l = leaf_new();
1105 if (!l)
1106 return NULL;
1108 l->key = key;
1109 li = leaf_info_new(plen);
1111 if (!li) {
1112 free_leaf(l);
1113 return NULL;
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(t, (struct tnode *)tp, cindex, (struct rt_trie_node *)l);
1126 } else {
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
1133 if (tp)
1134 pos = tp->pos+tp->bits;
1135 else
1136 pos = 0;
1138 if (n) {
1139 newpos = tkey_mismatch(key, pos, n->key);
1140 tn = tnode_new(n->key, newpos, 1);
1141 } else {
1142 newpos = 0;
1143 tn = tnode_new(key, newpos, 1); /* First tnode */
1146 if (!tn) {
1147 free_leaf_info(li);
1148 free_leaf(l);
1149 return NULL;
1152 node_set_parent((struct rt_trie_node *)tn, tp);
1154 missbit = tkey_extract_bits(key, newpos, 1);
1155 put_child(t, tn, missbit, (struct rt_trie_node *)l);
1156 put_child(t, tn, 1-missbit, n);
1158 if (tp) {
1159 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1160 put_child(t, (struct tnode *)tp, cindex,
1161 (struct rt_trie_node *)tn);
1162 } else {
1163 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1164 tp = tn;
1168 if (tp && tp->pos + tp->bits > 32)
1169 pr_warning("fib_trie"
1170 " tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1171 tp, tp->pos, tp->bits, key, plen);
1173 /* Rebalance the trie */
1175 trie_rebalance(t, tp);
1176 done:
1177 return fa_head;
1181 * Caller must hold RTNL.
1183 int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
1185 struct trie *t = (struct trie *) tb->tb_data;
1186 struct fib_alias *fa, *new_fa;
1187 struct list_head *fa_head = NULL;
1188 struct fib_info *fi;
1189 int plen = cfg->fc_dst_len;
1190 u8 tos = cfg->fc_tos;
1191 u32 key, mask;
1192 int err;
1193 struct leaf *l;
1195 if (plen > 32)
1196 return -EINVAL;
1198 key = ntohl(cfg->fc_dst);
1200 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1202 mask = ntohl(inet_make_mask(plen));
1204 if (key & ~mask)
1205 return -EINVAL;
1207 key = key & mask;
1209 fi = fib_create_info(cfg);
1210 if (IS_ERR(fi)) {
1211 err = PTR_ERR(fi);
1212 goto err;
1215 l = fib_find_node(t, key);
1216 fa = NULL;
1218 if (l) {
1219 fa_head = get_fa_head(l, plen);
1220 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1223 /* Now fa, if non-NULL, points to the first fib alias
1224 * with the same keys [prefix,tos,priority], if such key already
1225 * exists or to the node before which we will insert new one.
1227 * If fa is NULL, we will need to allocate a new one and
1228 * insert to the head of f.
1230 * If f is NULL, no fib node matched the destination key
1231 * and we need to allocate a new one of those as well.
1234 if (fa && fa->fa_tos == tos &&
1235 fa->fa_info->fib_priority == fi->fib_priority) {
1236 struct fib_alias *fa_first, *fa_match;
1238 err = -EEXIST;
1239 if (cfg->fc_nlflags & NLM_F_EXCL)
1240 goto out;
1242 /* We have 2 goals:
1243 * 1. Find exact match for type, scope, fib_info to avoid
1244 * duplicate routes
1245 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1247 fa_match = NULL;
1248 fa_first = fa;
1249 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1250 list_for_each_entry_continue(fa, fa_head, fa_list) {
1251 if (fa->fa_tos != tos)
1252 break;
1253 if (fa->fa_info->fib_priority != fi->fib_priority)
1254 break;
1255 if (fa->fa_type == cfg->fc_type &&
1256 fa->fa_info == fi) {
1257 fa_match = fa;
1258 break;
1262 if (cfg->fc_nlflags & NLM_F_REPLACE) {
1263 struct fib_info *fi_drop;
1264 u8 state;
1266 fa = fa_first;
1267 if (fa_match) {
1268 if (fa == fa_match)
1269 err = 0;
1270 goto out;
1272 err = -ENOBUFS;
1273 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1274 if (new_fa == NULL)
1275 goto out;
1277 fi_drop = fa->fa_info;
1278 new_fa->fa_tos = fa->fa_tos;
1279 new_fa->fa_info = fi;
1280 new_fa->fa_type = cfg->fc_type;
1281 state = fa->fa_state;
1282 new_fa->fa_state = state & ~FA_S_ACCESSED;
1284 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1285 alias_free_mem_rcu(fa);
1287 fib_release_info(fi_drop);
1288 if (state & FA_S_ACCESSED)
1289 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1290 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1291 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1293 goto succeeded;
1295 /* Error if we find a perfect match which
1296 * uses the same scope, type, and nexthop
1297 * information.
1299 if (fa_match)
1300 goto out;
1302 if (!(cfg->fc_nlflags & NLM_F_APPEND))
1303 fa = fa_first;
1305 err = -ENOENT;
1306 if (!(cfg->fc_nlflags & NLM_F_CREATE))
1307 goto out;
1309 err = -ENOBUFS;
1310 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1311 if (new_fa == NULL)
1312 goto out;
1314 new_fa->fa_info = fi;
1315 new_fa->fa_tos = tos;
1316 new_fa->fa_type = cfg->fc_type;
1317 new_fa->fa_state = 0;
1319 * Insert new entry to the list.
1322 if (!fa_head) {
1323 fa_head = fib_insert_node(t, key, plen);
1324 if (unlikely(!fa_head)) {
1325 err = -ENOMEM;
1326 goto out_free_new_fa;
1330 if (!plen)
1331 tb->tb_num_default++;
1333 list_add_tail_rcu(&new_fa->fa_list,
1334 (fa ? &fa->fa_list : fa_head));
1336 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1337 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1338 &cfg->fc_nlinfo, 0);
1339 succeeded:
1340 return 0;
1342 out_free_new_fa:
1343 kmem_cache_free(fn_alias_kmem, new_fa);
1344 out:
1345 fib_release_info(fi);
1346 err:
1347 return err;
1350 /* should be called with rcu_read_lock */
1351 static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
1352 t_key key, const struct flowi4 *flp,
1353 struct fib_result *res, int fib_flags)
1355 struct leaf_info *li;
1356 struct hlist_head *hhead = &l->list;
1357 struct hlist_node *node;
1359 hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1360 struct fib_alias *fa;
1361 int plen = li->plen;
1362 __be32 mask = inet_make_mask(plen);
1364 if (l->key != (key & ntohl(mask)))
1365 continue;
1367 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
1368 struct fib_info *fi = fa->fa_info;
1369 int nhsel, err;
1371 if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1372 continue;
1373 if (fa->fa_info->fib_scope < flp->flowi4_scope)
1374 continue;
1375 fib_alias_accessed(fa);
1376 err = fib_props[fa->fa_type].error;
1377 if (err) {
1378 #ifdef CONFIG_IP_FIB_TRIE_STATS
1379 t->stats.semantic_match_passed++;
1380 #endif
1381 return err;
1383 if (fi->fib_flags & RTNH_F_DEAD)
1384 continue;
1385 for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
1386 const struct fib_nh *nh = &fi->fib_nh[nhsel];
1388 if (nh->nh_flags & RTNH_F_DEAD)
1389 continue;
1390 if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
1391 continue;
1393 #ifdef CONFIG_IP_FIB_TRIE_STATS
1394 t->stats.semantic_match_passed++;
1395 #endif
1396 res->prefixlen = plen;
1397 res->nh_sel = nhsel;
1398 res->type = fa->fa_type;
1399 res->scope = fa->fa_info->fib_scope;
1400 res->fi = fi;
1401 res->table = tb;
1402 res->fa_head = &li->falh;
1403 if (!(fib_flags & FIB_LOOKUP_NOREF))
1404 atomic_inc(&res->fi->fib_clntref);
1405 return 0;
1409 #ifdef CONFIG_IP_FIB_TRIE_STATS
1410 t->stats.semantic_match_miss++;
1411 #endif
1414 return 1;
1417 int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
1418 struct fib_result *res, int fib_flags)
1420 struct trie *t = (struct trie *) tb->tb_data;
1421 int ret;
1422 struct rt_trie_node *n;
1423 struct tnode *pn;
1424 unsigned int pos, bits;
1425 t_key key = ntohl(flp->daddr);
1426 unsigned int chopped_off;
1427 t_key cindex = 0;
1428 unsigned int current_prefix_length = KEYLENGTH;
1429 struct tnode *cn;
1430 t_key pref_mismatch;
1432 rcu_read_lock();
1434 n = rcu_dereference(t->trie);
1435 if (!n)
1436 goto failed;
1438 #ifdef CONFIG_IP_FIB_TRIE_STATS
1439 t->stats.gets++;
1440 #endif
1442 /* Just a leaf? */
1443 if (IS_LEAF(n)) {
1444 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1445 goto found;
1448 pn = (struct tnode *) n;
1449 chopped_off = 0;
1451 while (pn) {
1452 pos = pn->pos;
1453 bits = pn->bits;
1455 if (!chopped_off)
1456 cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1457 pos, bits);
1459 n = tnode_get_child_rcu(pn, cindex);
1461 if (n == NULL) {
1462 #ifdef CONFIG_IP_FIB_TRIE_STATS
1463 t->stats.null_node_hit++;
1464 #endif
1465 goto backtrace;
1468 if (IS_LEAF(n)) {
1469 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1470 if (ret > 0)
1471 goto backtrace;
1472 goto found;
1475 cn = (struct tnode *)n;
1478 * It's a tnode, and we can do some extra checks here if we
1479 * like, to avoid descending into a dead-end branch.
1480 * This tnode is in the parent's child array at index
1481 * key[p_pos..p_pos+p_bits] but potentially with some bits
1482 * chopped off, so in reality the index may be just a
1483 * subprefix, padded with zero at the end.
1484 * We can also take a look at any skipped bits in this
1485 * tnode - everything up to p_pos is supposed to be ok,
1486 * and the non-chopped bits of the index (se previous
1487 * paragraph) are also guaranteed ok, but the rest is
1488 * considered unknown.
1490 * The skipped bits are key[pos+bits..cn->pos].
1493 /* If current_prefix_length < pos+bits, we are already doing
1494 * actual prefix matching, which means everything from
1495 * pos+(bits-chopped_off) onward must be zero along some
1496 * branch of this subtree - otherwise there is *no* valid
1497 * prefix present. Here we can only check the skipped
1498 * bits. Remember, since we have already indexed into the
1499 * parent's child array, we know that the bits we chopped of
1500 * *are* zero.
1503 /* NOTA BENE: Checking only skipped bits
1504 for the new node here */
1506 if (current_prefix_length < pos+bits) {
1507 if (tkey_extract_bits(cn->key, current_prefix_length,
1508 cn->pos - current_prefix_length)
1509 || !(cn->child[0]))
1510 goto backtrace;
1514 * If chopped_off=0, the index is fully validated and we
1515 * only need to look at the skipped bits for this, the new,
1516 * tnode. What we actually want to do is to find out if
1517 * these skipped bits match our key perfectly, or if we will
1518 * have to count on finding a matching prefix further down,
1519 * because if we do, we would like to have some way of
1520 * verifying the existence of such a prefix at this point.
1523 /* The only thing we can do at this point is to verify that
1524 * any such matching prefix can indeed be a prefix to our
1525 * key, and if the bits in the node we are inspecting that
1526 * do not match our key are not ZERO, this cannot be true.
1527 * Thus, find out where there is a mismatch (before cn->pos)
1528 * and verify that all the mismatching bits are zero in the
1529 * new tnode's key.
1533 * Note: We aren't very concerned about the piece of
1534 * the key that precede pn->pos+pn->bits, since these
1535 * have already been checked. The bits after cn->pos
1536 * aren't checked since these are by definition
1537 * "unknown" at this point. Thus, what we want to see
1538 * is if we are about to enter the "prefix matching"
1539 * state, and in that case verify that the skipped
1540 * bits that will prevail throughout this subtree are
1541 * zero, as they have to be if we are to find a
1542 * matching prefix.
1545 pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
1548 * In short: If skipped bits in this node do not match
1549 * the search key, enter the "prefix matching"
1550 * state.directly.
1552 if (pref_mismatch) {
1553 int mp = KEYLENGTH - fls(pref_mismatch);
1555 if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
1556 goto backtrace;
1558 if (current_prefix_length >= cn->pos)
1559 current_prefix_length = mp;
1562 pn = (struct tnode *)n; /* Descend */
1563 chopped_off = 0;
1564 continue;
1566 backtrace:
1567 chopped_off++;
1569 /* As zero don't change the child key (cindex) */
1570 while ((chopped_off <= pn->bits)
1571 && !(cindex & (1<<(chopped_off-1))))
1572 chopped_off++;
1574 /* Decrease current_... with bits chopped off */
1575 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1576 current_prefix_length = pn->pos + pn->bits
1577 - chopped_off;
1580 * Either we do the actual chop off according or if we have
1581 * chopped off all bits in this tnode walk up to our parent.
1584 if (chopped_off <= pn->bits) {
1585 cindex &= ~(1 << (chopped_off-1));
1586 } else {
1587 struct tnode *parent = node_parent_rcu((struct rt_trie_node *) pn);
1588 if (!parent)
1589 goto failed;
1591 /* Get Child's index */
1592 cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1593 pn = parent;
1594 chopped_off = 0;
1596 #ifdef CONFIG_IP_FIB_TRIE_STATS
1597 t->stats.backtrack++;
1598 #endif
1599 goto backtrace;
1602 failed:
1603 ret = 1;
1604 found:
1605 rcu_read_unlock();
1606 return ret;
1610 * Remove the leaf and return parent.
1612 static void trie_leaf_remove(struct trie *t, struct leaf *l)
1614 struct tnode *tp = node_parent((struct rt_trie_node *) l);
1616 pr_debug("entering trie_leaf_remove(%p)\n", l);
1618 if (tp) {
1619 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1620 put_child(t, (struct tnode *)tp, cindex, NULL);
1621 trie_rebalance(t, tp);
1622 } else
1623 rcu_assign_pointer(t->trie, NULL);
1625 free_leaf(l);
1629 * Caller must hold RTNL.
1631 int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
1633 struct trie *t = (struct trie *) tb->tb_data;
1634 u32 key, mask;
1635 int plen = cfg->fc_dst_len;
1636 u8 tos = cfg->fc_tos;
1637 struct fib_alias *fa, *fa_to_delete;
1638 struct list_head *fa_head;
1639 struct leaf *l;
1640 struct leaf_info *li;
1642 if (plen > 32)
1643 return -EINVAL;
1645 key = ntohl(cfg->fc_dst);
1646 mask = ntohl(inet_make_mask(plen));
1648 if (key & ~mask)
1649 return -EINVAL;
1651 key = key & mask;
1652 l = fib_find_node(t, key);
1654 if (!l)
1655 return -ESRCH;
1657 fa_head = get_fa_head(l, plen);
1658 fa = fib_find_alias(fa_head, tos, 0);
1660 if (!fa)
1661 return -ESRCH;
1663 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1665 fa_to_delete = NULL;
1666 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1667 list_for_each_entry_continue(fa, fa_head, fa_list) {
1668 struct fib_info *fi = fa->fa_info;
1670 if (fa->fa_tos != tos)
1671 break;
1673 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1674 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1675 fa->fa_info->fib_scope == cfg->fc_scope) &&
1676 (!cfg->fc_prefsrc ||
1677 fi->fib_prefsrc == cfg->fc_prefsrc) &&
1678 (!cfg->fc_protocol ||
1679 fi->fib_protocol == cfg->fc_protocol) &&
1680 fib_nh_match(cfg, fi) == 0) {
1681 fa_to_delete = fa;
1682 break;
1686 if (!fa_to_delete)
1687 return -ESRCH;
1689 fa = fa_to_delete;
1690 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1691 &cfg->fc_nlinfo, 0);
1693 l = fib_find_node(t, key);
1694 li = find_leaf_info(l, plen);
1696 list_del_rcu(&fa->fa_list);
1698 if (!plen)
1699 tb->tb_num_default--;
1701 if (list_empty(fa_head)) {
1702 hlist_del_rcu(&li->hlist);
1703 free_leaf_info(li);
1706 if (hlist_empty(&l->list))
1707 trie_leaf_remove(t, l);
1709 if (fa->fa_state & FA_S_ACCESSED)
1710 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1712 fib_release_info(fa->fa_info);
1713 alias_free_mem_rcu(fa);
1714 return 0;
1717 static int trie_flush_list(struct list_head *head)
1719 struct fib_alias *fa, *fa_node;
1720 int found = 0;
1722 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1723 struct fib_info *fi = fa->fa_info;
1725 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1726 list_del_rcu(&fa->fa_list);
1727 fib_release_info(fa->fa_info);
1728 alias_free_mem_rcu(fa);
1729 found++;
1732 return found;
1735 static int trie_flush_leaf(struct leaf *l)
1737 int found = 0;
1738 struct hlist_head *lih = &l->list;
1739 struct hlist_node *node, *tmp;
1740 struct leaf_info *li = NULL;
1742 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
1743 found += trie_flush_list(&li->falh);
1745 if (list_empty(&li->falh)) {
1746 hlist_del_rcu(&li->hlist);
1747 free_leaf_info(li);
1750 return found;
1754 * Scan for the next right leaf starting at node p->child[idx]
1755 * Since we have back pointer, no recursion necessary.
1757 static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1759 do {
1760 t_key idx;
1762 if (c)
1763 idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1764 else
1765 idx = 0;
1767 while (idx < 1u << p->bits) {
1768 c = tnode_get_child_rcu(p, idx++);
1769 if (!c)
1770 continue;
1772 if (IS_LEAF(c)) {
1773 prefetch(rcu_dereference_rtnl(p->child[idx]));
1774 return (struct leaf *) c;
1777 /* Rescan start scanning in new node */
1778 p = (struct tnode *) c;
1779 idx = 0;
1782 /* Node empty, walk back up to parent */
1783 c = (struct rt_trie_node *) p;
1784 } while ((p = node_parent_rcu(c)) != NULL);
1786 return NULL; /* Root of trie */
1789 static struct leaf *trie_firstleaf(struct trie *t)
1791 struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
1793 if (!n)
1794 return NULL;
1796 if (IS_LEAF(n)) /* trie is just a leaf */
1797 return (struct leaf *) n;
1799 return leaf_walk_rcu(n, NULL);
1802 static struct leaf *trie_nextleaf(struct leaf *l)
1804 struct rt_trie_node *c = (struct rt_trie_node *) l;
1805 struct tnode *p = node_parent_rcu(c);
1807 if (!p)
1808 return NULL; /* trie with just one leaf */
1810 return leaf_walk_rcu(p, c);
1813 static struct leaf *trie_leafindex(struct trie *t, int index)
1815 struct leaf *l = trie_firstleaf(t);
1817 while (l && index-- > 0)
1818 l = trie_nextleaf(l);
1820 return l;
1825 * Caller must hold RTNL.
1827 int fib_table_flush(struct fib_table *tb)
1829 struct trie *t = (struct trie *) tb->tb_data;
1830 struct leaf *l, *ll = NULL;
1831 int found = 0;
1833 for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1834 found += trie_flush_leaf(l);
1836 if (ll && hlist_empty(&ll->list))
1837 trie_leaf_remove(t, ll);
1838 ll = l;
1841 if (ll && hlist_empty(&ll->list))
1842 trie_leaf_remove(t, ll);
1844 pr_debug("trie_flush found=%d\n", found);
1845 return found;
1848 void fib_free_table(struct fib_table *tb)
1850 kfree(tb);
1853 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1854 struct fib_table *tb,
1855 struct sk_buff *skb, struct netlink_callback *cb)
1857 int i, s_i;
1858 struct fib_alias *fa;
1859 __be32 xkey = htonl(key);
1861 s_i = cb->args[5];
1862 i = 0;
1864 /* rcu_read_lock is hold by caller */
1866 list_for_each_entry_rcu(fa, fah, fa_list) {
1867 if (i < s_i) {
1868 i++;
1869 continue;
1872 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1873 cb->nlh->nlmsg_seq,
1874 RTM_NEWROUTE,
1875 tb->tb_id,
1876 fa->fa_type,
1877 xkey,
1878 plen,
1879 fa->fa_tos,
1880 fa->fa_info, NLM_F_MULTI) < 0) {
1881 cb->args[5] = i;
1882 return -1;
1884 i++;
1886 cb->args[5] = i;
1887 return skb->len;
1890 static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1891 struct sk_buff *skb, struct netlink_callback *cb)
1893 struct leaf_info *li;
1894 struct hlist_node *node;
1895 int i, s_i;
1897 s_i = cb->args[4];
1898 i = 0;
1900 /* rcu_read_lock is hold by caller */
1901 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
1902 if (i < s_i) {
1903 i++;
1904 continue;
1907 if (i > s_i)
1908 cb->args[5] = 0;
1910 if (list_empty(&li->falh))
1911 continue;
1913 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1914 cb->args[4] = i;
1915 return -1;
1917 i++;
1920 cb->args[4] = i;
1921 return skb->len;
1924 int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
1925 struct netlink_callback *cb)
1927 struct leaf *l;
1928 struct trie *t = (struct trie *) tb->tb_data;
1929 t_key key = cb->args[2];
1930 int count = cb->args[3];
1932 rcu_read_lock();
1933 /* Dump starting at last key.
1934 * Note: 0.0.0.0/0 (ie default) is first key.
1936 if (count == 0)
1937 l = trie_firstleaf(t);
1938 else {
1939 /* Normally, continue from last key, but if that is missing
1940 * fallback to using slow rescan
1942 l = fib_find_node(t, key);
1943 if (!l)
1944 l = trie_leafindex(t, count);
1947 while (l) {
1948 cb->args[2] = l->key;
1949 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1950 cb->args[3] = count;
1951 rcu_read_unlock();
1952 return -1;
1955 ++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;
1961 rcu_read_unlock();
1963 return skb->len;
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;
1982 struct trie *t;
1984 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1985 GFP_KERNEL);
1986 if (tb == NULL)
1987 return NULL;
1989 tb->tb_id = id;
1990 tb->tb_default = -1;
1991 tb->tb_num_default = 0;
1993 t = (struct trie *) tb->tb_data;
1994 memset(t, 0, sizeof(*t));
1996 return tb;
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;
2005 unsigned int index;
2006 unsigned int depth;
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;
2013 struct tnode *p;
2015 /* A single entry routing table */
2016 if (!tn)
2017 return NULL;
2019 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2020 iter->tnode, iter->index, iter->depth);
2021 rescan:
2022 while (cindex < (1<<tn->bits)) {
2023 struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
2025 if (n) {
2026 if (IS_LEAF(n)) {
2027 iter->tnode = tn;
2028 iter->index = cindex + 1;
2029 } else {
2030 /* push down one level */
2031 iter->tnode = (struct tnode *) n;
2032 iter->index = 0;
2033 ++iter->depth;
2035 return n;
2038 ++cindex;
2041 /* Current node exhausted, pop back up */
2042 p = node_parent_rcu((struct rt_trie_node *)tn);
2043 if (p) {
2044 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2045 tn = p;
2046 --iter->depth;
2047 goto rescan;
2050 /* got root? */
2051 return NULL;
2054 static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
2055 struct trie *t)
2057 struct rt_trie_node *n;
2059 if (!t)
2060 return NULL;
2062 n = rcu_dereference(t->trie);
2063 if (!n)
2064 return NULL;
2066 if (IS_TNODE(n)) {
2067 iter->tnode = (struct tnode *) n;
2068 iter->index = 0;
2069 iter->depth = 1;
2070 } else {
2071 iter->tnode = NULL;
2072 iter->index = 0;
2073 iter->depth = 0;
2076 return 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));
2086 rcu_read_lock();
2087 for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2088 if (IS_LEAF(n)) {
2089 struct leaf *l = (struct leaf *)n;
2090 struct leaf_info *li;
2091 struct hlist_node *tmp;
2093 s->leaves++;
2094 s->totdepth += iter.depth;
2095 if (iter.depth > s->maxdepth)
2096 s->maxdepth = iter.depth;
2098 hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
2099 ++s->prefixes;
2100 } else {
2101 const struct tnode *tn = (const struct tnode *) n;
2102 int i;
2104 s->tnodes++;
2105 if (tn->bits < MAX_STAT_DEPTH)
2106 s->nodesizes[tn->bits]++;
2108 for (i = 0; i < (1<<tn->bits); i++)
2109 if (!tn->child[i])
2110 s->nullpointers++;
2113 rcu_read_unlock();
2117 * This outputs /proc/net/fib_triestats
2119 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2121 unsigned int i, max, pointers, bytes, avdepth;
2123 if (stat->leaves)
2124 avdepth = stat->totdepth*100 / stat->leaves;
2125 else
2126 avdepth = 0;
2128 seq_printf(seq, "\tAver depth: %u.%02d\n",
2129 avdepth / 100, avdepth % 100);
2130 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
2132 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
2133 bytes = sizeof(struct leaf) * stat->leaves;
2135 seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes);
2136 bytes += sizeof(struct leaf_info) * stat->prefixes;
2138 seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2139 bytes += sizeof(struct tnode) * stat->tnodes;
2141 max = MAX_STAT_DEPTH;
2142 while (max > 0 && stat->nodesizes[max-1] == 0)
2143 max--;
2145 pointers = 0;
2146 for (i = 1; i <= max; i++)
2147 if (stat->nodesizes[i] != 0) {
2148 seq_printf(seq, " %u: %u", i, stat->nodesizes[i]);
2149 pointers += (1<<i) * stat->nodesizes[i];
2151 seq_putc(seq, '\n');
2152 seq_printf(seq, "\tPointers: %u\n", pointers);
2154 bytes += sizeof(struct rt_trie_node *) * pointers;
2155 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2156 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
2159 #ifdef CONFIG_IP_FIB_TRIE_STATS
2160 static void trie_show_usage(struct seq_file *seq,
2161 const struct trie_use_stats *stats)
2163 seq_printf(seq, "\nCounters:\n---------\n");
2164 seq_printf(seq, "gets = %u\n", stats->gets);
2165 seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2166 seq_printf(seq, "semantic match passed = %u\n",
2167 stats->semantic_match_passed);
2168 seq_printf(seq, "semantic match miss = %u\n",
2169 stats->semantic_match_miss);
2170 seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2171 seq_printf(seq, "skipped node resize = %u\n\n",
2172 stats->resize_node_skipped);
2174 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2176 static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2178 if (tb->tb_id == RT_TABLE_LOCAL)
2179 seq_puts(seq, "Local:\n");
2180 else if (tb->tb_id == RT_TABLE_MAIN)
2181 seq_puts(seq, "Main:\n");
2182 else
2183 seq_printf(seq, "Id %d:\n", tb->tb_id);
2187 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2189 struct net *net = (struct net *)seq->private;
2190 unsigned int h;
2192 seq_printf(seq,
2193 "Basic info: size of leaf:"
2194 " %Zd bytes, size of tnode: %Zd bytes.\n",
2195 sizeof(struct leaf), sizeof(struct tnode));
2197 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2198 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2199 struct hlist_node *node;
2200 struct fib_table *tb;
2202 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2203 struct trie *t = (struct trie *) tb->tb_data;
2204 struct trie_stat stat;
2206 if (!t)
2207 continue;
2209 fib_table_print(seq, tb);
2211 trie_collect_stats(t, &stat);
2212 trie_show_stats(seq, &stat);
2213 #ifdef CONFIG_IP_FIB_TRIE_STATS
2214 trie_show_usage(seq, &t->stats);
2215 #endif
2219 return 0;
2222 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2224 return single_open_net(inode, file, fib_triestat_seq_show);
2227 static const struct file_operations fib_triestat_fops = {
2228 .owner = THIS_MODULE,
2229 .open = fib_triestat_seq_open,
2230 .read = seq_read,
2231 .llseek = seq_lseek,
2232 .release = single_release_net,
2235 static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2237 struct fib_trie_iter *iter = seq->private;
2238 struct net *net = seq_file_net(seq);
2239 loff_t idx = 0;
2240 unsigned int h;
2242 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2243 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2244 struct hlist_node *node;
2245 struct fib_table *tb;
2247 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2248 struct rt_trie_node *n;
2250 for (n = fib_trie_get_first(iter,
2251 (struct trie *) tb->tb_data);
2252 n; n = fib_trie_get_next(iter))
2253 if (pos == idx++) {
2254 iter->tb = tb;
2255 return n;
2260 return NULL;
2263 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2264 __acquires(RCU)
2266 rcu_read_lock();
2267 return fib_trie_get_idx(seq, *pos);
2270 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2272 struct fib_trie_iter *iter = seq->private;
2273 struct net *net = seq_file_net(seq);
2274 struct fib_table *tb = iter->tb;
2275 struct hlist_node *tb_node;
2276 unsigned int h;
2277 struct rt_trie_node *n;
2279 ++*pos;
2280 /* next node in same table */
2281 n = fib_trie_get_next(iter);
2282 if (n)
2283 return n;
2285 /* walk rest of this hash chain */
2286 h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2287 while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2288 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2289 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2290 if (n)
2291 goto found;
2294 /* new hash chain */
2295 while (++h < FIB_TABLE_HASHSZ) {
2296 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2297 hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) {
2298 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2299 if (n)
2300 goto found;
2303 return NULL;
2305 found:
2306 iter->tb = tb;
2307 return n;
2310 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2311 __releases(RCU)
2313 rcu_read_unlock();
2316 static void seq_indent(struct seq_file *seq, int n)
2318 while (n-- > 0)
2319 seq_puts(seq, " ");
2322 static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2324 switch (s) {
2325 case RT_SCOPE_UNIVERSE: return "universe";
2326 case RT_SCOPE_SITE: return "site";
2327 case RT_SCOPE_LINK: return "link";
2328 case RT_SCOPE_HOST: return "host";
2329 case RT_SCOPE_NOWHERE: return "nowhere";
2330 default:
2331 snprintf(buf, len, "scope=%d", s);
2332 return buf;
2336 static const char *const rtn_type_names[__RTN_MAX] = {
2337 [RTN_UNSPEC] = "UNSPEC",
2338 [RTN_UNICAST] = "UNICAST",
2339 [RTN_LOCAL] = "LOCAL",
2340 [RTN_BROADCAST] = "BROADCAST",
2341 [RTN_ANYCAST] = "ANYCAST",
2342 [RTN_MULTICAST] = "MULTICAST",
2343 [RTN_BLACKHOLE] = "BLACKHOLE",
2344 [RTN_UNREACHABLE] = "UNREACHABLE",
2345 [RTN_PROHIBIT] = "PROHIBIT",
2346 [RTN_THROW] = "THROW",
2347 [RTN_NAT] = "NAT",
2348 [RTN_XRESOLVE] = "XRESOLVE",
2351 static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2353 if (t < __RTN_MAX && rtn_type_names[t])
2354 return rtn_type_names[t];
2355 snprintf(buf, len, "type %u", t);
2356 return buf;
2359 /* Pretty print the trie */
2360 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2362 const struct fib_trie_iter *iter = seq->private;
2363 struct rt_trie_node *n = v;
2365 if (!node_parent_rcu(n))
2366 fib_table_print(seq, iter->tb);
2368 if (IS_TNODE(n)) {
2369 struct tnode *tn = (struct tnode *) n;
2370 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2372 seq_indent(seq, iter->depth-1);
2373 seq_printf(seq, " +-- %pI4/%d %d %d %d\n",
2374 &prf, tn->pos, tn->bits, tn->full_children,
2375 tn->empty_children);
2377 } else {
2378 struct leaf *l = (struct leaf *) n;
2379 struct leaf_info *li;
2380 struct hlist_node *node;
2381 __be32 val = htonl(l->key);
2383 seq_indent(seq, iter->depth);
2384 seq_printf(seq, " |-- %pI4\n", &val);
2386 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2387 struct fib_alias *fa;
2389 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2390 char buf1[32], buf2[32];
2392 seq_indent(seq, iter->depth+1);
2393 seq_printf(seq, " /%d %s %s", li->plen,
2394 rtn_scope(buf1, sizeof(buf1),
2395 fa->fa_info->fib_scope),
2396 rtn_type(buf2, sizeof(buf2),
2397 fa->fa_type));
2398 if (fa->fa_tos)
2399 seq_printf(seq, " tos=%d", fa->fa_tos);
2400 seq_putc(seq, '\n');
2405 return 0;
2408 static const struct seq_operations fib_trie_seq_ops = {
2409 .start = fib_trie_seq_start,
2410 .next = fib_trie_seq_next,
2411 .stop = fib_trie_seq_stop,
2412 .show = fib_trie_seq_show,
2415 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2417 return seq_open_net(inode, file, &fib_trie_seq_ops,
2418 sizeof(struct fib_trie_iter));
2421 static const struct file_operations fib_trie_fops = {
2422 .owner = THIS_MODULE,
2423 .open = fib_trie_seq_open,
2424 .read = seq_read,
2425 .llseek = seq_lseek,
2426 .release = seq_release_net,
2429 struct fib_route_iter {
2430 struct seq_net_private p;
2431 struct trie *main_trie;
2432 loff_t pos;
2433 t_key key;
2436 static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2438 struct leaf *l = NULL;
2439 struct trie *t = iter->main_trie;
2441 /* use cache location of last found key */
2442 if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2443 pos -= iter->pos;
2444 else {
2445 iter->pos = 0;
2446 l = trie_firstleaf(t);
2449 while (l && pos-- > 0) {
2450 iter->pos++;
2451 l = trie_nextleaf(l);
2454 if (l)
2455 iter->key = pos; /* remember it */
2456 else
2457 iter->pos = 0; /* forget it */
2459 return l;
2462 static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2463 __acquires(RCU)
2465 struct fib_route_iter *iter = seq->private;
2466 struct fib_table *tb;
2468 rcu_read_lock();
2469 tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2470 if (!tb)
2471 return NULL;
2473 iter->main_trie = (struct trie *) tb->tb_data;
2474 if (*pos == 0)
2475 return SEQ_START_TOKEN;
2476 else
2477 return fib_route_get_idx(iter, *pos - 1);
2480 static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2482 struct fib_route_iter *iter = seq->private;
2483 struct leaf *l = v;
2485 ++*pos;
2486 if (v == SEQ_START_TOKEN) {
2487 iter->pos = 0;
2488 l = trie_firstleaf(iter->main_trie);
2489 } else {
2490 iter->pos++;
2491 l = trie_nextleaf(l);
2494 if (l)
2495 iter->key = l->key;
2496 else
2497 iter->pos = 0;
2498 return l;
2501 static void fib_route_seq_stop(struct seq_file *seq, void *v)
2502 __releases(RCU)
2504 rcu_read_unlock();
2507 static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2509 unsigned int flags = 0;
2511 if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
2512 flags = RTF_REJECT;
2513 if (fi && fi->fib_nh->nh_gw)
2514 flags |= RTF_GATEWAY;
2515 if (mask == htonl(0xFFFFFFFF))
2516 flags |= RTF_HOST;
2517 flags |= RTF_UP;
2518 return flags;
2522 * This outputs /proc/net/route.
2523 * The format of the file is not supposed to be changed
2524 * and needs to be same as fib_hash output to avoid breaking
2525 * legacy utilities
2527 static int fib_route_seq_show(struct seq_file *seq, void *v)
2529 struct leaf *l = v;
2530 struct leaf_info *li;
2531 struct hlist_node *node;
2533 if (v == SEQ_START_TOKEN) {
2534 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2535 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2536 "\tWindow\tIRTT");
2537 return 0;
2540 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2541 struct fib_alias *fa;
2542 __be32 mask, prefix;
2544 mask = inet_make_mask(li->plen);
2545 prefix = htonl(l->key);
2547 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2548 const struct fib_info *fi = fa->fa_info;
2549 unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2550 int len;
2552 if (fa->fa_type == RTN_BROADCAST
2553 || fa->fa_type == RTN_MULTICAST)
2554 continue;
2556 if (fi)
2557 seq_printf(seq,
2558 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2559 "%d\t%08X\t%d\t%u\t%u%n",
2560 fi->fib_dev ? fi->fib_dev->name : "*",
2561 prefix,
2562 fi->fib_nh->nh_gw, flags, 0, 0,
2563 fi->fib_priority,
2564 mask,
2565 (fi->fib_advmss ?
2566 fi->fib_advmss + 40 : 0),
2567 fi->fib_window,
2568 fi->fib_rtt >> 3, &len);
2569 else
2570 seq_printf(seq,
2571 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2572 "%d\t%08X\t%d\t%u\t%u%n",
2573 prefix, 0, flags, 0, 0, 0,
2574 mask, 0, 0, 0, &len);
2576 seq_printf(seq, "%*s\n", 127 - len, "");
2580 return 0;
2583 static const struct seq_operations fib_route_seq_ops = {
2584 .start = fib_route_seq_start,
2585 .next = fib_route_seq_next,
2586 .stop = fib_route_seq_stop,
2587 .show = fib_route_seq_show,
2590 static int fib_route_seq_open(struct inode *inode, struct file *file)
2592 return seq_open_net(inode, file, &fib_route_seq_ops,
2593 sizeof(struct fib_route_iter));
2596 static const struct file_operations fib_route_fops = {
2597 .owner = THIS_MODULE,
2598 .open = fib_route_seq_open,
2599 .read = seq_read,
2600 .llseek = seq_lseek,
2601 .release = seq_release_net,
2604 int __net_init fib_proc_init(struct net *net)
2606 if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
2607 goto out1;
2609 if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
2610 &fib_triestat_fops))
2611 goto out2;
2613 if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
2614 goto out3;
2616 return 0;
2618 out3:
2619 proc_net_remove(net, "fib_triestat");
2620 out2:
2621 proc_net_remove(net, "fib_trie");
2622 out1:
2623 return -ENOMEM;
2626 void __net_exit fib_proc_exit(struct net *net)
2628 proc_net_remove(net, "fib_trie");
2629 proc_net_remove(net, "fib_triestat");
2630 proc_net_remove(net, "route");
2633 #endif /* CONFIG_PROC_FS */