fib_trie.c 58.5 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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
/*
 *   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.
 *
 *   Jens Laas <jens.laas@data.slu.se> Swedish University of 
 *     Agricultural Sciences.
 * 
 *   Hans Liss <hans.liss@its.uu.se>  Uppsala Universitet
 *
 * This work is based on the LPC-trie which is originally descibed in:
 * 
 * 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 67

#include <asm/uaccess.h>
#include <asm/system.h>
#include <asm/bitops.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/sched.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 已提交
68
#include <linux/inetdevice.h>
69 70 71
#include <linux/netdevice.h>
#include <linux/if_arp.h>
#include <linux/proc_fs.h>
R
Robert Olsson 已提交
72
#include <linux/rcupdate.h>
73 74 75 76 77 78 79 80 81 82 83 84 85
#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 已提交
86
#define MAX_STAT_DEPTH 32
87 88 89 90 91 92 93 94 95 96

#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 已提交
97
#define NODE_PARENT(node) \
R
Robert Olsson 已提交
98 99 100 101 102 103 104
	((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 已提交
105 106 107

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

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

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

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

struct tnode {
O
Olof Johansson 已提交
129 130 131 132 133 134
	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 已提交
135
	struct rcu_head rcu;
O
Olof Johansson 已提交
136
	struct node *child[0];
137 138 139 140 141 142 143 144 145
};

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

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

struct trie {
O
Olof Johansson 已提交
160
	struct node *trie;
161 162 163
#ifdef CONFIG_IP_FIB_TRIE_STATS
	struct trie_use_stats stats;
#endif
O
Olof Johansson 已提交
164
	int size;
165 166 167 168 169 170
	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);
171 172
static struct tnode *inflate(struct trie *t, struct tnode *tn);
static struct tnode *halve(struct trie *t, struct tnode *tn);
173 174
static void tnode_free(struct tnode *tn);

175
static kmem_cache_t *fn_alias_kmem __read_mostly;
176 177
static struct trie *trie_local = NULL, *trie_main = NULL;

R
Robert Olsson 已提交
178 179 180

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

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

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

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

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

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

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

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

219 220 221
	if (!diff)
		return 0;
	while ((diff << i) >> (KEYLENGTH-1) == 0)
222 223 224 225 226 227 228 229 230 231 232 233
		i++;
	return i;
}

/*
  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 
  all of the bits in that key are significant.

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

  If n is a leaf, every bit in its key is significant. Its presence is 
R
Robert Olsson 已提交
234
  necessitated by path compression, since during a tree traversal (when 
235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263
  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 
  correct key path.

  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 
  call to tkey_sub_equals() in trie_insert().

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

  Example:  
  _________________________________________________________________
  | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
  -----------------------------------------------------------------
    0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15 

  _________________________________________________________________
  | 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 已提交
264
  n->bits = 4
265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282

  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 
  not use them for anything.

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

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

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

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

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

*/

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

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

R
Robert Olsson 已提交
299 300

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

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

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

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

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

326 327
static struct tnode *tnode_alloc(unsigned int size)
{
R
Robert Olsson 已提交
328 329 330 331 332 333 334 335 336 337
	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);
338 339
}

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

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

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

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

382 383 384 385
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 *);
386
	struct tnode *tn = tnode_alloc(sz);
387

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

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

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

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

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

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

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

433 434 435 436 437 438

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

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

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

450 451
	if (n)
		NODE_SET_PARENT(n, tn);
452

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

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

 	if (!tn)
		return NULL;

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

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

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

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

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

	check_tnode(tn);
554

555 556 557 558 559 560 561
	/* Keep root node larger  */

	if(!tn->parent)
		inflate_threshold_use = inflate_threshold_root;
	else 
		inflate_threshold_use = inflate_threshold;

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

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

	check_tnode(tn);

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

585 586 587 588 589 590 591 592

	/* Keep root node larger  */

	if(!tn->parent)
		halve_threshold_use = halve_threshold_root;
	else 
		halve_threshold_use = halve_threshold;

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

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

609

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

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

			/* compress one level */

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

	return (struct node *) tn;
}

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

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

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

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

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

	for (i = 0; i < olen; i++) {
651 652 653 654 655 656 657 658
		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);
659

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

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

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

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

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

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

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

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

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

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

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

O
Olof Johansson 已提交
736
		BUG_ON(!left);
737

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

O
Olof Johansson 已提交
741
		BUG_ON(!right);
742

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

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

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

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

766 767
		return ERR_PTR(-ENOMEM);
	}
768 769
}

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

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

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

781 782
	if (!tn)
		return ERR_PTR(-ENOMEM);
783 784

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

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

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

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

			if (!newn)
802
				goto nomem;
