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("ERROR 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                 if (fa->fa_info->fib_nh == NULL) {
1836                         printk("Trie error _fib_nh=NULL in fa[%d] k=%08x plen=%d\n", i, key, plen);
1837                         i++;
1838                         continue;
1839                 }
1840                 if (fa->fa_info == NULL) {
1841                         printk("Trie error fa_info=NULL in fa[%d] k=%08x plen=%d\n", i, key, plen);
1842                         i++;
1843                         continue;
1844                 }
1845
1846                 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1847                                   cb->nlh->nlmsg_seq,
1848                                   RTM_NEWROUTE,
1849                                   tb->tb_id,
1850                                   fa->fa_type,
1851                                   fa->fa_scope,
1852                                   &xkey,
1853                                   plen,
1854                                   fa->fa_tos,
1855                                   fa->fa_info, 0) < 0) {
1856                         cb->args[3] = i;
1857                         return -1;
1858                 }
1859                 i++;
1860         }
1861         cb->args[3] = i;
1862         return skb->len;
1863 }
1864
1865 static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb,
1866                              struct netlink_callback *cb)
1867 {
1868         int h, s_h;
1869         struct list_head *fa_head;
1870         struct leaf *l = NULL;
1871
1872         s_h = cb->args[2];
1873
1874         for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1875                 if (h < s_h)
1876                         continue;
1877                 if (h > s_h)
1878                         memset(&cb->args[3], 0,
1879                                sizeof(cb->args) - 3*sizeof(cb->args[0]));
1880
1881                 fa_head = get_fa_head(l, plen);
1882
1883                 if (!fa_head)
1884                         continue;
1885
1886                 if (list_empty(fa_head))
1887                         continue;
1888
1889                 if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
1890                         cb->args[2] = h;
1891                         return -1;
1892                 }
1893         }
1894         cb->args[2] = h;
1895         return skb->len;
1896 }
1897
1898 static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlink_callback *cb)
1899 {
1900         int m, s_m;
1901         struct trie *t = (struct trie *) tb->tb_data;
1902
1903         s_m = cb->args[1];
1904
1905         rcu_read_lock();
1906         for (m = 0; m <= 32; m++) {
1907                 if (m < s_m)
1908                         continue;
1909                 if (m > s_m)
1910                         memset(&cb->args[2], 0,
1911                                 sizeof(cb->args) - 2*sizeof(cb->args[0]));
1912
1913                 if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) {
1914                         cb->args[1] = m;
1915                         goto out;
1916                 }
1917         }
1918         rcu_read_unlock();
1919         cb->args[1] = m;
1920         return skb->len;
1921 out:
1922         rcu_read_unlock();
1923         return -1;
1924 }
1925
1926 /* Fix more generic FIB names for init later */
1927
1928 #ifdef CONFIG_IP_MULTIPLE_TABLES
1929 struct fib_table * fib_hash_init(int id)
1930 #else
1931 struct fib_table * __init fib_hash_init(int id)
1932 #endif
1933 {
1934         struct fib_table *tb;
1935         struct trie *t;
1936
1937         if (fn_alias_kmem == NULL)
1938                 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1939                                                   sizeof(struct fib_alias),
1940                                                   0, SLAB_HWCACHE_ALIGN,
1941                                                   NULL, NULL);
1942
1943         tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1944                      GFP_KERNEL);
1945         if (tb == NULL)
1946                 return NULL;
1947
1948         tb->tb_id = id;
1949         tb->tb_lookup = fn_trie_lookup;
1950         tb->tb_insert = fn_trie_insert;
1951         tb->tb_delete = fn_trie_delete;
1952         tb->tb_flush = fn_trie_flush;
1953         tb->tb_select_default = fn_trie_select_default;
1954         tb->tb_dump = fn_trie_dump;
1955         memset(tb->tb_data, 0, sizeof(struct trie));
1956
1957         t = (struct trie *) tb->tb_data;
1958
1959         trie_init(t);
1960
1961         if (id == RT_TABLE_LOCAL)
1962                 trie_local = t;
1963         else if (id == RT_TABLE_MAIN)
1964                 trie_main = t;
1965
1966         if (id == RT_TABLE_LOCAL)
1967                 printk("IPv4 FIB: Using LC-trie version %s\n", VERSION);
1968
1969         return tb;
1970 }
1971
1972 #ifdef CONFIG_PROC_FS
1973 /* Depth first Trie walk iterator */
1974 struct fib_trie_iter {
1975         struct tnode *tnode;
1976         struct trie *trie;
1977         unsigned index;
1978         unsigned depth;
1979 };
1980
1981 static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
1982 {
1983         struct tnode *tn = iter->tnode;
1984         unsigned cindex = iter->index;
1985         struct tnode *p;
1986
1987         pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
1988                  iter->tnode, iter->index, iter->depth);
1989 rescan:
1990         while (cindex < (1<<tn->bits)) {
1991                 struct node *n = tnode_get_child(tn, cindex);
1992
1993                 if (n) {
1994                         if (IS_LEAF(n)) {
1995                                 iter->tnode = tn;
1996                                 iter->index = cindex + 1;
1997                         } else {
1998                                 /* push down one level */
1999                                 iter->tnode = (struct tnode *) n;
2000                                 iter->index = 0;
2001                                 ++iter->depth;
2002                         }
2003                         return n;
2004                 }
2005
2006                 ++cindex;
2007         }
2008
2009         /* Current node exhausted, pop back up */
2010         p = NODE_PARENT(tn);
2011         if (p) {
2012                 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2013                 tn = p;
2014                 --iter->depth;
2015                 goto rescan;
2016         }
2017
2018         /* got root? */
2019         return NULL;
2020 }
2021
2022 static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
2023                                        struct trie *t)
2024 {
2025         struct node *n = rcu_dereference(t->trie);
2026
2027         if (n && IS_TNODE(n)) {
2028                 iter->tnode = (struct tnode *) n;
2029                 iter->trie = t;
2030                 iter->index = 0;
2031                 iter->depth = 1;
2032                 return n;
2033         }
2034         return NULL;
2035 }
2036
2037 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2038 {
2039         struct node *n;
2040         struct fib_trie_iter iter;
2041
2042         memset(s, 0, sizeof(*s));
2043
2044         rcu_read_lock();
2045         for (n = fib_trie_get_first(&iter, t); n;
2046              n = fib_trie_get_next(&iter)) {
2047                 if (IS_LEAF(n)) {
2048                         s->leaves++;
2049                         s->totdepth += iter.depth;
2050                         if (iter.depth > s->maxdepth)
2051                                 s->maxdepth = iter.depth;
2052                 } else {
2053                         const struct tnode *tn = (const struct tnode *) n;
2054                         int i;
2055
2056                         s->tnodes++;
2057                         s->nodesizes[tn->bits]++;
2058                         for (i = 0; i < (1<<tn->bits); i++)
2059                                 if (!tn->child[i])
2060                                         s->nullpointers++;
2061                 }
2062         }
2063         rcu_read_unlock();
2064 }
2065
2066 /*
2067  *      This outputs /proc/net/fib_triestats
2068  */
2069 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2070 {
2071         unsigned i, max, pointers, bytes, avdepth;
2072
2073         if (stat->leaves)
2074                 avdepth = stat->totdepth*100 / stat->leaves;
2075         else
2076                 avdepth = 0;
2077
2078         seq_printf(seq, "\tAver depth:     %d.%02d\n", avdepth / 100, avdepth % 100 );
2079         seq_printf(seq, "\tMax depth:      %u\n", stat->maxdepth);
2080
2081         seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
2082
2083         bytes = sizeof(struct leaf) * stat->leaves;
2084         seq_printf(seq, "\tInternal nodes: %d\n\t", stat->tnodes);
2085         bytes += sizeof(struct tnode) * stat->tnodes;
2086
2087         max = MAX_CHILDS-1;
2088         while (max >= 0 && stat->nodesizes[max] == 0)
2089                 max--;
2090
2091         pointers = 0;
2092         for (i = 1; i <= max; i++)
2093                 if (stat->nodesizes[i] != 0) {
2094                         seq_printf(seq, "  %d: %d",  i, stat->nodesizes[i]);
2095                         pointers += (1<<i) * stat->nodesizes[i];
2096                 }
2097         seq_putc(seq, '\n');
2098         seq_printf(seq, "\tPointers: %d\n", pointers);
2099
2100         bytes += sizeof(struct node *) * pointers;
2101         seq_printf(seq, "Null ptrs: %d\n", stat->nullpointers);
2102         seq_printf(seq, "Total size: %d  kB\n", (bytes + 1023) / 1024);
2103
2104 #ifdef CONFIG_IP_FIB_TRIE_STATS
2105         seq_printf(seq, "Counters:\n---------\n");
2106         seq_printf(seq,"gets = %d\n", t->stats.gets);
2107         seq_printf(seq,"backtracks = %d\n", t->stats.backtrack);
2108         seq_printf(seq,"semantic match passed = %d\n", t->stats.semantic_match_passed);
2109         seq_printf(seq,"semantic match miss = %d\n", t->stats.semantic_match_miss);
2110         seq_printf(seq,"null node hit= %d\n", t->stats.null_node_hit);
2111         seq_printf(seq,"skipped node resize = %d\n", t->stats.resize_node_skipped);
2112 #ifdef CLEAR_STATS
2113         memset(&(t->stats), 0, sizeof(t->stats));
2114 #endif
2115 #endif /*  CONFIG_IP_FIB_TRIE_STATS */
2116 }
2117
2118 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2119 {
2120         struct trie_stat *stat;
2121
2122         stat = kmalloc(sizeof(*stat), GFP_KERNEL);
2123         if (!stat)
2124                 return -ENOMEM;
2125
2126         seq_printf(seq, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
2127                    sizeof(struct leaf), sizeof(struct tnode));
2128
2129         if (trie_local) {
2130                 seq_printf(seq, "Local:\n");
2131                 trie_collect_stats(trie_local, stat);
2132                 trie_show_stats(seq, stat);
2133         }
2134
2135         if (trie_main) {
2136                 seq_printf(seq, "Main:\n");
2137                 trie_collect_stats(trie_main, stat);
2138                 trie_show_stats(seq, stat);
2139         }
2140         kfree(stat);
2141
2142         return 0;
2143 }
2144
2145 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2146 {
2147         return single_open(file, fib_triestat_seq_show, NULL);
2148 }
2149
2150 static struct file_operations fib_triestat_fops = {
2151         .owner  = THIS_MODULE,
2152         .open   = fib_triestat_seq_open,
2153         .read   = seq_read,
2154         .llseek = seq_lseek,
2155         .release = single_release,
2156 };
2157
2158 static struct node *fib_trie_get_idx(struct fib_trie_iter *iter,
2159                                       loff_t pos)
2160 {
2161         loff_t idx = 0;
2162         struct node *n;
2163
2164         for (n = fib_trie_get_first(iter, trie_local);
2165              n; ++idx, n = fib_trie_get_next(iter)) {
2166                 if (pos == idx)
2167                         return n;
2168         }
2169
2170         for (n = fib_trie_get_first(iter, trie_main);
2171              n; ++idx, n = fib_trie_get_next(iter)) {
2172                 if (pos == idx)
2173                         return n;
2174         }
2175         return NULL;
2176 }
2177
2178 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2179 {
2180         rcu_read_lock();
2181         if (*pos == 0)
2182                 return SEQ_START_TOKEN;
2183         return fib_trie_get_idx(seq->private, *pos - 1);
2184 }
2185
2186 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2187 {
2188         struct fib_trie_iter *iter = seq->private;
2189         void *l = v;
2190
2191         ++*pos;
2192         if (v == SEQ_START_TOKEN)
2193                 return fib_trie_get_idx(iter, 0);
2194
2195         v = fib_trie_get_next(iter);
2196         BUG_ON(v == l);
2197         if (v)
2198                 return v;
2199
2200         /* continue scan in next trie */
2201         if (iter->trie == trie_local)
2202                 return fib_trie_get_first(iter, trie_main);
2203
2204         return NULL;
2205 }
2206
2207 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2208 {
2209         rcu_read_unlock();
2210 }
2211
2212 static void seq_indent(struct seq_file *seq, int n)
2213 {
2214         while (n-- > 0) seq_puts(seq, "   ");
2215 }
2216
2217 static inline const char *rtn_scope(enum rt_scope_t s)
2218 {
2219         static char buf[32];
2220
2221         switch(s) {
2222         case RT_SCOPE_UNIVERSE: return "universe";
2223         case RT_SCOPE_SITE:     return "site";
2224         case RT_SCOPE_LINK:     return "link";
2225         case RT_SCOPE_HOST:     return "host";
2226         case RT_SCOPE_NOWHERE:  return "nowhere";
2227         default:
2228                 snprintf(buf, sizeof(buf), "scope=%d", s);
2229                 return buf;
2230         }
2231 }
2232
2233 static const char *rtn_type_names[__RTN_MAX] = {
2234         [RTN_UNSPEC] = "UNSPEC",
2235         [RTN_UNICAST] = "UNICAST",
2236         [RTN_LOCAL] = "LOCAL",
2237         [RTN_BROADCAST] = "BROADCAST",
2238         [RTN_ANYCAST] = "ANYCAST",
2239         [RTN_MULTICAST] = "MULTICAST",
2240         [RTN_BLACKHOLE] = "BLACKHOLE",
2241         [RTN_UNREACHABLE] = "UNREACHABLE",
2242         [RTN_PROHIBIT] = "PROHIBIT",
2243         [RTN_THROW] = "THROW",
2244         [RTN_NAT] = "NAT",
2245         [RTN_XRESOLVE] = "XRESOLVE",
2246 };
2247
2248 static inline const char *rtn_type(unsigned t)
2249 {
2250         static char buf[32];
2251
2252         if (t < __RTN_MAX && rtn_type_names[t])
2253                 return rtn_type_names[t];
2254         snprintf(buf, sizeof(buf), "type %d", t);
2255         return buf;
2256 }
2257
2258 /* Pretty print the trie */
2259 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2260 {
2261         const struct fib_trie_iter *iter = seq->private;
2262         struct node *n = v;
2263
2264         if (v == SEQ_START_TOKEN)
2265                 return 0;
2266
2267         if (IS_TNODE(n)) {
2268                 struct tnode *tn = (struct tnode *) n;
2269                 t_key prf = ntohl(MASK_PFX(tn->key, tn->pos));
2270
2271                 if (!NODE_PARENT(n)) {
2272                         if (iter->trie == trie_local)
2273                                 seq_puts(seq, "<local>:\n");
2274                         else
2275                                 seq_puts(seq, "<main>:\n");
2276                 }
2277                 seq_indent(seq, iter->depth-1);
2278                 seq_printf(seq, "  +-- %d.%d.%d.%d/%d %d %d %d\n",
2279                            NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
2280                            tn->empty_children);
2281
2282         } else {
2283                 struct leaf *l = (struct leaf *) n;
2284                 int i;
2285                 u32 val = ntohl(l->key);
2286
2287                 seq_indent(seq, iter->depth);
2288                 seq_printf(seq, "  |-- %d.%d.%d.%d\n", NIPQUAD(val));
2289                 for (i = 32; i >= 0; i--) {
2290                         struct leaf_info *li = find_leaf_info(l, i);
2291                         if (li) {
2292                                 struct fib_alias *fa;
2293                                 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2294                                         seq_indent(seq, iter->depth+1);
2295                                         seq_printf(seq, "  /%d %s %s", i,
2296                                                    rtn_scope(fa->fa_scope),
2297                                                    rtn_type(fa->fa_type));
2298                                         if (fa->fa_tos)
2299                                                 seq_printf(seq, "tos =%d\n",
2300                                                            fa->fa_tos);
2301                                         seq_putc(seq, '\n');
2302                                 }
2303                         }
2304                 }
2305         }
2306
2307         return 0;
2308 }
2309
2310 static struct seq_operations fib_trie_seq_ops = {
2311         .start  = fib_trie_seq_start,
2312         .next   = fib_trie_seq_next,
2313         .stop   = fib_trie_seq_stop,
2314         .show   = fib_trie_seq_show,
2315 };
2316
2317 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2318 {
2319         struct seq_file *seq;
2320         int rc = -ENOMEM;
2321         struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
2322
2323         if (!s)
2324                 goto out;
2325
2326         rc = seq_open(file, &fib_trie_seq_ops);
2327         if (rc)
2328                 goto out_kfree;
2329
2330         seq          = file->private_data;
2331         seq->private = s;
2332         memset(s, 0, sizeof(*s));
2333 out:
2334         return rc;
2335 out_kfree:
2336         kfree(s);
2337         goto out;
2338 }
2339
2340 static struct file_operations fib_trie_fops = {
2341         .owner  = THIS_MODULE,
2342         .open   = fib_trie_seq_open,
2343         .read   = seq_read,
2344         .llseek = seq_lseek,
2345         .release = seq_release_private,
2346 };
2347
2348 static unsigned fib_flag_trans(int type, u32 mask, const struct fib_info *fi)
2349 {
2350         static unsigned type2flags[RTN_MAX + 1] = {
2351                 [7] = RTF_REJECT, [8] = RTF_REJECT,
2352         };
2353         unsigned flags = type2flags[type];
2354
2355         if (fi && fi->fib_nh->nh_gw)
2356                 flags |= RTF_GATEWAY;
2357         if (mask == 0xFFFFFFFF)
2358                 flags |= RTF_HOST;
2359         flags |= RTF_UP;
2360         return flags;
2361 }
2362
2363 /*
2364  *      This outputs /proc/net/route.
2365  *      The format of the file is not supposed to be changed
2366  *      and needs to be same as fib_hash output to avoid breaking
2367  *      legacy utilities
2368  */
2369 static int fib_route_seq_show(struct seq_file *seq, void *v)
2370 {
2371         struct leaf *l = v;
2372         int i;
2373         char bf[128];
2374
2375         if (v == SEQ_START_TOKEN) {
2376                 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2377                            "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2378                            "\tWindow\tIRTT");
2379                 return 0;
2380         }
2381
2382         if (IS_TNODE(l))
2383                 return 0;
2384
2385         for (i=32; i>=0; i--) {
2386                 struct leaf_info *li = find_leaf_info(l, i);
2387                 struct fib_alias *fa;
2388                 u32 mask, prefix;
2389
2390                 if (!li)
2391                         continue;
2392
2393                 mask = inet_make_mask(li->plen);
2394                 prefix = htonl(l->key);
2395
2396                 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2397                         const struct fib_info *fi = rcu_dereference(fa->fa_info);
2398                         unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2399
2400                         if (fa->fa_type == RTN_BROADCAST
2401                             || fa->fa_type == RTN_MULTICAST)
2402                                 continue;
2403
2404                         if (fi)
2405                                 snprintf(bf, sizeof(bf),
2406                                          "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2407                                          fi->fib_dev ? fi->fib_dev->name : "*",
2408                                          prefix,
2409                                          fi->fib_nh->nh_gw, flags, 0, 0,
2410                                          fi->fib_priority,
2411                                          mask,
2412                                          (fi->fib_advmss ? fi->fib_advmss + 40 : 0),
2413                                          fi->fib_window,
2414                                          fi->fib_rtt >> 3);
2415                         else
2416                                 snprintf(bf, sizeof(bf),
2417                                          "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2418                                          prefix, 0, flags, 0, 0, 0,
2419                                          mask, 0, 0, 0);
2420
2421                         seq_printf(seq, "%-127s\n", bf);
2422                 }
2423         }
2424
2425         return 0;
2426 }
2427
2428 static struct seq_operations fib_route_seq_ops = {
2429         .start  = fib_trie_seq_start,
2430         .next   = fib_trie_seq_next,
2431         .stop   = fib_trie_seq_stop,
2432         .show   = fib_route_seq_show,
2433 };
2434
2435 static int fib_route_seq_open(struct inode *inode, struct file *file)
2436 {
2437         struct seq_file *seq;
2438         int rc = -ENOMEM;
2439         struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
2440
2441         if (!s)
2442                 goto out;
2443
2444         rc = seq_open(file, &fib_route_seq_ops);
2445         if (rc)
2446                 goto out_kfree;
2447
2448         seq          = file->private_data;
2449         seq->private = s;
2450         memset(s, 0, sizeof(*s));
2451 out:
2452         return rc;
2453 out_kfree:
2454         kfree(s);
2455         goto out;
2456 }
2457
2458 static struct file_operations fib_route_fops = {
2459         .owner  = THIS_MODULE,
2460         .open   = fib_route_seq_open,
2461         .read   = seq_read,
2462         .llseek = seq_lseek,
2463         .release = seq_release_private,
2464 };
2465
2466 int __init fib_proc_init(void)
2467 {
2468         if (!proc_net_fops_create("fib_trie", S_IRUGO, &fib_trie_fops))
2469                 goto out1;
2470
2471         if (!proc_net_fops_create("fib_triestat", S_IRUGO, &fib_triestat_fops))
2472                 goto out2;
2473
2474         if (!proc_net_fops_create("route", S_IRUGO, &fib_route_fops))
2475                 goto out3;
2476
2477         return 0;
2478
2479 out3:
2480         proc_net_remove("fib_triestat");
2481 out2:
2482         proc_net_remove("fib_trie");
2483 out1:
2484         return -ENOMEM;
2485 }
2486
2487 void __init fib_proc_exit(void)
2488 {
2489         proc_net_remove("fib_trie");
2490         proc_net_remove("fib_triestat");
2491         proc_net_remove("route");
2492 }
2493
2494 #endif /* CONFIG_PROC_FS */