Re: [RFC PATCH bpf-next 04/14] bpf: add support for an extended JA instruction

[David Faust <david.faust@oracle.com>]

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@isovalent.com>
>>> ---
>>>  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 {
>>