JavaScript engine internals: NaN-boxing

In researching code plugin sandboxing with WebAssembly, my thoughts naturally turned to how to let people actually program for that environment without forcing use of low-level C++ or such… so naturally, now I’m writing a small JavaScript-like runtime engine and compiler that targets WebAssembly. ;)

My explorations so far are themselves written in C++, with tiny JS samples hand-translated into C++ code that calls the runtime’s classes. If I continue the project, I may switch to directly emitting Wasm source from the translator, with an eye towards future Wasm improvements like native garbage-collected reference types. (Right now I have to implement garbage collection myself, which will be the subject of another blog post!)

The first step of implementing a JavaScript engine is to implement a representation for values, which is tricky because JS values can be any of several distinct types:

  • undefined
  • null
  • boolean
  • number (float64)
  • object reference (string, Symbol, Object, etc)

Many other dynamic languages like PHP and Python similarly allow a value to hold multiple competing types like this. There are two main ways to implement a value type like this.

Tagged unions

The first is to use a “tagged union” struct, something like this:

enum TypeTag {
  TAG_UNDEFINED,
  TAG_INT32,
  TAG_DOUBLE,
  ...
  TAG_OBJECT
};

struct Value {
  TypeTag tag;
  union {
    int32_t int32_val;
    double double_val;
    Object* object_val;
  };
};

Then add accessor/mutator functions which check the tag and perform appropriate accesses or conversions. This is simple, but has the downside of requiring 16 bytes per value (to maintain 8-byte alignment on the double-precision float or a 64-bit pointer or int64). That means most reads require two loads, writes require two stores, and you can’t pass a value in a register reliably. (WebAssembly’s local variables and function arguments are sort of like CPU registers in how they’re addressed, so would be the equivalent.)

To get around these, a common trick in high-performance dynamic language runtimes like LuaJIT and all major JavaScript engines is known as NaN boxing.

NaN boxing the SpiderMonkey way

Floating point numbers are a complex beast! A 64-bit double-precision float can be broken down into several sets of bits:

  • 1 bit for sign
  • 11 bits for exponent part
  • 52 bits for binary fractional part

If the exponent bits are all 1, then you have a special value:

  • if the fractional bits are all 0, then it represents infinity (positive or negative, depending on the sign bit)
  • if any fractional bit is 1, then it represents “not a number” (NaN), used as a special signal that an operation was invalid or a non-value is being represented.
  • and oh by the way, regular operations only ever produce a canonical NaN value with just the topmost fractional bit set.

The interesting part is that means you have an entire number space within the range of representable NaN values that will never be produced by legit math operations on legit numbers!

  • 1 bit for sign (set to 1 for a signalling NaN that won’t be produced by math ops)
  • 11 bits for exponent (all set to 1)
  • 1 bit to force it to NaN rather than Infinity if rest is 0s
  • 51 bits for tag and payload

Firefox’s SpiderMonkey engine divides this up into 4 bits of tag (16 types) and 47 bits of address, which is enough for x86_64 (where bit 48 will always be 0 in user space and bits 49-64 aren’t needed … yet) but apparently causes problems on AArch64 and Sparc64. (They work around this by deliberately mapping memory in the lower 47 bits of address space with mmap.)

I’ve chosen to experiment with a similar technique, but only using 3 bits of tag (8 types) to leave a clean 48 bits of address. Though when building to WebAssembly, you only need 32 bits of address so it doesn’t make much difference. ;)

When reading a value of as-yet-unknown type, you mask off the top X bits and compare against some constant values:

  • each type other than double-precision its has a particular tag value, so you just == for it
  • actual double-precision values can be detected quickly by forcing the sign bit on and then doing a uint64 compare against a cutoff value: any legit double including canonical NaNs will be <= 0b1111111111111000’0000000000000000’0000000000000000’0000000000000000 once sign/signalling bit is set.
  • if there are multiple type tags for pointer types, you can put them at the high end of the tag range and do a uint64 compare against a cutoff value

One downside is that every object dereference has to be masked from the stored value, and typical JavaScript code does a lot of objects. It’s a bit-op so it’s cheap, though… and in WebAssembly you can actually wrap the 64-bit value down to 32-bits without masking, since pointers are 32 bits. :)

JavaScriptCore style

WebKit’s JavaScriptCore uses a different technique on 64-bit native architecture.

