Hacker News Reader

Comment by bleepblorp | Hacker News Reader

It's worth mentioning that x86 CPUs had a single instruction overflow test that would raise a hardware interrupt in response to an integer overflow. This allowed for extremely low cost integer overflow tests.

Unfortunately, this capability was deleted from x86-64 and we're now stuck with either accepting the risks of integer overflows or suffering a performance hit to test for them by using multiple instructions.

Another extremely useful instruction deleted from x86-64 tested if an array access was in bounds. Determining how many buffer overflow exploits could have been prevented if this instruction was widely used--and carried over to x64--is left as an exercise for the reader.

View on HN

It's still a single instruction in the hot path: jo.

All such overflow jumps could go to the same handler, in which case it really would just be one instruction overall, but you'd lose the ability to report the exact location of the overflow. A small per-overflow thunk would solve that (it could be as small as a single call instruction).

Currently the jo doesn't macro-fuse with the addition on Intel chip, but maybe that will change in the future.

I don’t know x86, but, after googling, I would guess that trapping instruction was INTO.

Reading https://xem.github.io/minix86/manual/intel-x86-and-64-manual..., that would give the handler enough information to figure out where the overflow happened. Of course, that would be at the cost of some performance (setting those registers takes time)

Yes, one advantage of INTO over JO is that the interrupt mechanism insures that you know where you came from, so you can build location reporting on top of that.

However, I would consider that advantage fairly small, and it's not easy to implement either in a modular way since the way interrupts or signals are handled is a shared global thing, so you have to have process-wide agreement on how this overflow trapping is going to work (or at least an agreement on how to disagree). In a shared runtime language where everything plays by the same rules, but in low level native langues like C, C++ and Rust it is more difficult.

A jump based approach has the advantage that is is standalone and really doesn't seem much more expensive than INTO. The single jump instruction, and a bit more cold, out of line, code if you want accurate location reporting.

If/when AMD and Intel start fusing JO with the preceding arithmetic operation, it will be have a non-trivial perf advantage over INTO.

This was interesting, intel mpx is seen as a failure

https://en.m.wikipedia.org/wiki/Intel_MPX

While Solaris on SPARC ADI is doing just fine, and there are ongoing efforts on ARM.

Intel just missed the mark once more.

It's also IMHO a failure of RISC-V. "We did not include special instruction set support for overflow checks on integer arithmetic operations in the base instruction set, as many overflow checks can be cheaply implemented using RISC-V branches"

Cheaply is not freely.

The question is how much more expensive then a overflow checked add, which is mostly likely not as cheap as a non checked add.

I mean in the end both do a non checked add and then branch on the carry. One does it implicitly and branches to an interrupt and one does it explicitly and branches however you like it.

(Slightly) Increased chip complexity should be included in the choice, too.

I guess the main difference would/could be if used with some form of branch prediction.

I prefer branching. Interrupt is inconvenient especially if you mean not panic and die but do some recovery. Conditional jump after arithmetic operation could be as cheap as one instruction, branch prediction could make this instruction to cost almost nothing in terms of execution times (at least if overflows are a rare thing), and you could point this branch anywhere you like, so you could process overflow and try to recover from error without going outside of a current stack frame.

It could be ugly in a high-level languages though. Instead of (a+b)*c you might get something like

    a.checked_add(b)
     .map(|x| x.checked_mul(c))
     .flatten()
     .unwrap_or_else(|| do_something_to_recover(a, b, c));

At the same time there is nothing to forbid a syntax like:

   ((a⊕b)⊙c).flatten().unwrap_or_else(|| do_something to recover(a, b, c));

Just people do not like to use unicode in programming languages.

Your comment actually swayed my opinion. If you are to do anything useful after the overflow, you'll need branching...

No, sometimes overflow is so rare the trap saves you time in the majority case. Also sometimes panicking on hardware trap is the useful thing.

If we had more ALU variety these discussions wouldn't pop up. Saturating arithmetic, bounded arithmetic, etc are all useful and safer by default in most cases.

I wasn’t aware of this - which instruction do you mean?

There's an integer overflow flag that gets set after operations. My x86 books are all boxed up somewhere so I can't look up the details.

That still exists though? add rax, rbx/jo overflow_error is how you do overflow checking on x86-64.

