tree f760fce3adbf0afc846a41982ea243577c631047
parent 1c93783b744b63906acb875abde3b31023c6ec1d
author Luis Hector Chavez <lhchavez@google.com> 1532238356 -0700
committer Luis Hector Chavez <lhchavez@google.com> 1532496709 +0000

syscall_filter: Add a small operand optimization

Since all <, <=, >, >= operands are unsigned, when the immediate fits in
32-bits (which should be the vast majority of the time), we can omit one
of the comparison that would normally occur. So, for

 arg1 >= K

That would be roughly translated to

 if (hi(arg1) > hi(K)) jump NEXT;
 if (hi(arg1) == hi(K) && lo(arg1) >= lo(K)) jump NEXT;
 jump KILL;

If the first check (|hi(arg1) > hi(K)|) fails, we then evaluate the
whole second expression. If |hi(K) == 0|, then the only value of
|hi(arg1)| for which it would fail would be if |hi(arg1) == 0|, so we
don't need to evaluate |hi(arg1) == hi(K)| at all, since we know that
it's always going to be true. In other words,

 // given that |hi(K) == 0|,
 if (hi(arg1) > 0) jump NEXT;
 // if the code gets here, |hi(arg1) == 0|.
 if (lo(arg1) >= lo(K)) jump NEXT;
 jump KILL;

The case for > is identical, and </<= get translated into >/>= since
cBPF only supports the latter two operators, which concludes the
proof of correctness for this optimization.

This saves one opcode.

Bug: 111726641
Test: make tests
Test: echo 'read: arg1 <= 0xbadc0ffee0ddf00d' | \
      ./parse_seccomp_policy --dump - | \
      ./libseccomp/tools/scmp_bpf_disasm
Test: echo 'read: arg1 <= 0xff' | ./parse_seccomp_policy --dump - | \
      ./libseccomp/tools/scmp_bpf_disasm

Change-Id: Ia00362ce92ff5e858c7366dab013e2db88c09818