fib_trie.c 59.3 KB
Newer Older
1 2 3 4 5 6 7 8 9
/*
 *   This program is free software; you can redistribute it and/or
 *   modify it under the terms of the GNU General Public License
 *   as published by the Free Software Foundation; either version
 *   2 of the License, or (at your option) any later version.
 *
 *   Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
 *     & Swedish University of Agricultural Sciences.
 *
10
 *   Jens Laas <jens.laas@data.slu.se> Swedish University of
11
 *     Agricultural Sciences.
12
 *
13 14 15
 *   Hans Liss <hans.liss@its.uu.se>  Uppsala Universitet
 *
 * This work is based on the LPC-trie which is originally descibed in:
16
 *
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 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;
}

1548 1549 1550 1551
/*
 * Remove the leaf and return parent.
 */
static void trie_leaf_remove(struct trie *t, struct leaf *l)
1552
{
1553
	struct tnode *tp = node_parent((struct node *) l);
1554

1555
	pr_debug("entering trie_leaf_remove(%p)\n", l);
1556

1557
	if (tp) {
1558
		t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1559
		put_child(t, (struct tnode *)tp, cindex, NULL);
R
Robert Olsson 已提交
1560
		rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
O
Olof Johansson 已提交
1561
	} else
R
Robert Olsson 已提交
1562
		rcu_assign_pointer(t->trie, NULL);
1563

1564
	tnode_free((struct tnode *) l);
1565 1566
}

1567 1568 1569
/*
 * Caller must hold RTNL.
 */
1570
static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
1571 1572 1573
{
	struct trie *t = (struct trie *) tb->tb_data;
	u32 key, mask;
1574 1575
	int plen = cfg->fc_dst_len;
	u8 tos = cfg->fc_tos;
1576 1577 1578
	struct fib_alias *fa, *fa_to_delete;
	struct list_head *fa_head;
	struct leaf *l;
O
Olof Johansson 已提交
1579 1580
	struct leaf_info *li;

1581
	if (plen > 32)
1582 1583
		return -EINVAL;

1584
	key = ntohl(cfg->fc_dst);
O
Olof Johansson 已提交
1585
	mask = ntohl(inet_make_mask(plen));
1586

1587
	if (key & ~mask)
1588 1589 1590 1591 1592
		return -EINVAL;

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

1593
	if (!l)
1594 1595 1596 1597 1598 1599 1600 1601
		return -ESRCH;

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

	if (!fa)
		return -ESRCH;

S
Stephen Hemminger 已提交
1602
	pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1603 1604 1605

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

1607 1608 1609 1610 1611 1612
	list_for_each_entry(fa, fa_head, fa_list) {
		struct fib_info *fi = fa->fa_info;

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

1613 1614 1615 1616 1617 1618
		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) {
1619 1620 1621 1622 1623
			fa_to_delete = fa;
			break;
		}
	}

O
Olof Johansson 已提交
1624 1625
	if (!fa_to_delete)
		return -ESRCH;
1626

O
Olof Johansson 已提交
1627
	fa = fa_to_delete;
1628
	rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1629
		  &cfg->fc_nlinfo, 0);
O
Olof Johansson 已提交
1630 1631

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

R
Robert Olsson 已提交
1634
	list_del_rcu(&fa->fa_list);
1635

O
Olof Johansson 已提交
1636
	if (list_empty(fa_head)) {
R
Robert Olsson 已提交
1637
		hlist_del_rcu(&li->hlist);
O
Olof Johansson 已提交
1638
		free_leaf_info(li);
R
Robert Olsson 已提交
1639
	}
1640

O
Olof Johansson 已提交
1641
	if (hlist_empty(&l->list))
1642
		trie_leaf_remove(t, l);
1643

O
Olof Johansson 已提交
1644 1645
	if (fa->fa_state & FA_S_ACCESSED)
		rt_cache_flush(-1);
1646

R
Robert Olsson 已提交
1647 1648
	fib_release_info(fa->fa_info);
	alias_free_mem_rcu(fa);
O
Olof Johansson 已提交
1649
	return 0;
