fib_trie.c 61.4 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
 *   Hans Liss <hans.liss@its.uu.se>  Uppsala Universitet
 *
L
Lucas De Marchi 已提交
15
 * This work is based on the LPC-trie which is originally described in:
16
 *
17 18
 * An experimental study of compression methods for dynamic tries
 * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
19
 * http://www.csc.kth.se/~snilsson/software/dyntrie2/
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
 *
 *
 * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
 * IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999
 *
 *
 * 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 已提交
42 43 44 45 46 47 48
 *
 * 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>
49 50
 */

J
Jens Låås 已提交
51
#define VERSION "0.409"
52 53

#include <asm/uaccess.h>
J
Jiri Slaby 已提交
54
#include <linux/bitops.h>
55 56 57 58 59 60 61 62 63
#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 已提交
64
#include <linux/inetdevice.h>
65 66 67
#include <linux/netdevice.h>
#include <linux/if_arp.h>
#include <linux/proc_fs.h>
R
Robert Olsson 已提交
68
#include <linux/rcupdate.h>
69 70 71 72
#include <linux/skbuff.h>
#include <linux/netlink.h>
#include <linux/init.h>
#include <linux/list.h>
73
#include <linux/slab.h>
74
#include <linux/prefetch.h>
75
#include <linux/export.h>
76
#include <net/net_namespace.h>
77 78 79 80 81 82 83 84
#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"

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

#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 已提交
94 95
#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)

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

99
struct rt_trie_node {
O
Olof Johansson 已提交
100
	unsigned long parent;
101
	t_key key;
102 103 104
};

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

struct leaf_info {
	struct hlist_node hlist;
	int plen;
114
	u32 mask_plen; /* ntohl(inet_make_mask(plen)) */
115
	struct list_head falh;
116
	struct rcu_head rcu;
117 118 119
};

struct tnode {
O
Olof Johansson 已提交
120
	unsigned long parent;
121
	t_key key;
122 123
	unsigned char pos;		/* 2log(KEYLENGTH) bits needed */
	unsigned char bits;		/* 2log(KEYLENGTH) bits needed */
124 125
	unsigned int full_children;	/* KEYLENGTH bits needed */
	unsigned int empty_children;	/* KEYLENGTH bits needed */
126 127 128
	union {
		struct rcu_head rcu;
		struct work_struct work;
J
Jarek Poplawski 已提交
129
		struct tnode *tnode_free;
130
	};
E
Eric Dumazet 已提交
131
	struct rt_trie_node __rcu *child[0];
132 133 134 135 136 137 138 139 140
};

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

struct trie_stat {
	unsigned int totdepth;
	unsigned int maxdepth;
	unsigned int tnodes;
	unsigned int leaves;
	unsigned int nullpointers;
151
	unsigned int prefixes;
R
Robert Olsson 已提交
152
	unsigned int nodesizes[MAX_STAT_DEPTH];
153
};
154 155

struct trie {
E
Eric Dumazet 已提交
156
	struct rt_trie_node __rcu *trie;
157 158 159 160 161
#ifdef CONFIG_IP_FIB_TRIE_STATS
	struct trie_use_stats stats;
#endif
};

162
static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
163
				  int wasfull);
164
static struct rt_trie_node *resize(struct trie *t, struct tnode *tn);
165 166
static struct tnode *inflate(struct trie *t, struct tnode *tn);
static struct tnode *halve(struct trie *t, struct tnode *tn);
J
Jarek Poplawski 已提交
167 168
/* tnodes to free after resize(); protected by RTNL */
static struct tnode *tnode_free_head;
169 170 171 172 173 174 175 176
static size_t tnode_free_size;

/*
 * synchronize_rcu after call_rcu for that many pages; it should be especially
 * useful before resizing the root node with PREEMPT_NONE configs; the value was
 * obtained experimentally, aiming to avoid visible slowdown.
 */
static const int sync_pages = 128;
177

178
static struct kmem_cache *fn_alias_kmem __read_mostly;
179
static struct kmem_cache *trie_leaf_kmem __read_mostly;
180

E
Eric Dumazet 已提交
181 182 183 184
/*
 * caller must hold RTNL
 */
static inline struct tnode *node_parent(const struct rt_trie_node *node)
S
Stephen Hemminger 已提交
185
{
E
Eric Dumazet 已提交
186 187 188 189 190
	unsigned long parent;

	parent = rcu_dereference_index_check(node->parent, lockdep_rtnl_is_held());

	return (struct tnode *)(parent & ~NODE_TYPE_MASK);
191 192
}

E
Eric Dumazet 已提交
193 194 195 196
/*
 * caller must hold RCU read lock or RTNL
 */
static inline struct tnode *node_parent_rcu(const struct rt_trie_node *node)
197
{
E
Eric Dumazet 已提交
198 199 200 201
	unsigned long parent;

	parent = rcu_dereference_index_check(node->parent, rcu_read_lock_held() ||
							   lockdep_rtnl_is_held());
S
Stephen Hemminger 已提交
202

E
Eric Dumazet 已提交
203
	return (struct tnode *)(parent & ~NODE_TYPE_MASK);
S
Stephen Hemminger 已提交
204 205
}

206
/* Same as rcu_assign_pointer
207 208
 * but that macro() assumes that value is a pointer.
 */
209
static inline void node_set_parent(struct rt_trie_node *node, struct tnode *ptr)
S
Stephen Hemminger 已提交
210
{
211 212
	smp_wmb();
	node->parent = (unsigned long)ptr | NODE_TYPE(node);
S
Stephen Hemminger 已提交
213
}
R
Robert Olsson 已提交
214

E
Eric Dumazet 已提交
215 216 217 218
/*
 * caller must hold RTNL
 */
static inline struct rt_trie_node *tnode_get_child(const struct tnode *tn, unsigned int i)
219 220
{
	BUG_ON(i >= 1U << tn->bits);
R
Robert Olsson 已提交
221

E
Eric Dumazet 已提交
222
	return rtnl_dereference(tn->child[i]);
223 224
}

E
Eric Dumazet 已提交
225 226 227 228
/*
 * caller must hold RCU read lock or RTNL
 */
static inline struct rt_trie_node *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
229
{
E
Eric Dumazet 已提交
230
	BUG_ON(i >= 1U << tn->bits);
231

E
Eric Dumazet 已提交
232
	return rcu_dereference_rtnl(tn->child[i]);
233 234
}

S
Stephen Hemmigner 已提交
235
static inline int tnode_child_length(const struct tnode *tn)
236
{
O
Olof Johansson 已提交
237
	return 1 << tn->bits;
238 239
}

240
static inline t_key mask_pfx(t_key k, unsigned int l)
S
Stephen Hemminger 已提交
241 242 243 244
{
	return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
}

245
static inline t_key tkey_extract_bits(t_key a, unsigned int offset, unsigned int bits)
246
{
O
Olof Johansson 已提交
247
	if (offset < KEYLENGTH)
248
		return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
O
Olof Johansson 已提交
249
	else
250 251 252 253 254
		return 0;
}

static inline int tkey_equals(t_key a, t_key b)
{
255
	return a == b;
256 257 258 259
}

static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
{
260 261
	if (bits == 0 || offset >= KEYLENGTH)
		return 1;
O
Olof Johansson 已提交
262 263
	bits = bits > KEYLENGTH ? KEYLENGTH : bits;
	return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
264
}
265 266 267 268 269 270

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

271 272 273
	if (!diff)
		return 0;
	while ((diff << i) >> (KEYLENGTH-1) == 0)
274 275 276 277 278
		i++;
	return i;
}

/*
279 280
  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
281 282 283 284
  all of the bits in that key are significant.

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

285 286 287 288 289
  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
290 291
  correct key path.

292 293 294 295 296
  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
297 298
  call to tkey_sub_equals() in trie_insert().

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

302
  Example:
303 304 305
  _________________________________________________________________
  | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
  -----------------------------------------------------------------
306
    0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
307 308 309 310 311 312 313 314 315

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

318 319
  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
320 321 322
  not use them for anything.

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

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

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

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

335

336 337 338 339 340
  The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
  at this point.

*/

S
Stephen Hemminger 已提交
341
static inline void check_tnode(const struct tnode *tn)
342
{
S
Stephen Hemminger 已提交
343
	WARN_ON(tn && tn->pos+tn->bits > 32);
344 345
}

346 347
static const int halve_threshold = 25;
static const int inflate_threshold = 50;
348
static const int halve_threshold_root = 15;
J
Jens Låås 已提交
349
static const int inflate_threshold_root = 30;
R
Robert Olsson 已提交
350 351

static void __alias_free_mem(struct rcu_head *head)
352
{
R
Robert Olsson 已提交
353 354
	struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
	kmem_cache_free(fn_alias_kmem, fa);
355 356
}

R
Robert Olsson 已提交
357
static inline void alias_free_mem_rcu(struct fib_alias *fa)
358
{
R
Robert Olsson 已提交
359 360
	call_rcu(&fa->rcu, __alias_free_mem);
}
O
Olof Johansson 已提交
361

R
Robert Olsson 已提交
362 363
static void __leaf_free_rcu(struct rcu_head *head)
{
364 365
	struct leaf *l = container_of(head, struct leaf, rcu);
	kmem_cache_free(trie_leaf_kmem, l);
R
Robert Olsson 已提交
366
}
O
Olof Johansson 已提交
367

368 369
static inline void free_leaf(struct leaf *l)
{
370
	call_rcu(&l->rcu, __leaf_free_rcu);
371 372
}

R
Robert Olsson 已提交
373
static inline void free_leaf_info(struct leaf_info *leaf)
374
{
375
	kfree_rcu(leaf, rcu);
376 377
}

378
static struct tnode *tnode_alloc(size_t size)
379
{
R
Robert Olsson 已提交
380
	if (size <= PAGE_SIZE)
381
		return kzalloc(size, GFP_KERNEL);
382
	else
383
		return vzalloc(size);
384
}
R
Robert Olsson 已提交
385