S
Stephen Hemminger 已提交
803

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

	}
808

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

812 813
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
814

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

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

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

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

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

848 849
		return ERR_PTR(-ENOMEM);
	}
850 851
}

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

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

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

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

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

878 879 880 881 882
	return NULL;
}

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

O
Olof Johansson 已提交
885 886
	if (!li)
		return NULL;
887

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

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

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

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

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

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

927
		check_tnode(tn);
O
Olof Johansson 已提交
928

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

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

940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957
	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 已提交
958

959
		if (!NODE_PARENT(tn))
960 961 962 963 964
			break;

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

	return (struct node*) tn;
}

R
Robert Olsson 已提交
971 972
/* only used from updater-side */

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

	pos = 0;
986
	n = t->trie;
987

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

1009
		check_tnode(tn);
O
Olof Johansson 已提交
1010

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

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

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

O
Olof Johansson 已提交
1027
	BUG_ON(tp && IS_LEAF(tp));
1028 1029 1030

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

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

1034
		li = leaf_info_new(plen);
O
Olof Johansson 已提交
1035

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

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

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

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

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

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

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

		NODE_SET_PARENT(l, tp);

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

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

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

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

1099 1100
		NODE_SET_PARENT(tn, tp);

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

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

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

1118
	/* Rebalance the trie */
R
Robert Olsson 已提交
1119 1120

	rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
1121 1122
done:
	t->revision++;
O
Olof Johansson 已提交
1123
err:
1124 1125 1126 1127 1128 1129 1130 1131 1132
	return fa_head;
}

static int
fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
	       struct nlmsghdr *nlhdr, struct netlink_skb_parms *req)
{
	struct trie *t = (struct trie *) tb->tb_data;
	struct fib_alias *fa, *new_fa;
1133
	struct list_head *fa_head = NULL;
1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145
	struct fib_info *fi;
	int plen = r->rtm_dst_len;
	int type = r->rtm_type;
	u8 tos = r->rtm_tos;
	u32 key, mask;
	int err;
	struct leaf *l;

	if (plen > 32)
		return -EINVAL;

	key = 0;
1146
	if (rta->rta_dst)
1147 1148 1149 1150
		memcpy(&key, rta->rta_dst, 4);

	key = ntohl(key);

S
Stephen Hemminger 已提交
1151
	pr_debug("Insert table=%d %08x/%d\n", tb->tb_id, key, plen);
1152

O
Olof Johansson 已提交
1153
	mask = ntohl(inet_make_mask(plen));
1154

1155
	if (key & ~mask)
1156 1157 1158 1159
		return -EINVAL;

	key = key & mask;

O
Olof Johansson 已提交
1160 1161 1162
	fi = fib_create_info(r, rta, nlhdr, &err);

	if (!fi)
1163 1164 1165
		goto err;

