fib_trie.c 61.0 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
	union {
		struct rcu_head rcu;
J
Jarek Poplawski 已提交
128
		struct tnode *tnode_free;
129
	};
E
Eric Dumazet 已提交
130
	struct rt_trie_node __rcu *child[0];
131 132 133 134 135 136 137 138 139
};

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

334

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

*/

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

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

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

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

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

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

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

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

static void __tnode_free_rcu(struct rcu_head *head)
386
{
R
Robert Olsson 已提交
387
	struct tnode *tn = container_of(head, struct tnode, rcu);
388
	size_t size = sizeof(struct tnode) +
389
		      (sizeof(struct rt_trie_node *) << tn->bits);
390 391 392

	if (size <= PAGE_SIZE)
		kfree(tn);
A
Al Viro 已提交
393 394
	else
		vfree(tn);
395 396
}

R
Robert Olsson 已提交
397 398
static inline void tnode_free(struct tnode *tn)
{
399 400 401
	if (IS_LEAF(tn))
		free_leaf((struct leaf *) tn);
	else
R
Robert Olsson 已提交
402
		call_rcu(&tn->rcu, __tnode_free_rcu);
R
Robert Olsson 已提交
403 404
}

J
Jarek Poplawski 已提交
405 406 407
static void tnode_free_safe(struct tnode *tn)
{
	BUG_ON(IS_LEAF(tn));
408 409
	tn->tnode_free = tnode_free_head;
	tnode_free_head = tn;
410
	tnode_free_size += sizeof(struct tnode) +
411
			   (sizeof(struct rt_trie_node *) << tn->bits);
J
Jarek Poplawski 已提交
412 413 414 415 416 417 418 419 420 421 422
}

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);
	}
423 424 425 426 427

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

R
Robert Olsson 已提交
430 431
static struct leaf *leaf_new(void)
{
432
	struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
R
Robert Olsson 已提交
433 434 435 436 437 438 439 440 441 442 443 444
	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;
445
		li->mask_plen = ntohl(inet_make_mask(plen));
R
Robert Olsson 已提交
446 447 448 449 450
		INIT_LIST_HEAD(&li->falh);
	}
	return li;
}

451
static struct tnode *tnode_new(t_key key, int pos, int bits)
452
{
453
	size_t sz = sizeof(struct tnode) + (sizeof(struct rt_trie_node *) << bits);
454
	struct tnode *tn = tnode_alloc(sz);
455

O
Olof Johansson 已提交
456
	if (tn) {
R
Robert Olsson 已提交
457
		tn->parent = T_TNODE;
458 459 460 461 462 463
		tn->pos = pos;
		tn->bits = bits;
		tn->key = key;
		tn->full_children = 0;
		tn->empty_children = 1<<bits;
	}
464

E
Eric Dumazet 已提交
465
	pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode),
L
Lin Ming 已提交
466
		 sizeof(struct rt_trie_node *) << bits);
467 468 469 470 471 472 473 474
	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
 */

475
static inline int tnode_full(const struct tnode *tn, const struct rt_trie_node *n)
476
{
477
	if (n == NULL || IS_LEAF(n))
478 479 480 481 482
		return 0;

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

L
Lin Ming 已提交
483
static inline void put_child(struct tnode *tn, int i,
484
			     struct rt_trie_node *n)
485 486 487 488
{
	tnode_put_child_reorg(tn, i, n, -1);
}

489
 /*
490 491 492 493
  * Add a child at position i overwriting the old value.
  * Update the value of full_children and empty_children.
  */

494
static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
495
				  int wasfull)
496
{
E
Eric Dumazet 已提交
497
	struct rt_trie_node *chi = rtnl_dereference(tn->child[i]);
498 499
	int isfull;

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

502 503 504 505 506
	/* update emptyChildren */
	if (n == NULL && chi != NULL)
		tn->empty_children++;
	else if (n != NULL && chi == NULL)
		tn->empty_children--;
507

508
	/* update fullChildren */
O
Olof Johansson 已提交
509
	if (wasfull == -1)
510 511 512
		wasfull = tnode_full(tn, chi);

	isfull = tnode_full(tn, n);
513
	if (wasfull && !isfull)
514
		tn->full_children--;
515
	else if (!wasfull && isfull)
516
		tn->full_children++;
O
Olof Johansson 已提交
517

518
	if (n)
S
Stephen Hemminger 已提交
519
		node_set_parent(n, tn);
520

521
	rcu_assign_pointer(tn->child[i], n);
522 523
}

J
Jens Låås 已提交
524
#define MAX_WORK 10
525
static struct rt_trie_node *resize(struct trie *t, struct tnode *tn)
526 527
{
	int i;
528
	struct tnode *old_tn;
529 530
	int inflate_threshold_use;
	int halve_threshold_use;
J
Jens Låås 已提交
531
	int max_work;
532

533
	if (!tn)
534 535
		return NULL;

S
Stephen Hemminger 已提交
536 537
	pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
		 tn, inflate_threshold, halve_threshold);
538 539 540

	/* No children */
	if (tn->empty_children == tnode_child_length(tn)) {
J
Jarek Poplawski 已提交
541
		tnode_free_safe(tn);
542 543 544 545
		return NULL;
	}
	/* One child */
	if (tn->empty_children == tnode_child_length(tn) - 1)
J
Jens Låås 已提交
546
		goto one_child;
547
	/*
548 549 550 551 552
	 * Double as long as the resulting node has a number of
	 * nonempty nodes that are above the threshold.
	 */

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

	check_tnode(tn);
612

613 614
	/* Keep root node larger  */

615
	if (!node_parent((struct rt_trie_node *)tn)) {
J
Jens Låås 已提交
616 617
		inflate_threshold_use = inflate_threshold_root;
		halve_threshold_use = halve_threshold_root;
E
Eric Dumazet 已提交
618
	} else {
619
		inflate_threshold_use = inflate_threshold;
J
Jens Låås 已提交
620 621
		halve_threshold_use = halve_threshold;
	}
622

J
Jens Låås 已提交
623 624
	max_work = MAX_WORK;
	while ((tn->full_children > 0 &&  max_work-- &&
625 626 627
		50 * (tn->full_children + tnode_child_length(tn)
		      - tn->empty_children)
		>= inflate_threshold_use * tnode_child_length(tn))) {
628

629 630
		old_tn = tn;
		tn = inflate(t, tn);
631

632 633
		if (IS_ERR(tn)) {
			tn = old_tn;
634 635 636 637 638
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.resize_node_skipped++;
#endif
			break;
		}
639 640 641 642
	}

	check_tnode(tn);

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

647 648 649 650
	/*
	 * Halve as long as the number of empty children in this
	 * node is above threshold.
	 */
651

J
Jens Låås 已提交
652 653
	max_work = MAX_WORK;
	while (tn->bits > 1 &&  max_work-- &&
654
	       100 * (tnode_child_length(tn) - tn->empty_children) <
655
	       halve_threshold_use * tnode_child_length(tn)) {
656

657 658 659 660
		old_tn = tn;
		tn = halve(t, tn);
		if (IS_ERR(tn)) {
			tn = old_tn;
661 662 663 664 665 666
#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.resize_node_skipped++;
#endif
			break;
		}
	}
667

668

669
	/* Only one child remains */
J
Jens Låås 已提交
670 671
	if (tn->empty_children == tnode_child_length(tn) - 1) {
one_child:
672
		for (i = 0; i < tnode_child_length(tn); i++) {
673
			struct rt_trie_node *n;
674

E
Eric Dumazet 已提交
675
			n = rtnl_dereference(tn->child[i]);
R
Robert Olsson 已提交
676
			if (!n)
O
Olof Johansson 已提交
677 678 679 680
				continue;

			/* compress one level */

S
Stephen Hemminger 已提交
681
			node_set_parent(n, NULL);
J
Jarek Poplawski 已提交
682
			tnode_free_safe(tn);
O
Olof Johansson 已提交
683
			return n;
684
		}
J
Jens Låås 已提交
685
	}
