fib_trie.c 58.7 KB
Newer Older
1 2 3 4 5 6 7 8 9
/*
 *   This program is free software; you can redistribute it and/or
 *   modify it under the terms of the GNU General Public License
 *   as published by the Free Software Foundation; either version
 *   2 of the License, or (at your option) any later version.
 *
 *   Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
 *     & Swedish University of Agricultural Sciences.
 *
10
 *   Jens Laas <jens.laas@data.slu.se> Swedish University of
11
 *     Agricultural Sciences.
12
 *
13 14 15
 *   Hans Liss <hans.liss@its.uu.se>  Uppsala Universitet
 *
 * This work is based on the LPC-trie which is originally descibed in:
16
 *
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
 * An experimental study of compression methods for dynamic tries
 * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
 * http://www.nada.kth.se/~snilsson/public/papers/dyntrie2/
 *
 *
 * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
 * IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999
 *
 * Version:	$Id: fib_trie.c,v 1.3 2005/06/08 14:20:01 robert Exp $
 *
 *
 * Code from fib_hash has been reused which includes the following header:
 *
 *
 * INET		An implementation of the TCP/IP protocol suite for the LINUX
 *		operating system.  INET is implemented using the  BSD Socket
 *		interface as the means of communication with the user level.
 *
 *		IPv4 FIB: lookup engine and maintenance routines.
 *
 *
 * Authors:	Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
 *
 *		This program is free software; you can redistribute it and/or
 *		modify it under the terms of the GNU General Public License
 *		as published by the Free Software Foundation; either version
 *		2 of the License, or (at your option) any later version.
R
Robert Olsson 已提交
44 45 46 47 48 49 50
 *
 * Substantial contributions to this work comes from:
 *
 *		David S. Miller, <davem@davemloft.net>
 *		Stephen Hemminger <shemminger@osdl.org>
 *		Paul E. McKenney <paulmck@us.ibm.com>
 *		Patrick McHardy <kaber@trash.net>
51 52
 */

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

#include <asm/uaccess.h>
#include <asm/system.h>
J
Jiri Slaby 已提交
57
#include <linux/bitops.h>
58 59 60 61 62 63 64 65 66
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/mm.h>
#include <linux/string.h>
#include <linux/socket.h>
#include <linux/sockios.h>
#include <linux/errno.h>
#include <linux/in.h>
#include <linux/inet.h>
S
Stephen Hemminger 已提交
67
#include <linux/inetdevice.h>
68 69 70
#include <linux/netdevice.h>
#include <linux/if_arp.h>
#include <linux/proc_fs.h>
R
Robert Olsson 已提交
71
#include <linux/rcupdate.h>
72 73 74 75
#include <linux/skbuff.h>
#include <linux/netlink.h>
#include <linux/init.h>
#include <linux/list.h>
76
#include <net/net_namespace.h>
77 78 79 80 81 82 83 84 85
#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

#define KEYLENGTH (8*sizeof(t_key))

typedef unsigned int t_key;

#define T_TNODE 0
#define T_LEAF  1
#define NODE_TYPE_MASK	0x1UL
R
Robert Olsson 已提交
95 96
#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)

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

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

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

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

struct tnode {
O
Olof Johansson 已提交
120 121 122 123 124 125
	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 已提交
126
	struct rcu_head rcu;
O
Olof Johansson 已提交
127
	struct node *child[0];
128 129 130 131 132 133 134 135 136
};

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

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

struct trie {
O
Olof Johansson 已提交
151
	struct node *trie;
152 153 154
#ifdef CONFIG_IP_FIB_TRIE_STATS
	struct trie_use_stats stats;
#endif
O
Olof Johansson 已提交
155
	int size;
156 157 158 159 160 161
	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);
162 163
static struct tnode *inflate(struct trie *t, struct tnode *tn);
static struct tnode *halve(struct trie *t, struct tnode *tn);
164 165
static void tnode_free(struct tnode *tn);

166
static struct kmem_cache *fn_alias_kmem __read_mostly;
167 168
static struct trie *trie_local = NULL, *trie_main = NULL;

S
Stephen Hemminger 已提交
169 170 171 172 173 174 175 176 177 178 179 180 181
static inline struct tnode *node_parent(struct node *node)
{
	struct tnode *ret;

	ret = (struct tnode *)(node->parent & ~NODE_TYPE_MASK);
	return rcu_dereference(ret);
}

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

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

185
static inline struct node *tnode_get_child(struct tnode *tn, int i)
186
{
O
Olof Johansson 已提交
187
	BUG_ON(i >= 1 << tn->bits);
188

R
Robert Olsson 已提交
189
	return rcu_dereference(tn->child[i]);
190 191
}

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

S
Stephen Hemminger 已提交
197 198 199 200 201
static inline t_key mask_pfx(t_key k, unsigned short l)
{
	return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
}

202 203
static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
{
O
Olof Johansson 已提交
204
	if (offset < KEYLENGTH)
205
		return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
O
Olof Johansson 已提交
206
	else
207 208 209 210 211
		return 0;
}

static inline int tkey_equals(t_key a, t_key b)
{
212
	return a == b;
213 214 215 216
}

static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
{
217 218
	if (bits == 0 || offset >= KEYLENGTH)
		return 1;
O
Olof Johansson 已提交
219 220
	bits = bits > KEYLENGTH ? KEYLENGTH : bits;
	return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
221
}
222 223 224 225 226 227

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

228 229 230
	if (!diff)
		return 0;
	while ((diff << i) >> (KEYLENGTH-1) == 0)
231 232 233 234 235
		i++;
	return i;
}

/*
236 237
  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
238 239 240 241
  all of the bits in that key are significant.

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

242 243 244 245 246
  If n is a leaf, every bit in its key is significant. Its presence is
  necessitated by path compression, since during a tree traversal (when
  searching for a leaf - unless we are doing an insertion) we will completely
  ignore all skipped bits we encounter. Thus we need to verify, at the end of
  a potentially successful search, that we have indeed been walking the
247 248
  correct key path.

249 250 251 252 253
  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
254 255
  call to tkey_sub_equals() in trie_insert().

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

259
  Example:
260 261 262
  _________________________________________________________________
  | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
  -----------------------------------------------------------------
263
    0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
264 265 266 267 268 269 270 271 272

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

275 276
  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
277 278 279
  not use them for anything.

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

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

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

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

292

293 294 295 296 297
  The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
  at this point.

*/

S
Stephen Hemminger 已提交
298
static inline void check_tnode(const struct tnode *tn)
299
{
S
Stephen Hemminger 已提交
300
	WARN_ON(tn && tn->pos+tn->bits > 32);
301 302 303 304
}

static int halve_threshold = 25;
static int inflate_threshold = 50;
305 306
static int halve_threshold_root = 8;
static int inflate_threshold_root = 15;
307

R
Robert Olsson 已提交
308 309

static void __alias_free_mem(struct rcu_head *head)
310
{
R
Robert Olsson 已提交
311 312
	struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
	kmem_cache_free(fn_alias_kmem, fa);
313 314
}

R
Robert Olsson 已提交
315
static inline void alias_free_mem_rcu(struct fib_alias *fa)
316
{
R
Robert Olsson 已提交
317 318
	call_rcu(&fa->rcu, __alias_free_mem);
}
O
Olof Johansson 已提交
319

