On 3/18/25 12:24, Anton Protopopov wrote:
> On 25/03/18 12:00PM, David Faust wrote:
>>
>>
>> On 3/18/25 07:33, Anton Protopopov wrote:
>>> Add support for a new version of JA instruction, a static branch JA. Such
>>> instructions may either jump to the specified offset or act as nops. To
>>> distinguish such instructions from normal JA the BPF_STATIC_BRANCH_JA flag
>>> should be set for the SRC register.
>>>
>>> By default on program load such instructions are jitted as a normal JA.
>>> However, if the BPF_STATIC_BRANCH_NOP flag is set in the SRC register,
>>> then the instruction is jitted to a NOP.
>>
>> [adding context from the cover letter:]
>>> 3) Patch 4 adds support for a new BPF instruction. It looks
>>> reasonable to use an extended BPF_JMP|BPF_JA instruction, and not
>>> may_goto. Reasons: a follow up will add support for
>>> BPF_JMP|BPF_JA|BPF_X (indirect jumps), which also utilizes INSN_SET maps (see [2]).
>>> Then another follow up will add support CALL|BPF_X, for which there's
>>> no corresponding magic instruction (to be discussed at the following
>>> LSF/MM/BPF).
>>
>> I don't understand the reasoning to extend JA rather than JCOND.
>>
>> Couldn't the followup for indirect jumps also use JCOND, with BPF_SRC_X
>> set to distinguish from the absolute jumps here?
>>
>> If the problem is that the indirect version will need both reigster
>> fields and JCOND is using SRC to encode the operation (0 for may_goto),
>> aren't you going to have exactly the same problem with BPF_JA|BPF_X and
>> the BPF_STATIC_BRANCH flag? Or is the plan to stick the flag in another
>> different field of BPF_JA|BPF_X instruction...?
>>
>> It seems like the general problem here that there is a growing class of
>> statically-decided-post-compiler conditional jumps, but no more free
>> insn class bits to use. I suggest we try hard to encapsulate them as
>> much as possible under JCOND rather than (ab)using different fields of
>> different JMP insns to encode the 'maybe' versions on a case-by-case
>> basis.
>>
>> To put it another way, why not make BPF_JMP|BPF_JCOND its own "class"
>> of insn and encode all of these conditional pseudo-jumps under it?
>
> I agree that the "magic jump" (BPF_STATIC_BRANCH) is, maybe, better to go with
> BPF_JMP|BPF_JCOND, as it emphasizes that the instruction is a special one.
>
> However, for indirect jumps the BPF_JMP|BPF_JA|BPF_X looks more natural.
Ah, maybe I misunderstood the context; will these BPF_JMP|BPF_JA|BPF_X indirect
jumps exclusively be "real" or was the intent that they also have the "maybe"
variant (could be jitted to no-op)? I was thinking the latter.
For the always-real version I agree BPF_JA|BPF_X makes total sense.
If there is a "maybe" variant that could be jitted to no-op then that should
fall under JCOND.
>
>> As far as I am aware (I may be out of date), the only JCOND insn
>> currently is may_goto (src_reg == 0), and may_goto only uses the 16-bit
>> offset. That seems to leave a lot of room (and bits) to design a whole
>> sub-class of JMP|JCOND instructions in a backwards compatible way...
>>
>>>
>>> In order to generate BPF_STATIC_BRANCH_JA instructions using llvm two new
>>> instructions will be added:
>>>
>>> asm volatile goto ("nop_or_gotol %l[label]" :::: label);
>>>
>>> will generate the BPF_STATIC_BRANCH_JA|BPF_STATIC_BRANCH_NOP instuction and
>>>
>>> asm volatile goto ("gotol_or_nop %l[label]" :::: label);
>>>
>>> will generate a BPF_STATIC_BRANCH_JA instruction, without an extra bit set.
>>> The reason for adding two instructions is that both are required to implement
>>> static keys functionality for BPF, namely, to distinguish between likely and
>>> unlikely branches.
>>>
>>> The verifier logic is extended to check both possible paths: jump and nop.
>>>
>>> Signed-off-by: Anton Protopopov <aspsk@xxxxxxxxxxxxx>
>>> ---
>>> arch/x86/net/bpf_jit_comp.c | 19 +++++++++++++--
>>> include/uapi/linux/bpf.h | 10 ++++++++
>>> kernel/bpf/verifier.c | 43 +++++++++++++++++++++++++++-------
>>> tools/include/uapi/linux/bpf.h | 10 ++++++++
>>> 4 files changed, 71 insertions(+), 11 deletions(-)
>>>
>>> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
>>> index d3491cc0898b..5856ac1aab80 100644
>>> --- a/arch/x86/net/bpf_jit_comp.c
>>> +++ b/arch/x86/net/bpf_jit_comp.c
>>> @@ -1482,6 +1482,15 @@ static void emit_priv_frame_ptr(u8 **pprog, void __percpu *priv_frame_ptr)
>>> *pprog = prog;
>>> }
>>>
>>> +static bool is_static_ja_nop(const struct bpf_insn *insn)
>>> +{
>>> + u8 code = insn->code;
>>> +
>>> + return (code == (BPF_JMP | BPF_JA) || code == (BPF_JMP32 | BPF_JA)) &&
>>> + (insn->src_reg & BPF_STATIC_BRANCH_JA) &&
>>> + (insn->src_reg & BPF_STATIC_BRANCH_NOP);
>>> +}
>>> +
>>> #define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))
>>>
>>> #define __LOAD_TCC_PTR(off) \
>>> @@ -2519,9 +2528,15 @@ st: if (is_imm8(insn->off))
>>> }
>>> emit_nops(&prog, INSN_SZ_DIFF - 2);
>>> }
>>> - EMIT2(0xEB, jmp_offset);
>>> + if (is_static_ja_nop(insn))
>>> + emit_nops(&prog, 2);
>>> + else
>>> + EMIT2(0xEB, jmp_offset);
>>> } else if (is_simm32(jmp_offset)) {
>>> - EMIT1_off32(0xE9, jmp_offset);
>>> + if (is_static_ja_nop(insn))
>>> + emit_nops(&prog, 5);
>>> + else
>>> + EMIT1_off32(0xE9, jmp_offset);
>>> } else {
>>> pr_err("jmp gen bug %llx\n", jmp_offset);
>>> return -EFAULT;
>>> diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
>>> index b8e588ed6406..57e0fd636a27 100644
>>> --- a/include/uapi/linux/bpf.h
>>> +++ b/include/uapi/linux/bpf.h
>>> @@ -1462,6 +1462,16 @@ struct bpf_stack_build_id {
>>> };
>>> };
>>>
>>> +/* Flags for JA insn, passed in SRC_REG */
>>> +enum {
>>> + BPF_STATIC_BRANCH_JA = 1 << 0,
>>> + BPF_STATIC_BRANCH_NOP = 1 << 1,
>>> +};
>>> +
>>> +#define BPF_STATIC_BRANCH_MASK (BPF_STATIC_BRANCH_JA | \
>>> + BPF_STATIC_BRANCH_NOP)
>>> +
>>> +
>>> #define BPF_OBJ_NAME_LEN 16U
>>>
>>> union bpf_attr {
>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>> index 6554f7aea0d8..0860ef57d5af 100644
>>> --- a/kernel/bpf/verifier.c
>>> +++ b/kernel/bpf/verifier.c
>>> @@ -17374,14 +17374,24 @@ static int visit_insn(int t, struct bpf_verifier_env *env)
>>> else
>>> off = insn->imm;
>>>
>>> - /* unconditional jump with single edge */
>>> - ret = push_insn(t, t + off + 1, FALLTHROUGH, env);
>>> - if (ret)
>>> - return ret;
>>> + if (insn->src_reg & BPF_STATIC_BRANCH_JA) {
>>> + /* static branch - jump with two edges */
>>> + mark_prune_point(env, t);
>>>
>>> - mark_prune_point(env, t + off + 1);
>>> - mark_jmp_point(env, t + off + 1);
>>> + ret = push_insn(t, t + 1, FALLTHROUGH, env);
>>> + if (ret)
>>> + return ret;
>>> +
>>> + ret = push_insn(t, t + off + 1, BRANCH, env);
>>> + } else {
>>> + /* unconditional jump with single edge */
>>> + ret = push_insn(t, t + off + 1, FALLTHROUGH, env);
>>> + if (ret)
>>> + return ret;
>>>
>>> + mark_prune_point(env, t + off + 1);
>>> + mark_jmp_point(env, t + off + 1);
>>> + }
>>> return ret;
>>>
>>> default:
>>> @@ -19414,8 +19424,11 @@ static int do_check(struct bpf_verifier_env *env)
>>>
>>> mark_reg_scratched(env, BPF_REG_0);
>>> } else if (opcode == BPF_JA) {
>>> + struct bpf_verifier_state *other_branch;
>>> + u32 jmp_offset;
>>> +
>>> if (BPF_SRC(insn->code) != BPF_K ||
>>> - insn->src_reg != BPF_REG_0 ||
>>> + (insn->src_reg & ~BPF_STATIC_BRANCH_MASK) ||
>>> insn->dst_reg != BPF_REG_0 ||
>>> (class == BPF_JMP && insn->imm != 0) ||
>>> (class == BPF_JMP32 && insn->off != 0)) {
>>> @@ -19424,9 +19437,21 @@ static int do_check(struct bpf_verifier_env *env)
>>> }
>>>
>>> if (class == BPF_JMP)
>>> - env->insn_idx += insn->off + 1;
>>> + jmp_offset = insn->off + 1;
>>> else
>>> - env->insn_idx += insn->imm + 1;
>>> + jmp_offset = insn->imm + 1;
>>> +
>>> + /* Staic branch can either jump to +off or +0 */
>>> + if (insn->src_reg & BPF_STATIC_BRANCH_JA) {
>>> + other_branch = push_stack(env, env->insn_idx + jmp_offset,
>>> + env->insn_idx, false);
>>> + if (!other_branch)
>>> + return -EFAULT;
>>> +
>>> + jmp_offset = 1;
>>> + }
>>> +
>>> + env->insn_idx += jmp_offset;
>>> continue;
>>>
>>> } else if (opcode == BPF_EXIT) {
>>> diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
>>> index b8e588ed6406..57e0fd636a27 100644
>>> --- a/tools/include/uapi/linux/bpf.h
>>> +++ b/tools/include/uapi/linux/bpf.h
>>> @@ -1462,6 +1462,16 @@ struct bpf_stack_build_id {
>>> };
>>> };
>>>
>>> +/* Flags for JA insn, passed in SRC_REG */
>>> +enum {
>>> + BPF_STATIC_BRANCH_JA = 1 << 0,
>>> + BPF_STATIC_BRANCH_NOP = 1 << 1,
>>> +};
>>> +
>>> +#define BPF_STATIC_BRANCH_MASK (BPF_STATIC_BRANCH_JA | \
>>> + BPF_STATIC_BRANCH_NOP)
>>> +
>>> +
>>> #define BPF_OBJ_NAME_LEN 16U
>>>
>>> union bpf_attr {
>>
