CodeGen: rewrite implementation [3/3]

CodeGen: rewrite implementation [3/3]

This is a complete rewrite of CodeGen from scratch, taking advantage
of the fact that a while back we changed PolicyCompiler to not require
modifying instructions after they're created.  In particular, we no
longer need topological sorting because the MakeInstruction call order
implicitly sorts instructions for us.  Additionally, we no longer need
to compute basic blocks even because they were only needed for
sorting.

It turns out that a simple greedy algorithm with basic memoization
suffices for flattening the instruction graph, and we only really need
to worry about inserting "jump" instructions when the targets are too
far away.  With just this, we're able to emit programs that are just
as efficient as the old CodeGen implementation did.

As a bonus, the new code generator is now fully deterministic because
it doesn't create any sets or maps using pointer values as keys.

BUG=414363
Committed: https://crrev.com/1fe9104fec2241de3cb547f0580ebb24edc13613
Cr-Commit-Position: refs/heads/master@{#304977}

[mdempsky, 2014-11-04 00:56:24]

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

[rickyz (no longer on Chrome), 2014-11-12 23:43:50]

lgtm

Wow, that's one big cleanup :-) Would be interesting to see what the diff in
code size for some of our policies is with the change.

https://codereview.chromium.org/699633003/diff/100001/sandbox/linux/seccomp-b...
File sandbox/linux/seccomp-bpf/codegen.cc (right):

https://codereview.chromium.org/699633003/diff/100001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen.cc:23: out->assign(program_.rbegin() +
Offset(head), program_.rend());
Will head always end up being the most recently added instruction? Might be
worth removing the parameter later if so.

https://codereview.chromium.org/699633003/diff/100001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen.cc:51: if (Offset(jt) >= 255) {
Should this be 256?

https://codereview.chromium.org/699633003/diff/100001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen.cc:90: program_.push_back((sock_filter){code,
jt, jf, k});
Might be good to CHECK_LE(program_.size(), BPF_MAXINSNS) here.

https://codereview.chromium.org/699633003/diff/100001/sandbox/linux/seccomp-b...
File sandbox/linux/seccomp-bpf/codegen_unittest.cc (right):

https://codereview.chromium.org/699633003/diff/100001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen_unittest.cc:208: // 2: JUMP to $3             
         (insn2)
Update this comment now that we got rid of the jump

https://codereview.chromium.org/699633003/diff/100001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen_unittest.cc:339: }  // namespace
Can you add a test that calls MakeInstruction with jt/jf > 255?

[mdempsky, 2014-11-18 01:07:30]

https://codereview.chromium.org/699633003/diff/100001/sandbox/linux/seccomp-b...
File sandbox/linux/seccomp-bpf/codegen.cc (right):

https://codereview.chromium.org/699633003/diff/100001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen.cc:23: out->assign(program_.rbegin() +
Offset(head), program_.rend());
On 2014/11/12 23:43:50, rickyz wrote:
> Will head always end up being the most recently added instruction? Might be
> worth removing the parameter later if so.

In practice it will be, but I feel a bit safer making it explicit, and it makes
describing the API a bit simpler too IMO.

https://codereview.chromium.org/699633003/diff/100001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen.cc:51: if (Offset(jt) >= 255) {
On 2014/11/12 23:43:50, rickyz wrote:
> Should this be 256?

Sort of.  It was 255 so I wouldn't need to worry about rechecking it if we need
to add a Jump for jf.

I've changed it to use a loop and added an explanatory comment.  Also added a
kBranchRange constant to eliminate the magic 255/256.

https://codereview.chromium.org/699633003/diff/100001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen.cc:90: program_.push_back((sock_filter){code,
jt, jf, k});
On 2014/11/12 23:43:50, rickyz wrote:
> Might be good to CHECK_LE(program_.size(), BPF_MAXINSNS) here.

Done.  (I added a CHECK_LT before the push_back.)

