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/prefetch.h>
  75#include <linux/export.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_warn("fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1173			tp, tp->pos, tp->bits, key, plen);
1174
1175	/* Rebalance the trie */
1176
1177	trie_rebalance(t, tp);
1178done:
1179	return fa_head;
1180}
1181
1182/*
1183 * Caller must hold RTNL.
1184 */
1185int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
1186{
1187	struct trie *t = (struct trie *) tb->tb_data;
 
1188	struct fib_alias *fa, *new_fa;
1189	struct list_head *fa_head = NULL;
 
1190	struct fib_info *fi;
1191	int plen = cfg->fc_dst_len;
 
1192	u8 tos = cfg->fc_tos;
1193	u32 key, mask;
1194	int err;
1195	struct leaf *l;
1196
1197	if (plen > 32)
1198		return -EINVAL;
1199
1200	key = ntohl(cfg->fc_dst);
1201
1202	pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1203
1204	mask = ntohl(inet_make_mask(plen));
1205
1206	if (key & ~mask)
1207		return -EINVAL;
1208
1209	key = key & mask;
1210
1211	fi = fib_create_info(cfg);
1212	if (IS_ERR(fi)) {
1213		err = PTR_ERR(fi);
1214		goto err;
1215	}
1216
1217	l = fib_find_node(t, key);
1218	fa = NULL;
1219
1220	if (l) {
1221		fa_head = get_fa_head(l, plen);
1222		fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1223	}
1224
1225	/* Now fa, if non-NULL, points to the first fib alias
1226	 * with the same keys [prefix,tos,priority], if such key already
1227	 * exists or to the node before which we will insert new one.
1228	 *
1229	 * If fa is NULL, we will need to allocate a new one and
1230	 * insert to the head of f.
1231	 *
1232	 * If f is NULL, no fib node matched the destination key
1233	 * and we need to allocate a new one of those as well.
1234	 */
1235
1236	if (fa && fa->fa_tos == tos &&
1237	    fa->fa_info->fib_priority == fi->fib_priority) {
1238		struct fib_alias *fa_first, *fa_match;
1239
1240		err = -EEXIST;
1241		if (cfg->fc_nlflags & NLM_F_EXCL)
1242			goto out;
1243
 
 
1244		/* We have 2 goals:
1245		 * 1. Find exact match for type, scope, fib_info to avoid
1246		 * duplicate routes
1247		 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1248		 */
1249		fa_match = NULL;
1250		fa_first = fa;
1251		fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1252		list_for_each_entry_continue(fa, fa_head, fa_list) {
1253			if (fa->fa_tos != tos)
 
1254				break;
1255			if (fa->fa_info->fib_priority != fi->fib_priority)
1256				break;
1257			if (fa->fa_type == cfg->fc_type &&
1258			    fa->fa_info == fi) {
1259				fa_match = fa;
1260				break;
1261			}
1262		}
1263
1264		if (cfg->fc_nlflags & NLM_F_REPLACE) {
1265			struct fib_info *fi_drop;
1266			u8 state;
1267
 
1268			fa = fa_first;
1269			if (fa_match) {
1270				if (fa == fa_match)
1271					err = 0;
1272				goto out;
1273			}
1274			err = -ENOBUFS;
1275			new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1276			if (new_fa == NULL)
1277				goto out;
1278
1279			fi_drop = fa->fa_info;
1280			new_fa->fa_tos = fa->fa_tos;
1281			new_fa->fa_info = fi;
1282			new_fa->fa_type = cfg->fc_type;
1283			state = fa->fa_state;
1284			new_fa->fa_state = state & ~FA_S_ACCESSED;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1285
1286			list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1287			alias_free_mem_rcu(fa);
1288
1289			fib_release_info(fi_drop);
1290			if (state & FA_S_ACCESSED)
1291				rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1292			rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1293				tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1294
1295			goto succeeded;
1296		}
1297		/* Error if we find a perfect match which
1298		 * uses the same scope, type, and nexthop
1299		 * information.
1300		 */
1301		if (fa_match)
1302			goto out;
1303
1304		if (!(cfg->fc_nlflags & NLM_F_APPEND))
 
 
 
1305			fa = fa_first;
 
1306	}
1307	err = -ENOENT;
1308	if (!(cfg->fc_nlflags & NLM_F_CREATE))
1309		goto out;
1310
 
1311	err = -ENOBUFS;
1312	new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1313	if (new_fa == NULL)
1314		goto out;
1315
1316	new_fa->fa_info = fi;
1317	new_fa->fa_tos = tos;
1318	new_fa->fa_type = cfg->fc_type;
1319	new_fa->fa_state = 0;
1320	/*
1321	 * Insert new entry to the list.
1322	 */
1323
1324	if (!fa_head) {
1325		fa_head = fib_insert_node(t, key, plen);
1326		if (unlikely(!fa_head)) {
1327			err = -ENOMEM;
1328			goto out_free_new_fa;
1329		}
1330	}
 
1331
1332	if (!plen)
1333		tb->tb_num_default++;
1334
1335	list_add_tail_rcu(&new_fa->fa_list,
1336			  (fa ? &fa->fa_list : fa_head));
1337
1338	rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1339	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1340		  &cfg->fc_nlinfo, 0);
1341succeeded:
1342	return 0;
1343
 
 
 
 
 
 
 
 
1344out_free_new_fa:
1345	kmem_cache_free(fn_alias_kmem, new_fa);
1346out:
1347	fib_release_info(fi);
1348err:
1349	return err;
1350}
1351
1352/* should be called with rcu_read_lock */
1353static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
1354		      t_key key,  const struct flowi4 *flp,
1355		      struct fib_result *res, int fib_flags)
1356{
1357	struct leaf_info *li;
1358	struct hlist_head *hhead = &l->list;
1359	struct hlist_node *node;
1360
1361	hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1362		struct fib_alias *fa;
1363
1364		if (l->key != (key & li->mask_plen))
1365			continue;
1366
1367		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
1368			struct fib_info *fi = fa->fa_info;
1369			int nhsel, err;
1370
1371			if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1372				continue;
1373			if (fi->fib_dead)
1374				continue;
1375			if (fa->fa_info->fib_scope < flp->flowi4_scope)
1376				continue;
1377			fib_alias_accessed(fa);
1378			err = fib_props[fa->fa_type].error;
1379			if (err) {
1380#ifdef CONFIG_IP_FIB_TRIE_STATS
1381				t->stats.semantic_match_passed++;
1382#endif
1383				return err;
1384			}
1385			if (fi->fib_flags & RTNH_F_DEAD)
1386				continue;
1387			for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
1388				const struct fib_nh *nh = &fi->fib_nh[nhsel];
1389
1390				if (nh->nh_flags & RTNH_F_DEAD)
1391					continue;
1392				if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
1393					continue;
1394
1395#ifdef CONFIG_IP_FIB_TRIE_STATS
1396				t->stats.semantic_match_passed++;
1397#endif
1398				res->prefixlen = li->plen;
1399				res->nh_sel = nhsel;
1400				res->type = fa->fa_type;
1401				res->scope = fa->fa_info->fib_scope;
1402				res->fi = fi;
1403				res->table = tb;
1404				res->fa_head = &li->falh;
1405				if (!(fib_flags & FIB_LOOKUP_NOREF))
1406					atomic_inc(&fi->fib_clntref);
1407				return 0;
1408			}
1409		}
1410
1411#ifdef CONFIG_IP_FIB_TRIE_STATS
1412		t->stats.semantic_match_miss++;
1413#endif
1414	}
1415
1416	return 1;
1417}
1418
 
