wasm32-unknown-unknown results in out of bounds memory access

[jiayihu]

I tried this code:

#![allow(non_snake_case)]

fn init_array<const M: usize, const N: usize>(
    m: usize,
    n: usize,
    A: &mut [[f32; N]; M],
    r: &mut [f32; M],
    p: &mut [f32; N],
) {
    for i in 0..n {
        p[i] = (i % n) as f32 / n as f32;
    }
    for i in 0..m {
        r[i] = (i % m) as f32 / m as f32;
        for j in 0..n {
            A[i][j] = (i * (j + 1) % m) as f32 / m as f32;
        }
    }
}

fn kernel_bicg<const M: usize, const N: usize>(
    m: usize,
    n: usize,
    A: &[[f32; N]; M],
    s: &mut [f32; N],
    q: &mut [f32; M],
    p: &[f32; N],
    r: &[f32; M],
) {
    for i in 0..n {
        s[i] = 0.0;
    }
    for i in 0..m {
        q[i] = 0.0;
        for j in 0..n {
            s[j] = s[j] + r[i] * A[i][j];
            q[i] = q[i] + A[i][j] * p[j];
        }
    }
}

#[no_mangle]
pub extern "C" fn bench() {
    const M: usize = 1;
    const N: usize = 1;

    let mut A = [[0_f32; N]; M];
    let mut s = [0_f32; N];
    let mut q = [0_f32; M];
    let mut p = [0_f32; N];
    let mut r = [0_f32; M];

    init_array(M, N, &mut A, &mut r, &mut p);
    kernel_bicg(M, N, &A, &mut s, &mut q, &p, &r);
}

Here is the wat file:

Backtrace

(module
  (type $t0 (func))
  (func $bench (type $t0)
    (local $l0 i32) (local $l1 i32) (local $l2 i32) (local $l3 f32)
    global.get $g0
    i32.const 32
    i32.sub
    local.set $l0
    i32.const 0
    local.set $l1
    block $B0
      loop $L1
        local.get $l1
        i32.const 4
        i32.eq
        br_if $B0
        local.get $l0
        i32.const 28
        i32.add
        local.get $l1
        i32.add
        i32.const 0
        i32.store
        local.get $l1
        i32.const 4
        i32.add
        local.set $l1
        br $L1
      end
    end
    i32.const 0
    local.set $l1
    local.get $l0
    i32.load offset=28
    local.set $l2
    block $B2
      loop $L3
        local.get $l1
        i32.const 4
        i32.eq
        br_if $B2
        local.get $l0
        i32.const 12
        i32.add
        local.get $l1
        i32.add
        local.get $l2
        i32.store
        local.get $l1
        i32.const 4
        i32.add
        local.set $l1
        br $L3
      end
    end
    i32.const 0
    local.set $l1
    block $B4
      loop $L5
        local.get $l1
        i32.const 4
        i32.eq
        br_if $B4
        local.get $l0
        i32.const 16
        i32.add
        local.get $l1
        i32.add
        i32.const 0
        i32.store
        local.get $l1
        i32.const 4
        i32.add
        local.set $l1
        br $L5
      end
    end
    i32.const 0
    local.set $l1
    block $B6
      loop $L7
        local.get $l1
        i32.const 4
        i32.eq
        br_if $B6
        local.get $l0
        i32.const 20
        i32.add
        local.get $l1
        i32.add
        i32.const 0
        i32.store
        local.get $l1
        i32.const 4
        i32.add
        local.set $l1
        br $L7
      end
    end
    i32.const 0
    local.set $l1
    block $B8
      loop $L9
        local.get $l1
        i32.const 4
        i32.eq
        br_if $B8
        local.get $l0
        i32.const 24
        i32.add
        local.get $l1
        i32.add
        i32.const 0
        i32.store
        local.get $l1
        i32.const 4
        i32.add
        local.set $l1
        br $L9
      end
    end
    i32.const 0
    local.set $l1
    block $B10
      loop $L11
        local.get $l1
        i32.const 4
        i32.eq
        br_if $B10
        local.get $l0
        i32.const 28
        i32.add
        local.get $l1
        i32.add
        i32.const 0
        i32.store
        local.get $l1
        i32.const 4
        i32.add
        local.set $l1
        br $L11
      end
    end
    local.get $l0
    i32.const 0
    i32.store offset=28
    local.get $l0
    i32.const 0
    i32.store offset=24
    local.get $l0
    i32.const 0
    i32.store offset=12
    local.get $l0
    i32.const 0
    i32.store offset=16
    f32.const 0x0p+0 (;=0;)
    local.set $l3
    i32.const 1
    local.set $l1
    block $B12
      loop $L13
        local.get $l1
        i32.const 1
        i32.and
        i32.eqz
        br_if $B12
        local.get $l0
        f32.const 0x0p+0 (;=0;)
        local.get $l3
        f32.add
        local.tee $l3
        f32.store offset=20
        local.get $l0
        f32.const 0x0p+0 (;=0;)
        local.get $l0
        f32.load offset=16
        f32.add
        f32.store offset=16
        i32.const 0
        local.set $l1
        br $L13
      end
    end)
  (memory $memory 1)
  (global $g0 (mut i32) (i32.const 16))
  (global $__data_end i32 (i32.const 16))
  (global $__heap_base i32 (i32.const 16))
  (export "memory" (memory 0))
  (export "bench" (func $bench))
  (export "__data_end" (global 1))
  (export "__heap_base" (global 2)))