When storing a double value, the bit pattern is treated as a uint64 and has a constant added to it to “rotate” the NaN patterns such that the top 1 bits in a range of the signaling NaNs turn into 0s.

  • object references have 0x0000 in the top 16 bits, meaning a 48-bit pointer can be read directly with a 64-bit read — no bit-masking penalty on dereference!
  • int32 values have 0xffff in the top 16 bits, making common integer operations easy with a mask
  • true/false/undefined/null are stored as special fake pointer values in the object pointer space
  • most double-precision float values sit in the 0x0001-0xfffe space, and have to subtract the constant to get back to their original bit pattern.
  • -Infinity has to be specially stored in the object space because the shift puts it in the wrong place

Sounds clever!

I haven’t checked what Chrome’s V8 and Edge’s ChakraCore do, but I believe they are similar to one or the other of the above.

Security considerations

The downside of all this magic bit-fiddling is that you have to be careful at API boundaries between the JS world and the external world it’s connected to to canonicalize all incoming NaN values in doubles, or it would be possible to create arbitrary object pointer references from within the scripting language — a huge security hole.

So, you know, be careful with that. ;)

 

Thoughts on WebAssembly as a plugin sandbox

I’ve been thinking about ways to run user-supplied untrusted code in the browser, with an eye towards things like interactive demo programs in Wikipedia articles and user interface & editor extensions. Just running JavaScript provided by the user is wildly unsafe — it can dig into your web page’s UI and submit server requests on your user’s behalf without permission, for instance — and sandboxing things into iframes can be a bit funky and hard to fully lock down.

Current web browsers have another language they can run, though, which is WebAssembly — and WebAssembly makes much stricter sandboxing guarantees:

  • Sandboxed code has literally no way to access memory or objects not provided to it
    • no DOM access
    • no network access
    • no eval()
  • Imported objects can only be numbers (read-only) or functions (call-only)
  • Only numbers can be passed as arguments or returned to/from foreign functions
  • Maximum memory usage can be set at compile time
  • Compiled modules can be cached offline in indexedDB and reloaded safely

This means there’s no way an arbitrary wasm binary can access your document.cookies or submit a form, unless you pass in a function that allows that.

This also means that unless you provide an API to the wasm code, it can’t actually do anything other than calculate numbers. It also means that whatever API you do provide becomes a security boundary — you must make sure that you don’t introduce a function that can be exploited contrary to the security guarantees you want to make!

There are also a couple things that wasm by itself doesn’t solve:

  • The halting problem — like JS code, wasm code can loop forever if it wants and there’s no way for the caller to interrupt it.

But wait — you can run a wasm binary in a Web Worker thread. And you can terminate Web Worker threads from the main thread! Depending on your API, if asynchronous messaging around the calls is workable this might be a good way to avoid hanging the main thread in the face of a misbehaving plugin.

So what’s the downside? Well, a few things to consider:

  • wasm APIs must be wrapped to idiomatically transfer strings or data buffers with your main JS.
  • Getting the emscripten compiler to produce “bare wasm” from C/C++ without assuming some JS imports are available seems tricky.
  • C and C++ may not be the friendliest languages for plugin writers on text/GUI-heavy systems!
  • Note rustc also has wasm compilation support, but the same concern applies.
  • Any other language runtimes/libraries you use have to be built into the wasm binary… unless you rig up some kind of cross-module linking and ship multiple modules which link together, which seems super hard right now.

Something to consider for later. :D

 

emscripten fun: porting libffi to WebAssembly part 1

I have a silly dream of seeing graphical Linux/FOSS programs running portably on any browser-based system outside of app store constraints. Two of my weekend side projects are working in this direction: an x86 emulator core to load and run ELF binaries, and better emscripten cross-compilation support for the GTK+ stack.

Emulation ideas

An x86 emulator written in WebAssembly could run pre-built Linux binaries, meaning in theory you could make an automated packager for anything in a popular software repository.

But even if all the hard work of making a process-level emulator work, and hooking up the Linux-level libraries to emulated devices for i/o and rendering, there are some big performance implications, and you’re probably also bundling lots of library code you don’t need at runtime.

Instruction decoding and dispatch will be slow, much slower than native. And it looks pretty complex to do JIT-ing of traces. While I think it could be made to work in principle, I don’t think it’ll ever give a satisfactory user experience.

