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