net/ipv4/fib_semantics.c

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