1/*
   2 *   This program is free software; you can redistribute it and/or
   3 *   modify it under the terms of the GNU General Public License
   4 *   as published by the Free Software Foundation; either version
   5 *   2 of the License, or (at your option) any later version.
   6 *
   7 *   Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
   8 *     & Swedish University of Agricultural Sciences.
   9 *
  10 *   Jens Laas <jens.laas@data.slu.se> Swedish University of
  11 *     Agricultural Sciences.
  12 *
  13 *   Hans Liss <hans.liss@its.uu.se>  Uppsala Universitet
  14 *
  15 * This work is based on the LPC-trie which is originally described in:
  16 *
  17 * An experimental study of compression methods for dynamic tries
  18 * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
  19 * http://www.csc.kth.se/~snilsson/software/dyntrie2/
  20 *
  21 *
  22 * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
  23 * IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999
  24 *
  25 *
  26 * Code from fib_hash has been reused which includes the following header:
  27 *
  28 *
  29 * INET		An implementation of the TCP/IP protocol suite for the LINUX
  30 *		operating system.  INET is implemented using the  BSD Socket
  31 *		interface as the means of communication with the user level.
  32 *
  33 *		IPv4 FIB: lookup engine and maintenance routines.
  34 *
  35 *
  36 * Authors:	Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
  37 *
  38 *		This program is free software; you can redistribute it and/or
  39 *		modify it under the terms of the GNU General Public License
  40 *		as published by the Free Software Foundation; either version
  41 *		2 of the License, or (at your option) any later version.
  42 *
  43 * Substantial contributions to this work comes from:
  44 *
  45 *		David S. Miller, <davem@davemloft.net>
  46 *		Stephen Hemminger <shemminger@osdl.org>
  47 *		Paul E. McKenney <paulmck@us.ibm.com>
  48 *		Patrick McHardy <kaber@trash.net>
  49 */
  50
  51#define VERSION "0.409"
  52
  53#include <asm/uaccess.h>
  54#include <linux/bitops.h>
  55#include <linux/types.h>
  56#include <linux/kernel.h>
  57#include <linux/mm.h>
  58#include <linux/string.h>
  59#include <linux/socket.h>
  60#include <linux/sockios.h>
  61#include <linux/errno.h>
  62#include <linux/in.h>
  63#include <linux/inet.h>
  64#include <linux/inetdevice.h>
  65#include <linux/netdevice.h>
  66#include <linux/if_arp.h>
  67#include <linux/proc_fs.h>
  68#include <linux/rcupdate.h>
 
  69#include <linux/skbuff.h>
  70#include <linux/netlink.h>
  71#include <linux/init.h>
  72#include <linux/list.h>
  73#include <linux/slab.h>
  74#include <linux/export.h>
 
 
  75#include <net/net_namespace.h>
 
  76#include <net/ip.h>
  77#include <net/protocol.h>
  78#include <net/route.h>
  79#include <net/tcp.h>
  80#include <net/sock.h>
  81#include <net/ip_fib.h>
 
 
  82#include "fib_lookup.h"
  83
  84#define MAX_STAT_DEPTH 32
  85
  86#define KEYLENGTH (8*sizeof(t_key))
  87
  88typedef unsigned int t_key;
 
 
 
 
 
 
 
 
 
 
 
  89
  90#define T_TNODE 0
  91#define T_LEAF  1
  92#define NODE_TYPE_MASK	0x1UL
  93#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
 
 
 
 
 
 
 
 
 
 
 
 
  94
  95#define IS_TNODE(n) (!(n->parent & T_LEAF))
  96#define IS_LEAF(n) (n->parent & T_LEAF)
  97
  98struct rt_trie_node {
  99	unsigned long parent;
 100	t_key key;
 101};
 102
 103struct leaf {
 104	unsigned long parent;
 105	t_key key;
 106	struct hlist_head list;
 107	struct rcu_head rcu;
 108};
 109
 110struct leaf_info {
 111	struct hlist_node hlist;
 112	int plen;
 113	u32 mask_plen; /* ntohl(inet_make_mask(plen)) */
 114	struct list_head falh;
 115	struct rcu_head rcu;
 116};
 117
 118struct tnode {
 119	unsigned long parent;
 120	t_key key;
 121	unsigned char pos;		/* 2log(KEYLENGTH) bits needed */
 122	unsigned char bits;		/* 2log(KEYLENGTH) bits needed */
 123	unsigned int full_children;	/* KEYLENGTH bits needed */
 124	unsigned int empty_children;	/* KEYLENGTH bits needed */
 125	union {
 126		struct rcu_head rcu;
 127		struct tnode *tnode_free;
 
 
 128	};
 129	struct rt_trie_node __rcu *child[0];
 130};
 131
 
 
 
 
 
 
 
 
 
 
 
 
 132#ifdef CONFIG_IP_FIB_TRIE_STATS
 133struct trie_use_stats {
 134	unsigned int gets;
 135	unsigned int backtrack;
 136	unsigned int semantic_match_passed;
 137	unsigned int semantic_match_miss;
 138	unsigned int null_node_hit;
 139	unsigned int resize_node_skipped;
 140};
 141#endif
 142
 143struct trie_stat {
 144	unsigned int totdepth;
 145	unsigned int maxdepth;
 146	unsigned int tnodes;
 147	unsigned int leaves;
 148	unsigned int nullpointers;
 149	unsigned int prefixes;
 150	unsigned int nodesizes[MAX_STAT_DEPTH];
 151};
 152
 153struct trie {
 154	struct rt_trie_node __rcu *trie;
 155#ifdef CONFIG_IP_FIB_TRIE_STATS
 156	struct trie_use_stats stats;
 157#endif
 158};
 159
 160static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
 161				  int wasfull);
 162static struct rt_trie_node *resize(struct trie *t, struct tnode *tn);
 163static struct tnode *inflate(struct trie *t, struct tnode *tn);
 164static struct tnode *halve(struct trie *t, struct tnode *tn);
 165/* tnodes to free after resize(); protected by RTNL */
 166static struct tnode *tnode_free_head;
 167static size_t tnode_free_size;
 168
 169/*
 170 * synchronize_rcu after call_rcu for that many pages; it should be especially
 171 * useful before resizing the root node with PREEMPT_NONE configs; the value was
 172 * obtained experimentally, aiming to avoid visible slowdown.
 173 */
 174static const int sync_pages = 128;
 
 
 175
 176static struct kmem_cache *fn_alias_kmem __read_mostly;
 177static struct kmem_cache *trie_leaf_kmem __read_mostly;
 178
 179/*
 180 * caller must hold RTNL
 181 */
 182static inline struct tnode *node_parent(const struct rt_trie_node *node)
 183{
 184	unsigned long parent;
 185
 186	parent = rcu_dereference_index_check(node->parent, lockdep_rtnl_is_held());
 187
 188	return (struct tnode *)(parent & ~NODE_TYPE_MASK);
 189}
 190
 191/*
 192 * caller must hold RCU read lock or RTNL
 193 */
 194static inline struct tnode *node_parent_rcu(const struct rt_trie_node *node)
 195{
 196	unsigned long parent;
 197
 198	parent = rcu_dereference_index_check(node->parent, rcu_read_lock_held() ||
 199							   lockdep_rtnl_is_held());
 200
 201	return (struct tnode *)(parent & ~NODE_TYPE_MASK);
 202}
 
 203
 204/* Same as rcu_assign_pointer
 205 * but that macro() assumes that value is a pointer.
 206 */
 207static inline void node_set_parent(struct rt_trie_node *node, struct tnode *ptr)
 208{
 209	smp_wmb();
 210	node->parent = (unsigned long)ptr | NODE_TYPE(node);
 211}
 212
 213/*
 214 * caller must hold RTNL
 215 */
 216static inline struct rt_trie_node *tnode_get_child(const struct tnode *tn, unsigned int i)
 217{
 218	BUG_ON(i >= 1U << tn->bits);
 219
 220	return rtnl_dereference(tn->child[i]);
 221}
 222
 223/*
 224 * caller must hold RCU read lock or RTNL
 225 */
 226static inline struct rt_trie_node *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
 227{
 228	BUG_ON(i >= 1U << tn->bits);
 229
 230	return rcu_dereference_rtnl(tn->child[i]);
 231}
 232
 233static inline int tnode_child_length(const struct tnode *tn)
 234{
 235	return 1 << tn->bits;
 236}
 237
 238static inline t_key mask_pfx(t_key k, unsigned int l)
 239{
 240	return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
 241}
 242
 243static inline t_key tkey_extract_bits(t_key a, unsigned int offset, unsigned int bits)
 244{
 245	if (offset < KEYLENGTH)
 246		return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
 247	else
 248		return 0;
 249}
 250
 251static inline int tkey_equals(t_key a, t_key b)
 252{
 253	return a == b;
 254}
 255
 256static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
 257{
 258	if (bits == 0 || offset >= KEYLENGTH)
 259		return 1;
 260	bits = bits > KEYLENGTH ? KEYLENGTH : bits;
 261	return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
 262}
 263
 264static inline int tkey_mismatch(t_key a, int offset, t_key b)
 265{
 266	t_key diff = a ^ b;
 267	int i = offset;
 268
 269	if (!diff)
 270		return 0;
 271	while ((diff << i) >> (KEYLENGTH-1) == 0)
 272		i++;
 273	return i;
 274}
 275
 276/*
 277  To understand this stuff, an understanding of keys and all their bits is
 278  necessary. Every node in the trie has a key associated with it, but not
 279  all of the bits in that key are significant.
 280
 281  Consider a node 'n' and its parent 'tp'.
 282
 283  If n is a leaf, every bit in its key is significant. Its presence is
 284  necessitated by path compression, since during a tree traversal (when
 285  searching for a leaf - unless we are doing an insertion) we will completely
 286  ignore all skipped bits we encounter. Thus we need to verify, at the end of
 287  a potentially successful search, that we have indeed been walking the
 288  correct key path.
 289
 290  Note that we can never "miss" the correct key in the tree if present by
 291  following the wrong path. Path compression ensures that segments of the key
 292  that are the same for all keys with a given prefix are skipped, but the
 293  skipped part *is* identical for each node in the subtrie below the skipped
 294  bit! trie_insert() in this implementation takes care of that - note the
 295  call to tkey_sub_equals() in trie_insert().
 296
 297  if n is an internal node - a 'tnode' here, the various parts of its key
 298  have many different meanings.
 299
 300  Example:
 301  _________________________________________________________________
 302  | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
 303  -----------------------------------------------------------------
 304    0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 305
 306  _________________________________________________________________
 307  | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
 308  -----------------------------------------------------------------
 309   16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31
 310
 311  tp->pos = 7
 312  tp->bits = 3
 313  n->pos = 15
 314  n->bits = 4
 315
 316  First, let's just ignore the bits that come before the parent tp, that is
 317  the bits from 0 to (tp->pos-1). They are *known* but at this point we do
 318  not use them for anything.
 319
 320  The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
 321  index into the parent's child array. That is, they will be used to find
 322  'n' among tp's children.
 323
 324  The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
 325  for the node n.
 326
 327  All the bits we have seen so far are significant to the node n. The rest
 328  of the bits are really not needed or indeed known in n->key.
 329
 330  The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
 331  n's child array, and will of course be different for each child.
 332
 333
 334  The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
 335  at this point.
 336
 337*/
 338
 339static inline void check_tnode(const struct tnode *tn)
 340{
 341	WARN_ON(tn && tn->pos+tn->bits > 32);
 342}
 343
 344static const int halve_threshold = 25;
 345static const int inflate_threshold = 50;
 346static const int halve_threshold_root = 15;
 347static const int inflate_threshold_root = 30;
 348
 349static void __alias_free_mem(struct rcu_head *head)
 350{
 351	struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
 352	kmem_cache_free(fn_alias_kmem, fa);
 353}
 354
 355static inline void alias_free_mem_rcu(struct fib_alias *fa)
 356{
 357	call_rcu(&fa->rcu, __alias_free_mem);
 358}
 359
 360static void __leaf_free_rcu(struct rcu_head *head)
 361{
 362	struct leaf *l = container_of(head, struct leaf, rcu);
 363	kmem_cache_free(trie_leaf_kmem, l);
 364}
 365
 366static inline void free_leaf(struct leaf *l)
 367{
 368	call_rcu(&l->rcu, __leaf_free_rcu);
 369}
 370
 371static inline void free_leaf_info(struct leaf_info *leaf)
 372{
 373	kfree_rcu(leaf, rcu);
 
 374}
 375
 376static struct tnode *tnode_alloc(size_t size)
 
 
 377{
 
 
 
 
 
 
 
 
 
 378	if (size <= PAGE_SIZE)
 379		return kzalloc(size, GFP_KERNEL);
 380	else
 381		return vzalloc(size);
 382}
 383
 384static void __tnode_free_rcu(struct rcu_head *head)
 385{
 386	struct tnode *tn = container_of(head, struct tnode, rcu);
 387	size_t size = sizeof(struct tnode) +
 388		      (sizeof(struct rt_trie_node *) << tn->bits);
 389
 390	if (size <= PAGE_SIZE)
 391		kfree(tn);
 392	else
 393		vfree(tn);
 394}
 395
 396static inline void tnode_free(struct tnode *tn)
 397{
 398	if (IS_LEAF(tn))
 399		free_leaf((struct leaf *) tn);
 400	else
 401		call_rcu(&tn->rcu, __tnode_free_rcu);
 402}
 403
 404static void tnode_free_safe(struct tnode *tn)
 405{
 406	BUG_ON(IS_LEAF(tn));
 407	tn->tnode_free = tnode_free_head;
 408	tnode_free_head = tn;
 409	tnode_free_size += sizeof(struct tnode) +
 410			   (sizeof(struct rt_trie_node *) << tn->bits);
 411}
 412
 413static void tnode_free_flush(void)
 414{
 415	struct tnode *tn;
 
 416
 417	while ((tn = tnode_free_head)) {
 418		tnode_free_head = tn->tnode_free;
 419		tn->tnode_free = NULL;
 420		tnode_free(tn);
 421	}
 422
 423	if (tnode_free_size >= PAGE_SIZE * sync_pages) {
 424		tnode_free_size = 0;
 425		synchronize_rcu();
 426	}
 427}
 
 
 
 
 
 428
 429static struct leaf *leaf_new(void)
 430{
 431	struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
 432	if (l) {
 433		l->parent = T_LEAF;
 434		INIT_HLIST_HEAD(&l->list);
 435	}
 436	return l;
 437}
 438
 439static struct leaf_info *leaf_info_new(int plen)
 440{
 441	struct leaf_info *li = kmalloc(sizeof(struct leaf_info),  GFP_KERNEL);
 442	if (li) {
 443		li->plen = plen;
 444		li->mask_plen = ntohl(inet_make_mask(plen));
 445		INIT_LIST_HEAD(&li->falh);
 446	}
 447	return li;
 448}
 449
 450static struct tnode *tnode_new(t_key key, int pos, int bits)
 451{
 452	size_t sz = sizeof(struct tnode) + (sizeof(struct rt_trie_node *) << bits);
 453	struct tnode *tn = tnode_alloc(sz);
 454
 455	if (tn) {
 456		tn->parent = T_TNODE;
 457		tn->pos = pos;
 458		tn->bits = bits;
 459		tn->key = key;
 460		tn->full_children = 0;
 461		tn->empty_children = 1<<bits;
 462	}
 463
 464	pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode),
 465		 sizeof(struct rt_trie_node *) << bits);
 466	return tn;
 467}
 468
 469/*
 470 * Check whether a tnode 'n' is "full", i.e. it is an internal node
 471 * and no bits are skipped. See discussion in dyntree paper p. 6
 472 */
 473
 474static inline int tnode_full(const struct tnode *tn, const struct rt_trie_node *n)
 475{
 476	if (n == NULL || IS_LEAF(n))
 477		return 0;
 
 478
 479	return ((struct tnode *) n)->pos == tn->pos + tn->bits;
 480}
 481
 482static inline void put_child(struct tnode *tn, int i,
 483			     struct rt_trie_node *n)
 
 
 484{
 485	tnode_put_child_reorg(tn, i, n, -1);
 486}
 487
 488 /*
 489  * Add a child at position i overwriting the old value.
 490  * Update the value of full_children and empty_children.
 491  */
 492
 493static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
 494				  int wasfull)
 495{
 496	struct rt_trie_node *chi = rtnl_dereference(tn->child[i]);
 497	int isfull;
 498
 499	BUG_ON(i >= 1<<tn->bits);
 500
 501	/* update emptyChildren */
 502	if (n == NULL && chi != NULL)
 503		tn->empty_children++;
 504	else if (n != NULL && chi == NULL)
 505		tn->empty_children--;
 506
 507	/* update fullChildren */
 508	if (wasfull == -1)
 509		wasfull = tnode_full(tn, chi);
 510
 511	isfull = tnode_full(tn, n);
 
 512	if (wasfull && !isfull)
 513		tn->full_children--;
 514	else if (!wasfull && isfull)
 515		tn->full_children++;
 516
 517	if (n)
 518		node_set_parent(n, tn);
 519
 520	rcu_assign_pointer(tn->child[i], n);
 521}
 522
 523#define MAX_WORK 10
 524static struct rt_trie_node *resize(struct trie *t, struct tnode *tn)
 525{
 526	int i;
 527	struct tnode *old_tn;
 528	int inflate_threshold_use;
 529	int halve_threshold_use;
 530	int max_work;
 531
 532	if (!tn)
 533		return NULL;
 
 534
 535	pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
 536		 tn, inflate_threshold, halve_threshold);
 537
 538	/* No children */
 539	if (tn->empty_children == tnode_child_length(tn)) {
 540		tnode_free_safe(tn);
 541		return NULL;
 
 
 
 
 542	}
 543	/* One child */
 544	if (tn->empty_children == tnode_child_length(tn) - 1)
 545		goto one_child;
 546	/*
 547	 * Double as long as the resulting node has a number of
 548	 * nonempty nodes that are above the threshold.
 549	 */
 550
 551	/*
 552	 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
 553	 * the Helsinki University of Technology and Matti Tikkanen of Nokia
 554	 * Telecommunications, page 6:
 555	 * "A node is doubled if the ratio of non-empty children to all
 556	 * children in the *doubled* node is at least 'high'."
 557	 *
 558	 * 'high' in this instance is the variable 'inflate_threshold'. It
 559	 * is expressed as a percentage, so we multiply it with
 560	 * tnode_child_length() and instead of multiplying by 2 (since the
 561	 * child array will be doubled by inflate()) and multiplying
 562	 * the left-hand side by 100 (to handle the percentage thing) we
 563	 * multiply the left-hand side by 50.
 564	 *
 565	 * The left-hand side may look a bit weird: tnode_child_length(tn)
 566	 * - tn->empty_children is of course the number of non-null children
 567	 * in the current node. tn->full_children is the number of "full"
 568	 * children, that is non-null tnodes with a skip value of 0.
 569	 * All of those will be doubled in the resulting inflated tnode, so
 570	 * we just count them one extra time here.
 571	 *
 572	 * A clearer way to write this would be:
 573	 *
 574	 * to_be_doubled = tn->full_children;
 575	 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
 576	 *     tn->full_children;
 577	 *
 578	 * new_child_length = tnode_child_length(tn) * 2;
 579	 *
 580	 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
 581	 *      new_child_length;
 582	 * if (new_fill_factor >= inflate_threshold)
 583	 *
 584	 * ...and so on, tho it would mess up the while () loop.
 585	 *
 586	 * anyway,
 587	 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
 588	 *      inflate_threshold
 589	 *
 590	 * avoid a division:
 591	 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
 592	 *      inflate_threshold * new_child_length
 593	 *
 594	 * expand not_to_be_doubled and to_be_doubled, and shorten:
 595	 * 100 * (tnode_child_length(tn) - tn->empty_children +
 596	 *    tn->full_children) >= inflate_threshold * new_child_length
 597	 *
 598	 * expand new_child_length:
 599	 * 100 * (tnode_child_length(tn) - tn->empty_children +
 600	 *    tn->full_children) >=
 601	 *      inflate_threshold * tnode_child_length(tn) * 2
 602	 *
 603	 * shorten again:
 604	 * 50 * (tn->full_children + tnode_child_length(tn) -
 605	 *    tn->empty_children) >= inflate_threshold *
 606	 *    tnode_child_length(tn)
 607	 *
 608	 */
 609
 610	check_tnode(tn);
 
 
 
 
 
 
 
 611
 612	/* Keep root node larger  */
 
 
 
 613
 614	if (!node_parent((struct rt_trie_node *)tn)) {
 615		inflate_threshold_use = inflate_threshold_root;
 616		halve_threshold_use = halve_threshold_root;
 617	} else {
 618		inflate_threshold_use = inflate_threshold;
 619		halve_threshold_use = halve_threshold;
 620	}
 621
 622	max_work = MAX_WORK;
 623	while ((tn->full_children > 0 &&  max_work-- &&
 624		50 * (tn->full_children + tnode_child_length(tn)
 625		      - tn->empty_children)
 626		>= inflate_threshold_use * tnode_child_length(tn))) {
 627
 628		old_tn = tn;
 629		tn = inflate(t, tn);
 
 
 630
 631		if (IS_ERR(tn)) {
 632			tn = old_tn;
 633#ifdef CONFIG_IP_FIB_TRIE_STATS
 634			t->stats.resize_node_skipped++;
 635#endif
 636			break;
 637		}
 638	}
 639
 640	check_tnode(tn);
 641
 642	/* Return if at least one inflate is run */
 643	if (max_work != MAX_WORK)
 644		return (struct rt_trie_node *) tn;
 645
 646	/*
 647	 * Halve as long as the number of empty children in this
 648	 * node is above threshold.
 649	 */
 650
 651	max_work = MAX_WORK;
 652	while (tn->bits > 1 &&  max_work-- &&
 653	       100 * (tnode_child_length(tn) - tn->empty_children) <
 654	       halve_threshold_use * tnode_child_length(tn)) {
 655
 656		old_tn = tn;
 657		tn = halve(t, tn);
 658		if (IS_ERR(tn)) {
 659			tn = old_tn;
 660#ifdef CONFIG_IP_FIB_TRIE_STATS
 661			t->stats.resize_node_skipped++;
 662#endif
 663			break;
 664		}
 665	}
 
 666
 
 
 
 
 
 
 667
 668	/* Only one child remains */
 669	if (tn->empty_children == tnode_child_length(tn) - 1) {
 670one_child:
 671		for (i = 0; i < tnode_child_length(tn); i++) {
 672			struct rt_trie_node *n;
 673
 674			n = rtnl_dereference(tn->child[i]);
 675			if (!n)
 676				continue;
 677
 678			/* compress one level */
 
 679
 680			node_set_parent(n, NULL);
 681			tnode_free_safe(tn);
 682			return n;
 683		}
 684	}
 685	return (struct rt_trie_node *) tn;
 686}
 687
 688
 689static void tnode_clean_free(struct tnode *tn)
 690{
 691	int i;
 692	struct tnode *tofree;
 693
 694	for (i = 0; i < tnode_child_length(tn); i++) {
 695		tofree = (struct tnode *)rtnl_dereference(tn->child[i]);
 696		if (tofree)
 697			tnode_free(tofree);
 698	}
 699	tnode_free(tn);
 
 700}
 701
 702static struct tnode *inflate(struct trie *t, struct tnode *tn)
 
 703{
 704	struct tnode *oldtnode = tn;
 705	int olen = tnode_child_length(tn);
 706	int i;
 707
 708	pr_debug("In inflate\n");
 709
 710	tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
 711
 712	if (!tn)
 713		return ERR_PTR(-ENOMEM);
 714
 715	/*
 716	 * Preallocate and store tnodes before the actual work so we
 717	 * don't get into an inconsistent state if memory allocation
 718	 * fails. In case of failure we return the oldnode and  inflate
 719	 * of tnode is ignored.
 720	 */
 721
 722	for (i = 0; i < olen; i++) {
 723		struct tnode *inode;
 724
 725		inode = (struct tnode *) tnode_get_child(oldtnode, i);
 726		if (inode &&
 727		    IS_TNODE(inode) &&
 728		    inode->pos == oldtnode->pos + oldtnode->bits &&
 729		    inode->bits > 1) {
 730			struct tnode *left, *right;
 731			t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
 732
 733			left = tnode_new(inode->key&(~m), inode->pos + 1,
 734					 inode->bits - 1);
 735			if (!left)
 736				goto nomem;
 737
 738			right = tnode_new(inode->key|m, inode->pos + 1,
 739					  inode->bits - 1);
 740
 741			if (!right) {
 742				tnode_free(left);
 743				goto nomem;
 744			}
 745
 746			put_child(tn, 2*i, (struct rt_trie_node *) left);
 747			put_child(tn, 2*i+1, (struct rt_trie_node *) right);
 748		}
 749	}
 750
 751	for (i = 0; i < olen; i++) {
 752		struct tnode *inode;
 753		struct rt_trie_node *node = tnode_get_child(oldtnode, i);
 754		struct tnode *left, *right;
 755		int size, j;
 756
 757		/* An empty child */
 758		if (node == NULL)
 759			continue;
 760
 761		/* A leaf or an internal node with skipped bits */
 762
 763		if (IS_LEAF(node) || ((struct tnode *) node)->pos >
 764		   tn->pos + tn->bits - 1) {
 765			put_child(tn,
 766				tkey_extract_bits(node->key, oldtnode->pos, oldtnode->bits + 1),
 767				node);
 768			continue;
 769		}
 770
 771		/* An internal node with two children */
 772		inode = (struct tnode *) node;
 773
 
 774		if (inode->bits == 1) {
 775			put_child(tn, 2*i, rtnl_dereference(inode->child[0]));
 776			put_child(tn, 2*i+1, rtnl_dereference(inode->child[1]));
 777
 778			tnode_free_safe(inode);
 779			continue;
 780		}
 781
 782		/* An internal node with more than two children */
 783
 784		/* We will replace this node 'inode' with two new
 785		 * ones, 'left' and 'right', each with half of the
 786		 * original children. The two new nodes will have
 787		 * a position one bit further down the key and this
 788		 * means that the "significant" part of their keys
 789		 * (see the discussion near the top of this file)
 790		 * will differ by one bit, which will be "0" in
 791		 * left's key and "1" in right's key. Since we are
 792		 * moving the key position by one step, the bit that
 793		 * we are moving away from - the bit at position
 794		 * (inode->pos) - is the one that will differ between
 795		 * left and right. So... we synthesize that bit in the
 796		 * two  new keys.
 797		 * The mask 'm' below will be a single "one" bit at
 798		 * the position (inode->pos)
 799		 */
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 800
 801		/* Use the old key, but set the new significant
 802		 *   bit to zero.
 803		 */
 
 
 
 
 
 
 
 
 
 
 
 804
 805		left = (struct tnode *) tnode_get_child(tn, 2*i);
 806		put_child(tn, 2*i, NULL);
 807
 808		BUG_ON(!left);
 
 
 809
 810		right = (struct tnode *) tnode_get_child(tn, 2*i+1);
 811		put_child(tn, 2*i+1, NULL);
 812
 813		BUG_ON(!right);
 
 
 
 
 
 
 
 
 814
 815		size = tnode_child_length(left);
 816		for (j = 0; j < size; j++) {
 817			put_child(left, j, rtnl_dereference(inode->child[j]));
 818			put_child(right, j, rtnl_dereference(inode->child[j + size]));
 819		}
 820		put_child(tn, 2*i, resize(t, left));
 821		put_child(tn, 2*i+1, resize(t, right));
 822
 823		tnode_free_safe(inode);
 
 
 
 
 
 
 
 
 
 
 
 
 824	}
 825	tnode_free_safe(oldtnode);
 826	return tn;
 
 827nomem:
 828	tnode_clean_free(tn);
 829	return ERR_PTR(-ENOMEM);
 
 
 830}
 831
 832static struct tnode *halve(struct trie *t, struct tnode *tn)
 
 833{
 834	struct tnode *oldtnode = tn;
 835	struct rt_trie_node *left, *right;
 836	int i;
 837	int olen = tnode_child_length(tn);
 838
 839	pr_debug("In halve\n");
 
 
 840
 841	tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
 
 
 
 842
 843	if (!tn)
 844		return ERR_PTR(-ENOMEM);
 845
 846	/*
 847	 * Preallocate and store tnodes before the actual work so we
 848	 * don't get into an inconsistent state if memory allocation
 849	 * fails. In case of failure we return the oldnode and halve
 850	 * of tnode is ignored.
 851	 */
 852
 853	for (i = 0; i < olen; i += 2) {
 854		left = tnode_get_child(oldtnode, i);
 855		right = tnode_get_child(oldtnode, i+1);
 
 
 856
 857		/* Two nonempty children */
 858		if (left && right) {
 859			struct tnode *newn;
 
 
 860
 861			newn = tnode_new(left->key, tn->pos + tn->bits, 1);
 
 
 
 
 
 
 862
 863			if (!newn)
 864				goto nomem;
 865
 866			put_child(tn, i/2, (struct rt_trie_node *)newn);
 867		}
 
 
 868
 
 
 
 869	}
 870
 871	for (i = 0; i < olen; i += 2) {
 872		struct tnode *newBinNode;
 873
 874		left = tnode_get_child(oldtnode, i);
 875		right = tnode_get_child(oldtnode, i+1);
 876
 877		/* At least one of the children is empty */
 878		if (left == NULL) {
 879			if (right == NULL)    /* Both are empty */
 880				continue;
 881			put_child(tn, i/2, right);
 882			continue;
 883		}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 884
 885		if (right == NULL) {
 886			put_child(tn, i/2, left);
 887			continue;
 888		}
 889
 890		/* Two nonempty children */
 891		newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
 892		put_child(tn, i/2, NULL);
 893		put_child(newBinNode, 0, left);
 894		put_child(newBinNode, 1, right);
 895		put_child(tn, i/2, resize(t, newBinNode));
 896	}
 897	tnode_free_safe(oldtnode);
 898	return tn;
 899nomem:
 900	tnode_clean_free(tn);
 901	return ERR_PTR(-ENOMEM);
 902}
 903
 904/* readside must use rcu_read_lock currently dump routines
 905 via get_fa_head and dump */
 906
 907static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
 908{
 909	struct hlist_head *head = &l->list;
 910	struct leaf_info *li;
 911
 912	hlist_for_each_entry_rcu(li, head, hlist)
 913		if (li->plen == plen)
 914			return li;
 915
 916	return NULL;
 
 
 917}
 918
 919static inline struct list_head *get_fa_head(struct leaf *l, int plen)
 920{
 921	struct leaf_info *li = find_leaf_info(l, plen);
 922
 923	if (!li)
 924		return NULL;
 
 
 
 925
 926	return &li->falh;
 
 927}
 928
 929static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
 
 930{
 931	struct leaf_info *li = NULL, *last = NULL;
 
 
 
 
 
 932
 933	if (hlist_empty(head)) {
 934		hlist_add_head_rcu(&new->hlist, head);
 935	} else {
 936		hlist_for_each_entry(li, head, hlist) {
 937			if (new->plen > li->plen)
 938				break;
 939
 940			last = li;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 941		}
 942		if (last)
 943			hlist_add_after_rcu(&last->hlist, &new->hlist);
 944		else
 945			hlist_add_before_rcu(&new->hlist, &li->hlist);
 946	}
 947}
 948
 949/* rcu_read_lock needs to be hold by caller from readside */
 
 950
 951static struct leaf *
 952fib_find_node(struct trie *t, u32 key)
 953{
 954	int pos;
 955	struct tnode *tn;
 956	struct rt_trie_node *n;
 957
 958	pos = 0;
 959	n = rcu_dereference_rtnl(t->trie);
 960
 961	while (n != NULL &&  NODE_TYPE(n) == T_TNODE) {
 962		tn = (struct tnode *) n;
 963
 964		check_tnode(tn);
 965
 966		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
 967			pos = tn->pos + tn->bits;
 968			n = tnode_get_child_rcu(tn,
 969						tkey_extract_bits(key,
 970								  tn->pos,
 971								  tn->bits));
 972		} else
 973			break;
 
 
 
 
 974	}
 975	/* Case we have found a leaf. Compare prefixes */
 976
 977	if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
 978		return (struct leaf *)n;
 
 979
 980	return NULL;
 
 981}
 982
 983static void trie_rebalance(struct trie *t, struct tnode *tn)
 984{
 985	int wasfull;
 986	t_key cindex, key;
 987	struct tnode *tp;
 988
 989	key = tn->key;
 
 
 
 990
 991	while (tn != NULL && (tp = node_parent((struct rt_trie_node *)tn)) != NULL) {
 992		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
 993		wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
 994		tn = (struct tnode *)resize(t, tn);
 995
 996		tnode_put_child_reorg(tp, cindex,
 997				      (struct rt_trie_node *)tn, wasfull);
 
 
 
 
 
 
 
 
 
 
 
 
 998
 999		tp = node_parent((struct rt_trie_node *) tn);
1000		if (!tp)
1001			rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1002
1003		tnode_free_flush();
1004		if (!tp)
1005			break;
1006		tn = tp;
1007	}
1008
1009	/* Handle last (top) tnode */
1010	if (IS_TNODE(tn))
1011		tn = (struct tnode *)resize(t, tn);
1012
1013	rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1014	tnode_free_flush();
1015}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1016
1017/* only used from updater-side */
 
