[TUHS] History of select(2)

[TUHS] History of select(2)

[Noel Chiappa]

    > From: Johnny Billquist <bqt at softjar.se>

    > And RFC791 is dated September 1981.

Yes, but it had pretty much only editorial changes from RFC-760, dated January
1980 (almost two years before), and from a number of IEN's dated even earlier
than that (which I'm too lazy to paw through).

    > So I have this problem with people who say that they implemented TC/IP
    > in 1978 for some reason.

If you look at IEN-44, June 1978 (issued shortly after the fateful June 15-16
meeting, where the awful 32-bit address decision was taken), you will see that
the packet format as of that date was pretty much what we have today (the
format of addresses kept changing for many years, but I'll put that aside for
now).

    > Especially if they say ... it was working well in heterogeneous
    > networks.

TCP/IP didn't work "well" for a long time after 1981 - until we got the
congestion control stuff worked out in the late 80's. And IIRC the routing/
addressing stuff took even longer.

    > I don't think it's correct to say that it was TCP/IP, as we know it
    > today.

Why not? A box implementing the June '78 spec would probably talk to a current
one (as long as suitable addresses were used on each end).

    > It was either some other protocol (like NCP) or some other version of
    > IP, which was not even published as an RFC.

Nope. And don't put too much weight on the RFC part - TCP/IP stuff didn't
start getting published as RFC's until it was _done_ (i.e. ready for the
ARPANet to convert from NCP to TCP/IP - which happened January 1, 1983).

All work prior to TCP/IP being declared 'done' is documented in IEN's (very
similar documents to RFC's, distributed by the exact same person - Jon
Postel).

	Noel

[TUHS] History of select(2)

[Johnny Billquist]

On 2017-01-15 00:43, Noel Chiappa wrote:
>     > From: Johnny Billquist <bqt at softjar.se>
>
>     > And RFC791 is dated September 1981.
>
> Yes, but it had pretty much only editorial changes from RFC-760, dated January
> 1980 (almost two years before), and from a number of IEN's dated even earlier
> than that (which I'm too lazy to paw through).

Like I pointed out, RFC760 lacks ICMP. Error messaging was supposed to 
be carried in IP options. That is more than an editorial change.

>     > So I have this problem with people who say that they implemented TC/IP
>     > in 1978 for some reason.
>
> If you look at IEN-44, June 1978 (issued shortly after the fateful June 15-16
> meeting, where the awful 32-bit address decision was taken), you will see that
> the packet format as of that date was pretty much what we have today (the
> format of addresses kept changing for many years, but I'll put that aside for
> now).

Packet format, yes. Semantics and operations differed. ICMP didn't even 
exist.

>     > Especially if they say ... it was working well in heterogeneous
>     > networks.
>
> TCP/IP didn't work "well" for a long time after 1981 - until we got the
> congestion control stuff worked out in the late 80's. And IIRC the routing/
> addressing stuff took even longer.

Depending on how you defined "well", people might still argue about 
that. :-)

>     > I don't think it's correct to say that it was TCP/IP, as we know it
>     > today.
>
> Why not? A box implementing the June '78 spec would probably talk to a current
> one (as long as suitable addresses were used on each end).

I would seriously question that, if nothing based on just my comments 
about ICMP above.

Anyway, let's dig a bit more then, shall we...

RFC 762 is "Assigned numbers". There you will find that the IP version 
field in the IP header values. Version 4 was defined in August 1979, 
with a reference to: "Postel, J. "DOD Standard Internet Protocol," 
IEN-128, USC/Information Sciences Institute, January 1980."

Which also makes one question how anyone would have known about IPv4 in 
1978.

Also, first definition of TCP shows up in RFC 761, which is also 
IEN-129. And that is the DoD standard. Also dated January 1980.

Another rather interesting document is RFC 801, which lists the current 
status of TCP/IP implementations in appendix D. This document is from 
November 1981, and there it is clearly stated which implementations 
exist at that point (that the authors know about). And it's for the most 
part very much "work in progress". And this is at the end of 1981...

So yes, I still have problems with claims that they had it all running 
in 1978. :-)

