__P() removal
[dragonfly.git] / sys / net / route.c
1 /*
2  * Copyright (c) 1980, 1986, 1991, 1993
3  *      The Regents of the University of California.  All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  * 3. All advertising materials mentioning features or use of this software
14  *    must display the following acknowledgement:
15  *      This product includes software developed by the University of
16  *      California, Berkeley and its contributors.
17  * 4. Neither the name of the University nor the names of its contributors
18  *    may be used to endorse or promote products derived from this software
19  *    without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31  * SUCH DAMAGE.
32  *
33  *      @(#)route.c     8.3 (Berkeley) 1/9/95
34  * $FreeBSD: src/sys/net/route.c,v 1.59.2.10 2003/01/17 08:04:00 ru Exp $
35  * $DragonFly: src/sys/net/route.c,v 1.6 2003/08/26 20:49:47 rob Exp $
36  */
37
38 #include "opt_inet.h"
39
40 #include <sys/param.h>
41 #include <sys/systm.h>
42 #include <sys/malloc.h>
43 #include <sys/mbuf.h>
44 #include <sys/socket.h>
45 #include <sys/domain.h>
46 #include <sys/kernel.h>
47
48 #include <net/if.h>
49 #include <net/route.h>
50
51 #include <netinet/in.h>
52 #include <net/ip_mroute/ip_mroute.h>
53
54 #define SA(p) ((struct sockaddr *)(p))
55
56 struct route_cb route_cb;
57 static struct rtstat rtstat;
58 struct radix_node_head *rt_tables[AF_MAX+1];
59
60 static int      rttrash;                /* routes not in table but not freed */
61
62 static void rt_maskedcopy (struct sockaddr *,
63             struct sockaddr *, struct sockaddr *);
64 static void rtable_init (void **);
65
66 static void
67 rtable_init(table)
68         void **table;
69 {
70         struct domain *dom;
71         for (dom = domains; dom; dom = dom->dom_next)
72                 if (dom->dom_rtattach)
73                         dom->dom_rtattach(&table[dom->dom_family],
74                             dom->dom_rtoffset);
75 }
76
77 void
78 route_init()
79 {
80         rn_init();      /* initialize all zeroes, all ones, mask table */
81         rtable_init((void **)rt_tables);
82 }
83
84 /*
85  * Packet routing routines.
86  */
87 void
88 rtalloc(ro)
89         struct route *ro;
90 {
91         rtalloc_ign(ro, 0UL);
92 }
93
94 void
95 rtalloc_ign(ro, ignore)
96         struct route *ro;
97         u_long ignore;
98 {
99         struct rtentry *rt;
100         int s;
101
102         if ((rt = ro->ro_rt) != NULL) {
103                 if (rt->rt_ifp != NULL && rt->rt_flags & RTF_UP)
104                         return;
105                 /* XXX - We are probably always at splnet here already. */
106                 s = splnet();
107                 RTFREE(rt);
108                 ro->ro_rt = NULL;
109                 splx(s);
110         }
111         ro->ro_rt = rtalloc1(&ro->ro_dst, 1, ignore);
112 }
113
114 /*
115  * Look up the route that matches the address given
116  * Or, at least try.. Create a cloned route if needed.
117  */
118 struct rtentry *
119 rtalloc1(dst, report, ignflags)
120         struct sockaddr *dst;
121         int report;
122         u_long ignflags;
123 {
124         struct radix_node_head *rnh = rt_tables[dst->sa_family];
125         struct rtentry *rt;
126         struct radix_node *rn;
127         struct rtentry *newrt = 0;
128         struct rt_addrinfo info;
129         u_long nflags;
130         int  s = splnet(), err = 0, msgtype = RTM_MISS;
131
132         /*
133          * Look up the address in the table for that Address Family
134          */
135         if (rnh && (rn = rnh->rnh_matchaddr((caddr_t)dst, rnh)) &&
136             ((rn->rn_flags & RNF_ROOT) == 0)) {
137                 /*
138                  * If we find it and it's not the root node, then
139                  * get a refernce on the rtentry associated.
140                  */
141                 newrt = rt = (struct rtentry *)rn;
142                 nflags = rt->rt_flags & ~ignflags;
143                 if (report && (nflags & (RTF_CLONING | RTF_PRCLONING))) {
144                         /*
145                          * We are apparently adding (report = 0 in delete).
146                          * If it requires that it be cloned, do so.
147                          * (This implies it wasn't a HOST route.)
148                          */
149                         err = rtrequest(RTM_RESOLVE, dst, SA(0),
150                                               SA(0), 0, &newrt);
151                         if (err) {
152                                 /*
153                                  * If the cloning didn't succeed, maybe
154                                  * what we have will do. Return that.
155                                  */
156                                 newrt = rt;
157                                 rt->rt_refcnt++;
158                                 goto miss;
159                         }
160                         if ((rt = newrt) && (rt->rt_flags & RTF_XRESOLVE)) {
161                                 /*
162                                  * If the new route specifies it be
163                                  * externally resolved, then go do that.
164                                  */
165                                 msgtype = RTM_RESOLVE;
166                                 goto miss;
167                         }
168                         /* Inform listeners of the new route. */
169                         bzero(&info, sizeof(info));
170                         info.rti_info[RTAX_DST] = rt_key(rt);
171                         info.rti_info[RTAX_NETMASK] = rt_mask(rt);
172                         info.rti_info[RTAX_GATEWAY] = rt->rt_gateway;
173                         if (rt->rt_ifp != NULL) {
174                                 info.rti_info[RTAX_IFP] =
175                                     TAILQ_FIRST(&rt->rt_ifp->if_addrhead)->ifa_addr;
176                                 info.rti_info[RTAX_IFA] = rt->rt_ifa->ifa_addr;
177                         }
178                         rt_missmsg(RTM_ADD, &info, rt->rt_flags, 0);
179                 } else
180                         rt->rt_refcnt++;
181         } else {
182                 /*
183                  * Either we hit the root or couldn't find any match,
184                  * Which basically means
185                  * "caint get there frm here"
186                  */
187                 rtstat.rts_unreach++;
188         miss:   if (report) {
189                         /*
190                          * If required, report the failure to the supervising
191                          * Authorities.
192                          * For a delete, this is not an error. (report == 0)
193                          */
194                         bzero((caddr_t)&info, sizeof(info));
195                         info.rti_info[RTAX_DST] = dst;
196                         rt_missmsg(msgtype, &info, 0, err);
197                 }
198         }
199         splx(s);
200         return (newrt);
201 }
202
203 /*
204  * Remove a reference count from an rtentry.
205  * If the count gets low enough, take it out of the routing table
206  */
207 void
208 rtfree(rt)
209         struct rtentry *rt;
210 {
211         /*
212          * find the tree for that address family
213          */
214         struct radix_node_head *rnh =
215                 rt_tables[rt_key(rt)->sa_family];
216         struct ifaddr *ifa;
217
218         if (rt == 0 || rnh == 0)
219                 panic("rtfree");
220
221         /*
222          * decrement the reference count by one and if it reaches 0,
223          * and there is a close function defined, call the close function
224          */
225         rt->rt_refcnt--;
226         if(rnh->rnh_close && rt->rt_refcnt == 0) {
227                 rnh->rnh_close((struct radix_node *)rt, rnh);
228         }
229
230         /*
231          * If we are no longer "up" (and ref == 0)
232          * then we can free the resources associated
233          * with the route.
234          */
235         if (rt->rt_refcnt <= 0 && (rt->rt_flags & RTF_UP) == 0) {
236                 if (rt->rt_nodes->rn_flags & (RNF_ACTIVE | RNF_ROOT))
237                         panic ("rtfree 2");
238                 /*
239                  * the rtentry must have been removed from the routing table
240                  * so it is represented in rttrash.. remove that now.
241                  */
242                 rttrash--;
243
244 #ifdef  DIAGNOSTIC
245                 if (rt->rt_refcnt < 0) {
246                         printf("rtfree: %p not freed (neg refs)\n", rt);
247                         return;
248                 }
249 #endif
250
251                 /*
252                  * release references on items we hold them on..
253                  * e.g other routes and ifaddrs.
254                  */
255                 if((ifa = rt->rt_ifa))
256                         IFAFREE(ifa);
257                 if (rt->rt_parent) {
258                         RTFREE(rt->rt_parent);
259                 }
260
261                 /*
262                  * The key is separatly alloc'd so free it (see rt_setgate()).
263                  * This also frees the gateway, as they are always malloc'd
264                  * together.
265                  */
266                 Free(rt_key(rt));
267
268                 /*
269                  * and the rtentry itself of course
270                  */
271                 Free(rt);
272         }
273 }
274
275 void
276 ifafree(ifa)
277         struct ifaddr *ifa;
278 {
279         if (ifa == NULL)
280                 panic("ifafree");
281         if (ifa->ifa_refcnt == 0)
282                 free(ifa, M_IFADDR);
283         else
284                 ifa->ifa_refcnt--;
285 }
286
287 /*
288  * Force a routing table entry to the specified
289  * destination to go through the given gateway.
290  * Normally called as a result of a routing redirect
291  * message from the network layer.
292  *
293  * N.B.: must be called at splnet
294  *
295  */
296 void
297 rtredirect(dst, gateway, netmask, flags, src, rtp)
298         struct sockaddr *dst, *gateway, *netmask, *src;
299         int flags;
300         struct rtentry **rtp;
301 {
302         struct rtentry *rt;
303         int error = 0;
304         short *stat = 0;
305         struct rt_addrinfo info;
306         struct ifaddr *ifa;
307
308         /* verify the gateway is directly reachable */
309         if ((ifa = ifa_ifwithnet(gateway)) == 0) {
310                 error = ENETUNREACH;
311                 goto out;
312         }
313         rt = rtalloc1(dst, 0, 0UL);
314         /*
315          * If the redirect isn't from our current router for this dst,
316          * it's either old or wrong.  If it redirects us to ourselves,
317          * we have a routing loop, perhaps as a result of an interface
318          * going down recently.
319          */
320 #define equal(a1, a2) (bcmp((caddr_t)(a1), (caddr_t)(a2), (a1)->sa_len) == 0)
321         if (!(flags & RTF_DONE) && rt &&
322              (!equal(src, rt->rt_gateway) || rt->rt_ifa != ifa))
323                 error = EINVAL;
324         else if (ifa_ifwithaddr(gateway))
325                 error = EHOSTUNREACH;
326         if (error)
327                 goto done;
328         /*
329          * Create a new entry if we just got back a wildcard entry
330          * or the the lookup failed.  This is necessary for hosts
331          * which use routing redirects generated by smart gateways
332          * to dynamically build the routing tables.
333          */
334         if ((rt == 0) || (rt_mask(rt) && rt_mask(rt)->sa_len < 2))
335                 goto create;
336         /*
337          * Don't listen to the redirect if it's
338          * for a route to an interface.
339          */
340         if (rt->rt_flags & RTF_GATEWAY) {
341                 if (((rt->rt_flags & RTF_HOST) == 0) && (flags & RTF_HOST)) {
342                         /*
343                          * Changing from route to net => route to host.
344                          * Create new route, rather than smashing route to net.
345                          */
346                 create:
347                         if (rt)
348                                 rtfree(rt);
349                         flags |=  RTF_GATEWAY | RTF_DYNAMIC;
350                         bzero((caddr_t)&info, sizeof(info));
351                         info.rti_info[RTAX_DST] = dst;
352                         info.rti_info[RTAX_GATEWAY] = gateway;
353                         info.rti_info[RTAX_NETMASK] = netmask;
354                         info.rti_ifa = ifa;
355                         info.rti_flags = flags;
356                         rt = NULL;
357                         error = rtrequest1(RTM_ADD, &info, &rt);
358                         if (rt != NULL)
359                                 flags = rt->rt_flags;
360                         stat = &rtstat.rts_dynamic;
361                 } else {
362                         /*
363                          * Smash the current notion of the gateway to
364                          * this destination.  Should check about netmask!!!
365                          */
366                         rt->rt_flags |= RTF_MODIFIED;
367                         flags |= RTF_MODIFIED;
368                         stat = &rtstat.rts_newgateway;
369                         /*
370                          * add the key and gateway (in one malloc'd chunk).
371                          */
372                         rt_setgate(rt, rt_key(rt), gateway);
373                 }
374         } else
375                 error = EHOSTUNREACH;
376 done:
377         if (rt) {
378                 if (rtp && !error)
379                         *rtp = rt;
380                 else
381                         rtfree(rt);
382         }
383 out:
384         if (error)
385                 rtstat.rts_badredirect++;
386         else if (stat != NULL)
387                 (*stat)++;
388         bzero((caddr_t)&info, sizeof(info));
389         info.rti_info[RTAX_DST] = dst;
390         info.rti_info[RTAX_GATEWAY] = gateway;
391         info.rti_info[RTAX_NETMASK] = netmask;
392         info.rti_info[RTAX_AUTHOR] = src;
393         rt_missmsg(RTM_REDIRECT, &info, flags, error);
394 }
395
396 /*
397 * Routing table ioctl interface.
398 */
399 int
400 rtioctl(u_long req, caddr_t data, struct thread *td)
401 {
402 #ifdef INET
403         /* Multicast goop, grrr... */
404         return mrt_ioctl ? mrt_ioctl(req, data) : EOPNOTSUPP;
405 #else /* INET */
406         return ENXIO;
407 #endif /* INET */
408 }
409
410 struct ifaddr *
411 ifa_ifwithroute(flags, dst, gateway)
412         int flags;
413         struct sockaddr *dst, *gateway;
414 {
415         struct ifaddr *ifa;
416         if ((flags & RTF_GATEWAY) == 0) {
417                 /*
418                  * If we are adding a route to an interface,
419                  * and the interface is a pt to pt link
420                  * we should search for the destination
421                  * as our clue to the interface.  Otherwise
422                  * we can use the local address.
423                  */
424                 ifa = 0;
425                 if (flags & RTF_HOST) {
426                         ifa = ifa_ifwithdstaddr(dst);
427                 }
428                 if (ifa == 0)
429                         ifa = ifa_ifwithaddr(gateway);
430         } else {
431                 /*
432                  * If we are adding a route to a remote net
433                  * or host, the gateway may still be on the
434                  * other end of a pt to pt link.
435                  */
436                 ifa = ifa_ifwithdstaddr(gateway);
437         }
438         if (ifa == 0)
439                 ifa = ifa_ifwithnet(gateway);
440         if (ifa == 0) {
441                 struct rtentry *rt = rtalloc1(gateway, 0, 0UL);
442                 if (rt == 0)
443                         return (0);
444                 rt->rt_refcnt--;
445                 if ((ifa = rt->rt_ifa) == 0)
446                         return (0);
447         }
448         if (ifa->ifa_addr->sa_family != dst->sa_family) {
449                 struct ifaddr *oifa = ifa;
450                 ifa = ifaof_ifpforaddr(dst, ifa->ifa_ifp);
451                 if (ifa == 0)
452                         ifa = oifa;
453         }
454         return (ifa);
455 }
456
457 static int rt_fixdelete (struct radix_node *, void *);
458 static int rt_fixchange (struct radix_node *, void *);
459
460 struct rtfc_arg {
461         struct rtentry *rt0;
462         struct radix_node_head *rnh;
463 };
464
465 /*
466  * Do appropriate manipulations of a routing tree given
467  * all the bits of info needed
468  */
469 int
470 rtrequest(req, dst, gateway, netmask, flags, ret_nrt)
471         int req, flags;
472         struct sockaddr *dst, *gateway, *netmask;
473         struct rtentry **ret_nrt;
474 {
475         struct rt_addrinfo info;
476
477         bzero((caddr_t)&info, sizeof(info));
478         info.rti_flags = flags;
479         info.rti_info[RTAX_DST] = dst;
480         info.rti_info[RTAX_GATEWAY] = gateway;
481         info.rti_info[RTAX_NETMASK] = netmask;
482         return rtrequest1(req, &info, ret_nrt);
483 }
484
485 /*
486  * These (questionable) definitions of apparent local variables apply
487  * to the next two functions.  XXXXXX!!!
488  */
489 #define dst     info->rti_info[RTAX_DST]
490 #define gateway info->rti_info[RTAX_GATEWAY]
491 #define netmask info->rti_info[RTAX_NETMASK]
492 #define ifaaddr info->rti_info[RTAX_IFA]
493 #define ifpaddr info->rti_info[RTAX_IFP]
494 #define flags   info->rti_flags
495
496 int
497 rt_getifa(info)
498         struct rt_addrinfo *info;
499 {
500         struct ifaddr *ifa;
501         int error = 0;
502
503         /*
504          * ifp may be specified by sockaddr_dl
505          * when protocol address is ambiguous.
506          */
507         if (info->rti_ifp == NULL && ifpaddr != NULL &&
508             ifpaddr->sa_family == AF_LINK &&
509             (ifa = ifa_ifwithnet(ifpaddr)) != NULL)
510                 info->rti_ifp = ifa->ifa_ifp;
511         if (info->rti_ifa == NULL && ifaaddr != NULL)
512                 info->rti_ifa = ifa_ifwithaddr(ifaaddr);
513         if (info->rti_ifa == NULL) {
514                 struct sockaddr *sa;
515
516                 sa = ifaaddr != NULL ? ifaaddr :
517                     (gateway != NULL ? gateway : dst);
518                 if (sa != NULL && info->rti_ifp != NULL)
519                         info->rti_ifa = ifaof_ifpforaddr(sa, info->rti_ifp);
520                 else if (dst != NULL && gateway != NULL)
521                         info->rti_ifa = ifa_ifwithroute(flags, dst, gateway);
522                 else if (sa != NULL)
523                         info->rti_ifa = ifa_ifwithroute(flags, sa, sa);
524         }
525         if ((ifa = info->rti_ifa) != NULL) {
526                 if (info->rti_ifp == NULL)
527                         info->rti_ifp = ifa->ifa_ifp;
528         } else
529                 error = ENETUNREACH;
530         return (error);
531 }
532
533 int
534 rtrequest1(req, info, ret_nrt)
535         int req;
536         struct rt_addrinfo *info;
537         struct rtentry **ret_nrt;
538 {
539         int s = splnet(); int error = 0;
540         struct rtentry *rt;
541         struct radix_node *rn;
542         struct radix_node_head *rnh;
543         struct ifaddr *ifa;
544         struct sockaddr *ndst;
545 #define senderr(x) { error = x ; goto bad; }
546
547         /*
548          * Find the correct routing tree to use for this Address Family
549          */
550         if ((rnh = rt_tables[dst->sa_family]) == 0)
551                 senderr(EAFNOSUPPORT);
552         /*
553          * If we are adding a host route then we don't want to put
554          * a netmask in the tree, nor do we want to clone it.
555          */
556         if (flags & RTF_HOST) {
557                 netmask = 0;
558                 flags &= ~(RTF_CLONING | RTF_PRCLONING);
559         }
560         switch (req) {
561         case RTM_DELETE:
562                 /*
563                  * Remove the item from the tree and return it.
564                  * Complain if it is not there and do no more processing.
565                  */
566                 if ((rn = rnh->rnh_deladdr(dst, netmask, rnh)) == 0)
567                         senderr(ESRCH);
568                 if (rn->rn_flags & (RNF_ACTIVE | RNF_ROOT))
569                         panic ("rtrequest delete");
570                 rt = (struct rtentry *)rn;
571
572                 /*
573                  * Now search what's left of the subtree for any cloned
574                  * routes which might have been formed from this node.
575                  */
576                 if ((rt->rt_flags & (RTF_CLONING | RTF_PRCLONING)) &&
577                     rt_mask(rt)) {
578                         rnh->rnh_walktree_from(rnh, dst, rt_mask(rt),
579                                                rt_fixdelete, rt);
580                 }
581
582                 /*
583                  * Remove any external references we may have.
584                  * This might result in another rtentry being freed if
585                  * we held its last reference.
586                  */
587                 if (rt->rt_gwroute) {
588                         rt = rt->rt_gwroute;
589                         RTFREE(rt);
590                         (rt = (struct rtentry *)rn)->rt_gwroute = 0;
591                 }
592
593                 /*
594                  * NB: RTF_UP must be set during the search above,
595                  * because we might delete the last ref, causing
596                  * rt to get freed prematurely.
597                  *  eh? then why not just add a reference?
598                  * I'm not sure how RTF_UP helps matters. (JRE)
599                  */
600                 rt->rt_flags &= ~RTF_UP;
601
602                 /*
603                  * give the protocol a chance to keep things in sync.
604                  */
605                 if ((ifa = rt->rt_ifa) && ifa->ifa_rtrequest)
606                         ifa->ifa_rtrequest(RTM_DELETE, rt, info);
607
608                 /*
609                  * one more rtentry floating around that is not
610                  * linked to the routing table.
611                  */
612                 rttrash++;
613
614                 /*
615                  * If the caller wants it, then it can have it,
616                  * but it's up to it to free the rtentry as we won't be
617                  * doing it.
618                  */
619                 if (ret_nrt)
620                         *ret_nrt = rt;
621                 else if (rt->rt_refcnt <= 0) {
622                         rt->rt_refcnt++; /* make a 1->0 transition */
623                         rtfree(rt);
624                 }
625                 break;
626
627         case RTM_RESOLVE:
628                 if (ret_nrt == 0 || (rt = *ret_nrt) == 0)
629                         senderr(EINVAL);
630                 ifa = rt->rt_ifa;
631                 flags = rt->rt_flags &
632                     ~(RTF_CLONING | RTF_PRCLONING | RTF_STATIC);
633                 flags |= RTF_WASCLONED;
634                 gateway = rt->rt_gateway;
635                 if ((netmask = rt->rt_genmask) == 0)
636                         flags |= RTF_HOST;
637                 goto makeroute;
638
639         case RTM_ADD:
640                 if ((flags & RTF_GATEWAY) && !gateway)
641                         panic("rtrequest: GATEWAY but no gateway");
642
643                 if (info->rti_ifa == NULL && (error = rt_getifa(info)))
644                         senderr(error);
645                 ifa = info->rti_ifa;
646
647         makeroute:
648                 R_Malloc(rt, struct rtentry *, sizeof(*rt));
649                 if (rt == 0)
650                         senderr(ENOBUFS);
651                 Bzero(rt, sizeof(*rt));
652                 rt->rt_flags = RTF_UP | flags;
653                 /*
654                  * Add the gateway. Possibly re-malloc-ing the storage for it
655                  * also add the rt_gwroute if possible.
656                  */
657                 if ((error = rt_setgate(rt, dst, gateway)) != 0) {
658                         Free(rt);
659                         senderr(error);
660                 }
661
662                 /*
663                  * point to the (possibly newly malloc'd) dest address.
664                  */
665                 ndst = rt_key(rt);
666
667                 /*
668                  * make sure it contains the value we want (masked if needed).
669                  */
670                 if (netmask) {
671                         rt_maskedcopy(dst, ndst, netmask);
672                 } else
673                         Bcopy(dst, ndst, dst->sa_len);
674
675                 /*
676                  * Note that we now have a reference to the ifa.
677                  * This moved from below so that rnh->rnh_addaddr() can
678                  * examine the ifa and  ifa->ifa_ifp if it so desires.
679                  */
680                 ifa->ifa_refcnt++;
681                 rt->rt_ifa = ifa;
682                 rt->rt_ifp = ifa->ifa_ifp;
683                 /* XXX mtu manipulation will be done in rnh_addaddr -- itojun */
684
685                 rn = rnh->rnh_addaddr((caddr_t)ndst, (caddr_t)netmask,
686                                         rnh, rt->rt_nodes);
687                 if (rn == 0) {
688                         struct rtentry *rt2;
689                         /*
690                          * Uh-oh, we already have one of these in the tree.
691                          * We do a special hack: if the route that's already
692                          * there was generated by the protocol-cloning
693                          * mechanism, then we just blow it away and retry
694                          * the insertion of the new one.
695                          */
696                         rt2 = rtalloc1(dst, 0, RTF_PRCLONING);
697                         if (rt2 && rt2->rt_parent) {
698                                 rtrequest(RTM_DELETE,
699                                           (struct sockaddr *)rt_key(rt2),
700                                           rt2->rt_gateway,
701                                           rt_mask(rt2), rt2->rt_flags, 0);
702                                 RTFREE(rt2);
703                                 rn = rnh->rnh_addaddr((caddr_t)ndst,
704                                                       (caddr_t)netmask,
705                                                       rnh, rt->rt_nodes);
706                         } else if (rt2) {
707                                 /* undo the extra ref we got */
708                                 RTFREE(rt2);
709                         }
710                 }
711
712                 /*
713                  * If it still failed to go into the tree,
714                  * then un-make it (this should be a function)
715                  */
716                 if (rn == 0) {
717                         if (rt->rt_gwroute)
718                                 rtfree(rt->rt_gwroute);
719                         if (rt->rt_ifa) {
720                                 IFAFREE(rt->rt_ifa);
721                         }
722                         Free(rt_key(rt));
723                         Free(rt);
724                         senderr(EEXIST);
725                 }
726
727                 rt->rt_parent = 0;
728
729                 /*
730                  * If we got here from RESOLVE, then we are cloning
731                  * so clone the rest, and note that we
732                  * are a clone (and increment the parent's references)
733                  */
734                 if (req == RTM_RESOLVE) {
735                         rt->rt_rmx = (*ret_nrt)->rt_rmx; /* copy metrics */
736                         rt->rt_rmx.rmx_pksent = 0; /* reset packet counter */
737                         if ((*ret_nrt)->rt_flags & (RTF_CLONING | RTF_PRCLONING)) {
738                                 rt->rt_parent = (*ret_nrt);
739                                 (*ret_nrt)->rt_refcnt++;
740                         }
741                 }
742
743                 /*
744                  * if this protocol has something to add to this then
745                  * allow it to do that as well.
746                  */
747                 if (ifa->ifa_rtrequest)
748                         ifa->ifa_rtrequest(req, rt, info);
749
750                 /*
751                  * We repeat the same procedure from rt_setgate() here because
752                  * it doesn't fire when we call it there because the node
753                  * hasn't been added to the tree yet.
754                  */
755                 if (req == RTM_ADD &&
756                     !(rt->rt_flags & RTF_HOST) && rt_mask(rt) != 0) {
757                         struct rtfc_arg arg;
758                         arg.rnh = rnh;
759                         arg.rt0 = rt;
760                         rnh->rnh_walktree_from(rnh, rt_key(rt), rt_mask(rt),
761                                                rt_fixchange, &arg);
762                 }
763
764                 /*
765                  * actually return a resultant rtentry and
766                  * give the caller a single reference.
767                  */
768                 if (ret_nrt) {
769                         *ret_nrt = rt;
770                         rt->rt_refcnt++;
771                 }
772                 break;
773         default:
774                 error = EOPNOTSUPP;
775         }
776 bad:
777         splx(s);
778         return (error);
779 #undef dst
780 #undef gateway
781 #undef netmask
782 #undef ifaaddr
783 #undef ifpaddr
784 #undef flags
785 }
786
787 /*
788  * Called from rtrequest(RTM_DELETE, ...) to fix up the route's ``family''
789  * (i.e., the routes related to it by the operation of cloning).  This
790  * routine is iterated over all potential former-child-routes by way of
791  * rnh->rnh_walktree_from() above, and those that actually are children of
792  * the late parent (passed in as VP here) are themselves deleted.
793  */
794 static int
795 rt_fixdelete(rn, vp)
796         struct radix_node *rn;
797         void *vp;
798 {
799         struct rtentry *rt = (struct rtentry *)rn;
800         struct rtentry *rt0 = vp;
801
802         if (rt->rt_parent == rt0 &&
803             !(rt->rt_flags & (RTF_PINNED | RTF_CLONING | RTF_PRCLONING))) {
804                 return rtrequest(RTM_DELETE, rt_key(rt),
805                                  (struct sockaddr *)0, rt_mask(rt),
806                                  rt->rt_flags, (struct rtentry **)0);
807         }
808         return 0;
809 }
810
811 /*
812  * This routine is called from rt_setgate() to do the analogous thing for
813  * adds and changes.  There is the added complication in this case of a
814  * middle insert; i.e., insertion of a new network route between an older
815  * network route and (cloned) host routes.  For this reason, a simple check
816  * of rt->rt_parent is insufficient; each candidate route must be tested
817  * against the (mask, value) of the new route (passed as before in vp)
818  * to see if the new route matches it.
819  *
820  * XXX - it may be possible to do fixdelete() for changes and reserve this
821  * routine just for adds.  I'm not sure why I thought it was necessary to do
822  * changes this way.
823  */
824 #ifdef DEBUG
825 static int rtfcdebug = 0;
826 #endif
827
828 static int
829 rt_fixchange(rn, vp)
830         struct radix_node *rn;
831         void *vp;
832 {
833         struct rtentry *rt = (struct rtentry *)rn;
834         struct rtfc_arg *ap = vp;
835         struct rtentry *rt0 = ap->rt0;
836         struct radix_node_head *rnh = ap->rnh;
837         u_char *xk1, *xm1, *xk2, *xmp;
838         int i, len, mlen;
839
840 #ifdef DEBUG
841         if (rtfcdebug)
842                 printf("rt_fixchange: rt %p, rt0 %p\n", rt, rt0);
843 #endif
844
845         if (!rt->rt_parent ||
846             (rt->rt_flags & (RTF_PINNED | RTF_CLONING | RTF_PRCLONING))) {
847 #ifdef DEBUG
848                 if(rtfcdebug) printf("no parent, pinned or cloning\n");
849 #endif
850                 return 0;
851         }
852
853         if (rt->rt_parent == rt0) {
854 #ifdef DEBUG
855                 if(rtfcdebug) printf("parent match\n");
856 #endif
857                 return rtrequest(RTM_DELETE, rt_key(rt),
858                                  (struct sockaddr *)0, rt_mask(rt),
859                                  rt->rt_flags, (struct rtentry **)0);
860         }
861
862         /*
863          * There probably is a function somewhere which does this...
864          * if not, there should be.
865          */
866         len = imin(((struct sockaddr *)rt_key(rt0))->sa_len,
867                    ((struct sockaddr *)rt_key(rt))->sa_len);
868
869         xk1 = (u_char *)rt_key(rt0);
870         xm1 = (u_char *)rt_mask(rt0);
871         xk2 = (u_char *)rt_key(rt);
872
873         /* avoid applying a less specific route */
874         xmp = (u_char *)rt_mask(rt->rt_parent);
875         mlen = ((struct sockaddr *)rt_key(rt->rt_parent))->sa_len;
876         if (mlen > ((struct sockaddr *)rt_key(rt0))->sa_len) {
877 #ifdef DEBUG
878                 if (rtfcdebug)
879                         printf("rt_fixchange: inserting a less "
880                                "specific route\n");
881 #endif
882                 return 0;
883         }
884         for (i = rnh->rnh_treetop->rn_offset; i < mlen; i++) {
885                 if ((xmp[i] & ~(xmp[i] ^ xm1[i])) != xmp[i]) {
886 #ifdef DEBUG
887                         if (rtfcdebug)
888                                 printf("rt_fixchange: inserting a less "
889                                        "specific route\n");
890 #endif
891                         return 0;
892                 }
893         }
894
895         for (i = rnh->rnh_treetop->rn_offset; i < len; i++) {
896                 if ((xk2[i] & xm1[i]) != xk1[i]) {
897 #ifdef DEBUG
898                         if(rtfcdebug) printf("no match\n");
899 #endif
900                         return 0;
901                 }
902         }
903
904         /*
905          * OK, this node is a clone, and matches the node currently being
906          * changed/added under the node's mask.  So, get rid of it.
907          */
908 #ifdef DEBUG
909         if(rtfcdebug) printf("deleting\n");
910 #endif
911         return rtrequest(RTM_DELETE, rt_key(rt), (struct sockaddr *)0,
912                          rt_mask(rt), rt->rt_flags, (struct rtentry **)0);
913 }
914
915 #define ROUNDUP(a) (a>0 ? (1 + (((a) - 1) | (sizeof(long) - 1))) : sizeof(long))
916
917 int
918 rt_setgate(rt0, dst, gate)
919         struct rtentry *rt0;
920         struct sockaddr *dst, *gate;
921 {
922         caddr_t new, old;
923         int dlen = ROUNDUP(dst->sa_len), glen = ROUNDUP(gate->sa_len);
924         struct rtentry *rt = rt0;
925         struct radix_node_head *rnh = rt_tables[dst->sa_family];
926
927         /*
928          * A host route with the destination equal to the gateway
929          * will interfere with keeping LLINFO in the routing
930          * table, so disallow it.
931          */
932         if (((rt0->rt_flags & (RTF_HOST|RTF_GATEWAY|RTF_LLINFO)) ==
933                                         (RTF_HOST|RTF_GATEWAY)) &&
934             (dst->sa_len == gate->sa_len) &&
935             (bcmp(dst, gate, dst->sa_len) == 0)) {
936                 /*
937                  * The route might already exist if this is an RTM_CHANGE
938                  * or a routing redirect, so try to delete it.
939                  */
940                 if (rt_key(rt0))
941                         rtrequest(RTM_DELETE, (struct sockaddr *)rt_key(rt0),
942                             rt0->rt_gateway, rt_mask(rt0), rt0->rt_flags, 0);
943                 return EADDRNOTAVAIL;
944         }
945
946         /*
947          * Both dst and gateway are stored in the same malloc'd chunk
948          * (If I ever get my hands on....)
949          * if we need to malloc a new chunk, then keep the old one around
950          * till we don't need it any more.
951          */
952         if (rt->rt_gateway == 0 || glen > ROUNDUP(rt->rt_gateway->sa_len)) {
953                 old = (caddr_t)rt_key(rt);
954                 R_Malloc(new, caddr_t, dlen + glen);
955                 if (new == 0)
956                         return ENOBUFS;
957                 rt->rt_nodes->rn_key = new;
958         } else {
959                 /*
960                  * otherwise just overwrite the old one
961                  */
962                 new = rt->rt_nodes->rn_key;
963                 old = 0;
964         }
965
966         /*
967          * copy the new gateway value into the memory chunk
968          */
969         Bcopy(gate, (rt->rt_gateway = (struct sockaddr *)(new + dlen)), glen);
970
971         /*
972          * if we are replacing the chunk (or it's new) we need to
973          * replace the dst as well
974          */
975         if (old) {
976                 Bcopy(dst, new, dlen);
977                 Free(old);
978         }
979
980         /*
981          * If there is already a gwroute, it's now almost definitly wrong
982          * so drop it.
983          */
984         if (rt->rt_gwroute != NULL) {
985                 RTFREE(rt->rt_gwroute);
986                 rt->rt_gwroute = NULL;
987         }
988         /*
989          * Cloning loop avoidance:
990          * In the presence of protocol-cloning and bad configuration,
991          * it is possible to get stuck in bottomless mutual recursion
992          * (rtrequest rt_setgate rtalloc1).  We avoid this by not allowing
993          * protocol-cloning to operate for gateways (which is probably the
994          * correct choice anyway), and avoid the resulting reference loops
995          * by disallowing any route to run through itself as a gateway.
996          * This is obviously mandatory when we get rt->rt_output().
997          */
998         if (rt->rt_flags & RTF_GATEWAY) {
999                 rt->rt_gwroute = rtalloc1(gate, 1, RTF_PRCLONING);
1000                 if (rt->rt_gwroute == rt) {
1001                         RTFREE(rt->rt_gwroute);
1002                         rt->rt_gwroute = 0;
1003                         return EDQUOT; /* failure */
1004                 }
1005         }
1006
1007         /*
1008          * This isn't going to do anything useful for host routes, so
1009          * don't bother.  Also make sure we have a reasonable mask
1010          * (we don't yet have one during adds).
1011          */
1012         if (!(rt->rt_flags & RTF_HOST) && rt_mask(rt) != 0) {
1013                 struct rtfc_arg arg;
1014                 arg.rnh = rnh;
1015                 arg.rt0 = rt;
1016                 rnh->rnh_walktree_from(rnh, rt_key(rt), rt_mask(rt),
1017                                        rt_fixchange, &arg);
1018         }
1019
1020         return 0;
1021 }
1022
1023 static void
1024 rt_maskedcopy(src, dst, netmask)
1025         struct sockaddr *src, *dst, *netmask;
1026 {
1027         u_char *cp1 = (u_char *)src;
1028         u_char *cp2 = (u_char *)dst;
1029         u_char *cp3 = (u_char *)netmask;
1030         u_char *cplim = cp2 + *cp3;
1031         u_char *cplim2 = cp2 + *cp1;
1032
1033         *cp2++ = *cp1++; *cp2++ = *cp1++; /* copies sa_len & sa_family */
1034         cp3 += 2;
1035         if (cplim > cplim2)
1036                 cplim = cplim2;
1037         while (cp2 < cplim)
1038                 *cp2++ = *cp1++ & *cp3++;
1039         if (cp2 < cplim2)
1040                 bzero((caddr_t)cp2, (unsigned)(cplim2 - cp2));
1041 }
1042
1043 /*
1044  * Set up a routing table entry, normally
1045  * for an interface.
1046  */
1047 int
1048 rtinit(ifa, cmd, flags)
1049         struct ifaddr *ifa;
1050         int cmd, flags;
1051 {
1052         struct rtentry *rt;
1053         struct sockaddr *dst;
1054         struct sockaddr *deldst;
1055         struct sockaddr *netmask;
1056         struct mbuf *m = 0;
1057         struct rtentry *nrt = 0;
1058         struct radix_node_head *rnh;
1059         struct radix_node *rn;
1060         int error;
1061         struct rt_addrinfo info;
1062
1063         if (flags & RTF_HOST) {
1064                 dst = ifa->ifa_dstaddr;
1065                 netmask = NULL;
1066         } else {
1067                 dst = ifa->ifa_addr;
1068                 netmask = ifa->ifa_netmask;
1069         }
1070         /*
1071          * If it's a delete, check that if it exists, it's on the correct
1072          * interface or we might scrub a route to another ifa which would
1073          * be confusing at best and possibly worse.
1074          */
1075         if (cmd == RTM_DELETE) {
1076                 /*
1077                  * It's a delete, so it should already exist..
1078                  * If it's a net, mask off the host bits
1079                  * (Assuming we have a mask)
1080                  */
1081                 if (netmask != NULL) {
1082                         m = m_get(M_DONTWAIT, MT_SONAME);
1083                         if (m == NULL)
1084                                 return(ENOBUFS);
1085                         deldst = mtod(m, struct sockaddr *);
1086                         rt_maskedcopy(dst, deldst, netmask);
1087                         dst = deldst;
1088                 }
1089                 /*
1090                  * Look up an rtentry that is in the routing tree and
1091                  * contains the correct info.
1092                  */
1093                 if ((rnh = rt_tables[dst->sa_family]) == NULL ||
1094                     (rn = rnh->rnh_lookup(dst, netmask, rnh)) == NULL ||
1095                     (rn->rn_flags & RNF_ROOT) ||
1096                     ((struct rtentry *)rn)->rt_ifa != ifa ||
1097                     !equal(SA(rn->rn_key), dst)) {
1098                         if (m)
1099                                 (void) m_free(m);
1100                         return (flags & RTF_HOST ? EHOSTUNREACH : ENETUNREACH);
1101                 }
1102                 /* XXX */
1103 #if 0
1104                 else {
1105                         /*
1106                          * One would think that as we are deleting, and we know
1107                          * it doesn't exist, we could just return at this point
1108                          * with an "ELSE" clause, but apparently not..
1109                          */
1110                         return (flags & RTF_HOST ? EHOSTUNREACH : ENETUNREACH);
1111                 }
1112 #endif
1113         }
1114         /*
1115          * Do the actual request
1116          */
1117         bzero((caddr_t)&info, sizeof(info));
1118         info.rti_ifa = ifa;
1119         info.rti_flags = flags | ifa->ifa_flags;
1120         info.rti_info[RTAX_DST] = dst;
1121         info.rti_info[RTAX_GATEWAY] = ifa->ifa_addr;
1122         info.rti_info[RTAX_NETMASK] = netmask;
1123         error = rtrequest1(cmd, &info, &nrt);
1124         if (error == 0 && (rt = nrt) != NULL) {
1125                 /*
1126                  * notify any listening routing agents of the change
1127                  */
1128                 rt_newaddrmsg(cmd, ifa, error, rt);
1129                 if (cmd == RTM_DELETE) {
1130                         /*
1131                          * If we are deleting, and we found an entry, then
1132                          * it's been removed from the tree.. now throw it away.
1133                          */
1134                         if (rt->rt_refcnt <= 0) {
1135                                 rt->rt_refcnt++; /* make a 1->0 transition */
1136                                 rtfree(rt);
1137                         }
1138                 } else if (cmd == RTM_ADD) {
1139                         /*
1140                          * We just wanted to add it.. we don't actually
1141                          * need a reference.
1142                          */
1143                         rt->rt_refcnt--;
1144                 }
1145         }
1146         if (m)
1147                 (void) m_free(m);
1148         return (error);
1149 }
1150
1151 /* This must be before ip6_init2(), which is now SI_ORDER_MIDDLE */
1152 SYSINIT(route, SI_SUB_PROTO_DOMAIN, SI_ORDER_THIRD, route_init, 0);