// PupAlComProcb.bcpl - Pup level 0 driver for the ComProc
// Copyright Xerox Corporation 1979

// Last modified January 30, 1979  1:28 PM by Boggs

get "Pup0.decl"
get "PupAlComProc.decl"

external
[
// outgoing procedures
EncapsulateCPPup; SendCPPacket; SendCPStats
CPInputDone; CPOutputDone
CPProcess; CPPupFilter; CPRoutingFilter

// incoming procedures
Enqueue; Dequeue; Dismiss; Min; MultEq; DoubleIncrement
SetTimer; TimerHasExpired; MoveBlock
StartCPT; StopCPT; StartCPR; StopCPR

// incoming statics
pbiFreeQ; lenPup; cpNDB; cpLT
]

//----------------------------------------------------------------------------
let EncapsulateCPPup(pbi, pdh) be
//----------------------------------------------------------------------------
// Performs ComProc dependent encapsulation
// pbi points at a PBI
// pdh is physical destination host for Pup
[
pbi>>CPPBI.dest = pdh
pbi>>CPPBI.type = typePup
pbi>>CPPBI.broadcast = pdh eq 0
pbi>>CPPBI.allLines = false
pbi>>PBI.packetLength = (pbi>>PBI.pup.length+3) & #177776
]

//----------------------------------------------------------------------------
and SendCPPacket(pbi) be
//----------------------------------------------------------------------------
// Routes packet to host given in CPPBI.dest via some line.
// Sends broadcast packets out all lines that are up.
// Packets to self are routed through a looped-back line, if any.
[
test pbi>>CPPBI.allLines % pbi>>CPPBI.broadcast
   ifso CPOutputDispose(pbi, 0)  //send first on line 0
   ifnot
      [
      let rte = cpNDB>>CPNDB.rt↑(pbi>>CPPBI.dest)
      test pbi>>CPPBI.dest le maxHost &  //host in range?
       rte<<RTE.hopCnt ne #377  //can get there from here?
         ifso EnqueueCPOutput(pbi, rte<<RTE.line)  //yes, send
         ifnot Enqueue(pbi>>PBI.queue, pbi)  //no, discard
      ]
]

//----------------------------------------------------------------------------
and SendCPStats(pbi, ndb) = valof
//----------------------------------------------------------------------------
[
pbi>>PBI.pup.length = pupOvBytes + lenSLAStats
let stats = lv pbi>>PBI.pup.words
stats>>SLAStats.statsType = netTypeSLA
stats>>SLAStats.statsVersion = slaStatsVersion
stats>>SLAStats.maxHost = maxHost
MoveBlock(lv stats>>SLAStats.rt↑1, lv ndb>>CPNDB.rt↑1, maxHost)
stats>>SLAStats.maxLine = maxLine
for line = 0 to maxLine do
   MoveBlock(lv stats>>SLAStats.lineStats↑line,
    lv ndb>>CPNDB.lcb↑line.stats, lenSLAStats)
resultis true
]

//----------------------------------------------------------------------------
and EnqueueCPOutput(pbi, line) be
//----------------------------------------------------------------------------
// Enqueues pbi on output queue for line, then starts output if required.
[
let lcb = lv cpNDB>>CPNDB.lcb↑line

// Decide whether high- or low-priority packet.
// Non-Pups (ie, just routing tables at present) are always high-priority.
// Pups are high-priority iff Pup length le maxHiPriBytes and there are not
// any already-queued low-priority Pups with same source and destination.
// The latter check is made so as to avoid scrambling packets belonging
// to a single conversation.
let high = valof
   [
   if pbi>>CPPBI.type ne typePup resultis true  //non-Pup
   if pbi>>PBI.pup.length gr maxHiPriBytes resultis false  //large Pup
   let curr = lcb>>LCB.lowOQ.head
   while curr ne 0 do
      [  // Search for low-priority Pup with same source and destination.
      if MultEq(lv curr>>PBI.pup.dPort, lv pbi>>PBI.pup.dPort, 2*lenPort) then
         resultis false  //found one, make new pbi low-priority also
      curr = curr!0
      ]
   resultis true
   ]
Enqueue((high? lv lcb>>LCB.highOQ, lv lcb>>LCB.lowOQ), pbi)

// Start output if necessary
StartCPOutput(lcb)
]

