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