A specific pattern of pushes to array causes a runtime error in ~lib/rt/tlsf/insertBlock

[vladimir-tikhonov]

This is another of "randomly occurred after a couple of seconds" errors. This time it was caused by pushing into an array. As you can see from the code, I've basically recorded and replicated a pattern of pushes that lead to an error.

Webassembly studio: https://webassembly.studio/?f=ul7d4jxj0rd

Code:

const tracing: i32[] = [ 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 3, 0, 3, 0, 3, 0, 3, 0, 3, 0, 3, 0, 3, 0, 3, 0, 6, 0, 6, 0, 6, 0, 6, 0, 6, 0, 6, 0, 6, 0, 6, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 13, 0, 13, 0, 13, 0, 13, 0, 13, 0, 13, 0, 13, 0, 13, 0, 16, 0, 16, 0, 16, 0, 16, 0, 16, 0, 16, 0, 16, 0, 16, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 12, 0, 12, 0, 12, 0, 12, 0, 12, 0, 12, 0, 12, 0, 12, 0, 15, 0, 15, 0, 15, 0, 15, 0, 15, 0, 15, 0, 15, 0, 15, 0, 11, 0, 11, 0, 11, 0, 11, 0, 11, 0, 11, 0, 11, 0, 11, 0, 14, 0, 14, 0, 14, 0, 14, 0, 14, 0, 14, 0, 14, 0, 14, 0, 17, 0, 17, 0, 17, 0, 17, 0, 17, 0, 17, 0, 17, 0, 17, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 3, 0, 3, 0, 3, 0, 3, 0, 3, 0, 3, 0, 3, 0, 3, 0, 6, 0, 6, 0, 6, 0, 6, 0, 6, 0, 6, 0, 6, 0, 6, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 13 ];
const arrayBuffer: Array<i32[]|null> = [];

function inflate( buffer: Array<i32[]|null>, targetLength: i32 ): void {
    while ( buffer.length < targetLength ) {
        buffer.push( null );
    }
}

function push( arrayId: i32 ): void {
    if ( arrayBuffer.length <= arrayId ) {
        inflate( arrayBuffer, arrayId + 1 );
    }
    let array = arrayBuffer[ arrayId ];
    if ( array === null ) {
        array = [];
        arrayBuffer[ arrayId ] = array;
    }

    array.push( 0 );
}

for ( let j = 0; j < 2; j++ ) {
    for ( let i = 0; i < tracing.length; i++ ) {
        push( tracing[ i ] );
    }
}

Stack trace:

RuntimeError: unreachable
    at ~lib/rt/tlsf/insertBlock
    at ~lib/rt/tlsf/reallocateBlock
    at ~lib/rt/tlsf/__realloc
    at ~lib/array/ensureSize
    at ~lib/array/Array<i32>#push
    at assembly/index/push
    at start:assembly/index
    at start

[vladimir-tikhonov]

A reduced example:

const tracing: i32[] = [ 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 3, 0, 3, 0, 3, 0, 3, 0, 3, 0, 3, 0, 3, 0, 3, 0, 6, 0, 6, 0, 6, 0, 6, 0, 6, 0, 6, 0, 6, 0, 6, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 13, 0, 13, 0, 13, 0, 13, 0, 13, 0, 13, 0, 13, 0, 13, 0, 16, 0, 16, 0, 16, 0, 16, 0, 16, 0, 16, 0, 16, 0, 16, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 12, 0, 12, 0, 12, 0, 12, 0, 12, 0, 12, 0, 12, 0, 12, 0, 15, 0, 15, 0, 15, 0, 15, 0, 15, 0, 15, 0, 15, 0, 15, 0, 11, 0, 11, 0, 11, 0, 11, 0, 11, 0, 11, 0, 11, 0, 11, 0, 14, 0, 14, 0, 14, 0, 14, 0, 14, 0, 14, 0, 14, 0, 14, 0, 17, 0, 17, 0, 17, 0, 17, 0, 17, 0, 17, 0, 17, 0, 17, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 3, 0, 3, 0, 3, 0, 3, 0, 3, 0, 3, 0, 3, 0, 3, 0, 6, 0, 6, 0, 6, 0, 6, 0, 6, 0, 6, 0, 6, 0, 6, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 13 ];
const arrayBuffer: Array<i32[]|null> = new Array( 32 );
arrayBuffer.fill( null );

