LLVM 4.0 code generation bug

LLVM 4.0 code generation bug

[David Miller]

If the last BPF instruction before exit is a ldimm64, branches to the
exit point at the wrong location.

Here is what I get from test_pkt_access.c on sparc:

0000000000000000 <process>:
   0:	b7 00 00 00 00 00 00 02 	mov	r0, 2
   8:	61 21 00 50 00 00 00 00 	ldw	r2, [r1+80]
  10:	61 11 00 4c 00 00 00 00 	ldw	r1, [r1+76]
  18:	bf 41 00 00 00 00 00 00 	mov	r4, r1
  20:	07 40 00 00 00 00 00 0e 	add	r4, 14
  28:	2d 42 00 25 00 00 00 00 	jgt	r4, r2, 148 <LBB0_11>
 ...
0000000000000148 <LBB0_11>:
 148:	18 00 00 00 ff ff ff ff 	ldimm64	r0, 4294967295
 150:	00 00 00 00 00 00 00 00 

0000000000000158 <LBB0_12>:
 158:	95 00 00 00 00 00 00 00 	exit	

The offset field in the "jgt" instruction is 0x25 which multiplied by
8 is 0x128, add 0x128 to the instruction location which is 0x28, and
we get 0x150, which is the second 64-bit chunk of the ldimm64
instruction.

At least this is what my JIT is interpreting this situation as, am I
off by one or something?

Re: LLVM 4.0 code generation bug

[Alexei Starovoitov]

On 5/1/17 7:31 PM, David Miller wrote:
>
> If the last BPF instruction before exit is a ldimm64, branches to the
> exit point at the wrong location.
>
> Here is what I get from test_pkt_access.c on sparc:
>
> 0000000000000000 <process>:
>    0:	b7 00 00 00 00 00 00 02 	mov	r0, 2
>    8:	61 21 00 50 00 00 00 00 	ldw	r2, [r1+80]
>   10:	61 11 00 4c 00 00 00 00 	ldw	r1, [r1+76]
>   18:	bf 41 00 00 00 00 00 00 	mov	r4, r1
>   20:	07 40 00 00 00 00 00 0e 	add	r4, 14
>   28:	2d 42 00 25 00 00 00 00 	jgt	r4, r2, 148 <LBB0_11>
>  ...
> 0000000000000148 <LBB0_11>:
>  148:	18 00 00 00 ff ff ff ff 	ldimm64	r0, 4294967295
>  150:	00 00 00 00 00 00 00 00
>
> 0000000000000158 <LBB0_12>:
>  158:	95 00 00 00 00 00 00 00 	exit	
>
> The offset field in the "jgt" instruction is 0x25 which multiplied by
> 8 is 0x128, add 0x128 to the instruction location which is 0x28, and
> we get 0x150, which is the second 64-bit chunk of the ldimm64
> instruction.

looks fine to me. it jumps to 0x158,
since offset 0 is the next insn after jump which is 0x30
That's how classic bpf defined jumps.

Re: LLVM 4.0 code generation bug

[David Miller]

From: Alexei Starovoitov <ast@fb.com>
Date: Mon, 1 May 2017 19:39:33 -0700

> On 5/1/17 7:31 PM, David Miller wrote:
>>
>> If the last BPF instruction before exit is a ldimm64, branches to the
>> exit point at the wrong location.
>>
>> Here is what I get from test_pkt_access.c on sparc:
>>
>> 0000000000000000 <process>:
>>    0:	b7 00 00 00 00 00 00 02 	mov	r0, 2
>>    8:	61 21 00 50 00 00 00 00 	ldw	r2, [r1+80]
>>   10:	61 11 00 4c 00 00 00 00 	ldw	r1, [r1+76]
>>   18:	bf 41 00 00 00 00 00 00 	mov	r4, r1
>>   20:	07 40 00 00 00 00 00 0e 	add	r4, 14
>>   28:	2d 42 00 25 00 00 00 00 	jgt	r4, r2, 148 <LBB0_11>
>>  ...
>> 0000000000000148 <LBB0_11>:
>>  148:	18 00 00 00 ff ff ff ff 	ldimm64	r0, 4294967295
>>  150:	00 00 00 00 00 00 00 00
>>
>> 0000000000000158 <LBB0_12>:
>>  158:	95 00 00 00 00 00 00 00 	exit	
>>
>> The offset field in the "jgt" instruction is 0x25 which multiplied by
>> 8 is 0x128, add 0x128 to the instruction location which is 0x28, and
>> we get 0x150, which is the second 64-bit chunk of the ldimm64
>> instruction.
> 
> looks fine to me. it jumps to 0x158,
> since offset 0 is the next insn after jump which is 0x30
> That's how classic bpf defined jumps.

Ok, let me first fix the binutils disassembler :-)

sparc64 and ARM64 JIT bug (was Re: LLVM 4.0 code generation bug)

[David Miller]

From: Alexei Starovoitov <ast@fb.com>
Date: Mon, 1 May 2017 19:39:33 -0700

> On 5/1/17 7:31 PM, David Miller wrote:
>>
>> If the last BPF instruction before exit is a ldimm64, branches to the
>> exit point at the wrong location.
>>
>> Here is what I get from test_pkt_access.c on sparc:
>>
>> 0000000000000000 <process>:
>>    0:	b7 00 00 00 00 00 00 02 	mov	r0, 2
>>    8:	61 21 00 50 00 00 00 00 	ldw	r2, [r1+80]
>>   10:	61 11 00 4c 00 00 00 00 	ldw	r1, [r1+76]
>>   18:	bf 41 00 00 00 00 00 00 	mov	r4, r1
>>   20:	07 40 00 00 00 00 00 0e 	add	r4, 14
>>   28:	2d 42 00 25 00 00 00 00 	jgt	r4, r2, 148 <LBB0_11>
>>  ...
>> 0000000000000148 <LBB0_11>:
>>  148:	18 00 00 00 ff ff ff ff 	ldimm64	r0, 4294967295
>>  150:	00 00 00 00 00 00 00 00
>>
>> 0000000000000158 <LBB0_12>:
>>  158:	95 00 00 00 00 00 00 00 	exit	
 ...
