fib_trie.c 58.2 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.407"
54 55 56 57 58 59 60 61 62 63 64 65 66

#include <asm/uaccess.h>
#include <asm/system.h>
#include <asm/bitops.h>
#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 76 77 78 79 80 81 82 83 84
#include <linux/skbuff.h>
#include <linux/netlink.h>
#include <linux/init.h>
#include <linux/list.h>
#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"

#undef CONFIG_IP_FIB_TRIE_STATS
R
Robert Olsson 已提交
85
#define MAX_STAT_DEPTH 32
86 87 88 89 90 91 92 93 94 95

#define KEYLENGTH (8*sizeof(t_key))
#define MASK_PFX(k, l) (((l)==0)?0:(k >> (KEYLENGTH-l)) << (KEYLENGTH-l))
#define TKEY_GET_MASK(offset, bits) (((bits)==0)?0:((t_key)(-1) << (KEYLENGTH - bits) >> offset))

typedef unsigned int t_key;

#define T_TNODE 0
#define T_LEAF  1
#define NODE_TYPE_MASK	0x1UL
O
Olof Johansson 已提交
96
#define NODE_PARENT(node) \
R
Robert Olsson 已提交
97 98 99 100 101 102 103
	((struct tnode *)rcu_dereference(((node)->parent & ~NODE_TYPE_MASK)))

#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)

#define NODE_SET_PARENT(node, ptr)		\
	rcu_assign_pointer((node)->parent,	\
			   ((unsigned long)(ptr)) | NODE_TYPE(node))
O
Olof Johansson 已提交
104 105 106

#define IS_TNODE(n) (!(n->parent & T_LEAF))
#define IS_LEAF(n) (n->parent & T_LEAF)
107 108

struct node {
O
Olof Johansson 已提交
109 110
	t_key key;
	unsigned long parent;
111 112 113
};

struct leaf {
O
Olof Johansson 已提交
114 115
	t_key key;
	unsigned long parent;
116
	struct hlist_head list;
R
Robert Olsson 已提交
117
	struct rcu_head rcu;
118 119 120 121
};

struct leaf_info {
	struct hlist_node hlist;
R
Robert Olsson 已提交
122
	struct rcu_head rcu;
123 124 125 126 127
	int plen;
	struct list_head falh;
};

struct tnode {
O
Olof Johansson 已提交
128 129 130 131 132 133
	t_key key;
	unsigned long parent;
	unsigned short pos:5;		/* 2log(KEYLENGTH) bits needed */
	unsigned short bits:5;		/* 2log(KEYLENGTH) bits needed */
	unsigned short full_children;	/* KEYLENGTH bits needed */
	unsigned short empty_children;	/* KEYLENGTH bits needed */
R
Robert Olsson 已提交
134
	struct rcu_head rcu;
O
Olof Johansson 已提交
135
	struct node *child[0];
136 137 138 139 140 141 142 143 144
};

#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;
145
	unsigned int resize_node_skipped;
146 147 148 149 150 151 152 153 154
};
#endif

struct trie_stat {
	unsigned int totdepth;
	unsigned int maxdepth;
	unsigned int tnodes;
	unsigned int leaves;
	unsigned int nullpointers;
R
Robert Olsson 已提交
155
	unsigned int nodesizes[MAX_STAT_DEPTH];
156
};
157 158

struct trie {
O
Olof Johansson 已提交
159
	struct node *trie;
160 161 162
#ifdef CONFIG_IP_FIB_TRIE_STATS
	struct trie_use_stats stats;
#endif
O
Olof Johansson 已提交
163
	int size;
164 165 166 167 168 169
	unsigned int revision;
};

static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull);
static struct node *resize(struct trie *t, struct tnode *tn);
170 171
static struct tnode *inflate(struct trie *t, struct tnode *tn);
static struct tnode *halve(struct trie *t, struct tnode *tn);
172 173
static void tnode_free(struct tnode *tn);

174
static struct kmem_cache *fn_alias_kmem __read_mostly;
175 176
static struct trie *trie_local = NULL, *trie_main = NULL;

R
Robert Olsson 已提交
177 178 179

/* rcu_read_lock needs to be hold by caller from readside */

180
static inline struct node *tnode_get_child(struct tnode *tn, int i)
181
{
O
Olof Johansson 已提交
182
	BUG_ON(i >= 1 << tn->bits);
183

R
Robert Olsson 已提交
184
	return rcu_dereference(tn->child[i]);
185 186
}

S
Stephen Hemmigner 已提交
187
static inline int tnode_child_length(const struct tnode *tn)
188
{
O
Olof Johansson 已提交
189
	return 1 << tn->bits;
190 191 192 193
}

static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
{
O
Olof Johansson 已提交
194
	if (offset < KEYLENGTH)
195
		return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
O
Olof Johansson 已提交
196
	else
197 198 199 200 201
		return 0;
}

static inline int tkey_equals(t_key a, t_key b)
{
202
	return a == b;
203 204 205 206
}

static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
{
207 208
	if (bits == 0 || offset >= KEYLENGTH)
		return 1;
O
Olof Johansson 已提交
209 210
	bits = bits > KEYLENGTH ? KEYLENGTH : bits;
	return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
211
}
212 213 214 215 216 217

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

218 219 220
	if (!diff)
		return 0;
	while ((diff << i) >> (KEYLENGTH-1) == 0)
221 222 223 224 225
		i++;
	return i;
}

/*
226 227
  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
228 229 230 231
  all of the bits in that key are significant.

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

232 233 234 235 236
  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
237 238
  correct key path.

239 240 241 242 243
  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
244 245
  call to tkey_sub_equals() in trie_insert().

246
  if n is an internal node - a 'tnode' here, the various parts of its key
247 248
  have many different meanings.

249
  Example:
250 251 252
  _________________________________________________________________
  | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
  -----------------------------------------------------------------
253
    0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
254 255 256 257 258 259 260 261 262

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

265 266
  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
267 268 269
  not use them for anything.

  The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
270
  index into the parent's child array. That is, they will be used to find
271 272 273 274 275
  'n' among tp's children.

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

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

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

282

283 284 285 286 287
  The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
  at this point.

*/

S
Stephen Hemminger 已提交
288
static inline void check_tnode(const struct tnode *tn)
289
{
S
Stephen Hemminger 已提交
290
	WARN_ON(tn && tn->pos+tn->bits > 32);
291 292 293 294
}

static int halve_threshold = 25;
static int inflate_threshold = 50;
295
static int halve_threshold_root = 15;
296
static int inflate_threshold_root = 25;
297

R
Robert Olsson 已提交
298 299

static void __alias_free_mem(struct rcu_head *head)
300
{
R
Robert Olsson 已提交
301 302
	struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
	kmem_cache_free(fn_alias_kmem, fa);
303 304
}

R
Robert Olsson 已提交
305
static inline void alias_free_mem_rcu(struct fib_alias *fa)
306
{
R
Robert Olsson 已提交
307 308
	call_rcu(&fa->rcu, __alias_free_mem);
}
O
Olof Johansson 已提交
309

R
Robert Olsson 已提交
310 311 312 313
static void __leaf_free_rcu(struct rcu_head *head)
{
	kfree(container_of(head, struct leaf, rcu));
}
O
Olof Johansson 已提交
314

R
Robert Olsson 已提交
315
static void __leaf_info_free_rcu(struct rcu_head *head)
316
{
R
Robert Olsson 已提交
317
	kfree(container_of(head, struct leaf_info, rcu));
318 319
}

R
Robert Olsson 已提交
320
static inline void free_leaf_info(struct leaf_info *leaf)
321
{
R
Robert Olsson 已提交
322
	call_rcu(&leaf->rcu, __leaf_info_free_rcu);
323 324
}

325 326
static struct tnode *tnode_alloc(unsigned int size)
{
R
Robert Olsson 已提交
327 328 329 330 331 332 333 334 335 336
	struct page *pages;

	if (size <= PAGE_SIZE)
		return kcalloc(size, 1, GFP_KERNEL);

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

	return page_address(pages);
337 338
}

