fib_trie.c 59.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 42 43
 * 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
 *
 * Version:	$Id: fib_trie.c,v 1.3 2005/06/08 14:20:01 robert Exp $
 *
 *
 * 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 已提交
44 45 46 47 48 49 50
 *
 * 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>
51 52
 */

R
Robert Olsson 已提交
53
#define VERSION "0.408"
54 55 56

#include <asm/uaccess.h>
#include <asm/system.h>
J
Jiri Slaby 已提交
57
#include <linux/bitops.h>
58 59 60 61 62 63 64 65 66
#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 已提交
67
#include <linux/inetdevice.h>
68 69 70
#include <linux/netdevice.h>
#include <linux/if_arp.h>
#include <linux/proc_fs.h>
R
Robert Olsson 已提交
71
#include <linux/rcupdate.h>
72 73 74 75
#include <linux/skbuff.h>
#include <linux/netlink.h>
#include <linux/init.h>
#include <linux/list.h>
76
#include <net/net_namespace.h>
77 78 79 80 81 82 83 84
#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 已提交
85
#define MAX_STAT_DEPTH 32
86 87 88 89 90 91 92 93

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

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

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

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

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

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

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

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

struct trie {
O
Olof Johansson 已提交
151
	struct node *trie;
152 153 154 155 156 157
#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);
158 159
static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
				  int wasfull);
160
static struct node *resize(struct trie *t, struct tnode *tn);
161 162
static struct tnode *inflate(struct trie *t, struct tnode *tn);
static struct tnode *halve(struct trie *t, struct tnode *tn);
163 164
static void tnode_free(struct tnode *tn);

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 180 181 182 183 184

	return rcu_dereference(ret);
}

static inline void node_set_parent(struct node *node, struct tnode *ptr)
{
	rcu_assign_pointer(node->parent,
			   (unsigned long)ptr | NODE_TYPE(node));
}
R
Robert Olsson 已提交
185

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

190 191 192 193
	return tn->child[i];
}

static inline struct node *tnode_get_child_rcu(struct tnode *tn, unsigned int i)
194
{
195
	struct node *ret = tnode_get_child(tn, i);
196

197
	return rcu_dereference(ret);
198 199
}

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

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

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

static inline int tkey_equals(t_key a, t_key b)
{
220
	return a == b;
221 222 223 224
}

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

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

236 237 238
	if (!diff)
		return 0;
	while ((diff << i) >> (KEYLENGTH-1) == 0)
239 240 241 242 243
		i++;
	return i;
}

/*
244 245
  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
246 247 248 249
  all of the bits in that key are significant.

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

250 251 252 253 254
  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
255 256
  correct key path.

257 258 259 260 261
  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
262 263
  call to tkey_sub_equals() in trie_insert().

264
  if n is an internal node - a 'tnode' here, the various parts of its key
265 266
  have many different meanings.

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

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

283 284
  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
285 286 287
  not use them for anything.

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

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

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

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

300

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

*/

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

311 312 313 314
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;
315

R
Robert Olsson 已提交
316 317

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

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

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

R
Robert Olsson 已提交
334
static void __leaf_info_free_rcu(struct rcu_head *head)
335
{
R
Robert Olsson 已提交
336
	kfree(container_of(head, struct leaf_info, rcu));
337 338
}

R
Robert Olsson 已提交
339
static inline void free_leaf_info(struct leaf_info *leaf)
340
{
R
Robert Olsson 已提交
341
	call_rcu(&leaf->rcu, __leaf_info_free_rcu);
342 343
}

344
static struct tnode *tnode_alloc(size_t size)
345
{
R
Robert Olsson 已提交
346 347 348
	struct page *pages;

	if (size <= PAGE_SIZE)
349
		return kzalloc(size, GFP_KERNEL);
R
Robert Olsson 已提交
350 351 352 353 354 355

	pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size));
	if (!pages)
		return NULL;

	return page_address(pages);
356 357
}

R
Robert Olsson 已提交
358
static void __tnode_free_rcu(struct rcu_head *head)
359
{
R
Robert Olsson 已提交
360
	struct tnode *tn = container_of(head, struct tnode, rcu);
361 362
	size_t size = sizeof(struct tnode) +
		      (sizeof(struct node *) << tn->bits);
363 364 365 366 367 368 369

	if (size <= PAGE_SIZE)
		kfree(tn);
	else
		free_pages((unsigned long)tn, get_order(size));
}

R
Robert Olsson 已提交
370 371
static inline void tnode_free(struct tnode *tn)
{
S
Stephen Hemminger 已提交
372
	if (IS_LEAF(tn)) {
R
Robert Olsson 已提交
373 374
		struct leaf *l = (struct leaf *) tn;
		call_rcu_bh(&l->rcu, __leaf_free_rcu);
S
Stephen Hemminger 已提交
375
	} else
R
Robert Olsson 已提交
376
		call_rcu(&tn->rcu, __tnode_free_rcu);
R
Robert Olsson 已提交
377 378 379 380
}

static struct leaf *leaf_new(void)
{
381
	struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
R
Robert Olsson 已提交
382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398
	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;
}

399
static struct tnode *tnode_new(t_key key, int pos, int bits)
400
{
401
	size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits);
402
	struct tnode *tn = tnode_alloc(sz);
403

O
Olof Johansson 已提交
404
	if (tn) {
R
Robert Olsson 已提交
405
		tn->parent = T_TNODE;
406 407 408 409 410 411
		tn->pos = pos;
		tn->bits = bits;
		tn->key = key;
		tn->full_children = 0;
		tn->empty_children = 1<<bits;
	}
412

413 414
	pr_debug("AT %p s=%u %lu\n", tn, (unsigned int) sizeof(struct tnode),
		 (unsigned long) (sizeof(struct node) << bits));
415 416 417 418 419 420 421 422
	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 已提交
423
static inline int tnode_full(const struct tnode *tn, const struct node *n)
424
{
425
	if (n == NULL || IS_LEAF(n))
426 427 428 429 430
		return 0;

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

431 432
static inline void put_child(struct trie *t, struct tnode *tn, int i,
			     struct node *n)
433 434 435 436
{
	tnode_put_child_reorg(tn, i, n, -1);
}

437
 /*
438 439 440 441
  * Add a child at position i overwriting the old value.
  * Update the value of full_children and empty_children.
  */

442 443
static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
				  int wasfull)
444
{
R
Robert Olsson 已提交
445
	struct node *chi = tn->child[i];
446 447
	int isfull;

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

450 451 452 453 454 455

	/* update emptyChildren */
	if (n == NULL && chi != NULL)
		tn->empty_children++;
	else if (n != NULL && chi == NULL)
		tn->empty_children--;
456

457
	/* update fullChildren */
O
Olof Johansson 已提交
458
	if (wasfull == -1)
459 460 461
		wasfull = tnode_full(tn, chi);

	isfull = tnode_full(tn, n);
462
	if (wasfull && !isfull)
463
		tn->full_children--;
464
	else if (!wasfull && isfull)
465
		tn->full_children++;
O
Olof Johansson 已提交
466

467
	if (n)
S
Stephen Hemminger 已提交
468
		node_set_parent(n, tn);
469

R
Robert Olsson 已提交
470
	rcu_assign_pointer(tn->child[i], n);
471 472
}

473
static struct node *resize(struct trie *t, struct tnode *tn)
474 475
{
	int i;
476
	int err = 0;
477
	struct tnode *old_tn;
478 479
	int inflate_threshold_use;
	int halve_threshold_use;
R
Robert Olsson 已提交
480
	int max_resize;
481

482
	if (!tn)
483 484
		return NULL;

S
Stephen Hemminger 已提交
485 486
	pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
		 tn, inflate_threshold, halve_threshold);
487 488 489 490 491 492 493 494 495

	/* 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 已提交
496
			struct node *n;
497

O
Olof Johansson 已提交
498
			n = tn->child[i];
R
Robert Olsson 已提交
499
			if (!n)
O
Olof Johansson 已提交
500 501 502
				continue;

			/* compress one level */
