Pup Package

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.

1. 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
PupSpec.Press)  and in  other documents  also to  be found  in the
 directory.  A higher-level  overview of the Pup protocols  may be
found  in  the   report  "Pup:  An  Internetwork   Architecture",  file
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.

                   Copyright Xerox Corporation 1981

Pup Package                November 21, 1981                          2

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:

        let GetKeys() = valof
           while Endofs(keys) do Block()
           resultis Gets(keys)

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.

1.1. 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:

    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

Pup Package                November 21, 1981                          3

    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).

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

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.

1.2. File Conventions

The Pup  package is distributed  as file PupPackage.dm,  which contains
the following binary files:

Pup Package                November 21, 1981                          4

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
    PupAlComProcb.br         Driver for Communication Processor

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

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 PupNetDirLoo

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.

Pup Package                November 21, 1981                          5

    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

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.

Module Name             Files               Other Modules Required

BSP Block Transfer      PupBSPBlock.br      BSP

ByteBlt (external)      AltoByteBlt.br

BSP                     PupBSPStreams.br    RTP

RTP                     PupRTP.br           Level 1

Net Dir Lookup          PupNetDirLookup.br  Level 1
Name Lookup             PupNameLookup.br    Level 1

Level 1                 Pup1b.br            Level 0
                        Pup1OpenClose.br    Timer

Level 0                 PupAlEthb.br        Context
                        PupAlEtha.br        Interrupt
                        PupAlEthInit.br     Queue

Context (external)      Context.br

Interrupt (external)    Interrupt.br

Pup Package                November 21, 1981                          6

Queue (external)        AltoQueue.br

Timer (external)        AltoTimer.br

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:

    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

Additionally, there are several command files:

    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

The source files are formatted for printing in a small fixed-pitch font
such as Gacha8 (the normal default for Empress).

1.3. Glossary of Data Types

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

Pup Package                November 21, 1981                          7

                        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

Pup      Pup0.decl      An   inter-network   packet,   as   defined  by

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

Pup Package                November 21, 1981                          8

2. 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

This module  requires the existence  of the following  external statics
(all of which are defined in level 1):

    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

    lenPup    The maximum length of a Pup (in words).

The externally-callable procedures in this module are the following:

InitAltoEther(zone, ctxQ, device)
    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

    "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.

EncapsulateEtherPup(pbi, pdh)

Pup Package                November 21, 1981                          9

    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

    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.

SendEtherStats(pbi, ndb) = true or false
    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.

    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.

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"

Pup Package                November 21, 1981                         10

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.

3. 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:

    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

Pup Package                November 21, 1981                         11

                   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.

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):

    dPSIB     Pointer  to default  socket info  block, used  to provide
              initial values in part of each PupSoc when it is created.

Pup Package                November 21, 1981                         12

    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

    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.

The level  1 module  must be initialized  by calling  InitPupLevel1, as

InitPupLevel1(zone,  ctxQ, numPBI,  pupDataBytes [defaultPupDataBytes],
    numRTE [9])
    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.

Pup Package                November 21, 1981                         13

    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.

    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.

The  following  procedures  are provided  for  creating  and destroying

OpenLevel1Socket(soc, lclPort [defaulted], frnPort  [zeroes], transient
    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

Pup Package                November 21, 1981                         14

    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

    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).

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

Pup Package                November 21, 1981                         15

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.

SetAllocation(soc, total, input, output)
    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".

GetPBI(soc, returnOnFail [false]) = PBI
    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.

    Releases the "pbi" and appropriately credits the allocations in the
    socket to which it was assigned.

CompletePup(pbi, type [], length [])
    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

Pup Package                November 21, 1981                         16

    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.

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

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

Pup Package                November 21, 1981                         17

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:

HLookup(rt, net, dontPromote [...false]) = RTE or 0
    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

HInsert(rt, net) = RTE
    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

HDelete(rt, net)

Pup Package                November 21, 1981                         18

    Deletes the RTE for "net" in "rt", if one exists.

HEnumerate(rt, proc, arg)
    Enumerates all RTEs in "rt", calling proc(rte, arg) for each one.

The  following miscellaneous  procedures  are of  possible  interest to

LocateNet(net) = rte or 0
    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.

PupError(pbi, errorType, string)
    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.

    Exchanges the  Pup source and  destination ports in  "pbi".  Useful
    when  sending a  packet  back where  it came  from  (possibly after
    modifying its contents).

AppendStringToPup(pbi, firstByte, string)
    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.

SetPupDPort(pbi, port)
    Copies the specified "port" into the Pup destination port  field of

SetPupSPort(pbi, port)
    Copies  the specified  "port"  into the  Pup source  port  field of

SetPupID(pbi, pupID)
    Copies the two words pointed to by "pupID" into the Pup ID field of

    Dequeues and releases all PBIs presently on "queue".

OnesComplementAdd(a, b)
    Returns the ones-complement sum of "a" and "b".

OnesComplementSubtract(a, b)
    Returns the ones-complement difference between "a" and "b".

LeftCycle(word, count) = result
    Returns the result of left-cycling "word" by "count" mod 16 bits.

MultEq(adr1, adr2, nWords [...2]) = true or false

Pup Package                November 21, 1981                         19

    Compares the nWords words  starting at adr1 with  the corresponding
    words starting at adr2, returning true iff they all match.

Max(a, b); Min(a, b)
    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.

DoubleIncrement(adr, offset)
    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.

DoubleDifference(adr1, adr2) = value
    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

DoubleSubtract(adr1, adr2)
    Subtracts  the 32-bit  number  pointed to  by "adr2"  from  the one
    pointed to by "adr1", and leaves the result in "adr1".

4. Rendezvous/Termination Protocol Interface

The RTP module (file  PupRTP) contains primitives for  establishing and
breaking   connections  with   foreign  processes   according   to  the
Rendezvous/Termination Protocol.

