2022-01-22 03:55:19

by Song Liu

[permalink] [raw]
Subject: [PATCH v6 bpf-next 0/7] bpf_prog_pack allocator

Changes v5 => v6:
1. Make jit_hole_buffer 128 byte long. Only fill the first and last 128
bytes of header with INT3. (Alexei)
2. Use kvmalloc for temporary buffer. (Alexei)
3. Rename tmp_header/tmp_image => rw_header/rw_image. Remove tmp_image from
x64_jit_data. (Alexei)
4. Change fall back round_up_to in bpf_jit_binary_alloc_pack() from
BPF_PROG_MAX_PACK_PROG_SIZE to PAGE_SIZE.

Changes v4 => v5:
1. Do not use atomic64 for bpf_jit_current. (Alexei)

Changes v3 => v4:
1. Rename text_poke_jit() => text_poke_copy(). (Peter)
2. Change comment style. (Peter)

Changes v2 => v3:
1. Fix tailcall.

Changes v1 => v2:
1. Use text_poke instead of writing through linear mapping. (Peter)
2. Avoid making changes to non-x86_64 code.

Most BPF programs are small, but they consume a page each. For systems
with busy traffic and many BPF programs, this could also add significant
pressure to instruction TLB.

This set tries to solve this problem with customized allocator that pack
multiple programs into a huge page.

Patches 1-5 prepare the work. Patch 6 contains key logic of the allocator.
Patch 7 uses this allocator in x86_64 jit compiler.

Song Liu (7):
x86/Kconfig: select HAVE_ARCH_HUGE_VMALLOC with HAVE_ARCH_HUGE_VMAP
bpf: use bytes instead of pages for bpf_jit_[charge|uncharge]_modmem
bpf: use size instead of pages in bpf_binary_header
bpf: add a pointer of bpf_binary_header to bpf_prog
x86/alternative: introduce text_poke_copy
bpf: introduce bpf_prog_pack allocator
bpf, x86_64: use bpf_prog_pack allocator

arch/x86/Kconfig | 1 +
arch/x86/include/asm/text-patching.h | 1 +
arch/x86/kernel/alternative.c | 32 ++++
arch/x86/net/bpf_jit_comp.c | 143 ++++++++++++++----
include/linux/bpf.h | 4 +-
include/linux/filter.h | 23 ++-
kernel/bpf/core.c | 210 ++++++++++++++++++++++++---
kernel/bpf/trampoline.c | 6 +-
8 files changed, 363 insertions(+), 57 deletions(-)

--
2.30.2


2022-01-22 03:55:25

by Song Liu

[permalink] [raw]
Subject: [PATCH v6 bpf-next 3/7] bpf: use size instead of pages in bpf_binary_header

From: Song Liu <[email protected]>

This is necessary to charge sub page memory for the BPF program.

Signed-off-by: Song Liu <[email protected]>
---
include/linux/filter.h | 6 +++---
kernel/bpf/core.c | 11 +++++------
2 files changed, 8 insertions(+), 9 deletions(-)

diff --git a/include/linux/filter.h b/include/linux/filter.h
index d23e999dc032..5855eb474c62 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -548,7 +548,7 @@ struct sock_fprog_kern {
#define BPF_IMAGE_ALIGNMENT 8

struct bpf_binary_header {
- u32 pages;
+ u32 size;
u8 image[] __aligned(BPF_IMAGE_ALIGNMENT);
};

@@ -886,8 +886,8 @@ static inline void bpf_prog_lock_ro(struct bpf_prog *fp)
static inline void bpf_jit_binary_lock_ro(struct bpf_binary_header *hdr)
{
set_vm_flush_reset_perms(hdr);
- set_memory_ro((unsigned long)hdr, hdr->pages);
- set_memory_x((unsigned long)hdr, hdr->pages);
+ set_memory_ro((unsigned long)hdr, hdr->size >> PAGE_SHIFT);
+ set_memory_x((unsigned long)hdr, hdr->size >> PAGE_SHIFT);
}

static inline struct bpf_binary_header *
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index b9c6a426a7dd..f252d8529b0b 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -543,7 +543,7 @@ bpf_prog_ksym_set_addr(struct bpf_prog *prog)
WARN_ON_ONCE(!bpf_prog_ebpf_jited(prog));

prog->aux->ksym.start = (unsigned long) prog->bpf_func;
- prog->aux->ksym.end = addr + hdr->pages * PAGE_SIZE;
+ prog->aux->ksym.end = addr + hdr->size;
}

static void
@@ -866,7 +866,7 @@ bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
bpf_jit_fill_hole_t bpf_fill_ill_insns)
{
struct bpf_binary_header *hdr;
- u32 size, hole, start, pages;
+ u32 size, hole, start;

WARN_ON_ONCE(!is_power_of_2(alignment) ||
alignment > BPF_IMAGE_ALIGNMENT);
@@ -876,7 +876,6 @@ bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
* random section of illegal instructions.
*/
size = round_up(proglen + sizeof(*hdr) + 128, PAGE_SIZE);
- pages = size / PAGE_SIZE;

if (bpf_jit_charge_modmem(size))
return NULL;
@@ -889,7 +888,7 @@ bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
/* Fill space with illegal/arch-dep instructions. */
bpf_fill_ill_insns(hdr, size);

- hdr->pages = pages;
+ hdr->size = size;
hole = min_t(unsigned int, size - (proglen + sizeof(*hdr)),
PAGE_SIZE - sizeof(*hdr));
start = (get_random_int() % hole) & ~(alignment - 1);
@@ -902,10 +901,10 @@ bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,

void bpf_jit_binary_free(struct bpf_binary_header *hdr)
{
- u32 pages = hdr->pages;
+ u32 size = hdr->size;

bpf_jit_free_exec(hdr);
- bpf_jit_uncharge_modmem(pages << PAGE_SHIFT);
+ bpf_jit_uncharge_modmem(size);
}

/* This symbol is only overridden by archs that have different
--
2.30.2

2022-01-22 03:55:44

by Song Liu

[permalink] [raw]
Subject: [PATCH v6 bpf-next 4/7] bpf: add a pointer of bpf_binary_header to bpf_prog

With sub page allocation, we cannot simply use bpf_func & PAGE_MASK to
find the bpf_binary_header. Add a pointer to struct bpf_prog to avoid
this logic.

Use this point for x86_64. If the pointer is not set by the jit engine,
fall back to original logic.

Signed-off-by: Song Liu <[email protected]>
---
arch/x86/net/bpf_jit_comp.c | 2 ++
include/linux/filter.h | 10 ++++++++--
2 files changed, 10 insertions(+), 2 deletions(-)

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index ce1f86f245c9..fe4f08e25a1d 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -2339,6 +2339,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
if (header)
bpf_jit_binary_free(header);
prog = orig_prog;
+ header = NULL;
goto out_addrs;
}
if (image) {
@@ -2406,6 +2407,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
if (tmp_blinded)
bpf_jit_prog_release_other(prog, prog == orig_prog ?
tmp : orig_prog);
+ prog->hdr = header;
return prog;
}

diff --git a/include/linux/filter.h b/include/linux/filter.h
index 5855eb474c62..27ea68604c22 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -584,6 +584,7 @@ struct bpf_prog {
const struct bpf_insn *insn);
struct bpf_prog_aux *aux; /* Auxiliary fields */
struct sock_fprog_kern *orig_prog; /* Original BPF program */
+ struct bpf_binary_header *hdr;
/* Instructions for interpreter */
union {
DECLARE_FLEX_ARRAY(struct sock_filter, insns);
@@ -893,9 +894,14 @@ static inline void bpf_jit_binary_lock_ro(struct bpf_binary_header *hdr)
static inline struct bpf_binary_header *
bpf_jit_binary_hdr(const struct bpf_prog *fp)
{
- unsigned long real_start = (unsigned long)fp->bpf_func;
- unsigned long addr = real_start & PAGE_MASK;
+ unsigned long real_start;
+ unsigned long addr;

+ if (fp->hdr)
+ return fp->hdr;
+
+ real_start = (unsigned long)fp->bpf_func;
+ addr = real_start & PAGE_MASK;
return (void *)addr;
}

--
2.30.2

2022-01-22 03:55:55

by Song Liu

[permalink] [raw]
Subject: [PATCH v6 bpf-next 5/7] x86/alternative: introduce text_poke_copy

This will be used by BPF jit compiler to dump JITed binary to a RX huge
page, and thus allow multiple BPF programs sharing the a huge (2MB) page.

Acked-by: Peter Zijlstra (Intel) <[email protected]>
Signed-off-by: Song Liu <[email protected]>
---
arch/x86/include/asm/text-patching.h | 1 +
arch/x86/kernel/alternative.c | 32 ++++++++++++++++++++++++++++
2 files changed, 33 insertions(+)

diff --git a/arch/x86/include/asm/text-patching.h b/arch/x86/include/asm/text-patching.h
index b7421780e4e9..4cc18ba1b75e 100644
--- a/arch/x86/include/asm/text-patching.h
+++ b/arch/x86/include/asm/text-patching.h
@@ -44,6 +44,7 @@ extern void text_poke_early(void *addr, const void *opcode, size_t len);
extern void *text_poke(void *addr, const void *opcode, size_t len);
extern void text_poke_sync(void);
extern void *text_poke_kgdb(void *addr, const void *opcode, size_t len);
+extern void *text_poke_copy(void *addr, const void *opcode, size_t len);
extern int poke_int3_handler(struct pt_regs *regs);
extern void text_poke_bp(void *addr, const void *opcode, size_t len, const void *emulate);

diff --git a/arch/x86/kernel/alternative.c b/arch/x86/kernel/alternative.c
index 23fb4d51a5da..903a415c19fa 100644
--- a/arch/x86/kernel/alternative.c
+++ b/arch/x86/kernel/alternative.c
@@ -1102,6 +1102,38 @@ void *text_poke_kgdb(void *addr, const void *opcode, size_t len)
return __text_poke(addr, opcode, len);
}

+/**
+ * text_poke_copy - Copy instructions into (an unused part of) RX memory
+ * @addr: address to modify
+ * @opcode: source of the copy
+ * @len: length to copy, could be more than 2x PAGE_SIZE
+ *
+ * Not safe against concurrent execution; useful for JITs to dump
+ * new code blocks into unused regions of RX memory. Can be used in
+ * conjunction with synchronize_rcu_tasks() to wait for existing
+ * execution to quiesce after having made sure no existing functions
+ * pointers are live.
+ */
+void *text_poke_copy(void *addr, const void *opcode, size_t len)
+{
+ unsigned long start = (unsigned long)addr;
+ size_t patched = 0;
+
+ if (WARN_ON_ONCE(core_kernel_text(start)))
+ return NULL;
+
+ while (patched < len) {
+ unsigned long ptr = start + patched;
+ size_t s;
+
+ s = min_t(size_t, PAGE_SIZE * 2 - offset_in_page(ptr), len - patched);
+
+ __text_poke((void *)ptr, opcode + patched, s);
+ patched += s;
+ }
+ return addr;
+}
+
static void do_sync_core(void *info)
{
sync_core();
--
2.30.2

2022-01-22 03:56:05

by Song Liu

[permalink] [raw]
Subject: [PATCH v6 bpf-next 1/7] x86/Kconfig: select HAVE_ARCH_HUGE_VMALLOC with HAVE_ARCH_HUGE_VMAP

From: Song Liu <[email protected]>

This enables module_alloc() to allocate huge page for 2MB+ requests.
To check the difference of this change, we need enable config
CONFIG_PTDUMP_DEBUGFS, and call module_alloc(2MB). Before the change,
/sys/kernel/debug/page_tables/kernel shows pte for this map. With the
change, /sys/kernel/debug/page_tables/ show pmd for thie map.

Signed-off-by: Song Liu <[email protected]>
---
arch/x86/Kconfig | 1 +
1 file changed, 1 insertion(+)

diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 8910b09b5601..b5d1582ea848 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -158,6 +158,7 @@ config X86
select HAVE_ALIGNED_STRUCT_PAGE if SLUB
select HAVE_ARCH_AUDITSYSCALL
select HAVE_ARCH_HUGE_VMAP if X86_64 || X86_PAE
+ select HAVE_ARCH_HUGE_VMALLOC if HAVE_ARCH_HUGE_VMAP
select HAVE_ARCH_JUMP_LABEL
select HAVE_ARCH_JUMP_LABEL_RELATIVE
select HAVE_ARCH_KASAN if X86_64
--
2.30.2

2022-01-22 03:56:24

by Song Liu

[permalink] [raw]
Subject: [PATCH v6 bpf-next 2/7] bpf: use bytes instead of pages for bpf_jit_[charge|uncharge]_modmem

From: Song Liu <[email protected]>

This enables sub-page memory charge and allocation.

Signed-off-by: Song Liu <[email protected]>
---
include/linux/bpf.h | 4 ++--
kernel/bpf/core.c | 17 ++++++++---------
kernel/bpf/trampoline.c | 6 +++---
3 files changed, 13 insertions(+), 14 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index dce54eb0aae8..9232db5014a3 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -827,8 +827,8 @@ void bpf_image_ksym_add(void *data, struct bpf_ksym *ksym);
void bpf_image_ksym_del(struct bpf_ksym *ksym);
void bpf_ksym_add(struct bpf_ksym *ksym);
void bpf_ksym_del(struct bpf_ksym *ksym);
-int bpf_jit_charge_modmem(u32 pages);
-void bpf_jit_uncharge_modmem(u32 pages);
+int bpf_jit_charge_modmem(u32 size);
+void bpf_jit_uncharge_modmem(u32 size);
bool bpf_prog_has_trampoline(const struct bpf_prog *prog);
#else
static inline int bpf_trampoline_link_prog(struct bpf_prog *prog,
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index de3e5bc6781f..b9c6a426a7dd 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -833,12 +833,11 @@ static int __init bpf_jit_charge_init(void)
}
pure_initcall(bpf_jit_charge_init);

-int bpf_jit_charge_modmem(u32 pages)
+int bpf_jit_charge_modmem(u32 size)
{
- if (atomic_long_add_return(pages, &bpf_jit_current) >
- (bpf_jit_limit >> PAGE_SHIFT)) {
+ if (atomic_long_add_return(size, &bpf_jit_current) > bpf_jit_limit) {
if (!bpf_capable()) {
- atomic_long_sub(pages, &bpf_jit_current);
+ atomic_long_sub(size, &bpf_jit_current);
return -EPERM;
}
}
@@ -846,9 +845,9 @@ int bpf_jit_charge_modmem(u32 pages)
return 0;
}

-void bpf_jit_uncharge_modmem(u32 pages)
+void bpf_jit_uncharge_modmem(u32 size)
{
- atomic_long_sub(pages, &bpf_jit_current);
+ atomic_long_sub(size, &bpf_jit_current);
}

void *__weak bpf_jit_alloc_exec(unsigned long size)
@@ -879,11 +878,11 @@ bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
size = round_up(proglen + sizeof(*hdr) + 128, PAGE_SIZE);
pages = size / PAGE_SIZE;

- if (bpf_jit_charge_modmem(pages))
+ if (bpf_jit_charge_modmem(size))
return NULL;
hdr = bpf_jit_alloc_exec(size);
if (!hdr) {
- bpf_jit_uncharge_modmem(pages);
+ bpf_jit_uncharge_modmem(size);
return NULL;
}

@@ -906,7 +905,7 @@ void bpf_jit_binary_free(struct bpf_binary_header *hdr)
u32 pages = hdr->pages;

bpf_jit_free_exec(hdr);
- bpf_jit_uncharge_modmem(pages);
+ bpf_jit_uncharge_modmem(pages << PAGE_SHIFT);
}

/* This symbol is only overridden by archs that have different
diff --git a/kernel/bpf/trampoline.c b/kernel/bpf/trampoline.c
index 4b6974a195c1..e76a488c09c3 100644
--- a/kernel/bpf/trampoline.c
+++ b/kernel/bpf/trampoline.c
@@ -213,7 +213,7 @@ static void __bpf_tramp_image_put_deferred(struct work_struct *work)
im = container_of(work, struct bpf_tramp_image, work);
bpf_image_ksym_del(&im->ksym);
bpf_jit_free_exec(im->image);
- bpf_jit_uncharge_modmem(1);
+ bpf_jit_uncharge_modmem(PAGE_SIZE);
percpu_ref_exit(&im->pcref);
kfree_rcu(im, rcu);
}
@@ -310,7 +310,7 @@ static struct bpf_tramp_image *bpf_tramp_image_alloc(u64 key, u32 idx)
if (!im)
goto out;

- err = bpf_jit_charge_modmem(1);
+ err = bpf_jit_charge_modmem(PAGE_SIZE);
if (err)
goto out_free_im;

@@ -332,7 +332,7 @@ static struct bpf_tramp_image *bpf_tramp_image_alloc(u64 key, u32 idx)
out_free_image:
bpf_jit_free_exec(im->image);
out_uncharge:
- bpf_jit_uncharge_modmem(1);
+ bpf_jit_uncharge_modmem(PAGE_SIZE);
out_free_im:
kfree(im);
out:
--
2.30.2

2022-01-22 03:57:10

by Song Liu

[permalink] [raw]
Subject: [PATCH v6 bpf-next 7/7] bpf, x86_64: use bpf_prog_pack allocator

From: Song Liu <[email protected]>

Use bpf_prog_pack allocator in x86_64 jit.

The program header from bpf_prog_pack is read only during the jit process.
Therefore, the binary is first written to a temporary buffer, and later
copied to final location with text_poke_copy().

Similarly, jit_fill_hole() is updated to fill the hole with 0xcc using
text_poke_copy().

Signed-off-by: Song Liu <[email protected]>
---
arch/x86/net/bpf_jit_comp.c | 141 ++++++++++++++++++++++++++++--------
1 file changed, 111 insertions(+), 30 deletions(-)

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index fe4f08e25a1d..fcdfec992184 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -216,11 +216,32 @@ static u8 simple_alu_opcodes[] = {
[BPF_ARSH] = 0xF8,
};

+#define BPF_X86_JIT_HOLE_BUFFER_SIZE 128
+static char jit_hole_buffer[BPF_X86_JIT_HOLE_BUFFER_SIZE] = {};
+
static void jit_fill_hole(void *area, unsigned int size)
+{
+ struct bpf_binary_header *hdr = area;
+
+ /* fill the first and last 128 bytes of the buffer with INT3 */
+ text_poke_copy(area, jit_hole_buffer, BPF_X86_JIT_HOLE_BUFFER_SIZE);
+ text_poke_copy(area + size - BPF_X86_JIT_HOLE_BUFFER_SIZE,
+ jit_hole_buffer, BPF_X86_JIT_HOLE_BUFFER_SIZE);
+
+ /*
+ * bpf_jit_binary_alloc_pack cannot write size directly to the ro
+ * mapping. Write it here with text_poke_copy().
+ */
+ text_poke_copy(&hdr->size, &size, sizeof(size));
+}
+
+static int __init x86_jit_fill_hole_init(void)
{
/* Fill whole space with INT3 instructions */
- memset(area, 0xcc, size);
+ memset(jit_hole_buffer, 0xcc, BPF_X86_JIT_HOLE_BUFFER_SIZE);
+ return 0;
}
+pure_initcall(x86_jit_fill_hole_init);

struct jit_context {
int cleanup_addr; /* Epilogue code offset */
@@ -361,14 +382,11 @@ static int __bpf_arch_text_poke(void *ip, enum bpf_text_poke_type t,

ret = -EBUSY;
mutex_lock(&text_mutex);
- if (memcmp(ip, old_insn, X86_PATCH_SIZE))
+ if (text_live && memcmp(ip, old_insn, X86_PATCH_SIZE))
goto out;
ret = 1;
if (memcmp(ip, new_insn, X86_PATCH_SIZE)) {
- if (text_live)
- text_poke_bp(ip, new_insn, X86_PATCH_SIZE, NULL);
- else
- memcpy(ip, new_insn, X86_PATCH_SIZE);
+ text_poke_bp(ip, new_insn, X86_PATCH_SIZE, NULL);
ret = 0;
}
out:
@@ -537,7 +555,7 @@ static void emit_bpf_tail_call_direct(struct bpf_jit_poke_descriptor *poke,
*pprog = prog;
}

-static void bpf_tail_call_direct_fixup(struct bpf_prog *prog)
+static void bpf_tail_call_direct_fixup(struct bpf_prog *prog, bool text_live)
{
struct bpf_jit_poke_descriptor *poke;
struct bpf_array *array;
@@ -558,24 +576,15 @@ static void bpf_tail_call_direct_fixup(struct bpf_prog *prog)
mutex_lock(&array->aux->poke_mutex);
target = array->ptrs[poke->tail_call.key];
if (target) {
- /* Plain memcpy is used when image is not live yet
- * and still not locked as read-only. Once poke
- * location is active (poke->tailcall_target_stable),
- * any parallel bpf_arch_text_poke() might occur
- * still on the read-write image until we finally
- * locked it as read-only. Both modifications on
- * the given image are under text_mutex to avoid
- * interference.
- */
ret = __bpf_arch_text_poke(poke->tailcall_target,
BPF_MOD_JUMP, NULL,
(u8 *)target->bpf_func +
- poke->adj_off, false);
+ poke->adj_off, text_live);
BUG_ON(ret < 0);
ret = __bpf_arch_text_poke(poke->tailcall_bypass,
BPF_MOD_JUMP,
(u8 *)poke->tailcall_target +
- X86_PATCH_SIZE, NULL, false);
+ X86_PATCH_SIZE, NULL, text_live);
BUG_ON(ret < 0);
}
WRITE_ONCE(poke->tailcall_target_stable, true);
@@ -867,7 +876,7 @@ static void emit_nops(u8 **pprog, int len)

#define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))

-static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
+static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image,
int oldproglen, struct jit_context *ctx, bool jmp_padding)
{
bool tail_call_reachable = bpf_prog->aux->tail_call_reachable;
@@ -894,8 +903,8 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
push_callee_regs(&prog, callee_regs_used);

ilen = prog - temp;
- if (image)
- memcpy(image + proglen, temp, ilen);
+ if (rw_image)
+ memcpy(rw_image + proglen, temp, ilen);
proglen += ilen;
addrs[0] = proglen;
prog = temp;
@@ -1324,8 +1333,10 @@ st: if (is_imm8(insn->off))
pr_err("extable->insn doesn't fit into 32-bit\n");
return -EFAULT;
}
- ex->insn = delta;
+ /* switch ex to temporary buffer for writes */
+ ex = (void *)rw_image + ((void *)ex - (void *)image);

+ ex->insn = delta;
ex->type = EX_TYPE_BPF;

if (dst_reg > BPF_REG_9) {
@@ -1706,7 +1717,7 @@ st: if (is_imm8(insn->off))
pr_err("bpf_jit: fatal error\n");
return -EFAULT;
}
- memcpy(image + proglen, temp, ilen);
+ memcpy(rw_image + proglen, temp, ilen);
}
proglen += ilen;
addrs[i] = proglen;
@@ -2248,6 +2259,12 @@ int arch_prepare_bpf_dispatcher(void *image, s64 *funcs, int num_funcs)

