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