1419int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
1420		     struct fib_result *res, int fib_flags)
1421{
1422	struct trie *t = (struct trie *) tb->tb_data;
1423	int ret;
1424	struct rt_trie_node *n;
1425	struct tnode *pn;
1426	unsigned int pos, bits;
1427	t_key key = ntohl(flp->daddr);
1428	unsigned int chopped_off;
1429	t_key cindex = 0;
1430	unsigned int current_prefix_length = KEYLENGTH;
1431	struct tnode *cn;
1432	t_key pref_mismatch;
1433
1434	rcu_read_lock();
1435
1436	n = rcu_dereference(t->trie);
1437	if (!n)
1438		goto failed;
1439
1440#ifdef CONFIG_IP_FIB_TRIE_STATS
1441	t->stats.gets++;
1442#endif
 
 
 
 
 
1443
1444	/* Just a leaf? */
1445	if (IS_LEAF(n)) {
1446		ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1447		goto found;
1448	}
1449
1450	pn = (struct tnode *) n;
1451	chopped_off = 0;
1452
1453	while (pn) {
1454		pos = pn->pos;
1455		bits = pn->bits;
1456
1457		if (!chopped_off)
1458			cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1459						   pos, bits);
1460
1461		n = tnode_get_child_rcu(pn, cindex);
 
 
 
 
1462
1463		if (n == NULL) {
1464#ifdef CONFIG_IP_FIB_TRIE_STATS
1465			t->stats.null_node_hit++;
1466#endif
1467			goto backtrace;
1468		}
1469
1470		if (IS_LEAF(n)) {
1471			ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1472			if (ret > 0)
1473				goto backtrace;
1474			goto found;
1475		}
1476
1477		cn = (struct tnode *)n;
1478
1479		/*
1480		 * It's a tnode, and we can do some extra checks here if we
1481		 * like, to avoid descending into a dead-end branch.
1482		 * This tnode is in the parent's child array at index
1483		 * key[p_pos..p_pos+p_bits] but potentially with some bits
1484		 * chopped off, so in reality the index may be just a
1485		 * subprefix, padded with zero at the end.
1486		 * We can also take a look at any skipped bits in this
1487		 * tnode - everything up to p_pos is supposed to be ok,
1488		 * and the non-chopped bits of the index (se previous
1489		 * paragraph) are also guaranteed ok, but the rest is
1490		 * considered unknown.
1491		 *
1492		 * The skipped bits are key[pos+bits..cn->pos].
 
 
1493		 */
 
 
1494
1495		/* If current_prefix_length < pos+bits, we are already doing
1496		 * actual prefix  matching, which means everything from
1497		 * pos+(bits-chopped_off) onward must be zero along some
1498		 * branch of this subtree - otherwise there is *no* valid
1499		 * prefix present. Here we can only check the skipped
1500		 * bits. Remember, since we have already indexed into the
1501		 * parent's child array, we know that the bits we chopped of
1502		 * *are* zero.
1503		 */
 
 
 
 
1504
1505		/* NOTA BENE: Checking only skipped bits
1506		   for the new node here */
 
 
1507
1508		if (current_prefix_length < pos+bits) {
1509			if (tkey_extract_bits(cn->key, current_prefix_length,
1510						cn->pos - current_prefix_length)
1511			    || !(cn->child[0]))
1512				goto backtrace;
1513		}
1514
1515		/*
1516		 * If chopped_off=0, the index is fully validated and we
1517		 * only need to look at the skipped bits for this, the new,
1518		 * tnode. What we actually want to do is to find out if
1519		 * these skipped bits match our key perfectly, or if we will
1520		 * have to count on finding a matching prefix further down,
1521		 * because if we do, we would like to have some way of
1522		 * verifying the existence of such a prefix at this point.
1523		 */
 
 
1524
1525		/* The only thing we can do at this point is to verify that
1526		 * any such matching prefix can indeed be a prefix to our
1527		 * key, and if the bits in the node we are inspecting that
1528		 * do not match our key are not ZERO, this cannot be true.
1529		 * Thus, find out where there is a mismatch (before cn->pos)
1530		 * and verify that all the mismatching bits are zero in the
1531		 * new tnode's key.
1532		 */
1533
1534		/*
1535		 * Note: We aren't very concerned about the piece of
1536		 * the key that precede pn->pos+pn->bits, since these
1537		 * have already been checked. The bits after cn->pos
1538		 * aren't checked since these are by definition
1539		 * "unknown" at this point. Thus, what we want to see
1540		 * is if we are about to enter the "prefix matching"
1541		 * state, and in that case verify that the skipped
1542		 * bits that will prevail throughout this subtree are
1543		 * zero, as they have to be if we are to find a
1544		 * matching prefix.
1545		 */
1546
1547		pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1548
1549		/*
1550		 * In short: If skipped bits in this node do not match
1551		 * the search key, enter the "prefix matching"
1552		 * state.directly.
1553		 */
1554		if (pref_mismatch) {
1555			int mp = KEYLENGTH - fls(pref_mismatch);
1556
1557			if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
1558				goto backtrace;
 
1559
1560			if (current_prefix_length >= cn->pos)
1561				current_prefix_length = mp;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1562		}
 
 
1563
1564		pn = (struct tnode *)n; /* Descend */
1565		chopped_off = 0;
1566		continue;
 
1567
1568backtrace:
1569		chopped_off++;
1570
1571		/* As zero don't change the child key (cindex) */
1572		while ((chopped_off <= pn->bits)
1573		       && !(cindex & (1<<(chopped_off-1))))
1574			chopped_off++;
1575
1576		/* Decrease current_... with bits chopped off */
1577		if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1578			current_prefix_length = pn->pos + pn->bits
1579				- chopped_off;
1580
1581		/*
1582		 * Either we do the actual chop off according or if we have
1583		 * chopped off all bits in this tnode walk up to our parent.
1584		 */
1585
1586		if (chopped_off <= pn->bits) {
1587			cindex &= ~(1 << (chopped_off-1));
1588		} else {
1589			struct tnode *parent = node_parent_rcu((struct rt_trie_node *) pn);
1590			if (!parent)
1591				goto failed;
1592
1593			/* Get Child's index */
1594			cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1595			pn = parent;
1596			chopped_off = 0;
1597
 
 
 
 
 
 
 
 
 
1598#ifdef CONFIG_IP_FIB_TRIE_STATS
1599			t->stats.backtrack++;
1600#endif
1601			goto backtrace;
 
 
1602		}
1603	}
1604failed:
1605	ret = 1;
1606found:
1607	rcu_read_unlock();
1608	return ret;
1609}
1610EXPORT_SYMBOL_GPL(fib_table_lookup);
1611
1612/*
1613 * Remove the leaf and return parent.
1614 */
1615static void trie_leaf_remove(struct trie *t, struct leaf *l)
1616{
1617	struct tnode *tp = node_parent((struct rt_trie_node *) l);
 
 
1618
1619	pr_debug("entering trie_leaf_remove(%p)\n", l);
 
1620
1621	if (tp) {
1622		t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1623		put_child(t, (struct tnode *)tp, cindex, NULL);
 
 
 
 
 
1624		trie_rebalance(t, tp);
1625	} else
1626		RCU_INIT_POINTER(t->trie, NULL);
 
 
 
 
1627
1628	free_leaf(l);
 
 
1629}
1630
1631/*
1632 * Caller must hold RTNL.
1633 */
1634int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
1635{
1636	struct trie *t = (struct trie *) tb->tb_data;
1637	u32 key, mask;
1638	int plen = cfg->fc_dst_len;
1639	u8 tos = cfg->fc_tos;
1640	struct fib_alias *fa, *fa_to_delete;
1641	struct list_head *fa_head;
1642	struct leaf *l;
1643	struct leaf_info *li;
1644
1645	if (plen > 32)
1646		return -EINVAL;
1647
1648	key = ntohl(cfg->fc_dst);
1649	mask = ntohl(inet_make_mask(plen));
1650
1651	if (key & ~mask)
1652		return -EINVAL;
1653
1654	key = key & mask;
1655	l = fib_find_node(t, key);
1656
1657	if (!l)
1658		return -ESRCH;
1659
1660	fa_head = get_fa_head(l, plen);
1661	fa = fib_find_alias(fa_head, tos, 0);
1662
1663	if (!fa)
1664		return -ESRCH;
1665
1666	pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1667
1668	fa_to_delete = NULL;
1669	fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1670	list_for_each_entry_continue(fa, fa_head, fa_list) {
1671		struct fib_info *fi = fa->fa_info;
1672
1673		if (fa->fa_tos != tos)
 
 
1674			break;
1675
1676		if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1677		    (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1678		     fa->fa_info->fib_scope == cfg->fc_scope) &&
1679		    (!cfg->fc_prefsrc ||
1680		     fi->fib_prefsrc == cfg->fc_prefsrc) &&
1681		    (!cfg->fc_protocol ||
1682		     fi->fib_protocol == cfg->fc_protocol) &&
1683		    fib_nh_match(cfg, fi) == 0) {
 
1684			fa_to_delete = fa;
1685			break;
1686		}
1687	}
1688
1689	if (!fa_to_delete)
1690		return -ESRCH;
1691
1692	fa = fa_to_delete;
1693	rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
 