R
Robert Olsson 已提交
339
static void __tnode_free_rcu(struct rcu_head *head)
340
{
R
Robert Olsson 已提交
341
	struct tnode *tn = container_of(head, struct tnode, rcu);
342
	unsigned int size = sizeof(struct tnode) +
R
Robert Olsson 已提交
343
		(1 << tn->bits) * sizeof(struct node *);
344 345 346 347 348 349 350

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

R
Robert Olsson 已提交
351 352
static inline void tnode_free(struct tnode *tn)
{
S
Stephen Hemminger 已提交
353
	if (IS_LEAF(tn)) {
R
Robert Olsson 已提交
354 355
		struct leaf *l = (struct leaf *) tn;
		call_rcu_bh(&l->rcu, __leaf_free_rcu);
S
Stephen Hemminger 已提交
356
	} else
R
Robert Olsson 已提交
357
		call_rcu(&tn->rcu, __tnode_free_rcu);
R
Robert Olsson 已提交
358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379
}

static struct leaf *leaf_new(void)
{
	struct leaf *l = kmalloc(sizeof(struct leaf),  GFP_KERNEL);
	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;
}

380 381 382 383
static struct tnode* tnode_new(t_key key, int pos, int bits)
{
	int nchildren = 1<<bits;
	int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *);
384
	struct tnode *tn = tnode_alloc(sz);
385

O
Olof Johansson 已提交
386
	if (tn) {
387
		memset(tn, 0, sz);
R
Robert Olsson 已提交
388
		tn->parent = T_TNODE;
389 390 391 392 393 394
		tn->pos = pos;
		tn->bits = bits;
		tn->key = key;
		tn->full_children = 0;
		tn->empty_children = 1<<bits;
	}
395

S
Stephen Hemminger 已提交
396 397
	pr_debug("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode),
		 (unsigned int) (sizeof(struct node) * 1<<bits));
398 399 400 401 402 403 404 405
	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 已提交
406
static inline int tnode_full(const struct tnode *tn, const struct node *n)
407
{
408
	if (n == NULL || IS_LEAF(n))
409 410 411 412 413
		return 0;

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

414
static inline void put_child(struct trie *t, struct tnode *tn, int i, struct node *n)
415 416 417 418
{
	tnode_put_child_reorg(tn, i, n, -1);
}

419
 /*
420 421 422 423
  * Add a child at position i overwriting the old value.
  * Update the value of full_children and empty_children.
  */

424
static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull)
425
{
R
Robert Olsson 已提交
426
	struct node *chi = tn->child[i];
427 428
	int isfull;

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

431 432 433 434 435 436

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

438
	/* update fullChildren */
O
Olof Johansson 已提交
439
	if (wasfull == -1)
440 441 442
		wasfull = tnode_full(tn, chi);

	isfull = tnode_full(tn, n);
443
	if (wasfull && !isfull)
444
		tn->full_children--;
445
	else if (!wasfull && isfull)
446
		tn->full_children++;
O
Olof Johansson 已提交
447

448 449
	if (n)
		NODE_SET_PARENT(n, tn);
450

R
Robert Olsson 已提交
451
	rcu_assign_pointer(tn->child[i], n);
452 453
}

454
static struct node *resize(struct trie *t, struct tnode *tn)
455 456
{
	int i;
457
	int err = 0;
458
	struct tnode *old_tn;
459 460
	int inflate_threshold_use;
	int halve_threshold_use;
461

462
	if (!tn)
463 464
		return NULL;

S
Stephen Hemminger 已提交
465 466
	pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
		 tn, inflate_threshold, halve_threshold);
467 468 469 470 471 472 473 474 475

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

O
Olof Johansson 已提交
478
			n = tn->child[i];
R
Robert Olsson 已提交
479
			if (!n)
O
Olof Johansson 已提交
480 481 482
				continue;

			/* compress one level */
R
Robert Olsson 已提交
483
			NODE_SET_PARENT(n, NULL);
O
Olof Johansson 已提交
484 485
			tnode_free(tn);
			return n;
486
		}
487
	/*
488 489 490 491 492
	 * Double as long as the resulting node has a number of
	 * nonempty nodes that are above the threshold.
	 */

	/*
493 494
	 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
	 * the Helsinki University of Technology and Matti Tikkanen of Nokia
495
	 * Telecommunications, page 6:
496
	 * "A node is doubled if the ratio of non-empty children to all
497 498
	 * children in the *doubled* node is at least 'high'."
	 *
499 500 501 502 503
	 * '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
504
	 * multiply the left-hand side by 50.
505 506 507 508
	 *
	 * 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"
509
	 * children, that is non-null tnodes with a skip value of 0.
510
	 * All of those will be doubled in the resulting inflated tnode, so
511
	 * we just count them one extra time here.
512
	 *
513
	 * A clearer way to write this would be:
514
	 *
515
	 * to_be_doubled = tn->full_children;
516
	 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
517 518 519 520
	 *     tn->full_children;
	 *
	 * new_child_length = tnode_child_length(tn) * 2;
	 *
521
	 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
522 523
	 *      new_child_length;
	 * if (new_fill_factor >= inflate_threshold)
524 525 526
	 *
	 * ...and so on, tho it would mess up the while () loop.
	 *
527 528 529
	 * anyway,
	 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
	 *      inflate_threshold
530
	 *
531 532 533
	 * avoid a division:
	 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
	 *      inflate_threshold * new_child_length
534
	 *
535
	 * expand not_to_be_doubled and to_be_doubled, and shorten:
536
	 * 100 * (tnode_child_length(tn) - tn->empty_children +
O
Olof Johansson 已提交
537
	 *    tn->full_children) >= inflate_threshold * new_child_length
538
	 *
539
	 * expand new_child_length:
540
	 * 100 * (tnode_child_length(tn) - tn->empty_children +
O
Olof Johansson 已提交
541
	 *    tn->full_children) >=
542
	 *      inflate_threshold * tnode_child_length(tn) * 2
543
	 *
544
	 * shorten again:
545
	 * 50 * (tn->full_children + tnode_child_length(tn) -
O
Olof Johansson 已提交
546
	 *    tn->empty_children) >= inflate_threshold *
547
	 *    tnode_child_length(tn)
548
	 *
549 550 551
	 */

	check_tnode(tn);
552

553 554
	/* Keep root node larger  */

S
Stephen Hemminger 已提交
555
	if (!tn->parent)
556
		inflate_threshold_use = inflate_threshold_root;
557
	else
558 559
		inflate_threshold_use = inflate_threshold;

560
	err = 0;
561 562
	while ((tn->full_children > 0 &&
	       50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >=
563
				inflate_threshold_use * tnode_child_length(tn))) {
564

565 566 567 568
		old_tn = tn;
		tn = inflate(t, tn);
		if (IS_ERR(tn)) {
			tn = old_tn;
569 570 571 572 573
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.resize_node_skipped++;
#endif
			break;
		}
574 575 576 577 578 579 580 581
	}

	check_tnode(tn);

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

583 584 585

	/* Keep root node larger  */

S
Stephen Hemminger 已提交
586
	if (!tn->parent)
587
		halve_threshold_use = halve_threshold_root;
588
	else
589 590
		halve_threshold_use = halve_threshold;

591
	err = 0;
592 593
	while (tn->bits > 1 &&
	       100 * (tnode_child_length(tn) - tn->empty_children) <
594
	       halve_threshold_use * tnode_child_length(tn)) {
595

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

607

608 609 610
	/* 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 已提交
611
			struct node *n;
612

O
Olof Johansson 已提交
613
			n = tn->child[i];
R
Robert Olsson 已提交
614
			if (!n)
O
Olof Johansson 已提交
615 616 617 618
				continue;

			/* compress one level */

R
Robert Olsson 已提交
619
			NODE_SET_PARENT(n, NULL);
O
Olof Johansson 已提交
620 621
			tnode_free(tn);
			return n;
622 623 624 625 626
		}

	return (struct node *) tn;
}