The local end of a  connection is maintained within the confines  of an
RTPSoc, an RTP socket structure (defined in PupRTP.decl).   This begins
with  a  level  1  Pup  socket  (PupSoc),  but  includes  the following
additional information:

    ctx                 A pointer to the background context maintaining
                        the connection.

    state               The state of the connection (see below).

    connID              The connection ID (see "Pup Specifications").

    rtpOtherPupProc     A procedure called upon receipt of any Pup that
                        is  not  part  of   the  Rendezvous/Termination

    rtpOtherTimer       A timer for use by higher levels of protocol.

    rtpOtherTimerProc   A procedure called when rtpOtherTimer expires.

There is  some other information  (wasListening, rtpTimer) used  by the
RTP module but not of interest to external programs.

At a given moment, an RTPSoc may be in one of a number of  "states".  A
detailed explanation of  the meanings of these  states may be  found in
the memo "Pup Connection State Diagram" (file RTPStates.press).

Pup Package                November 21, 1981                         20

    stateClosed    No  connection  exists: either  none  has  ever been
                   created  or  a  previously  existing  connection has

    stateRFCOut    The  local  process  has  initiated  a  request  for
                   connection (RFC) to  some foreign process.   A reply
                   is expected from the remote process.

    stateListening The local process is "listening" for an RFC from any
                   foreign process.

    stateOpen      The connection is considered by both parties to have
                   been established.  What the cooperating processes do
                   with  this connection  is a  matter  of higher-level
                   protocol (e.g., BSP).

    stateEndIn     The   foreign   process  has   requested   that  the
                   connection   be  terminated,   and  is   awaiting  a
                   confirmation from the local process.

    stateEndOut    The local process has requested that  the connection
                   be terminated, and  is awaiting a  confirmation from
                   the foreign process.

    stateDally     A transitory state having to do with the termination
                   handshake (see "Pup Specifications").

    stateAbort     The connection  has been  aborted abnormally  by the
                   foreign process.

An RTPSoc is created  by calling OpenRTPSocket, which  performs various
initialization, creates a background process to manage  the connection,
and  interacts with  some foreign  process in  one of  three  ways (see
below) to  open a  connection.  Once  the connection  is open,  the RTP
background process monitors the  socket for arrival of  Pups requesting
that the connection be closed or aborted, and updates the state  of the
socket appropriately.   The local process  may also  request explicitly
that the connection be terminated, by calling CloseRTPSocket.

The procedures defined in the RTP module are the following:

OpenRTPSocket(soc, ctxQ [pupCtxQ], openMode [modeInitAndWait], connID
          [random], otherProc [DefaultOtherPupProc], timeout
          [defaultTimeout], zone [pupZone]) = true or false
    Causes an RTP socket to be created and optional interactions with a
    foreign  process  to be  initiated.   "soc" is  a  block  of length
    lenRTPSoc which  must already  have been initialized  as a  level 1
    socket (PupSoc) by a prior call to OpenLevel1Socket.   (An external
    static "lRTPSoc" exists whose value  is the length of an  RTPSoc in
    words.) Both  the local and  foreign port addresses  (the "lclPort"
    and "frnPort" fields in the PupSoc) must be completely established,
    unless "openMode" is "listenAndWait" or "listenAndReturn", in which
    case only the local socket number (soc>>PupSoc.lclPort.socket) need
    be established.

    "ctxQ"  is a  context  queue to  which  a context  created  by this
    procedure  may be  appended.  It  defaults to  pupCtxQ  (the "ctxQ"
    passed to InitPupLevel1).

Pup Package                November 21, 1981                         21

    "openMode" specifies the  manner in which  the connection is  to be
    opened.  If  it is "modeInitAndWait",  a request for  connection to
    the  foreign process  is initiated,  and OpenRTPSocket  then blocks
    until either  the answering  RFC is  received and  the connection's
    state becomes  open (in  which case  it returns  true) or  an error
    occurs  (in  which  case the  RTPSoc  is  closed  and OpenRTPSocket
    returns  false).   If  it is  "modeInitAndReturn",  the  request is
    initiated in a similar manner, but then OpenRTPSocket  returns true
    immediately and  it is the  caller's responsibility to  monitor the
    subsequent state of the connection.

    If "openMode"  is "modeListenAndWait",  the socket  is placed  in a
    "listening" state.  When a request for connection is  received from
    some  foreign  process, a  reply  is generated  and  the connection
    becomes  open,  and OpenRTPSocket  returns  true.  If  the  mode is
    "modeListenAndReturn", OpenRTPSocket  returns true  immediately and
    it is the caller's  responsibility to monitor the  subsequent state
    of the connection.

    If  "openMode" is  "modeImmediateOpen", the  socket  is immediately
    placed in the open state (it is assumed that the caller has already
    performed  a  rendezvous with  the  foreign process  in  some other
    manner) and OpenRTPSocket returns true.

    "connID"  is  a  pointer  to  a  two-word  vector   specifying  the
    connection  ID (see  "Pup  Specifications").  If  not  specified, a
    connection  ID  is  chosen  at  random.   "connID"  need  never  be
    specified if "openMode" is one of the listening modes.

    "otherProc"  is a  procedure to  be called  when a  non-RTP  Pup is
    received  by the  socket.  This  will be  described in  more detail
    later.     If    not    specified,    "otherProc"    defaults    to
    DefaultOtherPupProc, a procedure that simply releases any PBI it is
    passed   (one   may   change   the   default   by   clobbering  the
    DefaultOtherPupProc static with something else).

    "timeout" specifies  the maximum time  OpenRTPSocket will  wait (if
    "openMode"  is  "modeInitAndWait"  or  "modeListenAndWait")  before
    timing  out  and  returning false.   It  (and  all  other "timeout"
    arguments in the Pup package) is in units of 10  milliseconds, with
    a maximum legal value of 2↑15 (a little over 5  minutes), according
    to  the   conventions  established  in   the  Timer   Package.   If
    unspecified,  "timeout"  defaults  to  "defaultTimeout",  a  static
    defined in this module, whose value in the released package is 6000
    (i.e.,    60   seconds;    this   is    set   by    the   parameter
    "defaultDefaultTimeout" in PupParams.decl).

    "zone" is a free-storage zone  from which a context block  (of size
    rtpStackSize) may  be allocated.  If  it is not  specified, pupZone
    (the "zone" passed to InitPupLevel1) is used.   Note: OpenRTPSocket
    calls InitializeContext, so the ContextInit module must be resident
    (despite what the Context Package writeup says).