386 387 388 389
static void __tnode_vfree(struct work_struct *arg)
{
	struct tnode *tn = container_of(arg, struct tnode, work);
	vfree(tn);
390 391
}

R
Robert Olsson 已提交
392
static void __tnode_free_rcu(struct rcu_head *head)
393
{
R
Robert Olsson 已提交
394
	struct tnode *tn = container_of(head, struct tnode, rcu);
395
	size_t size = sizeof(struct tnode) +
396
		      (sizeof(struct rt_trie_node *) << tn->bits);
397 398 399

	if (size <= PAGE_SIZE)
		kfree(tn);
400 401 402 403
	else {
		INIT_WORK(&tn->work, __tnode_vfree);
		schedule_work(&tn->work);
	}
404 405
}

R
Robert Olsson 已提交
406 407
static inline void tnode_free(struct tnode *tn)
{
408 409 410
	if (IS_LEAF(tn))
		free_leaf((struct leaf *) tn);
	else
R
Robert Olsson 已提交
411
		call_rcu(&tn->rcu, __tnode_free_rcu);
R
Robert Olsson 已提交
412 413
}

J
Jarek Poplawski 已提交
414 415 416
static void tnode_free_safe(struct tnode *tn)
{
	BUG_ON(IS_LEAF(tn));
417 418
	tn->tnode_free = tnode_free_head;
	tnode_free_head = tn;
419
	tnode_free_size += sizeof(struct tnode) +
420
			   (sizeof(struct rt_trie_node *) << tn->bits);
J
Jarek Poplawski 已提交
421 422 423 424 425 426 427 428 429 430 431
}

static void tnode_free_flush(void)
{
	struct tnode *tn;

	while ((tn = tnode_free_head)) {
		tnode_free_head = tn->tnode_free;
		tn->tnode_free = NULL;
		tnode_free(tn);
	}
432 433 434 435 436

	if (tnode_free_size >= PAGE_SIZE * sync_pages) {
		tnode_free_size = 0;
		synchronize_rcu();
	}
J
Jarek Poplawski 已提交
437 438
}

R
Robert Olsson 已提交
439 440
static struct leaf *leaf_new(void)
{
441
	struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
R
Robert Olsson 已提交
442 443 444 445 446 447 448 449 450 451 452 453
	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;
454
		li->mask_plen = ntohl(inet_make_mask(plen));
R
Robert Olsson 已提交
455 456 457 458 459
		INIT_LIST_HEAD(&li->falh);
	}
	return li;
}

460
static struct tnode *tnode_new(t_key key, int pos, int bits)
461
{
462
	size_t sz = sizeof(struct tnode) + (sizeof(struct rt_trie_node *) << bits);
463
	struct tnode *tn = tnode_alloc(sz);
464

O
Olof Johansson 已提交
465
	if (tn) {
R
Robert Olsson 已提交
466
		tn->parent = T_TNODE;
467 468 469 470 471 472
		tn->pos = pos;
		tn->bits = bits;
		tn->key = key;
		tn->full_children = 0;
		tn->empty_children = 1<<bits;
	}
473

E
Eric Dumazet 已提交
474
	pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode),
L
Lin Ming 已提交
475
		 sizeof(struct rt_trie_node *) << bits);
476 477 478 479 480 481 482 483
	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
 */

484
static inline int tnode_full(const struct tnode *tn, const struct rt_trie_node *n)
485
{
486
	if (n == NULL || IS_LEAF(n))
487 488 489 490 491
		return 0;

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

L
Lin Ming 已提交
492
static inline void put_child(struct tnode *tn, int i,
493
			     struct rt_trie_node *n)
494 495 496 497
{
	tnode_put_child_reorg(tn, i, n, -1);
}

498
 /*
499 500 501 502
  * Add a child at position i overwriting the old value.
  * Update the value of full_children and empty_children.
  */

503
static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
504
				  int wasfull)
505
{
E
Eric Dumazet 已提交
506
	struct rt_trie_node *chi = rtnl_dereference(tn->child[i]);
507 508
	int isfull;

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

511 512 513 514 515
	/* update emptyChildren */
	if (n == NULL && chi != NULL)
		tn->empty_children++;
	else if (n != NULL && chi == NULL)
		tn->empty_children--;
516

517
	/* update fullChildren */
O
Olof Johansson 已提交
518
	if (wasfull == -1)
519 520 521
		wasfull = tnode_full(tn, chi);

	isfull = tnode_full(tn, n);
522
	if (wasfull && !isfull)
523
		tn->full_children--;
524
	else if (!wasfull && isfull)
525
		tn->full_children++;
O
Olof Johansson 已提交
526

527
	if (n)
S
Stephen Hemminger 已提交
528
		node_set_parent(n, tn);
529

530
	rcu_assign_pointer(tn->child[i], n);
531 532
}

J
Jens Låås 已提交
533
#define MAX_WORK 10
534
static struct rt_trie_node *resize(struct trie *t, struct tnode *tn)
535 536
{
	int i;
537
	struct tnode *old_tn;
538 539
	int inflate_threshold_use;
	int halve_threshold_use;
J
Jens Låås 已提交
540
	int max_work;
541

542
	if (!tn)
543 544
		return NULL;

S
Stephen Hemminger 已提交
545 546
	pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
		 tn, inflate_threshold, halve_threshold);
547 548 549

	/* No children */
	if (tn->empty_children == tnode_child_length(tn)) {
J
Jarek Poplawski 已提交
550
		tnode_free_safe(tn);
551 552 553 554
		return NULL;
	}
	/* One child */
	if (tn->empty_children == tnode_child_length(tn) - 1)
J
Jens Låås 已提交
555
		goto one_child;
556
	/*
557 558 559 560 561
	 * Double as long as the resulting node has a number of
	 * nonempty nodes that are above the threshold.
	 */

	/*
562 563
	 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
	 * the Helsinki University of Technology and Matti Tikkanen of Nokia
564
	 * Telecommunications, page 6:
565
	 * "A node is doubled if the ratio of non-empty children to all
566 567
	 * children in the *doubled* node is at least 'high'."
	 *
568 569 570 571 572
	 * '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
573
	 * multiply the left-hand side by 50.
574 575 576 577
	 *
	 * 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"
578
	 * children, that is non-null tnodes with a skip value of 0.
579
	 * All of those will be doubled in the resulting inflated tnode, so
580
	 * we just count them one extra time here.
581
	 *
582
	 * A clearer way to write this would be:
583
	 *
584
	 * to_be_doubled = tn->full_children;
585
	 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
586 587 588 589
	 *     tn->full_children;
	 *
	 * new_child_length = tnode_child_length(tn) * 2;
	 *
590
	 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
591 592
	 *      new_child_length;
	 * if (new_fill_factor >= inflate_threshold)
593 594 595
	 *
	 * ...and so on, tho it would mess up the while () loop.
	 *
596 597 598
	 * anyway,
	 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
	 *      inflate_threshold
599
	 *
600 601 602
	 * avoid a division:
	 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
	 *      inflate_threshold * new_child_length
603
	 *
604
	 * expand not_to_be_doubled and to_be_doubled, and shorten:
605
	 * 100 * (tnode_child_length(tn) - tn->empty_children +
O
Olof Johansson 已提交
606
	 *    tn->full_children) >= inflate_threshold * new_child_length
607
	 *
608
	 * expand new_child_length:
609
	 * 100 * (tnode_child_length(tn) - tn->empty_children +
O
Olof Johansson 已提交
610
	 *    tn->full_children) >=
611
	 *      inflate_threshold * tnode_child_length(tn) * 2
612
	 *
613
	 * shorten again:
614
	 * 50 * (tn->full_children + tnode_child_length(tn) -
O
Olof Johansson 已提交
615
	 *    tn->empty_children) >= inflate_threshold *
616
	 *    tnode_child_length(tn)
617
	 *
618 619 620
	 */

	check_tnode(tn);
621

622 623
	/* Keep root node larger  */

624
	if (!node_parent((struct rt_trie_node *)tn)) {
J
Jens Låås 已提交
625 626
		inflate_threshold_use = inflate_threshold_root;
		halve_threshold_use = halve_threshold_root;
E
Eric Dumazet 已提交
627
	} else {
628
		inflate_threshold_use = inflate_threshold;
J
Jens Låås 已提交
629 630
		halve_threshold_use = halve_threshold;
	}
631

J
Jens Låås 已提交
632 633
	max_work = MAX_WORK;
	while ((tn->full_children > 0 &&  max_work-- &&
634 635 636
		50 * (tn->full_children + tnode_child_length(tn)
		      - tn->empty_children)
		>= inflate_threshold_use * tnode_child_length(tn))) {
637

638 639
		old_tn = tn;
		tn = inflate(t, tn);
640

641 642
		if (IS_ERR(tn)) {
			tn = old_tn;
643 644 645 646 647
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.resize_node_skipped++;
#endif
			break;
		}
648 649 650 651
	}

	check_tnode(tn);

J
Jens Låås 已提交
652
	/* Return if at least one inflate is run */
E
Eric Dumazet 已提交
653
	if (max_work != MAX_WORK)
654
		return (struct rt_trie_node *) tn;
J
Jens Låås 已提交
655

656 657 658 659
	/*
	 * Halve as long as the number of empty children in this
	 * node is above threshold.
	 */
660

J
Jens Låås 已提交
661 662
	max_work = MAX_WORK;
	while (tn->bits > 1 &&  max_work-- &&
663
	       100 * (tnode_child_length(tn) - tn->empty_children) <
664
	       halve_threshold_use * tnode_child_length(tn)) {
665

666 667 668 669
		old_tn = tn;
		tn = halve(t, tn);
		if (IS_ERR(tn)) {
			tn = old_tn;
670 671 672 673 674 675
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.resize_node_skipped++;
#endif
			break;
		}
	}
676

677

678
	/* Only one child remains */
