net/ipv4/fib_trie.c

   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
  89 typedef 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
  99 struct rt_trie_node {
 100         unsigned long parent;
 101         t_key key;
 102 };
 103
 104 struct leaf {
 105         unsigned long parent;
 106         t_key key;
 107         struct hlist_head list;
 108         struct rcu_head rcu;
 109 };
 110
 111 struct 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
 119 struct 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
 135 struct 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
 145 struct 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
 155 struct 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
 162 static void put_child(struct trie *t, struct tnode *tn, int i, struct rt_trie_node *n);
 163 static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
 164                                   int wasfull);
 165 static struct rt_trie_node *resize(struct trie *t, struct tnode *tn);
 166 static struct tnode *inflate(struct trie *t, struct tnode *tn);
 167 static struct tnode *halve(struct trie *t, struct tnode *tn);
 168 /* tnodes to free after resize(); protected by RTNL */
 169 static struct tnode *tnode_free_head;
 170 static 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  */
 177 static const int sync_pages = 128;
 178
 179 static struct kmem_cache *fn_alias_kmem __read_mostly;
 180 static struct kmem_cache *trie_leaf_kmem __read_mostly;
 181
 182 /*
 183  * caller must hold RTNL
 184  */
 185 static 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  */
 197 static 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  */
 210 static 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  */
 219 static 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  */
 229 static 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
 236 static inline int tnode_child_length(const struct tnode *tn)
 237 {
 238         return 1 << tn->bits;
 239 }
 240
 241 static inline t_key mask_pfx(t_key k, unsigned int l)
 242 {
 243         return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
 244 }
 245
 246 static 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
 254 static inline int tkey_equals(t_key a, t_key b)
 255 {
 256         return a == b;
 257 }
 258
 259 static 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
 267 static 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
 342 static inline void check_tnode(const struct tnode *tn)
 343 {
 344         WARN_ON(tn && tn->pos+tn->bits > 32);
 345 }
 346
 347 static const int halve_threshold = 25;
 348 static const int inflate_threshold = 50;
 349 static const int halve_threshold_root = 15;
 350 static const int inflate_threshold_root = 30;
 351
 352 static 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
 358 static inline void alias_free_mem_rcu(struct fib_alias *fa)
 359 {
 360         call_rcu(&fa->rcu, __alias_free_mem);
 361 }
 362
 363 static 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
 369 static inline void free_leaf(struct leaf *l)
 370 {
 371         call_rcu_bh(&l->rcu, __leaf_free_rcu);
 372 }
 373
 374 static inline void free_leaf_info(struct leaf_info *leaf)
 375 {
 376         kfree_rcu(leaf, rcu);
 377 }
 378
 379 static struct tnode *tnode_alloc(size_t size)
 380 {
 381         if (size <= PAGE_SIZE)
 382                 return kzalloc(size, GFP_KERNEL);
 383         else
 384                 return vzalloc(size);
 385 }
 386
 387 static void __tnode_vfree(struct work_struct *arg)
 388 {
 389         struct tnode *tn = container_of(arg, struct tnode, work);
 390         vfree(tn);
 391 }
 392
 393 static 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
 407 static 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
 415 static 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
 424 static 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
 440 static 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
 450 static 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
 461 static struct tnode *tnode_new(t_key key, int pos, int bits)
 462 {
 463         size_t sz = sizeof(struct tnode) + (sizeof(struct rt_trie_node *) << bits);
 464         struct tnode *tn = tnode_alloc(sz);
 465
 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
 485 static inline int tnode_full(const struct tnode *tn, const struct rt_trie_node *n)
 486 {
 487         if (n == NULL || IS_LEAF(n))
 488                 return 0;
 489
 490         return ((struct tnode *) n)->pos == tn->pos + tn->bits;
 491 }
 492
 493 static 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
 504 static 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
 535 static 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) {
 681 one_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
 700 static 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
 713 static 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;
 841 nomem:
 842         tnode_clean_free(tn);
 843         return ERR_PTR(-ENOMEM);
 844 }
 845
 846 static struct tnode *halve(struct trie *t, struct tnode *tn)
 847 {
 848         struct tnode *oldtnode = tn;
 849         struct rt_trie_node *left, *right;
 850         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;
 913 nomem:
 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
 921 static 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
 934 static 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
 944 static 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
 967 static struct leaf *
 968 fib_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
 999 static 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, tn);
