I'm still happily experimenting with my combination of a V6 kernel with the 1981 tcp/ip stack from BBN, for example figuring out how one would write something like 'ping' using that API. That brought me to pondering the origins of the 'alarm()' sys call and how some things were done on the Spider network.
These are my observations:
1. First of all: I understand that early Unix version numbers and dates mostly refer to the manual editions, and that core users had more frequent snapshots of a constantly evolving code base.
2. If I read the TUHS archive correctly, alarm() apparently did not exist in the original V6 edition of mid-1975. On the same basis, it was definitely there by the time of the V7 edition of early '79 (with sleep() removed) - so alarm() would seem to have appeared somewhere in the '75-'78 time frame.
3. The network enhanced NCP Unix versions in the TUHS archive have alarm() appear next to sleep(). Although the surviving tapes date from '79, it would seem to suggest that alarm() may have originated in the earlier part of the '75-'78 time frame.
4. The Spider network file store program 'nfs' (source here: http://chiselapp.com/user/pnr/repository/Spider/dir?mtime=0&type=flat&udc=1…) uses idioms like the below to avoid getting hung on a dead server/network:
signal(14,timeout); alarm(30);
if((read(fn,rply,100)) < 0) trouble();
alarm(0);
The 'nfs' program certainly was available in the 5th edition, maybe even in the 4th edition (the surviving 4th edition source code includes a Spider device driver). However, the surviving source for 'nfs' is from 1979 as well, so it may include later additions to the original design.
5. Replacing sleep() with alarm() and a user space library routine seems to have happened only some time after alarm() appeared, so it would seem that this was an optimization that alarm() enabled, and not its raison d'être.
So here are some questions that the old hands may be able to shed some light on:
- When/where did alarm() appear? Was network programming driving its inception?
- Did Spider programs use a precursor to alarm() before that? (similar to V5 including 'snstat' in its libc - a precursor to ioctl).
Paul
> / uses the system sleep call rather than the standard C library
> / sleep (sleep (III)) because there is a critical race in the
> / C library implementation which could result in the process
> / pausing forever. This is a horrible bug in the UNIX process
> / control mechanism.
>
> Quoted without comment from me!
Intriguing comment. I think your v6+ system probably has a lot of
PWB stuff in there. The libc source for sleep() in stock V6 is:
.globl _sleep
sleep = 35.
_sleep:
mov r5,-(sp)
mov sp,r5
mov 4(r5),r0
sys sleep
mov (sp)+,r5
rts pc
The PWB version uses something alarm/pause based, but apparently
gets it wrong:
.globl _sleep
alarm = 27.
pause = 29.
rti = 2
_sleep:
mov r5,-(sp)
mov sp,r5
sys signal; 14.; 1f
mov 4(r5),r0
sys alarm
sys pause
clr r0
sys alarm
mov (sp)+,r5
rts pc
1:
rti
I think the race occurs when an interrupt arrives between the sys alarm
and the sys pause lines, and the handler calls sleep again.
sleep() in the V7 libc is a much more elaborate C routine.
When I first read the race condition comment, I thought the issue would
be like that of write:
_write:
mov r5,-(sp)
mov sp,r5
mov 4(r5),r0
mov 6(r5),0f
mov 8(r5),0f+2
sys 0; 9f
bec 1f
jmp cerror
1:
mov (sp)+,r5
rts pc
.data
9:
sys write; 0:..; ..
This pattern appears in several V6 sys call routines, and would
not be safe when used in a context with signal based multi-
threading.
> From: Dave Horsfall
> As I dimly recall ... it returns the number of characters in the input
> queue (at that time)
Well, remember, this is the MIT V6 PDP-11 system, which had a tty driver which
had been completely re-written at MIT years before, so you'd really have to
check the MIT V6 sources to see exactly what it did. I suspect they borrowed
the name, and basic semantics, from Berkeley, but everything else - who
knows.
This user telnet is from 1982 (originally), but I was looking at the final
version, which is from 1984; the use of the ioctl was apparently a later
addition. I haven't checked to see what it did originally for reading from the
user's terminal (although the earlier version also used the 'tasking'
package).
Noel
> From: Paul Ruizendaal
> It would not seem terribly complex to add non-blocking i/o capability to
> V6. ... Adding a 'capacity' field to the sgtty interface would not
> have been a big leap either. ...
> Maybe in the 1975-1980 time frame this was not felt to be 'how Unix does
> it'?
This point interested me, so I went and had a look at how the MIT V6+/PWB
TCP/IP did it. I looked at user TELNET, which should be pretty simple (server
would probably be more complicated, due to PTY stuff).
It's totally different - although that's in part because in the MIT system,
TCP is in the user process, along with the application. In the user process,
there's a common non-premptive 'tasking' package which both the TCP and TELNET
code use. When there are no tasks ready to run, the process uses the sleep()
system call to wait for a fixed, limited quantum (interrupts, i.e. signals,
will usually wake it before the quantum runs out); note this comment:
/ uses the system sleep call rather than the standard C library
/ sleep (sleep (III)) because there is a critical race in the
/ C library implementation which could result in the process
/ pausing forever. This is a horrible bug in the UNIX process
/ control mechanism.
Quoted without comment from me!
There are 3 TCP tasks - send, receive and timer. The process receives an
'asynchronous I/O complete' signal when a packet arrives, and that wakes up
the process, and then one of the tasks therein, to do packet processing
(incoming data, acks, etc).
There appears to be a single TELNET task, which reads from the user's
keyboard, and sends data to the network. (It looks like processing of incoming
data is handled in the context of one of the TCP tasks.) Its main loop starts
with this:
ioctl (0, FIONREAD, &nch);
if (nch == 0) {
tk_yield ();
continue;
}
}
if ((c = getchar()) == EOF) {
so that ioctl() must look to see if there is any data waiting in the terminal
input buffer (I'm too lazy to go see what FIONREAD does, right at the moment).
Noel
Clem, Ron,
Thanks for the explanations! Some comments below.
>> 1. First of all: I understand that early Unix version numbers and dates
>> mostly refer to the manual editions, and that core users had more
>> frequent snapshots of a constantly evolving code base.
>
> Eh? They primarily refer to the distributions (Research V6, V7, PWB, the
> various BSD tapes).
> I'm not sure what "core users" are referring to. Most of us had many
> versions as we hacked and merged the stock releasesx.
I was too brief. I was referring just to the pre-V7 versions, and I had the implicit assumption that alarm() originated at the labs. My understanding was that the labels 5th, 6th and 7th edition had little meaning inside the labs, as there just was a continuously developing code base. Maybe this is a mis-understanding.
> "alarm was introduced as part of Unix/TS" "PWB [..] had both sleep() and alarm() as system calls"
Thanks for those pointers! I'm not sure I fully grasp the lineage of Unix/TS and PWB, but the TUHS wiki has a page about it: https://wiki.tuhs.org/doku.php?id=misc:snippets:mert1
From that, and from the TUHS Unix Tree web page I get that PWB1.0 from mid 1977 was probably the root source of alarm() for people outside AT&T. As PWB apparently got started much before that, it is possible that alarm() goes back much further as well.
> A bigger networking issue was select() (or the like). It used to be an
> interesting kludge of running two processes inorder to do simoultaneous
> read/write before that.
Yes: the NCP Unix team (Grossman/Holmgren/Bunch) also mentioned that as the big issue/annoyance that they ran into in 1975.
As discussed in this list before, 3 years elapsed before Jack Haverty came up with await() for V6. I was told that there was a lot of discussion in the 4.1x/4.2 BSD steering group in 1981/2 whether this functionality should be stateful (like await) or stateless (like select). Looking at the implementations for both, I can see why stateless carried the day.
> Right and select(2) was created by Sam and wnj during the 4.2 development. I've forgotten which sub-version (it was in 4.1c, but it might have been in b or a before that). There was a lot of arguing at the time about it's need; the multiple process solution was considered more 'Unix-like.'
That is an interesting point, and it got me wondering about another related feature that could have been in Unix in the 1975-1980 time frame, being both useful and practical even on a 11/40 class machine, but for some reason wasn't:
It would not seem terribly complex to add non-blocking i/o capability to V6. It could have been implemented as a TTY flag and it is not a big conceptual leap from EINTR to EAGAIN. Adding a 'capacity' field to the sgtty interface would not have been a big leap either. This would have allowed user processes to scan a number of tty lines e.g. once a second in a loop and do processing as needed. In NCP Unix this would not have been hard to extend to network pipes.
The NCP Unix / Arpanet crowd certainly had a need for it, it would have been very useful for Spider/Datakit connections and probably for uucp as well. And from there it is not a million miles to replace the timed user loop with something like select(). Yet non-blocking I/O and select() only appear in 1982.
Maybe in the 1975-1980 time frame this was not felt to be 'how Unix does it'?
Hello folks,
I realized I should mention this here on TUHS, since it is likely of
interest to at least some of you!
I recently wrote a DMD 5620 emulator, currently available on Linux and
Macintosh, with Windows support coming soon. Here's a brief demo of the
Mac version:
https://www.youtube.com/watch?v=tcSWqBmAMeY
I wrote it because DMD 5620s are becoming incredibly rare, and showing
them off in person is quite difficult nowadays.
This emulator is using ROM version 2.0 (8;7;5) dumped from my personal
5620. If anyone out there has a DMD 5620 with an older ROM, I would be
incredibly grateful if you could dump the ROMs. I'd like to find
versions of 1.x (8;7;3 or earlier); so far I've had no luck.
The main reason I'm interested in older ROMs, besides pure preservation
reasons, is that the 'mux' and 'muxterm' system on Research UNIX V8/V9
is hard-coded for the 1.1 ROMs. It doesn't work with the emulator
without significant tweaking of the source. It DOES work perfectly well
with the DMD Core Utilities package for the AT&T 3B2, however.
All the best!
-Seth
--
Seth Morabito
Poulsbo, WA, USA
web(a)loomcom.com
In the June 1966 CACM [1], Wirth and Hoare published "A contribution to the development of ALGOL”, which describes a language very similar to Algol W. In Wirth’s Turing Award lecture (published in the Feb 1985 CACM [2]) "From programming language design to computer construction”, he noted:
“The Working Group assumed the task of proposing a successor and soon split into two camps. On one side were the ambitious who wanted to erect another milestone in language design, and, on the other, those who felt that time was pressing and that an adequately extended ALGOL 60 would be a productive endeavor. I belonged to this second party and submitted a proposal that lost the election. Thereafter, the proposal was improved with contributions from Tony Hoare (a member of the same group) and implemented on Stanford University's first IBM 360. The language later became known as ALGOL W and was used in several universities for teaching purposes.”
In particular, Hoare’s work on “Record Handling” (see [3]) had a strong impact on Algol W and Wirth’s later languages.
[1] http://doi.acm.org/10.1145/365696.3657022
[2] http://doi.acm.org/10.1145/2786.2789
[3] http://www.softwarepreservation.org/projects/ALGOL/standards/.
> On Jan 10, 2019, at 7:06 PM, clemc(a)ccc.com wrote:
>
> From: Clem cole <clemc(a)ccc.com <mailto:clemc@ccc.com>>
> To: Dave Horsfall <dave(a)horsfall.org <mailto:dave@horsfall.org>>
> Cc: The Eunuchs Hysterical Society <tuhs(a)tuhs.org <mailto:tuhs@tuhs.org>>
>
> Dave. The w in Algolw was Wirth. He was at Stanford at the time. It was written in PL/360 btw. The sources are googlable. FWIW Pascal was done a couple of years later with lessons learned from Algolw and reaction to Algol68.
>
> Sent from my PDP-7 Running UNIX V0 expect things to be almost but not quite.
>
>> On Jan 10, 2019, at 6:52 PM, Dave Horsfall <dave(a)horsfall.org <mailto:dave@horsfall.org>> wrote:
>>
>> [Not sure whether this is more appropriate for COFF instead, so it's here; advice (apart from STFU) gratefully accepted.)
>>
>> Sir Charles Antony Richard Hoare FRS FREng was born on this day in 1934; a computer pioneer (one of the greats) he gave us things like the quicksort algorithm (which became qsort() in Unix) and ALGOLW (a neat language).
>>
>> -- Dave
>
[Not sure whether this is more appropriate for COFF instead, so it's
here; advice (apart from STFU) gratefully accepted.)
Sir Charles Antony Richard Hoare FRS FREng was born on this day in 1934; a
computer pioneer (one of the greats) he gave us things like the quicksort
algorithm (which became qsort() in Unix) and ALGOLW (a neat language).
-- Dave
So what's the origin of the name 'strategy' for the I/O routine in Unix
that drivers provide? Everything I've found in the early papers just says
that's what the routine is called. Is there a story behind why it was
chosen? My own theory is that it's in the sense of 'coping strategy' when
the driver needs to service more I/O for the upper layers, but that's just
a WAG.
Warner
On Tue, 8 Jan 2019, Warner Losh wrote:
> The name seems obvious because I've seen it for the last 30 years. But
> I've not seen it used elsewhere, nor have I seen it documented except in
> relationship to Unix. It could have been called blkio or bufio or bio or
> even just work or morework and still been as meaningful. VMS uses the
> FDT table to process the IRPs sent down. RT-11 has a series of entry
> points that have boring names. Other systems have a start routine
> (though more often that is a common routine used by both the queue me
> and isr functions). There is a wide diversity here...
I must admit that this is an interesting thread, just as long as it wasn't
called XXoptimize() unless you wanted a backlash from British English
speakers :-)
In hindsight I suppose that XXstrategy() is obvious, but back then, as you
ask? Dunno, but Ken might (if he's reading this thread).
One of my favo[u]rites is sched(); some pronounce it as "shed" and others
as "sked". Another American/British thing, I think...
Wasn't it Mark Twain who said "Two nations divided by a common language"?
I no longer have my Lions books on me, sadly enough (lost in a house move)
but there certainly were some peculiar names in the kernel...
ObGripe: Could anyone replying to the digest version please take the
trouble to update the Subject: line accordingly? I've now put the
original back as a courtesy to others, but I shouldn't have to; it's as
bad as top-posting.
-- Dave