J
Jens Låås 已提交
679 680
	if (tn->empty_children == tnode_child_length(tn) - 1) {
one_child:
681
		for (i = 0; i < tnode_child_length(tn); i++) {
682
			struct rt_trie_node *n;
683

E
Eric Dumazet 已提交
684
			n = rtnl_dereference(tn->child[i]);
R
Robert Olsson 已提交
685
			if (!n)
O
Olof Johansson 已提交
686 687 688 689
				continue;

			/* compress one level */

S
Stephen Hemminger 已提交
690
			node_set_parent(n, NULL);
J
Jarek Poplawski 已提交
691
			tnode_free_safe(tn);
O
Olof Johansson 已提交
692
			return n;
693
		}
J
Jens Låås 已提交
694
	}
695
	return (struct rt_trie_node *) tn;
696 697
}

E
Eric Dumazet 已提交
698 699 700 701 702 703 704 705 706 707 708 709 710 711

static void tnode_clean_free(struct tnode *tn)
{
	int i;
	struct tnode *tofree;

	for (i = 0; i < tnode_child_length(tn); i++) {
		tofree = (struct tnode *)rtnl_dereference(tn->child[i]);
		if (tofree)
			tnode_free(tofree);
	}
	tnode_free(tn);
}

712
static struct tnode *inflate(struct trie *t, struct tnode *tn)
713 714 715 716 717
{
	struct tnode *oldtnode = tn;
	int olen = tnode_child_length(tn);
	int i;

S
Stephen Hemminger 已提交
718
	pr_debug("In inflate\n");
719 720 721

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

S
Stephen Hemminger 已提交
722
	if (!tn)
723
		return ERR_PTR(-ENOMEM);
724 725

	/*
726 727 728
	 * 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
729 730
	 * of tnode is ignored.
	 */
O
Olof Johansson 已提交
731 732

	for (i = 0; i < olen; i++) {
733
		struct tnode *inode;
734

735
		inode = (struct tnode *) tnode_get_child(oldtnode, i);
736 737 738 739 740
		if (inode &&
		    IS_TNODE(inode) &&
		    inode->pos == oldtnode->pos + oldtnode->bits &&
		    inode->bits > 1) {
			struct tnode *left, *right;
S
Stephen Hemminger 已提交
741
			t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
742

743 744
			left = tnode_new(inode->key&(~m), inode->pos + 1,
					 inode->bits - 1);
745 746
			if (!left)
				goto nomem;
O
Olof Johansson 已提交
747

748 749 750
			right = tnode_new(inode->key|m, inode->pos + 1,
					  inode->bits - 1);

751
			if (!right) {
752 753
				tnode_free(left);
				goto nomem;
754
			}
755

L
Lin Ming 已提交
756 757
			put_child(tn, 2*i, (struct rt_trie_node *) left);
			put_child(tn, 2*i+1, (struct rt_trie_node *) right);
758 759 760
		}
	}

O
Olof Johansson 已提交
761
	for (i = 0; i < olen; i++) {
762
		struct tnode *inode;
763
		struct rt_trie_node *node = tnode_get_child(oldtnode, i);
O
Olof Johansson 已提交
764 765
		struct tnode *left, *right;
		int size, j;
766

767 768 769 770 771 772
		/* An empty child */
		if (node == NULL)
			continue;

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

773
		if (IS_LEAF(node) || ((struct tnode *) node)->pos >
774
		   tn->pos + tn->bits - 1) {
775 776 777
			if (tkey_extract_bits(node->key,
					      oldtnode->pos + oldtnode->bits,
					      1) == 0)
L
Lin Ming 已提交
778
				put_child(tn, 2*i, node);
779
			else
L
Lin Ming 已提交
780
				put_child(tn, 2*i+1, node);
781 782 783 784 785 786 787
			continue;
		}

		/* An internal node with two children */
		inode = (struct tnode *) node;

		if (inode->bits == 1) {
L
Lin Ming 已提交
788 789
			put_child(tn, 2*i, rtnl_dereference(inode->child[0]));
			put_child(tn, 2*i+1, rtnl_dereference(inode->child[1]));
790

J
Jarek Poplawski 已提交
791
			tnode_free_safe(inode);
O
Olof Johansson 已提交
792
			continue;
793 794
		}

O
Olof Johansson 已提交
795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812
		/* 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)
		 */
813

O
Olof Johansson 已提交
814 815 816
		/* Use the old key, but set the new significant
		 *   bit to zero.
		 */
817

O
Olof Johansson 已提交
818
		left = (struct tnode *) tnode_get_child(tn, 2*i);
L
Lin Ming 已提交
819
		put_child(tn, 2*i, NULL);
820

O
Olof Johansson 已提交
821
		BUG_ON(!left);
822

O
Olof Johansson 已提交
823
		right = (struct tnode *) tnode_get_child(tn, 2*i+1);
L
Lin Ming 已提交
824
		put_child(tn, 2*i+1, NULL);
825

O
Olof Johansson 已提交
826
		BUG_ON(!right);
827

O
Olof Johansson 已提交
828 829
		size = tnode_child_length(left);
		for (j = 0; j < size; j++) {
L
Lin Ming 已提交
830 831
			put_child(left, j, rtnl_dereference(inode->child[j]));
			put_child(right, j, rtnl_dereference(inode->child[j + size]));
832
		}
L
Lin Ming 已提交
833 834
		put_child(tn, 2*i, resize(t, left));
		put_child(tn, 2*i+1, resize(t, right));
O
Olof Johansson 已提交
835

J
Jarek Poplawski 已提交
836
		tnode_free_safe(inode);
837
	}
J
Jarek Poplawski 已提交
838
	tnode_free_safe(oldtnode);
839
	return tn;
840
nomem:
E
Eric Dumazet 已提交
841 842
	tnode_clean_free(tn);
	return ERR_PTR(-ENOMEM);
843 844
}

845
static struct tnode *halve(struct trie *t, struct tnode *tn)
846 847
{
	struct tnode *oldtnode = tn;
848
	struct rt_trie_node *left, *right;
849 850 851
	int i;
	int olen = tnode_child_length(tn);

S
Stephen Hemminger 已提交
852
	pr_debug("In halve\n");
853 854

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

856 857
	if (!tn)
		return ERR_PTR(-ENOMEM);
858 859

	/*
860 861 862
	 * 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
863 864 865
	 * of tnode is ignored.
	 */

O
Olof Johansson 已提交
866
	for (i = 0; i < olen; i += 2) {
867 868
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
869

870
		/* Two nonempty children */
S
Stephen Hemminger 已提交
871
		if (left && right) {
872
			struct tnode *newn;
S
Stephen Hemminger 已提交
873

874
			newn = tnode_new(left->key, tn->pos + tn->bits, 1);
S
Stephen Hemminger 已提交
875 876

			if (!newn)
877
				goto nomem;
S
Stephen Hemminger 已提交
878

L
Lin Ming 已提交
879
			put_child(tn, i/2, (struct rt_trie_node *)newn);
880 881 882
		}

	}
883

O
Olof Johansson 已提交
884 885 886
	for (i = 0; i < olen; i += 2) {
		struct tnode *newBinNode;

887 888
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
889

890 891 892 893
		/* At least one of the children is empty */
		if (left == NULL) {
			if (right == NULL)    /* Both are empty */
				continue;
L
Lin Ming 已提交
894
			put_child(tn, i/2, right);
O
Olof Johansson 已提交
895
			continue;
S
Stephen Hemminger 已提交
896
		}
O
Olof Johansson 已提交
897 898

		if (right == NULL) {
L
Lin Ming 已提交
899
			put_child(tn, i/2, left);
O
Olof Johansson 已提交
900 901
			continue;
		}
902

903
		/* Two nonempty children */
O
Olof Johansson 已提交
904
		newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
L
Lin Ming 已提交
905 906 907 908
		put_child(tn, i/2, NULL);
		put_child(newBinNode, 0, left);
		put_child(newBinNode, 1, right);
		put_child(tn, i/2, resize(t, newBinNode));
909
	}
J
Jarek Poplawski 已提交
910
	tnode_free_safe(oldtnode);
911
	return tn;
912
nomem:
E
Eric Dumazet 已提交
913 914
	tnode_clean_free(tn);
	return ERR_PTR(-ENOMEM);
915 916
}

R
Robert Olsson 已提交
917
/* readside must use rcu_read_lock currently dump routines
R
Robert Olsson 已提交
918 919
 via get_fa_head and dump */

R
Robert Olsson 已提交
920
static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
921
{
R
Robert Olsson 已提交
922
	struct hlist_head *head = &l->list;
923 924 925
	struct hlist_node *node;
	struct leaf_info *li;

R
Robert Olsson 已提交
926
	hlist_for_each_entry_rcu(li, node, head, hlist)
927
		if (li->plen == plen)
928
			return li;
O
Olof Johansson 已提交
929

930 931 932
	return NULL;
}

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

O
Olof Johansson 已提交
937 938
	if (!li)
		return NULL;
939

O
Olof Johansson 已提交
940
	return &li->falh;
941 942 943 944
}

static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
{
945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961
	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);
	}
962 963
}

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

966 967 968 969 970
static struct leaf *
fib_find_node(struct trie *t, u32 key)
{
	int pos;
	struct tnode *tn;
971
	struct rt_trie_node *n;
972 973

	pos = 0;
E
Eric Dumazet 已提交
974
	n = rcu_dereference_rtnl(t->trie);
975 976 977

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

979
		check_tnode(tn);
O
Olof Johansson 已提交
980

981
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
O
Olof Johansson 已提交
982
			pos = tn->pos + tn->bits;
983 984 985 986
			n = tnode_get_child_rcu(tn,
						tkey_extract_bits(key,
								  tn->pos,
								  tn->bits));
O
Olof Johansson 已提交
987
		} else
988 989 990 991
			break;
	}
	/* Case we have found a leaf. Compare prefixes */

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

995 996 997
	return NULL;
}

