fib_trie.c 62.8 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
	union {
		struct rcu_head rcu;
		struct work_struct work;
J
Jarek Poplawski 已提交
126
		struct tnode *tnode_free;
127
	};
O
Olof Johansson 已提交
128
	struct node *child[0];
129 130 131 132 133 134 135 136 137
};

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

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

struct trie {
O
Olof Johansson 已提交
153
	struct node *trie;
154 155 156 157 158 159
#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);
160 161
static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
				  int wasfull);
162
static struct node *resize(struct trie *t, struct tnode *tn);
163 164
static struct tnode *inflate(struct trie *t, struct tnode *tn);
static struct tnode *halve(struct trie *t, struct tnode *tn);
J
Jarek Poplawski 已提交
165 166
/* tnodes to free after resize(); protected by RTNL */
static struct tnode *tnode_free_head;
167 168 169 170 171 172 173 174
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;
175

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

S
Stephen Hemminger 已提交
179 180
static inline struct tnode *node_parent(struct node *node)
{
181 182 183 184 185 186
	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 已提交
187 188 189 190

	return rcu_dereference(ret);
}

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

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

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

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

211
	return rcu_dereference(ret);
212 213
}

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

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

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

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

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

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

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

/*
258 259
  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
260 261 262 263
  all of the bits in that key are significant.

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

264 265 266 267 268
  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
269 270
  correct key path.

271 272 273 274 275
  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
276 277
  call to tkey_sub_equals() in trie_insert().

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

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

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

297 298
  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
299 300 301
  not use them for anything.

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

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

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

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

314

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

*/

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

325 326
static const int halve_threshold = 25;
static const int inflate_threshold = 50;
327 328
static const int halve_threshold_root = 15;
static const int inflate_threshold_root = 25;
329

330 331
static int inflate_threshold_root_fix;
#define INFLATE_FIX_MAX 10	/* a comment in resize() */
R
Robert Olsson 已提交
332 333

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

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

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

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

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

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

365
static struct tnode *tnode_alloc(size_t size)
366
{
R
Robert Olsson 已提交
367
	if (size <= PAGE_SIZE)
368
		return kzalloc(size, GFP_KERNEL);
369 370 371
	else
		return __vmalloc(size, GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL);
}
R
Robert Olsson 已提交
372

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

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

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

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

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

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);
	}
419 420 421 422 423

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

R
Robert Olsson 已提交
426 427
static struct leaf *leaf_new(void)
{
428
	struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
R
Robert Olsson 已提交
429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445
	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;
}

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

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

460 461
	pr_debug("AT %p s=%u %lu\n", tn, (unsigned int) sizeof(struct tnode),
		 (unsigned long) (sizeof(struct node) << bits));
462 463 464 465 466 467 468 469
	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 已提交
470
static inline int tnode_full(const struct tnode *tn, const struct node *n)
471
{
472
	if (n == NULL || IS_LEAF(n))
473 474 475 476 477
		return 0;

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

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

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

489 490
static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
				  int wasfull)
491
{
R
Robert Olsson 已提交
492
	struct node *chi = tn->child[i];
493 494
	int isfull;

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

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

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

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

513
	if (n)
S
Stephen Hemminger 已提交
514
		node_set_parent(n, tn);
515

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

519
static struct node *resize(struct trie *t, struct tnode *tn)
520 521
{
	int i;
522
	int err = 0;
523
	struct tnode *old_tn;
524 525
	int inflate_threshold_use;
	int halve_threshold_use;
R
Robert Olsson 已提交
526
	int max_resize;
527

528
	if (!tn)
529 530
		return NULL;

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

	/* No children */
	if (tn->empty_children == tnode_child_length(tn)) {
J
Jarek Poplawski 已提交
536
		tnode_free_safe(tn);
537 538 539 540 541
		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 已提交
542
			struct node *n;
543

O
Olof Johansson 已提交
544
			n = tn->child[i];
R
Robert Olsson 已提交
545
			if (!n)
O
Olof Johansson 已提交
546 547 548
				continue;

			/* compress one level */
S
Stephen Hemminger 已提交
549
			node_set_parent(n, NULL);
J
Jarek Poplawski 已提交
550
			tnode_free_safe(tn);
O
Olof Johansson 已提交
551
			return n;
552
		}
553
	/*
554 555 556 557 558
	 * Double as long as the resulting node has a number of
	 * nonempty nodes that are above the threshold.
	 */

	/*
559 560
	 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
	 * the Helsinki University of Technology and Matti Tikkanen of Nokia
561
	 * Telecommunications, page 6:
562
	 * "A node is doubled if the ratio of non-empty children to all
563 564
	 * children in the *doubled* node is at least 'high'."
	 *
565 566 567 568 569
	 * '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
570
	 * multiply the left-hand side by 50.
571 572 573 574
	 *
	 * 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"
575
	 * children, that is non-null tnodes with a skip value of 0.
576
	 * All of those will be doubled in the resulting inflated tnode, so
577
	 * we just count them one extra time here.
578
	 *
579
	 * A clearer way to write this would be:
580
	 *
581
	 * to_be_doubled = tn->full_children;
582
	 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
583 584 585 586
	 *     tn->full_children;
	 *
	 * new_child_length = tnode_child_length(tn) * 2;
	 *
587
	 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
588 589
	 *      new_child_length;
	 * if (new_fill_factor >= inflate_threshold)
590 591 592
	 *
	 * ...and so on, tho it would mess up the while () loop.
	 *
593 594 595
	 * anyway,
	 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
	 *      inflate_threshold
596
	 *
597 598 599
	 * avoid a division:
	 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
	 *      inflate_threshold * new_child_length
600
	 *
601
	 * expand not_to_be_doubled and to_be_doubled, and shorten:
602
	 * 100 * (tnode_child_length(tn) - tn->empty_children +
O
Olof Johansson 已提交
603
	 *    tn->full_children) >= inflate_threshold * new_child_length
604
	 *
605
	 * expand new_child_length:
606
	 * 100 * (tnode_child_length(tn) - tn->empty_children +
O
Olof Johansson 已提交
607
	 *    tn->full_children) >=
608
	 *      inflate_threshold * tnode_child_length(tn) * 2
609
	 *
610
	 * shorten again:
611
	 * 50 * (tn->full_children + tnode_child_length(tn) -
O
Olof Johansson 已提交
612
	 *    tn->empty_children) >= inflate_threshold *
613
	 *    tnode_child_length(tn)
614
	 *
615 616 617
	 */

	check_tnode(tn);
618

619 620
	/* Keep root node larger  */

S
Stephen Hemminger 已提交
621
	if (!tn->parent)
622 623
		inflate_threshold_use = inflate_threshold_root +
					inflate_threshold_root_fix;
624
	else
625 626
		inflate_threshold_use = inflate_threshold;

627
	err = 0;
R
Robert Olsson 已提交
628 629
	max_resize = 10;
	while ((tn->full_children > 0 &&  max_resize-- &&
630 631 632
		50 * (tn->full_children + tnode_child_length(tn)
		      - tn->empty_children)
		>= inflate_threshold_use * tnode_child_length(tn))) {
633

634 635
		old_tn = tn;
		tn = inflate(t, tn);
636

637 638
		if (IS_ERR(tn)) {
			tn = old_tn;
639 640 641 642 643
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.resize_node_skipped++;
#endif
			break;
		}
644 645
	}

R
Robert Olsson 已提交
646
	if (max_resize < 0) {
647 648 649 650 651 652 653 654 655 656 657 658 659 660 661
		if (!tn->parent) {
			/*
			 * It was observed that during large updates even
			 * inflate_threshold_root = 35 might be needed to avoid
			 * this warning; but it should be temporary, so let's
			 * try to handle this automatically.
			 */
			if (inflate_threshold_root_fix < INFLATE_FIX_MAX)
				inflate_threshold_root_fix++;
			else
				pr_warning("Fix inflate_threshold_root."
					   " Now=%d size=%d bits fix=%d\n",
					   inflate_threshold_root, tn->bits,
					   inflate_threshold_root_fix);
		} else {
662 663 664
			pr_warning("Fix inflate_threshold."
				   " Now=%d size=%d bits\n",
				   inflate_threshold, tn->bits);
665 666 667
		}
	} else if (max_resize > 3 && !tn->parent && inflate_threshold_root_fix)
		inflate_threshold_root_fix--;
R
Robert Olsson 已提交
668

669 670 671 672 673 674
	check_tnode(tn);

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

676 677 678

	/* Keep root node larger  */

S
Stephen Hemminger 已提交
679
	if (!tn->parent)
680
		halve_threshold_use = halve_threshold_root;
681
	else
682 683
		halve_threshold_use = halve_threshold;

684
	err = 0;
R
Robert Olsson 已提交
685 686
	max_resize = 10;
	while (tn->bits > 1 &&  max_resize-- &&
687
	       100 * (tnode_child_length(tn) - tn->empty_children) <
688
	       halve_threshold_use * tnode_child_length(tn)) {
689

690 691 692 693
		old_tn = tn;
		tn = halve(t, tn);
		if (IS_ERR(tn)) {
			tn = old_tn;
694 695 696 697 698 699
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.resize_node_skipped++;
#endif
			break;
		}
	}
700

R
Robert Olsson 已提交
701 702
	if (max_resize < 0) {
		if (!tn->parent)
703 704 705
			pr_warning("Fix halve_threshold_root."
				   " Now=%d size=%d bits\n",
				   halve_threshold_root, tn->bits);
R
Robert Olsson 已提交
706
		else
707 708 709
			pr_warning("Fix halve_threshold."
				   " Now=%d size=%d bits\n",
				   halve_threshold, tn->bits);
R
Robert Olsson 已提交
710
	}
711

712 713 714
	/* 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 已提交
715
			struct node *n;
716

O
Olof Johansson 已提交
717
			n = tn->child[i];
R
Robert Olsson 已提交
718
			if (!n)
O
Olof Johansson 已提交
719 720 721 722
				continue;

			/* compress one level */

S
Stephen Hemminger 已提交
723
			node_set_parent(n, NULL);
J
Jarek Poplawski 已提交
724
			tnode_free_safe(tn);
O
Olof Johansson 已提交
725
			return n;
726 727 728 729 730
		}

	return (struct node *) tn;
}

