9 ms·
Myths about Integer Overflow in Rust
- eximius 10y agoIt'd be nice if there were a function annotation for this.
- wyldfire 10y agoThis is a great writeup, thanks! > in debug mode, arithmetic ... is checked for overflow > in release mode, overflow is not checked ... > "But what about performance?" I hear you ask. It is true that undefined behaviour drives optimisations by allowing the compiler to make assumptions Are there any targets that have instructions like integer-add-but-trap-if-overflow? Or maybe a mode that can be switched? It would be interesting if there could be a high-performing path to leave the check in for release mode.
- deleted 10y ago[deleted]
- masklinn 10y ago> Are there any targets that have instructions like integer-add-but-trap-if-overflow? No "modern" targets. MIPS and Alpha could trap on overflow (on MIPS `add` would trap, `addu` would not, not sure about Alpha) but neither x86_64 nor ARM have hardware support for trapping on overflow. x86 had INTO, which would INT 4 if the overflow flag was set, it still required additional instructions and the OS needed to convert that to an application trap, but there you are. It was removed in x86_64, likely because it wasn't used much.
- GolDDranks 10y agoDo you know if there is any interest to re-introduce the feature? It'd certainly be nice to be able to eliminate overflow bugs without runtime overhead.
- Gankro 10y agoApparently modern Intel CPUs will fuse JO instructions to preceding adds, producing the effect of dedicated "checked add" instructions: https://gist.github.com/regehr/65252e90fb6bad82d533#gistcomment-1733637 https://gist.github.com/regehr/65252e90fb6bad82d533#gistcomm...
- chrisseaton 10y agoIn the examples the article this shows this will not help, as the overflow is in indirect addressing, not add instructions. I'm not a microcode expert but I guess arithmetic instructions, even without a jo, are not as efficient as indirect addressing, so we can't switch to arithmetic instructions with jo.
- dbaupp 10y agoThe efficiency of the add/jo combo does help (i.e. checking overflow isn't a total drag), it just doesn't completely solve the performance problem.
- chrisseaton 10y agoPerhaps we could have a new addressing mode that is the same as normal indirect but falls through and sets o if some part of it overflows. Then you'd do mov, jo which could then be fused. But I don't really know what I'm talking about.
- amelius 10y ago> It was removed in x86_64, likely because it wasn't used much. Well, to be honest (anecdotal data) in my career of programming (with lots of C++), I must say that I can't remember having any actual problems with integer overflow. But for security (buffer overflow protection), it could be useful.
- nightpool 10y agoRust already has bounds checking on buffers though, so that specific issue isn't a huge concern. However, there is a class of security bugs introduced by bad logic, its just a little more difficult to exploit.
- nitrogen 10y agoWhen doing integer math with medium sized numbers on systems without floating point hardware, I have to be careful to arrange operations so they do not overflow, and sometimes it's still necessary to give up and use a 64-bit type on a 32-bit CPU. An example calculation would be projecting a 3D coordinate into a 2D space.
- prodigal_erik 10y agoIf you don't deliberately send an overflow through every function that does any arithmetic, they could quietly give wrong answers sometimes and I don't see how you'd know that.
- spc476 10y agoIn my career of programming (doing a lot of x86 programming in the late 80s/early 90s) I never saw INTO used, and on modern systems, it's very slow and worse yet, at least under Linux, it's mapped to a SIGSEGV (http://boston.conman.org/2015/09/05.2 http://boston.conman.org/2015/09/05.2).
- hbbio 10y agoIt was most likely removed from x86_64 because it is less useful! 32 bit overflows are possible (I have seen them in scientific algorithms for instance). But I have yet to see 64 bits overflows.
- dikaiosune 10y agoOverflows in subtraction remain common for 64-bit unsigned integers, however.
- dspillett 10y agoIt is going to be less common in many fields but I can imagine 64-bit overflow is a concern in a fair few scientific number crunching situations. Also, if you were to use the scaled integer method of representing fractional numbers (like the fixed-point data types seen in many SQL implementations) with a scale factor of 2^32 then a 64-bit overflow is a 32-bit overflow effectively (though I'll admit that is going to be no less rare than genuinely needing the full range of 64-bit integers). And I'm guessing all this applies to underflow as much as it is does to overflow which could be a concern for unsigned integers of any size.
- msbarnett 10y agoIIRC MIPS did. Alpha did as well I think.
- deleted 10y ago[deleted]
- Someone 10y agoI don't understand their logic. If "for X in" gets rid of many cases where overflow checking might hurt performance, what is the argument for disabling it (by default) in release builds, in a language that aims to be safe? Do they think it is that important to win benchmarks run with default compiler flags? Also, I expect Rust will still do bounds checking, and would guess many of the cases where the release build removes checks for overflow will now require some extra out of bounds checks: those for negative indices.
- Filligree 10y agoThe article talks about three different levels of optimization. - Detect and trap overflows. - Assume that two's complement math is a thing, and overflow can lead to additions producing negative values. - Assume that overflow never happens, and optimize on this basis. Rust does #1 in debug mode, #2 in release mode except when explicitly told not to. C compilers do #3. #3 is what leads to developers screaming at their compilers.
- dbaupp 10y agoArithmetic still happens a lot in programs, and especially so in tight loops (most tight loops will be filled with arithmetic, rather than anything else), even if it doesn't happen as the loop counters. You are correct that Rust does bounds checks in release mode, but fortunately there's no extra bounds checks needed: - all indexing is done with unsigned values, and, - even if signed values were used, the '< 0' comparison is still not necessary because one can first cast to unsigned (a noop) and then do a single '< length' comparison: negative values will be huge, at least as large as MEMORY_SPACE/2, which is in fact the limit on array lengths in Rust[1]. [1]: http://doc.rust-lang.org/stable/nomicon/vec-alloc.html http://doc.rust-lang.org/stable/nomicon/vec-alloc.html search for isize::MAX.
- pcwalton 10y ago> in a language that aims to be safe There are different levels of safety. Rust does not compromise on memory safety. Rust does compromise on integer overflow safety. This is not to say that memory safety is all that matters: rather it's to say that the line has to be drawn somewhere, and memory safety is where it was drawn. > I expect Rust will still do bounds checking, and would guess many of the cases where the release build removes checks for overflow will now require some extra out of bounds checks: those for negative indices. No, for two reasons: (1) you can only index arrays by unsigned values in Rust; (2) twos complement means that at the CPU level you can check for both negative indices and positive out of bounds indices by simply using one unsigned compare instruction.
- nvus 10y agoBefore reading the article I just have to say that I love the design of your page.
- EugeneOZ 10y agoWill it be possible to set some flag in Cargo.toml or in compiler arguments to enforce "saturating" behavior everywhere is possible? (even by price of some performance degradation).
- eridius 10y agoWhy would you want that? "saturating" behavior is something you want only rarely. It certainly isn't something you want to use by default for arithmetic operations.
- zzzcpan 10y agoHow about just different operators for different intents? Like prepending a special symbol in front of an operator to make it behave differently.
- eridius 10y agoThe article already mentioned the idea of using separate operators to control this behavior, similarly to how Swift has a separate set of operators for wrapping arithmetic.
- pcwalton 10y agoThat's discussed in the article. "The current state isn’t necessarily the final state of overflow checking: the RFC even mentioned some future directions. Rust could introduce operators like Swift’s wrapping +% in future, something that was not done initially because Rust tries to be conservative and reasonably minimal, as well as hypothetically having scoped disabling of overflow checking (e.g. a single function could be explicitly marked, and its internals would thus be unchecked in all modes). There’s interest in the latter particularly, from some of Rust’s keenest (potential) users Servo and Gecko."
- zzzcpan 10y agoYes, I know. But more operators is the solution, it removes all that ambiguity with multiple intents and simplifies a lot of things.
- Symmetry 10y agoThere are some architectures that support saturating arithmetic in hardware, DSPs for example. I wonder if the Rust saturating arithmetic commands get turned into those automatically?
- vardump 10y agoAnd x86 (SSE). http://felix.abecassis.me/2011/10/sse-saturation-arithmetic/ http://felix.abecassis.me/2011/10/sse-saturation-arithmetic/
- pslam 10y agoI very much believe overflow checking should be on for release builds, and not just debug. Overflow is defined by the language as an illegal operation, but if it's only enabled by debug builds, then it's effectively defined as "somewhat" illegal. I think this gives the community the wrong impression, and a firmer stance should be taken. This is a killer feature, in my opinion. In practice, for anything which isn't a micro-benchmark, it's a negligible performance hit. For things resembling a micro-benchmark, you can specifically use wrapped-arithmetic operations, or disable it for that module. I see a strong correlation between people complaining about overflow checking overhead, and people who don't actually care about the safety features.
- kibwen 10y agoThe operations themselves may only impose a performance hit of 10% or less, but the optimizations that those checks inhibit can easily cascade into a 2x slowdown, which isn't acceptable if Rust wants to compete with C++. As for your correlation, I care a lot about safety, but I also recognize that the safest language in the world isn't going to pose any real-world improvement if it's not capable of competing with less-safe languages in their entrenched domains.
- adrianN 10y agoMany people complaining about overflow checking either work in high performance computing, where it really matters how fast you can add two numbers, or in embedded systems where you can't afford either the extra space for the instructions, or the extra execution time.
- Manishearth 10y ago> Overflow is defined by the language as an illegal operation Is it? What do you mean by illegal here? Overflow can't cause UB madness in Rust like it does in C; the compiler does not optimize loops assuming no overflow.
- vardump 10y agoUB can be confusing, but please remember it also means a lot of very reasonable optimization opportunities. Say in data flow analysis, when the compiler can assume "(value + 1) > value" to be always true, a whole expensive branch can be removed. If the overflow is never going to happen anyways, the savings are considerable (expensive branch eliminated) and the result is always correct.
- konne88 10y agoWhat we really need is a hardware extension for ARM/Intel that traps on under/overflow: http://blog.regehr.org/archives/1154 http://blog.regehr.org/archives/1154
- snuxoll 10y agoThe overflow flag does a fine job of this, IMO.
- kazagistar 10y agoThe overflow flag requires a operation and branch to check. A trap is "free" until it actually happens.
- rcthompson 10y agoIf you allow overflow in your module, and then another module uses yours but disallows overflow, what happens? Could the overflow behavior be encoded in an integer's type to make this kind of code mixing explicit (via casts)?
- wyldfire 10y agoThe code generated for each will be different.
- rcthompson 10y agoWhat I mean is, suppose your module does an arithmetic operation involving a _function from the other module like "x + other_module_function(y) * 2". You've enabled panicking on overflow in your module for safety. Is it still possible that "other_module_function(y)" will return a result that overflowed without panicking? Does this mean that anyone writing code with overflow disallowed must carefully choose what modules they call to avoid calling any that allow overflow?
- dbaupp 10y agoThis is all hypothetical (in Rust), because there's no implementation. However, I would think that per-module enabling would be sticky, disregarding any call/use-sites: a module defining a hash function would say that overflow is OK/expected, and it would be incorrect for someone else to externally decide it is an error. (This also seems to be the only thing that is consistent: what if it is used from two modules with different options?)
- billforsternz 10y agoI started my career 35+ years ago programming in 8080 and then Z80 assembly language. A few years later I learned C and have been happily using it and C++ (I admit it, I use it as C plus classes) ever since. Because of my background I remember distinctly one of my first thoughts when encountering C was, "how do I access the overflow flag?" It seemed a huge problem. But I must admit I forgot all about it, (and have never had an overflow issue that I can remember), until recently when there suddenly seems a profusion of "C is a terrible language because of undefined behavior problems" posts, articles and discussions. So I do wonder how strongly coupled overflow concerns are with most practical every day programming. In my favourite problem domain of chess, I use uint8_t to represent say the number of white pawns (8 is the upper limit), and uint32_t to represent the number of games in my database (10,000,000 is a practical limit). Hitting 4 billion games is about as much of a problem to me as hitting 256 pawns. And uint64_t is waiting if I ever need it. Using integer types with massively excessive capacity seems a pretty obvious, easy and painless strategy to use for most everyday programming. Of course I realise that there are domains and situations in which this would be an exceptionally naive way to look at it - but I suspect they are at least somewhat exceptional.
- kibwen 10y agoPart of the difference is that 35 years ago the potential attack surface of any given piece of software was, generally, much lesser. Today it seems like everything is ubiquitously networked, and any given person's personal information is stored on god-only-knows how many servers under the purview of god-only-knows how many different people. I agree that integer overflow is a relatively minor concern for things like locally-installed non-networked chess applications, but as soon as you give attackers both an attack surface and an incentive to attack, the equation changes somewhat.
- pornel 10y agopawns - 1 would overflow. How big of a problem it is depends on the domain. I work with graphics where overflows happen all the time: you can find images large enough that width * height * constant doesn't fit in 31 bits. Image formats have 1-2 byte integers everywhere. You have to be careful with rounding and clamping pixels to avoid 255 white from flipping to 0 black, etc.
- openasocket 10y agoOne problem I have from a mathematical standpoint with dealing with overflow is often you may want the check to apply to an entire expression rather than individual operations. For instance, the expression "x + y - z" may cause an overflow when adding x and y, but may be "recovered" when subtracting z. We could change the expression to "x + (y - z)" but now we have to resign ourselves to the fact that addition is no longer associative, and requires the programmer to know which operations should be grouped together. Is there a way to do bounds checking of some sort on these expressions to ensure there is no overflow in a decidable way?
- dbaupp 10y agoYeah, it can definitely be annoying when an expression as a whole doesn't overflow, but subexpressions do... however, chains of addition and subtraction are special in this regard, even something like (x + y) / 2 (from binary search) is problematic. Of course, chains of + and - like that do pop up, so maybe an analysis of them would be valuable. In any case, that sort of recovery is a major reason that overflow is defined to wrap when checking is off: errors may cancel out.
- simcop2387 10y agoAnd x + (y - z) doesn't even fix the problem. y-z can still underflow, while (x+y) - z wouldn't. Being able to do it on the expression overall would be ideal.
- openasocket 10y agoYeah, I'm wondering how that would look at the assembly level. In the "x + y - z" example we get an overflow from the "x + y" and an underflow when we add z. So you'd have to check if the number of overflows and the number of underflows are equal, and the assembly would probably be really slow. You'd want some kind of bounds check optimization to try and remove as many of those checks as you can. Fortunately, I don't think these issues will appear too often (at least they haven't in my experience), and you can probably get away with just adding unit tests. To be completely thorough you should probably use some sort of formal modeling and proof system, which I would like to see someone try and develop for Rust.