overlong bit shifts cause undefined behaviour

1 >> 24353125315

At some point we discussed this in a meeting and decided it was acceptable.

@nikomatsakis

@nikomatsakis: it's not just an unspecified result as I previously thought though, it breaks memory safety

Do you have a concrete example where this leads to breaking memory safety? I can imagine how it might theoretically happen (that is, the behavior of the program as a whole is technically undefined), but I'm not sure that it actually does? I guess I can imagine some compiler saying that "since i1 >> i2 implies i2 < 32, then I'll do some wacky optimization to some expression involving i2..."

@nikomatsakis

@nikomatsakis: LLVM won't reserve a register for the return value, and will just read arbitrary registers on a read of the value, so for example a bounds check could fail to work

@thestinger

@thestinger return value of what function? read of what value? Can you spell it out more?

For example, a pattern like this:

let mut xs = [1, 2, 3];
let index = 1 >> 128; // this is `undef`
xs[index] = 100;

The indexing operation will essentially expand to this:

if index < 3 {
    *unsafe_index(xs, index) = 100;
} else {
    fail_bounds_check(...);
}

The index value as read for the comparison may be different than the value passed to unsafe_index.

http://llvm.org/docs/LangRef.html#undefined-values

In practice, it likely won't be in most cases, but in a more complex example where there was register pressure it would be.

The key part:

an ‘undef‘ “variable” can arbitrarily change its value over its “live range”. This is true because the variable doesn’t actually have a live range. Instead, the value is logically read from arbitrary registers that happen to be around when needed, so the value is not necessarily consistent over time.

Nominating.

I see. Fascinating! Is there a way to "capture" an undefined value and make it constant? For example, storing it to a stack slot and reading it back? (Presumably this load/store could be optimized away, so prob not). If so, we could capture the output of shift operations in this way.

Accepted for P-backcompat lang. There are a variety of ways to deal with this. We need to choose one. Will discuss further (e.g. in tues mtg).

I don't think this is backwards incompatible at a language level. It will not cause code that was working OK to stop working. Nominating.

changing priority to P-high. not assigning to 1.0 milestone.

auto merge of #15324 : sneves/rust/master, r=alexcrichton

@pcwalton

@pcwalton Is it not true that the logic of your last comment generalize to cover e.g. "integer overflow is undefined behavior.", in the sense that one could argue "code that is not exercising the conditions that yield undefined behavior will continue to work fine" in that scenario too?

I had thought that we considered it an important property that we actually tie down the semantics for operations in order to not head off into the undefined behavior weeds.

(Sorry for revisiting an old topic; it came up on IRC.)

context for previous comment: https://botbot.me/mozilla/rust-internals/2014-10-01/?msg=22667069&page=5

It's not fixed for shifts by constants either. The optional warning doesn't remove the responsibility of the compiler to prevent memory unsafety.

Currently, the following code panics in debug mode but runs fine in release mode:

fn main() {
    let sh = 32;
    assert_eq!(0, 1_i32 << sh);
}

(Or try it in the playpen.)

I am not sure whether this is by design or whether it is a bug, but either way, the documentation of shl nor the documentation of i32 mentions this behaviour.

The overflow RFC addresses this, and I have a bug open to reconcile all RFCs with the reference, so this will be taken care of as part of that.

This is a memory safety hole in the implementation. It's an issue regardless of how the language is intended to work per RFCs...

@steveklabnik

@steveklabnik How does the overflow RFC address this?

Sorry, by 'address' I mean a decision was made, and I'll be documenting the result. Not that it's any different than today.

This bug isn't asking for a change in semantics, it's filed to cover a known memory safety hole in the language. The fact that a clear solution has been specified doesn't mean the bug is fixed... pretending memory safety holes don't exist in the implementation doesn't make them go away.

Agreed this issue should not be closed until UB in safe Rust does not occur.

I don't think the RFC addresses this issue at all. Under "unresolved questions", it lists "shifts by an excessive number of bits". It just proposes debug assertions and doesn't prevent undefined behavior in release builds.

@ruud-v-a

Here is a variant of @ruud-v-a 's example that assert fails (in different places) in both -O0 and -O2 modes. (It was adapted from #23551.)

#![allow(exceeding_bitshifts)]

fn id<T>(x: T) -> T { x }

fn main() {
    let sh = 32;
    assert_eq!(0, 1_i32 << 32);     // note that this line "is the same" as the two below
    assert_eq!(0, 1_i32 << sh);     // fails here with -O0
    assert_eq!(0, 1_i32 << id(sh)); // fails here with -O2
}

playpen

@ben0x539

@ben0x539 I believe the intent of the RFC is to ensure that the fallback behaviors, when reasonable, do not expose undefined behavior from LLVM.

In these cases, it seems like the fallbacks should simply mask-out the higher order bits as appropriate for each type.

Added panic-on-overflow for rhs of left and right shift expressions.

Navigation Menu

Repository navigation

overlong bit shifts cause undefined behaviour #10183

13 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

overlong bit shifts cause undefined behaviour #10183

Description

Activity

nikomatsakis commented on Oct 31, 2013

thestinger commented on Oct 31, 2013

nikomatsakis commented on Oct 31, 2013

thestinger commented on Oct 31, 2013

nikomatsakis commented on Oct 31, 2013

thestinger commented on Oct 31, 2013

thestinger commented on Oct 31, 2013

brson commented on Oct 31, 2013

nikomatsakis commented on Oct 31, 2013

pnkfelix commented on Nov 7, 2013

pcwalton commented on Nov 22, 2013

pnkfelix commented on Dec 19, 2013

pnkfelix commented on Oct 1, 2014

pnkfelix commented on Oct 1, 2014

13 remaining items

thestinger commented on Nov 25, 2014

ruuda commented on Feb 16, 2015

steveklabnik commented on Feb 16, 2015

thestinger commented on Feb 17, 2015

srh commented on Feb 17, 2015

steveklabnik commented on Feb 17, 2015

thestinger commented on Feb 17, 2015

Gankra commented on Feb 17, 2015

ben0x539 commented on Feb 17, 2015

pnkfelix commented on Mar 20, 2015

pnkfelix commented on Mar 20, 2015

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions