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