S
Stephen Hemminger 已提交
503
			node_set_parent(n, NULL);
O
Olof Johansson 已提交
504 505
			tnode_free(tn);
			return n;
506
		}
507
	/*
508 509 510 511 512
	 * Double as long as the resulting node has a number of
	 * nonempty nodes that are above the threshold.
	 */

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

	check_tnode(tn);
572

573 574
	/* Keep root node larger  */

S
Stephen Hemminger 已提交
575
	if (!tn->parent)
576
		inflate_threshold_use = inflate_threshold_root;
577
	else
578 579
		inflate_threshold_use = inflate_threshold;

580
	err = 0;
R
Robert Olsson 已提交
581 582
	max_resize = 10;
	while ((tn->full_children > 0 &&  max_resize-- &&
583 584 585
		50 * (tn->full_children + tnode_child_length(tn)
		      - tn->empty_children)
		>= inflate_threshold_use * tnode_child_length(tn))) {
586

587 588
		old_tn = tn;
		tn = inflate(t, tn);
589

590 591
		if (IS_ERR(tn)) {
			tn = old_tn;
592 593 594 595 596
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.resize_node_skipped++;
#endif
			break;
		}
597 598
	}

R
Robert Olsson 已提交
599 600
	if (max_resize < 0) {
		if (!tn->parent)
601 602 603
			pr_warning("Fix inflate_threshold_root."
				   " Now=%d size=%d bits\n",
				   inflate_threshold_root, tn->bits);
R
Robert Olsson 已提交
604
		else
605 606 607
			pr_warning("Fix inflate_threshold."
				   " Now=%d size=%d bits\n",
				   inflate_threshold, tn->bits);
R
Robert Olsson 已提交
608 609
	}

610 611 612 613 614 615
	check_tnode(tn);

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

617 618 619

	/* Keep root node larger  */

S
Stephen Hemminger 已提交
620
	if (!tn->parent)
621
		halve_threshold_use = halve_threshold_root;
622
	else
623 624
		halve_threshold_use = halve_threshold;

625
	err = 0;
R
Robert Olsson 已提交
626 627
	max_resize = 10;
	while (tn->bits > 1 &&  max_resize-- &&
628
	       100 * (tnode_child_length(tn) - tn->empty_children) <
629
	       halve_threshold_use * tnode_child_length(tn)) {
630

631 632 633 634
		old_tn = tn;
		tn = halve(t, tn);
		if (IS_ERR(tn)) {
			tn = old_tn;
635 636 637 638 639 640
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.resize_node_skipped++;
#endif
			break;
		}
	}
641

R
Robert Olsson 已提交
642 643
	if (max_resize < 0) {
		if (!tn->parent)
644 645 646
			pr_warning("Fix halve_threshold_root."
				   " Now=%d size=%d bits\n",
				   halve_threshold_root, tn->bits);
R
Robert Olsson 已提交
647
		else
648 649 650
			pr_warning("Fix halve_threshold."
				   " Now=%d size=%d bits\n",
				   halve_threshold, tn->bits);
R
Robert Olsson 已提交
651
	}
652

653 654 655
	/* 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 已提交
656
			struct node *n;
657

O
Olof Johansson 已提交
658
			n = tn->child[i];
R
Robert Olsson 已提交
659
			if (!n)
O
Olof Johansson 已提交
660 661 662 663
				continue;

			/* compress one level */

S
Stephen Hemminger 已提交
664
			node_set_parent(n, NULL);
O
Olof Johansson 已提交
665 666
			tnode_free(tn);
			return n;
667 668 669 670 671
		}

	return (struct node *) tn;
}

672
static struct tnode *inflate(struct trie *t, struct tnode *tn)
673 674 675 676 677
{
	struct tnode *oldtnode = tn;
	int olen = tnode_child_length(tn);
	int i;

S
Stephen Hemminger 已提交
678
	pr_debug("In inflate\n");
679 680 681

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

S
Stephen Hemminger 已提交
682
	if (!tn)
683
		return ERR_PTR(-ENOMEM);
684 685

	/*
686 687 688
	 * 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
689 690
	 * of tnode is ignored.
	 */
O
Olof Johansson 已提交
691 692

	for (i = 0; i < olen; i++) {
693
		struct tnode *inode;
694

695
		inode = (struct tnode *) tnode_get_child(oldtnode, i);
696 697 698 699 700
		if (inode &&
		    IS_TNODE(inode) &&
		    inode->pos == oldtnode->pos + oldtnode->bits &&
		    inode->bits > 1) {
			struct tnode *left, *right;
S
Stephen Hemminger 已提交
701
			t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
702

703 704
			left = tnode_new(inode->key&(~m), inode->pos + 1,
					 inode->bits - 1);
705 706
			if (!left)
				goto nomem;
O
Olof Johansson 已提交
707

708 709 710
			right = tnode_new(inode->key|m, inode->pos + 1,
					  inode->bits - 1);

711
			if (!right) {
712 713
				tnode_free(left);
				goto nomem;
714
			}
715 716 717 718 719 720

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

O
Olof Johansson 已提交
721
	for (i = 0; i < olen; i++) {
722
		struct tnode *inode;
723
		struct node *node = tnode_get_child(oldtnode, i);
O
Olof Johansson 已提交
724 725
		struct tnode *left, *right;
		int size, j;
726

727 728 729 730 731 732
		/* An empty child */
		if (node == NULL)
			continue;

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

733
		if (IS_LEAF(node) || ((struct tnode *) node)->pos >
734
		   tn->pos + tn->bits - 1) {
735 736 737
			if (tkey_extract_bits(node->key,
					      oldtnode->pos + oldtnode->bits,
					      1) == 0)
738 739 740 741 742 743 744 745 746 747 748 749 750 751
				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 已提交
752
			continue;
753 754
		}

O
Olof Johansson 已提交
755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772
		/* 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)
		 */
773

O
Olof Johansson 已提交
774 775 776
		/* Use the old key, but set the new significant
		 *   bit to zero.
		 */
777

O
Olof Johansson 已提交
778 779
		left = (struct tnode *) tnode_get_child(tn, 2*i);
		put_child(t, tn, 2*i, NULL);
780

O
Olof Johansson 已提交
781
		BUG_ON(!left);
782

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

O
Olof Johansson 已提交
786
		BUG_ON(!right);
787

O
Olof Johansson 已提交
788 789 790 791
		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]);
792
		}
O
Olof Johansson 已提交
793 794 795 796
		put_child(t, tn, 2*i, resize(t, left));
		put_child(t, tn, 2*i+1, resize(t, right));

		tnode_free(inode);
797 798 799
	}
	tnode_free(oldtnode);
	return tn;
800 801 802 803 804
nomem:
	{
		int size = tnode_child_length(tn);
		int j;

S
Stephen Hemminger 已提交
805
		for (j = 0; j < size; j++)
806 807 808 809
			if (tn->child[j])
				tnode_free((struct tnode *)tn->child[j]);

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

811 812
		return ERR_PTR(-ENOMEM);
	}
813 814
}

815
static struct tnode *halve(struct trie *t, struct tnode *tn)
816 817 818 819 820 821
{
	struct tnode *oldtnode = tn;
	struct node *left, *right;
	int i;
	int olen = tnode_child_length(tn);

S
Stephen Hemminger 已提交
822
	pr_debug("In halve\n");
823 824

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

826 827
	if (!tn)
		return ERR_PTR(-ENOMEM);
828 829

	/*
830 831 832
	 * 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
833 834 835
	 * of tnode is ignored.
	 */

O
Olof Johansson 已提交
836
	for (i = 0; i < olen; i += 2) {
837 838
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
839

840
		/* Two nonempty children */
S
Stephen Hemminger 已提交
841
		if (left && right) {
842
			struct tnode *newn;
S
Stephen Hemminger 已提交
843

844
			newn = tnode_new(left->key, tn->pos + tn->bits, 1);
S
Stephen Hemminger 已提交
845 846

			if (!newn)
847
				goto nomem;
S
Stephen Hemminger 已提交
848

849
			put_child(t, tn, i/2, (struct node *)newn);
850 851 852
		}

	}
853

O
Olof Johansson 已提交
854 855 856
	for (i = 0; i < olen; i += 2) {
		struct tnode *newBinNode;

857 858
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
859

860 861 862 863 864
		/* 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 已提交
865
			continue;
S
Stephen Hemminger 已提交
866
		}
O
Olof Johansson 已提交
867 868

		if (right == NULL) {
869
			put_child(t, tn, i/2, left);
O
Olof Johansson 已提交
870 871
			continue;
		}
872

873
		/* Two nonempty children */
O
Olof Johansson 已提交
874 875 876 877 878
		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));