1650 1651 1652 1653 1654 1655 1656 1657 1658 1659
}

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 已提交
1660 1661 1662 1663
		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);
1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680
			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 已提交
1681
			hlist_del_rcu(&li->hlist);
1682 1683 1684 1685 1686 1687
			free_leaf_info(li);
		}
	}
	return found;
}

1688 1689 1690 1691 1692
/*
 * 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)
1693
{
1694 1695
	do {
		t_key idx;
1696 1697

		if (c)
1698
			idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1699
		else
1700
			idx = 0;
R
Robert Olsson 已提交
1701

1702 1703
		while (idx < 1u << p->bits) {
			c = tnode_get_child_rcu(p, idx++);
R
Robert Olsson 已提交
1704
			if (!c)
O
Olof Johansson 已提交
1705 1706
				continue;

1707 1708 1709
			if (IS_LEAF(c)) {
				prefetch(p->child[idx]);
				return (struct leaf *) c;
1710
			}
1711 1712 1713 1714

			/* Rescan start scanning in new node */
			p = (struct tnode *) c;
			idx = 0;
1715
		}
1716 1717

		/* Node empty, walk back up to parent */
O
Olof Johansson 已提交
1718
		c = (struct node *) p;
1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746
	} while ( (p = node_parent_rcu(c)) != NULL);

	return NULL; /* Root of trie */
}


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

	if (!n)
		return NULL;

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

	return leaf_walk_rcu(n, NULL);
}

static struct leaf *trie_nextleaf(struct leaf *l)
{
	struct node *c = (struct node *) l;
	struct tnode *p = node_parent(c);

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

	return leaf_walk_rcu(p, c);
1747 1748
}

1749 1750 1751
/*
 * Caller must hold RTNL.
 */
1752 1753 1754
static int fn_trie_flush(struct fib_table *tb)
{
	struct trie *t = (struct trie *) tb->tb_data;
1755
	struct leaf *l, *ll = NULL;
1756
	int found = 0;
1757

1758
	for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1759 1760 1761
		found += trie_flush_leaf(t, l);

		if (ll && hlist_empty(&ll->list))
1762
			trie_leaf_remove(t, ll);
1763 1764 1765 1766
		ll = l;
	}

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

S
Stephen Hemminger 已提交
1769
	pr_debug("trie_flush found=%d\n", found);
1770 1771 1772
	return found;
}

1773 1774 1775
static void fn_trie_select_default(struct fib_table *tb,
				   const struct flowi *flp,
				   struct fib_result *res)
1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788
{
	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 已提交
1789
	rcu_read_lock();
1790

1791
	l = fib_find_node(t, 0);
1792
	if (!l)
1793 1794 1795
		goto out;

	fa_head = get_fa_head(l, 0);
1796
	if (!fa_head)
1797 1798
		goto out;

1799
	if (list_empty(fa_head))
1800 1801
		goto out;

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

1805 1806 1807
		if (fa->fa_scope != res->scope ||
		    fa->fa_type != RTN_UNICAST)
			continue;
O
Olof Johansson 已提交
1808

1809 1810 1811 1812 1813 1814
		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 已提交
1815

1816 1817 1818 1819
		if (fi == NULL) {
			if (next_fi != res->fi)
				break;
		} else if (!fib_detect_death(fi, order, &last_resort,
1820
					     &last_idx, tb->tb_default)) {
1821
			fib_result_assign(res, fi);
1822
			tb->tb_default = order;
1823 1824 1825 1826 1827 1828
			goto out;
		}
		fi = next_fi;
		order++;
	}
	if (order <= 0 || fi == NULL) {
1829
		tb->tb_default = -1;
1830 1831 1832
		goto out;
	}

1833 1834
	if (!fib_detect_death(fi, order, &last_resort, &last_idx,
				tb->tb_default)) {
1835
		fib_result_assign(res, fi);
1836
		tb->tb_default = order;
1837 1838
		goto out;
	}
1839 1840
	if (last_idx >= 0)
		fib_result_assign(res, last_resort);
1841 1842
	tb->tb_default = last_idx;
