1502033 - Bulk table / memory bounds checking semantics update

Status: RESOLVED FIXED

(Core :: JavaScript: WebAssembly, enhancement, P3)

Description

[Lars T Hansen [:lth]]

A spec change requires bounds checks to be per-access (details TBD, no rush to implement this) while we currently have an up-front check as per the older spec.

Of course a per-access check will be absurdly expensive, so we will want to optimize.  Certainly until we have mmap/mprotect and can unmap pages, if an up-front check determines that we're not going to fault then we should be able to do a fast block copy.  It may in general be a theme that we block-copy up to the limit of the copy range or to the bounds limit, and then check the range, and while we pass the check we continue to copy the next bit (this assumes a concurrent thread that grows memory).  Etc.

Shared memory is a little tricky to deal with however, with concurrent grows not necessarily showing up atomically; some thinking required.

Comment 1

[Lars T Hansen [:lth]]

Some discussion:
https://github.com/WebAssembly/bulk-memory-operations/issues/10
https://github.com/WebAssembly/bulk-memory-operations/issues/11
https://github.com/WebAssembly/design/issues/897#issuecomment-266432753 et seq

Vague-ish spec language here:
https://github.com/WebAssembly/bulk-memory-operations/blob/master/proposals/bulk-memory-operations/Overview.md#memoryinit-instruction

(That is "vague" because it requires the memory to be "accessed" but if the number of bytes written is zero then the memory is not "accessed" per se, yet the sense of the committee in the discussion quoted above was that there should be a bounds check that should fail in this case.)

Comment 2

[Lars T Hansen [:lth]]

There's a clarification on zero-length accesses, traps are required if the addresses are out of bounds, whether any bytes are read or written: https://github.com/WebAssembly/bulk-memory-operations/pull/48/files

I have checked the code and we are handling this aspect properly already.

(Still need solid details on per-access checks, which would allow partial writes.)

Comment 3

[Lars T Hansen [:lth]]

More data is accumulating here:
https://github.com/WebAssembly/bulk-memory-operations/issues/10

For memory.init and table.init we want something like this:

Initialization takes place bytewise from lower addresses toward higher addresses. A trap resulting from an access outside the source data segment or target memory only occurs once the first byte that is outside the source or target is reached. Bytes written before the trap stay written.

For memory.fill, we want something like this:

Filling takes place bytewise from lower addresses toward higher addresses. A trap resulting from an access outside the target memory only occurs once the first byte that is outside the target is reached. Bytes written before the trap stay written.

For memory.copy it's much more open in the context of shared memory and the mythical mprotect. I've filed this to pin down the memory.copy semantics, with pseudocode we can use now if we want for getting the bounds checking right until we have an mprotect instruction:
https://github.com/WebAssembly/bulk-memory-operations/issues/49

Comment 4

[Lars T Hansen [:lth]]

Attachment: bug1502033-bulkmen-partial-write.patch

WIP. This implements partial writes for memFill and memInit. Needs test cases, and of course the spec is not quite baked, but I filed a PR against it to clarify this behavior, so we'll see.

Found a couple existing bugs here (not serious): we can't use straight memcpy and memset if the memory is shared, as this is UB, we have to use our safe-for-races shims. Flagged with comments, may land separately.

Comment 5

[Lars T Hansen [:lth]]

Attachment: bug1502033-bulkmen-partial-write-v2.patch

Code complete for memory.{copy,init,fill} but more test cases needed for copy.

Comment 6

[Lars T Hansen [:lth]]

Attachment: bug1502033-bulk-memory-partial-write-v2.patch

Comment 7

[Lars T Hansen [:lth]]

Attachment: bug1502033-bulk-memory-partial-write-v3.patch

Implements element-by-element bounds checking behavior for memory.init, memory.fill, and memory.copy, and copy-up/copy-down semantics for memory.copy.

Comment 8

[Lars T Hansen [:lth]]

Attachment: bug1502033-bulk-table-partial-write.patch

Ditto code + tests for tables.

Comment 9

[Julian Seward [:jseward]]

Comment on attachment 9040325 [details] [diff] [review]
bug1502033-bulk-memory-partial-write-v3.patch

Review of attachment 9040325 [details] [diff] [review]:
-----------------------------------------------------------------

Looks pretty straightforward.  Some small queries but nothing to block landing.