879 880 881
	}
	tnode_free(oldtnode);
	return tn;
882 883 884 885 886
nomem:
	{
		int size = tnode_child_length(tn);
		int j;

S
Stephen Hemminger 已提交
887
		for (j = 0; j < size; j++)
888 889 890 891
			if (tn->child[j])
				tnode_free((struct tnode *)tn->child[j]);

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

893 894
		return ERR_PTR(-ENOMEM);
	}
895 896
}

R
Robert Olsson 已提交
897
/* readside must use rcu_read_lock currently dump routines
R
Robert Olsson 已提交
898 899
 via get_fa_head and dump */

R
Robert Olsson 已提交
900
static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
901
{
R
Robert Olsson 已提交
902
	struct hlist_head *head = &l->list;
903 904 905
	struct hlist_node *node;
	struct leaf_info *li;

R
Robert Olsson 已提交
906
	hlist_for_each_entry_rcu(li, node, head, hlist)
907
		if (li->plen == plen)
908
			return li;
O
Olof Johansson 已提交
909

910 911 912
	return NULL;
}

913
static inline struct list_head *get_fa_head(struct leaf *l, int plen)
914
{
R
Robert Olsson 已提交
915
	struct leaf_info *li = find_leaf_info(l, plen);
916

O
Olof Johansson 已提交
917 918
	if (!li)
		return NULL;
919

O
Olof Johansson 已提交
920
	return &li->falh;
921 922 923 924
}

static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
{
925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941
	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);
	}
942 943
}

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

946 947 948 949 950 951 952 953
static struct leaf *
fib_find_node(struct trie *t, u32 key)
{
	int pos;
	struct tnode *tn;
	struct node *n;

	pos = 0;
R
Robert Olsson 已提交
954
	n = rcu_dereference(t->trie);
955 956 957

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

959
		check_tnode(tn);
O
Olof Johansson 已提交
960

961
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
O
Olof Johansson 已提交
962
			pos = tn->pos + tn->bits;
963 964 965 966
			n = tnode_get_child_rcu(tn,
						tkey_extract_bits(key,
								  tn->pos,
								  tn->bits));
O
Olof Johansson 已提交
967
		} else
968 969 970 971
			break;
	}
	/* Case we have found a leaf. Compare prefixes */

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

975 976 977 978 979 980
	return NULL;
}

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

S
Stephen Hemminger 已提交
984
	while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) {
985 986
		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
		wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
987 988 989 990
		tn = (struct tnode *) resize(t, (struct tnode *)tn);

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

S
Stephen Hemminger 已提交
992 993
		tp = node_parent((struct node *) tn);
		if (!tp)
994
			break;
S
Stephen Hemminger 已提交
995
		tn = tp;
996
	}
S
Stephen Hemminger 已提交
997

998
	/* Handle last (top) tnode */
999
	if (IS_TNODE(tn))
1000
		tn = (struct tnode *)resize(t, (struct tnode *)tn);
1001

1002
	return (struct node *)tn;
1003 1004
}

R
Robert Olsson 已提交
1005 1006
/* only used from updater-side */

1007
static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
1008 1009 1010 1011 1012 1013
{
	int pos, newpos;
	struct tnode *tp = NULL, *tn = NULL;
	struct node *n;
	struct leaf *l;
	int missbit;
1014
	struct list_head *fa_head = NULL;
1015 1016 1017 1018
	struct leaf_info *li;
	t_key cindex;

	pos = 0;
1019
	n = t->trie;
1020

1021 1022
	/* 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,
1023
	 * and we should just put our new leaf in that.
1024 1025
	 * 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
1026 1027
	 * not be the parent's 'pos'+'bits'!
	 *
1028
	 * If it does match the current key, get pos/bits from it, extract
1029 1030 1031 1032
	 * 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.
	 *
1033 1034 1035
	 * 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.
1036 1037 1038 1039 1040
	 * 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 已提交
1041

1042
		check_tnode(tn);
O
Olof Johansson 已提交
1043

1044
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1045
			tp = tn;
O
Olof Johansson 已提交
1046
			pos = tn->pos + tn->bits;
1047 1048 1049 1050
			n = tnode_get_child(tn,
					    tkey_extract_bits(key,
							      tn->pos,
							      tn->bits));
1051

S
Stephen Hemminger 已提交
1052
			BUG_ON(n && node_parent(n) != tn);
O
Olof Johansson 已提交
1053
		} else
1054 1055 1056 1057 1058 1059
			break;
	}

	/*
	 * n  ----> NULL, LEAF or TNODE
	 *
1060
	 * tp is n's (parent) ----> NULL or TNODE
1061 1062
	 */

O
Olof Johansson 已提交
1063
	BUG_ON(tp && IS_LEAF(tp));
1064 1065 1066

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

1067
	if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1068
		l = (struct leaf *) n;
1069
		li = leaf_info_new(plen);
O
Olof Johansson 已提交
1070

1071 1072
		if (!li)
			return NULL;
1073 1074 1075 1076 1077 1078 1079

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

1080 1081
	if (!l)
		return NULL;
1082 1083 1084 1085

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

1086
	if (!li) {
1087
		tnode_free((struct tnode *) l);
1088
		return NULL;
1089
	}
1090 1091 1092 1093 1094

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

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

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

O
Olof Johansson 已提交
1099 1100 1101 1102
		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. */
1103 1104
		/*
		 *  Add a new tnode here
1105 1106 1107 1108
		 *  first tnode need some special handling
		 */

		if (tp)
O
Olof Johansson 已提交
1109
			pos = tp->pos+tp->bits;
1110
		else
O
Olof Johansson 已提交
1111 1112
			pos = 0;

1113
		if (n) {
1114 1115
			newpos = tkey_mismatch(key, pos, n->key);
			tn = tnode_new(n->key, newpos, 1);
O
Olof Johansson 已提交
1116
		} else {
1117
			newpos = 0;
1118
			tn = tnode_new(key, newpos, 1); /* First tnode */
1119 1120
		}

1121
		if (!tn) {
1122 1123
			free_leaf_info(li);
			tnode_free((struct tnode *) l);
1124
			return NULL;
O
Olof Johansson 已提交
1125 1126
		}

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

O
Olof Johansson 已提交
1129
		missbit = tkey_extract_bits(key, newpos, 1);
1130 1131 1132
		put_child(t, tn, missbit, (struct node *)l);
		put_child(t, tn, 1-missbit, n);

1133
		if (tp) {
1134
			cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1135 1136
			put_child(t, (struct tnode *)tp, cindex,
				  (struct node *)tn);
O
Olof Johansson 已提交
1137
		} else {
1138
			rcu_assign_pointer(t->trie, (struct node *)tn);
1139 1140 1141
			tp = tn;
		}
	}
O
Olof Johansson 已提交
1142 1143

	if (tp && tp->pos + tp->bits > 32)
1144 1145 1146
		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 已提交
1147

1148
	/* Rebalance the trie */
R
Robert Olsson 已提交
1149 1150

	rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
1151
done:
1152 1153 1154
	return fa_head;
}

1155 1156 1157
/*
 * Caller must hold RTNL.
 */
