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 <linux/config.h> 19 #include <asm/uaccess.h> 20 #include <asm/system.h> 21 #include <linux/bitops.h> 22 #include <linux/types.h> 23 #include <linux/kernel.h> 24 #include <linux/jiffies.h> 25 #include <linux/mm.h> 26 #include <linux/string.h> 27 #include <linux/socket.h> 28 #include <linux/sockios.h> 29 #include <linux/errno.h> 30 #include <linux/in.h> 31 #include <linux/inet.h> 32 #include <linux/inetdevice.h> 33 #include <linux/netdevice.h> 34 #include <linux/if_arp.h> 35 #include <linux/proc_fs.h> 36 #include <linux/skbuff.h> 37 #include <linux/netlink.h> 38 #include <linux/init.h> 39 40 #include <net/arp.h> 41 #include <net/ip.h> 42 #include <net/protocol.h> 43 #include <net/route.h> 44 #include <net/tcp.h> 45 #include <net/sock.h> 46 #include <net/ip_fib.h> 47 #include <net/ip_mp_alg.h> 48 49 #include "fib_lookup.h" 50 51 #define FSprintk(a...) 52 53 static DEFINE_RWLOCK(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 write_lock(&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 write_unlock(&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 ^= 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(u32 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 read_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 read_unlock(&fib_info_lock); 267 return 0; 268 } 269 } 270 271 read_unlock(&fib_info_lock); 272 273 return -1; 274 } 275 276 void rtmsg_fib(int event, u32 key, struct fib_alias *fa, 277 int z, int tb_id, 278 struct nlmsghdr *n, struct netlink_skb_parms *req) 279 { 280 struct sk_buff *skb; 281 u32 pid = req ? req->pid : n->nlmsg_pid; 282 int size = NLMSG_SPACE(sizeof(struct rtmsg)+256); 283 284 skb = alloc_skb(size, GFP_KERNEL); 285 if (!skb) 286 return; 287 288 if (fib_dump_info(skb, pid, n->nlmsg_seq, event, tb_id, 289 fa->fa_type, fa->fa_scope, &key, z, 290 fa->fa_tos, 291 fa->fa_info, 0) < 0) { 292 kfree_skb(skb); 293 return; 294 } 295 NETLINK_CB(skb).dst_group = RTNLGRP_IPV4_ROUTE; 296 if (n->nlmsg_flags&NLM_F_ECHO) 297 atomic_inc(&skb->users); 298 netlink_broadcast(rtnl, skb, pid, RTNLGRP_IPV4_ROUTE, GFP_KERNEL); 299 if (n->nlmsg_flags&NLM_F_ECHO) 300 netlink_unicast(rtnl, skb, pid, MSG_DONTWAIT); 301 } 302 303 /* Return the first fib alias matching TOS with 304 * priority less than or equal to PRIO. 305 */ 306 struct fib_alias *fib_find_alias(struct list_head *fah, u8 tos, u32 prio) 307 { 308 if (fah) { 309 struct fib_alias *fa; 310 list_for_each_entry(fa, fah, fa_list) { 311 if (fa->fa_tos > tos) 312 continue; 313 if (fa->fa_info->fib_priority >= prio || 314 fa->fa_tos < tos) 315 return fa; 316 } 317 } 318 return NULL; 319 } 320 321 int fib_detect_death(struct fib_info *fi, int order, 322 struct fib_info **last_resort, int *last_idx, int *dflt) 323 { 324 struct neighbour *n; 325 int state = NUD_NONE; 326 327 n = neigh_lookup(&arp_tbl, &fi->fib_nh[0].nh_gw, fi->fib_dev); 328 if (n) { 329 state = n->nud_state; 330 neigh_release(n); 331 } 332 if (state==NUD_REACHABLE) 333 return 0; 334 if ((state&NUD_VALID) && order != *dflt) 335 return 0; 336 if ((state&NUD_VALID) || 337 (*last_idx<0 && order > *dflt)) { 338 *last_resort = fi; 339 *last_idx = order; 340 } 341 return 1; 342 } 343 344 #ifdef CONFIG_IP_ROUTE_MULTIPATH 345 346 static u32 fib_get_attr32(struct rtattr *attr, int attrlen, int type) 347 { 348 while (RTA_OK(attr,attrlen)) { 349 if (attr->rta_type == type) 350 return *(u32*)RTA_DATA(attr); 351 attr = RTA_NEXT(attr, attrlen); 352 } 353 return 0; 354 } 355 356 static int 357 fib_count_nexthops(struct rtattr *rta) 358 { 359 int nhs = 0; 360 struct rtnexthop *nhp = RTA_DATA(rta); 361 int nhlen = RTA_PAYLOAD(rta); 362 363 while (nhlen >= (int)sizeof(struct rtnexthop)) { 364 if ((nhlen -= nhp->rtnh_len) < 0) 365 return 0; 366 nhs++; 367 nhp = RTNH_NEXT(nhp); 368 }; 369 return nhs; 370 } 371 372 static int 373 fib_get_nhs(struct fib_info *fi, const struct rtattr *rta, const struct rtmsg *r) 374 { 375 struct rtnexthop *nhp = RTA_DATA(rta); 376 int nhlen = RTA_PAYLOAD(rta); 377 378 change_nexthops(fi) { 379 int attrlen = nhlen - sizeof(struct rtnexthop); 380 if (attrlen < 0 || (nhlen -= nhp->rtnh_len) < 0) 381 return -EINVAL; 382 nh->nh_flags = (r->rtm_flags&~0xFF) | nhp->rtnh_flags; 383 nh->nh_oif = nhp->rtnh_ifindex; 384 nh->nh_weight = nhp->rtnh_hops + 1; 385 if (attrlen) { 386 nh->nh_gw = fib_get_attr32(RTNH_DATA(nhp), attrlen, RTA_GATEWAY); 387 #ifdef CONFIG_NET_CLS_ROUTE 388 nh->nh_tclassid = fib_get_attr32(RTNH_DATA(nhp), attrlen, RTA_FLOW); 389 #endif 390 } 391 nhp = RTNH_NEXT(nhp); 392 } endfor_nexthops(fi); 393 return 0; 394 } 395 396 #endif 397 398 int fib_nh_match(struct rtmsg *r, struct nlmsghdr *nlh, struct kern_rta *rta, 399 struct fib_info *fi) 400 { 401 #ifdef CONFIG_IP_ROUTE_MULTIPATH 402 struct rtnexthop *nhp; 403 int nhlen; 404 #endif 405 406 if (rta->rta_priority && 407 *rta->rta_priority != fi->fib_priority) 408 return 1; 409 410 if (rta->rta_oif || rta->rta_gw) { 411 if ((!rta->rta_oif || *rta->rta_oif == fi->fib_nh->nh_oif) && 412 (!rta->rta_gw || memcmp(rta->rta_gw, &fi->fib_nh->nh_gw, 4) == 0)) 413 return 0; 414 return 1; 415 } 416 417 #ifdef CONFIG_IP_ROUTE_MULTIPATH 418 if (rta->rta_mp == NULL) 419 return 0; 420 nhp = RTA_DATA(rta->rta_mp); 421 nhlen = RTA_PAYLOAD(rta->rta_mp); 422 423 for_nexthops(fi) { 424 int attrlen = nhlen - sizeof(struct rtnexthop); 425 u32 gw; 426 427 if (attrlen < 0 || (nhlen -= nhp->rtnh_len) < 0) 428 return -EINVAL; 429 if (nhp->rtnh_ifindex && nhp->rtnh_ifindex != nh->nh_oif) 430 return 1; 431 if (attrlen) { 432 gw = fib_get_attr32(RTNH_DATA(nhp), attrlen, RTA_GATEWAY); 433 if (gw && gw != nh->nh_gw) 434 return 1; 435 #ifdef CONFIG_NET_CLS_ROUTE 436 gw = fib_get_attr32(RTNH_DATA(nhp), attrlen, RTA_FLOW); 437 if (gw && gw != nh->nh_tclassid) 438 return 1; 439 #endif 440 } 441 nhp = RTNH_NEXT(nhp); 442 } endfor_nexthops(fi); 443 #endif 444 return 0; 445 } 446 447 448 /* 449 Picture 450 ------- 451 452 Semantics of nexthop is very messy by historical reasons. 453 We have to take into account, that: 454 a) gateway can be actually local interface address, 455 so that gatewayed route is direct. 456 b) gateway must be on-link address, possibly 457 described not by an ifaddr, but also by a direct route. 458 c) If both gateway and interface are specified, they should not 459 contradict. 460 d) If we use tunnel routes, gateway could be not on-link. 461 462 Attempt to reconcile all of these (alas, self-contradictory) conditions 463 results in pretty ugly and hairy code with obscure logic. 464 465 I chose to generalized it instead, so that the size 466 of code does not increase practically, but it becomes 467 much more general. 468 Every prefix is assigned a "scope" value: "host" is local address, 469 "link" is direct route, 470 [ ... "site" ... "interior" ... ] 471 and "universe" is true gateway route with global meaning. 472 473 Every prefix refers to a set of "nexthop"s (gw, oif), 474 where gw must have narrower scope. This recursion stops 475 when gw has LOCAL scope or if "nexthop" is declared ONLINK, 476 which means that gw is forced to be on link. 477 478 Code is still hairy, but now it is apparently logically 479 consistent and very flexible. F.e. as by-product it allows 480 to co-exists in peace independent exterior and interior 481 routing processes. 482 483 Normally it looks as following. 484 485 {universe prefix} -> (gw, oif) [scope link] 486 | 487 |-> {link prefix} -> (gw, oif) [scope local] 488 | 489 |-> {local prefix} (terminal node) 490 */ 491 492 static int fib_check_nh(const struct rtmsg *r, struct fib_info *fi, struct fib_nh *nh) 493 { 494 int err; 495 496 if (nh->nh_gw) { 497 struct fib_result res; 498 499 #ifdef CONFIG_IP_ROUTE_PERVASIVE 500 if (nh->nh_flags&RTNH_F_PERVASIVE) 501 return 0; 502 #endif 503 if (nh->nh_flags&RTNH_F_ONLINK) { 504 struct net_device *dev; 505 506 if (r->rtm_scope >= RT_SCOPE_LINK) 507 return -EINVAL; 508 if (inet_addr_type(nh->nh_gw) != RTN_UNICAST) 509 return -EINVAL; 510 if ((dev = __dev_get_by_index(nh->nh_oif)) == NULL) 511 return -ENODEV; 512 if (!(dev->flags&IFF_UP)) 513 return -ENETDOWN; 514 nh->nh_dev = dev; 515 dev_hold(dev); 516 nh->nh_scope = RT_SCOPE_LINK; 517 return 0; 518 } 519 { 520 struct flowi fl = { .nl_u = { .ip4_u = 521 { .daddr = nh->nh_gw, 522 .scope = r->rtm_scope + 1 } }, 523 .oif = nh->nh_oif }; 524 525 /* It is not necessary, but requires a bit of thinking */ 526 if (fl.fl4_scope < RT_SCOPE_LINK) 527 fl.fl4_scope = RT_SCOPE_LINK; 528 if ((err = fib_lookup(&fl, &res)) != 0) 529 return err; 530 } 531 err = -EINVAL; 532 if (res.type != RTN_UNICAST && res.type != RTN_LOCAL) 533 goto out; 534 nh->nh_scope = res.scope; 535 nh->nh_oif = FIB_RES_OIF(res); 536 if ((nh->nh_dev = FIB_RES_DEV(res)) == NULL) 537 goto out; 538 dev_hold(nh->nh_dev); 539 err = -ENETDOWN; 540 if (!(nh->nh_dev->flags & IFF_UP)) 541 goto out; 542 err = 0; 543 out: 544 fib_res_put(&res); 545 return err; 546 } else { 547 struct in_device *in_dev; 548 549 if (nh->nh_flags&(RTNH_F_PERVASIVE|RTNH_F_ONLINK)) 550 return -EINVAL; 551 552 in_dev = inetdev_by_index(nh->nh_oif); 553 if (in_dev == NULL) 554 return -ENODEV; 555 if (!(in_dev->dev->flags&IFF_UP)) { 556 in_dev_put(in_dev); 557 return -ENETDOWN; 558 } 559 nh->nh_dev = in_dev->dev; 560 dev_hold(nh->nh_dev); 561 nh->nh_scope = RT_SCOPE_HOST; 562 in_dev_put(in_dev); 563 } 564 return 0; 565 } 566 567 static inline unsigned int fib_laddr_hashfn(u32 val) 568 { 569 unsigned int mask = (fib_hash_size - 1); 570 571 return (val ^ (val >> 7) ^ (val >> 14)) & mask; 572 } 573 574 static struct hlist_head *fib_hash_alloc(int bytes) 575 { 576 if (bytes <= PAGE_SIZE) 577 return kmalloc(bytes, GFP_KERNEL); 578 else 579 return (struct hlist_head *) 580 __get_free_pages(GFP_KERNEL, get_order(bytes)); 581 } 582 583 static void fib_hash_free(struct hlist_head *hash, int bytes) 584 { 585 if (!hash) 586 return; 587 588 if (bytes <= PAGE_SIZE) 589 kfree(hash); 590 else 591 free_pages((unsigned long) hash, get_order(bytes)); 592 } 593 594 static void fib_hash_move(struct hlist_head *new_info_hash, 595 struct hlist_head *new_laddrhash, 596 unsigned int new_size) 597 { 598 struct hlist_head *old_info_hash, *old_laddrhash; 599 unsigned int old_size = fib_hash_size; 600 unsigned int i, bytes; 601 602 write_lock(&fib_info_lock); 603 old_info_hash = fib_info_hash; 604 old_laddrhash = fib_info_laddrhash; 605 fib_hash_size = new_size; 606 607 for (i = 0; i < old_size; i++) { 608 struct hlist_head *head = &fib_info_hash[i]; 609 struct hlist_node *node, *n; 610 struct fib_info *fi; 611 612 hlist_for_each_entry_safe(fi, node, n, head, fib_hash) { 613 struct hlist_head *dest; 614 unsigned int new_hash; 615 616 hlist_del(&fi->fib_hash); 617 618 new_hash = fib_info_hashfn(fi); 619 dest = &new_info_hash[new_hash]; 620 hlist_add_head(&fi->fib_hash, dest); 621 } 622 } 623 fib_info_hash = new_info_hash; 624 625 for (i = 0; i < old_size; i++) { 626 struct hlist_head *lhead = &fib_info_laddrhash[i]; 627 struct hlist_node *node, *n; 628 struct fib_info *fi; 629 630 hlist_for_each_entry_safe(fi, node, n, lhead, fib_lhash) { 631 struct hlist_head *ldest; 632 unsigned int new_hash; 633 634 hlist_del(&fi->fib_lhash); 635 636 new_hash = fib_laddr_hashfn(fi->fib_prefsrc); 637 ldest = &new_laddrhash[new_hash]; 638 hlist_add_head(&fi->fib_lhash, ldest); 639 } 640 } 641 fib_info_laddrhash = new_laddrhash; 642 643 write_unlock(&fib_info_lock); 644 645 bytes = old_size * sizeof(struct hlist_head *); 646 fib_hash_free(old_info_hash, bytes); 647 fib_hash_free(old_laddrhash, bytes); 648 } 649 650 struct fib_info * 651 fib_create_info(const struct rtmsg *r, struct kern_rta *rta, 652 const struct nlmsghdr *nlh, int *errp) 653 { 654 int err; 655 struct fib_info *fi = NULL; 656 struct fib_info *ofi; 657 #ifdef CONFIG_IP_ROUTE_MULTIPATH 658 int nhs = 1; 659 #else 660 const int nhs = 1; 661 #endif 662 #ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED 663 u32 mp_alg = IP_MP_ALG_NONE; 664 #endif 665 666 /* Fast check to catch the most weird cases */ 667 if (fib_props[r->rtm_type].scope > r->rtm_scope) 668 goto err_inval; 669 670 #ifdef CONFIG_IP_ROUTE_MULTIPATH 671 if (rta->rta_mp) { 672 nhs = fib_count_nexthops(rta->rta_mp); 673 if (nhs == 0) 674 goto err_inval; 675 } 676 #endif 677 #ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED 678 if (rta->rta_mp_alg) { 679 mp_alg = *rta->rta_mp_alg; 680 681 if (mp_alg < IP_MP_ALG_NONE || 682 mp_alg > IP_MP_ALG_MAX) 683 goto err_inval; 684 } 685 #endif 686 687 err = -ENOBUFS; 688 if (fib_info_cnt >= fib_hash_size) { 689 unsigned int new_size = fib_hash_size << 1; 690 struct hlist_head *new_info_hash; 691 struct hlist_head *new_laddrhash; 692 unsigned int bytes; 693 694 if (!new_size) 695 new_size = 1; 696 bytes = new_size * sizeof(struct hlist_head *); 697 new_info_hash = fib_hash_alloc(bytes); 698 new_laddrhash = fib_hash_alloc(bytes); 699 if (!new_info_hash || !new_laddrhash) { 700 fib_hash_free(new_info_hash, bytes); 701 fib_hash_free(new_laddrhash, bytes); 702 } else { 703 memset(new_info_hash, 0, bytes); 704 memset(new_laddrhash, 0, bytes); 705 706 fib_hash_move(new_info_hash, new_laddrhash, new_size); 707 } 708 709 if (!fib_hash_size) 710 goto failure; 711 } 712 713 fi = kmalloc(sizeof(*fi)+nhs*sizeof(struct fib_nh), GFP_KERNEL); 714 if (fi == NULL) 715 goto failure; 716 fib_info_cnt++; 717 memset(fi, 0, sizeof(*fi)+nhs*sizeof(struct fib_nh)); 718 719 fi->fib_protocol = r->rtm_protocol; 720 721 fi->fib_nhs = nhs; 722 change_nexthops(fi) { 723 nh->nh_parent = fi; 724 } endfor_nexthops(fi) 725 726 fi->fib_flags = r->rtm_flags; 727 if (rta->rta_priority) 728 fi->fib_priority = *rta->rta_priority; 729 if (rta->rta_mx) { 730 int attrlen = RTA_PAYLOAD(rta->rta_mx); 731 struct rtattr *attr = RTA_DATA(rta->rta_mx); 732 733 while (RTA_OK(attr, attrlen)) { 734 unsigned flavor = attr->rta_type; 735 if (flavor) { 736 if (flavor > RTAX_MAX) 737 goto err_inval; 738 fi->fib_metrics[flavor-1] = *(unsigned*)RTA_DATA(attr); 739 } 740 attr = RTA_NEXT(attr, attrlen); 741 } 742 } 743 if (rta->rta_prefsrc) 744 memcpy(&fi->fib_prefsrc, rta->rta_prefsrc, 4); 745 746 if (rta->rta_mp) { 747 #ifdef CONFIG_IP_ROUTE_MULTIPATH 748 if ((err = fib_get_nhs(fi, rta->rta_mp, r)) != 0) 749 goto failure; 750 if (rta->rta_oif && fi->fib_nh->nh_oif != *rta->rta_oif) 751 goto err_inval; 752 if (rta->rta_gw && memcmp(&fi->fib_nh->nh_gw, rta->rta_gw, 4)) 753 goto err_inval; 754 #ifdef CONFIG_NET_CLS_ROUTE 755 if (rta->rta_flow && memcmp(&fi->fib_nh->nh_tclassid, rta->rta_flow, 4)) 756 goto err_inval; 757 #endif 758 #else 759 goto err_inval; 760 #endif 761 } else { 762 struct fib_nh *nh = fi->fib_nh; 763 if (rta->rta_oif) 764 nh->nh_oif = *rta->rta_oif; 765 if (rta->rta_gw) 766 memcpy(&nh->nh_gw, rta->rta_gw, 4); 767 #ifdef CONFIG_NET_CLS_ROUTE 768 if (rta->rta_flow) 769 memcpy(&nh->nh_tclassid, rta->rta_flow, 4); 770 #endif 771 nh->nh_flags = r->rtm_flags; 772 #ifdef CONFIG_IP_ROUTE_MULTIPATH 773 nh->nh_weight = 1; 774 #endif 775 } 776 777 #ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED 778 fi->fib_mp_alg = mp_alg; 779 #endif 780 781 if (fib_props[r->rtm_type].error) { 782 if (rta->rta_gw || rta->rta_oif || rta->rta_mp) 783 goto err_inval; 784 goto link_it; 785 } 786 787 if (r->rtm_scope > RT_SCOPE_HOST) 788 goto err_inval; 789 790 if (r->rtm_scope == RT_SCOPE_HOST) { 791 struct fib_nh *nh = fi->fib_nh; 792 793 /* Local address is added. */ 794 if (nhs != 1 || nh->nh_gw) 795 goto err_inval; 796 nh->nh_scope = RT_SCOPE_NOWHERE; 797 nh->nh_dev = dev_get_by_index(fi->fib_nh->nh_oif); 798 err = -ENODEV; 799 if (nh->nh_dev == NULL) 800 goto failure; 801 } else { 802 change_nexthops(fi) { 803 if ((err = fib_check_nh(r, fi, nh)) != 0) 804 goto failure; 805 } endfor_nexthops(fi) 806 } 807 808 if (fi->fib_prefsrc) { 809 if (r->rtm_type != RTN_LOCAL || rta->rta_dst == NULL || 810 memcmp(&fi->fib_prefsrc, rta->rta_dst, 4)) 811 if (inet_addr_type(fi->fib_prefsrc) != RTN_LOCAL) 812 goto err_inval; 813 } 814 815 link_it: 816 if ((ofi = fib_find_info(fi)) != NULL) { 817 fi->fib_dead = 1; 818 free_fib_info(fi); 819 ofi->fib_treeref++; 820 return ofi; 821 } 822 823 fi->fib_treeref++; 824 atomic_inc(&fi->fib_clntref); 825 write_lock(&fib_info_lock); 826 hlist_add_head(&fi->fib_hash, 827 &fib_info_hash[fib_info_hashfn(fi)]); 828 if (fi->fib_prefsrc) { 829 struct hlist_head *head; 830 831 head = &fib_info_laddrhash[fib_laddr_hashfn(fi->fib_prefsrc)]; 832 hlist_add_head(&fi->fib_lhash, head); 833 } 834 change_nexthops(fi) { 835 struct hlist_head *head; 836 unsigned int hash; 837 838 if (!nh->nh_dev) 839 continue; 840 hash = fib_devindex_hashfn(nh->nh_dev->ifindex); 841 head = &fib_info_devhash[hash]; 842 hlist_add_head(&nh->nh_hash, head); 843 } endfor_nexthops(fi) 844 write_unlock(&fib_info_lock); 845 return fi; 846 847 err_inval: 848 err = -EINVAL; 849 850 failure: 851 *errp = err; 852 if (fi) { 853 fi->fib_dead = 1; 854 free_fib_info(fi); 855 } 856 return NULL; 857 } 858 859 /* Note! fib_semantic_match intentionally uses RCU list functions. */ 860 int fib_semantic_match(struct list_head *head, const struct flowi *flp, 861 struct fib_result *res, __u32 zone, __u32 mask, 862 int prefixlen) 863 { 864 struct fib_alias *fa; 865 int nh_sel = 0; 866 867 list_for_each_entry_rcu(fa, head, fa_list) { 868 int err; 869 870 if (fa->fa_tos && 871 fa->fa_tos != flp->fl4_tos) 872 continue; 873 874 if (fa->fa_scope < flp->fl4_scope) 875 continue; 876 877 fa->fa_state |= FA_S_ACCESSED; 878 879 err = fib_props[fa->fa_type].error; 880 if (err == 0) { 881 struct fib_info *fi = fa->fa_info; 882 883 if (fi->fib_flags & RTNH_F_DEAD) 884 continue; 885 886 switch (fa->fa_type) { 887 case RTN_UNICAST: 888 case RTN_LOCAL: 889 case RTN_BROADCAST: 890 case RTN_ANYCAST: 891 case RTN_MULTICAST: 892 for_nexthops(fi) { 893 if (nh->nh_flags&RTNH_F_DEAD) 894 continue; 895 if (!flp->oif || flp->oif == nh->nh_oif) 896 break; 897 } 898 #ifdef CONFIG_IP_ROUTE_MULTIPATH 899 if (nhsel < fi->fib_nhs) { 900 nh_sel = nhsel; 901 goto out_fill_res; 902 } 903 #else 904 if (nhsel < 1) { 905 goto out_fill_res; 906 } 907 #endif 908 endfor_nexthops(fi); 909 continue; 910 911 default: 912 printk(KERN_DEBUG "impossible 102\n"); 913 return -EINVAL; 914 }; 915 } 916 return err; 917 } 918 return 1; 919 920 out_fill_res: 921 res->prefixlen = prefixlen; 922 res->nh_sel = nh_sel; 923 res->type = fa->fa_type; 924 res->scope = fa->fa_scope; 925 res->fi = fa->fa_info; 926 #ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED 927 res->netmask = mask; 928 res->network = zone & 929 (0xFFFFFFFF >> (32 - prefixlen)); 930 #endif 931 atomic_inc(&res->fi->fib_clntref); 932 return 0; 933 } 934 935 /* Find appropriate source address to this destination */ 936 937 u32 __fib_res_prefsrc(struct fib_result *res) 938 { 939 return inet_select_addr(FIB_RES_DEV(*res), FIB_RES_GW(*res), res->scope); 940 } 941 942 int 943 fib_dump_info(struct sk_buff *skb, u32 pid, u32 seq, int event, 944 u8 tb_id, u8 type, u8 scope, void *dst, int dst_len, u8 tos, 945 struct fib_info *fi, unsigned int flags) 946 { 947 struct rtmsg *rtm; 948 struct nlmsghdr *nlh; 949 unsigned char *b = skb->tail; 950 951 nlh = NLMSG_NEW(skb, pid, seq, event, sizeof(*rtm), flags); 952 rtm = NLMSG_DATA(nlh); 953 rtm->rtm_family = AF_INET; 954 rtm->rtm_dst_len = dst_len; 955 rtm->rtm_src_len = 0; 956 rtm->rtm_tos = tos; 957 rtm->rtm_table = tb_id; 958 rtm->rtm_type = type; 959 rtm->rtm_flags = fi->fib_flags; 960 rtm->rtm_scope = scope; 961 if (rtm->rtm_dst_len) 962 RTA_PUT(skb, RTA_DST, 4, dst); 963 rtm->rtm_protocol = fi->fib_protocol; 964 if (fi->fib_priority) 965 RTA_PUT(skb, RTA_PRIORITY, 4, &fi->fib_priority); 966 #ifdef CONFIG_NET_CLS_ROUTE 967 if (fi->fib_nh[0].nh_tclassid) 968 RTA_PUT(skb, RTA_FLOW, 4, &fi->fib_nh[0].nh_tclassid); 969 #endif 970 if (rtnetlink_put_metrics(skb, fi->fib_metrics) < 0) 971 goto rtattr_failure; 972 if (fi->fib_prefsrc) 973 RTA_PUT(skb, RTA_PREFSRC, 4, &fi->fib_prefsrc); 974 if (fi->fib_nhs == 1) { 975 if (fi->fib_nh->nh_gw) 976 RTA_PUT(skb, RTA_GATEWAY, 4, &fi->fib_nh->nh_gw); 977 if (fi->fib_nh->nh_oif) 978 RTA_PUT(skb, RTA_OIF, sizeof(int), &fi->fib_nh->nh_oif); 979 } 980 #ifdef CONFIG_IP_ROUTE_MULTIPATH 981 if (fi->fib_nhs > 1) { 982 struct rtnexthop *nhp; 983 struct rtattr *mp_head; 984 if (skb_tailroom(skb) <= RTA_SPACE(0)) 985 goto rtattr_failure; 986 mp_head = (struct rtattr*)skb_put(skb, RTA_SPACE(0)); 987 988 for_nexthops(fi) { 989 if (skb_tailroom(skb) < RTA_ALIGN(RTA_ALIGN(sizeof(*nhp)) + 4)) 990 goto rtattr_failure; 991 nhp = (struct rtnexthop*)skb_put(skb, RTA_ALIGN(sizeof(*nhp))); 992 nhp->rtnh_flags = nh->nh_flags & 0xFF; 993 nhp->rtnh_hops = nh->nh_weight-1; 994 nhp->rtnh_ifindex = nh->nh_oif; 995 if (nh->nh_gw) 996 RTA_PUT(skb, RTA_GATEWAY, 4, &nh->nh_gw); 997 nhp->rtnh_len = skb->tail - (unsigned char*)nhp; 998 } endfor_nexthops(fi); 999 mp_head->rta_type = RTA_MULTIPATH; 1000 mp_head->rta_len = skb->tail - (u8*)mp_head; 1001 } 1002 #endif 1003 nlh->nlmsg_len = skb->tail - b; 1004 return skb->len; 1005 1006 nlmsg_failure: 1007 rtattr_failure: 1008 skb_trim(skb, b - skb->data); 1009 return -1; 1010 } 1011 1012 #ifndef CONFIG_IP_NOSIOCRT 1013 1014 int 1015 fib_convert_rtentry(int cmd, struct nlmsghdr *nl, struct rtmsg *rtm, 1016 struct kern_rta *rta, struct rtentry *r) 1017 { 1018 int plen; 1019 u32 *ptr; 1020 1021 memset(rtm, 0, sizeof(*rtm)); 1022 memset(rta, 0, sizeof(*rta)); 1023 1024 if (r->rt_dst.sa_family != AF_INET) 1025 return -EAFNOSUPPORT; 1026 1027 /* Check mask for validity: 1028 a) it must be contiguous. 1029 b) destination must have all host bits clear. 1030 c) if application forgot to set correct family (AF_INET), 1031 reject request unless it is absolutely clear i.e. 1032 both family and mask are zero. 1033 */ 1034 plen = 32; 1035 ptr = &((struct sockaddr_in*)&r->rt_dst)->sin_addr.s_addr; 1036 if (!(r->rt_flags&RTF_HOST)) { 1037 u32 mask = ((struct sockaddr_in*)&r->rt_genmask)->sin_addr.s_addr; 1038 if (r->rt_genmask.sa_family != AF_INET) { 1039 if (mask || r->rt_genmask.sa_family) 1040 return -EAFNOSUPPORT; 1041 } 1042 if (bad_mask(mask, *ptr)) 1043 return -EINVAL; 1044 plen = inet_mask_len(mask); 1045 } 1046 1047 nl->nlmsg_flags = NLM_F_REQUEST; 1048 nl->nlmsg_pid = 0; 1049 nl->nlmsg_seq = 0; 1050 nl->nlmsg_len = NLMSG_LENGTH(sizeof(*rtm)); 1051 if (cmd == SIOCDELRT) { 1052 nl->nlmsg_type = RTM_DELROUTE; 1053 nl->nlmsg_flags = 0; 1054 } else { 1055 nl->nlmsg_type = RTM_NEWROUTE; 1056 nl->nlmsg_flags = NLM_F_REQUEST|NLM_F_CREATE; 1057 rtm->rtm_protocol = RTPROT_BOOT; 1058 } 1059 1060 rtm->rtm_dst_len = plen; 1061 rta->rta_dst = ptr; 1062 1063 if (r->rt_metric) { 1064 *(u32*)&r->rt_pad3 = r->rt_metric - 1; 1065 rta->rta_priority = (u32*)&r->rt_pad3; 1066 } 1067 if (r->rt_flags&RTF_REJECT) { 1068 rtm->rtm_scope = RT_SCOPE_HOST; 1069 rtm->rtm_type = RTN_UNREACHABLE; 1070 return 0; 1071 } 1072 rtm->rtm_scope = RT_SCOPE_NOWHERE; 1073 rtm->rtm_type = RTN_UNICAST; 1074 1075 if (r->rt_dev) { 1076 char *colon; 1077 struct net_device *dev; 1078 char devname[IFNAMSIZ]; 1079 1080 if (copy_from_user(devname, r->rt_dev, IFNAMSIZ-1)) 1081 return -EFAULT; 1082 devname[IFNAMSIZ-1] = 0; 1083 colon = strchr(devname, ':'); 1084 if (colon) 1085 *colon = 0; 1086 dev = __dev_get_by_name(devname); 1087 if (!dev) 1088 return -ENODEV; 1089 rta->rta_oif = &dev->ifindex; 1090 if (colon) { 1091 struct in_ifaddr *ifa; 1092 struct in_device *in_dev = __in_dev_get_rtnl(dev); 1093 if (!in_dev) 1094 return -ENODEV; 1095 *colon = ':'; 1096 for (ifa = in_dev->ifa_list; ifa; ifa = ifa->ifa_next) 1097 if (strcmp(ifa->ifa_label, devname) == 0) 1098 break; 1099 if (ifa == NULL) 1100 return -ENODEV; 1101 rta->rta_prefsrc = &ifa->ifa_local; 1102 } 1103 } 1104 1105 ptr = &((struct sockaddr_in*)&r->rt_gateway)->sin_addr.s_addr; 1106 if (r->rt_gateway.sa_family == AF_INET && *ptr) { 1107 rta->rta_gw = ptr; 1108 if (r->rt_flags&RTF_GATEWAY && inet_addr_type(*ptr) == RTN_UNICAST) 1109 rtm->rtm_scope = RT_SCOPE_UNIVERSE; 1110 } 1111 1112 if (cmd == SIOCDELRT) 1113 return 0; 1114 1115 if (r->rt_flags&RTF_GATEWAY && rta->rta_gw == NULL) 1116 return -EINVAL; 1117 1118 if (rtm->rtm_scope == RT_SCOPE_NOWHERE) 1119 rtm->rtm_scope = RT_SCOPE_LINK; 1120 1121 if (r->rt_flags&(RTF_MTU|RTF_WINDOW|RTF_IRTT)) { 1122 struct rtattr *rec; 1123 struct rtattr *mx = kmalloc(RTA_LENGTH(3*RTA_LENGTH(4)), GFP_KERNEL); 1124 if (mx == NULL) 1125 return -ENOMEM; 1126 rta->rta_mx = mx; 1127 mx->rta_type = RTA_METRICS; 1128 mx->rta_len = RTA_LENGTH(0); 1129 if (r->rt_flags&RTF_MTU) { 1130 rec = (void*)((char*)mx + RTA_ALIGN(mx->rta_len)); 1131 rec->rta_type = RTAX_ADVMSS; 1132 rec->rta_len = RTA_LENGTH(4); 1133 mx->rta_len += RTA_LENGTH(4); 1134 *(u32*)RTA_DATA(rec) = r->rt_mtu - 40; 1135 } 1136 if (r->rt_flags&RTF_WINDOW) { 1137 rec = (void*)((char*)mx + RTA_ALIGN(mx->rta_len)); 1138 rec->rta_type = RTAX_WINDOW; 1139 rec->rta_len = RTA_LENGTH(4); 1140 mx->rta_len += RTA_LENGTH(4); 1141 *(u32*)RTA_DATA(rec) = r->rt_window; 1142 } 1143 if (r->rt_flags&RTF_IRTT) { 1144 rec = (void*)((char*)mx + RTA_ALIGN(mx->rta_len)); 1145 rec->rta_type = RTAX_RTT; 1146 rec->rta_len = RTA_LENGTH(4); 1147 mx->rta_len += RTA_LENGTH(4); 1148 *(u32*)RTA_DATA(rec) = r->rt_irtt<<3; 1149 } 1150 } 1151 return 0; 1152 } 1153 1154 #endif 1155 1156 /* 1157 Update FIB if: 1158 - local address disappeared -> we must delete all the entries 1159 referring to it. 1160 - device went down -> we must shutdown all nexthops going via it. 1161 */ 1162 1163 int fib_sync_down(u32 local, struct net_device *dev, int force) 1164 { 1165 int ret = 0; 1166 int scope = RT_SCOPE_NOWHERE; 1167 1168 if (force) 1169 scope = -1; 1170 1171 if (local && fib_info_laddrhash) { 1172 unsigned int hash = fib_laddr_hashfn(local); 1173 struct hlist_head *head = &fib_info_laddrhash[hash]; 1174 struct hlist_node *node; 1175 struct fib_info *fi; 1176 1177 hlist_for_each_entry(fi, node, head, fib_lhash) { 1178 if (fi->fib_prefsrc == local) { 1179 fi->fib_flags |= RTNH_F_DEAD; 1180 ret++; 1181 } 1182 } 1183 } 1184 1185 if (dev) { 1186 struct fib_info *prev_fi = NULL; 1187 unsigned int hash = fib_devindex_hashfn(dev->ifindex); 1188 struct hlist_head *head = &fib_info_devhash[hash]; 1189 struct hlist_node *node; 1190 struct fib_nh *nh; 1191 1192 hlist_for_each_entry(nh, node, head, nh_hash) { 1193 struct fib_info *fi = nh->nh_parent; 1194 int dead; 1195 1196 BUG_ON(!fi->fib_nhs); 1197 if (nh->nh_dev != dev || fi == prev_fi) 1198 continue; 1199 prev_fi = fi; 1200 dead = 0; 1201 change_nexthops(fi) { 1202 if (nh->nh_flags&RTNH_F_DEAD) 1203 dead++; 1204 else if (nh->nh_dev == dev && 1205 nh->nh_scope != scope) { 1206 nh->nh_flags |= RTNH_F_DEAD; 1207 #ifdef CONFIG_IP_ROUTE_MULTIPATH 1208 spin_lock_bh(&fib_multipath_lock); 1209 fi->fib_power -= nh->nh_power; 1210 nh->nh_power = 0; 1211 spin_unlock_bh(&fib_multipath_lock); 1212 #endif 1213 dead++; 1214 } 1215 #ifdef CONFIG_IP_ROUTE_MULTIPATH 1216 if (force > 1 && nh->nh_dev == dev) { 1217 dead = fi->fib_nhs; 1218 break; 1219 } 1220 #endif 1221 } endfor_nexthops(fi) 1222 if (dead == fi->fib_nhs) { 1223 fi->fib_flags |= RTNH_F_DEAD; 1224 ret++; 1225 } 1226 } 1227 } 1228 1229 return ret; 1230 } 1231 1232 #ifdef CONFIG_IP_ROUTE_MULTIPATH 1233 1234 /* 1235 Dead device goes up. We wake up dead nexthops. 1236 It takes sense only on multipath routes. 1237 */ 1238 1239 int fib_sync_up(struct net_device *dev) 1240 { 1241 struct fib_info *prev_fi; 1242 unsigned int hash; 1243 struct hlist_head *head; 1244 struct hlist_node *node; 1245 struct fib_nh *nh; 1246 int ret; 1247 1248 if (!(dev->flags&IFF_UP)) 1249 return 0; 1250 1251 prev_fi = NULL; 1252 hash = fib_devindex_hashfn(dev->ifindex); 1253 head = &fib_info_devhash[hash]; 1254 ret = 0; 1255 1256 hlist_for_each_entry(nh, node, head, nh_hash) { 1257 struct fib_info *fi = nh->nh_parent; 1258 int alive; 1259 1260 BUG_ON(!fi->fib_nhs); 1261 if (nh->nh_dev != dev || fi == prev_fi) 1262 continue; 1263 1264 prev_fi = fi; 1265 alive = 0; 1266 change_nexthops(fi) { 1267 if (!(nh->nh_flags&RTNH_F_DEAD)) { 1268 alive++; 1269 continue; 1270 } 1271 if (nh->nh_dev == NULL || !(nh->nh_dev->flags&IFF_UP)) 1272 continue; 1273 if (nh->nh_dev != dev || !__in_dev_get_rtnl(dev)) 1274 continue; 1275 alive++; 1276 spin_lock_bh(&fib_multipath_lock); 1277 nh->nh_power = 0; 1278 nh->nh_flags &= ~RTNH_F_DEAD; 1279 spin_unlock_bh(&fib_multipath_lock); 1280 } endfor_nexthops(fi) 1281 1282 if (alive > 0) { 1283 fi->fib_flags &= ~RTNH_F_DEAD; 1284 ret++; 1285 } 1286 } 1287 1288 return ret; 1289 } 1290 1291 /* 1292 The algorithm is suboptimal, but it provides really 1293 fair weighted route distribution. 1294 */ 1295 1296 void fib_select_multipath(const struct flowi *flp, struct fib_result *res) 1297 { 1298 struct fib_info *fi = res->fi; 1299 int w; 1300 1301 spin_lock_bh(&fib_multipath_lock); 1302 if (fi->fib_power <= 0) { 1303 int power = 0; 1304 change_nexthops(fi) { 1305 if (!(nh->nh_flags&RTNH_F_DEAD)) { 1306 power += nh->nh_weight; 1307 nh->nh_power = nh->nh_weight; 1308 } 1309 } endfor_nexthops(fi); 1310 fi->fib_power = power; 1311 if (power <= 0) { 1312 spin_unlock_bh(&fib_multipath_lock); 1313 /* Race condition: route has just become dead. */ 1314 res->nh_sel = 0; 1315 return; 1316 } 1317 } 1318 1319 1320 /* w should be random number [0..fi->fib_power-1], 1321 it is pretty bad approximation. 1322 */ 1323 1324 w = jiffies % fi->fib_power; 1325 1326 change_nexthops(fi) { 1327 if (!(nh->nh_flags&RTNH_F_DEAD) && nh->nh_power) { 1328 if ((w -= nh->nh_power) <= 0) { 1329 nh->nh_power--; 1330 fi->fib_power--; 1331 res->nh_sel = nhsel; 1332 spin_unlock_bh(&fib_multipath_lock); 1333 return; 1334 } 1335 } 1336 } endfor_nexthops(fi); 1337 1338 /* Race condition: route has just become dead. */ 1339 res->nh_sel = 0; 1340 spin_unlock_bh(&fib_multipath_lock); 1341 } 1342 #endif 1343