bpf_dsl: support arbitrary (arg & mask) == val expressions

bpf_dsl: support arbitrary (arg & mask) == val expressions

Rework the seccomp_bpf compiler internals to work in terms of a single
general masked-equality condition instead of the variety of limited
condition operators previously supported.  All of the peephole
optimizations previously applied continue to be supported so similar
instructions should be emitted, but the handling of upper/lower words
is more cleanly structured now.

The old sandbox->Cond() interface continues to be supported for now so
that the old seccomp_bpf_unittests continue to give us assurances that
the new code generator is still correct.  Meanwhile, we provide a new
lower-level sandbox->CondMaskedEqual() method that bpf_dsl can now use.

BUG=408845
R=jln@chromium.org

Committed: https://chromium.googlesource.com/chromium/src/+/2761abc6db37817c1d8df352903d3748bc3048cc

[mdempsky, 2014-09-02 23:28:12]

mdempsky@chromium.org changed reviewers:
+ jln@chromium.org

[mdempsky, 2014-09-02 23:28:13]

I've skipped implementing most of verifier.cc for OP_MASKED_EQUAL since I'm
instead testing the new function via bpf_dsl_unittest.cc instead of
sandbox_bpf_unittest.cc, but I could do the latter too if you like.  (I was
going to put that off until the followup CL to remove the redundancies.)

[mdempsky, 2014-09-03 15:55:06]

On 2014/09/02 23:28:13, mdempsky wrote:
> I've skipped implementing most of verifier.cc for OP_MASKED_EQUAL since I'm
> instead testing the new function via bpf_dsl_unittest.cc instead of
> sandbox_bpf_unittest.cc, but I could do the latter too if you like.  (I was
> going to put that off until the followup CL to remove the redundancies.)

Actually hold off a second on reviewing this if you haven't already.

After sending this out for review I started worked on the followup CL, and
realized it's a bit simpler than I originally expected, and doing them together
means less churn back and forth.

[jln (very slow on Chromium), 2014-09-03 16:09:48]

On 2014/09/03 15:55:06, mdempsky wrote:
> On 2014/09/02 23:28:13, mdempsky wrote:
> > I've skipped implementing most of verifier.cc for OP_MASKED_EQUAL since I'm
> > instead testing the new function via bpf_dsl_unittest.cc instead of
> > sandbox_bpf_unittest.cc, but I could do the latter too if you like.  (I was
> > going to put that off until the followup CL to remove the redundancies.)
> 
> Actually hold off a second on reviewing this if you haven't already.
> 
> After sending this out for review I started worked on the followup CL, and
> realized it's a bit simpler than I originally expected, and doing them
together
> means less churn back and forth.

Ok, holding off then. Please, ping me!

[mdempsky, 2014-09-03 19:25:56]

On 2014/09/03 16:09:48, jln wrote:
> Ok, holding off then. Please, ping me!

Okay, I think it's ready for review now.  I suggest looking at the changes to
seccomp-bpf first, and then the changes to bpf_dsl should be pretty straight
forward.

[jln (very slow on Chromium), 2014-09-04 02:08:36]

PS#5 looks pretty good but I'll take a quick look at the newer patchsets as
well.

As mentioned in person, I would also like to have some basic testing of the new
functionality within seccomp_bpf_unittests.cc and not only at the higher layer.

https://chromiumcodereview.appspot.com/530133003/diff/80001/sandbox/linux/sec...
File sandbox/linux/seccomp-bpf/sandbox_bpf.cc (right):

https://chromiumcodereview.appspot.com/530133003/diff/80001/sandbox/linux/sec...
sandbox/linux/seccomp-bpf/sandbox_bpf.cc:920: // On 32-bit platforms, the upper
32-bits should always be 0:
I think it would be redundant with your previous check, but I wonder if you
could improve readability by asserting that cond.value_ also has these bits set
to zero).

https://chromiumcodereview.appspot.com/530133003/diff/80001/sandbox/linux/sec...
sandbox/linux/seccomp-bpf/sandbox_bpf.cc:969: return passed;
Shouldn't you assert that value == 0 here again? The fact that this check lives
higher in the call stacks makes reading this scary.

https://chromiumcodereview.appspot.com/530133003/diff/80001/sandbox/linux/sec...
File sandbox/linux/seccomp-bpf/verifier.cc (right):

https://chromiumcodereview.appspot.com/530133003/diff/80001/sandbox/linux/sec...
sandbox/linux/seccomp-bpf/verifier.cc:94: uint64_t ignored_bits = ~code.mask();
Maybe it would add a little coverage to:

1. Doing the same with "some_ignored_bits = ignored_bits & 0x55AA55AA";

2. Below, to detect that changing bits in the mask is detected as inequality:
"some_considered_bits = code.mask() & 0x055AA55AA"

Either instead or in addition to what you're already doing?

https://chromiumcodereview.appspot.com/530133003/diff/80001/sandbox/linux/sec...
sandbox/linux/seccomp-bpf/verifier.cc:131: // validate the upper 32-bits.  Here
we test that validation.
Nit: there is an extra space in front of "Here".

