~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/net/ipv4/fib_semantics.c

Version: ~ [ linux-5.16-rc3 ] ~ [ linux-5.15.5 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.82 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.162 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.218 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.256 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.291 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.293 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp