Template literals cause GC crash

[HerrCai0907]

code like this, after serval times running, wasm will crash

@global const ASC_GC_SWEEPCOST: i32 = 1000;  // make sweep bigger so the bug will easier to be reproduced

function randomNew(): void {
  trace("test");
  const a = Math.random();
  `bbbbbbb${a.toString()}bb`;
}

for (;;) {
  randomNew();
}

Error: abort: at ~lib/rt/itcms.ts:228:20
at abort (/home/ccc/Desktop/test/as/node_modules/@assemblyscript/loader/umd/index.js:105:13)
at ~lib/rt/itcms/step (wasm-function[42]:0x21cd)
at ~lib/rt/itcms/interrupt (wasm-function[43]:0x220f)
at ~lib/rt/itcms/__new (wasm-function[54]:0x279e)
at ~lib/util/number/dtoa (wasm-function[71]:0x2b7d)
at ~lib/number/F64#toString (wasm-function[55]:0x27e0)
at assembly/index/randomNew (wasm-function[70]:0x2a5c)
at start:assembly/index (wasm-function[62]:0x28ea)
at ~start (wasm-function[68]:0x29b3)
at Object.curr. [as _start] (/home/ccc/Desktop/test/as/node_modules/@assemblyscript/loader/umd/index.js:545:20)

[HerrCai0907]

This is my analysis but I'm not sure whether it is correct.

function step(): usize {
  // Magic constants responsible for pause times. Obtained experimentally
  // using the compiler compiling itself. 2048 budget pro run by default.
  const MARKCOST = isDefined(ASC_GC_MARKCOST) ? ASC_GC_MARKCOST : 1;
  const SWEEPCOST = isDefined(ASC_GC_SWEEPCOST) ? ASC_GC_SWEEPCOST : 10;
  var obj: Object;
  switch (state) {
    case STATE_IDLE: {
      state = STATE_MARK;
      visitCount = 0;
      visitRoots(VISIT_SCAN);
      iter = toSpace;
      return visitCount * MARKCOST;
    }
    case STATE_MARK: {
      let black = i32(!white);
      obj = iter.next;
      while (obj != toSpace) {
        iter = obj;
        if (obj.color != black) { // skip already-blacks (pointerfree)
          obj.color = black;
          visitCount = 0;
          __visit_members(changetype<usize>(obj) + TOTAL_OVERHEAD, VISIT_SCAN);
          return visitCount * MARKCOST;
        }
        obj = obj.next;
      }
      visitCount = 0;
      visitRoots(VISIT_SCAN);
      obj = iter.next;
      if (obj == toSpace) {
        visitStack(VISIT_SCAN);
        obj = iter.next;
        while (obj != toSpace) {
          if (obj.color != black) {
            obj.color = black;
            __visit_members(changetype<usize>(obj) + TOTAL_OVERHEAD, VISIT_SCAN);
          }
          obj = obj.next;
        }
        let from = fromSpace;
        fromSpace = toSpace;
        toSpace = from;
        white = black;
        iter = from.next;
        state = STATE_SWEEP;                                                                 // in the STATE_SWEEP, iter pointer the toSpace.next
      }
      return visitCount * MARKCOST;
    }
    case STATE_SWEEP: {
      obj = iter;
      if (obj != toSpace) {
        iter = obj.next;                                                                              // remove toSpace chain one by one
        if (DEBUG) assert(obj.color == i32(!white)); // old white
        free(obj);
        return SWEEPCOST;
      }
      toSpace.nextWithColor = changetype<usize>(toSpace);
      toSpace.prev = toSpace;
      state = STATE_IDLE;
      break;
    }
  }
  return 0;
}


/** Links this object to the specified list, with the given color. */
linkTo(list: Object, withColor: i32): void {
  let prev = list.prev;
  this.nextWithColor = changetype<usize>(list) | withColor;
  this.prev = prev;
  prev.next = this;
  list.prev = this;
}

