Visual walkthrough: choosing CPU 3
JIT investigation update
The kernel’s JIT selects native instructions, but Clang has already expanded the bit-count operation into BPF arithmetic. Fresh Clang 22.1.8 probes show 9 BPF operations for nonzero CTZ and 19 for population count; compiling the same C for Zen 5 gives TZCNT and POPCNT directly. The inspected reference JIT does not recognize and collapse those sequences.
The installed kernel ELF matches the running build ID and BTF. Actual Cake native JIT output is still unavailable: direct BPF inspection is permission-blocked. Full investigation, disassembly and implementation options.
Each bit represents a CPU. A 1 means that CPU survived Cake’s eligibility and preference checks. In this example, CPUs 3, 5 and 7 remain.
CPU number 7 6 5 4 3 2 1 0
Candidate mask 1 0 1 0 1 0 0 0
↑ └───┘
CPU 3 three trailing zeros
Result: trailing-zero count = 3 → try to claim CPU 3
Scheduling pathWakeup / enqueue / pool-work search
↓
Find idle CPUs allowed for this task and relevant LLC
↓
Prefer capacity, whole cores, unreserved seats, quieter CPUs and platform rank
↓
Count trailing zeros of the surviving bitmap
↓
Atomically try to claim that CPU
↓
Success: use it. Failure: remove its bit and try another candidate.
The source line in cake_pick_cold() is:
return (s32)__builtin_ctzll(
cake_rank_tier(cake_prefer_irq_clean(best, noisy)));
The builtin states the desired calculation. It does not force the BPF backend to emit an x86 TZCNT instruction.
Software route · captured BPF
- Copy the candidate mask.
- Negate the copy.
- AND with the original: isolate the lowest 1 bit.
- Load a special constant.
- Multiply the isolated bit by that constant.
- Shift right by 58: produce a table index.
- Load the lookup table’s address.
- Add the index to the address.
- Load the byte containing the CPU number.
10101000 → 00001000 → index → table[index] → 3
This multiplication-and-table method is a de Bruijn bit scan. The table maps each possible single-bit position to its bit number.Proposed inline hardware route
tzcnt result, mask
The CPU’s dedicated bit-count hardware directly returns the number of zeros below the lowest set bit.
10101000 → TZCNT → 3
No software multiplication, lookup-table address calculation or lookup-table memory read for the bit scan.
One native instruction for the core operation. Argument/result moves or surrounding spills can still add work. This is not an ordinary function call.Why we said 12, and the more precise count
The retained standalone CTZ benchmark has 12 x86 instructions: initialize the zero-input result, compare against zero, branch if zero, then the nine scan operations. Cake’s captured nonempty path omits those three zero-input instructions. Its nine BPF operations are not a verified count of today’s final native code.
The earlier generic claim that CTZ’s count included an exit jump was incorrect: this generated CTZ block has no exit jump. The benchmark’s dependency-feeding ADD is separate from the 12-instruction count.
Only the highlighted bit scan gets replaced. Cake still needs the same CPU eligibility checks, ranking policy, atomic claim and race retry. POPCNT has a similar opportunity, replacing software bit arithmetic when counting idle CPUs; LZCNT belongs to the separate proposed division-replacement experiment.
One instruction at which layer?
C expression → LLVM BPF → verifier → x86 JIT → CPU µopsNative code can still contain a long emulation sequence. One x86 instruction can contain multiple µops. Latency and reciprocal throughput are different measurements.
BPF expansion
The compiler emits shifts, masks and arithmetic. The JIT turns that sequence into native instructions.
Ordinary kfunc
A native function contains the operation, but calling it can add moves, spills, call and return costs.
JIT-inlined kfunc
The JIT substitutes the dedicated instruction. Surrounding argument/result moves and spills still need checking.
The host advertises ABM, BMI1, BMI2 and POPCNT. Its inspected vmlinux BTF does not expose the proposed bpf_clz64, bpf_ctz64, or bpf_popcnt64. This is a BPF access-path question, not missing CPU hardware.
Published Zen 5 register-to-register LZCNT and POPCNT measurements report one executed µop and one-cycle input-to-result latency. These are architecture reference measurements, separate from Cake’s full expression costs.