fib_trie.c 61.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 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
 * An experimental study of compression methods for dynamic tries
 * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
 * http://www.nada.kth.se/~snilsson/public/papers/dyntrie2/
 *
 *
 * 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
 */

R
Robert Olsson 已提交
51
#define VERSION "0.408"
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 <net/net_namespace.h>
75 76 77 78 79 80 81 82
#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 已提交
83
#define MAX_STAT_DEPTH 32
84 85 86 87 88 89 90 91

#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 已提交
92 93
#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)

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

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

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

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

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

#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;
137
	unsigned int resize_node_skipped;
138 139 140 141 142 143 144 145 146
};
#endif

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

struct trie {
O
Olof Johansson 已提交
152
	struct node *trie;
153 154 155 156 157 158
#ifdef CONFIG_IP_FIB_TRIE_STATS
	struct trie_use_stats stats;
#endif
};

static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
159 160
static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
				  int wasfull);
161
static struct node *resize(struct trie *t, struct tnode *tn);
162 163
static struct tnode *inflate(struct trie *t, struct tnode *tn);
static struct tnode *halve(struct trie *t, struct tnode *tn);
164

165
static struct kmem_cache *fn_alias_kmem __read_mostly;
166
static struct kmem_cache *trie_leaf_kmem __read_mostly;
167

S
Stephen Hemminger 已提交
168 169
static inline struct tnode *node_parent(struct node *node)
{
170 171 172 173 174 175
	return (struct tnode *)(node->parent & ~NODE_TYPE_MASK);
}

static inline struct tnode *node_parent_rcu(struct node *node)
{
	struct tnode *ret = node_parent(node);
S
Stephen Hemminger 已提交
176 177 178 179

	return rcu_dereference(ret);
}

180 181 182
/* Same as rcu_assign_pointer
 * but that macro() assumes that value is a pointer.
 */
S
Stephen Hemminger 已提交
183 184
static inline void node_set_parent(struct node *node, struct tnode *ptr)
{
185 186
	smp_wmb();
	node->parent = (unsigned long)ptr | NODE_TYPE(node);
S
Stephen Hemminger 已提交
187
}
R
Robert Olsson 已提交
188

189 190 191
static inline struct node *tnode_get_child(struct tnode *tn, unsigned int i)
{
	BUG_ON(i >= 1U << tn->bits);
R
Robert Olsson 已提交
192

193 194 195 196
	return tn->child[i];
}

static inline struct node *tnode_get_child_rcu(struct tnode *tn, unsigned int i)
197
{
198
	struct node *ret = tnode_get_child(tn, i);
199

200
	return rcu_dereference(ret);
201 202
}

S
Stephen Hemmigner 已提交
203
static inline int tnode_child_length(const struct tnode *tn)
204
{
O
Olof Johansson 已提交
205
	return 1 << tn->bits;
206 207
}

S
Stephen Hemminger 已提交
208 209 210 211 212
static inline t_key mask_pfx(t_key k, unsigned short l)
{
	return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
}

213 214
static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
{
O
Olof Johansson 已提交
215
	if (offset < KEYLENGTH)
216
		return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
O
Olof Johansson 已提交
217
	else
218 219 220 221 222
		return 0;
}

static inline int tkey_equals(t_key a, t_key b)
{
223
	return a == b;
224 225 226 227
}

static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
{
228 229
	if (bits == 0 || offset >= KEYLENGTH)
		return 1;
O
Olof Johansson 已提交
230 231
	bits = bits > KEYLENGTH ? KEYLENGTH : bits;
	return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
232
}
233 234 235 236 237 238

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

239 240 241
	if (!diff)
		return 0;
	while ((diff << i) >> (KEYLENGTH-1) == 0)
242 243 244 245 246
		i++;
	return i;
}

/*
247 248
  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
249 250 251 252
  all of the bits in that key are significant.

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

253 254 255 256 257
  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
258 259
  correct key path.

260 261 262 263 264
  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
265 266
  call to tkey_sub_equals() in trie_insert().

267
  if n is an internal node - a 'tnode' here, the various parts of its key
268 269
  have many different meanings.

270
  Example:
271 272 273
  _________________________________________________________________
  | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
  -----------------------------------------------------------------
274
    0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
275 276 277 278 279 280 281 282 283

  _________________________________________________________________
  | 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 已提交
284
  n->bits = 4
285

286 287
  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
288 289 290
  not use them for anything.

  The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
291
  index into the parent's child array. That is, they will be used to find
292 293 294 295 296
  'n' among tp's children.

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

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

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

303

304 305 306 307 308
  The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
  at this point.

*/

S
Stephen Hemminger 已提交
309
static inline void check_tnode(const struct tnode *tn)
310
{
S
Stephen Hemminger 已提交
311
	WARN_ON(tn && tn->pos+tn->bits > 32);
312 313
}

314 315 316 317
static const int halve_threshold = 25;
static const int inflate_threshold = 50;
static const int halve_threshold_root = 8;
static const int inflate_threshold_root = 15;
318

R
Robert Olsson 已提交
319 320

static void __alias_free_mem(struct rcu_head *head)
321
{
R
Robert Olsson 已提交
322 323
	struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
	kmem_cache_free(fn_alias_kmem, fa);
324 325
}

R
Robert Olsson 已提交
326
static inline void alias_free_mem_rcu(struct fib_alias *fa)
327
{
R
Robert Olsson 已提交
328 329
	call_rcu(&fa->rcu, __alias_free_mem);
}
O
Olof Johansson 已提交
330

R
Robert Olsson 已提交
331 332
static void __leaf_free_rcu(struct rcu_head *head)
{
333 334
	struct leaf *l = container_of(head, struct leaf, rcu);
	kmem_cache_free(trie_leaf_kmem, l);
R
Robert Olsson 已提交
335
}
O
Olof Johansson 已提交
336

337 338 339 340 341
static inline void free_leaf(struct leaf *l)
{
	call_rcu_bh(&l->rcu, __leaf_free_rcu);
}

R
Robert Olsson 已提交
342
static void __leaf_info_free_rcu(struct rcu_head *head)
343
{
R
Robert Olsson 已提交
344
	kfree(container_of(head, struct leaf_info, rcu));
345 346
}

R
Robert Olsson 已提交
347
static inline void free_leaf_info(struct leaf_info *leaf)
348
{
R
Robert Olsson 已提交
349
	call_rcu(&leaf->rcu, __leaf_info_free_rcu);
350 351
}

352
static struct tnode *tnode_alloc(size_t size)
353
{
R
Robert Olsson 已提交
354
	if (size <= PAGE_SIZE)
355
		return kzalloc(size, GFP_KERNEL);
356 357 358
	else
		return __vmalloc(size, GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL);
}
R
Robert Olsson 已提交
359

360 361 362 363
static void __tnode_vfree(struct work_struct *arg)
{
	struct tnode *tn = container_of(arg, struct tnode, work);
	vfree(tn);
364 365
}

R
Robert Olsson 已提交
366
static void __tnode_free_rcu(struct rcu_head *head)
367
{
R
Robert Olsson 已提交
368
	struct tnode *tn = container_of(head, struct tnode, rcu);
369 370
	size_t size = sizeof(struct tnode) +
		      (sizeof(struct node *) << tn->bits);
371 372 373

	if (size <= PAGE_SIZE)
		kfree(tn);
374 375 376 377
	else {
		INIT_WORK(&tn->work, __tnode_vfree);
		schedule_work(&tn->work);
	}
378 379
}

