[ih] Ping Eduardo A. Suárez (was Re: What is the origin of the root account?)

[Jack Haverty]

Tony,

Thanks for that link!  I downloaded the book and it appears to be the
kind of content I remember (level of detail about kernel innards).
That plus the source code was enough to start the project to create a
TCP implementation back in 1977.

What I recall using wasn't a book, but more like a set of notes for a
class or tutorial.  That correlates with the book, which says in the
introduction that the book is the descendant of class notes for an
operating system course taught in 1976-77.  I probably had a copy of
those notes, which ARPA had somehow obtained.   I don't remember that
Australia was on the ARPANET for FTPing.  The Unix kernel code came
from ATT of course, through ARPA.  But it pretty much matched the code
described in Lions material.

I thought it was "University of Wollongong", but University of New
South Wales is probably the right source.   Hey, at least I remembered
the right continent..... Ahah, a little googling reveals that
University of Woolongong is in New South Wales, Australia and seems to
be a subsidiary of University of NSW.

/Jack

PS - Since this is the "internet history" mailing list, perhaps I
should capture a bit of the history of the Internet and Unix, since I
was there when the two came together.  So, while I still remember,
here's some more details in case someone's ever interested in the
collision of Unix and TCP at the start of The Internet.

As I said in an earlier message, I got the assignment to create a TCP
running on a PDP-11/40 under Unix, sometime in the second half of
1977.   That TCP was a "version 2.5" TCP, which I implemented on that
11/40 and subsequently evolved to TCP4.  The work was done under one
of Vint's contracts at ARPA, as I believe were most or maybe all of
the other implementations.   Postel's report on the first "TCP
Bakeoff" is a good reference to identify the set of early
implementations that first managed to talk with each other rather than
just themselves.

The PDP-11/40 ran a variant of Unix V6 -- e.g., it had the "Rand
ports" extensions.  That particular model PDP11 was very memory
constrained - 32K of address space.  So the whole kernel, instructions
and data, had to fit in 32K.  Other models, e.g., PDP11/45 and
PDP11/70, had twice the memory address space, by "i/d separation"
which put instructions and data into separate address spaces.  But the
PDP11/40 had no "elbow room".   Definitely coach class networking.

Randy Rettberg and I, both at BBN, took the TCP/Unix challenge.  We
were both Unix neophytes.  After figuring out what we could (Lion's
notes were a great help), we still didn't see any clean way to
construct the common kinds of network programs inside the Unix
environment.  In particular, it didn't seem possible to write a
program that could serve a duplex information flow, where you couldn't
predict from which direction the next piece of data would come.  I.E.,
when the program was ready to go into an idle state and wait for more
work to do, you could issue a "read" call to the kernel, specifying a
file descriptor, and it would hang until data was available from that
"file".  But if you picked the "wrong" fd to wait on for input, your
program would wait forever.  How would a "telnet" program, for
example, know whether its local human user would type another
character next, or its remote partner across the net would send the
next character for output to that user terminal.   There may have been
a way to do this in Unix of the era, but we neophytes couldn't see it.
 Networking didn't seem to fit the Unix "concatenation of pipes"
paradigm where input flows unidirectionally to output.

We invented a very, very simple mechanism to enable a process to wait
on any of several file descriptors, and to also determine how much
could be read or written without causing the system call to hang
waiting for more data than what was already in the kernel buffers.
Those were the AWAIT and CAPAC system calls, which we added to the
kernel.   There was actually a paper about this in 1978 -- J. F.
Haverty, R. D. Rettberg, “Inter-process Communication for a Server in
UNIX," Proceedings Compcon 78, September 1978, pp. 312-315.   With
AWAIT and CAPAC added to the kernel, it was possible to then write
networking software.  Later primitives, e.g., "sockets", provided
similar mechanisms but with richer functionality.

Adding those primitives to the kernel was a real challenge.  The
kernel memory was full, at least with the 32K limitation of the 11/40.
  Adding any new functionality meant you had to remove something else
to make room, or find some place to optimize and squeeze out a few
words of space.   The guys at Bell Labs were very good coders -- not
much fat to trim.   I recall poring through the kernel listing,
searching for places to optimize, and mostly finding space by taking
out some "panic" code --- code that checked something and halted the
processor if things were bad.  You did what you had to do....and this
is why the AWAIT/CAPAC primitives were so primitive -- absolute
minimum new kernel code.