1158
static int fn_trie_insert(struct fib_table *tb, struct fib_config *cfg)
1159 1160 1161
{
	struct trie *t = (struct trie *) tb->tb_data;
	struct fib_alias *fa, *new_fa;
1162
	struct list_head *fa_head = NULL;
1163
	struct fib_info *fi;
1164 1165
	int plen = cfg->fc_dst_len;
	u8 tos = cfg->fc_tos;
1166 1167 1168 1169 1170 1171 1172
	u32 key, mask;
	int err;
	struct leaf *l;

	if (plen > 32)
		return -EINVAL;

1173
	key = ntohl(cfg->fc_dst);
1174

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

O
Olof Johansson 已提交
1177
	mask = ntohl(inet_make_mask(plen));
1178

1179
	if (key & ~mask)
1180 1181 1182 1183
		return -EINVAL;

	key = key & mask;

1184 1185 1186
	fi = fib_create_info(cfg);
	if (IS_ERR(fi)) {
		err = PTR_ERR(fi);
1187
		goto err;
1188
	}
1189 1190

	l = fib_find_node(t, key);
1191
	fa = NULL;
1192

1193
	if (l) {
1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208
		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.
	 */

O
Olof Johansson 已提交
1209
	if (fa && fa->fa_info->fib_priority == fi->fib_priority) {
1210 1211 1212
		struct fib_alias *fa_orig;

		err = -EEXIST;
1213
		if (cfg->fc_nlflags & NLM_F_EXCL)
1214 1215
			goto out;

1216
		if (cfg->fc_nlflags & NLM_F_REPLACE) {
1217 1218 1219
			struct fib_info *fi_drop;
			u8 state;

1220 1221 1222
			if (fi->fib_treeref > 1)
				goto out;

R
Robert Olsson 已提交
1223
			err = -ENOBUFS;
1224
			new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
R
Robert Olsson 已提交
1225 1226
			if (new_fa == NULL)
				goto out;
1227 1228

			fi_drop = fa->fa_info;
R
Robert Olsson 已提交
1229 1230
			new_fa->fa_tos = fa->fa_tos;
			new_fa->fa_info = fi;
1231 1232
			new_fa->fa_type = cfg->fc_type;
			new_fa->fa_scope = cfg->fc_scope;
1233
			state = fa->fa_state;
R
Robert Olsson 已提交
1234
			new_fa->fa_state &= ~FA_S_ACCESSED;
1235

R
Robert Olsson 已提交
1236 1237
			list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
			alias_free_mem_rcu(fa);
1238 1239 1240

			fib_release_info(fi_drop);
			if (state & FA_S_ACCESSED)
O
Olof Johansson 已提交
1241
				rt_cache_flush(-1);
1242 1243
			rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
				tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1244

O
Olof Johansson 已提交
1245
			goto succeeded;
1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256
		}
		/* Error if we find a perfect match which
		 * uses the same scope, type, and nexthop
		 * information.
		 */
		fa_orig = fa;
		list_for_each_entry(fa, fa_orig->fa_list.prev, fa_list) {
			if (fa->fa_tos != tos)
				break;
			if (fa->fa_info->fib_priority != fi->fib_priority)
				break;
1257 1258
			if (fa->fa_type == cfg->fc_type &&
			    fa->fa_scope == cfg->fc_scope &&
1259
			    fa->fa_info == fi)
1260 1261
				goto out;
		}
1262

1263
		if (!(cfg->fc_nlflags & NLM_F_APPEND))
1264 1265 1266
			fa = fa_orig;
	}
	err = -ENOENT;
1267
	if (!(cfg->fc_nlflags & NLM_F_CREATE))
1268 1269 1270
		goto out;

	err = -ENOBUFS;
1271
	new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1272 1273 1274 1275 1276
	if (new_fa == NULL)
		goto out;

	new_fa->fa_info = fi;
	new_fa->fa_tos = tos;
1277 1278
	new_fa->fa_type = cfg->fc_type;
	new_fa->fa_scope = cfg->fc_scope;
1279 1280 1281 1282 1283
	new_fa->fa_state = 0;
	/*
	 * Insert new entry to the list.
	 */

1284
	if (!fa_head) {
1285 1286 1287
		fa_head = fib_insert_node(t, key, plen);
		if (unlikely(!fa_head)) {
			err = -ENOMEM;
1288
			goto out_free_new_fa;
1289
		}
1290
	}
1291

R
Robert Olsson 已提交
1292 1293
	list_add_tail_rcu(&new_fa->fa_list,
			  (fa ? &fa->fa_list : fa_head));
1294 1295

	rt_cache_flush(-1);
1296
	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1297
		  &cfg->fc_nlinfo, 0);
1298 1299
succeeded:
	return 0;
1300 1301 1302

out_free_new_fa:
	kmem_cache_free(fn_alias_kmem, new_fa);
1303 1304
out:
	fib_release_info(fi);
O
Olof Johansson 已提交
1305
err:
1306 1307 1308
	return err;
}

R
Robert Olsson 已提交
1309

R
Robert Olsson 已提交
1310
/* should be called with rcu_read_lock */
1311 1312 1313
static int check_leaf(struct trie *t, struct leaf *l,
		      t_key key,  const struct flowi *flp,
		      struct fib_result *res)
1314 1315 1316 1317
{
	struct leaf_info *li;
	struct hlist_head *hhead = &l->list;
	struct hlist_node *node;
1318

R
Robert Olsson 已提交
1319
	hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1320 1321 1322 1323
		int err;
		int plen = li->plen;
		__be32 mask = inet_make_mask(plen);

1324
		if (l->key != (key & ntohl(mask)))
1325 1326
			continue;

1327 1328 1329
		err = fib_semantic_match(&li->falh, flp, res,
					 htonl(l->key), mask, plen);

1330
#ifdef CONFIG_IP_FIB_TRIE_STATS
1331
		if (err <= 0)
1332
			t->stats.semantic_match_passed++;
1333 1334
		else
			t->stats.semantic_match_miss++;
1335
#endif
1336 1337
		if (err <= 0)
			return plen;
1338
	}
1339 1340

	return -1;
1341 1342
}

1343 1344
static int fn_trie_lookup(struct fib_table *tb, const struct flowi *flp,
			  struct fib_result *res)
1345 1346 1347 1348 1349 1350
{
	struct trie *t = (struct trie *) tb->tb_data;
	int plen, ret = 0;
	struct node *n;
	struct tnode *pn;
	int pos, bits;
O
Olof Johansson 已提交
1351
	t_key key = ntohl(flp->fl4_dst);
1352 1353 1354
	int chopped_off;
	t_key cindex = 0;
	int current_prefix_length = KEYLENGTH;
O
Olof Johansson 已提交
1355 1356 1357 1358
	struct tnode *cn;
	t_key node_prefix, key_prefix, pref_mismatch;
	int mp;

R
Robert Olsson 已提交
1359
	rcu_read_lock();
O
Olof Johansson 已提交
1360

R
Robert Olsson 已提交
1361
	n = rcu_dereference(t->trie);
1362
	if (!n)
1363 1364 1365 1366 1367 1368 1369 1370
		goto failed;

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

	/* Just a leaf? */
	if (IS_LEAF(n)) {
1371 1372 1373 1374 1375
		plen = check_leaf(t, (struct leaf *)n, key, flp, res);
		if (plen < 0)
			goto failed;
		ret = 0;
		goto found;
1376
	}
1377

1378 1379
	pn = (struct tnode *) n;
	chopped_off = 0;
1380

O
Olof Johansson 已提交
1381
	while (pn) {
1382 1383 1384
		pos = pn->pos;
		bits = pn->bits;

1385
		if (!chopped_off)
S
Stephen Hemminger 已提交
1386 1387
			cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
						   pos, bits);
1388 1389 1390 1391 1392 1393 1394 1395 1396 1397

		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 已提交
1398
		if (IS_LEAF(n)) {
1399 1400
			plen = check_leaf(t, (struct leaf *)n, key, flp, res);
			if (plen < 0)
O
Olof Johansson 已提交
1401
				goto backtrace;
1402 1403 1404

			ret = 0;
			goto found;
O
Olof Johansson 已提交
1405 1406 1407
		}

		cn = (struct tnode *)n;
1408

O
Olof Johansson 已提交
1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423
		/*
		 * 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].
		 */
1424

O
Olof Johansson 已提交
1425 1426 1427 1428 1429 1430 1431 1432 1433
		/* 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.
		 */
1434

1435 1436
		/* NOTA BENE: Checking only skipped bits
		   for the new node here */
1437

O
Olof Johansson 已提交
1438 1439
		if (current_prefix_length < pos+bits) {
			if (tkey_extract_bits(cn->key, current_prefix_length,
1440 1441
						cn->pos - current_prefix_length)
			    || !(cn->child[0]))
O
Olof Johansson 已提交
1442 1443
				goto backtrace;
		}
1444

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

O
Olof Johansson 已提交
1455 1456 1457 1458 1459 1460 1461 1462
		/* 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.
		 */
1463

1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474
		/*
		 * 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 已提交
1475 1476
		 */

S
Stephen Hemminger 已提交
1477 1478
		node_prefix = mask_pfx(cn->key, cn->pos);
		key_prefix = mask_pfx(key, cn->pos);
O
Olof Johansson 已提交
1479 1480 1481
		pref_mismatch = key_prefix^node_prefix;
		mp = 0;

1482 1483 1484 1485
		/*
		 * In short: If skipped bits in this node do not match
		 * the search key, enter the "prefix matching"
		 * state.directly.
O
Olof Johansson 已提交
1486 1487 1488 1489
		 */
		if (pref_mismatch) {
			while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
				mp++;
1490
				pref_mismatch = pref_mismatch << 1;
O
Olof Johansson 已提交
1491 1492 1493 1494 1495 1496 1497 1498
			}
			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;
1499
		}
