go: proposal: spec: change all int types to panic on wraparound, overflow

From a programmer’s point of view, proposal #19623 is a significant simplification (wrap around and overflow disappear, and the new int type is both simpler in semantics and more powerful in use), while this proposal is a significant complication (wrap around and overflow now panic, and the new int type is both more complex in semantics and more difficult to use).

One of Go’s ideas is to reduce the intrinsic complexity of the programming language at hand while at the same time provide mechanisms that are general and powerful and thus enable programmer productivity and increased readability. We need to look at language changes not from a compiler writer’s point of view, but from a programmer’s productivity point of view. I think this proposal would be a step backward in the philosophy of Go.

I am also not convinced about the claim that overflow checking is “likely much lower than using arbitrary-precision ints”: The cost of arbitrary precision ints is there when one actually uses them, otherwise their cost is similar to what needs to be done for bounds/overflow checking (it’s the same test, essentially). There’s a grey area for ints that use all 64 (or 32) bits as they will become “big ints” internally (at least one bit is usually reserved to implement “tagged ints” efficiently) - but in code that straddles this boundary and if it matters one might be better off using a sized intxx type anyway. Finally, there’s a GC cost since the garbage collector will need to do extra work. But all that said, dealing with overflow panic will also require extra code, and that has to be written by each programmer by hand. It is also much harder to verify/read that code.

I’m not in favor of this proposal.

@griesemer

proposal #19623 is a significant simplification […], while this proposal is a significant complication

I believe that the two proposals are compatible (and even complementary). We could make int and uint arbitrary-precision types (to make default behavior simpler), and also make the sized integer types panic on overflow (to make complex behavior safer).

But all that said, dealing with overflow panic will also require extra code, and that has to be written by each programmer by hand. It is also much harder to verify/read that code.

Could you elaborate on this point? I would expect that most code would either not handle the panic, or use a wrapping integer type explicitly. Even the latter option does not seem like a lot of extra code.

I am curious how other (modern) programming languages like Swift approach this.

An arbitrary sampling:

Swift traps overflows by default and provides a set of parallel overflow operators (for example, &+ means “+ ignoring overflow”).

Rust traps overflows in debug mode, and provides explicit wrapping, saturating, checked, and overflowing variants. The overflowing variant is delightfully similar to what I’m proposing here. The Rust folks are keeping a handy list of overflow bugs they’ve found since adding the checks in debug mode.

C# has a checked keyword that enables overflow checks; overflows are silent by default.

Clojure throws an ArithmeticException by default; it can be disabled by setting *unchecked-math* or using explicit functions like unchecked-add.

The Kotlin reference doesn’t talk about overflow at all. In this thread the suggestion to check overflow appears to be rejected on efficiency grounds.

D overflows silently, but provides a checkedint library that sets a boolean on overflow.

And of course Java “[does] not indicate overflow or underflow in any way”, but Java 8 added Math.addExact and related functions, and the SEI CERT coding standard requires detection or prevention of overflow except for bitwise operations and “carefully documented” benign usage (such as hashing).

I think either proposal is an improvement over the status quo. Programmers who assert the nonexistence of overflow will write the same code they do today, so no cognitive overhead there, and I won’t have to worry about silent errors if they’re wrong.

@nnemkin Thanks for the reply. You did answer my question but I phrased my question incorrectly. Your suggestion would give me the wrong answer, the answer that this issue is designed to avoid. What I’m looking for is the expression that says “if I do this operation, will it panic?” That is, I want to not only avoid getting the wrong answer, I also want to avoid panicking. In general code should not panic. If we change the language as proposed, then people writing carefully will need to avoid the panic on overflow, and perhaps return an error instead. They need a reasonably simple way to do that that does not involve a deferred function calling recover.

I note that for every case in Go that currently causes a run time panic there is a straightforward way to avoid the panic: write p != nil or i < len(s) or divisor != 0 and so forth. What is the straightforward way to avoid arithmetic overflow in the type int, for the six operations that can overflow (I’m not counting ++ or --)?

Separate question: should we treat x >> y as an overflow if the value of y is greater than the number of bits in the type of x?

@griesemer

We need to look at language changes not from a compiler writer’s point of view, but from a programmer’s productivity point of view.

I want to come back to this point: I agree with it and I agree that it’s important. In fact, it is essentially the whole motivation behind this proposal.

Implicit wraparound favors the compiler-writer over the programmer. Let me explain.

The things that implicit wraparound makes easier are:

Implementation of hash functions.

Hash functions ignore overflow because they’re preserving the overflowed information in the other bits of the computed hash.