Cross-compilation

Since we’ve got the source of Linux/FOSS programs by definition, cross-compiling them directly to WebAssembly will give far better performance!

In theory even something from the GNOME stack would work, given an emscripten-specific gdk backend rendering to a WebGL canvas just like games use SDL2 or similar to wrap i/o.

But long before we can get to that, there are low-level library dependencies.

Let’s start with glib, which implements a bunch of runtime functions and the GObject type system, used throughout the stack.

Glib needs libffi, a library for calling functions with at-runtime call signatures and creating closure functions which enclose a state variable around a callback.

In other words, libffi needs to do things that you cannot do in standard C, because it needs system-specific information about how function arguments and return values are transferred (part of the ABI, application binary interface). And to top it off, in many cases (emscripten included) you still can’t do it in C, because asm.js and WebAssembly provide no way to make a call with an arbitrary argument list. So, like a new binary platform, libffi must be ported…

It seems to be doable by bumping up to JavaScript, where you can construct an array of mixed-type arguments and use Function.prototype.apply to call the target function. Using an EM_ASM_ block in my shiny new wasm32/ffi.c I was able to write a JavaScript implementation of the guts of ffi_call which works for int, float, and double parameters (still have to implement 64-bit ints and structs).

The second part of libffi is the closure creation API, which I think requires creating a closure function in the JavaScript side, inserting it into the module’s function tables, and then returning the appropriate index as its address. This should be doable, but I haven’t started yet.

Emscripten function pointers

There are two output targets for the emscripten compiler: asm.js JavaScript and WebAssembly. They have similar capabilities and the wrapper JS is much the same in both, but there are some differences in implementation and internals as well as the code format.

One is in function tables for indirect calls. In both cases, the low-level asm.js/WASM code can’t store the actual pointer address of a function, so they use an index into a table of functions. Any function whose address is taken at compile time is added to the table, and its index used as the address. Then, when an indirect call through a “function pointer” is made, the pointer is used as the index into the function table, and an actual function call is made on it. Voila!

In asm.js, there are lots of Weird Things done about type consistency to make the JavaScript compilers fast. One is that the JS compiler gets confused if you have an array of functions that _contain different signatures_, making indirect calls run through slower paths in final compiled code. So for each distinct function signature (“returns void” or “returns int, called with float32” etc) there was a separate array. This also means that function pointers have meaning only with their exact function signature — if you take a pointer to a function with a parameter and call it without one, it could end up calling an entirely different function at runtime because that index has a different meaning in that signature!

In WebAssembly, this is handled differently. Signatures are encoded at the call site in the call_indirect opcode, so no type inference needs to be done.

But.

At least currently, the asm.js-style table separation is still being used, with the multiple tables encoded into the single WebAssembly table with a compile-time-known constant offset.

In both cases, the JS side can do indirect calls by calculating the signature string (“vf” for “void return, float32 arg” etc) and calling the appropriate “dynCall_vf” etc method, passing first the pointer and then the rest of the argument list. On asm.js this will look up in the tables directly; on WASM it’ll apply the index.

(etc)

It’s possible that emscripten will change the WASM mode to use a single array without the constant offset indirection. This will simplify lookups, and I think make it easier to add more functions at runtime.

Because you see, if you want to add a callback at runtime, like libffi’s closure API wants to, then you need to add another entry to that table. And in asm.js the table sizes are fixed for asm.js validation rules, and in WASM current mode the sub-tables are definitely fixed at compile time, since those constant offsets are used throughout.

So currently there’s an option you can use at build time to reserve room for runtime function pointers, I think I’ll have to use it, but that only reserves *fixed space* of a given number of pointers.

Next

Coming up next time: int64 and struct in the emscripten ABI, and does the closure API work as expected?

String concatenation garbage collection madness!

We got a report of a bug with the new 3D model viewing extension on Wikimedia Commons, where a particular file wasn’t rendering a thumbnail due to an out-of-memory condition. The file was kind-of big (73 MiB) but not super huge, and should have been well within the memory limits of the renderer process.

On investigation, it turned out to be a problem with how three.js’s STLLoader class was parsing the ASCII variant of the file format:

  • First, the file is loaded as a binary ArrayBuffer
  • Then, the buffer is checked to see whether it contains binary or text-format data
  • If it’s text, the entire buffer is converted to a string for further processing