struct x64_jit_data {
struct bpf_binary_header *header;
+ /*
+ * With bpf_prog_pack, header points to read-only memory.
+ * rw_header holds a temporary rw buffer for JIT. When JIT is done,
+ * the binary is copied to header with text_poke_copy().
+ */
+ struct bpf_binary_header *rw_header;
int *addrs;
u8 *image;
int proglen;
@@ -2259,6 +2276,7 @@ struct x64_jit_data {

struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
{
+ struct bpf_binary_header *rw_header = NULL;
struct bpf_binary_header *header = NULL;
struct bpf_prog *tmp, *orig_prog = prog;
struct x64_jit_data *jit_data;
@@ -2267,6 +2285,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
bool tmp_blinded = false;
bool extra_pass = false;
bool padding = false;
+ u8 *rw_image = NULL;
u8 *image = NULL;
int *addrs;
int pass;
@@ -2302,6 +2321,8 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
oldproglen = jit_data->proglen;
image = jit_data->image;
header = jit_data->header;
+ rw_header = jit_data->rw_header;
+ rw_image = (void *)rw_header + ((void *)image - (void *)header);
extra_pass = true;
padding = true;
goto skip_init_addrs;
@@ -2332,14 +2353,18 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
for (pass = 0; pass < MAX_PASSES || image; pass++) {
if (!padding && pass >= PADDING_PASSES)
padding = true;
- proglen = do_jit(prog, addrs, image, oldproglen, &ctx, padding);
+ proglen = do_jit(prog, addrs, image, rw_image, oldproglen, &ctx, padding);
if (proglen <= 0) {
out_image:
image = NULL;
- if (header)
- bpf_jit_binary_free(header);
+ rw_image = NULL;
+ if (header) {
+ bpf_jit_binary_free_pack(header);
+ kfree(rw_header);
+ }
prog = orig_prog;
header = NULL;
+ rw_header = NULL;
goto out_addrs;
}
if (image) {
@@ -2362,12 +2387,34 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
sizeof(struct exception_table_entry);

/* allocate module memory for x86 insns and extable */
- header = bpf_jit_binary_alloc(roundup(proglen, align) + extable_size,
- &image, align, jit_fill_hole);
+ header = bpf_jit_binary_alloc_pack(roundup(proglen, align) + extable_size,
+ &image, align, jit_fill_hole);
if (!header) {
prog = orig_prog;
goto out_addrs;
}
+ if (header->size > bpf_prog_pack_max_size()) {
+ rw_header = header;
+ rw_image = image;
+ } else {
+ /*
+ * With bpf_prog_pack, header and image
+ * points to read-only memory. Allocate a
+ * rw buffer for writes during JIT.
+ *
+ * When the JIT is done, the binary is copied
+ * to header with text_poke_copy().
+ */
+ rw_header = kvmalloc(header->size, GFP_KERNEL | __GFP_ZERO);
+ if (!rw_header) {
+ bpf_jit_binary_free_pack(header);
+ header = NULL;
+ prog = orig_prog;
+ goto out_addrs;
+ }
+ rw_header->size = header->size;
+ rw_image = (void *)rw_header + ((void *)image - (void *)header);
+ }
prog->aux->extable = (void *) image + roundup(proglen, align);
}
oldproglen = proglen;
@@ -2379,14 +2426,23 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)

if (image) {
if (!prog->is_func || extra_pass) {
- bpf_tail_call_direct_fixup(prog);
- bpf_jit_binary_lock_ro(header);
+ if (header->size > bpf_prog_pack_max_size()) {
+ /*
+ * bpf_prog_pack cannot handle too big
+ * program (> ~2MB). Fall back to regular
+ * module_alloc(), and do the fixup and
+ * lock_ro here.
+ */
+ bpf_tail_call_direct_fixup(prog, false);
+ bpf_jit_binary_lock_ro(header);
+ }
} else {
jit_data->addrs = addrs;
jit_data->ctx = ctx;
jit_data->proglen = proglen;
jit_data->image = image;
jit_data->header = header;
+ jit_data->rw_header = rw_header;
}
prog->bpf_func = (void *)image;
prog->jited = 1;
@@ -2402,6 +2458,17 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
kvfree(addrs);
kfree(jit_data);
prog->aux->jit_data = NULL;
+ jit_data = NULL;
+ if (rw_header != header) {
+ text_poke_copy(header, rw_header, header->size);
+ kvfree(rw_header);
+ /*
+ * Do the fixup after final text_poke_copy().
+ * Otherwise, the fix up will be overwritten by
+ * text_poke_copy().
+ */
+ bpf_tail_call_direct_fixup(prog, true);
+ }
}
out:
if (tmp_blinded)
@@ -2415,3 +2482,17 @@ bool bpf_jit_supports_kfunc_call(void)
{
return true;
}
+
+void bpf_jit_free(struct bpf_prog *fp)
+{
+ if (fp->jited) {
+ struct bpf_binary_header *hdr = bpf_jit_binary_hdr(fp);
+
+ if (hdr->size > bpf_prog_pack_max_size())
+ bpf_jit_binary_free(hdr);
+ else
+ bpf_jit_binary_free_pack(hdr);
+ }
+
+ bpf_prog_unlock_free(fp);
+}
--
2.30.2

2022-01-22 06:15:14

by Song Liu

[permalink] [raw]
Subject: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

From: Song Liu <[email protected]>

Most BPF programs are small, but they consume a page each. For systems
with busy traffic and many BPF programs, this could add significant
pressure to instruction TLB.

Introduce bpf_prog_pack allocator to pack multiple BPF programs in a huge
page. The memory is then allocated in 64 byte chunks.

Memory allocated by bpf_prog_pack allocator is RO protected after initial
allocation. To write to it, the user (jit engine) need to use text poke
API.

Signed-off-by: Song Liu <[email protected]>
---
include/linux/filter.h | 7 ++
kernel/bpf/core.c | 184 ++++++++++++++++++++++++++++++++++++++++-
2 files changed, 187 insertions(+), 4 deletions(-)

diff --git a/include/linux/filter.h b/include/linux/filter.h
index 27ea68604c22..a58658442d2e 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -1074,6 +1074,13 @@ void *bpf_jit_alloc_exec(unsigned long size);
void bpf_jit_free_exec(void *addr);
void bpf_jit_free(struct bpf_prog *fp);

+struct bpf_binary_header *
+bpf_jit_binary_alloc_pack(unsigned int proglen, u8 **image_r_ptr,
+ unsigned int alignment,
+ bpf_jit_fill_hole_t bpf_fill_ill_insns);
+void bpf_jit_binary_free_pack(struct bpf_binary_header *hdr);
+int bpf_prog_pack_max_size(void);
+
int bpf_jit_add_poke_descriptor(struct bpf_prog *prog,
struct bpf_jit_poke_descriptor *poke);

diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index f252d8529b0b..a912818a5205 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -808,6 +808,116 @@ int bpf_jit_add_poke_descriptor(struct bpf_prog *prog,
return slot;
}

+/*
+ * BPF program pack allocator.
+ *
+ * Most BPF programs are pretty small. Allocating a hole page for each
+ * program is sometime a waste. Many small bpf program also adds pressure
+ * to instruction TLB. To solve this issue, we introduce a BPF program pack
+ * allocator. The prog_pack allocator uses HPAGE_PMD_SIZE page (2MB on x86)
+ * to host BPF programs.
+ */
+#define BPF_PROG_PACK_SIZE HPAGE_PMD_SIZE
+#define BPF_PROG_CHUNK_SHIFT 6
+#define BPF_PROG_CHUNK_SIZE (1 << BPF_PROG_CHUNK_SHIFT)
+#define BPF_PROG_CHUNK_COUNT (BPF_PROG_PACK_SIZE / BPF_PROG_CHUNK_SIZE)
+
+struct bpf_prog_pack {
+ struct list_head list;
+ void *ptr;
+ unsigned long bitmap[BITS_TO_LONGS(BPF_PROG_CHUNK_COUNT)];
+};
+
+#define BPF_PROG_MAX_PACK_PROG_SIZE HPAGE_PMD_SIZE
+#define BPF_PROG_SIZE_TO_NBITS(size) (round_up(size, BPF_PROG_CHUNK_SIZE) / BPF_PROG_CHUNK_SIZE)
+
+static DEFINE_MUTEX(pack_mutex);
+static LIST_HEAD(pack_list);
+
+static struct bpf_prog_pack *alloc_new_pack(void)
+{
+ struct bpf_prog_pack *pack;
+
+ pack = kzalloc(sizeof(*pack), GFP_KERNEL);
+ if (!pack)
+ return NULL;
+ pack->ptr = module_alloc(BPF_PROG_PACK_SIZE);
+ if (!pack->ptr) {
+ kfree(pack);
+ return NULL;
+ }
+ bitmap_zero(pack->bitmap, BPF_PROG_PACK_SIZE / BPF_PROG_CHUNK_SIZE);
+ list_add_tail(&pack->list, &pack_list);
+
+ set_vm_flush_reset_perms(pack);
+ set_memory_ro((unsigned long)pack->ptr, BPF_PROG_PACK_SIZE / PAGE_SIZE);
+ set_memory_x((unsigned long)pack->ptr, BPF_PROG_PACK_SIZE / PAGE_SIZE);
+ return pack;
+}
+
+static void *bpf_prog_pack_alloc(u32 size)
+{
+ unsigned int nbits = BPF_PROG_SIZE_TO_NBITS(size);
+ struct bpf_prog_pack *pack;
+ unsigned long pos;
+ void *ptr = NULL;
+
+ mutex_lock(&pack_mutex);
+ list_for_each_entry(pack, &pack_list, list) {
+ pos = bitmap_find_next_zero_area(pack->bitmap, BPF_PROG_CHUNK_COUNT, 0,
+ nbits, 0);
+ if (pos < BPF_PROG_CHUNK_COUNT)
+ goto found_free_area;
+ }
+
+ pack = alloc_new_pack();
+ if (!pack)
+ goto out;
+
+ pos = 0;
+
+found_free_area:
+ bitmap_set(pack->bitmap, pos, nbits);
+ ptr = (void *)(pack->ptr) + (pos << BPF_PROG_CHUNK_SHIFT);
+
+out:
+ mutex_unlock(&pack_mutex);
+ return ptr;
+}
+
+static void bpf_prog_pack_free(struct bpf_binary_header *hdr)
+{
+ void *pack_ptr = (void *)((unsigned long)hdr & ~(BPF_PROG_PACK_SIZE - 1));
+ struct bpf_prog_pack *pack = NULL, *tmp;
+ unsigned int nbits;
+ unsigned long pos;
+
+ mutex_lock(&pack_mutex);
+
+ list_for_each_entry(tmp, &pack_list, list) {
+ if (tmp->ptr == pack_ptr) {
+ pack = tmp;
+ break;
+ }
+ }
+
+ if (WARN_ONCE(!pack, "bpf_prog_pack bug\n"))
+ goto out;
+
+ nbits = BPF_PROG_SIZE_TO_NBITS(hdr->size);
+ pos = ((unsigned long)hdr - (unsigned long)pack_ptr) >> BPF_PROG_CHUNK_SHIFT;
+
+ bitmap_clear(pack->bitmap, pos, nbits);
+ if (bitmap_find_next_zero_area(pack->bitmap, BPF_PROG_CHUNK_COUNT, 0,
+ BPF_PROG_CHUNK_COUNT, 0) == 0) {
+ list_del(&pack->list);
+ module_memfree(pack->ptr);
+ kfree(pack);
+ }
+out:
+ mutex_unlock(&pack_mutex);
+}
+
static atomic_long_t bpf_jit_current;

/* Can be overridden by an arch's JIT compiler if it has a custom,
@@ -860,10 +970,59 @@ void __weak bpf_jit_free_exec(void *addr)
module_memfree(addr);
}

+static struct bpf_binary_header *
+__bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
+ unsigned int alignment,
+ bpf_jit_fill_hole_t bpf_fill_ill_insns,
+ u32 round_up_to)
+{
+ struct bpf_binary_header *hdr;
+ u32 size, hole, start;
+
+ WARN_ON_ONCE(!is_power_of_2(alignment) ||
+ alignment > BPF_IMAGE_ALIGNMENT);
+
+ /* Most of BPF filters are really small, but if some of them
+ * fill a page, allow at least 128 extra bytes to insert a
+ * random section of illegal instructions.
+ */
+ size = round_up(proglen + sizeof(*hdr) + 128, round_up_to);
+
+ if (bpf_jit_charge_modmem(size))
+ return NULL;
+ hdr = bpf_jit_alloc_exec(size);
+ if (!hdr) {
+ bpf_jit_uncharge_modmem(size);
+ return NULL;
+ }
+
+ /* Fill space with illegal/arch-dep instructions. */
+ bpf_fill_ill_insns(hdr, size);
+
+ hdr->size = size;
+ hole = min_t(unsigned int, size - (proglen + sizeof(*hdr)),
+ PAGE_SIZE - sizeof(*hdr));
+ start = (get_random_int() % hole) & ~(alignment - 1);
+
+ /* Leave a random number of instructions before BPF code. */
+ *image_ptr = &hdr->image[start];
+
+ return hdr;
+}
+
struct bpf_binary_header *
bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
unsigned int alignment,
bpf_jit_fill_hole_t bpf_fill_ill_insns)
+{
+ return __bpf_jit_binary_alloc(proglen, image_ptr, alignment,
+ bpf_fill_ill_insns, PAGE_SIZE);
+}
+
+struct bpf_binary_header *
+bpf_jit_binary_alloc_pack(unsigned int proglen, u8 **image_ptr,
+ unsigned int alignment,
+ bpf_jit_fill_hole_t bpf_fill_ill_insns)
{
struct bpf_binary_header *hdr;
u32 size, hole, start;
@@ -875,11 +1034,16 @@ bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
* fill a page, allow at least 128 extra bytes to insert a
* random section of illegal instructions.
*/
- size = round_up(proglen + sizeof(*hdr) + 128, PAGE_SIZE);
+ size = round_up(proglen + sizeof(*hdr) + 128, BPF_PROG_CHUNK_SIZE);
+
+ /* for too big program, use __bpf_jit_binary_alloc. */
+ if (size > BPF_PROG_MAX_PACK_PROG_SIZE)
+ return __bpf_jit_binary_alloc(proglen, image_ptr, alignment,
+ bpf_fill_ill_insns, PAGE_SIZE);

if (bpf_jit_charge_modmem(size))
return NULL;
- hdr = bpf_jit_alloc_exec(size);
+ hdr = bpf_prog_pack_alloc(size);
if (!hdr) {
bpf_jit_uncharge_modmem(size);
return NULL;
@@ -888,9 +1052,8 @@ bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
/* Fill space with illegal/arch-dep instructions. */
bpf_fill_ill_insns(hdr, size);

- hdr->size = size;
hole = min_t(unsigned int, size - (proglen + sizeof(*hdr)),
- PAGE_SIZE - sizeof(*hdr));
+ BPF_PROG_CHUNK_SIZE - sizeof(*hdr));
start = (get_random_int() % hole) & ~(alignment - 1);

/* Leave a random number of instructions before BPF code. */
@@ -907,6 +1070,19 @@ void bpf_jit_binary_free(struct bpf_binary_header *hdr)
bpf_jit_uncharge_modmem(size);
}

+void bpf_jit_binary_free_pack(struct bpf_binary_header *hdr)
+{
+ u32 size = hdr->size;
+
+ bpf_prog_pack_free(hdr);
+ bpf_jit_uncharge_modmem(size);
+}
+
+int bpf_prog_pack_max_size(void)
+{
+ return BPF_PROG_MAX_PACK_PROG_SIZE;
+}
+
/* This symbol is only overridden by archs that have different
* requirements than the usual eBPF JITs, f.e. when they only
* implement cBPF JIT, do not set images read-only, etc.
--
2.30.2

2022-01-22 19:59:02

by Alexei Starovoitov

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On Fri, Jan 21, 2022 at 11:49 AM Song Liu <[email protected]> wrote:
>
> +static struct bpf_binary_header *
> +__bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
> + unsigned int alignment,
> + bpf_jit_fill_hole_t bpf_fill_ill_insns,
> + u32 round_up_to)
> +{
> + struct bpf_binary_header *hdr;
> + u32 size, hole, start;
> +
> + WARN_ON_ONCE(!is_power_of_2(alignment) ||
> + alignment > BPF_IMAGE_ALIGNMENT);
> +
> + /* Most of BPF filters are really small, but if some of them
> + * fill a page, allow at least 128 extra bytes to insert a
> + * random section of illegal instructions.
> + */
> + size = round_up(proglen + sizeof(*hdr) + 128, round_up_to);
> +
> + if (bpf_jit_charge_modmem(size))
> + return NULL;
> + hdr = bpf_jit_alloc_exec(size);
> + if (!hdr) {
> + bpf_jit_uncharge_modmem(size);
> + return NULL;
> + }
> +
> + /* Fill space with illegal/arch-dep instructions. */
> + bpf_fill_ill_insns(hdr, size);
> +
> + hdr->size = size;
> + hole = min_t(unsigned int, size - (proglen + sizeof(*hdr)),
> + PAGE_SIZE - sizeof(*hdr));

It probably should be 'round_up_to' instead of PAGE_SIZE ?

> + start = (get_random_int() % hole) & ~(alignment - 1);
> +
> + /* Leave a random number of instructions before BPF code. */
> + *image_ptr = &hdr->image[start];
> +
> + return hdr;
> +}
> +
> struct bpf_binary_header *
> bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
> unsigned int alignment,
> bpf_jit_fill_hole_t bpf_fill_ill_insns)
> +{
> + return __bpf_jit_binary_alloc(proglen, image_ptr, alignment,
> + bpf_fill_ill_insns, PAGE_SIZE);
> +}
> +
> +struct bpf_binary_header *
> +bpf_jit_binary_alloc_pack(unsigned int proglen, u8 **image_ptr,
> + unsigned int alignment,
> + bpf_jit_fill_hole_t bpf_fill_ill_insns)
> {
> struct bpf_binary_header *hdr;
> u32 size, hole, start;
> @@ -875,11 +1034,16 @@ bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
> * fill a page, allow at least 128 extra bytes to insert a
> * random section of illegal instructions.
> */
> - size = round_up(proglen + sizeof(*hdr) + 128, PAGE_SIZE);
> + size = round_up(proglen + sizeof(*hdr) + 128, BPF_PROG_CHUNK_SIZE);
> +
> + /* for too big program, use __bpf_jit_binary_alloc. */
> + if (size > BPF_PROG_MAX_PACK_PROG_SIZE)
> + return __bpf_jit_binary_alloc(proglen, image_ptr, alignment,
> + bpf_fill_ill_insns, PAGE_SIZE);
>
> if (bpf_jit_charge_modmem(size))
> return NULL;
> - hdr = bpf_jit_alloc_exec(size);
> + hdr = bpf_prog_pack_alloc(size);
> if (!hdr) {
> bpf_jit_uncharge_modmem(size);
> return NULL;
> @@ -888,9 +1052,8 @@ bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
> /* Fill space with illegal/arch-dep instructions. */
> bpf_fill_ill_insns(hdr, size);
>
> - hdr->size = size;

I'm missing where it's assigned.
Looks like hdr->size stays zero, so free is never performed?

> hole = min_t(unsigned int, size - (proglen + sizeof(*hdr)),
> - PAGE_SIZE - sizeof(*hdr));
> + BPF_PROG_CHUNK_SIZE - sizeof(*hdr));

Before this change size - (proglen + sizeof(*hdr)) would
be at least 128 and potentially bigger than PAGE_SIZE
when extra 128 crossed page boundary.
Hence min() was necessary with the 2nd arg being PAGE_SIZE - sizeof(*hdr).

With new code size - (proglen + sizeof(*hdr)) would
be between 128 and 128+64
while BPF_PROG_CHUNK_SIZE - sizeof(*hdr) is a constant less than 64.
What is the point of min() ?

2022-01-22 19:59:02

by Song Liu

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator



> On Jan 21, 2022, at 3:55 PM, Alexei Starovoitov <[email protected]> wrote:
>
> On Fri, Jan 21, 2022 at 11:49 AM Song Liu <[email protected]> wrote:
>>
>> +static struct bpf_binary_header *
>> +__bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
>> + unsigned int alignment,
>> + bpf_jit_fill_hole_t bpf_fill_ill_insns,
>> + u32 round_up_to)
>> +{
>> + struct bpf_binary_header *hdr;
>> + u32 size, hole, start;
>> +
>> + WARN_ON_ONCE(!is_power_of_2(alignment) ||
>> + alignment > BPF_IMAGE_ALIGNMENT);
>> +
>> + /* Most of BPF filters are really small, but if some of them
>> + * fill a page, allow at least 128 extra bytes to insert a
>> + * random section of illegal instructions.
>> + */
>> + size = round_up(proglen + sizeof(*hdr) + 128, round_up_to);
>> +
>> + if (bpf_jit_charge_modmem(size))
>> + return NULL;
>> + hdr = bpf_jit_alloc_exec(size);
>> + if (!hdr) {
>> + bpf_jit_uncharge_modmem(size);
>> + return NULL;
>> + }
>> +
>> + /* Fill space with illegal/arch-dep instructions. */
>> + bpf_fill_ill_insns(hdr, size);
>> +
>> + hdr->size = size;
>> + hole = min_t(unsigned int, size - (proglen + sizeof(*hdr)),
>> + PAGE_SIZE - sizeof(*hdr));
>
> It probably should be 'round_up_to' instead of PAGE_SIZE ?

Actually, some of these change is not longer needed after the following
change in v6:

4. Change fall back round_up_to in bpf_jit_binary_alloc_pack() from
BPF_PROG_MAX_PACK_PROG_SIZE to PAGE_SIZE.

My initial thought (last year) was if we allocate more than 2MB (either
2.1MB or 3.9MB), we round up to 4MB to save page table entries.
However, when I revisited this earlier today, I thought we should still
round up to PAGE_SIZE to save memory

Right now, I am not sure which way is better. What do you think? If we
round up to PAGE_SIZE, we don't need split out __bpf_jit_binary_alloc().

>
>> + start = (get_random_int() % hole) & ~(alignment - 1);
>> +
>> + /* Leave a random number of instructions before BPF code. */
>> + *image_ptr = &hdr->image[start];
>> +
>> + return hdr;
>> +}
>> +
>> struct bpf_binary_header *
>> bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
>> unsigned int alignment,
>> bpf_jit_fill_hole_t bpf_fill_ill_insns)
>> +{
>> + return __bpf_jit_binary_alloc(proglen, image_ptr, alignment,
>> + bpf_fill_ill_insns, PAGE_SIZE);
>> +}
>> +
>> +struct bpf_binary_header *
>> +bpf_jit_binary_alloc_pack(unsigned int proglen, u8 **image_ptr,
>> + unsigned int alignment,
>> + bpf_jit_fill_hole_t bpf_fill_ill_insns)
>> {
>> struct bpf_binary_header *hdr;
>> u32 size, hole, start;
>> @@ -875,11 +1034,16 @@ bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
>> * fill a page, allow at least 128 extra bytes to insert a
>> * random section of illegal instructions.
>> */
>> - size = round_up(proglen + sizeof(*hdr) + 128, PAGE_SIZE);
>> + size = round_up(proglen + sizeof(*hdr) + 128, BPF_PROG_CHUNK_SIZE);
>> +
>> + /* for too big program, use __bpf_jit_binary_alloc. */
>> + if (size > BPF_PROG_MAX_PACK_PROG_SIZE)
>> + return __bpf_jit_binary_alloc(proglen, image_ptr, alignment,
>> + bpf_fill_ill_insns, PAGE_SIZE);
>>
>> if (bpf_jit_charge_modmem(size))
>> return NULL;
>> - hdr = bpf_jit_alloc_exec(size);
>> + hdr = bpf_prog_pack_alloc(size);
>> if (!hdr) {
>> bpf_jit_uncharge_modmem(size);
>> return NULL;
>> @@ -888,9 +1052,8 @@ bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
>> /* Fill space with illegal/arch-dep instructions. */
>> bpf_fill_ill_insns(hdr, size);
>>
>> - hdr->size = size;
>
> I'm missing where it's assigned.
> Looks like hdr->size stays zero, so free is never performed?

This is read only memory, so we set it in bpf_fill_ill_insns(). There was a
comment in x86/bpf_jit_comp.c. I guess we also need a comment here.

>
>> hole = min_t(unsigned int, size - (proglen + sizeof(*hdr)),
>> - PAGE_SIZE - sizeof(*hdr));
>> + BPF_PROG_CHUNK_SIZE - sizeof(*hdr));
>
> Before this change size - (proglen + sizeof(*hdr)) would
> be at least 128 and potentially bigger than PAGE_SIZE
> when extra 128 crossed page boundary.
> Hence min() was necessary with the 2nd arg being PAGE_SIZE - sizeof(*hdr).
>
> With new code size - (proglen + sizeof(*hdr)) would
> be between 128 and 128+64
> while BPF_PROG_CHUNK_SIZE - sizeof(*hdr) is a constant less than 64.
> What is the point of min() ?

Yeah, I guess I didn't finish my math homework here. Will fix it in the
next version.

2022-01-22 19:59:19

by Alexei Starovoitov

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On Fri, Jan 21, 2022 at 4:23 PM Song Liu <[email protected]> wrote:
>
>
>
> > On Jan 21, 2022, at 3:55 PM, Alexei Starovoitov <[email protected]> wrote:
> >
> > On Fri, Jan 21, 2022 at 11:49 AM Song Liu <[email protected]> wrote:
> >>
> >> +static struct bpf_binary_header *
> >> +__bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
> >> + unsigned int alignment,
> >> + bpf_jit_fill_hole_t bpf_fill_ill_insns,
> >> + u32 round_up_to)
> >> +{
> >> + struct bpf_binary_header *hdr;
> >> + u32 size, hole, start;
> >> +
> >> + WARN_ON_ONCE(!is_power_of_2(alignment) ||
> >> + alignment > BPF_IMAGE_ALIGNMENT);
> >> +
> >> + /* Most of BPF filters are really small, but if some of them
> >> + * fill a page, allow at least 128 extra bytes to insert a
> >> + * random section of illegal instructions.
> >> + */
> >> + size = round_up(proglen + sizeof(*hdr) + 128, round_up_to);
> >> +
> >> + if (bpf_jit_charge_modmem(size))
> >> + return NULL;
> >> + hdr = bpf_jit_alloc_exec(size);
> >> + if (!hdr) {
> >> + bpf_jit_uncharge_modmem(size);
> >> + return NULL;
> >> + }
> >> +
> >> + /* Fill space with illegal/arch-dep instructions. */
> >> + bpf_fill_ill_insns(hdr, size);
> >> +
> >> + hdr->size = size;
> >> + hole = min_t(unsigned int, size - (proglen + sizeof(*hdr)),
> >> + PAGE_SIZE - sizeof(*hdr));
> >
> > It probably should be 'round_up_to' instead of PAGE_SIZE ?
>
> Actually, some of these change is not longer needed after the following
> change in v6:
>
> 4. Change fall back round_up_to in bpf_jit_binary_alloc_pack() from
> BPF_PROG_MAX_PACK_PROG_SIZE to PAGE_SIZE.
>
> My initial thought (last year) was if we allocate more than 2MB (either
> 2.1MB or 3.9MB), we round up to 4MB to save page table entries.
> However, when I revisited this earlier today, I thought we should still
> round up to PAGE_SIZE to save memory
>
> Right now, I am not sure which way is better. What do you think? If we
> round up to PAGE_SIZE, we don't need split out __bpf_jit_binary_alloc().

The less code duplication the better.

> >
> >> + start = (get_random_int() % hole) & ~(alignment - 1);
> >> +
> >> + /* Leave a random number of instructions before BPF code. */
> >> + *image_ptr = &hdr->image[start];
> >> +
> >> + return hdr;
> >> +}
> >> +
> >> struct bpf_binary_header *
> >> bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
> >> unsigned int alignment,
> >> bpf_jit_fill_hole_t bpf_fill_ill_insns)
> >> +{
> >> + return __bpf_jit_binary_alloc(proglen, image_ptr, alignment,
> >> + bpf_fill_ill_insns, PAGE_SIZE);
> >> +}
> >> +
> >> +struct bpf_binary_header *
> >> +bpf_jit_binary_alloc_pack(unsigned int proglen, u8 **image_ptr,
> >> + unsigned int alignment,
> >> + bpf_jit_fill_hole_t bpf_fill_ill_insns)
> >> {
> >> struct bpf_binary_header *hdr;
> >> u32 size, hole, start;
> >> @@ -875,11 +1034,16 @@ bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
> >> * fill a page, allow at least 128 extra bytes to insert a
> >> * random section of illegal instructions.
> >> */
> >> - size = round_up(proglen + sizeof(*hdr) + 128, PAGE_SIZE);
> >> + size = round_up(proglen + sizeof(*hdr) + 128, BPF_PROG_CHUNK_SIZE);
> >> +
> >> + /* for too big program, use __bpf_jit_binary_alloc. */
> >> + if (size > BPF_PROG_MAX_PACK_PROG_SIZE)
> >> + return __bpf_jit_binary_alloc(proglen, image_ptr, alignment,
> >> + bpf_fill_ill_insns, PAGE_SIZE);
> >>
> >> if (bpf_jit_charge_modmem(size))
> >> return NULL;
> >> - hdr = bpf_jit_alloc_exec(size);
> >> + hdr = bpf_prog_pack_alloc(size);
> >> if (!hdr) {
> >> bpf_jit_uncharge_modmem(size);
> >> return NULL;
> >> @@ -888,9 +1052,8 @@ bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
> >> /* Fill space with illegal/arch-dep instructions. */
> >> bpf_fill_ill_insns(hdr, size);
> >>
> >> - hdr->size = size;
> >
> > I'm missing where it's assigned.
> > Looks like hdr->size stays zero, so free is never performed?
>
> This is read only memory, so we set it in bpf_fill_ill_insns(). There was a
> comment in x86/bpf_jit_comp.c. I guess we also need a comment here.

Ahh. Found it. Pls don't do it in fill_insn.
It's the wrong layering.
It feels that callbacks need to be redesigned.
I would operate on rw_header here and use
existing arch specific callback fill_insn to write into rw_image.
Both insns during JITing and 0xcc on both sides of the prog.
Populate rw_header->size (either before or after JITing)
and then do single text_poke_copy to write the whole thing
into the correct spot.

2022-01-22 20:00:47

by Alexei Starovoitov

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On Fri, Jan 21, 2022 at 5:01 PM Song Liu <[email protected]> wrote:
>
> In this way, we need to allocate rw_image here, and free it in
> bpf_jit_comp.c. This feels a little weird to me, but I guess that
> is still the cleanest solution for now.

You mean inside bpf_jit_binary_alloc?
That won't be arch independent.
It needs to be split into generic piece that stays in core.c
and callbacks like bpf_jit_fill_hole_t
or into multiple helpers with prep in-between.
Don't worry if all archs need to be touched.

2022-01-22 20:01:09

by Song Liu

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator



> On Jan 21, 2022, at 4:41 PM, Alexei Starovoitov <[email protected]> wrote:
>
> On Fri, Jan 21, 2022 at 4:23 PM Song Liu <[email protected]> wrote:
>>
>>
>>
>>> On Jan 21, 2022, at 3:55 PM, Alexei Starovoitov <[email protected]> wrote:
>>>
>>> On Fri, Jan 21, 2022 at 11:49 AM Song Liu <[email protected]> wrote:
>>>>
>>>> +static struct bpf_binary_header *
>>>> +__bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
>>>> + unsigned int alignment,
>>>> + bpf_jit_fill_hole_t bpf_fill_ill_insns,
>>>> + u32 round_up_to)
>>>> +{
>>>> + struct bpf_binary_header *hdr;
>>>> + u32 size, hole, start;
>>>> +
>>>> + WARN_ON_ONCE(!is_power_of_2(alignment) ||
>>>> + alignment > BPF_IMAGE_ALIGNMENT);
>>>> +
>>>> + /* Most of BPF filters are really small, but if some of them
>>>> + * fill a page, allow at least 128 extra bytes to insert a
>>>> + * random section of illegal instructions.
>>>> + */
>>>> + size = round_up(proglen + sizeof(*hdr) + 128, round_up_to);
>>>> +
>>>> + if (bpf_jit_charge_modmem(size))
>>>> + return NULL;
>>>> + hdr = bpf_jit_alloc_exec(size);
>>>> + if (!hdr) {
>>>> + bpf_jit_uncharge_modmem(size);
>>>> + return NULL;
>>>> + }
>>>> +
>>>> + /* Fill space with illegal/arch-dep instructions. */
>>>> + bpf_fill_ill_insns(hdr, size);
>>>> +
>>>> + hdr->size = size;
>>>> + hole = min_t(unsigned int, size - (proglen + sizeof(*hdr)),
>>>> + PAGE_SIZE - sizeof(*hdr));
>>>
>>> It probably should be 'round_up_to' instead of PAGE_SIZE ?
>>
>> Actually, some of these change is not longer needed after the following
>> change in v6:
>>
>> 4. Change fall back round_up_to in bpf_jit_binary_alloc_pack() from
>> BPF_PROG_MAX_PACK_PROG_SIZE to PAGE_SIZE.
>>
>> My initial thought (last year) was if we allocate more than 2MB (either
>> 2.1MB or 3.9MB), we round up to 4MB to save page table entries.
>> However, when I revisited this earlier today, I thought we should still
>> round up to PAGE_SIZE to save memory
>>
>> Right now, I am not sure which way is better. What do you think? If we
>> round up to PAGE_SIZE, we don't need split out __bpf_jit_binary_alloc().
>
> The less code duplication the better.

Got it. Will go with PAGE_SIZE.

[...]

>>>> +
>>>> if (bpf_jit_charge_modmem(size))
>>>> return NULL;
>>>> - hdr = bpf_jit_alloc_exec(size);
>>>> + hdr = bpf_prog_pack_alloc(size);
>>>> if (!hdr) {
>>>> bpf_jit_uncharge_modmem(size);
>>>> return NULL;
>>>> @@ -888,9 +1052,8 @@ bpf_jit_binary_alloc(unsigned int proglen, u8 **image_ptr,
>>>> /* Fill space with illegal/arch-dep instructions. */
>>>> bpf_fill_ill_insns(hdr, size);
>>>>
>>>> - hdr->size = size;
>>>
>>> I'm missing where it's assigned.
>>> Looks like hdr->size stays zero, so free is never performed?
>>
>> This is read only memory, so we set it in bpf_fill_ill_insns(). There was a
>> comment in x86/bpf_jit_comp.c. I guess we also need a comment here.
>
> Ahh. Found it. Pls don't do it in fill_insn.
> It's the wrong layering.
> It feels that callbacks need to be redesigned.
> I would operate on rw_header here and use
> existing arch specific callback fill_insn to write into rw_image.
> Both insns during JITing and 0xcc on both sides of the prog.
> Populate rw_header->size (either before or after JITing)
> and then do single text_poke_copy to write the whole thing
> into the correct spot.

In this way, we need to allocate rw_image here, and free it in
bpf_jit_comp.c. This feels a little weird to me, but I guess that
is still the cleanest solution for now.

Thanks,
Song

2022-01-23 00:13:07

by Song Liu

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator



> On Jan 21, 2022, at 5:12 PM, Alexei Starovoitov <[email protected]> wrote:
>
> On Fri, Jan 21, 2022 at 5:01 PM Song Liu <[email protected]> wrote:
>>
>> In this way, we need to allocate rw_image here, and free it in
>> bpf_jit_comp.c. This feels a little weird to me, but I guess that
>> is still the cleanest solution for now.
>
> You mean inside bpf_jit_binary_alloc?
> That won't be arch independent.
> It needs to be split into generic piece that stays in core.c
> and callbacks like bpf_jit_fill_hole_t
> or into multiple helpers with prep in-between.
> Don't worry if all archs need to be touched.

How about we introduce callback bpf_jit_set_header_size_t? Then we
can split x86's jit_fill_hole() into two functions, one to fill the
hole, the other to set size. The rest of the logic gonna stay the same.

Archs that do not use bpf_prog_pack won't need bpf_jit_set_header_size_t.

Thanks,
Song

2022-01-23 00:13:34

by Alexei Starovoitov

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On Fri, Jan 21, 2022 at 5:30 PM Song Liu <[email protected]> wrote:
>
>
>
> > On Jan 21, 2022, at 5:12 PM, Alexei Starovoitov <[email protected]> wrote:
> >
> > On Fri, Jan 21, 2022 at 5:01 PM Song Liu <[email protected]> wrote:
> >>
> >> In this way, we need to allocate rw_image here, and free it in
> >> bpf_jit_comp.c. This feels a little weird to me, but I guess that
> >> is still the cleanest solution for now.
> >
> > You mean inside bpf_jit_binary_alloc?
> > That won't be arch independent.
> > It needs to be split into generic piece that stays in core.c
> > and callbacks like bpf_jit_fill_hole_t
> > or into multiple helpers with prep in-between.
> > Don't worry if all archs need to be touched.
>
> How about we introduce callback bpf_jit_set_header_size_t? Then we
> can split x86's jit_fill_hole() into two functions, one to fill the
> hole, the other to set size. The rest of the logic gonna stay the same.
>
> Archs that do not use bpf_prog_pack won't need bpf_jit_set_header_size_t.

That's not any better.

Currently the choice of bpf_jit_binary_alloc_pack vs bpf_jit_binary_alloc
leaks into arch bits and bpf_prog_pack_max_size() doesn't
really make it generic.

Ideally all archs continue to use bpf_jit_binary_alloc()
and magic happens in a generic code.
If not then please remove bpf_prog_pack_max_size(),
since it doesn't provide much value and pick
bpf_jit_binary_alloc_pack() signature to fit x86 jit better.
It wouldn't need bpf_jit_fill_hole_t callback at all.
Please think it through so we don't need to redesign it
when another arch will decide to use huge pages for bpf progs.

cc-ing Ilya for ideas on how that would fit s390.

2022-01-23 15:54:27

by Song Liu

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator



> On Jan 21, 2022, at 6:12 PM, Alexei Starovoitov <[email protected]> wrote:
>
> On Fri, Jan 21, 2022 at 5:30 PM Song Liu <[email protected]> wrote:
>>
>>
>>
>>> On Jan 21, 2022, at 5:12 PM, Alexei Starovoitov <[email protected]> wrote:
>>>
>>> On Fri, Jan 21, 2022 at 5:01 PM Song Liu <[email protected]> wrote:
>>>>
>>>> In this way, we need to allocate rw_image here, and free it in
>>>> bpf_jit_comp.c. This feels a little weird to me, but I guess that
>>>> is still the cleanest solution for now.
>>>
>>> You mean inside bpf_jit_binary_alloc?
>>> That won't be arch independent.
>>> It needs to be split into generic piece that stays in core.c
>>> and callbacks like bpf_jit_fill_hole_t
>>> or into multiple helpers with prep in-between.
>>> Don't worry if all archs need to be touched.
>>
>> How about we introduce callback bpf_jit_set_header_size_t? Then we
>> can split x86's jit_fill_hole() into two functions, one to fill the
>> hole, the other to set size. The rest of the logic gonna stay the same.
>>
>> Archs that do not use bpf_prog_pack won't need bpf_jit_set_header_size_t.
>
> That's not any better.
>
> Currently the choice of bpf_jit_binary_alloc_pack vs bpf_jit_binary_alloc
> leaks into arch bits and bpf_prog_pack_max_size() doesn't
> really make it generic.
>
> Ideally all archs continue to use bpf_jit_binary_alloc()
> and magic happens in a generic code.
> If not then please remove bpf_prog_pack_max_size(),
> since it doesn't provide much value and pick
> bpf_jit_binary_alloc_pack() signature to fit x86 jit better.
> It wouldn't need bpf_jit_fill_hole_t callback at all.
> Please think it through so we don't need to redesign it
> when another arch will decide to use huge pages for bpf progs.
>
> cc-ing Ilya for ideas on how that would fit s390.

I guess we have a few different questions here:

1. Can we use bpf_jit_binary_alloc() for both regular page and shared
huge page?

I think the answer is no, as bpf_jit_binary_alloc() allocates a rw
buffer, and arch calls bpf_jit_binary_lock_ro after JITing. The new
allocator will return a slice of a shared huge page, which is locked
RO before JITing.

2. The problem with bpf_prog_pack_max_size() limitation.

I think this is the worst part of current version of bpf_prog_pack,
but it shouldn't be too hard to fix. I will remove this limitation
in the next version.

3. How to set proper header->size?

I guess we can introduce something similar to bpf_arch_text_poke()
for this?


My proposal for the next version is:
1. No changes to archs that do not use huge page, just keep using
bpf_jit_binary_alloc.

2. For x86_64 (and other arch that would support bpf program on huge
pages):
2.1 arch/bpf_jit_comp calls bpf_jit_binary_alloc_pack() to allocate
an RO bpf_binary_header;
2.2 arch allocates a temporary buffer for JIT. Once JIT is done,
use text_poke_copy to copy the code to the RO bpf_binary_header.

3. Remove bpf_prog_pack_max_size limitation.


Does this sound reasonable?

Thanks,
Song


2022-01-24 19:13:03

by Ilya Leoshkevich

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator



On 1/23/22 02:03, Song Liu wrote:
>
>
>> On Jan 21, 2022, at 6:12 PM, Alexei Starovoitov <[email protected]> wrote:
>>
>> On Fri, Jan 21, 2022 at 5:30 PM Song Liu <[email protected]> wrote:
>>>
>>>
>>>
>>>> On Jan 21, 2022, at 5:12 PM, Alexei Starovoitov <[email protected]> wrote:
>>>>
>>>> On Fri, Jan 21, 2022 at 5:01 PM Song Liu <[email protected]> wrote:
>>>>>
>>>>> In this way, we need to allocate rw_image here, and free it in
>>>>> bpf_jit_comp.c. This feels a little weird to me, but I guess that
>>>>> is still the cleanest solution for now.
>>>>
>>>> You mean inside bpf_jit_binary_alloc?
>>>> That won't be arch independent.
>>>> It needs to be split into generic piece that stays in core.c
>>>> and callbacks like bpf_jit_fill_hole_t
>>>> or into multiple helpers with prep in-between.
>>>> Don't worry if all archs need to be touched.
>>>
>>> How about we introduce callback bpf_jit_set_header_size_t? Then we
>>> can split x86's jit_fill_hole() into two functions, one to fill the
>>> hole, the other to set size. The rest of the logic gonna stay the same.
>>>
>>> Archs that do not use bpf_prog_pack won't need bpf_jit_set_header_size_t.
>>
>> That's not any better.
>>
>> Currently the choice of bpf_jit_binary_alloc_pack vs bpf_jit_binary_alloc
>> leaks into arch bits and bpf_prog_pack_max_size() doesn't
>> really make it generic.
>>
>> Ideally all archs continue to use bpf_jit_binary_alloc()
>> and magic happens in a generic code.
>> If not then please remove bpf_prog_pack_max_size(),
>> since it doesn't provide much value and pick
>> bpf_jit_binary_alloc_pack() signature to fit x86 jit better.
>> It wouldn't need bpf_jit_fill_hole_t callback at all.
>> Please think it through so we don't need to redesign it
>> when another arch will decide to use huge pages for bpf progs.
>>
>> cc-ing Ilya for ideas on how that would fit s390.
>
> I guess we have a few different questions here:
>
> 1. Can we use bpf_jit_binary_alloc() for both regular page and shared
> huge page?
>
> I think the answer is no, as bpf_jit_binary_alloc() allocates a rw
> buffer, and arch calls bpf_jit_binary_lock_ro after JITing. The new
> allocator will return a slice of a shared huge page, which is locked
> RO before JITing.
>
> 2. The problem with bpf_prog_pack_max_size() limitation.
>
> I think this is the worst part of current version of bpf_prog_pack,
> but it shouldn't be too hard to fix. I will remove this limitation
> in the next version.
>
> 3. How to set proper header->size?
>
> I guess we can introduce something similar to bpf_arch_text_poke()
> for this?
>
>
> My proposal for the next version is:
> 1. No changes to archs that do not use huge page, just keep using
> bpf_jit_binary_alloc.
>
> 2. For x86_64 (and other arch that would support bpf program on huge
> pages):
> 2.1 arch/bpf_jit_comp calls bpf_jit_binary_alloc_pack() to allocate
> an RO bpf_binary_header;
> 2.2 arch allocates a temporary buffer for JIT. Once JIT is done,
> use text_poke_copy to copy the code to the RO bpf_binary_header.

Are arches expected to allocate rw buffers in different ways? If not,
I would consider putting this into the common code as well. Then
arch-specific code would do something like

header = bpf_jit_binary_alloc_pack(size, &prg_buf, &prg_addr, ...);
...
/*
* Generate code into prg_buf, the code should assume that its first
* byte is located at prg_addr.
*/
...
bpf_jit_binary_finalize_pack(header, prg_buf);

where bpf_jit_binary_finalize_pack() would copy prg_buf to header and
free it.

If this won't work, I also don't see any big problems in the scheme
that you propose (especially if bpf_prog_pack_max_size() limitation is
gone).

[...]

Btw, are there any existing benchmarks that I can use to check whether
this is worth enabling on s390?

Best regards,
Ilya

2022-01-24 19:13:20

by Peter Zijlstra

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On Sun, Jan 23, 2022 at 01:03:25AM +0000, Song Liu wrote:

> I guess we can introduce something similar to bpf_arch_text_poke()
> for this?

IIRC the s390 version of the text_poke_copy() function is called
s390_kernel_write().

2022-01-24 19:52:41

by Song Liu

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator



> On Jan 24, 2022, at 4:29 AM, Ilya Leoshkevich <[email protected]> wrote:
>
>
>
> On 1/23/22 02:03, Song Liu wrote:
>>> On Jan 21, 2022, at 6:12 PM, Alexei Starovoitov <[email protected]> wrote:
>>>
>>> On Fri, Jan 21, 2022 at 5:30 PM Song Liu <[email protected]> wrote:
>>>>
>>>>
>>>>
>>>>> On Jan 21, 2022, at 5:12 PM, Alexei Starovoitov <[email protected]> wrote:
>>>>>
>>>>> On Fri, Jan 21, 2022 at 5:01 PM Song Liu <[email protected]> wrote:
>>>>>>
>>>>>> In this way, we need to allocate rw_image here, and free it in
>>>>>> bpf_jit_comp.c. This feels a little weird to me, but I guess that
>>>>>> is still the cleanest solution for now.
>>>>>
>>>>> You mean inside bpf_jit_binary_alloc?
>>>>> That won't be arch independent.
>>>>> It needs to be split into generic piece that stays in core.c
>>>>> and callbacks like bpf_jit_fill_hole_t
>>>>> or into multiple helpers with prep in-between.
>>>>> Don't worry if all archs need to be touched.
>>>>
>>>> How about we introduce callback bpf_jit_set_header_size_t? Then we
>>>> can split x86's jit_fill_hole() into two functions, one to fill the
>>>> hole, the other to set size. The rest of the logic gonna stay the same.
>>>>
>>>> Archs that do not use bpf_prog_pack won't need bpf_jit_set_header_size_t.
>>>
>>> That's not any better.
>>>
>>> Currently the choice of bpf_jit_binary_alloc_pack vs bpf_jit_binary_alloc
>>> leaks into arch bits and bpf_prog_pack_max_size() doesn't
>>> really make it generic.
>>>
>>> Ideally all archs continue to use bpf_jit_binary_alloc()
>>> and magic happens in a generic code.
>>> If not then please remove bpf_prog_pack_max_size(),
>>> since it doesn't provide much value and pick
>>> bpf_jit_binary_alloc_pack() signature to fit x86 jit better.
>>> It wouldn't need bpf_jit_fill_hole_t callback at all.
>>> Please think it through so we don't need to redesign it
>>> when another arch will decide to use huge pages for bpf progs.
>>>
>>> cc-ing Ilya for ideas on how that would fit s390.
>> I guess we have a few different questions here:
>> 1. Can we use bpf_jit_binary_alloc() for both regular page and shared
>> huge page?
>> I think the answer is no, as bpf_jit_binary_alloc() allocates a rw
>> buffer, and arch calls bpf_jit_binary_lock_ro after JITing. The new
>> allocator will return a slice of a shared huge page, which is locked
>> RO before JITing.
>> 2. The problem with bpf_prog_pack_max_size() limitation.
>> I think this is the worst part of current version of bpf_prog_pack,
>> but it shouldn't be too hard to fix. I will remove this limitation
>> in the next version.
>> 3. How to set proper header->size?
>> I guess we can introduce something similar to bpf_arch_text_poke()
>> for this?
>> My proposal for the next version is:
>> 1. No changes to archs that do not use huge page, just keep using
>> bpf_jit_binary_alloc.
>> 2. For x86_64 (and other arch that would support bpf program on huge
>> pages):
>> 2.1 arch/bpf_jit_comp calls bpf_jit_binary_alloc_pack() to allocate
>> an RO bpf_binary_header;
>> 2.2 arch allocates a temporary buffer for JIT. Once JIT is done,
>> use text_poke_copy to copy the code to the RO bpf_binary_header.
>
> Are arches expected to allocate rw buffers in different ways? If not,
> I would consider putting this into the common code as well. Then
> arch-specific code would do something like
>
> header = bpf_jit_binary_alloc_pack(size, &prg_buf, &prg_addr, ...);
> ...
> /*
> * Generate code into prg_buf, the code should assume that its first
> * byte is located at prg_addr.
> */
> ...
> bpf_jit_binary_finalize_pack(header, prg_buf);
>
> where bpf_jit_binary_finalize_pack() would copy prg_buf to header and
> free it.

I think this should work.

We will need an API like: bpf_arch_text_copy, which uses text_poke_copy()
for x86_64 and s390_kernel_write() for x390. We will use bpf_arch_text_copy
to
1) write header->size;
2) do finally copy in bpf_jit_binary_finalize_pack().

The syntax of bpf_arch_text_copy is quite different to existing
bpf_arch_text_poke, so I guess a new API is better.

>
> If this won't work, I also don't see any big problems in the scheme
> that you propose (especially if bpf_prog_pack_max_size() limitation is
> gone).
>
> [...]
>
> Btw, are there any existing benchmarks that I can use to check whether
> this is worth enabling on s390?

Unfortunately, we don't have a benchmark to share. Most of our benchmarks
are shadow tests that cannot run out of production environment. We have
issues with iTLB misses for most of our big services. A typical system
may see hundreds of iTLB misses per million instruction. Some sched_cls
programs are often the top triggers of these iTLB misses.

Thanks,
Song

2022-01-25 09:08:59

by Alexei Starovoitov

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On Mon, Jan 24, 2022 at 10:27 AM Song Liu <[email protected]> wrote:
> >
> > Are arches expected to allocate rw buffers in different ways? If not,
> > I would consider putting this into the common code as well. Then
> > arch-specific code would do something like
> >
> > header = bpf_jit_binary_alloc_pack(size, &prg_buf, &prg_addr, ...);
> > ...
> > /*
> > * Generate code into prg_buf, the code should assume that its first
> > * byte is located at prg_addr.
> > */
> > ...
> > bpf_jit_binary_finalize_pack(header, prg_buf);
> >
> > where bpf_jit_binary_finalize_pack() would copy prg_buf to header and
> > free it.

It feels right, but bpf_jit_binary_finalize_pack() sounds 100% arch
dependent. The only thing it will do is perform a copy via text_poke.
What else?

> I think this should work.
>
> We will need an API like: bpf_arch_text_copy, which uses text_poke_copy()
> for x86_64 and s390_kernel_write() for x390. We will use bpf_arch_text_copy
> to
> 1) write header->size;
> 2) do finally copy in bpf_jit_binary_finalize_pack().

