Segfault in safe Rust when compiling with optimisations

[Wilfred]

#![feature(box_syntax, box_patterns)]

use std::num::Wrapping;

#[derive(Debug, Clone)]
pub enum Instruction {
    Increment {
        amount: Wrapping<i8>,
    },
    Loop(Vec<Box<Instruction>>),
}

/// Defines a method on iterators to map a function over all loop bodies.
trait MapLoopsExt: Iterator<Item=Box<Instruction>> {
    fn map_loops<F>(&mut self, f: F) -> Vec<Box<Instruction>>
        where F: Fn(Vec<Box<Instruction>>) -> Vec<Box<Instruction>>
    {
        self.map(|instr| {
            match instr {
                box Instruction::Loop(body) => box Instruction::Loop(f(body)),
                other => other
            }
        }).collect()
    }
}

impl<I> MapLoopsExt for I where I: Iterator<Item=Box<Instruction>> { }

pub fn remove_dead_loops(instrs: Vec<Box<Instruction>>) -> Vec<Box<Instruction>> {
    instrs.clone()
          .into_iter()
          .enumerate()
          .map(|(_, instr)| instr)
          .map_loops(remove_dead_loops)
}

fn main() {
    let mut instrs = vec![];
    instrs = remove_dead_loops(instrs);
    println!("{:?}", instrs);
}

Compiling and running it:

$ rustc --version
rustc 1.6.0-nightly (1805bba39 2015-11-26)

$ rustc main.rs
$ ./main
[]

$ rustc main.rs -C opt-level=3
$ ./main
[1]    4179 segmentation fault (core dumped)  ./main

[thepowersgang]

Reproduction without box patterns:

#[derive(Debug, Clone)]
pub enum Instruction {
    Increment {
        amount: ::std::num::Wrapping<i8>,
    },
    Loop(Vec<Box<Instruction>>),
}

/// Defines a method on iterators to map a function over all loop bodies.
trait MapLoopsExt: Iterator<Item=Box<Instruction>> {
    fn map_loops<F>(&mut self, f: F) -> Vec<Box<Instruction>>
        where F: Fn(Vec<Box<Instruction>>) -> Vec<Box<Instruction>>
    {
        self.map(|instr| {
            match *instr {
                Instruction::Loop(body) => Box::new( Instruction::Loop(f(body)) ),
                other => Box::new(other)
            }
        }).collect()
    }
}

impl<I> MapLoopsExt for I where I: Iterator<Item=Box<Instruction>> { }

/// Remove any loops where we know the current cell is zero.
pub fn remove_dead_loops(instrs: Vec<Box<Instruction>>) -> Vec<Box<Instruction>> {
    instrs.clone()
          .into_iter()
          .enumerate()
          .map(|(_, instr)| instr)
          .map_loops(remove_dead_loops)
}

fn main() {
    let mut instrs = vec![];
    instrs = remove_dead_loops(instrs);
    println!("{:?}", instrs);
}

Running in valgrind (rustc 1.rs -O -g) gives

==2557== Invalid read of size 1
==2557==    at 0x10F71A: call_once (ops.rs:1813)
==2557==    by 0x10F71A: map<Box<1::Instruction>,&mut closure> (option.rs:427)
==2557==    by 0x10F71A: iter::_$LT$impl$GT$::next::next::h16905190649762655698 (iter.rs:3267)
==2557==    by 0x10E0AE: from_iter<core::iter::Map<&mut core::iter::Map<core::iter::Enumerate<collections::vec::IntoIter<Box<1::Instruction>>>, closure>, closure>> (vec.rs:1239)
==2557==    by 0x10E0AE: collect<core::iter::Map<&mut core::iter::Map<core::iter::Enumerate<collections::vec::IntoIter<Box<1::Instruction>>>, closure>, closure>,collections::vec::Vec<Box<1::Instruction>>> (iter.rs:1461)
==2557==    by 0x10E0AE: map_loops<core::iter::Map<core::iter::Enumerate<collections::vec::IntoIter<Box<1::Instruction>>>, closure>,fn(collections::vec::Vec<Box<1::Instruction>>) -> collections::vec::Vec<Box<1::Instruction>>> (1.rs:17)
==2557==    by 0x10E0AE: remove_dead_loops::hee4c54714bae2292bda (1.rs:30)
==2557==    by 0x110DA4: main::hbe4f3ed567dbb481Bda (1.rs:39)
==2557==    by 0x118EF4: sys_common::unwind::try::try_fn::h13155858200411868877 (in /home/tpg/1)
==2557==    by 0x116A98: __rust_try (in /home/tpg/1)
==2557==    by 0x118B96: rt::lang_start::h45458ea0787b3e00e0x (in /home/tpg/1)
==2557==    by 0x5491A3F: (below main) (libc-start.c:289)
==2557==  Address 0x0 is not stack'd, malloc'd or (recently) free'd

