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