we can combine all text_poke operations into one.

Can we add an 'image' pointer into struct bpf_binary_header ?
Then do:
int bpf_jit_binary_alloc_pack(size, &ro_hdr, &rw_hdr);

ro_hdr->image would be the address used to compute offsets by JIT.
rw_hdr->image would point to kvmalloc-ed area for emitting insns.
rw_hdr->size would already be populated.

The JITs would write insns into rw_hdr->image including 'int 3' insns.
At the end the JIT will do text_poke_copy(ro_hdr, rw_hdr, rw_hdr->size);
That would be the only copy that will transfer everything into final
location.
Then kvfree(rw_hdr)

wdyt?

2022-01-25 09:34:27

by Song Liu

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On Mon, Jan 24, 2022 at 9:21 PM Alexei Starovoitov
<[email protected]> wrote:
>
> On Mon, Jan 24, 2022 at 10:27 AM Song Liu <[email protected]> wrote:
> > >
> > > Are arches expected to allocate rw buffers in different ways? If not,
> > > I would consider putting this into the common code as well. Then
> > > arch-specific code would do something like
> > >
> > > header = bpf_jit_binary_alloc_pack(size, &prg_buf, &prg_addr, ...);
> > > ...
> > > /*
> > > * Generate code into prg_buf, the code should assume that its first
> > > * byte is located at prg_addr.
> > > */
> > > ...
> > > bpf_jit_binary_finalize_pack(header, prg_buf);
> > >
> > > where bpf_jit_binary_finalize_pack() would copy prg_buf to header and
> > > free it.
>
> It feels right, but bpf_jit_binary_finalize_pack() sounds 100% arch
> dependent. The only thing it will do is perform a copy via text_poke.
> What else?
>
> > I think this should work.
> >
> > We will need an API like: bpf_arch_text_copy, which uses text_poke_copy()
> > for x86_64 and s390_kernel_write() for x390. We will use bpf_arch_text_copy
> > to
> > 1) write header->size;
> > 2) do finally copy in bpf_jit_binary_finalize_pack().
>
> we can combine all text_poke operations into one.
>
> Can we add an 'image' pointer into struct bpf_binary_header ?

