fib_trie.c 58.3 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
	return fa_head;
}

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

	if (plen > 32)
		return -EINVAL;

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

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

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

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

	key = key & mask;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

R
Robert Olsson 已提交
1272

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

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

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

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

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

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

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

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

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

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

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

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

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

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

O
Olof Johansson 已提交
1394 1395 1396 1397 1398 1399
		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;
		}
1400

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

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

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

1456 1457 1458 1459
backtrace:
		chopped_off++;

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

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

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

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

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

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

O
Olof Johansson 已提交
1511
	while (n != NULL && IS_TNODE(n)) {
1512 1513 1514 1515
		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 已提交
1516
		BUG_ON(n && NODE_PARENT(n) != tn);
O
Olof Johansson 已提交
1517
	}
1518 1519
	l = (struct leaf *) n;

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

	/*
	 * Key found.
	 * Remove the leaf and rebalance the tree
1526 1527 1528 1529 1530
	 */

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

R
Robert Olsson 已提交
1531
	preempt_disable();
1532 1533 1534
	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 1541
		rcu_assign_pointer(t->trie, NULL);
	preempt_enable();
1542 1543 1544 1545

	return 1;
}

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

1557
	if (plen > 32)
1558 1559
		return -EINVAL;

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

1563
	if (key & ~mask)
1564 1565 1566 1567 1568
		return -EINVAL;

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

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

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

	if (!fa)
		return -ESRCH;

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

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

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

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

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

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

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

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

R
Robert Olsson 已提交
1610
	list_del_rcu(&fa->fa_list);
1611

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

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

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

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

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

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

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

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

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

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

1684 1685 1686 1687
	while (p) {
		int pos, last;

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

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

			if (!c)
O
Olof Johansson 已提交
1698 1699 1700
				continue;

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

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

				/* Done with this tnode? */
R
Robert Olsson 已提交
1711
				if (idx >= (1 << p->bits) || !c)
O
Olof Johansson 已提交
1712
					goto up;
1713
			}
R
Robert Olsson 已提交
1714
			return (struct leaf *) c;
1715 1716 1717
		}
up:
		/* No more children go up one step  */
O
Olof Johansson 已提交
1718
		c = (struct node *) p;
1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731
		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 已提交
1732
	for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1733 1734 1735 1736 1737 1738 1739 1740 1741 1742
		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 已提交
1743
	pr_debug("trie_flush found=%d\n", found);
1744 1745 1746
	return found;
}

O
Olof Johansson 已提交
1747
static int trie_last_dflt = -1;
1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763

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 已提交
1764
	rcu_read_lock();
1765

1766
	l = fib_find_node(t, 0);
1767
	if (!l)
1768 1769 1770
		goto out;

	fa_head = get_fa_head(l, 0);
1771
	if (!fa_head)
1772 1773
		goto out;

1774
	if (list_empty(fa_head))
1775 1776
		goto out;

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

1780 1781 1782
		if (fa->fa_scope != res->scope ||
		    fa->fa_type != RTN_UNICAST)
			continue;
O
Olof Johansson 已提交
1783

1784 1785 1786 1787 1788 1789
		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 已提交
1790

1791 1792 1793 1794 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
		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 已提交
1828
	rcu_read_unlock();
1829 1830
}

1831
static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fib_table *tb,
1832 1833 1834 1835 1836
			   struct sk_buff *skb, struct netlink_callback *cb)
{
	int i, s_i;
	struct fib_alias *fa;

A
Al Viro 已提交
1837
	__be32 xkey = htonl(key);
1838

1839
	s_i = cb->args[4];
1840 1841
	i = 0;

R
Robert Olsson 已提交
1842 1843 1844
	/* rcu_read_lock is hold by caller */

	list_for_each_entry_rcu(fa, fah, fa_list) {
1845 1846 1847 1848
		if (i < s_i) {
			i++;
			continue;
		}
S
Stephen Hemminger 已提交
1849
		BUG_ON(!fa->fa_info);
1850 1851 1852 1853 1854 1855 1856

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

1870
static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb,
1871 1872 1873 1874 1875 1876
			     struct netlink_callback *cb)
{
	int h, s_h;
	struct list_head *fa_head;
	struct leaf *l = NULL;

1877
	s_h = cb->args[3];
1878

O
Olof Johansson 已提交
1879
	for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1880 1881 1882
		if (h < s_h)
			continue;
		if (h > s_h)
1883 1884
			memset(&cb->args[4], 0,
			       sizeof(cb->args) - 4*sizeof(cb->args[0]));
1885 1886

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

1888
		if (!fa_head)
1889 1890
			continue;

1891
		if (list_empty(fa_head))
1892 1893 1894
			continue;