CloseRTPSocket(soc, timeout [...defaultTimeout]) = true or false
    Requests  that  the  connection  rooted  in  the  RTPSoc  "soc"  be
    terminated.   If  "timeout"  is nonzero,  a  normal  termination is
    attempted if possible; if zero (or the attempted normal termination
    times  out),  the connection  is  aborted  (terminated abnormally).
    When  the  connection  has  been  closed,  the  context  created by

Pup Package                November 21, 1981                         22

    OpenRTPSocket is destroyed and  returned to the zone from  which it
    was allocated.  CloseRTPSocket then returns true if  the connection
    was  terminated  normally and  false  if abnormally.   The  level 1
    PupSoc pointed  to by "soc"  still exists, and  it is  the caller's
    responsibility to dispose of it appropriately (generally by calling

The  process  created by  OpenRTPSocket  (called  RTPSocketProcess) has
several responsibilities.  First, all Pups arriving on the  socket's iQ
are  dequeued  and  inspected.   Ones  whose  types  are  part  of  the
Rendezvous/Termination protocol are processed internally.  All protocol
interactions  (including  replies,  retransmissions,  and  local  state
changes) are handled automatically.

Received  Pups  that  are  not  part  of  the  RTP  are  passed  to the
"rtpOtherPupProc" procedure,  which is  initialized to  the "otherProc"
argument in OpenRTPSocket.  More specifically, the statement


is executed,  and it  is up  to the  called procedure  to appropriately
process and  dispose of the  PBI.  Since this  call is made  within the
context of the RTPSocketProcess, which has only "rtpStackSize"  (130 as
released) words of stack space, the called procedure cannot  make heavy
demands  on  the  stack  without risk  of  stack  overflow.   One might
increase rtpStackSize (a static  defined in this module,  whose initial
value  is given  in PupParams.decl  as "defaultRTPStackSize"),  but the
safest course of action is  for the called procedure simply  to enqueue
the PBI  on some  queue looked at  by another  process with  more stack
space  available   to  it.   (One   should  note,  however,   that  the
"rtpOtherPupProc" procedure defined by the BSP module, to  be described
in the next section, manages to do all its work--a significant amount--
without  overflowing  the  RTP  process's  stack.   The  main potential
pitfall is in  calling system procedures such  as Ws that  require very
large amounts of stack space in some cases.)

"Abort" and "Error" Pups, while handled by RTPSocketProcess  (for their
effects  on   the  socket's   state),  are  also   passed  on   to  the
"rtpOtherPupProc" procedure, for purposes such as displaying  the Pup's
text to  the user.   The RTP module  distinguishes between  "fatal" and
"non-fatal" sub-types  of Errors,  treating the former  the same  as an
Abort  (thereby  placing  the  connection  in  the  "Abort"  state) and
ignoring   the   latter;   both   kinds,   however,   are   passed   to

Additionally,  the RTPSocketProcess  checks for  expiration of  a timer
called "rtpOtherTimer"  in the  RTPSoc.  If  it expires,  the procedure
given  in  "rtpOtherTimerProc"  is  called,  with  the  socket  as  its
argument.  This facility is used in the BSP module, which also requires
the  ability  to do  asynchronous  processing.   "rtpOtherTimerProc" is
initialized to Noop when OpenRTPSocket is called.

The following miscellaneous procedures defined in the RTP module are of
possible interest to callers:

RTPFilter(pbi, checkFrnPort, checkID) = true or false
    Does selective filtering of "pbi" against parameters in  the socket
    to  which the  PBI is  assigned,  and returns  true if  the  PBI is
    accepted and false if rejected.  First, broadcast Pups (destination

Pup Package                November 21, 1981                         23

    host zero) are always rejected.  Then, if checkFrnPort is true, the
    source port  address of the  PBI is checked  for equality  with the
    foreign port address given  in the socket.  Finally, if  checkID is
    true,  the Pup  ID in  the  PBI is  checked for  equality  with the
    connection ID in the socket.

CompleteRTPPup(pbi, type, length)
    Stores "type"  and "length"  in the respective  fields of  the Pup,
    copies the connection  ID from the socket  to the Pup,  and finally
    calls CompletePup(pbi) to send it on its way.

5. Byte Stream Protocol Interface

The BSP module (files PupBSPStreams, PupBSPProt, and  PupBSPa) contains
procedures for sending  and receiving error-free,  flow-controlled byte
streams to and from a  foreign process, and for dealing with  the other
primitives defined by the BSP (namely Marks and Interrupts).

A process's interface to  the BSP module is by  way of a BSPSoc,  a BSP
socket structure, which is a further extension of an RTPSoc  (which, it
will be recalled, is an extension of a PupSoc).  The BSPSoc  contains a
large amount  of additional information,  most of which  fortunately is
not of interest to external  programs.  The items that are  of interest
are the following:

    bspStatus           A   word   containing   various   status  bits,
                        including the following three:

    markPending         A Mark has  been encountered while  reading the
                        incoming  byte  stream.   Further  attempts  at
                        input  (via  Gets  or  BSPReadBlock)  will fail
                        until this bit is cleared (either explicitly or
                        by calling BSPGetMark).

    interruptIn         An Interrupt has been received.  If  the caller
                        depends on this bit for noticing the arrival of
                        Interrupts,   then  it   must  clear   the  bit
                        explicitly after doing so.  Interrupts arriving
                        in close succession will not be distinguishable
                        as separate events unless they  are intercepted
                        via the "bspOtherPupProc"  mechanism, described

    noInactivityTimeout This flag, normally  false, may be set  to true
                        to disable an automatic timeout  mechanism that
                        aborts  the  BSP  connection  if   the  foreign
                        process does  not respond  to any  BSP protocol
                        requests for two minutes.  The purpose  of this
                        is to detect that a connection has died (due to
                        network   failure   or   the   foreign  process
                        crashing).  Being able to disable  this timeout
                        mechanism is handy during debugging.

    bspOtherPupProc     A procedure called upon receipt of any  Pup not
                        part of the BSP (or RTP).

Pup Package                November 21, 1981                         24

    bspStr              A  block  containing  a  BSPStr,  a  BSP stream
                        structure.   This contains  the  dispatches for
                        interfacing to  the operating  system's generic
                        stream-handling  procedures (Gets,  Puts), plus
                        some information specific to the BSP stream.

A BSP  stream is  created by first  opening a  connection to  a foreign
process (by means of the RTP), then calling the following procedure:

CreateBSPStream(soc) = str
    Creates and initializes a BSP socket, and returns a pointer  to the
    stream block  within it.  "soc"  must point to  a region  of length
    lenBSPSoc (which is the  value of an external static  lBSPSoc), and
    it  must already  support one  end of  an open  RTP  connection (by
    having been passed to OpenLevel1Socket and then OpenRTPSocket).  If
    the  state  of  the  connection  is  not  stateOpen  or stateEndIn,
    CreateBSPStream returns zero.  Otherwise, the stream  is completely
    initialized  and the  pointer to  it is  returned.  See  the sample
    program at the  end of this document  for an example of  the proper
    sequence of operations for opening a BSP stream from scratch.

All the  generic stream  procedures (Gets, Puts,  etc.) must  be passed
"str"  as  an  argument,  as  should  the  procedures  BSPReadBlock and
BSPWriteBlock.  However, all other operations on the  socket (including
specialized BSP  functions such  as BSPGetMark)  must be  passed "soc".
When necessary, "str" and "soc" may be computed from each other  by the
following statements:

    str = soc+offsetBSPStr
    soc = str-offsetBSPStr

where offsetBSPStr is an external static defined in the BSP package.

The defined generic stream procedures are as follows.  The descriptions
of  Gets  and  Puts  assume  that  the  default  stream  error-handling
procedure  (invoked  by Errors(str,  ec))  is in  use;  the  real truth
appears in the description of Errors.

Gets(str, timeout [...-1]) = byte or -1
    Attempts to return the next byte from the BSP stream "str"; returns
    -1 on  any failure.  A  failure will result  if the  connection has
    become  closed  or a  Mark  has been  encountered  in  the incoming
    stream.  If "timeout" is -1 (the default), Gets  waits indefinitely
    for data to arrive (or  some failure condition to arise);  if other
    than -1, it  waits up to "timeout"  (units of 10  milliseconds) and
    then gives the failure return.

    Note  that  occurrence  of the  timeout  condition  does  not imply
    anything about the health of the connection; the timeout feature is
    provided entirely for the caller's convenience, and has  nothing to
    do  with  the  internal  connection  inactivity  timeout.   If  the
    connection  fails,  the connection  state  (soc>>RTPSoc.state) will
    change to something other than stateOpen.

Puts(str, byte, timeout [...-1]) = true or false
    Attempts to output "byte" to the BSP stream "str"; returns  true on
    success  and  false  on  failure.  A  failure  will  result  if the
    connection  has  become closed  or  the operation  times  out.  The
    "timeout"  is   defined  as   for  Gets,   with  -1   meaning  wait

Pup Package                November 21, 1981                         25

    indefinitely.  Note  that in  general, outputting a  byte to  a BSP
    stream  merely causes  that  byte to  be appended  to  a partially-
    constructed Pup  in memory;  only when a  Pup is  filled up  is any
    packet  actually  sent  over  the  net.   BSPForceOutput (described
    below) must be called to cause a partially-filled Pup to  be closed
    out and transmitted immediately.

Endofs(str) = true or false
    Returns true if there is not presently any data to be read from the
    BSP stream "str"  or a Mark has  been encountered.  Note  that this
    definition of Endofs is analogous to that for "keys" as  opposed to
    that for disk files; i.e., so long as the connection is still open,
    Endofs(str) being true says only that there is not now any  data to
    be read, not that there won't be data at some time in the future.

Closes(str) = true or false
    Closes the BSP stream "str" and destroys the associated  socket, as
    detailed in the description of CloseBSPSocket (below).

Errors(str, ec) = value
    The stream  error procedure (which  is initialized to  BSPErrors by
    CreateBSPStream) is called  under various error  conditions arising
    in  Gets  and  Puts.   The  error code  "ec"  will  be  one  of the

    ecBadStateForGets   Gets has  failed because  the connection  is no
                        longer open.  This can occur either  because an
                        Abort or fatal Error is received or because the
                        connection's  inactivity  timeout  (2  minutes)
                        expires.   (The  timeout  may  be  disabled for
                        debugging       purposes       by       setting
                        soc>>BSPSoc.noInactivityTimeout to true.)

    ecGetsTimeout       Gets   has  failed   because  no   data  became
                        available  for   reading  within   the  timeout
                        specified in the call to Gets.

    ecMarkEncountered   Gets has  failed because  it has  encountered a
                        Mark in the stream.

    ecBadStateForPuts   Puts has  failed because  the connection  is no
                        longer open.

    ecPutsTimeout       Puts has failed because it was not  possible to
                        output the byte within the timeout specified in
                        the call to Puts.

    In each case, the Gets or Puts returns the result of calling Errors
    with the  corresponding error code.   The default  Errors procedure
    returns -1 when passed any  of the Gets error codes and  false when
    passed one of the  Puts error codes, thereby obtaining  the failure
    behavior presented earlier in the descriptions of Gets and Puts.

The  remaining procedures  operate on  a "soc"  (BSPSoc) rather  than a
"str", since they are peculiar to BSP.

CloseBSPSocket(soc, timeout [...defaultTimeout]) = true or false
    Closes the connection and destroys the BSPSoc pointed to  by "soc".
    First,  if  the connection  is  still in  a  reasonable  state, any

Pup Package                November 21, 1981                         26

    pending  output  is  transmitted; CloseBSPSocket  will  wait  up to
    "timeout" for  successful acknowledgment of  this data.   Next, the
    connection  is  terminated   by  a  call  to   CloseRTPSocket  (the
    description  of which  includes the  interpretation  of "timeout").
    Then all  PBIs still  residing on the  BSPSoc's various  queues are
    released.   Finally,  the  socket   is  destroyed  by  a   call  to
    CloseLevel1Socket.  The result  returned is true if  the connection
    was closed normally, false if abnormally.

BSPGetMark(soc) = byte
    Returns the value of the pending Mark byte in the  incoming stream,
    and clears  the markPending flag  so as to  permit future  calls to
    Gets to read data past the Mark in the stream.  This procedure will
    call SysErr(soc, ecBadBSPGetMark)  if a Mark  has not in  fact been

BSPPutMark(soc, markByte, timeout [...-1], sendNow [false]) = true or
    Inserts the specified "markByte" into the outgoing stream.  Calling
    this procedure causes all data up to and including the Mark byte to
    actually  be   transmitted  immediately.   The   interpretation  of
    "timeout" and the result returned by the procedure are the  same as
    for Puts; "sendNow" is described under BSPForceOutput (below).

BSPForceOutput(soc, sendNow [false])
    Forces   any  partially-filled   output  Pup   to   be  transmitted
    immediately.   This procedure  will never  block.  If  "sendNow" is
    true,  the BSP  package  will elicit  an  immediate acknowledgment,
    thereby expediting the process  of flushing the local  output queue
    of unacknowledged  Pups.  The  caller should  set this  argument to
    true  when  it  expects  not  to  send  more  data  for   a  while,
    particularly if it  is about to turn  around and receive  some data
    over the same stream.

BSPPutInterrupt(soc, code, string, timeout [...-1]) = true or false
    Generates a BSP Interrupt Pup (see "Pup Specifications")  using the
    specified  "code"  for  the Interrupt  Code  and  "string"  for the
    Interrupt Text.   The procedure  returns true  unless it  failed to
    send the  Interrupt due  either to the  connection no  longer being
    open or to exhausting the specified "timeout".

The BSP module accomplishes much of its work as a result of being given
control by the socket's RTPSocketProcess context through two paths: the
"rtpOtherPupProc" procedure, called when a non-RTP Pup  is encountered,
and the "rtpOtherTimerProc" procedure, called when  the "rtpOtherTimer"
expires.   These  three  cells  in  the  RTPSoc  structure  are renamed
"bspPupProc", "bspTimer", and "bspTimerProc" within the BSP module.  By
this means, the management  of both incoming and outgoing  byte streams
is   accomplished   automatically   (including   the    generation   of
acknowledgments and retransmissions).

Received Pups that are not part of either the RTP or the BSP are handed
to the  procedure given  in the "bspOtherPupProc"  cell in  the socket.
This  is  initialized  to   the  previous  contents  of   the  socket's
"rtpOtherPupProc" by  CreateBSPStream (which then  stores a  pointer to
the BSP  module's own  BSPPupProc into the  latter cell).   The earlier
description of  "rtpOtherPupProc" (in  the section  on the  RTP module)
applies to "bspOtherPupProc".

Pup Package                November 21, 1981                         27

Received Interrupt packets  are also passed to  "bspOtherPupProc" after
being processed by  the BSP module.  Note  that an Interrupt  passed in
this manner has been verified to conform to protocol (this is  the case
also for Abort and Error packets passed up from the RTP module) and may
therefore be "believed".  Any other type of packet, on the  other hand,
has had no checking done on it beyond the level 1 interface  (where the
destination port and checksum were verified).

A note on allocations:  this BSP implementation probably will  not work
at all unless the socket's PBI allocations are at least 3, 2, and 2 for
"total", "input", and  "output" respectively.  High throughput  will be
gained only by giving the socket somewhat larger allocations (say, 6 to
10 PBIs) for the direction(s) in which high throughput is desired.

In a program with at most one active BSP connection, that socket should
be allocated  all of the  PBIs in the  system except one  per directly-
connected network  (there must  always be one  extra PBI  available for
receiving  incoming  packets  on each  network);  this  is  the default
allocation established  in dPSIB by  InitPupLevel1.  In a  program with
several  active  connections,  one  should  adjust   individual  socket
allocations appropriately (though  probably not simply by  dividing the
total PBIs by the number of sockets, since doing so typically  leads to
underutilization of PBIs).   Assuming there are  plenty of PBIs  in the
system,  it  is  generally  safe  to  overcommit  the  system resources
(relying  on  the  statistical  unlikelihood  that  all   sockets  will
simultaneously  tie up  all  the PBIs  to which  they  are individually
entitled).   One  should  be  aware,  however,  that  the  higher-level
protocols  can  get into  deadlock  conditions if  the  system pbiFreeQ
becomes exhausted.  For  the same reason, a  PBI passed to  an external
program via the "bspOtherPupProc" entry in the socket must  be released
as  quickly  as possible,  since  it is  charged  against  the socket's

The BSP module includes a static "bspVersion" whose value  is (protocol
version * 1000) + package version.

6. BSP Block Transfer Procedures

The BSP stream mechanism just presented, while being a "fast stream" in
the sense defined by the operating system, is still relatively slow and
is  therefore not  well suited  to transferring  large volumes  of data
(such  as file  transfers  between disk  and net).   A  separate module
(PupBSPBlock) is provided for accomplishing block transfers at least an
order of magnitude faster than by iterated calls on Gets or Puts.  This
module requires  that the  AltoByteBlt module  (released as  a separate
package) be loaded as well.

Two procedures are defined in this module:

BSPReadBlock(str, wordP, byteP, count, timeout [...-1]) = count
    Reads a maximum of "count" bytes from the BSP stream "str", storing
    them in memory starting  at byte position "byteP" relative  to word
    address "wordP" (for example, byteP = 0 means the left byte  of the
    word referenced by "wordP").  The transfer terminates under  any of
    the  conditions that  would cause  Gets(soc,timeout) to  return -1.
    The procedure returns the actual number of bytes transferred.

Pup Package                November 21, 1981                         28

BSPWriteBlock(str, wordP, byteP, count, timeout [...-1]) = count
    Writes  a  maximum  of  "count"  bytes  to  the  BSP  stream "str",
    obtaining  them  from  memory  starting  at  byte  position "byteP"
    relative to  word address "wordP".   The transfer  terminates under
    any of  the conditions that  would cause  Puts(soc,byte,timeout) to
    return false.   The procedure  returns the  actual number  of bytes

7. Network Directory Lookup Module

This  module  (file  PupNetDirLookup)  contains  procedures  to convert
between  a string  consisting of  any legal  inter-network name/address
expression and a  Port structure containing the  corresponding address.
See  the  memo  "Naming  and  Addressing  Conventions  for  Pup"  (file
PupName.press) for information on legal expressions.

The PupNetDirLookup module contains all the procedures described below.
The alternative PupNameLookup module,  included in the Pup  package for
historical reasons, contains only GetPartner and  ParseAddressConst; it
is  somewhat  smaller  than  PupNetDirLookup, and  it  may  be  used in
situations where the other functions are not needed.

GetPartner(name, stream [none], port, s1 [...none], s2 [...none]) =
          true or false
    Parses  the BCPL  string "name"  and stores  the  resulting address
    value in  the Port structure  "port", returning true  if successful
    and false otherwise.  "stream", if nonzero, is used  for publishing
    an error message if the conversion is unsuccessful.  "s1" and "s2",
    if supplied, specify the  high- and low-order parts of  the default
    socket number, which is  substituted into the "port" if  the socket
    number is unspecified in the "name".

    If the "name" consists  entirely of address constants (in  the form
    "net#host#socket" or some subset thereof, where the  components are
    octal numbers), then  it is parsed locally.   Otherwise, GetPartner
    attempts  to  establish  contact with  a  Network  Directory Lookup
    server, to which it passes the "name" for evaluation.  If the reply
    consists of several alternative addresses, the "best" one is chosen
    on the basis of information in the local routing table.  Regardless
    of whether  or not  the string is  an address  constant, GetPartner
    will return false (with the message "Can't get there from here") if
    no routing table entry exists for the resulting network and several
    calls to LocateNet discover no way of reaching that network.

ParseAddressConst(name, port) = true or false
    Attempts to parse the BCPL string "name" as an address  constant of
    the  form  "net#host#socket".   Stores  the  result  in  "port" and
    returns true if successful; returns false if unsuccessful.

EnumeratePupAddresses(name, filter [TakeTheFirst], arg [], dontCheckRT
          [false]) = 0 or error code
    Evaluates "name" to one or more addresses.  For each address, calls
    filter(port,  arg), where  port is  a pointer  to a  Port structure
    containing  that   address  and   arg  is   the  "arg"   passed  to
    EnumeratePupAddresses.  If filter returns true,  enumeration stops;
    if false, enumeration continues.

Pup Package                November 21, 1981                         29

    Ordinarily  the addresses  are  enumerated in  order  of increasing
    distance away from here (hop count), and inaccessible addresses are
    omitted;  however,  if  "dontCheckRT"  is  supplied  and  true, the
    addresses are not sorted and are all returned.  Filter  defaults to
    an internal procedure TakeTheFirst, which treats "arg" as a pointer
    to a Port and copies the first Pup address to that port, discarding
    the rest.

    EnumeratePupAddresses returns zero if successful and an  error code
    (from  PupNetDir.decl)  if  unsuccessful.   The  error   codes  are
    ecNameNotFound,  meaning that  the name  is not  registered  in the
    Network Directory  server data  base; ecCantGetThere,  meaning that
    the name exists but none of the addresses are  currently accessible
    in the internet;  and ecNoServerResponded, meaning that  no Network
    Directory server could be located.

PupAddressLookup(port, lvEC [], zone [pupZone]) = string or 0
    Interacts with  a network  directory server to  find a  name string
    corresponding  to  the  Pup  address  pointed  to  by  "port".   If
    successful, returns a string allocated from "zone"  (which defaults
    to pupZone,  the zone passed  to InitPupLevel1).   If unsuccessful,
    stores an error code  (from PupNetDir.decl) at @lvEC (which  may be
    omitted) and returns zero.  The error codes  are ecAddressNotFound,
    meaning that the address is not registered in the Network Directory
    server data base; and ecNoServerResponded, meaning that  no Network
    Directory server could be located.

8. Example

The  following example  program  makes use  of most  of  the facilities
provided in  the Pup  package.  It is  basically a  rock-bottom minimal
user Telnet (like Chat) with no redeeming features whatsoever.

The main procedure  PupExample performs initialization,  which consists
of  creating a  large zone,  initializing the  Pup package,  creating a
large display window, and  creating and starting a context  running the
procedure TopLevel.

TopLevel first requests the user to type in a foreign port  name, which
it  parses  by  calling  GetPartner (note  that  the  socket  number is
defaulted to 1,  the server Telnet socket).   Then a socket  is created
and a connection is opened.  Two new contexts are now  created, running
the  procedures KeysToNet  and  NetToDsp.  TopLevel  then  blocks until
either the connection is no longer open or the second blank key  on the
right of the  keyboard is pressed, at  which point it destroys  the two
contexts  it created,  closes  the connection,  and loops  back  to the

The KeysToNet procedure blocks waiting for keyboard input, then outputs
the typed-in character  to the BSP  stream and calls  BSPForceOutput to
force  immediate transmission.   If  the Puts  fails,  KeysToNet simply
blocks forever, in the  expectation that TopLevel will detect  that the
connection is no longer open and take appropriate action.

The NetToDsp procedure  blocks waiting for  input from the  BSP stream.
When a normal character is  received, it is output to the  display.  If

Pup Package                November 21, 1981                         30

Gets returns -1,  then either a Mark  is pending or the  connection has
ended; if the former, a message is printed and BSPGetMark is  called to
clear  the  Mark  pending  status;  if  the  latter,   NetToDsp  blocks

// PupExample.bcpl

// Bldr PupExample PupBSPStreams PupBSPProt PupBSPa PupBSPOpenClose ↑
//  PupRTP PupRTPOpenClose PupNameLookup ↑
//  Pup1b PupAl1a Pup1OpenClose PupRoute ↑
//  PupAlEthb PupAlEtha ↑
//  Context ContextInit Interrupt AltoQueue AltoTimer ↑
//  Pup1Init PupDummyGate PupAlEthInit InterruptInit

get "Pup.decl"

InitPupLevel1; OpenLevel1Socket; CloseLevel1Socket; SetAllocation
OpenRTPSocket; CreateBSPStream; GetPartner
BSPForceOutput; BSPGetMark
InitializeContext; CallContextList; Block; Enqueue; Unqueue
InitializeZone; CreateDisplayStream; ShowDisplayStream
Gets; Puts; Closes; Endofs; Ws
keys; dsp
static [ ctxQ; myDsp; bspSoc; bspStr ]

let PupExample() be  // initialization
let myZone = vec 10000; InitializeZone(myZone, 10000)
let q = vec 1; ctxQ = q; ctxQ!0 = 0
InitPupLevel1(myZone, ctxQ, 20)
let v = vec 10000
myDsp = CreateDisplayStream(40, v, 10000)
let v = vec 3000
Enqueue(ctxQ, InitializeContext(v, 3000, TopLevel))
CallContextList(ctxQ!0) repeat

and TopLevel() be  // top-level process
Ws("*nConnect to: ")
let name = vec 127; GetString(name)
if name>>String.length eq 0 then finish
let frnPort = vec lenPort
unless GetPartner(name, dsp, frnPort, 0, 1) do loop
let v = vec lenBSPSoc; bspSoc = v
OpenLevel1Socket(bspSoc, 0, frnPort)
unless OpenRTPSocket(bspSoc, ctxQ) do
   [ Ws("*nFailed to connect"); CloseLevel1Socket(bspSoc); loop]
bspStr = CreateBSPStream(bspSoc)
let keysToNetCtx, netToDspCtx = vec 1000, vec 1000
Enqueue(ctxQ, InitializeContext(keysToNetCtx, 1000, KeysToNet))
Enqueue(ctxQ, InitializeContext(netToDspCtx, 1000, NetToDsp))

Pup Package                November 21, 1981                         31

Block() repeatuntil bspSoc>>BSPSoc.state ne stateOpen %
   @#177035 eq #177775  //second blank key pressed
Unqueue(ctxQ, keysToNetCtx); Unqueue(ctxQ, netToDspCtx)
] repeat

and KeysToNet() be
test Puts(bspStr, GetKeys())
   ifso BSPForceOutput(bspSoc)
   ifnot Block() repeat
] repeat

and NetToDsp() be
let char = Gets(bspStr)
if char eq -1 then
   test bspSoc>>BSPSoc.markPending
         Ws("*nI saw a Mark!")
      ifnot Block() repeat
Puts(myDsp, char)
] repeat

