5 ms·
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 allowe
by bleepblorp 6y ago
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.
- chrisseaton 6y agoI wasn’t aware of this - which instruction do you mean?
- wmil 6y agoThere'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.
- gsg 6y agoThat still exists though? add rax, rbx/jo overflow_error is how you do overflow checking on x86-64.
- chrisseaton 6y agoThat doesn’t work with a lot of arithmetic, so you have to use slower arithmetic in order to use it.
- gsg 6y agoSure, 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.
- praptak 6y agoAs 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.
- gpderetta 6y agoINTO 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.
- zeotroph 6y agoIs 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?
- deleted 6y ago[deleted]
- xpressvideoz 6y agoHaving a mode that makes all existing arithmetic instructions interrupt sounds plausible, though there must be something I overlooked.
- tom_mellior 6y agoThat 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.
- zeotroph 6y agoI 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.
- deleted 6y ago[deleted]
- gopalv 6y agoI think the GP was probably thinking of INTO(0xCE). https://en.wikipedia.org/wiki/INT_(x86_instruction)#INTO 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 https://en.wikipedia.org/wiki/Intel_MPX#Extensions
- bleepblorp 6y agoI 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 https://hjlebbink.github.io/x86doc/html/BOUND.html
- gsg 6y agoBOUND 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.
- pjmlp 6y agoModern 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.
- bleepblorp 6y agoINTO. 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.
- chrisseaton 6y agoYeah 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.
- BeeOnRope 6y agoUnfortunately jo is not fused on Intel chips, which is a bit surprising.
- raverbashing 6y agoCausing an interrupt is much more expensive than having a jump that won't be taken most of the time
- deleted 6y ago[deleted]
- rightbyte 6y agoUsually you don't really care that much about the overflow cost if it is an error right?
- raverbashing 6y agoTrue 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.
- kzrdude 6y agoThis was interesting, intel mpx is seen as a failure https://en.m.wikipedia.org/wiki/Intel_MPX https://en.m.wikipedia.org/wiki/Intel_MPX
- pjmlp 6y agoWhile Solaris on SPARC ADI is doing just fine, and there are ongoing efforts on ARM. Intel just missed the mark once more.
- brohee 6y agoIt'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.
- dathinab 6y agoThe 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.
- ordu 6y agoI 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.
- BeeOnRope 6y agoIt'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.
- Someone 6y agoI 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-vol3/o_fe12b1e2a880e0ce-210.html 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)
- BeeOnRope 6y agoYes, 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.