	l = fib_find_node(t, key);
1166
	fa = NULL;
1167

1168
	if (l) {
1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183
		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 已提交
1184
	if (fa && fa->fa_info->fib_priority == fi->fib_priority) {
1185 1186 1187 1188 1189 1190 1191 1192 1193 1194
		struct fib_alias *fa_orig;

		err = -EEXIST;
		if (nlhdr->nlmsg_flags & NLM_F_EXCL)
			goto out;

		if (nlhdr->nlmsg_flags & NLM_F_REPLACE) {
			struct fib_info *fi_drop;
			u8 state;

R
Robert Olsson 已提交
1195 1196 1197 1198
			err = -ENOBUFS;
			new_fa = kmem_cache_alloc(fn_alias_kmem, SLAB_KERNEL);
			if (new_fa == NULL)
				goto out;
1199 1200

			fi_drop = fa->fa_info;
R
Robert Olsson 已提交
1201 1202 1203 1204
			new_fa->fa_tos = fa->fa_tos;
			new_fa->fa_info = fi;
			new_fa->fa_type = type;
			new_fa->fa_scope = r->rtm_scope;
1205
			state = fa->fa_state;
R
Robert Olsson 已提交
1206
			new_fa->fa_state &= ~FA_S_ACCESSED;
1207

R
Robert Olsson 已提交
1208 1209
			list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
			alias_free_mem_rcu(fa);
1210 1211 1212

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

O
Olof Johansson 已提交
1215
			goto succeeded;
1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236
		}
		/* 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;
			if (fa->fa_type == type &&
			    fa->fa_scope == r->rtm_scope &&
			    fa->fa_info == fi) {
				goto out;
			}
		}
		if (!(nlhdr->nlmsg_flags & NLM_F_APPEND))
			fa = fa_orig;
	}
	err = -ENOENT;
O
Olof Johansson 已提交
1237
	if (!(nlhdr->nlmsg_flags & NLM_F_CREATE))
1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253
		goto out;

	err = -ENOBUFS;
	new_fa = kmem_cache_alloc(fn_alias_kmem, SLAB_KERNEL);
	if (new_fa == NULL)
		goto out;

	new_fa->fa_info = fi;
	new_fa->fa_tos = tos;
	new_fa->fa_type = type;
	new_fa->fa_scope = r->rtm_scope;
	new_fa->fa_state = 0;
	/*
	 * Insert new entry to the list.
	 */

1254
	if (!fa_head) {
1255
		err = 0;
1256
		fa_head = fib_insert_node(t, &err, key, plen);
1257
		if (err)
1258 1259
			goto out_free_new_fa;
	}
1260

R
Robert Olsson 已提交
1261 1262
	list_add_tail_rcu(&new_fa->fa_list,
			  (fa ? &fa->fa_list : fa_head));
1263 1264 1265 1266 1267

	rt_cache_flush(-1);
	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id, nlhdr, req);
succeeded:
	return 0;
1268 1269 1270

out_free_new_fa:
	kmem_cache_free(fn_alias_kmem, new_fa);
1271 1272
out:
	fib_release_info(fi);
O
Olof Johansson 已提交
1273
err:
1274 1275 1276
	return err;
}

R
Robert Olsson 已提交
1277

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

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

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

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 已提交
1317
	t_key key = ntohl(flp->fl4_dst);
1318 1319 1320
	int chopped_off;
	t_key cindex = 0;
	int current_prefix_length = KEYLENGTH;
O
Olof Johansson 已提交
1321 1322 1323 1324
	struct tnode *cn;
	t_key node_prefix, key_prefix, pref_mismatch;
	int mp;

R
Robert Olsson 已提交
1325
	rcu_read_lock();
O
Olof Johansson 已提交
1326

R
Robert Olsson 已提交
1327
	n = rcu_dereference(t->trie);
1328
	if (!n)
1329 1330 1331 1332 1333 1334 1335 1336
		goto failed;

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

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

O
Olof Johansson 已提交
1344
	while (pn) {
1345 1346 1347
		pos = pn->pos;
		bits = pn->bits;

1348
		if (!chopped_off)
1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359
			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 已提交
1360 1361 1362 1363 1364 1365 1366
		if (IS_LEAF(n)) {
			if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
				goto found;
			else
				goto backtrace;
		}

1367 1368
#define HL_OPTIMIZE
#ifdef HL_OPTIMIZE
O
Olof Johansson 已提交
1369
		cn = (struct tnode *)n;
1370

O
Olof Johansson 已提交
1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385
		/*
		 * 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].
		 */
1386

O
Olof Johansson 已提交
1387 1388 1389 1390 1391 1392 1393 1394 1395
		/* 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.
		 */
1396

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

O
Olof Johansson 已提交
1399 1400 1401 1402 1403 1404
		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;
		}
1405

O
Olof Johansson 已提交
1406 1407 1408 1409 1410 1411 1412 1413 1414
		/*
		 * 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.
		 */
1415

O
Olof Johansson 已提交
1416 1417 1418 1419 1420 1421 1422 1423
		/* 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.
		 */
1424

O
Olof Johansson 已提交
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 1451 1452 1453 1454
		/* 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;
1455
		}
O
Olof Johansson 已提交
1456 1457 1458 1459 1460
#endif
		pn = (struct tnode *)n; /* Descend */
		chopped_off = 0;
		continue;

1461 1462 1463 1464
backtrace:
		chopped_off++;

		/* As zero don't change the child key (cindex) */
O
Olof Johansson 已提交
1465
		while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1))))
1466 1467 1468 1469 1470
			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 已提交
1471

1472
		/*
1473
		 * Either we do the actual chop off according or if we have
1474 1475 1476
		 * chopped off all bits in this tnode walk up to our parent.
		 */