R
Robert Olsson 已提交
380 381
static inline void tnode_free(struct tnode *tn)
{
382 383 384
	if (IS_LEAF(tn))
		free_leaf((struct leaf *) tn);
	else
R
Robert Olsson 已提交
385
		call_rcu(&tn->rcu, __tnode_free_rcu);
R
Robert Olsson 已提交
386 387 388 389
}

static struct leaf *leaf_new(void)
{
390
	struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
R
Robert Olsson 已提交
391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407
	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;
}

408
static struct tnode *tnode_new(t_key key, int pos, int bits)
409
{
410
	size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits);
411
	struct tnode *tn = tnode_alloc(sz);
412

O
Olof Johansson 已提交
413
	if (tn) {
R
Robert Olsson 已提交
414
		tn->parent = T_TNODE;
415 416 417 418 419 420
		tn->pos = pos;
		tn->bits = bits;
		tn->key = key;
		tn->full_children = 0;
		tn->empty_children = 1<<bits;
	}
421

422 423
	pr_debug("AT %p s=%u %lu\n", tn, (unsigned int) sizeof(struct tnode),
		 (unsigned long) (sizeof(struct node) << bits));
424 425 426 427 428 429 430 431
	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
 */

S
Stephen Hemmigner 已提交
432
static inline int tnode_full(const struct tnode *tn, const struct node *n)
433
{
434
	if (n == NULL || IS_LEAF(n))
435 436 437 438 439
		return 0;

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

440 441
static inline void put_child(struct trie *t, struct tnode *tn, int i,
			     struct node *n)
442 443 444 445
{
	tnode_put_child_reorg(tn, i, n, -1);
}

446
 /*
447 448 449 450
  * Add a child at position i overwriting the old value.
  * Update the value of full_children and empty_children.
  */

451 452
static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
				  int wasfull)
453
{
R
Robert Olsson 已提交
454
	struct node *chi = tn->child[i];
455 456
	int isfull;

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

459 460 461 462 463
	/* update emptyChildren */
	if (n == NULL && chi != NULL)
		tn->empty_children++;
	else if (n != NULL && chi == NULL)
		tn->empty_children--;
464

465
	/* update fullChildren */
O
Olof Johansson 已提交
466
	if (wasfull == -1)
467 468 469
		wasfull = tnode_full(tn, chi);

	isfull = tnode_full(tn, n);
470
	if (wasfull && !isfull)
471
		tn->full_children--;
472
	else if (!wasfull && isfull)
473
		tn->full_children++;
O
Olof Johansson 已提交
474

475
	if (n)
S
Stephen Hemminger 已提交
476
		node_set_parent(n, tn);
477

R
Robert Olsson 已提交
478
	rcu_assign_pointer(tn->child[i], n);
479 480
}

481
static struct node *resize(struct trie *t, struct tnode *tn)
482 483
{
	int i;
484
	int err = 0;
485
	struct tnode *old_tn;
486 487
	int inflate_threshold_use;
	int halve_threshold_use;
R
Robert Olsson 已提交
488
	int max_resize;
489

490
	if (!tn)
491 492
		return NULL;

S
Stephen Hemminger 已提交
493 494
	pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
		 tn, inflate_threshold, halve_threshold);
495 496 497 498 499 500 501 502 503

	/* No children */
	if (tn->empty_children == tnode_child_length(tn)) {
		tnode_free(tn);
		return NULL;
	}
	/* One child */
	if (tn->empty_children == tnode_child_length(tn) - 1)
		for (i = 0; i < tnode_child_length(tn); i++) {
O
Olof Johansson 已提交
504
			struct node *n;
505

O
Olof Johansson 已提交
506
			n = tn->child[i];
R
Robert Olsson 已提交
507
			if (!n)
O
Olof Johansson 已提交
508 509 510
				continue;

			/* compress one level */
S
Stephen Hemminger 已提交
511
			node_set_parent(n, NULL);
O
Olof Johansson 已提交
512 513
			tnode_free(tn);
			return n;
514
		}
515
	/*
516 517 518 519 520
	 * Double as long as the resulting node has a number of
	 * nonempty nodes that are above the threshold.
	 */

	/*
521 522
	 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
	 * the Helsinki University of Technology and Matti Tikkanen of Nokia
523
	 * Telecommunications, page 6:
524
	 * "A node is doubled if the ratio of non-empty children to all
525 526
	 * children in the *doubled* node is at least 'high'."
	 *
527 528 529 530 531
	 * '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
532
	 * multiply the left-hand side by 50.
533 534 535 536
	 *
	 * 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"
537
	 * children, that is non-null tnodes with a skip value of 0.
538
	 * All of those will be doubled in the resulting inflated tnode, so
539
	 * we just count them one extra time here.
540
	 *
541
	 * A clearer way to write this would be:
542
	 *
543
	 * to_be_doubled = tn->full_children;
544
	 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
545 546 547 548
	 *     tn->full_children;
	 *
	 * new_child_length = tnode_child_length(tn) * 2;
	 *
549
	 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
550 551
	 *      new_child_length;
	 * if (new_fill_factor >= inflate_threshold)
552 553 554
	 *
	 * ...and so on, tho it would mess up the while () loop.
	 *
555 556 557
	 * anyway,
	 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
	 *      inflate_threshold
558
	 *
559 560 561
	 * avoid a division:
	 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
	 *      inflate_threshold * new_child_length
562
	 *
563
	 * expand not_to_be_doubled and to_be_doubled, and shorten:
564
	 * 100 * (tnode_child_length(tn) - tn->empty_children +
O
Olof Johansson 已提交
565
	 *    tn->full_children) >= inflate_threshold * new_child_length
566
	 *
567
	 * expand new_child_length:
568
	 * 100 * (tnode_child_length(tn) - tn->empty_children +
O
Olof Johansson 已提交
569
	 *    tn->full_children) >=
570
	 *      inflate_threshold * tnode_child_length(tn) * 2
571
	 *
572
	 * shorten again:
573
	 * 50 * (tn->full_children + tnode_child_length(tn) -
O
Olof Johansson 已提交
574
	 *    tn->empty_children) >= inflate_threshold *
575
	 *    tnode_child_length(tn)
576
	 *
577 578 579
	 */

	check_tnode(tn);
580

581 582
	/* Keep root node larger  */

S
Stephen Hemminger 已提交
583
	if (!tn->parent)
584
		inflate_threshold_use = inflate_threshold_root;
585
	else
586 587
		inflate_threshold_use = inflate_threshold;

588
	err = 0;
R
Robert Olsson 已提交
589 590
	max_resize = 10;
	while ((tn->full_children > 0 &&  max_resize-- &&
591 592 593
		50 * (tn->full_children + tnode_child_length(tn)
		      - tn->empty_children)
		>= inflate_threshold_use * tnode_child_length(tn))) {
594

595 596
		old_tn = tn;
		tn = inflate(t, tn);
597

598 599
		if (IS_ERR(tn)) {
			tn = old_tn;
600 601 602 603 604
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.resize_node_skipped++;
#endif
			break;
		}
605 606
	}

