fib_trie.c 57.9 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 44 45
/*
 *   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.
 */

46
#define VERSION "0.403"
47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

#include <linux/config.h>
#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>
#include <linux/netdevice.h>
#include <linux/if_arp.h>
#include <linux/proc_fs.h>
R
Robert Olsson 已提交
65
#include <linux/rcupdate.h>
66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
#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
#define MAX_CHILDS 16384

#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 已提交
90
#define NODE_PARENT(node) \
R
Robert Olsson 已提交
91 92 93 94 95 96 97
	((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 已提交
98 99 100

#define IS_TNODE(n) (!(n->parent & T_LEAF))
#define IS_LEAF(n) (n->parent & T_LEAF)
101 102

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

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

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

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

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

struct trie_stat {
	unsigned int totdepth;
	unsigned int maxdepth;
	unsigned int tnodes;
	unsigned int leaves;
	unsigned int nullpointers;
	unsigned int nodesizes[MAX_CHILDS];
150
};
151 152

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

168
static kmem_cache_t *fn_alias_kmem __read_mostly;
169 170
static struct trie *trie_local = NULL, *trie_main = NULL;

R
Robert Olsson 已提交
171 172 173

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

174
static inline struct node *tnode_get_child(struct tnode *tn, int i)
175
{
O
Olof Johansson 已提交
176
	BUG_ON(i >= 1 << tn->bits);
177

R
Robert Olsson 已提交
178
	return rcu_dereference(tn->child[i]);
179 180
}

S
Stephen Hemmigner 已提交
181
static inline int tnode_child_length(const struct tnode *tn)
182
{
O
Olof Johansson 已提交
183
	return 1 << tn->bits;
184 185 186 187
}

static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
{
O
Olof Johansson 已提交
188
	if (offset < KEYLENGTH)
189
		return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
O
Olof Johansson 已提交
190
	else
191 192 193 194 195
		return 0;
}

static inline int tkey_equals(t_key a, t_key b)
{
196
	return a == b;
197 198 199 200
}

static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
{
201 202
	if (bits == 0 || offset >= KEYLENGTH)
		return 1;
O
Olof Johansson 已提交
203 204
	bits = bits > KEYLENGTH ? KEYLENGTH : bits;
	return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
205
}
206 207 208 209 210 211

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

212 213 214
	if (!diff)
		return 0;
	while ((diff << i) >> (KEYLENGTH-1) == 0)
215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256
		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 
  necessitaded 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 
  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 已提交
257
  n->bits = 4
258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275

  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.
  
276

277 278 279 280 281
  The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
  at this point.

*/

S
Stephen Hemminger 已提交
282
static inline void check_tnode(const struct tnode *tn)
283
{
S
Stephen Hemminger 已提交
284
	WARN_ON(tn && tn->pos+tn->bits > 32);
285 286 287 288 289
}

static int halve_threshold = 25;
static int inflate_threshold = 50;

R
Robert Olsson 已提交
290 291

static void __alias_free_mem(struct rcu_head *head)
292
{
R
Robert Olsson 已提交
293 294
	struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
	kmem_cache_free(fn_alias_kmem, fa);
295 296
}

R
Robert Olsson 已提交
297
static inline void alias_free_mem_rcu(struct fib_alias *fa)
298
{
R
Robert Olsson 已提交
299 300
	call_rcu(&fa->rcu, __alias_free_mem);
}
O
Olof Johansson 已提交
301

R
Robert Olsson 已提交
302 303 304 305
static void __leaf_free_rcu(struct rcu_head *head)
{
	kfree(container_of(head, struct leaf, rcu));
}
O
Olof Johansson 已提交
306

R
Robert Olsson 已提交
307 308 309
static inline void free_leaf(struct leaf *leaf)
{
	call_rcu(&leaf->rcu, __leaf_free_rcu);
310 311
}

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

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

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

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

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

R
Robert Olsson 已提交
348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372
static inline void tnode_free(struct tnode *tn)
{
	call_rcu(&tn->rcu, __tnode_free_rcu);
}

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

373 374 375 376
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 *);
377
	struct tnode *tn = tnode_alloc(sz);
378

O
Olof Johansson 已提交
379
	if (tn) {
380
		memset(tn, 0, sz);
R
Robert Olsson 已提交
381
		tn->parent = T_TNODE;
382 383 384 385 386 387
		tn->pos = pos;
		tn->bits = bits;
		tn->key = key;
		tn->full_children = 0;
		tn->empty_children = 1<<bits;
	}
388

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

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

407
static inline void put_child(struct trie *t, struct tnode *tn, int i, struct node *n)
408 409 410 411
{
	tnode_put_child_reorg(tn, i, n, -1);
}

412
 /*
413 414 415 416
  * Add a child at position i overwriting the old value.
  * Update the value of full_children and empty_children.
  */

417
static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull)
418
{
R
Robert Olsson 已提交
419
	struct node *chi = tn->child[i];
420 421
	int isfull;

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

424 425 426 427 428 429

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

431
	/* update fullChildren */
O
Olof Johansson 已提交
432
	if (wasfull == -1)
433 434 435
		wasfull = tnode_full(tn, chi);

	isfull = tnode_full(tn, n);
436
	if (wasfull && !isfull)
437
		tn->full_children--;
438
	else if (!wasfull && isfull)
439
		tn->full_children++;
O
Olof Johansson 已提交
440

441 442
	if (n)
		NODE_SET_PARENT(n, tn);
443

R
Robert Olsson 已提交
444
	rcu_assign_pointer(tn->child[i], n);
445 446
}

447
static struct node *resize(struct trie *t, struct tnode *tn)
448 449
{
	int i;
450
	int err = 0;
451
	struct tnode *old_tn;
452 453 454 455

 	if (!tn)
		return NULL;

S
Stephen Hemminger 已提交
456 457
	pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
		 tn, inflate_threshold, halve_threshold);
458 459 460 461 462 463 464 465 466

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

O
Olof Johansson 已提交
469
			n = tn->child[i];
R
Robert Olsson 已提交
470
			if (!n)
O
Olof Johansson 已提交
471 472 473
				continue;

			/* compress one level */
R
Robert Olsson 已提交
474
			NODE_SET_PARENT(n, NULL);
O
Olof Johansson 已提交
475 476
			tnode_free(tn);
			return n;
477
		}
