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