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