No range integer type? Saftey beyond memory?

classic Classic list List threaded Threaded
24 messages Options
12
Reply | Threaded
Open this post in threaded view
|

No range integer type? Saftey beyond memory?

tsam
I am very excited to hear about Rust because the world is greatly in need
of a language which increases safety and expressiveness without
compromising performance and this seems to be one of the motivations
behind Rust.

But I am concerned that ranged types are not a core part of the language,
or even overflow-checked machine types. Our profession should be
embarrassed that memory safety is still but it looks like Rust has a
chance of finally solving it. But memory safety is only one part of
creating reliable software.  Java has substantial memory safety, although
not as much as Rust, and still java software is full of bugs... perhaps a
higher defect rate than common C code once you correct for java's
verbosity.  I worry that once Rust fixes memory safety it will quickly be
time to replace Rust to correct all the other programmer-traps.

On example is overflow. This is a common source of flaws in C/C++
software. Instrumenting to detect overflow is difficult, and it is
difficult or impossible to determine the permitted ranges output from
library functions in order to by-hand statically certify software against
overflow. Tools like valgrind make memory safety often fairly painless but
overflow and other kinds of logic flaws cannot be easily statically or
dynamically detected because the languages (and machine code) do not
express enough for the machine to tell when the behavior is wrong.

In Rust (like C) there doesn't appear to be any way to access the
processor flags to cheaply detect overflow on machine types, so writing
your "safe integer objects" will likely have poor performance and of
course not work with the standard libraries. Integrated ranged types would
also be synergistic with memory safety since a function which takes
limited-range inputs can sometimes be statically proven memory-safe when
it couldn't otherwise be, allowing the boundary check to be hoisted out of
functions entirely even across closed-source-library boundaries when their
interfaces are range constrained.

Some C compilers now offer an int128 type that uses the fast hardware
carry support, which makes certain kinds of overflow safety easier (for
example 64bit x 64bit cannot overflow int128) as long as you don't mind
non-portable code, but it doesn't appear that Rust has this either.

Overflow is something that ada seems to handle well, but ada doesn't
really seem to be in the running for a wide spread next language outside
of certain niches.

I hope some thought has been given to how greater safety could be added
later without making an inconsistent mess of the language.

In any case, thank you for the exciting new language!


_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Graydon Hoare
On 21/04/2013 12:09 AM, [hidden email] wrote:

> I worry that once Rust fixes memory safety it will quickly be
> time to replace Rust to correct all the other programmer-traps.

Yeah. There are unfortunately always limits and compromises when making
a real language. Rust is attacking a very difficult niche so we have to
spend a lot of energy on things that are not strictly about safety. But
I appreciate your concern.

> In Rust (like C) there doesn't appear to be any way to access the
> processor flags to cheaply detect overflow on machine types

It would be done with some per-platform inline asm (which we support
now), or intrinsics, or an attribute on (say) newtyped integral types.
Any of these would probably be ok. The attribute form would make it part
of the type, so you'd wind up with checks performed on cast boundaries
as well as any non-approximated operations.

> your "safe integer objects" will likely have poor performance and of
> course not work with the standard libraries.

I believe any such integration -- inline asm, intrinsics or attribute --
would be similar, performance-wise. Maybe LLVM's scheduler could do a
better job with them if it knows more about the instruction (an argument
for intrinsics), and if it knows about the type range itself it may
eliminate certain branches as dead code, but otherwise inlining should
boil off most of the abstractions equivalently.

> Integrated ranged types would
> also be synergistic with memory safety since a function which takes
> limited-range inputs can sometimes be statically proven memory-safe when
> it couldn't otherwise be, allowing the boundary check to be hoisted out of
> functions entirely even across closed-source-library boundaries when their
> interfaces are range constrained.

Not entirely. There are always limited approximations at work in these
things; range checks can only be statically eliminated in some cases
when the approximation is tight, otherwise it has to be repeated on each
potentially range-violating arithmetic operation.

LLVM does expose range-limited types and, presumably, does some such
check-elimination. I'd not be opposed to absorbing this via a
well-integrated attribute on integer types.

We've also had some requests for a mechanism to enable overflow checking
on _all_ integer types within a given static or dynamic program extent,
using attributes. And similar things are going to be desirable wrt. the
floating point environment, which is trickier since it's latent in the
CPU state rather than the (static) operations performed. Again, I'd be
happy to work through developing patches for this and exploring the
problem space. It's a set of bugs usually swept under the rug in C.

> Overflow is something that ada seems to handle well, but ada doesn't
> really seem to be in the running for a wide spread next language outside
> of certain niches.