R
Robert Olsson 已提交
607 608
	if (max_resize < 0) {
		if (!tn->parent)
609 610 611
			pr_warning("Fix inflate_threshold_root."
				   " Now=%d size=%d bits\n",
				   inflate_threshold_root, tn->bits);
R
Robert Olsson 已提交
612
		else
613 614 615
			pr_warning("Fix inflate_threshold."
				   " Now=%d size=%d bits\n",
				   inflate_threshold, tn->bits);
R
Robert Olsson 已提交
616 617
	}

618 619 620 621 622 623
	check_tnode(tn);

	/*
	 * Halve as long as the number of empty children in this
	 * node is above threshold.
	 */
624

625 626 627

	/* Keep root node larger  */

S
Stephen Hemminger 已提交
628
	if (!tn->parent)
629
		halve_threshold_use = halve_threshold_root;
630
	else
631 632
		halve_threshold_use = halve_threshold;

633
	err = 0;
R
Robert Olsson 已提交
634 635
	max_resize = 10;
	while (tn->bits > 1 &&  max_resize-- &&
636
	       100 * (tnode_child_length(tn) - tn->empty_children) <
637
	       halve_threshold_use * tnode_child_length(tn)) {
638

639 640 641 642
		old_tn = tn;
		tn = halve(t, tn);
		if (IS_ERR(tn)) {
			tn = old_tn;
643 644 645 646 647 648
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.resize_node_skipped++;
#endif
			break;
		}
	}
649

R
Robert Olsson 已提交
650 651
	if (max_resize < 0) {
		if (!tn->parent)
652 653 654
			pr_warning("Fix halve_threshold_root."
				   " Now=%d size=%d bits\n",
				   halve_threshold_root, tn->bits);
R
Robert Olsson 已提交
655
		else
656 657 658
			pr_warning("Fix halve_threshold."
				   " Now=%d size=%d bits\n",
				   halve_threshold, tn->bits);
R
Robert Olsson 已提交
659
	}
660

661 662 663
	/* Only one child remains */
	if (tn->empty_children == tnode_child_length(tn) - 1)
		for (i = 0; i < tnode_child_length(tn); i++) {
O
Olof Johansson 已提交
664
			struct node *n;
665

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

			/* compress one level */

S
Stephen Hemminger 已提交
672
			node_set_parent(n, NULL);
O
Olof Johansson 已提交
673 674
			tnode_free(tn);
			return n;
675 676 677 678 679
		}

	return (struct node *) tn;
}

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

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

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

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

	/*
694 695 696
	 * 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
697 698
	 * of tnode is ignored.
	 */
O
Olof Johansson 已提交
699 700

	for (i = 0; i < olen; i++) {
701
		struct tnode *inode;
702

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

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

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

719
			if (!right) {
720 721
				tnode_free(left);
				goto nomem;
722
			}
723 724 725 726 727 728

			put_child(t, tn, 2*i, (struct node *) left);
			put_child(t, tn, 2*i+1, (struct node *) right);
		}
	}

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

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

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

741
		if (IS_LEAF(node) || ((struct tnode *) node)->pos >
742
		   tn->pos + tn->bits - 1) {
743 744 745
			if (tkey_extract_bits(node->key,
					      oldtnode->pos + oldtnode->bits,
					      1) == 0)
746 747 748 749 750 751 752 753 754 755 756 757 758 759
				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]);

			tnode_free(inode);
O
Olof Johansson 已提交
760
			continue;
761 762
		}

O
Olof Johansson 已提交
763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780
		/* 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)
		 */
781

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

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

O
Olof Johansson 已提交
789
		BUG_ON(!left);
790

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

O
Olof Johansson 已提交
794
		BUG_ON(!right);
795

O
Olof Johansson 已提交
796 797 798 799
		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]);
800
		}
O
Olof Johansson 已提交
801 802 803 804
		put_child(t, tn, 2*i, resize(t, left));
		put_child(t, tn, 2*i+1, resize(t, right));

		tnode_free(inode);
805 806 807
	}
	tnode_free(oldtnode);
	return tn;
808 809 810 811 812
nomem:
	{
		int size = tnode_child_length(tn);
		int j;

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

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

819 820
		return ERR_PTR(-ENOMEM);
	}
821 822
}

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

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

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

834 835
	if (!tn)
		return ERR_PTR(-ENOMEM);
836 837

	/*
838 839 840
	 * 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
841 842 843
	 * of tnode is ignored.
	 */

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

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

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

			if (!newn)
855
				goto nomem;
S
Stephen Hemminger 已提交
856

857
			put_child(t, tn, i/2, (struct node *)newn);
858 859 860
		}

	}
861

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

865 866
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
867

868 869 870 871 872
		/* 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 已提交
873
			continue;
S
Stephen Hemminger 已提交
874
		}
O
Olof Johansson 已提交
875 876

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

881
		/* Two nonempty children */
O
Olof Johansson 已提交
882 883 884 885 886
		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));
887 888 889
	}
	tnode_free(oldtnode);
	return tn;
890 891 892 893 894
nomem:
	{
		int size = tnode_child_length(tn);
		int j;

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

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

901 902
		return ERR_PTR(-ENOMEM);
	}
903 904
}

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

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

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

918 919 920
	return NULL;
}

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

O
Olof Johansson 已提交
925 926
	if (!li)
		return NULL;
927

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

static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
{
933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949
	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);
	}
950 951
}

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

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

	pos = 0;
R
Robert Olsson 已提交
962
	n = rcu_dereference(t->trie);
963 964 965

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

967
		check_tnode(tn);
O
Olof Johansson 已提交
968

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

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

983 984 985 986 987 988
	return NULL;
}

static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
{
	int wasfull;
S
Stephen Hemminger 已提交
989 990
	t_key cindex, key = tn->key;
	struct tnode *tp;
991

S
Stephen Hemminger 已提交
992
	while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) {
993 994
		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
		wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
995 996 997 998
		tn = (struct tnode *) resize(t, (struct tnode *)tn);

		tnode_put_child_reorg((struct tnode *)tp, cindex,
				      (struct node *)tn, wasfull);
O
Olof Johansson 已提交
999

S
Stephen Hemminger 已提交
1000 1001
		tp = node_parent((struct node *) tn);
		if (!tp)
1002
			break;
S
Stephen Hemminger 已提交
1003
		tn = tp;
1004
	}
S
Stephen Hemminger 已提交
1005

1006
	/* Handle last (top) tnode */
1007
	if (IS_TNODE(tn))
1008
		tn = (struct tnode *)resize(t, (struct tnode *)tn);
1009

1010
	return (struct node *)tn;
1011 1012
}

R
Robert Olsson 已提交
1013 1014
/* only used from updater-side */