731
static struct tnode *inflate(struct trie *t, struct tnode *tn)
732 733 734 735 736
{
	struct tnode *oldtnode = tn;
	int olen = tnode_child_length(tn);
	int i;

S
Stephen Hemminger 已提交
737
	pr_debug("In inflate\n");
738 739 740

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

S
Stephen Hemminger 已提交
741
	if (!tn)
742
		return ERR_PTR(-ENOMEM);
743 744

	/*
745 746 747
	 * 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
748 749
	 * of tnode is ignored.
	 */
O
Olof Johansson 已提交
750 751

	for (i = 0; i < olen; i++) {
752
		struct tnode *inode;
753

754
		inode = (struct tnode *) tnode_get_child(oldtnode, i);
755 756 757 758 759
		if (inode &&
		    IS_TNODE(inode) &&
		    inode->pos == oldtnode->pos + oldtnode->bits &&
		    inode->bits > 1) {
			struct tnode *left, *right;
S
Stephen Hemminger 已提交
760
			t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
761

762 763
			left = tnode_new(inode->key&(~m), inode->pos + 1,
					 inode->bits - 1);
764 765
			if (!left)
				goto nomem;
O
Olof Johansson 已提交
766

767 768 769
			right = tnode_new(inode->key|m, inode->pos + 1,
					  inode->bits - 1);

770
			if (!right) {
771 772
				tnode_free(left);
				goto nomem;
773
			}
774 775 776 777 778 779

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

O
Olof Johansson 已提交
780
	for (i = 0; i < olen; i++) {
781
		struct tnode *inode;
782
		struct node *node = tnode_get_child(oldtnode, i);
O
Olof Johansson 已提交
783 784
		struct tnode *left, *right;
		int size, j;
785

786 787 788 789 790 791
		/* An empty child */
		if (node == NULL)
			continue;

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

792
		if (IS_LEAF(node) || ((struct tnode *) node)->pos >
793
		   tn->pos + tn->bits - 1) {
794 795 796
			if (tkey_extract_bits(node->key,
					      oldtnode->pos + oldtnode->bits,
					      1) == 0)
797 798 799 800 801 802 803 804 805 806 807 808 809
				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 已提交
810
			tnode_free_safe(inode);
O
Olof Johansson 已提交
811
			continue;
812 813
		}

O
Olof Johansson 已提交
814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831
		/* 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)
		 */
832

O
Olof Johansson 已提交
833 834 835
		/* Use the old key, but set the new significant
		 *   bit to zero.
		 */
836

O
Olof Johansson 已提交
837 838
		left = (struct tnode *) tnode_get_child(tn, 2*i);
		put_child(t, tn, 2*i, NULL);
839

O
Olof Johansson 已提交
840
		BUG_ON(!left);
841

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

O
Olof Johansson 已提交
845
		BUG_ON(!right);
846

O
Olof Johansson 已提交
847 848 849 850
		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]);
851
		}
O
Olof Johansson 已提交
852 853 854
		put_child(t, tn, 2*i, resize(t, left));
		put_child(t, tn, 2*i+1, resize(t, right));

J
Jarek Poplawski 已提交
855
		tnode_free_safe(inode);
856
	}
J
Jarek Poplawski 已提交
857
	tnode_free_safe(oldtnode);
858
	return tn;
859 860 861 862 863
nomem:
	{
		int size = tnode_child_length(tn);
		int j;

S
Stephen Hemminger 已提交
864
		for (j = 0; j < size; j++)
865 866 867 868
			if (tn->child[j])
				tnode_free((struct tnode *)tn->child[j]);

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

870 871
		return ERR_PTR(-ENOMEM);
	}
872 873
}

874
static struct tnode *halve(struct trie *t, struct tnode *tn)
875 876 877 878 879 880
{
	struct tnode *oldtnode = tn;
	struct node *left, *right;
	int i;
	int olen = tnode_child_length(tn);

S
Stephen Hemminger 已提交
881
	pr_debug("In halve\n");
882 883

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

885 886
	if (!tn)
		return ERR_PTR(-ENOMEM);
887 888

	/*
889 890 891
	 * 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
892 893 894
	 * of tnode is ignored.
	 */

O
Olof Johansson 已提交
895
	for (i = 0; i < olen; i += 2) {
896 897
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
898

899
		/* Two nonempty children */
S
Stephen Hemminger 已提交
900
		if (left && right) {
901
			struct tnode *newn;
S
Stephen Hemminger 已提交
902

903
			newn = tnode_new(left->key, tn->pos + tn->bits, 1);
S
Stephen Hemminger 已提交
904 905

			if (!newn)
906
				goto nomem;
S
Stephen Hemminger 已提交
907

908
			put_child(t, tn, i/2, (struct node *)newn);
909 910 911
		}

	}
912

O
Olof Johansson 已提交
913 914 915
	for (i = 0; i < olen; i += 2) {
		struct tnode *newBinNode;

916 917
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
918

919 920 921 922 923
		/* 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 已提交
924
			continue;
S
Stephen Hemminger 已提交
925
		}
O
Olof Johansson 已提交
926 927

		if (right == NULL) {
928
			put_child(t, tn, i/2, left);
O
Olof Johansson 已提交
929 930
			continue;
		}
931

932
		/* Two nonempty children */
O
Olof Johansson 已提交
933 934 935 936 937
		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));