		if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
1895
			cb->args[3] = h;
1896 1897 1898
			return -1;
		}
	}
1899
	cb->args[3] = h;
1900 1901 1902 1903 1904 1905 1906 1907
	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;

1908
	s_m = cb->args[2];
1909

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

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

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

#ifdef CONFIG_IP_MULTIPLE_TABLES
1934
struct fib_table * fib_hash_init(u32 id)
1935
#else
1936
struct fib_table * __init fib_hash_init(u32 id)
1937 1938 1939 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
#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);

1966
	if (id == RT_TABLE_LOCAL)
O
Olof Johansson 已提交
1967
		trie_local = t;
1968
	else if (id == RT_TABLE_MAIN)
O
Olof Johansson 已提交
1969
		trie_main = t;
1970 1971

	if (id == RT_TABLE_LOCAL)
S
Stephen Hemminger 已提交
1972
		printk(KERN_INFO "IPv4 FIB: Using LC-trie version %s\n", VERSION);
1973 1974 1975 1976

	return tb;
}

1977 1978 1979 1980 1981 1982 1983 1984
#ifdef CONFIG_PROC_FS
/* Depth first Trie walk iterator */
struct fib_trie_iter {
	struct tnode *tnode;
	struct trie *trie;
	unsigned index;
	unsigned depth;
};
1985

1986
static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
1987
{
1988 1989 1990
	struct tnode *tn = iter->tnode;
	unsigned cindex = iter->index;
	struct tnode *p;
1991

1992 1993 1994 1995 1996
	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);
1997

1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009
		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;
		}
2010

2011 2012
		++cindex;
	}
O
Olof Johansson 已提交
2013

2014 2015 2016 2017 2018 2019 2020
	/* 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;
2021
	}
2022 2023 2024

	/* got root? */
	return NULL;
2025 2026
}

2027 2028
static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
				       struct trie *t)
2029
{
2030 2031 2032 2033 2034 2035 2036 2037 2038
	struct node *n ;

	if(!t)
		return NULL;

	n = rcu_dereference(t->trie);

	if(!iter)
		return NULL;
2039

2040 2041 2042 2043
	if (n && IS_TNODE(n)) {
		iter->tnode = (struct tnode *) n;
		iter->trie = t;
		iter->index = 0;
2044
		iter->depth = 1;
2045
		return n;
O
Olof Johansson 已提交
2046
	}
2047 2048
	return NULL;
}
O
Olof Johansson 已提交
2049

2050 2051 2052 2053
static void trie_collect_stats(struct trie *t, struct trie_stat *s)
{
	struct node *n;
	struct fib_trie_iter iter;
O
Olof Johansson 已提交
2054

2055
	memset(s, 0, sizeof(*s));
O
Olof Johansson 已提交
2056

2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069
	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 已提交
2070 2071 2072
			if(tn->bits < MAX_STAT_DEPTH)
				s->nodesizes[tn->bits]++;

2073 2074 2075
			for (i = 0; i < (1<<tn->bits); i++)
				if (!tn->child[i])
					s->nullpointers++;
2076 2077
		}
	}
R
Robert Olsson 已提交
2078
	rcu_read_unlock();
2079 2080
}

2081 2082 2083 2084
/*
 *	This outputs /proc/net/fib_triestats
 */
static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2085
{
2086
	unsigned i, max, pointers, bytes, avdepth;
2087

2088 2089 2090 2091
	if (stat->leaves)
		avdepth = stat->totdepth*100 / stat->leaves;
	else
		avdepth = 0;
O
Olof Johansson 已提交
2092

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

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

2098 2099 2100
	bytes = sizeof(struct leaf) * stat->leaves;
	seq_printf(seq, "\tInternal nodes: %d\n\t", stat->tnodes);
	bytes += sizeof(struct tnode) * stat->tnodes;
2101

R
Robert Olsson 已提交
2102 2103
	max = MAX_STAT_DEPTH;
	while (max > 0 && stat->nodesizes[max-1] == 0)
2104
		max--;
2105

2106 2107 2108 2109 2110 2111 2112 2113
	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 已提交
2114

2115 2116 2117
	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 已提交
2118

2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131
#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 */
}
2132