R
Robert Olsson 已提交
320 321 322 323
static void __leaf_free_rcu(struct rcu_head *head)
{
	kfree(container_of(head, struct leaf, rcu));
}
O
Olof Johansson 已提交
324

R
Robert Olsson 已提交
325
static void __leaf_info_free_rcu(struct rcu_head *head)
326
{
R
Robert Olsson 已提交
327
	kfree(container_of(head, struct leaf_info, rcu));
328 329
}

R
Robert Olsson 已提交
330
static inline void free_leaf_info(struct leaf_info *leaf)
331
{
R
Robert Olsson 已提交
332
	call_rcu(&leaf->rcu, __leaf_info_free_rcu);
333 334
}

335 336
static struct tnode *tnode_alloc(unsigned int size)
{
R
Robert Olsson 已提交
337 338 339 340 341 342 343 344 345 346
	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);
347 348
}

R
Robert Olsson 已提交
349
static void __tnode_free_rcu(struct rcu_head *head)
350
{
R
Robert Olsson 已提交
351
	struct tnode *tn = container_of(head, struct tnode, rcu);
352
	unsigned int size = sizeof(struct tnode) +
R
Robert Olsson 已提交
353
		(1 << tn->bits) * sizeof(struct node *);
354 355 356 357 358 359 360

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

R
Robert Olsson 已提交
361 362
static inline void tnode_free(struct tnode *tn)
{
S
Stephen Hemminger 已提交
363
	if (IS_LEAF(tn)) {
R
Robert Olsson 已提交
364 365
		struct leaf *l = (struct leaf *) tn;
		call_rcu_bh(&l->rcu, __leaf_free_rcu);
S
Stephen Hemminger 已提交
366
	} else
R
Robert Olsson 已提交
367
		call_rcu(&tn->rcu, __tnode_free_rcu);
R
Robert Olsson 已提交
368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389
}

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

390 391 392 393
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 *);
394
	struct tnode *tn = tnode_alloc(sz);
395

O
Olof Johansson 已提交
396
	if (tn) {
397
		memset(tn, 0, sz);
R
Robert Olsson 已提交
398
		tn->parent = T_TNODE;
399 400 401 402 403 404
		tn->pos = pos;
		tn->bits = bits;
		tn->key = key;
		tn->full_children = 0;
		tn->empty_children = 1<<bits;
	}
405

S
Stephen Hemminger 已提交
406 407
	pr_debug("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode),
		 (unsigned int) (sizeof(struct node) * 1<<bits));
408 409 410 411 412 413 414 415
	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 已提交
416
static inline int tnode_full(const struct tnode *tn, const struct node *n)
417
{
418
	if (n == NULL || IS_LEAF(n))
419 420 421 422 423
		return 0;

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

424
static inline void put_child(struct trie *t, struct tnode *tn, int i, struct node *n)
425 426 427 428
{
	tnode_put_child_reorg(tn, i, n, -1);
}

429
 /*
430 431 432 433
  * Add a child at position i overwriting the old value.
  * Update the value of full_children and empty_children.
  */

434
static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull)
435
{
R
Robert Olsson 已提交
436
	struct node *chi = tn->child[i];
437 438
	int isfull;

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

441 442 443 444 445 446

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

448
	/* update fullChildren */
O
Olof Johansson 已提交
449
	if (wasfull == -1)
450 451 452
		wasfull = tnode_full(tn, chi);

	isfull = tnode_full(tn, n);
453
	if (wasfull && !isfull)
454
		tn->full_children--;
455
	else if (!wasfull && isfull)
456
		tn->full_children++;
O
Olof Johansson 已提交
457

458
	if (n)
S
Stephen Hemminger 已提交
459
		node_set_parent(n, tn);
460

R
Robert Olsson 已提交
461
	rcu_assign_pointer(tn->child[i], n);
462 463
}

464
static struct node *resize(struct trie *t, struct tnode *tn)
465 466
{
	int i;
467
	int err = 0;
468
	struct tnode *old_tn;
469 470
	int inflate_threshold_use;
	int halve_threshold_use;
R
Robert Olsson 已提交
471
	int max_resize;
472

473
	if (!tn)
474 475
		return NULL;

S
Stephen Hemminger 已提交
476 477
	pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
		 tn, inflate_threshold, halve_threshold);
478 479 480 481 482 483 484 485 486

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

O
Olof Johansson 已提交
489
			n = tn->child[i];
R
Robert Olsson 已提交
490
			if (!n)
O
Olof Johansson 已提交
491 492 493
				continue;

			/* compress one level */
S
Stephen Hemminger 已提交
494
			node_set_parent(n, NULL);
O
Olof Johansson 已提交
495 496
			tnode_free(tn);
			return n;
497
		}
498
	/*
499 500 501 502 503
	 * Double as long as the resulting node has a number of
	 * nonempty nodes that are above the threshold.
	 */

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

	check_tnode(tn);
563

564 565
	/* Keep root node larger  */

S
Stephen Hemminger 已提交
566
	if (!tn->parent)
567
		inflate_threshold_use = inflate_threshold_root;
568
	else
569 570
		inflate_threshold_use = inflate_threshold;

571
	err = 0;
R
Robert Olsson 已提交
572 573
	max_resize = 10;
	while ((tn->full_children > 0 &&  max_resize-- &&
574
	       50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >=
575
				inflate_threshold_use * tnode_child_length(tn))) {
576

577 578 579 580
		old_tn = tn;
		tn = inflate(t, tn);
		if (IS_ERR(tn)) {
			tn = old_tn;
581 582 583 584 585
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.resize_node_skipped++;
#endif
			break;
		}
586 587
	}

R
Robert Olsson 已提交
588 589 590 591 592 593 594 595 596
	if (max_resize < 0) {
		if (!tn->parent)
			printk(KERN_WARNING "Fix inflate_threshold_root. Now=%d size=%d bits\n",
			       inflate_threshold_root, tn->bits);
		else
			printk(KERN_WARNING "Fix inflate_threshold. Now=%d size=%d bits\n",
			       inflate_threshold, tn->bits);
	}

597 598 599 600 601 602
	check_tnode(tn);

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

604 605 606

	/* Keep root node larger  */

S
Stephen Hemminger 已提交
607
	if (!tn->parent)
608
		halve_threshold_use = halve_threshold_root;
609
	else
610 611
		halve_threshold_use = halve_threshold;

612
	err = 0;
R
Robert Olsson 已提交
613 614
	max_resize = 10;
	while (tn->bits > 1 &&  max_resize-- &&
615
	       100 * (tnode_child_length(tn) - tn->empty_children) <
616
	       halve_threshold_use * tnode_child_length(tn)) {
617

618 619 620 621
		old_tn = tn;
		tn = halve(t, tn);
		if (IS_ERR(tn)) {
			tn = old_tn;
622 623 624 625 626 627
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.resize_node_skipped++;
#endif
			break;
		}
	}
628

R
Robert Olsson 已提交
629 630 631 632 633 634 635 636
	if (max_resize < 0) {
		if (!tn->parent)
			printk(KERN_WARNING "Fix halve_threshold_root. Now=%d size=%d bits\n",
			       halve_threshold_root, tn->bits);
		else
			printk(KERN_WARNING "Fix halve_threshold. Now=%d size=%d bits\n",
			       halve_threshold, tn->bits);
	}