686
	return (struct rt_trie_node *) tn;
687 688
}

E
Eric Dumazet 已提交
689 690 691 692 693 694 695 696 697 698 699 700 701 702

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

703
static struct tnode *inflate(struct trie *t, struct tnode *tn)
704 705 706 707 708
{
	struct tnode *oldtnode = tn;
	int olen = tnode_child_length(tn);
	int i;

S
Stephen Hemminger 已提交
709
	pr_debug("In inflate\n");
710 711 712

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

S
Stephen Hemminger 已提交
713
	if (!tn)
714
		return ERR_PTR(-ENOMEM);
715 716

	/*
717 718 719
	 * 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
720 721
	 * of tnode is ignored.
	 */
O
Olof Johansson 已提交
722 723

	for (i = 0; i < olen; i++) {
724
		struct tnode *inode;
725

726
		inode = (struct tnode *) tnode_get_child(oldtnode, i);
727 728 729 730 731
		if (inode &&
		    IS_TNODE(inode) &&
		    inode->pos == oldtnode->pos + oldtnode->bits &&
		    inode->bits > 1) {
			struct tnode *left, *right;
S
Stephen Hemminger 已提交
732
			t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
733

734 735
			left = tnode_new(inode->key&(~m), inode->pos + 1,
					 inode->bits - 1);
736 737
			if (!left)
				goto nomem;
O
Olof Johansson 已提交
738

739 740 741
			right = tnode_new(inode->key|m, inode->pos + 1,
					  inode->bits - 1);

742
			if (!right) {
743 744
				tnode_free(left);
				goto nomem;
745
			}
746

L
Lin Ming 已提交
747 748
			put_child(tn, 2*i, (struct rt_trie_node *) left);
			put_child(tn, 2*i+1, (struct rt_trie_node *) right);
749 750 751
		}
	}

O
Olof Johansson 已提交
752
	for (i = 0; i < olen; i++) {
753
		struct tnode *inode;
754
		struct rt_trie_node *node = tnode_get_child(oldtnode, i);
O
Olof Johansson 已提交
755 756
		struct tnode *left, *right;
		int size, j;
757

758 759 760 761 762 763
		/* An empty child */
		if (node == NULL)
			continue;

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

764
		if (IS_LEAF(node) || ((struct tnode *) node)->pos >
765
		   tn->pos + tn->bits - 1) {
766 767 768
			if (tkey_extract_bits(node->key,
					      oldtnode->pos + oldtnode->bits,
					      1) == 0)
L
Lin Ming 已提交
769
				put_child(tn, 2*i, node);
770
			else
L
Lin Ming 已提交
771
				put_child(tn, 2*i+1, node);
772 773 774 775 776 777 778
			continue;
		}

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

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

J
Jarek Poplawski 已提交
782
			tnode_free_safe(inode);
O
Olof Johansson 已提交
783
			continue;
784 785
		}

O
Olof Johansson 已提交
786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803
		/* 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)
		 */
804

O
Olof Johansson 已提交
805 806 807
		/* Use the old key, but set the new significant
		 *   bit to zero.
		 */
808

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

O
Olof Johansson 已提交
812
		BUG_ON(!left);
813

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

O
Olof Johansson 已提交
817
		BUG_ON(!right);
818

O
Olof Johansson 已提交
819 820
		size = tnode_child_length(left);
		for (j = 0; j < size; j++) {
L
Lin Ming 已提交
821 822
			put_child(left, j, rtnl_dereference(inode->child[j]));
			put_child(right, j, rtnl_dereference(inode->child[j + size]));
823
		}
L
Lin Ming 已提交
824 825
		put_child(tn, 2*i, resize(t, left));
		put_child(tn, 2*i+1, resize(t, right));
O
Olof Johansson 已提交
826

J
Jarek Poplawski 已提交
827
		tnode_free_safe(inode);
828
	}
J
Jarek Poplawski 已提交
829
	tnode_free_safe(oldtnode);
830
	return tn;
831
nomem:
E
Eric Dumazet 已提交
832 833
	tnode_clean_free(tn);
	return ERR_PTR(-ENOMEM);
834 835
}

836
static struct tnode *halve(struct trie *t, struct tnode *tn)
837 838
{
	struct tnode *oldtnode = tn;
839
	struct rt_trie_node *left, *right;
840 841 842
	int i;
	int olen = tnode_child_length(tn);

S
Stephen Hemminger 已提交
843
	pr_debug("In halve\n");
844 845

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

847 848
	if (!tn)
		return ERR_PTR(-ENOMEM);
849 850

	/*
851 852 853
	 * 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
854 855 856
	 * of tnode is ignored.
	 */

O
Olof Johansson 已提交
857
	for (i = 0; i < olen; i += 2) {
858 859
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
860

861
		/* Two nonempty children */
S
Stephen Hemminger 已提交
862
		if (left && right) {
863
			struct tnode *newn;
S
Stephen Hemminger 已提交
864

865
			newn = tnode_new(left->key, tn->pos + tn->bits, 1);
S
Stephen Hemminger 已提交
866 867

			if (!newn)
868
				goto nomem;
S
Stephen Hemminger 已提交
869

L
Lin Ming 已提交
870
			put_child(tn, i/2, (struct rt_trie_node *)newn);
871 872 873
		}

	}
874

O
Olof Johansson 已提交
875 876 877
	for (i = 0; i < olen; i += 2) {
		struct tnode *newBinNode;

878 879
		left = tnode_get_child(oldtnode, i);
		right = tnode_get_child(oldtnode, i+1);
880

881 882 883 884
		/* At least one of the children is empty */
		if (left == NULL) {
			if (right == NULL)    /* Both are empty */
				continue;
L
Lin Ming 已提交
885
			put_child(tn, i/2, right);
O
Olof Johansson 已提交
886
			continue;
S
Stephen Hemminger 已提交
887
		}
O
Olof Johansson 已提交
888 889

		if (right == NULL) {
L
Lin Ming 已提交
890
			put_child(tn, i/2, left);
O
Olof Johansson 已提交
891 892
			continue;
		}
893

894
		/* Two nonempty children */
O
Olof Johansson 已提交
895
		newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
L
Lin Ming 已提交
896 897 898 899
		put_child(tn, i/2, NULL);
		put_child(newBinNode, 0, left);
		put_child(newBinNode, 1, right);
		put_child(tn, i/2, resize(t, newBinNode));
900
	}
J
Jarek Poplawski 已提交
901
	tnode_free_safe(oldtnode);
902
	return tn;
903
nomem:
E
Eric Dumazet 已提交
904 905
	tnode_clean_free(tn);
	return ERR_PTR(-ENOMEM);
906 907
}

R
Robert Olsson 已提交
908
/* readside must use rcu_read_lock currently dump routines
R
Robert Olsson 已提交
909 910
 via get_fa_head and dump */

R
Robert Olsson 已提交
911
static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
912
{
R
Robert Olsson 已提交
913
	struct hlist_head *head = &l->list;
914 915
	struct leaf_info *li;

916
	hlist_for_each_entry_rcu(li, head, hlist)
917
		if (li->plen == plen)
918
			return li;
O
Olof Johansson 已提交
919

920 921 922
	return NULL;
}

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

O
Olof Johansson 已提交
927 928
	if (!li)
		return NULL;
929

O
Olof Johansson 已提交
930
	return &li->falh;
931 932 933 934
}

