fib_trie.c 60.3 KB
Newer Older
1 2 3 4 5 6 7 8 9
/*
 *   This program is free software; you can redistribute it and/or
 *   modify it under the terms of the GNU General Public License
 *   as published by the Free Software Foundation; either version
 *   2 of the License, or (at your option) any later version.
 *
 *   Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
 *     & Swedish University of Agricultural Sciences.
 *
10
 *   Jens Laas <jens.laas@data.slu.se> Swedish University of
11
 *     Agricultural Sciences.
12
 *
13 14 15
 *   Hans Liss <hans.liss@its.uu.se>  Uppsala Universitet
 *
 * This work is based on the LPC-trie which is originally descibed in:
16
 *
17 18
 * An experimental study of compression methods for dynamic tries
 * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
19
 * http://www.csc.kth.se/~snilsson/software/dyntrie2/
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
 *
 *
 * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
 * IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999
 *
 *
 * Code from fib_hash has been reused which includes the following header:
 *
 *
 * INET		An implementation of the TCP/IP protocol suite for the LINUX
 *		operating system.  INET is implemented using the  BSD Socket
 *		interface as the means of communication with the user level.
 *
 *		IPv4 FIB: lookup engine and maintenance routines.
 *
 *
 * Authors:	Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
 *
 *		This program is free software; you can redistribute it and/or
 *		modify it under the terms of the GNU General Public License
 *		as published by the Free Software Foundation; either version
 *		2 of the License, or (at your option) any later version.
R
Robert Olsson 已提交
42 43 44 45 46 47 48
 *
 * Substantial contributions to this work comes from:
 *
 *		David S. Miller, <davem@davemloft.net>
 *		Stephen Hemminger <shemminger@osdl.org>
 *		Paul E. McKenney <paulmck@us.ibm.com>
 *		Patrick McHardy <kaber@trash.net>
49 50
 */

J
Jens Låås 已提交
51
#define VERSION "0.409"
52 53 54

#include <asm/uaccess.h>
#include <asm/system.h>
J
Jiri Slaby 已提交
55
#include <linux/bitops.h>
56 57 58 59 60 61 62 63 64
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/mm.h>
#include <linux/string.h>
#include <linux/socket.h>
#include <linux/sockios.h>
#include <linux/errno.h>
#include <linux/in.h>
#include <linux/inet.h>
S
Stephen Hemminger 已提交
65
#include <linux/inetdevice.h>
66 67 68
#include <linux/netdevice.h>
#include <linux/if_arp.h>
#include <linux/proc_fs.h>
R
Robert Olsson 已提交
69
#include <linux/rcupdate.h>
70 71 72 73
#include <linux/skbuff.h>
#include <linux/netlink.h>
#include <linux/init.h>
#include <linux/list.h>
74
#include <linux/slab.h>
75
#include <net/net_namespace.h>
76 77 78 79 80 81 82 83
#include <net/ip.h>
#include <net/protocol.h>
#include <net/route.h>
#include <net/tcp.h>
#include <net/sock.h>
#include <net/ip_fib.h>
#include "fib_lookup.h"

R
Robert Olsson 已提交
84
#define MAX_STAT_DEPTH 32
85 86 87 88 89 90 91 92

#define KEYLENGTH (8*sizeof(t_key))

typedef unsigned int t_key;

#define T_TNODE 0
#define T_LEAF  1
#define NODE_TYPE_MASK	0x1UL
R
Robert Olsson 已提交
93 94
#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)

O
Olof Johansson 已提交
95 96
#define IS_TNODE(n) (!(n->parent & T_LEAF))
#define IS_LEAF(n) (n->parent & T_LEAF)
97

98
struct rt_trie_node {
O
Olof Johansson 已提交
99
	unsigned long parent;
100
	t_key key;
101 102 103
};

struct leaf {
O
Olof Johansson 已提交
104
	unsigned long parent;
105
	t_key key;
106
	struct hlist_head list;
R
Robert Olsson 已提交
107
	struct rcu_head rcu;
108 109 110 111
};

struct leaf_info {
	struct hlist_node hlist;
R
Robert Olsson 已提交
112
	struct rcu_head rcu;
113 114 115 116 117
	int plen;
	struct list_head falh;
};

struct tnode {
O
Olof Johansson 已提交
118
	unsigned long parent;
119
	t_key key;
120 121
	unsigned char pos;		/* 2log(KEYLENGTH) bits needed */
	unsigned char bits;		/* 2log(KEYLENGTH) bits needed */
122 123
	unsigned int full_children;	/* KEYLENGTH bits needed */
	unsigned int empty_children;	/* KEYLENGTH bits needed */
124 125 126
	union {
		struct rcu_head rcu;
		struct work_struct work;
J
Jarek Poplawski 已提交
127
		struct tnode *tnode_free;
128
	};
129
	struct rt_trie_node *child[0];
130 131 132 133 134 135 136 137 138
};

#ifdef CONFIG_IP_FIB_TRIE_STATS
struct trie_use_stats {
	unsigned int gets;
	unsigned int backtrack;
	unsigned int semantic_match_passed;
	unsigned int semantic_match_miss;
	unsigned int null_node_hit;
139
	unsigned int resize_node_skipped;
140 141 142 143 144 145 146 147 148
};
#endif

struct trie_stat {
	unsigned int totdepth;
	unsigned int maxdepth;
	unsigned int tnodes;
	unsigned int leaves;
	unsigned int nullpointers;
149
	unsigned int prefixes;
R
Robert Olsson 已提交
150
	unsigned int nodesizes[MAX_STAT_DEPTH];
151
};
152 153

struct trie {
154
	struct rt_trie_node *trie;
155 156 157 158 159
#ifdef CONFIG_IP_FIB_TRIE_STATS
	struct trie_use_stats stats;
#endif
};

160 161
static void put_child(struct trie *t, struct tnode *tn, int i, struct rt_trie_node *n);
static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
162
				  int wasfull);
163
static struct rt_trie_node *resize(struct trie *t, struct tnode *tn);
164 165
static struct tnode *inflate(struct trie *t, struct tnode *tn);
static struct tnode *halve(struct trie *t, struct tnode *tn);
J
Jarek Poplawski 已提交
166 167
/* tnodes to free after resize(); protected by RTNL */
static struct tnode *tnode_free_head;
168 169 170 171 172 173 174 175
static size_t tnode_free_size;

/*
 * synchronize_rcu after call_rcu for that many pages; it should be especially
 * useful before resizing the root node with PREEMPT_NONE configs; the value was
 * obtained experimentally, aiming to avoid visible slowdown.
 */
static const int sync_pages = 128;
176

177
static struct kmem_cache *fn_alias_kmem __read_mostly;
178
static struct kmem_cache *trie_leaf_kmem __read_mostly;
179

180
static inline struct tnode *node_parent(struct rt_trie_node *node)
S
Stephen Hemminger 已提交
181
{
182 183 184
	return (struct tnode *)(node->parent & ~NODE_TYPE_MASK);
}

185
static inline struct tnode *node_parent_rcu(struct rt_trie_node *node)
186 187
{
	struct tnode *ret = node_parent(node);
S
Stephen Hemminger 已提交
188

E
Eric Dumazet 已提交
189
	return rcu_dereference_rtnl(ret);
S
Stephen Hemminger 已提交
190 191
}

192 193 194
/* Same as rcu_assign_pointer
 * but that macro() assumes that value is a pointer.
 */
195
static inline void node_set_parent(struct rt_trie_node *node, struct tnode *ptr)
S
Stephen Hemminger 已提交
196
{
197 198
	smp_wmb();
	node->parent = (unsigned long)ptr | NODE_TYPE(node);
S
Stephen Hemminger 已提交
199
}
R
Robert Olsson 已提交
200

201
static inline struct rt_trie_node *tnode_get_child(struct tnode *tn, unsigned int i)
202 203
{
	BUG_ON(i >= 1U << tn->bits);
R
Robert Olsson 已提交
204

205 206 207
	return tn->child[i];
}

208
static inline struct rt_trie_node *tnode_get_child_rcu(struct tnode *tn, unsigned int i)
209
{
210
	struct rt_trie_node *ret = tnode_get_child(tn, i);
211

E
Eric Dumazet 已提交
212
	return rcu_dereference_rtnl(ret);
213 214
}

S
Stephen Hemmigner 已提交
215
static inline int tnode_child_length(const struct tnode *tn)
216
{
O
Olof Johansson 已提交
217
	return 1 << tn->bits;
218 219
}

S
Stephen Hemminger 已提交
220 221 222 223 224
static inline t_key mask_pfx(t_key k, unsigned short l)
{
	return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
}

225 226
static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
{
O
Olof Johansson 已提交
227
	if (offset < KEYLENGTH)
228
		return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
O
Olof Johansson 已提交
229
	else
230 231 232 233 234
		return 0;
}

static inline int tkey_equals(t_key a, t_key b)
{
235
	return a == b;
236 237 238 239
}

static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
{
240 241
	if (bits == 0 || offset >= KEYLENGTH)
		return 1;
O
Olof Johansson 已提交
242 243
	bits = bits > KEYLENGTH ? KEYLENGTH : bits;
	return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
244
}
245 246 247 248 249 250

static inline int tkey_mismatch(t_key a, int offset, t_key b)
{
	t_key diff = a ^ b;
	int i = offset;

251 252 253
	if (!diff)
		return 0;
	while ((diff << i) >> (KEYLENGTH-1) == 0)
254 255 256 257 258
		i++;
	return i;
}

/*
259 260
  To understand this stuff, an understanding of keys and all their bits is
  necessary. Every node in the trie has a key associated with it, but not
261 262 263 264
  all of the bits in that key are significant.

  Consider a node 'n' and its parent 'tp'.

265 266 267 268 269
  If n is a leaf, every bit in its key is significant. Its presence is
  necessitated by path compression, since during a tree traversal (when
  searching for a leaf - unless we are doing an insertion) we will completely
  ignore all skipped bits we encounter. Thus we need to verify, at the end of
  a potentially successful search, that we have indeed been walking the
270 271
  correct key path.

272 273 274 275 276
  Note that we can never "miss" the correct key in the tree if present by
  following the wrong path. Path compression ensures that segments of the key
  that are the same for all keys with a given prefix are skipped, but the
  skipped part *is* identical for each node in the subtrie below the skipped
  bit! trie_insert() in this implementation takes care of that - note the
277 278
  call to tkey_sub_equals() in trie_insert().

279
  if n is an internal node - a 'tnode' here, the various parts of its key
280 281
  have many different meanings.

282
  Example:
283 284 285
  _________________________________________________________________
  | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
  -----------------------------------------------------------------
286
    0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
287 288 289 290 291 292 293 294 295

  _________________________________________________________________
  | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
  -----------------------------------------------------------------
   16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31

  tp->pos = 7
  tp->bits = 3
  n->pos = 15
O
Olof Johansson 已提交
296
  n->bits = 4
297

298 299
  First, let's just ignore the bits that come before the parent tp, that is
  the bits from 0 to (tp->pos-1). They are *known* but at this point we do
300 301 302
  not use them for anything.

  The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
303
  index into the parent's child array. That is, they will be used to find
304 305 306 307 308
  'n' among tp's children.

  The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
  for the node n.

309
  All the bits we have seen so far are significant to the node n. The rest
310 311
  of the bits are really not needed or indeed known in n->key.

312
  The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
313
  n's child array, and will of course be different for each child.
314

315

316 317 318 319 320
  The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
  at this point.

*/

