<> <> <> <<>> <> <<>> DIRECTORY BasicTime USING [GetClockPulses, MicrosecondsToPulses, Pulses, PulsesToMicroseconds], CommDriver USING [GetNetworkChain, InsertReceiveProc, Network], Endian USING [CardFromF, CardFromH, HFromCard], XNS USING [Address, broadcastNet, GetThisHost, Host, Net, Socket, unknownAddress, unknownHost, unknownNet, unknownSocket], XNSBuf USING [Buffer], XNSErrorTypes USING [protocolViolationErr], XNSRouter USING [Hops, RoutingTableEntry, unreachable], XNSRouterPrivate USING [EventProc, TakeThis], XNSRoutingBuf USING [Buffer, hdrBytes, maxBytes, maxTuples, NumTuplesFromUserBytes, Tuple, UserBytesFromNumTuples], XNSSocket USING [AllocBuffer, Broadcast, Create, dontWait, FixupSourceAndDest, FreeBuffer, Get, GetUserBytes, Handle, Milliseconds, ReturnError, Send, SetGetTimeout, SetUserBytes], XNSWKS USING [routing]; XNSRouterImpl: CEDAR MONITOR IMPORTS BasicTime, CommDriver, Endian, XNS, XNSRouterPrivate, XNSRoutingBuf, XNSSocket EXPORTS XNSRouter, XNSRouterPrivate ~ { Net: TYPE ~ XNS.Net; Host: TYPE ~ XNS.Host; Socket: TYPE ~ XNS.Socket; Address: TYPE ~ XNS.Address; NetGT: PROC [x,y: Net] RETURNS [BOOL] ~ TRUSTED INLINE { RETURN [ Endian.CardFromF[LOOPHOLE[x]] > Endian.CardFromF[LOOPHOLE[y]] ] }; unknownHost: Host ~ XNS.unknownHost; unknownNet: Net ~ XNS.unknownNet; broadcastNet: Net ~ XNS.broadcastNet; unknownSocket: Socket ~ XNS.unknownSocket; unknownAddress: Address ~ XNS.unknownAddress; thisHost: Host ~ XNS.GetThisHost[]; Network: TYPE ~ CommDriver.Network; Hops: TYPE ~ XNSRouter.Hops; unreachable: Hops ~ XNSRouter.unreachable; <> 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; <> <> <<>> <> <<>> numHashHeaders: CARDINAL ~ 300; HashIndex: TYPE ~ [0 .. numHashHeaders); RoutingTable: TYPE ~ REF RoutingTableRep; RoutingTableRep: TYPE ~ ARRAY HashIndex OF RoutingEntry; RoutingEntry: TYPE ~ REF RoutingEntryObject; RoutingEntryObject: TYPE ~ RECORD [ next: RoutingEntry, sortedNext, sortedPrev: RoutingEntry, dest: Net, hops: Hops, network: Network, immediate: Host, sweepsSinceRefresh: CARDINAL]; routingTable: RoutingTable ~ NEW[RoutingTableRep]; sortedHead: RoutingEntry _ NIL; Hash: PROC [net: Net] RETURNS [HashIndex] ~ TRUSTED INLINE { RETURN [ Endian.CardFromF[LOOPHOLE[net]] MOD numHashHeaders ] }; FindEntry: PROC [net: Net] RETURNS [eH: RoutingEntry] ~ INLINE { FOR eH _ routingTable^[Hash[net]], eH.next WHILE (eH # NIL) AND (eH.dest # net) DO NULL ENDLOOP; RETURN [eH] }; additions: INT _ 0; AddEntry: PROC [newH: RoutingEntry] ~ { <> h: HashIndex ~ Hash[newH.dest]; prevH, leftH, rightH: RoutingEntry _ NIL; additions _ additions.SUCC; IF Monitoring[] THEN PostEvent[newH~newH]; rightH _ sortedHead; WHILE (rightH # NIL) AND NetGT[newH.dest, rightH.dest] DO leftH _ rightH; rightH _ rightH.sortedNext; ENDLOOP; newH.next _ routingTable^[h]; routingTable^[h] _ newH; newH.sortedPrev _ leftH; newH.sortedNext _ rightH; IF rightH # NIL THEN rightH.sortedPrev _ newH; IF leftH # NIL THEN leftH.sortedNext _ newH ELSE sortedHead _ newH; }; replacements: INT _ 0; ReplaceEntry: PROC [newH: RoutingEntry, oldH: RoutingEntry] ~ { <> h: HashIndex ~ Hash[newH.dest]; prevH: RoutingEntry _ NIL; replacements _ replacements.SUCC; IF Monitoring[] THEN PostEvent[oldH~oldH, newH~newH]; FOR temp: RoutingEntry _ routingTable^[h], temp.next WHILE temp # oldH DO prevH _ temp ENDLOOP; newH.next _ routingTable^[h]; routingTable^[h] _ newH; IF prevH # NIL THEN prevH.next _ oldH.next ELSE newH.next _ oldH.next; IF (newH.sortedPrev _ oldH.sortedPrev) # NIL THEN newH.sortedPrev.sortedNext _ newH ELSE sortedHead _ newH; IF (newH.sortedNext _ oldH.sortedNext) # NIL THEN newH.sortedNext.sortedPrev _ newH; }; deletions: INT _ 0; DeleteEntry: PROC [oldH: RoutingEntry] ~ { <> h: HashIndex ~ Hash[oldH.dest]; prevH: RoutingEntry _ NIL; deletions _ deletions.SUCC; IF Monitoring[] THEN PostEvent[oldH~oldH]; FOR temp: RoutingEntry _ routingTable^[h], temp.next WHILE temp # oldH DO prevH _ temp ENDLOOP; IF prevH # NIL THEN prevH.next _ oldH.next ELSE routingTable^[h] _ oldH.next; IF oldH.sortedPrev # NIL THEN oldH.sortedPrev.sortedNext _ oldH.sortedNext ELSE sortedHead _ oldH.sortedNext; IF oldH.sortedNext # NIL THEN oldH.sortedNext.sortedPrev _ oldH.sortedPrev; }; changes: INT _ 0; ChangeEntry: PROC [oldH: RoutingEntry, newHops: Hops] ~ INLINE { <> IF oldH.hops # newHops THEN { changes _ changes.SUCC; IF Monitoring[] THEN PostChangeEvent[oldH, newHops]; oldH.hops _ newHops }; oldH.sweepsSinceRefresh _ 0 }; <> responsesSent: INT _ 0; ProcessRequest: PROC [b: XNSRoutingBuf.Buffer, userBytes: CARDINAL] ~ { <> 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 ~ { <> 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[handle~routingSocketHandle, b~sendBuf, dest~b.hdr1.source] ELSE XNSSocket.Broadcast[handle~routingSocketHandle, b~sendBuf, socket~XNSWKS.routing]; }; AddToSendBuf: PROC [eH: RoutingEntry] ~ { <> IF (sendBuf # NIL) AND (iSend >= XNSRoutingBuf.maxTuples) THEN { Send[]; sendBuf _ NIL }; IF sendBuf = NIL THEN { sendBuf _ XNSSocket.AllocBuffer[handle~routingSocketHandle]; iSend _ 0 }; TRUSTED { srb: XNSRoutingBuf.Buffer ~ LOOPHOLE[sendBuf]; srb.body.tuples[iSend] _ [net~eH.dest, delay~eH.hops] }; iSend _ iSend + 1; }; 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 { <> FOR eH: RoutingEntry _ sortedHead, eH.sortedNext WHILE eH # NIL DO AddToSendBuf[eH]; ENDLOOP; } ELSE { <> FOR iReq: CARDINAL IN [0 .. nReq) DO eH: RoutingEntry ~ FindEntry[b.body.tuples[iReq].net]; IF eH # NIL THEN AddToSendBuf[eH]; ENDLOOP; }; IF sendBuf # NIL THEN { Send[]; sendBuf _ NIL }; responsesSent _ responsesSent.SUCC; }; ProcessResponse: PROC [b: XNSRoutingBuf.Buffer, userBytes: CARDINAL] ~ { <> network: Network _ NARROW[b.ovh.network]; immediate: Host _ b.hdr1.source.host; tuple: XNSRoutingBuf.Tuple; hops: CARDINAL; eH, newH: RoutingEntry; IF network.xns.net = unknownNet THEN { <> network.xns.net _ b.hdr1.source.net; -- NOT ATOMIC ConnectNets[] }; FOR i: CARDINAL IN [0 .. XNSRoutingBuf.NumTuplesFromUserBytes[userBytes]) DO tuple _ b.body.tuples[i]; hops _ Endian.CardFromH[tuple.delay]; IF (eH _ FindEntry[tuple.net]) # NIL THEN { <> IF (eH.network = network) AND (eH.immediate = immediate) THEN { IF hops < unreachable THEN { ChangeEntry[eH, hops] } ELSE { DeleteEntry[eH] }; LOOP }; <> IF eH.sweepsSinceRefresh < suspectSweeps THEN { IF eH.hops < hops THEN LOOP; IF (eH.hops = hops) AND (eH.network.speed >= network.speed) THEN LOOP; }; <> IF hops >= unreachable THEN { IF eH.sweepsSinceRefresh >= suspectSweeps AND (eH.network = network) THEN { DeleteEntry[eH] }; LOOP }; <> newH _ NEW [RoutingEntryObject _ [dest~tuple.net, hops~hops, network~network, immediate~immediate, sweepsSinceRefresh~0]]; ReplaceEntry[newH~newH, oldH~eH]; LOOP; }; <> IF hops >= unreachable THEN LOOP; <> newH _ NEW [RoutingEntryObject _ [dest~tuple.net, hops~hops, network~network, immediate~immediate, sweepsSinceRefresh~0]]; AddEntry[newH]; ENDLOOP; }; ConnectNets: PROC [] ~ { <> oldH, newH: RoutingEntry; FOR network: Network _ CommDriver.GetNetworkChain[], network.next UNTIL network = NIL DO IF network.xns.net = unknownNet THEN LOOP; oldH _ FindEntry[network.xns.net]; IF oldH # NIL AND oldH.hops = 0 THEN { oldH.sweepsSinceRefresh _ 0; LOOP }; newH _ NEW[RoutingEntryObject _ [dest~network.xns.net, hops~0, network~network, immediate~unknownHost, sweepsSinceRefresh~0]]; IF oldH # NIL THEN ReplaceEntry[newH~newH, oldH~oldH] ELSE AddEntry[newH~newH]; ENDLOOP; }; Sweep: PROC ~ { <> eH, nextH: RoutingEntry; FOR eH _ sortedHead, nextH WHILE eH # NIL DO nextH _ eH.sortedNext; IF eH.sweepsSinceRefresh >= invalidSweeps THEN DeleteEntry[eH] ELSE eH.sweepsSinceRefresh _ eH.sweepsSinceRefresh.SUCC; ENDLOOP; }; packetsReceived: INT _ 0; requestsReceived: INT _ 0; responsesReceived: INT _ 0; badLength: INT _ 0; badProtocol: INT _ 0; sweeps: INT _ 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 <> userBytes: CARDINAL ~ XNSSocket.GetUserBytes[b]; rB: XNSRoutingBuf.Buffer; packetsReceived _ packetsReceived.SUCC; IF b.hdr1.type # routing THEN { badProtocol _ badProtocol.SUCC; XNSSocket.ReturnError[handle~routingSocketHandle, 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[handle~routingSocketHandle, b~b, type~XNSErrorTypes.protocolViolationErr]; b _ NIL }; GOTO Next; EXITS Next => IF b # NIL THEN XNSSocket.FreeBuffer[routingSocketHandle, b]; END ELSE BEGIN <> minSweepPulses _ MIN[minSweepPulses, PulsesSince[lastSweep]]; ConnectNets[]; Sweep[]; sweeps _ sweeps.SUCC; lastSweep _ BasicTime.GetClockPulses[]; END; ENDLOOP; }; PokeGateways: PROC ~ { b: XNSBuf.Buffer; rB: XNSRoutingBuf.Buffer; b _ XNSSocket.AllocBuffer[handle~routingSocketHandle]; TRUSTED { rB _ LOOPHOLE[b] }; rB.hdr1.type _ routing; rB.hdr2.type _ request; rB.body.tuples[0] _ [net~broadcastNet, delay~Endian.HFromCard[unreachable]]; XNSSocket.SetUserBytes [b~b, bytes~XNSRoutingBuf.UserBytesFromNumTuples[1]]; XNSSocket.Broadcast[handle~routingSocketHandle, b~b, socket~XNSWKS.routing]; }; <> Route: PUBLIC PROC [him: XNS.Address] RETURNS [network: Network, immediate: XNS.Host] ~ { eH: RoutingEntry ~ FindEntry[him.net]; IF eH = NIL THEN RETURN [NIL, unknownHost]; IF eH.hops = 0 THEN RETURN [eH.network, him.host]; IF eH.hops >= unreachable THEN ERROR; -- Gateways: RETURN [NIL, unknownHost]; RETURN [eH.network, eH.immediate]; }; <> 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 ENTRY PROC [proc: EventProc] ~ { eventProcList _ NEW[ EventProcObject _ [next~eventProcList, proc~proc] ]; }; ClearEventProc: PUBLIC ENTRY PROC [proc: EventProc] ~ { p, prev: EventProcList; 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 }; }; Monitoring: PROC RETURNS [BOOL] ~ INLINE { RETURN [eventProcList # NIL] }; PostEvent: PROC [oldH, newH: RoutingEntry _ NIL] ~ { net: Net; oldRTEH, newRTEH: RTEHandle _ NIL; IF oldH # NIL THEN { oldRTEH _ oldStaticBuffer; oldRTEH^ _ [hops~oldH.hops, immediate~[net~oldH.network.xns.net, host~oldH.immediate, socket~unknownSocket], time~(oldH.sweepsSinceRefresh*sweepSeconds)]; net _ oldH.dest }; IF newH # NIL THEN { newRTEH _ newStaticBuffer; newRTEH^ _ [hops~newH.hops, immediate~[net~newH.network.xns.net, host~newH.immediate, socket~unknownSocket], time~(newH.sweepsSinceRefresh*sweepSeconds)]; net _ newH.dest }; FOR pH: EventProcList _ eventProcList, pH.next WHILE pH # NIL DO (pH.proc)[net, oldRTEH, newRTEH]; ENDLOOP; }; PostChangeEvent: PROC [oldH: RoutingEntry, newHops: Hops] ~ { oldStaticBuffer^ _ [hops~oldH.hops, immediate~[net~oldH.network.xns.net, host~oldH.immediate, socket~unknownSocket], time~(oldH.sweepsSinceRefresh*sweepSeconds)]; newStaticBuffer^ _ [hops~newHops, immediate~[net~oldH.network.xns.net, host~oldH.immediate, socket~unknownSocket], time~0]; FOR pH: EventProcList _ eventProcList, pH.next WHILE pH # NIL DO (pH.proc)[oldH.dest, oldStaticBuffer, newStaticBuffer]; ENDLOOP; }; <> Fast: PUBLIC PROC [net: Net] RETURNS [yes: BOOL] ~ { eH: RoutingEntry ~ FindEntry[net]; IF eH = NIL THEN RETURN[FALSE]; SELECT eH.network.type FROM ethernet => RETURN[TRUE]; ethernetOne => RETURN[TRUE]; ENDCASE => RETURN[FALSE]; }; GetHops: PUBLIC PROC [net: Net] RETURNS [Hops] ~ { eH: RoutingEntry ~ FindEntry[net]; IF eH = NIL THEN RETURN [unreachable]; RETURN [eH.hops]; }; GetRouting: PUBLIC PROC [net: Net] RETURNS [XNSRouter.RoutingTableEntry] ~ { eH: RoutingEntry ~ FindEntry[net]; IF eH = NIL THEN RETURN [[ hops~unreachable, immediate~unknownAddress, time~0]]; RETURN [[ hops~eH.hops, immediate~[net~eH.network.xns.net, host~eH.immediate, socket~unknownSocket], time~(eH.sweepsSinceRefresh*sweepSeconds)]]; }; Enumerate: PUBLIC PROC [ low: Hops _ 0, high: Hops _ unreachable, proc: PROC [Net, XNSRouter.RoutingTableEntry]] ~ { FOR eH: RoutingEntry _ sortedHead, eH.sortedNext WHILE eH # NIL DO IF eH.hops >= low AND eH.hops <= high THEN proc[ eH.dest, [ hops~eH.hops, immediate~[net~eH.network.xns.net, host~eH.immediate, socket~unknownSocket], time~(eH.sweepsSinceRefresh*sweepSeconds)] ]; ENDLOOP; }; <> daemonProcess: PROCESS; routingSocketHandle: XNSSocket.Handle; Init: PROC ~ { <<>> <> CommDriver.InsertReceiveProc[network~NIL, type~xns, proc~XNSRouterPrivate.TakeThis]; <<>> <> routingSocketHandle _ XNSSocket.Create[local~XNSWKS.routing]; daemonProcess _ FORK Daemon[]; PokeGateways[]; }; Init[]; }.