637

638 639 640
	/* 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 已提交
641
			struct node *n;
642

O
Olof Johansson 已提交
643
			n = tn->child[i];
R
Robert Olsson 已提交
644
			if (!n)
O
Olof Johansson 已提交
645 646 647 648
				continue;

			/* compress one level */

S
Stephen Hemminger 已提交
649
			node_set_parent(n, NULL);
O
Olof Johansson 已提交
650 651
			tnode_free(tn);
			return n;
652 653 654 655 656
		}

	return (struct node *) tn;
}

657
static struct tnode *inflate(struct trie *t, struct tnode *tn)
658 659 660 661 662 663
{
	struct tnode *inode;
	struct tnode *oldtnode = tn;
	int olen = tnode_child_length(tn);
	int i;

S
Stephen Hemminger 已提交
664
	pr_debug("In inflate\n");
665 666 667

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

S
Stephen Hemminger 已提交
668
	if (!tn)
669
		return ERR_PTR(-ENOMEM);
670 671

	/*
672 673 674
	 * 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
675 676
	 * of tnode is ignored.
	 */
O
Olof Johansson 已提交
677 678

	for (i = 0; i < olen; i++) {
679 680 681 682 683 684 685
		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;
S
Stephen Hemminger 已提交
686
			t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
687

688 689
			left = tnode_new(inode->key&(~m), inode->pos + 1,
					 inode->bits - 1);
690 691
			if (!left)
				goto nomem;
O
Olof Johansson 已提交
692

693 694 695
			right = tnode_new(inode->key|m, inode->pos + 1,
					  inode->bits - 1);

696
			if (!right) {
697 698
				tnode_free(left);
				goto nomem;
699
			}
700 701 702 703 704 705

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

O
Olof Johansson 已提交
706
	for (i = 0; i < olen; i++) {
707
		struct node *node = tnode_get_child(oldtnode, i);
O
Olof Johansson 已提交
708 709
		struct tnode *left, *right;
		int size, j;
710

711 712 713 714 715 716
		/* An empty child */
		if (node == NULL)
			continue;

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

717
		if (IS_LEAF(node) || ((struct tnode *) node)->pos >
718
		   tn->pos + tn->bits - 1) {
719
			if (tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits,
720 721 722 723 724 725 726 727 728 729 730 731 732 733 734
					     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 已提交
735
			continue;
736 737
		}

O
Olof Johansson 已提交
738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755
		/* 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)
		 */
756

O
Olof Johansson 已提交
757 758 759
		/* Use the old key, but set the new significant
		 *   bit to zero.
		 */
760

O
Olof Johansson 已提交
761 762
		left = (struct tnode *) tnode_get_child(tn, 2*i);
		put_child(t, tn, 2*i, NULL);
763

O
Olof Johansson 已提交
764
		BUG_ON(!left);
765

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

O
Olof Johansson 已提交
769
		BUG_ON(!right);
770

O
Olof Johansson 已提交
771 772 773 774
		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]);
775
		}
O
Olof Johansson 已提交
776 777 778 779
		put_child(t, tn, 2*i, resize(t, left));
		put_child(t, tn, 2*i+1, resize(t, right));

		tnode_free(inode);
780 781 782
	}
	tnode_free(oldtnode);
	return tn;
783 784 785 786 787
nomem:
	{
		int size = tnode_child_length(tn);
		int j;

S
Stephen Hemminger 已提交
788
		for (j = 0; j < size; j++)
789 790 791 792
			if (tn->child[j])
				tnode_free((struct tnode *)tn->child[j]);

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

794 795
		return ERR_PTR(-ENOMEM);
	}
796 797
}

798
static struct tnode *halve(struct trie *t, struct tnode *tn)
799 800 801 802 803 804
{
	struct tnode *oldtnode = tn;
	struct node *left, *right;
	int i;
	int olen = tnode_child_length(tn);

S
Stephen Hemminger 已提交
805
	pr_debug("In halve\n");
806 807

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

809 810
	if (!tn)
		return ERR_PTR(-ENOMEM);
811 812

	/*
813 814 815
	 * 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
816 817 818
	 * of tnode is ignored.
	 */

O
Olof Johansson 已提交
819
	for (i = 0; i < olen; i += 2) {
820 821
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
822

823
		/* Two nonempty children */
S
Stephen Hemminger 已提交
824
		if (left && right) {
825
			struct tnode *newn;
S
Stephen Hemminger 已提交
826

827
			newn = tnode_new(left->key, tn->pos + tn->bits, 1);
S
Stephen Hemminger 已提交
828 829

			if (!newn)
830
				goto nomem;
S
Stephen Hemminger 已提交
831

832
			put_child(t, tn, i/2, (struct node *)newn);
833 834 835
		}

	}
836

O
Olof Johansson 已提交
837 838 839
	for (i = 0; i < olen; i += 2) {
		struct tnode *newBinNode;

840 841
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
842

843 844 845 846 847
		/* 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 已提交
848
			continue;
S
Stephen Hemminger 已提交
849
		}
O
Olof Johansson 已提交
850 851

		if (right == NULL) {
852
			put_child(t, tn, i/2, left);
O
Olof Johansson 已提交
853 854
			continue;
		}
855

856
		/* Two nonempty children */
O
Olof Johansson 已提交
857 858 859 860 861
		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));
862 863 864
	}
	tnode_free(oldtnode);
	return tn;
865 866 867 868 869
nomem:
	{
		int size = tnode_child_length(tn);
		int j;

S
Stephen Hemminger 已提交
870
		for (j = 0; j < size; j++)
871 872 873 874
			if (tn->child[j])
				tnode_free((struct tnode *)tn->child[j]);

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

876 877
		return ERR_PTR(-ENOMEM);
	}
878 879
}

O
Olof Johansson 已提交
880
static void trie_init(struct trie *t)
881
{
O
Olof Johansson 已提交
882 883 884 885
	if (!t)
		return;

	t->size = 0;
R
Robert Olsson 已提交
886
	rcu_assign_pointer(t->trie, NULL);
O
Olof Johansson 已提交
887
	t->revision = 0;
888
#ifdef CONFIG_IP_FIB_TRIE_STATS
O
Olof Johansson 已提交
889
	memset(&t->stats, 0, sizeof(struct trie_use_stats));
890 891 892
#endif
}

R
Robert Olsson 已提交
893
/* readside must use rcu_read_lock currently dump routines
R
Robert Olsson 已提交
894 895
 via get_fa_head and dump */

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

R
Robert Olsson 已提交
902
	hlist_for_each_entry_rcu(li, node, head, hlist)
903
		if (li->plen == plen)
904
			return li;
O
Olof Johansson 已提交
905

906 907 908 909 910
	return NULL;
}

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

O
Olof Johansson 已提交
913 914
	if (!li)
		return NULL;
915

O
Olof Johansson 已提交
916
	return &li->falh;
917 918 919 920
}

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

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