998
static void trie_rebalance(struct trie *t, struct tnode *tn)
999 1000
{
	int wasfull;
R
Robert Olsson 已提交
1001
	t_key cindex, key;
S
Stephen Hemminger 已提交
1002
	struct tnode *tp;
1003

R
Robert Olsson 已提交
1004 1005
	key = tn->key;

1006
	while (tn != NULL && (tp = node_parent((struct rt_trie_node *)tn)) != NULL) {
1007 1008
		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
		wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
J
Joe Perches 已提交
1009
		tn = (struct tnode *)resize(t, tn);
1010

J
Joe Perches 已提交
1011
		tnode_put_child_reorg(tp, cindex,
1012
				      (struct rt_trie_node *)tn, wasfull);
O
Olof Johansson 已提交
1013

1014
		tp = node_parent((struct rt_trie_node *) tn);
1015
		if (!tp)
1016
			rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1017

J
Jarek Poplawski 已提交
1018
		tnode_free_flush();
S
Stephen Hemminger 已提交
1019
		if (!tp)
1020
			break;
S
Stephen Hemminger 已提交
1021
		tn = tp;
1022
	}
S
Stephen Hemminger 已提交
1023

1024
	/* Handle last (top) tnode */
1025
	if (IS_TNODE(tn))
J
Joe Perches 已提交
1026
		tn = (struct tnode *)resize(t, tn);
1027

1028
	rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1029
	tnode_free_flush();
1030 1031
}

R
Robert Olsson 已提交
1032 1033
/* only used from updater-side */

1034
static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
1035 1036 1037
{
	int pos, newpos;
	struct tnode *tp = NULL, *tn = NULL;
1038
	struct rt_trie_node *n;
1039 1040
	struct leaf *l;
	int missbit;
1041
	struct list_head *fa_head = NULL;
1042 1043 1044 1045
	struct leaf_info *li;
	t_key cindex;

	pos = 0;
E
Eric Dumazet 已提交
1046
	n = rtnl_dereference(t->trie);
1047

1048 1049
	/* 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,
1050
	 * and we should just put our new leaf in that.
1051 1052
	 * 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
1053 1054
	 * not be the parent's 'pos'+'bits'!
	 *
1055
	 * If it does match the current key, get pos/bits from it, extract
1056 1057 1058 1059
	 * 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.
	 *
1060 1061 1062
	 * 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.
1063 1064 1065 1066 1067
	 * 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 已提交
1068

1069
		check_tnode(tn);
O
Olof Johansson 已提交
1070

1071
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1072
			tp = tn;
O
Olof Johansson 已提交
1073
			pos = tn->pos + tn->bits;
1074 1075 1076 1077
			n = tnode_get_child(tn,
					    tkey_extract_bits(key,
							      tn->pos,
							      tn->bits));
1078

S
Stephen Hemminger 已提交
1079
			BUG_ON(n && node_parent(n) != tn);
O
Olof Johansson 已提交
1080
		} else
1081 1082 1083 1084 1085 1086
			break;
	}

	/*
	 * n  ----> NULL, LEAF or TNODE
	 *
1087
	 * tp is n's (parent) ----> NULL or TNODE
1088 1089
	 */

O
Olof Johansson 已提交
1090
	BUG_ON(tp && IS_LEAF(tp));
1091 1092 1093

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

1094
	if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1095
		l = (struct leaf *) n;
1096
		li = leaf_info_new(plen);
O
Olof Johansson 已提交
1097

1098 1099
		if (!li)
			return NULL;
1100 1101 1102 1103 1104 1105 1106

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

1107 1108
	if (!l)
		return NULL;
1109 1110 1111 1112

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

1113
	if (!li) {
1114
		free_leaf(l);
1115
		return NULL;
1116
	}
1117 1118 1119 1120 1121

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

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

1124
		node_set_parent((struct rt_trie_node *)l, tp);
1125

O
Olof Johansson 已提交
1126
		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
L
Lin Ming 已提交
1127
		put_child(tp, cindex, (struct rt_trie_node *)l);
O
Olof Johansson 已提交
1128 1129
	} else {
		/* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1130 1131
		/*
		 *  Add a new tnode here
1132 1133 1134 1135
		 *  first tnode need some special handling
		 */

		if (tp)
O
Olof Johansson 已提交
1136
			pos = tp->pos+tp->bits;
1137
		else
O
Olof Johansson 已提交
1138 1139
			pos = 0;

1140
		if (n) {
1141 1142
			newpos = tkey_mismatch(key, pos, n->key);
			tn = tnode_new(n->key, newpos, 1);
O
Olof Johansson 已提交
1143
		} else {
1144
			newpos = 0;
1145
			tn = tnode_new(key, newpos, 1); /* First tnode */
1146 1147
		}

1148
		if (!tn) {
1149
			free_leaf_info(li);
1150
			free_leaf(l);
1151
			return NULL;
O
Olof Johansson 已提交
1152 1153
		}

1154
		node_set_parent((struct rt_trie_node *)tn, tp);
1155

O
Olof Johansson 已提交
1156
		missbit = tkey_extract_bits(key, newpos, 1);
L
Lin Ming 已提交
1157 1158
		put_child(tn, missbit, (struct rt_trie_node *)l);
		put_child(tn, 1-missbit, n);
1159

1160
		if (tp) {
1161
			cindex = tkey_extract_bits(key, tp->pos, tp->bits);
L
Lin Ming 已提交
1162
			put_child(tp, cindex, (struct rt_trie_node *)tn);
O
Olof Johansson 已提交
1163
		} else {
1164
			rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1165 1166 1167
			tp = tn;
		}
	}
O
Olof Johansson 已提交
1168 1169

	if (tp && tp->pos + tp->bits > 32)
J
Joe Perches 已提交
1170 1171
		pr_warn("fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
			tp, tp->pos, tp->bits, key, plen);
O
Olof Johansson 已提交
1172

1173
	/* Rebalance the trie */
R
Robert Olsson 已提交
1174

1175
	trie_rebalance(t, tp);
1176
done:
1177 1178 1179
	return fa_head;
}

1180 1181 1182
/*
 * Caller must hold RTNL.
 */
1183
int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
1184 1185 1186
{
	struct trie *t = (struct trie *) tb->tb_data;
	struct fib_alias *fa, *new_fa;
1187
	struct list_head *fa_head = NULL;
1188
	struct fib_info *fi;
1189 1190
	int plen = cfg->fc_dst_len;
	u8 tos = cfg->fc_tos;
1191 1192 1193 1194 1195 1196 1197
	u32 key, mask;
	int err;
	struct leaf *l;

	if (plen > 32)
		return -EINVAL;

1198
	key = ntohl(cfg->fc_dst);
1199

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

O
Olof Johansson 已提交
1202
	mask = ntohl(inet_make_mask(plen));
1203

1204
	if (key & ~mask)
1205 1206 1207 1208
		return -EINVAL;

	key = key & mask;

1209 1210 1211
	fi = fib_create_info(cfg);
	if (IS_ERR(fi)) {
		err = PTR_ERR(fi);
1212
		goto err;
1213
	}
1214 1215

	l = fib_find_node(t, key);
1216
	fa = NULL;
1217

1218
	if (l) {
1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233
		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.
	 */

1234 1235 1236
	if (fa && fa->fa_tos == tos &&
	    fa->fa_info->fib_priority == fi->fib_priority) {
		struct fib_alias *fa_first, *fa_match;
1237 1238

		err = -EEXIST;
1239
		if (cfg->fc_nlflags & NLM_F_EXCL)
1240 1241
			goto out;

1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261
		/* We have 2 goals:
		 * 1. Find exact match for type, scope, fib_info to avoid
		 * duplicate routes
		 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
		 */
		fa_match = NULL;
		fa_first = fa;
		fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
		list_for_each_entry_continue(fa, fa_head, fa_list) {
			if (fa->fa_tos != tos)
				break;
			if (fa->fa_info->fib_priority != fi->fib_priority)
				break;
			if (fa->fa_type == cfg->fc_type &&
			    fa->fa_info == fi) {
				fa_match = fa;
				break;
			}
		}

1262
		if (cfg->fc_nlflags & NLM_F_REPLACE) {
1263 1264 1265
			struct fib_info *fi_drop;
			u8 state;

1266 1267 1268 1269
			fa = fa_first;
			if (fa_match) {
				if (fa == fa_match)
					err = 0;
1270
				goto out;
1271
			}
R
Robert Olsson 已提交
1272
			err = -ENOBUFS;
1273
			new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
R
Robert Olsson 已提交
1274 1275
			if (new_fa == NULL)
				goto out;
1276 1277

			fi_drop = fa->fa_info;
R
Robert Olsson 已提交
1278 1279
			new_fa->fa_tos = fa->fa_tos;
			new_fa->fa_info = fi;
1280
			new_fa->fa_type = cfg->fc_type;
1281
			state = fa->fa_state;
1282
			new_fa->fa_state = state & ~FA_S_ACCESSED;
1283

R
Robert Olsson 已提交
1284 1285
			list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
			alias_free_mem_rcu(fa);
1286 1287 1288

			fib_release_info(fi_drop);
			if (state & FA_S_ACCESSED)
1289
				rt_cache_flush(cfg->fc_nlinfo.nl_net);
1290 1291
			rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
				tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1292

O
Olof Johansson 已提交
1293
			goto succeeded;
1294 1295 1296 1297 1298
		}
		/* Error if we find a perfect match which
		 * uses the same scope, type, and nexthop
		 * information.
		 */
1299 1300
		if (fa_match)
			goto out;
1301

1302
		if (!(cfg->fc_nlflags & NLM_F_APPEND))
1303
			fa = fa_first;
1304 1305
	}
	err = -ENOENT;
1306
	if (!(cfg->fc_nlflags & NLM_F_CREATE))
1307 1308 1309
		goto out;

	err = -ENOBUFS;
1310
	new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1311 1312 1313 1314 1315
	if (new_fa == NULL)
		goto out;

	new_fa->fa_info = fi;
	new_fa->fa_tos = tos;
1316
	new_fa->fa_type = cfg->fc_type;
1317 1318 1319 1320 1321
	new_fa->fa_state = 0;
	/*
	 * Insert new entry to the list.
	 */

1322
	if (!fa_head) {
1323 1324 1325
		fa_head = fib_insert_node(t, key, plen);
		if (unlikely(!fa_head)) {
			err = -ENOMEM;
1326
			goto out_free_new_fa;
1327
		}
1328
	}
1329

1330 1331 1332
	if (!plen)
		tb->tb_num_default++;

R
Robert Olsson 已提交
1333 1334
	list_add_tail_rcu(&new_fa->fa_list,
			  (fa ? &fa->fa_list : fa_head));
1335

1336
	rt_cache_flush(cfg->fc_nlinfo.nl_net);
1337
	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1338
		  &cfg->fc_nlinfo, 0);
1339 1340
succeeded:
	return 0;
1341 1342 1343

out_free_new_fa:
	kmem_cache_free(fn_alias_kmem, new_fa);
1344 1345
out:
	fib_release_info(fi);
O
Olof Johansson 已提交
1346
err:
1347 1348 1349
	return err;
}