S
Stephen Hemminger 已提交
321
static inline void check_tnode(const struct tnode *tn)
322
{
S
Stephen Hemminger 已提交
323
	WARN_ON(tn && tn->pos+tn->bits > 32);
324 325
}

326 327
static const int halve_threshold = 25;
static const int inflate_threshold = 50;
328
static const int halve_threshold_root = 15;
J
Jens Låås 已提交
329
static const int inflate_threshold_root = 30;
R
Robert Olsson 已提交
330 331

static void __alias_free_mem(struct rcu_head *head)
332
{
R
Robert Olsson 已提交
333 334
	struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
	kmem_cache_free(fn_alias_kmem, fa);
335 336
}

R
Robert Olsson 已提交
337
static inline void alias_free_mem_rcu(struct fib_alias *fa)
338
{
R
Robert Olsson 已提交
339 340
	call_rcu(&fa->rcu, __alias_free_mem);
}
O
Olof Johansson 已提交
341

R
Robert Olsson 已提交
342 343
static void __leaf_free_rcu(struct rcu_head *head)
{
344 345
	struct leaf *l = container_of(head, struct leaf, rcu);
	kmem_cache_free(trie_leaf_kmem, l);
R
Robert Olsson 已提交
346
}
O
Olof Johansson 已提交
347

348 349 350 351 352
static inline void free_leaf(struct leaf *l)
{
	call_rcu_bh(&l->rcu, __leaf_free_rcu);
}

R
Robert Olsson 已提交
353
static void __leaf_info_free_rcu(struct rcu_head *head)
354
{
R
Robert Olsson 已提交
355
	kfree(container_of(head, struct leaf_info, rcu));
356 357
}

R
Robert Olsson 已提交
358
static inline void free_leaf_info(struct leaf_info *leaf)
359
{
R
Robert Olsson 已提交
360
	call_rcu(&leaf->rcu, __leaf_info_free_rcu);
361 362
}

363
static struct tnode *tnode_alloc(size_t size)
364
{
R
Robert Olsson 已提交
365
	if (size <= PAGE_SIZE)
366
		return kzalloc(size, GFP_KERNEL);
367
	else
368
		return vzalloc(size);
369
}
R
Robert Olsson 已提交
370

371 372 373 374
static void __tnode_vfree(struct work_struct *arg)
{
	struct tnode *tn = container_of(arg, struct tnode, work);
	vfree(tn);
375 376
}

R
Robert Olsson 已提交
377
static void __tnode_free_rcu(struct rcu_head *head)
378
{
R
Robert Olsson 已提交
379
	struct tnode *tn = container_of(head, struct tnode, rcu);
380
	size_t size = sizeof(struct tnode) +
381
		      (sizeof(struct rt_trie_node *) << tn->bits);
382 383 384

	if (size <= PAGE_SIZE)
		kfree(tn);
385 386 387 388
	else {
		INIT_WORK(&tn->work, __tnode_vfree);
		schedule_work(&tn->work);
	}
389 390
}

R
Robert Olsson 已提交
391 392
static inline void tnode_free(struct tnode *tn)
{
393 394 395
	if (IS_LEAF(tn))
		free_leaf((struct leaf *) tn);
	else
R
Robert Olsson 已提交
396
		call_rcu(&tn->rcu, __tnode_free_rcu);
R
Robert Olsson 已提交
397 398
}

J
Jarek Poplawski 已提交
399 400 401
static void tnode_free_safe(struct tnode *tn)
{
	BUG_ON(IS_LEAF(tn));
402 403
	tn->tnode_free = tnode_free_head;
	tnode_free_head = tn;
404
	tnode_free_size += sizeof(struct tnode) +
405
			   (sizeof(struct rt_trie_node *) << tn->bits);
J
Jarek Poplawski 已提交
406 407 408 409 410 411 412 413 414 415 416
}

static void tnode_free_flush(void)
{
	struct tnode *tn;

	while ((tn = tnode_free_head)) {
		tnode_free_head = tn->tnode_free;
		tn->tnode_free = NULL;
		tnode_free(tn);
	}
417 418 419 420 421

	if (tnode_free_size >= PAGE_SIZE * sync_pages) {
		tnode_free_size = 0;
		synchronize_rcu();
	}
J
Jarek Poplawski 已提交
422 423
}

R
Robert Olsson 已提交
424 425
static struct leaf *leaf_new(void)
{
426
	struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
R
Robert Olsson 已提交
427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443
	if (l) {
		l->parent = T_LEAF;
		INIT_HLIST_HEAD(&l->list);
	}
	return l;
}

static struct leaf_info *leaf_info_new(int plen)
{
	struct leaf_info *li = kmalloc(sizeof(struct leaf_info),  GFP_KERNEL);
	if (li) {
		li->plen = plen;
		INIT_LIST_HEAD(&li->falh);
	}
	return li;
}

444
static struct tnode *tnode_new(t_key key, int pos, int bits)
445
{
446
	size_t sz = sizeof(struct tnode) + (sizeof(struct rt_trie_node *) << bits);
447
	struct tnode *tn = tnode_alloc(sz);
448

O
Olof Johansson 已提交
449
	if (tn) {
R
Robert Olsson 已提交
450
		tn->parent = T_TNODE;
451 452 453 454 455 456
		tn->pos = pos;
		tn->bits = bits;
		tn->key = key;
		tn->full_children = 0;
		tn->empty_children = 1<<bits;
	}
457

E
Eric Dumazet 已提交
458
	pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode),
459
		 sizeof(struct rt_trie_node) << bits);
460 461 462 463 464 465 466 467
	return tn;
}

/*
 * Check whether a tnode 'n' is "full", i.e. it is an internal node
 * and no bits are skipped. See discussion in dyntree paper p. 6
 */

468
static inline int tnode_full(const struct tnode *tn, const struct rt_trie_node *n)
469
{
470
	if (n == NULL || IS_LEAF(n))
471 472 473 474 475
		return 0;

	return ((struct tnode *) n)->pos == tn->pos + tn->bits;
}

476
static inline void put_child(struct trie *t, struct tnode *tn, int i,
477
			     struct rt_trie_node *n)
478 479 480 481
{
	tnode_put_child_reorg(tn, i, n, -1);
}

482
 /*
483 484 485 486
  * Add a child at position i overwriting the old value.
  * Update the value of full_children and empty_children.
  */

487
static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
488
				  int wasfull)
489
{
490
	struct rt_trie_node *chi = tn->child[i];
491 492
	int isfull;

S
Stephen Hemminger 已提交
493 494
	BUG_ON(i >= 1<<tn->bits);

495 496 497 498 499
	/* update emptyChildren */
	if (n == NULL && chi != NULL)
		tn->empty_children++;
	else if (n != NULL && chi == NULL)
		tn->empty_children--;
500

501
	/* update fullChildren */
O
Olof Johansson 已提交
502
	if (wasfull == -1)
503 504 505
		wasfull = tnode_full(tn, chi);

	isfull = tnode_full(tn, n);
506
	if (wasfull && !isfull)
507
		tn->full_children--;
508
	else if (!wasfull && isfull)
509
		tn->full_children++;
O
Olof Johansson 已提交
510

511
	if (n)
S
Stephen Hemminger 已提交
512
		node_set_parent(n, tn);
513

R
Robert Olsson 已提交
514
	rcu_assign_pointer(tn->child[i], n);
515 516
}

J
Jens Låås 已提交
517
#define MAX_WORK 10
518
static struct rt_trie_node *resize(struct trie *t, struct tnode *tn)
519 520
{
	int i;
521
	struct tnode *old_tn;
522 523
	int inflate_threshold_use;
	int halve_threshold_use;
J
Jens Låås 已提交
524
	int max_work;
525

526
	if (!tn)
527 528
		return NULL;

S
Stephen Hemminger 已提交
529 530
	pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
		 tn, inflate_threshold, halve_threshold);
531 532 533

	/* No children */
	if (tn->empty_children == tnode_child_length(tn)) {
J
Jarek Poplawski 已提交
534
		tnode_free_safe(tn);
535 536 537 538
		return NULL;
	}
	/* One child */
	if (tn->empty_children == tnode_child_length(tn) - 1)
J
Jens Låås 已提交
539
		goto one_child;
540
	/*
541 542 543 544 545
	 * Double as long as the resulting node has a number of
	 * nonempty nodes that are above the threshold.
	 */

	/*
546 547
	 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
	 * the Helsinki University of Technology and Matti Tikkanen of Nokia
548
	 * Telecommunications, page 6:
549
	 * "A node is doubled if the ratio of non-empty children to all
550 551
	 * children in the *doubled* node is at least 'high'."
	 *
552 553 554 555 556
	 * 'high' in this instance is the variable 'inflate_threshold'. It
	 * is expressed as a percentage, so we multiply it with
	 * tnode_child_length() and instead of multiplying by 2 (since the
	 * child array will be doubled by inflate()) and multiplying
	 * the left-hand side by 100 (to handle the percentage thing) we
557
	 * multiply the left-hand side by 50.
558 559 560 561
	 *
	 * The left-hand side may look a bit weird: tnode_child_length(tn)
	 * - tn->empty_children is of course the number of non-null children
	 * in the current node. tn->full_children is the number of "full"
562
	 * children, that is non-null tnodes with a skip value of 0.
563
	 * All of those will be doubled in the resulting inflated tnode, so
564
	 * we just count them one extra time here.
565
	 *
566
	 * A clearer way to write this would be:
567
	 *
568
	 * to_be_doubled = tn->full_children;
569
	 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
570 571 572 573
	 *     tn->full_children;
	 *
	 * new_child_length = tnode_child_length(tn) * 2;
	 *
574
	 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
575 576
	 *      new_child_length;
	 * if (new_fill_factor >= inflate_threshold)
577 578 579
	 *
	 * ...and so on, tho it would mess up the while () loop.
	 *
580 581 582
	 * anyway,
	 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
	 *      inflate_threshold
583
	 *
584 585 586
	 * avoid a division:
	 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
	 *      inflate_threshold * new_child_length
587
	 *
588
	 * expand not_to_be_doubled and to_be_doubled, and shorten:
589
	 * 100 * (tnode_child_length(tn) - tn->empty_children +
O
Olof Johansson 已提交
590
	 *    tn->full_children) >= inflate_threshold * new_child_length
591
	 *
592
	 * expand new_child_length:
593
	 * 100 * (tnode_child_length(tn) - tn->empty_children +
O
Olof Johansson 已提交
594
	 *    tn->full_children) >=
595
	 *      inflate_threshold * tnode_child_length(tn) * 2
596
	 *
597
	 * shorten again:
598
	 * 50 * (tn->full_children + tnode_child_length(tn) -
O
Olof Johansson 已提交
599
	 *    tn->empty_children) >= inflate_threshold *
600
	 *    tnode_child_length(tn)
601
	 *
602 603 604
	 */

	check_tnode(tn);
605

606 607
	/* Keep root node larger  */

608
	if (!node_parent((struct rt_trie_node *)tn)) {
J
Jens Låås 已提交
609 610
		inflate_threshold_use = inflate_threshold_root;
		halve_threshold_use = halve_threshold_root;
E
Eric Dumazet 已提交
611
	} else {
612
		inflate_threshold_use = inflate_threshold;
J
Jens Låås 已提交
613 614
		halve_threshold_use = halve_threshold;
	}