Agreed.

-Graydon

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Sebastian Sylvan
FWIW I'd *love* if all integer types could get efficient dynamic range checking turned on in Debug builds. So it wouldn't be a safety issue in the traditional sense because it would be disabled in shipping builds, but it would be great for catching bugs. Still needs to be efficient because Debug builds that aren't interactive don't get used for development.


On Mon, Apr 22, 2013 at 9:18 AM, Graydon Hoare <[hidden email]> wrote:
On 21/04/2013 12:09 AM, [hidden email] wrote:

I worry that once Rust fixes memory safety it will quickly be
time to replace Rust to correct all the other programmer-traps.

Yeah. There are unfortunately always limits and compromises when making a real language. Rust is attacking a very difficult niche so we have to spend a lot of energy on things that are not strictly about safety. But I appreciate your concern.


In Rust (like C) there doesn't appear to be any way to access the
processor flags to cheaply detect overflow on machine types

It would be done with some per-platform inline asm (which we support now), or intrinsics, or an attribute on (say) newtyped integral types. Any of these would probably be ok. The attribute form would make it part of the type, so you'd wind up with checks performed on cast boundaries as well as any non-approximated operations.


your "safe integer objects" will likely have poor performance and of
course not work with the standard libraries.

I believe any such integration -- inline asm, intrinsics or attribute -- would be similar, performance-wise. Maybe LLVM's scheduler could do a better job with them if it knows more about the instruction (an argument for intrinsics), and if it knows about the type range itself it may eliminate certain branches as dead code, but otherwise inlining should boil off most of the abstractions equivalently.


Integrated ranged types would
also be synergistic with memory safety since a function which takes
limited-range inputs can sometimes be statically proven memory-safe when
it couldn't otherwise be, allowing the boundary check to be hoisted out of
functions entirely even across closed-source-library boundaries when their
interfaces are range constrained.

Not entirely. There are always limited approximations at work in these things; range checks can only be statically eliminated in some cases when the approximation is tight, otherwise it has to be repeated on each potentially range-violating arithmetic operation.

LLVM does expose range-limited types and, presumably, does some such check-elimination. I'd not be opposed to absorbing this via a well-integrated attribute on integer types.

We've also had some requests for a mechanism to enable overflow checking on _all_ integer types within a given static or dynamic program extent, using attributes. And similar things are going to be desirable wrt. the floating point environment, which is trickier since it's latent in the CPU state rather than the (static) operations performed. Again, I'd be happy to work through developing patches for this and exploring the problem space. It's a set of bugs usually swept under the rug in C.


Overflow is something that ada seems to handle well, but ada doesn't
really seem to be in the running for a wide spread next language outside
of certain niches.

Agreed.

-Graydon


_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev



--
Sebastian Sylvan

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Robert O'Callahan
In reply to this post by Graydon Hoare
On Tue, Apr 23, 2013 at 4:18 AM, Graydon Hoare <[hidden email]> wrote:
We've also had some requests for a mechanism to enable overflow checking on _all_ integer types within a given static or dynamic program extent, using attributes.

I, at least, made a request for overflow checking on all integer types, full stop :-). And I still want it; failure of obvious properties like "a >= 0 ===> a + b >= b" is just crazy, and I'm tired of living in crazy-land.

On the other hand, I don't see this as important for floating point types. Accumulating NaNs and infinities is much saner than simply producing the wrong answer, has seldom led to critical browser bugs in my experience, and I can't see how it would without an intervening conversion to integer type which would, of course, be checked. (OK, I can recall exactly one infinite-recursion bug involving NaNs that didn't require an integer conversion.)

Rob
--
q“qIqfq qyqoquq qlqoqvqeq qtqhqoqsqeq qwqhqoq qlqoqvqeq qyqoquq,q qwqhqaqtq qcqrqeqdqiqtq qiqsq qtqhqaqtq qtqoq qyqoquq?q qEqvqeqnq qsqiqnqnqeqrqsq qlqoqvqeq qtqhqoqsqeq qwqhqoq qlqoqvqeq qtqhqeqmq.q qAqnqdq qiqfq qyqoquq qdqoq qgqoqoqdq qtqoq qtqhqoqsqeq qwqhqoq qaqrqeq qgqoqoqdq qtqoq qyqoquq,q qwqhqaqtq qcqrqeqdqiqtq qiqsq qtqhqaqtq qtqoq qyqoquq?q qEqvqeqnq qsqiqnqnqeqrqsq qdqoq qtqhqaqtq.q"

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Graydon Hoare
On 22/04/2013 9:57 PM, Robert O'Callahan wrote:

> On Tue, Apr 23, 2013 at 4:18 AM, Graydon Hoare <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     We've also had some requests for a mechanism to enable overflow
>     checking on _all_ integer types within a given static or dynamic
>     program extent, using attributes.
>
>
> I, at least, made a request for overflow checking on all integer types,
> full stop :-). And I still want it; failure of obvious properties like
> "a >= 0 ===> a + b >= b" is just crazy, and I'm tired of living in
> crazy-land.