1015
static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
1016 1017 1018 1019 1020 1021
{
	int pos, newpos;
	struct tnode *tp = NULL, *tn = NULL;
	struct node *n;
	struct leaf *l;
	int missbit;
1022
	struct list_head *fa_head = NULL;
1023 1024 1025 1026
	struct leaf_info *li;
	t_key cindex;

	pos = 0;
1027
	n = t->trie;
1028

1029 1030
	/* 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,
1031
	 * and we should just put our new leaf in that.
1032 1033
	 * 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
1034 1035
	 * not be the parent's 'pos'+'bits'!
	 *
1036
	 * If it does match the current key, get pos/bits from it, extract
1037 1038 1039 1040
	 * 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.
	 *
1041 1042 1043
	 * 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.
1044 1045 1046 1047 1048
	 * 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 已提交
1049

1050
		check_tnode(tn);
O
Olof Johansson 已提交
1051

1052
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1053
			tp = tn;
O
Olof Johansson 已提交
1054
			pos = tn->pos + tn->bits;
1055 1056 1057 1058
			n = tnode_get_child(tn,
					    tkey_extract_bits(key,
							      tn->pos,
							      tn->bits));
1059

S
Stephen Hemminger 已提交
1060
			BUG_ON(n && node_parent(n) != tn);
O
Olof Johansson 已提交
1061
		} else
1062 1063 1064 1065 1066 1067
			break;
	}

	/*
	 * n  ----> NULL, LEAF or TNODE
	 *
1068
	 * tp is n's (parent) ----> NULL or TNODE
1069 1070
	 */

O
Olof Johansson 已提交
1071
	BUG_ON(tp && IS_LEAF(tp));
1072 1073 1074

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

1075
	if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1076
		l = (struct leaf *) n;
1077
		li = leaf_info_new(plen);
O
Olof Johansson 已提交
1078

1079 1080
		if (!li)
			return NULL;
1081 1082 1083 1084 1085 1086 1087

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

1088 1089
	if (!l)
		return NULL;
1090 1091 1092 1093

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

1094
	if (!li) {
1095
		free_leaf(l);
1096
		return NULL;
1097
	}
1098 1099 1100 1101 1102

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

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

S
Stephen Hemminger 已提交
1105
		node_set_parent((struct node *)l, tp);
1106

O
Olof Johansson 已提交
1107 1108 1109 1110
		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
		put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
	} else {
		/* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1111 1112
		/*
		 *  Add a new tnode here
1113 1114 1115 1116
		 *  first tnode need some special handling
		 */

		if (tp)
O
Olof Johansson 已提交
1117
			pos = tp->pos+tp->bits;
1118
		else
O
Olof Johansson 已提交
1119 1120
			pos = 0;

1121
		if (n) {
1122 1123
			newpos = tkey_mismatch(key, pos, n->key);
			tn = tnode_new(n->key, newpos, 1);
O
Olof Johansson 已提交
1124
		} else {
1125
			newpos = 0;
1126
			tn = tnode_new(key, newpos, 1); /* First tnode */
1127 1128
		}

1129
		if (!tn) {
1130
			free_leaf_info(li);
1131
			free_leaf(l);
1132
			return NULL;
O
Olof Johansson 已提交
1133 1134
		}

S
Stephen Hemminger 已提交
1135
		node_set_parent((struct node *)tn, tp);
1136

O
Olof Johansson 已提交
1137
		missbit = tkey_extract_bits(key, newpos, 1);
1138 1139 1140
		put_child(t, tn, missbit, (struct node *)l);
		put_child(t, tn, 1-missbit, n);

1141
		if (tp) {
1142
			cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1143 1144
			put_child(t, (struct tnode *)tp, cindex,
				  (struct node *)tn);
O
Olof Johansson 已提交
1145
		} else {
1146
			rcu_assign_pointer(t->trie, (struct node *)tn);
1147 1148 1149
			tp = tn;
		}
	}
O
Olof Johansson 已提交
1150 1151

	if (tp && tp->pos + tp->bits > 32)
1152 1153 1154
		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 已提交
1155

1156
	/* Rebalance the trie */
R
Robert Olsson 已提交
1157 1158

	rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
1159
done:
1160 1161 1162
	return fa_head;
}

1163 1164 1165
/*
 * Caller must hold RTNL.
 */
1166
static int fn_trie_insert(struct fib_table *tb, struct fib_config *cfg)
1167 1168 1169
{
	struct trie *t = (struct trie *) tb->tb_data;
	struct fib_alias *fa, *new_fa;
1170
	struct list_head *fa_head = NULL;
1171
	struct fib_info *fi;
1172 1173
	int plen = cfg->fc_dst_len;
	u8 tos = cfg->fc_tos;
1174 1175 1176 1177 1178 1179 1180
	u32 key, mask;
	int err;
	struct leaf *l;

	if (plen > 32)
		return -EINVAL;

1181
	key = ntohl(cfg->fc_dst);
1182

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

O
Olof Johansson 已提交
1185
	mask = ntohl(inet_make_mask(plen));
1186

1187
	if (key & ~mask)
1188 1189 1190 1191
		return -EINVAL;

	key = key & mask;

1192 1193 1194
	fi = fib_create_info(cfg);
	if (IS_ERR(fi)) {
		err = PTR_ERR(fi);
1195
		goto err;
1196
	}
1197 1198

	l = fib_find_node(t, key);
1199
	fa = NULL;
1200

1201
	if (l) {
1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216
		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.
	 */

1217 1218 1219
	if (fa && fa->fa_tos == tos &&
	    fa->fa_info->fib_priority == fi->fib_priority) {
		struct fib_alias *fa_first, *fa_match;
1220 1221

		err = -EEXIST;
1222
		if (cfg->fc_nlflags & NLM_F_EXCL)
1223 1224
			goto out;

1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245
		/* 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;
			}
		}

1246
		if (cfg->fc_nlflags & NLM_F_REPLACE) {
1247 1248 1249
			struct fib_info *fi_drop;
			u8 state;

1250 1251 1252 1253
			fa = fa_first;
			if (fa_match) {
				if (fa == fa_match)
					err = 0;
1254
				goto out;
1255
			}
R
Robert Olsson 已提交
1256
			err = -ENOBUFS;
1257
			new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
R
Robert Olsson 已提交
1258 1259
			if (new_fa == NULL)
				goto out;
1260 1261

			fi_drop = fa->fa_info;
R
Robert Olsson 已提交
1262 1263
			new_fa->fa_tos = fa->fa_tos;
			new_fa->fa_info = fi;
1264 1265
			new_fa->fa_type = cfg->fc_type;
			new_fa->fa_scope = cfg->fc_scope;
1266
			state = fa->fa_state;
1267
			new_fa->fa_state = state & ~FA_S_ACCESSED;
1268

R
Robert Olsson 已提交
1269 1270
			list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
			alias_free_mem_rcu(fa);
1271 1272 1273

			fib_release_info(fi_drop);
			if (state & FA_S_ACCESSED)
1274
				rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1275 1276
			rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
				tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1277

O
Olof Johansson 已提交
1278
			goto succeeded;
1279 1280 1281 1282 1283
		}
		/* Error if we find a perfect match which
		 * uses the same scope, type, and nexthop
		 * information.
		 */
1284 1285
		if (fa_match)
			goto out;
1286

1287
		if (!(cfg->fc_nlflags & NLM_F_APPEND))
1288
			fa = fa_first;
1289 1290
	}
	err = -ENOENT;
1291
	if (!(cfg->fc_nlflags & NLM_F_CREATE))
1292 1293 1294
		goto out;

	err = -ENOBUFS;
1295
	new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1296 1297 1298 1299 1300
	if (new_fa == NULL)
		goto out;

	new_fa->fa_info = fi;
	new_fa->fa_tos = tos;
1301 1302
	new_fa->fa_type = cfg->fc_type;
	new_fa->fa_scope = cfg->fc_scope;
1303 1304 1305 1306 1307
	new_fa->fa_state = 0;
	/*
	 * Insert new entry to the list.
	 */

1308
	if (!fa_head) {
1309 1310 1311
		fa_head = fib_insert_node(t, key, plen);
		if (unlikely(!fa_head)) {
			err = -ENOMEM;
1312
			goto out_free_new_fa;
1313
		}
1314
	}
1315

R
Robert Olsson 已提交
1316 1317
	list_add_tail_rcu(&new_fa->fa_list,
			  (fa ? &fa->fa_list : fa_head));
1318

1319
	rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1320
	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1321
		  &cfg->fc_nlinfo, 0);
1322 1323
succeeded:
	return 0;
1324 1325 1326

out_free_new_fa:
	kmem_cache_free(fn_alias_kmem, new_fa);
1327 1328
out:
	fib_release_info(fi);
O
Olof Johansson 已提交
1329
err:
1330 1331 1332
	return err;
}

