DIRECTORY
Arpa USING [Address, NetNumber, nullAddress],
ArpaBuf USING [Buffer],
ArpaRouter USING [Hops, RoutingTableEntry, unreachable],
ArpaRouterPrivate USING [EventProc, TakeThis],
ArpaRoutingBuf USING [Buffer, hdrBytes, maxBytes, maxTuples, NumTuplesFromUserBytes, Tuple, UserBytesFromNumTuples],
Basics USING [Card32FromF, Card16FromH, FFromCard32, HFromCard16],
BasicTime USING [GetClockPulses, MicrosecondsToPulses, Pulses, PulsesToMicroseconds],
Booting USING [RegisterProcs, RollbackProc],
CardTab USING [Create, EachPairAction, Fetch, Insert, Key, Pairs, Ref],
CommDriver USING [GetNetworkChain, InsertReceiveProc, Network],
Process USING [PauseMsec],
XNS USING [Address, broadcastNet, GetThisHost, Host, Net, Socket, unknownAddress, unknownHost, unknownNet, unknownSocket],
XNSErrorTypes USING [protocolViolationErr],
XNSSocket USING [AllocBuffer, Broadcast, Create, dontWait, FixupSourceAndDest, FreeBuffer, Get, GetUserBytes, Handle, Milliseconds, ReturnError, Send, SetGetTimeout, SetUserBytes],
XNSWKS USING [routing];
ArpaRouterImpl:
CEDAR
MONITOR
LOCKS routingEntry USING routingEntry: RoutingEntry
IMPORTS Arpa, ArpaRouterPrivate, Basics, BasicTime, Booting, CardTab, CommDriver, Process, XNS, XNSRoutingBuf, XNSSocket
EXPORTS ArpaRouter, ArpaRouterPrivate
~ {
Net: TYPE ~ XNS.Net; -- presumed equivalent to Basics.FWORD
Address: TYPE ~ Arpa.Address;
unknownAddress: Address ~ Arpa.nullAddress;
thisHost: Host ~ XNS.GetThisHost[]; -- ????
Network: TYPE ~ CommDriver.Network;
Hops: TYPE ~ ArpaRouter.Hops;
unreachable: Hops ~ ArpaRouter.unreachable;
Timeouts
Pulses: TYPE ~ BasicTime.Pulses;
Msecs: TYPE ~ XNSSocket.Milliseconds;
PulsesSince:
PROC [then: Pulses]
RETURNS[Pulses] ~
INLINE {
RETURN [BasicTime.GetClockPulses[] - then] };
sweepSeconds: CARDINAL ~ 15;
sweepPulses: Pulses ~ BasicTime.MicrosecondsToPulses[ LONG[sweepSeconds] * 1000000 ];
suspectSweeps: CARDINAL ← 6;
invalidSweeps: CARDINAL ← 12;
Routing Table
Routing Entries are kept in a hash table, keyed by the net you're trying to reach.
INVARIANT: routingEntry.hops = unreachable IFF routingEntry.network = NIL.
RoutingTable: TYPE ~ CardTab.Ref;
initialTableSize: NAT ← 311;
RoutingEntry: TYPE ~ REF RoutingEntryObject;
RoutingEntryObject:
TYPE ~
MONITORED
RECORD [
hops: Hops ← unreachable, -- hops to the desired net
immediate: Address ← unknownAddress, -- first router on route
network: Network ← NIL, -- directly connected net to first router
sweepsSinceRefresh: CARDINAL ← 0];
routingTable: RoutingTable ← CardTab.Create[initialTableSize];
KeyFromAddress:
PROC [address: Address]
RETURNS [CardTab.Key] ~
--INLINE-- {
RETURN [ Basics.Card32FromF[LOOPHOLE[Arpa.NetNumber[address]]] ] };
NetAddressFromKey:
PROC [key: CardTab.Key]
RETURNS [Address] ~
--INLINE-- {
RETURN [ LOOPHOLE[Basics.FFromCard32[key]] ] };
LookupEntry:
PROC [address: Address]
RETURNS [val:
REF] ~
--INLINE-- {
Lookup entry. Return NIL is no entry exists.
[val~val] ← CardTab.Fetch[routingTable, KeyFromAddress[address]] };
GetEntry:
PROC [address: Address]
RETURNS [val:
REF] ~ {
Lookup entry, or create a new one if none exists. Never return NIL.
key: CardTab.Key ~ KeyFromAddress[address];
new: REF ← NIL;
DO
[val~val] ← CardTab.Fetch[routingTable, key];
IF val # NIL THEN RETURN;
IF new = NIL THEN new ← NEW[RoutingEntryObject];
val ← new;
IF CardTab.Insert[routingTable, key, val] THEN RETURN;
ENDLOOP;
};
Routing Daemon
responsesSent: INT ← 0;
ProcessRequest:
PROC [b: XNSRoutingBuf.Buffer, userBytes:
CARDINAL] ~ {
Reply to b^ (which must be a routing information request packet of length userBytes). For a simple router (not gateway) this is done only if the b^ was directed at this host (rather than broadcast). The request buffer b may be NIL, in which case we "reply" to it by broadcasting our entire routing table.
sendBuf: XNSBuf.Buffer ← NIL; -- the send buffer.
iSend: CARDINAL; -- index into sb.body.tuples
nReq: CARDINAL ← 0; -- number of request tuples in b, or 0 if b = NIL
Send:
PROC ~ {
Send sendBuf^ to destination computed from b.
TRUSTED {
srb: XNSRoutingBuf.Buffer ~ LOOPHOLE[sendBuf];
srb.hdr1.type ← routing;
srb.hdr2.type ← response };
XNSSocket.SetUserBytes[sendBuf, XNSRoutingBuf.UserBytesFromNumTuples[iSend]];
IF b #
NIL
THEN XNSSocket.Send[b~sendBuf, dest~b.hdr1.source]
ELSE XNSSocket.Broadcast[b~sendBuf, socket~XNSWKS.routing];
};
AddToSendBuf: CardTab.EachPairAction
-- [key, val] RETURNS [quit]-- ~ {
Add info from routingEntry to response packet in sendBuf^, sending the old response packet and allocating a new one if necessary.
IF (sendBuf #
NIL)
AND (iSend >= XNSRoutingBuf.maxTuples)
THEN {
Send[]; sendBuf ← NIL };
IF sendBuf =
NIL THEN {
sendBuf ← XNSSocket.AllocBuffer[handle~routingSocketHandle];
iSend ← 0 };
AddToSendBufInner[routingEntry~NARROW[val], net~NetAddressFromKey[key]];
iSend ← iSend + 1;
RETURN [FALSE] };
AddToSendBufInner:
ENTRY
PROC [routingEntry: RoutingEntry, net: Net] ~
--INLINE-- {
TRUSTED {
srb: XNSRoutingBuf.Buffer ~ LOOPHOLE[sendBuf];
srb.body.tuples[iSend] ← [net~net, delay~Basics.HFromCard16[routingEntry.hops]];
};
};
IF b #
NIL
THEN {
IF b.hdr1.dest.host # thisHost THEN RETURN; -- Simple router responds only to requests directed at it.
TRUSTED { XNSSocket.FixupSourceAndDest[LOOPHOLE[b]] };
nReq ← XNSRoutingBuf.NumTuplesFromUserBytes[userBytes] };
IF (b =
NIL)
OR ((nReq > 0)
AND (b.body.tuples[0].net = broadcastNet))
THEN {
Dump the entire routing table.
[] ← CardTab.Pairs[routingTable, AddToSendBuf];
}
ELSE {
Reply with routing table entries for requested nets only. Responses are in the same order as the requests ...
FOR iReq:
CARDINAL
IN [0 .. nReq)
DO
net: Net ~ b.body.tuples[iReq].net;
routingEntry: RoutingEntry ~ NARROW[ LookupEntry[????net] ];
IF routingEntry # NIL THEN
[] ← AddToSendBuf[Basics.Card32FromF[net], routingEntry];
ENDLOOP;
};
IF sendBuf # NIL THEN { Send[]; sendBuf ← NIL };
responsesSent ← responsesSent.SUCC;
};
ProcessResponse:
PROC [b: XNSRoutingBuf.Buffer, userBytes:
CARDINAL] ~ {
Update the routing table using information from b^ (which must be a routing information response packet of length userBytes).
network: Network ← NARROW[b.ovh.network];
immediate: Host ← b.hdr1.source.host;
tuple: XNSRoutingBuf.Tuple;
hops: CARDINAL;
UpdateEntryFromTuple:
ENTRY
PROC [routingEntry: RoutingEntry] ~
--INLINE-- {
IF (routingEntry.network = network)
AND (routingEntry.immediate = immediate)
THEN {
Update is from owner of entry, we will accept it.
IF Monitoring[] AND (routingEntry.hops # hops) THEN PostChange[tuple.net, routingEntry, hops, network.xns.net, immediate];
}
ELSE {
Update is not from owner of entry, we may want to reject it.
Update less desirable than the current entry is rejected.
IF routingEntry.sweepsSinceRefresh < suspectSweeps
THEN {
IF routingEntry.hops < hops THEN RETURN;
IF (routingEntry.hops = hops) AND (routingEntry.network # NIL) AND (routingEntry.network.speed >= network.speed) THEN RETURN;
};
Update making an (unowned) entry unreachable is rejected if it comes from a gateway on a different net from the old route. That's just a heuristic.
IF (hops >= unreachable) AND (network # routingEntry.network) THEN RETURN;
IF Monitoring[] THEN PostChange[tuple.net, routingEntry, hops, network.xns.net, immediate];
routingEntry.network ← network;
routingEntry.immediate ← immediate;
};
routingEntry.hops ← hops;
routingEntry.sweepsSinceRefresh ← 0;
IF hops >= unreachable
THEN {
routingEntry.network ← NIL;
routingEntry.immediate ← unknownAddress };
};
IF network.xns.net = unknownNet
THEN {
We have just learned the network number of a directly-connected net.
network.xns.net ← b.hdr1.source.net; -- NOT ATOMIC but there's only one daemon ...
ConnectNets[] };
FOR i:
CARDINAL
IN [0 .. XNSRoutingBuf.NumTuplesFromUserBytes[userBytes])
DO
tuple ← b.body.tuples[i];
hops ← Basics.Card16FromH[tuple.delay];
UpdateEntryFromTuple[NARROW[GetEntry[tuple.net]]];
ENDLOOP;
};
ConnectNets:
PROC [] ~ {
Ensure that there's a valid 0-hops routing entry for each connected network for which the network number (network.ns.net) has already been filled in.
network: Network;
ConnectNetInner:
ENTRY PROC [routingEntry: RoutingEntry] ~
--INLINE-- {
routingEntry.hops ← 0;
routingEntry.network ← network;
routingEntry.sweepsSinceRefresh ← 0;
};
FOR network ← CommDriver.GetNetworkChain[], network.next
UNTIL network =
NIL
DO
IF network.xns.net # unknownNet THEN ConnectNetInner[NARROW[GetEntry[network.xns.net]]];
ENDLOOP;
};
Sweep:
PROC ~ {
Throw away (i.e. mark as unreachable) any routing entries that are too old to be credible.
CheckEntry: CardTab.EachPairAction
-- [key, val] RETURNS [quit]-- ~ {
CheckEntryInner[NARROW[val]];
RETURN [FALSE] };
CheckEntryInner:
ENTRY
PROC [routingEntry: RoutingEntry] ~
--INLINE-- {
IF routingEntry.sweepsSinceRefresh >= invalidSweeps
THEN routingEntry.hops ← unreachable;
routingEntry.sweepsSinceRefresh ← routingEntry.sweepsSinceRefresh.SUCC;
};
[] ← CardTab.Pairs[routingTable, CheckEntry];
};
packetsReceived: INT ← 0;
requestsReceived: INT ← 0;
responsesReceived: INT ← 0;
badLength: INT ← 0;
badProtocol: INT ← 0;
sweeps: CARD ← 0;
minSweepPulses: Pulses ← sweepPulses;
lastSweep: Pulses ← BasicTime.GetClockPulses[];
Daemon:
PROC ~ {
DO
b: XNSBuf.Buffer;
sinceSweep: Pulses ~ PulsesSince[lastSweep];
getTimeout: Msecs ~
IF sinceSweep >= sweepPulses
THEN XNSSocket.dontWait
ELSE (1 + (BasicTime.PulsesToMicroseconds[sweepPulses - sinceSweep] / 1000));
XNSSocket.SetGetTimeout[routingSocketHandle, getTimeout];
IF (b ← XNSSocket.Get[routingSocketHandle]) #
NIL
THEN
BEGIN
Receive and process a routing info packet.
userBytes: CARDINAL ~ XNSSocket.GetUserBytes[b];
rB: XNSRoutingBuf.Buffer;
packetsReceived ← packetsReceived.SUCC;
IF b.hdr1.type # routing
THEN {
badProtocol ← badProtocol.SUCC;
XNSSocket.ReturnError[b~b, type~XNSErrorTypes.protocolViolationErr];
b ← NIL;
GOTO Next };
IF (userBytes < XNSRoutingBuf.hdrBytes)
OR (userBytes > XNSRoutingBuf.maxBytes)
THEN {
badLength ← badLength.SUCC;
GOTO Next };
TRUSTED { rB ← LOOPHOLE[b] };
SELECT rB.hdr2.type
FROM
request => {
requestsReceived ← requestsReceived.SUCC;
ProcessRequest[rB, userBytes] };
response => {
responsesReceived ← responsesReceived.SUCC;
ProcessResponse[rB, userBytes] };
ENDCASE => {
XNSSocket.ReturnError[b~b, type~XNSErrorTypes.protocolViolationErr];
b ← NIL };
GOTO Next;
EXITS
Next => IF b # NIL THEN XNSSocket.FreeBuffer[b];
END
ELSE BEGIN
Sweep the table.
minSweepPulses ← MIN[minSweepPulses, PulsesSince[lastSweep]];
ConnectNets[];
Sweep[];
sweeps ← sweeps.SUCC;
lastSweep ← BasicTime.GetClockPulses[];
END;
ENDLOOP;
};
Requesting Tables From the Gateways
WeUseTranslation:
PROC
RETURNS [yes:
BOOL] ~ {
FOR network: CommDriver.Network ← CommDriver.GetNetworkChain[], network.next
UNTIL network =
NIL
DO
IF network.xns.translation # NIL THEN RETURN [TRUE];
ENDLOOP;
RETURN [FALSE] };
PokeGateways:
PROC ~ {
If we use translation, this pokes the gateways twice, with a one-second pause in between, to give them time to fill their address translation caches.
nTries: INT ← IF WeUseTranslation[] THEN 2 ELSE 1;
FOR try:
INT ← 0, try+1
WHILE try < nTries
DO
b: XNSBuf.Buffer;
rB: XNSRoutingBuf.Buffer;
IF try > 0 THEN Process.PauseMsec[1111];
b ← XNSSocket.AllocBuffer[handle~routingSocketHandle];
TRUSTED { rB ← LOOPHOLE[b] };
rB.hdr1.type ← routing;
rB.hdr2.type ← request;
rB.body.tuples[0] ← [net~broadcastNet, delay~Basics.HFromCard16[unreachable]];
XNSSocket.SetUserBytes [b~b, bytes~XNSRoutingBuf.UserBytesFromNumTuples[1]];
XNSSocket.Broadcast[b~b, socket~XNSWKS.routing];
ENDLOOP;
};
Routing a Packet
Route:
PUBLIC
PROC [him: Arpa.Address]
RETURNS [network: Network, immediate: Address] ~ {
entry: REF ~ LookupEntry[him];
RouteInner:
ENTRY
PROC [routingEntry: RoutingEntry] ~
--INLINE-- {
network ← routingEntry.network;
immediate ← IF routingEntry.hops = 0 THEN him.host ELSE routingEntry.immediate;
};
IF entry = NIL THEN RETURN [NIL, unknownAddress];
RouteInner[NARROW[entry]];
};
Rollback
Rollback: Booting.RollbackProc = {
SmashEntry: CardTab.EachPairAction
-- [key, val] RETURNS [quit]-- ~ {
SmashEntryInner[NARROW[val]];
RETURN [FALSE] };
SmashEntryInner:
ENTRY
PROC [routingEntry: RoutingEntry] ~
--INLINE-- {
routingEntry.sweepsSinceRefresh ← invalidSweeps.PRED;
};
[] ← CardTab.Pairs[routingTable, SmashEntry];
PokeGateways[];
};
Event Monitoring (Exported to XNSRouterPrivate)
eventLock: RoutingEntry ← NEW[RoutingEntryObject];
RTEHandle: TYPE ~ REF RTEObject;
RTEObject: TYPE ~ XNSRouter.RoutingTableEntry;
oldStaticBuffer: RTEHandle ~ NEW [RTEObject ← [hops~, immediate~, time~]];
newStaticBuffer: RTEHandle ~ NEW [RTEObject ← [hops~, immediate~, time~]];
EventProc: TYPE ~ XNSRouterPrivate.EventProc;
EventProcList: TYPE ~ REF EventProcObject;
EventProcObject:
TYPE ~
RECORD [
next: EventProcList ← NIL,
proc: EventProc];
eventProcList: EventProcList ← NIL;
SetEventProc:
PUBLIC
PROC [proc: EventProc] ~ {
SetEventProcInner:
ENTRY
PROC [routingEntry: RoutingEntry] ~
--INLINE-- {
eventProcList ← NEW[ EventProcObject ← [next~eventProcList, proc~proc] ] };
SetEventProcInner[eventLock] };
ClearEventProc:
PUBLIC
PROC [proc: EventProc] ~ {
p, prev: EventProcList;
ClearEventProcInner:
ENTRY
PROC [routingEntry: RoutingEntry] ~
--INLINE-- {
p ← eventProcList; prev ← NIL;
WHILE (p # NIL) AND (p.proc # proc) DO prev ← p; p ← p.next ENDLOOP;
IF p #
NIL
THEN {
IF prev = NIL THEN eventProcList ← p.next ELSE prev.next ← p.next };
};
ClearEventProcInner[eventLock] };
Monitoring: PROC RETURNS [BOOL] ~ INLINE { RETURN [eventProcList # NIL] };
PostChange:
PROC [net: Net, old: RoutingEntry, hops: Hops, immNet: Net, immHost: Host] ~ {
PostChangeInner:
ENTRY
PROC [routingEntry: RoutingEntry
-- lock --] ~
--INLINE-- {
oldStaticBuffer^ ← [
hops~old.hops,
immediate~[net~(IF old.network # NIL THEN old.network.xns.net ELSE unknownNet), host~old.immediate, socket~unknownSocket],
time~(old.sweepsSinceRefresh*sweepSeconds)];
newStaticBuffer^ ← [
hops~hops,
immediate~[net~immNet, host~immHost, socket~unknownSocket],
time~0];
FOR pH: EventProcList ← eventProcList, pH.next
WHILE pH #
NIL
DO
(pH.proc)[net, oldStaticBuffer, newStaticBuffer];
ENDLOOP;
};
PostChangeInner[eventLock] };
Client Interface (Exported to ArpaRouter)
Fast:
PUBLIC
PROC [address: Address]
RETURNS [yes:
BOOL] ~ {
routingEntry: RoutingEntry ~ NARROW[LookupEntry[address]];
IF (routingEntry = NIL) OR (routingEntry.network = NIL) THEN RETURN[FALSE];
SELECT routingEntry.network.type
FROM
ethernet => RETURN[TRUE];
ethernetOne => RETURN[TRUE];
ENDCASE => RETURN[FALSE];
};
GetHops:
PUBLIC PROC [address: Address]
RETURNS [hops: Hops ← unreachable] ~ {
entry: REF ~ LookupEntry[address];
GetHopsInner:
ENTRY
PROC [routingEntry: RoutingEntry] ~
--INLINE-- {
IF routingEntry # NIL THEN hops ← routingEntry.hops };
IF entry # NIL THEN GetHopsInner[NARROW[entry]];
};
GetRouting:
PUBLIC
PROC [address: Address]
RETURNS [rte: XNSRouter.RoutingTableEntry ←
[hops~unreachable, immediate~unknownAddress, time~0]] ~ {
entry: REF ~ LookupEntry[address];
GetRoutingInner:
ENTRY
PROC [routingEntry: RoutingEntry] ~
--INLINE-- {
rte ← [
hops~routingEntry.hops,
immediate~[
net~(IF routingEntry.network # NIL THEN routingEntry.network.xns.net ELSE unknownNet),
host~routingEntry.immediate,
socket~unknownSocket],
time~(routingEntry.sweepsSinceRefresh*sweepSeconds)];
};
IF entry # NIL THEN GetRoutingInner[NARROW[entry]]
};
Enumerate:
PUBLIC PROC [
low: Hops ← 0, high: Hops ← unreachable,
proc: PROC [Net, XNSRouter.RoutingTableEntry]] ~ {
EachPair: CardTab.EachPairAction
-- [key, val] RETURNS [quit] -- ~ {
rte: XNSRouter.RoutingTableEntry;
EachPairInner:
ENTRY
PROC [routingEntry: RoutingEntry]
RETURNS [inRange:
BOOL] ~
--INLINE-- {
IF (inRange ← ((routingEntry.hops >= low)
AND (routingEntry.hops <= high)))
THEN {
rte ← [
hops~routingEntry.hops,
immediate~[
net~(IF routingEntry.network # NIL THEN routingEntry.network.xns.net ELSE unknownNet),
host~routingEntry.immediate,
socket~unknownSocket],
time~(routingEntry.sweepsSinceRefresh*sweepSeconds)];
};
};
IF EachPairInner[NARROW[val]].inRange THEN proc[ NetAddressFromKey[key], rte ];
};
[] ← CardTab.Pairs[routingTable, EachPair];
};
Initialization
daemonProcess: PROCESS;
routingSocketHandle: XNSSocket.Handle;
Init:
PROC ~ {
Install recv proc for each network on chain.
CommDriver.InsertReceiveProc[network~NIL, type~xns, proc~XNSRouterPrivate.TakeThis];
Register rollback proc.
Booting.RegisterProcs[r: Rollback];
Start routing daemon.
routingSocketHandle ← XNSSocket.Create[local~XNSWKS.routing];
daemonProcess ← FORK Daemon[];
PokeGateways[];
};
Init[];
}.