Subzero. Wasm. Implement sbrk and correctly do bounds checks.

Subzero. Wasm. Implement sbrk and correctly do bounds checks.

Cleans up and generally improves memory handling in
WASM. WasmTranslator now outputs the number of pages requested so the
runtime can do correct bounds checks. The runtime also initializes the
stack pointer correctly (stored at address 1024), so we no longer have
to deal with negative pointers. This allows bounds checks to be done
with a single comparison against the size of the heap. Because of
this, we now support non-power-of-two heap sizes.

Sbrk is implemented by having the runtime keep track of the current
heap break and incrementing it as necessary. The heap break is
initialized to the start of the first page beyond any initialized data
in the WASM heap.

These changes allow us to pass the complete set of torture tests that
are passing on the Wasm waterfall.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4369
R=kschimpf@google.com, stichnot@chromium.org

Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a=commit;h=4aae81af8a41f824ab80c58fd84113817431fcc6

[Eric Holk, 2016-04-22 18:37:27]

eholk@chromium.org changed reviewers:
+ jpp@chromium.org, kschimpf@google.com, sehr@chromium.org,
stichnot@chromium.org

[Karl, 2016-04-22 19:18:14]

Otherwise, LGTM.

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp
File src/WasmTranslator.cpp (right):

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp#...
src/WasmTranslator.cpp:1315: CfgNode *getAbortTarget() {
Does this need an atomic or a mutex to avoid multiple generations.

You should be able to do this using an "std::atomic_bool createAbortTarget;",
initialize it to true, and then use:

   if (!AbortTarget) {
     if (createAbortTarget.exchange(false)) {
       ... create abort target
     }
   }

[Jim Stichnoth, 2016-04-22 20:48:54]

Awesome!

https://codereview.chromium.org/1913153003/diff/20001/pydir/wasm-run-torture-...
File pydir/wasm-run-torture-tests.py (right):

https://codereview.chromium.org/1913153003/diff/20001/pydir/wasm-run-torture-...
pydir/wasm-run-torture-tests.py:24: # waterfall known failures
There are a number of blank lines in this list, without a leading comment.  That
makes me wonder whether they all belong to the set of "waterfall known
failures".  If so, I suggest making that clear in the comment, e.g. "All the
rest are known waterfall failures".

https://codereview.chromium.org/1913153003/diff/20001/runtime/wasm-runtime.cpp
File runtime/wasm-runtime.cpp (right):

https://codereview.chromium.org/1913153003/diff/20001/runtime/wasm-runtime.cp...
runtime/wasm-runtime.cpp:17: #include <stdint.h>
<cstdint> ?
(I think cstdint requires C++11 or later)

https://codereview.chromium.org/1913153003/diff/20001/runtime/wasm-runtime.cp...
runtime/wasm-runtime.cpp:21: const int32_t PageSizeLog2 = 16;
constexpr

https://codereview.chromium.org/1913153003/diff/20001/runtime/wasm-runtime.cp...
runtime/wasm-runtime.cpp:21: const int32_t PageSizeLog2 = 16;
If it's a Log2 value, make it uint32_t

https://codereview.chromium.org/1913153003/diff/20001/runtime/wasm-runtime.cp...
runtime/wasm-runtime.cpp:22: const int32_t PageSize = 1 << PageSizeLog2; // 64KB
uint32_t ?

https://codereview.chromium.org/1913153003/diff/20001/runtime/wasm-runtime.cp...
runtime/wasm-runtime.cpp:32: } // end of env namespace
end of namespace env

https://codereview.chromium.org/1913153003/diff/20001/runtime/wasm-runtime.cp...
runtime/wasm-runtime.cpp:47: extern int32_t WASM_DATA_SIZE;
uint32_t ?

https://codereview.chromium.org/1913153003/diff/20001/runtime/wasm-runtime.cp...
runtime/wasm-runtime.cpp:125: WASM_DEREF(int32_t, StackPtrLoc) = WASM_NUM_PAGES
* PageSize;
Instead of "* PageSize", how about "<< PageSizeLog2" ?

This is more in line with the previous statement using PageSize-1 as a bitmask
and therefore counting on PageSize to be a power of 2.

Alternatively or in addition, make PageSize a local var within main().

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp
File src/WasmTranslator.cpp (right):

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp#...
src/WasmTranslator.cpp:1153: return Base;
Another possibility is GlobalContext::getConstantZero() - your call.

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp#...
src/WasmTranslator.cpp:1166: // Do the bounds check.
Maybe in a separate CL, but can you add a flag to allow suppressing the bounds
check?  This would be for perf-testing its impact.