and GetKeys() = valof
while Endofs(keys) do Block()
resultis Gets(keys)

and GetString(string) be
for i = 1 to 255 do
   let char = GetKeys(); Puts(dsp, char)
   test char eq $*n
      ifnot string>>String.char↑i = char
      ifso [ string>>String.length = i-1; return ]

9. Revision History

March 25, 1976

Various  minor bugs  in both  code and  documentation were  fixed.  One
serious  error  in  the   documentation  was  in  the   description  of

Pup Package                November 21, 1981                         32

CreateBSPStream, where "lenBSPStr"  should have been  "lenBSPSoc".  The
level 1, RTP,  and BSP modules  each became slightly  smaller.  Various
calls to CallSwat were changed to SysErr with registered error codes.

Level 0: External change: file PupAlEth.bcpl replaced by PupAlEthb.bcpl
and  PupAlEtha.asm.  Internal  change: fast  (~20-instruction) Ethernet
receiver turnaround implemented.

Level  1:  External   changes:  statics  pupZone  and   pupCtxQ  added;
procedures SetPupDPort, SetPupSPort, SetPupSPort, and FlushQueue added;
RT structure definition changed; default pupErrSt is now a "nil" stream
rather than "dsp".

RTP:  External changes:  defaultTimeout and  rtpStackSize  changed from
manifests  to statics  (with default  values  defaultDefaultTimeout and
defaultRTPStackSize); DefaultOtherPupProc added.

