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 long 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                 nr_allocated = alloc_pages_bulk_array_node(
2794                         gfp, nid, nr_pages, pages);
2795         else
2796                 /*
2797                  * Compound pages required for remap_vmalloc_page if
2798                  * high-order pages.
2799                  */
2800                 gfp |= __GFP_COMP;
2801
2802         /* High-order pages or fallback path if "bulk" fails. */
2803         while (nr_allocated < nr_pages) {
2804                 struct page *page;
2805                 int i;
2806
2807                 page = alloc_pages_node(nid, gfp, order);
2808                 if (unlikely(!page))
2809                         break;
2810
2811                 /*
2812                  * Careful, we allocate and map page-order pages, but
2813                  * tracking is done per PAGE_SIZE page so as to keep the
2814                  * vm_struct APIs independent of the physical/mapped size.
2815                  */
2816                 for (i = 0; i < (1U << order); i++)
2817                         pages[nr_allocated + i] = page + i;
2818
2819                 if (gfpflags_allow_blocking(gfp))
2820                         cond_resched();
2821
2822                 nr_allocated += 1U << order;
2823         }
2824
2825         return nr_allocated;
2826 }
2827
2828 static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask,
2829                                  pgprot_t prot, unsigned int page_shift,
2830                                  int node)
2831 {
2832         const gfp_t nested_gfp = (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO;
2833         unsigned long addr = (unsigned long)area->addr;
2834         unsigned long size = get_vm_area_size(area);
2835         unsigned long array_size;
2836         unsigned int nr_small_pages = size >> PAGE_SHIFT;
2837         unsigned int page_order;
2838
2839         array_size = (unsigned long)nr_small_pages * sizeof(struct page *);
2840         gfp_mask |= __GFP_NOWARN;
2841         if (!(gfp_mask & (GFP_DMA | GFP_DMA32)))
2842                 gfp_mask |= __GFP_HIGHMEM;
2843
2844         /* Please note that the recursion is strictly bounded. */
2845         if (array_size > PAGE_SIZE) {
2846                 area->pages = __vmalloc_node(array_size, 1, nested_gfp, node,
2847                                         area->caller);
2848         } else {
2849                 area->pages = kmalloc_node(array_size, nested_gfp, node);
2850         }
2851
2852         if (!area->pages) {
2853                 warn_alloc(gfp_mask, NULL,
2854                         "vmalloc error: size %lu, failed to allocated page array size %lu",
2855                         nr_small_pages * PAGE_SIZE, array_size);
2856                 free_vm_area(area);
2857                 return NULL;
2858         }
2859
2860         set_vm_area_page_order(area, page_shift - PAGE_SHIFT);
2861         page_order = vm_area_page_order(area);
2862
2863         area->nr_pages = vm_area_alloc_pages(gfp_mask, node,
2864                 page_order, nr_small_pages, area->pages);
2865
2866         atomic_long_add(area->nr_pages, &nr_vmalloc_pages);
2867
2868         /*
2869          * If not enough pages were obtained to accomplish an
2870          * allocation request, free them via __vfree() if any.
2871          */
2872         if (area->nr_pages != nr_small_pages) {
2873                 warn_alloc(gfp_mask, NULL,
2874                         "vmalloc error: size %lu, page order %u, failed to allocate pages",
2875                         area->nr_pages * PAGE_SIZE, page_order);
2876                 goto fail;
2877         }
2878
2879         if (vmap_pages_range(addr, addr + size, prot, area->pages,
2880                         page_shift) < 0) {
2881                 warn_alloc(gfp_mask, NULL,
2882                         "vmalloc error: size %lu, failed to map pages",
2883                         area->nr_pages * PAGE_SIZE);
2884                 goto fail;
2885         }
2886
2887         return area->addr;
2888
2889 fail:
2890         __vfree(area->addr);
2891         return NULL;
2892 }
2893
2894 /**
2895  * __vmalloc_node_range - allocate virtually contiguous memory
2896  * @size:                 allocation size
2897  * @align:                desired alignment
2898  * @start:                vm area range start
2899  * @end:                  vm area range end
2900  * @gfp_mask:             flags for the page level allocator
2901  * @prot:                 protection mask for the allocated pages
2902  * @vm_flags:             additional vm area flags (e.g. %VM_NO_GUARD)
2903  * @node:                 node to use for allocation or NUMA_NO_NODE
2904  * @caller:               caller's return address
2905  *
2906  * Allocate enough pages to cover @size from the page level
2907  * allocator with @gfp_mask flags.  Map them into contiguous
2908  * kernel virtual space, using a pagetable protection of @prot.
2909  *
2910  * Return: the address of the area or %NULL on failure
2911  */
2912 void *__vmalloc_node_range(unsigned long size, unsigned long align,
2913                         unsigned long start, unsigned long end, gfp_t gfp_mask,
2914                         pgprot_t prot, unsigned long vm_flags, int node,
2915                         const void *caller)
2916 {
2917         struct vm_struct *area;
2918         void *addr;
2919         unsigned long real_size = size;
2920         unsigned long real_align = align;
2921         unsigned int shift = PAGE_SHIFT;
2922
2923         if (WARN_ON_ONCE(!size))
2924                 return NULL;
2925
2926         if ((size >> PAGE_SHIFT) > totalram_pages()) {
2927                 warn_alloc(gfp_mask, NULL,
2928                         "vmalloc error: size %lu, exceeds total pages",
2929                         real_size);
2930                 return NULL;
2931         }
2932
2933         if (vmap_allow_huge && !(vm_flags & VM_NO_HUGE_VMAP)) {
2934                 unsigned long size_per_node;
2935
2936                 /*
2937                  * Try huge pages. Only try for PAGE_KERNEL allocations,
2938                  * others like modules don't yet expect huge pages in
2939                  * their allocations due to apply_to_page_range not
2940                  * supporting them.
2941                  */
2942
2943                 size_per_node = size;
2944                 if (node == NUMA_NO_NODE)
2945                         size_per_node /= num_online_nodes();
2946                 if (arch_vmap_pmd_supported(prot) && size_per_node >= PMD_SIZE)
2947                         shift = PMD_SHIFT;
2948                 else
2949                         shift = arch_vmap_pte_supported_shift(size_per_node);
2950
2951                 align = max(real_align, 1UL << shift);
2952                 size = ALIGN(real_size, 1UL << shift);
2953         }
2954
2955 again:
2956         area = __get_vm_area_node(real_size, align, shift, VM_ALLOC |
2957                                   VM_UNINITIALIZED | vm_flags, start, end, node,
2958                                   gfp_mask, caller);
2959         if (!area) {
2960                 warn_alloc(gfp_mask, NULL,
2961                         "vmalloc error: size %lu, vm_struct allocation failed",
2962                         real_size);
2963                 goto fail;
2964         }
2965
2966         addr = __vmalloc_area_node(area, gfp_mask, prot, shift, node);
2967         if (!addr)
2968                 goto fail;
2969
2970         /*
2971          * In this function, newly allocated vm_struct has VM_UNINITIALIZED
2972          * flag. It means that vm_struct is not fully initialized.
2973          * Now, it is fully initialized, so remove this flag here.
2974          */
2975         clear_vm_uninitialized_flag(area);
2976
2977         size = PAGE_ALIGN(size);
2978         kmemleak_vmalloc(area, size, gfp_mask);
2979
2980         return addr;
2981
2982 fail:
2983         if (shift > PAGE_SHIFT) {
2984                 shift = PAGE_SHIFT;
2985                 align = real_align;
2986                 size = real_size;
2987                 goto again;
2988         }
2989
2990         return NULL;
2991 }
2992
2993 /**
2994  * __vmalloc_node - allocate virtually contiguous memory
2995  * @size:           allocation size
2996  * @align:          desired alignment
2997  * @gfp_mask:       flags for the page level allocator
2998  * @node:           node to use for allocation or NUMA_NO_NODE
2999  * @caller:         caller's return address
3000  *
3001  * Allocate enough pages to cover @size from the page level allocator with
3002  * @gfp_mask flags.  Map them into contiguous kernel virtual space.
3003  *
3004  * Reclaim modifiers in @gfp_mask - __GFP_NORETRY, __GFP_RETRY_MAYFAIL
3005  * and __GFP_NOFAIL are not supported
3006  *
3007  * Any use of gfp flags outside of GFP_KERNEL should be consulted
3008  * with mm people.
3009  *
3010  * Return: pointer to the allocated memory or %NULL on error
3011  */
3012 void *__vmalloc_node(unsigned long size, unsigned long align,
3013                             gfp_t gfp_mask, int node, const void *caller)
3014 {
3015         return __vmalloc_node_range(size, align, VMALLOC_START, VMALLOC_END,
3016                                 gfp_mask, PAGE_KERNEL, 0, node, caller);
3017 }
3018 /*
3019  * This is only for performance analysis of vmalloc and stress purpose.
3020  * It is required by vmalloc test module, therefore do not use it other
3021  * than that.
3022  */
3023 #ifdef CONFIG_TEST_VMALLOC_MODULE
3024 EXPORT_SYMBOL_GPL(__vmalloc_node);
3025 #endif
3026
3027 void *__vmalloc(unsigned long size, gfp_t gfp_mask)
3028 {
3029         return __vmalloc_node(size, 1, gfp_mask, NUMA_NO_NODE,
3030                                 __builtin_return_address(0));
3031 }
3032 EXPORT_SYMBOL(__vmalloc);
3033
3034 /**
3035  * vmalloc - allocate virtually contiguous memory
3036  * @size:    allocation size
3037  *
3038  * Allocate enough pages to cover @size from the page level
3039  * allocator and map them into contiguous kernel virtual space.
3040  *
3041  * For tight control over page level allocator and protection flags
3042  * use __vmalloc() instead.
3043  *
3044  * Return: pointer to the allocated memory or %NULL on error
3045  */
3046 void *vmalloc(unsigned long size)
3047 {
3048         return __vmalloc_node(size, 1, GFP_KERNEL, NUMA_NO_NODE,
3049                                 __builtin_return_address(0));
3050 }
3051 EXPORT_SYMBOL(vmalloc);
3052
3053 /**
3054  * vmalloc_no_huge - allocate virtually contiguous memory using small pages
3055  * @size:    allocation size
3056  *
3057  * Allocate enough non-huge pages to cover @size from the page level
3058  * allocator and map them into contiguous kernel virtual space.
3059  *
3060  * Return: pointer to the allocated memory or %NULL on error
3061  */
3062 void *vmalloc_no_huge(unsigned long size)
3063 {
3064         return __vmalloc_node_range(size, 1, VMALLOC_START, VMALLOC_END,
3065                                     GFP_KERNEL, PAGE_KERNEL, VM_NO_HUGE_VMAP,
3066                                     NUMA_NO_NODE, __builtin_return_address(0));
3067 }
3068 EXPORT_SYMBOL(vmalloc_no_huge);
3069
3070 /**
3071  * vzalloc - allocate virtually contiguous memory with zero fill
3072  * @size:    allocation size
3073  *
3074  * Allocate enough pages to cover @size from the page level
3075  * allocator and map them into contiguous kernel virtual space.
3076  * The memory allocated is set to zero.
3077  *
3078  * For tight control over page level allocator and protection flags
3079  * use __vmalloc() instead.
3080  *
3081  * Return: pointer to the allocated memory or %NULL on error
3082  */
3083 void *vzalloc(unsigned long size)
3084 {
3085         return __vmalloc_node(size, 1, GFP_KERNEL | __GFP_ZERO, NUMA_NO_NODE,
3086                                 __builtin_return_address(0));
3087 }
3088 EXPORT_SYMBOL(vzalloc);
3089
3090 /**
3091  * vmalloc_user - allocate zeroed virtually contiguous memory for userspace
3092  * @size: allocation size
3093  *
3094  * The resulting memory area is zeroed so it can be mapped to userspace
3095  * without leaking data.
3096  *
3097  * Return: pointer to the allocated memory or %NULL on error
3098  */
3099 void *vmalloc_user(unsigned long size)
3100 {
3101         return __vmalloc_node_range(size, SHMLBA,  VMALLOC_START, VMALLOC_END,
3102                                     GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL,
3103                                     VM_USERMAP, NUMA_NO_NODE,
3104                                     __builtin_return_address(0));
3105 }
3106 EXPORT_SYMBOL(vmalloc_user);
3107
3108 /**
3109  * vmalloc_node - allocate memory on a specific node
3110  * @size:         allocation size
3111  * @node:         numa node
3112  *
3113  * Allocate enough pages to cover @size from the page level
3114  * allocator and map them into contiguous kernel virtual space.
3115  *
3116  * For tight control over page level allocator and protection flags
3117  * use __vmalloc() instead.
3118  *
3119  * Return: pointer to the allocated memory or %NULL on error
3120  */
3121 void *vmalloc_node(unsigned long size, int node)
3122 {
3123         return __vmalloc_node(size, 1, GFP_KERNEL, node,
3124                         __builtin_return_address(0));
3125 }
3126 EXPORT_SYMBOL(vmalloc_node);
3127
3128 /**
3129  * vzalloc_node - allocate memory on a specific node with zero fill
3130  * @size:       allocation size
3131  * @node:       numa node
3132  *
3133  * Allocate enough pages to cover @size from the page level
3134  * allocator and map them into contiguous kernel virtual space.
3135  * The memory allocated is set to zero.
3136  *
3137  * Return: pointer to the allocated memory or %NULL on error
3138  */
3139 void *vzalloc_node(unsigned long size, int node)
3140 {
3141         return __vmalloc_node(size, 1, GFP_KERNEL | __GFP_ZERO, node,
3142                                 __builtin_return_address(0));
3143 }
3144 EXPORT_SYMBOL(vzalloc_node);
3145
3146 #if defined(CONFIG_64BIT) && defined(CONFIG_ZONE_DMA32)
3147 #define GFP_VMALLOC32 (GFP_DMA32 | GFP_KERNEL)
3148 #elif defined(CONFIG_64BIT) && defined(CONFIG_ZONE_DMA)
3149 #define GFP_VMALLOC32 (GFP_DMA | GFP_KERNEL)
3150 #else
3151 /*
3152  * 64b systems should always have either DMA or DMA32 zones. For others
3153  * GFP_DMA32 should do the right thing and use the normal zone.
3154  */
3155 #define GFP_VMALLOC32 (GFP_DMA32 | GFP_KERNEL)
3156 #endif
3157
3158 /**
3159  * vmalloc_32 - allocate virtually contiguous memory (32bit addressable)
3160  * @size:       allocation size
3161  *
3162  * Allocate enough 32bit PA addressable pages to cover @size from the
3163  * page level allocator and map them into contiguous kernel virtual space.
3164  *
3165  * Return: pointer to the allocated memory or %NULL on error
3166  */
3167 void *vmalloc_32(unsigned long size)
3168 {
3169         return __vmalloc_node(size, 1, GFP_VMALLOC32, NUMA_NO_NODE,
3170                         __builtin_return_address(0));
3171 }
3172 EXPORT_SYMBOL(vmalloc_32);
3173
3174 /**
3175  * vmalloc_32_user - allocate zeroed virtually contiguous 32bit memory
3176  * @size:            allocation size
3177  *
3178  * The resulting memory area is 32bit addressable and zeroed so it can be
3179  * mapped to userspace without leaking data.
3180  *
3181  * Return: pointer to the allocated memory or %NULL on error
3182  */
3183 void *vmalloc_32_user(unsigned long size)
3184 {
3185         return __vmalloc_node_range(size, SHMLBA,  VMALLOC_START, VMALLOC_END,
3186                                     GFP_VMALLOC32 | __GFP_ZERO, PAGE_KERNEL,
3187                                     VM_USERMAP, NUMA_NO_NODE,
3188                                     __builtin_return_address(0));
3189 }
3190 EXPORT_SYMBOL(vmalloc_32_user);
3191
3192 /*
3193  * small helper routine , copy contents to buf from addr.
3194  * If the page is not present, fill zero.
3195  */
3196
3197 static int aligned_vread(char *buf, char *addr, unsigned long count)
3198 {
3199         struct page *p;
3200         int copied = 0;
3201
3202         while (count) {
3203                 unsigned long offset, length;
3204
3205                 offset = offset_in_page(addr);
3206                 length = PAGE_SIZE - offset;
3207                 if (length > count)
3208                         length = count;
3209                 p = vmalloc_to_page(addr);
3210                 /*
3211                  * To do safe access to this _mapped_ area, we need
3212                  * lock. But adding lock here means that we need to add
3213                  * overhead of vmalloc()/vfree() calls for this _debug_
3214                  * interface, rarely used. Instead of that, we'll use
3215                  * kmap() and get small overhead in this access function.
3216                  */
3217                 if (p) {
3218                         /* We can expect USER0 is not used -- see vread() */
3219                         void *map = kmap_atomic(p);
3220                         memcpy(buf, map + offset, length);
3221                         kunmap_atomic(map);
3222                 } else
3223                         memset(buf, 0, length);
3224
3225                 addr += length;
3226                 buf += length;
3227                 copied += length;
3228                 count -= length;
3229         }
3230         return copied;
3231 }
3232
3233 /**
3234  * vread() - read vmalloc area in a safe way.
3235  * @buf:     buffer for reading data
3236  * @addr:    vm address.
3237  * @count:   number of bytes to be read.
3238  *
3239  * This function checks that addr is a valid vmalloc'ed area, and
3240  * copy data from that area to a given buffer. If the given memory range
3241  * of [addr...addr+count) includes some valid address, data is copied to
3242  * proper area of @buf. If there are memory holes, they'll be zero-filled.
3243  * IOREMAP area is treated as memory hole and no copy is done.
3244  *
3245  * If [addr...addr+count) doesn't includes any intersects with alive
3246  * vm_struct area, returns 0. @buf should be kernel's buffer.
3247  *
3248  * Note: In usual ops, vread() is never necessary because the caller
3249  * should know vmalloc() area is valid and can use memcpy().
3250  * This is for routines which have to access vmalloc area without
3251  * any information, as /proc/kcore.
3252  *
3253  * Return: number of bytes for which addr and buf should be increased
3254  * (same number as @count) or %0 if [addr...addr+count) doesn't
3255  * include any intersection with valid vmalloc area
3256  */
3257 long vread(char *buf, char *addr, unsigned long count)
3258 {
3259         struct vmap_area *va;
3260         struct vm_struct *vm;
3261         char *vaddr, *buf_start = buf;
3262         unsigned long buflen = count;
3263         unsigned long n;
3264
3265         /* Don't allow overflow */
3266         if ((unsigned long) addr + count < count)
3267                 count = -(unsigned long) addr;
3268
3269         spin_lock(&vmap_area_lock);
3270         va = __find_vmap_area((unsigned long)addr);
3271         if (!va)
3272                 goto finished;
3273         list_for_each_entry_from(va, &vmap_area_list, list) {
3274                 if (!count)
3275                         break;
3276
3277                 if (!va->vm)
3278                         continue;
3279
3280                 vm = va->vm;
3281                 vaddr = (char *) vm->addr;
3282                 if (addr >= vaddr + get_vm_area_size(vm))
3283                         continue;
3284                 while (addr < vaddr) {
3285                         if (count == 0)
3286                                 goto finished;
3287                         *buf = '\0';
3288                         buf++;
3289                         addr++;
3290                         count--;
3291                 }
3292                 n = vaddr + get_vm_area_size(vm) - addr;
3293                 if (n > count)
3294                         n = count;
3295                 if (!(vm->flags & VM_IOREMAP))
3296                         aligned_vread(buf, addr, n);
3297                 else /* IOREMAP area is treated as memory hole */
3298                         memset(buf, 0, n);
3299                 buf += n;
3300                 addr += n;
3301                 count -= n;
3302         }
3303 finished:
3304         spin_unlock(&vmap_area_lock);
3305
3306         if (buf == buf_start)
3307                 return 0;
3308         /* zero-fill memory holes */
3309         if (buf != buf_start + buflen)
3310                 memset(buf, 0, buflen - (buf - buf_start));
3311
3312         return buflen;
3313 }
3314
3315 /**
3316  * remap_vmalloc_range_partial - map vmalloc pages to userspace
3317  * @vma:                vma to cover
3318  * @uaddr:              target user address to start at
3319  * @kaddr:              virtual address of vmalloc kernel memory
3320  * @pgoff:              offset from @kaddr to start at
3321  * @size:               size of map area
3322  *
3323  * Returns:     0 for success, -Exxx on failure
3324  *
3325  * This function checks that @kaddr is a valid vmalloc'ed area,
3326  * and that it is big enough to cover the range starting at
3327  * @uaddr in @vma. Will return failure if that criteria isn't
3328  * met.
3329  *
3330  * Similar to remap_pfn_range() (see mm/memory.c)
3331  */
3332 int remap_vmalloc_range_partial(struct vm_area_struct *vma, unsigned long uaddr,
3333                                 void *kaddr, unsigned long pgoff,
3334                                 unsigned long size)
3335 {
3336         struct vm_struct *area;
3337         unsigned long off;
3338         unsigned long end_index;
3339
3340         if (check_shl_overflow(pgoff, PAGE_SHIFT, &off))
3341                 return -EINVAL;
3342
3343         size = PAGE_ALIGN(size);
3344
3345         if (!PAGE_ALIGNED(uaddr) || !PAGE_ALIGNED(kaddr))
3346                 return -EINVAL;
3347
3348         area = find_vm_area(kaddr);
3349         if (!area)
3350                 return -EINVAL;
3351
3352         if (!(area->flags & (VM_USERMAP | VM_DMA_COHERENT)))
3353                 return -EINVAL;
3354
3355         if (check_add_overflow(size, off, &end_index) ||
3356             end_index > get_vm_area_size(area))
3357                 return -EINVAL;
3358         kaddr += off;
3359
3360         do {
3361                 struct page *page = vmalloc_to_page(kaddr);
3362                 int ret;
3363
3364                 ret = vm_insert_page(vma, uaddr, page);
3365                 if (ret)
3366                         return ret;
3367
3368                 uaddr += PAGE_SIZE;
3369                 kaddr += PAGE_SIZE;
3370                 size -= PAGE_SIZE;
3371         } while (size > 0);
3372
3373         vma->vm_flags |= VM_DONTEXPAND | VM_DONTDUMP;
3374
3375         return 0;
3376 }
3377
3378 /**
3379  * remap_vmalloc_range - map vmalloc pages to userspace
3380  * @vma:                vma to cover (map full range of vma)
3381  * @addr:               vmalloc memory
3382  * @pgoff:              number of pages into addr before first page to map
3383  *
3384  * Returns:     0 for success, -Exxx on failure
3385  *
3386  * This function checks that addr is a valid vmalloc'ed area, and
3387  * that it is big enough to cover the vma. Will return failure if
3388  * that criteria isn't met.
3389  *
3390  * Similar to remap_pfn_range() (see mm/memory.c)
3391  */
3392 int remap_vmalloc_range(struct vm_area_struct *vma, void *addr,
3393                                                 unsigned long pgoff)
3394 {
3395         return remap_vmalloc_range_partial(vma, vma->vm_start,
3396                                            addr, pgoff,
3397                                            vma->vm_end - vma->vm_start);
3398 }
3399 EXPORT_SYMBOL(remap_vmalloc_range);
3400
3401 void free_vm_area(struct vm_struct *area)
3402 {
3403         struct vm_struct *ret;
3404         ret = remove_vm_area(area->addr);
3405         BUG_ON(ret != area);
3406         kfree(area);
3407 }
3408 EXPORT_SYMBOL_GPL(free_vm_area);
3409
3410 #ifdef CONFIG_SMP
3411 static struct vmap_area *node_to_va(struct rb_node *n)
3412 {
3413         return rb_entry_safe(n, struct vmap_area, rb_node);
3414 }
3415
3416 /**
3417  * pvm_find_va_enclose_addr - find the vmap_area @addr belongs to
3418  * @addr: target address
3419  *
3420  * Returns: vmap_area if it is found. If there is no such area
3421  *   the first highest(reverse order) vmap_area is returned
3422  *   i.e. va->va_start < addr && va->va_end < addr or NULL
3423  *   if there are no any areas before @addr.
3424  */
3425 static struct vmap_area *
3426 pvm_find_va_enclose_addr(unsigned long addr)
3427 {
3428         struct vmap_area *va, *tmp;
3429         struct rb_node *n;
3430
3431         n = free_vmap_area_root.rb_node;
3432         va = NULL;
3433
3434         while (n) {
3435                 tmp = rb_entry(n, struct vmap_area, rb_node);
3436                 if (tmp->va_start <= addr) {
3437                         va = tmp;
3438                         if (tmp->va_end >= addr)
3439                                 break;
3440
3441                         n = n->rb_right;
3442                 } else {
3443                         n = n->rb_left;
3444                 }
3445         }
3446
3447         return va;
3448 }
3449
3450 /**
3451  * pvm_determine_end_from_reverse - find the highest aligned address
3452  * of free block below VMALLOC_END
3453  * @va:
3454  *   in - the VA we start the search(reverse order);
3455  *   out - the VA with the highest aligned end address.
3456  * @align: alignment for required highest address
3457  *
3458  * Returns: determined end address within vmap_area
3459  */
3460 static unsigned long
3461 pvm_determine_end_from_reverse(struct vmap_area **va, unsigned long align)
3462 {
3463         unsigned long vmalloc_end = VMALLOC_END & ~(align - 1);
3464         unsigned long addr;
3465
3466         if (likely(*va)) {
3467                 list_for_each_entry_from_reverse((*va),
3468                                 &free_vmap_area_list, list) {
3469                         addr = min((*va)->va_end & ~(align - 1), vmalloc_end);
3470                         if ((*va)->va_start < addr)
3471                                 return addr;
3472                 }
3473         }
3474
3475         return 0;
3476 }
3477
3478 /**
3479  * pcpu_get_vm_areas - allocate vmalloc areas for percpu allocator
3480  * @offsets: array containing offset of each area
3481  * @sizes: array containing size of each area
3482  * @nr_vms: the number of areas to allocate
3483  * @align: alignment, all entries in @offsets and @sizes must be aligned to this
3484  *
3485  * Returns: kmalloc'd vm_struct pointer array pointing to allocated
3486  *          vm_structs on success, %NULL on failure
3487  *
3488  * Percpu allocator wants to use congruent vm areas so that it can
3489  * maintain the offsets among percpu areas.  This function allocates
3490  * congruent vmalloc areas for it with GFP_KERNEL.  These areas tend to
3491  * be scattered pretty far, distance between two areas easily going up
3492  * to gigabytes.  To avoid interacting with regular vmallocs, these
3493  * areas are allocated from top.
3494  *
3495  * Despite its complicated look, this allocator is rather simple. It
3496  * does everything top-down and scans free blocks from the end looking
3497  * for matching base. While scanning, if any of the areas do not fit the
3498  * base address is pulled down to fit the area. Scanning is repeated till
3499  * all the areas fit and then all necessary data structures are inserted
3500  * and the result is returned.
3501  */
3502 struct vm_struct **pcpu_get_vm_areas(const unsigned long *offsets,
3503                                      const size_t *sizes, int nr_vms,
3504                                      size_t align)
3505 {
3506         const unsigned long vmalloc_start = ALIGN(VMALLOC_START, align);
3507         const unsigned long vmalloc_end = VMALLOC_END & ~(align - 1);
3508         struct vmap_area **vas, *va;
3509         struct vm_struct **vms;
3510         int area, area2, last_area, term_area;
3511         unsigned long base, start, size, end, last_end, orig_start, orig_end;
3512         bool purged = false;
3513         enum fit_type type;
3514
3515         /* verify parameters and allocate data structures */
3516         BUG_ON(offset_in_page(align) || !is_power_of_2(align));
3517         for (last_area = 0, area = 0; area < nr_vms; area++) {
3518                 start = offsets[area];
3519                 end = start + sizes[area];
3520
3521                 /* is everything aligned properly? */
3522                 BUG_ON(!IS_ALIGNED(offsets[area], align));
3523                 BUG_ON(!IS_ALIGNED(sizes[area], align));
3524
3525                 /* detect the area with the highest address */
3526                 if (start > offsets[last_area])
3527                         last_area = area;
3528
3529                 for (area2 = area + 1; area2 < nr_vms; area2++) {
3530                         unsigned long start2 = offsets[area2];
3531                         unsigned long end2 = start2 + sizes[area2];
3532
3533                         BUG_ON(start2 < end && start < end2);
3534                 }
3535         }
3536         last_end = offsets[last_area] + sizes[last_area];
3537
3538         if (vmalloc_end - vmalloc_start < last_end) {
3539                 WARN_ON(true);
3540                 return NULL;
3541         }
3542
3543         vms = kcalloc(nr_vms, sizeof(vms[0]), GFP_KERNEL);
3544         vas = kcalloc(nr_vms, sizeof(vas[0]), GFP_KERNEL);
3545         if (!vas || !vms)
3546                 goto err_free2;
3547
3548         for (area = 0; area < nr_vms; area++) {
3549                 vas[area] = kmem_cache_zalloc(vmap_area_cachep, GFP_KERNEL);
3550                 vms[area] = kzalloc(sizeof(struct vm_struct), GFP_KERNEL);
3551                 if (!vas[area] || !vms[area])
3552                         goto err_free;
3553         }
3554 retry:
3555         spin_lock(&free_vmap_area_lock);
3556
3557         /* start scanning - we scan from the top, begin with the last area */
3558         area = term_area = last_area;
3559         start = offsets[area];
3560         end = start + sizes[area];
3561
3562         va = pvm_find_va_enclose_addr(vmalloc_end);
3563         base = pvm_determine_end_from_reverse(&va, align) - end;
3564
3565         while (true) {
3566                 /*
3567                  * base might have underflowed, add last_end before
3568                  * comparing.
3569                  */
3570                 if (base + last_end < vmalloc_start + last_end)
3571                         goto overflow;
3572
3573                 /*
3574                  * Fitting base has not been found.
3575                  */
3576                 if (va == NULL)
3577                         goto overflow;
3578
3579                 /*
3580                  * If required width exceeds current VA block, move
3581                  * base downwards and then recheck.
3582                  */
3583                 if (base + end > va->va_end) {
3584                         base = pvm_determine_end_from_reverse(&va, align) - end;
3585                         term_area = area;
3586                         continue;
3587                 }
3588
3589                 /*
3590                  * If this VA does not fit, move base downwards and recheck.
3591                  */
3592                 if (base + start < va->va_start) {
3593                         va = node_to_va(rb_prev(&va->rb_node));
3594                         base = pvm_determine_end_from_reverse(&va, align) - end;
3595                         term_area = area;
3596                         continue;
3597                 }
3598
3599                 /*
3600                  * This area fits, move on to the previous one.  If
3601                  * the previous one is the terminal one, we're done.
3602                  */
3603                 area = (area + nr_vms - 1) % nr_vms;
3604                 if (area == term_area)
3605                         break;
3606
3607                 start = offsets[area];
3608                 end = start + sizes[area];
3609                 va = pvm_find_va_enclose_addr(base + end);
3610         }
3611
3612         /* we've found a fitting base, insert all va's */
3613         for (area = 0; area < nr_vms; area++) {
3614                 int ret;
3615
3616                 start = base + offsets[area];
3617                 size = sizes[area];
3618
3619                 va = pvm_find_va_enclose_addr(start);
3620                 if (WARN_ON_ONCE(va == NULL))
3621                         /* It is a BUG(), but trigger recovery instead. */
3622                         goto recovery;
3623
3624                 type = classify_va_fit_type(va, start, size);
3625                 if (WARN_ON_ONCE(type == NOTHING_FIT))
3626                         /* It is a BUG(), but trigger recovery instead. */
3627                         goto recovery;
3628
3629                 ret = adjust_va_to_fit_type(va, start, size, type);
3630                 if (unlikely(ret))
3631                         goto recovery;
3632
3633                 /* Allocated area. */
3634                 va = vas[area];
3635                 va->va_start = start;
3636                 va->va_end = start + size;
3637         }
3638
3639         spin_unlock(&free_vmap_area_lock);
3640
3641         /* populate the kasan shadow space */
3642         for (area = 0; area < nr_vms; area++) {
3643                 if (kasan_populate_vmalloc(vas[area]->va_start, sizes[area]))
3644                         goto err_free_shadow;
3645
3646                 kasan_unpoison_vmalloc((void *)vas[area]->va_start,
3647                                        sizes[area]);
3648         }
3649
3650         /* insert all vm's */
3651         spin_lock(&vmap_area_lock);
3652         for (area = 0; area < nr_vms; area++) {
3653                 insert_vmap_area(vas[area], &vmap_area_root, &vmap_area_list);
3654
3655                 setup_vmalloc_vm_locked(vms[area], vas[area], VM_ALLOC,
3656                                  pcpu_get_vm_areas);
3657         }
3658         spin_unlock(&vmap_area_lock);
3659
3660         kfree(vas);
3661         return vms;
3662
3663 recovery:
3664         /*
3665          * Remove previously allocated areas. There is no
3666          * need in removing these areas from the busy tree,
3667          * because they are inserted only on the final step
3668          * and when pcpu_get_vm_areas() is success.
3669          */
3670         while (area--) {
3671                 orig_start = vas[area]->va_start;
3672                 orig_end = vas[area]->va_end;
3673                 va = merge_or_add_vmap_area_augment(vas[area], &free_vmap_area_root,
3674                                 &free_vmap_area_list);
3675                 if (va)
3676                         kasan_release_vmalloc(orig_start, orig_end,
3677                                 va->va_start, va->va_end);
3678                 vas[area] = NULL;
3679         }
3680
3681 overflow:
3682         spin_unlock(&free_vmap_area_lock);
3683         if (!purged) {
3684                 purge_vmap_area_lazy();
3685                 purged = true;
3686
3687                 /* Before "retry", check if we recover. */
3688                 for (area = 0; area < nr_vms; area++) {
3689                         if (vas[area])
3690                                 continue;
3691
3692                         vas[area] = kmem_cache_zalloc(
3693                                 vmap_area_cachep, GFP_KERNEL);
3694                         if (!vas[area])
3695                                 goto err_free;
3696                 }
3697
3698                 goto retry;
3699         }
3700
3701 err_free:
3702         for (area = 0; area < nr_vms; area++) {
3703                 if (vas[area])
3704                         kmem_cache_free(vmap_area_cachep, vas[area]);
3705
3706                 kfree(vms[area]);
3707         }
3708 err_free2:
3709         kfree(vas);
3710         kfree(vms);
3711         return NULL;
3712
3713 err_free_shadow:
3714         spin_lock(&free_vmap_area_lock);
3715         /*
3716          * We release all the vmalloc shadows, even the ones for regions that
3717          * hadn't been successfully added. This relies on kasan_release_vmalloc
3718          * being able to tolerate this case.
3719          */
3720         for (area = 0; area < nr_vms; area++) {
3721                 orig_start = vas[area]->va_start;
3722                 orig_end = vas[area]->va_end;
3723                 va = merge_or_add_vmap_area_augment(vas[area], &free_vmap_area_root,
3724                                 &free_vmap_area_list);
3725                 if (va)
3726                         kasan_release_vmalloc(orig_start, orig_end,
3727                                 va->va_start, va->va_end);
3728                 vas[area] = NULL;
3729                 kfree(vms[area]);
3730         }
3731         spin_unlock(&free_vmap_area_lock);
3732         kfree(vas);
3733         kfree(vms);
3734         return NULL;
3735 }
3736
3737 /**
3738  * pcpu_free_vm_areas - free vmalloc areas for percpu allocator
3739  * @vms: vm_struct pointer array returned by pcpu_get_vm_areas()
3740  * @nr_vms: the number of allocated areas
3741  *
3742  * Free vm_structs and the array allocated by pcpu_get_vm_areas().
3743  */
3744 void pcpu_free_vm_areas(struct vm_struct **vms, int nr_vms)
3745 {
3746         int i;
3747
3748         for (i = 0; i < nr_vms; i++)
3749                 free_vm_area(vms[i]);
3750         kfree(vms);
3751 }
3752 #endif  /* CONFIG_SMP */
3753
3754 #ifdef CONFIG_PRINTK
3755 bool vmalloc_dump_obj(void *object)
3756 {
3757         struct vm_struct *vm;
3758         void *objp = (void *)PAGE_ALIGN((unsigned long)object);
3759
3760         vm = find_vm_area(objp);
3761         if (!vm)
3762                 return false;
3763         pr_cont(" %u-page vmalloc region starting at %#lx allocated at %pS\n",
3764                 vm->nr_pages, (unsigned long)vm->addr, vm->caller);
3765         return true;
3766 }
3767 #endif
3768
3769 #ifdef CONFIG_PROC_FS
3770 static void *s_start(struct seq_file *m, loff_t *pos)
3771         __acquires(&vmap_purge_lock)
3772         __acquires(&vmap_area_lock)
3773 {
3774         mutex_lock(&vmap_purge_lock);
3775         spin_lock(&vmap_area_lock);
3776
3777         return seq_list_start(&vmap_area_list, *pos);
3778 }
3779
3780 static void *s_next(struct seq_file *m, void *p, loff_t *pos)
3781 {
3782         return seq_list_next(p, &vmap_area_list, pos);
3783 }
3784
3785 static void s_stop(struct seq_file *m, void *p)
3786         __releases(&vmap_area_lock)
3787         __releases(&vmap_purge_lock)
3788 {
3789         spin_unlock(&vmap_area_lock);
3790         mutex_unlock(&vmap_purge_lock);
3791 }
3792
3793 static void show_numa_info(struct seq_file *m, struct vm_struct *v)
3794 {
3795         if (IS_ENABLED(CONFIG_NUMA)) {
3796                 unsigned int nr, *counters = m->private;
3797
3798                 if (!counters)
3799                         return;
3800
3801                 if (v->flags & VM_UNINITIALIZED)
3802                         return;
3803                 /* Pair with smp_wmb() in clear_vm_uninitialized_flag() */
3804                 smp_rmb();
3805
3806                 memset(counters, 0, nr_node_ids * sizeof(unsigned int));
3807
3808                 for (nr = 0; nr < v->nr_pages; nr++)
3809                         counters[page_to_nid(v->pages[nr])]++;
3810
3811                 for_each_node_state(nr, N_HIGH_MEMORY)
3812                         if (counters[nr])
3813                                 seq_printf(m, " N%u=%u", nr, counters[nr]);
3814         }
3815 }
3816
3817 static void show_purge_info(struct seq_file *m)
3818 {
3819         struct vmap_area *va;
3820
3821         spin_lock(&purge_vmap_area_lock);
3822         list_for_each_entry(va, &purge_vmap_area_list, list) {
3823                 seq_printf(m, "0x%pK-0x%pK %7ld unpurged vm_area\n",
3824                         (void *)va->va_start, (void *)va->va_end,
3825                         va->va_end - va->va_start);
3826         }
3827         spin_unlock(&purge_vmap_area_lock);
3828 }
3829
3830 static int s_show(struct seq_file *m, void *p)
3831 {
3832         struct vmap_area *va;
3833         struct vm_struct *v;
3834
3835         va = list_entry(p, struct vmap_area, list);
3836
3837         /*
3838          * s_show can encounter race with remove_vm_area, !vm on behalf
3839          * of vmap area is being tear down or vm_map_ram allocation.
3840          */
3841         if (!va->vm) {
3842                 seq_printf(m, "0x%pK-0x%pK %7ld vm_map_ram\n",
3843                         (void *)va->va_start, (void *)va->va_end,
3844                         va->va_end - va->va_start);
3845
3846                 return 0;
3847         }
3848
3849         v = va->vm;
3850
3851         seq_printf(m, "0x%pK-0x%pK %7ld",
3852                 v->addr, v->addr + v->size, v->size);
3853
3854         if (v->caller)
3855                 seq_printf(m, " %pS", v->caller);
3856
3857         if (v->nr_pages)
3858                 seq_printf(m, " pages=%d", v->nr_pages);
3859
3860         if (v->phys_addr)
3861                 seq_printf(m, " phys=%pa", &v->phys_addr);
3862
3863         if (v->flags & VM_IOREMAP)
3864                 seq_puts(m, " ioremap");
3865
3866         if (v->flags & VM_ALLOC)
3867                 seq_puts(m, " vmalloc");
3868
3869         if (v->flags & VM_MAP)
3870                 seq_puts(m, " vmap");
3871
3872         if (v->flags & VM_USERMAP)
3873                 seq_puts(m, " user");
3874
3875         if (v->flags & VM_DMA_COHERENT)
3876                 seq_puts(m, " dma-coherent");
3877
3878         if (is_vmalloc_addr(v->pages))
3879                 seq_puts(m, " vpages");
3880
3881         show_numa_info(m, v);
3882         seq_putc(m, '\n');
3883
3884         /*
3885          * As a final step, dump "unpurged" areas.
3886          */
3887         if (list_is_last(&va->list, &vmap_area_list))
3888                 show_purge_info(m);
3889
3890         return 0;
3891 }
3892
3893 static const struct seq_operations vmalloc_op = {
3894         .start = s_start,
3895         .next = s_next,
3896         .stop = s_stop,
3897         .show = s_show,
3898 };
3899
3900 static int __init proc_vmalloc_init(void)
3901 {
3902         if (IS_ENABLED(CONFIG_NUMA))
3903                 proc_create_seq_private("vmallocinfo", 0400, NULL,
3904                                 &vmalloc_op,
3905                                 nr_node_ids * sizeof(unsigned int), NULL);
3906         else
3907                 proc_create_seq("vmallocinfo", 0400, NULL, &vmalloc_op);
3908         return 0;
3909 }
3910 module_init(proc_vmalloc_init);
3911
3912 #endif