Even better, make the flag be numeric instead of boolean, so that we could mock
the effect of having to make 2 (or more!) cmp/br operations per bounds check.

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp#...
src/WasmTranslator.cpp:1177: *ControlPtr = OperandNode(CheckPassed);
This one is definitely for a separate CL.

I think it's going to be a big problem if every memory access effectively
creates a new basic block.

- Liveness analysis cost increases with the number of nodes.

- A number of low-cost optimizations are suppressed on variables with
multi-block live ranges.  Splitting "natural" blocks because of memory accesses
reduces the number of such opportunities.

To make this work, you might need to introduce a new flavor of InstBr.  There is
already one flavor for conditional branches, and one for unconditional.  The
third flavor would be an intra-block branch to a CfgNode, and this flavor of
branch would not be considered a terminator instruction.  (Actually, maybe that
should be a new instruction type separate from InstBr, to make it easier to roll
in.)

This assumes that the AbortTarget node unconditionally leaves the function and
doesn't have any out-edges to other nodes in this function.  Otherwise we might
have to make changes to liveness analysis.

One last point - in this approach, the AbortTarget wouldn't have any explicit
in-edges, so care would have to be taken that the node doesn't get removed for
being "unreachable".

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp#...
src/WasmTranslator.cpp:1315: CfgNode *getAbortTarget() {
On 2016/04/22 19:18:14, Karl wrote:
> Does this need an atomic or a mutex to avoid multiple generations.
> 
> You should be able to do this using an "std::atomic_bool createAbortTarget;",
> initialize it to true, and then use:
> 
>    if (!AbortTarget) {
>      if (createAbortTarget.exchange(false)) {
>        ... create abort target
>      }
>    }

I don't think there's any concurrency at this level, so atomics should be
unnecessary.

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp#...
src/WasmTranslator.cpp:1317: AbortTarget = Func->makeNode();
I think it's best if you can somehow force this node to be at the end of the
linearization list.  Or maybe it will just happen naturally during a
re-linearization pass?

[Eric Holk, 2016-04-22 21:02:10]

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp
File src/WasmTranslator.cpp (right):

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp#...
src/WasmTranslator.cpp:1315: CfgNode *getAbortTarget() {
On 2016/04/22 19:18:14, Karl wrote:
> Does this need an atomic or a mutex to avoid multiple generations.
> 
> You should be able to do this using an "std::atomic_bool createAbortTarget;",
> initialize it to true, and then use:
> 
>    if (!AbortTarget) {
>      if (createAbortTarget.exchange(false)) {
>        ... create abort target
>      }
>    }

I think unless we have plans to parallelize Wasm decoding as finer granularity
than per function that there's no reason to do this.

The IceBuilder that contains this abort target is created and destroyed for each
function that is translated (see WasmTranslator::translateFunction around line
1343). There shouldn't be any way for this data to be shared between threads.

[Eric Holk, 2016-04-22 22:32:48]

https://codereview.chromium.org/1913153003/diff/20001/pydir/wasm-run-torture-...
File pydir/wasm-run-torture-tests.py (right):

https://codereview.chromium.org/1913153003/diff/20001/pydir/wasm-run-torture-...
pydir/wasm-run-torture-tests.py:24: # waterfall known failures
On 2016/04/22 20:48:53, stichnot wrote:
> There are a number of blank lines in this list, without a leading comment. 
That
> makes me wonder whether they all belong to the set of "waterfall known
> failures".  If so, I suggest making that clear in the comment, e.g. "All the
> rest are known waterfall failures".

Done.

https://codereview.chromium.org/1913153003/diff/20001/runtime/wasm-runtime.cpp
File runtime/wasm-runtime.cpp (right):

https://codereview.chromium.org/1913153003/diff/20001/runtime/wasm-runtime.cp...
runtime/wasm-runtime.cpp:17: #include <stdint.h>
On 2016/04/22 20:48:53, stichnot wrote:
> <cstdint> ?
> (I think cstdint requires C++11 or later)

So far I've been avoiding using C++11 because of some silliness with how Clang
tries to apply -std=c++11 to .c files as well. I'd rather delay the shift to
C++11 until I have a more principled way of building the runtime.

I'll add a TODO to remind me to switch this.

https://codereview.chromium.org/1913153003/diff/20001/runtime/wasm-runtime.cp...
runtime/wasm-runtime.cpp:21: const int32_t PageSizeLog2 = 16;
On 2016/04/22 20:48:53, stichnot wrote:
> constexpr

See my previous comment about C++11. I added a TODO to add constexpr once I get
C++11 enabled.

https://codereview.chromium.org/1913153003/diff/20001/runtime/wasm-runtime.cp...
runtime/wasm-runtime.cpp:21: const int32_t PageSizeLog2 = 16;
On 2016/04/22 20:48:54, stichnot wrote:
> If it's a Log2 value, make it uint32_t

Done.

https://codereview.chromium.org/1913153003/diff/20001/runtime/wasm-runtime.cp...
runtime/wasm-runtime.cpp:22: const int32_t PageSize = 1 << PageSizeLog2; // 64KB
On 2016/04/22 20:48:53, stichnot wrote:
> uint32_t ?

Done. I'll replace most of the other int32_t with uint32_t now. Since I'm
explicitly setting the stack pointer now, negative memory addresses aren't being
used which means most of what was signed should be unsigned.

https://codereview.chromium.org/1913153003/diff/20001/runtime/wasm-runtime.cp...
runtime/wasm-runtime.cpp:32: } // end of env namespace
On 2016/04/22 20:48:53, stichnot wrote:
> end of namespace env

Done.

https://codereview.chromium.org/1913153003/diff/20001/runtime/wasm-runtime.cp...
runtime/wasm-runtime.cpp:47: extern int32_t WASM_DATA_SIZE;
On 2016/04/22 20:48:53, stichnot wrote:
> uint32_t ?

Done.

https://codereview.chromium.org/1913153003/diff/20001/runtime/wasm-runtime.cp...
runtime/wasm-runtime.cpp:125: WASM_DEREF(int32_t, StackPtrLoc) = WASM_NUM_PAGES
* PageSize;
On 2016/04/22 20:48:53, stichnot wrote:
> Instead of "* PageSize", how about "<< PageSizeLog2" ?
> 
> This is more in line with the previous statement using PageSize-1 as a bitmask
> and therefore counting on PageSize to be a power of 2.
> 
> Alternatively or in addition, make PageSize a local var within main().

I like the shift better, so done.

I'd rather keep both PageSize and PageSizeLog2 as a global, since it'll probably
be convenient to have both in other portions of the runtime too.

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp
File src/WasmTranslator.cpp (right):

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp#...
src/WasmTranslator.cpp:1153: return Base;
On 2016/04/22 20:48:54, stichnot wrote:
> Another possibility is GlobalContext::getConstantZero() - your call.

Returning 0 is better. It means that even this dereference manages to happen
somehow it will still trap by being a null pointer dereference.

Done.

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp#...
src/WasmTranslator.cpp:1166: // Do the bounds check.
On 2016/04/22 20:48:54, stichnot wrote:
> Maybe in a separate CL, but can you add a flag to allow suppressing the bounds
> check?  This would be for perf-testing its impact.
> 
> Even better, make the flag be numeric instead of boolean, so that we could
mock
> the effect of having to make 2 (or more!) cmp/br operations per bounds check.

I added a TODO.

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp#...
src/WasmTranslator.cpp:1177: *ControlPtr = OperandNode(CheckPassed);
On 2016/04/22 20:48:54, stichnot wrote:
> This one is definitely for a separate CL.
> 
> I think it's going to be a big problem if every memory access effectively
> creates a new basic block.
> 
> - Liveness analysis cost increases with the number of nodes.
> 
> - A number of low-cost optimizations are suppressed on variables with
> multi-block live ranges.  Splitting "natural" blocks because of memory
accesses
> reduces the number of such opportunities.
> 
> To make this work, you might need to introduce a new flavor of InstBr.  There
is
> already one flavor for conditional branches, and one for unconditional.  The
> third flavor would be an intra-block branch to a CfgNode, and this flavor of
> branch would not be considered a terminator instruction.  (Actually, maybe
that
> should be a new instruction type separate from InstBr, to make it easier to
roll
> in.)
> 
> This assumes that the AbortTarget node unconditionally leaves the function and
> doesn't have any out-edges to other nodes in this function.  Otherwise we
might
> have to make changes to liveness analysis.
> 
> One last point - in this approach, the AbortTarget wouldn't have any explicit
> in-edges, so care would have to be taken that the node doesn't get removed for
> being "unreachable".

I added a TODO, with a link to this comment.

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp#...
src/WasmTranslator.cpp:1317: AbortTarget = Func->makeNode();
On 2016/04/22 20:48:54, stichnot wrote:
> I think it's best if you can somehow force this node to be at the end of the
> linearization list.  Or maybe it will just happen naturally during a
> re-linearization pass?

Do you know a good strategy for doing this off hand?

This node currently ends up somewhere in the middle of the function.

[Jim Stichnoth, 2016-04-23 16:23:05]

lgtm

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp
File src/WasmTranslator.cpp (right):

https://codereview.chromium.org/1913153003/diff/20001/src/WasmTranslator.cpp#...
src/WasmTranslator.cpp:1317: AbortTarget = Func->makeNode();
On 2016/04/22 22:32:48, Eric Holk wrote:
> On 2016/04/22 20:48:54, stichnot wrote:
> > I think it's best if you can somehow force this node to be at the end of the
> > linearization list.  Or maybe it will just happen naturally during a
> > re-linearization pass?
> 
> Do you know a good strategy for doing this off hand?
> 
> This node currently ends up somewhere in the middle of the function.

I would probably just do a post-pass that heavy-handedly moves it to the end of
the node vector, making sure to properly renumber the nodes.

Leave it as a TODO for now. :)