1694		  &cfg->fc_nlinfo, 0);
1695
1696	l = fib_find_node(t, key);
1697	li = find_leaf_info(l, plen);
1698
1699	list_del_rcu(&fa->fa_list);
1700
1701	if (!plen)
1702		tb->tb_num_default--;
1703
1704	if (list_empty(fa_head)) {
1705		hlist_del_rcu(&li->hlist);
1706		free_leaf_info(li);
1707	}
1708
1709	if (hlist_empty(&l->list))
1710		trie_leaf_remove(t, l);
1711
1712	if (fa->fa_state & FA_S_ACCESSED)
1713		rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1714
1715	fib_release_info(fa->fa_info);
1716	alias_free_mem_rcu(fa);
1717	return 0;
1718}
1719
1720static int trie_flush_list(struct list_head *head)
 
1721{
1722	struct fib_alias *fa, *fa_node;
1723	int found = 0;
1724
1725	list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1726		struct fib_info *fi = fa->fa_info;
 
 
 
1727
1728		if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1729			list_del_rcu(&fa->fa_list);
1730			fib_release_info(fa->fa_info);
1731			alias_free_mem_rcu(fa);
1732			found++;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1733		}
 
 
 
 
 
 
 
 
 
 
 
 
 
1734	}
1735	return found;
 
 
 
 
 
 
1736}
1737
1738static int trie_flush_leaf(struct leaf *l)
1739{
1740	int found = 0;
1741	struct hlist_head *lih = &l->list;
1742	struct hlist_node *node, *tmp;
1743	struct leaf_info *li = NULL;
1744
1745	hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
1746		found += trie_flush_list(&li->falh);
1747
1748		if (list_empty(&li->falh)) {
1749			hlist_del_rcu(&li->hlist);
1750			free_leaf_info(li);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1751		}
 
 
 
1752	}
1753	return found;
 
 
 
 
1754}
1755
1756/*
1757 * Scan for the next right leaf starting at node p->child[idx]
1758 * Since we have back pointer, no recursion necessary.
1759 */
1760static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1761{
1762	do {
1763		t_key idx;
 
 
 
 
1764
1765		if (c)
1766			idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1767		else
1768			idx = 0;
 
 
 
 
 
 
 
 
 
 
1769
1770		while (idx < 1u << p->bits) {
1771			c = tnode_get_child_rcu(p, idx++);
1772			if (!c)
1773				continue;
1774
1775			if (IS_LEAF(c)) {
1776				prefetch(rcu_dereference_rtnl(p->child[idx]));
1777				return (struct leaf *) c;
1778			}
1779
1780			/* Rescan start scanning in new node */
1781			p = (struct tnode *) c;
1782			idx = 0;
 
 
 
 
 
 
 
 
1783		}
1784
1785		/* Node empty, walk back up to parent */
1786		c = (struct rt_trie_node *) p;
1787	} while ((p = node_parent_rcu(c)) != NULL);
 
 
1788
1789	return NULL; /* Root of trie */
 
 
 
 
1790}
1791
1792static struct leaf *trie_firstleaf(struct trie *t)
 