::: js/src/jit-test/tests/wasm/passive-segs-boundary.js
@@ +219,5 @@
> +    let v = new Uint8Array(ins.exports.mem.buffer);
> +    for (let i=0; i < backup; i++)
> +        assertEq(v[offs+i], val);
> +    if (offs > 0)
> +        assertEq(v[offs-1], 0);

Is it worth checking that the entire rest of the array is still zero, rather than just the element before the start of the written area?

@@ +287,5 @@
> +// perform the operation up to the appropriate bound.  Major cases:
> +//
> +// - non-overlapping regions
> +// - overlapping regions with src >= dest
> +// - overlapping regions with src < dest

I would prefer to have 3 tests here, for the <, = and > cases, just in case it shakes out any < vs <= or > vs >= style bugs in the C++.

::: js/src/wasm/WasmInstance.cpp
@@ +446,5 @@
> +        len = 0;
> +      } else {
> +        // Compute what we have space for in target and what's available in the
> +        // source and pick the lowest value as the new len.
> +        uint64_t srcAvail = memLen < srcByteOffset ? 0 : memLen - srcByteOffset;

Although it doesn't change the computed value (zero), I'd prefer the use of <= here, so as to be consistent with the usual C idiom that "OOB === index >= numElements".  As for example a few lines up:

if (highestDstOffset >= memLen || highestSrcOffset >= memLen) {

Ditto comment in the appearances below.

Comment 10

[Julian Seward [:jseward]]

Comment on attachment 9040640 [details] [diff] [review]
bug1502033-bulk-table-partial-write.patch

Review of attachment 9040640 [details] [diff] [review]:
-----------------------------------------------------------------

This is isomorphic to the memory patch, minus the fill case, so the review comments are too.

::: js/src/jit-test/tests/wasm/passive-segs-boundary.js
@@ +585,5 @@
> +    }
> +    for (let i=Math.min(backup, tbl_init_len); i < backup; i++)
> +        assertEq(tbl.get(offs + i), null);
> +    if (offs > 0)
> +        assertEq(tbl.get(offs - 1), null);

Is it worth checking for null-ness all the way back to index zero?

@@ +607,5 @@
> +// perform the operation up to the appropriate bound.  Major cases:
> +//
> +// - non-overlapping regions
> +// - overlapping regions with src >= dest
> +// - overlapping regions with src < dest

I'd prefer to test the <, = and > cases separately.

::: js/src/wasm/WasmInstance.cpp
@@ +668,5 @@
> +        len = 0;
> +      } else {
> +        // Compute what we have space for in target and what's available in the
> +        // source and pick the lowest value as the new len.
> +        uint64_t srcAvail = srcTableLen < srcOffset ? 0 : srcTableLen - srcOffset;

<= rather than <, here and below, only so as to conform the usual C idioms for bound checks.

Comment 11

[Lars T Hansen [:lth]]

(In reply to Julian Seward [:jseward] from comment #9)

Comment on attachment 9040325 [details] [diff] [review]
bug1502033-bulk-memory-partial-write-v3.patch

Review of attachment 9040325 [details] [diff] [review]:

::: js/src/wasm/WasmInstance.cpp
@@ +446,5 @@

•    len = 0;
  

•  } else {
  

•    // Compute what we have space for in target and what's available in the
  

•    // source and pick the lowest value as the new len.
  

•    uint64_t srcAvail = memLen < srcByteOffset ? 0 : memLen - srcByteOffset;
  

Although it doesn't change the computed value (zero), I'd prefer the use of
<= here, so as to be consistent with the usual C idiom that "OOB === index >= numElements".

Cleaned up the test cases as suggested, but this I'll leave as it is. It's not a bounds check, it's Max(0,memLen-srcByteOffset) -- but since those values are unsigned it gets expressed as a conditional.

Comment 12

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/a1c6c6703dfb
Implement partial write for memInit, memFill, memCopy. r=jseward
https://hg.mozilla.org/integration/mozilla-inbound/rev/e3e2baccf180
Implement partial write for tableInit, tableCopy. r=jseward
https://hg.mozilla.org/integration/mozilla-inbound/rev/9ddffb46398b
Factor some tests to avoid timeouts on simulators. rs=jseward

Comment 13

[Narcis Beleuzu [:NarcisB]]

https://hg.mozilla.org/mozilla-central/rev/a1c6c6703dfb
https://hg.mozilla.org/mozilla-central/rev/e3e2baccf180
https://hg.mozilla.org/mozilla-central/rev/9ddffb46398b