[RFC][PATCH bpf 1/2] bpf: allow 64-bit offsets for bpf function calls

[RFC][PATCH bpf 1/2] bpf: allow 64-bit offsets for bpf function calls

[Sandipan Das]

The imm field of a bpf_insn is a signed 32-bit integer. For
JIT-ed bpf-to-bpf function calls, it stores the offset from
__bpf_call_base to the start of the callee function.

For some architectures, such as powerpc64, it was found that
this offset may be as large as 64 bits because of which this
cannot be accomodated in the imm field without truncation.

To resolve this, we additionally use the aux data within each
bpf_prog associated with the caller functions to store the
addresses of their respective callees.

Signed-off-by: Sandipan Das <sandipan@linux.vnet.ibm.com>
---
 kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++-
 1 file changed, 38 insertions(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 5fb69a85d967..52088b4ca02f 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5282,6 +5282,19 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 	 * run last pass of JIT
 	 */
 	for (i = 0; i <= env->subprog_cnt; i++) {
+		u32 flen = func[i]->len, callee_cnt = 0;
+		struct bpf_prog **callee;
+
+		/* for now assume that the maximum number of bpf function
+		 * calls that can be made by a caller must be at most the
+		 * number of bpf instructions in that function
+		 */
+		callee = kzalloc(sizeof(func[i]) * flen, GFP_KERNEL);
+		if (!callee) {
+			err = -ENOMEM;
+			goto out_free;
+		}
+
 		insn = func[i]->insnsi;
 		for (j = 0; j < func[i]->len; j++, insn++) {
 			if (insn->code != (BPF_JMP | BPF_CALL) ||
@@ -5292,6 +5305,26 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 			insn->imm = (u64 (*)(u64, u64, u64, u64, u64))
 				func[subprog]->bpf_func -
 				__bpf_call_base;
+
+			/* the offset to the callee from __bpf_call_base
+			 * may be larger than what the 32 bit integer imm
+			 * can accomodate which will truncate the higher
+			 * order bits
+			 *
+			 * to avoid this, we additionally utilize the aux
+			 * data of each caller function for storing the
+			 * addresses of every callee associated with it
+			 */
+			callee[callee_cnt++] = func[subprog];
+		}
+
+		/* free up callee list if no function calls were made */
+		if (!callee_cnt) {
+			kfree(callee);
+			callee = NULL;
+		} else {
+			func[i]->aux->func = callee;
+			func[i]->aux->func_cnt = callee_cnt;
 		}
 	}
 	for (i = 0; i <= env->subprog_cnt; i++) {
@@ -5338,8 +5371,12 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 	return 0;
 out_free:
 	for (i = 0; i <= env->subprog_cnt; i++)
-		if (func[i])
+		if (func[i]) {
+			/* cleanup callee list */
+			if (func[i]->aux->func)
+				kfree(func[i]->aux->func);
 			bpf_jit_free(func[i]);
+		}
 	kfree(func);
 	/* cleanup main prog to be interpreted */
 	prog->jit_requested = 0;
-- 
2.14.3

[RFC][PATCH bpf 2/2] bpf: powerpc64: add JIT support for multi-function programs

[Sandipan Das]

This adds support for bpf-to-bpf function calls for the powerpc64
JIT compiler. After a round of the usual JIT passes, the offsets
to callee functions from __bpf_call_base are known. To update the
target addresses for the branch instructions associated with each
BPF_CALL, an extra pass is performed.

Since it is seen that the offsets may be as large as 64 bits for
powerpc64, we use the aux data associated with each caller to get
the correct branch target address rather than using the imm field
of the BPF_CALL instruction.

Signed-off-by: Sandipan Das <sandipan@linux.vnet.ibm.com>
---
 arch/powerpc/net/bpf_jit_comp64.c | 77 ++++++++++++++++++++++++++++++++++-----
 1 file changed, 67 insertions(+), 10 deletions(-)

diff --git a/arch/powerpc/net/bpf_jit_comp64.c b/arch/powerpc/net/bpf_jit_comp64.c
index 0a34b0cec7b7..f31f22c8cb0b 100644
--- a/arch/powerpc/net/bpf_jit_comp64.c
+++ b/arch/powerpc/net/bpf_jit_comp64.c
@@ -290,7 +290,7 @@ static void bpf_jit_emit_tail_call(u32 *image, struct codegen_context *ctx, u32
 /* Assemble the body code between the prologue & epilogue */
 static int bpf_jit_build_body(struct bpf_prog *fp, u32 *image,
 			      struct codegen_context *ctx,
-			      u32 *addrs)
+			      u32 *addrs, bool extra_pass)
 {
 	const struct bpf_insn *insn = fp->insnsi;
 	int flen = fp->len;
@@ -299,6 +299,10 @@ static int bpf_jit_build_body(struct bpf_prog *fp, u32 *image,
 	/* Start of epilogue code - will only be valid 2nd pass onwards */
 	u32 exit_addr = addrs[flen];
 
+	/* List of callee functions - will only be valid for the extra pass */
+	struct bpf_prog **callee = fp->aux->func;
+	u32 callee_cnt = fp->aux->func_cnt, callee_idx = 0;
+
 	for (i = 0; i < flen; i++) {
 		u32 code = insn[i].code;
 		u32 dst_reg = b2p[insn[i].dst_reg];
@@ -746,11 +750,17 @@ static int bpf_jit_build_body(struct bpf_prog *fp, u32 *image,
 			break;
 
 		/*
-		 * Call kernel helper
+		 * Call kernel helper or bpf function
 		 */
 		case BPF_JMP | BPF_CALL:
 			ctx->seen |= SEEN_FUNC;
-			func = (u8 *) __bpf_call_base + imm;
+			if (insn[i].src_reg == BPF_PSEUDO_CALL && extra_pass)
+				if (callee && callee_idx < callee_cnt)
+					func = (u8 *) callee[callee_idx++]->bpf_func;
+				else
+					return -EINVAL;
+			else
+				func = (u8 *) __bpf_call_base + imm;
 
 			/* Save skb pointer if we need to re-cache skb data */
 			if ((ctx->seen & SEEN_SKB) &&
@@ -970,6 +980,14 @@ static int bpf_jit_build_body(struct bpf_prog *fp, u32 *image,
 	return 0;
 }
 
+struct powerpc64_jit_data {
+	struct bpf_binary_header *header;
+	u32 *addrs;
+	u8 *image;
+	u32 proglen;
+	struct codegen_context ctx;
+};
+
 struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *fp)
 {
 	u32 proglen;
@@ -977,6 +995,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *fp)
 	u8 *image = NULL;
 	u32 *code_base;
 	u32 *addrs;
+	struct powerpc64_jit_data *jit_data;
 	struct codegen_context cgctx;
 	int pass;
 	int flen;
@@ -984,6 +1003,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *fp)
 	struct bpf_prog *org_fp = fp;
 	struct bpf_prog *tmp_fp;
 	bool bpf_blinded = false;
+	bool extra_pass = false;
 
 	if (!fp->jit_requested)
 		return org_fp;
@@ -997,7 +1017,28 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *fp)
 		fp = tmp_fp;
 	}
 
+	jit_data = fp->aux->jit_data;
+	if (!jit_data) {
+		jit_data = kzalloc(sizeof(*jit_data), GFP_KERNEL);
+		if (!jit_data) {
+			fp = org_fp;
+			goto out;
+		}
+		fp->aux->jit_data = jit_data;
+	}
+
 	flen = fp->len;
+	addrs = jit_data->addrs;
+	if (addrs) {
+		cgctx = jit_data->ctx;
+		image = jit_data->image;
+		bpf_hdr = jit_data->header;
+		proglen = jit_data->proglen;
+		alloclen = proglen + FUNCTION_DESCR_SIZE;
+		extra_pass = true;
+		goto skip_init_ctx;
+	}
+
 	addrs = kzalloc((flen+1) * sizeof(*addrs), GFP_KERNEL);
 	if (addrs == NULL) {
 		fp = org_fp;
@@ -1010,10 +1051,10 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *fp)
 	cgctx.stack_size = round_up(fp->aux->stack_depth, 16);
 
 	/* Scouting faux-generate pass 0 */
-	if (bpf_jit_build_body(fp, 0, &cgctx, addrs)) {
+	if (bpf_jit_build_body(fp, 0, &cgctx, addrs, false)) {
 		/* We hit something illegal or unsupported. */
 		fp = org_fp;
-		goto out;
+		goto out_addrs;
 	}
 
 	/*
@@ -1031,9 +1072,10 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *fp)
 			bpf_jit_fill_ill_insns);
 	if (!bpf_hdr) {
 		fp = org_fp;
-		goto out;
+		goto out_addrs;
 	}
 
+skip_init_ctx:
 	code_base = (u32 *)(image + FUNCTION_DESCR_SIZE);
 
 	/* Code generation passes 1-2 */
@@ -1041,7 +1083,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *fp)
 		/* Now build the prologue, body code & epilogue for real. */
 		cgctx.idx = 0;
 		bpf_jit_build_prologue(code_base, &cgctx);
-		bpf_jit_build_body(fp, code_base, &cgctx, addrs);
+		bpf_jit_build_body(fp, code_base, &cgctx, addrs, extra_pass);
 		bpf_jit_build_epilogue(code_base, &cgctx);
 
 		if (bpf_jit_enable > 1)
@@ -1062,15 +1104,30 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *fp)
 	((u64 *)image)[1] = local_paca->kernel_toc;
 #endif
 
+	bpf_flush_icache(bpf_hdr, (u8 *)bpf_hdr + (bpf_hdr->pages * PAGE_SIZE));
+
+	if (!fp->is_func || extra_pass) {
+		bpf_jit_binary_lock_ro(bpf_hdr);
+	} else {
+		jit_data->addrs = addrs;
+		jit_data->ctx = cgctx;
+		jit_data->proglen = proglen;
+		jit_data->image = image;
+		jit_data->header = bpf_hdr;
+	}
+
 	fp->bpf_func = (void *)image;
 	fp->jited = 1;
 	fp->jited_len = alloclen;
 
-	bpf_flush_icache(bpf_hdr, (u8 *)bpf_hdr + (bpf_hdr->pages * PAGE_SIZE));
+	if (!fp->is_func || extra_pass) {
+out_addrs:
+		kfree(addrs);
+		kfree(jit_data);
+		fp->aux->jit_data = NULL;
+	}
 
 out:
-	kfree(addrs);
-
 	if (bpf_blinded)
 		bpf_jit_prog_release_other(fp, fp == org_fp ? tmp_fp : org_fp);
 
-- 
2.14.3

Re: [RFC][PATCH bpf 1/2] bpf: allow 64-bit offsets for bpf function calls

[Alexei Starovoitov]

On 2/8/18 4:03 AM, Sandipan Das wrote:
> The imm field of a bpf_insn is a signed 32-bit integer. For
> JIT-ed bpf-to-bpf function calls, it stores the offset from
> __bpf_call_base to the start of the callee function.
>
> For some architectures, such as powerpc64, it was found that
> this offset may be as large as 64 bits because of which this
> cannot be accomodated in the imm field without truncation.
>
> To resolve this, we additionally use the aux data within each
> bpf_prog associated with the caller functions to store the
> addresses of their respective callees.
>
> Signed-off-by: Sandipan Das <sandipan@linux.vnet.ibm.com>
> ---
>  kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 38 insertions(+), 1 deletion(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 5fb69a85d967..52088b4ca02f 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -5282,6 +5282,19 @@ static int jit_subprogs(struct bpf_verifier_env *env)
>  	 * run last pass of JIT
>  	 */
>  	for (i = 0; i <= env->subprog_cnt; i++) {
> +		u32 flen = func[i]->len, callee_cnt = 0;
> +		struct bpf_prog **callee;
> +
> +		/* for now assume that the maximum number of bpf function
> +		 * calls that can be made by a caller must be at most the
> +		 * number of bpf instructions in that function
> +		 */
> +		callee = kzalloc(sizeof(func[i]) * flen, GFP_KERNEL);
> +		if (!callee) {
> +			err = -ENOMEM;
> +			goto out_free;
> +		}
> +
>  		insn = func[i]->insnsi;
>  		for (j = 0; j < func[i]->len; j++, insn++) {
>  			if (insn->code != (BPF_JMP | BPF_CALL) ||
> @@ -5292,6 +5305,26 @@ static int jit_subprogs(struct bpf_verifier_env *env)
>  			insn->imm = (u64 (*)(u64, u64, u64, u64, u64))
>  				func[subprog]->bpf_func -
>  				__bpf_call_base;
> +
> +			/* the offset to the callee from __bpf_call_base
> +			 * may be larger than what the 32 bit integer imm
> +			 * can accomodate which will truncate the higher
> +			 * order bits
> +			 *
> +			 * to avoid this, we additionally utilize the aux
> +			 * data of each caller function for storing the
> +			 * addresses of every callee associated with it
> +			 */
> +			callee[callee_cnt++] = func[subprog];

can you share typical /proc/kallsyms ?
Are you saying that kernel and kernel modules are allocated from
address spaces that are always more than 32-bit apart?
That would mean that all kernel calls into modules are far calls
and the other way around form .ko into kernel?
Performance is probably suffering because every call needs to be built
with full 64-bit offset. No ?

Re: [RFC][PATCH bpf 1/2] bpf: allow 64-bit offsets for bpf function calls

[Naveen N. Rao]

Alexei Starovoitov wrote:
> On 2/8/18 4:03 AM, Sandipan Das wrote:
>> The imm field of a bpf_insn is a signed 32-bit integer. For
>> JIT-ed bpf-to-bpf function calls, it stores the offset from
>> __bpf_call_base to the start of the callee function.
>>
>> For some architectures, such as powerpc64, it was found that
>> this offset may be as large as 64 bits because of which this
>> cannot be accomodated in the imm field without truncation.
>>
>> To resolve this, we additionally use the aux data within each
>> bpf_prog associated with the caller functions to store the
>> addresses of their respective callees.
>>
>> Signed-off-by: Sandipan Das <sandipan@linux.vnet.ibm.com>
>> ---
>>  kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++-
>>  1 file changed, 38 insertions(+), 1 deletion(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 5fb69a85d967..52088b4ca02f 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -5282,6 +5282,19 @@ static int jit_subprogs(struct bpf_verifier_env *env)
>>  	 * run last pass of JIT
>>  	 */
>>  	for (i = 0; i <= env->subprog_cnt; i++) {
>> +		u32 flen = func[i]->len, callee_cnt = 0;
>> +		struct bpf_prog **callee;
>> +
>> +		/* for now assume that the maximum number of bpf function
>> +		 * calls that can be made by a caller must be at most the
>> +		 * number of bpf instructions in that function
>> +		 */
>> +		callee = kzalloc(sizeof(func[i]) * flen, GFP_KERNEL);
>> +		if (!callee) {
>> +			err = -ENOMEM;
>> +			goto out_free;
>> +		}
>> +
>>  		insn = func[i]->insnsi;
>>  		for (j = 0; j < func[i]->len; j++, insn++) {
>>  			if (insn->code != (BPF_JMP | BPF_CALL) ||
>> @@ -5292,6 +5305,26 @@ static int jit_subprogs(struct bpf_verifier_env *env)
>>  			insn->imm = (u64 (*)(u64, u64, u64, u64, u64))
>>  				func[subprog]->bpf_func -
>>  				__bpf_call_base;
>> +
>> +			/* the offset to the callee from __bpf_call_base
>> +			 * may be larger than what the 32 bit integer imm
>> +			 * can accomodate which will truncate the higher
>> +			 * order bits
>> +			 *
>> +			 * to avoid this, we additionally utilize the aux
>> +			 * data of each caller function for storing the
>> +			 * addresses of every callee associated with it
>> +			 */
>> +			callee[callee_cnt++] = func[subprog];
> 
> can you share typical /proc/kallsyms ?
> Are you saying that kernel and kernel modules are allocated from
> address spaces that are always more than 32-bit apart?

Yes. On ppc64, kernel text is linearly mapped from 0xc000000000000000, 
while vmalloc'ed area starts from 0xd000000000000000 (for radix, this is
different, but still beyond a 32-bit offset).

> That would mean that all kernel calls into modules are far calls
> and the other way around form .ko into kernel?
> Performance is probably suffering because every call needs to be built
> with full 64-bit offset. No ?

Possibly, and I think Michael can give a better perspective, but I think
this is due to our ABI. For inter-module calls, we need to setup the TOC
pointer (or the address of the function being called with ABIv2), which 
would require us to load a full address regardless.

- Naveen

Re: [RFC][PATCH bpf 1/2] bpf: allow 64-bit offsets for bpf function calls

[Naveen N. Rao]

Alexei Starovoitov wrote:
> On 2/8/18 4:03 AM, Sandipan Das wrote:
>> The imm field of a bpf_insn is a signed 32-bit integer. For
>> JIT-ed bpf-to-bpf function calls, it stores the offset from
>> __bpf_call_base to the start of the callee function.
>>
>> For some architectures, such as powerpc64, it was found that
>> this offset may be as large as 64 bits because of which this
>> cannot be accomodated in the imm field without truncation.
>>
>> To resolve this, we additionally use the aux data within each
>> bpf_prog associated with the caller functions to store the
>> addresses of their respective callees.
>>
>> Signed-off-by: Sandipan Das <sandipan@linux.vnet.ibm.com>
>> ---
>>  kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++-
>>  1 file changed, 38 insertions(+), 1 deletion(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 5fb69a85d967..52088b4ca02f 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -5282,6 +5282,19 @@ static int jit_subprogs(struct bpf_verifier_env *=
env)
>>  	 * run last pass of JIT
>>  	 */
>>  	for (i =3D 0; i <=3D env->subprog_cnt; i++) {
>> +		u32 flen =3D func[i]->len, callee_cnt =3D 0;
>> +		struct bpf_prog **callee;
>> +
>> +		/* for now assume that the maximum number of bpf function
>> +		 * calls that can be made by a caller must be at most the
>> +		 * number of bpf instructions in that function
>> +		 */
>> +		callee =3D kzalloc(sizeof(func[i]) * flen, GFP_KERNEL);
>> +		if (!callee) {
>> +			err =3D -ENOMEM;
>> +			goto out_free;
>> +		}
>> +
>>  		insn =3D func[i]->insnsi;
>>  		for (j =3D 0; j < func[i]->len; j++, insn++) {
>>  			if (insn->code !=3D (BPF_JMP | BPF_CALL) ||
>> @@ -5292,6 +5305,26 @@ static int jit_subprogs(struct bpf_verifier_env *=
env)
>>  			insn->imm =3D (u64 (*)(u64, u64, u64, u64, u64))
>>  				func[subprog]->bpf_func -
>>  				__bpf_call_base;
>> +
>> +			/* the offset to the callee from __bpf_call_base
>> +			 * may be larger than what the 32 bit integer imm
>> +			 * can accomodate which will truncate the higher
>> +			 * order bits
>> +			 *
>> +			 * to avoid this, we additionally utilize the aux
>> +			 * data of each caller function for storing the
>> +			 * addresses of every callee associated with it
>> +			 */
>> +			callee[callee_cnt++] =3D func[subprog];
>=20
> can you share typical /proc/kallsyms ?
> Are you saying that kernel and kernel modules are allocated from
> address spaces that are always more than 32-bit apart?

Yes. On ppc64, kernel text is linearly mapped from 0xc000000000000000,=20
while vmalloc'ed area starts from 0xd000000000000000 (for radix, this is
different, but still beyond a 32-bit offset).

> That would mean that all kernel calls into modules are far calls
> and the other way around form .ko into kernel?
> Performance is probably suffering because every call needs to be built
> with full 64-bit offset. No ?

Possibly, and I think Michael can give a better perspective, but I think
this is due to our ABI. For inter-module calls, we need to setup the TOC
pointer (or the address of the function being called with ABIv2), which=20
would require us to load a full address regardless.

- Naveen

=

Re: [RFC][PATCH bpf 1/2] bpf: allow 64-bit offsets for bpf function calls

[Naveen N. Rao]

Naveen N. Rao wrote:
> Alexei Starovoitov wrote:
>> On 2/8/18 4:03 AM, Sandipan Das wrote:
>>> The imm field of a bpf_insn is a signed 32-bit integer. For
>>> JIT-ed bpf-to-bpf function calls, it stores the offset from
>>> __bpf_call_base to the start of the callee function.
>>>
>>> For some architectures, such as powerpc64, it was found that
>>> this offset may be as large as 64 bits because of which this
>>> cannot be accomodated in the imm field without truncation.
>>>
>>> To resolve this, we additionally use the aux data within each
>>> bpf_prog associated with the caller functions to store the
>>> addresses of their respective callees.
>>>
>>> Signed-off-by: Sandipan Das <sandipan@linux.vnet.ibm.com>
>>> ---
>>>  kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++-
>>>  1 file changed, 38 insertions(+), 1 deletion(-)
>>>
>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>> index 5fb69a85d967..52088b4ca02f 100644
>>> --- a/kernel/bpf/verifier.c
>>> +++ b/kernel/bpf/verifier.c
>>> @@ -5282,6 +5282,19 @@ static int jit_subprogs(struct bpf_verifier_env *env)
>>>  	 * run last pass of JIT
>>>  	 */
>>>  	for (i = 0; i <= env->subprog_cnt; i++) {
>>> +		u32 flen = func[i]->len, callee_cnt = 0;
>>> +		struct bpf_prog **callee;
>>> +
>>> +		/* for now assume that the maximum number of bpf function
>>> +		 * calls that can be made by a caller must be at most the
>>> +		 * number of bpf instructions in that function
>>> +		 */
>>> +		callee = kzalloc(sizeof(func[i]) * flen, GFP_KERNEL);
>>> +		if (!callee) {
>>> +			err = -ENOMEM;
>>> +			goto out_free;
>>> +		}
>>> +
>>>  		insn = func[i]->insnsi;
>>>  		for (j = 0; j < func[i]->len; j++, insn++) {
>>>  			if (insn->code != (BPF_JMP | BPF_CALL) ||
>>> @@ -5292,6 +5305,26 @@ static int jit_subprogs(struct bpf_verifier_env *env)
>>>  			insn->imm = (u64 (*)(u64, u64, u64, u64, u64))
>>>  				func[subprog]->bpf_func -
>>>  				__bpf_call_base;
>>> +
>>> +			/* the offset to the callee from __bpf_call_base
>>> +			 * may be larger than what the 32 bit integer imm
>>> +			 * can accomodate which will truncate the higher
>>> +			 * order bits
>>> +			 *
>>> +			 * to avoid this, we additionally utilize the aux
>>> +			 * data of each caller function for storing the
>>> +			 * addresses of every callee associated with it
>>> +			 */
>>> +			callee[callee_cnt++] = func[subprog];
>> 
>> can you share typical /proc/kallsyms ?
>> Are you saying that kernel and kernel modules are allocated from
>> address spaces that are always more than 32-bit apart?
> 
> Yes. On ppc64, kernel text is linearly mapped from 0xc000000000000000, 
> while vmalloc'ed area starts from 0xd000000000000000 (for radix, this is
> different, but still beyond a 32-bit offset).
> 
>> That would mean that all kernel calls into modules are far calls
>> and the other way around form .ko into kernel?
>> Performance is probably suffering because every call needs to be built
>> with full 64-bit offset. No ?
> 
> Possibly, and I think Michael can give a better perspective, but I think
> this is due to our ABI. For inter-module calls, we need to setup the TOC
> pointer (or the address of the function being called with ABIv2), which 
> would require us to load a full address regardless.

Thinking more about this, as an optimization, for bpf-to-bpf calls, we 
could detect a near call and just emit a relative branch since we don't 
care about TOC with BPF. But, this will depend on whether the different 
BPF functions are close enough (within 32MB) of one another.

We can attempt that once the generic changes are finalized on.

Thanks,
Naveen

Re: [RFC][PATCH bpf 1/2] bpf: allow 64-bit offsets for bpf function calls

[Naveen N. Rao]

Naveen N. Rao wrote:
> Alexei Starovoitov wrote:
>> On 2/8/18 4:03 AM, Sandipan Das wrote:
>>> The imm field of a bpf_insn is a signed 32-bit integer. For
>>> JIT-ed bpf-to-bpf function calls, it stores the offset from
>>> __bpf_call_base to the start of the callee function.
>>>
>>> For some architectures, such as powerpc64, it was found that
>>> this offset may be as large as 64 bits because of which this
>>> cannot be accomodated in the imm field without truncation.
>>>
>>> To resolve this, we additionally use the aux data within each
>>> bpf_prog associated with the caller functions to store the
>>> addresses of their respective callees.
>>>
>>> Signed-off-by: Sandipan Das <sandipan@linux.vnet.ibm.com>
>>> ---
>>>  kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++-
>>>  1 file changed, 38 insertions(+), 1 deletion(-)
>>>
>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>> index 5fb69a85d967..52088b4ca02f 100644
>>> --- a/kernel/bpf/verifier.c
>>> +++ b/kernel/bpf/verifier.c
>>> @@ -5282,6 +5282,19 @@ static int jit_subprogs(struct bpf_verifier_env =
*env)
>>>  	 * run last pass of JIT
>>>  	 */
>>>  	for (i =3D 0; i <=3D env->subprog_cnt; i++) {
>>> +		u32 flen =3D func[i]->len, callee_cnt =3D 0;
>>> +		struct bpf_prog **callee;
>>> +
>>> +		/* for now assume that the maximum number of bpf function
>>> +		 * calls that can be made by a caller must be at most the
>>> +		 * number of bpf instructions in that function
>>> +		 */
>>> +		callee =3D kzalloc(sizeof(func[i]) * flen, GFP_KERNEL);
>>> +		if (!callee) {
>>> +			err =3D -ENOMEM;
>>> +			goto out_free;
>>> +		}
>>> +
>>>  		insn =3D func[i]->insnsi;
>>>  		for (j =3D 0; j < func[i]->len; j++, insn++) {
>>>  			if (insn->code !=3D (BPF_JMP | BPF_CALL) ||
>>> @@ -5292,6 +5305,26 @@ static int jit_subprogs(struct bpf_verifier_env =
*env)
>>>  			insn->imm =3D (u64 (*)(u64, u64, u64, u64, u64))
>>>  				func[subprog]->bpf_func -
>>>  				__bpf_call_base;
>>> +
>>> +			/* the offset to the callee from __bpf_call_base
>>> +			 * may be larger than what the 32 bit integer imm
>>> +			 * can accomodate which will truncate the higher
>>> +			 * order bits
>>> +			 *
>>> +			 * to avoid this, we additionally utilize the aux
>>> +			 * data of each caller function for storing the
>>> +			 * addresses of every callee associated with it
>>> +			 */
>>> +			callee[callee_cnt++] =3D func[subprog];
>>=20
>> can you share typical /proc/kallsyms ?
>> Are you saying that kernel and kernel modules are allocated from
>> address spaces that are always more than 32-bit apart?
>=20
> Yes. On ppc64, kernel text is linearly mapped from 0xc000000000000000,=20
> while vmalloc'ed area starts from 0xd000000000000000 (for radix, this is
> different, but still beyond a 32-bit offset).
>=20
>> That would mean that all kernel calls into modules are far calls
>> and the other way around form .ko into kernel?
>> Performance is probably suffering because every call needs to be built
>> with full 64-bit offset. No ?
>=20
> Possibly, and I think Michael can give a better perspective, but I think
> this is due to our ABI. For inter-module calls, we need to setup the TOC
> pointer (or the address of the function being called with ABIv2), which=20
> would require us to load a full address regardless.

Thinking more about this, as an optimization, for bpf-to-bpf calls, we=20
could detect a near call and just emit a relative branch since we don't=20
care about TOC with BPF. But, this will depend on whether the different=20
BPF functions are close enough (within 32MB) of one another.

We can attempt that once the generic changes are finalized on.

Thanks,
Naveen

=

Re: [RFC][PATCH bpf 1/2] bpf: allow 64-bit offsets for bpf function calls

[Alexei Starovoitov]

On 2/9/18 8:54 AM, Naveen N. Rao wrote:
> Naveen N. Rao wrote:
>> Alexei Starovoitov wrote:
>>> On 2/8/18 4:03 AM, Sandipan Das wrote:
>>>> The imm field of a bpf_insn is a signed 32-bit integer. For
>>>> JIT-ed bpf-to-bpf function calls, it stores the offset from
>>>> __bpf_call_base to the start of the callee function.
>>>>
>>>> For some architectures, such as powerpc64, it was found that
>>>> this offset may be as large as 64 bits because of which this
>>>> cannot be accomodated in the imm field without truncation.
>>>>
>>>> To resolve this, we additionally use the aux data within each
>>>> bpf_prog associated with the caller functions to store the
>>>> addresses of their respective callees.
>>>>
>>>> Signed-off-by: Sandipan Das <sandipan@linux.vnet.ibm.com>
>>>> ---
>>>>  kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++-
>>>>  1 file changed, 38 insertions(+), 1 deletion(-)
>>>>
>>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>>> index 5fb69a85d967..52088b4ca02f 100644
>>>> --- a/kernel/bpf/verifier.c
>>>> +++ b/kernel/bpf/verifier.c
>>>> @@ -5282,6 +5282,19 @@ static int jit_subprogs(struct
>>>> bpf_verifier_env *env)
>>>>       * run last pass of JIT
>>>>       */
>>>>      for (i = 0; i <= env->subprog_cnt; i++) {
>>>> +        u32 flen = func[i]->len, callee_cnt = 0;
>>>> +        struct bpf_prog **callee;
>>>> +
>>>> +        /* for now assume that the maximum number of bpf function
>>>> +         * calls that can be made by a caller must be at most the
>>>> +         * number of bpf instructions in that function
>>>> +         */
>>>> +        callee = kzalloc(sizeof(func[i]) * flen, GFP_KERNEL);
>>>> +        if (!callee) {
>>>> +            err = -ENOMEM;
>>>> +            goto out_free;
>>>> +        }
>>>> +
>>>>          insn = func[i]->insnsi;
>>>>          for (j = 0; j < func[i]->len; j++, insn++) {
>>>>              if (insn->code != (BPF_JMP | BPF_CALL) ||
>>>> @@ -5292,6 +5305,26 @@ static int jit_subprogs(struct
>>>> bpf_verifier_env *env)
>>>>              insn->imm = (u64 (*)(u64, u64, u64, u64, u64))
>>>>                  func[subprog]->bpf_func -
>>>>                  __bpf_call_base;
>>>> +
>>>> +            /* the offset to the callee from __bpf_call_base
>>>> +             * may be larger than what the 32 bit integer imm
>>>> +             * can accomodate which will truncate the higher
>>>> +             * order bits
>>>> +             *
>>>> +             * to avoid this, we additionally utilize the aux
>>>> +             * data of each caller function for storing the
>>>> +             * addresses of every callee associated with it
>>>> +             */
>>>> +            callee[callee_cnt++] = func[subprog];
>>>
>>> can you share typical /proc/kallsyms ?
>>> Are you saying that kernel and kernel modules are allocated from
>>> address spaces that are always more than 32-bit apart?
>>
>> Yes. On ppc64, kernel text is linearly mapped from 0xc000000000000000,
>> while vmalloc'ed area starts from 0xd000000000000000 (for radix, this is
>> different, but still beyond a 32-bit offset).
>>
>>> That would mean that all kernel calls into modules are far calls
>>> and the other way around form .ko into kernel?
>>> Performance is probably suffering because every call needs to be built
>>> with full 64-bit offset. No ?
>>
>> Possibly, and I think Michael can give a better perspective, but I think
>> this is due to our ABI. For inter-module calls, we need to setup the TOC
>> pointer (or the address of the function being called with ABIv2),
>> which would require us to load a full address regardless.
>
> Thinking more about this, as an optimization, for bpf-to-bpf calls, we
> could detect a near call and just emit a relative branch since we don't
> care about TOC with BPF. But, this will depend on whether the different
> BPF functions are close enough (within 32MB) of one another.

so that will be just an optimization. Understood.
How about instead of doing callee = kzalloc(sizeof(func[i]) * flen..
we keep  insn->off pointing to subprog and move
prog->aux->func = func;
before the last JIT pass.
Then you won't need to alloc this extra array.

Re: [RFC][PATCH bpf 1/2] bpf: allow 64-bit offsets for bpf function calls

[Sandipan Das]

On 02/10/2018 06:08 AM, Alexei Starovoitov wrote:
> On 2/9/18 8:54 AM, Naveen N. Rao wrote:
>> Naveen N. Rao wrote:
>>> Alexei Starovoitov wrote:
>>>> On 2/8/18 4:03 AM, Sandipan Das wrote:
>>>>> The imm field of a bpf_insn is a signed 32-bit integer. For
>>>>> JIT-ed bpf-to-bpf function calls, it stores the offset from
>>>>> __bpf_call_base to the start of the callee function.
>>>>>
>>>>> For some architectures, such as powerpc64, it was found that
>>>>> this offset may be as large as 64 bits because of which this
>>>>> cannot be accomodated in the imm field without truncation.
>>>>>
>>>>> To resolve this, we additionally use the aux data within each
>>>>> bpf_prog associated with the caller functions to store the
>>>>> addresses of their respective callees.
>>>>>
>>>>> Signed-off-by: Sandipan Das <sandipan@linux.vnet.ibm.com>
>>>>> ---
>>>>>  kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++-
>>>>>  1 file changed, 38 insertions(+), 1 deletion(-)
>>>>>
>>>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>>>> index 5fb69a85d967..52088b4ca02f 100644
>>>>> --- a/kernel/bpf/verifier.c
>>>>> +++ b/kernel/bpf/verifier.c
>>>>> @@ -5282,6 +5282,19 @@ static int jit_subprogs(struct
>>>>> bpf_verifier_env *env)
>>>>>       * run last pass of JIT
>>>>>       */
>>>>>      for (i = 0; i <= env->subprog_cnt; i++) {
>>>>> +        u32 flen = func[i]->len, callee_cnt = 0;
>>>>> +        struct bpf_prog **callee;
>>>>> +
>>>>> +        /* for now assume that the maximum number of bpf function
>>>>> +         * calls that can be made by a caller must be at most the
>>>>> +         * number of bpf instructions in that function
>>>>> +         */
>>>>> +        callee = kzalloc(sizeof(func[i]) * flen, GFP_KERNEL);
>>>>> +        if (!callee) {
>>>>> +            err = -ENOMEM;
>>>>> +            goto out_free;
>>>>> +        }
>>>>> +
>>>>>          insn = func[i]->insnsi;
>>>>>          for (j = 0; j < func[i]->len; j++, insn++) {
>>>>>              if (insn->code != (BPF_JMP | BPF_CALL) ||
>>>>> @@ -5292,6 +5305,26 @@ static int jit_subprogs(struct
>>>>> bpf_verifier_env *env)
>>>>>              insn->imm = (u64 (*)(u64, u64, u64, u64, u64))
>>>>>                  func[subprog]->bpf_func -
>>>>>                  __bpf_call_base;
>>>>> +
>>>>> +            /* the offset to the callee from __bpf_call_base
>>>>> +             * may be larger than what the 32 bit integer imm
>>>>> +             * can accomodate which will truncate the higher
>>>>> +             * order bits
>>>>> +             *
>>>>> +             * to avoid this, we additionally utilize the aux
>>>>> +             * data of each caller function for storing the
>>>>> +             * addresses of every callee associated with it
>>>>> +             */
>>>>> +            callee[callee_cnt++] = func[subprog];
>>>>
>>>> can you share typical /proc/kallsyms ?
>>>> Are you saying that kernel and kernel modules are allocated from
>>>> address spaces that are always more than 32-bit apart?
>>>
>>> Yes. On ppc64, kernel text is linearly mapped from 0xc000000000000000,
>>> while vmalloc'ed area starts from 0xd000000000000000 (for radix, this is
>>> different, but still beyond a 32-bit offset).
>>>
>>>> That would mean that all kernel calls into modules are far calls
>>>> and the other way around form .ko into kernel?
>>>> Performance is probably suffering because every call needs to be built
>>>> with full 64-bit offset. No ?
>>>
>>> Possibly, and I think Michael can give a better perspective, but I think
>>> this is due to our ABI. For inter-module calls, we need to setup the TOC
>>> pointer (or the address of the function being called with ABIv2),
>>> which would require us to load a full address regardless.
>>
>> Thinking more about this, as an optimization, for bpf-to-bpf calls, we
>> could detect a near call and just emit a relative branch since we don't
>> care about TOC with BPF. But, this will depend on whether the different
>> BPF functions are close enough (within 32MB) of one another.
> 
> so that will be just an optimization. Understood.
> How about instead of doing callee = kzalloc(sizeof(func[i]) * flen..
> we keep  insn->off pointing to subprog and move
> prog->aux->func = func;
> before the last JIT pass.
> Then you won't need to alloc this extra array.
> 

Agreed. Will make the necessary changes in v2.

Re: [RFC][PATCH bpf 1/2] bpf: allow 64-bit offsets for bpf function calls

[Sandipan Das]

On 02/10/2018 06:08 AM, Alexei Starovoitov wrote:
> On 2/9/18 8:54 AM, Naveen N. Rao wrote:
>> Naveen N. Rao wrote:
>>> Alexei Starovoitov wrote:
>>>> On 2/8/18 4:03 AM, Sandipan Das wrote:
>>>>> The imm field of a bpf_insn is a signed 32-bit integer. For
>>>>> JIT-ed bpf-to-bpf function calls, it stores the offset from
>>>>> __bpf_call_base to the start of the callee function.
>>>>>
>>>>> For some architectures, such as powerpc64, it was found that
>>>>> this offset may be as large as 64 bits because of which this
>>>>> cannot be accomodated in the imm field without truncation.
>>>>>
>>>>> To resolve this, we additionally use the aux data within each
>>>>> bpf_prog associated with the caller functions to store the
>>>>> addresses of their respective callees.
>>>>>
>>>>> Signed-off-by: Sandipan Das <sandipan@linux.vnet.ibm.com>
>>>>> ---
>>>>>  kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++-
>>>>>  1 file changed, 38 insertions(+), 1 deletion(-)
>>>>>
>>>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>>>> index 5fb69a85d967..52088b4ca02f 100644
>>>>> --- a/kernel/bpf/verifier.c
>>>>> +++ b/kernel/bpf/verifier.c
>>>>> @@ -5282,6 +5282,19 @@ static int jit_subprogs(struct
>>>>> bpf_verifier_env *env)
>>>>>       * run last pass of JIT
>>>>>       */
>>>>>      for (i = 0; i <= env->subprog_cnt; i++) {
>>>>> +        u32 flen = func[i]->len, callee_cnt = 0;
>>>>> +        struct bpf_prog **callee;
>>>>> +
>>>>> +        /* for now assume that the maximum number of bpf function
>>>>> +         * calls that can be made by a caller must be at most the
>>>>> +         * number of bpf instructions in that function
>>>>> +         */
>>>>> +        callee = kzalloc(sizeof(func[i]) * flen, GFP_KERNEL);
>>>>> +        if (!callee) {
>>>>> +            err = -ENOMEM;
>>>>> +            goto out_free;
>>>>> +        }
>>>>> +
>>>>>          insn = func[i]->insnsi;
>>>>>          for (j = 0; j < func[i]->len; j++, insn++) {
>>>>>              if (insn->code != (BPF_JMP | BPF_CALL) ||
>>>>> @@ -5292,6 +5305,26 @@ static int jit_subprogs(struct
>>>>> bpf_verifier_env *env)
>>>>>              insn->imm = (u64 (*)(u64, u64, u64, u64, u64))
>>>>>                  func[subprog]->bpf_func -
>>>>>                  __bpf_call_base;
>>>>> +
>>>>> +            /* the offset to the callee from __bpf_call_base
>>>>> +             * may be larger than what the 32 bit integer imm
>>>>> +             * can accomodate which will truncate the higher
>>>>> +             * order bits
>>>>> +             *
>>>>> +             * to avoid this, we additionally utilize the aux
>>>>> +             * data of each caller function for storing the
>>>>> +             * addresses of every callee associated with it
>>>>> +             */
>>>>> +            callee[callee_cnt++] = func[subprog];
>>>>
>>>> can you share typical /proc/kallsyms ?
>>>> Are you saying that kernel and kernel modules are allocated from
>>>> address spaces that are always more than 32-bit apart?
>>>
>>> Yes. On ppc64, kernel text is linearly mapped from 0xc000000000000000,
>>> while vmalloc'ed area starts from 0xd000000000000000 (for radix, this is
>>> different, but still beyond a 32-bit offset).
>>>
>>>> That would mean that all kernel calls into modules are far calls
>>>> and the other way around form .ko into kernel?
>>>> Performance is probably suffering because every call needs to be built
>>>> with full 64-bit offset. No ?
>>>
>>> Possibly, and I think Michael can give a better perspective, but I think
>>> this is due to our ABI. For inter-module calls, we need to setup the TOC
>>> pointer (or the address of the function being called with ABIv2),
>>> which would require us to load a full address regardless.
>>
>> Thinking more about this, as an optimization, for bpf-to-bpf calls, we
>> could detect a near call and just emit a relative branch since we don't
>> care about TOC with BPF. But, this will depend on whether the different
>> BPF functions are close enough (within 32MB) of one another.
> 
> so that will be just an optimization. Understood.
> How about instead of doing callee = kzalloc(sizeof(func[i]) * flen..
> we keep  insn->off pointing to subprog and move
> prog->aux->func = func;
> before the last JIT pass.
> Then you won't need to alloc this extra array.
> 

Agreed. Will make the necessary changes in v2.

--
With Regards,
Sandipan