-- RouterImpl.mesa (last edited by: BLyon on: March 21, 1981 11:53 AM) -- Function: The implementation module for the Pilot OISCP Router switch. -- Last Edited by: Levin, August 9, 1983 9:22 am DIRECTORY Basics USING [LongNumber], BufferDefs USING [OisBuffer], Checksums USING [SetChecksum, TestChecksum], CommunicationInternal USING [], CommFlags USING [doDebug, doStats, doStorms], CommUtilDefs USING [CopyLong], DriverDefs USING [ ChangeNumberOfInputBuffers, DriverXmitStatus, GetDeviceChain, Glitch, MaybeGetFreeOisBuffer, Network, PutOnGlobalDoneQueue, RouterObject, SetOisRouter], OISCP USING [ allHostIDs, CreditReceiveOisBuffer, EnqueueOis, MaybeGetFreeReceiveOisBufferFromPool, unknownNetID, unknownSocketID], OISCPConstants USING [routingInformationSocket], OISCPTypes USING [ bytesPerPktHeader, bytesPerPktText, maxBytesPerPkt, OISErrorCode, TransPortControl], Process USING [Yield], ProcessorFace USING [GetClockPulses], Router USING [ AddNetwork, FindNetworkAndTransmit, FindDestinationRelativeNetID, ForwardPacket, RemoveNetwork, RoutingInformationPacket, RoutingTableOn, RoutingTableOff, SocketTable, StateChanged, XmitStatus], SocketInternal USING [SocketHandle], SpecialCommunication USING [RoutersFunction], NSAddress USING [ broadcastHostNumber, GetProcessorID, HostNumber, NetworkAddress, nullNetworkNumber, NetworkNumber, SocketNumber], StatsDefs USING [StatIncr]; RouterImpl: MONITOR LOCKS socketRouterLock IMPORTS BufferDefs, Checksums, CommUtilDefs, DriverDefs, OISCP, Process, ProcessorFace, Router, NSAddress, StatsDefs EXPORTS BufferDefs, CommunicationInternal, OISCP, Router SHARES BufferDefs = BEGIN OPEN DriverDefs, OISCP, OISCPTypes, SocketInternal, StatsDefs; -- Many of these variables must eventually live in outerspace so that multiple MDSs -- access the same router variables. The modules in the primary MDS will have the -- proceses and will perform the initialization of the "globals", while the others will not. -- The lock covers both SocketImpl and RouterImpl, specifically the socket objects, -- the socket table, and spare socket ID counter. These will all live in outerspace. -- The monitor locks some variables on the global frame too. They can be MDS specific. -- EXPORTed TYPEs Network: PUBLIC TYPE = DriverDefs.Network; -- switches and variables that don't change during execution unless for diagnostics primaryMDS: PUBLIC BOOLEAN ← TRUE; -- we are in the primary MDS. checkIt: PUBLIC BOOLEAN ← TRUE; -- checksums on for everybody driverLoopback: BOOLEAN ← FALSE; -- loopback in router stormy: BOOLEAN ← FALSE; -- storms for debugging are not on routersFunction: PUBLIC SpecialCommunication.RoutersFunction ← vanillaRouting; myHostID: NSAddress.HostNumber; -- processor ID of this system element initialSpareSocketID: NSAddress.SocketNumber = [1001]; initialTransportControl: OISCPTypes.TransPortControl = [trace: FALSE, filler: 0, hopCount: 0]; -- oiscp router object for the dispatcher. There will only be one for all MDSs, but it -- can live on all global frame instances or we can put it in hyperspace and have the -- dispatcher access it via a long pointer. The former is preferable. oiscpRouter: DriverDefs.RouterObject ← [input: LOOPHOLE[ReceivePacket], broadcast: LOOPHOLE[SendBroadcastPacketToCorrectNet], addNetwork: Router.AddNetwork, removeNetwork: Router.RemoveNetwork, stateChanged: Router.StateChanged]; -- monitor protected data. -- parameters for killing packets for debugging lightning: INTEGER ← 30; bolt: INTEGER ← 10; -- I think only the following need be in outerspace, accesible via a pointer since these -- will be touched by multiple MDS processes via their copy of RouterImpl and SocketImpl. socketRouterLock: PUBLIC MONITORLOCK; -- lock for the router and all the sockets. -- Some day the socketIDs in use will be remembered across wrap around, and maybe -- the rebooting of Pilot. spareSocketID: NSAddress.SocketNumber; -- socket table socketTable: Router.SocketTable; -- various Glitches generated by the router IllegalOisPktLength: ERROR = CODE; -- Cool Procedures -- This procedure assigns a temporary socket number in an NSAddress.NetworkAddress. -- Some day the active socket numbers in use will be kept around, so that on wrap -- around an unused number will be assigned. When the system element is connected to -- more than one network, this procedure must return a list of NSAddress.NetworkAddress. AssignOisAddress: PUBLIC ENTRY PROCEDURE RETURNS [localAddr: NSAddress.NetworkAddress] = BEGIN localAddr ← [net: Router.FindDestinationRelativeNetID[NSAddress.nullNetworkNumber], host: myHostID, socket: spareSocketID]; IF (spareSocketID ← [spareSocketID + 1]) = NSAddress.SocketNumber[0] THEN spareSocketID ← initialSpareSocketID; END; -- AssignOisAddress -- This procedure is just like the previous one except that the network number is relative -- to the destination network. That is, we pick that one of our locally connected -- networks that is the best way to get to destNet, with the hope that it is the best -- way to get from destNet to us. AssignDestinationRelativeOisAddress: PUBLIC ENTRY PROCEDURE [destNet: NSAddress.NetworkNumber] RETURNS [localAddr: NSAddress.NetworkAddress] = BEGIN localAddr ← [net: Router.FindDestinationRelativeNetID[destNet], host: myHostID, socket: spareSocketID]; IF (spareSocketID ← [spareSocketID + 1]) = NSAddress.SocketNumber[0] THEN spareSocketID ← initialSpareSocketID; END; -- AssignDestinationRelativeOisAddress -- This procedure tells the OISCP Router about a new socket. AddSocket: PUBLIC ENTRY PROCEDURE [sH: SocketHandle] = BEGIN MaybeIncreaseDriversBuffers: PROCEDURE = INLINE BEGIN previousSH: SocketHandle ← socketTable.first; UNTIL previousSH = NIL DO IF previousSH.pool.total > 0 THEN RETURN; previousSH ← previousSH.next; ENDLOOP; DriverDefs.ChangeNumberOfInputBuffers[TRUE]; -- TRUE => increase END; -- add new socket to the head of the table IF sH.pool.total > 0 THEN MaybeIncreaseDriversBuffers[]; sH.next ← socketTable.first; socketTable.first ← sH; socketTable.length ← socketTable.length + 1; END; -- AddSocket -- This procedure removes a socket from the OISCP Router's tables. RemoveSocket: PUBLIC ENTRY PROCEDURE [sH: SocketHandle] = BEGIN MaybeDecreaseDriversBuffers: PROCEDURE = INLINE BEGIN previousSH ← socketTable.first; UNTIL previousSH = NIL DO IF previousSH.pool.total > 0 THEN RETURN; previousSH ← previousSH.next; ENDLOOP; DriverDefs.ChangeNumberOfInputBuffers[FALSE]; -- FALSE => decrease END; previousSH: SocketHandle; IF socketTable.first = sH THEN socketTable.first ← sH.next ELSE BEGIN previousSH ← socketTable.first; UNTIL previousSH = NIL DO IF previousSH.next = sH THEN BEGIN previousSH.next ← sH.next; EXIT; END; previousSH ← previousSH.next; ENDLOOP; END; socketTable.length ← socketTable.length - 1; IF sH.pool.total > 0 THEN MaybeDecreaseDriversBuffers[]; END; -- RemoveSocket -- This is not an entry procedure because we change it only for debugging and can -- live with a race condition. SetOisStormy: PUBLIC PROCEDURE [new: BOOLEAN] = BEGIN stormy ← new; END; -- SetOisStormy -- This is not an entry procedure because we change it only for debugging and can -- live with a race condition. SetOisCheckit: PUBLIC PROCEDURE [new: BOOLEAN] = BEGIN checkIt ← new; END; -- SetOisCheckIt -- This is not an entry procedure because we change it only for debugging and can -- live with a race condition. SetOisDriverLoopback: PUBLIC PROCEDURE [new: BOOLEAN] = BEGIN driverLoopback ← new; END; -- SetOisDriverLoopback -- This procedure returns the processor ID of this machine. FindMyHostID: PUBLIC PROCEDURE RETURNS [NSAddress.HostNumber] = BEGIN RETURN[myHostID]; END; -- FindMyHostID GetOisPacketTextLength: PUBLIC PROCEDURE [b: BufferDefs.OisBuffer] RETURNS [CARDINAL] = BEGIN RETURN[b.ois.pktLength - bytesPerPktHeader]; END; -- GetOisPacketTextLength SetOisPacketTextLength: PUBLIC PROCEDURE [b: BufferDefs.OisBuffer, len: CARDINAL] = BEGIN IF len IN [0..bytesPerPktText] THEN b.ois.pktLength ← len + bytesPerPktHeader ELSE IF CommFlags.doDebug THEN Glitch[IllegalOisPktLength]; END; -- SetOisPacketTextLength SetOisPacketLength: PUBLIC PROCEDURE [b: BufferDefs.OisBuffer, len: CARDINAL] = BEGIN IF len IN [bytesPerPktHeader..maxBytesPerPkt] THEN b.ois.pktLength ← len ELSE IF CommFlags.doDebug THEN Glitch[IllegalOisPktLength]; END; -- SetOisPacketLength -- Hot Procedures -- This procedure transmits a packet over a locally connected network. -- The procedure assumes that all fields of the buffer have been filled in appropriately, -- except the encapsulation and buffer length which depend on the network. If the -- packet is destined for a local socket and we do NOT want to do loopback at the -- driver or at the network, then it gets looped back here. Broadcast -- packets are NOT delivered to the source socket. -- Packets are no longer copied into system buffers. -- The caller owns the buffer. The buffer is asynchronously sent and retruned to the -- caller process by the dispatcher using b.requeueProcedure. SendPacket: PUBLIC PROCEDURE [b: BufferDefs.OisBuffer] = BEGIN IF CommFlags.doStorms AND stormy AND PacketHit[] THEN BEGIN DriverDefs.PutOnGlobalDoneQueue[b]; RETURN; -- for debugging only END; IF b.ois.destination.host = myHostID AND NOT driverLoopback THEN -- packet is for a local socket; broadcast packets are not delivered locally BEGIN IF NOT DeliveredToLocalSocket[b, TRUE] THEN -- TRUE -> copy this buffer BEGIN nullNetwork: Network = NIL; -- because of EXPORTed TYPEs bug -- no socket IF CommFlags.doStats THEN StatIncr[statJunkOisForUsNoLocalSocket]; b.network ← nullNetwork; SendErrorPacket[b, noSocketOisErrorCode, 0]; END; -- we requeue here because we shorted the drivers and dispatcher. -- we Yield here to prevent local communication from using all of the cycles. DriverDefs.PutOnGlobalDoneQueue[b]; Process.Yield[]; END ELSE -- packet is for a remote machine BEGIN -- If the destination net is inaccessible then we will have suffered the overhead of -- computing a checksum, but we don't expect inaccessible nets that often. -- set the checksum if appropriate b.ois.transCntlAndPktTp.transportControl ← initialTransportControl; IF checkIt THEN Checksums.SetChecksum[b] ELSE b.ois.checksum ← 177777B; [] ← Router.FindNetworkAndTransmit[b]; END; END; -- SendPacket -- This procedure is called by the Dispatcher when it sees a valid ois packet in a system -- buffer. The procedure checks the checksum field and then routes the packet to a -- local socket. If this is an internetwork router, then the packets are forwarded over -- a suitable network. We now own this packet. ReceivePacket: PUBLIC PROCEDURE [b: BufferDefs.OisBuffer] = BEGIN badChecksum: BOOLEAN; incomingNet: Network; destHost: NSAddress.HostNumber ← b.ois.destination.host; broadcastPacket: BOOLEAN ← FALSE; IF b.ois.pktLength < OISCPTypes.bytesPerPktHeader THEN BEGIN IF CommFlags.doStats THEN StatIncr[statOisDiscarded]; DriverDefs.PutOnGlobalDoneQueue[b]; -- done with this packet RETURN; END; IF (badChecksum ← IF checkIt THEN NOT Checksums.TestChecksum[b] ELSE FALSE) THEN -- hardware says ok, but bad end-to-end software checksum. BEGIN IF CommFlags.doStats THEN BEGIN StatIncr[statReceivedBadOisChecksum]; StatIncr[statOisDiscarded]; END; DriverDefs.PutOnGlobalDoneQueue[b]; -- done with this packet RETURN; END; -- packet is in good shape, route it. IF CommFlags.doStorms AND stormy AND PacketHit[] THEN BEGIN DriverDefs.PutOnGlobalDoneQueue[b]; RETURN; END; -- for debugging only incomingNet ← b.network; IF destHost = myHostID OR ((broadcastPacket←(destHost = allHostIDs)) AND (incomingNet.netNumber = b.ois.destination.net) OR (b.ois.destination.net = NSAddress.nullNetworkNumber)) THEN BEGIN -- incomming packet for us (we may have broadcast it) IF NOT DeliveredToLocalSocket[b, FALSE] THEN -- FALSE -> do not copy this buffer, but deliver it BEGIN -- routing information socket is part of router in another module IF b.ois.destination.socket = OISCPConstants.routingInformationSocket THEN Router.RoutingInformationPacket[b] -- we still own this packet! ELSE BEGIN -- packet for unknown socket IF NOT broadcastPacket THEN BEGIN SendErrorPacket[b, noSocketOisErrorCode, 0]; IF CommFlags.doStats THEN StatIncr[statJunkOisForUsNoLocalSocket]; END ELSE IF CommFlags.doStats THEN StatIncr[statJunkBroadcastOis] END; DriverDefs.PutOnGlobalDoneQueue[b]; -- done with this packet END; END ELSE SELECT TRUE FROM routersFunction=interNetworkRouting => BEGIN Router.ForwardPacket[b]; -- dispatcher returns to system pool END; b.ois.destination.socket=OISCPConstants.routingInformationSocket => BEGIN Router.RoutingInformationPacket[b]; -- we still own this packet! DriverDefs.PutOnGlobalDoneQueue[b]; END; ENDCASE => BEGIN IF CommFlags.doStats THEN StatIncr[statOisDiscarded]; DriverDefs.PutOnGlobalDoneQueue[b]; -- we got the packet when we shouldn't have! END; END; -- ReceivePacket -- Hot, except should really not exist; therefor cold? -- This procedure attempts to hit a packet with a bolt of lightening, and if it succeeds, -- then it returns true else false. The caller dispenses with the buffer. PacketHit: ENTRY PROCEDURE RETURNS [BOOLEAN] = BEGIN IF (lightning ← lightning + 1) > bolt OR lightning < 0 THEN BEGIN IF lightning > bolt THEN BEGIN IF bolt > 100 THEN BEGIN randLong: LONG CARDINAL ← ProcessorFace.GetClockPulses[]; rand: CARDINAL ← LOOPHOLE[randLong, Basics.LongNumber].lowbits; lightning ← -INTEGER[rand MOD 20B]; bolt ← 10; END ELSE BEGIN lightning ← 0; bolt ← bolt + 1; END; END; IF CommFlags.doStats THEN StatIncr[statZappedP]; RETURN[TRUE]; END ELSE RETURN[FALSE]; END; -- PacketHit -- This procedure finds a local socket object to deliver the packet to, and if it succeeds, -- then it returns true else false. Caller retains ownership of buffer if useCopy is true -- or return is false; caller loses buffer ownership if NOT useCopy and return is true. DeliveredToLocalSocket: ENTRY PROCEDURE [b: BufferDefs.OisBuffer, useCopy: BOOLEAN] RETURNS [BOOLEAN] = BEGIN ENABLE UNWIND => NULL; destSocket: NSAddress.SocketNumber ← b.ois.destination.socket; sH, prevSH: SocketHandle; -- find the correct socket for this packet FOR sH ← (prevSH ← socketTable.first), sH.next UNTIL sH = NIL DO IF sH.localAddr.socket = destSocket THEN BEGIN IF useCopy THEN EnqueueCopyOfNewInput[sH, b] ELSE EnqueueNewInput[sH, b]; -- do some dynamic socket ordering before returning; rearange the list only if -- sH was not in the first two entries of the list. IF prevSH # socketTable.first THEN BEGIN prevSH.next ← sH.next; -- this removes sH from the list sH.next ← socketTable.first; socketTable.first ← sH; -- this puts sH at head of list END; RETURN[TRUE]; END; prevSH ← sH; ENDLOOP; RETURN[FALSE]; END; -- DeliveredToLocalSocket -- This procedure enqueues a new input packet at the socket object. -- The incoming buffer is from a network driver and NOT a local socket. -- The caller of this routine relinquishes ownership of this buffer. EnqueueNewInput: INTERNAL PROCEDURE [sH: SocketHandle, b: BufferDefs.OisBuffer] = INLINE BEGIN IF (sH.channelState = aborted) OR NOT (OISCP.CreditReceiveOisBuffer[sH.pool, b]) THEN BEGIN IF CommFlags.doStats THEN StatsDefs.StatIncr[statOisInputQueueOverflow]; DriverDefs.PutOnGlobalDoneQueue[b]; RETURN; END; b.status ← LOOPHOLE[Router.XmitStatus[goodCompletion]]; EnqueueOis[sH.completedUserGetQueue, b]; BROADCAST sH.newUserInput; END; -- EnqueueNewInput -- This procedure enqueues a new input packet at the socket object. -- The incoming buffer is only from a local socket. -- The caller of this routine retains ownership of this buffer. EnqueueCopyOfNewInput: INTERNAL PROCEDURE [ sH: SocketHandle, b: BufferDefs.OisBuffer] = INLINE BEGIN getBuffer: BufferDefs.OisBuffer ← IF sH.channelState = aborted THEN NIL ELSE MaybeGetFreeReceiveOisBufferFromPool[sH.pool]; -- Copy b into the first OisBuffer on the pendingGetQueue, if there is one. IF (getBuffer # NIL) THEN BEGIN getBuffer.status ← LOOPHOLE[Router.XmitStatus[goodCompletion]]; -- assume always good -- getBuffer is full sized OisBuffer, therefore no need to check length CommUtilDefs.CopyLong[ from: @b.ois.checksum, nwords: (b.ois.pktLength + 1)/2, to: @getBuffer.ois.checksum]; EnqueueOis[sH.completedUserGetQueue, getBuffer]; BROADCAST sH.newUserInput; END ELSE IF CommFlags.doStats THEN StatsDefs.StatIncr[statOisInputQueueOverflow]; -- funny name END; -- EnqueueNewLocalInput -- This procedure causes a broadcast packet to be sent over all networks. BroadcastThisPacket: PUBLIC PROCEDURE [b: BufferDefs.OisBuffer] = BEGIN network: Network; IF CommFlags.doStats THEN StatIncr[statOisBroadcast]; b.allNets ← TRUE; -- this is where it gets turned on b.ois.destination.host ← NSAddress.broadcastHostNumber; b.network ← network ← DriverDefs.GetDeviceChain[]; IF network = NIL THEN BEGIN DriverDefs.PutOnGlobalDoneQueue[b]; IF CommFlags.doStats THEN StatsDefs.StatIncr[statOisSentNowhere]; RETURN; END; SendBroadcastPacketToCorrectNet[b]; END; -- BroadcastThisPacket -- This procedure causes a broadcast packet to be sent out over the right network. SendBroadcastPacketToCorrectNet: PUBLIC PROCEDURE [b: BufferDefs.OisBuffer] = BEGIN network: Network ← b.network; IF ~network.alive OR (b.bypassZeroNet AND network.netNumber = [0, 0]) THEN BEGIN DriverDefs.PutOnGlobalDoneQueue[b]; RETURN; END; -- goes (slowly) around in circles b.ois.destination.net ← b.ois.source.net ← network.netNumber; b.ois.source.host ← myHostID; IF checkIt THEN Checksums.SetChecksum[b] ELSE b.ois.checksum ← 177777B; LOOPHOLE[b.status, DriverDefs.DriverXmitStatus] ← goodCompletion; network.encapsulateOis[b, NSAddress.broadcastHostNumber]; network.sendBuffer[b]; END; -- SendBroadcastPacketToCorrectNet -- This procedure generates and sends an error packet. All or most of the -- offending packet is copied into the the error packet. The caller of this -- Procedure still owns offendingPkt. SendErrorPacket: PUBLIC PROCEDURE [offendingPkt: BufferDefs.OisBuffer, errCode: OISCPTypes.OISErrorCode, errParm: CARDINAL] = BEGIN net: Network = offendingPkt.network; b: BufferDefs.OisBuffer; offenseLen: CARDINAL; IF offendingPkt.ois.transCntlAndPktTp.packetType=error THEN RETURN; -- don't send errors about errors IF (b ← DriverDefs.MaybeGetFreeOisBuffer[])=NIL THEN RETURN; -- give up! b.ois.destination ← offendingPkt.ois.source; b.ois.source ← [ IF net=NIL THEN OISCP.unknownNetID ELSE net.netNumber, myHostID, OISCP.unknownSocketID]; b.ois.transCntlAndPktTp ← [initialTransportControl, error]; b.ois.errorType ← errCode; b.ois.errorParameter ← errParm; offenseLen ← MIN[offendingPkt.ois.pktLength, OISCPTypes.bytesPerPktText-4]; -- four is for errorType and errorParameter. CommUtilDefs.CopyLong[@offendingPkt.ois, (offenseLen+1)/2, @b.ois.errorBody]; SetOisPacketTextLength[b, offenseLen+4]; SendPacket[b]; END; -- SendErrorPacket --Cold Procedures -- This procedure turns the router on. The Communication software is written with the -- idea of eventually turning the code on and off during execution, and so we should -- get the latest values of netID and hostID when being turned back on. OisRouterOn: PUBLIC PROCEDURE = BEGIN OisRouterActivate[]; Router.RoutingTableOn[]; DriverDefs.SetOisRouter[@oiscpRouter]; END; -- OisRouterOn OisRouterActivate: ENTRY PROCEDURE = INLINE BEGIN myHostID ← NSAddress.GetProcessorID[]; IF primaryMDS THEN socketTable ← [length: 0, first: NIL]; END; -- OisRouterActivate OisRouterOff: PUBLIC PROCEDURE = BEGIN DriverDefs.SetOisRouter[NIL]; OisRouterDeactivate[]; Router.RoutingTableOff[]; END; -- OisRouterOff OisRouterDeactivate: ENTRY PROCEDURE = INLINE BEGIN -- cleanup the socket table. --IF primaryMDS THEN END; -- OisRouterDeactivate --Cold -- initialization IF primaryMDS THEN spareSocketID ← initialSpareSocketID; END. -- RouterImpl module. LOG Time: January 19, 1980 4:05 PM By: Dalal Action: Split OISCPRouter into two. Time: January 21, 1980 6:07 PM By: Dalal Action: one lock for SocketImpl and RouterImpl. Time: March 13, 1980 4:55 PM By: BLyon Action: modified SendPacket. Time: March 18, 1980 4:09 PM By: BLyon Action: Modified EnqueueNewInput where it gets an input buffer. Time: May 12, 1980 6:38 PM By: BLyon Action: Put checksum into microcode (switched order parameters too). Time: May 16, 1980 10:07 AM PM By: BLyon Action: Removed all ShortenPointer to allow multiple MDS. Time: June 30, 1980 1:02 PM By: BLyon Action: Checkit init to FALSE instead of TRUE.. Time: July 22, 1980 11:03 AM By: BLyon Action: Checkit changed back to TRUE; checksums stuff put in seperate modules; we now receive out own broadcasts. Time: August 1, 1980 1:29 PM By: BLyon Action: replaced internetRouter by routersFunction. Time: September 13, 1980 6:15 PM By: HGM Action: Add StateChanged. Time: September 18, 1980 3:34 PM By: BLyon Action: AssignOisAddress puts unknownNetID in network field rather than primaryNetID. Time: February 24, 1981 3:25 PM By: BLyon Action: put extra clause in ReceivePacket so that an INR would forward a broadcast instead of eating it with a local socket.