1793{
1794	struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
 
 
 
 
1795
1796	if (!n)
1797		return NULL;
 
 
1798
1799	if (IS_LEAF(n))          /* trie is just a leaf */
1800		return (struct leaf *) n;
1801
1802	return leaf_walk_rcu(n, NULL);
1803}
 
1804
1805static struct leaf *trie_nextleaf(struct leaf *l)
1806{
1807	struct rt_trie_node *c = (struct rt_trie_node *) l;
1808	struct tnode *p = node_parent_rcu(c);
 
 
 
1809
1810	if (!p)
1811		return NULL;	/* trie with just one leaf */
1812
1813	return leaf_walk_rcu(p, c);
1814}
 
 
1815
1816static struct leaf *trie_leafindex(struct trie *t, int index)
1817{
1818	struct leaf *l = trie_firstleaf(t);
 
1819
1820	while (l && index-- > 0)
1821		l = trie_nextleaf(l);
1822
1823	return l;
1824}
 
 
 
 
 
 
 
1825
 
 
 
1826
1827/*
1828 * Caller must hold RTNL.
1829 */
1830int fib_table_flush(struct fib_table *tb)
 
 
 
 
 
 
 
 
1831{
1832	struct trie *t = (struct trie *) tb->tb_data;
1833	struct leaf *l, *ll = NULL;
 
 
 
1834	int found = 0;
1835
1836	for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1837		found += trie_flush_leaf(l);
 
 
1838
1839		if (ll && hlist_empty(&ll->list))
1840			trie_leaf_remove(t, ll);
1841		ll = l;
1842	}
 
 
1843
1844	if (ll && hlist_empty(&ll->list))
1845		trie_leaf_remove(t, ll);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1846
1847	pr_debug("trie_flush found=%d\n", found);
1848	return found;
1849}
1850
1851void fib_free_table(struct fib_table *tb)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1852{
1853	kfree(tb);
 
 
 
 
 
 
 
 
1854}
1855
1856static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1857			   struct fib_table *tb,
1858			   struct sk_buff *skb, struct netlink_callback *cb)
1859{
1860	int i, s_i;
1861	struct fib_alias *fa;
1862	__be32 xkey = htonl(key);
1863
1864	s_i = cb->args[5];
1865	i = 0;
1866
1867	/* rcu_read_lock is hold by caller */
 
1868
1869	list_for_each_entry_rcu(fa, fah, fa_list) {
1870		if (i < s_i) {
1871			i++;
 
1872			continue;
1873		}
1874
1875		if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1876				  cb->nlh->nlmsg_seq,
1877				  RTM_NEWROUTE,
1878				  tb->tb_id,
1879				  fa->fa_type,
1880				  xkey,
1881				  plen,
1882				  fa->fa_tos,
1883				  fa->fa_info, NLM_F_MULTI) < 0) {
1884			cb->args[5] = i;
1885			return -1;
1886		}
1887		i++;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1888	}
1889	cb->args[5] = i;
1890	return skb->len;
1891}
1892
1893static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1894			struct sk_buff *skb, struct netlink_callback *cb)
1895{
1896	struct leaf_info *li;
1897	struct hlist_node *node;
1898	int i, s_i;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1899
1900	s_i = cb->args[4];
 
1901	i = 0;
1902
1903	/* rcu_read_lock is hold by caller */
1904	hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
1905		if (i < s_i) {
1906			i++;
1907			continue;
1908		}
1909
1910		if (i > s_i)
1911			cb->args[5] = 0;
1912
1913		if (list_empty(&li->falh))
1914			continue;
 
 
1915
1916		if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1917			cb->args[4] = i;
1918			return -1;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1919		}
 
 
 
 
 
 
 
 
 