615

J
Jens Låås 已提交
616 617
	max_work = MAX_WORK;
	while ((tn->full_children > 0 &&  max_work-- &&
618 619 620
		50 * (tn->full_children + tnode_child_length(tn)
		      - tn->empty_children)
		>= inflate_threshold_use * tnode_child_length(tn))) {
621

622 623
		old_tn = tn;
		tn = inflate(t, tn);
624

625 626
		if (IS_ERR(tn)) {
			tn = old_tn;
627 628 629 630 631
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.resize_node_skipped++;
#endif
			break;
		}
632 633 634 635
	}

	check_tnode(tn);

J
Jens Låås 已提交
636
	/* Return if at least one inflate is run */
E
Eric Dumazet 已提交
637
	if (max_work != MAX_WORK)
638
		return (struct rt_trie_node *) tn;
J
Jens Låås 已提交
639

640 641 642 643
	/*
	 * Halve as long as the number of empty children in this
	 * node is above threshold.
	 */
644

J
Jens Låås 已提交
645 646
	max_work = MAX_WORK;
	while (tn->bits > 1 &&  max_work-- &&
647
	       100 * (tnode_child_length(tn) - tn->empty_children) <
648
	       halve_threshold_use * tnode_child_length(tn)) {
649

650 651 652 653
		old_tn = tn;
		tn = halve(t, tn);
		if (IS_ERR(tn)) {
			tn = old_tn;
654 655 656 657 658 659
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.resize_node_skipped++;
#endif
			break;
		}
	}
660

661

662
	/* Only one child remains */
J
Jens Låås 已提交
663 664
	if (tn->empty_children == tnode_child_length(tn) - 1) {
one_child:
665
		for (i = 0; i < tnode_child_length(tn); i++) {
666
			struct rt_trie_node *n;
667

O
Olof Johansson 已提交
668
			n = tn->child[i];
R
Robert Olsson 已提交
669
			if (!n)
O
Olof Johansson 已提交
670 671 672 673
				continue;

			/* compress one level */

S
Stephen Hemminger 已提交
674
			node_set_parent(n, NULL);
J
Jarek Poplawski 已提交
675
			tnode_free_safe(tn);
O
Olof Johansson 已提交
676
			return n;
677
		}
J
Jens Låås 已提交
678
	}
679
	return (struct rt_trie_node *) tn;
680 681
}

682
static struct tnode *inflate(struct trie *t, struct tnode *tn)
683 684 685 686 687
{
	struct tnode *oldtnode = tn;
	int olen = tnode_child_length(tn);
	int i;

S
Stephen Hemminger 已提交
688
	pr_debug("In inflate\n");
689 690 691

	tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);

S
Stephen Hemminger 已提交
692
	if (!tn)
693
		return ERR_PTR(-ENOMEM);
694 695

	/*
696 697 698
	 * Preallocate and store tnodes before the actual work so we
	 * don't get into an inconsistent state if memory allocation
	 * fails. In case of failure we return the oldnode and  inflate
699 700
	 * of tnode is ignored.
	 */
O
Olof Johansson 已提交
701 702

	for (i = 0; i < olen; i++) {
703
		struct tnode *inode;
704

705
		inode = (struct tnode *) tnode_get_child(oldtnode, i);
706 707 708 709 710
		if (inode &&
		    IS_TNODE(inode) &&
		    inode->pos == oldtnode->pos + oldtnode->bits &&
		    inode->bits > 1) {
			struct tnode *left, *right;
S
Stephen Hemminger 已提交
711
			t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
712

713 714
			left = tnode_new(inode->key&(~m), inode->pos + 1,
					 inode->bits - 1);
715 716
			if (!left)
				goto nomem;
O
Olof Johansson 已提交
717

718 719 720
			right = tnode_new(inode->key|m, inode->pos + 1,
					  inode->bits - 1);

721
			if (!right) {
722 723
				tnode_free(left);
				goto nomem;
724
			}
725

726 727
			put_child(t, tn, 2*i, (struct rt_trie_node *) left);
			put_child(t, tn, 2*i+1, (struct rt_trie_node *) right);
728 729 730
		}
	}

O
Olof Johansson 已提交
731
	for (i = 0; i < olen; i++) {
732
		struct tnode *inode;
733
		struct rt_trie_node *node = tnode_get_child(oldtnode, i);
O
Olof Johansson 已提交
734 735
		struct tnode *left, *right;
		int size, j;
736

737 738 739 740 741 742
		/* An empty child */
		if (node == NULL)
			continue;

		/* A leaf or an internal node with skipped bits */

743
		if (IS_LEAF(node) || ((struct tnode *) node)->pos >
744
		   tn->pos + tn->bits - 1) {
745 746 747
			if (tkey_extract_bits(node->key,
					      oldtnode->pos + oldtnode->bits,
					      1) == 0)
748 749 750 751 752 753 754 755 756 757 758 759 760
				put_child(t, tn, 2*i, node);
			else
				put_child(t, tn, 2*i+1, node);
			continue;
		}

		/* An internal node with two children */
		inode = (struct tnode *) node;

		if (inode->bits == 1) {
			put_child(t, tn, 2*i, inode->child[0]);
			put_child(t, tn, 2*i+1, inode->child[1]);

J
Jarek Poplawski 已提交
761
			tnode_free_safe(inode);
O
Olof Johansson 已提交
762
			continue;
763 764
		}

O
Olof Johansson 已提交
765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782
		/* An internal node with more than two children */

		/* We will replace this node 'inode' with two new
		 * ones, 'left' and 'right', each with half of the
		 * original children. The two new nodes will have
		 * a position one bit further down the key and this
		 * means that the "significant" part of their keys
		 * (see the discussion near the top of this file)
		 * will differ by one bit, which will be "0" in
		 * left's key and "1" in right's key. Since we are
		 * moving the key position by one step, the bit that
		 * we are moving away from - the bit at position
		 * (inode->pos) - is the one that will differ between
		 * left and right. So... we synthesize that bit in the
		 * two  new keys.
		 * The mask 'm' below will be a single "one" bit at
		 * the position (inode->pos)
		 */
783

O
Olof Johansson 已提交
784 785 786
		/* Use the old key, but set the new significant
		 *   bit to zero.
		 */
787

O
Olof Johansson 已提交
788 789
		left = (struct tnode *) tnode_get_child(tn, 2*i);
		put_child(t, tn, 2*i, NULL);
790

O
Olof Johansson 已提交
791
		BUG_ON(!left);
792

O
Olof Johansson 已提交
793 794
		right = (struct tnode *) tnode_get_child(tn, 2*i+1);
		put_child(t, tn, 2*i+1, NULL);
795

O
Olof Johansson 已提交
796
		BUG_ON(!right);
797

O
Olof Johansson 已提交
798 799 800 801
		size = tnode_child_length(left);
		for (j = 0; j < size; j++) {
			put_child(t, left, j, inode->child[j]);
			put_child(t, right, j, inode->child[j + size]);
802
		}
O
Olof Johansson 已提交
803 804 805
		put_child(t, tn, 2*i, resize(t, left));
		put_child(t, tn, 2*i+1, resize(t, right));

J
Jarek Poplawski 已提交
806
		tnode_free_safe(inode);
807
	}
J
Jarek Poplawski 已提交
808
	tnode_free_safe(oldtnode);
809
	return tn;
810 811 812 813 814
nomem:
	{
		int size = tnode_child_length(tn);
		int j;

S
Stephen Hemminger 已提交
815
		for (j = 0; j < size; j++)
816 817 818 819
			if (tn->child[j])
				tnode_free((struct tnode *)tn->child[j]);

		tnode_free(tn);
S
Stephen Hemminger 已提交
820

821 822
		return ERR_PTR(-ENOMEM);
	}
823 824
}

825
static struct tnode *halve(struct trie *t, struct tnode *tn)
826 827
{
	struct tnode *oldtnode = tn;
828
	struct rt_trie_node *left, *right;
829 830 831
	int i;
	int olen = tnode_child_length(tn);

S
Stephen Hemminger 已提交
832
	pr_debug("In halve\n");
833 834

	tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
835

836 837
	if (!tn)
		return ERR_PTR(-ENOMEM);
838 839

	/*
840 841 842
	 * Preallocate and store tnodes before the actual work so we
	 * don't get into an inconsistent state if memory allocation
	 * fails. In case of failure we return the oldnode and halve
843 844 845
	 * of tnode is ignored.
	 */

O
Olof Johansson 已提交
846
	for (i = 0; i < olen; i += 2) {
847 848
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
849

850
		/* Two nonempty children */
S
Stephen Hemminger 已提交
851
		if (left && right) {
852
			struct tnode *newn;
S
Stephen Hemminger 已提交
853

854
			newn = tnode_new(left->key, tn->pos + tn->bits, 1);
S
Stephen Hemminger 已提交
855 856

			if (!newn)
857
				goto nomem;
S
Stephen Hemminger 已提交
858

859
			put_child(t, tn, i/2, (struct rt_trie_node *)newn);
860 861 862
		}

	}
863

O
Olof Johansson 已提交
864 865 866
	for (i = 0; i < olen; i += 2) {
		struct tnode *newBinNode;

867 868
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
869

870 871 872 873 874
		/* At least one of the children is empty */
		if (left == NULL) {
			if (right == NULL)    /* Both are empty */
				continue;
			put_child(t, tn, i/2, right);
O
Olof Johansson 已提交
875
			continue;
S
Stephen Hemminger 已提交
876
		}
O
Olof Johansson 已提交
877 878

		if (right == NULL) {
879
			put_child(t, tn, i/2, left);
O
Olof Johansson 已提交
880 881
			continue;
		}
882

883
		/* Two nonempty children */
O
Olof Johansson 已提交
884 885 886 887 888
		newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
		put_child(t, tn, i/2, NULL);
		put_child(t, newBinNode, 0, left);
		put_child(t, newBinNode, 1, right);
		put_child(t, tn, i/2, resize(t, newBinNode));
889
	}
J
Jarek Poplawski 已提交
890
	tnode_free_safe(oldtnode);
891
	return tn;
892 893 894 895 896
nomem:
	{
		int size = tnode_child_length(tn);
		int j;

S
Stephen Hemminger 已提交
897
		for (j = 0; j < size; j++)
898 899 900 901
			if (tn->child[j])
				tnode_free((struct tnode *)tn->child[j]);

		tnode_free(tn);
S
Stephen Hemminger 已提交
902

903 904
		return ERR_PTR(-ENOMEM);
	}
905 906
}

R
Robert Olsson 已提交
907
/* readside must use rcu_read_lock currently dump routines
R
Robert Olsson 已提交
908 909
 via get_fa_head and dump */

R
Robert Olsson 已提交
910
static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
911
{
R
Robert Olsson 已提交
912
	struct hlist_head *head = &l->list;
913 914 915
	struct hlist_node *node;
	struct leaf_info *li;

R
Robert Olsson 已提交
916
	hlist_for_each_entry_rcu(li, node, head, hlist)
917
		if (li->plen == plen)
918
			return li;
O
Olof Johansson 已提交
919

920 921 922
	return NULL;
}