https://codereview.chromium.org/699633003/diff/100001/sandbox/linux/seccomp-b...
File sandbox/linux/seccomp-bpf/codegen_unittest.cc (right):

https://codereview.chromium.org/699633003/diff/100001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen_unittest.cc:208: // 2: JUMP to $3             
         (insn2)
On 2014/11/12 23:43:50, rickyz wrote:
> Update this comment now that we got rid of the jump

So my reasoning was this is the description of the program we logically want to
encode, and then below is how we actually encoded it using the current CodeGen
API.  The current API uses implicit JUMPs from simply reusing a Node (hence the
"Implicit JUMP" comment below).

If you prefer, I can remove the JUMP and renumber the insn variables?

https://codereview.chromium.org/699633003/diff/100001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen_unittest.cc:339: }  // namespace
On 2014/11/12 23:43:50, rickyz wrote:
> Can you add a test that calls MakeInstruction with jt/jf > 255?

Done.

[mdempsky, 2014-11-18 01:17:35]

On 2014/11/12 23:43:50, rickyz wrote:
> Wow, that's one big cleanup :-) Would be interesting to see what the diff in
> code size for some of our policies is with the change.

Yeah, I spent a while looking at this.  The policies remain around the same
size, within a couple instructions most of the time.

Actually the old CodeGen randomly generated much *worse* programs, because ASLR
caused the pointer sorting in the toposort step to occasionally pick really
*bad* block orders, which could then cause a lot of JUMP instructions to be
needed between blocks.

[jln (very slow on Chromium), 2014-11-19 00:32:05]

This looks like a pretty spectacular cleanup, thanks!

I'm pretty sure this is ok as-is, but I'm sick today and I would like to do
another pass with a working brain.

In general: I think it would be nice to add some more comments about the design
& strategy. Perhaps even explain what optimization were removed in the commit
message and that you manually checked they weren't useful (even if they were, I
think this is a great step towards a better compiler anyways).

Maybe even a small example about how CodeGen is intended to be used?

All up to you!

https://chromiumcodereview.appspot.com/699633003/diff/120001/sandbox/linux/se...
File sandbox/linux/seccomp-bpf/codegen.cc (right):

https://chromiumcodereview.appspot.com/699633003/diff/120001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.cc:16: const size_t kBranchRange =
std::numeric_limits<uint8_t>::max();
Make me happy that this is now allowed :)

https://chromiumcodereview.appspot.com/699633003/diff/120001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.cc:26: void CodeGen::Compile(CodeGen::Node
head, Program* out) {
DCHECK(out) ?

https://chromiumcodereview.appspot.com/699633003/diff/120001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.cc:34: if (BPF_CLASS(code) == BPF_JMP) {
Do you want to move this if-else block into another private function?

It will be slightly more readable if you can simply "return" rather than having
a nested code path.

Also this would give a good opportunity to document the rationale for these
checks.

https://chromiumcodereview.appspot.com/699633003/diff/120001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.cc:35: CHECK_NE(BPF_JA, BPF_OP(code));
Add comment?

https://chromiumcodereview.appspot.com/699633003/diff/120001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.cc:47: // Lookup the cache entry, inserting a
new one if necessary.
That comment isn't very useful. Could you explain the strategy of using this
cache instead, perhaps providing example of what it saves or when it's not
enough to optimize?

https://chromiumcodereview.appspot.com/699633003/diff/120001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.cc:48: auto it =
cache_.insert(std::make_pair(CacheKey(code, k, jt, jf), kNullNode));
It's a little weird to call this "it" even though it's not an iterator. Wouldn't
it be more readable to swap "res" and "it" here?

https://chromiumcodereview.appspot.com/699633003/diff/120001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.cc:52: if (miss) {
How about if (!miss) return res; to simplify nesting?

https://chromiumcodereview.appspot.com/699633003/diff/120001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.cc:96: program_.push_back((sock_filter){code,
jt, jf, k});
This qualifies as a compound literal no? Is this proper C++11 syntax?

