[bpf-next,04/16] bpf: Introduce bpf_arena.

Message ID	20240206220441.38311-5-alexei.starovoitov@gmail.com (mailing list archive)
State	New
Headers	show Return-Path: <owner-linux-mm@kvack.org> From: Alexei Starovoitov <alexei.starovoitov@gmail.com> To: bpf@vger.kernel.org Cc: daniel@iogearbox.net, andrii@kernel.org, martin.lau@kernel.org, memxor@gmail.com, eddyz87@gmail.com, tj@kernel.org, brho@google.com, hannes@cmpxchg.org, linux-mm@kvack.org, kernel-team@fb.com Subject: [PATCH bpf-next 04/16] bpf: Introduce bpf_arena. Date: Tue, 6 Feb 2024 14:04:29 -0800 Message-Id: <20240206220441.38311-5-alexei.starovoitov@gmail.com> In-Reply-To: <20240206220441.38311-1-alexei.starovoitov@gmail.com> References: <20240206220441.38311-1-alexei.starovoitov@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Sender: owner-linux-mm@kvack.org Precedence: bulk
Series	bpf: Introduce BPF arena. \| expand [bpf-next,00/16] bpf: Introduce BPF arena. [bpf-next,01/16] bpf: Allow kfuncs return 'void *' [bpf-next,02/16] bpf: Recognize '__map' suffix in kfunc arguments [bpf-next,03/16] mm: Expose vmap_pages_range() to the rest of the kernel. [bpf-next,04/16] bpf: Introduce bpf_arena. [bpf-next,05/16] bpf: Disasm support for cast_kern/user instructions. [bpf-next,06/16] bpf: Add x86-64 JIT support for PROBE_MEM32 pseudo instructions. [bpf-next,07/16] bpf: Add x86-64 JIT support for bpf_cast_user instruction. [bpf-next,08/16] bpf: Recognize cast_kern/user instructions in the verifier. [bpf-next,09/16] bpf: Recognize btf_decl_tag("arg:arena") as PTR_TO_ARENA. [bpf-next,10/16] libbpf: Add __arg_arena to bpf_helpers.h [bpf-next,11/16] libbpf: Add support for bpf_arena. [bpf-next,12/16] libbpf: Allow specifying 64-bit integers in map BTF. [bpf-next,13/16] bpf: Tell bpf programs kernel's PAGE_SIZE [bpf-next,14/16] bpf: Add helper macro bpf_arena_cast() [bpf-next,15/16] selftests/bpf: Add bpf_arena_list test. [bpf-next,16/16] selftests/bpf: Add bpf_arena_htab test.

Alexei Starovoitov Feb. 6, 2024, 10:04 p.m. UTC

From: Alexei Starovoitov <ast@kernel.org>

Introduce bpf_arena, which is a sparse shared memory region between the bpf
program and user space.

Use cases:
1. User space mmap-s bpf_arena and uses it as a traditional mmap-ed anonymous
   region, like memcached or any key/value storage. The bpf program implements an
   in-kernel accelerator. XDP prog can search for a key in bpf_arena and return a
   value without going to user space.
2. The bpf program builds arbitrary data structures in bpf_arena (hash tables,
   rb-trees, sparse arrays), while user space occasionally consumes it.
3. bpf_arena is a "heap" of memory from the bpf program's point of view. It is
   not shared with user space.

Initially, the kernel vm_area and user vma are not populated. User space can
fault in pages within the range. While servicing a page fault, bpf_arena logic
will insert a new page into the kernel and user vmas. The bpf program can
allocate pages from that region via bpf_arena_alloc_pages(). This kernel
function will insert pages into the kernel vm_area. The subsequent fault-in
from user space will populate that page into the user vma. The
BPF_F_SEGV_ON_FAULT flag at arena creation time can be used to prevent fault-in
from user space. In such a case, if a page is not allocated by the bpf program
and not present in the kernel vm_area, the user process will segfault. This is
useful for use cases 2 and 3 above.

bpf_arena_alloc_pages() is similar to user space mmap(). It allocates pages
either at a specific address within the arena or allocates a range with the
maple tree. bpf_arena_free_pages() is analogous to munmap(), which frees pages
and removes the range from the kernel vm_area and from user process vmas.

bpf_arena can be used as a bpf program "heap" of up to 4GB. The memory is not
shared with user space. This is use case 3. In such a case, the
BPF_F_NO_USER_CONV flag is recommended. It will tell the verifier to treat the
rX = bpf_arena_cast_user(rY) instruction as a 32-bit move wX = wY, which will
improve bpf prog performance. Otherwise, bpf_arena_cast_user is translated by
JIT to conditionally add the upper 32 bits of user vm_start (if the pointer is
not NULL) to arena pointers before they are stored into memory. This way, user
space sees them as valid 64-bit pointers.

Diff https://github.com/llvm/llvm-project/pull/79902 taught LLVM BPF backend to
generate the bpf_cast_kern() instruction before dereference of the arena
pointer and the bpf_cast_user() instruction when the arena pointer is formed.
In a typical bpf program there will be very few bpf_cast_user().

From LLVM's point of view, arena pointers are tagged as
__attribute__((address_space(1))). Hence, clang provides helpful diagnostics
when pointers cross address space. Libbpf and the kernel support only
address_space == 1. All other address space identifiers are reserved.

rX = bpf_cast_kern(rY, addr_space) tells the verifier that
rX->type = PTR_TO_ARENA. Any further operations on PTR_TO_ARENA register have
to be in the 32-bit domain. The verifier will mark load/store through
PTR_TO_ARENA with PROBE_MEM32. JIT will generate them as
kern_vm_start + 32bit_addr memory accesses. The behavior is similar to
copy_from_kernel_nofault() except that no address checks are necessary. The
address is guaranteed to be in the 4GB range. If the page is not present, the
destination register is zeroed on read, and the operation is ignored on write.

