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