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