478
	/*
479 480 481 482 483
	 * Double as long as the resulting node has a number of
	 * nonempty nodes that are above the threshold.
	 */

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

	check_tnode(tn);
543

544
	err = 0;
545 546 547 548
	while ((tn->full_children > 0 &&
	       50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >=
				inflate_threshold * tnode_child_length(tn))) {

549 550 551 552
		old_tn = tn;
		tn = inflate(t, tn);
		if (IS_ERR(tn)) {
			tn = old_tn;
553 554 555 556 557
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.resize_node_skipped++;
#endif
			break;
		}
558 559 560 561 562 563 564 565
	}

	check_tnode(tn);

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

	err = 0;
568 569
	while (tn->bits > 1 &&
	       100 * (tnode_child_length(tn) - tn->empty_children) <
570 571
	       halve_threshold * tnode_child_length(tn)) {

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

583

584 585 586
	/* 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 已提交
587
			struct node *n;
588

O
Olof Johansson 已提交
589
			n = tn->child[i];
R
Robert Olsson 已提交
590
			if (!n)
O
Olof Johansson 已提交
591 592 593 594
				continue;

			/* compress one level */

R
Robert Olsson 已提交
595
			NODE_SET_PARENT(n, NULL);
O
Olof Johansson 已提交
596 597
			tnode_free(tn);
			return n;
598 599 600 601 602
		}

	return (struct node *) tn;
}

603
static struct tnode *inflate(struct trie *t, struct tnode *tn)
604 605 606 607 608 609
{
	struct tnode *inode;
	struct tnode *oldtnode = tn;
	int olen = tnode_child_length(tn);
	int i;

S
Stephen Hemminger 已提交
610
	pr_debug("In inflate\n");
611 612 613

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

S
Stephen Hemminger 已提交
614
	if (!tn)
615
		return ERR_PTR(-ENOMEM);
616 617

	/*
618 619 620
	 * 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
621 622
	 * of tnode is ignored.
	 */
O
Olof Johansson 已提交
623 624

	for (i = 0; i < olen; i++) {
625 626 627 628 629 630 631 632
		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);
633

634 635
			left = tnode_new(inode->key&(~m), inode->pos + 1,
					 inode->bits - 1);
636 637
			if (!left)
				goto nomem;
O
Olof Johansson 已提交
638

639 640 641
			right = tnode_new(inode->key|m, inode->pos + 1,
					  inode->bits - 1);

642 643 644 645
                        if (!right) {
				tnode_free(left);
				goto nomem;
                        }
646 647 648 649 650 651

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

O
Olof Johansson 已提交
652
	for (i = 0; i < olen; i++) {
653
		struct node *node = tnode_get_child(oldtnode, i);
O
Olof Johansson 已提交
654 655
		struct tnode *left, *right;
		int size, j;
656

657 658 659 660 661 662
		/* An empty child */
		if (node == NULL)
			continue;

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

663
		if (IS_LEAF(node) || ((struct tnode *) node)->pos >
664
		   tn->pos + tn->bits - 1) {
665
			if (tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits,
666 667 668 669 670 671 672 673 674 675 676 677 678 679 680
					     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 已提交
681
			continue;
682 683
		}

O
Olof Johansson 已提交
684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701
		/* 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)
		 */
702

O
Olof Johansson 已提交
703 704 705
		/* Use the old key, but set the new significant
		 *   bit to zero.
		 */
706

O
Olof Johansson 已提交
707 708
		left = (struct tnode *) tnode_get_child(tn, 2*i);
		put_child(t, tn, 2*i, NULL);
709

O
Olof Johansson 已提交
710
		BUG_ON(!left);
711

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

O
Olof Johansson 已提交
715
		BUG_ON(!right);
716

O
Olof Johansson 已提交
717 718 719 720
		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]);
721
		}
O
Olof Johansson 已提交
722 723 724 725
		put_child(t, tn, 2*i, resize(t, left));
		put_child(t, tn, 2*i+1, resize(t, right));

		tnode_free(inode);
726 727 728
	}
	tnode_free(oldtnode);
	return tn;
729 730 731 732 733
nomem:
	{
		int size = tnode_child_length(tn);
		int j;

S
Stephen Hemminger 已提交
734
		for (j = 0; j < size; j++)
735 736 737 738
			if (tn->child[j])
				tnode_free((struct tnode *)tn->child[j]);

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

740 741
		return ERR_PTR(-ENOMEM);
	}
742 743
}

744
static struct tnode *halve(struct trie *t, struct tnode *tn)
745 746 747 748 749 750
{
	struct tnode *oldtnode = tn;
	struct node *left, *right;
	int i;
	int olen = tnode_child_length(tn);

S
Stephen Hemminger 已提交
751
	pr_debug("In halve\n");
752 753

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

755 756
	if (!tn)
		return ERR_PTR(-ENOMEM);
757 758

	/*
759 760 761
	 * 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
762 763 764
	 * of tnode is ignored.
	 */

O
Olof Johansson 已提交
765
	for (i = 0; i < olen; i += 2) {
766 767
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
768

769
		/* Two nonempty children */
S
Stephen Hemminger 已提交
770
		if (left && right) {
771
			struct tnode *newn;
S
Stephen Hemminger 已提交
772

773
			newn = tnode_new(left->key, tn->pos + tn->bits, 1);
S
Stephen Hemminger 已提交
774 775

			if (!newn)
776
				goto nomem;
S
Stephen Hemminger 已提交
777

778
			put_child(t, tn, i/2, (struct node *)newn);
779 780 781
		}

	}
782

O
Olof Johansson 已提交
783 784 785
	for (i = 0; i < olen; i += 2) {
		struct tnode *newBinNode;

786 787
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
788

789 790 791 792 793
		/* 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 已提交
794
			continue;
S
Stephen Hemminger 已提交
795
		}
O
Olof Johansson 已提交
796 797

		if (right == NULL) {
798
			put_child(t, tn, i/2, left);
O
Olof Johansson 已提交
799 800
			continue;
		}
801

802
		/* Two nonempty children */
O
Olof Johansson 已提交
803 804 805 806 807
		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));
808 809 810
	}
	tnode_free(oldtnode);
	return tn;