1920		i++;
1921	}
1922
1923	cb->args[4] = i;
1924	return skb->len;
 
 
 
 
 
1925}
1926
 
1927int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
1928		   struct netlink_callback *cb)
1929{
1930	struct leaf *l;
1931	struct trie *t = (struct trie *) tb->tb_data;
1932	t_key key = cb->args[2];
1933	int count = cb->args[3];
1934
1935	rcu_read_lock();
1936	/* Dump starting at last key.
1937	 * Note: 0.0.0.0/0 (ie default) is first key.
1938	 */
1939	if (count == 0)
1940		l = trie_firstleaf(t);
1941	else {
1942		/* Normally, continue from last key, but if that is missing
1943		 * fallback to using slow rescan
1944		 */
1945		l = fib_find_node(t, key);
1946		if (!l)
1947			l = trie_leafindex(t, count);
1948	}
1949
1950	while (l) {
1951		cb->args[2] = l->key;
1952		if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1953			cb->args[3] = count;
1954			rcu_read_unlock();
1955			return -1;
1956		}
1957
1958		++count;
1959		l = trie_nextleaf(l);
 
1960		memset(&cb->args[4], 0,
1961		       sizeof(cb->args) - 4*sizeof(cb->args[0]));
 
 
 
 
1962	}
1963	cb->args[3] = count;
1964	rcu_read_unlock();
 
1965
1966	return skb->len;
1967}
1968
1969void __init fib_trie_init(void)
1970{
1971	fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1972					  sizeof(struct fib_alias),
1973					  0, SLAB_PANIC, NULL);
1974
1975	trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1976					   max(sizeof(struct leaf),
1977					       sizeof(struct leaf_info)),
1978					   0, SLAB_PANIC, NULL);
1979}
1980
1981
1982struct fib_table *fib_trie_table(u32 id)
1983{
1984	struct fib_table *tb;
1985	struct trie *t;
 
 
 
 
1986
1987	tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1988		     GFP_KERNEL);
1989	if (tb == NULL)
1990		return NULL;
1991
1992	tb->tb_id = id;
1993	tb->tb_default = -1;
1994	tb->tb_num_default = 0;
 
 
 
 
1995
1996	t = (struct trie *) tb->tb_data;
1997	memset(t, 0, sizeof(*t));
 
 
 
 
 
 
 
 
1998
1999	return tb;
2000}
2001
2002#ifdef CONFIG_PROC_FS
2003/* Depth first Trie walk iterator */
2004struct fib_trie_iter {
2005	struct seq_net_private p;
2006	struct fib_table *tb;
2007	struct tnode *tnode;
2008	unsigned int index;
2009	unsigned int depth;
2010};
2011
2012static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
2013{
2014	struct tnode *tn = iter->tnode;
2015	unsigned int cindex = iter->index;
2016	struct tnode *p;
2017
2018	/* A single entry routing table */
2019	if (!tn)
2020		return NULL;
2021
2022	pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2023		 iter->tnode, iter->index, iter->depth);
2024rescan:
2025	while (cindex < (1<<tn->bits)) {
2026		struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
2027
2028		if (n) {
 
 
 
 
 
 
2029			if (IS_LEAF(n)) {
2030				iter->tnode = tn;
2031				iter->index = cindex + 1;
2032			} else {
2033				/* push down one level */
2034				iter->tnode = (struct tnode *) n;
2035				iter->index = 0;
2036				++iter->depth;
2037			}
 
2038			return n;
2039		}
2040
2041		++cindex;
2042	}
2043
2044	/* Current node exhausted, pop back up */
2045	p = node_parent_rcu((struct rt_trie_node *)tn);
2046	if (p) {
2047		cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2048		tn = p;
2049		--iter->depth;
2050		goto rescan;
2051	}
2052
2053	/* got root? */
 
 
 