2133 2134 2135
static int fib_triestat_seq_show(struct seq_file *seq, void *v)
{
	struct trie_stat *stat;
O
Olof Johansson 已提交
2136

2137 2138 2139
	stat = kmalloc(sizeof(*stat), GFP_KERNEL);
	if (!stat)
		return -ENOMEM;
O
Olof Johansson 已提交
2140

2141 2142
	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 已提交
2143

2144 2145 2146 2147 2148
	if (trie_local) {
		seq_printf(seq, "Local:\n");
		trie_collect_stats(trie_local, stat);
		trie_show_stats(seq, stat);
	}
O
Olof Johansson 已提交
2149

2150 2151 2152 2153
	if (trie_main) {
		seq_printf(seq, "Main:\n");
		trie_collect_stats(trie_main, stat);
		trie_show_stats(seq, stat);
2154
	}
2155
	kfree(stat);
2156

2157
	return 0;
2158 2159
}

2160
static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2161
{
2162
	return single_open(file, fib_triestat_seq_show, NULL);
2163 2164
}

2165 2166 2167 2168 2169 2170 2171 2172 2173 2174
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)
2175
{
2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189
	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;
	}
2190 2191 2192
	return NULL;
}

2193
static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2194
{
2195 2196
	rcu_read_lock();
	if (*pos == 0)
O
Olof Johansson 已提交
2197
		return SEQ_START_TOKEN;
2198
	return fib_trie_get_idx(seq->private, *pos - 1);
2199 2200
}

2201
static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2202
{
2203 2204 2205
	struct fib_trie_iter *iter = seq->private;
	void *l = v;

2206
	++*pos;
O
Olof Johansson 已提交
2207
	if (v == SEQ_START_TOKEN)
2208
		return fib_trie_get_idx(iter, 0);
2209

2210 2211 2212 2213
	v = fib_trie_get_next(iter);
	BUG_ON(v == l);
	if (v)
		return v;
2214

2215 2216 2217
	/* continue scan in next trie */
	if (iter->trie == trie_local)
		return fib_trie_get_first(iter, trie_main);
2218

2219 2220
	return NULL;
}
2221

2222
static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2223
{
2224 2225
	rcu_read_unlock();
}
O
Olof Johansson 已提交
2226

2227 2228 2229 2230
static void seq_indent(struct seq_file *seq, int n)
{
	while (n-- > 0) seq_puts(seq, "   ");
}
2231

2232 2233 2234
static inline const char *rtn_scope(enum rt_scope_t s)
{
	static char buf[32];
2235

2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246
	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;
	}
}
2247

2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261
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",
};
2262

2263 2264 2265
static inline const char *rtn_type(unsigned t)
{
	static char buf[32];
2266

2267 2268 2269 2270
	if (t < __RTN_MAX && rtn_type_names[t])
		return rtn_type_names[t];
	snprintf(buf, sizeof(buf), "type %d", t);
	return buf;
2271 2272
}

2273 2274
/* Pretty print the trie */
static int fib_trie_seq_show(struct seq_file *seq, void *v)
2275
{
2276 2277
	const struct fib_trie_iter *iter = seq->private;
	struct node *n = v;
2278

2279 2280
	if (v == SEQ_START_TOKEN)
		return 0;
2281

2282 2283
	if (IS_TNODE(n)) {
		struct tnode *tn = (struct tnode *) n;
A
Al Viro 已提交
2284
		__be32 prf = htonl(MASK_PFX(tn->key, tn->pos));
O
Olof Johansson 已提交
2285

2286 2287 2288 2289 2290
		if (!NODE_PARENT(n)) {
			if (iter->trie == trie_local)
				seq_puts(seq, "<local>:\n");
			else
				seq_puts(seq, "<main>:\n");
2291 2292 2293 2294 2295 2296
		} 
		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);
		
2297 2298 2299
	} else {
		struct leaf *l = (struct leaf *) n;
		int i;
A
Al Viro 已提交
2300
		__be32 val = htonl(l->key);
2301 2302 2303 2304

		seq_indent(seq, iter->depth);
		seq_printf(seq, "  |-- %d.%d.%d.%d\n", NIPQUAD(val));
		for (i = 32; i >= 0; i--) {
R
Robert Olsson 已提交
2305
			struct leaf_info *li = find_leaf_info(l, i);
2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319
			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');
				}
			}
		}
2320
	}
2321