R
Robert Olsson 已提交
1333
/* should be called with rcu_read_lock */
1334 1335 1336
static int check_leaf(struct trie *t, struct leaf *l,
		      t_key key,  const struct flowi *flp,
		      struct fib_result *res)
1337 1338 1339 1340
{
	struct leaf_info *li;
	struct hlist_head *hhead = &l->list;
	struct hlist_node *node;
1341

R
Robert Olsson 已提交
1342
	hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1343 1344 1345 1346
		int err;
		int plen = li->plen;
		__be32 mask = inet_make_mask(plen);

1347
		if (l->key != (key & ntohl(mask)))
1348 1349
			continue;

1350 1351 1352
		err = fib_semantic_match(&li->falh, flp, res,
					 htonl(l->key), mask, plen);

1353
#ifdef CONFIG_IP_FIB_TRIE_STATS
1354
		if (err <= 0)
1355
			t->stats.semantic_match_passed++;
1356 1357
		else
			t->stats.semantic_match_miss++;
1358
#endif
1359
		if (err <= 0)
1360
			return err;
1361
	}
1362

1363
	return 1;
1364 1365
}

1366 1367
static int fn_trie_lookup(struct fib_table *tb, const struct flowi *flp,
			  struct fib_result *res)
1368 1369
{
	struct trie *t = (struct trie *) tb->tb_data;
1370
	int ret;
1371 1372 1373
	struct node *n;
	struct tnode *pn;
	int pos, bits;
O
Olof Johansson 已提交
1374
	t_key key = ntohl(flp->fl4_dst);
1375 1376 1377
	int chopped_off;
	t_key cindex = 0;
	int current_prefix_length = KEYLENGTH;
O
Olof Johansson 已提交
1378 1379 1380 1381
	struct tnode *cn;
	t_key node_prefix, key_prefix, pref_mismatch;
	int mp;

R
Robert Olsson 已提交
1382
	rcu_read_lock();
O
Olof Johansson 已提交
1383

R
Robert Olsson 已提交
1384
	n = rcu_dereference(t->trie);
1385
	if (!n)
1386 1387 1388 1389 1390 1391 1392 1393
		goto failed;

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

	/* Just a leaf? */
	if (IS_LEAF(n)) {
1394
		ret = check_leaf(t, (struct leaf *)n, key, flp, res);
1395
		goto found;
1396
	}
1397

1398 1399
	pn = (struct tnode *) n;
	chopped_off = 0;
1400

O
Olof Johansson 已提交
1401
	while (pn) {
1402 1403 1404
		pos = pn->pos;
		bits = pn->bits;

1405
		if (!chopped_off)
S
Stephen Hemminger 已提交
1406 1407
			cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
						   pos, bits);
1408 1409 1410 1411 1412 1413 1414 1415 1416 1417

		n = tnode_get_child(pn, cindex);

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

O
Olof Johansson 已提交
1418
		if (IS_LEAF(n)) {
1419 1420
			ret = check_leaf(t, (struct leaf *)n, key, flp, res);
			if (ret > 0)
O
Olof Johansson 已提交
1421
				goto backtrace;
1422
			goto found;
O
Olof Johansson 已提交
1423 1424 1425
		}

		cn = (struct tnode *)n;
1426

O
Olof Johansson 已提交
1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441
		/*
		 * 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].
		 */
1442

O
Olof Johansson 已提交
1443 1444 1445 1446 1447 1448 1449 1450 1451
		/* 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.
		 */
1452

1453 1454
		/* NOTA BENE: Checking only skipped bits
		   for the new node here */
1455

O
Olof Johansson 已提交
1456 1457
		if (current_prefix_length < pos+bits) {
			if (tkey_extract_bits(cn->key, current_prefix_length,
1458 1459
						cn->pos - current_prefix_length)
			    || !(cn->child[0]))
O
Olof Johansson 已提交
1460 1461
				goto backtrace;
		}
1462

O
Olof Johansson 已提交
1463 1464 1465 1466 1467 1468 1469 1470 1471
		/*
		 * 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.
		 */
1472

O
Olof Johansson 已提交
1473 1474 1475 1476 1477 1478 1479 1480
		/* 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.
		 */
1481

1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492
		/*
		 * 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 已提交
1493 1494
		 */

S
Stephen Hemminger 已提交
1495 1496
		node_prefix = mask_pfx(cn->key, cn->pos);
		key_prefix = mask_pfx(key, cn->pos);
O
Olof Johansson 已提交
1497 1498 1499
		pref_mismatch = key_prefix^node_prefix;
		mp = 0;

1500 1501 1502 1503
		/*
		 * In short: If skipped bits in this node do not match
		 * the search key, enter the "prefix matching"
		 * state.directly.
O
Olof Johansson 已提交
1504 1505 1506 1507
		 */
		if (pref_mismatch) {
			while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
				mp++;
1508
				pref_mismatch = pref_mismatch << 1;
O
Olof Johansson 已提交
1509 1510 1511 1512 1513 1514 1515 1516
			}
			key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);

			if (key_prefix != 0)
				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 {
S
Stephen Hemminger 已提交
1544 1545
			struct tnode *parent = node_parent((struct node *) pn);
			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 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);
R
Robert Olsson 已提交
1578
		rcu_assign_pointer(t->trie, 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
static int fn_trie_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 1709
/*
 * Scan for the next right leaf starting at node p->child[idx]
 * Since we have back pointer, no recursion necessary.
 */
static struct leaf *leaf_walk_rcu(struct tnode *p, struct 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 */
O
Olof Johansson 已提交
1735
		c = (struct node *) p;
1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762
	} while ( (p = node_parent_rcu(c)) != NULL);

	return NULL; /* Root of trie */
}

