static char sccsid
[] = "@(#)routed.c 4.9 %G%";
* Routing Table Management Daemon
/* casts to keep lint happy */
#define insque(q,p) _insque((caddr_t)q,(caddr_t)p)
#define remque(q) _remque((caddr_t)q)
(bcmp((caddr_t)(a1), (caddr_t)(a2), sizeof (struct sockaddr)) == 0)
#define min(a,b) ((a)>(b)?(b):(a))
struct sockaddr_in myaddr
= { AF_INET
, IPPORT_ROUTESERVER
};
int supplier
; /* process should supply updates */
int initializing
; /* stem off broadcast() calls */
int install
= 1; /* if 1 call kernel */
int lookforinterfaces
= 1;
char packet
[MAXPACKETSIZE
];
struct in_addr
if_makeaddr();
struct ifnet
*if_ifwithaddr(), *if_ifwithnet();
extern int errno
, exit();
{ int t
= open("/dev/tty", 2);
(void) freopen("/etc/routerlog", "a", stdout
);
(void) dup2(fileno(stdout
), 2);
myaddr
.sin_port
= htons(myaddr
.sin_port
);
s
= socket(SOCK_DGRAM
, 0, &myaddr
, 0);
if (strcmp(*argv
, "-s") == 0)
else if (strcmp(*argv
, "-q") == 0)
* Listen for routing packets
cc
= receive(s
, &from
, packet
, sizeof (packet
));
if (cc
< 0 && errno
!= EINTR
)
* Look in a file for any gateways we should configure
* outside the directly connected ones. This is a kludge,
* but until we can find out about gateways on the "other side"
* of the ARPANET using GGP, it's a must.
* We don't really know the distance to the gateway, so we
* assume it's a neighbor.
struct sockaddr_in dst
, gate
;
FILE *fp
= fopen("/etc/gateways", "r");
bzero((char *)&dst
, sizeof (dst
));
bzero((char *)&gate
, sizeof (gate
));
dst
.sin_family
= AF_INET
;
gate
.sin_family
= AF_INET
;
while (fscanf(fp
, "%x %x", &dst
.sin_addr
.s_addr
,
&gate
.sin_addr
.s_addr
) != EOF
) {
rtadd((struct sockaddr
*)&dst
, (struct sockaddr
*)&gate
, 1);
rt
= rtlookup((struct sockaddr
*)&dst
);
rt
->rt_state
|= RTS_SILENT
;
* o handle timers on table entries,
* o invalidate entries which haven't been updated in a while,
* o delete entries which are too old,
* o retry ioctl's which weren't successful the first
* time due to the kernel entry being busy
* o if we're an internetwork router, supply routing updates
register struct rthash
*rh
;
register struct rt_entry
*rt
;
struct rthash
*base
= hosthash
;
printf(">>> time %d >>>\n", timeval
);
for (rh
= base
; rh
< &base
[ROUTEHASHSIZ
]; rh
++) {
for (; rt
!= (struct rt_entry
*)rh
; rt
= rt
->rt_forw
) {
* If the host is indicated to be
* "silent" (i.e. it's one we got
* from the initialization file),
* don't time out it's entry.
if ((rt
->rt_state
& RTS_SILENT
) == 0)
rt
->rt_timer
+= TIMER_RATE
;
* If the entry should be deleted
* attempt to do so and reclaim space.
if (rt
->rt_timer
>= GARBAGE_TIME
||
(rt
->rt_state
& RTS_DELRT
)) {
* If we haven't heard from the router
* in a long time indicate the route is
if (rt
->rt_timer
>= EXPIRE_TIME
)
rt
->rt_metric
= HOPCNT_INFINITY
;
if (rt
->rt_state
& RTS_CHGRT
)
if (!ioctl(s
, SIOCCHGRT
,(char *)&rt
->rt_rt
) ||
rt
->rt_state
&= ~RTS_CHGRT
;
* Try to add the route to the kernel tables.
* If this fails because the entry already exists
* (perhaps because someone manually added it)
* change the add to a change. If the operation
* fails otherwise (likely because the entry is
* in use), retry the operation a few more times.
if (rt
->rt_state
& RTS_ADDRT
) {
if (!ioctl(s
, SIOCADDRT
,(char *)&rt
->rt_rt
)) {
rt
->rt_state
&= ~RTS_ADDRT
;
rt
->rt_state
|= RTS_CHGRT
;
(EXPIRE_TIME
/TIMER_RATE
);
rt
->rt_state
&= ~RTS_ADDRT
;
if (lookforinterfaces
&& (timeval
% CHECK_INTERVAL
) == 0)
if (supplier
&& (timeval
% SUPPLY_INTERVAL
) == 0)
printf("<<< time %d <<<\n", timeval
);
* Find the network interfaces attached to this machine.
* (1) initialize the routing tables, as done by the kernel.
* (2) ignore incoming packets we send.
* (3) figure out broadcast capability and addresses.
* (4) figure out if we're an internetwork gateway.
* We don't handle anything but Internet addresses.
* Note: this routine may be called periodically to
* scan for new interfaces. In fact, the timer routine
* does so based on the flag lookforinterfaces. The
* flag performnlist is set whenever something odd occurs
* while scanning the kernel; this is likely to occur
* if /vmunix isn't up to date (e.g. someone booted /ovmunix).
struct ifnet ifstruct
, *next
;
register struct sockaddr
*dst
;
if (nl
[N_IFNET
].n_value
== 0) {
printf("ifnet: not in namelist\n");
kmem
= open("/dev/kmem", 0);
if (lseek(kmem
, (long)nl
[N_IFNET
].n_value
, 0) == -1 ||
read(kmem
, (char *)&ifp
, sizeof (ifp
)) != sizeof (ifp
)) {
bzero((char *)&net
, sizeof (net
));
net
.sin_family
= AF_INET
;
if (lseek(kmem
, (long)ifp
, 0) == -1 ||
read(kmem
, (char *)&ifstruct
, sizeof (ifstruct
)) !=
lookforinterfaces
= performnlist
= 1;
if ((ifp
->if_flags
& IFF_UP
) == 0) {
if (ifp
->if_addr
.sa_family
!= AF_INET
)
/* ignore software loopback networks. */
if (ifp
->if_net
== LOOPBACKNET
)
/* check if we already know about this one */
if (if_ifwithaddr(&ifstruct
.if_addr
)) {
ifp
= (struct ifnet
*)malloc(sizeof (struct ifnet
));
printf("routed: out of memory\n");
bcopy((char *)&ifstruct
, (char *)ifp
, sizeof (struct ifnet
));
* Count the # of directly connected networks
* and point to point links which aren't looped
* back to ourself. This is used below to
* decide if we should be a routing "supplier".
if ((ifp
->if_flags
& IFF_POINTOPOINT
) == 0 ||
if_ifwithaddr(&ifp
->if_dstaddr
) == 0)
if (ifp
->if_flags
& IFF_POINTOPOINT
)
net
.sin_addr
= if_makeaddr(ifp
->if_net
, INADDR_ANY
);
dst
= (struct sockaddr
*)&net
;
rtadd(dst
, &ifp
->if_addr
, 0);
* Send a request message to all directly
* connected hosts and networks.
register struct rip
*msg
= (struct rip
*)packet
;
msg
->rip_cmd
= RIPCMD_REQUEST
;
msg
->rip_nets
[0].rip_dst
.sa_family
= AF_UNSPEC
;
msg
->rip_nets
[0].rip_metric
= HOPCNT_INFINITY
;
* Broadcast a new, or modified, routing table entry
* to all directly connected hosts and networks.
struct rip
*msg
= (struct rip
*)packet
;
msg
->rip_cmd
= RIPCMD_RESPONSE
;
msg
->rip_nets
[0].rip_dst
= entry
->rt_dst
;
msg
->rip_nets
[0].rip_metric
= min(entry
->rt_metric
+1, HOPCNT_INFINITY
);
* Send "packet" to all neighbors.
register struct rthash
*rh
;
register struct rt_entry
*rt
;
register struct sockaddr
*dst
;
struct rthash
*base
= hosthash
;
for (rh
= base
; rh
< &base
[ROUTEHASHSIZ
]; rh
++)
for (rt
= rh
->rt_forw
; rt
!= (struct rt_entry
*)rh
; rt
= rt
->rt_forw
) {
if ((rt
->rt_state
& RTS_SILENT
) || rt
->rt_metric
> 0)
if (rt
->rt_ifp
&& (rt
->rt_ifp
->if_flags
& IFF_BROADCAST
))
dst
= &rt
->rt_ifp
->if_broadaddr
;
(*afswitch
[dst
->sa_family
].af_output
)(dst
, sizeof (struct rip
));
* Supply all directly connected neighbors with the
* current state of the routing tables.
register struct rt_entry
*rt
;
register struct rthash
*rh
;
register struct sockaddr
*dst
;
struct rthash
*base
= hosthash
;
for (rh
= base
; rh
< &base
[ROUTEHASHSIZ
]; rh
++)
for (rt
= rh
->rt_forw
; rt
!= (struct rt_entry
*)rh
; rt
= rt
->rt_forw
) {
if ((rt
->rt_state
& RTS_SILENT
) || rt
->rt_metric
> 0)
if (rt
->rt_ifp
&& (rt
->rt_ifp
->if_flags
& IFF_BROADCAST
))
dst
= &rt
->rt_ifp
->if_broadaddr
;
* Supply routing information to target "sa".
struct rip
*msg
= (struct rip
*)packet
;
struct netinfo
*n
= msg
->rip_nets
;
register struct rthash
*rh
;
register struct rt_entry
*rt
;
struct rthash
*base
= hosthash
;
int (*output
)() = afswitch
[sa
->sa_family
].af_output
;
msg
->rip_cmd
= RIPCMD_RESPONSE
;
for (rh
= base
; rh
< &base
[ROUTEHASHSIZ
]; rh
++)
for (rt
= rh
->rt_forw
; rt
!= (struct rt_entry
*)rh
; rt
= rt
->rt_forw
) {
* Flush packet out if not enough room for
* another routing table entry.
size
= (char *)n
- packet
;
if (size
> MAXPACKETSIZE
- sizeof (struct netinfo
)) {
n
->rip_metric
= min(rt
->rt_metric
+ 1, HOPCNT_INFINITY
);
(*output
)(sa
, (char *)n
- packet
);
* Respond to a routing info request.
register struct rip
*msg
= (struct rip
*)packet
;
struct netinfo
*np
= msg
->rip_nets
;
size
-= 4 * sizeof (char);
if (size
< sizeof (struct netinfo
))
size
-= sizeof (struct netinfo
);
if (np
->rip_dst
.sa_family
== AF_UNSPEC
&&
np
->rip_metric
== HOPCNT_INFINITY
&& size
== 0) {
rt
= rtlookup(&np
->rip_dst
);
np
->rip_metric
= rt
== 0 ?
HOPCNT_INFINITY
: min(rt
->rt_metric
+1, HOPCNT_INFINITY
);
np
++, newsize
+= sizeof (struct netinfo
);
msg
->rip_cmd
= RIPCMD_RESPONSE
;
(*afswitch
[from
->sa_family
].af_output
)(from
, newsize
);
* Handle an incoming routing packet.
register struct rip
*msg
= (struct rip
*)packet
;
/* verify message came from a priviledged port */
if ((*afswitch
[from
->sa_family
].af_portmatch
)(from
) == 0)
* Extraneous information like Internet ports
* must first be purged from the sender's address for
* pattern matching below.
(*afswitch
[from
->sa_family
].af_canon
)(from
);
printf("input from %x\n",
((struct sockaddr_in
*)from
)->sin_addr
);
* If response packet is from ourselves, use it only
* to reset timer on entry. Otherwise, we'd believe
* it as gospel (since it comes from the router) and
* unknowingly update the metric to show the outgoing
* cost (higher than our real cost). I guess the protocol
* spec doesn't address this because Xerox Ethernets
* don't hear their own broadcasts?
if (if_ifwithaddr(from
)) {
size
-= 4 * sizeof (char);
for (; size
> 0; size
-= sizeof (struct netinfo
), n
++) {
if (size
< sizeof (struct netinfo
))
printf("dst %x hc %d...",
((struct sockaddr_in
*)&n
->rip_dst
)->sin_addr
,
rt
= rtlookup(&n
->rip_dst
);
* Unknown entry, add it to the tables only if
if (n
->rip_metric
< HOPCNT_INFINITY
)
rtadd(&n
->rip_dst
, from
, n
->rip_metric
);
printf("ours: gate %x hc %d timer %d\n",
((struct sockaddr_in
*)&rt
->rt_gateway
)->sin_addr
,
rt
->rt_metric
, rt
->rt_timer
);
* Update the entry if one of the following is true:
* (1) The update came directly from the gateway.
* (2) A shorter path is provided.
* (3) The entry hasn't been updated in a while
* and a path of equivalent cost is offered
* (with the cost finite).
if (equal(from
, &rt
->rt_gateway
) ||
rt
->rt_metric
> n
->rip_metric
||
(rt
->rt_timer
> (EXPIRE_TIME
/2) &&
rt
->rt_metric
== n
->rip_metric
&&
rt
->rt_metric
< HOPCNT_INFINITY
)) {
rtchange(rt
, from
, n
->rip_metric
);
register struct rthash
*rh
;
for (rh
= nethash
; rh
< &nethash
[ROUTEHASHSIZ
]; rh
++)
rh
->rt_forw
= rh
->rt_back
= (struct rt_entry
*)rh
;
for (rh
= hosthash
; rh
< &hosthash
[ROUTEHASHSIZ
]; rh
++)
rh
->rt_forw
= rh
->rt_back
= (struct rt_entry
*)rh
;
* Lookup an entry to the appropriate dstination.
register struct rt_entry
*rt
;
register struct rthash
*rh
;
register int hash
, (*match
)();
int af
= dst
->sa_family
, doinghost
= 1;
(*afswitch
[af
].af_hash
)(dst
, &h
);
rh
= &hosthash
[hash
% ROUTEHASHSIZ
];
for (rt
= rh
->rt_forw
; rt
!= (struct rt_entry
*)rh
; rt
= rt
->rt_forw
) {
if (equal(&rt
->rt_dst
, dst
))
if (rt
->rt_dst
.sa_family
== af
&&
(*match
)(&rt
->rt_dst
, dst
))
match
= afswitch
[af
].af_netmatch
;
rh
= &nethash
[hash
% ROUTEHASHSIZ
];
struct sockaddr
*dst
, *gate
;
register struct rt_entry
*rt
;
int af
= dst
->sa_family
, flags
, hash
;
(*afswitch
[af
].af_hash
)(dst
, &h
);
flags
= (*afswitch
[af
].af_checkhost
)(dst
) ? RTF_HOST
: 0;
rh
= &hosthash
[hash
% ROUTEHASHSIZ
];
rh
= &nethash
[hash
% ROUTEHASHSIZ
];
rt
= (struct rt_entry
*)malloc(sizeof (*rt
));
rt
->rt_flags
= RTF_UP
| flags
;
rt
->rt_ifp
= if_ifwithnet(&rt
->rt_gateway
);
rt
->rt_flags
|= RTF_DIRECT
;
rt
->rt_state
|= RTS_ADDRT
;
rt
->rt_retry
= EXPIRE_TIME
/TIMER_RATE
;
* Look to see if a change to an existing entry
* is warranted; if so, make it.
rtchange(rt
, gate
, metric
)
if (!equal(&rt
->rt_gateway
, gate
)) {
* If the hop count has changed, adjust
* the flags in the routing table entry accordingly.
if (metric
!= rt
->rt_metric
) {
rt
->rt_flags
&= ~RTF_DIRECT
;
if (metric
>= HOPCNT_INFINITY
)
rt
->rt_state
|= RTS_CHGRT
;
rt
->rt_retry
= EXPIRE_TIME
/TIMER_RATE
;
* Delete a routing table entry.
if (ioctl(s
, SIOCDELRT
, (char *)&rt
->rt_rt
) &&
rt
->rt_state
|= RTS_DELRT
;
struct sockaddr_in
*dst
, *gate
;
{ RTF_DIRECT
, "DIRECT" },
{ RTS_SILENT
, "SILENT" },
printf("%s ", operation
);
dst
= (struct sockaddr_in
*)&rt
->rt_dst
;
gate
= (struct sockaddr_in
*)&rt
->rt_gateway
;
printf("dst %x, router %x, metric %d, flags",
dst
->sin_addr
, gate
->sin_addr
, rt
->rt_metric
);
for (first
= 1, p
= flagbits
; p
->t_bits
> 0; p
++) {
if ((rt
->rt_flags
& p
->t_bits
) == 0)
for (first
= 1, p
= statebits
; p
->t_bits
> 0; p
++) {
if ((rt
->rt_state
& p
->t_bits
) == 0)
* Find the interface with address "addr".
register struct ifnet
*ifp
;
(bcmp((caddr_t)((a1)->sa_data), (caddr_t)((a2)->sa_data), 14) == 0)
for (ifp
= ifnet
; ifp
; ifp
= ifp
->if_next
) {
if (ifp
->if_addr
.sa_family
!= addr
->sa_family
)
if (same(&ifp
->if_addr
, addr
))
if ((ifp
->if_flags
& IFF_BROADCAST
) &&
same(&ifp
->if_broadaddr
, addr
))
* Find the interface with network imbedded in
* the sockaddr "addr". Must use per-af routine
register struct sockaddr
*addr
;
register struct ifnet
*ifp
;
register int af
= addr
->sa_family
;
register int (*netmatch
)();
netmatch
= afswitch
[af
].af_netmatch
;
for (ifp
= ifnet
; ifp
; ifp
= ifp
->if_next
) {
if (af
!= ifp
->if_addr
.sa_family
)
if ((*netmatch
)(addr
, &ifp
->if_addr
))
* Formulate an Internet address.
addr
= (net
<< 24) | host
;
addr
= (net
<< 16) | host
;
addr
= (net
<< 8) | host
;
return (*(struct in_addr
*)&addr
);