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