static struct leaf *trie_firstleaf(struct trie *t)
{
	struct tnode *n = (struct tnode *) rcu_dereference(t->trie);

	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)
{
	struct node *c = (struct node *) l;
	struct tnode *p = node_parent(c);

	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 1780 1781
static int fn_trie_flush(struct fib_table *tb)
{
	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
static void fn_trie_select_default(struct fib_table *tb,
				   const struct flowi *flp,
				   struct fib_result *res)
1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815
{
	struct trie *t = (struct trie *) tb->tb_data;
	int order, last_idx;
	struct fib_info *fi = NULL;
	struct fib_info *last_resort;
	struct fib_alias *fa = NULL;
	struct list_head *fa_head;
	struct leaf *l;

	last_idx = -1;
	last_resort = NULL;
	order = -1;

R
Robert Olsson 已提交
1816
	rcu_read_lock();
1817

1818
	l = fib_find_node(t, 0);
1819
	if (!l)
1820 1821 1822
		goto out;

	fa_head = get_fa_head(l, 0);
1823
	if (!fa_head)
1824 1825
		goto out;

1826
	if (list_empty(fa_head))
1827 1828
		goto out;

R
Robert Olsson 已提交
1829
	list_for_each_entry_rcu(fa, fa_head, fa_list) {
1830
		struct fib_info *next_fi = fa->fa_info;
O
Olof Johansson 已提交
1831

1832 1833 1834
		if (fa->fa_scope != res->scope ||
		    fa->fa_type != RTN_UNICAST)
			continue;
O
Olof Johansson 已提交
1835

1836 1837 1838 1839 1840 1841
		if (next_fi->fib_priority > res->fi->fib_priority)
			break;
		if (!next_fi->fib_nh[0].nh_gw ||
		    next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
			continue;
		fa->fa_state |= FA_S_ACCESSED;
O
Olof Johansson 已提交
1842

1843 1844 1845 1846
		if (fi == NULL) {
			if (next_fi != res->fi)
				break;
		} else if (!fib_detect_death(fi, order, &last_resort,
1847
					     &last_idx, tb->tb_default)) {
1848
			fib_result_assign(res, fi);
1849
			tb->tb_default = order;
1850 1851 1852 1853 1854 1855
			goto out;
		}
		fi = next_fi;
		order++;
	}
	if (order <= 0 || fi == NULL) {
1856
		tb->tb_default = -1;
1857 1858 1859
		goto out;
	}

1860 1861
	if (!fib_detect_death(fi, order, &last_resort, &last_idx,
				tb->tb_default)) {
1862
		fib_result_assign(res, fi);
1863
		tb->tb_default = order;
1864 1865
		goto out;
	}
1866 1867
	if (last_idx >= 0)
		fib_result_assign(res, last_resort);
1868 1869
	tb->tb_default = last_idx;
out:
R
Robert Olsson 已提交
1870
	rcu_read_unlock();
1871 1872
}

1873 1874
static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
			   struct fib_table *tb,
1875 1876 1877 1878
			   struct sk_buff *skb, struct netlink_callback *cb)
{
	int i, s_i;
	struct fib_alias *fa;
A
Al Viro 已提交
1879
	__be32 xkey = htonl(key);
1880

1881
	s_i = cb->args[5];
1882 1883
	i = 0;

R
Robert Olsson 已提交
1884 1885 1886
	/* rcu_read_lock is hold by caller */

	list_for_each_entry_rcu(fa, fah, fa_list) {
1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897
		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,
1898
				  xkey,
1899 1900
				  plen,
				  fa->fa_tos,
1901
				  fa->fa_info, NLM_F_MULTI) < 0) {
1902
			cb->args[5] = i;
1903
			return -1;
O
Olof Johansson 已提交
1904
		}
1905 1906
		i++;
	}
1907
	cb->args[5] = i;
1908 1909 1910
	return skb->len;
}

1911 1912
static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
			struct sk_buff *skb, struct netlink_callback *cb)
1913
{
1914 1915 1916
	struct leaf_info *li;
	struct hlist_node *node;
	int i, s_i;
1917

1918
	s_i = cb->args[4];
1919
	i = 0;
1920

1921 1922 1923 1924
	/* rcu_read_lock is hold by caller */
	hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
		if (i < s_i) {
			i++;
1925
			continue;
1926
		}
O
Olof Johansson 已提交
1927

1928
		if (i > s_i)
1929
			cb->args[5] = 0;
1930

1931
		if (list_empty(&li->falh))
1932 1933
			continue;

1934
		if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1935
			cb->args[4] = i;
1936 1937
			return -1;
		}
1938
		i++;
1939
	}
1940

1941
	cb->args[4] = i;
1942 1943 1944
	return skb->len;
}

1945 1946
static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb,
			struct netlink_callback *cb)
1947
{
1948
	struct leaf *l;
1949
	struct trie *t = (struct trie *) tb->tb_data;
1950
	t_key key = cb->args[2];
1951
	int count = cb->args[3];
1952

R
Robert Olsson 已提交
1953
	rcu_read_lock();
1954 1955 1956
	/* Dump starting at last key.
	 * Note: 0.0.0.0/0 (ie default) is first key.
	 */
1957
	if (count == 0)
1958 1959
		l = trie_firstleaf(t);
	else {
1960 1961 1962
		/* Normally, continue from last key, but if that is missing
		 * fallback to using slow rescan
		 */
1963
		l = fib_find_node(t, key);
1964 1965
		if (!l)
			l = trie_leafindex(t, count);
1966
	}
1967

1968 1969
	while (l) {
		cb->args[2] = l->key;
1970
		if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1971
			cb->args[3] = count;
1972 1973
			rcu_read_unlock();
			return -1;
1974
		}
1975

1976
		++count;
1977
		l = trie_nextleaf(l);
1978 1979
		memset(&cb->args[4], 0,
		       sizeof(cb->args) - 4*sizeof(cb->args[0]));
1980
	}
1981
	cb->args[3] = count;
R
Robert Olsson 已提交
1982
	rcu_read_unlock();
1983

1984 1985 1986
	return skb->len;
}

1987 1988
void __init fib_hash_init(void)
{
1989 1990
	fn_alias_kmem = kmem_cache_create("ip_fib_alias",
					  sizeof(struct fib_alias),
1991 1992 1993 1994 1995 1996
					  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);
1997
}
1998

1999 2000 2001

/* Fix more generic FIB names for init later */
struct fib_table *fib_hash_table(u32 id)
2002 2003 2004 2005 2006 2007 2008 2009 2010 2011
{
	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;
2012
	tb->tb_default = -1;
2013 2014 2015 2016 2017 2018 2019 2020
	tb->tb_lookup = fn_trie_lookup;
	tb->tb_insert = fn_trie_insert;
	tb->tb_delete = fn_trie_delete;
	tb->tb_flush = fn_trie_flush;
	tb->tb_select_default = fn_trie_select_default;
	tb->tb_dump = fn_trie_dump;

	t = (struct trie *) tb->tb_data;
2021
	memset(t, 0, sizeof(*t));
2022 2023

	if (id == RT_TABLE_LOCAL)
2024
		pr_info("IPv4 FIB: Using LC-trie version %s\n", VERSION);
2025 2026 2027 2028

	return tb;
}

2029 2030 2031
#ifdef CONFIG_PROC_FS
/* Depth first Trie walk iterator */
struct fib_trie_iter {
2032
	struct seq_net_private p;
2033
	struct fib_table *tb;
2034 2035 2036 2037
	struct tnode *tnode;
	unsigned index;
	unsigned depth;
};
2038

