// 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
]