Subzero: Add sandboxing for x86-32.

Subzero: Add sandboxing for x86-32.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4079
R=jvoung@chromium.org, kschimpf@google.com

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

[Jim Stichnoth, 2015-02-17 20:45:41]

stichnot@chromium.org changed reviewers:
+ jvoung@chromium.org, kschimpf@google.com, shyamsundarr@chromium.org

[Jim Stichnoth, 2015-02-17 20:53:11]

This is not ready for review yet.

I'd appreciate feedback on the bundling logic in CfgNode::emitIAS().  It
basically seems to more or less work, by virtue of not crashing or asserting in
the instruction loop.

For completeness, the integrated assembler needs a few more things:
  - Local labels should be allowed to be bound more than once, due to bundling
retries.
  - j() and jmp() should always assume forward branch labels are not bound,
because of retries.
  - j() and jmp() near backward branch calculation should be conservative in
align_to_end mode, because after initial padding, the backward branch could
become far.

I don't think any of these issues will come up in practice, though, due to the
limited bundling sequences we use.

[jvoung (off chromium), 2015-02-17 22:57:45]

https://codereview.chromium.org/930733002/diff/80001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/930733002/diff/80001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:1006: if ((BufSizePre & BundleMask) != (BufSizePost &
BundleMask)) {
Maybe put this into an inlined helper function.

https://codereview.chromium.org/930733002/diff/80001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:1010: I->emitIAS(Func);
Besides labels being bound twice, I think the other thing to check is that
fixups aren't recorded twice, and then converted to relocs by the elf writer.

[jvoung (off chromium), 2015-02-17 23:01:16]

On 2015/02/17 20:53:11, stichnot wrote:
> This is not ready for review yet.
> 
> I'd appreciate feedback on the bundling logic in CfgNode::emitIAS().  It
> basically seems to more or less work, by virtue of not crashing or asserting
in
> the instruction loop.
> 
> For completeness, the integrated assembler needs a few more things:
>   - Local labels should be allowed to be bound more than once, due to bundling
> retries.
>   - j() and jmp() should always assume forward branch labels are not bound,
> because of retries.

Does this include the "local" forward branches? The margin is *probably* still
okay to use the 8-bit encoding for those?


>   - j() and jmp() near backward branch calculation should be conservative in
> align_to_end mode, because after initial padding, the backward branch could
> become far.

Can this really be a problem? The target of the jump doesn't get shifted by the
time the backward branch is assembled, so the issue is if the branch itself
moves from padding? However, in that case you check and retry the branch, so the
retry will know the new distance.


> I don't think any of these issues will come up in practice, though, due to the
> limited bundling sequences we use.

[Jim Stichnoth, 2015-02-17 23:34:00]

On 2015/02/17 23:01:16, jvoung wrote:
> On 2015/02/17 20:53:11, stichnot wrote:
> > This is not ready for review yet.
> > 
> > I'd appreciate feedback on the bundling logic in CfgNode::emitIAS().  It
> > basically seems to more or less work, by virtue of not crashing or asserting
> in
> > the instruction loop.
> > 
> > For completeness, the integrated assembler needs a few more things:
> >   - Local labels should be allowed to be bound more than once, due to
bundling
> > retries.
> >   - j() and jmp() should always assume forward branch labels are not bound,
> > because of retries.
> 
> Does this include the "local" forward branches? The margin is *probably* still
> okay to use the 8-bit encoding for those?

Right, I didn't mean the "local" branches, and I agree that the lowering
sequence shouldn't be so long as to make bundling an issue.

> 
> >   - j() and jmp() near backward branch calculation should be conservative in
> > align_to_end mode, because after initial padding, the backward branch could
> > become far.
> 
> Can this really be a problem? The target of the jump doesn't get shifted by
the
> time the backward branch is assembled, so the issue is if the branch itself
> moves from padding? However, in that case you check and retry the branch, so
the
> retry will know the new distance.

For align_to_end, it does a speculative emission, then most likely rolls back
and adds one or two chunks of padding, then does the final emission.  The
backward branch target won't move, but the branch instruction may move further
away due to padding, and that could be enough to change it to a 4-byte branch
and then it would fail to align_to_end.

[jvoung (off chromium), 2015-02-18 01:35:36]

On 2015/02/17 23:34:00, stichnot wrote:
> On 2015/02/17 23:01:16, jvoung wrote:
> > On 2015/02/17 20:53:11, stichnot wrote:
> > > This is not ready for review yet.
> > > 
> > > I'd appreciate feedback on the bundling logic in CfgNode::emitIAS().  It
> > > basically seems to more or less work, by virtue of not crashing or
asserting
> > in
> > > the instruction loop.
> > > 
> > > For completeness, the integrated assembler needs a few more things:
> > >   - Local labels should be allowed to be bound more than once, due to
> bundling
> > > retries.
> > >   - j() and jmp() should always assume forward branch labels are not
bound,
> > > because of retries.
> > 
> > Does this include the "local" forward branches? The margin is *probably*
still
> > okay to use the 8-bit encoding for those?
> 
> Right, I didn't mean the "local" branches, and I agree that the lowering
> sequence shouldn't be so long as to make bundling an issue.
> 
> > 
> > >   - j() and jmp() near backward branch calculation should be conservative
in
> > > align_to_end mode, because after initial padding, the backward branch
could
> > > become far.
> > 
> > Can this really be a problem? The target of the jump doesn't get shifted by
> the
> > time the backward branch is assembled, so the issue is if the branch itself
> > moves from padding? However, in that case you check and retry the branch, so
> the
> > retry will know the new distance.
> 
> For align_to_end, it does a speculative emission, then most likely rolls back
> and adds one or two chunks of padding, then does the final emission.  The
> backward branch target won't move, but the branch instruction may move further
> away due to padding, and that could be enough to change it to a 4-byte branch
> and then it would fail to align_to_end.

Ouch, okay I see what you mean... I guess in llvm-mc things that are part of a
bundle-lock/unlock are pessimistically "relaxed" to the 4-bit variant as well, I
think. If the branch isn't part of a bundle-lock/unlock group it doesn't need to
be relaxed?

[jvoung (off chromium), 2015-02-18 01:37:50]

On 2015/02/18 01:35:36, jvoung wrote:
> On 2015/02/17 23:34:00, stichnot wrote:
> > On 2015/02/17 23:01:16, jvoung wrote:
> > > On 2015/02/17 20:53:11, stichnot wrote:
> > > > This is not ready for review yet.
> > > > 
> > > > I'd appreciate feedback on the bundling logic in CfgNode::emitIAS().  It
> > > > basically seems to more or less work, by virtue of not crashing or
> asserting
> > > in
> > > > the instruction loop.
> > > > 
> > > > For completeness, the integrated assembler needs a few more things:
> > > >   - Local labels should be allowed to be bound more than once, due to
> > bundling
> > > > retries.
> > > >   - j() and jmp() should always assume forward branch labels are not
> bound,
> > > > because of retries.
> > > 
> > > Does this include the "local" forward branches? The margin is *probably*
> still
> > > okay to use the 8-bit encoding for those?
> > 
> > Right, I didn't mean the "local" branches, and I agree that the lowering
> > sequence shouldn't be so long as to make bundling an issue.
> > 
> > > 
> > > >   - j() and jmp() near backward branch calculation should be
conservative
> in
> > > > align_to_end mode, because after initial padding, the backward branch
> could
> > > > become far.
> > > 
> > > Can this really be a problem? The target of the jump doesn't get shifted
by
> > the
> > > time the backward branch is assembled, so the issue is if the branch
itself
> > > moves from padding? However, in that case you check and retry the branch,
so
> > the
> > > retry will know the new distance.
> > 
> > For align_to_end, it does a speculative emission, then most likely rolls
back
> > and adds one or two chunks of padding, then does the final emission.  The
> > backward branch target won't move, but the branch instruction may move
further
> > away due to padding, and that could be enough to change it to a 4-byte
branch
> > and then it would fail to align_to_end.
> 
> Ouch, okay I see what you mean... I guess in llvm-mc things that are part of a
> bundle-lock/unlock are pessimistically "relaxed" to the 4-bit variant as well,
I
> think. If the branch isn't part of a bundle-lock/unlock group it doesn't need
to
> be relaxed?

Err... 4-byte... and sounds like this is basically what you were saying.

[Jim Stichnoth, 2015-02-18 07:06:14]

https://codereview.chromium.org/930733002/diff/80001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/930733002/diff/80001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:1006: if ((BufSizePre & BundleMask) != (BufSizePost &
BundleMask)) {
On 2015/02/17 22:57:45, jvoung wrote:
> Maybe put this into an inlined helper function.

Yeah, this started getting out of control and so I plan to try to simplify all
the alignment calculations soon.

https://codereview.chromium.org/930733002/diff/80001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:1010: I->emitIAS(Func);
On 2015/02/17 22:57:45, jvoung wrote:
> Besides labels being bound twice, I think the other thing to check is that
> fixups aren't recorded twice, and then converted to relocs by the elf writer.

IIUC, binding labels twice isn't fundamentally much of a problem because you can
just overwrite the binding, but linking to a label twice is a real problem
because you need to actively remove the first (incorrect) link.  I haven't
gotten so far yet, but I agree it's probably also necessary to avoid generating
duplicate relocs.

I can't think of a clean and simple way to roll back all the bind/link/reloc
operations done within a bundle lock region (including the implicit
single-instruction bundling) and allow retrying.  So I'm leaning toward
unconditionally making two passes over every bundle locked region, and
signalling to the assembler not to actually create a bind/link/reloc during the
first pass.  Except perhaps to allow rebinding so that near backward branches
within a bundle lock region are allowed/handled.

[jvoung (off chromium), 2015-02-18 18:25:31]

On 2015/02/18 07:06:14, stichnot wrote:
> https://codereview.chromium.org/930733002/diff/80001/src/IceCfgNode.cpp
> File src/IceCfgNode.cpp (right):
> 
>
https://codereview.chromium.org/930733002/diff/80001/src/IceCfgNode.cpp#newco...
> src/IceCfgNode.cpp:1006: if ((BufSizePre & BundleMask) != (BufSizePost &
> BundleMask)) {
> On 2015/02/17 22:57:45, jvoung wrote:
> > Maybe put this into an inlined helper function.
> 
> Yeah, this started getting out of control and so I plan to try to simplify all
> the alignment calculations soon.
> 
>
https://codereview.chromium.org/930733002/diff/80001/src/IceCfgNode.cpp#newco...
> src/IceCfgNode.cpp:1010: I->emitIAS(Func);
> On 2015/02/17 22:57:45, jvoung wrote:
> > Besides labels being bound twice, I think the other thing to check is that
> > fixups aren't recorded twice, and then converted to relocs by the elf
writer.
> 
> IIUC, binding labels twice isn't fundamentally much of a problem because you
can
> just overwrite the binding, but linking to a label twice is a real problem
> because you need to actively remove the first (incorrect) link.  I haven't
> gotten so far yet, but I agree it's probably also necessary to avoid
generating
> duplicate relocs.

I think binding also has side-effects if there are links:

  assert(!label->IsBound()); // Labels can only be bound once.
  while (label->IsLinked()) {
    intptr_t position = label->LinkPosition();
    intptr_t next = buffer_.Load<int32_t>(position);
    buffer_.Store<int32_t>(position, bound - (position + 4));
    label->position_ = next;
    ^^ uh oh!
  }
  while (label->HasNear()) {
    intptr_t position = label->NearPosition();
    ^^ NearPosition() also modifies state =(
    // ...
  }

rebinding could be safe if there are no links I guess.

That said it might be safer overall to do the two pass method so that people
don't have to remember all the caveats... though, I think most instructions
won't deal with bind/link (assuming most instructions are movs or binop of some
kind).

> 
> I can't think of a clean and simple way to roll back all the bind/link/reloc
> operations done within a bundle lock region (including the implicit
> single-instruction bundling) and allow retrying.  So I'm leaning toward
> unconditionally making two passes over every bundle locked region, and
> signalling to the assembler not to actually create a bind/link/reloc during
the
> first pass.  Except perhaps to allow rebinding so that near backward branches
> within a bundle lock region are allowed/handled.

[Jim Stichnoth, 2015-02-19 08:15:46]

On 2015/02/18 18:25:31, jvoung wrote:
> That said it might be safer overall to do the two pass method so that people
> don't have to remember all the caveats... though, I think most instructions
> won't deal with bind/link (assuming most instructions are movs or binop of
some
> kind).

It's true that most instructions don't bind/link, but many instructions may need
fixups.  On the other hand, it seems that it should be a lot easier to
checkpoint/restore the fixups state than the bind/link state.

[Jim Stichnoth, 2015-02-19 18:52:42]

This is now ready for review, though I will soon add some new explicit
sandboxing tests.

For now, I tested with -sandbox and all combinations of
-filetype={asm,iasm,obj}, for spec2k and pnacl-llc.pexe.  None of the copious
assertions fail.

[jvoung (off chromium), 2015-02-19 21:01:47]

Cool -- generally looks good

https://codereview.chromium.org/930733002/diff/160001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/930733002/diff/160001/src/IceCfg.cpp#newcode439
src/IceCfg.cpp:439: Str << "\t.bundle_align_mode " <<
Asm->getBundleAlignLog2Bytes() << "\n";
Should this only be for getUseSandboxing()?

https://codereview.chromium.org/930733002/diff/160001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/930733002/diff/160001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:895: 
could put in an anonymous namespace

https://codereview.chromium.org/930733002/diff/160001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:897: class EmitHelper {
Perhaps have bundle/bundling in the name somewhere?

https://codereview.chromium.org/930733002/diff/160001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:952: // Update bookkeeping when the bundle_unlock instlist is
processed.
instlist -> instruction

https://codereview.chromium.org/930733002/diff/160001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:1032: 
Leave a brief high level comment somewhere about the strategy (unconditional two
passes)?

https://codereview.chromium.org/930733002/diff/160001/src/assembler.h
File src/assembler.h (right):

https://codereview.chromium.org/930733002/diff/160001/src/assembler.h#newcode210
src/assembler.h:210: virtual void padWithNop(intptr_t Padding) = 0;
Maybe put this padWithNop along with the alignFunction method?

https://codereview.chromium.org/930733002/diff/160001/src/assembler.h#newcode219
src/assembler.h:219: bool Preliminary;
Document what Preliminary does

[Jim Stichnoth, 2015-02-19 23:17:39]

https://codereview.chromium.org/930733002/diff/160001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/930733002/diff/160001/src/IceCfg.cpp#newcode439
src/IceCfg.cpp:439: Str << "\t.bundle_align_mode " <<
Asm->getBundleAlignLog2Bytes() << "\n";
On 2015/02/19 21:01:47, jvoung wrote:
> Should this only be for getUseSandboxing()?

Oops, done.

https://codereview.chromium.org/930733002/diff/160001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/930733002/diff/160001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:895: 
On 2015/02/19 21:01:47, jvoung wrote:
> could put in an anonymous namespace

Done.

https://codereview.chromium.org/930733002/diff/160001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:897: class EmitHelper {
On 2015/02/19 21:01:47, jvoung wrote:
> Perhaps have bundle/bundling in the name somewhere?

Done.

https://codereview.chromium.org/930733002/diff/160001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:952: // Update bookkeeping when the bundle_unlock instlist is
processed.
On 2015/02/19 21:01:47, jvoung wrote:
> instlist -> instruction

Done.

https://codereview.chromium.org/930733002/diff/160001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:1032: 
On 2015/02/19 21:01:47, jvoung wrote:
> Leave a brief high level comment somewhere about the strategy (unconditional
two
> passes)?

Done.

https://codereview.chromium.org/930733002/diff/160001/src/assembler.h
File src/assembler.h (right):

https://codereview.chromium.org/930733002/diff/160001/src/assembler.h#newcode210
src/assembler.h:210: virtual void padWithNop(intptr_t Padding) = 0;
On 2015/02/19 21:01:47, jvoung wrote:
> Maybe put this padWithNop along with the alignFunction method?

Done.

https://codereview.chromium.org/930733002/diff/160001/src/assembler.h#newcode219
src/assembler.h:219: bool Preliminary;
On 2015/02/19 21:01:47, jvoung wrote:
> Document what Preliminary does

Done.

[jvoung (off chromium), 2015-02-20 01:50:35]

lgtm

[Jim Stichnoth, 2015-02-20 07:32:26]

New patchsets have been uploaded after l-g-t-m from jvoung@chromium.org

[Jim Stichnoth, 2015-02-20 07:34:52]

Added a lit test as promised.

[Karl, 2015-02-20 15:56:41]

lgtm

[Jim Stichnoth, 2015-02-20 17:20:21]

Committed patchset #11 (id:200001) manually as
9f42d8ca95d6ed94b6334e652181f82d2edcaa05 (presubmit successful).