//----------------------------------------------------------------------------
and StartCPOutput(lcb) be
//----------------------------------------------------------------------------
// Starts output if line is idle and there is a packet waiting to go out.
[
if lcb>>LCB.oPBI eq 0 then
   [
   // Output not already active, try to dequeue a pbi.
   // Check the high-priority queue first, then the low.
   lcb>>LCB.oPBI = Dequeue(lv lcb>>LCB.highOQ)
   if lcb>>LCB.oPBI eq 0 then lcb>>LCB.oPBI = Dequeue(lv lcb>>LCB.lowOQ)
   if lcb>>LCB.oPBI ne 0 then
      [
      // Now idle, start transmitter
      StartCPT(lcb)

      // Compute timeout on the basis of worst-case transmission time
      // at 2160 baud (2400 baud minus 10% for multiplexor overhead and slop).
      // Timeout = (2*packetLength+frameOverheadBytes) / 270 seconds
      //  = 10 * (2*packetLength+frameOverheadBytes) / 27 timer ticks (10 ms).
      // We use 2*packetLength in case every byte is a DLE that is doubled.
      // 270 bytes/second corresponds to 2160 baud.
      SetTimer(lv lcb>>LCB.tTimer,
       (10*(2 * lcb>>LCB.oPBI>>PBI.packetLength + frameOverheadBytes))/27)
      ]
   ]
]

//----------------------------------------------------------------------------
and CPOutputDone(lcb) be
//----------------------------------------------------------------------------
// Called from interrupt level after a packet has been sent.
[
DoubleIncrement(lv lcb>>LCB.transmitPackets)
DoubleIncrement(lv lcb>>LCB.transmitBytes, lcb>>LCB.oPBI>>PBI.packetLength)
CPOutputDispose(lcb>>LCB.oPBI, lcb>>LCB.line+1)
lcb>>LCB.oPBI = 0
StartCPOutput(lcb)
]

//----------------------------------------------------------------------------
and CPOutputDispose(pbi, firstLine) be
//----------------------------------------------------------------------------
// Called to dispose of a pbi possibly being sent to multiple lines.
// If pbi is going to all lines, send it to firstLine (if in range).
// If pbi is a broadcast Pup, send it to the first line ge
// firstLine that is up.
[
if pbi>>CPPBI.allLines % pbi>>CPPBI.broadcast then
   for line = firstLine to maxLine do
      if cpLT>>CPLT.cpLTE↑line.exists & (pbi>>CPPBI.allLines %
         (lv cpNDB>>CPNDB.lcb↑line)>>LCB.state ne slaLineDown) then
         [
         EnqueueCPOutput(pbi, line)
         return
         ]
Enqueue(pbi>>PBI.queue, pbi)  //no more lines to output to
]

//----------------------------------------------------------------------------
and CPInputDone(lcb) be
//----------------------------------------------------------------------------
//called from interrupt level after a packet has arrived.
[
let pbi = lcb>>LCB.iPBI
pbi>>PBI.ndb = cpNDB
pbi>>CPPBI.line = lcb>>LCB.line
DoubleIncrement(lv lcb>>LCB.receivePackets)
DoubleIncrement(lv lcb>>LCB.receiveBytes, pbi>>PBI.packetLength)
let pf = cpNDB>>CPNDB.pfQ.head
while pf ne 0 do
   [
   if (pf>>PF.predicate)(pbi) then
      [
      lcb>>LCB.iPBI = 0
      Enqueue(pf>>PF.queue, pbi)
      break
      ]
   pf = pf>>PF.link
   ]
]

