1 /* 2 * INET An implementation of the TCP/IP protocol suite for the LINUX 3 * operating system. INET is implemented using the BSD Socket 4 * interface as the means of communication with the user level. 5 * 6 * IPv4 Forwarding Information Base: semantics. 7 * 8 * Version: $Id: fib_semantics.c,v 1.19 2002/01/12 07:54:56 davem Exp $ 9 * 10 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru> 11 * 12 * This program is free software; you can redistribute it and/or 13 * modify it under the terms of the GNU General Public License 14 * as published by the Free Software Foundation; either version 15 * 2 of the License, or (at your option) any later version. 16 */ 17 18 #include <asm/uaccess.h> 19 #include <asm/system.h> 20 #include <linux/bitops.h> 21 #include <linux/types.h> 22 #include <linux/kernel.h> 23 #include <linux/jiffies.h> 24 #include <linux/mm.h> 25 #include <linux/string.h> 26 #include <linux/socket.h> 27 #include <linux/sockios.h> 28 #include <linux/errno.h> 29 #include <linux/in.h> 30 #include <linux/inet.h> 31 #include <linux/inetdevice.h> 32 #include <linux/netdevice.h> 33 #include <linux/if_arp.h> 34 #include <linux/proc_fs.h> 35 #include <linux/skbuff.h> 36 #include <linux/init.h> 37 38 #include <net/arp.h> 39 #include <net/ip.h> 40 #include <net/protocol.h> 41 #include <net/route.h> 42 #include <net/tcp.h> 43 #include <net/sock.h> 44 #include <net/ip_fib.h> 45 #include <net/ip_mp_alg.h> 46 #include <net/netlink.h> 47 #include <net/nexthop.h> 48 49 #include "fib_lookup.h" 50 51 #define FSprintk(a...) 52 53 static DEFINE_SPINLOCK(fib_info_lock); 54 static struct hlist_head *fib_info_hash; 55 static struct hlist_head *fib_info_laddrhash; 56 static unsigned int fib_hash_size; 57 static unsigned int fib_info_cnt; 58 59 #define DEVINDEX_HASHBITS 8 60 #define DEVINDEX_HASHSIZE (1U << DEVINDEX_HASHBITS) 61 static struct hlist_head fib_info_devhash[DEVINDEX_HASHSIZE]; 62 63 #ifdef CONFIG_IP_ROUTE_MULTIPATH 64 65 static DEFINE_SPINLOCK(fib_multipath_lock); 66 67 #define for_nexthops(fi) { int nhsel; const struct fib_nh * nh; \ 68 for (nhsel=0, nh = (fi)->fib_nh; nhsel < (fi)->fib_nhs; nh++, nhsel++) 69 70 #define change_nexthops(fi) { int nhsel; struct fib_nh * nh; \ 71 for (nhsel=0, nh = (struct fib_nh*)((fi)->fib_nh); nhsel < (fi)->fib_nhs; nh++, nhsel++) 72 73 #else /* CONFIG_IP_ROUTE_MULTIPATH */ 74 75 /* Hope, that gcc will optimize it to get rid of dummy loop */ 76 77 #define for_nexthops(fi) { int nhsel=0; const struct fib_nh * nh = (fi)->fib_nh; \ 78 for (nhsel=0; nhsel < 1; nhsel++) 79 80 #define change_nexthops(fi) { int nhsel=0; struct fib_nh * nh = (struct fib_nh*)((fi)->fib_nh); \ 81 for (nhsel=0; nhsel < 1; nhsel++) 82 83 #endif /* CONFIG_IP_ROUTE_MULTIPATH */ 84 85 #define endfor_nexthops(fi) } 86 87 88 static const struct 89 { 90 int error; 91 u8 scope; 92 } fib_props[RTA_MAX + 1] = { 93 { 94 .error = 0, 95 .scope = RT_SCOPE_NOWHERE, 96 }, /* RTN_UNSPEC */ 97 { 98 .error = 0, 99 .scope = RT_SCOPE_UNIVERSE, 100 }, /* RTN_UNICAST */ 101 { 102 .error = 0, 103 .scope = RT_SCOPE_HOST, 104 }, /* RTN_LOCAL */ 105 { 106 .error = 0, 107 .scope = RT_SCOPE_LINK, 108 }, /* RTN_BROADCAST */ 109 { 110 .error = 0, 111 .scope = RT_SCOPE_LINK, 112 }, /* RTN_ANYCAST */ 113 { 114 .error = 0, 115 .scope = RT_SCOPE_UNIVERSE, 116 }, /* RTN_MULTICAST */ 117 { 118 .error = -EINVAL, 119 .scope = RT_SCOPE_UNIVERSE, 120 }, /* RTN_BLACKHOLE */ 121 { 122 .error = -EHOSTUNREACH, 123 .scope = RT_SCOPE_UNIVERSE, 124 }, /* RTN_UNREACHABLE */ 125 { 126 .error = -EACCES, 127 .scope = RT_SCOPE_UNIVERSE, 128 }, /* RTN_PROHIBIT */ 129 { 130 .error = -EAGAIN, 131 .scope = RT_SCOPE_UNIVERSE, 132 }, /* RTN_THROW */ 133 { 134 .error = -EINVAL, 135 .scope = RT_SCOPE_NOWHERE, 136 }, /* RTN_NAT */ 137 { 138 .error = -EINVAL, 139 .scope = RT_SCOPE_NOWHERE, 140 }, /* RTN_XRESOLVE */ 141 }; 142 143 144 /* Release a nexthop info record */ 145 146 void free_fib_info(struct fib_info *fi) 147 { 148 if (fi->fib_dead == 0) { 149 printk("Freeing alive fib_info %p\n", fi); 150 return; 151 } 152 change_nexthops(fi) { 153 if (nh->nh_dev) 154 dev_put(nh->nh_dev); 155 nh->nh_dev = NULL; 156 } endfor_nexthops(fi); 157 fib_info_cnt--; 158 kfree(fi); 159 } 160 161 void fib_release_info(struct fib_info *fi) 162 { 163 spin_lock_bh(&fib_info_lock); 164 if (fi && --fi->fib_treeref == 0) { 165 hlist_del(&fi->fib_hash); 166 if (fi->fib_prefsrc) 167 hlist_del(&fi->fib_lhash); 168 change_nexthops(fi) { 169 if (!nh->nh_dev) 170 continue; 171 hlist_del(&nh->nh_hash); 172 } endfor_nexthops(fi) 173 fi->fib_dead = 1; 174 fib_info_put(fi); 175 } 176 spin_unlock_bh(&fib_info_lock); 177 } 178 179 static __inline__ int nh_comp(const struct fib_info *fi, const struct fib_info *ofi) 180 { 181 const struct fib_nh *onh = ofi->fib_nh; 182 183 for_nexthops(fi) { 184 if (nh->nh_oif != onh->nh_oif || 185 nh->nh_gw != onh->nh_gw || 186 nh->nh_scope != onh->nh_scope || 187 #ifdef CONFIG_IP_ROUTE_MULTIPATH 188 nh->nh_weight != onh->nh_weight || 189 #endif 190 #ifdef CONFIG_NET_CLS_ROUTE 191 nh->nh_tclassid != onh->nh_tclassid || 192 #endif 193 ((nh->nh_flags^onh->nh_flags)&~RTNH_F_DEAD)) 194 return -1; 195 onh++; 196 } endfor_nexthops(fi); 197 return 0; 198 } 199 200 static inline unsigned int fib_info_hashfn(const struct fib_info *fi) 201 { 202 unsigned int mask = (fib_hash_size - 1); 203 unsigned int val = fi->fib_nhs; 204 205 val ^= fi->fib_protocol; 206 val ^= (__force u32)fi->fib_prefsrc; 207 val ^= fi->fib_priority; 208 209 return (val ^ (val >> 7) ^ (val >> 12)) & mask; 210 } 211 212 static struct fib_info *fib_find_info(const struct fib_info *nfi) 213 { 214 struct hlist_head *head; 215 struct hlist_node *node; 216 struct fib_info *fi; 217 unsigned int hash; 218 219 hash = fib_info_hashfn(nfi); 220 head = &fib_info_hash[hash]; 221 222 hlist_for_each_entry(fi, node, head, fib_hash) { 223 if (fi->fib_nhs != nfi->fib_nhs) 224 continue; 225 if (nfi->fib_protocol == fi->fib_protocol && 226 nfi->fib_prefsrc == fi->fib_prefsrc && 227 nfi->fib_priority == fi->fib_priority && 228 memcmp(nfi->fib_metrics, fi->fib_metrics, 229 sizeof(fi->fib_metrics)) == 0 && 230 ((nfi->fib_flags^fi->fib_flags)&~RTNH_F_DEAD) == 0 && 231 (nfi->fib_nhs == 0 || nh_comp(fi, nfi) == 0)) 232 return fi; 233 } 234 235 return NULL; 236 } 237 238 static inline unsigned int fib_devindex_hashfn(unsigned int val) 239 { 240 unsigned int mask = DEVINDEX_HASHSIZE - 1; 241 242 return (val ^ 243 (val >> DEVINDEX_HASHBITS) ^ 244 (val >> (DEVINDEX_HASHBITS * 2))) & mask; 245 } 246 247 /* Check, that the gateway is already configured. 248 Used only by redirect accept routine. 249 */ 250 251 int ip_fib_check_default(__be32 gw, struct net_device *dev) 252 { 253 struct hlist_head *head; 254 struct hlist_node *node; 255 struct fib_nh *nh; 256 unsigned int hash; 257 258 spin_lock(&fib_info_lock); 259 260 hash = fib_devindex_hashfn(dev->ifindex); 261 head = &fib_info_devhash[hash]; 262 hlist_for_each_entry(nh, node, head, nh_hash) { 263 if (nh->nh_dev == dev && 264 nh->nh_gw == gw && 265 !(nh->nh_flags&RTNH_F_DEAD)) { 266 spin_unlock(&fib_info_lock); 267 return 0; 268 } 269 } 270 271 spin_unlock(&fib_info_lock); 272 273 return -1; 274 } 275 276 static inline size_t fib_nlmsg_size(struct fib_info *fi) 277 { 278 size_t payload = NLMSG_ALIGN(sizeof(struct rtmsg)) 279 + nla_total_size(4) /* RTA_TABLE */ 280 + nla_total_size(4) /* RTA_DST */ 281 + nla_total_size(4) /* RTA_PRIORITY */ 282 + nla_total_size(4); /* RTA_PREFSRC */ 283 284 /* space for nested metrics */ 285 payload += nla_total_size((RTAX_MAX * nla_total_size(4))); 286 287 if (fi->fib_nhs) { 288 /* Also handles the special case fib_nhs == 1 */ 289 290 /* each nexthop is packed in an attribute */ 291 size_t nhsize = nla_total_size(sizeof(struct rtnexthop)); 292 293 /* may contain flow and gateway attribute */ 294 nhsize += 2 * nla_total_size(4); 295 296 /* all nexthops are packed in a nested attribute */ 297 payload += nla_total_size(fi->fib_nhs * nhsize); 298 } 299 300 return payload; 301 } 302 303 void rtmsg_fib(int event, __be32 key, struct fib_alias *fa, 304 int dst_len, u32 tb_id, struct nl_info *info) 305 { 306 struct sk_buff *skb; 307 u32 seq = info->nlh ? info->nlh->nlmsg_seq : 0; 308 int err = -ENOBUFS; 309 310 skb = nlmsg_new(fib_nlmsg_size(fa->fa_info), GFP_KERNEL); 311 if (skb == NULL) 312 goto errout; 313 314 err = fib_dump_info(skb, info->pid, seq, event, tb_id, 315 fa->fa_type, fa->fa_scope, key, dst_len, 316 fa->fa_tos, fa->fa_info, 0); 317 if (err < 0) { 318 /* -EMSGSIZE implies BUG in fib_nlmsg_size() */ 319 WARN_ON(err == -EMSGSIZE); 320 kfree_skb(skb); 321 goto errout; 322 } 323 err = rtnl_notify(skb, info->pid, RTNLGRP_IPV4_ROUTE, 324 info->nlh, GFP_KERNEL); 325 errout: 326 if (err < 0) 327 rtnl_set_sk_err(RTNLGRP_IPV4_ROUTE, err); 328 } 329 330 /* Return the first fib alias matching TOS with 331 * priority less than or equal to PRIO. 332 */ 333 struct fib_alias *fib_find_alias(struct list_head *fah, u8 tos, u32 prio) 334 { 335 if (fah) { 336 struct fib_alias *fa; 337 list_for_each_entry(fa, fah, fa_list) { 338 if (fa->fa_tos > tos) 339 continue; 340 if (fa->fa_info->fib_priority >= prio || 341 fa->fa_tos < tos) 342 return fa; 343 } 344 } 345 return NULL; 346 } 347 348 int fib_detect_death(struct fib_info *fi, int order, 349 struct fib_info **last_resort, int *last_idx, int *dflt) 350 { 351 struct neighbour *n; 352 int state = NUD_NONE; 353 354 n = neigh_lookup(&arp_tbl, &fi->fib_nh[0].nh_gw, fi->fib_dev); 355 if (n) { 356 state = n->nud_state; 357 neigh_release(n); 358 } 359 if (state==NUD_REACHABLE) 360 return 0; 361 if ((state&NUD_VALID) && order != *dflt) 362 return 0; 363 if ((state&NUD_VALID) || 364 (*last_idx<0 && order > *dflt)) { 365 *last_resort = fi; 366 *last_idx = order; 367 } 368 return 1; 369 } 370 371 #ifdef CONFIG_IP_ROUTE_MULTIPATH 372 373 static int fib_count_nexthops(struct rtnexthop *rtnh, int remaining) 374 { 375 int nhs = 0; 376 377 while (rtnh_ok(rtnh, remaining)) { 378 nhs++; 379 rtnh = rtnh_next(rtnh, &remaining); 380 } 381 382 /* leftover implies invalid nexthop configuration, discard it */ 383 return remaining > 0 ? 0 : nhs; 384 } 385 386 static int fib_get_nhs(struct fib_info *fi, struct rtnexthop *rtnh, 387 int remaining, struct fib_config *cfg) 388 { 389 change_nexthops(fi) { 390 int attrlen; 391 392 if (!rtnh_ok(rtnh, remaining)) 393 return -EINVAL; 394 395 nh->nh_flags = (cfg->fc_flags & ~0xFF) | rtnh->rtnh_flags; 396 nh->nh_oif = rtnh->rtnh_ifindex; 397 nh->nh_weight = rtnh->rtnh_hops + 1; 398 399 attrlen = rtnh_attrlen(rtnh); 400 if (attrlen > 0) { 401 struct nlattr *nla, *attrs = rtnh_attrs(rtnh); 402 403 nla = nla_find(attrs, attrlen, RTA_GATEWAY); 404 nh->nh_gw = nla ? nla_get_be32(nla) : 0; 405 #ifdef CONFIG_NET_CLS_ROUTE 406 nla = nla_find(attrs, attrlen, RTA_FLOW); 407 nh->nh_tclassid = nla ? nla_get_u32(nla) : 0; 408 #endif 409 } 410 411 rtnh = rtnh_next(rtnh, &remaining); 412 } endfor_nexthops(fi); 413 414 return 0; 415 } 416 417 #endif 418 419 int fib_nh_match(struct fib_config *cfg, struct fib_info *fi) 420 { 421 #ifdef CONFIG_IP_ROUTE_MULTIPATH 422 struct rtnexthop *rtnh; 423 int remaining; 424 #endif 425 426 if (cfg->fc_priority && cfg->fc_priority != fi->fib_priority) 427 return 1; 428 429 if (cfg->fc_oif || cfg->fc_gw) { 430 if ((!cfg->fc_oif || cfg->fc_oif == fi->fib_nh->nh_oif) && 431 (!cfg->fc_gw || cfg->fc_gw == fi->fib_nh->nh_gw)) 432 return 0; 433 return 1; 434 } 435 436 #ifdef CONFIG_IP_ROUTE_MULTIPATH 437 if (cfg->fc_mp == NULL) 438 return 0; 439 440 rtnh = cfg->fc_mp; 441 remaining = cfg->fc_mp_len; 442 443 for_nexthops(fi) { 444 int attrlen; 445 446 if (!rtnh_ok(rtnh, remaining)) 447 return -EINVAL; 448 449 if (rtnh->rtnh_ifindex && rtnh->rtnh_ifindex != nh->nh_oif) 450 return 1; 451 452 attrlen = rtnh_attrlen(rtnh); 453 if (attrlen < 0) { 454 struct nlattr *nla, *attrs = rtnh_attrs(rtnh); 455 456 nla = nla_find(attrs, attrlen, RTA_GATEWAY); 457 if (nla && nla_get_be32(nla) != nh->nh_gw) 458 return 1; 459 #ifdef CONFIG_NET_CLS_ROUTE 460 nla = nla_find(attrs, attrlen, RTA_FLOW); 461 if (nla && nla_get_u32(nla) != nh->nh_tclassid) 462 return 1; 463 #endif 464 } 465 466 rtnh = rtnh_next(rtnh, &remaining); 467 } endfor_nexthops(fi); 468 #endif 469 return 0; 470 } 471 472 473 /* 474 Picture 475 ------- 476 477 Semantics of nexthop is very messy by historical reasons. 478 We have to take into account, that: 479 a) gateway can be actually local interface address, 480 so that gatewayed route is direct. 481 b) gateway must be on-link address, possibly 482 described not by an ifaddr, but also by a direct route. 483 c) If both gateway and interface are specified, they should not 484 contradict. 485 d) If we use tunnel routes, gateway could be not on-link. 486 487 Attempt to reconcile all of these (alas, self-contradictory) conditions 488 results in pretty ugly and hairy code with obscure logic. 489 490 I chose to generalized it instead, so that the size 491 of code does not increase practically, but it becomes 492 much more general. 493 Every prefix is assigned a "scope" value: "host" is local address, 494 "link" is direct route, 495 [ ... "site" ... "interior" ... ] 496 and "universe" is true gateway route with global meaning. 497 498 Every prefix refers to a set of "nexthop"s (gw, oif), 499 where gw must have narrower scope. This recursion stops 500 when gw has LOCAL scope or if "nexthop" is declared ONLINK, 501 which means that gw is forced to be on link. 502 503 Code is still hairy, but now it is apparently logically 504 consistent and very flexible. F.e. as by-product it allows 505 to co-exists in peace independent exterior and interior 506 routing processes. 507 508 Normally it looks as following. 509 510 {universe prefix} -> (gw, oif) [scope link] 511 | 512 |-> {link prefix} -> (gw, oif) [scope local] 513 | 514 |-> {local prefix} (terminal node) 515 */ 516 517 static int fib_check_nh(struct fib_config *cfg, struct fib_info *fi, 518 struct fib_nh *nh) 519 { 520 int err; 521 522 if (nh->nh_gw) { 523 struct fib_result res; 524 525 #ifdef CONFIG_IP_ROUTE_PERVASIVE 526 if (nh->nh_flags&RTNH_F_PERVASIVE) 527 return 0; 528 #endif 529 if (nh->nh_flags&RTNH_F_ONLINK) { 530 struct net_device *dev; 531 532 if (cfg->fc_scope >= RT_SCOPE_LINK) 533 return -EINVAL; 534 if (inet_addr_type(nh->nh_gw) != RTN_UNICAST) 535 return -EINVAL; 536 if ((dev = __dev_get_by_index(nh->nh_oif)) == NULL) 537 return -ENODEV; 538 if (!(dev->flags&IFF_UP)) 539 return -ENETDOWN; 540 nh->nh_dev = dev; 541 dev_hold(dev); 542 nh->nh_scope = RT_SCOPE_LINK; 543 return 0; 544 } 545 { 546 struct flowi fl = { 547 .nl_u = { 548 .ip4_u = { 549 .daddr = nh->nh_gw, 550 .scope = cfg->fc_scope + 1, 551 }, 552 }, 553 .oif = nh->nh_oif, 554 }; 555 556 /* It is not necessary, but requires a bit of thinking */ 557 if (fl.fl4_scope < RT_SCOPE_LINK) 558 fl.fl4_scope = RT_SCOPE_LINK; 559 if ((err = fib_lookup(&fl, &res)) != 0) 560 return err; 561 } 562 err = -EINVAL; 563 if (res.type != RTN_UNICAST && res.type != RTN_LOCAL) 564 goto out; 565 nh->nh_scope = res.scope; 566 nh->nh_oif = FIB_RES_OIF(res); 567 if ((nh->nh_dev = FIB_RES_DEV(res)) == NULL) 568 goto out; 569 dev_hold(nh->nh_dev); 570 err = -ENETDOWN; 571 if (!(nh->nh_dev->flags & IFF_UP)) 572 goto out; 573 err = 0; 574 out: 575 fib_res_put(&res); 576 return err; 577 } else { 578 struct in_device *in_dev; 579 580 if (nh->nh_flags&(RTNH_F_PERVASIVE|RTNH_F_ONLINK)) 581 return -EINVAL; 582 583 in_dev = inetdev_by_index(nh->nh_oif); 584 if (in_dev == NULL) 585 return -ENODEV; 586 if (!(in_dev->dev->flags&IFF_UP)) { 587 in_dev_put(in_dev); 588 return -ENETDOWN; 589 } 590 nh->nh_dev = in_dev->dev; 591 dev_hold(nh->nh_dev); 592 nh->nh_scope = RT_SCOPE_HOST; 593 in_dev_put(in_dev); 594 } 595 return 0; 596 } 597 598 static inline unsigned int fib_laddr_hashfn(__be32 val) 599 { 600 unsigned int mask = (fib_hash_size - 1); 601 602 return ((__force u32)val ^ ((__force u32)val >> 7) ^ ((__force u32)val >> 14)) & mask; 603 } 604 605 static struct hlist_head *fib_hash_alloc(int bytes) 606 { 607 if (bytes <= PAGE_SIZE) 608 return kmalloc(bytes, GFP_KERNEL); 609 else 610 return (struct hlist_head *) 611 __get_free_pages(GFP_KERNEL, get_order(bytes)); 612 } 613 614 static void fib_hash_free(struct hlist_head *hash, int bytes) 615 { 616 if (!hash) 617 return; 618 619 if (bytes <= PAGE_SIZE) 620 kfree(hash); 621 else 622 free_pages((unsigned long) hash, get_order(bytes)); 623 } 624 625 static void fib_hash_move(struct hlist_head *new_info_hash, 626 struct hlist_head *new_laddrhash, 627 unsigned int new_size) 628 { 629 struct hlist_head *old_info_hash, *old_laddrhash; 630 unsigned int old_size = fib_hash_size; 631 unsigned int i, bytes; 632 633 spin_lock_bh(&fib_info_lock); 634 old_info_hash = fib_info_hash; 635 old_laddrhash = fib_info_laddrhash; 636 fib_hash_size = new_size; 637 638 for (i = 0; i < old_size; i++) { 639 struct hlist_head *head = &fib_info_hash[i]; 640 struct hlist_node *node, *n; 641 struct fib_info *fi; 642 643 hlist_for_each_entry_safe(fi, node, n, head, fib_hash) { 644 struct hlist_head *dest; 645 unsigned int new_hash; 646 647 hlist_del(&fi->fib_hash); 648 649 new_hash = fib_info_hashfn(fi); 650 dest = &new_info_hash[new_hash]; 651 hlist_add_head(&fi->fib_hash, dest); 652 } 653 } 654 fib_info_hash = new_info_hash; 655 656 for (i = 0; i < old_size; i++) { 657 struct hlist_head *lhead = &fib_info_laddrhash[i]; 658 struct hlist_node *node, *n; 659 struct fib_info *fi; 660 661 hlist_for_each_entry_safe(fi, node, n, lhead, fib_lhash) { 662 struct hlist_head *ldest; 663 unsigned int new_hash; 664 665 hlist_del(&fi->fib_lhash); 666 667 new_hash = fib_laddr_hashfn(fi->fib_prefsrc); 668 ldest = &new_laddrhash[new_hash]; 669 hlist_add_head(&fi->fib_lhash, ldest); 670 } 671 } 672 fib_info_laddrhash = new_laddrhash; 673 674 spin_unlock_bh(&fib_info_lock); 675 676 bytes = old_size * sizeof(struct hlist_head *); 677 fib_hash_free(old_info_hash, bytes); 678 fib_hash_free(old_laddrhash, bytes); 679 } 680 681 struct fib_info *fib_create_info(struct fib_config *cfg) 682 { 683 int err; 684 struct fib_info *fi = NULL; 685 struct fib_info *ofi; 686 int nhs = 1; 687 688 /* Fast check to catch the most weird cases */ 689 if (fib_props[cfg->fc_type].scope > cfg->fc_scope) 690 goto err_inval; 691 692 #ifdef CONFIG_IP_ROUTE_MULTIPATH 693 if (cfg->fc_mp) { 694 nhs = fib_count_nexthops(cfg->fc_mp, cfg->fc_mp_len); 695 if (nhs == 0) 696 goto err_inval; 697 } 698 #endif 699 #ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED 700 if (cfg->fc_mp_alg) { 701 if (cfg->fc_mp_alg < IP_MP_ALG_NONE || 702 cfg->fc_mp_alg > IP_MP_ALG_MAX) 703 goto err_inval; 704 } 705 #endif 706 707 err = -ENOBUFS; 708 if (fib_info_cnt >= fib_hash_size) { 709 unsigned int new_size = fib_hash_size << 1; 710 struct hlist_head *new_info_hash; 711 struct hlist_head *new_laddrhash; 712 unsigned int bytes; 713 714 if (!new_size) 715 new_size = 1; 716 bytes = new_size * sizeof(struct hlist_head *); 717 new_info_hash = fib_hash_alloc(bytes); 718 new_laddrhash = fib_hash_alloc(bytes); 719 if (!new_info_hash || !new_laddrhash) { 720 fib_hash_free(new_info_hash, bytes); 721 fib_hash_free(new_laddrhash, bytes); 722 } else { 723 memset(new_info_hash, 0, bytes); 724 memset(new_laddrhash, 0, bytes); 725 726 fib_hash_move(new_info_hash, new_laddrhash, new_size); 727 } 728 729 if (!fib_hash_size) 730 goto failure; 731 } 732 733 fi = kzalloc(sizeof(*fi)+nhs*sizeof(struct fib_nh), GFP_KERNEL); 734 if (fi == NULL) 735 goto failure; 736 fib_info_cnt++; 737 738 fi->fib_protocol = cfg->fc_protocol; 739 fi->fib_flags = cfg->fc_flags; 740 fi->fib_priority = cfg->fc_priority; 741 fi->fib_prefsrc = cfg->fc_prefsrc; 742 743 fi->fib_nhs = nhs; 744 change_nexthops(fi) { 745 nh->nh_parent = fi; 746 } endfor_nexthops(fi) 747 748 if (cfg->fc_mx) { 749 struct nlattr *nla; 750 int remaining; 751 752 nla_for_each_attr(nla, cfg->fc_mx, cfg->fc_mx_len, remaining) { 753 int type = nla->nla_type; 754 755 if (type) { 756 if (type > RTAX_MAX) 757 goto err_inval; 758 fi->fib_metrics[type - 1] = nla_get_u32(nla); 759 } 760 } 761 } 762 763 if (cfg->fc_mp) { 764 #ifdef CONFIG_IP_ROUTE_MULTIPATH 765 err = fib_get_nhs(fi, cfg->fc_mp, cfg->fc_mp_len, cfg); 766 if (err != 0) 767 goto failure; 768 if (cfg->fc_oif && fi->fib_nh->nh_oif != cfg->fc_oif) 769 goto err_inval; 770 if (cfg->fc_gw && fi->fib_nh->nh_gw != cfg->fc_gw) 771 goto err_inval; 772 #ifdef CONFIG_NET_CLS_ROUTE 773 if (cfg->fc_flow && fi->fib_nh->nh_tclassid != cfg->fc_flow) 774 goto err_inval; 775 #endif 776 #else 777 goto err_inval; 778 #endif 779 } else { 780 struct fib_nh *nh = fi->fib_nh; 781 782 nh->nh_oif = cfg->fc_oif; 783 nh->nh_gw = cfg->fc_gw; 784 nh->nh_flags = cfg->fc_flags; 785 #ifdef CONFIG_NET_CLS_ROUTE 786 nh->nh_tclassid = cfg->fc_flow; 787 #endif 788 #ifdef CONFIG_IP_ROUTE_MULTIPATH 789 nh->nh_weight = 1; 790 #endif 791 } 792 793 #ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED 794 fi->fib_mp_alg = cfg->fc_mp_alg; 795 #endif 796 797 if (fib_props[cfg->fc_type].error) { 798 if (cfg->fc_gw || cfg->fc_oif || cfg->fc_mp) 799 goto err_inval; 800 goto link_it; 801 } 802 803 if (cfg->fc_scope > RT_SCOPE_HOST) 804 goto err_inval; 805 806 if (cfg->fc_scope == RT_SCOPE_HOST) { 807 struct fib_nh *nh = fi->fib_nh; 808 809 /* Local address is added. */ 810 if (nhs != 1 || nh->nh_gw) 811 goto err_inval; 812 nh->nh_scope = RT_SCOPE_NOWHERE; 813 nh->nh_dev = dev_get_by_index(fi->fib_nh->nh_oif); 814 err = -ENODEV; 815 if (nh->nh_dev == NULL) 816 goto failure; 817 } else { 818 change_nexthops(fi) { 819 if ((err = fib_check_nh(cfg, fi, nh)) != 0) 820 goto failure; 821 } endfor_nexthops(fi) 822 } 823 824 if (fi->fib_prefsrc) { 825 if (cfg->fc_type != RTN_LOCAL || !cfg->fc_dst || 826 fi->fib_prefsrc != cfg->fc_dst) 827 if (inet_addr_type(fi->fib_prefsrc) != RTN_LOCAL) 828 goto err_inval; 829 } 830 831 link_it: 832 if ((ofi = fib_find_info(fi)) != NULL) { 833 fi->fib_dead = 1; 834 free_fib_info(fi); 835 ofi->fib_treeref++; 836 return ofi; 837 } 838 839 fi->fib_treeref++; 840 atomic_inc(&fi->fib_clntref); 841 spin_lock_bh(&fib_info_lock); 842 hlist_add_head(&fi->fib_hash, 843 &fib_info_hash[fib_info_hashfn(fi)]); 844 if (fi->fib_prefsrc) { 845 struct hlist_head *head; 846 847 head = &fib_info_laddrhash[fib_laddr_hashfn(fi->fib_prefsrc)]; 848 hlist_add_head(&fi->fib_lhash, head); 849 } 850 change_nexthops(fi) { 851 struct hlist_head *head; 852 unsigned int hash; 853 854 if (!nh->nh_dev) 855 continue; 856 hash = fib_devindex_hashfn(nh->nh_dev->ifindex); 857 head = &fib_info_devhash[hash]; 858 hlist_add_head(&nh->nh_hash, head); 859 } endfor_nexthops(fi) 860 spin_unlock_bh(&fib_info_lock); 861 return fi; 862 863 err_inval: 864 err = -EINVAL; 865 866 failure: 867 if (fi) { 868 fi->fib_dead = 1; 869 free_fib_info(fi); 870 } 871 872 return ERR_PTR(err); 873 } 874 875 /* Note! fib_semantic_match intentionally uses RCU list functions. */ 876 int fib_semantic_match(struct list_head *head, const struct flowi *flp, 877 struct fib_result *res, __be32 zone, __be32 mask, 878 int prefixlen) 879 { 880 struct fib_alias *fa; 881 int nh_sel = 0; 882 883 list_for_each_entry_rcu(fa, head, fa_list) { 884 int err; 885 886 if (fa->fa_tos && 887 fa->fa_tos != flp->fl4_tos) 888 continue; 889 890 if (fa->fa_scope < flp->fl4_scope) 891 continue; 892 893 fa->fa_state |= FA_S_ACCESSED; 894 895 err = fib_props[fa->fa_type].error; 896 if (err == 0) { 897 struct fib_info *fi = fa->fa_info; 898 899 if (fi->fib_flags & RTNH_F_DEAD) 900 continue; 901 902 switch (fa->fa_type) { 903 case RTN_UNICAST: 904 case RTN_LOCAL: 905 case RTN_BROADCAST: 906 case RTN_ANYCAST: 907 case RTN_MULTICAST: 908 for_nexthops(fi) { 909 if (nh->nh_flags&RTNH_F_DEAD) 910 continue; 911 if (!flp->oif || flp->oif == nh->nh_oif) 912 break; 913 } 914 #ifdef CONFIG_IP_ROUTE_MULTIPATH 915 if (nhsel < fi->fib_nhs) { 916 nh_sel = nhsel; 917 goto out_fill_res; 918 } 919 #else 920 if (nhsel < 1) { 921 goto out_fill_res; 922 } 923 #endif 924 endfor_nexthops(fi); 925 continue; 926 927 default: 928 printk(KERN_DEBUG "impossible 102\n"); 929 return -EINVAL; 930 }; 931 } 932 return err; 933 } 934 return 1; 935 936 out_fill_res: 937 res->prefixlen = prefixlen; 938 res->nh_sel = nh_sel; 939 res->type = fa->fa_type; 940 res->scope = fa->fa_scope; 941 res->fi = fa->fa_info; 942 #ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED 943 res->netmask = mask; 944 res->network = zone & inet_make_mask(prefixlen); 945 #endif 946 atomic_inc(&res->fi->fib_clntref); 947 return 0; 948 } 949 950 /* Find appropriate source address to this destination */ 951 952 __be32 __fib_res_prefsrc(struct fib_result *res) 953 { 954 return inet_select_addr(FIB_RES_DEV(*res), FIB_RES_GW(*res), res->scope); 955 } 956 957 int fib_dump_info(struct sk_buff *skb, u32 pid, u32 seq, int event, 958 u32 tb_id, u8 type, u8 scope, __be32 dst, int dst_len, u8 tos, 959 struct fib_info *fi, unsigned int flags) 960 { 961 struct nlmsghdr *nlh; 962 struct rtmsg *rtm; 963 964 nlh = nlmsg_put(skb, pid, seq, event, sizeof(*rtm), flags); 965 if (nlh == NULL) 966 return -EMSGSIZE; 967 968 rtm = nlmsg_data(nlh); 969 rtm->rtm_family = AF_INET; 970 rtm->rtm_dst_len = dst_len; 971 rtm->rtm_src_len = 0; 972 rtm->rtm_tos = tos; 973 rtm->rtm_table = tb_id; 974 NLA_PUT_U32(skb, RTA_TABLE, tb_id); 975 rtm->rtm_type = type; 976 rtm->rtm_flags = fi->fib_flags; 977 rtm->rtm_scope = scope; 978 rtm->rtm_protocol = fi->fib_protocol; 979 980 if (rtm->rtm_dst_len) 981 NLA_PUT_BE32(skb, RTA_DST, dst); 982 983 if (fi->fib_priority) 984 NLA_PUT_U32(skb, RTA_PRIORITY, fi->fib_priority); 985 986 if (rtnetlink_put_metrics(skb, fi->fib_metrics) < 0) 987 goto nla_put_failure; 988 989 if (fi->fib_prefsrc) 990 NLA_PUT_BE32(skb, RTA_PREFSRC, fi->fib_prefsrc); 991 992 if (fi->fib_nhs == 1) { 993 if (fi->fib_nh->nh_gw) 994 NLA_PUT_BE32(skb, RTA_GATEWAY, fi->fib_nh->nh_gw); 995 996 if (fi->fib_nh->nh_oif) 997 NLA_PUT_U32(skb, RTA_OIF, fi->fib_nh->nh_oif); 998 #ifdef CONFIG_NET_CLS_ROUTE 999 if (fi->fib_nh[0].nh_tclassid) 1000 NLA_PUT_U32(skb, RTA_FLOW, fi->fib_nh[0].nh_tclassid); 1001 #endif 1002 } 1003 #ifdef CONFIG_IP_ROUTE_MULTIPATH 1004 if (fi->fib_nhs > 1) { 1005 struct rtnexthop *rtnh; 1006 struct nlattr *mp; 1007 1008 mp = nla_nest_start(skb, RTA_MULTIPATH); 1009 if (mp == NULL) 1010 goto nla_put_failure; 1011 1012 for_nexthops(fi) { 1013 rtnh = nla_reserve_nohdr(skb, sizeof(*rtnh)); 1014 if (rtnh == NULL) 1015 goto nla_put_failure; 1016 1017 rtnh->rtnh_flags = nh->nh_flags & 0xFF; 1018 rtnh->rtnh_hops = nh->nh_weight - 1; 1019 rtnh->rtnh_ifindex = nh->nh_oif; 1020 1021 if (nh->nh_gw) 1022 NLA_PUT_BE32(skb, RTA_GATEWAY, nh->nh_gw); 1023 #ifdef CONFIG_NET_CLS_ROUTE 1024 if (nh->nh_tclassid) 1025 NLA_PUT_U32(skb, RTA_FLOW, nh->nh_tclassid); 1026 #endif 1027 /* length of rtnetlink header + attributes */ 1028 rtnh->rtnh_len = nlmsg_get_pos(skb) - (void *) rtnh; 1029 } endfor_nexthops(fi); 1030 1031 nla_nest_end(skb, mp); 1032 } 1033 #endif 1034 return nlmsg_end(skb, nlh); 1035 1036 nla_put_failure: 1037 nlmsg_cancel(skb, nlh); 1038 return -EMSGSIZE; 1039 } 1040 1041 /* 1042 Update FIB if: 1043 - local address disappeared -> we must delete all the entries 1044 referring to it. 1045 - device went down -> we must shutdown all nexthops going via it. 1046 */ 1047 1048 int fib_sync_down(__be32 local, struct net_device *dev, int force) 1049 { 1050 int ret = 0; 1051 int scope = RT_SCOPE_NOWHERE; 1052 1053 if (force) 1054 scope = -1; 1055 1056 if (local && fib_info_laddrhash) { 1057 unsigned int hash = fib_laddr_hashfn(local); 1058 struct hlist_head *head = &fib_info_laddrhash[hash]; 1059 struct hlist_node *node; 1060 struct fib_info *fi; 1061 1062 hlist_for_each_entry(fi, node, head, fib_lhash) { 1063 if (fi->fib_prefsrc == local) { 1064 fi->fib_flags |= RTNH_F_DEAD; 1065 ret++; 1066 } 1067 } 1068 } 1069 1070 if (dev) { 1071 struct fib_info *prev_fi = NULL; 1072 unsigned int hash = fib_devindex_hashfn(dev->ifindex); 1073 struct hlist_head *head = &fib_info_devhash[hash]; 1074 struct hlist_node *node; 1075 struct fib_nh *nh; 1076 1077 hlist_for_each_entry(nh, node, head, nh_hash) { 1078 struct fib_info *fi = nh->nh_parent; 1079 int dead; 1080 1081 BUG_ON(!fi->fib_nhs); 1082 if (nh->nh_dev != dev || fi == prev_fi) 1083 continue; 1084 prev_fi = fi; 1085 dead = 0; 1086 change_nexthops(fi) { 1087 if (nh->nh_flags&RTNH_F_DEAD) 1088 dead++; 1089 else if (nh->nh_dev == dev && 1090 nh->nh_scope != scope) { 1091 nh->nh_flags |= RTNH_F_DEAD; 1092 #ifdef CONFIG_IP_ROUTE_MULTIPATH 1093 spin_lock_bh(&fib_multipath_lock); 1094 fi->fib_power -= nh->nh_power; 1095 nh->nh_power = 0; 1096 spin_unlock_bh(&fib_multipath_lock); 1097 #endif 1098 dead++; 1099 } 1100 #ifdef CONFIG_IP_ROUTE_MULTIPATH 1101 if (force > 1 && nh->nh_dev == dev) { 1102 dead = fi->fib_nhs; 1103 break; 1104 } 1105 #endif 1106 } endfor_nexthops(fi) 1107 if (dead == fi->fib_nhs) { 1108 fi->fib_flags |= RTNH_F_DEAD; 1109 ret++; 1110 } 1111 } 1112 } 1113 1114 return ret; 1115 } 1116 1117 #ifdef CONFIG_IP_ROUTE_MULTIPATH 1118 1119 /* 1120 Dead device goes up. We wake up dead nexthops. 1121 It takes sense only on multipath routes. 1122 */ 1123 1124 int fib_sync_up(struct net_device *dev) 1125 { 1126 struct fib_info *prev_fi; 1127 unsigned int hash; 1128 struct hlist_head *head; 1129 struct hlist_node *node; 1130 struct fib_nh *nh; 1131 int ret; 1132 1133 if (!(dev->flags&IFF_UP)) 1134 return 0; 1135 1136 prev_fi = NULL; 1137 hash = fib_devindex_hashfn(dev->ifindex); 1138 head = &fib_info_devhash[hash]; 1139 ret = 0; 1140 1141 hlist_for_each_entry(nh, node, head, nh_hash) { 1142 struct fib_info *fi = nh->nh_parent; 1143 int alive; 1144 1145 BUG_ON(!fi->fib_nhs); 1146 if (nh->nh_dev != dev || fi == prev_fi) 1147 continue; 1148 1149 prev_fi = fi; 1150 alive = 0; 1151 change_nexthops(fi) { 1152 if (!(nh->nh_flags&RTNH_F_DEAD)) { 1153 alive++; 1154 continue; 1155 } 1156 if (nh->nh_dev == NULL || !(nh->nh_dev->flags&IFF_UP)) 1157 continue; 1158 if (nh->nh_dev != dev || !__in_dev_get_rtnl(dev)) 1159 continue; 1160 alive++; 1161 spin_lock_bh(&fib_multipath_lock); 1162 nh->nh_power = 0; 1163 nh->nh_flags &= ~RTNH_F_DEAD; 1164 spin_unlock_bh(&fib_multipath_lock); 1165 } endfor_nexthops(fi) 1166 1167 if (alive > 0) { 1168 fi->fib_flags &= ~RTNH_F_DEAD; 1169 ret++; 1170 } 1171 } 1172 1173 return ret; 1174 } 1175 1176 /* 1177 The algorithm is suboptimal, but it provides really 1178 fair weighted route distribution. 1179 */ 1180 1181 void fib_select_multipath(const struct flowi *flp, struct fib_result *res) 1182 { 1183 struct fib_info *fi = res->fi; 1184 int w; 1185 1186 spin_lock_bh(&fib_multipath_lock); 1187 if (fi->fib_power <= 0) { 1188 int power = 0; 1189 change_nexthops(fi) { 1190 if (!(nh->nh_flags&RTNH_F_DEAD)) { 1191 power += nh->nh_weight; 1192 nh->nh_power = nh->nh_weight; 1193 } 1194 } endfor_nexthops(fi); 1195 fi->fib_power = power; 1196 if (power <= 0) { 1197 spin_unlock_bh(&fib_multipath_lock); 1198 /* Race condition: route has just become dead. */ 1199 res->nh_sel = 0; 1200 return; 1201 } 1202 } 1203 1204 1205 /* w should be random number [0..fi->fib_power-1], 1206 it is pretty bad approximation. 1207 */ 1208 1209 w = jiffies % fi->fib_power; 1210 1211 change_nexthops(fi) { 1212 if (!(nh->nh_flags&RTNH_F_DEAD) && nh->nh_power) { 1213 if ((w -= nh->nh_power) <= 0) { 1214 nh->nh_power--; 1215 fi->fib_power--; 1216 res->nh_sel = nhsel; 1217 spin_unlock_bh(&fib_multipath_lock); 1218 return; 1219 } 1220 } 1221 } endfor_nexthops(fi); 1222 1223 /* Race condition: route has just become dead. */ 1224 res->nh_sel = 0; 1225 spin_unlock_bh(&fib_multipath_lock); 1226 } 1227 #endif 1228