627
static struct tnode *inflate(struct trie *t, struct tnode *tn)
628 629 630 631 632 633
{
	struct tnode *inode;
	struct tnode *oldtnode = tn;
	int olen = tnode_child_length(tn);
	int i;

S
Stephen Hemminger 已提交
634
	pr_debug("In inflate\n");
635 636 637

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

S
Stephen Hemminger 已提交
638
	if (!tn)
639
		return ERR_PTR(-ENOMEM);
640 641

	/*
642 643 644
	 * 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
645 646
	 * of tnode is ignored.
	 */
O
Olof Johansson 已提交
647 648

	for (i = 0; i < olen; i++) {
649 650 651 652 653 654 655 656
		struct tnode *inode = (struct tnode *) tnode_get_child(oldtnode, i);

		if (inode &&
		    IS_TNODE(inode) &&
		    inode->pos == oldtnode->pos + oldtnode->bits &&
		    inode->bits > 1) {
			struct tnode *left, *right;
			t_key m = TKEY_GET_MASK(inode->pos, 1);
657

658 659
			left = tnode_new(inode->key&(~m), inode->pos + 1,
					 inode->bits - 1);
660 661
			if (!left)
				goto nomem;
O
Olof Johansson 已提交
662

663 664 665
			right = tnode_new(inode->key|m, inode->pos + 1,
					  inode->bits - 1);

666
			if (!right) {
667 668
				tnode_free(left);
				goto nomem;
669
			}
670 671 672 673 674 675

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

O
Olof Johansson 已提交
676
	for (i = 0; i < olen; i++) {
677
		struct node *node = tnode_get_child(oldtnode, i);
O
Olof Johansson 已提交
678 679
		struct tnode *left, *right;
		int size, j;
680

681 682 683 684 685 686
		/* An empty child */
		if (node == NULL)
			continue;

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

687
		if (IS_LEAF(node) || ((struct tnode *) node)->pos >
688
		   tn->pos + tn->bits - 1) {
689
			if (tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits,
690 691 692 693 694 695 696 697 698 699 700 701 702 703 704
					     1) == 0)
				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 已提交
705
			continue;
706 707
		}

O
Olof Johansson 已提交
708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725
		/* 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)
		 */
726

O
Olof Johansson 已提交
727 728 729
		/* Use the old key, but set the new significant
		 *   bit to zero.
		 */
730

O
Olof Johansson 已提交
731 732
		left = (struct tnode *) tnode_get_child(tn, 2*i);
		put_child(t, tn, 2*i, NULL);
733

O
Olof Johansson 已提交
734
		BUG_ON(!left);
735

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

O
Olof Johansson 已提交
739
		BUG_ON(!right);
740

O
Olof Johansson 已提交
741 742 743 744
		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]);
745
		}
O
Olof Johansson 已提交
746 747 748 749
		put_child(t, tn, 2*i, resize(t, left));
		put_child(t, tn, 2*i+1, resize(t, right));

		tnode_free(inode);
750 751 752
	}
	tnode_free(oldtnode);
	return tn;
753 754 755 756 757
nomem:
	{
		int size = tnode_child_length(tn);
		int j;

S
Stephen Hemminger 已提交
758
		for (j = 0; j < size; j++)
759 760 761 762
			if (tn->child[j])
				tnode_free((struct tnode *)tn->child[j]);

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

764 765
		return ERR_PTR(-ENOMEM);
	}
766 767
}

768
static struct tnode *halve(struct trie *t, struct tnode *tn)
769 770 771 772 773 774
{
	struct tnode *oldtnode = tn;
	struct node *left, *right;
	int i;
	int olen = tnode_child_length(tn);

S
Stephen Hemminger 已提交
775
	pr_debug("In halve\n");
776 777

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

779 780
	if (!tn)
		return ERR_PTR(-ENOMEM);
781 782

	/*
783 784 785
	 * 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
786 787 788
	 * of tnode is ignored.
	 */

O
Olof Johansson 已提交
789
	for (i = 0; i < olen; i += 2) {
790 791
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
792

793
		/* Two nonempty children */
S
Stephen Hemminger 已提交
794
		if (left && right) {
795
			struct tnode *newn;
S
Stephen Hemminger 已提交
796

797
			newn = tnode_new(left->key, tn->pos + tn->bits, 1);
S
Stephen Hemminger 已提交
798 799

			if (!newn)
800
				goto nomem;
S
Stephen Hemminger 已提交
801

802
			put_child(t, tn, i/2, (struct node *)newn);
803 804 805
		}

	}
806

O
Olof Johansson 已提交
807 808 809
	for (i = 0; i < olen; i += 2) {
		struct tnode *newBinNode;

810 811
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
812

813 814 815 816 817
		/* 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 已提交
818
			continue;
S
Stephen Hemminger 已提交
819
		}
O
Olof Johansson 已提交
820 821

		if (right == NULL) {
822
			put_child(t, tn, i/2, left);
O
Olof Johansson 已提交
823 824
			continue;
		}
825

826
		/* Two nonempty children */
O
Olof Johansson 已提交
827 828 829 830 831
		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));
832 833 834
	}
	tnode_free(oldtnode);
	return tn;
835 836 837 838 839
nomem:
	{
		int size = tnode_child_length(tn);
		int j;

S
Stephen Hemminger 已提交
840
		for (j = 0; j < size; j++)
841 842 843 844
			if (tn->child[j])
				tnode_free((struct tnode *)tn->child[j]);

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

846 847
		return ERR_PTR(-ENOMEM);
	}
848 849
}

O
Olof Johansson 已提交
850
static void trie_init(struct trie *t)
851
{
O
Olof Johansson 已提交
852 853 854 855
	if (!t)
		return;

	t->size = 0;
R
Robert Olsson 已提交
856
	rcu_assign_pointer(t->trie, NULL);
O
Olof Johansson 已提交
857
	t->revision = 0;
858
#ifdef CONFIG_IP_FIB_TRIE_STATS
O
Olof Johansson 已提交
859
	memset(&t->stats, 0, sizeof(struct trie_use_stats));
860 861 862
#endif
}

R
Robert Olsson 已提交
863
/* readside must use rcu_read_lock currently dump routines
R
Robert Olsson 已提交
864 865
 via get_fa_head and dump */

R
Robert Olsson 已提交
866
static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
867
{
R
Robert Olsson 已提交
868
	struct hlist_head *head = &l->list;
869 870 871
	struct hlist_node *node;
	struct leaf_info *li;

R
Robert Olsson 已提交
872
	hlist_for_each_entry_rcu(li, node, head, hlist)
873
		if (li->plen == plen)
874
			return li;
O
Olof Johansson 已提交
875

876 877 878 879 880
	return NULL;
}

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

O
Olof Johansson 已提交
883 884
	if (!li)
		return NULL;
885

O
Olof Johansson 已提交
886
	return &li->falh;
887 888 889 890
}

static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
{
891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907
	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);
	}
908 909
}

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

912 913 914 915 916 917 918 919
static struct leaf *
fib_find_node(struct trie *t, u32 key)
{
	int pos;
	struct tnode *tn;
	struct node *n;

	pos = 0;
R
Robert Olsson 已提交
920
	n = rcu_dereference(t->trie);
921 922 923

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

925
		check_tnode(tn);
O
Olof Johansson 已提交
926

927
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
O
Olof Johansson 已提交
928
			pos = tn->pos + tn->bits;
929
			n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
O
Olof Johansson 已提交
930
		} else
931 932 933 934
			break;
	}
	/* Case we have found a leaf. Compare prefixes */

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

938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955
	return NULL;
}

static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
{
	int wasfull;
	t_key cindex, key;
	struct tnode *tp = NULL;

	key = tn->key;

	while (tn != NULL && NODE_PARENT(tn) != NULL) {

		tp = NODE_PARENT(tn);
		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
		wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
		tn = (struct tnode *) resize (t, (struct tnode *)tn);
		tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull);
O
Olof Johansson 已提交
956

957
		if (!NODE_PARENT(tn))
958 959 960 961 962
			break;

		tn = NODE_PARENT(tn);
	}
	/* Handle last (top) tnode */
963
	if (IS_TNODE(tn))
964 965 966 967 968
		tn = (struct tnode*) resize(t, (struct tnode *)tn);

	return (struct node*) tn;
}

R
Robert Olsson 已提交
969 970
/* only used from updater-side */