2322 2323 2324
	return 0;
}

2325 2326 2327 2328 2329
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,
2330 2331
};

2332
static int fib_trie_seq_open(struct inode *inode, struct file *file)
2333 2334 2335
{
	struct seq_file *seq;
	int rc = -ENOMEM;
2336
	struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
2337

2338 2339 2340 2341
	if (!s)
		goto out;

	rc = seq_open(file, &fib_trie_seq_ops);
2342 2343 2344
	if (rc)
		goto out_kfree;

2345 2346 2347
	seq	     = file->private_data;
	seq->private = s;
	memset(s, 0, sizeof(*s));
2348 2349 2350
out:
	return rc;
out_kfree:
2351
	kfree(s);
2352 2353 2354
	goto out;
}

2355 2356 2357 2358 2359
static struct file_operations fib_trie_fops = {
	.owner  = THIS_MODULE,
	.open   = fib_trie_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2360
	.release = seq_release_private,
2361 2362
};

A
Al Viro 已提交
2363
static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2364
{
2365 2366 2367 2368
	static unsigned type2flags[RTN_MAX + 1] = {
		[7] = RTF_REJECT, [8] = RTF_REJECT,
	};
	unsigned flags = type2flags[type];
2369

2370 2371
	if (fi && fi->fib_nh->nh_gw)
		flags |= RTF_GATEWAY;
A
Al Viro 已提交
2372
	if (mask == htonl(0xFFFFFFFF))
2373 2374 2375
		flags |= RTF_HOST;
	flags |= RTF_UP;
	return flags;
2376 2377
}

2378 2379 2380 2381 2382 2383 2384
/*
 *	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)
2385
{
2386
	const struct fib_trie_iter *iter = seq->private;
2387 2388 2389
	struct leaf *l = v;
	int i;
	char bf[128];
2390

2391 2392 2393 2394 2395 2396
	if (v == SEQ_START_TOKEN) {
		seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
			   "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
			   "\tWindow\tIRTT");
		return 0;
	}
2397

2398 2399
	if (iter->trie == trie_local)
		return 0;
2400 2401
	if (IS_TNODE(l))
		return 0;
2402

2403
	for (i=32; i>=0; i--) {
R
Robert Olsson 已提交
2404
		struct leaf_info *li = find_leaf_info(l, i);
2405
		struct fib_alias *fa;
A
Al Viro 已提交
2406
		__be32 mask, prefix;
O
Olof Johansson 已提交
2407

2408 2409
		if (!li)
			continue;
2410

2411 2412
		mask = inet_make_mask(li->plen);
		prefix = htonl(l->key);
2413

2414
		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2415
			const struct fib_info *fi = fa->fa_info;
2416
			unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2417

2418 2419 2420
			if (fa->fa_type == RTN_BROADCAST
			    || fa->fa_type == RTN_MULTICAST)
				continue;
2421

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

2439 2440
			seq_printf(seq, "%-127s\n", bf);
		}
2441 2442 2443 2444 2445
	}

	return 0;
}

2446 2447 2448 2449 2450
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,
2451 2452
};

2453
static int fib_route_seq_open(struct inode *inode, struct file *file)
2454 2455 2456
{
	struct seq_file *seq;
	int rc = -ENOMEM;
2457
	struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
2458

2459 2460 2461 2462
	if (!s)
		goto out;

	rc = seq_open(file, &fib_route_seq_ops);
2463 2464 2465
	if (rc)
		goto out_kfree;

2466 2467 2468
	seq	     = file->private_data;
	seq->private = s;
	memset(s, 0, sizeof(*s));
2469 2470 2471
out:
	return rc;
out_kfree:
2472
	kfree(s);
2473 2474 2475
	goto out;
}

2476 2477 2478 2479 2480 2481
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,
2482 2483 2484 2485
};

int __init fib_proc_init(void)
{
2486 2487 2488 2489 2490 2491 2492 2493 2494
	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;

2495
	return 0;
2496 2497 2498 2499 2500 2501 2502

out3:
	proc_net_remove("fib_triestat");
out2:
	proc_net_remove("fib_trie");
out1:
	return -ENOMEM;
2503 2504 2505 2506 2507
}

void __init fib_proc_exit(void)
{
	proc_net_remove("fib_trie");
2508 2509
	proc_net_remove("fib_triestat");
	proc_net_remove("route");
2510 2511 2512
}

#endif /* CONFIG_PROC_FS */