out:
R
Robert Olsson 已提交
1843
	rcu_read_unlock();
1844 1845
}

1846 1847
static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
			   struct fib_table *tb,
1848 1849 1850 1851 1852
			   struct sk_buff *skb, struct netlink_callback *cb)
{
	int i, s_i;
	struct fib_alias *fa;

A
Al Viro 已提交
1853
	__be32 xkey = htonl(key);
1854

1855
	s_i = cb->args[4];
1856 1857
	i = 0;

R
Robert Olsson 已提交
1858 1859 1860
	/* rcu_read_lock is hold by caller */

	list_for_each_entry_rcu(fa, fah, fa_list) {
1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871
		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,
1872
				  xkey,
1873 1874
				  plen,
				  fa->fa_tos,
1875
				  fa->fa_info, NLM_F_MULTI) < 0) {
1876
			cb->args[4] = i;
1877
			return -1;
O
Olof Johansson 已提交
1878
		}
1879 1880
		i++;
	}
1881
	cb->args[4] = i;
1882 1883 1884
	return skb->len;
}

1885 1886 1887

static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
			struct sk_buff *skb, struct netlink_callback *cb)
1888
{
1889 1890 1891
	struct leaf_info *li;
	struct hlist_node *node;
	int i, s_i;
1892

1893 1894
	s_i = cb->args[3];
	i = 0;
1895

1896 1897 1898 1899
	/* rcu_read_lock is hold by caller */
	hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
		if (i < s_i) {
			i++;
1900
			continue;
1901
		}
O
Olof Johansson 已提交
1902

1903 1904
		if (i > s_i)
			cb->args[4] = 0;
1905

1906
		if (list_empty(&li->falh))
1907 1908
			continue;

1909 1910
		if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
			cb->args[3] = i;
1911 1912
			return -1;
		}
1913
		i++;
1914
	}
1915 1916

	cb->args[3] = i;
1917 1918 1919
	return skb->len;
}

1920 1921
static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb,
			struct netlink_callback *cb)
1922
{
1923
	struct leaf *l;
1924
	struct trie *t = (struct trie *) tb->tb_data;
1925
	t_key key = cb->args[2];
1926

R
Robert Olsson 已提交
1927
	rcu_read_lock();
1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940
	/* Dump starting at last key.
	 * Note: 0.0.0.0/0 (ie default) is first key.
	 */
	if (!key)
		l = trie_firstleaf(t);
	else {
		l = fib_find_node(t, key);
		if (!l) {
			/* The table changed during the dump, rather than
			 * giving partial data, just make application retry.
			 */
			rcu_read_unlock();
			return -EBUSY;
1941
		}
1942
	}
1943

1944 1945
	while (l) {
		cb->args[2] = l->key;
1946 1947 1948
		if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
			rcu_read_unlock();
			return -1;
1949
		}
1950 1951 1952 1953

		l = trie_nextleaf(l);
		memset(&cb->args[3], 0,
		       sizeof(cb->args) - 3*sizeof(cb->args[0]));
1954
	}
R
Robert Olsson 已提交
1955
	rcu_read_unlock();
1956

1957 1958 1959
	return skb->len;
}

1960 1961
void __init fib_hash_init(void)
{
1962 1963
	fn_alias_kmem = kmem_cache_create("ip_fib_alias",
					  sizeof(struct fib_alias),
1964 1965 1966 1967 1968 1969
					  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);
1970
}
1971

1972 1973 1974

/* Fix more generic FIB names for init later */
struct fib_table *fib_hash_table(u32 id)
1975 1976 1977 1978 1979 1980 1981 1982 1983 1984
{
	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;
1985
	tb->tb_default = -1;
1986 1987 1988 1989 1990 1991 1992 1993
	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;
1994
	memset(t, 0, sizeof(*t));
1995 1996

	if (id == RT_TABLE_LOCAL)
1997
		pr_info("IPv4 FIB: Using LC-trie version %s\n", VERSION);
1998 1999 2000 2001

	return tb;
}

