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