942 943 944 945 946 947 948 949
static struct leaf *
fib_find_node(struct trie *t, u32 key)
{
	int pos;
	struct tnode *tn;
	struct node *n;

	pos = 0;
R
Robert Olsson 已提交
950
	n = rcu_dereference(t->trie);
951 952 953

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

955
		check_tnode(tn);
O
Olof Johansson 已提交
956

957
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
O
Olof Johansson 已提交
958
			pos = tn->pos + tn->bits;
959
			n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
O
Olof Johansson 已提交
960
		} else
961 962 963 964
			break;
	}
	/* Case we have found a leaf. Compare prefixes */

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

968 969 970 971 972 973
	return NULL;
}

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

S
Stephen Hemminger 已提交
977
	while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) {
978 979 980 981
		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 已提交
982

S
Stephen Hemminger 已提交
983 984
		tp = node_parent((struct node *) tn);
		if (!tp)
985
			break;
S
Stephen Hemminger 已提交
986
		tn = tp;
987
	}
S
Stephen Hemminger 已提交
988

989
	/* Handle last (top) tnode */
990
	if (IS_TNODE(tn))
991 992 993 994 995
		tn = (struct tnode*) resize(t, (struct tnode *)tn);

	return (struct node*) tn;
}

R
Robert Olsson 已提交
996 997
/* only used from updater-side */

998 999
static  struct list_head *
fib_insert_node(struct trie *t, int *err, u32 key, int plen)
1000 1001 1002 1003 1004 1005
{
	int pos, newpos;
	struct tnode *tp = NULL, *tn = NULL;
	struct node *n;
	struct leaf *l;
	int missbit;
1006
	struct list_head *fa_head = NULL;
1007 1008 1009 1010
	struct leaf_info *li;
	t_key cindex;

	pos = 0;
1011
	n = t->trie;
1012

1013 1014
	/* 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,
1015
	 * and we should just put our new leaf in that.
1016 1017
	 * 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
1018 1019
	 * not be the parent's 'pos'+'bits'!
	 *
1020
	 * If it does match the current key, get pos/bits from it, extract
1021 1022 1023 1024
	 * 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.
	 *
1025 1026 1027
	 * 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.
1028 1029 1030 1031 1032
	 * 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 已提交
1033

1034
		check_tnode(tn);
O
Olof Johansson 已提交
1035

1036
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1037
			tp = tn;
O
Olof Johansson 已提交
1038
			pos = tn->pos + tn->bits;
1039 1040
			n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));

S
Stephen Hemminger 已提交
1041
			BUG_ON(n && node_parent(n) != tn);
O
Olof Johansson 已提交
1042
		} else
1043 1044 1045 1046 1047 1048
			break;
	}

	/*
	 * n  ----> NULL, LEAF or TNODE
	 *
1049
	 * tp is n's (parent) ----> NULL or TNODE
1050 1051
	 */

O
Olof Johansson 已提交
1052
	BUG_ON(tp && IS_LEAF(tp));
1053 1054 1055

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

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

1059
		li = leaf_info_new(plen);
O
Olof Johansson 已提交
1060

1061
		if (!li) {
1062 1063 1064
			*err = -ENOMEM;
			goto err;
		}
1065 1066 1067 1068 1069 1070 1071 1072

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

1073
	if (!l) {
1074 1075 1076
		*err = -ENOMEM;
		goto err;
	}
1077 1078 1079 1080

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

1081
	if (!li) {
1082 1083 1084 1085
		tnode_free((struct tnode *) l);
		*err = -ENOMEM;
		goto err;
	}
1086 1087 1088 1089 1090

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

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

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

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

		if (tp)
O
Olof Johansson 已提交
1105
			pos = tp->pos+tp->bits;
1106
		else
O
Olof Johansson 已提交
1107 1108
			pos = 0;

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

1117
		if (!tn) {
1118 1119 1120 1121
			free_leaf_info(li);
			tnode_free((struct tnode *) l);
			*err = -ENOMEM;
			goto err;
O
Olof Johansson 已提交
1122 1123
		}

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

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

1130
		if (tp) {
1131 1132
			cindex = tkey_extract_bits(key, tp->pos, tp->bits);
			put_child(t, (struct tnode *)tp, cindex, (struct node *)tn);
O
Olof Johansson 已提交
1133
		} else {
R
Robert Olsson 已提交
1134
			rcu_assign_pointer(t->trie, (struct node *)tn); /* First tnode */
1135 1136 1137
			tp = tn;
		}
	}
O
Olof Johansson 已提交
1138 1139

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

1143
	/* Rebalance the trie */
R
Robert Olsson 已提交
1144 1145

	rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
1146 1147
done:
	t->revision++;
O
Olof Johansson 已提交
1148
err:
1149 1150 1151
	return fa_head;
}

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

	if (plen > 32)
		return -EINVAL;

1170
	key = ntohl(cfg->fc_dst);
1171

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

O
Olof Johansson 已提交
1174
	mask = ntohl(inet_make_mask(plen));
1175

1176
	if (key & ~mask)
1177 1178 1179 1180
		return -EINVAL;

	key = key & mask;

1181 1182 1183
	fi = fib_create_info(cfg);
	if (IS_ERR(fi)) {
		err = PTR_ERR(fi);
1184
		goto err;
1185
	}
1186 1187

	l = fib_find_node(t, key);
1188
	fa = NULL;
1189

1190
	if (l) {
1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205
		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 已提交
1206
	if (fa && fa->fa_info->fib_priority == fi->fib_priority) {
1207 1208 1209
		struct fib_alias *fa_orig;

		err = -EEXIST;
1210
		if (cfg->fc_nlflags & NLM_F_EXCL)
1211 1212
			goto out;

1213
		if (cfg->fc_nlflags & NLM_F_REPLACE) {
1214 1215 1216
			struct fib_info *fi_drop;
			u8 state;

R
Robert Olsson 已提交
1217
			err = -ENOBUFS;
1218
			new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
R
Robert Olsson 已提交
1219 1220
			if (new_fa == NULL)
				goto out;
1221 1222

			fi_drop = fa->fa_info;
R
Robert Olsson 已提交
1223 1224
			new_fa->fa_tos = fa->fa_tos;
			new_fa->fa_info = fi;
1225 1226
			new_fa->fa_type = cfg->fc_type;
			new_fa->fa_scope = cfg->fc_scope;
1227
			state = fa->fa_state;
R
Robert Olsson 已提交
1228
			new_fa->fa_state &= ~FA_S_ACCESSED;
1229

R
Robert Olsson 已提交
1230 1231
			list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
			alias_free_mem_rcu(fa);
1232 1233 1234

			fib_release_info(fi_drop);
			if (state & FA_S_ACCESSED)
O
Olof Johansson 已提交
1235
				rt_cache_flush(-1);
1236 1237
			rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
				tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1238

O
Olof Johansson 已提交
1239
			goto succeeded;
1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250
		}
		/* 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;
1251 1252
			if (fa->fa_type == cfg->fc_type &&
			    fa->fa_scope == cfg->fc_scope &&
1253 1254 1255 1256
			    fa->fa_info == fi) {
				goto out;
			}
		}
1257
		if (!(cfg->fc_nlflags & NLM_F_APPEND))
1258 1259 1260
			fa = fa_orig;
	}
	err = -ENOENT;
1261
	if (!(cfg->fc_nlflags & NLM_F_CREATE))
1262 1263 1264
		goto out;

	err = -ENOBUFS;
1265
	new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1266 1267 1268 1269 1270
	if (new_fa == NULL)
		goto out;

	new_fa->fa_info = fi;
	new_fa->fa_tos = tos;
1271 1272
	new_fa->fa_type = cfg->fc_type;
	new_fa->fa_scope = cfg->fc_scope;
1273 1274 1275 1276 1277
	new_fa->fa_state = 0;
	/*
	 * Insert new entry to the list.
	 */

1278
	if (!fa_head) {
1279
		err = 0;
1280
		fa_head = fib_insert_node(t, &err, key, plen);
1281
		if (err)
1282 1283
			goto out_free_new_fa;
	}
1284

R
Robert Olsson 已提交
1285 1286
	list_add_tail_rcu(&new_fa->fa_list,
			  (fa ? &fa->fa_list : fa_head));
1287 1288

	rt_cache_flush(-1);
1289
	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1290
		  &cfg->fc_nlinfo, 0);
1291 1292
succeeded:
	return 0;
1293 1294 1295

out_free_new_fa:
	kmem_cache_free(fn_alias_kmem, new_fa);
1296 1297
out:
	fib_release_info(fi);
O
Olof Johansson 已提交
1298
err:
1299 1300 1301
	return err;
}