That conversion step had code that looked roughly like this:

var str = '';
for (var i = 0; i < arr.length; i++) {
    str += String.fromCharCode(arr[i]);
}
return str;

Pretty straightforward code, right? Appends one character to the string until the input binary array is out, then returns it.

Well, JavaScript strings are actually immutable — the “+=” operator is just shorthand for “str = str + …”. This means that on every step through the new loop, we create two new strings: one for the character, and a second for the concatenation of the previous string with the new character.

The JavaScript virtual machine’s automatic garbage collection is supposed to magically de-allocate the intermediate strings once they’re no longer referenced (at some point after the next run through the loop) but for some reason this isn’t happening in Node.js. So when we run through this loop 70-some million times, we get a LOT of intermediate strings still in memory and eventually the VM just dies.

Remember this is before any of the 3d processing — we’re just copying bytes from a binary array to a string, and killing the VM with that. What!?

Newer versions of the STLLoader use a more efficient path through the browser’s TextDecoder API, which we can polyfill in node using Buffer, making it blazing fast and memory-efficient… this seems to fix the thumbnailing for this file in my local testing.

Just for fun though I thought, what would it take to get it working in Node or Chrome without the fancy native API helpers? Turns out you can significantly reduce the memory usage of this conversion just by switching the order of operations….

The original append code results in operations like: (((a + b) + c) + d) which increases the size of the left operand linearly as we go along.

If we instead do it like ((a + b) + (c + d)) we’ll increase _both_ sides more slowly, leading to much smaller intermediate strings clogging up the heap.

Something like this, with a sort of binary bisection thingy:

function do_clever(arr, start, end) {
    if (start === end) {
        return '';
    } else if (start + 1 === end) {
        return String.fromCharCode(arr[start]);
    } else {
        var mid = start + Math.floor((end - start) / 2);
        return do_clever(arr, start, mid) +
               do_clever(arr, mid, end);
    }
}

return do_clever(arr, 0, arr.length);

Compared to the naive linear append, I’m able to run through the 73 MiB file in Node, and it’s a bit faster too.

But it turns out there’s not much reason to use that code — most browsers have native TextDecoder (even faster) and Node can fake it with another native API, and those that don’t are Edge and IE, which have a special optimization for appending to strings.

Yes that’s right, Edge 16 and IE 11 actually handle the linear append case significantly faster than the clever version! It’s still not _fast_, with a noticeable delay of a couple seconds on IE especially, but it works.

So once the thumbnail fix goes live, that file should work both in the Node thumbnailer service *and* in browsers with native TextDecoder *and* in Edge and IE 11. Yay!

ogv.js 1.5.7 released

I’ve released ogv.js 1.5.7 with performance boosts for VP8/VP9 video (especially on IE 11) and Opus audio decoding, and a fix for audio/webm seeking.

npm: https://www.npmjs.com/package/ogv
zip: https://github.com/brion/ogv.js/releases/tag/1.5.7

emscripten versus IE 11: arithmetic optimization for ogv.js

ogv.js is a web video & audio playback engine for supporting the free & open Ogg and WebM formats in browsers that don’t support them natively, such as Safari, Edge, and Internet Explorer. We use it at Wikipedia and Wikimedia Commons, where we don’t currently allow the more common MP4 family of file formats due to patent concerns.

IE 11, that old nemesis, still isn’t quite gone, and it’s definitely the hardest to support. It’s several years old now, with all new improvements going only into Edge on Windows 10… so no WebAssembly, no asm.js optimizations, and in general it’s just kind of ….. vveerryy ssllooww compared to any more current browser.

But for ogv.js I still want to support it as much as possible. I found that for WebM videos using the VP8 or VP9 codecs, there was a *huge* slowdown in IE compared to other browsers, and wanted to see if I could pick off some low-hanging fruit to at least reduce the gap a bit and improve playback for devices right on the edge of running smoothly at low resolutions…

Profiling in IE is a bit tough since the dev tools often skew JS performance in weird directions… but always showed that a large bottleneck was the Math.imul polyfill.

Math.imul, on supporting browsers, is a native function that implements 32-bit integer multiplication correctly and very very quickly, including all the weird overflow conditions that can result from multiplying large numbers — this is used in the asm.js code produced by the emscripten compiler to make sure that multiplication is both fast and correct.