After struggling with AWAIT and CAPAC, which had to be in the kernel,
it was pretty clear that there was no way to shoehorn a TCP
implementation in there too.  So the TCP itself also had to be in user
space - a separate user process that communicated with the kernel to
interact with the ARPANET/1822 hardware in a full-duplex fashion, and
communicated full-duplex with TCP user's processes (e.g., a Telnet
program) by using multiple Rand ports.

I started with Jim Mathis' TCP implementation for MOS that was in use
on LSI11 systems.  It was written in Macro-11, so it was compatible
with the PDP11/40, and "simply" had to be restructured to fit in the
Unix world and then changed as we changed the TCP definition.  That's
what I did.  This all happened in the late 1977 timeframe, while
others were also working on TCPs -- Bill Plummer, Bob Braden, Dave
Clark, et al.  We were also simultaneously changing the definition of
TCP, e.g., splitting into TCP and IP, changing header formats and
state diagrams, etc., as part of going from TCP2 to TCP4 through many
intermediate stages.

Life was not wonderful though.  I recall getting the 11/40 TCP finally
to the state that it could open a connection, to itself, and send
data.  So I rigged up a quick performance test, sending a large
convenient text file (probably the source code) through a TCP
connection, looking at my watch, and then dividing to compute the
throughput.

That first TCP was blazing away at an average of 11 bits/second ....
yes, bits.   I did the math twice.  Embarassing.  It couldn't keep a
model 33 teletype busy.  I could write good code, or so I thought.

More diving into the system to see where the time was going.
Profiling indicated that more than 95% of the time was spent inside
system calls involving I/O through pipes/ports.  Making my code
infinitely efficient could only hope to get a 5% improvement.  So it
was back into the Unix kernel listing to see what was happening.

After much poking around, I remember finding the offending code.   I
can't recall whether it was pipes or ports or both, but the
implementation of that mechanism was basically a tiny wrapper around
the general file I/O code.  A pipe/port was essentially a standard
file, with a "read pointer" and a "write pointer" showing where the
input and output was stopped at the moment.  A bit of code made sure
the reader never got in front of the writer, and another bit of code
held both sides up when the file hit a certain length (4096 bytes
IIRC); when the reader caught the writer at that position, the file
was truncated back to 0 length and I/O resumed from there.  It was
basically just a 4K FIFO, with a file descriptor attached to each end
and "control" that every 4K stopped the writer to wait for the reader
to catch up and then clear the FIFO.

The problem was that, since it was built on top of the regular file
system, the rest of the system didn't know that the underlying file
was about to be truncated.  There was no notion of "truncating" a
file.  So the kernel viewed that 4K of file data as being "dirty" and
in need of writing out to the physical disk before allowing any
further activity on that file.  So all network traffic had to be
written to disk as well.  With the limited physical memory it was
maybe even taking detours to the swap file.  We had a slow "cartridge"
disk.

Result -- 11 bits per second TCP performance.

Some more kernel hacking and "panic removal" made some space to make
the pipe/port mechanism somewhat more efficient, and got the TCP to
the point that we could use it in the projects which needed it.

Subsequently we argued, successfully, that a PDP11/40 wasn't a good
choice for this kind of thing, and the newer /45 and /70 were better.
In those machines, there was a lot more space - a whole additional 32K
for instructions and data, so it was feasible to put the TCP
implementation into the kernel.  As I recall Mike Wingfield and Al
Nemeth subsequently worked on that for the PDP-11/70, and Rob Gurwitz
for the Vax, all at BBN under various ARPA or DCA contracts.  The
Macro-11 user-space TCP that I wrote for Unix on the 11/40 was
thankfully and quickly abandoned.

And that's the way it was, circa 1977-78 in the early days of The
Internet and the Unix system...

Hope this helps some Internet and Unix historians,
/Jack Haverty
April 17, 2013






On Wed, Apr 17, 2013 at 3:37 AM, Tony Finch <dot at dotat.at> wrote:
> Jack Haverty <jack at 3kitty.org> wrote:
>>
>> The only document about Unix internals I recall finding (in 1978) was
>> from the University of Wollongong (Australia), where someone had
>> written up a nice description of the architecture of the kernel and
>> the software structure, data, etc.  Very, very helpful in getting that
>> TCP running.   I guess Wollongong was far enough away from AT&T to not
>> be worried.
>
> Are you referring to the Lions book?
> http://www.lemis.com/grog/Documentation/Lions/
>
> Tony.
> --
> f.anthony.n.finch  <dot at dotat.at>  http://dotat.at/
> Forties, Cromarty: East, veering southeast, 4 or 5, occasionally 6 at first.
> Rough, becoming slight or moderate. Showers, rain at first. Moderate or good,
> occasionally poor at first.