>     > It was either some other protocol (like NCP) or some other version of
>     > IP, which was not even published as an RFC.
>
> Nope. And don't put too much weight on the RFC part - TCP/IP stuff didn't
> start getting published as RFC's until it was _done_ (i.e. ready for the
> ARPANet to convert from NCP to TCP/IP - which happened January 1, 1983).

I don't really agree with your view on the RFCs here. :-)

> All work prior to TCP/IP being declared 'done' is documented in IEN's (very
> similar documents to RFC's, distributed by the exact same person - Jon
> Postel).

Yes, except of course, those documents aren't really that much earlier 
in some cases, like ones I pointed out above, which I think are most 
relevant here...

	Johnny

-- 
Johnny Billquist                  || "I'm on a bus
                                   ||  on a psychedelic trip
email: bqt at softjar.se             ||  Reading murder books
pdp is alive!                     ||  tryin' to stay hip" - B. Idol

[TUHS] History of select(2)

[Johnny Billquist]

On 2017-01-14 23:02, Johnny Billquist wrote:
> On 2017-01-13 18:57, Paul Ruizendaal <pnr at planet.nl> wrote:
>>
>> On 12 Jan 2017, at 4:54 , Clem Cole wrote:
>>
>>> The point is that while I have no memory of capac(), but I can
>>> confirm that I definitely programmed with the empty() system call and
>>> Rand ports on a v6 based kernel in the mid-1970s and that it was
>>> definitely at places besides Rand themselves.
>> Thank you for confirming that. If anybody knows of surviving source
>> for these extensions I'd love to hear about it. Although the
>> description in the implementation report is clear enough to recreate
>> it (it would seem to be one file similar to pipe.c and a pseudo device
>> driver similar in size to mem.c), original code is better. It is also
>> possible that the code in pipe.c was modified to drive both pipes and
>> ports -- there would have been a lot of similarity between the two,
>> and kernel space was at a premium.
>>
>>> [...] confirming something I have been saying for few years and some
>>> people have had a hard time believing. The specifications for what
>>> would become IP and TCP were kicking around the ARPAnet in the late
>>> 1970s.
>> My understanding is that all RFC's and IEN's were available to all
>> legit users of the Arpanet. By 1979 there were 90 nodes (IMP's) and
>> about 200 hosts connected. I don't get the impression that stuff was
>> always easy to find, with Postel making a few posts about putting
>> together "protocol information binders". Apparently nobody had the
>> idea to put all RFC's in a directory and give FTP access to it.
>
> They were, and still are. And I suspect Clem is thinking of me, as I
> constantly question his memory on this subject.
>
> The problem is that all the RFCs are available, and they are later than
> this. The ARPAnet existed in 1979, but it was not using TCP/IP. If you
> look at the early drafts of TCP/IP, from around 1980-1981, you will also
> see that there are significant differences compared to the TCP/IP we
> know today. There was no ICMP, for example. Error handling and passing
> around looked different.
> IMPs did not talk IP, just for the record.
>
> RFC760 defines IPv4, and is dated January 1980. It refers to some
> previous documents that describe IP, but they are not RFCs. Also, if you
> look at RFC760, you will see that errors were supposed to be handled
> through options in the packet header, and that IP addresses, while 32
> bits, were just split into 8 bits for network number, and 24 bits for
> host. There were obviously still some work needed before we got to what
> people think on IPv4 today. Anyone implementing RFC760 would probably
> not work at all with an IPv4 implementation that exist today.

I should have also said that RFC791 is where IPv4 pretty much becomes 
what we can recognize, and what will probably work against other 
machines today.
And RFC791 is dated September 1981.

So I have this problem with people who say that they implemented TC/IP 
in 1978 for some reason. :-) Especially if they say they followed some 
RFC, and it was working well in heterogeneous networks.

I don't want to claim that people didn't do the networking, but I don't 
think it's correct to say that it was TCP/IP, as we know it today. It 
was either some other protocol (like NCP) or some other version of IP, 
which was not even published as an RFC.

Or else the RFCs in the IETF archives have been falsified with regards 
to their dates.

	Johnny

-- 
Johnny Billquist                  || "I'm on a bus
                                   ||  on a psychedelic trip