rX = bpf_cast_user(rY, addr_space) tells the verifier that
rX->type = unknown scalar. If arena->map_flags has BPF_F_NO_USER_CONV set, then
the verifier converts cast_user to mov32. Otherwise, JIT will emit native code
equivalent to:
rX = (u32)rY;
if (rX)
  rX |= arena->user_vm_start & ~(u64)~0U;

After such conversion, the pointer becomes a valid user pointer within
bpf_arena range. The user process can access data structures created in
bpf_arena without any additional computations. For example, a linked list built
by a bpf program can be walked natively by user space.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf.h            |   5 +-
 include/linux/bpf_types.h      |   1 +
 include/uapi/linux/bpf.h       |   7 +
 kernel/bpf/Makefile            |   3 +
 kernel/bpf/arena.c             | 518 +++++++++++++++++++++++++++++++++
 kernel/bpf/core.c              |  11 +
 kernel/bpf/syscall.c           |   3 +
 kernel/bpf/verifier.c          |   1 +
 tools/include/uapi/linux/bpf.h |   7 +
 9 files changed, 554 insertions(+), 2 deletions(-)
 create mode 100644 kernel/bpf/arena.c

Barret Rhoden Feb. 7, 2024, 6:40 p.m. UTC | #1

On 2/6/24 17:04, Alexei Starovoitov wrote:
> +
> +static long compute_pgoff(struct bpf_arena *arena, long uaddr)
> +{
> +	return (u32)(uaddr - (u32)arena->user_vm_start) >> PAGE_SHIFT;
> +}
> +
> +#define MT_ENTRY ((void *)&arena_map_ops) /* unused. has to be valid pointer */
> +
> +/*
> + * Reserve a "zero page", so that bpf prog and user space never see
> + * a pointer to arena with lower 32 bits being zero.
> + * bpf_cast_user() promotes it to full 64-bit NULL.
> + */
> +static int reserve_zero_page(struct bpf_arena *arena)
> +{
> +	long pgoff = compute_pgoff(arena, 0);
> +
> +	return mtree_insert(&arena->mt, pgoff, MT_ENTRY, GFP_KERNEL);
> +}
> +

this is pretty tricky, and i think i didn't understand it at first.

you're punching a hole in the arena, such that BPF won't allocate it via 
arena_alloc_pages().  thus BPF won't 'produce' an object with a pointer 
ending in 0x00000000.

depending on where userspace mmaps the arena, that hole may or may not 
be the first page in the array.  if userspace mmaps it to a 4GB aligned 
virtual address, it'll be page 0.  but it could be at some arbitrary 
offset within the 4GB arena.

that arbitrariness makes it harder for a BPF program to do its own 
allocations within the arena.  i'm planning on carving up the 4GB arena 
for my own purposes, managed by BPF, with the expectation that i'll be 
able to allocate any 'virtual address' within the arena.  but there's a 
magic page that won't be usable.

i can certainly live with this.  just mmap userspace to a 4GB aligned 
address + PGSIZE, so that the last page in the arena is page 0.  but 
it's a little weird.

though i think we'll have more serious issues if anyone accidentally 
tries to use that zero page.  BPF would get an EEXIST if they try to 
allocate it directly, but then page fault and die if they touched it, 
since there's no page.  i can live with that, if we force it to be the 
last page in the arena.

however, i think you need to add something to the fault handler (below) 
in case userspace touches that page:

[snip]
> +static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
> +{
> +	struct bpf_map *map = vmf->vma->vm_file->private_data;
> +	struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
> +	struct page *page;
> +	long kbase, kaddr;
> +	int ret;
> +
> +	kbase = bpf_arena_get_kern_vm_start(arena);
> +	kaddr = kbase + (u32)(vmf->address & PAGE_MASK);
> +
> +	guard(mutex)(&arena->lock);
> +	page = vmalloc_to_page((void *)kaddr);
> +	if (page)
> +		/* already have a page vmap-ed */
> +		goto out;
> +
> +	if (arena->map.map_flags & BPF_F_SEGV_ON_FAULT)
> +		/* User space requested to segfault when page is not allocated by bpf prog */
> +		return VM_FAULT_SIGSEGV;
> +
> +	ret = mtree_insert(&arena->mt, vmf->pgoff, MT_ENTRY, GFP_KERNEL);
> +	if (ret == -EEXIST)
> +		return VM_FAULT_RETRY;

say this was the zero page.  vmalloc_to_page() failed, so we tried to 
insert.  we get EEXIST, since the slot is reserved.  we retry, since we 
were expecting the case where "no page, yet slot reserved" meant that 
BPF was in the middle of filling this page.

though i think you can fix this by just treating this as a SIGSEGV 
instead of RETRY.  when i made the original suggestion of making this a 
retry (in an email off list), that was before you had the arena mutex. 
now that you have the mutex, you shouldn't have the scenario where two 
threads are concurrently trying to fill a page.  i.e. mtree_insert + 
page_alloc + vmap are all atomic w.r.t. the mutex.

> +	if (ret)
> +		return VM_FAULT_SIGSEGV;
> +
> +	page = alloc_page(GFP_KERNEL | __GFP_ZERO);
> +	if (!page) {
> +		mtree_erase(&arena->mt, vmf->pgoff);
> +		return VM_FAULT_SIGSEGV;
> +	}
> +
> +	ret = vmap_pages_range(kaddr, kaddr + PAGE_SIZE, PAGE_KERNEL, &page, PAGE_SHIFT);
> +	if (ret) {
> +		mtree_erase(&arena->mt, vmf->pgoff);
> +		__free_page(page);
> +		return VM_FAULT_SIGSEGV;
> +	}
> +out:
> +	page_ref_add(page, 1);
> +	vmf->page = page;
> +	return 0;
> +}

[snip]