1018
1019static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
 
 
 
 
 
 
 
1020{
1021	int pos, newpos;
1022	struct tnode *tp = NULL, *tn = NULL;
1023	struct rt_trie_node *n;
1024	struct leaf *l;
1025	int missbit;
1026	struct list_head *fa_head = NULL;
1027	struct leaf_info *li;
1028	t_key cindex;
1029
1030	pos = 0;
1031	n = rtnl_dereference(t->trie);
1032
1033	/* If we point to NULL, stop. Either the tree is empty and we should
1034	 * just put a new leaf in if, or we have reached an empty child slot,
1035	 * and we should just put our new leaf in that.
1036	 * If we point to a T_TNODE, check if it matches our key. Note that
1037	 * a T_TNODE might be skipping any number of bits - its 'pos' need
1038	 * not be the parent's 'pos'+'bits'!
1039	 *
1040	 * If it does match the current key, get pos/bits from it, extract
1041	 * the index from our key, push the T_TNODE and walk the tree.
1042	 *
1043	 * If it doesn't, we have to replace it with a new T_TNODE.
1044	 *
1045	 * If we point to a T_LEAF, it might or might not have the same key
1046	 * as we do. If it does, just change the value, update the T_LEAF's
1047	 * value, and return it.
1048	 * If it doesn't, we need to replace it with a T_TNODE.
1049	 */
1050
1051	while (n != NULL &&  NODE_TYPE(n) == T_TNODE) {
1052		tn = (struct tnode *) n;
 
 
 
 
 
 
 
 
 
 
 
 
 
1053
1054		check_tnode(tn);
 
1055
1056		if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1057			tp = tn;
1058			pos = tn->pos + tn->bits;
1059			n = tnode_get_child(tn,
1060					    tkey_extract_bits(key,
1061							      tn->pos,
1062							      tn->bits));
 
1063
1064			BUG_ON(n && node_parent(n) != tn);
1065		} else
1066			break;
 
 
 
 
 
 
 
 
 
 
 
1067	}
1068
1069	/*
1070	 * n  ----> NULL, LEAF or TNODE
1071	 *
1072	 * tp is n's (parent) ----> NULL or TNODE
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1073	 */
 
 
 
 
1074
1075	BUG_ON(tp && IS_LEAF(tp));
 
