Concurrency support for PNaCl ABI

docs/PNaClLangRef.rst

Index: docs/PNaClLangRef.rst
diff --git a/docs/PNaClLangRef.rst b/docs/PNaClLangRef.rst
index b1d39a7187806fc36a4dc8a54d38feb6441eb48d..d2b0cf8581dc7bb7743bf323688c6ad03965a8d4 100644
--- a/docs/PNaClLangRef.rst
+++ b/docs/PNaClLangRef.rst
@@ -106,21 +106,76 @@ Volatile Memory Accesses
 
 `LLVM LangRef: Volatile Memory Accesses <LangRef.html#volatile>`_
 
-TODO: are we going to promote volatile to atomic?
+We recommend that C11/C++11 atomics be used instead of ``volatile``.

[Mark Seaborn, 2013/06/26 14:33:41]

Saying "we recommend" is kind of vague.  If this document is a reference, it
should be about what guarantees PNaCl does and doesn't provide.  In W3C specs,
recommendations usually go in sections labeled "non-normative".  Maybe you could
do something similar here, and separate the recommendations from the
specification of the behaviour?

[JF, 2013/06/26 15:52:29]

Should I just offer a rationale? The original LLVM Bitcode Reference manual does
this.

[eliben, 2013/06/26 16:20:57]

This document serves a very specific role: it documents the bitcode - currently
in semantic terms, but later more strictly - describing the binary encoding as
well. It's not user-facing documentation. JF - the sections you have added seem
to be useful to programmers porting to PNaCl, and not only people interested in
targeting PNaCl in other toolchains.

I suppose we can leave it here for now, for lack of a better place, but
eventually we should have a separate "user manual" where descriptions like these
belong.

[Mark Seaborn, 2013/06/26 16:47:01]

Maybe.  A rationale could be useful.  But a rationale is still different from
recommendations.

[JF, 2013/06/26 22:56:36]

I meant: a rationale for the recommendation: "We recommend not using volatile
because volatile doesn't do what you think it does".

+
+The C and C++ standards mandate that ``volatile`` accesses execute in
+program order (but are not fences, so other memory operations can
+reorder around them), are not necessarily atomic, and can’t be elided or
+fused.
+
+The PNaCl toolchain applies regular LLVM optimizations along these
+guidelines, and the PNaCl then toolchain freezes ``volatile`` accesses
+into atomic accesses with sequential consistency memory ordering. This
+eases the support of legacy (i.e. non-C11/C++11) code, and combined with
+builtin fences these programs can do meaningful cross-thread
+communication without changing code.
+
+Relaxed ordering could be used instead, but for the first release it is
+more conservative to apply sequential consistency. Future releases may
+change what happens at compile-time, but already-release pexes will
+continue using sequential consistency.
+
+The PNaCl toolchain also tries to guarantee natural alignment of
+``volatile`` accesses, a requirement for atomicity on some platforms.
 
 Memory Model for Concurrent Operations
 --------------------------------------
 
 `LLVM LangRef: Memory Model for Concurrent Operations <LangRef.html#memmodel>`_
 
-TODO.
+The PNaCl toolchain currently supports concurrent memory accesses
+through legacy GCC-style ``__sync_*`` builtins, as well as through
+C11/C++11 atomic primitives. ``volatile`` memory accesses can also be
+used, though these are discouraged.
+
+Note that PNaCl explicitly supports concurrency through threading, but
+doesn't support interacting with device memory, nor does it attempt to
+support cross-program communication, including through shared

[Mark Seaborn, 2013/06/26 14:33:41]

"Cross-program" is vague.  Do you mean cross-process?  I think it will be
confusing to developers to say here that PNaCl doesn't support shared memory
when PPAPI will add this soon.

[JF, 2013/06/26 15:52:29]

Yes, cross-process. Are you saying that I should avoid mentioning either?

[eliben, 2013/06/26 16:20:57]

Isn't the more commonly known term "inter-process communication" (IPC) - at
least this is how it's usually called in linux

[Mark Seaborn, 2013/06/26 16:47:01]

Yes.  Cross-process communication includes message-passing, which we do support.
 Since we'll soon support shared memory, I don't think you should rule it out
here.

[JF, 2013/06/26 22:56:36]

Agreed, if we're soon going to offer IPC then it shouldn't be ruled out here.

My aim with this paragraph is to specify what you can do with concurrency as
well as what a PNaCl backend must guarantee and care about.