That doesn’t work with a lot of arithmetic, so you have to use slower arithmetic in order to use it.

Sure, but that didn't change much between x86 and x86-64. Perhaps it got a little worse because the SIMD instructions aren't overflow check friendly.

As I understand this is about trapping, which makes overflow checking free for non-overflowing operations.

Flag checking, as opposed to trapping, incurs costs on all operations.

INTO would still need to check the flags and you would need to invoke it after every operation that could overflow. You can't configure the integer ALU to raise an interrupt automatically after any overflow.

Is there a reason to not add a new instruction to x86-64 which does interrupt the program on an integer operation overflow so no branching happens in the program? And can this instruction be made just as fast as the unchecked ones?

Having a mode that makes all existing arithmetic instructions interrupt sounds plausible, though there must be something I overlooked.

That wouldn't work well for C since signed overflow is undefined, but unsigned overflow is well-defined, with wrapping semantics. Making all existing arithmetic instructions trapping would mean paying trapping costs for well-defined unsigned overflow.

I think this would be a per-thread state which you toggle, defaulting to "off". Then instead of checking and branching after each operation you flip it on/off depending on the type of arithmetic you want. The trick would be to get to the minimal number of toggles and not do the "safe" thing and set it to on/off for each operation.

Generally this sort of global states are considered a misfeature. They are hard to use and impede cpu design (they are particularly bad for OoO). It is better to have per instruction flags.

For exemple while SSE still has an fpu control word, explicit instructions were added for some stuff that historically was handled by the control register (rounding for example).

Maybe is possible and it would be very useful.

I know nothing about micro-architectural implementations, but as far as I can remember, all instructions that can trap (load/stores, divs, etc) take more than one clock cycle. Simple sub/adds usually have 1 cycle latency; there just might not be enough latency budget to fit the trapping machinery.

I guess that the trapping doesn't actually need happen in the critical path (i.e. the results might be available earlier) but this would mean that even ALU instructions cause speculation.

I think the GP was probably thinking of INTO(0xCE).

https://en.wikipedia.org/wiki/INT_(x86_instruction)#INTO

The bounds-checking was MPX, I think.

> Another extremely useful instruction deleted from x86-64 tested if an array access was in bounds.

https://en.wikipedia.org/wiki/Intel_MPX#Extensions

I was thinking of BOUND[0] rather than MPX. It's a much lighter solution than MPX and didn't require OS support.

[0] https://hjlebbink.github.io/x86doc/html/BOUND.html

BOUND is pretty slow, and requires an odd start/end pair to be placed in memory. I don't see any reason that it would be better than the usual unsigned comparison + branch that languages with bounds checking tend to use.

Besides, much of the difficulty with memory safety in C and C++ is the existence of pointers (or wrappers around them, like iterators), which do not come with an associated length. Length checking machinery can't help with that problem whether special instructions exist or not.

In short, it's doubtful that the availability of these old instructions would make any difference to the practicality of bounds checking on modern x86 machines whatsoever.

Modern approaches take advantage of 64bit addressing modes to handle tagged pointers.

The irony that we need a Lisp Machines solution to fix C and its derived languages.

INTO.

It signals int 0x04 if the instruction is executed while the overflow flag is set due to a prior signed arithmetic operation wrapping.

It seems I misspoke somewhat; there is somewhat equivalent functionality in x64 in the JO instructions, but they're six bytes rather than one and the extra size could have cache and/or memory bandwidth impacts under demanding circumstances.

Yeah I knew about jo, and I think add-jo is even fused, but without a trap you have to write code everywhere to handle the overflow which you wouldn’t need if you had a trap. And of course jo doesn’t work for address arithmetic. That’s where the real overhead is.

Unfortunately jo is not fused on Intel chips, which is a bit surprising.

Causing an interrupt is much more expensive than having a jump that won't be taken most of the time

Usually you don't really care that much about the overflow cost if it is an error right?

True but do you care for all sums/muls in your code?

Might be better to check where exactly can you have the overflows and test in the code for those cases. I think checking for overflows over the entire code is useful for testing/validation purposes but not really useful in production.

Or use bigger data types if you're hitting overflows frequently.

> Might be better to check where exactly can you have the overflows and test in the code for those cases.

Compilers already track possible ranges and do this.

Reply on news.ycombinator.com