How much of a performance penalty is it worth? I believe you can trap
this in C presently with a gcc flag too (-ftrapv); but it's a flag
rarely turned on.

(I generally concur and wanted rust integers to overflow to bignums
originally! But I have had to retreat from such stances due to
complaints about performance / not-C-ness. I suspect the attribute
mechanism is the right approach for such pragmas; would it be acceptable
to put one attribute in each of your crates?)

-Graydon

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Daniel Micay
On Tue, Apr 23, 2013 at 1:43 PM, Graydon Hoare <[hidden email]> wrote:

> On 22/04/2013 9:57 PM, Robert O'Callahan wrote:
>>
>> On Tue, Apr 23, 2013 at 4:18 AM, Graydon Hoare <[hidden email]
>> <mailto:[hidden email]>> wrote:
>>
>>     We've also had some requests for a mechanism to enable overflow
>>     checking on _all_ integer types within a given static or dynamic
>>     program extent, using attributes.
>>
>>
>> I, at least, made a request for overflow checking on all integer types,
>> full stop :-). And I still want it; failure of obvious properties like
>> "a >= 0 ===> a + b >= b" is just crazy, and I'm tired of living in
>> crazy-land.
>
>
> How much of a performance penalty is it worth? I believe you can trap this
> in C presently with a gcc flag too (-ftrapv); but it's a flag rarely turned
> on.
>
> (I generally concur and wanted rust integers to overflow to bignums
> originally! But I have had to retreat from such stances due to complaints
> about performance / not-C-ness. I suspect the attribute mechanism is the
> right approach for such pragmas; would it be acceptable to put one attribute
> in each of your crates?)
>
> -Graydon

I don't really think you need an attribute, just good support for an
integer type in the library that traps the overflow and expands to a
big integer.

At the very least, the overhead would involve making integers 2 words
instead of 1 for a tag, adding a branch to every operation and also
adding a branch after almost every fixnum representation.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Vadim Chugunov
If all that's needed is the safety from overflow exploits, a better option would be to raise a condition on overflow.  That would avoid any size overhead.


On Tue, Apr 23, 2013 at 11:01 AM, Daniel Micay <[hidden email]> wrote:
On Tue, Apr 23, 2013 at 1:43 PM, Graydon Hoare <[hidden email]> wrote:
> On 22/04/2013 9:57 PM, Robert O'Callahan wrote:
>>
>> On Tue, Apr 23, 2013 at 4:18 AM, Graydon Hoare <[hidden email]
>> <mailto:[hidden email]>> wrote:
>>
>>     We've also had some requests for a mechanism to enable overflow
>>     checking on _all_ integer types within a given static or dynamic
>>     program extent, using attributes.
>>
>>
>> I, at least, made a request for overflow checking on all integer types,
>> full stop :-). And I still want it; failure of obvious properties like
>> "a >= 0 ===> a + b >= b" is just crazy, and I'm tired of living in
>> crazy-land.
>
>
> How much of a performance penalty is it worth? I believe you can trap this
> in C presently with a gcc flag too (-ftrapv); but it's a flag rarely turned
> on.
>
> (I generally concur and wanted rust integers to overflow to bignums
> originally! But I have had to retreat from such stances due to complaints
> about performance / not-C-ness. I suspect the attribute mechanism is the
> right approach for such pragmas; would it be acceptable to put one attribute
> in each of your crates?)
>
> -Graydon

I don't really think you need an attribute, just good support for an
integer type in the library that traps the overflow and expands to a
big integer.

At the very least, the overhead would involve making integers 2 words
instead of 1 for a tag, adding a branch to every operation and also
adding a branch after almost every fixnum representation.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev


_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Robert O'Callahan
In reply to this post by Graydon Hoare
On Wed, Apr 24, 2013 at 5:43 AM, Graydon Hoare <[hidden email]> wrote:
How much of a performance penalty is it worth? I believe you can trap this in C presently with a gcc flag too (-ftrapv); but it's a flag rarely turned on.

That's a hard question to answer, but if it cost only 1%, I'd say it's a no-brainer. If it cost 10%, I might say it's not worth it.