2002 2003 2004
#ifdef CONFIG_PROC_FS
/* Depth first Trie walk iterator */
struct fib_trie_iter {
2005
	struct seq_net_private p;
2006
	struct trie *trie_local, *trie_main;
2007 2008 2009 2010 2011
	struct tnode *tnode;
	struct trie *trie;
	unsigned index;
	unsigned depth;
};
2012

2013
static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
2014
{
2015 2016 2017
	struct tnode *tn = iter->tnode;
	unsigned cindex = iter->index;
	struct tnode *p;
2018

2019 2020 2021 2022
	/* A single entry routing table */
	if (!tn)
		return NULL;

2023 2024 2025 2026
	pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
		 iter->tnode, iter->index, iter->depth);
rescan:
	while (cindex < (1<<tn->bits)) {
2027
		struct node *n = tnode_get_child_rcu(tn, cindex);
2028

2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040
		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;
		}
2041

2042 2043
		++cindex;
	}
O
Olof Johansson 已提交
2044

2045
	/* Current node exhausted, pop back up */
2046
	p = node_parent_rcu((struct node *)tn);
2047 2048 2049 2050 2051
	if (p) {
		cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
		tn = p;
		--iter->depth;
		goto rescan;
2052
	}
2053 2054 2055

	/* got root? */
	return NULL;
2056 2057
}

2058 2059
static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
				       struct trie *t)
2060
{
2061 2062
	struct node *n ;

S
Stephen Hemminger 已提交
2063
	if (!t)
2064 2065 2066 2067
		return NULL;

	n = rcu_dereference(t->trie);

S
Stephen Hemminger 已提交
2068
	if (!iter)
2069
		return NULL;
2070

2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082
	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;
		}
2083
		return n;
O
Olof Johansson 已提交
2084
	}
2085 2086
	return NULL;
}
O
Olof Johansson 已提交
2087

2088 2089 2090 2091
static void trie_collect_stats(struct trie *t, struct trie_stat *s)
{
	struct node *n;
	struct fib_trie_iter iter;
O
Olof Johansson 已提交
2092

2093
	memset(s, 0, sizeof(*s));
O
Olof Johansson 已提交
2094

2095 2096 2097 2098
	rcu_read_lock();
	for (n = fib_trie_get_first(&iter, t); n;
	     n = fib_trie_get_next(&iter)) {
		if (IS_LEAF(n)) {
2099 2100 2101 2102
			struct leaf *l = (struct leaf *)n;
			struct leaf_info *li;
			struct hlist_node *tmp;

2103 2104 2105 2106
			s->leaves++;
			s->totdepth += iter.depth;
			if (iter.depth > s->maxdepth)
				s->maxdepth = iter.depth;
2107 2108 2109

			hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
				++s->prefixes;
2110 2111 2112 2113 2114
		} else {
			const struct tnode *tn = (const struct tnode *) n;
			int i;

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

2118 2119 2120
			for (i = 0; i < (1<<tn->bits); i++)
				if (!tn->child[i])
					s->nullpointers++;
2121 2122
		}
	}
R
Robert Olsson 已提交
2123
	rcu_read_unlock();
2124 2125
}

2126 2127 2128 2129
/*
 *	This outputs /proc/net/fib_triestats
 */
static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2130
{
2131
	unsigned i, max, pointers, bytes, avdepth;
2132

2133 2134 2135 2136
	if (stat->leaves)
		avdepth = stat->totdepth*100 / stat->leaves;
	else
		avdepth = 0;
O
Olof Johansson 已提交
2137

2138 2139
	seq_printf(seq, "\tAver depth:     %u.%02d\n",
		   avdepth / 100, avdepth % 100);
2140
	seq_printf(seq, "\tMax depth:      %u\n", stat->maxdepth);
O
Olof Johansson 已提交
2141

2142 2143
	seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
	bytes = sizeof(struct leaf) * stat->leaves;
2144 2145 2146 2147

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

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

R
Robert Olsson 已提交
2151 2152
	max = MAX_STAT_DEPTH;
	while (max > 0 && stat->nodesizes[max-1] == 0)
2153
		max--;
2154

2155 2156 2157
	pointers = 0;
	for (i = 1; i <= max; i++)
		if (stat->nodesizes[i] != 0) {
2158
			seq_printf(seq, "  %u: %u",  i, stat->nodesizes[i]);
2159 2160 2161
			pointers += (1<<i) * stat->nodesizes[i];
		}
	seq_putc(seq, '\n');
2162
	seq_printf(seq, "\tPointers: %u\n", pointers);
R
Robert Olsson 已提交
2163

2164
	bytes += sizeof(struct node *) * pointers;
2165 2166
	seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
	seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
2167
}
R
Robert Olsson 已提交
2168