R
Robert Olsson 已提交
1350
/* should be called with rcu_read_lock */
1351
static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
1352
		      t_key key,  const struct flowi4 *flp,
E
Eric Dumazet 已提交
1353
		      struct fib_result *res, int fib_flags)
1354 1355 1356 1357
{
	struct leaf_info *li;
	struct hlist_head *hhead = &l->list;
	struct hlist_node *node;
1358

R
Robert Olsson 已提交
1359
	hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1360
		struct fib_alias *fa;
1361

1362
		if (l->key != (key & li->mask_plen))
1363 1364
			continue;

1365 1366 1367
		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
			struct fib_info *fi = fa->fa_info;
			int nhsel, err;
1368

1369
			if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1370
				continue;
1371 1372
			if (fi->fib_dead)
				continue;
1373
			if (fa->fa_info->fib_scope < flp->flowi4_scope)
1374 1375 1376 1377
				continue;
			fib_alias_accessed(fa);
			err = fib_props[fa->fa_type].error;
			if (err) {
1378
#ifdef CONFIG_IP_FIB_TRIE_STATS
1379
				t->stats.semantic_match_passed++;
1380
#endif
1381
				return err;
1382 1383 1384 1385 1386 1387 1388 1389
			}
			if (fi->fib_flags & RTNH_F_DEAD)
				continue;
			for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
				const struct fib_nh *nh = &fi->fib_nh[nhsel];

				if (nh->nh_flags & RTNH_F_DEAD)
					continue;
1390
				if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
1391 1392 1393 1394 1395
					continue;

#ifdef CONFIG_IP_FIB_TRIE_STATS
				t->stats.semantic_match_passed++;
#endif
1396
				res->prefixlen = li->plen;
1397 1398
				res->nh_sel = nhsel;
				res->type = fa->fa_type;
1399
				res->scope = fa->fa_info->fib_scope;
1400 1401 1402 1403
				res->fi = fi;
				res->table = tb;
				res->fa_head = &li->falh;
				if (!(fib_flags & FIB_LOOKUP_NOREF))
1404
					atomic_inc(&fi->fib_clntref);
1405 1406 1407 1408 1409 1410
				return 0;
			}
		}

#ifdef CONFIG_IP_FIB_TRIE_STATS
		t->stats.semantic_match_miss++;
1411 1412
#endif
	}
1413

1414
	return 1;
1415 1416
}

1417
int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
E
Eric Dumazet 已提交
1418
		     struct fib_result *res, int fib_flags)
1419 1420
{
	struct trie *t = (struct trie *) tb->tb_data;
1421
	int ret;
1422
	struct rt_trie_node *n;
1423
	struct tnode *pn;
1424
	unsigned int pos, bits;
1425
	t_key key = ntohl(flp->daddr);
1426
	unsigned int chopped_off;
1427
	t_key cindex = 0;
1428
	unsigned int current_prefix_length = KEYLENGTH;
O
Olof Johansson 已提交
1429
	struct tnode *cn;
1430
	t_key pref_mismatch;
O
Olof Johansson 已提交
1431

R
Robert Olsson 已提交
1432
	rcu_read_lock();
O
Olof Johansson 已提交
1433

R
Robert Olsson 已提交
1434
	n = rcu_dereference(t->trie);
1435
	if (!n)
1436 1437 1438 1439 1440 1441 1442 1443
		goto failed;

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

	/* Just a leaf? */
	if (IS_LEAF(n)) {
1444
		ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1445
		goto found;
1446
	}
1447

1448 1449
	pn = (struct tnode *) n;
	chopped_off = 0;
1450

O
Olof Johansson 已提交
1451
	while (pn) {
1452 1453 1454
		pos = pn->pos;
		bits = pn->bits;

1455
		if (!chopped_off)
S
Stephen Hemminger 已提交
1456 1457
			cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
						   pos, bits);
1458

1459
		n = tnode_get_child_rcu(pn, cindex);
1460 1461 1462 1463 1464 1465 1466 1467

		if (n == NULL) {
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.null_node_hit++;
#endif
			goto backtrace;
		}

O
Olof Johansson 已提交
1468
		if (IS_LEAF(n)) {
1469
			ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1470
			if (ret > 0)
O
Olof Johansson 已提交
1471
				goto backtrace;
1472
			goto found;
O
Olof Johansson 已提交
1473 1474 1475
		}

		cn = (struct tnode *)n;
1476

O
Olof Johansson 已提交
1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491
		/*
		 * 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].
		 */
1492

O
Olof Johansson 已提交
1493 1494 1495 1496 1497 1498 1499 1500 1501
		/* 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.
		 */
1502

1503 1504
		/* NOTA BENE: Checking only skipped bits
		   for the new node here */
1505

O
Olof Johansson 已提交
1506 1507
		if (current_prefix_length < pos+bits) {
			if (tkey_extract_bits(cn->key, current_prefix_length,
1508 1509
						cn->pos - current_prefix_length)
			    || !(cn->child[0]))
O
Olof Johansson 已提交
1510 1511
				goto backtrace;
		}
1512

O
Olof Johansson 已提交
1513 1514 1515 1516 1517 1518 1519 1520 1521
		/*
		 * 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.
		 */
1522

O
Olof Johansson 已提交
1523 1524 1525 1526 1527 1528 1529 1530
		/* 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.
		 */
1531

1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542
		/*
		 * 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.
O
Olof Johansson 已提交
1543 1544
		 */

1545
		pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
O
Olof Johansson 已提交
1546

1547 1548 1549 1550
		/*
		 * In short: If skipped bits in this node do not match
		 * the search key, enter the "prefix matching"
		 * state.directly.
O
Olof Johansson 已提交
1551 1552
		 */
		if (pref_mismatch) {
1553 1554
			/* fls(x) = __fls(x) + 1 */
			int mp = KEYLENGTH - __fls(pref_mismatch) - 1;
O
Olof Johansson 已提交
1555

1556
			if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
O
Olof Johansson 已提交
1557 1558 1559 1560
				goto backtrace;

			if (current_prefix_length >= cn->pos)
				current_prefix_length = mp;
1561
		}
1562

O
Olof Johansson 已提交
1563 1564 1565 1566
		pn = (struct tnode *)n; /* Descend */
		chopped_off = 0;
		continue;

1567 1568 1569 1570
backtrace:
		chopped_off++;

		/* As zero don't change the child key (cindex) */
1571 1572
		while ((chopped_off <= pn->bits)
		       && !(cindex & (1<<(chopped_off-1))))
1573 1574 1575 1576
			chopped_off++;

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

1580
		/*
1581
		 * Either we do the actual chop off according or if we have
1582 1583 1584
		 * chopped off all bits in this tnode walk up to our parent.
		 */

O
Olof Johansson 已提交
1585
		if (chopped_off <= pn->bits) {
1586
			cindex &= ~(1 << (chopped_off-1));
O
Olof Johansson 已提交
1587
		} else {
1588
			struct tnode *parent = node_parent_rcu((struct rt_trie_node *) pn);
S
Stephen Hemminger 已提交
1589
			if (!parent)
1590
				goto failed;
O
Olof Johansson 已提交
1591

1592
			/* Get Child's index */
S
Stephen Hemminger 已提交
1593 1594
			cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
			pn = parent;
1595 1596 1597 1598 1599 1600
			chopped_off = 0;

#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.backtrack++;
#endif
			goto backtrace;
1601
		}
1602 1603
	}
failed:
1604
	ret = 1;
1605
found:
R
Robert Olsson 已提交
1606
	rcu_read_unlock();
1607 1608
	return ret;
}
1609
EXPORT_SYMBOL_GPL(fib_table_lookup);
1610

1611 1612 1613 1614
/*
 * Remove the leaf and return parent.
 */
static void trie_leaf_remove(struct trie *t, struct leaf *l)
1615
{
1616
	struct tnode *tp = node_parent((struct rt_trie_node *) l);
1617

1618
	pr_debug("entering trie_leaf_remove(%p)\n", l);
1619

1620
	if (tp) {
1621
		t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
L
Lin Ming 已提交
1622
		put_child(tp, cindex, NULL);
1623
		trie_rebalance(t, tp);
O
Olof Johansson 已提交
1624
	} else
1625
		RCU_INIT_POINTER(t->trie, NULL);
1626

1627
	free_leaf(l);
1628 1629
}

1630 1631 1632
/*
 * Caller must hold RTNL.
 */