811 812 813 814 815
nomem:
	{
		int size = tnode_child_length(tn);
		int j;

S
Stephen Hemminger 已提交
816
		for (j = 0; j < size; j++)
817 818 819 820
			if (tn->child[j])
				tnode_free((struct tnode *)tn->child[j]);

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

822 823
		return ERR_PTR(-ENOMEM);
	}
824 825
}

O
Olof Johansson 已提交
826
static void trie_init(struct trie *t)
827
{
O
Olof Johansson 已提交
828 829 830 831
	if (!t)
		return;

	t->size = 0;
R
Robert Olsson 已提交
832
	rcu_assign_pointer(t->trie, NULL);
O
Olof Johansson 已提交
833
	t->revision = 0;
834
#ifdef CONFIG_IP_FIB_TRIE_STATS
O
Olof Johansson 已提交
835
	memset(&t->stats, 0, sizeof(struct trie_use_stats));
836 837 838
#endif
}

R
Robert Olsson 已提交
839 840 841
/* readside most use rcu_read_lock currently dump routines
 via get_fa_head and dump */

842 843 844 845 846
static struct leaf_info *find_leaf_info(struct hlist_head *head, int plen)
{
	struct hlist_node *node;
	struct leaf_info *li;

R
Robert Olsson 已提交
847
	hlist_for_each_entry_rcu(li, node, head, hlist)
848
		if (li->plen == plen)
849
			return li;
O
Olof Johansson 已提交
850

851 852 853 854 855 856
	return NULL;
}

static inline struct list_head * get_fa_head(struct leaf *l, int plen)
{
	struct leaf_info *li = find_leaf_info(&l->list, plen);
857

O
Olof Johansson 已提交
858 859
	if (!li)
		return NULL;
860

O
Olof Johansson 已提交
861
	return &li->falh;
862 863 864 865
}

static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
{
R
Robert Olsson 已提交
866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882
        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);
        }
883 884
}

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

887 888 889 890 891 892 893 894
static struct leaf *
fib_find_node(struct trie *t, u32 key)
{
	int pos;
	struct tnode *tn;
	struct node *n;

	pos = 0;
R
Robert Olsson 已提交
895
	n = rcu_dereference(t->trie);
896 897 898

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

900
		check_tnode(tn);
O
Olof Johansson 已提交
901

902
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
O
Olof Johansson 已提交
903
			pos = tn->pos + tn->bits;
904
			n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
O
Olof Johansson 已提交
905
		} else
906 907 908 909
			break;
	}
	/* Case we have found a leaf. Compare prefixes */

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

913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930
	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 已提交
931

932
		if (!NODE_PARENT(tn))
933 934 935 936 937
			break;

		tn = NODE_PARENT(tn);
	}
	/* Handle last (top) tnode */
938
	if (IS_TNODE(tn))
939 940 941 942 943
		tn = (struct tnode*) resize(t, (struct tnode *)tn);

	return (struct node*) tn;
}

R
Robert Olsson 已提交
944 945
/* only used from updater-side */

946 947
static  struct list_head *
fib_insert_node(struct trie *t, int *err, u32 key, int plen)
948 949 950 951 952 953
{
	int pos, newpos;
	struct tnode *tp = NULL, *tn = NULL;
	struct node *n;
	struct leaf *l;
	int missbit;
954
	struct list_head *fa_head = NULL;
955 956 957 958
	struct leaf_info *li;
	t_key cindex;

	pos = 0;
959
	n = t->trie;
960

961 962
	/* 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,
963
	 * and we should just put our new leaf in that.
964 965
	 * 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
966 967
	 * not be the parent's 'pos'+'bits'!
	 *
968
	 * If it does match the current key, get pos/bits from it, extract
969 970 971 972
	 * 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.
	 *
973 974 975
	 * 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.
976 977 978 979 980
	 * 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 已提交
981

982
		check_tnode(tn);
O
Olof Johansson 已提交
983

984
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
985
			tp = tn;
O
Olof Johansson 已提交
986
			pos = tn->pos + tn->bits;
987 988
			n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));

S
Stephen Hemminger 已提交
989
			BUG_ON(n && NODE_PARENT(n) != tn);
O
Olof Johansson 已提交
990
		} else
991 992 993 994 995 996
			break;
	}

	/*
	 * n  ----> NULL, LEAF or TNODE
	 *
997
	 * tp is n's (parent) ----> NULL or TNODE
998 999
	 */

O
Olof Johansson 已提交
1000
	BUG_ON(tp && IS_LEAF(tp));
1001 1002 1003

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

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

1007
		li = leaf_info_new(plen);
O
Olof Johansson 已提交
1008

1009
		if (!li) {
1010 1011 1012
			*err = -ENOMEM;
			goto err;
		}
1013 1014 1015 1016 1017 1018 1019 1020

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

1021
	if (!l) {
1022 1023 1024
		*err = -ENOMEM;
		goto err;
	}
1025 1026 1027 1028

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

1029
	if (!li) {
1030 1031 1032 1033
		tnode_free((struct tnode *) l);
		*err = -ENOMEM;
		goto err;
	}
1034 1035 1036 1037 1038

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

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

		NODE_SET_PARENT(l, tp);

O
Olof Johansson 已提交
1043 1044 1045 1046
		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. */
1047 1048
		/*
		 *  Add a new tnode here
1049 1050 1051 1052
		 *  first tnode need some special handling
		 */

		if (tp)
O
Olof Johansson 已提交
1053
			pos = tp->pos+tp->bits;
1054
		else
O
Olof Johansson 已提交
1055 1056
			pos = 0;

1057
		if (n) {
1058 1059
			newpos = tkey_mismatch(key, pos, n->key);
			tn = tnode_new(n->key, newpos, 1);
O
Olof Johansson 已提交
1060
		} else {
1061
			newpos = 0;
1062
			tn = tnode_new(key, newpos, 1); /* First tnode */
1063 1064
		}

1065
		if (!tn) {
1066 1067 1068 1069
			free_leaf_info(li);
			tnode_free((struct tnode *) l);
			*err = -ENOMEM;
			goto err;
O
Olof Johansson 已提交
1070 1071
		}

1072 1073
		NODE_SET_PARENT(tn, tp);

O
Olof Johansson 已提交
1074
		missbit = tkey_extract_bits(key, newpos, 1);
1075 1076 1077
		put_child(t, tn, missbit, (struct node *)l);
		put_child(t, tn, 1-missbit, n);

1078
		if (tp) {
1079 1080
			cindex = tkey_extract_bits(key, tp->pos, tp->bits);
			put_child(t, (struct tnode *)tp, cindex, (struct node *)tn);
O
Olof Johansson 已提交
1081
		} else {
R
Robert Olsson 已提交
1082
			rcu_assign_pointer(t->trie, (struct node *)tn); /* First tnode */
1083 1084 1085
			tp = tn;
		}
	}
