Hacker News Reader

> I feel like PNaCl is the technically superior approach - define a stable set of LLVM bytecode and build an interface to run it in the browser.

I don't agree. I think that LLVM bitcode was not really designed for this either [1]. Google has not succeeded in eliminating all of the undefined behavior from LLVM [2]. At least asm.js has a fully defined semantics as specified by ECMA-262. For any hope of interoperability between browsers, that's critical. Things like order of iteration of properties were once left undefined by ECMA-262, but pages began to rely on Netscape's behavior and other browsers had to reverse engineer what Netscape did. Eventually they were added to the standard. Likewise, without all the undefined behavior removed from PNaCl, anyone who wanted a separate implementation of PNaCl would have to reverse engineer what Chrome did.

There is also the issue of compilation speed: asm.js was designed to compile quickly by a backend that doesn't do much optimization. LLVM, on the other hand, was optimized for -O2, which compiles much less quickly. PNaCl at -O0 is far worse than either V8 or OdinMonkey. On the Web, compilation speed matters a lot.

I think an actually technically superior approach, if backwards compatibility were not a concern, would involve:

1. A from-scratch, untyped, non-SSA bytecode, basically an isomorphism to asm.js. All operations would have fully defined semantics. This would yield fast compilation without the JavaScript syntax and would be amenable to multiple backends, like LLVM or V8.

2. A mechanism for providing a C binding to WebIDL-based Web APIs. This would eliminate the necessity of Pepper and would mean that any new Web APIs would instantly be available to native code.

PNaCl, unfortunately, is neither of these. asm.js isn't either, but I think it's closer to this ideal than PNaCl is.

[1]: http://lists.cs.uiuc.edu/pipermail/llvmdev/2011-October/0437...

[2]: http://www.chromium.org/nativeclient/pnacl/stability-of-the-...

I think quoting Dan's email repeatedly is entirely unhelpful, I'd appreciate it if you wouldn't to that. We've actually addressed every single point in Dan's email, talked to Dan repeatedly, and gone beyond what he originally wrote. Sure it has a catchy title, but if you actually read it (and the replies it generated back then), and then compare to what PNaCl does (including discussions on the LLVM mailing list) you'll see that I'm not making things up here. Our IR subset was designed to be portable and stable.

Undefined behavior: it's mostly gone by the time the pexe is created, and our intent is to remove all that's left (e.g. shift by larger than bit width is trivial to fix). I think what's left is mostly non-issues that can't be easily fixed without breakage, so honestly I don't think undefined behavior is any kind of a deal breaker at this point. asm.js still doesn't have canonical NaNs so it's not fully defined ;-)

Note for other readers here: yes C/C++ have undefined behavior, but both PNaCl and asm.js settle on actual behavior before something gets shipped to the browser.

On compile speed: agreed, but I'll take the "it's getting better" approach here (hey, asm.js can do it for runtime!).

I'm not quite sure why having a non-SSA representation would be a requirement. I agree that there are advantages, but I think that's true of both approaches.

Extra bindings and non-Pepper: agreed.

> I think quoting Dan's email repeatedly is entirely unhelpful, I'd appreciate it if you wouldn't to that. We've actually addressed every single point in Dan's email, talked to Dan repeatedly, and gone beyond what he originally wrote. Sure it has a catchy title, but if you actually read it (and the replies it generated back then), and then compare to what PNaCl does (including discussions on the LLVM mailing list) you'll see that I'm not making things up here. Our IR subset was designed to be portable and stable.

My point wasn't to imply that PNaCl has done a bad job moving mountains to make LLVM into something stable and portable—in fact, the project has done an incredible job with it. I'm just saying that LLVM is not really any more of a natural fit than JS is. JS starts with compatibility and defined semantics and needs to add a low-level type system to become a portable native runtime. LLVM starts with a low-level type system and needs to add compatibility and a defined semantics to become a portable native runtime. In neither case was the system designed for it, as Dan's email shows.