> looks fine to me. it jumps to 0x158,
> since offset 0 is the next insn after jump which is 0x30
> That's how classic bpf defined jumps.

Ok, it seems that both arm64 and sparc64's JIT handle the above
situation improperly.

They both work by recording the instruction offsets in an array which
is indexed off by one.  It it built like this:

	for (i = 0; i < prog->len; i++) {
		const struct bpf_insn *insn = &prog->insnsi[i];
		int ret;

		ret = build_insn(insn, ctx);
		ctx->offset[i] = ctx->idx;

		if (ret > 0) {
			i++;
			continue;
		}
		if (ret)
			return ret;
	}

That is, we record the JIT'd instruction offset for BPF instruction
'idx' in array entry 'idx - 1'.

Then when we emit a relative branch, we lookup the destination offset
using "ctx->offset[this_insn_idx + insn->off]"

And this works most of the time.  It doesn't work for the scenerio
above, because 'idx - 1' is not necessarily the index of the previous
BPF instruction.  Instead, that might point to the second half of an
lddimm64 instruction.

This bug was introduced by commit
8eee539ddea09bccae2426f09b0ba6a18b72b691 ("arm64: bpf: fix
out-of-bounds read in bpf2a64_offset()") and I copied the logic into
sparc64 :-)

Re: sparc64 and ARM64 JIT bug

[David Miller]

From: David Miller <davem@davemloft.net>
Date: Mon, 01 May 2017 23:02:34 -0400 (EDT)

> 	for (i = 0; i < prog->len; i++) {
> 		const struct bpf_insn *insn = &prog->insnsi[i];
> 		int ret;
> 
> 		ret = build_insn(insn, ctx);
> 		ctx->offset[i] = ctx->idx;
> 
> 		if (ret > 0) {
> 			i++;
> 			continue;
> 		}
> 		if (ret)
> 			return ret;
> 	}

Ok, the fix is to defer the ctx->offset[i] setting until after the
potential extra "i++" increment inside of the "if (ret > 0)" test.

This is how x86_64's JIT handles this.

I'm testing this fix on sparc64 now.

Re: sparc64 and ARM64 JIT bug (was Re: LLVM 4.0 code generation bug)

[Daniel Borkmann]

On 05/02/2017 05:02 AM, David Miller wrote:
> From: Alexei Starovoitov <ast@fb.com>
> Date: Mon, 1 May 2017 19:39:33 -0700
>
>> On 5/1/17 7:31 PM, David Miller wrote:
>>>
>>> If the last BPF instruction before exit is a ldimm64, branches to the
>>> exit point at the wrong location.
>>>
>>> Here is what I get from test_pkt_access.c on sparc:
>>>
>>> 0000000000000000 <process>:
>>>     0:	b7 00 00 00 00 00 00 02 	mov	r0, 2
>>>     8:	61 21 00 50 00 00 00 00 	ldw	r2, [r1+80]
>>>    10:	61 11 00 4c 00 00 00 00 	ldw	r1, [r1+76]
>>>    18:	bf 41 00 00 00 00 00 00 	mov	r4, r1
>>>    20:	07 40 00 00 00 00 00 0e 	add	r4, 14
>>>    28:	2d 42 00 25 00 00 00 00 	jgt	r4, r2, 148 <LBB0_11>
>>>   ...
>>> 0000000000000148 <LBB0_11>:
>>>   148:	18 00 00 00 ff ff ff ff 	ldimm64	r0, 4294967295
>>>   150:	00 00 00 00 00 00 00 00
>>>
>>> 0000000000000158 <LBB0_12>:
>>>   158:	95 00 00 00 00 00 00 00 	exit	
>   ...
>> looks fine to me. it jumps to 0x158,
>> since offset 0 is the next insn after jump which is 0x30
>> That's how classic bpf defined jumps.
>
> Ok, it seems that both arm64 and sparc64's JIT handle the above
> situation improperly.
>
> They both work by recording the instruction offsets in an array which
> is indexed off by one.  It it built like this:
>
> 	for (i = 0; i < prog->len; i++) {
> 		const struct bpf_insn *insn = &prog->insnsi[i];
> 		int ret;
>
> 		ret = build_insn(insn, ctx);
> 		ctx->offset[i] = ctx->idx;
>
> 		if (ret > 0) {
> 			i++;
> 			continue;
> 		}
> 		if (ret)
> 			return ret;
> 	}
>
> That is, we record the JIT'd instruction offset for BPF instruction
> 'idx' in array entry 'idx - 1'.
>
> Then when we emit a relative branch, we lookup the destination offset
> using "ctx->offset[this_insn_idx + insn->off]"
>
> And this works most of the time.  It doesn't work for the scenerio
> above, because 'idx - 1' is not necessarily the index of the previous
> BPF instruction.  Instead, that might point to the second half of an
> lddimm64 instruction.
>
> This bug was introduced by commit
> 8eee539ddea09bccae2426f09b0ba6a18b72b691 ("arm64: bpf: fix
> out-of-bounds read in bpf2a64_offset()") and I copied the logic into
> sparc64 :-)

I'll take a look at the arm64 one since I have a node at hand, and add
tests into lib/test_bpf.c as well later today.