O
Olof Johansson 已提交
1477
		if (chopped_off <= pn->bits) {
1478
			cindex &= ~(1 << (chopped_off-1));
O
Olof Johansson 已提交
1479
		} else {
1480
			if (NODE_PARENT(pn) == NULL)
1481
				goto failed;
O
Olof Johansson 已提交
1482

1483 1484 1485 1486 1487 1488 1489 1490 1491
			/* 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;
1492
		}
1493 1494
	}
failed:
1495
	ret = 1;
1496
found:
R
Robert Olsson 已提交
1497
	rcu_read_unlock();
1498 1499 1500
	return ret;
}

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

	/* Note that in the case skipped bits, those bits are *not* checked!
1512
	 * When we finish this, we will have NULL or a T_LEAF, and the
1513 1514 1515
	 * T_LEAF may or may not match our key.
	 */

O
Olof Johansson 已提交
1516
	while (n != NULL && IS_TNODE(n)) {
1517 1518 1519 1520
		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 已提交
1521
		BUG_ON(n && NODE_PARENT(n) != tn);
O
Olof Johansson 已提交
1522
	}
1523 1524
	l = (struct leaf *) n;

1525
	if (!n || !tkey_equals(l->key, key))
1526
		return 0;
1527 1528 1529 1530

	/*
	 * Key found.
	 * Remove the leaf and rebalance the tree
1531 1532 1533 1534 1535
	 */

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

R
Robert Olsson 已提交
1536
	preempt_disable();
1537 1538 1539
	tp = NODE_PARENT(n);
	tnode_free((struct tnode *) n);

1540
	if (tp) {
1541 1542
		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
		put_child(t, (struct tnode *)tp, cindex, NULL);
R
Robert Olsson 已提交
1543
		rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
O
Olof Johansson 已提交
1544
	} else
R
Robert Olsson 已提交
1545 1546
		rcu_assign_pointer(t->trie, NULL);
	preempt_enable();
1547 1548 1549 1550 1551 1552

	return 1;
}

static int
fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
O
Olof Johansson 已提交
1553
		struct nlmsghdr *nlhdr, struct netlink_skb_parms *req)
1554 1555 1556 1557 1558 1559 1560 1561
{
	struct trie *t = (struct trie *) tb->tb_data;
	u32 key, mask;
	int plen = r->rtm_dst_len;
	u8 tos = r->rtm_tos;
	struct fib_alias *fa, *fa_to_delete;
	struct list_head *fa_head;
	struct leaf *l;
O
Olof Johansson 已提交
1562 1563
	struct leaf_info *li;

1564

1565
	if (plen > 32)
1566 1567 1568
		return -EINVAL;

	key = 0;
1569
	if (rta->rta_dst)
1570 1571 1572
		memcpy(&key, rta->rta_dst, 4);

	key = ntohl(key);
O
Olof Johansson 已提交
1573
	mask = ntohl(inet_make_mask(plen));
1574

1575
	if (key & ~mask)
1576 1577 1578 1579 1580
		return -EINVAL;

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

1581
	if (!l)
1582 1583 1584 1585 1586 1587 1588 1589
		return -ESRCH;

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

	if (!fa)
		return -ESRCH;

S
Stephen Hemminger 已提交
1590
	pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1591 1592 1593

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

1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 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;

		if ((!r->rtm_type ||
		     fa->fa_type == r->rtm_type) &&
		    (r->rtm_scope == RT_SCOPE_NOWHERE ||
		     fa->fa_scope == r->rtm_scope) &&
		    (!r->rtm_protocol ||
		     fi->fib_protocol == r->rtm_protocol) &&
		    fib_nh_match(r, nlhdr, rta, fi) == 0) {
			fa_to_delete = fa;
			break;
		}
	}

O
Olof Johansson 已提交
1613 1614
	if (!fa_to_delete)
		return -ESRCH;
1615

O
Olof Johansson 已提交
1616 1617 1618 1619
	fa = fa_to_delete;
	rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id, nlhdr, req);

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

R
Robert Olsson 已提交
1622
	list_del_rcu(&fa->fa_list);
1623

O
Olof Johansson 已提交
1624
	if (list_empty(fa_head)) {
R
Robert Olsson 已提交
1625
		hlist_del_rcu(&li->hlist);
O
Olof Johansson 已提交
1626
		free_leaf_info(li);
R
Robert Olsson 已提交
1627
	}
1628

O
Olof Johansson 已提交
1629 1630
	if (hlist_empty(&l->list))
		trie_leaf_remove(t, key);
1631

O
Olof Johansson 已提交
1632 1633
	if (fa->fa_state & FA_S_ACCESSED)
		rt_cache_flush(-1);
1634

R
Robert Olsson 已提交
1635 1636
	fib_release_info(fa->fa_info);
	alias_free_mem_rcu(fa);
O
Olof Johansson 已提交
1637
	return 0;
1638 1639 1640 1641 1642 1643 1644 1645 1646 1647
}

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 已提交
1648 1649 1650 1651
		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);
1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668
			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 已提交
1669
			hlist_del_rcu(&li->hlist);
1670 1671 1672 1673 1674 1675
			free_leaf_info(li);
		}
	}
	return found;
}

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