> Undefined behavior: it's mostly gone by the time the pexe is created, and our intent is to remove all that's left (e.g. shift by larger than bit width is trivial to fix). I think what's left is mostly non-issues that can't be easily fixed without breakage, so honestly I don't think undefined behavior is any kind of a deal breaker at this point.

I just wish PNaCl hadn't shipped with any known undefined behavior. (I don't believe NaN canonicalization problems were known at the time asm.js shipped.)

Does PNaCl still have undefined behavior if you access outside a valid allocated region, as that document states ("accessing undefined/freed memory")? It is defined in asm.js, as the application ships its own malloc and there is no type system to tell the runtime what kind of pointer something is. Supposedly Microsoft got into trouble with their libc's malloc because they couldn't change it without breaking apps that relied on accessing freed memory in certain ways. I can see that being true on the Web as well…

Oh I see your point on being a proper fit. It's not much of an argument then, since you're just saying that making it work when it wasn't quite designed for that use is hard, but we did make it work. So I agree :-)

I also wish there weren't any UD, but we did try to do a good list and I think we chose which to fix and which to punt on purpose.

I see memory allocation (both for code and data) as well-defined randomness: saying that the allocated base addresses are random allows many interesting types of sandboxing to be used which couldn't be used otherwise (more on that in the future). I think this will lead to interesting perf gain in some cases, and interesting security gains in others. More pragmatically it currently allows ASLR while still providing memory access without indirection (i.e. reg-reg addressing) on x86-32 and ARM.

Just out of curiosity, what is the rationale for a non-SSA bytecode? Is the idea that each implementation will have a platform-optimized SSA format?

SSA tends to result in a larger on-the-wire format since you have more values and phi nodes. Interpretation is slower because you end up with a lot of values unless you do some sort of register allocation, and you have to interpret phi nodes. If and when you need SSA, the dominance frontiers algorithm is fast in practice (as IonMonkey/Crankshaft show).

While you may be right with regards to the file size (although most SSA-representations are not built for small size, there is quite some potential to reduce it, imho), you'll have to do register allocation/spilling/etc. in your VM/compiler anyway and that is easier and faster on SSA[1, and more]. The dominance frontiers algorithm is actually not that good imho, there are better options[2], especially considering that one may not want to construct an unnecessary dominance tree in an Interpreter/VM. Now, I have no experience how much overhead SSA-deconstruction inflicts when lowering to machine code.

[1] http://www.cdl.uni-saarland.de/projects/ssara/ [2] http://www.cdl.uni-saarland.de/projects/ssaconstr/

Yes, I'm associated with that group.

> the dominance frontiers algorithm

AFAIK V8 does not use dominance frontier based algorithm for SSA construction. It just inserts phis eagerly at loops headers and on forward edges it inserts phis when merge is needed.

> So asm.js took a beeline - leveraging existing Javascript machinery for security/JIT and shoehorning a way to run executable LLVM on top of it.

A big advantage of asm.js over PNaCl is that it's not LLVM.

On the other hand PNaCl is very tightly coupled to LLVM. Any time I find myself checking if a some $feature is available in PNaCl, the discussion revolves around what LLVM can or can't do and how LLVM does it, see [1] for most recent example.

I just can't see how PNaCl could be meaningfully reimplemented. Reimplementing it from scratch would require implementing something bug-for-bug compatible with LLVM. That's a gargantuan task. On the other end of the spectrum, why not just use the original implementation? Then it would work very much like any other plugin. I don't think it's a good solution. It seems the only remaining option is implementing it on top of LLVM. But then you still share all potential limitations (e.g. in portability) and all security issues with all other LLVM-based implementations. It could end up being not that bad -- it means more work on LLVM itself, making it better -- but I'm not sure if that would offset the other problems. How many features that appeared first in chrome or webkit were then reimplemented elsewhere in a different, better way? Do we want to end up with only one browser? No, there are lots of things we wouldn't have if Firefox didn't happen, there are lots of things we wouldn't have if Chrome didn't happen. Do we want to end up with only one PNaCl runtime?