R
Robert Olsson 已提交
1302

R
Robert Olsson 已提交
1303
/* should be called with rcu_read_lock */
S
Stephen Hemminger 已提交
1304 1305
static inline int check_leaf(struct trie *t, struct leaf *l,
			     t_key key, int *plen, const struct flowi *flp,
1306
			     struct fib_result *res)
1307
{
1308
	int err, i;
1309
	__be32 mask;
1310 1311 1312
	struct leaf_info *li;
	struct hlist_head *hhead = &l->list;
	struct hlist_node *node;
1313

R
Robert Olsson 已提交
1314
	hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1315
		i = li->plen;
1316 1317
		mask = inet_make_mask(i);
		if (l->key != (key & ntohl(mask)))
1318 1319
			continue;

1320
		if ((err = fib_semantic_match(&li->falh, flp, res, htonl(l->key), mask, i)) <= 0) {
1321 1322 1323 1324
			*plen = i;
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.semantic_match_passed++;
#endif
1325
			return err;
1326 1327 1328 1329 1330
		}
#ifdef CONFIG_IP_FIB_TRIE_STATS
		t->stats.semantic_match_miss++;
#endif
	}
1331
	return 1;
1332 1333 1334 1335 1336 1337 1338 1339 1340 1341
}

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 已提交
1342
	t_key key = ntohl(flp->fl4_dst);
1343 1344 1345
	int chopped_off;
	t_key cindex = 0;
	int current_prefix_length = KEYLENGTH;
O
Olof Johansson 已提交
1346 1347 1348 1349
	struct tnode *cn;
	t_key node_prefix, key_prefix, pref_mismatch;
	int mp;

R
Robert Olsson 已提交
1350
	rcu_read_lock();
O
Olof Johansson 已提交
1351

R
Robert Olsson 已提交
1352
	n = rcu_dereference(t->trie);
1353
	if (!n)
1354 1355 1356 1357 1358 1359 1360 1361
		goto failed;

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

	/* Just a leaf? */
	if (IS_LEAF(n)) {
1362
		if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
1363 1364 1365 1366 1367
			goto found;
		goto failed;
	}
	pn = (struct tnode *) n;
	chopped_off = 0;
1368

O
Olof Johansson 已提交
1369
	while (pn) {
1370 1371 1372
		pos = pn->pos;
		bits = pn->bits;

1373
		if (!chopped_off)
S
Stephen Hemminger 已提交
1374 1375
			cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
						   pos, bits);
1376 1377 1378 1379 1380 1381 1382 1383 1384 1385

		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 已提交
1386 1387 1388 1389 1390 1391 1392
		if (IS_LEAF(n)) {
			if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
				goto found;
			else
				goto backtrace;
		}

1393 1394
#define HL_OPTIMIZE
#ifdef HL_OPTIMIZE
O
Olof Johansson 已提交
1395
		cn = (struct tnode *)n;
1396

O
Olof Johansson 已提交
1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411
		/*
		 * 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].
		 */
1412

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

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

O
Olof Johansson 已提交
1425 1426 1427 1428 1429 1430
		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;
		}
1431

O
Olof Johansson 已提交
1432 1433 1434 1435 1436 1437 1438 1439 1440
		/*
		 * 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.
		 */
1441

O
Olof Johansson 已提交
1442 1443 1444 1445 1446 1447 1448 1449
		/* 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.
		 */
1450

O
Olof Johansson 已提交
1451 1452 1453 1454 1455 1456 1457 1458 1459 1460
		/* 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.
		 */

S
Stephen Hemminger 已提交
1461 1462
		node_prefix = mask_pfx(cn->key, cn->pos);
		key_prefix = mask_pfx(key, cn->pos);
O
Olof Johansson 已提交
1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480
		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;
1481
		}
O
Olof Johansson 已提交
1482 1483 1484 1485 1486
#endif
		pn = (struct tnode *)n; /* Descend */
		chopped_off = 0;
		continue;

1487 1488 1489 1490
backtrace:
		chopped_off++;

		/* As zero don't change the child key (cindex) */
O
Olof Johansson 已提交
1491
		while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1))))
1492 1493 1494 1495 1496
			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 已提交
1497

1498
		/*
1499
		 * Either we do the actual chop off according or if we have
1500 1501 1502
		 * chopped off all bits in this tnode walk up to our parent.
		 */

O
Olof Johansson 已提交
1503
		if (chopped_off <= pn->bits) {
1504
			cindex &= ~(1 << (chopped_off-1));
O
Olof Johansson 已提交
1505
		} else {
S
Stephen Hemminger 已提交
1506 1507
			struct tnode *parent = node_parent((struct node *) pn);
			if (!parent)
1508
				goto failed;
O
Olof Johansson 已提交
1509

1510
			/* Get Child's index */
S
Stephen Hemminger 已提交
1511 1512
			cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
			pn = parent;
1513 1514 1515 1516 1517 1518
			chopped_off = 0;

#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.backtrack++;
#endif
			goto backtrace;
1519
		}
1520 1521
	}
failed:
1522
	ret = 1;
1523
found:
R
Robert Olsson 已提交
1524
	rcu_read_unlock();
1525 1526 1527
	return ret;
}

R
Robert Olsson 已提交
1528
/* only called from updater side */
1529 1530 1531 1532 1533 1534 1535
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 已提交
1536
	pr_debug("entering trie_leaf_remove(%p)\n", n);
1537 1538

	/* Note that in the case skipped bits, those bits are *not* checked!
1539
	 * When we finish this, we will have NULL or a T_LEAF, and the
1540 1541 1542
	 * T_LEAF may or may not match our key.
	 */

O
Olof Johansson 已提交
1543
	while (n != NULL && IS_TNODE(n)) {
1544 1545 1546 1547
		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 已提交
1548
		BUG_ON(n && node_parent(n) != tn);
O
Olof Johansson 已提交
1549
	}
1550 1551
	l = (struct leaf *) n;

1552
	if (!n || !tkey_equals(l->key, key))
1553
		return 0;