1011
1012                 tnode_put_child_reorg(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, 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
1035 static 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, 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, tp, cindex, (struct rt_trie_node *)tn);
1164                 } else {
1165                         rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1166                         tp = tn;
1167                 }
1168         }
1169
1170         if (tp && tp->pos + tp->bits > 32)
1171                 pr_warn("fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1172                         tp, tp->pos, tp->bits, key, plen);
1173
1174         /* Rebalance the trie */
1175
1176         trie_rebalance(t, tp);
1177 done:
1178         return fa_head;
1179 }
1180
1181 /*
1182  * Caller must hold RTNL.
1183  */
1184 int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
1185 {
1186         struct trie *t = (struct trie *) tb->tb_data;
1187         struct fib_alias *fa, *new_fa;
1188         struct list_head *fa_head = NULL;
1189         struct fib_info *fi;
1190         int plen = cfg->fc_dst_len;
1191         u8 tos = cfg->fc_tos;
1192         u32 key, mask;
1193         int err;
1194         struct leaf *l;
1195
1196         if (plen > 32)
1197                 return -EINVAL;
1198
1199         key = ntohl(cfg->fc_dst);
1200
1201         pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1202
1203         mask = ntohl(inet_make_mask(plen));
1204
1205         if (key & ~mask)
1206                 return -EINVAL;
1207
1208         key = key & mask;
1209
1210         fi = fib_create_info(cfg);
1211         if (IS_ERR(fi)) {
1212                 err = PTR_ERR(fi);
1213                 goto err;
1214         }
1215
1216         l = fib_find_node(t, key);
1217         fa = NULL;
1218
1219         if (l) {
1220                 fa_head = get_fa_head(l, plen);
1221                 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1222         }
1223
1224         /* Now fa, if non-NULL, points to the first fib alias
1225          * with the same keys [prefix,tos,priority], if such key already
1226          * exists or to the node before which we will insert new one.
1227          *
1228          * If fa is NULL, we will need to allocate a new one and
1229          * insert to the head of f.
1230          *
1231          * If f is NULL, no fib node matched the destination key
1232          * and we need to allocate a new one of those as well.
1233          */
1234
1235         if (fa && fa->fa_tos == tos &&
1236             fa->fa_info->fib_priority == fi->fib_priority) {
1237                 struct fib_alias *fa_first, *fa_match;
1238
1239                 err = -EEXIST;
1240                 if (cfg->fc_nlflags & NLM_F_EXCL)
1241                         goto out;
1242
1243                 /* We have 2 goals:
1244                  * 1. Find exact match for type, scope, fib_info to avoid
1245                  * duplicate routes
1246                  * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1247                  */
1248                 fa_match = NULL;
1249                 fa_first = fa;
1250                 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1251                 list_for_each_entry_continue(fa, fa_head, fa_list) {
1252                         if (fa->fa_tos != tos)
1253                                 break;
1254                         if (fa->fa_info->fib_priority != fi->fib_priority)
1255                                 break;
1256                         if (fa->fa_type == cfg->fc_type &&
1257                             fa->fa_info == fi) {
1258                                 fa_match = fa;
1259                                 break;
1260                         }
1261                 }
1262
1263                 if (cfg->fc_nlflags & NLM_F_REPLACE) {
1264                         struct fib_info *fi_drop;
1265                         u8 state;
1266
1267                         fa = fa_first;
1268                         if (fa_match) {
1269                                 if (fa == fa_match)
1270                                         err = 0;
1271                                 goto out;
1272                         }
1273                         err = -ENOBUFS;
1274                         new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1275                         if (new_fa == NULL)
1276                                 goto out;
1277
1278                         fi_drop = fa->fa_info;
1279                         new_fa->fa_tos = fa->fa_tos;
1280                         new_fa->fa_info = fi;
1281                         new_fa->fa_type = cfg->fc_type;
1282                         state = fa->fa_state;
1283                         new_fa->fa_state = state & ~FA_S_ACCESSED;
1284
1285                         list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1286                         alias_free_mem_rcu(fa);
1287
1288                         fib_release_info(fi_drop);
1289                         if (state & FA_S_ACCESSED)
1290                                 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1291                         rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1292                                 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1293
1294                         goto succeeded;
1295                 }
1296                 /* Error if we find a perfect match which
1297                  * uses the same scope, type, and nexthop
1298                  * information.
1299                  */
1300                 if (fa_match)
1301                         goto out;
1302
1303                 if (!(cfg->fc_nlflags & NLM_F_APPEND))
1304                         fa = fa_first;
1305         }
1306         err = -ENOENT;
1307         if (!(cfg->fc_nlflags & NLM_F_CREATE))
1308                 goto out;
1309
1310         err = -ENOBUFS;
1311         new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1312         if (new_fa == NULL)
1313                 goto out;
1314
1315         new_fa->fa_info = fi;
1316         new_fa->fa_tos = tos;
1317         new_fa->fa_type = cfg->fc_type;
1318         new_fa->fa_state = 0;
1319         /*
1320          * Insert new entry to the list.
1321          */
1322
1323         if (!fa_head) {
1324                 fa_head = fib_insert_node(t, key, plen);
1325                 if (unlikely(!fa_head)) {
1326                         err = -ENOMEM;
1327                         goto out_free_new_fa;
1328                 }
1329         }
1330
1331         if (!plen)
1332                 tb->tb_num_default++;
1333
1334         list_add_tail_rcu(&new_fa->fa_list,
1335                           (fa ? &fa->fa_list : fa_head));
1336
1337         rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1338         rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1339                   &cfg->fc_nlinfo, 0);
1340 succeeded:
1341         return 0;
1342
1343 out_free_new_fa:
1344         kmem_cache_free(fn_alias_kmem, new_fa);
1345 out:
1346         fib_release_info(fi);
1347 err:
1348         return err;
1349 }
1350
1351 /* should be called with rcu_read_lock */
1352 static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
1353                       t_key key,  const struct flowi4 *flp,
1354                       struct fib_result *res, int fib_flags)
1355 {
1356         struct leaf_info *li;
1357         struct hlist_head *hhead = &l->list;
1358         struct hlist_node *node;
1359
1360         hlist_for_each_entry_rcu(li, node, hhead, hlist) {
1361                 struct fib_alias *fa;
1362
1363                 if (l->key != (key & li->mask_plen))
1364                         continue;
1365
1366                 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
1367                         struct fib_info *fi = fa->fa_info;
1368                         int nhsel, err;
1369
1370                         if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1371                                 continue;
1372                         if (fi->fib_dead)
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
1418 int 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
1567 backtrace:
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         }
1603 failed:
1604         ret = 1;
1605 found:
1606         rcu_read_unlock();
1607         return ret;
1608 }
1609 EXPORT_SYMBOL_GPL(fib_table_lookup);
1610
1611 /*
1612  * Remove the leaf and return parent.
1613  */
1614 static void trie_leaf_remove(struct trie *t, struct leaf *l)
1615 {
1616         struct tnode *tp = node_parent((struct rt_trie_node *) l);
1617
1618         pr_debug("entering trie_leaf_remove(%p)\n", l);
1619
1620         if (tp) {
1621                 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1622                 put_child(t, tp, cindex, NULL);
1623                 trie_rebalance(t, tp);
1624         } else
1625                 RCU_INIT_POINTER(t->trie, NULL);
1626
1627         free_leaf(l);
1628 }
1629
1630 /*
1631  * Caller must hold RTNL.
1632  */
1633 int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
1634 {
1635         struct trie *t = (struct trie *) tb->tb_data;
1636         u32 key, mask;
1637         int plen = cfg->fc_dst_len;
1638         u8 tos = cfg->fc_tos;
1639         struct fib_alias *fa, *fa_to_delete;
1640         struct list_head *fa_head;
1641         struct leaf *l;
1642         struct leaf_info *li;
1643
1644         if (plen > 32)
1645                 return -EINVAL;
1646
1647         key = ntohl(cfg->fc_dst);
1648         mask = ntohl(inet_make_mask(plen));
1649
1650         if (key & ~mask)
1651                 return -EINVAL;
1652
1653         key = key & mask;
1654         l = fib_find_node(t, key);
1655
1656         if (!l)
1657                 return -ESRCH;
1658
1659         fa_head = get_fa_head(l, plen);
1660         fa = fib_find_alias(fa_head, tos, 0);
1661
1662         if (!fa)
1663                 return -ESRCH;
1664
1665         pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1666
1667         fa_to_delete = NULL;
1668         fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1669         list_for_each_entry_continue(fa, fa_head, fa_list) {
1670                 struct fib_info *fi = fa->fa_info;
1671
1672                 if (fa->fa_tos != tos)
1673                         break;
1674
1675                 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1676                     (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1677                      fa->fa_info->fib_scope == cfg->fc_scope) &&
1678                     (!cfg->fc_prefsrc ||
1679                      fi->fib_prefsrc == cfg->fc_prefsrc) &&
1680                     (!cfg->fc_protocol ||
1681                      fi->fib_protocol == cfg->fc_protocol) &&
1682                     fib_nh_match(cfg, fi) == 0) {
1683                         fa_to_delete = fa;
1684                         break;
1685                 }
1686         }
1687
1688         if (!fa_to_delete)
1689                 return -ESRCH;
1690
1691         fa = fa_to_delete;
1692         rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1693                   &cfg->fc_nlinfo, 0);
1694
1695         l = fib_find_node(t, key);
1696         li = find_leaf_info(l, plen);
1697
1698         list_del_rcu(&fa->fa_list);
1699
1700         if (!plen)
1701                 tb->tb_num_default--;
1702
1703         if (list_empty(fa_head)) {
1704                 hlist_del_rcu(&li->hlist);
1705                 free_leaf_info(li);
1706         }
1707
1708         if (hlist_empty(&l->list))
1709                 trie_leaf_remove(t, l);
1710
1711         if (fa->fa_state & FA_S_ACCESSED)
1712                 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
1713
1714         fib_release_info(fa->fa_info);
1715         alias_free_mem_rcu(fa);
1716         return 0;
1717 }
1718
1719 static int trie_flush_list(struct list_head *head)
1720 {
1721         struct fib_alias *fa, *fa_node;
1722         int found = 0;
1723
1724         list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1725                 struct fib_info *fi = fa->fa_info;
1726
1727                 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1728                         list_del_rcu(&fa->fa_list);
1729                         fib_release_info(fa->fa_info);
1730                         alias_free_mem_rcu(fa);
1731                         found++;
1732                 }
1733         }
1734         return found;
1735 }
1736
1737 static int trie_flush_leaf(struct leaf *l)
1738 {
1739         int found = 0;
1740         struct hlist_head *lih = &l->list;
1741         struct hlist_node *node, *tmp;
1742         struct leaf_info *li = NULL;
1743
1744         hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
1745                 found += trie_flush_list(&li->falh);
1746
1747                 if (list_empty(&li->falh)) {
1748                         hlist_del_rcu(&li->hlist);
1749                         free_leaf_info(li);
1750                 }
1751         }
1752         return found;
1753 }
1754
1755 /*
1756  * Scan for the next right leaf starting at node p->child[idx]
1757  * Since we have back pointer, no recursion necessary.
1758  */
1759 static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1760 {
1761         do {
1762                 t_key idx;
1763
1764                 if (c)
1765                         idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1766                 else
1767                         idx = 0;
1768
1769                 while (idx < 1u << p->bits) {
1770                         c = tnode_get_child_rcu(p, idx++);
1771                         if (!c)
1772                                 continue;
1773
1774                         if (IS_LEAF(c)) {
1775                                 prefetch(rcu_dereference_rtnl(p->child[idx]));
1776                                 return (struct leaf *) c;
1777                         }
1778
1779                         /* Rescan start scanning in new node */
1780                         p = (struct tnode *) c;
1781                         idx = 0;
1782                 }
1783
1784                 /* Node empty, walk back up to parent */
1785                 c = (struct rt_trie_node *) p;
1786         } while ((p = node_parent_rcu(c)) != NULL);
1787
1788         return NULL; /* Root of trie */
1789 }
1790
1791 static struct leaf *trie_firstleaf(struct trie *t)
1792 {
1793         struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
1794
1795         if (!n)
1796                 return NULL;
1797
1798         if (IS_LEAF(n))          /* trie is just a leaf */
1799                 return (struct leaf *) n;
1800
1801         return leaf_walk_rcu(n, NULL);
1802 }
1803
1804 static struct leaf *trie_nextleaf(struct leaf *l)
1805 {
1806         struct rt_trie_node *c = (struct rt_trie_node *) l;
1807         struct tnode *p = node_parent_rcu(c);
1808
1809         if (!p)
1810                 return NULL;    /* trie with just one leaf */
1811
1812         return leaf_walk_rcu(p, c);
1813 }
1814
1815 static struct leaf *trie_leafindex(struct trie *t, int index)
1816 {
1817         struct leaf *l = trie_firstleaf(t);
1818
1819         while (l && index-- > 0)
1820                 l = trie_nextleaf(l);
1821
1822         return l;
1823 }
1824
1825
1826 /*
1827  * Caller must hold RTNL.
1828  */
1829 int fib_table_flush(struct fib_table *tb)
1830 {
1831         struct trie *t = (struct trie *) tb->tb_data;
1832         struct leaf *l, *ll = NULL;
1833         int found = 0;
1834
1835         for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1836                 found += trie_flush_leaf(l);
1837
1838                 if (ll && hlist_empty(&ll->list))
1839                         trie_leaf_remove(t, ll);
1840                 ll = l;
1841         }
1842
1843         if (ll && hlist_empty(&ll->list))
1844                 trie_leaf_remove(t, ll);
1845
1846         pr_debug("trie_flush found=%d\n", found);
1847         return found;
1848 }
1849
1850 void fib_free_table(struct fib_table *tb)
1851 {
1852         kfree(tb);
1853 }
1854
1855 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1856                            struct fib_table *tb,
1857                            struct sk_buff *skb, struct netlink_callback *cb)
1858 {
1859         int i, s_i;
1860         struct fib_alias *fa;
1861         __be32 xkey = htonl(key);
1862
1863         s_i = cb->args[5];
1864         i = 0;
1865
1866         /* rcu_read_lock is hold by caller */
1867
1868         list_for_each_entry_rcu(fa, fah, fa_list) {
1869                 if (i < s_i) {
1870                         i++;
1871                         continue;
1872                 }
1873
1874                 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1875                                   cb->nlh->nlmsg_seq,
1876                                   RTM_NEWROUTE,
1877                                   tb->tb_id,
1878                                   fa->fa_type,
1879                                   xkey,
1880                                   plen,
1881                                   fa->fa_tos,
1882                                   fa->fa_info, NLM_F_MULTI) < 0) {
1883                         cb->args[5] = i;
1884                         return -1;
1885                 }
1886                 i++;
1887         }
1888         cb->args[5] = i;
1889         return skb->len;
1890 }
1891
1892 static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1893                         struct sk_buff *skb, struct netlink_callback *cb)
1894 {
1895         struct leaf_info *li;
1896         struct hlist_node *node;
1897         int i, s_i;
1898
1899         s_i = cb->args[4];
1900         i = 0;
1901
1902         /* rcu_read_lock is hold by caller */
1903         hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
1904                 if (i < s_i) {
1905                         i++;
1906                         continue;
1907                 }
1908
1909                 if (i > s_i)
1910                         cb->args[5] = 0;
1911
1912                 if (list_empty(&li->falh))
1913                         continue;
1914
1915                 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1916                         cb->args[4] = i;
1917                         return -1;
1918                 }
1919                 i++;
1920         }
1921
1922         cb->args[4] = i;
1923         return skb->len;
1924 }
1925
1926 int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
1927                    struct netlink_callback *cb)
1928 {
1929         struct leaf *l;
1930         struct trie *t = (struct trie *) tb->tb_data;
1931         t_key key = cb->args[2];
1932         int count = cb->args[3];
1933
1934         rcu_read_lock();
1935         /* Dump starting at last key.
1936          * Note: 0.0.0.0/0 (ie default) is first key.
1937          */
1938         if (count == 0)
1939                 l = trie_firstleaf(t);
1940         else {
1941                 /* Normally, continue from last key, but if that is missing
1942                  * fallback to using slow rescan
1943                  */
1944                 l = fib_find_node(t, key);
1945                 if (!l)
1946                         l = trie_leafindex(t, count);
1947         }
1948
1949         while (l) {
1950                 cb->args[2] = l->key;
1951                 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1952                         cb->args[3] = count;
1953                         rcu_read_unlock();
1954                         return -1;
1955                 }
1956
1957                 ++count;
1958                 l = trie_nextleaf(l);
1959                 memset(&cb->args[4], 0,
1960                        sizeof(cb->args) - 4*sizeof(cb->args[0]));
1961         }
1962         cb->args[3] = count;
1963         rcu_read_unlock();
1964
1965         return skb->len;
1966 }
1967
1968 void __init fib_trie_init(void)
1969 {
1970         fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1971                                           sizeof(struct fib_alias),
1972                                           0, SLAB_PANIC, NULL);
1973
1974         trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1975                                            max(sizeof(struct leaf),
1976                                                sizeof(struct leaf_info)),
1977                                            0, SLAB_PANIC, NULL);
1978 }
1979
1980
1981 struct fib_table *fib_trie_table(u32 id)
1982 {
1983         struct fib_table *tb;
1984         struct trie *t;
1985
1986         tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1987                      GFP_KERNEL);
1988         if (tb == NULL)
1989                 return NULL;
1990
1991         tb->tb_id = id;
1992         tb->tb_default = -1;
1993         tb->tb_num_default = 0;
1994
1995         t = (struct trie *) tb->tb_data;
1996         memset(t, 0, sizeof(*t));
1997
1998         return tb;
1999 }
2000
2001 #ifdef CONFIG_PROC_FS
2002 /* Depth first Trie walk iterator */
2003 struct fib_trie_iter {
2004         struct seq_net_private p;
2005         struct fib_table *tb;
2006         struct tnode *tnode;
2007         unsigned int index;
2008         unsigned int depth;
2009 };
2010
2011 static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
2012 {
2013         struct tnode *tn = iter->tnode;
2014         unsigned int cindex = iter->index;
2015         struct tnode *p;
2016
2017         /* A single entry routing table */
2018         if (!tn)
2019                 return NULL;
2020
2021         pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2022                  iter->tnode, iter->index, iter->depth);
2023 rescan:
2024         while (cindex < (1<<tn->bits)) {
2025                 struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
2026
2027                 if (n) {
2028                         if (IS_LEAF(n)) {
2029                                 iter->tnode = tn;
2030                                 iter->index = cindex + 1;
2031                         } else {
2032                                 /* push down one level */
2033                                 iter->tnode = (struct tnode *) n;
2034                                 iter->index = 0;
2035                                 ++iter->depth;
2036                         }
2037                         return n;
2038                 }
2039
2040                 ++cindex;
2041         }
2042
2043         /* Current node exhausted, pop back up */
2044         p = node_parent_rcu((struct rt_trie_node *)tn);
2045         if (p) {
2046                 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2047                 tn = p;
2048                 --iter->depth;
2049                 goto rescan;
2050         }
2051
2052         /* got root? */
2053         return NULL;
2054 }
2055
2056 static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
2057                                        struct trie *t)
2058 {
2059         struct rt_trie_node *n;
2060
2061         if (!t)
2062                 return NULL;
2063
2064         n = rcu_dereference(t->trie);
2065         if (!n)
2066                 return NULL;
2067
2068         if (IS_TNODE(n)) {
2069                 iter->tnode = (struct tnode *) n;
2070                 iter->index = 0;
2071                 iter->depth = 1;
2072         } else {
2073                 iter->tnode = NULL;
2074                 iter->index = 0;
2075                 iter->depth = 0;
2076         }
2077
2078         return n;
2079 }
2080
2081 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2082 {
2083         struct rt_trie_node *n;
2084         struct fib_trie_iter iter;
2085
2086         memset(s, 0, sizeof(*s));
2087
2088         rcu_read_lock();
2089         for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2090                 if (IS_LEAF(n)) {
2091                         struct leaf *l = (struct leaf *)n;
2092                         struct leaf_info *li;
2093                         struct hlist_node *tmp;
2094
2095                         s->leaves++;
2096                         s->totdepth += iter.depth;
2097                         if (iter.depth > s->maxdepth)
2098                                 s->maxdepth = iter.depth;
2099
2100                         hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
2101                                 ++s->prefixes;
2102                 } else {
2103                         const struct tnode *tn = (const struct tnode *) n;
2104                         int i;
2105
2106                         s->tnodes++;
2107                         if (tn->bits < MAX_STAT_DEPTH)
2108                                 s->nodesizes[tn->bits]++;
2109
2110                         for (i = 0; i < (1<<tn->bits); i++)
2111                                 if (!tn->child[i])
2112                                         s->nullpointers++;
2113                 }
2114         }
2115         rcu_read_unlock();
2116 }
2117
2118 /*
2119  *      This outputs /proc/net/fib_triestats
2120  */
2121 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2122 {
2123         unsigned int i, max, pointers, bytes, avdepth;
2124
2125         if (stat->leaves)
2126                 avdepth = stat->totdepth*100 / stat->leaves;
2127         else
2128                 avdepth = 0;
2129
2130         seq_printf(seq, "\tAver depth:     %u.%02d\n",
2131                    avdepth / 100, avdepth % 100);
2132         seq_printf(seq, "\tMax depth:      %u\n", stat->maxdepth);
2133
2134         seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
2135         bytes = sizeof(struct leaf) * stat->leaves;
2136
2137         seq_printf(seq, "\tPrefixes:       %u\n", stat->prefixes);
2138         bytes += sizeof(struct leaf_info) * stat->prefixes;
2139
2140         seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2141         bytes += sizeof(struct tnode) * stat->tnodes;
2142
2143         max = MAX_STAT_DEPTH;
2144         while (max > 0 && stat->nodesizes[max-1] == 0)
2145                 max--;
2146
2147         pointers = 0;
2148         for (i = 1; i <= max; i++)
2149                 if (stat->nodesizes[i] != 0) {
2150                         seq_printf(seq, "  %u: %u",  i, stat->nodesizes[i]);
2151                         pointers += (1<<i) * stat->nodesizes[i];
2152                 }
2153         seq_putc(seq, '\n');
2154         seq_printf(seq, "\tPointers: %u\n", pointers);
2155
2156         bytes += sizeof(struct rt_trie_node *) * pointers;
2157         seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2158         seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
2159 }
2160
2161 #ifdef CONFIG_IP_FIB_TRIE_STATS
2162 static void trie_show_usage(struct seq_file *seq,
2163                             const struct trie_use_stats *stats)
2164 {
2165         seq_printf(seq, "\nCounters:\n---------\n");
2166         seq_printf(seq, "gets = %u\n", stats->gets);
2167         seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2168         seq_printf(seq, "semantic match passed = %u\n",
2169                    stats->semantic_match_passed);
2170         seq_printf(seq, "semantic match miss = %u\n",
2171                    stats->semantic_match_miss);
2172         seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2173         seq_printf(seq, "skipped node resize = %u\n\n",
2174                    stats->resize_node_skipped);
2175 }
2176 #endif /*  CONFIG_IP_FIB_TRIE_STATS */
2177
2178 static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2179 {
2180         if (tb->tb_id == RT_TABLE_LOCAL)
2181                 seq_puts(seq, "Local:\n");
2182         else if (tb->tb_id == RT_TABLE_MAIN)
2183                 seq_puts(seq, "Main:\n");
2184         else
2185                 seq_printf(seq, "Id %d:\n", tb->tb_id);
2186 }
2187
2188
2189 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2190 {
2191         struct net *net = (struct net *)seq->private;
2192         unsigned int h;
2193
2194         seq_printf(seq,
2195                    "Basic info: size of leaf:"
2196                    " %Zd bytes, size of tnode: %Zd bytes.\n",
2197                    sizeof(struct leaf), sizeof(struct tnode));
2198
2199         for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2200                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2201                 struct hlist_node *node;
2202                 struct fib_table *tb;
2203
2204                 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2205                         struct trie *t = (struct trie *) tb->tb_data;
2206                         struct trie_stat stat;
2207
2208                         if (!t)
2209                                 continue;
2210
2211                         fib_table_print(seq, tb);
2212
2213                         trie_collect_stats(t, &stat);
2214                         trie_show_stats(seq, &stat);
2215 #ifdef CONFIG_IP_FIB_TRIE_STATS
2216                         trie_show_usage(seq, &t->stats);
2217 #endif
2218                 }
2219         }
2220
2221         return 0;
2222 }
2223
2224 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2225 {
2226         return single_open_net(inode, file, fib_triestat_seq_show);
2227 }
2228
2229 static const struct file_operations fib_triestat_fops = {
2230         .owner  = THIS_MODULE,
2231         .open   = fib_triestat_seq_open,
2232         .read   = seq_read,
2233         .llseek = seq_lseek,
2234         .release = single_release_net,
2235 };
2236
2237 static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2238 {
2239         struct fib_trie_iter *iter = seq->private;
2240         struct net *net = seq_file_net(seq);
2241         loff_t idx = 0;
2242         unsigned int h;
2243
2244         for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2245                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2246                 struct hlist_node *node;
2247                 struct fib_table *tb;
2248
2249                 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2250                         struct rt_trie_node *n;
2251
2252                         for (n = fib_trie_get_first(iter,
2253                                                     (struct trie *) tb->tb_data);
2254                              n; n = fib_trie_get_next(iter))
2255                                 if (pos == idx++) {
2256                                         iter->tb = tb;
2257                                         return n;
2258                                 }
2259                 }
2260         }
2261
2262         return NULL;
2263 }
2264
2265 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2266         __acquires(RCU)
2267 {
2268         rcu_read_lock();
2269         return fib_trie_get_idx(seq, *pos);
2270 }
2271
2272 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2273 {
2274         struct fib_trie_iter *iter = seq->private;
2275         struct net *net = seq_file_net(seq);
2276         struct fib_table *tb = iter->tb;
2277         struct hlist_node *tb_node;
2278         unsigned int h;
2279         struct rt_trie_node *n;
2280
2281         ++*pos;
2282         /* next node in same table */
2283         n = fib_trie_get_next(iter);
2284         if (n)
2285                 return n;
2286
2287         /* walk rest of this hash chain */
2288         h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2289         while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2290                 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2291                 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2292                 if (n)
2293                         goto found;
2294         }
2295
2296         /* new hash chain */
2297         while (++h < FIB_TABLE_HASHSZ) {
2298                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2299                 hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) {
2300                         n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2301                         if (n)
2302                                 goto found;
2303                 }
2304         }
2305         return NULL;
2306
2307 found:
2308         iter->tb = tb;
2309         return n;
2310 }
2311
2312 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2313         __releases(RCU)
2314 {
2315         rcu_read_unlock();
2316 }
2317
2318 static void seq_indent(struct seq_file *seq, int n)
2319 {
2320         while (n-- > 0)
2321                 seq_puts(seq, "   ");
2322 }
2323
2324 static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2325 {
2326         switch (s) {
2327         case RT_SCOPE_UNIVERSE: return "universe";
2328         case RT_SCOPE_SITE:     return "site";
2329         case RT_SCOPE_LINK:     return "link";
2330         case RT_SCOPE_HOST:     return "host";
2331         case RT_SCOPE_NOWHERE:  return "nowhere";
2332         default:
2333                 snprintf(buf, len, "scope=%d", s);
2334                 return buf;
2335         }
2336 }
2337
2338 static const char *const rtn_type_names[__RTN_MAX] = {
2339         [RTN_UNSPEC] = "UNSPEC",
2340         [RTN_UNICAST] = "UNICAST",
2341         [RTN_LOCAL] = "LOCAL",
2342         [RTN_BROADCAST] = "BROADCAST",
2343         [RTN_ANYCAST] = "ANYCAST",
2344         [RTN_MULTICAST] = "MULTICAST",
2345         [RTN_BLACKHOLE] = "BLACKHOLE",
2346         [RTN_UNREACHABLE] = "UNREACHABLE",
2347         [RTN_PROHIBIT] = "PROHIBIT",
2348         [RTN_THROW] = "THROW",
2349         [RTN_NAT] = "NAT",
2350         [RTN_XRESOLVE] = "XRESOLVE",
2351 };
2352
2353 static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2354 {
2355         if (t < __RTN_MAX && rtn_type_names[t])
2356                 return rtn_type_names[t];
2357         snprintf(buf, len, "type %u", t);
2358         return buf;
2359 }
2360
2361 /* Pretty print the trie */
2362 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2363 {
2364         const struct fib_trie_iter *iter = seq->private;
2365         struct rt_trie_node *n = v;
2366
2367         if (!node_parent_rcu(n))
2368                 fib_table_print(seq, iter->tb);
2369
2370         if (IS_TNODE(n)) {
2371                 struct tnode *tn = (struct tnode *) n;
2372                 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2373
2374                 seq_indent(seq, iter->depth-1);
2375                 seq_printf(seq, "  +-- %pI4/%d %d %d %d\n",
2376                            &prf, tn->pos, tn->bits, tn->full_children,
2377                            tn->empty_children);
2378
2379         } else {
2380                 struct leaf *l = (struct leaf *) n;
2381                 struct leaf_info *li;
2382                 struct hlist_node *node;
2383                 __be32 val = htonl(l->key);
2384
2385                 seq_indent(seq, iter->depth);
2386                 seq_printf(seq, "  |-- %pI4\n", &val);
2387
2388                 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2389                         struct fib_alias *fa;
2390
2391                         list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2392                                 char buf1[32], buf2[32];
2393
2394                                 seq_indent(seq, iter->depth+1);
2395                                 seq_printf(seq, "  /%d %s %s", li->plen,
2396                                            rtn_scope(buf1, sizeof(buf1),
2397                                                      fa->fa_info->fib_scope),
2398                                            rtn_type(buf2, sizeof(buf2),
2399                                                     fa->fa_type));
2400                                 if (fa->fa_tos)
2401                                         seq_printf(seq, " tos=%d", fa->fa_tos);
2402                                 seq_putc(seq, '\n');
2403                         }
2404                 }
2405         }
2406
2407         return 0;
2408 }
2409
2410 static const struct seq_operations fib_trie_seq_ops = {
2411         .start  = fib_trie_seq_start,
2412         .next   = fib_trie_seq_next,
2413         .stop   = fib_trie_seq_stop,
2414         .show   = fib_trie_seq_show,
2415 };
2416
2417 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2418 {
2419         return seq_open_net(inode, file, &fib_trie_seq_ops,
2420                             sizeof(struct fib_trie_iter));
2421 }
2422
2423 static const struct file_operations fib_trie_fops = {
2424         .owner  = THIS_MODULE,
2425         .open   = fib_trie_seq_open,
2426         .read   = seq_read,
2427         .llseek = seq_lseek,
2428         .release = seq_release_net,
2429 };
2430
2431 struct fib_route_iter {
2432         struct seq_net_private p;
2433         struct trie *main_trie;
2434         loff_t  pos;
2435         t_key   key;
2436 };
2437
2438 static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2439 {
2440         struct leaf *l = NULL;
2441         struct trie *t = iter->main_trie;
2442
2443         /* use cache location of last found key */
2444         if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2445                 pos -= iter->pos;
2446         else {
2447                 iter->pos = 0;
2448                 l = trie_firstleaf(t);
2449         }
2450
2451         while (l && pos-- > 0) {
2452                 iter->pos++;
2453                 l = trie_nextleaf(l);
2454         }
2455
2456         if (l)
2457                 iter->key = pos;        /* remember it */
2458         else
2459                 iter->pos = 0;          /* forget it */
2460
2461         return l;
2462 }
2463
2464 static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2465         __acquires(RCU)
2466 {
2467         struct fib_route_iter *iter = seq->private;
2468         struct fib_table *tb;
2469
2470         rcu_read_lock();
2471         tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2472         if (!tb)
2473                 return NULL;
2474
2475         iter->main_trie = (struct trie *) tb->tb_data;
2476         if (*pos == 0)
2477                 return SEQ_START_TOKEN;
2478         else
2479                 return fib_route_get_idx(iter, *pos - 1);
2480 }
2481
2482 static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2483 {
2484         struct fib_route_iter *iter = seq->private;
2485         struct leaf *l = v;
2486
2487         ++*pos;
2488         if (v == SEQ_START_TOKEN) {
2489                 iter->pos = 0;
2490                 l = trie_firstleaf(iter->main_trie);
2491         } else {
2492                 iter->pos++;
2493                 l = trie_nextleaf(l);
2494         }
2495
2496         if (l)
2497                 iter->key = l->key;
2498         else
2499                 iter->pos = 0;
2500         return l;
2501 }
2502
2503 static void fib_route_seq_stop(struct seq_file *seq, void *v)
2504         __releases(RCU)
2505 {
2506         rcu_read_unlock();
2507 }
2508
2509 static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2510 {
2511         unsigned int flags = 0;
2512
2513         if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
2514                 flags = RTF_REJECT;
2515         if (fi && fi->fib_nh->nh_gw)
2516                 flags |= RTF_GATEWAY;
2517         if (mask == htonl(0xFFFFFFFF))
2518                 flags |= RTF_HOST;
2519         flags |= RTF_UP;
2520         return flags;
2521 }
2522
2523 /*
2524  *      This outputs /proc/net/route.
2525  *      The format of the file is not supposed to be changed
2526  *      and needs to be same as fib_hash output to avoid breaking
2527  *      legacy utilities
2528  */
2529 static int fib_route_seq_show(struct seq_file *seq, void *v)
2530 {
2531         struct leaf *l = v;
2532         struct leaf_info *li;
2533         struct hlist_node *node;
2534
2535         if (v == SEQ_START_TOKEN) {
2536                 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2537                            "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2538                            "\tWindow\tIRTT");
2539                 return 0;
2540         }
2541
2542         hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2543                 struct fib_alias *fa;
2544                 __be32 mask, prefix;
2545
2546                 mask = inet_make_mask(li->plen);
2547                 prefix = htonl(l->key);
2548
2549                 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2550                         const struct fib_info *fi = fa->fa_info;
2551                         unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2552                         int len;
2553
2554                         if (fa->fa_type == RTN_BROADCAST
2555                             || fa->fa_type == RTN_MULTICAST)
2556                                 continue;
2557
2558                         if (fi)
2559                                 seq_printf(seq,
2560                                          "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2561                                          "%d\t%08X\t%d\t%u\t%u%n",
2562                                          fi->fib_dev ? fi->fib_dev->name : "*",
2563                                          prefix,
2564                                          fi->fib_nh->nh_gw, flags, 0, 0,
2565                                          fi->fib_priority,
2566                                          mask,
2567                                          (fi->fib_advmss ?
2568                                           fi->fib_advmss + 40 : 0),
2569                                          fi->fib_window,
2570                                          fi->fib_rtt >> 3, &len);
2571                         else
2572                                 seq_printf(seq,
2573                                          "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2574                                          "%d\t%08X\t%d\t%u\t%u%n",
2575                                          prefix, 0, flags, 0, 0, 0,
2576                                          mask, 0, 0, 0, &len);
2577
2578                         seq_printf(seq, "%*s\n", 127 - len, "");
2579                 }
2580         }
2581
2582         return 0;
2583 }
2584
2585 static const struct seq_operations fib_route_seq_ops = {
2586         .start  = fib_route_seq_start,
2587         .next   = fib_route_seq_next,
2588         .stop   = fib_route_seq_stop,
2589         .show   = fib_route_seq_show,
2590 };
2591
2592 static int fib_route_seq_open(struct inode *inode, struct file *file)
2593 {
2594         return seq_open_net(inode, file, &fib_route_seq_ops,
2595                             sizeof(struct fib_route_iter));
2596 }
2597
2598 static const struct file_operations fib_route_fops = {
2599         .owner  = THIS_MODULE,
2600         .open   = fib_route_seq_open,
2601         .read   = seq_read,
2602         .llseek = seq_lseek,
2603         .release = seq_release_net,
2604 };
2605
2606 int __net_init fib_proc_init(struct net *net)
2607 {
2608         if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
2609                 goto out1;
2610
2611         if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
2612                                   &fib_triestat_fops))
2613                 goto out2;
2614
2615         if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
2616                 goto out3;
2617
2618         return 0;
2619
2620 out3:
2621         proc_net_remove(net, "fib_triestat");
2622 out2:
2623         proc_net_remove(net, "fib_trie");
2624 out1:
2625         return -ENOMEM;
2626 }
2627
2628 void __net_exit fib_proc_exit(struct net *net)
2629 {
2630         proc_net_remove(net, "fib_trie");
2631         proc_net_remove(net, "fib_triestat");
2632         proc_net_remove(net, "route");
2633 }
2634
2635 #endif /* CONFIG_PROC_FS */