[thepowersgang]

Two changes that have eliminated the crash:

• Removing the data from Instruction::Increment
• Rewriting the match to mem::replace in and out

        self.map(|mut instr| {
            if let Instruction::Loop(ref mut body) = *instr {
                *body = f( ::std::mem::replace(body, Vec::new()) );
            }
            instr
        }).collect()

[Ms2ger]

A little simpler:

pub enum Instruction {
    Increment(i8),
    Loop(Vec<Box<Instruction>>),
}

/// Defines a method on iterators to map a function over all loop bodies.
fn map_loops<F, I>(it: I, f: F) -> Vec<Box<Instruction>>
    where F: Fn(Vec<Box<Instruction>>) -> Vec<Box<Instruction>>,
          I: Iterator<Item=Box<Instruction>>
{
    it.map(|instr| {
        match *instr {
            Instruction::Loop(body) => Box::new( Instruction::Loop(f(body)) ),
            other => Box::new(other)
        }
    }).collect()
}

/// Remove any loops where we know the current cell is zero.
pub fn remove_dead_loops(instrs: Vec<Box<Instruction>>) -> Vec<Box<Instruction>> {
    map_loops(instrs.into_iter()
          .enumerate()
          .map(|(_, instr)| instr), remove_dead_loops)
}

fn main() {
    let mut instrs = vec![];
    instrs = remove_dead_loops(instrs);
    println!("{:?}", instrs.len());
}

[mitaa]

pub enum Instruction {
    Increment(i8),
    Loop(Box<Box<()>>),
}

fn main() {
    let instrs: Option<(u8, Box<Instruction>)> = None;
    instrs.into_iter()
          .map(|(_, instr)| instr)
          .map(|instr| match *instr { _other => {} })
          .last();
}

[thepowersgang]

@mitaa - That code leads to main being just ud2. May or may not be related.

00000000000054d0 <_ZN4main20h5435d5ad9987115aoaaE>:
    54d0:       55                      push   %rbp
    54d1:       48 89 e5                mov    %rsp,%rbp
    54d4:       0f 0b                   ud2    
    54d6:       66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
    54dd:       00 00 00 

[arielb1]

cc @dotdash

[dotdash]

@mitaa's example doesn't lead directly to ud2 for me. For some reason, the second closure is getting called there though, with instr being a nullptr, i.e. map is calling the closure with a None value. Not sure why that happens yet.

[dotdash]

It's our null check elimination pass. At some point, the optimizer replaces something like

%cmp = icmp eq i8* %ptr, null
%thing = getelementptr i8, i8* %ptr, i64 0
%ptr = select i1 %cmp, i8* null, i8* %thing
%cond = icmp eq i8* %ptr, null
br i1 %cond, label %none, label %some

with just

%ptr = getelementptr inbounds i8, i8* %ptr, i64 0
%cond = icmp eq i8* %ptr, null
br i1 %cond, label %none, label %some

And then the null check elimination pass turns that into

%ptr = getelementptr inbounds i8, i8* %ptr, i64 0
%cond = icmp eq i8* %ptr, null
br i1 false, label %none, label %some