email: bqt at softjar.se             ||  Reading murder books
pdp is alive!                     ||  tryin' to stay hip" - B. Idol

[TUHS] History of select(2)

[Johnny Billquist]

On 2017-01-13 18:57, Paul Ruizendaal <pnr at planet.nl> wrote:
>
> On 12 Jan 2017, at 4:54 , Clem Cole wrote:
>
>> The point is that while I have no memory of capac(), but I can confirm that I definitely programmed with the empty() system call and Rand ports on a v6 based kernel in the mid-1970s and that it was definitely at places besides Rand themselves.
> Thank you for confirming that. If anybody knows of surviving source for these extensions I'd love to hear about it. Although the description in the implementation report is clear enough to recreate it (it would seem to be one file similar to pipe.c and a pseudo device driver similar in size to mem.c), original code is better. It is also possible that the code in pipe.c was modified to drive both pipes and ports -- there would have been a lot of similarity between the two, and kernel space was at a premium.
>
>> [...] confirming something I have been saying for few years and some people have had a hard time believing. The specifications for what would become IP and TCP were kicking around the ARPAnet in the late 1970s.
> My understanding is that all RFC's and IEN's were available to all legit users of the Arpanet. By 1979 there were 90 nodes (IMP's) and about 200 hosts connected. I don't get the impression that stuff was always easy to find, with Postel making a few posts about putting together "protocol information binders". Apparently nobody had the idea to put all RFC's in a directory and give FTP access to it.

They were, and still are. And I suspect Clem is thinking of me, as I 
constantly question his memory on this subject.

The problem is that all the RFCs are available, and they are later than 
this. The ARPAnet existed in 1979, but it was not using TCP/IP. If you 
look at the early drafts of TCP/IP, from around 1980-1981, you will also 
see that there are significant differences compared to the TCP/IP we 
know today. There was no ICMP, for example. Error handling and passing 
around looked different.
IMPs did not talk IP, just for the record.

RFC760 defines IPv4, and is dated January 1980. It refers to some 
previous documents that describe IP, but they are not RFCs. Also, if you 
look at RFC760, you will see that errors were supposed to be handled 
through options in the packet header, and that IP addresses, while 32 
bits, were just split into 8 bits for network number, and 24 bits for 
host. There were obviously still some work needed before we got to what 
people think on IPv4 today. Anyone implementing RFC760 would probably 
not work at all with an IPv4 implementation that exist today.

> I am not sure how available this stuff was outside the Arpanet community. I think I should put a question out about this, over on the internet history mailing list.
>
> As an aside: IMHO, conceptually the difference between NCP and TCP wasn't all that big. In my current understanding the big difference was that NCP assumes in-order, reliable delivery of packets (as was the case between IMP's) and that TCP allows for unreliable links. Otherwise, the connection build-up and tear-down and the flow control were similar. See for instance RFC54 and RFC55 from 1970. My point is: yes, these concepts were kicking around for over a decade in academia before BSD.

Not sure if BSD is a good reference point. Much stuff was not actually 
done on Unix systems at all, if you start reading machine lists in the 
early RFCs. Unix had this UUCP thingy, that they liked. ;-) BSD and 
networking research came more to the front doing all the refinements 
over the years.

Anyway, yes, for sure TCP did not come out of the void. It was based on 
earlier work. But there are some significant differences between TCP/IP 
and NCP, which is why you had the big switch day.

	Johnny

-- 
Johnny Billquist                  || "I'm on a bus
                                   ||  on a psychedelic trip
email: bqt at softjar.se             ||  Reading murder books
pdp is alive!                     ||  tryin' to stay hip" - B. Idol

[TUHS] History of select(2)

[Nelson H. F. Beebe]

Paul Ruizendaal <pnr at planet.nl> writes today at Fri, 13 Jan 2017 10:13:47 +0100:

>> By 1979 there were 90 nodes (IMP's) and about 200 hosts connected.

I just checked my archives of our TOPS-20 PDP-10 filesystem (retired
31-Oct-1990); the oldests hosts.txt file has a filesystem timestamp of
30-Apr-1986, with 3210 lines, of which 3124 are hostnames (98 of them
at the University of Utah).  The comment header says

	; DoD Internet Host Table
	;  28-Apr-86
	;  Version number 534

If someone / some site wishes to collect hosts.txt generations for a
historical record, let me know offlist, and I'll supply a pointer to a
copy of my file.  

Sadly, it looks like we just replaced PS:<SYSTEM>HOSTS.TXT with a new
generation from time to time, purging previous generations (a legacy
of the days when a washing-machine-sized 200MB disk drive and cabinet
cost US$15,000).


-------------------------------------------------------------------------------
- Nelson H. F. Beebe                    Tel: +1 801 581 5254                  -
- University of Utah                    FAX: +1 801 581 4148                  -
- Department of Mathematics, 110 LCB    Internet e-mail: beebe at math.utah.edu  -
- 155 S 1400 E RM 233                       beebe at acm.org  beebe at computer.org -
- Salt Lake City, UT 84112-0090, USA    URL: http://www.math.utah.edu/~beebe/ -
-------------------------------------------------------------------------------

[TUHS] History of select(2)

[Ron Natalie]

I have in a box somewhere a printed copy of the TCP/IP protocol book printed
by SRI.  It's about 3" thick and has the essential protocol RFCs needed at
the time the Arpanet went TCP/IP.   Another slightly smaller one had the
mail RFCs in it.    Almost anybody who was working with these things had
copies of these things on their desk.

Understand that these networks were slow compared to modern standards.
FTPing down that much data wasn't something you did casually.    My mind is
hazy about where the RFPs were archived before the cut over but afterward
they most certainly were in the FTP directory at the SRI-NIC host.   This
was also where you downloaded the host table (though a later RFC made a
non-FTP transfer available as well).

An amusing historical tidbit on the host tables.    The table had entries
that looked like this:
    HOST : 10.0.0.73 : SRI-NIC,NIC : FOONLY-F3 : TENEX :NCP/TELNET,NCP/FTP,
TCP/TELNET, TCP/FTP :

Where you had the IP address, the names for the host, the hardware type, the
OS, and a list of supported protocols.

Now the BSD network code had their own format for /etc/hosts.    A small
yacc program was used to convert the above format to /etc/hosts.    Then a
routine, then just called rhost would look up in /etc/hosts.

Now I thought this was silly.   So the BRL machines just used hosts.txt
directly.   I modified rhost read it without the intermediary hosts.txt.
To accomplish this I went to the appropriate RFC for the file format and
implemented my own little parser.

Now one day, we got our first networked attached laser printer.    We named
it BRL-ZAP and for a CPU type I just put down 68000.   This was a legitimate
thing to put in the host table.   Well, my parser read it fine as did the
TENEX and other parsers, but there was an error in the yacc grammar on the
BSD machines.   Every UNIX system on the net (other than mine) gagged trying
to parse the BRL-ZAP entry.    When people complained I pointed out that
using yacc was pretty silly.   That, gee, there might be some other
important files on UNIX that uses a bunch of fields separated by colons
first and then commas (/etc/passwd) and nobody had felt it necessary to
write a yacc grammar to interpret those.     There was a strong feeling that
I did this on purpose (the fact that I called the machine ZAP didn't help,
but ZAPPING was what we called printing on the laser printers compared to
the mechanical printers back then).

[TUHS] History of select(2)

[Paul Ruizendaal]

On 12 Jan 2017, at 4:54 , Clem Cole wrote:

> Paul -- this is a great stuff and fills in some pieces of my memories.

Thanks!

> The point is that while I have no memory of capac(), but I can confirm that I definitely programmed with the empty() system call and Rand ports on a v6 based kernel in the mid-1970s and that it was definitely at places besides Rand themselves.

Thank you for confirming that. If anybody knows of surviving source for these extensions I'd love to hear about it. Although the description in the implementation report is clear enough to recreate it (it would seem to be one file similar to pipe.c and a pseudo device driver similar in size to mem.c), original code is better. It is also possible that the code in pipe.c was modified to drive both pipes and ports -- there would have been a lot of similarity between the two, and kernel space was at a premium.

> [...] confirming something I have been saying for few years and some people have had a hard time believing. The specifications for what would become IP and TCP were kicking around the ARPAnet in the late 1970s.

My understanding is that all RFC's and IEN's were available to all legit users of the Arpanet. By 1979 there were 90 nodes (IMP's) and about 200 hosts connected. I don't get the impression that stuff was always easy to find, with Postel making a few posts about putting together "protocol information binders". Apparently nobody had the idea to put all RFC's in a directory and give FTP access to it.

I am not sure how available this stuff was outside the Arpanet community. I think I should put a question out about this, over on the internet history mailing list.

As an aside: IMHO, conceptually the difference between NCP and TCP wasn't all that big. In my current understanding the big difference was that NCP assumes in-order, reliable delivery of packets (as was the case between IMP's) and that TCP allows for unreliable links. Otherwise, the connection build-up and tear-down and the flow control were similar. See for instance RFC54 and RFC55 from 1970. My point is: yes, these concepts were kicking around for over a decade in academia before BSD.

Paul

[TUHS] History of select(2)

[Clem Cole]

Paul -- this is a great stuff and fills in some pieces of my memories.


FYI:   CMU had the the Rand Ports code including empty() in some
implementations of kernels in use in the mid 1970s.   The later UNIX cu(1)
program did not exist, and a couple of people hacked together a program
called "connect" which was used to connect between serial ports for
downloading PPT images to microprocessors such as a KIM-1 and communicating
with it.   I say a "couple of people," because I do not remember who wrote
the original version.   It could have been a number of us.  I know I hacked
on it a good bit, as did others over the course of time (and we did not use
source control in those days).   The sources were there for all to work
with and we all added stuff as we though of things that would help us out.


Anyway, besides microprocessor support, we also used connect(1) to
"front-end" the serial lines from the PDP-10's in CS and were doing some
rudimentary networking stuff over parallel DR-11C's, in the pre-TCP/IP
world [a discussion a couple of us have had separately - more in a minute].
  But the point is that the dates line up with my being there and what we
were doing at the time.  One version of connect(1) used the empty() system
call and Rand ports to do its thing.    I also remember reading the
connect(1) code as an early education in network technology and concepts.
We would later take hunks of into a TCP stack [3-4 years later Phil Karn
would write the infamous KA9Q TCP stack and a few years later, Stan Smith
and I would write the VMS TCP etc in BLISS but it model on some C network
stuff from CMU... -- amazing circle].

Anyway, around the same time (either sept 76 or 77 would be my guess) the
late Ted Kowalski came to CMU for his OYOC time (I've forgotten which it
was to be honest) and brought a pre-UNIX/TS system with him - TS begat V7.
Ted brought that system up on the 11/34 in EE and I remember connect(1) was
the most important program that immediately broke.   I also remember a
large argument between Ted and one of the other hackers (I've forgotten
whom), Ted saying we did not need it, it was wasteful, etc... and not in
the official editions.   I remember he re-implemented the connect(1)
program one night with multiple process and EE systems were from them on
based on Ted's system [although, I would later get to know Chesson and Greg
would give me the mpx() code a year or two later for some networking stuff
I would work on but that is a different story].