static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
{
935 936 937 938 939
	struct leaf_info *li = NULL, *last = NULL;

	if (hlist_empty(head)) {
		hlist_add_head_rcu(&new->hlist, head);
	} else {
940
		hlist_for_each_entry(li, head, hlist) {
941 942 943 944 945 946 947 948 949 950
			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);
	}
951 952
}

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

955 956 957 958 959
static struct leaf *
fib_find_node(struct trie *t, u32 key)
{
	int pos;
	struct tnode *tn;
960
	struct rt_trie_node *n;
961 962

	pos = 0;
E
Eric Dumazet 已提交
963
	n = rcu_dereference_rtnl(t->trie);
964 965 966

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

968
		check_tnode(tn);
O
Olof Johansson 已提交
969

970
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
O
Olof Johansson 已提交
971
			pos = tn->pos + tn->bits;
972 973 974 975
			n = tnode_get_child_rcu(tn,
						tkey_extract_bits(key,
								  tn->pos,
								  tn->bits));
O
Olof Johansson 已提交
976
		} else
977 978 979 980
			break;
	}
	/* Case we have found a leaf. Compare prefixes */

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

984 985 986
	return NULL;
}

987
static void trie_rebalance(struct trie *t, struct tnode *tn)
988 989
{
	int wasfull;
R
Robert Olsson 已提交
990
	t_key cindex, key;
S
Stephen Hemminger 已提交
991
	struct tnode *tp;
992

R
Robert Olsson 已提交
993 994
	key = tn->key;

995
	while (tn != NULL && (tp = node_parent((struct rt_trie_node *)tn)) != NULL) {
996 997
		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
		wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
J
Joe Perches 已提交
998
		tn = (struct tnode *)resize(t, tn);
999

J
Joe Perches 已提交
1000
		tnode_put_child_reorg(tp, cindex,
1001
				      (struct rt_trie_node *)tn, wasfull);
O
Olof Johansson 已提交
1002

1003
		tp = node_parent((struct rt_trie_node *) tn);
1004
		if (!tp)
1005
			rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1006

J
Jarek Poplawski 已提交
1007
		tnode_free_flush();
S
Stephen Hemminger 已提交
1008
		if (!tp)
1009
			break;
S
Stephen Hemminger 已提交
1010
		tn = tp;
1011
	}
S
Stephen Hemminger 已提交
1012

1013
	/* Handle last (top) tnode */
1014
	if (IS_TNODE(tn))
J
Joe Perches 已提交
1015
		tn = (struct tnode *)resize(t, tn);
1016

1017
	rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1018
	tnode_free_flush();
1019 1020
}

R
Robert Olsson 已提交
1021 1022
/* only used from updater-side */

1023
static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
1024 1025 1026
{
	int pos, newpos;
	struct tnode *tp = NULL, *tn = NULL;
1027
	struct rt_trie_node *n;
1028 1029
	struct leaf *l;
	int missbit;
1030
	struct list_head *fa_head = NULL;
1031 1032 1033 1034
	struct leaf_info *li;
	t_key cindex;

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

1037 1038
	/* 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,
1039
	 * and we should just put our new leaf in that.
1040 1041
	 * 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
1042 1043
	 * not be the parent's 'pos'+'bits'!
	 *
1044
	 * If it does match the current key, get pos/bits from it, extract
1045 1046 1047 1048
	 * 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.
	 *
1049 1050 1051
	 * 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.
1052 1053 1054 1055 1056
	 * 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 已提交
1057

1058
		check_tnode(tn);
O
Olof Johansson 已提交
1059

1060
		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1061
			tp = tn;
O
Olof Johansson 已提交
1062
			pos = tn->pos + tn->bits;
1063 1064 1065 1066
			n = tnode_get_child(tn,
					    tkey_extract_bits(key,
							      tn->pos,
							      tn->bits));
1067

S
Stephen Hemminger 已提交
1068
			BUG_ON(n && node_parent(n) != tn);
O
Olof Johansson 已提交
1069
		} else
1070 1071 1072 1073 1074 1075
			break;
	}

	/*
	 * n  ----> NULL, LEAF or TNODE
	 *
1076
	 * tp is n's (parent) ----> NULL or TNODE
1077 1078
	 */

O
Olof Johansson 已提交
1079
	BUG_ON(tp && IS_LEAF(tp));
1080 1081 1082

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

1083
	if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1084
		l = (struct leaf *) n;
1085
		li = leaf_info_new(plen);
O
Olof Johansson 已提交
1086

1087 1088
		if (!li)
			return NULL;
1089 1090 1091 1092 1093 1094 1095

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

1096 1097
	if (!l)
		return NULL;
1098 1099 1100 1101

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

1102
	if (!li) {
1103
		free_leaf(l);
1104
		return NULL;
1105
	}
1106 1107 1108 1109 1110

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

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

1113
		node_set_parent((struct rt_trie_node *)l, tp);
1114

O
Olof Johansson 已提交
1115
		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
L
Lin Ming 已提交
1116
		put_child(tp, cindex, (struct rt_trie_node *)l);
O
Olof Johansson 已提交
1117 1118
	} else {
		/* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1119 1120
		/*
		 *  Add a new tnode here
1121 1122 1123 1124
		 *  first tnode need some special handling
		 */

		if (tp)
O
Olof Johansson 已提交
1125
			pos = tp->pos+tp->bits;
1126
		else
O
Olof Johansson 已提交
1127 1128
			pos = 0;

1129
		if (n) {
1130 1131
			newpos = tkey_mismatch(key, pos, n->key);
			tn = tnode_new(n->key, newpos, 1);
O
Olof Johansson 已提交
1132
		} else {
1133
			newpos = 0;
1134
			tn = tnode_new(key, newpos, 1); /* First tnode */
1135 1136
		}

1137
		if (!tn) {
1138
			free_leaf_info(li);
1139
			free_leaf(l);
1140
			return NULL;
O
Olof Johansson 已提交
1141 1142
		}

1143
		node_set_parent((struct rt_trie_node *)tn, tp);
1144

O
Olof Johansson 已提交
1145
		missbit = tkey_extract_bits(key, newpos, 1);
L
Lin Ming 已提交
1146 1147
		put_child(tn, missbit, (struct rt_trie_node *)l);
		put_child(tn, 1-missbit, n);
1148

1149
		if (tp) {
1150
			cindex = tkey_extract_bits(key, tp->pos, tp->bits);
L
Lin Ming 已提交
1151
			put_child(tp, cindex, (struct rt_trie_node *)tn);
O
Olof Johansson 已提交
1152
		} else {
1153
			rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1154 1155 1156
			tp = tn;
		}
	}
O
Olof Johansson 已提交
1157 1158

	if (tp && tp->pos + tp->bits > 32)
J
Joe Perches 已提交
1159 1160
		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 已提交
1161

1162
	/* Rebalance the trie */
R
Robert Olsson 已提交
1163

1164
	trie_rebalance(t, tp);
1165
done:
1166 1167 1168
	return fa_head;
}

1169 1170 1171
/*
 * Caller must hold RTNL.
 */