1500

O
Olof Johansson 已提交
1501 1502 1503 1504
		pn = (struct tnode *)n; /* Descend */
		chopped_off = 0;
		continue;

1505 1506 1507 1508
backtrace:
		chopped_off++;

		/* As zero don't change the child key (cindex) */
1509 1510
		while ((chopped_off <= pn->bits)
		       && !(cindex & (1<<(chopped_off-1))))
1511 1512 1513 1514
			chopped_off++;

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

1518
		/*
1519
		 * Either we do the actual chop off according or if we have
1520 1521 1522
		 * chopped off all bits in this tnode walk up to our parent.
		 */

O
Olof Johansson 已提交
1523
		if (chopped_off <= pn->bits) {
1524
			cindex &= ~(1 << (chopped_off-1));
O
Olof Johansson 已提交
1525
		} else {
S
Stephen Hemminger 已提交
1526 1527
			struct tnode *parent = node_parent((struct node *) pn);
			if (!parent)
1528
				goto failed;
O
Olof Johansson 已提交
1529

1530
			/* Get Child's index */
S
Stephen Hemminger 已提交
1531 1532
			cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
			pn = parent;
1533 1534 1535 1536 1537 1538
			chopped_off = 0;

#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.backtrack++;
#endif
			goto backtrace;
1539
		}
1540 1541
	}
failed:
1542
	ret = 1;
1543
found:
R
Robert Olsson 已提交
1544
	rcu_read_unlock();
1545 1546 1547
	return ret;
}

R
Robert Olsson 已提交
1548
/* only called from updater side */
1549 1550 1551 1552 1553 1554 1555
static int trie_leaf_remove(struct trie *t, t_key key)
{
	t_key cindex;
	struct tnode *tp = NULL;
	struct node *n = t->trie;
	struct leaf *l;

S
Stephen Hemminger 已提交
1556
	pr_debug("entering trie_leaf_remove(%p)\n", n);
1557 1558

	/* Note that in the case skipped bits, those bits are *not* checked!
1559
	 * When we finish this, we will have NULL or a T_LEAF, and the
1560 1561 1562
	 * T_LEAF may or may not match our key.
	 */

O
Olof Johansson 已提交
1563
	while (n != NULL && IS_TNODE(n)) {
1564 1565
		struct tnode *tn = (struct tnode *) n;
		check_tnode(tn);
1566 1567
		n = tnode_get_child(tn, tkey_extract_bits(key,
							  tn->pos, tn->bits));
1568

S
Stephen Hemminger 已提交
1569
		BUG_ON(n && node_parent(n) != tn);
O
Olof Johansson 已提交
1570
	}
1571 1572
	l = (struct leaf *) n;

1573
	if (!n || !tkey_equals(l->key, key))
1574
		return 0;
1575 1576 1577 1578

	/*
	 * Key found.
	 * Remove the leaf and rebalance the tree
1579
	 */
S
Stephen Hemminger 已提交
1580
	tp = node_parent(n);
1581 1582
	tnode_free((struct tnode *) n);

1583
	if (tp) {
1584 1585
		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
		put_child(t, (struct tnode *)tp, cindex, NULL);
R
Robert Olsson 已提交
1586
		rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
O
Olof Johansson 已提交
1587
	} else
R
Robert Olsson 已提交
1588
		rcu_assign_pointer(t->trie, NULL);
1589 1590 1591 1592

	return 1;
}

1593 1594 1595
/*
 * Caller must hold RTNL.
 */
1596
static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
1597 1598 1599
{
	struct trie *t = (struct trie *) tb->tb_data;
	u32 key, mask;
1600 1601
	int plen = cfg->fc_dst_len;
	u8 tos = cfg->fc_tos;
1602 1603 1604
	struct fib_alias *fa, *fa_to_delete;
	struct list_head *fa_head;
	struct leaf *l;
O
Olof Johansson 已提交
1605 1606
	struct leaf_info *li;

1607
	if (plen > 32)
1608 1609
		return -EINVAL;

1610
	key = ntohl(cfg->fc_dst);
O
Olof Johansson 已提交
1611
	mask = ntohl(inet_make_mask(plen));
1612

1613
	if (key & ~mask)
1614 1615 1616 1617 1618
		return -EINVAL;

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

1619
	if (!l)
1620 1621 1622 1623 1624 1625 1626 1627
		return -ESRCH;

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

	if (!fa)
		return -ESRCH;

S
Stephen Hemminger 已提交
1628
	pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1629 1630 1631

	fa_to_delete = NULL;
	fa_head = fa->fa_list.prev;
R
Robert Olsson 已提交
1632

1633 1634 1635 1636 1637 1638
	list_for_each_entry(fa, fa_head, fa_list) {
		struct fib_info *fi = fa->fa_info;

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

1639 1640 1641 1642 1643 1644
		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) {
1645 1646 1647 1648 1649
			fa_to_delete = fa;
			break;
		}
	}

O
Olof Johansson 已提交
1650 1651
	if (!fa_to_delete)
		return -ESRCH;
1652

O
Olof Johansson 已提交
1653
	fa = fa_to_delete;
1654
	rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1655
		  &cfg->fc_nlinfo, 0);
O
Olof Johansson 已提交
1656 1657

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

R
Robert Olsson 已提交
1660
	list_del_rcu(&fa->fa_list);
1661

O
Olof Johansson 已提交
1662
	if (list_empty(fa_head)) {
R
Robert Olsson 已提交
1663
		hlist_del_rcu(&li->hlist);
O
Olof Johansson 已提交
1664
		free_leaf_info(li);
R
Robert Olsson 已提交
1665
	}
1666

O
Olof Johansson 已提交
1667 1668
	if (hlist_empty(&l->list))
		trie_leaf_remove(t, key);
1669

O
Olof Johansson 已提交
1670 1671
	if (fa->fa_state & FA_S_ACCESSED)
		rt_cache_flush(-1);
1672

R
Robert Olsson 已提交
1673 1674
	fib_release_info(fa->fa_info);
	alias_free_mem_rcu(fa);
O
Olof Johansson 已提交
1675
	return 0;
1676 1677 1678 1679 1680 1681 1682 1683 1684 1685
}

static int trie_flush_list(struct trie *t, struct list_head *head)
{
	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 已提交
1686 1687 1688 1689
		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);
