Re: [RFC PATCH v1 05/14] bpf: Implement BPF exception frame descriptor generation

[Eduard Zingerman <eddyz87@gmail.com>]

On Thu, 2024-02-01 at 04:21 +0000, Kumar Kartikeya Dwivedi wrote:

Question: are there any real-life programs adapted to use exceptions
with cleanup feature? It would be interesting to see how robust
one-descriptor-per-pc is in practice, and also how it affects memory
consumption during verification.

The algorithm makes sense to me, a few comments/nits below.

[...]

> +static int find_and_merge_frame_desc(struct bpf_verifier_env *env, struct bpf_exception_frame_desc_tab *fdtab, u64 pc, struct bpf_frame_desc_reg_entry *fd)
> +{
> +	struct bpf_exception_frame_desc **descs = NULL, *desc = NULL, *p;
> +	int ret = 0;
> +
> +	for (int i = 0; i < fdtab->cnt; i++) {
> +		if (pc != fdtab->desc[i]->pc)
> +			continue;
> +		descs = &fdtab->desc[i];
> +		desc = fdtab->desc[i];
> +		break;
> +	}
> +
> +	if (!desc) {
> +		verbose(env, "frame_desc: find_and_merge: cannot find frame descriptor for pc=%llu, creating new entry\n", pc);
> +		return -ENOENT;
> +	}
> +
> +	if (fd->off < 0)
> +		goto stack;

Nit: maybe write it down as

	if (fd->off >= 0)
		return merge_frame_desc(...);

     and avoid goto?

[...]

> +static int gen_exception_frame_desc_stack_entry(struct bpf_verifier_env *env, struct bpf_func_state *frame, int stack_off)
> +{
> +	int spi = stack_off / BPF_REG_SIZE, off = -stack_off - 1;
> +	struct bpf_reg_state *reg, not_init_reg, null_reg;
> +	int slot_type, ret;
> +
> +	__mark_reg_not_init(env, &not_init_reg);
> +	__mark_reg_known_zero(&null_reg);

__mark_reg_known_zero() does not set .type field,
thus null_reg.type value is undefined.

> +
> +	slot_type = frame->stack[spi].slot_type[BPF_REG_SIZE - 1];
> +	reg = &frame->stack[spi].spilled_ptr;
> +
> +	switch (slot_type) {
> +	case STACK_SPILL:
> +		/* We skip all kinds of scalar registers, except NULL values, which consume a slot. */
> +		if (is_spilled_scalar_reg(&frame->stack[spi]) && !register_is_null(&frame->stack[spi].spilled_ptr))
> +			break;
> +		ret = gen_exception_frame_desc_reg_entry(env, reg, off, frame->frameno);
> +		if (ret < 0)
> +			return ret;
> +		break;
> +	case STACK_DYNPTR:
> +		/* Keep iterating until we find the first slot. */
> +		if (!reg->dynptr.first_slot)
> +			break;
> +		ret = gen_exception_frame_desc_dynptr_entry(env, reg, off, frame->frameno);
> +		if (ret < 0)
> +			return ret;
> +		break;
> +	case STACK_ITER:
> +		/* Keep iterating until we find the first slot. */
> +		if (!reg->ref_obj_id)
> +			break;
> +		ret = gen_exception_frame_desc_iter_entry(env, reg, off, frame->frameno);
> +		if (ret < 0)
> +			return ret;
> +		break;
> +	case STACK_MISC:
> +	case STACK_INVALID:
> +		/* Create an invalid entry for MISC and INVALID */
> +		ret = gen_exception_frame_desc_reg_entry(env, &not_init_reg, off, frame->frameno);
> +		if (ret < 0)
> +			return 0;

No tests are failing if I comment out this block.
Looking at the merge_frame_desc() logic it appears to me that fd
entries with fd->type == NOT_INIT would only be merged with other
NOT_INIT entries. What is the point of having such entries at all?

> +		break;
> +	case STACK_ZERO:
> +		reg = &null_reg;
> +		for (int i = BPF_REG_SIZE - 1; i >= 0; i--) {
> +			if (frame->stack[spi].slot_type[i] != STACK_ZERO)
> +				reg = &not_init_reg;
> +		}
> +		ret = gen_exception_frame_desc_reg_entry(env, &null_reg, off, frame->frameno);
> +		if (ret < 0)
> +			return ret;

Same here, no tests are failing if STACK_ZERO block is commented.
In general, what is the point of adding STACK_ZERO entries?
There is a logic in place to merge NULL and non-NULL entries,
but how is it different from not adding NULL entries in a first place?
find_and_merge_frame_desc() does a linear scan over bpf_exception_frame_desc->stack
and does not rely on entries being sorted by .off field.

> +		break;
> +	default:
> +		verbose(env, "verifier internal error: frame%d stack off=%d slot_type=%d missing handling for exception frame generation\n",
> +			frame->frameno, off, slot_type);
> +		return -EFAULT;
> +	}
> +	return 0;
> +}