> +static int arena_map_mmap(struct bpf_map *map, struct vm_area_struct *vma)
> +{
> +	struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
> +	int err;
> +
> +	if (arena->user_vm_start && arena->user_vm_start != vma->vm_start)
> +		/*
> +		 * 1st user process can do mmap(NULL, ...) to pick user_vm_start
> +		 * 2nd user process must pass the same addr to mmap(addr, MAP_FIXED..);
> +		 *   or
> +		 * specify addr in map_extra at map creation time and
> +		 * use the same addr later with mmap(addr, MAP_FIXED..);
> +		 */
> +		return -EBUSY;
> +
> +	if (arena->user_vm_end && arena->user_vm_end != vma->vm_end)
> +		/* all user processes must have the same size of mmap-ed region */
> +		return -EBUSY;
> +
> +	if (vma->vm_end - vma->vm_start > 1ull << 32)
> +		/* Must not be bigger than 4Gb */
> +		return -E2BIG;
> +
> +	if (remember_vma(arena, vma))
> +		return -ENOMEM;
> +
> +	if (!arena->user_vm_start) {
> +		arena->user_vm_start = vma->vm_start;
> +		err = reserve_zero_page(arena);
> +		if (err)
> +			return err;
> +	}
> +	arena->user_vm_end = vma->vm_end;
> +	/*
> +	 * bpf_map_mmap() checks that it's being mmaped as VM_SHARED and
> +	 * clears VM_MAYEXEC. Set VM_DONTEXPAND as well to avoid
> +	 * potential change of user_vm_start.
> +	 */
> +	vm_flags_set(vma, VM_DONTEXPAND);
> +	vma->vm_ops = &arena_vm_ops;
> +	return 0;
> +}

i think this whole function needs to be protected by the mutex, or at 
least all the stuff relate to user_vm_{start,end}.  if you have to 
threads mmapping the region for the first time, you'll race on the 
values of user_vm_*.

[snip]

> +/*
> + * Allocate pages and vmap them into kernel vmalloc area.
> + * Later the pages will be mmaped into user space vma.
> + */
> +static long arena_alloc_pages(struct bpf_arena *arena, long uaddr, long page_cnt, int node_id)

instead of uaddr, can you change this to take an address relative to the 
arena ("arena virtual address"?)?  the caller of this is in BPF, and 
they don't easily know the user virtual address.  maybe even just pgoff 
directly.

additionally, you won't need to call compute_pgoff().  as it is now, i'm 
not sure what would happen if BPF did an arena_alloc with a uaddr and 
user_vm_start wasn't set yet.  actually, i guess it'd just be 0, so 
uaddr would act like an arena virtual address, up until the moment where 
someone mmaps, then it'd suddenly change to be a user virtual address.

either way, making uaddr an arena-relative addr would make all that moot.

> +{
> +	long page_cnt_max = (arena->user_vm_end - arena->user_vm_start) >> PAGE_SHIFT;

any time you compute_pgoff() or look at user_vm_{start,end}, maybe 
either hold the mutex, or only do it from mmap faults (where we know 
user_vm_start is already set).  o/w there might be subtle races where 
some other thread is mmapping the arena for the first time.

> +	u64 kern_vm_start = bpf_arena_get_kern_vm_start(arena);
> +	long pgoff = 0, kaddr, nr_pages = 0;
> +	struct page **pages;
> +	int ret, i;
> +
> +	if (page_cnt >= page_cnt_max)
> +		return 0;
> +
> +	if (uaddr) {
> +		if (uaddr & ~PAGE_MASK)
> +			return 0;
> +		pgoff = compute_pgoff(arena, uaddr);
> +		if (pgoff + page_cnt > page_cnt_max)
> +			/* requested address will be outside of user VMA */
> +			return 0;
> +	}
> +
> +	/* zeroing is needed, since alloc_pages_bulk_array() only fills in non-zero entries */
> +	pages = kvcalloc(page_cnt, sizeof(struct page *), GFP_KERNEL);
> +	if (!pages)
> +		return 0;
> +
> +	guard(mutex)(&arena->lock);
> +
> +	if (uaddr)
> +		ret = mtree_insert_range(&arena->mt, pgoff, pgoff + page_cnt,
> +					 MT_ENTRY, GFP_KERNEL);
> +	else
> +		ret = mtree_alloc_range(&arena->mt, &pgoff, MT_ENTRY,
> +					page_cnt, 0, page_cnt_max, GFP_KERNEL);
> +	if (ret)
> +		goto out_free_pages;
> +
> +	nr_pages = alloc_pages_bulk_array_node(GFP_KERNEL | __GFP_ZERO, node_id, page_cnt, pages);
> +	if (nr_pages != page_cnt)
> +		goto out;
> +
> +	kaddr = kern_vm_start + (u32)(arena->user_vm_start + pgoff * PAGE_SIZE);

adding user_vm_start here is pretty subtle.

so far i've been thinking that the mtree is the "address space" of the 
arena, in units of pages instead of bytes.  and pgoff is an address 
within the arena.  so mtree slot 0 is the 0th page of the 4GB region. 
and that "arena address space" is mapped at a kernel virtual address and 
a user virtual address (the same for all processes).

to convert user addresses (uaddr et al.) to arena addresses, we subtract 
user_vm_start, which makes sense.  that's what compute_pgoff() does.

i was expecting kaddr = kern_vm_start + pgoff * PGSIZE, essentially 
converting from arena address space to kernel virtual address.

instead, by adding user_vm_start and casting to u32, you're converting 
or shifting arena addresses to *another* arena address (user address, 
truncated to 4GB to keep it in the arena), and that is the one that the 
kernel will use.

is that correct?

my one concern is that there's some subtle wrap-around going on, and due 
to the shifting, kaddr can be very close to the end of the arena and 
page_cnt can be big enough to go outside the 4GB range.  we'd want it to 
wrap around.  e.g.

user_start_va = 0x1,fffff000
user_end_va =   0x2,fffff000
page_cnt_max = 0x100000 or whatever.  full 4GB range.

say we want to alloc at pgoff=0 (uaddr 0x1,fffff000), page_cnt = X.  you 
can get this pgoff either by doing mtree_insert_range or 
mtree_alloc_range on an arena with no allocations.

kaddr = kern_vm_start + 0xfffff000

the size of the vm area is 4GB + guard stuff, and we're right up against 
the end of it.

if page_cnt > the guard size, vmap_pages_range() would be called on 
something outside the vm area we reserved, which seems bad.  and even if 
it wasn't, what we want is for later page maps to start at the beginning 
of kern_vm_start.

the fix might be to just only map a page at a time - maybe a loop.  or 
detect when we're close to the edge and break it into two vmaps.  i feel 
like the loop would be easier to understand, but maybe less efficient.

> +	ret = vmap_pages_range(kaddr, kaddr + PAGE_SIZE * page_cnt, PAGE_KERNEL,
> +			       pages, PAGE_SHIFT);
> +	if (ret)
> +		goto out;
> +	kvfree(pages);
> +	return clear_lo32(arena->user_vm_start) + (u32)(kaddr - kern_vm_start);
> +out:
> +	mtree_erase(&arena->mt, pgoff);
> +out_free_pages:
> +	if (pages)
> +		for (i = 0; i < nr_pages; i++)
> +			__free_page(pages[i]);
> +	kvfree(pages);
> +	return 0;
> +}

