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