Make decode() and encodeInto() accept SharedArrayBuffer-backed views

[juj]

In conjunction to WebAssembly and multithreading, there is a need for a new TextDecoder.decode() API for converting e.g. UTF-8 encoded strings in a typed array to a JavaScript string.

Currently to convert a string in WebAssembly heap to a JS string, one can do

// init:
var textDecoder = new TextDecoder("utf8");
var wasmHeap = new UintArray(...); // coming from Wasm instantiation

// use:
var pointerToUtf8EncodedStringInHeap = 0x421341; // A UTF-8 encoded C string residing on the heap
var stringNullByteIndex = pointerToUtf8EncodedStringInHeap;
while(wasmHeap[stringNullByteIndex] != 0) ++stringNullByteIndex;
var jsString = textDecoder.decode(wasmHeap.subarray(pointerToUtf8EncodedStringInHeap, stringNullByteIndex);

There are three shortcomings with this API that are bugging Emscripten/asm.js/WebAssembly uses:

1. TextDecoder.decode() does not work with SharedArrayBuffer, so the above fails if wasmHeap viewed a SharedArrayBuffer in a multithreaded WebAssembly program.

2. TextDecoder.decode() needs a TypedArrayView, and it always converts the whole view. As result, one has to call wasmHeap.subarray() on the large wasm heap to generate a small view that only encompasses the portion of the memory that the contains the string. This generates temporary garbage that would be needless with a more appropriate API.

3. The semantics of TextDecoder.decode() are to always convert the whole input view that is passed to the function. This means that if there exists a null byte \0 in the middle of the view, the generated JS string will have a null UTF-16 code point in it in the middle. I.e. decoding will not stop when the first null byte is found, but continues on from there. This has the effect that in order to use the API from a WebAssembly program that is dealing with null-terminated C strings, JavaScript or Wasm code must first scan the whole string to find the first null byte. This is harmful for performance when dealing with long strings. It would be better to have an API where the decode size that is specified would be a maxBytesToRead style of size, instead of exact size. That way JS/WebAssembly did not need to pre-scan through each string to find how long the string actually is, improving performance.

This kind of code often occurs in compiled C programs, which already provide max sizes of their buffers to deal against buffer overflows in C code. That is,

char str[256] = ...;
UTF8ToString(str, sizeof(str)); // Convert C string to JS string, but provide a max cap for the buffer that cannot be exceeded

or

size_t len = 256;
char *str = malloc(len);
UTF8ToString(str, len);

Having to do a O(N) scan to figure out a buffer overflow guard bound would not be ideal.

It would be good to have a new function on TextDecoder, e.g.

TextDecoder.decodeRange(ArrayBuffer|SharedArrayBuffer|TypedArrayView, startIndex, [optional: maxElementsToRead]);`

which would allow reading from SharedArrayBuffers, took in startIdx to the array, and optionally the max number of elements to read. This is parallel to what was done to WebGL 2, with the advent of WebAssembly and multithreading: all entry points in WebGL 2 dealing with typed arrays accumulated a new variant of the function that take in SharedArrayBuffers and do not produce temporary garbage: https://www.khronos.org/registry/webgl/specs/latest/2.0/#3.7

Also in case of WebGL, all API entry points were retroactively re-specced to allow SharedArrayBuffers and SharedArrayViews in addition to regular typed arrays and views. That would be nice to happen with decode() as well, although if so, it should probably happen exactly at the same time as a new function decodeRange() was added, so that code can feature test via the presence of decodeRange() if the old decode() function has been improved or not.

With such a new decodeRange() function, the JS code at the very top would transform to

// init:
var textDecoder = new TextDecoder("utf8");
var wasmHeap = new UintArray(...); // coming from Wasm instantiation

// use:
var pointerToUtf8EncodedStringInHeap = 0x421341; // A UTF-8 encoded C string residing on the heap
var jsString = textDecoder.decodeRange(wasmHeap, pointerToUtf8EncodedStringInHeap);

which would work with multithreading, improve performance, and be smaller code size.

The reason why this is somewhat important is that with Emscripten and WebAssembly, marshalling strings across wasm and JS language barriers is really common, something most Emscripten compiled applications are doing, and in the absence of multithreading capable text marshalling, applications that need string marshalling have to resort to a manual JS side implementation that loops and appends String.fromCharCode()s character by character:

https://github.com/emscripten-core/emscripten/blob/c2b3c49f71ab98fbd9ff829d6cbd30445b56a93e/src/runtime_strings.js#L98

It would be good for that code to be able to go away.

CC @kripken, @dschuff, @lars-t-hansen, @binji, @lukewagner, @titzer, @bnjbvr, @aheejin , who have been working on WebAssembly multithreading.

[domenic]

.decodeRange(ArrayBuffer|SharedArrayBuffer|TypedArrayView, startIndex, [optional: maxElementsToRead])

Note that this style of (ArrayBuffer, startIndex, length) is exactly a TypedArray, and consensus has been to use Typed Arrays for this API design in the past. See #69 and https://esdiscuss.org/topic/idiomatic-representation-of-buffer-bytesread .

So, that aspect of your before/after code samples would stay the same; you'd still use subarray() with any new APIs we add.

Separately, I don't understand how you find the null byte in your second code example. Are you suggesting decodeRange treat null bytes specially?

[inexorabletash]

An option to stop decoding on null was discussed very early on in the API design. I think we rejected it due to lack of use cases at the time.

We'd need to make sure the decoding algorithms play nicely with it, and there is no ambiguity about a null in the middle of a multibyte sequence. (I'd assume this is designed into the encodings, but don't actually know.)

[lukewagner]

For SAB-compatibility: is that as simple as adding [AllowShared] to decode?

Regarding the garbage created by temporary views, it is a distinct goal of the Host Bindings proposal (explainer quite outdated; refresh coming soon) which we've re-started focusing on recently, including others from the Google Emscripten team like @jgravelle-google. Basically, wasm should be able to pass two i32s that get coerced into a view that is never actually GC-allocated since it is immediately consumed by a C++ implementation that just wants a (base*,length) pair. See also the discussion for encodeInto where we are critically assuming this Host Bindings capabilities for what would otherwise by very garbage-producing API.

For the null-terminating use case: yes, I can definitely see the utility in specifying a terminating code point (like null) to avoid an otherwise superfluous scan through the string. Maybe we can focus on that use case?

[annevk]

Welcome @juj and others. https://whatwg.org/working-mode and https://whatwg.org/faq#adding-new-features might help provide some additional context, though I think we have enough to move forward here.

For SAB, is the copy that https://encoding.spec.whatwg.org/#dom-textdecoder-decode makes acceptable? If not, we'd somehow have to make decoding robust against input changing, right? It's not clear that's desirable. Either way, that would require a fair number of tests.

For scanning, we could add something to https://encoding.spec.whatwg.org/#textdecodeoptions API-wise. I'm not sure if encoding libraries expose such primitives though, but if not they could be added I suppose.

cc @hsivonen

[hsivonen]

TextDecoder.decode() does not work with SharedArrayBuffer

On the first look, being able to use TextDecoder.decode() directly from wasm memory and TextEncoder.encodeInto() directly to wasm memory seems like something we should want even when wasm memory is a SharedArrayBuffer. However, I don't understand the Gecko implementation implications of [AllowShared]. What does [AllowShared] actually do and what requirements does it impose on the DOM-side C++/Rust code that operates on the buffer?

The semantics of TextDecoder.decode() are to always convert the whole input view that is passed to the function. This means that if there exists a null byte \0 in the middle of the view, the generated JS string will have a null UTF-16 code point in it in the middle. I.e. decoding will not stop when the first null byte is found, but continues on from there.

The semantics of TextDecoder.decode() make sense for Rust strings in wasm and C++ std::string in wasm. Only C strings in wasm have this problem. In Gecko (and, last I checked, in Blink and WebKit, too, but it's better if Blink and WebKit developers confirm) the decoders are designed to work with inputs that have explicit length and don't have any scanning for a zero byte built into the conversion loop. (The Gecko-internal legacy APIs that appear to accept C strings actually first run strlen() and then run the conversion step with pointer and length.)

For non-UTF-8 encodings, I'm definitely not going to be baking optional zero termination into the conversion loop, so there'd be a DOM-side prescan if the API got an option to look for a zero terminator. For UTF-8, I'm very reluctant to add yet another UTF-8 to UTF-16 converter that had zero termination baked into the conversion loop, but it might be possible to persuade me to add a different UTF-8 to UTF-16 converter that interleaves zero termination into the converter if there's data to show that it would be a big win for Firefox's wasm story for wasm code that uses C strings. It won't be baked in as a flag into the primary UTF-8 to UTF-16 converter, though. (For both SSE2 and aarch64 checking a 16-byte vector for ASCII is one vector instruction followed by one ALU comparison than can be branched on. Adding checking if there's a zero byte in the vector would complicate things in the hottest loop that works fine for C++ and Rust callers.)

I think C in wasm should run strlen() on the wasm side, hopefully with the wasm to native compiler using SSE4.2, if available, to vectorize the operation, and should surface a pointer (start index) and a length to the JS glue code layer just like C++ (if using std::string or similar as opposed to C strings) and Rust would.

We'd need to make sure the decoding algorithms play nicely with it, and there is no ambiguity about a null in the middle of a multibyte sequence. (I'd assume this is designed into the encodings, but don't actually know.)

UTF-16BE and UTF-16LE are not compatible with C strings. The other encodings defined in the Encoding Standard are.

[annevk]

[AllowShared] makes it so that the binding does not throw on a view being backed by a shared buffer, nothing else. The algorithm-side would get a reference to the buffer and can then do whatever, but it needs to realize the bytes in the buffer can change at any moment.

[hsivonen]

but it needs to realize the bytes in the buffer can change at any moment.

So basically all DOM code operating on SharedArrayBuffer is in the territory of "we're reasoning about Undefined Behavior"?

In Gecko, TextDecoder.decode() can read the same memory location twice without synchronization: first a wider read for ASCIIness check and if the ASCIIness check failed, then as narrower reads. The narrower reads have their own bound checks. However, if a sufficiently smart compiler figured out that the ASCIIness checking failing means that the tail loop has to terminate by finding a non-ASCII byte, the compiler could eliminate the bound check from the tail loop. Then if the memory changed from non-ASCII to ASCII between the ASCIIness-check wide read and the narrow-read tail loop, the tail loop would read out of bounds...

Are we really relying on the compilers we use to write DOM-side code not optimizing too hard on the assumption that memory doesn't change from underneath us in cases where it would be UB for it to change underneath us?

[lars-t-hansen]

Are we really relying on the compilers we use to write DOM-side code not optimizing too hard on the assumption that memory doesn't change from underneath us in cases where it would be UB for it to change underneath us?

Yes and no. Currently our DOM code can't extract the buffer pointer without extracting a sharedness flag at the same time, and in some(*) cases where it does that we assert that the sharedness flag is false and don't touch the memory if it is shared. We are aware that if it did touch that memory it would be UB.

The plan is to remedy this by using UB-safe primitives for accessing shared memory, see https://bugzilla.mozilla.org/show_bug.cgi?id=1225033. In this case, DOM would have (as the JS engine already has) two code paths, one for known-unshared memory and one for possibly-shared memory, where in non-perf-critical cases we can just use the latter. Every DOM API that can handle shared memory will have to be adapted to greater or lesser extent to deal with that reality.

Also see long comment in dom/bindings/TypedArray.h.

(*) When the SAB code landed I believe I handled all the cases in DOM at the time by either disallowing shared memory (error out) or by using UB-prone code or by pretending the memory is zero-length, but I may have missed some spots and/or DOM may have grown in the mean time and/or code I wrote may have since been rewritten.

(Edited for clarity)

[hsivonen]

The plan is to remedy this by using UB-safe primitives for accessing shared memory, see https://bugzilla.mozilla.org/show_bug.cgi?id=1225033.

OK, so from C++ a safely-racy load is a call through a function pointer to a JIT-generated function that the C++ compiler never can see into. I wonder if just using the safely-racy memcpy replacement followed by normal code operating on the copy is more efficient that going through a function pointer on a per-byte basis.

Is there any plan to provide a Rust crate that provides access to these operations? Is there any plan to provide safely-racy loads and stores of 128-bit SIMD vectors? Is there's a reliable way (inline asm with the right amount of volatile) to convince the LLVM optimizer on the C++ or Rust side that the world may have changed between each load without adding the overhead of a function call via function pointer for each load or are these going to continue to have the cost of a function call via function pointer on a per byte basis?

In the case of TextEncoder.encodeInto() how terrible an idea would it be to live dangerously and trust that there's no way the Rust compiler could be optimizing bound checks on the assumption that the memory being written to isn't changed by anyone else?

[lars-t-hansen]

The plan is to remedy this by using UB-safe primitives for accessing shared memory, see https://bugzilla.mozilla.org/show_bug.cgi?id=1225033.

OK, so from C++ a safely-racy load is a call through a function pointer to a JIT-generated function that the C++ compiler never can see into. I wonder if just using the safely-racy memcpy replacement followed by normal code operating on the copy is more efficient that going through a function pointer on a per-byte basis.

Almost certainly. The safely-racy memcpy isn't as fast as a native memcpy but we can improve it to approach native speed; that is not true for a call-per-byte.

Is there any plan to provide a Rust crate that provides access to these operations? Is there any plan to provide safely-racy loads and stores of 128-bit SIMD vectors?

There have been no plans for this since plans are driven by need and with SAB being disabled the need hasn't arisen, but I don't think there's any reason in principle we could not do so.

Is there's a reliable way (inline asm with the right amount of volatile) to convince the LLVM optimizer on the C++ or Rust side that the world may have changed between each load without adding the overhead of a function call via function pointer for each load or are these going to continue to have the cost of a function call via function pointer on a per byte basis?

I don't know and until the one-compiler-to-rule-them-all reality that we have now it wasn't really an interesting question, as we have had other compilers and indeed other compilers that don't do inline asm at all. My gut feeling was that it is easier to trust the C++ compiler with a call to a function that it couldn't possibly know anything about than with inline asm that it might try to figure out the meaning of.

Patches welcome, along with proofs that they are adequate to avoid UB :)

In the case of TextEncoder.encodeInto() how terrible an idea would it be to live dangerously and trust that there's no way the Rust compiler could be optimizing bound checks on the assumption that the memory being written to isn't changed by anyone else?

I don't think I know enough about Rust to have an opinion. Even in the case of C++ it's not completely certain that we had to go as far as we have with the UB-safe primitives, but we now have every reason to believe that they are safe and that UB will not bite us (when they are used properly). My gut feeling is that Rust will have exactly the same problems as C++, esp given that rustc uses llvm.

[hsivonen]

If the most obvious path to for-sure non-UB implementation is to make the DOM code use a presently-slower-than-memcpy replacement for memcpy with an intermediate buffer, is there any reason why that would be better than having the JS glue code between wasm and WebIDL make the intermediate copy within the JS engine?

[hsivonen]

Is there's a reliable way (inline asm with the right amount of volatile) to convince the LLVM optimizer on the C++ or Rust side that the world may have changed between each load without adding the overhead of a function call via function pointer for each load or are these going to continue to have the cost of a function call via function pointer on a per byte basis?

Thinking about this more, being able to use C++11/C11 atomic operations for this would be nice (and Rust-compatible).