1678 1679 1680 1681 1682
static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
{
	struct node *c = (struct node *) thisleaf;
	struct tnode *p;
	int idx;
R
Robert Olsson 已提交
1683
	struct node *trie = rcu_dereference(t->trie);
1684

1685
	if (c == NULL) {
R
Robert Olsson 已提交
1686
		if (trie == NULL)
1687 1688
			return NULL;

R
Robert Olsson 已提交
1689 1690
		if (IS_LEAF(trie))          /* trie w. just a leaf */
			return (struct leaf *) trie;
1691

R
Robert Olsson 已提交
1692
		p = (struct tnode*) trie;  /* Start */
O
Olof Johansson 已提交
1693
	} else
1694
		p = (struct tnode *) NODE_PARENT(c);
1695

1696 1697 1698 1699
	while (p) {
		int pos, last;

		/*  Find the next child of the parent */
1700 1701 1702
		if (c)
			pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits);
		else
1703 1704 1705
			pos = 0;

		last = 1 << p->bits;
O
Olof Johansson 已提交
1706
		for (idx = pos; idx < last ; idx++) {
R
Robert Olsson 已提交
1707 1708 1709
			c = rcu_dereference(p->child[idx]);

			if (!c)
O
Olof Johansson 已提交
1710 1711 1712
				continue;

			/* Decend if tnode */
R
Robert Olsson 已提交
1713 1714 1715
			while (IS_TNODE(c)) {
				p = (struct tnode *) c;
  				idx = 0;
O
Olof Johansson 已提交
1716 1717 1718

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

				/* Done with this tnode? */
R
Robert Olsson 已提交
1723
				if (idx >= (1 << p->bits) || !c)
O
Olof Johansson 已提交
1724
					goto up;
1725
			}
R
Robert Olsson 已提交
1726
			return (struct leaf *) c;
1727 1728 1729
		}
up:
		/* No more children go up one step  */
O
Olof Johansson 已提交
1730
		c = (struct node *) p;
1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743
		p = (struct tnode *) NODE_PARENT(p);
	}
	return NULL; /* Ready. Root of trie */
}

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 已提交
1744
	for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1745 1746 1747 1748 1749 1750 1751 1752 1753 1754
		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 已提交
1755
	pr_debug("trie_flush found=%d\n", found);
1756 1757 1758
	return found;
}

O
Olof Johansson 已提交
1759
static int trie_last_dflt = -1;
1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775

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 已提交
1776
	rcu_read_lock();
1777

1778
	l = fib_find_node(t, 0);
1779
	if (!l)
1780 1781 1782
		goto out;

	fa_head = get_fa_head(l, 0);
1783
	if (!fa_head)
1784 1785
		goto out;

1786
	if (list_empty(fa_head))
1787 1788
		goto out;

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

1792 1793 1794
		if (fa->fa_scope != res->scope ||
		    fa->fa_type != RTN_UNICAST)
			continue;
O
Olof Johansson 已提交
1795

1796 1797 1798 1799 1800 1801
		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 已提交
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 1833 1834 1835 1836 1837 1838 1839
		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 已提交
1840
	rcu_read_unlock();
1841 1842
}

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

O
Olof Johansson 已提交
1849
	u32 xkey = htonl(key);
1850

O
Olof Johansson 已提交
1851
	s_i = cb->args[3];
1852 1853
	i = 0;

R
Robert Olsson 已提交
1854 1855 1856
	/* rcu_read_lock is hold by caller */

	list_for_each_entry_rcu(fa, fah, fa_list) {
1857 1858 1859 1860
		if (i < s_i) {
			i++;
			continue;
		}
S
Stephen Hemminger 已提交
1861
		BUG_ON(!fa->fa_info);
1862 1863 1864 1865 1866 1867 1868 1869 1870 1871

		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,
				  &xkey,
				  plen,
				  fa->fa_tos,
1872
				  fa->fa_info, 0) < 0) {
1873 1874
			cb->args[3] = i;
			return -1;
O
Olof Johansson 已提交
1875
		}
1876 1877
		i++;
	}
O
Olof Johansson 已提交
1878
	cb->args[3] = i;
1879 1880 1881
	return skb->len;
}

1882
static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb,
1883 1884 1885 1886 1887 1888
			     struct netlink_callback *cb)
{
	int h, s_h;
	struct list_head *fa_head;
	struct leaf *l = NULL;

O
Olof Johansson 已提交
1889
	s_h = cb->args[2];
1890

O
Olof Johansson 已提交
1891
	for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1892 1893 1894 1895 1896 1897 1898
		if (h < s_h)
			continue;
		if (h > s_h)
			memset(&cb->args[3], 0,
			       sizeof(cb->args) - 3*sizeof(cb->args[0]));

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

1900
		if (!fa_head)
1901 1902
			continue;

1903
		if (list_empty(fa_head))
1904 1905 1906
			continue;

		if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
O
Olof Johansson 已提交
1907
			cb->args[2] = h;
1908 1909 1910
			return -1;
		}
	}
