fib_trie.c 61.6 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 163
static void put_child(struct trie *t, struct tnode *tn, int i, struct rt_trie_node *n);
static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
164
				  int wasfull);
165
static struct rt_trie_node *resize(struct trie *t, struct tnode *tn);
166 167
static struct tnode *inflate(struct trie *t, struct tnode *tn);
static struct tnode *halve(struct trie *t, struct tnode *tn);
J
Jarek Poplawski 已提交
168 169
/* tnodes to free after resize(); protected by RTNL */
static struct tnode *tnode_free_head;
170 171 172 173 174 175 176 177
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;
178

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

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

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

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

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

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

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

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

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

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

E
Eric Dumazet 已提交
226 227 228 229
/*
 * 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)
230
{
E
Eric Dumazet 已提交
231
	BUG_ON(i >= 1U << tn->bits);
232

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

336

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

*/

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

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

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

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

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

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

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

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

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

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

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

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

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

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);
	}
433 434 435 436 437

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

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

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

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

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

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

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

493
static inline void put_child(struct trie *t, struct tnode *tn, int i,
494
			     struct rt_trie_node *n)
495 496 497 498
{
	tnode_put_child_reorg(tn, i, n, -1);
}

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

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

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

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

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

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

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

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

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

543
	if (!tn)
544 545
		return NULL;

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

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

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

	check_tnode(tn);
622

623 624
	/* Keep root node larger  */

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

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

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

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

	check_tnode(tn);

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

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

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

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

678

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

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

			/* compress one level */

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

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

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

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

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

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

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

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

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

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

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

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

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

757 758
			put_child(t, tn, 2*i, (struct rt_trie_node *) left);
			put_child(t, tn, 2*i+1, (struct rt_trie_node *) right);
759 760 761
		}
	}

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

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

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

774
		if (IS_LEAF(node) || ((struct tnode *) node)->pos >
775
		   tn->pos + tn->bits - 1) {
776 777 778
			if (tkey_extract_bits(node->key,
					      oldtnode->pos + oldtnode->bits,
					      1) == 0)
779 780 781 782 783 784 785 786 787 788
				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) {
E
Eric Dumazet 已提交
789 790
			put_child(t, tn, 2*i, rtnl_dereference(inode->child[0]));
			put_child(t, tn, 2*i+1, rtnl_dereference(inode->child[1]));
791

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

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

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

O
Olof Johansson 已提交
819 820
		left = (struct tnode *) tnode_get_child(tn, 2*i);
		put_child(t, tn, 2*i, NULL);
821

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

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

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

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

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

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

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

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

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

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

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

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

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

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

880
			put_child(t, tn, i/2, (struct rt_trie_node *)newn);
881 882 883
		}

	}
884

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

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

891 892 893 894 895
		/* 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 已提交
896
			continue;
S
Stephen Hemminger 已提交
897
		}
O
Olof Johansson 已提交
898 899

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

904
		/* Two nonempty children */
O
Olof Johansson 已提交
905 906 907 908 909
		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));
910
	}
J
Jarek Poplawski 已提交
911
	tnode_free_safe(oldtnode);
912
	return tn;
913
nomem:
E
Eric Dumazet 已提交
914 915
	tnode_clean_free(tn);
	return ERR_PTR(-ENOMEM);
916 917
}

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

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

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

931 932 933
	return NULL;
}

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

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

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

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

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

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

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

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

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

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

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

996 997 998
	return NULL;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	if (tp && tp->pos + tp->bits > 32)
J
Joe Perches 已提交
1171 1172
		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 已提交
1173

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

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

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

	if (plen > 32)
		return -EINVAL;

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

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

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

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

	key = key & mask;

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

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

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

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

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

