2 * Copyright (c) 1983, 1988, 1993
3 * The Regents of the University of California. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * @(#)tables.c 8.1 (Berkeley) 6/5/93
30 * $FreeBSD: src/sbin/routed/table.c,v 1.9.2.2 2000/08/14 17:00:04 sheldonh Exp $
35 static struct rt_spare
*rts_better(struct rt_entry
*);
36 static struct rt_spare rts_empty
= {0,0,0,HOPCNT_INFINITY
,0,0,0};
37 static void set_need_flash(void);
39 static void masktrim(struct sockaddr_in
*ap
);
41 static void masktrim(struct sockaddr_in_new
*ap
);
45 struct radix_node_head
*rhead
; /* root of the radix tree */
47 int need_flash
= 1; /* flash update needed
48 * start =1 to suppress the 1st
51 struct timeval age_timer
; /* next check of old routes */
52 struct timeval need_kern
= { /* need to update kernel table */
53 EPOCH
+MIN_WAITTIME
-1, 0
60 /* zap any old routes through this gateway */
64 /* It is desirable to "aggregate" routes, to combine differing routes of
65 * the same metric and next hop into a common route with a smaller netmask
66 * or to suppress redundant routes, routes that add no information to
67 * routes with smaller netmasks.
69 * A route is redundant if and only if any and all routes with smaller
70 * but matching netmasks and nets are the same. Since routes are
71 * kept sorted in the radix tree, redundant routes always come second.
73 * There are two kinds of aggregations. First, two routes of the same bit
74 * mask and differing only in the least significant bit of the network
75 * number can be combined into a single route with a coarser mask.
77 * Second, a route can be suppressed in favor of another route with a more
78 * coarse mask provided no incompatible routes with intermediate masks
79 * are present. The second kind of aggregation involves suppressing routes.
80 * A route must not be suppressed if an incompatible route exists with
81 * an intermediate mask, since the suppressed route would be covered
82 * by the intermediate.
84 * This code relies on the radix tree walk encountering routes
85 * sorted first by address, with the smallest address first.
88 struct ag_info ag_slots
[NUM_AG_SLOTS
], *ag_avail
, *ag_corsest
, *ag_finest
;
90 /* #define DEBUG_AG */
92 #define CHECK_AG() {int acnt = 0; struct ag_info *cag; \
93 for (cag = ag_avail; cag != NULL; cag = cag->ag_fine) \
95 for (cag = ag_corsest; cag != NULL; cag = cag->ag_fine) \
97 if (acnt != NUM_AG_SLOTS) { \
107 /* Output the contents of an aggregation table slot.
108 * This function must always be immediately followed with the deletion
109 * of the target slot.
112 ag_out(struct ag_info
*ag
,
113 void (*out
)(struct ag_info
*))
115 struct ag_info
*ag_cors
;
119 /* Forget it if this route should not be output for split-horizon. */
120 if (ag
->ag_state
& AGS_SPLIT_HZ
)
123 /* If we output both the even and odd twins, then the immediate parent,
124 * if it is present, is redundant, unless the parent manages to
125 * aggregate into something coarser.
126 * On successive calls, this code detects the even and odd twins,
127 * and marks the parent.
129 * Note that the order in which the radix tree code emits routes
130 * ensures that the twins are seen before the parent is emitted.
132 ag_cors
= ag
->ag_cors
;
134 && ag_cors
->ag_mask
== ag
->ag_mask
<<1
135 && ag_cors
->ag_dst_h
== (ag
->ag_dst_h
& ag_cors
->ag_mask
)) {
136 ag_cors
->ag_state
|= ((ag_cors
->ag_dst_h
== ag
->ag_dst_h
)
141 /* Skip it if this route is itself redundant.
143 * It is ok to change the contents of the slot here, since it is
144 * always deleted next.
146 if (ag
->ag_state
& AGS_REDUN0
) {
147 if (ag
->ag_state
& AGS_REDUN1
)
148 return; /* quit if fully redundant */
149 /* make it finer if it is half-redundant */
150 bit
= (-ag
->ag_mask
) >> 1;
154 } else if (ag
->ag_state
& AGS_REDUN1
) {
155 /* make it finer if it is half-redundant */
156 bit
= (-ag
->ag_mask
) >> 1;
164 ag_del(struct ag_info
*ag
)
168 if (ag
->ag_cors
== 0)
169 ag_corsest
= ag
->ag_fine
;
171 ag
->ag_cors
->ag_fine
= ag
->ag_fine
;
173 if (ag
->ag_fine
== 0)
174 ag_finest
= ag
->ag_cors
;
176 ag
->ag_fine
->ag_cors
= ag
->ag_cors
;
178 ag
->ag_fine
= ag_avail
;
185 /* Flush routes waiting for aggregation.
186 * This must not suppress a route unless it is known that among all
187 * routes with coarser masks that match it, the one with the longest
188 * mask is appropriate. This is ensured by scanning the routes
189 * in lexical order, and with the most restrictive mask first
190 * among routes to the same destination.
193 ag_flush(naddr lim_dst_h
, /* flush routes to here */
194 naddr lim_mask
, /* matching this mask */
195 void (*out
)(struct ag_info
*))
197 struct ag_info
*ag
, *ag_cors
;
202 ag
!= NULL
&& ag
->ag_mask
>= lim_mask
;
204 ag_cors
= ag
->ag_cors
;
206 /* work on only the specified routes */
207 dst_h
= ag
->ag_dst_h
;
208 if ((dst_h
& lim_mask
) != lim_dst_h
)
211 if (!(ag
->ag_state
& AGS_SUPPRESS
))
214 else for ( ; ; ag_cors
= ag_cors
->ag_cors
) {
215 /* Look for a route that can suppress the
217 if (ag_cors
== NULL
) {
218 /* failed, so output it and look for
219 * another route to work on
225 if ((dst_h
& ag_cors
->ag_mask
) == ag_cors
->ag_dst_h
) {
226 /* We found a route with a coarser mask that
227 * aggregates the current target.
229 * If it has a different next hop, it
230 * cannot replace the target, so output
233 if (ag
->ag_gate
!= ag_cors
->ag_gate
234 && !(ag
->ag_state
& AGS_FINE_GATE
)
235 && !(ag_cors
->ag_state
& AGS_CORS_GATE
)) {
240 /* If the coarse route has a good enough
241 * metric, it suppresses the target.
242 * If the suppressed target was redundant,
243 * then mark the suppressor redundant.
245 if (ag_cors
->ag_pref
<= ag
->ag_pref
) {
246 if (ag_cors
->ag_seqno
> ag
->ag_seqno
)
247 ag_cors
->ag_seqno
= ag
->ag_seqno
;
248 if (AG_IS_REDUN(ag
->ag_state
)
249 && ag_cors
->ag_mask
==ag
->ag_mask
<<1) {
250 if (ag_cors
->ag_dst_h
== dst_h
)
251 ag_cors
->ag_state
|= AGS_REDUN0
;
253 ag_cors
->ag_state
|= AGS_REDUN1
;
255 if (ag
->ag_tag
!= ag_cors
->ag_tag
)
257 if (ag
->ag_nhop
!= ag_cors
->ag_nhop
)
258 ag_cors
->ag_nhop
= 0;
264 /* That route has either been output or suppressed */
265 ag_cors
= ag
->ag_cors
;
273 /* Try to aggregate a route with previous routes.
285 void (*out
)(struct ag_info
*)) /* output using this */
287 struct ag_info
*ag
, *nag
, *ag_cors
;
293 /* Punt non-contiguous subnet masks.
295 * (X & -X) contains a single bit if and only if X is a power of 2.
296 * (X + (X & -X)) == 0 if and only if X is a power of 2.
298 if ((mask
& -mask
) + mask
!= 0) {
299 struct ag_info nc_ag
;
301 nc_ag
.ag_dst_h
= dst
;
302 nc_ag
.ag_mask
= mask
;
303 nc_ag
.ag_gate
= gate
;
304 nc_ag
.ag_nhop
= nhop
;
305 nc_ag
.ag_metric
= metric
;
306 nc_ag
.ag_pref
= pref
;
308 nc_ag
.ag_state
= state
;
309 nc_ag
.ag_seqno
= seqnum
;
314 /* Search for the right slot in the aggregation table.
319 if (ag
->ag_mask
>= mask
)
322 /* Suppress old routes (i.e. combine with compatible routes
323 * with coarser masks) as we look for the right slot in the
324 * aggregation table for the new route.
325 * A route to an address less than the current destination
326 * will not be affected by the current route or any route
327 * seen hereafter. That means it is safe to suppress it.
328 * This check keeps poor routes (e.g. with large hop counts)
329 * from preventing suppression of finer routes.
332 && ag
->ag_dst_h
< dst
333 && (ag
->ag_state
& AGS_SUPPRESS
)
334 && ag_cors
->ag_pref
<= ag
->ag_pref
335 && (ag
->ag_dst_h
& ag_cors
->ag_mask
) == ag_cors
->ag_dst_h
336 && (ag_cors
->ag_gate
== ag
->ag_gate
337 || (ag
->ag_state
& AGS_FINE_GATE
)
338 || (ag_cors
->ag_state
& AGS_CORS_GATE
))) {
339 if (ag_cors
->ag_seqno
> ag
->ag_seqno
)
340 ag_cors
->ag_seqno
= ag
->ag_seqno
;
341 /* If the suppressed target was redundant,
342 * then mark the suppressor redundant.
344 if (AG_IS_REDUN(ag
->ag_state
)
345 && ag_cors
->ag_mask
== ag
->ag_mask
<<1) {
346 if (ag_cors
->ag_dst_h
== dst
)
347 ag_cors
->ag_state
|= AGS_REDUN0
;
349 ag_cors
->ag_state
|= AGS_REDUN1
;
351 if (ag
->ag_tag
!= ag_cors
->ag_tag
)
353 if (ag
->ag_nhop
!= ag_cors
->ag_nhop
)
354 ag_cors
->ag_nhop
= 0;
360 ag
= ag_cors
->ag_fine
;
363 /* If we find the even/odd twin of the new route, and if the
364 * masks and so forth are equal, we can aggregate them.
365 * We can probably promote one of the pair.
367 * Since the routes are encountered in lexical order,
368 * the new route must be odd. However, the second or later
369 * times around this loop, it could be the even twin promoted
370 * from the even/odd pair of twins of the finer route.
373 && ag
->ag_mask
== mask
374 && ((ag
->ag_dst_h
^ dst
) & (mask
<<1)) == 0) {
376 /* Here we know the target route and the route in the current
377 * slot have the same netmasks and differ by at most the
378 * last bit. They are either for the same destination, or
379 * for an even/odd pair of destinations.
381 if (ag
->ag_dst_h
== dst
) {
382 /* We have two routes to the same destination.
383 * Routes are encountered in lexical order, so a
384 * route is never promoted until the parent route is
385 * already present. So we know that the new route is
386 * a promoted (or aggregated) pair and the route
387 * already in the slot is the explicit route.
389 * Prefer the best route if their metrics differ,
390 * or the aggregated one if not, following a sort
391 * of longest-match rule.
393 if (pref
<= ag
->ag_pref
) {
397 ag
->ag_metric
= metric
;
400 ag
->ag_state
= state
;
404 /* The sequence number controls flash updating,
405 * and should be the smaller of the two.
407 if (ag
->ag_seqno
> seqnum
)
408 ag
->ag_seqno
= seqnum
;
410 /* Some bits are set if they are set on either route,
411 * except when the route is for an interface.
413 if (!(ag
->ag_state
& AGS_IF
))
414 ag
->ag_state
|= (state
& (AGS_AGGREGATE_EITHER
420 /* If one of the routes can be promoted and the other can
421 * be suppressed, it may be possible to combine them or
422 * worthwhile to promote one.
424 * Any route that can be promoted is always
425 * marked to be eligible to be suppressed.
427 if (!((state
& AGS_AGGREGATE
)
428 && (ag
->ag_state
& AGS_SUPPRESS
))
429 && !((ag
->ag_state
& AGS_AGGREGATE
)
430 && (state
& AGS_SUPPRESS
)))
433 /* A pair of even/odd twin routes can be combined
434 * if either is redundant, or if they are via the
435 * same gateway and have the same metric.
437 if (AG_IS_REDUN(ag
->ag_state
)
438 || AG_IS_REDUN(state
)
439 || (ag
->ag_gate
== gate
440 && ag
->ag_pref
== pref
441 && (state
& ag
->ag_state
& AGS_AGGREGATE
) != 0)) {
443 /* We have both the even and odd pairs.
444 * Since the routes are encountered in order,
445 * the route in the slot must be the even twin.
447 * Combine and promote (aggregate) the pair of routes.
449 if (seqnum
> ag
->ag_seqno
)
450 seqnum
= ag
->ag_seqno
;
451 if (!AG_IS_REDUN(state
))
452 state
&= ~AGS_REDUN1
;
453 if (AG_IS_REDUN(ag
->ag_state
))
456 state
&= ~AGS_REDUN0
;
457 state
|= (ag
->ag_state
& AGS_AGGREGATE_EITHER
);
458 if (ag
->ag_tag
!= tag
)
460 if (ag
->ag_nhop
!= nhop
)
463 /* Get rid of the even twin that was already
468 } else if (ag
->ag_pref
>= pref
469 && (ag
->ag_state
& AGS_AGGREGATE
)) {
470 /* If we cannot combine the pair, maybe the route
471 * with the worse metric can be promoted.
473 * Promote the old, even twin, by giving its slot
474 * in the table to the new, odd twin.
490 /* The promoted route is even-redundant only if the
491 * even twin was fully redundant. It is not
492 * odd-redundant because the odd-twin will still be
499 ag
->ag_state
= state
;
503 ag
->ag_metric
= metric
;
510 /* take the newest sequence number */
511 if (seqnum
>= ag
->ag_seqno
)
512 seqnum
= ag
->ag_seqno
;
514 ag
->ag_seqno
= seqnum
;
517 if (!(state
& AGS_AGGREGATE
))
518 break; /* cannot promote either twin */
520 /* Promote the new, odd twin by shaving its
522 * The promoted route is odd-redundant only if the
523 * odd twin was fully redundant. It is not
524 * even-redundant because the even twin is still in
527 if (!AG_IS_REDUN(state
))
528 state
&= ~AGS_REDUN1
;
529 state
&= ~AGS_REDUN0
;
530 if (seqnum
> ag
->ag_seqno
)
531 seqnum
= ag
->ag_seqno
;
533 ag
->ag_seqno
= seqnum
;
539 if (ag_cors
== NULL
) {
544 ag_cors
= ag
->ag_cors
;
547 /* When we can no longer promote and combine routes,
548 * flush the old route in the target slot. Also flush
549 * any finer routes that we know will never be aggregated by
552 * In case we moved toward coarser masks,
553 * get back where we belong
556 && ag
->ag_mask
< mask
) {
561 /* Empty the target slot
563 if (ag
!= NULL
&& ag
->ag_mask
== mask
) {
564 ag_flush(ag
->ag_dst_h
, ag
->ag_mask
, out
);
565 ag
= (ag_cors
== NULL
) ? ag_corsest
: ag_cors
->ag_fine
;
570 if (ag
== NULL
&& ag_cors
!= ag_finest
)
572 if (ag_cors
== NULL
&& ag
!= ag_corsest
)
574 if (ag
!= NULL
&& ag
->ag_cors
!= ag_cors
)
576 if (ag_cors
!= NULL
&& ag_cors
->ag_fine
!= ag
)
581 /* Save the new route on the end of the table.
584 ag_avail
= nag
->ag_fine
;
590 nag
->ag_metric
= metric
;
593 nag
->ag_state
= state
;
594 nag
->ag_seqno
= seqnum
;
601 nag
->ag_cors
= ag_cors
;
605 ag_cors
->ag_fine
= nag
;
612 rtm_type_name(u_char type
)
614 static const char *rtm_types
[] = {
632 #define NEW_RTM_PAT "RTM type %#x"
633 static char name0
[sizeof(NEW_RTM_PAT
)+2];
636 if (type
> sizeof(rtm_types
)/sizeof(rtm_types
[0])
638 snprintf(name0
, sizeof(name0
), NEW_RTM_PAT
, type
);
641 return rtm_types
[type
-1];
647 /* Trim a mask in a sockaddr
648 * Produce a length of 0 for an address of 0.
649 * Otherwise produce the index of the first zero byte.
653 masktrim(struct sockaddr_in
*ap
)
655 masktrim(struct sockaddr_in_new
*ap
)
660 if (ap
->sin_addr
.s_addr
== 0) {
664 cp
= (char *)(&ap
->sin_addr
.s_addr
+1);
667 ap
->sin_len
= cp
- (char*)ap
+ 1;
671 /* Tell the kernel to add, delete or change a route
674 rtioctl(int action
, /* RTM_DELETE, etc */
682 struct rt_msghdr w_rtm
;
683 struct sockaddr_in w_dst
;
684 struct sockaddr_in w_gate
;
686 struct sockaddr_in w_mask
;
688 struct sockaddr_in_new w_mask
;
692 # define PAT " %-10s %s metric=%d flags=%#x"
693 # define ARGS rtm_type_name(action), rtname(dst,mask,gate), metric, flags
696 memset(&w
, 0, sizeof(w
));
697 w
.w_rtm
.rtm_msglen
= sizeof(w
);
698 w
.w_rtm
.rtm_version
= RTM_VERSION
;
699 w
.w_rtm
.rtm_type
= action
;
700 w
.w_rtm
.rtm_flags
= flags
;
701 w
.w_rtm
.rtm_seq
= ++rt_sock_seqno
;
702 w
.w_rtm
.rtm_addrs
= RTA_DST
|RTA_GATEWAY
;
703 if (metric
!= 0 || action
== RTM_CHANGE
) {
704 w
.w_rtm
.rtm_rmx
.rmx_hopcount
= metric
;
705 w
.w_rtm
.rtm_inits
|= RTV_HOPCOUNT
;
707 w
.w_dst
.sin_family
= AF_INET
;
708 w
.w_dst
.sin_addr
.s_addr
= dst
;
709 w
.w_gate
.sin_family
= AF_INET
;
710 w
.w_gate
.sin_addr
.s_addr
= gate
;
712 w
.w_dst
.sin_len
= sizeof(w
.w_dst
);
713 w
.w_gate
.sin_len
= sizeof(w
.w_gate
);
715 if (mask
== HOST_MASK
) {
716 w
.w_rtm
.rtm_flags
|= RTF_HOST
;
717 w
.w_rtm
.rtm_msglen
-= sizeof(w
.w_mask
);
719 w
.w_rtm
.rtm_addrs
|= RTA_NETMASK
;
720 w
.w_mask
.sin_addr
.s_addr
= htonl(mask
);
723 if (w
.w_mask
.sin_len
== 0)
724 w
.w_mask
.sin_len
= sizeof(long);
725 w
.w_rtm
.rtm_msglen
-= (sizeof(w
.w_mask
) - w
.w_mask
.sin_len
);
730 cc
= write(rt_sock
, &w
, w
.w_rtm
.rtm_msglen
);
733 && (action
== RTM_CHANGE
|| action
== RTM_DELETE
)) {
734 trace_act("route disappeared before" PAT
, ARGS
);
735 if (action
== RTM_CHANGE
) {
741 msglog("write(rt_sock)" PAT
": %s", ARGS
, strerror(errno
));
743 } else if (cc
!= w
.w_rtm
.rtm_msglen
) {
744 msglog("write(rt_sock) wrote %ld instead of %d for" PAT
,
745 cc
, w
.w_rtm
.rtm_msglen
, ARGS
);
750 trace_misc("write kernel" PAT
, ARGS
);
756 #define KHASH_SIZE 71 /* should be prime */
757 #define KHASH(a,m) khash_bins[((a) ^ (m)) % KHASH_SIZE]
758 static struct khash
{
759 struct khash
*k_next
;
766 #define KS_DELETE 0x002 /* need to delete the route */
767 #define KS_ADD 0x004 /* add to the kernel */
768 #define KS_CHANGE 0x008 /* tell kernel to change the route */
769 #define KS_DEL_ADD 0x010 /* delete & add to change the kernel */
770 #define KS_STATIC 0x020 /* Static flag in kernel */
771 #define KS_GATEWAY 0x040 /* G flag in kernel */
772 #define KS_DYNAMIC 0x080 /* result of redirect */
773 #define KS_DELETED 0x100 /* already deleted from kernel */
774 #define KS_CHECK 0x200
776 #define K_KEEP_LIM 30
777 time_t k_redirect_time
; /* when redirected route 1st seen */
778 } *khash_bins
[KHASH_SIZE
];
782 kern_find(naddr dst
, naddr mask
, struct khash
***ppk
)
784 struct khash
*k
, **pk
;
786 for (pk
= &KHASH(dst
,mask
); (k
= *pk
) != NULL
; pk
= &k
->k_next
) {
787 if (k
->k_dst
== dst
&& k
->k_mask
== mask
)
797 kern_add(naddr dst
, naddr mask
)
799 struct khash
*k
, **pk
;
801 k
= kern_find(dst
, mask
, &pk
);
805 k
= (struct khash
*)rtmalloc(sizeof(*k
), "kern_add");
807 memset(k
, 0, sizeof(*k
));
811 k
->k_keep
= now
.tv_sec
;
818 /* If a kernel route has a non-zero metric, check that it is still in the
819 * daemon table, and not deleted by interfaces coming and going.
822 kern_check_static(struct khash
*k
,
823 struct interface
*ifp
)
828 if (k
->k_metric
== 0)
831 memset(&new, 0, sizeof(new));
833 new.rts_gate
= k
->k_gate
;
834 new.rts_router
= (ifp
!= NULL
) ? ifp
->int_addr
: loopaddr
;
835 new.rts_metric
= k
->k_metric
;
836 new.rts_time
= now
.tv_sec
;
838 rt
= rtget(k
->k_dst
, k
->k_mask
);
840 if (!(rt
->rt_state
& RS_STATIC
))
841 rtchange(rt
, rt
->rt_state
| RS_STATIC
, &new, 0);
843 rtadd(k
->k_dst
, k
->k_mask
, RS_STATIC
, &new);
848 /* operate on a kernel entry
851 kern_ioctl(struct khash
*k
,
852 int action
, /* RTM_DELETE, etc */
858 k
->k_state
&= ~KS_DYNAMIC
;
859 if (k
->k_state
& KS_DELETED
)
861 k
->k_state
|= KS_DELETED
;
864 k
->k_state
&= ~KS_DELETED
;
867 if (k
->k_state
& KS_DELETED
) {
869 k
->k_state
&= ~KS_DELETED
;
874 rtioctl(action
, k
->k_dst
, k
->k_gate
, k
->k_mask
, k
->k_metric
, flags
);
878 /* add a route the kernel told us
881 rtm_add(struct rt_msghdr
*rtm
,
882 struct rt_addrinfo
*info
,
886 struct interface
*ifp
;
890 if (rtm
->rtm_flags
& RTF_HOST
) {
892 } else if (INFO_MASK(info
) != 0) {
893 mask
= ntohl(S_ADDR(INFO_MASK(info
)));
895 msglog("ignore %s without mask", rtm_type_name(rtm
->rtm_type
));
899 k
= kern_add(S_ADDR(INFO_DST(info
)), mask
);
900 if (k
->k_state
& KS_NEW
)
901 k
->k_keep
= now
.tv_sec
+keep
;
902 if (INFO_GATE(info
) == 0) {
903 trace_act("note %s without gateway",
904 rtm_type_name(rtm
->rtm_type
));
905 k
->k_metric
= HOPCNT_INFINITY
;
906 } else if (INFO_GATE(info
)->sa_family
!= AF_INET
) {
907 trace_act("note %s with gateway AF=%d",
908 rtm_type_name(rtm
->rtm_type
),
909 INFO_GATE(info
)->sa_family
);
910 k
->k_metric
= HOPCNT_INFINITY
;
912 k
->k_gate
= S_ADDR(INFO_GATE(info
));
913 k
->k_metric
= rtm
->rtm_rmx
.rmx_hopcount
;
916 else if (k
->k_metric
> HOPCNT_INFINITY
-1)
917 k
->k_metric
= HOPCNT_INFINITY
-1;
919 k
->k_state
&= ~(KS_DELETE
| KS_ADD
| KS_CHANGE
| KS_DEL_ADD
920 | KS_DELETED
| KS_GATEWAY
| KS_STATIC
921 | KS_NEW
| KS_CHECK
);
922 if (rtm
->rtm_flags
& RTF_GATEWAY
)
923 k
->k_state
|= KS_GATEWAY
;
924 if (rtm
->rtm_flags
& RTF_STATIC
)
925 k
->k_state
|= KS_STATIC
;
927 if (0 != (rtm
->rtm_flags
& (RTF_DYNAMIC
| RTF_MODIFIED
))) {
928 if (INFO_AUTHOR(info
) != 0
929 && INFO_AUTHOR(info
)->sa_family
== AF_INET
)
930 ifp
= iflookup(S_ADDR(INFO_AUTHOR(info
)));
934 && (ifp
== NULL
|| !(ifp
->int_state
& IS_REDIRECT_OK
))) {
935 /* Routers are not supposed to listen to redirects,
936 * so delete it if it came via an unknown interface
937 * or the interface does not have special permission.
939 k
->k_state
&= ~KS_DYNAMIC
;
940 k
->k_state
|= KS_DELETE
;
941 LIM_SEC(need_kern
, 0);
942 trace_act("mark for deletion redirected %s --> %s"
944 addrname(k
->k_dst
, k
->k_mask
, 0),
945 naddr_ntoa(k
->k_gate
),
946 ifp
? ifp
->int_name
: "unknown interface");
948 k
->k_state
|= KS_DYNAMIC
;
949 k
->k_redirect_time
= now
.tv_sec
;
950 trace_act("accept redirected %s --> %s via %s",
951 addrname(k
->k_dst
, k
->k_mask
, 0),
952 naddr_ntoa(k
->k_gate
),
953 ifp
? ifp
->int_name
: "unknown interface");
958 /* If it is not a static route, quit until the next comparison
959 * between the kernel and daemon tables, when it will be deleted.
961 if (!(k
->k_state
& KS_STATIC
)) {
962 k
->k_state
|= KS_DELETE
;
963 LIM_SEC(need_kern
, k
->k_keep
);
967 /* Put static routes with real metrics into the daemon table so
968 * they can be advertised.
970 * Find the interface toward the gateway.
972 ifp
= iflookup(k
->k_gate
);
974 msglog("static route %s --> %s impossibly lacks ifp",
975 addrname(S_ADDR(INFO_DST(info
)), mask
, 0),
976 naddr_ntoa(k
->k_gate
));
978 kern_check_static(k
, ifp
);
982 /* deal with packet loss
985 rtm_lose(struct rt_msghdr
*rtm
,
986 struct rt_addrinfo
*info
)
988 if (INFO_GATE(info
) == 0
989 || INFO_GATE(info
)->sa_family
!= AF_INET
) {
990 trace_act("ignore %s without gateway",
991 rtm_type_name(rtm
->rtm_type
));
996 rdisc_age(S_ADDR(INFO_GATE(info
)));
997 age(S_ADDR(INFO_GATE(info
)));
1001 /* Make the gateway slot of an info structure point to something
1002 * useful. If it is not already useful, but it specifies an interface,
1003 * then fill in the sockaddr_in provided and point it there.
1006 get_info_gate(struct sockaddr
**sap
,
1007 struct sockaddr_in
*in
)
1009 struct sockaddr_dl
*sdl
= (struct sockaddr_dl
*)*sap
;
1010 struct interface
*ifp
;
1014 if ((sdl
)->sdl_family
== AF_INET
)
1016 if ((sdl
)->sdl_family
!= AF_LINK
)
1019 ifp
= ifwithindex(sdl
->sdl_index
, 1);
1023 in
->sin_addr
.s_addr
= ifp
->int_addr
;
1025 in
->sin_len
= sizeof(*in
);
1027 in
->sin_family
= AF_INET
;
1028 *sap
= (struct sockaddr
*)in
;
1034 /* Clean the kernel table by copying it to the daemon image.
1035 * Eventually the daemon will delete any extra routes.
1040 static char *sysctl_buf
;
1041 static size_t sysctl_buf_size
= 0;
1045 struct rt_msghdr
*rtm
;
1046 struct sockaddr_in gate_sin
;
1047 struct rt_addrinfo info
;
1052 for (i
= 0; i
< KHASH_SIZE
; i
++) {
1053 for (k
= khash_bins
[i
]; k
!= NULL
; k
= k
->k_next
) {
1054 k
->k_state
|= KS_CHECK
;
1060 mib
[2] = 0; /* protocol */
1061 mib
[3] = 0; /* wildcard address family */
1062 mib
[4] = NET_RT_DUMP
;
1063 mib
[5] = 0; /* no flags */
1065 if ((needed
= sysctl_buf_size
) != 0) {
1066 if (sysctl(mib
, 6, sysctl_buf
,&needed
, 0, 0) >= 0)
1068 if (errno
!= ENOMEM
&& errno
!= EFAULT
)
1069 BADERR(1,"flush_kern: sysctl(RT_DUMP)");
1073 if (sysctl(mib
, 6, 0, &needed
, 0, 0) < 0)
1074 BADERR(1,"flush_kern: sysctl(RT_DUMP) estimate");
1075 /* Kludge around the habit of some systems, such as
1076 * BSD/OS 3.1, to not admit how many routes are in the
1077 * kernel, or at least to be quite wrong.
1079 needed
+= 50*(sizeof(*rtm
)+5*sizeof(struct sockaddr
));
1080 sysctl_buf
= rtmalloc(sysctl_buf_size
= needed
,
1081 "flush_kern sysctl(RT_DUMP)");
1084 lim
= sysctl_buf
+ needed
;
1085 for (next
= sysctl_buf
; next
< lim
; next
+= rtm
->rtm_msglen
) {
1086 rtm
= (struct rt_msghdr
*)next
;
1087 if (rtm
->rtm_msglen
== 0) {
1088 msglog("zero length kernel route at "
1089 " %#lx in buffer %#lx before %#lx",
1090 (u_long
)rtm
, (u_long
)sysctl_buf
, (u_long
)lim
);
1095 (struct sockaddr
*)(rtm
+1),
1096 (struct sockaddr
*)(next
+ rtm
->rtm_msglen
),
1099 if (INFO_DST(&info
) == 0
1100 || INFO_DST(&info
)->sa_family
!= AF_INET
)
1103 /* ignore ARP table entries on systems with a merged route
1106 if (rtm
->rtm_flags
& RTF_LLINFO
)
1109 /* ignore multicast addresses
1111 if (IN_MULTICAST(ntohl(S_ADDR(INFO_DST(&info
)))))
1114 if (!get_info_gate(&INFO_GATE(&info
), &gate_sin
))
1117 /* Note static routes and interface routes, and also
1118 * preload the image of the kernel table so that
1119 * we can later clean it, as well as avoid making
1120 * unneeded changes. Keep the old kernel routes for a
1121 * few seconds to allow a RIP or router-discovery
1122 * response to be heard.
1124 rtm_add(rtm
,&info
,MIN_WAITTIME
);
1127 for (i
= 0; i
< KHASH_SIZE
; i
++) {
1128 for (k
= khash_bins
[i
]; k
!= NULL
; k
= k
->k_next
) {
1129 if (k
->k_state
& KS_CHECK
) {
1130 msglog("%s --> %s disappeared from kernel",
1131 addrname(k
->k_dst
, k
->k_mask
, 0),
1132 naddr_ntoa(k
->k_gate
));
1133 del_static(k
->k_dst
, k
->k_mask
, k
->k_gate
, 1);
1140 /* Listen to announcements from the kernel
1146 struct interface
*ifp
;
1147 struct sockaddr_in gate_sin
;
1151 struct rt_msghdr rtm
;
1152 struct sockaddr addrs
[RTAX_MAX
];
1154 struct if_msghdr ifm
;
1156 char str
[100], *strp
;
1157 struct rt_addrinfo info
;
1161 cc
= read(rt_sock
, &m
, sizeof(m
));
1163 if (cc
< 0 && errno
!= EWOULDBLOCK
)
1164 LOGERR("read(rt_sock)");
1168 if (m
.r
.rtm
.rtm_version
!= RTM_VERSION
) {
1169 msglog("bogus routing message version %d",
1170 m
.r
.rtm
.rtm_version
);
1174 /* Ignore our own results.
1176 if (m
.r
.rtm
.rtm_type
<= RTM_CHANGE
1177 && m
.r
.rtm
.rtm_pid
== mypid
) {
1178 static int complained
= 0;
1180 msglog("receiving our own change messages");
1186 if (m
.r
.rtm
.rtm_type
== RTM_IFINFO
1187 || m
.r
.rtm
.rtm_type
== RTM_NEWADDR
1188 || m
.r
.rtm
.rtm_type
== RTM_DELADDR
) {
1189 ifp
= ifwithindex(m
.ifm
.ifm_index
,
1190 m
.r
.rtm
.rtm_type
!= RTM_DELADDR
);
1192 trace_act("note %s with flags %#x"
1193 " for unknown interface index #%d",
1194 rtm_type_name(m
.r
.rtm
.rtm_type
),
1198 trace_act("note %s with flags %#x for %s",
1199 rtm_type_name(m
.r
.rtm
.rtm_type
),
1203 /* After being informed of a change to an interface,
1204 * check them all now if the check would otherwise
1205 * be a long time from now, if the interface is
1206 * not known, or if the interface has been turned
1209 if (ifinit_timer
.tv_sec
-now
.tv_sec
>=CHECK_BAD_INTERVAL
1211 || ((ifp
->int_if_flags
^ m
.ifm
.ifm_flags
)
1213 ifinit_timer
.tv_sec
= now
.tv_sec
;
1217 strcpy(str
, rtm_type_name(m
.r
.rtm
.rtm_type
));
1218 strp
= &str
[strlen(str
)];
1219 if (m
.r
.rtm
.rtm_type
<= RTM_CHANGE
)
1220 strp
+= sprintf(strp
," from pid %d",m
.r
.rtm
.rtm_pid
);
1222 rt_xaddrs(&info
, m
.r
.addrs
, &m
.r
.addrs
[RTAX_MAX
],
1225 if (INFO_DST(&info
) == 0) {
1226 trace_act("ignore %s without dst", str
);
1230 if (INFO_DST(&info
)->sa_family
!= AF_INET
) {
1231 trace_act("ignore %s for AF %d", str
,
1232 INFO_DST(&info
)->sa_family
);
1236 mask
= ((INFO_MASK(&info
) != 0)
1237 ? ntohl(S_ADDR(INFO_MASK(&info
)))
1238 : (m
.r
.rtm
.rtm_flags
& RTF_HOST
)
1240 : std_mask(S_ADDR(INFO_DST(&info
))));
1242 strp
+= sprintf(strp
, ": %s",
1243 addrname(S_ADDR(INFO_DST(&info
)), mask
, 0));
1245 if (IN_MULTICAST(ntohl(S_ADDR(INFO_DST(&info
))))) {
1246 trace_act("ignore multicast %s", str
);
1250 if (m
.r
.rtm
.rtm_flags
& RTF_LLINFO
) {
1251 trace_act("ignore ARP %s", str
);
1255 if (get_info_gate(&INFO_GATE(&info
), &gate_sin
)) {
1256 gate
= S_ADDR(INFO_GATE(&info
));
1257 strp
+= sprintf(strp
, " --> %s", naddr_ntoa(gate
));
1262 if (INFO_AUTHOR(&info
) != 0)
1263 strp
+= sprintf(strp
, " by authority of %s",
1264 saddr_ntoa(INFO_AUTHOR(&info
)));
1266 switch (m
.r
.rtm
.rtm_type
) {
1270 if (m
.r
.rtm
.rtm_errno
!= 0) {
1271 trace_act("ignore %s with \"%s\" error",
1272 str
, strerror(m
.r
.rtm
.rtm_errno
));
1274 trace_act("%s", str
);
1275 rtm_add(&m
.r
.rtm
,&info
,0);
1280 if (m
.r
.rtm
.rtm_errno
!= 0
1281 && m
.r
.rtm
.rtm_errno
!= ESRCH
) {
1282 trace_act("ignore %s with \"%s\" error",
1283 str
, strerror(m
.r
.rtm
.rtm_errno
));
1285 trace_act("%s", str
);
1286 del_static(S_ADDR(INFO_DST(&info
)), mask
,
1292 trace_act("%s", str
);
1293 rtm_lose(&m
.r
.rtm
,&info
);
1297 trace_act("ignore %s", str
);
1304 /* after aggregating, note routes that belong in the kernel
1307 kern_out(struct ag_info
*ag
)
1312 /* Do not install bad routes if they are not already present.
1313 * This includes routes that had RS_NET_SYN for interfaces that
1316 if (ag
->ag_metric
== HOPCNT_INFINITY
) {
1317 k
= kern_find(htonl(ag
->ag_dst_h
), ag
->ag_mask
, 0);
1321 k
= kern_add(htonl(ag
->ag_dst_h
), ag
->ag_mask
);
1324 if (k
->k_state
& KS_NEW
) {
1325 /* will need to add new entry to the kernel table */
1326 k
->k_state
= KS_ADD
;
1327 if (ag
->ag_state
& AGS_GATEWAY
)
1328 k
->k_state
|= KS_GATEWAY
;
1329 k
->k_gate
= ag
->ag_gate
;
1330 k
->k_metric
= ag
->ag_metric
;
1334 if (k
->k_state
& KS_STATIC
)
1337 /* modify existing kernel entry if necessary */
1338 if (k
->k_gate
!= ag
->ag_gate
1339 || k
->k_metric
!= ag
->ag_metric
) {
1340 /* Must delete bad interface routes etc. to change them. */
1341 if (k
->k_metric
== HOPCNT_INFINITY
)
1342 k
->k_state
|= KS_DEL_ADD
;
1343 k
->k_gate
= ag
->ag_gate
;
1344 k
->k_metric
= ag
->ag_metric
;
1345 k
->k_state
|= KS_CHANGE
;
1348 /* If the daemon thinks the route should exist, forget
1349 * about any redirections.
1350 * If the daemon thinks the route should exist, eventually
1351 * override manual intervention by the operator.
1353 if ((k
->k_state
& (KS_DYNAMIC
| KS_DELETED
)) != 0) {
1354 k
->k_state
&= ~KS_DYNAMIC
;
1355 k
->k_state
|= (KS_ADD
| KS_DEL_ADD
);
1358 if ((k
->k_state
& KS_GATEWAY
)
1359 && !(ag
->ag_state
& AGS_GATEWAY
)) {
1360 k
->k_state
&= ~KS_GATEWAY
;
1361 k
->k_state
|= (KS_ADD
| KS_DEL_ADD
);
1362 } else if (!(k
->k_state
& KS_GATEWAY
)
1363 && (ag
->ag_state
& AGS_GATEWAY
)) {
1364 k
->k_state
|= KS_GATEWAY
;
1365 k
->k_state
|= (KS_ADD
| KS_DEL_ADD
);
1368 /* Deleting-and-adding is necessary to change aspects of a route.
1369 * Just delete instead of deleting and then adding a bad route.
1370 * Otherwise, we want to keep the route in the kernel.
1372 if (k
->k_metric
== HOPCNT_INFINITY
1373 && (k
->k_state
& KS_DEL_ADD
))
1374 k
->k_state
|= KS_DELETE
;
1376 k
->k_state
&= ~KS_DELETE
;
1383 walk_kern(struct radix_node
*rn
, __unused
struct walkarg
*argp
)
1385 #define RT ((struct rt_entry *)rn)
1390 /* Do not install synthetic routes */
1391 if (RT
->rt_state
& RS_NET_SYN
)
1394 if (!(RT
->rt_state
& RS_IF
)) {
1395 /* This is an ordinary route, not for an interface.
1398 /* aggregate, ordinary good routes without regard to
1402 ags
|= (AGS_GATEWAY
| AGS_SUPPRESS
| AGS_AGGREGATE
);
1404 /* Do not install host routes directly to hosts, to avoid
1405 * interfering with ARP entries in the kernel table.
1408 && ntohl(RT
->rt_dst
) == RT
->rt_gate
)
1412 /* This is an interface route.
1413 * Do not install routes for "external" remote interfaces.
1415 if (RT
->rt_ifp
!= 0 && (RT
->rt_ifp
->int_state
& IS_EXTERNAL
))
1418 /* Interfaces should override received routes.
1421 ags
|= (AGS_IF
| AGS_CORS_GATE
);
1423 /* If it is not an interface, or an alias for an interface,
1424 * it must be a "gateway."
1426 * If it is a "remote" interface, it is also a "gateway" to
1427 * the kernel if is not a alias.
1430 || (RT
->rt_ifp
->int_state
& IS_REMOTE
))
1431 ags
|= (AGS_GATEWAY
| AGS_SUPPRESS
| AGS_AGGREGATE
);
1434 /* If RIP is off and IRDP is on, let the route to the discovered
1435 * route suppress any RIP routes. Eventually the RIP routes
1436 * will time-out and be deleted. This reaches the steady-state
1439 if ((RT
->rt_state
& RS_RDISC
) && rip_sock
< 0)
1440 ags
|= AGS_CORS_GATE
;
1442 metric
= RT
->rt_metric
;
1443 if (metric
== HOPCNT_INFINITY
) {
1444 /* if the route is dead, so try hard to aggregate. */
1445 pref
= HOPCNT_INFINITY
;
1446 ags
|= (AGS_FINE_GATE
| AGS_SUPPRESS
);
1447 ags
&= ~(AGS_IF
| AGS_CORS_GATE
);
1450 ag_check(RT
->rt_dst
, RT
->rt_mask
, RT
->rt_gate
, 0,
1451 metric
,pref
, 0, 0, ags
, kern_out
);
1457 /* Update the kernel table to match the daemon table.
1463 struct khash
*k
, **pk
;
1466 need_kern
= age_timer
;
1468 /* Walk daemon table, updating the copy of the kernel table.
1470 rn_walktree(rhead
, walk_kern
, 0);
1471 ag_flush(0,0,kern_out
);
1473 for (i
= 0; i
< KHASH_SIZE
; i
++) {
1474 for (pk
= &khash_bins
[i
]; (k
= *pk
) != NULL
; ) {
1475 /* Do not touch static routes */
1476 if (k
->k_state
& KS_STATIC
) {
1477 kern_check_static(k
,0);
1482 /* check hold on routes deleted by the operator */
1483 if (k
->k_keep
> now
.tv_sec
) {
1484 /* ensure we check when the hold is over */
1485 LIM_SEC(need_kern
, k
->k_keep
);
1486 /* mark for the next cycle */
1487 k
->k_state
|= KS_DELETE
;
1492 if ((k
->k_state
& KS_DELETE
)
1493 && !(k
->k_state
& KS_DYNAMIC
)) {
1494 kern_ioctl(k
, RTM_DELETE
, 0);
1500 if (k
->k_state
& KS_DEL_ADD
)
1501 kern_ioctl(k
, RTM_DELETE
, 0);
1503 if (k
->k_state
& KS_ADD
) {
1504 kern_ioctl(k
, RTM_ADD
,
1505 ((0 != (k
->k_state
& (KS_GATEWAY
1507 ? RTF_GATEWAY
: 0));
1508 } else if (k
->k_state
& KS_CHANGE
) {
1509 kern_ioctl(k
, RTM_CHANGE
,
1510 ((0 != (k
->k_state
& (KS_GATEWAY
1512 ? RTF_GATEWAY
: 0));
1514 k
->k_state
&= ~(KS_ADD
|KS_CHANGE
|KS_DEL_ADD
);
1516 /* Mark this route to be deleted in the next cycle.
1517 * This deletes routes that disappear from the
1518 * daemon table, since the normal aging code
1519 * will clear the bit for routes that have not
1520 * disappeared from the daemon table.
1522 k
->k_state
|= KS_DELETE
;
1529 /* Delete a static route in the image of the kernel table.
1532 del_static(naddr dst
,
1538 struct rt_entry
*rt
;
1540 /* Just mark it in the table to be deleted next time the kernel
1542 * If it has already been deleted, mark it as such, and set its
1543 * keep-timer so that it will not be deleted again for a while.
1544 * This lets the operator delete a route added by the daemon
1545 * and add a replacement.
1547 k
= kern_find(dst
, mask
, 0);
1548 if (k
!= NULL
&& (gate
== 0 || k
->k_gate
== gate
)) {
1549 k
->k_state
&= ~(KS_STATIC
| KS_DYNAMIC
| KS_CHECK
);
1550 k
->k_state
|= KS_DELETE
;
1552 k
->k_state
|= KS_DELETED
;
1553 k
->k_keep
= now
.tv_sec
+ K_KEEP_LIM
;
1557 rt
= rtget(dst
, mask
);
1558 if (rt
!= NULL
&& (rt
->rt_state
& RS_STATIC
))
1563 /* Delete all routes generated from ICMP Redirects that use a given gateway,
1564 * as well as old redirected routes.
1567 del_redirects(naddr bad_gate
,
1574 for (i
= 0; i
< KHASH_SIZE
; i
++) {
1575 for (k
= khash_bins
[i
]; k
!= NULL
; k
= k
->k_next
) {
1576 if (!(k
->k_state
& KS_DYNAMIC
)
1577 || (k
->k_state
& KS_STATIC
))
1580 if (k
->k_gate
!= bad_gate
1581 && k
->k_redirect_time
> old
1585 k
->k_state
|= KS_DELETE
;
1586 k
->k_state
&= ~KS_DYNAMIC
;
1587 need_kern
.tv_sec
= now
.tv_sec
;
1588 trace_act("mark redirected %s --> %s for deletion",
1589 addrname(k
->k_dst
, k
->k_mask
, 0),
1590 naddr_ntoa(k
->k_gate
));
1596 /* Start the daemon tables.
1598 extern int max_keylen
;
1606 /* Initialize the radix trees */
1607 max_keylen
= sizeof(struct sockaddr_in
);
1609 rn_inithead(&rhead
, 32);
1611 /* mark all of the slots in the table free */
1612 ag_avail
= ag_slots
;
1613 for (ag
= ag_slots
, i
= 1; i
< NUM_AG_SLOTS
; i
++) {
1620 #ifdef _HAVE_SIN_LEN
1621 static struct sockaddr_in dst_sock
= {sizeof(dst_sock
), AF_INET
, 0, {0}, {0}};
1622 static struct sockaddr_in mask_sock
= {sizeof(mask_sock
), AF_INET
, 0, {0}, {0}};
1624 static struct sockaddr_in_new dst_sock
= {_SIN_ADDR_SIZE
, AF_INET
};
1625 static struct sockaddr_in_new mask_sock
= {_SIN_ADDR_SIZE
, AF_INET
};
1630 set_need_flash(void)
1634 /* Do not send the flash update immediately. Wait a little
1635 * while to hear from other routers.
1637 no_flash
.tv_sec
= now
.tv_sec
+ MIN_WAITTIME
;
1642 /* Get a particular routing table entry
1645 rtget(naddr dst
, naddr mask
)
1647 struct rt_entry
*rt
;
1649 dst_sock
.sin_addr
.s_addr
= dst
;
1650 mask_sock
.sin_addr
.s_addr
= htonl(mask
);
1651 masktrim(&mask_sock
);
1652 rt
= (struct rt_entry
*)rhead
->rnh_lookup(&dst_sock
,&mask_sock
,rhead
);
1654 || rt
->rt_dst
!= dst
1655 || rt
->rt_mask
!= mask
)
1662 /* Find a route to dst as the kernel would.
1667 dst_sock
.sin_addr
.s_addr
= dst
;
1668 return (struct rt_entry
*)rhead
->rnh_matchaddr(&dst_sock
, rhead
);
1672 /* add a route to the table
1677 u_int state
, /* rt_state for the entry */
1678 struct rt_spare
*new)
1680 struct rt_entry
*rt
;
1683 struct rt_spare
*rts
;
1685 rt
= (struct rt_entry
*)rtmalloc(sizeof (*rt
), "rtadd");
1686 memset(rt
, 0, sizeof(*rt
));
1687 for (rts
= rt
->rt_spares
, i
= NUM_SPARES
; i
!= 0; i
--, rts
++)
1688 rts
->rts_metric
= HOPCNT_INFINITY
;
1690 rt
->rt_nodes
->rn_key
= (caddr_t
)&rt
->rt_dst_sock
;
1692 rt
->rt_dst_sock
.sin_family
= AF_INET
;
1693 #ifdef _HAVE_SIN_LEN
1694 rt
->rt_dst_sock
.sin_len
= dst_sock
.sin_len
;
1696 if (mask
!= HOST_MASK
) {
1697 smask
= std_mask(dst
);
1698 if ((smask
& ~mask
) == 0 && mask
> smask
)
1701 mask_sock
.sin_addr
.s_addr
= htonl(mask
);
1702 masktrim(&mask_sock
);
1704 rt
->rt_state
= state
;
1705 rt
->rt_spares
[0] = *new;
1706 rt
->rt_time
= now
.tv_sec
;
1707 rt
->rt_poison_metric
= HOPCNT_INFINITY
;
1708 rt
->rt_seqno
= update_seqno
;
1710 if (++total_routes
== MAX_ROUTES
)
1711 msglog("have maximum (%d) routes", total_routes
);
1713 trace_add_del("Add", rt
);
1715 need_kern
.tv_sec
= now
.tv_sec
;
1718 if (0 == rhead
->rnh_addaddr(&rt
->rt_dst_sock
, &mask_sock
,
1719 rhead
, rt
->rt_nodes
)) {
1720 msglog("rnh_addaddr() failed for %s mask=%#lx",
1721 naddr_ntoa(dst
), (u_long
)mask
);
1727 /* notice a changed route
1730 rtchange(struct rt_entry
*rt
,
1731 u_int state
, /* new state bits */
1732 struct rt_spare
*new,
1735 if (rt
->rt_metric
!= new->rts_metric
) {
1736 /* Fix the kernel immediately if it seems the route
1737 * has gone bad, since there may be a working route that
1738 * aggregates this route.
1740 if (new->rts_metric
== HOPCNT_INFINITY
) {
1741 need_kern
.tv_sec
= now
.tv_sec
;
1742 if (new->rts_time
>= now
.tv_sec
- EXPIRE_TIME
)
1743 new->rts_time
= now
.tv_sec
- EXPIRE_TIME
;
1745 rt
->rt_seqno
= update_seqno
;
1749 if (rt
->rt_gate
!= new->rts_gate
) {
1750 need_kern
.tv_sec
= now
.tv_sec
;
1751 rt
->rt_seqno
= update_seqno
;
1755 state
|= (rt
->rt_state
& RS_SUBNET
);
1757 /* Keep various things from deciding ageless routes are stale.
1759 if (!AGE_RT(state
, new->rts_ifp
))
1760 new->rts_time
= now
.tv_sec
;
1763 trace_change(rt
, state
, new,
1764 label
? label
: "Chg ");
1766 rt
->rt_state
= state
;
1767 rt
->rt_spares
[0] = *new;
1771 /* check for a better route among the spares
1773 static struct rt_spare
*
1774 rts_better(struct rt_entry
*rt
)
1776 struct rt_spare
*rts
, *rts1
;
1779 /* find the best alternative among the spares */
1780 rts
= rt
->rt_spares
+1;
1781 for (i
= NUM_SPARES
, rts1
= rts
+1; i
> 2; i
--, rts1
++) {
1782 if (BETTER_LINK(rt
,rts1
,rts
))
1790 /* switch to a backup route
1793 rtswitch(struct rt_entry
*rt
,
1794 struct rt_spare
*rts
)
1796 struct rt_spare swap
;
1800 /* Do not change permanent routes */
1801 if (0 != (rt
->rt_state
& (RS_MHOME
| RS_STATIC
| RS_RDISC
1802 | RS_NET_SYN
| RS_IF
)))
1805 /* find the best alternative among the spares */
1807 rts
= rts_better(rt
);
1809 /* Do not bother if it is not worthwhile.
1811 if (!BETTER_LINK(rt
, rts
, rt
->rt_spares
))
1814 swap
= rt
->rt_spares
[0];
1815 sprintf(label
, "Use #%d", (int)(rts
- rt
->rt_spares
));
1816 rtchange(rt
, rt
->rt_state
& ~(RS_NET_SYN
| RS_RDISC
), rts
, label
);
1817 if (swap
.rts_metric
== HOPCNT_INFINITY
) {
1826 rtdelete(struct rt_entry
*rt
)
1832 trace_add_del("Del", rt
);
1834 k
= kern_find(rt
->rt_dst
, rt
->rt_mask
, 0);
1836 k
->k_state
|= KS_DELETE
;
1837 need_kern
.tv_sec
= now
.tv_sec
;
1840 dst_sock
.sin_addr
.s_addr
= rt
->rt_dst
;
1841 mask_sock
.sin_addr
.s_addr
= htonl(rt
->rt_mask
);
1842 masktrim(&mask_sock
);
1843 if (rt
!= (struct rt_entry
*)rhead
->rnh_deladdr(&dst_sock
, &mask_sock
,
1845 msglog("rnh_deladdr() failed");
1854 rts_delete(struct rt_entry
*rt
,
1855 struct rt_spare
*rts
)
1857 trace_upslot(rt
, rts
, &rts_empty
);
1862 /* Get rid of a bad route, and try to switch to a replacement.
1865 rtbad(struct rt_entry
*rt
)
1867 struct rt_spare
new;
1869 /* Poison the route */
1870 new = rt
->rt_spares
[0];
1871 new.rts_metric
= HOPCNT_INFINITY
;
1872 rtchange(rt
, rt
->rt_state
& ~(RS_IF
| RS_LOCAL
| RS_STATIC
), &new, 0);
1877 /* Junk a RS_NET_SYN or RS_LOCAL route,
1878 * unless it is needed by another interface.
1881 rtbad_sub(struct rt_entry
*rt
)
1883 struct interface
*ifp
, *ifp1
;
1884 struct intnet
*intnetp
;
1891 if (rt
->rt_state
& RS_LOCAL
) {
1892 /* Is this the route through loopback for the interface?
1893 * If so, see if it is used by any other interfaces, such
1894 * as a point-to-point interface with the same local address.
1896 for (ifp
= ifnet
; ifp
!= NULL
; ifp
= ifp
->int_next
) {
1897 /* Retain it if another interface needs it.
1899 if (ifp
->int_addr
== rt
->rt_ifp
->int_addr
) {
1908 if (!(state
& RS_LOCAL
)) {
1909 /* Retain RIPv1 logical network route if there is another
1910 * interface that justifies it.
1912 if (rt
->rt_state
& RS_NET_SYN
) {
1913 for (ifp
= ifnet
; ifp
!= NULL
; ifp
= ifp
->int_next
) {
1914 if ((ifp
->int_state
& IS_NEED_NET_SYN
)
1915 && rt
->rt_mask
== ifp
->int_std_mask
1916 && rt
->rt_dst
== ifp
->int_std_addr
) {
1917 state
|= RS_NET_SYN
;
1924 /* or if there is an authority route that needs it. */
1925 for (intnetp
= intnets
;
1927 intnetp
= intnetp
->intnet_next
) {
1928 if (intnetp
->intnet_addr
== rt
->rt_dst
1929 && intnetp
->intnet_mask
== rt
->rt_mask
) {
1930 state
|= (RS_NET_SYN
| RS_NET_INT
);
1936 if (ifp1
!= NULL
|| (state
& RS_NET_SYN
)) {
1937 struct rt_spare
new = rt
->rt_spares
[0];
1939 rtchange(rt
, ((rt
->rt_state
& ~(RS_NET_SYN
|RS_LOCAL
)) | state
),
1947 /* Called while walking the table looking for sick interfaces
1948 * or after a time change.
1952 walk_bad(struct radix_node
*rn
, __unused
struct walkarg
*argp
)
1954 #define RT ((struct rt_entry *)rn)
1955 struct rt_spare
*rts
;
1959 /* fix any spare routes through the interface
1961 rts
= RT
->rt_spares
;
1962 for (i
= NUM_SPARES
; i
!= 1; i
--) {
1964 if (rts
->rts_metric
< HOPCNT_INFINITY
1965 && (rts
->rts_ifp
== 0
1966 || (rts
->rts_ifp
->int_state
& IS_BROKE
)))
1967 rts_delete(RT
, rts
);
1970 /* Deal with the main route
1972 /* finished if it has been handled before or if its interface is ok
1974 if (RT
->rt_ifp
== 0 || !(RT
->rt_ifp
->int_state
& IS_BROKE
))
1977 /* Bad routes for other than interfaces are easy.
1979 if (0 == (RT
->rt_state
& (RS_IF
| RS_NET_SYN
| RS_LOCAL
))) {
1990 /* Check the age of an individual route.
1994 walk_age(struct radix_node
*rn
, __unused
struct walkarg
*argp
)
1996 #define RT ((struct rt_entry *)rn)
1997 struct interface
*ifp
;
1998 struct rt_spare
*rts
;
2002 /* age all of the spare routes, including the primary route
2005 rts
= RT
->rt_spares
;
2006 for (i
= NUM_SPARES
; i
!= 0; i
--, rts
++) {
2009 if (i
== NUM_SPARES
) {
2010 if (!AGE_RT(RT
->rt_state
, ifp
)) {
2011 /* Keep various things from deciding ageless
2014 rts
->rts_time
= now
.tv_sec
;
2018 /* forget RIP routes after RIP has been turned off.
2026 /* age failing routes
2028 if (age_bad_gate
== rts
->rts_gate
2029 && rts
->rts_time
>= now_stale
) {
2030 rts
->rts_time
-= SUPPLY_INTERVAL
;
2033 /* trash the spare routes when they go bad */
2034 if (rts
->rts_metric
< HOPCNT_INFINITY
2035 && now_garbage
> rts
->rts_time
2037 rts_delete(RT
, rts
);
2041 /* finished if the active route is still fresh */
2042 if (now_stale
<= RT
->rt_time
)
2045 /* try to switch to an alternative */
2048 /* Delete a dead route after it has been publically mourned. */
2049 if (now_garbage
> RT
->rt_time
) {
2054 /* Start poisoning a bad route before deleting it. */
2055 if (now
.tv_sec
- RT
->rt_time
> EXPIRE_TIME
) {
2056 struct rt_spare
new = RT
->rt_spares
[0];
2057 new.rts_metric
= HOPCNT_INFINITY
;
2058 rtchange(RT
, RT
->rt_state
, &new, 0);
2064 /* Watch for dead routes and interfaces.
2069 struct interface
*ifp
;
2072 /* If not listening to RIP, there is no need to age the routes in
2075 age_timer
.tv_sec
= (now
.tv_sec
2076 + ((rip_sock
< 0) ? NEVER
: SUPPLY_INTERVAL
));
2078 /* Check for dead IS_REMOTE interfaces by timing their
2081 for (ifp
= ifnet
; ifp
; ifp
= ifp
->int_next
) {
2082 if (!(ifp
->int_state
& IS_REMOTE
))
2085 /* ignore unreachable remote interfaces */
2086 if (!check_remote(ifp
))
2089 /* Restore remote interface that has become reachable
2091 if (ifp
->int_state
& IS_BROKE
)
2092 if_ok(ifp
, "remote ");
2094 if (ifp
->int_act_time
!= NEVER
2095 && now
.tv_sec
- ifp
->int_act_time
> EXPIRE_TIME
) {
2096 msglog("remote interface %s to %s timed out after"
2099 naddr_ntoa(ifp
->int_dstaddr
),
2100 (now
.tv_sec
- ifp
->int_act_time
)/60,
2101 (now
.tv_sec
- ifp
->int_act_time
)%60);
2105 /* If we have not heard from the other router
2108 if (now
.tv_sec
>= ifp
->int_query_time
) {
2109 ifp
->int_query_time
= NEVER
;
2115 age_bad_gate
= bad_gate
;
2116 rn_walktree(rhead
, walk_age
, 0);
2118 /* delete old redirected routes to keep the kernel table small
2119 * and prevent blackholes
2121 del_redirects(bad_gate
, now
.tv_sec
-STALE_TIME
);
2123 /* Update the kernel routing table. */
2126 /* poke reticent remote gateways */