1076
1077	/* Case 1: n is a leaf. Compare prefixes */
1078
1079	if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1080		l = (struct leaf *) n;
1081		li = leaf_info_new(plen);
 
1082
1083		if (!li)
1084			return NULL;
1085
1086		fa_head = &li->falh;
1087		insert_leaf_info(&l->list, li);
1088		goto done;
 
 
 
 
 
 
 
 
 
 
 
 
1089	}
1090	l = leaf_new();
1091
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1092	if (!l)
1093		return NULL;
1094
1095	l->key = key;
1096	li = leaf_info_new(plen);
1097
1098	if (!li) {
1099		free_leaf(l);
1100		return NULL;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1101	}
1102
1103	fa_head = &li->falh;
1104	insert_leaf_info(&l->list, li);
 
 
 
1105
1106	if (t->trie && n == NULL) {
1107		/* Case 2: n is NULL, and will just insert a new leaf */
 
 
 
 
1108
1109		node_set_parent((struct rt_trie_node *)l, tp);
 
 
 
 
 
1110
1111		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1112		put_child(tp, cindex, (struct rt_trie_node *)l);
1113	} else {
1114		/* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1115		/*
1116		 *  Add a new tnode here
1117		 *  first tnode need some special handling
1118		 */
1119
1120		if (n) {
1121			pos = tp ? tp->pos+tp->bits : 0;
1122			newpos = tkey_mismatch(key, pos, n->key);
1123			tn = tnode_new(n->key, newpos, 1);
1124		} else {
1125			newpos = 0;
1126			tn = tnode_new(key, newpos, 1); /* First tnode */
1127		}
1128
1129		if (!tn) {
1130			free_leaf_info(li);
1131			free_leaf(l);
1132			return NULL;
1133		}
1134
1135		node_set_parent((struct rt_trie_node *)tn, tp);
 
 
 
 
1136
1137		missbit = tkey_extract_bits(key, newpos, 1);
1138		put_child(tn, missbit, (struct rt_trie_node *)l);
1139		put_child(tn, 1-missbit, n);
1140
1141		if (tp) {
1142			cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1143			put_child(tp, cindex, (struct rt_trie_node *)tn);
1144		} else {
1145			rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1146			tp = tn;
1147		}
1148	}
1149
1150	if (tp && tp->pos + tp->bits > 32)
1151		pr_warn("fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1152			tp, tp->pos, tp->bits, key, plen);
1153
1154	/* Rebalance the trie */
1155
1156	trie_rebalance(t, tp);
1157done:
1158	return fa_head;
1159}
1160
1161/*
1162 * Caller must hold RTNL.
1163 */
1164int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
 
 
1165{
1166	struct trie *t = (struct trie *) tb->tb_data;
1167	struct fib_alias *fa, *new_fa;
1168	struct list_head *fa_head = NULL;
 
1169	struct fib_info *fi;
1170	int plen = cfg->fc_dst_len;
1171	u8 tos = cfg->fc_tos;
1172	u32 key, mask;
 
1173	int err;
1174	struct leaf *l;
1175
1176	if (plen > 32)
1177		return -EINVAL;
1178
1179	key = ntohl(cfg->fc_dst);
1180
1181	pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1182
1183	mask = ntohl(inet_make_mask(plen));
1184
1185	if (key & ~mask)
1186		return -EINVAL;
1187
1188	key = key & mask;
1189
1190	fi = fib_create_info(cfg);
1191	if (IS_ERR(fi)) {
1192		err = PTR_ERR(fi);
1193		goto err;
1194	}
1195
1196	l = fib_find_node(t, key);
1197	fa = NULL;
1198
1199	if (l) {
1200		fa_head = get_fa_head(l, plen);
1201		fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1202	}
1203
1204	/* Now fa, if non-NULL, points to the first fib alias
1205	 * with the same keys [prefix,tos,priority], if such key already
1206	 * exists or to the node before which we will insert new one.
1207	 *
1208	 * If fa is NULL, we will need to allocate a new one and
1209	 * insert to the head of f.
1210	 *
1211	 * If f is NULL, no fib node matched the destination key
1212	 * and we need to allocate a new one of those as well.
1213	 */
1214
1215	if (fa && fa->fa_tos == tos &&
1216	    fa->fa_info->fib_priority == fi->fib_priority) {
1217		struct fib_alias *fa_first, *fa_match;
1218
1219		err = -EEXIST;
1220		if (cfg->fc_nlflags & NLM_F_EXCL)
1221			goto out;
1222
 
 
1223		/* We have 2 goals:
1224		 * 1. Find exact match for type, scope, fib_info to avoid
1225		 * duplicate routes
1226		 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1227		 */
1228		fa_match = NULL;
1229		fa_first = fa;
1230		fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1231		list_for_each_entry_continue(fa, fa_head, fa_list) {
1232			if (fa->fa_tos != tos)
 
1233				break;
1234			if (fa->fa_info->fib_priority != fi->fib_priority)
1235				break;
1236			if (fa->fa_type == cfg->fc_type &&
1237			    fa->fa_info == fi) {
1238				fa_match = fa;
1239				break;
1240			}
1241		}
1242
1243		if (cfg->fc_nlflags & NLM_F_REPLACE) {
1244			struct fib_info *fi_drop;
1245			u8 state;
1246
 
1247			fa = fa_first;
1248			if (fa_match) {
1249				if (fa == fa_match)
1250					err = 0;
1251				goto out;
1252			}
1253			err = -ENOBUFS;
1254			new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1255			if (new_fa == NULL)
1256				goto out;
1257
1258			fi_drop = fa->fa_info;
1259			new_fa->fa_tos = fa->fa_tos;
1260			new_fa->fa_info = fi;
1261			new_fa->fa_type = cfg->fc_type;
1262			state = fa->fa_state;
1263			new_fa->fa_state = state & ~FA_S_ACCESSED;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1264
1265			list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1266			alias_free_mem_rcu(fa);
1267
1268			fib_release_info(fi_drop);
1269			if (state & FA_S_ACCESSED)
1270				rt_cache_flush(cfg->fc_nlinfo.nl_net);
1271			rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1272				tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1273
1274			goto succeeded;
1275		}
1276		/* Error if we find a perfect match which
1277		 * uses the same scope, type, and nexthop
1278		 * information.
1279		 */
1280		if (fa_match)
1281			goto out;
1282
1283		if (!(cfg->fc_nlflags & NLM_F_APPEND))
 
 
1284			fa = fa_first;
1285	}
1286	err = -ENOENT;
1287	if (!(cfg->fc_nlflags & NLM_F_CREATE))
1288		goto out;
1289
 
1290	err = -ENOBUFS;
1291	new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1292	if (new_fa == NULL)
1293		goto out;
1294
1295	new_fa->fa_info = fi;
1296	new_fa->fa_tos = tos;
1297	new_fa->fa_type = cfg->fc_type;
1298	new_fa->fa_state = 0;
1299	/*
1300	 * Insert new entry to the list.
1301	 */
1302
1303	if (!fa_head) {
1304		fa_head = fib_insert_node(t, key, plen);
1305		if (unlikely(!fa_head)) {
1306			err = -ENOMEM;
1307			goto out_free_new_fa;
1308		}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1309	}
1310
1311	if (!plen)
1312		tb->tb_num_default++;
1313
1314	list_add_tail_rcu(&new_fa->fa_list,
1315			  (fa ? &fa->fa_list : fa_head));
1316
1317	rt_cache_flush(cfg->fc_nlinfo.nl_net);
1318	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1319		  &cfg->fc_nlinfo, 0);
1320succeeded:
1321	return 0;
1322
 
 
1323out_free_new_fa:
1324	kmem_cache_free(fn_alias_kmem, new_fa);
1325out:
1326	fib_release_info(fi);
1327err:
1328	return err;
1329}
1330
1331/* should be called with rcu_read_lock */
1332static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
1333		      t_key key,  const struct flowi4 *flp,
1334		      struct fib_result *res, int fib_flags)
1335{
1336	struct leaf_info *li;
1337	struct hlist_head *hhead = &l->list;
1338
1339	hlist_for_each_entry_rcu(li, hhead, hlist) {
1340		struct fib_alias *fa;
1341
1342		if (l->key != (key & li->mask_plen))
1343			continue;
1344
1345		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
1346			struct fib_info *fi = fa->fa_info;
1347			int nhsel, err;
1348
1349			if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1350				continue;
1351			if (fi->fib_dead)
1352				continue;
1353			if (fa->fa_info->fib_scope < flp->flowi4_scope)
1354				continue;
1355			fib_alias_accessed(fa);
1356			err = fib_props[fa->fa_type].error;
1357			if (err) {
1358#ifdef CONFIG_IP_FIB_TRIE_STATS
1359				t->stats.semantic_match_passed++;
1360#endif
1361				return err;
1362			}
1363			if (fi->fib_flags & RTNH_F_DEAD)
1364				continue;
1365			for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
1366				const struct fib_nh *nh = &fi->fib_nh[nhsel];
1367
1368				if (nh->nh_flags & RTNH_F_DEAD)
1369					continue;
1370				if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
1371					continue;
 
1372
1373#ifdef CONFIG_IP_FIB_TRIE_STATS
1374				t->stats.semantic_match_passed++;
1375#endif
1376				res->prefixlen = li->plen;
1377				res->nh_sel = nhsel;
1378				res->type = fa->fa_type;
1379				res->scope = fa->fa_info->fib_scope;
1380				res->fi = fi;
1381				res->table = tb;
1382				res->fa_head = &li->falh;
1383				if (!(fib_flags & FIB_LOOKUP_NOREF))
1384					atomic_inc(&fi->fib_clntref);
1385				return 0;
1386			}
1387		}
1388
1389#ifdef CONFIG_IP_FIB_TRIE_STATS
1390		t->stats.semantic_match_miss++;
1391#endif
1392	}
1393
1394	return 1;
1395}
1396
 