938
	}
J
Jarek Poplawski 已提交
939
	tnode_free_safe(oldtnode);
940
	return tn;
941 942 943 944 945
nomem:
	{
		int size = tnode_child_length(tn);
		int j;

S
Stephen Hemminger 已提交
946
		for (j = 0; j < size; j++)
947 948 949 950
			if (tn->child[j])
				tnode_free((struct tnode *)tn->child[j]);

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

952 953
		return ERR_PTR(-ENOMEM);
	}
954 955
}

R
Robert Olsson 已提交
956
/* readside must use rcu_read_lock currently dump routines
R
Robert Olsson 已提交
957 958
 via get_fa_head and dump */

R
Robert Olsson 已提交
959
static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
960
{
R
Robert Olsson 已提交
961
	struct hlist_head *head = &l->list;
962 963 964
	struct hlist_node *node;
	struct leaf_info *li;

R
Robert Olsson 已提交
965
	hlist_for_each_entry_rcu(li, node, head, hlist)
966
		if (li->plen == plen)
967
			return li;
O
Olof Johansson 已提交
968

969 970 971
	return NULL;
}

972
static inline struct list_head *get_fa_head(struct leaf *l, int plen)
973
{
R
Robert Olsson 已提交
974
	struct leaf_info *li = find_leaf_info(l, plen);
975

O
Olof Johansson 已提交
976 977
	if (!li)
		return NULL;
978

O
Olof Johansson 已提交
979
	return &li->falh;
980 981 982 983
}

static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
{
984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000
	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);
	}
1001 1002
}

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

1005 1006 1007 1008 1009 1010 1011 1012
static struct leaf *
fib_find_node(struct trie *t, u32 key)
{
	int pos;
	struct tnode *tn;
	struct node *n;

	pos = 0;
R
Robert Olsson 已提交
1013
	n = rcu_dereference(t->trie);
1014 1015 1016

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

1018
		check_tnode(tn);
O
Olof Johansson 已提交
1019

1020
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
O
Olof Johansson 已提交
1021
			pos = tn->pos + tn->bits;
1022 1023 1024 1025
			n = tnode_get_child_rcu(tn,
						tkey_extract_bits(key,
								  tn->pos,
								  tn->bits));
O
Olof Johansson 已提交
1026
		} else
1027 1028 1029 1030
			break;
	}
	/* Case we have found a leaf. Compare prefixes */

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

1034 1035 1036
	return NULL;
}

1037
static void trie_rebalance(struct trie *t, struct tnode *tn)
1038 1039
{
	int wasfull;
R
Robert Olsson 已提交
1040
	t_key cindex, key;
S
Stephen Hemminger 已提交
1041
	struct tnode *tp;
1042

R
Robert Olsson 已提交
1043 1044
	key = tn->key;

S
Stephen Hemminger 已提交
1045
	while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) {
1046 1047
		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
		wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
1048 1049 1050 1051
		tn = (struct tnode *) resize(t, (struct tnode *)tn);

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

S
Stephen Hemminger 已提交
1053
		tp = node_parent((struct node *) tn);
1054 1055 1056
		if (!tp)
			rcu_assign_pointer(t->trie, (struct node *)tn);

J
Jarek Poplawski 已提交
1057
		tnode_free_flush();
S
Stephen Hemminger 已提交
1058
		if (!tp)
1059
			break;
S
Stephen Hemminger 已提交
1060
		tn = tp;
1061
	}
S
Stephen Hemminger 已提交
1062

1063
	/* Handle last (top) tnode */
1064
	if (IS_TNODE(tn))
1065
		tn = (struct tnode *)resize(t, (struct tnode *)tn);
1066

1067 1068 1069 1070
	rcu_assign_pointer(t->trie, (struct node *)tn);
	tnode_free_flush();

	return;
1071 1072
}

R
Robert Olsson 已提交
1073 1074
/* only used from updater-side */

1075
static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
1076 1077 1078 1079 1080 1081
{
	int pos, newpos;
	struct tnode *tp = NULL, *tn = NULL;
	struct node *n;
	struct leaf *l;
	int missbit;
1082
	struct list_head *fa_head = NULL;
1083 1084 1085 1086
	struct leaf_info *li;
	t_key cindex;

	pos = 0;
1087
	n = t->trie;
1088

1089 1090
	/* 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,
1091
	 * and we should just put our new leaf in that.
1092 1093
	 * 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
1094 1095
	 * not be the parent's 'pos'+'bits'!
	 *
1096
	 * If it does match the current key, get pos/bits from it, extract
1097 1098 1099 1100
	 * 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.
	 *
1101 1102 1103
	 * 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.
1104 1105 1106 1107 1108
	 * 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 已提交
1109

1110
		check_tnode(tn);
O
Olof Johansson 已提交
1111

1112
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1113
			tp = tn;
O
Olof Johansson 已提交
1114
			pos = tn->pos + tn->bits;
1115 1116 1117 1118
			n = tnode_get_child(tn,
					    tkey_extract_bits(key,
							      tn->pos,
							      tn->bits));
1119

S
Stephen Hemminger 已提交
1120
			BUG_ON(n && node_parent(n) != tn);
O
Olof Johansson 已提交
1121
		} else
1122 1123 1124 1125 1126 1127
			break;
	}

	/*
	 * n  ----> NULL, LEAF or TNODE
	 *
1128
	 * tp is n's (parent) ----> NULL or TNODE
1129 1130
	 */

O
Olof Johansson 已提交
1131
	BUG_ON(tp && IS_LEAF(tp));
1132 1133 1134

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

1135
	if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1136
		l = (struct leaf *) n;
1137
		li = leaf_info_new(plen);
O
Olof Johansson 已提交
1138

1139 1140
		if (!li)
			return NULL;
1141 1142 1143 1144 1145 1146 1147

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

1148 1149
	if (!l)
		return NULL;
1150 1151 1152 1153

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

1154
	if (!li) {
1155
		free_leaf(l);
1156
		return NULL;
1157
	}
1158 1159 1160 1161 1162

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

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

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

O
Olof Johansson 已提交
1167 1168 1169 1170
		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. */
1171 1172
		/*
		 *  Add a new tnode here
1173 1174 1175 1176
		 *  first tnode need some special handling
		 */

		if (tp)
O
Olof Johansson 已提交
1177
			pos = tp->pos+tp->bits;
1178
		else
O
Olof Johansson 已提交
1179 1180
			pos = 0;

1181
		if (n) {
1182 1183
			newpos = tkey_mismatch(key, pos, n->key);
			tn = tnode_new(n->key, newpos, 1);
O
Olof Johansson 已提交
1184
		} else {
1185
			newpos = 0;
1186
			tn = tnode_new(key, newpos, 1); /* First tnode */
1187 1188
		}

1189
		if (!tn) {
1190
			free_leaf_info(li);
1191
			free_leaf(l);
1192
			return NULL;
O
Olof Johansson 已提交
1193 1194
		}

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

O
Olof Johansson 已提交
1197
		missbit = tkey_extract_bits(key, newpos, 1);
1198 1199 1200
		put_child(t, tn, missbit, (struct node *)l);
		put_child(t, tn, 1-missbit, n);

1201
		if (tp) {
1202
			cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1203 1204
			put_child(t, (struct tnode *)tp, cindex,
				  (struct node *)tn);
O
Olof Johansson 已提交
1205
		} else {
1206
			rcu_assign_pointer(t->trie, (struct node *)tn);
1207 1208 1209
			tp = tn;
		}
	}