We’ve got lots of hash functions in the standard library (in hash/ and crypto/), but how many have you seen in user code? Even when programmers implement their own hash-based data structures (currently very difficult due to https://github.com/golang/go/issues/15292), they should generally be using an existing “good” hash function rather than trying to “roll their own”. Fast, low-collision hash functions are notoriously difficult to get right.

So “writing hash functions” is usually the complier-writer’s task, not the programmer’s task.

Implementation of multi-word integer types

Multi-word integer implementations (such as big.Int) ignore overflow because they’re preserving the overflowed bits in the next word.

I believe that you yourself are the author of much of math/big. So implicit overflow makes your job a bit easier — but how many application programmers do you think are writing that sort of code, especially given the existence of math/big?

Compiler code generation

Most CPUs running Go code today implement two’s-complement integer arithmetic and don’t trap on overflow. So if you define the language to implement two’s-complement arithmetic that ignores overflow, it’s easy to generate efficient code in the compiler: you don’t have to generate or optimize the code to check for overflows, and you don’t have to worry about writing optimizations to reduce the need for overflow checks.

The things that implicit wraparound makes harder are:

Programs that count things reliably

If you’re writing programs that deal with 32-bit timestamps, you want to avoid Y2038 bugs, such as silently adding a future calendar entry at a point in the distant past. If you’re writing programs that display view counts, you want to avoid treating popular items as negatively popular. If you’re writing programs that tally votes or compute financial statements, you’d really rather detect when you’ve hit the limits of your program rather than, say, accidentally treat a $3B expenditure as a credit. If you’re serving user data, you’d really rather detect invalid document IDs than accidentally serve unrelated documents with the same ID mod 2^32.

Programs that marshal and unmarshal large data structures

There have been multiple protobuf bugs due to overflows in the encode/decode paths. For example, see https://github.com/google/protobuf/issues/1731 and https://github.com/google/protobuf/issues/157 in the public repo — the latter being a potential DoS attack. Even in the cases in which Go’s slice bounds checks protect against that sort of bug, it’s not good for Go marshalers to generate payloads that might potentially corrupt or crash downstream clients or servers.

I don’t know about you, but to me, “counting things” and “marshaling data” seem much more representative of “programmer” use-cases. So I think you’ve got it backwards: the status quo favors compiler writers, and detecting overflow by default would push the balance more toward general programmers.

Is it possible to add this type into go1.9? Just add a type called uint64OverflowPanic may be enough to start try this stuff. I think We may need both overflow panic uint64 and non overflow panic uint64 in go 2.

Let me put it this way: I don’t think we’ve seen a good answer to my question about avoiding panics other than subsuming #6815.

Wrap-around arithmetic is necessary for crypto and other algorithms, but panic on overflow is very useful for security and correctness (i.e. not continuing silently with invalid data).

The balance can be achieved if only signed arithmetic panics on overflow (option 3 in the proposal). App logic dealing with quantities should use the default type int or appropriately large type for the task (int64, int128). Binary math algorithms can happily continue to use uint, uint64, uintptr etc.

The cost of signed overflow checking is minor. It is also a lot easier to optimize statically and locally, compared to arbitrary precision math proposal. There’s no fallback path and overflow branches can be inserted late, all targeting the same panic call (one per function, to distinguish them). Single JO after every ADD + a dozen dead bytes per function should give a pretty realistic performance impact estimate.

FWIW both GCC and Clang have -ftrapv, and Clang also has -fsanitize=signed-integer-overflow.

This doesn’t work for division by zero, but for addition, subtraction, and multiplication s, ok := a op b can assign useful values to s in even when ok is false. For subtraction and addition, the result is what you’d get right now. For multiplication, I think also “what you get now”, which is (I think) the low-order bits of the overflowing multiplication.

For the add/sub case you can directly compute what the answer should have been; for multiplication, you have the low-x-low part of your ultimate result.

We could do this, without the panics, in Go 1, which both gives people a clear way to write this now, and future-proofs it against panic-on-overflow in Go 2 (because you wrote this where you thought it would happen). It would come into minor conflict with a Go 2 “int just grows as needed” int type (but not the sized types) – either it always returns “okay” or we statically error out on that case, and we could conceivably remove them automatically (if the “ok” were involved in a complex expression we’d have to be a little more careful).

Maybe just 0 – the zero value for the type as with type assertions? https://play.golang.org/p/CBYt8ISMAu

(I’m not thinking of implementation details though)

@bronze1man A type called uint64OverflowPanic would be counterproductive. Users who are spelling out verbose type-names are presumably already thinking about overflow, and at that level of verbosity they can just as easily make calls to some library to check the operations.

The point of this proposal is to make detection of overflow the default behavior. That’s why it’s a language proposal and not just a library.

@bcmills Perhaps. My point is that this all adds extra complexity to the language where I am not convinced that we need more. We need less. Most people couldn’t care less about overflow and simply want integers that “just work”.

In a more complicated scenario, I would be quite frustrated by having to use an assignment for each and every operation.

I think you have misunderstood the proposal. You would only need one assignment per “expression consisting of arithmetic operators and / or conversions between integer types”, not one per operation: the check applies to the whole expression tree.

In the current draft, the only place you have to chop up the expression tree is at function-call boundaries, and even that could perhaps be relaxed.

The proposed , ok extension here would make the fix for #21481 much clearer. Instead of:

if c := cap(b.buf); c > maxInt-c-n {
  panic(ErrTooLarge)
}
newBuf = makeSlice(2*cap(b.buf) + n)

we could write

s, ok := 2*cap(b.buf) + n
if !ok {
  panic(ErrTooLarge)
}
newBuf = makeSlice(s)

What if instead of panicking, we marked overflowed ints as tainted.

An interesting idea.

One implementation approach would be to steal a “tag bit” to indicate overflow, but that has the downside of requiring all the fixed-width integer types to be n-1 bits (int31 instead of int32). My experience with languages in the ML family is that that’s really annoying: pretty much the whole point of fixed-width integer types is to interoperate with other languages and to make wire-encodings easy to work with, and those overwhelmingly tend to use power-of-two integer sizes.

Another implementation approach would be to use the arbitrary-length-integer trick of using the tag bit to indicate a pointer (or an offset in a table somewhere) that points to the real value, which would still be power-of-2-sized. My intuition is that that’s likely to be strictly more overhead than trapping on overflow, but perhaps not fatal. But it would imply that tainted Go ints could not be used directly in cgo or kernel structs, which in turn implies that “Go integer” and “C integer” probably need to actually be separate types in the type system.

So, maybe not terrible in terms of performance, but a bit awkward.

My bigger concern is that it would make overflow checking substantially weaker: we would only detect overflows that result in a validity check somewhere, which means we could still end up serializing corrupted values (e.g. incorrect length stamps in framing messages) and triggering arbitrary bugs in the (non-Go) programs on the receiving end.

@nathany

The Ariane 5 explosion is a nice example, but note that it involved many layers of failures:

1. The value overflowed.
2. The overflow resulted in an exception.
3. The exception was not handled.
4. The unhandled exception in a non-flight-critical task terminated flight-critical tasks on the computer.
5. …and the major part you’re leaving out: The overflow did not occur during testing.

The Ariane 501 Failure Report has a lot of interesting analysis, but I want to call out the second recommendation in particular:

R2 […] [T]est […] as much real equipment as technically feasible, inject realistic input data, and perform complete, closed-loop, system testing. […]

With silent overflow, it is easy to miss overflow errors even with fairly comprehensive tests: comparisons of overflowed values may work out anyway during tests because they happen to wrap around to values that satisfy some of the same invariants. (For example, the overflow in https://github.com/golang/go/issues/20687 was not caught in previous testing because the inputs happen to overflow to nonnegative values.)

On the other hand, a panic is hard to miss. It can be accidentally or intentionally recovered (e.g. by the fmt or http package), but in most cases a test that triggers a panic will fail, visibly and with an easy-to-debug stack trace. With visible test failures, overflow bugs are more likely to be caught before reaching production.

@ianlancetaylor

If we change the language as proposed, then people writing carefully will need to avoid the panic on overflow, and perhaps return an error instead.

Note that people writing carefully already need to avoid data corruption on overflow today: the need for these checks in carefully-written code is more-or-less orthogonal to the detection of that overflow.

I note that for every case in Go that currently causes a run time panic there is a straightforward way to avoid the panic

Another sometimes-not-straightforward case is avoiding panics from closing already-closed channels. But that is another matter. The general point is well-taken.

Now, on to the checks!

FWIW, only checks 3 and 4 strike me as reasonably readable, and both require fairly substantial checks to the language.

For increasing precision without math.Big and without arbitrary-precision ints, here’s a (mostly) tongue-in-cheek suggestion: add built-in [u]intNN types for arbitrary power-of-two NN. No more arguing about where to stop! 😃

@bronze1man Do you have reason to think that the cost of JSON encoding is dominated by integer arithmetic? On a modern CPU many algorithms are dominated by the time it takes to load values from memory, and that should not change under this proposal.

Just a datapoint, the code in https://golang.org/src/runtime/hash64.go takes advantage of overflow in almost every line of source (for the uintptr type).

Maybe we can’t do this until Go 2, but we can do experiments to get some data about it now. We could hack panic on overflow into the compiler today. What happens performance-wise with the go1 benchmarks? How many false positives are there? How many true positives are there?