923
static inline struct list_head *get_fa_head(struct leaf *l, int plen)
924
{
R
Robert Olsson 已提交
925
	struct leaf_info *li = find_leaf_info(l, plen);
926

O
Olof Johansson 已提交
927 928
	if (!li)
		return NULL;
929

O
Olof Johansson 已提交
930
	return &li->falh;
931 932 933 934
}

static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
{
935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951
	struct leaf_info *li = NULL, *last = NULL;
	struct hlist_node *node;

	if (hlist_empty(head)) {
		hlist_add_head_rcu(&new->hlist, head);
	} else {
		hlist_for_each_entry(li, node, head, hlist) {
			if (new->plen > li->plen)
				break;

			last = li;
		}
		if (last)
			hlist_add_after_rcu(&last->hlist, &new->hlist);
		else
			hlist_add_before_rcu(&new->hlist, &li->hlist);
	}
952 953
}

R
Robert Olsson 已提交
954 955
/* rcu_read_lock needs to be hold by caller from readside */

956 957 958 959 960
static struct leaf *
fib_find_node(struct trie *t, u32 key)
{
	int pos;
	struct tnode *tn;
961
	struct rt_trie_node *n;
962 963

	pos = 0;
E
Eric Dumazet 已提交
964
	n = rcu_dereference_rtnl(t->trie);
965 966 967

	while (n != NULL &&  NODE_TYPE(n) == T_TNODE) {
		tn = (struct tnode *) n;
O
Olof Johansson 已提交
968

969
		check_tnode(tn);
O
Olof Johansson 已提交
970

971
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
O
Olof Johansson 已提交
972
			pos = tn->pos + tn->bits;
973 974 975 976
			n = tnode_get_child_rcu(tn,
						tkey_extract_bits(key,
								  tn->pos,
								  tn->bits));
O
Olof Johansson 已提交
977
		} else
978 979 980 981
			break;
	}
	/* Case we have found a leaf. Compare prefixes */

O
Olof Johansson 已提交
982 983 984
	if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
		return (struct leaf *)n;

985 986 987
	return NULL;
}

988
static void trie_rebalance(struct trie *t, struct tnode *tn)
989 990
{
	int wasfull;
R
Robert Olsson 已提交
991
	t_key cindex, key;
S
Stephen Hemminger 已提交
992
	struct tnode *tp;
993

R
Robert Olsson 已提交
994 995
	key = tn->key;

996
	while (tn != NULL && (tp = node_parent((struct rt_trie_node *)tn)) != NULL) {
997 998
		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
		wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
999 1000 1001
		tn = (struct tnode *) resize(t, (struct tnode *)tn);

		tnode_put_child_reorg((struct tnode *)tp, cindex,
1002
				      (struct rt_trie_node *)tn, wasfull);
O
Olof Johansson 已提交
1003

1004
		tp = node_parent((struct rt_trie_node *) tn);
1005
		if (!tp)
1006
			rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1007

J
Jarek Poplawski 已提交
1008
		tnode_free_flush();
S
Stephen Hemminger 已提交
1009
		if (!tp)
1010
			break;
S
Stephen Hemminger 已提交
1011
		tn = tp;
1012
	}
S
Stephen Hemminger 已提交
1013

1014
	/* Handle last (top) tnode */
1015
	if (IS_TNODE(tn))
1016
		tn = (struct tnode *)resize(t, (struct tnode *)tn);
1017

1018
	rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1019
	tnode_free_flush();
1020 1021
}

R
Robert Olsson 已提交
1022 1023
/* only used from updater-side */

1024
static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
1025 1026 1027
{
	int pos, newpos;
	struct tnode *tp = NULL, *tn = NULL;
1028
	struct rt_trie_node *n;
1029 1030
	struct leaf *l;
	int missbit;
1031
	struct list_head *fa_head = NULL;
1032 1033 1034 1035
	struct leaf_info *li;
	t_key cindex;

	pos = 0;
1036
	n = t->trie;
1037

1038 1039
	/* If we point to NULL, stop. Either the tree is empty and we should
	 * just put a new leaf in if, or we have reached an empty child slot,
1040
	 * and we should just put our new leaf in that.
1041 1042
	 * If we point to a T_TNODE, check if it matches our key. Note that
	 * a T_TNODE might be skipping any number of bits - its 'pos' need
1043 1044
	 * not be the parent's 'pos'+'bits'!
	 *
1045
	 * If it does match the current key, get pos/bits from it, extract
1046 1047 1048 1049
	 * the index from our key, push the T_TNODE and walk the tree.
	 *
	 * If it doesn't, we have to replace it with a new T_TNODE.
	 *
1050 1051 1052
	 * If we point to a T_LEAF, it might or might not have the same key
	 * as we do. If it does, just change the value, update the T_LEAF's
	 * value, and return it.
1053 1054 1055 1056 1057
	 * If it doesn't, we need to replace it with a T_TNODE.
	 */

	while (n != NULL &&  NODE_TYPE(n) == T_TNODE) {
		tn = (struct tnode *) n;
O
Olof Johansson 已提交
1058

1059
		check_tnode(tn);
O
Olof Johansson 已提交
1060

1061
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1062
			tp = tn;
O
Olof Johansson 已提交
1063
			pos = tn->pos + tn->bits;
1064 1065 1066 1067
			n = tnode_get_child(tn,
					    tkey_extract_bits(key,
							      tn->pos,
							      tn->bits));
1068

S
Stephen Hemminger 已提交
1069
			BUG_ON(n && node_parent(n) != tn);
O
Olof Johansson 已提交
1070
		} else
1071 1072 1073 1074 1075 1076
			break;
	}

	/*
	 * n  ----> NULL, LEAF or TNODE
	 *
1077
	 * tp is n's (parent) ----> NULL or TNODE
1078 1079
	 */

O
Olof Johansson 已提交
1080
	BUG_ON(tp && IS_LEAF(tp));
1081 1082 1083

	/* Case 1: n is a leaf. Compare prefixes */

1084
	if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1085
		l = (struct leaf *) n;
1086
		li = leaf_info_new(plen);
O
Olof Johansson 已提交
1087

1088 1089
		if (!li)
			return NULL;
1090 1091 1092 1093 1094 1095 1096

		fa_head = &li->falh;
		insert_leaf_info(&l->list, li);
		goto done;
	}
	l = leaf_new();

1097 1098
	if (!l)
		return NULL;
1099 1100 1101 1102

	l->key = key;
	li = leaf_info_new(plen);

1103
	if (!li) {
1104
		free_leaf(l);
1105
		return NULL;
1106
	}
1107 1108 1109 1110 1111

	fa_head = &li->falh;
	insert_leaf_info(&l->list, li);

	if (t->trie && n == NULL) {
O
Olof Johansson 已提交
1112
		/* Case 2: n is NULL, and will just insert a new leaf */
1113

1114
		node_set_parent((struct rt_trie_node *)l, tp);
1115

O
Olof Johansson 已提交
1116
		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1117
		put_child(t, (struct tnode *)tp, cindex, (struct rt_trie_node *)l);
O
Olof Johansson 已提交
1118 1119
	} else {
		/* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1120 1121
		/*
		 *  Add a new tnode here
1122 1123 1124 1125
		 *  first tnode need some special handling
		 */

		if (tp)
O
Olof Johansson 已提交
1126
			pos = tp->pos+tp->bits;
1127
		else
O
Olof Johansson 已提交
1128 1129
			pos = 0;

1130
		if (n) {
1131 1132
			newpos = tkey_mismatch(key, pos, n->key);
			tn = tnode_new(n->key, newpos, 1);
O
Olof Johansson 已提交
1133
		} else {
1134
			newpos = 0;
1135
			tn = tnode_new(key, newpos, 1); /* First tnode */
1136 1137
		}

1138
		if (!tn) {
1139
			free_leaf_info(li);
1140
			free_leaf(l);
1141
			return NULL;
O
Olof Johansson 已提交
1142 1143
		}

1144
		node_set_parent((struct rt_trie_node *)tn, tp);
1145

O
Olof Johansson 已提交
1146
		missbit = tkey_extract_bits(key, newpos, 1);
1147
		put_child(t, tn, missbit, (struct rt_trie_node *)l);
1148 1149
		put_child(t, tn, 1-missbit, n);

1150
		if (tp) {
1151
			cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1152
			put_child(t, (struct tnode *)tp, cindex,
1153
				  (struct rt_trie_node *)tn);
O
Olof Johansson 已提交
1154
		} else {
1155
			rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1156 1157 1158
			tp = tn;
		}
	}
O
Olof Johansson 已提交
1159 1160

	if (tp && tp->pos + tp->bits > 32)
1161 1162 1163
		pr_warning("fib_trie"
			   " tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
			   tp, tp->pos, tp->bits, key, plen);
O
Olof Johansson 已提交
1164

1165
	/* Rebalance the trie */
R
Robert Olsson 已提交
1166

1167
	trie_rebalance(t, tp);
1168
done:
1169 1170 1171
	return fa_head;
}

1172 1173 1174
/*
 * Caller must hold RTNL.
 */