I know that sock_filter{code, jt, jf, k} (no parens) is valid.

https://chromiumcodereview.appspot.com/699633003/diff/120001/sandbox/linux/se...
File sandbox/linux/seccomp-bpf/codegen.h (right):

https://chromiumcodereview.appspot.com/699633003/diff/120001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.h:99: // Append adds a new instruction to the
end of |program_|.
I would further clarify what "Appends" mean: since here it sort of means prepend
:)

[mdempsky, 2014-11-19 03:05:23]

PTAL!

> This looks like a pretty spectacular cleanup, thanks!

:-)

> In general: I think it would be nice to add some more comments about the
design
> & strategy.

Done: please see top of codegen.cc.

> Perhaps even explain what optimization were removed in the commit
> message and that you manually checked they weren't useful (even if they were,
I
> think this is a great step towards a better compiler anyways).

Clarified a bit in the commit message and codegen.cc documentation.

> Maybe even a small example about how CodeGen is intended to be used?

I think the existing docs cover that, but I can elaborate more if you think
appropriate.

https://codereview.chromium.org/699633003/diff/120001/sandbox/linux/seccomp-b...
File sandbox/linux/seccomp-bpf/codegen.cc (right):

https://codereview.chromium.org/699633003/diff/120001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen.cc:26: void CodeGen::Compile(CodeGen::Node
head, Program* out) {
On 2014/11/19 00:32:04, jln wrote:
> DCHECK(out) ?

Done.

https://codereview.chromium.org/699633003/diff/120001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen.cc:34: if (BPF_CLASS(code) == BPF_JMP) {
On 2014/11/19 00:32:04, jln wrote:
> Do you want to move this if-else block into another private function?
> 
> It will be slightly more readable if you can simply "return" rather than
having
> a nested code path.
> 
> Also this would give a good opportunity to document the rationale for these
> checks.

Done.

https://codereview.chromium.org/699633003/diff/120001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen.cc:35: CHECK_NE(BPF_JA, BPF_OP(code));
On 2014/11/19 00:32:04, jln wrote:
> Add comment?

Done.

https://codereview.chromium.org/699633003/diff/120001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen.cc:47: // Lookup the cache entry, inserting a
new one if necessary.
On 2014/11/19 00:32:04, jln wrote:
> That comment isn't very useful. Could you explain the strategy of using this
> cache instead, perhaps providing example of what it saves or when it's not
> enough to optimize?

Done.

https://codereview.chromium.org/699633003/diff/120001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen.cc:48: auto it =
cache_.insert(std::make_pair(CacheKey(code, k, jt, jf), kNullNode));
On 2014/11/19 00:32:04, jln wrote:
> It's a little weird to call this "it" even though it's not an iterator.
Wouldn't
> it be more readable to swap "res" and "it" here?

Done.

https://codereview.chromium.org/699633003/diff/120001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen.cc:52: if (miss) {
On 2014/11/19 00:32:04, jln wrote:
> How about if (!miss) return res; to simplify nesting?

Done by factoring out AppendInstruction().

(I had originally kept the extra nesting because I wanted to emphasize that the
extra code only happens in the "miss" case, and that the return statement was
otherwise the same either way.  Otherwise it's possible the miss-handling code
could been 'optimized' from "res = xxx; return res;" to "return xxx;", which
would be correct on the first call, but on subsequent calls the cache entry
would be wrong.)

https://codereview.chromium.org/699633003/diff/120001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen.cc:96: program_.push_back((sock_filter){code,
jt, jf, k});
On 2014/11/19 00:32:04, jln wrote:
> This qualifies as a compound literal no? Is this proper C++11 syntax?

Nope, it's GNU C-ism I copied from the old implementation (see lines 567--568).