2039
static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
2040
{
2041 2042 2043
	struct tnode *tn = iter->tnode;
	unsigned cindex = iter->index;
	struct tnode *p;
2044

2045 2046 2047 2048
	/* A single entry routing table */
	if (!tn)
		return NULL;

2049 2050 2051 2052
	pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
		 iter->tnode, iter->index, iter->depth);
rescan:
	while (cindex < (1<<tn->bits)) {
2053
		struct node *n = tnode_get_child_rcu(tn, cindex);
2054

2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066
		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;
		}
2067

2068 2069
		++cindex;
	}
O
Olof Johansson 已提交
2070

2071
	/* Current node exhausted, pop back up */
2072
	p = node_parent_rcu((struct node *)tn);
2073 2074 2075 2076 2077
	if (p) {
		cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
		tn = p;
		--iter->depth;
		goto rescan;
2078
	}
2079 2080 2081

	/* got root? */
	return NULL;
2082 2083
}

2084 2085
static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
				       struct trie *t)
2086
{
2087
	struct node *n;
2088

S
Stephen Hemminger 已提交
2089
	if (!t)
2090 2091 2092
		return NULL;

	n = rcu_dereference(t->trie);
2093
	if (!n)
2094
		return NULL;
2095

2096 2097 2098 2099 2100 2101 2102 2103
	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 已提交
2104
	}
2105 2106

	return n;
2107
}
O
Olof Johansson 已提交
2108

2109 2110 2111 2112
static void trie_collect_stats(struct trie *t, struct trie_stat *s)
{
	struct node *n;
	struct fib_trie_iter iter;
O
Olof Johansson 已提交
2113

2114
	memset(s, 0, sizeof(*s));
O
Olof Johansson 已提交
2115

2116
	rcu_read_lock();
2117
	for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2118
		if (IS_LEAF(n)) {
2119 2120 2121 2122
			struct leaf *l = (struct leaf *)n;
			struct leaf_info *li;
			struct hlist_node *tmp;

2123 2124 2125 2126
			s->leaves++;
			s->totdepth += iter.depth;
			if (iter.depth > s->maxdepth)
				s->maxdepth = iter.depth;
2127 2128 2129

			hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
				++s->prefixes;
2130 2131 2132 2133 2134
		} else {
			const struct tnode *tn = (const struct tnode *) n;
			int i;

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

2138 2139 2140
			for (i = 0; i < (1<<tn->bits); i++)
				if (!tn->child[i])
					s->nullpointers++;
2141 2142
		}
	}
R
Robert Olsson 已提交
2143
	rcu_read_unlock();
2144 2145
}

2146 2147 2148 2149
/*
 *	This outputs /proc/net/fib_triestats
 */
static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2150
{
2151
	unsigned i, max, pointers, bytes, avdepth;
2152

2153 2154 2155 2156
	if (stat->leaves)
		avdepth = stat->totdepth*100 / stat->leaves;
	else
		avdepth = 0;
O
Olof Johansson 已提交
2157

2158 2159
	seq_printf(seq, "\tAver depth:     %u.%02d\n",
		   avdepth / 100, avdepth % 100);
2160
	seq_printf(seq, "\tMax depth:      %u\n", stat->maxdepth);
O
Olof Johansson 已提交
2161

2162 2163
	seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
	bytes = sizeof(struct leaf) * stat->leaves;
2164 2165 2166 2167

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

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

R
Robert Olsson 已提交
2171 2172
	max = MAX_STAT_DEPTH;
	while (max > 0 && stat->nodesizes[max-1] == 0)
2173
		max--;
2174

2175 2176 2177
	pointers = 0;
	for (i = 1; i <= max; i++)
		if (stat->nodesizes[i] != 0) {
2178
			seq_printf(seq, "  %u: %u",  i, stat->nodesizes[i]);
2179 2180 2181
			pointers += (1<<i) * stat->nodesizes[i];
		}
	seq_putc(seq, '\n');
2182
	seq_printf(seq, "\tPointers: %u\n", pointers);
R
Robert Olsson 已提交
2183

2184
	bytes += sizeof(struct node *) * pointers;
2185 2186
	seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
	seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
2187
}
R
Robert Olsson 已提交
2188

2189
#ifdef CONFIG_IP_FIB_TRIE_STATS
2190 2191 2192 2193
static void trie_show_usage(struct seq_file *seq,
			    const struct trie_use_stats *stats)
{
	seq_printf(seq, "\nCounters:\n---------\n");
2194 2195 2196 2197 2198 2199 2200 2201 2202
	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);
2203
}
2204 2205
#endif /*  CONFIG_IP_FIB_TRIE_STATS */

2206
static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2207
{
2208 2209 2210 2211 2212 2213
	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);
2214
}
2215

2216

2217 2218
static int fib_triestat_seq_show(struct seq_file *seq, void *v)
{
2219
	struct net *net = (struct net *)seq->private;
2220
	unsigned int h;
2221

2222
	seq_printf(seq,
2223 2224
		   "Basic info: size of leaf:"
		   " %Zd bytes, size of tnode: %Zd bytes.\n",
2225 2226
		   sizeof(struct leaf), sizeof(struct tnode));

2227 2228 2229 2230 2231 2232 2233 2234
	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;
2235

2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247
			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
		}
	}
2248

2249
	return 0;
2250 2251
}

2252
static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2253
{
2254
	return single_open_net(inode, file, fib_triestat_seq_show);
2255 2256
}

2257
static const struct file_operations fib_triestat_fops = {
2258 2259 2260 2261
	.owner	= THIS_MODULE,
	.open	= fib_triestat_seq_open,
	.read	= seq_read,
	.llseek	= seq_lseek,
2262
	.release = single_release_net,
2263 2264
};

2265
static struct node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2266
{
2267 2268
	struct fib_trie_iter *iter = seq->private;
	struct net *net = seq_file_net(seq);
2269
	loff_t idx = 0;
2270
	unsigned int h;
2271

2272 2273 2274 2275
	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;
2276

2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287
		hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
			struct node *n;

			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;
				}
		}
2288
	}
2289

2290 2291 2292
	return NULL;
}

2293
static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2294
	__acquires(RCU)
2295
{
2296
	rcu_read_lock();
2297
	return fib_trie_get_idx(seq, *pos);
2298 2299
}