But on IE 11 it’s not present, so a replacement function (“polyfill”) is used by emscripten instead. This does several bit shifts, a couple multiplications, blah blah details, anyway even when the JIT compiler inlines the function, it’s slower than necessary.

I hacked together a quick test to search the generated asm.js code for calls to the minified reference to Math.imul, and replace them with direct multiplication… and found significant performance improvements!

I also found it broke some of the multiplications by using wrong order of operations though, so replaced it with a corrected transformation that instead of a regex on the code, uses a proper JS parser, walks the tree for call sites, and replaces them with direct multiplication… after some more confusion with my benchmarking, I confirmed that the updated code was still faster:

This is about a 15-20% improvement, plus or minus, which seems a pretty significant bump!

Of course more modern browsers like current versions of Safari and Edge will use the Web Assembly version of ogv.js anyway, and are several times faster…

 

Daydream View phone VR headset

I somehow ended up with a $100 credit at the Google Store, and decided to splurge on something I didn’t need but wanted — the Daydream View phone VR headset.

This is basically one step up from the old Google Cardboard viewer where you put your phone in a lens/goggles getup, but it actually straps to your head so you don’t have to hold it to your face manually. It’s also got a wireless controller instead of just a single clicky button, so you get a basic pointer within the VR world with selection & home buttons and even a little touchpad, allowing a fair range of controls within VR apps.

Using the controller, the Daydream launcher interface also provides an in-VR UI for browsing Google Play Store and purchasing new games/apps. You can even broadcast a 2d view to a ChromeCast device to share your fun with the rest of the room, though there’s no apparent way to save a recording.

The hardware is still pretty limiting compared to what the PC VR headsets like the Rift and Vive can do — there’s no positional tracking for either head tracking or the controller, so you’re limited to rotation. This means things in the VR world don’t move properly as you move your head around, and you can only use the controller to point, not to pick up VR objects in 3d space. And it’s still running on a phone (Pixel 2 in my case) so you’re not going to get the richest graphics — most apps I’ve tried so far have limited, cartoony graphics.

Still it’s pretty fun to play with; I’ll probably play through a few of these games and then put it away mostly forever, unless I figure out some kind of Wikipedia-related VR project to work on on the side. :)

Old Xeon E5520 versus PS3 emulator RPCS3

I’ve been fixing up my old Dell Precision T5500 workstation, which had been repurposed to run (slightly older) games, to run both work stuff & more current games if possible. Although the per-core performance of a 2009-era Xeon E5520 processor is not great, with 8 cores / 16 threads total (dual CPUs!) it still packs a punch on multithreaded workloads compared to a laptop.

When I stumbled on the RPCS3 Playstation 3 emulator, I just had to try it too and see what happened… especially since I’ve been jonesing for a Katamari fix since getting rid of my old PS3 a couple years ago!

The result is surprisingly decent graphics, but badly garbled audio:

My current theory based on reading a bunch in their support forums is that the per-thread performance is too bad to run the thread doing audio processing, so it’s garbling/stuttering at short intervals. Between the low clock speed (2.26 GHz / 2.5 GHz boost) and the older processor tech AND the emulation overhead, one Xeon core is probably not going to be as fast as one PS3 Cell SPE unit, so if that thread was just close enough to full to work on the PS3 it’ll be too slow on my PC…

Windows’ Task Manager shows a spread of work over 8-9 logical processors, but not fully utilized. Threads that are woken/sleeped frequently like audio or video processing tend to get broken up on this kind of graph (switching processors on each wake), so you can’t tell if one *OS* thread is maxed out as easily from the graph.

This all leads me to believe the emulator’s inherently CPU-bound here, and really would do better with a more modern 4-core or 6-core CPU in the 3ish-to-4ish GHz range. I’ll try some of the other games I have discs still lying around for just for fun, but I expect similar results.

This is probably something to shelve until I’ve got a more modern PC, which probably means a big investment (either new CPU+RAM+motherboard or just a whole new PC) so no rush. :)

2009 Workstation recovery – libvpx benchmark

I’m slowly upgrading my old 2009-era workstation into the modern world. It’s kind of a fun project! Although the CPUs are a bit long in the tooth, with 8 cores total it still can run some tasks faster than my more modern MacBook Pro with just 2 cores.

Enjoy some notes from benchmarking VP9 video encoding with libvpx and ffmpeg on the workstation versus the laptop…

(end)