> I know that sock_filter{code, jt, jf, k} (no parens) is valid.

Ah, much better; done.

https://codereview.chromium.org/699633003/diff/120001/sandbox/linux/seccomp-b...
File sandbox/linux/seccomp-bpf/codegen.h (right):

https://codereview.chromium.org/699633003/diff/120001/sandbox/linux/seccomp-b...
sandbox/linux/seccomp-bpf/codegen.h:99: // Append adds a new instruction to the
end of |program_|.
On 2014/11/19 00:32:05, jln wrote:
> I would further clarify what "Appends" mean: since here it sort of means
prepend
> :)

Done.

[mdempsky, 2014-11-19 04:11:54]

I plan on investigating the WithinRange optimizations further in a followup CL,
but some quick experimentation reveals that reusing existing JAs would reduce
BaselinePolicy from 420 BPF instructions down to 368; i.e., a 12% reduction,
which really surprised me.

For comparison, over 101 runs, here's how many instructions old CodeGen emitted
for BaselinePolicy:

      1 412
     27 417
     19 418
      3 419
      2 420
      2 421
      5 422
      4 423
      3 424
     26 425
      2 426
      4 427
      2 428
      1 436

I.e., even at 420 instructions, new CodeGen compares well and even matches old
CodeGen's median. But at 368 instructions, the new code generator *way*
outperforms the old one, at least in the code size metric.

[jln (very slow on Chromium), 2014-11-20 02:00:03]

lgtm

This is really elegant, love it! :)

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

https://chromiumcodereview.appspot.com/699633003/diff/140001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.cc:67: // To avoid generating redundant code
sequences, we memoize the
nit: memorize

https://chromiumcodereview.appspot.com/699633003/diff/140001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.cc:71: if (res.second) {  // Newly inserted
memo entry
Nit: final dot

https://chromiumcodereview.appspot.com/699633003/diff/140001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.cc:77: CodeGen::Node
CodeGen::AppendInstruction(uint16_t code,
Shouldn't we document the fact that this slightly expands the BPF language by
allowing arbitrary jt for non-jump instructions?

https://chromiumcodereview.appspot.com/699633003/diff/140001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.cc:88: jt = WithinRange(jt, kBranchRange);
This looks a tiny bit odd, but no big deal.

Technically, this is a recursion that is guaranteed to converge to a fixed
point. It so happens that the fixed point will be found after 2 (or one and a
half) iterations.

I wonder if this would be clearer if expressed as such: for instance an infinite
loop that breaks on fixed point, but with a CHECK that the number of iterations
doesn't exceed 2.

I would very easily be convinced that this wouldn't make things clearer at all
though ;)

https://chromiumcodereview.appspot.com/699633003/diff/140001/sandbox/linux/se...
File sandbox/linux/seccomp-bpf/codegen.h (right):

https://chromiumcodereview.appspot.com/699633003/diff/140001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.h:96: Node WithinRange(Node next, size_t
range);
No big deal, but if you manage to come up with a name that makes it clearer that
this can add a Node, this could be helpful. (MakeWithingRange?)

Feel free to skip if you think that's clear.

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

https://chromiumcodereview.appspot.com/699633003/diff/140001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen_unittest.cc:347: 
Add a quick reference about jump offsets being 8 bits to explain the test maybe?

[mdempsky, 2014-11-20 02:53:22]

Responded to a couple of your points, but unfortunately most of them I don't
have good answers for, and they're all things that I wasn't 100% happy with
already. :-/

So I'm going to go ahead and CQ this, and I'll continue thinking about those
while I work on followup CLs.  Or if you have suggestions let me know!

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

https://chromiumcodereview.appspot.com/699633003/diff/140001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.cc:67: // To avoid generating redundant code
sequences, we memoize the
On 2014/11/20 02:00:03, jln wrote:
> nit: memorize

Nope, I meant memoize: http://en.wikipedia.org/wiki/Memoization