https://codereview.chromium.org/1913153003/diff/40001/src/WasmTranslator.cpp
File src/WasmTranslator.cpp (right):

https://codereview.chromium.org/1913153003/diff/40001/src/WasmTranslator.cpp#...
src/WasmTranslator.cpp:1153: return Ctx->getConstantZero(IceType_i32);
Maybe use getPointerType() instead of IceType_i32, to be a bit more
future-proof?

https://codereview.chromium.org/1913153003/diff/40001/src/WasmTranslator.cpp#...
src/WasmTranslator.cpp:1173: // terrible (see https://goto.google.com/aqydy). 
Try adding a new
Use a link that is externally viewable...

[Eric Holk, 2016-04-25 19:52:51]

Description was changed from

==========
Subzero. Wasm. Implement sbrk and correctly do bounds checks.

Cleans up and generally improves memory handling in
WASM. WasmTranslator now outputs the number of pages requested so the
runtime can do correct bounds checks. The runtime also initializes the
stack pointer correctly (stored at address 1024), so we no longer have
to deal with negative pointers. This allows bounds checks to be done
with a single comparison against the size of the heap. Because of
this, we now support non-power-of-two heap sizes.

Sbrk is implemented by having the runtime keep track of the current
heap break and incrementing it as necessary. The heap break is
initialized to the start of the first page beyond any initialized data
in the WASM heap.

