<> <> <> <<>> <> <<>> DIRECTORY Arpa USING [Address, NetNumber, nullAddress], ArpaExtras USING [broadcastAddress, IsMyAddress, IsSpecificNet, NetAndSubnetNumber, NetAndSubnetNumberWithMask], ArpaRIPBuf USING [arpaAddressFamily, Buffer, hdrBytes, maxBytes, maxTuples, NumTuplesFromUserBytes, UserBytesFromNumTuples], ArpaRouter USING [Hops, maxHops, RoutingTableEntry, unreachable], ArpaRouterPrivate USING [EventProc, EventReason, TakeThis], ArpaTranslation USING [GetSubnetMask], ArpaUDP USING [AllocBuffers, Create, dontWait, FreeBuffers, Get, GetSource, GetUserBytes, Handle, Port, Send, SetGetTimeout, SetUserBytes], ArpaUDPBuf USING [Buffer], Basics USING [Card32FromF, FFromCard32, HFromCard16, HWORD], BasicTime USING [GetClockPulses, MicrosecondsToPulses, Pulses, PulsesToMicroseconds], Booting USING [RegisterProcs, RollbackProc], CardTab USING [Create, EachPairAction, Fetch, Insert, Key, Pairs, Ref], CommDriver USING [GetNetworkChain, InsertReceiveProc, Network] ; ArpaRouterImpl: CEDAR MONITOR LOCKS routingEntry USING routingEntry: RoutingEntry IMPORTS Arpa, ArpaExtras, ArpaRIPBuf, ArpaRouterPrivate, ArpaTranslation, ArpaUDP, Basics, BasicTime, Booting, CardTab, CommDriver EXPORTS ArpaRouter, ArpaRouterPrivate ~ { HWORD: TYPE ~ Basics.HWORD; Address: TYPE ~ Arpa.Address; Port: TYPE ~ ArpaUDP.Port; unknownAddress: Address ~ Arpa.nullAddress; Network: TYPE ~ CommDriver.Network; Hops: TYPE ~ ArpaRouter.Hops; maxHops: Hops ~ ArpaRouter.maxHops; unreachable: Hops ~ ArpaRouter.unreachable; <> ripVersion: BYTE ~ 1; ripPort: Port ~ Basics.HFromCard16[520]; ripArpaAddressFamily: HWORD ~ ArpaRIPBuf.arpaAddressFamily; <> Pulses: TYPE ~ BasicTime.Pulses; Msecs: TYPE ~ CARD; 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]; <> defaultRoutingEntry: RoutingEntry _ NEW[RoutingEntryObject]; <> <> <> KeyFromAddress: PROC [address: Address] RETURNS [CardTab.Key] ~ INLINE { RETURN [ LOOPHOLE[address] ] }; AddressFromKey: PROC [key: CardTab.Key] RETURNS [Address] ~ INLINE { RETURN [ LOOPHOLE[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: ArpaRIPBuf.Buffer, userBytes: CARDINAL] ~ { <> sendBuf: ArpaUDPBuf.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 ~ { <> srb: ArpaRIPBuf.Buffer; TRUSTED { srb _ LOOPHOLE[sendBuf] }; srb.hdr3 _ [command~response, version~ripVersion, filler~[0, 0]]; ArpaUDP.SetUserBytes[sendBuf, ArpaRIPBuf.UserBytesFromNumTuples[iSend]]; { destAddress: Address; destPort: Port; TRUSTED { [destAddress, destPort] _ ArpaUDP.GetSource[LOOPHOLE[b]] }; ArpaUDP.Send[b~sendBuf, address~destAddress, port~destPort]; }; ArpaUDP.FreeBuffers[sendBuf]; sendBuf _ NIL; }; AddToSendBuf: CardTab.EachPairAction -- [key, val] RETURNS [quit]-- ~ { <> IF (sendBuf # NIL) AND (iSend >= ArpaRIPBuf.maxTuples) THEN { Send[]; sendBuf _ NIL }; IF sendBuf = NIL THEN { sendBuf _ ArpaUDP.AllocBuffers[h~routingSocketHandle]; iSend _ 0 }; AddToSendBufInner[routingEntry~NARROW[val], net~AddressFromKey[key]]; iSend _ iSend + 1; RETURN [FALSE] }; AddToSendBufInner: ENTRY PROC [routingEntry: RoutingEntry, net: Address] ~ --INLINE-- { TRUSTED { srb: ArpaRIPBuf.Buffer ~ LOOPHOLE[sendBuf]; srb.body.tuples[iSend] _ [addressFamily~ripArpaAddressFamily, filler1~[0,0], address~net, filler2~[[0,0], [0,0]], filler3~[[0,0], [0,0]], delay~Basics.FFromCard32[routingEntry.hops]]; }; }; IF b = NIL THEN ERROR; IF NOT ArpaExtras.IsMyAddress[b.hdr1.dest] THEN RETURN; -- Simple router responds only to requests directed at it. nReq _ ArpaRIPBuf.NumTuplesFromUserBytes[userBytes]; IF (nReq = 1) AND (b.body.tuples[0].addressFamily = [0, 0]) AND (Basics.Card32FromF[b.body.tuples[0].delay] > ArpaRouter.maxHops) THEN { <> [] _ CardTab.Pairs[routingTable, AddToSendBuf]; } ELSE { <> FOR iReq: CARDINAL IN [0 .. nReq) DO adr: Address; routingEntry: RoutingEntry; IF b.body.tuples[iReq].addressFamily # ripArpaAddressFamily THEN LOOP; adr _ b.body.tuples[iReq].address; routingEntry _ NARROW[ LookupEntry[adr] ]; IF routingEntry # NIL THEN [] _ AddToSendBuf[KeyFromAddress[adr], routingEntry]; ENDLOOP; }; IF sendBuf # NIL THEN { Send[]; sendBuf _ NIL }; responsesSent _ responsesSent.SUCC; }; totalTuples: CARD _ 0; bogusTuples: CARD _ 0; ProcessResponse: PROC [b: ArpaRIPBuf.Buffer, userBytes: CARDINAL] ~ { <> network: Network _ NARROW[b.ovh.network]; immediate: Address _ b.hdr1.source; tupleAddress: Address; hops: CARD; UpdateEntryFromTuple: ENTRY PROC [routingEntry: RoutingEntry] ~ { IF (routingEntry.network = network) AND (routingEntry.immediate = immediate) THEN { <> IF Monitoring[] AND (routingEntry.hops # hops) THEN PostChange[tupleAddress, routingEntry, hops, 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[tupleAddress, routingEntry, hops, immediate]; routingEntry.network _ network; routingEntry.immediate _ immediate; }; routingEntry.hops _ hops; routingEntry.sweepsSinceRefresh _ 0; IF hops >= unreachable THEN { routingEntry.network _ NIL; routingEntry.immediate _ unknownAddress }; }; UpdateDefaultEntryFromTuple: ENTRY PROC [routingEntry: RoutingEntry] ~ { IF (routingEntry.immediate # immediate) AND (routingEntry.hops < maxHops) AND (routingEntry.sweepsSinceRefresh < suspectSweeps) THEN RETURN; IF Monitoring[] THEN PostChange[unknownAddress, routingEntry, 1, immediate]; routingEntry.network _ network; routingEntry.immediate _ immediate; routingEntry.hops _ 1; -- Kludge! routingEntry.sweepsSinceRefresh _ 0; }; UpdateDefaultEntryNotFromTuple: ENTRY PROC [routingEntry: RoutingEntry] ~ { IF routingEntry.hops < unreachable THEN RETURN; IF Monitoring[] THEN PostChange[unknownAddress, routingEntry, maxHops, immediate]; routingEntry.network _ network; routingEntry.immediate _ immediate; routingEntry.hops _ maxHops; -- Kludge! routingEntry.sweepsSinceRefresh _ 0; }; FOR i: CARDINAL IN [0 .. ArpaRIPBuf.NumTuplesFromUserBytes[userBytes]) DO totalTuples _ totalTuples.SUCC; tupleAddress _ b.body.tuples[i].address; hops _ Basics.Card32FromF[b.body.tuples[i].delay]; SELECT TRUE FROM ArpaExtras.IsSpecificNet[tupleAddress] => UpdateEntryFromTuple[NARROW[GetEntry[tupleAddress]]]; tupleAddress = unknownAddress => UpdateDefaultEntryFromTuple[defaultRoutingEntry]; ENDCASE => bogusTuples _ bogusTuples.SUCC; ENDLOOP; UpdateDefaultEntryNotFromTuple[defaultRoutingEntry]; }; bogusRedirects: CARD _ 0; Redirect: PUBLIC PROC [dest: Address, network: Network, immediate: Address] ~ { RedirectInner: ENTRY PROC [routingEntry: RoutingEntry] ~ { hops: Hops ~ IF routingEntry.hops <= maxHops THEN routingEntry.hops ELSE maxHops; IF Monitoring[] THEN PostChange[dest, routingEntry, hops, immediate, icmp]; routingEntry.network _ network; routingEntry.immediate _ immediate; routingEntry.hops _ hops; routingEntry.sweepsSinceRefresh _ 0; }; IF NOT ArpaExtras.IsSpecificNet[dest] THEN { bogusRedirects _ bogusRedirects.SUCC; RETURN }; RedirectInner[NARROW[GetEntry[dest]]]; }; 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 WHILE network # NIL DO netAddress: Address; IF network.arpa.host = unknownAddress THEN LOOP; netAddress _ ArpaExtras.NetAndSubnetNumberWithMask[network.arpa.host, ArpaTranslation.GetSubnetMask[network]]; ConnectNetInner[NARROW[GetEntry[netAddress]]]; ENDLOOP; }; Sweep: PROC ~ { <> CheckEntry: CardTab.EachPairAction -- [key, val] RETURNS [quit]-- ~ { CheckEntryInner[NARROW[val]]; RETURN [FALSE] }; CheckEntryInner: ENTRY PROC [routingEntry: RoutingEntry] ~ { IF routingEntry.sweepsSinceRefresh >= invalidSweeps THEN routingEntry.hops _ unreachable; routingEntry.sweepsSinceRefresh _ routingEntry.sweepsSinceRefresh.SUCC; }; [] _ CardTab.Pairs[routingTable, CheckEntry]; CheckEntryInner[defaultRoutingEntry]; }; packetsReceived: INT _ 0; requestsReceived: INT _ 0; responsesReceived: INT _ 0; badLength: INT _ 0; badProtocol: INT _ 0; badCommand: INT _ 0; sweeps: CARD _ 0; minSweepPulses: Pulses _ sweepPulses; lastSweep: Pulses _ BasicTime.GetClockPulses[]; Daemon: PROC ~ { DO sinceSweep: Pulses ~ PulsesSince[lastSweep]; b: ArpaUDPBuf.Buffer; getTimeout: Msecs ~ IF sinceSweep >= sweepPulses THEN ArpaUDP.dontWait ELSE (1 + (BasicTime.PulsesToMicroseconds[sweepPulses - sinceSweep] / 1000)); ArpaUDP.SetGetTimeout[routingSocketHandle, getTimeout]; IF (b _ ArpaUDP.Get[routingSocketHandle]) # NIL THEN BEGIN <> userBytes: CARDINAL ~ ArpaUDP.GetUserBytes[b]; rB: ArpaRIPBuf.Buffer; packetsReceived _ packetsReceived.SUCC; IF (userBytes < ArpaRIPBuf.hdrBytes) OR (userBytes > ArpaRIPBuf.maxBytes) THEN { badLength _ badLength.SUCC; GOTO Next }; TRUSTED { rB _ LOOPHOLE[b] }; IF rB.hdr3.version = 0 THEN { badProtocol _ badProtocol.SUCC; GOTO Next }; SELECT rB.hdr3.command FROM request => { requestsReceived _ requestsReceived.SUCC; ProcessRequest[rB, userBytes] }; response => { responsesReceived _ responsesReceived.SUCC; ProcessResponse[rB, userBytes] }; ENDCASE => { badCommand _ badCommand.SUCC; }; GOTO Next; EXITS Next => IF b # NIL THEN ArpaUDP.FreeBuffers[b]; END ELSE BEGIN <> minSweepPulses _ MIN[minSweepPulses, PulsesSince[lastSweep]]; ConnectNets[]; Sweep[]; sweeps _ sweeps.SUCC; lastSweep _ BasicTime.GetClockPulses[]; END; ENDLOOP; }; <> PokeGateways: PROC ~ { b: ArpaUDPBuf.Buffer; rB: ArpaRIPBuf.Buffer; b _ ArpaUDP.AllocBuffers[h~routingSocketHandle]; TRUSTED { rB _ LOOPHOLE[b] }; rB.hdr3 _ [command~request, version~ripVersion, filler~[0, 0]]; rB.body.tuples[0] _ [addressFamily~[0, 0], filler1~[0,0], address~unknownAddress, filler2~[[0,0], [0,0]], filler3~[[0,0], [0,0]], delay~Basics.FFromCard32[ArpaRouter.unreachable]]; ArpaUDP.SetUserBytes [b~b, bytes~ArpaRIPBuf.UserBytesFromNumTuples[1]]; ArpaUDP.Send[b~b, address~ArpaExtras.broadcastAddress, port~ripPort]; ArpaUDP.FreeBuffers[b]; }; <> Route: PUBLIC PROC [him: Arpa.Address] RETURNS [network: Network, immediate: Address] ~ { entry: REF; RouteInner: ENTRY PROC [routingEntry: RoutingEntry] ~ --INLINE-- { network _ routingEntry.network; immediate _ IF routingEntry.hops = 0 THEN him ELSE routingEntry.immediate; }; IF (entry _ LookupEntry[him]) # NIL THEN { RouteInner[NARROW[entry]]; RETURN }; IF (entry _ LookupEntry[ArpaExtras.NetAndSubnetNumber[him]]) # NIL THEN { RouteInner[NARROW[entry]]; RETURN }; IF (entry _ LookupEntry[Arpa.NetNumber[him]]) # NIL THEN { RouteInner[NARROW[entry]]; RETURN }; RouteInner[defaultRoutingEntry]; }; <> 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; }; defaultRoutingEntry _ NEW[RoutingEntryObject]; [] _ CardTab.Pairs[routingTable, SmashEntry]; PokeGateways[]; }; <> eventLock: RoutingEntry _ NEW[RoutingEntryObject]; EventProc: TYPE ~ ArpaRouterPrivate.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 [key: Address, old: RoutingEntry, newHops: Hops, newImmediate: Address, why: ArpaRouterPrivate.EventReason _ rip] ~ { PostChangeInner: ENTRY PROC [routingEntry: RoutingEntry _ eventLock] ~ { FOR pH: EventProcList _ eventProcList, pH.next WHILE pH # NIL DO (pH.proc)[ key, [ hops~old.hops, immediate~old.immediate, time~(old.sweepsSinceRefresh*sweepSeconds)], [ hops~newHops, immediate~newImmediate, time~0], why ]; ENDLOOP; }; PostChangeInner[]; }; <> 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] ~ { entry: REF; GetHopsInner: ENTRY PROC [routingEntry: RoutingEntry] RETURNS [Hops] ~ { RETURN [routingEntry.hops] }; IF (entry _ LookupEntry[address]) # NIL THEN RETURN[GetHopsInner[NARROW[entry]]]; IF (entry _ LookupEntry[ArpaExtras.NetAndSubnetNumber[address]]) # NIL THEN RETURN[GetHopsInner[NARROW[entry]]]; IF (entry _ LookupEntry[Arpa.NetNumber[address]]) # NIL THEN RETURN[GetHopsInner[NARROW[entry]]]; RETURN [unreachable]; -- don't use default route to determine hops }; RTEFromRE: PROC [routingEntry: RoutingEntry] RETURNS [ArpaRouter.RoutingTableEntry] ~ INLINE { RETURN [[hops~routingEntry.hops, immediate~routingEntry.immediate, time~(routingEntry.sweepsSinceRefresh*sweepSeconds)]]; }; GetRouting: PUBLIC PROC [address: Address] RETURNS [rte: ArpaRouter.RoutingTableEntry] ~ { entry: REF; GetRoutingInner: ENTRY PROC [routingEntry: RoutingEntry] RETURNS [ArpaRouter.RoutingTableEntry] ~ { RETURN [RTEFromRE[routingEntry]]; }; IF (entry _ LookupEntry[address]) # NIL THEN RETURN [GetRoutingInner[NARROW[entry]]]; IF (entry _ LookupEntry[ArpaExtras.NetAndSubnetNumber[address]]) # NIL THEN RETURN [GetRoutingInner[NARROW[entry]]]; IF (entry _ LookupEntry[Arpa.NetNumber[address]]) # NIL THEN RETURN [GetRoutingInner[NARROW[entry]]]; RETURN [GetRoutingInner[defaultRoutingEntry]]; }; Enumerate: PUBLIC PROC [ low: Hops _ 0, high: Hops _ unreachable, proc: PROC [Address, ArpaRouter.RoutingTableEntry]] ~ { EachPair: CardTab.EachPairAction -- [key, val] RETURNS [quit] -- ~ { rte: ArpaRouter.RoutingTableEntry; EachPairInner: ENTRY PROC [routingEntry: RoutingEntry] RETURNS [inRange: BOOL] ~ --INLINE-- { IF (inRange _ ((routingEntry.hops >= low) AND (routingEntry.hops <= high))) THEN { rte _ RTEFromRE[routingEntry]; }; }; IF EachPairInner[NARROW[val]].inRange THEN proc[ AddressFromKey[key], rte ]; }; [] _ CardTab.Pairs[routingTable, EachPair]; }; <> daemonProcess: PROCESS; routingSocketHandle: ArpaUDP.Handle; Init: PROC ~ { <<>> <> CommDriver.InsertReceiveProc[network~NIL, type~arpa, proc~ArpaRouterPrivate.TakeThis]; <<>> <> Booting.RegisterProcs[r: Rollback]; <> routingSocketHandle _ ArpaUDP.Create[localPort~ripPort]; daemonProcess _ FORK Daemon[]; ConnectNets[]; PokeGateways[]; }; Init[]; }.