/** Marks this object as gray, that is reachable with unscanned children. */
makeGray(): void {
  if (this == iter) iter = assert(this.prev);
  this.unlink();
  this.linkTo(toSpace, this.isPointerfree ? i32(!white) : gray);                         // will insert this obj into toSpace 
}


@global @unsafe
export function __link(parentPtr: usize, childPtr: usize, expectMultiple: bool): void {
  // Write barrier is unnecessary if non-incremental
  if (!childPtr) return;
  if (DEBUG) assert(parentPtr);
  var child = changetype<Object>(childPtr - TOTAL_OVERHEAD);
  if (child.color == white) {                                                                              // I guess this is the key point! It should check child's color, but for template literals, const string part will strore in data section and the color is 0. but sometime white is 1
    let parent = changetype<Object>(parentPtr - TOTAL_OVERHEAD);
    let parentColor = parent.color;
    if (parentColor == i32(!white)) {
      // Maintain the invariant that no black object may point to a white object.
      if (expectMultiple) {
        // Move the barrier "backward". Suitable for containers receiving multiple stores.
        // Avoids a barrier for subsequent objects stored into the same container.
        parent.makeGray();
      } else {
        // Move the barrier "forward". Suitable for objects receiving isolated stores.
        child.makeGray();
      }
    } else if (parentColor == transparent && state == STATE_MARK) {
      // Pinned objects are considered 'black' during the mark phase.
      child.makeGray();
    }
  }
}

[dcodeIO]

Objects in static memory, that is below __heap_base, should not be tracked by the GC, so what's in gcInfo should not be relevant. Perhaps the underlying issue here is that one of these objects ends up in the GC nonetheless? Typically, the RT functions have a check to not look at objects below __heap_base, and that's missing somewhere?

[HerrCai0907]

Objects in static memory, that is below __heap_base, should not be tracked by the GC, so what's in gcInfo should not be relevant. Perhaps the underlying issue here is that one of these objects ends up in the GC nonetheless? Typically, the RT functions have a check to not look at objects below __heap_base, and that's missing somewhere?

The reason is, In template string, compile constructs a StaticArray and store it in data section, and then call __link. This action cause the object below __heap_base will be add into toSpace.

By the way, if the object below __heap_base should not be tracked by GC, how can we deal with this condition:

let a = ["a","b","c"]    // seems like a will be compiled as a StaticArray below __heap_base
function test():void{
    let b:string
    a[1] = b
}
test()
// out of scope of b, but b should keep beacuse a has it.

[dcodeIO]

In the snippet, what happens is that a is a pointer to a static array below __heap_base. Neither the array nor the values, which are also static, should be tracked by GC. This is independent, however, from __visiting all reachable members, which still starts at the global a and marks everything reachable from it, but in the process skips what's below __heap_base. Hence, b, which is above __heap_base, will be (the only object in the sample that is) marked.

It is perfectly possible of course that something somewhere is wrong, as indicated by the existence of this issue :)

[HerrCai0907]

Another possible point is when GC run in STATE_SWEEP, it will free toSpace one by one. but __linkTo will call makeGray and add Obj into the end of toSpace.
However if it's tenable, It should be easy to reproduce, unfortunately I cannot reproduce.

[JamieSinn]

Repro-able here: https://github.com/DevCycleHQ/as-repro

[dcodeIO]

Thinking about this a little more, perhaps the underlying issue really is that those arrays in static memory that only temporarily become a root, should always be considered roots. Doing so would guarantee that their black/white/gray states are kept in sync and not dependent on whether they are currently reachable or not.

A way to achieve this seems to be to update compileVisitGlobals to include visiting such memory segments alongside actual global variables. Requires maintaining a list somewhere which offsets in linear memory are which type, perhaps as part of the segments array before it is applied.

[HerrCai0907]

A way to achieve this seems to be to update compileVisitGlobals to include visiting such memory segments alongside actual global variables. Requires maintaining a list somewhere which offsets in linear memory are which type, perhaps as part of the segments array before it is applied.

It will cause the additional load during GC if there are lot of static array. Do you think it is a good idea to alloc some memory dynamically when assembly template literals and then free it. It will slow the template literals but no additional performance influence.