So the question is how much would it cost? I believe the answer will depend on whether the language also does array bounds checking, since there must be a significant amount of synergy between array bounds checking and overflow checking when you try to intelligently optimize them both. For that and other reasons I think it would be difficult to extrapolate from C to Rust (except maybe to establish an upper bound).

(I generally concur and wanted rust integers to overflow to bignums originally!

I do NOT want overflow to bignums. I don't think that's useful in a browser and would cause a larger performance penalty than necessary for the no-overflow common case. I think integer overflow should simply cause the task to fail.

Overflowing to bignums sounds way more expensive then just failing --- it would introduce internal polymorphism all over the place, and would tightly constrain the scheduling of overflow checks. If overflow simply causes the task to fail, then you (or your out-of-order CPU) can schedule overflow checking very freely.

I don't think bignums are useful in a browser because as a browser developer I will choose data types that cover the ranges of values I want to handle. If I think I need to handle integer values that don't fit in 32 bits, I'll use a 64-bit integer type, or a floating point type. Overflow always means I have a bug*. Overflows in the field usually mean my code is being maliciously attacked, in which case fail-fast is definitely the best thing to do.

* Sometimes developers use overflow to get modulo-2^N behavior (which is incorrect in C anyway), and intrinsic functions for those operations would be helpful.

But I have had to retreat from such stances due to complaints about performance / not-C-ness. I suspect the attribute mechanism is the right approach for such pragmas; would it be acceptable to put one attribute in each of your crates?)

Much better than nothing, but if the overhead of overflow checking is very low, I think the case for making it the default would be very strong.

Rob
--
q“qIqfq qyqoquq qlqoqvqeq qtqhqoqsqeq qwqhqoq qlqoqvqeq qyqoquq,q qwqhqaqtq qcqrqeqdqiqtq qiqsq qtqhqaqtq qtqoq qyqoquq?q qEqvqeqnq qsqiqnqnqeqrqsq qlqoqvqeq qtqhqoqsqeq qwqhqoq qlqoqvqeq qtqhqeqmq.q qAqnqdq qiqfq qyqoquq qdqoq qgqoqoqdq qtqoq qtqhqoqsqeq qwqhqoq qaqrqeq qgqoqoqdq qtqoq qyqoquq,q qwqhqaqtq qcqrqeqdqiqtq qiqsq qtqhqaqtq qtqoq qyqoquq?q qEqvqeqnq qsqiqnqnqeqrqsq qdqoq qtqhqaqtq.q"

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Robert O'Callahan
On Wed, Apr 24, 2013 at 11:25 AM, Robert O'Callahan <[hidden email]> wrote:
I don't think bignums are useful in a browser because as a browser developer I will choose data types that cover the ranges of values I want to handle. If I think I need to handle integer values that don't fit in 32 bits, I'll use a 64-bit integer type, or a floating point type. Overflow always means I have a bug*.

Well, in C and C++ it does, and of course that's what most browser developers are going to be used to.