O
Olof Johansson 已提交
1086 1087

	if (tp && tp->pos + tp->bits > 32)
1088
		printk("ERROR tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1089
		       tp, tp->pos, tp->bits, key, plen);
O
Olof Johansson 已提交
1090

1091
	/* Rebalance the trie */
R
Robert Olsson 已提交
1092 1093

	rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
1094 1095
done:
	t->revision++;
O
Olof Johansson 已提交
1096
err:
1097 1098 1099 1100 1101 1102 1103 1104 1105
	return fa_head;
}

static int
fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
	       struct nlmsghdr *nlhdr, struct netlink_skb_parms *req)
{
	struct trie *t = (struct trie *) tb->tb_data;
	struct fib_alias *fa, *new_fa;
1106
	struct list_head *fa_head = NULL;
1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118
	struct fib_info *fi;
	int plen = r->rtm_dst_len;
	int type = r->rtm_type;
	u8 tos = r->rtm_tos;
	u32 key, mask;
	int err;
	struct leaf *l;

	if (plen > 32)
		return -EINVAL;

	key = 0;
1119
	if (rta->rta_dst)
1120 1121 1122 1123
		memcpy(&key, rta->rta_dst, 4);

	key = ntohl(key);

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

O
Olof Johansson 已提交
1126
	mask = ntohl(inet_make_mask(plen));
1127

1128
	if (key & ~mask)
1129 1130 1131 1132
		return -EINVAL;

	key = key & mask;

O
Olof Johansson 已提交
1133 1134 1135
	fi = fib_create_info(r, rta, nlhdr, &err);

	if (!fi)
1136 1137 1138
		goto err;

	l = fib_find_node(t, key);
1139
	fa = NULL;
1140

1141
	if (l) {
1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156
		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 已提交
1157
	if (fa && fa->fa_info->fib_priority == fi->fib_priority) {
1158 1159 1160 1161 1162 1163 1164 1165 1166 1167
		struct fib_alias *fa_orig;

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

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

R
Robert Olsson 已提交
1168 1169 1170 1171
			err = -ENOBUFS;
			new_fa = kmem_cache_alloc(fn_alias_kmem, SLAB_KERNEL);
			if (new_fa == NULL)
				goto out;
1172 1173

			fi_drop = fa->fa_info;
R
Robert Olsson 已提交
1174 1175 1176 1177
			new_fa->fa_tos = fa->fa_tos;
			new_fa->fa_info = fi;
			new_fa->fa_type = type;
			new_fa->fa_scope = r->rtm_scope;
1178
			state = fa->fa_state;
R
Robert Olsson 已提交
1179
			new_fa->fa_state &= ~FA_S_ACCESSED;
1180

R
Robert Olsson 已提交
1181 1182
			list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
			alias_free_mem_rcu(fa);
1183 1184 1185

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

O
Olof Johansson 已提交
1188
			goto succeeded;
1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209
		}
		/* Error if we find a perfect match which
		 * uses the same scope, type, and nexthop
		 * information.
		 */
		fa_orig = fa;
		list_for_each_entry(fa, fa_orig->fa_list.prev, fa_list) {
			if (fa->fa_tos != tos)
				break;
			if (fa->fa_info->fib_priority != fi->fib_priority)
				break;
			if (fa->fa_type == type &&
			    fa->fa_scope == r->rtm_scope &&
			    fa->fa_info == fi) {
				goto out;
			}
		}
		if (!(nlhdr->nlmsg_flags & NLM_F_APPEND))
			fa = fa_orig;
	}
	err = -ENOENT;
O
Olof Johansson 已提交
1210
	if (!(nlhdr->nlmsg_flags & NLM_F_CREATE))
1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226
		goto out;

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

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

1227
	if (!fa_head) {
1228 1229
		fa_head = fib_insert_node(t, &err, key, plen);
		err = 0;
1230
		if (err)
1231 1232
			goto out_free_new_fa;
	}
1233

R
Robert Olsson 已提交
1234 1235
	list_add_tail_rcu(&new_fa->fa_list,
			  (fa ? &fa->fa_list : fa_head));
1236 1237 1238 1239 1240

	rt_cache_flush(-1);
	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id, nlhdr, req);
succeeded:
	return 0;
1241 1242 1243

out_free_new_fa:
	kmem_cache_free(fn_alias_kmem, new_fa);
1244 1245
out:
	fib_release_info(fi);
O
Olof Johansson 已提交
1246
err:
1247 1248 1249
	return err;
}

R
Robert Olsson 已提交
1250 1251

/* should be clalled with rcu_read_lock */
S
Stephen Hemminger 已提交
1252 1253
static inline int check_leaf(struct trie *t, struct leaf *l,
			     t_key key, int *plen, const struct flowi *flp,
1254
			     struct fib_result *res)
1255
{
1256
	int err, i;
1257 1258 1259 1260
	t_key mask;
	struct leaf_info *li;
	struct hlist_head *hhead = &l->list;
	struct hlist_node *node;
1261

R
Robert Olsson 已提交
1262
	hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1263 1264
		i = li->plen;
		mask = ntohl(inet_make_mask(i));
1265
		if (l->key != (key & mask))
1266 1267
			continue;

1268
		if ((err = fib_semantic_match(&li->falh, flp, res, l->key, mask, i)) <= 0) {
1269 1270 1271 1272
			*plen = i;
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.semantic_match_passed++;
#endif
1273
			return err;
1274 1275 1276 1277 1278
		}
#ifdef CONFIG_IP_FIB_TRIE_STATS
		t->stats.semantic_match_miss++;
#endif
	}
1279
	return 1;
1280 1281 1282 1283 1284 1285 1286 1287 1288 1289
}

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 已提交
1290
	t_key key = ntohl(flp->fl4_dst);
1291 1292 1293
	int chopped_off;
	t_key cindex = 0;
	int current_prefix_length = KEYLENGTH;