1175
int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
1176 1177 1178
{
	struct trie *t = (struct trie *) tb->tb_data;
	struct fib_alias *fa, *new_fa;
1179
	struct list_head *fa_head = NULL;
1180
	struct fib_info *fi;
1181 1182
	int plen = cfg->fc_dst_len;
	u8 tos = cfg->fc_tos;
1183 1184 1185 1186 1187 1188 1189
	u32 key, mask;
	int err;
	struct leaf *l;

	if (plen > 32)
		return -EINVAL;

1190
	key = ntohl(cfg->fc_dst);
1191

1192
	pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1193

O
Olof Johansson 已提交
1194
	mask = ntohl(inet_make_mask(plen));
1195

1196
	if (key & ~mask)
1197 1198 1199 1200
		return -EINVAL;

	key = key & mask;

1201 1202 1203
	fi = fib_create_info(cfg);
	if (IS_ERR(fi)) {
		err = PTR_ERR(fi);
1204
		goto err;
1205
	}
1206 1207

	l = fib_find_node(t, key);
1208
	fa = NULL;
1209

1210
	if (l) {
1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225
		fa_head = get_fa_head(l, plen);
		fa = fib_find_alias(fa_head, tos, fi->fib_priority);
	}

	/* Now fa, if non-NULL, points to the first fib alias
	 * with the same keys [prefix,tos,priority], if such key already
	 * exists or to the node before which we will insert new one.
	 *
	 * If fa is NULL, we will need to allocate a new one and
	 * insert to the head of f.
	 *
	 * If f is NULL, no fib node matched the destination key
	 * and we need to allocate a new one of those as well.
	 */

1226 1227 1228
	if (fa && fa->fa_tos == tos &&
	    fa->fa_info->fib_priority == fi->fib_priority) {
		struct fib_alias *fa_first, *fa_match;
1229 1230

		err = -EEXIST;
1231
		if (cfg->fc_nlflags & NLM_F_EXCL)
1232 1233
			goto out;

1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254
		/* We have 2 goals:
		 * 1. Find exact match for type, scope, fib_info to avoid
		 * duplicate routes
		 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
		 */
		fa_match = NULL;
		fa_first = fa;
		fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
		list_for_each_entry_continue(fa, fa_head, fa_list) {
			if (fa->fa_tos != tos)
				break;
			if (fa->fa_info->fib_priority != fi->fib_priority)
				break;
			if (fa->fa_type == cfg->fc_type &&
			    fa->fa_scope == cfg->fc_scope &&
			    fa->fa_info == fi) {
				fa_match = fa;
				break;
			}
		}

1255
		if (cfg->fc_nlflags & NLM_F_REPLACE) {
1256 1257 1258
			struct fib_info *fi_drop;
			u8 state;

1259 1260 1261 1262
			fa = fa_first;
			if (fa_match) {
				if (fa == fa_match)
					err = 0;
1263
				goto out;
1264
			}
R
Robert Olsson 已提交
1265
			err = -ENOBUFS;
1266
			new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
R
Robert Olsson 已提交
1267 1268
			if (new_fa == NULL)
				goto out;
1269 1270

			fi_drop = fa->fa_info;
R
Robert Olsson 已提交
1271 1272
			new_fa->fa_tos = fa->fa_tos;
			new_fa->fa_info = fi;
1273 1274
			new_fa->fa_type = cfg->fc_type;
			new_fa->fa_scope = cfg->fc_scope;
1275
			state = fa->fa_state;
1276
			new_fa->fa_state = state & ~FA_S_ACCESSED;
1277

R
Robert Olsson 已提交
1278 1279
			list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
			alias_free_mem_rcu(fa);
1280 1281 1282

			fib_release_info(fi_drop);
			if (state & FA_S_ACCESSED)
1283
				rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1284 1285
			rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
				tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1286

O
Olof Johansson 已提交
1287
			goto succeeded;
1288 1289 1290 1291 1292
		}
		/* Error if we find a perfect match which
		 * uses the same scope, type, and nexthop
		 * information.
		 */
1293 1294
		if (fa_match)
			goto out;
1295

1296
		if (!(cfg->fc_nlflags & NLM_F_APPEND))
1297
			fa = fa_first;
1298 1299
	}
	err = -ENOENT;
1300
	if (!(cfg->fc_nlflags & NLM_F_CREATE))
1301 1302 1303
		goto out;

	err = -ENOBUFS;
1304
	new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1305 1306 1307 1308 1309
	if (new_fa == NULL)
		goto out;

	new_fa->fa_info = fi;
	new_fa->fa_tos = tos;
1310 1311
	new_fa->fa_type = cfg->fc_type;
	new_fa->fa_scope = cfg->fc_scope;
1312 1313 1314 1315 1316
	new_fa->fa_state = 0;
	/*
	 * Insert new entry to the list.
	 */

1317
	if (!fa_head) {
1318 1319 1320
		fa_head = fib_insert_node(t, key, plen);
		if (unlikely(!fa_head)) {
			err = -ENOMEM;
1321
			goto out_free_new_fa;
1322
		}
1323
	}
1324

R
Robert Olsson 已提交
1325 1326
	list_add_tail_rcu(&new_fa->fa_list,
			  (fa ? &fa->fa_list : fa_head));
1327

1328
	rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1329
	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1330
		  &cfg->fc_nlinfo, 0);
1331 1332
succeeded:
	return 0;
1333 1334 1335

out_free_new_fa:
	kmem_cache_free(fn_alias_kmem, new_fa);
1336 1337
out:
	fib_release_info(fi);
O
Olof Johansson 已提交
1338
err:
1339 1340 1341
	return err;
}

R
Robert Olsson 已提交
1342
/* should be called with rcu_read_lock */
1343
static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
1344
		      t_key key,  const struct flowi *flp,
E
Eric Dumazet 已提交
1345
		      struct fib_result *res, int fib_flags)
1346 1347 1348 1349
{
	struct leaf_info *li;
	struct hlist_head *hhead = &l->list;
	struct hlist_node *node;
1350

R
Robert Olsson 已提交
1351
	hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1352 1353 1354 1355
		int err;
		int plen = li->plen;
		__be32 mask = inet_make_mask(plen);

1356
		if (l->key != (key & ntohl(mask)))
1357 1358
			continue;

1359
		err = fib_semantic_match(tb, &li->falh, flp, res, plen, fib_flags);
1360

1361
#ifdef CONFIG_IP_FIB_TRIE_STATS
1362
		if (err <= 0)
1363
			t->stats.semantic_match_passed++;
1364 1365
		else
			t->stats.semantic_match_miss++;
1366
#endif
1367
		if (err <= 0)
1368
			return err;
1369
	}
1370

1371
	return 1;
1372 1373
}

1374
int fib_table_lookup(struct fib_table *tb, const struct flowi *flp,
E
Eric Dumazet 已提交
1375
		     struct fib_result *res, int fib_flags)
1376 1377
{
	struct trie *t = (struct trie *) tb->tb_data;
1378
	int ret;
1379
	struct rt_trie_node *n;
1380 1381
	struct tnode *pn;
	int pos, bits;
O
Olof Johansson 已提交
1382
	t_key key = ntohl(flp->fl4_dst);
1383 1384 1385
	int chopped_off;
	t_key cindex = 0;
	int current_prefix_length = KEYLENGTH;
O
Olof Johansson 已提交
1386
	struct tnode *cn;
1387
	t_key pref_mismatch;
O
Olof Johansson 已提交
1388

R
Robert Olsson 已提交
1389
	rcu_read_lock();
O
Olof Johansson 已提交
1390

R
Robert Olsson 已提交
1391
	n = rcu_dereference(t->trie);
1392
	if (!n)
1393 1394 1395 1396 1397 1398 1399 1400
		goto failed;

#ifdef CONFIG_IP_FIB_TRIE_STATS
	t->stats.gets++;
#endif

	/* Just a leaf? */
	if (IS_LEAF(n)) {
1401
		ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1402
		goto found;
1403
	}
1404

1405 1406
	pn = (struct tnode *) n;
	chopped_off = 0;
1407

O
Olof Johansson 已提交
1408
	while (pn) {
1409 1410 1411
		pos = pn->pos;
		bits = pn->bits;

1412
		if (!chopped_off)
S
Stephen Hemminger 已提交
1413 1414
			cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
						   pos, bits);
1415

1416
		n = tnode_get_child_rcu(pn, cindex);
1417 1418 1419 1420 1421 1422 1423 1424

		if (n == NULL) {
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.null_node_hit++;
#endif
			goto backtrace;
		}

O
Olof Johansson 已提交
1425
		if (IS_LEAF(n)) {
1426
			ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1427
			if (ret > 0)
O
Olof Johansson 已提交
1428
				goto backtrace;
1429
			goto found;
O
Olof Johansson 已提交
1430 1431 1432
		}

		cn = (struct tnode *)n;
1433

O
Olof Johansson 已提交
1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448
		/*
		 * It's a tnode, and we can do some extra checks here if we
		 * like, to avoid descending into a dead-end branch.
		 * This tnode is in the parent's child array at index
		 * key[p_pos..p_pos+p_bits] but potentially with some bits
		 * chopped off, so in reality the index may be just a
		 * subprefix, padded with zero at the end.
		 * We can also take a look at any skipped bits in this
		 * tnode - everything up to p_pos is supposed to be ok,
		 * and the non-chopped bits of the index (se previous
		 * paragraph) are also guaranteed ok, but the rest is
		 * considered unknown.
		 *
		 * The skipped bits are key[pos+bits..cn->pos].
		 */
1449

O
Olof Johansson 已提交
1450 1451 1452 1453 1454 1455 1456 1457 1458
		/* If current_prefix_length < pos+bits, we are already doing
		 * actual prefix  matching, which means everything from
		 * pos+(bits-chopped_off) onward must be zero along some
		 * branch of this subtree - otherwise there is *no* valid
		 * prefix present. Here we can only check the skipped
		 * bits. Remember, since we have already indexed into the
		 * parent's child array, we know that the bits we chopped of
		 * *are* zero.
		 */
1459

1460 1461
		/* NOTA BENE: Checking only skipped bits
		   for the new node here */
1462

O
Olof Johansson 已提交
1463 1464
		if (current_prefix_length < pos+bits) {
			if (tkey_extract_bits(cn->key, current_prefix_length,
1465 1466
						cn->pos - current_prefix_length)
			    || !(cn->child[0]))
O
Olof Johansson 已提交
1467 1468
				goto backtrace;
		}
1469

O
Olof Johansson 已提交
1470 1471 1472 1473 1474 1475 1476 1477 1478
		/*
		 * If chopped_off=0, the index is fully validated and we
		 * only need to look at the skipped bits for this, the new,
		 * tnode. What we actually want to do is to find out if
		 * these skipped bits match our key perfectly, or if we will
		 * have to count on finding a matching prefix further down,
		 * because if we do, we would like to have some way of
		 * verifying the existence of such a prefix at this point.
		 */
1479

O
Olof Johansson 已提交
1480 1481 1482 1483 1484 1485 1486 1487
		/* The only thing we can do at this point is to verify that
		 * any such matching prefix can indeed be a prefix to our
		 * key, and if the bits in the node we are inspecting that
		 * do not match our key are not ZERO, this cannot be true.
		 * Thus, find out where there is a mismatch (before cn->pos)
		 * and verify that all the mismatching bits are zero in the
		 * new tnode's key.
		 */
1488

1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499
		/*
		 * Note: We aren't very concerned about the piece of
		 * the key that precede pn->pos+pn->bits, since these
		 * have already been checked. The bits after cn->pos
		 * aren't checked since these are by definition
		 * "unknown" at this point. Thus, what we want to see
		 * is if we are about to enter the "prefix matching"
		 * state, and in that case verify that the skipped
		 * bits that will prevail throughout this subtree are
		 * zero, as they have to be if we are to find a
		 * matching prefix.
O
Olof Johansson 已提交
1500 1501
		 */

1502
		pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
O
Olof Johansson 已提交
1503

1504 1505 1506 1507
		/*
		 * In short: If skipped bits in this node do not match
		 * the search key, enter the "prefix matching"
		 * state.directly.
O
Olof Johansson 已提交
1508 1509
		 */
		if (pref_mismatch) {
1510
			int mp = KEYLENGTH - fls(pref_mismatch);
O
Olof Johansson 已提交
1511

1512
			if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
O
Olof Johansson 已提交
1513 1514 1515 1516
				goto backtrace;

			if (current_prefix_length >= cn->pos)
				current_prefix_length = mp;
1517
		}
1518

O
Olof Johansson 已提交
1519 1520 1521 1522
		pn = (struct tnode *)n; /* Descend */
		chopped_off = 0;
		continue;

1523 1524 1525 1526
backtrace:
		chopped_off++;

		/* As zero don't change the child key (cindex) */
1527 1528
		while ((chopped_off <= pn->bits)
		       && !(cindex & (1<<(chopped_off-1))))
1529 1530 1531 1532
			chopped_off++;

		/* Decrease current_... with bits chopped off */
		if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1533 1534
			current_prefix_length = pn->pos + pn->bits
				- chopped_off;
O
Olof Johansson 已提交
1535

1536
		/*
1537
		 * Either we do the actual chop off according or if we have
1538 1539 1540
		 * chopped off all bits in this tnode walk up to our parent.
		 */

O
Olof Johansson 已提交
1541
		if (chopped_off <= pn->bits) {
1542
			cindex &= ~(1 << (chopped_off-1));
O
Olof Johansson 已提交
1543
		} else {
1544
			struct tnode *parent = node_parent_rcu((struct rt_trie_node *) pn);
S
Stephen Hemminger 已提交
1545
			if (!parent)
1546
				goto failed;
O
Olof Johansson 已提交
1547

1548
			/* Get Child's index */
S
Stephen Hemminger 已提交
1549 1550
			cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
			pn = parent;
1551 1552 1553 1554 1555 1556
			chopped_off = 0;

#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.backtrack++;
#endif
			goto backtrace;
1557
		}
1558 1559
	}