1554 1555 1556 1557

	/*
	 * Key found.
	 * Remove the leaf and rebalance the tree
1558 1559 1560 1561 1562
	 */

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

S
Stephen Hemminger 已提交
1563
	tp = node_parent(n);
1564 1565
	tnode_free((struct tnode *) n);

1566
	if (tp) {
1567 1568
		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
		put_child(t, (struct tnode *)tp, cindex, NULL);
R
Robert Olsson 已提交
1569
		rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
O
Olof Johansson 已提交
1570
	} else
R
Robert Olsson 已提交
1571
		rcu_assign_pointer(t->trie, NULL);
1572 1573 1574 1575

	return 1;
}

1576 1577 1578
/*
 * Caller must hold RTNL.
 */
1579
static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
1580 1581 1582
{
	struct trie *t = (struct trie *) tb->tb_data;
	u32 key, mask;
1583 1584
	int plen = cfg->fc_dst_len;
	u8 tos = cfg->fc_tos;
1585 1586 1587
	struct fib_alias *fa, *fa_to_delete;
	struct list_head *fa_head;
	struct leaf *l;
O
Olof Johansson 已提交
1588 1589
	struct leaf_info *li;

1590
	if (plen > 32)
1591 1592
		return -EINVAL;

1593
	key = ntohl(cfg->fc_dst);
O
Olof Johansson 已提交
1594
	mask = ntohl(inet_make_mask(plen));
1595

1596
	if (key & ~mask)
1597 1598 1599 1600 1601
		return -EINVAL;

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

1602
	if (!l)
1603 1604 1605 1606 1607 1608 1609 1610
		return -ESRCH;

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

	if (!fa)
		return -ESRCH;

S
Stephen Hemminger 已提交
1611
	pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1612 1613 1614

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

1616 1617 1618 1619 1620 1621
	list_for_each_entry(fa, fa_head, fa_list) {
		struct fib_info *fi = fa->fa_info;

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

1622 1623 1624 1625 1626 1627
		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) {
1628 1629 1630 1631 1632
			fa_to_delete = fa;
			break;
		}
	}

O
Olof Johansson 已提交
1633 1634
	if (!fa_to_delete)
		return -ESRCH;
1635

O
Olof Johansson 已提交
1636
	fa = fa_to_delete;
1637
	rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1638
		  &cfg->fc_nlinfo, 0);
O
Olof Johansson 已提交
1639 1640

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

R
Robert Olsson 已提交
1643
	list_del_rcu(&fa->fa_list);
1644

O
Olof Johansson 已提交
1645
	if (list_empty(fa_head)) {
R
Robert Olsson 已提交
1646
		hlist_del_rcu(&li->hlist);
O
Olof Johansson 已提交
1647
		free_leaf_info(li);
R
Robert Olsson 已提交
1648
	}
1649

O
Olof Johansson 已提交
1650 1651
	if (hlist_empty(&l->list))
		trie_leaf_remove(t, key);
1652

O
Olof Johansson 已提交
1653 1654
	if (fa->fa_state & FA_S_ACCESSED)
		rt_cache_flush(-1);
1655

R
Robert Olsson 已提交
1656 1657
	fib_release_info(fa->fa_info);
	alias_free_mem_rcu(fa);
O
Olof Johansson 已提交
1658
	return 0;
1659 1660 1661 1662 1663 1664 1665 1666 1667 1668
}

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 已提交
1669 1670 1671 1672
		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);
1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689
			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 已提交
1690
			hlist_del_rcu(&li->hlist);
1691 1692 1693 1694 1695 1696
			free_leaf_info(li);
		}
	}
	return found;
}

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

1699 1700 1701 1702 1703
static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
{
	struct node *c = (struct node *) thisleaf;
	struct tnode *p;
	int idx;
R
Robert Olsson 已提交
1704
	struct node *trie = rcu_dereference(t->trie);
1705

1706
	if (c == NULL) {
R
Robert Olsson 已提交
1707
		if (trie == NULL)
1708 1709
			return NULL;

R
Robert Olsson 已提交
1710 1711
		if (IS_LEAF(trie))          /* trie w. just a leaf */
			return (struct leaf *) trie;
1712

R
Robert Olsson 已提交
1713
		p = (struct tnode*) trie;  /* Start */
O
Olof Johansson 已提交
1714
	} else
S
Stephen Hemminger 已提交
1715
		p = node_parent(c);
1716

1717 1718 1719 1720
	while (p) {
		int pos, last;

		/*  Find the next child of the parent */
1721 1722 1723
		if (c)
			pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits);
		else
1724 1725 1726
			pos = 0;

		last = 1 << p->bits;
O
Olof Johansson 已提交
1727
		for (idx = pos; idx < last ; idx++) {
R
Robert Olsson 已提交
1728 1729 1730
			c = rcu_dereference(p->child[idx]);

			if (!c)
O
Olof Johansson 已提交
1731 1732 1733
				continue;

			/* Decend if tnode */
R
Robert Olsson 已提交
1734 1735
			while (IS_TNODE(c)) {
				p = (struct tnode *) c;
1736
				idx = 0;
O
Olof Johansson 已提交
1737 1738 1739

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

				/* Done with this tnode? */
R
Robert Olsson 已提交
1744
				if (idx >= (1 << p->bits) || !c)
O
Olof Johansson 已提交
1745
					goto up;
1746
			}
R
Robert Olsson 已提交
1747
			return (struct leaf *) c;
1748 1749 1750
		}
up:
		/* No more children go up one step  */
O
Olof Johansson 已提交
1751
		c = (struct node *) p;
S
Stephen Hemminger 已提交
1752
		p = node_parent(c);
1753 1754 1755 1756
	}
	return NULL; /* Ready. Root of trie */
}

1757 1758 1759
/*
 * Caller must hold RTNL.
 */
1760 1761 1762 1763 1764 1765 1766 1767
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 已提交
1768
	for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1769 1770 1771 1772 1773 1774 1775 1776 1777 1778
		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 已提交
1779
	pr_debug("trie_flush found=%d\n", found);
1780 1781 1782
	return found;
}

O
Olof Johansson 已提交
1783
static int trie_last_dflt = -1;
1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799

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 已提交
1800
	rcu_read_lock();
1801

1802
	l = fib_find_node(t, 0);
1803
	if (!l)
1804 1805 1806
		goto out;

	fa_head = get_fa_head(l, 0);
1807
	if (!fa_head)
1808 1809
		goto out;

1810
	if (list_empty(fa_head))
1811 1812
		goto out;

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

1816 1817 1818
		if (fa->fa_scope != res->scope ||
		    fa->fa_type != RTN_UNICAST)
			continue;
O
Olof Johansson 已提交
1819

1820 1821 1822 1823 1824 1825
		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 已提交
1826

1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863
		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 已提交
1864
	rcu_read_unlock();
1865 1866
}

1867
static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fib_table *tb,
1868 1869 1870 1871 1872
			   struct sk_buff *skb, struct netlink_callback *cb)
{
	int i, s_i;
	struct fib_alias *fa;

A
Al Viro 已提交
1873
	__be32 xkey = htonl(key);
1874

1875
	s_i = cb->args[4];
1876 1877
	i = 0;

R
Robert Olsson 已提交
1878 1879 1880
	/* rcu_read_lock is hold by caller */

