[TUHS] Re: when did v8 or later get networking?

[TUHS] Re: when did v8 or later get networking?

[Paul Ruizendaal]

> Date: Thu, 10 Aug 2023 03:17:25 +0000
> From: segaloco
> 
>>>> TCP/IP, not datakit
> 
> 
> All of the files that have timestamps at the top list 83/07/29, except ip_input.c which has 83/08/16 instead.  The V8 version has _device (device driver) and _ld (line discipline) components that the 4.1cBSD code does not have.  Many other files have analogs between the two.  The byte ordering subroutines have been copied into a file, goo.s, from their home in 4.1cBSD in the C library (/usr/src/lib/libc/net/misc).  When this work originated someone else would need to answer, [...]

As far as I can tell the history of this code line goes back to 1977, when Jack Haverty at BBN wrote a TCP/IP library (porting earlier work written in PDP-11 assembler) for a slightly modified 6th Edition Unix. Fighting with 64KB core limits, throughput was horrific and he concluded that a bigger PDP-11 was needed. Mike Wingfield then did a re-implementation in C for a PDP-11/70. This worked in early 1979 and is arguably the first Unix TCP/IP stack that can still interoperate with current IPv4. However, it was still mostly a proof of concept user mode design (it was funded as a test vehicle for the later abandoned Autodin-II fork of TCP).

BBN then got a contract to write a kernel mode TCP/IP stack for 4BSD (“VAX TCP” in the old BBN doc’s). This work was performed by Rob Gurwitz under supervision of Jack Haverty. This stack - although all new code - still showed its heritage: it was designed as a loosely bound kernel process providing the NCP-Unix API. Some sources seem to imply that it was developed first as a user mode process and once working in that context changed into a kernel process / thread. Beta releases were available in 1981. It worked (and interoperates with modern IPv4), but in my experiments a few years back it turned out that it is difficult to get the scheduling for this kernel process right at higher system loads.

Bill Joy of CSRG concluded that the BBN stack did not perform according to his expectations. Note that CSRG was focused on usage over (thick) ethernet links, and BBN was focused on usage over Arpanet and other wide-area networks (with much lower bandwidth, and higher latency and error rates). He then in 1982 rewrote the stack to match the CSRG environment, changing the design to use software interrupts instead of a kernel thread and optimising the code (e.g. checksumming and fast code paths). It was a matter of debate how new the code was, with the extremes being that it was written from scratch using the spec versus it being mostly copied. Looking at it with a nearly 50 year distance, it seems in between: small bits of surviving SCCS suggest CSRG starting with parts of BBN code followed by rapid, massive modification; the end result is quite different but retained the ‘mbuf’ core data structure and a BBN bug (off-by-one for OOB TCP segments).

The shift from the NCP-Unix API to sockets is separate from this and was planned. CSRG had the contract to develop a new API for facilitating distributed systems with Unix and this gelled into the sockets interface. The first prototypes for this were done in 1981.

Nearly all of the above source is available in the TUHS online Unix Tree (Wingfield, VAX-TCP and two early versions from CSRG - one in 2.9BSD and one in 4.1cBSD).

[TUHS] Re: when did v8 or later get networking?

[Warner Losh]