O
Olof Johansson 已提交
1294 1295 1296 1297
	struct tnode *cn;
	t_key node_prefix, key_prefix, pref_mismatch;
	int mp;

R
Robert Olsson 已提交
1298
	rcu_read_lock();
O
Olof Johansson 已提交
1299

R
Robert Olsson 已提交
1300
	n = rcu_dereference(t->trie);
1301
	if (!n)
1302 1303 1304 1305 1306 1307 1308 1309
		goto failed;

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

	/* Just a leaf? */
	if (IS_LEAF(n)) {
1310
		if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
1311 1312 1313 1314 1315
			goto found;
		goto failed;
	}
	pn = (struct tnode *) n;
	chopped_off = 0;
1316

O
Olof Johansson 已提交
1317
	while (pn) {
1318 1319 1320
		pos = pn->pos;
		bits = pn->bits;

1321
		if (!chopped_off)
1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332
			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 已提交
1333 1334 1335 1336 1337 1338 1339
		if (IS_LEAF(n)) {
			if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
				goto found;
			else
				goto backtrace;
		}

1340 1341
#define HL_OPTIMIZE
#ifdef HL_OPTIMIZE
O
Olof Johansson 已提交
1342
		cn = (struct tnode *)n;
1343

O
Olof Johansson 已提交
1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358
		/*
		 * 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].
		 */
1359

O
Olof Johansson 已提交
1360 1361 1362 1363 1364 1365 1366 1367 1368
		/* 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.
		 */
1369

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

O
Olof Johansson 已提交
1372 1373 1374 1375 1376 1377
		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;
		}
1378

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

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

O
Olof Johansson 已提交
1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427
		/* 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;
1428
		}
O
Olof Johansson 已提交
1429 1430 1431 1432 1433
#endif
		pn = (struct tnode *)n; /* Descend */
		chopped_off = 0;
		continue;

1434 1435 1436 1437
backtrace:
		chopped_off++;

		/* As zero don't change the child key (cindex) */
O
Olof Johansson 已提交
1438
		while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1))))
1439 1440 1441 1442 1443
			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 已提交
1444

1445
		/*
1446
		 * Either we do the actual chop off according or if we have
1447 1448 1449
		 * chopped off all bits in this tnode walk up to our parent.
		 */

O
Olof Johansson 已提交
1450
		if (chopped_off <= pn->bits) {
1451
			cindex &= ~(1 << (chopped_off-1));
O
Olof Johansson 已提交
1452
		} else {
1453
			if (NODE_PARENT(pn) == NULL)
1454
				goto failed;
O
Olof Johansson 已提交
1455

1456 1457 1458 1459 1460 1461 1462 1463 1464
			/* 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;
1465
		}
1466 1467
	}
failed:
1468
	ret = 1;
1469
found:
R
Robert Olsson 已提交
1470
	rcu_read_unlock();
1471 1472 1473
	return ret;
}

R
Robert Olsson 已提交
1474
/* only called from updater side */
1475 1476 1477 1478 1479 1480 1481
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 已提交
1482
	pr_debug("entering trie_leaf_remove(%p)\n", n);
1483 1484

	/* Note that in the case skipped bits, those bits are *not* checked!
1485
	 * When we finish this, we will have NULL or a T_LEAF, and the
1486 1487 1488
	 * T_LEAF may or may not match our key.
	 */

O
Olof Johansson 已提交
1489
	while (n != NULL && IS_TNODE(n)) {
1490 1491 1492 1493
		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 已提交
1494
		BUG_ON(n && NODE_PARENT(n) != tn);
O
Olof Johansson 已提交
1495
	}
1496 1497
	l = (struct leaf *) n;

1498
	if (!n || !tkey_equals(l->key, key))
1499
		return 0;
1500 1501 1502 1503

	/*
	 * Key found.
	 * Remove the leaf and rebalance the tree
1504 1505 1506 1507 1508
	 */

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

R
Robert Olsson 已提交
1509
	preempt_disable();
1510 1511 1512
	tp = NODE_PARENT(n);
	tnode_free((struct tnode *) n);

1513
	if (tp) {
1514 1515
		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
		put_child(t, (struct tnode *)tp, cindex, NULL);
R
Robert Olsson 已提交
1516
		rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
O
Olof Johansson 已提交
1517
	} else
R
Robert Olsson 已提交
1518 1519
		rcu_assign_pointer(t->trie, NULL);
	preempt_enable();
1520 1521 1522 1523 1524 1525

	return 1;
}

static int
fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
O
Olof Johansson 已提交
1526
		struct nlmsghdr *nlhdr, struct netlink_skb_parms *req)
1527 1528 1529 1530 1531 1532 1533 1534
{
	struct trie *t = (struct trie *) tb->tb_data;
	u32 key, mask;
	int plen = r->rtm_dst_len;
	u8 tos = r->rtm_tos;
	struct fib_alias *fa, *fa_to_delete;
	struct list_head *fa_head;
	struct leaf *l;
O
Olof Johansson 已提交
1535 1536
	struct leaf_info *li;

1537

1538
	if (plen > 32)
1539 1540 1541
		return -EINVAL;

	key = 0;
1542
	if (rta->rta_dst)
1543 1544 1545
		memcpy(&key, rta->rta_dst, 4);

	key = ntohl(key);
O
Olof Johansson 已提交
1546
	mask = ntohl(inet_make_mask(plen));
1547

1548
	if (key & ~mask)
1549 1550 1551 1552 1553
		return -EINVAL;

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

1554
	if (!l)
1555 1556 1557 1558 1559 1560 1561 1562
		return -ESRCH;

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

	if (!fa)
		return -ESRCH;

S
Stephen Hemminger 已提交
1563
	pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1564 1565 1566

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

1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585
	list_for_each_entry(fa, fa_head, fa_list) {
		struct fib_info *fi = fa->fa_info;

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

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

O
Olof Johansson 已提交
1586 1587
	if (!fa_to_delete)
		return -ESRCH;
1588

O
Olof Johansson 已提交
1589 1590 1591 1592 1593
	fa = fa_to_delete;
	rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id, nlhdr, req);

	l = fib_find_node(t, key);
	li = find_leaf_info(&l->list, plen);
1594

R
Robert Olsson 已提交
1595
	list_del_rcu(&fa->fa_list);
1596

O
Olof Johansson 已提交
1597
	if (list_empty(fa_head)) {
R
Robert Olsson 已提交
1598
		hlist_del_rcu(&li->hlist);
O
Olof Johansson 已提交
1599
		free_leaf_info(li);
R
Robert Olsson 已提交
1600
	}
1601

O
Olof Johansson 已提交
1602 1603
	if (hlist_empty(&l->list))
		trie_leaf_remove(t, key);
1604

O
Olof Johansson 已提交
1605 1606
	if (fa->fa_state & FA_S_ACCESSED)
		rt_cache_flush(-1);
1607

R
Robert Olsson 已提交
1608 1609
	fib_release_info(fa->fa_info);
	alias_free_mem_rcu(fa);
O
Olof Johansson 已提交
1610
	return 0;
1611 1612 1613 1614 1615 1616 1617 1618 1619 1620
}

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 已提交
1621 1622 1623 1624
		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);
