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