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/llist.h>
  35 #include <linux/bitops.h>
  36 #include <linux/rbtree_augmented.h>
  37 #include <linux/overflow.h>
  38 #include <linux/pgtable.h>
  39 #include <linux/uaccess.h>
  40 #include <linux/hugetlb.h>
  41 #include <asm/tlbflush.h>
  42 #include <asm/shmparam.h>
  43
  44 #include "internal.h"
  45 #include "pgalloc-track.h"
  46
  47 #ifdef CONFIG_HAVE_ARCH_HUGE_VMALLOC
  48 static bool __ro_after_init vmap_allow_huge = true;
  49
  50 static int __init set_nohugevmalloc(char *str)
  51 {
  52         vmap_allow_huge = false;
  53         return 0;
  54 }
  55 early_param("nohugevmalloc", set_nohugevmalloc);
  56 #else /* CONFIG_HAVE_ARCH_HUGE_VMALLOC */
  57 static const bool vmap_allow_huge = false;
  58 #endif  /* CONFIG_HAVE_ARCH_HUGE_VMALLOC */
  59
  60 bool is_vmalloc_addr(const void *x)
  61 {
  62         unsigned long addr = (unsigned long)x;
  63
  64         return addr >= VMALLOC_START && addr < VMALLOC_END;
  65 }
  66 EXPORT_SYMBOL(is_vmalloc_addr);
  67
  68 struct vfree_deferred {
  69         struct llist_head list;
  70         struct work_struct wq;
  71 };
  72 static DEFINE_PER_CPU(struct vfree_deferred, vfree_deferred);
  73
  74 static void __vunmap(const void *, int);
  75
  76 static void free_work(struct work_struct *w)
  77 {
  78         struct vfree_deferred *p = container_of(w, struct vfree_deferred, wq);
  79         struct llist_node *t, *llnode;
  80
  81         llist_for_each_safe(llnode, t, llist_del_all(&p->list))
  82                 __vunmap((void *)llnode, 1);
  83 }
  84
  85 /*** Page table manipulation functions ***/
  86 static int vmap_pte_range(pmd_t *pmd, unsigned long addr, unsigned long end,
  87                         phys_addr_t phys_addr, pgprot_t prot,
  88                         unsigned int max_page_shift, pgtbl_mod_mask *mask)
  89 {
  90         pte_t *pte;
  91         u64 pfn;
  92         unsigned long size = PAGE_SIZE;
  93
  94         pfn = phys_addr >> PAGE_SHIFT;
  95         pte = pte_alloc_kernel_track(pmd, addr, mask);
  96         if (!pte)
  97                 return -ENOMEM;
  98         do {
  99                 BUG_ON(!pte_none(*pte));
 100
 101 #ifdef CONFIG_HUGETLB_PAGE
 102                 size = arch_vmap_pte_range_map_size(addr, end, pfn, max_page_shift);
 103                 if (size != PAGE_SIZE) {
 104                         pte_t entry = pfn_pte(pfn, prot);
 105
 106                         entry = pte_mkhuge(entry);
 107                         entry = arch_make_huge_pte(entry, ilog2(size), 0);
 108                         set_huge_pte_at(&init_mm, addr, pte, entry);
 109                         pfn += PFN_DOWN(size);
 110                         continue;
 111                 }
 112 #endif
 113                 set_pte_at(&init_mm, addr, pte, pfn_pte(pfn, prot));
 114                 pfn++;
 115         } while (pte += PFN_DOWN(size), addr += size, addr != end);
 116         *mask |= PGTBL_PTE_MODIFIED;
 117         return 0;
 118 }
 119
 120 static int vmap_try_huge_pmd(pmd_t *pmd, unsigned long addr, unsigned long end,
 121                         phys_addr_t phys_addr, pgprot_t prot,
 122                         unsigned int max_page_shift)
 123 {
 124         if (max_page_shift < PMD_SHIFT)
 125                 return 0;
 126
 127         if (!arch_vmap_pmd_supported(prot))
 128                 return 0;
 129
 130         if ((end - addr) != PMD_SIZE)
 131                 return 0;
 132
 133         if (!IS_ALIGNED(addr, PMD_SIZE))
 134                 return 0;
 135
 136         if (!IS_ALIGNED(phys_addr, PMD_SIZE))
 137                 return 0;
 138
 139         if (pmd_present(*pmd) && !pmd_free_pte_page(pmd, addr))
 140                 return 0;
 141
 142         return pmd_set_huge(pmd, phys_addr, prot);
 143 }
 144
 145 static int vmap_pmd_range(pud_t *pud, unsigned long addr, unsigned long end,
 146                         phys_addr_t phys_addr, pgprot_t prot,
 147                         unsigned int max_page_shift, pgtbl_mod_mask *mask)
 148 {
 149         pmd_t *pmd;
 150         unsigned long next;
 151
 152         pmd = pmd_alloc_track(&init_mm, pud, addr, mask);
 153         if (!pmd)
 154                 return -ENOMEM;
 155         do {
 156                 next = pmd_addr_end(addr, end);
 157
 158                 if (vmap_try_huge_pmd(pmd, addr, next, phys_addr, prot,
 159                                         max_page_shift)) {
 160                         *mask |= PGTBL_PMD_MODIFIED;
 161                         continue;
 162                 }
 163
 164                 if (vmap_pte_range(pmd, addr, next, phys_addr, prot, max_page_shift, mask))
 165                         return -ENOMEM;
 166         } while (pmd++, phys_addr += (next - addr), addr = next, addr != end);
 167         return 0;
 168 }
 169
 170 static int vmap_try_huge_pud(pud_t *pud, unsigned long addr, unsigned long end,
 171                         phys_addr_t phys_addr, pgprot_t prot,
 172                         unsigned int max_page_shift)
 173 {
 174         if (max_page_shift < PUD_SHIFT)
 175                 return 0;
 176
 177         if (!arch_vmap_pud_supported(prot))
 178                 return 0;
 179
 180         if ((end - addr) != PUD_SIZE)
 181                 return 0;
 182
 183         if (!IS_ALIGNED(addr, PUD_SIZE))
 184                 return 0;
 185
 186         if (!IS_ALIGNED(phys_addr, PUD_SIZE))
 187                 return 0;
 188
 189         if (pud_present(*pud) && !pud_free_pmd_page(pud, addr))
 190                 return 0;
 191
 192         return pud_set_huge(pud, phys_addr, prot);
 193 }
 194
 195 static int vmap_pud_range(p4d_t *p4d, unsigned long addr, unsigned long end,
 196                         phys_addr_t phys_addr, pgprot_t prot,
 197                         unsigned int max_page_shift, pgtbl_mod_mask *mask)
 198 {
 199         pud_t *pud;
 200         unsigned long next;
 201
 202         pud = pud_alloc_track(&init_mm, p4d, addr, mask);
 203         if (!pud)
 204                 return -ENOMEM;
 205         do {
 206                 next = pud_addr_end(addr, end);
 207
 208                 if (vmap_try_huge_pud(pud, addr, next, phys_addr, prot,
 209                                         max_page_shift)) {
 210                         *mask |= PGTBL_PUD_MODIFIED;
 211                         continue;
 212                 }
 213
 214                 if (vmap_pmd_range(pud, addr, next, phys_addr, prot,
 215                                         max_page_shift, mask))
 216                         return -ENOMEM;
 217         } while (pud++, phys_addr += (next - addr), addr = next, addr != end);
 218         return 0;
 219 }
 220
 221 static int vmap_try_huge_p4d(p4d_t *p4d, unsigned long addr, unsigned long end,
 222                         phys_addr_t phys_addr, pgprot_t prot,
 223                         unsigned int max_page_shift)
 224 {
 225         if (max_page_shift < P4D_SHIFT)
 226                 return 0;
 227
 228         if (!arch_vmap_p4d_supported(prot))
 229                 return 0;
 230
 231         if ((end - addr) != P4D_SIZE)
 232                 return 0;
 233
 234         if (!IS_ALIGNED(addr, P4D_SIZE))
 235                 return 0;
 236
 237         if (!IS_ALIGNED(phys_addr, P4D_SIZE))
 238                 return 0;
 239
 240         if (p4d_present(*p4d) && !p4d_free_pud_page(p4d, addr))
 241                 return 0;
 242
 243         return p4d_set_huge(p4d, phys_addr, prot);
 244 }
 245
 246 static int vmap_p4d_range(pgd_t *pgd, unsigned long addr, unsigned long end,
 247                         phys_addr_t phys_addr, pgprot_t prot,
 248                         unsigned int max_page_shift, pgtbl_mod_mask *mask)
 249 {
 250         p4d_t *p4d;
 251         unsigned long next;
 252
 253         p4d = p4d_alloc_track(&init_mm, pgd, addr, mask);
 254         if (!p4d)
 255                 return -ENOMEM;
 256         do {
 257                 next = p4d_addr_end(addr, end);
 258
 259                 if (vmap_try_huge_p4d(p4d, addr, next, phys_addr, prot,
 260                                         max_page_shift)) {
 261                         *mask |= PGTBL_P4D_MODIFIED;
 262                         continue;
 263                 }
 264
 265                 if (vmap_pud_range(p4d, addr, next, phys_addr, prot,
 266                                         max_page_shift, mask))
 267                         return -ENOMEM;
 268         } while (p4d++, phys_addr += (next - addr), addr = next, addr != end);
 269         return 0;
 270 }
 271
 272 static int vmap_range_noflush(unsigned long addr, unsigned long end,
 273                         phys_addr_t phys_addr, pgprot_t prot,
 274                         unsigned int max_page_shift)
 275 {
 276         pgd_t *pgd;
 277         unsigned long start;
 278         unsigned long next;
 279         int err;
 280         pgtbl_mod_mask mask = 0;
 281
 282         might_sleep();
 283         BUG_ON(addr >= end);
 284
 285         start = addr;
 286         pgd = pgd_offset_k(addr);
 287         do {
 288                 next = pgd_addr_end(addr, end);
 289                 err = vmap_p4d_range(pgd, addr, next, phys_addr, prot,
 290                                         max_page_shift, &mask);
 291                 if (err)
 292                         break;
 293         } while (pgd++, phys_addr += (next - addr), addr = next, addr != end);
 294
 295         if (mask & ARCH_PAGE_TABLE_SYNC_MASK)
 296                 arch_sync_kernel_mappings(start, end);
 297
 298         return err;
 299 }
 300
 301 int vmap_range(unsigned long addr, unsigned long end,
 302                         phys_addr_t phys_addr, pgprot_t prot,
 303                         unsigned int max_page_shift)
 304 {
 305         int err;
 306
 307         err = vmap_range_noflush(addr, end, phys_addr, prot, max_page_shift);
 308         flush_cache_vmap(addr, end);
 309
 310         return err;
 311 }
 312
 313 static void vunmap_pte_range(pmd_t *pmd, unsigned long addr, unsigned long end,
 314                              pgtbl_mod_mask *mask)
 315 {
 316         pte_t *pte;
 317
 318         pte = pte_offset_kernel(pmd, addr);
 319         do {
 320                 pte_t ptent = ptep_get_and_clear(&init_mm, addr, pte);
 321                 WARN_ON(!pte_none(ptent) && !pte_present(ptent));
 322         } while (pte++, addr += PAGE_SIZE, addr != end);
 323         *mask |= PGTBL_PTE_MODIFIED;
 324 }
 325
 326 static void vunmap_pmd_range(pud_t *pud, unsigned long addr, unsigned long end,
 327                              pgtbl_mod_mask *mask)
 328 {
 329         pmd_t *pmd;
 330         unsigned long next;
 331         int cleared;
 332
 333         pmd = pmd_offset(pud, addr);
 334         do {
 335                 next = pmd_addr_end(addr, end);
 336
 337                 cleared = pmd_clear_huge(pmd);
 338                 if (cleared || pmd_bad(*pmd))
 339                         *mask |= PGTBL_PMD_MODIFIED;
 340
 341                 if (cleared)
 342                         continue;
 343                 if (pmd_none_or_clear_bad(pmd))
 344                         continue;
 345                 vunmap_pte_range(pmd, addr, next, mask);
 346
 347                 cond_resched();
 348         } while (pmd++, addr = next, addr != end);
 349 }
 350
 351 static void vunmap_pud_range(p4d_t *p4d, unsigned long addr, unsigned long end,
 352                              pgtbl_mod_mask *mask)
 353 {
 354         pud_t *pud;
 355         unsigned long next;
 356         int cleared;
 357
 358         pud = pud_offset(p4d, addr);
 359         do {
 360                 next = pud_addr_end(addr, end);
 361
 362                 cleared = pud_clear_huge(pud);
 363                 if (cleared || pud_bad(*pud))
 364                         *mask |= PGTBL_PUD_MODIFIED;
 365
 366                 if (cleared)
 367                         continue;
 368                 if (pud_none_or_clear_bad(pud))
 369                         continue;
 370                 vunmap_pmd_range(pud, addr, next, mask);
 371         } while (pud++, addr = next, addr != end);
 372 }
 373
 374 static void vunmap_p4d_range(pgd_t *pgd, unsigned long addr, unsigned long end,
 375                              pgtbl_mod_mask *mask)
 376 {
 377         p4d_t *p4d;
 378         unsigned long next;
 379         int cleared;
 380
 381         p4d = p4d_offset(pgd, addr);
 382         do {
 383                 next = p4d_addr_end(addr, end);
 384
 385                 cleared = p4d_clear_huge(p4d);
 386                 if (cleared || p4d_bad(*p4d))
 387                         *mask |= PGTBL_P4D_MODIFIED;
 388
 389                 if (cleared)
 390                         continue;
 391                 if (p4d_none_or_clear_bad(p4d))
 392                         continue;
 393                 vunmap_pud_range(p4d, addr, next, mask);
 394         } while (p4d++, addr = next, addr != end);
 395 }
 396
 397 /*
 398  * vunmap_range_noflush is similar to vunmap_range, but does not
 399  * flush caches or TLBs.
 400  *
 401  * The caller is responsible for calling flush_cache_vmap() before calling
 402  * this function, and flush_tlb_kernel_range after it has returned
 403  * successfully (and before the addresses are expected to cause a page fault
 404  * or be re-mapped for something else, if TLB flushes are being delayed or
 405  * coalesced).
 406  *
 407  * This is an internal function only. Do not use outside mm/.
 408  */
 409 void vunmap_range_noflush(unsigned long start, unsigned long end)
 410 {
 411         unsigned long next;
 412         pgd_t *pgd;
 413         unsigned long addr = start;
 414         pgtbl_mod_mask mask = 0;
 415
 416         BUG_ON(addr >= end);
 417         pgd = pgd_offset_k(addr);
 418         do {
 419                 next = pgd_addr_end(addr, end);
 420                 if (pgd_bad(*pgd))
 421                         mask |= PGTBL_PGD_MODIFIED;
 422                 if (pgd_none_or_clear_bad(pgd))
 423                         continue;
 424                 vunmap_p4d_range(pgd, addr, next, &mask);
 425         } while (pgd++, addr = next, addr != end);
 426
 427         if (mask & ARCH_PAGE_TABLE_SYNC_MASK)
 428                 arch_sync_kernel_mappings(start, end);
 429 }
 430
 431 /**
 432  * vunmap_range - unmap kernel virtual addresses
 433  * @addr: start of the VM area to unmap
 434  * @end: end of the VM area to unmap (non-inclusive)
 435  *
 436  * Clears any present PTEs in the virtual address range, flushes TLBs and
 437  * caches. Any subsequent access to the address before it has been re-mapped
 438  * is a kernel bug.
 439  */
 440 void vunmap_range(unsigned long addr, unsigned long end)
 441 {
 442         flush_cache_vunmap(addr, end);
 443         vunmap_range_noflush(addr, end);
 444         flush_tlb_kernel_range(addr, end);
 445 }
 446
 447 static int vmap_pages_pte_range(pmd_t *pmd, unsigned long addr,
 448                 unsigned long end, pgprot_t prot, struct page **pages, int *nr,
 449                 pgtbl_mod_mask *mask)
 450 {
 451         pte_t *pte;
 452
 453         /*
 454          * nr is a running index into the array which helps higher level
 455          * callers keep track of where we're up to.
 456          */
 457
 458         pte = pte_alloc_kernel_track(pmd, addr, mask);
 459         if (!pte)
 460                 return -ENOMEM;
 461         do {
 462                 struct page *page = pages[*nr];
 463
 464                 if (WARN_ON(!pte_none(*pte)))
 465                         return -EBUSY;
 466                 if (WARN_ON(!page))
 467                         return -ENOMEM;
 468                 set_pte_at(&init_mm, addr, pte, mk_pte(page, prot));
 469                 (*nr)++;
 470         } while (pte++, addr += PAGE_SIZE, addr != end);
 471         *mask |= PGTBL_PTE_MODIFIED;
 472         return 0;
 473 }
 474
 475 static int vmap_pages_pmd_range(pud_t *pud, unsigned long addr,
 476                 unsigned long end, pgprot_t prot, struct page **pages, int *nr,
 477                 pgtbl_mod_mask *mask)
 478 {
 479         pmd_t *pmd;
 480         unsigned long next;
 481
 482         pmd = pmd_alloc_track(&init_mm, pud, addr, mask);
 483         if (!pmd)
 484                 return -ENOMEM;
 485         do {
 486                 next = pmd_addr_end(addr, end);
 487                 if (vmap_pages_pte_range(pmd, addr, next, prot, pages, nr, mask))
 488                         return -ENOMEM;
 489         } while (pmd++, addr = next, addr != end);
 490         return 0;
 491 }
 492
 493 static int vmap_pages_pud_range(p4d_t *p4d, unsigned long addr,
 494                 unsigned long end, pgprot_t prot, struct page **pages, int *nr,
 495                 pgtbl_mod_mask *mask)
 496 {
 497         pud_t *pud;
 498         unsigned long next;
 499
 500         pud = pud_alloc_track(&init_mm, p4d, addr, mask);
 501         if (!pud)
 502                 return -ENOMEM;
 503         do {
 504                 next = pud_addr_end(addr, end);
 505                 if (vmap_pages_pmd_range(pud, addr, next, prot, pages, nr, mask))
 506                         return -ENOMEM;
 507         } while (pud++, addr = next, addr != end);
 508         return 0;
 509 }
 510
 511 static int vmap_pages_p4d_range(pgd_t *pgd, unsigned long addr,
 512                 unsigned long end, pgprot_t prot, struct page **pages, int *nr,
 513                 pgtbl_mod_mask *mask)
 514 {
 515         p4d_t *p4d;
 516         unsigned long next;
 517
 518         p4d = p4d_alloc_track(&init_mm, pgd, addr, mask);
 519         if (!p4d)
 520                 return -ENOMEM;
 521         do {
 522                 next = p4d_addr_end(addr, end);
 523                 if (vmap_pages_pud_range(p4d, addr, next, prot, pages, nr, mask))
 524                         return -ENOMEM;
 525         } while (p4d++, addr = next, addr != end);
 526         return 0;
 527 }
 528
 529 static int vmap_small_pages_range_noflush(unsigned long addr, unsigned long end,
 530                 pgprot_t prot, struct page **pages)
 531 {
 532         unsigned long start = addr;
 533         pgd_t *pgd;
 534         unsigned long next;
 535         int err = 0;
 536         int nr = 0;
 537         pgtbl_mod_mask mask = 0;
 538
 539         BUG_ON(addr >= end);
 540         pgd = pgd_offset_k(addr);
 541         do {
 542                 next = pgd_addr_end(addr, end);
 543                 if (pgd_bad(*pgd))
 544                         mask |= PGTBL_PGD_MODIFIED;
 545                 err = vmap_pages_p4d_range(pgd, addr, next, prot, pages, &nr, &mask);
 546                 if (err)
 547                         return err;
 548         } while (pgd++, addr = next, addr != end);
 549
 550         if (mask & ARCH_PAGE_TABLE_SYNC_MASK)
 551                 arch_sync_kernel_mappings(start, end);
 552
 553         return 0;
 554 }
 555
 556 /*
 557  * vmap_pages_range_noflush is similar to vmap_pages_range, but does not
 558  * flush caches.
 559  *
 560  * The caller is responsible for calling flush_cache_vmap() after this
 561  * function returns successfully and before the addresses are accessed.
 562  *
 563  * This is an internal function only. Do not use outside mm/.
 564  */
 565 int vmap_pages_range_noflush(unsigned long addr, unsigned long end,
 566                 pgprot_t prot, struct page **pages, unsigned int page_shift)
 567 {
 568         unsigned int i, nr = (end - addr) >> PAGE_SHIFT;
 569
 570         WARN_ON(page_shift < PAGE_SHIFT);
 571
 572         if (!IS_ENABLED(CONFIG_HAVE_ARCH_HUGE_VMALLOC) ||
 573                         page_shift == PAGE_SHIFT)
 574                 return vmap_small_pages_range_noflush(addr, end, prot, pages);
 575
 576         for (i = 0; i < nr; i += 1U << (page_shift - PAGE_SHIFT)) {
 577                 int err;
 578
 579                 err = vmap_range_noflush(addr, addr + (1UL << page_shift),
 580                                         __pa(page_address(pages[i])), prot,
 581                                         page_shift);
 582                 if (err)
 583                         return err;
 584
 585                 addr += 1UL << page_shift;
 586         }
 587
 588         return 0;
 589 }
 590
 591 /**
 592  * vmap_pages_range - map pages to a kernel virtual address
 593  * @addr: start of the VM area to map
 594  * @end: end of the VM area to map (non-inclusive)
 595  * @prot: page protection flags to use
 596  * @pages: pages to map (always PAGE_SIZE pages)
 597  * @page_shift: maximum shift that the pages may be mapped with, @pages must
 598  * be aligned and contiguous up to at least this shift.
 599  *
 600  * RETURNS:
 601  * 0 on success, -errno on failure.
 602  */
 603 static int vmap_pages_range(unsigned long addr, unsigned long end,
 604                 pgprot_t prot, struct page **pages, unsigned int page_shift)
 605 {
 606         int err;
 607
 608         err = vmap_pages_range_noflush(addr, end, prot, pages, page_shift);
 609         flush_cache_vmap(addr, end);
 610         return err;
 611 }
 612
 613 int is_vmalloc_or_module_addr(const void *x)
 614 {
 615         /*
 616          * ARM, x86-64 and sparc64 put modules in a special place,
 617          * and fall back on vmalloc() if that fails. Others
 618          * just put it in the vmalloc space.
 619          */
 620 #if defined(CONFIG_MODULES) && defined(MODULES_VADDR)
 621         unsigned long addr = (unsigned long)x;
 622         if (addr >= MODULES_VADDR && addr < MODULES_END)
 623                 return 1;
 624 #endif
 625         return is_vmalloc_addr(x);
 626 }
 627
 628 /*
 629  * Walk a vmap address to the struct page it maps. Huge vmap mappings will
 630  * return the tail page that corresponds to the base page address, which
 631  * matches small vmap mappings.
 632  */
 633 struct page *vmalloc_to_page(const void *vmalloc_addr)
 634 {
 635         unsigned long addr = (unsigned long) vmalloc_addr;
 636         struct page *page = NULL;
 637         pgd_t *pgd = pgd_offset_k(addr);
 638         p4d_t *p4d;
 639         pud_t *pud;
 640         pmd_t *pmd;
 641         pte_t *ptep, pte;
 642
 643         /*
 644          * XXX we might need to change this if we add VIRTUAL_BUG_ON for
 645          * architectures that do not vmalloc module space
 646          */
 647         VIRTUAL_BUG_ON(!is_vmalloc_or_module_addr(vmalloc_addr));
 648
 649         if (pgd_none(*pgd))
 650                 return NULL;
 651         if (WARN_ON_ONCE(pgd_leaf(*pgd)))
 652                 return NULL; /* XXX: no allowance for huge pgd */
 653         if (WARN_ON_ONCE(pgd_bad(*pgd)))
 654                 return NULL;
 655
 656         p4d = p4d_offset(pgd, addr);
 657         if (p4d_none(*p4d))
 658                 return NULL;
 659         if (p4d_leaf(*p4d))
 660                 return p4d_page(*p4d) + ((addr & ~P4D_MASK) >> PAGE_SHIFT);
 661         if (WARN_ON_ONCE(p4d_bad(*p4d)))
 662                 return NULL;
 663
 664         pud = pud_offset(p4d, addr);
 665         if (pud_none(*pud))
 666                 return NULL;
 667         if (pud_leaf(*pud))
 668                 return pud_page(*pud) + ((addr & ~PUD_MASK) >> PAGE_SHIFT);
 669         if (WARN_ON_ONCE(pud_bad(*pud)))
 670                 return NULL;
 671
 672         pmd = pmd_offset(pud, addr);
 673         if (pmd_none(*pmd))
 674                 return NULL;
 675         if (pmd_leaf(*pmd))
 676                 return pmd_page(*pmd) + ((addr & ~PMD_MASK) >> PAGE_SHIFT);
 677         if (WARN_ON_ONCE(pmd_bad(*pmd)))
 678                 return NULL;
 679
 680         ptep = pte_offset_map(pmd, addr);
 681         pte = *ptep;
 682         if (pte_present(pte))
 683                 page = pte_page(pte);
 684         pte_unmap(ptep);
 685
 686         return page;
 687 }
 688 EXPORT_SYMBOL(vmalloc_to_page);
 689
 690 /*
 691  * Map a vmalloc()-space virtual address to the physical page frame number.
 692  */
 693 unsigned long vmalloc_to_pfn(const void *vmalloc_addr)
 694 {
 695         return page_to_pfn(vmalloc_to_page(vmalloc_addr));
 696 }
 697 EXPORT_SYMBOL(vmalloc_to_pfn);
 698
 699
 700 /*** Global kva allocator ***/
 701
 702 #define DEBUG_AUGMENT_PROPAGATE_CHECK 0
 703 #define DEBUG_AUGMENT_LOWEST_MATCH_CHECK 0
 704
 705
 706 static DEFINE_SPINLOCK(vmap_area_lock);
 707 static DEFINE_SPINLOCK(free_vmap_area_lock);
 708 /* Export for kexec only */
 709 LIST_HEAD(vmap_area_list);
 710 static struct rb_root vmap_area_root = RB_ROOT;
 711 static bool vmap_initialized __read_mostly;
 712
 713 static struct rb_root purge_vmap_area_root = RB_ROOT;
 714 static LIST_HEAD(purge_vmap_area_list);
 715 static DEFINE_SPINLOCK(purge_vmap_area_lock);
 716
 717 /*
 718  * This kmem_cache is used for vmap_area objects. Instead of
 719  * allocating from slab we reuse an object from this cache to
 720  * make things faster. Especially in "no edge" splitting of
 721  * free block.
 722  */
 723 static struct kmem_cache *vmap_area_cachep;
 724
 725 /*
 726  * This linked list is used in pair with free_vmap_area_root.
 727  * It gives O(1) access to prev/next to perform fast coalescing.
 728  */
 729 static LIST_HEAD(free_vmap_area_list);
 730
 731 /*
 732  * This augment red-black tree represents the free vmap space.
 733  * All vmap_area objects in this tree are sorted by va->va_start
 734  * address. It is used for allocation and merging when a vmap
 735  * object is released.
 736  *
 737  * Each vmap_area node contains a maximum available free block
 738  * of its sub-tree, right or left. Therefore it is possible to
 739  * find a lowest match of free area.
 740  */
 741 static struct rb_root free_vmap_area_root = RB_ROOT;
 742
 743 /*
 744  * Preload a CPU with one object for "no edge" split case. The
 745  * aim is to get rid of allocations from the atomic context, thus
 746  * to use more permissive allocation masks.
 747  */
 748 static DEFINE_PER_CPU(struct vmap_area *, ne_fit_preload_node);
 749
 750 static __always_inline unsigned long
 751 va_size(struct vmap_area *va)
 752 {
 753         return (va->va_end - va->va_start);
 754 }
 755
 756 static __always_inline unsigned long
 757 get_subtree_max_size(struct rb_node *node)
 758 {
 759         struct vmap_area *va;
 760
 761         va = rb_entry_safe(node, struct vmap_area, rb_node);
 762         return va ? va->subtree_max_size : 0;
 763 }
 764
 765 /*
 766  * Gets called when remove the node and rotate.
 767  */
 768 static __always_inline unsigned long
 769 compute_subtree_max_size(struct vmap_area *va)
 770 {
 771         return max3(va_size(va),
 772                 get_subtree_max_size(va->rb_node.rb_left),
 773                 get_subtree_max_size(va->rb_node.rb_right));
 774 }
 775
 776 RB_DECLARE_CALLBACKS_MAX(static, free_vmap_area_rb_augment_cb,
 777         struct vmap_area, rb_node, unsigned long, subtree_max_size, va_size)
 778
 779 static void purge_vmap_area_lazy(void);
 780 static BLOCKING_NOTIFIER_HEAD(vmap_notify_list);
 781 static unsigned long lazy_max_pages(void);
 782
 783 static atomic_long_t nr_vmalloc_pages;
 784
 785 unsigned long vmalloc_nr_pages(void)
 786 {
 787         return atomic_long_read(&nr_vmalloc_pages);
 788 }
 789
 790 static struct vmap_area *__find_vmap_area(unsigned long addr)
 791 {
 792         struct rb_node *n = vmap_area_root.rb_node;
 793
 794         while (n) {
 795                 struct vmap_area *va;
 796
 797                 va = rb_entry(n, struct vmap_area, rb_node);
 798                 if (addr < va->va_start)
 799                         n = n->rb_left;
 800                 else if (addr >= va->va_end)
 801                         n = n->rb_right;
 802                 else
 803                         return va;
 804         }
 805
 806         return NULL;
 807 }
 808
 809 /*
 810  * This function returns back addresses of parent node
 811  * and its left or right link for further processing.
 812  *
 813  * Otherwise NULL is returned. In that case all further
 814  * steps regarding inserting of conflicting overlap range
 815  * have to be declined and actually considered as a bug.
 816  */
 817 static __always_inline struct rb_node **
 818 find_va_links(struct vmap_area *va,
 819         struct rb_root *root, struct rb_node *from,
 820         struct rb_node **parent)
 821 {
 822         struct vmap_area *tmp_va;
 823         struct rb_node **link;
 824
 825         if (root) {
 826                 link = &root->rb_node;
 827                 if (unlikely(!*link)) {
 828                         *parent = NULL;
 829                         return link;
 830                 }
 831         } else {
 832                 link = &from;
 833         }
 834
 835         /*
 836          * Go to the bottom of the tree. When we hit the last point
 837          * we end up with parent rb_node and correct direction, i name
 838          * it link, where the new va->rb_node will be attached to.
 839          */
 840         do {
 841                 tmp_va = rb_entry(*link, struct vmap_area, rb_node);
 842
 843                 /*
 844                  * During the traversal we also do some sanity check.
 845                  * Trigger the BUG() if there are sides(left/right)
 846                  * or full overlaps.
 847                  */
 848                 if (va->va_start < tmp_va->va_end &&
 849                                 va->va_end <= tmp_va->va_start)
 850                         link = &(*link)->rb_left;
 851                 else if (va->va_end > tmp_va->va_start &&
 852                                 va->va_start >= tmp_va->va_end)
 853                         link = &(*link)->rb_right;
 854                 else {
 855                         WARN(1, "vmalloc bug: 0x%lx-0x%lx overlaps with 0x%lx-0x%lx\n",
 856                                 va->va_start, va->va_end, tmp_va->va_start, tmp_va->va_end);
 857
 858                         return NULL;
 859                 }
 860         } while (*link);
 861
 862         *parent = &tmp_va->rb_node;
 863         return link;
 864 }
 865
 866 static __always_inline struct list_head *
 867 get_va_next_sibling(struct rb_node *parent, struct rb_node **link)
 868 {
 869         struct list_head *list;
 870
 871         if (unlikely(!parent))
 872                 /*
 873                  * The red-black tree where we try to find VA neighbors
 874                  * before merging or inserting is empty, i.e. it means
 875                  * there is no free vmap space. Normally it does not
 876                  * happen but we handle this case anyway.
 877                  */
 878                 return NULL;
 879
 880         list = &rb_entry(parent, struct vmap_area, rb_node)->list;
 881         return (&parent->rb_right == link ? list->next : list);
 882 }
 883
 884 static __always_inline void
 885 link_va(struct vmap_area *va, struct rb_root *root,
 886         struct rb_node *parent, struct rb_node **link, struct list_head *head)
 887 {
 888         /*
 889          * VA is still not in the list, but we can
 890          * identify its future previous list_head node.
 891          */
 892         if (likely(parent)) {
 893                 head = &rb_entry(parent, struct vmap_area, rb_node)->list;
 894                 if (&parent->rb_right != link)
 895                         head = head->prev;
 896         }
 897
 898         /* Insert to the rb-tree */
 899         rb_link_node(&va->rb_node, parent, link);
 900         if (root == &free_vmap_area_root) {
 901                 /*
 902                  * Some explanation here. Just perform simple insertion
 903                  * to the tree. We do not set va->subtree_max_size to
 904                  * its current size before calling rb_insert_augmented().
 905                  * It is because of we populate the tree from the bottom
 906                  * to parent levels when the node _is_ in the tree.
 907                  *
 908                  * Therefore we set subtree_max_size to zero after insertion,
 909                  * to let __augment_tree_propagate_from() puts everything to
 910                  * the correct order later on.
 911                  */
 912                 rb_insert_augmented(&va->rb_node,
 913                         root, &free_vmap_area_rb_augment_cb);
 914                 va->subtree_max_size = 0;
 915         } else {
 916                 rb_insert_color(&va->rb_node, root);
 917         }
 918
 919         /* Address-sort this list */
 920         list_add(&va->list, head);
 921 }
 922
 923 static __always_inline void
 924 unlink_va(struct vmap_area *va, struct rb_root *root)
 925 {
 926         if (WARN_ON(RB_EMPTY_NODE(&va->rb_node)))
 927                 return;
 928
 929         if (root == &free_vmap_area_root)
 930                 rb_erase_augmented(&va->rb_node,
 931                         root, &free_vmap_area_rb_augment_cb);
 932         else
 933                 rb_erase(&va->rb_node, root);
 934
 935         list_del(&va->list);
 936         RB_CLEAR_NODE(&va->rb_node);
 937 }
 938
 939 #if DEBUG_AUGMENT_PROPAGATE_CHECK
 940 static void
 941 augment_tree_propagate_check(void)
 942 {
 943         struct vmap_area *va;
 944         unsigned long computed_size;
 945
 946         list_for_each_entry(va, &free_vmap_area_list, list) {
 947                 computed_size = compute_subtree_max_size(va);
 948                 if (computed_size != va->subtree_max_size)
 949                         pr_emerg("tree is corrupted: %lu, %lu\n",
 950                                 va_size(va), va->subtree_max_size);
 951         }
 952 }
 953 #endif
 954
 955 /*
 956  * This function populates subtree_max_size from bottom to upper
 957  * levels starting from VA point. The propagation must be done
 958  * when VA size is modified by changing its va_start/va_end. Or
 959  * in case of newly inserting of VA to the tree.
 960  *
 961  * It means that __augment_tree_propagate_from() must be called:
 962  * - After VA has been inserted to the tree(free path);
 963  * - After VA has been shrunk(allocation path);
 964  * - After VA has been increased(merging path).
 965  *
 966  * Please note that, it does not mean that upper parent nodes
 967  * and their subtree_max_size are recalculated all the time up
 968  * to the root node.
 969  *
 970  *       4--8
 971  *        /\
 972  *       /  \
 973  *      /    \
 974  *    2--2  8--8
 975  *
 976  * For example if we modify the node 4, shrinking it to 2, then
 977  * no any modification is required. If we shrink the node 2 to 1
 978  * its subtree_max_size is updated only, and set to 1. If we shrink
 979  * the node 8 to 6, then its subtree_max_size is set to 6 and parent
 980  * node becomes 4--6.
 981  */
 982 static __always_inline void
 983 augment_tree_propagate_from(struct vmap_area *va)
 984 {
 985         /*
 986          * Populate the tree from bottom towards the root until
 987          * the calculated maximum available size of checked node
 988          * is equal to its current one.
 989          */
 990         free_vmap_area_rb_augment_cb_propagate(&va->rb_node, NULL);
 991
 992 #if DEBUG_AUGMENT_PROPAGATE_CHECK
 993         augment_tree_propagate_check();
 994 #endif
 995 }
 996
 997 static void
 998 insert_vmap_area(struct vmap_area *va,
 999         struct rb_root *root, struct list_head *head)