thanks,
barret

> +
> +/*
> + * If page is present in vmalloc area, unmap it from vmalloc area,
> + * unmap it from all user space vma-s,
> + * and free it.
> + */
> +static void zap_pages(struct bpf_arena *arena, long uaddr, long page_cnt)
> +{
> +	struct vma_list *vml;
> +
> +	list_for_each_entry(vml, &arena->vma_list, head)
> +		zap_page_range_single(vml->vma, uaddr,
> +				      PAGE_SIZE * page_cnt, NULL);
> +}
> +
> +static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt)
> +{
> +	u64 full_uaddr, uaddr_end;
> +	long kaddr, pgoff, i;
> +	struct page *page;
> +
> +	/* only aligned lower 32-bit are relevant */
> +	uaddr = (u32)uaddr;
> +	uaddr &= PAGE_MASK;
> +	full_uaddr = clear_lo32(arena->user_vm_start) + uaddr;
> +	uaddr_end = min(arena->user_vm_end, full_uaddr + (page_cnt << PAGE_SHIFT));
> +	if (full_uaddr >= uaddr_end)
> +		return;
> +
> +	page_cnt = (uaddr_end - full_uaddr) >> PAGE_SHIFT;
> +
> +	kaddr = bpf_arena_get_kern_vm_start(arena) + uaddr;
> +
> +	guard(mutex)(&arena->lock);
> +
> +	pgoff = compute_pgoff(arena, uaddr);
> +	/* clear range */
> +	mtree_store_range(&arena->mt, pgoff, pgoff + page_cnt, NULL, GFP_KERNEL);
> +
> +	if (page_cnt > 1)
> +		/* bulk zap if multiple pages being freed */
> +		zap_pages(arena, full_uaddr, page_cnt);
> +
> +	for (i = 0; i < page_cnt; i++, kaddr += PAGE_SIZE, full_uaddr += PAGE_SIZE) {
> +		page = vmalloc_to_page((void *)kaddr);
> +		if (!page)
> +			continue;
> +		if (page_cnt == 1 && page_mapped(page)) /* mapped by some user process */
> +			zap_pages(arena, full_uaddr, 1);
> +		vunmap_range(kaddr, kaddr + PAGE_SIZE);
> +		__free_page(page);
> +	}
> +}
> +
> +__bpf_kfunc_start_defs();
> +
> +__bpf_kfunc void *bpf_arena_alloc_pages(void *p__map, void *addr__ign, u32 page_cnt,
> +					int node_id, u64 flags)
> +{
> +	struct bpf_map *map = p__map;
> +	struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
> +
> +	if (map->map_type != BPF_MAP_TYPE_ARENA || !arena->user_vm_start || flags)
> +		return NULL;
> +
> +	return (void *)arena_alloc_pages(arena, (long)addr__ign, page_cnt, node_id);
> +}
> +
> +__bpf_kfunc void bpf_arena_free_pages(void *p__map, void *ptr__ign, u32 page_cnt)
> +{
> +	struct bpf_map *map = p__map;
> +	struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
> +
> +	if (map->map_type != BPF_MAP_TYPE_ARENA || !arena->user_vm_start)
> +		return;
> +	arena_free_pages(arena, (long)ptr__ign, page_cnt);
> +}

Alexei Starovoitov Feb. 7, 2024, 8:55 p.m. UTC | #2

On Wed, Feb 7, 2024 at 10:40 AM Barret Rhoden <brho@google.com> wrote:
>
> On 2/6/24 17:04, Alexei Starovoitov wrote:
> > +
> > +static long compute_pgoff(struct bpf_arena *arena, long uaddr)
> > +{
> > +     return (u32)(uaddr - (u32)arena->user_vm_start) >> PAGE_SHIFT;
> > +}
> > +
> > +#define MT_ENTRY ((void *)&arena_map_ops) /* unused. has to be valid pointer */
> > +
> > +/*
> > + * Reserve a "zero page", so that bpf prog and user space never see
> > + * a pointer to arena with lower 32 bits being zero.
> > + * bpf_cast_user() promotes it to full 64-bit NULL.
> > + */
> > +static int reserve_zero_page(struct bpf_arena *arena)
> > +{
> > +     long pgoff = compute_pgoff(arena, 0);
> > +
> > +     return mtree_insert(&arena->mt, pgoff, MT_ENTRY, GFP_KERNEL);
> > +}
> > +
>
> this is pretty tricky, and i think i didn't understand it at first.
>
> you're punching a hole in the arena, such that BPF won't allocate it via
> arena_alloc_pages().  thus BPF won't 'produce' an object with a pointer
> ending in 0x00000000.
>
> depending on where userspace mmaps the arena, that hole may or may not
> be the first page in the array.  if userspace mmaps it to a 4GB aligned
> virtual address, it'll be page 0.  but it could be at some arbitrary
> offset within the 4GB arena.
>
> that arbitrariness makes it harder for a BPF program to do its own
> allocations within the arena.  i'm planning on carving up the 4GB arena
> for my own purposes, managed by BPF, with the expectation that i'll be
> able to allocate any 'virtual address' within the arena.  but there's a
> magic page that won't be usable.
>
> i can certainly live with this.  just mmap userspace to a 4GB aligned
> address + PGSIZE, so that the last page in the arena is page 0.  but
> it's a little weird.