What do we guarantee w.r.t. IPC? I think it's the same guarantees as
cross-thread?

[Mark Seaborn, 2013/06/27 01:04:33]

Yes, the guarantees with memory shared between processes should be the same as
the guarantees with memory shared between threads.

[JF, 2013/06/27 01:31:39]

Great. I updated the comment.

+memory. These concerns are left up to the embedding sandbox's runtime
+(e.g. NaCl's Pepper APIs).
+
+PNaCl also doesn't currently support signal handling, and therefore
+promotes all primitives to cross-thread (instead of single-thread). This
+may change at a later date.
+
+The PNaCl toolchain currently optimizes for memory ordering as LLVM
+normally does, but at pexe creation time it promotes all ``volatile``
+accesses as well as all atomic accesses to be sequentially consistent.
+
+This means that ``volatile`` and atomic memory accesses can only be
+re-ordered before the pexe is created, and will act as fences for all
+memory accesses (even non-atomic and non-``volatile``) after pexe
+creation. Non-atomic and non-``volatile`` memory accesses may be
+reordered (unless a fence intervenes), separate, elided or fused
+according to C and C++'s memory model before the pexe is created as well
+as after its creation.
 
 Atomic Memory Ordering Constraints
 ----------------------------------
 
 `LLVM LangRef: Atomic Memory Ordering Constraints <LangRef.html#ordering>`_
 
-TODO.
+Atomics follow the same ordering constraints as in regular LLVM, but all
+accesses are promoted to sequential consistency (the strongest memory
+ordering) at pexe creation time. We may relax these rules an honor the

[Mark Seaborn, 2013/06/26 14:33:41]

"an" -> "and"

[JF, 2013/06/26 15:52:29]

Done.

+program's memory ordering constraints as more C11/C++11 code allows us
+to understand performance and portability needs.
+
+As in C11/C++11:
+
+ - Atomic accesses must at least be naturally aligned.
+ - Some accesses may not actually be atomic on certain platforms,
+   requiring an implementation that uses a global lock.
 
 Fast-Math Flags
 ---------------
@@ -270,14 +325,6 @@ Only the LLVM instructions listed here are supported by PNaCl bitcode.
   The pointer argument of these instructions must be a *normalized* pointer
   (see :ref:`pointer types <pointertypes>`).
 
-* ``fence``
-* ``cmpxchg``, ``atomicrmw``
-
-  The pointer argument of these instructions must be a *normalized* pointer
-  (see :ref:`pointer types <pointertypes>`).
-
-  TODO(jfb): this may change
-
 * ``trunc``
 * ``zext``
 * ``sext``
@@ -316,8 +363,6 @@ Intrinsic Functions
 
 The only intrinsics supported by PNaCl bitcode are the following.
 
-TODO(jfb): atomics
-
 * ``llvm.memcpy``
 * ``llvm.memmove``
 * ``llvm.memset``
@@ -346,3 +391,40 @@ TODO(jfb): atomics
 
   TODO: describe
 
+* ``llvm.nacl.atomic.8``

[eliben, 2013/06/26 16:20:57]

It's not clear what the prototype of these intrinsics is. Since they're NaCl
specific, we should document it.

[JF, 2013/06/26 22:23:12]

I moved this documentation from Intrinsics.td to this document instead.

+* ``llvm.nacl.atomic.16``
+* ``llvm.nacl.atomic.32``
+* ``llvm.nacl.atomic.64``
+
+  These intrinsics provide support for atomic accesses at 8, 16, 32 and
+  64-bit sizes for primitives required to implement C11/C++11 atomic
+  accesses:
+
+   - load
+   - store
+   - add
+   - sub
+   - or
+   - and
+   - xor
+   - xchg
+   - cmpxchg
+   - fence
+
+  They also support C11/C++11 memory orderings:
+
+   - Relaxed: no operation orders memory.
+   - Consume: a load operation performs a consume operation on the
+     affected memory location (currently unsupported by LLVM).
+   - Acquire: a load operation performs an acquire operation on the
+     affected memory location.
+   - Release: a store operation performs a release operation on the
+     affected memory location.
+   - Acquire-release: load and store operations perform acquire and
+     release operations on the affected memory.
+   - Sequentially consistent: same as acquire-release, but providing a
+     total ordering for all affected locations.
+
+  Note that PNaCl currently strengthens all memory ordering
+  specifications to sequential consistency, the strongest form of memory
+  ordering.