Math is hard

When developing software to run in a Unix environment, you will often be able to use the same system features and benefit from good developer tools, regardless of the particular platform you're working on, as most processors will provide a rich instruction set and virtual memory, among other things.

When you're on the other side of the fence, and working in the kernel, all the gory details which will heavily differ across platforms can no longer be ignored, and sometimes, the shortcomings of a given processor architecture can become a real pain in the arse.

For example, if you have read the m88k saga, you might remember that the need, for the operating system exception handler, to perform all the pending load and stores before returning from exception processing, had been a source of problems for years.

The 88100 processor is not the only processor which sometimes makes the kernel developer's life harder than it could have been.

Let me tell you about a processor design choice which turned out to have a significant cost in the kernel (but in a rare situation.)

The VAX architecture, introduced at the end of 1977, is one of the oldest 32-bit architectures. The architecture has a large instruction set, plenty of addressing modes, but nothing fancy: no out-of-order execution, no branch delay slots, no register renaming, no hyper threading, and even no cache memory on the earliest designs, which did not need any as they wouldn't run faster than the memory refresh cycle (back then, processors speeds were expressed as cycle times in micro- or nano-seconds, rather than megahertz: a 5MHz processor would be described as having a 200ns cycle time; in comparison, the memory refresh cycles would be around 120ns, and as progress were made, were slowly decreasing, with 100ns memory being common at the end of the 1980s, 80ns in the first half of the 1990s, 70ns and 60ns later on.)

The exception model of the VAX was also quite simple, with the ``Exceptions and Interrupts'' chapter of the VAX Architecture Reference Manual being only 36 pages long in the first edition (and 43 in the second edition, mostly because of a slightly larger font rather than extra text.)

Quoting from it:

A trap is an exception that occurs at the end of the instruction that caused the exception. Therefore the PC saved on the stack is the address of the next instruction that would normally have been executed.

[...]

A fault is an exception that occurs during an instruction and that leaves the registers and memory in a consistent state such that elimination of the fault condition and restarting the instruction will give correct results. After an instruction faults, the PC saved on the stack points to the instruction that faulted.

So far, this is textbook processor design. If the processor encounters a situation which is not recoverable (and will cause your process to be killed), it's a trap.

If, however, there is a chance that some recovery action can be done and the offending instruction given another chance, then it's a fault.

For example, accessing a memory page which is not mapped will cause a fault. If the address is legitimate, the appropriate page and its contents will be fetched from swap (or from the binary file you are running), and the operation can be restarted. If the address is not legitimate, then your process will be sent a SIGSEGV signal and die.

Dividing by zero, on the other hand, is a trap. No matter what one may try to bend the laws of mathematics, there is no way for such a computation to ever deliver a meaningful result. Your process will be sent a SIGFPE (Floating-Point Exception) signal - even if this was an integer divide. (The siginfo_t extra information will let an hypothetical signal handler tell integer divide by zero (FPE_INTDIV) and floating-point divide by zero (FPE_FLTDIV) apart.)

So far, so good - the VAX exception handler (trap() in sys/arch/vax/vax/trap.c) would let the VM system recover the missing page faults, and would send a SIGFPE signal down the throat of your process, for arithmetic traps. This code has been almost unchanged since 3BSD.

Did you know?

Back in 1980, the illegal instruction signal nowadays known as SIGILL was called SIGINS, SIGSEGV was called SIGSEG, SIGKILL was called SIGKIL, SIGFPE was called SIGFPT, SIGTERM was called SIGTRM, and roads were uphill both ways...

Excerpt from 3BSD sys/h/param.h, dated january 5th, 1980: /* * signals * dont change */

#define NSIG 17 /* * No more than 16 signals (1-16) because they are * stored in bits in a word. */ #define SIGHUP 1 /* hangup */ #define SIGINT 2 /* interrupt (rubout) */ #define SIGQUIT 3 /* quit (FS) */ #define SIGINS 4 /* illegal instruction */ #define SIGTRC 5 /* trace or breakpoint */ #define SIGIOT 6 /* iot */ #define SIGEMT 7 /* emt */ #define SIGFPT 8 /* floating exception */ #define SIGKIL 9 /* kill, uncatchable termination */ #define SIGBUS 10 /* bus error */ #define SIGSEG 11 /* segmentation violation */ #define SIGSYS 12 /* bad system call */ #define SIGPIPE 13 /* end of pipe */ #define SIGCLK 14 /* alarm clock */ #define SIGTRM 15 /* Catchable termination */

In late april 2002, Todd Miller, who was - among other things - taking care of Perl in the OpenBSD basesystem, tried the latest Perl snapshot which would