Agree. I made the same conclusion while adding global variables to the arena.
From the compiler point of view all such global vars start at offset zero
and there is no way to just "move them up by a page".
For example in C code it will look like:
int __arena var1;
int __arena var2;

&var1 == user_vm_start
&var2 == user_vm_start + 4

If __ulong(map_extra,...) was used or mmap(addr, MAP_FIXED)
and was 4Gb aligned the lower 32-bits of &var1 address will be zero
and there is not much we can do about it.
We can tell LLVM to emit extra 8 byte padding to the arena section,
but it will be useless pad if the arena is not aligned to 4Gb.

Anyway, in the v2 I will remove this reserve_zero_page() logic.
It's causing more harm than good.

>
> though i think we'll have more serious issues if anyone accidentally
> tries to use that zero page.  BPF would get an EEXIST if they try to
> allocate it directly, but then page fault and die if they touched it,
> since there's no page.  i can live with that, if we force it to be the
> last page in the arena.
>
> however, i think you need to add something to the fault handler (below)
> in case userspace touches that page:
>
> [snip]
> > +static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
> > +{
> > +     struct bpf_map *map = vmf->vma->vm_file->private_data;
> > +     struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
> > +     struct page *page;
> > +     long kbase, kaddr;
> > +     int ret;
> > +
> > +     kbase = bpf_arena_get_kern_vm_start(arena);
> > +     kaddr = kbase + (u32)(vmf->address & PAGE_MASK);
> > +
> > +     guard(mutex)(&arena->lock);
> > +     page = vmalloc_to_page((void *)kaddr);
> > +     if (page)
> > +             /* already have a page vmap-ed */
> > +             goto out;
> > +
> > +     if (arena->map.map_flags & BPF_F_SEGV_ON_FAULT)
> > +             /* User space requested to segfault when page is not allocated by bpf prog */
> > +             return VM_FAULT_SIGSEGV;
> > +
> > +     ret = mtree_insert(&arena->mt, vmf->pgoff, MT_ENTRY, GFP_KERNEL);
> > +     if (ret == -EEXIST)
> > +             return VM_FAULT_RETRY;
>
> say this was the zero page.  vmalloc_to_page() failed, so we tried to
> insert.  we get EEXIST, since the slot is reserved.  we retry, since we
> were expecting the case where "no page, yet slot reserved" meant that
> BPF was in the middle of filling this page.

Yes. Great catch! I hit that too while playing with global vars.

>
> though i think you can fix this by just treating this as a SIGSEGV
> instead of RETRY.

Agree.

> when i made the original suggestion of making this a
> retry (in an email off list), that was before you had the arena mutex.
> now that you have the mutex, you shouldn't have the scenario where two
> threads are concurrently trying to fill a page.  i.e. mtree_insert +
> page_alloc + vmap are all atomic w.r.t. the mutex.

yes. mutex part makes sense.

> > +
> > +     if (!arena->user_vm_start) {
> > +             arena->user_vm_start = vma->vm_start;
> > +             err = reserve_zero_page(arena);
> > +             if (err)
> > +                     return err;
> > +     }
> > +     arena->user_vm_end = vma->vm_end;
> > +     /*
> > +      * bpf_map_mmap() checks that it's being mmaped as VM_SHARED and
> > +      * clears VM_MAYEXEC. Set VM_DONTEXPAND as well to avoid
> > +      * potential change of user_vm_start.
> > +      */
> > +     vm_flags_set(vma, VM_DONTEXPAND);
> > +     vma->vm_ops = &arena_vm_ops;
> > +     return 0;
> > +}
>
> i think this whole function needs to be protected by the mutex, or at
> least all the stuff relate to user_vm_{start,end}.  if you have to
> threads mmapping the region for the first time, you'll race on the
> values of user_vm_*.

yes. will add a mutex guard.

>
> [snip]
>
> > +/*
> > + * Allocate pages and vmap them into kernel vmalloc area.
> > + * Later the pages will be mmaped into user space vma.
> > + */
> > +static long arena_alloc_pages(struct bpf_arena *arena, long uaddr, long page_cnt, int node_id)
>
> instead of uaddr, can you change this to take an address relative to the
> arena ("arena virtual address"?)?  the caller of this is in BPF, and
> they don't easily know the user virtual address.  maybe even just pgoff
> directly.

I thought about it, but it doesn't quite make sense.
bpf prog only sees user addresses.
All load/store returns them. If it bpf_printk-s an address it will be
user address.
bpf_arena_alloc_pages() also returns a user address.

Kernel addresses are not seen by bpf prog at all.
kern_vm_base is completely hidden.
Only at JIT time, it's added to pointers.
So passing uaddr to arena_alloc_pages() matches mmap style.

uaddr = bpf_arena_alloc_pages(... uaddr ...)
uaddr = mmap(uaddr, ...MAP_FIXED)

Passing pgoff would be weird.
Also note that there is no extra flag for bpf_arena_alloc_pages().
uaddr == full 64-bit of zeros is not a valid addr to use.

> additionally, you won't need to call compute_pgoff().  as it is now, i'm
> not sure what would happen if BPF did an arena_alloc with a uaddr and
> user_vm_start wasn't set yet.

