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 err;
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 ret;
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                 ret = check_leaf(t, (struct leaf *)n, key, flp, res);
1397                 goto found;
1398         }
1399
1400         pn = (struct tnode *) n;
1401         chopped_off = 0;
1402
1403         while (pn) {
1404                 pos = pn->pos;
1405                 bits = pn->bits;
1406
1407                 if (!chopped_off)
1408                         cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1409                                                    pos, bits);
1410
1411                 n = tnode_get_child(pn, cindex);
1412
1413                 if (n == NULL) {
1414 #ifdef CONFIG_IP_FIB_TRIE_STATS
1415                         t->stats.null_node_hit++;
1416 #endif
1417                         goto backtrace;
1418                 }
1419
1420                 if (IS_LEAF(n)) {
1421                         ret = check_leaf(t, (struct leaf *)n, key, flp, res);
1422                         if (ret > 0)
1423                                 goto backtrace;
1424                         goto found;
1425                 }
1426
1427                 cn = (struct tnode *)n;
1428
1429                 /*
1430                  * It's a tnode, and we can do some extra checks here if we
1431                  * like, to avoid descending into a dead-end branch.
1432                  * This tnode is in the parent's child array at index
1433                  * key[p_pos..p_pos+p_bits] but potentially with some bits
1434                  * chopped off, so in reality the index may be just a
1435                  * subprefix, padded with zero at the end.
1436                  * We can also take a look at any skipped bits in this
1437                  * tnode - everything up to p_pos is supposed to be ok,
1438                  * and the non-chopped bits of the index (se previous
1439                  * paragraph) are also guaranteed ok, but the rest is
1440                  * considered unknown.
1441                  *
1442                  * The skipped bits are key[pos+bits..cn->pos].
1443                  */
1444
1445                 /* If current_prefix_length < pos+bits, we are already doing
1446                  * actual prefix  matching, which means everything from
1447                  * pos+(bits-chopped_off) onward must be zero along some
1448                  * branch of this subtree - otherwise there is *no* valid
1449                  * prefix present. Here we can only check the skipped
1450                  * bits. Remember, since we have already indexed into the
1451                  * parent's child array, we know that the bits we chopped of
1452                  * *are* zero.
1453                  */
1454
1455                 /* NOTA BENE: Checking only skipped bits
1456                    for the new node here */
1457
1458                 if (current_prefix_length < pos+bits) {
1459                         if (tkey_extract_bits(cn->key, current_prefix_length,
1460                                                 cn->pos - current_prefix_length)
1461                             || !(cn->child[0]))
1462                                 goto backtrace;
1463                 }
1464
1465                 /*
1466                  * If chopped_off=0, the index is fully validated and we
1467                  * only need to look at the skipped bits for this, the new,
1468                  * tnode. What we actually want to do is to find out if
1469                  * these skipped bits match our key perfectly, or if we will
1470                  * have to count on finding a matching prefix further down,
1471                  * because if we do, we would like to have some way of
1472                  * verifying the existence of such a prefix at this point.
1473                  */
1474
1475                 /* The only thing we can do at this point is to verify that
1476                  * any such matching prefix can indeed be a prefix to our
1477                  * key, and if the bits in the node we are inspecting that
1478                  * do not match our key are not ZERO, this cannot be true.
1479                  * Thus, find out where there is a mismatch (before cn->pos)
1480                  * and verify that all the mismatching bits are zero in the
1481                  * new tnode's key.
1482                  */
1483
1484                 /*
1485                  * Note: We aren't very concerned about the piece of
1486                  * the key that precede pn->pos+pn->bits, since these
1487                  * have already been checked. The bits after cn->pos
1488                  * aren't checked since these are by definition
1489                  * "unknown" at this point. Thus, what we want to see
1490                  * is if we are about to enter the "prefix matching"
1491                  * state, and in that case verify that the skipped
1492                  * bits that will prevail throughout this subtree are
1493                  * zero, as they have to be if we are to find a
1494                  * matching prefix.
1495                  */
1496
1497                 node_prefix = mask_pfx(cn->key, cn->pos);
1498                 key_prefix = mask_pfx(key, cn->pos);
1499                 pref_mismatch = key_prefix^node_prefix;
1500                 mp = 0;
1501
1502                 /*
1503                  * In short: If skipped bits in this node do not match
1504                  * the search key, enter the "prefix matching"
1505                  * state.directly.
1506                  */
1507                 if (pref_mismatch) {
1508                         while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
1509                                 mp++;
1510                                 pref_mismatch = pref_mismatch << 1;
1511                         }
1512                         key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);
1513
1514                         if (key_prefix != 0)
1515                                 goto backtrace;
1516
1517                         if (current_prefix_length >= cn->pos)
1518                                 current_prefix_length = mp;
1519                 }
1520
1521                 pn = (struct tnode *)n; /* Descend */
1522                 chopped_off = 0;
1523                 continue;
1524
1525 backtrace:
1526                 chopped_off++;
1527
1528                 /* As zero don't change the child key (cindex) */
1529                 while ((chopped_off <= pn->bits)
1530                        && !(cindex & (1<<(chopped_off-1))))
1531                         chopped_off++;
1532
1533                 /* Decrease current_... with bits chopped off */
1534                 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1535                         current_prefix_length = pn->pos + pn->bits
1536                                 - chopped_off;
1537
1538                 /*
1539                  * Either we do the actual chop off according or if we have
1540                  * chopped off all bits in this tnode walk up to our parent.
1541                  */
1542
1543                 if (chopped_off <= pn->bits) {
1544                         cindex &= ~(1 << (chopped_off-1));
1545                 } else {
1546                         struct tnode *parent = node_parent((struct node *) pn);
1547                         if (!parent)
1548                                 goto failed;
1549
1550                         /* Get Child's index */
1551                         cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1552                         pn = parent;
1553                         chopped_off = 0;
1554
1555 #ifdef CONFIG_IP_FIB_TRIE_STATS
1556                         t->stats.backtrack++;
1557 #endif
1558                         goto backtrace;
1559                 }
1560         }
1561 failed:
1562         ret = 1;
1563 found:
1564         rcu_read_unlock();
1565         return ret;
1566 }
1567
1568 /*
1569  * Remove the leaf and return parent.
1570  */
1571 static void trie_leaf_remove(struct trie *t, struct leaf *l)
1572 {
1573         struct tnode *tp = node_parent((struct node *) l);
1574
1575         pr_debug("entering trie_leaf_remove(%p)\n", l);
1576
1577         if (tp) {
1578                 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1579                 put_child(t, (struct tnode *)tp, cindex, NULL);
1580                 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
1581         } else
1582                 rcu_assign_pointer(t->trie, NULL);
1583
1584         free_leaf(l);
1585 }
1586
1587 /*
1588  * Caller must hold RTNL.
1589  */
1590 static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
1591 {
1592         struct trie *t = (struct trie *) tb->tb_data;
1593         u32 key, mask;
1594         int plen = cfg->fc_dst_len;
1595         u8 tos = cfg->fc_tos;
1596         struct fib_alias *fa, *fa_to_delete;
1597         struct list_head *fa_head;
1598         struct leaf *l;
1599         struct leaf_info *li;
1600
1601         if (plen > 32)
1602                 return -EINVAL;
1603
1604         key = ntohl(cfg->fc_dst);
1605         mask = ntohl(inet_make_mask(plen));
1606
1607         if (key & ~mask)
1608                 return -EINVAL;
1609
1610         key = key & mask;
1611         l = fib_find_node(t, key);
1612
1613         if (!l)
1614                 return -ESRCH;
1615
1616         fa_head = get_fa_head(l, plen);
1617         fa = fib_find_alias(fa_head, tos, 0);
1618
1619         if (!fa)
1620                 return -ESRCH;
1621
1622         pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1623
1624         fa_to_delete = NULL;
1625         fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1626         list_for_each_entry_continue(fa, fa_head, fa_list) {
1627                 struct fib_info *fi = fa->fa_info;
1628
1629                 if (fa->fa_tos != tos)
1630                         break;
1631
1632                 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1633                     (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1634                      fa->fa_scope == cfg->fc_scope) &&
1635                     (!cfg->fc_protocol ||
1636                      fi->fib_protocol == cfg->fc_protocol) &&
1637                     fib_nh_match(cfg, fi) == 0) {
1638                         fa_to_delete = fa;
1639                         break;
1640                 }
1641         }
1642
1643         if (!fa_to_delete)
1644                 return -ESRCH;
1645
1646         fa = fa_to_delete;
1647         rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1648                   &cfg->fc_nlinfo, 0);
1649
1650         l = fib_find_node(t, key);
1651         li = find_leaf_info(l, plen);
1652
1653         list_del_rcu(&fa->fa_list);
1654
1655         if (list_empty(fa_head)) {
1656                 hlist_del_rcu(&li->hlist);
1657                 free_leaf_info(li);
1658         }
1659
1660         if (hlist_empty(&l->list))
1661                 trie_leaf_remove(t, l);
1662
1663         if (fa->fa_state & FA_S_ACCESSED)
1664                 rt_cache_flush(-1);
1665
1666         fib_release_info(fa->fa_info);
1667         alias_free_mem_rcu(fa);
1668         return 0;
1669 }
1670
1671 static int trie_flush_list(struct list_head *head)
1672 {
1673         struct fib_alias *fa, *fa_node;
1674         int found = 0;
1675
1676         list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1677                 struct fib_info *fi = fa->fa_info;
1678
1679                 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1680                         list_del_rcu(&fa->fa_list);
1681                         fib_release_info(fa->fa_info);
1682                         alias_free_mem_rcu(fa);
1683                         found++;
1684                 }
1685         }
1686         return found;
1687 }
1688
1689 static int trie_flush_leaf(struct leaf *l)
1690 {
1691         int found = 0;
1692         struct hlist_head *lih = &l->list;
1693         struct hlist_node *node, *tmp;
1694         struct leaf_info *li = NULL;
1695
1696         hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
1697                 found += trie_flush_list(&li->falh);
1698
1699                 if (list_empty(&li->falh)) {
1700                         hlist_del_rcu(&li->hlist);
1701                         free_leaf_info(li);
1702                 }
1703         }
1704         return found;
1705 }
1706
1707 /*
1708  * Scan for the next right leaf starting at node p->child[idx]
1709  * Since we have back pointer, no recursion necessary.
1710  */
1711 static struct leaf *leaf_walk_rcu(struct tnode *p, struct node *c)
1712 {
1713         do {
1714                 t_key idx;
1715
1716                 if (c)
1717                         idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1718                 else
1719                         idx = 0;
1720
1721                 while (idx < 1u << p->bits) {
1722                         c = tnode_get_child_rcu(p, idx++);
1723                         if (!c)
1724                                 continue;
1725
1726                         if (IS_LEAF(c)) {
1727                                 prefetch(p->child[idx]);
1728                                 return (struct leaf *) c;
1729                         }
1730
1731                         /* Rescan start scanning in new node */
1732                         p = (struct tnode *) c;
1733                         idx = 0;
1734                 }
1735
1736                 /* Node empty, walk back up to parent */
1737                 c = (struct node *) p;
1738         } while ( (p = node_parent_rcu(c)) != NULL);
1739
1740         return NULL; /* Root of trie */
1741 }
1742
1743 static struct leaf *trie_firstleaf(struct trie *t)
1744 {
1745         struct tnode *n = (struct tnode *) rcu_dereference(t->trie);
1746
1747         if (!n)
1748                 return NULL;
1749
1750         if (IS_LEAF(n))          /* trie is just a leaf */
1751                 return (struct leaf *) n;
1752
1753         return leaf_walk_rcu(n, NULL);
1754 }
1755
1756 static struct leaf *trie_nextleaf(struct leaf *l)
1757 {
1758         struct node *c = (struct node *) l;
1759         struct tnode *p = node_parent(c);
1760
1761         if (!p)
1762                 return NULL;    /* trie with just one leaf */
1763
1764         return leaf_walk_rcu(p, c);
1765 }
1766
1767 static struct leaf *trie_leafindex(struct trie *t, int index)
1768 {
1769         struct leaf *l = trie_firstleaf(t);
1770
1771         while (l && index-- > 0)
1772                 l = trie_nextleaf(l);
1773
1774         return l;
1775 }
1776
1777
1778 /*
1779  * Caller must hold RTNL.
1780  */
1781 static int fn_trie_flush(struct fib_table *tb)
1782 {
1783         struct trie *t = (struct trie *) tb->tb_data;
1784         struct leaf *l, *ll = NULL;
1785         int found = 0;
1786
1787         for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1788                 found += trie_flush_leaf(l);
1789
1790                 if (ll && hlist_empty(&ll->list))
1791                         trie_leaf_remove(t, ll);
1792                 ll = l;
1793         }
1794
1795         if (ll && hlist_empty(&ll->list))
1796                 trie_leaf_remove(t, ll);
1797
1798         pr_debug("trie_flush found=%d\n", found);
1799         return found;
1800 }
1801
1802 static void fn_trie_select_default(struct fib_table *tb,
1803                                    const struct flowi *flp,
1804                                    struct fib_result *res)
1805 {
1806         struct trie *t = (struct trie *) tb->tb_data;
1807         int order, last_idx;
1808         struct fib_info *fi = NULL;
1809         struct fib_info *last_resort;
1810         struct fib_alias *fa = NULL;
1811         struct list_head *fa_head;
1812         struct leaf *l;
1813
1814         last_idx = -1;
1815         last_resort = NULL;
1816         order = -1;
1817
1818         rcu_read_lock();
1819
1820         l = fib_find_node(t, 0);
1821         if (!l)
1822                 goto out;
1823
1824         fa_head = get_fa_head(l, 0);
1825         if (!fa_head)
1826                 goto out;
1827
1828         if (list_empty(fa_head))
1829                 goto out;
1830
1831         list_for_each_entry_rcu(fa, fa_head, fa_list) {
1832                 struct fib_info *next_fi = fa->fa_info;
1833
1834                 if (fa->fa_scope != res->scope ||
1835                     fa->fa_type != RTN_UNICAST)
1836                         continue;
1837
1838                 if (next_fi->fib_priority > res->fi->fib_priority)
1839                         break;
1840                 if (!next_fi->fib_nh[0].nh_gw ||
1841                     next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
1842                         continue;
1843                 fa->fa_state |= FA_S_ACCESSED;
1844
1845                 if (fi == NULL) {
1846                         if (next_fi != res->fi)
1847                                 break;
1848                 } else if (!fib_detect_death(fi, order, &last_resort,
1849                                              &last_idx, tb->tb_default)) {
1850                         fib_result_assign(res, fi);
1851                         tb->tb_default = order;
1852                         goto out;
1853                 }
1854                 fi = next_fi;
1855                 order++;
1856         }
1857         if (order <= 0 || fi == NULL) {
1858                 tb->tb_default = -1;
1859                 goto out;
1860         }
1861
1862         if (!fib_detect_death(fi, order, &last_resort, &last_idx,
1863                                 tb->tb_default)) {
1864                 fib_result_assign(res, fi);
1865                 tb->tb_default = order;
1866                 goto out;
1867         }
1868         if (last_idx >= 0)
1869                 fib_result_assign(res, last_resort);
1870         tb->tb_default = last_idx;
1871 out:
1872         rcu_read_unlock();
1873 }
1874
1875 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1876                            struct fib_table *tb,
1877                            struct sk_buff *skb, struct netlink_callback *cb)
1878 {
1879         int i, s_i;
1880         struct fib_alias *fa;
1881         __be32 xkey = htonl(key);
1882
1883         s_i = cb->args[5];
1884         i = 0;
1885
1886         /* rcu_read_lock is hold by caller */
1887
1888         list_for_each_entry_rcu(fa, fah, fa_list) {
1889                 if (i < s_i) {
1890                         i++;
1891                         continue;
1892                 }
1893
1894                 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1895                                   cb->nlh->nlmsg_seq,
1896                                   RTM_NEWROUTE,
1897                                   tb->tb_id,
1898                                   fa->fa_type,
1899                                   fa->fa_scope,
1900                                   xkey,
1901                                   plen,
1902                                   fa->fa_tos,
1903                                   fa->fa_info, NLM_F_MULTI) < 0) {
1904                         cb->args[5] = i;
1905                         return -1;
1906                 }
1907                 i++;
1908         }
1909         cb->args[5] = i;
1910         return skb->len;
1911 }
1912
1913 static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1914                         struct sk_buff *skb, struct netlink_callback *cb)
1915 {
1916         struct leaf_info *li;
1917         struct hlist_node *node;
1918         int i, s_i;
1919
1920         s_i = cb->args[4];
1921         i = 0;
1922
1923         /* rcu_read_lock is hold by caller */
1924         hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
1925                 if (i < s_i) {
1926                         i++;
1927                         continue;
1928                 }
1929
1930                 if (i > s_i)
1931                         cb->args[5] = 0;
1932
1933                 if (list_empty(&li->falh))
1934                         continue;
1935
1936                 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1937                         cb->args[4] = i;
1938                         return -1;
1939                 }
1940                 i++;
1941         }
1942
1943         cb->args[4] = i;
1944         return skb->len;
1945 }
1946
1947 static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb,
1948                         struct netlink_callback *cb)
1949 {
1950         struct leaf *l;
1951         struct trie *t = (struct trie *) tb->tb_data;
1952         t_key key = cb->args[2];
1953         int count = cb->args[3];
1954
1955         rcu_read_lock();
1956         /* Dump starting at last key.
1957          * Note: 0.0.0.0/0 (ie default) is first key.
1958          */
1959         if (count == 0)
1960                 l = trie_firstleaf(t);
1961         else {
1962                 /* Normally, continue from last key, but if that is missing
1963                  * fallback to using slow rescan
1964                  */
1965                 l = fib_find_node(t, key);
1966                 if (!l)
1967                         l = trie_leafindex(t, count);
1968         }
1969
1970         while (l) {
1971                 cb->args[2] = l->key;
1972                 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1973                         cb->args[3] = count;
1974                         rcu_read_unlock();
1975                         return -1;
1976                 }
1977
1978                 ++count;
1979                 l = trie_nextleaf(l);
1980                 memset(&cb->args[4], 0,
1981                        sizeof(cb->args) - 4*sizeof(cb->args[0]));
1982         }
1983         cb->args[3] = count;
1984         rcu_read_unlock();
1985
1986         return skb->len;
1987 }
1988
1989 void __init fib_hash_init(void)
1990 {
1991         fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1992                                           sizeof(struct fib_alias),
1993                                           0, SLAB_PANIC, NULL);
1994
1995         trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1996                                            max(sizeof(struct leaf),
1997                                                sizeof(struct leaf_info)),
1998                                            0, SLAB_PANIC, NULL);
1999 }
2000
2001
2002 /* Fix more generic FIB names for init later */
2003 struct fib_table *fib_hash_table(u32 id)
2004 {
2005         struct fib_table *tb;
2006         struct trie *t;
2007
2008         tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
2009                      GFP_KERNEL);
2010         if (tb == NULL)
2011                 return NULL;
2012
2013         tb->tb_id = id;
2014         tb->tb_default = -1;
2015         tb->tb_lookup = fn_trie_lookup;
2016         tb->tb_insert = fn_trie_insert;
2017         tb->tb_delete = fn_trie_delete;
2018         tb->tb_flush = fn_trie_flush;
2019         tb->tb_select_default = fn_trie_select_default;
2020         tb->tb_dump = fn_trie_dump;
2021
2022         t = (struct trie *) tb->tb_data;
2023         memset(t, 0, sizeof(*t));
2024
2025         if (id == RT_TABLE_LOCAL)
2026                 pr_info("IPv4 FIB: Using LC-trie version %s\n", VERSION);
2027
2028         return tb;
2029 }
2030
2031 #ifdef CONFIG_PROC_FS
2032 /* Depth first Trie walk iterator */
2033 struct fib_trie_iter {
2034         struct seq_net_private p;
2035         struct fib_table *tb;
2036         struct tnode *tnode;
2037         unsigned index;
2038         unsigned depth;
2039 };
2040
2041 static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
2042 {
2043         struct tnode *tn = iter->tnode;
2044         unsigned cindex = iter->index;
2045         struct tnode *p;
2046
2047         /* A single entry routing table */
2048         if (!tn)
2049                 return NULL;
2050
2051         pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2052                  iter->tnode, iter->index, iter->depth);
2053 rescan:
2054         while (cindex < (1<<tn->bits)) {
2055                 struct node *n = tnode_get_child_rcu(tn, cindex);
2056
2057                 if (n) {
2058                         if (IS_LEAF(n)) {
2059                                 iter->tnode = tn;
2060                                 iter->index = cindex + 1;
2061                         } else {
2062                                 /* push down one level */
2063                                 iter->tnode = (struct tnode *) n;
2064                                 iter->index = 0;
2065                                 ++iter->depth;
2066                         }
2067                         return n;
2068                 }
2069
2070                 ++cindex;
2071         }
2072
2073         /* Current node exhausted, pop back up */
2074         p = node_parent_rcu((struct node *)tn);
2075         if (p) {
2076                 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2077                 tn = p;
2078                 --iter->depth;
2079                 goto rescan;
2080         }
2081
2082         /* got root? */
2083         return NULL;
2084 }
2085
2086 static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
2087                                        struct trie *t)
2088 {
2089         struct node *n;
2090
2091         if (!t)
2092                 return NULL;
2093
2094         n = rcu_dereference(t->trie);
2095         if (!n)
2096                 return NULL;
2097
2098         if (IS_TNODE(n)) {
2099                 iter->tnode = (struct tnode *) n;
2100                 iter->index = 0;
2101                 iter->depth = 1;
2102         } else {
2103                 iter->tnode = NULL;
2104                 iter->index = 0;
2105                 iter->depth = 0;
2106         }
2107
2108         return n;
2109 }
2110
2111 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2112 {
2113         struct node *n;
2114         struct fib_trie_iter iter;
2115
2116         memset(s, 0, sizeof(*s));
2117
2118         rcu_read_lock();
2119         for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2120                 if (IS_LEAF(n)) {
2121                         struct leaf *l = (struct leaf *)n;
2122                         struct leaf_info *li;
2123                         struct hlist_node *tmp;
2124
2125                         s->leaves++;
2126                         s->totdepth += iter.depth;
2127                         if (iter.depth > s->maxdepth)
2128                                 s->maxdepth = iter.depth;
2129
2130                         hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
2131                                 ++s->prefixes;
2132                 } else {
2133                         const struct tnode *tn = (const struct tnode *) n;
2134                         int i;
2135
2136                         s->tnodes++;
2137                         if (tn->bits < MAX_STAT_DEPTH)
2138                                 s->nodesizes[tn->bits]++;
2139
2140                         for (i = 0; i < (1<<tn->bits); i++)
2141                                 if (!tn->child[i])
2142                                         s->nullpointers++;
2143                 }
2144         }
2145         rcu_read_unlock();
2146 }
2147
2148 /*
2149  *      This outputs /proc/net/fib_triestats
2150  */
2151 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2152 {
2153         unsigned i, max, pointers, bytes, avdepth;
2154
2155         if (stat->leaves)
2156                 avdepth = stat->totdepth*100 / stat->leaves;
2157         else
2158                 avdepth = 0;
2159
2160         seq_printf(seq, "\tAver depth:     %u.%02d\n",
2161                    avdepth / 100, avdepth % 100);
2162         seq_printf(seq, "\tMax depth:      %u\n", stat->maxdepth);
2163
2164         seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
2165         bytes = sizeof(struct leaf) * stat->leaves;
2166
2167         seq_printf(seq, "\tPrefixes:       %u\n", stat->prefixes);
2168         bytes += sizeof(struct leaf_info) * stat->prefixes;
2169
2170         seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2171         bytes += sizeof(struct tnode) * stat->tnodes;
2172
2173         max = MAX_STAT_DEPTH;
2174         while (max > 0 && stat->nodesizes[max-1] == 0)
2175                 max--;
2176
2177         pointers = 0;
2178         for (i = 1; i <= max; i++)
2179                 if (stat->nodesizes[i] != 0) {
2180                         seq_printf(seq, "  %u: %u",  i, stat->nodesizes[i]);
2181                         pointers += (1<<i) * stat->nodesizes[i];
2182                 }
2183         seq_putc(seq, '\n');
2184         seq_printf(seq, "\tPointers: %u\n", pointers);
2185
2186         bytes += sizeof(struct node *) * pointers;
2187         seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2188         seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
2189 }
2190
2191 #ifdef CONFIG_IP_FIB_TRIE_STATS
2192 static void trie_show_usage(struct seq_file *seq,
2193                             const struct trie_use_stats *stats)
2194 {
2195         seq_printf(seq, "\nCounters:\n---------\n");
2196         seq_printf(seq, "gets = %u\n", stats->gets);
2197         seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2198         seq_printf(seq, "semantic match passed = %u\n",
2199                    stats->semantic_match_passed);
2200         seq_printf(seq, "semantic match miss = %u\n",
2201                    stats->semantic_match_miss);
2202         seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2203         seq_printf(seq, "skipped node resize = %u\n\n",
2204                    stats->resize_node_skipped);
2205 }
2206 #endif /*  CONFIG_IP_FIB_TRIE_STATS */
2207
2208 static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2209 {
2210         if (tb->tb_id == RT_TABLE_LOCAL)
2211                 seq_puts(seq, "Local:\n");
2212         else if (tb->tb_id == RT_TABLE_MAIN)
2213                 seq_puts(seq, "Main:\n");
2214         else
2215                 seq_printf(seq, "Id %d:\n", tb->tb_id);
2216 }
2217
2218
2219 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2220 {
2221         struct net *net = (struct net *)seq->private;
2222         unsigned int h;
2223
2224         seq_printf(seq,
2225                    "Basic info: size of leaf:"
2226                    " %Zd bytes, size of tnode: %Zd bytes.\n",
2227                    sizeof(struct leaf), sizeof(struct tnode));
2228
2229         for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2230                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2231                 struct hlist_node *node;
2232                 struct fib_table *tb;
2233
2234                 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2235                         struct trie *t = (struct trie *) tb->tb_data;
2236                         struct trie_stat stat;
2237
2238                         if (!t)
2239                                 continue;
2240
2241                         fib_table_print(seq, tb);
2242
2243                         trie_collect_stats(t, &stat);
2244                         trie_show_stats(seq, &stat);
2245 #ifdef CONFIG_IP_FIB_TRIE_STATS
2246                         trie_show_usage(seq, &t->stats);
2247 #endif
2248                 }
2249         }
2250
2251         return 0;
2252 }
2253
2254 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2255 {
2256         int err;
2257         struct net *net;
2258
2259         net = get_proc_net(inode);
2260         if (net == NULL)
2261                 return -ENXIO;
2262         err = single_open(file, fib_triestat_seq_show, net);
2263         if (err < 0) {
2264                 put_net(net);
2265                 return err;
2266         }
2267         return 0;
2268 }
2269
2270 static int fib_triestat_seq_release(struct inode *ino, struct file *f)
2271 {
2272         struct seq_file *seq = f->private_data;
2273         put_net(seq->private);
2274         return single_release(ino, f);
2275 }
2276
2277 static const struct file_operations fib_triestat_fops = {
2278         .owner  = THIS_MODULE,
2279         .open   = fib_triestat_seq_open,
2280         .read   = seq_read,
2281         .llseek = seq_lseek,
2282         .release = fib_triestat_seq_release,
2283 };
2284
2285 static struct node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2286 {
2287         struct fib_trie_iter *iter = seq->private;
2288         struct net *net = seq_file_net(seq);
2289         loff_t idx = 0;
2290         unsigned int h;
2291
2292         for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2293                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2294                 struct hlist_node *node;
2295                 struct fib_table *tb;
2296
2297                 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2298                         struct node *n;
2299
2300                         for (n = fib_trie_get_first(iter,
2301                                                     (struct trie *) tb->tb_data);
2302                              n; n = fib_trie_get_next(iter))
2303                                 if (pos == idx++) {
2304                                         iter->tb = tb;
2305                                         return n;
2306                                 }
2307                 }
2308         }
2309
2310         return NULL;
2311 }
2312
2313 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2314         __acquires(RCU)
2315 {
2316         rcu_read_lock();
2317         return fib_trie_get_idx(seq, *pos);
2318 }
2319
2320 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2321 {
2322         struct fib_trie_iter *iter = seq->private;
2323         struct net *net = seq_file_net(seq);
2324         struct fib_table *tb = iter->tb;
2325         struct hlist_node *tb_node;
2326         unsigned int h;
2327         struct node *n;
2328
2329         ++*pos;
2330         /* next node in same table */
2331         n = fib_trie_get_next(iter);
2332         if (n)
2333                 return n;
2334
2335         /* walk rest of this hash chain */
2336         h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2337         while ( (tb_node = rcu_dereference(tb->tb_hlist.next)) ) {
2338                 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2339                 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2340                 if (n)
2341                         goto found;
2342         }
2343
2344         /* new hash chain */
2345         while (++h < FIB_TABLE_HASHSZ) {
2346                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2347                 hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) {
2348                         n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2349                         if (n)
2350                                 goto found;
2351                 }
2352         }
2353         return NULL;
2354
2355 found:
2356         iter->tb = tb;
2357         return n;
2358 }
2359
2360 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2361         __releases(RCU)
2362 {
2363         rcu_read_unlock();
2364 }
2365
2366 static void seq_indent(struct seq_file *seq, int n)
2367 {
2368         while (n-- > 0) seq_puts(seq, "   ");
2369 }
2370
2371 static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2372 {
2373         switch (s) {
2374         case RT_SCOPE_UNIVERSE: return "universe";
2375         case RT_SCOPE_SITE:     return "site";
2376         case RT_SCOPE_LINK:     return "link";
2377         case RT_SCOPE_HOST:     return "host";
2378         case RT_SCOPE_NOWHERE:  return "nowhere";
2379         default:
2380                 snprintf(buf, len, "scope=%d", s);
2381                 return buf;
2382         }
2383 }
2384
2385 static const char *rtn_type_names[__RTN_MAX] = {
2386         [RTN_UNSPEC] = "UNSPEC",
2387         [RTN_UNICAST] = "UNICAST",
2388         [RTN_LOCAL] = "LOCAL",
2389         [RTN_BROADCAST] = "BROADCAST",
2390         [RTN_ANYCAST] = "ANYCAST",
2391         [RTN_MULTICAST] = "MULTICAST",
2392         [RTN_BLACKHOLE] = "BLACKHOLE",
2393         [RTN_UNREACHABLE] = "UNREACHABLE",
2394         [RTN_PROHIBIT] = "PROHIBIT",
2395         [RTN_THROW] = "THROW",
2396         [RTN_NAT] = "NAT",
2397         [RTN_XRESOLVE] = "XRESOLVE",
2398 };
2399
2400 static inline const char *rtn_type(char *buf, size_t len, unsigned t)
2401 {
2402         if (t < __RTN_MAX && rtn_type_names[t])
2403                 return rtn_type_names[t];
2404         snprintf(buf, len, "type %u", t);
2405         return buf;
2406 }
2407
2408 /* Pretty print the trie */
2409 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2410 {
2411         const struct fib_trie_iter *iter = seq->private;
2412         struct node *n = v;
2413
2414         if (!node_parent_rcu(n))
2415                 fib_table_print(seq, iter->tb);
2416
2417         if (IS_TNODE(n)) {
2418                 struct tnode *tn = (struct tnode *) n;
2419                 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2420
2421                 seq_indent(seq, iter->depth-1);
2422                 seq_printf(seq, "  +-- " NIPQUAD_FMT "/%d %d %d %d\n",
2423                            NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
2424                            tn->empty_children);
2425
2426         } else {
2427                 struct leaf *l = (struct leaf *) n;
2428                 struct leaf_info *li;
2429                 struct hlist_node *node;
2430                 __be32 val = htonl(l->key);
2431
2432                 seq_indent(seq, iter->depth);
2433                 seq_printf(seq, "  |-- " NIPQUAD_FMT "\n", NIPQUAD(val));
2434
2435                 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2436                         struct fib_alias *fa;
2437
2438                         list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2439                                 char buf1[32], buf2[32];
2440
2441                                 seq_indent(seq, iter->depth+1);
2442                                 seq_printf(seq, "  /%d %s %s", li->plen,
2443                                            rtn_scope(buf1, sizeof(buf1),
2444                                                      fa->fa_scope),
2445                                            rtn_type(buf2, sizeof(buf2),
2446                                                     fa->fa_type));
2447                                 if (fa->fa_tos)
2448                                         seq_printf(seq, " tos=%d", fa->fa_tos);
2449                                 seq_putc(seq, '\n');
2450                         }
2451                 }
2452         }
2453
2454         return 0;
2455 }
2456
2457 static const struct seq_operations fib_trie_seq_ops = {
2458         .start  = fib_trie_seq_start,
2459         .next   = fib_trie_seq_next,
2460         .stop   = fib_trie_seq_stop,
2461         .show   = fib_trie_seq_show,
2462 };
2463
2464 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2465 {
2466         return seq_open_net(inode, file, &fib_trie_seq_ops,
2467                             sizeof(struct fib_trie_iter));
2468 }
2469
2470 static const struct file_operations fib_trie_fops = {
2471         .owner  = THIS_MODULE,
2472         .open   = fib_trie_seq_open,
2473         .read   = seq_read,
2474         .llseek = seq_lseek,
2475         .release = seq_release_net,
2476 };
2477
2478 struct fib_route_iter {
2479         struct seq_net_private p;
2480         struct trie *main_trie;
2481         loff_t  pos;
2482         t_key   key;
2483 };
2484
2485 static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2486 {
2487         struct leaf *l = NULL;
2488         struct trie *t = iter->main_trie;
2489
2490         /* use cache location of last found key */
2491         if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2492                 pos -= iter->pos;
2493         else {
2494                 iter->pos = 0;
2495                 l = trie_firstleaf(t);
2496         }
2497
2498         while (l && pos-- > 0) {
2499                 iter->pos++;
2500                 l = trie_nextleaf(l);
2501         }
2502
2503         if (l)
2504                 iter->key = pos;        /* remember it */
2505         else
2506                 iter->pos = 0;          /* forget it */
2507
2508         return l;
2509 }
2510
2511 static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2512         __acquires(RCU)
2513 {
2514         struct fib_route_iter *iter = seq->private;
2515         struct fib_table *tb;
2516
2517         rcu_read_lock();
2518         tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2519         if (!tb)
2520                 return NULL;
2521
2522         iter->main_trie = (struct trie *) tb->tb_data;
2523         if (*pos == 0)
2524                 return SEQ_START_TOKEN;
2525         else
2526                 return fib_route_get_idx(iter, *pos - 1);
2527 }
2528
2529 static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2530 {
2531         struct fib_route_iter *iter = seq->private;
2532         struct leaf *l = v;
2533
2534         ++*pos;
2535         if (v == SEQ_START_TOKEN) {
2536                 iter->pos = 0;
2537                 l = trie_firstleaf(iter->main_trie);
2538         } else {
2539                 iter->pos++;
2540                 l = trie_nextleaf(l);
2541         }
2542
2543         if (l)
2544                 iter->key = l->key;
2545         else
2546                 iter->pos = 0;
2547         return l;
2548 }
2549
2550 static void fib_route_seq_stop(struct seq_file *seq, void *v)
2551         __releases(RCU)
2552 {
2553         rcu_read_unlock();
2554 }
2555
2556 static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2557 {
2558         static unsigned type2flags[RTN_MAX + 1] = {
2559                 [7] = RTF_REJECT, [8] = RTF_REJECT,
2560         };
2561         unsigned flags = type2flags[type];
2562
2563         if (fi && fi->fib_nh->nh_gw)
2564                 flags |= RTF_GATEWAY;
2565         if (mask == htonl(0xFFFFFFFF))
2566                 flags |= RTF_HOST;
2567         flags |= RTF_UP;
2568         return flags;
2569 }
2570
2571 /*
2572  *      This outputs /proc/net/route.
2573  *      The format of the file is not supposed to be changed
2574  *      and needs to be same as fib_hash output to avoid breaking
2575  *      legacy utilities
2576  */
2577 static int fib_route_seq_show(struct seq_file *seq, void *v)
2578 {
2579         struct leaf *l = v;
2580         struct leaf_info *li;
2581         struct hlist_node *node;
2582
2583         if (v == SEQ_START_TOKEN) {
2584                 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2585                            "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2586                            "\tWindow\tIRTT");
2587                 return 0;
2588         }
2589
2590         hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2591                 struct fib_alias *fa;
2592                 __be32 mask, prefix;
2593
2594                 mask = inet_make_mask(li->plen);
2595                 prefix = htonl(l->key);
2596
2597                 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2598                         const struct fib_info *fi = fa->fa_info;
2599                         unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2600                         int len;
2601
2602                         if (fa->fa_type == RTN_BROADCAST
2603                             || fa->fa_type == RTN_MULTICAST)
2604                                 continue;
2605
2606                         if (fi)
2607                                 seq_printf(seq,
2608                                          "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2609                                          "%d\t%08X\t%d\t%u\t%u%n",
2610                                          fi->fib_dev ? fi->fib_dev->name : "*",
2611                                          prefix,
2612                                          fi->fib_nh->nh_gw, flags, 0, 0,
2613                                          fi->fib_priority,
2614                                          mask,
2615                                          (fi->fib_advmss ?
2616                                           fi->fib_advmss + 40 : 0),
2617                                          fi->fib_window,
2618                                          fi->fib_rtt >> 3, &len);
2619                         else
2620                                 seq_printf(seq,
2621                                          "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2622                                          "%d\t%08X\t%d\t%u\t%u%n",
2623                                          prefix, 0, flags, 0, 0, 0,
2624                                          mask, 0, 0, 0, &len);
2625
2626                         seq_printf(seq, "%*s\n", 127 - len, "");
2627                 }
2628         }
2629
2630         return 0;
2631 }
2632
2633 static const struct seq_operations fib_route_seq_ops = {
2634         .start  = fib_route_seq_start,
2635         .next   = fib_route_seq_next,
2636         .stop   = fib_route_seq_stop,
2637         .show   = fib_route_seq_show,
2638 };
2639
2640 static int fib_route_seq_open(struct inode *inode, struct file *file)
2641 {
2642         return seq_open_net(inode, file, &fib_route_seq_ops,
2643                             sizeof(struct fib_route_iter));
2644 }
2645
2646 static const struct file_operations fib_route_fops = {
2647         .owner  = THIS_MODULE,
2648         .open   = fib_route_seq_open,
2649         .read   = seq_read,
2650         .llseek = seq_lseek,
2651         .release = seq_release_net,
2652 };
2653
2654 int __net_init fib_proc_init(struct net *net)
2655 {
2656         if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
2657                 goto out1;
2658
2659         if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
2660                                   &fib_triestat_fops))
2661                 goto out2;
2662
2663         if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
2664                 goto out3;
2665
2666         return 0;
2667
2668 out3:
2669         proc_net_remove(net, "fib_triestat");
2670 out2:
2671         proc_net_remove(net, "fib_trie");
2672 out1:
2673         return -ENOMEM;
2674 }
2675
2676 void __net_exit fib_proc_exit(struct net *net)
2677 {
2678         proc_net_remove(net, "fib_trie");
2679         proc_net_remove(net, "fib_triestat");
2680         proc_net_remove(net, "route");
2681 }
2682
2683 #endif /* CONFIG_PROC_FS */