1397int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
1398		     struct fib_result *res, int fib_flags)
1399{
1400	struct trie *t = (struct trie *) tb->tb_data;
1401	int ret;
1402	struct rt_trie_node *n;
1403	struct tnode *pn;
1404	unsigned int pos, bits;
1405	t_key key = ntohl(flp->daddr);
1406	unsigned int chopped_off;
1407	t_key cindex = 0;
1408	unsigned int current_prefix_length = KEYLENGTH;
1409	struct tnode *cn;
1410	t_key pref_mismatch;
1411
1412	rcu_read_lock();
1413
1414	n = rcu_dereference(t->trie);
1415	if (!n)
1416		goto failed;
1417
1418#ifdef CONFIG_IP_FIB_TRIE_STATS
1419	t->stats.gets++;
1420#endif
 
 
 
 
 
1421
1422	/* Just a leaf? */
1423	if (IS_LEAF(n)) {
1424		ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1425		goto found;
1426	}
1427
1428	pn = (struct tnode *) n;
1429	chopped_off = 0;
1430
1431	while (pn) {
1432		pos = pn->pos;
1433		bits = pn->bits;
1434
1435		if (!chopped_off)
1436			cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1437						   pos, bits);
1438
1439		n = tnode_get_child_rcu(pn, cindex);
 
 
 
 
1440
1441		if (n == NULL) {
1442#ifdef CONFIG_IP_FIB_TRIE_STATS
1443			t->stats.null_node_hit++;
1444#endif
1445			goto backtrace;
1446		}
1447
1448		if (IS_LEAF(n)) {
1449			ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1450			if (ret > 0)
1451				goto backtrace;
1452			goto found;
1453		}
1454
1455		cn = (struct tnode *)n;
1456
1457		/*
1458		 * It's a tnode, and we can do some extra checks here if we
1459		 * like, to avoid descending into a dead-end branch.
1460		 * This tnode is in the parent's child array at index
1461		 * key[p_pos..p_pos+p_bits] but potentially with some bits
1462		 * chopped off, so in reality the index may be just a
1463		 * subprefix, padded with zero at the end.
1464		 * We can also take a look at any skipped bits in this
1465		 * tnode - everything up to p_pos is supposed to be ok,
1466		 * and the non-chopped bits of the index (se previous
1467		 * paragraph) are also guaranteed ok, but the rest is
1468		 * considered unknown.
 
1469		 *
1470		 * The skipped bits are key[pos+bits..cn->pos].
1471		 */
1472
1473		/* If current_prefix_length < pos+bits, we are already doing
1474		 * actual prefix  matching, which means everything from
1475		 * pos+(bits-chopped_off) onward must be zero along some
1476		 * branch of this subtree - otherwise there is *no* valid
1477		 * prefix present. Here we can only check the skipped
1478		 * bits. Remember, since we have already indexed into the
1479		 * parent's child array, we know that the bits we chopped of
1480		 * *are* zero.
1481		 */
 
 
1482
1483		/* NOTA BENE: Checking only skipped bits
1484		   for the new node here */
 
1485
1486		if (current_prefix_length < pos+bits) {
1487			if (tkey_extract_bits(cn->key, current_prefix_length,
1488						cn->pos - current_prefix_length)
1489			    || !(cn->child[0]))
1490				goto backtrace;
1491		}
1492
1493		/*
1494		 * If chopped_off=0, the index is fully validated and we
1495		 * only need to look at the skipped bits for this, the new,
1496		 * tnode. What we actually want to do is to find out if
1497		 * these skipped bits match our key perfectly, or if we will
1498		 * have to count on finding a matching prefix further down,
1499		 * because if we do, we would like to have some way of
1500		 * verifying the existence of such a prefix at this point.
1501		 */
 
 
 
 
1502
1503		/* The only thing we can do at this point is to verify that
1504		 * any such matching prefix can indeed be a prefix to our
1505		 * key, and if the bits in the node we are inspecting that
1506		 * do not match our key are not ZERO, this cannot be true.
1507		 * Thus, find out where there is a mismatch (before cn->pos)
1508		 * and verify that all the mismatching bits are zero in the
1509		 * new tnode's key.
1510		 */
1511
1512		/*
1513		 * Note: We aren't very concerned about the piece of
1514		 * the key that precede pn->pos+pn->bits, since these
1515		 * have already been checked. The bits after cn->pos
1516		 * aren't checked since these are by definition
1517		 * "unknown" at this point. Thus, what we want to see
1518		 * is if we are about to enter the "prefix matching"
1519		 * state, and in that case verify that the skipped
1520		 * bits that will prevail throughout this subtree are
1521		 * zero, as they have to be if we are to find a
1522		 * matching prefix.
1523		 */
 
 
1524
1525		pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
 
 
1526
1527		/*
1528		 * In short: If skipped bits in this node do not match
1529		 * the search key, enter the "prefix matching"
1530		 * state.directly.
1531		 */
1532		if (pref_mismatch) {
1533			/* fls(x) = __fls(x) + 1 */
1534			int mp = KEYLENGTH - __fls(pref_mismatch) - 1;
1535
1536			if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
1537				goto backtrace;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1538
1539			if (current_prefix_length >= cn->pos)
1540				current_prefix_length = mp;
1541		}
 
1542
1543		pn = (struct tnode *)n; /* Descend */
1544		chopped_off = 0;
1545		continue;
1546
1547backtrace:
1548		chopped_off++;
 
 
 
1549
1550		/* As zero don't change the child key (cindex) */
1551		while ((chopped_off <= pn->bits)
1552		       && !(cindex & (1<<(chopped_off-1))))
1553			chopped_off++;
1554
1555		/* Decrease current_... with bits chopped off */
1556		if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1557			current_prefix_length = pn->pos + pn->bits
1558				- chopped_off;
1559
1560		/*
1561		 * Either we do the actual chop off according or if we have
1562		 * chopped off all bits in this tnode walk up to our parent.
1563		 */
 
 
 
 
 
 
 
 
 
1564
1565		if (chopped_off <= pn->bits) {
1566			cindex &= ~(1 << (chopped_off-1));
1567		} else {
1568			struct tnode *parent = node_parent_rcu((struct rt_trie_node *) pn);
1569			if (!parent)
1570				goto failed;
1571
1572			/* Get Child's index */
1573			cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1574			pn = parent;
1575			chopped_off = 0;
 
 
 
 
1576
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1577#ifdef CONFIG_IP_FIB_TRIE_STATS
1578			t->stats.backtrack++;
1579#endif
1580			goto backtrace;
 
 
1581		}
1582	}
1583failed:
1584	ret = 1;
1585found:
1586	rcu_read_unlock();
1587	return ret;
1588}
1589EXPORT_SYMBOL_GPL(fib_table_lookup);
1590
1591/*
1592 * Remove the leaf and return parent.
1593 */
1594static void trie_leaf_remove(struct trie *t, struct leaf *l)
1595{
1596	struct tnode *tp = node_parent((struct rt_trie_node *) l);
 
 
1597
1598	pr_debug("entering trie_leaf_remove(%p)\n", l);
 
1599
1600	if (tp) {
1601		t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1602		put_child(tp, cindex, NULL);
 
 
 
 
 
1603		trie_rebalance(t, tp);
1604	} else
1605		RCU_INIT_POINTER(t->trie, NULL);
1606
1607	free_leaf(l);
 
 
 
 
 
 
1608}
1609
1610/*
1611 * Caller must hold RTNL.
1612 */
1613int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1614{
1615	struct trie *t = (struct trie *) tb->tb_data;
1616	u32 key, mask;
1617	int plen = cfg->fc_dst_len;
1618	u8 tos = cfg->fc_tos;
1619	struct fib_alias *fa, *fa_to_delete;
1620	struct list_head *fa_head;
1621	struct leaf *l;
1622	struct leaf_info *li;
1623
1624	if (plen > 32)
1625		return -EINVAL;
1626
1627	key = ntohl(cfg->fc_dst);
1628	mask = ntohl(inet_make_mask(plen));
1629
1630	if (key & ~mask)
1631		return -EINVAL;
1632
1633	key = key & mask;
1634	l = fib_find_node(t, key);
1635
1636	if (!l)
1637		return -ESRCH;
1638
1639	li = find_leaf_info(l, plen);
1640
1641	if (!li)
1642		return -ESRCH;
1643
1644	fa_head = &li->falh;
1645	fa = fib_find_alias(fa_head, tos, 0);
1646
1647	if (!fa)
1648		return -ESRCH;
1649
1650	pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
 
1651
1652	fa_to_delete = NULL;
1653	fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1654	list_for_each_entry_continue(fa, fa_head, fa_list) {
1655		struct fib_info *fi = fa->fa_info;
1656
1657		if (fa->fa_tos != tos)
 
 
1658			break;
1659
1660		if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1661		    (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1662		     fa->fa_info->fib_scope == cfg->fc_scope) &&
1663		    (!cfg->fc_prefsrc ||
1664		     fi->fib_prefsrc == cfg->fc_prefsrc) &&
1665		    (!cfg->fc_protocol ||
1666		     fi->fib_protocol == cfg->fc_protocol) &&
1667		    fib_nh_match(cfg, fi) == 0) {
 
1668			fa_to_delete = fa;
1669			break;
1670		}
1671	}
1672
1673	if (!fa_to_delete)
1674		return -ESRCH;
1675
1676	fa = fa_to_delete;
1677	rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1678		  &cfg->fc_nlinfo, 0);
1679
1680	list_del_rcu(&fa->fa_list);
1681
1682	if (!plen)
1683		tb->tb_num_default--;
1684
1685	if (list_empty(fa_head)) {
1686		hlist_del_rcu(&li->hlist);
1687		free_leaf_info(li);
1688	}
1689
1690	if (hlist_empty(&l->list))
1691		trie_leaf_remove(t, l);
1692
1693	if (fa->fa_state & FA_S_ACCESSED)
1694		rt_cache_flush(cfg->fc_nlinfo.nl_net);
1695
1696	fib_release_info(fa->fa_info);
1697	alias_free_mem_rcu(fa);
1698	return 0;
1699}
1700
1701static int trie_flush_list(struct list_head *head)
 