1172
int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
1173 1174 1175
{
	struct trie *t = (struct trie *) tb->tb_data;
	struct fib_alias *fa, *new_fa;
1176
	struct list_head *fa_head = NULL;
1177
	struct fib_info *fi;
1178 1179
	int plen = cfg->fc_dst_len;
	u8 tos = cfg->fc_tos;
1180 1181 1182 1183 1184 1185 1186
	u32 key, mask;
	int err;
	struct leaf *l;

	if (plen > 32)
		return -EINVAL;

1187
	key = ntohl(cfg->fc_dst);
1188

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

O
Olof Johansson 已提交
1191
	mask = ntohl(inet_make_mask(plen));
1192

1193
	if (key & ~mask)
1194 1195 1196 1197
		return -EINVAL;

	key = key & mask;

1198 1199 1200
	fi = fib_create_info(cfg);
	if (IS_ERR(fi)) {
		err = PTR_ERR(fi);
1201
		goto err;
1202
	}
1203 1204

	l = fib_find_node(t, key);
1205
	fa = NULL;
1206

1207
	if (l) {
1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222
		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.
	 */

1223 1224 1225
	if (fa && fa->fa_tos == tos &&
	    fa->fa_info->fib_priority == fi->fib_priority) {
		struct fib_alias *fa_first, *fa_match;
1226 1227

		err = -EEXIST;
1228
		if (cfg->fc_nlflags & NLM_F_EXCL)
1229 1230
			goto out;

1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250
		/* 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;
			}
		}

1251
		if (cfg->fc_nlflags & NLM_F_REPLACE) {
1252 1253 1254
			struct fib_info *fi_drop;
			u8 state;

1255 1256 1257 1258
			fa = fa_first;
			if (fa_match) {
				if (fa == fa_match)
					err = 0;
1259
				goto out;
1260
			}
R
Robert Olsson 已提交
1261
			err = -ENOBUFS;
1262
			new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
R
Robert Olsson 已提交
1263 1264
			if (new_fa == NULL)
				goto out;
1265 1266

			fi_drop = fa->fa_info;
R
Robert Olsson 已提交
1267 1268
			new_fa->fa_tos = fa->fa_tos;
			new_fa->fa_info = fi;
1269
			new_fa->fa_type = cfg->fc_type;
1270
			state = fa->fa_state;
1271
			new_fa->fa_state = state & ~FA_S_ACCESSED;
1272

R
Robert Olsson 已提交
1273 1274
			list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
			alias_free_mem_rcu(fa);
1275 1276 1277

			fib_release_info(fi_drop);
			if (state & FA_S_ACCESSED)
1278
				rt_cache_flush(cfg->fc_nlinfo.nl_net);
1279 1280
			rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
				tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1281

O
Olof Johansson 已提交
1282
			goto succeeded;
1283 1284 1285 1286 1287
		}
		/* Error if we find a perfect match which
		 * uses the same scope, type, and nexthop
		 * information.
		 */
1288 1289
		if (fa_match)
			goto out;
1290

1291
		if (!(cfg->fc_nlflags & NLM_F_APPEND))
1292
			fa = fa_first;
1293 1294
	}
	err = -ENOENT;
1295
	if (!(cfg->fc_nlflags & NLM_F_CREATE))
1296 1297 1298
		goto out;

	err = -ENOBUFS;
1299
	new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1300 1301 1302 1303 1304
	if (new_fa == NULL)
		goto out;

	new_fa->fa_info = fi;
	new_fa->fa_tos = tos;
1305
	new_fa->fa_type = cfg->fc_type;
1306 1307 1308 1309 1310
	new_fa->fa_state = 0;
	/*
	 * Insert new entry to the list.
	 */

1311
	if (!fa_head) {
1312 1313 1314
		fa_head = fib_insert_node(t, key, plen);
		if (unlikely(!fa_head)) {
			err = -ENOMEM;
1315
			goto out_free_new_fa;
1316
		}
1317
	}
1318

1319 1320 1321
	if (!plen)
		tb->tb_num_default++;

R
Robert Olsson 已提交
1322 1323
	list_add_tail_rcu(&new_fa->fa_list,
			  (fa ? &fa->fa_list : fa_head));
1324

1325
	rt_cache_flush(cfg->fc_nlinfo.nl_net);
1326
	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1327
		  &cfg->fc_nlinfo, 0);
1328 1329
succeeded:
	return 0;
1330 1331 1332

out_free_new_fa:
	kmem_cache_free(fn_alias_kmem, new_fa);
1333 1334
out:
	fib_release_info(fi);
O
Olof Johansson 已提交
1335
err:
1336 1337 1338
	return err;
}

R
Robert Olsson 已提交
1339
/* should be called with rcu_read_lock */
1340
static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
1341
		      t_key key,  const struct flowi4 *flp,
E
Eric Dumazet 已提交
1342
		      struct fib_result *res, int fib_flags)
1343 1344 1345
{
	struct leaf_info *li;
	struct hlist_head *hhead = &l->list;
1346

1347
	hlist_for_each_entry_rcu(li, hhead, hlist) {
1348
		struct fib_alias *fa;
1349

1350
		if (l->key != (key & li->mask_plen))
1351 1352
			continue;

1353 1354 1355
		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
			struct fib_info *fi = fa->fa_info;
			int nhsel, err;
1356

1357
			if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1358
				continue;
1359 1360
			if (fi->fib_dead)
				continue;
1361
			if (fa->fa_info->fib_scope < flp->flowi4_scope)
1362 1363 1364 1365
				continue;
			fib_alias_accessed(fa);
			err = fib_props[fa->fa_type].error;
			if (err) {
1366
#ifdef CONFIG_IP_FIB_TRIE_STATS
1367
				t->stats.semantic_match_passed++;
1368
#endif
1369
				return err;
1370 1371 1372 1373 1374 1375 1376 1377
			}
			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;
1378
				if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
1379 1380 1381 1382 1383
					continue;

#ifdef CONFIG_IP_FIB_TRIE_STATS
				t->stats.semantic_match_passed++;
#endif
1384
				res->prefixlen = li->plen;
1385 1386
				res->nh_sel = nhsel;
				res->type = fa->fa_type;
1387
				res->scope = fa->fa_info->fib_scope;
1388 1389 1390 1391
				res->fi = fi;
				res->table = tb;
				res->fa_head = &li->falh;
				if (!(fib_flags & FIB_LOOKUP_NOREF))
1392
					atomic_inc(&fi->fib_clntref);
1393 1394 1395 1396 1397 1398
				return 0;
			}
		}

#ifdef CONFIG_IP_FIB_TRIE_STATS
		t->stats.semantic_match_miss++;
1399 1400
#endif
	}
1401

1402
	return 1;
1403 1404
}

1405
int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
E
Eric Dumazet 已提交
1406
		     struct fib_result *res, int fib_flags)