2169
#ifdef CONFIG_IP_FIB_TRIE_STATS
2170 2171 2172 2173
static void trie_show_usage(struct seq_file *seq,
			    const struct trie_use_stats *stats)
{
	seq_printf(seq, "\nCounters:\n---------\n");
2174 2175 2176 2177 2178 2179 2180 2181 2182
	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);
2183
}
2184 2185
#endif /*  CONFIG_IP_FIB_TRIE_STATS */

2186 2187
static void fib_trie_show(struct seq_file *seq, const char *name,
			  struct trie *trie)
2188 2189 2190 2191
{
	struct trie_stat stat;

	trie_collect_stats(trie, &stat);
2192
	seq_printf(seq, "%s:\n", name);
2193 2194 2195 2196 2197
	trie_show_stats(seq, &stat);
#ifdef CONFIG_IP_FIB_TRIE_STATS
	trie_show_usage(seq, &trie->stats);
#endif
}
2198

2199 2200
static int fib_triestat_seq_show(struct seq_file *seq, void *v)
{
2201
	struct net *net = (struct net *)seq->private;
2202 2203
	struct fib_table *tb;

2204
	seq_printf(seq,
2205 2206
		   "Basic info: size of leaf:"
		   " %Zd bytes, size of tnode: %Zd bytes.\n",
2207 2208
		   sizeof(struct leaf), sizeof(struct tnode));

2209
	tb = fib_get_table(net, RT_TABLE_LOCAL);
2210
	if (tb)
2211
		fib_trie_show(seq, "Local", (struct trie *) tb->tb_data);
2212

2213
	tb = fib_get_table(net, RT_TABLE_MAIN);
2214
	if (tb)
2215
		fib_trie_show(seq, "Main", (struct trie *) tb->tb_data);
2216

2217
	return 0;
2218 2219
}

2220
static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2221
{
2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240
	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);
2241 2242
}

2243
static const struct file_operations fib_triestat_fops = {
2244 2245 2246 2247
	.owner	= THIS_MODULE,
	.open	= fib_triestat_seq_open,
	.read	= seq_read,
	.llseek	= seq_lseek,
2248
	.release = fib_triestat_seq_release,
2249 2250 2251 2252
};

static struct node *fib_trie_get_idx(struct fib_trie_iter *iter,
				      loff_t pos)
2253
{
2254 2255 2256
	loff_t idx = 0;
	struct node *n;

2257
	for (n = fib_trie_get_first(iter, iter->trie_local);
2258 2259 2260 2261 2262
	     n; ++idx, n = fib_trie_get_next(iter)) {
		if (pos == idx)
			return n;
	}

2263
	for (n = fib_trie_get_first(iter, iter->trie_main);
2264 2265 2266 2267
	     n; ++idx, n = fib_trie_get_next(iter)) {
		if (pos == idx)
			return n;
	}
2268 2269 2270
	return NULL;
}

2271
static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2272
	__acquires(RCU)
2273
{
2274 2275 2276 2277
	struct fib_trie_iter *iter = seq->private;
	struct fib_table *tb;

	if (!iter->trie_local) {
2278
		tb = fib_get_table(iter->p.net, RT_TABLE_LOCAL);
2279 2280 2281 2282
		if (tb)
			iter->trie_local = (struct trie *) tb->tb_data;
	}
	if (!iter->trie_main) {
2283
		tb = fib_get_table(iter->p.net, RT_TABLE_MAIN);
2284 2285 2286
		if (tb)
			iter->trie_main = (struct trie *) tb->tb_data;
	}
2287 2288
	rcu_read_lock();
	if (*pos == 0)
O
Olof Johansson 已提交
2289
		return SEQ_START_TOKEN;
2290
	return fib_trie_get_idx(iter, *pos - 1);
2291 2292
}