[mdempsky, 2014-09-04 17:26:49]

https://codereview.chromium.org/530133003/diff/80001/sandbox/linux/seccomp-bp...
File sandbox/linux/seccomp-bpf/sandbox_bpf.cc (right):

https://codereview.chromium.org/530133003/diff/80001/sandbox/linux/seccomp-bp...
sandbox/linux/seccomp-bpf/sandbox_bpf.cc:920: // On 32-bit platforms, the upper
32-bits should always be 0:
On 2014/09/04 02:08:36, jln wrote:
> I think it would be redundant with your previous check, but I wonder if you
> could improve readability by asserting that cond.value_ also has these bits
set
> to zero).

Yeah, it should be redundant, but I went ahead and extended the check for mask_
to also check value_ anyway.  (This check is now in CondExpression() though,
alongside the other sanity checks.)

https://codereview.chromium.org/530133003/diff/80001/sandbox/linux/seccomp-bp...
sandbox/linux/seccomp-bpf/sandbox_bpf.cc:969: return passed;
On 2014/09/04 02:08:35, jln wrote:
> Shouldn't you assert that value == 0 here again? The fact that this check
lives
> higher in the call stacks makes reading this scary.

Fair enough, done.

https://codereview.chromium.org/530133003/diff/80001/sandbox/linux/seccomp-bp...
File sandbox/linux/seccomp-bpf/verifier.cc (right):

https://codereview.chromium.org/530133003/diff/80001/sandbox/linux/seccomp-bp...
sandbox/linux/seccomp-bpf/verifier.cc:94: uint64_t ignored_bits = ~code.mask();
On 2014/09/04 02:08:36, jln wrote:
> Maybe it would add a little coverage to:
> 
> 1. Doing the same with "some_ignored_bits = ignored_bits & 0x55AA55AA";
> 
> 2. Below, to detect that changing bits in the mask is detected as inequality:
> "some_considered_bits = code.mask() & 0x055AA55AA"
> 
> Either instead or in addition to what you're already doing?

The unfortunate thing is that this runs recursively, and adding too many extra
cases quickly causes an exponential explosion of test cases and starts causing
timeouts. :-(

In lieu of adding the extra test cases you suggested, I've added a TODO to note
that we should rework how this is implemented to avoid explosions.

https://codereview.chromium.org/530133003/diff/80001/sandbox/linux/seccomp-bp...
sandbox/linux/seccomp-bpf/verifier.cc:131: // validate the upper 32-bits.  Here
we test that validation.
On 2014/09/04 02:08:36, jln wrote:
> Nit: there is an extra space in front of "Here".

Done. (I generally use two spaces between sentences out of habit, but prevailing
style in the seccomp-bpf directory seems to be one, so I'll be consistent here.)

[mdempsky, 2014-09-04 17:39:20]

On 2014/09/04 02:08:36, jln wrote:
> As mentioned in person, I would also like to have some basic testing of the
new
> functionality within seccomp_bpf_unittests.cc and not only at the higher
layer.

Oops, haven't done this yet.  Guess I'll work on that today.

[mdempsky, 2014-09-04 20:50:55]

PTAL!

On 2014/09/04 02:08:36, jln wrote:
> As mentioned in person, I would also like to have some basic testing of the
new
> functionality within seccomp_bpf_unittests.cc and not only at the higher
layer.

Done.

[jln (very slow on Chromium), 2014-09-04 21:45:06]

lgtm

I never quite know what to do about the TP_32BIT / TP_64BIT issue.

In the majority of cases, we want to do TP_64BIT. On 32 bits,
counter-intuitively, I think we always want to do TP_64BITS.

https://chromiumcodereview.appspot.com/530133003/diff/140001/sandbox/linux/se...
File sandbox/linux/seccomp-bpf/sandbox_bpf.cc (right):

https://chromiumcodereview.appspot.com/530133003/diff/140001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/sandbox_bpf.cc:1077: // convert value==0 here.
Should this comment be below (inside the switch) ?

https://chromiumcodereview.appspot.com/530133003/diff/160001/sandbox/linux/se...
File sandbox/linux/seccomp-bpf/sandbox_bpf.cc (right):

https://chromiumcodereview.appspot.com/530133003/diff/160001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/sandbox_bpf.cc:887: // because some SandboxBPF unit
tests exercise it.
TP_64BIT is actually the right default most of the time. It's the only one that
says "match exactly this value".

TP_32BIT is something that often worries me.

[mdempsky, 2014-09-04 21:53:03]

The CQ bit was checked by mdempsky@chromium.org

[mdempsky, 2014-09-04 21:53:52]

The CQ bit was unchecked by mdempsky@chromium.org

[mdempsky, 2014-09-04 21:59:43]

Committed patchset #9 (id:160001) manually as 2761abc (presubmit successful).

[commit-bot: I haz the power, 2014-09-10 03:33:00]

Patchset 9 (id:??) landed as
https://crrev.com/2761abc6db37817c1d8df352903d3748bc3048cc
Cr-Commit-Position: refs/heads/master@{#293347}