1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641
			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 已提交
1642
			hlist_del_rcu(&li->hlist);
1643 1644 1645 1646 1647 1648
			free_leaf_info(li);
		}
	}
	return found;
}

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

1651 1652 1653 1654 1655
static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
{
	struct node *c = (struct node *) thisleaf;
	struct tnode *p;
	int idx;
R
Robert Olsson 已提交
1656
	struct node *trie = rcu_dereference(t->trie);
1657

1658
	if (c == NULL) {
R
Robert Olsson 已提交
1659
		if (trie == NULL)
1660 1661
			return NULL;

R
Robert Olsson 已提交
1662 1663
		if (IS_LEAF(trie))          /* trie w. just a leaf */
			return (struct leaf *) trie;
1664

R
Robert Olsson 已提交
1665
		p = (struct tnode*) trie;  /* Start */
O
Olof Johansson 已提交
1666
	} else
1667
		p = (struct tnode *) NODE_PARENT(c);
1668

1669 1670 1671 1672
	while (p) {
		int pos, last;

		/*  Find the next child of the parent */
1673 1674 1675
		if (c)
			pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits);
		else
1676 1677 1678
			pos = 0;

		last = 1 << p->bits;
O
Olof Johansson 已提交
1679
		for (idx = pos; idx < last ; idx++) {
R
Robert Olsson 已提交
1680 1681 1682
			c = rcu_dereference(p->child[idx]);

			if (!c)
O
Olof Johansson 已提交
1683 1684 1685
				continue;

			/* Decend if tnode */
R
Robert Olsson 已提交
1686 1687 1688
			while (IS_TNODE(c)) {
				p = (struct tnode *) c;
  				idx = 0;
O
Olof Johansson 已提交
1689 1690 1691

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

				/* Done with this tnode? */
R
Robert Olsson 已提交
1696
				if (idx >= (1 << p->bits) || !c)
O
Olof Johansson 已提交
1697
					goto up;
1698
			}
R
Robert Olsson 已提交
1699
			return (struct leaf *) c;
1700 1701 1702
		}
up:
		/* No more children go up one step  */
O
Olof Johansson 已提交
1703
		c = (struct node *) p;
1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716
		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++;

R
Robert Olsson 已提交
1717
	rcu_read_lock();
O
Olof Johansson 已提交
1718
	for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1719 1720 1721 1722 1723 1724
		found += trie_flush_leaf(t, l);

		if (ll && hlist_empty(&ll->list))
			trie_leaf_remove(t, ll->key);
		ll = l;
	}
R
Robert Olsson 已提交
1725
	rcu_read_unlock();  
1726 1727 1728 1729

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

S
Stephen Hemminger 已提交
1730
	pr_debug("trie_flush found=%d\n", found);
1731 1732 1733
	return found;
}

O
Olof Johansson 已提交
1734
static int trie_last_dflt = -1;
1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750

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 已提交
1751
	rcu_read_lock();
1752

1753
	l = fib_find_node(t, 0);
1754
	if (!l)
1755 1756 1757
		goto out;

	fa_head = get_fa_head(l, 0);
1758
	if (!fa_head)
1759 1760
		goto out;

1761
	if (list_empty(fa_head))
1762 1763
		goto out;

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

1767 1768 1769
		if (fa->fa_scope != res->scope ||
		    fa->fa_type != RTN_UNICAST)
			continue;
O
Olof Johansson 已提交
1770

1771 1772 1773 1774 1775 1776
		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 已提交
1777

1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 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
		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 已提交
1815
	rcu_read_unlock();
1816 1817
}

1818
static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fib_table *tb,
1819 1820 1821 1822 1823
			   struct sk_buff *skb, struct netlink_callback *cb)
{
	int i, s_i;
	struct fib_alias *fa;

O
Olof Johansson 已提交
1824
	u32 xkey = htonl(key);
1825

O
Olof Johansson 已提交
1826
	s_i = cb->args[3];
1827 1828
	i = 0;

R
Robert Olsson 已提交
1829 1830 1831
	/* rcu_read_lock is hold by caller */

	list_for_each_entry_rcu(fa, fah, fa_list) {
1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855
		if (i < s_i) {
			i++;
			continue;
		}
		if (fa->fa_info->fib_nh == NULL) {
			printk("Trie error _fib_nh=NULL in fa[%d] k=%08x plen=%d\n", i, key, plen);
			i++;
			continue;
		}
		if (fa->fa_info == NULL) {
			printk("Trie error fa_info=NULL in fa[%d] k=%08x plen=%d\n", i, key, plen);
			i++;
			continue;
		}

		if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
				  cb->nlh->nlmsg_seq,
				  RTM_NEWROUTE,
				  tb->tb_id,
				  fa->fa_type,
				  fa->fa_scope,
				  &xkey,
				  plen,
				  fa->fa_tos,
1856
				  fa->fa_info, 0) < 0) {
1857 1858
			cb->args[3] = i;
			return -1;
O
Olof Johansson 已提交
1859
		}
1860 1861
		i++;
	}
O
Olof Johansson 已提交
1862
	cb->args[3] = i;
1863 1864 1865
	return skb->len;
}