[-- Attachment #1: Type: text/plain, Size: 2098 bytes --]

On Fri, Aug 11, 2023 at 3:05 AM Paul Ruizendaal <pnr@planet.nl> wrote:

> Bill Joy of CSRG concluded that the BBN stack did not perform according to
> his expectations. Note that CSRG was focused on usage over (thick) ethernet
> links, and BBN was focused on usage over Arpanet and other wide-area
> networks (with much lower bandwidth, and higher latency and error rates).
> He then in 1982 rewrote the stack to match the CSRG environment, changing
> the design to use software interrupts instead of a kernel thread and
> optimising the code (e.g. checksumming and fast code paths). It was a
> matter of debate how new the code was, with the extremes being that it was
> written from scratch using the spec versus it being mostly copied. Looking
> at it with a nearly 50 year distance, it seems in between: small bits of
> surviving SCCS suggest CSRG starting with parts of BBN code followed by
> rapid, massive modification; the end result is quite different but retained
> the ‘mbuf’ core data structure and a BBN bug (off-by-one for OOB TCP
> segments).
>

When Kirk McKusick tells  the story, UCB got a beta release (or early
access) of the BBN stack. UCB was supposed to add the socket interface to
whatever was there. But Bill Joy found it performed terribly (multiple
seconds to connect sometimes, single digit kB over 10Mb media, etc). He
optimized it to make it perform well. This was a combination of rewriting
chunks and tweaking other chunks, which matches your analysis of SCCS. When
BBN came back with their new, release ready stack Bill supposedly said
something like 'no thanks, we already got one that works way better.' This
is why much of the structure of the original BBN stack survived the
rewrite: if there wasn't a big issue with them, the design and mechanisms
wound up being conserved by this effort. It was too much work to move from
mbuf to something else, and too little gain.

I tried to find a good link, but they are in his BSD history retrospective
talks to differing degrees. Sorry I don't have an exact reference.

Warner

[-- Attachment #2: Type: text/html, Size: 2433 bytes --]

[TUHS] Re: when did v8 or later get networking?

[George Michaelson]

[-- Attachment #1: Type: text/plain, Size: 2919 bytes --]

Someone who worked at BBN told me they had no overhang budget for
improvements, they wrote code to fixed price contracts with DARPA and
'maybe we could do that better' was impossible without a second grant.

The butterfly we had at UCL had issues. No support worth writing home for.
Pre BGP routing was a bit of a disaster. Fixed size prefix tables and LRU
ejection. You could time out a telnet to the USA before the login: prompt
assuming you even had a route.

"Diamond" their SGML multimedia mailer was great, but a one-shot.

Smart people. Very focused on the bottom line.

(Apologies if this offends anyone ex BBN it's recollection of coffee room
gossip from 1985)

G

On Sat, 12 Aug 2023, 3:08 pm Warner Losh, <imp@bsdimp.com> wrote:

>
>
> On Fri, Aug 11, 2023 at 3:05 AM Paul Ruizendaal <pnr@planet.nl> wrote:
>
>> Bill Joy of CSRG concluded that the BBN stack did not perform according
>> to his expectations. Note that CSRG was focused on usage over (thick)
>> ethernet links, and BBN was focused on usage over Arpanet and other
>> wide-area networks (with much lower bandwidth, and higher latency and error
>> rates). He then in 1982 rewrote the stack to match the CSRG environment,
>> changing the design to use software interrupts instead of a kernel thread
>> and optimising the code (e.g. checksumming and fast code paths). It was a
>> matter of debate how new the code was, with the extremes being that it was
>> written from scratch using the spec versus it being mostly copied. Looking
>> at it with a nearly 50 year distance, it seems in between: small bits of
>> surviving SCCS suggest CSRG starting with parts of BBN code followed by
>> rapid, massive modification; the end result is quite different but retained
>> the ‘mbuf’ core data structure and a BBN bug (off-by-one for OOB TCP
>> segments).
>>
>
> When Kirk McKusick tells  the story, UCB got a beta release (or early
> access) of the BBN stack. UCB was supposed to add the socket interface to
> whatever was there. But Bill Joy found it performed terribly (multiple
> seconds to connect sometimes, single digit kB over 10Mb media, etc). He
> optimized it to make it perform well. This was a combination of rewriting
> chunks and tweaking other chunks, which matches your analysis of SCCS. When
> BBN came back with their new, release ready stack Bill supposedly said
> something like 'no thanks, we already got one that works way better.' This
> is why much of the structure of the original BBN stack survived the
> rewrite: if there wasn't a big issue with them, the design and mechanisms
> wound up being conserved by this effort. It was too much work to move from
> mbuf to something else, and too little gain.
>
> I tried to find a good link, but they are in his BSD history retrospective
> talks to differing degrees. Sorry I don't have an exact reference.
>
> Warner
>

[-- Attachment #2: Type: text/html, Size: 3715 bytes --]

[TUHS] Re: when did v8 or later get networking?

[Paul Ruizendaal]

> On 12 Aug 2023, at 07:08, Warner Losh <imp@bsdimp.com> wrote:
> 
> On Fri, Aug 11, 2023 at 3:05 AM Paul Ruizendaal <pnr@planet.nl> wrote:
> Bill Joy of CSRG concluded that the BBN stack did not perform according to his expectations. Note that CSRG was focused on usage over (thick) ethernet links, and BBN was focused on usage over Arpanet and other wide-area networks (with much lower bandwidth, and higher latency and error rates). He then in 1982 rewrote the stack to match the CSRG environment, changing the design to use software interrupts instead of a kernel thread and optimising the code (e.g. checksumming and fast code paths). It was a matter of debate how new the code was, with the extremes being that it was written from scratch using the spec versus it being mostly copied. Looking at it with a nearly 50 year distance, it seems in between: small bits of surviving SCCS suggest CSRG starting with parts of BBN code followed by rapid, massive modification; the end result is quite different but retained the ‘mbuf’ core data structure and a BBN bug (off-by-one for OOB TCP segments).
> 
> When Kirk McKusick tells  the story, UCB got a beta release (or early access) of the BBN stack. UCB was supposed to add the socket interface to whatever was there. But Bill Joy found it performed terribly (multiple seconds to connect sometimes, single digit kB over 10Mb media, etc). He optimized it to make it perform well. This was a combination of rewriting chunks and tweaking other chunks, which matches your analysis of SCCS. When BBN came back with their new, release ready stack Bill supposedly said something like 'no thanks, we already got one that works way better.' This is why much of the structure of the original BBN stack survived the rewrite: if there wasn't a big issue with them, the design and mechanisms wound up being conserved by this effort. It was too much work to move from mbuf to something else, and too little gain.
> 
> I tried to find a good link, but they are in his BSD history retrospective talks to differing degrees. Sorry I don't have an exact reference.
> 
> Warner

===

> UCB got a beta release (or early access) of the BBN stack.

This is certainly true. There are four surviving BBN tapes in the CSRG archive, from memory the first was from August 1981 and the last from early 1982. Again from memory, the oldest SCCS entries for the rewrite are from Oct ’81. All of this is on Kirk’s DVD.

Indeed the first tape is early code, written to just interface with Arpanet IMP’s. Things like routing are rudimentary or hard-coded, etc. This is all filled out by the time of the last tape, which also includes a token ring driver (written by Noel Chiappa, if I remember well).

There are two editions of Mike Muuss’ TCP-DIGEST mailing list with posts on performance from Joy and Gurwitz respectively (both from late 1981):

https://groups.google.com/g/fa.tcp-ip/c/WNE_j4mAbAE/m/3nCB79uvNcUJ

https://groups.google.com/g/fa.tcp-ip/c/zfYZh-kRlMg/m/pl-5oLQtYxIJ

Jonathan Gray sent me a good link of one of Kirk’s talks that addresses this bit of history:
https://youtu.be/DEEr6dT-4uQ?t=706

===

Maybe Kirk was using some hyperbole in that talk. As far as I can tell the main issues were the below:

- BBN coded the checksum routine in C and it compiled badly. Even Joy's hand-optimised version still took some 25% of CPU when traffic maxed out.

- The time-out constants were 2s and 5s. This makes sense for the Arpanet of the time. For local ethernet this was changed to 0.2s and 0.5s.

- The BBN code used at lot of bit fields. This too compiled badly, and was later changed to and/or with #define’d constants

- The BBN code took a very layered approach, often abstracting small bits of functionality into a separate routine. Without compiler inlining and a somewhat slow VAX subroutine mechanism this had a cost. Some of these functions where later changed to #define’s instead of functions.

- Although Kirk singles out replacing the state machine with a big switch statement in the above talk, I’m not sure this was a major performance boost. It is certainly the most visible/recognisable change in the source though. Somehow, this seems to have become core to the debate at the time (ref. the BBN talk at the Summer '84 Usenix conference). Maybe I underestimate the impact of this aspect.

- The TCP management process ran as a kernel thread with normal scheduling. On a loaded machine this meant that it could take seconds for this process to be scheduled again. Changing this to a software interrupt mechanism (somewhat similar to the runrun flag, although Joy appears to have credited VMS for the idea) made things more responsive and avoided context switches.

Of all the above, it would seem to me that only the last point was fundamental to the design. The other things appear relatively easy to fix.

===

Doug McIlroy wrote: "I recall expressions of surprise (dismay?) at the size of the BSD internet code, but without it we'd have lost our place in the Unix community."

An interesting question is how much of this size is unavoidable. Just counting file lines (i.e. ‘wc -l’), 4.2BSD has some 2200 lines of TCP code (i.e. just the TCP part), the ‘82 BBN implementation 2400 lines, 8th edition had some 2400 lines, and the first version of Plan9 some 2200 lines.

Some parts of TCP could perhaps be simplified (pseudo headers and ‘urgent' segments come to mind), but not much. Maybe this is just the code size that it takes.

URP is smaller, but if I remember well it does not handle out-of-order packets or packet duplicates (both of which do not occur in a (virtual) line switched context).

On the other hand, these sizes compare with 900 lines for the IL protocol in early Plan9.

[TUHS] Re: when did v8 or later get networking?

[Paul Ruizendaal]

> URP is smaller, but if I remember well it does not handle out-of-order packets or packet duplicates (both of which do not occur in a (virtual) line switched context).

Upon reflection, duplicates of course can occur when an ACK is lost.

[TUHS] Re: when did v8 or later get networking?

[Warner Losh]

[-- Attachment #1: Type: text/plain, Size: 402 bytes --]

On Sat, Aug 12, 2023, 4:29 AM Paul Ruizendaal <pnr@planet.nl> wrote:

> > URP is smaller, but if I remember well it does not handle out-of-order
> packets or packet duplicates (both of which do not occur in a (virtual)
> line switched context).
>
> Upon reflection, duplicates of course can occur when an ACK is lost.
>

What's URP? Sounds a little like UDP, is it a typo or something else?

Warner

>

[-- Attachment #2: Type: text/html, Size: 942 bytes --]

[TUHS] Re: when did v8 or later get networking?

[Dan Cross]

On Sat, Aug 12, 2023 at 11:20 AM Warner Losh <imp@bsdimp.com> wrote:
> On Sat, Aug 12, 2023, 4:29 AM Paul Ruizendaal <pnr@planet.nl> wrote:
>> > URP is smaller, but if I remember well it does not handle out-of-order packets or packet duplicates (both of which do not occur in a (virtual) line switched context).
>>
>> Upon reflection, duplicates of course can occur when an ACK is lost.
>
> What's URP? Sounds a little like UDP, is it a typo or something else?

I thought that might be a typo for UDP, but that doesn't have ACKs.

[TUHS] Re: when did v8 or later get networking?

[Paul Ruizendaal]

Universal Receiver Protocol, the protocol that Sandy Fraser invented for Datakit. The best description of it (imho) is the patent:

https://patentimages.storage.googleapis.com/37/a9/70/46f8c44ebd4e3a/US4852127.pdf

At first the patent is very focused on hardware implementation, but towards the end it gives the algorithms in pseudo-code.

Sandy Fraser wrote a 1993 retrospective paper “Early Experiments with Asynchronous Time Division Networks”. This paper includes a short summary of the origins of the universal receiver protocol, and how it evolved through 3 main steps. Unfortunately behind a paywall.

The implementation for 8th edition (some 750 lines) is here:
https://www.tuhs.org/cgi-bin/utree.pl?file=V8/usr/sys/dev/dkp.c

I think early Plan9 had an implementation of URP as well.


> On 12 Aug 2023, at 17:24, Dan Cross <crossd@gmail.com> wrote:
> 
> On Sat, Aug 12, 2023 at 11:20 AM Warner Losh <imp@bsdimp.com> wrote:
>> On Sat, Aug 12, 2023, 4:29 AM Paul Ruizendaal <pnr@planet.nl> wrote:
>>>> URP is smaller, but if I remember well it does not handle out-of-order packets or packet duplicates (both of which do not occur in a (virtual) line switched context).
>>> 
>>> Upon reflection, duplicates of course can occur when an ACK is lost.
>> 
>> What's URP? Sounds a little like UDP, is it a typo or something else?
> 
> I thought that might be a typo for UDP, but that doesn't have ACKs.

[TUHS] Re: when did v8 or later get networking?

[Paul Ruizendaal]

> On Aug 12, 2023, at 5:05 PM, Noel Chiappa <jnc@mercury.lcs.mit.edu> wrote:
> 
>> From: Paul Ruizendaal <pnr@planet.nl>
> 
>> a token ring driver (written by Noel Chiappa, if I remember well).
> 
> No (unless they took one I wrote for the V6 machine and adapted it); I never
> did anything on any Unix after V6 (I think there's nothing of any significant
> interest in any later Unix).
> 
> Anyway, writing a driver for that board would be about as much work as
> writing a driver for an RK11 controller - i.e. a day or so for someone
> competent.
> 
> 	Noel

Found it: it is the Proteon driver on BBN tape 2. The file has the following comment at the top:

/*
 * Proteon VII Local Net Interface Driver 
 * (adapted from Noel Chiappa's V6 driver and ACC driver by Rob Gurwitz, BBN)
 *
 * NB. Make sure definition of VII_CONF is correct for configuration of ring,
 *     i.e., VII_HEN for use with wire center, VII_STE for use without.
 */

So yes, they indeed took one you wrote for the V6 machine and adapted it.

[TUHS] Re: when did v8 or later get networking?

[Noel Chiappa]

    > From: Paul Ruizendaal <pnr@planet.nl>

    > a token ring driver (written by Noel Chiappa, if I remember well).

No (unless they took one I wrote for the V6 machine and adapted it); I never
did anything on any Unix after V6 (I think there's nothing of any significant
interest in any later Unix).

Anyway, writing a driver for that board would be about as much work as
writing a driver for an RK11 controller - i.e. a day or so for someone
competent.

	Noel

[TUHS] Re: when did v8 or later get networking?

[Jonathan Gray]

On Wed, Aug 09, 2023 at 06:09:40PM -0700, Larry McVoy wrote:
> 
> TCP/IP, not datakit.
> 

"The closest we got to using 4.n BSD was when Robert Morris, now at MIT,
imported the 4.1c TCP/IP stack into 7/8th edition (I believe in 84)
nominally as my summer student."
Dave Presotto on 9fans, 2001-10-01
https://marc.info/?l=9fans&m=111558818409805&w=2

"the 8th edition system including Streams was already pretty
much in place by the time that Robert Morris adapted
the then-current BSD TCP/IP stack to streams.  At that time,
we were using either serial communication over various modems,
and more notably Datakit. Looking back at this, one of
the satisfying things is that the communication structure
built then was adaptable so smoothly to TCP/IP when
the protocol's importance became undeniable."
Dennis Ritchie on 9fans, 2001-10-02
https://marc.info/?l=9fans&m=111558818709848&w=2

[TUHS] Re: when did v8 or later get networking?

[Douglas McIlroy]

My preface to the manual: says v8 " incorporates facilities from the
Seventh Edition, System V, andBerkeley BSD 4.1. The distinctive theme
...is distributed computing"It goes on to cite streams, Datakit, RFS,
and Blit. The internet lurks in the citation of BSD 4.1.

The preface goes on to suggest how the new facilities affected life in
the lab: "These facilities have spurred a host of programs for remote
information services, interactive graphics, debugging, and simple
fun".

On rereading this, I am struck by how blinkered I was not to overtly
mention either the internet, which brought us out of the clumsy era of
uucp and CSNET, or upas, which seamlessly integrated remote and local
mail (and would eventually save us from the Morris worm).

I recall expressions of surprise (dismay?) at the size of the BSD
internet code, but without it we'd have lost our place in the Unix
community. Even greater concern about the complexity of sendmail led
Presotto to develop the simpler upas.

Doug


On Wed, Aug 9, 2023 at 9:09 PM Larry McVoy <lm@mcvoy.com> wrote:
>
>
> TCP/IP, not datakit.

[TUHS] Re: when did v8 or later get networking?

[John Cowan]

[-- Attachment #1: Type: text/plain, Size: 365 bytes --]

On Wed, Aug 9, 2023 at 11:18 PM Rob Pike <robpike@gmail.com> wrote:

> STREAMS was the Unix support group's shouty adaptation. The V8 one that
> dmr put together was the gentler dulcet-toned Streams.
>
> Seriously, no one could figure out why they wanted to yell.
>

I always supposed it was a trademark (like UNIX), or at least was intended
to be one.

[-- Attachment #2: Type: text/html, Size: 1039 bytes --]

[TUHS] Re: when did v8 or later get networking?

[Rob Pike]

[-- Attachment #1: Type: text/plain, Size: 842 bytes --]

STREAMS was the Unix support group's shouty adaptation. The V8 one that dmr
put together was the gentler dulcet-toned Streams.

Seriously, no one could figure out why they wanted to yell.

-rob


On Thu, Aug 10, 2023 at 12:46 PM Warner Losh <imp@bsdimp.com> wrote:

>
>
> On Wed, Aug 9, 2023, 8:38 PM segaloco via TUHS <tuhs@tuhs.org> wrote:
>
>> > TCP/IP, not datakit.
>>
>> The V8 manual contains internet(3), tcp(3), and udp(3).  In the copy I
>> have these are dated 8/7/85.  Down in the kernel in /usr/sys/inet the
>> earliest files appear to be dated 3/22/85.  I'm going to do a comparison
>> with the 4.1cBSD TCP/IP stuff because a casual glance reveals some overlap.
>>
>
> Yea, I thought it was 4.1bsd + later tcp code but with a STREAMS instead
> of Socket interface...
>
> Warner
>
> - Matt G.
>>
>

[-- Attachment #2: Type: text/html, Size: 2117 bytes --]

[TUHS] Re: when did v8 or later get networking?

[segaloco via TUHS]

> > > TCP/IP, not datakit.
> > 
> > The V8 manual contains internet(3), tcp(3), and udp(3). In the copy I have these are dated 8/7/85. Down in the kernel in /usr/sys/inet the earliest files appear to be dated 3/22/85. I'm going to do a comparison with the 4.1cBSD TCP/IP stuff because a casual glance reveals some overlap.
> > - Matt G.
> 
> 
> Yea, I thought it was 4.1bsd + later tcp code but with a STREAMS instead of Socket interface...
> 
> Warner

This comment at the top of /usr/sys/netinet/socket.c is illuminating:

> /*
>  * socket emulation routines
>  * pretty much 4.2 sys/uipc_socket2.c
>  */

All of the files that have timestamps at the top list 83/07/29, except ip_input.c which has 83/08/16 instead.  The V8 version has _device (device driver) and _ld (line discipline) components that the 4.1cBSD code does not have.  Many other files have analogs between the two.  The byte ordering subroutines have been copied into a file, goo.s, from their home in 4.1cBSD in the C library (/usr/src/lib/libc/net/misc).  When this work originated someone else would need to answer, but looks like it was as Warner described, modified 4.xBSD TCP/IP.

- Matt G.

[TUHS] Re: when did v8 or later get networking?

[Warner Losh]

[-- Attachment #1: Type: text/plain, Size: 516 bytes --]

On Wed, Aug 9, 2023, 8:38 PM segaloco via TUHS <tuhs@tuhs.org> wrote:

> > TCP/IP, not datakit.
>
> The V8 manual contains internet(3), tcp(3), and udp(3).  In the copy I
> have these are dated 8/7/85.  Down in the kernel in /usr/sys/inet the
> earliest files appear to be dated 3/22/85.  I'm going to do a comparison
> with the 4.1cBSD TCP/IP stuff because a casual glance reveals some overlap.
>

Yea, I thought it was 4.1bsd + later tcp code but with a STREAMS instead of
Socket interface...

Warner

- Matt G.
>

[-- Attachment #2: Type: text/html, Size: 1090 bytes --]

[TUHS] Re: when did v8 or later get networking?

[segaloco via TUHS]

> TCP/IP, not datakit.

The V8 manual contains internet(3), tcp(3), and udp(3).  In the copy I have these are dated 8/7/85.  Down in the kernel in /usr/sys/inet the earliest files appear to be dated 3/22/85.  I'm going to do a comparison with the 4.1cBSD TCP/IP stuff because a casual glance reveals some overlap.

- Matt G.