1407 1408
{
	struct trie *t = (struct trie *) tb->tb_data;
1409
	int ret;
1410
	struct rt_trie_node *n;
1411
	struct tnode *pn;
1412
	unsigned int pos, bits;
1413
	t_key key = ntohl(flp->daddr);
1414
	unsigned int chopped_off;
1415
	t_key cindex = 0;
1416
	unsigned int current_prefix_length = KEYLENGTH;
O
Olof Johansson 已提交
1417
	struct tnode *cn;
1418
	t_key pref_mismatch;
O
Olof Johansson 已提交
1419

R
Robert Olsson 已提交
1420
	rcu_read_lock();
O
Olof Johansson 已提交
1421

R
Robert Olsson 已提交
1422
	n = rcu_dereference(t->trie);
1423
	if (!n)
1424 1425 1426 1427 1428 1429 1430 1431
		goto failed;

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

	/* Just a leaf? */
	if (IS_LEAF(n)) {
1432
		ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1433
		goto found;
1434
	}
1435

1436 1437
	pn = (struct tnode *) n;
	chopped_off = 0;
1438

O
Olof Johansson 已提交
1439
	while (pn) {
1440 1441 1442
		pos = pn->pos;
		bits = pn->bits;

1443
		if (!chopped_off)
S
Stephen Hemminger 已提交
1444 1445
			cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
						   pos, bits);
1446

1447
		n = tnode_get_child_rcu(pn, cindex);
1448 1449 1450 1451 1452 1453 1454 1455

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

O
Olof Johansson 已提交
1456
		if (IS_LEAF(n)) {
1457
			ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1458
			if (ret > 0)
O
Olof Johansson 已提交
1459
				goto backtrace;
1460
			goto found;
O
Olof Johansson 已提交
1461 1462 1463
		}

		cn = (struct tnode *)n;
1464

O
Olof Johansson 已提交
1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479
		/*
		 * 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].
		 */
1480

O
Olof Johansson 已提交
1481 1482 1483 1484 1485 1486 1487 1488 1489
		/* 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.
		 */
1490

1491 1492
		/* NOTA BENE: Checking only skipped bits
		   for the new node here */
1493

O
Olof Johansson 已提交
1494 1495
		if (current_prefix_length < pos+bits) {
			if (tkey_extract_bits(cn->key, current_prefix_length,
1496 1497
						cn->pos - current_prefix_length)
			    || !(cn->child[0]))
O
Olof Johansson 已提交
1498 1499
				goto backtrace;
		}
1500

O
Olof Johansson 已提交
1501 1502 1503 1504 1505 1506 1507 1508 1509
		/*
		 * 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.
		 */
1510

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

1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530
		/*
		 * 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 已提交
1531 1532
		 */

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

1535 1536 1537 1538
		/*
		 * In short: If skipped bits in this node do not match
		 * the search key, enter the "prefix matching"
		 * state.directly.
O
Olof Johansson 已提交
1539 1540
		 */
		if (pref_mismatch) {
1541 1542
			/* fls(x) = __fls(x) + 1 */
			int mp = KEYLENGTH - __fls(pref_mismatch) - 1;
O
Olof Johansson 已提交
1543

1544
			if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
O
Olof Johansson 已提交
1545 1546 1547 1548
				goto backtrace;

			if (current_prefix_length >= cn->pos)
				current_prefix_length = mp;
1549
		}
1550

O
Olof Johansson 已提交
1551 1552 1553 1554
		pn = (struct tnode *)n; /* Descend */
		chopped_off = 0;
		continue;

1555 1556 1557 1558
backtrace:
		chopped_off++;

		/* As zero don't change the child key (cindex) */
1559 1560
		while ((chopped_off <= pn->bits)
		       && !(cindex & (1<<(chopped_off-1))))
1561 1562 1563 1564
			chopped_off++;

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

1568
		/*
1569
		 * Either we do the actual chop off according or if we have
1570 1571 1572
		 * chopped off all bits in this tnode walk up to our parent.
		 */

O
Olof Johansson 已提交
1573
		if (chopped_off <= pn->bits) {
1574
			cindex &= ~(1 << (chopped_off-1));
O
Olof Johansson 已提交
1575
		} else {
1576
			struct tnode *parent = node_parent_rcu((struct rt_trie_node *) pn);
S
Stephen Hemminger 已提交
1577
			if (!parent)
1578
				goto failed;
O
Olof Johansson 已提交
1579

1580
			/* Get Child's index */
S
Stephen Hemminger 已提交
1581 1582
			cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
			pn = parent;
1583 1584 1585 1586 1587 1588
			chopped_off = 0;

#ifdef CONFIG_IP_FIB_TRIE_STATS
			t->stats.backtrack++;
#endif
			goto backtrace;
1589
		}
1590 1591
	}
failed:
1592
	ret = 1;
1593
found:
R
Robert Olsson 已提交
1594
	rcu_read_unlock();
1595 1596
	return ret;
}
1597
EXPORT_SYMBOL_GPL(fib_table_lookup);
1598

1599 1600 1601 1602
/*
 * Remove the leaf and return parent.
 */
static void trie_leaf_remove(struct trie *t, struct leaf *l)
1603
{
1604
	struct tnode *tp = node_parent((struct rt_trie_node *) l);
1605

1606
	pr_debug("entering trie_leaf_remove(%p)\n", l);
1607

1608
	if (tp) {
1609
		t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
L
Lin Ming 已提交
1610
		put_child(tp, cindex, NULL);
1611
		trie_rebalance(t, tp);
O
Olof Johansson 已提交
1612
	} else
1613
		RCU_INIT_POINTER(t->trie, NULL);
1614

1615
	free_leaf(l);
1616 1617
}

1618 1619 1620
/*
 * Caller must hold RTNL.
 */
1621
int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
1622 1623 1624
{
	struct trie *t = (struct trie *) tb->tb_data;
	u32 key, mask;
1625 1626
	int plen = cfg->fc_dst_len;
	u8 tos = cfg->fc_tos;
1627 1628 1629
	struct fib_alias *fa, *fa_to_delete;
	struct list_head *fa_head;
	struct leaf *l;
O
Olof Johansson 已提交
1630 1631
	struct leaf_info *li;

1632
	if (plen > 32)
1633 1634
		return -EINVAL;

1635
	key = ntohl(cfg->fc_dst);
O
Olof Johansson 已提交
1636
	mask = ntohl(inet_make_mask(plen));
1637

1638
	if (key & ~mask)
1639 1640 1641 1642 1643
		return -EINVAL;

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

1644
	if (!l)
1645 1646
		return -ESRCH;

1647 1648 1649 1650 1651 1652
	li = find_leaf_info(l, plen);

	if (!li)
		return -ESRCH;

	fa_head = &li->falh;
1653 1654 1655 1656 1657
	fa = fib_find_alias(fa_head, tos, 0);

	if (!fa)
		return -ESRCH;

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

	fa_to_delete = NULL;
1661 1662
	fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
	list_for_each_entry_continue(fa, fa_head, fa_list) {
1663 1664 1665 1666 1667
		struct fib_info *fi = fa->fa_info;

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

1668 1669
		if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
		    (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1670
		     fa->fa_info->fib_scope == cfg->fc_scope) &&
1671 1672
		    (!cfg->fc_prefsrc ||
		     fi->fib_prefsrc == cfg->fc_prefsrc) &&
1673 1674 1675
		    (!cfg->fc_protocol ||
		     fi->fib_protocol == cfg->fc_protocol) &&
		    fib_nh_match(cfg, fi) == 0) {
1676 1677 1678 1679 1680
			fa_to_delete = fa;
			break;
		}
	}

O
Olof Johansson 已提交
1681 1682
	if (!fa_to_delete)
		return -ESRCH;
1683

O
Olof Johansson 已提交
1684
	fa = fa_to_delete;
1685
	rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1686
		  &cfg->fc_nlinfo, 0);
O
Olof Johansson 已提交
1687

R
Robert Olsson 已提交
1688
	list_del_rcu(&fa->fa_list);
1689

1690 1691 1692
	if (!plen)
		tb->tb_num_default--;

O
Olof Johansson 已提交
1693
	if (list_empty(fa_head)) {
R
Robert Olsson 已提交
1694
		hlist_del_rcu(&li->hlist);
O
Olof Johansson 已提交
1695
		free_leaf_info(li);
R
Robert Olsson 已提交
1696
	}
1697

O
Olof Johansson 已提交
1698
	if (hlist_empty(&l->list))
1699
		trie_leaf_remove(t, l);
1700

O
Olof Johansson 已提交
1701
	if (fa->fa_state & FA_S_ACCESSED)
1702
		rt_cache_flush(cfg->fc_nlinfo.nl_net);
1703

R
Robert Olsson 已提交
1704 1705
	fib_release_info(fa->fa_info);
	alias_free_mem_rcu(fa);
O
Olof Johansson 已提交
1706
	return 0;
1707 1708
}

1709
static int trie_flush_list(struct list_head *head)
1710 1711 1712 1713 1714 1715 1716
{
	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 已提交
1717 1718 1719 1720
		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);
1721 1722 1723 1724 1725 1726
			found++;
		}
	}
	return found;
}

