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