1 /* 2 * Linux INET6 implementation 3 * Forwarding Information Database 4 * 5 * Authors: 6 * Pedro Roque <roque@di.fc.ul.pt> 7 * 8 * This program is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU General Public License 10 * as published by the Free Software Foundation; either version 11 * 2 of the License, or (at your option) any later version. 12 */ 13 14 /* 15 * Changes: 16 * Yuji SEKIYA @USAGI: Support default route on router node; 17 * remove ip6_null_entry from the top of 18 * routing table. 19 * Ville Nuorvala: Fixed routing subtrees. 20 */ 21 22 #define pr_fmt(fmt) "IPv6: " fmt 23 24 #include <linux/errno.h> 25 #include <linux/types.h> 26 #include <linux/net.h> 27 #include <linux/route.h> 28 #include <linux/netdevice.h> 29 #include <linux/in6.h> 30 #include <linux/init.h> 31 #include <linux/list.h> 32 #include <linux/slab.h> 33 34 #include <net/ipv6.h> 35 #include <net/ndisc.h> 36 #include <net/addrconf.h> 37 38 #include <net/ip6_fib.h> 39 #include <net/ip6_route.h> 40 41 #define RT6_DEBUG 2 42 43 #if RT6_DEBUG >= 3 44 #define RT6_TRACE(x...) pr_debug(x) 45 #else 46 #define RT6_TRACE(x...) do { ; } while (0) 47 #endif 48 49 static struct kmem_cache * fib6_node_kmem __read_mostly; 50 51 enum fib_walk_state_t 52 { 53 #ifdef CONFIG_IPV6_SUBTREES 54 FWS_S, 55 #endif 56 FWS_L, 57 FWS_R, 58 FWS_C, 59 FWS_U 60 }; 61 62 struct fib6_cleaner_t 63 { 64 struct fib6_walker_t w; 65 struct net *net; 66 int (*func)(struct rt6_info *, void *arg); 67 void *arg; 68 }; 69 70 static DEFINE_RWLOCK(fib6_walker_lock); 71 72 #ifdef CONFIG_IPV6_SUBTREES 73 #define FWS_INIT FWS_S 74 #else 75 #define FWS_INIT FWS_L 76 #endif 77 78 static void fib6_prune_clones(struct net *net, struct fib6_node *fn, 79 struct rt6_info *rt); 80 static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn); 81 static struct fib6_node *fib6_repair_tree(struct net *net, struct fib6_node *fn); 82 static int fib6_walk(struct fib6_walker_t *w); 83 static int fib6_walk_continue(struct fib6_walker_t *w); 84 85 /* 86 * A routing update causes an increase of the serial number on the 87 * affected subtree. This allows for cached routes to be asynchronously 88 * tested when modifications are made to the destination cache as a 89 * result of redirects, path MTU changes, etc. 90 */ 91 92 static __u32 rt_sernum; 93 94 static void fib6_gc_timer_cb(unsigned long arg); 95 96 static LIST_HEAD(fib6_walkers); 97 #define FOR_WALKERS(w) list_for_each_entry(w, &fib6_walkers, lh) 98 99 static inline void fib6_walker_link(struct fib6_walker_t *w) 100 { 101 write_lock_bh(&fib6_walker_lock); 102 list_add(&w->lh, &fib6_walkers); 103 write_unlock_bh(&fib6_walker_lock); 104 } 105 106 static inline void fib6_walker_unlink(struct fib6_walker_t *w) 107 { 108 write_lock_bh(&fib6_walker_lock); 109 list_del(&w->lh); 110 write_unlock_bh(&fib6_walker_lock); 111 } 112 static __inline__ u32 fib6_new_sernum(void) 113 { 114 u32 n = ++rt_sernum; 115 if ((__s32)n <= 0) 116 rt_sernum = n = 1; 117 return n; 118 } 119 120 /* 121 * Auxiliary address test functions for the radix tree. 122 * 123 * These assume a 32bit processor (although it will work on 124 * 64bit processors) 125 */ 126 127 /* 128 * test bit 129 */ 130 #if defined(__LITTLE_ENDIAN) 131 # define BITOP_BE32_SWIZZLE (0x1F & ~7) 132 #else 133 # define BITOP_BE32_SWIZZLE 0 134 #endif 135 136 static __inline__ __be32 addr_bit_set(const void *token, int fn_bit) 137 { 138 const __be32 *addr = token; 139 /* 140 * Here, 141 * 1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f) 142 * is optimized version of 143 * htonl(1 << ((~fn_bit)&0x1F)) 144 * See include/asm-generic/bitops/le.h. 145 */ 146 return (__force __be32)(1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)) & 147 addr[fn_bit >> 5]; 148 } 149 150 static __inline__ struct fib6_node * node_alloc(void) 151 { 152 struct fib6_node *fn; 153 154 fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC); 155 156 return fn; 157 } 158 159 static __inline__ void node_free(struct fib6_node * fn) 160 { 161 kmem_cache_free(fib6_node_kmem, fn); 162 } 163 164 static __inline__ void rt6_release(struct rt6_info *rt) 165 { 166 if (atomic_dec_and_test(&rt->rt6i_ref)) 167 dst_free(&rt->dst); 168 } 169 170 static void fib6_link_table(struct net *net, struct fib6_table *tb) 171 { 172 unsigned int h; 173 174 /* 175 * Initialize table lock at a single place to give lockdep a key, 176 * tables aren't visible prior to being linked to the list. 177 */ 178 rwlock_init(&tb->tb6_lock); 179 180 h = tb->tb6_id & (FIB6_TABLE_HASHSZ - 1); 181 182 /* 183 * No protection necessary, this is the only list mutatation 184 * operation, tables never disappear once they exist. 185 */ 186 hlist_add_head_rcu(&tb->tb6_hlist, &net->ipv6.fib_table_hash[h]); 187 } 188 189 #ifdef CONFIG_IPV6_MULTIPLE_TABLES 190 191 static struct fib6_table *fib6_alloc_table(struct net *net, u32 id) 192 { 193 struct fib6_table *table; 194 195 table = kzalloc(sizeof(*table), GFP_ATOMIC); 196 if (table) { 197 table->tb6_id = id; 198 table->tb6_root.leaf = net->ipv6.ip6_null_entry; 199 table->tb6_root.fn_flags = RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO; 200 inet_peer_base_init(&table->tb6_peers); 201 } 202 203 return table; 204 } 205 206 struct fib6_table *fib6_new_table(struct net *net, u32 id) 207 { 208 struct fib6_table *tb; 209 210 if (id == 0) 211 id = RT6_TABLE_MAIN; 212 tb = fib6_get_table(net, id); 213 if (tb) 214 return tb; 215 216 tb = fib6_alloc_table(net, id); 217 if (tb) 218 fib6_link_table(net, tb); 219 220 return tb; 221 } 222 223 struct fib6_table *fib6_get_table(struct net *net, u32 id) 224 { 225 struct fib6_table *tb; 226 struct hlist_head *head; 227 unsigned int h; 228 229 if (id == 0) 230 id = RT6_TABLE_MAIN; 231 h = id & (FIB6_TABLE_HASHSZ - 1); 232 rcu_read_lock(); 233 head = &net->ipv6.fib_table_hash[h]; 234 hlist_for_each_entry_rcu(tb, head, tb6_hlist) { 235 if (tb->tb6_id == id) { 236 rcu_read_unlock(); 237 return tb; 238 } 239 } 240 rcu_read_unlock(); 241 242 return NULL; 243 } 244 245 static void __net_init fib6_tables_init(struct net *net) 246 { 247 fib6_link_table(net, net->ipv6.fib6_main_tbl); 248 fib6_link_table(net, net->ipv6.fib6_local_tbl); 249 } 250 #else 251 252 struct fib6_table *fib6_new_table(struct net *net, u32 id) 253 { 254 return fib6_get_table(net, id); 255 } 256 257 struct fib6_table *fib6_get_table(struct net *net, u32 id) 258 { 259 return net->ipv6.fib6_main_tbl; 260 } 261 262 struct dst_entry *fib6_rule_lookup(struct net *net, struct flowi6 *fl6, 263 int flags, pol_lookup_t lookup) 264 { 265 return (struct dst_entry *) lookup(net, net->ipv6.fib6_main_tbl, fl6, flags); 266 } 267 268 static void __net_init fib6_tables_init(struct net *net) 269 { 270 fib6_link_table(net, net->ipv6.fib6_main_tbl); 271 } 272 273 #endif 274 275 static int fib6_dump_node(struct fib6_walker_t *w) 276 { 277 int res; 278 struct rt6_info *rt; 279 280 for (rt = w->leaf; rt; rt = rt->dst.rt6_next) { 281 res = rt6_dump_route(rt, w->args); 282 if (res < 0) { 283 /* Frame is full, suspend walking */ 284 w->leaf = rt; 285 return 1; 286 } 287 WARN_ON(res == 0); 288 } 289 w->leaf = NULL; 290 return 0; 291 } 292 293 static void fib6_dump_end(struct netlink_callback *cb) 294 { 295 struct fib6_walker_t *w = (void*)cb->args[2]; 296 297 if (w) { 298 if (cb->args[4]) { 299 cb->args[4] = 0; 300 fib6_walker_unlink(w); 301 } 302 cb->args[2] = 0; 303 kfree(w); 304 } 305 cb->done = (void*)cb->args[3]; 306 cb->args[1] = 3; 307 } 308 309 static int fib6_dump_done(struct netlink_callback *cb) 310 { 311 fib6_dump_end(cb); 312 return cb->done ? cb->done(cb) : 0; 313 } 314 315 static int fib6_dump_table(struct fib6_table *table, struct sk_buff *skb, 316 struct netlink_callback *cb) 317 { 318 struct fib6_walker_t *w; 319 int res; 320 321 w = (void *)cb->args[2]; 322 w->root = &table->tb6_root; 323 324 if (cb->args[4] == 0) { 325 w->count = 0; 326 w->skip = 0; 327 328 read_lock_bh(&table->tb6_lock); 329 res = fib6_walk(w); 330 read_unlock_bh(&table->tb6_lock); 331 if (res > 0) { 332 cb->args[4] = 1; 333 cb->args[5] = w->root->fn_sernum; 334 } 335 } else { 336 if (cb->args[5] != w->root->fn_sernum) { 337 /* Begin at the root if the tree changed */ 338 cb->args[5] = w->root->fn_sernum; 339 w->state = FWS_INIT; 340 w->node = w->root; 341 w->skip = w->count; 342 } else 343 w->skip = 0; 344 345 read_lock_bh(&table->tb6_lock); 346 res = fib6_walk_continue(w); 347 read_unlock_bh(&table->tb6_lock); 348 if (res <= 0) { 349 fib6_walker_unlink(w); 350 cb->args[4] = 0; 351 } 352 } 353 354 return res; 355 } 356 357 static int inet6_dump_fib(struct sk_buff *skb, struct netlink_callback *cb) 358 { 359 struct net *net = sock_net(skb->sk); 360 unsigned int h, s_h; 361 unsigned int e = 0, s_e; 362 struct rt6_rtnl_dump_arg arg; 363 struct fib6_walker_t *w; 364 struct fib6_table *tb; 365 struct hlist_head *head; 366 int res = 0; 367 368 s_h = cb->args[0]; 369 s_e = cb->args[1]; 370 371 w = (void *)cb->args[2]; 372 if (!w) { 373 /* New dump: 374 * 375 * 1. hook callback destructor. 376 */ 377 cb->args[3] = (long)cb->done; 378 cb->done = fib6_dump_done; 379 380 /* 381 * 2. allocate and initialize walker. 382 */ 383 w = kzalloc(sizeof(*w), GFP_ATOMIC); 384 if (!w) 385 return -ENOMEM; 386 w->func = fib6_dump_node; 387 cb->args[2] = (long)w; 388 } 389 390 arg.skb = skb; 391 arg.cb = cb; 392 arg.net = net; 393 w->args = &arg; 394 395 rcu_read_lock(); 396 for (h = s_h; h < FIB6_TABLE_HASHSZ; h++, s_e = 0) { 397 e = 0; 398 head = &net->ipv6.fib_table_hash[h]; 399 hlist_for_each_entry_rcu(tb, head, tb6_hlist) { 400 if (e < s_e) 401 goto next; 402 res = fib6_dump_table(tb, skb, cb); 403 if (res != 0) 404 goto out; 405 next: 406 e++; 407 } 408 } 409 out: 410 rcu_read_unlock(); 411 cb->args[1] = e; 412 cb->args[0] = h; 413 414 res = res < 0 ? res : skb->len; 415 if (res <= 0) 416 fib6_dump_end(cb); 417 return res; 418 } 419 420 /* 421 * Routing Table 422 * 423 * return the appropriate node for a routing tree "add" operation 424 * by either creating and inserting or by returning an existing 425 * node. 426 */ 427 428 static struct fib6_node * fib6_add_1(struct fib6_node *root, void *addr, 429 int addrlen, int plen, 430 int offset, int allow_create, 431 int replace_required) 432 { 433 struct fib6_node *fn, *in, *ln; 434 struct fib6_node *pn = NULL; 435 struct rt6key *key; 436 int bit; 437 __be32 dir = 0; 438 __u32 sernum = fib6_new_sernum(); 439 440 RT6_TRACE("fib6_add_1\n"); 441 442 /* insert node in tree */ 443 444 fn = root; 445 446 do { 447 key = (struct rt6key *)((u8 *)fn->leaf + offset); 448 449 /* 450 * Prefix match 451 */ 452 if (plen < fn->fn_bit || 453 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) { 454 if (!allow_create) { 455 if (replace_required) { 456 pr_warn("Can't replace route, no match found\n"); 457 return ERR_PTR(-ENOENT); 458 } 459 pr_warn("NLM_F_CREATE should be set when creating new route\n"); 460 } 461 goto insert_above; 462 } 463 464 /* 465 * Exact match ? 466 */ 467 468 if (plen == fn->fn_bit) { 469 /* clean up an intermediate node */ 470 if (!(fn->fn_flags & RTN_RTINFO)) { 471 rt6_release(fn->leaf); 472 fn->leaf = NULL; 473 } 474 475 fn->fn_sernum = sernum; 476 477 return fn; 478 } 479 480 /* 481 * We have more bits to go 482 */ 483 484 /* Try to walk down on tree. */ 485 fn->fn_sernum = sernum; 486 dir = addr_bit_set(addr, fn->fn_bit); 487 pn = fn; 488 fn = dir ? fn->right: fn->left; 489 } while (fn); 490 491 if (!allow_create) { 492 /* We should not create new node because 493 * NLM_F_REPLACE was specified without NLM_F_CREATE 494 * I assume it is safe to require NLM_F_CREATE when 495 * REPLACE flag is used! Later we may want to remove the 496 * check for replace_required, because according 497 * to netlink specification, NLM_F_CREATE 498 * MUST be specified if new route is created. 499 * That would keep IPv6 consistent with IPv4 500 */ 501 if (replace_required) { 502 pr_warn("Can't replace route, no match found\n"); 503 return ERR_PTR(-ENOENT); 504 } 505 pr_warn("NLM_F_CREATE should be set when creating new route\n"); 506 } 507 /* 508 * We walked to the bottom of tree. 509 * Create new leaf node without children. 510 */ 511 512 ln = node_alloc(); 513 514 if (!ln) 515 return ERR_PTR(-ENOMEM); 516 ln->fn_bit = plen; 517 518 ln->parent = pn; 519 ln->fn_sernum = sernum; 520 521 if (dir) 522 pn->right = ln; 523 else 524 pn->left = ln; 525 526 return ln; 527 528 529 insert_above: 530 /* 531 * split since we don't have a common prefix anymore or 532 * we have a less significant route. 533 * we've to insert an intermediate node on the list 534 * this new node will point to the one we need to create 535 * and the current 536 */ 537 538 pn = fn->parent; 539 540 /* find 1st bit in difference between the 2 addrs. 541 542 See comment in __ipv6_addr_diff: bit may be an invalid value, 543 but if it is >= plen, the value is ignored in any case. 544 */ 545 546 bit = __ipv6_addr_diff(addr, &key->addr, addrlen); 547 548 /* 549 * (intermediate)[in] 550 * / \ 551 * (new leaf node)[ln] (old node)[fn] 552 */ 553 if (plen > bit) { 554 in = node_alloc(); 555 ln = node_alloc(); 556 557 if (!in || !ln) { 558 if (in) 559 node_free(in); 560 if (ln) 561 node_free(ln); 562 return ERR_PTR(-ENOMEM); 563 } 564 565 /* 566 * new intermediate node. 567 * RTN_RTINFO will 568 * be off since that an address that chooses one of 569 * the branches would not match less specific routes 570 * in the other branch 571 */ 572 573 in->fn_bit = bit; 574 575 in->parent = pn; 576 in->leaf = fn->leaf; 577 atomic_inc(&in->leaf->rt6i_ref); 578 579 in->fn_sernum = sernum; 580 581 /* update parent pointer */ 582 if (dir) 583 pn->right = in; 584 else 585 pn->left = in; 586 587 ln->fn_bit = plen; 588 589 ln->parent = in; 590 fn->parent = in; 591 592 ln->fn_sernum = sernum; 593 594 if (addr_bit_set(addr, bit)) { 595 in->right = ln; 596 in->left = fn; 597 } else { 598 in->left = ln; 599 in->right = fn; 600 } 601 } else { /* plen <= bit */ 602 603 /* 604 * (new leaf node)[ln] 605 * / \ 606 * (old node)[fn] NULL 607 */ 608 609 ln = node_alloc(); 610 611 if (!ln) 612 return ERR_PTR(-ENOMEM); 613 614 ln->fn_bit = plen; 615 616 ln->parent = pn; 617 618 ln->fn_sernum = sernum; 619 620 if (dir) 621 pn->right = ln; 622 else 623 pn->left = ln; 624 625 if (addr_bit_set(&key->addr, plen)) 626 ln->right = fn; 627 else 628 ln->left = fn; 629 630 fn->parent = ln; 631 } 632 return ln; 633 } 634 635 static inline bool rt6_qualify_for_ecmp(struct rt6_info *rt) 636 { 637 return (rt->rt6i_flags & (RTF_GATEWAY|RTF_ADDRCONF|RTF_DYNAMIC)) == 638 RTF_GATEWAY; 639 } 640 641 /* 642 * Insert routing information in a node. 643 */ 644 645 static int fib6_add_rt2node(struct fib6_node *fn, struct rt6_info *rt, 646 struct nl_info *info) 647 { 648 struct rt6_info *iter = NULL; 649 struct rt6_info **ins; 650 int replace = (info->nlh && 651 (info->nlh->nlmsg_flags & NLM_F_REPLACE)); 652 int add = (!info->nlh || 653 (info->nlh->nlmsg_flags & NLM_F_CREATE)); 654 int found = 0; 655 bool rt_can_ecmp = rt6_qualify_for_ecmp(rt); 656 657 ins = &fn->leaf; 658 659 for (iter = fn->leaf; iter; iter = iter->dst.rt6_next) { 660 /* 661 * Search for duplicates 662 */ 663 664 if (iter->rt6i_metric == rt->rt6i_metric) { 665 /* 666 * Same priority level 667 */ 668 if (info->nlh && 669 (info->nlh->nlmsg_flags & NLM_F_EXCL)) 670 return -EEXIST; 671 if (replace) { 672 found++; 673 break; 674 } 675 676 if (iter->dst.dev == rt->dst.dev && 677 iter->rt6i_idev == rt->rt6i_idev && 678 ipv6_addr_equal(&iter->rt6i_gateway, 679 &rt->rt6i_gateway)) { 680 if (rt->rt6i_nsiblings) 681 rt->rt6i_nsiblings = 0; 682 if (!(iter->rt6i_flags & RTF_EXPIRES)) 683 return -EEXIST; 684 if (!(rt->rt6i_flags & RTF_EXPIRES)) 685 rt6_clean_expires(iter); 686 else 687 rt6_set_expires(iter, rt->dst.expires); 688 return -EEXIST; 689 } 690 /* If we have the same destination and the same metric, 691 * but not the same gateway, then the route we try to 692 * add is sibling to this route, increment our counter 693 * of siblings, and later we will add our route to the 694 * list. 695 * Only static routes (which don't have flag 696 * RTF_EXPIRES) are used for ECMPv6. 697 * 698 * To avoid long list, we only had siblings if the 699 * route have a gateway. 700 */ 701 if (rt_can_ecmp && 702 rt6_qualify_for_ecmp(iter)) 703 rt->rt6i_nsiblings++; 704 } 705 706 if (iter->rt6i_metric > rt->rt6i_metric) 707 break; 708 709 ins = &iter->dst.rt6_next; 710 } 711 712 /* Reset round-robin state, if necessary */ 713 if (ins == &fn->leaf) 714 fn->rr_ptr = NULL; 715 716 /* Link this route to others same route. */ 717 if (rt->rt6i_nsiblings) { 718 unsigned int rt6i_nsiblings; 719 struct rt6_info *sibling, *temp_sibling; 720 721 /* Find the first route that have the same metric */ 722 sibling = fn->leaf; 723 while (sibling) { 724 if (sibling->rt6i_metric == rt->rt6i_metric && 725 rt6_qualify_for_ecmp(sibling)) { 726 list_add_tail(&rt->rt6i_siblings, 727 &sibling->rt6i_siblings); 728 break; 729 } 730 sibling = sibling->dst.rt6_next; 731 } 732 /* For each sibling in the list, increment the counter of 733 * siblings. BUG() if counters does not match, list of siblings 734 * is broken! 735 */ 736 rt6i_nsiblings = 0; 737 list_for_each_entry_safe(sibling, temp_sibling, 738 &rt->rt6i_siblings, rt6i_siblings) { 739 sibling->rt6i_nsiblings++; 740 BUG_ON(sibling->rt6i_nsiblings != rt->rt6i_nsiblings); 741 rt6i_nsiblings++; 742 } 743 BUG_ON(rt6i_nsiblings != rt->rt6i_nsiblings); 744 } 745 746 /* 747 * insert node 748 */ 749 if (!replace) { 750 if (!add) 751 pr_warn("NLM_F_CREATE should be set when creating new route\n"); 752 753 add: 754 rt->dst.rt6_next = iter; 755 *ins = rt; 756 rt->rt6i_node = fn; 757 atomic_inc(&rt->rt6i_ref); 758 inet6_rt_notify(RTM_NEWROUTE, rt, info); 759 info->nl_net->ipv6.rt6_stats->fib_rt_entries++; 760 761 if (!(fn->fn_flags & RTN_RTINFO)) { 762 info->nl_net->ipv6.rt6_stats->fib_route_nodes++; 763 fn->fn_flags |= RTN_RTINFO; 764 } 765 766 } else { 767 if (!found) { 768 if (add) 769 goto add; 770 pr_warn("NLM_F_REPLACE set, but no existing node found!\n"); 771 return -ENOENT; 772 } 773 *ins = rt; 774 rt->rt6i_node = fn; 775 rt->dst.rt6_next = iter->dst.rt6_next; 776 atomic_inc(&rt->rt6i_ref); 777 inet6_rt_notify(RTM_NEWROUTE, rt, info); 778 rt6_release(iter); 779 if (!(fn->fn_flags & RTN_RTINFO)) { 780 info->nl_net->ipv6.rt6_stats->fib_route_nodes++; 781 fn->fn_flags |= RTN_RTINFO; 782 } 783 } 784 785 return 0; 786 } 787 788 static __inline__ void fib6_start_gc(struct net *net, struct rt6_info *rt) 789 { 790 if (!timer_pending(&net->ipv6.ip6_fib_timer) && 791 (rt->rt6i_flags & (RTF_EXPIRES | RTF_CACHE))) 792 mod_timer(&net->ipv6.ip6_fib_timer, 793 jiffies + net->ipv6.sysctl.ip6_rt_gc_interval); 794 } 795 796 void fib6_force_start_gc(struct net *net) 797 { 798 if (!timer_pending(&net->ipv6.ip6_fib_timer)) 799 mod_timer(&net->ipv6.ip6_fib_timer, 800 jiffies + net->ipv6.sysctl.ip6_rt_gc_interval); 801 } 802 803 /* 804 * Add routing information to the routing tree. 805 * <destination addr>/<source addr> 806 * with source addr info in sub-trees 807 */ 808 809 int fib6_add(struct fib6_node *root, struct rt6_info *rt, struct nl_info *info) 810 { 811 struct fib6_node *fn, *pn = NULL; 812 int err = -ENOMEM; 813 int allow_create = 1; 814 int replace_required = 0; 815 816 if (info->nlh) { 817 if (!(info->nlh->nlmsg_flags & NLM_F_CREATE)) 818 allow_create = 0; 819 if (info->nlh->nlmsg_flags & NLM_F_REPLACE) 820 replace_required = 1; 821 } 822 if (!allow_create && !replace_required) 823 pr_warn("RTM_NEWROUTE with no NLM_F_CREATE or NLM_F_REPLACE\n"); 824 825 fn = fib6_add_1(root, &rt->rt6i_dst.addr, sizeof(struct in6_addr), 826 rt->rt6i_dst.plen, offsetof(struct rt6_info, rt6i_dst), 827 allow_create, replace_required); 828 829 if (IS_ERR(fn)) { 830 err = PTR_ERR(fn); 831 goto out; 832 } 833 834 pn = fn; 835 836 #ifdef CONFIG_IPV6_SUBTREES 837 if (rt->rt6i_src.plen) { 838 struct fib6_node *sn; 839 840 if (!fn->subtree) { 841 struct fib6_node *sfn; 842 843 /* 844 * Create subtree. 845 * 846 * fn[main tree] 847 * | 848 * sfn[subtree root] 849 * \ 850 * sn[new leaf node] 851 */ 852 853 /* Create subtree root node */ 854 sfn = node_alloc(); 855 if (!sfn) 856 goto st_failure; 857 858 sfn->leaf = info->nl_net->ipv6.ip6_null_entry; 859 atomic_inc(&info->nl_net->ipv6.ip6_null_entry->rt6i_ref); 860 sfn->fn_flags = RTN_ROOT; 861 sfn->fn_sernum = fib6_new_sernum(); 862 863 /* Now add the first leaf node to new subtree */ 864 865 sn = fib6_add_1(sfn, &rt->rt6i_src.addr, 866 sizeof(struct in6_addr), rt->rt6i_src.plen, 867 offsetof(struct rt6_info, rt6i_src), 868 allow_create, replace_required); 869 870 if (IS_ERR(sn)) { 871 /* If it is failed, discard just allocated 872 root, and then (in st_failure) stale node 873 in main tree. 874 */ 875 node_free(sfn); 876 err = PTR_ERR(sn); 877 goto st_failure; 878 } 879 880 /* Now link new subtree to main tree */ 881 sfn->parent = fn; 882 fn->subtree = sfn; 883 } else { 884 sn = fib6_add_1(fn->subtree, &rt->rt6i_src.addr, 885 sizeof(struct in6_addr), rt->rt6i_src.plen, 886 offsetof(struct rt6_info, rt6i_src), 887 allow_create, replace_required); 888 889 if (IS_ERR(sn)) { 890 err = PTR_ERR(sn); 891 goto st_failure; 892 } 893 } 894 895 if (!fn->leaf) { 896 fn->leaf = rt; 897 atomic_inc(&rt->rt6i_ref); 898 } 899 fn = sn; 900 } 901 #endif 902 903 err = fib6_add_rt2node(fn, rt, info); 904 if (!err) { 905 fib6_start_gc(info->nl_net, rt); 906 if (!(rt->rt6i_flags & RTF_CACHE)) 907 fib6_prune_clones(info->nl_net, pn, rt); 908 } 909 910 out: 911 if (err) { 912 #ifdef CONFIG_IPV6_SUBTREES 913 /* 914 * If fib6_add_1 has cleared the old leaf pointer in the 915 * super-tree leaf node we have to find a new one for it. 916 */ 917 if (pn != fn && pn->leaf == rt) { 918 pn->leaf = NULL; 919 atomic_dec(&rt->rt6i_ref); 920 } 921 if (pn != fn && !pn->leaf && !(pn->fn_flags & RTN_RTINFO)) { 922 pn->leaf = fib6_find_prefix(info->nl_net, pn); 923 #if RT6_DEBUG >= 2 924 if (!pn->leaf) { 925 WARN_ON(pn->leaf == NULL); 926 pn->leaf = info->nl_net->ipv6.ip6_null_entry; 927 } 928 #endif 929 atomic_inc(&pn->leaf->rt6i_ref); 930 } 931 #endif 932 dst_free(&rt->dst); 933 } 934 return err; 935 936 #ifdef CONFIG_IPV6_SUBTREES 937 /* Subtree creation failed, probably main tree node 938 is orphan. If it is, shoot it. 939 */ 940 st_failure: 941 if (fn && !(fn->fn_flags & (RTN_RTINFO|RTN_ROOT))) 942 fib6_repair_tree(info->nl_net, fn); 943 dst_free(&rt->dst); 944 return err; 945 #endif 946 } 947 948 /* 949 * Routing tree lookup 950 * 951 */ 952 953 struct lookup_args { 954 int offset; /* key offset on rt6_info */ 955 const struct in6_addr *addr; /* search key */ 956 }; 957 958 static struct fib6_node * fib6_lookup_1(struct fib6_node *root, 959 struct lookup_args *args) 960 { 961 struct fib6_node *fn; 962 __be32 dir; 963 964 if (unlikely(args->offset == 0)) 965 return NULL; 966 967 /* 968 * Descend on a tree 969 */ 970 971 fn = root; 972 973 for (;;) { 974 struct fib6_node *next; 975 976 dir = addr_bit_set(args->addr, fn->fn_bit); 977 978 next = dir ? fn->right : fn->left; 979 980 if (next) { 981 fn = next; 982 continue; 983 } 984 break; 985 } 986 987 while (fn) { 988 if (FIB6_SUBTREE(fn) || fn->fn_flags & RTN_RTINFO) { 989 struct rt6key *key; 990 991 key = (struct rt6key *) ((u8 *) fn->leaf + 992 args->offset); 993 994 if (ipv6_prefix_equal(&key->addr, args->addr, key->plen)) { 995 #ifdef CONFIG_IPV6_SUBTREES 996 if (fn->subtree) 997 fn = fib6_lookup_1(fn->subtree, args + 1); 998 #endif 999 if (!fn || fn->fn_flags & RTN_RTINFO) 1000 return fn; 1001 } 1002 } 1003 1004 if (fn->fn_flags & RTN_ROOT) 1005 break; 1006 1007 fn = fn->parent; 1008 } 1009 1010 return NULL; 1011 } 1012 1013 struct fib6_node * fib6_lookup(struct fib6_node *root, const struct in6_addr *daddr, 1014 const struct in6_addr *saddr) 1015 { 1016 struct fib6_node *fn; 1017 struct lookup_args args[] = { 1018 { 1019 .offset = offsetof(struct rt6_info, rt6i_dst), 1020 .addr = daddr, 1021 }, 1022 #ifdef CONFIG_IPV6_SUBTREES 1023 { 1024 .offset = offsetof(struct rt6_info, rt6i_src), 1025 .addr = saddr, 1026 }, 1027 #endif 1028 { 1029 .offset = 0, /* sentinel */ 1030 } 1031 }; 1032 1033 fn = fib6_lookup_1(root, daddr ? args : args + 1); 1034 if (!fn || fn->fn_flags & RTN_TL_ROOT) 1035 fn = root; 1036 1037 return fn; 1038 } 1039 1040 /* 1041 * Get node with specified destination prefix (and source prefix, 1042 * if subtrees are used) 1043 */ 1044 1045 1046 static struct fib6_node * fib6_locate_1(struct fib6_node *root, 1047 const struct in6_addr *addr, 1048 int plen, int offset) 1049 { 1050 struct fib6_node *fn; 1051 1052 for (fn = root; fn ; ) { 1053 struct rt6key *key = (struct rt6key *)((u8 *)fn->leaf + offset); 1054 1055 /* 1056 * Prefix match 1057 */ 1058 if (plen < fn->fn_bit || 1059 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) 1060 return NULL; 1061 1062 if (plen == fn->fn_bit) 1063 return fn; 1064 1065 /* 1066 * We have more bits to go 1067 */ 1068 if (addr_bit_set(addr, fn->fn_bit)) 1069 fn = fn->right; 1070 else 1071 fn = fn->left; 1072 } 1073 return NULL; 1074 } 1075 1076 struct fib6_node * fib6_locate(struct fib6_node *root, 1077 const struct in6_addr *daddr, int dst_len, 1078 const struct in6_addr *saddr, int src_len) 1079 { 1080 struct fib6_node *fn; 1081 1082 fn = fib6_locate_1(root, daddr, dst_len, 1083 offsetof(struct rt6_info, rt6i_dst)); 1084 1085 #ifdef CONFIG_IPV6_SUBTREES 1086 if (src_len) { 1087 WARN_ON(saddr == NULL); 1088 if (fn && fn->subtree) 1089 fn = fib6_locate_1(fn->subtree, saddr, src_len, 1090 offsetof(struct rt6_info, rt6i_src)); 1091 } 1092 #endif 1093 1094 if (fn && fn->fn_flags & RTN_RTINFO) 1095 return fn; 1096 1097 return NULL; 1098 } 1099 1100 1101 /* 1102 * Deletion 1103 * 1104 */ 1105 1106 static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn) 1107 { 1108 if (fn->fn_flags & RTN_ROOT) 1109 return net->ipv6.ip6_null_entry; 1110 1111 while (fn) { 1112 if (fn->left) 1113 return fn->left->leaf; 1114 if (fn->right) 1115 return fn->right->leaf; 1116 1117 fn = FIB6_SUBTREE(fn); 1118 } 1119 return NULL; 1120 } 1121 1122 /* 1123 * Called to trim the tree of intermediate nodes when possible. "fn" 1124 * is the node we want to try and remove. 1125 */ 1126 1127 static struct fib6_node *fib6_repair_tree(struct net *net, 1128 struct fib6_node *fn) 1129 { 1130 int children; 1131 int nstate; 1132 struct fib6_node *child, *pn; 1133 struct fib6_walker_t *w; 1134 int iter = 0; 1135 1136 for (;;) { 1137 RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter); 1138 iter++; 1139 1140 WARN_ON(fn->fn_flags & RTN_RTINFO); 1141 WARN_ON(fn->fn_flags & RTN_TL_ROOT); 1142 WARN_ON(fn->leaf != NULL); 1143 1144 children = 0; 1145 child = NULL; 1146 if (fn->right) child = fn->right, children |= 1; 1147 if (fn->left) child = fn->left, children |= 2; 1148 1149 if (children == 3 || FIB6_SUBTREE(fn) 1150 #ifdef CONFIG_IPV6_SUBTREES 1151 /* Subtree root (i.e. fn) may have one child */ 1152 || (children && fn->fn_flags & RTN_ROOT) 1153 #endif 1154 ) { 1155 fn->leaf = fib6_find_prefix(net, fn); 1156 #if RT6_DEBUG >= 2 1157 if (!fn->leaf) { 1158 WARN_ON(!fn->leaf); 1159 fn->leaf = net->ipv6.ip6_null_entry; 1160 } 1161 #endif 1162 atomic_inc(&fn->leaf->rt6i_ref); 1163 return fn->parent; 1164 } 1165 1166 pn = fn->parent; 1167 #ifdef CONFIG_IPV6_SUBTREES 1168 if (FIB6_SUBTREE(pn) == fn) { 1169 WARN_ON(!(fn->fn_flags & RTN_ROOT)); 1170 FIB6_SUBTREE(pn) = NULL; 1171 nstate = FWS_L; 1172 } else { 1173 WARN_ON(fn->fn_flags & RTN_ROOT); 1174 #endif 1175 if (pn->right == fn) pn->right = child; 1176 else if (pn->left == fn) pn->left = child; 1177 #if RT6_DEBUG >= 2 1178 else 1179 WARN_ON(1); 1180 #endif 1181 if (child) 1182 child->parent = pn; 1183 nstate = FWS_R; 1184 #ifdef CONFIG_IPV6_SUBTREES 1185 } 1186 #endif 1187 1188 read_lock(&fib6_walker_lock); 1189 FOR_WALKERS(w) { 1190 if (!child) { 1191 if (w->root == fn) { 1192 w->root = w->node = NULL; 1193 RT6_TRACE("W %p adjusted by delroot 1\n", w); 1194 } else if (w->node == fn) { 1195 RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w, w->state, nstate); 1196 w->node = pn; 1197 w->state = nstate; 1198 } 1199 } else { 1200 if (w->root == fn) { 1201 w->root = child; 1202 RT6_TRACE("W %p adjusted by delroot 2\n", w); 1203 } 1204 if (w->node == fn) { 1205 w->node = child; 1206 if (children&2) { 1207 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state); 1208 w->state = w->state>=FWS_R ? FWS_U : FWS_INIT; 1209 } else { 1210 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state); 1211 w->state = w->state>=FWS_C ? FWS_U : FWS_INIT; 1212 } 1213 } 1214 } 1215 } 1216 read_unlock(&fib6_walker_lock); 1217 1218 node_free(fn); 1219 if (pn->fn_flags & RTN_RTINFO || FIB6_SUBTREE(pn)) 1220 return pn; 1221 1222 rt6_release(pn->leaf); 1223 pn->leaf = NULL; 1224 fn = pn; 1225 } 1226 } 1227 1228 static void fib6_del_route(struct fib6_node *fn, struct rt6_info **rtp, 1229 struct nl_info *info) 1230 { 1231 struct fib6_walker_t *w; 1232 struct rt6_info *rt = *rtp; 1233 struct net *net = info->nl_net; 1234 1235 RT6_TRACE("fib6_del_route\n"); 1236 1237 /* Unlink it */ 1238 *rtp = rt->dst.rt6_next; 1239 rt->rt6i_node = NULL; 1240 net->ipv6.rt6_stats->fib_rt_entries--; 1241 net->ipv6.rt6_stats->fib_discarded_routes++; 1242 1243 /* Reset round-robin state, if necessary */ 1244 if (fn->rr_ptr == rt) 1245 fn->rr_ptr = NULL; 1246 1247 /* Remove this entry from other siblings */ 1248 if (rt->rt6i_nsiblings) { 1249 struct rt6_info *sibling, *next_sibling; 1250 1251 list_for_each_entry_safe(sibling, next_sibling, 1252 &rt->rt6i_siblings, rt6i_siblings) 1253 sibling->rt6i_nsiblings--; 1254 rt->rt6i_nsiblings = 0; 1255 list_del_init(&rt->rt6i_siblings); 1256 } 1257 1258 /* Adjust walkers */ 1259 read_lock(&fib6_walker_lock); 1260 FOR_WALKERS(w) { 1261 if (w->state == FWS_C && w->leaf == rt) { 1262 RT6_TRACE("walker %p adjusted by delroute\n", w); 1263 w->leaf = rt->dst.rt6_next; 1264 if (!w->leaf) 1265 w->state = FWS_U; 1266 } 1267 } 1268 read_unlock(&fib6_walker_lock); 1269 1270 rt->dst.rt6_next = NULL; 1271 1272 /* If it was last route, expunge its radix tree node */ 1273 if (!fn->leaf) { 1274 fn->fn_flags &= ~RTN_RTINFO; 1275 net->ipv6.rt6_stats->fib_route_nodes--; 1276 fn = fib6_repair_tree(net, fn); 1277 } 1278 1279 if (atomic_read(&rt->rt6i_ref) != 1) { 1280 /* This route is used as dummy address holder in some split 1281 * nodes. It is not leaked, but it still holds other resources, 1282 * which must be released in time. So, scan ascendant nodes 1283 * and replace dummy references to this route with references 1284 * to still alive ones. 1285 */ 1286 while (fn) { 1287 if (!(fn->fn_flags & RTN_RTINFO) && fn->leaf == rt) { 1288 fn->leaf = fib6_find_prefix(net, fn); 1289 atomic_inc(&fn->leaf->rt6i_ref); 1290 rt6_release(rt); 1291 } 1292 fn = fn->parent; 1293 } 1294 /* No more references are possible at this point. */ 1295 BUG_ON(atomic_read(&rt->rt6i_ref) != 1); 1296 } 1297 1298 inet6_rt_notify(RTM_DELROUTE, rt, info); 1299 rt6_release(rt); 1300 } 1301 1302 int fib6_del(struct rt6_info *rt, struct nl_info *info) 1303 { 1304 struct net *net = info->nl_net; 1305 struct fib6_node *fn = rt->rt6i_node; 1306 struct rt6_info **rtp; 1307 1308 #if RT6_DEBUG >= 2 1309 if (rt->dst.obsolete>0) { 1310 WARN_ON(fn != NULL); 1311 return -ENOENT; 1312 } 1313 #endif 1314 if (!fn || rt == net->ipv6.ip6_null_entry) 1315 return -ENOENT; 1316 1317 WARN_ON(!(fn->fn_flags & RTN_RTINFO)); 1318 1319 if (!(rt->rt6i_flags & RTF_CACHE)) { 1320 struct fib6_node *pn = fn; 1321 #ifdef CONFIG_IPV6_SUBTREES 1322 /* clones of this route might be in another subtree */ 1323 if (rt->rt6i_src.plen) { 1324 while (!(pn->fn_flags & RTN_ROOT)) 1325 pn = pn->parent; 1326 pn = pn->parent; 1327 } 1328 #endif 1329 fib6_prune_clones(info->nl_net, pn, rt); 1330 } 1331 1332 /* 1333 * Walk the leaf entries looking for ourself 1334 */ 1335 1336 for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->dst.rt6_next) { 1337 if (*rtp == rt) { 1338 fib6_del_route(fn, rtp, info); 1339 return 0; 1340 } 1341 } 1342 return -ENOENT; 1343 } 1344 1345 /* 1346 * Tree traversal function. 1347 * 1348 * Certainly, it is not interrupt safe. 1349 * However, it is internally reenterable wrt itself and fib6_add/fib6_del. 1350 * It means, that we can modify tree during walking 1351 * and use this function for garbage collection, clone pruning, 1352 * cleaning tree when a device goes down etc. etc. 1353 * 1354 * It guarantees that every node will be traversed, 1355 * and that it will be traversed only once. 1356 * 1357 * Callback function w->func may return: 1358 * 0 -> continue walking. 1359 * positive value -> walking is suspended (used by tree dumps, 1360 * and probably by gc, if it will be split to several slices) 1361 * negative value -> terminate walking. 1362 * 1363 * The function itself returns: 1364 * 0 -> walk is complete. 1365 * >0 -> walk is incomplete (i.e. suspended) 1366 * <0 -> walk is terminated by an error. 1367 */ 1368 1369 static int fib6_walk_continue(struct fib6_walker_t *w) 1370 { 1371 struct fib6_node *fn, *pn; 1372 1373 for (;;) { 1374 fn = w->node; 1375 if (!fn) 1376 return 0; 1377 1378 if (w->prune && fn != w->root && 1379 fn->fn_flags & RTN_RTINFO && w->state < FWS_C) { 1380 w->state = FWS_C; 1381 w->leaf = fn->leaf; 1382 } 1383 switch (w->state) { 1384 #ifdef CONFIG_IPV6_SUBTREES 1385 case FWS_S: 1386 if (FIB6_SUBTREE(fn)) { 1387 w->node = FIB6_SUBTREE(fn); 1388 continue; 1389 } 1390 w->state = FWS_L; 1391 #endif 1392 case FWS_L: 1393 if (fn->left) { 1394 w->node = fn->left; 1395 w->state = FWS_INIT; 1396 continue; 1397 } 1398 w->state = FWS_R; 1399 case FWS_R: 1400 if (fn->right) { 1401 w->node = fn->right; 1402 w->state = FWS_INIT; 1403 continue; 1404 } 1405 w->state = FWS_C; 1406 w->leaf = fn->leaf; 1407 case FWS_C: 1408 if (w->leaf && fn->fn_flags & RTN_RTINFO) { 1409 int err; 1410 1411 if (w->skip) { 1412 w->skip--; 1413 continue; 1414 } 1415 1416 err = w->func(w); 1417 if (err) 1418 return err; 1419 1420 w->count++; 1421 continue; 1422 } 1423 w->state = FWS_U; 1424 case FWS_U: 1425 if (fn == w->root) 1426 return 0; 1427 pn = fn->parent; 1428 w->node = pn; 1429 #ifdef CONFIG_IPV6_SUBTREES 1430 if (FIB6_SUBTREE(pn) == fn) { 1431 WARN_ON(!(fn->fn_flags & RTN_ROOT)); 1432 w->state = FWS_L; 1433 continue; 1434 } 1435 #endif 1436 if (pn->left == fn) { 1437 w->state = FWS_R; 1438 continue; 1439 } 1440 if (pn->right == fn) { 1441 w->state = FWS_C; 1442 w->leaf = w->node->leaf; 1443 continue; 1444 } 1445 #if RT6_DEBUG >= 2 1446 WARN_ON(1); 1447 #endif 1448 } 1449 } 1450 } 1451 1452 static int fib6_walk(struct fib6_walker_t *w) 1453 { 1454 int res; 1455 1456 w->state = FWS_INIT; 1457 w->node = w->root; 1458 1459 fib6_walker_link(w); 1460 res = fib6_walk_continue(w); 1461 if (res <= 0) 1462 fib6_walker_unlink(w); 1463 return res; 1464 } 1465 1466 static int fib6_clean_node(struct fib6_walker_t *w) 1467 { 1468 int res; 1469 struct rt6_info *rt; 1470 struct fib6_cleaner_t *c = container_of(w, struct fib6_cleaner_t, w); 1471 struct nl_info info = { 1472 .nl_net = c->net, 1473 }; 1474 1475 for (rt = w->leaf; rt; rt = rt->dst.rt6_next) { 1476 res = c->func(rt, c->arg); 1477 if (res < 0) { 1478 w->leaf = rt; 1479 res = fib6_del(rt, &info); 1480 if (res) { 1481 #if RT6_DEBUG >= 2 1482 pr_debug("%s: del failed: rt=%p@%p err=%d\n", 1483 __func__, rt, rt->rt6i_node, res); 1484 #endif 1485 continue; 1486 } 1487 return 0; 1488 } 1489 WARN_ON(res != 0); 1490 } 1491 w->leaf = rt; 1492 return 0; 1493 } 1494 1495 /* 1496 * Convenient frontend to tree walker. 1497 * 1498 * func is called on each route. 1499 * It may return -1 -> delete this route. 1500 * 0 -> continue walking 1501 * 1502 * prune==1 -> only immediate children of node (certainly, 1503 * ignoring pure split nodes) will be scanned. 1504 */ 1505 1506 static void fib6_clean_tree(struct net *net, struct fib6_node *root, 1507 int (*func)(struct rt6_info *, void *arg), 1508 int prune, void *arg) 1509 { 1510 struct fib6_cleaner_t c; 1511 1512 c.w.root = root; 1513 c.w.func = fib6_clean_node; 1514 c.w.prune = prune; 1515 c.w.count = 0; 1516 c.w.skip = 0; 1517 c.func = func; 1518 c.arg = arg; 1519 c.net = net; 1520 1521 fib6_walk(&c.w); 1522 } 1523 1524 void fib6_clean_all_ro(struct net *net, int (*func)(struct rt6_info *, void *arg), 1525 int prune, void *arg) 1526 { 1527 struct fib6_table *table; 1528 struct hlist_head *head; 1529 unsigned int h; 1530 1531 rcu_read_lock(); 1532 for (h = 0; h < FIB6_TABLE_HASHSZ; h++) { 1533 head = &net->ipv6.fib_table_hash[h]; 1534 hlist_for_each_entry_rcu(table, head, tb6_hlist) { 1535 read_lock_bh(&table->tb6_lock); 1536 fib6_clean_tree(net, &table->tb6_root, 1537 func, prune, arg); 1538 read_unlock_bh(&table->tb6_lock); 1539 } 1540 } 1541 rcu_read_unlock(); 1542 } 1543 void fib6_clean_all(struct net *net, int (*func)(struct rt6_info *, void *arg), 1544 int prune, void *arg) 1545 { 1546 struct fib6_table *table; 1547 struct hlist_head *head; 1548 unsigned int h; 1549 1550 rcu_read_lock(); 1551 for (h = 0; h < FIB6_TABLE_HASHSZ; h++) { 1552 head = &net->ipv6.fib_table_hash[h]; 1553 hlist_for_each_entry_rcu(table, head, tb6_hlist) { 1554 write_lock_bh(&table->tb6_lock); 1555 fib6_clean_tree(net, &table->tb6_root, 1556 func, prune, arg); 1557 write_unlock_bh(&table->tb6_lock); 1558 } 1559 } 1560 rcu_read_unlock(); 1561 } 1562 1563 static int fib6_prune_clone(struct rt6_info *rt, void *arg) 1564 { 1565 if (rt->rt6i_flags & RTF_CACHE) { 1566 RT6_TRACE("pruning clone %p\n", rt); 1567 return -1; 1568 } 1569 1570 return 0; 1571 } 1572 1573 static void fib6_prune_clones(struct net *net, struct fib6_node *fn, 1574 struct rt6_info *rt) 1575 { 1576 fib6_clean_tree(net, fn, fib6_prune_clone, 1, rt); 1577 } 1578 1579 /* 1580 * Garbage collection 1581 */ 1582 1583 static struct fib6_gc_args 1584 { 1585 int timeout; 1586 int more; 1587 } gc_args; 1588 1589 static int fib6_age(struct rt6_info *rt, void *arg) 1590 { 1591 unsigned long now = jiffies; 1592 1593 /* 1594 * check addrconf expiration here. 1595 * Routes are expired even if they are in use. 1596 * 1597 * Also age clones. Note, that clones are aged out 1598 * only if they are not in use now. 1599 */ 1600 1601 if (rt->rt6i_flags & RTF_EXPIRES && rt->dst.expires) { 1602 if (time_after(now, rt->dst.expires)) { 1603 RT6_TRACE("expiring %p\n", rt); 1604 return -1; 1605 } 1606 gc_args.more++; 1607 } else if (rt->rt6i_flags & RTF_CACHE) { 1608 if (atomic_read(&rt->dst.__refcnt) == 0 && 1609 time_after_eq(now, rt->dst.lastuse + gc_args.timeout)) { 1610 RT6_TRACE("aging clone %p\n", rt); 1611 return -1; 1612 } else if (rt->rt6i_flags & RTF_GATEWAY) { 1613 struct neighbour *neigh; 1614 __u8 neigh_flags = 0; 1615 1616 neigh = dst_neigh_lookup(&rt->dst, &rt->rt6i_gateway); 1617 if (neigh) { 1618 neigh_flags = neigh->flags; 1619 neigh_release(neigh); 1620 } 1621 if (!(neigh_flags & NTF_ROUTER)) { 1622 RT6_TRACE("purging route %p via non-router but gateway\n", 1623 rt); 1624 return -1; 1625 } 1626 } 1627 gc_args.more++; 1628 } 1629 1630 return 0; 1631 } 1632 1633 static DEFINE_SPINLOCK(fib6_gc_lock); 1634 1635 void fib6_run_gc(unsigned long expires, struct net *net) 1636 { 1637 if (expires != ~0UL) { 1638 spin_lock_bh(&fib6_gc_lock); 1639 gc_args.timeout = expires ? (int)expires : 1640 net->ipv6.sysctl.ip6_rt_gc_interval; 1641 } else { 1642 if (!spin_trylock_bh(&fib6_gc_lock)) { 1643 mod_timer(&net->ipv6.ip6_fib_timer, jiffies + HZ); 1644 return; 1645 } 1646 gc_args.timeout = net->ipv6.sysctl.ip6_rt_gc_interval; 1647 } 1648 1649 gc_args.more = icmp6_dst_gc(); 1650 1651 fib6_clean_all(net, fib6_age, 0, NULL); 1652 1653 if (gc_args.more) 1654 mod_timer(&net->ipv6.ip6_fib_timer, 1655 round_jiffies(jiffies 1656 + net->ipv6.sysctl.ip6_rt_gc_interval)); 1657 else 1658 del_timer(&net->ipv6.ip6_fib_timer); 1659 spin_unlock_bh(&fib6_gc_lock); 1660 } 1661 1662 static void fib6_gc_timer_cb(unsigned long arg) 1663 { 1664 fib6_run_gc(0, (struct net *)arg); 1665 } 1666 1667 static int __net_init fib6_net_init(struct net *net) 1668 { 1669 size_t size = sizeof(struct hlist_head) * FIB6_TABLE_HASHSZ; 1670 1671 setup_timer(&net->ipv6.ip6_fib_timer, fib6_gc_timer_cb, (unsigned long)net); 1672 1673 net->ipv6.rt6_stats = kzalloc(sizeof(*net->ipv6.rt6_stats), GFP_KERNEL); 1674 if (!net->ipv6.rt6_stats) 1675 goto out_timer; 1676 1677 /* Avoid false sharing : Use at least a full cache line */ 1678 size = max_t(size_t, size, L1_CACHE_BYTES); 1679 1680 net->ipv6.fib_table_hash = kzalloc(size, GFP_KERNEL); 1681 if (!net->ipv6.fib_table_hash) 1682 goto out_rt6_stats; 1683 1684 net->ipv6.fib6_main_tbl = kzalloc(sizeof(*net->ipv6.fib6_main_tbl), 1685 GFP_KERNEL); 1686 if (!net->ipv6.fib6_main_tbl) 1687 goto out_fib_table_hash; 1688 1689 net->ipv6.fib6_main_tbl->tb6_id = RT6_TABLE_MAIN; 1690 net->ipv6.fib6_main_tbl->tb6_root.leaf = net->ipv6.ip6_null_entry; 1691 net->ipv6.fib6_main_tbl->tb6_root.fn_flags = 1692 RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO; 1693 inet_peer_base_init(&net->ipv6.fib6_main_tbl->tb6_peers); 1694 1695 #ifdef CONFIG_IPV6_MULTIPLE_TABLES 1696 net->ipv6.fib6_local_tbl = kzalloc(sizeof(*net->ipv6.fib6_local_tbl), 1697 GFP_KERNEL); 1698 if (!net->ipv6.fib6_local_tbl) 1699 goto out_fib6_main_tbl; 1700 net->ipv6.fib6_local_tbl->tb6_id = RT6_TABLE_LOCAL; 1701 net->ipv6.fib6_local_tbl->tb6_root.leaf = net->ipv6.ip6_null_entry; 1702 net->ipv6.fib6_local_tbl->tb6_root.fn_flags = 1703 RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO; 1704 inet_peer_base_init(&net->ipv6.fib6_local_tbl->tb6_peers); 1705 #endif 1706 fib6_tables_init(net); 1707 1708 return 0; 1709 1710 #ifdef CONFIG_IPV6_MULTIPLE_TABLES 1711 out_fib6_main_tbl: 1712 kfree(net->ipv6.fib6_main_tbl); 1713 #endif 1714 out_fib_table_hash: 1715 kfree(net->ipv6.fib_table_hash); 1716 out_rt6_stats: 1717 kfree(net->ipv6.rt6_stats); 1718 out_timer: 1719 return -ENOMEM; 1720 } 1721 1722 static void fib6_net_exit(struct net *net) 1723 { 1724 rt6_ifdown(net, NULL); 1725 del_timer_sync(&net->ipv6.ip6_fib_timer); 1726 1727 #ifdef CONFIG_IPV6_MULTIPLE_TABLES 1728 inetpeer_invalidate_tree(&net->ipv6.fib6_local_tbl->tb6_peers); 1729 kfree(net->ipv6.fib6_local_tbl); 1730 #endif 1731 inetpeer_invalidate_tree(&net->ipv6.fib6_main_tbl->tb6_peers); 1732 kfree(net->ipv6.fib6_main_tbl); 1733 kfree(net->ipv6.fib_table_hash); 1734 kfree(net->ipv6.rt6_stats); 1735 } 1736 1737 static struct pernet_operations fib6_net_ops = { 1738 .init = fib6_net_init, 1739 .exit = fib6_net_exit, 1740 }; 1741 1742 int __init fib6_init(void) 1743 { 1744 int ret = -ENOMEM; 1745 1746 fib6_node_kmem = kmem_cache_create("fib6_nodes", 1747 sizeof(struct fib6_node), 1748 0, SLAB_HWCACHE_ALIGN, 1749 NULL); 1750 if (!fib6_node_kmem) 1751 goto out; 1752 1753 ret = register_pernet_subsys(&fib6_net_ops); 1754 if (ret) 1755 goto out_kmem_cache_create; 1756 1757 ret = __rtnl_register(PF_INET6, RTM_GETROUTE, NULL, inet6_dump_fib, 1758 NULL); 1759 if (ret) 1760 goto out_unregister_subsys; 1761 out: 1762 return ret; 1763 1764 out_unregister_subsys: 1765 unregister_pernet_subsys(&fib6_net_ops); 1766 out_kmem_cache_create: 1767 kmem_cache_destroy(fib6_node_kmem); 1768 goto out; 1769 } 1770 1771 void fib6_gc_cleanup(void) 1772 { 1773 unregister_pernet_subsys(&fib6_net_ops); 1774 kmem_cache_destroy(fib6_node_kmem); 1775 } 1776