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).
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.