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