commit 7a21ffee7cba39e3f8fa69c72bcf9d48691e46b1
author Luis Hector Chavez <lhchavez@google.com> Wed Dec 05 16:54:30 2018 -0800
committer Luis Hector Chavez <lhchavez@google.com> Mon Mar 25 17:02:26 2019 -0700
tree c008a2e83c4a644e4d33ec5de86a289e165c3335
parent 29c72343333ef5218d5ed3cdab2ab21e51458056

tools/compile_seccomp_policy: Add a new optimizing compiler

This change introduces a new optimizing compiler. Since this new
compiler uses a better intermediate representation, it is able to cut
down a lot of unnecessary unconditional jumps and some families of
unnecessary loads. This alone removes ~20% overhead compared to the
in-process Minijail compiler (with regards to the number of
comparisons/jumps, which correlates linearly with the in-kernel filter
evaluation time).

This compiler also has an optimizing mode that can produce a biased
Binary Search Tree (instead of a linear chain of comparisons), that can
save an additional ~10% overhead (number of comparisons/jumps)

This new compiler also understands a couple more language additions:

* The introduction of the '~' unary operator, which performs a bitwise
  complement of the constant that follows it. This will be backported
  into the in-process compiler.
* The relaxation of the '|' binary operator while parsing. Spaces can
  now be added around this operator.
* The introduction of metadata attributes. For now, only the 'frequency'
  attribute is supported, and is used to inform the compiler about the
  costs of each individual syscall. Support for ignoring this will be
  added into the in-process compiler.

Bug: chromium:856315
Test: ./tools/compiler_unittest.py
Test: ./tools/compile_seccomp_policy.py --optimization-strategy=bst \
      test/seccomp.policy test/seccomp.optimized.bpf
Test: ./tools/compile_seccomp_policy.py --optimization-strategy=linear \
      test/seccomp.policy test/seccomp.optimized.bpf
Test: minijail0 --seccomp-bpf-binary=test/seccomp.optimized.bpf \
      ./test_program

Change-Id: I03909c382aa2136a6db3b2e1a418f081396f535b