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