O
Olof Johansson 已提交
1210 1211

	if (tp && tp->pos + tp->bits > 32)
1212 1213 1214
		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 已提交
1215

1216
	/* Rebalance the trie */
R
Robert Olsson 已提交
1217

1218
	trie_rebalance(t, tp);
1219
done:
1220 1221 1222
	return fa_head;
}

1223 1224 1225
/*
 * Caller must hold RTNL.
 */
1226
static int fn_trie_insert(struct fib_table *tb, struct fib_config *cfg)
1227 1228 1229
{
	struct trie *t = (struct trie *) tb->tb_data;
	struct fib_alias *fa, *new_fa;
1230
	struct list_head *fa_head = NULL;
1231
	struct fib_info *fi;
1232 1233
	int plen = cfg->fc_dst_len;
	u8 tos = cfg->fc_tos;
1234 1235 1236 1237 1238 1239 1240
	u32 key, mask;
	int err;
	struct leaf *l;

	if (plen > 32)
		return -EINVAL;

1241
	key = ntohl(cfg->fc_dst);
1242

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

O
Olof Johansson 已提交
1245
	mask = ntohl(inet_make_mask(plen));
1246

1247
	if (key & ~mask)
1248 1249 1250 1251
		return -EINVAL;

	key = key & mask;

1252 1253 1254
	fi = fib_create_info(cfg);
	if (IS_ERR(fi)) {
		err = PTR_ERR(fi);
1255
		goto err;
1256
	}
1257 1258

	l = fib_find_node(t, key);
1259
	fa = NULL;
1260

1261
	if (l) {
1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276
		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.
	 */

1277 1278 1279
	if (fa && fa->fa_tos == tos &&
	    fa->fa_info->fib_priority == fi->fib_priority) {
		struct fib_alias *fa_first, *fa_match;
1280 1281

		err = -EEXIST;
1282
		if (cfg->fc_nlflags & NLM_F_EXCL)
1283 1284
			goto out;

1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305
		/* 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;
			}
		}

1306
		if (cfg->fc_nlflags & NLM_F_REPLACE) {
1307 1308 1309
			struct fib_info *fi_drop;
			u8 state;

1310 1311 1312 1313
			fa = fa_first;
			if (fa_match) {
				if (fa == fa_match)
					err = 0;
1314
				goto out;
1315
			}
R
Robert Olsson 已提交
1316
			err = -ENOBUFS;
1317
			new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
R
Robert Olsson 已提交
1318 1319
			if (new_fa == NULL)
				goto out;
1320 1321

			fi_drop = fa->fa_info;
R
Robert Olsson 已提交
1322 1323
			new_fa->fa_tos = fa->fa_tos;
			new_fa->fa_info = fi;
1324 1325
			new_fa->fa_type = cfg->fc_type;
			new_fa->fa_scope = cfg->fc_scope;
1326
			state = fa->fa_state;
1327
			new_fa->fa_state = state & ~FA_S_ACCESSED;
1328

R
Robert Olsson 已提交
1329 1330
			list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
			alias_free_mem_rcu(fa);
1331 1332 1333

			fib_release_info(fi_drop);
			if (state & FA_S_ACCESSED)
1334
				rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1335 1336
			rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
				tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1337

O
Olof Johansson 已提交
1338
			goto succeeded;
1339 1340 1341 1342 1343
		}
		/* Error if we find a perfect match which
		 * uses the same scope, type, and nexthop
		 * information.
		 */
1344 1345
		if (fa_match)
			goto out;
1346

1347
		if (!(cfg->fc_nlflags & NLM_F_APPEND))
1348
			fa = fa_first;
1349 1350
	}
	err = -ENOENT;
1351
	if (!(cfg->fc_nlflags & NLM_F_CREATE))
1352 1353 1354
		goto out;

	err = -ENOBUFS;
1355
	new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1356 1357 1358 1359 1360
	if (new_fa == NULL)
		goto out;

	new_fa->fa_info = fi;
	new_fa->fa_tos = tos;
1361 1362
	new_fa->fa_type = cfg->fc_type;
	new_fa->fa_scope = cfg->fc_scope;
1363 1364 1365 1366 1367
	new_fa->fa_state = 0;
	/*
	 * Insert new entry to the list.
	 */

1368
	if (!fa_head) {
1369 1370 1371
		fa_head = fib_insert_node(t, key, plen);
		if (unlikely(!fa_head)) {
			err = -ENOMEM;
1372
			goto out_free_new_fa;
1373
		}
1374
	}
1375

R
Robert Olsson 已提交
1376 1377
	list_add_tail_rcu(&new_fa->fa_list,
			  (fa ? &fa->fa_list : fa_head));
1378

1379
	rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1380
	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1381
		  &cfg->fc_nlinfo, 0);
1382 1383
succeeded:
	return 0;
1384 1385 1386

out_free_new_fa:
	kmem_cache_free(fn_alias_kmem, new_fa);
1387 1388
out:
	fib_release_info(fi);
O
Olof Johansson 已提交
1389
err:
1390 1391 1392
	return err;
}

R
Robert Olsson 已提交
1393
/* should be called with rcu_read_lock */
1394 1395 1396
static int check_leaf(struct trie *t, struct leaf *l,
		      t_key key,  const struct flowi *flp,
		      struct fib_result *res)
1397 1398 1399 1400
{
	struct leaf_info *li;
	struct hlist_head *hhead = &l->list;
	struct hlist_node *node;
1401

R
Robert Olsson 已提交
1402
	hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1403 1404 1405 1406
		int err;
		int plen = li->plen;
		__be32 mask = inet_make_mask(plen);

1407
		if (l->key != (key & ntohl(mask)))
1408 1409
			continue;

1410
		err = fib_semantic_match(&li->falh, flp, res, plen);
1411

1412
#ifdef CONFIG_IP_FIB_TRIE_STATS
1413
		if (err <= 0)
1414
			t->stats.semantic_match_passed++;
1415 1416
		else
			t->stats.semantic_match_miss++;
1417
#endif
1418
		if (err <= 0)
1419
			return err;
1420
	}
1421

1422
	return 1;
1423 1424
}

1425 1426
static int fn_trie_lookup(struct fib_table *tb, const struct flowi *flp,
			  struct fib_result *res)