eventually become Perl 5.8, and noticed it would fail to build on the i386 and vax platforms, because miniperl (a subset of Perl itself used during the build to produce various files needed by the full-blown Perl) would sometimes spin, apparently stuck but keeping the processor busy.

Investigating, he managed to produce a standalone reproducer.

Date: Tue, 30 Apr 2002 16:24:50 -0600 From: Todd C. Miller To: private OpenBSD mailinglist Subject: i386 divide by zero bug

The following program hangs forever with: 29142 a.out PSIG SIGFPE caught handler=0x1 mask=0x0 addr=0x17ba trapno=8

Vax has similar behavior when you overflow a double.

- todd

#include <stdio.h> #include <stdlib.h> #include <signal.h>

int main(int argc, char **argv) { int i;

signal(SIGFPE, SIG_IGN); i = 1 / 0;

exit(0); }

The i386 situation got taken care of quite quickly, but we were left with the Vax situation.

On may 7th, there was this very terse, but to the point, status report on the OpenBSD developers chatroom.

<deraadt> Todd, what about that SIGFPE stuff? <millert> What about it? <millert> It's still fucked as far as I know <millert> And that means that when perl gets updated, it won't work on vax...

One week later, this was still pending...

<deraadt> ok, so Todd, the new perl just wants a vax FPE fix eh? <millert> Yes. <deraadt> the correct behaviour should be? <millert> The problem is that when you try to ignore SIGFPE and an overflow occurs the kernel keeps delivering the signal and doesn't stop. It should not deliver the signal at all since it is ignored. <deraadt> and it should... do what? <deraadt> advance over the instruction I suppose.

<millert> I guess. There are ways to tell the vax to ignore FPU exceptions but I didn't find any real info on it.

The next day, I chimed in:

<miod> I was thinking about the SIGFPE-in-a-loop problem <miod> and found this note: <miod> When we get an arithmetic fault of types 8,9,10. The PC is backed up to point at the instruction causing the fault. If we just send a SIGFPE and return, and there is no SIGFPE hander, the program goes into an infinite loop <hugh> heh <miod> that might be what we are experiencing here <miod> I'll check with the VARM this evening (VARM here being the VAX Architecture Reference Manual.) This note was actually an excerpt from the Linux-vax project, as it was not dead yet at that time. This todolist is no longer online, but has been saved by the Wayback Machine. The complete text from which I quoted was:

When we get an arithmetic fault of types 8,9,10. The PC is backed up to point at the instruction causing the fault. If we just send a SIGFPE and return, and there is no SIGFPE hander, the program goes into an infinite loop with the arith_fault handler, and the faulting instr. Should we a) try and advance PC, or b) send it a signal that kills it?

After some tinkering, I had a crude diff which had a chance to solve the problem.

Date: Wed, 15 May 2002 19:44:14 +0000 From: Miod Vallat To: Hugh Graham, Todd C. Miller Subject: the vax SIGFPE problem, WIP

As told on ICB, I think I've found the reason behind the SIGFPE loop. Arithmetic fault can either be "traps", or restartable "faults". In the fault case, the frame pc points to the instruction that faulted, and not the following instruction, in case we could save the world and make it not fault again.

Since we only deliver a signal in this case, it loops. The workaround is to skip to the next instruction.

I cooked the following diff, but it's not finished compiling, so be careful, it might not be a bright idea, but I think you might have comments on the way I'm doing it...

Oh, and ddb needs fixes to properly recognize two-byte opcodes, but this will be a later diff.

Miod [...]

The problem was indeed simple: if the arithmetic trap was a fault, as opposed to a trap, and the SIGFPE signal was ignored, then we had to resume process execution after the faulting instruction. But the VAX exception model does not give us the ability to return from exception and skip that instruction.

So the kernel had to skip the instruction by itself. VAX instructions are of variable length, depending on the actual operands and addressing modes used. This meant that, in order to compute the correct instruction length, the kernel had to disassemble the instruction to skip. Which is no simple task since, when using some of the most insane addressing modes, a VAX instruction can span more than 16 bytes!

The high-level logic was simple and easy to document:

Index: vax/trap.c =================================================================== RCS file: /cvs/src/sys/arch/vax/vax/trap.c,v retrieving revision 1.22 diff -u -r1.22 trap.c --- vax/trap.c 2002/03/14 03:16:02 1.22 +++ vax/trap.c 2002/05/15 19:38:24 @@ -313,8 +313,25 @@ }

if (trapsig) { sv.sival_ptr = (caddr_t)frame->pc; trapsignal(p, sig, frame->code, typ, sv); + + /* + * Arithmetic exceptions can be of two kinds: + * - traps (codes 1..7), where pc points to the + * next instruction to execute.