11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds * INET An implementation of the TCP/IP protocol suite for the LINUX 31da177e4SLinus Torvalds * operating system. INET is implemented using the BSD Socket 41da177e4SLinus Torvalds * interface as the means of communication with the user level. 51da177e4SLinus Torvalds * 61da177e4SLinus Torvalds * IPv4 Forwarding Information Base: semantics. 71da177e4SLinus Torvalds * 81da177e4SLinus Torvalds * Version: $Id: fib_semantics.c,v 1.19 2002/01/12 07:54:56 davem Exp $ 91da177e4SLinus Torvalds * 101da177e4SLinus Torvalds * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru> 111da177e4SLinus Torvalds * 121da177e4SLinus Torvalds * This program is free software; you can redistribute it and/or 131da177e4SLinus Torvalds * modify it under the terms of the GNU General Public License 141da177e4SLinus Torvalds * as published by the Free Software Foundation; either version 151da177e4SLinus Torvalds * 2 of the License, or (at your option) any later version. 161da177e4SLinus Torvalds */ 171da177e4SLinus Torvalds 181da177e4SLinus Torvalds #include <asm/uaccess.h> 191da177e4SLinus Torvalds #include <asm/system.h> 201da177e4SLinus Torvalds #include <linux/bitops.h> 211da177e4SLinus Torvalds #include <linux/types.h> 221da177e4SLinus Torvalds #include <linux/kernel.h> 231da177e4SLinus Torvalds #include <linux/jiffies.h> 241da177e4SLinus Torvalds #include <linux/mm.h> 251da177e4SLinus Torvalds #include <linux/string.h> 261da177e4SLinus Torvalds #include <linux/socket.h> 271da177e4SLinus Torvalds #include <linux/sockios.h> 281da177e4SLinus Torvalds #include <linux/errno.h> 291da177e4SLinus Torvalds #include <linux/in.h> 301da177e4SLinus Torvalds #include <linux/inet.h> 3114c85021SArnaldo Carvalho de Melo #include <linux/inetdevice.h> 321da177e4SLinus Torvalds #include <linux/netdevice.h> 331da177e4SLinus Torvalds #include <linux/if_arp.h> 341da177e4SLinus Torvalds #include <linux/proc_fs.h> 351da177e4SLinus Torvalds #include <linux/skbuff.h> 361da177e4SLinus Torvalds #include <linux/init.h> 371da177e4SLinus Torvalds 3814c85021SArnaldo Carvalho de Melo #include <net/arp.h> 391da177e4SLinus Torvalds #include <net/ip.h> 401da177e4SLinus Torvalds #include <net/protocol.h> 411da177e4SLinus Torvalds #include <net/route.h> 421da177e4SLinus Torvalds #include <net/tcp.h> 431da177e4SLinus Torvalds #include <net/sock.h> 441da177e4SLinus Torvalds #include <net/ip_fib.h> 451da177e4SLinus Torvalds #include <net/ip_mp_alg.h> 46f21c7bc5SThomas Graf #include <net/netlink.h> 474e902c57SThomas Graf #include <net/nexthop.h> 481da177e4SLinus Torvalds 491da177e4SLinus Torvalds #include "fib_lookup.h" 501da177e4SLinus Torvalds 511da177e4SLinus Torvalds #define FSprintk(a...) 521da177e4SLinus Torvalds 53832b4c5eSStephen Hemminger static DEFINE_SPINLOCK(fib_info_lock); 541da177e4SLinus Torvalds static struct hlist_head *fib_info_hash; 551da177e4SLinus Torvalds static struct hlist_head *fib_info_laddrhash; 561da177e4SLinus Torvalds static unsigned int fib_hash_size; 571da177e4SLinus Torvalds static unsigned int fib_info_cnt; 581da177e4SLinus Torvalds 591da177e4SLinus Torvalds #define DEVINDEX_HASHBITS 8 601da177e4SLinus Torvalds #define DEVINDEX_HASHSIZE (1U << DEVINDEX_HASHBITS) 611da177e4SLinus Torvalds static struct hlist_head fib_info_devhash[DEVINDEX_HASHSIZE]; 621da177e4SLinus Torvalds 631da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH 641da177e4SLinus Torvalds 651da177e4SLinus Torvalds static DEFINE_SPINLOCK(fib_multipath_lock); 661da177e4SLinus Torvalds 671da177e4SLinus Torvalds #define for_nexthops(fi) { int nhsel; const struct fib_nh * nh; \ 681da177e4SLinus Torvalds for (nhsel=0, nh = (fi)->fib_nh; nhsel < (fi)->fib_nhs; nh++, nhsel++) 691da177e4SLinus Torvalds 701da177e4SLinus Torvalds #define change_nexthops(fi) { int nhsel; struct fib_nh * nh; \ 711da177e4SLinus Torvalds for (nhsel=0, nh = (struct fib_nh*)((fi)->fib_nh); nhsel < (fi)->fib_nhs; nh++, nhsel++) 721da177e4SLinus Torvalds 731da177e4SLinus Torvalds #else /* CONFIG_IP_ROUTE_MULTIPATH */ 741da177e4SLinus Torvalds 751da177e4SLinus Torvalds /* Hope, that gcc will optimize it to get rid of dummy loop */ 761da177e4SLinus Torvalds 771da177e4SLinus Torvalds #define for_nexthops(fi) { int nhsel=0; const struct fib_nh * nh = (fi)->fib_nh; \ 781da177e4SLinus Torvalds for (nhsel=0; nhsel < 1; nhsel++) 791da177e4SLinus Torvalds 801da177e4SLinus Torvalds #define change_nexthops(fi) { int nhsel=0; struct fib_nh * nh = (struct fib_nh*)((fi)->fib_nh); \ 811da177e4SLinus Torvalds for (nhsel=0; nhsel < 1; nhsel++) 821da177e4SLinus Torvalds 831da177e4SLinus Torvalds #endif /* CONFIG_IP_ROUTE_MULTIPATH */ 841da177e4SLinus Torvalds 851da177e4SLinus Torvalds #define endfor_nexthops(fi) } 861da177e4SLinus Torvalds 871da177e4SLinus Torvalds 889b5b5cffSArjan van de Ven static const struct 891da177e4SLinus Torvalds { 901da177e4SLinus Torvalds int error; 911da177e4SLinus Torvalds u8 scope; 921da177e4SLinus Torvalds } fib_props[RTA_MAX + 1] = { 931da177e4SLinus Torvalds { 941da177e4SLinus Torvalds .error = 0, 951da177e4SLinus Torvalds .scope = RT_SCOPE_NOWHERE, 961da177e4SLinus Torvalds }, /* RTN_UNSPEC */ 971da177e4SLinus Torvalds { 981da177e4SLinus Torvalds .error = 0, 991da177e4SLinus Torvalds .scope = RT_SCOPE_UNIVERSE, 1001da177e4SLinus Torvalds }, /* RTN_UNICAST */ 1011da177e4SLinus Torvalds { 1021da177e4SLinus Torvalds .error = 0, 1031da177e4SLinus Torvalds .scope = RT_SCOPE_HOST, 1041da177e4SLinus Torvalds }, /* RTN_LOCAL */ 1051da177e4SLinus Torvalds { 1061da177e4SLinus Torvalds .error = 0, 1071da177e4SLinus Torvalds .scope = RT_SCOPE_LINK, 1081da177e4SLinus Torvalds }, /* RTN_BROADCAST */ 1091da177e4SLinus Torvalds { 1101da177e4SLinus Torvalds .error = 0, 1111da177e4SLinus Torvalds .scope = RT_SCOPE_LINK, 1121da177e4SLinus Torvalds }, /* RTN_ANYCAST */ 1131da177e4SLinus Torvalds { 1141da177e4SLinus Torvalds .error = 0, 1151da177e4SLinus Torvalds .scope = RT_SCOPE_UNIVERSE, 1161da177e4SLinus Torvalds }, /* RTN_MULTICAST */ 1171da177e4SLinus Torvalds { 1181da177e4SLinus Torvalds .error = -EINVAL, 1191da177e4SLinus Torvalds .scope = RT_SCOPE_UNIVERSE, 1201da177e4SLinus Torvalds }, /* RTN_BLACKHOLE */ 1211da177e4SLinus Torvalds { 1221da177e4SLinus Torvalds .error = -EHOSTUNREACH, 1231da177e4SLinus Torvalds .scope = RT_SCOPE_UNIVERSE, 1241da177e4SLinus Torvalds }, /* RTN_UNREACHABLE */ 1251da177e4SLinus Torvalds { 1261da177e4SLinus Torvalds .error = -EACCES, 1271da177e4SLinus Torvalds .scope = RT_SCOPE_UNIVERSE, 1281da177e4SLinus Torvalds }, /* RTN_PROHIBIT */ 1291da177e4SLinus Torvalds { 1301da177e4SLinus Torvalds .error = -EAGAIN, 1311da177e4SLinus Torvalds .scope = RT_SCOPE_UNIVERSE, 1321da177e4SLinus Torvalds }, /* RTN_THROW */ 1331da177e4SLinus Torvalds { 1341da177e4SLinus Torvalds .error = -EINVAL, 1351da177e4SLinus Torvalds .scope = RT_SCOPE_NOWHERE, 1361da177e4SLinus Torvalds }, /* RTN_NAT */ 1371da177e4SLinus Torvalds { 1381da177e4SLinus Torvalds .error = -EINVAL, 1391da177e4SLinus Torvalds .scope = RT_SCOPE_NOWHERE, 1401da177e4SLinus Torvalds }, /* RTN_XRESOLVE */ 1411da177e4SLinus Torvalds }; 1421da177e4SLinus Torvalds 1431da177e4SLinus Torvalds 1441da177e4SLinus Torvalds /* Release a nexthop info record */ 1451da177e4SLinus Torvalds 1461da177e4SLinus Torvalds void free_fib_info(struct fib_info *fi) 1471da177e4SLinus Torvalds { 1481da177e4SLinus Torvalds if (fi->fib_dead == 0) { 1491da177e4SLinus Torvalds printk("Freeing alive fib_info %p\n", fi); 1501da177e4SLinus Torvalds return; 1511da177e4SLinus Torvalds } 1521da177e4SLinus Torvalds change_nexthops(fi) { 1531da177e4SLinus Torvalds if (nh->nh_dev) 1541da177e4SLinus Torvalds dev_put(nh->nh_dev); 1551da177e4SLinus Torvalds nh->nh_dev = NULL; 1561da177e4SLinus Torvalds } endfor_nexthops(fi); 1571da177e4SLinus Torvalds fib_info_cnt--; 1581da177e4SLinus Torvalds kfree(fi); 1591da177e4SLinus Torvalds } 1601da177e4SLinus Torvalds 1611da177e4SLinus Torvalds void fib_release_info(struct fib_info *fi) 1621da177e4SLinus Torvalds { 163832b4c5eSStephen Hemminger spin_lock_bh(&fib_info_lock); 1641da177e4SLinus Torvalds if (fi && --fi->fib_treeref == 0) { 1651da177e4SLinus Torvalds hlist_del(&fi->fib_hash); 1661da177e4SLinus Torvalds if (fi->fib_prefsrc) 1671da177e4SLinus Torvalds hlist_del(&fi->fib_lhash); 1681da177e4SLinus Torvalds change_nexthops(fi) { 1691da177e4SLinus Torvalds if (!nh->nh_dev) 1701da177e4SLinus Torvalds continue; 1711da177e4SLinus Torvalds hlist_del(&nh->nh_hash); 1721da177e4SLinus Torvalds } endfor_nexthops(fi) 1731da177e4SLinus Torvalds fi->fib_dead = 1; 1741da177e4SLinus Torvalds fib_info_put(fi); 1751da177e4SLinus Torvalds } 176832b4c5eSStephen Hemminger spin_unlock_bh(&fib_info_lock); 1771da177e4SLinus Torvalds } 1781da177e4SLinus Torvalds 1791da177e4SLinus Torvalds static __inline__ int nh_comp(const struct fib_info *fi, const struct fib_info *ofi) 1801da177e4SLinus Torvalds { 1811da177e4SLinus Torvalds const struct fib_nh *onh = ofi->fib_nh; 1821da177e4SLinus Torvalds 1831da177e4SLinus Torvalds for_nexthops(fi) { 1841da177e4SLinus Torvalds if (nh->nh_oif != onh->nh_oif || 1851da177e4SLinus Torvalds nh->nh_gw != onh->nh_gw || 1861da177e4SLinus Torvalds nh->nh_scope != onh->nh_scope || 1871da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH 1881da177e4SLinus Torvalds nh->nh_weight != onh->nh_weight || 1891da177e4SLinus Torvalds #endif 1901da177e4SLinus Torvalds #ifdef CONFIG_NET_CLS_ROUTE 1911da177e4SLinus Torvalds nh->nh_tclassid != onh->nh_tclassid || 1921da177e4SLinus Torvalds #endif 1931da177e4SLinus Torvalds ((nh->nh_flags^onh->nh_flags)&~RTNH_F_DEAD)) 1941da177e4SLinus Torvalds return -1; 1951da177e4SLinus Torvalds onh++; 1961da177e4SLinus Torvalds } endfor_nexthops(fi); 1971da177e4SLinus Torvalds return 0; 1981da177e4SLinus Torvalds } 1991da177e4SLinus Torvalds 2001da177e4SLinus Torvalds static inline unsigned int fib_info_hashfn(const struct fib_info *fi) 2011da177e4SLinus Torvalds { 2021da177e4SLinus Torvalds unsigned int mask = (fib_hash_size - 1); 2031da177e4SLinus Torvalds unsigned int val = fi->fib_nhs; 2041da177e4SLinus Torvalds 2051da177e4SLinus Torvalds val ^= fi->fib_protocol; 2061da177e4SLinus Torvalds val ^= fi->fib_prefsrc; 2071da177e4SLinus Torvalds val ^= fi->fib_priority; 2081da177e4SLinus Torvalds 2091da177e4SLinus Torvalds return (val ^ (val >> 7) ^ (val >> 12)) & mask; 2101da177e4SLinus Torvalds } 2111da177e4SLinus Torvalds 2121da177e4SLinus Torvalds static struct fib_info *fib_find_info(const struct fib_info *nfi) 2131da177e4SLinus Torvalds { 2141da177e4SLinus Torvalds struct hlist_head *head; 2151da177e4SLinus Torvalds struct hlist_node *node; 2161da177e4SLinus Torvalds struct fib_info *fi; 2171da177e4SLinus Torvalds unsigned int hash; 2181da177e4SLinus Torvalds 2191da177e4SLinus Torvalds hash = fib_info_hashfn(nfi); 2201da177e4SLinus Torvalds head = &fib_info_hash[hash]; 2211da177e4SLinus Torvalds 2221da177e4SLinus Torvalds hlist_for_each_entry(fi, node, head, fib_hash) { 2231da177e4SLinus Torvalds if (fi->fib_nhs != nfi->fib_nhs) 2241da177e4SLinus Torvalds continue; 2251da177e4SLinus Torvalds if (nfi->fib_protocol == fi->fib_protocol && 2261da177e4SLinus Torvalds nfi->fib_prefsrc == fi->fib_prefsrc && 2271da177e4SLinus Torvalds nfi->fib_priority == fi->fib_priority && 2281da177e4SLinus Torvalds memcmp(nfi->fib_metrics, fi->fib_metrics, 2291da177e4SLinus Torvalds sizeof(fi->fib_metrics)) == 0 && 2301da177e4SLinus Torvalds ((nfi->fib_flags^fi->fib_flags)&~RTNH_F_DEAD) == 0 && 2311da177e4SLinus Torvalds (nfi->fib_nhs == 0 || nh_comp(fi, nfi) == 0)) 2321da177e4SLinus Torvalds return fi; 2331da177e4SLinus Torvalds } 2341da177e4SLinus Torvalds 2351da177e4SLinus Torvalds return NULL; 2361da177e4SLinus Torvalds } 2371da177e4SLinus Torvalds 2381da177e4SLinus Torvalds static inline unsigned int fib_devindex_hashfn(unsigned int val) 2391da177e4SLinus Torvalds { 2401da177e4SLinus Torvalds unsigned int mask = DEVINDEX_HASHSIZE - 1; 2411da177e4SLinus Torvalds 2421da177e4SLinus Torvalds return (val ^ 2431da177e4SLinus Torvalds (val >> DEVINDEX_HASHBITS) ^ 2441da177e4SLinus Torvalds (val >> (DEVINDEX_HASHBITS * 2))) & mask; 2451da177e4SLinus Torvalds } 2461da177e4SLinus Torvalds 2471da177e4SLinus Torvalds /* Check, that the gateway is already configured. 2481da177e4SLinus Torvalds Used only by redirect accept routine. 2491da177e4SLinus Torvalds */ 2501da177e4SLinus Torvalds 2511da177e4SLinus Torvalds int ip_fib_check_default(u32 gw, struct net_device *dev) 2521da177e4SLinus Torvalds { 2531da177e4SLinus Torvalds struct hlist_head *head; 2541da177e4SLinus Torvalds struct hlist_node *node; 2551da177e4SLinus Torvalds struct fib_nh *nh; 2561da177e4SLinus Torvalds unsigned int hash; 2571da177e4SLinus Torvalds 258832b4c5eSStephen Hemminger spin_lock(&fib_info_lock); 2591da177e4SLinus Torvalds 2601da177e4SLinus Torvalds hash = fib_devindex_hashfn(dev->ifindex); 2611da177e4SLinus Torvalds head = &fib_info_devhash[hash]; 2621da177e4SLinus Torvalds hlist_for_each_entry(nh, node, head, nh_hash) { 2631da177e4SLinus Torvalds if (nh->nh_dev == dev && 2641da177e4SLinus Torvalds nh->nh_gw == gw && 2651da177e4SLinus Torvalds !(nh->nh_flags&RTNH_F_DEAD)) { 266832b4c5eSStephen Hemminger spin_unlock(&fib_info_lock); 2671da177e4SLinus Torvalds return 0; 2681da177e4SLinus Torvalds } 2691da177e4SLinus Torvalds } 2701da177e4SLinus Torvalds 271832b4c5eSStephen Hemminger spin_unlock(&fib_info_lock); 2721da177e4SLinus Torvalds 2731da177e4SLinus Torvalds return -1; 2741da177e4SLinus Torvalds } 2751da177e4SLinus Torvalds 2761da177e4SLinus Torvalds void rtmsg_fib(int event, u32 key, struct fib_alias *fa, 2774e902c57SThomas Graf int dst_len, u32 tb_id, struct nl_info *info) 2781da177e4SLinus Torvalds { 2791da177e4SLinus Torvalds struct sk_buff *skb; 280f21c7bc5SThomas Graf int payload = sizeof(struct rtmsg) + 256; 2814e902c57SThomas Graf u32 seq = info->nlh ? info->nlh->nlmsg_seq : 0; 282f21c7bc5SThomas Graf int err = -ENOBUFS; 2831da177e4SLinus Torvalds 284f21c7bc5SThomas Graf skb = nlmsg_new(nlmsg_total_size(payload), GFP_KERNEL); 285f21c7bc5SThomas Graf if (skb == NULL) 286f21c7bc5SThomas Graf goto errout; 2871da177e4SLinus Torvalds 2884e902c57SThomas Graf err = fib_dump_info(skb, info->pid, seq, event, tb_id, 289be403ea1SThomas Graf fa->fa_type, fa->fa_scope, key, dst_len, 2904e902c57SThomas Graf fa->fa_tos, fa->fa_info, 0); 291f21c7bc5SThomas Graf if (err < 0) { 2921da177e4SLinus Torvalds kfree_skb(skb); 293f21c7bc5SThomas Graf goto errout; 2941da177e4SLinus Torvalds } 295f21c7bc5SThomas Graf 2964e902c57SThomas Graf err = rtnl_notify(skb, info->pid, RTNLGRP_IPV4_ROUTE, 2974e902c57SThomas Graf info->nlh, GFP_KERNEL); 298f21c7bc5SThomas Graf errout: 299f21c7bc5SThomas Graf if (err < 0) 300f21c7bc5SThomas Graf rtnl_set_sk_err(RTNLGRP_IPV4_ROUTE, err); 3011da177e4SLinus Torvalds } 3021da177e4SLinus Torvalds 3031da177e4SLinus Torvalds /* Return the first fib alias matching TOS with 3041da177e4SLinus Torvalds * priority less than or equal to PRIO. 3051da177e4SLinus Torvalds */ 3061da177e4SLinus Torvalds struct fib_alias *fib_find_alias(struct list_head *fah, u8 tos, u32 prio) 3071da177e4SLinus Torvalds { 3081da177e4SLinus Torvalds if (fah) { 3091da177e4SLinus Torvalds struct fib_alias *fa; 3101da177e4SLinus Torvalds list_for_each_entry(fa, fah, fa_list) { 3111da177e4SLinus Torvalds if (fa->fa_tos > tos) 3121da177e4SLinus Torvalds continue; 3131da177e4SLinus Torvalds if (fa->fa_info->fib_priority >= prio || 3141da177e4SLinus Torvalds fa->fa_tos < tos) 3151da177e4SLinus Torvalds return fa; 3161da177e4SLinus Torvalds } 3171da177e4SLinus Torvalds } 3181da177e4SLinus Torvalds return NULL; 3191da177e4SLinus Torvalds } 3201da177e4SLinus Torvalds 3211da177e4SLinus Torvalds int fib_detect_death(struct fib_info *fi, int order, 3221da177e4SLinus Torvalds struct fib_info **last_resort, int *last_idx, int *dflt) 3231da177e4SLinus Torvalds { 3241da177e4SLinus Torvalds struct neighbour *n; 3251da177e4SLinus Torvalds int state = NUD_NONE; 3261da177e4SLinus Torvalds 3271da177e4SLinus Torvalds n = neigh_lookup(&arp_tbl, &fi->fib_nh[0].nh_gw, fi->fib_dev); 3281da177e4SLinus Torvalds if (n) { 3291da177e4SLinus Torvalds state = n->nud_state; 3301da177e4SLinus Torvalds neigh_release(n); 3311da177e4SLinus Torvalds } 3321da177e4SLinus Torvalds if (state==NUD_REACHABLE) 3331da177e4SLinus Torvalds return 0; 3341da177e4SLinus Torvalds if ((state&NUD_VALID) && order != *dflt) 3351da177e4SLinus Torvalds return 0; 3361da177e4SLinus Torvalds if ((state&NUD_VALID) || 3371da177e4SLinus Torvalds (*last_idx<0 && order > *dflt)) { 3381da177e4SLinus Torvalds *last_resort = fi; 3391da177e4SLinus Torvalds *last_idx = order; 3401da177e4SLinus Torvalds } 3411da177e4SLinus Torvalds return 1; 3421da177e4SLinus Torvalds } 3431da177e4SLinus Torvalds 3441da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH 3451da177e4SLinus Torvalds 3464e902c57SThomas Graf static int fib_count_nexthops(struct rtnexthop *rtnh, int remaining) 3471da177e4SLinus Torvalds { 3481da177e4SLinus Torvalds int nhs = 0; 3491da177e4SLinus Torvalds 3504e902c57SThomas Graf while (rtnh_ok(rtnh, remaining)) { 3511da177e4SLinus Torvalds nhs++; 3524e902c57SThomas Graf rtnh = rtnh_next(rtnh, &remaining); 3531da177e4SLinus Torvalds } 3541da177e4SLinus Torvalds 3554e902c57SThomas Graf /* leftover implies invalid nexthop configuration, discard it */ 3564e902c57SThomas Graf return remaining > 0 ? 0 : nhs; 3574e902c57SThomas Graf } 3581da177e4SLinus Torvalds 3594e902c57SThomas Graf static int fib_get_nhs(struct fib_info *fi, struct rtnexthop *rtnh, 3604e902c57SThomas Graf int remaining, struct fib_config *cfg) 3614e902c57SThomas Graf { 3621da177e4SLinus Torvalds change_nexthops(fi) { 3634e902c57SThomas Graf int attrlen; 3644e902c57SThomas Graf 3654e902c57SThomas Graf if (!rtnh_ok(rtnh, remaining)) 3661da177e4SLinus Torvalds return -EINVAL; 3674e902c57SThomas Graf 3684e902c57SThomas Graf nh->nh_flags = (cfg->fc_flags & ~0xFF) | rtnh->rtnh_flags; 3694e902c57SThomas Graf nh->nh_oif = rtnh->rtnh_ifindex; 3704e902c57SThomas Graf nh->nh_weight = rtnh->rtnh_hops + 1; 3714e902c57SThomas Graf 3724e902c57SThomas Graf attrlen = rtnh_attrlen(rtnh); 3734e902c57SThomas Graf if (attrlen > 0) { 3744e902c57SThomas Graf struct nlattr *nla, *attrs = rtnh_attrs(rtnh); 3754e902c57SThomas Graf 3764e902c57SThomas Graf nla = nla_find(attrs, attrlen, RTA_GATEWAY); 3774e902c57SThomas Graf nh->nh_gw = nla ? nla_get_u32(nla) : 0; 3781da177e4SLinus Torvalds #ifdef CONFIG_NET_CLS_ROUTE 3794e902c57SThomas Graf nla = nla_find(attrs, attrlen, RTA_FLOW); 3804e902c57SThomas Graf nh->nh_tclassid = nla ? nla_get_u32(nla) : 0; 3811da177e4SLinus Torvalds #endif 3821da177e4SLinus Torvalds } 3834e902c57SThomas Graf 3844e902c57SThomas Graf rtnh = rtnh_next(rtnh, &remaining); 3851da177e4SLinus Torvalds } endfor_nexthops(fi); 3864e902c57SThomas Graf 3871da177e4SLinus Torvalds return 0; 3881da177e4SLinus Torvalds } 3891da177e4SLinus Torvalds 3901da177e4SLinus Torvalds #endif 3911da177e4SLinus Torvalds 3924e902c57SThomas Graf int fib_nh_match(struct fib_config *cfg, struct fib_info *fi) 3931da177e4SLinus Torvalds { 3941da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH 3954e902c57SThomas Graf struct rtnexthop *rtnh; 3964e902c57SThomas Graf int remaining; 3971da177e4SLinus Torvalds #endif 3981da177e4SLinus Torvalds 3994e902c57SThomas Graf if (cfg->fc_priority && cfg->fc_priority != fi->fib_priority) 4001da177e4SLinus Torvalds return 1; 4011da177e4SLinus Torvalds 4024e902c57SThomas Graf if (cfg->fc_oif || cfg->fc_gw) { 4034e902c57SThomas Graf if ((!cfg->fc_oif || cfg->fc_oif == fi->fib_nh->nh_oif) && 4044e902c57SThomas Graf (!cfg->fc_gw || cfg->fc_gw == fi->fib_nh->nh_gw)) 4051da177e4SLinus Torvalds return 0; 4061da177e4SLinus Torvalds return 1; 4071da177e4SLinus Torvalds } 4081da177e4SLinus Torvalds 4091da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH 4104e902c57SThomas Graf if (cfg->fc_mp == NULL) 4111da177e4SLinus Torvalds return 0; 4124e902c57SThomas Graf 4134e902c57SThomas Graf rtnh = cfg->fc_mp; 4144e902c57SThomas Graf remaining = cfg->fc_mp_len; 4151da177e4SLinus Torvalds 4161da177e4SLinus Torvalds for_nexthops(fi) { 4174e902c57SThomas Graf int attrlen; 4181da177e4SLinus Torvalds 4194e902c57SThomas Graf if (!rtnh_ok(rtnh, remaining)) 4201da177e4SLinus Torvalds return -EINVAL; 4214e902c57SThomas Graf 4224e902c57SThomas Graf if (rtnh->rtnh_ifindex && rtnh->rtnh_ifindex != nh->nh_oif) 4231da177e4SLinus Torvalds return 1; 4244e902c57SThomas Graf 4254e902c57SThomas Graf attrlen = rtnh_attrlen(rtnh); 4264e902c57SThomas Graf if (attrlen < 0) { 4274e902c57SThomas Graf struct nlattr *nla, *attrs = rtnh_attrs(rtnh); 4284e902c57SThomas Graf 4294e902c57SThomas Graf nla = nla_find(attrs, attrlen, RTA_GATEWAY); 4304e902c57SThomas Graf if (nla && nla_get_u32(nla) != nh->nh_gw) 4311da177e4SLinus Torvalds return 1; 4321da177e4SLinus Torvalds #ifdef CONFIG_NET_CLS_ROUTE 4334e902c57SThomas Graf nla = nla_find(attrs, attrlen, RTA_FLOW); 4344e902c57SThomas Graf if (nla && nla_get_u32(nla) != nh->nh_tclassid) 4351da177e4SLinus Torvalds return 1; 4361da177e4SLinus Torvalds #endif 4371da177e4SLinus Torvalds } 4384e902c57SThomas Graf 4394e902c57SThomas Graf rtnh = rtnh_next(rtnh, &remaining); 4401da177e4SLinus Torvalds } endfor_nexthops(fi); 4411da177e4SLinus Torvalds #endif 4421da177e4SLinus Torvalds return 0; 4431da177e4SLinus Torvalds } 4441da177e4SLinus Torvalds 4451da177e4SLinus Torvalds 4461da177e4SLinus Torvalds /* 4471da177e4SLinus Torvalds Picture 4481da177e4SLinus Torvalds ------- 4491da177e4SLinus Torvalds 4501da177e4SLinus Torvalds Semantics of nexthop is very messy by historical reasons. 4511da177e4SLinus Torvalds We have to take into account, that: 4521da177e4SLinus Torvalds a) gateway can be actually local interface address, 4531da177e4SLinus Torvalds so that gatewayed route is direct. 4541da177e4SLinus Torvalds b) gateway must be on-link address, possibly 4551da177e4SLinus Torvalds described not by an ifaddr, but also by a direct route. 4561da177e4SLinus Torvalds c) If both gateway and interface are specified, they should not 4571da177e4SLinus Torvalds contradict. 4581da177e4SLinus Torvalds d) If we use tunnel routes, gateway could be not on-link. 4591da177e4SLinus Torvalds 4601da177e4SLinus Torvalds Attempt to reconcile all of these (alas, self-contradictory) conditions 4611da177e4SLinus Torvalds results in pretty ugly and hairy code with obscure logic. 4621da177e4SLinus Torvalds 4631da177e4SLinus Torvalds I chose to generalized it instead, so that the size 4641da177e4SLinus Torvalds of code does not increase practically, but it becomes 4651da177e4SLinus Torvalds much more general. 4661da177e4SLinus Torvalds Every prefix is assigned a "scope" value: "host" is local address, 4671da177e4SLinus Torvalds "link" is direct route, 4681da177e4SLinus Torvalds [ ... "site" ... "interior" ... ] 4691da177e4SLinus Torvalds and "universe" is true gateway route with global meaning. 4701da177e4SLinus Torvalds 4711da177e4SLinus Torvalds Every prefix refers to a set of "nexthop"s (gw, oif), 4721da177e4SLinus Torvalds where gw must have narrower scope. This recursion stops 4731da177e4SLinus Torvalds when gw has LOCAL scope or if "nexthop" is declared ONLINK, 4741da177e4SLinus Torvalds which means that gw is forced to be on link. 4751da177e4SLinus Torvalds 4761da177e4SLinus Torvalds Code is still hairy, but now it is apparently logically 4771da177e4SLinus Torvalds consistent and very flexible. F.e. as by-product it allows 4781da177e4SLinus Torvalds to co-exists in peace independent exterior and interior 4791da177e4SLinus Torvalds routing processes. 4801da177e4SLinus Torvalds 4811da177e4SLinus Torvalds Normally it looks as following. 4821da177e4SLinus Torvalds 4831da177e4SLinus Torvalds {universe prefix} -> (gw, oif) [scope link] 4841da177e4SLinus Torvalds | 4851da177e4SLinus Torvalds |-> {link prefix} -> (gw, oif) [scope local] 4861da177e4SLinus Torvalds | 4871da177e4SLinus Torvalds |-> {local prefix} (terminal node) 4881da177e4SLinus Torvalds */ 4891da177e4SLinus Torvalds 4904e902c57SThomas Graf static int fib_check_nh(struct fib_config *cfg, struct fib_info *fi, 4914e902c57SThomas Graf struct fib_nh *nh) 4921da177e4SLinus Torvalds { 4931da177e4SLinus Torvalds int err; 4941da177e4SLinus Torvalds 4951da177e4SLinus Torvalds if (nh->nh_gw) { 4961da177e4SLinus Torvalds struct fib_result res; 4971da177e4SLinus Torvalds 4981da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_PERVASIVE 4991da177e4SLinus Torvalds if (nh->nh_flags&RTNH_F_PERVASIVE) 5001da177e4SLinus Torvalds return 0; 5011da177e4SLinus Torvalds #endif 5021da177e4SLinus Torvalds if (nh->nh_flags&RTNH_F_ONLINK) { 5031da177e4SLinus Torvalds struct net_device *dev; 5041da177e4SLinus Torvalds 5054e902c57SThomas Graf if (cfg->fc_scope >= RT_SCOPE_LINK) 5061da177e4SLinus Torvalds return -EINVAL; 5071da177e4SLinus Torvalds if (inet_addr_type(nh->nh_gw) != RTN_UNICAST) 5081da177e4SLinus Torvalds return -EINVAL; 5091da177e4SLinus Torvalds if ((dev = __dev_get_by_index(nh->nh_oif)) == NULL) 5101da177e4SLinus Torvalds return -ENODEV; 5111da177e4SLinus Torvalds if (!(dev->flags&IFF_UP)) 5121da177e4SLinus Torvalds return -ENETDOWN; 5131da177e4SLinus Torvalds nh->nh_dev = dev; 5141da177e4SLinus Torvalds dev_hold(dev); 5151da177e4SLinus Torvalds nh->nh_scope = RT_SCOPE_LINK; 5161da177e4SLinus Torvalds return 0; 5171da177e4SLinus Torvalds } 5181da177e4SLinus Torvalds { 5194e902c57SThomas Graf struct flowi fl = { 5204e902c57SThomas Graf .nl_u = { 5214e902c57SThomas Graf .ip4_u = { 5224e902c57SThomas Graf .daddr = nh->nh_gw, 5234e902c57SThomas Graf .scope = cfg->fc_scope + 1, 5244e902c57SThomas Graf }, 5254e902c57SThomas Graf }, 5264e902c57SThomas Graf .oif = nh->nh_oif, 5274e902c57SThomas Graf }; 5281da177e4SLinus Torvalds 5291da177e4SLinus Torvalds /* It is not necessary, but requires a bit of thinking */ 5301da177e4SLinus Torvalds if (fl.fl4_scope < RT_SCOPE_LINK) 5311da177e4SLinus Torvalds fl.fl4_scope = RT_SCOPE_LINK; 5321da177e4SLinus Torvalds if ((err = fib_lookup(&fl, &res)) != 0) 5331da177e4SLinus Torvalds return err; 5341da177e4SLinus Torvalds } 5351da177e4SLinus Torvalds err = -EINVAL; 5361da177e4SLinus Torvalds if (res.type != RTN_UNICAST && res.type != RTN_LOCAL) 5371da177e4SLinus Torvalds goto out; 5381da177e4SLinus Torvalds nh->nh_scope = res.scope; 5391da177e4SLinus Torvalds nh->nh_oif = FIB_RES_OIF(res); 5401da177e4SLinus Torvalds if ((nh->nh_dev = FIB_RES_DEV(res)) == NULL) 5411da177e4SLinus Torvalds goto out; 5421da177e4SLinus Torvalds dev_hold(nh->nh_dev); 5431da177e4SLinus Torvalds err = -ENETDOWN; 5441da177e4SLinus Torvalds if (!(nh->nh_dev->flags & IFF_UP)) 5451da177e4SLinus Torvalds goto out; 5461da177e4SLinus Torvalds err = 0; 5471da177e4SLinus Torvalds out: 5481da177e4SLinus Torvalds fib_res_put(&res); 5491da177e4SLinus Torvalds return err; 5501da177e4SLinus Torvalds } else { 5511da177e4SLinus Torvalds struct in_device *in_dev; 5521da177e4SLinus Torvalds 5531da177e4SLinus Torvalds if (nh->nh_flags&(RTNH_F_PERVASIVE|RTNH_F_ONLINK)) 5541da177e4SLinus Torvalds return -EINVAL; 5551da177e4SLinus Torvalds 5561da177e4SLinus Torvalds in_dev = inetdev_by_index(nh->nh_oif); 5571da177e4SLinus Torvalds if (in_dev == NULL) 5581da177e4SLinus Torvalds return -ENODEV; 5591da177e4SLinus Torvalds if (!(in_dev->dev->flags&IFF_UP)) { 5601da177e4SLinus Torvalds in_dev_put(in_dev); 5611da177e4SLinus Torvalds return -ENETDOWN; 5621da177e4SLinus Torvalds } 5631da177e4SLinus Torvalds nh->nh_dev = in_dev->dev; 5641da177e4SLinus Torvalds dev_hold(nh->nh_dev); 5651da177e4SLinus Torvalds nh->nh_scope = RT_SCOPE_HOST; 5661da177e4SLinus Torvalds in_dev_put(in_dev); 5671da177e4SLinus Torvalds } 5681da177e4SLinus Torvalds return 0; 5691da177e4SLinus Torvalds } 5701da177e4SLinus Torvalds 5711da177e4SLinus Torvalds static inline unsigned int fib_laddr_hashfn(u32 val) 5721da177e4SLinus Torvalds { 5731da177e4SLinus Torvalds unsigned int mask = (fib_hash_size - 1); 5741da177e4SLinus Torvalds 5751da177e4SLinus Torvalds return (val ^ (val >> 7) ^ (val >> 14)) & mask; 5761da177e4SLinus Torvalds } 5771da177e4SLinus Torvalds 5781da177e4SLinus Torvalds static struct hlist_head *fib_hash_alloc(int bytes) 5791da177e4SLinus Torvalds { 5801da177e4SLinus Torvalds if (bytes <= PAGE_SIZE) 5811da177e4SLinus Torvalds return kmalloc(bytes, GFP_KERNEL); 5821da177e4SLinus Torvalds else 5831da177e4SLinus Torvalds return (struct hlist_head *) 5841da177e4SLinus Torvalds __get_free_pages(GFP_KERNEL, get_order(bytes)); 5851da177e4SLinus Torvalds } 5861da177e4SLinus Torvalds 5871da177e4SLinus Torvalds static void fib_hash_free(struct hlist_head *hash, int bytes) 5881da177e4SLinus Torvalds { 5891da177e4SLinus Torvalds if (!hash) 5901da177e4SLinus Torvalds return; 5911da177e4SLinus Torvalds 5921da177e4SLinus Torvalds if (bytes <= PAGE_SIZE) 5931da177e4SLinus Torvalds kfree(hash); 5941da177e4SLinus Torvalds else 5951da177e4SLinus Torvalds free_pages((unsigned long) hash, get_order(bytes)); 5961da177e4SLinus Torvalds } 5971da177e4SLinus Torvalds 5981da177e4SLinus Torvalds static void fib_hash_move(struct hlist_head *new_info_hash, 5991da177e4SLinus Torvalds struct hlist_head *new_laddrhash, 6001da177e4SLinus Torvalds unsigned int new_size) 6011da177e4SLinus Torvalds { 602b7656e7fSDavid S. Miller struct hlist_head *old_info_hash, *old_laddrhash; 6031da177e4SLinus Torvalds unsigned int old_size = fib_hash_size; 604b7656e7fSDavid S. Miller unsigned int i, bytes; 6051da177e4SLinus Torvalds 606832b4c5eSStephen Hemminger spin_lock_bh(&fib_info_lock); 607b7656e7fSDavid S. Miller old_info_hash = fib_info_hash; 608b7656e7fSDavid S. Miller old_laddrhash = fib_info_laddrhash; 6091da177e4SLinus Torvalds fib_hash_size = new_size; 6101da177e4SLinus Torvalds 6111da177e4SLinus Torvalds for (i = 0; i < old_size; i++) { 6121da177e4SLinus Torvalds struct hlist_head *head = &fib_info_hash[i]; 6131da177e4SLinus Torvalds struct hlist_node *node, *n; 6141da177e4SLinus Torvalds struct fib_info *fi; 6151da177e4SLinus Torvalds 6161da177e4SLinus Torvalds hlist_for_each_entry_safe(fi, node, n, head, fib_hash) { 6171da177e4SLinus Torvalds struct hlist_head *dest; 6181da177e4SLinus Torvalds unsigned int new_hash; 6191da177e4SLinus Torvalds 6201da177e4SLinus Torvalds hlist_del(&fi->fib_hash); 6211da177e4SLinus Torvalds 6221da177e4SLinus Torvalds new_hash = fib_info_hashfn(fi); 6231da177e4SLinus Torvalds dest = &new_info_hash[new_hash]; 6241da177e4SLinus Torvalds hlist_add_head(&fi->fib_hash, dest); 6251da177e4SLinus Torvalds } 6261da177e4SLinus Torvalds } 6271da177e4SLinus Torvalds fib_info_hash = new_info_hash; 6281da177e4SLinus Torvalds 6291da177e4SLinus Torvalds for (i = 0; i < old_size; i++) { 6301da177e4SLinus Torvalds struct hlist_head *lhead = &fib_info_laddrhash[i]; 6311da177e4SLinus Torvalds struct hlist_node *node, *n; 6321da177e4SLinus Torvalds struct fib_info *fi; 6331da177e4SLinus Torvalds 6341da177e4SLinus Torvalds hlist_for_each_entry_safe(fi, node, n, lhead, fib_lhash) { 6351da177e4SLinus Torvalds struct hlist_head *ldest; 6361da177e4SLinus Torvalds unsigned int new_hash; 6371da177e4SLinus Torvalds 6381da177e4SLinus Torvalds hlist_del(&fi->fib_lhash); 6391da177e4SLinus Torvalds 6401da177e4SLinus Torvalds new_hash = fib_laddr_hashfn(fi->fib_prefsrc); 6411da177e4SLinus Torvalds ldest = &new_laddrhash[new_hash]; 6421da177e4SLinus Torvalds hlist_add_head(&fi->fib_lhash, ldest); 6431da177e4SLinus Torvalds } 6441da177e4SLinus Torvalds } 6451da177e4SLinus Torvalds fib_info_laddrhash = new_laddrhash; 6461da177e4SLinus Torvalds 647832b4c5eSStephen Hemminger spin_unlock_bh(&fib_info_lock); 648b7656e7fSDavid S. Miller 649b7656e7fSDavid S. Miller bytes = old_size * sizeof(struct hlist_head *); 650b7656e7fSDavid S. Miller fib_hash_free(old_info_hash, bytes); 651b7656e7fSDavid S. Miller fib_hash_free(old_laddrhash, bytes); 6521da177e4SLinus Torvalds } 6531da177e4SLinus Torvalds 6544e902c57SThomas Graf struct fib_info *fib_create_info(struct fib_config *cfg) 6551da177e4SLinus Torvalds { 6561da177e4SLinus Torvalds int err; 6571da177e4SLinus Torvalds struct fib_info *fi = NULL; 6581da177e4SLinus Torvalds struct fib_info *ofi; 6591da177e4SLinus Torvalds int nhs = 1; 6601da177e4SLinus Torvalds 6611da177e4SLinus Torvalds /* Fast check to catch the most weird cases */ 6624e902c57SThomas Graf if (fib_props[cfg->fc_type].scope > cfg->fc_scope) 6631da177e4SLinus Torvalds goto err_inval; 6641da177e4SLinus Torvalds 6651da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH 6664e902c57SThomas Graf if (cfg->fc_mp) { 6674e902c57SThomas Graf nhs = fib_count_nexthops(cfg->fc_mp, cfg->fc_mp_len); 6681da177e4SLinus Torvalds if (nhs == 0) 6691da177e4SLinus Torvalds goto err_inval; 6701da177e4SLinus Torvalds } 6711da177e4SLinus Torvalds #endif 6721da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED 6734e902c57SThomas Graf if (cfg->fc_mp_alg) { 6744e902c57SThomas Graf if (cfg->fc_mp_alg < IP_MP_ALG_NONE || 6754e902c57SThomas Graf cfg->fc_mp_alg > IP_MP_ALG_MAX) 6761da177e4SLinus Torvalds goto err_inval; 6771da177e4SLinus Torvalds } 6781da177e4SLinus Torvalds #endif 6791da177e4SLinus Torvalds 6801da177e4SLinus Torvalds err = -ENOBUFS; 6811da177e4SLinus Torvalds if (fib_info_cnt >= fib_hash_size) { 6821da177e4SLinus Torvalds unsigned int new_size = fib_hash_size << 1; 6831da177e4SLinus Torvalds struct hlist_head *new_info_hash; 6841da177e4SLinus Torvalds struct hlist_head *new_laddrhash; 6851da177e4SLinus Torvalds unsigned int bytes; 6861da177e4SLinus Torvalds 6871da177e4SLinus Torvalds if (!new_size) 6881da177e4SLinus Torvalds new_size = 1; 6891da177e4SLinus Torvalds bytes = new_size * sizeof(struct hlist_head *); 6901da177e4SLinus Torvalds new_info_hash = fib_hash_alloc(bytes); 6911da177e4SLinus Torvalds new_laddrhash = fib_hash_alloc(bytes); 6921da177e4SLinus Torvalds if (!new_info_hash || !new_laddrhash) { 6931da177e4SLinus Torvalds fib_hash_free(new_info_hash, bytes); 6941da177e4SLinus Torvalds fib_hash_free(new_laddrhash, bytes); 6951da177e4SLinus Torvalds } else { 6961da177e4SLinus Torvalds memset(new_info_hash, 0, bytes); 6971da177e4SLinus Torvalds memset(new_laddrhash, 0, bytes); 6981da177e4SLinus Torvalds 6991da177e4SLinus Torvalds fib_hash_move(new_info_hash, new_laddrhash, new_size); 7001da177e4SLinus Torvalds } 7011da177e4SLinus Torvalds 7021da177e4SLinus Torvalds if (!fib_hash_size) 7031da177e4SLinus Torvalds goto failure; 7041da177e4SLinus Torvalds } 7051da177e4SLinus Torvalds 7060da974f4SPanagiotis Issaris fi = kzalloc(sizeof(*fi)+nhs*sizeof(struct fib_nh), GFP_KERNEL); 7071da177e4SLinus Torvalds if (fi == NULL) 7081da177e4SLinus Torvalds goto failure; 7091da177e4SLinus Torvalds fib_info_cnt++; 7101da177e4SLinus Torvalds 7114e902c57SThomas Graf fi->fib_protocol = cfg->fc_protocol; 7124e902c57SThomas Graf fi->fib_flags = cfg->fc_flags; 7134e902c57SThomas Graf fi->fib_priority = cfg->fc_priority; 7144e902c57SThomas Graf fi->fib_prefsrc = cfg->fc_prefsrc; 7151da177e4SLinus Torvalds 7161da177e4SLinus Torvalds fi->fib_nhs = nhs; 7171da177e4SLinus Torvalds change_nexthops(fi) { 7181da177e4SLinus Torvalds nh->nh_parent = fi; 7191da177e4SLinus Torvalds } endfor_nexthops(fi) 7201da177e4SLinus Torvalds 7214e902c57SThomas Graf if (cfg->fc_mx) { 7224e902c57SThomas Graf struct nlattr *nla; 7234e902c57SThomas Graf int remaining; 7241da177e4SLinus Torvalds 7254e902c57SThomas Graf nla_for_each_attr(nla, cfg->fc_mx, cfg->fc_mx_len, remaining) { 7264e902c57SThomas Graf int type = nla->nla_type; 7274e902c57SThomas Graf 7284e902c57SThomas Graf if (type) { 7294e902c57SThomas Graf if (type > RTAX_MAX) 7301da177e4SLinus Torvalds goto err_inval; 7314e902c57SThomas Graf fi->fib_metrics[type - 1] = nla_get_u32(nla); 7321da177e4SLinus Torvalds } 7331da177e4SLinus Torvalds } 7344e902c57SThomas Graf } 7351da177e4SLinus Torvalds 7364e902c57SThomas Graf if (cfg->fc_mp) { 7371da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH 7384e902c57SThomas Graf err = fib_get_nhs(fi, cfg->fc_mp, cfg->fc_mp_len, cfg); 7394e902c57SThomas Graf if (err != 0) 7401da177e4SLinus Torvalds goto failure; 7414e902c57SThomas Graf if (cfg->fc_oif && fi->fib_nh->nh_oif != cfg->fc_oif) 7421da177e4SLinus Torvalds goto err_inval; 7434e902c57SThomas Graf if (cfg->fc_gw && fi->fib_nh->nh_gw != cfg->fc_gw) 7441da177e4SLinus Torvalds goto err_inval; 7451da177e4SLinus Torvalds #ifdef CONFIG_NET_CLS_ROUTE 7464e902c57SThomas Graf if (cfg->fc_flow && fi->fib_nh->nh_tclassid != cfg->fc_flow) 7471da177e4SLinus Torvalds goto err_inval; 7481da177e4SLinus Torvalds #endif 7491da177e4SLinus Torvalds #else 7501da177e4SLinus Torvalds goto err_inval; 7511da177e4SLinus Torvalds #endif 7521da177e4SLinus Torvalds } else { 7531da177e4SLinus Torvalds struct fib_nh *nh = fi->fib_nh; 7544e902c57SThomas Graf 7554e902c57SThomas Graf nh->nh_oif = cfg->fc_oif; 7564e902c57SThomas Graf nh->nh_gw = cfg->fc_gw; 7574e902c57SThomas Graf nh->nh_flags = cfg->fc_flags; 7581da177e4SLinus Torvalds #ifdef CONFIG_NET_CLS_ROUTE 7594e902c57SThomas Graf nh->nh_tclassid = cfg->fc_flow; 7601da177e4SLinus Torvalds #endif 7611da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH 7621da177e4SLinus Torvalds nh->nh_weight = 1; 7631da177e4SLinus Torvalds #endif 7641da177e4SLinus Torvalds } 7651da177e4SLinus Torvalds 7661da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED 7674e902c57SThomas Graf fi->fib_mp_alg = cfg->fc_mp_alg; 7681da177e4SLinus Torvalds #endif 7691da177e4SLinus Torvalds 7704e902c57SThomas Graf if (fib_props[cfg->fc_type].error) { 7714e902c57SThomas Graf if (cfg->fc_gw || cfg->fc_oif || cfg->fc_mp) 7721da177e4SLinus Torvalds goto err_inval; 7731da177e4SLinus Torvalds goto link_it; 7741da177e4SLinus Torvalds } 7751da177e4SLinus Torvalds 7764e902c57SThomas Graf if (cfg->fc_scope > RT_SCOPE_HOST) 7771da177e4SLinus Torvalds goto err_inval; 7781da177e4SLinus Torvalds 7794e902c57SThomas Graf if (cfg->fc_scope == RT_SCOPE_HOST) { 7801da177e4SLinus Torvalds struct fib_nh *nh = fi->fib_nh; 7811da177e4SLinus Torvalds 7821da177e4SLinus Torvalds /* Local address is added. */ 7831da177e4SLinus Torvalds if (nhs != 1 || nh->nh_gw) 7841da177e4SLinus Torvalds goto err_inval; 7851da177e4SLinus Torvalds nh->nh_scope = RT_SCOPE_NOWHERE; 7861da177e4SLinus Torvalds nh->nh_dev = dev_get_by_index(fi->fib_nh->nh_oif); 7871da177e4SLinus Torvalds err = -ENODEV; 7881da177e4SLinus Torvalds if (nh->nh_dev == NULL) 7891da177e4SLinus Torvalds goto failure; 7901da177e4SLinus Torvalds } else { 7911da177e4SLinus Torvalds change_nexthops(fi) { 7924e902c57SThomas Graf if ((err = fib_check_nh(cfg, fi, nh)) != 0) 7931da177e4SLinus Torvalds goto failure; 7941da177e4SLinus Torvalds } endfor_nexthops(fi) 7951da177e4SLinus Torvalds } 7961da177e4SLinus Torvalds 7971da177e4SLinus Torvalds if (fi->fib_prefsrc) { 7984e902c57SThomas Graf if (cfg->fc_type != RTN_LOCAL || !cfg->fc_dst || 7994e902c57SThomas Graf fi->fib_prefsrc != cfg->fc_dst) 8001da177e4SLinus Torvalds if (inet_addr_type(fi->fib_prefsrc) != RTN_LOCAL) 8011da177e4SLinus Torvalds goto err_inval; 8021da177e4SLinus Torvalds } 8031da177e4SLinus Torvalds 8041da177e4SLinus Torvalds link_it: 8051da177e4SLinus Torvalds if ((ofi = fib_find_info(fi)) != NULL) { 8061da177e4SLinus Torvalds fi->fib_dead = 1; 8071da177e4SLinus Torvalds free_fib_info(fi); 8081da177e4SLinus Torvalds ofi->fib_treeref++; 8091da177e4SLinus Torvalds return ofi; 8101da177e4SLinus Torvalds } 8111da177e4SLinus Torvalds 8121da177e4SLinus Torvalds fi->fib_treeref++; 8131da177e4SLinus Torvalds atomic_inc(&fi->fib_clntref); 814832b4c5eSStephen Hemminger spin_lock_bh(&fib_info_lock); 8151da177e4SLinus Torvalds hlist_add_head(&fi->fib_hash, 8161da177e4SLinus Torvalds &fib_info_hash[fib_info_hashfn(fi)]); 8171da177e4SLinus Torvalds if (fi->fib_prefsrc) { 8181da177e4SLinus Torvalds struct hlist_head *head; 8191da177e4SLinus Torvalds 8201da177e4SLinus Torvalds head = &fib_info_laddrhash[fib_laddr_hashfn(fi->fib_prefsrc)]; 8211da177e4SLinus Torvalds hlist_add_head(&fi->fib_lhash, head); 8221da177e4SLinus Torvalds } 8231da177e4SLinus Torvalds change_nexthops(fi) { 8241da177e4SLinus Torvalds struct hlist_head *head; 8251da177e4SLinus Torvalds unsigned int hash; 8261da177e4SLinus Torvalds 8271da177e4SLinus Torvalds if (!nh->nh_dev) 8281da177e4SLinus Torvalds continue; 8291da177e4SLinus Torvalds hash = fib_devindex_hashfn(nh->nh_dev->ifindex); 8301da177e4SLinus Torvalds head = &fib_info_devhash[hash]; 8311da177e4SLinus Torvalds hlist_add_head(&nh->nh_hash, head); 8321da177e4SLinus Torvalds } endfor_nexthops(fi) 833832b4c5eSStephen Hemminger spin_unlock_bh(&fib_info_lock); 8341da177e4SLinus Torvalds return fi; 8351da177e4SLinus Torvalds 8361da177e4SLinus Torvalds err_inval: 8371da177e4SLinus Torvalds err = -EINVAL; 8381da177e4SLinus Torvalds 8391da177e4SLinus Torvalds failure: 8401da177e4SLinus Torvalds if (fi) { 8411da177e4SLinus Torvalds fi->fib_dead = 1; 8421da177e4SLinus Torvalds free_fib_info(fi); 8431da177e4SLinus Torvalds } 8444e902c57SThomas Graf 8454e902c57SThomas Graf return ERR_PTR(err); 8461da177e4SLinus Torvalds } 8471da177e4SLinus Torvalds 848e5b43760SRobert Olsson /* Note! fib_semantic_match intentionally uses RCU list functions. */ 8491da177e4SLinus Torvalds int fib_semantic_match(struct list_head *head, const struct flowi *flp, 8501da177e4SLinus Torvalds struct fib_result *res, __u32 zone, __u32 mask, 8511da177e4SLinus Torvalds int prefixlen) 8521da177e4SLinus Torvalds { 8531da177e4SLinus Torvalds struct fib_alias *fa; 8541da177e4SLinus Torvalds int nh_sel = 0; 8551da177e4SLinus Torvalds 856e5b43760SRobert Olsson list_for_each_entry_rcu(fa, head, fa_list) { 8571da177e4SLinus Torvalds int err; 8581da177e4SLinus Torvalds 8591da177e4SLinus Torvalds if (fa->fa_tos && 8601da177e4SLinus Torvalds fa->fa_tos != flp->fl4_tos) 8611da177e4SLinus Torvalds continue; 8621da177e4SLinus Torvalds 8631da177e4SLinus Torvalds if (fa->fa_scope < flp->fl4_scope) 8641da177e4SLinus Torvalds continue; 8651da177e4SLinus Torvalds 8661da177e4SLinus Torvalds fa->fa_state |= FA_S_ACCESSED; 8671da177e4SLinus Torvalds 8681da177e4SLinus Torvalds err = fib_props[fa->fa_type].error; 8691da177e4SLinus Torvalds if (err == 0) { 8701da177e4SLinus Torvalds struct fib_info *fi = fa->fa_info; 8711da177e4SLinus Torvalds 8721da177e4SLinus Torvalds if (fi->fib_flags & RTNH_F_DEAD) 8731da177e4SLinus Torvalds continue; 8741da177e4SLinus Torvalds 8751da177e4SLinus Torvalds switch (fa->fa_type) { 8761da177e4SLinus Torvalds case RTN_UNICAST: 8771da177e4SLinus Torvalds case RTN_LOCAL: 8781da177e4SLinus Torvalds case RTN_BROADCAST: 8791da177e4SLinus Torvalds case RTN_ANYCAST: 8801da177e4SLinus Torvalds case RTN_MULTICAST: 8811da177e4SLinus Torvalds for_nexthops(fi) { 8821da177e4SLinus Torvalds if (nh->nh_flags&RTNH_F_DEAD) 8831da177e4SLinus Torvalds continue; 8841da177e4SLinus Torvalds if (!flp->oif || flp->oif == nh->nh_oif) 8851da177e4SLinus Torvalds break; 8861da177e4SLinus Torvalds } 8871da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH 8881da177e4SLinus Torvalds if (nhsel < fi->fib_nhs) { 8891da177e4SLinus Torvalds nh_sel = nhsel; 8901da177e4SLinus Torvalds goto out_fill_res; 8911da177e4SLinus Torvalds } 8921da177e4SLinus Torvalds #else 8931da177e4SLinus Torvalds if (nhsel < 1) { 8941da177e4SLinus Torvalds goto out_fill_res; 8951da177e4SLinus Torvalds } 8961da177e4SLinus Torvalds #endif 8971da177e4SLinus Torvalds endfor_nexthops(fi); 8981da177e4SLinus Torvalds continue; 8991da177e4SLinus Torvalds 9001da177e4SLinus Torvalds default: 9011da177e4SLinus Torvalds printk(KERN_DEBUG "impossible 102\n"); 9021da177e4SLinus Torvalds return -EINVAL; 9031da177e4SLinus Torvalds }; 9041da177e4SLinus Torvalds } 9051da177e4SLinus Torvalds return err; 9061da177e4SLinus Torvalds } 9071da177e4SLinus Torvalds return 1; 9081da177e4SLinus Torvalds 9091da177e4SLinus Torvalds out_fill_res: 9101da177e4SLinus Torvalds res->prefixlen = prefixlen; 9111da177e4SLinus Torvalds res->nh_sel = nh_sel; 9121da177e4SLinus Torvalds res->type = fa->fa_type; 9131da177e4SLinus Torvalds res->scope = fa->fa_scope; 9141da177e4SLinus Torvalds res->fi = fa->fa_info; 9151da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED 9161da177e4SLinus Torvalds res->netmask = mask; 9171da177e4SLinus Torvalds res->network = zone & 9181da177e4SLinus Torvalds (0xFFFFFFFF >> (32 - prefixlen)); 9191da177e4SLinus Torvalds #endif 9201da177e4SLinus Torvalds atomic_inc(&res->fi->fib_clntref); 9211da177e4SLinus Torvalds return 0; 9221da177e4SLinus Torvalds } 9231da177e4SLinus Torvalds 9241da177e4SLinus Torvalds /* Find appropriate source address to this destination */ 9251da177e4SLinus Torvalds 926*b83738aeSAl Viro __be32 __fib_res_prefsrc(struct fib_result *res) 9271da177e4SLinus Torvalds { 9281da177e4SLinus Torvalds return inet_select_addr(FIB_RES_DEV(*res), FIB_RES_GW(*res), res->scope); 9291da177e4SLinus Torvalds } 9301da177e4SLinus Torvalds 931be403ea1SThomas Graf int fib_dump_info(struct sk_buff *skb, u32 pid, u32 seq, int event, 932be403ea1SThomas Graf u32 tb_id, u8 type, u8 scope, u32 dst, int dst_len, u8 tos, 933b6544c0bSJamal Hadi Salim struct fib_info *fi, unsigned int flags) 9341da177e4SLinus Torvalds { 9351da177e4SLinus Torvalds struct nlmsghdr *nlh; 936be403ea1SThomas Graf struct rtmsg *rtm; 9371da177e4SLinus Torvalds 938be403ea1SThomas Graf nlh = nlmsg_put(skb, pid, seq, event, sizeof(*rtm), flags); 939be403ea1SThomas Graf if (nlh == NULL) 940be403ea1SThomas Graf return -ENOBUFS; 941be403ea1SThomas Graf 942be403ea1SThomas Graf rtm = nlmsg_data(nlh); 9431da177e4SLinus Torvalds rtm->rtm_family = AF_INET; 9441da177e4SLinus Torvalds rtm->rtm_dst_len = dst_len; 9451da177e4SLinus Torvalds rtm->rtm_src_len = 0; 9461da177e4SLinus Torvalds rtm->rtm_tos = tos; 9471da177e4SLinus Torvalds rtm->rtm_table = tb_id; 948be403ea1SThomas Graf NLA_PUT_U32(skb, RTA_TABLE, tb_id); 9491da177e4SLinus Torvalds rtm->rtm_type = type; 9501da177e4SLinus Torvalds rtm->rtm_flags = fi->fib_flags; 9511da177e4SLinus Torvalds rtm->rtm_scope = scope; 9521da177e4SLinus Torvalds rtm->rtm_protocol = fi->fib_protocol; 953be403ea1SThomas Graf 954be403ea1SThomas Graf if (rtm->rtm_dst_len) 955be403ea1SThomas Graf NLA_PUT_U32(skb, RTA_DST, dst); 956be403ea1SThomas Graf 9571da177e4SLinus Torvalds if (fi->fib_priority) 958be403ea1SThomas Graf NLA_PUT_U32(skb, RTA_PRIORITY, fi->fib_priority); 959be403ea1SThomas Graf 9601da177e4SLinus Torvalds if (rtnetlink_put_metrics(skb, fi->fib_metrics) < 0) 961be403ea1SThomas Graf goto nla_put_failure; 962be403ea1SThomas Graf 9631da177e4SLinus Torvalds if (fi->fib_prefsrc) 964be403ea1SThomas Graf NLA_PUT_U32(skb, RTA_PREFSRC, fi->fib_prefsrc); 965be403ea1SThomas Graf 9661da177e4SLinus Torvalds if (fi->fib_nhs == 1) { 9671da177e4SLinus Torvalds if (fi->fib_nh->nh_gw) 968be403ea1SThomas Graf NLA_PUT_U32(skb, RTA_GATEWAY, fi->fib_nh->nh_gw); 969be403ea1SThomas Graf 9701da177e4SLinus Torvalds if (fi->fib_nh->nh_oif) 971be403ea1SThomas Graf NLA_PUT_U32(skb, RTA_OIF, fi->fib_nh->nh_oif); 9728265abc0SPatrick McHardy #ifdef CONFIG_NET_CLS_ROUTE 9738265abc0SPatrick McHardy if (fi->fib_nh[0].nh_tclassid) 974be403ea1SThomas Graf NLA_PUT_U32(skb, RTA_FLOW, fi->fib_nh[0].nh_tclassid); 9758265abc0SPatrick McHardy #endif 9761da177e4SLinus Torvalds } 9771da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH 9781da177e4SLinus Torvalds if (fi->fib_nhs > 1) { 979be403ea1SThomas Graf struct rtnexthop *rtnh; 980be403ea1SThomas Graf struct nlattr *mp; 981be403ea1SThomas Graf 982be403ea1SThomas Graf mp = nla_nest_start(skb, RTA_MULTIPATH); 983be403ea1SThomas Graf if (mp == NULL) 984be403ea1SThomas Graf goto nla_put_failure; 9851da177e4SLinus Torvalds 9861da177e4SLinus Torvalds for_nexthops(fi) { 987be403ea1SThomas Graf rtnh = nla_reserve_nohdr(skb, sizeof(*rtnh)); 988be403ea1SThomas Graf if (rtnh == NULL) 989be403ea1SThomas Graf goto nla_put_failure; 990be403ea1SThomas Graf 991be403ea1SThomas Graf rtnh->rtnh_flags = nh->nh_flags & 0xFF; 992be403ea1SThomas Graf rtnh->rtnh_hops = nh->nh_weight - 1; 993be403ea1SThomas Graf rtnh->rtnh_ifindex = nh->nh_oif; 994be403ea1SThomas Graf 9951da177e4SLinus Torvalds if (nh->nh_gw) 996be403ea1SThomas Graf NLA_PUT_U32(skb, RTA_GATEWAY, nh->nh_gw); 9978265abc0SPatrick McHardy #ifdef CONFIG_NET_CLS_ROUTE 9988265abc0SPatrick McHardy if (nh->nh_tclassid) 999be403ea1SThomas Graf NLA_PUT_U32(skb, RTA_FLOW, nh->nh_tclassid); 10008265abc0SPatrick McHardy #endif 1001be403ea1SThomas Graf /* length of rtnetlink header + attributes */ 1002be403ea1SThomas Graf rtnh->rtnh_len = nlmsg_get_pos(skb) - (void *) rtnh; 10031da177e4SLinus Torvalds } endfor_nexthops(fi); 1004be403ea1SThomas Graf 1005be403ea1SThomas Graf nla_nest_end(skb, mp); 10061da177e4SLinus Torvalds } 10071da177e4SLinus Torvalds #endif 1008be403ea1SThomas Graf return nlmsg_end(skb, nlh); 10091da177e4SLinus Torvalds 1010be403ea1SThomas Graf nla_put_failure: 1011be403ea1SThomas Graf return nlmsg_cancel(skb, nlh); 10121da177e4SLinus Torvalds } 10131da177e4SLinus Torvalds 10141da177e4SLinus Torvalds /* 10151da177e4SLinus Torvalds Update FIB if: 10161da177e4SLinus Torvalds - local address disappeared -> we must delete all the entries 10171da177e4SLinus Torvalds referring to it. 10181da177e4SLinus Torvalds - device went down -> we must shutdown all nexthops going via it. 10191da177e4SLinus Torvalds */ 10201da177e4SLinus Torvalds 10211da177e4SLinus Torvalds int fib_sync_down(u32 local, struct net_device *dev, int force) 10221da177e4SLinus Torvalds { 10231da177e4SLinus Torvalds int ret = 0; 10241da177e4SLinus Torvalds int scope = RT_SCOPE_NOWHERE; 10251da177e4SLinus Torvalds 10261da177e4SLinus Torvalds if (force) 10271da177e4SLinus Torvalds scope = -1; 10281da177e4SLinus Torvalds 10291da177e4SLinus Torvalds if (local && fib_info_laddrhash) { 10301da177e4SLinus Torvalds unsigned int hash = fib_laddr_hashfn(local); 10311da177e4SLinus Torvalds struct hlist_head *head = &fib_info_laddrhash[hash]; 10321da177e4SLinus Torvalds struct hlist_node *node; 10331da177e4SLinus Torvalds struct fib_info *fi; 10341da177e4SLinus Torvalds 10351da177e4SLinus Torvalds hlist_for_each_entry(fi, node, head, fib_lhash) { 10361da177e4SLinus Torvalds if (fi->fib_prefsrc == local) { 10371da177e4SLinus Torvalds fi->fib_flags |= RTNH_F_DEAD; 10381da177e4SLinus Torvalds ret++; 10391da177e4SLinus Torvalds } 10401da177e4SLinus Torvalds } 10411da177e4SLinus Torvalds } 10421da177e4SLinus Torvalds 10431da177e4SLinus Torvalds if (dev) { 10441da177e4SLinus Torvalds struct fib_info *prev_fi = NULL; 10451da177e4SLinus Torvalds unsigned int hash = fib_devindex_hashfn(dev->ifindex); 10461da177e4SLinus Torvalds struct hlist_head *head = &fib_info_devhash[hash]; 10471da177e4SLinus Torvalds struct hlist_node *node; 10481da177e4SLinus Torvalds struct fib_nh *nh; 10491da177e4SLinus Torvalds 10501da177e4SLinus Torvalds hlist_for_each_entry(nh, node, head, nh_hash) { 10511da177e4SLinus Torvalds struct fib_info *fi = nh->nh_parent; 10521da177e4SLinus Torvalds int dead; 10531da177e4SLinus Torvalds 10541da177e4SLinus Torvalds BUG_ON(!fi->fib_nhs); 10551da177e4SLinus Torvalds if (nh->nh_dev != dev || fi == prev_fi) 10561da177e4SLinus Torvalds continue; 10571da177e4SLinus Torvalds prev_fi = fi; 10581da177e4SLinus Torvalds dead = 0; 10591da177e4SLinus Torvalds change_nexthops(fi) { 10601da177e4SLinus Torvalds if (nh->nh_flags&RTNH_F_DEAD) 10611da177e4SLinus Torvalds dead++; 10621da177e4SLinus Torvalds else if (nh->nh_dev == dev && 10631da177e4SLinus Torvalds nh->nh_scope != scope) { 10641da177e4SLinus Torvalds nh->nh_flags |= RTNH_F_DEAD; 10651da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH 10661da177e4SLinus Torvalds spin_lock_bh(&fib_multipath_lock); 10671da177e4SLinus Torvalds fi->fib_power -= nh->nh_power; 10681da177e4SLinus Torvalds nh->nh_power = 0; 10691da177e4SLinus Torvalds spin_unlock_bh(&fib_multipath_lock); 10701da177e4SLinus Torvalds #endif 10711da177e4SLinus Torvalds dead++; 10721da177e4SLinus Torvalds } 10731da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH 10741da177e4SLinus Torvalds if (force > 1 && nh->nh_dev == dev) { 10751da177e4SLinus Torvalds dead = fi->fib_nhs; 10761da177e4SLinus Torvalds break; 10771da177e4SLinus Torvalds } 10781da177e4SLinus Torvalds #endif 10791da177e4SLinus Torvalds } endfor_nexthops(fi) 10801da177e4SLinus Torvalds if (dead == fi->fib_nhs) { 10811da177e4SLinus Torvalds fi->fib_flags |= RTNH_F_DEAD; 10821da177e4SLinus Torvalds ret++; 10831da177e4SLinus Torvalds } 10841da177e4SLinus Torvalds } 10851da177e4SLinus Torvalds } 10861da177e4SLinus Torvalds 10871da177e4SLinus Torvalds return ret; 10881da177e4SLinus Torvalds } 10891da177e4SLinus Torvalds 10901da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH 10911da177e4SLinus Torvalds 10921da177e4SLinus Torvalds /* 10931da177e4SLinus Torvalds Dead device goes up. We wake up dead nexthops. 10941da177e4SLinus Torvalds It takes sense only on multipath routes. 10951da177e4SLinus Torvalds */ 10961da177e4SLinus Torvalds 10971da177e4SLinus Torvalds int fib_sync_up(struct net_device *dev) 10981da177e4SLinus Torvalds { 10991da177e4SLinus Torvalds struct fib_info *prev_fi; 11001da177e4SLinus Torvalds unsigned int hash; 11011da177e4SLinus Torvalds struct hlist_head *head; 11021da177e4SLinus Torvalds struct hlist_node *node; 11031da177e4SLinus Torvalds struct fib_nh *nh; 11041da177e4SLinus Torvalds int ret; 11051da177e4SLinus Torvalds 11061da177e4SLinus Torvalds if (!(dev->flags&IFF_UP)) 11071da177e4SLinus Torvalds return 0; 11081da177e4SLinus Torvalds 11091da177e4SLinus Torvalds prev_fi = NULL; 11101da177e4SLinus Torvalds hash = fib_devindex_hashfn(dev->ifindex); 11111da177e4SLinus Torvalds head = &fib_info_devhash[hash]; 11121da177e4SLinus Torvalds ret = 0; 11131da177e4SLinus Torvalds 11141da177e4SLinus Torvalds hlist_for_each_entry(nh, node, head, nh_hash) { 11151da177e4SLinus Torvalds struct fib_info *fi = nh->nh_parent; 11161da177e4SLinus Torvalds int alive; 11171da177e4SLinus Torvalds 11181da177e4SLinus Torvalds BUG_ON(!fi->fib_nhs); 11191da177e4SLinus Torvalds if (nh->nh_dev != dev || fi == prev_fi) 11201da177e4SLinus Torvalds continue; 11211da177e4SLinus Torvalds 11221da177e4SLinus Torvalds prev_fi = fi; 11231da177e4SLinus Torvalds alive = 0; 11241da177e4SLinus Torvalds change_nexthops(fi) { 11251da177e4SLinus Torvalds if (!(nh->nh_flags&RTNH_F_DEAD)) { 11261da177e4SLinus Torvalds alive++; 11271da177e4SLinus Torvalds continue; 11281da177e4SLinus Torvalds } 11291da177e4SLinus Torvalds if (nh->nh_dev == NULL || !(nh->nh_dev->flags&IFF_UP)) 11301da177e4SLinus Torvalds continue; 1131e5ed6399SHerbert Xu if (nh->nh_dev != dev || !__in_dev_get_rtnl(dev)) 11321da177e4SLinus Torvalds continue; 11331da177e4SLinus Torvalds alive++; 11341da177e4SLinus Torvalds spin_lock_bh(&fib_multipath_lock); 11351da177e4SLinus Torvalds nh->nh_power = 0; 11361da177e4SLinus Torvalds nh->nh_flags &= ~RTNH_F_DEAD; 11371da177e4SLinus Torvalds spin_unlock_bh(&fib_multipath_lock); 11381da177e4SLinus Torvalds } endfor_nexthops(fi) 11391da177e4SLinus Torvalds 11401da177e4SLinus Torvalds if (alive > 0) { 11411da177e4SLinus Torvalds fi->fib_flags &= ~RTNH_F_DEAD; 11421da177e4SLinus Torvalds ret++; 11431da177e4SLinus Torvalds } 11441da177e4SLinus Torvalds } 11451da177e4SLinus Torvalds 11461da177e4SLinus Torvalds return ret; 11471da177e4SLinus Torvalds } 11481da177e4SLinus Torvalds 11491da177e4SLinus Torvalds /* 11501da177e4SLinus Torvalds The algorithm is suboptimal, but it provides really 11511da177e4SLinus Torvalds fair weighted route distribution. 11521da177e4SLinus Torvalds */ 11531da177e4SLinus Torvalds 11541da177e4SLinus Torvalds void fib_select_multipath(const struct flowi *flp, struct fib_result *res) 11551da177e4SLinus Torvalds { 11561da177e4SLinus Torvalds struct fib_info *fi = res->fi; 11571da177e4SLinus Torvalds int w; 11581da177e4SLinus Torvalds 11591da177e4SLinus Torvalds spin_lock_bh(&fib_multipath_lock); 11601da177e4SLinus Torvalds if (fi->fib_power <= 0) { 11611da177e4SLinus Torvalds int power = 0; 11621da177e4SLinus Torvalds change_nexthops(fi) { 11631da177e4SLinus Torvalds if (!(nh->nh_flags&RTNH_F_DEAD)) { 11641da177e4SLinus Torvalds power += nh->nh_weight; 11651da177e4SLinus Torvalds nh->nh_power = nh->nh_weight; 11661da177e4SLinus Torvalds } 11671da177e4SLinus Torvalds } endfor_nexthops(fi); 11681da177e4SLinus Torvalds fi->fib_power = power; 11691da177e4SLinus Torvalds if (power <= 0) { 11701da177e4SLinus Torvalds spin_unlock_bh(&fib_multipath_lock); 11711da177e4SLinus Torvalds /* Race condition: route has just become dead. */ 11721da177e4SLinus Torvalds res->nh_sel = 0; 11731da177e4SLinus Torvalds return; 11741da177e4SLinus Torvalds } 11751da177e4SLinus Torvalds } 11761da177e4SLinus Torvalds 11771da177e4SLinus Torvalds 11781da177e4SLinus Torvalds /* w should be random number [0..fi->fib_power-1], 11791da177e4SLinus Torvalds it is pretty bad approximation. 11801da177e4SLinus Torvalds */ 11811da177e4SLinus Torvalds 11821da177e4SLinus Torvalds w = jiffies % fi->fib_power; 11831da177e4SLinus Torvalds 11841da177e4SLinus Torvalds change_nexthops(fi) { 11851da177e4SLinus Torvalds if (!(nh->nh_flags&RTNH_F_DEAD) && nh->nh_power) { 11861da177e4SLinus Torvalds if ((w -= nh->nh_power) <= 0) { 11871da177e4SLinus Torvalds nh->nh_power--; 11881da177e4SLinus Torvalds fi->fib_power--; 11891da177e4SLinus Torvalds res->nh_sel = nhsel; 11901da177e4SLinus Torvalds spin_unlock_bh(&fib_multipath_lock); 11911da177e4SLinus Torvalds return; 11921da177e4SLinus Torvalds } 11931da177e4SLinus Torvalds } 11941da177e4SLinus Torvalds } endfor_nexthops(fi); 11951da177e4SLinus Torvalds 11961da177e4SLinus Torvalds /* Race condition: route has just become dead. */ 11971da177e4SLinus Torvalds res->nh_sel = 0; 11981da177e4SLinus Torvalds spin_unlock_bh(&fib_multipath_lock); 11991da177e4SLinus Torvalds } 12001da177e4SLinus Torvalds #endif 1201