1427 1428
{
	struct trie *t = (struct trie *) tb->tb_data;
1429
	int ret;
1430 1431 1432
	struct node *n;
	struct tnode *pn;
	int pos, bits;
O
Olof Johansson 已提交
1433
	t_key key = ntohl(flp->fl4_dst);
1434 1435 1436
	int chopped_off;
	t_key cindex = 0;
	int current_prefix_length = KEYLENGTH;
O
Olof Johansson 已提交
1437 1438 1439 1440
	struct tnode *cn;
	t_key node_prefix, key_prefix, pref_mismatch;
	int mp;

R
Robert Olsson 已提交
1441
	rcu_read_lock();
O
Olof Johansson 已提交
1442

R
Robert Olsson 已提交
1443
	n = rcu_dereference(t->trie);
1444
	if (!n)
1445 1446 1447 1448 1449 1450 1451 1452
		goto failed;

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

	/* Just a leaf? */
	if (IS_LEAF(n)) {
1453
		ret = check_leaf(t, (struct leaf *)n, key, flp, res);
1454
		goto found;
1455
	}
1456

1457 1458
	pn = (struct tnode *) n;
	chopped_off = 0;
1459

O
Olof Johansson 已提交
1460
	while (pn) {
1461 1462 1463
		pos = pn->pos;
		bits = pn->bits;

1464
		if (!chopped_off)
S
Stephen Hemminger 已提交
1465 1466
			cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
						   pos, bits);
1467

1468
		n = tnode_get_child_rcu(pn, cindex);
1469 1470 1471 1472 1473 1474 1475 1476

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

O
Olof Johansson 已提交
1477
		if (IS_LEAF(n)) {
1478 1479
			ret = check_leaf(t, (struct leaf *)n, key, flp, res);
			if (ret > 0)
O
Olof Johansson 已提交
1480
				goto backtrace;
1481
			goto found;
O
Olof Johansson 已提交
1482 1483 1484
		}

		cn = (struct tnode *)n;
1485

O
Olof Johansson 已提交
1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500
		/*
		 * 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].
		 */
1501

O
Olof Johansson 已提交
1502 1503 1504 1505 1506 1507 1508 1509 1510
		/* 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.
		 */
1511

1512 1513
		/* NOTA BENE: Checking only skipped bits
		   for the new node here */
1514

O
Olof Johansson 已提交
1515 1516
		if (current_prefix_length < pos+bits) {
			if (tkey_extract_bits(cn->key, current_prefix_length,
1517 1518
						cn->pos - current_prefix_length)
			    || !(cn->child[0]))
O
Olof Johansson 已提交
1519 1520
				goto backtrace;
		}
1521

O
Olof Johansson 已提交
1522 1523 1524 1525 1526 1527 1528 1529 1530
		/*
		 * 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.
		 */
1531

O
Olof Johansson 已提交
1532 1533 1534 1535 1536 1537 1538 1539
		/* 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.
		 */
1540

1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551
		/*
		 * 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 已提交
1552 1553
		 */

S
Stephen Hemminger 已提交
1554 1555
		node_prefix = mask_pfx(cn->key, cn->pos);
		key_prefix = mask_pfx(key, cn->pos);
O
Olof Johansson 已提交
1556 1557 1558
		pref_mismatch = key_prefix^node_prefix;
		mp = 0;

1559 1560 1561 1562
		/*
		 * In short: If skipped bits in this node do not match
		 * the search key, enter the "prefix matching"
		 * state.directly.
O
Olof Johansson 已提交
1563 1564 1565 1566
		 */
		if (pref_mismatch) {
			while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
				mp++;
1567
				pref_mismatch = pref_mismatch << 1;
O
Olof Johansson 已提交
1568 1569 1570 1571 1572 1573 1574 1575
			}
			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;
1576
		}
1577

O
Olof Johansson 已提交
1578 1579 1580 1581
		pn = (struct tnode *)n; /* Descend */
		chopped_off = 0;
		continue;

1582 1583 1584 1585
backtrace:
		chopped_off++;

		/* As zero don't change the child key (cindex) */
1586 1587
		while ((chopped_off <= pn->bits)
		       && !(cindex & (1<<(chopped_off-1))))
1588 1589 1590 1591
			chopped_off++;

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

1595
		/*
1596
		 * Either we do the actual chop off according or if we have
1597 1598 1599
		 * chopped off all bits in this tnode walk up to our parent.
		 */

O
Olof Johansson 已提交
1600
		if (chopped_off <= pn->bits) {
1601
			cindex &= ~(1 << (chopped_off-1));
O
Olof Johansson 已提交
1602
		} else {
1603
			struct tnode *parent = node_parent_rcu((struct node *) pn);
S
Stephen Hemminger 已提交
1604
			if (!parent)
1605
				goto failed;
O
Olof Johansson 已提交
1606

1607
			/* Get Child's index */
S
Stephen Hemminger 已提交
1608 1609
			cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
			pn = parent;
1610 1611 1612 1613 1614 1615
			chopped_off = 0;

#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.backtrack++;
#endif
			goto backtrace;
1616
		}
1617 1618
	}
failed:
1619
	ret = 1;
1620
found:
R
Robert Olsson 已提交
1621
	rcu_read_unlock();
1622 1623 1624
	return ret;
}

1625 1626 1627 1628
/*
 * Remove the leaf and return parent.
 */
static void trie_leaf_remove(struct trie *t, struct leaf *l)
1629
{
1630
	struct tnode *tp = node_parent((struct node *) l);
1631

1632
	pr_debug("entering trie_leaf_remove(%p)\n", l);
1633

1634
	if (tp) {
1635
		t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1636
		put_child(t, (struct tnode *)tp, cindex, NULL);
1637
		trie_rebalance(t, tp);
O
Olof Johansson 已提交
1638
	} else
R
Robert Olsson 已提交
1639
		rcu_assign_pointer(t->trie, NULL);
1640

1641
	free_leaf(l);
1642 1643
}

1644 1645 1646
/*
 * Caller must hold RTNL.
 */
1647
static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
1648 1649 1650
{
	struct trie *t = (struct trie *) tb->tb_data;
	u32 key, mask;
1651 1652
	int plen = cfg->fc_dst_len;
	u8 tos = cfg->fc_tos;
1653 1654 1655
	struct fib_alias *fa, *fa_to_delete;
	struct list_head *fa_head;
	struct leaf *l;
O
Olof Johansson 已提交
1656 1657
	struct leaf_info *li;

1658
	if (plen > 32)
1659 1660
		return -EINVAL;

1661
	key = ntohl(cfg->fc_dst);
O
Olof Johansson 已提交
1662
	mask = ntohl(inet_make_mask(plen));
1663

1664
	if (key & ~mask)
1665 1666 1667 1668 1669
		return -EINVAL;

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

1670
	if (!l)
1671 1672 1673 1674 1675 1676 1677 1678
		return -ESRCH;

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

	if (!fa)
		return -ESRCH;

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

	fa_to_delete = NULL;
1682 1683
	fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
	list_for_each_entry_continue(fa, fa_head, fa_list) {
1684 1685 1686 1687 1688
		struct fib_info *fi = fa->fa_info;

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

1689 1690 1691 1692 1693 1694
		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) {
1695 1696 1697 1698 1699
			fa_to_delete = fa;
			break;
		}
	}

O
Olof Johansson 已提交
1700 1701
	if (!fa_to_delete)
		return -ESRCH;
1702

O
Olof Johansson 已提交
1703
	fa = fa_to_delete;
1704
	rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1705
		  &cfg->fc_nlinfo, 0);
O
Olof Johansson 已提交
1706 1707

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

R
Robert Olsson 已提交
1710
	list_del_rcu(&fa->fa_list);
1711

O
Olof Johansson 已提交
1712
	if (list_empty(fa_head)) {
R
Robert Olsson 已提交
1713
		hlist_del_rcu(&li->hlist);
O
Olof Johansson 已提交
1714
		free_leaf_info(li);
R
Robert Olsson 已提交
1715
	}
1716

O
Olof Johansson 已提交
1717
	if (hlist_empty(&l->list))
1718
		trie_leaf_remove(t, l);
1719

O
Olof Johansson 已提交
1720
	if (fa->fa_state & FA_S_ACCESSED)
1721
		rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1722

R
Robert Olsson 已提交
1723 1724
	fib_release_info(fa->fa_info);
	alias_free_mem_rcu(fa);
O
Olof Johansson 已提交
1725
	return 0;
1726 1727
}

1728
static int trie_flush_list(struct list_head *head)
1729 1730 1731 1732 1733 1734 1735
{
	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 已提交
1736 1737 1738 1739
		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);
1740 1741 1742 1743 1744 1745
			found++;
		}
	}
	return found;
}

