3dad12ee76c35a76b851a433108a5be1aa30aa44
[linux-2.6.git] / net / ipv4 / fib_semantics.c
1 /*
2  * INET         An implementation of the TCP/IP protocol suite for the LINUX
3  *              operating system.  INET is implemented using the  BSD Socket
4  *              interface as the means of communication with the user level.
5  *
6  *              IPv4 Forwarding Information Base: semantics.
7  *
8  * Version:     $Id: fib_semantics.c,v 1.19 2002/01/12 07:54:56 davem Exp $
9  *
10  * Authors:     Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
11  *
12  *              This program is free software; you can redistribute it and/or
13  *              modify it under the terms of the GNU General Public License
14  *              as published by the Free Software Foundation; either version
15  *              2 of the License, or (at your option) any later version.
16  */
17
18 #include <asm/uaccess.h>
19 #include <asm/system.h>
20 #include <linux/bitops.h>
21 #include <linux/types.h>
22 #include <linux/kernel.h>
23 #include <linux/jiffies.h>
24 #include <linux/mm.h>
25 #include <linux/string.h>
26 #include <linux/socket.h>
27 #include <linux/sockios.h>
28 #include <linux/errno.h>
29 #include <linux/in.h>
30 #include <linux/inet.h>
31 #include <linux/inetdevice.h>
32 #include <linux/netdevice.h>
33 #include <linux/if_arp.h>
34 #include <linux/proc_fs.h>
35 #include <linux/skbuff.h>
36 #include <linux/init.h>
37
38 #include <net/arp.h>
39 #include <net/ip.h>
40 #include <net/protocol.h>
41 #include <net/route.h>
42 #include <net/tcp.h>
43 #include <net/sock.h>
44 #include <net/ip_fib.h>
45 #include <net/ip_mp_alg.h>
46 #include <net/netlink.h>
47 #include <net/nexthop.h>
48
49 #include "fib_lookup.h"
50
51 #define FSprintk(a...)
52
53 static DEFINE_SPINLOCK(fib_info_lock);
54 static struct hlist_head *fib_info_hash;
55 static struct hlist_head *fib_info_laddrhash;
56 static unsigned int fib_hash_size;
57 static unsigned int fib_info_cnt;
58
59 #define DEVINDEX_HASHBITS 8
60 #define DEVINDEX_HASHSIZE (1U << DEVINDEX_HASHBITS)
61 static struct hlist_head fib_info_devhash[DEVINDEX_HASHSIZE];
62
63 #ifdef CONFIG_IP_ROUTE_MULTIPATH
64
65 static DEFINE_SPINLOCK(fib_multipath_lock);
66
67 #define for_nexthops(fi) { int nhsel; const struct fib_nh * nh; \
68 for (nhsel=0, nh = (fi)->fib_nh; nhsel < (fi)->fib_nhs; nh++, nhsel++)
69
70 #define change_nexthops(fi) { int nhsel; struct fib_nh * nh; \
71 for (nhsel=0, nh = (struct fib_nh*)((fi)->fib_nh); nhsel < (fi)->fib_nhs; nh++, nhsel++)
72
73 #else /* CONFIG_IP_ROUTE_MULTIPATH */
74
75 /* Hope, that gcc will optimize it to get rid of dummy loop */
76
77 #define for_nexthops(fi) { int nhsel=0; const struct fib_nh * nh = (fi)->fib_nh; \
78 for (nhsel=0; nhsel < 1; nhsel++)
79
80 #define change_nexthops(fi) { int nhsel=0; struct fib_nh * nh = (struct fib_nh*)((fi)->fib_nh); \
81 for (nhsel=0; nhsel < 1; nhsel++)
82
83 #endif /* CONFIG_IP_ROUTE_MULTIPATH */
84
85 #define endfor_nexthops(fi) }
86
87
88 static const struct
89 {
90         int     error;
91         u8      scope;
92 } fib_props[RTN_MAX + 1] = {
93         {
94                 .error  = 0,
95                 .scope  = RT_SCOPE_NOWHERE,
96         },      /* RTN_UNSPEC */
97         {
98                 .error  = 0,
99                 .scope  = RT_SCOPE_UNIVERSE,
100         },      /* RTN_UNICAST */
101         {
102                 .error  = 0,
103                 .scope  = RT_SCOPE_HOST,
104         },      /* RTN_LOCAL */
105         {
106                 .error  = 0,
107                 .scope  = RT_SCOPE_LINK,
108         },      /* RTN_BROADCAST */
109         {
110                 .error  = 0,
111                 .scope  = RT_SCOPE_LINK,
112         },      /* RTN_ANYCAST */
113         {
114                 .error  = 0,
115                 .scope  = RT_SCOPE_UNIVERSE,
116         },      /* RTN_MULTICAST */
117         {
118                 .error  = -EINVAL,
119                 .scope  = RT_SCOPE_UNIVERSE,
120         },      /* RTN_BLACKHOLE */
121         {
122                 .error  = -EHOSTUNREACH,
123                 .scope  = RT_SCOPE_UNIVERSE,
124         },      /* RTN_UNREACHABLE */
125         {
126                 .error  = -EACCES,
127                 .scope  = RT_SCOPE_UNIVERSE,
128         },      /* RTN_PROHIBIT */
129         {
130                 .error  = -EAGAIN,
131                 .scope  = RT_SCOPE_UNIVERSE,
132         },      /* RTN_THROW */
133         {
134                 .error  = -EINVAL,
135                 .scope  = RT_SCOPE_NOWHERE,
136         },      /* RTN_NAT */
137         {
138                 .error  = -EINVAL,
139                 .scope  = RT_SCOPE_NOWHERE,
140         },      /* RTN_XRESOLVE */
141 };
142
143
144 /* Release a nexthop info record */
145
146 void free_fib_info(struct fib_info *fi)
147 {
148         if (fi->fib_dead == 0) {
149                 printk("Freeing alive fib_info %p\n", fi);
150                 return;
151         }
152         change_nexthops(fi) {
153                 if (nh->nh_dev)
154                         dev_put(nh->nh_dev);
155                 nh->nh_dev = NULL;
156         } endfor_nexthops(fi);
157         fib_info_cnt--;
158         kfree(fi);
159 }
160
161 void fib_release_info(struct fib_info *fi)
162 {
163         spin_lock_bh(&fib_info_lock);
164         if (fi && --fi->fib_treeref == 0) {
165                 hlist_del(&fi->fib_hash);
166                 if (fi->fib_prefsrc)
167                         hlist_del(&fi->fib_lhash);
168                 change_nexthops(fi) {
169                         if (!nh->nh_dev)
170                                 continue;
171                         hlist_del(&nh->nh_hash);
172                 } endfor_nexthops(fi)
173                 fi->fib_dead = 1;
174                 fib_info_put(fi);
175         }
176         spin_unlock_bh(&fib_info_lock);
177 }
178
179 static __inline__ int nh_comp(const struct fib_info *fi, const struct fib_info *ofi)
180 {
181         const struct fib_nh *onh = ofi->fib_nh;
182
183         for_nexthops(fi) {
184                 if (nh->nh_oif != onh->nh_oif ||
185                     nh->nh_gw  != onh->nh_gw ||
186                     nh->nh_scope != onh->nh_scope ||
187 #ifdef CONFIG_IP_ROUTE_MULTIPATH
188                     nh->nh_weight != onh->nh_weight ||
189 #endif
190 #ifdef CONFIG_NET_CLS_ROUTE
191                     nh->nh_tclassid != onh->nh_tclassid ||
192 #endif
193                     ((nh->nh_flags^onh->nh_flags)&~RTNH_F_DEAD))
194                         return -1;
195                 onh++;
196         } endfor_nexthops(fi);
197         return 0;
198 }
199
200 static inline unsigned int fib_info_hashfn(const struct fib_info *fi)
201 {
202         unsigned int mask = (fib_hash_size - 1);
203         unsigned int val = fi->fib_nhs;
204
205         val ^= fi->fib_protocol;
206         val ^= (__force u32)fi->fib_prefsrc;
207         val ^= fi->fib_priority;
208
209         return (val ^ (val >> 7) ^ (val >> 12)) & mask;
210 }
211
212 static struct fib_info *fib_find_info(const struct fib_info *nfi)
213 {
214         struct hlist_head *head;
215         struct hlist_node *node;
216         struct fib_info *fi;
217         unsigned int hash;
218
219         hash = fib_info_hashfn(nfi);
220         head = &fib_info_hash[hash];
221
222         hlist_for_each_entry(fi, node, head, fib_hash) {
223                 if (fi->fib_nhs != nfi->fib_nhs)
224                         continue;
225                 if (nfi->fib_protocol == fi->fib_protocol &&
226                     nfi->fib_prefsrc == fi->fib_prefsrc &&
227                     nfi->fib_priority == fi->fib_priority &&
228                     memcmp(nfi->fib_metrics, fi->fib_metrics,
229                            sizeof(fi->fib_metrics)) == 0 &&
230                     ((nfi->fib_flags^fi->fib_flags)&~RTNH_F_DEAD) == 0 &&
231                     (nfi->fib_nhs == 0 || nh_comp(fi, nfi) == 0))
232                         return fi;
233         }
234
235         return NULL;
236 }
237
238 static inline unsigned int fib_devindex_hashfn(unsigned int val)
239 {
240         unsigned int mask = DEVINDEX_HASHSIZE - 1;
241
242         return (val ^
243                 (val >> DEVINDEX_HASHBITS) ^
244                 (val >> (DEVINDEX_HASHBITS * 2))) & mask;
245 }
246
247 /* Check, that the gateway is already configured.
248    Used only by redirect accept routine.
249  */
250
251 int ip_fib_check_default(__be32 gw, struct net_device *dev)
252 {
253         struct hlist_head *head;
254         struct hlist_node *node;
255         struct fib_nh *nh;
256         unsigned int hash;
257
258         spin_lock(&fib_info_lock);
259
260         hash = fib_devindex_hashfn(dev->ifindex);
261         head = &fib_info_devhash[hash];
262         hlist_for_each_entry(nh, node, head, nh_hash) {
263                 if (nh->nh_dev == dev &&
264                     nh->nh_gw == gw &&
265                     !(nh->nh_flags&RTNH_F_DEAD)) {
266                         spin_unlock(&fib_info_lock);
267                         return 0;
268                 }
269         }
270
271         spin_unlock(&fib_info_lock);
272
273         return -1;
274 }
275
276 static inline size_t fib_nlmsg_size(struct fib_info *fi)
277 {
278         size_t payload = NLMSG_ALIGN(sizeof(struct rtmsg))
279                          + nla_total_size(4) /* RTA_TABLE */
280                          + nla_total_size(4) /* RTA_DST */
281                          + nla_total_size(4) /* RTA_PRIORITY */
282                          + nla_total_size(4); /* RTA_PREFSRC */
283
284         /* space for nested metrics */
285         payload += nla_total_size((RTAX_MAX * nla_total_size(4)));
286
287         if (fi->fib_nhs) {
288                 /* Also handles the special case fib_nhs == 1 */
289
290                 /* each nexthop is packed in an attribute */
291                 size_t nhsize = nla_total_size(sizeof(struct rtnexthop));
292
293                 /* may contain flow and gateway attribute */
294                 nhsize += 2 * nla_total_size(4);
295
296                 /* all nexthops are packed in a nested attribute */
297                 payload += nla_total_size(fi->fib_nhs * nhsize);
298         }
299
300         return payload;
301 }
302
303 void rtmsg_fib(int event, __be32 key, struct fib_alias *fa,
304                int dst_len, u32 tb_id, struct nl_info *info)
305 {
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         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(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 #ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED
700         if (cfg->fc_mp_alg) {
701                 if (cfg->fc_mp_alg < IP_MP_ALG_NONE ||
702                     cfg->fc_mp_alg > IP_MP_ALG_MAX)
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                         memset(new_info_hash, 0, bytes);
724                         memset(new_laddrhash, 0, bytes);
725
726                         fib_hash_move(new_info_hash, new_laddrhash, new_size);
727                 }
728
729                 if (!fib_hash_size)
730                         goto failure;
731         }
732
733         fi = kzalloc(sizeof(*fi)+nhs*sizeof(struct fib_nh), GFP_KERNEL);
734         if (fi == NULL)
735                 goto failure;
736         fib_info_cnt++;
737
738         fi->fib_protocol = cfg->fc_protocol;
739         fi->fib_flags = cfg->fc_flags;
740         fi->fib_priority = cfg->fc_priority;
741         fi->fib_prefsrc = cfg->fc_prefsrc;
742
743         fi->fib_nhs = nhs;
744         change_nexthops(fi) {
745                 nh->nh_parent = fi;
746         } endfor_nexthops(fi)
747
748         if (cfg->fc_mx) {
749                 struct nlattr *nla;
750                 int remaining;
751
752                 nla_for_each_attr(nla, cfg->fc_mx, cfg->fc_mx_len, remaining) {
753                         int type = nla->nla_type;
754
755                         if (type) {
756                                 if (type > RTAX_MAX)
757                                         goto err_inval;
758                                 fi->fib_metrics[type - 1] = nla_get_u32(nla);
759                         }
760                 }
761         }
762
763         if (cfg->fc_mp) {
764 #ifdef CONFIG_IP_ROUTE_MULTIPATH
765                 err = fib_get_nhs(fi, cfg->fc_mp, cfg->fc_mp_len, cfg);
766                 if (err != 0)
767                         goto failure;
768                 if (cfg->fc_oif && fi->fib_nh->nh_oif != cfg->fc_oif)
769                         goto err_inval;
770                 if (cfg->fc_gw && fi->fib_nh->nh_gw != cfg->fc_gw)
771                         goto err_inval;
772 #ifdef CONFIG_NET_CLS_ROUTE
773                 if (cfg->fc_flow && fi->fib_nh->nh_tclassid != cfg->fc_flow)
774                         goto err_inval;
775 #endif
776 #else
777                 goto err_inval;
778 #endif
779         } else {
780                 struct fib_nh *nh = fi->fib_nh;
781
782                 nh->nh_oif = cfg->fc_oif;
783                 nh->nh_gw = cfg->fc_gw;
784                 nh->nh_flags = cfg->fc_flags;
785 #ifdef CONFIG_NET_CLS_ROUTE
786                 nh->nh_tclassid = cfg->fc_flow;
787 #endif
788 #ifdef CONFIG_IP_ROUTE_MULTIPATH
789                 nh->nh_weight = 1;
790 #endif
791         }
792
793 #ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED
794         fi->fib_mp_alg = cfg->fc_mp_alg;
795 #endif
796
797         if (fib_props[cfg->fc_type].error) {
798                 if (cfg->fc_gw || cfg->fc_oif || cfg->fc_mp)
799                         goto err_inval;
800                 goto link_it;
801         }
802
803         if (cfg->fc_scope > RT_SCOPE_HOST)
804                 goto err_inval;
805
806         if (cfg->fc_scope == RT_SCOPE_HOST) {
807                 struct fib_nh *nh = fi->fib_nh;
808
809                 /* Local address is added. */
810                 if (nhs != 1 || nh->nh_gw)
811                         goto err_inval;
812                 nh->nh_scope = RT_SCOPE_NOWHERE;
813                 nh->nh_dev = dev_get_by_index(fi->fib_nh->nh_oif);
814                 err = -ENODEV;
815                 if (nh->nh_dev == NULL)
816                         goto failure;
817         } else {
818                 change_nexthops(fi) {
819                         if ((err = fib_check_nh(cfg, fi, nh)) != 0)
820                                 goto failure;
821                 } endfor_nexthops(fi)
822         }
823
824         if (fi->fib_prefsrc) {
825                 if (cfg->fc_type != RTN_LOCAL || !cfg->fc_dst ||
826                     fi->fib_prefsrc != cfg->fc_dst)
827                         if (inet_addr_type(fi->fib_prefsrc) != RTN_LOCAL)
828                                 goto err_inval;
829         }
830
831 link_it:
832         if ((ofi = fib_find_info(fi)) != NULL) {
833                 fi->fib_dead = 1;
834                 free_fib_info(fi);
835                 ofi->fib_treeref++;
836                 return ofi;
837         }
838
839         fi->fib_treeref++;
840         atomic_inc(&fi->fib_clntref);
841         spin_lock_bh(&fib_info_lock);
842         hlist_add_head(&fi->fib_hash,
843                        &fib_info_hash[fib_info_hashfn(fi)]);
844         if (fi->fib_prefsrc) {
845                 struct hlist_head *head;
846
847                 head = &fib_info_laddrhash[fib_laddr_hashfn(fi->fib_prefsrc)];
848                 hlist_add_head(&fi->fib_lhash, head);
849         }
850         change_nexthops(fi) {
851                 struct hlist_head *head;
852                 unsigned int hash;
853
854                 if (!nh->nh_dev)
855                         continue;
856                 hash = fib_devindex_hashfn(nh->nh_dev->ifindex);
857                 head = &fib_info_devhash[hash];
858                 hlist_add_head(&nh->nh_hash, head);
859         } endfor_nexthops(fi)
860         spin_unlock_bh(&fib_info_lock);
861         return fi;
862
863 err_inval:
864         err = -EINVAL;
865
866 failure:
867         if (fi) {
868                 fi->fib_dead = 1;
869                 free_fib_info(fi);
870         }
871
872         return ERR_PTR(err);
873 }
874
875 /* Note! fib_semantic_match intentionally uses  RCU list functions. */
876 int fib_semantic_match(struct list_head *head, const struct flowi *flp,
877                        struct fib_result *res, __be32 zone, __be32 mask,
878                         int prefixlen)
879 {
880         struct fib_alias *fa;
881         int nh_sel = 0;
882
883         list_for_each_entry_rcu(fa, head, fa_list) {
884                 int err;
885
886                 if (fa->fa_tos &&
887                     fa->fa_tos != flp->fl4_tos)
888                         continue;
889
890                 if (fa->fa_scope < flp->fl4_scope)
891                         continue;
892
893                 fa->fa_state |= FA_S_ACCESSED;
894
895                 err = fib_props[fa->fa_type].error;
896                 if (err == 0) {
897                         struct fib_info *fi = fa->fa_info;
898
899                         if (fi->fib_flags & RTNH_F_DEAD)
900                                 continue;
901
902                         switch (fa->fa_type) {
903                         case RTN_UNICAST:
904                         case RTN_LOCAL:
905                         case RTN_BROADCAST:
906                         case RTN_ANYCAST:
907                         case RTN_MULTICAST:
908                                 for_nexthops(fi) {
909                                         if (nh->nh_flags&RTNH_F_DEAD)
910                                                 continue;
911                                         if (!flp->oif || flp->oif == nh->nh_oif)
912                                                 break;
913                                 }
914 #ifdef CONFIG_IP_ROUTE_MULTIPATH
915                                 if (nhsel < fi->fib_nhs) {
916                                         nh_sel = nhsel;
917                                         goto out_fill_res;
918                                 }
919 #else
920                                 if (nhsel < 1) {
921                                         goto out_fill_res;
922                                 }
923 #endif
924                                 endfor_nexthops(fi);
925                                 continue;
926
927                         default:
928                                 printk(KERN_DEBUG "impossible 102\n");
929                                 return -EINVAL;
930                         };
931                 }
932                 return err;
933         }
934         return 1;
935
936 out_fill_res:
937         res->prefixlen = prefixlen;
938         res->nh_sel = nh_sel;
939         res->type = fa->fa_type;
940         res->scope = fa->fa_scope;
941         res->fi = fa->fa_info;
942 #ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED
943         res->netmask = mask;
944         res->network = zone & inet_make_mask(prefixlen);
945 #endif
946         atomic_inc(&res->fi->fib_clntref);
947         return 0;
948 }
949
950 /* Find appropriate source address to this destination */
951
952 __be32 __fib_res_prefsrc(struct fib_result *res)
953 {
954         return inet_select_addr(FIB_RES_DEV(*res), FIB_RES_GW(*res), res->scope);
955 }
956
957 int fib_dump_info(struct sk_buff *skb, u32 pid, u32 seq, int event,
958                   u32 tb_id, u8 type, u8 scope, __be32 dst, int dst_len, u8 tos,
959                   struct fib_info *fi, unsigned int flags)
960 {
961         struct nlmsghdr *nlh;
962         struct rtmsg *rtm;
963
964         nlh = nlmsg_put(skb, pid, seq, event, sizeof(*rtm), flags);
965         if (nlh == NULL)
966                 return -EMSGSIZE;
967
968         rtm = nlmsg_data(nlh);
969         rtm->rtm_family = AF_INET;
970         rtm->rtm_dst_len = dst_len;
971         rtm->rtm_src_len = 0;
972         rtm->rtm_tos = tos;
973         rtm->rtm_table = tb_id;
974         NLA_PUT_U32(skb, RTA_TABLE, tb_id);
975         rtm->rtm_type = type;
976         rtm->rtm_flags = fi->fib_flags;
977         rtm->rtm_scope = scope;
978         rtm->rtm_protocol = fi->fib_protocol;
979
980         if (rtm->rtm_dst_len)
981                 NLA_PUT_BE32(skb, RTA_DST, dst);
982
983         if (fi->fib_priority)
984                 NLA_PUT_U32(skb, RTA_PRIORITY, fi->fib_priority);
985
986         if (rtnetlink_put_metrics(skb, fi->fib_metrics) < 0)
987                 goto nla_put_failure;
988
989         if (fi->fib_prefsrc)
990                 NLA_PUT_BE32(skb, RTA_PREFSRC, fi->fib_prefsrc);
991
992         if (fi->fib_nhs == 1) {
993                 if (fi->fib_nh->nh_gw)
994                         NLA_PUT_BE32(skb, RTA_GATEWAY, fi->fib_nh->nh_gw);
995
996                 if (fi->fib_nh->nh_oif)
997                         NLA_PUT_U32(skb, RTA_OIF, fi->fib_nh->nh_oif);
998 #ifdef CONFIG_NET_CLS_ROUTE
999                 if (fi->fib_nh[0].nh_tclassid)
1000                         NLA_PUT_U32(skb, RTA_FLOW, fi->fib_nh[0].nh_tclassid);
1001 #endif
1002         }
1003 #ifdef CONFIG_IP_ROUTE_MULTIPATH
1004         if (fi->fib_nhs > 1) {
1005                 struct rtnexthop *rtnh;
1006                 struct nlattr *mp;
1007
1008                 mp = nla_nest_start(skb, RTA_MULTIPATH);
1009                 if (mp == NULL)
1010                         goto nla_put_failure;
1011
1012                 for_nexthops(fi) {
1013                         rtnh = nla_reserve_nohdr(skb, sizeof(*rtnh));
1014                         if (rtnh == NULL)
1015                                 goto nla_put_failure;
1016
1017                         rtnh->rtnh_flags = nh->nh_flags & 0xFF;
1018                         rtnh->rtnh_hops = nh->nh_weight - 1;
1019                         rtnh->rtnh_ifindex = nh->nh_oif;
1020
1021                         if (nh->nh_gw)
1022                                 NLA_PUT_BE32(skb, RTA_GATEWAY, nh->nh_gw);
1023 #ifdef CONFIG_NET_CLS_ROUTE
1024                         if (nh->nh_tclassid)
1025                                 NLA_PUT_U32(skb, RTA_FLOW, nh->nh_tclassid);
1026 #endif
1027                         /* length of rtnetlink header + attributes */
1028                         rtnh->rtnh_len = nlmsg_get_pos(skb) - (void *) rtnh;
1029                 } endfor_nexthops(fi);
1030
1031                 nla_nest_end(skb, mp);
1032         }
1033 #endif
1034         return nlmsg_end(skb, nlh);
1035
1036 nla_put_failure:
1037         nlmsg_cancel(skb, nlh);
1038         return -EMSGSIZE;
1039 }
1040
1041 /*
1042    Update FIB if:
1043    - local address disappeared -> we must delete all the entries
1044      referring to it.
1045    - device went down -> we must shutdown all nexthops going via it.
1046  */
1047
1048 int fib_sync_down(__be32 local, struct net_device *dev, int force)
1049 {
1050         int ret = 0;
1051         int scope = RT_SCOPE_NOWHERE;
1052
1053         if (force)
1054                 scope = -1;
1055
1056         if (local && fib_info_laddrhash) {
1057                 unsigned int hash = fib_laddr_hashfn(local);
1058                 struct hlist_head *head = &fib_info_laddrhash[hash];
1059                 struct hlist_node *node;
1060                 struct fib_info *fi;
1061
1062                 hlist_for_each_entry(fi, node, head, fib_lhash) {
1063                         if (fi->fib_prefsrc == local) {
1064                                 fi->fib_flags |= RTNH_F_DEAD;
1065                                 ret++;
1066                         }
1067                 }
1068         }
1069
1070         if (dev) {
1071                 struct fib_info *prev_fi = NULL;
1072                 unsigned int hash = fib_devindex_hashfn(dev->ifindex);
1073                 struct hlist_head *head = &fib_info_devhash[hash];
1074                 struct hlist_node *node;
1075                 struct fib_nh *nh;
1076
1077                 hlist_for_each_entry(nh, node, head, nh_hash) {
1078                         struct fib_info *fi = nh->nh_parent;
1079                         int dead;
1080
1081                         BUG_ON(!fi->fib_nhs);
1082                         if (nh->nh_dev != dev || fi == prev_fi)
1083                                 continue;
1084                         prev_fi = fi;
1085                         dead = 0;
1086                         change_nexthops(fi) {
1087                                 if (nh->nh_flags&RTNH_F_DEAD)
1088                                         dead++;
1089                                 else if (nh->nh_dev == dev &&
1090                                          nh->nh_scope != scope) {
1091                                         nh->nh_flags |= RTNH_F_DEAD;
1092 #ifdef CONFIG_IP_ROUTE_MULTIPATH
1093                                         spin_lock_bh(&fib_multipath_lock);
1094                                         fi->fib_power -= nh->nh_power;
1095                                         nh->nh_power = 0;
1096                                         spin_unlock_bh(&fib_multipath_lock);
1097 #endif
1098                                         dead++;
1099                                 }
1100 #ifdef CONFIG_IP_ROUTE_MULTIPATH
1101                                 if (force > 1 && nh->nh_dev == dev) {
1102                                         dead = fi->fib_nhs;
1103                                         break;
1104                                 }
1105 #endif
1106                         } endfor_nexthops(fi)
1107                         if (dead == fi->fib_nhs) {
1108                                 fi->fib_flags |= RTNH_F_DEAD;
1109                                 ret++;
1110                         }
1111                 }
1112         }
1113
1114         return ret;
1115 }
1116
1117 #ifdef CONFIG_IP_ROUTE_MULTIPATH
1118
1119 /*
1120    Dead device goes up. We wake up dead nexthops.
1121    It takes sense only on multipath routes.
1122  */
1123
1124 int fib_sync_up(struct net_device *dev)
1125 {
1126         struct fib_info *prev_fi;
1127         unsigned int hash;
1128         struct hlist_head *head;
1129         struct hlist_node *node;
1130         struct fib_nh *nh;
1131         int ret;
1132
1133         if (!(dev->flags&IFF_UP))
1134                 return 0;
1135
1136         prev_fi = NULL;
1137         hash = fib_devindex_hashfn(dev->ifindex);
1138         head = &fib_info_devhash[hash];
1139         ret = 0;
1140
1141         hlist_for_each_entry(nh, node, head, nh_hash) {
1142                 struct fib_info *fi = nh->nh_parent;
1143                 int alive;
1144
1145                 BUG_ON(!fi->fib_nhs);
1146                 if (nh->nh_dev != dev || fi == prev_fi)
1147                         continue;
1148
1149                 prev_fi = fi;
1150                 alive = 0;
1151                 change_nexthops(fi) {
1152                         if (!(nh->nh_flags&RTNH_F_DEAD)) {
1153                                 alive++;
1154                                 continue;
1155                         }
1156                         if (nh->nh_dev == NULL || !(nh->nh_dev->flags&IFF_UP))
1157                                 continue;
1158                         if (nh->nh_dev != dev || !__in_dev_get_rtnl(dev))
1159                                 continue;
1160                         alive++;
1161                         spin_lock_bh(&fib_multipath_lock);
1162                         nh->nh_power = 0;
1163                         nh->nh_flags &= ~RTNH_F_DEAD;
1164                         spin_unlock_bh(&fib_multipath_lock);
1165                 } endfor_nexthops(fi)
1166
1167                 if (alive > 0) {
1168                         fi->fib_flags &= ~RTNH_F_DEAD;
1169                         ret++;
1170                 }
1171         }
1172
1173         return ret;
1174 }
1175
1176 /*
1177    The algorithm is suboptimal, but it provides really
1178    fair weighted route distribution.
1179  */
1180
1181 void fib_select_multipath(const struct flowi *flp, struct fib_result *res)
1182 {
1183         struct fib_info *fi = res->fi;
1184         int w;
1185
1186         spin_lock_bh(&fib_multipath_lock);
1187         if (fi->fib_power <= 0) {
1188                 int power = 0;
1189                 change_nexthops(fi) {
1190                         if (!(nh->nh_flags&RTNH_F_DEAD)) {
1191                                 power += nh->nh_weight;
1192                                 nh->nh_power = nh->nh_weight;
1193                         }
1194                 } endfor_nexthops(fi);
1195                 fi->fib_power = power;
1196                 if (power <= 0) {
1197                         spin_unlock_bh(&fib_multipath_lock);
1198                         /* Race condition: route has just become dead. */
1199                         res->nh_sel = 0;
1200                         return;
1201                 }
1202         }
1203
1204
1205         /* w should be random number [0..fi->fib_power-1],
1206            it is pretty bad approximation.
1207          */
1208
1209         w = jiffies % fi->fib_power;
1210
1211         change_nexthops(fi) {
1212                 if (!(nh->nh_flags&RTNH_F_DEAD) && nh->nh_power) {
1213                         if ((w -= nh->nh_power) <= 0) {
1214                                 nh->nh_power--;
1215                                 fi->fib_power--;
1216                                 res->nh_sel = nhsel;
1217                                 spin_unlock_bh(&fib_multipath_lock);
1218                                 return;
1219                         }
1220                 }
1221         } endfor_nexthops(fi);
1222
1223         /* Race condition: route has just become dead. */
1224         res->nh_sel = 0;
1225         spin_unlock_bh(&fib_multipath_lock);
1226 }
1227 #endif