If we could rely on checked overflows in Rust, then we could start to lean on that and declare that some tests that trigger overflow are simply tests where task failure is an acceptable result. (Offensive as this may to the cult of correctness, in practice priorities dictate we have to do this kind of thing all the time --- declare that a bug is not worth fixing as long as it's not exploitable.)

Rob
--
q“qIqfq qyqoquq qlqoqvqeq qtqhqoqsqeq qwqhqoq qlqoqvqeq qyqoquq,q qwqhqaqtq qcqrqeqdqiqtq qiqsq qtqhqaqtq qtqoq qyqoquq?q qEqvqeqnq qsqiqnqnqeqrqsq qlqoqvqeq qtqhqoqsqeq qwqhqoq qlqoqvqeq qtqhqeqmq.q qAqnqdq qiqfq qyqoquq qdqoq qgqoqoqdq qtqoq qtqhqoqsqeq qwqhqoq qaqrqeq qgqoqoqdq qtqoq qyqoquq,q qwqhqaqtq qcqrqeqdqiqtq qiqsq qtqhqaqtq qtqoq qyqoquq?q qEqvqeqnq qsqiqnqnqeqrqsq qdqoq qtqhqaqtq.q"

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Graydon Hoare
On 13-04-23 04:53 PM, Robert O'Callahan wrote:

> On Wed, Apr 24, 2013 at 11:25 AM, Robert O'Callahan
> <[hidden email] <mailto:[hidden email]>> wrote:
>
>     I don't think bignums are useful in a browser because as a browser
>     developer I will choose data types that cover the ranges of values I
>     want to handle. If I think I need to handle integer values that
>     don't fit in 32 bits, I'll use a 64-bit integer type, or a floating
>     point type. Overflow always means I have a bug*.
>
>
> Well, in C and C++ it does, and of course that's what most browser
> developers are going to be used to.
>
> If we could rely on checked overflows in Rust, then we could start to
> lean on that and declare that some tests that trigger overflow are
> simply tests where task failure is an acceptable result. (Offensive as
> this may to the cult of correctness, in practice priorities dictate we
> have to do this kind of thing all the time --- declare that a bug is not
> worth fixing as long as it's not exploitable.)

Sure. I'd be happy to look into this as a mode for rust; I don't think
we can expect to make it "always on", but we could possibly make it
"reasonably easy to turn on" on a crate-by-crate basis.

First thing to do is look into enabling it. There are a variety of
pieces lying around we could look into:

http://llvm.org/docs/LangRef.html#range-metadata
http://llvm.org/docs/LangRef.html#arithmetic-with-overflow-intrinsics
http://clang.llvm.org/docs/UsersManual.html#controlling-code-generation
http://embed.cs.utah.edu/ioc/

I suspect there's enough to work with there. It might require
duplicating some of the lowerings that clang does in rust's trans layer.

-Graydon
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Niko Matsakis
I think checked integer overflow could be a good idea, presuming the cost is reasonable, but I am somewhat skeptical of having it be enabled or disabled on a module-by-module basis. This would imply that if I move a function from one module to another, it stops working? It seems surprising. Having the overflow checking be based on the type seems more robust. But maybe this would not be a big issue in practice; after all, it's already the case that moving a function requires various corrections (name resolution etc) to account for the new scope. But somehow this feels "different" than those, because this would mean that compilation succeeds but the dynamic behavior silently changes.

In the past I had thought about saying that the unsized types (`uint`, `int`) are overflow checked but the sized types (`u32`, `i32`, etc) act as they do in C. But Roc's email made me reconsider if that is reasonable. Perhaps it's just too pat, and we would actually want a distinct family of "overflow-checked" types (perhaps a library, as Graydon suggests, though it seems like something that you might want to opt out of, rather than opt in).

Definitely a Milestone 2 consideration ;)


Niko



On Wed, Apr 24, 2013 at 5:37 PM, Graydon Hoare <[hidden email]> wrote:
On 13-04-23 04:53 PM, Robert O'Callahan wrote:
> On Wed, Apr 24, 2013 at 11:25 AM, Robert O'Callahan
> <[hidden email] <mailto:[hidden email]>> wrote:
>
>     I don't think bignums are useful in a browser because as a browser
>     developer I will choose data types that cover the ranges of values I
>     want to handle. If I think I need to handle integer values that
>     don't fit in 32 bits, I'll use a 64-bit integer type, or a floating
>     point type. Overflow always means I have a bug*.
>
>
> Well, in C and C++ it does, and of course that's what most browser
> developers are going to be used to.
>
> If we could rely on checked overflows in Rust, then we could start to
> lean on that and declare that some tests that trigger overflow are
> simply tests where task failure is an acceptable result. (Offensive as
> this may to the cult of correctness, in practice priorities dictate we
> have to do this kind of thing all the time --- declare that a bug is not
> worth fixing as long as it's not exploitable.)

Sure. I'd be happy to look into this as a mode for rust; I don't think
we can expect to make it "always on", but we could possibly make it
"reasonably easy to turn on" on a crate-by-crate basis.

First thing to do is look into enabling it. There are a variety of
pieces lying around we could look into:

http://llvm.org/docs/LangRef.html#range-metadata
http://llvm.org/docs/LangRef.html#arithmetic-with-overflow-intrinsics
http://clang.llvm.org/docs/UsersManual.html#controlling-code-generation
http://embed.cs.utah.edu/ioc/

I suspect there's enough to work with there. It might require
duplicating some of the lowerings that clang does in rust's trans layer.

-Graydon
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev


_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Graydon Hoare
On 26/04/2013 3:07 AM, Niko Matsakis wrote:

> I think checked integer overflow could be a good idea, presuming the
> cost is reasonable, but I am somewhat skeptical of having it be enabled
> or disabled on a module-by-module basis. This would imply that if I move
> a function from one module to another, it stops working? It seems
> surprising. Having the overflow checking be based on the type seems more
> robust. But maybe this would not be a big issue in practice; after all,
> it's already the case that moving a function requires various
> corrections (name resolution etc) to account for the new scope. But
> somehow this feels "different" than those, because this would mean that
> compilation succeeds but the dynamic behavior silently changes.

Yeah. This is tricky state to enforce. Reminds me a bit of locales, tbh.

If you think that's awful, allow me also to direct your attention to the
_global_ state that controls the interpretation of floating point
arithmetic. How on earth does a programmer influence that reliably, when
composing programs from subprograms with differing assumptions?
Save-and-reload at module-crossings? Attach the modes to types? Figure
out a subtype lattice for dispatching operations? Hahaha. Thankfully the
754 authors left all of this undefined, for us to struggle with.

There _is_ some interesting work in this space. I recommend browsing
through these notes:

http://grouper.ieee.org/groups/754/meeting-materials/2001-10-18-langdesign.pdf

and perhaps the Borneo design. It might (oh, interesting!) also
influence how we think about rounding modes on integer division. Weirdly.

> In the past I had thought about saying that the unsized types (`uint`,
> `int`) are overflow checked but the sized types (`u32`, `i32`, etc) act
> as they do in C. But Roc's email made me reconsider if that is
> reasonable. Perhaps it's just too pat, and we would actually want a
> distinct family of "overflow-checked" types (perhaps a library, as
> Graydon suggests, though it seems like something that you might want to
> opt out of, rather than opt in).

I think it has to be opt-in, yeah. Sadly. I mean, I wish we were living
in the world of hardware garbage collection and tagged memory words too,
and hensel codes had won out over floating point, and all our languages
had well defined total functional subsets with industrial strength
provers attached to them that we were legally obliged to use.

But some such dreams remain off the table when competing for market
acceptance with C++ :)

> Definitely a Milestone 2 consideration ;)