1746
static int trie_flush_leaf(struct leaf *l)
1747 1748 1749 1750 1751 1752 1753
{
	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) {
1754
		found += trie_flush_list(&li->falh);
1755 1756

		if (list_empty(&li->falh)) {
R
Robert Olsson 已提交
1757
			hlist_del_rcu(&li->hlist);
1758 1759 1760 1761 1762 1763
			free_leaf_info(li);
		}
	}
	return found;
}

1764 1765 1766 1767 1768
/*
 * 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)
1769
{
1770 1771
	do {
		t_key idx;
1772 1773

		if (c)
1774
			idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1775
		else
1776
			idx = 0;
R
Robert Olsson 已提交
1777

1778 1779
		while (idx < 1u << p->bits) {
			c = tnode_get_child_rcu(p, idx++);
R
Robert Olsson 已提交
1780
			if (!c)
O
Olof Johansson 已提交
1781 1782
				continue;

1783 1784 1785
			if (IS_LEAF(c)) {
				prefetch(p->child[idx]);
				return (struct leaf *) c;
1786
			}
1787 1788 1789 1790

			/* Rescan start scanning in new node */
			p = (struct tnode *) c;
			idx = 0;
1791
		}
1792 1793

		/* Node empty, walk back up to parent */
O
Olof Johansson 已提交
1794
		c = (struct node *) p;
1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815
	} 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;
1816
	struct tnode *p = node_parent_rcu(c);
1817 1818 1819 1820 1821

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

	return leaf_walk_rcu(p, c);
1822 1823
}

1824 1825 1826 1827
static struct leaf *trie_leafindex(struct trie *t, int index)
{
	struct leaf *l = trie_firstleaf(t);

S
Stephen Hemminger 已提交
1828
	while (l && index-- > 0)
1829
		l = trie_nextleaf(l);
S
Stephen Hemminger 已提交
1830

1831 1832 1833 1834
	return l;
}


1835 1836 1837
/*
 * Caller must hold RTNL.
 */
1838 1839 1840
static int fn_trie_flush(struct fib_table *tb)
{
	struct trie *t = (struct trie *) tb->tb_data;
1841
	struct leaf *l, *ll = NULL;
1842
	int found = 0;
1843

1844
	for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1845
		found += trie_flush_leaf(l);
1846 1847

		if (ll && hlist_empty(&ll->list))
1848
			trie_leaf_remove(t, ll);
1849 1850 1851 1852
		ll = l;
	}

	if (ll && hlist_empty(&ll->list))
1853
		trie_leaf_remove(t, ll);
1854

S
Stephen Hemminger 已提交
1855
	pr_debug("trie_flush found=%d\n", found);
1856 1857 1858
	return found;
}

1859 1860 1861
static void fn_trie_select_default(struct fib_table *tb,
				   const struct flowi *flp,
				   struct fib_result *res)
1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874
{
	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 已提交
1875
	rcu_read_lock();
1876

1877
	l = fib_find_node(t, 0);
1878
	if (!l)
1879 1880 1881
		goto out;

	fa_head = get_fa_head(l, 0);
1882
	if (!fa_head)
1883 1884
		goto out;

1885
	if (list_empty(fa_head))
1886 1887
		goto out;

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

1891 1892 1893
		if (fa->fa_scope != res->scope ||
		    fa->fa_type != RTN_UNICAST)
			continue;
O
Olof Johansson 已提交
1894

1895 1896 1897 1898 1899 1900
		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 已提交
1901

1902 1903 1904 1905
		if (fi == NULL) {
			if (next_fi != res->fi)
				break;
		} else if (!fib_detect_death(fi, order, &last_resort,
1906
					     &last_idx, tb->tb_default)) {
1907
			fib_result_assign(res, fi);
1908
			tb->tb_default = order;
1909 1910 1911 1912 1913 1914
			goto out;
		}
		fi = next_fi;
		order++;
	}
	if (order <= 0 || fi == NULL) {
1915
		tb->tb_default = -1;
1916 1917 1918
		goto out;
	}

1919 1920
	if (!fib_detect_death(fi, order, &last_resort, &last_idx,
				tb->tb_default)) {
1921
		fib_result_assign(res, fi);
1922
		tb->tb_default = order;
1923 1924
		goto out;
	}
1925 1926
	if (last_idx >= 0)
		fib_result_assign(res, last_resort);
1927 1928
	tb->tb_default = last_idx;
out:
R
Robert Olsson 已提交
1929
	rcu_read_unlock();
1930 1931
}

1932 1933
static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
			   struct fib_table *tb,
1934 1935 1936 1937
			   struct sk_buff *skb, struct netlink_callback *cb)
{
	int i, s_i;
	struct fib_alias *fa;
A
Al Viro 已提交
1938
	__be32 xkey = htonl(key);
1939

1940
	s_i = cb->args[5];
1941 1942
	i = 0;

R
Robert Olsson 已提交
1943 1944 1945
	/* rcu_read_lock is hold by caller */

	list_for_each_entry_rcu(fa, fah, fa_list) {
1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956
		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,
1957
				  xkey,
1958 1959
				  plen,
				  fa->fa_tos,
1960
				  fa->fa_info, NLM_F_MULTI) < 0) {
1961
			cb->args[5] = i;
1962
			return -1;
O
Olof Johansson 已提交
1963
		}
1964 1965
		i++;
	}
1966
	cb->args[5] = i;
1967 1968 1969
	return skb->len;
}

1970 1971
static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
			struct sk_buff *skb, struct netlink_callback *cb)
1972
{
1973 1974 1975
	struct leaf_info *li;
	struct hlist_node *node;
	int i, s_i;
1976

1977
	s_i = cb->args[4];
1978
	i = 0;
1979

1980 1981 1982 1983
	/* rcu_read_lock is hold by caller */
	hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
		if (i < s_i) {
			i++;
1984
			continue;
1985
		}
O
Olof Johansson 已提交
1986

1987
		if (i > s_i)
1988
			cb->args[5] = 0;
1989

1990
		if (list_empty(&li->falh))
1991 1992
			continue;

1993
		if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1994
			cb->args[4] = i;
1995 1996
			return -1;
		}
1997
		i++;
1998
	}
1999

2000
	cb->args[4] = i;
2001 2002 2003
	return skb->len;
}

2004 2005
static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb,
			struct netlink_callback *cb)
2006
{
2007
	struct leaf *l;
2008
	struct trie *t = (struct trie *) tb->tb_data;
2009
	t_key key = cb->args[2];
2010
	int count = cb->args[3];
2011

R
Robert Olsson 已提交
2012
	rcu_read_lock();
2013 2014 2015
	/* Dump starting at last key.
	 * Note: 0.0.0.0/0 (ie default) is first key.
	 */
2016
	if (count == 0)
2017 2018
		l = trie_firstleaf(t);
	else {
2019 2020 2021
		/* Normally, continue from last key, but if that is missing
		 * fallback to using slow rescan
		 */
2022
		l = fib_find_node(t, key);
2023 2024
		if (!l)
			l = trie_leafindex(t, count);
2025
	}
2026

2027 2028
	while (l) {
		cb->args[2] = l->key;
2029
		if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
2030
			cb->args[3] = count;
2031 2032
			rcu_read_unlock();
			return -1;
2033
		}
2034

2035
		++count;
2036
		l = trie_nextleaf(l);
2037 2038
		memset(&cb->args[4], 0,
		       sizeof(cb->args) - 4*sizeof(cb->args[0]));
2039
	}
2040
	cb->args[3] = count;
R
Robert Olsson 已提交
2041
	rcu_read_unlock();
2042

2043 2044 2045
	return skb->len;
}