971 972
static  struct list_head *
fib_insert_node(struct trie *t, int *err, u32 key, int plen)
973 974 975 976 977 978
{
	int pos, newpos;
	struct tnode *tp = NULL, *tn = NULL;
	struct node *n;
	struct leaf *l;
	int missbit;
979
	struct list_head *fa_head = NULL;
980 981 982 983
	struct leaf_info *li;
	t_key cindex;

	pos = 0;
984
	n = t->trie;
985

986 987
	/* 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,
988
	 * and we should just put our new leaf in that.
989 990
	 * 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
991 992
	 * not be the parent's 'pos'+'bits'!
	 *
993
	 * If it does match the current key, get pos/bits from it, extract
994 995 996 997
	 * 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.
	 *
998 999 1000
	 * 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.
1001 1002 1003 1004 1005
	 * 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 已提交
1006

1007
		check_tnode(tn);
O
Olof Johansson 已提交
1008

1009
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1010
			tp = tn;
O
Olof Johansson 已提交
1011
			pos = tn->pos + tn->bits;
1012 1013
			n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));

S
Stephen Hemminger 已提交
1014
			BUG_ON(n && NODE_PARENT(n) != tn);
O
Olof Johansson 已提交
1015
		} else
1016 1017 1018 1019 1020 1021
			break;
	}

	/*
	 * n  ----> NULL, LEAF or TNODE
	 *
1022
	 * tp is n's (parent) ----> NULL or TNODE
1023 1024
	 */

O
Olof Johansson 已提交
1025
	BUG_ON(tp && IS_LEAF(tp));
1026 1027 1028

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

1029
	if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
O
Olof Johansson 已提交
1030 1031
		struct leaf *l = (struct leaf *) n;

1032
		li = leaf_info_new(plen);
O
Olof Johansson 已提交
1033

1034
		if (!li) {
1035 1036 1037
			*err = -ENOMEM;
			goto err;
		}
1038 1039 1040 1041 1042 1043 1044 1045

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

1046
	if (!l) {
1047 1048 1049
		*err = -ENOMEM;
		goto err;
	}
1050 1051 1052 1053

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

1054
	if (!li) {
1055 1056 1057 1058
		tnode_free((struct tnode *) l);
		*err = -ENOMEM;
		goto err;
	}
1059 1060 1061 1062 1063

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

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

		NODE_SET_PARENT(l, tp);

O
Olof Johansson 已提交
1068 1069 1070 1071
		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. */
1072 1073
		/*
		 *  Add a new tnode here
1074 1075 1076 1077
		 *  first tnode need some special handling
		 */

		if (tp)
O
Olof Johansson 已提交
1078
			pos = tp->pos+tp->bits;
1079
		else
O
Olof Johansson 已提交
1080 1081
			pos = 0;

1082
		if (n) {
1083 1084
			newpos = tkey_mismatch(key, pos, n->key);
			tn = tnode_new(n->key, newpos, 1);
O
Olof Johansson 已提交
1085
		} else {
1086
			newpos = 0;
1087
			tn = tnode_new(key, newpos, 1); /* First tnode */
1088 1089
		}

1090
		if (!tn) {
1091 1092 1093 1094
			free_leaf_info(li);
			tnode_free((struct tnode *) l);
			*err = -ENOMEM;
			goto err;
O
Olof Johansson 已提交
1095 1096
		}

1097 1098
		NODE_SET_PARENT(tn, tp);

O
Olof Johansson 已提交
1099
		missbit = tkey_extract_bits(key, newpos, 1);
1100 1101 1102
		put_child(t, tn, missbit, (struct node *)l);
		put_child(t, tn, 1-missbit, n);

1103
		if (tp) {
1104 1105
			cindex = tkey_extract_bits(key, tp->pos, tp->bits);
			put_child(t, (struct tnode *)tp, cindex, (struct node *)tn);
O
Olof Johansson 已提交
1106
		} else {
R
Robert Olsson 已提交
1107
			rcu_assign_pointer(t->trie, (struct node *)tn); /* First tnode */
1108 1109 1110
			tp = tn;
		}
	}
O
Olof Johansson 已提交
1111 1112

	if (tp && tp->pos + tp->bits > 32)
S
Stephen Hemminger 已提交
1113
		printk(KERN_WARNING "fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1114
		       tp, tp->pos, tp->bits, key, plen);
O
Olof Johansson 已提交
1115

1116
	/* Rebalance the trie */
R
Robert Olsson 已提交
1117 1118

	rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
1119 1120
done:
	t->revision++;
O
Olof Johansson 已提交
1121
err:
1122 1123 1124
	return fa_head;
}

1125 1126 1127
/*
 * Caller must hold RTNL.
 */
1128
static int fn_trie_insert(struct fib_table *tb, struct fib_config *cfg)
1129 1130 1131
{
	struct trie *t = (struct trie *) tb->tb_data;
	struct fib_alias *fa, *new_fa;
1132
	struct list_head *fa_head = NULL;
1133
	struct fib_info *fi;
1134 1135
	int plen = cfg->fc_dst_len;
	u8 tos = cfg->fc_tos;
1136 1137 1138 1139 1140 1141 1142
	u32 key, mask;
	int err;
	struct leaf *l;

	if (plen > 32)
		return -EINVAL;

1143
	key = ntohl(cfg->fc_dst);
1144

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

O
Olof Johansson 已提交
1147
	mask = ntohl(inet_make_mask(plen));
1148

1149
	if (key & ~mask)
1150 1151 1152 1153
		return -EINVAL;

	key = key & mask;

1154 1155 1156
	fi = fib_create_info(cfg);
	if (IS_ERR(fi)) {
		err = PTR_ERR(fi);
1157
		goto err;
1158
	}
1159 1160

	l = fib_find_node(t, key);
1161
	fa = NULL;
1162

1163
	if (l) {
1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178
		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 已提交
1179
	if (fa && fa->fa_info->fib_priority == fi->fib_priority) {
1180 1181 1182
		struct fib_alias *fa_orig;

		err = -EEXIST;
1183
		if (cfg->fc_nlflags & NLM_F_EXCL)
1184 1185
			goto out;

1186
		if (cfg->fc_nlflags & NLM_F_REPLACE) {
1187 1188 1189
			struct fib_info *fi_drop;
			u8 state;

R
Robert Olsson 已提交
1190
			err = -ENOBUFS;
1191
			new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
R
Robert Olsson 已提交
1192 1193
			if (new_fa == NULL)
				goto out;
1194 1195

			fi_drop = fa->fa_info;
R
Robert Olsson 已提交
1196 1197
			new_fa->fa_tos = fa->fa_tos;
			new_fa->fa_info = fi;
1198 1199
			new_fa->fa_type = cfg->fc_type;
			new_fa->fa_scope = cfg->fc_scope;
1200
			state = fa->fa_state;
R
Robert Olsson 已提交
1201
			new_fa->fa_state &= ~FA_S_ACCESSED;
1202

R
Robert Olsson 已提交
1203 1204
			list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
			alias_free_mem_rcu(fa);
1205 1206 1207

			fib_release_info(fi_drop);
			if (state & FA_S_ACCESSED)
O
Olof Johansson 已提交
1208
				rt_cache_flush(-1);
1209

O
Olof Johansson 已提交
1210
			goto succeeded;
1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221
		}
		/* 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;
1222 1223
			if (fa->fa_type == cfg->fc_type &&
			    fa->fa_scope == cfg->fc_scope &&
1224 1225 1226 1227
			    fa->fa_info == fi) {
				goto out;
			}
		}
1228
		if (!(cfg->fc_nlflags & NLM_F_APPEND))
1229 1230 1231
			fa = fa_orig;
	}
	err = -ENOENT;
1232
	if (!(cfg->fc_nlflags & NLM_F_CREATE))
1233 1234 1235
		goto out;

	err = -ENOBUFS;
1236
	new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1237 1238 1239 1240 1241
	if (new_fa == NULL)
		goto out;

	new_fa->fa_info = fi;
	new_fa->fa_tos = tos;
1242 1243
	new_fa->fa_type = cfg->fc_type;
	new_fa->fa_scope = cfg->fc_scope;
1244 1245 1246 1247 1248
	new_fa->fa_state = 0;
	/*
	 * Insert new entry to the list.
	 */

1249
	if (!fa_head) {
1250
		err = 0;
1251
		fa_head = fib_insert_node(t, &err, key, plen);
1252
		if (err)
1253 1254
			goto out_free_new_fa;
	}
1255

R
Robert Olsson 已提交
1256 1257
	list_add_tail_rcu(&new_fa->fa_list,
			  (fa ? &fa->fa_list : fa_head));
1258 1259

	rt_cache_flush(-1);
1260 1261
	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
		  &cfg->fc_nlinfo);
1262 1263
succeeded:
	return 0;
1264 1265 1266

out_free_new_fa:
	kmem_cache_free(fn_alias_kmem, new_fa);
1267 1268
out:
	fib_release_info(fi);
O
Olof Johansson 已提交
1269
err:
1270 1271 1272
	return err;
}

R
Robert Olsson 已提交
1273

R
Robert Olsson 已提交
1274
/* should be called with rcu_read_lock */
S
Stephen Hemminger 已提交
1275 1276
static inline int check_leaf(struct trie *t, struct leaf *l,
			     t_key key, int *plen, const struct flowi *flp,
1277
			     struct fib_result *res)
1278
{
1279
	int err, i;
1280
	__be32 mask;
1281 1282 1283
	struct leaf_info *li;
	struct hlist_head *hhead = &l->list;
	struct hlist_node *node;
1284

R
Robert Olsson 已提交
1285
	hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1286
		i = li->plen;
1287 1288
		mask = inet_make_mask(i);
		if (l->key != (key & ntohl(mask)))
1289 1290
			continue;

1291
		if ((err = fib_semantic_match(&li->falh, flp, res, htonl(l->key), mask, i)) <= 0) {
1292 1293 1294 1295
			*plen = i;
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.semantic_match_passed++;
#endif
1296
			return err;
1297 1298 1299 1300 1301
		}
#ifdef CONFIG_IP_FIB_TRIE_STATS
		t->stats.semantic_match_miss++;
#endif
	}
1302
	return 1;
1303 1304 1305 1306 1307 1308 1309 1310 1311 1312
}