That's impossible. bpf prog won't load, if the arena map is not created
either with fixed map_extra == user_vm_start or map is created
with map_extra == 0 and mmaped.
Only then bpf prog that uses that arena can be loaded.

>
> > +{
> > +     long page_cnt_max = (arena->user_vm_end - arena->user_vm_start) >> PAGE_SHIFT;
>
> any time you compute_pgoff() or look at user_vm_{start,end}, maybe
> either hold the mutex, or only do it from mmap faults (where we know
> user_vm_start is already set).  o/w there might be subtle races where
> some other thread is mmapping the arena for the first time.

That's unnecessary, since user_vm_start is fixed for the lifetime of
bpf prog.
But you spotted a bug. I need to set user_vm_end in arena_map_alloc()
when map_extra is specified.
Otherwise after arena create and before mmap bpf prog will see different
page_cnt_max. user_vm_start will be the same, of course.

> > +
> > +     kaddr = kern_vm_start + (u32)(arena->user_vm_start + pgoff * PAGE_SIZE);
>
> adding user_vm_start here is pretty subtle.
>
> so far i've been thinking that the mtree is the "address space" of the
> arena, in units of pages instead of bytes.  and pgoff is an address
> within the arena.  so mtree slot 0 is the 0th page of the 4GB region.
> and that "arena address space" is mapped at a kernel virtual address and
> a user virtual address (the same for all processes).
>
> to convert user addresses (uaddr et al.) to arena addresses, we subtract
> user_vm_start, which makes sense.  that's what compute_pgoff() does.
>
> i was expecting kaddr = kern_vm_start + pgoff * PGSIZE, essentially
> converting from arena address space to kernel virtual address.
>
> instead, by adding user_vm_start and casting to u32, you're converting
> or shifting arena addresses to *another* arena address (user address,
> truncated to 4GB to keep it in the arena), and that is the one that the
> kernel will use.
>
> is that correct?

Pretty much. kern and user have to see lower 32-bit exactly the same.
From user pov allocation starts at pgoff=0 which is the first page
after user_vm_start. Which is normal mmap behavior and in-kernel
vma convention.
Hence in arena_alloc_pages() does the same pgoff=0 is the first
page from user vma pov.
The math to compute kernel address gets complicated because two
bases need to be added. Both kernel and user bases are different
64-bit bases and may not be aligned to 4G.

> my one concern is that there's some subtle wrap-around going on, and due
> to the shifting, kaddr can be very close to the end of the arena and
> page_cnt can be big enough to go outside the 4GB range.  we'd want it to

page_cnt cannot go outside of 4gb range.
page_cnt is a number of pages in arena->user_vm_end - arena->user_vm_start
and during mmap we check that it's <= 4gb.

> wrap around.  e.g.
>
> user_start_va = 0x1,fffff000
> user_end_va =   0x2,fffff000
> page_cnt_max = 0x100000 or whatever.  full 4GB range.
>
> say we want to alloc at pgoff=0 (uaddr 0x1,fffff000), page_cnt = X.  you
> can get this pgoff either by doing mtree_insert_range or
> mtree_alloc_range on an arena with no allocations.
>
> kaddr = kern_vm_start + 0xfffff000
>
> the size of the vm area is 4GB + guard stuff, and we're right up against
> the end of it.
>
> if page_cnt > the guard size, vmap_pages_range() would be called on
> something outside the vm area we reserved, which seems bad.  and even if
> it wasn't, what we want is for later page maps to start at the beginning
> of kern_vm_start.
>
> the fix might be to just only map a page at a time - maybe a loop.  or
> detect when we're close to the edge and break it into two vmaps.  i feel
> like the loop would be easier to understand, but maybe less efficient.

Oops. You're correct. Great catch.
In earlier versions I had it as a loop, but then I decided that doing
all mapping ops page at a time is not efficient.
Oh well. Will fix.

Thanks a lot for the review!

Barret Rhoden Feb. 7, 2024, 9:11 p.m. UTC | #3

On 2/7/24 15:55, Alexei Starovoitov wrote:
>> instead of uaddr, can you change this to take an address relative to the
>> arena ("arena virtual address"?)?  the caller of this is in BPF, and
>> they don't easily know the user virtual address.  maybe even just pgoff
>> directly.
> I thought about it, but it doesn't quite make sense.
> bpf prog only sees user addresses.
> All load/store returns them. If it bpf_printk-s an address it will be
> user address.
> bpf_arena_alloc_pages() also returns a user address.

Yeah, makes sense to keep them all in the same address space.

> 
> Kernel addresses are not seen by bpf prog at all.
> kern_vm_base is completely hidden.
> Only at JIT time, it's added to pointers.
> So passing uaddr to arena_alloc_pages() matches mmap style.
> 
> uaddr = bpf_arena_alloc_pages(... uaddr ...)
> uaddr = mmap(uaddr, ...MAP_FIXED)
> 
> Passing pgoff would be weird.
> Also note that there is no extra flag for bpf_arena_alloc_pages().
> uaddr == full 64-bit of zeros is not a valid addr to use.

The problem I had with uaddr was that when I'm writing a BPF program, I 
don't know which address to use for a given page, e.g. the beginning of 
the arena.  I needed some way to tell me the user address "base" of the 
arena.  Though now that I can specify the user_vm_start through the 
map_extra, I think I'm ok.

Specifically, say I want to break up my arena into two, 2GB chunks, one 
for each numa node, and I want to bump-allocate from each chunk.  When I 
want to allocate the first page from either segment, I'll need to know 
what user address is offset 0 or offset 2GB.

Since I know the user_start_vm at compile time, I can just hardcode that 
to convert from "arena address" (e.g. pgoff) to the user address space.

thanks,

barret

Alexei Starovoitov Feb. 8, 2024, 6:26 a.m. UTC | #4

On Wed, Feb 7, 2024 at 1:12 PM Barret Rhoden <brho@google.com> wrote:
>
> On 2/7/24 15:55, Alexei Starovoitov wrote:
> >> instead of uaddr, can you change this to take an address relative to the
> >> arena ("arena virtual address"?)?  the caller of this is in BPF, and
> >> they don't easily know the user virtual address.  maybe even just pgoff
> >> directly.
> > I thought about it, but it doesn't quite make sense.
> > bpf prog only sees user addresses.
> > All load/store returns them. If it bpf_printk-s an address it will be
> > user address.
> > bpf_arena_alloc_pages() also returns a user address.
>
> Yeah, makes sense to keep them all in the same address space.
>
> >
> > Kernel addresses are not seen by bpf prog at all.
> > kern_vm_base is completely hidden.
> > Only at JIT time, it's added to pointers.
> > So passing uaddr to arena_alloc_pages() matches mmap style.
> >
> > uaddr = bpf_arena_alloc_pages(... uaddr ...)
> > uaddr = mmap(uaddr, ...MAP_FIXED)
> >
> > Passing pgoff would be weird.
> > Also note that there is no extra flag for bpf_arena_alloc_pages().
> > uaddr == full 64-bit of zeros is not a valid addr to use.
>
> The problem I had with uaddr was that when I'm writing a BPF program, I
> don't know which address to use for a given page, e.g. the beginning of
> the arena.  I needed some way to tell me the user address "base" of the
> arena.  Though now that I can specify the user_vm_start through the
> map_extra, I think I'm ok.
>
> Specifically, say I want to break up my arena into two, 2GB chunks, one
> for each numa node, and I want to bump-allocate from each chunk.  When I
> want to allocate the first page from either segment, I'll need to know
> what user address is offset 0 or offset 2GB.

bump allocate... you mean like page_frag alloc does?
I've implemented one on top of arena:
https://git.kernel.org/pub/scm/linux/kernel/git/ast/bpf.git/tree/tools/testing/selftests/bpf/bpf_arena_alloc.h?h=arena&id=36d78b0f1c14c959d907d68cd7d54439b9213d0c

Also I believe I addressed all issues with missing mutex and wrap around,
and pushed to:
https://git.kernel.org/pub/scm/linux/kernel/git/ast/bpf.git/commit/?h=arena&id=e1cb522fee661e7346e8be567eade9cf607eaf11
Please take a look.

Including the wrap around test in the last commit:
https://git.kernel.org/pub/scm/linux/kernel/git/ast/bpf.git/commit/?h=arena&id=01653c393a4167ccca23dc5a69aa9cf34a46eabd

Will wait a bit before sending v2.

Barret Rhoden Feb. 8, 2024, 9:58 p.m. UTC | #5

On 2/8/24 01:26, Alexei Starovoitov wrote:
> Also I believe I addressed all issues with missing mutex and wrap around,
> and pushed to:
> https://git.kernel.org/pub/scm/linux/kernel/git/ast/bpf.git/commit/?h=arena&id=e1cb522fee661e7346e8be567eade9cf607eaf11
> Please take a look.

LGTM, thanks.

minor things:

> +static void arena_vm_close(struct vm_area_struct *vma)
> +{
> +	struct vma_list *vml;
> +
> +	vml = vma->vm_private_data;
> +	list_del(&vml->head);
> +	vma->vm_private_data = NULL;
> +	kfree(vml);
> +}

i think this also needs protected by the arena mutex.  otherwise two 
VMAs that close at the same time can corrupt the arena vma_list.  or a 
VMA that closes while you're zapping.

remember_vma() already has the mutex held, since it's called from mmap.

> +static long arena_alloc_pages(struct bpf_arena *arena, long uaddr, long page_cnt, int node_id)
> +{
> +	long page_cnt_max = (arena->user_vm_end - arena->user_vm_start) >> PAGE_SHIFT;

this function and arena_free_pages() are both using user_vm_start/end 
before grabbing the mutex.  so need to grab the mutex very early.

alternatively, you could make it so that the user must set the 
user_vm_start via map_extra, so you don't have to worry about these 
changing after the arena is created.

thanks,

barret

Alexei Starovoitov Feb. 8, 2024, 11:36 p.m. UTC | #6

On Thu, Feb 8, 2024 at 1:58 PM Barret Rhoden <brho@google.com> wrote:
>
> On 2/8/24 01:26, Alexei Starovoitov wrote:
> > Also I believe I addressed all issues with missing mutex and wrap around,
> > and pushed to:
> > https://git.kernel.org/pub/scm/linux/kernel/git/ast/bpf.git/commit/?h=arena&id=e1cb522fee661e7346e8be567eade9cf607eaf11
> > Please take a look.
>
> LGTM, thanks.
>
> minor things:
>
> > +static void arena_vm_close(struct vm_area_struct *vma)
> > +{
> > +     struct vma_list *vml;
> > +
> > +     vml = vma->vm_private_data;
> > +     list_del(&vml->head);
> > +     vma->vm_private_data = NULL;
> > +     kfree(vml);
> > +}
>
> i think this also needs protected by the arena mutex.  otherwise two
> VMAs that close at the same time can corrupt the arena vma_list.  or a
> VMA that closes while you're zapping.

Excellent catch.

> remember_vma() already has the mutex held, since it's called from mmap.
>
> > +static long arena_alloc_pages(struct bpf_arena *arena, long uaddr, long page_cnt, int node_id)
> > +{
> > +     long page_cnt_max = (arena->user_vm_end - arena->user_vm_start) >> PAGE_SHIFT;
>
> this function and arena_free_pages() are both using user_vm_start/end
> before grabbing the mutex.  so need to grab the mutex very early.
>
> alternatively, you could make it so that the user must set the
> user_vm_start via map_extra, so you don't have to worry about these
> changing after the arena is created.

Looks like I lost the diff hunk where verifier checks that
arena has user_vm_start set before loading the prog.
And for some reason forgot to remove
if (!arena->user_vm_start) return..
in bpf_arena_alloc/free_page().
I'll remove the latter and add the verifier enforcement back.
The intent was to never call arena_alloc/free_pages when the arena is
not fully formed.
Once it's fixed there will be no race in arena_alloc_pages().
user_vm_end/start are fixed before the program is loaded.

One more thing.
The vmap_pages_range_wrap32() fix that you saw in that commit is not
enough.
Turns out that [%r12 + src_reg + off] in JIT asm doesn't
fully conform to "kernel bounds all access into 32-bit".
That "+ off" part is added _after_ src_reg is bounded to 32-bit.
Remember, that was the reason we added guard pages before and after
kernel 4Gb vm area.
It's working as intended, but for this wrap32 case we need to
map one page into the normal kernel vma _and_ into the guard page.
Consider your example:
user_start_va = 0x1,fffff000
user_end_va =   0x2,fffff000

the pgoff = 0 is uaddr 0x1,fffff000.
It's kaddr = kern_vm_start + 0xfffff000
and kaddr + PAGE_SIZE is kern_vm_start + 0.

When bpf prog access an arena pointer it can do:
dst_reg = *(u64 *)(src_reg + 0)
and
dst_reg = *(u64 *)(src_reg + 4096)

the first LDX is fine, but the 2nd will be faulting
when src_reg is fffff000.
From user space pov it's a virtually contiguous address range.
For bpf prog it's also contiguous when src_reg is 32-bit bounded,
but "+ 4096" breaks that.
The 2nd load becomes:
kern_vm_start + 0xfffff000 + 4096
and it faults.
Theoretically a solution is to do:
kern_vm_start + (u32)(0xfffff000 + 4096)
in JIT, but that is too expensive.

Hence I went with arena fix (ignore lack of error checking):
static int vunmap_guard_pages(u64 kern_vm_start, u64 start, u64 end)
{
        end = (u32)end;
        if (start < S16_MAX) {
                u64 end1 = min(end, S16_MAX + 1);

                vunmap_range(kern_vm_start + (1ull << 32) + start,
                             kern_vm_start + (1ull << 32) + end1);
        }

        if (end >= U32_MAX - S16_MAX + 1) {
                u64 start2 = max(start, U32_MAX - S16_MAX + 1);

                vunmap_range(kern_vm_start - (1ull << 32) + start2,
                             kern_vm_start - (1ull << 32) + end);
        }
        return 0;
}
static int vmap_pages_range_wrap32(u64 kern_vm_start, u64 uaddr, u64 page_cnt,
                                   struct page **pages)
{
        u64 start = kern_vm_start + uaddr;
        u64 end = start + page_cnt * PAGE_SIZE;
        u64 part1_page_cnt, start2, end2;
        int ret;

        if (page_cnt == 1 || !((uaddr + page_cnt * PAGE_SIZE) >> 32)) {
                /* uaddr doesn't overflow in 32-bit */
                ret = vmap_pages_range(start, end, PAGE_KERNEL, pages,
PAGE_SHIFT);
                if (ret)
                        return ret;
                vmap_guard_pages(kern_vm_start, uaddr, uaddr +
page_cnt * PAGE_SIZE, pages);
                return 0;
        }

        part1_page_cnt = ((1ull << 32) - (u32)uaddr) >> PAGE_SHIFT;
        end = start + part1_page_cnt * PAGE_SIZE;
        ret = vmap_pages_range(start, end,
                               PAGE_KERNEL, pages, PAGE_SHIFT);
        if (ret)
            return ret;

        vmap_guard_pages(kern_vm_start, uaddr, uaddr + part1_page_cnt
* PAGE_SIZE, pages);

        start2 = kern_vm_start;
        end2 = start2 + (page_cnt - part1_page_cnt) * PAGE_SIZE;
        ret = vmap_pages_range(start2, end2,
                               PAGE_KERNEL, &pages[part1_page_cnt], PAGE_SHIFT);
        if (ret) {
                vunmap_range(start, end);
                return ret;
        }

        vmap_guard_pages(kern_vm_start, 0, (page_cnt - part1_page_cnt)
* PAGE_SIZE,
                         pages + part1_page_cnt);
        return 0;
}

It's working, but too complicated.
Instead of single vmap_pages_range()
we might need to do up to 4 calls and map certain pages into
two places to make both 64-bit virtual addresses:
kern_vm_start + 0xfffff000 + 4096
and
kern_vm_start + (u32)(0xfffff000 + 4096)
point to the same page.

I'm inclined to tackle wrap32 issue differently and simply
disallow [user_vm_start, user_vm_end] combination
where lower 32-bit can wrap.

In other words it would mean that mmap() of len=4Gb will be
aligned to 4Gb,
while mmap() of len=1M will be offsetted in such a way
that both addr and add+1M have the same upper 32-bit.
(It's not the same as 1M aligned).

With that I will remove vmap_pages_range_wrap32() and
do single normal vmap_pages_range() without extra tricks.

wdyt?

Barret Rhoden Feb. 8, 2024, 11:50 p.m. UTC | #7

On 2/8/24 18:36, Alexei Starovoitov wrote:
> I'm inclined to tackle wrap32 issue differently and simply
> disallow [user_vm_start, user_vm_end] combination
> where lower 32-bit can wrap.
> 
> In other words it would mean that mmap() of len=4Gb will be
> aligned to 4Gb,
> while mmap() of len=1M will be offsetted in such a way
> that both addr and add+1M have the same upper 32-bit.
> (It's not the same as 1M aligned).
> 
> With that I will remove vmap_pages_range_wrap32() and
> do single normal vmap_pages_range() without extra tricks.
> 
> wdyt?

SGTM.

knowing that you can't wrap the lower 32 removes a lot of headaches. 
and the restriction of aligning a 4GB mapping to 4GB boundary is pretty 
sane.  TBH doing it elsewhere is just asking for heartache.  =)

barret

[bpf-next,04/16] bpf: Introduce bpf_arena.

Commit Message

Comments

Patch