There is a 4-byte hole in bpf_binary_header. How about we put
image_offset there? Actually we only need 2 bytes for offset.

> Then do:
> int bpf_jit_binary_alloc_pack(size, &ro_hdr, &rw_hdr);
>
> ro_hdr->image would be the address used to compute offsets by JIT.

If we only do one text_poke(), we cannot write ro_hdr->image yet. We
can use ro_hdr + rw_hdr->image_offset instead.

> rw_hdr->image would point to kvmalloc-ed area for emitting insns.
> rw_hdr->size would already be populated.
>
> The JITs would write insns into rw_hdr->image including 'int 3' insns.
> At the end the JIT will do text_poke_copy(ro_hdr, rw_hdr, rw_hdr->size);
> That would be the only copy that will transfer everything into final
> location.
> Then kvfree(rw_hdr)

The only problem is the asymmetry of allocating rw_hdr from bpf/core.c,
and freeing it from arch/bpf_jit_comp.c. But it doesn't bother me too much.

Thanks,
Song

2022-01-26 08:38:20

by Alexei Starovoitov

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On Mon, Jan 24, 2022 at 11:21 PM Song Liu <[email protected]> wrote:
>
> On Mon, Jan 24, 2022 at 9:21 PM Alexei Starovoitov
> <[email protected]> wrote:
> >
> > On Mon, Jan 24, 2022 at 10:27 AM Song Liu <[email protected]> wrote:
> > > >
> > > > Are arches expected to allocate rw buffers in different ways? If not,
> > > > I would consider putting this into the common code as well. Then
> > > > arch-specific code would do something like
> > > >
> > > > header = bpf_jit_binary_alloc_pack(size, &prg_buf, &prg_addr, ...);
> > > > ...
> > > > /*
> > > > * Generate code into prg_buf, the code should assume that its first
> > > > * byte is located at prg_addr.
> > > > */
> > > > ...
> > > > bpf_jit_binary_finalize_pack(header, prg_buf);
> > > >
> > > > where bpf_jit_binary_finalize_pack() would copy prg_buf to header and
> > > > free it.
> >
> > It feels right, but bpf_jit_binary_finalize_pack() sounds 100% arch
> > dependent. The only thing it will do is perform a copy via text_poke.
> > What else?
> >
> > > I think this should work.
> > >
> > > We will need an API like: bpf_arch_text_copy, which uses text_poke_copy()
> > > for x86_64 and s390_kernel_write() for x390. We will use bpf_arch_text_copy
> > > to
> > > 1) write header->size;
> > > 2) do finally copy in bpf_jit_binary_finalize_pack().
> >
> > we can combine all text_poke operations into one.
> >
> > Can we add an 'image' pointer into struct bpf_binary_header ?
>
> There is a 4-byte hole in bpf_binary_header. How about we put
> image_offset there? Actually we only need 2 bytes for offset.
>
> > Then do:
> > int bpf_jit_binary_alloc_pack(size, &ro_hdr, &rw_hdr);
> >
> > ro_hdr->image would be the address used to compute offsets by JIT.
>
> If we only do one text_poke(), we cannot write ro_hdr->image yet. We
> can use ro_hdr + rw_hdr->image_offset instead.