1702{
1703	struct fib_alias *fa, *fa_node;
1704	int found = 0;
1705
1706	list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1707		struct fib_info *fi = fa->fa_info;
 
 
 
1708
1709		if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1710			list_del_rcu(&fa->fa_list);
1711			fib_release_info(fa->fa_info);
1712			alias_free_mem_rcu(fa);
1713			found++;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1714		}
 
 
 
 
 
 
 
 
 
 
 
 
 
1715	}
1716	return found;
 
 
 
 
 
 
1717}
1718
1719static int trie_flush_leaf(struct leaf *l)
1720{
1721	int found = 0;
1722	struct hlist_head *lih = &l->list;
 
1723	struct hlist_node *tmp;
1724	struct leaf_info *li = NULL;
 
 
 
 
 
 
 
 
 
 
1725
1726	hlist_for_each_entry_safe(li, tmp, lih, hlist) {
1727		found += trie_flush_list(&li->falh);
1728
1729		if (list_empty(&li->falh)) {
1730			hlist_del_rcu(&li->hlist);
1731			free_leaf_info(li);
 
 
 
 
1732		}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1733	}
1734	return found;
 
 
 
 
1735}
1736
1737/*
1738 * Scan for the next right leaf starting at node p->child[idx]
1739 * Since we have back pointer, no recursion necessary.
1740 */
1741static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1742{
1743	do {
1744		t_key idx;
 
 
 
 
1745
1746		if (c)
1747			idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1748		else
1749			idx = 0;
 
 
 
 
 
 
 
1750
1751		while (idx < 1u << p->bits) {
1752			c = tnode_get_child_rcu(p, idx++);
1753			if (!c)
 
1754				continue;
1755
1756			if (IS_LEAF(c))
1757				return (struct leaf *) c;
 
 
 
 
1758
1759			/* Rescan start scanning in new node */
1760			p = (struct tnode *) c;
1761			idx = 0;
 
 
 
 
 
 
1762		}
1763
1764		/* Node empty, walk back up to parent */
1765		c = (struct rt_trie_node *) p;
1766	} while ((p = node_parent_rcu(c)) != NULL);
 
 
 
 
 
 
1767
1768	return NULL; /* Root of trie */
1769}
1770
1771static struct leaf *trie_firstleaf(struct trie *t)
 
