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