failed:
1560
	ret = 1;
1561
found:
R
Robert Olsson 已提交
1562
	rcu_read_unlock();
1563 1564 1565
	return ret;
}

1566 1567 1568 1569
/*
 * Remove the leaf and return parent.
 */
static void trie_leaf_remove(struct trie *t, struct leaf *l)
1570
{
1571
	struct tnode *tp = node_parent((struct rt_trie_node *) l);
1572

1573
	pr_debug("entering trie_leaf_remove(%p)\n", l);
1574

1575
	if (tp) {
1576
		t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1577
		put_child(t, (struct tnode *)tp, cindex, NULL);
1578
		trie_rebalance(t, tp);
O
Olof Johansson 已提交
1579
	} else
R
Robert Olsson 已提交
1580
		rcu_assign_pointer(t->trie, NULL);
1581

1582
	free_leaf(l);
1583 1584
}

1585 1586 1587
/*
 * Caller must hold RTNL.
 */
1588
int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
1589 1590 1591
{
	struct trie *t = (struct trie *) tb->tb_data;
	u32 key, mask;
1592 1593
	int plen = cfg->fc_dst_len;
	u8 tos = cfg->fc_tos;
1594 1595 1596
	struct fib_alias *fa, *fa_to_delete;
	struct list_head *fa_head;
	struct leaf *l;
O
Olof Johansson 已提交
1597 1598
	struct leaf_info *li;

1599
	if (plen > 32)
1600 1601
		return -EINVAL;

1602
	key = ntohl(cfg->fc_dst);
O
Olof Johansson 已提交
1603
	mask = ntohl(inet_make_mask(plen));
1604

1605
	if (key & ~mask)
1606 1607 1608 1609 1610
		return -EINVAL;

	key = key & mask;
	l = fib_find_node(t, key);

1611
	if (!l)
1612 1613 1614 1615 1616 1617 1618 1619
		return -ESRCH;

	fa_head = get_fa_head(l, plen);
	fa = fib_find_alias(fa_head, tos, 0);

	if (!fa)
		return -ESRCH;

S
Stephen Hemminger 已提交
1620
	pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1621 1622

	fa_to_delete = NULL;
1623 1624
	fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
	list_for_each_entry_continue(fa, fa_head, fa_list) {
1625 1626 1627 1628 1629
		struct fib_info *fi = fa->fa_info;

		if (fa->fa_tos != tos)
			break;

1630 1631 1632 1633 1634 1635
		if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
		    (cfg->fc_scope == RT_SCOPE_NOWHERE ||
		     fa->fa_scope == cfg->fc_scope) &&
		    (!cfg->fc_protocol ||
		     fi->fib_protocol == cfg->fc_protocol) &&
		    fib_nh_match(cfg, fi) == 0) {
1636 1637 1638 1639 1640
			fa_to_delete = fa;
			break;
		}
	}

O
Olof Johansson 已提交
1641 1642
	if (!fa_to_delete)
		return -ESRCH;
1643

O
Olof Johansson 已提交
1644
	fa = fa_to_delete;
1645
	rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1646
		  &cfg->fc_nlinfo, 0);
O
Olof Johansson 已提交
1647 1648

	l = fib_find_node(t, key);
R
Robert Olsson 已提交
1649
	li = find_leaf_info(l, plen);
1650

R
Robert Olsson 已提交
1651
	list_del_rcu(&fa->fa_list);
1652

O
Olof Johansson 已提交
1653
	if (list_empty(fa_head)) {
R
Robert Olsson 已提交
1654
		hlist_del_rcu(&li->hlist);
O
Olof Johansson 已提交
1655
		free_leaf_info(li);
R
Robert Olsson 已提交
1656
	}
1657

O
Olof Johansson 已提交
1658
	if (hlist_empty(&l->list))
1659
		trie_leaf_remove(t, l);
1660

O
Olof Johansson 已提交
1661
	if (fa->fa_state & FA_S_ACCESSED)
1662
		rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1663

R
Robert Olsson 已提交
1664 1665
	fib_release_info(fa->fa_info);
	alias_free_mem_rcu(fa);
O
Olof Johansson 已提交
1666
	return 0;
1667 1668
}

1669
static int trie_flush_list(struct list_head *head)
1670 1671 1672 1673 1674 1675 1676
{
	struct fib_alias *fa, *fa_node;
	int found = 0;

	list_for_each_entry_safe(fa, fa_node, head, fa_list) {
		struct fib_info *fi = fa->fa_info;

R
Robert Olsson 已提交
1677 1678 1679 1680
		if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
			list_del_rcu(&fa->fa_list);
			fib_release_info(fa->fa_info);
			alias_free_mem_rcu(fa);
1681 1682 1683 1684 1685 1686
			found++;
		}
	}
	return found;
}

1687
static int trie_flush_leaf(struct leaf *l)
1688 1689 1690 1691 1692 1693 1694
{
	int found = 0;
	struct hlist_head *lih = &l->list;
	struct hlist_node *node, *tmp;
	struct leaf_info *li = NULL;

	hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
1695
		found += trie_flush_list(&li->falh);
1696 1697

		if (list_empty(&li->falh)) {
R
Robert Olsson 已提交
1698
			hlist_del_rcu(&li->hlist);
1699 1700 1701 1702 1703 1704
			free_leaf_info(li);
		}
	}
	return found;
}

1705 1706 1707 1708
/*
 * Scan for the next right leaf starting at node p->child[idx]
 * Since we have back pointer, no recursion necessary.
 */
1709
static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1710
{
1711 1712
	do {
		t_key idx;
1713 1714

		if (c)
1715
			idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1716
		else
1717
			idx = 0;
R
Robert Olsson 已提交
1718

1719 1720
		while (idx < 1u << p->bits) {
			c = tnode_get_child_rcu(p, idx++);
R
Robert Olsson 已提交
1721
			if (!c)
O
Olof Johansson 已提交
1722 1723
				continue;

1724 1725 1726
			if (IS_LEAF(c)) {
				prefetch(p->child[idx]);
				return (struct leaf *) c;
1727
			}
1728 1729 1730 1731

			/* Rescan start scanning in new node */
			p = (struct tnode *) c;
			idx = 0;
1732
		}
1733 1734

		/* Node empty, walk back up to parent */
1735
		c = (struct rt_trie_node *) p;
E
Eric Dumazet 已提交
1736
	} while ((p = node_parent_rcu(c)) != NULL);
1737 1738 1739 1740 1741 1742

	return NULL; /* Root of trie */
}

static struct leaf *trie_firstleaf(struct trie *t)
{
E
Eric Dumazet 已提交
1743
	struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755

	if (!n)
		return NULL;

	if (IS_LEAF(n))          /* trie is just a leaf */
		return (struct leaf *) n;

	return leaf_walk_rcu(n, NULL);
}

static struct leaf *trie_nextleaf(struct leaf *l)
{
1756
	struct rt_trie_node *c = (struct rt_trie_node *) l;
1757
	struct tnode *p = node_parent_rcu(c);
1758 1759 1760 1761 1762

	if (!p)
		return NULL;	/* trie with just one leaf */

	return leaf_walk_rcu(p, c);
1763 1764
}

1765 1766 1767 1768
static struct leaf *trie_leafindex(struct trie *t, int index)
{
	struct leaf *l = trie_firstleaf(t);

S
Stephen Hemminger 已提交
1769
	while (l && index-- > 0)
1770
		l = trie_nextleaf(l);
S
Stephen Hemminger 已提交
1771

1772 1773 1774 1775
	return l;
}


1776 1777 1778
/*
 * Caller must hold RTNL.
 */
1779
int fib_table_flush(struct fib_table *tb)
1780 1781
{
	struct trie *t = (struct trie *) tb->tb_data;
1782
	struct leaf *l, *ll = NULL;
1783
	int found = 0;
1784

1785
	for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1786
		found += trie_flush_leaf(l);
1787 1788

		if (ll && hlist_empty(&ll->list))
1789
			trie_leaf_remove(t, ll);
1790 1791 1792 1793
		ll = l;
	}

	if (ll && hlist_empty(&ll->list))
1794
		trie_leaf_remove(t, ll);
1795

S
Stephen Hemminger 已提交
1796
	pr_debug("trie_flush found=%d\n", found);
1797 1798 1799
	return found;
}

1800 1801 1802 1803 1804
void fib_free_table(struct fib_table *tb)
{
	kfree(tb);
}

1805 1806
static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
			   struct fib_table *tb,
1807 1808 1809 1810
			   struct sk_buff *skb, struct netlink_callback *cb)
{
	int i, s_i;
	struct fib_alias *fa;
A
Al Viro 已提交
1811
	__be32 xkey = htonl(key);
1812

1813
	s_i = cb->args[5];
1814 1815
	i = 0;

R
Robert Olsson 已提交
1816 1817 1818
	/* rcu_read_lock is hold by caller */

	list_for_each_entry_rcu(fa, fah, fa_list) {
1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829
		if (i < s_i) {
			i++;
			continue;
		}

		if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
				  cb->nlh->nlmsg_seq,
				  RTM_NEWROUTE,
				  tb->tb_id,
				  fa->fa_type,
				  fa->fa_scope,
1830
				  xkey,
1831 1832
				  plen,
				  fa->fa_tos,
1833
				  fa->fa_info, NLM_F_MULTI) < 0) {
1834
			cb->args[5] = i;
1835
			return -1;
O
Olof Johansson 已提交
1836
		}
1837 1838
		i++;
	}
1839
	cb->args[5] = i;
1840 1841 1842
	return skb->len;
}

1843 1844
static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
			struct sk_buff *skb, struct netlink_callback *cb)
1845
{
1846 1847 1848
	struct leaf_info *li;
	struct hlist_node *node;
	int i, s_i;
1849

1850
	s_i = cb->args[4];
1851
	i = 0;
1852

1853 1854 1855 1856
	/* rcu_read_lock is hold by caller */
	hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
		if (i < s_i) {
			i++;
1857
			continue;
1858
		}
O
Olof Johansson 已提交
1859

1860
		if (i > s_i)
1861
			cb->args[5] = 0;
1862

1863
		if (list_empty(&li->falh))
1864 1865
			continue;

1866
		if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1867
			cb->args[4] = i;
1868 1869
			return -1;
		}
1870
		i++;
1871
	}
1872

1873
	cb->args[4] = i;
1874 1875 1876
	return skb->len;
}

1877 1878
int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
		   struct netlink_callback *cb)
1879
{
1880
	struct leaf *l;
1881
	struct trie *t = (struct trie *) tb->tb_data;
1882
	t_key key = cb->args[2];
1883
	int count = cb->args[3];
1884

R
Robert Olsson 已提交
1885
	rcu_read_lock();
1886 1887 1888
	/* Dump starting at last key.
	 * Note: 0.0.0.0/0 (ie default) is first key.
	 */
1889
	if (count == 0)
1890 1891
		l = trie_firstleaf(t);
	else {
1892 1893 1894
		/* Normally, continue from last key, but if that is missing
		 * fallback to using slow rescan
		 */
1895
		l = fib_find_node(t, key);
1896 1897
		if (!l)
			l = trie_leafindex(t, count);
1898
	}
1899

1900 1901
	while (l) {
		cb->args[2] = l->key;
1902
		if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1903
			cb->args[3] = count;
1904 1905
			rcu_read_unlock();
			return -1;
1906
		}
1907

1908
		++count;
1909
		l = trie_nextleaf(l);
1910 1911
		memset(&cb->args[4], 0,
		       sizeof(cb->args) - 4*sizeof(cb->args[0]));
1912
	}
1913
	cb->args[3] = count;
R
Robert Olsson 已提交
1914
	rcu_read_unlock();
1915

1916 1917 1918
	return skb->len;
}

1919
void __init fib_trie_init(void)
1920
{
1921 1922
	fn_alias_kmem = kmem_cache_create("ip_fib_alias",
					  sizeof(struct fib_alias),
1923 1924 1925 1926 1927 1928
					  0, SLAB_PANIC, NULL);

	trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
					   max(sizeof(struct leaf),
					       sizeof(struct leaf_info)),
					   0, SLAB_PANIC, NULL);
1929
}
1930

1931

1932
struct fib_table *fib_trie_table(u32 id)
1933 1934 1935 1936 1937 1938 1939 1940 1941 1942
{
	struct fib_table *tb;
	struct trie *t;

	tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
		     GFP_KERNEL);
	if (tb == NULL)
		return NULL;

	tb->tb_id = id;
1943
	tb->tb_default = -1;
1944 1945

	t = (struct trie *) tb->tb_data;
1946
	memset(t, 0, sizeof(*t));
1947 1948

	if (id == RT_TABLE_LOCAL)
1949
		pr_info("IPv4 FIB: Using LC-trie version %s\n", VERSION);
1950 1951 1952 1953

	return tb;
}

1954 1955 1956
#ifdef CONFIG_PROC_FS
/* Depth first Trie walk iterator */
struct fib_trie_iter {
1957
	struct seq_net_private p;
1958
	struct fib_table *tb;
1959
	struct tnode *tnode;
E
Eric Dumazet 已提交
1960 1961
	unsigned int index;
	unsigned int depth;
1962
};
1963

1964
static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
1965
{
1966
	struct tnode *tn = iter->tnode;
E
Eric Dumazet 已提交
1967
	unsigned int cindex = iter->index;
1968
	struct tnode *p;
1969

1970 1971 1972 1973
	/* A single entry routing table */
	if (!tn)
		return NULL;

1974 1975 1976 1977
	pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
		 iter->tnode, iter->index, iter->depth);
rescan:
	while (cindex < (1<<tn->bits)) {
1978
		struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
1979

1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991
		if (n) {
			if (IS_LEAF(n)) {
				iter->tnode = tn;
				iter->index = cindex + 1;
			} else {
				/* push down one level */
				iter->tnode = (struct tnode *) n;
				iter->index = 0;
				++iter->depth;
			}
			return n;
		}
1992

1993 1994
		++cindex;
	}
O
Olof Johansson 已提交
1995

1996
	/* Current node exhausted, pop back up */
1997
	p = node_parent_rcu((struct rt_trie_node *)tn);
1998 1999 2000 2001 2002
	if (p) {
		cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
		tn = p;
		--iter->depth;
		goto rescan;
2003
	}
2004 2005 2006

	/* got root? */
	return NULL;
2007 2008
}

2009
static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
2010
				       struct trie *t)
2011
{
2012
	struct rt_trie_node *n;
2013

S
Stephen Hemminger 已提交
2014
	if (!t)
2015 2016 2017
		return NULL;

	n = rcu_dereference(t->trie);
2018
	if (!n)
2019
		return NULL;
2020

2021 2022 2023 2024 2025 2026 2027 2028
	if (IS_TNODE(n)) {
		iter->tnode = (struct tnode *) n;
		iter->index = 0;
		iter->depth = 1;
	} else {
		iter->tnode = NULL;
		iter->index = 0;
		iter->depth = 0;
O
Olof Johansson 已提交
2029
	}
2030 2031

	return n;
2032
}
O
Olof Johansson 已提交
2033

2034 2035
static void trie_collect_stats(struct trie *t, struct trie_stat *s)
{
2036
	struct rt_trie_node *n;
2037
	struct fib_trie_iter iter;
O
Olof Johansson 已提交
2038

2039
	memset(s, 0, sizeof(*s));
O
Olof Johansson 已提交
2040

2041
	rcu_read_lock();
2042
	for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2043
		if (IS_LEAF(n)) {
2044 2045 2046 2047
			struct leaf *l = (struct leaf *)n;
			struct leaf_info *li;
			struct hlist_node *tmp;

2048 2049 2050 2051
			s->leaves++;
			s->totdepth += iter.depth;
			if (iter.depth > s->maxdepth)
				s->maxdepth = iter.depth;
2052 2053 2054

			hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
				++s->prefixes;
2055 2056 2057 2058 2059
		} else {
			const struct tnode *tn = (const struct tnode *) n;
			int i;

			s->tnodes++;
S
Stephen Hemminger 已提交
2060
			if (tn->bits < MAX_STAT_DEPTH)
R
Robert Olsson 已提交
2061 2062
				s->nodesizes[tn->bits]++;

2063 2064 2065
			for (i = 0; i < (1<<tn->bits); i++)
				if (!tn->child[i])
					s->nullpointers++;
2066 2067
		}
	}
R
Robert Olsson 已提交
2068
	rcu_read_unlock();
2069 2070
}

2071 2072 2073 2074
/*
 *	This outputs /proc/net/fib_triestats
 */
static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2075
{
E
Eric Dumazet 已提交
2076
	unsigned int i, max, pointers, bytes, avdepth;
2077

2078 2079 2080 2081
	if (stat->leaves)
		avdepth = stat->totdepth*100 / stat->leaves;
	else
		avdepth = 0;
O
Olof Johansson 已提交
2082

2083 2084
	seq_printf(seq, "\tAver depth:     %u.%02d\n",
		   avdepth / 100, avdepth % 100);
2085
	seq_printf(seq, "\tMax depth:      %u\n", stat->maxdepth);
O
Olof Johansson 已提交
2086

2087 2088
	seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
	bytes = sizeof(struct leaf) * stat->leaves;
2089 2090 2091 2092

	seq_printf(seq, "\tPrefixes:       %u\n", stat->prefixes);
	bytes += sizeof(struct leaf_info) * stat->prefixes;

2093
	seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2094
	bytes += sizeof(struct tnode) * stat->tnodes;
2095

R
Robert Olsson 已提交
2096 2097
	max = MAX_STAT_DEPTH;
	while (max > 0 && stat->nodesizes[max-1] == 0)
2098
		max--;
2099

2100 2101 2102
	pointers = 0;
	for (i = 1; i <= max; i++)
		if (stat->nodesizes[i] != 0) {
2103
			seq_printf(seq, "  %u: %u",  i, stat->nodesizes[i]);
2104 2105 2106
			pointers += (1<<i) * stat->nodesizes[i];
		}
	seq_putc(seq, '\n');
2107
	seq_printf(seq, "\tPointers: %u\n", pointers);
R
Robert Olsson 已提交
2108

2109
	bytes += sizeof(struct rt_trie_node *) * pointers;
2110 2111
	seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
	seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
2112
}
R
Robert Olsson 已提交
2113

2114
#ifdef CONFIG_IP_FIB_TRIE_STATS
2115 2116 2117 2118
static void trie_show_usage(struct seq_file *seq,
			    const struct trie_use_stats *stats)
{
	seq_printf(seq, "\nCounters:\n---------\n");
2119 2120 2121 2122 2123 2124 2125 2126 2127
	seq_printf(seq, "gets = %u\n", stats->gets);
	seq_printf(seq, "backtracks = %u\n", stats->backtrack);
	seq_printf(seq, "semantic match passed = %u\n",
		   stats->semantic_match_passed);
	seq_printf(seq, "semantic match miss = %u\n",
		   stats->semantic_match_miss);
	seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
	seq_printf(seq, "skipped node resize = %u\n\n",
		   stats->resize_node_skipped);
2128
}
2129 2130
#endif /*  CONFIG_IP_FIB_TRIE_STATS */

2131
static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2132
{
2133 2134 2135 2136 2137 2138
	if (tb->tb_id == RT_TABLE_LOCAL)
		seq_puts(seq, "Local:\n");
	else if (tb->tb_id == RT_TABLE_MAIN)
		seq_puts(seq, "Main:\n");
	else
		seq_printf(seq, "Id %d:\n", tb->tb_id);
2139
}
2140

2141

2142 2143
static int fib_triestat_seq_show(struct seq_file *seq, void *v)
{
2144
	struct net *net = (struct net *)seq->private;
2145
	unsigned int h;
2146

2147
	seq_printf(seq,
2148 2149
		   "Basic info: size of leaf:"
		   " %Zd bytes, size of tnode: %Zd bytes.\n",
2150 2151
		   sizeof(struct leaf), sizeof(struct tnode));

2152 2153 2154 2155 2156 2157 2158 2159
	for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
		struct hlist_node *node;
		struct fib_table *tb;

		hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
			struct trie *t = (struct trie *) tb->tb_data;
			struct trie_stat stat;
2160

2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172
			if (!t)
				continue;

			fib_table_print(seq, tb);

			trie_collect_stats(t, &stat);
			trie_show_stats(seq, &stat);
#ifdef CONFIG_IP_FIB_TRIE_STATS
			trie_show_usage(seq, &t->stats);
#endif
		}
	}
2173

2174
	return 0;
2175 2176
}

2177
static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2178
{
2179
	return single_open_net(inode, file, fib_triestat_seq_show);
2180 2181
}

2182
static const struct file_operations fib_triestat_fops = {
2183 2184 2185 2186
	.owner	= THIS_MODULE,
	.open	= fib_triestat_seq_open,
	.read	= seq_read,
	.llseek	= seq_lseek,
2187
	.release = single_release_net,
2188 2189
};

2190
static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2191
{
2192 2193
	struct fib_trie_iter *iter = seq->private;
	struct net *net = seq_file_net(seq);
2194
	loff_t idx = 0;
2195
	unsigned int h;
2196

2197 2198 2199 2200
	for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
		struct hlist_node *node;
		struct fib_table *tb;
2201

2202
		hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2203
			struct rt_trie_node *n;
2204 2205 2206 2207 2208 2209 2210 2211 2212

			for (n = fib_trie_get_first(iter,
						    (struct trie *) tb->tb_data);
			     n; n = fib_trie_get_next(iter))
				if (pos == idx++) {
					iter->tb = tb;
					return n;
				}
		}
2213
	}
2214

2215 2216 2217
	return NULL;
}

2218
static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2219
	__acquires(RCU)
2220
{
2221
	rcu_read_lock();
2222
	return fib_trie_get_idx(seq, *pos);
2223 2224
}

