.alone←declaration(expurgate)=0;
.if alone then start
.require "<altosource>ttydefs.pub" source!file
.end
.every heading (|Pup Package|,|November 21, 1981|,{page})
.once center
Pup Package
.skip 3
The Pup package consists of a large body of Alto software that implements communication by means of Pups (Parc Universal Packets) and Pup-based protocols. This software is broken into a number of independent modules implementing various "levels" of protocol in a hierarchical fashion. Each level depends on primitives defined at lower levels, and defines new primitives (e.g, inter-network addressing, process-to-process connections, byte streams) available to levels above it. A program making use of the Pup package need include only those components implementing primitives utilized by that program.
.sec Overview
This document is organized as a general overview followed by descriptions of each of the components of the package, with the lowest levels described first. A history of revisions to the package may be found at the end.
Before beginning the real documentation, we should like to mention a number of points worth bearing in mind throughout, as well as various caveats and suggestions for use.
a. This document concerns itself only with external program interfaces and not with protocol specifications, internal implementation, motivations for design choices, etc. The Pup package implements the protocols described in the memo "Pup Specifications" (Maxc file <Pup>PupSpec.Press) and in other documents also to be found in the <Pup> directory. A higher-level overview of the Pup protocols may be found in the report "Pup: An Internetwork Architecture", file <Pup>PupPaper.press. Users interested in protocol information are referred to those documents. Knowledge of these protocols is not required when writing programs making use of the higher-level primitives provided by the Pup package (specifically, connections and byte streams), but is essential when dealing directly with the lower-level primitives.
b. Since both the software and the protocols are still under active development, users are requested to avoid making changes to the package, if at all possible. This is so that subsequent releases of the package may be incorporated into existing programs with minimum fuss. We have attempted to provide as general-purpose a package as is reasonable (consistent with clean programming practices and considering Alto memory limitations), so if you come up with an application that simply can't be accomodated without modifying the package, we would like to know about it. There are a small number of parameters that we have designated as "user-adjustable" and separated out into a special declaration file (PupParams.decl). The intention is that users be able to change these parameters and recompile the package; however, one should be aware that the software has not been tested with parameters set to values other than the ones in the released version.
c. One of the design goals has been to implement software that will also run on a Nova. All Alto-specific code has been carefully separated out into modules containing "Al" in their names (e.g., PupAlEthb.bcpl for the Alto Ethernet driver). The Nova equivalents of the Alto-specific modules (released as a separate package) contain "Nv" in their names. Source files not containing "Al" or "Nv" in their names may be recompiled on the Nova (with BCPL or the Nova version of Asm) and run without change; either they are completely free of machine dependencies or (in a few cases) they enclose machine-dependent code in conditional compilation. People writing general-purpose subsystems making use of this package are encouraged to adopt the same approach.
d. The Pup package makes extensive use of primitives provided in four other software packages: Context, Interrupt, Queue, and Timer. The dependence on the Context package means that calling programs must operate in a manner compatible with contexts. In particular, the Pup package initiates a number of independent background processes that must be given an opportunity to run fairly frequently. Hence, the user's "main program" must run within a context, and wait loops and very long computations in the main program should be interspersed with calls to Block. For example, a call such as "Gets(keys)" (which causes busy-waiting inside the operating system) might be replaced by something like "GetKeys()", where the latter function is defined as:
.skip 1
.begin group verbatim
let GetKeys() = valof
[
while Endofs(keys) do Block()
resultis Gets(keys)
]
.end
Alternatively, you may change the Operating System's "Idle" procedure to call Block, if you understand what you are doing. Consult the the Context Package writeup for further information.
.ssec Organization
The Pup software is divided into three major levels, corresponding to levels 0 through 2 of the Pup protocol hierarchy. Software at a given level depends on primitives provided at all levels below it.
At level 0 is the "transport mechanism" software necessary for an Alto to send and receive Pups on an Ethernet. This consists of a small Ethernet interrupt handler that appends received Pups to an input queue and transmits Pups taken from an output queue. It is the only portion of the Pup package specific to the Ethernet or to the Alto-Ethernet interface. Corresponding drivers are included for the XEOS EIA interface and the ASD Communication Processor, for use in Altos that have those special interfaces installed.
Level 1 defines a number of important and generally useful primitives. A program desiring to send and receive "raw Pups" (without sequencing, retransmissions, flow control, etc.) would interface to the Pup package at this level. The level 1 module includes the following:
.begin indent 4,4
a. Procedures for creating, maintaining, and destroying a "socket", a process's logical connection to the Pup inter-network.
b. Procedures for managing "Packet Buffer Items" (PBIs), each of which holds a Pup and some associated information while the Pup resides in Alto memory.
c. A background process that distributes received Pups to the correct sockets. This includes checking port address fields and optionally verifying the Pup checksum.
d. Procedures for allocating PBIs, building Pups, and queueing them for transmission.
e. A background process that dynamically maintains a routing table for transmission of Pups to arbitrary inter-network addresses.
f. Optional procedures permitting the local host to be a gateway (not ordinarly used).
.end
At level 2 are modules implementing three higher-level protocols: the Rendezvous/Termination Protocol (RTP), the Byte Stream Protocol (BSP), and the Network Directory Lookup Protocol. These are independent, parallel protocols, each built on top of the primitives defined at level 1; however, the RTP and the BSP interact in a way such that, in this implementation, BSP depends on the existence of RTP.
The RTP module contains procedures for opening and closing a "connection" with a foreign process. These have options permitting the local process to operate in the role of either "initiator" or "listener".
The BSP module contains mechanisms for sending and receiving data by means of error-free, flow-controlled "byte streams" between a local and a foreign process. These are true "streams" in the sense defined by the Alto operating system. Additionally, means are provided for sending and receiving Marks and Interrupts, which are special in-sequence and out-of-sequence signals defined by the Byte Stream Protocol. A separate, optional module permits sending and receiving blocks of data in memory an order of magnitude more efficiently than by use of the basic "Puts" and "Gets" operations.
The Network Directory Lookup module contains procedures for converting between inter-network "names" (e.g., host names) and Pup addresses (ports). When necessary, it finds and interacts with some network directory lookup server on the directly connected network. The Name Lookup module converts only from names to addresses, and may be substituted for Network Directory Lookup when its other facilities are not required.
.ssec File Conventions
The Pup package is distributed as file PupPackage.dm, which contains the following binary files:
.skip 1
.begin nofill group tabs 5,30
Level 0
\PupAlEthb.br\Alto Ethernet driver (BCPL portion)
\PupAlEtha.br\Assembly code for Ethernet driver
\PupAlEthInit.br\Alto Ethernet initialization
\PupAlEIAb.br\Driver for EIA interface
\PupAlEIAa.br
\PupAlEIAInit.br
\PupAlComProcb.br\Driver for Communication Processor
\PupAlComProca.br
\PupAlComProcInit.br
.apart group
Level 1
\Pup1b.br\Main level 1 code (BCPL portion)
\PupAl1a.br\Assembly-language code for level 1
\Pup1OpenClose.br\Opening and closing Pup sockets
\PupRoute.br\Routing table maintenance and access
\PupDummyGate.br\Dummy substitute for gateway code
\Pup1Init.br\Level 1 initialization
.apart group
Level 2
\PupRTP.br\Rendezvous/Termination Protocol
\PupRTPOpenClose.br\Opening and closing RTP sockets
\PupBSPStreams.br\Byte Stream Protocol (BCPL portion)
\PupBSPProt.br\Additional BSP code
\PupBSPOpenClose.br\Opening and closing BSP sockets
\PupBSPa.br\Assembly-language code for BSP
\PupBSPBlock.br\Fast BSP block transfer procedures
\PupNetDirLookup.br\Network directory lookup module
\PupNameLookup.br\Name lookup module (subset of PupNetDirLookup)
.end
The files with "Init" in their names, as well as PupDummyGate.br, contain initialization code that need be executed only once and may then be thrown away. (Note, however, that the level 1 and level 0 "Destroy" procedures are included in the "Init" modules.)
Files PupNetDirLookup, PupNameLookup.br, and the files with "OpenClose" in their names contain code that is infrequently executed (i.e., only when particular types of sockets are opened or closed) and may therefore be loaded into overlays (to be managed by the Overlay package) without significant performance penalties. All other modules must remain resident while any part of the Pup package is active, since they contain main-line code or code that is executed by continually-running contexts.
Additionally, the following "get" files are included. They contain declarations of all structures and other parameters likely to be of interest to calling programs (as well as some others of no interest to callers). We suggest that the user make listings of these files to accompany this documentation.
.skip 1
.begin nofill group tabs 5,30
\Pup0.decl\Level 0 definitions (network-independent)
\Pup1.decl\Level 1 definitions
\PupRTP.decl\Definitions for RTP
\PupBSP.decl\Definitions for BSP
\Pup.decl\Does "get" of all the above
\PupParams.decl\User-adjustable parameters
\PupNetDir.decl\Definitions for PupNetDirLookup
\PupStats.decl\Statistics definitions
\PupAlEth.decl\Definitions specific to Alto Ethernet
\PupAlEIA.decl\Definitions specific to EIA driver
\PupAlComProc.decl\Definitions specific to ComProc driver
.end
A program that does a "get" of any of the first group of files must also "get" all files earlier on the list, and in the same order. (We were not able to make this happen automatically because of a limit on the number of simultaneous open files at compilation time). The file Pup.decl is provided for the convenience of programs dealing with the package at the BSP level. A "get" of PupParams.decl is included in Pup0.decl, and PupAlEth.decl and PupStats.decl are not ordinarily of interest to outside programs.
The following table shows, for each module (including external packages), what .br files constitute that module and what other modules are also required.
.skip 1
.begin nofill tabs 25,45
Module Name\Files\Other Modules Required
BSP Block Transfer\PupBSPBlock.br\BSP
\\ByteBlt
ByteBlt (external)\AltoByteBlt.br
BSP\PupBSPStreams.br\RTP
\PupBSPProt.br
\PupBSPOpenClose.br
\PupBSPa.br
RTP\PupRTP.br\Level 1
\PupRTPOpenClose.br
Net Dir Lookup\PupNetDirLookup.br\Level 1
Name Lookup\PupNameLookup.br\Level 1
Level 1\Pup1b.br\Level 0
\Pup1OpenClose.br\Timer
\PupAl1a.br
\PupRoute.br
\PupDummyGate.br
\Pup1Init.br
Level 0\PupAlEthb.br\Context
\PupAlEtha.br\Interrupt
\PupAlEthInit.br\Queue
Context (external)\Context.br
\ContextInit.br
Interrupt (external)\Interrupt.br
\InterruptInit.br
Queue (external)\AltoQueue.br
Timer (external)\AltoTimer.br
.end
There are a few global parameters that may be changed by modifying the PupParams.decl file and then recompiling the entire Pup package. The most interesting parameter is "pupDebug", which, if true (default is false) causes some additional consistency checking code to be compiled.
The sources for the Pup package are contained in file PupSources.dm, and consist of the following files:
.skip 1
.begin nofill group indent 4 tabs 25,45
PupAlEthb.bcpl\PupAlEtha.asm\PupAlEthInit.bcpl
PupAlEIAb.bcpl\PupAlEIAa.asm\PupAlEIAInit.bcpl
PupAlComProcb.bcpl\PupAlComProca.asm\PupAlComProcInit.bcpl
Pup1b.bcpl\PupAl1a.asm\Pup1OpenClose.bcpl
PupRoute.decl\PupRoute.bcpl
Pup1Init.bcpl\PupDummyGate.bcpl
PupRTPInternal.decl\PupRTP.bcpl\PupRTPOpenClose.bcpl
PupBSPStreams.bcpl\PupBSPProt.bcpl\PupBSPa.asm
PupBSPOpenClose.bcpl\PupBSPBlock.bcpl
PupNameLookup.bcpl
.end
Additionally, there are several command files:
.skip 1
.begin nofill group indent 4 tabs 30
CompilePup.cm\Compiles all the source files
DumpPupPackage.cm\Creates PupPackage.dm
DumpPupSources.cm\Creates PupSources.dm
Pup.cm\A list of all the source files
.end
The source files are formatted for printing in a small fixed-pitch font such as Gacha8 (the normal default for Empress).
.ssec Glossary of Data Types
.begin indent 0,24 tabs 10,25
Name\Defined in\Meaning
BSPSoc\PupBSP.decl\BSP-level Pup socket, consisting of an RTP socket (RTPSoc) followed by additional information about a byte stream. This includes byte IDs (sequence numbers), queues, and allocations for incoming and outgoing data and interrupts, and a BSP stream block (BSPStr).
BSPStr\PupBSP.decl\BSP stream (part of a BSPSoc), for interfacing the BSPSoc to the Alto operating system's stream mechanism.
HTP\Pup1.decl\Hash Table Preamble, defining the publicly-accessible operations on a dictionary object (specifically, the Pup routing table). These operations are Lookup, Insert, Delete, and Enumerate. This object is misnamed in that it need not actually be implemented by means of a hash table; at present, the Pup routing table is not.
NDB\Pup0.decl\Network Data Block, containing information specific to each network physically attached to the local host. (A standard Alto has only one of these, for the directly-connected Ethernet.)
PBI\Pup0.decl\Packet Buffer Item, which holds a Pup and various associated information.
PF\Pup0.decl\Packet Filter, controlling acceptance of incoming packets on a given network.
Port\Pup0.decl\An inter-network address, consisting of network, host, and socket numbers, as defined by protocol.
PSIB\Pup1.decl\Pup Socket Info Block, contains data used for setting initial default values when a PupSoc is created.
Pup\Pup0.decl\An inter-network packet, as defined by protocol.
PupSoc\Pup1.decl\Level 1 Pup socket, defining a process's logical connection to the inter-network. It contains default local and foreign port addresses, PBI allocation information, and an input queue header.
RT\--\Routing Table, containing information necessary to route outgoing Pups to destination hosts or to gateways. There is only one instance of an RT, called pupRT. The structure of an RT is not public, but object procedures (see HTP) are provided for accessing and enumerating individual Routing Table Entries (RTEs), which are public structures.
RTE\Pup1.decl\Routing Table Entry (routing information for one network).
RTPSoc\PupRTP.decl\RTP-level Pup socket, consisting of a level 1 socket (PupSoc) followed by additional information about a connection. This includes state, connection ID, timers, and a higher-level Pup-handling procedure.
soc\--\An instance of a PupSoc, RTPSoc, or BSPSoc, depending on context. Note that a PupSoc may be the initial portion of an RTPSoc, which may in turn be the initial portion of a BSPSoc; hence, a given soc may be an instance of more than one of these structures.
str\--\An instance of a stream (most likely, a BSPStr).
.end
.sec Level 0 Interface
Only the level 0 driver for the Ethernet is described here. There also exist drivers for the EIA and ComProc interfaces, but they are somewhat specialized and are not documented here. Their function is analogous to the Ethernet driver and their operation is quite similar.
The level 0 module (files PupAlEthb, PupAlEtha, and PupAlEthInit) serves only to interface the Alto Ethernet to the network-independent Pup level 1 module. Assuming the level 1 code is being used, as is normally the case, external programs will generally have no occasion to deal directly with the level 0 module. Provisions are also made for sending and receiving non-Pup Ethernet packets, for use in unusual applications.
This module requires the existence of the following external statics (all of which are defined in level 1):
.begin indent 4,14 tabs 15
ndbQ\A pointer to a two-word queue header (hereafter referred to as "a queue"; see Queue Package documentation) upon which the Ethernet NDB (etherNDB) may be queued by this module. In a machine with more than one network interface, this queue contains an NDB for each network.
pbiFreeQ\A queue from which free PBIs may be obtained, for buffering received Pups.
pbiIQ\A queue to which PBIs are appended when Pups are received.
lenPup\The maximum length of a Pup (in words).
.end
The externally-callable procedures in this module are the following:
.begin indent 4,4
.once indent 0
InitAltoEther(zone, ctxQ, device)
.continue
Initializes the Alto Ethernet interface and associated data structures. "zone" is a free-storage zone from which space may be obtained for permanent data structures (currently less than 100 words). "ctxQ" is a queue on which a context created by this procedure may be queued. This procedure allocates an NDB and appends it to ndbQ; allocates an interrupt context (see Interrupt Package documentation) and sets it up to field Ethernet interrupts; and allocates and initiates an ordinary context (see Context Package documentation) which runs forever and whose job it is to restart the Ethernet interface if it is ever shut off due to running out of free PBIs for input. InitAltoEther returns having done nothing if the Alto doesn't have an Ethernet interface installed (the level 1 initialization detects the condition of ndbQ being empty after all interface initialization procedures have been called).
"device" should normally be 0, referring to the standard Alto Ethernet interface. However, in Altos with more than one Ethernet interface installed, the driver may be initialized multiple times, once for each interface; in this case, device numbers 1 and 2 refer to the first and second additional interfaces.
.once indent 0
EncapsulateEtherPup(pbi, pdh)
.continue
Encapsulates the Pup contained in "pbi" for transmission to physical destination host "pdh" on the directly-connected Ethernet. The PBI should contain a completely well-formed Pup. EncapsulateEtherPup sets the Ethernet destination, source, and type fields in the encapsulation portion of the packet, and also sets the packetLength word in the PBI. SendEtherPup is the procedure called from level 1 via the encapsulatePup entry in the Ethernet NDB.
.once indent 0
SendEtherPacket(pbi)
.continue
Queues "pbi" for transmission on the directly-connected Ethernet, and initiates transmission if the interface is idle. The PBI should contain a completely well-formed Ethernet packet (which need not be a Pup), the packetLength word in the PBI must contain the physical length of the packet in words, pbi>>PBI.queue must contain a pointer to a queue to which the PBI will be appended after it has been transmitted, and pbi>>PBI.ndb must contain a pointer to the NDB associated with the Ethernet interface through which the packet is to be sent. SendEtherPacket is the procedure called from level 1 via the level0Transmit entry in the Ethernet NDB.
.once indent 0
SendEtherStats(pbi, ndb) = true or false
.continue
If the debugging version of PupAlEthb is loaded (pupDebug on), this procedure copies the statistics accumulated by the Ethernet interface (described by ndb) into pbi and returns true. If the module was not compiled with debugging on, SendEtherStats immediately returns false.
.once indent 0
DestroyAltoEther(ndb)
.continue
Turns off the Ethernet interface designated by ndb, and releases all storage allocated by InitAltoEther. This is the procedure called from level 1 via the NDB.destroy procedure. This procedure is in the PupAlEthInit module, which must therefore be retained if the "destroy" operation is actually to be utilized.
.end
When a packet is received from the Ethernet, the input interrupt routine first verifies that the hardware and microcode status are correct, and discards the packet without error indication if not. It then tests the packet for acceptance by each Packet Filter (PF) on the Ethernet packet filter queue, as will be described shortly. If some PF accepts the packet, the PBI is then enqueued on the queue designated in the PF; otherwise it is discarded. A free PBI is then obtained from pbiFreeQ, and the receiver is restarted. (Actually, an attempt is made to restart the receiver before any other processing so as to minimize the interval during which a packet could be missed because the receiver isn't listening to the Ethernet.)
When an output PBI is passed to SendEtherPacket, it is queued on a local Ethernet output queue (eOQ, part of the NDB). If the interface is currently idle, transmission is initiated immediately; otherwise, the PBI is simply left on the queue for action by the interrupt routine. When an output completion interrupt occurs (or a fatal error indication such as a "load overflow", or a 100 millisecond software timeout), the PBI is then enqueued on the queue specified in the PBI (typically pbiFreeQ or a level 1 queue called pbiTQ).
Garden-variety errors (e.g., collisions, bad Ethernet CRCs, etc.) are handled automatically: input errors cause the received packet simply to be discarded, while output errors cause retransmission. "Impossible" errors (suggesting that the interface or the Alto is broken) result in a call to SysErr(@ePLoc, ecBadEtherStatus).
In the debugging version of this module (pupDebug on), a number of Ethernet performance statistics are gathered. These are intended for experimental purposes and measurements. One should consult PupStats.decl to see what is collected.
Though the primary purpose of the Pup level 0 module is to send and receive Pups on a particular directly-connected network, means are also provided for sending and receiving arbitrary network-dependent packets (i.e., Ethernet packets in an Alto).
Sending a non-Pup packet is straightforward: one simply calls SendEtherPacket after constructing the desired Ethernet packet in the PBI, as described above.
Discrimination among received packets is accomplished by one or more objects called Packet Filters (PFs), which reside on a Packet Filter Queue (pfQ) whose head is in the NDB. Each PF contains a predicate and a pointer to a queue. When a packet is received, the predicate in each PF in turn is called with the PBI as an argument. If the predicate returns true, the PBI is enqueued on the queue pointed to by the PF; if it returns false, the next PF is tried. If no PF accepts the packet, the PBI is discarded.
The pfQ initially contains a single PF that accepts Pups and appends them to pbiIQ (the level 1 Pup input queue). A program desiring to receive other kinds of Ethernet packets should construct its own PF and enqueue it on the Ethernet pfQ.
.sec Level 1 Interface
The level 1 module (files Pup1b, PupAl1a, PupRoute, Pup1OpenClose, PupDummyGate, and Pup1Init) contains the mechanisms enabling a process to send and receive individual Pups to and from other processes at arbitrary inter-network addresses. Concepts such as "connection" and "stream", however, are not defined at this level, so it is the process's responsibility to perform initial connection, sequencing, retransmission, duplicate detection, etc., where required.
A process deals with the level 1 module through a PupSoc, a level 1 socket structure (see Pup1.decl), which completely describes that process's interface to the inter-network at the first level of protocol. The information in the socket is as follows:
.begin indent 4,19 tabs 20
iQ\Input queue. PBIs received for the socket are appended to this queue. The two-word queue header is included in the socket structure itself, so to remove a packet from the iQ one would write "Dequeue(lv soc>>PupSoc.iQ)".
lclPort\Local port address (a Port structure). This serves two purposes. First, the "socket number" in the port enables the level 1 Pup input handler to distribute each incoming Pup to the correct PupSoc by comparing pbi>>PBI.pup.dPort.socket (the Pup destination socket number) with soc>>PupSoc.lclPort.socket of each active PupSoc until a match is found. Second, the source port fields of each outgoing Pup generated by the process are defaulted (if zero) to the values given in the local port address.
frnPort\Foreign port address (a Port structure). This provides information for defaulting the destination port fields of outgoing Pups, in the same manner as described for lclPort.
psib\Pup Socket Info Block (PSIB), which contains the information described below. Since it is generally the same for all sockets, there is a "default PSIB" (dPSIB) whose contents are copied into the psib for each socket when the socket is created.
maxTPBI\The maximum total number of PBIs that may be assigned to the socket. Since free PBIs are taken from a common pool, some means is required for ensuring that no single socket can usurp more than a certain share of the total available PBIs (which, aside from reducing performance for other sockets, could lead to deadlocks in higher-level protocols if the free pool became exhausted). This is discussed further in the descriptions of the GetPBI and ReleasePBI procedures.
numTPBI\The total number of additional PBIs that may be assigned to the socket (i.e., maxTPBI minus the number of PBIs already assigned).
maxIPBI\The maximum number of PBIs that may be assigned to the socket for input use.
numIPBI\The number of additional PBIs that may be assigned for input (i.e., maxIPBI minus the number of PBIs already assigned for input).
maxOPBI\The maximum number of PBIs that may be assigned to the socket for output use.
numOPBI\The number of additional PBIs that may be assigned for output (i.e., maxOPBI minus the number of PBIs already assigned for output).
doChecksum\If true, the Pup software checksum is checked by the level 1 software in incoming Pups (before being given to the process) and generated in outgoing Pups. The default value is true.
.end
The following statics are defined within the level 1 module and may be referenced externally (though only a few are likely to be of interest):
.begin indent 4,14 tabs 15
dPSIB\Pointer to default socket info block, used to provide initial values in part of each PupSoc when it is created.
gatewayIQ\Pointer to queue on which received Pups not addressed to this host are placed. Unless the Gateway package is loaded, gatewayIQ is initialized to pbiFreeQ.
lenPup\The length of the largest possible Pup, in words (derived from maxPupDataBytes).
lenPBI\The length of a PBI, in words (derived from lenPup). Note that all PBIs are of the same size and can each contain a Pup of maximum length.
lPupSoc\The length of a PupSoc, in words.
maxPupDataBytes The maximum number of data (content) bytes in a Pup. This is initialized to the "pupDataBytes" argument to InitPupLevel1 and remains constant thereafter.
ndbQ\Pointer to queue of NDBs for all the physically connected networks (see level 0 description). The first NDB on ndbQ is considered to be the "default" network, i.e., the one sent to if a process specifies a Pup destination network of zero.
numNets\The number of directly connected networks (always 1 in an Alto).
pbiFreeQ\Pointer to queue of free PBIs.
pbiIQ\Pointer to queue on which incoming Pups are placed by level 0 interrupt routines.
pbiTQ\Pointer to queue on which outgoing Pups are ordinarily placed after transmission.
pupCtxQ\Default context queue onto which new contexts created by the Pup package will be appended. This is initialized to the "ctxQ" argument to InitPupLevel1.
pupRT\Pointer to routing table (described later).
pupZone\Default zone from which allocations will be made by the Pup package. This is initialized to the "zone" argument to InitPupLevel1.
socketQ\Pointer to queue of all active PupSocs.
.end
The level 1 module must be initialized by calling InitPupLevel1, as follows:
.begin indent 4,4
.once indent 0
InitPupLevel1(zone, ctxQ, numPBI, pupDataBytes [defaultPupDataBytes], numRTE [9])
.continue
Initializes all the level 1 software, and also calls the appropriate level 0 initialization (InitAltoEther in the Alto version). "zone" is a free-storage zone from which permanent allocations may be done. "ctxQ" is a pointer to a queue of contexts to which the contexts created by this procedure may be appended. "numPBI" is the number of PBIs to be allocated (from "zone") and appended to the pbiFreeQ.
The optional argument "pupDataBytes" specifies the maximum number of data (content) bytes to be permitted in any Pup; it must be even and by convention should not be greater than 532. A smaller maximum Pup length is useful in some applications not requiring high throughput, since the PBIs are thereby smaller and one can have more of them at the same cost in memory. The default value of this parameter is 532.
The optional argument "numRTE" specifies the number of entries to allocate in the Pup routing table. These are used as a cache for routing information, and there should be at least as many entries as there are likely to be simultaneous conversations with hosts on different networks.
InitPupLevel1 does the following: it creates the queues pbiIQ, pbiTQ, pbiFreeQ, socketQ, and ndbQ; allocates "numPBI" PBIs and appends them to pbiFreeQ; creates the routing table pupRT; creates the default Pup socket info block dPSIB; calls the level 0 initialization procedure(s); creates the PupLevel1 and GatewayListener background contexts (to be described later); and broadcasts requests for gateway routing information. The total amount of storage taken from "zone" (in words) is approximately numPBI*290 + lenPSIB + lenPupSoc + numRTE*5 + 250 + the amount needed by level 0 initialization. InitPupLevel1 also calls the external procedure InitForwarder (ordinarily defined in PupDummyGate.br), initializes the static pupZone to "zone" and pupCtxQ to "ctxQ", and sets up the constants maxPupDataBytes, lenPup, and lenPBI on the basis of "pupDataBytes".
InitPupLevel1 does not call Block, so it is permissible to call it from initialization code that is not running as a context.
.once indent 0
DestroyPupLevel1()
.continue
Undoes the actions of InitPupLevel1. This includes calling all the level 0 "destroy" procedures (via the NDB.destroy operations in all NDBs on ndbQ) and releasing all storage allocated from pupZone. DestroyPupLevel1 is in the Pup1Init module, which must therefore be retained rather than discarded if this procedure is to be used.
.end
The following procedures are provided for creating and destroying sockets:
.begin indent 4,4
.once indent 0
OpenLevel1Socket(soc, lclPort [defaulted], frnPort [zeroes], transient [false])
.continue
Creates a PupSoc. "soc" should point to a block of size lenPupSoc. "lclPort", if specified and nonzero, points to a Port structure describing the desired local port address. "frnPort", if specified and nonzero, points to a Port structure describing the desired foreign port address. The "soc" is then appended to socketQ, thereby enabling reception of Pups directed to it.
Each field in the local port address is subject to defaulting if either the "lclPort" is unspecified or the field is zero, in the following manner. If the socket number is unspecified, one is chosen at random (it is guaranteed unique). If both the network and host numbers are unspecified, they are filled in with a reasonable local host address (perhaps based on the supplied "frnPort"). Ordinarily, one should allow the socket number to be defaulted unless one intends the process to reside at a "well-known socket" (as in a server), and one should always allow the network and host numbers to be defaulted.
If "frnPort" is unspecified, the foreign port in the "soc" is set to zeroes. Then, if the foreign network number is zero (generally for the purpose of designating the "directly connected" network), it is set to the connected network's actual number, if known. Note that the "lclPort" and "frnPort" fields in the "soc" are copied from the corresponding arguments to OpenLevel1Socket; the argument ports are not modified and are not needed thereafter.
If "transient" is true, the caller asserts that the socket's lifetime will be very short. This modifies the disposition of incoming Pups that arrive after the socket has been closed: ordinarily such Pups are answered with Error pups (saying that no such socket exists), but if the socket was transient they are simply ignored. This eliminates needless extra traffic in the case that the caller broadcasts a request through the socket, accepts the first reply, and immediately closes the socket. The "transient" feature works only if the local socket number is defaulted.
.once indent 0
CloseLevel1Socket(soc)
.continue
Causes "soc" to be removed from socketQ. This procedure blocks until all PBIs assigned to the socket have been recovered and released. If "soc" is not in fact on socketQ, this procedure calls SysErr(soc, ecNoSuchSocket).
.end
Control over assignment of PBIs to sockets is accomplished in a manner that is more complicated to describe than to implement. Associated with each socket are three numbers that determine the maximum number of PBIs that may be assigned to a socket simultaneously. The "total" (soc>>PupSoc.maxTPBI) is the maximum total number of PBIs permitted, while the "input" and "output" values (soc>>PupSoc.maxIPBI. soc>>PupSoc.maxOPBI) determine (independent of the overall total) the maximum number of PBIs that may be assigned for those respective purposes. The "total" maximum prevents a single socket from usurping more than a fixed share of the total PBIs in the system; within that, the "input" and "output" limits, if properly set, prevent all of a socket's allocation from being devoted to packets going in one direction (with resultant potential deadlocks). The "total" allocation must be greater than either "input" or "output", but need not be equal to their sum, since in most applications one expects heavy demands on PBIs in only a single direction.
The actual number of PBIs assigned to a socket at a given moment is reflected in three other cells in the socket: soc>>PupSoc.numTPBI, soc>>PupSoc.numIPBI, and soc>>PupSoc.numOPBI. These are initialized to the corresponding "max" values, decremented whenever a PBI is assigned to the socket, and incremented when the PBI is released. The code responsible for allocating and releasing PBIs (the PupLevel1 background process for input PBIs and the GetPBI procedure for output PBIs) do not permit any of these counts to go below zero; if allocating another PBI would cause a count to be decremented below zero, PupLevel1 will simply discard the Pup and release the PBI, and GetPBI will either block or fail (see below).
The allocations in the socket are also useful when destroying the socket. At the time CloseLevel1Socket is called, there may be PBIs that are assigned to the socket but that cannot be located at the moment because they reside on some other queue (such as the Ethernet output queue or the pbiTQ). CloseLevel1Socket simply blocks until soc>>PupSoc.numTPBI equals soc>>PupSoc.maxTPBI, at which point it is known that all PBIs have "returned" to the socket and been released.
PBIs may be added to the free pool simply by allocating blocks of size lenPBI and "Enqueue"ing them on pbiFreeQ. One could also remove PBIs from the system by "Dequeue"ing them from pbiFreeQ and freeing them, but of course one has no control over which PBIs are available for release. Note that such changes in the total number of PBIs are not automatically reflected in any socket allocations or in the default allocations contained in dPSIB.
.begin indent 4,4
.once indent 0
SetAllocation(soc, total, input, output)
.continue
Changes the number of PBIs that may be assigned to the socket. "total", "input", and "output" are the new maximum values. The "total" must be greater than either the "input" or "output". SetAllocation need be called only if the desired allocations differ from the defaults in dPSIB. Alternatively, one may manually change the contents of dPSIB; note that the "num" and "max" values for a given allocation must be the same and that the "total" allocation must be greater than or equal to the "input" and "output" allocations. Changing dPSIB does not affect allocations in sockets that have already been opened. The initial "total" allocation in dPSIB is numPBI-numNets, where numPBI is the argument to InitPupLevel1 that determines the number of PBIs initially created and numNets is the number of directly-connected networks (normally one in an Alto). The initial "input" and "output" allocations are each one less than the "total".
.once indent 0
GetPBI(soc, returnOnFail [false]) = PBI
.continue
Assigns a PBI from pbiFreeQ and charges it to the socket, for output use (that is, it decrements soc>>PupSoc.numTPBI (total) and soc>>PupSoc.numOPBI (output)). If the socket has exhausted its total or output allocation or the pbiFreeQ is empty, then GetPBI blocks unless returnOnFail is true, in which case it returns zero. The PBI returned has its Pup header zeroed so that if the caller later transmits the Pup without setting up source and destination port addresses, the addresses will be correctly defaulted from the socket. The PBI's "queue" pointer is set to pbiTQ, resulting in automatic release of the PBI after it is transmitted. The PBI's "socket" pointer is set to "soc", thereby recording the socket to which it has been assigned.
.once indent 0
ReleasePBI(pbi)
.continue
Releases the "pbi" and appropriately credits the allocations in the socket to which it was assigned.
.once indent 0
CompletePup(pbi, type [], length [])
.continue
Causes "pbi" to be completed and transmitted. "Completion" consists of the following operations: "type" and "length", if supplied, are stored in the Pup type and length fields; any zero fields in the Pup source or destination ports are defaulted to the values given in the owning socket's local and foreign port addresses, respectively; the transport control byte (used by gateways) is zeroed; then, if the socket's doChecksum flag is on (the default unless changed explicitly), a software Pup checksum is computed and stored in the Pup. The caller is expected to have set up the Pup's ID, and contents (if any) and its type and length if not supplied in the call. Finally, the PBI is routed to its destination and queued for transmission.
After transmission, the PBI is appended to pbi>>PBI.queue, which (unless changed explicitly by the caller) will be pbiTQ, resulting in automatic release of the PBI. If a different queue is specified for disposal of the PBI (as is done in the BSP package, for example), then the caller is responsible for keeping track of the PBI, and, in particular, for ensuring that all PBIs assigned to the socket have been released before destroying the socket.
A special mechanism exists for broadcasting a Pup on all directly-connected networks. If the allNets bit is set in the PBI status word, then instead of routing the Pup to the destination stated in the Pup header, CompletePup sends the Pup out on each directly-connected network. For each network, the local host address on that network is substituted for the network and host numbers in the Pup source port, and the local network number is also substituted for the destination network field (the checksum is recomputed each time this is done). The "queue" word in the PBI must be pbiTQ (the default) for this feature to work properly.
The allNets mechanism ordinarily causes a Pup to be sent on each directly-connected network, whether or not the network's identity is known. However, if the bypassZeroNet bit is also set, the Pup will not be sent on networks whose identity is not known.
.end
Distribution of received Pups to the correct sockets is the responsibility of a background process called PupLevel1. When a PBI appears on pbiIQ (where it was left by the level 0 input handler), PupLevel1 first performs some checks on the Pup destination address, and discards the PBI if it is not destined for a process in the local host (actually, it enqueues it on gatewayIQ, which, assuming the PupDummyGate module has been loaded, is the same as pbiFreeQ). It then searches the socketQ for a socket whose local socket number matches the Pup destination socket number. If no such socket is found, the PBI is passed to SocketNotFound(pbi), which generates an Error Pup and discards the packet (but could be made to do something else by clobbering the SocketNotFound procedure static with a different handling procedure).
Assuming the destination socket is found, PupLevel1 then checks the Pup checksum (assuming the socket's doChecksum flag is on), discarding the PBI if it is incorrect. Finally, the socket's "total" and "input" PBI allocations are checked. If either is exhausted, the PBI is discarded (causing an Error Pup to be returned to the Pup's source); otherwise, the allocations are updated and the PBI is appended to the socket's iQ.
PupLevel1 is also responsible for releasing PBIs on the pbiTQ, which is the default queue to which outgoing packets are appended after transmission.
Another process, GatewayListener, is responsible for dynamically maintaining the routing table pupRT and updating it with information periodically received from gateways. While routing and routing table maintenance are operations performed automatically (by CompletePup and GatewayListener), the format of the routing table is of possible interest to callers in certain cases--for example, in deciding which of several possible remote servers is the best choice in terms of network topology (see the PupNameLookup module for an example of this). The following description is much more than most programmers will wish to know about.
The RT is a dictionary object consisting of routing table entries (RTEs) keyed by network number, each containing information about a specific network. For a given RTE, if the "hops" field is zero, the network is one to which the local host is directly connected; otherwise, the network may be reached via the gateway whose host number is given in the "host" field (the "hops" field indicates the number of gateways believed to lie along the route to the destination net). In either case, the "ndb" field points to the NDB for the immediate destination network (see "Pup Specifications"). If the "hops" field is greater than "maxHops" (currently 15), the network is known to be inaccessible, and the remainder of the RTE should not be believed.
If no RTE exists for a particular network, then we know nothing about that network and can't route Pups to it. The routing table is treated as a cache of recently-used routing information. When an attempt is made to transmit a Pup to a network not represented in the routing table, new routing information is obtained from a nearby gateway and an RTE for that network is inserted into the routing table (possibly displacing some other RTE that has not been used recently). Note, however, that RTEs for directly-connected networks are never removed from the routing table.
Network number zero in the routing table is special. It refers to a network known to be directly connected to the local host (but whose identity may or may not be known, i.e., we may or may not know its network number). Pups handed to CompletePup for transmission to network zero will be sent over this network. This facility is essential during initialization, before any gateways have been located and the remainder of the RT filled out. It also permits communication among hosts on a network whose identity is unknown due to there being no connected gateways.
The routing table as a whole is treated as an "object", with standard operations defined by a Hash Table Preamble (HTP). This object is misnamed, since it need not be implemented by means of a hash table, and is not in the present implementation of the Pup routing table. The procedures described below are merely renamed versions of the Alto OS's Call0, Call1, etc. The operations return pointers to RTEs, and the caller may operate on the individual RTE by means of ordinary structure references. The defined operations are:
.begin indent 4,4
.once indent 0
HLookup(rt, net, dontPromote [...false]) = RTE or 0
.continue
Looks up "net" in the routing table "rt", returning a pointer to the RTE if it is found and zero if not. Unless "dontPromote" is supplied and true, the RTE is marked as having been referenced most recently.
.once indent 0
HInsert(rt, net) = RTE
.continue
Inserts an RTE for "net" into "rt", setting the "net" field of the RTE and zeroing the rest of the entry. If an entry already exists for "net", it is overwritten. If no entry already exists, a new one is created, possibly displacing the least recently referenced RTE.
.once indent 0
HDelete(rt, net)
.continue
Deletes the RTE for "net" in "rt", if one exists.
.once indent 0
HEnumerate(rt, proc, arg)
.continue
Enumerates all RTEs in "rt", calling proc(rte, arg) for each one.
.end
The following miscellaneous procedures are of possible interest to callers:
.begin indent 4,4
.once indent 0
LocateNet(net) = rte or 0
.continue
Attempts to locate a route to "net". If an RTE for "net" exists and is valid (i.e., hops not greater than maxHops), a pointer to it is returned. Otherwise, activity is initiated to locate a route to "net" and zero is returned.
.once indent 0
PupError(pbi, errorType, string)
.continue
Causes an "Error" Pup to be returned to the sender of "pbi", containing the specified "errorType" and "string". The PBI is released in the process. Consult the "Pup Error Protocol" specification for more information. PupError is called from several places inside PupLevel1 when incoming Pups are rejected for one reason or another.
.once indent 0
ExchangePorts(pbi)
.continue
Exchanges the Pup source and destination ports in "pbi". Useful when sending a packet back where it came from (possibly after modifying its contents).
.once indent 0
AppendStringToPup(pbi, firstByte, string)
.continue
Appends the supplied "string" to the Pup in "pbi", starting at byte position pbi>>PBI.pup.bytes↑firstByte, then sets the Pup length to include the data so stored. Useful for generating Pups that end in (or consist entirely of) a string, such as Error, Abort, and Interrupt Pups.
.once indent 0
SetPupDPort(pbi, port)
.continue
Copies the specified "port" into the Pup destination port field of "pbi".
.once indent 0
SetPupSPort(pbi, port)
.continue
Copies the specified "port" into the Pup source port field of "pbi".
.once indent 0
SetPupID(pbi, pupID)
.continue
Copies the two words pointed to by "pupID" into the Pup ID field of "pbi".
.once indent 0
FlushQueue(queue)
.continue
Dequeues and releases all PBIs presently on "queue".
.once indent 0
OnesComplementAdd(a, b)
.continue
Returns the ones-complement sum of "a" and "b".
.once indent 0
OnesComplementSubtract(a, b)
.continue
Returns the ones-complement difference between "a" and "b".
.once indent 0
LeftCycle(word, count) = result
.continue
Returns the result of left-cycling "word" by "count" mod 16 bits.
.once indent 0
MultEq(adr1, adr2, nWords [...2]) = true or false
.continue
Compares the nWords words starting at adr1 with the corresponding words starting at adr2, returning true iff they all match.
.once indent 0
Max(a, b); Min(a, b)
.continue
Return the arithmetic maximum or minimum, respectively, of "a" and "b". These are treated as signed integers and must differ by less than 2↑15.
.once indent 0
DoubleIncrement(adr, offset)
.continue
Adds the signed 16-bit integer "offset" to the 32-bit number pointed to by "adr". Note that a negative "offset" will cause the 32-bit number to be decremented.
.once indent 0
DoubleDifference(adr1, adr2) = value
.continue
Returns as a 16-bit signed integer the result of subtracting the 32-bit number pointed to by "adr2" from the one pointed to by "adr1". If the two numbers differ by more than 2↑15, the result is either 2↑15-1 or -2↑15, depending on the sign of the 32-bit difference.
.once indent 0
DoubleSubtract(adr1, adr2)
.continue
Subtracts the 32-bit number pointed to by "adr2" from the one pointed to by "adr1", and leaves the result in "adr1".
.end
.require "pupmore.pub" source!file