Good points.
Maybe let's go back to Ilya's suggestion and return 4 pointers
from bpf_jit_binary_alloc_pack ?

> > rw_hdr->image would point to kvmalloc-ed area for emitting insns.
> > rw_hdr->size would already be populated.
> >
> > The JITs would write insns into rw_hdr->image including 'int 3' insns.
> > At the end the JIT will do text_poke_copy(ro_hdr, rw_hdr, rw_hdr->size);
> > That would be the only copy that will transfer everything into final
> > location.
> > Then kvfree(rw_hdr)
>
> The only problem is the asymmetry of allocating rw_hdr from bpf/core.c,
> and freeing it from arch/bpf_jit_comp.c. But it doesn't bother me too much.

Indeed. Asymmetry needs to be fixed.
Let's then pass 4 pointers back into
bpf_jit_binary_finalize_pack()
which will call arch dependent weak function to do text_poke_copy
or use default __weak function that returns eopnotsupp
and then kvfree the rw_hdr ?
I'd like to avoid callbacks. imo __weak is easier to follow.

2022-01-26 11:35:15

by Song Liu

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On Tue, Jan 25, 2022 at 12:00 PM Alexei Starovoitov
<[email protected]> wrote:
>
> On Mon, Jan 24, 2022 at 11:21 PM Song Liu <[email protected]> wrote:
> >
> > On Mon, Jan 24, 2022 at 9:21 PM Alexei Starovoitov
> > <[email protected]> wrote:
> > >
> > > On Mon, Jan 24, 2022 at 10:27 AM Song Liu <[email protected]> wrote:
> > > > >
> > > > > Are arches expected to allocate rw buffers in different ways? If not,
> > > > > I would consider putting this into the common code as well. Then
> > > > > arch-specific code would do something like
> > > > >
> > > > > header = bpf_jit_binary_alloc_pack(size, &prg_buf, &prg_addr, ...);
> > > > > ...
> > > > > /*
> > > > > * Generate code into prg_buf, the code should assume that its first
> > > > > * byte is located at prg_addr.
> > > > > */
> > > > > ...
> > > > > bpf_jit_binary_finalize_pack(header, prg_buf);
> > > > >
> > > > > where bpf_jit_binary_finalize_pack() would copy prg_buf to header and
> > > > > free it.
> > >
> > > It feels right, but bpf_jit_binary_finalize_pack() sounds 100% arch
> > > dependent. The only thing it will do is perform a copy via text_poke.
> > > What else?
> > >
> > > > I think this should work.
> > > >
> > > > We will need an API like: bpf_arch_text_copy, which uses text_poke_copy()
> > > > for x86_64 and s390_kernel_write() for x390. We will use bpf_arch_text_copy
> > > > to
> > > > 1) write header->size;
> > > > 2) do finally copy in bpf_jit_binary_finalize_pack().
> > >
> > > we can combine all text_poke operations into one.
> > >
> > > Can we add an 'image' pointer into struct bpf_binary_header ?
> >
> > There is a 4-byte hole in bpf_binary_header. How about we put
> > image_offset there? Actually we only need 2 bytes for offset.
> >
> > > Then do:
> > > int bpf_jit_binary_alloc_pack(size, &ro_hdr, &rw_hdr);
> > >
> > > ro_hdr->image would be the address used to compute offsets by JIT.
> >
> > If we only do one text_poke(), we cannot write ro_hdr->image yet. We
> > can use ro_hdr + rw_hdr->image_offset instead.
>
> Good points.
> Maybe let's go back to Ilya's suggestion and return 4 pointers
> from bpf_jit_binary_alloc_pack ?

