Test that an integer is different from two other integers in eBPF without branch opcodes

Question

I'm writing an eBPF kprobe that checks task UIDs, namely that the only permitted UID changes between calls to execve are those allowed by setuid(), seteuid() and setreuid() calls.

Since the probe checks all tasks, it uses an unrolled loop that iterates starting from init_task, and it has to use at most 1024 or 8192 branches, depending on kernel version.

My question is, how to implement a check that returns nonzero if there is an illegal change, defined by:

(new_ruid != old_euid && new_ruid != old_ruid) ||
(new_euid != old_euid && new_euid != old_ruid && new_euid != old_suid)

but without using branches (clang uses jumps to short-circuit the check if any of the expressions between && evaluates to true).

Answer 1

You should be able to do this using bitwise OR, XOR, shifts and integer multiplication. I assume your variables are all __s32 or __u32, cast them to __u64 before proceeding to avoid problems (otherwise cast every operand of the multiplications below to __u64).

Clearly a != b can become a ^ b. The && is a bit trickier, but can be translated into a multiplication (where if any operand is 0 the result is 0). The first part of your condition then becomes:

// (new_ruid != old_euid && new_ruid != old_ruid)
__u64 x = (new_ruid ^ old_euid) * (new_ruid ^ old_euid);

However for the second part we have an overflow problem since there are 3 conditions. You can avoid it by "compressing" the result of the first two into the lower 32 bits, since you don't really care about the multiplication, just about its "truthiness":

// (new_euid != old_euid && new_euid != old_ruid && new_euid != old_suid)

__u64 y = (new_euid ^ old_euid) * (new_euid ^ old_ruid);
y = (y >> 32) | (y & 0xffffffff);
y *= (new_euid ^ old_suid);

And finally just OR the two parts for the result. You can also "compress" again to the lower 32 bits if you want a __u32:

__u64 res = x | y;
// or
__u64 tmp = x | y;
__u32 res = (tmp >> 32) | (tmp & 0xffffffff);

All of the above combined compiles without any branch for me regardless of optimization level.

Answer 2

Following the other answer, there are better reduction functions, than folding the top bits over low bits.

First starting with the original problem, the generated code is actually not that bad.

bool func0(uint64_t new_ruid,uint64_t old_euid, uint64_t old_ruid,
           uint64_t new_euid, uint64_t old_suid) {
   return
      (new_ruid != old_euid && new_ruid != old_ruid) ||
      (new_euid != old_euid && new_euid != old_ruid && new_euid != old_suid);
}

_Z5func0mmmmm:                          # @_Z5func0mmmmm
    cmpq    %rsi, %rdi
    je      .LBB0_2
    movb    $1, %al
    cmpq    %rdx, %rdi
    je      .LBB0_2
    retq
.LBB0_2:
    cmpq    %rsi, %rcx
    setne   %al
    cmpq    %rdx, %rcx
    setne   %dl
    andb    %al, %dl
    cmpq    %r8, %rcx
    setne   %al
    andb    %dl, %al
    retq

Only the first portion contains conditional branches, while the latter part is fully unrolled to set_conditionals.

Thus we have about three candidates for reduction:

uint32_t reduct1(uint64_t a, uint64_t b) {
    a ^= b;
    return (a >> 32) | (a & 0xffffffff);
}

    movq    %rdi, %rax
    xorq    %rsi, %rax
    movq    %rax, %rcx
    shrq    $32, %rcx
    orl     %ecx, %eax


uint8_t reduct2(uint64_t a, uint64_t b) {
   return __builtin_popcountl(a ^ b);
}
    xorq    %rsi, %rdi
    popcntq %rdi, %rax


uint8_t reduct3(uint64_t a, uint64_t b) {
    return a != b ? 1u : 0u;
}
    cmpq    %rsi, %rdi
    setne   %al

The first variant is quite bloated compared to the two other version, in addition of it suffering from the problem of the multiplicative overflow. The popcount variant returns values in range of 1-64 in case the input variables differ, meaning that the multiplicative overflow is solved.

However, the third variant is strength reduced to logical-and, which is way faster than multiplication -- and furthermore it allows a non-destructive comparison of the operands, which probably beats the popcount version (which OTOH has more opportunities for instruction level parallelism).

bool func( uint64_t new_ruid, uint64_t old_euid, uint64_t old_ruid,
uint64_t new_euid, uint64_t old_suid) {
    auto a = reduct3(new_ruid, old_euid);
    auto b = reduct3(new_ruid, old_ruid);
    auto c = reduct3(new_euid, old_euid);
    auto d = reduct3(new_euid, old_ruid);
    auto e = reduct3(new_euid, old_suid);
   return (a * b) || (c * d * e);
}
    cmpq    %rsi, %rdi
    setne   %r9b
    cmpq    %rdx, %rdi
    setne   %dil
    cmpq    %rsi, %rcx
    setne   %sil
    cmpq    %rdx, %rcx
    setne   %al
    cmpq    %r8, %rcx
    setne   %cl
    andb    %r9b, %dil
    andb    %sil, %al
    andb    %cl, %al
    orb     %dil, %al

The problem can be solved also in SSE2 domain, with careful selection of parameters:

   XMM0 = new_ruid | new_euid
   XMM1 = old_euid | old_euid
   XMM2 = old_ruid | old_ruid
   XMM3 = old_ruid | old_suid <- we compare new_ruid twice to same value

   XMM1 = _mm_cmpeq_epi64(XMM1, XMM0);
   XMM2 = _mm_cmpeq_epi64(XMM2, XMM0);
   XMM3 = _mm_cmpeq_epi64(XMM3, XMM0);
   XMM1 = _mm_or_si128(XMM1, XMM2);
   XMM1 = _mm_or_si128(XMM1, XMM3);

On SSE2 there's only ==, not !=, so we need to apply De-Morgan a few times, then combine left and right part, and movemask or movq the result out. (IDK if it's allowed to use SSE2 on Linux kernel, so this part may not fit the requirement.)