Hi everyone,
I've been wondering for a while whether it's feasible from a performance
standpoint for a systems language to detect and abort on
potentially-dangerous integer overflows by default. Overflow is an
insidious problem for several reasons:
(1) It can happen practically anywhere; anytime the basic arithmetic
operators are used, an overflow or underflow could occur.
(2) To reason about overflow, the programmer has to solve a global data
flow problem. An expression as simple as "a + b" necessitates an answer
to the question "could the program input have influenced a or b such
that the operation could overflow?"
(3) Overflow checking is rarely used in practice due to the performance
costs associated with it. ISAs aren't that well-suited for overflow
checking. For example, on the x86 one has to test for the overflow
and/or carry flag after every integer operation that could possibly set
it. Contrast this with the floating-point situation, in which a SIGFPE
is raised on overflow without having to explicitly test after each
instruction.
(4) It can be catastrophic from a memory safety and security standpoint
when overflow errors creep in, especially when unsafe operations such as
memory allocation and unchecked array copying are performed. We do
permit unsafe operations in Rust (although we certainly hope they're
going to be rare!)
I did a quick survey of the available literature and there isn't too
much out there*, but there is a recent gem of a paper from CERT:
http://www.cert.org/archive/pdf/09tn023.pdf
They managed to get quite impressive numbers: under 6% slowdown using
their As-If-Infinitely-Ranged model on GCC -O3. The trick is to delay
overflow checking to "observation points", which roughly correspond to
state being updated or I/O being performed (there's an interesting
connection between this and the operations that made a function "impure"
in the previous effect system).
This area seems promising enough that I was wondering if there was
interest in something like this for Rust. There's no harm in having the
programmer explicitly be able to turn off the checking at the block or
item level; some algorithms, such as hashing algorithms, rely on the
overflow semantics, after all. But it seems in the spirit of Rust (at
the risk of relying on a nebulous term) to be as safe as possible by
default, and so I'd like to propose exploring opt-out overflow checking
for integers at some point in the future.
Thoughts?
Patrick
* That said, Microsoft seems to have put more effort than most into
detecting integer overflows in its huge C++ codebases, both through
fairly sophisticated static analysis [1] and through dynamic checks with
the SafeInt library [2]. Choice quote: "SafeInt is currently used
extensively throughout Microsoft, with substantial adoption within
Office and Windows."
[1]: http://research.microsoft.com/pubs/80722/z3prefix.pdf
[2]: http://safeint.codeplex.com/
_______________________________________________
Rust-dev mailing list
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