	list_for_each_entry_rcu(fa, fah, fa_list) {
1881 1882 1883 1884
		if (i < s_i) {
			i++;
			continue;
		}
S
Stephen Hemminger 已提交
1885
		BUG_ON(!fa->fa_info);
1886 1887 1888 1889 1890 1891 1892

		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,
1893
				  xkey,
1894 1895
				  plen,
				  fa->fa_tos,
1896
				  fa->fa_info, 0) < 0) {
1897
			cb->args[4] = i;
1898
			return -1;
O
Olof Johansson 已提交
1899
		}
1900 1901
		i++;
	}
1902
	cb->args[4] = i;
1903 1904 1905
	return skb->len;
}

1906
static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb,
1907 1908 1909 1910 1911 1912
			     struct netlink_callback *cb)
{
	int h, s_h;
	struct list_head *fa_head;
	struct leaf *l = NULL;

1913
	s_h = cb->args[3];
1914

O
Olof Johansson 已提交
1915
	for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1916 1917 1918
		if (h < s_h)
			continue;
		if (h > s_h)
1919 1920
			memset(&cb->args[4], 0,
			       sizeof(cb->args) - 4*sizeof(cb->args[0]));
1921 1922

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

1924
		if (!fa_head)
1925 1926
			continue;

1927
		if (list_empty(fa_head))
1928 1929 1930
			continue;

		if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
1931
			cb->args[3] = h;
1932 1933 1934
			return -1;
		}
	}
1935
	cb->args[3] = h;
1936 1937 1938 1939 1940 1941 1942 1943
	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;

1944
	s_m = cb->args[2];
1945

R
Robert Olsson 已提交
1946
	rcu_read_lock();
O
Olof Johansson 已提交
1947
	for (m = 0; m <= 32; m++) {
1948 1949 1950
		if (m < s_m)
			continue;
		if (m > s_m)
1951 1952
			memset(&cb->args[3], 0,
				sizeof(cb->args) - 3*sizeof(cb->args[0]));
1953 1954

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

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

#ifdef CONFIG_IP_MULTIPLE_TABLES
1970
struct fib_table * fib_hash_init(u32 id)
1971
#else
1972
struct fib_table * __init fib_hash_init(u32 id)
1973 1974 1975 1976 1977 1978 1979 1980 1981
#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,
1982
						  NULL);
1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001

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

2002
	if (id == RT_TABLE_LOCAL)
O
Olof Johansson 已提交
2003
		trie_local = t;
2004
	else if (id == RT_TABLE_MAIN)
O
Olof Johansson 已提交
2005
		trie_main = t;
2006 2007

	if (id == RT_TABLE_LOCAL)
S
Stephen Hemminger 已提交
2008
		printk(KERN_INFO "IPv4 FIB: Using LC-trie version %s\n", VERSION);
2009 2010 2011 2012

	return tb;
}

2013 2014 2015 2016 2017 2018 2019 2020
#ifdef CONFIG_PROC_FS
/* Depth first Trie walk iterator */
struct fib_trie_iter {
	struct tnode *tnode;
	struct trie *trie;
	unsigned index;
	unsigned depth;
};
2021

2022
static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
2023
{
2024 2025 2026
	struct tnode *tn = iter->tnode;
	unsigned cindex = iter->index;
	struct tnode *p;
2027

2028 2029 2030 2031
	/* A single entry routing table */
	if (!tn)
		return NULL;

2032 2033 2034 2035 2036
	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);
2037

2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049
		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;
		}
2050

2051 2052
		++cindex;
	}
O
Olof Johansson 已提交
2053

2054
	/* Current node exhausted, pop back up */
S
Stephen Hemminger 已提交
2055
	p = node_parent((struct node *)tn);
2056 2057 2058 2059 2060
	if (p) {
		cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
		tn = p;
		--iter->depth;
		goto rescan;
2061
	}
2062 2063 2064

	/* got root? */
	return NULL;
2065 2066
}

2067 2068
static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
				       struct trie *t)
2069
{
2070 2071
	struct node *n ;

S
Stephen Hemminger 已提交
2072
	if (!t)
2073 2074 2075 2076
		return NULL;

	n = rcu_dereference(t->trie);

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

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

2097 2098 2099 2100
static void trie_collect_stats(struct trie *t, struct trie_stat *s)
{
	struct node *n;
	struct fib_trie_iter iter;
O
Olof Johansson 已提交
2101

2102
	memset(s, 0, sizeof(*s));
O
Olof Johansson 已提交
2103

2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116
	rcu_read_lock();
	for (n = fib_trie_get_first(&iter, t); n;
	     n = fib_trie_get_next(&iter)) {
		if (IS_LEAF(n)) {
			s->leaves++;
			s->totdepth += iter.depth;
			if (iter.depth > s->maxdepth)
				s->maxdepth = iter.depth;
		} else {
			const struct tnode *tn = (const struct tnode *) n;
			int i;

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

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

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

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

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

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

2145 2146 2147
	bytes = sizeof(struct leaf) * stat->leaves;
	seq_printf(seq, "\tInternal nodes: %d\n\t", stat->tnodes);
	bytes += sizeof(struct tnode) * stat->tnodes;
2148

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

2153 2154 2155 2156 2157 2158 2159 2160
	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 已提交
2161

2162 2163 2164
	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 已提交
2165

2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178
#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 */
}
2179

2180 2181 2182
static int fib_triestat_seq_show(struct seq_file *seq, void *v)
{
	struct trie_stat *stat;
O
Olof Johansson 已提交
2183

2184 2185 2186
	stat = kmalloc(sizeof(*stat), GFP_KERNEL);
	if (!stat)
		return -ENOMEM;
O
Olof Johansson 已提交
2187

2188 2189
	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 已提交
2190

2191 2192 2193 2194 2195
	if (trie_local) {
		seq_printf(seq, "Local:\n");
		trie_collect_stats(trie_local, stat);
		trie_show_stats(seq, stat);
	}
O
Olof Johansson 已提交
2196

2197 2198 2199 2200
	if (trie_main) {
		seq_printf(seq, "Main:\n");
		trie_collect_stats(trie_main, stat);
		trie_show_stats(seq, stat);
2201
	}
2202
	kfree(stat);
2203

2204
	return 0;
2205 2206
}

2207
static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2208
{
2209
	return single_open(file, fib_triestat_seq_show, NULL);
2210 2211
}

2212
static const struct file_operations fib_triestat_fops = {
2213 2214 2215 2216 2217 2218 2219 2220 2221
	.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)
2222
{
2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236
	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;
	}
2237 2238 2239
	return NULL;
}

2240
static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2241
{
2242 2243
	rcu_read_lock();
	if (*pos == 0)
O
Olof Johansson 已提交
2244
		return SEQ_START_TOKEN;
2245
	return fib_trie_get_idx(seq->private, *pos - 1);
2246 2247
}

2248
static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2249
{
2250 2251 2252
	struct fib_trie_iter *iter = seq->private;
	void *l = v;

2253
	++*pos;
O
Olof Johansson 已提交
2254
	if (v == SEQ_START_TOKEN)
2255
		return fib_trie_get_idx(iter, 0);
2256

2257 2258 2259 2260
	v = fib_trie_get_next(iter);
	BUG_ON(v == l);
	if (v)
		return v;
2261

2262 2263 2264
	/* continue scan in next trie */
	if (iter->trie == trie_local)
		return fib_trie_get_first(iter, trie_main);
2265

2266 2267
	return NULL;
}
2268

2269
static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2270
{
2271 2272
	rcu_read_unlock();
}
O
Olof Johansson 已提交
2273

2274 2275 2276 2277
static void seq_indent(struct seq_file *seq, int n)
{
	while (n-- > 0) seq_puts(seq, "   ");
}
2278

2279 2280 2281
static inline const char *rtn_scope(enum rt_scope_t s)
{
	static char buf[32];
2282

S
Stephen Hemminger 已提交
2283
	switch (s) {
2284 2285 2286 2287 2288 2289 2290 2291 2292 2293
	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;
	}
}
2294

2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308
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",
};
2309

2310 2311 2312
static inline const char *rtn_type(unsigned t)
{
	static char buf[32];
2313

2314 2315 2316 2317
	if (t < __RTN_MAX && rtn_type_names[t])
		return rtn_type_names[t];
	snprintf(buf, sizeof(buf), "type %d", t);
	return buf;
2318 2319
}

2320 2321
/* Pretty print the trie */
static int fib_trie_seq_show(struct seq_file *seq, void *v)
2322
{
2323 2324
	const struct fib_trie_iter *iter = seq->private;
	struct node *n = v;
2325

2326 2327
	if (v == SEQ_START_TOKEN)
		return 0;
2328

S
Stephen Hemminger 已提交
2329
	if (!node_parent(n)) {
2330 2331 2332 2333 2334 2335
		if (iter->trie == trie_local)
			seq_puts(seq, "<local>:\n");
		else
			seq_puts(seq, "<main>:\n");
	}

2336 2337
	if (IS_TNODE(n)) {
		struct tnode *tn = (struct tnode *) n;
S
Stephen Hemminger 已提交
2338
		__be32 prf = htonl(mask_pfx(tn->key, tn->pos));
O
Olof Johansson 已提交
2339

2340 2341
		seq_indent(seq, iter->depth-1);
		seq_printf(seq, "  +-- %d.%d.%d.%d/%d %d %d %d\n",
2342
			   NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
2343
			   tn->empty_children);
2344

2345 2346 2347
	} else {
		struct leaf *l = (struct leaf *) n;
		int i;
A
Al Viro 已提交
2348
		__be32 val = htonl(l->key);
2349 2350 2351 2352

		seq_indent(seq, iter->depth);
		seq_printf(seq, "  |-- %d.%d.%d.%d\n", NIPQUAD(val));
		for (i = 32; i >= 0; i--) {
R
Robert Olsson 已提交
2353
			struct leaf_info *li = find_leaf_info(l, i);
2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367
			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');
				}
			}
		}
2368
	}