1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706
			found++;
		}
	}
	return found;
}

static int trie_flush_leaf(struct trie *t, struct leaf *l)
{
	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) {
		found += trie_flush_list(t, &li->falh);

		if (list_empty(&li->falh)) {
R
Robert Olsson 已提交
1707
			hlist_del_rcu(&li->hlist);
1708 1709 1710 1711 1712 1713
			free_leaf_info(li);
		}
	}
	return found;
}

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

1716 1717 1718 1719 1720
static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
{
	struct node *c = (struct node *) thisleaf;
	struct tnode *p;
	int idx;
R
Robert Olsson 已提交
1721
	struct node *trie = rcu_dereference(t->trie);
1722

1723
	if (c == NULL) {
R
Robert Olsson 已提交
1724
		if (trie == NULL)
1725 1726
			return NULL;

R
Robert Olsson 已提交
1727 1728
		if (IS_LEAF(trie))          /* trie w. just a leaf */
			return (struct leaf *) trie;
1729

1730
		p = (struct tnode *)trie;  /* Start */
O
Olof Johansson 已提交
1731
	} else
1732
		p = node_parent_rcu(c);
1733

1734 1735 1736 1737
	while (p) {
		int pos, last;

		/*  Find the next child of the parent */
1738 1739 1740
		if (c)
			pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits);
		else
1741 1742 1743
			pos = 0;

		last = 1 << p->bits;
O
Olof Johansson 已提交
1744
		for (idx = pos; idx < last ; idx++) {
R
Robert Olsson 已提交
1745 1746 1747
			c = rcu_dereference(p->child[idx]);

			if (!c)
O
Olof Johansson 已提交
1748 1749 1750
				continue;

			/* Decend if tnode */
R
Robert Olsson 已提交
1751 1752
			while (IS_TNODE(c)) {
				p = (struct tnode *) c;
1753
				idx = 0;
O
Olof Johansson 已提交
1754 1755 1756

				/* Rightmost non-NULL branch */
				if (p && IS_TNODE(p))
R
Robert Olsson 已提交
1757 1758
					while (!(c = rcu_dereference(p->child[idx]))
					       && idx < (1<<p->bits)) idx++;
O
Olof Johansson 已提交
1759 1760

				/* Done with this tnode? */
R
Robert Olsson 已提交
1761
				if (idx >= (1 << p->bits) || !c)
O
Olof Johansson 已提交
1762
					goto up;
1763
			}
R
Robert Olsson 已提交
1764
			return (struct leaf *) c;
1765 1766 1767
		}
up:
		/* No more children go up one step  */
O
Olof Johansson 已提交
1768
		c = (struct node *) p;
1769
		p = node_parent_rcu(c);
1770 1771 1772 1773
	}
	return NULL; /* Ready. Root of trie */
}

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

O
Olof Johansson 已提交
1783
	for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1784 1785 1786 1787 1788 1789 1790 1791 1792 1793
		found += trie_flush_leaf(t, l);

		if (ll && hlist_empty(&ll->list))
			trie_leaf_remove(t, ll->key);
		ll = l;
	}

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

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

1798 1799 1800
static void fn_trie_select_default(struct fib_table *tb,
				   const struct flowi *flp,
				   struct fib_result *res)
1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813
{
	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 已提交
1814
	rcu_read_lock();
1815

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

	fa_head = get_fa_head(l, 0);
1821
	if (!fa_head)
1822 1823
		goto out;

1824
	if (list_empty(fa_head))
1825 1826
		goto out;

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

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

1834 1835 1836 1837 1838 1839
		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 已提交
1840

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

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

1871 1872
static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
			   struct fib_table *tb,
1873 1874 1875 1876 1877
			   struct sk_buff *skb, struct netlink_callback *cb)
{
	int i, s_i;
	struct fib_alias *fa;

A
Al Viro 已提交
1878
	__be32 xkey = htonl(key);
1879

1880
	s_i = cb->args[4];
1881 1882
	i = 0;

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

	list_for_each_entry_rcu(fa, fah, fa_list) {
1886 1887 1888 1889
		if (i < s_i) {
			i++;
			continue;
		}
S
Stephen Hemminger 已提交
1890
		BUG_ON(!fa->fa_info);
1891 1892 1893 1894 1895 1896 1897

		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, 0) < 0) {
1902
			cb->args[4] = i;
1903
			return -1;
O
Olof Johansson 已提交
1904
		}
1905 1906
		i++;
	}
1907
	cb->args[4] = i;
1908 1909 1910
	return skb->len;
}

1911 1912
static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb,
			     struct sk_buff *skb, struct netlink_callback *cb)
1913 1914 1915 1916 1917
{
	int h, s_h;
	struct list_head *fa_head;
	struct leaf *l = NULL;

1918
	s_h = cb->args[3];
1919

O
Olof Johansson 已提交
1920
	for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1921 1922 1923
		if (h < s_h)
			continue;
		if (h > s_h)
1924 1925
			memset(&cb->args[4], 0,
			       sizeof(cb->args) - 4*sizeof(cb->args[0]));
1926 1927

		fa_head = get_fa_head(l, plen);
O
Olof Johansson 已提交
1928

1929
		if (!fa_head)
1930 1931
			continue;

1932
		if (list_empty(fa_head))
1933 1934
			continue;

1935
		if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb) < 0) {
1936
			cb->args[3] = h;
1937 1938 1939
			return -1;
		}
	}
1940
	cb->args[3] = h;
1941 1942 1943
	return skb->len;
}

1944 1945
static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb,
			struct netlink_callback *cb)
1946 1947 1948 1949
{
	int m, s_m;
	struct trie *t = (struct trie *) tb->tb_data;

1950
	s_m = cb->args[2];
1951

R
Robert Olsson 已提交
1952
	rcu_read_lock();
O
Olof Johansson 已提交
1953
	for (m = 0; m <= 32; m++) {
1954 1955 1956
		if (m < s_m)
			continue;
		if (m > s_m)
1957 1958
			memset(&cb->args[3], 0,
				sizeof(cb->args) - 3*sizeof(cb->args[0]));
1959

1960
		if (fn_trie_dump_plen(t, 32-m, tb, skb, cb) < 0) {
1961
			cb->args[2] = m;
1962 1963 1964
			goto out;
		}
	}
R
Robert Olsson 已提交
1965
	rcu_read_unlock();
1966
	cb->args[2] = m;
1967
	return skb->len;
O
Olof Johansson 已提交
1968
out:
R
Robert Olsson 已提交
1969
	rcu_read_unlock();
1970 1971 1972
	return -1;
}

1973 1974
void __init fib_hash_init(void)
{
1975 1976
	fn_alias_kmem = kmem_cache_create("ip_fib_alias",
					  sizeof(struct fib_alias),
1977 1978 1979 1980 1981 1982
					  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);
1983
}
1984

1985 1986 1987

/* Fix more generic FIB names for init later */
struct fib_table *fib_hash_table(u32 id)
1988 1989 1990 1991 1992 1993 1994 1995 1996 1997
{
	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;
1998
	tb->tb_default = -1;
1999 2000 2001 2002 2003 2004 2005 2006
	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;
2007
	memset(t, 0, sizeof(*t));
2008 2009

	if (id == RT_TABLE_LOCAL)
2010
		pr_info("IPv4 FIB: Using LC-trie version %s\n", VERSION);
2011 2012 2013 2014

	return tb;
}

2015 2016 2017
#ifdef CONFIG_PROC_FS
/* Depth first Trie walk iterator */
struct fib_trie_iter {
2018
	struct seq_net_private p;
2019
	struct trie *trie_local, *trie_main;
2020 2021 2022 2023 2024
	struct tnode *tnode;
	struct trie *trie;
	unsigned index;
	unsigned depth;
};
2025

2026
static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
2027
{
2028 2029 2030
	struct tnode *tn = iter->tnode;
	unsigned cindex = iter->index;
	struct tnode *p;
2031

2032 2033 2034 2035
	/* A single entry routing table */
	if (!tn)
		return NULL;

2036 2037 2038 2039
	pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
		 iter->tnode, iter->index, iter->depth);