[1]: https://code.google.com/p/nativeclient/issues/detail?id=3475

I think you're conflating frontend and back end. As they currently exist both asm.js and PNaCl frontends are LLVM, if just because it's a good C/C++ solution to parse and optimize. The backend is indeed an LLVM subset as of today for PNaCl and not asm.js, but it's a very restricted subset because the complex bitcode definition LLVM has was pruned a lot for PNaCl, both to distance it from LLVM churn and to make it implementable in another VM.

It is definitely possible to implement a non LLVM back end for PNaCl.

The bug you quote is quite the opposite of what you state: Mark was explaining how complex and potentially often varying LLVM's representation of atomics was. There is a need for atomics to express the full breadth of capabilities C11/C++11 has, but it has to be solved in a way that is close to the standard and no more, non of LLVM's quirks and legacy cruft (LLVM predates these standards, launched PNaCl does not). The primitives also have to be packaged portably so that they can be expressed correctly on any hardware targets (this happens to be tricky to get right, especially since Clang usually makes assumptions about the target). I think PNaCl got this one exactly right, but then again I'm the one who implemented this. :-)

> As they currently exist both asm.js and PNaCl frontends are LLVM (...)

I don't think it's fair to call LLVM a frontend for asm.js just because LLVM can compile to asm.js. By that logic LLVM is also a frontend for x86. That doesn't mean anything. Asm.js is a platform, LLVM is a compiler, it's expected that LLVM can target it asm.js, so can other compilers. Hopefully both asm.js and PNaCl will be targeted by multiple compilers not using LLVM.

> It is definitely possible to implement a non LLVM back end for PNaCl.

Anything's possible. Reimplementing PNaCl from scratch (custom everything) obviously will take much more work than implementing it on top of LLVM. However i honestly think that there would be a large chasm between PNaCl on top of LLVM and PNaCl on top of any other virtual machine. And this is a problem.

EDIT:

I think i'm too focused on LLVM, sorry about that. What I should have written but didn't: PNaCl is hard to reimplement, and not only because it's a large project. For example iirc Chrome doesn't explicitly support the asm.js pragma and doesn't try to be compliant, but it already performs many of the optimizations from the its spec and the Chrome team appears receptive of changes that make this sorta support better. If things continue that way, soon it won't matter if Chrome supports the pragma or not. I.e. right now Chrome supports (say) 10% asm.js and eventually it could support up to 90% with no problems. On the other hand can Firefox implement PNaCl piecemally? What would a 10% reimplementation of PNaCl look like? I think even a 90% or anything else short of a full implementation will not be interoperable.

From a developer's perspective PNaCl and emscripten is almost the same to work with, the difference is just a couple of hundred lines of wrapper code (less then the differences betwenn iOS and Android wrapper code) and you need to find a higher abstraction layer for threaded code. And if the differences on the surface are so small, and the performance difference is acceptable as well (it is IMHO), I don't really care how the goal is achieved under the hood. Asm.js or PNaCl are not platform-lock-ins like DirectX or Flash. It's just POSIX + OpenGL with a handful of platform-specific functions, and practically the same code compiles on any other POSIXish + OpenGLish platform.

Good enough for C++, but with JVM/CLR languages running them right in the browser would be more ideal.

You're just considering the game-perspective, where you don't need anything but GL and sound. What about WebRTC? What about DOM manipulation? You can't do this from Emscripten very well.

It's actually really easy to build C interfaces to any Javascript API or lib. Since compiled code is just JS you can just directly call from C code into JS code and vice-versa. Most of emscripten's CRT wrapper is actually implemented in hand-written JS, as well as the OpenGL-to-WebGL wrapper. For an app which mainly needs to do DOM manipulation it is probably better to write it mostly in traditional JS and only implement the performance sensitive stuff in a C library compiled to JS. Best of both worlds...

