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/err.h> 6#include <linux/btf_ids.h> 7#include <linux/vmalloc.h> 8#include <linux/pagemap.h> 9 10/* 11 * bpf_arena is a sparsely populated shared memory region between bpf program and 12 * user space process. 13 * 14 * For example on x86-64 the values could be: 15 * user_vm_start 7f7d26200000 // picked by mmap() 16 * kern_vm_start ffffc90001e69000 // picked by get_vm_area() 17 * For user space all pointers within the arena are normal 8-byte addresses. 18 * In this example 7f7d26200000 is the address of the first page (pgoff=0). 19 * The bpf program will access it as: kern_vm_start + lower_32bit_of_user_ptr 20 * (u32)7f7d26200000 -> 26200000 21 * hence 22 * ffffc90001e69000 + 26200000 == ffffc90028069000 is "pgoff=0" within 4Gb 23 * kernel memory region. 24 * 25 * BPF JITs generate the following code to access arena: 26 * mov eax, eax // eax has lower 32-bit of user pointer 27 * mov word ptr [rax + r12 + off], bx 28 * where r12 == kern_vm_start and off is s16. 29 * Hence allocate 4Gb + GUARD_SZ/2 on each side. 30 * 31 * Initially kernel vm_area and user vma are not populated. 32 * User space can fault-in any address which will insert the page 33 * into kernel and user vma. 34 * bpf program can allocate a page via bpf_arena_alloc_pages() kfunc 35 * which will insert it into kernel vm_area. 36 * The later fault-in from user space will populate that page into user vma. 37 */ 38 39/* number of bytes addressable by LDX/STX insn with 16-bit 'off' field */ 40#define GUARD_SZ (1ull << sizeof(((struct bpf_insn *)0)->off) * 8) 41#define KERN_VM_SZ (SZ_4G + GUARD_SZ) 42 43struct bpf_arena { 44 struct bpf_map map; 45 u64 user_vm_start; 46 u64 user_vm_end; 47 struct vm_struct *kern_vm; 48 struct maple_tree mt; 49 struct list_head vma_list; 50 struct mutex lock; 51}; 52 53u64 bpf_arena_get_kern_vm_start(struct bpf_arena *arena) 54{ 55 return arena ? (u64) (long) arena->kern_vm->addr + GUARD_SZ / 2 : 0; 56} 57 58u64 bpf_arena_get_user_vm_start(struct bpf_arena *arena) 59{ 60 return arena ? arena->user_vm_start : 0; 61} 62 63static long arena_map_peek_elem(struct bpf_map *map, void *value) 64{ 65 return -EOPNOTSUPP; 66} 67 68static long arena_map_push_elem(struct bpf_map *map, void *value, u64 flags) 69{ 70 return -EOPNOTSUPP; 71} 72 73static long arena_map_pop_elem(struct bpf_map *map, void *value) 74{ 75 return -EOPNOTSUPP; 76} 77 78static long arena_map_delete_elem(struct bpf_map *map, void *value) 79{ 80 return -EOPNOTSUPP; 81} 82 83static int arena_map_get_next_key(struct bpf_map *map, void *key, void *next_key) 84{ 85 return -EOPNOTSUPP; 86} 87 88static long compute_pgoff(struct bpf_arena *arena, long uaddr) 89{ 90 return (u32)(uaddr - (u32)arena->user_vm_start) >> PAGE_SHIFT; 91} 92 93static struct bpf_map *arena_map_alloc(union bpf_attr *attr) 94{ 95 struct vm_struct *kern_vm; 96 int numa_node = bpf_map_attr_numa_node(attr); 97 struct bpf_arena *arena; 98 u64 vm_range; 99 int err = -ENOMEM; 100 101 if (attr->key_size || attr->value_size || attr->max_entries == 0 || 102 /* BPF_F_MMAPABLE must be set */ 103 !(attr->map_flags & BPF_F_MMAPABLE) || 104 /* No unsupported flags present */ 105 (attr->map_flags & ~(BPF_F_SEGV_ON_FAULT | BPF_F_MMAPABLE | BPF_F_NO_USER_CONV))) 106 return ERR_PTR(-EINVAL); 107 108 if (attr->map_extra & ~PAGE_MASK) 109 /* If non-zero the map_extra is an expected user VMA start address */ 110 return ERR_PTR(-EINVAL); 111 112 vm_range = (u64)attr->max_entries * PAGE_SIZE; 113 if (vm_range > SZ_4G) 114 return ERR_PTR(-E2BIG); 115 116 if ((attr->map_extra >> 32) != ((attr->map_extra + vm_range - 1) >> 32)) 117 /* user vma must not cross 32-bit boundary */ 118 return ERR_PTR(-ERANGE); 119 120 kern_vm = get_vm_area(KERN_VM_SZ, VM_SPARSE | VM_USERMAP); 121 if (!kern_vm) 122 return ERR_PTR(-ENOMEM); 123 124 arena = bpf_map_area_alloc(sizeof(*arena), numa_node); 125 if (!arena) 126 goto err; 127 128 arena->kern_vm = kern_vm; 129 arena->user_vm_start = attr->map_extra; 130 if (arena->user_vm_start) 131 arena->user_vm_end = arena->user_vm_start + vm_range; 132 133 INIT_LIST_HEAD(&arena->vma_list); 134 bpf_map_init_from_attr(&arena->map, attr); 135 mt_init_flags(&arena->mt, MT_FLAGS_ALLOC_RANGE); 136 mutex_init(&arena->lock); 137 138 return &arena->map; 139err: 140 free_vm_area(kern_vm); 141 return ERR_PTR(err); 142} 143 144static int existing_page_cb(pte_t *ptep, unsigned long addr, void *data) 145{ 146 struct page *page; 147 pte_t pte; 148 149 pte = ptep_get(ptep); 150 if (!pte_present(pte)) /* sanity check */ 151 return 0; 152 page = pte_page(pte); 153 /* 154 * We do not update pte here: 155 * 1. Nobody should be accessing bpf_arena's range outside of a kernel bug 156 * 2. TLB flushing is batched or deferred. Even if we clear pte, 157 * the TLB entries can stick around and continue to permit access to 158 * the freed page. So it all relies on 1. 159 */ 160 __free_page(page); 161 return 0; 162} 163 164static void arena_map_free(struct bpf_map *map) 165{ 166 struct bpf_arena *arena = container_of(map, struct bpf_arena, map); 167 168 /* 169 * Check that user vma-s are not around when bpf map is freed. 170 * mmap() holds vm_file which holds bpf_map refcnt. 171 * munmap() must have happened on vma followed by arena_vm_close() 172 * which would clear arena->vma_list. 173 */ 174 if (WARN_ON_ONCE(!list_empty(&arena->vma_list))) 175 return; 176 177 /* 178 * free_vm_area() calls remove_vm_area() that calls free_unmap_vmap_area(). 179 * It unmaps everything from vmalloc area and clears pgtables. 180 * Call apply_to_existing_page_range() first to find populated ptes and 181 * free those pages. 182 */ 183 apply_to_existing_page_range(&init_mm, bpf_arena_get_kern_vm_start(arena), 184 KERN_VM_SZ - GUARD_SZ, existing_page_cb, NULL); 185 free_vm_area(arena->kern_vm); 186 mtree_destroy(&arena->mt); 187 bpf_map_area_free(arena); 188} 189 190static void *arena_map_lookup_elem(struct bpf_map *map, void *key) 191{ 192 return ERR_PTR(-EINVAL); 193} 194 195static long arena_map_update_elem(struct bpf_map *map, void *key, 196 void *value, u64 flags) 197{ 198 return -EOPNOTSUPP; 199} 200 201static int arena_map_check_btf(const struct bpf_map *map, const struct btf *btf, 202 const struct btf_type *key_type, const struct btf_type *value_type) 203{ 204 return 0; 205} 206 207static u64 arena_map_mem_usage(const struct bpf_map *map) 208{ 209 return 0; 210} 211 212struct vma_list { 213 struct vm_area_struct *vma; 214 struct list_head head; 215}; 216 217static int remember_vma(struct bpf_arena *arena, struct vm_area_struct *vma) 218{ 219 struct vma_list *vml; 220 221 vml = kmalloc(sizeof(*vml), GFP_KERNEL); 222 if (!vml) 223 return -ENOMEM; 224 vma->vm_private_data = vml; 225 vml->vma = vma; 226 list_add(&vml->head, &arena->vma_list); 227 return 0; 228} 229 230static void arena_vm_close(struct vm_area_struct *vma) 231{ 232 struct bpf_map *map = vma->vm_file->private_data; 233 struct bpf_arena *arena = container_of(map, struct bpf_arena, map); 234 struct vma_list *vml; 235 236 guard(mutex)(&arena->lock); 237 vml = vma->vm_private_data; 238 list_del(&vml->head); 239 vma->vm_private_data = NULL; 240 kfree(vml); 241} 242 243#define MT_ENTRY ((void *)&arena_map_ops) /* unused. has to be valid pointer */ 244 245static vm_fault_t arena_vm_fault(struct vm_fault *vmf) 246{ 247 struct bpf_map *map = vmf->vma->vm_file->private_data; 248 struct bpf_arena *arena = container_of(map, struct bpf_arena, map); 249 struct page *page; 250 long kbase, kaddr; 251 int ret; 252 253 kbase = bpf_arena_get_kern_vm_start(arena); 254 kaddr = kbase + (u32)(vmf->address & PAGE_MASK); 255 256 guard(mutex)(&arena->lock); 257 page = vmalloc_to_page((void *)kaddr); 258 if (page) 259 /* already have a page vmap-ed */ 260 goto out; 261 262 if (arena->map.map_flags & BPF_F_SEGV_ON_FAULT) 263 /* User space requested to segfault when page is not allocated by bpf prog */ 264 return VM_FAULT_SIGSEGV; 265 266 ret = mtree_insert(&arena->mt, vmf->pgoff, MT_ENTRY, GFP_KERNEL); 267 if (ret) 268 return VM_FAULT_SIGSEGV; 269 270 /* Account into memcg of the process that created bpf_arena */ 271 ret = bpf_map_alloc_pages(map, GFP_KERNEL | __GFP_ZERO, NUMA_NO_NODE, 1, &page); 272 if (ret) { 273 mtree_erase(&arena->mt, vmf->pgoff); 274 return VM_FAULT_SIGSEGV; 275 } 276 277 ret = vm_area_map_pages(arena->kern_vm, kaddr, kaddr + PAGE_SIZE, &page); 278 if (ret) { 279 mtree_erase(&arena->mt, vmf->pgoff); 280 __free_page(page); 281 return VM_FAULT_SIGSEGV; 282 } 283out: 284 page_ref_add(page, 1); 285 vmf->page = page; 286 return 0; 287} 288 289static const struct vm_operations_struct arena_vm_ops = { 290 .close = arena_vm_close, 291 .fault = arena_vm_fault, 292}; 293 294static unsigned long arena_get_unmapped_area(struct file *filp, unsigned long addr, 295 unsigned long len, unsigned long pgoff, 296 unsigned long flags) 297{ 298 struct bpf_map *map = filp->private_data; 299 struct bpf_arena *arena = container_of(map, struct bpf_arena, map); 300 long ret; 301 302 if (pgoff) 303 return -EINVAL; 304 if (len > SZ_4G) 305 return -E2BIG; 306 307 /* if user_vm_start was specified at arena creation time */ 308 if (arena->user_vm_start) { 309 if (len > arena->user_vm_end - arena->user_vm_start) 310 return -E2BIG; 311 if (len != arena->user_vm_end - arena->user_vm_start) 312 return -EINVAL; 313 if (addr != arena->user_vm_start) 314 return -EINVAL; 315 } 316 317 ret = current->mm->get_unmapped_area(filp, addr, len * 2, 0, flags); 318 if (IS_ERR_VALUE(ret)) 319 return ret; 320 if ((ret >> 32) == ((ret + len - 1) >> 32)) 321 return ret; 322 if (WARN_ON_ONCE(arena->user_vm_start)) 323 /* checks at map creation time should prevent this */ 324 return -EFAULT; 325 return round_up(ret, SZ_4G); 326} 327 328static int arena_map_mmap(struct bpf_map *map, struct vm_area_struct *vma) 329{ 330 struct bpf_arena *arena = container_of(map, struct bpf_arena, map); 331 332 guard(mutex)(&arena->lock); 333 if (arena->user_vm_start && arena->user_vm_start != vma->vm_start) 334 /* 335 * If map_extra was not specified at arena creation time then 336 * 1st user process can do mmap(NULL, ...) to pick user_vm_start 337 * 2nd user process must pass the same addr to mmap(addr, MAP_FIXED..); 338 * or 339 * specify addr in map_extra and 340 * use the same addr later with mmap(addr, MAP_FIXED..); 341 */ 342 return -EBUSY; 343 344 if (arena->user_vm_end && arena->user_vm_end != vma->vm_end) 345 /* all user processes must have the same size of mmap-ed region */ 346 return -EBUSY; 347 348 /* Earlier checks should prevent this */ 349 if (WARN_ON_ONCE(vma->vm_end - vma->vm_start > SZ_4G || vma->vm_pgoff)) 350 return -EFAULT; 351 352 if (remember_vma(arena, vma)) 353 return -ENOMEM; 354 355 arena->user_vm_start = vma->vm_start; 356 arena->user_vm_end = vma->vm_end; 357 /* 358 * bpf_map_mmap() checks that it's being mmaped as VM_SHARED and 359 * clears VM_MAYEXEC. Set VM_DONTEXPAND as well to avoid 360 * potential change of user_vm_start. 361 */ 362 vm_flags_set(vma, VM_DONTEXPAND); 363 vma->vm_ops = &arena_vm_ops; 364 return 0; 365} 366 367static int arena_map_direct_value_addr(const struct bpf_map *map, u64 *imm, u32 off) 368{ 369 struct bpf_arena *arena = container_of(map, struct bpf_arena, map); 370 371 if ((u64)off > arena->user_vm_end - arena->user_vm_start) 372 return -ERANGE; 373 *imm = (unsigned long)arena->user_vm_start; 374 return 0; 375} 376 377BTF_ID_LIST_SINGLE(bpf_arena_map_btf_ids, struct, bpf_arena) 378const struct bpf_map_ops arena_map_ops = { 379 .map_meta_equal = bpf_map_meta_equal, 380 .map_alloc = arena_map_alloc, 381 .map_free = arena_map_free, 382 .map_direct_value_addr = arena_map_direct_value_addr, 383 .map_mmap = arena_map_mmap, 384 .map_get_unmapped_area = arena_get_unmapped_area, 385 .map_get_next_key = arena_map_get_next_key, 386 .map_push_elem = arena_map_push_elem, 387 .map_peek_elem = arena_map_peek_elem, 388 .map_pop_elem = arena_map_pop_elem, 389 .map_lookup_elem = arena_map_lookup_elem, 390 .map_update_elem = arena_map_update_elem, 391 .map_delete_elem = arena_map_delete_elem, 392 .map_check_btf = arena_map_check_btf, 393 .map_mem_usage = arena_map_mem_usage, 394 .map_btf_id = &bpf_arena_map_btf_ids[0], 395}; 396 397static u64 clear_lo32(u64 val) 398{ 399 return val & ~(u64)~0U; 400} 401 402/* 403 * Allocate pages and vmap them into kernel vmalloc area. 404 * Later the pages will be mmaped into user space vma. 405 */ 406static long arena_alloc_pages(struct bpf_arena *arena, long uaddr, long page_cnt, int node_id) 407{ 408 /* user_vm_end/start are fixed before bpf prog runs */ 409 long page_cnt_max = (arena->user_vm_end - arena->user_vm_start) >> PAGE_SHIFT; 410 u64 kern_vm_start = bpf_arena_get_kern_vm_start(arena); 411 struct page **pages; 412 long pgoff = 0; 413 u32 uaddr32; 414 int ret, i; 415 416 if (page_cnt > page_cnt_max) 417 return 0; 418 419 if (uaddr) { 420 if (uaddr & ~PAGE_MASK) 421 return 0; 422 pgoff = compute_pgoff(arena, uaddr); 423 if (pgoff > page_cnt_max - page_cnt) 424 /* requested address will be outside of user VMA */ 425 return 0; 426 } 427 428 /* zeroing is needed, since alloc_pages_bulk_array() only fills in non-zero entries */ 429 pages = kvcalloc(page_cnt, sizeof(struct page *), GFP_KERNEL); 430 if (!pages) 431 return 0; 432 433 guard(mutex)(&arena->lock); 434 435 if (uaddr) 436 ret = mtree_insert_range(&arena->mt, pgoff, pgoff + page_cnt - 1, 437 MT_ENTRY, GFP_KERNEL); 438 else 439 ret = mtree_alloc_range(&arena->mt, &pgoff, MT_ENTRY, 440 page_cnt, 0, page_cnt_max - 1, GFP_KERNEL); 441 if (ret) 442 goto out_free_pages; 443 444 ret = bpf_map_alloc_pages(&arena->map, GFP_KERNEL | __GFP_ZERO, 445 node_id, page_cnt, pages); 446 if (ret) 447 goto out; 448 449 uaddr32 = (u32)(arena->user_vm_start + pgoff * PAGE_SIZE); 450 /* Earlier checks made sure that uaddr32 + page_cnt * PAGE_SIZE - 1 451 * will not overflow 32-bit. Lower 32-bit need to represent 452 * contiguous user address range. 453 * Map these pages at kern_vm_start base. 454 * kern_vm_start + uaddr32 + page_cnt * PAGE_SIZE - 1 can overflow 455 * lower 32-bit and it's ok. 456 */ 457 ret = vm_area_map_pages(arena->kern_vm, kern_vm_start + uaddr32, 458 kern_vm_start + uaddr32 + page_cnt * PAGE_SIZE, pages); 459 if (ret) { 460 for (i = 0; i < page_cnt; i++) 461 __free_page(pages[i]); 462 goto out; 463 } 464 kvfree(pages); 465 return clear_lo32(arena->user_vm_start) + uaddr32; 466out: 467 mtree_erase(&arena->mt, pgoff); 468out_free_pages: 469 kvfree(pages); 470 return 0; 471} 472 473/* 474 * If page is present in vmalloc area, unmap it from vmalloc area, 475 * unmap it from all user space vma-s, 476 * and free it. 477 */ 478static void zap_pages(struct bpf_arena *arena, long uaddr, long page_cnt) 479{ 480 struct vma_list *vml; 481 482 list_for_each_entry(vml, &arena->vma_list, head) 483 zap_page_range_single(vml->vma, uaddr, 484 PAGE_SIZE * page_cnt, NULL); 485} 486 487static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt) 488{ 489 u64 full_uaddr, uaddr_end; 490 long kaddr, pgoff, i; 491 struct page *page; 492 493 /* only aligned lower 32-bit are relevant */ 494 uaddr = (u32)uaddr; 495 uaddr &= PAGE_MASK; 496 full_uaddr = clear_lo32(arena->user_vm_start) + uaddr; 497 uaddr_end = min(arena->user_vm_end, full_uaddr + (page_cnt << PAGE_SHIFT)); 498 if (full_uaddr >= uaddr_end) 499 return; 500 501 page_cnt = (uaddr_end - full_uaddr) >> PAGE_SHIFT; 502 503 guard(mutex)(&arena->lock); 504 505 pgoff = compute_pgoff(arena, uaddr); 506 /* clear range */ 507 mtree_store_range(&arena->mt, pgoff, pgoff + page_cnt - 1, NULL, GFP_KERNEL); 508 509 if (page_cnt > 1) 510 /* bulk zap if multiple pages being freed */ 511 zap_pages(arena, full_uaddr, page_cnt); 512 513 kaddr = bpf_arena_get_kern_vm_start(arena) + uaddr; 514 for (i = 0; i < page_cnt; i++, kaddr += PAGE_SIZE, full_uaddr += PAGE_SIZE) { 515 page = vmalloc_to_page((void *)kaddr); 516 if (!page) 517 continue; 518 if (page_cnt == 1 && page_mapped(page)) /* mapped by some user process */ 519 /* Optimization for the common case of page_cnt==1: 520 * If page wasn't mapped into some user vma there 521 * is no need to call zap_pages which is slow. When 522 * page_cnt is big it's faster to do the batched zap. 523 */ 524 zap_pages(arena, full_uaddr, 1); 525 vm_area_unmap_pages(arena->kern_vm, kaddr, kaddr + PAGE_SIZE); 526 __free_page(page); 527 } 528} 529 530__bpf_kfunc_start_defs(); 531 532__bpf_kfunc void *bpf_arena_alloc_pages(void *p__map, void *addr__ign, u32 page_cnt, 533 int node_id, u64 flags) 534{ 535 struct bpf_map *map = p__map; 536 struct bpf_arena *arena = container_of(map, struct bpf_arena, map); 537 538 if (map->map_type != BPF_MAP_TYPE_ARENA || flags || !page_cnt) 539 return NULL; 540 541 return (void *)arena_alloc_pages(arena, (long)addr__ign, page_cnt, node_id); 542} 543 544__bpf_kfunc void bpf_arena_free_pages(void *p__map, void *ptr__ign, u32 page_cnt) 545{ 546 struct bpf_map *map = p__map; 547 struct bpf_arena *arena = container_of(map, struct bpf_arena, map); 548 549 if (map->map_type != BPF_MAP_TYPE_ARENA || !page_cnt || !ptr__ign) 550 return; 551 arena_free_pages(arena, (long)ptr__ign, page_cnt); 552} 553__bpf_kfunc_end_defs(); 554 555BTF_KFUNCS_START(arena_kfuncs) 556BTF_ID_FLAGS(func, bpf_arena_alloc_pages, KF_TRUSTED_ARGS | KF_SLEEPABLE) 557BTF_ID_FLAGS(func, bpf_arena_free_pages, KF_TRUSTED_ARGS | KF_SLEEPABLE) 558BTF_KFUNCS_END(arena_kfuncs) 559 560static const struct btf_kfunc_id_set common_kfunc_set = { 561 .owner = THIS_MODULE, 562 .set = &arena_kfuncs, 563}; 564 565static int __init kfunc_init(void) 566{ 567 return register_btf_kfunc_id_set(BPF_PROG_TYPE_UNSPEC, &common_kfunc_set); 568} 569late_initcall(kfunc_init); 570