rescan:
	while (cindex < (1<<tn->bits)) {
2040
		struct node *n = tnode_get_child_rcu(tn, cindex);
2041

2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053
		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;
		}
2054

2055 2056
		++cindex;
	}
O
Olof Johansson 已提交
2057

2058
	/* Current node exhausted, pop back up */
2059
	p = node_parent_rcu((struct node *)tn);
2060 2061 2062 2063 2064
	if (p) {
		cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
		tn = p;
		--iter->depth;
		goto rescan;
2065
	}
2066 2067 2068

	/* got root? */
	return NULL;
2069 2070
}

2071 2072
static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
				       struct trie *t)
2073
{
2074 2075
	struct node *n ;

S
Stephen Hemminger 已提交
2076
	if (!t)
2077 2078 2079 2080
		return NULL;

	n = rcu_dereference(t->trie);

S
Stephen Hemminger 已提交
2081
	if (!iter)
2082
		return NULL;
2083

2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095
	if (n) {
		if (IS_TNODE(n)) {
			iter->tnode = (struct tnode *) n;
			iter->trie = t;
			iter->index = 0;
			iter->depth = 1;
		} else {
			iter->tnode = NULL;
			iter->trie  = t;
			iter->index = 0;
			iter->depth = 0;
		}
2096
		return n;
O
Olof Johansson 已提交
2097
	}
2098 2099
	return NULL;
}
O
Olof Johansson 已提交
2100

2101 2102 2103 2104
static void trie_collect_stats(struct trie *t, struct trie_stat *s)
{
	struct node *n;
	struct fib_trie_iter iter;
O
Olof Johansson 已提交
2105

2106
	memset(s, 0, sizeof(*s));
O
Olof Johansson 已提交
2107

2108 2109 2110 2111
	rcu_read_lock();
	for (n = fib_trie_get_first(&iter, t); n;
	     n = fib_trie_get_next(&iter)) {
		if (IS_LEAF(n)) {
2112 2113 2114 2115
			struct leaf *l = (struct leaf *)n;
			struct leaf_info *li;
			struct hlist_node *tmp;

2116 2117 2118 2119
			s->leaves++;
			s->totdepth += iter.depth;
			if (iter.depth > s->maxdepth)
				s->maxdepth = iter.depth;
2120 2121 2122

			hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
				++s->prefixes;
2123 2124 2125 2126 2127
		} else {
			const struct tnode *tn = (const struct tnode *) n;
			int i;

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

2131 2132 2133
			for (i = 0; i < (1<<tn->bits); i++)
				if (!tn->child[i])
					s->nullpointers++;
2134 2135
		}
	}
R
Robert Olsson 已提交
2136
	rcu_read_unlock();
2137 2138
}

2139 2140 2141 2142
/*
 *	This outputs /proc/net/fib_triestats
 */
static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2143
{
2144
	unsigned i, max, pointers, bytes, avdepth;
2145

2146 2147 2148 2149
	if (stat->leaves)
		avdepth = stat->totdepth*100 / stat->leaves;
	else
		avdepth = 0;
O
Olof Johansson 已提交
2150

2151 2152
	seq_printf(seq, "\tAver depth:     %u.%02d\n",
		   avdepth / 100, avdepth % 100);
2153
	seq_printf(seq, "\tMax depth:      %u\n", stat->maxdepth);
O
Olof Johansson 已提交
2154

2155 2156
	seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
	bytes = sizeof(struct leaf) * stat->leaves;
2157 2158 2159 2160

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

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

R
Robert Olsson 已提交
2164 2165
	max = MAX_STAT_DEPTH;
	while (max > 0 && stat->nodesizes[max-1] == 0)
2166
		max--;
2167

2168 2169 2170
	pointers = 0;
	for (i = 1; i <= max; i++)
		if (stat->nodesizes[i] != 0) {
2171
			seq_printf(seq, "  %u: %u",  i, stat->nodesizes[i]);
2172 2173 2174
			pointers += (1<<i) * stat->nodesizes[i];
		}
	seq_putc(seq, '\n');
2175
	seq_printf(seq, "\tPointers: %u\n", pointers);
R
Robert Olsson 已提交
2176

2177
	bytes += sizeof(struct node *) * pointers;
2178 2179
	seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
	seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
2180
}
R
Robert Olsson 已提交
2181

2182
#ifdef CONFIG_IP_FIB_TRIE_STATS
2183 2184 2185 2186
static void trie_show_usage(struct seq_file *seq,
			    const struct trie_use_stats *stats)
{
	seq_printf(seq, "\nCounters:\n---------\n");
2187 2188 2189 2190 2191 2192 2193 2194 2195
	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);
2196
}
2197 2198
#endif /*  CONFIG_IP_FIB_TRIE_STATS */

2199 2200
static void fib_trie_show(struct seq_file *seq, const char *name,
			  struct trie *trie)
2201 2202 2203 2204
{
	struct trie_stat stat;

	trie_collect_stats(trie, &stat);
2205
	seq_printf(seq, "%s:\n", name);
2206 2207 2208 2209 2210
	trie_show_stats(seq, &stat);
#ifdef CONFIG_IP_FIB_TRIE_STATS
	trie_show_usage(seq, &trie->stats);
#endif
}
2211

2212 2213
static int fib_triestat_seq_show(struct seq_file *seq, void *v)
{
2214
	struct net *net = (struct net *)seq->private;
2215 2216
	struct fib_table *tb;

2217
	seq_printf(seq,
2218 2219
		   "Basic info: size of leaf:"
		   " %Zd bytes, size of tnode: %Zd bytes.\n",
2220 2221
		   sizeof(struct leaf), sizeof(struct tnode));

2222
	tb = fib_get_table(net, RT_TABLE_LOCAL);
2223
	if (tb)
2224
		fib_trie_show(seq, "Local", (struct trie *) tb->tb_data);
2225

2226
	tb = fib_get_table(net, RT_TABLE_MAIN);
2227
	if (tb)
2228
		fib_trie_show(seq, "Main", (struct trie *) tb->tb_data);
2229

2230
	return 0;
2231 2232
}

2233
static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2234
{
2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253
	int err;
	struct net *net;

	net = get_proc_net(inode);
	if (net == NULL)
		return -ENXIO;
	err = single_open(file, fib_triestat_seq_show, net);
	if (err < 0) {
		put_net(net);
		return err;
	}
	return 0;
}

static int fib_triestat_seq_release(struct inode *ino, struct file *f)
{
	struct seq_file *seq = f->private_data;
	put_net(seq->private);
	return single_release(ino, f);
2254 2255
}

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

static struct node *fib_trie_get_idx(struct fib_trie_iter *iter,
				      loff_t pos)
2266
{
2267 2268 2269
	loff_t idx = 0;
	struct node *n;

2270
	for (n = fib_trie_get_first(iter, iter->trie_local);
2271 2272 2273 2274 2275
	     n; ++idx, n = fib_trie_get_next(iter)) {
		if (pos == idx)
			return n;
	}

2276
	for (n = fib_trie_get_first(iter, iter->trie_main);
2277 2278 2279 2280
	     n; ++idx, n = fib_trie_get_next(iter)) {
		if (pos == idx)
			return n;
	}
2281 2282 2283
	return NULL;
}

2284
static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2285
	__acquires(RCU)
2286
{
2287 2288 2289 2290
	struct fib_trie_iter *iter = seq->private;
	struct fib_table *tb;

	if (!iter->trie_local) {
2291
		tb = fib_get_table(iter->p.net, RT_TABLE_LOCAL);
2292 2293 2294 2295
		if (tb)
			iter->trie_local = (struct trie *) tb->tb_data;
	}
	if (!iter->trie_main) {
2296
		tb = fib_get_table(iter->p.net, RT_TABLE_MAIN);
2297 2298 2299
		if (tb)
			iter->trie_main = (struct trie *) tb->tb_data;
	}
2300 2301
	rcu_read_lock();
	if (*pos == 0)
O
Olof Johansson 已提交
2302
		return SEQ_START_TOKEN;
2303
	return fib_trie_get_idx(iter, *pos - 1);
2304 2305
}