1000 {
1001         struct rb_node **link;
1002         struct rb_node *parent;
1003
1004         link = find_va_links(va, root, NULL, &parent);
1005         if (link)
1006                 link_va(va, root, parent, link, head);
1007 }
1008
1009 static void
1010 insert_vmap_area_augment(struct vmap_area *va,
1011         struct rb_node *from, struct rb_root *root,
1012         struct list_head *head)
1013 {
1014         struct rb_node **link;
1015         struct rb_node *parent;
1016
1017         if (from)
1018                 link = find_va_links(va, NULL, from, &parent);
1019         else
1020                 link = find_va_links(va, root, NULL, &parent);
1021
1022         if (link) {
1023                 link_va(va, root, parent, link, head);
1024                 augment_tree_propagate_from(va);
1025         }
1026 }
1027
1028 /*
1029  * Merge de-allocated chunk of VA memory with previous
1030  * and next free blocks. If coalesce is not done a new
1031  * free area is inserted. If VA has been merged, it is
1032  * freed.
1033  *
1034  * Please note, it can return NULL in case of overlap
1035  * ranges, followed by WARN() report. Despite it is a
1036  * buggy behaviour, a system can be alive and keep
1037  * ongoing.
1038  */
1039 static __always_inline struct vmap_area *
1040 merge_or_add_vmap_area(struct vmap_area *va,
1041         struct rb_root *root, struct list_head *head)
1042 {
1043         struct vmap_area *sibling;
1044         struct list_head *next;
1045         struct rb_node **link;
1046         struct rb_node *parent;
1047         bool merged = false;
1048
1049         /*
1050          * Find a place in the tree where VA potentially will be
1051          * inserted, unless it is merged with its sibling/siblings.
1052          */
1053         link = find_va_links(va, root, NULL, &parent);
1054         if (!link)
1055                 return NULL;
1056
1057         /*
1058          * Get next node of VA to check if merging can be done.
1059          */
1060         next = get_va_next_sibling(parent, link);
1061         if (unlikely(next == NULL))
1062                 goto insert;
1063
1064         /*
1065          * start            end
1066          * |                |
1067          * |<------VA------>|<-----Next----->|
1068          *                  |                |
1069          *                  start            end
1070          */
1071         if (next != head) {
1072                 sibling = list_entry(next, struct vmap_area, list);
1073                 if (sibling->va_start == va->va_end) {
1074                         sibling->va_start = va->va_start;
1075
1076                         /* Free vmap_area object. */
1077                         kmem_cache_free(vmap_area_cachep, va);
1078
1079                         /* Point to the new merged area. */
1080                         va = sibling;
1081                         merged = true;
1082                 }
1083         }
1084
1085         /*
1086          * start            end
1087          * |                |
1088          * |<-----Prev----->|<------VA------>|
1089          *                  |                |
1090          *                  start            end
1091          */
1092         if (next->prev != head) {
1093                 sibling = list_entry(next->prev, struct vmap_area, list);
1094                 if (sibling->va_end == va->va_start) {
1095                         /*
1096                          * If both neighbors are coalesced, it is important
1097                          * to unlink the "next" node first, followed by merging
1098                          * with "previous" one. Otherwise the tree might not be
1099                          * fully populated if a sibling's augmented value is
1100                          * "normalized" because of rotation operations.
1101                          */
1102                         if (merged)
1103                                 unlink_va(va, root);
1104
1105                         sibling->va_end = va->va_end;
1106
1107                         /* Free vmap_area object. */
1108                         kmem_cache_free(vmap_area_cachep, va);
1109
1110                         /* Point to the new merged area. */
1111                         va = sibling;
1112                         merged = true;
1113                 }
1114         }
1115
1116 insert:
1117         if (!merged)
1118                 link_va(va, root, parent, link, head);
1119
1120         return va;
1121 }
1122
1123 static __always_inline struct vmap_area *
1124 merge_or_add_vmap_area_augment(struct vmap_area *va,
1125         struct rb_root *root, struct list_head *head)
1126 {
1127         va = merge_or_add_vmap_area(va, root, head);
1128         if (va)
1129                 augment_tree_propagate_from(va);
1130
1131         return va;
1132 }
1133
1134 static __always_inline bool
1135 is_within_this_va(struct vmap_area *va, unsigned long size,
1136         unsigned long align, unsigned long vstart)
1137 {
1138         unsigned long nva_start_addr;
1139
1140         if (va->va_start > vstart)
1141                 nva_start_addr = ALIGN(va->va_start, align);
1142         else
1143                 nva_start_addr = ALIGN(vstart, align);
1144
1145         /* Can be overflowed due to big size or alignment. */
1146         if (nva_start_addr + size < nva_start_addr ||
1147                         nva_start_addr < vstart)
1148                 return false;
1149
1150         return (nva_start_addr + size <= va->va_end);
1151 }
1152
1153 /*
1154  * Find the first free block(lowest start address) in the tree,
1155  * that will accomplish the request corresponding to passing
1156  * parameters.
1157  */
1158 static __always_inline struct vmap_area *
1159 find_vmap_lowest_match(unsigned long size,
1160         unsigned long align, unsigned long vstart)
1161 {
1162         struct vmap_area *va;
1163         struct rb_node *node;
1164         unsigned long length;
1165
1166         /* Start from the root. */
1167         node = free_vmap_area_root.rb_node;
1168
1169         /* Adjust the search size for alignment overhead. */
1170         length = size + align - 1;
1171
1172         while (node) {
1173                 va = rb_entry(node, struct vmap_area, rb_node);
1174
1175                 if (get_subtree_max_size(node->rb_left) >= length &&
1176                                 vstart < va->va_start) {
1177                         node = node->rb_left;
1178                 } else {
1179                         if (is_within_this_va(va, size, align, vstart))
1180                                 return va;
1181
1182                         /*
1183                          * Does not make sense to go deeper towards the right
1184                          * sub-tree if it does not have a free block that is
1185                          * equal or bigger to the requested search length.
1186                          */
1187                         if (get_subtree_max_size(node->rb_right) >= length) {
1188                                 node = node->rb_right;
1189                                 continue;
1190                         }
1191
1192                         /*
1193                          * OK. We roll back and find the first right sub-tree,
1194                          * that will satisfy the search criteria. It can happen
1195                          * only once due to "vstart" restriction.
1196                          */
1197                         while ((node = rb_parent(node))) {
1198                                 va = rb_entry(node, struct vmap_area, rb_node);
1199                                 if (is_within_this_va(va, size, align, vstart))
1200                                         return va;
1201
1202                                 if (get_subtree_max_size(node->rb_right) >= length &&
1203                                                 vstart <= va->va_start) {
1204                                         node = node->rb_right;
1205                                         break;
1206                                 }
1207                         }
1208                 }
1209         }
1210
1211         return NULL;
1212 }
1213
1214 #if DEBUG_AUGMENT_LOWEST_MATCH_CHECK
1215 #include <linux/random.h>
1216
1217 static struct vmap_area *
1218 find_vmap_lowest_linear_match(unsigned long size,
1219         unsigned long align, unsigned long vstart)
1220 {
1221         struct vmap_area *va;
1222
1223         list_for_each_entry(va, &free_vmap_area_list, list) {
1224                 if (!is_within_this_va(va, size, align, vstart))
1225                         continue;
1226
1227                 return va;
1228         }
1229
1230         return NULL;
1231 }
1232
1233 static void
1234 find_vmap_lowest_match_check(unsigned long size)
1235 {
1236         struct vmap_area *va_1, *va_2;
1237         unsigned long vstart;
1238         unsigned int rnd;
1239
1240         get_random_bytes(&rnd, sizeof(rnd));
1241         vstart = VMALLOC_START + rnd;
1242
1243         va_1 = find_vmap_lowest_match(size, 1, vstart);
1244         va_2 = find_vmap_lowest_linear_match(size, 1, vstart);
1245
1246         if (va_1 != va_2)
1247                 pr_emerg("not lowest: t: 0x%p, l: 0x%p, v: 0x%lx\n",
1248                         va_1, va_2, vstart);
1249 }
1250 #endif
1251
1252 enum fit_type {
1253         NOTHING_FIT = 0,
1254         FL_FIT_TYPE = 1,        /* full fit */
1255         LE_FIT_TYPE = 2,        /* left edge fit */
1256         RE_FIT_TYPE = 3,        /* right edge fit */
1257         NE_FIT_TYPE = 4         /* no edge fit */
1258 };
1259
1260 static __always_inline enum fit_type
1261 classify_va_fit_type(struct vmap_area *va,
1262         unsigned long nva_start_addr, unsigned long size)
1263 {
1264         enum fit_type type;
1265
1266         /* Check if it is within VA. */
1267         if (nva_start_addr < va->va_start ||
1268                         nva_start_addr + size > va->va_end)
1269                 return NOTHING_FIT;
1270
1271         /* Now classify. */
1272         if (va->va_start == nva_start_addr) {
1273                 if (va->va_end == nva_start_addr + size)
1274                         type = FL_FIT_TYPE;
1275                 else
1276                         type = LE_FIT_TYPE;
1277         } else if (va->va_end == nva_start_addr + size) {
1278                 type = RE_FIT_TYPE;
1279         } else {
1280                 type = NE_FIT_TYPE;
1281         }
1282
1283         return type;
1284 }
1285
1286 static __always_inline int
1287 adjust_va_to_fit_type(struct vmap_area *va,
1288         unsigned long nva_start_addr, unsigned long size,
1289         enum fit_type type)
1290 {
1291         struct vmap_area *lva = NULL;
1292
1293         if (type == FL_FIT_TYPE) {
1294                 /*
1295                  * No need to split VA, it fully fits.
1296                  *
1297                  * |               |
1298                  * V      NVA      V
1299                  * |---------------|
1300                  */
1301                 unlink_va(va, &free_vmap_area_root);
1302                 kmem_cache_free(vmap_area_cachep, va);
1303         } else if (type == LE_FIT_TYPE) {
1304                 /*
1305                  * Split left edge of fit VA.
1306                  *
1307                  * |       |
1308                  * V  NVA  V   R
1309                  * |-------|-------|
1310                  */
1311                 va->va_start += size;
1312         } else if (type == RE_FIT_TYPE) {
1313                 /*
1314                  * Split right edge of fit VA.
1315                  *
1316                  *         |       |
1317                  *     L   V  NVA  V
1318                  * |-------|-------|
1319                  */
1320                 va->va_end = nva_start_addr;
1321         } else if (type == NE_FIT_TYPE) {
1322                 /*
1323                  * Split no edge of fit VA.
1324                  *
1325                  *     |       |
1326                  *   L V  NVA  V R
1327                  * |---|-------|---|
1328                  */
1329                 lva = __this_cpu_xchg(ne_fit_preload_node, NULL);
1330                 if (unlikely(!lva)) {
1331                         /*
1332                          * For percpu allocator we do not do any pre-allocation
1333                          * and leave it as it is. The reason is it most likely
1334                          * never ends up with NE_FIT_TYPE splitting. In case of
1335                          * percpu allocations offsets and sizes are aligned to
1336                          * fixed align request, i.e. RE_FIT_TYPE and FL_FIT_TYPE
1337                          * are its main fitting cases.
1338                          *
1339                          * There are a few exceptions though, as an example it is
1340                          * a first allocation (early boot up) when we have "one"
1341                          * big free space that has to be split.
1342                          *
1343                          * Also we can hit this path in case of regular "vmap"
1344                          * allocations, if "this" current CPU was not preloaded.
1345                          * See the comment in alloc_vmap_area() why. If so, then
1346                          * GFP_NOWAIT is used instead to get an extra object for
1347                          * split purpose. That is rare and most time does not
1348                          * occur.
1349                          *
1350                          * What happens if an allocation gets failed. Basically,
1351                          * an "overflow" path is triggered to purge lazily freed
1352                          * areas to free some memory, then, the "retry" path is
1353                          * triggered to repeat one more time. See more details
1354                          * in alloc_vmap_area() function.
1355                          */
1356                         lva = kmem_cache_alloc(vmap_area_cachep, GFP_NOWAIT);
1357                         if (!lva)
1358                                 return -1;
1359                 }
1360
1361                 /*
1362                  * Build the remainder.
1363                  */
1364                 lva->va_start = va->va_start;
1365                 lva->va_end = nva_start_addr;
1366
1367                 /*
1368                  * Shrink this VA to remaining size.
1369                  */
1370                 va->va_start = nva_start_addr + size;
1371         } else {
1372                 return -1;
1373         }
1374
1375         if (type != FL_FIT_TYPE) {
1376                 augment_tree_propagate_from(va);
1377
1378                 if (lva)        /* type == NE_FIT_TYPE */
1379                         insert_vmap_area_augment(lva, &va->rb_node,
1380                                 &free_vmap_area_root, &free_vmap_area_list);
1381         }
1382
1383         return 0;
1384 }
1385
1386 /*
1387  * Returns a start address of the newly allocated area, if success.
1388  * Otherwise a vend is returned that indicates failure.
1389  */
1390 static __always_inline unsigned long
1391 __alloc_vmap_area(unsigned long size, unsigned long align,
1392         unsigned long vstart, unsigned long vend)
1393 {
1394         unsigned long nva_start_addr;
1395         struct vmap_area *va;
1396         enum fit_type type;
1397         int ret;
1398
1399         va = find_vmap_lowest_match(size, align, vstart);
1400         if (unlikely(!va))
1401                 return vend;
1402
1403         if (va->va_start > vstart)
1404                 nva_start_addr = ALIGN(va->va_start, align);
1405         else
1406                 nva_start_addr = ALIGN(vstart, align);
1407
1408         /* Check the "vend" restriction. */
1409         if (nva_start_addr + size > vend)
1410                 return vend;
1411
1412         /* Classify what we have found. */
1413         type = classify_va_fit_type(va, nva_start_addr, size);
1414         if (WARN_ON_ONCE(type == NOTHING_FIT))
1415                 return vend;
1416
1417         /* Update the free vmap_area. */
1418         ret = adjust_va_to_fit_type(va, nva_start_addr, size, type);
1419         if (ret)
1420                 return vend;
1421
1422 #if DEBUG_AUGMENT_LOWEST_MATCH_CHECK
1423         find_vmap_lowest_match_check(size);
1424 #endif
1425
1426         return nva_start_addr;
1427 }
1428
1429 /*
1430  * Free a region of KVA allocated by alloc_vmap_area
1431  */
1432 static void free_vmap_area(struct vmap_area *va)
1433 {
1434         /*
1435          * Remove from the busy tree/list.
1436          */
1437         spin_lock(&vmap_area_lock);
1438         unlink_va(va, &vmap_area_root);
1439         spin_unlock(&vmap_area_lock);
1440
1441         /*
1442          * Insert/Merge it back to the free tree/list.
1443          */
1444         spin_lock(&free_vmap_area_lock);
1445         merge_or_add_vmap_area_augment(va, &free_vmap_area_root, &free_vmap_area_list);
1446         spin_unlock(&free_vmap_area_lock);
1447 }
1448
1449 static inline void
1450 preload_this_cpu_lock(spinlock_t *lock, gfp_t gfp_mask, int node)
1451 {
1452         struct vmap_area *va = NULL;
1453
1454         /*
1455          * Preload this CPU with one extra vmap_area object. It is used
1456          * when fit type of free area is NE_FIT_TYPE. It guarantees that
1457          * a CPU that does an allocation is preloaded.
1458          *
1459          * We do it in non-atomic context, thus it allows us to use more
1460          * permissive allocation masks to be more stable under low memory
1461          * condition and high memory pressure.
1462          */
1463         if (!this_cpu_read(ne_fit_preload_node))
1464                 va = kmem_cache_alloc_node(vmap_area_cachep, gfp_mask, node);
1465
1466         spin_lock(lock);
1467
1468         if (va && __this_cpu_cmpxchg(ne_fit_preload_node, NULL, va))
1469                 kmem_cache_free(vmap_area_cachep, va);
1470 }
1471
1472 /*
1473  * Allocate a region of KVA of the specified size and alignment, within the
1474  * vstart and vend.
1475  */
1476 static struct vmap_area *alloc_vmap_area(unsigned long size,
1477                                 unsigned long align,
1478                                 unsigned long vstart, unsigned long vend,
1479                                 int node, gfp_t gfp_mask)
1480 {
1481         struct vmap_area *va;
1482         unsigned long addr;
1483         int purged = 0;
1484         int ret;
1485
1486         BUG_ON(!size);
1487         BUG_ON(offset_in_page(size));
1488         BUG_ON(!is_power_of_2(align));
1489
1490         if (unlikely(!vmap_initialized))
1491                 return ERR_PTR(-EBUSY);
1492
1493         might_sleep();
1494         gfp_mask = gfp_mask & GFP_RECLAIM_MASK;
1495
1496         va = kmem_cache_alloc_node(vmap_area_cachep, gfp_mask, node);
1497         if (unlikely(!va))
1498                 return ERR_PTR(-ENOMEM);
1499
1500         /*
1501          * Only scan the relevant parts containing pointers to other objects
1502          * to avoid false negatives.
1503          */
1504         kmemleak_scan_area(&va->rb_node, SIZE_MAX, gfp_mask);
1505
1506 retry:
1507         preload_this_cpu_lock(&free_vmap_area_lock, gfp_mask, node);
1508         addr = __alloc_vmap_area(size, align, vstart, vend);
1509         spin_unlock(&free_vmap_area_lock);
1510
1511         /*
1512          * If an allocation fails, the "vend" address is
1513          * returned. Therefore trigger the overflow path.
1514          */
1515         if (unlikely(addr == vend))
1516                 goto overflow;
1517
1518         va->va_start = addr;
1519         va->va_end = addr + size;
1520         va->vm = NULL;
1521
1522         spin_lock(&vmap_area_lock);
1523         insert_vmap_area(va, &vmap_area_root, &vmap_area_list);
1524         spin_unlock(&vmap_area_lock);
1525
1526         BUG_ON(!IS_ALIGNED(va->va_start, align));
1527         BUG_ON(va->va_start < vstart);
1528         BUG_ON(va->va_end > vend);
1529
1530         ret = kasan_populate_vmalloc(addr, size);
1531         if (ret) {
1532                 free_vmap_area(va);
1533                 return ERR_PTR(ret);
1534         }
1535
1536         return va;
1537
1538 overflow:
1539         if (!purged) {
1540                 purge_vmap_area_lazy();
1541                 purged = 1;
1542                 goto retry;
1543         }
1544
1545         if (gfpflags_allow_blocking(gfp_mask)) {
1546                 unsigned long freed = 0;
1547                 blocking_notifier_call_chain(&vmap_notify_list, 0, &freed);
1548                 if (freed > 0) {
1549                         purged = 0;
1550                         goto retry;
1551                 }
1552         }
1553
1554         if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit())
1555                 pr_warn("vmap allocation for size %lu failed: use vmalloc=<size> to increase size\n",
1556                         size);
1557
1558         kmem_cache_free(vmap_area_cachep, va);
1559         return ERR_PTR(-EBUSY);
1560 }
1561
1562 int register_vmap_purge_notifier(struct notifier_block *nb)
1563 {
1564         return blocking_notifier_chain_register(&vmap_notify_list, nb);
1565 }
1566 EXPORT_SYMBOL_GPL(register_vmap_purge_notifier);
1567
1568 int unregister_vmap_purge_notifier(struct notifier_block *nb)
1569 {
1570         return blocking_notifier_chain_unregister(&vmap_notify_list, nb);
1571 }
1572 EXPORT_SYMBOL_GPL(unregister_vmap_purge_notifier);
1573
1574 /*
1575  * lazy_max_pages is the maximum amount of virtual address space we gather up
1576  * before attempting to purge with a TLB flush.
1577  *
1578  * There is a tradeoff here: a larger number will cover more kernel page tables
1579  * and take slightly longer to purge, but it will linearly reduce the number of
1580  * global TLB flushes that must be performed. It would seem natural to scale
1581  * this number up linearly with the number of CPUs (because vmapping activity
1582  * could also scale linearly with the number of CPUs), however it is likely
1583  * that in practice, workloads might be constrained in other ways that mean
1584  * vmap activity will not scale linearly with CPUs. Also, I want to be
1585  * conservative and not introduce a big latency on huge systems, so go with
1586  * a less aggressive log scale. It will still be an improvement over the old
1587  * code, and it will be simple to change the scale factor if we find that it
1588  * becomes a problem on bigger systems.
1589  */
1590 static unsigned long lazy_max_pages(void)
1591 {
1592         unsigned int log;
1593
1594         log = fls(num_online_cpus());
1595
1596         return log * (32UL * 1024 * 1024 / PAGE_SIZE);
1597 }
1598
1599 static atomic_long_t vmap_lazy_nr = ATOMIC_LONG_INIT(0);
1600
1601 /*
1602  * Serialize vmap purging.  There is no actual critical section protected
1603  * by this look, but we want to avoid concurrent calls for performance
1604  * reasons and to make the pcpu_get_vm_areas more deterministic.
1605  */
1606 static DEFINE_MUTEX(vmap_purge_lock);
1607
1608 /* for per-CPU blocks */
1609 static void purge_fragmented_blocks_allcpus(void);
1610
1611 #ifdef CONFIG_X86_64
1612 /*
1613  * called before a call to iounmap() if the caller wants vm_area_struct's
1614  * immediately freed.
1615  */
1616 void set_iounmap_nonlazy(void)
1617 {
1618         atomic_long_set(&vmap_lazy_nr, lazy_max_pages()+1);
1619 }
1620 #endif /* CONFIG_X86_64 */
1621
1622 /*
1623  * Purges all lazily-freed vmap areas.
1624  */
1625 static bool __purge_vmap_area_lazy(unsigned long start, unsigned long end)
1626 {
1627         unsigned long resched_threshold;
1628         struct list_head local_pure_list;
1629         struct vmap_area *va, *n_va;
1630
1631         lockdep_assert_held(&vmap_purge_lock);
1632
1633         spin_lock(&purge_vmap_area_lock);
1634         purge_vmap_area_root = RB_ROOT;
1635         list_replace_init(&purge_vmap_area_list, &local_pure_list);
1636         spin_unlock(&purge_vmap_area_lock);
1637
1638         if (unlikely(list_empty(&local_pure_list)))
1639                 return false;
1640
1641         start = min(start,
1642                 list_first_entry(&local_pure_list,
1643                         struct vmap_area, list)->va_start);
1644
1645         end = max(end,
1646                 list_last_entry(&local_pure_list,
1647                         struct vmap_area, list)->va_end);
1648
1649         flush_tlb_kernel_range(start, end);
1650         resched_threshold = lazy_max_pages() << 1;
1651
1652         spin_lock(&free_vmap_area_lock);
1653         list_for_each_entry_safe(va, n_va, &local_pure_list, list) {
1654                 unsigned long nr = (va->va_end - va->va_start) >> PAGE_SHIFT;
1655                 unsigned long orig_start = va->va_start;
1656                 unsigned long orig_end = va->va_end;
1657
1658                 /*
1659                  * Finally insert or merge lazily-freed area. It is
1660                  * detached and there is no need to "unlink" it from
1661                  * anything.
1662                  */
1663                 va = merge_or_add_vmap_area_augment(va, &free_vmap_area_root,
1664                                 &free_vmap_area_list);
1665
1666                 if (!va)
1667                         continue;
1668
1669                 if (is_vmalloc_or_module_addr((void *)orig_start))
1670                         kasan_release_vmalloc(orig_start, orig_end,
1671                                               va->va_start, va->va_end);
1672
1673                 atomic_long_sub(nr, &vmap_lazy_nr);
1674
1675                 if (atomic_long_read(&vmap_lazy_nr) < resched_threshold)
1676                         cond_resched_lock(&free_vmap_area_lock);
1677         }
1678         spin_unlock(&free_vmap_area_lock);
1679         return true;
1680 }
1681
1682 /*
1683  * Kick off a purge of the outstanding lazy areas. Don't bother if somebody
1684  * is already purging.
1685  */
1686 static void try_purge_vmap_area_lazy(void)
1687 {
1688         if (mutex_trylock(&vmap_purge_lock)) {
1689                 __purge_vmap_area_lazy(ULONG_MAX, 0);
1690                 mutex_unlock(&vmap_purge_lock);
1691         }
1692 }
1693
1694 /*
1695  * Kick off a purge of the outstanding lazy areas.
1696  */
1697 static void purge_vmap_area_lazy(void)
1698 {
1699         mutex_lock(&vmap_purge_lock);
1700         purge_fragmented_blocks_allcpus();
1701         __purge_vmap_area_lazy(ULONG_MAX, 0);
1702         mutex_unlock(&vmap_purge_lock);
1703 }
1704
1705 /*
1706  * Free a vmap area, caller ensuring that the area has been unmapped
1707  * and flush_cache_vunmap had been called for the correct range
1708  * previously.
1709  */
1710 static void free_vmap_area_noflush(struct vmap_area *va)
1711 {
1712         unsigned long nr_lazy;
1713
1714         spin_lock(&vmap_area_lock);
1715         unlink_va(va, &vmap_area_root);
1716         spin_unlock(&vmap_area_lock);
1717
1718         nr_lazy = atomic_long_add_return((va->va_end - va->va_start) >>
1719                                 PAGE_SHIFT, &vmap_lazy_nr);
1720
1721         /*
1722          * Merge or place it to the purge tree/list.
1723          */
1724         spin_lock(&purge_vmap_area_lock);
1725         merge_or_add_vmap_area(va,
1726                 &purge_vmap_area_root, &purge_vmap_area_list);
1727         spin_unlock(&purge_vmap_area_lock);
1728
1729         /* After this point, we may free va at any time */
1730         if (unlikely(nr_lazy > lazy_max_pages()))
1731                 try_purge_vmap_area_lazy();
1732 }
1733
1734 /*
1735  * Free and unmap a vmap area
1736  */
1737 static void free_unmap_vmap_area(struct vmap_area *va)
1738 {
1739         flush_cache_vunmap(va->va_start, va->va_end);
1740         vunmap_range_noflush(va->va_start, va->va_end);
1741         if (debug_pagealloc_enabled_static())
1742                 flush_tlb_kernel_range(va->va_start, va->va_end);
1743
1744         free_vmap_area_noflush(va);
1745 }
1746
1747 static struct vmap_area *find_vmap_area(unsigned long addr)
1748 {
1749         struct vmap_area *va;
1750
1751         spin_lock(&vmap_area_lock);
1752         va = __find_vmap_area(addr);
1753         spin_unlock(&vmap_area_lock);
1754
1755         return va;
1756 }
1757
1758 /*** Per cpu kva allocator ***/
1759
1760 /*
1761  * vmap space is limited especially on 32 bit architectures. Ensure there is
1762  * room for at least 16 percpu vmap blocks per CPU.
1763  */
1764 /*
1765  * If we had a constant VMALLOC_START and VMALLOC_END, we'd like to be able
1766  * to #define VMALLOC_SPACE             (VMALLOC_END-VMALLOC_START). Guess
1767  * instead (we just need a rough idea)
1768  */
1769 #if BITS_PER_LONG == 32
1770 #define VMALLOC_SPACE           (128UL*1024*1024)
1771 #else
1772 #define VMALLOC_SPACE           (128UL*1024*1024*1024)
1773 #endif
1774
1775 #define VMALLOC_PAGES           (VMALLOC_SPACE / PAGE_SIZE)
1776 #define VMAP_MAX_ALLOC          BITS_PER_LONG   /* 256K with 4K pages */
1777 #define VMAP_BBMAP_BITS_MAX     1024    /* 4MB with 4K pages */
1778 #define VMAP_BBMAP_BITS_MIN     (VMAP_MAX_ALLOC*2)
1779 #define VMAP_MIN(x, y)          ((x) < (y) ? (x) : (y)) /* can't use min() */
1780 #define VMAP_MAX(x, y)          ((x) > (y) ? (x) : (y)) /* can't use max() */
1781 #define VMAP_BBMAP_BITS         \
1782                 VMAP_MIN(VMAP_BBMAP_BITS_MAX,   \
1783                 VMAP_MAX(VMAP_BBMAP_BITS_MIN,   \
1784                         VMALLOC_PAGES / roundup_pow_of_two(NR_CPUS) / 16))
1785
1786 #define VMAP_BLOCK_SIZE         (VMAP_BBMAP_BITS * PAGE_SIZE)
1787
1788 struct vmap_block_queue {
1789         spinlock_t lock;
1790         struct list_head free;
1791 };
1792
1793 struct vmap_block {
1794         spinlock_t lock;
1795         struct vmap_area *va;
1796         unsigned long free, dirty;
1797         unsigned long dirty_min, dirty_max; /*< dirty range */
1798         struct list_head free_list;
1799         struct rcu_head rcu_head;
1800         struct list_head purge;
1801 };
1802
1803 /* Queue of free and dirty vmap blocks, for allocation and flushing purposes */
1804 static DEFINE_PER_CPU(struct vmap_block_queue, vmap_block_queue);
1805
1806 /*
1807  * XArray of vmap blocks, indexed by address, to quickly find a vmap block
1808  * in the free path. Could get rid of this if we change the API to return a
1809  * "cookie" from alloc, to be passed to free. But no big deal yet.
1810  */
1811 static DEFINE_XARRAY(vmap_blocks);
1812
1813 /*
1814  * We should probably have a fallback mechanism to allocate virtual memory
1815  * out of partially filled vmap blocks. However vmap block sizing should be
1816  * fairly reasonable according to the vmalloc size, so it shouldn't be a
1817  * big problem.
1818  */
1819
1820 static unsigned long addr_to_vb_idx(unsigned long addr)
1821 {
1822         addr -= VMALLOC_START & ~(VMAP_BLOCK_SIZE-1);
1823         addr /= VMAP_BLOCK_SIZE;
1824         return addr;
1825 }
1826
1827 static void *vmap_block_vaddr(unsigned long va_start, unsigned long pages_off)
1828 {
1829         unsigned long addr;
1830
1831         addr = va_start + (pages_off << PAGE_SHIFT);
1832         BUG_ON(addr_to_vb_idx(addr) != addr_to_vb_idx(va_start));
1833         return (void *)addr;
1834 }
1835
1836 /**
1837  * new_vmap_block - allocates new vmap_block and occupies 2^order pages in this
1838  *                  block. Of course pages number can't exceed VMAP_BBMAP_BITS
1839  * @order:    how many 2^order pages should be occupied in newly allocated block
1840  * @gfp_mask: flags for the page level allocator
1841  *
1842  * Return: virtual address in a newly allocated block or ERR_PTR(-errno)
1843  */
1844 static void *new_vmap_block(unsigned int order, gfp_t gfp_mask)
1845 {
1846         struct vmap_block_queue *vbq;
1847         struct vmap_block *vb;
1848         struct vmap_area *va;
1849         unsigned long vb_idx;
1850         int node, err;
1851         void *vaddr;
1852
1853         node = numa_node_id();
1854
1855         vb = kmalloc_node(sizeof(struct vmap_block),
1856                         gfp_mask & GFP_RECLAIM_MASK, node);
1857         if (unlikely(!vb))
1858                 return ERR_PTR(-ENOMEM);
1859
1860         va = alloc_vmap_area(VMAP_BLOCK_SIZE, VMAP_BLOCK_SIZE,
1861                                         VMALLOC_START, VMALLOC_END,
1862                                         node, gfp_mask);
1863         if (IS_ERR(va)) {
1864                 kfree(vb);
1865                 return ERR_CAST(va);
1866         }
1867
1868         vaddr = vmap_block_vaddr(va->va_start, 0);
1869         spin_lock_init(&vb->lock);
1870         vb->va = va;
1871         /* At least something should be left free */
1872         BUG_ON(VMAP_BBMAP_BITS <= (1UL << order));
1873         vb->free = VMAP_BBMAP_BITS - (1UL << order);
1874         vb->dirty = 0;
1875         vb->dirty_min = VMAP_BBMAP_BITS;
1876         vb->dirty_max = 0;
1877         INIT_LIST_HEAD(&vb->free_list);
1878
1879         vb_idx = addr_to_vb_idx(va->va_start);
1880         err = xa_insert(&vmap_blocks, vb_idx, vb, gfp_mask);
1881         if (err) {
1882                 kfree(vb);
1883                 free_vmap_area(va);
1884                 return ERR_PTR(err);
1885         }
1886
1887         vbq = &get_cpu_var(vmap_block_queue);
1888         spin_lock(&vbq->lock);
1889         list_add_tail_rcu(&vb->free_list, &vbq->free);
1890         spin_unlock(&vbq->lock);
1891         put_cpu_var(vmap_block_queue);
1892
1893         return vaddr;
1894 }
1895
1896 static void free_vmap_block(struct vmap_block *vb)
1897 {
1898         struct vmap_block *tmp;
1899
1900         tmp = xa_erase(&vmap_blocks, addr_to_vb_idx(vb->va->va_start));
1901         BUG_ON(tmp != vb);
1902
1903         free_vmap_area_noflush(vb->va);
1904         kfree_rcu(vb, rcu_head);
1905 }
1906
1907 static void purge_fragmented_blocks(int cpu)
1908 {
1909         LIST_HEAD(purge);
1910         struct vmap_block *vb;
1911         struct vmap_block *n_vb;
1912         struct vmap_block_queue *vbq = &per_cpu(vmap_block_queue, cpu);
1913
1914         rcu_read_lock();
1915         list_for_each_entry_rcu(vb, &vbq->free, free_list) {
1916
1917                 if (!(vb->free + vb->dirty == VMAP_BBMAP_BITS && vb->dirty != VMAP_BBMAP_BITS))
1918                         continue;
1919
1920                 spin_lock(&vb->lock);
1921                 if (vb->free + vb->dirty == VMAP_BBMAP_BITS && vb->dirty != VMAP_BBMAP_BITS) {
1922                         vb->free = 0; /* prevent further allocs after releasing lock */
1923                         vb->dirty = VMAP_BBMAP_BITS; /* prevent purging it again */
1924                         vb->dirty_min = 0;
1925                         vb->dirty_max = VMAP_BBMAP_BITS;
1926                         spin_lock(&vbq->lock);
1927                         list_del_rcu(&vb->free_list);
1928                         spin_unlock(&vbq->lock);
1929                         spin_unlock(&vb->lock);
1930                         list_add_tail(&vb->purge, &purge);
1931                 } else
1932                         spin_unlock(&vb->lock);
1933         }
1934         rcu_read_unlock();
1935
1936         list_for_each_entry_safe(vb, n_vb, &purge, purge) {
1937                 list_del(&vb->purge);
1938                 free_vmap_block(vb);
1939         }
1940 }
1941
1942 static void purge_fragmented_blocks_allcpus(void)
1943 {
1944         int cpu;
1945
1946         for_each_possible_cpu(cpu)
1947                 purge_fragmented_blocks(cpu);
1948 }
1949
1950 static void *vb_alloc(unsigned long size, gfp_t gfp_mask)
1951 {
1952         struct vmap_block_queue *vbq;
1953         struct vmap_block *vb;
1954         void *vaddr = NULL;
1955         unsigned int order;
1956
1957         BUG_ON(offset_in_page(size));
1958         BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC);
1959         if (WARN_ON(size == 0)) {
1960                 /*
1961                  * Allocating 0 bytes isn't what caller wants since
1962                  * get_order(0) returns funny result. Just warn and terminate
1963                  * early.
1964                  */
1965                 return NULL;
1966         }
1967         order = get_order(size);
1968
1969         rcu_read_lock();
1970         vbq = &get_cpu_var(vmap_block_queue);
1971         list_for_each_entry_rcu(vb, &vbq->free, free_list) {
1972                 unsigned long pages_off;
1973
1974                 spin_lock(&vb->lock);
1975                 if (vb->free < (1UL << order)) {
1976                         spin_unlock(&vb->lock);
1977                         continue;
1978                 }
1979
1980                 pages_off = VMAP_BBMAP_BITS - vb->free;
1981                 vaddr = vmap_block_vaddr(vb->va->va_start, pages_off);
1982                 vb->free -= 1UL << order;
1983                 if (vb->free == 0) {
1984                         spin_lock(&vbq->lock);
1985                         list_del_rcu(&vb->free_list);
1986                         spin_unlock(&vbq->lock);
1987                 }
1988
1989                 spin_unlock(&vb->lock);
1990                 break;
1991         }
1992
1993         put_cpu_var(vmap_block_queue);
1994         rcu_read_unlock();
1995
1996         /* Allocate new block if nothing was found */
1997         if (!vaddr)
1998                 vaddr = new_vmap_block(order, gfp_mask);
1999
2000         return vaddr;
2001 }
2002
2003 static void vb_free(unsigned long addr, unsigned long size)
2004 {
2005         unsigned long offset;
2006         unsigned int order;
2007         struct vmap_block *vb;
2008
2009         BUG_ON(offset_in_page(size));
2010         BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC);
2011
2012         flush_cache_vunmap(addr, addr + size);
2013
2014         order = get_order(size);
2015         offset = (addr & (VMAP_BLOCK_SIZE - 1)) >> PAGE_SHIFT;
2016         vb = xa_load(&vmap_blocks, addr_to_vb_idx(addr));
2017
2018         vunmap_range_noflush(addr, addr + size);
2019
2020         if (debug_pagealloc_enabled_static())
2021                 flush_tlb_kernel_range(addr, addr + size);
2022
2023         spin_lock(&vb->lock);
2024
2025         /* Expand dirty range */
2026         vb->dirty_min = min(vb->dirty_min, offset);
2027         vb->dirty_max = max(vb->dirty_max, offset + (1UL << order));
2028
2029         vb->dirty += 1UL << order;
2030         if (vb->dirty == VMAP_BBMAP_BITS) {
2031                 BUG_ON(vb->free);
2032                 spin_unlock(&vb->lock);
2033                 free_vmap_block(vb);
2034         } else
2035                 spin_unlock(&vb->lock);
2036 }
2037
2038 static void _vm_unmap_aliases(unsigned long start, unsigned long end, int flush)
2039 {
2040         int cpu;
2041
2042         if (unlikely(!vmap_initialized))
2043                 return;
2044
2045         might_sleep();
2046
2047         for_each_possible_cpu(cpu) {
2048                 struct vmap_block_queue *vbq = &per_cpu(vmap_block_queue, cpu);
2049                 struct vmap_block *vb;
2050
2051                 rcu_read_lock();
2052                 list_for_each_entry_rcu(vb, &vbq->free, free_list) {
2053                         spin_lock(&vb->lock);
2054                         if (vb->dirty && vb->dirty != VMAP_BBMAP_BITS) {
2055                                 unsigned long va_start = vb->va->va_start;
2056                                 unsigned long s, e;
2057
2058                                 s = va_start + (vb->dirty_min << PAGE_SHIFT);
2059                                 e = va_start + (vb->dirty_max << PAGE_SHIFT);
2060
2061                                 start = min(s, start);
2062                                 end   = max(e, end);
2063
2064                                 flush = 1;
2065                         }
2066                         spin_unlock(&vb->lock);
2067                 }
2068                 rcu_read_unlock();
2069         }
2070
2071         mutex_lock(&vmap_purge_lock);
2072         purge_fragmented_blocks_allcpus();
2073         if (!__purge_vmap_area_lazy(start, end) && flush)
2074                 flush_tlb_kernel_range(start, end);
2075         mutex_unlock(&vmap_purge_lock);
2076 }
2077
2078 /**
2079  * vm_unmap_aliases - unmap outstanding lazy aliases in the vmap layer
2080  *
2081  * The vmap/vmalloc layer lazily flushes kernel virtual mappings primarily
2082  * to amortize TLB flushing overheads. What this means is that any page you
2083  * have now, may, in a former life, have been mapped into kernel virtual
2084  * address by the vmap layer and so there might be some CPUs with TLB entries
2085  * still referencing that page (additional to the regular 1:1 kernel mapping).
2086  *
2087  * vm_unmap_aliases flushes all such lazy mappings. After it returns, we can
2088  * be sure that none of the pages we have control over will have any aliases
2089  * from the vmap layer.
2090  */
2091 void vm_unmap_aliases(void)
2092 {
2093         unsigned long start = ULONG_MAX, end = 0;
2094         int flush = 0;
2095
2096         _vm_unmap_aliases(start, end, flush);
2097 }
2098 EXPORT_SYMBOL_GPL(vm_unmap_aliases);
2099
2100 /**
2101  * vm_unmap_ram - unmap linear kernel address space set up by vm_map_ram
2102  * @mem: the pointer returned by vm_map_ram
2103  * @count: the count passed to that vm_map_ram call (cannot unmap partial)
2104  */
2105 void vm_unmap_ram(const void *mem, unsigned int count)
2106 {
2107         unsigned long size = (unsigned long)count << PAGE_SHIFT;
2108         unsigned long addr = (unsigned long)mem;
2109         struct vmap_area *va;
2110
2111         might_sleep();
2112         BUG_ON(!addr);
2113         BUG_ON(addr < VMALLOC_START);
2114         BUG_ON(addr > VMALLOC_END);
2115         BUG_ON(!PAGE_ALIGNED(addr));
2116
2117         kasan_poison_vmalloc(mem, size);
2118
2119         if (likely(count <= VMAP_MAX_ALLOC)) {
2120                 debug_check_no_locks_freed(mem, size);
2121                 vb_free(addr, size);
2122                 return;
2123         }
2124
2125         va = find_vmap_area(addr);
2126         BUG_ON(!va);
2127         debug_check_no_locks_freed((void *)va->va_start,
2128                                     (va->va_end - va->va_start));
2129         free_unmap_vmap_area(va);
2130 }
2131 EXPORT_SYMBOL(vm_unmap_ram);
2132
2133 /**
2134  * vm_map_ram - map pages linearly into kernel virtual address (vmalloc space)
2135  * @pages: an array of pointers to the pages to be mapped
2136  * @count: number of pages
2137  * @node: prefer to allocate data structures on this node
2138  *
2139  * If you use this function for less than VMAP_MAX_ALLOC pages, it could be
2140  * faster than vmap so it's good.  But if you mix long-life and short-life
2141  * objects with vm_map_ram(), it could consume lots of address space through
2142  * fragmentation (especially on a 32bit machine).  You could see failures in
2143  * the end.  Please use this function for short-lived objects.
2144  *
2145  * Returns: a pointer to the address that has been mapped, or %NULL on failure
2146  */
2147 void *vm_map_ram(struct page **pages, unsigned int count, int node)
2148 {
2149         unsigned long size = (unsigned long)count << PAGE_SHIFT;
2150         unsigned long addr;
2151         void *mem;
2152
2153         if (likely(count <= VMAP_MAX_ALLOC)) {
2154                 mem = vb_alloc(size, GFP_KERNEL);
2155                 if (IS_ERR(mem))
2156                         return NULL;
2157                 addr = (unsigned long)mem;
2158         } else {
2159                 struct vmap_area *va;
2160                 va = alloc_vmap_area(size, PAGE_SIZE,
2161                                 VMALLOC_START, VMALLOC_END, node, GFP_KERNEL);
2162                 if (IS_ERR(va))
2163                         return NULL;
2164
2165                 addr = va->va_start;
2166                 mem = (void *)addr;
2167         }
2168
2169         kasan_unpoison_vmalloc(mem, size);
2170
2171         if (vmap_pages_range(addr, addr + size, PAGE_KERNEL,
2172                                 pages, PAGE_SHIFT) < 0) {
2173                 vm_unmap_ram(mem, count);
2174                 return NULL;
2175         }
2176
2177         return mem;
2178 }
2179 EXPORT_SYMBOL(vm_map_ram);
2180
2181 static struct vm_struct *vmlist __initdata;
2182
2183 static inline unsigned int vm_area_page_order(struct vm_struct *vm)
2184 {
2185 #ifdef CONFIG_HAVE_ARCH_HUGE_VMALLOC
2186         return vm->page_order;
2187 #else
2188         return 0;
2189 #endif
2190 }
2191
2192 static inline void set_vm_area_page_order(struct vm_struct *vm, unsigned int order)
2193 {
2194 #ifdef CONFIG_HAVE_ARCH_HUGE_VMALLOC
2195         vm->page_order = order;
2196 #else
2197         BUG_ON(order != 0);
2198 #endif
2199 }
2200
2201 /**
2202  * vm_area_add_early - add vmap area early during boot
2203  * @vm: vm_struct to add
2204  *
2205  * This function is used to add fixed kernel vm area to vmlist before
2206  * vmalloc_init() is called.  @vm->addr, @vm->size, and @vm->flags
2207  * should contain proper values and the other fields should be zero.
2208  *
2209  * DO NOT USE THIS FUNCTION UNLESS YOU KNOW WHAT YOU'RE DOING.
2210  */
2211 void __init vm_area_add_early(struct vm_struct *vm)
2212 {
2213         struct vm_struct *tmp, **p;
2214
2215         BUG_ON(vmap_initialized);
2216         for (p = &vmlist; (tmp = *p) != NULL; p = &tmp->next) {
2217                 if (tmp->addr >= vm->addr) {
2218                         BUG_ON(tmp->addr < vm->addr + vm->size);
2219                         break;
2220                 } else
2221                         BUG_ON(tmp->addr + tmp->size > vm->addr);
2222         }
2223         vm->next = *p;
2224         *p = vm;
2225 }
2226
2227 /**
2228  * vm_area_register_early - register vmap area early during boot
2229  * @vm: vm_struct to register
2230  * @align: requested alignment
2231  *
2232  * This function is used to register kernel vm area before
2233  * vmalloc_init() is called.  @vm->size and @vm->flags should contain
2234  * proper values on entry and other fields should be zero.  On return,
2235  * vm->addr contains the allocated address.
2236  *
2237  * DO NOT USE THIS FUNCTION UNLESS YOU KNOW WHAT YOU'RE DOING.
2238  */
2239 void __init vm_area_register_early(struct vm_struct *vm, size_t align)
2240 {
2241         static size_t vm_init_off __initdata;
2242         unsigned long addr;
2243
2244         addr = ALIGN(VMALLOC_START + vm_init_off, align);
2245         vm_init_off = PFN_ALIGN(addr + vm->size) - VMALLOC_START;
2246
2247         vm->addr = (void *)addr;
2248
2249         vm_area_add_early(vm);
2250 }
2251
2252 static void vmap_init_free_space(void)
2253 {
2254         unsigned long vmap_start = 1;
2255         const unsigned long vmap_end = ULONG_MAX;
2256         struct vmap_area *busy, *free;
2257
2258         /*
2259          *     B     F     B     B     B     F
2260          * -|-----|.....|-----|-----|-----|.....|-
2261          *  |           The KVA space           |
2262          *  |<--------------------------------->|
2263          */
2264         list_for_each_entry(busy, &vmap_area_list, list) {
2265                 if (busy->va_start - vmap_start > 0) {
2266                         free = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT);
2267                         if (!WARN_ON_ONCE(!free)) {
2268                                 free->va_start = vmap_start;
2269                                 free->va_end = busy->va_start;
2270
2271                                 insert_vmap_area_augment(free, NULL,
2272                                         &free_vmap_area_root,
2273                                                 &free_vmap_area_list);
2274                         }
2275                 }
2276
2277                 vmap_start = busy->va_end;
2278         }
2279
2280         if (vmap_end - vmap_start > 0) {
2281                 free = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT);
2282                 if (!WARN_ON_ONCE(!free)) {
2283                         free->va_start = vmap_start;
2284                         free->va_end = vmap_end;
2285
2286                         insert_vmap_area_augment(free, NULL,
2287                                 &free_vmap_area_root,
2288                                         &free_vmap_area_list);
2289                 }
2290         }
2291 }
2292
2293 void __init vmalloc_init(void)
2294 {
2295         struct vmap_area *va;
2296         struct vm_struct *tmp;
2297         int i;
2298
2299         /*
2300          * Create the cache for vmap_area objects.
2301          */
2302         vmap_area_cachep = KMEM_CACHE(vmap_area, SLAB_PANIC);
2303
2304         for_each_possible_cpu(i) {
2305                 struct vmap_block_queue *vbq;
2306                 struct vfree_deferred *p;
2307
2308                 vbq = &per_cpu(vmap_block_queue, i);
2309                 spin_lock_init(&vbq->lock);
2310                 INIT_LIST_HEAD(&vbq->free);
2311                 p = &per_cpu(vfree_deferred, i);
2312                 init_llist_head(&p->list);
2313                 INIT_WORK(&p->wq, free_work);
2314         }
2315
2316         /* Import existing vmlist entries. */
2317         for (tmp = vmlist; tmp; tmp = tmp->next) {
2318                 va = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT);
2319                 if (WARN_ON_ONCE(!va))
2320                         continue;
2321
2322                 va->va_start = (unsigned long)tmp->addr;
2323                 va->va_end = va->va_start + tmp->size;
2324                 va->vm = tmp;
2325                 insert_vmap_area(va, &vmap_area_root, &vmap_area_list);
2326         }
2327
2328         /*
2329          * Now we can initialize a free vmap space.
2330          */
2331         vmap_init_free_space();
2332         vmap_initialized = true;
2333 }
2334
2335 static inline void setup_vmalloc_vm_locked(struct vm_struct *vm,
2336         struct vmap_area *va, unsigned long flags, const void *caller)
2337 {
2338         vm->flags = flags;
2339         vm->addr = (void *)va->va_start;
2340         vm->size = va->va_end - va->va_start;
2341         vm->caller = caller;
2342         va->vm = vm;
2343 }
2344
2345 static void setup_vmalloc_vm(struct vm_struct *vm, struct vmap_area *va,
2346                               unsigned long flags, const void *caller)
2347 {
2348         spin_lock(&vmap_area_lock);
2349         setup_vmalloc_vm_locked(vm, va, flags, caller);
2350         spin_unlock(&vmap_area_lock);
2351 }
2352
2353 static void clear_vm_uninitialized_flag(struct vm_struct *vm)
2354 {
2355         /*
2356          * Before removing VM_UNINITIALIZED,
2357          * we should make sure that vm has proper values.
2358          * Pair with smp_rmb() in show_numa_info().
2359          */
2360         smp_wmb();
2361         vm->flags &= ~VM_UNINITIALIZED;
2362 }
2363
2364 static struct vm_struct *__get_vm_area_node(unsigned long size,
2365                 unsigned long align, unsigned long shift, unsigned long flags,
2366                 unsigned long start, unsigned long end, int node,
2367                 gfp_t gfp_mask, const void *caller)
2368 {
2369         struct vmap_area *va;
2370         struct vm_struct *area;
2371         unsigned long requested_size = size;
2372
2373         BUG_ON(in_interrupt());
2374         size = ALIGN(size, 1ul << shift);
2375         if (unlikely(!size))
2376                 return NULL;
2377
2378         if (flags & VM_IOREMAP)
2379                 align = 1ul << clamp_t(int, get_count_order_long(size),
2380                                        PAGE_SHIFT, IOREMAP_MAX_ORDER);
2381
2382         area = kzalloc_node(sizeof(*area), gfp_mask & GFP_RECLAIM_MASK, node);
2383         if (unlikely(!area))
2384                 return NULL;
2385
2386         if (!(flags & VM_NO_GUARD))
2387                 size += PAGE_SIZE;
2388
2389         va = alloc_vmap_area(size, align, start, end, node, gfp_mask);
2390         if (IS_ERR(va)) {
2391                 kfree(area);
2392                 return NULL;
2393         }
2394
2395         kasan_unpoison_vmalloc((void *)va->va_start, requested_size);
2396
2397         setup_vmalloc_vm(area, va, flags, caller);
2398
2399         return area;
2400 }
2401
2402 struct vm_struct *__get_vm_area_caller(unsigned long size, unsigned long flags,
2403                                        unsigned long start, unsigned long end,
2404                                        const void *caller)
2405 {
2406         return __get_vm_area_node(size, 1, PAGE_SHIFT, flags, start, end,
2407                                   NUMA_NO_NODE, GFP_KERNEL, caller);
2408 }
2409
2410 /**
2411  * get_vm_area - reserve a contiguous kernel virtual area
2412  * @size:        size of the area
2413  * @flags:       %VM_IOREMAP for I/O mappings or VM_ALLOC
2414  *
2415  * Search an area of @size in the kernel virtual mapping area,
2416  * and reserved it for out purposes.  Returns the area descriptor
2417  * on success or %NULL on failure.
2418  *
2419  * Return: the area descriptor on success or %NULL on failure.
2420  */
2421 struct vm_struct *get_vm_area(unsigned long size, unsigned long flags)
2422 {
2423         return __get_vm_area_node(size, 1, PAGE_SHIFT, flags,
2424                                   VMALLOC_START, VMALLOC_END,
2425                                   NUMA_NO_NODE, GFP_KERNEL,
2426                                   __builtin_return_address(0));
2427 }
2428
2429 struct vm_struct *get_vm_area_caller(unsigned long size, unsigned long flags,
2430                                 const void *caller)
2431 {
2432         return __get_vm_area_node(size, 1, PAGE_SHIFT, flags,
2433                                   VMALLOC_START, VMALLOC_END,
2434                                   NUMA_NO_NODE, GFP_KERNEL, caller);
2435 }
2436
2437 /**
2438  * find_vm_area - find a continuous kernel virtual area
2439  * @addr:         base address
2440  *
2441  * Search for the kernel VM area starting at @addr, and return it.
2442  * It is up to the caller to do all required locking to keep the returned
2443  * pointer valid.
2444  *
2445  * Return: the area descriptor on success or %NULL on failure.
2446  */
2447 struct vm_struct *find_vm_area(const void *addr)
2448 {
2449         struct vmap_area *va;
2450
2451         va = find_vmap_area((unsigned long)addr);
2452         if (!va)
2453                 return NULL;
2454
2455         return va->vm;
2456 }
2457
2458 /**
2459  * remove_vm_area - find and remove a continuous kernel virtual area
2460  * @addr:           base address
2461  *
2462  * Search for the kernel VM area starting at @addr, and remove it.
2463  * This function returns the found VM area, but using it is NOT safe
2464  * on SMP machines, except for its size or flags.
2465  *
2466  * Return: the area descriptor on success or %NULL on failure.
2467  */
2468 struct vm_struct *remove_vm_area(const void *addr)
2469 {
2470         struct vmap_area *va;
2471
2472         might_sleep();
2473
2474         spin_lock(&vmap_area_lock);
2475         va = __find_vmap_area((unsigned long)addr);
2476         if (va && va->vm) {
2477                 struct vm_struct *vm = va->vm;
2478
2479                 va->vm = NULL;
2480                 spin_unlock(&vmap_area_lock);
2481
2482                 kasan_free_shadow(vm);
2483                 free_unmap_vmap_area(va);
2484
2485                 return vm;
2486         }
2487
2488         spin_unlock(&vmap_area_lock);
2489         return NULL;
2490 }
2491
2492 static inline void set_area_direct_map(const struct vm_struct *area,
2493                                        int (*set_direct_map)(struct page *page))
2494 {
2495         int i;
2496
2497         /* HUGE_VMALLOC passes small pages to set_direct_map */
2498         for (i = 0; i < area->nr_pages; i++)
2499                 if (page_address(area->pages[i]))
2500                         set_direct_map(area->pages[i]);
2501 }
2502
2503 /* Handle removing and resetting vm mappings related to the vm_struct. */
2504 static void vm_remove_mappings(struct vm_struct *area, int deallocate_pages)
2505 {
2506         unsigned long start = ULONG_MAX, end = 0;
2507         unsigned int page_order = vm_area_page_order(area);
2508         int flush_reset = area->flags & VM_FLUSH_RESET_PERMS;
2509         int flush_dmap = 0;
2510         int i;
2511
2512         remove_vm_area(area->addr);
2513
2514         /* If this is not VM_FLUSH_RESET_PERMS memory, no need for the below. */
2515         if (!flush_reset)
2516                 return;
2517
2518         /*
2519          * If not deallocating pages, just do the flush of the VM area and
2520          * return.
2521          */
2522         if (!deallocate_pages) {
2523                 vm_unmap_aliases();
2524                 return;
2525         }
2526
2527         /*
2528          * If execution gets here, flush the vm mapping and reset the direct
2529          * map. Find the start and end range of the direct mappings to make sure
2530          * the vm_unmap_aliases() flush includes the direct map.
2531          */
2532         for (i = 0; i < area->nr_pages; i += 1U << page_order) {
2533                 unsigned long addr = (unsigned long)page_address(area->pages[i]);
2534                 if (addr) {
2535                         unsigned long page_size;
2536
2537                         page_size = PAGE_SIZE << page_order;
2538                         start = min(addr, start);
2539                         end = max(addr + page_size, end);
2540                         flush_dmap = 1;
2541                 }
2542         }
2543
2544         /*
2545          * Set direct map to something invalid so that it won't be cached if
2546          * there are any accesses after the TLB flush, then flush the TLB and
2547          * reset the direct map permissions to the default.
2548          */
2549         set_area_direct_map(area, set_direct_map_invalid_noflush);
2550         _vm_unmap_aliases(start, end, flush_dmap);
2551         set_area_direct_map(area, set_direct_map_default_noflush);
2552 }
2553
2554 static void __vunmap(const void *addr, int deallocate_pages)
2555 {
2556         struct vm_struct *area;
2557
2558         if (!addr)
2559                 return;
2560
2561         if (WARN(!PAGE_ALIGNED(addr), "Trying to vfree() bad address (%p)\n",
2562                         addr))
2563                 return;
2564
2565         area = find_vm_area(addr);
2566         if (unlikely(!area)) {
2567                 WARN(1, KERN_ERR "Trying to vfree() nonexistent vm area (%p)\n",
2568                                 addr);
2569                 return;
2570         }
2571
2572         debug_check_no_locks_freed(area->addr, get_vm_area_size(area));
2573         debug_check_no_obj_freed(area->addr, get_vm_area_size(area));
2574
2575         kasan_poison_vmalloc(area->addr, get_vm_area_size(area));
2576
2577         vm_remove_mappings(area, deallocate_pages);
2578
2579         if (deallocate_pages) {
2580                 unsigned int page_order = vm_area_page_order(area);
2581                 int i;
2582
2583                 for (i = 0; i < area->nr_pages; i += 1U << page_order) {
2584                         struct page *page = area->pages[i];
2585
2586                         BUG_ON(!page);
2587                         __free_pages(page, page_order);
2588                         cond_resched();
2589                 }
2590                 atomic_long_sub(area->nr_pages, &nr_vmalloc_pages);
2591
2592                 kvfree(area->pages);
2593         }
2594
2595         kfree(area);
2596 }
2597
2598 static inline void __vfree_deferred(const void *addr)
2599 {
2600         /*
2601          * Use raw_cpu_ptr() because this can be called from preemptible
2602          * context. Preemption is absolutely fine here, because the llist_add()
2603          * implementation is lockless, so it works even if we are adding to
2604          * another cpu's list. schedule_work() should be fine with this too.
2605          */
2606         struct vfree_deferred *p = raw_cpu_ptr(&vfree_deferred);
2607
2608         if (llist_add((struct llist_node *)addr, &p->list))
2609                 schedule_work(&p->wq);
2610 }
2611
2612 /**
2613  * vfree_atomic - release memory allocated by vmalloc()
2614  * @addr:         memory base address
2615  *
2616  * This one is just like vfree() but can be called in any atomic context
2617  * except NMIs.
2618  */
2619 void vfree_atomic(const void *addr)
2620 {
2621         BUG_ON(in_nmi());
2622
2623         kmemleak_free(addr);
2624
2625         if (!addr)
2626                 return;
2627         __vfree_deferred(addr);
2628 }
2629
2630 static void __vfree(const void *addr)
2631 {
2632         if (unlikely(in_interrupt()))
2633                 __vfree_deferred(addr);
2634         else
2635                 __vunmap(addr, 1);
2636 }
2637
2638 /**
2639  * vfree - Release memory allocated by vmalloc()
2640  * @addr:  Memory base address
2641  *
2642  * Free the virtually continuous memory area starting at @addr, as obtained
2643  * from one of the vmalloc() family of APIs.  This will usually also free the
2644  * physical memory underlying the virtual allocation, but that memory is
2645  * reference counted, so it will not be freed until the last user goes away.
2646  *
2647  * If @addr is NULL, no operation is performed.
2648  *
2649  * Context:
2650  * May sleep if called *not* from interrupt context.
2651  * Must not be called in NMI context (strictly speaking, it could be
2652  * if we have CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG, but making the calling
2653  * conventions for vfree() arch-dependent would be a really bad idea).
2654  */
2655 void vfree(const void *addr)
2656 {
2657         BUG_ON(in_nmi());
2658
2659         kmemleak_free(addr);
2660
2661         might_sleep_if(!in_interrupt());
2662
2663         if (!addr)
2664                 return;
2665
2666         __vfree(addr);
2667 }
2668 EXPORT_SYMBOL(vfree);
2669
2670 /**
2671  * vunmap - release virtual mapping obtained by vmap()
2672  * @addr:   memory base address
2673  *
2674  * Free the virtually contiguous memory area starting at @addr,
2675  * which was created from the page array passed to vmap().
2676  *
2677  * Must not be called in interrupt context.
2678  */
2679 void vunmap(const void *addr)
2680 {
2681         BUG_ON(in_interrupt());
2682         might_sleep();
2683         if (addr)
2684                 __vunmap(addr, 0);
2685 }
2686 EXPORT_SYMBOL(vunmap);
2687
2688 /**
2689  * vmap - map an array of pages into virtually contiguous space
2690  * @pages: array of page pointers
2691  * @count: number of pages to map
2692  * @flags: vm_area->flags
2693  * @prot: page protection for the mapping
2694  *
2695  * Maps @count pages from @pages into contiguous kernel virtual space.
2696  * If @flags contains %VM_MAP_PUT_PAGES the ownership of the pages array itself
2697  * (which must be kmalloc or vmalloc memory) and one reference per pages in it
2698  * are transferred from the caller to vmap(), and will be freed / dropped when
2699  * vfree() is called on the return value.
2700  *
2701  * Return: the address of the area or %NULL on failure
2702  */
2703 void *vmap(struct page **pages, unsigned int count,
2704            unsigned long flags, pgprot_t prot)
2705 {
2706         struct vm_struct *area;
2707         unsigned long addr;
2708         unsigned long size;             /* In bytes */
2709
2710         might_sleep();
2711
2712         if (count > totalram_pages())
2713                 return NULL;
2714
2715         size = (unsigned long)count << PAGE_SHIFT;
2716         area = get_vm_area_caller(size, flags, __builtin_return_address(0));
2717         if (!area)
2718                 return NULL;
2719
2720         addr = (unsigned long)area->addr;
2721         if (vmap_pages_range(addr, addr + size, pgprot_nx(prot),
2722                                 pages, PAGE_SHIFT) < 0) {
2723                 vunmap(area->addr);
2724                 return NULL;
2725         }
2726
2727         if (flags & VM_MAP_PUT_PAGES) {
2728                 area->pages = pages;
2729                 area->nr_pages = count;
2730         }
2731         return area->addr;
2732 }
2733 EXPORT_SYMBOL(vmap);
2734
2735 #ifdef CONFIG_VMAP_PFN
2736 struct vmap_pfn_data {
2737         unsigned long   *pfns;
2738         pgprot_t        prot;
2739         unsigned int    idx;
2740 };
2741
2742 static int vmap_pfn_apply(pte_t *pte, unsigned long addr, void *private)
2743 {
2744         struct vmap_pfn_data *data = private;
2745
2746         if (WARN_ON_ONCE(pfn_valid(data->pfns[data->idx])))
2747                 return -EINVAL;
2748         *pte = pte_mkspecial(pfn_pte(data->pfns[data->idx++], data->prot));
2749         return 0;
2750 }
2751
2752 /**
2753  * vmap_pfn - map an array of PFNs into virtually contiguous space
2754  * @pfns: array of PFNs
2755  * @count: number of pages to map
2756  * @prot: page protection for the mapping
2757  *
2758  * Maps @count PFNs from @pfns into contiguous kernel virtual space and returns
2759  * the start address of the mapping.
2760  */
2761 void *vmap_pfn(unsigned long *pfns, unsigned int count, pgprot_t prot)
2762 {
2763         struct vmap_pfn_data data = { .pfns = pfns, .prot = pgprot_nx(prot) };
2764         struct vm_struct *area;
2765
2766         area = get_vm_area_caller(count * PAGE_SIZE, VM_IOREMAP,
2767                         __builtin_return_address(0));
2768         if (!area)
2769                 return NULL;
2770         if (apply_to_page_range(&init_mm, (unsigned long)area->addr,
2771                         count * PAGE_SIZE, vmap_pfn_apply, &data)) {
2772                 free_vm_area(area);
2773                 return NULL;
2774         }
2775         return area->addr;
2776 }
2777 EXPORT_SYMBOL_GPL(vmap_pfn);
2778 #endif /* CONFIG_VMAP_PFN */
2779
2780 static inline unsigned int
2781 vm_area_alloc_pages(gfp_t gfp, int nid,
2782                 unsigned int order, unsigned int nr_pages, struct page **pages)
2783 {
2784         unsigned int nr_allocated = 0;
2785
2786         /*
2787          * For order-0 pages we make use of bulk allocator, if
2788          * the page array is partly or not at all populated due
2789          * to fails, fallback to a single page allocator that is
2790          * more permissive.
2791          */
2792         if (!order) {
2793                 while (nr_allocated < nr_pages) {
2794                         unsigned int nr, nr_pages_request;
2795
2796                         /*
2797                          * A maximum allowed request is hard-coded and is 100
2798                          * pages per call. That is done in order to prevent a
2799                          * long preemption off scenario in the bulk-allocator
2800                          * so the range is [1:100].
2801                          */
2802                         nr_pages_request = min(100U, nr_pages - nr_allocated);
2803
2804                         nr = alloc_pages_bulk_array_node(gfp, nid,
2805                                 nr_pages_request, pages + nr_allocated);
2806
2807                         nr_allocated += nr;
2808                         cond_resched();
2809
2810                         /*
2811                          * If zero or pages were obtained partly,
2812                          * fallback to a single page allocator.
2813                          */
2814                         if (nr != nr_pages_request)
2815                                 break;
2816                 }
2817         } else
2818                 /*
2819                  * Compound pages required for remap_vmalloc_page if
2820                  * high-order pages.
2821                  */
2822                 gfp |= __GFP_COMP;
2823
2824         /* High-order pages or fallback path if "bulk" fails. */
2825         while (nr_allocated < nr_pages) {
2826                 struct page *page;
2827                 int i;
2828
2829                 page = alloc_pages_node(nid, gfp, order);
2830                 if (unlikely(!page))
2831                         break;
2832
2833                 /*
2834                  * Careful, we allocate and map page-order pages, but
2835                  * tracking is done per PAGE_SIZE page so as to keep the
2836                  * vm_struct APIs independent of the physical/mapped size.
2837                  */
2838                 for (i = 0; i < (1U << order); i++)
2839                         pages[nr_allocated + i] = page + i;
2840
2841                 if (gfpflags_allow_blocking(gfp))
2842                         cond_resched();
2843
2844                 nr_allocated += 1U << order;
2845         }
2846
2847         return nr_allocated;
2848 }
2849
2850 static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask,
2851                                  pgprot_t prot, unsigned int page_shift,
2852                                  int node)
2853 {
2854         const gfp_t nested_gfp = (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO;
2855         unsigned long addr = (unsigned long)area->addr;
2856         unsigned long size = get_vm_area_size(area);
2857         unsigned long array_size;
2858         unsigned int nr_small_pages = size >> PAGE_SHIFT;
2859         unsigned int page_order;
2860
2861         array_size = (unsigned long)nr_small_pages * sizeof(struct page *);
2862         gfp_mask |= __GFP_NOWARN;
2863         if (!(gfp_mask & (GFP_DMA | GFP_DMA32)))
2864                 gfp_mask |= __GFP_HIGHMEM;
2865
2866         /* Please note that the recursion is strictly bounded. */
2867         if (array_size > PAGE_SIZE) {
2868                 area->pages = __vmalloc_node(array_size, 1, nested_gfp, node,
2869                                         area->caller);
2870         } else {
2871                 area->pages = kmalloc_node(array_size, nested_gfp, node);
2872         }
2873
2874         if (!area->pages) {
2875                 warn_alloc(gfp_mask, NULL,
2876                         "vmalloc error: size %lu, failed to allocated page array size %lu",
2877                         nr_small_pages * PAGE_SIZE, array_size);
2878                 free_vm_area(area);
2879                 return NULL;
2880         }
2881
2882         set_vm_area_page_order(area, page_shift - PAGE_SHIFT);
2883         page_order = vm_area_page_order(area);
2884
2885         area->nr_pages = vm_area_alloc_pages(gfp_mask, node,
2886                 page_order, nr_small_pages, area->pages);
2887
2888         atomic_long_add(area->nr_pages, &nr_vmalloc_pages);
2889
2890         /*
2891          * If not enough pages were obtained to accomplish an
2892          * allocation request, free them via __vfree() if any.
2893          */
2894         if (area->nr_pages != nr_small_pages) {
2895                 warn_alloc(gfp_mask, NULL,
2896                         "vmalloc error: size %lu, page order %u, failed to allocate pages",
2897                         area->nr_pages * PAGE_SIZE, page_order);
2898                 goto fail;
2899         }
2900
2901         if (vmap_pages_range(addr, addr + size, prot, area->pages,
2902                         page_shift) < 0) {
2903                 warn_alloc(gfp_mask, NULL,
2904                         "vmalloc error: size %lu, failed to map pages",
2905                         area->nr_pages * PAGE_SIZE);
2906                 goto fail;
2907         }
2908
2909         return area->addr;
2910
2911 fail:
2912         __vfree(area->addr);
2913         return NULL;
2914 }
2915
2916 /**
2917  * __vmalloc_node_range - allocate virtually contiguous memory
2918  * @size:                 allocation size
2919  * @align:                desired alignment
2920  * @start:                vm area range start
2921  * @end:                  vm area range end
2922  * @gfp_mask:             flags for the page level allocator
2923  * @prot:                 protection mask for the allocated pages
2924  * @vm_flags:             additional vm area flags (e.g. %VM_NO_GUARD)
2925  * @node:                 node to use for allocation or NUMA_NO_NODE
2926  * @caller:               caller's return address
2927  *
2928  * Allocate enough pages to cover @size from the page level
2929  * allocator with @gfp_mask flags.  Map them into contiguous
2930  * kernel virtual space, using a pagetable protection of @prot.
2931  *
2932  * Return: the address of the area or %NULL on failure
2933  */
2934 void *__vmalloc_node_range(unsigned long size, unsigned long align,
2935                         unsigned long start, unsigned long end, gfp_t gfp_mask,
2936                         pgprot_t prot, unsigned long vm_flags, int node,
2937                         const void *caller)
2938 {
2939         struct vm_struct *area;
2940         void *addr;
2941         unsigned long real_size = size;
2942         unsigned long real_align = align;
2943         unsigned int shift = PAGE_SHIFT;
2944
2945         if (WARN_ON_ONCE(!size))
2946                 return NULL;
2947
2948         if ((size >> PAGE_SHIFT) > totalram_pages()) {
2949                 warn_alloc(gfp_mask, NULL,
2950                         "vmalloc error: size %lu, exceeds total pages",
2951                         real_size);
2952                 return NULL;
2953         }
2954
2955         if (vmap_allow_huge && !(vm_flags & VM_NO_HUGE_VMAP)) {
2956                 unsigned long size_per_node;
2957
2958                 /*
2959                  * Try huge pages. Only try for PAGE_KERNEL allocations,
2960                  * others like modules don't yet expect huge pages in
2961                  * their allocations due to apply_to_page_range not
2962                  * supporting them.
2963                  */
2964
2965                 size_per_node = size;
2966                 if (node == NUMA_NO_NODE)
2967                         size_per_node /= num_online_nodes();
2968                 if (arch_vmap_pmd_supported(prot) && size_per_node >= PMD_SIZE)
2969                         shift = PMD_SHIFT;
2970                 else
2971                         shift = arch_vmap_pte_supported_shift(size_per_node);
2972
2973                 align = max(real_align, 1UL << shift);
2974                 size = ALIGN(real_size, 1UL << shift);
2975         }
2976
2977 again:
2978         area = __get_vm_area_node(real_size, align, shift, VM_ALLOC |
2979                                   VM_UNINITIALIZED | vm_flags, start, end, node,
2980                                   gfp_mask, caller);
2981         if (!area) {
2982                 warn_alloc(gfp_mask, NULL,
2983                         "vmalloc error: size %lu, vm_struct allocation failed",
2984                         real_size);
2985                 goto fail;
2986         }
2987
2988         addr = __vmalloc_area_node(area, gfp_mask, prot, shift, node);
2989         if (!addr)
2990                 goto fail;
2991
2992         /*
2993          * In this function, newly allocated vm_struct has VM_UNINITIALIZED
2994          * flag. It means that vm_struct is not fully initialized.
2995          * Now, it is fully initialized, so remove this flag here.
2996          */
2997         clear_vm_uninitialized_flag(area);
2998
2999         size = PAGE_ALIGN(size);
3000         kmemleak_vmalloc(area, size, gfp_mask);
3001
3002         return addr;
3003
3004 fail:
3005         if (shift > PAGE_SHIFT) {
3006                 shift = PAGE_SHIFT;
3007                 align = real_align;
3008                 size = real_size;
3009                 goto again;
3010         }
3011
3012         return NULL;
3013 }
3014
3015 /**
3016  * __vmalloc_node - allocate virtually contiguous memory
3017  * @size:           allocation size
3018  * @align:          desired alignment
3019  * @gfp_mask:       flags for the page level allocator
3020  * @node:           node to use for allocation or NUMA_NO_NODE
3021  * @caller:         caller's return address
3022  *
3023  * Allocate enough pages to cover @size from the page level allocator with
3024  * @gfp_mask flags.  Map them into contiguous kernel virtual space.
3025  *
3026  * Reclaim modifiers in @gfp_mask - __GFP_NORETRY, __GFP_RETRY_MAYFAIL
3027  * and __GFP_NOFAIL are not supported
3028  *
3029  * Any use of gfp flags outside of GFP_KERNEL should be consulted
3030  * with mm people.
3031  *
3032  * Return: pointer to the allocated memory or %NULL on error
3033  */
3034 void *__vmalloc_node(unsigned long size, unsigned long align,
3035                             gfp_t gfp_mask, int node, const void *caller)
3036 {
3037         return __vmalloc_node_range(size, align, VMALLOC_START, VMALLOC_END,
3038                                 gfp_mask, PAGE_KERNEL, 0, node, caller);
3039 }
3040 /*
3041  * This is only for performance analysis of vmalloc and stress purpose.
3042  * It is required by vmalloc test module, therefore do not use it other
3043  * than that.
3044  */
3045 #ifdef CONFIG_TEST_VMALLOC_MODULE
3046 EXPORT_SYMBOL_GPL(__vmalloc_node);
3047 #endif
3048
3049 void *__vmalloc(unsigned long size, gfp_t gfp_mask)
3050 {
3051         return __vmalloc_node(size, 1, gfp_mask, NUMA_NO_NODE,
3052                                 __builtin_return_address(0));
3053 }
3054 EXPORT_SYMBOL(__vmalloc);
3055
3056 /**
3057  * vmalloc - allocate virtually contiguous memory
3058  * @size:    allocation size
3059  *
3060  * Allocate enough pages to cover @size from the page level
3061  * allocator and map them into contiguous kernel virtual space.
3062  *
3063  * For tight control over page level allocator and protection flags
3064  * use __vmalloc() instead.
3065  *
3066  * Return: pointer to the allocated memory or %NULL on error
3067  */
3068 void *vmalloc(unsigned long size)
3069 {
3070         return __vmalloc_node(size, 1, GFP_KERNEL, NUMA_NO_NODE,
3071                                 __builtin_return_address(0));
3072 }
3073 EXPORT_SYMBOL(vmalloc);
3074
3075 /**
3076  * vmalloc_no_huge - allocate virtually contiguous memory using small pages
3077  * @size:    allocation size
3078  *
3079  * Allocate enough non-huge pages to cover @size from the page level
3080  * allocator and map them into contiguous kernel virtual space.
3081  *
3082  * Return: pointer to the allocated memory or %NULL on error
3083  */
3084 void *vmalloc_no_huge(unsigned long size)
3085 {
3086         return __vmalloc_node_range(size, 1, VMALLOC_START, VMALLOC_END,
3087                                     GFP_KERNEL, PAGE_KERNEL, VM_NO_HUGE_VMAP,
3088                                     NUMA_NO_NODE, __builtin_return_address(0));
3089 }
3090 EXPORT_SYMBOL(vmalloc_no_huge);
3091
3092 /**
3093  * vzalloc - allocate virtually contiguous memory with zero fill
3094  * @size:    allocation size
3095  *
3096  * Allocate enough pages to cover @size from the page level
3097  * allocator and map them into contiguous kernel virtual space.
3098  * The memory allocated is set to zero.
3099  *
3100  * For tight control over page level allocator and protection flags
3101  * use __vmalloc() instead.
3102  *
3103  * Return: pointer to the allocated memory or %NULL on error
3104  */
3105 void *vzalloc(unsigned long size)
3106 {
3107         return __vmalloc_node(size, 1, GFP_KERNEL | __GFP_ZERO, NUMA_NO_NODE,
3108                                 __builtin_return_address(0));
3109 }
3110 EXPORT_SYMBOL(vzalloc);
3111
3112 /**
3113  * vmalloc_user - allocate zeroed virtually contiguous memory for userspace
3114  * @size: allocation size
3115  *
3116  * The resulting memory area is zeroed so it can be mapped to userspace
3117  * without leaking data.
3118  *
3119  * Return: pointer to the allocated memory or %NULL on error
3120  */
3121 void *vmalloc_user(unsigned long size)
3122 {
3123         return __vmalloc_node_range(size, SHMLBA,  VMALLOC_START, VMALLOC_END,
3124                                     GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL,
3125                                     VM_USERMAP, NUMA_NO_NODE,
3126                                     __builtin_return_address(0));
3127 }
3128 EXPORT_SYMBOL(vmalloc_user);
3129
3130 /**
3131  * vmalloc_node - allocate memory on a specific node
3132  * @size:         allocation size
3133  * @node:         numa node
3134  *
3135  * Allocate enough pages to cover @size from the page level
3136  * allocator and map them into contiguous kernel virtual space.
3137  *
3138  * For tight control over page level allocator and protection flags
3139  * use __vmalloc() instead.
3140  *
3141  * Return: pointer to the allocated memory or %NULL on error
3142  */
3143 void *vmalloc_node(unsigned long size, int node)
3144 {
3145         return __vmalloc_node(size, 1, GFP_KERNEL, node,
3146                         __builtin_return_address(0));
3147 }
3148 EXPORT_SYMBOL(vmalloc_node);
3149
3150 /**
3151  * vzalloc_node - allocate memory on a specific node with zero fill
3152  * @size:       allocation size
3153  * @node:       numa node
3154  *
3155  * Allocate enough pages to cover @size from the page level
3156  * allocator and map them into contiguous kernel virtual space.
3157  * The memory allocated is set to zero.
3158  *
3159  * Return: pointer to the allocated memory or %NULL on error
3160  */
3161 void *vzalloc_node(unsigned long size, int node)
3162 {
3163         return __vmalloc_node(size, 1, GFP_KERNEL | __GFP_ZERO, node,
3164                                 __builtin_return_address(0));
3165 }
3166 EXPORT_SYMBOL(vzalloc_node);
3167
3168 #if defined(CONFIG_64BIT) && defined(CONFIG_ZONE_DMA32)
3169 #define GFP_VMALLOC32 (GFP_DMA32 | GFP_KERNEL)
3170 #elif defined(CONFIG_64BIT) && defined(CONFIG_ZONE_DMA)
3171 #define GFP_VMALLOC32 (GFP_DMA | GFP_KERNEL)
3172 #else
3173 /*
3174  * 64b systems should always have either DMA or DMA32 zones. For others
3175  * GFP_DMA32 should do the right thing and use the normal zone.
3176  */
3177 #define GFP_VMALLOC32 (GFP_DMA32 | GFP_KERNEL)
3178 #endif
3179
3180 /**
3181  * vmalloc_32 - allocate virtually contiguous memory (32bit addressable)
3182  * @size:       allocation size
3183  *
3184  * Allocate enough 32bit PA addressable pages to cover @size from the
3185  * page level allocator and map them into contiguous kernel virtual space.
3186  *
3187  * Return: pointer to the allocated memory or %NULL on error
3188  */
3189 void *vmalloc_32(unsigned long size)
3190 {
3191         return __vmalloc_node(size, 1, GFP_VMALLOC32, NUMA_NO_NODE,
3192                         __builtin_return_address(0));
3193 }
3194 EXPORT_SYMBOL(vmalloc_32);
3195
3196 /**
3197  * vmalloc_32_user - allocate zeroed virtually contiguous 32bit memory
3198  * @size:            allocation size
3199  *
3200  * The resulting memory area is 32bit addressable and zeroed so it can be
3201  * mapped to userspace without leaking data.
3202  *
3203  * Return: pointer to the allocated memory or %NULL on error
3204  */
3205 void *vmalloc_32_user(unsigned long size)
3206 {
3207         return __vmalloc_node_range(size, SHMLBA,  VMALLOC_START, VMALLOC_END,
3208                                     GFP_VMALLOC32 | __GFP_ZERO, PAGE_KERNEL,
3209                                     VM_USERMAP, NUMA_NO_NODE,
3210                                     __builtin_return_address(0));
3211 }
3212 EXPORT_SYMBOL(vmalloc_32_user);
3213
3214 /*
3215  * small helper routine , copy contents to buf from addr.
3216  * If the page is not present, fill zero.
3217  */
3218
3219 static int aligned_vread(char *buf, char *addr, unsigned long count)
3220 {
3221         struct page *p;
3222         int copied = 0;
3223
3224         while (count) {
3225                 unsigned long offset, length;
3226
3227                 offset = offset_in_page(addr);
3228                 length = PAGE_SIZE - offset;
3229                 if (length > count)
3230                         length = count;
3231                 p = vmalloc_to_page(addr);
3232                 /*
3233                  * To do safe access to this _mapped_ area, we need
3234                  * lock. But adding lock here means that we need to add
3235                  * overhead of vmalloc()/vfree() calls for this _debug_
3236                  * interface, rarely used. Instead of that, we'll use
3237                  * kmap() and get small overhead in this access function.
3238                  */
3239                 if (p) {
3240                         /* We can expect USER0 is not used -- see vread() */
3241                         void *map = kmap_atomic(p);
3242                         memcpy(buf, map + offset, length);
3243                         kunmap_atomic(map);
3244                 } else
3245                         memset(buf, 0, length);
3246
3247                 addr += length;
3248                 buf += length;
3249                 copied += length;
3250                 count -= length;
3251         }
3252         return copied;
3253 }
3254
3255 /**
3256  * vread() - read vmalloc area in a safe way.
3257  * @buf:     buffer for reading data
3258  * @addr:    vm address.
3259  * @count:   number of bytes to be read.
3260  *
3261  * This function checks that addr is a valid vmalloc'ed area, and
3262  * copy data from that area to a given buffer. If the given memory range
3263  * of [addr...addr+count) includes some valid address, data is copied to
3264  * proper area of @buf. If there are memory holes, they'll be zero-filled.
3265  * IOREMAP area is treated as memory hole and no copy is done.
3266  *
3267  * If [addr...addr+count) doesn't includes any intersects with alive
3268  * vm_struct area, returns 0. @buf should be kernel's buffer.
3269  *
3270  * Note: In usual ops, vread() is never necessary because the caller
3271  * should know vmalloc() area is valid and can use memcpy().
3272  * This is for routines which have to access vmalloc area without
3273  * any information, as /proc/kcore.
3274  *
3275  * Return: number of bytes for which addr and buf should be increased
3276  * (same number as @count) or %0 if [addr...addr+count) doesn't
3277  * include any intersection with valid vmalloc area
3278  */
3279 long vread(char *buf, char *addr, unsigned long count)
3280 {
3281         struct vmap_area *va;
3282         struct vm_struct *vm;
3283         char *vaddr, *buf_start = buf;
3284         unsigned long buflen = count;
3285         unsigned long n;
3286
3287         /* Don't allow overflow */
3288         if ((unsigned long) addr + count < count)
3289                 count = -(unsigned long) addr;
3290
3291         spin_lock(&vmap_area_lock);
3292         va = __find_vmap_area((unsigned long)addr);
3293         if (!va)
3294                 goto finished;
3295         list_for_each_entry_from(va, &vmap_area_list, list) {
3296                 if (!count)
3297                         break;
3298
3299                 if (!va->vm)
3300                         continue;
3301
3302                 vm = va->vm;
3303                 vaddr = (char *) vm->addr;
3304                 if (addr >= vaddr + get_vm_area_size(vm))
3305                         continue;
3306                 while (addr < vaddr) {
3307                         if (count == 0)
3308                                 goto finished;
3309                         *buf = '\0';
3310                         buf++;
3311                         addr++;
3312                         count--;
3313                 }
3314                 n = vaddr + get_vm_area_size(vm) - addr;
3315                 if (n > count)
3316                         n = count;
3317                 if (!(vm->flags & VM_IOREMAP))
3318                         aligned_vread(buf, addr, n);
3319                 else /* IOREMAP area is treated as memory hole */
3320                         memset(buf, 0, n);
3321                 buf += n;
3322                 addr += n;
3323                 count -= n;
3324         }
3325 finished:
3326         spin_unlock(&vmap_area_lock);
3327
3328         if (buf == buf_start)
3329                 return 0;
3330         /* zero-fill memory holes */
3331         if (buf != buf_start + buflen)
3332                 memset(buf, 0, buflen - (buf - buf_start));
3333
3334         return buflen;
3335 }
3336
3337 /**
3338  * remap_vmalloc_range_partial - map vmalloc pages to userspace
3339  * @vma:                vma to cover
3340  * @uaddr:              target user address to start at
3341  * @kaddr:              virtual address of vmalloc kernel memory
3342  * @pgoff:              offset from @kaddr to start at
3343  * @size:               size of map area
3344  *
3345  * Returns:     0 for success, -Exxx on failure
3346  *
3347  * This function checks that @kaddr is a valid vmalloc'ed area,
3348  * and that it is big enough to cover the range starting at
3349  * @uaddr in @vma. Will return failure if that criteria isn't
3350  * met.
3351  *
3352  * Similar to remap_pfn_range() (see mm/memory.c)
3353  */
3354 int remap_vmalloc_range_partial(struct vm_area_struct *vma, unsigned long uaddr,
3355                                 void *kaddr, unsigned long pgoff,
3356                                 unsigned long size)
3357 {
3358         struct vm_struct *area;
3359         unsigned long off;
3360         unsigned long end_index;
3361
3362         if (check_shl_overflow(pgoff, PAGE_SHIFT, &off))
3363                 return -EINVAL;
3364
3365         size = PAGE_ALIGN(size);
3366
3367         if (!PAGE_ALIGNED(uaddr) || !PAGE_ALIGNED(kaddr))
3368                 return -EINVAL;
3369
3370         area = find_vm_area(kaddr);
3371         if (!area)
3372                 return -EINVAL;
3373
3374         if (!(area->flags & (VM_USERMAP | VM_DMA_COHERENT)))
3375                 return -EINVAL;
3376
3377         if (check_add_overflow(size, off, &end_index) ||
3378             end_index > get_vm_area_size(area))
3379                 return -EINVAL;
3380         kaddr += off;
3381
3382         do {
3383                 struct page *page = vmalloc_to_page(kaddr);
3384                 int ret;
3385
3386                 ret = vm_insert_page(vma, uaddr, page);
3387                 if (ret)
3388                         return ret;
3389
3390                 uaddr += PAGE_SIZE;
3391                 kaddr += PAGE_SIZE;
3392                 size -= PAGE_SIZE;
3393         } while (size > 0);
3394
3395         vma->vm_flags |= VM_DONTEXPAND | VM_DONTDUMP;
3396
3397         return 0;
3398 }
3399
3400 /**
3401  * remap_vmalloc_range - map vmalloc pages to userspace
3402  * @vma:                vma to cover (map full range of vma)
3403  * @addr:               vmalloc memory
3404  * @pgoff:              number of pages into addr before first page to map
3405  *
3406  * Returns:     0 for success, -Exxx on failure
3407  *
3408  * This function checks that addr is a valid vmalloc'ed area, and
3409  * that it is big enough to cover the vma. Will return failure if
3410  * that criteria isn't met.
3411  *
3412  * Similar to remap_pfn_range() (see mm/memory.c)
3413  */
3414 int remap_vmalloc_range(struct vm_area_struct *vma, void *addr,
3415                                                 unsigned long pgoff)
3416 {
3417         return remap_vmalloc_range_partial(vma, vma->vm_start,
3418                                            addr, pgoff,
3419                                            vma->vm_end - vma->vm_start);
3420 }
3421 EXPORT_SYMBOL(remap_vmalloc_range);
3422
3423 void free_vm_area(struct vm_struct *area)
3424 {
3425         struct vm_struct *ret;
3426         ret = remove_vm_area(area->addr);
3427         BUG_ON(ret != area);
3428         kfree(area);
3429 }
3430 EXPORT_SYMBOL_GPL(free_vm_area);
3431
3432 #ifdef CONFIG_SMP
3433 static struct vmap_area *node_to_va(struct rb_node *n)
3434 {
3435         return rb_entry_safe(n, struct vmap_area, rb_node);
3436 }
3437
3438 /**
3439  * pvm_find_va_enclose_addr - find the vmap_area @addr belongs to
3440  * @addr: target address
3441  *
3442  * Returns: vmap_area if it is found. If there is no such area
3443  *   the first highest(reverse order) vmap_area is returned
3444  *   i.e. va->va_start < addr && va->va_end < addr or NULL
3445  *   if there are no any areas before @addr.
3446  */
3447 static struct vmap_area *
3448 pvm_find_va_enclose_addr(unsigned long addr)
3449 {
3450         struct vmap_area *va, *tmp;
3451         struct rb_node *n;
3452
3453         n = free_vmap_area_root.rb_node;
3454         va = NULL;
3455
3456         while (n) {
3457                 tmp = rb_entry(n, struct vmap_area, rb_node);
3458                 if (tmp->va_start <= addr) {
3459                         va = tmp;
3460                         if (tmp->va_end >= addr)
3461                                 break;
3462
3463                         n = n->rb_right;
3464                 } else {
3465                         n = n->rb_left;
3466                 }
3467         }
3468
3469         return va;
3470 }
3471
3472 /**
3473  * pvm_determine_end_from_reverse - find the highest aligned address
3474  * of free block below VMALLOC_END
3475  * @va:
3476  *   in - the VA we start the search(reverse order);
3477  *   out - the VA with the highest aligned end address.
3478  * @align: alignment for required highest address
3479  *
3480  * Returns: determined end address within vmap_area
3481  */
3482 static unsigned long
3483 pvm_determine_end_from_reverse(struct vmap_area **va, unsigned long align)
3484 {
3485         unsigned long vmalloc_end = VMALLOC_END & ~(align - 1);
3486         unsigned long addr;
3487
3488         if (likely(*va)) {
3489                 list_for_each_entry_from_reverse((*va),
3490                                 &free_vmap_area_list, list) {
3491                         addr = min((*va)->va_end & ~(align - 1), vmalloc_end);
3492                         if ((*va)->va_start < addr)
3493                                 return addr;
3494                 }
3495         }
3496
3497         return 0;
3498 }
3499
3500 /**
3501  * pcpu_get_vm_areas - allocate vmalloc areas for percpu allocator
3502  * @offsets: array containing offset of each area
3503  * @sizes: array containing size of each area
3504  * @nr_vms: the number of areas to allocate
3505  * @align: alignment, all entries in @offsets and @sizes must be aligned to this
3506  *
3507  * Returns: kmalloc'd vm_struct pointer array pointing to allocated
3508  *          vm_structs on success, %NULL on failure
3509  *
3510  * Percpu allocator wants to use congruent vm areas so that it can
3511  * maintain the offsets among percpu areas.  This function allocates
3512  * congruent vmalloc areas for it with GFP_KERNEL.  These areas tend to
3513  * be scattered pretty far, distance between two areas easily going up
3514  * to gigabytes.  To avoid interacting with regular vmallocs, these
3515  * areas are allocated from top.
3516  *
3517  * Despite its complicated look, this allocator is rather simple. It
3518  * does everything top-down and scans free blocks from the end looking
3519  * for matching base. While scanning, if any of the areas do not fit the
3520  * base address is pulled down to fit the area. Scanning is repeated till
3521  * all the areas fit and then all necessary data structures are inserted
3522  * and the result is returned.
3523  */
3524 struct vm_struct **pcpu_get_vm_areas(const unsigned long *offsets,
3525                                      const size_t *sizes, int nr_vms,
3526                                      size_t align)
3527 {
3528         const unsigned long vmalloc_start = ALIGN(VMALLOC_START, align);
3529         const unsigned long vmalloc_end = VMALLOC_END & ~(align - 1);
3530         struct vmap_area **vas, *va;
3531         struct vm_struct **vms;
3532         int area, area2, last_area, term_area;
3533         unsigned long base, start, size, end, last_end, orig_start, orig_end;
3534         bool purged = false;
3535         enum fit_type type;
3536
3537         /* verify parameters and allocate data structures */
3538         BUG_ON(offset_in_page(align) || !is_power_of_2(align));
3539         for (last_area = 0, area = 0; area < nr_vms; area++) {
3540                 start = offsets[area];
3541                 end = start + sizes[area];
3542
3543                 /* is everything aligned properly? */
3544                 BUG_ON(!IS_ALIGNED(offsets[area], align));
3545                 BUG_ON(!IS_ALIGNED(sizes[area], align));
3546
3547                 /* detect the area with the highest address */
3548                 if (start > offsets[last_area])
3549                         last_area = area;
3550
3551                 for (area2 = area + 1; area2 < nr_vms; area2++) {
3552                         unsigned long start2 = offsets[area2];
3553                         unsigned long end2 = start2 + sizes[area2];
3554
3555                         BUG_ON(start2 < end && start < end2);
3556                 }
3557         }
3558         last_end = offsets[last_area] + sizes[last_area];
3559
3560         if (vmalloc_end - vmalloc_start < last_end) {
3561                 WARN_ON(true);
3562                 return NULL;
3563         }
3564
3565         vms = kcalloc(nr_vms, sizeof(vms[0]), GFP_KERNEL);
3566         vas = kcalloc(nr_vms, sizeof(vas[0]), GFP_KERNEL);
3567         if (!vas || !vms)
3568                 goto err_free2;
3569
3570         for (area = 0; area < nr_vms; area++) {
3571                 vas[area] = kmem_cache_zalloc(vmap_area_cachep, GFP_KERNEL);
3572                 vms[area] = kzalloc(sizeof(struct vm_struct), GFP_KERNEL);
3573                 if (!vas[area] || !vms[area])
3574                         goto err_free;
3575         }
3576 retry:
3577         spin_lock(&free_vmap_area_lock);
3578
3579         /* start scanning - we scan from the top, begin with the last area */
3580         area = term_area = last_area;
3581         start = offsets[area];
3582         end = start + sizes[area];
3583
3584         va = pvm_find_va_enclose_addr(vmalloc_end);
3585         base = pvm_determine_end_from_reverse(&va, align) - end;
3586
3587         while (true) {
3588                 /*
3589                  * base might have underflowed, add last_end before
3590                  * comparing.
3591                  */
3592                 if (base + last_end < vmalloc_start + last_end)
3593                         goto overflow;
3594
3595                 /*
3596                  * Fitting base has not been found.
3597                  */
3598                 if (va == NULL)
3599                         goto overflow;
3600
3601                 /*
3602                  * If required width exceeds current VA block, move
3603                  * base downwards and then recheck.
3604                  */
3605                 if (base + end > va->va_end) {
3606                         base = pvm_determine_end_from_reverse(&va, align) - end;
3607                         term_area = area;
3608                         continue;
3609                 }
3610
3611                 /*
3612                  * If this VA does not fit, move base downwards and recheck.
3613                  */
3614                 if (base + start < va->va_start) {
3615                         va = node_to_va(rb_prev(&va->rb_node));
3616                         base = pvm_determine_end_from_reverse(&va, align) - end;
3617                         term_area = area;
3618                         continue;
3619                 }
3620
3621                 /*
3622                  * This area fits, move on to the previous one.  If
3623                  * the previous one is the terminal one, we're done.
3624                  */
3625                 area = (area + nr_vms - 1) % nr_vms;
3626                 if (area == term_area)
3627                         break;
3628
3629                 start = offsets[area];
3630                 end = start + sizes[area];
3631                 va = pvm_find_va_enclose_addr(base + end);
3632         }
3633
3634         /* we've found a fitting base, insert all va's */
3635         for (area = 0; area < nr_vms; area++) {
3636                 int ret;
3637
3638                 start = base + offsets[area];
3639                 size = sizes[area];
3640
3641                 va = pvm_find_va_enclose_addr(start);
3642                 if (WARN_ON_ONCE(va == NULL))
3643                         /* It is a BUG(), but trigger recovery instead. */
3644                         goto recovery;
3645
3646                 type = classify_va_fit_type(va, start, size);
3647                 if (WARN_ON_ONCE(type == NOTHING_FIT))
3648                         /* It is a BUG(), but trigger recovery instead. */
3649                         goto recovery;
3650
3651                 ret = adjust_va_to_fit_type(va, start, size, type);
3652                 if (unlikely(ret))
3653                         goto recovery;
3654
3655                 /* Allocated area. */
3656                 va = vas[area];
3657                 va->va_start = start;
3658                 va->va_end = start + size;
3659         }
3660
3661         spin_unlock(&free_vmap_area_lock);
3662
3663         /* populate the kasan shadow space */
3664         for (area = 0; area < nr_vms; area++) {
3665                 if (kasan_populate_vmalloc(vas[area]->va_start, sizes[area]))
3666                         goto err_free_shadow;
3667
3668                 kasan_unpoison_vmalloc((void *)vas[area]->va_start,
3669                                        sizes[area]);
3670         }
3671
3672         /* insert all vm's */
3673         spin_lock(&vmap_area_lock);
3674         for (area = 0; area < nr_vms; area++) {
3675                 insert_vmap_area(vas[area], &vmap_area_root, &vmap_area_list);
3676
3677                 setup_vmalloc_vm_locked(vms[area], vas[area], VM_ALLOC,
3678                                  pcpu_get_vm_areas);
3679         }
3680         spin_unlock(&vmap_area_lock);
3681
3682         kfree(vas);
3683         return vms;
3684
3685 recovery:
3686         /*
3687          * Remove previously allocated areas. There is no
3688          * need in removing these areas from the busy tree,
3689          * because they are inserted only on the final step
3690          * and when pcpu_get_vm_areas() is success.
3691          */
3692         while (area--) {
3693                 orig_start = vas[area]->va_start;
3694                 orig_end = vas[area]->va_end;
3695                 va = merge_or_add_vmap_area_augment(vas[area], &free_vmap_area_root,
3696                                 &free_vmap_area_list);
3697                 if (va)
3698                         kasan_release_vmalloc(orig_start, orig_end,
3699                                 va->va_start, va->va_end);
3700                 vas[area] = NULL;
3701         }
3702
3703 overflow:
3704         spin_unlock(&free_vmap_area_lock);
3705         if (!purged) {
3706                 purge_vmap_area_lazy();
3707                 purged = true;
3708
3709                 /* Before "retry", check if we recover. */
3710                 for (area = 0; area < nr_vms; area++) {
3711                         if (vas[area])
3712                                 continue;
3713
3714                         vas[area] = kmem_cache_zalloc(
3715                                 vmap_area_cachep, GFP_KERNEL);
3716                         if (!vas[area])
3717                                 goto err_free;
3718                 }
3719
3720                 goto retry;
3721         }
3722
3723 err_free:
3724         for (area = 0; area < nr_vms; area++) {
3725                 if (vas[area])
3726                         kmem_cache_free(vmap_area_cachep, vas[area]);
3727
3728                 kfree(vms[area]);
3729         }
3730 err_free2:
3731         kfree(vas);
3732         kfree(vms);
3733         return NULL;
3734
3735 err_free_shadow:
3736         spin_lock(&free_vmap_area_lock);
3737         /*
3738          * We release all the vmalloc shadows, even the ones for regions that
3739          * hadn't been successfully added. This relies on kasan_release_vmalloc
3740          * being able to tolerate this case.
3741          */
3742         for (area = 0; area < nr_vms; area++) {
3743                 orig_start = vas[area]->va_start;
3744                 orig_end = vas[area]->va_end;
3745                 va = merge_or_add_vmap_area_augment(vas[area], &free_vmap_area_root,
3746                                 &free_vmap_area_list);
3747                 if (va)
3748                         kasan_release_vmalloc(orig_start, orig_end,
3749                                 va->va_start, va->va_end);
3750                 vas[area] = NULL;
3751                 kfree(vms[area]);
3752         }
3753         spin_unlock(&free_vmap_area_lock);
3754         kfree(vas);
3755         kfree(vms);
3756         return NULL;
3757 }
3758
3759 /**
3760  * pcpu_free_vm_areas - free vmalloc areas for percpu allocator
3761  * @vms: vm_struct pointer array returned by pcpu_get_vm_areas()
3762  * @nr_vms: the number of allocated areas
3763  *
3764  * Free vm_structs and the array allocated by pcpu_get_vm_areas().
3765  */
3766 void pcpu_free_vm_areas(struct vm_struct **vms, int nr_vms)
3767 {
3768         int i;
3769
3770         for (i = 0; i < nr_vms; i++)
3771                 free_vm_area(vms[i]);
3772         kfree(vms);
3773 }
3774 #endif  /* CONFIG_SMP */
3775
3776 #ifdef CONFIG_PRINTK
3777 bool vmalloc_dump_obj(void *object)
3778 {
3779         struct vm_struct *vm;
3780         void *objp = (void *)PAGE_ALIGN((unsigned long)object);
3781
3782         vm = find_vm_area(objp);
3783         if (!vm)
3784                 return false;
3785         pr_cont(" %u-page vmalloc region starting at %#lx allocated at %pS\n",
3786                 vm->nr_pages, (unsigned long)vm->addr, vm->caller);
3787         return true;
3788 }
3789 #endif
3790
3791 #ifdef CONFIG_PROC_FS
3792 static void *s_start(struct seq_file *m, loff_t *pos)
3793         __acquires(&vmap_purge_lock)
3794         __acquires(&vmap_area_lock)
3795 {
3796         mutex_lock(&vmap_purge_lock);
3797         spin_lock(&vmap_area_lock);
3798
3799         return seq_list_start(&vmap_area_list, *pos);
3800 }
3801
3802 static void *s_next(struct seq_file *m, void *p, loff_t *pos)
3803 {
3804         return seq_list_next(p, &vmap_area_list, pos);
3805 }
3806
3807 static void s_stop(struct seq_file *m, void *p)
3808         __releases(&vmap_area_lock)
3809         __releases(&vmap_purge_lock)
3810 {
3811         spin_unlock(&vmap_area_lock);
3812         mutex_unlock(&vmap_purge_lock);
3813 }
3814
3815 static void show_numa_info(struct seq_file *m, struct vm_struct *v)
3816 {
3817         if (IS_ENABLED(CONFIG_NUMA)) {
3818                 unsigned int nr, *counters = m->private;
3819
3820                 if (!counters)
3821                         return;
3822
3823                 if (v->flags & VM_UNINITIALIZED)
3824                         return;
3825                 /* Pair with smp_wmb() in clear_vm_uninitialized_flag() */
3826                 smp_rmb();
3827
3828                 memset(counters, 0, nr_node_ids * sizeof(unsigned int));
3829
3830                 for (nr = 0; nr < v->nr_pages; nr++)
3831                         counters[page_to_nid(v->pages[nr])]++;
3832
3833                 for_each_node_state(nr, N_HIGH_MEMORY)
3834                         if (counters[nr])
3835                                 seq_printf(m, " N%u=%u", nr, counters[nr]);
3836         }
3837 }
3838
3839 static void show_purge_info(struct seq_file *m)
3840 {
3841         struct vmap_area *va;
3842
3843         spin_lock(&purge_vmap_area_lock);
3844         list_for_each_entry(va, &purge_vmap_area_list, list) {
3845                 seq_printf(m, "0x%pK-0x%pK %7ld unpurged vm_area\n",
3846                         (void *)va->va_start, (void *)va->va_end,
3847                         va->va_end - va->va_start);
3848         }
3849         spin_unlock(&purge_vmap_area_lock);
3850 }
3851
3852 static int s_show(struct seq_file *m, void *p)
3853 {
3854         struct vmap_area *va;
3855         struct vm_struct *v;
3856
3857         va = list_entry(p, struct vmap_area, list);
3858
3859         /*
3860          * s_show can encounter race with remove_vm_area, !vm on behalf
3861          * of vmap area is being tear down or vm_map_ram allocation.
3862          */
3863         if (!va->vm) {
3864                 seq_printf(m, "0x%pK-0x%pK %7ld vm_map_ram\n",
3865                         (void *)va->va_start, (void *)va->va_end,
3866                         va->va_end - va->va_start);
3867
3868                 return 0;
3869         }
3870
3871         v = va->vm;
3872
3873         seq_printf(m, "0x%pK-0x%pK %7ld",
3874                 v->addr, v->addr + v->size, v->size);
3875
3876         if (v->caller)
3877                 seq_printf(m, " %pS", v->caller);
3878
3879         if (v->nr_pages)
3880                 seq_printf(m, " pages=%d", v->nr_pages);
3881
3882         if (v->phys_addr)
3883                 seq_printf(m, " phys=%pa", &v->phys_addr);
3884
3885         if (v->flags & VM_IOREMAP)
3886                 seq_puts(m, " ioremap");
3887
3888         if (v->flags & VM_ALLOC)
3889                 seq_puts(m, " vmalloc");
3890
3891         if (v->flags & VM_MAP)
3892                 seq_puts(m, " vmap");
3893
3894         if (v->flags & VM_USERMAP)
3895                 seq_puts(m, " user");
3896
3897         if (v->flags & VM_DMA_COHERENT)
3898                 seq_puts(m, " dma-coherent");
3899
3900         if (is_vmalloc_addr(v->pages))
3901                 seq_puts(m, " vpages");
3902
3903         show_numa_info(m, v);
3904         seq_putc(m, '\n');
3905
3906         /*
3907          * As a final step, dump "unpurged" areas.
3908          */
3909         if (list_is_last(&va->list, &vmap_area_list))
3910                 show_purge_info(m);
3911
3912         return 0;
3913 }
3914
3915 static const struct seq_operations vmalloc_op = {
3916         .start = s_start,
3917         .next = s_next,
3918         .stop = s_stop,
3919         .show = s_show,
3920 };
3921
3922 static int __init proc_vmalloc_init(void)
3923 {
3924         if (IS_ENABLED(CONFIG_NUMA))
3925                 proc_create_seq_private("vmallocinfo", 0400, NULL,
3926                                 &vmalloc_op,
3927                                 nr_node_ids * sizeof(unsigned int), NULL);
3928         else
3929                 proc_create_seq("vmallocinfo", 0400, NULL, &vmalloc_op);
3930         return 0;
3931 }
3932 module_init(proc_vmalloc_init);
3933
3934 #endif