1727
static int trie_flush_leaf(struct leaf *l)
1728 1729 1730
{
	int found = 0;
	struct hlist_head *lih = &l->list;
1731
	struct hlist_node *tmp;
1732 1733
	struct leaf_info *li = NULL;

1734
	hlist_for_each_entry_safe(li, tmp, lih, hlist) {
1735
		found += trie_flush_list(&li->falh);
1736 1737

		if (list_empty(&li->falh)) {
R
Robert Olsson 已提交
1738
			hlist_del_rcu(&li->hlist);
1739 1740 1741 1742 1743 1744
			free_leaf_info(li);
		}
	}
	return found;
}

1745 1746 1747 1748
/*
 * Scan for the next right leaf starting at node p->child[idx]
 * Since we have back pointer, no recursion necessary.
 */
1749
static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1750
{
1751 1752
	do {
		t_key idx;
1753 1754

		if (c)
1755
			idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1756
		else
1757
			idx = 0;
R
Robert Olsson 已提交
1758

1759 1760
		while (idx < 1u << p->bits) {
			c = tnode_get_child_rcu(p, idx++);
R
Robert Olsson 已提交
1761
			if (!c)
O
Olof Johansson 已提交
1762 1763
				continue;

1764
			if (IS_LEAF(c)) {
E
Eric Dumazet 已提交
1765
				prefetch(rcu_dereference_rtnl(p->child[idx]));
1766
				return (struct leaf *) c;
1767
			}
1768 1769 1770 1771

			/* Rescan start scanning in new node */
			p = (struct tnode *) c;
			idx = 0;
1772
		}
1773 1774

		/* Node empty, walk back up to parent */
1775
		c = (struct rt_trie_node *) p;
E
Eric Dumazet 已提交
1776
	} while ((p = node_parent_rcu(c)) != NULL);
1777 1778 1779 1780 1781 1782

	return NULL; /* Root of trie */
}

static struct leaf *trie_firstleaf(struct trie *t)
{
E
Eric Dumazet 已提交
1783
	struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795

	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)
{
1796
	struct rt_trie_node *c = (struct rt_trie_node *) l;
1797
	struct tnode *p = node_parent_rcu(c);
1798 1799 1800 1801 1802

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

	return leaf_walk_rcu(p, c);
1803 1804
}

1805 1806 1807 1808
static struct leaf *trie_leafindex(struct trie *t, int index)
{
	struct leaf *l = trie_firstleaf(t);

S
Stephen Hemminger 已提交
1809
	while (l && index-- > 0)
1810
		l = trie_nextleaf(l);
S
Stephen Hemminger 已提交
1811

1812 1813 1814 1815
	return l;
}


1816 1817 1818
/*
 * Caller must hold RTNL.
 */
1819
int fib_table_flush(struct fib_table *tb)
1820 1821
{
	struct trie *t = (struct trie *) tb->tb_data;
1822
	struct leaf *l, *ll = NULL;
1823
	int found = 0;
1824

1825
	for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1826
		found += trie_flush_leaf(l);
1827 1828

		if (ll && hlist_empty(&ll->list))
1829
			trie_leaf_remove(t, ll);
1830 1831 1832 1833
		ll = l;
	}

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

S
Stephen Hemminger 已提交
1836
	pr_debug("trie_flush found=%d\n", found);
1837 1838 1839
	return found;
}

1840 1841 1842 1843 1844
void fib_free_table(struct fib_table *tb)
{
	kfree(tb);
}

1845 1846
static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
			   struct fib_table *tb,
1847 1848 1849 1850
			   struct sk_buff *skb, struct netlink_callback *cb)
{
	int i, s_i;
	struct fib_alias *fa;
A
Al Viro 已提交
1851
	__be32 xkey = htonl(key);
1852

1853
	s_i = cb->args[5];
1854 1855
	i = 0;

R
Robert Olsson 已提交
1856 1857 1858
	/* rcu_read_lock is hold by caller */

	list_for_each_entry_rcu(fa, fah, fa_list) {
1859 1860 1861 1862 1863
		if (i < s_i) {
			i++;
			continue;
		}

1864
		if (fib_dump_info(skb, NETLINK_CB(cb->skb).portid,
1865 1866 1867 1868
				  cb->nlh->nlmsg_seq,
				  RTM_NEWROUTE,
				  tb->tb_id,
				  fa->fa_type,
1869
				  xkey,
1870 1871
				  plen,
				  fa->fa_tos,
1872
				  fa->fa_info, NLM_F_MULTI) < 0) {
1873
			cb->args[5] = i;
1874
			return -1;
O
Olof Johansson 已提交
1875
		}
1876 1877
		i++;
	}
1878
	cb->args[5] = i;
1879 1880 1881
	return skb->len;
}

1882 1883
static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
			struct sk_buff *skb, struct netlink_callback *cb)
1884
{
1885 1886
	struct leaf_info *li;
	int i, s_i;
1887

1888
	s_i = cb->args[4];
1889
	i = 0;
1890

1891
	/* rcu_read_lock is hold by caller */
1892
	hlist_for_each_entry_rcu(li, &l->list, hlist) {
1893 1894
		if (i < s_i) {
			i++;
1895
			continue;
1896
		}
O
Olof Johansson 已提交
1897

1898
		if (i > s_i)
1899
			cb->args[5] = 0;
1900

1901
		if (list_empty(&li->falh))
1902 1903
			continue;

1904
		if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1905
			cb->args[4] = i;
1906 1907
			return -1;
		}
1908
		i++;
1909
	}
1910

1911
	cb->args[4] = i;
1912 1913 1914
	return skb->len;
}

1915 1916
int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
		   struct netlink_callback *cb)
1917
{
1918
	struct leaf *l;
1919
	struct trie *t = (struct trie *) tb->tb_data;
1920
	t_key key = cb->args[2];
1921
	int count = cb->args[3];
1922

R
Robert Olsson 已提交
1923
	rcu_read_lock();
1924 1925 1926
	/* Dump starting at last key.
	 * Note: 0.0.0.0/0 (ie default) is first key.
	 */
1927
	if (count == 0)
1928 1929
		l = trie_firstleaf(t);
	else {
1930 1931 1932
		/* Normally, continue from last key, but if that is missing
		 * fallback to using slow rescan
		 */
1933
		l = fib_find_node(t, key);
1934 1935
		if (!l)
			l = trie_leafindex(t, count);
1936
	}
1937

1938 1939
	while (l) {
		cb->args[2] = l->key;
1940
		if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1941
			cb->args[3] = count;
1942 1943
			rcu_read_unlock();
			return -1;
1944
		}
1945

1946
		++count;
1947
		l = trie_nextleaf(l);
1948 1949
		memset(&cb->args[4], 0,
		       sizeof(cb->args) - 4*sizeof(cb->args[0]));
1950
	}
1951
	cb->args[3] = count;
R
Robert Olsson 已提交
1952
	rcu_read_unlock();
1953

1954 1955 1956
	return skb->len;
}

1957
void __init fib_trie_init(void)
1958
{
1959 1960
	fn_alias_kmem = kmem_cache_create("ip_fib_alias",
					  sizeof(struct fib_alias),
1961 1962 1963 1964 1965 1966
					  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);
1967
}
1968

1969

1970
struct fib_table *fib_trie_table(u32 id)
1971 1972 1973 1974 1975 1976 1977 1978 1979 1980
{
	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;
1981
	tb->tb_default = -1;
1982
	tb->tb_num_default = 0;
1983 1984

	t = (struct trie *) tb->tb_data;
1985
	memset(t, 0, sizeof(*t));
1986 1987 1988 1989

	return tb;
}

1990 1991 1992
#ifdef CONFIG_PROC_FS
/* Depth first Trie walk iterator */
struct fib_trie_iter {
1993
	struct seq_net_private p;
1994
	struct fib_table *tb;
1995
	struct tnode *tnode;
E
Eric Dumazet 已提交
1996 1997
	unsigned int index;
	unsigned int depth;
1998
};
1999