static int
fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
{
	struct trie *t = (struct trie *) tb->tb_data;
	int plen, ret = 0;
	struct node *n;
	struct tnode *pn;
	int pos, bits;
O
Olof Johansson 已提交
1313
	t_key key = ntohl(flp->fl4_dst);
1314 1315 1316
	int chopped_off;
	t_key cindex = 0;
	int current_prefix_length = KEYLENGTH;
O
Olof Johansson 已提交
1317 1318 1319 1320
	struct tnode *cn;
	t_key node_prefix, key_prefix, pref_mismatch;
	int mp;

R
Robert Olsson 已提交
1321
	rcu_read_lock();
O
Olof Johansson 已提交
1322

R
Robert Olsson 已提交
1323
	n = rcu_dereference(t->trie);
1324
	if (!n)
1325 1326 1327 1328 1329 1330 1331 1332
		goto failed;

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

	/* Just a leaf? */
	if (IS_LEAF(n)) {
1333
		if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
1334 1335 1336 1337 1338
			goto found;
		goto failed;
	}
	pn = (struct tnode *) n;
	chopped_off = 0;
1339

O
Olof Johansson 已提交
1340
	while (pn) {
1341 1342 1343
		pos = pn->pos;
		bits = pn->bits;

1344
		if (!chopped_off)
1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355
			cindex = tkey_extract_bits(MASK_PFX(key, current_prefix_length), pos, bits);

		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 已提交
1356 1357 1358 1359 1360 1361 1362
		if (IS_LEAF(n)) {
			if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
				goto found;
			else
				goto backtrace;
		}

1363 1364
#define HL_OPTIMIZE
#ifdef HL_OPTIMIZE
O
Olof Johansson 已提交
1365
		cn = (struct tnode *)n;
1366

O
Olof Johansson 已提交
1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381
		/*
		 * 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].
		 */
1382

O
Olof Johansson 已提交
1383 1384 1385 1386 1387 1388 1389 1390 1391
		/* 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.
		 */
1392

O
Olof Johansson 已提交
1393
		/* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */
1394

O
Olof Johansson 已提交
1395 1396 1397 1398 1399 1400
		if (current_prefix_length < pos+bits) {
			if (tkey_extract_bits(cn->key, current_prefix_length,
						cn->pos - current_prefix_length) != 0 ||
			    !(cn->child[0]))
				goto backtrace;
		}
1401

O
Olof Johansson 已提交
1402 1403 1404 1405 1406 1407 1408 1409 1410
		/*
		 * 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.
		 */
1411

O
Olof Johansson 已提交
1412 1413 1414 1415 1416 1417 1418 1419
		/* 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.
		 */
1420

O
Olof Johansson 已提交
1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450
		/* 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.
		 */

		node_prefix = MASK_PFX(cn->key, cn->pos);
		key_prefix = MASK_PFX(key, cn->pos);
		pref_mismatch = key_prefix^node_prefix;
		mp = 0;

		/* In short: If skipped bits in this node do not match the search
		 * key, enter the "prefix matching" state.directly.
		 */
		if (pref_mismatch) {
			while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
				mp++;
				pref_mismatch = pref_mismatch <<1;
			}
			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;
1451
		}
O
Olof Johansson 已提交
1452 1453 1454 1455 1456
#endif
		pn = (struct tnode *)n; /* Descend */
		chopped_off = 0;
		continue;

1457 1458 1459 1460
backtrace:
		chopped_off++;

		/* As zero don't change the child key (cindex) */
O
Olof Johansson 已提交
1461
		while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1))))
1462 1463 1464 1465 1466
			chopped_off++;

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

1468
		/*
1469
		 * Either we do the actual chop off according or if we have
1470 1471 1472
		 * chopped off all bits in this tnode walk up to our parent.
		 */

O
Olof Johansson 已提交
1473
		if (chopped_off <= pn->bits) {
1474
			cindex &= ~(1 << (chopped_off-1));
O
Olof Johansson 已提交
1475
		} else {
1476
			if (NODE_PARENT(pn) == NULL)
1477
				goto failed;
O
Olof Johansson 已提交
1478

1479 1480 1481 1482 1483 1484 1485 1486 1487
			/* Get Child's index */
			cindex = tkey_extract_bits(pn->key, NODE_PARENT(pn)->pos, NODE_PARENT(pn)->bits);
			pn = NODE_PARENT(pn);
			chopped_off = 0;

#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.backtrack++;
#endif
			goto backtrace;
1488
		}
1489 1490
	}
failed:
1491
	ret = 1;
1492
found:
R
Robert Olsson 已提交
1493
	rcu_read_unlock();
1494 1495 1496
	return ret;
}

R
Robert Olsson 已提交
1497
/* only called from updater side */
1498 1499 1500 1501 1502 1503 1504
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 已提交
1505
	pr_debug("entering trie_leaf_remove(%p)\n", n);
1506 1507

	/* Note that in the case skipped bits, those bits are *not* checked!
1508
	 * When we finish this, we will have NULL or a T_LEAF, and the
1509 1510 1511
	 * T_LEAF may or may not match our key.
	 */

O
Olof Johansson 已提交
1512
	while (n != NULL && IS_TNODE(n)) {
1513 1514 1515 1516
		struct tnode *tn = (struct tnode *) n;
		check_tnode(tn);
		n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits));

S
Stephen Hemminger 已提交
1517
		BUG_ON(n && NODE_PARENT(n) != tn);
O
Olof Johansson 已提交
1518
	}
1519 1520
	l = (struct leaf *) n;

1521
	if (!n || !tkey_equals(l->key, key))
1522
		return 0;
1523 1524 1525 1526

	/*
	 * Key found.
	 * Remove the leaf and rebalance the tree
1527 1528 1529 1530 1531 1532 1533 1534
	 */

	t->revision++;
	t->size--;

	tp = NODE_PARENT(n);
	tnode_free((struct tnode *) n);

1535
	if (tp) {
1536 1537
		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
		put_child(t, (struct tnode *)tp, cindex, NULL);
R
Robert Olsson 已提交
1538
		rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
O
Olof Johansson 已提交
1539
	} else
R
Robert Olsson 已提交
1540
		rcu_assign_pointer(t->trie, NULL);
1541 1542 1543 1544

	return 1;
}

1545 1546 1547
/*
 * Caller must hold RTNL.
 */
1548
static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
1549 1550 1551
{
	struct trie *t = (struct trie *) tb->tb_data;
	u32 key, mask;
1552 1553
	int plen = cfg->fc_dst_len;
	u8 tos = cfg->fc_tos;
1554 1555 1556
	struct fib_alias *fa, *fa_to_delete;
	struct list_head *fa_head;
	struct leaf *l;
O
Olof Johansson 已提交
1557 1558
	struct leaf_info *li;

1559
	if (plen > 32)
1560 1561
		return -EINVAL;

1562
	key = ntohl(cfg->fc_dst);
O
Olof Johansson 已提交
1563
	mask = ntohl(inet_make_mask(plen));
1564

1565
	if (key & ~mask)
1566 1567 1568 1569 1570
		return -EINVAL;

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

1571
	if (!l)
1572 1573 1574 1575 1576 1577 1578 1579
		return -ESRCH;

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

	if (!fa)
		return -ESRCH;

S
Stephen Hemminger 已提交
1580
	pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1581 1582 1583

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

1585 1586 1587 1588 1589 1590
	list_for_each_entry(fa, fa_head, fa_list) {
		struct fib_info *fi = fa->fa_info;

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

1591 1592 1593 1594 1595 1596
		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) {
1597 1598 1599 1600 1601
			fa_to_delete = fa;
			break;
		}
	}

O
Olof Johansson 已提交
1602 1603
	if (!fa_to_delete)
		return -ESRCH;
1604

O
Olof Johansson 已提交
1605
	fa = fa_to_delete;
1606 1607
	rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
		  &cfg->fc_nlinfo);
O
Olof Johansson 已提交
1608 1609

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

R
Robert Olsson 已提交
1612
	list_del_rcu(&fa->fa_list);
1613

O
Olof Johansson 已提交
1614
	if (list_empty(fa_head)) {
R
Robert Olsson 已提交
1615
		hlist_del_rcu(&li->hlist);
O
Olof Johansson 已提交
1616
		free_leaf_info(li);
R
Robert Olsson 已提交
1617
	}
