net/ipv4/fib_trie.c

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