2293
static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2294
{
2295 2296 2297
	struct fib_trie_iter *iter = seq->private;
	void *l = v;

2298
	++*pos;
O
Olof Johansson 已提交
2299
	if (v == SEQ_START_TOKEN)
2300
		return fib_trie_get_idx(iter, 0);
2301

2302 2303 2304 2305
	v = fib_trie_get_next(iter);
	BUG_ON(v == l);
	if (v)
		return v;
2306

2307
	/* continue scan in next trie */
2308 2309
	if (iter->trie == iter->trie_local)
		return fib_trie_get_first(iter, iter->trie_main);
2310

2311 2312
	return NULL;
}
2313

2314
static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2315
	__releases(RCU)
2316
{
2317 2318
	rcu_read_unlock();
}
O
Olof Johansson 已提交
2319

2320 2321 2322 2323
static void seq_indent(struct seq_file *seq, int n)
{
	while (n-- > 0) seq_puts(seq, "   ");
}
2324

2325
static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2326
{
S
Stephen Hemminger 已提交
2327
	switch (s) {
2328 2329 2330 2331 2332 2333
	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:
2334
		snprintf(buf, len, "scope=%d", s);
2335 2336 2337
		return buf;
	}
}
2338

2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352
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",
};
2353

2354
static inline const char *rtn_type(char *buf, size_t len, unsigned t)
2355 2356 2357
{
	if (t < __RTN_MAX && rtn_type_names[t])
		return rtn_type_names[t];
2358
	snprintf(buf, len, "type %u", t);
2359
	return buf;
2360 2361
}

2362 2363
/* Pretty print the trie */
static int fib_trie_seq_show(struct seq_file *seq, void *v)
2364
{
2365 2366
	const struct fib_trie_iter *iter = seq->private;
	struct node *n = v;
2367

2368 2369
	if (v == SEQ_START_TOKEN)
		return 0;
2370

2371
	if (!node_parent_rcu(n)) {
2372
		if (iter->trie == iter->trie_local)
2373 2374 2375 2376 2377
			seq_puts(seq, "<local>:\n");
		else
			seq_puts(seq, "<main>:\n");
	}

2378 2379
	if (IS_TNODE(n)) {
		struct tnode *tn = (struct tnode *) n;
S
Stephen Hemminger 已提交
2380
		__be32 prf = htonl(mask_pfx(tn->key, tn->pos));
O
Olof Johansson 已提交
2381

2382 2383
		seq_indent(seq, iter->depth-1);
		seq_printf(seq, "  +-- %d.%d.%d.%d/%d %d %d %d\n",
2384
			   NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
2385
			   tn->empty_children);
2386

2387 2388
	} else {
		struct leaf *l = (struct leaf *) n;
2389 2390 2391
		struct leaf_info *li;
		struct hlist_node *node;

A
Al Viro 已提交
2392
		__be32 val = htonl(l->key);
2393 2394 2395

		seq_indent(seq, iter->depth);
		seq_printf(seq, "  |-- %d.%d.%d.%d\n", NIPQUAD(val));
2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412

		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)
					seq_printf(seq, "tos =%d\n",
						   fa->fa_tos);
				seq_putc(seq, '\n');
2413 2414
			}
		}
2415
	}
2416

2417 2418 2419
	return 0;
}

2420
static const struct seq_operations fib_trie_seq_ops = {
2421 2422 2423 2424
	.start  = fib_trie_seq_start,
	.next   = fib_trie_seq_next,
	.stop   = fib_trie_seq_stop,
	.show   = fib_trie_seq_show,
2425 2426
};

2427
static int fib_trie_seq_open(struct inode *inode, struct file *file)
2428
{
2429 2430
	return seq_open_net(inode, file, &fib_trie_seq_ops,
			    sizeof(struct fib_trie_iter));
2431 2432
}