The point is that while I have no memory of capac(), but I can confirm that
I definitely programmed with the empty() system call and Rand ports on a v6
based kernel in the mid-1970s and that it was definitely at places besides
Rand themselves.

Another thing I want thank you  for it confirming something I have been
saying for  few years and some people have had a hard time believing.   The
specifications for what would become IP and TCP were kicking around the
ARPAnet in the late 1970s.   We definitely had them at CMU and that's where
I first was introduced to them, long before the planned cut over in the
early 1980s.   I probably was not aware of the global politics involved
outside of the ARPA community because I certainly thought at the time IP
was we were headed and it was what we were thinking about and considering
how to implement.

Anyway - thanks again for a great piece of hunt up some good stuff.

Clem

On Mon, Jan 9, 2017 at 2:36 AM, Paul Ruizendaal <pnr at planet.nl> wrote:

> On 9 Jan 2017, at 3:35 , Warren Toomey wrote:
>
> > Also, I came across this history of select(2) a while back:
> >
> > https://idea.popcount.org/2016-11-01-a-brief-history-of-select2/
> >
> > Cheers, Warren
>
> That is an interesting blog post, but I think it is a bit short on the
> history of things before 4.2BSD. Below my current understanding of what
> came before select().
>
> In March 1975 the first networked Unix was created at the University of
> Illinois, initially based on 5th edition, but soon ported to 6th edition.
> It is described in RFC681 and a paper by Greg Chesson. Note that UoI was
> the very first Unix licensee. Its primary authors were Steve Holmgren,
> Steve Bunch and Gary Grossman. Greg Chesson was also involved. Grossman had
> already done two earlier Arpanet implementations (the ANTS and ANTS II
> systems) on bare metal and had a deep understanding of what a good
> implementation needed.
>
> Their implementation was compact (about a thousand lines added to the
> kernel, and another thousand in the connection daemon) and - I'm my opinion
> at least - conceptually well integrated into the existing file API. It
> became the leading Unix Arpanet implementation with wide use from 1975 to
> 1981. Two things stand out: (i) no accept(); and (ii) no select(). The
> original authors are still with us, with the exception of Greg, and I asked
> for their input as well.
>
> (i) no accept()
>
> Listening sockets worked a bit different from today. If one opened a
> listening socket it would not return a descriptor but block instead; when a
> connection was made it would return with the listening socket now bound to
> the new connection. Server applications would open a listening socket and
> do a double fork for the client connection (i.e. getting process 1 as its
> parent); the main process would loop around and open a new listening socket
> (this can all be verified in surviving application sources). According to
> Steve Holmgren this was not perceived as a big problem at the time. Network
> speeds were still so low that the brief gap in listening did not matter
> much, and the double fork was just a few lines of code.
>
> This changed when the CSRG team moved from a long-haul, Arpanet, 56Kb/s
> context to a local, Ethernet, 3Mb/s context and Sam Leffler came up with
> the concept of accept(). In 4.1a BSD and 2.9BSD the queue of pending
> connections was fixed (possibly 1, I have to check). In 4.1c BSD listen()
> was introduced; before then whether a socket was active or listening was a
> flag to opening the socket. The second parameter to listen() specified the
> maximum number of pending connections [as an aside, note that I'm using
> 'socket' in the BSD sense; the term socket changed meaning several times
> between 1973 and 1983].
>
> (ii) no select()
>
> This was the real pain (Holmgren reconfirmed that). This is what Dennis
> must have referred to in his retrospect paper. Various solutions were
> thought of, but in Network Unix the model remained using separate processes
> for simultaneous reading and writing. Progress in this area came from two
> other places involved in Unix and Arpanet: Rand and BBN.
>
> In 1977 Rand was taking on this problem (see
> http://www.dtic.mil/dtic/tr/fulltext/u2/a044200.pdf and
> http://www.dtic.mil/dtic/tr/fulltext/u2/a044201.pdf). They considered a
> solution with a new system call 'empty()' that would tell if there was any
> data available on a file descriptor, a crude form of non-blocking I/O if
> you like. As this would consume precious CPU cycles it proved inadequate.
> Instead they came up with "ports". A port was a (possibly named) pipe with
> multiple writers and a single reader, and it was created with a 'port()'
> system call. The reader would see each write preceded by a header block
> identifying the reader. The implementation (see second PDF) was simple,
> apparently only taking 200 words of kernel code. Rand ports are a
> simplistic version of the 'mpx' facility done by Greg Chesson at Bell Labs
> (in 1978?). I am not sure whether this was independent invention or that
> Greg was aware of Rand ports. Unfortunately we cannot ask him anymore.
>
> Later in 1977, over at BBN, Jack Haverty was doing an experimental TCP/IP
> stack for Unix (this was TCP 2.5, not TCP 4). He had a working stack
> written in PDP11 assembler for a different OS and was making this run on
> Unix. He was using Rand ports to connect clients to the network stack, but
> still lacked the required primitives to make this work properly. So he came
> up with the await() system call, a direct precursor to select(). It is
> documented in BBN report 3911 (http://bit.ly/2iU1TNK), including man
> pages. With the awtenb() and awtdis() one would manage the monitored
> descriptors (like the bit vectors going into a select), and await() would
> then wait for an event or time out.
>
> Related to this was the capac() system call, to get the 'capacity' of a
> descriptor. This returns the amount of data that can safely be written to
> or read from a descriptor. I suppose it is an improved version of empty().
> There is no equivalent of that in the later BSD sockets, perhaps because
> non-blocking I/O in the current sense was about to arrive. With port(),
> await() and capac() it becomes possible to write single threaded network
> programs.
>
> An example may be found here, the first TCP/IP (version 4) stack in C for
> Unix, from early 1979: http://digital2.library.ucla.e
> du/viewItem.do?ark=21198/zz002gvzqg (scroll down past IMP stuff). It's
> documented in IEN98 (https://www.rfc-editor.org/ien/ien98.txt). I'm
> currently retyping this source so that it can be better studied.
>
> The await() call is not in the TCP/IP code done for 4.1 BSD by BBN. I'm
> puzzled by this as it is evidently useful and Jack Haverty and Rob Gurwitz
> worked in the same corridor at BBN at the time. In 4.1a the select() call
> appears and it seems to be an improved version of await(), with the need
> for awtenb() en awtdis() replaced by the use of bit vectors. I am not sure
> if Bill Joy was aware of await() or whether it was independent invention.
> Here we can ask, but I have no contact details.
>
> Hope the above is of interest. I'm still learning new things about these
> topics every day, so please advise if my above understanding is wrong.
>
>
> As a side note, I am still looking for:
>
> - surviving copies of UoI "Network Unix" (I'm currently no further than
> papers and bits of source that lingered in other code bases)
>
> - surviving copies of the 4.1a BSD distribution tape (Kirk McKusick's tape
> was damaged)
>
> - surviving source of the kernel code of port(), await() and capac();
> (could possibly be recreated from documentation)
>
> Any and all help very much appreciated.
>
> Paul
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20170111/5e07d4e9/attachment.html>

[TUHS] History of select(2)

[Warren Toomey]

> On 9 Jan 2017, at 3:35 , Warren Toomey wrote:
> > Also, I came across this history of select(2) a while back:
> > https://idea.popcount.org/2016-11-01-a-brief-history-of-select2/

On Mon, Jan 09, 2017 at 11:36:20AM +0100, Paul Ruizendaal wrote:
> That is an interesting blog post, but I think it is a bit short on the
> history of things before 4.2BSD. Below my current understanding of what
> came before select().

Wow, that's an excellent writeup of the early history of select(2).
Thanks Paul!
	Warren

[TUHS] History of select(2)

[Paul Ruizendaal]

On 9 Jan 2017, at 3:35 , Warren Toomey wrote:

> Also, I came across this history of select(2) a while back:
> 
> https://idea.popcount.org/2016-11-01-a-brief-history-of-select2/
> 
> Cheers, Warren

That is an interesting blog post, but I think it is a bit short on the history of things before 4.2BSD. Below my current understanding of what came before select().

In March 1975 the first networked Unix was created at the University of Illinois, initially based on 5th edition, but soon ported to 6th edition. It is described in RFC681 and a paper by Greg Chesson. Note that UoI was the very first Unix licensee. Its primary authors were Steve Holmgren, Steve Bunch and Gary Grossman. Greg Chesson was also involved. Grossman had already done two earlier Arpanet implementations (the ANTS and ANTS II systems) on bare metal and had a deep understanding of what a good implementation needed.

Their implementation was compact (about a thousand lines added to the kernel, and another thousand in the connection daemon) and - I'm my opinion at least - conceptually well integrated into the existing file API. It became the leading Unix Arpanet implementation with wide use from 1975 to 1981. Two things stand out: (i) no accept(); and (ii) no select(). The original authors are still with us, with the exception of Greg, and I asked for their input as well.

(i) no accept()

Listening sockets worked a bit different from today. If one opened a listening socket it would not return a descriptor but block instead; when a connection was made it would return with the listening socket now bound to the new connection. Server applications would open a listening socket and do a double fork for the client connection (i.e. getting process 1 as its parent); the main process would loop around and open a new listening socket (this can all be verified in surviving application sources). According to Steve Holmgren this was not perceived as a big problem at the time. Network speeds were still so low that the brief gap in listening did not matter much, and the double fork was just a few lines of code.

This changed when the CSRG team moved from a long-haul, Arpanet, 56Kb/s context to a local, Ethernet, 3Mb/s context and Sam Leffler came up with the concept of accept(). In 4.1a BSD and 2.9BSD the queue of pending connections was fixed (possibly 1, I have to check). In 4.1c BSD listen() was introduced; before then whether a socket was active or listening was a flag to opening the socket. The second parameter to listen() specified the maximum number of pending connections [as an aside, note that I'm using 'socket' in the BSD sense; the term socket changed meaning several times between 1973 and 1983].

(ii) no select()

This was the real pain (Holmgren reconfirmed that). This is what Dennis must have referred to in his retrospect paper. Various solutions were thought of, but in Network Unix the model remained using separate processes for simultaneous reading and writing. Progress in this area came from two other places involved in Unix and Arpanet: Rand and BBN.

In 1977 Rand was taking on this problem (see http://www.dtic.mil/dtic/tr/fulltext/u2/a044200.pdf and http://www.dtic.mil/dtic/tr/fulltext/u2/a044201.pdf). They considered a  solution with a new system call 'empty()' that would tell if there was any data available on a file descriptor, a crude form of non-blocking I/O if you like. As this would consume precious CPU cycles it proved inadequate. Instead they came up with "ports". A port was a (possibly named) pipe with multiple writers and a single reader, and it was created with a 'port()' system call. The reader would see each write preceded by a header block identifying the reader. The implementation (see second PDF) was simple, apparently only taking 200 words of kernel code. Rand ports are a simplistic version of the 'mpx' facility done by Greg Chesson at Bell Labs (in 1978?). I am not sure whether this was independent invention or that Greg was aware of Rand ports. Unfortunately we cannot ask him anymore.

Later in 1977, over at BBN, Jack Haverty was doing an experimental TCP/IP stack for Unix (this was TCP 2.5, not TCP 4). He had a working stack written in PDP11 assembler for a different OS and was making this run on Unix. He was using Rand ports to connect clients to the network stack, but still lacked the required primitives to make this work properly. So he came up with the await() system call, a direct precursor to select(). It is documented in BBN report 3911 (http://bit.ly/2iU1TNK), including man pages. With the awtenb() and awtdis() one would manage the monitored descriptors (like the bit vectors going into a select), and await() would then wait for an event or time out.

Related to this was the capac() system call, to get the 'capacity' of a descriptor. This returns the amount of data that can safely be written to or read from a descriptor. I suppose it is an improved version of empty(). There is no equivalent of that in the later BSD sockets, perhaps because non-blocking I/O in the current sense was about to arrive. With port(), await() and capac() it becomes possible to write single threaded network programs.

An example may be found here, the first TCP/IP (version 4) stack in C for Unix, from early 1979: http://digital2.library.ucla.edu/viewItem.do?ark=21198/zz002gvzqg (scroll down past IMP stuff). It's documented in IEN98 (https://www.rfc-editor.org/ien/ien98.txt). I'm currently retyping this source so that it can be better studied.

The await() call is not in the TCP/IP code done for 4.1 BSD by BBN. I'm puzzled by this as it is evidently useful and Jack Haverty and Rob Gurwitz worked in the same corridor at BBN at the time. In 4.1a the select() call appears and it seems to be an improved version of await(), with the need for awtenb() en awtdis() replaced by the use of bit vectors. I am not sure if Bill Joy was aware of await() or whether it was independent invention. Here we can ask, but I have no contact details.

Hope the above is of interest. I'm still learning new things about these topics every day, so please advise if my above understanding is wrong.


As a side note, I am still looking for:

- surviving copies of UoI "Network Unix" (I'm currently no further than papers and bits of source that lingered in other code bases)

- surviving copies of the 4.1a BSD distribution tape (Kirk McKusick's tape was damaged)

- surviving source of the kernel code of port(), await() and capac(); (could possibly be recreated from documentation)

Any and all help very much appreciated.

Paul

[TUHS] History of select(2)

[Warren Toomey]

Also, I came across this history of select(2) a while back:

https://idea.popcount.org/2016-11-01-a-brief-history-of-select2/

Cheers, Warren