2369

2370 2371 2372
	return 0;
}

2373
static const struct seq_operations fib_trie_seq_ops = {
2374 2375 2376 2377
	.start  = fib_trie_seq_start,
	.next   = fib_trie_seq_next,
	.stop   = fib_trie_seq_stop,
	.show   = fib_trie_seq_show,
2378 2379
};

2380
static int fib_trie_seq_open(struct inode *inode, struct file *file)
2381
{
2382 2383
	return seq_open_private(file, &fib_trie_seq_ops,
			sizeof(struct fib_trie_iter));
2384 2385
}

2386
static const struct file_operations fib_trie_fops = {
2387 2388 2389 2390
	.owner  = THIS_MODULE,
	.open   = fib_trie_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2391
	.release = seq_release_private,
2392 2393
};

A
Al Viro 已提交
2394
static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2395
{
2396 2397 2398 2399
	static unsigned type2flags[RTN_MAX + 1] = {
		[7] = RTF_REJECT, [8] = RTF_REJECT,
	};
	unsigned flags = type2flags[type];
2400

2401 2402
	if (fi && fi->fib_nh->nh_gw)
		flags |= RTF_GATEWAY;
A
Al Viro 已提交
2403
	if (mask == htonl(0xFFFFFFFF))
2404 2405 2406
		flags |= RTF_HOST;
	flags |= RTF_UP;
	return flags;
2407 2408
}

2409 2410 2411 2412 2413 2414 2415
/*
 *	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)
2416
{
2417
	const struct fib_trie_iter *iter = seq->private;
2418 2419 2420
	struct leaf *l = v;
	int i;
	char bf[128];
2421

2422 2423 2424 2425 2426 2427
	if (v == SEQ_START_TOKEN) {
		seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
			   "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
			   "\tWindow\tIRTT");
		return 0;
	}
2428

2429 2430
	if (iter->trie == trie_local)
		return 0;
2431 2432
	if (IS_TNODE(l))
		return 0;
2433

2434
	for (i=32; i>=0; i--) {
R
Robert Olsson 已提交
2435
		struct leaf_info *li = find_leaf_info(l, i);
2436
		struct fib_alias *fa;
A
Al Viro 已提交
2437
		__be32 mask, prefix;
O
Olof Johansson 已提交
2438

2439 2440
		if (!li)
			continue;
2441

2442 2443
		mask = inet_make_mask(li->plen);
		prefix = htonl(l->key);
2444

2445
		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2446
			const struct fib_info *fi = fa->fa_info;
2447
			unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2448

2449 2450 2451
			if (fa->fa_type == RTN_BROADCAST
			    || fa->fa_type == RTN_MULTICAST)
				continue;
2452

2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468
			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);
2469

2470 2471
			seq_printf(seq, "%-127s\n", bf);
		}
2472 2473 2474 2475 2476
	}

	return 0;
}

2477
static const struct seq_operations fib_route_seq_ops = {
2478 2479 2480 2481
	.start  = fib_trie_seq_start,
	.next   = fib_trie_seq_next,
	.stop   = fib_trie_seq_stop,
	.show   = fib_route_seq_show,
2482 2483
};

2484
static int fib_route_seq_open(struct inode *inode, struct file *file)
2485
{
2486 2487
	return seq_open_private(file, &fib_route_seq_ops,
			sizeof(struct fib_trie_iter));
2488 2489
}

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

int __init fib_proc_init(void)
{
2500
	if (!proc_net_fops_create(&init_net, "fib_trie", S_IRUGO, &fib_trie_fops))
2501 2502
		goto out1;

2503
	if (!proc_net_fops_create(&init_net, "fib_triestat", S_IRUGO, &fib_triestat_fops))
2504 2505
		goto out2;

2506
	if (!proc_net_fops_create(&init_net, "route", S_IRUGO, &fib_route_fops))
2507 2508
		goto out3;

2509
	return 0;
2510 2511

out3:
2512
	proc_net_remove(&init_net, "fib_triestat");
2513
out2:
2514
	proc_net_remove(&init_net, "fib_trie");
2515 2516
out1:
	return -ENOMEM;
2517 2518 2519 2520
}

void __init fib_proc_exit(void)
{
2521 2522 2523
	proc_net_remove(&init_net, "fib_trie");
	proc_net_remove(&init_net, "fib_triestat");
	proc_net_remove(&init_net, "route");
2524 2525 2526
}

#endif /* CONFIG_PROC_FS */