//----------------------------------------------------------------------------
and CPPupFilter(pbi) =
//----------------------------------------------------------------------------
pbi>>CPPBI.type eq typePup &
 pbi>>PBI.packetLength eq ((pbi>>PBI.pup.length+3) & #177776)

//----------------------------------------------------------------------------
and CPRoutingFilter(pbi) = pbi>>CPPBI.type eq typeRoute
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
and CPProcess() be
//----------------------------------------------------------------------------
// This background process maintains an internal routing table,
// times out hung transmitter lines, and restarts reception on lines that
// ran out of PBIs.

// The routing algorithm is similar to that used in the Arpanet,
// but with a modification that permits keeping less local state.
// The state we maintain is simply a line number and a hop count
// for every destination host.  When a routing table is received
// from a neighbor over a line l, we simply purge all entries in
// our own routing table that route out over line l, then replace
// entries in our routing table with corresponding ones in the
// incoming table iff the incoming entry's hop count +1 is le ours.
// The test is "le" rather than "ls" so that in the long run we will
// spread the load among all equally-good routes.
// Purged entries have a hop count of "infinity" = #377.
// When a line or neighbor goes down (no routing table received
// for some timeout), we purge all entries routing out through
// that line.  If there is an alternate path to some purged
// destination, we will discover that eventually, when some other
// neighbor tells us about it, whereas in the Arpanet algorithm
// the alternate path is usually known immediately since the
// number of hops to a given destination through each line
// is kept, and hence a new routing can be computed immediately.
// Our algorithm, however, requires only (number of hosts) entries
// in the routing table, whereas the Arpanet algorithm requires
// an array of size (number of hosts)*(number of lines).

// A special case we handle is that of a looped-back line
// (detected when we receive our own routing table over that line).
// In this case, we set up our own entry in the routing table
// to route out over that line (with 1 hop), since this is useful
// for the purpose of testing the line.  However, when we send
// our routing table to a neighbor, we zero our own entry's hop
// count in the copy we give him so that the normal routing table
// update process works correctly.
[
let rtTimer = nil; SetTimer(lv rtTimer, 0)
   [
   Dismiss(10)  // 100 ms
   if cpNDB>>CPNDB.rIQ.head ne 0 then
      [  //received a routing table
      let pbi = Dequeue(lv cpNDB>>CPNDB.rIQ)
      let line = pbi>>CPPBI.line
      let lcb = lv cpNDB>>CPNDB.lcb↑line
      SetTimer(lv lcb>>LCB.rTimer, routingTimeout)
      PurgeLineFromRT(line)  //purge all entries routing to line
      test pbi>>RTPBI.srcHost eq cpNDB>>NDB.localHost
         ifso
            [  //received my routing table, line is looped back
            lcb>>LCB.state = slaLineLoopedBack
            let rte = lv cpNDB>>CPNDB.rt↑(cpNDB>>NDB.localHost)
            rte>>RTE.line = line  //route to myself via this line
            rte>>RTE.hopCnt = 1
            ]
         ifnot
            [  //received a neighbor's routing table
            lcb>>LCB.state = slaLineUp
            for i = 1 to Min(maxHost, pbi>>RTPBI.numEntries) do
               [
               let rte = lv cpNDB>>CPNDB.rt↑i
               let newHop = pbi>>RTPBI.rt↑i.hopCnt+1
               if newHop le rte>>RTE.hopCnt then
                  [
                  rte>>RTE.hopCnt = newHop le maxHops? newHop, #377
                  rte>>RTE.line = line
                  ]
               ]
            ]
      Enqueue(pbiFreeQ, pbi)
      ]

// CPProcess (cont'd)

   for line = 0 to maxLine do if cpLT>>CPLT.cpLTE↑line.exists then
      [
      //flush routing entries for dead lines
      let lcb = lv cpNDB>>CPNDB.lcb↑line
      if TimerHasExpired(lv lcb>>LCB.rTimer) then
         [
         lcb>>LCB.state = slaLineDown
         PurgeLineFromRT(line)
         ]
      if TimerHasExpired(lv lcb>>LCB.tTimer) & lcb>>LCB.oPBI ne 0 then
         while lcb>>LCB.oPBI ne 0 do  // Transmitter is hung.
            [
            // Stop it and dispose of all pbis queued for this line.
            // Note that CPOutputDone will cause the hardware to be
            // started for each pbi discarded, but since the line is
            // dead that doesn't really matter.
            StopCPT(lcb)
            CPOutputDone(lcb)
            ]
      // Restart reception for a line that ran out of input PBIs.
      if lcb>>LCB.iPBI eq 0 then
         [
         lcb>>LCB.iPBI = Dequeue(pbiFreeQ)
         if lcb>>LCB.iPBI ne 0 then StartCPR(lcb)
         ]
      ]

   if TimerHasExpired(lv rtTimer) then
      [
      //time to broadcast our level 0 routing table
      let pbi = Dequeue(pbiFreeQ); if pbi ne 0 then
         [
         SetTimer(lv rtTimer, routingProbeInterval)
         pbi>>PBI.queue = pbiFreeQ
         pbi>>CPPBI.allLines = true
         pbi>>CPPBI.type = typeRoute
         MoveBlock(lv pbi>>RTPBI.rt, lv cpNDB>>CPNDB.rt, maxHost*lenRTE)
         pbi>>RTPBI.rt↑(cpNDB>>NDB.localHost) = 0
         pbi>>RTPBI.srcHost = cpNDB>>NDB.localHost
         pbi>>RTPBI.numEntries = maxHost
         pbi>>PBI.packetLength = lenRTPacket*2
         SendCPPacket(pbi)
         ]
      ]
   ] repeat
]

//----------------------------------------------------------------------------
and PurgeLineFromRT(line) be
//----------------------------------------------------------------------------
[
for j = 1 to maxHost do
   if cpNDB>>CPNDB.rt↑j.line eq line then
      cpNDB>>CPNDB.rt↑j.hopCnt = -1
]