1633
int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
1634 1635 1636
{
	struct trie *t = (struct trie *) tb->tb_data;
	u32 key, mask;
1637 1638
	int plen = cfg->fc_dst_len;
	u8 tos = cfg->fc_tos;
1639 1640 1641
	struct fib_alias *fa, *fa_to_delete;
	struct list_head *fa_head;
	struct leaf *l;
O
Olof Johansson 已提交
1642 1643
	struct leaf_info *li;

1644
	if (plen > 32)
1645 1646
		return -EINVAL;

1647
	key = ntohl(cfg->fc_dst);
O
Olof Johansson 已提交
1648
	mask = ntohl(inet_make_mask(plen));
1649

1650
	if (key & ~mask)
1651 1652 1653 1654 1655
		return -EINVAL;

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

1656
	if (!l)
1657 1658
		return -ESRCH;

1659 1660 1661 1662 1663 1664
	li = find_leaf_info(l, plen);

	if (!li)
		return -ESRCH;

	fa_head = &li->falh;
1665 1666 1667 1668 1669
	fa = fib_find_alias(fa_head, tos, 0);

	if (!fa)
		return -ESRCH;

S
Stephen Hemminger 已提交
1670
	pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1671 1672

	fa_to_delete = NULL;
1673 1674
	fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
	list_for_each_entry_continue(fa, fa_head, fa_list) {
1675 1676 1677 1678 1679
		struct fib_info *fi = fa->fa_info;

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

1680 1681
		if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
		    (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1682
		     fa->fa_info->fib_scope == cfg->fc_scope) &&
1683 1684
		    (!cfg->fc_prefsrc ||
		     fi->fib_prefsrc == cfg->fc_prefsrc) &&
1685 1686 1687
		    (!cfg->fc_protocol ||
		     fi->fib_protocol == cfg->fc_protocol) &&
		    fib_nh_match(cfg, fi) == 0) {
1688 1689 1690 1691 1692
			fa_to_delete = fa;
			break;
		}
	}

O
Olof Johansson 已提交
1693 1694
	if (!fa_to_delete)
		return -ESRCH;
1695

O
Olof Johansson 已提交
1696
	fa = fa_to_delete;
1697
	rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1698
		  &cfg->fc_nlinfo, 0);
O
Olof Johansson 已提交
1699

R
Robert Olsson 已提交
1700
	list_del_rcu(&fa->fa_list);
1701

1702 1703 1704
	if (!plen)
		tb->tb_num_default--;

O
Olof Johansson 已提交
1705
	if (list_empty(fa_head)) {
R
Robert Olsson 已提交
1706
		hlist_del_rcu(&li->hlist);
O
Olof Johansson 已提交
1707
		free_leaf_info(li);
R
Robert Olsson 已提交
1708
	}
1709

O
Olof Johansson 已提交
1710
	if (hlist_empty(&l->list))
1711
		trie_leaf_remove(t, l);
1712

O
Olof Johansson 已提交
1713
	if (fa->fa_state & FA_S_ACCESSED)
1714
		rt_cache_flush(cfg->fc_nlinfo.nl_net);
1715

R
Robert Olsson 已提交
1716 1717
	fib_release_info(fa->fa_info);
	alias_free_mem_rcu(fa);
O
Olof Johansson 已提交
1718
	return 0;
1719 1720
}

1721
static int trie_flush_list(struct list_head *head)
1722 1723 1724 1725 1726 1727 1728
{
	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 已提交
1729 1730 1731 1732
		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);
1733 1734 1735 1736 1737 1738
			found++;
		}
	}
	return found;
}

1739
static int trie_flush_leaf(struct leaf *l)
1740 1741 1742 1743 1744 1745 1746
{
	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) {
1747
		found += trie_flush_list(&li->falh);
1748 1749

		if (list_empty(&li->falh)) {
R
Robert Olsson 已提交
1750
			hlist_del_rcu(&li->hlist);
1751 1752 1753 1754 1755 1756
			free_leaf_info(li);
		}
	}
	return found;
}

1757 1758 1759 1760
/*
 * Scan for the next right leaf starting at node p->child[idx]
 * Since we have back pointer, no recursion necessary.
 */
1761
static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1762
{
1763 1764
	do {
		t_key idx;
1765 1766

		if (c)
1767
			idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1768
		else
1769
			idx = 0;
R
Robert Olsson 已提交
1770

1771 1772
		while (idx < 1u << p->bits) {
			c = tnode_get_child_rcu(p, idx++);
R
Robert Olsson 已提交
1773
			if (!c)
O
Olof Johansson 已提交
1774 1775
				continue;

1776
			if (IS_LEAF(c)) {
E
Eric Dumazet 已提交
1777
				prefetch(rcu_dereference_rtnl(p->child[idx]));
1778
				return (struct leaf *) c;
1779
			}
1780 1781 1782 1783

			/* Rescan start scanning in new node */
			p = (struct tnode *) c;
			idx = 0;
1784
		}
1785 1786

		/* Node empty, walk back up to parent */
1787
		c = (struct rt_trie_node *) p;
E
Eric Dumazet 已提交
1788
	} while ((p = node_parent_rcu(c)) != NULL);
1789 1790 1791 1792 1793 1794

	return NULL; /* Root of trie */
}

static struct leaf *trie_firstleaf(struct trie *t)
{
E
Eric Dumazet 已提交
1795
	struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807

	if (!n)
		return NULL;

	if (IS_LEAF(n))          /* trie is just a leaf */
		return (struct leaf *) n;

	return leaf_walk_rcu(n, NULL);
}

static struct leaf *trie_nextleaf(struct leaf *l)
{
1808
	struct rt_trie_node *c = (struct rt_trie_node *) l;
1809
	struct tnode *p = node_parent_rcu(c);
1810 1811 1812 1813 1814

	if (!p)
		return NULL;	/* trie with just one leaf */

	return leaf_walk_rcu(p, c);
1815 1816
}

1817 1818 1819 1820
static struct leaf *trie_leafindex(struct trie *t, int index)
{
	struct leaf *l = trie_firstleaf(t);

S
Stephen Hemminger 已提交
1821
	while (l && index-- > 0)
1822
		l = trie_nextleaf(l);
S
Stephen Hemminger 已提交
1823

1824 1825 1826 1827
	return l;
}


1828 1829 1830
/*
 * Caller must hold RTNL.
 */
1831
int fib_table_flush(struct fib_table *tb)
1832 1833
{
	struct trie *t = (struct trie *) tb->tb_data;
1834
	struct leaf *l, *ll = NULL;
1835
	int found = 0;
1836

1837
	for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1838
		found += trie_flush_leaf(l);
1839 1840

		if (ll && hlist_empty(&ll->list))
1841
			trie_leaf_remove(t, ll);
1842 1843 1844 1845
		ll = l;
	}

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

S
Stephen Hemminger 已提交
1848
	pr_debug("trie_flush found=%d\n", found);
1849 1850 1851
	return found;
}

1852 1853 1854 1855 1856
void fib_free_table(struct fib_table *tb)
{
	kfree(tb);
}

1857 1858
static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
			   struct fib_table *tb,
1859 1860 1861 1862
			   struct sk_buff *skb, struct netlink_callback *cb)
{
	int i, s_i;
	struct fib_alias *fa;
A
Al Viro 已提交
1863
	__be32 xkey = htonl(key);
1864

1865
	s_i = cb->args[5];
1866 1867
	i = 0;

R
Robert Olsson 已提交
1868 1869 1870
	/* rcu_read_lock is hold by caller */

	list_for_each_entry_rcu(fa, fah, fa_list) {
1871 1872 1873 1874 1875 1876 1877 1878 1879 1880
		if (i < s_i) {
			i++;
			continue;
		}

		if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
				  cb->nlh->nlmsg_seq,
				  RTM_NEWROUTE,
				  tb->tb_id,
				  fa->fa_type,
1881
				  xkey,
1882 1883
				  plen,
				  fa->fa_tos,
1884
				  fa->fa_info, NLM_F_MULTI) < 0) {
1885
			cb->args[5] = i;
1886
			return -1;
O
Olof Johansson 已提交
1887
		}
1888 1889
		i++;
	}
1890
	cb->args[5] = i;
1891 1892 1893
	return skb->len;
}

1894 1895
static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
			struct sk_buff *skb, struct netlink_callback *cb)
1896
{
1897 1898 1899
	struct leaf_info *li;
	struct hlist_node *node;
	int i, s_i;
1900

1901
	s_i = cb->args[4];
1902
	i = 0;
1903

1904 1905 1906 1907
	/* rcu_read_lock is hold by caller */
	hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
		if (i < s_i) {
			i++;
1908
			continue;
1909
		}
O
Olof Johansson 已提交
1910

1911
		if (i > s_i)
1912
			cb->args[5] = 0;
1913

1914
		if (list_empty(&li->falh))
1915 1916
			continue;

1917
		if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1918
			cb->args[4] = i;
1919 1920
			return -1;
		}
1921
		i++;
1922
	}
1923

1924
	cb->args[4] = i;
1925 1926 1927
	return skb->len;
}

1928 1929
int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
		   struct netlink_callback *cb)
1930
{
1931
	struct leaf *l;
1932
	struct trie *t = (struct trie *) tb->tb_data;
1933
	t_key key = cb->args[2];
1934
	int count = cb->args[3];
1935

R
Robert Olsson 已提交
1936
	rcu_read_lock();
1937 1938 1939
	/* Dump starting at last key.
	 * Note: 0.0.0.0/0 (ie default) is first key.
	 */
1940
	if (count == 0)
1941 1942
		l = trie_firstleaf(t);
	else {
1943 1944 1945
		/* Normally, continue from last key, but if that is missing
		 * fallback to using slow rescan
		 */
1946
		l = fib_find_node(t, key);
1947 1948
		if (!l)
			l = trie_leafindex(t, count);
1949
	}
1950

1951 1952
	while (l) {
		cb->args[2] = l->key;
1953
		if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1954
			cb->args[3] = count;
1955 1956
			rcu_read_unlock();
			return -1;
1957
		}
1958

1959
		++count;
1960
		l = trie_nextleaf(l);
1961 1962
		memset(&cb->args[4], 0,
		       sizeof(cb->args) - 4*sizeof(cb->args[0]));
1963
	}
1964
	cb->args[3] = count;
R
Robert Olsson 已提交
1965
	rcu_read_unlock();
1966

1967 1968 1969
	return skb->len;
}