1618

O
Olof Johansson 已提交
1619 1620
	if (hlist_empty(&l->list))
		trie_leaf_remove(t, key);
1621

O
Olof Johansson 已提交
1622 1623
	if (fa->fa_state & FA_S_ACCESSED)
		rt_cache_flush(-1);
1624

R
Robert Olsson 已提交
1625 1626
	fib_release_info(fa->fa_info);
	alias_free_mem_rcu(fa);
O
Olof Johansson 已提交
1627
	return 0;
1628 1629 1630 1631 1632 1633 1634 1635 1636 1637
}

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 已提交
1638 1639 1640 1641
		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);
1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658
			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 已提交
1659
			hlist_del_rcu(&li->hlist);
1660 1661 1662 1663 1664 1665
			free_leaf_info(li);
		}
	}
	return found;
}

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

1668 1669 1670 1671 1672
static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
{
	struct node *c = (struct node *) thisleaf;
	struct tnode *p;
	int idx;
R
Robert Olsson 已提交
1673
	struct node *trie = rcu_dereference(t->trie);
1674

1675
	if (c == NULL) {
R
Robert Olsson 已提交
1676
		if (trie == NULL)
1677 1678
			return NULL;

R
Robert Olsson 已提交
1679 1680
		if (IS_LEAF(trie))          /* trie w. just a leaf */
			return (struct leaf *) trie;
1681

R
Robert Olsson 已提交
1682
		p = (struct tnode*) trie;  /* Start */
O
Olof Johansson 已提交
1683
	} else
1684
		p = (struct tnode *) NODE_PARENT(c);
1685

1686 1687 1688 1689
	while (p) {
		int pos, last;

		/*  Find the next child of the parent */
1690 1691 1692
		if (c)
			pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits);
		else
1693 1694 1695
			pos = 0;

		last = 1 << p->bits;
O
Olof Johansson 已提交
1696
		for (idx = pos; idx < last ; idx++) {
R
Robert Olsson 已提交
1697 1698 1699
			c = rcu_dereference(p->child[idx]);

			if (!c)
O
Olof Johansson 已提交
1700 1701 1702
				continue;

			/* Decend if tnode */
R
Robert Olsson 已提交
1703 1704
			while (IS_TNODE(c)) {
				p = (struct tnode *) c;
1705
				idx = 0;
O
Olof Johansson 已提交
1706 1707 1708

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

				/* Done with this tnode? */
R
Robert Olsson 已提交
1713
				if (idx >= (1 << p->bits) || !c)
O
Olof Johansson 已提交
1714
					goto up;
1715
			}
R
Robert Olsson 已提交
1716
			return (struct leaf *) c;
1717 1718 1719
		}
up:
		/* No more children go up one step  */
O
Olof Johansson 已提交
1720
		c = (struct node *) p;
1721 1722 1723 1724 1725
		p = (struct tnode *) NODE_PARENT(p);
	}
	return NULL; /* Ready. Root of trie */
}

1726 1727 1728
/*
 * Caller must hold RTNL.
 */
1729 1730 1731 1732 1733 1734 1735 1736
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;

	t->revision++;

O
Olof Johansson 已提交
1737
	for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1738 1739 1740 1741 1742 1743 1744 1745 1746 1747
		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 已提交
1748
	pr_debug("trie_flush found=%d\n", found);
1749 1750 1751
	return found;
}

O
Olof Johansson 已提交
1752
static int trie_last_dflt = -1;
1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768

static void
fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
{
	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 已提交
1769
	rcu_read_lock();
1770

1771
	l = fib_find_node(t, 0);
1772
	if (!l)
1773 1774 1775
		goto out;

	fa_head = get_fa_head(l, 0);
1776
	if (!fa_head)
1777 1778
		goto out;

1779
	if (list_empty(fa_head))
1780 1781
		goto out;

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

1785 1786 1787
		if (fa->fa_scope != res->scope ||
		    fa->fa_type != RTN_UNICAST)
			continue;
O
Olof Johansson 已提交
1788

1789 1790 1791 1792 1793 1794
		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 已提交
1795

1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832
		if (fi == NULL) {
			if (next_fi != res->fi)
				break;
		} else if (!fib_detect_death(fi, order, &last_resort,
					     &last_idx, &trie_last_dflt)) {
			if (res->fi)
				fib_info_put(res->fi);
			res->fi = fi;
			atomic_inc(&fi->fib_clntref);
			trie_last_dflt = order;
			goto out;
		}
		fi = next_fi;
		order++;
	}
	if (order <= 0 || fi == NULL) {
		trie_last_dflt = -1;
		goto out;
	}

	if (!fib_detect_death(fi, order, &last_resort, &last_idx, &trie_last_dflt)) {
		if (res->fi)
			fib_info_put(res->fi);
		res->fi = fi;
		atomic_inc(&fi->fib_clntref);
		trie_last_dflt = order;
		goto out;
	}
	if (last_idx >= 0) {
		if (res->fi)
			fib_info_put(res->fi);
		res->fi = last_resort;
		if (last_resort)
			atomic_inc(&last_resort->fib_clntref);
	}
	trie_last_dflt = last_idx;
 out:;
R
Robert Olsson 已提交
1833
	rcu_read_unlock();
1834 1835
}

1836
static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fib_table *tb,
1837 1838 1839 1840 1841
			   struct sk_buff *skb, struct netlink_callback *cb)
{
	int i, s_i;
	struct fib_alias *fa;

A
Al Viro 已提交
1842
	__be32 xkey = htonl(key);
1843

1844
	s_i = cb->args[4];
1845 1846
	i = 0;

R
Robert Olsson 已提交
1847 1848 1849
	/* rcu_read_lock is hold by caller */

	list_for_each_entry_rcu(fa, fah, fa_list) {
1850 1851 1852 1853
		if (i < s_i) {
			i++;
			continue;
		}
S
Stephen Hemminger 已提交
1854
		BUG_ON(!fa->fa_info);
1855 1856 1857 1858 1859 1860 1861

		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,
1862
				  xkey,
1863 1864
				  plen,
				  fa->fa_tos,
1865
				  fa->fa_info, 0) < 0) {
1866
			cb->args[4] = i;
1867
			return -1;
O
Olof Johansson 已提交
1868
		}
1869 1870
		i++;
	}
1871
	cb->args[4] = i;
1872 1873 1874
	return skb->len;
}

1875
static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb,
1876 1877 1878 1879 1880 1881
			     struct netlink_callback *cb)
{
	int h, s_h;
	struct list_head *fa_head;
	struct leaf *l = NULL;

1882
	s_h = cb->args[3];
1883

O
Olof Johansson 已提交
1884
	for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1885 1886 1887
		if (h < s_h)
			continue;
		if (h > s_h)
1888 1889
			memset(&cb->args[4], 0,
			       sizeof(cb->args) - 4*sizeof(cb->args[0]));
1890 1891

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

1893
		if (!fa_head)
1894 1895
			continue;

1896
		if (list_empty(fa_head))
1897 1898 1899
			continue;

		if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
1900
			cb->args[3] = h;
1901 1902 1903
			return -1;
		}
	}
1904
	cb->args[3] = h;
1905 1906 1907 1908 1909 1910 1911 1912
	return skb->len;
}

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

1913
	s_m = cb->args[2];
1914

R
Robert Olsson 已提交
1915
	rcu_read_lock();
O
Olof Johansson 已提交
1916
	for (m = 0; m <= 32; m++) {
1917 1918 1919
		if (m < s_m)
			continue;
		if (m > s_m)
1920 1921
			memset(&cb->args[3], 0,
				sizeof(cb->args) - 3*sizeof(cb->args[0]));
1922 1923

		if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) {
1924
			cb->args[2] = m;
1925 1926 1927
			goto out;
		}
	}
R
Robert Olsson 已提交
1928
	rcu_read_unlock();
1929
	cb->args[2] = m;
1930
	return skb->len;
O
Olof Johansson 已提交
1931
out:
R
Robert Olsson 已提交
1932
	rcu_read_unlock();
1933 1934 1935 1936 1937 1938
	return -1;
}

/* Fix more generic FIB names for init later */