How about we use image_offset, like:

struct bpf_binary_header {
u32 size;
u32 image_offset;
u8 image[] __aligned(BPF_IMAGE_ALIGNMENT);
};

Then we can use

image = (void *)header + header->image_offset;

In this way, we will only have two output pointers.

>
> > > rw_hdr->image would point to kvmalloc-ed area for emitting insns.
> > > rw_hdr->size would already be populated.
> > >
> > > The JITs would write insns into rw_hdr->image including 'int 3' insns.
> > > At the end the JIT will do text_poke_copy(ro_hdr, rw_hdr, rw_hdr->size);
> > > That would be the only copy that will transfer everything into final
> > > location.
> > > Then kvfree(rw_hdr)
> >
> > The only problem is the asymmetry of allocating rw_hdr from bpf/core.c,
> > and freeing it from arch/bpf_jit_comp.c. But it doesn't bother me too much.
>
> Indeed. Asymmetry needs to be fixed.
> Let's then pass 4 pointers back into
> bpf_jit_binary_finalize_pack()
> which will call arch dependent weak function to do text_poke_copy
> or use default __weak function that returns eopnotsupp
> and then kvfree the rw_hdr ?
> I'd like to avoid callbacks. imo __weak is easier to follow.

Yeah, I also like __weak function better.

Thanks,
Song

2022-01-26 12:37:31

