git.oblomov.eu Git - linux-2.6/blob - net/ipv4/fib_trie.c

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