Wandering Thoughts archives

The format of strings in early (pre-C) Unix

The very earliest version of Unix was written before C was created and even after C's creation the whole system wasn't rewritten in it immediately. Courtesy of the Unix Heritage Society, much of the surviving source code from this era is available online. It doesn't make up a complete source tree for any of the early Research Unixes, but it does let us peek back in time to read code and documentation that was written in that pre-C era.

In light of a recent entry on C strings, I became curious about what the format of strings was in Unix back before C existed. Even in the pre-C era, the kernel and assembly language programs needed strings for some things; for example, system calls like creat() and open() have to take filaname arguments in some form, and programs often have constant strings for messages that they'll print out. So I went and looked at early Unix source and documentation, for Research V1 (entirely pre-C), Research V2, and Research V3.

I will skip to the punchline:

Unix strings have been null-terminated from the very beginning of Unix, even before C existed.

Unix did not get null-terminated strings from C. Instead, C got null-terminated strings from Unix (specifically, Research V1 Unix). I don't know where V1 Unix got them from, if anywhere.

There's plenty of traces of this in the surviving Research V1 files. For instance, the V1 creat manpage says:

creat creates a new file or prepares to rewrite an existing file called name; name is the address of a null--terminated string. [...]

The V1 shell also contains uses of null-terminated strings. These are written with an interesting notation:

[...]
   bec 1f / branch if no error
   jsr r5,error / error in file name
       <Input not found\n\0>; .even
   sys exit
[...]
qchdir:
   <chdir\0>
glogin:
   <login\0>
[...]

Not all strings in the shell are null-terminated in this way, probably because it was natural to have their lengths just known in the code. If we need more confirmation, the error function specifically comments that a 0 byte is the end of the 'line' (here a string):

error:
   movb  (r5)+,och / pick up diagnostic character
   beq   1f / 0 is end of line
   mov   $1,r0 / set for tty output
   sys   write; och; 1 / print it
   br    error / continue to get characters
1:
   [... goes on ...]

I suspect that one reason this format for strings was adopted was simply that it was easy to express and support in the assembler. Based on the usage here, a string was simply a '<....>' block that supported some escape sequences, including \0 for a null byte; presumably this was basically copied straight into the object file after escape translation. There's no need for either the assembler or the programmer to count up the string length and then get that too into the object code somehow.

(It turns out that the V1 as manpage documents all of this.)

PS: it's interesting that although the V1 write system call supports writing many bytes at once, the error code here simply does brute force one character at a time output. Presumably that was just simpler to code.

Update: See the comments for interesting additional information and pointers. Other people have added a bunch of good stuff.

A fun Bash buffering bug (apparently on Linux only)

I'll present this in the traditional illustrated form:

$ cat repro
#!/bin/bash
function cleanup() {
   r1=$(/bin/echo one)
   r2=$(echo two)
   #echo $r1 '!' $r2 >>/tmp/logfile
   echo $r1 '!' $r2 1>&2
}
trap cleanup EXIT
sleep 1
echo final

$ ./repro | false
final
one final ! final two
$

Wait, what? This should print merely 'one ! two'. The 'echo final' should be written to stdout, which is a pipe to false (and anyways, it's closed by the time the echo runs, since false will already have exited by the time 'sleep 1' finishes). Then the cleanup function should run on termination, with $r1 winding up being "one" and $r2 winding up being "two" from the command substitutions, and they should then get echoed out to standard error as 'one ! two'.

(Indeed you can get exactly this output with a command line like './repro >/dev/null'.)

What is actually happening here (or at least appears to be happening) is an interaction between IO buffering, our old friend SIGPIPE, and forking children while you have unclean state. Based on strace, the sequence of events is:

1. Bash gets to 'echo final' and attempts to write it to the now-closed standard output pipe by calling 'write(1, "final\n", 6)'. This gets an immediate SIGPIPE.
2. Since we've set a general EXIT trap, bash immediately runs our cleanup function (since the script is now exiting due to the SIGPIPE).

3. Bash forks to run the $(/bin/echo one) command substitution. In the child, it runs /bin/echo and then, just before the child exits, does a 'write(1, "final\n", 6)'. This succeeds, since the child's stdout is connected to the parent's pipe. In the main bash process, it reads back one\n and then final\n from the child process, and turns this into "one final" as the value assigned to $r1.

4. For '$(echo two)', the child process just winds up calling write(1, "final\ntwo\n", 10). This becomes "final two" for $r2's value.

   (This child doesn't fork to run /bin/echo because we're using the Bash builtin echo instead.)

5. At last, the main process temporarily duplicates standard error to standard output and calls 'write(1, ....)' to produce all of the output we see here.

What appears to be going on is that when the initial 'echo final' in the main Bash process was interrupted by a SIGPIPE, it left "final\n" in stdout's IO buffer as unflushed output. When Bash forked for each $(...) command substitution, the child inherited this unflushed buffer. In the $r1 case, the child noticed this unflushed buffer as it was exiting and wrote it out at that point; in the $r2 case, the child appended the output of its builtin echo command to the unflushed stdout buffer and then wrote the whole thing out. Then, finally, when the parent ran the echo at the end of cleanup(), it too appended its echo output to the stdout buffer and wrote everything out.

There are two Bash bugs here. First, the output from the initial failed 'echo final' should have been discarded from stdout's IO buffer, not retained to show up later on. Second, the children forked for each $(...) should not have inherited this unflushed IO buffer, because allowing unflushed buffers to make it into children is a well known recipe for having exactly this sort of multiple-flush happen.

(Well, allowing any unflushed or un-cleaned-up resource into children will do this, at least if your children are allowed to then notice it and attempt to clean it up.)

I don't know why this bug seems to be Linux specific. Perhaps Bash is using stdio, and Linux's stdio is the only version that behaves this way (either on the initial write that gets SIGPIPE, or in allowing the unflushed buffer state to propagate into forked children). If this is Linux stdio at work, I don't know if the semantics are legal according to POSIX/SUS and in a way it doesn't matter, as stdio libraries with this behavior are on a lot of deployed machines so your code had better be prepared for it.

(Regardless of what POSIX and SUS say, in practice 'standard' Unix is mostly defined this way. Code that you want to be portable has to cope with existing realities, however non-compliant they may be.)

By the way, finding this Bash issue from the initial, rather drastic symptoms that manifested in a complex environment was what they call a lot of fun (and it was Didier Spezia who did the vital work of identifying where the failure was; I just ground away from there).

PS: If you want to see some extra fun, switch which version of the final echo is run in cleanup() and then watch the main Bash process with strace.