Maybe. At least consideration. I think any variant would have to be
additive (backwards compatible) simply because in languages like this,
it's _really_ not what people assume as the default.

We've already got in trouble for / trapping divide-by-zero by a
branch/fault rather than a signal; it hits inner loops and costs us
performance. Really.

(We don't currently have a way to route signals into task failure; we
will need this and hopefully the new UV-based scheduler will help here.
I believe it will.)

-Graydon


_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Florian Weimer
In reply to this post by Graydon Hoare
* Graydon Hoare:

> How much of a performance penalty is it worth? I believe you can trap
> this in C presently with a gcc flag too (-ftrapv); but it's a flag
> rarely turned on.

GCC cannot use the OF flag, but LLVM has overflow-checking
instructions, and Clang actually emits instructions using the OF flag
for operator new[]: <http://gcc.gnu.org/ml/gcc/2010-12/msg00154.html>

With undefined or trapping overflow, it's even more difficult to write
overflow checks.  GNAT addresses this by offering a mode which
evaluates comparisons with infinite precision (with appropriate
optimizations for common cases where full bignum arithmetic is not
necessary).  Ada allows suppressing an overflow exception as long as
the mathematically correct result is produced.

For a memory-safe language such as Java where pointer arithmetic or
equivalents are rare (although some native code wrappers contain
security-relevant range checks in Java code), overflow checking for
integer types is not absolutely essential.  For writing unsafe
modules, I imagine overflow checks whould be rather helpful.  For
Rust, the interaction with resource management would be tricky, I
think.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Robert O'Callahan
In reply to this post by Graydon Hoare
On Sat, Apr 27, 2013 at 4:23 AM, Graydon Hoare <[hidden email]> wrote:
I think it has to be opt-in, yeah. Sadly. I mean, I wish we were living in the world of hardware garbage collection and tagged memory words too, and hensel codes had won out over floating point, and all our languages had well defined total functional subsets with industrial strength provers attached to them that we were legally obliged to use.

I don't understand the relationship between those features and integer overflow checking. There are very strong reasons why those features haven't developed, and none of those reasons apply to integer overflow checking.


Definitely a Milestone 2 consideration ;)

Maybe. At least consideration. I think any variant would have to be additive (backwards compatible) simply because in languages like this, it's _really_ not what people assume as the default.

In my experience the default assumption is that integer overflow doesn't happen.