1772{
1773	struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
 
 
 
 
1774
1775	if (!n)
1776		return NULL;
 
 
1777
1778	if (IS_LEAF(n))          /* trie is just a leaf */
1779		return (struct leaf *) n;
1780
1781	return leaf_walk_rcu(n, NULL);
1782}
 
1783
1784static struct leaf *trie_nextleaf(struct leaf *l)
1785{
1786	struct rt_trie_node *c = (struct rt_trie_node *) l;
1787	struct tnode *p = node_parent_rcu(c);
 
 
 
1788
1789	if (!p)
1790		return NULL;	/* trie with just one leaf */
1791
1792	return leaf_walk_rcu(p, c);
1793}
 
 
1794
1795static struct leaf *trie_leafindex(struct trie *t, int index)
1796{
1797	struct leaf *l = trie_firstleaf(t);
 
1798
1799	while (l && index-- > 0)
1800		l = trie_nextleaf(l);
1801
1802	return l;
1803}
 
 
 
 
 
 
 
1804
 
 
 
1805
1806/*
1807 * Caller must hold RTNL.
1808 */
1809int fib_table_flush(struct fib_table *tb)
 
 
 
 
 
 
 
 
1810{
1811	struct trie *t = (struct trie *) tb->tb_data;
1812	struct leaf *l, *ll = NULL;
 
 
 
 
1813	int found = 0;
1814
1815	for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1816		found += trie_flush_leaf(l);
 
 
1817
1818		if (ll && hlist_empty(&ll->list))
1819			trie_leaf_remove(t, ll);
1820		ll = l;
1821	}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1822
1823	if (ll && hlist_empty(&ll->list))
1824		trie_leaf_remove(t, ll);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1825
1826	pr_debug("trie_flush found=%d\n", found);
1827	return found;
1828}
1829
1830void fib_free_table(struct fib_table *tb)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1831{
1832	kfree(tb);
 
 
 
 
 
 
 
 
 
1833}
1834
1835static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1836			   struct fib_table *tb,
1837			   struct sk_buff *skb, struct netlink_callback *cb)
1838{
1839	int i, s_i;
1840	struct fib_alias *fa;
1841	__be32 xkey = htonl(key);
 
1842
1843	s_i = cb->args[5];
1844	i = 0;
1845
1846	/* rcu_read_lock is hold by caller */
 
1847
1848	list_for_each_entry_rcu(fa, fah, fa_list) {
1849		if (i < s_i) {
1850			i++;
 
1851			continue;
1852		}
1853
1854		if (fib_dump_info(skb, NETLINK_CB(cb->skb).portid,
1855				  cb->nlh->nlmsg_seq,
1856				  RTM_NEWROUTE,
1857				  tb->tb_id,
1858				  fa->fa_type,
1859				  xkey,
1860				  plen,
1861				  fa->fa_tos,
1862				  fa->fa_info, NLM_F_MULTI) < 0) {
1863			cb->args[5] = i;
1864			return -1;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1865		}
1866		i++;
1867	}
1868	cb->args[5] = i;
1869	return skb->len;
1870}
1871
1872static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1873			struct sk_buff *skb, struct netlink_callback *cb)
1874{
1875	struct leaf_info *li;
1876	int i, s_i;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1877
1878	s_i = cb->args[4];
 
1879	i = 0;
1880
1881	/* rcu_read_lock is hold by caller */
1882	hlist_for_each_entry_rcu(li, &l->list, hlist) {
1883		if (i < s_i) {
1884			i++;
1885			continue;
1886		}
1887
1888		if (i > s_i)
1889			cb->args[5] = 0;
1890
1891		if (list_empty(&li->falh))
1892			continue;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1893
1894		if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1895			cb->args[4] = i;
1896			return -1;
1897		}
 
 
 
 
 
 
 
 
 
1898		i++;
1899	}
1900
1901	cb->args[4] = i;
1902	return skb->len;
 
 
 
 
 
1903}
1904
 
