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