function push( arrayId: i32 ): void {
    let array = arrayBuffer[ arrayId ];
    if ( array === null ) {
        array = [];
        arrayBuffer[ arrayId ] = array;
    }

    array.push( 0 );
}

for ( let j = 0; j < 2; j++ ) {
    for ( let i = 0; i < tracing.length; i++ ) {
        push( tracing[ i ] );
    }
}

webassembly studio

[MaxGraey]

It seems problem with alignment for data memory section. If comment last 8 bytes in tracing array issue is gone:
https://webassembly.studio/?f=02njk07n7h5e

[MaxGraey]

minimal example:

EDITED

const tracing = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1];
const arrayBuffer = new Array<i32[] | null>(2);

for (let j = 0; j < 2; j++) {
  for (let i = 0; i < tracing.length; i++) {
    let id = tracing[i];
    let arr = arrayBuffer[id];
    if (!arr) arr = arrayBuffer[id] = [];
    arr.push(0);
  }
}

[vladimir-tikhonov]

@MaxGraey it seems like in your example arr.push(0); will always fail because arr is always null?

[MaxGraey]

Yeah, good catch! fixed this (see EDITed version)

[dcodeIO]

Reduced a little more

{
  let arrays = new Array<i32[] | null>(2);
  for (let i = 0; i < 18; i++) {
    let id = i % 2;
    let arr = arrays[id];
    if (!arr) arr = arrays[id] = new Array();
    arr.push(0);
  }
}

From toying around with it it seems that this might have something to do with = arrays[id] = doing something strange.

[vladimir-tikhonov]

I'm not sure if this is related or not, but I've also found another bug:

let arrays = new Array<i32[]>(1);
const x = arrays[0];

This will fail in ~lib/array/Array<~lib/array/Array<i32>>#__get. Overall this seems kinda confusing. Should new Array<i32[]>(1) allocate one i32[] and store it as a first element? This is not a case in js, but in assemblyscript Array<i32[]> implies that it won't contains nulls.

[dcodeIO]

This error is expected because the value type is a non-nullable i32[], but the returned value is "what would be" undefined (in AS: null). There is a runtime check to guard for this to ensure type safety. Expectation is that the array is immediately filled with valid values before its elements are accesses. In general this case is a bit unfortunate because JS behavior clashes with static compilation.

[vladimir-tikhonov]

Got it, thanks for explanation, @dcodeIO

[vladimir-tikhonov]

Reduced the example a little more:

{
  let arrays: i32[][] = [ [], [] ];
  for (let i = 0; i < 18; i++) {
    let id = i % 2;
    arrays[id].push(0);
  }
}

[dcodeIO]

{
  let a1 = new Array<i32>(); // 2128, buf=2160
  let a2 = new Array<i32>(); // 2192, buf=2224

  // ALLOC 2256     \
  // FREE 2160 @ 1  | grow a1, buf=2256
  // ++ 2256 @ 0->1 /
  // ALLOC 2304     \
  // FREE 2224 @ 1  | grow a2, buf=2304
  // ++ 2304 @ 0->1 /
  // ALLOC 2352     \
  // FREE 2256 @ 1  | grow a1, buf=2352
  // ++ 2352 @ 0->1 /
  // ALLOC 2224     \
  // abort          | grow a2?

  a1.push(0);
  a1.push(0);
  a1.push(0);
  a1.push(0);
  a1.push(0);
  a1.push(0);
  a1.push(0);
  a1.push(0);

  a2.push(0);
  a2.push(0);
  a2.push(0);
  a2.push(0);
  a2.push(0);
  a2.push(0);
  a2.push(0);
  a2.push(0);

  a1.push(0);

  a2.push(0); // here
}

[dcodeIO]

The assertion should be fixed now, but when I tested the initial code sample I noticed that there's some leaking going on that I can't yet explain.

[dcodeIO]

Turned out there was an issue with RTrace not accounting for some realloc changes, leading to false reporting of leaks. Initial example looks fine in tracing now.

[dcodeIO]

Going ahead and closing this issue. Please let me know if there's still something wrong :)