<> <> <> <<>> <> <<>> 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; <> 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; <> <> <<>> <> 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-- { <> [val~val] _ CardTab.Fetch[routingTable, KeyFromAddress[address]] }; GetEntry: PROC [address: Address] RETURNS [val: REF] ~ { <> 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; }; <> 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[b~sendBuf, dest~b.hdr1.source] ELSE XNSSocket.Broadcast[b~sendBuf, socket~XNSWKS.routing]; }; AddToSendBuf: CardTab.EachPairAction -- [key, val] RETURNS [quit]-- ~ { <> 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 { <> [] _ CardTab.Pairs[routingTable, AddToSendBuf]; } ELSE { <> 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] ~ { <> 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 { <> IF Monitoring[] AND (routingEntry.hops # hops) THEN PostChange[tuple.net, routingEntry, hops, network.xns.net, immediate]; } ELSE { <> <> 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; }; <> 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 { <> 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 [] ~ { <> 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 ~ { <> 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 <> 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 <> minSweepPulses _ MIN[minSweepPulses, PulsesSince[lastSweep]]; ConnectNets[]; Sweep[]; sweeps _ sweeps.SUCC; lastSweep _ BasicTime.GetClockPulses[]; END; ENDLOOP; }; <> 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 ~ { <> 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; }; <> 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: 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[]; }; <> 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] }; <> 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]; }; <> daemonProcess: PROCESS; routingSocketHandle: XNSSocket.Handle; Init: PROC ~ { <<>> <> CommDriver.InsertReceiveProc[network~NIL, type~xns, proc~XNSRouterPrivate.TakeThis]; <<>> <> Booting.RegisterProcs[r: Rollback]; <> routingSocketHandle _ XNSSocket.Create[local~XNSWKS.routing]; daemonProcess _ FORK Daemon[]; PokeGateways[]; }; Init[]; }.