2054	return NULL;
2055}
2056
2057static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
2058				       struct trie *t)
2059{
2060	struct rt_trie_node *n;
2061
2062	if (!t)
2063		return NULL;
2064
2065	n = rcu_dereference(t->trie);
 
2066	if (!n)
2067		return NULL;
2068
2069	if (IS_TNODE(n)) {
2070		iter->tnode = (struct tnode *) n;
2071		iter->index = 0;
2072		iter->depth = 1;
2073	} else {
2074		iter->tnode = NULL;
2075		iter->index = 0;
2076		iter->depth = 0;
2077	}
2078
2079	return n;
2080}
2081
2082static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2083{
2084	struct rt_trie_node *n;
2085	struct fib_trie_iter iter;
2086
2087	memset(s, 0, sizeof(*s));
2088
2089	rcu_read_lock();
2090	for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2091		if (IS_LEAF(n)) {
2092			struct leaf *l = (struct leaf *)n;
2093			struct leaf_info *li;
2094			struct hlist_node *tmp;
2095
2096			s->leaves++;
2097			s->totdepth += iter.depth;
2098			if (iter.depth > s->maxdepth)
2099				s->maxdepth = iter.depth;
2100
2101			hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
2102				++s->prefixes;
2103		} else {
2104			const struct tnode *tn = (const struct tnode *) n;
2105			int i;
2106
2107			s->tnodes++;
2108			if (tn->bits < MAX_STAT_DEPTH)
2109				s->nodesizes[tn->bits]++;
2110
2111			for (i = 0; i < (1<<tn->bits); i++)
2112				if (!tn->child[i])
2113					s->nullpointers++;
2114		}
2115	}
2116	rcu_read_unlock();
2117}
2118
2119/*
2120 *	This outputs /proc/net/fib_triestats
2121 */
2122static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2123{
2124	unsigned int i, max, pointers, bytes, avdepth;
2125
2126	if (stat->leaves)
2127		avdepth = stat->totdepth*100 / stat->leaves;
2128	else
2129		avdepth = 0;
2130
2131	seq_printf(seq, "\tAver depth:     %u.%02d\n",
2132		   avdepth / 100, avdepth % 100);
2133	seq_printf(seq, "\tMax depth:      %u\n", stat->maxdepth);
2134
2135	seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
2136	bytes = sizeof(struct leaf) * stat->leaves;
2137
2138	seq_printf(seq, "\tPrefixes:       %u\n", stat->prefixes);
2139	bytes += sizeof(struct leaf_info) * stat->prefixes;
2140
2141	seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2142	bytes += sizeof(struct tnode) * stat->tnodes;
2143
2144	max = MAX_STAT_DEPTH;
2145	while (max > 0 && stat->nodesizes[max-1] == 0)
2146		max--;
2147
2148	pointers = 0;
2149	for (i = 1; i <= max; i++)
2150		if (stat->nodesizes[i] != 0) {
2151			seq_printf(seq, "  %u: %u",  i, stat->nodesizes[i]);
2152			pointers += (1<<i) * stat->nodesizes[i];
2153		}
2154	seq_putc(seq, '\n');
2155	seq_printf(seq, "\tPointers: %u\n", pointers);
2156
2157	bytes += sizeof(struct rt_trie_node *) * pointers;
2158	seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2159	seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
2160}
2161
2162#ifdef CONFIG_IP_FIB_TRIE_STATS
2163static void trie_show_usage(struct seq_file *seq,
2164			    const struct trie_use_stats *stats)
2165{
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2166	seq_printf(seq, "\nCounters:\n---------\n");
2167	seq_printf(seq, "gets = %u\n", stats->gets);
2168	seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2169	seq_printf(seq, "semantic match passed = %u\n",
2170		   stats->semantic_match_passed);
2171	seq_printf(seq, "semantic match miss = %u\n",
2172		   stats->semantic_match_miss);
2173	seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2174	seq_printf(seq, "skipped node resize = %u\n\n",
2175		   stats->resize_node_skipped);
2176}
2177#endif /*  CONFIG_IP_FIB_TRIE_STATS */
2178
2179static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2180{
2181	if (tb->tb_id == RT_TABLE_LOCAL)
2182		seq_puts(seq, "Local:\n");
2183	else if (tb->tb_id == RT_TABLE_MAIN)
2184		seq_puts(seq, "Main:\n");
2185	else
2186		seq_printf(seq, "Id %d:\n", tb->tb_id);
2187}
2188
2189
2190static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2191{
2192	struct net *net = (struct net *)seq->private;
2193	unsigned int h;
2194
2195	seq_printf(seq,
2196		   "Basic info: size of leaf:"
2197		   " %Zd bytes, size of tnode: %Zd bytes.\n",
2198		   sizeof(struct leaf), sizeof(struct tnode));
2199
2200	for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2201		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2202		struct hlist_node *node;
2203		struct fib_table *tb;
2204
2205		hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2206			struct trie *t = (struct trie *) tb->tb_data;
2207			struct trie_stat stat;
2208
2209			if (!t)
2210				continue;
2211
2212			fib_table_print(seq, tb);
2213
2214			trie_collect_stats(t, &stat);
2215			trie_show_stats(seq, &stat);
2216#ifdef CONFIG_IP_FIB_TRIE_STATS
2217			trie_show_usage(seq, &t->stats);
2218#endif
2219		}
2220	}
2221
2222	return 0;
2223}
2224
2225static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2226{
2227	return single_open_net(inode, file, fib_triestat_seq_show);
2228}
2229
2230static const struct file_operations fib_triestat_fops = {
2231	.owner	= THIS_MODULE,
2232	.open	= fib_triestat_seq_open,
2233	.read	= seq_read,
2234	.llseek	= seq_lseek,
2235	.release = single_release_net,
2236};
2237
2238static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2239{
2240	struct fib_trie_iter *iter = seq->private;
2241	struct net *net = seq_file_net(seq);
2242	loff_t idx = 0;
2243	unsigned int h;
2244
2245	for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2246		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2247		struct hlist_node *node;
2248		struct fib_table *tb;
2249
2250		hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2251			struct rt_trie_node *n;
2252
2253			for (n = fib_trie_get_first(iter,
2254						    (struct trie *) tb->tb_data);
2255			     n; n = fib_trie_get_next(iter))
2256				if (pos == idx++) {
2257					iter->tb = tb;
2258					return n;
2259				}
2260		}
2261	}
2262
2263	return NULL;
2264}
2265
2266static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2267	__acquires(RCU)
2268{
2269	rcu_read_lock();
2270	return fib_trie_get_idx(seq, *pos);
2271}
2272
2273static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2274{
2275	struct fib_trie_iter *iter = seq->private;
2276	struct net *net = seq_file_net(seq);
2277	struct fib_table *tb = iter->tb;
2278	struct hlist_node *tb_node;
2279	unsigned int h;
2280	struct rt_trie_node *n;
2281
2282	++*pos;
2283	/* next node in same table */
2284	n = fib_trie_get_next(iter);
2285	if (n)
2286		return n;
2287
2288	/* walk rest of this hash chain */
2289	h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2290	while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2291		tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2292		n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2293		if (n)
2294			goto found;
2295	}
2296
2297	/* new hash chain */
2298	while (++h < FIB_TABLE_HASHSZ) {
2299		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2300		hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) {
2301			n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2302			if (n)
2303				goto found;
2304		}
2305	}
2306	return NULL;
2307
2308found:
2309	iter->tb = tb;
2310	return n;
2311}
2312
2313static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2314	__releases(RCU)
2315{
2316	rcu_read_unlock();
2317}
2318
2319static void seq_indent(struct seq_file *seq, int n)
2320{
2321	while (n-- > 0)
2322		seq_puts(seq, "   ");
2323}
2324
2325static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2326{
2327	switch (s) {
2328	case RT_SCOPE_UNIVERSE: return "universe";
2329	case RT_SCOPE_SITE:	return "site";
2330	case RT_SCOPE_LINK:	return "link";
2331	case RT_SCOPE_HOST:	return "host";
2332	case RT_SCOPE_NOWHERE:	return "nowhere";
2333	default:
2334		snprintf(buf, len, "scope=%d", s);
2335		return buf;
2336	}
2337}
2338
2339static const char *const rtn_type_names[__RTN_MAX] = {
2340	[RTN_UNSPEC] = "UNSPEC",
2341	[RTN_UNICAST] = "UNICAST",
2342	[RTN_LOCAL] = "LOCAL",
2343	[RTN_BROADCAST] = "BROADCAST",
2344	[RTN_ANYCAST] = "ANYCAST",
2345	[RTN_MULTICAST] = "MULTICAST",
2346	[RTN_BLACKHOLE] = "BLACKHOLE",
2347	[RTN_UNREACHABLE] = "UNREACHABLE",
2348	[RTN_PROHIBIT] = "PROHIBIT",
2349	[RTN_THROW] = "THROW",
2350	[RTN_NAT] = "NAT",
2351	[RTN_XRESOLVE] = "XRESOLVE",
2352};
2353
2354static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2355{
2356	if (t < __RTN_MAX && rtn_type_names[t])
2357		return rtn_type_names[t];
2358	snprintf(buf, len, "type %u", t);
2359	return buf;
2360}
2361
2362/* Pretty print the trie */
2363static int fib_trie_seq_show(struct seq_file *seq, void *v)
2364{
2365	const struct fib_trie_iter *iter = seq->private;
2366	struct rt_trie_node *n = v;
2367
2368	if (!node_parent_rcu(n))
2369		fib_table_print(seq, iter->tb);
2370
2371	if (IS_TNODE(n)) {
2372		struct tnode *tn = (struct tnode *) n;
2373		__be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2374
2375		seq_indent(seq, iter->depth-1);
2376		seq_printf(seq, "  +-- %pI4/%d %d %d %d\n",
2377			   &prf, tn->pos, tn->bits, tn->full_children,
2378			   tn->empty_children);
2379
2380	} else {
2381		struct leaf *l = (struct leaf *) n;
2382		struct leaf_info *li;
2383		struct hlist_node *node;
2384		__be32 val = htonl(l->key);
2385
2386		seq_indent(seq, iter->depth);
2387		seq_printf(seq, "  |-- %pI4\n", &val);
2388
2389		hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2390			struct fib_alias *fa;
2391
2392			list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2393				char buf1[32], buf2[32];
2394
2395				seq_indent(seq, iter->depth+1);
2396				seq_printf(seq, "  /%d %s %s", li->plen,
2397					   rtn_scope(buf1, sizeof(buf1),
2398						     fa->fa_info->fib_scope),
2399					   rtn_type(buf2, sizeof(buf2),
2400						    fa->fa_type));
2401				if (fa->fa_tos)
2402					seq_printf(seq, " tos=%d", fa->fa_tos);
2403				seq_putc(seq, '\n');
2404			}
2405		}
2406	}
2407
2408	return 0;
2409}
2410
2411static const struct seq_operations fib_trie_seq_ops = {
2412	.start  = fib_trie_seq_start,
2413	.next   = fib_trie_seq_next,
2414	.stop   = fib_trie_seq_stop,
2415	.show   = fib_trie_seq_show,
2416};
2417
2418static int fib_trie_seq_open(struct inode *inode, struct file *file)
2419{
2420	return seq_open_net(inode, file, &fib_trie_seq_ops,
2421			    sizeof(struct fib_trie_iter));
2422}
2423
2424static const struct file_operations fib_trie_fops = {
2425	.owner  = THIS_MODULE,
2426	.open   = fib_trie_seq_open,
2427	.read   = seq_read,
2428	.llseek = seq_lseek,
2429	.release = seq_release_net,
2430};
2431
2432struct fib_route_iter {
2433	struct seq_net_private p;
2434	struct trie *main_trie;
 
2435	loff_t	pos;
2436	t_key	key;
2437};
2438
2439static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
 
