Re: [PATCH bpf-next 10/13] bpf, x86: BPF_PROBE_MEM handling for insn->off < 0

[Dave Marchevsky <davemarchevsky@meta.com>]

On 12/6/22 9:39 PM, Alexei Starovoitov wrote:
> On Tue, Dec 06, 2022 at 03:09:57PM -0800, Dave Marchevsky wrote:
>> Current comment in BPF_PROBE_MEM jit code claims that verifier prevents
>> insn->off < 0, but this appears to not be true irrespective of changes
>> in this series. Regardless, changes in this series will result in an
>> example like:
>>
>>   struct example_node {
>>     long key;
>>     long val;
>>     struct bpf_rb_node node;
>>   }
>>
>>   /* In BPF prog, assume root contains example_node nodes */
>>   struct bpf_rb_node res = bpf_rbtree_first(&root);
>>   if (!res)
>>     return 1;
>>
>>   struct example_node n = container_of(res, struct example_node, node);
>>   long key = n->key;
>>
>> Resulting in a load with off = -16, as bpf_rbtree_first's return is
> 
> Looks like the bug in the previous patch:
> +                       } else if (meta.func_id == special_kfunc_list[KF_bpf_rbtree_remove] ||
> +                                  meta.func_id == special_kfunc_list[KF_bpf_rbtree_first]) {
> +                               struct btf_field *field = meta.arg_rbtree_root.field;
> +
> +                               mark_reg_datastructure_node(regs, BPF_REG_0,
> +                                                           &field->datastructure_head);
> 
> The R0 .off should have been:
>  regs[BPF_REG_0].off = field->rb_node.node_offset;
> 
> node, not root.
> 
> PTR_TO_BTF_ID should have been returned with approriate 'off',
> so that container_of() would it bring back to zero offset.
> 

The root's btf_field is used to hold information about the node type. Of
specific interest to us are value_btf_id and node_offset, which
mark_reg_datastructure_node uses to set REG_0's type and offset correctly.

This "use head type to keep info about node type" strategy felt strange to me
initially too: all PTR_TO_BTF_ID regs are passing around their type info, so
why not use that to lookup bpf_rb_node field info? But consider that
bpf_rbtree_first (and bpf_list_pop_{front,back}) doesn't take a node as
input arg, so there's no opportunity to get btf_field info from input
reg type. 

So we'll need to keep this info in rbtree_root's btf_field
regardless, and since any rbtree API function that operates on a node
also operates on a root and expects its node arg to match the node
type expected by the root, might as well use root's field as the main
lookup for this info and not even have &field->rb_node for now.
All __process_kf_arg_ptr_to_datastructure_node calls (added earlier
in the series) use the &meta->arg_{list_head,rbtree_root}.field for same
reason.

So it's setting the reg offset correctly.

> All PTR_TO_BTF_ID need to have positive offset.
> I'm not sure btf_struct_walk() and other PTR_TO_BTF_ID accessors
> can deal with negative offsets.
> There could be all kinds of things to fix.

I think you may be conflating reg offset and insn offset here. None of the
changes in this series result in a PTR_TO_BTF_ID reg w/ negative offset
being returned. But LLVM may generate load insns with a negative offset,
and since we're passing around pointers to bpf_rb_node that may come
after useful data fields in a type, this will happen more often.

Consider this small example from selftests in this series:

struct node_data {
  long key;
  long data;
  struct bpf_rb_node node;
};

static bool less(struct bpf_rb_node *a, const struct bpf_rb_node *b)
{
        struct node_data *node_a;
        struct node_data *node_b;

        node_a = container_of(a, struct node_data, node);
        node_b = container_of(b, struct node_data, node);

        return node_a->key < node_b->key;
}

llvm-objdump shows this bpf bytecode for 'less':

0000000000000000 <less>:
;       return node_a->key < node_b->key;
       0:       79 22 f0 ff 00 00 00 00 r2 = *(u64 *)(r2 - 0x10)
       1:       79 11 f0 ff 00 00 00 00 r1 = *(u64 *)(r1 - 0x10)
       2:       b4 00 00 00 01 00 00 00 w0 = 0x1
;       return node_a->key < node_b->key;
       3:       cd 21 01 00 00 00 00 00 if r1 s< r2 goto +0x1 <LBB2_2>
       4:       b4 00 00 00 00 00 00 00 w0 = 0x0

0000000000000028 <LBB2_2>:
;       return node_a->key < node_b->key;
       5:       95 00 00 00 00 00 00 00 exit

Insns 0 and 1 are loading node_b->key and node_a->key, respectively, using
negative insn->off. Verifier's view or R1 and R2 before insn 0 is
untrusted_ptr_node_data(off=16). If there were some intermediate insns
storing result of container_of() before dereferencing:

  r3 = (r2 - 0x10)
  r2 = *(u64 *)(r3)

Verifier would see R3 as untrusted_ptr_node_data(off=0), and load for
r2 would have insn->off = 0. But LLVM decides to just do a load-with-offset
using original arg ptrs to less() instead of storing container_of() ptr
adjustments.

Since the container_of usage and code pattern in above example's less()
isn't particularly specific to this series, I think there are other scenarios
where such code would be generated and considered this a general bugfix in
cover letter.

[ below paragraph was moved here, it originally preceded "All PTR_TO_BTF_ID"
  paragraph ]

> The apporach of returning untrusted from bpf_rbtree_first is questionable.
> Without doing that this issue would not have surfaced.
> 

I agree re: PTR_UNTRUSTED, but note that my earlier example doesn't involve
bpf_rbtree_first. Regardless, I think the issue is that PTR_UNTRUSTED is
used to denote a few separate traits of a PTR_TO_BTF_ID reg:

  * "I have no ownership over the thing I'm pointing to"
  * "My backing memory may go away at any time"
  * "Access to my fields might result in page fault"
  * "Kfuncs shouldn't accept me as an arg"

Seems like original PTR_UNTRUSTED usage really wanted to denote the first
point and the others were just naturally implied from the first. But
as you've noted there are some things using PTR_UNTRUSTED that really
want to make more granular statements:

ref_set_release_on_unlock logic sets release_on_unlock = true and adds
PTR_UNTRUSTED to the reg type. In this case PTR_UNTRUSTED is trying to say:

  * "I have no ownership over the thing I'm pointing to"
  * "My backing memory may go away at any time _after_ bpf_spin_unlock"
    * Before spin_unlock it's guaranteed to be valid
  * "Kfuncs shouldn't accept me as an arg"
    * We don't want arbitrary kfunc saving and accessing release_on_unlock
      reg after bpf_spin_unlock, as its backing memory can go away any time
      after spin_unlock.

The "backing memory" statement PTR_UNTRUSTED is making is a blunt superset
of what release_on_unlock really needs.

For less() callback we just want

  * "I have no ownership over the thing I'm pointing to"
  * "Kfuncs shouldn't accept me as an arg"

There is probably a way to decompose PTR_UNTRUSTED into a few flags such that
it's possible to denote these things separately and avoid unwanted additional
behavior. But after talking to David Vernet about current complexity of
PTR_TRUSTED and PTR_UNTRUSTED logic and his desire to refactor, it seemed
better to continue with PTR_UNTRUSTED blunt instrument with a bit of
special casing for now, instead of piling on more flags.

> 
>> modified by verifier to be PTR_TO_BTF_ID of example_node w/ offset =
>> offsetof(struct example_node, node), instead of PTR_TO_BTF_ID of
>> bpf_rb_node. So it's necessary to support negative insn->off when
>> jitting BPF_PROBE_MEM.
> 
> I'm not convinced it's necessary.
> container_of() seems to be the only case where bpf prog can convert
> PTR_TO_BTF_ID with off >= 0 to negative off.
> Normal pointer walking will not make it negative.
> 

I see what you mean - if some non-container_of case resulted in load generation
with negative insn->off, this probably would've been noticed already. But
hopefully my replies above explain why it should be addressed now.

>> In order to ensure that page fault for a BPF_PROBE_MEM load of *src_reg +
>> insn->off is safely handled, we must confirm that *src_reg + insn->off is
>> in kernel's memory. Two runtime checks are emitted to confirm that:
>>
>>   1) (*src_reg + insn->off) > boundary between user and kernel address
>>   spaces
>>   2) (*src_reg + insn->off) does not overflow to a small positive
>>   number. This might happen if some function meant to set src_reg
>>   returns ERR_PTR(-EINVAL) or similar.
>>
>> Check 1 currently is sligtly off - it compares a
>>
>>   u64 limit = TASK_SIZE_MAX + PAGE_SIZE + abs(insn->off);
>>
>> to *src_reg, aborting the load if limit is larger. Rewriting this as an
>> inequality:
>>
>>   *src_reg > TASK_SIZE_MAX + PAGE_SIZE + abs(insn->off)
>>   *src_reg - abs(insn->off) > TASK_SIZE_MAX + PAGE_SIZE
>>
>> shows that this isn't quite right even if insn->off is positive, as we
>> really want:
>>
>>   *src_reg + insn->off > TASK_SIZE_MAX + PAGE_SIZE
>>   *src_reg > TASK_SIZE_MAX + PAGE_SIZE - insn_off
>>
>> Since *src_reg + insn->off is the address we'll be loading from, not
>> *src_reg - insn->off or *src_reg - abs(insn->off). So change the
>> subtraction to an addition and remove the abs(), as comment indicates
>> that it was only added to ignore negative insn->off.
>>
>> For Check 2, currently "does not overflow to a small positive number" is
>> confirmed by emitting an 'add insn->off, src_reg' instruction and
>> checking for carry flag. While this works fine for a positive insn->off,
>> a small negative insn->off like -16 is almost guaranteed to wrap over to
>> a small positive number when added to any kernel address.
>>
>> This patch addresses this by not doing Check 2 at BPF prog runtime when
>> insn->off is negative, rather doing a stronger check at JIT-time. The
>> logic supporting this is as follows:
>>
>> 1) Assume insn->off is negative, call the largest such negative offset
>>    MAX_NEGATIVE_OFF. So insn->off >= MAX_NEGATIVE_OFF for all possible
>>    insn->off.
>>
>> 2) *src_reg + insn->off will not wrap over to an unexpected address by
>>    virtue of negative insn->off, but it might wrap under if
>>    -insn->off > *src_reg, as that implies *src_reg + insn->off < 0
>>
>> 3) Inequality (TASK_SIZE_MAX + PAGE_SIZE - insn->off) > (TASK_SIZE_MAX + PAGE_SIZE)
>>    must be true since insn->off is negative.
>>
>> 4) If we've completed check 1, we know that
>>    src_reg >= (TASK_SIZE_MAX + PAGE_SIZE - insn->off)
>>
>> 5) Combining statements 3 and 4, we know src_reg > (TASK_SIZE_MAX + PAGE_SIZE)
>>
>> 6) By statements 1, 4, and 5, if we can prove
>>    (TASK_SIZE_MAX + PAGE_SIZE) > -MAX_NEGATIVE_OFF, we'll know that
>>    (TASK_SIZE_MAX + PAGE_SIZE) > -insn->off for all possible insn->off
>>    values. We can rewrite this as (TASK_SIZE_MAX + PAGE_SIZE) +
>>    MAX_NEGATIVE_OFF > 0.
>>
>>    Since src_reg > TASK_SIZE_MAX + PAGE_SIZE and MAX_NEGATIVE_OFF is
>>    negative, if the previous inequality is true,
>>    src_reg + MAX_NEGATIVE_OFF > 0 is also true for all src_reg values.
>>    Similarly, since insn->off >= MAX_NEGATIVE_OFF for all possible
>>    negative insn->off vals, src_reg + insn->off > 0 and there can be no
>>    wrapping under.
>>
>> So proving (TASK_SIZE_MAX + PAGE_SIZE) + MAX_NEGATIVE_OFF > 0 implies
>> *src_reg + insn->off > 0 for any src_reg that's passed check 1 and any
>> negative insn->off. Luckily the former inequality does not need to be
>> checked at runtime, and in fact could be a static_assert if
>> TASK_SIZE_MAX wasn't determined by a function when CONFIG_X86_5LEVEL
>> kconfig is used.
>>
>> Regardless, we can just check (TASK_SIZE_MAX + PAGE_SIZE) +
>> MAX_NEGATIVE_OFF > 0 once per do_jit call instead of emitting a runtime
>> check. Given that insn->off is a s16 and is unlikely to grow larger,
>> this check should always succeed on any x86 processor made in the 21st
>> century. If it doesn't fail all do_jit calls and complain loudly with
>> the assumption that the BPF subsystem is misconfigured or has a bug.
>>
>> A few instructions are saved for negative insn->offs as a result. Using
>> the struct example_node / off = -16 example from before, code looks
>> like:
> 
> This is quite complex to review. I couldn't convince myself
> that droping 2nd check is safe, but don't have an argument to
> prove that it's not safe.
> Let's get to these details when there is need to support negative off.
> 