2046 2047
void __init fib_hash_init(void)
{
2048 2049
	fn_alias_kmem = kmem_cache_create("ip_fib_alias",
					  sizeof(struct fib_alias),
2050 2051 2052 2053 2054 2055
					  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);
2056
}
2057

2058 2059 2060

/* Fix more generic FIB names for init later */
struct fib_table *fib_hash_table(u32 id)
2061 2062 2063 2064 2065 2066 2067 2068 2069 2070
{
	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;
2071
	tb->tb_default = -1;
2072 2073 2074 2075 2076 2077 2078 2079
	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;
2080
	memset(t, 0, sizeof(*t));
2081 2082

	if (id == RT_TABLE_LOCAL)
2083
		pr_info("IPv4 FIB: Using LC-trie version %s\n", VERSION);
2084 2085 2086 2087

	return tb;
}

2088 2089 2090
#ifdef CONFIG_PROC_FS
/* Depth first Trie walk iterator */
struct fib_trie_iter {
2091
	struct seq_net_private p;
2092
	struct fib_table *tb;
2093 2094 2095 2096
	struct tnode *tnode;
	unsigned index;
	unsigned depth;
};
2097

2098
static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
2099
{
2100 2101 2102
	struct tnode *tn = iter->tnode;
	unsigned cindex = iter->index;
	struct tnode *p;
2103

2104 2105 2106 2107
	/* A single entry routing table */
	if (!tn)
		return NULL;

2108 2109 2110 2111
	pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
		 iter->tnode, iter->index, iter->depth);
rescan:
	while (cindex < (1<<tn->bits)) {
2112
		struct node *n = tnode_get_child_rcu(tn, cindex);
2113

2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125
		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;
		}
2126

2127 2128
		++cindex;
	}
O
Olof Johansson 已提交
2129

2130
	/* Current node exhausted, pop back up */
2131
	p = node_parent_rcu((struct node *)tn);
2132 2133 2134 2135 2136
	if (p) {
		cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
		tn = p;
		--iter->depth;
		goto rescan;
2137
	}
2138 2139 2140

	/* got root? */
	return NULL;
2141 2142
}

2143 2144
static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
				       struct trie *t)
2145
{
2146
	struct node *n;
2147

S
Stephen Hemminger 已提交
2148
	if (!t)
2149 2150 2151
		return NULL;

	n = rcu_dereference(t->trie);
2152
	if (!n)
2153
		return NULL;
2154

2155 2156 2157 2158 2159 2160 2161 2162
	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 已提交
2163
	}
2164 2165

	return n;
2166
}
O
Olof Johansson 已提交
2167

2168 2169 2170 2171
static void trie_collect_stats(struct trie *t, struct trie_stat *s)
{
	struct node *n;
	struct fib_trie_iter iter;
O
Olof Johansson 已提交
2172

2173
	memset(s, 0, sizeof(*s));
O
Olof Johansson 已提交
2174

2175
	rcu_read_lock();
2176
	for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2177
		if (IS_LEAF(n)) {
2178 2179 2180 2181
			struct leaf *l = (struct leaf *)n;
			struct leaf_info *li;
			struct hlist_node *tmp;

2182 2183 2184 2185
			s->leaves++;
			s->totdepth += iter.depth;
			if (iter.depth > s->maxdepth)
				s->maxdepth = iter.depth;
2186 2187 2188

			hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
				++s->prefixes;
2189 2190 2191 2192 2193
		} else {
			const struct tnode *tn = (const struct tnode *) n;
			int i;

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

2197 2198 2199
			for (i = 0; i < (1<<tn->bits); i++)
				if (!tn->child[i])
					s->nullpointers++;
2200 2201
		}
	}
R
Robert Olsson 已提交
2202
	rcu_read_unlock();
2203 2204
}

2205 2206 2207 2208
/*
 *	This outputs /proc/net/fib_triestats
 */
static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2209
{
2210
	unsigned i, max, pointers, bytes, avdepth;
2211

2212 2213 2214 2215
	if (stat->leaves)
		avdepth = stat->totdepth*100 / stat->leaves;
	else
		avdepth = 0;
O
Olof Johansson 已提交
2216

2217 2218
	seq_printf(seq, "\tAver depth:     %u.%02d\n",
		   avdepth / 100, avdepth % 100);
2219
	seq_printf(seq, "\tMax depth:      %u\n", stat->maxdepth);
O
Olof Johansson 已提交
2220

2221 2222
	seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
	bytes = sizeof(struct leaf) * stat->leaves;
2223 2224 2225 2226

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

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

R
Robert Olsson 已提交
2230 2231
	max = MAX_STAT_DEPTH;
	while (max > 0 && stat->nodesizes[max-1] == 0)
2232
		max--;
2233

2234 2235 2236
	pointers = 0;
	for (i = 1; i <= max; i++)
		if (stat->nodesizes[i] != 0) {
2237
			seq_printf(seq, "  %u: %u",  i, stat->nodesizes[i]);
2238 2239 2240
			pointers += (1<<i) * stat->nodesizes[i];
		}
	seq_putc(seq, '\n');
2241
	seq_printf(seq, "\tPointers: %u\n", pointers);
R
Robert Olsson 已提交
2242

2243
	bytes += sizeof(struct node *) * pointers;
2244 2245
	seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
	seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
2246
}
R
Robert Olsson 已提交
2247

2248
#ifdef CONFIG_IP_FIB_TRIE_STATS
2249 2250 2251 2252
static void trie_show_usage(struct seq_file *seq,
			    const struct trie_use_stats *stats)
{
	seq_printf(seq, "\nCounters:\n---------\n");
2253 2254 2255 2256 2257 2258 2259 2260 2261
	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);
2262
}
2263 2264
#endif /*  CONFIG_IP_FIB_TRIE_STATS */

2265
static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2266
{
2267 2268 2269 2270 2271 2272
	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);
2273
}
2274

2275

2276 2277
static int fib_triestat_seq_show(struct seq_file *seq, void *v)
{
2278
	struct net *net = (struct net *)seq->private;
2279
	unsigned int h;
2280

2281
	seq_printf(seq,
2282 2283
		   "Basic info: size of leaf:"
		   " %Zd bytes, size of tnode: %Zd bytes.\n",
2284 2285
		   sizeof(struct leaf), sizeof(struct tnode));

2286 2287 2288 2289 2290 2291 2292 2293
	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;
2294

2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306
			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
		}
	}
2307

2308
	return 0;
2309 2310
}

2311
static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2312
{
2313
	return single_open_net(inode, file, fib_triestat_seq_show);
2314 2315
}

2316
static const struct file_operations fib_triestat_fops = {
2317 2318 2319 2320
	.owner	= THIS_MODULE,
	.open	= fib_triestat_seq_open,
	.read	= seq_read,
	.llseek	= seq_lseek,
2321
	.release = single_release_net,
2322 2323
};

2324
static struct node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2325
{
2326 2327
	struct fib_trie_iter *iter = seq->private;
	struct net *net = seq_file_net(seq);
2328
	loff_t idx = 0;
2329
	unsigned int h;
2330

2331 2332 2333 2334
	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;
2335

2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346
		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;
				}
		}
2347
	}
2348

2349 2350 2351
	return NULL;
}

2352
static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2353
	__acquires(RCU)
2354
{
2355
	rcu_read_lock();
2356
	return fib_trie_get_idx(seq, *pos);
2357 2358
}

