| Message ID | 20250318143318.656785-5-aspsk@isovalent.com (mailing list archive) |
|---|---|
| State | RFC |
| Delegated to: | BPF |
| Headers | show |
| Series | instruction sets and static keys | expand |
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? 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 {
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. > 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 { >
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 { >>
On 25/03/18 12:30PM, David Faust wrote: > > > 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. Yes, those are real, no patching: goto rX (where rX is properly loaded from an instruction set). > > > >> 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 { > >> >
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 {
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. 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(-)