Math Is Hard – OpenBSD Stories

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 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:

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.

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 */

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

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:

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 [...]

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. + * - faults (codes 8..10), where pc points to the + * faulting instruction. + * In the latter case, we need to advance pc by ourselves + * to prevent a signal loop. + * + * XXX this is gross -- miod + */ + if (code == (T_ARITHFLT | T_USER) && frame->code >= 8) { + extern void *skip_opcode(void *); + + frame->pc = skip_opcode(frame->pc); + } } if (umode == 0)

About 6 hours later, I had an ugly workaround: I was reusing part of the disassembler code from the kernel debugger to parse the faulting instruction and compute its length.

Date: Wed, 15 May 2002 21:28:53 +0000 From: Miod Vallat To: Hugh Graham, Todd C. Miller, Theo de Raadt Subject: working vax sigfpe diff As Hugh and Todd already know, the SIGFPE problem is very simple: 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. To do so, I'm borrowing some MD ddb code, hence a lot of ugly #ifdef to ensure that non-DDB kernel can have this fix and not bring too much stuff. Miod [...]

So I reworked my changes to make the skip_opcode completely independent from the debugger code, but duplicating a few lines of code.

Date: Thu, 16 May 2002 00:49:16 +0000 From: Miod Vallat To: Theo de Raadt, Hugh Graham, Todd C. Miller Subject: improved vax sigfpe diff with goodies This new diff: - does not interfere with ddb anymore, at the expense of a few lines in machdep.c - features my improved db_disasm that correctly recognizes two-byte opcodes. Builds with or without option DDB, passes the fpe regress test, no issues so far here. Comments? Miod [...]

Fix a long standing problem on vax: on "arithmetic fault" exceptions, we schedule a SIGFPE signal delivery to the faulting process. However, arithmetic faults come in two flavors: "traps" that are "regular" exceptions, and "faults" that are restartable exceptions. In the "fault" case, the frame pc points to the faulting instruction, instead of the next instruction, in case we could save the world by tweaking memory and make the instruction not fault again when restarted. In practice, this led to processes blocked in a SIGFPE loop madness. To avoid this, add a skip_opcode() routine to compute the address of the next opcode, effectively skipping the offending instruction ; this routine is a very stripped-down db_disasm(). While there, enhance the ddb disassembler to correctly recognize and disassemble two-byte opcodes. ok hugh@, deraadt@

However, two days later, Michael Hitch noticed a bug in this change and fixed it.

On the vax, the trapsignal() call will change frame->sp to point to a callg on the user's stack that calls the user's signal handler, so do the skip_opcode() before calling trapsignal(). A floating point overflow no longer causes a signal loop. This should stop the native compile hangs trying to compile src/lib/libm/complex/catan.ln.

When handling SIGFPE, do the `advance pc if exception is a fault (as opposed to a trap)' dance before invoking trapsignal(), which will mess with the pc too. My bug initially, can't believe I never noticed; fixed first in NetBSD. This makes libsqlite3 build.

But there remains an unanswered question: with BSD having been runinng on VAX hardware since 1979, how come this problem was not fixed until 2002?

One possible reason is that few programs, if any, did ignore SIGFPE (or attempt to handle it), so when SIGFPE got delivered, these programs would be terminated immediately, without looping on the offending instruction.

But I think the real reason is different.

I suppose very few of my readers will satisfy any of these three conditions, so I will explain.

In the first edition of the VAX Architecture Reference Manual, on page 231, table 5.1 lists the Arithmetic Exception Type Codes:

| Exception Type | Mnemonic | Decimal | Hex | Traps | ||| | integer overflow | SS$_INTOVF | 1 | 1 | | integer divide-by-zero | SS$_INTDIV | 2 | 2 | | floating overflow | SS$_FLTOVF | 3 | 3 | | floating or decimal divide-by-zero | SS$_FLTDIV | 4 | 4 | | floating underflow | SS$_FLTUND | 5 | 5 | | decimal overflow | SS$_DECOVF | 6 | 6 | | subscript range | SS$_SUBRNG | 7 | 7 | Faults | ||| | floating overflow | SS$_FLTOVF_F | 8 | 8 | | floating divide-by-zero | SS$_FLTDIV_F | 9 | 9 | | floating underflow | SS$_FLTUND_F | 10 | A |

Note that the three fault conditions also exist as trap conditions.

In fact, their descriptions are quite similar. For example:

Exception Type | Mnemonic | Decimal | Hex | Traps | ||| | integer overflow | SS$_INTOVF | 1 | 1 | | integer divide-by-zero | SS$_INTDIV | 2 | 2 | | decimal divide-by-zero | SS$_FLTDIV | 4 | 4 | | decimal overflow | SS$_DECOVF | 6 | 6 | | subscript range | SS$_SUBRNG | 7 | 7 | Faults | ||| | floating overflow | SS$_FLTOVF_F | 8 | 8 | | floating divide-by-zero | SS$_FLTDIV_F | 9 | 9 | | floating underflow | SS$_FLTUND_F | 10 | A |

After the various traps and faults descriptions, the note finally gives us the clue:

Therefore, in the very beginning, when the only VAX systems were 11/780s, all arithmetic exceptions were traps, and could not get restarted. There was simply no need for the BSD kernel to skip the instruction, as the hardware had already done the work.

The only other exceptions which were faults, not traps, were memory management exceptions, which would always behave as "either the operating system can fix the problem and restart the instruction, or this is a non-recoverable error and your program can't continue" (and if you ignore SIGSEGV, it is considered perfectly acceptable that your program spins in a SIGSEGV loop until you kill it.)

When the architecture was changed to turn these into faults, I guess nobody paid enough attention to the consequences of that change to realize the need for the operating system to sometimes skip the faulting instruction, as one could not imagine software would mask SIGFPE or try to mess with the register values and restart the computation.

It is also very likely that the consequences of this change were only considered from a VMS point of view, with Unix (well, BSD) being considered irrelevant by Digital at the time.

But the net result is that the hardware does not provide any facility to get the address of the next instruction, in case a fault needs to be handled as a trap. After all, since the instruction has been executed, the address of the next one is known somewhere in the processor.

I wish there had been a way to get that address easily (either from the trap frame or from a special processor register), as this would have made fixing the problem simpler. But this situation is rare enough that the cost of having the kernel do the work turned out to be acceptable.

This implies the actual processor rework took place sometime earlier. Since the second VAX model, the VAX-11/750, was only announced in 1980, this is also consistent with all the mentions that only models 780 had the "every arithmetic exception is a trap" behaviour.

Figuring out when VAX-11/780 installations started to be modified by Digital field engineers (and in which order) would be an interesting detective work, but I doubt the paperwork trail of these reworks is still existing somewhere, especially with Digital having been bought by Compaq and then later by HP.

After all, we're talking about events having taken place about 45 years ago, which is an eternity, in computing times...

Also, in the few VMS release notes which can be found there on Bitsavers, there does not seem to be any mention of a 11/780 rework required (or advised).

The VMS 1.5 release notes, dated february 1979, in section 4.3, refer to a "CVTTP FCO" (CVTTP being a VAX instruction processing decimal data, FCO being a Field Change Order, when a Field Engineer is required to apply hardware changes to the system) required for proper Cobol-74 operation; but this is not related to floating-point aritmetic exceptions, thus not the change discussed here.