BSP: External  change: static bspVersion  added.  Internal  change: the
transmission strategy was  modified to elicit an  acknowledgment before
allocation is completely exhausted, hence reducing lost  throughput due
to round-trip delay.

April 16, 1976

The released package Pup.dm was renamed PupPackage.dm, and  a debugging
version  of the  package  released as  PupDebug.dm.  A  number  of bugs
(particularly in level 1) were uncovered while bringing up the software
on the Nova.

Level 0: External change:  lenPup and lenPBI changed from  manifests to
statics  (defined  in level  1)  to permit  changing  PBI  size without
recompiling  the  package.  Internal  change:  100-millisecond transmit
timeout and discard added (eliminating deadlocks caused by  things like
disconnecting the Alto from the Ethernet).

Level 1: External changes:  gateway code split out into  separate files
PupGateway and PupDummyGate, one  of which must be loaded  (usually the
latter); optional extra argument "pupDataBytes" added to InitPupLevel1;
default allocations in dPSIB changed  to permit a socket to  assign all
but  one  of the  PBIs  in the  system;  OpenLevel1Socket  defaults the
foreign net in some  circumstances.  Internal change: if  "pupDebug" is
on, PupLevel1 checks for the pbiFreeQ being exhausted for more  than 20
seconds and calls Swat (this usually indicates a deadlock).

