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