1866
static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb,
1867 1868 1869 1870 1871 1872
			     struct netlink_callback *cb)
{
	int h, s_h;
	struct list_head *fa_head;
	struct leaf *l = NULL;

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

O
Olof Johansson 已提交
1875
	for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1876 1877 1878 1879 1880 1881 1882
		if (h < s_h)
			continue;
		if (h > s_h)
			memset(&cb->args[3], 0,
			       sizeof(cb->args) - 3*sizeof(cb->args[0]));

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

1884
		if (!fa_head)
1885 1886
			continue;

1887
		if (list_empty(fa_head))
1888 1889 1890
			continue;

		if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
O
Olof Johansson 已提交
1891
			cb->args[2] = h;
1892 1893 1894
			return -1;
		}
	}
O
Olof Johansson 已提交
1895
	cb->args[2] = h;
1896 1897 1898 1899 1900 1901 1902 1903 1904 1905
	return skb->len;
}

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

	s_m = cb->args[1];

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

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

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

#ifdef CONFIG_IP_MULTIPLE_TABLES
struct fib_table * fib_hash_init(int id)
#else
struct fib_table * __init fib_hash_init(int id)
#endif
{
	struct fib_table *tb;
	struct trie *t;

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

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

	tb->tb_id = id;
	tb->tb_lookup = fn_trie_lookup;
	tb->tb_insert = fn_trie_insert;
	tb->tb_delete = fn_trie_delete;
	tb->tb_flush = fn_trie_flush;
	tb->tb_select_default = fn_trie_select_default;
	tb->tb_dump = fn_trie_dump;
	memset(tb->tb_data, 0, sizeof(struct trie));

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

	trie_init(t);

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

	if (id == RT_TABLE_LOCAL)
		printk("IPv4 FIB: Using LC-trie version %s\n", VERSION);

	return tb;
}

1973 1974 1975 1976 1977 1978 1979 1980
#ifdef CONFIG_PROC_FS
/* Depth first Trie walk iterator */
struct fib_trie_iter {
	struct tnode *tnode;
	struct trie *trie;
	unsigned index;
	unsigned depth;
};
1981

1982
static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
1983
{
1984 1985 1986
	struct tnode *tn = iter->tnode;
	unsigned cindex = iter->index;
	struct tnode *p;
1987

1988 1989 1990 1991 1992
	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);
1993

1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005
		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;
		}
2006

2007 2008
		++cindex;
	}
O
Olof Johansson 已提交
2009

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

	/* got root? */
	return NULL;
2021 2022
}

2023 2024
static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
				       struct trie *t)
2025
{
2026
	struct node *n = rcu_dereference(t->trie);
2027

2028 2029 2030 2031
	if (n && IS_TNODE(n)) {
		iter->tnode = (struct tnode *) n;
		iter->trie = t;
		iter->index = 0;
2032
		iter->depth = 1;
2033
		return n;
O
Olof Johansson 已提交
2034
	}
2035 2036
	return NULL;
}
O
Olof Johansson 已提交
2037

2038 2039 2040 2041
static void trie_collect_stats(struct trie *t, struct trie_stat *s)
{
	struct node *n;
	struct fib_trie_iter iter;
O
Olof Johansson 已提交
2042

2043
	memset(s, 0, sizeof(*s));
O
Olof Johansson 已提交
2044

2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061
	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->nodesizes[tn->bits]++;
			for (i = 0; i < (1<<tn->bits); i++)
				if (!tn->child[i])
					s->nullpointers++;
2062 2063
		}
	}
R
Robert Olsson 已提交
2064
	rcu_read_unlock();
2065 2066
}

2067 2068 2069 2070
/*
 *	This outputs /proc/net/fib_triestats
 */
static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2071
{
2072
	unsigned i, max, pointers, bytes, avdepth;
2073

2074 2075 2076 2077
	if (stat->leaves)
		avdepth = stat->totdepth*100 / stat->leaves;
	else
		avdepth = 0;
O
Olof Johansson 已提交
2078

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

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

2084 2085 2086
	bytes = sizeof(struct leaf) * stat->leaves;
	seq_printf(seq, "\tInternal nodes: %d\n\t", stat->tnodes);
	bytes += sizeof(struct tnode) * stat->tnodes;
2087

2088 2089 2090
	max = MAX_CHILDS-1;
	while (max >= 0 && stat->nodesizes[max] == 0)
		max--;
2091

2092 2093 2094 2095 2096 2097 2098 2099
	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 已提交
2100

2101 2102 2103
	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 已提交
2104

2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117
#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 */
}
2118

2119 2120 2121
static int fib_triestat_seq_show(struct seq_file *seq, void *v)
{
	struct trie_stat *stat;
O
Olof Johansson 已提交
2122

2123 2124 2125
	stat = kmalloc(sizeof(*stat), GFP_KERNEL);
	if (!stat)
		return -ENOMEM;
O
Olof Johansson 已提交
2126

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

2130 2131 2132 2133 2134
	if (trie_local) {
		seq_printf(seq, "Local:\n");
		trie_collect_stats(trie_local, stat);
		trie_show_stats(seq, stat);
	}
O
Olof Johansson 已提交
2135

2136 2137 2138 2139
	if (trie_main) {
		seq_printf(seq, "Main:\n");
		trie_collect_stats(trie_main, stat);
		trie_show_stats(seq, stat);
2140
	}
2141
	kfree(stat);
2142

2143
	return 0;
2144 2145
}

2146
static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2147
{
2148
	return single_open(file, fib_triestat_seq_show, NULL);
2149 2150
}

2151 2152 2153 2154 2155 2156 2157 2158 2159 2160
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)
2161
{
2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175
	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;
	}
2176 2177 2178
	return NULL;
}

2179
static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2180
{
2181 2182
	rcu_read_lock();
	if (*pos == 0)
O
Olof Johansson 已提交
2183
		return SEQ_START_TOKEN;
2184
	return fib_trie_get_idx(seq->private, *pos - 1);
2185 2186
}

2187
static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2188
{
2189 2190 2191
	struct fib_trie_iter *iter = seq->private;
	void *l = v;

2192
	++*pos;
O
Olof Johansson 已提交
2193
	if (v == SEQ_START_TOKEN)
2194
		return fib_trie_get_idx(iter, 0);
2195

2196 2197 2198 2199
	v = fib_trie_get_next(iter);
	BUG_ON(v == l);
	if (v)
		return v;
2200

2201 2202 2203
	/* continue scan in next trie */
	if (iter->trie == trie_local)
		return fib_trie_get_first(iter, trie_main);
2204

2205 2206
	return NULL;
}
2207