O
Olof Johansson 已提交
1911
	cb->args[2] = h;
1912 1913 1914 1915 1916 1917 1918 1919 1920 1921
	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;

	s_m = cb->args[1];

R
Robert Olsson 已提交
1922
	rcu_read_lock();
O
Olof Johansson 已提交
1923
	for (m = 0; m <= 32; m++) {
1924 1925 1926 1927
		if (m < s_m)
			continue;
		if (m > s_m)
			memset(&cb->args[2], 0,
O
Olof Johansson 已提交
1928
				sizeof(cb->args) - 2*sizeof(cb->args[0]));
1929 1930 1931 1932 1933 1934

		if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) {
			cb->args[1] = m;
			goto out;
		}
	}
R
Robert Olsson 已提交
1935
	rcu_read_unlock();
1936 1937
	cb->args[1] = m;
	return skb->len;
O
Olof Johansson 已提交
1938
out:
R
Robert Olsson 已提交
1939
	rcu_read_unlock();
1940 1941 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 1971 1972 1973 1974 1975 1976 1977
	return -1;
}

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

#ifdef CONFIG_IP_MULTIPLE_TABLES
struct fib_table * fib_hash_init(int id)
#else
struct fib_table * __init fib_hash_init(int id)
#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);

1978
	if (id == RT_TABLE_LOCAL)
O
Olof Johansson 已提交
1979
		trie_local = t;
1980
	else if (id == RT_TABLE_MAIN)
O
Olof Johansson 已提交
1981
		trie_main = t;
1982 1983

	if (id == RT_TABLE_LOCAL)
S
Stephen Hemminger 已提交
1984
		printk(KERN_INFO "IPv4 FIB: Using LC-trie version %s\n", VERSION);
1985 1986 1987 1988

	return tb;
}

1989 1990 1991 1992 1993 1994 1995 1996
#ifdef CONFIG_PROC_FS
/* Depth first Trie walk iterator */
struct fib_trie_iter {
	struct tnode *tnode;
	struct trie *trie;
	unsigned index;
	unsigned depth;
};
1997

1998
static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
1999
{
2000 2001 2002
	struct tnode *tn = iter->tnode;
	unsigned cindex = iter->index;
	struct tnode *p;
2003

2004 2005 2006 2007 2008
	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);
2009

2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021
		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;
		}
2022

2023 2024
		++cindex;
	}
O
Olof Johansson 已提交
2025

2026 2027 2028 2029 2030 2031 2032
	/* 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;
2033
	}
2034 2035 2036

	/* got root? */
	return NULL;
2037 2038
}

2039 2040
static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
				       struct trie *t)
2041
{
2042 2043 2044 2045 2046 2047 2048 2049 2050
	struct node *n ;

	if(!t)
		return NULL;

	n = rcu_dereference(t->trie);

	if(!iter)
		return NULL;
2051

2052 2053 2054 2055
	if (n && IS_TNODE(n)) {
		iter->tnode = (struct tnode *) n;
		iter->trie = t;
		iter->index = 0;
2056
		iter->depth = 1;
2057
		return n;
O
Olof Johansson 已提交
2058
	}
2059 2060
	return NULL;
}
O
Olof Johansson 已提交
2061

2062 2063 2064 2065
static void trie_collect_stats(struct trie *t, struct trie_stat *s)
{
	struct node *n;
	struct fib_trie_iter iter;
O
Olof Johansson 已提交
2066

2067
	memset(s, 0, sizeof(*s));
O
Olof Johansson 已提交
2068

2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081
	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++;
R
Robert Olsson 已提交
2082 2083 2084
			if(tn->bits < MAX_STAT_DEPTH)
				s->nodesizes[tn->bits]++;

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

2093 2094 2095 2096
/*
 *	This outputs /proc/net/fib_triestats
 */
static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2097
{
2098
	unsigned i, max, pointers, bytes, avdepth;
2099

2100 2101 2102 2103
	if (stat->leaves)
		avdepth = stat->totdepth*100 / stat->leaves;
	else
		avdepth = 0;
O
Olof Johansson 已提交
2104

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

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

2110 2111 2112
	bytes = sizeof(struct leaf) * stat->leaves;
	seq_printf(seq, "\tInternal nodes: %d\n\t", stat->tnodes);
	bytes += sizeof(struct tnode) * stat->tnodes;
2113

R
Robert Olsson 已提交
2114 2115
	max = MAX_STAT_DEPTH;
	while (max > 0 && stat->nodesizes[max-1] == 0)
2116
		max--;
2117

2118 2119 2120 2121 2122 2123 2124 2125
	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 已提交
2126

2127 2128 2129
	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 已提交
2130

2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143
#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 */
}
2144

2145 2146 2147
static int fib_triestat_seq_show(struct seq_file *seq, void *v)
{
	struct trie_stat *stat;
O
Olof Johansson 已提交
2148

2149 2150 2151
	stat = kmalloc(sizeof(*stat), GFP_KERNEL);
	if (!stat)
		return -ENOMEM;
O
Olof Johansson 已提交
2152

2153 2154
	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 已提交
2155

2156 2157 2158 2159 2160
	if (trie_local) {
		seq_printf(seq, "Local:\n");
		trie_collect_stats(trie_local, stat);
		trie_show_stats(seq, stat);
	}
O
Olof Johansson 已提交
2161

2162 2163 2164 2165
	if (trie_main) {
		seq_printf(seq, "Main:\n");
		trie_collect_stats(trie_main, stat);
		trie_show_stats(seq, stat);
2166
	}
2167
	kfree(stat);
2168

2169
	return 0;
2170 2171
}

2172
static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2173
{
2174
	return single_open(file, fib_triestat_seq_show, NULL);
2175 2176
}

2177 2178 2179 2180 2181 2182 2183 2184 2185 2186
static struct file_operations fib_triestat_fops = {
	.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)
2187
{
2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201
	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;
	}
2202 2203 2204
	return NULL;
}

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