Hopefully above explanation shows that there's need to support it now.
I will try to simplify and rephrase the summary to make it easier to follow,
but will prioritize addressing feedback in less complex patches, so this
patch may not change for a few respins.

>>
>> BEFORE CHANGE
>>   72:   movabs $0x800000000010,%r11
>>   7c:   cmp    %r11,%rdi
>>   7f:   jb     0x000000000000008d         (check 1 on 7c and here)
>>   81:   mov    %rdi,%r11
>>   84:   add    $0xfffffffffffffff0,%r11   (check 2, will set carry for almost any r11, so bug for
>>   8b:   jae    0x0000000000000091          negative insn->off)
>>   8d:   xor    %edi,%edi                  (as a result long key = n->key; will be 0'd out here)
>>   8f:   jmp    0x0000000000000095
>>   91:   mov    -0x10(%rdi),%rdi
>>   95:
>>
>> AFTER CHANGE:
>>   5a:   movabs $0x800000000010,%r11
>>   64:   cmp    %r11,%rdi
>>   67:   jae    0x000000000000006d     (check 1 on 64 and here, but now JNC instead of JC)
>>   69:   xor    %edi,%edi              (no check 2, 0 out if %rdi - %r11 < 0)
>>   6b:   jmp    0x0000000000000071
>>   6d:   mov    -0x10(%rdi),%rdi
>>   71:
>>
>> We could do the same for insn->off == 0, but for now keep code
>> generation unchanged for previously working nonnegative insn->offs.
>>
>> Signed-off-by: Dave Marchevsky <davemarchevsky@fb.com>
>> ---
>>  arch/x86/net/bpf_jit_comp.c | 123 +++++++++++++++++++++++++++---------
>>  1 file changed, 92 insertions(+), 31 deletions(-)
>>
>> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
>> index 36ffe67ad6e5..843f619d0d35 100644
>> --- a/arch/x86/net/bpf_jit_comp.c
>> +++ b/arch/x86/net/bpf_jit_comp.c
>> @@ -11,6 +11,7 @@
>>  #include <linux/bpf.h>
>>  #include <linux/memory.h>
>>  #include <linux/sort.h>
>> +#include <linux/limits.h>
>>  #include <asm/extable.h>
>>  #include <asm/set_memory.h>
>>  #include <asm/nospec-branch.h>
>> @@ -94,6 +95,7 @@ static int bpf_size_to_x86_bytes(int bpf_size)
>>   */
>>  #define X86_JB  0x72
>>  #define X86_JAE 0x73
>> +#define X86_JNC 0x73
>>  #define X86_JE  0x74
>>  #define X86_JNE 0x75
>>  #define X86_JBE 0x76
>> @@ -950,6 +952,36 @@ static void emit_shiftx(u8 **pprog, u32 dst_reg, u8 src_reg, bool is64, u8 op)
>>  	*pprog = prog;
>>  }
>>  
>> +/* Check that condition necessary for PROBE_MEM handling for insn->off < 0
>> + * holds.
>> + *
>> + * This could be a static_assert((TASK_SIZE_MAX + PAGE_SIZE) > -S16_MIN),
>> + * but TASK_SIZE_MAX can't always be evaluated at compile time, so let's not
>> + * assume insn->off size either
>> + */
>> +static int check_probe_mem_task_size_overflow(void)
>> +{
>> +	struct bpf_insn insn;
>> +	s64 max_negative;
>> +
>> +	switch (sizeof(insn.off)) {
>> +	case 2:
>> +		max_negative = S16_MIN;
>> +		break;
>> +	default:
>> +		pr_err("bpf_jit_error: unexpected bpf_insn->off size\n");
>> +		return -EFAULT;
>> +	}
>> +
>> +	if (!((TASK_SIZE_MAX + PAGE_SIZE) > -max_negative)) {
>> +		pr_err("bpf jit error: assumption does not hold:\n");
>> +		pr_err("\t(TASK_SIZE_MAX + PAGE_SIZE) + (max negative insn->off) > 0\n");
>> +		return -EFAULT;
>> +	}
>> +
>> +	return 0;
>> +}
>> +
>>  #define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))
>>  
>>  static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image,
>> @@ -967,6 +999,10 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
>>  	u8 *prog = temp;
>>  	int err;
>>  
>> +	err = check_probe_mem_task_size_overflow();
>> +	if (err)
>> +		return err;
>> +
>>  	detect_reg_usage(insn, insn_cnt, callee_regs_used,
>>  			 &tail_call_seen);
>>  
>> @@ -1359,20 +1395,30 @@ st:			if (is_imm8(insn->off))
>>  		case BPF_LDX | BPF_MEM | BPF_DW:
>>  		case BPF_LDX | BPF_PROBE_MEM | BPF_DW:
>>  			if (BPF_MODE(insn->code) == BPF_PROBE_MEM) {
>> -				/* Though the verifier prevents negative insn->off in BPF_PROBE_MEM
>> -				 * add abs(insn->off) to the limit to make sure that negative
>> -				 * offset won't be an issue.
>> -				 * insn->off is s16, so it won't affect valid pointers.
>> -				 */
>> -				u64 limit = TASK_SIZE_MAX + PAGE_SIZE + abs(insn->off);
>> -				u8 *end_of_jmp1, *end_of_jmp2;
>> -
>>  				/* Conservatively check that src_reg + insn->off is a kernel address:
>> -				 * 1. src_reg + insn->off >= limit
>> -				 * 2. src_reg + insn->off doesn't become small positive.
>> -				 * Cannot do src_reg + insn->off >= limit in one branch,
>> -				 * since it needs two spare registers, but JIT has only one.
>> +				 * 1. src_reg + insn->off >= TASK_SIZE_MAX + PAGE_SIZE
>> +				 * 2. src_reg + insn->off doesn't overflow and become small positive
>> +				 *
>> +				 * For check 1, to save regs, do
>> +				 * src_reg >= (TASK_SIZE_MAX + PAGE_SIZE - insn->off) call rhs
>> +				 * of inequality 'limit'
>> +				 *
>> +				 * For check 2:
>> +				 * If insn->off is positive, add src_reg + insn->off and check
>> +				 * overflow directly
>> +				 * If insn->off is negative, we know that
>> +				 *   (TASK_SIZE_MAX + PAGE_SIZE - insn->off) > (TASK_SIZE_MAX + PAGE_SIZE)
>> +				 * and from check 1 we know
>> +				 *   src_reg >= (TASK_SIZE_MAX + PAGE_SIZE - insn->off)
>> +				 * So if (TASK_SIZE_MAX + PAGE_SIZE) + MAX_NEGATIVE_OFF > 0 we can
>> +				 * be sure that src_reg + insn->off won't overflow in either
>> +				 * direction and avoid runtime check entirely.
>> +				 *
>> +				 * check_probe_mem_task_size_overflow confirms the above assumption
>> +				 * at the beginning of this function
>>  				 */
>> +				u64 limit = TASK_SIZE_MAX + PAGE_SIZE - insn->off;
>> +				u8 *end_of_jmp1, *end_of_jmp2;
>>  
>>  				/* movabsq r11, limit */
>>  				EMIT2(add_1mod(0x48, AUX_REG), add_1reg(0xB8, AUX_REG));
>> @@ -1381,32 +1427,47 @@ st:			if (is_imm8(insn->off))
>>  				/* cmp src_reg, r11 */
>>  				maybe_emit_mod(&prog, src_reg, AUX_REG, true);
>>  				EMIT2(0x39, add_2reg(0xC0, src_reg, AUX_REG));
>> -				/* if unsigned '<' goto end_of_jmp2 */
>> -				EMIT2(X86_JB, 0);
>> -				end_of_jmp1 = prog;
>> -
>> -				/* mov r11, src_reg */
>> -				emit_mov_reg(&prog, true, AUX_REG, src_reg);
>> -				/* add r11, insn->off */
>> -				maybe_emit_1mod(&prog, AUX_REG, true);
>> -				EMIT2_off32(0x81, add_1reg(0xC0, AUX_REG), insn->off);
>> -				/* jmp if not carry to start_of_ldx
>> -				 * Otherwise ERR_PTR(-EINVAL) + 128 will be the user addr
>> -				 * that has to be rejected.
>> -				 */
>> -				EMIT2(0x73 /* JNC */, 0);
>> -				end_of_jmp2 = prog;
>> +				if (insn->off >= 0) {
>> +					/* cmp src_reg, r11 */
>> +					/* if unsigned '<' goto end_of_jmp2 */
>> +					EMIT2(X86_JB, 0);
>> +					end_of_jmp1 = prog;
>> +
>> +					/* mov r11, src_reg */
>> +					emit_mov_reg(&prog, true, AUX_REG, src_reg);
>> +					/* add r11, insn->off */
>> +					maybe_emit_1mod(&prog, AUX_REG, true);
>> +					EMIT2_off32(0x81, add_1reg(0xC0, AUX_REG), insn->off);
>> +					/* jmp if not carry to start_of_ldx
>> +					 * Otherwise ERR_PTR(-EINVAL) + 128 will be the user addr
>> +					 * that has to be rejected.
>> +					 */
>> +					EMIT2(X86_JNC, 0);
>> +					end_of_jmp2 = prog;
>> +				} else {
>> +					/* cmp src_reg, r11 */
>> +					/* if unsigned '>=' goto start_of_ldx
>> +					 * w/o needing to do check 2
>> +					 */
>> +					EMIT2(X86_JAE, 0);
>> +					end_of_jmp1 = prog;
>> +				}
>>  
>>  				/* xor dst_reg, dst_reg */
>>  				emit_mov_imm32(&prog, false, dst_reg, 0);
>>  				/* jmp byte_after_ldx */
>>  				EMIT2(0xEB, 0);
>>  
>> -				/* populate jmp_offset for JB above to jump to xor dst_reg */
>> -				end_of_jmp1[-1] = end_of_jmp2 - end_of_jmp1;
>> -				/* populate jmp_offset for JNC above to jump to start_of_ldx */
>>  				start_of_ldx = prog;
>> -				end_of_jmp2[-1] = start_of_ldx - end_of_jmp2;
>> +				if (insn->off >= 0) {
>> +					/* populate jmp_offset for JB above to jump to xor dst_reg */
>> +					end_of_jmp1[-1] = end_of_jmp2 - end_of_jmp1;
>> +					/* populate jmp_offset for JNC above to jump to start_of_ldx */
>> +					end_of_jmp2[-1] = start_of_ldx - end_of_jmp2;
>> +				} else {
>> +					/* populate jmp_offset for JAE above to jump to start_of_ldx */
>> +					end_of_jmp1[-1] = start_of_ldx - end_of_jmp1;
>> +				}
>>  			}
>>  			emit_ldx(&prog, BPF_SIZE(insn->code), dst_reg, src_reg, insn->off);
>>  			if (BPF_MODE(insn->code) == BPF_PROBE_MEM) {
>> -- 
>> 2.30.2
>>