xref: /linux/net/ipv4/fib_semantics.c (revision 5a56a0b3a45dd0cc5b2f7bec6afd053a474ed9f5)
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  * Authors:	Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
91da177e4SLinus Torvalds  *
101da177e4SLinus Torvalds  *		This program is free software; you can redistribute it and/or
111da177e4SLinus Torvalds  *		modify it under the terms of the GNU General Public License
121da177e4SLinus Torvalds  *		as published by the Free Software Foundation; either version
131da177e4SLinus Torvalds  *		2 of the License, or (at your option) any later version.
141da177e4SLinus Torvalds  */
151da177e4SLinus Torvalds 
161da177e4SLinus Torvalds #include <asm/uaccess.h>
171da177e4SLinus Torvalds #include <linux/bitops.h>
181da177e4SLinus Torvalds #include <linux/types.h>
191da177e4SLinus Torvalds #include <linux/kernel.h>
201da177e4SLinus Torvalds #include <linux/jiffies.h>
211da177e4SLinus Torvalds #include <linux/mm.h>
221da177e4SLinus Torvalds #include <linux/string.h>
231da177e4SLinus Torvalds #include <linux/socket.h>
241da177e4SLinus Torvalds #include <linux/sockios.h>
251da177e4SLinus Torvalds #include <linux/errno.h>
261da177e4SLinus Torvalds #include <linux/in.h>
271da177e4SLinus Torvalds #include <linux/inet.h>
2814c85021SArnaldo Carvalho de Melo #include <linux/inetdevice.h>
291da177e4SLinus Torvalds #include <linux/netdevice.h>
301da177e4SLinus Torvalds #include <linux/if_arp.h>
311da177e4SLinus Torvalds #include <linux/proc_fs.h>
321da177e4SLinus Torvalds #include <linux/skbuff.h>
331da177e4SLinus Torvalds #include <linux/init.h>
345a0e3ad6STejun Heo #include <linux/slab.h>
351da177e4SLinus Torvalds 
3614c85021SArnaldo Carvalho de Melo #include <net/arp.h>
371da177e4SLinus Torvalds #include <net/ip.h>
381da177e4SLinus Torvalds #include <net/protocol.h>
391da177e4SLinus Torvalds #include <net/route.h>
401da177e4SLinus Torvalds #include <net/tcp.h>
411da177e4SLinus Torvalds #include <net/sock.h>
421da177e4SLinus Torvalds #include <net/ip_fib.h>
43f21c7bc5SThomas Graf #include <net/netlink.h>
444e902c57SThomas Graf #include <net/nexthop.h>
45571e7226SRoopa Prabhu #include <net/lwtunnel.h>
461da177e4SLinus Torvalds 
471da177e4SLinus Torvalds #include "fib_lookup.h"
481da177e4SLinus Torvalds 
49832b4c5eSStephen Hemminger static DEFINE_SPINLOCK(fib_info_lock);
501da177e4SLinus Torvalds static struct hlist_head *fib_info_hash;
511da177e4SLinus Torvalds static struct hlist_head *fib_info_laddrhash;
52123b9731SDavid S. Miller static unsigned int fib_info_hash_size;
531da177e4SLinus Torvalds static unsigned int fib_info_cnt;
541da177e4SLinus Torvalds 
551da177e4SLinus Torvalds #define DEVINDEX_HASHBITS 8
561da177e4SLinus Torvalds #define DEVINDEX_HASHSIZE (1U << DEVINDEX_HASHBITS)
571da177e4SLinus Torvalds static struct hlist_head fib_info_devhash[DEVINDEX_HASHSIZE];
581da177e4SLinus Torvalds 
591da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH
600e884c78SPeter Nørlund u32 fib_multipath_secret __read_mostly;
611da177e4SLinus Torvalds 
626a31d2a9SEric Dumazet #define for_nexthops(fi) {						\
636a31d2a9SEric Dumazet 	int nhsel; const struct fib_nh *nh;				\
646a31d2a9SEric Dumazet 	for (nhsel = 0, nh = (fi)->fib_nh;				\
656a31d2a9SEric Dumazet 	     nhsel < (fi)->fib_nhs;					\
666a31d2a9SEric Dumazet 	     nh++, nhsel++)
671da177e4SLinus Torvalds 
686a31d2a9SEric Dumazet #define change_nexthops(fi) {						\
696a31d2a9SEric Dumazet 	int nhsel; struct fib_nh *nexthop_nh;				\
706a31d2a9SEric Dumazet 	for (nhsel = 0,	nexthop_nh = (struct fib_nh *)((fi)->fib_nh);	\
716a31d2a9SEric Dumazet 	     nhsel < (fi)->fib_nhs;					\
726a31d2a9SEric Dumazet 	     nexthop_nh++, nhsel++)
731da177e4SLinus Torvalds 
741da177e4SLinus Torvalds #else /* CONFIG_IP_ROUTE_MULTIPATH */
751da177e4SLinus Torvalds 
761da177e4SLinus Torvalds /* Hope, that gcc will optimize it to get rid of dummy loop */
771da177e4SLinus Torvalds 
786a31d2a9SEric Dumazet #define for_nexthops(fi) {						\
796a31d2a9SEric Dumazet 	int nhsel; const struct fib_nh *nh = (fi)->fib_nh;		\
801da177e4SLinus Torvalds 	for (nhsel = 0; nhsel < 1; nhsel++)
811da177e4SLinus Torvalds 
826a31d2a9SEric Dumazet #define change_nexthops(fi) {						\
836a31d2a9SEric Dumazet 	int nhsel;							\
846a31d2a9SEric Dumazet 	struct fib_nh *nexthop_nh = (struct fib_nh *)((fi)->fib_nh);	\
851da177e4SLinus Torvalds 	for (nhsel = 0; nhsel < 1; nhsel++)
861da177e4SLinus Torvalds 
871da177e4SLinus Torvalds #endif /* CONFIG_IP_ROUTE_MULTIPATH */
881da177e4SLinus Torvalds 
891da177e4SLinus Torvalds #define endfor_nexthops(fi) }
901da177e4SLinus Torvalds 
911da177e4SLinus Torvalds 
923be0686bSDavid S. Miller const struct fib_prop fib_props[RTN_MAX + 1] = {
936a31d2a9SEric Dumazet 	[RTN_UNSPEC] = {
941da177e4SLinus Torvalds 		.error	= 0,
951da177e4SLinus Torvalds 		.scope	= RT_SCOPE_NOWHERE,
966a31d2a9SEric Dumazet 	},
976a31d2a9SEric Dumazet 	[RTN_UNICAST] = {
981da177e4SLinus Torvalds 		.error	= 0,
991da177e4SLinus Torvalds 		.scope	= RT_SCOPE_UNIVERSE,
1006a31d2a9SEric Dumazet 	},
1016a31d2a9SEric Dumazet 	[RTN_LOCAL] = {
1021da177e4SLinus Torvalds 		.error	= 0,
1031da177e4SLinus Torvalds 		.scope	= RT_SCOPE_HOST,
1046a31d2a9SEric Dumazet 	},
1056a31d2a9SEric Dumazet 	[RTN_BROADCAST] = {
1061da177e4SLinus Torvalds 		.error	= 0,
1071da177e4SLinus Torvalds 		.scope	= RT_SCOPE_LINK,
1086a31d2a9SEric Dumazet 	},
1096a31d2a9SEric Dumazet 	[RTN_ANYCAST] = {
1101da177e4SLinus Torvalds 		.error	= 0,
1111da177e4SLinus Torvalds 		.scope	= RT_SCOPE_LINK,
1126a31d2a9SEric Dumazet 	},
1136a31d2a9SEric Dumazet 	[RTN_MULTICAST] = {
1141da177e4SLinus Torvalds 		.error	= 0,
1151da177e4SLinus Torvalds 		.scope	= RT_SCOPE_UNIVERSE,
1166a31d2a9SEric Dumazet 	},
1176a31d2a9SEric Dumazet 	[RTN_BLACKHOLE] = {
1181da177e4SLinus Torvalds 		.error	= -EINVAL,
1191da177e4SLinus Torvalds 		.scope	= RT_SCOPE_UNIVERSE,
1206a31d2a9SEric Dumazet 	},
1216a31d2a9SEric Dumazet 	[RTN_UNREACHABLE] = {
1221da177e4SLinus Torvalds 		.error	= -EHOSTUNREACH,
1231da177e4SLinus Torvalds 		.scope	= RT_SCOPE_UNIVERSE,
1246a31d2a9SEric Dumazet 	},
1256a31d2a9SEric Dumazet 	[RTN_PROHIBIT] = {
1261da177e4SLinus Torvalds 		.error	= -EACCES,
1271da177e4SLinus Torvalds 		.scope	= RT_SCOPE_UNIVERSE,
1286a31d2a9SEric Dumazet 	},
1296a31d2a9SEric Dumazet 	[RTN_THROW] = {
1301da177e4SLinus Torvalds 		.error	= -EAGAIN,
1311da177e4SLinus Torvalds 		.scope	= RT_SCOPE_UNIVERSE,
1326a31d2a9SEric Dumazet 	},
1336a31d2a9SEric Dumazet 	[RTN_NAT] = {
1341da177e4SLinus Torvalds 		.error	= -EINVAL,
1351da177e4SLinus Torvalds 		.scope	= RT_SCOPE_NOWHERE,
1366a31d2a9SEric Dumazet 	},
1376a31d2a9SEric Dumazet 	[RTN_XRESOLVE] = {
1381da177e4SLinus Torvalds 		.error	= -EINVAL,
1391da177e4SLinus Torvalds 		.scope	= RT_SCOPE_NOWHERE,
1406a31d2a9SEric Dumazet 	},
1411da177e4SLinus Torvalds };
1421da177e4SLinus Torvalds 
143c5038a83SDavid S. Miller static void rt_fibinfo_free(struct rtable __rcu **rtp)
14454764bb6SEric Dumazet {
14554764bb6SEric Dumazet 	struct rtable *rt = rcu_dereference_protected(*rtp, 1);
14654764bb6SEric Dumazet 
14754764bb6SEric Dumazet 	if (!rt)
14854764bb6SEric Dumazet 		return;
14954764bb6SEric Dumazet 
15054764bb6SEric Dumazet 	/* Not even needed : RCU_INIT_POINTER(*rtp, NULL);
15154764bb6SEric Dumazet 	 * because we waited an RCU grace period before calling
15254764bb6SEric Dumazet 	 * free_fib_info_rcu()
15354764bb6SEric Dumazet 	 */
15454764bb6SEric Dumazet 
15554764bb6SEric Dumazet 	dst_free(&rt->dst);
15654764bb6SEric Dumazet }
15754764bb6SEric Dumazet 
158c5038a83SDavid S. Miller static void free_nh_exceptions(struct fib_nh *nh)
159c5038a83SDavid S. Miller {
160caa41527SEric Dumazet 	struct fnhe_hash_bucket *hash;
161c5038a83SDavid S. Miller 	int i;
162c5038a83SDavid S. Miller 
163caa41527SEric Dumazet 	hash = rcu_dereference_protected(nh->nh_exceptions, 1);
164caa41527SEric Dumazet 	if (!hash)
165caa41527SEric Dumazet 		return;
166c5038a83SDavid S. Miller 	for (i = 0; i < FNHE_HASH_SIZE; i++) {
167c5038a83SDavid S. Miller 		struct fib_nh_exception *fnhe;
168c5038a83SDavid S. Miller 
169c5038a83SDavid S. Miller 		fnhe = rcu_dereference_protected(hash[i].chain, 1);
170c5038a83SDavid S. Miller 		while (fnhe) {
171c5038a83SDavid S. Miller 			struct fib_nh_exception *next;
172c5038a83SDavid S. Miller 
173c5038a83SDavid S. Miller 			next = rcu_dereference_protected(fnhe->fnhe_next, 1);
174c5038a83SDavid S. Miller 
1752ffae99dSTimo Teräs 			rt_fibinfo_free(&fnhe->fnhe_rth_input);
1762ffae99dSTimo Teräs 			rt_fibinfo_free(&fnhe->fnhe_rth_output);
177c5038a83SDavid S. Miller 
178c5038a83SDavid S. Miller 			kfree(fnhe);
179c5038a83SDavid S. Miller 
180c5038a83SDavid S. Miller 			fnhe = next;
181c5038a83SDavid S. Miller 		}
182c5038a83SDavid S. Miller 	}
183c5038a83SDavid S. Miller 	kfree(hash);
184c5038a83SDavid S. Miller }
185c5038a83SDavid S. Miller 
186c5038a83SDavid S. Miller static void rt_fibinfo_free_cpus(struct rtable __rcu * __percpu *rtp)
187d26b3a7cSEric Dumazet {
188d26b3a7cSEric Dumazet 	int cpu;
189d26b3a7cSEric Dumazet 
190d26b3a7cSEric Dumazet 	if (!rtp)
191d26b3a7cSEric Dumazet 		return;
192d26b3a7cSEric Dumazet 
193d26b3a7cSEric Dumazet 	for_each_possible_cpu(cpu) {
194d26b3a7cSEric Dumazet 		struct rtable *rt;
195d26b3a7cSEric Dumazet 
196d26b3a7cSEric Dumazet 		rt = rcu_dereference_protected(*per_cpu_ptr(rtp, cpu), 1);
197d26b3a7cSEric Dumazet 		if (rt)
198d26b3a7cSEric Dumazet 			dst_free(&rt->dst);
199d26b3a7cSEric Dumazet 	}
200d26b3a7cSEric Dumazet 	free_percpu(rtp);
201d26b3a7cSEric Dumazet }
202d26b3a7cSEric Dumazet 
2031da177e4SLinus Torvalds /* Release a nexthop info record */
20419c1ea14SYan, Zheng static void free_fib_info_rcu(struct rcu_head *head)
20519c1ea14SYan, Zheng {
20619c1ea14SYan, Zheng 	struct fib_info *fi = container_of(head, struct fib_info, rcu);
20719c1ea14SYan, Zheng 
208e49cc0daSYanmin Zhang 	change_nexthops(fi) {
209e49cc0daSYanmin Zhang 		if (nexthop_nh->nh_dev)
210e49cc0daSYanmin Zhang 			dev_put(nexthop_nh->nh_dev);
2115a6228a0SNicolas Dichtel 		lwtstate_put(nexthop_nh->nh_lwtstate);
2124895c771SDavid S. Miller 		free_nh_exceptions(nexthop_nh);
213c5038a83SDavid S. Miller 		rt_fibinfo_free_cpus(nexthop_nh->nh_pcpu_rth_output);
214c5038a83SDavid S. Miller 		rt_fibinfo_free(&nexthop_nh->nh_rth_input);
215e49cc0daSYanmin Zhang 	} endfor_nexthops(fi);
216e49cc0daSYanmin Zhang 
21719c1ea14SYan, Zheng 	if (fi->fib_metrics != (u32 *) dst_default_metrics)
21819c1ea14SYan, Zheng 		kfree(fi->fib_metrics);
21919c1ea14SYan, Zheng 	kfree(fi);
22019c1ea14SYan, Zheng }
2211da177e4SLinus Torvalds 
2221da177e4SLinus Torvalds void free_fib_info(struct fib_info *fi)
2231da177e4SLinus Torvalds {
2241da177e4SLinus Torvalds 	if (fi->fib_dead == 0) {
225058bd4d2SJoe Perches 		pr_warn("Freeing alive fib_info %p\n", fi);
2261da177e4SLinus Torvalds 		return;
2271da177e4SLinus Torvalds 	}
2281da177e4SLinus Torvalds 	fib_info_cnt--;
2297a9bc9b8SDavid S. Miller #ifdef CONFIG_IP_ROUTE_CLASSID
2307a9bc9b8SDavid S. Miller 	change_nexthops(fi) {
2317a9bc9b8SDavid S. Miller 		if (nexthop_nh->nh_tclassid)
232f4530fa5SDavid S. Miller 			fi->fib_net->ipv4.fib_num_tclassid_users--;
2337a9bc9b8SDavid S. Miller 	} endfor_nexthops(fi);
2347a9bc9b8SDavid S. Miller #endif
23519c1ea14SYan, Zheng 	call_rcu(&fi->rcu, free_fib_info_rcu);
2361da177e4SLinus Torvalds }
2371da177e4SLinus Torvalds 
2381da177e4SLinus Torvalds void fib_release_info(struct fib_info *fi)
2391da177e4SLinus Torvalds {
240832b4c5eSStephen Hemminger 	spin_lock_bh(&fib_info_lock);
2411da177e4SLinus Torvalds 	if (fi && --fi->fib_treeref == 0) {
2421da177e4SLinus Torvalds 		hlist_del(&fi->fib_hash);
2431da177e4SLinus Torvalds 		if (fi->fib_prefsrc)
2441da177e4SLinus Torvalds 			hlist_del(&fi->fib_lhash);
2451da177e4SLinus Torvalds 		change_nexthops(fi) {
24671fceff0SDavid S. Miller 			if (!nexthop_nh->nh_dev)
2471da177e4SLinus Torvalds 				continue;
24871fceff0SDavid S. Miller 			hlist_del(&nexthop_nh->nh_hash);
2491da177e4SLinus Torvalds 		} endfor_nexthops(fi)
2501da177e4SLinus Torvalds 		fi->fib_dead = 1;
2511da177e4SLinus Torvalds 		fib_info_put(fi);
2521da177e4SLinus Torvalds 	}
253832b4c5eSStephen Hemminger 	spin_unlock_bh(&fib_info_lock);
2541da177e4SLinus Torvalds }
2551da177e4SLinus Torvalds 
2566a31d2a9SEric Dumazet static inline int nh_comp(const struct fib_info *fi, const struct fib_info *ofi)
2571da177e4SLinus Torvalds {
2581da177e4SLinus Torvalds 	const struct fib_nh *onh = ofi->fib_nh;
2591da177e4SLinus Torvalds 
2601da177e4SLinus Torvalds 	for_nexthops(fi) {
2611da177e4SLinus Torvalds 		if (nh->nh_oif != onh->nh_oif ||
2621da177e4SLinus Torvalds 		    nh->nh_gw  != onh->nh_gw ||
2631da177e4SLinus Torvalds 		    nh->nh_scope != onh->nh_scope ||
2641da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH
2651da177e4SLinus Torvalds 		    nh->nh_weight != onh->nh_weight ||
2661da177e4SLinus Torvalds #endif
267c7066f70SPatrick McHardy #ifdef CONFIG_IP_ROUTE_CLASSID
2681da177e4SLinus Torvalds 		    nh->nh_tclassid != onh->nh_tclassid ||
2691da177e4SLinus Torvalds #endif
270571e7226SRoopa Prabhu 		    lwtunnel_cmp_encap(nh->nh_lwtstate, onh->nh_lwtstate) ||
2718a3d0316SAndy Gospodarek 		    ((nh->nh_flags ^ onh->nh_flags) & ~RTNH_COMPARE_MASK))
2721da177e4SLinus Torvalds 			return -1;
2731da177e4SLinus Torvalds 		onh++;
2741da177e4SLinus Torvalds 	} endfor_nexthops(fi);
2751da177e4SLinus Torvalds 	return 0;
2761da177e4SLinus Torvalds }
2771da177e4SLinus Torvalds 
27888ebc72fSDavid S. Miller static inline unsigned int fib_devindex_hashfn(unsigned int val)
27988ebc72fSDavid S. Miller {
28088ebc72fSDavid S. Miller 	unsigned int mask = DEVINDEX_HASHSIZE - 1;
28188ebc72fSDavid S. Miller 
28288ebc72fSDavid S. Miller 	return (val ^
28388ebc72fSDavid S. Miller 		(val >> DEVINDEX_HASHBITS) ^
28488ebc72fSDavid S. Miller 		(val >> (DEVINDEX_HASHBITS * 2))) & mask;
28588ebc72fSDavid S. Miller }
28688ebc72fSDavid S. Miller 
2871da177e4SLinus Torvalds static inline unsigned int fib_info_hashfn(const struct fib_info *fi)
2881da177e4SLinus Torvalds {
289123b9731SDavid S. Miller 	unsigned int mask = (fib_info_hash_size - 1);
2901da177e4SLinus Torvalds 	unsigned int val = fi->fib_nhs;
2911da177e4SLinus Torvalds 
29237e826c5SDavid S. Miller 	val ^= (fi->fib_protocol << 8) | fi->fib_scope;
29381f7bf6cSAl Viro 	val ^= (__force u32)fi->fib_prefsrc;
2941da177e4SLinus Torvalds 	val ^= fi->fib_priority;
29588ebc72fSDavid S. Miller 	for_nexthops(fi) {
29688ebc72fSDavid S. Miller 		val ^= fib_devindex_hashfn(nh->nh_oif);
29788ebc72fSDavid S. Miller 	} endfor_nexthops(fi)
2981da177e4SLinus Torvalds 
2991da177e4SLinus Torvalds 	return (val ^ (val >> 7) ^ (val >> 12)) & mask;
3001da177e4SLinus Torvalds }
3011da177e4SLinus Torvalds 
3021da177e4SLinus Torvalds static struct fib_info *fib_find_info(const struct fib_info *nfi)
3031da177e4SLinus Torvalds {
3041da177e4SLinus Torvalds 	struct hlist_head *head;
3051da177e4SLinus Torvalds 	struct fib_info *fi;
3061da177e4SLinus Torvalds 	unsigned int hash;
3071da177e4SLinus Torvalds 
3081da177e4SLinus Torvalds 	hash = fib_info_hashfn(nfi);
3091da177e4SLinus Torvalds 	head = &fib_info_hash[hash];
3101da177e4SLinus Torvalds 
311b67bfe0dSSasha Levin 	hlist_for_each_entry(fi, head, fib_hash) {
31209ad9bc7SOctavian Purdila 		if (!net_eq(fi->fib_net, nfi->fib_net))
3134814bdbdSDenis V. Lunev 			continue;
3141da177e4SLinus Torvalds 		if (fi->fib_nhs != nfi->fib_nhs)
3151da177e4SLinus Torvalds 			continue;
3161da177e4SLinus Torvalds 		if (nfi->fib_protocol == fi->fib_protocol &&
31737e826c5SDavid S. Miller 		    nfi->fib_scope == fi->fib_scope &&
3181da177e4SLinus Torvalds 		    nfi->fib_prefsrc == fi->fib_prefsrc &&
3191da177e4SLinus Torvalds 		    nfi->fib_priority == fi->fib_priority &&
320f4ef85bbSEric Dumazet 		    nfi->fib_type == fi->fib_type &&
3211da177e4SLinus Torvalds 		    memcmp(nfi->fib_metrics, fi->fib_metrics,
322fcd13f42SEric Dumazet 			   sizeof(u32) * RTAX_MAX) == 0 &&
3238a3d0316SAndy Gospodarek 		    !((nfi->fib_flags ^ fi->fib_flags) & ~RTNH_COMPARE_MASK) &&
3241da177e4SLinus Torvalds 		    (nfi->fib_nhs == 0 || nh_comp(fi, nfi) == 0))
3251da177e4SLinus Torvalds 			return fi;
3261da177e4SLinus Torvalds 	}
3271da177e4SLinus Torvalds 
3281da177e4SLinus Torvalds 	return NULL;
3291da177e4SLinus Torvalds }
3301da177e4SLinus Torvalds 
3311da177e4SLinus Torvalds /* Check, that the gateway is already configured.
3326a31d2a9SEric Dumazet  * Used only by redirect accept routine.
3331da177e4SLinus Torvalds  */
334d878e72eSAl Viro int ip_fib_check_default(__be32 gw, struct net_device *dev)
3351da177e4SLinus Torvalds {
3361da177e4SLinus Torvalds 	struct hlist_head *head;
3371da177e4SLinus Torvalds 	struct fib_nh *nh;
3381da177e4SLinus Torvalds 	unsigned int hash;
3391da177e4SLinus Torvalds 
340832b4c5eSStephen Hemminger 	spin_lock(&fib_info_lock);
3411da177e4SLinus Torvalds 
3421da177e4SLinus Torvalds 	hash = fib_devindex_hashfn(dev->ifindex);
3431da177e4SLinus Torvalds 	head = &fib_info_devhash[hash];
344b67bfe0dSSasha Levin 	hlist_for_each_entry(nh, head, nh_hash) {
3451da177e4SLinus Torvalds 		if (nh->nh_dev == dev &&
3461da177e4SLinus Torvalds 		    nh->nh_gw == gw &&
3471da177e4SLinus Torvalds 		    !(nh->nh_flags & RTNH_F_DEAD)) {
348832b4c5eSStephen Hemminger 			spin_unlock(&fib_info_lock);
3491da177e4SLinus Torvalds 			return 0;
3501da177e4SLinus Torvalds 		}
3511da177e4SLinus Torvalds 	}
3521da177e4SLinus Torvalds 
353832b4c5eSStephen Hemminger 	spin_unlock(&fib_info_lock);
3541da177e4SLinus Torvalds 
3551da177e4SLinus Torvalds 	return -1;
3561da177e4SLinus Torvalds }
3571da177e4SLinus Torvalds 
358339bf98fSThomas Graf static inline size_t fib_nlmsg_size(struct fib_info *fi)
359339bf98fSThomas Graf {
360339bf98fSThomas Graf 	size_t payload = NLMSG_ALIGN(sizeof(struct rtmsg))
361339bf98fSThomas Graf 			 + nla_total_size(4) /* RTA_TABLE */
362339bf98fSThomas Graf 			 + nla_total_size(4) /* RTA_DST */
363339bf98fSThomas Graf 			 + nla_total_size(4) /* RTA_PRIORITY */
364ea697639SDaniel Borkmann 			 + nla_total_size(4) /* RTA_PREFSRC */
365ea697639SDaniel Borkmann 			 + nla_total_size(TCP_CA_NAME_MAX); /* RTAX_CC_ALGO */
366339bf98fSThomas Graf 
367339bf98fSThomas Graf 	/* space for nested metrics */
368339bf98fSThomas Graf 	payload += nla_total_size((RTAX_MAX * nla_total_size(4)));
369339bf98fSThomas Graf 
370339bf98fSThomas Graf 	if (fi->fib_nhs) {
371571e7226SRoopa Prabhu 		size_t nh_encapsize = 0;
372339bf98fSThomas Graf 		/* Also handles the special case fib_nhs == 1 */
373339bf98fSThomas Graf 
374339bf98fSThomas Graf 		/* each nexthop is packed in an attribute */
375339bf98fSThomas Graf 		size_t nhsize = nla_total_size(sizeof(struct rtnexthop));
376339bf98fSThomas Graf 
377339bf98fSThomas Graf 		/* may contain flow and gateway attribute */
378339bf98fSThomas Graf 		nhsize += 2 * nla_total_size(4);
379339bf98fSThomas Graf 
380571e7226SRoopa Prabhu 		/* grab encap info */
381571e7226SRoopa Prabhu 		for_nexthops(fi) {
382571e7226SRoopa Prabhu 			if (nh->nh_lwtstate) {
383571e7226SRoopa Prabhu 				/* RTA_ENCAP_TYPE */
384571e7226SRoopa Prabhu 				nh_encapsize += lwtunnel_get_encap_size(
385571e7226SRoopa Prabhu 						nh->nh_lwtstate);
386571e7226SRoopa Prabhu 				/* RTA_ENCAP */
387571e7226SRoopa Prabhu 				nh_encapsize +=  nla_total_size(2);
388571e7226SRoopa Prabhu 			}
389571e7226SRoopa Prabhu 		} endfor_nexthops(fi);
390571e7226SRoopa Prabhu 
391339bf98fSThomas Graf 		/* all nexthops are packed in a nested attribute */
392571e7226SRoopa Prabhu 		payload += nla_total_size((fi->fib_nhs * nhsize) +
393571e7226SRoopa Prabhu 					  nh_encapsize);
394571e7226SRoopa Prabhu 
395339bf98fSThomas Graf 	}
396339bf98fSThomas Graf 
397339bf98fSThomas Graf 	return payload;
398339bf98fSThomas Graf }
399339bf98fSThomas Graf 
40081f7bf6cSAl Viro void rtmsg_fib(int event, __be32 key, struct fib_alias *fa,
4019877b253SJoe Perches 	       int dst_len, u32 tb_id, const struct nl_info *info,
402b8f55831SMilan Kocian 	       unsigned int nlm_flags)
4031da177e4SLinus Torvalds {
4041da177e4SLinus Torvalds 	struct sk_buff *skb;
4054e902c57SThomas Graf 	u32 seq = info->nlh ? info->nlh->nlmsg_seq : 0;
406f21c7bc5SThomas Graf 	int err = -ENOBUFS;
4071da177e4SLinus Torvalds 
408339bf98fSThomas Graf 	skb = nlmsg_new(fib_nlmsg_size(fa->fa_info), GFP_KERNEL);
40951456b29SIan Morris 	if (!skb)
410f21c7bc5SThomas Graf 		goto errout;
4111da177e4SLinus Torvalds 
41215e47304SEric W. Biederman 	err = fib_dump_info(skb, info->portid, seq, event, tb_id,
41337e826c5SDavid S. Miller 			    fa->fa_type, key, dst_len,
414b8f55831SMilan Kocian 			    fa->fa_tos, fa->fa_info, nlm_flags);
41526932566SPatrick McHardy 	if (err < 0) {
41626932566SPatrick McHardy 		/* -EMSGSIZE implies BUG in fib_nlmsg_size() */
41726932566SPatrick McHardy 		WARN_ON(err == -EMSGSIZE);
41826932566SPatrick McHardy 		kfree_skb(skb);
41926932566SPatrick McHardy 		goto errout;
42026932566SPatrick McHardy 	}
42115e47304SEric W. Biederman 	rtnl_notify(skb, info->nl_net, info->portid, RTNLGRP_IPV4_ROUTE,
4224e902c57SThomas Graf 		    info->nlh, GFP_KERNEL);
4231ce85fe4SPablo Neira Ayuso 	return;
424f21c7bc5SThomas Graf errout:
425f21c7bc5SThomas Graf 	if (err < 0)
4264d1169c1SDenis V. Lunev 		rtnl_set_sk_err(info->nl_net, RTNLGRP_IPV4_ROUTE, err);
4271da177e4SLinus Torvalds }
4281da177e4SLinus Torvalds 
429c9cb6b6eSStephen Hemminger static int fib_detect_death(struct fib_info *fi, int order,
430c9cb6b6eSStephen Hemminger 			    struct fib_info **last_resort, int *last_idx,
431c9cb6b6eSStephen Hemminger 			    int dflt)
4321da177e4SLinus Torvalds {
4331da177e4SLinus Torvalds 	struct neighbour *n;
4341da177e4SLinus Torvalds 	int state = NUD_NONE;
4351da177e4SLinus Torvalds 
4361da177e4SLinus Torvalds 	n = neigh_lookup(&arp_tbl, &fi->fib_nh[0].nh_gw, fi->fib_dev);
4371da177e4SLinus Torvalds 	if (n) {
4381da177e4SLinus Torvalds 		state = n->nud_state;
4391da177e4SLinus Torvalds 		neigh_release(n);
44088f64320SJulian Anastasov 	} else {
44188f64320SJulian Anastasov 		return 0;
4421da177e4SLinus Torvalds 	}
4431da177e4SLinus Torvalds 	if (state == NUD_REACHABLE)
4441da177e4SLinus Torvalds 		return 0;
445c17860a0SDenis V. Lunev 	if ((state & NUD_VALID) && order != dflt)
4461da177e4SLinus Torvalds 		return 0;
4471da177e4SLinus Torvalds 	if ((state & NUD_VALID) ||
44888f64320SJulian Anastasov 	    (*last_idx < 0 && order > dflt && state != NUD_INCOMPLETE)) {
4491da177e4SLinus Torvalds 		*last_resort = fi;
4501da177e4SLinus Torvalds 		*last_idx = order;
4511da177e4SLinus Torvalds 	}
4521da177e4SLinus Torvalds 	return 1;
4531da177e4SLinus Torvalds }
4541da177e4SLinus Torvalds 
4551da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH
4561da177e4SLinus Torvalds 
4574e902c57SThomas Graf static int fib_count_nexthops(struct rtnexthop *rtnh, int remaining)
4581da177e4SLinus Torvalds {
4591da177e4SLinus Torvalds 	int nhs = 0;
4601da177e4SLinus Torvalds 
4614e902c57SThomas Graf 	while (rtnh_ok(rtnh, remaining)) {
4621da177e4SLinus Torvalds 		nhs++;
4634e902c57SThomas Graf 		rtnh = rtnh_next(rtnh, &remaining);
4641da177e4SLinus Torvalds 	}
4651da177e4SLinus Torvalds 
4664e902c57SThomas Graf 	/* leftover implies invalid nexthop configuration, discard it */
4674e902c57SThomas Graf 	return remaining > 0 ? 0 : nhs;
4684e902c57SThomas Graf }
4691da177e4SLinus Torvalds 
4704e902c57SThomas Graf static int fib_get_nhs(struct fib_info *fi, struct rtnexthop *rtnh,
4714e902c57SThomas Graf 		       int remaining, struct fib_config *cfg)
4724e902c57SThomas Graf {
473571e7226SRoopa Prabhu 	struct net *net = cfg->fc_nlinfo.nl_net;
474571e7226SRoopa Prabhu 	int ret;
475571e7226SRoopa Prabhu 
4761da177e4SLinus Torvalds 	change_nexthops(fi) {
4774e902c57SThomas Graf 		int attrlen;
4784e902c57SThomas Graf 
4794e902c57SThomas Graf 		if (!rtnh_ok(rtnh, remaining))
4801da177e4SLinus Torvalds 			return -EINVAL;
4814e902c57SThomas Graf 
48280610229SJulian Anastasov 		if (rtnh->rtnh_flags & (RTNH_F_DEAD | RTNH_F_LINKDOWN))
48380610229SJulian Anastasov 			return -EINVAL;
48480610229SJulian Anastasov 
48571fceff0SDavid S. Miller 		nexthop_nh->nh_flags =
48671fceff0SDavid S. Miller 			(cfg->fc_flags & ~0xFF) | rtnh->rtnh_flags;
48771fceff0SDavid S. Miller 		nexthop_nh->nh_oif = rtnh->rtnh_ifindex;
48871fceff0SDavid S. Miller 		nexthop_nh->nh_weight = rtnh->rtnh_hops + 1;
4894e902c57SThomas Graf 
4904e902c57SThomas Graf 		attrlen = rtnh_attrlen(rtnh);
4914e902c57SThomas Graf 		if (attrlen > 0) {
4924e902c57SThomas Graf 			struct nlattr *nla, *attrs = rtnh_attrs(rtnh);
4934e902c57SThomas Graf 
4944e902c57SThomas Graf 			nla = nla_find(attrs, attrlen, RTA_GATEWAY);
49567b61f6cSJiri Benc 			nexthop_nh->nh_gw = nla ? nla_get_in_addr(nla) : 0;
496c7066f70SPatrick McHardy #ifdef CONFIG_IP_ROUTE_CLASSID
4974e902c57SThomas Graf 			nla = nla_find(attrs, attrlen, RTA_FLOW);
49871fceff0SDavid S. Miller 			nexthop_nh->nh_tclassid = nla ? nla_get_u32(nla) : 0;
4997a9bc9b8SDavid S. Miller 			if (nexthop_nh->nh_tclassid)
500f4530fa5SDavid S. Miller 				fi->fib_net->ipv4.fib_num_tclassid_users++;
5011da177e4SLinus Torvalds #endif
502571e7226SRoopa Prabhu 			nla = nla_find(attrs, attrlen, RTA_ENCAP);
503571e7226SRoopa Prabhu 			if (nla) {
504571e7226SRoopa Prabhu 				struct lwtunnel_state *lwtstate;
505571e7226SRoopa Prabhu 				struct net_device *dev = NULL;
506571e7226SRoopa Prabhu 				struct nlattr *nla_entype;
507571e7226SRoopa Prabhu 
508571e7226SRoopa Prabhu 				nla_entype = nla_find(attrs, attrlen,
509571e7226SRoopa Prabhu 						      RTA_ENCAP_TYPE);
510571e7226SRoopa Prabhu 				if (!nla_entype)
511571e7226SRoopa Prabhu 					goto err_inval;
512571e7226SRoopa Prabhu 				if (cfg->fc_oif)
513571e7226SRoopa Prabhu 					dev = __dev_get_by_index(net, cfg->fc_oif);
514571e7226SRoopa Prabhu 				ret = lwtunnel_build_state(dev, nla_get_u16(
515571e7226SRoopa Prabhu 							   nla_entype),
516127eb7cdSTom Herbert 							   nla,  AF_INET, cfg,
517127eb7cdSTom Herbert 							   &lwtstate);
518571e7226SRoopa Prabhu 				if (ret)
519571e7226SRoopa Prabhu 					goto errout;
5205a6228a0SNicolas Dichtel 				nexthop_nh->nh_lwtstate =
5215a6228a0SNicolas Dichtel 					lwtstate_get(lwtstate);
522571e7226SRoopa Prabhu 			}
5231da177e4SLinus Torvalds 		}
5244e902c57SThomas Graf 
5254e902c57SThomas Graf 		rtnh = rtnh_next(rtnh, &remaining);
5261da177e4SLinus Torvalds 	} endfor_nexthops(fi);
5274e902c57SThomas Graf 
5281da177e4SLinus Torvalds 	return 0;
529571e7226SRoopa Prabhu 
530571e7226SRoopa Prabhu err_inval:
531571e7226SRoopa Prabhu 	ret = -EINVAL;
532571e7226SRoopa Prabhu 
533571e7226SRoopa Prabhu errout:
534571e7226SRoopa Prabhu 	return ret;
5351da177e4SLinus Torvalds }
5361da177e4SLinus Torvalds 
5370e884c78SPeter Nørlund static void fib_rebalance(struct fib_info *fi)
5380e884c78SPeter Nørlund {
5390e884c78SPeter Nørlund 	int total;
5400e884c78SPeter Nørlund 	int w;
5410e884c78SPeter Nørlund 	struct in_device *in_dev;
5420e884c78SPeter Nørlund 
5430e884c78SPeter Nørlund 	if (fi->fib_nhs < 2)
5440e884c78SPeter Nørlund 		return;
5450e884c78SPeter Nørlund 
5460e884c78SPeter Nørlund 	total = 0;
5470e884c78SPeter Nørlund 	for_nexthops(fi) {
5480e884c78SPeter Nørlund 		if (nh->nh_flags & RTNH_F_DEAD)
5490e884c78SPeter Nørlund 			continue;
5500e884c78SPeter Nørlund 
55151161aa9SDavid Ahern 		in_dev = __in_dev_get_rtnl(nh->nh_dev);
5520e884c78SPeter Nørlund 
5530e884c78SPeter Nørlund 		if (in_dev &&
5540e884c78SPeter Nørlund 		    IN_DEV_IGNORE_ROUTES_WITH_LINKDOWN(in_dev) &&
5550e884c78SPeter Nørlund 		    nh->nh_flags & RTNH_F_LINKDOWN)
5560e884c78SPeter Nørlund 			continue;
5570e884c78SPeter Nørlund 
5580e884c78SPeter Nørlund 		total += nh->nh_weight;
5590e884c78SPeter Nørlund 	} endfor_nexthops(fi);
5600e884c78SPeter Nørlund 
5610e884c78SPeter Nørlund 	w = 0;
5620e884c78SPeter Nørlund 	change_nexthops(fi) {
5630e884c78SPeter Nørlund 		int upper_bound;
5640e884c78SPeter Nørlund 
56551161aa9SDavid Ahern 		in_dev = __in_dev_get_rtnl(nexthop_nh->nh_dev);
5660e884c78SPeter Nørlund 
5670e884c78SPeter Nørlund 		if (nexthop_nh->nh_flags & RTNH_F_DEAD) {
5680e884c78SPeter Nørlund 			upper_bound = -1;
5690e884c78SPeter Nørlund 		} else if (in_dev &&
5700e884c78SPeter Nørlund 			   IN_DEV_IGNORE_ROUTES_WITH_LINKDOWN(in_dev) &&
5710e884c78SPeter Nørlund 			   nexthop_nh->nh_flags & RTNH_F_LINKDOWN) {
5720e884c78SPeter Nørlund 			upper_bound = -1;
5730e884c78SPeter Nørlund 		} else {
5740e884c78SPeter Nørlund 			w += nexthop_nh->nh_weight;
5750a837fe4SPeter Nørlund 			upper_bound = DIV_ROUND_CLOSEST_ULL((u64)w << 31,
5760e884c78SPeter Nørlund 							    total) - 1;
5770e884c78SPeter Nørlund 		}
5780e884c78SPeter Nørlund 
5790e884c78SPeter Nørlund 		atomic_set(&nexthop_nh->nh_upper_bound, upper_bound);
5800e884c78SPeter Nørlund 	} endfor_nexthops(fi);
5810e884c78SPeter Nørlund 
5820e884c78SPeter Nørlund 	net_get_random_once(&fib_multipath_secret,
5830e884c78SPeter Nørlund 			    sizeof(fib_multipath_secret));
5840e884c78SPeter Nørlund }
5850e884c78SPeter Nørlund 
5860e884c78SPeter Nørlund static inline void fib_add_weight(struct fib_info *fi,
5870e884c78SPeter Nørlund 				  const struct fib_nh *nh)
5880e884c78SPeter Nørlund {
5890e884c78SPeter Nørlund 	fi->fib_weight += nh->nh_weight;
5900e884c78SPeter Nørlund }
5910e884c78SPeter Nørlund 
5920e884c78SPeter Nørlund #else /* CONFIG_IP_ROUTE_MULTIPATH */
5930e884c78SPeter Nørlund 
5940e884c78SPeter Nørlund #define fib_rebalance(fi) do { } while (0)
5950e884c78SPeter Nørlund #define fib_add_weight(fi, nh) do { } while (0)
5960e884c78SPeter Nørlund 
5970e884c78SPeter Nørlund #endif /* CONFIG_IP_ROUTE_MULTIPATH */
5981da177e4SLinus Torvalds 
599e01286efSYing Xue static int fib_encap_match(struct net *net, u16 encap_type,
600571e7226SRoopa Prabhu 			   struct nlattr *encap,
601127eb7cdSTom Herbert 			   int oif, const struct fib_nh *nh,
602127eb7cdSTom Herbert 			   const struct fib_config *cfg)
603571e7226SRoopa Prabhu {
604571e7226SRoopa Prabhu 	struct lwtunnel_state *lwtstate;
605571e7226SRoopa Prabhu 	struct net_device *dev = NULL;
606df383e62SJiri Benc 	int ret, result = 0;
607571e7226SRoopa Prabhu 
608571e7226SRoopa Prabhu 	if (encap_type == LWTUNNEL_ENCAP_NONE)
609571e7226SRoopa Prabhu 		return 0;
610571e7226SRoopa Prabhu 
611571e7226SRoopa Prabhu 	if (oif)
612571e7226SRoopa Prabhu 		dev = __dev_get_by_index(net, oif);
613127eb7cdSTom Herbert 	ret = lwtunnel_build_state(dev, encap_type, encap,
614127eb7cdSTom Herbert 				   AF_INET, cfg, &lwtstate);
615df383e62SJiri Benc 	if (!ret) {
616df383e62SJiri Benc 		result = lwtunnel_cmp_encap(lwtstate, nh->nh_lwtstate);
617df383e62SJiri Benc 		lwtstate_free(lwtstate);
618df383e62SJiri Benc 	}
619571e7226SRoopa Prabhu 
620df383e62SJiri Benc 	return result;
621571e7226SRoopa Prabhu }
622571e7226SRoopa Prabhu 
6234e902c57SThomas Graf int fib_nh_match(struct fib_config *cfg, struct fib_info *fi)
6241da177e4SLinus Torvalds {
625571e7226SRoopa Prabhu 	struct net *net = cfg->fc_nlinfo.nl_net;
6261da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH
6274e902c57SThomas Graf 	struct rtnexthop *rtnh;
6284e902c57SThomas Graf 	int remaining;
6291da177e4SLinus Torvalds #endif
6301da177e4SLinus Torvalds 
6314e902c57SThomas Graf 	if (cfg->fc_priority && cfg->fc_priority != fi->fib_priority)
6321da177e4SLinus Torvalds 		return 1;
6331da177e4SLinus Torvalds 
6344e902c57SThomas Graf 	if (cfg->fc_oif || cfg->fc_gw) {
635571e7226SRoopa Prabhu 		if (cfg->fc_encap) {
636571e7226SRoopa Prabhu 			if (fib_encap_match(net, cfg->fc_encap_type,
637571e7226SRoopa Prabhu 					    cfg->fc_encap, cfg->fc_oif,
638127eb7cdSTom Herbert 					    fi->fib_nh, cfg))
639571e7226SRoopa Prabhu 			    return 1;
640571e7226SRoopa Prabhu 		}
6414e902c57SThomas Graf 		if ((!cfg->fc_oif || cfg->fc_oif == fi->fib_nh->nh_oif) &&
6424e902c57SThomas Graf 		    (!cfg->fc_gw  || cfg->fc_gw == fi->fib_nh->nh_gw))
6431da177e4SLinus Torvalds 			return 0;
6441da177e4SLinus Torvalds 		return 1;
6451da177e4SLinus Torvalds 	}
6461da177e4SLinus Torvalds 
6471da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH
64851456b29SIan Morris 	if (!cfg->fc_mp)
6491da177e4SLinus Torvalds 		return 0;
6504e902c57SThomas Graf 
6514e902c57SThomas Graf 	rtnh = cfg->fc_mp;
6524e902c57SThomas Graf 	remaining = cfg->fc_mp_len;
6531da177e4SLinus Torvalds 
6541da177e4SLinus Torvalds 	for_nexthops(fi) {
6554e902c57SThomas Graf 		int attrlen;
6561da177e4SLinus Torvalds 
6574e902c57SThomas Graf 		if (!rtnh_ok(rtnh, remaining))
6581da177e4SLinus Torvalds 			return -EINVAL;
6594e902c57SThomas Graf 
6604e902c57SThomas Graf 		if (rtnh->rtnh_ifindex && rtnh->rtnh_ifindex != nh->nh_oif)
6611da177e4SLinus Torvalds 			return 1;
6624e902c57SThomas Graf 
6634e902c57SThomas Graf 		attrlen = rtnh_attrlen(rtnh);
664f76936d0SJiri Pirko 		if (attrlen > 0) {
6654e902c57SThomas Graf 			struct nlattr *nla, *attrs = rtnh_attrs(rtnh);
6664e902c57SThomas Graf 
6674e902c57SThomas Graf 			nla = nla_find(attrs, attrlen, RTA_GATEWAY);
66867b61f6cSJiri Benc 			if (nla && nla_get_in_addr(nla) != nh->nh_gw)
6691da177e4SLinus Torvalds 				return 1;
670c7066f70SPatrick McHardy #ifdef CONFIG_IP_ROUTE_CLASSID
6714e902c57SThomas Graf 			nla = nla_find(attrs, attrlen, RTA_FLOW);
6724e902c57SThomas Graf 			if (nla && nla_get_u32(nla) != nh->nh_tclassid)
6731da177e4SLinus Torvalds 				return 1;
6741da177e4SLinus Torvalds #endif
6751da177e4SLinus Torvalds 		}
6764e902c57SThomas Graf 
6774e902c57SThomas Graf 		rtnh = rtnh_next(rtnh, &remaining);
6781da177e4SLinus Torvalds 	} endfor_nexthops(fi);
6791da177e4SLinus Torvalds #endif
6801da177e4SLinus Torvalds 	return 0;
6811da177e4SLinus Torvalds }
6821da177e4SLinus Torvalds 
6831da177e4SLinus Torvalds 
6841da177e4SLinus Torvalds /*
6856a31d2a9SEric Dumazet  * Picture
6866a31d2a9SEric Dumazet  * -------
6876a31d2a9SEric Dumazet  *
6886a31d2a9SEric Dumazet  * Semantics of nexthop is very messy by historical reasons.
6896a31d2a9SEric Dumazet  * We have to take into account, that:
6906a31d2a9SEric Dumazet  * a) gateway can be actually local interface address,
6916a31d2a9SEric Dumazet  *    so that gatewayed route is direct.
6926a31d2a9SEric Dumazet  * b) gateway must be on-link address, possibly
6936a31d2a9SEric Dumazet  *    described not by an ifaddr, but also by a direct route.
6946a31d2a9SEric Dumazet  * c) If both gateway and interface are specified, they should not
6956a31d2a9SEric Dumazet  *    contradict.
6966a31d2a9SEric Dumazet  * d) If we use tunnel routes, gateway could be not on-link.
6976a31d2a9SEric Dumazet  *
6986a31d2a9SEric Dumazet  * Attempt to reconcile all of these (alas, self-contradictory) conditions
6996a31d2a9SEric Dumazet  * results in pretty ugly and hairy code with obscure logic.
7006a31d2a9SEric Dumazet  *
7016a31d2a9SEric Dumazet  * I chose to generalized it instead, so that the size
7026a31d2a9SEric Dumazet  * of code does not increase practically, but it becomes
7036a31d2a9SEric Dumazet  * much more general.
7046a31d2a9SEric Dumazet  * Every prefix is assigned a "scope" value: "host" is local address,
7056a31d2a9SEric Dumazet  * "link" is direct route,
7066a31d2a9SEric Dumazet  * [ ... "site" ... "interior" ... ]
7076a31d2a9SEric Dumazet  * and "universe" is true gateway route with global meaning.
7086a31d2a9SEric Dumazet  *
7096a31d2a9SEric Dumazet  * Every prefix refers to a set of "nexthop"s (gw, oif),
7106a31d2a9SEric Dumazet  * where gw must have narrower scope. This recursion stops
7116a31d2a9SEric Dumazet  * when gw has LOCAL scope or if "nexthop" is declared ONLINK,
7126a31d2a9SEric Dumazet  * which means that gw is forced to be on link.
7136a31d2a9SEric Dumazet  *
7146a31d2a9SEric Dumazet  * Code is still hairy, but now it is apparently logically
7156a31d2a9SEric Dumazet  * consistent and very flexible. F.e. as by-product it allows
7166a31d2a9SEric Dumazet  * to co-exists in peace independent exterior and interior
7176a31d2a9SEric Dumazet  * routing processes.
7186a31d2a9SEric Dumazet  *
7196a31d2a9SEric Dumazet  * Normally it looks as following.
7206a31d2a9SEric Dumazet  *
7216a31d2a9SEric Dumazet  * {universe prefix}  -> (gw, oif) [scope link]
7226a31d2a9SEric Dumazet  *		  |
7236a31d2a9SEric Dumazet  *		  |-> {link prefix} -> (gw, oif) [scope local]
7246a31d2a9SEric Dumazet  *					|
7256a31d2a9SEric Dumazet  *					|-> {local prefix} (terminal node)
7261da177e4SLinus Torvalds  */
7274e902c57SThomas Graf static int fib_check_nh(struct fib_config *cfg, struct fib_info *fi,
7284e902c57SThomas Graf 			struct fib_nh *nh)
7291da177e4SLinus Torvalds {
730127eb7cdSTom Herbert 	int err = 0;
73186167a37SDenis V. Lunev 	struct net *net;
7326a31d2a9SEric Dumazet 	struct net_device *dev;
7331da177e4SLinus Torvalds 
73486167a37SDenis V. Lunev 	net = cfg->fc_nlinfo.nl_net;
7351da177e4SLinus Torvalds 	if (nh->nh_gw) {
7361da177e4SLinus Torvalds 		struct fib_result res;
7371da177e4SLinus Torvalds 
7381da177e4SLinus Torvalds 		if (nh->nh_flags & RTNH_F_ONLINK) {
73930bbaa19SDavid Ahern 			unsigned int addr_type;
7401da177e4SLinus Torvalds 
7414e902c57SThomas Graf 			if (cfg->fc_scope >= RT_SCOPE_LINK)
7421da177e4SLinus Torvalds 				return -EINVAL;
7436a31d2a9SEric Dumazet 			dev = __dev_get_by_index(net, nh->nh_oif);
7446a31d2a9SEric Dumazet 			if (!dev)
7451da177e4SLinus Torvalds 				return -ENODEV;
7461da177e4SLinus Torvalds 			if (!(dev->flags & IFF_UP))
7471da177e4SLinus Torvalds 				return -ENETDOWN;
74830bbaa19SDavid Ahern 			addr_type = inet_addr_type_dev_table(net, dev, nh->nh_gw);
74930bbaa19SDavid Ahern 			if (addr_type != RTN_UNICAST)
75030bbaa19SDavid Ahern 				return -EINVAL;
7518a3d0316SAndy Gospodarek 			if (!netif_carrier_ok(dev))
7528a3d0316SAndy Gospodarek 				nh->nh_flags |= RTNH_F_LINKDOWN;
7531da177e4SLinus Torvalds 			nh->nh_dev = dev;
7541da177e4SLinus Torvalds 			dev_hold(dev);
7551da177e4SLinus Torvalds 			nh->nh_scope = RT_SCOPE_LINK;
7561da177e4SLinus Torvalds 			return 0;
7571da177e4SLinus Torvalds 		}
758ebc0ffaeSEric Dumazet 		rcu_read_lock();
7591da177e4SLinus Torvalds 		{
7603bfd8472SDavid Ahern 			struct fib_table *tbl = NULL;
7619ade2286SDavid S. Miller 			struct flowi4 fl4 = {
7629ade2286SDavid S. Miller 				.daddr = nh->nh_gw,
7639ade2286SDavid S. Miller 				.flowi4_scope = cfg->fc_scope + 1,
7649ade2286SDavid S. Miller 				.flowi4_oif = nh->nh_oif,
7656a662719SCong Wang 				.flowi4_iif = LOOPBACK_IFINDEX,
7664e902c57SThomas Graf 			};
7671da177e4SLinus Torvalds 
7681da177e4SLinus Torvalds 			/* It is not necessary, but requires a bit of thinking */
7699ade2286SDavid S. Miller 			if (fl4.flowi4_scope < RT_SCOPE_LINK)
7709ade2286SDavid S. Miller 				fl4.flowi4_scope = RT_SCOPE_LINK;
7713bfd8472SDavid Ahern 
7723bfd8472SDavid Ahern 			if (cfg->fc_table)
7733bfd8472SDavid Ahern 				tbl = fib_get_table(net, cfg->fc_table);
7743bfd8472SDavid Ahern 
7753bfd8472SDavid Ahern 			if (tbl)
7763bfd8472SDavid Ahern 				err = fib_table_lookup(tbl, &fl4, &res,
7771e313678SEric Dumazet 						       FIB_LOOKUP_IGNORE_LINKSTATE |
7781e313678SEric Dumazet 						       FIB_LOOKUP_NOREF);
7794c9bcd11SDavid Ahern 
7804c9bcd11SDavid Ahern 			/* on error or if no table given do full lookup. This
7814c9bcd11SDavid Ahern 			 * is needed for example when nexthops are in the local
7824c9bcd11SDavid Ahern 			 * table rather than the given table
7834c9bcd11SDavid Ahern 			 */
7844c9bcd11SDavid Ahern 			if (!tbl || err) {
7850eeb075fSAndy Gospodarek 				err = fib_lookup(net, &fl4, &res,
7860eeb075fSAndy Gospodarek 						 FIB_LOOKUP_IGNORE_LINKSTATE);
7874c9bcd11SDavid Ahern 			}
7884c9bcd11SDavid Ahern 
789ebc0ffaeSEric Dumazet 			if (err) {
790ebc0ffaeSEric Dumazet 				rcu_read_unlock();
7911da177e4SLinus Torvalds 				return err;
7921da177e4SLinus Torvalds 			}
793ebc0ffaeSEric Dumazet 		}
7941da177e4SLinus Torvalds 		err = -EINVAL;
7951da177e4SLinus Torvalds 		if (res.type != RTN_UNICAST && res.type != RTN_LOCAL)
7961da177e4SLinus Torvalds 			goto out;
7971da177e4SLinus Torvalds 		nh->nh_scope = res.scope;
7981da177e4SLinus Torvalds 		nh->nh_oif = FIB_RES_OIF(res);
7996a31d2a9SEric Dumazet 		nh->nh_dev = dev = FIB_RES_DEV(res);
8006a31d2a9SEric Dumazet 		if (!dev)
8011da177e4SLinus Torvalds 			goto out;
8026a31d2a9SEric Dumazet 		dev_hold(dev);
8038a3d0316SAndy Gospodarek 		if (!netif_carrier_ok(dev))
8048a3d0316SAndy Gospodarek 			nh->nh_flags |= RTNH_F_LINKDOWN;
8058723e1b4SEric Dumazet 		err = (dev->flags & IFF_UP) ? 0 : -ENETDOWN;
8061da177e4SLinus Torvalds 	} else {
8071da177e4SLinus Torvalds 		struct in_device *in_dev;
8081da177e4SLinus Torvalds 
8091da177e4SLinus Torvalds 		if (nh->nh_flags & (RTNH_F_PERVASIVE | RTNH_F_ONLINK))
8101da177e4SLinus Torvalds 			return -EINVAL;
8111da177e4SLinus Torvalds 
8128723e1b4SEric Dumazet 		rcu_read_lock();
8138723e1b4SEric Dumazet 		err = -ENODEV;
81486167a37SDenis V. Lunev 		in_dev = inetdev_by_index(net, nh->nh_oif);
81551456b29SIan Morris 		if (!in_dev)
8168723e1b4SEric Dumazet 			goto out;
8178723e1b4SEric Dumazet 		err = -ENETDOWN;
8188723e1b4SEric Dumazet 		if (!(in_dev->dev->flags & IFF_UP))
8198723e1b4SEric Dumazet 			goto out;
8201da177e4SLinus Torvalds 		nh->nh_dev = in_dev->dev;
8211da177e4SLinus Torvalds 		dev_hold(nh->nh_dev);
8221da177e4SLinus Torvalds 		nh->nh_scope = RT_SCOPE_HOST;
8238a3d0316SAndy Gospodarek 		if (!netif_carrier_ok(nh->nh_dev))
8248a3d0316SAndy Gospodarek 			nh->nh_flags |= RTNH_F_LINKDOWN;
8258723e1b4SEric Dumazet 		err = 0;
8261da177e4SLinus Torvalds 	}
8278723e1b4SEric Dumazet out:
8288723e1b4SEric Dumazet 	rcu_read_unlock();
8298723e1b4SEric Dumazet 	return err;
8301da177e4SLinus Torvalds }
8311da177e4SLinus Torvalds 
83281f7bf6cSAl Viro static inline unsigned int fib_laddr_hashfn(__be32 val)
8331da177e4SLinus Torvalds {
834123b9731SDavid S. Miller 	unsigned int mask = (fib_info_hash_size - 1);
8351da177e4SLinus Torvalds 
8366a31d2a9SEric Dumazet 	return ((__force u32)val ^
8376a31d2a9SEric Dumazet 		((__force u32)val >> 7) ^
8386a31d2a9SEric Dumazet 		((__force u32)val >> 14)) & mask;
8391da177e4SLinus Torvalds }
8401da177e4SLinus Torvalds 
841123b9731SDavid S. Miller static struct hlist_head *fib_info_hash_alloc(int bytes)
8421da177e4SLinus Torvalds {
8431da177e4SLinus Torvalds 	if (bytes <= PAGE_SIZE)
84488f83491SJoonwoo Park 		return kzalloc(bytes, GFP_KERNEL);
8451da177e4SLinus Torvalds 	else
8461da177e4SLinus Torvalds 		return (struct hlist_head *)
8476a31d2a9SEric Dumazet 			__get_free_pages(GFP_KERNEL | __GFP_ZERO,
8486a31d2a9SEric Dumazet 					 get_order(bytes));
8491da177e4SLinus Torvalds }
8501da177e4SLinus Torvalds 
851123b9731SDavid S. Miller static void fib_info_hash_free(struct hlist_head *hash, int bytes)
8521da177e4SLinus Torvalds {
8531da177e4SLinus Torvalds 	if (!hash)
8541da177e4SLinus Torvalds 		return;
8551da177e4SLinus Torvalds 
8561da177e4SLinus Torvalds 	if (bytes <= PAGE_SIZE)
8571da177e4SLinus Torvalds 		kfree(hash);
8581da177e4SLinus Torvalds 	else
8591da177e4SLinus Torvalds 		free_pages((unsigned long) hash, get_order(bytes));
8601da177e4SLinus Torvalds }
8611da177e4SLinus Torvalds 
862123b9731SDavid S. Miller static void fib_info_hash_move(struct hlist_head *new_info_hash,
8631da177e4SLinus Torvalds 			       struct hlist_head *new_laddrhash,
8641da177e4SLinus Torvalds 			       unsigned int new_size)
8651da177e4SLinus Torvalds {
866b7656e7fSDavid S. Miller 	struct hlist_head *old_info_hash, *old_laddrhash;
867123b9731SDavid S. Miller 	unsigned int old_size = fib_info_hash_size;
868b7656e7fSDavid S. Miller 	unsigned int i, bytes;
8691da177e4SLinus Torvalds 
870832b4c5eSStephen Hemminger 	spin_lock_bh(&fib_info_lock);
871b7656e7fSDavid S. Miller 	old_info_hash = fib_info_hash;
872b7656e7fSDavid S. Miller 	old_laddrhash = fib_info_laddrhash;
873123b9731SDavid S. Miller 	fib_info_hash_size = new_size;
8741da177e4SLinus Torvalds 
8751da177e4SLinus Torvalds 	for (i = 0; i < old_size; i++) {
8761da177e4SLinus Torvalds 		struct hlist_head *head = &fib_info_hash[i];
877b67bfe0dSSasha Levin 		struct hlist_node *n;
8781da177e4SLinus Torvalds 		struct fib_info *fi;
8791da177e4SLinus Torvalds 
880b67bfe0dSSasha Levin 		hlist_for_each_entry_safe(fi, n, head, fib_hash) {
8811da177e4SLinus Torvalds 			struct hlist_head *dest;
8821da177e4SLinus Torvalds 			unsigned int new_hash;
8831da177e4SLinus Torvalds 
8841da177e4SLinus Torvalds 			new_hash = fib_info_hashfn(fi);
8851da177e4SLinus Torvalds 			dest = &new_info_hash[new_hash];
8861da177e4SLinus Torvalds 			hlist_add_head(&fi->fib_hash, dest);
8871da177e4SLinus Torvalds 		}
8881da177e4SLinus Torvalds 	}
8891da177e4SLinus Torvalds 	fib_info_hash = new_info_hash;
8901da177e4SLinus Torvalds 
8911da177e4SLinus Torvalds 	for (i = 0; i < old_size; i++) {
8921da177e4SLinus Torvalds 		struct hlist_head *lhead = &fib_info_laddrhash[i];
893b67bfe0dSSasha Levin 		struct hlist_node *n;
8941da177e4SLinus Torvalds 		struct fib_info *fi;
8951da177e4SLinus Torvalds 
896b67bfe0dSSasha Levin 		hlist_for_each_entry_safe(fi, n, lhead, fib_lhash) {
8971da177e4SLinus Torvalds 			struct hlist_head *ldest;
8981da177e4SLinus Torvalds 			unsigned int new_hash;
8991da177e4SLinus Torvalds 
9001da177e4SLinus Torvalds 			new_hash = fib_laddr_hashfn(fi->fib_prefsrc);
9011da177e4SLinus Torvalds 			ldest = &new_laddrhash[new_hash];
9021da177e4SLinus Torvalds 			hlist_add_head(&fi->fib_lhash, ldest);
9031da177e4SLinus Torvalds 		}
9041da177e4SLinus Torvalds 	}
9051da177e4SLinus Torvalds 	fib_info_laddrhash = new_laddrhash;
9061da177e4SLinus Torvalds 
907832b4c5eSStephen Hemminger 	spin_unlock_bh(&fib_info_lock);
908b7656e7fSDavid S. Miller 
909b7656e7fSDavid S. Miller 	bytes = old_size * sizeof(struct hlist_head *);
910123b9731SDavid S. Miller 	fib_info_hash_free(old_info_hash, bytes);
911123b9731SDavid S. Miller 	fib_info_hash_free(old_laddrhash, bytes);
9121da177e4SLinus Torvalds }
9131da177e4SLinus Torvalds 
914436c3b66SDavid S. Miller __be32 fib_info_update_nh_saddr(struct net *net, struct fib_nh *nh)
915436c3b66SDavid S. Miller {
916436c3b66SDavid S. Miller 	nh->nh_saddr = inet_select_addr(nh->nh_dev,
917436c3b66SDavid S. Miller 					nh->nh_gw,
91837e826c5SDavid S. Miller 					nh->nh_parent->fib_scope);
919436c3b66SDavid S. Miller 	nh->nh_saddr_genid = atomic_read(&net->ipv4.dev_addr_genid);
920436c3b66SDavid S. Miller 
921436c3b66SDavid S. Miller 	return nh->nh_saddr;
922436c3b66SDavid S. Miller }
923436c3b66SDavid S. Miller 
924021dd3b8SDavid Ahern static bool fib_valid_prefsrc(struct fib_config *cfg, __be32 fib_prefsrc)
925021dd3b8SDavid Ahern {
926021dd3b8SDavid Ahern 	if (cfg->fc_type != RTN_LOCAL || !cfg->fc_dst ||
927021dd3b8SDavid Ahern 	    fib_prefsrc != cfg->fc_dst) {
9289b8ff518SDavid Ahern 		u32 tb_id = cfg->fc_table;
929e1b8d903SDavid Ahern 		int rc;
930021dd3b8SDavid Ahern 
931021dd3b8SDavid Ahern 		if (tb_id == RT_TABLE_MAIN)
932021dd3b8SDavid Ahern 			tb_id = RT_TABLE_LOCAL;
933021dd3b8SDavid Ahern 
934e1b8d903SDavid Ahern 		rc = inet_addr_type_table(cfg->fc_nlinfo.nl_net,
935e1b8d903SDavid Ahern 					  fib_prefsrc, tb_id);
936e1b8d903SDavid Ahern 
937e1b8d903SDavid Ahern 		if (rc != RTN_LOCAL && tb_id != RT_TABLE_LOCAL) {
938e1b8d903SDavid Ahern 			rc = inet_addr_type_table(cfg->fc_nlinfo.nl_net,
939e1b8d903SDavid Ahern 						  fib_prefsrc, RT_TABLE_LOCAL);
940021dd3b8SDavid Ahern 		}
941e1b8d903SDavid Ahern 
942e1b8d903SDavid Ahern 		if (rc != RTN_LOCAL)
943e1b8d903SDavid Ahern 			return false;
944021dd3b8SDavid Ahern 	}
945021dd3b8SDavid Ahern 	return true;
946021dd3b8SDavid Ahern }
947021dd3b8SDavid Ahern 
9486cf9dfd3SFlorian Westphal static int
9496cf9dfd3SFlorian Westphal fib_convert_metrics(struct fib_info *fi, const struct fib_config *cfg)
9506cf9dfd3SFlorian Westphal {
951c3a8d947SDaniel Borkmann 	bool ecn_ca = false;
9526cf9dfd3SFlorian Westphal 	struct nlattr *nla;
9536cf9dfd3SFlorian Westphal 	int remaining;
9546cf9dfd3SFlorian Westphal 
9556cf9dfd3SFlorian Westphal 	if (!cfg->fc_mx)
9566cf9dfd3SFlorian Westphal 		return 0;
9576cf9dfd3SFlorian Westphal 
9586cf9dfd3SFlorian Westphal 	nla_for_each_attr(nla, cfg->fc_mx, cfg->fc_mx_len, remaining) {
9596cf9dfd3SFlorian Westphal 		int type = nla_type(nla);
9606cf9dfd3SFlorian Westphal 		u32 val;
9616cf9dfd3SFlorian Westphal 
9626cf9dfd3SFlorian Westphal 		if (!type)
9636cf9dfd3SFlorian Westphal 			continue;
9646cf9dfd3SFlorian Westphal 		if (type > RTAX_MAX)
9656cf9dfd3SFlorian Westphal 			return -EINVAL;
9666cf9dfd3SFlorian Westphal 
9676cf9dfd3SFlorian Westphal 		if (type == RTAX_CC_ALGO) {
9686cf9dfd3SFlorian Westphal 			char tmp[TCP_CA_NAME_MAX];
9696cf9dfd3SFlorian Westphal 
9706cf9dfd3SFlorian Westphal 			nla_strlcpy(tmp, nla, sizeof(tmp));
971c3a8d947SDaniel Borkmann 			val = tcp_ca_get_key_by_name(tmp, &ecn_ca);
9726cf9dfd3SFlorian Westphal 			if (val == TCP_CA_UNSPEC)
9736cf9dfd3SFlorian Westphal 				return -EINVAL;
9746cf9dfd3SFlorian Westphal 		} else {
9756cf9dfd3SFlorian Westphal 			val = nla_get_u32(nla);
9766cf9dfd3SFlorian Westphal 		}
9776cf9dfd3SFlorian Westphal 		if (type == RTAX_ADVMSS && val > 65535 - 40)
9786cf9dfd3SFlorian Westphal 			val = 65535 - 40;
9796cf9dfd3SFlorian Westphal 		if (type == RTAX_MTU && val > 65535 - 15)
9806cf9dfd3SFlorian Westphal 			val = 65535 - 15;
981626abd59SPaolo Abeni 		if (type == RTAX_HOPLIMIT && val > 255)
982626abd59SPaolo Abeni 			val = 255;
983b8d3e416SDaniel Borkmann 		if (type == RTAX_FEATURES && (val & ~RTAX_FEATURE_MASK))
984b8d3e416SDaniel Borkmann 			return -EINVAL;
9856cf9dfd3SFlorian Westphal 		fi->fib_metrics[type - 1] = val;
9866cf9dfd3SFlorian Westphal 	}
9876cf9dfd3SFlorian Westphal 
988c3a8d947SDaniel Borkmann 	if (ecn_ca)
989c3a8d947SDaniel Borkmann 		fi->fib_metrics[RTAX_FEATURES - 1] |= DST_FEATURE_ECN_CA;
990c3a8d947SDaniel Borkmann 
9916cf9dfd3SFlorian Westphal 	return 0;
9926cf9dfd3SFlorian Westphal }
9936cf9dfd3SFlorian Westphal 
9944e902c57SThomas Graf struct fib_info *fib_create_info(struct fib_config *cfg)
9951da177e4SLinus Torvalds {
9961da177e4SLinus Torvalds 	int err;
9971da177e4SLinus Torvalds 	struct fib_info *fi = NULL;
9981da177e4SLinus Torvalds 	struct fib_info *ofi;
9991da177e4SLinus Torvalds 	int nhs = 1;
10007462bd74SDenis V. Lunev 	struct net *net = cfg->fc_nlinfo.nl_net;
10011da177e4SLinus Torvalds 
10024c8237cdSDavid S. Miller 	if (cfg->fc_type > RTN_MAX)
10034c8237cdSDavid S. Miller 		goto err_inval;
10044c8237cdSDavid S. Miller 
10051da177e4SLinus Torvalds 	/* Fast check to catch the most weird cases */
10064e902c57SThomas Graf 	if (fib_props[cfg->fc_type].scope > cfg->fc_scope)
10071da177e4SLinus Torvalds 		goto err_inval;
10081da177e4SLinus Torvalds 
100980610229SJulian Anastasov 	if (cfg->fc_flags & (RTNH_F_DEAD | RTNH_F_LINKDOWN))
101080610229SJulian Anastasov 		goto err_inval;
101180610229SJulian Anastasov 
10121da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH
10134e902c57SThomas Graf 	if (cfg->fc_mp) {
10144e902c57SThomas Graf 		nhs = fib_count_nexthops(cfg->fc_mp, cfg->fc_mp_len);
10151da177e4SLinus Torvalds 		if (nhs == 0)
10161da177e4SLinus Torvalds 			goto err_inval;
10171da177e4SLinus Torvalds 	}
10181da177e4SLinus Torvalds #endif
10191da177e4SLinus Torvalds 
10201da177e4SLinus Torvalds 	err = -ENOBUFS;
1021123b9731SDavid S. Miller 	if (fib_info_cnt >= fib_info_hash_size) {
1022123b9731SDavid S. Miller 		unsigned int new_size = fib_info_hash_size << 1;
10231da177e4SLinus Torvalds 		struct hlist_head *new_info_hash;
10241da177e4SLinus Torvalds 		struct hlist_head *new_laddrhash;
10251da177e4SLinus Torvalds 		unsigned int bytes;
10261da177e4SLinus Torvalds 
10271da177e4SLinus Torvalds 		if (!new_size)
1028d94ce9b2SEric Dumazet 			new_size = 16;
10291da177e4SLinus Torvalds 		bytes = new_size * sizeof(struct hlist_head *);
1030123b9731SDavid S. Miller 		new_info_hash = fib_info_hash_alloc(bytes);
1031123b9731SDavid S. Miller 		new_laddrhash = fib_info_hash_alloc(bytes);
10321da177e4SLinus Torvalds 		if (!new_info_hash || !new_laddrhash) {
1033123b9731SDavid S. Miller 			fib_info_hash_free(new_info_hash, bytes);
1034123b9731SDavid S. Miller 			fib_info_hash_free(new_laddrhash, bytes);
103588f83491SJoonwoo Park 		} else
1036123b9731SDavid S. Miller 			fib_info_hash_move(new_info_hash, new_laddrhash, new_size);
10371da177e4SLinus Torvalds 
1038123b9731SDavid S. Miller 		if (!fib_info_hash_size)
10391da177e4SLinus Torvalds 			goto failure;
10401da177e4SLinus Torvalds 	}
10411da177e4SLinus Torvalds 
10420da974f4SPanagiotis Issaris 	fi = kzalloc(sizeof(*fi)+nhs*sizeof(struct fib_nh), GFP_KERNEL);
104351456b29SIan Morris 	if (!fi)
10441da177e4SLinus Torvalds 		goto failure;
1045aeefa1ecSSergey Popovich 	fib_info_cnt++;
1046725d1e1bSDavid S. Miller 	if (cfg->fc_mx) {
10479c150e82SDavid S. Miller 		fi->fib_metrics = kzalloc(sizeof(u32) * RTAX_MAX, GFP_KERNEL);
10489c150e82SDavid S. Miller 		if (!fi->fib_metrics)
10499c150e82SDavid S. Miller 			goto failure;
1050725d1e1bSDavid S. Miller 	} else
1051725d1e1bSDavid S. Miller 		fi->fib_metrics = (u32 *) dst_default_metrics;
10521da177e4SLinus Torvalds 
1053efd7ef1cSEric W. Biederman 	fi->fib_net = net;
10544e902c57SThomas Graf 	fi->fib_protocol = cfg->fc_protocol;
105537e826c5SDavid S. Miller 	fi->fib_scope = cfg->fc_scope;
10564e902c57SThomas Graf 	fi->fib_flags = cfg->fc_flags;
10574e902c57SThomas Graf 	fi->fib_priority = cfg->fc_priority;
10584e902c57SThomas Graf 	fi->fib_prefsrc = cfg->fc_prefsrc;
1059f4ef85bbSEric Dumazet 	fi->fib_type = cfg->fc_type;
1060*5a56a0b3SMark Tomlinson 	fi->fib_tb_id = cfg->fc_table;
10611da177e4SLinus Torvalds 
10621da177e4SLinus Torvalds 	fi->fib_nhs = nhs;
10631da177e4SLinus Torvalds 	change_nexthops(fi) {
106471fceff0SDavid S. Miller 		nexthop_nh->nh_parent = fi;
1065d26b3a7cSEric Dumazet 		nexthop_nh->nh_pcpu_rth_output = alloc_percpu(struct rtable __rcu *);
1066f8a17175SJulian Anastasov 		if (!nexthop_nh->nh_pcpu_rth_output)
1067f8a17175SJulian Anastasov 			goto failure;
10681da177e4SLinus Torvalds 	} endfor_nexthops(fi)
10691da177e4SLinus Torvalds 
10706cf9dfd3SFlorian Westphal 	err = fib_convert_metrics(fi, cfg);
10716cf9dfd3SFlorian Westphal 	if (err)
10726cf9dfd3SFlorian Westphal 		goto failure;
10731da177e4SLinus Torvalds 
10744e902c57SThomas Graf 	if (cfg->fc_mp) {
10751da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH
10764e902c57SThomas Graf 		err = fib_get_nhs(fi, cfg->fc_mp, cfg->fc_mp_len, cfg);
10774e902c57SThomas Graf 		if (err != 0)
10781da177e4SLinus Torvalds 			goto failure;
10794e902c57SThomas Graf 		if (cfg->fc_oif && fi->fib_nh->nh_oif != cfg->fc_oif)
10801da177e4SLinus Torvalds 			goto err_inval;
10814e902c57SThomas Graf 		if (cfg->fc_gw && fi->fib_nh->nh_gw != cfg->fc_gw)
10821da177e4SLinus Torvalds 			goto err_inval;
1083c7066f70SPatrick McHardy #ifdef CONFIG_IP_ROUTE_CLASSID
10844e902c57SThomas Graf 		if (cfg->fc_flow && fi->fib_nh->nh_tclassid != cfg->fc_flow)
10851da177e4SLinus Torvalds 			goto err_inval;
10861da177e4SLinus Torvalds #endif
10871da177e4SLinus Torvalds #else
10881da177e4SLinus Torvalds 		goto err_inval;
10891da177e4SLinus Torvalds #endif
10901da177e4SLinus Torvalds 	} else {
10911da177e4SLinus Torvalds 		struct fib_nh *nh = fi->fib_nh;
10924e902c57SThomas Graf 
1093571e7226SRoopa Prabhu 		if (cfg->fc_encap) {
1094571e7226SRoopa Prabhu 			struct lwtunnel_state *lwtstate;
1095571e7226SRoopa Prabhu 			struct net_device *dev = NULL;
1096571e7226SRoopa Prabhu 
1097571e7226SRoopa Prabhu 			if (cfg->fc_encap_type == LWTUNNEL_ENCAP_NONE)
1098571e7226SRoopa Prabhu 				goto err_inval;
1099571e7226SRoopa Prabhu 			if (cfg->fc_oif)
1100571e7226SRoopa Prabhu 				dev = __dev_get_by_index(net, cfg->fc_oif);
1101571e7226SRoopa Prabhu 			err = lwtunnel_build_state(dev, cfg->fc_encap_type,
1102127eb7cdSTom Herbert 						   cfg->fc_encap, AF_INET, cfg,
1103127eb7cdSTom Herbert 						   &lwtstate);
1104571e7226SRoopa Prabhu 			if (err)
1105571e7226SRoopa Prabhu 				goto failure;
1106571e7226SRoopa Prabhu 
11075a6228a0SNicolas Dichtel 			nh->nh_lwtstate = lwtstate_get(lwtstate);
1108571e7226SRoopa Prabhu 		}
11094e902c57SThomas Graf 		nh->nh_oif = cfg->fc_oif;
11104e902c57SThomas Graf 		nh->nh_gw = cfg->fc_gw;
11114e902c57SThomas Graf 		nh->nh_flags = cfg->fc_flags;
1112c7066f70SPatrick McHardy #ifdef CONFIG_IP_ROUTE_CLASSID
11134e902c57SThomas Graf 		nh->nh_tclassid = cfg->fc_flow;
11147a9bc9b8SDavid S. Miller 		if (nh->nh_tclassid)
1115f4530fa5SDavid S. Miller 			fi->fib_net->ipv4.fib_num_tclassid_users++;
11161da177e4SLinus Torvalds #endif
11171da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH
11181da177e4SLinus Torvalds 		nh->nh_weight = 1;
11191da177e4SLinus Torvalds #endif
11201da177e4SLinus Torvalds 	}
11211da177e4SLinus Torvalds 
11224e902c57SThomas Graf 	if (fib_props[cfg->fc_type].error) {
11234e902c57SThomas Graf 		if (cfg->fc_gw || cfg->fc_oif || cfg->fc_mp)
11241da177e4SLinus Torvalds 			goto err_inval;
11251da177e4SLinus Torvalds 		goto link_it;
11264c8237cdSDavid S. Miller 	} else {
11274c8237cdSDavid S. Miller 		switch (cfg->fc_type) {
11284c8237cdSDavid S. Miller 		case RTN_UNICAST:
11294c8237cdSDavid S. Miller 		case RTN_LOCAL:
11304c8237cdSDavid S. Miller 		case RTN_BROADCAST:
11314c8237cdSDavid S. Miller 		case RTN_ANYCAST:
11324c8237cdSDavid S. Miller 		case RTN_MULTICAST:
11334c8237cdSDavid S. Miller 			break;
11344c8237cdSDavid S. Miller 		default:
11354c8237cdSDavid S. Miller 			goto err_inval;
11364c8237cdSDavid S. Miller 		}
11371da177e4SLinus Torvalds 	}
11381da177e4SLinus Torvalds 
11394e902c57SThomas Graf 	if (cfg->fc_scope > RT_SCOPE_HOST)
11401da177e4SLinus Torvalds 		goto err_inval;
11411da177e4SLinus Torvalds 
11424e902c57SThomas Graf 	if (cfg->fc_scope == RT_SCOPE_HOST) {
11431da177e4SLinus Torvalds 		struct fib_nh *nh = fi->fib_nh;
11441da177e4SLinus Torvalds 
11451da177e4SLinus Torvalds 		/* Local address is added. */
11461da177e4SLinus Torvalds 		if (nhs != 1 || nh->nh_gw)
11471da177e4SLinus Torvalds 			goto err_inval;
11481da177e4SLinus Torvalds 		nh->nh_scope = RT_SCOPE_NOWHERE;
11497462bd74SDenis V. Lunev 		nh->nh_dev = dev_get_by_index(net, fi->fib_nh->nh_oif);
11501da177e4SLinus Torvalds 		err = -ENODEV;
115151456b29SIan Morris 		if (!nh->nh_dev)
11521da177e4SLinus Torvalds 			goto failure;
11531da177e4SLinus Torvalds 	} else {
11548a3d0316SAndy Gospodarek 		int linkdown = 0;
11558a3d0316SAndy Gospodarek 
11561da177e4SLinus Torvalds 		change_nexthops(fi) {
11576a31d2a9SEric Dumazet 			err = fib_check_nh(cfg, fi, nexthop_nh);
11586a31d2a9SEric Dumazet 			if (err != 0)
11591da177e4SLinus Torvalds 				goto failure;
11608a3d0316SAndy Gospodarek 			if (nexthop_nh->nh_flags & RTNH_F_LINKDOWN)
11618a3d0316SAndy Gospodarek 				linkdown++;
11621da177e4SLinus Torvalds 		} endfor_nexthops(fi)
11638a3d0316SAndy Gospodarek 		if (linkdown == fi->fib_nhs)
11648a3d0316SAndy Gospodarek 			fi->fib_flags |= RTNH_F_LINKDOWN;
11651da177e4SLinus Torvalds 	}
11661da177e4SLinus Torvalds 
1167021dd3b8SDavid Ahern 	if (fi->fib_prefsrc && !fib_valid_prefsrc(cfg, fi->fib_prefsrc))
11681da177e4SLinus Torvalds 		goto err_inval;
11691da177e4SLinus Torvalds 
11701fc050a1SDavid S. Miller 	change_nexthops(fi) {
1171436c3b66SDavid S. Miller 		fib_info_update_nh_saddr(net, nexthop_nh);
11720e884c78SPeter Nørlund 		fib_add_weight(fi, nexthop_nh);
11731fc050a1SDavid S. Miller 	} endfor_nexthops(fi)
11741fc050a1SDavid S. Miller 
11750e884c78SPeter Nørlund 	fib_rebalance(fi);
11760e884c78SPeter Nørlund 
11771da177e4SLinus Torvalds link_it:
11786a31d2a9SEric Dumazet 	ofi = fib_find_info(fi);
11796a31d2a9SEric Dumazet 	if (ofi) {
11801da177e4SLinus Torvalds 		fi->fib_dead = 1;
11811da177e4SLinus Torvalds 		free_fib_info(fi);
11821da177e4SLinus Torvalds 		ofi->fib_treeref++;
11831da177e4SLinus Torvalds 		return ofi;
11841da177e4SLinus Torvalds 	}
11851da177e4SLinus Torvalds 
11861da177e4SLinus Torvalds 	fi->fib_treeref++;
11871da177e4SLinus Torvalds 	atomic_inc(&fi->fib_clntref);
1188832b4c5eSStephen Hemminger 	spin_lock_bh(&fib_info_lock);
11891da177e4SLinus Torvalds 	hlist_add_head(&fi->fib_hash,
11901da177e4SLinus Torvalds 		       &fib_info_hash[fib_info_hashfn(fi)]);
11911da177e4SLinus Torvalds 	if (fi->fib_prefsrc) {
11921da177e4SLinus Torvalds 		struct hlist_head *head;
11931da177e4SLinus Torvalds 
11941da177e4SLinus Torvalds 		head = &fib_info_laddrhash[fib_laddr_hashfn(fi->fib_prefsrc)];
11951da177e4SLinus Torvalds 		hlist_add_head(&fi->fib_lhash, head);
11961da177e4SLinus Torvalds 	}
11971da177e4SLinus Torvalds 	change_nexthops(fi) {
11981da177e4SLinus Torvalds 		struct hlist_head *head;
11991da177e4SLinus Torvalds 		unsigned int hash;
12001da177e4SLinus Torvalds 
120171fceff0SDavid S. Miller 		if (!nexthop_nh->nh_dev)
12021da177e4SLinus Torvalds 			continue;
120371fceff0SDavid S. Miller 		hash = fib_devindex_hashfn(nexthop_nh->nh_dev->ifindex);
12041da177e4SLinus Torvalds 		head = &fib_info_devhash[hash];
120571fceff0SDavid S. Miller 		hlist_add_head(&nexthop_nh->nh_hash, head);
12061da177e4SLinus Torvalds 	} endfor_nexthops(fi)
1207832b4c5eSStephen Hemminger 	spin_unlock_bh(&fib_info_lock);
12081da177e4SLinus Torvalds 	return fi;
12091da177e4SLinus Torvalds 
12101da177e4SLinus Torvalds err_inval:
12111da177e4SLinus Torvalds 	err = -EINVAL;
12121da177e4SLinus Torvalds 
12131da177e4SLinus Torvalds failure:
12141da177e4SLinus Torvalds 	if (fi) {
12151da177e4SLinus Torvalds 		fi->fib_dead = 1;
12161da177e4SLinus Torvalds 		free_fib_info(fi);
12171da177e4SLinus Torvalds 	}
12184e902c57SThomas Graf 
12194e902c57SThomas Graf 	return ERR_PTR(err);
12201da177e4SLinus Torvalds }
12211da177e4SLinus Torvalds 
122215e47304SEric W. Biederman int fib_dump_info(struct sk_buff *skb, u32 portid, u32 seq, int event,
122337e826c5SDavid S. Miller 		  u32 tb_id, u8 type, __be32 dst, int dst_len, u8 tos,
1224b6544c0bSJamal Hadi Salim 		  struct fib_info *fi, unsigned int flags)
12251da177e4SLinus Torvalds {
12261da177e4SLinus Torvalds 	struct nlmsghdr *nlh;
1227be403ea1SThomas Graf 	struct rtmsg *rtm;
12281da177e4SLinus Torvalds 
122915e47304SEric W. Biederman 	nlh = nlmsg_put(skb, portid, seq, event, sizeof(*rtm), flags);
123051456b29SIan Morris 	if (!nlh)
123126932566SPatrick McHardy 		return -EMSGSIZE;
1232be403ea1SThomas Graf 
1233be403ea1SThomas Graf 	rtm = nlmsg_data(nlh);
12341da177e4SLinus Torvalds 	rtm->rtm_family = AF_INET;
12351da177e4SLinus Torvalds 	rtm->rtm_dst_len = dst_len;
12361da177e4SLinus Torvalds 	rtm->rtm_src_len = 0;
12371da177e4SLinus Torvalds 	rtm->rtm_tos = tos;
1238709772e6SKrzysztof Piotr Oledzki 	if (tb_id < 256)
12391da177e4SLinus Torvalds 		rtm->rtm_table = tb_id;
1240709772e6SKrzysztof Piotr Oledzki 	else
1241709772e6SKrzysztof Piotr Oledzki 		rtm->rtm_table = RT_TABLE_COMPAT;
1242f3756b79SDavid S. Miller 	if (nla_put_u32(skb, RTA_TABLE, tb_id))
1243f3756b79SDavid S. Miller 		goto nla_put_failure;
12441da177e4SLinus Torvalds 	rtm->rtm_type = type;
12451da177e4SLinus Torvalds 	rtm->rtm_flags = fi->fib_flags;
124637e826c5SDavid S. Miller 	rtm->rtm_scope = fi->fib_scope;
12471da177e4SLinus Torvalds 	rtm->rtm_protocol = fi->fib_protocol;
1248be403ea1SThomas Graf 
1249f3756b79SDavid S. Miller 	if (rtm->rtm_dst_len &&
1250930345eaSJiri Benc 	    nla_put_in_addr(skb, RTA_DST, dst))
1251f3756b79SDavid S. Miller 		goto nla_put_failure;
1252f3756b79SDavid S. Miller 	if (fi->fib_priority &&
1253f3756b79SDavid S. Miller 	    nla_put_u32(skb, RTA_PRIORITY, fi->fib_priority))
1254f3756b79SDavid S. Miller 		goto nla_put_failure;
12551da177e4SLinus Torvalds 	if (rtnetlink_put_metrics(skb, fi->fib_metrics) < 0)
1256be403ea1SThomas Graf 		goto nla_put_failure;
1257be403ea1SThomas Graf 
1258f3756b79SDavid S. Miller 	if (fi->fib_prefsrc &&
1259930345eaSJiri Benc 	    nla_put_in_addr(skb, RTA_PREFSRC, fi->fib_prefsrc))
1260f3756b79SDavid S. Miller 		goto nla_put_failure;
12611da177e4SLinus Torvalds 	if (fi->fib_nhs == 1) {
12620eeb075fSAndy Gospodarek 		struct in_device *in_dev;
12630eeb075fSAndy Gospodarek 
1264f3756b79SDavid S. Miller 		if (fi->fib_nh->nh_gw &&
1265930345eaSJiri Benc 		    nla_put_in_addr(skb, RTA_GATEWAY, fi->fib_nh->nh_gw))
1266f3756b79SDavid S. Miller 			goto nla_put_failure;
1267f3756b79SDavid S. Miller 		if (fi->fib_nh->nh_oif &&
1268f3756b79SDavid S. Miller 		    nla_put_u32(skb, RTA_OIF, fi->fib_nh->nh_oif))
1269f3756b79SDavid S. Miller 			goto nla_put_failure;
12700eeb075fSAndy Gospodarek 		if (fi->fib_nh->nh_flags & RTNH_F_LINKDOWN) {
127196ac5cc9SAndy Gospodarek 			in_dev = __in_dev_get_rtnl(fi->fib_nh->nh_dev);
12720eeb075fSAndy Gospodarek 			if (in_dev &&
12730eeb075fSAndy Gospodarek 			    IN_DEV_IGNORE_ROUTES_WITH_LINKDOWN(in_dev))
12740eeb075fSAndy Gospodarek 				rtm->rtm_flags |= RTNH_F_DEAD;
12750eeb075fSAndy Gospodarek 		}
1276c7066f70SPatrick McHardy #ifdef CONFIG_IP_ROUTE_CLASSID
1277f3756b79SDavid S. Miller 		if (fi->fib_nh[0].nh_tclassid &&
1278f3756b79SDavid S. Miller 		    nla_put_u32(skb, RTA_FLOW, fi->fib_nh[0].nh_tclassid))
1279f3756b79SDavid S. Miller 			goto nla_put_failure;
12808265abc0SPatrick McHardy #endif
1281571e7226SRoopa Prabhu 		if (fi->fib_nh->nh_lwtstate)
1282571e7226SRoopa Prabhu 			lwtunnel_fill_encap(skb, fi->fib_nh->nh_lwtstate);
12831da177e4SLinus Torvalds 	}
12841da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH
12851da177e4SLinus Torvalds 	if (fi->fib_nhs > 1) {
1286be403ea1SThomas Graf 		struct rtnexthop *rtnh;
1287be403ea1SThomas Graf 		struct nlattr *mp;
1288be403ea1SThomas Graf 
1289be403ea1SThomas Graf 		mp = nla_nest_start(skb, RTA_MULTIPATH);
129051456b29SIan Morris 		if (!mp)
1291be403ea1SThomas Graf 			goto nla_put_failure;
12921da177e4SLinus Torvalds 
12931da177e4SLinus Torvalds 		for_nexthops(fi) {
12940eeb075fSAndy Gospodarek 			struct in_device *in_dev;
12950eeb075fSAndy Gospodarek 
1296be403ea1SThomas Graf 			rtnh = nla_reserve_nohdr(skb, sizeof(*rtnh));
129751456b29SIan Morris 			if (!rtnh)
1298be403ea1SThomas Graf 				goto nla_put_failure;
1299be403ea1SThomas Graf 
1300be403ea1SThomas Graf 			rtnh->rtnh_flags = nh->nh_flags & 0xFF;
13010eeb075fSAndy Gospodarek 			if (nh->nh_flags & RTNH_F_LINKDOWN) {
130296ac5cc9SAndy Gospodarek 				in_dev = __in_dev_get_rtnl(nh->nh_dev);
13030eeb075fSAndy Gospodarek 				if (in_dev &&
13040eeb075fSAndy Gospodarek 				    IN_DEV_IGNORE_ROUTES_WITH_LINKDOWN(in_dev))
13050eeb075fSAndy Gospodarek 					rtnh->rtnh_flags |= RTNH_F_DEAD;
13060eeb075fSAndy Gospodarek 			}
1307be403ea1SThomas Graf 			rtnh->rtnh_hops = nh->nh_weight - 1;
1308be403ea1SThomas Graf 			rtnh->rtnh_ifindex = nh->nh_oif;
1309be403ea1SThomas Graf 
1310f3756b79SDavid S. Miller 			if (nh->nh_gw &&
1311930345eaSJiri Benc 			    nla_put_in_addr(skb, RTA_GATEWAY, nh->nh_gw))
1312f3756b79SDavid S. Miller 				goto nla_put_failure;
1313c7066f70SPatrick McHardy #ifdef CONFIG_IP_ROUTE_CLASSID
1314f3756b79SDavid S. Miller 			if (nh->nh_tclassid &&
1315f3756b79SDavid S. Miller 			    nla_put_u32(skb, RTA_FLOW, nh->nh_tclassid))
1316f3756b79SDavid S. Miller 				goto nla_put_failure;
13178265abc0SPatrick McHardy #endif
1318571e7226SRoopa Prabhu 			if (nh->nh_lwtstate)
1319571e7226SRoopa Prabhu 				lwtunnel_fill_encap(skb, nh->nh_lwtstate);
1320be403ea1SThomas Graf 			/* length of rtnetlink header + attributes */
1321be403ea1SThomas Graf 			rtnh->rtnh_len = nlmsg_get_pos(skb) - (void *) rtnh;
13221da177e4SLinus Torvalds 		} endfor_nexthops(fi);
1323be403ea1SThomas Graf 
1324be403ea1SThomas Graf 		nla_nest_end(skb, mp);
13251da177e4SLinus Torvalds 	}
13261da177e4SLinus Torvalds #endif
1327053c095aSJohannes Berg 	nlmsg_end(skb, nlh);
1328053c095aSJohannes Berg 	return 0;
13291da177e4SLinus Torvalds 
1330be403ea1SThomas Graf nla_put_failure:
133126932566SPatrick McHardy 	nlmsg_cancel(skb, nlh);
133226932566SPatrick McHardy 	return -EMSGSIZE;
13331da177e4SLinus Torvalds }
13341da177e4SLinus Torvalds 
13351da177e4SLinus Torvalds /*
13366a31d2a9SEric Dumazet  * Update FIB if:
13376a31d2a9SEric Dumazet  * - local address disappeared -> we must delete all the entries
13386a31d2a9SEric Dumazet  *   referring to it.
13396a31d2a9SEric Dumazet  * - device went down -> we must shutdown all nexthops going via it.
13401da177e4SLinus Torvalds  */
1341*5a56a0b3SMark Tomlinson int fib_sync_down_addr(struct net_device *dev, __be32 local)
13421da177e4SLinus Torvalds {
13431da177e4SLinus Torvalds 	int ret = 0;
13441da177e4SLinus Torvalds 	unsigned int hash = fib_laddr_hashfn(local);
13451da177e4SLinus Torvalds 	struct hlist_head *head = &fib_info_laddrhash[hash];
1346*5a56a0b3SMark Tomlinson 	struct net *net = dev_net(dev);
1347*5a56a0b3SMark Tomlinson 	int tb_id = l3mdev_fib_table(dev);
13481da177e4SLinus Torvalds 	struct fib_info *fi;
13491da177e4SLinus Torvalds 
135051456b29SIan Morris 	if (!fib_info_laddrhash || local == 0)
135185326fa5SDenis V. Lunev 		return 0;
135285326fa5SDenis V. Lunev 
1353b67bfe0dSSasha Levin 	hlist_for_each_entry(fi, head, fib_lhash) {
1354*5a56a0b3SMark Tomlinson 		if (!net_eq(fi->fib_net, net) ||
1355*5a56a0b3SMark Tomlinson 		    fi->fib_tb_id != tb_id)
13564814bdbdSDenis V. Lunev 			continue;
13571da177e4SLinus Torvalds 		if (fi->fib_prefsrc == local) {
13581da177e4SLinus Torvalds 			fi->fib_flags |= RTNH_F_DEAD;
13591da177e4SLinus Torvalds 			ret++;
13601da177e4SLinus Torvalds 		}
13611da177e4SLinus Torvalds 	}
136285326fa5SDenis V. Lunev 	return ret;
13631da177e4SLinus Torvalds }
13641da177e4SLinus Torvalds 
13654f823defSJulian Anastasov /* Event              force Flags           Description
13664f823defSJulian Anastasov  * NETDEV_CHANGE      0     LINKDOWN        Carrier OFF, not for scope host
13674f823defSJulian Anastasov  * NETDEV_DOWN        0     LINKDOWN|DEAD   Link down, not for scope host
13684f823defSJulian Anastasov  * NETDEV_DOWN        1     LINKDOWN|DEAD   Last address removed
13694f823defSJulian Anastasov  * NETDEV_UNREGISTER  1     LINKDOWN|DEAD   Device removed
13704f823defSJulian Anastasov  */
13714f823defSJulian Anastasov int fib_sync_down_dev(struct net_device *dev, unsigned long event, bool force)
137285326fa5SDenis V. Lunev {
137385326fa5SDenis V. Lunev 	int ret = 0;
137485326fa5SDenis V. Lunev 	int scope = RT_SCOPE_NOWHERE;
13751da177e4SLinus Torvalds 	struct fib_info *prev_fi = NULL;
13761da177e4SLinus Torvalds 	unsigned int hash = fib_devindex_hashfn(dev->ifindex);
13771da177e4SLinus Torvalds 	struct hlist_head *head = &fib_info_devhash[hash];
13781da177e4SLinus Torvalds 	struct fib_nh *nh;
13791da177e4SLinus Torvalds 
13804f823defSJulian Anastasov 	if (force)
138185326fa5SDenis V. Lunev 		scope = -1;
138285326fa5SDenis V. Lunev 
1383b67bfe0dSSasha Levin 	hlist_for_each_entry(nh, head, nh_hash) {
13841da177e4SLinus Torvalds 		struct fib_info *fi = nh->nh_parent;
13851da177e4SLinus Torvalds 		int dead;
13861da177e4SLinus Torvalds 
13871da177e4SLinus Torvalds 		BUG_ON(!fi->fib_nhs);
13881da177e4SLinus Torvalds 		if (nh->nh_dev != dev || fi == prev_fi)
13891da177e4SLinus Torvalds 			continue;
13901da177e4SLinus Torvalds 		prev_fi = fi;
13911da177e4SLinus Torvalds 		dead = 0;
13921da177e4SLinus Torvalds 		change_nexthops(fi) {
139371fceff0SDavid S. Miller 			if (nexthop_nh->nh_flags & RTNH_F_DEAD)
13941da177e4SLinus Torvalds 				dead++;
139571fceff0SDavid S. Miller 			else if (nexthop_nh->nh_dev == dev &&
139671fceff0SDavid S. Miller 				 nexthop_nh->nh_scope != scope) {
13978a3d0316SAndy Gospodarek 				switch (event) {
13988a3d0316SAndy Gospodarek 				case NETDEV_DOWN:
13998a3d0316SAndy Gospodarek 				case NETDEV_UNREGISTER:
140071fceff0SDavid S. Miller 					nexthop_nh->nh_flags |= RTNH_F_DEAD;
14018a3d0316SAndy Gospodarek 					/* fall through */
14028a3d0316SAndy Gospodarek 				case NETDEV_CHANGE:
14038a3d0316SAndy Gospodarek 					nexthop_nh->nh_flags |= RTNH_F_LINKDOWN;
14048a3d0316SAndy Gospodarek 					break;
14058a3d0316SAndy Gospodarek 				}
14061da177e4SLinus Torvalds 				dead++;
14071da177e4SLinus Torvalds 			}
14081da177e4SLinus Torvalds #ifdef CONFIG_IP_ROUTE_MULTIPATH
14098a3d0316SAndy Gospodarek 			if (event == NETDEV_UNREGISTER &&
14108a3d0316SAndy Gospodarek 			    nexthop_nh->nh_dev == dev) {
14111da177e4SLinus Torvalds 				dead = fi->fib_nhs;
14121da177e4SLinus Torvalds 				break;
14131da177e4SLinus Torvalds 			}
14141da177e4SLinus Torvalds #endif
14151da177e4SLinus Torvalds 		} endfor_nexthops(fi)
14161da177e4SLinus Torvalds 		if (dead == fi->fib_nhs) {
14178a3d0316SAndy Gospodarek 			switch (event) {
14188a3d0316SAndy Gospodarek 			case NETDEV_DOWN:
14198a3d0316SAndy Gospodarek 			case NETDEV_UNREGISTER:
14201da177e4SLinus Torvalds 				fi->fib_flags |= RTNH_F_DEAD;
14218a3d0316SAndy Gospodarek 				/* fall through */
14228a3d0316SAndy Gospodarek 			case NETDEV_CHANGE:
14238a3d0316SAndy Gospodarek 				fi->fib_flags |= RTNH_F_LINKDOWN;
14248a3d0316SAndy Gospodarek 				break;
14258a3d0316SAndy Gospodarek 			}
14261da177e4SLinus Torvalds 			ret++;
14271da177e4SLinus Torvalds 		}
14280e884c78SPeter Nørlund 
14290e884c78SPeter Nørlund 		fib_rebalance(fi);
14301da177e4SLinus Torvalds 	}
14311da177e4SLinus Torvalds 
14321da177e4SLinus Torvalds 	return ret;
14331da177e4SLinus Torvalds }
14341da177e4SLinus Torvalds 
14350c838ff1SDavid S. Miller /* Must be invoked inside of an RCU protected region.  */
14362392debcSJulian Anastasov void fib_select_default(const struct flowi4 *flp, struct fib_result *res)
14370c838ff1SDavid S. Miller {
14380c838ff1SDavid S. Miller 	struct fib_info *fi = NULL, *last_resort = NULL;
143956315f9eSAlexander Duyck 	struct hlist_head *fa_head = res->fa_head;
14400c838ff1SDavid S. Miller 	struct fib_table *tb = res->table;
144118a912e9SJulian Anastasov 	u8 slen = 32 - res->prefixlen;
14420c838ff1SDavid S. Miller 	int order = -1, last_idx = -1;
14432392debcSJulian Anastasov 	struct fib_alias *fa, *fa1 = NULL;
14442392debcSJulian Anastasov 	u32 last_prio = res->fi->fib_priority;
14452392debcSJulian Anastasov 	u8 last_tos = 0;
14460c838ff1SDavid S. Miller 
144756315f9eSAlexander Duyck 	hlist_for_each_entry_rcu(fa, fa_head, fa_list) {
14480c838ff1SDavid S. Miller 		struct fib_info *next_fi = fa->fa_info;
14490c838ff1SDavid S. Miller 
145018a912e9SJulian Anastasov 		if (fa->fa_slen != slen)
145118a912e9SJulian Anastasov 			continue;
14522392debcSJulian Anastasov 		if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
14532392debcSJulian Anastasov 			continue;
145418a912e9SJulian Anastasov 		if (fa->tb_id != tb->tb_id)
145518a912e9SJulian Anastasov 			continue;
14562392debcSJulian Anastasov 		if (next_fi->fib_priority > last_prio &&
14572392debcSJulian Anastasov 		    fa->fa_tos == last_tos) {
14582392debcSJulian Anastasov 			if (last_tos)
14592392debcSJulian Anastasov 				continue;
14602392debcSJulian Anastasov 			break;
14612392debcSJulian Anastasov 		}
14622392debcSJulian Anastasov 		if (next_fi->fib_flags & RTNH_F_DEAD)
14632392debcSJulian Anastasov 			continue;
14642392debcSJulian Anastasov 		last_tos = fa->fa_tos;
14652392debcSJulian Anastasov 		last_prio = next_fi->fib_priority;
14662392debcSJulian Anastasov 
146737e826c5SDavid S. Miller 		if (next_fi->fib_scope != res->scope ||
14680c838ff1SDavid S. Miller 		    fa->fa_type != RTN_UNICAST)
14690c838ff1SDavid S. Miller 			continue;
14700c838ff1SDavid S. Miller 		if (!next_fi->fib_nh[0].nh_gw ||
14710c838ff1SDavid S. Miller 		    next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
14720c838ff1SDavid S. Miller 			continue;
14730c838ff1SDavid S. Miller 
14740c838ff1SDavid S. Miller 		fib_alias_accessed(fa);
14750c838ff1SDavid S. Miller 
147651456b29SIan Morris 		if (!fi) {
14770c838ff1SDavid S. Miller 			if (next_fi != res->fi)
14780c838ff1SDavid S. Miller 				break;
14792392debcSJulian Anastasov 			fa1 = fa;
14800c838ff1SDavid S. Miller 		} else if (!fib_detect_death(fi, order, &last_resort,
14812392debcSJulian Anastasov 					     &last_idx, fa1->fa_default)) {
14820c838ff1SDavid S. Miller 			fib_result_assign(res, fi);
14832392debcSJulian Anastasov 			fa1->fa_default = order;
14840c838ff1SDavid S. Miller 			goto out;
14850c838ff1SDavid S. Miller 		}
14860c838ff1SDavid S. Miller 		fi = next_fi;
14870c838ff1SDavid S. Miller 		order++;
14880c838ff1SDavid S. Miller 	}
14890c838ff1SDavid S. Miller 
149051456b29SIan Morris 	if (order <= 0 || !fi) {
14912392debcSJulian Anastasov 		if (fa1)
14922392debcSJulian Anastasov 			fa1->fa_default = -1;
14930c838ff1SDavid S. Miller 		goto out;
14940c838ff1SDavid S. Miller 	}
14950c838ff1SDavid S. Miller 
14960c838ff1SDavid S. Miller 	if (!fib_detect_death(fi, order, &last_resort, &last_idx,
14972392debcSJulian Anastasov 			      fa1->fa_default)) {
14980c838ff1SDavid S. Miller 		fib_result_assign(res, fi);
14992392debcSJulian Anastasov 		fa1->fa_default = order;
15000c838ff1SDavid S. Miller 		goto out;
15010c838ff1SDavid S. Miller 	}
15020c838ff1SDavid S. Miller 
15030c838ff1SDavid S. Miller 	if (last_idx >= 0)
15040c838ff1SDavid S. Miller 		fib_result_assign(res, last_resort);
15052392debcSJulian Anastasov 	fa1->fa_default = last_idx;
15060c838ff1SDavid S. Miller out:
150731d40937SEric Dumazet 	return;
15080c838ff1SDavid S. Miller }
15090c838ff1SDavid S. Miller 
15101da177e4SLinus Torvalds /*
15116a31d2a9SEric Dumazet  * Dead device goes up. We wake up dead nexthops.
15126a31d2a9SEric Dumazet  * It takes sense only on multipath routes.
15131da177e4SLinus Torvalds  */
15148a3d0316SAndy Gospodarek int fib_sync_up(struct net_device *dev, unsigned int nh_flags)
15151da177e4SLinus Torvalds {
15161da177e4SLinus Torvalds 	struct fib_info *prev_fi;
15171da177e4SLinus Torvalds 	unsigned int hash;
15181da177e4SLinus Torvalds 	struct hlist_head *head;
15191da177e4SLinus Torvalds 	struct fib_nh *nh;
15201da177e4SLinus Torvalds 	int ret;
15211da177e4SLinus Torvalds 
15221da177e4SLinus Torvalds 	if (!(dev->flags & IFF_UP))
15231da177e4SLinus Torvalds 		return 0;
15241da177e4SLinus Torvalds 
1525c9b3292eSJulian Anastasov 	if (nh_flags & RTNH_F_DEAD) {
1526c9b3292eSJulian Anastasov 		unsigned int flags = dev_get_flags(dev);
1527c9b3292eSJulian Anastasov 
1528c9b3292eSJulian Anastasov 		if (flags & (IFF_RUNNING | IFF_LOWER_UP))
1529c9b3292eSJulian Anastasov 			nh_flags |= RTNH_F_LINKDOWN;
1530c9b3292eSJulian Anastasov 	}
1531c9b3292eSJulian Anastasov 
15321da177e4SLinus Torvalds 	prev_fi = NULL;
15331da177e4SLinus Torvalds 	hash = fib_devindex_hashfn(dev->ifindex);
15341da177e4SLinus Torvalds 	head = &fib_info_devhash[hash];
15351da177e4SLinus Torvalds 	ret = 0;
15361da177e4SLinus Torvalds 
1537b67bfe0dSSasha Levin 	hlist_for_each_entry(nh, head, nh_hash) {
15381da177e4SLinus Torvalds 		struct fib_info *fi = nh->nh_parent;
15391da177e4SLinus Torvalds 		int alive;
15401da177e4SLinus Torvalds 
15411da177e4SLinus Torvalds 		BUG_ON(!fi->fib_nhs);
15421da177e4SLinus Torvalds 		if (nh->nh_dev != dev || fi == prev_fi)
15431da177e4SLinus Torvalds 			continue;
15441da177e4SLinus Torvalds 
15451da177e4SLinus Torvalds 		prev_fi = fi;
15461da177e4SLinus Torvalds 		alive = 0;
15471da177e4SLinus Torvalds 		change_nexthops(fi) {
15488a3d0316SAndy Gospodarek 			if (!(nexthop_nh->nh_flags & nh_flags)) {
15491da177e4SLinus Torvalds 				alive++;
15501da177e4SLinus Torvalds 				continue;
15511da177e4SLinus Torvalds 			}
155251456b29SIan Morris 			if (!nexthop_nh->nh_dev ||
155371fceff0SDavid S. Miller 			    !(nexthop_nh->nh_dev->flags & IFF_UP))
15541da177e4SLinus Torvalds 				continue;
155571fceff0SDavid S. Miller 			if (nexthop_nh->nh_dev != dev ||
155671fceff0SDavid S. Miller 			    !__in_dev_get_rtnl(dev))
15571da177e4SLinus Torvalds 				continue;
15581da177e4SLinus Torvalds 			alive++;
15598a3d0316SAndy Gospodarek 			nexthop_nh->nh_flags &= ~nh_flags;
15601da177e4SLinus Torvalds 		} endfor_nexthops(fi)
15611da177e4SLinus Torvalds 
15621da177e4SLinus Torvalds 		if (alive > 0) {
15638a3d0316SAndy Gospodarek 			fi->fib_flags &= ~nh_flags;
15641da177e4SLinus Torvalds 			ret++;
15651da177e4SLinus Torvalds 		}
15660e884c78SPeter Nørlund 
15670e884c78SPeter Nørlund 		fib_rebalance(fi);
15681da177e4SLinus Torvalds 	}
15691da177e4SLinus Torvalds 
15701da177e4SLinus Torvalds 	return ret;
15711da177e4SLinus Torvalds }
15721da177e4SLinus Torvalds 
15738a3d0316SAndy Gospodarek #ifdef CONFIG_IP_ROUTE_MULTIPATH
1574a6db4494SDavid Ahern static bool fib_good_nh(const struct fib_nh *nh)
1575a6db4494SDavid Ahern {
1576a6db4494SDavid Ahern 	int state = NUD_REACHABLE;
1577a6db4494SDavid Ahern 
1578a6db4494SDavid Ahern 	if (nh->nh_scope == RT_SCOPE_LINK) {
1579a6db4494SDavid Ahern 		struct neighbour *n;
1580a6db4494SDavid Ahern 
1581a6db4494SDavid Ahern 		rcu_read_lock_bh();
1582a6db4494SDavid Ahern 
1583a6db4494SDavid Ahern 		n = __ipv4_neigh_lookup_noref(nh->nh_dev, nh->nh_gw);
1584a6db4494SDavid Ahern 		if (n)
1585a6db4494SDavid Ahern 			state = n->nud_state;
1586a6db4494SDavid Ahern 
1587a6db4494SDavid Ahern 		rcu_read_unlock_bh();
1588a6db4494SDavid Ahern 	}
1589a6db4494SDavid Ahern 
1590a6db4494SDavid Ahern 	return !!(state & NUD_VALID);
1591a6db4494SDavid Ahern }
15928a3d0316SAndy Gospodarek 
15930e884c78SPeter Nørlund void fib_select_multipath(struct fib_result *res, int hash)
15941da177e4SLinus Torvalds {
15951da177e4SLinus Torvalds 	struct fib_info *fi = res->fi;
1596a6db4494SDavid Ahern 	struct net *net = fi->fib_net;
1597a6db4494SDavid Ahern 	bool first = false;
15981da177e4SLinus Torvalds 
15990e884c78SPeter Nørlund 	for_nexthops(fi) {
16000e884c78SPeter Nørlund 		if (hash > atomic_read(&nh->nh_upper_bound))
16010eeb075fSAndy Gospodarek 			continue;
16021da177e4SLinus Torvalds 
1603a6db4494SDavid Ahern 		if (!net->ipv4.sysctl_fib_multipath_use_neigh ||
1604a6db4494SDavid Ahern 		    fib_good_nh(nh)) {
16051da177e4SLinus Torvalds 			res->nh_sel = nhsel;
16061da177e4SLinus Torvalds 			return;
1607a6db4494SDavid Ahern 		}
1608a6db4494SDavid Ahern 		if (!first) {
1609a6db4494SDavid Ahern 			res->nh_sel = nhsel;
1610a6db4494SDavid Ahern 			first = true;
1611a6db4494SDavid Ahern 		}
16121da177e4SLinus Torvalds 	} endfor_nexthops(fi);
16131da177e4SLinus Torvalds }
16141da177e4SLinus Torvalds #endif
16153ce58d84SDavid Ahern 
16163ce58d84SDavid Ahern void fib_select_path(struct net *net, struct fib_result *res,
16173ce58d84SDavid Ahern 		     struct flowi4 *fl4, int mp_hash)
16183ce58d84SDavid Ahern {
16193ce58d84SDavid Ahern #ifdef CONFIG_IP_ROUTE_MULTIPATH
16203ce58d84SDavid Ahern 	if (res->fi->fib_nhs > 1 && fl4->flowi4_oif == 0) {
16213ce58d84SDavid Ahern 		if (mp_hash < 0)
16229920e48bSPaolo Abeni 			mp_hash = get_hash_from_flowi4(fl4) >> 1;
16239920e48bSPaolo Abeni 
16243ce58d84SDavid Ahern 		fib_select_multipath(res, mp_hash);
16253ce58d84SDavid Ahern 	}
16263ce58d84SDavid Ahern 	else
16273ce58d84SDavid Ahern #endif
16283ce58d84SDavid Ahern 	if (!res->prefixlen &&
16293ce58d84SDavid Ahern 	    res->table->tb_num_default > 1 &&
16303ce58d84SDavid Ahern 	    res->type == RTN_UNICAST && !fl4->flowi4_oif)
16313ce58d84SDavid Ahern 		fib_select_default(fl4, res);
16323ce58d84SDavid Ahern 
16333ce58d84SDavid Ahern 	if (!fl4->saddr)
16343ce58d84SDavid Ahern 		fl4->saddr = FIB_RES_PREFSRC(net, *res);
16353ce58d84SDavid Ahern }
16363ce58d84SDavid Ahern EXPORT_SYMBOL_GPL(fib_select_path);
1637