2306
static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2307
{
2308 2309 2310
	struct fib_trie_iter *iter = seq->private;
	void *l = v;

2311
	++*pos;
O
Olof Johansson 已提交
2312
	if (v == SEQ_START_TOKEN)
2313
		return fib_trie_get_idx(iter, 0);
2314

2315 2316 2317 2318
	v = fib_trie_get_next(iter);
	BUG_ON(v == l);
	if (v)
		return v;
2319

2320
	/* continue scan in next trie */
2321 2322
	if (iter->trie == iter->trie_local)
		return fib_trie_get_first(iter, iter->trie_main);
2323

2324 2325
	return NULL;
}
2326

2327
static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2328
	__releases(RCU)
2329
{
2330 2331
	rcu_read_unlock();
}
O
Olof Johansson 已提交
2332

2333 2334 2335 2336
static void seq_indent(struct seq_file *seq, int n)
{
	while (n-- > 0) seq_puts(seq, "   ");
}
2337

2338
static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2339
{
S
Stephen Hemminger 已提交
2340
	switch (s) {
2341 2342 2343 2344 2345 2346
	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:
2347
		snprintf(buf, len, "scope=%d", s);
2348 2349 2350
		return buf;
	}
}
2351

2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365
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",
};
2366

2367
static inline const char *rtn_type(char *buf, size_t len, unsigned t)
2368 2369 2370
{
	if (t < __RTN_MAX && rtn_type_names[t])
		return rtn_type_names[t];
2371
	snprintf(buf, len, "type %u", t);
2372
	return buf;
2373 2374
}

2375 2376
/* Pretty print the trie */
static int fib_trie_seq_show(struct seq_file *seq, void *v)
2377
{
2378 2379
	const struct fib_trie_iter *iter = seq->private;
	struct node *n = v;
2380

2381 2382
	if (v == SEQ_START_TOKEN)
		return 0;
2383

2384
	if (!node_parent_rcu(n)) {
2385
		if (iter->trie == iter->trie_local)
2386 2387 2388 2389 2390
			seq_puts(seq, "<local>:\n");
		else
			seq_puts(seq, "<main>:\n");
	}

2391 2392
	if (IS_TNODE(n)) {
		struct tnode *tn = (struct tnode *) n;
S
Stephen Hemminger 已提交
2393
		__be32 prf = htonl(mask_pfx(tn->key, tn->pos));
O
Olof Johansson 已提交
2394

2395 2396
		seq_indent(seq, iter->depth-1);
		seq_printf(seq, "  +-- %d.%d.%d.%d/%d %d %d %d\n",
2397
			   NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
2398
			   tn->empty_children);
2399

2400 2401 2402
	} else {
		struct leaf *l = (struct leaf *) n;
		int i;
A
Al Viro 已提交
2403
		__be32 val = htonl(l->key);
2404 2405 2406 2407

		seq_indent(seq, iter->depth);
		seq_printf(seq, "  |-- %d.%d.%d.%d\n", NIPQUAD(val));
		for (i = 32; i >= 0; i--) {
R
Robert Olsson 已提交
2408
			struct leaf_info *li = find_leaf_info(l, i);
2409

2410 2411
			if (li) {
				struct fib_alias *fa;
2412

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

2416 2417
					seq_indent(seq, iter->depth+1);
					seq_printf(seq, "  /%d %s %s", i,
2418 2419 2420 2421
						   rtn_scope(buf1, sizeof(buf1),
							     fa->fa_scope),
						   rtn_type(buf2, sizeof(buf2),
							     fa->fa_type));
2422 2423 2424 2425 2426 2427 2428
					if (fa->fa_tos)
						seq_printf(seq, "tos =%d\n",
							   fa->fa_tos);
					seq_putc(seq, '\n');
				}
			}
		}
2429
	}
2430

2431 2432 2433
	return 0;
}

2434
static const struct seq_operations fib_trie_seq_ops = {
2435 2436 2437 2438
	.start  = fib_trie_seq_start,
	.next   = fib_trie_seq_next,
	.stop   = fib_trie_seq_stop,
	.show   = fib_trie_seq_show,
2439 2440
};

2441
static int fib_trie_seq_open(struct inode *inode, struct file *file)
2442
{
2443 2444
	return seq_open_net(inode, file, &fib_trie_seq_ops,
			    sizeof(struct fib_trie_iter));
2445 2446
}

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

A
Al Viro 已提交
2455
static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2456
{
2457 2458 2459 2460
	static unsigned type2flags[RTN_MAX + 1] = {
		[7] = RTF_REJECT, [8] = RTF_REJECT,
	};
	unsigned flags = type2flags[type];
2461

2462 2463
	if (fi && fi->fib_nh->nh_gw)
		flags |= RTF_GATEWAY;
A
Al Viro 已提交
2464
	if (mask == htonl(0xFFFFFFFF))
2465 2466 2467
		flags |= RTF_HOST;
	flags |= RTF_UP;
	return flags;
2468 2469
}

2470 2471 2472 2473 2474 2475 2476
/*
 *	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)
2477
{
2478
	const struct fib_trie_iter *iter = seq->private;
2479 2480 2481
	struct leaf *l = v;
	int i;
	char bf[128];
2482

2483 2484 2485 2486 2487 2488
	if (v == SEQ_START_TOKEN) {
		seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
			   "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
			   "\tWindow\tIRTT");
		return 0;
	}
2489

2490
	if (iter->trie == iter->trie_local)
2491
		return 0;
2492

2493 2494
	if (IS_TNODE(l))
		return 0;
2495

2496
	for (i = 32; i >= 0; i--) {
R
Robert Olsson 已提交
2497
		struct leaf_info *li = find_leaf_info(l, i);
2498
		struct fib_alias *fa;
A
Al Viro 已提交
2499
		__be32 mask, prefix;
O
Olof Johansson 已提交
2500

2501 2502
		if (!li)
			continue;
2503

2504 2505
		mask = inet_make_mask(li->plen);
		prefix = htonl(l->key);
2506

2507
		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2508
			const struct fib_info *fi = fa->fa_info;
2509
			unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2510

2511 2512 2513
			if (fa->fa_type == RTN_BROADCAST
			    || fa->fa_type == RTN_MULTICAST)
				continue;
2514

2515 2516 2517 2518 2519 2520 2521 2522
			if (fi)
				snprintf(bf, sizeof(bf),
					 "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
					 fi->fib_dev ? fi->fib_dev->name : "*",
					 prefix,
					 fi->fib_nh->nh_gw, flags, 0, 0,
					 fi->fib_priority,
					 mask,
2523 2524
					 (fi->fib_advmss ?
					  fi->fib_advmss + 40 : 0),
2525 2526 2527 2528 2529 2530 2531
					 fi->fib_window,
					 fi->fib_rtt >> 3);
			else
				snprintf(bf, sizeof(bf),
					 "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
					 prefix, 0, flags, 0, 0, 0,
					 mask, 0, 0, 0);
2532

2533 2534
			seq_printf(seq, "%-127s\n", bf);
		}
2535 2536 2537 2538 2539
	}

	return 0;
}

2540
static const struct seq_operations fib_route_seq_ops = {
2541 2542 2543 2544
	.start  = fib_trie_seq_start,
	.next   = fib_trie_seq_next,
	.stop   = fib_trie_seq_stop,
	.show   = fib_route_seq_show,
2545 2546
};

2547
static int fib_route_seq_open(struct inode *inode, struct file *file)
2548
{
2549 2550
	return seq_open_net(inode, file, &fib_route_seq_ops,
			    sizeof(struct fib_trie_iter));
2551 2552
}

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

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

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

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

2573
	return 0;
2574 2575

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

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

#endif /* CONFIG_PROC_FS */