Currently no site describes a lock, so every lock that a throw finds held is kept in a hidden slot. Its address is stored before the call that takes the lock, and cleared before the unlock. A lock does not move, so a site can describe it: - The lock of a global variable, or of the only element of any other array map that the program refers to, is at an address known at verification time. Its resource class carries the address. The site entry is marked BPF_FRAME_ENT_FIXED and reads nothing from the frame. This does not apply to an inner map: the map that stands for it during verification has no values. - Any other lock is found through a pointer to the map value or allocated object that contains it. Such a pointer has the same id as the lock. The acquisition records the offset of the lock in the object, and the site gives a stack slot or a register that holds such a pointer, with the difference as its adjustment. A lock whose offset does not fit in an adjustment is not found through a pointer. A lock at a fixed address then costs the program nothing when every visit to a site finds it held. Any other lock costs nothing when, in addition, the frame has a pointer to the containing object in the same location on every visit. A lock that some visits to a site find held and others do not still takes a hidden slot. Signed-off-by: Kumar Kartikeya Dwivedi --- include/linux/bpf.h | 4 ++ include/linux/bpf_verifier.h | 2 + kernel/bpf/frame_desc.c | 77 +++++++++++++++++++++++++++++------- kernel/bpf/unwind.c | 2 + 4 files changed, 70 insertions(+), 15 deletions(-) diff --git a/include/linux/bpf.h b/include/linux/bpf.h index b157863cb952..cbb0d7a61f98 100644 --- a/include/linux/bpf.h +++ b/include/linux/bpf.h @@ -1860,6 +1860,7 @@ struct bpf_resource { union { void (*dtor)(void *); struct btf_struct_meta *meta; + void *addr; /* a lock at a fixed address, in the only element of an array map */ }; }; @@ -1880,6 +1881,8 @@ struct bpf_resource { * bpf_arch_throw_entry(); * - with BPF_FRAME_ENT_OBJ the resource itself, an iterator or saved IRQ * flags the frame has on its stack whenever it is at the site; + * - with BPF_FRAME_ENT_FIXED no location: a lock at the address its class + * gives, which the frame holds whenever it is at the site; * - with BPF_FRAME_ENT_COUNTER a hidden slot that holds a count of sections, * signed: the sections the frame entered less those of its callers it left; * - with BPF_FRAME_ENT_COUNT no location: the count of the sections the frame @@ -1891,6 +1894,7 @@ struct bpf_resource { /* Released before the other entries of the frame, which it may be using. */ #define BPF_FRAME_ENT_FIRST BIT(3) #define BPF_FRAME_ENT_REG BIT(4) +#define BPF_FRAME_ENT_FIXED BIT(5) struct bpf_frame_desc_entry { u16 res; /* index into the program's resource classes */ diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 158e7eddc19f..a7c9b113e071 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -1253,6 +1253,7 @@ void bpf_patch_image_install(struct bpf_prog *prog, const struct bpf_patch_image #define BPF_RES_F_MAY_FAIL BIT(1) /* acquired only when the call returns 0 */ #define BPF_RES_F_DEREF BIT(2) /* the handle is the first word of a dynptr on the stack */ #define BPF_RES_F_CTX BIT(3) /* a __ref argument the kernel passes the main program */ +#define BPF_RES_F_NO_PTR BIT(5) /* a lock that no pointer to what it is in leads to */ /* * A call that acquires a resource, see frame_desc.c. When a frame can be @@ -1301,6 +1302,7 @@ struct bpf_res_loc { u16 acq; /* index of the acquisition */ u8 cnt; /* the places left */ bool obj; /* they are the resource itself, an object on the stack */ + bool fixed; /* it is a lock at the address of its class, and needs no place */ struct { s16 off; /* relative to R10, or the number of the register */ s16 adj; /* the pointer there points that many bytes into the object */ diff --git a/kernel/bpf/frame_desc.c b/kernel/bpf/frame_desc.c index 5cb837688f90..72dc6597321a 100644 --- a/kernel/bpf/frame_desc.c +++ b/kernel/bpf/frame_desc.c @@ -376,6 +376,42 @@ static int resource_of_kind(struct bpf_verifier_env *env, u8 kind) return resource_intern(env, &res); } +/* + * The class of the lock that the current insn takes through @reg, a pointer + * to it. A lock in the only element of an array map, which every global + * variable is, is at a fixed address: its class says where, and a site needs + * no place for it. That is so for a map the program refers to itself only: + * what stands for the inner maps of a map has no values. Any other lock is + * @off bytes into what the pointer is into, a map value or an object: a site + * finds it through a pointer to that which the frame keeps, unless the offset + * is too large for a site to tell, see BPF_RES_F_NO_PTR. + */ +static int resource_of_lock(struct bpf_verifier_env *env, const struct bpf_reference_state *ref, + const struct bpf_reg_state *reg, s16 *off, u8 *flags) +{ + struct bpf_resource res; + const struct bpf_map *map; + u64 base; + u32 i; + + memset(&res, 0, sizeof(res)); + res.kind = ref->type == REF_TYPE_LOCK ? BPF_RESOURCE_SPIN_LOCK : BPF_RESOURCE_RES_LOCK; + if (!reg || !tnum_is_const(reg->var_off) || + reg->var_off.value != (u64)(s16)reg->var_off.value) { + *flags |= BPF_RES_F_NO_PTR; + return resource_intern(env, &res); + } + *off = reg->var_off.value; + map = reg->type == PTR_TO_MAP_VALUE ? reg->map_ptr : NULL; + for (i = 0; map && i < env->used_map_cnt; i++) + if (env->used_maps[i] == map) + break; + if (map && i < env->used_map_cnt && map->map_type == BPF_MAP_TYPE_ARRAY && + map->ops->map_direct_value_addr && !map->ops->map_direct_value_addr(map, &base, *off)) + res.addr = (void *)(long)(base + *off); + return resource_intern(env, &res); +} + /* The offset from R10 of the stack slot @spi of a frame. */ static s16 spi_off(int spi) { @@ -397,6 +433,8 @@ static int acquired_class(struct bpf_verifier_env *env, struct bpf_verifier_stat s16 *adj, s16 *obj_off) { const struct bpf_func_state *frame = st->frame[st->curframe]; + /* a handle that is in no register can only be found by the sites */ + bool in_reg = regno >= BPF_REG_0 && regno <= BPF_REG_5; const struct bpf_stack_state *slot; struct bpf_resource res; struct bpf_reg_state reg; @@ -414,8 +452,7 @@ static int acquired_class(struct bpf_verifier_env *env, struct bpf_verifier_stat } *flags |= BPF_RES_F_ARG; if (ref->type & REF_TYPE_LOCK_MASK) - return resource_of_kind(env, ref->type == REF_TYPE_LOCK ? BPF_RESOURCE_SPIN_LOCK : - BPF_RESOURCE_RES_LOCK); + return resource_of_lock(env, ref, in_reg ? &frame->regs[regno] : NULL, adj, flags); if (!stack_object_find(st, ref, &objframe, &spi)) return -EOPNOTSUPP; if (objframe != st->curframe) @@ -794,9 +831,11 @@ static const u8 site_regs[] = { * The places of frame @f of @st that hold the handle of @ref, which the frame * owns, in @loc: the stack object the reference is of, or the slots of the * stack a pointer to the object is spilled in and the registers that hold - * one, see site_regs; @throws when the frame calls bpf_throw(). A lock has - * none. The slots a spill is removed from again, see - * bpf_remove_fastcall_spills_fills(), hold nothing at run time. + * one, see site_regs; @throws when the frame calls bpf_throw(). A lock at a + * fixed address needs no place. Any other lock is found like an object, + * through a pointer to what it is in, which has the id of the lock. The slots + * a spill is removed from again, see bpf_remove_fastcall_spills_fills(), hold + * nothing at run time. */ static void ref_locations(struct bpf_verifier_env *env, const struct bpf_verifier_state *st, int f, const struct bpf_reference_state *ref, bool throws, @@ -805,42 +844,50 @@ static void ref_locations(struct bpf_verifier_env *env, const struct bpf_verifie const struct bpf_res_acq *acq = &env->res_acqs[ref->acq - 1]; const struct bpf_func_state *frame = st->frame[f]; s16 adj, lim = env->subprog_info[frame->subprogno].fastcall_stack_end; + bool lock = ref->type & REF_TYPE_LOCK_MASK, ptr; const struct bpf_stack_state *slot; int k; + memset(loc->at, 0, sizeof(loc->at)); loc->cnt = 0; loc->obj = false; - if (ref->type & REF_TYPE_LOCK_MASK) + loc->fixed = lock && env->resources[acq->res].addr; + if (loc->fixed) { + loc->cnt = 1; return; + } + /* a pointer the frame keeps: to the object, or to what a lock with an id is in */ + ptr = lock ? ref->id && !(acq->flags & BPF_RES_F_NO_PTR) : + ref->type == REF_TYPE_PTR && !(acq->flags & BPF_RES_F_ARG); for (k = 0; k < bpf_stack_nr_slots(frame) && loc->cnt < BPF_RES_LOC_MAX; k++) { slot = bpf_stack_slot(frame, k); adj = 0; if (spi_off(k) < lim) break; - if (stack_slot_is_object(slot, ref->id)) { + if (!lock && stack_slot_is_object(slot, ref->id)) { /* the handle of a dynptr is its first word, as when it was created */ if (slot->slot_type[BPF_REG_SIZE - 1] != STACK_DYNPTR) { loc->obj = true; loc->cnt = 0; } - } else if (ref->type != REF_TYPE_PTR || (acq->flags & BPF_RES_F_ARG) || - !bpf_is_spilled_reg(slot) || !reg_ref_off(&slot->spilled_ptr, ref->id, &adj)) { + } else if (!ptr || !bpf_is_spilled_reg(slot) || + !reg_ref_off(&slot->spilled_ptr, ref->id, &adj)) { continue; } loc->at[loc->cnt].off = spi_off(k); - loc->at[loc->cnt].reg = false; - loc->at[loc->cnt++].adj = adj; + /* the acquisition of a lock has how far the lock is into what it is in */ + loc->at[loc->cnt++].adj = lock ? adj - acq->adj : adj; if (loc->obj) return; } - if (!env->describe_regs || ref->type != REF_TYPE_PTR || (acq->flags & BPF_RES_F_ARG)) + if (!env->describe_regs || !ptr) return; for (k = 0; k < (throws ? ARRAY_SIZE(site_regs) : 4) && loc->cnt < BPF_RES_LOC_MAX; k++) { if (!reg_ref_off(&frame->regs[site_regs[k]], ref->id, &adj)) continue; loc->at[loc->cnt].off = site_regs[k]; loc->at[loc->cnt].reg = true; - loc->at[loc->cnt++].adj = adj; + loc->at[loc->cnt++].adj = lock ? adj - acq->adj : adj; } } @@ -908,7 +955,7 @@ static int site_visit(struct bpf_verifier_env *env, const struct bpf_verifier_st if (cur.at[j].off == loc->at[k].off && cur.at[j].adj == loc->at[k].adj && cur.at[j].reg == loc->at[k].reg) break; - if (j < cur.cnt && cur.obj == loc->obj) + if (j < cur.cnt && cur.obj == loc->obj && cur.fixed == loc->fixed) loc->at[n++] = loc->at[k]; } loc->cnt = n; @@ -1481,7 +1528,7 @@ static int build_site(struct bpf_verifier_env *env, u32 idx, const u32 *new_of) for (i = 0; i < env->res_loc_cnt; i++) { const struct bpf_res_loc *loc = &env->res_locs[i]; const struct bpf_res_acq *a = &env->res_acqs[loc->acq]; - u16 flags = loc->obj ? BPF_FRAME_ENT_OBJ : 0; + u16 flags = loc->obj ? BPF_FRAME_ENT_OBJ : loc->fixed ? BPF_FRAME_ENT_FIXED : 0; if (loc->site != idx || a->slot) continue; diff --git a/kernel/bpf/unwind.c b/kernel/bpf/unwind.c index 473897c3aff7..d3cd95f08769 100644 --- a/kernel/bpf/unwind.c +++ b/kernel/bpf/unwind.c @@ -233,6 +233,8 @@ static void bpf_unwind_release_desc(struct bpf_unwind_ctx *ctx, const struct bpf continue; if (ent->flags & BPF_FRAME_ENT_OBJ) { handle = loc; + } else if (ent->flags & BPF_FRAME_ENT_FIXED) { + handle = res->addr; } else { /* no descriptor names a register that was not captured */ if ((ent->flags & BPF_FRAME_ENT_REG) && WARN_ON_ONCE(!ctx->entry)) -- 2.53.0