1970
void __init fib_trie_init(void)
1971
{
1972 1973
	fn_alias_kmem = kmem_cache_create("ip_fib_alias",
					  sizeof(struct fib_alias),
1974 1975 1976 1977 1978 1979
					  0, SLAB_PANIC, NULL);

	trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
					   max(sizeof(struct leaf),
					       sizeof(struct leaf_info)),
					   0, SLAB_PANIC, NULL);
1980
}
1981

1982

1983
struct fib_table *fib_trie_table(u32 id)
1984 1985 1986 1987 1988 1989 1990 1991 1992 1993
{
	struct fib_table *tb;
	struct trie *t;

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

	tb->tb_id = id;
1994
	tb->tb_default = -1;
1995
	tb->tb_num_default = 0;
1996 1997

	t = (struct trie *) tb->tb_data;
1998
	memset(t, 0, sizeof(*t));
1999 2000 2001 2002

	return tb;
}

2003 2004 2005
#ifdef CONFIG_PROC_FS
/* Depth first Trie walk iterator */
struct fib_trie_iter {
2006
	struct seq_net_private p;
2007
	struct fib_table *tb;
2008
	struct tnode *tnode;
E
Eric Dumazet 已提交
2009 2010
	unsigned int index;
	unsigned int depth;
2011
};
2012

2013
static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
2014
{
2015
	struct tnode *tn = iter->tnode;
E
Eric Dumazet 已提交
2016
	unsigned int cindex = iter->index;
2017
	struct tnode *p;
2018

2019 2020 2021 2022
	/* A single entry routing table */
	if (!tn)
		return NULL;

2023 2024 2025 2026
	pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
		 iter->tnode, iter->index, iter->depth);
rescan:
	while (cindex < (1<<tn->bits)) {
2027
		struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
2028

2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040
		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;
		}
2041

2042 2043
		++cindex;
	}
O
Olof Johansson 已提交
2044

2045
	/* Current node exhausted, pop back up */
2046
	p = node_parent_rcu((struct rt_trie_node *)tn);
2047 2048 2049 2050 2051
	if (p) {
		cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
		tn = p;
		--iter->depth;
		goto rescan;
2052
	}
2053 2054 2055

	/* got root? */
	return NULL;
2056 2057
}

2058
static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
2059
				       struct trie *t)
2060
{
2061
	struct rt_trie_node *n;
2062

S
Stephen Hemminger 已提交
2063
	if (!t)
2064 2065 2066
		return NULL;

	n = rcu_dereference(t->trie);
2067
	if (!n)
2068
		return NULL;
2069

2070 2071 2072 2073 2074 2075 2076 2077
	if (IS_TNODE(n)) {
		iter->tnode = (struct tnode *) n;
		iter->index = 0;
		iter->depth = 1;
	} else {
		iter->tnode = NULL;
		iter->index = 0;
		iter->depth = 0;
O
Olof Johansson 已提交
2078
	}
2079 2080

	return n;
2081
}
O
Olof Johansson 已提交
2082

2083 2084
static void trie_collect_stats(struct trie *t, struct trie_stat *s)
{
2085
	struct rt_trie_node *n;
2086
	struct fib_trie_iter iter;
O
Olof Johansson 已提交
2087

2088
	memset(s, 0, sizeof(*s));
O
Olof Johansson 已提交
2089

2090
	rcu_read_lock();
2091
	for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2092
		if (IS_LEAF(n)) {
2093 2094 2095 2096
			struct leaf *l = (struct leaf *)n;
			struct leaf_info *li;
			struct hlist_node *tmp;

2097 2098 2099 2100
			s->leaves++;
			s->totdepth += iter.depth;
			if (iter.depth > s->maxdepth)
				s->maxdepth = iter.depth;
2101 2102 2103

			hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
				++s->prefixes;
2104 2105 2106 2107 2108
		} else {
			const struct tnode *tn = (const struct tnode *) n;
			int i;

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

2112 2113 2114
			for (i = 0; i < (1<<tn->bits); i++)
				if (!tn->child[i])
					s->nullpointers++;
2115 2116
		}
	}
R
Robert Olsson 已提交
2117
	rcu_read_unlock();
2118 2119
}

2120 2121 2122 2123
/*
 *	This outputs /proc/net/fib_triestats
 */
static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2124
{
E
Eric Dumazet 已提交
2125
	unsigned int i, max, pointers, bytes, avdepth;
2126

2127 2128 2129 2130
	if (stat->leaves)
		avdepth = stat->totdepth*100 / stat->leaves;
	else
		avdepth = 0;
O
Olof Johansson 已提交
2131

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

2136 2137
	seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
	bytes = sizeof(struct leaf) * stat->leaves;
2138 2139 2140 2141

	seq_printf(seq, "\tPrefixes:       %u\n", stat->prefixes);
	bytes += sizeof(struct leaf_info) * stat->prefixes;

2142
	seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2143
	bytes += sizeof(struct tnode) * stat->tnodes;
2144

R
Robert Olsson 已提交
2145 2146
	max = MAX_STAT_DEPTH;
	while (max > 0 && stat->nodesizes[max-1] == 0)
2147
		max--;
2148

2149 2150 2151
	pointers = 0;
	for (i = 1; i <= max; i++)
		if (stat->nodesizes[i] != 0) {
2152
			seq_printf(seq, "  %u: %u",  i, stat->nodesizes[i]);
2153 2154 2155
			pointers += (1<<i) * stat->nodesizes[i];
		}
	seq_putc(seq, '\n');
2156
	seq_printf(seq, "\tPointers: %u\n", pointers);
R
Robert Olsson 已提交
2157

2158
	bytes += sizeof(struct rt_trie_node *) * pointers;
2159 2160
	seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
	seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
2161
}
R
Robert Olsson 已提交
2162

2163
#ifdef CONFIG_IP_FIB_TRIE_STATS
2164 2165 2166 2167
static void trie_show_usage(struct seq_file *seq,
			    const struct trie_use_stats *stats)
{
	seq_printf(seq, "\nCounters:\n---------\n");
2168 2169 2170 2171 2172 2173 2174 2175 2176
	seq_printf(seq, "gets = %u\n", stats->gets);
	seq_printf(seq, "backtracks = %u\n", stats->backtrack);
	seq_printf(seq, "semantic match passed = %u\n",
		   stats->semantic_match_passed);
	seq_printf(seq, "semantic match miss = %u\n",
		   stats->semantic_match_miss);
	seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
	seq_printf(seq, "skipped node resize = %u\n\n",
		   stats->resize_node_skipped);
2177
}
2178 2179
#endif /*  CONFIG_IP_FIB_TRIE_STATS */

2180
static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2181
{
2182 2183 2184 2185 2186 2187
	if (tb->tb_id == RT_TABLE_LOCAL)
		seq_puts(seq, "Local:\n");
	else if (tb->tb_id == RT_TABLE_MAIN)
		seq_puts(seq, "Main:\n");
	else
		seq_printf(seq, "Id %d:\n", tb->tb_id);
2188
}
2189

2190

2191 2192
static int fib_triestat_seq_show(struct seq_file *seq, void *v)
{
2193
	struct net *net = (struct net *)seq->private;
2194
	unsigned int h;
2195

2196
	seq_printf(seq,
2197 2198
		   "Basic info: size of leaf:"
		   " %Zd bytes, size of tnode: %Zd bytes.\n",
2199 2200
		   sizeof(struct leaf), sizeof(struct tnode));

2201 2202 2203 2204 2205 2206 2207 2208
	for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
		struct hlist_node *node;
		struct fib_table *tb;

		hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
			struct trie *t = (struct trie *) tb->tb_data;
			struct trie_stat stat;
2209

2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221
			if (!t)
				continue;

			fib_table_print(seq, tb);

			trie_collect_stats(t, &stat);
			trie_show_stats(seq, &stat);
#ifdef CONFIG_IP_FIB_TRIE_STATS
			trie_show_usage(seq, &t->stats);
#endif
		}
	}
2222

2223
	return 0;
2224 2225
}

2226
static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2227
{
2228
	return single_open_net(inode, file, fib_triestat_seq_show);
2229 2230
}

2231
static const struct file_operations fib_triestat_fops = {
2232 2233 2234 2235
	.owner	= THIS_MODULE,
	.open	= fib_triestat_seq_open,
	.read	= seq_read,
	.llseek	= seq_lseek,
2236
	.release = single_release_net,
2237 2238
};

2239
static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2240
{
2241 2242
	struct fib_trie_iter *iter = seq->private;
	struct net *net = seq_file_net(seq);
2243
	loff_t idx = 0;
2244
	unsigned int h;
2245

2246 2247 2248 2249
	for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
		struct hlist_node *node;
		struct fib_table *tb;
2250

2251
		hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2252
			struct rt_trie_node *n;
2253 2254 2255 2256 2257 2258 2259 2260 2261

			for (n = fib_trie_get_first(iter,
						    (struct trie *) tb->tb_data);
			     n; n = fib_trie_get_next(iter))
				if (pos == idx++) {
					iter->tb = tb;
					return n;
				}
		}
2262
	}
2263

2264 2265 2266
	return NULL;
}

2267
static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2268
	__acquires(RCU)
2269
{
2270
	rcu_read_lock();
2271
	return fib_trie_get_idx(seq, *pos);
2272 2273
}

2274
static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2275
{
2276
	struct fib_trie_iter *iter = seq->private;
2277
	struct net *net = seq_file_net(seq);
2278 2279 2280
	struct fib_table *tb = iter->tb;
	struct hlist_node *tb_node;
	unsigned int h;
2281
	struct rt_trie_node *n;
2282

2283
	++*pos;
2284 2285 2286 2287
	/* next node in same table */
	n = fib_trie_get_next(iter);
	if (n)
		return n;
2288

2289 2290
	/* walk rest of this hash chain */
	h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
E
Eric Dumazet 已提交
2291
	while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2292 2293 2294 2295 2296
		tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
		n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
		if (n)
			goto found;
	}
2297

