개념 설명 전체 · v6.18.37 / mm/vmalloc.c
1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * Copyright (C) 1993 Linus Torvalds 4 * Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999 5 * SMP-safe vmalloc/vfree/ioremap, Tigran Aivazian <tigran@veritas.com>, May 2000 6 * Major rework to support vmap/vunmap, Christoph Hellwig, SGI, August 2002 7 * Numa awareness, Christoph Lameter, SGI, June 2005 8 * Improving global KVA allocator, Uladzislau Rezki, Sony, May 2019 9 */ 10 11 #include <linux/vmalloc.h> 12 #include <linux/mm.h> 13 #include <linux/module.h> 14 #include <linux/highmem.h> 15 #include <linux/sched/signal.h> 16 #include <linux/slab.h> 17 #include <linux/spinlock.h> 18 #include <linux/interrupt.h> 19 #include <linux/proc_fs.h> 20 #include <linux/seq_file.h> 21 #include <linux/set_memory.h> 22 #include <linux/debugobjects.h> 23 #include <linux/kallsyms.h> 24 #include <linux/list.h> 25 #include <linux/notifier.h> 26 #include <linux/rbtree.h> 27 #include <linux/xarray.h> 28 #include <linux/io.h> 29 #include <linux/rcupdate.h> 30 #include <linux/pfn.h> 31 #include <linux/kmemleak.h> 32 #include <linux/atomic.h> 33 #include <linux/compiler.h> 34 #include <linux/memcontrol.h> 35 #include <linux/llist.h> 36 #include <linux/uio.h> 37 #include <linux/bitops.h> 38 #include <linux/rbtree_augmented.h> 39 #include <linux/overflow.h> 40 #include <linux/pgtable.h> 41 #include <linux/hugetlb.h> 42 #include <linux/sched/mm.h> 43 #include <asm/tlbflush.h> 44 #include <asm/shmparam.h> 45 #include <linux/page_owner.h> 46 47 #define CREATE_TRACE_POINTS 48 #include <trace/events/vmalloc.h> 49 50 #include "internal.h" 51 #include "pgalloc-track.h" 52 53 #ifdef CONFIG_HAVE_ARCH_HUGE_VMAP 54 static unsigned int __ro_after_init ioremap_max_page_shift = BITS_PER_LONG - 1; 55 56 static int __init set_nohugeiomap(char *str) 57 { 58 ioremap_max_page_shift = PAGE_SHIFT; 59 return 0; 60 } 61 early_param("nohugeiomap", set_nohugeiomap); 62 #else /* CONFIG_HAVE_ARCH_HUGE_VMAP */ 63 static const unsigned int ioremap_max_page_shift = PAGE_SHIFT; 64 #endif /* CONFIG_HAVE_ARCH_HUGE_VMAP */ 65 66 #ifdef CONFIG_HAVE_ARCH_HUGE_VMALLOC 67 static bool __ro_after_init vmap_allow_huge = true; 68 69 static int __init set_nohugevmalloc(char *str) 70 { 71 vmap_allow_huge = false; 72 return 0; 73 } 74 early_param("nohugevmalloc", set_nohugevmalloc); 75 #else /* CONFIG_HAVE_ARCH_HUGE_VMALLOC */ 76 static const bool vmap_allow_huge = false; 77 #endif /* CONFIG_HAVE_ARCH_HUGE_VMALLOC */ 78 79 bool is_vmalloc_addr(const void *x) 80 { 81 unsigned long addr = (unsigned long)kasan_reset_tag(x); 82 83 return addr >= VMALLOC_START && addr < VMALLOC_END; 84 } 85 EXPORT_SYMBOL(is_vmalloc_addr); 86 87 struct vfree_deferred { 88 struct llist_head list; 89 struct work_struct wq; 90 }; 91 static DEFINE_PER_CPU(struct vfree_deferred, vfree_deferred); 92 93 /*** Page table manipulation functions ***/ 94 static int vmap_pte_range(pmd_t *pmd, unsigned long addr, unsigned long end, 95 phys_addr_t phys_addr, pgprot_t prot, 96 unsigned int max_page_shift, pgtbl_mod_mask *mask) 97 { 98 pte_t *pte; 99 u64 pfn; 100 struct page *page; 101 unsigned long size = PAGE_SIZE; 102 103 pfn = phys_addr >> PAGE_SHIFT; 104 pte = pte_alloc_kernel_track(pmd, addr, mask); 105 if (!pte) 106 return -ENOMEM; 107 108 arch_enter_lazy_mmu_mode(); 109 110 do { 111 if (unlikely(!pte_none(ptep_get(pte)))) { 112 if (pfn_valid(pfn)) { 113 page = pfn_to_page(pfn); 114 dump_page(page, "remapping already mapped page"); 115 } 116 BUG(); 117 } 118 119 #ifdef CONFIG_HUGETLB_PAGE 120 size = arch_vmap_pte_range_map_size(addr, end, pfn, max_page_shift); 121 if (size != PAGE_SIZE) { 122 pte_t entry = pfn_pte(pfn, prot); 123 124 entry = arch_make_huge_pte(entry, ilog2(size), 0); 125 set_huge_pte_at(&init_mm, addr, pte, entry, size); 126 pfn += PFN_DOWN(size); 127 continue; 128 } 129 #endif 130 set_pte_at(&init_mm, addr, pte, pfn_pte(pfn, prot)); 131 pfn++; 132 } while (pte += PFN_DOWN(size), addr += size, addr != end); 133 134 arch_leave_lazy_mmu_mode(); 135 *mask |= PGTBL_PTE_MODIFIED; 136 return 0; 137 } 138 139 static int vmap_try_huge_pmd(pmd_t *pmd, unsigned long addr, unsigned long end, 140 phys_addr_t phys_addr, pgprot_t prot, 141 unsigned int max_page_shift) 142 { 143 if (max_page_shift < PMD_SHIFT) 144 return 0; 145 146 if (!arch_vmap_pmd_supported(prot)) 147 return 0; 148 149 if ((end - addr) != PMD_SIZE) 150 return 0; 151 152 if (!IS_ALIGNED(addr, PMD_SIZE)) 153 return 0; 154 155 if (!IS_ALIGNED(phys_addr, PMD_SIZE)) 156 return 0; 157 158 if (pmd_present(*pmd) && !pmd_free_pte_page(pmd, addr)) 159 return 0; 160 161 return pmd_set_huge(pmd, phys_addr, prot); 162 } 163 164 static int vmap_pmd_range(pud_t *pud, unsigned long addr, unsigned long end, 165 phys_addr_t phys_addr, pgprot_t prot, 166 unsigned int max_page_shift, pgtbl_mod_mask *mask) 167 { 168 pmd_t *pmd; 169 unsigned long next; 170 171 pmd = pmd_alloc_track(&init_mm, pud, addr, mask); 172 if (!pmd) 173 return -ENOMEM; 174 do { 175 next = pmd_addr_end(addr, end); 176 177 if (vmap_try_huge_pmd(pmd, addr, next, phys_addr, prot, 178 max_page_shift)) { 179 *mask |= PGTBL_PMD_MODIFIED; 180 continue; 181 } 182 183 if (vmap_pte_range(pmd, addr, next, phys_addr, prot, max_page_shift, mask)) 184 return -ENOMEM; 185 } while (pmd++, phys_addr += (next - addr), addr = next, addr != end); 186 return 0; 187 } 188 189 static int vmap_try_huge_pud(pud_t *pud, unsigned long addr, unsigned long end, 190 phys_addr_t phys_addr, pgprot_t prot, 191 unsigned int max_page_shift) 192 { 193 if (max_page_shift < PUD_SHIFT) 194 return 0; 195 196 if (!arch_vmap_pud_supported(prot)) 197 return 0; 198 199 if ((end - addr) != PUD_SIZE) 200 return 0; 201 202 if (!IS_ALIGNED(addr, PUD_SIZE)) 203 return 0; 204 205 if (!IS_ALIGNED(phys_addr, PUD_SIZE)) 206 return 0; 207 208 if (pud_present(*pud) && !pud_free_pmd_page(pud, addr)) 209 return 0; 210 211 return pud_set_huge(pud, phys_addr, prot); 212 } 213 214 static int vmap_pud_range(p4d_t *p4d, unsigned long addr, unsigned long end, 215 phys_addr_t phys_addr, pgprot_t prot, 216 unsigned int max_page_shift, pgtbl_mod_mask *mask) 217 { 218 pud_t *pud; 219 unsigned long next; 220 221 pud = pud_alloc_track(&init_mm, p4d, addr, mask); 222 if (!pud) 223 return -ENOMEM; 224 do { 225 next = pud_addr_end(addr, end); 226 227 if (vmap_try_huge_pud(pud, addr, next, phys_addr, prot, 228 max_page_shift)) { 229 *mask |= PGTBL_PUD_MODIFIED; 230 continue; 231 } 232 233 if (vmap_pmd_range(pud, addr, next, phys_addr, prot, 234 max_page_shift, mask)) 235 return -ENOMEM; 236 } while (pud++, phys_addr += (next - addr), addr = next, addr != end); 237 return 0; 238 } 239 240 static int vmap_try_huge_p4d(p4d_t *p4d, unsigned long addr, unsigned long end, 241 phys_addr_t phys_addr, pgprot_t prot, 242 unsigned int max_page_shift) 243 { 244 if (max_page_shift < P4D_SHIFT) 245 return 0; 246 247 if (!arch_vmap_p4d_supported(prot)) 248 return 0; 249 250 if ((end - addr) != P4D_SIZE) 251 return 0; 252 253 if (!IS_ALIGNED(addr, P4D_SIZE)) 254 return 0; 255 256 if (!IS_ALIGNED(phys_addr, P4D_SIZE)) 257 return 0; 258 259 if (p4d_present(*p4d) && !p4d_free_pud_page(p4d, addr)) 260 return 0; 261 262 return p4d_set_huge(p4d, phys_addr, prot); 263 } 264 265 static int vmap_p4d_range(pgd_t *pgd, unsigned long addr, unsigned long end, 266 phys_addr_t phys_addr, pgprot_t prot, 267 unsigned int max_page_shift, pgtbl_mod_mask *mask) 268 { 269 p4d_t *p4d; 270 unsigned long next; 271 272 p4d = p4d_alloc_track(&init_mm, pgd, addr, mask); 273 if (!p4d) 274 return -ENOMEM; 275 do { 276 next = p4d_addr_end(addr, end); 277 278 if (vmap_try_huge_p4d(p4d, addr, next, phys_addr, prot, 279 max_page_shift)) { 280 *mask |= PGTBL_P4D_MODIFIED; 281 continue; 282 } 283 284 if (vmap_pud_range(p4d, addr, next, phys_addr, prot, 285 max_page_shift, mask)) 286 return -ENOMEM; 287 } while (p4d++, phys_addr += (next - addr), addr = next, addr != end); 288 return 0; 289 } 290 291 static int vmap_range_noflush(unsigned long addr, unsigned long end, 292 phys_addr_t phys_addr, pgprot_t prot, 293 unsigned int max_page_shift) 294 { 295 pgd_t *pgd; 296 unsigned long start; 297 unsigned long next; 298 int err; 299 pgtbl_mod_mask mask = 0; 300 301 might_sleep(); 302 BUG_ON(addr >= end); 303 304 start = addr; 305 pgd = pgd_offset_k(addr); 306 do { 307 next = pgd_addr_end(addr, end); 308 err = vmap_p4d_range(pgd, addr, next, phys_addr, prot, 309 max_page_shift, &mask); 310 if (err) 311 break; 312 } while (pgd++, phys_addr += (next - addr), addr = next, addr != end); 313 314 if (mask & ARCH_PAGE_TABLE_SYNC_MASK) 315 arch_sync_kernel_mappings(start, end); 316 317 return err; 318 } 319 320 int vmap_page_range(unsigned long addr, unsigned long end, 321 phys_addr_t phys_addr, pgprot_t prot) 322 { 323 int err; 324 325 err = vmap_range_noflush(addr, end, phys_addr, pgprot_nx(prot), 326 ioremap_max_page_shift); 327 flush_cache_vmap(addr, end); 328 if (!err) 329 err = kmsan_ioremap_page_range(addr, end, phys_addr, prot, 330 ioremap_max_page_shift); 331 return err; 332 } 333 334 int ioremap_page_range(unsigned long addr, unsigned long end, 335 phys_addr_t phys_addr, pgprot_t prot) 336 { 337 struct vm_struct *area; 338 339 area = find_vm_area((void *)addr); 340 if (!area || !(area->flags & VM_IOREMAP)) { 341 WARN_ONCE(1, "vm_area at addr %lx is not marked as VM_IOREMAP\n", addr); 342 return -EINVAL; 343 } 344 if (addr != (unsigned long)area->addr || 345 (void *)end != area->addr + get_vm_area_size(area)) { 346 WARN_ONCE(1, "ioremap request [%lx,%lx) doesn't match vm_area [%lx, %lx)\n", 347 addr, end, (long)area->addr, 348 (long)area->addr + get_vm_area_size(area)); 349 return -ERANGE; 350 } 351 return vmap_page_range(addr, end, phys_addr, prot); 352 } 353 354 static void vunmap_pte_range(pmd_t *pmd, unsigned long addr, unsigned long end, 355 pgtbl_mod_mask *mask) 356 { 357 pte_t *pte; 358 pte_t ptent; 359 unsigned long size = PAGE_SIZE; 360 361 pte = pte_offset_kernel(pmd, addr); 362 arch_enter_lazy_mmu_mode(); 363 364 do { 365 #ifdef CONFIG_HUGETLB_PAGE 366 size = arch_vmap_pte_range_unmap_size(addr, pte); 367 if (size != PAGE_SIZE) { 368 if (WARN_ON(!IS_ALIGNED(addr, size))) { 369 addr = ALIGN_DOWN(addr, size); 370 pte = PTR_ALIGN_DOWN(pte, sizeof(*pte) * (size >> PAGE_SHIFT)); 371 } 372 ptent = huge_ptep_get_and_clear(&init_mm, addr, pte, size); 373 if (WARN_ON(end - addr < size)) 374 size = end - addr; 375 } else 376 #endif 377 ptent = ptep_get_and_clear(&init_mm, addr, pte); 378 WARN_ON(!pte_none(ptent) && !pte_present(ptent)); 379 } while (pte += (size >> PAGE_SHIFT), addr += size, addr != end); 380 381 arch_leave_lazy_mmu_mode(); 382 *mask |= PGTBL_PTE_MODIFIED; 383 } 384 385 static void vunmap_pmd_range(pud_t *pud, unsigned long addr, unsigned long end, 386 pgtbl_mod_mask *mask) 387 { 388 pmd_t *pmd; 389 unsigned long next; 390 int cleared; 391 392 pmd = pmd_offset(pud, addr); 393 do { 394 next = pmd_addr_end(addr, end); 395 396 cleared = pmd_clear_huge(pmd); 397 if (cleared || pmd_bad(*pmd)) 398 *mask |= PGTBL_PMD_MODIFIED; 399 400 if (cleared) { 401 WARN_ON(next - addr < PMD_SIZE); 402 continue; 403 } 404 if (pmd_none_or_clear_bad(pmd)) 405 continue; 406 vunmap_pte_range(pmd, addr, next, mask); 407 408 cond_resched(); 409 } while (pmd++, addr = next, addr != end); 410 } 411 412 static void vunmap_pud_range(p4d_t *p4d, unsigned long addr, unsigned long end, 413 pgtbl_mod_mask *mask) 414 { 415 pud_t *pud; 416 unsigned long next; 417 int cleared; 418 419 pud = pud_offset(p4d, addr); 420 do { 421 next = pud_addr_end(addr, end); 422 423 cleared = pud_clear_huge(pud); 424 if (cleared || pud_bad(*pud)) 425 *mask |= PGTBL_PUD_MODIFIED; 426 427 if (cleared) { 428 WARN_ON(next - addr < PUD_SIZE); 429 continue; 430 } 431 if (pud_none_or_clear_bad(pud)) 432 continue; 433 vunmap_pmd_range(pud, addr, next, mask); 434 } while (pud++, addr = next, addr != end); 435 } 436 437 static void vunmap_p4d_range(pgd_t *pgd, unsigned long addr, unsigned long end, 438 pgtbl_mod_mask *mask) 439 { 440 p4d_t *p4d; 441 unsigned long next; 442 443 p4d = p4d_offset(pgd, addr); 444 do { 445 next = p4d_addr_end(addr, end); 446 447 p4d_clear_huge(p4d); 448 if (p4d_bad(*p4d)) 449 *mask |= PGTBL_P4D_MODIFIED; 450 451 if (p4d_none_or_clear_bad(p4d)) 452 continue; 453 vunmap_pud_range(p4d, addr, next, mask); 454 } while (p4d++, addr = next, addr != end); 455 } 456 457 /* 458 * vunmap_range_noflush is similar to vunmap_range, but does not 459 * flush caches or TLBs. 460 * 461 * The caller is responsible for calling flush_cache_vmap() before calling 462 * this function, and flush_tlb_kernel_range after it has returned 463 * successfully (and before the addresses are expected to cause a page fault 464 * or be re-mapped for something else, if TLB flushes are being delayed or 465 * coalesced). 466 * 467 * This is an internal function only. Do not use outside mm/. 468 */ 469 void __vunmap_range_noflush(unsigned long start, unsigned long end) 470 { 471 unsigned long next; 472 pgd_t *pgd; 473 unsigned long addr = start; 474 pgtbl_mod_mask mask = 0; 475 476 BUG_ON(addr >= end); 477 pgd = pgd_offset_k(addr); 478 do { 479 next = pgd_addr_end(addr, end); 480 if (pgd_bad(*pgd)) 481 mask |= PGTBL_PGD_MODIFIED; 482 if (pgd_none_or_clear_bad(pgd)) 483 continue; 484 vunmap_p4d_range(pgd, addr, next, &mask); 485 } while (pgd++, addr = next, addr != end); 486 487 if (mask & ARCH_PAGE_TABLE_SYNC_MASK) 488 arch_sync_kernel_mappings(start, end); 489 } 490 491 void vunmap_range_noflush(unsigned long start, unsigned long end) 492 { 493 kmsan_vunmap_range_noflush(start, end); 494 __vunmap_range_noflush(start, end); 495 } 496 497 /** 498 * vunmap_range - unmap kernel virtual addresses 499 * @addr: start of the VM area to unmap 500 * @end: end of the VM area to unmap (non-inclusive) 501 * 502 * Clears any present PTEs in the virtual address range, flushes TLBs and 503 * caches. Any subsequent access to the address before it has been re-mapped 504 * is a kernel bug. 505 */ 506 void vunmap_range(unsigned long addr, unsigned long end) 507 { 508 flush_cache_vunmap(addr, end); 509 vunmap_range_noflush(addr, end); 510 flush_tlb_kernel_range(addr, end); 511 } 512 513 static int vmap_pages_pte_range(pmd_t *pmd, unsigned long addr, 514 unsigned long end, pgprot_t prot, struct page **pages, int *nr, 515 pgtbl_mod_mask *mask) 516 { 517 int err = 0; 518 pte_t *pte; 519 520 /* 521 * nr is a running index into the array which helps higher level 522 * callers keep track of where we're up to. 523 */ 524 525 pte = pte_alloc_kernel_track(pmd, addr, mask); 526 if (!pte) 527 return -ENOMEM; 528 529 arch_enter_lazy_mmu_mode(); 530 531 do { 532 struct page *page = pages[*nr]; 533 534 if (WARN_ON(!pte_none(ptep_get(pte)))) { 535 err = -EBUSY; 536 break; 537 } 538 if (WARN_ON(!page)) { 539 err = -ENOMEM; 540 break; 541 } 542 if (WARN_ON(!pfn_valid(page_to_pfn(page)))) { 543 err = -EINVAL; 544 break; 545 } 546 547 set_pte_at(&init_mm, addr, pte, mk_pte(page, prot)); 548 (*nr)++; 549 } while (pte++, addr += PAGE_SIZE, addr != end); 550 551 arch_leave_lazy_mmu_mode(); 552 *mask |= PGTBL_PTE_MODIFIED; 553 554 return err; 555 } 556 557 static int vmap_pages_pmd_range(pud_t *pud, unsigned long addr, 558 unsigned long end, pgprot_t prot, struct page **pages, int *nr, 559 pgtbl_mod_mask *mask) 560 { 561 pmd_t *pmd; 562 unsigned long next; 563 564 pmd = pmd_alloc_track(&init_mm, pud, addr, mask); 565 if (!pmd) 566 return -ENOMEM; 567 do { 568 next = pmd_addr_end(addr, end); 569 if (vmap_pages_pte_range(pmd, addr, next, prot, pages, nr, mask)) 570 return -ENOMEM; 571 } while (pmd++, addr = next, addr != end); 572 return 0; 573 } 574 575 static int vmap_pages_pud_range(p4d_t *p4d, unsigned long addr, 576 unsigned long end, pgprot_t prot, struct page **pages, int *nr, 577 pgtbl_mod_mask *mask) 578 { 579 pud_t *pud; 580 unsigned long next; 581 582 pud = pud_alloc_track(&init_mm, p4d, addr, mask); 583 if (!pud) 584 return -ENOMEM; 585 do { 586 next = pud_addr_end(addr, end); 587 if (vmap_pages_pmd_range(pud, addr, next, prot, pages, nr, mask)) 588 return -ENOMEM; 589 } while (pud++, addr = next, addr != end); 590 return 0; 591 } 592 593 static int vmap_pages_p4d_range(pgd_t *pgd, unsigned long addr, 594 unsigned long end, pgprot_t prot, struct page **pages, int *nr, 595 pgtbl_mod_mask *mask) 596 { 597 p4d_t *p4d; 598 unsigned long next; 599 600 p4d = p4d_alloc_track(&init_mm, pgd, addr, mask); 601 if (!p4d) 602 return -ENOMEM; 603 do { 604 next = p4d_addr_end(addr, end); 605 if (vmap_pages_pud_range(p4d, addr, next, prot, pages, nr, mask)) 606 return -ENOMEM; 607 } while (p4d++, addr = next, addr != end); 608 return 0; 609 } 610 611 static int vmap_small_pages_range_noflush(unsigned long addr, unsigned long end, 612 pgprot_t prot, struct page **pages) 613 { 614 unsigned long start = addr; 615 pgd_t *pgd; 616 unsigned long next; 617 int err = 0; 618 int nr = 0; 619 pgtbl_mod_mask mask = 0; 620 621 BUG_ON(addr >= end); 622 pgd = pgd_offset_k(addr); 623 do { 624 next = pgd_addr_end(addr, end); 625 if (pgd_bad(*pgd)) 626 mask |= PGTBL_PGD_MODIFIED; 627 err = vmap_pages_p4d_range(pgd, addr, next, prot, pages, &nr, &mask); 628 if (err) 629 break; 630 } while (pgd++, addr = next, addr != end); 631 632 if (mask & ARCH_PAGE_TABLE_SYNC_MASK) 633 arch_sync_kernel_mappings(start, end); 634 635 return err; 636 } 637 638 /* 639 * vmap_pages_range_noflush is similar to vmap_pages_range, but does not 640 * flush caches. 641 * 642 * The caller is responsible for calling flush_cache_vmap() after this 643 * function returns successfully and before the addresses are accessed. 644 * 645 * This is an internal function only. Do not use outside mm/. 646 */ 647 int __vmap_pages_range_noflush(unsigned long addr, unsigned long end, 648 pgprot_t prot, struct page **pages, unsigned int page_shift) 649 { 650 unsigned int i, nr = (end - addr) >> PAGE_SHIFT; 651 652 WARN_ON(page_shift < PAGE_SHIFT); 653 654 if (!IS_ENABLED(CONFIG_HAVE_ARCH_HUGE_VMALLOC) || 655 page_shift == PAGE_SHIFT) 656 return vmap_small_pages_range_noflush(addr, end, prot, pages); 657 658 for (i = 0; i < nr; i += 1U << (page_shift - PAGE_SHIFT)) { 659 int err; 660 661 err = vmap_range_noflush(addr, addr + (1UL << page_shift), 662 page_to_phys(pages[i]), prot, 663 page_shift); 664 if (err) 665 return err; 666 667 addr += 1UL << page_shift; 668 } 669 670 return 0; 671 } 672 673 int vmap_pages_range_noflush(unsigned long addr, unsigned long end, 674 pgprot_t prot, struct page **pages, unsigned int page_shift) 675 { 676 int ret = kmsan_vmap_pages_range_noflush(addr, end, prot, pages, 677 page_shift); 678 679 if (ret) 680 return ret; 681 return __vmap_pages_range_noflush(addr, end, prot, pages, page_shift); 682 } 683 684 /** 685 * vmap_pages_range - map pages to a kernel virtual address 686 * @addr: start of the VM area to map 687 * @end: end of the VM area to map (non-inclusive) 688 * @prot: page protection flags to use 689 * @pages: pages to map (always PAGE_SIZE pages) 690 * @page_shift: maximum shift that the pages may be mapped with, @pages must 691 * be aligned and contiguous up to at least this shift. 692 * 693 * RETURNS: 694 * 0 on success, -errno on failure. 695 */ 696 int vmap_pages_range(unsigned long addr, unsigned long end, 697 pgprot_t prot, struct page **pages, unsigned int page_shift) 698 { 699 int err; 700 701 err = vmap_pages_range_noflush(addr, end, prot, pages, page_shift); 702 flush_cache_vmap(addr, end); 703 return err; 704 } 705 706 static int check_sparse_vm_area(struct vm_struct *area, unsigned long start, 707 unsigned long end) 708 { 709 might_sleep(); 710 if (WARN_ON_ONCE(area->flags & VM_FLUSH_RESET_PERMS)) 711 return -EINVAL; 712 if (WARN_ON_ONCE(area->flags & VM_NO_GUARD)) 713 return -EINVAL; 714 if (WARN_ON_ONCE(!(area->flags & VM_SPARSE))) 715 return -EINVAL; 716 if ((end - start) >> PAGE_SHIFT > totalram_pages()) 717 return -E2BIG; 718 if (start < (unsigned long)area->addr || 719 (void *)end > area->addr + get_vm_area_size(area)) 720 return -ERANGE; 721 return 0; 722 } 723 724 /** 725 * vm_area_map_pages - map pages inside given sparse vm_area 726 * @area: vm_area 727 * @start: start address inside vm_area 728 * @end: end address inside vm_area 729 * @pages: pages to map (always PAGE_SIZE pages) 730 */ 731 int vm_area_map_pages(struct vm_struct *area, unsigned long start, 732 unsigned long end, struct page **pages) 733 { 734 int err; 735 736 err = check_sparse_vm_area(area, start, end); 737 if (err) 738 return err; 739 740 return vmap_pages_range(start, end, PAGE_KERNEL, pages, PAGE_SHIFT); 741 } 742 743 /** 744 * vm_area_unmap_pages - unmap pages inside given sparse vm_area 745 * @area: vm_area 746 * @start: start address inside vm_area 747 * @end: end address inside vm_area 748 */ 749 void vm_area_unmap_pages(struct vm_struct *area, unsigned long start, 750 unsigned long end) 751 { 752 if (check_sparse_vm_area(area, start, end)) 753 return; 754 755 vunmap_range(start, end); 756 } 757 758 int is_vmalloc_or_module_addr(const void *x) 759 { 760 /* 761 * ARM, x86-64 and sparc64 put modules in a special place, 762 * and fall back on vmalloc() if that fails. Others 763 * just put it in the vmalloc space. 764 */ 765 #if defined(CONFIG_EXECMEM) && defined(MODULES_VADDR) 766 unsigned long addr = (unsigned long)kasan_reset_tag(x); 767 if (addr >= MODULES_VADDR && addr < MODULES_END) 768 return 1; 769 #endif 770 return is_vmalloc_addr(x); 771 } 772 EXPORT_SYMBOL_GPL(is_vmalloc_or_module_addr); 773 774 /* 775 * Walk a vmap address to the struct page it maps. Huge vmap mappings will 776 * return the tail page that corresponds to the base page address, which 777 * matches small vmap mappings. 778 */ 779 struct page *vmalloc_to_page(const void *vmalloc_addr) 780 { 781 unsigned long addr = (unsigned long) vmalloc_addr; 782 struct page *page = NULL; 783 pgd_t *pgd = pgd_offset_k(addr); 784 p4d_t *p4d; 785 pud_t *pud; 786 pmd_t *pmd; 787 pte_t *ptep, pte; 788 789 /* 790 * XXX we might need to change this if we add VIRTUAL_BUG_ON for 791 * architectures that do not vmalloc module space 792 */ 793 VIRTUAL_BUG_ON(!is_vmalloc_or_module_addr(vmalloc_addr)); 794 795 if (pgd_none(*pgd)) 796 return NULL; 797 if (WARN_ON_ONCE(pgd_leaf(*pgd))) 798 return NULL; /* XXX: no allowance for huge pgd */ 799 if (WARN_ON_ONCE(pgd_bad(*pgd))) 800 return NULL; 801 802 p4d = p4d_offset(pgd, addr); 803 if (p4d_none(*p4d)) 804 return NULL; 805 if (p4d_leaf(*p4d)) 806 return p4d_page(*p4d) + ((addr & ~P4D_MASK) >> PAGE_SHIFT); 807 if (WARN_ON_ONCE(p4d_bad(*p4d))) 808 return NULL; 809 810 pud = pud_offset(p4d, addr); 811 if (pud_none(*pud)) 812 return NULL; 813 if (pud_leaf(*pud)) 814 return pud_page(*pud) + ((addr & ~PUD_MASK) >> PAGE_SHIFT); 815 if (WARN_ON_ONCE(pud_bad(*pud))) 816 return NULL; 817 818 pmd = pmd_offset(pud, addr); 819 if (pmd_none(*pmd)) 820 return NULL; 821 if (pmd_leaf(*pmd)) 822 return pmd_page(*pmd) + ((addr & ~PMD_MASK) >> PAGE_SHIFT); 823 if (WARN_ON_ONCE(pmd_bad(*pmd))) 824 return NULL; 825 826 ptep = pte_offset_kernel(pmd, addr); 827 pte = ptep_get(ptep); 828 if (pte_present(pte)) 829 page = pte_page(pte); 830 831 return page; 832 } 833 EXPORT_SYMBOL(vmalloc_to_page); 834 835 /* 836 * Map a vmalloc()-space virtual address to the physical page frame number. 837 */ 838 unsigned long vmalloc_to_pfn(const void *vmalloc_addr) 839 { 840 return page_to_pfn(vmalloc_to_page(vmalloc_addr)); 841 } 842 EXPORT_SYMBOL(vmalloc_to_pfn); 843 844 845 /*** Global kva allocator ***/ 846 847 #define DEBUG_AUGMENT_PROPAGATE_CHECK 0 848 #define DEBUG_AUGMENT_LOWEST_MATCH_CHECK 0 849 850 851 static DEFINE_SPINLOCK(free_vmap_area_lock); 852 static bool vmap_initialized __read_mostly; 853 854 /* 855 * This kmem_cache is used for vmap_area objects. Instead of 856 * allocating from slab we reuse an object from this cache to 857 * make things faster. Especially in "no edge" splitting of 858 * free block. 859 */ 860 static struct kmem_cache *vmap_area_cachep; 861 862 /* 863 * This linked list is used in pair with free_vmap_area_root. 864 * It gives O(1) access to prev/next to perform fast coalescing. 865 */ 866 static LIST_HEAD(free_vmap_area_list); 867 868 /* 869 * This augment red-black tree represents the free vmap space. 870 * All vmap_area objects in this tree are sorted by va->va_start 871 * address. It is used for allocation and merging when a vmap 872 * object is released. 873 * 874 * Each vmap_area node contains a maximum available free block 875 * of its sub-tree, right or left. Therefore it is possible to 876 * find a lowest match of free area. 877 */ 878 static struct rb_root free_vmap_area_root = RB_ROOT; 879 880 /* 881 * Preload a CPU with one object for "no edge" split case. The 882 * aim is to get rid of allocations from the atomic context, thus 883 * to use more permissive allocation masks. 884 */ 885 static DEFINE_PER_CPU(struct vmap_area *, ne_fit_preload_node); 886 887 /* 888 * This structure defines a single, solid model where a list and 889 * rb-tree are part of one entity protected by the lock. Nodes are 890 * sorted in ascending order, thus for O(1) access to left/right 891 * neighbors a list is used as well as for sequential traversal. 892 */ 893 struct rb_list { 894 struct rb_root root; 895 struct list_head head; 896 spinlock_t lock; 897 }; 898 899 /* 900 * A fast size storage contains VAs up to 1M size. A pool consists 901 * of linked between each other ready to go VAs of certain sizes. 902 * An index in the pool-array corresponds to number of pages + 1. 903 */ 904 #define MAX_VA_SIZE_PAGES 256 905 906 struct vmap_pool { 907 struct list_head head; 908 unsigned long len; 909 }; 910 911 /* 912 * An effective vmap-node logic. Users make use of nodes instead 913 * of a global heap. It allows to balance an access and mitigate 914 * contention. 915 */ 916 static struct vmap_node { 917 /* Simple size segregated storage. */ 918 struct vmap_pool pool[MAX_VA_SIZE_PAGES]; 919 spinlock_t pool_lock; 920 bool skip_populate; 921 922 /* Bookkeeping data of this node. */ 923 struct rb_list busy; 924 struct rb_list lazy; 925 926 /* 927 * Ready-to-free areas. 928 */ 929 struct list_head purge_list; 930 struct work_struct purge_work; 931 unsigned long nr_purged; 932 } single; 933 934 /* 935 * Initial setup consists of one single node, i.e. a balancing 936 * is fully disabled. Later on, after vmap is initialized these 937 * parameters are updated based on a system capacity. 938 */ 939 static struct vmap_node *vmap_nodes = &single; 940 static __read_mostly unsigned int nr_vmap_nodes = 1; 941 static __read_mostly unsigned int vmap_zone_size = 1; 942 943 /* A simple iterator over all vmap-nodes. */ 944 #define for_each_vmap_node(vn) \ 945 for ((vn) = &vmap_nodes[0]; \ 946 (vn) < &vmap_nodes[nr_vmap_nodes]; (vn)++) 947 948 static inline unsigned int 949 addr_to_node_id(unsigned long addr) 950 { 951 return (addr / vmap_zone_size) % nr_vmap_nodes; 952 } 953 954 static inline struct vmap_node * 955 addr_to_node(unsigned long addr) 956 { 957 return &vmap_nodes[addr_to_node_id(addr)]; 958 } 959 960 static inline struct vmap_node * 961 id_to_node(unsigned int id) 962 { 963 return &vmap_nodes[id % nr_vmap_nodes]; 964 } 965 966 static inline unsigned int 967 node_to_id(struct vmap_node *node) 968 { 969 /* Pointer arithmetic. */ 970 unsigned int id = node - vmap_nodes; 971 972 if (likely(id < nr_vmap_nodes)) 973 return id; 974 975 WARN_ONCE(1, "An address 0x%p is out-of-bounds.\n", node); 976 return 0; 977 } 978 979 /* 980 * We use the value 0 to represent "no node", that is why 981 * an encoded value will be the node-id incremented by 1. 982 * It is always greater then 0. A valid node_id which can 983 * be encoded is [0:nr_vmap_nodes - 1]. If a passed node_id 984 * is not valid 0 is returned. 985 */ 986 static unsigned int 987 encode_vn_id(unsigned int node_id) 988 { 989 /* Can store U8_MAX [0:254] nodes. */ 990 if (node_id < nr_vmap_nodes) 991 return (node_id + 1) << BITS_PER_BYTE; 992 993 /* Warn and no node encoded. */ 994 WARN_ONCE(1, "Encode wrong node id (%u)\n", node_id); 995 return 0; 996 } 997 998 /* 999 * Returns an encoded node-id, the valid range is within 1000 * [0:nr_vmap_nodes-1] values. Otherwise nr_vmap_nodes is 1001 * returned if extracted data is wrong. 1002 */ 1003 static unsigned int 1004 decode_vn_id(unsigned int val) 1005 { 1006 unsigned int node_id = (val >> BITS_PER_BYTE) - 1; 1007 1008 /* Can store U8_MAX [0:254] nodes. */ 1009 if (node_id < nr_vmap_nodes) 1010 return node_id; 1011 1012 /* If it was _not_ zero, warn. */ 1013 WARN_ONCE(node_id != UINT_MAX, 1014 "Decode wrong node id (%d)\n", node_id); 1015 1016 return nr_vmap_nodes; 1017 } 1018 1019 static bool 1020 is_vn_id_valid(unsigned int node_id) 1021 { 1022 if (node_id < nr_vmap_nodes) 1023 return true; 1024 1025 return false; 1026 } 1027 1028 static __always_inline unsigned long 1029 va_size(struct vmap_area *va) 1030 { 1031 return (va->va_end - va->va_start); 1032 } 1033 1034 static __always_inline unsigned long 1035 get_subtree_max_size(struct rb_node *node) 1036 { 1037 struct vmap_area *va; 1038 1039 va = rb_entry_safe(node, struct vmap_area, rb_node); 1040 return va ? va->subtree_max_size : 0; 1041 } 1042 1043 RB_DECLARE_CALLBACKS_MAX(static, free_vmap_area_rb_augment_cb, 1044 struct vmap_area, rb_node, unsigned long, subtree_max_size, va_size) 1045 1046 static void reclaim_and_purge_vmap_areas(void); 1047 static BLOCKING_NOTIFIER_HEAD(vmap_notify_list); 1048 static void drain_vmap_area_work(struct work_struct *work); 1049 static DECLARE_WORK(drain_vmap_work, drain_vmap_area_work); 1050 1051 static __cacheline_aligned_in_smp atomic_long_t nr_vmalloc_pages; 1052 static __cacheline_aligned_in_smp atomic_long_t vmap_lazy_nr; 1053 1054 unsigned long vmalloc_nr_pages(void) 1055 { 1056 return atomic_long_read(&nr_vmalloc_pages); 1057 } 1058 1059 static struct vmap_area *__find_vmap_area(unsigned long addr, struct rb_root *root) 1060 { 1061 struct rb_node *n = root->rb_node; 1062 1063 addr = (unsigned long)kasan_reset_tag((void *)addr); 1064 1065 while (n) { 1066 struct vmap_area *va; 1067 1068 va = rb_entry(n, struct vmap_area, rb_node); 1069 if (addr < va->va_start) 1070 n = n->rb_left; 1071 else if (addr >= va->va_end) 1072 n = n->rb_right; 1073 else 1074 return va; 1075 } 1076 1077 return NULL; 1078 } 1079 1080 /* Look up the first VA which satisfies addr < va_end, NULL if none. */ 1081 static struct vmap_area * 1082 __find_vmap_area_exceed_addr(unsigned long addr, struct rb_root *root) 1083 { 1084 struct vmap_area *va = NULL; 1085 struct rb_node *n = root->rb_node; 1086 1087 addr = (unsigned long)kasan_reset_tag((void *)addr); 1088 1089 while (n) { 1090 struct vmap_area *tmp; 1091 1092 tmp = rb_entry(n, struct vmap_area, rb_node); 1093 if (tmp->va_end > addr) { 1094 va = tmp; 1095 if (tmp->va_start <= addr) 1096 break; 1097 1098 n = n->rb_left; 1099 } else 1100 n = n->rb_right; 1101 } 1102 1103 return va; 1104 } 1105 1106 /* 1107 * Returns a node where a first VA, that satisfies addr < va_end, resides. 1108 * If success, a node is locked. A user is responsible to unlock it when a 1109 * VA is no longer needed to be accessed. 1110 * 1111 * Returns NULL if nothing found. 1112 */ 1113 static struct vmap_node * 1114 find_vmap_area_exceed_addr_lock(unsigned long addr, struct vmap_area **va) 1115 { 1116 unsigned long va_start_lowest; 1117 struct vmap_node *vn; 1118 1119 repeat: 1120 va_start_lowest = 0; 1121 1122 for_each_vmap_node(vn) { 1123 spin_lock(&vn->busy.lock); 1124 *va = __find_vmap_area_exceed_addr(addr, &vn->busy.root); 1125 1126 if (*va) 1127 if (!va_start_lowest || (*va)->va_start < va_start_lowest) 1128 va_start_lowest = (*va)->va_start; 1129 spin_unlock(&vn->busy.lock); 1130 } 1131 1132 /* 1133 * Check if found VA exists, it might have gone away. In this case we 1134 * repeat the search because a VA has been removed concurrently and we 1135 * need to proceed to the next one, which is a rare case. 1136 */ 1137 if (va_start_lowest) { 1138 vn = addr_to_node(va_start_lowest); 1139 1140 spin_lock(&vn->busy.lock); 1141 *va = __find_vmap_area(va_start_lowest, &vn->busy.root); 1142 1143 if (*va) 1144 return vn; 1145 1146 spin_unlock(&vn->busy.lock); 1147 goto repeat; 1148 } 1149 1150 return NULL; 1151 } 1152 1153 /* 1154 * This function returns back addresses of parent node 1155 * and its left or right link for further processing. 1156 * 1157 * Otherwise NULL is returned. In that case all further 1158 * steps regarding inserting of conflicting overlap range 1159 * have to be declined and actually considered as a bug. 1160 */ 1161 static __always_inline struct rb_node ** 1162 find_va_links(struct vmap_area *va, 1163 struct rb_root *root, struct rb_node *from, 1164 struct rb_node **parent) 1165 { 1166 struct vmap_area *tmp_va; 1167 struct rb_node **link; 1168 1169 if (root) { 1170 link = &root->rb_node; 1171 if (unlikely(!*link)) { 1172 *parent = NULL; 1173 return link; 1174 } 1175 } else { 1176 link = &from; 1177 } 1178 1179 /* 1180 * Go to the bottom of the tree. When we hit the last point 1181 * we end up with parent rb_node and correct direction, i name 1182 * it link, where the new va->rb_node will be attached to. 1183 */ 1184 do { 1185 tmp_va = rb_entry(*link, struct vmap_area, rb_node); 1186 1187 /* 1188 * During the traversal we also do some sanity check. 1189 * Trigger the BUG() if there are sides(left/right) 1190 * or full overlaps. 1191 */ 1192 if (va->va_end <= tmp_va->va_start) 1193 link = &(*link)->rb_left; 1194 else if (va->va_start >= tmp_va->va_end) 1195 link = &(*link)->rb_right; 1196 else { 1197 WARN(1, "vmalloc bug: 0x%lx-0x%lx overlaps with 0x%lx-0x%lx\n", 1198 va->va_start, va->va_end, tmp_va->va_start, tmp_va->va_end); 1199 1200 return NULL; 1201 } 1202 } while (*link); 1203 1204 *parent = &tmp_va->rb_node; 1205 return link; 1206 } 1207 1208 static __always_inline struct list_head * 1209 get_va_next_sibling(struct rb_node *parent, struct rb_node **link) 1210 { 1211 struct list_head *list; 1212 1213 if (unlikely(!parent)) 1214 /* 1215 * The red-black tree where we try to find VA neighbors 1216 * before merging or inserting is empty, i.e. it means 1217 * there is no free vmap space. Normally it does not 1218 * happen but we handle this case anyway. 1219 */ 1220 return NULL; 1221 1222 list = &rb_entry(parent, struct vmap_area, rb_node)->list; 1223 return (&parent->rb_right == link ? list->next : list); 1224 } 1225 1226 static __always_inline void 1227 __link_va(struct vmap_area *va, struct rb_root *root, 1228 struct rb_node *parent, struct rb_node **link, 1229 struct list_head *head, bool augment) 1230 { 1231 /* 1232 * VA is still not in the list, but we can 1233 * identify its future previous list_head node. 1234 */ 1235 if (likely(parent)) { 1236 head = &rb_entry(parent, struct vmap_area, rb_node)->list; 1237 if (&parent->rb_right != link) 1238 head = head->prev; 1239 } 1240 1241 /* Insert to the rb-tree */ 1242 rb_link_node(&va->rb_node, parent, link); 1243 if (augment) { 1244 /* 1245 * Some explanation here. Just perform simple insertion 1246 * to the tree. We do not set va->subtree_max_size to 1247 * its current size before calling rb_insert_augmented(). 1248 * It is because we populate the tree from the bottom 1249 * to parent levels when the node _is_ in the tree. 1250 * 1251 * Therefore we set subtree_max_size to zero after insertion, 1252 * to let __augment_tree_propagate_from() puts everything to 1253 * the correct order later on. 1254 */ 1255 rb_insert_augmented(&va->rb_node, 1256 root, &free_vmap_area_rb_augment_cb); 1257 va->subtree_max_size = 0; 1258 } else { 1259 rb_insert_color(&va->rb_node, root); 1260 } 1261 1262 /* Address-sort this list */ 1263 list_add(&va->list, head); 1264 } 1265 1266 static __always_inline void 1267 link_va(struct vmap_area *va, struct rb_root *root, 1268 struct rb_node *parent, struct rb_node **link, 1269 struct list_head *head) 1270 { 1271 __link_va(va, root, parent, link, head, false); 1272 } 1273 1274 static __always_inline void 1275 link_va_augment(struct vmap_area *va, struct rb_root *root, 1276 struct rb_node *parent, struct rb_node **link, 1277 struct list_head *head) 1278 { 1279 __link_va(va, root, parent, link, head, true); 1280 } 1281 1282 static __always_inline void 1283 __unlink_va(struct vmap_area *va, struct rb_root *root, bool augment) 1284 { 1285 if (WARN_ON(RB_EMPTY_NODE(&va->rb_node))) 1286 return; 1287 1288 if (augment) 1289 rb_erase_augmented(&va->rb_node, 1290 root, &free_vmap_area_rb_augment_cb); 1291 else 1292 rb_erase(&va->rb_node, root); 1293 1294 list_del_init(&va->list); 1295 RB_CLEAR_NODE(&va->rb_node); 1296 } 1297 1298 static __always_inline void 1299 unlink_va(struct vmap_area *va, struct rb_root *root) 1300 { 1301 __unlink_va(va, root, false); 1302 } 1303 1304 static __always_inline void 1305 unlink_va_augment(struct vmap_area *va, struct rb_root *root) 1306 { 1307 __unlink_va(va, root, true); 1308 } 1309 1310 #if DEBUG_AUGMENT_PROPAGATE_CHECK 1311 /* 1312 * Gets called when remove the node and rotate. 1313 */ 1314 static __always_inline unsigned long 1315 compute_subtree_max_size(struct vmap_area *va) 1316 { 1317 return max3(va_size(va), 1318 get_subtree_max_size(va->rb_node.rb_left), 1319 get_subtree_max_size(va->rb_node.rb_right)); 1320 } 1321 1322 static void 1323 augment_tree_propagate_check(void) 1324 { 1325 struct vmap_area *va; 1326 unsigned long computed_size; 1327 1328 list_for_each_entry(va, &free_vmap_area_list, list) { 1329 computed_size = compute_subtree_max_size(va); 1330 if (computed_size != va->subtree_max_size) 1331 pr_emerg("tree is corrupted: %lu, %lu\n", 1332 va_size(va), va->subtree_max_size); 1333 } 1334 } 1335 #endif 1336 1337 /* 1338 * This function populates subtree_max_size from bottom to upper 1339 * levels starting from VA point. The propagation must be done 1340 * when VA size is modified by changing its va_start/va_end. Or 1341 * in case of newly inserting of VA to the tree. 1342 * 1343 * It means that __augment_tree_propagate_from() must be called: 1344 * - After VA has been inserted to the tree(free path); 1345 * - After VA has been shrunk(allocation path); 1346 * - After VA has been increased(merging path). 1347 * 1348 * Please note that, it does not mean that upper parent nodes 1349 * and their subtree_max_size are recalculated all the time up 1350 * to the root node. 1351 * 1352 * 4--8 1353 * /\ 1354 * / \ 1355 * / \ 1356 * 2--2 8--8 1357 * 1358 * For example if we modify the node 4, shrinking it to 2, then 1359 * no any modification is required. If we shrink the node 2 to 1 1360 * its subtree_max_size is updated only, and set to 1. If we shrink 1361 * the node 8 to 6, then its subtree_max_size is set to 6 and parent 1362 * node becomes 4--6. 1363 */ 1364 static __always_inline void 1365 augment_tree_propagate_from(struct vmap_area *va) 1366 { 1367 /* 1368 * Populate the tree from bottom towards the root until 1369 * the calculated maximum available size of checked node 1370 * is equal to its current one. 1371 */ 1372 free_vmap_area_rb_augment_cb_propagate(&va->rb_node, NULL); 1373 1374 #if DEBUG_AUGMENT_PROPAGATE_CHECK 1375 augment_tree_propagate_check(); 1376 #endif 1377 } 1378 1379 static void 1380 insert_vmap_area(struct vmap_area *va, 1381 struct rb_root *root, struct list_head *head) 1382 { 1383 struct rb_node **link; 1384 struct rb_node *parent; 1385 1386 link = find_va_links(va, root, NULL, &parent); 1387 if (link) 1388 link_va(va, root, parent, link, head); 1389 } 1390 1391 static void 1392 insert_vmap_area_augment(struct vmap_area *va, 1393 struct rb_node *from, struct rb_root *root, 1394 struct list_head *head) 1395 { 1396 struct rb_node **link; 1397 struct rb_node *parent; 1398 1399 if (from) 1400 link = find_va_links(va, NULL, from, &parent); 1401 else 1402 link = find_va_links(va, root, NULL, &parent); 1403 1404 if (link) { 1405 link_va_augment(va, root, parent, link, head); 1406 augment_tree_propagate_from(va); 1407 } 1408 } 1409 1410 /* 1411 * Merge de-allocated chunk of VA memory with previous 1412 * and next free blocks. If coalesce is not done a new 1413 * free area is inserted. If VA has been merged, it is 1414 * freed. 1415 * 1416 * Please note, it can return NULL in case of overlap 1417 * ranges, followed by WARN() report. Despite it is a 1418 * buggy behaviour, a system can be alive and keep 1419 * ongoing. 1420 */ 1421 static __always_inline struct vmap_area * 1422 __merge_or_add_vmap_area(struct vmap_area *va, 1423 struct rb_root *root, struct list_head *head, bool augment) 1424 { 1425 struct vmap_area *sibling; 1426 struct list_head *next; 1427 struct rb_node **link; 1428 struct rb_node *parent; 1429 bool merged = false; 1430 1431 /* 1432 * Find a place in the tree where VA potentially will be 1433 * inserted, unless it is merged with its sibling/siblings. 1434 */ 1435 link = find_va_links(va, root, NULL, &parent); 1436 if (!link) 1437 return NULL; 1438 1439 /* 1440 * Get next node of VA to check if merging can be done. 1441 */ 1442 next = get_va_next_sibling(parent, link); 1443 if (unlikely(next == NULL)) 1444 goto insert; 1445 1446 /* 1447 * start end 1448 * | | 1449 * |<------VA------>|<-----Next----->| 1450 * | | 1451 * start end 1452 */ 1453 if (next != head) { 1454 sibling = list_entry(next, struct vmap_area, list); 1455 if (sibling->va_start == va->va_end) { 1456 sibling->va_start = va->va_start; 1457 1458 /* Free vmap_area object. */ 1459 kmem_cache_free(vmap_area_cachep, va); 1460 1461 /* Point to the new merged area. */ 1462 va = sibling; 1463 merged = true; 1464 } 1465 } 1466 1467 /* 1468 * start end 1469 * | | 1470 * |<-----Prev----->|<------VA------>| 1471 * | | 1472 * start end 1473 */ 1474 if (next->prev != head) { 1475 sibling = list_entry(next->prev, struct vmap_area, list); 1476 if (sibling->va_end == va->va_start) { 1477 /* 1478 * If both neighbors are coalesced, it is important 1479 * to unlink the "next" node first, followed by merging 1480 * with "previous" one. Otherwise the tree might not be 1481 * fully populated if a sibling's augmented value is 1482 * "normalized" because of rotation operations. 1483 */ 1484 if (merged) 1485 __unlink_va(va, root, augment); 1486 1487 sibling->va_end = va->va_end; 1488 1489 /* Free vmap_area object. */ 1490 kmem_cache_free(vmap_area_cachep, va); 1491 1492 /* Point to the new merged area. */ 1493 va = sibling; 1494 merged = true; 1495 } 1496 } 1497 1498 insert: 1499 if (!merged) 1500 __link_va(va, root, parent, link, head, augment); 1501 1502 return va; 1503 } 1504 1505 static __always_inline struct vmap_area * 1506 merge_or_add_vmap_area(struct vmap_area *va, 1507 struct rb_root *root, struct list_head *head) 1508 { 1509 return __merge_or_add_vmap_area(va, root, head, false); 1510 } 1511 1512 static __always_inline struct vmap_area * 1513 merge_or_add_vmap_area_augment(struct vmap_area *va, 1514 struct rb_root *root, struct list_head *head) 1515 { 1516 va = __merge_or_add_vmap_area(va, root, head, true); 1517 if (va) 1518 augment_tree_propagate_from(va); 1519 1520 return va; 1521 } 1522 1523 static __always_inline bool 1524 is_within_this_va(struct vmap_area *va, unsigned long size, 1525 unsigned long align, unsigned long vstart) 1526 { 1527 unsigned long nva_start_addr; 1528 1529 if (va->va_start > vstart) 1530 nva_start_addr = ALIGN(va->va_start, align); 1531 else 1532 nva_start_addr = ALIGN(vstart, align); 1533 1534 /* Can be overflowed due to big size or alignment. */ 1535 if (nva_start_addr + size < nva_start_addr || 1536 nva_start_addr < vstart) 1537 return false; 1538 1539 return (nva_start_addr + size <= va->va_end); 1540 } 1541 1542 /* 1543 * Find the first free block(lowest start address) in the tree, 1544 * that will accomplish the request corresponding to passing 1545 * parameters. Please note, with an alignment bigger than PAGE_SIZE, 1546 * a search length is adjusted to account for worst case alignment 1547 * overhead. 1548 */ 1549 static __always_inline struct vmap_area * 1550 find_vmap_lowest_match(struct rb_root *root, unsigned long size, 1551 unsigned long align, unsigned long vstart, bool adjust_search_size) 1552 { 1553 struct vmap_area *va; 1554 struct rb_node *node; 1555 unsigned long length; 1556 1557 /* Start from the root. */ 1558 node = root->rb_node; 1559 1560 /* Adjust the search size for alignment overhead. */ 1561 length = adjust_search_size ? size + align - 1 : size; 1562 1563 while (node) { 1564 va = rb_entry(node, struct vmap_area, rb_node); 1565 1566 if (get_subtree_max_size(node->rb_left) >= length && 1567 vstart < va->va_start) { 1568 node = node->rb_left; 1569 } else { 1570 if (is_within_this_va(va, size, align, vstart)) 1571 return va; 1572 1573 /* 1574 * Does not make sense to go deeper towards the right 1575 * sub-tree if it does not have a free block that is 1576 * equal or bigger to the requested search length. 1577 */ 1578 if (get_subtree_max_size(node->rb_right) >= length) { 1579 node = node->rb_right; 1580 continue; 1581 } 1582 1583 /* 1584 * OK. We roll back and find the first right sub-tree, 1585 * that will satisfy the search criteria. It can happen 1586 * due to "vstart" restriction or an alignment overhead 1587 * that is bigger then PAGE_SIZE. 1588 */ 1589 while ((node = rb_parent(node))) { 1590 va = rb_entry(node, struct vmap_area, rb_node); 1591 if (is_within_this_va(va, size, align, vstart)) 1592 return va; 1593 1594 if (get_subtree_max_size(node->rb_right) >= length && 1595 vstart <= va->va_start) { 1596 /* 1597 * Shift the vstart forward. Please note, we update it with 1598 * parent's start address adding "1" because we do not want 1599 * to enter same sub-tree after it has already been checked 1600 * and no suitable free block found there. 1601 */ 1602 vstart = va->va_start + 1; 1603 node = node->rb_right; 1604 break; 1605 } 1606 } 1607 } 1608 } 1609 1610 return NULL; 1611 } 1612 1613 #if DEBUG_AUGMENT_LOWEST_MATCH_CHECK 1614 #include <linux/random.h> 1615 1616 static struct vmap_area * 1617 find_vmap_lowest_linear_match(struct list_head *head, unsigned long size, 1618 unsigned long align, unsigned long vstart) 1619 { 1620 struct vmap_area *va; 1621 1622 list_for_each_entry(va, head, list) { 1623 if (!is_within_this_va(va, size, align, vstart)) 1624 continue; 1625 1626 return va; 1627 } 1628 1629 return NULL; 1630 } 1631 1632 static void 1633 find_vmap_lowest_match_check(struct rb_root *root, struct list_head *head, 1634 unsigned long size, unsigned long align) 1635 { 1636 struct vmap_area *va_1, *va_2; 1637 unsigned long vstart; 1638 unsigned int rnd; 1639 1640 get_random_bytes(&rnd, sizeof(rnd)); 1641 vstart = VMALLOC_START + rnd; 1642 1643 va_1 = find_vmap_lowest_match(root, size, align, vstart, false); 1644 va_2 = find_vmap_lowest_linear_match(head, size, align, vstart); 1645 1646 if (va_1 != va_2) 1647 pr_emerg("not lowest: t: 0x%p, l: 0x%p, v: 0x%lx\n", 1648 va_1, va_2, vstart); 1649 } 1650 #endif 1651 1652 enum fit_type { 1653 NOTHING_FIT = 0, 1654 FL_FIT_TYPE = 1, /* full fit */ 1655 LE_FIT_TYPE = 2, /* left edge fit */ 1656 RE_FIT_TYPE = 3, /* right edge fit */ 1657 NE_FIT_TYPE = 4 /* no edge fit */ 1658 }; 1659 1660 static __always_inline enum fit_type 1661 classify_va_fit_type(struct vmap_area *va, 1662 unsigned long nva_start_addr, unsigned long size) 1663 { 1664 enum fit_type type; 1665 1666 /* Check if it is within VA. */ 1667 if (nva_start_addr < va->va_start || 1668 nva_start_addr + size > va->va_end) 1669 return NOTHING_FIT; 1670 1671 /* Now classify. */ 1672 if (va->va_start == nva_start_addr) { 1673 if (va->va_end == nva_start_addr + size) 1674 type = FL_FIT_TYPE; 1675 else 1676 type = LE_FIT_TYPE; 1677 } else if (va->va_end == nva_start_addr + size) { 1678 type = RE_FIT_TYPE; 1679 } else { 1680 type = NE_FIT_TYPE; 1681 } 1682 1683 return type; 1684 } 1685 1686 static __always_inline int 1687 va_clip(struct rb_root *root, struct list_head *head, 1688 struct vmap_area *va, unsigned long nva_start_addr, 1689 unsigned long size) 1690 { 1691 struct vmap_area *lva = NULL; 1692 enum fit_type type = classify_va_fit_type(va, nva_start_addr, size); 1693 1694 if (type == FL_FIT_TYPE) { 1695 /* 1696 * No need to split VA, it fully fits. 1697 * 1698 * | | 1699 * V NVA V 1700 * |---------------| 1701 */ 1702 unlink_va_augment(va, root); 1703 kmem_cache_free(vmap_area_cachep, va); 1704 } else if (type == LE_FIT_TYPE) { 1705 /* 1706 * Split left edge of fit VA. 1707 * 1708 * | | 1709 * V NVA V R 1710 * |-------|-------| 1711 */ 1712 va->va_start += size; 1713 } else if (type == RE_FIT_TYPE) { 1714 /* 1715 * Split right edge of fit VA. 1716 * 1717 * | | 1718 * L V NVA V 1719 * |-------|-------| 1720 */ 1721 va->va_end = nva_start_addr; 1722 } else if (type == NE_FIT_TYPE) { 1723 /* 1724 * Split no edge of fit VA. 1725 * 1726 * | | 1727 * L V NVA V R 1728 * |---|-------|---| 1729 */ 1730 lva = __this_cpu_xchg(ne_fit_preload_node, NULL); 1731 if (unlikely(!lva)) { 1732 /* 1733 * For percpu allocator we do not do any pre-allocation 1734 * and leave it as it is. The reason is it most likely 1735 * never ends up with NE_FIT_TYPE splitting. In case of 1736 * percpu allocations offsets and sizes are aligned to 1737 * fixed align request, i.e. RE_FIT_TYPE and FL_FIT_TYPE 1738 * are its main fitting cases. 1739 * 1740 * There are a few exceptions though, as an example it is 1741 * a first allocation (early boot up) when we have "one" 1742 * big free space that has to be split. 1743 * 1744 * Also we can hit this path in case of regular "vmap" 1745 * allocations, if "this" current CPU was not preloaded. 1746 * See the comment in alloc_vmap_area() why. If so, then 1747 * GFP_NOWAIT is used instead to get an extra object for 1748 * split purpose. That is rare and most time does not 1749 * occur. 1750 * 1751 * What happens if an allocation gets failed. Basically, 1752 * an "overflow" path is triggered to purge lazily freed 1753 * areas to free some memory, then, the "retry" path is 1754 * triggered to repeat one more time. See more details 1755 * in alloc_vmap_area() function. 1756 */ 1757 lva = kmem_cache_alloc(vmap_area_cachep, GFP_NOWAIT); 1758 if (!lva) 1759 return -ENOMEM; 1760 } 1761 1762 /* 1763 * Build the remainder. 1764 */ 1765 lva->va_start = va->va_start; 1766 lva->va_end = nva_start_addr; 1767 1768 /* 1769 * Shrink this VA to remaining size. 1770 */ 1771 va->va_start = nva_start_addr + size; 1772 } else { 1773 return -EINVAL; 1774 } 1775 1776 if (type != FL_FIT_TYPE) { 1777 augment_tree_propagate_from(va); 1778 1779 if (lva) /* type == NE_FIT_TYPE */ 1780 insert_vmap_area_augment(lva, &va->rb_node, root, head); 1781 } 1782 1783 return 0; 1784 } 1785 1786 static unsigned long 1787 va_alloc(struct vmap_area *va, 1788 struct rb_root *root, struct list_head *head, 1789 unsigned long size, unsigned long align, 1790 unsigned long vstart, unsigned long vend) 1791 { 1792 unsigned long nva_start_addr; 1793 int ret; 1794 1795 if (va->va_start > vstart) 1796 nva_start_addr = ALIGN(va->va_start, align); 1797 else 1798 nva_start_addr = ALIGN(vstart, align); 1799 1800 /* Check the "vend" restriction. */ 1801 if (nva_start_addr + size > vend) 1802 return -ERANGE; 1803 1804 /* Update the free vmap_area. */ 1805 ret = va_clip(root, head, va, nva_start_addr, size); 1806 if (WARN_ON_ONCE(ret)) 1807 return ret; 1808 1809 return nva_start_addr; 1810 } 1811 1812 /* 1813 * Returns a start address of the newly allocated area, if success. 1814 * Otherwise an error value is returned that indicates failure. 1815 */ 1816 static __always_inline unsigned long 1817 __alloc_vmap_area(struct rb_root *root, struct list_head *head, 1818 unsigned long size, unsigned long align, 1819 unsigned long vstart, unsigned long vend) 1820 { 1821 bool adjust_search_size = true; 1822 unsigned long nva_start_addr; 1823 struct vmap_area *va; 1824 1825 /* 1826 * Do not adjust when: 1827 * a) align <= PAGE_SIZE, because it does not make any sense. 1828 * All blocks(their start addresses) are at least PAGE_SIZE 1829 * aligned anyway; 1830 * b) a short range where a requested size corresponds to exactly 1831 * specified [vstart:vend] interval and an alignment > PAGE_SIZE. 1832 * With adjusted search length an allocation would not succeed. 1833 */ 1834 if (align <= PAGE_SIZE || (align > PAGE_SIZE && (vend - vstart) == size)) 1835 adjust_search_size = false; 1836 1837 va = find_vmap_lowest_match(root, size, align, vstart, adjust_search_size); 1838 if (unlikely(!va)) 1839 return -ENOENT; 1840 1841 nva_start_addr = va_alloc(va, root, head, size, align, vstart, vend); 1842 1843 #if DEBUG_AUGMENT_LOWEST_MATCH_CHECK 1844 if (!IS_ERR_VALUE(nva_start_addr)) 1845 find_vmap_lowest_match_check(root, head, size, align); 1846 #endif 1847 1848 return nva_start_addr; 1849 } 1850 1851 /* 1852 * Free a region of KVA allocated by alloc_vmap_area 1853 */ 1854 static void free_vmap_area(struct vmap_area *va) 1855 { 1856 struct vmap_node *vn = addr_to_node(va->va_start); 1857 1858 /* 1859 * Remove from the busy tree/list. 1860 */ 1861 spin_lock(&vn->busy.lock); 1862 unlink_va(va, &vn->busy.root); 1863 spin_unlock(&vn->busy.lock); 1864 1865 /* 1866 * Insert/Merge it back to the free tree/list. 1867 */ 1868 spin_lock(&free_vmap_area_lock); 1869 merge_or_add_vmap_area_augment(va, &free_vmap_area_root, &free_vmap_area_list); 1870 spin_unlock(&free_vmap_area_lock); 1871 } 1872 1873 static inline void 1874 preload_this_cpu_lock(spinlock_t *lock, gfp_t gfp_mask, int node) 1875 { 1876 struct vmap_area *va = NULL, *tmp; 1877 1878 /* 1879 * Preload this CPU with one extra vmap_area object. It is used 1880 * when fit type of free area is NE_FIT_TYPE. It guarantees that 1881 * a CPU that does an allocation is preloaded. 1882 * 1883 * We do it in non-atomic context, thus it allows us to use more 1884 * permissive allocation masks to be more stable under low memory 1885 * condition and high memory pressure. 1886 */ 1887 if (!this_cpu_read(ne_fit_preload_node)) 1888 va = kmem_cache_alloc_node(vmap_area_cachep, gfp_mask, node); 1889 1890 spin_lock(lock); 1891 1892 tmp = NULL; 1893 if (va && !__this_cpu_try_cmpxchg(ne_fit_preload_node, &tmp, va)) 1894 kmem_cache_free(vmap_area_cachep, va); 1895 } 1896 1897 static struct vmap_pool * 1898 size_to_va_pool(struct vmap_node *vn, unsigned long size) 1899 { 1900 unsigned int idx = (size - 1) / PAGE_SIZE; 1901 1902 if (idx < MAX_VA_SIZE_PAGES) 1903 return &vn->pool[idx]; 1904 1905 return NULL; 1906 } 1907 1908 static bool 1909 node_pool_add_va(struct vmap_node *n, struct vmap_area *va) 1910 { 1911 struct vmap_pool *vp; 1912 1913 vp = size_to_va_pool(n, va_size(va)); 1914 if (!vp) 1915 return false; 1916 1917 spin_lock(&n->pool_lock); 1918 list_add(&va->list, &vp->head); 1919 WRITE_ONCE(vp->len, vp->len + 1); 1920 spin_unlock(&n->pool_lock); 1921 1922 return true; 1923 } 1924 1925 static struct vmap_area * 1926 node_pool_del_va(struct vmap_node *vn, unsigned long size, 1927 unsigned long align, unsigned long vstart, 1928 unsigned long vend) 1929 { 1930 struct vmap_area *va = NULL; 1931 struct vmap_pool *vp; 1932 int err = 0; 1933 1934 vp = size_to_va_pool(vn, size); 1935 if (!vp || list_empty(&vp->head)) 1936 return NULL; 1937 1938 spin_lock(&vn->pool_lock); 1939 if (!list_empty(&vp->head)) { 1940 va = list_first_entry(&vp->head, struct vmap_area, list); 1941 1942 if (IS_ALIGNED(va->va_start, align)) { 1943 /* 1944 * Do some sanity check and emit a warning 1945 * if one of below checks detects an error. 1946 */ 1947 err |= (va_size(va) != size); 1948 err |= (va->va_start < vstart); 1949 err |= (va->va_end > vend); 1950 1951 if (!WARN_ON_ONCE(err)) { 1952 list_del_init(&va->list); 1953 WRITE_ONCE(vp->len, vp->len - 1); 1954 } else { 1955 va = NULL; 1956 } 1957 } else { 1958 list_move_tail(&va->list, &vp->head); 1959 va = NULL; 1960 } 1961 } 1962 spin_unlock(&vn->pool_lock); 1963 1964 return va; 1965 } 1966 1967 static struct vmap_area * 1968 node_alloc(unsigned long size, unsigned long align, 1969 unsigned long vstart, unsigned long vend, 1970 unsigned long *addr, unsigned int *vn_id) 1971 { 1972 struct vmap_area *va; 1973 1974 *vn_id = 0; 1975 *addr = -EINVAL; 1976 1977 /* 1978 * Fallback to a global heap if not vmalloc or there 1979 * is only one node. 1980 */ 1981 if (vstart != VMALLOC_START || vend != VMALLOC_END || 1982 nr_vmap_nodes == 1) 1983 return NULL; 1984 1985 *vn_id = raw_smp_processor_id() % nr_vmap_nodes; 1986 va = node_pool_del_va(id_to_node(*vn_id), size, align, vstart, vend); 1987 *vn_id = encode_vn_id(*vn_id); 1988 1989 if (va) 1990 *addr = va->va_start; 1991 1992 return va; 1993 } 1994 1995 static inline void setup_vmalloc_vm(struct vm_struct *vm, 1996 struct vmap_area *va, unsigned long flags, const void *caller) 1997 { 1998 vm->flags = flags; 1999 vm->addr = (void *)va->va_start; 2000 vm->size = vm->requested_size = va_size(va); 2001 vm->caller = caller; 2002 va->vm = vm; 2003 } 2004 2005 /* 2006 * Allocate a region of KVA of the specified size and alignment, within the 2007 * vstart and vend. If vm is passed in, the two will also be bound. 2008 */ 2009 static struct vmap_area *alloc_vmap_area(unsigned long size, 2010 unsigned long align, 2011 unsigned long vstart, unsigned long vend, 2012 int node, gfp_t gfp_mask, 2013 unsigned long va_flags, struct vm_struct *vm) 2014 { 2015 struct vmap_node *vn; 2016 struct vmap_area *va; 2017 unsigned long freed; 2018 unsigned long addr; 2019 unsigned int vn_id; 2020 int purged = 0; 2021 int ret; 2022 2023 if (unlikely(!size || offset_in_page(size) || !is_power_of_2(align))) 2024 return ERR_PTR(-EINVAL); 2025 2026 if (unlikely(!vmap_initialized)) 2027 return ERR_PTR(-EBUSY); 2028 2029 /* Only reclaim behaviour flags are relevant. */ 2030 gfp_mask = gfp_mask & GFP_RECLAIM_MASK; 2031 might_sleep(); 2032 2033 /* 2034 * If a VA is obtained from a global heap(if it fails here) 2035 * it is anyway marked with this "vn_id" so it is returned 2036 * to this pool's node later. Such way gives a possibility 2037 * to populate pools based on users demand. 2038 * 2039 * On success a ready to go VA is returned. 2040 */ 2041 va = node_alloc(size, align, vstart, vend, &addr, &vn_id); 2042 if (!va) { 2043 va = kmem_cache_alloc_node(vmap_area_cachep, gfp_mask, node); 2044 if (unlikely(!va)) 2045 return ERR_PTR(-ENOMEM); 2046 2047 /* 2048 * Only scan the relevant parts containing pointers to other objects 2049 * to avoid false negatives. 2050 */ 2051 kmemleak_scan_area(&va->rb_node, SIZE_MAX, gfp_mask); 2052 } 2053 2054 retry: 2055 if (IS_ERR_VALUE(addr)) { 2056 preload_this_cpu_lock(&free_vmap_area_lock, gfp_mask, node); 2057 addr = __alloc_vmap_area(&free_vmap_area_root, &free_vmap_area_list, 2058 size, align, vstart, vend); 2059 spin_unlock(&free_vmap_area_lock); 2060 2061 /* 2062 * This is not a fast path. Check if yielding is needed. This 2063 * is the only reschedule point in the vmalloc() path. 2064 */ 2065 cond_resched(); 2066 } 2067 2068 trace_alloc_vmap_area(addr, size, align, vstart, vend, IS_ERR_VALUE(addr)); 2069 2070 /* 2071 * If an allocation fails, the error value is 2072 * returned. Therefore trigger the overflow path. 2073 */ 2074 if (IS_ERR_VALUE(addr)) 2075 goto overflow; 2076 2077 va->va_start = addr; 2078 va->va_end = addr + size; 2079 va->vm = NULL; 2080 va->flags = (va_flags | vn_id); 2081 2082 if (vm) { 2083 vm->addr = (void *)va->va_start; 2084 vm->size = va_size(va); 2085 va->vm = vm; 2086 } 2087 2088 vn = addr_to_node(va->va_start); 2089 2090 spin_lock(&vn->busy.lock); 2091 insert_vmap_area(va, &vn->busy.root, &vn->busy.head); 2092 spin_unlock(&vn->busy.lock); 2093 2094 BUG_ON(!IS_ALIGNED(va->va_start, align)); 2095 BUG_ON(va->va_start < vstart); 2096 BUG_ON(va->va_end > vend); 2097 2098 ret = kasan_populate_vmalloc(addr, size, gfp_mask); 2099 if (ret) { 2100 free_vmap_area(va); 2101 return ERR_PTR(ret); 2102 } 2103 2104 return va; 2105 2106 overflow: 2107 if (!purged) { 2108 reclaim_and_purge_vmap_areas(); 2109 purged = 1; 2110 goto retry; 2111 } 2112 2113 freed = 0; 2114 blocking_notifier_call_chain(&vmap_notify_list, 0, &freed); 2115 2116 if (freed > 0) { 2117 purged = 0; 2118 goto retry; 2119 } 2120 2121 if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) 2122 pr_warn("vmalloc_node_range for size %lu failed: Address range restricted to %#lx - %#lx\n", 2123 size, vstart, vend); 2124 2125 kmem_cache_free(vmap_area_cachep, va); 2126 return ERR_PTR(-EBUSY); 2127 } 2128 2129 int register_vmap_purge_notifier(struct notifier_block *nb) 2130 { 2131 return blocking_notifier_chain_register(&vmap_notify_list, nb); 2132 } 2133 EXPORT_SYMBOL_GPL(register_vmap_purge_notifier); 2134 2135 int unregister_vmap_purge_notifier(struct notifier_block *nb) 2136 { 2137 return blocking_notifier_chain_unregister(&vmap_notify_list, nb); 2138 } 2139 EXPORT_SYMBOL_GPL(unregister_vmap_purge_notifier); 2140 2141 /* 2142 * lazy_max_pages is the maximum amount of virtual address space we gather up 2143 * before attempting to purge with a TLB flush. 2144 * 2145 * There is a tradeoff here: a larger number will cover more kernel page tables 2146 * and take slightly longer to purge, but it will linearly reduce the number of 2147 * global TLB flushes that must be performed. It would seem natural to scale 2148 * this number up linearly with the number of CPUs (because vmapping activity 2149 * could also scale linearly with the number of CPUs), however it is likely 2150 * that in practice, workloads might be constrained in other ways that mean 2151 * vmap activity will not scale linearly with CPUs. Also, I want to be 2152 * conservative and not introduce a big latency on huge systems, so go with 2153 * a less aggressive log scale. It will still be an improvement over the old 2154 * code, and it will be simple to change the scale factor if we find that it 2155 * becomes a problem on bigger systems. 2156 */ 2157 static unsigned long lazy_max_pages(void) 2158 { 2159 unsigned int log; 2160 2161 log = fls(num_online_cpus()); 2162 2163 return log * (32UL * 1024 * 1024 / PAGE_SIZE); 2164 } 2165 2166 /* 2167 * Serialize vmap purging. There is no actual critical section protected 2168 * by this lock, but we want to avoid concurrent calls for performance 2169 * reasons and to make the pcpu_get_vm_areas more deterministic. 2170 */ 2171 static DEFINE_MUTEX(vmap_purge_lock); 2172 2173 /* for per-CPU blocks */ 2174 static void purge_fragmented_blocks_allcpus(void); 2175 2176 static void 2177 reclaim_list_global(struct list_head *head) 2178 { 2179 struct vmap_area *va, *n; 2180 2181 if (list_empty(head)) 2182 return; 2183 2184 spin_lock(&free_vmap_area_lock); 2185 list_for_each_entry_safe(va, n, head, list) 2186 merge_or_add_vmap_area_augment(va, 2187 &free_vmap_area_root, &free_vmap_area_list); 2188 spin_unlock(&free_vmap_area_lock); 2189 } 2190 2191 static void 2192 decay_va_pool_node(struct vmap_node *vn, bool full_decay) 2193 { 2194 LIST_HEAD(decay_list); 2195 struct rb_root decay_root = RB_ROOT; 2196 struct vmap_area *va, *nva; 2197 unsigned long n_decay, pool_len; 2198 int i; 2199 2200 for (i = 0; i < MAX_VA_SIZE_PAGES; i++) { 2201 LIST_HEAD(tmp_list); 2202 2203 if (list_empty(&vn->pool[i].head)) 2204 continue; 2205 2206 /* Detach the pool, so no-one can access it. */ 2207 spin_lock(&vn->pool_lock); 2208 list_replace_init(&vn->pool[i].head, &tmp_list); 2209 spin_unlock(&vn->pool_lock); 2210 2211 pool_len = n_decay = vn->pool[i].len; 2212 WRITE_ONCE(vn->pool[i].len, 0); 2213 2214 /* Decay a pool by ~25% out of left objects. */ 2215 if (!full_decay) 2216 n_decay >>= 2; 2217 pool_len -= n_decay; 2218 2219 list_for_each_entry_safe(va, nva, &tmp_list, list) { 2220 if (!n_decay--) 2221 break; 2222 2223 list_del_init(&va->list); 2224 merge_or_add_vmap_area(va, &decay_root, &decay_list); 2225 } 2226 2227 /* 2228 * Attach the pool back if it has been partly decayed. 2229 * Please note, it is supposed that nobody(other contexts) 2230 * can populate the pool therefore a simple list replace 2231 * operation takes place here. 2232 */ 2233 if (!list_empty(&tmp_list)) { 2234 spin_lock(&vn->pool_lock); 2235 list_replace_init(&tmp_list, &vn->pool[i].head); 2236 WRITE_ONCE(vn->pool[i].len, pool_len); 2237 spin_unlock(&vn->pool_lock); 2238 } 2239 } 2240 2241 reclaim_list_global(&decay_list); 2242 } 2243 2244 #define KASAN_RELEASE_BATCH_SIZE 32 2245 2246 static void 2247 kasan_release_vmalloc_node(struct vmap_node *vn) 2248 { 2249 struct vmap_area *va; 2250 unsigned long start, end; 2251 unsigned int batch_count = 0; 2252 2253 start = list_first_entry(&vn->purge_list, struct vmap_area, list)->va_start; 2254 end = list_last_entry(&vn->purge_list, struct vmap_area, list)->va_end; 2255 2256 list_for_each_entry(va, &vn->purge_list, list) { 2257 if (is_vmalloc_or_module_addr((void *) va->va_start)) 2258 kasan_release_vmalloc(va->va_start, va->va_end, 2259 va->va_start, va->va_end, 2260 KASAN_VMALLOC_PAGE_RANGE); 2261 2262 if (need_resched() || (++batch_count >= KASAN_RELEASE_BATCH_SIZE)) { 2263 cond_resched(); 2264 batch_count = 0; 2265 } 2266 } 2267 2268 kasan_release_vmalloc(start, end, start, end, KASAN_VMALLOC_TLB_FLUSH); 2269 } 2270 2271 static void purge_vmap_node(struct work_struct *work) 2272 { 2273 struct vmap_node *vn = container_of(work, 2274 struct vmap_node, purge_work); 2275 unsigned long nr_purged_pages = 0; 2276 struct vmap_area *va, *n_va; 2277 LIST_HEAD(local_list); 2278 2279 if (IS_ENABLED(CONFIG_KASAN_VMALLOC)) 2280 kasan_release_vmalloc_node(vn); 2281 2282 vn->nr_purged = 0; 2283 2284 list_for_each_entry_safe(va, n_va, &vn->purge_list, list) { 2285 unsigned long nr = va_size(va) >> PAGE_SHIFT; 2286 unsigned int vn_id = decode_vn_id(va->flags); 2287 2288 list_del_init(&va->list); 2289 2290 nr_purged_pages += nr; 2291 vn->nr_purged++; 2292 2293 if (is_vn_id_valid(vn_id) && !vn->skip_populate) 2294 if (node_pool_add_va(vn, va)) 2295 continue; 2296 2297 /* Go back to global. */ 2298 list_add(&va->list, &local_list); 2299 } 2300 2301 atomic_long_sub(nr_purged_pages, &vmap_lazy_nr); 2302 2303 reclaim_list_global(&local_list); 2304 } 2305 2306 /* 2307 * Purges all lazily-freed vmap areas. 2308 */ 2309 static bool __purge_vmap_area_lazy(unsigned long start, unsigned long end, 2310 bool full_pool_decay) 2311 { 2312 unsigned long nr_purged_areas = 0; 2313 unsigned int nr_purge_helpers; 2314 static cpumask_t purge_nodes; 2315 unsigned int nr_purge_nodes; 2316 struct vmap_node *vn; 2317 int i; 2318 2319 lockdep_assert_held(&vmap_purge_lock); 2320 2321 /* 2322 * Use cpumask to mark which node has to be processed. 2323 */ 2324 purge_nodes = CPU_MASK_NONE; 2325 2326 for_each_vmap_node(vn) { 2327 INIT_LIST_HEAD(&vn->purge_list); 2328 vn->skip_populate = full_pool_decay; 2329 decay_va_pool_node(vn, full_pool_decay); 2330 2331 if (RB_EMPTY_ROOT(&vn->lazy.root)) 2332 continue; 2333 2334 spin_lock(&vn->lazy.lock); 2335 WRITE_ONCE(vn->lazy.root.rb_node, NULL); 2336 list_replace_init(&vn->lazy.head, &vn->purge_list); 2337 spin_unlock(&vn->lazy.lock); 2338 2339 start = min(start, list_first_entry(&vn->purge_list, 2340 struct vmap_area, list)->va_start); 2341 2342 end = max(end, list_last_entry(&vn->purge_list, 2343 struct vmap_area, list)->va_end); 2344 2345 cpumask_set_cpu(node_to_id(vn), &purge_nodes); 2346 } 2347 2348 nr_purge_nodes = cpumask_weight(&purge_nodes); 2349 if (nr_purge_nodes > 0) { 2350 flush_tlb_kernel_range(start, end); 2351 2352 /* One extra worker is per a lazy_max_pages() full set minus one. */ 2353 nr_purge_helpers = atomic_long_read(&vmap_lazy_nr) / lazy_max_pages(); 2354 nr_purge_helpers = clamp(nr_purge_helpers, 1U, nr_purge_nodes) - 1; 2355 2356 for_each_cpu(i, &purge_nodes) { 2357 vn = &vmap_nodes[i]; 2358 2359 if (nr_purge_helpers > 0) { 2360 INIT_WORK(&vn->purge_work, purge_vmap_node); 2361 2362 if (cpumask_test_cpu(i, cpu_online_mask)) 2363 schedule_work_on(i, &vn->purge_work); 2364 else 2365 schedule_work(&vn->purge_work); 2366 2367 nr_purge_helpers--; 2368 } else { 2369 vn->purge_work.func = NULL; 2370 purge_vmap_node(&vn->purge_work); 2371 nr_purged_areas += vn->nr_purged; 2372 } 2373 } 2374 2375 for_each_cpu(i, &purge_nodes) { 2376 vn = &vmap_nodes[i]; 2377 2378 if (vn->purge_work.func) { 2379 flush_work(&vn->purge_work); 2380 nr_purged_areas += vn->nr_purged; 2381 } 2382 } 2383 } 2384 2385 trace_purge_vmap_area_lazy(start, end, nr_purged_areas); 2386 return nr_purged_areas > 0; 2387 } 2388 2389 /* 2390 * Reclaim vmap areas by purging fragmented blocks and purge_vmap_area_list. 2391 */ 2392 static void reclaim_and_purge_vmap_areas(void) 2393 2394 { 2395 mutex_lock(&vmap_purge_lock); 2396 purge_fragmented_blocks_allcpus(); 2397 __purge_vmap_area_lazy(ULONG_MAX, 0, true); 2398 mutex_unlock(&vmap_purge_lock); 2399 } 2400 2401 static void drain_vmap_area_work(struct work_struct *work) 2402 { 2403 mutex_lock(&vmap_purge_lock); 2404 __purge_vmap_area_lazy(ULONG_MAX, 0, false); 2405 mutex_unlock(&vmap_purge_lock); 2406 } 2407 2408 /* 2409 * Free a vmap area, caller ensuring that the area has been unmapped, 2410 * unlinked and flush_cache_vunmap had been called for the correct 2411 * range previously. 2412 */ 2413 static void free_vmap_area_noflush(struct vmap_area *va) 2414 { 2415 unsigned long nr_lazy_max = lazy_max_pages(); 2416 unsigned long va_start = va->va_start; 2417 unsigned int vn_id = decode_vn_id(va->flags); 2418 struct vmap_node *vn; 2419 unsigned long nr_lazy; 2420 2421 if (WARN_ON_ONCE(!list_empty(&va->list))) 2422 return; 2423 2424 nr_lazy = atomic_long_add_return_relaxed(va_size(va) >> PAGE_SHIFT, 2425 &vmap_lazy_nr); 2426 2427 /* 2428 * If it was request by a certain node we would like to 2429 * return it to that node, i.e. its pool for later reuse. 2430 */ 2431 vn = is_vn_id_valid(vn_id) ? 2432 id_to_node(vn_id):addr_to_node(va->va_start); 2433 2434 spin_lock(&vn->lazy.lock); 2435 insert_vmap_area(va, &vn->lazy.root, &vn->lazy.head); 2436 spin_unlock(&vn->lazy.lock); 2437 2438 trace_free_vmap_area_noflush(va_start, nr_lazy, nr_lazy_max); 2439 2440 /* After this point, we may free va at any time */ 2441 if (unlikely(nr_lazy > nr_lazy_max)) 2442 schedule_work(&drain_vmap_work); 2443 } 2444 2445 /* 2446 * Free and unmap a vmap area 2447 */ 2448 static void free_unmap_vmap_area(struct vmap_area *va) 2449 { 2450 flush_cache_vunmap(va->va_start, va->va_end); 2451 vunmap_range_noflush(va->va_start, va->va_end); 2452 if (debug_pagealloc_enabled_static()) 2453 flush_tlb_kernel_range(va->va_start, va->va_end); 2454 2455 free_vmap_area_noflush(va); 2456 } 2457 2458 struct vmap_area *find_vmap_area(unsigned long addr) 2459 { 2460 struct vmap_node *vn; 2461 struct vmap_area *va; 2462 int i, j; 2463 2464 if (unlikely(!vmap_initialized)) 2465 return NULL; 2466 2467 /* 2468 * An addr_to_node_id(addr) converts an address to a node index 2469 * where a VA is located. If VA spans several zones and passed 2470 * addr is not the same as va->va_start, what is not common, we 2471 * may need to scan extra nodes. See an example: 2472 * 2473 * <----va----> 2474 * -|-----|-----|-----|-----|- 2475 * 1 2 0 1 2476 * 2477 * VA resides in node 1 whereas it spans 1, 2 an 0. If passed 2478 * addr is within 2 or 0 nodes we should do extra work. 2479 */ 2480 i = j = addr_to_node_id(addr); 2481 do { 2482 vn = &vmap_nodes[i]; 2483 2484 spin_lock(&vn->busy.lock); 2485 va = __find_vmap_area(addr, &vn->busy.root); 2486 spin_unlock(&vn->busy.lock); 2487 2488 if (va) 2489 return va; 2490 } while ((i = (i + nr_vmap_nodes - 1) % nr_vmap_nodes) != j); 2491 2492 return NULL; 2493 } 2494 2495 static struct vmap_area *find_unlink_vmap_area(unsigned long addr) 2496 { 2497 struct vmap_node *vn; 2498 struct vmap_area *va; 2499 int i, j; 2500 2501 /* 2502 * Check the comment in the find_vmap_area() about the loop. 2503 */ 2504 i = j = addr_to_node_id(addr); 2505 do { 2506 vn = &vmap_nodes[i]; 2507 2508 spin_lock(&vn->busy.lock); 2509 va = __find_vmap_area(addr, &vn->busy.root); 2510 if (va) 2511 unlink_va(va, &vn->busy.root); 2512 spin_unlock(&vn->busy.lock); 2513 2514 if (va) 2515 return va; 2516 } while ((i = (i + nr_vmap_nodes - 1) % nr_vmap_nodes) != j); 2517 2518 return NULL; 2519 } 2520 2521 /*** Per cpu kva allocator ***/ 2522 2523 /* 2524 * vmap space is limited especially on 32 bit architectures. Ensure there is 2525 * room for at least 16 percpu vmap blocks per CPU. 2526 */ 2527 /* 2528 * If we had a constant VMALLOC_START and VMALLOC_END, we'd like to be able 2529 * to #define VMALLOC_SPACE (VMALLOC_END-VMALLOC_START). Guess 2530 * instead (we just need a rough idea) 2531 */ 2532 #if BITS_PER_LONG == 32 2533 #define VMALLOC_SPACE (128UL*1024*1024) 2534 #else 2535 #define VMALLOC_SPACE (128UL*1024*1024*1024) 2536 #endif 2537 2538 #define VMALLOC_PAGES (VMALLOC_SPACE / PAGE_SIZE) 2539 #define VMAP_MAX_ALLOC BITS_PER_LONG /* 256K with 4K pages */ 2540 #define VMAP_BBMAP_BITS_MAX 1024 /* 4MB with 4K pages */ 2541 #define VMAP_BBMAP_BITS_MIN (VMAP_MAX_ALLOC*2) 2542 #define VMAP_MIN(x, y) ((x) < (y) ? (x) : (y)) /* can't use min() */ 2543 #define VMAP_MAX(x, y) ((x) > (y) ? (x) : (y)) /* can't use max() */ 2544 #define VMAP_BBMAP_BITS \ 2545 VMAP_MIN(VMAP_BBMAP_BITS_MAX, \ 2546 VMAP_MAX(VMAP_BBMAP_BITS_MIN, \ 2547 VMALLOC_PAGES / roundup_pow_of_two(NR_CPUS) / 16)) 2548 2549 #define VMAP_BLOCK_SIZE (VMAP_BBMAP_BITS * PAGE_SIZE) 2550 2551 /* 2552 * Purge threshold to prevent overeager purging of fragmented blocks for 2553 * regular operations: Purge if vb->free is less than 1/4 of the capacity. 2554 */ 2555 #define VMAP_PURGE_THRESHOLD (VMAP_BBMAP_BITS / 4) 2556 2557 #define VMAP_RAM 0x1 /* indicates vm_map_ram area*/ 2558 #define VMAP_BLOCK 0x2 /* mark out the vmap_block sub-type*/ 2559 #define VMAP_FLAGS_MASK 0x3 2560 2561 struct vmap_block_queue { 2562 spinlock_t lock; 2563 struct list_head free; 2564 2565 /* 2566 * An xarray requires an extra memory dynamically to 2567 * be allocated. If it is an issue, we can use rb-tree 2568 * instead. 2569 */ 2570 struct xarray vmap_blocks; 2571 }; 2572 2573 struct vmap_block { 2574 spinlock_t lock; 2575 struct vmap_area *va; 2576 unsigned long free, dirty; 2577 DECLARE_BITMAP(used_map, VMAP_BBMAP_BITS); 2578 unsigned long dirty_min, dirty_max; /*< dirty range */ 2579 struct list_head free_list; 2580 struct rcu_head rcu_head; 2581 struct list_head purge; 2582 unsigned int cpu; 2583 }; 2584 2585 /* Queue of free and dirty vmap blocks, for allocation and flushing purposes */ 2586 static DEFINE_PER_CPU(struct vmap_block_queue, vmap_block_queue); 2587 2588 /* 2589 * In order to fast access to any "vmap_block" associated with a 2590 * specific address, we use a hash. 2591 * 2592 * A per-cpu vmap_block_queue is used in both ways, to serialize 2593 * an access to free block chains among CPUs(alloc path) and it 2594 * also acts as a vmap_block hash(alloc/free paths). It means we 2595 * overload it, since we already have the per-cpu array which is 2596 * used as a hash table. When used as a hash a 'cpu' passed to 2597 * per_cpu() is not actually a CPU but rather a hash index. 2598 * 2599 * A hash function is addr_to_vb_xa() which hashes any address 2600 * to a specific index(in a hash) it belongs to. This then uses a 2601 * per_cpu() macro to access an array with generated index. 2602 * 2603 * An example: 2604 * 2605 * CPU_1 CPU_2 CPU_0 2606 * | | | 2607 * V V V 2608 * 0 10 20 30 40 50 60 2609 * |------|------|------|------|------|------|...<vmap address space> 2610 * CPU0 CPU1 CPU2 CPU0 CPU1 CPU2 2611 * 2612 * - CPU_1 invokes vm_unmap_ram(6), 6 belongs to CPU0 zone, thus 2613 * it access: CPU0/INDEX0 -> vmap_blocks -> xa_lock; 2614 * 2615 * - CPU_2 invokes vm_unmap_ram(11), 11 belongs to CPU1 zone, thus 2616 * it access: CPU1/INDEX1 -> vmap_blocks -> xa_lock; 2617 * 2618 * - CPU_0 invokes vm_unmap_ram(20), 20 belongs to CPU2 zone, thus 2619 * it access: CPU2/INDEX2 -> vmap_blocks -> xa_lock. 2620 * 2621 * This technique almost always avoids lock contention on insert/remove, 2622 * however xarray spinlocks protect against any contention that remains. 2623 */ 2624 static struct xarray * 2625 addr_to_vb_xa(unsigned long addr) 2626 { 2627 int index = (addr / VMAP_BLOCK_SIZE) % nr_cpu_ids; 2628 2629 /* 2630 * Please note, nr_cpu_ids points on a highest set 2631 * possible bit, i.e. we never invoke cpumask_next() 2632 * if an index points on it which is nr_cpu_ids - 1. 2633 */ 2634 if (!cpu_possible(index)) 2635 index = cpumask_next(index, cpu_possible_mask); 2636 2637 return &per_cpu(vmap_block_queue, index).vmap_blocks; 2638 } 2639 2640 /* 2641 * We should probably have a fallback mechanism to allocate virtual memory 2642 * out of partially filled vmap blocks. However vmap block sizing should be 2643 * fairly reasonable according to the vmalloc size, so it shouldn't be a 2644 * big problem. 2645 */ 2646 2647 static unsigned long addr_to_vb_idx(unsigned long addr) 2648 { 2649 addr -= VMALLOC_START & ~(VMAP_BLOCK_SIZE-1); 2650 addr /= VMAP_BLOCK_SIZE; 2651 return addr; 2652 } 2653 2654 static void *vmap_block_vaddr(unsigned long va_start, unsigned long pages_off) 2655 { 2656 unsigned long addr; 2657 2658 addr = va_start + (pages_off << PAGE_SHIFT); 2659 BUG_ON(addr_to_vb_idx(addr) != addr_to_vb_idx(va_start)); 2660 return (void *)addr; 2661 } 2662 2663 /** 2664 * new_vmap_block - allocates new vmap_block and occupies 2^order pages in this 2665 * block. Of course pages number can't exceed VMAP_BBMAP_BITS 2666 * @order: how many 2^order pages should be occupied in newly allocated block 2667 * @gfp_mask: flags for the page level allocator 2668 * 2669 * Return: virtual address in a newly allocated block or ERR_PTR(-errno) 2670 */ 2671 static void *new_vmap_block(unsigned int order, gfp_t gfp_mask) 2672 { 2673 struct vmap_block_queue *vbq; 2674 struct vmap_block *vb; 2675 struct vmap_area *va; 2676 struct xarray *xa; 2677 unsigned long vb_idx; 2678 int node, err; 2679 void *vaddr; 2680 2681 node = numa_node_id(); 2682 2683 vb = kmalloc_node(sizeof(struct vmap_block), 2684 gfp_mask & GFP_RECLAIM_MASK, node); 2685 if (unlikely(!vb)) 2686 return ERR_PTR(-ENOMEM); 2687 2688 va = alloc_vmap_area(VMAP_BLOCK_SIZE, VMAP_BLOCK_SIZE, 2689 VMALLOC_START, VMALLOC_END, 2690 node, gfp_mask, 2691 VMAP_RAM|VMAP_BLOCK, NULL); 2692 if (IS_ERR(va)) { 2693 kfree(vb); 2694 return ERR_CAST(va); 2695 } 2696 2697 vaddr = vmap_block_vaddr(va->va_start, 0); 2698 spin_lock_init(&vb->lock); 2699 vb->va = va; 2700 /* At least something should be left free */ 2701 BUG_ON(VMAP_BBMAP_BITS <= (1UL << order)); 2702 bitmap_zero(vb->used_map, VMAP_BBMAP_BITS); 2703 vb->free = VMAP_BBMAP_BITS - (1UL << order); 2704 vb->dirty = 0; 2705 vb->dirty_min = VMAP_BBMAP_BITS; 2706 vb->dirty_max = 0; 2707 bitmap_set(vb->used_map, 0, (1UL << order)); 2708 INIT_LIST_HEAD(&vb->free_list); 2709 vb->cpu = raw_smp_processor_id(); 2710 2711 xa = addr_to_vb_xa(va->va_start); 2712 vb_idx = addr_to_vb_idx(va->va_start); 2713 err = xa_insert(xa, vb_idx, vb, gfp_mask); 2714 if (err) { 2715 kfree(vb); 2716 free_vmap_area(va); 2717 return ERR_PTR(err); 2718 } 2719 /* 2720 * list_add_tail_rcu could happened in another core 2721 * rather than vb->cpu due to task migration, which 2722 * is safe as list_add_tail_rcu will ensure the list's 2723 * integrity together with list_for_each_rcu from read 2724 * side. 2725 */ 2726 vbq = per_cpu_ptr(&vmap_block_queue, vb->cpu); 2727 spin_lock(&vbq->lock); 2728 list_add_tail_rcu(&vb->free_list, &vbq->free); 2729 spin_unlock(&vbq->lock); 2730 2731 return vaddr; 2732 } 2733 2734 static void free_vmap_block(struct vmap_block *vb) 2735 { 2736 struct vmap_node *vn; 2737 struct vmap_block *tmp; 2738 struct xarray *xa; 2739 2740 xa = addr_to_vb_xa(vb->va->va_start); 2741 tmp = xa_erase(xa, addr_to_vb_idx(vb->va->va_start)); 2742 BUG_ON(tmp != vb); 2743 2744 vn = addr_to_node(vb->va->va_start); 2745 spin_lock(&vn->busy.lock); 2746 unlink_va(vb->va, &vn->busy.root); 2747 spin_unlock(&vn->busy.lock); 2748 2749 free_vmap_area_noflush(vb->va); 2750 kfree_rcu(vb, rcu_head); 2751 } 2752 2753 static bool purge_fragmented_block(struct vmap_block *vb, 2754 struct list_head *purge_list, bool force_purge) 2755 { 2756 struct vmap_block_queue *vbq = &per_cpu(vmap_block_queue, vb->cpu); 2757 2758 if (vb->free + vb->dirty != VMAP_BBMAP_BITS || 2759 vb->dirty == VMAP_BBMAP_BITS) 2760 return false; 2761 2762 /* Don't overeagerly purge usable blocks unless requested */ 2763 if (!(force_purge || vb->free < VMAP_PURGE_THRESHOLD)) 2764 return false; 2765 2766 /* prevent further allocs after releasing lock */ 2767 WRITE_ONCE(vb->free, 0); 2768 /* prevent purging it again */ 2769 WRITE_ONCE(vb->dirty, VMAP_BBMAP_BITS); 2770 vb->dirty_min = 0; 2771 vb->dirty_max = VMAP_BBMAP_BITS; 2772 spin_lock(&vbq->lock); 2773 list_del_rcu(&vb->free_list); 2774 spin_unlock(&vbq->lock); 2775 list_add_tail(&vb->purge, purge_list); 2776 return true; 2777 } 2778 2779 static void free_purged_blocks(struct list_head *purge_list) 2780 { 2781 struct vmap_block *vb, *n_vb; 2782 2783 list_for_each_entry_safe(vb, n_vb, purge_list, purge) { 2784 list_del(&vb->purge); 2785 free_vmap_block(vb); 2786 } 2787 } 2788 2789 static void purge_fragmented_blocks(int cpu) 2790 { 2791 LIST_HEAD(purge); 2792 struct vmap_block *vb; 2793 struct vmap_block_queue *vbq = &per_cpu(vmap_block_queue, cpu); 2794 2795 rcu_read_lock(); 2796 list_for_each_entry_rcu(vb, &vbq->free, free_list) { 2797 unsigned long free = READ_ONCE(vb->free); 2798 unsigned long dirty = READ_ONCE(vb->dirty); 2799 2800 if (free + dirty != VMAP_BBMAP_BITS || 2801 dirty == VMAP_BBMAP_BITS) 2802 continue; 2803 2804 spin_lock(&vb->lock); 2805 purge_fragmented_block(vb, &purge, true); 2806 spin_unlock(&vb->lock); 2807 } 2808 rcu_read_unlock(); 2809 free_purged_blocks(&purge); 2810 } 2811 2812 static void purge_fragmented_blocks_allcpus(void) 2813 { 2814 int cpu; 2815 2816 for_each_possible_cpu(cpu) 2817 purge_fragmented_blocks(cpu); 2818 } 2819 2820 static void *vb_alloc(unsigned long size, gfp_t gfp_mask) 2821 { 2822 struct vmap_block_queue *vbq; 2823 struct vmap_block *vb; 2824 void *vaddr = NULL; 2825 unsigned int order; 2826 2827 BUG_ON(offset_in_page(size)); 2828 BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC); 2829 if (WARN_ON(size == 0)) { 2830 /* 2831 * Allocating 0 bytes isn't what caller wants since 2832 * get_order(0) returns funny result. Just warn and terminate 2833 * early. 2834 */ 2835 return ERR_PTR(-EINVAL); 2836 } 2837 order = get_order(size); 2838 2839 rcu_read_lock(); 2840 vbq = raw_cpu_ptr(&vmap_block_queue); 2841 list_for_each_entry_rcu(vb, &vbq->free, free_list) { 2842 unsigned long pages_off; 2843 2844 if (READ_ONCE(vb->free) < (1UL << order)) 2845 continue; 2846 2847 spin_lock(&vb->lock); 2848 if (vb->free < (1UL << order)) { 2849 spin_unlock(&vb->lock); 2850 continue; 2851 } 2852 2853 pages_off = VMAP_BBMAP_BITS - vb->free; 2854 vaddr = vmap_block_vaddr(vb->va->va_start, pages_off); 2855 WRITE_ONCE(vb->free, vb->free - (1UL << order)); 2856 bitmap_set(vb->used_map, pages_off, (1UL << order)); 2857 if (vb->free == 0) { 2858 spin_lock(&vbq->lock); 2859 list_del_rcu(&vb->free_list); 2860 spin_unlock(&vbq->lock); 2861 } 2862 2863 spin_unlock(&vb->lock); 2864 break; 2865 } 2866 2867 rcu_read_unlock(); 2868 2869 /* Allocate new block if nothing was found */ 2870 if (!vaddr) 2871 vaddr = new_vmap_block(order, gfp_mask); 2872 2873 return vaddr; 2874 } 2875 2876 static void vb_free(unsigned long addr, unsigned long size) 2877 { 2878 unsigned long offset; 2879 unsigned int order; 2880 struct vmap_block *vb; 2881 struct xarray *xa; 2882 2883 BUG_ON(offset_in_page(size)); 2884 BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC); 2885 2886 flush_cache_vunmap(addr, addr + size); 2887 2888 order = get_order(size); 2889 offset = (addr & (VMAP_BLOCK_SIZE - 1)) >> PAGE_SHIFT; 2890 2891 xa = addr_to_vb_xa(addr); 2892 vb = xa_load(xa, addr_to_vb_idx(addr)); 2893 2894 spin_lock(&vb->lock); 2895 bitmap_clear(vb->used_map, offset, (1UL << order)); 2896 spin_unlock(&vb->lock); 2897 2898 vunmap_range_noflush(addr, addr + size); 2899 2900 if (debug_pagealloc_enabled_static()) 2901 flush_tlb_kernel_range(addr, addr + size); 2902 2903 spin_lock(&vb->lock); 2904 2905 /* Expand the not yet TLB flushed dirty range */ 2906 vb->dirty_min = min(vb->dirty_min, offset); 2907 vb->dirty_max = max(vb->dirty_max, offset + (1UL << order)); 2908 2909 WRITE_ONCE(vb->dirty, vb->dirty + (1UL << order)); 2910 if (vb->dirty == VMAP_BBMAP_BITS) { 2911 BUG_ON(vb->free); 2912 spin_unlock(&vb->lock); 2913 free_vmap_block(vb); 2914 } else 2915 spin_unlock(&vb->lock); 2916 } 2917 2918 static void _vm_unmap_aliases(unsigned long start, unsigned long end, int flush) 2919 { 2920 LIST_HEAD(purge_list); 2921 int cpu; 2922 2923 if (unlikely(!vmap_initialized)) 2924 return; 2925 2926 mutex_lock(&vmap_purge_lock); 2927 2928 for_each_possible_cpu(cpu) { 2929 struct vmap_block_queue *vbq = &per_cpu(vmap_block_queue, cpu); 2930 struct vmap_block *vb; 2931 unsigned long idx; 2932 2933 rcu_read_lock(); 2934 xa_for_each(&vbq->vmap_blocks, idx, vb) { 2935 spin_lock(&vb->lock); 2936 2937 /* 2938 * Try to purge a fragmented block first. If it's 2939 * not purgeable, check whether there is dirty 2940 * space to be flushed. 2941 */ 2942 if (!purge_fragmented_block(vb, &purge_list, false) && 2943 vb->dirty_max && vb->dirty != VMAP_BBMAP_BITS) { 2944 unsigned long va_start = vb->va->va_start; 2945 unsigned long s, e; 2946 2947 s = va_start + (vb->dirty_min << PAGE_SHIFT); 2948 e = va_start + (vb->dirty_max << PAGE_SHIFT); 2949 2950 start = min(s, start); 2951 end = max(e, end); 2952 2953 /* Prevent that this is flushed again */ 2954 vb->dirty_min = VMAP_BBMAP_BITS; 2955 vb->dirty_max = 0; 2956 2957 flush = 1; 2958 } 2959 spin_unlock(&vb->lock); 2960 } 2961 rcu_read_unlock(); 2962 } 2963 free_purged_blocks(&purge_list); 2964 2965 if (!__purge_vmap_area_lazy(start, end, false) && flush) 2966 flush_tlb_kernel_range(start, end); 2967 mutex_unlock(&vmap_purge_lock); 2968 } 2969 2970 /** 2971 * vm_unmap_aliases - unmap outstanding lazy aliases in the vmap layer 2972 * 2973 * The vmap/vmalloc layer lazily flushes kernel virtual mappings primarily 2974 * to amortize TLB flushing overheads. What this means is that any page you 2975 * have now, may, in a former life, have been mapped into kernel virtual 2976 * address by the vmap layer and so there might be some CPUs with TLB entries 2977 * still referencing that page (additional to the regular 1:1 kernel mapping). 2978 * 2979 * vm_unmap_aliases flushes all such lazy mappings. After it returns, we can 2980 * be sure that none of the pages we have control over will have any aliases 2981 * from the vmap layer. 2982 */ 2983 void vm_unmap_aliases(void) 2984 { 2985 _vm_unmap_aliases(ULONG_MAX, 0, 0); 2986 } 2987 EXPORT_SYMBOL_GPL(vm_unmap_aliases); 2988 2989 /** 2990 * vm_unmap_ram - unmap linear kernel address space set up by vm_map_ram 2991 * @mem: the pointer returned by vm_map_ram 2992 * @count: the count passed to that vm_map_ram call (cannot unmap partial) 2993 */ 2994 void vm_unmap_ram(const void *mem, unsigned int count) 2995 { 2996 unsigned long size = (unsigned long)count << PAGE_SHIFT; 2997 unsigned long addr = (unsigned long)kasan_reset_tag(mem); 2998 struct vmap_area *va; 2999 3000 might_sleep(); 3001 BUG_ON(!addr); 3002 BUG_ON(addr < VMALLOC_START); 3003 BUG_ON(addr > VMALLOC_END); 3004 BUG_ON(!PAGE_ALIGNED(addr)); 3005 3006 kasan_poison_vmalloc(mem, size); 3007 3008 if (likely(count <= VMAP_MAX_ALLOC)) { 3009 debug_check_no_locks_freed(mem, size); 3010 vb_free(addr, size); 3011 return; 3012 } 3013 3014 va = find_unlink_vmap_area(addr); 3015 if (WARN_ON_ONCE(!va)) 3016 return; 3017 3018 debug_check_no_locks_freed((void *)va->va_start, va_size(va)); 3019 free_unmap_vmap_area(va); 3020 } 3021 EXPORT_SYMBOL(vm_unmap_ram); 3022 3023 /** 3024 * vm_map_ram - map pages linearly into kernel virtual address (vmalloc space) 3025 * @pages: an array of pointers to the pages to be mapped 3026 * @count: number of pages 3027 * @node: prefer to allocate data structures on this node 3028 * 3029 * If you use this function for less than VMAP_MAX_ALLOC pages, it could be 3030 * faster than vmap so it's good. But if you mix long-life and short-life 3031 * objects with vm_map_ram(), it could consume lots of address space through 3032 * fragmentation (especially on a 32bit machine). You could see failures in 3033 * the end. Please use this function for short-lived objects. 3034 * 3035 * Returns: a pointer to the address that has been mapped, or %NULL on failure 3036 */ 3037 void *vm_map_ram(struct page **pages, unsigned int count, int node) 3038 { 3039 unsigned long size = (unsigned long)count << PAGE_SHIFT; 3040 unsigned long addr; 3041 void *mem; 3042 3043 if (likely(count <= VMAP_MAX_ALLOC)) { 3044 mem = vb_alloc(size, GFP_KERNEL); 3045 if (IS_ERR(mem)) 3046 return NULL; 3047 addr = (unsigned long)mem; 3048 } else { 3049 struct vmap_area *va; 3050 va = alloc_vmap_area(size, PAGE_SIZE, 3051 VMALLOC_START, VMALLOC_END, 3052 node, GFP_KERNEL, VMAP_RAM, 3053 NULL); 3054 if (IS_ERR(va)) 3055 return NULL; 3056 3057 addr = va->va_start; 3058 mem = (void *)addr; 3059 } 3060 3061 if (vmap_pages_range(addr, addr + size, PAGE_KERNEL, 3062 pages, PAGE_SHIFT) < 0) { 3063 vm_unmap_ram(mem, count); 3064 return NULL; 3065 } 3066 3067 /* 3068 * Mark the pages as accessible, now that they are mapped. 3069 * With hardware tag-based KASAN, marking is skipped for 3070 * non-VM_ALLOC mappings, see __kasan_unpoison_vmalloc(). 3071 */ 3072 mem = kasan_unpoison_vmalloc(mem, size, KASAN_VMALLOC_PROT_NORMAL); 3073 3074 return mem; 3075 } 3076 EXPORT_SYMBOL(vm_map_ram); 3077 3078 static struct vm_struct *vmlist __initdata; 3079 3080 static inline unsigned int vm_area_page_order(struct vm_struct *vm) 3081 { 3082 #ifdef CONFIG_HAVE_ARCH_HUGE_VMALLOC 3083 return vm->page_order; 3084 #else 3085 return 0; 3086 #endif 3087 } 3088 3089 unsigned int get_vm_area_page_order(struct vm_struct *vm) 3090 { 3091 return vm_area_page_order(vm); 3092 } 3093 3094 static inline void set_vm_area_page_order(struct vm_struct *vm, unsigned int order) 3095 { 3096 #ifdef CONFIG_HAVE_ARCH_HUGE_VMALLOC 3097 vm->page_order = order; 3098 #else 3099 BUG_ON(order != 0); 3100 #endif 3101 } 3102 3103 /** 3104 * vm_area_add_early - add vmap area early during boot 3105 * @vm: vm_struct to add 3106 * 3107 * This function is used to add fixed kernel vm area to vmlist before 3108 * vmalloc_init() is called. @vm->addr, @vm->size, and @vm->flags 3109 * should contain proper values and the other fields should be zero. 3110 * 3111 * DO NOT USE THIS FUNCTION UNLESS YOU KNOW WHAT YOU'RE DOING. 3112 */ 3113 void __init vm_area_add_early(struct vm_struct *vm) 3114 { 3115 struct vm_struct *tmp, **p; 3116 3117 BUG_ON(vmap_initialized); 3118 for (p = &vmlist; (tmp = *p) != NULL; p = &tmp->next) { 3119 if (tmp->addr >= vm->addr) { 3120 BUG_ON(tmp->addr < vm->addr + vm->size); 3121 break; 3122 } else 3123 BUG_ON(tmp->addr + tmp->size > vm->addr); 3124 } 3125 vm->next = *p; 3126 *p = vm; 3127 } 3128 3129 /** 3130 * vm_area_register_early - register vmap area early during boot 3131 * @vm: vm_struct to register 3132 * @align: requested alignment 3133 * 3134 * This function is used to register kernel vm area before 3135 * vmalloc_init() is called. @vm->size and @vm->flags should contain 3136 * proper values on entry and other fields should be zero. On return, 3137 * vm->addr contains the allocated address. 3138 * 3139 * DO NOT USE THIS FUNCTION UNLESS YOU KNOW WHAT YOU'RE DOING. 3140 */ 3141 void __init vm_area_register_early(struct vm_struct *vm, size_t align) 3142 { 3143 unsigned long addr = ALIGN(VMALLOC_START, align); 3144 struct vm_struct *cur, **p; 3145 3146 BUG_ON(vmap_initialized); 3147 3148 for (p = &vmlist; (cur = *p) != NULL; p = &cur->next) { 3149 if ((unsigned long)cur->addr - addr >= vm->size) 3150 break; 3151 addr = ALIGN((unsigned long)cur->addr + cur->size, align); 3152 } 3153 3154 BUG_ON(addr > VMALLOC_END - vm->size); 3155 vm->addr = (void *)addr; 3156 vm->next = *p; 3157 *p = vm; 3158 kasan_populate_early_vm_area_shadow(vm->addr, vm->size); 3159 } 3160 3161 static void clear_vm_uninitialized_flag(struct vm_struct *vm) 3162 { 3163 /* 3164 * Before removing VM_UNINITIALIZED, 3165 * we should make sure that vm has proper values. 3166 * Pair with smp_rmb() in vread_iter() and vmalloc_info_show(). 3167 */ 3168 smp_wmb(); 3169 vm->flags &= ~VM_UNINITIALIZED; 3170 } 3171 3172 struct vm_struct *__get_vm_area_node(unsigned long size, 3173 unsigned long align, unsigned long shift, unsigned long flags, 3174 unsigned long start, unsigned long end, int node, 3175 gfp_t gfp_mask, const void *caller) 3176 { 3177 struct vmap_area *va; 3178 struct vm_struct *area; 3179 unsigned long requested_size = size; 3180 3181 BUG_ON(in_interrupt()); 3182 size = ALIGN(size, 1ul << shift); 3183 if (unlikely(!size)) 3184 return NULL; 3185 3186 if (flags & VM_IOREMAP) 3187 align = 1ul << clamp_t(int, get_count_order_long(size), 3188 PAGE_SHIFT, IOREMAP_MAX_ORDER); 3189 3190 area = kzalloc_node(sizeof(*area), gfp_mask & GFP_RECLAIM_MASK, node); 3191 if (unlikely(!area)) 3192 return NULL; 3193 3194 if (!(flags & VM_NO_GUARD)) 3195 size += PAGE_SIZE; 3196 3197 area->flags = flags; 3198 area->caller = caller; 3199 area->requested_size = requested_size; 3200 3201 va = alloc_vmap_area(size, align, start, end, node, gfp_mask, 0, area); 3202 if (IS_ERR(va)) { 3203 kfree(area); 3204 return NULL; 3205 } 3206 3207 /* 3208 * Mark pages for non-VM_ALLOC mappings as accessible. Do it now as a 3209 * best-effort approach, as they can be mapped outside of vmalloc code. 3210 * For VM_ALLOC mappings, the pages are marked as accessible after 3211 * getting mapped in __vmalloc_node_range(). 3212 * With hardware tag-based KASAN, marking is skipped for 3213 * non-VM_ALLOC mappings, see __kasan_unpoison_vmalloc(). 3214 */ 3215 if (!(flags & VM_ALLOC)) 3216 area->addr = kasan_unpoison_vmalloc(area->addr, requested_size, 3217 KASAN_VMALLOC_PROT_NORMAL); 3218 3219 return area; 3220 } 3221 3222 struct vm_struct *__get_vm_area_caller(unsigned long size, unsigned long flags, 3223 unsigned long start, unsigned long end, 3224 const void *caller) 3225 { 3226 return __get_vm_area_node(size, 1, PAGE_SHIFT, flags, start, end, 3227 NUMA_NO_NODE, GFP_KERNEL, caller); 3228 } 3229 3230 /** 3231 * get_vm_area - reserve a contiguous kernel virtual area 3232 * @size: size of the area 3233 * @flags: %VM_IOREMAP for I/O mappings or VM_ALLOC 3234 * 3235 * Search an area of @size in the kernel virtual mapping area, 3236 * and reserved it for out purposes. Returns the area descriptor 3237 * on success or %NULL on failure. 3238 * 3239 * Return: the area descriptor on success or %NULL on failure. 3240 */ 3241 struct vm_struct *get_vm_area(unsigned long size, unsigned long flags) 3242 { 3243 return __get_vm_area_node(size, 1, PAGE_SHIFT, flags, 3244 VMALLOC_START, VMALLOC_END, 3245 NUMA_NO_NODE, GFP_KERNEL, 3246 __builtin_return_address(0)); 3247 } 3248 3249 struct vm_struct *get_vm_area_caller(unsigned long size, unsigned long flags, 3250 const void *caller) 3251 { 3252 return __get_vm_area_node(size, 1, PAGE_SHIFT, flags, 3253 VMALLOC_START, VMALLOC_END, 3254 NUMA_NO_NODE, GFP_KERNEL, caller); 3255 } 3256 3257 /** 3258 * find_vm_area - find a continuous kernel virtual area 3259 * @addr: base address 3260 * 3261 * Search for the kernel VM area starting at @addr, and return it. 3262 * It is up to the caller to do all required locking to keep the returned 3263 * pointer valid. 3264 * 3265 * Return: the area descriptor on success or %NULL on failure. 3266 */ 3267 struct vm_struct *find_vm_area(const void *addr) 3268 { 3269 struct vmap_area *va; 3270 3271 va = find_vmap_area((unsigned long)addr); 3272 if (!va) 3273 return NULL; 3274 3275 return va->vm; 3276 } 3277 3278 /** 3279 * remove_vm_area - find and remove a continuous kernel virtual area 3280 * @addr: base address 3281 * 3282 * Search for the kernel VM area starting at @addr, and remove it. 3283 * This function returns the found VM area, but using it is NOT safe 3284 * on SMP machines, except for its size or flags. 3285 * 3286 * Return: the area descriptor on success or %NULL on failure. 3287 */ 3288 struct vm_struct *remove_vm_area(const void *addr) 3289 { 3290 struct vmap_area *va; 3291 struct vm_struct *vm; 3292 3293 might_sleep(); 3294 3295 if (WARN(!PAGE_ALIGNED(addr), "Trying to vfree() bad address (%p)\n", 3296 addr)) 3297 return NULL; 3298 3299 va = find_unlink_vmap_area((unsigned long)addr); 3300 if (!va || !va->vm) 3301 return NULL; 3302 vm = va->vm; 3303 3304 debug_check_no_locks_freed(vm->addr, get_vm_area_size(vm)); 3305 debug_check_no_obj_freed(vm->addr, get_vm_area_size(vm)); 3306 kasan_free_module_shadow(vm); 3307 kasan_poison_vmalloc(vm->addr, get_vm_area_size(vm)); 3308 3309 free_unmap_vmap_area(va); 3310 return vm; 3311 } 3312 3313 static inline void set_area_direct_map(const struct vm_struct *area, 3314 int (*set_direct_map)(struct page *page)) 3315 { 3316 int i; 3317 3318 /* HUGE_VMALLOC passes small pages to set_direct_map */ 3319 for (i = 0; i < area->nr_pages; i++) 3320 if (page_address(area->pages[i])) 3321 set_direct_map(area->pages[i]); 3322 } 3323 3324 /* 3325 * Flush the vm mapping and reset the direct map. 3326 */ 3327 static void vm_reset_perms(struct vm_struct *area) 3328 { 3329 unsigned long start = ULONG_MAX, end = 0; 3330 unsigned int page_order = vm_area_page_order(area); 3331 int flush_dmap = 0; 3332 int i; 3333 3334 /* 3335 * Find the start and end range of the direct mappings to make sure that 3336 * the vm_unmap_aliases() flush includes the direct map. 3337 */ 3338 for (i = 0; i < area->nr_pages; i += 1U << page_order) { 3339 unsigned long addr = (unsigned long)page_address(area->pages[i]); 3340 3341 if (addr) { 3342 unsigned long page_size; 3343 3344 page_size = PAGE_SIZE << page_order; 3345 start = min(addr, start); 3346 end = max(addr + page_size, end); 3347 flush_dmap = 1; 3348 } 3349 } 3350 3351 /* 3352 * Set direct map to something invalid so that it won't be cached if 3353 * there are any accesses after the TLB flush, then flush the TLB and 3354 * reset the direct map permissions to the default. 3355 */ 3356 set_area_direct_map(area, set_direct_map_invalid_noflush); 3357 _vm_unmap_aliases(start, end, flush_dmap); 3358 set_area_direct_map(area, set_direct_map_default_noflush); 3359 } 3360 3361 static void delayed_vfree_work(struct work_struct *w) 3362 { 3363 struct vfree_deferred *p = container_of(w, struct vfree_deferred, wq); 3364 struct llist_node *t, *llnode; 3365 3366 llist_for_each_safe(llnode, t, llist_del_all(&p->list)) 3367 vfree(llnode); 3368 } 3369 3370 /** 3371 * vfree_atomic - release memory allocated by vmalloc() 3372 * @addr: memory base address 3373 * 3374 * This one is just like vfree() but can be called in any atomic context 3375 * except NMIs. 3376 */ 3377 void vfree_atomic(const void *addr) 3378 { 3379 struct vfree_deferred *p = raw_cpu_ptr(&vfree_deferred); 3380 3381 BUG_ON(in_nmi()); 3382 kmemleak_free(addr); 3383 3384 /* 3385 * Use raw_cpu_ptr() because this can be called from preemptible 3386 * context. Preemption is absolutely fine here, because the llist_add() 3387 * implementation is lockless, so it works even if we are adding to 3388 * another cpu's list. schedule_work() should be fine with this too. 3389 */ 3390 if (addr && llist_add((struct llist_node *)addr, &p->list)) 3391 schedule_work(&p->wq); 3392 } 3393 3394 /** 3395 * vfree - Release memory allocated by vmalloc() 3396 * @addr: Memory base address 3397 * 3398 * Free the virtually continuous memory area starting at @addr, as obtained 3399 * from one of the vmalloc() family of APIs. This will usually also free the 3400 * physical memory underlying the virtual allocation, but that memory is 3401 * reference counted, so it will not be freed until the last user goes away. 3402 * 3403 * If @addr is NULL, no operation is performed. 3404 * 3405 * Context: 3406 * May sleep if called *not* from interrupt context. 3407 * Must not be called in NMI context (strictly speaking, it could be 3408 * if we have CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG, but making the calling 3409 * conventions for vfree() arch-dependent would be a really bad idea). 3410 */ 3411 void vfree(const void *addr) 3412 { 3413 struct vm_struct *vm; 3414 int i; 3415 3416 if (unlikely(in_interrupt())) { 3417 vfree_atomic(addr); 3418 return; 3419 } 3420 3421 BUG_ON(in_nmi()); 3422 kmemleak_free(addr); 3423 might_sleep(); 3424 3425 if (!addr) 3426 return; 3427 3428 vm = remove_vm_area(addr); 3429 if (unlikely(!vm)) { 3430 WARN(1, KERN_ERR "Trying to vfree() nonexistent vm area (%p)\n", 3431 addr); 3432 return; 3433 } 3434 3435 if (unlikely(vm->flags & VM_FLUSH_RESET_PERMS)) 3436 vm_reset_perms(vm); 3437 /* All pages of vm should be charged to same memcg, so use first one. */ 3438 if (vm->nr_pages && !(vm->flags & VM_MAP_PUT_PAGES)) 3439 mod_memcg_page_state(vm->pages[0], MEMCG_VMALLOC, -vm->nr_pages); 3440 for (i = 0; i < vm->nr_pages; i++) { 3441 struct page *page = vm->pages[i]; 3442 3443 BUG_ON(!page); 3444 /* 3445 * High-order allocs for huge vmallocs are split, so 3446 * can be freed as an array of order-0 allocations 3447 */ 3448 __free_page(page); 3449 cond_resched(); 3450 } 3451 if (!(vm->flags & VM_MAP_PUT_PAGES)) 3452 atomic_long_sub(vm->nr_pages, &nr_vmalloc_pages); 3453 kvfree(vm->pages); 3454 kfree(vm); 3455 } 3456 EXPORT_SYMBOL(vfree); 3457 3458 /** 3459 * vunmap - release virtual mapping obtained by vmap() 3460 * @addr: memory base address 3461 * 3462 * Free the virtually contiguous memory area starting at @addr, 3463 * which was created from the page array passed to vmap(). 3464 * 3465 * Must not be called in interrupt context. 3466 */ 3467 void vunmap(const void *addr) 3468 { 3469 struct vm_struct *vm; 3470 3471 BUG_ON(in_interrupt()); 3472 might_sleep(); 3473 3474 if (!addr) 3475 return; 3476 vm = remove_vm_area(addr); 3477 if (unlikely(!vm)) { 3478 WARN(1, KERN_ERR "Trying to vunmap() nonexistent vm area (%p)\n", 3479 addr); 3480 return; 3481 } 3482 kfree(vm); 3483 } 3484 EXPORT_SYMBOL(vunmap); 3485 3486 /** 3487 * vmap - map an array of pages into virtually contiguous space 3488 * @pages: array of page pointers 3489 * @count: number of pages to map 3490 * @flags: vm_area->flags 3491 * @prot: page protection for the mapping 3492 * 3493 * Maps @count pages from @pages into contiguous kernel virtual space. 3494 * If @flags contains %VM_MAP_PUT_PAGES the ownership of the pages array itself 3495 * (which must be kmalloc or vmalloc memory) and one reference per pages in it 3496 * are transferred from the caller to vmap(), and will be freed / dropped when 3497 * vfree() is called on the return value. 3498 * 3499 * Return: the address of the area or %NULL on failure 3500 */ 3501 void *vmap(struct page **pages, unsigned int count, 3502 unsigned long flags, pgprot_t prot) 3503 { 3504 struct vm_struct *area; 3505 unsigned long addr; 3506 unsigned long size; /* In bytes */ 3507 3508 might_sleep(); 3509 3510 if (WARN_ON_ONCE(flags & VM_FLUSH_RESET_PERMS)) 3511 return NULL; 3512 3513 /* 3514 * Your top guard is someone else's bottom guard. Not having a top 3515 * guard compromises someone else's mappings too. 3516 */ 3517 if (WARN_ON_ONCE(flags & VM_NO_GUARD)) 3518 flags &= ~VM_NO_GUARD; 3519 3520 if (count > totalram_pages()) 3521 return NULL; 3522 3523 size = (unsigned long)count << PAGE_SHIFT; 3524 area = get_vm_area_caller(size, flags, __builtin_return_address(0)); 3525 if (!area) 3526 return NULL; 3527 3528 addr = (unsigned long)area->addr; 3529 if (vmap_pages_range(addr, addr + size, pgprot_nx(prot), 3530 pages, PAGE_SHIFT) < 0) { 3531 vunmap(area->addr); 3532 return NULL; 3533 } 3534 3535 if (flags & VM_MAP_PUT_PAGES) { 3536 area->pages = pages; 3537 area->nr_pages = count; 3538 } 3539 return area->addr; 3540 } 3541 EXPORT_SYMBOL(vmap); 3542 3543 #ifdef CONFIG_VMAP_PFN 3544 struct vmap_pfn_data { 3545 unsigned long *pfns; 3546 pgprot_t prot; 3547 unsigned int idx; 3548 }; 3549 3550 static int vmap_pfn_apply(pte_t *pte, unsigned long addr, void *private) 3551 { 3552 struct vmap_pfn_data *data = private; 3553 unsigned long pfn = data->pfns[data->idx]; 3554 pte_t ptent; 3555 3556 if (WARN_ON_ONCE(pfn_valid(pfn))) 3557 return -EINVAL; 3558 3559 ptent = pte_mkspecial(pfn_pte(pfn, data->prot)); 3560 set_pte_at(&init_mm, addr, pte, ptent); 3561 3562 data->idx++; 3563 return 0; 3564 } 3565 3566 /** 3567 * vmap_pfn - map an array of PFNs into virtually contiguous space 3568 * @pfns: array of PFNs 3569 * @count: number of pages to map 3570 * @prot: page protection for the mapping 3571 * 3572 * Maps @count PFNs from @pfns into contiguous kernel virtual space and returns 3573 * the start address of the mapping. 3574 */ 3575 void *vmap_pfn(unsigned long *pfns, unsigned int count, pgprot_t prot) 3576 { 3577 struct vmap_pfn_data data = { .pfns = pfns, .prot = pgprot_nx(prot) }; 3578 struct vm_struct *area; 3579 3580 area = get_vm_area_caller(count * PAGE_SIZE, VM_IOREMAP, 3581 __builtin_return_address(0)); 3582 if (!area) 3583 return NULL; 3584 if (apply_to_page_range(&init_mm, (unsigned long)area->addr, 3585 count * PAGE_SIZE, vmap_pfn_apply, &data)) { 3586 free_vm_area(area); 3587 return NULL; 3588 } 3589 3590 flush_cache_vmap((unsigned long)area->addr, 3591 (unsigned long)area->addr + count * PAGE_SIZE); 3592 3593 return area->addr; 3594 } 3595 EXPORT_SYMBOL_GPL(vmap_pfn); 3596 #endif /* CONFIG_VMAP_PFN */ 3597 3598 static inline unsigned int 3599 vm_area_alloc_pages(gfp_t gfp, int nid, 3600 unsigned int order, unsigned int nr_pages, struct page **pages) 3601 { 3602 unsigned int nr_allocated = 0; 3603 struct page *page; 3604 int i; 3605 3606 /* 3607 * For order-0 pages we make use of bulk allocator, if 3608 * the page array is partly or not at all populated due 3609 * to fails, fallback to a single page allocator that is 3610 * more permissive. 3611 */ 3612 if (!order) { 3613 while (nr_allocated < nr_pages) { 3614 unsigned int nr, nr_pages_request; 3615 3616 /* 3617 * A maximum allowed request is hard-coded and is 100 3618 * pages per call. That is done in order to prevent a 3619 * long preemption off scenario in the bulk-allocator 3620 * so the range is [1:100]. 3621 */ 3622 nr_pages_request = min(100U, nr_pages - nr_allocated); 3623 3624 /* memory allocation should consider mempolicy, we can't 3625 * wrongly use nearest node when nid == NUMA_NO_NODE, 3626 * otherwise memory may be allocated in only one node, 3627 * but mempolicy wants to alloc memory by interleaving. 3628 */ 3629 if (IS_ENABLED(CONFIG_NUMA) && nid == NUMA_NO_NODE) 3630 nr = alloc_pages_bulk_mempolicy_noprof(gfp, 3631 nr_pages_request, 3632 pages + nr_allocated); 3633 else 3634 nr = alloc_pages_bulk_node_noprof(gfp, nid, 3635 nr_pages_request, 3636 pages + nr_allocated); 3637 3638 nr_allocated += nr; 3639 3640 /* 3641 * If zero or pages were obtained partly, 3642 * fallback to a single page allocator. 3643 */ 3644 if (nr != nr_pages_request) 3645 break; 3646 } 3647 } 3648 3649 /* High-order pages or fallback path if "bulk" fails. */ 3650 while (nr_allocated < nr_pages) { 3651 if (!(gfp & __GFP_NOFAIL) && fatal_signal_pending(current)) 3652 break; 3653 3654 if (nid == NUMA_NO_NODE) 3655 page = alloc_pages_noprof(gfp, order); 3656 else 3657 page = alloc_pages_node_noprof(nid, gfp, order); 3658 3659 if (unlikely(!page)) 3660 break; 3661 3662 /* 3663 * High-order allocations must be able to be treated as 3664 * independent small pages by callers (as they can with 3665 * small-page vmallocs). Some drivers do their own refcounting 3666 * on vmalloc_to_page() pages, some use page->mapping, 3667 * page->lru, etc. 3668 */ 3669 if (order) 3670 split_page(page, order); 3671 3672 /* 3673 * Careful, we allocate and map page-order pages, but 3674 * tracking is done per PAGE_SIZE page so as to keep the 3675 * vm_struct APIs independent of the physical/mapped size. 3676 */ 3677 for (i = 0; i < (1U << order); i++) 3678 pages[nr_allocated + i] = page + i; 3679 3680 nr_allocated += 1U << order; 3681 } 3682 3683 return nr_allocated; 3684 } 3685 3686 static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask, 3687 pgprot_t prot, unsigned int page_shift, 3688 int node) 3689 { 3690 const gfp_t nested_gfp = (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO; 3691 bool nofail = gfp_mask & __GFP_NOFAIL; 3692 unsigned long addr = (unsigned long)area->addr; 3693 unsigned long size = get_vm_area_size(area); 3694 unsigned long array_size; 3695 unsigned int nr_small_pages = size >> PAGE_SHIFT; 3696 unsigned int page_order; 3697 unsigned int flags; 3698 int ret; 3699 3700 array_size = (unsigned long)nr_small_pages * sizeof(struct page *); 3701 3702 if (!(gfp_mask & (GFP_DMA | GFP_DMA32))) 3703 gfp_mask |= __GFP_HIGHMEM; 3704 3705 /* Please note that the recursion is strictly bounded. */ 3706 if (array_size > PAGE_SIZE) { 3707 area->pages = __vmalloc_node_noprof(array_size, 1, nested_gfp, node, 3708 area->caller); 3709 } else { 3710 area->pages = kmalloc_node_noprof(array_size, nested_gfp, node); 3711 } 3712 3713 if (!area->pages) { 3714 warn_alloc(gfp_mask, NULL, 3715 "vmalloc error: size %lu, failed to allocated page array size %lu", 3716 nr_small_pages * PAGE_SIZE, array_size); 3717 free_vm_area(area); 3718 return NULL; 3719 } 3720 3721 set_vm_area_page_order(area, page_shift - PAGE_SHIFT); 3722 page_order = vm_area_page_order(area); 3723 3724 /* 3725 * High-order nofail allocations are really expensive and 3726 * potentially dangerous (pre-mature OOM, disruptive reclaim 3727 * and compaction etc. 3728 * 3729 * Please note, the __vmalloc_node_range_noprof() falls-back 3730 * to order-0 pages if high-order attempt is unsuccessful. 3731 */ 3732 area->nr_pages = vm_area_alloc_pages((page_order ? 3733 gfp_mask & ~__GFP_NOFAIL : gfp_mask) | __GFP_NOWARN, 3734 node, page_order, nr_small_pages, area->pages); 3735 3736 atomic_long_add(area->nr_pages, &nr_vmalloc_pages); 3737 /* All pages of vm should be charged to same memcg, so use first one. */ 3738 if (gfp_mask & __GFP_ACCOUNT && area->nr_pages) 3739 mod_memcg_page_state(area->pages[0], MEMCG_VMALLOC, 3740 area->nr_pages); 3741 3742 /* 3743 * If not enough pages were obtained to accomplish an 3744 * allocation request, free them via vfree() if any. 3745 */ 3746 if (area->nr_pages != nr_small_pages) { 3747 /* 3748 * vm_area_alloc_pages() can fail due to insufficient memory but 3749 * also:- 3750 * 3751 * - a pending fatal signal 3752 * - insufficient huge page-order pages 3753 * 3754 * Since we always retry allocations at order-0 in the huge page 3755 * case a warning for either is spurious. 3756 */ 3757 if (!fatal_signal_pending(current) && page_order == 0) 3758 warn_alloc(gfp_mask, NULL, 3759 "vmalloc error: size %lu, failed to allocate pages", 3760 area->nr_pages * PAGE_SIZE); 3761 goto fail; 3762 } 3763 3764 /* 3765 * page tables allocations ignore external gfp mask, enforce it 3766 * by the scope API 3767 */ 3768 if ((gfp_mask & (__GFP_FS | __GFP_IO)) == __GFP_IO) 3769 flags = memalloc_nofs_save(); 3770 else if ((gfp_mask & (__GFP_FS | __GFP_IO)) == 0) 3771 flags = memalloc_noio_save(); 3772 3773 do { 3774 ret = vmap_pages_range(addr, addr + size, prot, area->pages, 3775 page_shift); 3776 if (nofail && (ret < 0)) 3777 schedule_timeout_uninterruptible(1); 3778 } while (nofail && (ret < 0)); 3779 3780 if ((gfp_mask & (__GFP_FS | __GFP_IO)) == __GFP_IO) 3781 memalloc_nofs_restore(flags); 3782 else if ((gfp_mask & (__GFP_FS | __GFP_IO)) == 0) 3783 memalloc_noio_restore(flags); 3784 3785 if (ret < 0) { 3786 warn_alloc(gfp_mask, NULL, 3787 "vmalloc error: size %lu, failed to map pages", 3788 area->nr_pages * PAGE_SIZE); 3789 goto fail; 3790 } 3791 3792 return area->addr; 3793 3794 fail: 3795 vfree(area->addr); 3796 return NULL; 3797 } 3798 3799 /** 3800 * __vmalloc_node_range - allocate virtually contiguous memory 3801 * @size: allocation size 3802 * @align: desired alignment 3803 * @start: vm area range start 3804 * @end: vm area range end 3805 * @gfp_mask: flags for the page level allocator 3806 * @prot: protection mask for the allocated pages 3807 * @vm_flags: additional vm area flags (e.g. %VM_NO_GUARD) 3808 * @node: node to use for allocation or NUMA_NO_NODE 3809 * @caller: caller's return address 3810 * 3811 * Allocate enough pages to cover @size from the page level 3812 * allocator with @gfp_mask flags. Please note that the full set of gfp 3813 * flags are not supported. GFP_KERNEL, GFP_NOFS and GFP_NOIO are all 3814 * supported. 3815 * Zone modifiers are not supported. From the reclaim modifiers 3816 * __GFP_DIRECT_RECLAIM is required (aka GFP_NOWAIT is not supported) 3817 * and only __GFP_NOFAIL is supported (i.e. __GFP_NORETRY and 3818 * __GFP_RETRY_MAYFAIL are not supported). 3819 * 3820 * __GFP_NOWARN can be used to suppress failures messages. 3821 * 3822 * Map them into contiguous kernel virtual space, using a pagetable 3823 * protection of @prot. 3824 * 3825 * Return: the address of the area or %NULL on failure 3826 */ 3827 void *__vmalloc_node_range_noprof(unsigned long size, unsigned long align, 3828 unsigned long start, unsigned long end, gfp_t gfp_mask, 3829 pgprot_t prot, unsigned long vm_flags, int node, 3830 const void *caller) 3831 { 3832 struct vm_struct *area; 3833 void *ret; 3834 kasan_vmalloc_flags_t kasan_flags = KASAN_VMALLOC_NONE; 3835 unsigned long original_align = align; 3836 unsigned int shift = PAGE_SHIFT; 3837 3838 if (WARN_ON_ONCE(!size)) 3839 return NULL; 3840 3841 if ((size >> PAGE_SHIFT) > totalram_pages()) { 3842 warn_alloc(gfp_mask, NULL, 3843 "vmalloc error: size %lu, exceeds total pages", 3844 size); 3845 return NULL; 3846 } 3847 3848 if (vmap_allow_huge && (vm_flags & VM_ALLOW_HUGE_VMAP)) { 3849 /* 3850 * Try huge pages. Only try for PAGE_KERNEL allocations, 3851 * others like modules don't yet expect huge pages in 3852 * their allocations due to apply_to_page_range not 3853 * supporting them. 3854 */ 3855 3856 if (arch_vmap_pmd_supported(prot) && size >= PMD_SIZE) 3857 shift = PMD_SHIFT; 3858 else 3859 shift = arch_vmap_pte_supported_shift(size); 3860 3861 align = max(original_align, 1UL << shift); 3862 } 3863 3864 again: 3865 area = __get_vm_area_node(size, align, shift, VM_ALLOC | 3866 VM_UNINITIALIZED | vm_flags, start, end, node, 3867 gfp_mask, caller); 3868 if (!area) { 3869 bool nofail = gfp_mask & __GFP_NOFAIL; 3870 warn_alloc(gfp_mask, NULL, 3871 "vmalloc error: size %lu, vm_struct allocation failed%s", 3872 size, (nofail) ? ". Retrying." : ""); 3873 if (nofail) { 3874 schedule_timeout_uninterruptible(1); 3875 goto again; 3876 } 3877 goto fail; 3878 } 3879 3880 /* 3881 * Prepare arguments for __vmalloc_area_node() and 3882 * kasan_unpoison_vmalloc(). 3883 */ 3884 if (pgprot_val(prot) == pgprot_val(PAGE_KERNEL)) { 3885 if (kasan_hw_tags_enabled()) { 3886 /* 3887 * Modify protection bits to allow tagging. 3888 * This must be done before mapping. 3889 */ 3890 prot = arch_vmap_pgprot_tagged(prot); 3891 3892 /* 3893 * Skip page_alloc poisoning and zeroing for physical 3894 * pages backing VM_ALLOC mapping. Memory is instead 3895 * poisoned and zeroed by kasan_unpoison_vmalloc(). 3896 */ 3897 gfp_mask |= __GFP_SKIP_KASAN | __GFP_SKIP_ZERO; 3898 } 3899 3900 /* Take note that the mapping is PAGE_KERNEL. */ 3901 kasan_flags |= KASAN_VMALLOC_PROT_NORMAL; 3902 } 3903 3904 /* Allocate physical pages and map them into vmalloc space. */ 3905 ret = __vmalloc_area_node(area, gfp_mask, prot, shift, node); 3906 if (!ret) 3907 goto fail; 3908 3909 /* 3910 * Mark the pages as accessible, now that they are mapped. 3911 * The condition for setting KASAN_VMALLOC_INIT should complement the 3912 * one in post_alloc_hook() with regards to the __GFP_SKIP_ZERO check 3913 * to make sure that memory is initialized under the same conditions. 3914 * Tag-based KASAN modes only assign tags to normal non-executable 3915 * allocations, see __kasan_unpoison_vmalloc(). 3916 */ 3917 kasan_flags |= KASAN_VMALLOC_VM_ALLOC; 3918 if (!want_init_on_free() && want_init_on_alloc(gfp_mask) && 3919 (gfp_mask & __GFP_SKIP_ZERO)) 3920 kasan_flags |= KASAN_VMALLOC_INIT; 3921 /* KASAN_VMALLOC_PROT_NORMAL already set if required. */ 3922 area->addr = kasan_unpoison_vmalloc(area->addr, size, kasan_flags); 3923 3924 /* 3925 * In this function, newly allocated vm_struct has VM_UNINITIALIZED 3926 * flag. It means that vm_struct is not fully initialized. 3927 * Now, it is fully initialized, so remove this flag here. 3928 */ 3929 clear_vm_uninitialized_flag(area); 3930 3931 if (!(vm_flags & VM_DEFER_KMEMLEAK)) 3932 kmemleak_vmalloc(area, PAGE_ALIGN(size), gfp_mask); 3933 3934 return area->addr; 3935 3936 fail: 3937 if (shift > PAGE_SHIFT) { 3938 shift = PAGE_SHIFT; 3939 align = original_align; 3940 goto again; 3941 } 3942 3943 return NULL; 3944 } 3945 3946 /** 3947 * __vmalloc_node - allocate virtually contiguous memory 3948 * @size: allocation size 3949 * @align: desired alignment 3950 * @gfp_mask: flags for the page level allocator 3951 * @node: node to use for allocation or NUMA_NO_NODE 3952 * @caller: caller's return address 3953 * 3954 * Allocate enough pages to cover @size from the page level allocator with 3955 * @gfp_mask flags. Map them into contiguous kernel virtual space. 3956 * 3957 * Reclaim modifiers in @gfp_mask - __GFP_NORETRY, __GFP_RETRY_MAYFAIL 3958 * and __GFP_NOFAIL are not supported 3959 * 3960 * Any use of gfp flags outside of GFP_KERNEL should be consulted 3961 * with mm people. 3962 * 3963 * Return: pointer to the allocated memory or %NULL on error 3964 */ 3965 void *__vmalloc_node_noprof(unsigned long size, unsigned long align, 3966 gfp_t gfp_mask, int node, const void *caller) 3967 { 3968 return __vmalloc_node_range_noprof(size, align, VMALLOC_START, VMALLOC_END, 3969 gfp_mask, PAGE_KERNEL, 0, node, caller); 3970 } 3971 /* 3972 * This is only for performance analysis of vmalloc and stress purpose. 3973 * It is required by vmalloc test module, therefore do not use it other 3974 * than that. 3975 */ 3976 #ifdef CONFIG_TEST_VMALLOC_MODULE 3977 EXPORT_SYMBOL_GPL(__vmalloc_node_noprof); 3978 #endif 3979 3980 void *__vmalloc_noprof(unsigned long size, gfp_t gfp_mask) 3981 { 3982 return __vmalloc_node_noprof(size, 1, gfp_mask, NUMA_NO_NODE, 3983 __builtin_return_address(0)); 3984 } 3985 EXPORT_SYMBOL(__vmalloc_noprof); 3986 3987 /** 3988 * vmalloc - allocate virtually contiguous memory 3989 * @size: allocation size 3990 * 3991 * Allocate enough pages to cover @size from the page level 3992 * allocator and map them into contiguous kernel virtual space. 3993 * 3994 * For tight control over page level allocator and protection flags 3995 * use __vmalloc() instead. 3996 * 3997 * Return: pointer to the allocated memory or %NULL on error 3998 */ 3999 void *vmalloc_noprof(unsigned long size) 4000 { 4001 return __vmalloc_node_noprof(size, 1, GFP_KERNEL, NUMA_NO_NODE, 4002 __builtin_return_address(0)); 4003 } 4004 EXPORT_SYMBOL(vmalloc_noprof); 4005 4006 /** 4007 * vmalloc_huge_node - allocate virtually contiguous memory, allow huge pages 4008 * @size: allocation size 4009 * @gfp_mask: flags for the page level allocator 4010 * @node: node to use for allocation or NUMA_NO_NODE 4011 * 4012 * Allocate enough pages to cover @size from the page level 4013 * allocator and map them into contiguous kernel virtual space. 4014 * If @size is greater than or equal to PMD_SIZE, allow using 4015 * huge pages for the memory 4016 * 4017 * Return: pointer to the allocated memory or %NULL on error 4018 */ 4019 void *vmalloc_huge_node_noprof(unsigned long size, gfp_t gfp_mask, int node) 4020 { 4021 return __vmalloc_node_range_noprof(size, 1, VMALLOC_START, VMALLOC_END, 4022 gfp_mask, PAGE_KERNEL, VM_ALLOW_HUGE_VMAP, 4023 node, __builtin_return_address(0)); 4024 } 4025 EXPORT_SYMBOL_GPL(vmalloc_huge_node_noprof); 4026 4027 /** 4028 * vzalloc - allocate virtually contiguous memory with zero fill 4029 * @size: allocation size 4030 * 4031 * Allocate enough pages to cover @size from the page level 4032 * allocator and map them into contiguous kernel virtual space. 4033 * The memory allocated is set to zero. 4034 * 4035 * For tight control over page level allocator and protection flags 4036 * use __vmalloc() instead. 4037 * 4038 * Return: pointer to the allocated memory or %NULL on error 4039 */ 4040 void *vzalloc_noprof(unsigned long size) 4041 { 4042 return __vmalloc_node_noprof(size, 1, GFP_KERNEL | __GFP_ZERO, NUMA_NO_NODE, 4043 __builtin_return_address(0)); 4044 } 4045 EXPORT_SYMBOL(vzalloc_noprof); 4046 4047 /** 4048 * vmalloc_user - allocate zeroed virtually contiguous memory for userspace 4049 * @size: allocation size 4050 * 4051 * The resulting memory area is zeroed so it can be mapped to userspace 4052 * without leaking data. 4053 * 4054 * Return: pointer to the allocated memory or %NULL on error 4055 */ 4056 void *vmalloc_user_noprof(unsigned long size) 4057 { 4058 return __vmalloc_node_range_noprof(size, SHMLBA, VMALLOC_START, VMALLOC_END, 4059 GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL, 4060 VM_USERMAP, NUMA_NO_NODE, 4061 __builtin_return_address(0)); 4062 } 4063 EXPORT_SYMBOL(vmalloc_user_noprof); 4064 4065 /** 4066 * vmalloc_node - allocate memory on a specific node 4067 * @size: allocation size 4068 * @node: numa node 4069 * 4070 * Allocate enough pages to cover @size from the page level 4071 * allocator and map them into contiguous kernel virtual space. 4072 * 4073 * For tight control over page level allocator and protection flags 4074 * use __vmalloc() instead. 4075 * 4076 * Return: pointer to the allocated memory or %NULL on error 4077 */ 4078 void *vmalloc_node_noprof(unsigned long size, int node) 4079 { 4080 return __vmalloc_node_noprof(size, 1, GFP_KERNEL, node, 4081 __builtin_return_address(0)); 4082 } 4083 EXPORT_SYMBOL(vmalloc_node_noprof); 4084 4085 /** 4086 * vzalloc_node - allocate memory on a specific node with zero fill 4087 * @size: allocation size 4088 * @node: numa node 4089 * 4090 * Allocate enough pages to cover @size from the page level 4091 * allocator and map them into contiguous kernel virtual space. 4092 * The memory allocated is set to zero. 4093 * 4094 * Return: pointer to the allocated memory or %NULL on error 4095 */ 4096 void *vzalloc_node_noprof(unsigned long size, int node) 4097 { 4098 return __vmalloc_node_noprof(size, 1, GFP_KERNEL | __GFP_ZERO, node, 4099 __builtin_return_address(0)); 4100 } 4101 EXPORT_SYMBOL(vzalloc_node_noprof); 4102 4103 /** 4104 * vrealloc_node_align_noprof - reallocate virtually contiguous memory; contents 4105 * remain unchanged 4106 * @p: object to reallocate memory for 4107 * @size: the size to reallocate 4108 * @align: requested alignment 4109 * @flags: the flags for the page level allocator 4110 * @nid: node number of the target node 4111 * 4112 * If @p is %NULL, vrealloc_XXX() behaves exactly like vmalloc_XXX(). If @size 4113 * is 0 and @p is not a %NULL pointer, the object pointed to is freed. 4114 * 4115 * If the caller wants the new memory to be on specific node *only*, 4116 * __GFP_THISNODE flag should be set, otherwise the function will try to avoid 4117 * reallocation and possibly disregard the specified @nid. 4118 * 4119 * If __GFP_ZERO logic is requested, callers must ensure that, starting with the 4120 * initial memory allocation, every subsequent call to this API for the same 4121 * memory allocation is flagged with __GFP_ZERO. Otherwise, it is possible that 4122 * __GFP_ZERO is not fully honored by this API. 4123 * 4124 * Requesting an alignment that is bigger than the alignment of the existing 4125 * allocation will fail. 4126 * 4127 * In any case, the contents of the object pointed to are preserved up to the 4128 * lesser of the new and old sizes. 4129 * 4130 * This function must not be called concurrently with itself or vfree() for the 4131 * same memory allocation. 4132 * 4133 * Return: pointer to the allocated memory; %NULL if @size is zero or in case of 4134 * failure 4135 */ 4136 void *vrealloc_node_align_noprof(const void *p, size_t size, unsigned long align, 4137 gfp_t flags, int nid) 4138 { 4139 struct vm_struct *vm = NULL; 4140 size_t alloced_size = 0; 4141 size_t old_size = 0; 4142 void *n; 4143 4144 if (!size) { 4145 vfree(p); 4146 return NULL; 4147 } 4148 4149 if (p) { 4150 vm = find_vm_area(p); 4151 if (unlikely(!vm)) { 4152 WARN(1, "Trying to vrealloc() nonexistent vm area (%p)\n", p); 4153 return NULL; 4154 } 4155 4156 alloced_size = get_vm_area_size(vm); 4157 old_size = vm->requested_size; 4158 if (WARN(alloced_size < old_size, 4159 "vrealloc() has mismatched area vs requested sizes (%p)\n", p)) 4160 return NULL; 4161 if (WARN(!IS_ALIGNED((unsigned long)p, align), 4162 "will not reallocate with a bigger alignment (0x%lx)\n", align)) 4163 return NULL; 4164 if (unlikely(flags & __GFP_THISNODE) && nid != NUMA_NO_NODE && 4165 nid != page_to_nid(vmalloc_to_page(p))) 4166 goto need_realloc; 4167 } 4168 4169 /* 4170 * TODO: Shrink the vm_area, i.e. unmap and free unused pages. What 4171 * would be a good heuristic for when to shrink the vm_area? 4172 */ 4173 if (size <= old_size) { 4174 /* Zero out "freed" memory, potentially for future realloc. */ 4175 if (want_init_on_free() || want_init_on_alloc(flags)) 4176 memset((void *)p + size, 0, old_size - size); 4177 vm->requested_size = size; 4178 kasan_vrealloc(p, old_size, size); 4179 return (void *)p; 4180 } 4181 4182 /* 4183 * We already have the bytes available in the allocation; use them. 4184 */ 4185 if (size <= alloced_size) { 4186 /* 4187 * No need to zero memory here, as unused memory will have 4188 * already been zeroed at initial allocation time or during 4189 * realloc shrink time. 4190 */ 4191 vm->requested_size = size; 4192 kasan_vrealloc(p, old_size, size); 4193 return (void *)p; 4194 } 4195 4196 need_realloc: 4197 /* TODO: Grow the vm_area, i.e. allocate and map additional pages. */ 4198 n = __vmalloc_node_noprof(size, align, flags, nid, __builtin_return_address(0)); 4199 4200 if (!n) 4201 return NULL; 4202 4203 if (p) { 4204 memcpy(n, p, min(size, old_size)); 4205 vfree(p); 4206 } 4207 4208 return n; 4209 } 4210 4211 #if defined(CONFIG_64BIT) && defined(CONFIG_ZONE_DMA32) 4212 #define GFP_VMALLOC32 (GFP_DMA32 | GFP_KERNEL) 4213 #elif defined(CONFIG_64BIT) && defined(CONFIG_ZONE_DMA) 4214 #define GFP_VMALLOC32 (GFP_DMA | GFP_KERNEL) 4215 #else 4216 /* 4217 * 64b systems should always have either DMA or DMA32 zones. For others 4218 * GFP_DMA32 should do the right thing and use the normal zone. 4219 */ 4220 #define GFP_VMALLOC32 (GFP_DMA32 | GFP_KERNEL) 4221 #endif 4222 4223 /** 4224 * vmalloc_32 - allocate virtually contiguous memory (32bit addressable) 4225 * @size: allocation size 4226 * 4227 * Allocate enough 32bit PA addressable pages to cover @size from the 4228 * page level allocator and map them into contiguous kernel virtual space. 4229 * 4230 * Return: pointer to the allocated memory or %NULL on error 4231 */ 4232 void *vmalloc_32_noprof(unsigned long size) 4233 { 4234 return __vmalloc_node_noprof(size, 1, GFP_VMALLOC32, NUMA_NO_NODE, 4235 __builtin_return_address(0)); 4236 } 4237 EXPORT_SYMBOL(vmalloc_32_noprof); 4238 4239 /** 4240 * vmalloc_32_user - allocate zeroed virtually contiguous 32bit memory 4241 * @size: allocation size 4242 * 4243 * The resulting memory area is 32bit addressable and zeroed so it can be 4244 * mapped to userspace without leaking data. 4245 * 4246 * Return: pointer to the allocated memory or %NULL on error 4247 */ 4248 void *vmalloc_32_user_noprof(unsigned long size) 4249 { 4250 return __vmalloc_node_range_noprof(size, SHMLBA, VMALLOC_START, VMALLOC_END, 4251 GFP_VMALLOC32 | __GFP_ZERO, PAGE_KERNEL, 4252 VM_USERMAP, NUMA_NO_NODE, 4253 __builtin_return_address(0)); 4254 } 4255 EXPORT_SYMBOL(vmalloc_32_user_noprof); 4256 4257 /* 4258 * Atomically zero bytes in the iterator. 4259 * 4260 * Returns the number of zeroed bytes. 4261 */ 4262 static size_t zero_iter(struct iov_iter *iter, size_t count) 4263 { 4264 size_t remains = count; 4265 4266 while (remains > 0) { 4267 size_t num, copied; 4268 4269 num = min_t(size_t, remains, PAGE_SIZE); 4270 copied = copy_page_to_iter_nofault(ZERO_PAGE(0), 0, num, iter); 4271 remains -= copied; 4272 4273 if (copied < num) 4274 break; 4275 } 4276 4277 return count - remains; 4278 } 4279 4280 /* 4281 * small helper routine, copy contents to iter from addr. 4282 * If the page is not present, fill zero. 4283 * 4284 * Returns the number of copied bytes. 4285 */ 4286 static size_t aligned_vread_iter(struct iov_iter *iter, 4287 const char *addr, size_t count) 4288 { 4289 size_t remains = count; 4290 struct page *page; 4291 4292 while (remains > 0) { 4293 unsigned long offset, length; 4294 size_t copied = 0; 4295 4296 offset = offset_in_page(addr); 4297 length = PAGE_SIZE - offset; 4298 if (length > remains) 4299 length = remains; 4300 page = vmalloc_to_page(addr); 4301 /* 4302 * To do safe access to this _mapped_ area, we need lock. But 4303 * adding lock here means that we need to add overhead of 4304 * vmalloc()/vfree() calls for this _debug_ interface, rarely 4305 * used. Instead of that, we'll use an local mapping via 4306 * copy_page_to_iter_nofault() and accept a small overhead in 4307 * this access function. 4308 */ 4309 if (page) 4310 copied = copy_page_to_iter_nofault(page, offset, 4311 length, iter); 4312 else 4313 copied = zero_iter(iter, length); 4314 4315 addr += copied; 4316 remains -= copied; 4317 4318 if (copied != length) 4319 break; 4320 } 4321 4322 return count - remains; 4323 } 4324 4325 /* 4326 * Read from a vm_map_ram region of memory. 4327 * 4328 * Returns the number of copied bytes. 4329 */ 4330 static size_t vmap_ram_vread_iter(struct iov_iter *iter, const char *addr, 4331 size_t count, unsigned long flags) 4332 { 4333 char *start; 4334 struct vmap_block *vb; 4335 struct xarray *xa; 4336 unsigned long offset; 4337 unsigned int rs, re; 4338 size_t remains, n; 4339 4340 /* 4341 * If it's area created by vm_map_ram() interface directly, but 4342 * not further subdividing and delegating management to vmap_block, 4343 * handle it here. 4344 */ 4345 if (!(flags & VMAP_BLOCK)) 4346 return aligned_vread_iter(iter, addr, count); 4347 4348 remains = count; 4349 4350 /* 4351 * Area is split into regions and tracked with vmap_block, read out 4352 * each region and zero fill the hole between regions. 4353 */ 4354 xa = addr_to_vb_xa((unsigned long) addr); 4355 vb = xa_load(xa, addr_to_vb_idx((unsigned long)addr)); 4356 if (!vb) 4357 goto finished_zero; 4358 4359 spin_lock(&vb->lock); 4360 if (bitmap_empty(vb->used_map, VMAP_BBMAP_BITS)) { 4361 spin_unlock(&vb->lock); 4362 goto finished_zero; 4363 } 4364 4365 for_each_set_bitrange(rs, re, vb->used_map, VMAP_BBMAP_BITS) { 4366 size_t copied; 4367 4368 if (remains == 0) 4369 goto finished; 4370 4371 start = vmap_block_vaddr(vb->va->va_start, rs); 4372 4373 if (addr < start) { 4374 size_t to_zero = min_t(size_t, start - addr, remains); 4375 size_t zeroed = zero_iter(iter, to_zero); 4376 4377 addr += zeroed; 4378 remains -= zeroed; 4379 4380 if (remains == 0 || zeroed != to_zero) 4381 goto finished; 4382 } 4383 4384 /*it could start reading from the middle of used region*/ 4385 offset = offset_in_page(addr); 4386 n = ((re - rs + 1) << PAGE_SHIFT) - offset; 4387 if (n > remains) 4388 n = remains; 4389 4390 copied = aligned_vread_iter(iter, start + offset, n); 4391 4392 addr += copied; 4393 remains -= copied; 4394 4395 if (copied != n) 4396 goto finished; 4397 } 4398 4399 spin_unlock(&vb->lock); 4400 4401 finished_zero: 4402 /* zero-fill the left dirty or free regions */ 4403 return count - remains + zero_iter(iter, remains); 4404 finished: 4405 /* We couldn't copy/zero everything */ 4406 spin_unlock(&vb->lock); 4407 return count - remains; 4408 } 4409 4410 /** 4411 * vread_iter() - read vmalloc area in a safe way to an iterator. 4412 * @iter: the iterator to which data should be written. 4413 * @addr: vm address. 4414 * @count: number of bytes to be read. 4415 * 4416 * This function checks that addr is a valid vmalloc'ed area, and 4417 * copy data from that area to a given buffer. If the given memory range 4418 * of [addr...addr+count) includes some valid address, data is copied to 4419 * proper area of @buf. If there are memory holes, they'll be zero-filled. 4420 * IOREMAP area is treated as memory hole and no copy is done. 4421 * 4422 * If [addr...addr+count) doesn't includes any intersects with alive 4423 * vm_struct area, returns 0. @buf should be kernel's buffer. 4424 * 4425 * Note: In usual ops, vread() is never necessary because the caller 4426 * should know vmalloc() area is valid and can use memcpy(). 4427 * This is for routines which have to access vmalloc area without 4428 * any information, as /proc/kcore. 4429 * 4430 * Return: number of bytes for which addr and buf should be increased 4431 * (same number as @count) or %0 if [addr...addr+count) doesn't 4432 * include any intersection with valid vmalloc area 4433 */ 4434 long vread_iter(struct iov_iter *iter, const char *addr, size_t count) 4435 { 4436 struct vmap_node *vn; 4437 struct vmap_area *va; 4438 struct vm_struct *vm; 4439 char *vaddr; 4440 size_t n, size, flags, remains; 4441 unsigned long next; 4442 4443 addr = kasan_reset_tag(addr); 4444 4445 /* Don't allow overflow */ 4446 if ((unsigned long) addr + count < count) 4447 count = -(unsigned long) addr; 4448 4449 remains = count; 4450 4451 vn = find_vmap_area_exceed_addr_lock((unsigned long) addr, &va); 4452 if (!vn) 4453 goto finished_zero; 4454 4455 /* no intersects with alive vmap_area */ 4456 if ((unsigned long)addr + remains <= va->va_start) 4457 goto finished_zero; 4458 4459 do { 4460 size_t copied; 4461 4462 if (remains == 0) 4463 goto finished; 4464 4465 vm = va->vm; 4466 flags = va->flags & VMAP_FLAGS_MASK; 4467 /* 4468 * VMAP_BLOCK indicates a sub-type of vm_map_ram area, need 4469 * be set together with VMAP_RAM. 4470 */ 4471 WARN_ON(flags == VMAP_BLOCK); 4472 4473 if (!vm && !flags) 4474 goto next_va; 4475 4476 if (vm && (vm->flags & VM_UNINITIALIZED)) 4477 goto next_va; 4478 4479 /* Pair with smp_wmb() in clear_vm_uninitialized_flag() */ 4480 smp_rmb(); 4481 4482 vaddr = (char *) va->va_start; 4483 size = vm ? get_vm_area_size(vm) : va_size(va); 4484 4485 if (addr >= vaddr + size) 4486 goto next_va; 4487 4488 if (addr < vaddr) { 4489 size_t to_zero = min_t(size_t, vaddr - addr, remains); 4490 size_t zeroed = zero_iter(iter, to_zero); 4491 4492 addr += zeroed; 4493 remains -= zeroed; 4494 4495 if (remains == 0 || zeroed != to_zero) 4496 goto finished; 4497 } 4498 4499 n = vaddr + size - addr; 4500 if (n > remains) 4501 n = remains; 4502 4503 if (flags & VMAP_RAM) 4504 copied = vmap_ram_vread_iter(iter, addr, n, flags); 4505 else if (!(vm && (vm->flags & (VM_IOREMAP | VM_SPARSE)))) 4506 copied = aligned_vread_iter(iter, addr, n); 4507 else /* IOREMAP | SPARSE area is treated as memory hole */ 4508 copied = zero_iter(iter, n); 4509 4510 addr += copied; 4511 remains -= copied; 4512 4513 if (copied != n) 4514 goto finished; 4515 4516 next_va: 4517 next = va->va_end; 4518 spin_unlock(&vn->busy.lock); 4519 } while ((vn = find_vmap_area_exceed_addr_lock(next, &va))); 4520 4521 finished_zero: 4522 if (vn) 4523 spin_unlock(&vn->busy.lock); 4524 4525 /* zero-fill memory holes */ 4526 return count - remains + zero_iter(iter, remains); 4527 finished: 4528 /* Nothing remains, or We couldn't copy/zero everything. */ 4529 if (vn) 4530 spin_unlock(&vn->busy.lock); 4531 4532 return count - remains; 4533 } 4534 4535 /** 4536 * remap_vmalloc_range_partial - map vmalloc pages to userspace 4537 * @vma: vma to cover 4538 * @uaddr: target user address to start at 4539 * @kaddr: virtual address of vmalloc kernel memory 4540 * @pgoff: offset from @kaddr to start at 4541 * @size: size of map area 4542 * 4543 * Returns: 0 for success, -Exxx on failure 4544 * 4545 * This function checks that @kaddr is a valid vmalloc'ed area, 4546 * and that it is big enough to cover the range starting at 4547 * @uaddr in @vma. Will return failure if that criteria isn't 4548 * met. 4549 * 4550 * Similar to remap_pfn_range() (see mm/memory.c) 4551 */ 4552 int remap_vmalloc_range_partial(struct vm_area_struct *vma, unsigned long uaddr, 4553 void *kaddr, unsigned long pgoff, 4554 unsigned long size) 4555 { 4556 struct vm_struct *area; 4557 unsigned long off; 4558 unsigned long end_index; 4559 4560 if (check_shl_overflow(pgoff, PAGE_SHIFT, &off)) 4561 return -EINVAL; 4562 4563 size = PAGE_ALIGN(size); 4564 4565 if (!PAGE_ALIGNED(uaddr) || !PAGE_ALIGNED(kaddr)) 4566 return -EINVAL; 4567 4568 area = find_vm_area(kaddr); 4569 if (!area) 4570 return -EINVAL; 4571 4572 if (!(area->flags & (VM_USERMAP | VM_DMA_COHERENT))) 4573 return -EINVAL; 4574 4575 if (check_add_overflow(size, off, &end_index) || 4576 end_index > get_vm_area_size(area)) 4577 return -EINVAL; 4578 kaddr += off; 4579 4580 do { 4581 struct page *page = vmalloc_to_page(kaddr); 4582 int ret; 4583 4584 ret = vm_insert_page(vma, uaddr, page); 4585 if (ret) 4586 return ret; 4587 4588 uaddr += PAGE_SIZE; 4589 kaddr += PAGE_SIZE; 4590 size -= PAGE_SIZE; 4591 } while (size > 0); 4592 4593 vm_flags_set(vma, VM_DONTEXPAND | VM_DONTDUMP); 4594 4595 return 0; 4596 } 4597 4598 /** 4599 * remap_vmalloc_range - map vmalloc pages to userspace 4600 * @vma: vma to cover (map full range of vma) 4601 * @addr: vmalloc memory 4602 * @pgoff: number of pages into addr before first page to map 4603 * 4604 * Returns: 0 for success, -Exxx on failure 4605 * 4606 * This function checks that addr is a valid vmalloc'ed area, and 4607 * that it is big enough to cover the vma. Will return failure if 4608 * that criteria isn't met. 4609 * 4610 * Similar to remap_pfn_range() (see mm/memory.c) 4611 */ 4612 int remap_vmalloc_range(struct vm_area_struct *vma, void *addr, 4613 unsigned long pgoff) 4614 { 4615 return remap_vmalloc_range_partial(vma, vma->vm_start, 4616 addr, pgoff, 4617 vma->vm_end - vma->vm_start); 4618 } 4619 EXPORT_SYMBOL(remap_vmalloc_range); 4620 4621 void free_vm_area(struct vm_struct *area) 4622 { 4623 struct vm_struct *ret; 4624 ret = remove_vm_area(area->addr); 4625 BUG_ON(ret != area); 4626 kfree(area); 4627 } 4628 EXPORT_SYMBOL_GPL(free_vm_area); 4629 4630 #ifdef CONFIG_SMP 4631 static struct vmap_area *node_to_va(struct rb_node *n) 4632 { 4633 return rb_entry_safe(n, struct vmap_area, rb_node); 4634 } 4635 4636 /** 4637 * pvm_find_va_enclose_addr - find the vmap_area @addr belongs to 4638 * @addr: target address 4639 * 4640 * Returns: vmap_area if it is found. If there is no such area 4641 * the first highest(reverse order) vmap_area is returned 4642 * i.e. va->va_start < addr && va->va_end < addr or NULL 4643 * if there are no any areas before @addr. 4644 */ 4645 static struct vmap_area * 4646 pvm_find_va_enclose_addr(unsigned long addr) 4647 { 4648 struct vmap_area *va, *tmp; 4649 struct rb_node *n; 4650 4651 n = free_vmap_area_root.rb_node; 4652 va = NULL; 4653 4654 while (n) { 4655 tmp = rb_entry(n, struct vmap_area, rb_node); 4656 if (tmp->va_start <= addr) { 4657 va = tmp; 4658 if (tmp->va_end >= addr) 4659 break; 4660 4661 n = n->rb_right; 4662 } else { 4663 n = n->rb_left; 4664 } 4665 } 4666 4667 return va; 4668 } 4669 4670 /** 4671 * pvm_determine_end_from_reverse - find the highest aligned address 4672 * of free block below VMALLOC_END 4673 * @va: 4674 * in - the VA we start the search(reverse order); 4675 * out - the VA with the highest aligned end address. 4676 * @align: alignment for required highest address 4677 * 4678 * Returns: determined end address within vmap_area 4679 */ 4680 static unsigned long 4681 pvm_determine_end_from_reverse(struct vmap_area **va, unsigned long align) 4682 { 4683 unsigned long vmalloc_end = VMALLOC_END & ~(align - 1); 4684 unsigned long addr; 4685 4686 if (likely(*va)) { 4687 list_for_each_entry_from_reverse((*va), 4688 &free_vmap_area_list, list) { 4689 addr = min((*va)->va_end & ~(align - 1), vmalloc_end); 4690 if ((*va)->va_start < addr) 4691 return addr; 4692 } 4693 } 4694 4695 return 0; 4696 } 4697 4698 /** 4699 * pcpu_get_vm_areas - allocate vmalloc areas for percpu allocator 4700 * @offsets: array containing offset of each area 4701 * @sizes: array containing size of each area 4702 * @nr_vms: the number of areas to allocate 4703 * @align: alignment, all entries in @offsets and @sizes must be aligned to this 4704 * 4705 * Returns: kmalloc'd vm_struct pointer array pointing to allocated 4706 * vm_structs on success, %NULL on failure 4707 * 4708 * Percpu allocator wants to use congruent vm areas so that it can 4709 * maintain the offsets among percpu areas. This function allocates 4710 * congruent vmalloc areas for it with GFP_KERNEL. These areas tend to 4711 * be scattered pretty far, distance between two areas easily going up 4712 * to gigabytes. To avoid interacting with regular vmallocs, these 4713 * areas are allocated from top. 4714 * 4715 * Despite its complicated look, this allocator is rather simple. It 4716 * does everything top-down and scans free blocks from the end looking 4717 * for matching base. While scanning, if any of the areas do not fit the 4718 * base address is pulled down to fit the area. Scanning is repeated till 4719 * all the areas fit and then all necessary data structures are inserted 4720 * and the result is returned. 4721 */ 4722 struct vm_struct **pcpu_get_vm_areas(const unsigned long *offsets, 4723 const size_t *sizes, int nr_vms, 4724 size_t align) 4725 { 4726 const unsigned long vmalloc_start = ALIGN(VMALLOC_START, align); 4727 const unsigned long vmalloc_end = VMALLOC_END & ~(align - 1); 4728 struct vmap_area **vas, *va; 4729 struct vm_struct **vms; 4730 int area, area2, last_area, term_area; 4731 unsigned long base, start, size, end, last_end, orig_start, orig_end; 4732 bool purged = false; 4733 4734 /* verify parameters and allocate data structures */ 4735 BUG_ON(offset_in_page(align) || !is_power_of_2(align)); 4736 for (last_area = 0, area = 0; area < nr_vms; area++) { 4737 start = offsets[area]; 4738 end = start + sizes[area]; 4739 4740 /* is everything aligned properly? */ 4741 BUG_ON(!IS_ALIGNED(offsets[area], align)); 4742 BUG_ON(!IS_ALIGNED(sizes[area], align)); 4743 4744 /* detect the area with the highest address */ 4745 if (start > offsets[last_area]) 4746 last_area = area; 4747 4748 for (area2 = area + 1; area2 < nr_vms; area2++) { 4749 unsigned long start2 = offsets[area2]; 4750 unsigned long end2 = start2 + sizes[area2]; 4751 4752 BUG_ON(start2 < end && start < end2); 4753 } 4754 } 4755 last_end = offsets[last_area] + sizes[last_area]; 4756 4757 if (vmalloc_end - vmalloc_start < last_end) { 4758 WARN_ON(true); 4759 return NULL; 4760 } 4761 4762 vms = kcalloc(nr_vms, sizeof(vms[0]), GFP_KERNEL); 4763 vas = kcalloc(nr_vms, sizeof(vas[0]), GFP_KERNEL); 4764 if (!vas || !vms) 4765 goto err_free2; 4766 4767 for (area = 0; area < nr_vms; area++) { 4768 vas[area] = kmem_cache_zalloc(vmap_area_cachep, GFP_KERNEL); 4769 vms[area] = kzalloc(sizeof(struct vm_struct), GFP_KERNEL); 4770 if (!vas[area] || !vms[area]) 4771 goto err_free; 4772 } 4773 retry: 4774 spin_lock(&free_vmap_area_lock); 4775 4776 /* start scanning - we scan from the top, begin with the last area */ 4777 area = term_area = last_area; 4778 start = offsets[area]; 4779 end = start + sizes[area]; 4780 4781 va = pvm_find_va_enclose_addr(vmalloc_end); 4782 base = pvm_determine_end_from_reverse(&va, align) - end; 4783 4784 while (true) { 4785 /* 4786 * base might have underflowed, add last_end before 4787 * comparing. 4788 */ 4789 if (base + last_end < vmalloc_start + last_end) 4790 goto overflow; 4791 4792 /* 4793 * Fitting base has not been found. 4794 */ 4795 if (va == NULL) 4796 goto overflow; 4797 4798 /* 4799 * If required width exceeds current VA block, move 4800 * base downwards and then recheck. 4801 */ 4802 if (base + end > va->va_end) { 4803 base = pvm_determine_end_from_reverse(&va, align) - end; 4804 term_area = area; 4805 continue; 4806 } 4807 4808 /* 4809 * If this VA does not fit, move base downwards and recheck. 4810 */ 4811 if (base + start < va->va_start) { 4812 va = node_to_va(rb_prev(&va->rb_node)); 4813 base = pvm_determine_end_from_reverse(&va, align) - end; 4814 term_area = area; 4815 continue; 4816 } 4817 4818 /* 4819 * This area fits, move on to the previous one. If 4820 * the previous one is the terminal one, we're done. 4821 */ 4822 area = (area + nr_vms - 1) % nr_vms; 4823 if (area == term_area) 4824 break; 4825 4826 start = offsets[area]; 4827 end = start + sizes[area]; 4828 va = pvm_find_va_enclose_addr(base + end); 4829 } 4830 4831 /* we've found a fitting base, insert all va's */ 4832 for (area = 0; area < nr_vms; area++) { 4833 int ret; 4834 4835 start = base + offsets[area]; 4836 size = sizes[area]; 4837 4838 va = pvm_find_va_enclose_addr(start); 4839 if (WARN_ON_ONCE(va == NULL)) 4840 /* It is a BUG(), but trigger recovery instead. */ 4841 goto recovery; 4842 4843 ret = va_clip(&free_vmap_area_root, 4844 &free_vmap_area_list, va, start, size); 4845 if (WARN_ON_ONCE(unlikely(ret))) 4846 /* It is a BUG(), but trigger recovery instead. */ 4847 goto recovery; 4848 4849 /* Allocated area. */ 4850 va = vas[area]; 4851 va->va_start = start; 4852 va->va_end = start + size; 4853 } 4854 4855 spin_unlock(&free_vmap_area_lock); 4856 4857 /* populate the kasan shadow space */ 4858 for (area = 0; area < nr_vms; area++) { 4859 if (kasan_populate_vmalloc(vas[area]->va_start, sizes[area], GFP_KERNEL)) 4860 goto err_free_shadow; 4861 } 4862 4863 /* insert all vm's */ 4864 for (area = 0; area < nr_vms; area++) { 4865 struct vmap_node *vn = addr_to_node(vas[area]->va_start); 4866 4867 spin_lock(&vn->busy.lock); 4868 insert_vmap_area(vas[area], &vn->busy.root, &vn->busy.head); 4869 setup_vmalloc_vm(vms[area], vas[area], VM_ALLOC, 4870 pcpu_get_vm_areas); 4871 spin_unlock(&vn->busy.lock); 4872 } 4873 4874 /* 4875 * Mark allocated areas as accessible. Do it now as a best-effort 4876 * approach, as they can be mapped outside of vmalloc code. 4877 * With hardware tag-based KASAN, marking is skipped for 4878 * non-VM_ALLOC mappings, see __kasan_unpoison_vmalloc(). 4879 */ 4880 kasan_unpoison_vmap_areas(vms, nr_vms, KASAN_VMALLOC_PROT_NORMAL); 4881 4882 kfree(vas); 4883 return vms; 4884 4885 recovery: 4886 /* 4887 * Remove previously allocated areas. There is no 4888 * need in removing these areas from the busy tree, 4889 * because they are inserted only on the final step 4890 * and when pcpu_get_vm_areas() is success. 4891 */ 4892 while (area--) { 4893 orig_start = vas[area]->va_start; 4894 orig_end = vas[area]->va_end; 4895 va = merge_or_add_vmap_area_augment(vas[area], &free_vmap_area_root, 4896 &free_vmap_area_list); 4897 if (va) 4898 kasan_release_vmalloc(orig_start, orig_end, 4899 va->va_start, va->va_end, 4900 KASAN_VMALLOC_PAGE_RANGE | KASAN_VMALLOC_TLB_FLUSH); 4901 vas[area] = NULL; 4902 } 4903 4904 overflow: 4905 spin_unlock(&free_vmap_area_lock); 4906 if (!purged) { 4907 reclaim_and_purge_vmap_areas(); 4908 purged = true; 4909 4910 /* Before "retry", check if we recover. */ 4911 for (area = 0; area < nr_vms; area++) { 4912 if (vas[area]) 4913 continue; 4914 4915 vas[area] = kmem_cache_zalloc( 4916 vmap_area_cachep, GFP_KERNEL); 4917 if (!vas[area]) 4918 goto err_free; 4919 } 4920 4921 goto retry; 4922 } 4923 4924 err_free: 4925 for (area = 0; area < nr_vms; area++) { 4926 if (vas[area]) 4927 kmem_cache_free(vmap_area_cachep, vas[area]); 4928 4929 kfree(vms[area]); 4930 } 4931 err_free2: 4932 kfree(vas); 4933 kfree(vms); 4934 return NULL; 4935 4936 err_free_shadow: 4937 spin_lock(&free_vmap_area_lock); 4938 /* 4939 * We release all the vmalloc shadows, even the ones for regions that 4940 * hadn't been successfully added. This relies on kasan_release_vmalloc 4941 * being able to tolerate this case. 4942 */ 4943 for (area = 0; area < nr_vms; area++) { 4944 orig_start = vas[area]->va_start; 4945 orig_end = vas[area]->va_end; 4946 va = merge_or_add_vmap_area_augment(vas[area], &free_vmap_area_root, 4947 &free_vmap_area_list); 4948 if (va) 4949 kasan_release_vmalloc(orig_start, orig_end, 4950 va->va_start, va->va_end, 4951 KASAN_VMALLOC_PAGE_RANGE | KASAN_VMALLOC_TLB_FLUSH); 4952 vas[area] = NULL; 4953 kfree(vms[area]); 4954 } 4955 spin_unlock(&free_vmap_area_lock); 4956 kfree(vas); 4957 kfree(vms); 4958 return NULL; 4959 } 4960 4961 /** 4962 * pcpu_free_vm_areas - free vmalloc areas for percpu allocator 4963 * @vms: vm_struct pointer array returned by pcpu_get_vm_areas() 4964 * @nr_vms: the number of allocated areas 4965 * 4966 * Free vm_structs and the array allocated by pcpu_get_vm_areas(). 4967 */ 4968 void pcpu_free_vm_areas(struct vm_struct **vms, int nr_vms) 4969 { 4970 int i; 4971 4972 for (i = 0; i < nr_vms; i++) 4973 free_vm_area(vms[i]); 4974 kfree(vms); 4975 } 4976 #endif /* CONFIG_SMP */ 4977 4978 #ifdef CONFIG_PRINTK 4979 bool vmalloc_dump_obj(void *object) 4980 { 4981 const void *caller; 4982 struct vm_struct *vm; 4983 struct vmap_area *va; 4984 struct vmap_node *vn; 4985 unsigned long addr; 4986 unsigned int nr_pages; 4987 4988 addr = PAGE_ALIGN((unsigned long) object); 4989 vn = addr_to_node(addr); 4990 4991 if (!spin_trylock(&vn->busy.lock)) 4992 return false; 4993 4994 va = __find_vmap_area(addr, &vn->busy.root); 4995 if (!va || !va->vm) { 4996 spin_unlock(&vn->busy.lock); 4997 return false; 4998 } 4999 5000 vm = va->vm; 5001 addr = (unsigned long) vm->addr; 5002 caller = vm->caller; 5003 nr_pages = vm->nr_pages; 5004 spin_unlock(&vn->busy.lock); 5005 5006 pr_cont(" %u-page vmalloc region starting at %#lx allocated at %pS\n", 5007 nr_pages, addr, caller); 5008 5009 return true; 5010 } 5011 #endif 5012 5013 #ifdef CONFIG_PROC_FS 5014 5015 /* 5016 * Print number of pages allocated on each memory node. 5017 * 5018 * This function can only be called if CONFIG_NUMA is enabled 5019 * and VM_UNINITIALIZED bit in v->flags is disabled. 5020 */ 5021 static void show_numa_info(struct seq_file *m, struct vm_struct *v, 5022 unsigned int *counters) 5023 { 5024 unsigned int nr; 5025 unsigned int step = 1U << vm_area_page_order(v); 5026 5027 if (!counters) 5028 return; 5029 5030 memset(counters, 0, nr_node_ids * sizeof(unsigned int)); 5031 5032 for (nr = 0; nr < v->nr_pages; nr += step) 5033 counters[page_to_nid(v->pages[nr])] += step; 5034 for_each_node_state(nr, N_HIGH_MEMORY) 5035 if (counters[nr]) 5036 seq_printf(m, " N%u=%u", nr, counters[nr]); 5037 } 5038 5039 static void show_purge_info(struct seq_file *m) 5040 { 5041 struct vmap_node *vn; 5042 struct vmap_area *va; 5043 5044 for_each_vmap_node(vn) { 5045 spin_lock(&vn->lazy.lock); 5046 list_for_each_entry(va, &vn->lazy.head, list) { 5047 seq_printf(m, "0x%pK-0x%pK %7ld unpurged vm_area\n", 5048 (void *)va->va_start, (void *)va->va_end, 5049 va_size(va)); 5050 } 5051 spin_unlock(&vn->lazy.lock); 5052 } 5053 } 5054 5055 static int vmalloc_info_show(struct seq_file *m, void *p) 5056 { 5057 struct vmap_node *vn; 5058 struct vmap_area *va; 5059 struct vm_struct *v; 5060 unsigned int *counters; 5061 5062 if (IS_ENABLED(CONFIG_NUMA)) 5063 counters = kmalloc(nr_node_ids * sizeof(unsigned int), GFP_KERNEL); 5064 5065 for_each_vmap_node(vn) { 5066 spin_lock(&vn->busy.lock); 5067 list_for_each_entry(va, &vn->busy.head, list) { 5068 if (!va->vm) { 5069 if (va->flags & VMAP_RAM) 5070 seq_printf(m, "0x%pK-0x%pK %7ld vm_map_ram\n", 5071 (void *)va->va_start, (void *)va->va_end, 5072 va_size(va)); 5073 5074 continue; 5075 } 5076 5077 v = va->vm; 5078 if (v->flags & VM_UNINITIALIZED) 5079 continue; 5080 5081 /* Pair with smp_wmb() in clear_vm_uninitialized_flag() */ 5082 smp_rmb(); 5083 5084 seq_printf(m, "0x%pK-0x%pK %7ld", 5085 v->addr, v->addr + v->size, v->size); 5086 5087 if (v->caller) 5088 seq_printf(m, " %pS", v->caller); 5089 5090 if (v->nr_pages) 5091 seq_printf(m, " pages=%d", v->nr_pages); 5092 5093 if (v->phys_addr) 5094 seq_printf(m, " phys=%pa", &v->phys_addr); 5095 5096 if (v->flags & VM_IOREMAP) 5097 seq_puts(m, " ioremap"); 5098 5099 if (v->flags & VM_SPARSE) 5100 seq_puts(m, " sparse"); 5101 5102 if (v->flags & VM_ALLOC) 5103 seq_puts(m, " vmalloc"); 5104 5105 if (v->flags & VM_MAP) 5106 seq_puts(m, " vmap"); 5107 5108 if (v->flags & VM_USERMAP) 5109 seq_puts(m, " user"); 5110 5111 if (v->flags & VM_DMA_COHERENT) 5112 seq_puts(m, " dma-coherent"); 5113 5114 if (is_vmalloc_addr(v->pages)) 5115 seq_puts(m, " vpages"); 5116 5117 if (IS_ENABLED(CONFIG_NUMA)) 5118 show_numa_info(m, v, counters); 5119 5120 seq_putc(m, '\n'); 5121 } 5122 spin_unlock(&vn->busy.lock); 5123 } 5124 5125 /* 5126 * As a final step, dump "unpurged" areas. 5127 */ 5128 show_purge_info(m); 5129 if (IS_ENABLED(CONFIG_NUMA)) 5130 kfree(counters); 5131 return 0; 5132 } 5133 5134 static int __init proc_vmalloc_init(void) 5135 { 5136 proc_create_single("vmallocinfo", 0400, NULL, vmalloc_info_show); 5137 return 0; 5138 } 5139 module_init(proc_vmalloc_init); 5140 5141 #endif 5142 5143 static void __init vmap_init_free_space(void) 5144 { 5145 unsigned long vmap_start = 1; 5146 const unsigned long vmap_end = ULONG_MAX; 5147 struct vmap_area *free; 5148 struct vm_struct *busy; 5149 5150 /* 5151 * B F B B B F 5152 * -|-----|.....|-----|-----|-----|.....|- 5153 * | The KVA space | 5154 * |<--------------------------------->| 5155 */ 5156 for (busy = vmlist; busy; busy = busy->next) { 5157 if ((unsigned long) busy->addr - vmap_start > 0) { 5158 free = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT); 5159 if (!WARN_ON_ONCE(!free)) { 5160 free->va_start = vmap_start; 5161 free->va_end = (unsigned long) busy->addr; 5162 5163 insert_vmap_area_augment(free, NULL, 5164 &free_vmap_area_root, 5165 &free_vmap_area_list); 5166 } 5167 } 5168 5169 vmap_start = (unsigned long) busy->addr + busy->size; 5170 } 5171 5172 if (vmap_end - vmap_start > 0) { 5173 free = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT); 5174 if (!WARN_ON_ONCE(!free)) { 5175 free->va_start = vmap_start; 5176 free->va_end = vmap_end; 5177 5178 insert_vmap_area_augment(free, NULL, 5179 &free_vmap_area_root, 5180 &free_vmap_area_list); 5181 } 5182 } 5183 } 5184 5185 static void vmap_init_nodes(void) 5186 { 5187 struct vmap_node *vn; 5188 int i; 5189 5190 #if BITS_PER_LONG == 64 5191 /* 5192 * A high threshold of max nodes is fixed and bound to 128, 5193 * thus a scale factor is 1 for systems where number of cores 5194 * are less or equal to specified threshold. 5195 * 5196 * As for NUMA-aware notes. For bigger systems, for example 5197 * NUMA with multi-sockets, where we can end-up with thousands 5198 * of cores in total, a "sub-numa-clustering" should be added. 5199 * 5200 * In this case a NUMA domain is considered as a single entity 5201 * with dedicated sub-nodes in it which describe one group or 5202 * set of cores. Therefore a per-domain purging is supposed to 5203 * be added as well as a per-domain balancing. 5204 */ 5205 int n = clamp_t(unsigned int, num_possible_cpus(), 1, 128); 5206 5207 if (n > 1) { 5208 vn = kmalloc_array(n, sizeof(*vn), GFP_NOWAIT); 5209 if (vn) { 5210 /* Node partition is 16 pages. */ 5211 vmap_zone_size = (1 << 4) * PAGE_SIZE; 5212 nr_vmap_nodes = n; 5213 vmap_nodes = vn; 5214 } else { 5215 pr_err("Failed to allocate an array. Disable a node layer\n"); 5216 } 5217 } 5218 #endif 5219 5220 for_each_vmap_node(vn) { 5221 vn->busy.root = RB_ROOT; 5222 INIT_LIST_HEAD(&vn->busy.head); 5223 spin_lock_init(&vn->busy.lock); 5224 5225 vn->lazy.root = RB_ROOT; 5226 INIT_LIST_HEAD(&vn->lazy.head); 5227 spin_lock_init(&vn->lazy.lock); 5228 5229 for (i = 0; i < MAX_VA_SIZE_PAGES; i++) { 5230 INIT_LIST_HEAD(&vn->pool[i].head); 5231 WRITE_ONCE(vn->pool[i].len, 0); 5232 } 5233 5234 spin_lock_init(&vn->pool_lock); 5235 } 5236 } 5237 5238 static unsigned long 5239 vmap_node_shrink_count(struct shrinker *shrink, struct shrink_control *sc) 5240 { 5241 unsigned long count = 0; 5242 struct vmap_node *vn; 5243 int i; 5244 5245 for_each_vmap_node(vn) { 5246 for (i = 0; i < MAX_VA_SIZE_PAGES; i++) 5247 count += READ_ONCE(vn->pool[i].len); 5248 } 5249 5250 return count ? count : SHRINK_EMPTY; 5251 } 5252 5253 static unsigned long 5254 vmap_node_shrink_scan(struct shrinker *shrink, struct shrink_control *sc) 5255 { 5256 struct vmap_node *vn; 5257 5258 guard(mutex)(&vmap_purge_lock); 5259 for_each_vmap_node(vn) 5260 decay_va_pool_node(vn, true); 5261 5262 return SHRINK_STOP; 5263 } 5264 5265 void __init vmalloc_init(void) 5266 { 5267 struct shrinker *vmap_node_shrinker; 5268 struct vmap_area *va; 5269 struct vmap_node *vn; 5270 struct vm_struct *tmp; 5271 int i; 5272 5273 /* 5274 * Create the cache for vmap_area objects. 5275 */ 5276 vmap_area_cachep = KMEM_CACHE(vmap_area, SLAB_PANIC); 5277 5278 for_each_possible_cpu(i) { 5279 struct vmap_block_queue *vbq; 5280 struct vfree_deferred *p; 5281 5282 vbq = &per_cpu(vmap_block_queue, i); 5283 spin_lock_init(&vbq->lock); 5284 INIT_LIST_HEAD(&vbq->free); 5285 p = &per_cpu(vfree_deferred, i); 5286 init_llist_head(&p->list); 5287 INIT_WORK(&p->wq, delayed_vfree_work); 5288 xa_init(&vbq->vmap_blocks); 5289 } 5290 5291 /* 5292 * Setup nodes before importing vmlist. 5293 */ 5294 vmap_init_nodes(); 5295 5296 /* Import existing vmlist entries. */ 5297 for (tmp = vmlist; tmp; tmp = tmp->next) { 5298 va = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT); 5299 if (WARN_ON_ONCE(!va)) 5300 continue; 5301 5302 va->va_start = (unsigned long)tmp->addr; 5303 va->va_end = va->va_start + tmp->size; 5304 va->vm = tmp; 5305 5306 vn = addr_to_node(va->va_start); 5307 insert_vmap_area(va, &vn->busy.root, &vn->busy.head); 5308 } 5309 5310 /* 5311 * Now we can initialize a free vmap space. 5312 */ 5313 vmap_init_free_space(); 5314 vmap_initialized = true; 5315 5316 vmap_node_shrinker = shrinker_alloc(0, "vmap-node"); 5317 if (!vmap_node_shrinker) { 5318 pr_err("Failed to allocate vmap-node shrinker!\n"); 5319 return; 5320 } 5321 5322 vmap_node_shrinker->count_objects = vmap_node_shrink_count; 5323 vmap_node_shrinker->scan_objects = vmap_node_shrink_scan; 5324 shrinker_register(vmap_node_shrinker); 5325 }