Strange output of memset polyfill

[lexaknyazev]

All WAT snippets were taken from the editor on the AssemblyScript's front page.

Redundant operations

export function foo(): void {
  memory.fill(16, 255, 3);
}

;; INFO asc module.ts --textFile module.wat --binaryFile module.wasm -O3 --runtime stub
(module
 (type $none_=>_none (func))
 (memory $0 0)
 (export "foo" (func $module/foo))
 (export "memory" (memory $0))
 (func $module/foo
  i32.const 16
  i32.const 255
  i32.store8
  i32.const 18
  i32.const 255
  i32.store8
  i32.const 17
  i32.const 255
  i32.store8
  i32.const 18
  i32.const 255
  i32.store8
  i32.const 17
  i32.const 255
  i32.store8
  i32.const 16
  i32.const 255
  i32.store8
 )
)

Negative offsets

export function foo(): void {
  memory.fill(0, 0, 2);
}

;; INFO asc module.ts --textFile module.wat --binaryFile module.wasm -O3 --runtime stub
(module
 (type $none_=>_none (func))
 (memory $0 0)
 (export "foo" (func $module/foo))
 (export "memory" (memory $0))
 (func $module/foo
  i32.const 0
  i32.const 0
  i32.store8
  i32.const -2
  i32.const 0
  i32.store8 offset=3
 )
)

[MaxGraey]

Interesting. Actually all this correct but redundant. Like first version is equivalent to:

store<u8>(16, 255, 0);
store<u8>(18, 255, 0);
store<u8>(17, 255, 0);

store<u8>(18, 255, 0);
store<u8>(17, 255, 0);
store<u8>(16, 255, 0);

second version equivalent to:

store<u8>(0, 0, 0);
store<u8>(-2, 0, 3); // which the same as store<u8>(1, 0, 0)

All this optimizations performs by binaryen. And it seems will be great have Dead Store Elimination (DSE) pass for Binaryen.

[lexaknyazev]

The following snippet fails in Chrome, Firefox, and Safari with OOB memory access.

export function bar(): void {
  memory.grow(1);
  store<u8>(-2, 0, 3);
}

[MaxGraey]

The following snippet fails in Chrome, Firefox, and Safari with OOB memory access.

Binaryen perform this transform only when memoryBase >= 1024 as I remember.

[MaxGraey]

Btw memset(0, 0, 2) is invalid (unreachable) in C++:
https://godbolt.org/z/TTsnhr631

So I don't recommend rewrite to first 4 bytes of linear memory in any language. It should be reserved for null address

[lexaknyazev]

The WebAssembly execution spec defines the effective address as i + memarg.offset, so store<u8>(-2, 0, 3) and store<u8>(1, 0, 0) must be semantically equal. It's interesting why all three browsers treat these two instructions differently.

Btw, this fails as well:

export function bar(): void {
  memory.grow(1);
  store<u8>(-1, 0, 9);
}

[MaxGraey]

I guess most engines use bound checking which leave constant offset (last argument) out of scope. Not sure is it problem of engines or spec

[lexaknyazev]

Even if it's a bug with engines, It's probably safe to assume that it will remain as-is (because some platforms no longer receive updates).

For better compatibility, the compiler shouldn't knowingly produce negative offsets such as in the following case:

export function foo(): void {
  memory.grow(1);
  memory.fill(8, 0, 9);
}

[dcodeIO]

Relevant code section:

assemblyscript/std/assembly/util/memory.ts

Lines 202 to 212 in 057ce46

	// fill head and tail with minimal branching
	if (!n) return;
	let dend = dest + n - 4;
	store<u8>(dest, c);
	store<u8>(dend, c, 3);
	if (n <= 2) return;
	store<u8>(dest, c, 1);
	store<u8>(dest, c, 2);
	store<u8>(dend, c, 2);
	store<u8>(dend, c, 1);
	if (n <= 6) return;

Indeed looks like a bug, since offset operands do wrap around, while offset immediates do not, so a store(-1, 0, 2) for example is invalid and will always trap. To be correct, the memset polyfill should not use offset immediates where the offset operand may be negative.

[lexaknyazev]

since offset operands do wrap around

What does it mean? -1 becomes 4294967295?

The spec defines offset as signed and seems to throw only on offset + immoffset being OOB.

[dcodeIO]

If I'm not mistaken, offset does wrap around like a 32-bit integer, while immoffset is always added after/without wrapping, so that a store<T>(-offset, x, immoffset) will always trap if immoffset >= offset + sizeof<T>().

[lexaknyazev]

Just verified with wasm-interp.

The first offset value is indeed casted to u64 thus store<u8>(-1, 0, 1) tries to write to 4294967296.

[dcodeIO]

The PR linked above fixes invalid store offsets within memset leading to a trap, but I didn't yet look into reducing duplicate stores as seen in the first snippet, which appears to be a result of memset trying very hard to avoid unnecessary branches even if that means a redundant store here or there for small ns.

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed in one week if no further activity occurs. Thank you for your contributions!