BSP: External change:  PupBSPb.bcpl replaced by  PupBSPStreams.bcpl and
PupBSPProt.bcpl  (necessitated  by  Nova  BCPL's  inability  to compile
PupBSPb in one gulp).

May 18, 1976

Mostly  bug  fixes   and  performance  improvements.    Some  structure
definitions were changed, so recompilation of user programs is advised.

Level 0: Internal changes: more assembly code included to reduce packet
loss rate; performance statistics gathered if pupDebug on.

Level 1: External change: optional "type" and "length"  arguments added
to CompletePup.

October 6, 1976

Pup Package                November 21, 1981                         33

Significant internal changes were made  at levels 0 and 1,  and several
new capabilities were  added.  However, for  the most part  the changes
are  upward-compatible.    Many  structure  declarations   changed,  so
recompilation of programs that "get" any Pup .decl files is required.

Level  0: External  changes: SendEtherPup  removed; EncapsulateEtherPup
and  SendEtherPacket  added;  ability  to  send  and  receive  non-Pups

Level  1:  External  changes: PupRoute  file  added;  PupGateway module
deleted  from  public  Pup package  release;  routing  table completely
reorganized;  new  procedures  HLookup,  HInsert,  HDelete, HEnumerate,
HHash added; pupErrSt removed; mechanism added for broadcasting  to all
connected   networks;  procedures   DoubleIncrement,  DoubleDifference,
Double subtract  included (formerly in  BSP module).   Internal change:
GatewayListener dynamically maintains the best path to each network and
purges  RTEs of  networks  for which  no routing  information  has been
received recently.