2213
static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2214
{
2215 2216 2217
	struct fib_trie_iter *iter = seq->private;
	void *l = v;

2218
	++*pos;
O
Olof Johansson 已提交
2219
	if (v == SEQ_START_TOKEN)
2220
		return fib_trie_get_idx(iter, 0);
2221

2222 2223 2224 2225
	v = fib_trie_get_next(iter);
	BUG_ON(v == l);
	if (v)
		return v;
2226

2227 2228 2229
	/* continue scan in next trie */
	if (iter->trie == trie_local)
		return fib_trie_get_first(iter, trie_main);
2230

2231 2232
	return NULL;
}
2233

2234
static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2235
{
2236 2237
	rcu_read_unlock();
}
O
Olof Johansson 已提交
2238

2239 2240 2241 2242
static void seq_indent(struct seq_file *seq, int n)
{
	while (n-- > 0) seq_puts(seq, "   ");
}
2243

2244 2245 2246
static inline const char *rtn_scope(enum rt_scope_t s)
{
	static char buf[32];
2247

2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258
	switch(s) {
	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;
	}
}
2259

2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273
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",
};
2274

2275 2276 2277
static inline const char *rtn_type(unsigned t)
{
	static char buf[32];
2278

2279 2280 2281 2282
	if (t < __RTN_MAX && rtn_type_names[t])
		return rtn_type_names[t];
	snprintf(buf, sizeof(buf), "type %d", t);
	return buf;
2283 2284
}

2285 2286
/* Pretty print the trie */
static int fib_trie_seq_show(struct seq_file *seq, void *v)
2287
{
2288 2289
	const struct fib_trie_iter *iter = seq->private;
	struct node *n = v;
2290

2291 2292
	if (v == SEQ_START_TOKEN)
		return 0;
2293

2294 2295 2296
	if (IS_TNODE(n)) {
		struct tnode *tn = (struct tnode *) n;
		t_key prf = ntohl(MASK_PFX(tn->key, tn->pos));
O
Olof Johansson 已提交
2297

2298 2299 2300 2301 2302
		if (!NODE_PARENT(n)) {
			if (iter->trie == trie_local)
				seq_puts(seq, "<local>:\n");
			else
				seq_puts(seq, "<main>:\n");
2303 2304 2305 2306 2307 2308
		} 
		seq_indent(seq, iter->depth-1);
		seq_printf(seq, "  +-- %d.%d.%d.%d/%d %d %d %d\n",
			   NIPQUAD(prf), tn->pos, tn->bits, tn->full_children, 
			   tn->empty_children);
		
2309 2310 2311 2312 2313 2314 2315 2316
	} else {
		struct leaf *l = (struct leaf *) n;
		int i;
		u32 val = ntohl(l->key);

		seq_indent(seq, iter->depth);
		seq_printf(seq, "  |-- %d.%d.%d.%d\n", NIPQUAD(val));
		for (i = 32; i >= 0; i--) {
R
Robert Olsson 已提交
2317
			struct leaf_info *li = find_leaf_info(l, i);
2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331
			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');
				}
			}
		}
2332
	}
2333

2334 2335 2336
	return 0;
}

2337 2338 2339 2340 2341
static struct seq_operations fib_trie_seq_ops = {
	.start  = fib_trie_seq_start,
	.next   = fib_trie_seq_next,
	.stop   = fib_trie_seq_stop,
	.show   = fib_trie_seq_show,
2342 2343
};