2300
static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2301
{
2302
	struct fib_trie_iter *iter = seq->private;
2303
	struct net *net = seq_file_net(seq);
2304 2305 2306 2307
	struct fib_table *tb = iter->tb;
	struct hlist_node *tb_node;
	unsigned int h;
	struct node *n;
2308

2309
	++*pos;
2310 2311 2312 2313
	/* next node in same table */
	n = fib_trie_get_next(iter);
	if (n)
		return n;
2314

2315 2316 2317 2318 2319 2320 2321 2322
	/* 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;
	}
2323

2324 2325 2326 2327 2328 2329 2330 2331 2332
	/* 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;
		}
	}
2333
	return NULL;
2334 2335 2336 2337

found:
	iter->tb = tb;
	return n;
2338
}
2339

2340
static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2341
	__releases(RCU)
2342
{
2343 2344
	rcu_read_unlock();
}
O
Olof Johansson 已提交
2345

2346 2347 2348 2349
static void seq_indent(struct seq_file *seq, int n)
{
	while (n-- > 0) seq_puts(seq, "   ");
}
2350

2351
static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2352
{
S
Stephen Hemminger 已提交
2353
	switch (s) {
2354 2355 2356 2357 2358 2359
	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:
2360
		snprintf(buf, len, "scope=%d", s);
2361 2362 2363
		return buf;
	}
}
2364

2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378
static const char *rtn_type_names[__RTN_MAX] = {
	[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",
};
2379

2380
static inline const char *rtn_type(char *buf, size_t len, unsigned t)
2381 2382 2383
{
	if (t < __RTN_MAX && rtn_type_names[t])
		return rtn_type_names[t];
2384
	snprintf(buf, len, "type %u", t);
2385
	return buf;
2386 2387
}

2388 2389
/* Pretty print the trie */
static int fib_trie_seq_show(struct seq_file *seq, void *v)
2390
{
2391 2392
	const struct fib_trie_iter *iter = seq->private;
	struct node *n = v;
2393

2394 2395
	if (!node_parent_rcu(n))
		fib_table_print(seq, iter->tb);
2396

2397 2398
	if (IS_TNODE(n)) {
		struct tnode *tn = (struct tnode *) n;
S
Stephen Hemminger 已提交
2399
		__be32 prf = htonl(mask_pfx(tn->key, tn->pos));
O
Olof Johansson 已提交
2400

2401
		seq_indent(seq, iter->depth-1);
2402 2403
		seq_printf(seq, "  +-- %pI4/%d %d %d %d\n",
			   &prf, tn->pos, tn->bits, tn->full_children,
2404
			   tn->empty_children);
2405

2406 2407
	} else {
		struct leaf *l = (struct leaf *) n;
2408 2409
		struct leaf_info *li;
		struct hlist_node *node;
A
Al Viro 已提交
2410
		__be32 val = htonl(l->key);
2411 2412

		seq_indent(seq, iter->depth);
2413
		seq_printf(seq, "  |-- %pI4\n", &val);
2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427

		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)
2428
					seq_printf(seq, " tos=%d", fa->fa_tos);
2429
				seq_putc(seq, '\n');
2430 2431
			}
		}
2432
	}
2433

2434 2435 2436
	return 0;
}

2437
static const struct seq_operations fib_trie_seq_ops = {
2438 2439 2440 2441
	.start  = fib_trie_seq_start,
	.next   = fib_trie_seq_next,
	.stop   = fib_trie_seq_stop,
	.show   = fib_trie_seq_show,
2442 2443
};

2444
static int fib_trie_seq_open(struct inode *inode, struct file *file)
2445
{
2446 2447
	return seq_open_net(inode, file, &fib_trie_seq_ops,
			    sizeof(struct fib_trie_iter));
2448 2449
}

2450
static const struct file_operations fib_trie_fops = {
2451 2452 2453 2454
	.owner  = THIS_MODULE,
	.open   = fib_trie_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2455
	.release = seq_release_net,
2456 2457
};

2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497
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();
2498
	tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535
	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();
}

A
Al Viro 已提交
2536
static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2537
{
2538 2539 2540 2541
	static unsigned type2flags[RTN_MAX + 1] = {
		[7] = RTF_REJECT, [8] = RTF_REJECT,
	};
	unsigned flags = type2flags[type];
2542

2543 2544
	if (fi && fi->fib_nh->nh_gw)
		flags |= RTF_GATEWAY;
A
Al Viro 已提交
2545
	if (mask == htonl(0xFFFFFFFF))
2546 2547 2548
		flags |= RTF_HOST;
	flags |= RTF_UP;
	return flags;
2549 2550
}

2551 2552 2553 2554 2555 2556 2557
/*
 *	This outputs /proc/net/route.
 *	The format of the file is not supposed to be changed
 * 	and needs to be same as fib_hash output to avoid breaking
 *	legacy utilities
 */
static int fib_route_seq_show(struct seq_file *seq, void *v)
2558
{
2559
	struct leaf *l = v;
2560 2561
	struct leaf_info *li;
	struct hlist_node *node;
2562

2563 2564 2565 2566 2567 2568
	if (v == SEQ_START_TOKEN) {
		seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
			   "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
			   "\tWindow\tIRTT");
		return 0;
	}
2569

2570
	hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2571
		struct fib_alias *fa;
A
Al Viro 已提交
2572
		__be32 mask, prefix;
O
Olof Johansson 已提交
2573

2574 2575
		mask = inet_make_mask(li->plen);
		prefix = htonl(l->key);
2576

2577
		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2578
			const struct fib_info *fi = fa->fa_info;
2579
			unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2580
			int len;
2581

2582 2583 2584
			if (fa->fa_type == RTN_BROADCAST
			    || fa->fa_type == RTN_MULTICAST)
				continue;
2585

2586
			if (fi)
2587 2588 2589
				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",
2590 2591 2592 2593 2594
					 fi->fib_dev ? fi->fib_dev->name : "*",
					 prefix,
					 fi->fib_nh->nh_gw, flags, 0, 0,
					 fi->fib_priority,
					 mask,
2595 2596
					 (fi->fib_advmss ?
					  fi->fib_advmss + 40 : 0),
2597
					 fi->fib_window,
2598
					 fi->fib_rtt >> 3, &len);
2599
			else
2600 2601 2602
				seq_printf(seq,
					 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
					 "%d\t%08X\t%d\t%u\t%u%n",
2603
					 prefix, 0, flags, 0, 0, 0,
2604
					 mask, 0, 0, 0, &len);
2605

2606
			seq_printf(seq, "%*s\n", 127 - len, "");
2607
		}
2608 2609 2610 2611 2612
	}

	return 0;
}

2613
static const struct seq_operations fib_route_seq_ops = {
2614 2615 2616
	.start  = fib_route_seq_start,
	.next   = fib_route_seq_next,
	.stop   = fib_route_seq_stop,
2617
	.show   = fib_route_seq_show,
2618 2619
};

2620
static int fib_route_seq_open(struct inode *inode, struct file *file)
2621
{
2622
	return seq_open_net(inode, file, &fib_route_seq_ops,
2623
			    sizeof(struct fib_route_iter));
2624 2625
}

2626
static const struct file_operations fib_route_fops = {
2627 2628 2629 2630
	.owner  = THIS_MODULE,
	.open   = fib_route_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2631
	.release = seq_release_net,
2632 2633
};

2634
int __net_init fib_proc_init(struct net *net)
2635
{
2636
	if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
2637 2638
		goto out1;

2639 2640
	if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
				  &fib_triestat_fops))
2641 2642
		goto out2;

2643
	if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
2644 2645
		goto out3;

2646
	return 0;
2647 2648

out3:
2649
	proc_net_remove(net, "fib_triestat");
2650
out2:
2651
	proc_net_remove(net, "fib_trie");
2652 2653
out1:
	return -ENOMEM;
2654 2655
}

2656
void __net_exit fib_proc_exit(struct net *net)
2657
{
2658 2659 2660
	proc_net_remove(net, "fib_trie");
	proc_net_remove(net, "fib_triestat");
	proc_net_remove(net, "route");
2661 2662 2663
}

#endif /* CONFIG_PROC_FS */