1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262
		/* 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;
			}
		}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1370
			if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1371
				continue;
1372 1373
			if (fi->fib_dead)
				continue;
1374
			if (fa->fa_info->fib_scope < flp->flowi4_scope)
1375 1376 1377 1378
				continue;
			fib_alias_accessed(fa);
			err = fib_props[fa->fa_type].error;
			if (err) {
1379
#ifdef CONFIG_IP_FIB_TRIE_STATS
1380
				t->stats.semantic_match_passed++;
1381
#endif
1382
				return err;
1383 1384 1385 1386 1387 1388 1389 1390
			}
			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;
1391
				if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
1392 1393 1394 1395 1396
					continue;

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

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

1415
	return 1;
1416 1417
}

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

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

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

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

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

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

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

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

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

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

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

		cn = (struct tnode *)n;
1477

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

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

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

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

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

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

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

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

1548 1549 1550 1551
		/*
		 * In short: If skipped bits in this node do not match
		 * the search key, enter the "prefix matching"
		 * state.directly.
O
Olof Johansson 已提交
1552 1553
		 */
		if (pref_mismatch) {
1554
			int mp = KEYLENGTH - fls(pref_mismatch);
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);
J
Joe Perches 已提交
1622
		put_child(t, 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 1659 1660 1661 1662 1663 1664
		return -ESRCH;

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

	if (!fa)
		return -ESRCH;

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

	fa_to_delete = NULL;
1668 1669
	fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
	list_for_each_entry_continue(fa, fa_head, fa_list) {
1670 1671 1672 1673 1674
		struct fib_info *fi = fa->fa_info;

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

1675 1676
		if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
		    (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1677
		     fa->fa_info->fib_scope == cfg->fc_scope) &&
1678 1679
		    (!cfg->fc_prefsrc ||
		     fi->fib_prefsrc == cfg->fc_prefsrc) &&
1680 1681 1682
		    (!cfg->fc_protocol ||
		     fi->fib_protocol == cfg->fc_protocol) &&
		    fib_nh_match(cfg, fi) == 0) {
1683 1684 1685 1686 1687
			fa_to_delete = fa;
			break;
		}
	}

O
Olof Johansson 已提交
1688 1689
	if (!fa_to_delete)
		return -ESRCH;
1690

O
Olof Johansson 已提交
1691
	fa = fa_to_delete;
1692
	rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1693
		  &cfg->fc_nlinfo, 0);
O
Olof Johansson 已提交
1694 1695

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

R
Robert Olsson 已提交
1698
	list_del_rcu(&fa->fa_list);
1699

1700 1701 1702
	if (!plen)
		tb->tb_num_default--;

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

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

O
Olof Johansson 已提交
1711
	if (fa->fa_state & FA_S_ACCESSED)
1712
		rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1713

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

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

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

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

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

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

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

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

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

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

	return NULL; /* Root of trie */
}

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

	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)
{
1806
	struct rt_trie_node *c = (struct rt_trie_node *) l;
1807
	struct tnode *p = node_parent_rcu(c);
1808 1809 1810 1811 1812

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

	return leaf_walk_rcu(p, c);
1813 1814
}

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

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

1822 1823 1824 1825
	return l;
}


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

1835
	for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1836
		found += trie_flush_leaf(l);
1837 1838

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

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

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

1850 1851 1852 1853 1854
void fib_free_table(struct fib_table *tb)
{
	kfree(tb);
}

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

1863
	s_i = cb->args[5];
1864 1865
	i = 0;

R
Robert Olsson 已提交
1866 1867 1868
	/* rcu_read_lock is hold by caller */

	list_for_each_entry_rcu(fa, fah, fa_list) {
1869 1870 1871 1872 1873 1874 1875 1876 1877 1878
		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,
1879
				  xkey,
1880 1881
				  plen,
				  fa->fa_tos,
1882
				  fa->fa_info, NLM_F_MULTI) < 0) {
1883
			cb->args[5] = i;
1884
			return -1;
O
Olof Johansson 已提交
1885
		}
1886 1887
		i++;
	}