Here is the output from running wasm-interp wasm/bicg.wasm --run-all-exports --trace

Backtrace

>>> running export "bench":
#0.    0: V:0  | alloca 4
#0.    8: V:4  | global.get $0
#0.   16: V:5  | i32.const 32
#0.   24: V:6  | i32.sub 16, 32
#0.   28: V:5  | local.set $5, 4294967280
#0.   36: V:4  | i32.const 0
#0.   44: V:5  | local.set $4, 0
#0.   52: V:4  | local.get $3
#0.   60: V:5  | i32.const 4
#0.   68: V:6  | i32.eq 0, 4
#0.   72: V:5  | br_unless @88, 0
#0.   88: V:4  | local.get $4
#0.   96: V:5  | i32.const 28
#0.  104: V:6  | i32.add 4294967280, 28
#0.  108: V:5  | local.get $4
#0.  116: V:6  | i32.add 12, 0
#0.  120: V:5  | i32.const 0
#0.  128: V:6  | i32.store $0:12+$0, 0
#0.  140: V:4  | local.get $3
#0.  148: V:5  | i32.const 4
#0.  156: V:6  | i32.add 0, 4
#0.  160: V:5  | local.set $4, 4
#0.  168: V:4  | br @52
#0.   52: V:4  | local.get $3
#0.   60: V:5  | i32.const 4
#0.   68: V:6  | i32.eq 4, 4
#0.   72: V:5  | br_unless @88, 1
#0.   80: V:4  | br @176
#0.  176: V:4  | i32.const 0
#0.  184: V:5  | local.set $4, 0
#0.  192: V:4  | local.get $4
#0.  200: V:5  | i32.load $0:4294967280+$28
bench() => error: out of bounds memory access: access at 4294967308+4 >= max value 65536

From the wat file and the interpreter logs, there are several incorrect codes like local.set $5, 4294967280, i32.add 4294967280, 28 (overflow), and 32.load $0:4294967280+$28. Why are these illegal instructions generated?

I expected to see this happen: no out of bounds errors.

Instead, this happened: the resulting wasm file tries to access out of bounds memory from the value stack. I have tried with the parity/wasmi interpreter, wasm-interp and wasmtime.

The code is compiled with cargo --build --release and optimized using the following config. I also use the compiler flag "-C", "link-arg=-zstack-size=16".

[profile.release]
lto = true
opt-level = "z"

The issue is reproducible with pratically any file in https://github.com/jiayihu/polybench-rs/tree/master/wasm, which are wasm modules containing the Polybench functions.

Meta

rustc --version --verbose (I have tried also with rustc 1.50.0 nightly, which I was using before updating to latest to test if anything changed):

rustc 1.53.0-nightly (07e0e2ec2 2021-03-24)
binary: rustc
commit-hash: 07e0e2ec268c140e607e1ac7f49f145612d0f597
commit-date: 2021-03-24
host: x86_64-apple-darwin
release: 1.53.0-nightly
LLVM version: 12.0.0

[jiayihu]

My bad, I thought link-arg=-zstack-size=16 would mean 16*4KiB because the documentation said The size should be an even multiple of 4KB, that is the last three hexadecimal digits should be zero.. This resulted in stacks of only 16 bytes, which resulted in wasm trying to access negative addresses of the linear memory, which in turn results in OOB errors.

Related: rustwasm/wasm-pack#479, rustwasm/wasm-bindgen#1345