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