1888
	cb->args[5] = i;
1889 1890 1891
	return skb->len;
}

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

1899
	s_i = cb->args[4];
1900
	i = 0;
1901

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

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

1912
		if (list_empty(&li->falh))
1913 1914
			continue;

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

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

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

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

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

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

1965 1966 1967
	return skb->len;
}

1968
void __init fib_trie_init(void)
1969
{
1970 1971
	fn_alias_kmem = kmem_cache_create("ip_fib_alias",
					  sizeof(struct fib_alias),
1972 1973 1974 1975 1976 1977
					  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);
1978
}
1979

1980

1981
struct fib_table *fib_trie_table(u32 id)
1982 1983 1984 1985 1986 1987 1988 1989 1990 1991
{
	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;
1992
	tb->tb_default = -1;
1993
	tb->tb_num_default = 0;
1994 1995

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

	return tb;
}

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

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

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

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

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

2040 2041
		++cindex;
	}
O
Olof Johansson 已提交
2042

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

	/* got root? */
	return NULL;
2054 2055
}

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

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

	n = rcu_dereference(t->trie);
2065
	if (!n)
2066
		return NULL;
2067

2068 2069 2070 2071 2072 2073 2074 2075
	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 已提交
2076
	}
2077 2078

	return n;
2079
}
O
Olof Johansson 已提交
2080

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

2086
	memset(s, 0, sizeof(*s));
O
Olof Johansson 已提交
2087

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2161
#ifdef CONFIG_IP_FIB_TRIE_STATS
2162 2163 2164 2165
static void trie_show_usage(struct seq_file *seq,
			    const struct trie_use_stats *stats)
{
	seq_printf(seq, "\nCounters:\n---------\n");
2166 2167 2168 2169 2170 2171 2172 2173 2174
	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);
2175
}
2176 2177
#endif /*  CONFIG_IP_FIB_TRIE_STATS */

2178
static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2179
{
2180 2181 2182 2183 2184 2185
	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);
2186
}
2187

2188

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

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

2199 2200 2201 2202 2203 2204 2205 2206
	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;
2207

2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219
			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
		}
	}
2220

2221
	return 0;
2222 2223
}

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

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

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

2244 2245 2246 2247
	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;
2248

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

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

2262 2263 2264
	return NULL;
}

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

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

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

2287 2288
	/* walk rest of this hash chain */
	h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
E
Eric Dumazet 已提交
2289
	while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2290 2291 2292 2293 2294
		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;
	}
2295

2296 2297 2298 2299 2300 2301 2302 2303 2304
	/* 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;
		}
	}
2305
	return NULL;
2306 2307 2308 2309

found:
	iter->tb = tb;
	return n;
2310
}
2311

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

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

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

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

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

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

2367 2368
	if (!node_parent_rcu(n))
		fib_table_print(seq, iter->tb);
2369

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

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

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

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

		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),
2397
						     fa->fa_info->fib_scope),
2398 2399 2400
					   rtn_type(buf2, sizeof(buf2),
						    fa->fa_type));
				if (fa->fa_tos)
2401
					seq_printf(seq, " tos=%d", fa->fa_tos);
2402
				seq_putc(seq, '\n');
2403 2404
			}
		}
2405
	}
2406

2407 2408 2409
	return 0;
}

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

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

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

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
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();
2471
	tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2472 2473 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
	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 已提交
2509
static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2510
{
E
Eric Dumazet 已提交
2511
	unsigned int flags = 0;
2512

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

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

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

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

2546 2547
		mask = inet_make_mask(li->plen);
		prefix = htonl(l->key);
2548

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

2554 2555 2556
			if (fa->fa_type == RTN_BROADCAST
			    || fa->fa_type == RTN_MULTICAST)
				continue;
2557

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

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

	return 0;
}

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

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

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

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

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

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

2618
	return 0;
2619 2620

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

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

#endif /* CONFIG_PROC_FS */