How is PNaCl not Chromium lock-in? Pepper is defined by the Chromium implementation.

Only if you look at the generated binary. But the source code which created this binary can be compiled to a myriad of other platforms with only minimal changes. You can compile the (mostly) same source code to JS+WebGL, iOS, Android, OSX, Linux (SteamOS), even Windows (but not Windows Store apps), ... The differences between these platforms is about 1% or 2% of lines of code in a typical 3D game. Compared to porting a game to, say the Xbox One or WiiU this is "peanuts".

The other big advantage of PNaCl is that you have the option of distributing it as a signed application that the user downloads once. This is critical for doing in-browser encryption or manipulating sensitive data. You need there to be a trusted runtime that makes this possible, but this can't be done in pure Javascript (where it's too easy to insert malicious code that leaks your keys). It's not enough to simply use a crypto API in the browser either---you don't want the Javascript to touch the data at all (otherwise, it could leak the plaintext). Moreover, unlike Java and Flash, PNaCl code is compiled in such a way that the browser can do just-in-time static analysis to verify that the code cannot escape the runtime. These two features---signed code that's trust-on-first-use and JIT static analysis---make PNaCl a much more desirable runtime than asm.js in my opinion.

> PNaCl code is compiled in such a way that the browser can do just-in-time static analysis to verify that the code cannot escape the runtime.

You can (and people do) similar things to sandbox JS, by running it in an iframe or a web worker, for example, plus some static analysis.

Also, the structure of asm.js ensures that the code inside it cannot access outside except through a small number of statically analyzable entry points. You can likewise verify no one modifies the asm.js data array by putting the entire codebase in a closure, and doing a trivial static analysis to see that it is not used.

How do I verify the integrity of the sandbox JS, especially since I potentially have to download it each time I need it? Similarly, how do I verify the integrity of the asm.js code I'm receiving? Integrity is just as important, if not more important, than static analysis---for example, a malicious JS crypto library could pass a static analysis test, but intentionally generate weak keys.

There are ways to integrity checks manually, of course, but as far as I know the browser does not perform these integrity checks automatically (and it would be difficult to do so--you'd need to implement JS signing, and you'd need to implement PKI to get the right public keys to verify the JS signatures).

So your argument in favour of PNaCl is a completely incidental feature of it that could be (probably quite easily) added to regular javascript and is really just a workaround for the fact that the PKI trust model for SSL is totally broken?

That's a pretty odd way to end up lumped with a technology.

I need to verify that not only does the JS I received behave correctly (i.e. it will be appropriately sandboxed), but also that the JS I received from the server is the one that the developer intended to serve me. This is because even with perfectly secure transport, a compromised server can always give me JS that is valid and stays sandboxed, but does bad things (such as generating weak keys).

I need to perform an integrity check on the JS to satisfy the second requirement, and the integrity check should not depend on the server that served the JS (since a compromised server could lie about its hash, for example). Moreover, the check needs to be automatic, and trustworthy. One solution is to check the hash of the JS against known-good hashes from the developers (i.e. get the JS from the website, and get the hash from a CA), and then cache the JS locally until I determine that a new version of the JS exists (I want to avoid re-downloading it over and over--that only gives MITM and MITS attackers more chances to serve me bad JS, and it's slow). Not an easy problem; otherwise we'd be doing it already :)

PNaCl offers the infrastructure to do this. I would use asm.js if it did so as well.

> asm.js's compatibility with existing Javascript engines gives it the best chance of adoption.

This is the key. With asm.js the worst case is slow, not totally broken.

Which is why Google should have a PNaCl javascript implementation, so that it degrades gracefully like asm.js but the fast case is faster.

There you go http://trypepperjs.appspot.com/

Awesome. I had indeed seen this before and forgotten about it.