2225
static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2226
{
2227
	struct fib_trie_iter *iter = seq->private;
2228
	struct net *net = seq_file_net(seq);
2229 2230 2231
	struct fib_table *tb = iter->tb;
	struct hlist_node *tb_node;
	unsigned int h;
2232
	struct rt_trie_node *n;
2233

2234
	++*pos;
2235 2236 2237 2238
	/* next node in same table */
	n = fib_trie_get_next(iter);
	if (n)
		return n;
2239

2240 2241 2242 2243 2244 2245 2246 2247
	/* walk rest of this hash chain */
	h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
	while ( (tb_node = rcu_dereference(tb->tb_hlist.next)) ) {
		tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
		n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
		if (n)
			goto found;
	}
2248

2249 2250 2251 2252 2253 2254 2255 2256 2257
	/* new hash chain */
	while (++h < FIB_TABLE_HASHSZ) {
		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
		hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) {
			n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
			if (n)
				goto found;
		}
	}
2258
	return NULL;
2259 2260 2261 2262

found:
	iter->tb = tb;
	return n;
2263
}
2264

2265
static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2266
	__releases(RCU)
2267
{
2268 2269
	rcu_read_unlock();
}
O
Olof Johansson 已提交
2270

2271 2272
static void seq_indent(struct seq_file *seq, int n)
{
E
Eric Dumazet 已提交
2273 2274
	while (n-- > 0)
		seq_puts(seq, "   ");
2275
}
2276

2277
static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2278
{
S
Stephen Hemminger 已提交
2279
	switch (s) {
2280 2281 2282 2283 2284 2285
	case RT_SCOPE_UNIVERSE: return "universe";
	case RT_SCOPE_SITE:	return "site";
	case RT_SCOPE_LINK:	return "link";
	case RT_SCOPE_HOST:	return "host";
	case RT_SCOPE_NOWHERE:	return "nowhere";
	default:
2286
		snprintf(buf, len, "scope=%d", s);
2287 2288 2289
		return buf;
	}
}
2290

2291
static const char *const rtn_type_names[__RTN_MAX] = {
2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304
	[RTN_UNSPEC] = "UNSPEC",
	[RTN_UNICAST] = "UNICAST",
	[RTN_LOCAL] = "LOCAL",
	[RTN_BROADCAST] = "BROADCAST",
	[RTN_ANYCAST] = "ANYCAST",
	[RTN_MULTICAST] = "MULTICAST",
	[RTN_BLACKHOLE] = "BLACKHOLE",
	[RTN_UNREACHABLE] = "UNREACHABLE",
	[RTN_PROHIBIT] = "PROHIBIT",
	[RTN_THROW] = "THROW",
	[RTN_NAT] = "NAT",
	[RTN_XRESOLVE] = "XRESOLVE",
};
2305

E
Eric Dumazet 已提交
2306
static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2307 2308 2309
{
	if (t < __RTN_MAX && rtn_type_names[t])
		return rtn_type_names[t];
2310
	snprintf(buf, len, "type %u", t);
2311
	return buf;
2312 2313
}

2314 2315
/* Pretty print the trie */
static int fib_trie_seq_show(struct seq_file *seq, void *v)
2316
{
2317
	const struct fib_trie_iter *iter = seq->private;
2318
	struct rt_trie_node *n = v;
2319

2320 2321
	if (!node_parent_rcu(n))
		fib_table_print(seq, iter->tb);
2322

2323 2324
	if (IS_TNODE(n)) {
		struct tnode *tn = (struct tnode *) n;
S
Stephen Hemminger 已提交
2325
		__be32 prf = htonl(mask_pfx(tn->key, tn->pos));
O
Olof Johansson 已提交
2326

2327
		seq_indent(seq, iter->depth-1);
2328 2329
		seq_printf(seq, "  +-- %pI4/%d %d %d %d\n",
			   &prf, tn->pos, tn->bits, tn->full_children,
2330
			   tn->empty_children);
2331

2332 2333
	} else {
		struct leaf *l = (struct leaf *) n;
2334 2335
		struct leaf_info *li;
		struct hlist_node *node;
A
Al Viro 已提交
2336
		__be32 val = htonl(l->key);
2337 2338

		seq_indent(seq, iter->depth);
2339
		seq_printf(seq, "  |-- %pI4\n", &val);
2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353

		hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
			struct fib_alias *fa;

			list_for_each_entry_rcu(fa, &li->falh, fa_list) {
				char buf1[32], buf2[32];

				seq_indent(seq, iter->depth+1);
				seq_printf(seq, "  /%d %s %s", li->plen,
					   rtn_scope(buf1, sizeof(buf1),
						     fa->fa_scope),
					   rtn_type(buf2, sizeof(buf2),
						    fa->fa_type));
				if (fa->fa_tos)
2354
					seq_printf(seq, " tos=%d", fa->fa_tos);
2355
				seq_putc(seq, '\n');
2356 2357
			}
		}
2358
	}
2359

2360 2361 2362
	return 0;
}

2363
static const struct seq_operations fib_trie_seq_ops = {
2364 2365 2366 2367
	.start  = fib_trie_seq_start,
	.next   = fib_trie_seq_next,
	.stop   = fib_trie_seq_stop,
	.show   = fib_trie_seq_show,
2368 2369
};

2370
static int fib_trie_seq_open(struct inode *inode, struct file *file)
2371
{
2372 2373
	return seq_open_net(inode, file, &fib_trie_seq_ops,
			    sizeof(struct fib_trie_iter));
2374 2375
}

2376
static const struct file_operations fib_trie_fops = {
2377 2378 2379 2380
	.owner  = THIS_MODULE,
	.open   = fib_trie_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2381
	.release = seq_release_net,
2382 2383
};

2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423
struct fib_route_iter {
	struct seq_net_private p;
	struct trie *main_trie;
	loff_t	pos;
	t_key	key;
};

static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
{
	struct leaf *l = NULL;
	struct trie *t = iter->main_trie;

	/* use cache location of last found key */
	if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
		pos -= iter->pos;
	else {
		iter->pos = 0;
		l = trie_firstleaf(t);
	}

	while (l && pos-- > 0) {
		iter->pos++;
		l = trie_nextleaf(l);
	}

	if (l)
		iter->key = pos;	/* remember it */
	else
		iter->pos = 0;		/* forget it */

	return l;
}

static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
	__acquires(RCU)
{
	struct fib_route_iter *iter = seq->private;
	struct fib_table *tb;

	rcu_read_lock();
2424
	tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461
	if (!tb)
		return NULL;

	iter->main_trie = (struct trie *) tb->tb_data;
	if (*pos == 0)
		return SEQ_START_TOKEN;
	else
		return fib_route_get_idx(iter, *pos - 1);
}

static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
{
	struct fib_route_iter *iter = seq->private;
	struct leaf *l = v;

	++*pos;
	if (v == SEQ_START_TOKEN) {
		iter->pos = 0;
		l = trie_firstleaf(iter->main_trie);
	} else {
		iter->pos++;
		l = trie_nextleaf(l);
	}

	if (l)
		iter->key = l->key;
	else
		iter->pos = 0;
	return l;
}

static void fib_route_seq_stop(struct seq_file *seq, void *v)
	__releases(RCU)
{
	rcu_read_unlock();
}

E
Eric Dumazet 已提交
2462
static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2463
{
E
Eric Dumazet 已提交
2464
	unsigned int flags = 0;
2465

E
Eric Dumazet 已提交
2466 2467
	if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
		flags = RTF_REJECT;
2468 2469
	if (fi && fi->fib_nh->nh_gw)
		flags |= RTF_GATEWAY;
A
Al Viro 已提交
2470
	if (mask == htonl(0xFFFFFFFF))
2471 2472 2473
		flags |= RTF_HOST;
	flags |= RTF_UP;
	return flags;
2474 2475
}

2476 2477 2478
/*
 *	This outputs /proc/net/route.
 *	The format of the file is not supposed to be changed
E
Eric Dumazet 已提交
2479
 *	and needs to be same as fib_hash output to avoid breaking
2480 2481 2482
 *	legacy utilities
 */
static int fib_route_seq_show(struct seq_file *seq, void *v)
2483
{
2484
	struct leaf *l = v;
2485 2486
	struct leaf_info *li;
	struct hlist_node *node;
2487

2488 2489 2490 2491 2492 2493
	if (v == SEQ_START_TOKEN) {
		seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
			   "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
			   "\tWindow\tIRTT");
		return 0;
	}
2494

2495
	hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2496
		struct fib_alias *fa;
A
Al Viro 已提交
2497
		__be32 mask, prefix;
O
Olof Johansson 已提交
2498

2499 2500
		mask = inet_make_mask(li->plen);
		prefix = htonl(l->key);
2501

2502
		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2503
			const struct fib_info *fi = fa->fa_info;
E
Eric Dumazet 已提交
2504
			unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2505
			int len;
2506

2507 2508 2509
			if (fa->fa_type == RTN_BROADCAST
			    || fa->fa_type == RTN_MULTICAST)
				continue;
2510

2511
			if (fi)
2512 2513 2514
				seq_printf(seq,
					 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
					 "%d\t%08X\t%d\t%u\t%u%n",
2515 2516 2517 2518 2519
					 fi->fib_dev ? fi->fib_dev->name : "*",
					 prefix,
					 fi->fib_nh->nh_gw, flags, 0, 0,
					 fi->fib_priority,
					 mask,
2520 2521
					 (fi->fib_advmss ?
					  fi->fib_advmss + 40 : 0),
2522
					 fi->fib_window,
2523
					 fi->fib_rtt >> 3, &len);
2524
			else
2525 2526 2527
				seq_printf(seq,
					 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
					 "%d\t%08X\t%d\t%u\t%u%n",
2528
					 prefix, 0, flags, 0, 0, 0,
2529
					 mask, 0, 0, 0, &len);
2530

2531
			seq_printf(seq, "%*s\n", 127 - len, "");
2532
		}
2533 2534 2535 2536 2537
	}

	return 0;
}

2538
static const struct seq_operations fib_route_seq_ops = {
2539 2540 2541
	.start  = fib_route_seq_start,
	.next   = fib_route_seq_next,
	.stop   = fib_route_seq_stop,
2542
	.show   = fib_route_seq_show,
2543 2544
};

2545
static int fib_route_seq_open(struct inode *inode, struct file *file)
2546
{
2547
	return seq_open_net(inode, file, &fib_route_seq_ops,
2548
			    sizeof(struct fib_route_iter));
2549 2550
}

2551
static const struct file_operations fib_route_fops = {
2552 2553 2554 2555
	.owner  = THIS_MODULE,
	.open   = fib_route_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2556
	.release = seq_release_net,
2557 2558
};

2559
int __net_init fib_proc_init(struct net *net)
2560
{
2561
	if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
2562 2563
		goto out1;

2564 2565
	if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
				  &fib_triestat_fops))
2566 2567
		goto out2;

2568
	if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
2569 2570
		goto out3;

2571
	return 0;
2572 2573

out3:
2574
	proc_net_remove(net, "fib_triestat");
2575
out2:
2576
	proc_net_remove(net, "fib_trie");
2577 2578
out1:
	return -ENOMEM;
2579 2580
}

2581
void __net_exit fib_proc_exit(struct net *net)
2582
{
2583 2584 2585
	proc_net_remove(net, "fib_trie");
	proc_net_remove(net, "fib_triestat");
	proc_net_remove(net, "route");
2586 2587 2588
}

#endif /* CONFIG_PROC_FS */