2433
static const struct file_operations fib_trie_fops = {
2434 2435 2436 2437
	.owner  = THIS_MODULE,
	.open   = fib_trie_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2438
	.release = seq_release_net,
2439 2440
};

A
Al Viro 已提交
2441
static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2442
{
2443 2444 2445 2446
	static unsigned type2flags[RTN_MAX + 1] = {
		[7] = RTF_REJECT, [8] = RTF_REJECT,
	};
	unsigned flags = type2flags[type];
2447

2448 2449
	if (fi && fi->fib_nh->nh_gw)
		flags |= RTF_GATEWAY;
A
Al Viro 已提交
2450
	if (mask == htonl(0xFFFFFFFF))
2451 2452 2453
		flags |= RTF_HOST;
	flags |= RTF_UP;
	return flags;
2454 2455
}

2456 2457 2458 2459 2460 2461 2462
/*
 *	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)
2463
{
2464
	const struct fib_trie_iter *iter = seq->private;
2465
	struct leaf *l = v;
2466 2467
	struct leaf_info *li;
	struct hlist_node *node;
2468

2469 2470 2471 2472 2473 2474
	if (v == SEQ_START_TOKEN) {
		seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
			   "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
			   "\tWindow\tIRTT");
		return 0;
	}
2475

2476
	if (iter->trie == iter->trie_local)
2477
		return 0;
2478

2479 2480
	if (IS_TNODE(l))
		return 0;
2481

2482
	hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2483
		struct fib_alias *fa;
A
Al Viro 已提交
2484
		__be32 mask, prefix;
O
Olof Johansson 已提交
2485

2486 2487
		if (!li)
			continue;
2488

2489 2490
		mask = inet_make_mask(li->plen);
		prefix = htonl(l->key);
2491

2492
		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2493
			const struct fib_info *fi = fa->fa_info;
2494
			unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2495
			char bf[128];
2496

2497 2498 2499
			if (fa->fa_type == RTN_BROADCAST
			    || fa->fa_type == RTN_MULTICAST)
				continue;
2500

2501 2502 2503 2504 2505 2506 2507 2508
			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,
2509 2510
					 (fi->fib_advmss ?
					  fi->fib_advmss + 40 : 0),
2511 2512 2513 2514 2515 2516 2517
					 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);
2518

2519 2520
			seq_printf(seq, "%-127s\n", bf);
		}
2521 2522 2523 2524 2525
	}

	return 0;
}

2526
static const struct seq_operations fib_route_seq_ops = {
2527 2528 2529 2530
	.start  = fib_trie_seq_start,
	.next   = fib_trie_seq_next,
	.stop   = fib_trie_seq_stop,
	.show   = fib_route_seq_show,
2531 2532
};

2533
static int fib_route_seq_open(struct inode *inode, struct file *file)
2534
{
2535 2536
	return seq_open_net(inode, file, &fib_route_seq_ops,
			    sizeof(struct fib_trie_iter));
2537 2538
}

2539
static const struct file_operations fib_route_fops = {
2540 2541 2542 2543
	.owner  = THIS_MODULE,
	.open   = fib_route_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2544
	.release = seq_release_net,
2545 2546
};

2547
int __net_init fib_proc_init(struct net *net)
2548
{
2549
	if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
2550 2551
		goto out1;

2552 2553
	if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
				  &fib_triestat_fops))
2554 2555
		goto out2;

2556
	if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
2557 2558
		goto out3;

2559
	return 0;
2560 2561

out3:
2562
	proc_net_remove(net, "fib_triestat");
2563
out2:
2564
	proc_net_remove(net, "fib_trie");
2565 2566
out1:
	return -ENOMEM;
2567 2568
}

2569
void __net_exit fib_proc_exit(struct net *net)
2570
{
2571 2572 2573
	proc_net_remove(net, "fib_trie");
	proc_net_remove(net, "fib_triestat");
	proc_net_remove(net, "route");
2574 2575 2576
}

#endif /* CONFIG_PROC_FS */