#ifdef CONFIG_IP_MULTIPLE_TABLES
1939
struct fib_table * fib_hash_init(u32 id)
1940
#else
1941
struct fib_table * __init fib_hash_init(u32 id)
1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970
#endif
{
	struct fib_table *tb;
	struct trie *t;

	if (fn_alias_kmem == NULL)
		fn_alias_kmem = kmem_cache_create("ip_fib_alias",
						  sizeof(struct fib_alias),
						  0, SLAB_HWCACHE_ALIGN,
						  NULL, NULL);

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

	tb->tb_id = id;
	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;
	memset(tb->tb_data, 0, sizeof(struct trie));

	t = (struct trie *) tb->tb_data;

	trie_init(t);

1971
	if (id == RT_TABLE_LOCAL)
O
Olof Johansson 已提交
1972
		trie_local = t;
1973
	else if (id == RT_TABLE_MAIN)
O
Olof Johansson 已提交
1974
		trie_main = t;
1975 1976

	if (id == RT_TABLE_LOCAL)
S
Stephen Hemminger 已提交
1977
		printk(KERN_INFO "IPv4 FIB: Using LC-trie version %s\n", VERSION);
1978 1979 1980 1981

	return tb;
}

1982 1983 1984 1985 1986 1987 1988 1989
#ifdef CONFIG_PROC_FS
/* Depth first Trie walk iterator */
struct fib_trie_iter {
	struct tnode *tnode;
	struct trie *trie;
	unsigned index;
	unsigned depth;
};
1990

1991
static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
1992
{
1993 1994 1995
	struct tnode *tn = iter->tnode;
	unsigned cindex = iter->index;
	struct tnode *p;
1996

1997 1998 1999 2000
	/* A single entry routing table */
	if (!tn)
		return NULL;

2001 2002 2003 2004 2005
	pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
		 iter->tnode, iter->index, iter->depth);
rescan:
	while (cindex < (1<<tn->bits)) {
		struct node *n = tnode_get_child(tn, cindex);
2006

2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018
		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;
		}
2019

2020 2021
		++cindex;
	}
O
Olof Johansson 已提交
2022

2023 2024 2025 2026 2027 2028 2029
	/* Current node exhausted, pop back up */
	p = NODE_PARENT(tn);
	if (p) {
		cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
		tn = p;
		--iter->depth;
		goto rescan;
2030
	}
2031 2032 2033

	/* got root? */
	return NULL;
2034 2035
}

2036 2037
static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
				       struct trie *t)
2038
{
2039 2040
	struct node *n ;

S
Stephen Hemminger 已提交
2041
	if (!t)
2042 2043 2044 2045
		return NULL;

	n = rcu_dereference(t->trie);

S
Stephen Hemminger 已提交
2046
	if (!iter)
2047
		return NULL;
2048

2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060
	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;
		}
2061
		return n;
O
Olof Johansson 已提交
2062
	}
2063 2064
	return NULL;
}
O
Olof Johansson 已提交
2065

2066 2067 2068 2069
static void trie_collect_stats(struct trie *t, struct trie_stat *s)
{
	struct node *n;
	struct fib_trie_iter iter;
O
Olof Johansson 已提交
2070

2071
	memset(s, 0, sizeof(*s));
O
Olof Johansson 已提交
2072

2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085
	rcu_read_lock();
	for (n = fib_trie_get_first(&iter, t); n;
	     n = fib_trie_get_next(&iter)) {
		if (IS_LEAF(n)) {
			s->leaves++;
			s->totdepth += iter.depth;
			if (iter.depth > s->maxdepth)
				s->maxdepth = iter.depth;
		} else {
			const struct tnode *tn = (const struct tnode *) n;
			int i;

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

2089 2090 2091
			for (i = 0; i < (1<<tn->bits); i++)
				if (!tn->child[i])
					s->nullpointers++;
2092 2093
		}
	}
R
Robert Olsson 已提交
2094
	rcu_read_unlock();
2095 2096
}

2097 2098 2099 2100
/*
 *	This outputs /proc/net/fib_triestats
 */
static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2101
{
2102
	unsigned i, max, pointers, bytes, avdepth;
2103

2104 2105 2106 2107
	if (stat->leaves)
		avdepth = stat->totdepth*100 / stat->leaves;
	else
		avdepth = 0;
O
Olof Johansson 已提交
2108

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

2112
	seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
O
Olof Johansson 已提交
2113

2114 2115 2116
	bytes = sizeof(struct leaf) * stat->leaves;
	seq_printf(seq, "\tInternal nodes: %d\n\t", stat->tnodes);
	bytes += sizeof(struct tnode) * stat->tnodes;
2117

R
Robert Olsson 已提交
2118 2119
	max = MAX_STAT_DEPTH;
	while (max > 0 && stat->nodesizes[max-1] == 0)
2120
		max--;
2121

2122 2123 2124 2125 2126 2127 2128 2129
	pointers = 0;
	for (i = 1; i <= max; i++)
		if (stat->nodesizes[i] != 0) {
			seq_printf(seq, "  %d: %d",  i, stat->nodesizes[i]);
			pointers += (1<<i) * stat->nodesizes[i];
		}
	seq_putc(seq, '\n');
	seq_printf(seq, "\tPointers: %d\n", pointers);
R
Robert Olsson 已提交
2130

2131 2132 2133
	bytes += sizeof(struct node *) * pointers;
	seq_printf(seq, "Null ptrs: %d\n", stat->nullpointers);
	seq_printf(seq, "Total size: %d  kB\n", (bytes + 1023) / 1024);
R
Robert Olsson 已提交
2134

2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147
#ifdef CONFIG_IP_FIB_TRIE_STATS
	seq_printf(seq, "Counters:\n---------\n");
	seq_printf(seq,"gets = %d\n", t->stats.gets);
	seq_printf(seq,"backtracks = %d\n", t->stats.backtrack);
	seq_printf(seq,"semantic match passed = %d\n", t->stats.semantic_match_passed);
	seq_printf(seq,"semantic match miss = %d\n", t->stats.semantic_match_miss);
	seq_printf(seq,"null node hit= %d\n", t->stats.null_node_hit);
	seq_printf(seq,"skipped node resize = %d\n", t->stats.resize_node_skipped);
#ifdef CLEAR_STATS
	memset(&(t->stats), 0, sizeof(t->stats));
#endif
#endif /*  CONFIG_IP_FIB_TRIE_STATS */
}
2148

2149 2150 2151
static int fib_triestat_seq_show(struct seq_file *seq, void *v)
{
	struct trie_stat *stat;
O
Olof Johansson 已提交
2152

2153 2154 2155
	stat = kmalloc(sizeof(*stat), GFP_KERNEL);
	if (!stat)
		return -ENOMEM;
O
Olof Johansson 已提交
2156

2157 2158
	seq_printf(seq, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
		   sizeof(struct leaf), sizeof(struct tnode));
O
Olof Johansson 已提交
2159

2160 2161 2162 2163 2164
	if (trie_local) {
		seq_printf(seq, "Local:\n");
		trie_collect_stats(trie_local, stat);
		trie_show_stats(seq, stat);
	}
O
Olof Johansson 已提交
2165

2166 2167 2168 2169
	if (trie_main) {
		seq_printf(seq, "Main:\n");
		trie_collect_stats(trie_main, stat);
		trie_show_stats(seq, stat);
2170
	}
2171
	kfree(stat);
2172

2173
	return 0;
2174 2175
}

2176
static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2177
{
2178
	return single_open(file, fib_triestat_seq_show, NULL);
2179 2180
}

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

static struct node *fib_trie_get_idx(struct fib_trie_iter *iter,
				      loff_t pos)
2191
{
2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205
	loff_t idx = 0;
	struct node *n;

	for (n = fib_trie_get_first(iter, trie_local);
	     n; ++idx, n = fib_trie_get_next(iter)) {
		if (pos == idx)
			return n;
	}

	for (n = fib_trie_get_first(iter, trie_main);
	     n; ++idx, n = fib_trie_get_next(iter)) {
		if (pos == idx)
			return n;
	}
2206 2207 2208
	return NULL;
}

2209
static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2210
{
2211 2212
	rcu_read_lock();
	if (*pos == 0)
O
Olof Johansson 已提交
2213
		return SEQ_START_TOKEN;
2214
	return fib_trie_get_idx(seq->private, *pos - 1);
2215 2216
}

2217
static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2218
{
2219 2220 2221
	struct fib_trie_iter *iter = seq->private;
	void *l = v;

2222
	++*pos;
O
Olof Johansson 已提交
2223
	if (v == SEQ_START_TOKEN)
2224
		return fib_trie_get_idx(iter, 0);
2225

2226 2227 2228 2229
	v = fib_trie_get_next(iter);
	BUG_ON(v == l);
	if (v)
		return v;
2230

2231 2232 2233
	/* continue scan in next trie */
	if (iter->trie == trie_local)
		return fib_trie_get_first(iter, trie_main);
2234

2235 2236
	return NULL;
}
2237