1905int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
1906		   struct netlink_callback *cb)
1907{
1908	struct leaf *l;
1909	struct trie *t = (struct trie *) tb->tb_data;
1910	t_key key = cb->args[2];
1911	int count = cb->args[3];
1912
1913	rcu_read_lock();
1914	/* Dump starting at last key.
1915	 * Note: 0.0.0.0/0 (ie default) is first key.
1916	 */
1917	if (count == 0)
1918		l = trie_firstleaf(t);
1919	else {
1920		/* Normally, continue from last key, but if that is missing
1921		 * fallback to using slow rescan
1922		 */
1923		l = fib_find_node(t, key);
1924		if (!l)
1925			l = trie_leafindex(t, count);
1926	}
1927
1928	while (l) {
1929		cb->args[2] = l->key;
1930		if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1931			cb->args[3] = count;
1932			rcu_read_unlock();
1933			return -1;
 
 
 
 
 
 
 
 
1934		}
1935
1936		++count;
1937		l = trie_nextleaf(l);
 
1938		memset(&cb->args[4], 0,
1939		       sizeof(cb->args) - 4*sizeof(cb->args[0]));
 
 
 
 
1940	}
1941	cb->args[3] = count;
1942	rcu_read_unlock();
1943
1944	return skb->len;
 
 
 
1945}
1946
1947void __init fib_trie_init(void)
1948{
1949	fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1950					  sizeof(struct fib_alias),
1951					  0, SLAB_PANIC, NULL);
1952
1953	trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1954					   max(sizeof(struct leaf),
1955					       sizeof(struct leaf_info)),
1956					   0, SLAB_PANIC, NULL);
1957}
1958
1959
1960struct fib_table *fib_trie_table(u32 id)
1961{
1962	struct fib_table *tb;
1963	struct trie *t;
 
1964
1965	tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1966		     GFP_KERNEL);
1967	if (tb == NULL)
 
 
1968		return NULL;
1969
1970	tb->tb_id = id;
1971	tb->tb_default = -1;
1972	tb->tb_num_default = 0;
 
 
 
 
1973
1974	t = (struct trie *) tb->tb_data;
1975	memset(t, 0, sizeof(*t));
 
 
 
 
 
 
 
 
1976
1977	return tb;
1978}
1979
1980#ifdef CONFIG_PROC_FS
1981/* Depth first Trie walk iterator */
1982struct fib_trie_iter {
1983	struct seq_net_private p;
1984	struct fib_table *tb;
1985	struct tnode *tnode;
1986	unsigned int index;
1987	unsigned int depth;
1988};
1989
1990static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
1991{
1992	struct tnode *tn = iter->tnode;
1993	unsigned int cindex = iter->index;
1994	struct tnode *p;
1995
1996	/* A single entry routing table */
1997	if (!tn)
1998		return NULL;
1999
2000	pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2001		 iter->tnode, iter->index, iter->depth);
2002rescan:
2003	while (cindex < (1<<tn->bits)) {
2004		struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
2005
2006		if (n) {
 
 
 
 
 
 
2007			if (IS_LEAF(n)) {
2008				iter->tnode = tn;
2009				iter->index = cindex + 1;
2010			} else {
2011				/* push down one level */
2012				iter->tnode = (struct tnode *) n;
2013				iter->index = 0;
2014				++iter->depth;
2015			}
 
2016			return n;
2017		}
2018
2019		++cindex;
2020	}
2021
2022	/* Current node exhausted, pop back up */
2023	p = node_parent_rcu((struct rt_trie_node *)tn);
2024	if (p) {
2025		cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2026		tn = p;
2027		--iter->depth;
2028		goto rescan;
2029	}
2030
2031	/* got root? */
 
 
 
2032	return NULL;
2033}
2034
2035static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
2036				       struct trie *t)
2037{
2038	struct rt_trie_node *n;
2039
2040	if (!t)
2041		return NULL;
2042
2043	n = rcu_dereference(t->trie);
 
2044	if (!n)
2045		return NULL;
2046
2047	if (IS_TNODE(n)) {
2048		iter->tnode = (struct tnode *) n;
2049		iter->index = 0;
2050		iter->depth = 1;
2051	} else {
2052		iter->tnode = NULL;
2053		iter->index = 0;
2054		iter->depth = 0;
2055	}
2056
2057	return n;
2058}
2059
2060static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2061{
2062	struct rt_trie_node *n;
2063	struct fib_trie_iter iter;
2064
2065	memset(s, 0, sizeof(*s));
2066
2067	rcu_read_lock();
2068	for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2069		if (IS_LEAF(n)) {
2070			struct leaf *l = (struct leaf *)n;
2071			struct leaf_info *li;
2072
2073			s->leaves++;
2074			s->totdepth += iter.depth;
2075			if (iter.depth > s->maxdepth)
2076				s->maxdepth = iter.depth;
2077
2078			hlist_for_each_entry_rcu(li, &l->list, hlist)
2079				++s->prefixes;
2080		} else {
2081			const struct tnode *tn = (const struct tnode *) n;
2082			int i;
2083
2084			s->tnodes++;
2085			if (tn->bits < MAX_STAT_DEPTH)
2086				s->nodesizes[tn->bits]++;
2087
2088			for (i = 0; i < (1<<tn->bits); i++)
2089				if (!tn->child[i])
2090					s->nullpointers++;
2091		}
2092	}
2093	rcu_read_unlock();
2094}
2095
2096/*
2097 *	This outputs /proc/net/fib_triestats
2098 */
2099static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2100{
2101	unsigned int i, max, pointers, bytes, avdepth;
2102
2103	if (stat->leaves)
2104		avdepth = stat->totdepth*100 / stat->leaves;
2105	else
2106		avdepth = 0;
2107
2108	seq_printf(seq, "\tAver depth:     %u.%02d\n",
2109		   avdepth / 100, avdepth % 100);
2110	seq_printf(seq, "\tMax depth:      %u\n", stat->maxdepth);
2111
2112	seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
2113	bytes = sizeof(struct leaf) * stat->leaves;
2114
2115	seq_printf(seq, "\tPrefixes:       %u\n", stat->prefixes);
2116	bytes += sizeof(struct leaf_info) * stat->prefixes;
2117
2118	seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2119	bytes += sizeof(struct tnode) * stat->tnodes;
2120
2121	max = MAX_STAT_DEPTH;
2122	while (max > 0 && stat->nodesizes[max-1] == 0)
2123		max--;
2124
2125	pointers = 0;
2126	for (i = 1; i < max; i++)
2127		if (stat->nodesizes[i] != 0) {
2128			seq_printf(seq, "  %u: %u",  i, stat->nodesizes[i]);
2129			pointers += (1<<i) * stat->nodesizes[i];
2130		}
2131	seq_putc(seq, '\n');
2132	seq_printf(seq, "\tPointers: %u\n", pointers);
2133
2134	bytes += sizeof(struct rt_trie_node *) * pointers;
2135	seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2136	seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
2137}
2138
2139#ifdef CONFIG_IP_FIB_TRIE_STATS
2140static void trie_show_usage(struct seq_file *seq,
2141			    const struct trie_use_stats *stats)
2142{
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2143	seq_printf(seq, "\nCounters:\n---------\n");
2144	seq_printf(seq, "gets = %u\n", stats->gets);
2145	seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2146	seq_printf(seq, "semantic match passed = %u\n",
2147		   stats->semantic_match_passed);
2148	seq_printf(seq, "semantic match miss = %u\n",
2149		   stats->semantic_match_miss);
2150	seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2151	seq_printf(seq, "skipped node resize = %u\n\n",
2152		   stats->resize_node_skipped);
2153}
2154#endif /*  CONFIG_IP_FIB_TRIE_STATS */
2155
2156static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2157{
2158	if (tb->tb_id == RT_TABLE_LOCAL)
2159		seq_puts(seq, "Local:\n");
2160	else if (tb->tb_id == RT_TABLE_MAIN)
2161		seq_puts(seq, "Main:\n");
2162	else
2163		seq_printf(seq, "Id %d:\n", tb->tb_id);
2164}
2165
2166
2167static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2168{
2169	struct net *net = (struct net *)seq->private;
2170	unsigned int h;
2171
2172	seq_printf(seq,
2173		   "Basic info: size of leaf:"
2174		   " %Zd bytes, size of tnode: %Zd bytes.\n",
2175		   sizeof(struct leaf), sizeof(struct tnode));
2176
 
2177	for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2178		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2179		struct fib_table *tb;
2180
2181		hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2182			struct trie *t = (struct trie *) tb->tb_data;
2183			struct trie_stat stat;
2184
2185			if (!t)
2186				continue;
2187
2188			fib_table_print(seq, tb);
2189
2190			trie_collect_stats(t, &stat);
2191			trie_show_stats(seq, &stat);
2192#ifdef CONFIG_IP_FIB_TRIE_STATS
2193			trie_show_usage(seq, &t->stats);
2194#endif
2195		}
 
2196	}
 
