* The mrouted program is covered by the license in the accompanying file
* named "LICENSE". Use of the mrouted program represents acceptance of
* the terms and conditions listed in that file.
* The mrouted program is COPYRIGHT 1989 by The Board of Trustees of
* Leland Stanford Junior University.
* $Id: route.c,v 1.5 1993/06/24 05:11:16 deering Exp $
int routes_changed
; /* 1=>some routes have changed */
int delay_change_reports
; /* 1=>postpone change reports */
static struct rtentry
*routing_table
; /* pointer to list of route entries */
static struct rtentry
*rtp
; /* pointer to a route entry */
static unsigned nroutes
; /* current number of route entries */
* Initialize the routing table and associated variables.
delay_change_reports
= FALSE
;
* Initialize the children and leaf bits for route 'r', along with the
* associated dominant, subordinate, and leaf timing data structures.
* Return TRUE if this changes the value of either the children or
static int init_children_and_leaves(r
, parent
)
register struct rtentry
*r
;
vifbitmap_t old_children
, old_leaves
;
VIFM_COPY(r
->rt_children
, old_children
);
VIFM_COPY(r
->rt_leaves
, old_leaves
);
VIFM_CLRALL(r
->rt_children
);
VIFM_CLRALL(r
->rt_leaves
);
r
->rt_flags
&= ~RTF_LEAF_TIMING
;
for (vifi
= 0, v
= uvifs
; vifi
< numvifs
; ++vifi
, ++v
) {
r
->rt_dominants
[vifi
] = 0;
r
->rt_subordinates
[vifi
] = 0;
if (vifi
!= parent
&& !(v
->uv_flags
& (VIFF_DOWN
|VIFF_DISABLED
))) {
VIFM_SET(vifi
, r
->rt_children
);
if (v
->uv_neighbors
== NULL
) {
VIFM_SET(vifi
, r
->rt_leaves
);
r
->rt_leaf_timers
[vifi
] = 0;
r
->rt_leaf_timers
[vifi
] = LEAF_CONFIRMATION_TIME
;
r
->rt_flags
|= RTF_LEAF_TIMING
;
r
->rt_leaf_timers
[vifi
] = 0;
return (!VIFM_SAME(r
->rt_children
, old_children
) ||
!VIFM_SAME(r
->rt_leaves
, old_leaves
));
* A new vif has come up -- update the children and leaf bitmaps in all route
* entries to take that into account.
void add_vif_to_routes(vifi
)
register struct rtentry
*r
;
for (r
= routing_table
; r
!= NULL
; r
= r
->rt_next
) {
if (r
->rt_metric
!= UNREACHABLE
&&
!VIFM_ISSET(vifi
, r
->rt_children
)) {
VIFM_SET(vifi
, r
->rt_children
);
r
->rt_dominants
[vifi
] = 0;
r
->rt_subordinates
[vifi
] = 0;
if (v
->uv_neighbors
== NULL
) {
VIFM_SET(vifi
, r
->rt_leaves
);
r
->rt_leaf_timers
[vifi
] = 0;
VIFM_CLR(vifi
, r
->rt_leaves
);
r
->rt_leaf_timers
[vifi
] = LEAF_CONFIRMATION_TIME
;
r
->rt_flags
|= RTF_LEAF_TIMING
;
* A vif has gone down -- expire all routes that have that vif as parent,
* and update the children bitmaps in all other route entries to take into
* account the failed vif.
void delete_vif_from_routes(vifi
)
register struct rtentry
*r
;
for (r
= routing_table
; r
!= NULL
; r
= r
->rt_next
) {
if (r
->rt_metric
!= UNREACHABLE
) {
if (vifi
== r
->rt_parent
) {
r
->rt_timer
= ROUTE_EXPIRE_TIME
;
r
->rt_metric
= UNREACHABLE
;
r
->rt_flags
|= RTF_CHANGED
;
else if (VIFM_ISSET(vifi
, r
->rt_children
)) {
VIFM_CLR(vifi
, r
->rt_children
);
VIFM_CLR(vifi
, r
->rt_leaves
);
r
->rt_subordinates
[vifi
] = 0;
r
->rt_leaf_timers
[vifi
] = 0;
r
->rt_dominants
[vifi
] = 0;
* A neighbor has failed or become unreachable. If that neighbor was
* considered a dominant or subordinate router in any route entries,
* take appropriate action.
void delete_neighbor_from_routes(addr
, vifi
)
register struct rtentry
*r
;
for (r
= routing_table
; r
!= NULL
; r
= r
->rt_next
) {
if (r
->rt_metric
!= UNREACHABLE
) {
if (r
->rt_dominants
[vifi
] == addr
) {
VIFM_SET(vifi
, r
->rt_children
);
r
->rt_dominants
[vifi
] = 0;
r
->rt_subordinates
[vifi
] = 0;
if (v
->uv_neighbors
== NULL
) {
VIFM_SET(vifi
, r
->rt_leaves
);
r
->rt_leaf_timers
[vifi
] = 0;
VIFM_CLR(vifi
, r
->rt_leaves
);
r
->rt_leaf_timers
[vifi
] = LEAF_CONFIRMATION_TIME
;
r
->rt_flags
|= RTF_LEAF_TIMING
;
else if (r
->rt_subordinates
[vifi
] == addr
) {
r
->rt_subordinates
[vifi
] = 0;
if (v
->uv_neighbors
== NULL
) {
VIFM_SET(vifi
, r
->rt_leaves
);
r
->rt_leaf_timers
[vifi
] = LEAF_CONFIRMATION_TIME
;
r
->rt_flags
|= RTF_LEAF_TIMING
;
else if (v
->uv_neighbors
== NULL
&&
r
->rt_leaf_timers
[vifi
] != 0) {
VIFM_SET(vifi
, r
->rt_leaves
);
r
->rt_leaf_timers
[vifi
] = 0;
* Prepare for a sequence of ordered route updates by initializing a pointer
* to the start of the routing table. The pointer is used to remember our
* position in the routing table in order to avoid searching from the
* beginning for each update; this relies on having the route reports in
* a single message be in the same order as the route entries in the routing
void start_route_updates()
rtp
= (struct rtentry
*)&routing_table
;
* Starting at the route entry following the one to which 'rtp' points,
* look for a route entry matching the specified origin and mask. If a
* match is found, return TRUE and leave 'rtp' pointing at the found entry.
* If no match is found, return FALSE and leave 'rtp' pointing to the route
* entry preceding the point at which the new origin should be inserted.
* This code is optimized for the normal case in which the first entry to
* be examined is the matching entry.
static int find_route(origin
, mask
)
register u_long origin
, mask
;
register struct rtentry
*r
;
if (origin
== r
->rt_origin
&& mask
== r
->rt_originmask
) {
if (ntohl(mask
) > ntohl(r
->rt_originmask
) ||
(mask
== r
->rt_originmask
&&
ntohl(origin
) > ntohl(r
->rt_origin
))) {
* Search the entire routing table, looking for an entry which conflicts
* with the given origin and mask, for example, an entry which has the same
* origin under a different mask. If a conflicting entry is found, return
* a pointer to the entry preceding it (to facilitate deletion); if no
* conflict is found, return NULL.
static struct rtentry
*find_conflicting_route(origin
, mask
)
register u_long origin
, mask
;
register struct rtentry
*r
, *prev_r
;
for (prev_r
= (struct rtentry
*)&routing_table
, r
= routing_table
;
prev_r
= r
, r
= r
->rt_next
) {
if ((origin
& r
->rt_originmask
) == r
->rt_origin
||
(r
->rt_origin
& mask
) == origin
) {
* Create a new routing table entry for the specified origin and link it into
* the routing table. The shared variable 'rtp' is assumed to point to the
* routing entry after which the new one should be inserted. It is left
* pointing to the new entry.
* Only the origin, originmask, originwidth and flags fields are initialized
* in the new route entry; the caller is responsible for filling in the the
static void create_route(origin
, mask
)
register struct rtentry
*r
;
if ((r
= (struct rtentry
*) malloc(sizeof(struct rtentry
)
+ (3 * numvifs
* sizeof(u_long
)))) == NULL
) {
log(LOG_ERR
, 0, "ran out of memory"); /* fatal */
if (((char *)&mask
)[3] != 0) r
->rt_originwidth
= 4;
else if (((char *)&mask
)[2] != 0) r
->rt_originwidth
= 3;
else if (((char *)&mask
)[1] != 0) r
->rt_originwidth
= 2;
else r
->rt_originwidth
= 1;
r
->rt_dominants
= (u_long
*)(r
+ 1);
r
->rt_subordinates
= (u_long
*)(r
->rt_dominants
+ numvifs
);
r
->rt_leaf_timers
= (u_long
*)(r
->rt_subordinates
+ numvifs
);
r
->rt_next
= rtp
->rt_next
;
* Discard the routing table entry following the one to which 'prev_r' points.
static void discard_route(prev_r
)
register struct rtentry
*prev_r
;
register struct rtentry
*r
;
prev_r
->rt_next
= r
->rt_next
;
* Process a route report for a single origin, creating or updating the
* corresponding routing table entry if necessary. 'src' is either the
* address of a neighboring router from which the report arrived, or zero
* to indicate a change of status of one of our own interfaces.
void update_route(origin
, mask
, metric
, src
, vifi
)
register struct rtentry
*r
;
* Compute an adjusted metric, taking into account the cost of the
* subnet or tunnel over which the report arrived, and normalizing
* all unreachable/poisoned metrics into a single value.
if (src
!= 0 && (metric
< 1 || metric
>= 2*UNREACHABLE
)) {
"%s reports out-of-range metric %u for origin %s",
inet_fmt(src
, s1
), metric
, inet_fmts(origin
, mask
, s2
));
adj_metric
= metric
+ uvifs
[vifi
].uv_metric
;
if (adj_metric
> UNREACHABLE
) adj_metric
= UNREACHABLE
;
* Look up the reported origin in the routing table.
if (!find_route(origin
, mask
)) {
* Don't create a new entry if the report says it's unreachable,
* or if the reported origin and mask are invalid.
if (adj_metric
== UNREACHABLE
) {
if (src
!= 0 && !inet_valid_subnet(origin
, mask
)) {
"%s reports an invalid origin (%s) and/or mask (%08x)",
inet_fmt(src
, s1
), inet_fmt(origin
, s2
), ntohl(mask
));
* If the new origin and mask are inconsistent with an entry
* already in the routing table, either ignore this update
* (if it came from another router), or delete the conflicting
* entry (if the update is for a directly-connected subnet).
if ((prev_r
= find_conflicting_route(origin
, mask
)) != NULL
) {
"%s reports a conflicting origin (%s) and mask (%08x)",
inet_fmt(src
, s1
), inet_fmt(origin
, s2
), ntohl(mask
));
"deleting route with conflicting origin (%s), mask (%08x)",
inet_fmt(r
->rt_origin
, s1
), ntohl(r
->rt_originmask
));
if (r
->rt_metric
!= UNREACHABLE
) {
if (rtp
== r
) rtp
= prev_r
;
* OK, create the new routing entry. 'rtp' will be left pointing
create_route(origin
, mask
);
rtp
->rt_metric
= UNREACHABLE
; /* temporary; updated below */
* We now have a routing entry for the reported origin. Update it?
if (r
->rt_metric
== UNREACHABLE
) {
* The routing entry is for a formerly-unreachable or new origin.
* If the report claims reachability, update the entry to use
if (adj_metric
== UNREACHABLE
)
init_children_and_leaves(r
, vifi
);
r
->rt_metric
= adj_metric
;
r
->rt_flags
|= RTF_CHANGED
;
else if (src
== r
->rt_gateway
) {
* The report has come either from the interface directly-connected
* to the origin subnet (src and r->rt_gateway both equal zero) or
* from the gateway we have chosen as the best first-hop gateway back
* towards the origin (src and r->rt_gateway not equal zero). Reset
* the route timer and, if the reported metric has changed, update
if (adj_metric
== r
->rt_metric
)
if (adj_metric
== UNREACHABLE
) {
r
->rt_timer
= ROUTE_EXPIRE_TIME
;
else if (adj_metric
< r
->rt_metric
) {
if (init_children_and_leaves(r
, vifi
)) {
r
->rt_metric
= adj_metric
;
r
->rt_flags
|= RTF_CHANGED
;
(adj_metric
< r
->rt_metric
||
(adj_metric
== r
->rt_metric
&&
r
->rt_timer
>= ROUTE_SWITCH_TIME
)))) {
* The report is for an origin we consider reachable; the report
* comes either from one of our own interfaces or from a gateway
* other than the one we have chosen as the best first-hop gateway
* back towards the origin. If the source of the update is one of
* our own interfaces, or if the origin is not a directly-connected
* subnet and the reported metric for that origin is better than
* what our routing entry says, update the entry to use the new
* gateway and metric. We also switch gateways if the reported
* metric is the same as the one in the route entry and the gateway
* associated with the route entry has not been heard from recently.
if (r
->rt_parent
!= vifi
|| adj_metric
< r
->rt_metric
) {
if (init_children_and_leaves(r
, vifi
)) {
r
->rt_metric
= adj_metric
;
r
->rt_flags
|= RTF_CHANGED
;
else if (vifi
!= r
->rt_parent
) {
* The report came from a vif other than the route's parent vif.
* Update the children and leaf info, if necessary.
if (VIFM_ISSET(vifi
, r
->rt_children
)) {
* Vif is a child vif for this route.
if (metric
< r
->rt_metric
||
(metric
== r
->rt_metric
&&
ntohl(src
) < ntohl(uvifs
[vifi
].uv_lcl_addr
))) {
* Neighbor has lower metric to origin (or has same metric
* and lower IP address) -- it becomes the dominant router,
* and vif is no longer a child for me.
VIFM_CLR(vifi
, r
->rt_children
);
VIFM_CLR(vifi
, r
->rt_leaves
);
r
->rt_dominants
[vifi
] = src
;
r
->rt_subordinates
[vifi
] = 0;
r
->rt_leaf_timers
[vifi
] = 0;
else if (metric
> UNREACHABLE
) { /* "poisoned reverse" */
* Neighbor considers this vif to be on path to route's
* origin; if no subordinate recorded, record this neighbor
* as subordinate and clear the leaf flag.
if (r
->rt_subordinates
[vifi
] == 0) {
VIFM_CLR(vifi
, r
->rt_leaves
);
r
->rt_subordinates
[vifi
] = src
;
r
->rt_leaf_timers
[vifi
] = 0;
else if (src
== r
->rt_subordinates
[vifi
]) {
* Current subordinate no longer considers this vif to be on
* path to route's origin; it is no longer a subordinate
* router, and we set the leaf confirmation timer to give
* us time to hear from other subordinates.
r
->rt_subordinates
[vifi
] = 0;
if (uvifs
[vifi
].uv_neighbors
== NULL
||
uvifs
[vifi
].uv_neighbors
->al_next
== NULL
) {
VIFM_SET(vifi
, r
->rt_leaves
);
r
->rt_leaf_timers
[vifi
] = LEAF_CONFIRMATION_TIME
;
r
->rt_flags
|= RTF_LEAF_TIMING
;
else if (src
== r
->rt_dominants
[vifi
] &&
(metric
> r
->rt_metric
||
(metric
== r
->rt_metric
&&
ntohl(src
) > ntohl(uvifs
[vifi
].uv_lcl_addr
)))) {
* Current dominant no longer has a lower metric to origin
* (or same metric and lower IP address); we adopt the vif
VIFM_SET(vifi
, r
->rt_children
);
r
->rt_dominants
[vifi
] = 0;
if (metric
> UNREACHABLE
) {
r
->rt_subordinates
[vifi
] = src
;
else if (uvifs
[vifi
].uv_neighbors
== NULL
||
uvifs
[vifi
].uv_neighbors
->al_next
== NULL
) {
VIFM_SET(vifi
, r
->rt_leaves
);
r
->rt_leaf_timers
[vifi
] = LEAF_CONFIRMATION_TIME
;
r
->rt_flags
|= RTF_LEAF_TIMING
;
* On every timer interrupt, advance the timer in each routing entry.
register struct rtentry
*r
;
register struct rtentry
*prev_r
;
for (prev_r
= (struct rtentry
*)&routing_table
, r
= routing_table
;
prev_r
= r
, r
= r
->rt_next
) {
if ((r
->rt_timer
+= TIMER_INTERVAL
) < ROUTE_EXPIRE_TIME
) {
* Route is still good; see if any leaf timers need to be
if (r
->rt_flags
& RTF_LEAF_TIMING
) {
r
->rt_flags
&= ~RTF_LEAF_TIMING
;
for (vifi
= 0; vifi
< numvifs
; ++vifi
) {
if (r
->rt_leaf_timers
[vifi
] != 0) {
* Unlike other timers, leaf timers decrement.
if ((r
->rt_leaf_timers
[vifi
] -= TIMER_INTERVAL
) == 0){
VIFM_SET(vifi
, r
->rt_leaves
);
r
->rt_flags
|= RTF_LEAF_TIMING
;
else if (r
->rt_timer
>= ROUTE_DISCARD_TIME
) {
* Time to garbage-collect the route entry.
else if (r
->rt_metric
!= UNREACHABLE
) {
* Time to expire the route entry. If the gateway is zero,
* i.e., it is a route to a directly-connected subnet, just
* set the timer back to zero; such routes expire only when
* the interface to the subnet goes down.
if (r
->rt_gateway
== 0) {
r
->rt_metric
= UNREACHABLE
;
r
->rt_flags
|= RTF_CHANGED
;
* Mark all routes as unreachable. This function is called only from
* hup() in preparation for informing all neighbors that we are going
* off the air. For consistency, we ought also to delete all reachable
* route entries from the kernel, but since we are about to exit we rely
* on the kernel to do its own cleanup -- no point in making all those
* expensive kernel calls now.
register struct rtentry
*r
;
for (r
= routing_table
; r
!= NULL
; r
= r
->rt_next
) {
r
->rt_metric
= UNREACHABLE
;
r
->rt_flags
|= RTF_CHANGED
;
* Process an incoming neighbor probe message.
void accept_probe(src
, dst
)
if ((vifi
= find_vif(src
, dst
)) == NO_VIF
) {
"ignoring probe from non-neighbor %s", inet_fmt(src
, s1
));
if (!update_neighbor(vifi
, src
, DVMRP_PROBE
))
report(ALL_ROUTES
, vifi
, src
);
* Process an incoming route report message.
void accept_report(src
, dst
, p
, datalen
)
if ((vifi
= find_vif(src
, dst
)) == NO_VIF
) {
"ignoring route report from non-neighbor %s", inet_fmt(src
, s1
));
if (!update_neighbor(vifi
, src
, DVMRP_REPORT
))
while (datalen
> 0) { /* Loop through per-mask lists. */
"received truncated route report from %s", inet_fmt(src
, s1
));
((char *)&mask
)[0] = 0xff; width
= 1;
if ((((char *)&mask
)[1] = *p
++) != 0) width
= 2;
if ((((char *)&mask
)[2] = *p
++) != 0) width
= 3;
if ((((char *)&mask
)[3] = *p
++) != 0) width
= 4;
do { /* Loop through (origin, metric) pairs */
if (datalen
< width
+ 1) {
"received truncated route report from %s", inet_fmt(src
, s1
));
for (i
= 0; i
< width
; ++i
)
((char *)&origin
)[i
] = *p
++;
update_route(origin
, mask
, (metric
& 0x7f), src
, vifi
);
} while (!(metric
& 0x80));
if (routes_changed
&& !delay_change_reports
)
report_to_all_neighbors(CHANGED_ROUTES
);
* Send a route report message to destination 'dst', via virtual interface
* 'vifi'. 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
void report(which_routes
, vifi
, dst
)
register struct rtentry
*r
;
src
= uvifs
[vifi
].uv_lcl_addr
;
p
= send_buf
+ MIN_IP_HEADER_LEN
+ IGMP_MINLEN
;
for (r
= routing_table
; r
!= NULL
; r
= r
->rt_next
) {
if (which_routes
== CHANGED_ROUTES
&& !(r
->rt_flags
& RTF_CHANGED
))
* If there is no room for this route in the current message,
* send the message and start a new one.
if (datalen
+ ((r
->rt_originmask
== mask
) ?
(r
->rt_originwidth
+ 4)) > MAX_DVMRP_DATA_LEN
) {
send_igmp(src
, dst
, IGMP_DVMRP
, DVMRP_REPORT
,
htonl(MROUTED_LEVEL
), datalen
);
p
= send_buf
+ MIN_IP_HEADER_LEN
+ IGMP_MINLEN
;
if(r
->rt_originmask
!= mask
) {
width
= r
->rt_originwidth
;
if (datalen
!= 0) *(p
-1) |= 0x80;
*p
++ = ((char *)&mask
)[1];
*p
++ = ((char *)&mask
)[2];
*p
++ = ((char *)&mask
)[3];
for (i
= 0; i
< width
; ++i
)
*p
++ = ((char *)&(r
->rt_origin
))[i
];
*p
++ = (r
->rt_parent
== vifi
&& r
->rt_metric
!= UNREACHABLE
) ?
(char)(r
->rt_metric
+ UNREACHABLE
) : /* "poisoned reverse" */
send_igmp(src
, dst
, IGMP_DVMRP
, DVMRP_REPORT
,
htonl(MROUTED_LEVEL
), datalen
);
* Send a route report message to all neighboring routers.
* 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
void report_to_all_neighbors(which_routes
)
register struct rtentry
*r
;
int routes_changed_before
;
* Remember the state of the global routes_changed flag before
* generating the reports, and clear the flag.
routes_changed_before
= routes_changed
;
for (vifi
= 0, v
= uvifs
; vifi
< numvifs
; ++vifi
, ++v
) {
if (v
->uv_neighbors
!= NULL
) {
report(which_routes
, vifi
,
(v
->uv_flags
& VIFF_TUNNEL
) ? v
->uv_rmt_addr
* If there were changed routes before we sent the reports AND
* if no new changes occurred while sending the reports, clear
* the change flags in the individual route entries. If changes
* did occur while sending the reports, new reports will be
* generated at the next timer interrupt.
if (routes_changed_before
&& !routes_changed
) {
for (r
= routing_table
; r
!= NULL
; r
= r
->rt_next
) {
r
->rt_flags
&= ~RTF_CHANGED
;
* Set a flag to inhibit further reports of changed routes until the
* next timer interrupt. This is to alleviate update storms.
delay_change_reports
= TRUE
;
* Print the contents of the routing table on file 'fp'.
register struct rtentry
*r
;
"Multicast Routing Table (%u %s)\n%s",
nroutes
, (nroutes
== 1) ? "entry" : "entries",
" Origin-Subnet From-Gateway Metric In-Vif Out-Vifs\n");
for (r
= routing_table
; r
!= NULL
; r
= r
->rt_next
) {
fprintf(fp
, " %-15s %-15s ",
inet_fmts(r
->rt_origin
, r
->rt_originmask
, s1
),
(r
->rt_gateway
== 0) ? "" : inet_fmt(r
->rt_gateway
, s2
));
fprintf(fp
, (r
->rt_metric
== UNREACHABLE
) ? " NR " : "%4u ",
for (i
= 0; i
< numvifs
; ++i
) {
if (VIFM_ISSET(i
, r
->rt_children
)) {
i
, VIFM_ISSET(i
, r
->rt_leaves
) ? '*' : ' ');