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