[alexcrichton]

Interesting! I'd personally be ok just removing that pass from our LLVM build until we can get around to fixing this.

[dotdash]

Same for me. I wonder how much the pass even does for us now.

[dotdash]

As I'm too lazy to perform a detailed analysis of the changes, here's a plain size comparison:

With the pass enabled:

   text    data     bss     dec     hex filename
   9021   38039       8   47068    b7dc libarena-71b07a99.so
  32907   12731       4   45642    b24a libflate-71b07a99.so
  19346   40102       8   59456    e840 libfmt_macros-71b07a99.so
  60612   69884       4  130500   1fdc4 libgetopts-71b07a99.so
  12470   47663       8   60141    eaed libgraphviz-71b07a99.so
  25720   23692      24   49436    c11c liblog-71b07a99.so
  49696  103757       8  153461   25775 librbml-71b07a99.so
3326326 3204586      32 6530944  63a780 librustc-71b07a99.so
 216406   87608       8  304022   4a396 librustc_back-71b07a99.so
 303578  176852       4  480434   754b2 librustc_borrowck-71b07a99.so
  18669  148090       4  166763   28b6b librustc_data_structures-71b07a99.so
1914982  121522      12 2036516  1f1324 librustc_driver-71b07a99.so
 730220 1487287      16 2217523  21d633 librustc_front-71b07a99.so
 259036   65615       8  324659   4f433 librustc_lint-71b07a99.so
29220031        1896283  105744 31222058        1dc692a librustc_llvm-71b07a99.so
1555916  217260       4 1773180  1b0e7c librustc_metadata-71b07a99.so
 420615  164949       8  585572   8ef64 librustc_mir-71b07a99.so
 927001   39807       8  966816   ec0a0 librustc_platform_intrinsics-71b07a99.so
  39483   11805       8   51296    c860 librustc_plugin-71b07a99.so
  89501   21744       8  111253   1b295 librustc_privacy-71b07a99.so
 408297  163572       4  571873   8b9e1 librustc_resolve-71b07a99.so
2255972  712481      12 2968465  2d4b91 librustc_trans-71b07a99.so
1733482  559332       4 2292818  22fc52 librustc_typeck-71b07a99.so
3183929  702455      24 3886408  3b4d48 librustdoc-71b07a99.so
 162448  496300      16  658764   a0d4c libserialize-71b07a99.so
1625883 1808437    5912 3440232  347e68 libstd-71b07a99.so
3993545 3045683      24 7039252  6b6914 libsyntax-71b07a99.so
 139879   87268       4  227151   3774f libterm-71b07a99.so
 215919  126614      16  342549   53a15 libtest-71b07a99.so

With the pass disabled:

   text    data     bss     dec     hex filename
   9021   38037       8   47066    b7da libarena-71b07a99.so
  32863   12725       8   45596    b21c libflate-71b07a99.so
  19346   40109       8   59463    e847 libfmt_macros-71b07a99.so
  60572   69879       8  130459   1fd9b libgetopts-71b07a99.so
  12470   47663       8   60141    eaed libgraphviz-71b07a99.so
  25756   23682      24   49462    c136 liblog-71b07a99.so
  49680  103762       4  153446   25766 librbml-71b07a99.so
3327398 3204506      32 6531936  63ab60 librustc-71b07a99.so
 216430   87619       4  304053   4a3b5 librustc_back-71b07a99.so
 302458  176868       4  479330   75062 librustc_borrowck-71b07a99.so
  18669  148079       8  166756   28b64 librustc_data_structures-71b07a99.so
1914726  121504       8 2036238  1f120e librustc_driver-71b07a99.so
 730500 1487296      16 2217812  21d754 librustc_front-71b07a99.so
 259096   65640       8  324744   4f488 librustc_lint-71b07a99.so