BSP: Internal  change: adaptive  retransmission timeout  implemented to
reduce packet loss rate when  sending through slow networks or  to slow
destinations (e.g., Maxc).

March 21, 1977

Mostly bug fixes.  Some structure definitions at level 0  were changed,
so recompilation of user programs is advised.

Level 0: SendStats operation added to the NDB object.

July 11, 1977

No external  changes.  The Ethernet  driver was rewritten  to eliminate
several  low-probability   race  conditions  and   improve  performance
slightly.   The  driver  now  uses  the  "input  under  output" feature
unconditionally, so problems may be encountered on Alto-Is  running old

March 20, 1978

External changes:  Several source files  have been broken  into smaller
pieces to  permit much  of the code  to be  included in  overlays.  The
added modules  are Pup1OpenClose, PupRTPOpenClose,  and PupBSPOpenClose
(see section 1.2 for revised packaging information).   Recompilation is
required of any programs that get Pup.decl or PupBSP.decl.

Internal changes: BSP performance  through slow links and  gateways has
been improved.  GetPartner's timeout  has been increased.  A  few minor
bugs have been fixed.

November 6, 1978

Level 0: External changes: The Ethernet driver can now control multiple
interfaces  connected  to  the  same  Alto.   InitAltoEther  is  called
differently.  Drivers are now available for the XEOS EIA  interface and
the ASD Communication Processor, though they aren't documented here.

Level  1:  Internal  change: The  routing  module  data  structures and
algorithms have  geen modified  to conform to  some minor  Pup protocol

Pup Package                November 21, 1981                         34

BSP:  External  change:  An  inactivity  timeout  has  been   added  to
automatically abort connections that have died; this may be disabled by
setting the  noInactivityTimeout bit in  the BSPSoc.   Recompilation is
required of any programs that get Pup.decl or PupBSP.decl.

February 19, 1979

Level 0:  Internal change:  The format of  the statistics  collected by
drivers changed.

Level  1:  Internal  change: The  interface  between  PupRoute  and the
forwarder changed.   This is  only of  interest to  gateways.  External
change: The definitions of  pup types and well-known sockets  have been
removed from Pup1.decl.  We now  feel that these belong in  less global
declaration  files  closer   to  the  code  implementing   the  various
protocols.   Recompilation  of   user  programs  will   probably  cause
undefined symbols which you will have to add to your declaration files.

May 27, 1979

Level 1: External  changes: InitPupLevel1 takes an  additional optional
argument   "numRTE";   LocateNet   procedure   added;   HHash  removed;
PupDummyGate  module  moved from  resident  to  initialization; lPupSoc
static added.  Internal  changes: the routing table  is now a  cache of
routing information rather than a hash table of all accessible networks
in the internet; RTEs may  be "invalid" (hops greater than  maxHops and
ndb equal to zero); new PupRoute.decl includes definitions  internal to
the routing module.

RTP: External change: lRTPSoc static added.  Internal change: more code
moved from resident (PupRTP) to swappable (PupRTPOpenClose) modules.

BSP: External change: lBSPSoc and offsetBSPStr statics added.  Internal
changes: minor bugs fixed; more code moved from resident (PupBSPStreams
and PupBSPProt) to swappable (PupBSPOpenClose) modules.

NameLookup: External  changes: RequestNameLookup  and ParseAddressConst
procedures now exported.

March 9, 1980

Levels 0 & 1: External change: a "destroy" operation has been  added to
the NDB, and  the procedure DestroyPupLevel1  is included to  shut down
the Pup package.  A few bugs have been fixed.

December 30, 1980

BSP:  External  change:   The  default  timeouts  for   Puts,  PutMark,
PutInterrupt and BSPWriteBlock were changed from 'defaultTimeout' to '-
1' (infinity).   This makes the  'put' operations symmetrical  with the
'get' operations: so long as the other end of the connection  is alive,
the BSP will wait indefinitely to put or get a byte.   Recompilation of
client programs is not necessary.

January 25, 1981

BSP:   External   change:   optional   'sendNow'   argument   added  to
BSPForceOutput and BSPPutMark.  Recompilation of client programs is not

Pup Package                November 21, 1981                         35

November 21, 1981

Level  1:  External  change:  optional  "transient"  argument  added to

NameLookup: External change: a new module PupNetDirLookup  provides the
same functions as PupNameLookup (which still exists),  and additionally
contains  new  procedures  EnumeratePupAddresses  and PupAddressLookup.
Recompilation of client programs is not necessary.