On Thu, Apr 28, 2022 at 2:12 PM Joanne Koong <joannelkoong@xxxxxxxxx> wrote:
>
> This patch adds the bulk of the verifier work for supporting dynamic
> pointers (dynptrs) in bpf. This patch implements malloc-type dynptrs
> through 2 new APIs (bpf_dynptr_alloc and bpf_dynptr_put) that can be
> called by a bpf program. Malloc-type dynptrs are dynptrs that dynamically
> allocate memory on behalf of the program.
>
> A bpf_dynptr is opaque to the bpf program. It is a 16-byte structure
> defined internally as:
>
> struct bpf_dynptr_kern {
> void *data;
> u32 size;
> u32 offset;
> } __aligned(8);
>
> The upper 8 bits of *size* is reserved (it contains extra metadata about
> read-only status and dynptr type); consequently, a dynptr only supports
> memory less than 16 MB.
>
> The 2 new APIs for malloc-type dynptrs are:
>
> long bpf_dynptr_alloc(u32 size, u64 flags, struct bpf_dynptr *ptr);
> void bpf_dynptr_put(struct bpf_dynptr *ptr);
>
> Please note that there *must* be a corresponding bpf_dynptr_put for
> every bpf_dynptr_alloc (even if the alloc fails). This is enforced
> by the verifier.
>
> In the verifier, dynptr state information will be tracked in stack
> slots. When the program passes in an uninitialized dynptr
> (ARG_PTR_TO_DYNPTR | MEM_UNINIT), the stack slots corresponding
> to the frame pointer where the dynptr resides at are marked STACK_DYNPTR.
>
> For helper functions that take in initialized dynptrs (eg
> bpf_dynptr_read + bpf_dynptr_write which are added later in this
> patchset), the verifier enforces that the dynptr has been initialized
> properly by checking that their corresponding stack slots have been marked
> as STACK_DYNPTR. Dynptr release functions (eg bpf_dynptr_put) will clear the
> stack slots. The verifier enforces at program exit that there are no
> referenced dynptrs that haven't been released.
>
> Signed-off-by: Joanne Koong <joannelkoong@xxxxxxxxx>
> ---
> include/linux/bpf.h | 60 ++++++++-
> include/linux/bpf_verifier.h | 21 +++
> include/uapi/linux/bpf.h | 30 +++++
> kernel/bpf/helpers.c | 75 +++++++++++
> kernel/bpf/verifier.c | 225 ++++++++++++++++++++++++++++++++-
> scripts/bpf_doc.py | 2 +
> tools/include/uapi/linux/bpf.h | 30 +++++
> 7 files changed, 440 insertions(+), 3 deletions(-)
>
[...]
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 4565684839f1..16b7ea54a7e0 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -187,6 +187,11 @@ struct bpf_verifier_stack_elem {
> POISON_POINTER_DELTA))
> #define BPF_MAP_PTR(X) ((struct bpf_map *)((X) & ~BPF_MAP_PTR_UNPRIV))
>
> +/* forward declarations */
it's kind of obvious from C syntax, this comment doesn't really add value
> +static bool arg_type_is_mem_size(enum bpf_arg_type type);
> +static int acquire_reference_state(struct bpf_verifier_env *env, int insn_idx);
> +static int release_reference(struct bpf_verifier_env *env, int ref_obj_id);
> +
[...]
> static struct bpf_func_state *func(struct bpf_verifier_env *env,
> const struct bpf_reg_state *reg)
> {
> @@ -646,6 +672,134 @@ static void mark_verifier_state_scratched(struct bpf_verifier_env *env)
> env->scratched_stack_slots = ~0ULL;
> }
>
> +#define DYNPTR_TYPE_FLAG_MASK DYNPTR_TYPE_MALLOC
can this be put near where DYNPTR_TYPE_MALLOC is defined? It's quite
easy to forget to update this if it's somewhere far away
> +
> +static int arg_to_dynptr_type(enum bpf_arg_type arg_type)
> +{
> + switch (arg_type & DYNPTR_TYPE_FLAG_MASK) {
> + case DYNPTR_TYPE_MALLOC:
> + return BPF_DYNPTR_TYPE_MALLOC;
> + default:
> + return BPF_DYNPTR_TYPE_INVALID;
> + }
> +}
> +
[...]
> +static int unmark_stack_slots_dynptr(struct bpf_verifier_env *env, struct bpf_reg_state *reg)
> +{
> + struct bpf_func_state *state = func(env, reg);
> + int spi, i;
> +
> + spi = get_spi(reg->off);
> +
> + if (!is_spi_bounds_valid(state, spi, BPF_DYNPTR_NR_SLOTS))
> + return -EINVAL;
> +
> + for (i = 0; i < BPF_REG_SIZE; i++) {
> + state->stack[spi].slot_type[i] = STACK_INVALID;
> + state->stack[spi - 1].slot_type[i] = STACK_INVALID;
> + }
> +
> + /* Invalidate any slices associated with this dynptr */
> + if (dynptr_type_refcounted(state->stack[spi].spilled_ptr.dynptr.type)) {
> + release_reference(env, state->stack[spi].spilled_ptr.id);
> + state->stack[spi].spilled_ptr.id = 0;
> + state->stack[spi - 1].spilled_ptr.id = 0;
> + }
> +
> + state->stack[spi].spilled_ptr.dynptr.type = 0;
> + state->stack[spi - 1].spilled_ptr.dynptr.type = 0;
> +
> + state->stack[spi].spilled_ptr.dynptr.first_slot = false;
nit: given you marked slots as STACK_INVALID, we shouldn't even look
into spilled_ptr.dynptr, so this zeroing out isn't necessary, right?
> +
> + return 0;
> +}
> +
> +static bool is_dynptr_reg_valid_uninit(struct bpf_verifier_env *env, struct bpf_reg_state *reg)
> +{
> + struct bpf_func_state *state = func(env, reg);
> + int spi = get_spi(reg->off);
> + int i;
> +
> + if (!is_spi_bounds_valid(state, spi, BPF_DYNPTR_NR_SLOTS))
> + return true;
hm... if spi bounds are invalid, shouldn't that be an error?...
> +
> + for (i = 0; i < BPF_REG_SIZE; i++) {
> + if (state->stack[spi].slot_type[i] == STACK_DYNPTR ||
> + state->stack[spi - 1].slot_type[i] == STACK_DYNPTR)
> + return false;
> + }
> +
> + return true;
> +}
> +
> +static bool is_dynptr_reg_valid_init(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
> + enum bpf_arg_type arg_type)
> +{
> + struct bpf_func_state *state = func(env, reg);
> + int spi = get_spi(reg->off);
> + int i;
> +
> + if (!is_spi_bounds_valid(state, spi, BPF_DYNPTR_NR_SLOTS) ||
> + !state->stack[spi].spilled_ptr.dynptr.first_slot)
> + return false;
> +
> + for (i = 0; i < BPF_REG_SIZE; i++) {
> + if (state->stack[spi].slot_type[i] != STACK_DYNPTR ||
> + state->stack[spi - 1].slot_type[i] != STACK_DYNPTR)
> + return false;
> + }
minor, but seems like it's pretty common operation to set or check all
those "microslots" to STACK_DYNPTR, would two small helpers be useful
for this (e.g., is_stack_dynptr() and set_stack_dynptr() or something
along those lines)?
> +
> + /* ARG_PTR_TO_DYNPTR takes any type of dynptr */
> + if (arg_type == ARG_PTR_TO_DYNPTR)
> + return true;
> +
> + return state->stack[spi].spilled_ptr.dynptr.type == arg_to_dynptr_type(arg_type);
> +}
> +
[...]
> @@ -5837,6 +6011,35 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 arg,
> bool zero_size_allowed = (arg_type == ARG_CONST_SIZE_OR_ZERO);
>
> err = check_mem_size_reg(env, reg, regno, zero_size_allowed, meta);
> + } else if (arg_type_is_dynptr(arg_type)) {
> + /* Can't pass in a dynptr at a weird offset */
> + if (reg->off % BPF_REG_SIZE) {
> + verbose(env, "cannot pass in non-zero dynptr offset\n");
> + return -EINVAL;
> + }
> +
> + if (arg_type & MEM_UNINIT) {
> + if (!is_dynptr_reg_valid_uninit(env, reg)) {
> + verbose(env, "Arg #%d dynptr has to be an uninitialized dynptr\n",
> + arg + BPF_REG_1);
> + return -EINVAL;
> + }
> +
> + meta->uninit_dynptr_regno = arg + BPF_REG_1;
do we need a check that meta->uninit_dynptr_regno isn't already set?
I.e., prevent two uninit dynptr in a helper?
> + } else if (!is_dynptr_reg_valid_init(env, reg, arg_type)) {
> + const char *err_extra = "";
> +
> + switch (arg_type & DYNPTR_TYPE_FLAG_MASK) {
> + case DYNPTR_TYPE_MALLOC:
> + err_extra = "malloc ";
> + break;
> + default:
> + break;
> + }
> + verbose(env, "Expected an initialized %sdynptr as arg #%d\n",
> + err_extra, arg + BPF_REG_1);
> + return -EINVAL;
> + }
> } else if (arg_type_is_alloc_size(arg_type)) {
> if (!tnum_is_const(reg->var_off)) {
> verbose(env, "R%d is not a known constant'\n",
[...]