2359
static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2360
{
2361
	struct fib_trie_iter *iter = seq->private;
2362
	struct net *net = seq_file_net(seq);
2363 2364 2365 2366
	struct fib_table *tb = iter->tb;
	struct hlist_node *tb_node;
	unsigned int h;
	struct node *n;
2367

2368
	++*pos;
2369 2370 2371 2372
	/* next node in same table */
	n = fib_trie_get_next(iter);
	if (n)
		return n;
2373

2374 2375 2376 2377 2378 2379 2380 2381
	/* 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;
	}
2382

2383 2384 2385 2386 2387 2388 2389 2390 2391
	/* 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;
		}
	}
2392
	return NULL;
2393 2394 2395 2396

found:
	iter->tb = tb;
	return n;
2397
}
2398

2399
static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2400
	__releases(RCU)
2401
{
2402 2403
	rcu_read_unlock();
}
O
Olof Johansson 已提交
2404

2405 2406 2407 2408
static void seq_indent(struct seq_file *seq, int n)
{
	while (n-- > 0) seq_puts(seq, "   ");
}
2409

2410
static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2411
{
S
Stephen Hemminger 已提交
2412
	switch (s) {
2413 2414 2415 2416 2417 2418
	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:
2419
		snprintf(buf, len, "scope=%d", s);
2420 2421 2422
		return buf;
	}
}
2423

2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437
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",
};
2438

2439
static inline const char *rtn_type(char *buf, size_t len, unsigned t)
2440 2441 2442
{
	if (t < __RTN_MAX && rtn_type_names[t])
		return rtn_type_names[t];
2443
	snprintf(buf, len, "type %u", t);
2444
	return buf;
2445 2446
}

2447 2448
/* Pretty print the trie */
static int fib_trie_seq_show(struct seq_file *seq, void *v)
2449
{
2450 2451
	const struct fib_trie_iter *iter = seq->private;
	struct node *n = v;
2452

2453 2454
	if (!node_parent_rcu(n))
		fib_table_print(seq, iter->tb);
2455

2456 2457
	if (IS_TNODE(n)) {
		struct tnode *tn = (struct tnode *) n;
S
Stephen Hemminger 已提交
2458
		__be32 prf = htonl(mask_pfx(tn->key, tn->pos));
O
Olof Johansson 已提交
2459

2460
		seq_indent(seq, iter->depth-1);
2461 2462
		seq_printf(seq, "  +-- %pI4/%d %d %d %d\n",
			   &prf, tn->pos, tn->bits, tn->full_children,
2463
			   tn->empty_children);
2464

2465 2466
	} else {
		struct leaf *l = (struct leaf *) n;
2467 2468
		struct leaf_info *li;
		struct hlist_node *node;
A
Al Viro 已提交
2469
		__be32 val = htonl(l->key);
2470 2471

		seq_indent(seq, iter->depth);
2472
		seq_printf(seq, "  |-- %pI4\n", &val);
2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486

		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)
2487
					seq_printf(seq, " tos=%d", fa->fa_tos);
2488
				seq_putc(seq, '\n');
2489 2490
			}
		}
2491
	}
2492

2493 2494 2495
	return 0;
}

2496
static const struct seq_operations fib_trie_seq_ops = {
2497 2498 2499 2500
	.start  = fib_trie_seq_start,
	.next   = fib_trie_seq_next,
	.stop   = fib_trie_seq_stop,
	.show   = fib_trie_seq_show,
2501 2502
};

2503
static int fib_trie_seq_open(struct inode *inode, struct file *file)
2504
{
2505 2506
	return seq_open_net(inode, file, &fib_trie_seq_ops,
			    sizeof(struct fib_trie_iter));
2507 2508
}

2509
static const struct file_operations fib_trie_fops = {
2510 2511 2512 2513
	.owner  = THIS_MODULE,
	.open   = fib_trie_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2514
	.release = seq_release_net,
2515 2516
};

2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556
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();
2557
	tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594
	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 已提交
2595
static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2596
{
2597 2598 2599 2600
	static unsigned type2flags[RTN_MAX + 1] = {
		[7] = RTF_REJECT, [8] = RTF_REJECT,
	};
	unsigned flags = type2flags[type];
2601

2602 2603
	if (fi && fi->fib_nh->nh_gw)
		flags |= RTF_GATEWAY;
A
Al Viro 已提交
2604
	if (mask == htonl(0xFFFFFFFF))
2605 2606 2607
		flags |= RTF_HOST;
	flags |= RTF_UP;
	return flags;
2608 2609
}

2610 2611 2612 2613 2614 2615 2616
/*
 *	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)
2617
{
2618
	struct leaf *l = v;
2619 2620
	struct leaf_info *li;
	struct hlist_node *node;
2621

2622 2623 2624 2625 2626 2627
	if (v == SEQ_START_TOKEN) {
		seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
			   "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
			   "\tWindow\tIRTT");
		return 0;
	}
2628

2629
	hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2630
		struct fib_alias *fa;
A
Al Viro 已提交
2631
		__be32 mask, prefix;
O
Olof Johansson 已提交
2632

2633 2634
		mask = inet_make_mask(li->plen);
		prefix = htonl(l->key);
2635

2636
		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2637
			const struct fib_info *fi = fa->fa_info;
2638
			unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2639
			int len;
2640

2641 2642 2643
			if (fa->fa_type == RTN_BROADCAST
			    || fa->fa_type == RTN_MULTICAST)
				continue;
2644

2645
			if (fi)
2646 2647 2648
				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",
2649 2650 2651 2652 2653
					 fi->fib_dev ? fi->fib_dev->name : "*",
					 prefix,
					 fi->fib_nh->nh_gw, flags, 0, 0,
					 fi->fib_priority,
					 mask,
2654 2655
					 (fi->fib_advmss ?
					  fi->fib_advmss + 40 : 0),
2656
					 fi->fib_window,
2657
					 fi->fib_rtt >> 3, &len);
2658
			else
2659 2660 2661
				seq_printf(seq,
					 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
					 "%d\t%08X\t%d\t%u\t%u%n",
2662
					 prefix, 0, flags, 0, 0, 0,
2663
					 mask, 0, 0, 0, &len);
2664

2665
			seq_printf(seq, "%*s\n", 127 - len, "");
2666
		}
2667 2668 2669 2670 2671
	}

	return 0;
}

2672
static const struct seq_operations fib_route_seq_ops = {
2673 2674 2675
	.start  = fib_route_seq_start,
	.next   = fib_route_seq_next,
	.stop   = fib_route_seq_stop,
2676
	.show   = fib_route_seq_show,
2677 2678
};

2679
static int fib_route_seq_open(struct inode *inode, struct file *file)
2680
{
2681
	return seq_open_net(inode, file, &fib_route_seq_ops,
2682
			    sizeof(struct fib_route_iter));
2683 2684
}

2685
static const struct file_operations fib_route_fops = {
2686 2687 2688 2689
	.owner  = THIS_MODULE,
	.open   = fib_route_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2690
	.release = seq_release_net,
2691 2692
};

2693
int __net_init fib_proc_init(struct net *net)
2694
{
2695
	if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
2696 2697
		goto out1;

2698 2699
	if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
				  &fib_triestat_fops))
2700 2701
		goto out2;

2702
	if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
2703 2704
		goto out3;

2705
	return 0;
2706 2707

out3:
2708
	proc_net_remove(net, "fib_triestat");
2709
out2:
2710
	proc_net_remove(net, "fib_trie");
2711 2712
out1:
	return -ENOMEM;
2713 2714
}

2715
void __net_exit fib_proc_exit(struct net *net)
2716
{
2717 2718 2719
	proc_net_remove(net, "fib_trie");
	proc_net_remove(net, "fib_triestat");
	proc_net_remove(net, "route");
2720 2721 2722
}

#endif /* CONFIG_PROC_FS */