by Alexei Starovoitov

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On Tue, Jan 25, 2022 at 2:25 PM Song Liu <[email protected]> wrote:
>
> On Tue, Jan 25, 2022 at 12:00 PM Alexei Starovoitov
> <[email protected]> wrote:
> >
> > On Mon, Jan 24, 2022 at 11:21 PM Song Liu <[email protected]> wrote:
> > >
> > > On Mon, Jan 24, 2022 at 9:21 PM Alexei Starovoitov
> > > <[email protected]> wrote:
> > > >
> > > > On Mon, Jan 24, 2022 at 10:27 AM Song Liu <[email protected]> wrote:
> > > > > >
> > > > > > Are arches expected to allocate rw buffers in different ways? If not,
> > > > > > I would consider putting this into the common code as well. Then
> > > > > > arch-specific code would do something like
> > > > > >
> > > > > > header = bpf_jit_binary_alloc_pack(size, &prg_buf, &prg_addr, ...);
> > > > > > ...
> > > > > > /*
> > > > > > * Generate code into prg_buf, the code should assume that its first
> > > > > > * byte is located at prg_addr.
> > > > > > */
> > > > > > ...
> > > > > > bpf_jit_binary_finalize_pack(header, prg_buf);
> > > > > >
> > > > > > where bpf_jit_binary_finalize_pack() would copy prg_buf to header and
> > > > > > free it.
> > > >
> > > > It feels right, but bpf_jit_binary_finalize_pack() sounds 100% arch
> > > > dependent. The only thing it will do is perform a copy via text_poke.
> > > > What else?
> > > >
> > > > > I think this should work.
> > > > >
> > > > > We will need an API like: bpf_arch_text_copy, which uses text_poke_copy()
> > > > > for x86_64 and s390_kernel_write() for x390. We will use bpf_arch_text_copy
> > > > > to
> > > > > 1) write header->size;
> > > > > 2) do finally copy in bpf_jit_binary_finalize_pack().
> > > >
> > > > we can combine all text_poke operations into one.
> > > >
> > > > Can we add an 'image' pointer into struct bpf_binary_header ?
> > >
> > > There is a 4-byte hole in bpf_binary_header. How about we put
> > > image_offset there? Actually we only need 2 bytes for offset.
> > >
> > > > Then do:
> > > > int bpf_jit_binary_alloc_pack(size, &ro_hdr, &rw_hdr);
> > > >
> > > > ro_hdr->image would be the address used to compute offsets by JIT.
> > >
> > > If we only do one text_poke(), we cannot write ro_hdr->image yet. We
> > > can use ro_hdr + rw_hdr->image_offset instead.
> >
> > Good points.
> > Maybe let's go back to Ilya's suggestion and return 4 pointers
> > from bpf_jit_binary_alloc_pack ?
>
> How about we use image_offset, like:
>
> struct bpf_binary_header {
> u32 size;
> u32 image_offset;
> u8 image[] __aligned(BPF_IMAGE_ALIGNMENT);
> };
>
> Then we can use
>
> image = (void *)header + header->image_offset;

I'm not excited about it, since it leaks header details into JITs.
Looks like we don't need JIT to be aware of it.
How about we do random() % roundup(sizeof(struct bpf_binary_header), 64)
to pick the image start and populate
image-sizeof(struct bpf_binary_header) range
with 'int 3'.
This way we can completely hide binary_header inside generic code.
The bpf_jit_binary_alloc_pack() would return ro_image and rw_image only.
And JIT would pass them back into bpf_jit_binary_finalize_pack().
From the image pointer it would be trivial to get to binary_header with &63.
The 128 byte offset that we use today was chosen arbitrarily.
We were burning the whole page for a single program, so 128 bytes zone
at the front was ok.
Now we will be packing progs rounded up to 64 bytes, so it's better
to avoid wasting those 128 bytes regardless.

2022-01-26 13:00:57

by Song Liu

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On Tue, Jan 25, 2022 at 2:48 PM Alexei Starovoitov
<[email protected]> wrote:
>
> On Tue, Jan 25, 2022 at 2:25 PM Song Liu <[email protected]> wrote:
> >
> > On Tue, Jan 25, 2022 at 12:00 PM Alexei Starovoitov
> > <[email protected]> wrote:
> > >
> > > On Mon, Jan 24, 2022 at 11:21 PM Song Liu <[email protected]> wrote:
> > > >
> > > > On Mon, Jan 24, 2022 at 9:21 PM Alexei Starovoitov
> > > > <[email protected]> wrote:
> > > > >
> > > > > On Mon, Jan 24, 2022 at 10:27 AM Song Liu <[email protected]> wrote:
> > > > > > >
> > > > > > > Are arches expected to allocate rw buffers in different ways? If not,
> > > > > > > I would consider putting this into the common code as well. Then
> > > > > > > arch-specific code would do something like
> > > > > > >
> > > > > > > header = bpf_jit_binary_alloc_pack(size, &prg_buf, &prg_addr, ...);
> > > > > > > ...
> > > > > > > /*
> > > > > > > * Generate code into prg_buf, the code should assume that its first
> > > > > > > * byte is located at prg_addr.
> > > > > > > */
> > > > > > > ...
> > > > > > > bpf_jit_binary_finalize_pack(header, prg_buf);
> > > > > > >
> > > > > > > where bpf_jit_binary_finalize_pack() would copy prg_buf to header and
> > > > > > > free it.
> > > > >
> > > > > It feels right, but bpf_jit_binary_finalize_pack() sounds 100% arch
> > > > > dependent. The only thing it will do is perform a copy via text_poke.
> > > > > What else?
> > > > >
> > > > > > I think this should work.
> > > > > >
> > > > > > We will need an API like: bpf_arch_text_copy, which uses text_poke_copy()
> > > > > > for x86_64 and s390_kernel_write() for x390. We will use bpf_arch_text_copy
> > > > > > to
> > > > > > 1) write header->size;
> > > > > > 2) do finally copy in bpf_jit_binary_finalize_pack().
> > > > >
> > > > > we can combine all text_poke operations into one.
> > > > >
> > > > > Can we add an 'image' pointer into struct bpf_binary_header ?
> > > >
> > > > There is a 4-byte hole in bpf_binary_header. How about we put
> > > > image_offset there? Actually we only need 2 bytes for offset.
> > > >
> > > > > Then do:
> > > > > int bpf_jit_binary_alloc_pack(size, &ro_hdr, &rw_hdr);
> > > > >
> > > > > ro_hdr->image would be the address used to compute offsets by JIT.
> > > >
> > > > If we only do one text_poke(), we cannot write ro_hdr->image yet. We
> > > > can use ro_hdr + rw_hdr->image_offset instead.
> > >
> > > Good points.
> > > Maybe let's go back to Ilya's suggestion and return 4 pointers
> > > from bpf_jit_binary_alloc_pack ?
> >
> > How about we use image_offset, like:
> >
> > struct bpf_binary_header {
> > u32 size;
> > u32 image_offset;
> > u8 image[] __aligned(BPF_IMAGE_ALIGNMENT);
> > };
> >
> > Then we can use
> >
> > image = (void *)header + header->image_offset;
>
> I'm not excited about it, since it leaks header details into JITs.
> Looks like we don't need JIT to be aware of it.
> How about we do random() % roundup(sizeof(struct bpf_binary_header), 64)
> to pick the image start and populate
> image-sizeof(struct bpf_binary_header) range
> with 'int 3'.
> This way we can completely hide binary_header inside generic code.
> The bpf_jit_binary_alloc_pack() would return ro_image and rw_image only.
> And JIT would pass them back into bpf_jit_binary_finalize_pack().
> From the image pointer it would be trivial to get to binary_header with &63.
> The 128 byte offset that we use today was chosen arbitrarily.
> We were burning the whole page for a single program, so 128 bytes zone
> at the front was ok.
> Now we will be packing progs rounded up to 64 bytes, so it's better
> to avoid wasting those 128 bytes regardless.

In bpf_jit_binary_hdr(), we calculate header as image & PAGE_MASK.
If we want s/PAGE_MASK/63 for x86_64, we will have different versions
of bpf_jit_binary_hdr(). It is not on any hot path, so we can use __weak for
it. Other than this, I think the solution works fine.

Thanks,
Song

2022-01-26 13:46:13

by Alexei Starovoitov

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On Tue, Jan 25, 2022 at 3:09 PM Song Liu <[email protected]> wrote:
>
> On Tue, Jan 25, 2022 at 2:48 PM Alexei Starovoitov
> <[email protected]> wrote:
> >
> > On Tue, Jan 25, 2022 at 2:25 PM Song Liu <[email protected]> wrote:
> > >
> > > On Tue, Jan 25, 2022 at 12:00 PM Alexei Starovoitov
> > > <[email protected]> wrote:
> > > >
> > > > On Mon, Jan 24, 2022 at 11:21 PM Song Liu <[email protected]> wrote:
> > > > >
> > > > > On Mon, Jan 24, 2022 at 9:21 PM Alexei Starovoitov
> > > > > <[email protected]> wrote:
> > > > > >
> > > > > > On Mon, Jan 24, 2022 at 10:27 AM Song Liu <[email protected]> wrote:
> > > > > > > >
> > > > > > > > Are arches expected to allocate rw buffers in different ways? If not,
> > > > > > > > I would consider putting this into the common code as well. Then
> > > > > > > > arch-specific code would do something like
> > > > > > > >
> > > > > > > > header = bpf_jit_binary_alloc_pack(size, &prg_buf, &prg_addr, ...);
> > > > > > > > ...
> > > > > > > > /*
> > > > > > > > * Generate code into prg_buf, the code should assume that its first
> > > > > > > > * byte is located at prg_addr.
> > > > > > > > */
> > > > > > > > ...
> > > > > > > > bpf_jit_binary_finalize_pack(header, prg_buf);
> > > > > > > >
> > > > > > > > where bpf_jit_binary_finalize_pack() would copy prg_buf to header and
> > > > > > > > free it.
> > > > > >
> > > > > > It feels right, but bpf_jit_binary_finalize_pack() sounds 100% arch
> > > > > > dependent. The only thing it will do is perform a copy via text_poke.
> > > > > > What else?
> > > > > >
> > > > > > > I think this should work.
> > > > > > >
> > > > > > > We will need an API like: bpf_arch_text_copy, which uses text_poke_copy()
> > > > > > > for x86_64 and s390_kernel_write() for x390. We will use bpf_arch_text_copy
> > > > > > > to
> > > > > > > 1) write header->size;
> > > > > > > 2) do finally copy in bpf_jit_binary_finalize_pack().
> > > > > >
> > > > > > we can combine all text_poke operations into one.
> > > > > >
> > > > > > Can we add an 'image' pointer into struct bpf_binary_header ?
> > > > >
> > > > > There is a 4-byte hole in bpf_binary_header. How about we put
> > > > > image_offset there? Actually we only need 2 bytes for offset.
> > > > >
> > > > > > Then do:
> > > > > > int bpf_jit_binary_alloc_pack(size, &ro_hdr, &rw_hdr);
> > > > > >
> > > > > > ro_hdr->image would be the address used to compute offsets by JIT.
> > > > >
> > > > > If we only do one text_poke(), we cannot write ro_hdr->image yet. We
> > > > > can use ro_hdr + rw_hdr->image_offset instead.
> > > >
> > > > Good points.
> > > > Maybe let's go back to Ilya's suggestion and return 4 pointers
> > > > from bpf_jit_binary_alloc_pack ?
> > >
> > > How about we use image_offset, like:
> > >
> > > struct bpf_binary_header {
> > > u32 size;
> > > u32 image_offset;
> > > u8 image[] __aligned(BPF_IMAGE_ALIGNMENT);
> > > };
> > >
> > > Then we can use
> > >
> > > image = (void *)header + header->image_offset;
> >
> > I'm not excited about it, since it leaks header details into JITs.
> > Looks like we don't need JIT to be aware of it.
> > How about we do random() % roundup(sizeof(struct bpf_binary_header), 64)
> > to pick the image start and populate
> > image-sizeof(struct bpf_binary_header) range
> > with 'int 3'.
> > This way we can completely hide binary_header inside generic code.
> > The bpf_jit_binary_alloc_pack() would return ro_image and rw_image only.
> > And JIT would pass them back into bpf_jit_binary_finalize_pack().
> > From the image pointer it would be trivial to get to binary_header with &63.
> > The 128 byte offset that we use today was chosen arbitrarily.
> > We were burning the whole page for a single program, so 128 bytes zone
> > at the front was ok.
> > Now we will be packing progs rounded up to 64 bytes, so it's better
> > to avoid wasting those 128 bytes regardless.
>
> In bpf_jit_binary_hdr(), we calculate header as image & PAGE_MASK.
> If we want s/PAGE_MASK/63 for x86_64, we will have different versions
> of bpf_jit_binary_hdr(). It is not on any hot path, so we can use __weak for
> it. Other than this, I think the solution works fine.

I think it can stay generic.

The existing bpf_jit_binary_hdr() will do & PAGE_MASK
while bpf_jit_binary_hdr_pack() will do & 63.



> Thanks,
> Song

2022-01-26 13:46:41

