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