2208
static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2209
{
2210 2211
	rcu_read_unlock();
}
O
Olof Johansson 已提交
2212

2213 2214 2215 2216
static void seq_indent(struct seq_file *seq, int n)
{
	while (n-- > 0) seq_puts(seq, "   ");
}
2217

2218 2219 2220
static inline const char *rtn_scope(enum rt_scope_t s)
{
	static char buf[32];
2221

2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232
	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;
	}
}
2233

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

2249 2250 2251
static inline const char *rtn_type(unsigned t)
{
	static char buf[32];
2252

2253 2254 2255 2256
	if (t < __RTN_MAX && rtn_type_names[t])
		return rtn_type_names[t];
	snprintf(buf, sizeof(buf), "type %d", t);
	return buf;
2257 2258
}

2259 2260
/* Pretty print the trie */
static int fib_trie_seq_show(struct seq_file *seq, void *v)
2261
{
2262 2263
	const struct fib_trie_iter *iter = seq->private;
	struct node *n = v;
2264

2265 2266
	if (v == SEQ_START_TOKEN)
		return 0;
2267

2268 2269 2270
	if (IS_TNODE(n)) {
		struct tnode *tn = (struct tnode *) n;
		t_key prf = ntohl(MASK_PFX(tn->key, tn->pos));
O
Olof Johansson 已提交
2271

2272 2273 2274 2275 2276
		if (!NODE_PARENT(n)) {
			if (iter->trie == trie_local)
				seq_puts(seq, "<local>:\n");
			else
				seq_puts(seq, "<main>:\n");
2277 2278 2279 2280 2281 2282
		} 
		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);
		
2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305
	} else {
		struct leaf *l = (struct leaf *) n;
		int i;
		u32 val = ntohl(l->key);

		seq_indent(seq, iter->depth);
		seq_printf(seq, "  |-- %d.%d.%d.%d\n", NIPQUAD(val));
		for (i = 32; i >= 0; i--) {
			struct leaf_info *li = find_leaf_info(&l->list, i);
			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');
				}
			}
		}
2306
	}
2307

2308 2309 2310
	return 0;
}

2311 2312 2313 2314 2315
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,
2316 2317
};

2318
static int fib_trie_seq_open(struct inode *inode, struct file *file)
2319 2320 2321
{
	struct seq_file *seq;
	int rc = -ENOMEM;
2322
	struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
2323

2324 2325 2326 2327
	if (!s)
		goto out;

	rc = seq_open(file, &fib_trie_seq_ops);
2328 2329 2330
	if (rc)
		goto out_kfree;

2331 2332 2333
	seq	     = file->private_data;
	seq->private = s;
	memset(s, 0, sizeof(*s));
2334 2335 2336
out:
	return rc;
out_kfree:
2337
	kfree(s);
2338 2339 2340
	goto out;
}

2341 2342 2343 2344 2345
static struct file_operations fib_trie_fops = {
	.owner  = THIS_MODULE,
	.open   = fib_trie_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2346
	.release = seq_release_private,
2347 2348
};

2349
static unsigned fib_flag_trans(int type, u32 mask, const struct fib_info *fi)
2350
{
2351 2352 2353 2354
	static unsigned type2flags[RTN_MAX + 1] = {
		[7] = RTF_REJECT, [8] = RTF_REJECT,
	};
	unsigned flags = type2flags[type];
2355

2356 2357 2358 2359 2360 2361
	if (fi && fi->fib_nh->nh_gw)
		flags |= RTF_GATEWAY;
	if (mask == 0xFFFFFFFF)
		flags |= RTF_HOST;
	flags |= RTF_UP;
	return flags;
2362 2363
}

2364 2365 2366 2367 2368 2369 2370
/*
 *	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)
2371
{
2372 2373 2374
	struct leaf *l = v;
	int i;
	char bf[128];
2375

2376 2377 2378 2379 2380 2381
	if (v == SEQ_START_TOKEN) {
		seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
			   "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
			   "\tWindow\tIRTT");
		return 0;
	}
2382

2383 2384
	if (IS_TNODE(l))
		return 0;
2385

2386 2387 2388 2389
	for (i=32; i>=0; i--) {
		struct leaf_info *li = find_leaf_info(&l->list, i);
		struct fib_alias *fa;
		u32 mask, prefix;
O
Olof Johansson 已提交
2390

2391 2392
		if (!li)
			continue;
2393

2394 2395
		mask = inet_make_mask(li->plen);
		prefix = htonl(l->key);
2396

2397 2398 2399
		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
			const struct fib_info *fi = rcu_dereference(fa->fa_info);
			unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2400

2401 2402 2403
			if (fa->fa_type == RTN_BROADCAST
			    || fa->fa_type == RTN_MULTICAST)
				continue;
2404

2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420
			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);
2421

2422 2423
			seq_printf(seq, "%-127s\n", bf);
		}
2424 2425 2426 2427 2428
	}

	return 0;
}

2429 2430 2431 2432 2433
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,
2434 2435
};

2436
static int fib_route_seq_open(struct inode *inode, struct file *file)
2437 2438 2439
{
	struct seq_file *seq;
	int rc = -ENOMEM;
2440
	struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
2441

2442 2443 2444 2445
	if (!s)
		goto out;

	rc = seq_open(file, &fib_route_seq_ops);
2446 2447 2448
	if (rc)
		goto out_kfree;

2449 2450 2451
	seq	     = file->private_data;
	seq->private = s;
	memset(s, 0, sizeof(*s));
2452 2453 2454
out:
	return rc;
out_kfree:
2455
	kfree(s);
2456 2457 2458
	goto out;
}

2459 2460 2461 2462 2463 2464
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,
2465 2466 2467 2468
};

int __init fib_proc_init(void)
{
2469 2470 2471 2472 2473 2474 2475 2476 2477
	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;

2478
	return 0;
2479 2480 2481 2482 2483 2484 2485

out3:
	proc_net_remove("fib_triestat");
out2:
	proc_net_remove("fib_trie");
out1:
	return -ENOMEM;
2486 2487 2488 2489 2490
}

void __init fib_proc_exit(void)
{
	proc_net_remove("fib_trie");
2491 2492
	proc_net_remove("fib_triestat");
	proc_net_remove("route");
2493 2494 2495
}

#endif /* CONFIG_PROC_FS */