2298 2299 2300 2301 2302 2303 2304 2305 2306
	/* new hash chain */
	while (++h < FIB_TABLE_HASHSZ) {
		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
		hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) {
			n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
			if (n)
				goto found;
		}
	}
2307
	return NULL;
2308 2309 2310 2311

found:
	iter->tb = tb;
	return n;
2312
}
2313

2314
static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2315
	__releases(RCU)
2316
{
2317 2318
	rcu_read_unlock();
}
O
Olof Johansson 已提交
2319

2320 2321
static void seq_indent(struct seq_file *seq, int n)
{
E
Eric Dumazet 已提交
2322 2323
	while (n-- > 0)
		seq_puts(seq, "   ");
2324
}
2325

2326
static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2327
{
S
Stephen Hemminger 已提交
2328
	switch (s) {
2329 2330 2331 2332 2333 2334
	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:
2335
		snprintf(buf, len, "scope=%d", s);
2336 2337 2338
		return buf;
	}
}
2339

2340
static const char *const rtn_type_names[__RTN_MAX] = {
2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353
	[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",
};
2354

E
Eric Dumazet 已提交
2355
static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2356 2357 2358
{
	if (t < __RTN_MAX && rtn_type_names[t])
		return rtn_type_names[t];
2359
	snprintf(buf, len, "type %u", t);
2360
	return buf;
2361 2362
}

2363 2364
/* Pretty print the trie */
static int fib_trie_seq_show(struct seq_file *seq, void *v)
2365
{
2366
	const struct fib_trie_iter *iter = seq->private;
2367
	struct rt_trie_node *n = v;
2368

2369 2370
	if (!node_parent_rcu(n))
		fib_table_print(seq, iter->tb);
2371

2372 2373
	if (IS_TNODE(n)) {
		struct tnode *tn = (struct tnode *) n;
S
Stephen Hemminger 已提交
2374
		__be32 prf = htonl(mask_pfx(tn->key, tn->pos));
O
Olof Johansson 已提交
2375

2376
		seq_indent(seq, iter->depth-1);
2377 2378
		seq_printf(seq, "  +-- %pI4/%d %d %d %d\n",
			   &prf, tn->pos, tn->bits, tn->full_children,
2379
			   tn->empty_children);
2380

2381 2382
	} else {
		struct leaf *l = (struct leaf *) n;
2383 2384
		struct leaf_info *li;
		struct hlist_node *node;
A
Al Viro 已提交
2385
		__be32 val = htonl(l->key);
2386 2387

		seq_indent(seq, iter->depth);
2388
		seq_printf(seq, "  |-- %pI4\n", &val);
2389 2390 2391 2392 2393 2394 2395 2396 2397 2398

		hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
			struct fib_alias *fa;

			list_for_each_entry_rcu(fa, &li->falh, fa_list) {
				char buf1[32], buf2[32];

				seq_indent(seq, iter->depth+1);
				seq_printf(seq, "  /%d %s %s", li->plen,
					   rtn_scope(buf1, sizeof(buf1),
2399
						     fa->fa_info->fib_scope),
2400 2401 2402
					   rtn_type(buf2, sizeof(buf2),
						    fa->fa_type));
				if (fa->fa_tos)
2403
					seq_printf(seq, " tos=%d", fa->fa_tos);
2404
				seq_putc(seq, '\n');
2405 2406
			}
		}
2407
	}
2408

2409 2410 2411
	return 0;
}

2412
static const struct seq_operations fib_trie_seq_ops = {
2413 2414 2415 2416
	.start  = fib_trie_seq_start,
	.next   = fib_trie_seq_next,
	.stop   = fib_trie_seq_stop,
	.show   = fib_trie_seq_show,
2417 2418
};

2419
static int fib_trie_seq_open(struct inode *inode, struct file *file)
2420
{
2421 2422
	return seq_open_net(inode, file, &fib_trie_seq_ops,
			    sizeof(struct fib_trie_iter));
2423 2424
}

2425
static const struct file_operations fib_trie_fops = {
2426 2427 2428 2429
	.owner  = THIS_MODULE,
	.open   = fib_trie_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2430
	.release = seq_release_net,
2431 2432
};

2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472
struct fib_route_iter {
	struct seq_net_private p;
	struct trie *main_trie;
	loff_t	pos;
	t_key	key;
};

static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
{
	struct leaf *l = NULL;
	struct trie *t = iter->main_trie;

	/* use cache location of last found key */
	if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
		pos -= iter->pos;
	else {
		iter->pos = 0;
		l = trie_firstleaf(t);
	}

	while (l && pos-- > 0) {
		iter->pos++;
		l = trie_nextleaf(l);
	}

	if (l)
		iter->key = pos;	/* remember it */
	else
		iter->pos = 0;		/* forget it */

	return l;
}

static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
	__acquires(RCU)
{
	struct fib_route_iter *iter = seq->private;
	struct fib_table *tb;

	rcu_read_lock();
2473
	tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510
	if (!tb)
		return NULL;

	iter->main_trie = (struct trie *) tb->tb_data;
	if (*pos == 0)
		return SEQ_START_TOKEN;
	else
		return fib_route_get_idx(iter, *pos - 1);
}

static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
{
	struct fib_route_iter *iter = seq->private;
	struct leaf *l = v;

	++*pos;
	if (v == SEQ_START_TOKEN) {
		iter->pos = 0;
		l = trie_firstleaf(iter->main_trie);
	} else {
		iter->pos++;
		l = trie_nextleaf(l);
	}

	if (l)
		iter->key = l->key;
	else
		iter->pos = 0;
	return l;
}

static void fib_route_seq_stop(struct seq_file *seq, void *v)
	__releases(RCU)
{
	rcu_read_unlock();
}

E
Eric Dumazet 已提交
2511
static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2512
{
E
Eric Dumazet 已提交
2513
	unsigned int flags = 0;
2514

E
Eric Dumazet 已提交
2515 2516
	if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
		flags = RTF_REJECT;
2517 2518
	if (fi && fi->fib_nh->nh_gw)
		flags |= RTF_GATEWAY;
A
Al Viro 已提交
2519
	if (mask == htonl(0xFFFFFFFF))
2520 2521 2522
		flags |= RTF_HOST;
	flags |= RTF_UP;
	return flags;
2523 2524
}

2525 2526 2527
/*
 *	This outputs /proc/net/route.
 *	The format of the file is not supposed to be changed
E
Eric Dumazet 已提交
2528
 *	and needs to be same as fib_hash output to avoid breaking
2529 2530 2531
 *	legacy utilities
 */
static int fib_route_seq_show(struct seq_file *seq, void *v)
2532
{
2533
	struct leaf *l = v;
2534 2535
	struct leaf_info *li;
	struct hlist_node *node;
2536

2537 2538 2539 2540 2541 2542
	if (v == SEQ_START_TOKEN) {
		seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
			   "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
			   "\tWindow\tIRTT");
		return 0;
	}
2543

2544
	hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2545
		struct fib_alias *fa;
A
Al Viro 已提交
2546
		__be32 mask, prefix;
O
Olof Johansson 已提交
2547

2548 2549
		mask = inet_make_mask(li->plen);
		prefix = htonl(l->key);
2550

2551
		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2552
			const struct fib_info *fi = fa->fa_info;
E
Eric Dumazet 已提交
2553
			unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2554
			int len;
2555

2556 2557 2558
			if (fa->fa_type == RTN_BROADCAST
			    || fa->fa_type == RTN_MULTICAST)
				continue;
2559

2560
			if (fi)
2561 2562 2563
				seq_printf(seq,
					 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
					 "%d\t%08X\t%d\t%u\t%u%n",
2564 2565 2566 2567 2568
					 fi->fib_dev ? fi->fib_dev->name : "*",
					 prefix,
					 fi->fib_nh->nh_gw, flags, 0, 0,
					 fi->fib_priority,
					 mask,
2569 2570
					 (fi->fib_advmss ?
					  fi->fib_advmss + 40 : 0),
2571
					 fi->fib_window,
2572
					 fi->fib_rtt >> 3, &len);
2573
			else
2574 2575 2576
				seq_printf(seq,
					 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
					 "%d\t%08X\t%d\t%u\t%u%n",
2577
					 prefix, 0, flags, 0, 0, 0,
2578
					 mask, 0, 0, 0, &len);
2579

2580
			seq_printf(seq, "%*s\n", 127 - len, "");
2581
		}
2582 2583 2584 2585 2586
	}

	return 0;
}

2587
static const struct seq_operations fib_route_seq_ops = {
2588 2589 2590
	.start  = fib_route_seq_start,
	.next   = fib_route_seq_next,
	.stop   = fib_route_seq_stop,
2591
	.show   = fib_route_seq_show,
2592 2593
};

2594
static int fib_route_seq_open(struct inode *inode, struct file *file)
2595
{
2596
	return seq_open_net(inode, file, &fib_route_seq_ops,
2597
			    sizeof(struct fib_route_iter));
2598 2599
}

2600
static const struct file_operations fib_route_fops = {
2601 2602 2603 2604
	.owner  = THIS_MODULE,
	.open   = fib_route_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2605
	.release = seq_release_net,
2606 2607
};

2608
int __net_init fib_proc_init(struct net *net)
2609
{
2610
	if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
2611 2612
		goto out1;

2613 2614
	if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
				  &fib_triestat_fops))
2615 2616
		goto out2;

2617
	if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
2618 2619
		goto out3;

2620
	return 0;
2621 2622

out3:
2623
	proc_net_remove(net, "fib_triestat");
2624
out2:
2625
	proc_net_remove(net, "fib_trie");
2626 2627
out1:
	return -ENOMEM;
2628 2629
}

2630
void __net_exit fib_proc_exit(struct net *net)
2631
{
2632 2633 2634
	proc_net_remove(net, "fib_trie");
	proc_net_remove(net, "fib_triestat");
	proc_net_remove(net, "route");
2635 2636 2637
}

#endif /* CONFIG_PROC_FS */