Just for fun I did "grep -F ' + '" and "grep -F ' - '" in some mozilla-central graphics, DOM and layout code:
gfx/thebes/*.cpp
gfx/cairo/cairo/src/*.c
content/base/src/*.cpp
content/html/content/src/*.cpp
layout/generic/*.cpp
and skimmed the results. I might have missed something, but I found only three occurrences of addition/subtraction operators where overflow seemed expected: two in hash functions in cairo-cache.c, and one in a hash function in cairo-misc.c.

Based on that data and previous experience with this code, I'm certain that those occurrences are vastly outweighed by handwritten code that tries to detect/avoid integer overflows, and also by arithmetic operations that are still vulnerable to overflow bugs in spite of those checks.

Furthermore, I wonder how many average C/C++ programmers know that overflow of unsigned values is defined but overflow of signed values is not. I expect that most people's assumptions are plain incorrect.

So I contend that integer overflow checking is more likely to prevent unexpected behavior than to cause it, especially when it really matters: in shipped code that's being attacked. Once in a while someone writing a hash function or similar will trip over, but it will be easy for them to detect and correct their mistake.

We've already got in trouble for / trapping divide-by-zero by a branch/fault rather than a signal; it hits inner loops and costs us performance. Really.

Was this some unsafe-language benchmark shootout? Even if those are important due to some "Rust is slow, clinical tests prove it" bogo-PR effect, I assume you would disable overflow checking along with array-bounds checks in unsafe Rust code.

Rob
--
q“qIqfq qyqoquq qlqoqvqeq qtqhqoqsqeq qwqhqoq qlqoqvqeq qyqoquq,q qwqhqaqtq qcqrqeqdqiqtq qiqsq qtqhqaqtq qtqoq qyqoquq?q qEqvqeqnq qsqiqnqnqeqrqsq qlqoqvqeq qtqhqoqsqeq qwqhqoq qlqoqvqeq qtqhqeqmq.q qAqnqdq qiqfq qyqoquq qdqoq qgqoqoqdq qtqoq qtqhqoqsqeq qwqhqoq qaqrqeq qgqoqoqdq qtqoq qyqoquq,q qwqhqaqtq qcqrqeqdqiqtq qiqsq qtqhqaqtq qtqoq qyqoquq?q qEqvqeqnq qsqiqnqnqeqrqsq qdqoq qtqhqaqtq.q"

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Jack Moffitt
> Was this some unsafe-language benchmark shootout? Even if those are
> important due to some "Rust is slow, clinical tests prove it" bogo-PR
> effect, I assume you would disable overflow checking along with array-bounds
> checks in unsafe Rust code.

Clojure basically does this. By default, math operations (even on
primitives) are checked for overflow and throw an exception if
overflow occurs. There is a dynamic variable, *unchecked-math*, which
will allow silent overflow when set to true. It defaults, correctly
IMO, to false. There are also operations which will promote to
BigIntegers on overflow, but you must use them explicitly (+', *',
etc), as they always return boxed numbers. More can be found in the
Math Operations[1] section of the numerics documentation. The Clojure
team chose this path after trying several others as being the most
practical option. It's still quite fast, but also safe.

I would like to see checked math by default, which can be disabled
with some unsafe block. I would also like it if unsafe blocks
described what safety guarantees they gave up, so I could write code
like:

unsafe(math) { x + y }

to get the fast path where overflow is not checked.

[1] http://dev.clojure.org/display/doc/Documentation+for+1.3+Numerics

jack.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Mikhail Zabaluev
Hi,

2013/4/29 Jack Moffitt <[hidden email]>:
>
> I would like to see checked math by default, which can be disabled
> with some unsafe block. I would also like it if unsafe blocks
> described what safety guarantees they gave up, so I could write code
> like:
>
> unsafe(math) { x + y }
>
> to get the fast path where overflow is not checked.

I don't entirely dislike this, but I'm afraid this will turn
real-world code into a "broken window" land. Of course there is a
school of software engineering that says you should first make the
program correct and then profile and selectively optimize the hot
spots, but this would bring Rust dangerously close to the
slow-unless-made-ugly territory where I found Haskell after looking at
their much touted qsort example...

As was pointed out earlier with Mozilla source code, integer overflows
"do not happen". Probably because, in security-conscious code, you are
supposed to validate your inputs for your actual expected range, and
when you do, built-in overflow checks are just unnecessary overhead.
OTOH, Rust does array bound checks, but hopefully the optimizer can
turn these into loop boundary checks for inner loops where performance
matters.

This topic is annoyingly a tug of war between academics who want
mathematical rigor above all else (see also the discussion on integer
division), the folks who want safety above all else, and people who
just want a practical system programming language with modern
concurrency features built in. I'm in the latter category: I don't
mind protection against shooting myself in the foot (outside unsafe
blocks), but not at a significant runtime cost, compared to the
existing languages where I have already learned not to have my foot
shot at every so often. I agree with Graydon's assessment in the
modulo thread that Rust belongs with the languages where adding a
conditional jump after every integer arithmetic operation is
considered unacceptable performance-wise. That said, I can't see why
there should not appear a nice scripting language based on the Rust
runtime some day, where overflow safety, arbitrary precision math, and
variously ramified division modes could be enabled for arithmetic
operators.

Best regards,
  Mikhail
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Jack Moffitt
> As was pointed out earlier with Mozilla source code, integer overflows
> "do not happen". Probably because, in security-conscious code, you are
> supposed to validate your inputs for your actual expected range, and
> when you do, built-in overflow checks are just unnecessary overhead.

If you're referring to Robert's comments, then I read them exactly the
opposite way. He did mention that overflow to BigInts wasn't needed,
but he is on the wants checked math side.

I agree that this is a tradeoff, and that there is probably some
performance loss at which it doesn't make sense. Until we have data on
how expensive such a feature is, we can't make much progress in that
particular debate. I just wanted to note my preference for having it
default to on if it didn't cost too much, whatever "cost too much"
might mean :)

jack.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Matthieu Monrocq



On Mon, Apr 29, 2013 at 6:33 PM, Jack Moffitt <[hidden email]> wrote:
> As was pointed out earlier with Mozilla source code, integer overflows
> "do not happen". Probably because, in security-conscious code, you are
> supposed to validate your inputs for your actual expected range, and
> when you do, built-in overflow checks are just unnecessary overhead.

If you're referring to Robert's comments, then I read them exactly the
opposite way. He did mention that overflow to BigInts wasn't needed,
but he is on the wants checked math side.

I agree that this is a tradeoff, and that there is probably some
performance loss at which it doesn't make sense. Until we have data on
how expensive such a feature is, we can't make much progress in that
particular debate. I just wanted to note my preference for having it
default to on if it didn't cost too much, whatever "cost too much"
might mean :)

jack.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev

It might be interesting to check how Clang integrated UBSan and its performance implications. I know there was some work using "cold" functions and "expect" hints to teach LLVM than the "undefined" branch (and callback) were to be very rare so that it could optimize the code taking them out of the hot path.

You can check a blog article on usage of UBSan here [1], and rebound to the User's Manual from there; might be interesting to benchmark the code produced by Clang with/without integer overflow detection (and just that, UBSan include many other validations) to see what LLVM can do with it.

-- Matthieu

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Graydon Hoare
In reply to this post by Robert O'Callahan
On 13-04-28 03:03 PM, Robert O'Callahan wrote:
> I don't understand the relationship between those features and integer
> overflow checking. There are very strong reasons why those features
> haven't developed, and none of those reasons apply to integer overflow
> checking.

Sure. It costs performance. That's the reason in all such cases. It
sucks and I'm sad about it and _that argument in those words_ is what I
hear over and over from our target audience. Anything that costs
performance in the default case is resisted strenuously.

> Based on that data and previous experience with this code, I'm certain
> that those occurrences are vastly outweighed by handwritten code that
> tries to detect/avoid integer overflows, and also by arithmetic
> operations that are still vulnerable to overflow bugs in spite of those
> checks.

For the most part, nobody checks. They weighed the cost of those errors
against the potential performance loss and decided they would prefer to
go fast.

I'm very sad that people in this space are so quick to trade correctness
for speed. But they do. And they pick languages (in this space) based on
perception of speed. From benchmarks and informal experiments.

> So I contend that integer overflow checking is more likely to prevent
> unexpected behavior than to cause it, especially when it really matters:
> in shipped code that's being attacked. Once in a while someone writing a
> hash function or similar will trip over, but it will be easy for them to
> detect and correct their mistake.

We're not disagreeing on that.

> Was this some unsafe-language benchmark shootout? Even if those are
> important due to some "Rust is slow, clinical tests prove it" bogo-PR
> effect, I assume you would disable overflow checking along with
> array-bounds checks in unsafe Rust code.

Yes. I'm not sure how else to put this: we're in an unfair fight. We're
trying to ship a language that is safer than C++ but is _being
benchmarked against C++_. And in a market that generally picks
"whatever's fastest". Picking defaults that make us systematically
slower than C++ is problematic.

Since the speed is not before us in quantified terms, though, I suggest
deferring this for a bit: we can implement the feature as a check, and
set the flag to default allow, warn, deny, or forbid based on the
results of performance measurements. If it's trivially cheap, by all
means turn it on by default.

-Graydon

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: No range integer type? Saftey beyond memory?

Thad Guidry

Rust user base on a used napkin:

80% want safety.
100% want speed.
10% want it all.
50% do not care.

Rust will be aiming to please those 80% ...that also happen to like tacos and bacon and wont complain because they will be happy, full, productive, and content.

Order your t-shirts now. :)

-Thad


_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
12