2238
static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2239
{
2240 2241
	rcu_read_unlock();
}
O
Olof Johansson 已提交
2242

2243 2244 2245 2246
static void seq_indent(struct seq_file *seq, int n)
{
	while (n-- > 0) seq_puts(seq, "   ");
}
2247

2248 2249 2250
static inline const char *rtn_scope(enum rt_scope_t s)
{
	static char buf[32];
2251

S
Stephen Hemminger 已提交
2252
	switch (s) {
2253 2254 2255 2256 2257 2258 2259 2260 2261 2262
	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:
		snprintf(buf, sizeof(buf), "scope=%d", s);
		return buf;
	}
}
2263

2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277
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",
};
2278

2279 2280 2281
static inline const char *rtn_type(unsigned t)
{
	static char buf[32];
2282

2283 2284 2285 2286
	if (t < __RTN_MAX && rtn_type_names[t])
		return rtn_type_names[t];
	snprintf(buf, sizeof(buf), "type %d", t);
	return buf;
2287 2288
}

2289 2290
/* Pretty print the trie */
static int fib_trie_seq_show(struct seq_file *seq, void *v)
2291
{
2292 2293
	const struct fib_trie_iter *iter = seq->private;
	struct node *n = v;
2294

2295 2296
	if (v == SEQ_START_TOKEN)
		return 0;
2297

2298 2299 2300 2301 2302 2303 2304
	if (!NODE_PARENT(n)) {
		if (iter->trie == trie_local)
			seq_puts(seq, "<local>:\n");
		else
			seq_puts(seq, "<main>:\n");
	}

2305 2306
	if (IS_TNODE(n)) {
		struct tnode *tn = (struct tnode *) n;
A
Al Viro 已提交
2307
		__be32 prf = htonl(MASK_PFX(tn->key, tn->pos));
O
Olof Johansson 已提交
2308

2309 2310
		seq_indent(seq, iter->depth-1);
		seq_printf(seq, "  +-- %d.%d.%d.%d/%d %d %d %d\n",
2311
			   NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
2312
			   tn->empty_children);
2313

2314 2315 2316
	} else {
		struct leaf *l = (struct leaf *) n;
		int i;
A
Al Viro 已提交
2317
		__be32 val = htonl(l->key);
2318 2319 2320 2321

		seq_indent(seq, iter->depth);
		seq_printf(seq, "  |-- %d.%d.%d.%d\n", NIPQUAD(val));
		for (i = 32; i >= 0; i--) {
R
Robert Olsson 已提交
2322
			struct leaf_info *li = find_leaf_info(l, i);
2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336
			if (li) {
				struct fib_alias *fa;
				list_for_each_entry_rcu(fa, &li->falh, fa_list) {
					seq_indent(seq, iter->depth+1);
					seq_printf(seq, "  /%d %s %s", i,
						   rtn_scope(fa->fa_scope),
						   rtn_type(fa->fa_type));
					if (fa->fa_tos)
						seq_printf(seq, "tos =%d\n",
							   fa->fa_tos);
					seq_putc(seq, '\n');
				}
			}
		}
2337
	}
2338

2339 2340 2341
	return 0;
}

2342
static const struct seq_operations fib_trie_seq_ops = {
2343 2344 2345 2346
	.start  = fib_trie_seq_start,
	.next   = fib_trie_seq_next,
	.stop   = fib_trie_seq_stop,
	.show   = fib_trie_seq_show,
2347 2348
};

2349
static int fib_trie_seq_open(struct inode *inode, struct file *file)
2350 2351 2352
{
	struct seq_file *seq;
	int rc = -ENOMEM;
2353
	struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
2354

2355 2356 2357 2358
	if (!s)
		goto out;

	rc = seq_open(file, &fib_trie_seq_ops);
2359 2360 2361
	if (rc)
		goto out_kfree;

2362 2363 2364
	seq	     = file->private_data;
	seq->private = s;
	memset(s, 0, sizeof(*s));
2365 2366 2367
out:
	return rc;
out_kfree:
2368
	kfree(s);
2369 2370 2371
	goto out;
}

2372
static const struct file_operations fib_trie_fops = {
2373 2374 2375 2376
	.owner  = THIS_MODULE,
	.open   = fib_trie_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2377
	.release = seq_release_private,
2378 2379
};

A
Al Viro 已提交
2380
static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2381
{
2382 2383 2384 2385
	static unsigned type2flags[RTN_MAX + 1] = {
		[7] = RTF_REJECT, [8] = RTF_REJECT,
	};
	unsigned flags = type2flags[type];
2386

2387 2388
	if (fi && fi->fib_nh->nh_gw)
		flags |= RTF_GATEWAY;
A
Al Viro 已提交
2389
	if (mask == htonl(0xFFFFFFFF))
2390 2391 2392
		flags |= RTF_HOST;
	flags |= RTF_UP;
	return flags;
2393 2394
}

2395 2396 2397 2398 2399 2400 2401
/*
 *	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)
2402
{
2403
	const struct fib_trie_iter *iter = seq->private;
2404 2405 2406
	struct leaf *l = v;
	int i;
	char bf[128];
2407

2408 2409 2410 2411 2412 2413
	if (v == SEQ_START_TOKEN) {
		seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
			   "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
			   "\tWindow\tIRTT");
		return 0;
	}
2414

2415 2416
	if (iter->trie == trie_local)
		return 0;
2417 2418
	if (IS_TNODE(l))
		return 0;
2419

2420
	for (i=32; i>=0; i--) {
R
Robert Olsson 已提交
2421
		struct leaf_info *li = find_leaf_info(l, i);
2422
		struct fib_alias *fa;
A
Al Viro 已提交
2423
		__be32 mask, prefix;
O
Olof Johansson 已提交
2424

2425 2426
		if (!li)
			continue;
2427

2428 2429
		mask = inet_make_mask(li->plen);
		prefix = htonl(l->key);
2430

2431
		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2432
			const struct fib_info *fi = fa->fa_info;
2433
			unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2434

2435 2436 2437
			if (fa->fa_type == RTN_BROADCAST
			    || fa->fa_type == RTN_MULTICAST)
				continue;
2438

2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454
			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,
					 (fi->fib_advmss ? fi->fib_advmss + 40 : 0),
					 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);
2455

2456 2457
			seq_printf(seq, "%-127s\n", bf);
		}
2458 2459 2460 2461 2462
	}

	return 0;
}

2463
static const struct seq_operations fib_route_seq_ops = {
2464 2465 2466 2467
	.start  = fib_trie_seq_start,
	.next   = fib_trie_seq_next,
	.stop   = fib_trie_seq_stop,
	.show   = fib_route_seq_show,
2468 2469
};

2470
static int fib_route_seq_open(struct inode *inode, struct file *file)
2471 2472 2473
{
	struct seq_file *seq;
	int rc = -ENOMEM;
2474
	struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
2475

2476 2477 2478 2479
	if (!s)
		goto out;

	rc = seq_open(file, &fib_route_seq_ops);
2480 2481 2482
	if (rc)
		goto out_kfree;

2483 2484 2485
	seq	     = file->private_data;
	seq->private = s;
	memset(s, 0, sizeof(*s));
2486 2487 2488
out:
	return rc;
out_kfree:
2489
	kfree(s);
2490 2491 2492
	goto out;
}

2493
static const struct file_operations fib_route_fops = {
2494 2495 2496 2497 2498
	.owner  = THIS_MODULE,
	.open   = fib_route_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
	.release = seq_release_private,
2499 2500 2501 2502
};

int __init fib_proc_init(void)
{
2503 2504 2505 2506 2507 2508 2509 2510 2511
	if (!proc_net_fops_create("fib_trie", S_IRUGO, &fib_trie_fops))
		goto out1;

	if (!proc_net_fops_create("fib_triestat", S_IRUGO, &fib_triestat_fops))
		goto out2;

	if (!proc_net_fops_create("route", S_IRUGO, &fib_route_fops))
		goto out3;

2512
	return 0;
2513 2514 2515 2516 2517 2518 2519

out3:
	proc_net_remove("fib_triestat");
out2:
	proc_net_remove("fib_trie");
out1:
	return -ENOMEM;
2520 2521 2522 2523 2524
}

void __init fib_proc_exit(void)
{
	proc_net_remove("fib_trie");
2525 2526
	proc_net_remove("fib_triestat");
	proc_net_remove("route");
2527 2528 2529
}

#endif /* CONFIG_PROC_FS */