https://chromiumcodereview.appspot.com/699633003/diff/140001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.cc:71: if (res.second) {  // Newly inserted
memo entry
On 2014/11/20 02:00:03, jln wrote:
> Nit: final dot

Done.

https://chromiumcodereview.appspot.com/699633003/diff/140001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.cc:77: CodeGen::Node
CodeGen::AppendInstruction(uint16_t code,
On 2014/11/20 02:00:02, jln wrote:
> Shouldn't we document the fact that this slightly expands the BPF language by
> allowing arbitrary jt for non-jump instructions?

Hm, I'll think about it.  From the API's point of view, the user is just
constructing a DAG of instructions, and CodeGen then takes care of the nitty
details like how the VM actually proceeds from one instruction to the next.

https://chromiumcodereview.appspot.com/699633003/diff/140001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.cc:88: jt = WithinRange(jt, kBranchRange);
On 2014/11/20 02:00:02, jln wrote:
> Technically, this is a recursion that is guaranteed to converge to a fixed
> point. It so happens that the fixed point will be found after 2 (or one and a
> half) iterations.

Yep.

> I wonder if this would be clearer if expressed as such: for instance an
infinite
> loop that breaks on fixed point, but with a CHECK that the number of
iterations
> doesn't exceed 2.
> 
> I would very easily be convinced that this wouldn't make things clearer at all
> though ;)

Hm, I tried a few variations, and I didn't find anything that I felt really made
it any clearer without disproportionately increasing code complexity.  I think
as-is is still my favorite, but my runner's up would be:

  // We're guaranteed to reach a fixpoint within two iterations.
  for (int i = 0; i < 2; ++i) {
    jt = WithinRange(jt, kBranchRange);
    jf = WithinRange(jf, kBranchRange);
  }

  // Make sure |jt| stays within kBranchRange even if we need to add
  // a jump for |jf|.
  jt = WithinRange(jt, kBranchRange - 1);
  jf = WithinRange(jf, kBranchRange);

(For what it's worth, old CodeGen basically used the last technique.)

Lastly, in Append() I still CHECK that the offsets are within kBranchRange, so
if we don't reach a fixed point, it'll CHECK-fail either way.

https://chromiumcodereview.appspot.com/699633003/diff/140001/sandbox/linux/se...
File sandbox/linux/seccomp-bpf/codegen.h (right):

https://chromiumcodereview.appspot.com/699633003/diff/140001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen.h:96: Node WithinRange(Node next, size_t
range);
On 2014/11/20 02:00:03, jln wrote:
> No big deal, but if you manage to come up with a name that makes it clearer
that
> this can add a Node, this could be helpful. (MakeWithingRange?)
> 
> Feel free to skip if you think that's clear.

Yeah, I'm not super happy with the name.

I was largely thinking about "EnsureWithinRange", but I felt like that might
imply it fails if the Node is out of range.  And conversely I feel like
MakeWithinRange implies it'll duplicate it if it's already within range... hence
punting on FooWithinRange and just shortening it to WithinRange. :-/

I suppose "CopyWithinRangeIfNeeded" would do, but it just felt wordy for a
private helper function.

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

https://chromiumcodereview.appspot.com/699633003/diff/140001/sandbox/linux/se...
sandbox/linux/seccomp-bpf/codegen_unittest.cc:347: 
On 2014/11/20 02:00:03, jln wrote:
> Add a quick reference about jump offsets being 8 bits to explain the test
maybe?

Done.

[mdempsky, 2014-11-20 02:53:33]

The CQ bit was checked by mdempsky@chromium.org

[commit-bot: I haz the power, 2014-11-20 02:54:31]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/699633003/160001

[commit-bot: I haz the power, 2014-11-20 04:53:03]

Committed patchset #9 (id:160001)

[commit-bot: I haz the power, 2014-11-20 04:53:39]

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