xref: /openbmc/linux/net/ipv4/fib_trie.c (revision 6774def6)
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.
6  *
7  *   Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
8  *     & Swedish University of Agricultural Sciences.
9  *
10  *   Jens Laas <jens.laas@data.slu.se> Swedish University of
11  *     Agricultural Sciences.
12  *
13  *   Hans Liss <hans.liss@its.uu.se>  Uppsala Universitet
14  *
15  * This work is based on the LPC-trie which is originally described in:
16  *
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/
20  *
21  *
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
24  *
25  *
26  * Code from fib_hash has been reused which includes the following header:
27  *
28  *
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.
32  *
33  *		IPv4 FIB: lookup engine and maintenance routines.
34  *
35  *
36  * Authors:	Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
37  *
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.
42  *
43  * Substantial contributions to this work comes from:
44  *
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>
49  */
50 
51 #define VERSION "0.409"
52 
53 #include <asm/uaccess.h>
54 #include <linux/bitops.h>
55 #include <linux/types.h>
56 #include <linux/kernel.h>
57 #include <linux/mm.h>
58 #include <linux/string.h>
59 #include <linux/socket.h>
60 #include <linux/sockios.h>
61 #include <linux/errno.h>
62 #include <linux/in.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/export.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"
83 
84 #define MAX_STAT_DEPTH 32
85 
86 #define KEYLENGTH (8*sizeof(t_key))
87 
88 typedef unsigned int t_key;
89 
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)
94 
95 #define IS_TNODE(n) (!(n->parent & T_LEAF))
96 #define IS_LEAF(n) (n->parent & T_LEAF)
97 
98 struct rt_trie_node {
99 	unsigned long parent;
100 	t_key key;
101 };
102 
103 struct leaf {
104 	unsigned long parent;
105 	t_key key;
106 	struct hlist_head list;
107 	struct rcu_head rcu;
108 };
109 
110 struct leaf_info {
111 	struct hlist_node hlist;
112 	int plen;
113 	u32 mask_plen; /* ntohl(inet_make_mask(plen)) */
114 	struct list_head falh;
115 	struct rcu_head rcu;
116 };
117 
118 struct tnode {
119 	unsigned long parent;
120 	t_key key;
121 	unsigned char pos;		/* 2log(KEYLENGTH) bits needed */
122 	unsigned char bits;		/* 2log(KEYLENGTH) bits needed */
123 	unsigned int full_children;	/* KEYLENGTH bits needed */
124 	unsigned int empty_children;	/* KEYLENGTH bits needed */
125 	union {
126 		struct rcu_head rcu;
127 		struct tnode *tnode_free;
128 	};
129 	struct rt_trie_node __rcu *child[0];
130 };
131 
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;
140 };
141 #endif
142 
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];
151 };
152 
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
158 };
159 
160 static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
161 				  int wasfull);
162 static struct rt_trie_node *resize(struct trie *t, struct tnode *tn);
163 static struct tnode *inflate(struct trie *t, struct tnode *tn);
164 static struct tnode *halve(struct trie *t, struct tnode *tn);
165 /* tnodes to free after resize(); protected by RTNL */
166 static struct tnode *tnode_free_head;
167 static size_t tnode_free_size;
168 
169 /*
170  * synchronize_rcu after call_rcu for that many pages; it should be especially
171  * useful before resizing the root node with PREEMPT_NONE configs; the value was
172  * obtained experimentally, aiming to avoid visible slowdown.
173  */
174 static const int sync_pages = 128;
175 
176 static struct kmem_cache *fn_alias_kmem __read_mostly;
177 static struct kmem_cache *trie_leaf_kmem __read_mostly;
178 
179 /*
180  * caller must hold RTNL
181  */
182 static inline struct tnode *node_parent(const struct rt_trie_node *node)
183 {
184 	unsigned long parent;
185 
186 	parent = rcu_dereference_index_check(node->parent, lockdep_rtnl_is_held());
187 
188 	return (struct tnode *)(parent & ~NODE_TYPE_MASK);
189 }
190 
191 /*
192  * caller must hold RCU read lock or RTNL
193  */
194 static inline struct tnode *node_parent_rcu(const struct rt_trie_node *node)
195 {
196 	unsigned long parent;
197 
198 	parent = rcu_dereference_index_check(node->parent, rcu_read_lock_held() ||
199 							   lockdep_rtnl_is_held());
200 
201 	return (struct tnode *)(parent & ~NODE_TYPE_MASK);
202 }
203 
204 /* Same as rcu_assign_pointer
205  * but that macro() assumes that value is a pointer.
206  */
207 static inline void node_set_parent(struct rt_trie_node *node, struct tnode *ptr)
208 {
209 	smp_wmb();
210 	node->parent = (unsigned long)ptr | NODE_TYPE(node);
211 }
212 
213 /*
214  * caller must hold RTNL
215  */
216 static inline struct rt_trie_node *tnode_get_child(const struct tnode *tn, unsigned int i)
217 {
218 	BUG_ON(i >= 1U << tn->bits);
219 
220 	return rtnl_dereference(tn->child[i]);
221 }
222 
223 /*
224  * caller must hold RCU read lock or RTNL
225  */
226 static inline struct rt_trie_node *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
227 {
228 	BUG_ON(i >= 1U << tn->bits);
229 
230 	return rcu_dereference_rtnl(tn->child[i]);
231 }
232 
233 static inline int tnode_child_length(const struct tnode *tn)
234 {
235 	return 1 << tn->bits;
236 }
237 
238 static inline t_key mask_pfx(t_key k, unsigned int l)
239 {
240 	return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
241 }
242 
243 static inline t_key tkey_extract_bits(t_key a, unsigned int offset, unsigned int bits)
244 {
245 	if (offset < KEYLENGTH)
246 		return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
247 	else
248 		return 0;
249 }
250 
251 static inline int tkey_equals(t_key a, t_key b)
252 {
253 	return a == b;
254 }
255 
256 static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
257 {
258 	if (bits == 0 || offset >= KEYLENGTH)
259 		return 1;
260 	bits = bits > KEYLENGTH ? KEYLENGTH : bits;
261 	return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
262 }
263 
264 static inline int tkey_mismatch(t_key a, int offset, t_key b)
265 {
266 	t_key diff = a ^ b;
267 	int i = offset;
268 
269 	if (!diff)
270 		return 0;
271 	while ((diff << i) >> (KEYLENGTH-1) == 0)
272 		i++;
273 	return i;
274 }
275 
276 /*
277   To understand this stuff, an understanding of keys and all their bits is
278   necessary. Every node in the trie has a key associated with it, but not
279   all of the bits in that key are significant.
280 
281   Consider a node 'n' and its parent 'tp'.
282 
283   If n is a leaf, every bit in its key is significant. Its presence is
284   necessitated by path compression, since during a tree traversal (when
285   searching for a leaf - unless we are doing an insertion) we will completely
286   ignore all skipped bits we encounter. Thus we need to verify, at the end of
287   a potentially successful search, that we have indeed been walking the
288   correct key path.
289 
290   Note that we can never "miss" the correct key in the tree if present by
291   following the wrong path. Path compression ensures that segments of the key
292   that are the same for all keys with a given prefix are skipped, but the
293   skipped part *is* identical for each node in the subtrie below the skipped
294   bit! trie_insert() in this implementation takes care of that - note the
295   call to tkey_sub_equals() in trie_insert().
296 
297   if n is an internal node - a 'tnode' here, the various parts of its key
298   have many different meanings.
299 
300   Example:
301   _________________________________________________________________
302   | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
303   -----------------------------------------------------------------
304     0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
305 
306   _________________________________________________________________
307   | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
308   -----------------------------------------------------------------
309    16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31
310 
311   tp->pos = 7
312   tp->bits = 3
313   n->pos = 15
314   n->bits = 4
315 
316   First, let's just ignore the bits that come before the parent tp, that is
317   the bits from 0 to (tp->pos-1). They are *known* but at this point we do
318   not use them for anything.
319 
320   The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
321   index into the parent's child array. That is, they will be used to find
322   'n' among tp's children.
323 
324   The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
325   for the node n.
326 
327   All the bits we have seen so far are significant to the node n. The rest
328   of the bits are really not needed or indeed known in n->key.
329 
330   The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
331   n's child array, and will of course be different for each child.
332 
333 
334   The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
335   at this point.
336 
337 */
338 
339 static inline void check_tnode(const struct tnode *tn)
340 {
341 	WARN_ON(tn && tn->pos+tn->bits > 32);
342 }
343 
344 static const int halve_threshold = 25;
345 static const int inflate_threshold = 50;
346 static const int halve_threshold_root = 15;
347 static const int inflate_threshold_root = 30;
348 
349 static void __alias_free_mem(struct rcu_head *head)
350 {
351 	struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
352 	kmem_cache_free(fn_alias_kmem, fa);
353 }
354 
355 static inline void alias_free_mem_rcu(struct fib_alias *fa)
356 {
357 	call_rcu(&fa->rcu, __alias_free_mem);
358 }
359 
360 static void __leaf_free_rcu(struct rcu_head *head)
361 {
362 	struct leaf *l = container_of(head, struct leaf, rcu);
363 	kmem_cache_free(trie_leaf_kmem, l);
364 }
365 
366 static inline void free_leaf(struct leaf *l)
367 {
368 	call_rcu(&l->rcu, __leaf_free_rcu);
369 }
370 
371 static inline void free_leaf_info(struct leaf_info *leaf)
372 {
373 	kfree_rcu(leaf, rcu);
374 }
375 
376 static struct tnode *tnode_alloc(size_t size)
377 {
378 	if (size <= PAGE_SIZE)
379 		return kzalloc(size, GFP_KERNEL);
380 	else
381 		return vzalloc(size);
382 }
383 
384 static void __tnode_free_rcu(struct rcu_head *head)
385 {
386 	struct tnode *tn = container_of(head, struct tnode, rcu);
387 	size_t size = sizeof(struct tnode) +
388 		      (sizeof(struct rt_trie_node *) << tn->bits);
389 
390 	if (size <= PAGE_SIZE)
391 		kfree(tn);
392 	else
393 		vfree(tn);
394 }
395 
396 static inline void tnode_free(struct tnode *tn)
397 {
398 	if (IS_LEAF(tn))
399 		free_leaf((struct leaf *) tn);
400 	else
401 		call_rcu(&tn->rcu, __tnode_free_rcu);
402 }
403 
404 static void tnode_free_safe(struct tnode *tn)
405 {
406 	BUG_ON(IS_LEAF(tn));
407 	tn->tnode_free = tnode_free_head;
408 	tnode_free_head = tn;
409 	tnode_free_size += sizeof(struct tnode) +
410 			   (sizeof(struct rt_trie_node *) << tn->bits);
411 }
412 
413 static void tnode_free_flush(void)
414 {
415 	struct tnode *tn;
416 
417 	while ((tn = tnode_free_head)) {
418 		tnode_free_head = tn->tnode_free;
419 		tn->tnode_free = NULL;
420 		tnode_free(tn);
421 	}
422 
423 	if (tnode_free_size >= PAGE_SIZE * sync_pages) {
424 		tnode_free_size = 0;
425 		synchronize_rcu();
426 	}
427 }
428 
429 static struct leaf *leaf_new(void)
430 {
431 	struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
432 	if (l) {
433 		l->parent = T_LEAF;
434 		INIT_HLIST_HEAD(&l->list);
435 	}
436 	return l;
437 }
438 
439 static struct leaf_info *leaf_info_new(int plen)
440 {
441 	struct leaf_info *li = kmalloc(sizeof(struct leaf_info),  GFP_KERNEL);
442 	if (li) {
443 		li->plen = plen;
444 		li->mask_plen = ntohl(inet_make_mask(plen));
445 		INIT_LIST_HEAD(&li->falh);
446 	}
447 	return li;
448 }
449 
450 static struct tnode *tnode_new(t_key key, int pos, int bits)
451 {
452 	size_t sz = sizeof(struct tnode) + (sizeof(struct rt_trie_node *) << bits);
453 	struct tnode *tn = tnode_alloc(sz);
454 
455 	if (tn) {
456 		tn->parent = T_TNODE;
457 		tn->pos = pos;
458 		tn->bits = bits;
459 		tn->key = key;
460 		tn->full_children = 0;
461 		tn->empty_children = 1<<bits;
462 	}
463 
464 	pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode),
465 		 sizeof(struct rt_trie_node *) << bits);
466 	return tn;
467 }
468 
469 /*
470  * Check whether a tnode 'n' is "full", i.e. it is an internal node
471  * and no bits are skipped. See discussion in dyntree paper p. 6
472  */
473 
474 static inline int tnode_full(const struct tnode *tn, const struct rt_trie_node *n)
475 {
476 	if (n == NULL || IS_LEAF(n))
477 		return 0;
478 
479 	return ((struct tnode *) n)->pos == tn->pos + tn->bits;
480 }
481 
482 static inline void put_child(struct tnode *tn, int i,
483 			     struct rt_trie_node *n)
484 {
485 	tnode_put_child_reorg(tn, i, n, -1);
486 }
487 
488  /*
489   * Add a child at position i overwriting the old value.
490   * Update the value of full_children and empty_children.
491   */
492 
493 static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
494 				  int wasfull)
495 {
496 	struct rt_trie_node *chi = rtnl_dereference(tn->child[i]);
497 	int isfull;
498 
499 	BUG_ON(i >= 1<<tn->bits);
500 
501 	/* update emptyChildren */
502 	if (n == NULL && chi != NULL)
503 		tn->empty_children++;
504 	else if (n != NULL && chi == NULL)
505 		tn->empty_children--;
506 
507 	/* update fullChildren */
508 	if (wasfull == -1)
509 		wasfull = tnode_full(tn, chi);
510 
511 	isfull = tnode_full(tn, n);
512 	if (wasfull && !isfull)
513 		tn->full_children--;
514 	else if (!wasfull && isfull)
515 		tn->full_children++;
516 
517 	if (n)
518 		node_set_parent(n, tn);
519 
520 	rcu_assign_pointer(tn->child[i], n);
521 }
522 
523 #define MAX_WORK 10
524 static struct rt_trie_node *resize(struct trie *t, struct tnode *tn)
525 {
526 	int i;
527 	struct tnode *old_tn;
528 	int inflate_threshold_use;
529 	int halve_threshold_use;
530 	int max_work;
531 
532 	if (!tn)
533 		return NULL;
534 
535 	pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
536 		 tn, inflate_threshold, halve_threshold);
537 
538 	/* No children */
539 	if (tn->empty_children == tnode_child_length(tn)) {
540 		tnode_free_safe(tn);
541 		return NULL;
542 	}
543 	/* One child */
544 	if (tn->empty_children == tnode_child_length(tn) - 1)
545 		goto one_child;
546 	/*
547 	 * Double as long as the resulting node has a number of
548 	 * nonempty nodes that are above the threshold.
549 	 */
550 
551 	/*
552 	 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
553 	 * the Helsinki University of Technology and Matti Tikkanen of Nokia
554 	 * Telecommunications, page 6:
555 	 * "A node is doubled if the ratio of non-empty children to all
556 	 * children in the *doubled* node is at least 'high'."
557 	 *
558 	 * 'high' in this instance is the variable 'inflate_threshold'. It
559 	 * is expressed as a percentage, so we multiply it with
560 	 * tnode_child_length() and instead of multiplying by 2 (since the
561 	 * child array will be doubled by inflate()) and multiplying
562 	 * the left-hand side by 100 (to handle the percentage thing) we
563 	 * multiply the left-hand side by 50.
564 	 *
565 	 * The left-hand side may look a bit weird: tnode_child_length(tn)
566 	 * - tn->empty_children is of course the number of non-null children
567 	 * in the current node. tn->full_children is the number of "full"
568 	 * children, that is non-null tnodes with a skip value of 0.
569 	 * All of those will be doubled in the resulting inflated tnode, so
570 	 * we just count them one extra time here.
571 	 *
572 	 * A clearer way to write this would be:
573 	 *
574 	 * to_be_doubled = tn->full_children;
575 	 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
576 	 *     tn->full_children;
577 	 *
578 	 * new_child_length = tnode_child_length(tn) * 2;
579 	 *
580 	 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
581 	 *      new_child_length;
582 	 * if (new_fill_factor >= inflate_threshold)
583 	 *
584 	 * ...and so on, tho it would mess up the while () loop.
585 	 *
586 	 * anyway,
587 	 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
588 	 *      inflate_threshold
589 	 *
590 	 * avoid a division:
591 	 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
592 	 *      inflate_threshold * new_child_length
593 	 *
594 	 * expand not_to_be_doubled and to_be_doubled, and shorten:
595 	 * 100 * (tnode_child_length(tn) - tn->empty_children +
596 	 *    tn->full_children) >= inflate_threshold * new_child_length
597 	 *
598 	 * expand new_child_length:
599 	 * 100 * (tnode_child_length(tn) - tn->empty_children +
600 	 *    tn->full_children) >=
601 	 *      inflate_threshold * tnode_child_length(tn) * 2
602 	 *
603 	 * shorten again:
604 	 * 50 * (tn->full_children + tnode_child_length(tn) -
605 	 *    tn->empty_children) >= inflate_threshold *
606 	 *    tnode_child_length(tn)
607 	 *
608 	 */
609 
610 	check_tnode(tn);
611 
612 	/* Keep root node larger  */
613 
614 	if (!node_parent((struct rt_trie_node *)tn)) {
615 		inflate_threshold_use = inflate_threshold_root;
616 		halve_threshold_use = halve_threshold_root;
617 	} else {
618 		inflate_threshold_use = inflate_threshold;
619 		halve_threshold_use = halve_threshold;
620 	}
621 
622 	max_work = MAX_WORK;
623 	while ((tn->full_children > 0 &&  max_work-- &&
624 		50 * (tn->full_children + tnode_child_length(tn)
625 		      - tn->empty_children)
626 		>= inflate_threshold_use * tnode_child_length(tn))) {
627 
628 		old_tn = tn;
629 		tn = inflate(t, tn);
630 
631 		if (IS_ERR(tn)) {
632 			tn = old_tn;
633 #ifdef CONFIG_IP_FIB_TRIE_STATS
634 			t->stats.resize_node_skipped++;
635 #endif
636 			break;
637 		}
638 	}
639 
640 	check_tnode(tn);
641 
642 	/* Return if at least one inflate is run */
643 	if (max_work != MAX_WORK)
644 		return (struct rt_trie_node *) tn;
645 
646 	/*
647 	 * Halve as long as the number of empty children in this
648 	 * node is above threshold.
649 	 */
650 
651 	max_work = MAX_WORK;
652 	while (tn->bits > 1 &&  max_work-- &&
653 	       100 * (tnode_child_length(tn) - tn->empty_children) <
654 	       halve_threshold_use * tnode_child_length(tn)) {
655 
656 		old_tn = tn;
657 		tn = halve(t, tn);
658 		if (IS_ERR(tn)) {
659 			tn = old_tn;
660 #ifdef CONFIG_IP_FIB_TRIE_STATS
661 			t->stats.resize_node_skipped++;
662 #endif
663 			break;
664 		}
665 	}
666 
667 
668 	/* Only one child remains */
669 	if (tn->empty_children == tnode_child_length(tn) - 1) {
670 one_child:
671 		for (i = 0; i < tnode_child_length(tn); i++) {
672 			struct rt_trie_node *n;
673 
674 			n = rtnl_dereference(tn->child[i]);
675 			if (!n)
676 				continue;
677 
678 			/* compress one level */
679 
680 			node_set_parent(n, NULL);
681 			tnode_free_safe(tn);
682 			return n;
683 		}
684 	}
685 	return (struct rt_trie_node *) tn;
686 }
687 
688 
689 static void tnode_clean_free(struct tnode *tn)
690 {
691 	int i;
692 	struct tnode *tofree;
693 
694 	for (i = 0; i < tnode_child_length(tn); i++) {
695 		tofree = (struct tnode *)rtnl_dereference(tn->child[i]);
696 		if (tofree)
697 			tnode_free(tofree);
698 	}
699 	tnode_free(tn);
700 }
701 
702 static struct tnode *inflate(struct trie *t, struct tnode *tn)
703 {
704 	struct tnode *oldtnode = tn;
705 	int olen = tnode_child_length(tn);
706 	int i;
707 
708 	pr_debug("In inflate\n");
709 
710 	tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
711 
712 	if (!tn)
713 		return ERR_PTR(-ENOMEM);
714 
715 	/*
716 	 * Preallocate and store tnodes before the actual work so we
717 	 * don't get into an inconsistent state if memory allocation
718 	 * fails. In case of failure we return the oldnode and  inflate
719 	 * of tnode is ignored.
720 	 */
721 
722 	for (i = 0; i < olen; i++) {
723 		struct tnode *inode;
724 
725 		inode = (struct tnode *) tnode_get_child(oldtnode, i);
726 		if (inode &&
727 		    IS_TNODE(inode) &&
728 		    inode->pos == oldtnode->pos + oldtnode->bits &&
729 		    inode->bits > 1) {
730 			struct tnode *left, *right;
731 			t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
732 
733 			left = tnode_new(inode->key&(~m), inode->pos + 1,
734 					 inode->bits - 1);
735 			if (!left)
736 				goto nomem;
737 
738 			right = tnode_new(inode->key|m, inode->pos + 1,
739 					  inode->bits - 1);
740 
741 			if (!right) {
742 				tnode_free(left);
743 				goto nomem;
744 			}
745 
746 			put_child(tn, 2*i, (struct rt_trie_node *) left);
747 			put_child(tn, 2*i+1, (struct rt_trie_node *) right);
748 		}
749 	}
750 
751 	for (i = 0; i < olen; i++) {
752 		struct tnode *inode;
753 		struct rt_trie_node *node = tnode_get_child(oldtnode, i);
754 		struct tnode *left, *right;
755 		int size, j;
756 
757 		/* An empty child */
758 		if (node == NULL)
759 			continue;
760 
761 		/* A leaf or an internal node with skipped bits */
762 
763 		if (IS_LEAF(node) || ((struct tnode *) node)->pos >
764 		   tn->pos + tn->bits - 1) {
765 			put_child(tn,
766 				tkey_extract_bits(node->key, oldtnode->pos, oldtnode->bits + 1),
767 				node);
768 			continue;
769 		}
770 
771 		/* An internal node with two children */
772 		inode = (struct tnode *) node;
773 
774 		if (inode->bits == 1) {
775 			put_child(tn, 2*i, rtnl_dereference(inode->child[0]));
776 			put_child(tn, 2*i+1, rtnl_dereference(inode->child[1]));
777 
778 			tnode_free_safe(inode);
779 			continue;
780 		}
781 
782 		/* An internal node with more than two children */
783 
784 		/* We will replace this node 'inode' with two new
785 		 * ones, 'left' and 'right', each with half of the
786 		 * original children. The two new nodes will have
787 		 * a position one bit further down the key and this
788 		 * means that the "significant" part of their keys
789 		 * (see the discussion near the top of this file)
790 		 * will differ by one bit, which will be "0" in
791 		 * left's key and "1" in right's key. Since we are
792 		 * moving the key position by one step, the bit that
793 		 * we are moving away from - the bit at position
794 		 * (inode->pos) - is the one that will differ between
795 		 * left and right. So... we synthesize that bit in the
796 		 * two  new keys.
797 		 * The mask 'm' below will be a single "one" bit at
798 		 * the position (inode->pos)
799 		 */
800 
801 		/* Use the old key, but set the new significant
802 		 *   bit to zero.
803 		 */
804 
805 		left = (struct tnode *) tnode_get_child(tn, 2*i);
806 		put_child(tn, 2*i, NULL);
807 
808 		BUG_ON(!left);
809 
810 		right = (struct tnode *) tnode_get_child(tn, 2*i+1);
811 		put_child(tn, 2*i+1, NULL);
812 
813 		BUG_ON(!right);
814 
815 		size = tnode_child_length(left);
816 		for (j = 0; j < size; j++) {
817 			put_child(left, j, rtnl_dereference(inode->child[j]));
818 			put_child(right, j, rtnl_dereference(inode->child[j + size]));
819 		}
820 		put_child(tn, 2*i, resize(t, left));
821 		put_child(tn, 2*i+1, resize(t, right));
822 
823 		tnode_free_safe(inode);
824 	}
825 	tnode_free_safe(oldtnode);
826 	return tn;
827 nomem:
828 	tnode_clean_free(tn);
829 	return ERR_PTR(-ENOMEM);
830 }
831 
832 static struct tnode *halve(struct trie *t, struct tnode *tn)
833 {
834 	struct tnode *oldtnode = tn;
835 	struct rt_trie_node *left, *right;
836 	int i;
837 	int olen = tnode_child_length(tn);
838 
839 	pr_debug("In halve\n");
840 
841 	tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
842 
843 	if (!tn)
844 		return ERR_PTR(-ENOMEM);
845 
846 	/*
847 	 * Preallocate and store tnodes before the actual work so we
848 	 * don't get into an inconsistent state if memory allocation
849 	 * fails. In case of failure we return the oldnode and halve
850 	 * of tnode is ignored.
851 	 */
852 
853 	for (i = 0; i < olen; i += 2) {
854 		left = tnode_get_child(oldtnode, i);
855 		right = tnode_get_child(oldtnode, i+1);
856 
857 		/* Two nonempty children */
858 		if (left && right) {
859 			struct tnode *newn;
860 
861 			newn = tnode_new(left->key, tn->pos + tn->bits, 1);
862 
863 			if (!newn)
864 				goto nomem;
865 
866 			put_child(tn, i/2, (struct rt_trie_node *)newn);
867 		}
868 
869 	}
870 
871 	for (i = 0; i < olen; i += 2) {
872 		struct tnode *newBinNode;
873 
874 		left = tnode_get_child(oldtnode, i);
875 		right = tnode_get_child(oldtnode, i+1);
876 
877 		/* At least one of the children is empty */
878 		if (left == NULL) {
879 			if (right == NULL)    /* Both are empty */
880 				continue;
881 			put_child(tn, i/2, right);
882 			continue;
883 		}
884 
885 		if (right == NULL) {
886 			put_child(tn, i/2, left);
887 			continue;
888 		}
889 
890 		/* Two nonempty children */
891 		newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
892 		put_child(tn, i/2, NULL);
893 		put_child(newBinNode, 0, left);
894 		put_child(newBinNode, 1, right);
895 		put_child(tn, i/2, resize(t, newBinNode));
896 	}
897 	tnode_free_safe(oldtnode);
898 	return tn;
899 nomem:
900 	tnode_clean_free(tn);
901 	return ERR_PTR(-ENOMEM);
902 }
903 
904 /* readside must use rcu_read_lock currently dump routines
905  via get_fa_head and dump */
906 
907 static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
908 {
909 	struct hlist_head *head = &l->list;
910 	struct leaf_info *li;
911 
912 	hlist_for_each_entry_rcu(li, head, hlist)
913 		if (li->plen == plen)
914 			return li;
915 
916 	return NULL;
917 }
918 
919 static inline struct list_head *get_fa_head(struct leaf *l, int plen)
920 {
921 	struct leaf_info *li = find_leaf_info(l, plen);
922 
923 	if (!li)
924 		return NULL;
925 
926 	return &li->falh;
927 }
928 
929 static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
930 {
931 	struct leaf_info *li = NULL, *last = NULL;
932 
933 	if (hlist_empty(head)) {
934 		hlist_add_head_rcu(&new->hlist, head);
935 	} else {
936 		hlist_for_each_entry(li, head, hlist) {
937 			if (new->plen > li->plen)
938 				break;
939 
940 			last = li;
941 		}
942 		if (last)
943 			hlist_add_behind_rcu(&new->hlist, &last->hlist);
944 		else
945 			hlist_add_before_rcu(&new->hlist, &li->hlist);
946 	}
947 }
948 
949 /* rcu_read_lock needs to be hold by caller from readside */
950 
951 static struct leaf *
952 fib_find_node(struct trie *t, u32 key)
953 {
954 	int pos;
955 	struct tnode *tn;
956 	struct rt_trie_node *n;
957 
958 	pos = 0;
959 	n = rcu_dereference_rtnl(t->trie);
960 
961 	while (n != NULL &&  NODE_TYPE(n) == T_TNODE) {
962 		tn = (struct tnode *) n;
963 
964 		check_tnode(tn);
965 
966 		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
967 			pos = tn->pos + tn->bits;
968 			n = tnode_get_child_rcu(tn,
969 						tkey_extract_bits(key,
970 								  tn->pos,
971 								  tn->bits));
972 		} else
973 			break;
974 	}
975 	/* Case we have found a leaf. Compare prefixes */
976 
977 	if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
978 		return (struct leaf *)n;
979 
980 	return NULL;
981 }
982 
983 static void trie_rebalance(struct trie *t, struct tnode *tn)
984 {
985 	int wasfull;
986 	t_key cindex, key;
987 	struct tnode *tp;
988 
989 	key = tn->key;
990 
991 	while (tn != NULL && (tp = node_parent((struct rt_trie_node *)tn)) != NULL) {
992 		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
993 		wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
994 		tn = (struct tnode *)resize(t, tn);
995 
996 		tnode_put_child_reorg(tp, cindex,
997 				      (struct rt_trie_node *)tn, wasfull);
998 
999 		tp = node_parent((struct rt_trie_node *) tn);
1000 		if (!tp)
1001 			rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1002 
1003 		tnode_free_flush();
1004 		if (!tp)
1005 			break;
1006 		tn = tp;
1007 	}
1008 
1009 	/* Handle last (top) tnode */
1010 	if (IS_TNODE(tn))
1011 		tn = (struct tnode *)resize(t, tn);
1012 
1013 	rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1014 	tnode_free_flush();
1015 }
1016 
1017 /* only used from updater-side */
1018 
1019 static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
1020 {
1021 	int pos, newpos;
1022 	struct tnode *tp = NULL, *tn = NULL;
1023 	struct rt_trie_node *n;
1024 	struct leaf *l;
1025 	int missbit;
1026 	struct list_head *fa_head = NULL;
1027 	struct leaf_info *li;
1028 	t_key cindex;
1029 
1030 	pos = 0;
1031 	n = rtnl_dereference(t->trie);
1032 
1033 	/* If we point to NULL, stop. Either the tree is empty and we should
1034 	 * just put a new leaf in if, or we have reached an empty child slot,
1035 	 * and we should just put our new leaf in that.
1036 	 * If we point to a T_TNODE, check if it matches our key. Note that
1037 	 * a T_TNODE might be skipping any number of bits - its 'pos' need
1038 	 * not be the parent's 'pos'+'bits'!
1039 	 *
1040 	 * If it does match the current key, get pos/bits from it, extract
1041 	 * the index from our key, push the T_TNODE and walk the tree.
1042 	 *
1043 	 * If it doesn't, we have to replace it with a new T_TNODE.
1044 	 *
1045 	 * If we point to a T_LEAF, it might or might not have the same key
1046 	 * as we do. If it does, just change the value, update the T_LEAF's
1047 	 * value, and return it.
1048 	 * If it doesn't, we need to replace it with a T_TNODE.
1049 	 */
1050 
1051 	while (n != NULL &&  NODE_TYPE(n) == T_TNODE) {
1052 		tn = (struct tnode *) n;
1053 
1054 		check_tnode(tn);
1055 
1056 		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1057 			tp = tn;
1058 			pos = tn->pos + tn->bits;
1059 			n = tnode_get_child(tn,
1060 					    tkey_extract_bits(key,
1061 							      tn->pos,
1062 							      tn->bits));
1063 
1064 			BUG_ON(n && node_parent(n) != tn);
1065 		} else
1066 			break;
1067 	}
1068 
1069 	/*
1070 	 * n  ----> NULL, LEAF or TNODE
1071 	 *
1072 	 * tp is n's (parent) ----> NULL or TNODE
1073 	 */
1074 
1075 	BUG_ON(tp && IS_LEAF(tp));
1076 
1077 	/* Case 1: n is a leaf. Compare prefixes */
1078 
1079 	if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1080 		l = (struct leaf *) n;
1081 		li = leaf_info_new(plen);
1082 
1083 		if (!li)
1084 			return NULL;
1085 
1086 		fa_head = &li->falh;
1087 		insert_leaf_info(&l->list, li);
1088 		goto done;
1089 	}
1090 	l = leaf_new();
1091 
1092 	if (!l)
1093 		return NULL;
1094 
1095 	l->key = key;
1096 	li = leaf_info_new(plen);
1097 
1098 	if (!li) {
1099 		free_leaf(l);
1100 		return NULL;
1101 	}
1102 
1103 	fa_head = &li->falh;
1104 	insert_leaf_info(&l->list, li);
1105 
1106 	if (t->trie && n == NULL) {
1107 		/* Case 2: n is NULL, and will just insert a new leaf */
1108 
1109 		node_set_parent((struct rt_trie_node *)l, tp);
1110 
1111 		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1112 		put_child(tp, cindex, (struct rt_trie_node *)l);
1113 	} else {
1114 		/* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1115 		/*
1116 		 *  Add a new tnode here
1117 		 *  first tnode need some special handling
1118 		 */
1119 
1120 		if (n) {
1121 			pos = tp ? tp->pos+tp->bits : 0;
1122 			newpos = tkey_mismatch(key, pos, n->key);
1123 			tn = tnode_new(n->key, newpos, 1);
1124 		} else {
1125 			newpos = 0;
1126 			tn = tnode_new(key, newpos, 1); /* First tnode */
1127 		}
1128 
1129 		if (!tn) {
1130 			free_leaf_info(li);
1131 			free_leaf(l);
1132 			return NULL;
1133 		}
1134 
1135 		node_set_parent((struct rt_trie_node *)tn, tp);
1136 
1137 		missbit = tkey_extract_bits(key, newpos, 1);
1138 		put_child(tn, missbit, (struct rt_trie_node *)l);
1139 		put_child(tn, 1-missbit, n);
1140 
1141 		if (tp) {
1142 			cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1143 			put_child(tp, cindex, (struct rt_trie_node *)tn);
1144 		} else {
1145 			rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1146 			tp = tn;
1147 		}
1148 	}
1149 
1150 	if (tp && tp->pos + tp->bits > 32)
1151 		pr_warn("fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1152 			tp, tp->pos, tp->bits, key, plen);
1153 
1154 	/* Rebalance the trie */
1155 
1156 	trie_rebalance(t, tp);
1157 done:
1158 	return fa_head;
1159 }
1160 
1161 /*
1162  * Caller must hold RTNL.
1163  */
1164 int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
1165 {
1166 	struct trie *t = (struct trie *) tb->tb_data;
1167 	struct fib_alias *fa, *new_fa;
1168 	struct list_head *fa_head = NULL;
1169 	struct fib_info *fi;
1170 	int plen = cfg->fc_dst_len;
1171 	u8 tos = cfg->fc_tos;
1172 	u32 key, mask;
1173 	int err;
1174 	struct leaf *l;
1175 
1176 	if (plen > 32)
1177 		return -EINVAL;
1178 
1179 	key = ntohl(cfg->fc_dst);
1180 
1181 	pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1182 
1183 	mask = ntohl(inet_make_mask(plen));
1184 
1185 	if (key & ~mask)
1186 		return -EINVAL;
1187 
1188 	key = key & mask;
1189 
1190 	fi = fib_create_info(cfg);
1191 	if (IS_ERR(fi)) {
1192 		err = PTR_ERR(fi);
1193 		goto err;
1194 	}
1195 
1196 	l = fib_find_node(t, key);
1197 	fa = NULL;
1198 
1199 	if (l) {
1200 		fa_head = get_fa_head(l, plen);
1201 		fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1202 	}
1203 
1204 	/* Now fa, if non-NULL, points to the first fib alias
1205 	 * with the same keys [prefix,tos,priority], if such key already
1206 	 * exists or to the node before which we will insert new one.
1207 	 *
1208 	 * If fa is NULL, we will need to allocate a new one and
1209 	 * insert to the head of f.
1210 	 *
1211 	 * If f is NULL, no fib node matched the destination key
1212 	 * and we need to allocate a new one of those as well.
1213 	 */
1214 
1215 	if (fa && fa->fa_tos == tos &&
1216 	    fa->fa_info->fib_priority == fi->fib_priority) {
1217 		struct fib_alias *fa_first, *fa_match;
1218 
1219 		err = -EEXIST;
1220 		if (cfg->fc_nlflags & NLM_F_EXCL)
1221 			goto out;
1222 
1223 		/* We have 2 goals:
1224 		 * 1. Find exact match for type, scope, fib_info to avoid
1225 		 * duplicate routes
1226 		 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1227 		 */
1228 		fa_match = NULL;
1229 		fa_first = fa;
1230 		fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1231 		list_for_each_entry_continue(fa, fa_head, fa_list) {
1232 			if (fa->fa_tos != tos)
1233 				break;
1234 			if (fa->fa_info->fib_priority != fi->fib_priority)
1235 				break;
1236 			if (fa->fa_type == cfg->fc_type &&
1237 			    fa->fa_info == fi) {
1238 				fa_match = fa;
1239 				break;
1240 			}
1241 		}
1242 
1243 		if (cfg->fc_nlflags & NLM_F_REPLACE) {
1244 			struct fib_info *fi_drop;
1245 			u8 state;
1246 
1247 			fa = fa_first;
1248 			if (fa_match) {
1249 				if (fa == fa_match)
1250 					err = 0;
1251 				goto out;
1252 			}
1253 			err = -ENOBUFS;
1254 			new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1255 			if (new_fa == NULL)
1256 				goto out;
1257 
1258 			fi_drop = fa->fa_info;
1259 			new_fa->fa_tos = fa->fa_tos;
1260 			new_fa->fa_info = fi;
1261 			new_fa->fa_type = cfg->fc_type;
1262 			state = fa->fa_state;
1263 			new_fa->fa_state = state & ~FA_S_ACCESSED;
1264 
1265 			list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1266 			alias_free_mem_rcu(fa);
1267 
1268 			fib_release_info(fi_drop);
1269 			if (state & FA_S_ACCESSED)
1270 				rt_cache_flush(cfg->fc_nlinfo.nl_net);
1271 			rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1272 				tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1273 
1274 			goto succeeded;
1275 		}
1276 		/* Error if we find a perfect match which
1277 		 * uses the same scope, type, and nexthop
1278 		 * information.
1279 		 */
1280 		if (fa_match)
1281 			goto out;
1282 
1283 		if (!(cfg->fc_nlflags & NLM_F_APPEND))
1284 			fa = fa_first;
1285 	}
1286 	err = -ENOENT;
1287 	if (!(cfg->fc_nlflags & NLM_F_CREATE))
1288 		goto out;
1289 
1290 	err = -ENOBUFS;
1291 	new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1292 	if (new_fa == NULL)
1293 		goto out;
1294 
1295 	new_fa->fa_info = fi;
1296 	new_fa->fa_tos = tos;
1297 	new_fa->fa_type = cfg->fc_type;
1298 	new_fa->fa_state = 0;
1299 	/*
1300 	 * Insert new entry to the list.
1301 	 */
1302 
1303 	if (!fa_head) {
1304 		fa_head = fib_insert_node(t, key, plen);
1305 		if (unlikely(!fa_head)) {
1306 			err = -ENOMEM;
1307 			goto out_free_new_fa;
1308 		}
1309 	}
1310 
1311 	if (!plen)
1312 		tb->tb_num_default++;
1313 
1314 	list_add_tail_rcu(&new_fa->fa_list,
1315 			  (fa ? &fa->fa_list : fa_head));
1316 
1317 	rt_cache_flush(cfg->fc_nlinfo.nl_net);
1318 	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1319 		  &cfg->fc_nlinfo, 0);
1320 succeeded:
1321 	return 0;
1322 
1323 out_free_new_fa:
1324 	kmem_cache_free(fn_alias_kmem, new_fa);
1325 out:
1326 	fib_release_info(fi);
1327 err:
1328 	return err;
1329 }
1330 
1331 /* should be called with rcu_read_lock */
1332 static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
1333 		      t_key key,  const struct flowi4 *flp,
1334 		      struct fib_result *res, int fib_flags)
1335 {
1336 	struct leaf_info *li;
1337 	struct hlist_head *hhead = &l->list;
1338 
1339 	hlist_for_each_entry_rcu(li, hhead, hlist) {
1340 		struct fib_alias *fa;
1341 
1342 		if (l->key != (key & li->mask_plen))
1343 			continue;
1344 
1345 		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
1346 			struct fib_info *fi = fa->fa_info;
1347 			int nhsel, err;
1348 
1349 			if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1350 				continue;
1351 			if (fi->fib_dead)
1352 				continue;
1353 			if (fa->fa_info->fib_scope < flp->flowi4_scope)
1354 				continue;
1355 			fib_alias_accessed(fa);
1356 			err = fib_props[fa->fa_type].error;
1357 			if (err) {
1358 #ifdef CONFIG_IP_FIB_TRIE_STATS
1359 				t->stats.semantic_match_passed++;
1360 #endif
1361 				return err;
1362 			}
1363 			if (fi->fib_flags & RTNH_F_DEAD)
1364 				continue;
1365 			for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
1366 				const struct fib_nh *nh = &fi->fib_nh[nhsel];
1367 
1368 				if (nh->nh_flags & RTNH_F_DEAD)
1369 					continue;
1370 				if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
1371 					continue;
1372 
1373 #ifdef CONFIG_IP_FIB_TRIE_STATS
1374 				t->stats.semantic_match_passed++;
1375 #endif
1376 				res->prefixlen = li->plen;
1377 				res->nh_sel = nhsel;
1378 				res->type = fa->fa_type;
1379 				res->scope = fa->fa_info->fib_scope;
1380 				res->fi = fi;
1381 				res->table = tb;
1382 				res->fa_head = &li->falh;
1383 				if (!(fib_flags & FIB_LOOKUP_NOREF))
1384 					atomic_inc(&fi->fib_clntref);
1385 				return 0;
1386 			}
1387 		}
1388 
1389 #ifdef CONFIG_IP_FIB_TRIE_STATS
1390 		t->stats.semantic_match_miss++;
1391 #endif
1392 	}
1393 
1394 	return 1;
1395 }
1396 
1397 int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
1398 		     struct fib_result *res, int fib_flags)
1399 {
1400 	struct trie *t = (struct trie *) tb->tb_data;
1401 	int ret;
1402 	struct rt_trie_node *n;
1403 	struct tnode *pn;
1404 	unsigned int pos, bits;
1405 	t_key key = ntohl(flp->daddr);
1406 	unsigned int chopped_off;
1407 	t_key cindex = 0;
1408 	unsigned int current_prefix_length = KEYLENGTH;
1409 	struct tnode *cn;
1410 	t_key pref_mismatch;
1411 
1412 	rcu_read_lock();
1413 
1414 	n = rcu_dereference(t->trie);
1415 	if (!n)
1416 		goto failed;
1417 
1418 #ifdef CONFIG_IP_FIB_TRIE_STATS
1419 	t->stats.gets++;
1420 #endif
1421 
1422 	/* Just a leaf? */
1423 	if (IS_LEAF(n)) {
1424 		ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1425 		goto found;
1426 	}
1427 
1428 	pn = (struct tnode *) n;
1429 	chopped_off = 0;
1430 
1431 	while (pn) {
1432 		pos = pn->pos;
1433 		bits = pn->bits;
1434 
1435 		if (!chopped_off)
1436 			cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1437 						   pos, bits);
1438 
1439 		n = tnode_get_child_rcu(pn, cindex);
1440 
1441 		if (n == NULL) {
1442 #ifdef CONFIG_IP_FIB_TRIE_STATS
1443 			t->stats.null_node_hit++;
1444 #endif
1445 			goto backtrace;
1446 		}
1447 
1448 		if (IS_LEAF(n)) {
1449 			ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1450 			if (ret > 0)
1451 				goto backtrace;
1452 			goto found;
1453 		}
1454 
1455 		cn = (struct tnode *)n;
1456 
1457 		/*
1458 		 * It's a tnode, and we can do some extra checks here if we
1459 		 * like, to avoid descending into a dead-end branch.
1460 		 * This tnode is in the parent's child array at index
1461 		 * key[p_pos..p_pos+p_bits] but potentially with some bits
1462 		 * chopped off, so in reality the index may be just a
1463 		 * subprefix, padded with zero at the end.
1464 		 * We can also take a look at any skipped bits in this
1465 		 * tnode - everything up to p_pos is supposed to be ok,
1466 		 * and the non-chopped bits of the index (se previous
1467 		 * paragraph) are also guaranteed ok, but the rest is
1468 		 * considered unknown.
1469 		 *
1470 		 * The skipped bits are key[pos+bits..cn->pos].
1471 		 */
1472 
1473 		/* If current_prefix_length < pos+bits, we are already doing
1474 		 * actual prefix  matching, which means everything from
1475 		 * pos+(bits-chopped_off) onward must be zero along some
1476 		 * branch of this subtree - otherwise there is *no* valid
1477 		 * prefix present. Here we can only check the skipped
1478 		 * bits. Remember, since we have already indexed into the
1479 		 * parent's child array, we know that the bits we chopped of
1480 		 * *are* zero.
1481 		 */
1482 
1483 		/* NOTA BENE: Checking only skipped bits
1484 		   for the new node here */
1485 
1486 		if (current_prefix_length < pos+bits) {
1487 			if (tkey_extract_bits(cn->key, current_prefix_length,
1488 						cn->pos - current_prefix_length)
1489 			    || !(cn->child[0]))
1490 				goto backtrace;
1491 		}
1492 
1493 		/*
1494 		 * If chopped_off=0, the index is fully validated and we
1495 		 * only need to look at the skipped bits for this, the new,
1496 		 * tnode. What we actually want to do is to find out if
1497 		 * these skipped bits match our key perfectly, or if we will
1498 		 * have to count on finding a matching prefix further down,
1499 		 * because if we do, we would like to have some way of
1500 		 * verifying the existence of such a prefix at this point.
1501 		 */
1502 
1503 		/* The only thing we can do at this point is to verify that
1504 		 * any such matching prefix can indeed be a prefix to our
1505 		 * key, and if the bits in the node we are inspecting that
1506 		 * do not match our key are not ZERO, this cannot be true.
1507 		 * Thus, find out where there is a mismatch (before cn->pos)
1508 		 * and verify that all the mismatching bits are zero in the
1509 		 * new tnode's key.
1510 		 */
1511 
1512 		/*
1513 		 * Note: We aren't very concerned about the piece of
1514 		 * the key that precede pn->pos+pn->bits, since these
1515 		 * have already been checked. The bits after cn->pos
1516 		 * aren't checked since these are by definition
1517 		 * "unknown" at this point. Thus, what we want to see
1518 		 * is if we are about to enter the "prefix matching"
1519 		 * state, and in that case verify that the skipped
1520 		 * bits that will prevail throughout this subtree are
1521 		 * zero, as they have to be if we are to find a
1522 		 * matching prefix.
1523 		 */
1524 
1525 		pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
1526 
1527 		/*
1528 		 * In short: If skipped bits in this node do not match
1529 		 * the search key, enter the "prefix matching"
1530 		 * state.directly.
1531 		 */
1532 		if (pref_mismatch) {
1533 			/* fls(x) = __fls(x) + 1 */
1534 			int mp = KEYLENGTH - __fls(pref_mismatch) - 1;
1535 
1536 			if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
1537 				goto backtrace;
1538 
1539 			if (current_prefix_length >= cn->pos)
1540 				current_prefix_length = mp;
1541 		}
1542 
1543 		pn = (struct tnode *)n; /* Descend */
1544 		chopped_off = 0;
1545 		continue;
1546 
1547 backtrace:
1548 		chopped_off++;
1549 
1550 		/* As zero don't change the child key (cindex) */
1551 		while ((chopped_off <= pn->bits)
1552 		       && !(cindex & (1<<(chopped_off-1))))
1553 			chopped_off++;
1554 
1555 		/* Decrease current_... with bits chopped off */
1556 		if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1557 			current_prefix_length = pn->pos + pn->bits
1558 				- chopped_off;
1559 
1560 		/*
1561 		 * Either we do the actual chop off according or if we have
1562 		 * chopped off all bits in this tnode walk up to our parent.
1563 		 */
1564 
1565 		if (chopped_off <= pn->bits) {
1566 			cindex &= ~(1 << (chopped_off-1));
1567 		} else {
1568 			struct tnode *parent = node_parent_rcu((struct rt_trie_node *) pn);
1569 			if (!parent)
1570 				goto failed;
1571 
1572 			/* Get Child's index */
1573 			cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1574 			pn = parent;
1575 			chopped_off = 0;
1576 
1577 #ifdef CONFIG_IP_FIB_TRIE_STATS
1578 			t->stats.backtrack++;
1579 #endif
1580 			goto backtrace;
1581 		}
1582 	}
1583 failed:
1584 	ret = 1;
1585 found:
1586 	rcu_read_unlock();
1587 	return ret;
1588 }
1589 EXPORT_SYMBOL_GPL(fib_table_lookup);
1590 
1591 /*
1592  * Remove the leaf and return parent.
1593  */
1594 static void trie_leaf_remove(struct trie *t, struct leaf *l)
1595 {
1596 	struct tnode *tp = node_parent((struct rt_trie_node *) l);
1597 
1598 	pr_debug("entering trie_leaf_remove(%p)\n", l);
1599 
1600 	if (tp) {
1601 		t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1602 		put_child(tp, cindex, NULL);
1603 		trie_rebalance(t, tp);
1604 	} else
1605 		RCU_INIT_POINTER(t->trie, NULL);
1606 
1607 	free_leaf(l);
1608 }
1609 
1610 /*
1611  * Caller must hold RTNL.
1612  */
1613 int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
1614 {
1615 	struct trie *t = (struct trie *) tb->tb_data;
1616 	u32 key, mask;
1617 	int plen = cfg->fc_dst_len;
1618 	u8 tos = cfg->fc_tos;
1619 	struct fib_alias *fa, *fa_to_delete;
1620 	struct list_head *fa_head;
1621 	struct leaf *l;
1622 	struct leaf_info *li;
1623 
1624 	if (plen > 32)
1625 		return -EINVAL;
1626 
1627 	key = ntohl(cfg->fc_dst);
1628 	mask = ntohl(inet_make_mask(plen));
1629 
1630 	if (key & ~mask)
1631 		return -EINVAL;
1632 
1633 	key = key & mask;
1634 	l = fib_find_node(t, key);
1635 
1636 	if (!l)
1637 		return -ESRCH;
1638 
1639 	li = find_leaf_info(l, plen);
1640 
1641 	if (!li)
1642 		return -ESRCH;
1643 
1644 	fa_head = &li->falh;
1645 	fa = fib_find_alias(fa_head, tos, 0);
1646 
1647 	if (!fa)
1648 		return -ESRCH;
1649 
1650 	pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1651 
1652 	fa_to_delete = NULL;
1653 	fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1654 	list_for_each_entry_continue(fa, fa_head, fa_list) {
1655 		struct fib_info *fi = fa->fa_info;
1656 
1657 		if (fa->fa_tos != tos)
1658 			break;
1659 
1660 		if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1661 		    (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1662 		     fa->fa_info->fib_scope == cfg->fc_scope) &&
1663 		    (!cfg->fc_prefsrc ||
1664 		     fi->fib_prefsrc == cfg->fc_prefsrc) &&
1665 		    (!cfg->fc_protocol ||
1666 		     fi->fib_protocol == cfg->fc_protocol) &&
1667 		    fib_nh_match(cfg, fi) == 0) {
1668 			fa_to_delete = fa;
1669 			break;
1670 		}
1671 	}
1672 
1673 	if (!fa_to_delete)
1674 		return -ESRCH;
1675 
1676 	fa = fa_to_delete;
1677 	rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1678 		  &cfg->fc_nlinfo, 0);
1679 
1680 	list_del_rcu(&fa->fa_list);
1681 
1682 	if (!plen)
1683 		tb->tb_num_default--;
1684 
1685 	if (list_empty(fa_head)) {
1686 		hlist_del_rcu(&li->hlist);
1687 		free_leaf_info(li);
1688 	}
1689 
1690 	if (hlist_empty(&l->list))
1691 		trie_leaf_remove(t, l);
1692 
1693 	if (fa->fa_state & FA_S_ACCESSED)
1694 		rt_cache_flush(cfg->fc_nlinfo.nl_net);
1695 
1696 	fib_release_info(fa->fa_info);
1697 	alias_free_mem_rcu(fa);
1698 	return 0;
1699 }
1700 
1701 static int trie_flush_list(struct list_head *head)
1702 {
1703 	struct fib_alias *fa, *fa_node;
1704 	int found = 0;
1705 
1706 	list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1707 		struct fib_info *fi = fa->fa_info;
1708 
1709 		if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1710 			list_del_rcu(&fa->fa_list);
1711 			fib_release_info(fa->fa_info);
1712 			alias_free_mem_rcu(fa);
1713 			found++;
1714 		}
1715 	}
1716 	return found;
1717 }
1718 
1719 static int trie_flush_leaf(struct leaf *l)
1720 {
1721 	int found = 0;
1722 	struct hlist_head *lih = &l->list;
1723 	struct hlist_node *tmp;
1724 	struct leaf_info *li = NULL;
1725 
1726 	hlist_for_each_entry_safe(li, tmp, lih, hlist) {
1727 		found += trie_flush_list(&li->falh);
1728 
1729 		if (list_empty(&li->falh)) {
1730 			hlist_del_rcu(&li->hlist);
1731 			free_leaf_info(li);
1732 		}
1733 	}
1734 	return found;
1735 }
1736 
1737 /*
1738  * Scan for the next right leaf starting at node p->child[idx]
1739  * Since we have back pointer, no recursion necessary.
1740  */
1741 static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1742 {
1743 	do {
1744 		t_key idx;
1745 
1746 		if (c)
1747 			idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1748 		else
1749 			idx = 0;
1750 
1751 		while (idx < 1u << p->bits) {
1752 			c = tnode_get_child_rcu(p, idx++);
1753 			if (!c)
1754 				continue;
1755 
1756 			if (IS_LEAF(c))
1757 				return (struct leaf *) c;
1758 
1759 			/* Rescan start scanning in new node */
1760 			p = (struct tnode *) c;
1761 			idx = 0;
1762 		}
1763 
1764 		/* Node empty, walk back up to parent */
1765 		c = (struct rt_trie_node *) p;
1766 	} while ((p = node_parent_rcu(c)) != NULL);
1767 
1768 	return NULL; /* Root of trie */
1769 }
1770 
1771 static struct leaf *trie_firstleaf(struct trie *t)
1772 {
1773 	struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
1774 
1775 	if (!n)
1776 		return NULL;
1777 
1778 	if (IS_LEAF(n))          /* trie is just a leaf */
1779 		return (struct leaf *) n;
1780 
1781 	return leaf_walk_rcu(n, NULL);
1782 }
1783 
1784 static struct leaf *trie_nextleaf(struct leaf *l)
1785 {
1786 	struct rt_trie_node *c = (struct rt_trie_node *) l;
1787 	struct tnode *p = node_parent_rcu(c);
1788 
1789 	if (!p)
1790 		return NULL;	/* trie with just one leaf */
1791 
1792 	return leaf_walk_rcu(p, c);
1793 }
1794 
1795 static struct leaf *trie_leafindex(struct trie *t, int index)
1796 {
1797 	struct leaf *l = trie_firstleaf(t);
1798 
1799 	while (l && index-- > 0)
1800 		l = trie_nextleaf(l);
1801 
1802 	return l;
1803 }
1804 
1805 
1806 /*
1807  * Caller must hold RTNL.
1808  */
1809 int fib_table_flush(struct fib_table *tb)
1810 {
1811 	struct trie *t = (struct trie *) tb->tb_data;
1812 	struct leaf *l, *ll = NULL;
1813 	int found = 0;
1814 
1815 	for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1816 		found += trie_flush_leaf(l);
1817 
1818 		if (ll && hlist_empty(&ll->list))
1819 			trie_leaf_remove(t, ll);
1820 		ll = l;
1821 	}
1822 
1823 	if (ll && hlist_empty(&ll->list))
1824 		trie_leaf_remove(t, ll);
1825 
1826 	pr_debug("trie_flush found=%d\n", found);
1827 	return found;
1828 }
1829 
1830 void fib_free_table(struct fib_table *tb)
1831 {
1832 	kfree(tb);
1833 }
1834 
1835 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1836 			   struct fib_table *tb,
1837 			   struct sk_buff *skb, struct netlink_callback *cb)
1838 {
1839 	int i, s_i;
1840 	struct fib_alias *fa;
1841 	__be32 xkey = htonl(key);
1842 
1843 	s_i = cb->args[5];
1844 	i = 0;
1845 
1846 	/* rcu_read_lock is hold by caller */
1847 
1848 	list_for_each_entry_rcu(fa, fah, fa_list) {
1849 		if (i < s_i) {
1850 			i++;
1851 			continue;
1852 		}
1853 
1854 		if (fib_dump_info(skb, NETLINK_CB(cb->skb).portid,
1855 				  cb->nlh->nlmsg_seq,
1856 				  RTM_NEWROUTE,
1857 				  tb->tb_id,
1858 				  fa->fa_type,
1859 				  xkey,
1860 				  plen,
1861 				  fa->fa_tos,
1862 				  fa->fa_info, NLM_F_MULTI) < 0) {
1863 			cb->args[5] = i;
1864 			return -1;
1865 		}
1866 		i++;
1867 	}
1868 	cb->args[5] = i;
1869 	return skb->len;
1870 }
1871 
1872 static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1873 			struct sk_buff *skb, struct netlink_callback *cb)
1874 {
1875 	struct leaf_info *li;
1876 	int i, s_i;
1877 
1878 	s_i = cb->args[4];
1879 	i = 0;
1880 
1881 	/* rcu_read_lock is hold by caller */
1882 	hlist_for_each_entry_rcu(li, &l->list, hlist) {
1883 		if (i < s_i) {
1884 			i++;
1885 			continue;
1886 		}
1887 
1888 		if (i > s_i)
1889 			cb->args[5] = 0;
1890 
1891 		if (list_empty(&li->falh))
1892 			continue;
1893 
1894 		if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1895 			cb->args[4] = i;
1896 			return -1;
1897 		}
1898 		i++;
1899 	}
1900 
1901 	cb->args[4] = i;
1902 	return skb->len;
1903 }
1904 
1905 int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
1906 		   struct netlink_callback *cb)
1907 {
1908 	struct leaf *l;
1909 	struct trie *t = (struct trie *) tb->tb_data;
1910 	t_key key = cb->args[2];
1911 	int count = cb->args[3];
1912 
1913 	rcu_read_lock();
1914 	/* Dump starting at last key.
1915 	 * Note: 0.0.0.0/0 (ie default) is first key.
1916 	 */
1917 	if (count == 0)
1918 		l = trie_firstleaf(t);
1919 	else {
1920 		/* Normally, continue from last key, but if that is missing
1921 		 * fallback to using slow rescan
1922 		 */
1923 		l = fib_find_node(t, key);
1924 		if (!l)
1925 			l = trie_leafindex(t, count);
1926 	}
1927 
1928 	while (l) {
1929 		cb->args[2] = l->key;
1930 		if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1931 			cb->args[3] = count;
1932 			rcu_read_unlock();
1933 			return -1;
1934 		}
1935 
1936 		++count;
1937 		l = trie_nextleaf(l);
1938 		memset(&cb->args[4], 0,
1939 		       sizeof(cb->args) - 4*sizeof(cb->args[0]));
1940 	}
1941 	cb->args[3] = count;
1942 	rcu_read_unlock();
1943 
1944 	return skb->len;
1945 }
1946 
1947 void __init fib_trie_init(void)
1948 {
1949 	fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1950 					  sizeof(struct fib_alias),
1951 					  0, SLAB_PANIC, NULL);
1952 
1953 	trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1954 					   max(sizeof(struct leaf),
1955 					       sizeof(struct leaf_info)),
1956 					   0, SLAB_PANIC, NULL);
1957 }
1958 
1959 
1960 struct fib_table *fib_trie_table(u32 id)
1961 {
1962 	struct fib_table *tb;
1963 	struct trie *t;
1964 
1965 	tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1966 		     GFP_KERNEL);
1967 	if (tb == NULL)
1968 		return NULL;
1969 
1970 	tb->tb_id = id;
1971 	tb->tb_default = -1;
1972 	tb->tb_num_default = 0;
1973 
1974 	t = (struct trie *) tb->tb_data;
1975 	memset(t, 0, sizeof(*t));
1976 
1977 	return tb;
1978 }
1979 
1980 #ifdef CONFIG_PROC_FS
1981 /* Depth first Trie walk iterator */
1982 struct fib_trie_iter {
1983 	struct seq_net_private p;
1984 	struct fib_table *tb;
1985 	struct tnode *tnode;
1986 	unsigned int index;
1987 	unsigned int depth;
1988 };
1989 
1990 static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
1991 {
1992 	struct tnode *tn = iter->tnode;
1993 	unsigned int cindex = iter->index;
1994 	struct tnode *p;
1995 
1996 	/* A single entry routing table */
1997 	if (!tn)
1998 		return NULL;
1999 
2000 	pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2001 		 iter->tnode, iter->index, iter->depth);
2002 rescan:
2003 	while (cindex < (1<<tn->bits)) {
2004 		struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
2005 
2006 		if (n) {
2007 			if (IS_LEAF(n)) {
2008 				iter->tnode = tn;
2009 				iter->index = cindex + 1;
2010 			} else {
2011 				/* push down one level */
2012 				iter->tnode = (struct tnode *) n;
2013 				iter->index = 0;
2014 				++iter->depth;
2015 			}
2016 			return n;
2017 		}
2018 
2019 		++cindex;
2020 	}
2021 
2022 	/* Current node exhausted, pop back up */
2023 	p = node_parent_rcu((struct rt_trie_node *)tn);
2024 	if (p) {
2025 		cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2026 		tn = p;
2027 		--iter->depth;
2028 		goto rescan;
2029 	}
2030 
2031 	/* got root? */
2032 	return NULL;
2033 }
2034 
2035 static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
2036 				       struct trie *t)
2037 {
2038 	struct rt_trie_node *n;
2039 
2040 	if (!t)
2041 		return NULL;
2042 
2043 	n = rcu_dereference(t->trie);
2044 	if (!n)
2045 		return NULL;
2046 
2047 	if (IS_TNODE(n)) {
2048 		iter->tnode = (struct tnode *) n;
2049 		iter->index = 0;
2050 		iter->depth = 1;
2051 	} else {
2052 		iter->tnode = NULL;
2053 		iter->index = 0;
2054 		iter->depth = 0;
2055 	}
2056 
2057 	return n;
2058 }
2059 
2060 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2061 {
2062 	struct rt_trie_node *n;
2063 	struct fib_trie_iter iter;
2064 
2065 	memset(s, 0, sizeof(*s));
2066 
2067 	rcu_read_lock();
2068 	for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2069 		if (IS_LEAF(n)) {
2070 			struct leaf *l = (struct leaf *)n;
2071 			struct leaf_info *li;
2072 
2073 			s->leaves++;
2074 			s->totdepth += iter.depth;
2075 			if (iter.depth > s->maxdepth)
2076 				s->maxdepth = iter.depth;
2077 
2078 			hlist_for_each_entry_rcu(li, &l->list, hlist)
2079 				++s->prefixes;
2080 		} else {
2081 			const struct tnode *tn = (const struct tnode *) n;
2082 			int i;
2083 
2084 			s->tnodes++;
2085 			if (tn->bits < MAX_STAT_DEPTH)
2086 				s->nodesizes[tn->bits]++;
2087 
2088 			for (i = 0; i < (1<<tn->bits); i++)
2089 				if (!tn->child[i])
2090 					s->nullpointers++;
2091 		}
2092 	}
2093 	rcu_read_unlock();
2094 }
2095 
2096 /*
2097  *	This outputs /proc/net/fib_triestats
2098  */
2099 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2100 {
2101 	unsigned int i, max, pointers, bytes, avdepth;
2102 
2103 	if (stat->leaves)
2104 		avdepth = stat->totdepth*100 / stat->leaves;
2105 	else
2106 		avdepth = 0;
2107 
2108 	seq_printf(seq, "\tAver depth:     %u.%02d\n",
2109 		   avdepth / 100, avdepth % 100);
2110 	seq_printf(seq, "\tMax depth:      %u\n", stat->maxdepth);
2111 
2112 	seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
2113 	bytes = sizeof(struct leaf) * stat->leaves;
2114 
2115 	seq_printf(seq, "\tPrefixes:       %u\n", stat->prefixes);
2116 	bytes += sizeof(struct leaf_info) * stat->prefixes;
2117 
2118 	seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2119 	bytes += sizeof(struct tnode) * stat->tnodes;
2120 
2121 	max = MAX_STAT_DEPTH;
2122 	while (max > 0 && stat->nodesizes[max-1] == 0)
2123 		max--;
2124 
2125 	pointers = 0;
2126 	for (i = 1; i < max; i++)
2127 		if (stat->nodesizes[i] != 0) {
2128 			seq_printf(seq, "  %u: %u",  i, stat->nodesizes[i]);
2129 			pointers += (1<<i) * stat->nodesizes[i];
2130 		}
2131 	seq_putc(seq, '\n');
2132 	seq_printf(seq, "\tPointers: %u\n", pointers);
2133 
2134 	bytes += sizeof(struct rt_trie_node *) * pointers;
2135 	seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2136 	seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
2137 }
2138 
2139 #ifdef CONFIG_IP_FIB_TRIE_STATS
2140 static void trie_show_usage(struct seq_file *seq,
2141 			    const struct trie_use_stats *stats)
2142 {
2143 	seq_printf(seq, "\nCounters:\n---------\n");
2144 	seq_printf(seq, "gets = %u\n", stats->gets);
2145 	seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2146 	seq_printf(seq, "semantic match passed = %u\n",
2147 		   stats->semantic_match_passed);
2148 	seq_printf(seq, "semantic match miss = %u\n",
2149 		   stats->semantic_match_miss);
2150 	seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2151 	seq_printf(seq, "skipped node resize = %u\n\n",
2152 		   stats->resize_node_skipped);
2153 }
2154 #endif /*  CONFIG_IP_FIB_TRIE_STATS */
2155 
2156 static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2157 {
2158 	if (tb->tb_id == RT_TABLE_LOCAL)
2159 		seq_puts(seq, "Local:\n");
2160 	else if (tb->tb_id == RT_TABLE_MAIN)
2161 		seq_puts(seq, "Main:\n");
2162 	else
2163 		seq_printf(seq, "Id %d:\n", tb->tb_id);
2164 }
2165 
2166 
2167 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2168 {
2169 	struct net *net = (struct net *)seq->private;
2170 	unsigned int h;
2171 
2172 	seq_printf(seq,
2173 		   "Basic info: size of leaf:"
2174 		   " %Zd bytes, size of tnode: %Zd bytes.\n",
2175 		   sizeof(struct leaf), sizeof(struct tnode));
2176 
2177 	for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2178 		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2179 		struct fib_table *tb;
2180 
2181 		hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2182 			struct trie *t = (struct trie *) tb->tb_data;
2183 			struct trie_stat stat;
2184 
2185 			if (!t)
2186 				continue;
2187 
2188 			fib_table_print(seq, tb);
2189 
2190 			trie_collect_stats(t, &stat);
2191 			trie_show_stats(seq, &stat);
2192 #ifdef CONFIG_IP_FIB_TRIE_STATS
2193 			trie_show_usage(seq, &t->stats);
2194 #endif
2195 		}
2196 	}
2197 
2198 	return 0;
2199 }
2200 
2201 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2202 {
2203 	return single_open_net(inode, file, fib_triestat_seq_show);
2204 }
2205 
2206 static const struct file_operations fib_triestat_fops = {
2207 	.owner	= THIS_MODULE,
2208 	.open	= fib_triestat_seq_open,
2209 	.read	= seq_read,
2210 	.llseek	= seq_lseek,
2211 	.release = single_release_net,
2212 };
2213 
2214 static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2215 {
2216 	struct fib_trie_iter *iter = seq->private;
2217 	struct net *net = seq_file_net(seq);
2218 	loff_t idx = 0;
2219 	unsigned int h;
2220 
2221 	for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2222 		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2223 		struct fib_table *tb;
2224 
2225 		hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2226 			struct rt_trie_node *n;
2227 
2228 			for (n = fib_trie_get_first(iter,
2229 						    (struct trie *) tb->tb_data);
2230 			     n; n = fib_trie_get_next(iter))
2231 				if (pos == idx++) {
2232 					iter->tb = tb;
2233 					return n;
2234 				}
2235 		}
2236 	}
2237 
2238 	return NULL;
2239 }
2240 
2241 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2242 	__acquires(RCU)
2243 {
2244 	rcu_read_lock();
2245 	return fib_trie_get_idx(seq, *pos);
2246 }
2247 
2248 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2249 {
2250 	struct fib_trie_iter *iter = seq->private;
2251 	struct net *net = seq_file_net(seq);
2252 	struct fib_table *tb = iter->tb;
2253 	struct hlist_node *tb_node;
2254 	unsigned int h;
2255 	struct rt_trie_node *n;
2256 
2257 	++*pos;
2258 	/* next node in same table */
2259 	n = fib_trie_get_next(iter);
2260 	if (n)
2261 		return n;
2262 
2263 	/* walk rest of this hash chain */
2264 	h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2265 	while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2266 		tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2267 		n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2268 		if (n)
2269 			goto found;
2270 	}
2271 
2272 	/* new hash chain */
2273 	while (++h < FIB_TABLE_HASHSZ) {
2274 		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2275 		hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2276 			n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2277 			if (n)
2278 				goto found;
2279 		}
2280 	}
2281 	return NULL;
2282 
2283 found:
2284 	iter->tb = tb;
2285 	return n;
2286 }
2287 
2288 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2289 	__releases(RCU)
2290 {
2291 	rcu_read_unlock();
2292 }
2293 
2294 static void seq_indent(struct seq_file *seq, int n)
2295 {
2296 	while (n-- > 0)
2297 		seq_puts(seq, "   ");
2298 }
2299 
2300 static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2301 {
2302 	switch (s) {
2303 	case RT_SCOPE_UNIVERSE: return "universe";
2304 	case RT_SCOPE_SITE:	return "site";
2305 	case RT_SCOPE_LINK:	return "link";
2306 	case RT_SCOPE_HOST:	return "host";
2307 	case RT_SCOPE_NOWHERE:	return "nowhere";
2308 	default:
2309 		snprintf(buf, len, "scope=%d", s);
2310 		return buf;
2311 	}
2312 }
2313 
2314 static const char *const rtn_type_names[__RTN_MAX] = {
2315 	[RTN_UNSPEC] = "UNSPEC",
2316 	[RTN_UNICAST] = "UNICAST",
2317 	[RTN_LOCAL] = "LOCAL",
2318 	[RTN_BROADCAST] = "BROADCAST",
2319 	[RTN_ANYCAST] = "ANYCAST",
2320 	[RTN_MULTICAST] = "MULTICAST",
2321 	[RTN_BLACKHOLE] = "BLACKHOLE",
2322 	[RTN_UNREACHABLE] = "UNREACHABLE",
2323 	[RTN_PROHIBIT] = "PROHIBIT",
2324 	[RTN_THROW] = "THROW",
2325 	[RTN_NAT] = "NAT",
2326 	[RTN_XRESOLVE] = "XRESOLVE",
2327 };
2328 
2329 static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2330 {
2331 	if (t < __RTN_MAX && rtn_type_names[t])
2332 		return rtn_type_names[t];
2333 	snprintf(buf, len, "type %u", t);
2334 	return buf;
2335 }
2336 
2337 /* Pretty print the trie */
2338 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2339 {
2340 	const struct fib_trie_iter *iter = seq->private;
2341 	struct rt_trie_node *n = v;
2342 
2343 	if (!node_parent_rcu(n))
2344 		fib_table_print(seq, iter->tb);
2345 
2346 	if (IS_TNODE(n)) {
2347 		struct tnode *tn = (struct tnode *) n;
2348 		__be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2349 
2350 		seq_indent(seq, iter->depth-1);
2351 		seq_printf(seq, "  +-- %pI4/%d %d %d %d\n",
2352 			   &prf, tn->pos, tn->bits, tn->full_children,
2353 			   tn->empty_children);
2354 
2355 	} else {
2356 		struct leaf *l = (struct leaf *) n;
2357 		struct leaf_info *li;
2358 		__be32 val = htonl(l->key);
2359 
2360 		seq_indent(seq, iter->depth);
2361 		seq_printf(seq, "  |-- %pI4\n", &val);
2362 
2363 		hlist_for_each_entry_rcu(li, &l->list, hlist) {
2364 			struct fib_alias *fa;
2365 
2366 			list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2367 				char buf1[32], buf2[32];
2368 
2369 				seq_indent(seq, iter->depth+1);
2370 				seq_printf(seq, "  /%d %s %s", li->plen,
2371 					   rtn_scope(buf1, sizeof(buf1),
2372 						     fa->fa_info->fib_scope),
2373 					   rtn_type(buf2, sizeof(buf2),
2374 						    fa->fa_type));
2375 				if (fa->fa_tos)
2376 					seq_printf(seq, " tos=%d", fa->fa_tos);
2377 				seq_putc(seq, '\n');
2378 			}
2379 		}
2380 	}
2381 
2382 	return 0;
2383 }
2384 
2385 static const struct seq_operations fib_trie_seq_ops = {
2386 	.start  = fib_trie_seq_start,
2387 	.next   = fib_trie_seq_next,
2388 	.stop   = fib_trie_seq_stop,
2389 	.show   = fib_trie_seq_show,
2390 };
2391 
2392 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2393 {
2394 	return seq_open_net(inode, file, &fib_trie_seq_ops,
2395 			    sizeof(struct fib_trie_iter));
2396 }
2397 
2398 static const struct file_operations fib_trie_fops = {
2399 	.owner  = THIS_MODULE,
2400 	.open   = fib_trie_seq_open,
2401 	.read   = seq_read,
2402 	.llseek = seq_lseek,
2403 	.release = seq_release_net,
2404 };
2405 
2406 struct fib_route_iter {
2407 	struct seq_net_private p;
2408 	struct trie *main_trie;
2409 	loff_t	pos;
2410 	t_key	key;
2411 };
2412 
2413 static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2414 {
2415 	struct leaf *l = NULL;
2416 	struct trie *t = iter->main_trie;
2417 
2418 	/* use cache location of last found key */
2419 	if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2420 		pos -= iter->pos;
2421 	else {
2422 		iter->pos = 0;
2423 		l = trie_firstleaf(t);
2424 	}
2425 
2426 	while (l && pos-- > 0) {
2427 		iter->pos++;
2428 		l = trie_nextleaf(l);
2429 	}
2430 
2431 	if (l)
2432 		iter->key = pos;	/* remember it */
2433 	else
2434 		iter->pos = 0;		/* forget it */
2435 
2436 	return l;
2437 }
2438 
2439 static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2440 	__acquires(RCU)
2441 {
2442 	struct fib_route_iter *iter = seq->private;
2443 	struct fib_table *tb;
2444 
2445 	rcu_read_lock();
2446 	tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2447 	if (!tb)
2448 		return NULL;
2449 
2450 	iter->main_trie = (struct trie *) tb->tb_data;
2451 	if (*pos == 0)
2452 		return SEQ_START_TOKEN;
2453 	else
2454 		return fib_route_get_idx(iter, *pos - 1);
2455 }
2456 
2457 static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2458 {
2459 	struct fib_route_iter *iter = seq->private;
2460 	struct leaf *l = v;
2461 
2462 	++*pos;
2463 	if (v == SEQ_START_TOKEN) {
2464 		iter->pos = 0;
2465 		l = trie_firstleaf(iter->main_trie);
2466 	} else {
2467 		iter->pos++;
2468 		l = trie_nextleaf(l);
2469 	}
2470 
2471 	if (l)
2472 		iter->key = l->key;
2473 	else
2474 		iter->pos = 0;
2475 	return l;
2476 }
2477 
2478 static void fib_route_seq_stop(struct seq_file *seq, void *v)
2479 	__releases(RCU)
2480 {
2481 	rcu_read_unlock();
2482 }
2483 
2484 static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2485 {
2486 	unsigned int flags = 0;
2487 
2488 	if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
2489 		flags = RTF_REJECT;
2490 	if (fi && fi->fib_nh->nh_gw)
2491 		flags |= RTF_GATEWAY;
2492 	if (mask == htonl(0xFFFFFFFF))
2493 		flags |= RTF_HOST;
2494 	flags |= RTF_UP;
2495 	return flags;
2496 }
2497 
2498 /*
2499  *	This outputs /proc/net/route.
2500  *	The format of the file is not supposed to be changed
2501  *	and needs to be same as fib_hash output to avoid breaking
2502  *	legacy utilities
2503  */
2504 static int fib_route_seq_show(struct seq_file *seq, void *v)
2505 {
2506 	struct leaf *l = v;
2507 	struct leaf_info *li;
2508 
2509 	if (v == SEQ_START_TOKEN) {
2510 		seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2511 			   "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2512 			   "\tWindow\tIRTT");
2513 		return 0;
2514 	}
2515 
2516 	hlist_for_each_entry_rcu(li, &l->list, hlist) {
2517 		struct fib_alias *fa;
2518 		__be32 mask, prefix;
2519 
2520 		mask = inet_make_mask(li->plen);
2521 		prefix = htonl(l->key);
2522 
2523 		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2524 			const struct fib_info *fi = fa->fa_info;
2525 			unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2526 
2527 			if (fa->fa_type == RTN_BROADCAST
2528 			    || fa->fa_type == RTN_MULTICAST)
2529 				continue;
2530 
2531 			seq_setwidth(seq, 127);
2532 
2533 			if (fi)
2534 				seq_printf(seq,
2535 					 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2536 					 "%d\t%08X\t%d\t%u\t%u",
2537 					 fi->fib_dev ? fi->fib_dev->name : "*",
2538 					 prefix,
2539 					 fi->fib_nh->nh_gw, flags, 0, 0,
2540 					 fi->fib_priority,
2541 					 mask,
2542 					 (fi->fib_advmss ?
2543 					  fi->fib_advmss + 40 : 0),
2544 					 fi->fib_window,
2545 					 fi->fib_rtt >> 3);
2546 			else
2547 				seq_printf(seq,
2548 					 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2549 					 "%d\t%08X\t%d\t%u\t%u",
2550 					 prefix, 0, flags, 0, 0, 0,
2551 					 mask, 0, 0, 0);
2552 
2553 			seq_pad(seq, '\n');
2554 		}
2555 	}
2556 
2557 	return 0;
2558 }
2559 
2560 static const struct seq_operations fib_route_seq_ops = {
2561 	.start  = fib_route_seq_start,
2562 	.next   = fib_route_seq_next,
2563 	.stop   = fib_route_seq_stop,
2564 	.show   = fib_route_seq_show,
2565 };
2566 
2567 static int fib_route_seq_open(struct inode *inode, struct file *file)
2568 {
2569 	return seq_open_net(inode, file, &fib_route_seq_ops,
2570 			    sizeof(struct fib_route_iter));
2571 }
2572 
2573 static const struct file_operations fib_route_fops = {
2574 	.owner  = THIS_MODULE,
2575 	.open   = fib_route_seq_open,
2576 	.read   = seq_read,
2577 	.llseek = seq_lseek,
2578 	.release = seq_release_net,
2579 };
2580 
2581 int __net_init fib_proc_init(struct net *net)
2582 {
2583 	if (!proc_create("fib_trie", S_IRUGO, net->proc_net, &fib_trie_fops))
2584 		goto out1;
2585 
2586 	if (!proc_create("fib_triestat", S_IRUGO, net->proc_net,
2587 			 &fib_triestat_fops))
2588 		goto out2;
2589 
2590 	if (!proc_create("route", S_IRUGO, net->proc_net, &fib_route_fops))
2591 		goto out3;
2592 
2593 	return 0;
2594 
2595 out3:
2596 	remove_proc_entry("fib_triestat", net->proc_net);
2597 out2:
2598 	remove_proc_entry("fib_trie", net->proc_net);
2599 out1:
2600 	return -ENOMEM;
2601 }
2602 
2603 void __net_exit fib_proc_exit(struct net *net)
2604 {
2605 	remove_proc_entry("fib_trie", net->proc_net);
2606 	remove_proc_entry("fib_triestat", net->proc_net);
2607 	remove_proc_entry("route", net->proc_net);
2608 }
2609 
2610 #endif /* CONFIG_PROC_FS */
2611