29222032        1896257  105744 31224033        1dc70e1 librustc_llvm-71b07a99.so
1556264  217305       4 1773573  1b1005 librustc_metadata-71b07a99.so
 420447  164977       4  585428   8eed4 librustc_mir-71b07a99.so
 927001   39810       4  966815   ec09f librustc_platform_intrinsics-71b07a99.so
  39483   11804       4   51291    c85b librustc_plugin-71b07a99.so
  89557   21748       4  111309   1b2cd librustc_privacy-71b07a99.so
 408273  163546       4  571823   8b9af librustc_resolve-71b07a99.so
2256060  712538      12 2968610  2d4c22 librustc_trans-71b07a99.so
1733682  559378       4 2293064  22fd48 librustc_typeck-71b07a99.so
3183961  702420      24 3886405  3b4d45 librustdoc-71b07a99.so
 162432  496336      16  658784   a0d60 libserialize-71b07a99.so
1625667 1808398    5912 3439977  347d69 libstd-71b07a99.so
3993465 3045787      24 7039276  6b692c libsyntax-71b07a99.so
 139883   87270       8  227161   37759 libterm-71b07a99.so
 215891  126621      16  342528   53a00 libtest-71b07a99.so

Which suggests that the effects of the pass are pretty minor. It was probably worth more back when it was introduced because we had fewer means of marking things as non-null in LLVM. Now that we're using thing like !nonnull on loads and passing fat pointers as separate values, marking the data pointer as nonnull, I guess LLVM can already do most of the optimizations that this pass did in the pass.

So I almost feel inclined to just drop the pass completely instead of just disabling it. Opinions?

cc @rust-lang/compiler

[brson]

This happens on the beta channel too.

[ranma42]

@dotdash both transformations look legitimate to me: %ptr is always dereferenced, thus it should be guaranteed to either fault (SEGV?) or be non-null. Is it possible that there is a codeine issue?

How could I try to reproduce your results? Is it sufficient to compile without optimisation and to run them manually with opt?

[dotdash]

@ranma42 Yes, that should work to reproduce it, if you use opt from your rust build that still has the NCE pass.

I'm not sure where you're seeing a dereference there though. In the original IR, the deref only happens when the pointer is non-null. There's a slight mistake in the IR samples above, because I reused the name %ptr and forgot the inbounds on the first GEP, here's a fixed version:

%cmp = icmp eq i8* %ptr, null
%thing = getelementptr inbounds i8, i8* %ptr, i64 0
%ptr2 = select i1 %cmp, i8* null, i8* %thing
%cond = icmp eq i8* %ptr2, null
br i1 %cond, label %none, label %some

Here, %ptr2 will be null if %ptr is null, and %thing otherwise. So if %ptr is null, we'll take the branch to %none and all is good.

Now, after the first transformation we have:

%ptr2 = getelementptr inbounds i8, i8* %ptr, i64 0
%cond = icmp eq i8* %ptr2, null
br i1 %cond, label %none, label %some

And that happened because it assumed that %thing will be null if %ptr is null, which is a direct contradiction to the assumption upon which the NCE pass is based, because %thing is the result of an inbounds GEP.

[ranma42]

Sorry, you're right, there is no dereference; also, with the full names it is definitely easier to read :)

I am not completely sure about this, but I am afraid it might be the expected behaviour of LLVM poison values :\

In the first code, if %ptr is not null, everything should evaluate to this:

%cmp = false
%thing = %ptr
%ptr2 = %ptr
%cond = false
br label %some

If %ptr is null, instead:

%cmp = true
%thing = poison
%ptr2 = poison ; "Values other than phi nodes depend on their operands." :\
%cond = poison
br i1 %cond, label %none, label %some

In particular, I am unsure whether "%ptr2 will be null if %ptr is null" is correct, given the poison propagation rules from http://llvm.org/releases/3.7.0/docs/LangRef.html#poisonvalues
There is an open bug against the documentation of these rules (and in particular of their interaction with select) https://llvm.org/bugs/show_bug.cgi?id=20895
It looks like there is some consensus that select should not be poisoned as other operations, but it is now unclear to me what LLVM is doing and what it is supposed to do :(