2440{
2441	struct leaf *l = NULL;
2442	struct trie *t = iter->main_trie;
2443
2444	/* use cache location of last found key */
2445	if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2446		pos -= iter->pos;
2447	else {
2448		iter->pos = 0;
2449		l = trie_firstleaf(t);
2450	}
2451
2452	while (l && pos-- > 0) {
 
 
 
2453		iter->pos++;
2454		l = trie_nextleaf(l);
 
 
 
 
2455	}
2456
2457	if (l)
2458		iter->key = pos;	/* remember it */
2459	else
2460		iter->pos = 0;		/* forget it */
2461
2462	return l;
2463}
2464
2465static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2466	__acquires(RCU)
2467{
2468	struct fib_route_iter *iter = seq->private;
2469	struct fib_table *tb;
 
2470
2471	rcu_read_lock();
 
2472	tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2473	if (!tb)
2474		return NULL;
2475
2476	iter->main_trie = (struct trie *) tb->tb_data;
2477	if (*pos == 0)
2478		return SEQ_START_TOKEN;
2479	else
2480		return fib_route_get_idx(iter, *pos - 1);
 
 
 
 
 
 
2481}
2482
2483static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2484{
2485	struct fib_route_iter *iter = seq->private;
2486	struct leaf *l = v;
 
2487
2488	++*pos;
2489	if (v == SEQ_START_TOKEN) {
2490		iter->pos = 0;
2491		l = trie_firstleaf(iter->main_trie);
2492	} else {
2493		iter->pos++;
2494		l = trie_nextleaf(l);
2495	}
2496
2497	if (l)
 
 
 
 
2498		iter->key = l->key;
2499	else
 
2500		iter->pos = 0;
 
 
2501	return l;
2502}
2503
2504static void fib_route_seq_stop(struct seq_file *seq, void *v)
2505	__releases(RCU)
2506{
2507	rcu_read_unlock();
2508}
2509
2510static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2511{
2512	unsigned int flags = 0;
2513
2514	if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
2515		flags = RTF_REJECT;
2516	if (fi && fi->fib_nh->nh_gw)
2517		flags |= RTF_GATEWAY;
 
 
 
 
2518	if (mask == htonl(0xFFFFFFFF))
2519		flags |= RTF_HOST;
2520	flags |= RTF_UP;
2521	return flags;
2522}
2523
2524/*
2525 *	This outputs /proc/net/route.
2526 *	The format of the file is not supposed to be changed
2527 *	and needs to be same as fib_hash output to avoid breaking
2528 *	legacy utilities
2529 */
2530static int fib_route_seq_show(struct seq_file *seq, void *v)
2531{
2532	struct leaf *l = v;
2533	struct leaf_info *li;
2534	struct hlist_node *node;
 
 
2535
2536	if (v == SEQ_START_TOKEN) {
2537		seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2538			   "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2539			   "\tWindow\tIRTT");
2540		return 0;
2541	}
2542
2543	hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2544		struct fib_alias *fa;
2545		__be32 mask, prefix;
2546
2547		mask = inet_make_mask(li->plen);
2548		prefix = htonl(l->key);
 
 
2549
2550		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2551			const struct fib_info *fi = fa->fa_info;
2552			unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2553			int len;
2554
2555			if (fa->fa_type == RTN_BROADCAST
2556			    || fa->fa_type == RTN_MULTICAST)
2557				continue;
2558
2559			if (fi)
2560				seq_printf(seq,
2561					 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2562					 "%d\t%08X\t%d\t%u\t%u%n",
2563					 fi->fib_dev ? fi->fib_dev->name : "*",
2564					 prefix,
2565					 fi->fib_nh->nh_gw, flags, 0, 0,
2566					 fi->fib_priority,
2567					 mask,
2568					 (fi->fib_advmss ?
2569					  fi->fib_advmss + 40 : 0),
2570					 fi->fib_window,
2571					 fi->fib_rtt >> 3, &len);
2572			else
2573				seq_printf(seq,
2574					 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2575					 "%d\t%08X\t%d\t%u\t%u%n",
2576					 prefix, 0, flags, 0, 0, 0,
2577					 mask, 0, 0, 0, &len);
2578
2579			seq_printf(seq, "%*s\n", 127 - len, "");
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2580		}
 
2581	}
2582
2583	return 0;
2584}
2585
2586static const struct seq_operations fib_route_seq_ops = {
2587	.start  = fib_route_seq_start,
2588	.next   = fib_route_seq_next,
2589	.stop   = fib_route_seq_stop,
2590	.show   = fib_route_seq_show,
2591};
2592
2593static int fib_route_seq_open(struct inode *inode, struct file *file)
2594{
2595	return seq_open_net(inode, file, &fib_route_seq_ops,
2596			    sizeof(struct fib_route_iter));
2597}
2598
2599static const struct file_operations fib_route_fops = {
2600	.owner  = THIS_MODULE,
2601	.open   = fib_route_seq_open,
2602	.read   = seq_read,
2603	.llseek = seq_lseek,
2604	.release = seq_release_net,
2605};
2606
2607int __net_init fib_proc_init(struct net *net)
2608{
2609	if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
 
2610		goto out1;
2611
2612	if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
2613				  &fib_triestat_fops))
2614		goto out2;
2615
2616	if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
 
2617		goto out3;
2618
2619	return 0;
2620
2621out3:
2622	proc_net_remove(net, "fib_triestat");
2623out2:
2624	proc_net_remove(net, "fib_trie");
2625out1:
2626	return -ENOMEM;
2627}
2628
2629void __net_exit fib_proc_exit(struct net *net)
2630{
2631	proc_net_remove(net, "fib_trie");
2632	proc_net_remove(net, "fib_triestat");
2633	proc_net_remove(net, "route");
2634}
2635
2636#endif /* CONFIG_PROC_FS */