2344
static int fib_trie_seq_open(struct inode *inode, struct file *file)
2345 2346 2347
{
	struct seq_file *seq;
	int rc = -ENOMEM;
2348
	struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
2349

2350 2351 2352 2353
	if (!s)
		goto out;

	rc = seq_open(file, &fib_trie_seq_ops);
2354 2355 2356
	if (rc)
		goto out_kfree;

2357 2358 2359
	seq	     = file->private_data;
	seq->private = s;
	memset(s, 0, sizeof(*s));
2360 2361 2362
out:
	return rc;
out_kfree:
2363
	kfree(s);
2364 2365 2366
	goto out;
}

2367 2368 2369 2370 2371
static struct file_operations fib_trie_fops = {
	.owner  = THIS_MODULE,
	.open   = fib_trie_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2372
	.release = seq_release_private,
2373 2374
};

2375
static unsigned fib_flag_trans(int type, u32 mask, const struct fib_info *fi)
2376
{
2377 2378 2379 2380
	static unsigned type2flags[RTN_MAX + 1] = {
		[7] = RTF_REJECT, [8] = RTF_REJECT,
	};
	unsigned flags = type2flags[type];
2381

2382 2383 2384 2385 2386 2387
	if (fi && fi->fib_nh->nh_gw)
		flags |= RTF_GATEWAY;
	if (mask == 0xFFFFFFFF)
		flags |= RTF_HOST;
	flags |= RTF_UP;
	return flags;
2388 2389
}

2390 2391 2392 2393 2394 2395 2396
/*
 *	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)
2397
{
2398
	const struct fib_trie_iter *iter = seq->private;
2399 2400 2401
	struct leaf *l = v;
	int i;
	char bf[128];
2402

2403 2404 2405 2406 2407 2408
	if (v == SEQ_START_TOKEN) {
		seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
			   "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
			   "\tWindow\tIRTT");
		return 0;
	}
2409

2410 2411
	if (iter->trie == trie_local)
		return 0;
2412 2413
	if (IS_TNODE(l))
		return 0;
2414

2415
	for (i=32; i>=0; i--) {
R
Robert Olsson 已提交
2416
		struct leaf_info *li = find_leaf_info(l, i);
2417 2418
		struct fib_alias *fa;
		u32 mask, prefix;
O
Olof Johansson 已提交
2419

2420 2421
		if (!li)
			continue;
2422

2423 2424
		mask = inet_make_mask(li->plen);
		prefix = htonl(l->key);
2425

2426
		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2427
			const struct fib_info *fi = fa->fa_info;
2428
			unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2429

2430 2431 2432
			if (fa->fa_type == RTN_BROADCAST
			    || fa->fa_type == RTN_MULTICAST)
				continue;
2433

2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449
			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);
2450

2451 2452
			seq_printf(seq, "%-127s\n", bf);
		}
2453 2454 2455 2456 2457
	}

	return 0;
}

2458 2459 2460 2461 2462
static struct seq_operations fib_route_seq_ops = {
	.start  = fib_trie_seq_start,
	.next   = fib_trie_seq_next,
	.stop   = fib_trie_seq_stop,
	.show   = fib_route_seq_show,
2463 2464
};

2465
static int fib_route_seq_open(struct inode *inode, struct file *file)
2466 2467 2468
{
	struct seq_file *seq;
	int rc = -ENOMEM;
2469
	struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
2470

2471 2472 2473 2474
	if (!s)
		goto out;

	rc = seq_open(file, &fib_route_seq_ops);
2475 2476 2477
	if (rc)
		goto out_kfree;

2478 2479 2480
	seq	     = file->private_data;
	seq->private = s;
	memset(s, 0, sizeof(*s));
2481 2482 2483
out:
	return rc;
out_kfree:
2484
	kfree(s);
2485 2486 2487
	goto out;
}

2488 2489 2490 2491 2492 2493
static struct file_operations fib_route_fops = {
	.owner  = THIS_MODULE,
	.open   = fib_route_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
	.release = seq_release_private,
2494 2495 2496 2497
};

int __init fib_proc_init(void)
{
2498 2499 2500 2501 2502 2503 2504 2505 2506
	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;

2507
	return 0;
2508 2509 2510 2511 2512 2513 2514

out3:
	proc_net_remove("fib_triestat");
out2:
	proc_net_remove("fib_trie");
out1:
	return -ENOMEM;
2515 2516 2517 2518 2519
}

void __init fib_proc_exit(void)
{
	proc_net_remove("fib_trie");
2520 2521
	proc_net_remove("fib_triestat");
	proc_net_remove("route");
2522 2523 2524
}

#endif /* CONFIG_PROC_FS */