2000
static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
2001
{
2002
	struct tnode *tn = iter->tnode;
E
Eric Dumazet 已提交
2003
	unsigned int cindex = iter->index;
2004
	struct tnode *p;
2005

2006 2007 2008 2009
	/* A single entry routing table */
	if (!tn)
		return NULL;

2010 2011 2012 2013
	pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
		 iter->tnode, iter->index, iter->depth);
rescan:
	while (cindex < (1<<tn->bits)) {
2014
		struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
2015

2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027
		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;
		}
2028

2029 2030
		++cindex;
	}
O
Olof Johansson 已提交
2031

2032
	/* Current node exhausted, pop back up */
2033
	p = node_parent_rcu((struct rt_trie_node *)tn);
2034 2035 2036 2037 2038
	if (p) {
		cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
		tn = p;
		--iter->depth;
		goto rescan;
2039
	}
2040 2041 2042

	/* got root? */
	return NULL;
2043 2044
}

2045
static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
2046
				       struct trie *t)
2047
{
2048
	struct rt_trie_node *n;
2049

S
Stephen Hemminger 已提交
2050
	if (!t)
2051 2052 2053
		return NULL;

	n = rcu_dereference(t->trie);
2054
	if (!n)
2055
		return NULL;
2056

2057 2058 2059 2060 2061 2062 2063 2064
	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 已提交
2065
	}
2066 2067

	return n;
2068
}
O
Olof Johansson 已提交
2069

2070 2071
static void trie_collect_stats(struct trie *t, struct trie_stat *s)
{
2072
	struct rt_trie_node *n;
2073
	struct fib_trie_iter iter;
O
Olof Johansson 已提交
2074

2075
	memset(s, 0, sizeof(*s));
O
Olof Johansson 已提交
2076

2077
	rcu_read_lock();
2078
	for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2079
		if (IS_LEAF(n)) {
2080 2081 2082
			struct leaf *l = (struct leaf *)n;
			struct leaf_info *li;

2083 2084 2085 2086
			s->leaves++;
			s->totdepth += iter.depth;
			if (iter.depth > s->maxdepth)
				s->maxdepth = iter.depth;
2087

2088
			hlist_for_each_entry_rcu(li, &l->list, hlist)
2089
				++s->prefixes;
2090 2091 2092 2093 2094
		} else {
			const struct tnode *tn = (const struct tnode *) n;
			int i;

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

2098 2099 2100
			for (i = 0; i < (1<<tn->bits); i++)
				if (!tn->child[i])
					s->nullpointers++;
2101 2102
		}
	}
R
Robert Olsson 已提交
2103
	rcu_read_unlock();
2104 2105
}

2106 2107 2108 2109
/*
 *	This outputs /proc/net/fib_triestats
 */
static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2110
{
E
Eric Dumazet 已提交
2111
	unsigned int i, max, pointers, bytes, avdepth;
2112

2113 2114 2115 2116
	if (stat->leaves)
		avdepth = stat->totdepth*100 / stat->leaves;
	else
		avdepth = 0;
O
Olof Johansson 已提交
2117

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

2122 2123
	seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
	bytes = sizeof(struct leaf) * stat->leaves;
2124 2125 2126 2127

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

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

R
Robert Olsson 已提交
2131 2132
	max = MAX_STAT_DEPTH;
	while (max > 0 && stat->nodesizes[max-1] == 0)
2133
		max--;
2134

2135
	pointers = 0;
2136
	for (i = 1; i < max; i++)
2137
		if (stat->nodesizes[i] != 0) {
2138
			seq_printf(seq, "  %u: %u",  i, stat->nodesizes[i]);
2139 2140 2141
			pointers += (1<<i) * stat->nodesizes[i];
		}
	seq_putc(seq, '\n');
2142
	seq_printf(seq, "\tPointers: %u\n", pointers);
R
Robert Olsson 已提交
2143

2144
	bytes += sizeof(struct rt_trie_node *) * pointers;
2145 2146
	seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
	seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
2147
}
R
Robert Olsson 已提交
2148

2149
#ifdef CONFIG_IP_FIB_TRIE_STATS
2150 2151 2152 2153
static void trie_show_usage(struct seq_file *seq,
			    const struct trie_use_stats *stats)
{
	seq_printf(seq, "\nCounters:\n---------\n");
2154 2155 2156 2157 2158 2159 2160 2161 2162
	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);
2163
}
2164 2165
#endif /*  CONFIG_IP_FIB_TRIE_STATS */

2166
static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2167
{
2168 2169 2170 2171 2172 2173
	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);
2174
}
2175

2176

2177 2178
static int fib_triestat_seq_show(struct seq_file *seq, void *v)
{
2179
	struct net *net = (struct net *)seq->private;
2180
	unsigned int h;
2181

2182
	seq_printf(seq,
2183 2184
		   "Basic info: size of leaf:"
		   " %Zd bytes, size of tnode: %Zd bytes.\n",
2185 2186
		   sizeof(struct leaf), sizeof(struct tnode));

2187 2188 2189 2190
	for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
		struct fib_table *tb;

2191
		hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2192 2193
			struct trie *t = (struct trie *) tb->tb_data;
			struct trie_stat stat;
2194

2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206
			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
		}
	}
2207

2208
	return 0;
2209 2210
}

2211
static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2212
{
2213
	return single_open_net(inode, file, fib_triestat_seq_show);
2214 2215
}

2216
static const struct file_operations fib_triestat_fops = {
2217 2218 2219 2220
	.owner	= THIS_MODULE,
	.open	= fib_triestat_seq_open,
	.read	= seq_read,
	.llseek	= seq_lseek,
2221
	.release = single_release_net,
2222 2223
};

2224
static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2225
{
2226 2227
	struct fib_trie_iter *iter = seq->private;
	struct net *net = seq_file_net(seq);
2228
	loff_t idx = 0;
2229
	unsigned int h;
2230

2231 2232 2233
	for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
		struct fib_table *tb;
2234

2235
		hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2236
			struct rt_trie_node *n;
2237 2238 2239 2240 2241 2242 2243 2244 2245

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

2248 2249 2250
	return NULL;
}

2251
static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2252
	__acquires(RCU)
2253
{
2254
	rcu_read_lock();
2255
	return fib_trie_get_idx(seq, *pos);
2256 2257
}

2258
static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2259
{
2260
	struct fib_trie_iter *iter = seq->private;
2261
	struct net *net = seq_file_net(seq);
2262 2263 2264
	struct fib_table *tb = iter->tb;
	struct hlist_node *tb_node;
	unsigned int h;
2265
	struct rt_trie_node *n;
2266

2267
	++*pos;
2268 2269 2270 2271
	/* next node in same table */
	n = fib_trie_get_next(iter);
	if (n)
		return n;
2272

2273 2274
	/* walk rest of this hash chain */
	h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
E
Eric Dumazet 已提交
2275
	while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2276 2277 2278 2279 2280
		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;
	}
2281

2282 2283 2284
	/* new hash chain */
	while (++h < FIB_TABLE_HASHSZ) {
		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2285
		hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2286 2287 2288 2289 2290
			n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
			if (n)
				goto found;
		}
	}
2291
	return NULL;
2292 2293 2294 2295

found:
	iter->tb = tb;
	return n;
2296
}
2297

2298
static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2299
	__releases(RCU)
2300
{
2301 2302
	rcu_read_unlock();
}
O
Olof Johansson 已提交
2303

2304 2305
static void seq_indent(struct seq_file *seq, int n)
{
E
Eric Dumazet 已提交
2306 2307
	while (n-- > 0)
		seq_puts(seq, "   ");
2308
}
2309

