1 /* 2 * linux/mm/vmalloc.c 3 * 4 * Copyright (C) 1993 Linus Torvalds 5 * Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999 6 * SMP-safe vmalloc/vfree/ioremap, Tigran Aivazian <tigran@veritas.com>, May 2000 7 * Major rework to support vmap/vunmap, Christoph Hellwig, SGI, August 2002 8 * Numa awareness, Christoph Lameter, SGI, June 2005 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.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/debugobjects.h> 22 #include <linux/kallsyms.h> 23 #include <linux/list.h> 24 #include <linux/rbtree.h> 25 #include <linux/radix-tree.h> 26 #include <linux/rcupdate.h> 27 #include <linux/pfn.h> 28 #include <linux/kmemleak.h> 29 #include <linux/atomic.h> 30 #include <linux/llist.h> 31 #include <asm/uaccess.h> 32 #include <asm/tlbflush.h> 33 #include <asm/shmparam.h> 34 35 struct vfree_deferred { 36 struct llist_head list; 37 struct work_struct wq; 38 }; 39 static DEFINE_PER_CPU(struct vfree_deferred, vfree_deferred); 40 41 static void __vunmap(const void *, int); 42 43 static void free_work(struct work_struct *w) 44 { 45 struct vfree_deferred *p = container_of(w, struct vfree_deferred, wq); 46 struct llist_node *llnode = llist_del_all(&p->list); 47 while (llnode) { 48 void *p = llnode; 49 llnode = llist_next(llnode); 50 __vunmap(p, 1); 51 } 52 } 53 54 /*** Page table manipulation functions ***/ 55 56 static void vunmap_pte_range(pmd_t *pmd, unsigned long addr, unsigned long end) 57 { 58 pte_t *pte; 59 60 pte = pte_offset_kernel(pmd, addr); 61 do { 62 pte_t ptent = ptep_get_and_clear(&init_mm, addr, pte); 63 WARN_ON(!pte_none(ptent) && !pte_present(ptent)); 64 } while (pte++, addr += PAGE_SIZE, addr != end); 65 } 66 67 static void vunmap_pmd_range(pud_t *pud, unsigned long addr, unsigned long end) 68 { 69 pmd_t *pmd; 70 unsigned long next; 71 72 pmd = pmd_offset(pud, addr); 73 do { 74 next = pmd_addr_end(addr, end); 75 if (pmd_none_or_clear_bad(pmd)) 76 continue; 77 vunmap_pte_range(pmd, addr, next); 78 } while (pmd++, addr = next, addr != end); 79 } 80 81 static void vunmap_pud_range(pgd_t *pgd, unsigned long addr, unsigned long end) 82 { 83 pud_t *pud; 84 unsigned long next; 85 86 pud = pud_offset(pgd, addr); 87 do { 88 next = pud_addr_end(addr, end); 89 if (pud_none_or_clear_bad(pud)) 90 continue; 91 vunmap_pmd_range(pud, addr, next); 92 } while (pud++, addr = next, addr != end); 93 } 94 95 static void vunmap_page_range(unsigned long addr, unsigned long end) 96 { 97 pgd_t *pgd; 98 unsigned long next; 99 100 BUG_ON(addr >= end); 101 pgd = pgd_offset_k(addr); 102 do { 103 next = pgd_addr_end(addr, end); 104 if (pgd_none_or_clear_bad(pgd)) 105 continue; 106 vunmap_pud_range(pgd, addr, next); 107 } while (pgd++, addr = next, addr != end); 108 } 109 110 static int vmap_pte_range(pmd_t *pmd, unsigned long addr, 111 unsigned long end, pgprot_t prot, struct page **pages, int *nr) 112 { 113 pte_t *pte; 114 115 /* 116 * nr is a running index into the array which helps higher level 117 * callers keep track of where we're up to. 118 */ 119 120 pte = pte_alloc_kernel(pmd, addr); 121 if (!pte) 122 return -ENOMEM; 123 do { 124 struct page *page = pages[*nr]; 125 126 if (WARN_ON(!pte_none(*pte))) 127 return -EBUSY; 128 if (WARN_ON(!page)) 129 return -ENOMEM; 130 set_pte_at(&init_mm, addr, pte, mk_pte(page, prot)); 131 (*nr)++; 132 } while (pte++, addr += PAGE_SIZE, addr != end); 133 return 0; 134 } 135 136 static int vmap_pmd_range(pud_t *pud, unsigned long addr, 137 unsigned long end, pgprot_t prot, struct page **pages, int *nr) 138 { 139 pmd_t *pmd; 140 unsigned long next; 141 142 pmd = pmd_alloc(&init_mm, pud, addr); 143 if (!pmd) 144 return -ENOMEM; 145 do { 146 next = pmd_addr_end(addr, end); 147 if (vmap_pte_range(pmd, addr, next, prot, pages, nr)) 148 return -ENOMEM; 149 } while (pmd++, addr = next, addr != end); 150 return 0; 151 } 152 153 static int vmap_pud_range(pgd_t *pgd, unsigned long addr, 154 unsigned long end, pgprot_t prot, struct page **pages, int *nr) 155 { 156 pud_t *pud; 157 unsigned long next; 158 159 pud = pud_alloc(&init_mm, pgd, addr); 160 if (!pud) 161 return -ENOMEM; 162 do { 163 next = pud_addr_end(addr, end); 164 if (vmap_pmd_range(pud, addr, next, prot, pages, nr)) 165 return -ENOMEM; 166 } while (pud++, addr = next, addr != end); 167 return 0; 168 } 169 170 /* 171 * Set up page tables in kva (addr, end). The ptes shall have prot "prot", and 172 * will have pfns corresponding to the "pages" array. 173 * 174 * Ie. pte at addr+N*PAGE_SIZE shall point to pfn corresponding to pages[N] 175 */ 176 static int vmap_page_range_noflush(unsigned long start, unsigned long end, 177 pgprot_t prot, struct page **pages) 178 { 179 pgd_t *pgd; 180 unsigned long next; 181 unsigned long addr = start; 182 int err = 0; 183 int nr = 0; 184 185 BUG_ON(addr >= end); 186 pgd = pgd_offset_k(addr); 187 do { 188 next = pgd_addr_end(addr, end); 189 err = vmap_pud_range(pgd, addr, next, prot, pages, &nr); 190 if (err) 191 return err; 192 } while (pgd++, addr = next, addr != end); 193 194 return nr; 195 } 196 197 static int vmap_page_range(unsigned long start, unsigned long end, 198 pgprot_t prot, struct page **pages) 199 { 200 int ret; 201 202 ret = vmap_page_range_noflush(start, end, prot, pages); 203 flush_cache_vmap(start, end); 204 return ret; 205 } 206 207 int is_vmalloc_or_module_addr(const void *x) 208 { 209 /* 210 * ARM, x86-64 and sparc64 put modules in a special place, 211 * and fall back on vmalloc() if that fails. Others 212 * just put it in the vmalloc space. 213 */ 214 #if defined(CONFIG_MODULES) && defined(MODULES_VADDR) 215 unsigned long addr = (unsigned long)x; 216 if (addr >= MODULES_VADDR && addr < MODULES_END) 217 return 1; 218 #endif 219 return is_vmalloc_addr(x); 220 } 221 222 /* 223 * Walk a vmap address to the struct page it maps. 224 */ 225 struct page *vmalloc_to_page(const void *vmalloc_addr) 226 { 227 unsigned long addr = (unsigned long) vmalloc_addr; 228 struct page *page = NULL; 229 pgd_t *pgd = pgd_offset_k(addr); 230 231 /* 232 * XXX we might need to change this if we add VIRTUAL_BUG_ON for 233 * architectures that do not vmalloc module space 234 */ 235 VIRTUAL_BUG_ON(!is_vmalloc_or_module_addr(vmalloc_addr)); 236 237 if (!pgd_none(*pgd)) { 238 pud_t *pud = pud_offset(pgd, addr); 239 if (!pud_none(*pud)) { 240 pmd_t *pmd = pmd_offset(pud, addr); 241 if (!pmd_none(*pmd)) { 242 pte_t *ptep, pte; 243 244 ptep = pte_offset_map(pmd, addr); 245 pte = *ptep; 246 if (pte_present(pte)) 247 page = pte_page(pte); 248 pte_unmap(ptep); 249 } 250 } 251 } 252 return page; 253 } 254 EXPORT_SYMBOL(vmalloc_to_page); 255 256 /* 257 * Map a vmalloc()-space virtual address to the physical page frame number. 258 */ 259 unsigned long vmalloc_to_pfn(const void *vmalloc_addr) 260 { 261 return page_to_pfn(vmalloc_to_page(vmalloc_addr)); 262 } 263 EXPORT_SYMBOL(vmalloc_to_pfn); 264 265 266 /*** Global kva allocator ***/ 267 268 #define VM_LAZY_FREE 0x01 269 #define VM_LAZY_FREEING 0x02 270 #define VM_VM_AREA 0x04 271 272 static DEFINE_SPINLOCK(vmap_area_lock); 273 /* Export for kexec only */ 274 LIST_HEAD(vmap_area_list); 275 static struct rb_root vmap_area_root = RB_ROOT; 276 277 /* The vmap cache globals are protected by vmap_area_lock */ 278 static struct rb_node *free_vmap_cache; 279 static unsigned long cached_hole_size; 280 static unsigned long cached_vstart; 281 static unsigned long cached_align; 282 283 static unsigned long vmap_area_pcpu_hole; 284 285 static struct vmap_area *__find_vmap_area(unsigned long addr) 286 { 287 struct rb_node *n = vmap_area_root.rb_node; 288 289 while (n) { 290 struct vmap_area *va; 291 292 va = rb_entry(n, struct vmap_area, rb_node); 293 if (addr < va->va_start) 294 n = n->rb_left; 295 else if (addr > va->va_start) 296 n = n->rb_right; 297 else 298 return va; 299 } 300 301 return NULL; 302 } 303 304 static void __insert_vmap_area(struct vmap_area *va) 305 { 306 struct rb_node **p = &vmap_area_root.rb_node; 307 struct rb_node *parent = NULL; 308 struct rb_node *tmp; 309 310 while (*p) { 311 struct vmap_area *tmp_va; 312 313 parent = *p; 314 tmp_va = rb_entry(parent, struct vmap_area, rb_node); 315 if (va->va_start < tmp_va->va_end) 316 p = &(*p)->rb_left; 317 else if (va->va_end > tmp_va->va_start) 318 p = &(*p)->rb_right; 319 else 320 BUG(); 321 } 322 323 rb_link_node(&va->rb_node, parent, p); 324 rb_insert_color(&va->rb_node, &vmap_area_root); 325 326 /* address-sort this list */ 327 tmp = rb_prev(&va->rb_node); 328 if (tmp) { 329 struct vmap_area *prev; 330 prev = rb_entry(tmp, struct vmap_area, rb_node); 331 list_add_rcu(&va->list, &prev->list); 332 } else 333 list_add_rcu(&va->list, &vmap_area_list); 334 } 335 336 static void purge_vmap_area_lazy(void); 337 338 /* 339 * Allocate a region of KVA of the specified size and alignment, within the 340 * vstart and vend. 341 */ 342 static struct vmap_area *alloc_vmap_area(unsigned long size, 343 unsigned long align, 344 unsigned long vstart, unsigned long vend, 345 int node, gfp_t gfp_mask) 346 { 347 struct vmap_area *va; 348 struct rb_node *n; 349 unsigned long addr; 350 int purged = 0; 351 struct vmap_area *first; 352 353 BUG_ON(!size); 354 BUG_ON(size & ~PAGE_MASK); 355 BUG_ON(!is_power_of_2(align)); 356 357 va = kmalloc_node(sizeof(struct vmap_area), 358 gfp_mask & GFP_RECLAIM_MASK, node); 359 if (unlikely(!va)) 360 return ERR_PTR(-ENOMEM); 361 362 retry: 363 spin_lock(&vmap_area_lock); 364 /* 365 * Invalidate cache if we have more permissive parameters. 366 * cached_hole_size notes the largest hole noticed _below_ 367 * the vmap_area cached in free_vmap_cache: if size fits 368 * into that hole, we want to scan from vstart to reuse 369 * the hole instead of allocating above free_vmap_cache. 370 * Note that __free_vmap_area may update free_vmap_cache 371 * without updating cached_hole_size or cached_align. 372 */ 373 if (!free_vmap_cache || 374 size < cached_hole_size || 375 vstart < cached_vstart || 376 align < cached_align) { 377 nocache: 378 cached_hole_size = 0; 379 free_vmap_cache = NULL; 380 } 381 /* record if we encounter less permissive parameters */ 382 cached_vstart = vstart; 383 cached_align = align; 384 385 /* find starting point for our search */ 386 if (free_vmap_cache) { 387 first = rb_entry(free_vmap_cache, struct vmap_area, rb_node); 388 addr = ALIGN(first->va_end, align); 389 if (addr < vstart) 390 goto nocache; 391 if (addr + size - 1 < addr) 392 goto overflow; 393 394 } else { 395 addr = ALIGN(vstart, align); 396 if (addr + size - 1 < addr) 397 goto overflow; 398 399 n = vmap_area_root.rb_node; 400 first = NULL; 401 402 while (n) { 403 struct vmap_area *tmp; 404 tmp = rb_entry(n, struct vmap_area, rb_node); 405 if (tmp->va_end >= addr) { 406 first = tmp; 407 if (tmp->va_start <= addr) 408 break; 409 n = n->rb_left; 410 } else 411 n = n->rb_right; 412 } 413 414 if (!first) 415 goto found; 416 } 417 418 /* from the starting point, walk areas until a suitable hole is found */ 419 while (addr + size > first->va_start && addr + size <= vend) { 420 if (addr + cached_hole_size < first->va_start) 421 cached_hole_size = first->va_start - addr; 422 addr = ALIGN(first->va_end, align); 423 if (addr + size - 1 < addr) 424 goto overflow; 425 426 if (list_is_last(&first->list, &vmap_area_list)) 427 goto found; 428 429 first = list_entry(first->list.next, 430 struct vmap_area, list); 431 } 432 433 found: 434 if (addr + size > vend) 435 goto overflow; 436 437 va->va_start = addr; 438 va->va_end = addr + size; 439 va->flags = 0; 440 __insert_vmap_area(va); 441 free_vmap_cache = &va->rb_node; 442 spin_unlock(&vmap_area_lock); 443 444 BUG_ON(va->va_start & (align-1)); 445 BUG_ON(va->va_start < vstart); 446 BUG_ON(va->va_end > vend); 447 448 return va; 449 450 overflow: 451 spin_unlock(&vmap_area_lock); 452 if (!purged) { 453 purge_vmap_area_lazy(); 454 purged = 1; 455 goto retry; 456 } 457 if (printk_ratelimit()) 458 printk(KERN_WARNING 459 "vmap allocation for size %lu failed: " 460 "use vmalloc=<size> to increase size.\n", size); 461 kfree(va); 462 return ERR_PTR(-EBUSY); 463 } 464 465 static void __free_vmap_area(struct vmap_area *va) 466 { 467 BUG_ON(RB_EMPTY_NODE(&va->rb_node)); 468 469 if (free_vmap_cache) { 470 if (va->va_end < cached_vstart) { 471 free_vmap_cache = NULL; 472 } else { 473 struct vmap_area *cache; 474 cache = rb_entry(free_vmap_cache, struct vmap_area, rb_node); 475 if (va->va_start <= cache->va_start) { 476 free_vmap_cache = rb_prev(&va->rb_node); 477 /* 478 * We don't try to update cached_hole_size or 479 * cached_align, but it won't go very wrong. 480 */ 481 } 482 } 483 } 484 rb_erase(&va->rb_node, &vmap_area_root); 485 RB_CLEAR_NODE(&va->rb_node); 486 list_del_rcu(&va->list); 487 488 /* 489 * Track the highest possible candidate for pcpu area 490 * allocation. Areas outside of vmalloc area can be returned 491 * here too, consider only end addresses which fall inside 492 * vmalloc area proper. 493 */ 494 if (va->va_end > VMALLOC_START && va->va_end <= VMALLOC_END) 495 vmap_area_pcpu_hole = max(vmap_area_pcpu_hole, va->va_end); 496 497 kfree_rcu(va, rcu_head); 498 } 499 500 /* 501 * Free a region of KVA allocated by alloc_vmap_area 502 */ 503 static void free_vmap_area(struct vmap_area *va) 504 { 505 spin_lock(&vmap_area_lock); 506 __free_vmap_area(va); 507 spin_unlock(&vmap_area_lock); 508 } 509 510 /* 511 * Clear the pagetable entries of a given vmap_area 512 */ 513 static void unmap_vmap_area(struct vmap_area *va) 514 { 515 vunmap_page_range(va->va_start, va->va_end); 516 } 517 518 static void vmap_debug_free_range(unsigned long start, unsigned long end) 519 { 520 /* 521 * Unmap page tables and force a TLB flush immediately if 522 * CONFIG_DEBUG_PAGEALLOC is set. This catches use after free 523 * bugs similarly to those in linear kernel virtual address 524 * space after a page has been freed. 525 * 526 * All the lazy freeing logic is still retained, in order to 527 * minimise intrusiveness of this debugging feature. 528 * 529 * This is going to be *slow* (linear kernel virtual address 530 * debugging doesn't do a broadcast TLB flush so it is a lot 531 * faster). 532 */ 533 #ifdef CONFIG_DEBUG_PAGEALLOC 534 vunmap_page_range(start, end); 535 flush_tlb_kernel_range(start, end); 536 #endif 537 } 538 539 /* 540 * lazy_max_pages is the maximum amount of virtual address space we gather up 541 * before attempting to purge with a TLB flush. 542 * 543 * There is a tradeoff here: a larger number will cover more kernel page tables 544 * and take slightly longer to purge, but it will linearly reduce the number of 545 * global TLB flushes that must be performed. It would seem natural to scale 546 * this number up linearly with the number of CPUs (because vmapping activity 547 * could also scale linearly with the number of CPUs), however it is likely 548 * that in practice, workloads might be constrained in other ways that mean 549 * vmap activity will not scale linearly with CPUs. Also, I want to be 550 * conservative and not introduce a big latency on huge systems, so go with 551 * a less aggressive log scale. It will still be an improvement over the old 552 * code, and it will be simple to change the scale factor if we find that it 553 * becomes a problem on bigger systems. 554 */ 555 static unsigned long lazy_max_pages(void) 556 { 557 unsigned int log; 558 559 log = fls(num_online_cpus()); 560 561 return log * (32UL * 1024 * 1024 / PAGE_SIZE); 562 } 563 564 static atomic_t vmap_lazy_nr = ATOMIC_INIT(0); 565 566 /* for per-CPU blocks */ 567 static void purge_fragmented_blocks_allcpus(void); 568 569 /* 570 * called before a call to iounmap() if the caller wants vm_area_struct's 571 * immediately freed. 572 */ 573 void set_iounmap_nonlazy(void) 574 { 575 atomic_set(&vmap_lazy_nr, lazy_max_pages()+1); 576 } 577 578 /* 579 * Purges all lazily-freed vmap areas. 580 * 581 * If sync is 0 then don't purge if there is already a purge in progress. 582 * If force_flush is 1, then flush kernel TLBs between *start and *end even 583 * if we found no lazy vmap areas to unmap (callers can use this to optimise 584 * their own TLB flushing). 585 * Returns with *start = min(*start, lowest purged address) 586 * *end = max(*end, highest purged address) 587 */ 588 static void __purge_vmap_area_lazy(unsigned long *start, unsigned long *end, 589 int sync, int force_flush) 590 { 591 static DEFINE_SPINLOCK(purge_lock); 592 LIST_HEAD(valist); 593 struct vmap_area *va; 594 struct vmap_area *n_va; 595 int nr = 0; 596 597 /* 598 * If sync is 0 but force_flush is 1, we'll go sync anyway but callers 599 * should not expect such behaviour. This just simplifies locking for 600 * the case that isn't actually used at the moment anyway. 601 */ 602 if (!sync && !force_flush) { 603 if (!spin_trylock(&purge_lock)) 604 return; 605 } else 606 spin_lock(&purge_lock); 607 608 if (sync) 609 purge_fragmented_blocks_allcpus(); 610 611 rcu_read_lock(); 612 list_for_each_entry_rcu(va, &vmap_area_list, list) { 613 if (va->flags & VM_LAZY_FREE) { 614 if (va->va_start < *start) 615 *start = va->va_start; 616 if (va->va_end > *end) 617 *end = va->va_end; 618 nr += (va->va_end - va->va_start) >> PAGE_SHIFT; 619 list_add_tail(&va->purge_list, &valist); 620 va->flags |= VM_LAZY_FREEING; 621 va->flags &= ~VM_LAZY_FREE; 622 } 623 } 624 rcu_read_unlock(); 625 626 if (nr) 627 atomic_sub(nr, &vmap_lazy_nr); 628 629 if (nr || force_flush) 630 flush_tlb_kernel_range(*start, *end); 631 632 if (nr) { 633 spin_lock(&vmap_area_lock); 634 list_for_each_entry_safe(va, n_va, &valist, purge_list) 635 __free_vmap_area(va); 636 spin_unlock(&vmap_area_lock); 637 } 638 spin_unlock(&purge_lock); 639 } 640 641 /* 642 * Kick off a purge of the outstanding lazy areas. Don't bother if somebody 643 * is already purging. 644 */ 645 static void try_purge_vmap_area_lazy(void) 646 { 647 unsigned long start = ULONG_MAX, end = 0; 648 649 __purge_vmap_area_lazy(&start, &end, 0, 0); 650 } 651 652 /* 653 * Kick off a purge of the outstanding lazy areas. 654 */ 655 static void purge_vmap_area_lazy(void) 656 { 657 unsigned long start = ULONG_MAX, end = 0; 658 659 __purge_vmap_area_lazy(&start, &end, 1, 0); 660 } 661 662 /* 663 * Free a vmap area, caller ensuring that the area has been unmapped 664 * and flush_cache_vunmap had been called for the correct range 665 * previously. 666 */ 667 static void free_vmap_area_noflush(struct vmap_area *va) 668 { 669 va->flags |= VM_LAZY_FREE; 670 atomic_add((va->va_end - va->va_start) >> PAGE_SHIFT, &vmap_lazy_nr); 671 if (unlikely(atomic_read(&vmap_lazy_nr) > lazy_max_pages())) 672 try_purge_vmap_area_lazy(); 673 } 674 675 /* 676 * Free and unmap a vmap area, caller ensuring flush_cache_vunmap had been 677 * called for the correct range previously. 678 */ 679 static void free_unmap_vmap_area_noflush(struct vmap_area *va) 680 { 681 unmap_vmap_area(va); 682 free_vmap_area_noflush(va); 683 } 684 685 /* 686 * Free and unmap a vmap area 687 */ 688 static void free_unmap_vmap_area(struct vmap_area *va) 689 { 690 flush_cache_vunmap(va->va_start, va->va_end); 691 free_unmap_vmap_area_noflush(va); 692 } 693 694 static struct vmap_area *find_vmap_area(unsigned long addr) 695 { 696 struct vmap_area *va; 697 698 spin_lock(&vmap_area_lock); 699 va = __find_vmap_area(addr); 700 spin_unlock(&vmap_area_lock); 701 702 return va; 703 } 704 705 static void free_unmap_vmap_area_addr(unsigned long addr) 706 { 707 struct vmap_area *va; 708 709 va = find_vmap_area(addr); 710 BUG_ON(!va); 711 free_unmap_vmap_area(va); 712 } 713 714 715 /*** Per cpu kva allocator ***/ 716 717 /* 718 * vmap space is limited especially on 32 bit architectures. Ensure there is 719 * room for at least 16 percpu vmap blocks per CPU. 720 */ 721 /* 722 * If we had a constant VMALLOC_START and VMALLOC_END, we'd like to be able 723 * to #define VMALLOC_SPACE (VMALLOC_END-VMALLOC_START). Guess 724 * instead (we just need a rough idea) 725 */ 726 #if BITS_PER_LONG == 32 727 #define VMALLOC_SPACE (128UL*1024*1024) 728 #else 729 #define VMALLOC_SPACE (128UL*1024*1024*1024) 730 #endif 731 732 #define VMALLOC_PAGES (VMALLOC_SPACE / PAGE_SIZE) 733 #define VMAP_MAX_ALLOC BITS_PER_LONG /* 256K with 4K pages */ 734 #define VMAP_BBMAP_BITS_MAX 1024 /* 4MB with 4K pages */ 735 #define VMAP_BBMAP_BITS_MIN (VMAP_MAX_ALLOC*2) 736 #define VMAP_MIN(x, y) ((x) < (y) ? (x) : (y)) /* can't use min() */ 737 #define VMAP_MAX(x, y) ((x) > (y) ? (x) : (y)) /* can't use max() */ 738 #define VMAP_BBMAP_BITS \ 739 VMAP_MIN(VMAP_BBMAP_BITS_MAX, \ 740 VMAP_MAX(VMAP_BBMAP_BITS_MIN, \ 741 VMALLOC_PAGES / roundup_pow_of_two(NR_CPUS) / 16)) 742 743 #define VMAP_BLOCK_SIZE (VMAP_BBMAP_BITS * PAGE_SIZE) 744 745 static bool vmap_initialized __read_mostly = false; 746 747 struct vmap_block_queue { 748 spinlock_t lock; 749 struct list_head free; 750 }; 751 752 struct vmap_block { 753 spinlock_t lock; 754 struct vmap_area *va; 755 struct vmap_block_queue *vbq; 756 unsigned long free, dirty; 757 DECLARE_BITMAP(alloc_map, VMAP_BBMAP_BITS); 758 DECLARE_BITMAP(dirty_map, VMAP_BBMAP_BITS); 759 struct list_head free_list; 760 struct rcu_head rcu_head; 761 struct list_head purge; 762 }; 763 764 /* Queue of free and dirty vmap blocks, for allocation and flushing purposes */ 765 static DEFINE_PER_CPU(struct vmap_block_queue, vmap_block_queue); 766 767 /* 768 * Radix tree of vmap blocks, indexed by address, to quickly find a vmap block 769 * in the free path. Could get rid of this if we change the API to return a 770 * "cookie" from alloc, to be passed to free. But no big deal yet. 771 */ 772 static DEFINE_SPINLOCK(vmap_block_tree_lock); 773 static RADIX_TREE(vmap_block_tree, GFP_ATOMIC); 774 775 /* 776 * We should probably have a fallback mechanism to allocate virtual memory 777 * out of partially filled vmap blocks. However vmap block sizing should be 778 * fairly reasonable according to the vmalloc size, so it shouldn't be a 779 * big problem. 780 */ 781 782 static unsigned long addr_to_vb_idx(unsigned long addr) 783 { 784 addr -= VMALLOC_START & ~(VMAP_BLOCK_SIZE-1); 785 addr /= VMAP_BLOCK_SIZE; 786 return addr; 787 } 788 789 static struct vmap_block *new_vmap_block(gfp_t gfp_mask) 790 { 791 struct vmap_block_queue *vbq; 792 struct vmap_block *vb; 793 struct vmap_area *va; 794 unsigned long vb_idx; 795 int node, err; 796 797 node = numa_node_id(); 798 799 vb = kmalloc_node(sizeof(struct vmap_block), 800 gfp_mask & GFP_RECLAIM_MASK, node); 801 if (unlikely(!vb)) 802 return ERR_PTR(-ENOMEM); 803 804 va = alloc_vmap_area(VMAP_BLOCK_SIZE, VMAP_BLOCK_SIZE, 805 VMALLOC_START, VMALLOC_END, 806 node, gfp_mask); 807 if (IS_ERR(va)) { 808 kfree(vb); 809 return ERR_CAST(va); 810 } 811 812 err = radix_tree_preload(gfp_mask); 813 if (unlikely(err)) { 814 kfree(vb); 815 free_vmap_area(va); 816 return ERR_PTR(err); 817 } 818 819 spin_lock_init(&vb->lock); 820 vb->va = va; 821 vb->free = VMAP_BBMAP_BITS; 822 vb->dirty = 0; 823 bitmap_zero(vb->alloc_map, VMAP_BBMAP_BITS); 824 bitmap_zero(vb->dirty_map, VMAP_BBMAP_BITS); 825 INIT_LIST_HEAD(&vb->free_list); 826 827 vb_idx = addr_to_vb_idx(va->va_start); 828 spin_lock(&vmap_block_tree_lock); 829 err = radix_tree_insert(&vmap_block_tree, vb_idx, vb); 830 spin_unlock(&vmap_block_tree_lock); 831 BUG_ON(err); 832 radix_tree_preload_end(); 833 834 vbq = &get_cpu_var(vmap_block_queue); 835 vb->vbq = vbq; 836 spin_lock(&vbq->lock); 837 list_add_rcu(&vb->free_list, &vbq->free); 838 spin_unlock(&vbq->lock); 839 put_cpu_var(vmap_block_queue); 840 841 return vb; 842 } 843 844 static void free_vmap_block(struct vmap_block *vb) 845 { 846 struct vmap_block *tmp; 847 unsigned long vb_idx; 848 849 vb_idx = addr_to_vb_idx(vb->va->va_start); 850 spin_lock(&vmap_block_tree_lock); 851 tmp = radix_tree_delete(&vmap_block_tree, vb_idx); 852 spin_unlock(&vmap_block_tree_lock); 853 BUG_ON(tmp != vb); 854 855 free_vmap_area_noflush(vb->va); 856 kfree_rcu(vb, rcu_head); 857 } 858 859 static void purge_fragmented_blocks(int cpu) 860 { 861 LIST_HEAD(purge); 862 struct vmap_block *vb; 863 struct vmap_block *n_vb; 864 struct vmap_block_queue *vbq = &per_cpu(vmap_block_queue, cpu); 865 866 rcu_read_lock(); 867 list_for_each_entry_rcu(vb, &vbq->free, free_list) { 868 869 if (!(vb->free + vb->dirty == VMAP_BBMAP_BITS && vb->dirty != VMAP_BBMAP_BITS)) 870 continue; 871 872 spin_lock(&vb->lock); 873 if (vb->free + vb->dirty == VMAP_BBMAP_BITS && vb->dirty != VMAP_BBMAP_BITS) { 874 vb->free = 0; /* prevent further allocs after releasing lock */ 875 vb->dirty = VMAP_BBMAP_BITS; /* prevent purging it again */ 876 bitmap_fill(vb->alloc_map, VMAP_BBMAP_BITS); 877 bitmap_fill(vb->dirty_map, VMAP_BBMAP_BITS); 878 spin_lock(&vbq->lock); 879 list_del_rcu(&vb->free_list); 880 spin_unlock(&vbq->lock); 881 spin_unlock(&vb->lock); 882 list_add_tail(&vb->purge, &purge); 883 } else 884 spin_unlock(&vb->lock); 885 } 886 rcu_read_unlock(); 887 888 list_for_each_entry_safe(vb, n_vb, &purge, purge) { 889 list_del(&vb->purge); 890 free_vmap_block(vb); 891 } 892 } 893 894 static void purge_fragmented_blocks_thiscpu(void) 895 { 896 purge_fragmented_blocks(smp_processor_id()); 897 } 898 899 static void purge_fragmented_blocks_allcpus(void) 900 { 901 int cpu; 902 903 for_each_possible_cpu(cpu) 904 purge_fragmented_blocks(cpu); 905 } 906 907 static void *vb_alloc(unsigned long size, gfp_t gfp_mask) 908 { 909 struct vmap_block_queue *vbq; 910 struct vmap_block *vb; 911 unsigned long addr = 0; 912 unsigned int order; 913 int purge = 0; 914 915 BUG_ON(size & ~PAGE_MASK); 916 BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC); 917 if (WARN_ON(size == 0)) { 918 /* 919 * Allocating 0 bytes isn't what caller wants since 920 * get_order(0) returns funny result. Just warn and terminate 921 * early. 922 */ 923 return NULL; 924 } 925 order = get_order(size); 926 927 again: 928 rcu_read_lock(); 929 vbq = &get_cpu_var(vmap_block_queue); 930 list_for_each_entry_rcu(vb, &vbq->free, free_list) { 931 int i; 932 933 spin_lock(&vb->lock); 934 if (vb->free < 1UL << order) 935 goto next; 936 937 i = bitmap_find_free_region(vb->alloc_map, 938 VMAP_BBMAP_BITS, order); 939 940 if (i < 0) { 941 if (vb->free + vb->dirty == VMAP_BBMAP_BITS) { 942 /* fragmented and no outstanding allocations */ 943 BUG_ON(vb->dirty != VMAP_BBMAP_BITS); 944 purge = 1; 945 } 946 goto next; 947 } 948 addr = vb->va->va_start + (i << PAGE_SHIFT); 949 BUG_ON(addr_to_vb_idx(addr) != 950 addr_to_vb_idx(vb->va->va_start)); 951 vb->free -= 1UL << order; 952 if (vb->free == 0) { 953 spin_lock(&vbq->lock); 954 list_del_rcu(&vb->free_list); 955 spin_unlock(&vbq->lock); 956 } 957 spin_unlock(&vb->lock); 958 break; 959 next: 960 spin_unlock(&vb->lock); 961 } 962 963 if (purge) 964 purge_fragmented_blocks_thiscpu(); 965 966 put_cpu_var(vmap_block_queue); 967 rcu_read_unlock(); 968 969 if (!addr) { 970 vb = new_vmap_block(gfp_mask); 971 if (IS_ERR(vb)) 972 return vb; 973 goto again; 974 } 975 976 return (void *)addr; 977 } 978 979 static void vb_free(const void *addr, unsigned long size) 980 { 981 unsigned long offset; 982 unsigned long vb_idx; 983 unsigned int order; 984 struct vmap_block *vb; 985 986 BUG_ON(size & ~PAGE_MASK); 987 BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC); 988 989 flush_cache_vunmap((unsigned long)addr, (unsigned long)addr + size); 990 991 order = get_order(size); 992 993 offset = (unsigned long)addr & (VMAP_BLOCK_SIZE - 1); 994 995 vb_idx = addr_to_vb_idx((unsigned long)addr); 996 rcu_read_lock(); 997 vb = radix_tree_lookup(&vmap_block_tree, vb_idx); 998 rcu_read_unlock(); 999 BUG_ON(!vb); 1000 1001 vunmap_page_range((unsigned long)addr, (unsigned long)addr + size); 1002 1003 spin_lock(&vb->lock); 1004 BUG_ON(bitmap_allocate_region(vb->dirty_map, offset >> PAGE_SHIFT, order)); 1005 1006 vb->dirty += 1UL << order; 1007 if (vb->dirty == VMAP_BBMAP_BITS) { 1008 BUG_ON(vb->free); 1009 spin_unlock(&vb->lock); 1010 free_vmap_block(vb); 1011 } else 1012 spin_unlock(&vb->lock); 1013 } 1014 1015 /** 1016 * vm_unmap_aliases - unmap outstanding lazy aliases in the vmap layer 1017 * 1018 * The vmap/vmalloc layer lazily flushes kernel virtual mappings primarily 1019 * to amortize TLB flushing overheads. What this means is that any page you 1020 * have now, may, in a former life, have been mapped into kernel virtual 1021 * address by the vmap layer and so there might be some CPUs with TLB entries 1022 * still referencing that page (additional to the regular 1:1 kernel mapping). 1023 * 1024 * vm_unmap_aliases flushes all such lazy mappings. After it returns, we can 1025 * be sure that none of the pages we have control over will have any aliases 1026 * from the vmap layer. 1027 */ 1028 void vm_unmap_aliases(void) 1029 { 1030 unsigned long start = ULONG_MAX, end = 0; 1031 int cpu; 1032 int flush = 0; 1033 1034 if (unlikely(!vmap_initialized)) 1035 return; 1036 1037 for_each_possible_cpu(cpu) { 1038 struct vmap_block_queue *vbq = &per_cpu(vmap_block_queue, cpu); 1039 struct vmap_block *vb; 1040 1041 rcu_read_lock(); 1042 list_for_each_entry_rcu(vb, &vbq->free, free_list) { 1043 int i; 1044 1045 spin_lock(&vb->lock); 1046 i = find_first_bit(vb->dirty_map, VMAP_BBMAP_BITS); 1047 while (i < VMAP_BBMAP_BITS) { 1048 unsigned long s, e; 1049 int j; 1050 j = find_next_zero_bit(vb->dirty_map, 1051 VMAP_BBMAP_BITS, i); 1052 1053 s = vb->va->va_start + (i << PAGE_SHIFT); 1054 e = vb->va->va_start + (j << PAGE_SHIFT); 1055 flush = 1; 1056 1057 if (s < start) 1058 start = s; 1059 if (e > end) 1060 end = e; 1061 1062 i = j; 1063 i = find_next_bit(vb->dirty_map, 1064 VMAP_BBMAP_BITS, i); 1065 } 1066 spin_unlock(&vb->lock); 1067 } 1068 rcu_read_unlock(); 1069 } 1070 1071 __purge_vmap_area_lazy(&start, &end, 1, flush); 1072 } 1073 EXPORT_SYMBOL_GPL(vm_unmap_aliases); 1074 1075 /** 1076 * vm_unmap_ram - unmap linear kernel address space set up by vm_map_ram 1077 * @mem: the pointer returned by vm_map_ram 1078 * @count: the count passed to that vm_map_ram call (cannot unmap partial) 1079 */ 1080 void vm_unmap_ram(const void *mem, unsigned int count) 1081 { 1082 unsigned long size = count << PAGE_SHIFT; 1083 unsigned long addr = (unsigned long)mem; 1084 1085 BUG_ON(!addr); 1086 BUG_ON(addr < VMALLOC_START); 1087 BUG_ON(addr > VMALLOC_END); 1088 BUG_ON(addr & (PAGE_SIZE-1)); 1089 1090 debug_check_no_locks_freed(mem, size); 1091 vmap_debug_free_range(addr, addr+size); 1092 1093 if (likely(count <= VMAP_MAX_ALLOC)) 1094 vb_free(mem, size); 1095 else 1096 free_unmap_vmap_area_addr(addr); 1097 } 1098 EXPORT_SYMBOL(vm_unmap_ram); 1099 1100 /** 1101 * vm_map_ram - map pages linearly into kernel virtual address (vmalloc space) 1102 * @pages: an array of pointers to the pages to be mapped 1103 * @count: number of pages 1104 * @node: prefer to allocate data structures on this node 1105 * @prot: memory protection to use. PAGE_KERNEL for regular RAM 1106 * 1107 * Returns: a pointer to the address that has been mapped, or %NULL on failure 1108 */ 1109 void *vm_map_ram(struct page **pages, unsigned int count, int node, pgprot_t prot) 1110 { 1111 unsigned long size = count << PAGE_SHIFT; 1112 unsigned long addr; 1113 void *mem; 1114 1115 if (likely(count <= VMAP_MAX_ALLOC)) { 1116 mem = vb_alloc(size, GFP_KERNEL); 1117 if (IS_ERR(mem)) 1118 return NULL; 1119 addr = (unsigned long)mem; 1120 } else { 1121 struct vmap_area *va; 1122 va = alloc_vmap_area(size, PAGE_SIZE, 1123 VMALLOC_START, VMALLOC_END, node, GFP_KERNEL); 1124 if (IS_ERR(va)) 1125 return NULL; 1126 1127 addr = va->va_start; 1128 mem = (void *)addr; 1129 } 1130 if (vmap_page_range(addr, addr + size, prot, pages) < 0) { 1131 vm_unmap_ram(mem, count); 1132 return NULL; 1133 } 1134 return mem; 1135 } 1136 EXPORT_SYMBOL(vm_map_ram); 1137 1138 static struct vm_struct *vmlist __initdata; 1139 /** 1140 * vm_area_add_early - add vmap area early during boot 1141 * @vm: vm_struct to add 1142 * 1143 * This function is used to add fixed kernel vm area to vmlist before 1144 * vmalloc_init() is called. @vm->addr, @vm->size, and @vm->flags 1145 * should contain proper values and the other fields should be zero. 1146 * 1147 * DO NOT USE THIS FUNCTION UNLESS YOU KNOW WHAT YOU'RE DOING. 1148 */ 1149 void __init vm_area_add_early(struct vm_struct *vm) 1150 { 1151 struct vm_struct *tmp, **p; 1152 1153 BUG_ON(vmap_initialized); 1154 for (p = &vmlist; (tmp = *p) != NULL; p = &tmp->next) { 1155 if (tmp->addr >= vm->addr) { 1156 BUG_ON(tmp->addr < vm->addr + vm->size); 1157 break; 1158 } else 1159 BUG_ON(tmp->addr + tmp->size > vm->addr); 1160 } 1161 vm->next = *p; 1162 *p = vm; 1163 } 1164 1165 /** 1166 * vm_area_register_early - register vmap area early during boot 1167 * @vm: vm_struct to register 1168 * @align: requested alignment 1169 * 1170 * This function is used to register kernel vm area before 1171 * vmalloc_init() is called. @vm->size and @vm->flags should contain 1172 * proper values on entry and other fields should be zero. On return, 1173 * vm->addr contains the allocated address. 1174 * 1175 * DO NOT USE THIS FUNCTION UNLESS YOU KNOW WHAT YOU'RE DOING. 1176 */ 1177 void __init vm_area_register_early(struct vm_struct *vm, size_t align) 1178 { 1179 static size_t vm_init_off __initdata; 1180 unsigned long addr; 1181 1182 addr = ALIGN(VMALLOC_START + vm_init_off, align); 1183 vm_init_off = PFN_ALIGN(addr + vm->size) - VMALLOC_START; 1184 1185 vm->addr = (void *)addr; 1186 1187 vm_area_add_early(vm); 1188 } 1189 1190 void __init vmalloc_init(void) 1191 { 1192 struct vmap_area *va; 1193 struct vm_struct *tmp; 1194 int i; 1195 1196 for_each_possible_cpu(i) { 1197 struct vmap_block_queue *vbq; 1198 struct vfree_deferred *p; 1199 1200 vbq = &per_cpu(vmap_block_queue, i); 1201 spin_lock_init(&vbq->lock); 1202 INIT_LIST_HEAD(&vbq->free); 1203 p = &per_cpu(vfree_deferred, i); 1204 init_llist_head(&p->list); 1205 INIT_WORK(&p->wq, free_work); 1206 } 1207 1208 /* Import existing vmlist entries. */ 1209 for (tmp = vmlist; tmp; tmp = tmp->next) { 1210 va = kzalloc(sizeof(struct vmap_area), GFP_NOWAIT); 1211 va->flags = VM_VM_AREA; 1212 va->va_start = (unsigned long)tmp->addr; 1213 va->va_end = va->va_start + tmp->size; 1214 va->vm = tmp; 1215 __insert_vmap_area(va); 1216 } 1217 1218 vmap_area_pcpu_hole = VMALLOC_END; 1219 1220 vmap_initialized = true; 1221 } 1222 1223 /** 1224 * map_kernel_range_noflush - map kernel VM area with the specified pages 1225 * @addr: start of the VM area to map 1226 * @size: size of the VM area to map 1227 * @prot: page protection flags to use 1228 * @pages: pages to map 1229 * 1230 * Map PFN_UP(@size) pages at @addr. The VM area @addr and @size 1231 * specify should have been allocated using get_vm_area() and its 1232 * friends. 1233 * 1234 * NOTE: 1235 * This function does NOT do any cache flushing. The caller is 1236 * responsible for calling flush_cache_vmap() on to-be-mapped areas 1237 * before calling this function. 1238 * 1239 * RETURNS: 1240 * The number of pages mapped on success, -errno on failure. 1241 */ 1242 int map_kernel_range_noflush(unsigned long addr, unsigned long size, 1243 pgprot_t prot, struct page **pages) 1244 { 1245 return vmap_page_range_noflush(addr, addr + size, prot, pages); 1246 } 1247 1248 /** 1249 * unmap_kernel_range_noflush - unmap kernel VM area 1250 * @addr: start of the VM area to unmap 1251 * @size: size of the VM area to unmap 1252 * 1253 * Unmap PFN_UP(@size) pages at @addr. The VM area @addr and @size 1254 * specify should have been allocated using get_vm_area() and its 1255 * friends. 1256 * 1257 * NOTE: 1258 * This function does NOT do any cache flushing. The caller is 1259 * responsible for calling flush_cache_vunmap() on to-be-mapped areas 1260 * before calling this function and flush_tlb_kernel_range() after. 1261 */ 1262 void unmap_kernel_range_noflush(unsigned long addr, unsigned long size) 1263 { 1264 vunmap_page_range(addr, addr + size); 1265 } 1266 EXPORT_SYMBOL_GPL(unmap_kernel_range_noflush); 1267 1268 /** 1269 * unmap_kernel_range - unmap kernel VM area and flush cache and TLB 1270 * @addr: start of the VM area to unmap 1271 * @size: size of the VM area to unmap 1272 * 1273 * Similar to unmap_kernel_range_noflush() but flushes vcache before 1274 * the unmapping and tlb after. 1275 */ 1276 void unmap_kernel_range(unsigned long addr, unsigned long size) 1277 { 1278 unsigned long end = addr + size; 1279 1280 flush_cache_vunmap(addr, end); 1281 vunmap_page_range(addr, end); 1282 flush_tlb_kernel_range(addr, end); 1283 } 1284 1285 int map_vm_area(struct vm_struct *area, pgprot_t prot, struct page ***pages) 1286 { 1287 unsigned long addr = (unsigned long)area->addr; 1288 unsigned long end = addr + area->size - PAGE_SIZE; 1289 int err; 1290 1291 err = vmap_page_range(addr, end, prot, *pages); 1292 if (err > 0) { 1293 *pages += err; 1294 err = 0; 1295 } 1296 1297 return err; 1298 } 1299 EXPORT_SYMBOL_GPL(map_vm_area); 1300 1301 static void setup_vmalloc_vm(struct vm_struct *vm, struct vmap_area *va, 1302 unsigned long flags, const void *caller) 1303 { 1304 spin_lock(&vmap_area_lock); 1305 vm->flags = flags; 1306 vm->addr = (void *)va->va_start; 1307 vm->size = va->va_end - va->va_start; 1308 vm->caller = caller; 1309 va->vm = vm; 1310 va->flags |= VM_VM_AREA; 1311 spin_unlock(&vmap_area_lock); 1312 } 1313 1314 static void clear_vm_unlist(struct vm_struct *vm) 1315 { 1316 /* 1317 * Before removing VM_UNLIST, 1318 * we should make sure that vm has proper values. 1319 * Pair with smp_rmb() in show_numa_info(). 1320 */ 1321 smp_wmb(); 1322 vm->flags &= ~VM_UNLIST; 1323 } 1324 1325 static void insert_vmalloc_vm(struct vm_struct *vm, struct vmap_area *va, 1326 unsigned long flags, const void *caller) 1327 { 1328 setup_vmalloc_vm(vm, va, flags, caller); 1329 clear_vm_unlist(vm); 1330 } 1331 1332 static struct vm_struct *__get_vm_area_node(unsigned long size, 1333 unsigned long align, unsigned long flags, unsigned long start, 1334 unsigned long end, int node, gfp_t gfp_mask, const void *caller) 1335 { 1336 struct vmap_area *va; 1337 struct vm_struct *area; 1338 1339 BUG_ON(in_interrupt()); 1340 if (flags & VM_IOREMAP) { 1341 int bit = fls(size); 1342 1343 if (bit > IOREMAP_MAX_ORDER) 1344 bit = IOREMAP_MAX_ORDER; 1345 else if (bit < PAGE_SHIFT) 1346 bit = PAGE_SHIFT; 1347 1348 align = 1ul << bit; 1349 } 1350 1351 size = PAGE_ALIGN(size); 1352 if (unlikely(!size)) 1353 return NULL; 1354 1355 area = kzalloc_node(sizeof(*area), gfp_mask & GFP_RECLAIM_MASK, node); 1356 if (unlikely(!area)) 1357 return NULL; 1358 1359 /* 1360 * We always allocate a guard page. 1361 */ 1362 size += PAGE_SIZE; 1363 1364 va = alloc_vmap_area(size, align, start, end, node, gfp_mask); 1365 if (IS_ERR(va)) { 1366 kfree(area); 1367 return NULL; 1368 } 1369 1370 /* 1371 * When this function is called from __vmalloc_node_range, 1372 * we add VM_UNLIST flag to avoid accessing uninitialized 1373 * members of vm_struct such as pages and nr_pages fields. 1374 * They will be set later. 1375 */ 1376 if (flags & VM_UNLIST) 1377 setup_vmalloc_vm(area, va, flags, caller); 1378 else 1379 insert_vmalloc_vm(area, va, flags, caller); 1380 1381 return area; 1382 } 1383 1384 struct vm_struct *__get_vm_area(unsigned long size, unsigned long flags, 1385 unsigned long start, unsigned long end) 1386 { 1387 return __get_vm_area_node(size, 1, flags, start, end, NUMA_NO_NODE, 1388 GFP_KERNEL, __builtin_return_address(0)); 1389 } 1390 EXPORT_SYMBOL_GPL(__get_vm_area); 1391 1392 struct vm_struct *__get_vm_area_caller(unsigned long size, unsigned long flags, 1393 unsigned long start, unsigned long end, 1394 const void *caller) 1395 { 1396 return __get_vm_area_node(size, 1, flags, start, end, NUMA_NO_NODE, 1397 GFP_KERNEL, caller); 1398 } 1399 1400 /** 1401 * get_vm_area - reserve a contiguous kernel virtual area 1402 * @size: size of the area 1403 * @flags: %VM_IOREMAP for I/O mappings or VM_ALLOC 1404 * 1405 * Search an area of @size in the kernel virtual mapping area, 1406 * and reserved it for out purposes. Returns the area descriptor 1407 * on success or %NULL on failure. 1408 */ 1409 struct vm_struct *get_vm_area(unsigned long size, unsigned long flags) 1410 { 1411 return __get_vm_area_node(size, 1, flags, VMALLOC_START, VMALLOC_END, 1412 NUMA_NO_NODE, GFP_KERNEL, 1413 __builtin_return_address(0)); 1414 } 1415 1416 struct vm_struct *get_vm_area_caller(unsigned long size, unsigned long flags, 1417 const void *caller) 1418 { 1419 return __get_vm_area_node(size, 1, flags, VMALLOC_START, VMALLOC_END, 1420 NUMA_NO_NODE, GFP_KERNEL, caller); 1421 } 1422 1423 /** 1424 * find_vm_area - find a continuous kernel virtual area 1425 * @addr: base address 1426 * 1427 * Search for the kernel VM area starting at @addr, and return it. 1428 * It is up to the caller to do all required locking to keep the returned 1429 * pointer valid. 1430 */ 1431 struct vm_struct *find_vm_area(const void *addr) 1432 { 1433 struct vmap_area *va; 1434 1435 va = find_vmap_area((unsigned long)addr); 1436 if (va && va->flags & VM_VM_AREA) 1437 return va->vm; 1438 1439 return NULL; 1440 } 1441 1442 /** 1443 * remove_vm_area - find and remove a continuous kernel virtual area 1444 * @addr: base address 1445 * 1446 * Search for the kernel VM area starting at @addr, and remove it. 1447 * This function returns the found VM area, but using it is NOT safe 1448 * on SMP machines, except for its size or flags. 1449 */ 1450 struct vm_struct *remove_vm_area(const void *addr) 1451 { 1452 struct vmap_area *va; 1453 1454 va = find_vmap_area((unsigned long)addr); 1455 if (va && va->flags & VM_VM_AREA) { 1456 struct vm_struct *vm = va->vm; 1457 1458 spin_lock(&vmap_area_lock); 1459 va->vm = NULL; 1460 va->flags &= ~VM_VM_AREA; 1461 spin_unlock(&vmap_area_lock); 1462 1463 vmap_debug_free_range(va->va_start, va->va_end); 1464 free_unmap_vmap_area(va); 1465 vm->size -= PAGE_SIZE; 1466 1467 return vm; 1468 } 1469 return NULL; 1470 } 1471 1472 static void __vunmap(const void *addr, int deallocate_pages) 1473 { 1474 struct vm_struct *area; 1475 1476 if (!addr) 1477 return; 1478 1479 if ((PAGE_SIZE-1) & (unsigned long)addr) { 1480 WARN(1, KERN_ERR "Trying to vfree() bad address (%p)\n", addr); 1481 return; 1482 } 1483 1484 area = remove_vm_area(addr); 1485 if (unlikely(!area)) { 1486 WARN(1, KERN_ERR "Trying to vfree() nonexistent vm area (%p)\n", 1487 addr); 1488 return; 1489 } 1490 1491 debug_check_no_locks_freed(addr, area->size); 1492 debug_check_no_obj_freed(addr, area->size); 1493 1494 if (deallocate_pages) { 1495 int i; 1496 1497 for (i = 0; i < area->nr_pages; i++) { 1498 struct page *page = area->pages[i]; 1499 1500 BUG_ON(!page); 1501 __free_page(page); 1502 } 1503 1504 if (area->flags & VM_VPAGES) 1505 vfree(area->pages); 1506 else 1507 kfree(area->pages); 1508 } 1509 1510 kfree(area); 1511 return; 1512 } 1513 1514 /** 1515 * vfree - release memory allocated by vmalloc() 1516 * @addr: memory base address 1517 * 1518 * Free the virtually continuous memory area starting at @addr, as 1519 * obtained from vmalloc(), vmalloc_32() or __vmalloc(). If @addr is 1520 * NULL, no operation is performed. 1521 * 1522 * Must not be called in NMI context (strictly speaking, only if we don't 1523 * have CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG, but making the calling 1524 * conventions for vfree() arch-depenedent would be a really bad idea) 1525 * 1526 * NOTE: assumes that the object at *addr has a size >= sizeof(llist_node) 1527 * 1528 */ 1529 void vfree(const void *addr) 1530 { 1531 BUG_ON(in_nmi()); 1532 1533 kmemleak_free(addr); 1534 1535 if (!addr) 1536 return; 1537 if (unlikely(in_interrupt())) { 1538 struct vfree_deferred *p = &__get_cpu_var(vfree_deferred); 1539 llist_add((struct llist_node *)addr, &p->list); 1540 schedule_work(&p->wq); 1541 } else 1542 __vunmap(addr, 1); 1543 } 1544 EXPORT_SYMBOL(vfree); 1545 1546 /** 1547 * vunmap - release virtual mapping obtained by vmap() 1548 * @addr: memory base address 1549 * 1550 * Free the virtually contiguous memory area starting at @addr, 1551 * which was created from the page array passed to vmap(). 1552 * 1553 * Must not be called in interrupt context. 1554 */ 1555 void vunmap(const void *addr) 1556 { 1557 BUG_ON(in_interrupt()); 1558 might_sleep(); 1559 if (addr) 1560 __vunmap(addr, 0); 1561 } 1562 EXPORT_SYMBOL(vunmap); 1563 1564 /** 1565 * vmap - map an array of pages into virtually contiguous space 1566 * @pages: array of page pointers 1567 * @count: number of pages to map 1568 * @flags: vm_area->flags 1569 * @prot: page protection for the mapping 1570 * 1571 * Maps @count pages from @pages into contiguous kernel virtual 1572 * space. 1573 */ 1574 void *vmap(struct page **pages, unsigned int count, 1575 unsigned long flags, pgprot_t prot) 1576 { 1577 struct vm_struct *area; 1578 1579 might_sleep(); 1580 1581 if (count > totalram_pages) 1582 return NULL; 1583 1584 area = get_vm_area_caller((count << PAGE_SHIFT), flags, 1585 __builtin_return_address(0)); 1586 if (!area) 1587 return NULL; 1588 1589 if (map_vm_area(area, prot, &pages)) { 1590 vunmap(area->addr); 1591 return NULL; 1592 } 1593 1594 return area->addr; 1595 } 1596 EXPORT_SYMBOL(vmap); 1597 1598 static void *__vmalloc_node(unsigned long size, unsigned long align, 1599 gfp_t gfp_mask, pgprot_t prot, 1600 int node, const void *caller); 1601 static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask, 1602 pgprot_t prot, int node, const void *caller) 1603 { 1604 const int order = 0; 1605 struct page **pages; 1606 unsigned int nr_pages, array_size, i; 1607 gfp_t nested_gfp = (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO; 1608 1609 nr_pages = (area->size - PAGE_SIZE) >> PAGE_SHIFT; 1610 array_size = (nr_pages * sizeof(struct page *)); 1611 1612 area->nr_pages = nr_pages; 1613 /* Please note that the recursion is strictly bounded. */ 1614 if (array_size > PAGE_SIZE) { 1615 pages = __vmalloc_node(array_size, 1, nested_gfp|__GFP_HIGHMEM, 1616 PAGE_KERNEL, node, caller); 1617 area->flags |= VM_VPAGES; 1618 } else { 1619 pages = kmalloc_node(array_size, nested_gfp, node); 1620 } 1621 area->pages = pages; 1622 area->caller = caller; 1623 if (!area->pages) { 1624 remove_vm_area(area->addr); 1625 kfree(area); 1626 return NULL; 1627 } 1628 1629 for (i = 0; i < area->nr_pages; i++) { 1630 struct page *page; 1631 gfp_t tmp_mask = gfp_mask | __GFP_NOWARN; 1632 1633 if (node < 0) 1634 page = alloc_page(tmp_mask); 1635 else 1636 page = alloc_pages_node(node, tmp_mask, order); 1637 1638 if (unlikely(!page)) { 1639 /* Successfully allocated i pages, free them in __vunmap() */ 1640 area->nr_pages = i; 1641 goto fail; 1642 } 1643 area->pages[i] = page; 1644 } 1645 1646 if (map_vm_area(area, prot, &pages)) 1647 goto fail; 1648 return area->addr; 1649 1650 fail: 1651 warn_alloc_failed(gfp_mask, order, 1652 "vmalloc: allocation failure, allocated %ld of %ld bytes\n", 1653 (area->nr_pages*PAGE_SIZE), area->size); 1654 vfree(area->addr); 1655 return NULL; 1656 } 1657 1658 /** 1659 * __vmalloc_node_range - allocate virtually contiguous memory 1660 * @size: allocation size 1661 * @align: desired alignment 1662 * @start: vm area range start 1663 * @end: vm area range end 1664 * @gfp_mask: flags for the page level allocator 1665 * @prot: protection mask for the allocated pages 1666 * @node: node to use for allocation or NUMA_NO_NODE 1667 * @caller: caller's return address 1668 * 1669 * Allocate enough pages to cover @size from the page level 1670 * allocator with @gfp_mask flags. Map them into contiguous 1671 * kernel virtual space, using a pagetable protection of @prot. 1672 */ 1673 void *__vmalloc_node_range(unsigned long size, unsigned long align, 1674 unsigned long start, unsigned long end, gfp_t gfp_mask, 1675 pgprot_t prot, int node, const void *caller) 1676 { 1677 struct vm_struct *area; 1678 void *addr; 1679 unsigned long real_size = size; 1680 1681 size = PAGE_ALIGN(size); 1682 if (!size || (size >> PAGE_SHIFT) > totalram_pages) 1683 goto fail; 1684 1685 area = __get_vm_area_node(size, align, VM_ALLOC | VM_UNLIST, 1686 start, end, node, gfp_mask, caller); 1687 if (!area) 1688 goto fail; 1689 1690 addr = __vmalloc_area_node(area, gfp_mask, prot, node, caller); 1691 if (!addr) 1692 return NULL; 1693 1694 /* 1695 * In this function, newly allocated vm_struct has VM_UNLIST flag. 1696 * It means that vm_struct is not fully initialized. 1697 * Now, it is fully initialized, so remove this flag here. 1698 */ 1699 clear_vm_unlist(area); 1700 1701 /* 1702 * A ref_count = 3 is needed because the vm_struct and vmap_area 1703 * structures allocated in the __get_vm_area_node() function contain 1704 * references to the virtual address of the vmalloc'ed block. 1705 */ 1706 kmemleak_alloc(addr, real_size, 3, gfp_mask); 1707 1708 return addr; 1709 1710 fail: 1711 warn_alloc_failed(gfp_mask, 0, 1712 "vmalloc: allocation failure: %lu bytes\n", 1713 real_size); 1714 return NULL; 1715 } 1716 1717 /** 1718 * __vmalloc_node - allocate virtually contiguous memory 1719 * @size: allocation size 1720 * @align: desired alignment 1721 * @gfp_mask: flags for the page level allocator 1722 * @prot: protection mask for the allocated pages 1723 * @node: node to use for allocation or NUMA_NO_NODE 1724 * @caller: caller's return address 1725 * 1726 * Allocate enough pages to cover @size from the page level 1727 * allocator with @gfp_mask flags. Map them into contiguous 1728 * kernel virtual space, using a pagetable protection of @prot. 1729 */ 1730 static void *__vmalloc_node(unsigned long size, unsigned long align, 1731 gfp_t gfp_mask, pgprot_t prot, 1732 int node, const void *caller) 1733 { 1734 return __vmalloc_node_range(size, align, VMALLOC_START, VMALLOC_END, 1735 gfp_mask, prot, node, caller); 1736 } 1737 1738 void *__vmalloc(unsigned long size, gfp_t gfp_mask, pgprot_t prot) 1739 { 1740 return __vmalloc_node(size, 1, gfp_mask, prot, NUMA_NO_NODE, 1741 __builtin_return_address(0)); 1742 } 1743 EXPORT_SYMBOL(__vmalloc); 1744 1745 static inline void *__vmalloc_node_flags(unsigned long size, 1746 int node, gfp_t flags) 1747 { 1748 return __vmalloc_node(size, 1, flags, PAGE_KERNEL, 1749 node, __builtin_return_address(0)); 1750 } 1751 1752 /** 1753 * vmalloc - allocate virtually contiguous memory 1754 * @size: allocation size 1755 * Allocate enough pages to cover @size from the page level 1756 * allocator and map them into contiguous kernel virtual space. 1757 * 1758 * For tight control over page level allocator and protection flags 1759 * use __vmalloc() instead. 1760 */ 1761 void *vmalloc(unsigned long size) 1762 { 1763 return __vmalloc_node_flags(size, NUMA_NO_NODE, 1764 GFP_KERNEL | __GFP_HIGHMEM); 1765 } 1766 EXPORT_SYMBOL(vmalloc); 1767 1768 /** 1769 * vzalloc - allocate virtually contiguous memory with zero fill 1770 * @size: allocation size 1771 * Allocate enough pages to cover @size from the page level 1772 * allocator and map them into contiguous kernel virtual space. 1773 * The memory allocated is set to zero. 1774 * 1775 * For tight control over page level allocator and protection flags 1776 * use __vmalloc() instead. 1777 */ 1778 void *vzalloc(unsigned long size) 1779 { 1780 return __vmalloc_node_flags(size, NUMA_NO_NODE, 1781 GFP_KERNEL | __GFP_HIGHMEM | __GFP_ZERO); 1782 } 1783 EXPORT_SYMBOL(vzalloc); 1784 1785 /** 1786 * vmalloc_user - allocate zeroed virtually contiguous memory for userspace 1787 * @size: allocation size 1788 * 1789 * The resulting memory area is zeroed so it can be mapped to userspace 1790 * without leaking data. 1791 */ 1792 void *vmalloc_user(unsigned long size) 1793 { 1794 struct vm_struct *area; 1795 void *ret; 1796 1797 ret = __vmalloc_node(size, SHMLBA, 1798 GFP_KERNEL | __GFP_HIGHMEM | __GFP_ZERO, 1799 PAGE_KERNEL, NUMA_NO_NODE, 1800 __builtin_return_address(0)); 1801 if (ret) { 1802 area = find_vm_area(ret); 1803 area->flags |= VM_USERMAP; 1804 } 1805 return ret; 1806 } 1807 EXPORT_SYMBOL(vmalloc_user); 1808 1809 /** 1810 * vmalloc_node - allocate memory on a specific node 1811 * @size: allocation size 1812 * @node: numa node 1813 * 1814 * Allocate enough pages to cover @size from the page level 1815 * allocator and map them into contiguous kernel virtual space. 1816 * 1817 * For tight control over page level allocator and protection flags 1818 * use __vmalloc() instead. 1819 */ 1820 void *vmalloc_node(unsigned long size, int node) 1821 { 1822 return __vmalloc_node(size, 1, GFP_KERNEL | __GFP_HIGHMEM, PAGE_KERNEL, 1823 node, __builtin_return_address(0)); 1824 } 1825 EXPORT_SYMBOL(vmalloc_node); 1826 1827 /** 1828 * vzalloc_node - allocate memory on a specific node with zero fill 1829 * @size: allocation size 1830 * @node: numa node 1831 * 1832 * Allocate enough pages to cover @size from the page level 1833 * allocator and map them into contiguous kernel virtual space. 1834 * The memory allocated is set to zero. 1835 * 1836 * For tight control over page level allocator and protection flags 1837 * use __vmalloc_node() instead. 1838 */ 1839 void *vzalloc_node(unsigned long size, int node) 1840 { 1841 return __vmalloc_node_flags(size, node, 1842 GFP_KERNEL | __GFP_HIGHMEM | __GFP_ZERO); 1843 } 1844 EXPORT_SYMBOL(vzalloc_node); 1845 1846 #ifndef PAGE_KERNEL_EXEC 1847 # define PAGE_KERNEL_EXEC PAGE_KERNEL 1848 #endif 1849 1850 /** 1851 * vmalloc_exec - allocate virtually contiguous, executable memory 1852 * @size: allocation size 1853 * 1854 * Kernel-internal function to allocate enough pages to cover @size 1855 * the page level allocator and map them into contiguous and 1856 * executable kernel virtual space. 1857 * 1858 * For tight control over page level allocator and protection flags 1859 * use __vmalloc() instead. 1860 */ 1861 1862 void *vmalloc_exec(unsigned long size) 1863 { 1864 return __vmalloc_node(size, 1, GFP_KERNEL | __GFP_HIGHMEM, PAGE_KERNEL_EXEC, 1865 NUMA_NO_NODE, __builtin_return_address(0)); 1866 } 1867 1868 #if defined(CONFIG_64BIT) && defined(CONFIG_ZONE_DMA32) 1869 #define GFP_VMALLOC32 GFP_DMA32 | GFP_KERNEL 1870 #elif defined(CONFIG_64BIT) && defined(CONFIG_ZONE_DMA) 1871 #define GFP_VMALLOC32 GFP_DMA | GFP_KERNEL 1872 #else 1873 #define GFP_VMALLOC32 GFP_KERNEL 1874 #endif 1875 1876 /** 1877 * vmalloc_32 - allocate virtually contiguous memory (32bit addressable) 1878 * @size: allocation size 1879 * 1880 * Allocate enough 32bit PA addressable pages to cover @size from the 1881 * page level allocator and map them into contiguous kernel virtual space. 1882 */ 1883 void *vmalloc_32(unsigned long size) 1884 { 1885 return __vmalloc_node(size, 1, GFP_VMALLOC32, PAGE_KERNEL, 1886 NUMA_NO_NODE, __builtin_return_address(0)); 1887 } 1888 EXPORT_SYMBOL(vmalloc_32); 1889 1890 /** 1891 * vmalloc_32_user - allocate zeroed virtually contiguous 32bit memory 1892 * @size: allocation size 1893 * 1894 * The resulting memory area is 32bit addressable and zeroed so it can be 1895 * mapped to userspace without leaking data. 1896 */ 1897 void *vmalloc_32_user(unsigned long size) 1898 { 1899 struct vm_struct *area; 1900 void *ret; 1901 1902 ret = __vmalloc_node(size, 1, GFP_VMALLOC32 | __GFP_ZERO, PAGE_KERNEL, 1903 NUMA_NO_NODE, __builtin_return_address(0)); 1904 if (ret) { 1905 area = find_vm_area(ret); 1906 area->flags |= VM_USERMAP; 1907 } 1908 return ret; 1909 } 1910 EXPORT_SYMBOL(vmalloc_32_user); 1911 1912 /* 1913 * small helper routine , copy contents to buf from addr. 1914 * If the page is not present, fill zero. 1915 */ 1916 1917 static int aligned_vread(char *buf, char *addr, unsigned long count) 1918 { 1919 struct page *p; 1920 int copied = 0; 1921 1922 while (count) { 1923 unsigned long offset, length; 1924 1925 offset = (unsigned long)addr & ~PAGE_MASK; 1926 length = PAGE_SIZE - offset; 1927 if (length > count) 1928 length = count; 1929 p = vmalloc_to_page(addr); 1930 /* 1931 * To do safe access to this _mapped_ area, we need 1932 * lock. But adding lock here means that we need to add 1933 * overhead of vmalloc()/vfree() calles for this _debug_ 1934 * interface, rarely used. Instead of that, we'll use 1935 * kmap() and get small overhead in this access function. 1936 */ 1937 if (p) { 1938 /* 1939 * we can expect USER0 is not used (see vread/vwrite's 1940 * function description) 1941 */ 1942 void *map = kmap_atomic(p); 1943 memcpy(buf, map + offset, length); 1944 kunmap_atomic(map); 1945 } else 1946 memset(buf, 0, length); 1947 1948 addr += length; 1949 buf += length; 1950 copied += length; 1951 count -= length; 1952 } 1953 return copied; 1954 } 1955 1956 static int aligned_vwrite(char *buf, char *addr, unsigned long count) 1957 { 1958 struct page *p; 1959 int copied = 0; 1960 1961 while (count) { 1962 unsigned long offset, length; 1963 1964 offset = (unsigned long)addr & ~PAGE_MASK; 1965 length = PAGE_SIZE - offset; 1966 if (length > count) 1967 length = count; 1968 p = vmalloc_to_page(addr); 1969 /* 1970 * To do safe access to this _mapped_ area, we need 1971 * lock. But adding lock here means that we need to add 1972 * overhead of vmalloc()/vfree() calles for this _debug_ 1973 * interface, rarely used. Instead of that, we'll use 1974 * kmap() and get small overhead in this access function. 1975 */ 1976 if (p) { 1977 /* 1978 * we can expect USER0 is not used (see vread/vwrite's 1979 * function description) 1980 */ 1981 void *map = kmap_atomic(p); 1982 memcpy(map + offset, buf, length); 1983 kunmap_atomic(map); 1984 } 1985 addr += length; 1986 buf += length; 1987 copied += length; 1988 count -= length; 1989 } 1990 return copied; 1991 } 1992 1993 /** 1994 * vread() - read vmalloc area in a safe way. 1995 * @buf: buffer for reading data 1996 * @addr: vm address. 1997 * @count: number of bytes to be read. 1998 * 1999 * Returns # of bytes which addr and buf should be increased. 2000 * (same number to @count). Returns 0 if [addr...addr+count) doesn't 2001 * includes any intersect with alive vmalloc area. 2002 * 2003 * This function checks that addr is a valid vmalloc'ed area, and 2004 * copy data from that area to a given buffer. If the given memory range 2005 * of [addr...addr+count) includes some valid address, data is copied to 2006 * proper area of @buf. If there are memory holes, they'll be zero-filled. 2007 * IOREMAP area is treated as memory hole and no copy is done. 2008 * 2009 * If [addr...addr+count) doesn't includes any intersects with alive 2010 * vm_struct area, returns 0. @buf should be kernel's buffer. 2011 * 2012 * Note: In usual ops, vread() is never necessary because the caller 2013 * should know vmalloc() area is valid and can use memcpy(). 2014 * This is for routines which have to access vmalloc area without 2015 * any informaion, as /dev/kmem. 2016 * 2017 */ 2018 2019 long vread(char *buf, char *addr, unsigned long count) 2020 { 2021 struct vmap_area *va; 2022 struct vm_struct *vm; 2023 char *vaddr, *buf_start = buf; 2024 unsigned long buflen = count; 2025 unsigned long n; 2026 2027 /* Don't allow overflow */ 2028 if ((unsigned long) addr + count < count) 2029 count = -(unsigned long) addr; 2030 2031 spin_lock(&vmap_area_lock); 2032 list_for_each_entry(va, &vmap_area_list, list) { 2033 if (!count) 2034 break; 2035 2036 if (!(va->flags & VM_VM_AREA)) 2037 continue; 2038 2039 vm = va->vm; 2040 vaddr = (char *) vm->addr; 2041 if (addr >= vaddr + vm->size - PAGE_SIZE) 2042 continue; 2043 while (addr < vaddr) { 2044 if (count == 0) 2045 goto finished; 2046 *buf = '\0'; 2047 buf++; 2048 addr++; 2049 count--; 2050 } 2051 n = vaddr + vm->size - PAGE_SIZE - addr; 2052 if (n > count) 2053 n = count; 2054 if (!(vm->flags & VM_IOREMAP)) 2055 aligned_vread(buf, addr, n); 2056 else /* IOREMAP area is treated as memory hole */ 2057 memset(buf, 0, n); 2058 buf += n; 2059 addr += n; 2060 count -= n; 2061 } 2062 finished: 2063 spin_unlock(&vmap_area_lock); 2064 2065 if (buf == buf_start) 2066 return 0; 2067 /* zero-fill memory holes */ 2068 if (buf != buf_start + buflen) 2069 memset(buf, 0, buflen - (buf - buf_start)); 2070 2071 return buflen; 2072 } 2073 2074 /** 2075 * vwrite() - write vmalloc area in a safe way. 2076 * @buf: buffer for source data 2077 * @addr: vm address. 2078 * @count: number of bytes to be read. 2079 * 2080 * Returns # of bytes which addr and buf should be incresed. 2081 * (same number to @count). 2082 * If [addr...addr+count) doesn't includes any intersect with valid 2083 * vmalloc area, returns 0. 2084 * 2085 * This function checks that addr is a valid vmalloc'ed area, and 2086 * copy data from a buffer to the given addr. If specified range of 2087 * [addr...addr+count) includes some valid address, data is copied from 2088 * proper area of @buf. If there are memory holes, no copy to hole. 2089 * IOREMAP area is treated as memory hole and no copy is done. 2090 * 2091 * If [addr...addr+count) doesn't includes any intersects with alive 2092 * vm_struct area, returns 0. @buf should be kernel's buffer. 2093 * 2094 * Note: In usual ops, vwrite() is never necessary because the caller 2095 * should know vmalloc() area is valid and can use memcpy(). 2096 * This is for routines which have to access vmalloc area without 2097 * any informaion, as /dev/kmem. 2098 */ 2099 2100 long vwrite(char *buf, char *addr, unsigned long count) 2101 { 2102 struct vmap_area *va; 2103 struct vm_struct *vm; 2104 char *vaddr; 2105 unsigned long n, buflen; 2106 int copied = 0; 2107 2108 /* Don't allow overflow */ 2109 if ((unsigned long) addr + count < count) 2110 count = -(unsigned long) addr; 2111 buflen = count; 2112 2113 spin_lock(&vmap_area_lock); 2114 list_for_each_entry(va, &vmap_area_list, list) { 2115 if (!count) 2116 break; 2117 2118 if (!(va->flags & VM_VM_AREA)) 2119 continue; 2120 2121 vm = va->vm; 2122 vaddr = (char *) vm->addr; 2123 if (addr >= vaddr + vm->size - PAGE_SIZE) 2124 continue; 2125 while (addr < vaddr) { 2126 if (count == 0) 2127 goto finished; 2128 buf++; 2129 addr++; 2130 count--; 2131 } 2132 n = vaddr + vm->size - PAGE_SIZE - addr; 2133 if (n > count) 2134 n = count; 2135 if (!(vm->flags & VM_IOREMAP)) { 2136 aligned_vwrite(buf, addr, n); 2137 copied++; 2138 } 2139 buf += n; 2140 addr += n; 2141 count -= n; 2142 } 2143 finished: 2144 spin_unlock(&vmap_area_lock); 2145 if (!copied) 2146 return 0; 2147 return buflen; 2148 } 2149 2150 /** 2151 * remap_vmalloc_range - map vmalloc pages to userspace 2152 * @vma: vma to cover (map full range of vma) 2153 * @addr: vmalloc memory 2154 * @pgoff: number of pages into addr before first page to map 2155 * 2156 * Returns: 0 for success, -Exxx on failure 2157 * 2158 * This function checks that addr is a valid vmalloc'ed area, and 2159 * that it is big enough to cover the vma. Will return failure if 2160 * that criteria isn't met. 2161 * 2162 * Similar to remap_pfn_range() (see mm/memory.c) 2163 */ 2164 int remap_vmalloc_range(struct vm_area_struct *vma, void *addr, 2165 unsigned long pgoff) 2166 { 2167 struct vm_struct *area; 2168 unsigned long uaddr = vma->vm_start; 2169 unsigned long usize = vma->vm_end - vma->vm_start; 2170 2171 if ((PAGE_SIZE-1) & (unsigned long)addr) 2172 return -EINVAL; 2173 2174 area = find_vm_area(addr); 2175 if (!area) 2176 return -EINVAL; 2177 2178 if (!(area->flags & VM_USERMAP)) 2179 return -EINVAL; 2180 2181 if (usize + (pgoff << PAGE_SHIFT) > area->size - PAGE_SIZE) 2182 return -EINVAL; 2183 2184 addr += pgoff << PAGE_SHIFT; 2185 do { 2186 struct page *page = vmalloc_to_page(addr); 2187 int ret; 2188 2189 ret = vm_insert_page(vma, uaddr, page); 2190 if (ret) 2191 return ret; 2192 2193 uaddr += PAGE_SIZE; 2194 addr += PAGE_SIZE; 2195 usize -= PAGE_SIZE; 2196 } while (usize > 0); 2197 2198 vma->vm_flags |= VM_DONTEXPAND | VM_DONTDUMP; 2199 2200 return 0; 2201 } 2202 EXPORT_SYMBOL(remap_vmalloc_range); 2203 2204 /* 2205 * Implement a stub for vmalloc_sync_all() if the architecture chose not to 2206 * have one. 2207 */ 2208 void __attribute__((weak)) vmalloc_sync_all(void) 2209 { 2210 } 2211 2212 2213 static int f(pte_t *pte, pgtable_t table, unsigned long addr, void *data) 2214 { 2215 pte_t ***p = data; 2216 2217 if (p) { 2218 *(*p) = pte; 2219 (*p)++; 2220 } 2221 return 0; 2222 } 2223 2224 /** 2225 * alloc_vm_area - allocate a range of kernel address space 2226 * @size: size of the area 2227 * @ptes: returns the PTEs for the address space 2228 * 2229 * Returns: NULL on failure, vm_struct on success 2230 * 2231 * This function reserves a range of kernel address space, and 2232 * allocates pagetables to map that range. No actual mappings 2233 * are created. 2234 * 2235 * If @ptes is non-NULL, pointers to the PTEs (in init_mm) 2236 * allocated for the VM area are returned. 2237 */ 2238 struct vm_struct *alloc_vm_area(size_t size, pte_t **ptes) 2239 { 2240 struct vm_struct *area; 2241 2242 area = get_vm_area_caller(size, VM_IOREMAP, 2243 __builtin_return_address(0)); 2244 if (area == NULL) 2245 return NULL; 2246 2247 /* 2248 * This ensures that page tables are constructed for this region 2249 * of kernel virtual address space and mapped into init_mm. 2250 */ 2251 if (apply_to_page_range(&init_mm, (unsigned long)area->addr, 2252 size, f, ptes ? &ptes : NULL)) { 2253 free_vm_area(area); 2254 return NULL; 2255 } 2256 2257 return area; 2258 } 2259 EXPORT_SYMBOL_GPL(alloc_vm_area); 2260 2261 void free_vm_area(struct vm_struct *area) 2262 { 2263 struct vm_struct *ret; 2264 ret = remove_vm_area(area->addr); 2265 BUG_ON(ret != area); 2266 kfree(area); 2267 } 2268 EXPORT_SYMBOL_GPL(free_vm_area); 2269 2270 #ifdef CONFIG_SMP 2271 static struct vmap_area *node_to_va(struct rb_node *n) 2272 { 2273 return n ? rb_entry(n, struct vmap_area, rb_node) : NULL; 2274 } 2275 2276 /** 2277 * pvm_find_next_prev - find the next and prev vmap_area surrounding @end 2278 * @end: target address 2279 * @pnext: out arg for the next vmap_area 2280 * @pprev: out arg for the previous vmap_area 2281 * 2282 * Returns: %true if either or both of next and prev are found, 2283 * %false if no vmap_area exists 2284 * 2285 * Find vmap_areas end addresses of which enclose @end. ie. if not 2286 * NULL, *pnext->va_end > @end and *pprev->va_end <= @end. 2287 */ 2288 static bool pvm_find_next_prev(unsigned long end, 2289 struct vmap_area **pnext, 2290 struct vmap_area **pprev) 2291 { 2292 struct rb_node *n = vmap_area_root.rb_node; 2293 struct vmap_area *va = NULL; 2294 2295 while (n) { 2296 va = rb_entry(n, struct vmap_area, rb_node); 2297 if (end < va->va_end) 2298 n = n->rb_left; 2299 else if (end > va->va_end) 2300 n = n->rb_right; 2301 else 2302 break; 2303 } 2304 2305 if (!va) 2306 return false; 2307 2308 if (va->va_end > end) { 2309 *pnext = va; 2310 *pprev = node_to_va(rb_prev(&(*pnext)->rb_node)); 2311 } else { 2312 *pprev = va; 2313 *pnext = node_to_va(rb_next(&(*pprev)->rb_node)); 2314 } 2315 return true; 2316 } 2317 2318 /** 2319 * pvm_determine_end - find the highest aligned address between two vmap_areas 2320 * @pnext: in/out arg for the next vmap_area 2321 * @pprev: in/out arg for the previous vmap_area 2322 * @align: alignment 2323 * 2324 * Returns: determined end address 2325 * 2326 * Find the highest aligned address between *@pnext and *@pprev below 2327 * VMALLOC_END. *@pnext and *@pprev are adjusted so that the aligned 2328 * down address is between the end addresses of the two vmap_areas. 2329 * 2330 * Please note that the address returned by this function may fall 2331 * inside *@pnext vmap_area. The caller is responsible for checking 2332 * that. 2333 */ 2334 static unsigned long pvm_determine_end(struct vmap_area **pnext, 2335 struct vmap_area **pprev, 2336 unsigned long align) 2337 { 2338 const unsigned long vmalloc_end = VMALLOC_END & ~(align - 1); 2339 unsigned long addr; 2340 2341 if (*pnext) 2342 addr = min((*pnext)->va_start & ~(align - 1), vmalloc_end); 2343 else 2344 addr = vmalloc_end; 2345 2346 while (*pprev && (*pprev)->va_end > addr) { 2347 *pnext = *pprev; 2348 *pprev = node_to_va(rb_prev(&(*pnext)->rb_node)); 2349 } 2350 2351 return addr; 2352 } 2353 2354 /** 2355 * pcpu_get_vm_areas - allocate vmalloc areas for percpu allocator 2356 * @offsets: array containing offset of each area 2357 * @sizes: array containing size of each area 2358 * @nr_vms: the number of areas to allocate 2359 * @align: alignment, all entries in @offsets and @sizes must be aligned to this 2360 * 2361 * Returns: kmalloc'd vm_struct pointer array pointing to allocated 2362 * vm_structs on success, %NULL on failure 2363 * 2364 * Percpu allocator wants to use congruent vm areas so that it can 2365 * maintain the offsets among percpu areas. This function allocates 2366 * congruent vmalloc areas for it with GFP_KERNEL. These areas tend to 2367 * be scattered pretty far, distance between two areas easily going up 2368 * to gigabytes. To avoid interacting with regular vmallocs, these 2369 * areas are allocated from top. 2370 * 2371 * Despite its complicated look, this allocator is rather simple. It 2372 * does everything top-down and scans areas from the end looking for 2373 * matching slot. While scanning, if any of the areas overlaps with 2374 * existing vmap_area, the base address is pulled down to fit the 2375 * area. Scanning is repeated till all the areas fit and then all 2376 * necessary data structres are inserted and the result is returned. 2377 */ 2378 struct vm_struct **pcpu_get_vm_areas(const unsigned long *offsets, 2379 const size_t *sizes, int nr_vms, 2380 size_t align) 2381 { 2382 const unsigned long vmalloc_start = ALIGN(VMALLOC_START, align); 2383 const unsigned long vmalloc_end = VMALLOC_END & ~(align - 1); 2384 struct vmap_area **vas, *prev, *next; 2385 struct vm_struct **vms; 2386 int area, area2, last_area, term_area; 2387 unsigned long base, start, end, last_end; 2388 bool purged = false; 2389 2390 /* verify parameters and allocate data structures */ 2391 BUG_ON(align & ~PAGE_MASK || !is_power_of_2(align)); 2392 for (last_area = 0, area = 0; area < nr_vms; area++) { 2393 start = offsets[area]; 2394 end = start + sizes[area]; 2395 2396 /* is everything aligned properly? */ 2397 BUG_ON(!IS_ALIGNED(offsets[area], align)); 2398 BUG_ON(!IS_ALIGNED(sizes[area], align)); 2399 2400 /* detect the area with the highest address */ 2401 if (start > offsets[last_area]) 2402 last_area = area; 2403 2404 for (area2 = 0; area2 < nr_vms; area2++) { 2405 unsigned long start2 = offsets[area2]; 2406 unsigned long end2 = start2 + sizes[area2]; 2407 2408 if (area2 == area) 2409 continue; 2410 2411 BUG_ON(start2 >= start && start2 < end); 2412 BUG_ON(end2 <= end && end2 > start); 2413 } 2414 } 2415 last_end = offsets[last_area] + sizes[last_area]; 2416 2417 if (vmalloc_end - vmalloc_start < last_end) { 2418 WARN_ON(true); 2419 return NULL; 2420 } 2421 2422 vms = kcalloc(nr_vms, sizeof(vms[0]), GFP_KERNEL); 2423 vas = kcalloc(nr_vms, sizeof(vas[0]), GFP_KERNEL); 2424 if (!vas || !vms) 2425 goto err_free2; 2426 2427 for (area = 0; area < nr_vms; area++) { 2428 vas[area] = kzalloc(sizeof(struct vmap_area), GFP_KERNEL); 2429 vms[area] = kzalloc(sizeof(struct vm_struct), GFP_KERNEL); 2430 if (!vas[area] || !vms[area]) 2431 goto err_free; 2432 } 2433 retry: 2434 spin_lock(&vmap_area_lock); 2435 2436 /* start scanning - we scan from the top, begin with the last area */ 2437 area = term_area = last_area; 2438 start = offsets[area]; 2439 end = start + sizes[area]; 2440 2441 if (!pvm_find_next_prev(vmap_area_pcpu_hole, &next, &prev)) { 2442 base = vmalloc_end - last_end; 2443 goto found; 2444 } 2445 base = pvm_determine_end(&next, &prev, align) - end; 2446 2447 while (true) { 2448 BUG_ON(next && next->va_end <= base + end); 2449 BUG_ON(prev && prev->va_end > base + end); 2450 2451 /* 2452 * base might have underflowed, add last_end before 2453 * comparing. 2454 */ 2455 if (base + last_end < vmalloc_start + last_end) { 2456 spin_unlock(&vmap_area_lock); 2457 if (!purged) { 2458 purge_vmap_area_lazy(); 2459 purged = true; 2460 goto retry; 2461 } 2462 goto err_free; 2463 } 2464 2465 /* 2466 * If next overlaps, move base downwards so that it's 2467 * right below next and then recheck. 2468 */ 2469 if (next && next->va_start < base + end) { 2470 base = pvm_determine_end(&next, &prev, align) - end; 2471 term_area = area; 2472 continue; 2473 } 2474 2475 /* 2476 * If prev overlaps, shift down next and prev and move 2477 * base so that it's right below new next and then 2478 * recheck. 2479 */ 2480 if (prev && prev->va_end > base + start) { 2481 next = prev; 2482 prev = node_to_va(rb_prev(&next->rb_node)); 2483 base = pvm_determine_end(&next, &prev, align) - end; 2484 term_area = area; 2485 continue; 2486 } 2487 2488 /* 2489 * This area fits, move on to the previous one. If 2490 * the previous one is the terminal one, we're done. 2491 */ 2492 area = (area + nr_vms - 1) % nr_vms; 2493 if (area == term_area) 2494 break; 2495 start = offsets[area]; 2496 end = start + sizes[area]; 2497 pvm_find_next_prev(base + end, &next, &prev); 2498 } 2499 found: 2500 /* we've found a fitting base, insert all va's */ 2501 for (area = 0; area < nr_vms; area++) { 2502 struct vmap_area *va = vas[area]; 2503 2504 va->va_start = base + offsets[area]; 2505 va->va_end = va->va_start + sizes[area]; 2506 __insert_vmap_area(va); 2507 } 2508 2509 vmap_area_pcpu_hole = base + offsets[last_area]; 2510 2511 spin_unlock(&vmap_area_lock); 2512 2513 /* insert all vm's */ 2514 for (area = 0; area < nr_vms; area++) 2515 insert_vmalloc_vm(vms[area], vas[area], VM_ALLOC, 2516 pcpu_get_vm_areas); 2517 2518 kfree(vas); 2519 return vms; 2520 2521 err_free: 2522 for (area = 0; area < nr_vms; area++) { 2523 kfree(vas[area]); 2524 kfree(vms[area]); 2525 } 2526 err_free2: 2527 kfree(vas); 2528 kfree(vms); 2529 return NULL; 2530 } 2531 2532 /** 2533 * pcpu_free_vm_areas - free vmalloc areas for percpu allocator 2534 * @vms: vm_struct pointer array returned by pcpu_get_vm_areas() 2535 * @nr_vms: the number of allocated areas 2536 * 2537 * Free vm_structs and the array allocated by pcpu_get_vm_areas(). 2538 */ 2539 void pcpu_free_vm_areas(struct vm_struct **vms, int nr_vms) 2540 { 2541 int i; 2542 2543 for (i = 0; i < nr_vms; i++) 2544 free_vm_area(vms[i]); 2545 kfree(vms); 2546 } 2547 #endif /* CONFIG_SMP */ 2548 2549 #ifdef CONFIG_PROC_FS 2550 static void *s_start(struct seq_file *m, loff_t *pos) 2551 __acquires(&vmap_area_lock) 2552 { 2553 loff_t n = *pos; 2554 struct vmap_area *va; 2555 2556 spin_lock(&vmap_area_lock); 2557 va = list_entry((&vmap_area_list)->next, typeof(*va), list); 2558 while (n > 0 && &va->list != &vmap_area_list) { 2559 n--; 2560 va = list_entry(va->list.next, typeof(*va), list); 2561 } 2562 if (!n && &va->list != &vmap_area_list) 2563 return va; 2564 2565 return NULL; 2566 2567 } 2568 2569 static void *s_next(struct seq_file *m, void *p, loff_t *pos) 2570 { 2571 struct vmap_area *va = p, *next; 2572 2573 ++*pos; 2574 next = list_entry(va->list.next, typeof(*va), list); 2575 if (&next->list != &vmap_area_list) 2576 return next; 2577 2578 return NULL; 2579 } 2580 2581 static void s_stop(struct seq_file *m, void *p) 2582 __releases(&vmap_area_lock) 2583 { 2584 spin_unlock(&vmap_area_lock); 2585 } 2586 2587 static void show_numa_info(struct seq_file *m, struct vm_struct *v) 2588 { 2589 if (IS_ENABLED(CONFIG_NUMA)) { 2590 unsigned int nr, *counters = m->private; 2591 2592 if (!counters) 2593 return; 2594 2595 /* Pair with smp_wmb() in clear_vm_unlist() */ 2596 smp_rmb(); 2597 if (v->flags & VM_UNLIST) 2598 return; 2599 2600 memset(counters, 0, nr_node_ids * sizeof(unsigned int)); 2601 2602 for (nr = 0; nr < v->nr_pages; nr++) 2603 counters[page_to_nid(v->pages[nr])]++; 2604 2605 for_each_node_state(nr, N_HIGH_MEMORY) 2606 if (counters[nr]) 2607 seq_printf(m, " N%u=%u", nr, counters[nr]); 2608 } 2609 } 2610 2611 static int s_show(struct seq_file *m, void *p) 2612 { 2613 struct vmap_area *va = p; 2614 struct vm_struct *v; 2615 2616 if (va->flags & (VM_LAZY_FREE | VM_LAZY_FREEING)) 2617 return 0; 2618 2619 if (!(va->flags & VM_VM_AREA)) { 2620 seq_printf(m, "0x%pK-0x%pK %7ld vm_map_ram\n", 2621 (void *)va->va_start, (void *)va->va_end, 2622 va->va_end - va->va_start); 2623 return 0; 2624 } 2625 2626 v = va->vm; 2627 2628 seq_printf(m, "0x%pK-0x%pK %7ld", 2629 v->addr, v->addr + v->size, v->size); 2630 2631 if (v->caller) 2632 seq_printf(m, " %pS", v->caller); 2633 2634 if (v->nr_pages) 2635 seq_printf(m, " pages=%d", v->nr_pages); 2636 2637 if (v->phys_addr) 2638 seq_printf(m, " phys=%llx", (unsigned long long)v->phys_addr); 2639 2640 if (v->flags & VM_IOREMAP) 2641 seq_printf(m, " ioremap"); 2642 2643 if (v->flags & VM_ALLOC) 2644 seq_printf(m, " vmalloc"); 2645 2646 if (v->flags & VM_MAP) 2647 seq_printf(m, " vmap"); 2648 2649 if (v->flags & VM_USERMAP) 2650 seq_printf(m, " user"); 2651 2652 if (v->flags & VM_VPAGES) 2653 seq_printf(m, " vpages"); 2654 2655 show_numa_info(m, v); 2656 seq_putc(m, '\n'); 2657 return 0; 2658 } 2659 2660 static const struct seq_operations vmalloc_op = { 2661 .start = s_start, 2662 .next = s_next, 2663 .stop = s_stop, 2664 .show = s_show, 2665 }; 2666 2667 static int vmalloc_open(struct inode *inode, struct file *file) 2668 { 2669 unsigned int *ptr = NULL; 2670 int ret; 2671 2672 if (IS_ENABLED(CONFIG_NUMA)) { 2673 ptr = kmalloc(nr_node_ids * sizeof(unsigned int), GFP_KERNEL); 2674 if (ptr == NULL) 2675 return -ENOMEM; 2676 } 2677 ret = seq_open(file, &vmalloc_op); 2678 if (!ret) { 2679 struct seq_file *m = file->private_data; 2680 m->private = ptr; 2681 } else 2682 kfree(ptr); 2683 return ret; 2684 } 2685 2686 static const struct file_operations proc_vmalloc_operations = { 2687 .open = vmalloc_open, 2688 .read = seq_read, 2689 .llseek = seq_lseek, 2690 .release = seq_release_private, 2691 }; 2692 2693 static int __init proc_vmalloc_init(void) 2694 { 2695 proc_create("vmallocinfo", S_IRUSR, NULL, &proc_vmalloc_operations); 2696 return 0; 2697 } 2698 module_init(proc_vmalloc_init); 2699 2700 void get_vmalloc_info(struct vmalloc_info *vmi) 2701 { 2702 struct vmap_area *va; 2703 unsigned long free_area_size; 2704 unsigned long prev_end; 2705 2706 vmi->used = 0; 2707 vmi->largest_chunk = 0; 2708 2709 prev_end = VMALLOC_START; 2710 2711 spin_lock(&vmap_area_lock); 2712 2713 if (list_empty(&vmap_area_list)) { 2714 vmi->largest_chunk = VMALLOC_TOTAL; 2715 goto out; 2716 } 2717 2718 list_for_each_entry(va, &vmap_area_list, list) { 2719 unsigned long addr = va->va_start; 2720 2721 /* 2722 * Some archs keep another range for modules in vmalloc space 2723 */ 2724 if (addr < VMALLOC_START) 2725 continue; 2726 if (addr >= VMALLOC_END) 2727 break; 2728 2729 if (va->flags & (VM_LAZY_FREE | VM_LAZY_FREEING)) 2730 continue; 2731 2732 vmi->used += (va->va_end - va->va_start); 2733 2734 free_area_size = addr - prev_end; 2735 if (vmi->largest_chunk < free_area_size) 2736 vmi->largest_chunk = free_area_size; 2737 2738 prev_end = va->va_end; 2739 } 2740 2741 if (VMALLOC_END - prev_end > vmi->largest_chunk) 2742 vmi->largest_chunk = VMALLOC_END - prev_end; 2743 2744 out: 2745 spin_unlock(&vmap_area_lock); 2746 } 2747 #endif 2748 2749