by Song Liu

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On Tue, Jan 25, 2022 at 4:38 PM Alexei Starovoitov
<[email protected]> wrote:
>
> On Tue, Jan 25, 2022 at 3:09 PM Song Liu <[email protected]> wrote:
> >
> > On Tue, Jan 25, 2022 at 2:48 PM Alexei Starovoitov
> > <[email protected]> wrote:
> > >
> > > On Tue, Jan 25, 2022 at 2:25 PM Song Liu <[email protected]> wrote:
> > > >
> > > > On Tue, Jan 25, 2022 at 12:00 PM Alexei Starovoitov
> > > > <[email protected]> wrote:
> > > > >
> > > > > On Mon, Jan 24, 2022 at 11:21 PM Song Liu <[email protected]> wrote:
> > > > > >
> > > > > > On Mon, Jan 24, 2022 at 9:21 PM Alexei Starovoitov
> > > > > > <[email protected]> wrote:
> > > > > > >
> > > > > > > On Mon, Jan 24, 2022 at 10:27 AM Song Liu <[email protected]> wrote:
> > > > > > > > >
> > > > > > > > > Are arches expected to allocate rw buffers in different ways? If not,
> > > > > > > > > I would consider putting this into the common code as well. Then
> > > > > > > > > arch-specific code would do something like
> > > > > > > > >
> > > > > > > > > header = bpf_jit_binary_alloc_pack(size, &prg_buf, &prg_addr, ...);
> > > > > > > > > ...
> > > > > > > > > /*
> > > > > > > > > * Generate code into prg_buf, the code should assume that its first
> > > > > > > > > * byte is located at prg_addr.
> > > > > > > > > */
> > > > > > > > > ...
> > > > > > > > > bpf_jit_binary_finalize_pack(header, prg_buf);
> > > > > > > > >
> > > > > > > > > where bpf_jit_binary_finalize_pack() would copy prg_buf to header and
> > > > > > > > > free it.
> > > > > > >
> > > > > > > It feels right, but bpf_jit_binary_finalize_pack() sounds 100% arch
> > > > > > > dependent. The only thing it will do is perform a copy via text_poke.
> > > > > > > What else?
> > > > > > >
> > > > > > > > I think this should work.
> > > > > > > >
> > > > > > > > We will need an API like: bpf_arch_text_copy, which uses text_poke_copy()
> > > > > > > > for x86_64 and s390_kernel_write() for x390. We will use bpf_arch_text_copy
> > > > > > > > to
> > > > > > > > 1) write header->size;
> > > > > > > > 2) do finally copy in bpf_jit_binary_finalize_pack().
> > > > > > >
> > > > > > > we can combine all text_poke operations into one.
> > > > > > >
> > > > > > > Can we add an 'image' pointer into struct bpf_binary_header ?
> > > > > >
> > > > > > There is a 4-byte hole in bpf_binary_header. How about we put
> > > > > > image_offset there? Actually we only need 2 bytes for offset.
> > > > > >
> > > > > > > Then do:
> > > > > > > int bpf_jit_binary_alloc_pack(size, &ro_hdr, &rw_hdr);
> > > > > > >
> > > > > > > ro_hdr->image would be the address used to compute offsets by JIT.
> > > > > >
> > > > > > If we only do one text_poke(), we cannot write ro_hdr->image yet. We
> > > > > > can use ro_hdr + rw_hdr->image_offset instead.
> > > > >
> > > > > Good points.
> > > > > Maybe let's go back to Ilya's suggestion and return 4 pointers
> > > > > from bpf_jit_binary_alloc_pack ?
> > > >
> > > > How about we use image_offset, like:
> > > >
> > > > struct bpf_binary_header {
> > > > u32 size;
> > > > u32 image_offset;
> > > > u8 image[] __aligned(BPF_IMAGE_ALIGNMENT);
> > > > };
> > > >
> > > > Then we can use
> > > >
> > > > image = (void *)header + header->image_offset;
> > >
> > > I'm not excited about it, since it leaks header details into JITs.
> > > Looks like we don't need JIT to be aware of it.
> > > How about we do random() % roundup(sizeof(struct bpf_binary_header), 64)
> > > to pick the image start and populate
> > > image-sizeof(struct bpf_binary_header) range
> > > with 'int 3'.
> > > This way we can completely hide binary_header inside generic code.
> > > The bpf_jit_binary_alloc_pack() would return ro_image and rw_image only.
> > > And JIT would pass them back into bpf_jit_binary_finalize_pack().
> > > From the image pointer it would be trivial to get to binary_header with &63.
> > > The 128 byte offset that we use today was chosen arbitrarily.
> > > We were burning the whole page for a single program, so 128 bytes zone
> > > at the front was ok.
> > > Now we will be packing progs rounded up to 64 bytes, so it's better
> > > to avoid wasting those 128 bytes regardless.
> >
> > In bpf_jit_binary_hdr(), we calculate header as image & PAGE_MASK.
> > If we want s/PAGE_MASK/63 for x86_64, we will have different versions
> > of bpf_jit_binary_hdr(). It is not on any hot path, so we can use __weak for
> > it. Other than this, I think the solution works fine.
>
> I think it can stay generic.
>
> The existing bpf_jit_binary_hdr() will do & PAGE_MASK
> while bpf_jit_binary_hdr_pack() will do & 63.

The problem with this approach is that we need bpf_prog_ksym_set_addr
to be smart to pick bpf_jit_binary_hdr() or bpf_jit_binary_hdr_pack().

Song

2022-01-26 14:58:58

by Alexei Starovoitov

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On Tue, Jan 25, 2022 at 4:50 PM Song Liu <[email protected]> wrote:
>
> On Tue, Jan 25, 2022 at 4:38 PM Alexei Starovoitov
> <[email protected]> wrote:
> >
> > On Tue, Jan 25, 2022 at 3:09 PM Song Liu <[email protected]> wrote:
> > >
> > > On Tue, Jan 25, 2022 at 2:48 PM Alexei Starovoitov
> > > <[email protected]> wrote:
> > > >
> > > > On Tue, Jan 25, 2022 at 2:25 PM Song Liu <[email protected]> wrote:
> > > > >
> > > > > On Tue, Jan 25, 2022 at 12:00 PM Alexei Starovoitov
> > > > > <[email protected]> wrote:
> > > > > >
> > > > > > On Mon, Jan 24, 2022 at 11:21 PM Song Liu <[email protected]> wrote:
> > > > > > >
> > > > > > > On Mon, Jan 24, 2022 at 9:21 PM Alexei Starovoitov
> > > > > > > <[email protected]> wrote:
> > > > > > > >
> > > > > > > > On Mon, Jan 24, 2022 at 10:27 AM Song Liu <[email protected]> wrote:
> > > > > > > > > >
> > > > > > > > > > Are arches expected to allocate rw buffers in different ways? If not,
> > > > > > > > > > I would consider putting this into the common code as well. Then
> > > > > > > > > > arch-specific code would do something like
> > > > > > > > > >
> > > > > > > > > > header = bpf_jit_binary_alloc_pack(size, &prg_buf, &prg_addr, ...);
> > > > > > > > > > ...
> > > > > > > > > > /*
> > > > > > > > > > * Generate code into prg_buf, the code should assume that its first
> > > > > > > > > > * byte is located at prg_addr.
> > > > > > > > > > */
> > > > > > > > > > ...
> > > > > > > > > > bpf_jit_binary_finalize_pack(header, prg_buf);
> > > > > > > > > >
> > > > > > > > > > where bpf_jit_binary_finalize_pack() would copy prg_buf to header and
> > > > > > > > > > free it.
> > > > > > > >
> > > > > > > > It feels right, but bpf_jit_binary_finalize_pack() sounds 100% arch
> > > > > > > > dependent. The only thing it will do is perform a copy via text_poke.
> > > > > > > > What else?
> > > > > > > >
> > > > > > > > > I think this should work.
> > > > > > > > >
> > > > > > > > > We will need an API like: bpf_arch_text_copy, which uses text_poke_copy()
> > > > > > > > > for x86_64 and s390_kernel_write() for x390. We will use bpf_arch_text_copy
> > > > > > > > > to
> > > > > > > > > 1) write header->size;
> > > > > > > > > 2) do finally copy in bpf_jit_binary_finalize_pack().
> > > > > > > >
> > > > > > > > we can combine all text_poke operations into one.
> > > > > > > >
> > > > > > > > Can we add an 'image' pointer into struct bpf_binary_header ?
> > > > > > >
> > > > > > > There is a 4-byte hole in bpf_binary_header. How about we put
> > > > > > > image_offset there? Actually we only need 2 bytes for offset.
> > > > > > >
> > > > > > > > Then do:
> > > > > > > > int bpf_jit_binary_alloc_pack(size, &ro_hdr, &rw_hdr);
> > > > > > > >
> > > > > > > > ro_hdr->image would be the address used to compute offsets by JIT.
> > > > > > >
> > > > > > > If we only do one text_poke(), we cannot write ro_hdr->image yet. We
> > > > > > > can use ro_hdr + rw_hdr->image_offset instead.
> > > > > >
> > > > > > Good points.
> > > > > > Maybe let's go back to Ilya's suggestion and return 4 pointers
> > > > > > from bpf_jit_binary_alloc_pack ?
> > > > >
> > > > > How about we use image_offset, like:
> > > > >
> > > > > struct bpf_binary_header {
> > > > > u32 size;
> > > > > u32 image_offset;
> > > > > u8 image[] __aligned(BPF_IMAGE_ALIGNMENT);
> > > > > };
> > > > >
> > > > > Then we can use
> > > > >
> > > > > image = (void *)header + header->image_offset;
> > > >
> > > > I'm not excited about it, since it leaks header details into JITs.
> > > > Looks like we don't need JIT to be aware of it.
> > > > How about we do random() % roundup(sizeof(struct bpf_binary_header), 64)
> > > > to pick the image start and populate
> > > > image-sizeof(struct bpf_binary_header) range
> > > > with 'int 3'.
> > > > This way we can completely hide binary_header inside generic code.
> > > > The bpf_jit_binary_alloc_pack() would return ro_image and rw_image only.
> > > > And JIT would pass them back into bpf_jit_binary_finalize_pack().
> > > > From the image pointer it would be trivial to get to binary_header with &63.
> > > > The 128 byte offset that we use today was chosen arbitrarily.
> > > > We were burning the whole page for a single program, so 128 bytes zone
> > > > at the front was ok.
> > > > Now we will be packing progs rounded up to 64 bytes, so it's better
> > > > to avoid wasting those 128 bytes regardless.
> > >
> > > In bpf_jit_binary_hdr(), we calculate header as image & PAGE_MASK.
> > > If we want s/PAGE_MASK/63 for x86_64, we will have different versions
> > > of bpf_jit_binary_hdr(). It is not on any hot path, so we can use __weak for
> > > it. Other than this, I think the solution works fine.
> >
> > I think it can stay generic.
> >
> > The existing bpf_jit_binary_hdr() will do & PAGE_MASK
> > while bpf_jit_binary_hdr_pack() will do & 63.
>
> The problem with this approach is that we need bpf_prog_ksym_set_addr
> to be smart to pick bpf_jit_binary_hdr() or bpf_jit_binary_hdr_pack().

We can probably add a true JIT image size to bpf_prog_aux.
bpf_prog_ksym_set_addr() is approximating the end:
prog->aux->ksym.end = addr + hdr->pages * PAGE_SIZE
which doesn't have to include all the 'int 3' padding after the end.

Or add a flag to bpf_prog_aux.
Ideally bpf_jit_free() would stay generic too.

2022-01-26 15:06:58

by Song Liu

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On Tue, Jan 25, 2022 at 5:20 PM Alexei Starovoitov
<[email protected]> wrote:
>
> On Tue, Jan 25, 2022 at 4:50 PM Song Liu <[email protected]> wrote:
> >
> > On Tue, Jan 25, 2022 at 4:38 PM Alexei Starovoitov
> > <[email protected]> wrote:
> > >
[...]
> > > >
> > > > In bpf_jit_binary_hdr(), we calculate header as image & PAGE_MASK.
> > > > If we want s/PAGE_MASK/63 for x86_64, we will have different versions
> > > > of bpf_jit_binary_hdr(). It is not on any hot path, so we can use __weak for
> > > > it. Other than this, I think the solution works fine.
> > >
> > > I think it can stay generic.
> > >
> > > The existing bpf_jit_binary_hdr() will do & PAGE_MASK
> > > while bpf_jit_binary_hdr_pack() will do & 63.
> >
> > The problem with this approach is that we need bpf_prog_ksym_set_addr
> > to be smart to pick bpf_jit_binary_hdr() or bpf_jit_binary_hdr_pack().
>
> We can probably add a true JIT image size to bpf_prog_aux.
> bpf_prog_ksym_set_addr() is approximating the end:
> prog->aux->ksym.end = addr + hdr->pages * PAGE_SIZE
> which doesn't have to include all the 'int 3' padding after the end.
>
> Or add a flag to bpf_prog_aux.
> Ideally bpf_jit_free() would stay generic too.

Both ideas sound promising. Let me try to implement them and see
which is better (or maybe we get both).

Thanks for the suggestions!
Song

2022-01-26 15:07:32

by Song Liu

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On Tue, Jan 25, 2022 at 5:28 PM Song Liu <[email protected]> wrote:
>
> On Tue, Jan 25, 2022 at 5:20 PM Alexei Starovoitov
> <[email protected]> wrote:
> >
> > On Tue, Jan 25, 2022 at 4:50 PM Song Liu <[email protected]> wrote:
> > >
> > > On Tue, Jan 25, 2022 at 4:38 PM Alexei Starovoitov
> > > <[email protected]> wrote:
> > > >
> [...]
> > > > >
> > > > > In bpf_jit_binary_hdr(), we calculate header as image & PAGE_MASK.
> > > > > If we want s/PAGE_MASK/63 for x86_64, we will have different versions
> > > > > of bpf_jit_binary_hdr(). It is not on any hot path, so we can use __weak for
> > > > > it. Other than this, I think the solution works fine.
> > > >
> > > > I think it can stay generic.
> > > >
> > > > The existing bpf_jit_binary_hdr() will do & PAGE_MASK
> > > > while bpf_jit_binary_hdr_pack() will do & 63.
> > >
> > > The problem with this approach is that we need bpf_prog_ksym_set_addr
> > > to be smart to pick bpf_jit_binary_hdr() or bpf_jit_binary_hdr_pack().
> >
> > We can probably add a true JIT image size to bpf_prog_aux.
> > bpf_prog_ksym_set_addr() is approximating the end:
> > prog->aux->ksym.end = addr + hdr->pages * PAGE_SIZE
> > which doesn't have to include all the 'int 3' padding after the end.

Actually, we can use prog->jited_len in bpf_prog_ksym_set_addr(), right?

Song

2022-01-26 15:14:23

by Alexei Starovoitov

[permalink] [raw]
Subject: Re: [PATCH v6 bpf-next 6/7] bpf: introduce bpf_prog_pack allocator

On 1/25/22 5:31 PM, Song Liu wrote:
> On Tue, Jan 25, 2022 at 5:28 PM Song Liu <[email protected]> wrote:
>>
>> On Tue, Jan 25, 2022 at 5:20 PM Alexei Starovoitov
>> <[email protected]> wrote:
>>>
>>> On Tue, Jan 25, 2022 at 4:50 PM Song Liu <[email protected]> wrote:
>>>>
>>>> On Tue, Jan 25, 2022 at 4:38 PM Alexei Starovoitov
>>>> <[email protected]> wrote:
>>>>>
>> [...]
>>>>>>
>>>>>> In bpf_jit_binary_hdr(), we calculate header as image & PAGE_MASK.
>>>>>> If we want s/PAGE_MASK/63 for x86_64, we will have different versions
>>>>>> of bpf_jit_binary_hdr(). It is not on any hot path, so we can use __weak for
>>>>>> it. Other than this, I think the solution works fine.
>>>>>
>>>>> I think it can stay generic.
>>>>>
>>>>> The existing bpf_jit_binary_hdr() will do & PAGE_MASK
>>>>> while bpf_jit_binary_hdr_pack() will do & 63.
>>>>
>>>> The problem with this approach is that we need bpf_prog_ksym_set_addr
>>>> to be smart to pick bpf_jit_binary_hdr() or bpf_jit_binary_hdr_pack().
>>>
>>> We can probably add a true JIT image size to bpf_prog_aux.
>>> bpf_prog_ksym_set_addr() is approximating the end:
>>> prog->aux->ksym.end = addr + hdr->pages * PAGE_SIZE
>>> which doesn't have to include all the 'int 3' padding after the end.
>
> Actually, we can use prog->jited_len in bpf_prog_ksym_set_addr(), right?

Lol. Yeah. We should. Looks like somebody remembers their own
code in perf_event_bpf_emit_ksymbols() ;)