These changes allow us to pass the complete set of torture tests that
are passing on the Wasm waterfall.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4369
==========

to

==========
Subzero. Wasm. Implement sbrk and correctly do bounds checks.

Cleans up and generally improves memory handling in
WASM. WasmTranslator now outputs the number of pages requested so the
runtime can do correct bounds checks. The runtime also initializes the
stack pointer correctly (stored at address 1024), so we no longer have
to deal with negative pointers. This allows bounds checks to be done
with a single comparison against the size of the heap. Because of
this, we now support non-power-of-two heap sizes.

Sbrk is implemented by having the runtime keep track of the current
heap break and incrementing it as necessary. The heap break is
initialized to the start of the first page beyond any initialized data
in the WASM heap.

These changes allow us to pass the complete set of torture tests that
are passing on the Wasm waterfall.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4369
R=kschimpf@google.com, stichnot@chromium.org

Committed:
https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a...
==========

[Eric Holk, 2016-04-25 19:52:53]

Committed patchset #3 (id:40001) manually as
4aae81af8a41f824ab80c58fd84113817431fcc6 (presubmit successful).

[Eric Holk, 2016-04-25 19:53:04]

https://codereview.chromium.org/1913153003/diff/40001/src/WasmTranslator.cpp
File src/WasmTranslator.cpp (right):

https://codereview.chromium.org/1913153003/diff/40001/src/WasmTranslator.cpp#...
src/WasmTranslator.cpp:1153: return Ctx->getConstantZero(IceType_i32);
On 2016/04/23 16:23:04, stichnot wrote:
> Maybe use getPointerType() instead of IceType_i32, to be a bit more
> future-proof?

Done.

https://codereview.chromium.org/1913153003/diff/40001/src/WasmTranslator.cpp#...
src/WasmTranslator.cpp:1173: // terrible (see https://goto.google.com/aqydy). 
Try adding a new
On 2016/04/23 16:23:04, stichnot wrote:
> Use a link that is externally viewable...

I thought goto was, but just to be safe, I switched it to a goo.gl link.