2197
2198	return 0;
2199}
2200
2201static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2202{
2203	return single_open_net(inode, file, fib_triestat_seq_show);
2204}
2205
2206static const struct file_operations fib_triestat_fops = {
2207	.owner	= THIS_MODULE,
2208	.open	= fib_triestat_seq_open,
2209	.read	= seq_read,
2210	.llseek	= seq_lseek,
2211	.release = single_release_net,
2212};
2213
2214static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2215{
2216	struct fib_trie_iter *iter = seq->private;
2217	struct net *net = seq_file_net(seq);
2218	loff_t idx = 0;
2219	unsigned int h;
2220
2221	for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2222		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2223		struct fib_table *tb;
2224
2225		hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2226			struct rt_trie_node *n;
2227
2228			for (n = fib_trie_get_first(iter,
2229						    (struct trie *) tb->tb_data);
2230			     n; n = fib_trie_get_next(iter))
2231				if (pos == idx++) {
2232					iter->tb = tb;
2233					return n;
2234				}
2235		}
2236	}
2237
2238	return NULL;
2239}
2240
2241static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2242	__acquires(RCU)
2243{
2244	rcu_read_lock();
2245	return fib_trie_get_idx(seq, *pos);
2246}
2247
2248static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2249{
2250	struct fib_trie_iter *iter = seq->private;
2251	struct net *net = seq_file_net(seq);
2252	struct fib_table *tb = iter->tb;
2253	struct hlist_node *tb_node;
2254	unsigned int h;
2255	struct rt_trie_node *n;
2256
2257	++*pos;
2258	/* next node in same table */
2259	n = fib_trie_get_next(iter);
2260	if (n)
2261		return n;
2262
2263	/* walk rest of this hash chain */
2264	h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2265	while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2266		tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2267		n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2268		if (n)
2269			goto found;
2270	}
2271
2272	/* new hash chain */
2273	while (++h < FIB_TABLE_HASHSZ) {
2274		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2275		hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2276			n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2277			if (n)
2278				goto found;
2279		}
2280	}
2281	return NULL;
2282
2283found:
2284	iter->tb = tb;
2285	return n;
2286}
2287
2288static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2289	__releases(RCU)
2290{
2291	rcu_read_unlock();
2292}
2293
2294static void seq_indent(struct seq_file *seq, int n)
2295{
2296	while (n-- > 0)
2297		seq_puts(seq, "   ");
2298}
2299
2300static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2301{
2302	switch (s) {
2303	case RT_SCOPE_UNIVERSE: return "universe";
2304	case RT_SCOPE_SITE:	return "site";
2305	case RT_SCOPE_LINK:	return "link";
2306	case RT_SCOPE_HOST:	return "host";
2307	case RT_SCOPE_NOWHERE:	return "nowhere";
2308	default:
2309		snprintf(buf, len, "scope=%d", s);
2310		return buf;
2311	}
2312}
2313
2314static const char *const rtn_type_names[__RTN_MAX] = {
2315	[RTN_UNSPEC] = "UNSPEC",
2316	[RTN_UNICAST] = "UNICAST",
2317	[RTN_LOCAL] = "LOCAL",
2318	[RTN_BROADCAST] = "BROADCAST",
2319	[RTN_ANYCAST] = "ANYCAST",
2320	[RTN_MULTICAST] = "MULTICAST",
2321	[RTN_BLACKHOLE] = "BLACKHOLE",
2322	[RTN_UNREACHABLE] = "UNREACHABLE",
2323	[RTN_PROHIBIT] = "PROHIBIT",
2324	[RTN_THROW] = "THROW",
2325	[RTN_NAT] = "NAT",
2326	[RTN_XRESOLVE] = "XRESOLVE",
2327};
2328
2329static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2330{
2331	if (t < __RTN_MAX && rtn_type_names[t])
2332		return rtn_type_names[t];
2333	snprintf(buf, len, "type %u", t);
2334	return buf;
2335}
2336
2337/* Pretty print the trie */
2338static int fib_trie_seq_show(struct seq_file *seq, void *v)
2339{
2340	const struct fib_trie_iter *iter = seq->private;
2341	struct rt_trie_node *n = v;
2342
2343	if (!node_parent_rcu(n))
2344		fib_table_print(seq, iter->tb);
2345
2346	if (IS_TNODE(n)) {
2347		struct tnode *tn = (struct tnode *) n;
2348		__be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2349
2350		seq_indent(seq, iter->depth-1);
2351		seq_printf(seq, "  +-- %pI4/%d %d %d %d\n",
2352			   &prf, tn->pos, tn->bits, tn->full_children,
2353			   tn->empty_children);
2354
2355	} else {
2356		struct leaf *l = (struct leaf *) n;
2357		struct leaf_info *li;
2358		__be32 val = htonl(l->key);
2359
2360		seq_indent(seq, iter->depth);
2361		seq_printf(seq, "  |-- %pI4\n", &val);
2362
2363		hlist_for_each_entry_rcu(li, &l->list, hlist) {
2364			struct fib_alias *fa;
2365
2366			list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2367				char buf1[32], buf2[32];
2368
2369				seq_indent(seq, iter->depth+1);
2370				seq_printf(seq, "  /%d %s %s", li->plen,
2371					   rtn_scope(buf1, sizeof(buf1),
2372						     fa->fa_info->fib_scope),
2373					   rtn_type(buf2, sizeof(buf2),
2374						    fa->fa_type));
2375				if (fa->fa_tos)
2376					seq_printf(seq, " tos=%d", fa->fa_tos);
2377				seq_putc(seq, '\n');
2378			}
 
2379		}
2380	}
2381
2382	return 0;
2383}
2384
2385static const struct seq_operations fib_trie_seq_ops = {
2386	.start  = fib_trie_seq_start,
2387	.next   = fib_trie_seq_next,
2388	.stop   = fib_trie_seq_stop,
2389	.show   = fib_trie_seq_show,
2390};
2391
2392static int fib_trie_seq_open(struct inode *inode, struct file *file)
2393{
2394	return seq_open_net(inode, file, &fib_trie_seq_ops,
2395			    sizeof(struct fib_trie_iter));
2396}
2397
2398static const struct file_operations fib_trie_fops = {
2399	.owner  = THIS_MODULE,
2400	.open   = fib_trie_seq_open,
2401	.read   = seq_read,
2402	.llseek = seq_lseek,
2403	.release = seq_release_net,
2404};
2405
2406struct fib_route_iter {
2407	struct seq_net_private p;
2408	struct trie *main_trie;
 
2409	loff_t	pos;
2410	t_key	key;
2411};
2412
2413static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
 
2414{
2415	struct leaf *l = NULL;
2416	struct trie *t = iter->main_trie;
2417
2418	/* use cache location of last found key */
2419	if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2420		pos -= iter->pos;
2421	else {
2422		iter->pos = 0;
2423		l = trie_firstleaf(t);
2424	}
2425
2426	while (l && pos-- > 0) {
 
 
 
2427		iter->pos++;
2428		l = trie_nextleaf(l);
 
 
 
 
2429	}
2430
2431	if (l)
2432		iter->key = pos;	/* remember it */
2433	else
2434		iter->pos = 0;		/* forget it */
2435
2436	return l;
2437}
2438
2439static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2440	__acquires(RCU)
2441{
2442	struct fib_route_iter *iter = seq->private;
2443	struct fib_table *tb;
 
2444
2445	rcu_read_lock();
 
2446	tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2447	if (!tb)
2448		return NULL;
2449
2450	iter->main_trie = (struct trie *) tb->tb_data;
2451	if (*pos == 0)
2452		return SEQ_START_TOKEN;
2453	else
2454		return fib_route_get_idx(iter, *pos - 1);
 
 
 
 
 
 
2455}
2456
2457static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2458{
2459	struct fib_route_iter *iter = seq->private;
2460	struct leaf *l = v;
 
2461
2462	++*pos;
2463	if (v == SEQ_START_TOKEN) {
2464		iter->pos = 0;
2465		l = trie_firstleaf(iter->main_trie);
2466	} else {
2467		iter->pos++;
2468		l = trie_nextleaf(l);
2469	}
2470
2471	if (l)
 
 
 
 
2472		iter->key = l->key;
2473	else
 
2474		iter->pos = 0;
 
 
2475	return l;
2476}
2477
2478static void fib_route_seq_stop(struct seq_file *seq, void *v)
2479	__releases(RCU)
2480{
2481	rcu_read_unlock();
2482}
2483
2484static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2485{
2486	unsigned int flags = 0;
2487
2488	if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
2489		flags = RTF_REJECT;
2490	if (fi && fi->fib_nh->nh_gw)
2491		flags |= RTF_GATEWAY;
 
 
 
 
2492	if (mask == htonl(0xFFFFFFFF))
2493		flags |= RTF_HOST;
2494	flags |= RTF_UP;
2495	return flags;
2496}
2497
2498/*
2499 *	This outputs /proc/net/route.
2500 *	The format of the file is not supposed to be changed
2501 *	and needs to be same as fib_hash output to avoid breaking
2502 *	legacy utilities
2503 */
2504static int fib_route_seq_show(struct seq_file *seq, void *v)
2505{
2506	struct leaf *l = v;
2507	struct leaf_info *li;
 
 
 
2508
2509	if (v == SEQ_START_TOKEN) {
2510		seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2511			   "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2512			   "\tWindow\tIRTT");
2513		return 0;
2514	}
2515
2516	hlist_for_each_entry_rcu(li, &l->list, hlist) {
2517		struct fib_alias *fa;
2518		__be32 mask, prefix;
2519
2520		mask = inet_make_mask(li->plen);
2521		prefix = htonl(l->key);
2522
2523		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2524			const struct fib_info *fi = fa->fa_info;
2525			unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
 
2526
2527			if (fa->fa_type == RTN_BROADCAST
2528			    || fa->fa_type == RTN_MULTICAST)
2529				continue;
2530
2531			seq_setwidth(seq, 127);
 
2532
2533			if (fi)
2534				seq_printf(seq,
2535					 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2536					 "%d\t%08X\t%d\t%u\t%u",
2537					 fi->fib_dev ? fi->fib_dev->name : "*",
2538					 prefix,
2539					 fi->fib_nh->nh_gw, flags, 0, 0,
2540					 fi->fib_priority,
2541					 mask,
2542					 (fi->fib_advmss ?
2543					  fi->fib_advmss + 40 : 0),
2544					 fi->fib_window,
2545					 fi->fib_rtt >> 3);
2546			else
2547				seq_printf(seq,
2548					 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2549					 "%d\t%08X\t%d\t%u\t%u",
2550					 prefix, 0, flags, 0, 0, 0,
2551					 mask, 0, 0, 0);
2552
2553			seq_pad(seq, '\n');
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2554		}
 
2555	}
2556
2557	return 0;
2558}
2559
2560static const struct seq_operations fib_route_seq_ops = {
2561	.start  = fib_route_seq_start,
2562	.next   = fib_route_seq_next,
2563	.stop   = fib_route_seq_stop,
2564	.show   = fib_route_seq_show,
2565};
2566
2567static int fib_route_seq_open(struct inode *inode, struct file *file)
2568{
2569	return seq_open_net(inode, file, &fib_route_seq_ops,
2570			    sizeof(struct fib_route_iter));
2571}
2572
2573static const struct file_operations fib_route_fops = {
2574	.owner  = THIS_MODULE,
2575	.open   = fib_route_seq_open,
2576	.read   = seq_read,
2577	.llseek = seq_lseek,
2578	.release = seq_release_net,
2579};
2580
2581int __net_init fib_proc_init(struct net *net)
2582{
2583	if (!proc_create("fib_trie", S_IRUGO, net->proc_net, &fib_trie_fops))
 
2584		goto out1;
2585
2586	if (!proc_create("fib_triestat", S_IRUGO, net->proc_net,
2587			 &fib_triestat_fops))
2588		goto out2;
2589
2590	if (!proc_create("route", S_IRUGO, net->proc_net, &fib_route_fops))
 
2591		goto out3;
2592
2593	return 0;
2594
2595out3:
2596	remove_proc_entry("fib_triestat", net->proc_net);
2597out2:
2598	remove_proc_entry("fib_trie", net->proc_net);
2599out1:
2600	return -ENOMEM;
2601}
2602
2603void __net_exit fib_proc_exit(struct net *net)
2604{
2605	remove_proc_entry("fib_trie", net->proc_net);
2606	remove_proc_entry("fib_triestat", net->proc_net);
2607	remove_proc_entry("route", net->proc_net);
2608}
2609
2610#endif /* CONFIG_PROC_FS */