projects/linux·blob master · refs

1204 lines · 34.5 KiB

1// SPDX-License-Identifier: GPL-2.0-only
2/* Copyright (c) 2024 Meta Platforms, Inc. and affiliates. */
3#include <linux/bpf.h>
4#include <linux/btf.h>
5#include <linux/cacheflush.h>
6#include <linux/err.h>
7#include <linux/irq_work.h>
8#include "linux/filter.h"
9#include <linux/llist.h>
10#include <linux/btf_ids.h>
11#include <linux/vmalloc.h>
12#include <linux/pagemap.h>
13#include <asm/tlbflush.h>
14#include "range_tree.h"
15
16/*
17 * bpf_arena is a sparsely populated shared memory region between bpf program and
18 * user space process.
19 *
20 * For example on x86-64 the values could be:
21 * user_vm_start 7f7d26200000 // picked by mmap()
22 * kern_vm_start ffffc90001e69000 // picked by get_vm_area()
23 * For user space all pointers within the arena are normal 8-byte addresses.
24 * In this example 7f7d26200000 is the address of the first page (pgoff=0).
25 * The bpf program will access it as: kern_vm_start + lower_32bit_of_user_ptr
26 * (u32)7f7d26200000 -> 26200000
27 * hence
28 * ffffc90001e69000 + 26200000 == ffffc90028069000 is "pgoff=0" within 4Gb
29 * kernel memory region.
30 *
31 * BPF JITs generate the following code to access arena:
32 * mov eax, eax // eax has lower 32-bit of user pointer
33 * mov word ptr [rax + r12 + off], bx
34 * where r12 == kern_vm_start and off is s16.
35 * Hence allocate 4Gb + GUARD_SZ/2 on each side.
36 *
37 * Initially kernel vm_area and user vma are not populated.
38 * User space can fault-in any address which will insert the page
39 * into kernel and user vma.
40 * bpf program can allocate a page via bpf_arena_alloc_pages() kfunc
41 * which will insert it into kernel vm_area.
42 * The later fault-in from user space will populate that page into user vma.
43 */
44
45/* number of bytes addressable by LDX/STX insn with 16-bit 'off' field */
46#define GUARD_SZ round_up(1ull << sizeof_field(struct bpf_insn, off) * 8, PAGE_SIZE << 1)
47#define KERN_VM_SZ (SZ_4G + GUARD_SZ)
48
49static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt, bool sleepable);
50
51struct bpf_arena {
52 struct bpf_map map;
53 u64 user_vm_start;
54 u64 user_vm_end;
55 struct vm_struct *kern_vm;
56 struct page *scratch_page;
57 struct range_tree rt;
58 /* protects rt and nr_pages */
59 rqspinlock_t spinlock;
60 /* number of pages currently populated in the arena */
61 u64 nr_pages;
62 struct list_head vma_list;
63 /* protects vma_list */
64 struct mutex lock;
65 u64 zap_gen;
66 struct mutex zap_mutex;
67 struct irq_work free_irq;
68 struct work_struct free_work;
69 struct llist_head free_spans;
70};
71
72static void arena_free_worker(struct work_struct *work);
73static void arena_free_irq(struct irq_work *iw);
74
75struct arena_free_span {
76 struct llist_node node;
77 unsigned long uaddr;
78 u32 page_cnt;
79};
80
81u64 bpf_arena_get_kern_vm_start(struct bpf_arena *arena)
82{
83 return arena ? (u64) (long) arena->kern_vm->addr + GUARD_SZ / 2 : 0;
84}
85
86u64 bpf_arena_get_user_vm_start(struct bpf_arena *arena)
87{
88 return arena ? arena->user_vm_start : 0;
89}
90
91/**
92 * bpf_arena_map_kern_vm_start - kern_vm_start lookup by struct bpf_map *
93 * @map: a BPF_MAP_TYPE_ARENA map
94 *
95 * Return @map's kern_vm_start.
96 */
97u64 bpf_arena_map_kern_vm_start(struct bpf_map *map)
98{
99 return bpf_arena_get_kern_vm_start(container_of(map, struct bpf_arena, map));
100}
101
102/**
103 * bpf_prog_arena - return the bpf_map of the arena referenced by @prog
104 * @prog: a loaded BPF program
105 *
106 * The verifier enforces at most one arena per program and stores it in
107 * prog->aux->arena. Return that arena's underlying bpf_map, or NULL if
108 * @prog does not reference an arena.
109 */
110struct bpf_map *bpf_prog_arena(struct bpf_prog *prog)
111{
112 struct bpf_arena *arena = prog->aux->arena;
113
114 return arena ? &arena->map : NULL;
115}
116
117static long arena_map_peek_elem(struct bpf_map *map, void *value)
118{
119 return -EOPNOTSUPP;
120}
121
122static long arena_map_push_elem(struct bpf_map *map, void *value, u64 flags)
123{
124 return -EOPNOTSUPP;
125}
126
127static long arena_map_pop_elem(struct bpf_map *map, void *value)
128{
129 return -EOPNOTSUPP;
130}
131
132static long arena_map_delete_elem(struct bpf_map *map, void *value)
133{
134 return -EOPNOTSUPP;
135}
136
137static int arena_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
138{
139 return -EOPNOTSUPP;
140}
141
142static long compute_pgoff(struct bpf_arena *arena, long uaddr)
143{
144 return (u32)(uaddr - (u32)arena->user_vm_start) >> PAGE_SHIFT;
145}
146
147struct apply_range_data {
148 struct bpf_arena *arena;
149 struct page **pages;
150 int i;
151};
152
153struct clear_range_data {
154 struct bpf_arena *arena;
155 struct llist_head *free_pages;
156};
157
158static int apply_range_set_cb(pte_t *pte, unsigned long addr, void *data)
159{
160 struct apply_range_data *d = data;
161 struct page *page;
162 pte_t pteval;
163
164 if (!data)
165 return 0;
166
167 page = d->pages[d->i];
168 /* paranoia, similar to vmap_pages_pte_range() */
169 if (WARN_ON_ONCE(!pfn_valid(page_to_pfn(page))))
170 return -EINVAL;
171
172 pteval = mk_pte(page, PAGE_KERNEL);
173#ifdef ptep_try_set
174 /*
175 * Kernel-fault recovery may have installed the scratch page here, and
176 * some architectures (arm64) prohibit valid->valid PTE transitions.
177 * Install atomically into a none slot. If scratch is present, clear it
178 * and flush_tlb_before_set() (break-before-make) before retrying.
179 */
180 while (!ptep_try_set(pte, pteval)) {
181 pte_t old = ptep_get(pte);
182
183 if (pte_none(old))
184 continue;
185 if (WARN_ON_ONCE(pte_page(old) != d->arena->scratch_page))
186 return -EBUSY;
187 ptep_get_and_clear(&init_mm, addr, pte);
188 flush_tlb_before_set(addr);
189 }
190#else
191 /*
192 * Without ptep_try_set() there is no atomic installer, but such arches
193 * also do not wire up bpf_arena_handle_page_fault(), so no scratch page
194 * is ever installed and the slot is always none here.
195 */
196 if (unlikely(!pte_none(ptep_get(pte))))
197 return -EBUSY;
198 set_pte_at(&init_mm, addr, pte, pteval);
199#endif
200 d->i++;
201 WRITE_ONCE(d->arena->nr_pages, d->arena->nr_pages + 1);
202 return 0;
203}
204
205static void flush_vmap_cache(unsigned long start, unsigned long size)
206{
207 flush_cache_vmap(start, start + size);
208}
209
210static int apply_range_clear_cb(pte_t *pte, unsigned long addr, void *data)
211{
212 struct clear_range_data *d = data;
213 pte_t old_pte;
214 struct page *page;
215
216 /*
217 * Pairs with ptep_try_set() in the kernel-fault scratch installer.
218 * Both sides must be atomic.
219 */
220 old_pte = ptep_get_and_clear(&init_mm, addr, pte);
221 if (pte_none(old_pte) || !pte_present(old_pte))
222 return 0;
223
224 page = pte_page(old_pte);
225 if (WARN_ON_ONCE(!page))
226 return -EINVAL;
227
228 /*
229 * Skip the per-arena scratch page. A kernel fault on an unallocated uaddr
230 * scratches its PTE. A later bpf_arena_free_pages() over that range walks
231 * here. Without the skip, scratch_page would be freed.
232 */
233 if (page == d->arena->scratch_page)
234 return 0;
235
236 __llist_add(&page->pcp_llist, d->free_pages);
237 WRITE_ONCE(d->arena->nr_pages, d->arena->nr_pages - 1);
238 return 0;
239}
240
241static int apply_range_set_scratch_cb(pte_t *pte, unsigned long addr, void *data)
242{
243 struct page *scratch_page = data;
244
245 if (!pte_none(ptep_get(pte)))
246 return 0;
247 /*
248 * Best-effort install. ptep_try_set() returns false only if another
249 * installer (real allocation or concurrent fault) won the cmpxchg.
250 * Their PTE is already valid, so the access retry succeeds.
251 *
252 * No flush_tlb_kernel_range() needed. Stale "not mapped" entries just
253 * cause one extra re-fault through this same path.
254 */
255 ptep_try_set(pte, mk_pte(scratch_page, PAGE_KERNEL));
256 return 0;
257}
258
259static int populate_pgtable_except_pte(struct bpf_arena *arena)
260{
261 /* Populate intermediates for the recovery range (4 GiB + upper half-guard). */
262 return apply_to_page_range(&init_mm, bpf_arena_get_kern_vm_start(arena),
263 SZ_4G + GUARD_SZ / 2, apply_range_set_cb, NULL);
264}
265
266static struct bpf_map *arena_map_alloc(union bpf_attr *attr)
267{
268 struct vm_struct *kern_vm;
269 int numa_node = bpf_map_attr_numa_node(attr);
270 struct bpf_arena *arena;
271 u64 vm_range;
272 int err = -ENOMEM;
273
274 if (!bpf_jit_supports_arena())
275 return ERR_PTR(-EOPNOTSUPP);
276
277 if (attr->key_size || attr->value_size || attr->max_entries == 0 ||
278 /* BPF_F_MMAPABLE must be set */
279 !(attr->map_flags & BPF_F_MMAPABLE) ||
280 /* No unsupported flags present */
281 (attr->map_flags & ~(BPF_F_SEGV_ON_FAULT | BPF_F_MMAPABLE | BPF_F_NO_USER_CONV)))
282 return ERR_PTR(-EINVAL);
283
284 if (attr->map_extra & ~PAGE_MASK)
285 /* If non-zero the map_extra is an expected user VMA start address */
286 return ERR_PTR(-EINVAL);
287
288 vm_range = (u64)attr->max_entries * PAGE_SIZE;
289 if (vm_range > SZ_4G)
290 return ERR_PTR(-E2BIG);
291
292 if ((attr->map_extra >> 32) != ((attr->map_extra + vm_range - 1) >> 32))
293 /* user vma must not cross 32-bit boundary */
294 return ERR_PTR(-ERANGE);
295
296 kern_vm = get_vm_area(KERN_VM_SZ, VM_SPARSE | VM_USERMAP);
297 if (!kern_vm)
298 return ERR_PTR(-ENOMEM);
299
300 arena = bpf_map_area_alloc(sizeof(*arena), numa_node);
301 if (!arena)
302 goto err;
303
304 arena->kern_vm = kern_vm;
305 arena->user_vm_start = attr->map_extra;
306 if (arena->user_vm_start)
307 arena->user_vm_end = arena->user_vm_start + vm_range;
308
309 INIT_LIST_HEAD(&arena->vma_list);
310 init_llist_head(&arena->free_spans);
311 init_irq_work(&arena->free_irq, arena_free_irq);
312 INIT_WORK(&arena->free_work, arena_free_worker);
313 bpf_map_init_from_attr(&arena->map, attr);
314
315 err = bpf_map_alloc_pages(&arena->map, NUMA_NO_NODE, 1, &arena->scratch_page);
316 if (err)
317 goto err_free_arena;
318
319 range_tree_init(&arena->rt);
320 err = range_tree_set(&arena->rt, 0, attr->max_entries);
321 if (err)
322 goto err_free_scratch;
323 mutex_init(&arena->lock);
324 mutex_init(&arena->zap_mutex);
325 raw_res_spin_lock_init(&arena->spinlock);
326 err = populate_pgtable_except_pte(arena);
327 if (err)
328 goto err_destroy_rt;
329
330 return &arena->map;
331
332err_destroy_rt:
333 range_tree_destroy(&arena->rt);
334err_free_scratch:
335 __free_page(arena->scratch_page);
336err_free_arena:
337 bpf_map_area_free(arena);
338err:
339 free_vm_area(kern_vm);
340 return ERR_PTR(err);
341}
342
343static int existing_page_cb(pte_t *ptep, unsigned long addr, void *data)
344{
345 struct bpf_arena *arena = data;
346 struct page *page;
347 pte_t pte;
348
349 pte = ptep_get(ptep);
350 if (!pte_present(pte)) /* sanity check */
351 return 0;
352 page = pte_page(pte);
353 /*
354 * Skip the scratch page. The walk is page-table-driven, not range-tree-driven,
355 * so it can visit scratch PTEs at uaddrs the BPF program never allocated.
356 */
357 if (page == arena->scratch_page)
358 return 0;
359 /*
360 * We do not update pte here:
361 * 1. Nobody should be accessing bpf_arena's range outside of a kernel bug
362 * 2. TLB flushing is batched or deferred. Even if we clear pte,
363 * the TLB entries can stick around and continue to permit access to
364 * the freed page. So it all relies on 1.
365 */
366 __free_page(page);
367 return 0;
368}
369
370static void arena_map_free(struct bpf_map *map)
371{
372 struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
373
374 /*
375 * Check that user vma-s are not around when bpf map is freed.
376 * mmap() holds vm_file which holds bpf_map refcnt.
377 * munmap() must have happened on vma followed by arena_vm_close()
378 * which would clear arena->vma_list.
379 */
380 if (WARN_ON_ONCE(!list_empty(&arena->vma_list)))
381 return;
382
383 /* Ensure no pending deferred frees */
384 irq_work_sync(&arena->free_irq);
385 flush_work(&arena->free_work);
386
387 /*
388 * free_vm_area() calls remove_vm_area() that calls free_unmap_vmap_area().
389 * It unmaps everything from vmalloc area and clears pgtables.
390 * Call apply_to_existing_page_range() first to find populated ptes and
391 * free those pages.
392 */
393 apply_to_existing_page_range(&init_mm, bpf_arena_get_kern_vm_start(arena),
394 SZ_4G + GUARD_SZ / 2, existing_page_cb, arena);
395 free_vm_area(arena->kern_vm);
396 range_tree_destroy(&arena->rt);
397 __free_page(arena->scratch_page);
398 bpf_map_area_free(arena);
399}
400
401static void *arena_map_lookup_elem(struct bpf_map *map, void *key)
402{
403 return ERR_PTR(-EINVAL);
404}
405
406static long arena_map_update_elem(struct bpf_map *map, void *key,
407 void *value, u64 flags)
408{
409 return -EOPNOTSUPP;
410}
411
412static int arena_map_check_btf(struct bpf_map *map, const struct btf *btf,
413 const struct btf_type *key_type, const struct btf_type *value_type)
414{
415 return 0;
416}
417
418static u64 arena_map_mem_usage(const struct bpf_map *map)
419{
420 struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
421
422 return (u64)READ_ONCE(arena->nr_pages) << PAGE_SHIFT;
423}
424
425struct vma_list {
426 struct vm_area_struct *vma;
427 struct list_head head;
428 refcount_t mmap_count;
429 u64 zap_gen;
430};
431
432static int remember_vma(struct bpf_arena *arena, struct vm_area_struct *vma)
433{
434 struct vma_list *vml;
435
436 vml = kmalloc_obj(*vml);
437 if (!vml)
438 return -ENOMEM;
439 refcount_set(&vml->mmap_count, 1);
440 vma->vm_private_data = vml;
441 vml->vma = vma;
442 vml->zap_gen = 0;
443 list_add(&vml->head, &arena->vma_list);
444 return 0;
445}
446
447static void arena_vm_open(struct vm_area_struct *vma)
448{
449 struct vma_list *vml = vma->vm_private_data;
450
451 refcount_inc(&vml->mmap_count);
452}
453
454static int arena_vm_may_split(struct vm_area_struct *vma, unsigned long addr)
455{
456 return -EINVAL;
457}
458
459static int arena_vm_mremap(struct vm_area_struct *vma)
460{
461 return -EINVAL;
462}
463
464static void arena_vm_close(struct vm_area_struct *vma)
465{
466 struct bpf_map *map = vma->vm_file->private_data;
467 struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
468 struct vma_list *vml = vma->vm_private_data;
469
470 if (!refcount_dec_and_test(&vml->mmap_count))
471 return;
472 guard(mutex)(&arena->lock);
473 /* update link list under lock */
474 list_del(&vml->head);
475 vma->vm_private_data = NULL;
476 kfree(vml);
477}
478
479static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
480{
481 struct bpf_map *map = vmf->vma->vm_file->private_data;
482 struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
483 struct mem_cgroup *new_memcg, *old_memcg;
484 struct page *page;
485 long kbase, kaddr;
486 unsigned long flags;
487 int ret;
488
489 kbase = bpf_arena_get_kern_vm_start(arena);
490 kaddr = kbase + (u32)(vmf->address);
491
492 if (raw_res_spin_lock_irqsave(&arena->spinlock, flags))
493 /*
494 * A failed lock means a possible deadlock was detected. Don't
495 * return VM_FAULT_RETRY: this handler never took mmap_lock, but
496 * the fault path would re-take it on retry and deadlock. Fail.
497 */
498 return VM_FAULT_SIGBUS;
499
500 page = vmalloc_to_page((void *)kaddr);
501 if (page) {
502 if (page == arena->scratch_page)
503 /* BPF triggered scratch here; don't lazy-alloc over it */
504 goto out_sigsegv;
505 /* already have a page vmap-ed */
506 goto out;
507 }
508
509 bpf_map_memcg_enter(&arena->map, &old_memcg, &new_memcg);
510
511 if (arena->map.map_flags & BPF_F_SEGV_ON_FAULT)
512 /* User space requested to segfault when page is not allocated by bpf prog */
513 goto out_sigsegv_memcg;
514
515 ret = range_tree_clear(&arena->rt, vmf->pgoff, 1);
516 if (ret)
517 goto out_sigsegv_memcg;
518
519 struct apply_range_data data = { .arena = arena, .pages = &page, .i = 0 };
520 /* Account into memcg of the process that created bpf_arena */
521 ret = bpf_map_alloc_pages(map, NUMA_NO_NODE, 1, &page);
522 if (ret) {
523 range_tree_set(&arena->rt, vmf->pgoff, 1);
524 goto out_sigsegv_memcg;
525 }
526
527 ret = apply_to_page_range(&init_mm, kaddr, PAGE_SIZE, apply_range_set_cb, &data);
528 if (ret) {
529 range_tree_set(&arena->rt, vmf->pgoff, 1);
530 free_pages_nolock(page, 0);
531 goto out_sigsegv_memcg;
532 }
533 flush_vmap_cache(kaddr, PAGE_SIZE);
534 bpf_map_memcg_exit(old_memcg, new_memcg);
535out:
536 page_ref_add(page, 1);
537 raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
538 vmf->page = page;
539 return 0;
540out_sigsegv_memcg:
541 bpf_map_memcg_exit(old_memcg, new_memcg);
542out_sigsegv:
543 raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
544 return VM_FAULT_SIGSEGV;
545}
546
547static const struct vm_operations_struct arena_vm_ops = {
548 .open = arena_vm_open,
549 .may_split = arena_vm_may_split,
550 .mremap = arena_vm_mremap,
551 .close = arena_vm_close,
552 .fault = arena_vm_fault,
553};
554
555static unsigned long arena_get_unmapped_area(struct file *filp, unsigned long addr,
556 unsigned long len, unsigned long pgoff,
557 unsigned long flags)
558{
559 struct bpf_map *map = filp->private_data;
560 struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
561 long ret;
562
563 if (pgoff)
564 return -EINVAL;
565 if (len > SZ_4G)
566 return -E2BIG;
567
568 /* if user_vm_start was specified at arena creation time */
569 if (arena->user_vm_start) {
570 if (len > arena->user_vm_end - arena->user_vm_start)
571 return -E2BIG;
572 if (len != arena->user_vm_end - arena->user_vm_start)
573 return -EINVAL;
574 if (addr != arena->user_vm_start)
575 return -EINVAL;
576 }
577
578 ret = mm_get_unmapped_area(filp, addr, len * 2, 0, flags);
579 if (IS_ERR_VALUE(ret))
580 return ret;
581 if ((ret >> 32) == ((ret + len - 1) >> 32))
582 return ret;
583 if (WARN_ON_ONCE(arena->user_vm_start))
584 /* checks at map creation time should prevent this */
585 return -EFAULT;
586 return round_up(ret, SZ_4G);
587}
588
589static int arena_map_mmap(struct bpf_map *map, struct vm_area_struct *vma)
590{
591 struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
592
593 guard(mutex)(&arena->lock);
594 if (arena->user_vm_start && arena->user_vm_start != vma->vm_start)
595 /*
596 * If map_extra was not specified at arena creation time then
597 * 1st user process can do mmap(NULL, ...) to pick user_vm_start
598 * 2nd user process must pass the same addr to mmap(addr, MAP_FIXED..);
599 * or
600 * specify addr in map_extra and
601 * use the same addr later with mmap(addr, MAP_FIXED..);
602 */
603 return -EBUSY;
604
605 if (arena->user_vm_end && arena->user_vm_end != vma->vm_end)
606 /* all user processes must have the same size of mmap-ed region */
607 return -EBUSY;
608
609 /* Earlier checks should prevent this */
610 if (WARN_ON_ONCE(vma->vm_end - vma->vm_start > SZ_4G || vma->vm_pgoff))
611 return -EFAULT;
612
613 if (remember_vma(arena, vma))
614 return -ENOMEM;
615
616 arena->user_vm_start = vma->vm_start;
617 arena->user_vm_end = vma->vm_end;
618 /*
619 * bpf_map_mmap() checks that it's being mmaped as VM_SHARED and
620 * clears VM_MAYEXEC. Set VM_DONTEXPAND to avoid potential change
621 * of user_vm_start. Set VM_DONTCOPY to prevent arena VMA from
622 * being copied into the child process on fork.
623 */
624 vm_flags_set(vma, VM_DONTEXPAND | VM_DONTCOPY);
625 vma->vm_ops = &arena_vm_ops;
626 return 0;
627}
628
629static int arena_map_direct_value_addr(const struct bpf_map *map, u64 *imm, u32 off)
630{
631 struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
632
633 if ((u64)off >= arena->user_vm_end - arena->user_vm_start)
634 return -ERANGE;
635 *imm = (unsigned long)arena->user_vm_start;
636 return 0;
637}
638
639BTF_ID_LIST_SINGLE(bpf_arena_map_btf_ids, struct, bpf_arena)
640const struct bpf_map_ops arena_map_ops = {
641 .map_meta_equal = bpf_map_meta_equal,
642 .map_alloc = arena_map_alloc,
643 .map_free = arena_map_free,
644 .map_direct_value_addr = arena_map_direct_value_addr,
645 .map_mmap = arena_map_mmap,
646 .map_get_unmapped_area = arena_get_unmapped_area,
647 .map_get_next_key = arena_map_get_next_key,
648 .map_push_elem = arena_map_push_elem,
649 .map_peek_elem = arena_map_peek_elem,
650 .map_pop_elem = arena_map_pop_elem,
651 .map_lookup_elem = arena_map_lookup_elem,
652 .map_update_elem = arena_map_update_elem,
653 .map_delete_elem = arena_map_delete_elem,
654 .map_check_btf = arena_map_check_btf,
655 .map_mem_usage = arena_map_mem_usage,
656 .map_btf_id = &bpf_arena_map_btf_ids[0],
657};
658
659static u64 clear_lo32(u64 val)
660{
661 return val & ~(u64)~0U;
662}
663
664/*
665 * Allocate pages and vmap them into kernel vmalloc area.
666 * Later the pages will be mmaped into user space vma.
667 */
668static long arena_alloc_pages(struct bpf_arena *arena, long uaddr, long page_cnt, int node_id,
669 bool sleepable)
670{
671 /* user_vm_end/start are fixed before bpf prog runs */
672 long page_cnt_max = (arena->user_vm_end - arena->user_vm_start) >> PAGE_SHIFT;
673 u64 kern_vm_start = bpf_arena_get_kern_vm_start(arena);
674 struct mem_cgroup *new_memcg, *old_memcg;
675 struct apply_range_data data;
676 struct page **pages = NULL;
677 long remaining, mapped = 0;
678 long alloc_pages;
679 unsigned long flags;
680 long pgoff = 0;
681 u32 uaddr32;
682 int ret, i;
683
684 if (node_id != NUMA_NO_NODE &&
685 ((unsigned int)node_id >= nr_node_ids || !node_online(node_id)))
686 return 0;
687
688 if (page_cnt > page_cnt_max)
689 return 0;
690
691 if (uaddr) {
692 if (uaddr & ~PAGE_MASK)
693 return 0;
694 pgoff = compute_pgoff(arena, uaddr);
695 if (pgoff > page_cnt_max - page_cnt)
696 /* requested address will be outside of user VMA */
697 return 0;
698 }
699
700 bpf_map_memcg_enter(&arena->map, &old_memcg, &new_memcg);
701 /* Cap allocation size to KMALLOC_MAX_CACHE_SIZE so kmalloc_nolock() can succeed. */
702 alloc_pages = min(page_cnt, KMALLOC_MAX_CACHE_SIZE / sizeof(struct page *));
703 pages = kmalloc_nolock(alloc_pages * sizeof(struct page *), __GFP_ACCOUNT, NUMA_NO_NODE);
704 if (!pages) {
705 bpf_map_memcg_exit(old_memcg, new_memcg);
706 return 0;
707 }
708 data.arena = arena;
709 data.pages = pages;
710
711 if (raw_res_spin_lock_irqsave(&arena->spinlock, flags))
712 goto out_free_pages;
713
714 if (uaddr) {
715 ret = is_range_tree_set(&arena->rt, pgoff, page_cnt);
716 if (ret)
717 goto out_unlock_free_pages;
718 ret = range_tree_clear(&arena->rt, pgoff, page_cnt);
719 } else {
720 ret = pgoff = range_tree_find(&arena->rt, page_cnt);
721 if (pgoff >= 0)
722 ret = range_tree_clear(&arena->rt, pgoff, page_cnt);
723 }
724 if (ret)
725 goto out_unlock_free_pages;
726
727 remaining = page_cnt;
728 uaddr32 = (u32)(arena->user_vm_start + pgoff * PAGE_SIZE);
729
730 while (remaining) {
731 long this_batch = min(remaining, alloc_pages);
732
733 /* zeroing is needed, since alloc_pages_bulk() only fills in non-zero entries */
734 memset(pages, 0, this_batch * sizeof(struct page *));
735
736 ret = bpf_map_alloc_pages(&arena->map, node_id, this_batch, pages);
737 if (ret)
738 goto out;
739
740 /*
741 * Earlier checks made sure that uaddr32 + page_cnt * PAGE_SIZE - 1
742 * will not overflow 32-bit. Lower 32-bit need to represent
743 * contiguous user address range.
744 * Map these pages at kern_vm_start base.
745 * kern_vm_start + uaddr32 + page_cnt * PAGE_SIZE - 1 can overflow
746 * lower 32-bit and it's ok.
747 */
748 data.i = 0;
749 ret = apply_to_page_range(&init_mm,
750 kern_vm_start + uaddr32 + (mapped << PAGE_SHIFT),
751 this_batch << PAGE_SHIFT, apply_range_set_cb, &data);
752 if (ret) {
753 /* data.i pages were mapped, account them and free the remaining */
754 mapped += data.i;
755 for (i = data.i; i < this_batch; i++)
756 free_pages_nolock(pages[i], 0);
757 goto out;
758 }
759
760 mapped += this_batch;
761 remaining -= this_batch;
762 }
763 flush_vmap_cache(kern_vm_start + uaddr32, mapped << PAGE_SHIFT);
764 raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
765 kfree_nolock(pages);
766 bpf_map_memcg_exit(old_memcg, new_memcg);
767 return clear_lo32(arena->user_vm_start) + uaddr32;
768out:
769 range_tree_set(&arena->rt, pgoff + mapped, page_cnt - mapped);
770 raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
771 if (mapped) {
772 flush_vmap_cache(kern_vm_start + uaddr32, mapped << PAGE_SHIFT);
773 arena_free_pages(arena, uaddr32, mapped, sleepable);
774 }
775 goto out_free_pages;
776out_unlock_free_pages:
777 raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
778out_free_pages:
779 kfree_nolock(pages);
780 bpf_map_memcg_exit(old_memcg, new_memcg);
781 return 0;
782}
783
784/*
785 * If page is present in vmalloc area, unmap it from vmalloc area,
786 * unmap it from all user space vma-s,
787 * and free it.
788 */
789static void zap_pages(struct bpf_arena *arena, long uaddr, long page_cnt)
790{
791 unsigned long size = (unsigned long)page_cnt << PAGE_SHIFT;
792 struct vm_area_struct *vma;
793 struct mm_struct *mm;
794 struct vma_list *vml;
795 unsigned long vm_start;
796 u64 my_gen;
797
798 /*
799 * Taking mmap_read_lock() under arena->lock would deadlock against
800 * arena_vm_close(), which runs with mmap_write_lock held and then
801 * acquires arena->lock. Drop arena->lock for mmap_read_lock().
802 *
803 * Use per-call my_gen, recorded in vml->zap_gen, to remember which
804 * vmls this invocation has already processed across the lock drop.
805 * Hold zap_mutex around the whole walk so concurrent zap_pages()
806 * callers cannot overwrite each other's marks on shared vmls --
807 * otherwise call B's mark would make call A skip a vml that A has
808 * not yet zapped for A's uaddr range.
809 */
810 mutex_lock(&arena->zap_mutex);
811 mutex_lock(&arena->lock);
812 my_gen = ++arena->zap_gen;
813 for (;;) {
814 mm = NULL;
815 list_for_each_entry(vml, &arena->vma_list, head) {
816 if (vml->zap_gen >= my_gen)
817 continue;
818 vml->zap_gen = my_gen;
819 if (!mmget_not_zero(vml->vma->vm_mm))
820 continue;
821 mm = vml->vma->vm_mm;
822 vm_start = vml->vma->vm_start;
823 break;
824 }
825 if (!mm)
826 break;
827 mutex_unlock(&arena->lock);
828
829 mmap_read_lock(mm);
830 /*
831 * Re-resolve: while we waited the VMA could have been unmapped
832 * and a different mapping installed at the same address.
833 */
834 vma = find_vma(mm, vm_start);
835 if (vma && vma->vm_start == vm_start &&
836 vma->vm_file && vma->vm_file->private_data == &arena->map)
837 zap_vma_range(vma, uaddr, size);
838 mmap_read_unlock(mm);
839 mmput(mm);
840
841 mutex_lock(&arena->lock);
842 }
843 mutex_unlock(&arena->lock);
844 mutex_unlock(&arena->zap_mutex);
845}
846
847static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt, bool sleepable)
848{
849 struct mem_cgroup *new_memcg, *old_memcg;
850 u64 full_uaddr, uaddr_end;
851 long kaddr, pgoff;
852 struct page *page;
853 struct llist_head free_pages;
854 struct llist_node *pos, *t;
855 struct arena_free_span *s;
856 struct clear_range_data cdata;
857 unsigned long flags;
858 int ret = 0;
859
860 /* only aligned lower 32-bit are relevant */
861 uaddr = (u32)uaddr;
862 uaddr &= PAGE_MASK;
863 kaddr = bpf_arena_get_kern_vm_start(arena) + uaddr;
864 full_uaddr = clear_lo32(arena->user_vm_start) + uaddr;
865 if (full_uaddr < arena->user_vm_start)
866 return;
867 uaddr_end = min(arena->user_vm_end, full_uaddr + (page_cnt << PAGE_SHIFT));
868 if (full_uaddr >= uaddr_end)
869 return;
870
871 page_cnt = (uaddr_end - full_uaddr) >> PAGE_SHIFT;
872 pgoff = compute_pgoff(arena, uaddr);
873 bpf_map_memcg_enter(&arena->map, &old_memcg, &new_memcg);
874
875 if (!sleepable)
876 goto defer;
877
878 ret = raw_res_spin_lock_irqsave(&arena->spinlock, flags);
879
880 /* Can't proceed without holding the spinlock so defer the free */
881 if (ret)
882 goto defer;
883
884 range_tree_set(&arena->rt, pgoff, page_cnt);
885
886 init_llist_head(&free_pages);
887 cdata.arena = arena;
888 cdata.free_pages = &free_pages;
889 /* clear ptes and collect struct pages */
890 apply_to_existing_page_range(&init_mm, kaddr, page_cnt << PAGE_SHIFT,
891 apply_range_clear_cb, &cdata);
892
893 /* drop the lock to do the tlb flush and zap pages */
894 raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
895
896 /* ensure no stale TLB entries */
897 flush_tlb_kernel_range(kaddr, kaddr + (page_cnt * PAGE_SIZE));
898
899 if (page_cnt > 1)
900 /* bulk zap if multiple pages being freed */
901 zap_pages(arena, full_uaddr, page_cnt);
902
903 llist_for_each_safe(pos, t, __llist_del_all(&free_pages)) {
904 page = llist_entry(pos, struct page, pcp_llist);
905 if (page_cnt == 1 && page_ref_count(page) > 1) /* maybe mapped by user space */
906 /* Optimization for the common case of page_cnt==1:
907 * If page wasn't mapped into some user vma there
908 * is no need to call zap_pages which is slow. When
909 * page_cnt is big it's faster to do the batched zap.
910 */
911 zap_pages(arena, full_uaddr, 1);
912 __free_page(page);
913 }
914 bpf_map_memcg_exit(old_memcg, new_memcg);
915
916 return;
917
918defer:
919 s = kmalloc_nolock(sizeof(struct arena_free_span), __GFP_ACCOUNT, -1);
920 bpf_map_memcg_exit(old_memcg, new_memcg);
921 if (!s)
922 /*
923 * If allocation fails in non-sleepable context, pages are intentionally left
924 * inaccessible (leaked) until the arena is destroyed. Cleanup or retries are not
925 * possible here, so we intentionally omit them for safety.
926 */
927 return;
928
929 s->page_cnt = page_cnt;
930 s->uaddr = uaddr;
931 llist_add(&s->node, &arena->free_spans);
932 irq_work_queue(&arena->free_irq);
933}
934
935/*
936 * Reserve an arena virtual address range without populating it. This call stops
937 * bpf_arena_alloc_pages from adding pages to this range.
938 */
939static int arena_reserve_pages(struct bpf_arena *arena, long uaddr, u32 page_cnt)
940{
941 long page_cnt_max = (arena->user_vm_end - arena->user_vm_start) >> PAGE_SHIFT;
942 struct mem_cgroup *new_memcg, *old_memcg;
943 unsigned long flags;
944 long pgoff;
945 int ret;
946
947 if (uaddr & ~PAGE_MASK)
948 return 0;
949
950 pgoff = compute_pgoff(arena, uaddr);
951 if (pgoff + page_cnt > page_cnt_max)
952 return -EINVAL;
953
954 if (raw_res_spin_lock_irqsave(&arena->spinlock, flags))
955 return -EBUSY;
956
957 /* Cannot guard already allocated pages. */
958 ret = is_range_tree_set(&arena->rt, pgoff, page_cnt);
959 if (ret) {
960 ret = -EBUSY;
961 goto out;
962 }
963
964 /* "Allocate" the region to prevent it from being allocated. */
965 bpf_map_memcg_enter(&arena->map, &old_memcg, &new_memcg);
966 ret = range_tree_clear(&arena->rt, pgoff, page_cnt);
967 bpf_map_memcg_exit(old_memcg, new_memcg);
968out:
969 raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
970 return ret;
971}
972
973static void arena_free_worker(struct work_struct *work)
974{
975 struct bpf_arena *arena = container_of(work, struct bpf_arena, free_work);
976 struct mem_cgroup *new_memcg, *old_memcg;
977 struct llist_node *list, *pos, *t;
978 struct arena_free_span *s;
979 u64 arena_vm_start, user_vm_start;
980 struct llist_head free_pages;
981 struct clear_range_data cdata;
982 struct page *page;
983 unsigned long full_uaddr;
984 long kaddr, page_cnt, pgoff;
985 unsigned long flags;
986
987 if (raw_res_spin_lock_irqsave(&arena->spinlock, flags)) {
988 schedule_work(work);
989 return;
990 }
991
992 bpf_map_memcg_enter(&arena->map, &old_memcg, &new_memcg);
993
994 init_llist_head(&free_pages);
995 cdata.arena = arena;
996 cdata.free_pages = &free_pages;
997 arena_vm_start = bpf_arena_get_kern_vm_start(arena);
998 user_vm_start = bpf_arena_get_user_vm_start(arena);
999
1000 list = llist_del_all(&arena->free_spans);
1001 llist_for_each(pos, list) {
1002 s = llist_entry(pos, struct arena_free_span, node);
1003 page_cnt = s->page_cnt;
1004 kaddr = arena_vm_start + s->uaddr;
1005 pgoff = compute_pgoff(arena, s->uaddr);
1006
1007 /* clear ptes and collect pages in free_pages llist */
1008 apply_to_existing_page_range(&init_mm, kaddr, page_cnt << PAGE_SHIFT,
1009 apply_range_clear_cb, &cdata);
1010
1011 range_tree_set(&arena->rt, pgoff, page_cnt);
1012 }
1013 raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
1014
1015 /* Iterate the list again without holding spinlock to do the tlb flush and zap_pages */
1016 llist_for_each_safe(pos, t, list) {
1017 s = llist_entry(pos, struct arena_free_span, node);
1018 page_cnt = s->page_cnt;
1019 full_uaddr = clear_lo32(user_vm_start) + s->uaddr;
1020 kaddr = arena_vm_start + s->uaddr;
1021
1022 /* ensure no stale TLB entries */
1023 flush_tlb_kernel_range(kaddr, kaddr + (page_cnt * PAGE_SIZE));
1024
1025 /* remove pages from user vmas */
1026 zap_pages(arena, full_uaddr, page_cnt);
1027
1028 kfree_nolock(s);
1029 }
1030
1031 /* free all pages collected by apply_to_existing_page_range() in the first loop */
1032 llist_for_each_safe(pos, t, __llist_del_all(&free_pages)) {
1033 page = llist_entry(pos, struct page, pcp_llist);
1034 __free_page(page);
1035 }
1036
1037 bpf_map_memcg_exit(old_memcg, new_memcg);
1038}
1039
1040static void arena_free_irq(struct irq_work *iw)
1041{
1042 struct bpf_arena *arena = container_of(iw, struct bpf_arena, free_irq);
1043
1044 schedule_work(&arena->free_work);
1045}
1046
1047__bpf_kfunc_start_defs();
1048
1049__bpf_kfunc void *bpf_arena_alloc_pages(void *p__map, void *addr__ign, u32 page_cnt,
1050 int node_id, u64 flags)
1051{
1052 struct bpf_map *map = p__map;
1053 struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
1054
1055 if (map->map_type != BPF_MAP_TYPE_ARENA || flags || !page_cnt)
1056 return NULL;
1057
1058 return (void *)arena_alloc_pages(arena, (long)addr__ign, page_cnt, node_id, true);
1059}
1060
1061void *bpf_arena_alloc_pages_non_sleepable(void *p__map, void *addr__ign, u32 page_cnt,
1062 int node_id, u64 flags)
1063{
1064 struct bpf_map *map = p__map;
1065 struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
1066
1067 if (map->map_type != BPF_MAP_TYPE_ARENA || flags || !page_cnt)
1068 return NULL;
1069
1070 return (void *)arena_alloc_pages(arena, (long)addr__ign, page_cnt, node_id, false);
1071}
1072
1073void *bpf_arena_alloc_pages_sleepable(void *p__map, void *addr__ign, u32 page_cnt,
1074 int node_id, u64 flags)
1075{
1076 struct bpf_map *map = p__map;
1077 struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
1078
1079 if (map->map_type != BPF_MAP_TYPE_ARENA || flags || !page_cnt)
1080 return NULL;
1081
1082 return (void *)arena_alloc_pages(arena, (long)addr__ign, page_cnt, node_id, true);
1083}
1084
1085__bpf_kfunc void bpf_arena_free_pages(void *p__map, void *ptr__ign, u32 page_cnt)
1086{
1087 struct bpf_map *map = p__map;
1088 struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
1089
1090 if (map->map_type != BPF_MAP_TYPE_ARENA || !page_cnt || !ptr__ign)
1091 return;
1092 arena_free_pages(arena, (long)ptr__ign, page_cnt, true);
1093}
1094
1095void bpf_arena_free_pages_non_sleepable(void *p__map, void *ptr__ign, u32 page_cnt)
1096{
1097 struct bpf_map *map = p__map;
1098 struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
1099
1100 if (map->map_type != BPF_MAP_TYPE_ARENA || !page_cnt || !ptr__ign)
1101 return;
1102 arena_free_pages(arena, (long)ptr__ign, page_cnt, false);
1103}
1104
1105__bpf_kfunc int bpf_arena_reserve_pages(void *p__map, void *ptr__ign, u32 page_cnt)
1106{
1107 struct bpf_map *map = p__map;
1108 struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
1109
1110 if (map->map_type != BPF_MAP_TYPE_ARENA)
1111 return -EINVAL;
1112
1113 if (!page_cnt)
1114 return 0;
1115
1116 return arena_reserve_pages(arena, (long)ptr__ign, page_cnt);
1117}
1118__bpf_kfunc_end_defs();
1119
1120BTF_KFUNCS_START(arena_kfuncs)
1121BTF_ID_FLAGS(func, bpf_arena_alloc_pages, KF_ARENA_RET | KF_ARENA_ARG2 | KF_SPINLOCK_SAFE)
1122BTF_ID_FLAGS(func, bpf_arena_free_pages, KF_ARENA_ARG2 | KF_SPINLOCK_SAFE)
1123BTF_ID_FLAGS(func, bpf_arena_reserve_pages, KF_ARENA_ARG2 | KF_SPINLOCK_SAFE)
1124BTF_KFUNCS_END(arena_kfuncs)
1125
1126static const struct btf_kfunc_id_set common_kfunc_set = {
1127 .owner = THIS_MODULE,
1128 .set = &arena_kfuncs,
1129};
1130
1131static int __init kfunc_init(void)
1132{
1133 return register_btf_kfunc_id_set(BPF_PROG_TYPE_UNSPEC, &common_kfunc_set);
1134}
1135late_initcall(kfunc_init);
1136
1137static void __bpf_prog_report_arena_violation(struct bpf_prog *prog, bool write,
1138 unsigned long addr, unsigned long fault_ip)
1139{
1140 struct bpf_stream_stage ss;
1141 u64 user_vm_start;
1142
1143 /* Use main prog for stream access */
1144 prog = prog->aux->main_prog_aux->prog;
1145
1146 user_vm_start = bpf_arena_get_user_vm_start(prog->aux->arena);
1147 addr += clear_lo32(user_vm_start);
1148
1149 bpf_stream_stage(ss, prog, BPF_STDERR, ({
1150 bpf_stream_printk(ss, "ERROR: Arena %s access at unmapped address 0x%lx\n",
1151 write ? "WRITE" : "READ", addr);
1152 bpf_stream_dump_stack(ss);
1153 }));
1154}
1155
1156bool bpf_arena_handle_page_fault(unsigned long addr, bool is_write, unsigned long fault_ip)
1157{
1158 struct bpf_arena *arena;
1159 struct bpf_prog *prog;
1160 unsigned long kbase;
1161 unsigned long page_addr = addr & PAGE_MASK;
1162
1163 prog = bpf_prog_find_from_stack();
1164 if (!prog)
1165 return false;
1166
1167 arena = prog->aux->arena;
1168 /* a prog not using arena may be on stack, so arena can be NULL */
1169 if (!arena)
1170 return false;
1171
1172 kbase = bpf_arena_get_kern_vm_start(arena);
1173
1174 /*
1175 * Recovery covers the 4 GiB mappable band plus the upper half-guard.
1176 * Lower guard is unreachable from kfuncs; an address there indicates
1177 * a different bug class - leave it to the regular kernel oops path.
1178 */
1179 if (page_addr < kbase || page_addr >= kbase + SZ_4G + GUARD_SZ / 2)
1180 return false;
1181
1182 apply_to_page_range(&init_mm, page_addr, PAGE_SIZE,
1183 apply_range_set_scratch_cb, arena->scratch_page);
1184 flush_vmap_cache(page_addr, PAGE_SIZE);
1185 __bpf_prog_report_arena_violation(prog, is_write, page_addr - kbase, fault_ip);
1186 return true;
1187}
1188
1189void bpf_prog_report_arena_violation(bool write, unsigned long addr, unsigned long fault_ip)
1190{
1191 struct bpf_prog *prog;
1192
1193 /*
1194 * The RCU read lock is held to safely traverse the latch tree, but we
1195 * don't need its protection when accessing the prog, since it will not
1196 * disappear while we are handling the fault.
1197 */
1198 rcu_read_lock();
1199 prog = bpf_prog_ksym_find(fault_ip);
1200 rcu_read_unlock();
1201 if (!prog)
1202 return;
1203 __bpf_prog_report_arena_violation(prog, write, addr, fault_ip);
1204}