2310
static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2311
{
S
Stephen Hemminger 已提交
2312
	switch (s) {
2313 2314 2315 2316 2317 2318
	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:
2319
		snprintf(buf, len, "scope=%d", s);
2320 2321 2322
		return buf;
	}
}
2323

2324
static const char *const rtn_type_names[__RTN_MAX] = {
2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337
	[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",
};
2338

E
Eric Dumazet 已提交
2339
static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2340 2341 2342
{
	if (t < __RTN_MAX && rtn_type_names[t])
		return rtn_type_names[t];
2343
	snprintf(buf, len, "type %u", t);
2344
	return buf;
2345 2346
}

2347 2348
/* Pretty print the trie */
static int fib_trie_seq_show(struct seq_file *seq, void *v)
2349
{
2350
	const struct fib_trie_iter *iter = seq->private;
2351
	struct rt_trie_node *n = v;
2352

2353 2354
	if (!node_parent_rcu(n))
		fib_table_print(seq, iter->tb);
2355

2356 2357
	if (IS_TNODE(n)) {
		struct tnode *tn = (struct tnode *) n;
S
Stephen Hemminger 已提交
2358
		__be32 prf = htonl(mask_pfx(tn->key, tn->pos));
O
Olof Johansson 已提交
2359

2360
		seq_indent(seq, iter->depth-1);
2361 2362
		seq_printf(seq, "  +-- %pI4/%d %d %d %d\n",
			   &prf, tn->pos, tn->bits, tn->full_children,
2363
			   tn->empty_children);
2364

2365 2366
	} else {
		struct leaf *l = (struct leaf *) n;
2367
		struct leaf_info *li;
A
Al Viro 已提交
2368
		__be32 val = htonl(l->key);
2369 2370

		seq_indent(seq, iter->depth);
2371
		seq_printf(seq, "  |-- %pI4\n", &val);
2372

2373
		hlist_for_each_entry_rcu(li, &l->list, hlist) {
2374 2375 2376 2377 2378 2379 2380 2381
			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),
2382
						     fa->fa_info->fib_scope),
2383 2384 2385
					   rtn_type(buf2, sizeof(buf2),
						    fa->fa_type));
				if (fa->fa_tos)
2386
					seq_printf(seq, " tos=%d", fa->fa_tos);
2387
				seq_putc(seq, '\n');
2388 2389
			}
		}
2390
	}
2391

2392 2393 2394
	return 0;
}

2395
static const struct seq_operations fib_trie_seq_ops = {
2396 2397 2398 2399
	.start  = fib_trie_seq_start,
	.next   = fib_trie_seq_next,
	.stop   = fib_trie_seq_stop,
	.show   = fib_trie_seq_show,
2400 2401
};

2402
static int fib_trie_seq_open(struct inode *inode, struct file *file)
2403
{
2404 2405
	return seq_open_net(inode, file, &fib_trie_seq_ops,
			    sizeof(struct fib_trie_iter));
2406 2407
}

2408
static const struct file_operations fib_trie_fops = {
2409 2410 2411 2412
	.owner  = THIS_MODULE,
	.open   = fib_trie_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2413
	.release = seq_release_net,
2414 2415
};

2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 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
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();
2456
	tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493
	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 已提交
2494
static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2495
{
E
Eric Dumazet 已提交
2496
	unsigned int flags = 0;
2497

E
Eric Dumazet 已提交
2498 2499
	if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
		flags = RTF_REJECT;
2500 2501
	if (fi && fi->fib_nh->nh_gw)
		flags |= RTF_GATEWAY;
A
Al Viro 已提交
2502
	if (mask == htonl(0xFFFFFFFF))
2503 2504 2505
		flags |= RTF_HOST;
	flags |= RTF_UP;
	return flags;
2506 2507
}

2508 2509 2510
/*
 *	This outputs /proc/net/route.
 *	The format of the file is not supposed to be changed
E
Eric Dumazet 已提交
2511
 *	and needs to be same as fib_hash output to avoid breaking
2512 2513 2514
 *	legacy utilities
 */
static int fib_route_seq_show(struct seq_file *seq, void *v)
2515
{
2516
	struct leaf *l = v;
2517
	struct leaf_info *li;
2518

2519 2520 2521 2522 2523 2524
	if (v == SEQ_START_TOKEN) {
		seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
			   "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
			   "\tWindow\tIRTT");
		return 0;
	}
2525

2526
	hlist_for_each_entry_rcu(li, &l->list, hlist) {
2527
		struct fib_alias *fa;
A
Al Viro 已提交
2528
		__be32 mask, prefix;
O
Olof Johansson 已提交
2529

2530 2531
		mask = inet_make_mask(li->plen);
		prefix = htonl(l->key);
2532

2533
		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2534
			const struct fib_info *fi = fa->fa_info;
E
Eric Dumazet 已提交
2535
			unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2536
			int len;
2537

2538 2539 2540
			if (fa->fa_type == RTN_BROADCAST
			    || fa->fa_type == RTN_MULTICAST)
				continue;
2541

2542
			if (fi)
2543 2544 2545
				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",
2546 2547 2548 2549 2550
					 fi->fib_dev ? fi->fib_dev->name : "*",
					 prefix,
					 fi->fib_nh->nh_gw, flags, 0, 0,
					 fi->fib_priority,
					 mask,
2551 2552
					 (fi->fib_advmss ?
					  fi->fib_advmss + 40 : 0),
2553
					 fi->fib_window,
2554
					 fi->fib_rtt >> 3, &len);
2555
			else
2556 2557 2558
				seq_printf(seq,
					 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
					 "%d\t%08X\t%d\t%u\t%u%n",
2559
					 prefix, 0, flags, 0, 0, 0,
2560
					 mask, 0, 0, 0, &len);
2561

2562
			seq_printf(seq, "%*s\n", 127 - len, "");
2563
		}
2564 2565 2566 2567 2568
	}

	return 0;
}

2569
static const struct seq_operations fib_route_seq_ops = {
2570 2571 2572
	.start  = fib_route_seq_start,
	.next   = fib_route_seq_next,
	.stop   = fib_route_seq_stop,
2573
	.show   = fib_route_seq_show,
2574 2575
};

2576
static int fib_route_seq_open(struct inode *inode, struct file *file)
2577
{
2578
	return seq_open_net(inode, file, &fib_route_seq_ops,
2579
			    sizeof(struct fib_route_iter));
2580 2581
}

2582
static const struct file_operations fib_route_fops = {
2583 2584 2585 2586
	.owner  = THIS_MODULE,
	.open   = fib_route_seq_open,
	.read   = seq_read,
	.llseek = seq_lseek,
2587
	.release = seq_release_net,
2588 2589
};

2590
int __net_init fib_proc_init(struct net *net)
2591
{
2592
	if (!proc_create("fib_trie", S_IRUGO, net->proc_net, &fib_trie_fops))
2593 2594
		goto out1;

2595 2596
	if (!proc_create("fib_triestat", S_IRUGO, net->proc_net,
			 &fib_triestat_fops))
2597 2598
		goto out2;

2599
	if (!proc_create("route", S_IRUGO, net->proc_net, &fib_route_fops))
2600 2601
		goto out3;

2602
	return 0;
2603 2604

out3:
2605
	remove_proc_entry("fib_triestat", net->proc_net);
2606
out2:
2607
	remove_proc_entry("fib_trie", net->proc_net);
2608 2609
out1:
	return -ENOMEM;
2610 2611
}

2612
void __net_exit fib_proc_exit(struct net *net)
2613
{
2614 2615 2616
	remove_proc_entry("fib_trie", net->proc_net);
	remove_proc_entry("fib_triestat", net->proc_net);
	remove_proc_entry("route", net->proc_net);
2617 2618 2619
}

#endif /* CONFIG_PROC_FS */