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