Merge tag 'mm-hotfixes-stable-2025-07-11-16-16' of git://git.kernel.org/pub/scm/linux...
[linux-block.git] / mm / vmalloc.c
CommitLineData
457c8996 1// SPDX-License-Identifier: GPL-2.0-only
1da177e4 2/*
1da177e4
LT
3 * Copyright (C) 1993 Linus Torvalds
4 * Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
5 * SMP-safe vmalloc/vfree/ioremap, Tigran Aivazian <tigran@veritas.com>, May 2000
6 * Major rework to support vmap/vunmap, Christoph Hellwig, SGI, August 2002
930fc45a 7 * Numa awareness, Christoph Lameter, SGI, June 2005
d758ffe6 8 * Improving global KVA allocator, Uladzislau Rezki, Sony, May 2019
1da177e4
LT
9 */
10
db64fe02 11#include <linux/vmalloc.h>
1da177e4
LT
12#include <linux/mm.h>
13#include <linux/module.h>
14#include <linux/highmem.h>
c3edc401 15#include <linux/sched/signal.h>
1da177e4
LT
16#include <linux/slab.h>
17#include <linux/spinlock.h>
18#include <linux/interrupt.h>
5f6a6a9c 19#include <linux/proc_fs.h>
a10aa579 20#include <linux/seq_file.h>
868b104d 21#include <linux/set_memory.h>
3ac7fe5a 22#include <linux/debugobjects.h>
23016969 23#include <linux/kallsyms.h>
db64fe02 24#include <linux/list.h>
4da56b99 25#include <linux/notifier.h>
db64fe02 26#include <linux/rbtree.h>
0f14599c 27#include <linux/xarray.h>
5da96bdd 28#include <linux/io.h>
db64fe02 29#include <linux/rcupdate.h>
f0aa6617 30#include <linux/pfn.h>
89219d37 31#include <linux/kmemleak.h>
60063497 32#include <linux/atomic.h>
3b32123d 33#include <linux/compiler.h>
4e5aa1f4 34#include <linux/memcontrol.h>
32fcfd40 35#include <linux/llist.h>
4c91c07c 36#include <linux/uio.h>
0f616be1 37#include <linux/bitops.h>
68ad4a33 38#include <linux/rbtree_augmented.h>
bdebd6a2 39#include <linux/overflow.h>
c0eb315a 40#include <linux/pgtable.h>
f7ee1f13 41#include <linux/hugetlb.h>
451769eb 42#include <linux/sched/mm.h>
1da177e4 43#include <asm/tlbflush.h>
2dca6999 44#include <asm/shmparam.h>
21e516b9 45#include <linux/page_owner.h>
1da177e4 46
cf243da6
URS
47#define CREATE_TRACE_POINTS
48#include <trace/events/vmalloc.h>
49
dd56b046 50#include "internal.h"
2a681cfa 51#include "pgalloc-track.h"
dd56b046 52
82a70ce0
CH
53#ifdef CONFIG_HAVE_ARCH_HUGE_VMAP
54static unsigned int __ro_after_init ioremap_max_page_shift = BITS_PER_LONG - 1;
55
56static int __init set_nohugeiomap(char *str)
57{
58 ioremap_max_page_shift = PAGE_SHIFT;
59 return 0;
60}
61early_param("nohugeiomap", set_nohugeiomap);
62#else /* CONFIG_HAVE_ARCH_HUGE_VMAP */
63static const unsigned int ioremap_max_page_shift = PAGE_SHIFT;
64#endif /* CONFIG_HAVE_ARCH_HUGE_VMAP */
65
121e6f32
NP
66#ifdef CONFIG_HAVE_ARCH_HUGE_VMALLOC
67static bool __ro_after_init vmap_allow_huge = true;
68
69static int __init set_nohugevmalloc(char *str)
70{
71 vmap_allow_huge = false;
72 return 0;
73}
74early_param("nohugevmalloc", set_nohugevmalloc);
75#else /* CONFIG_HAVE_ARCH_HUGE_VMALLOC */
76static const bool vmap_allow_huge = false;
77#endif /* CONFIG_HAVE_ARCH_HUGE_VMALLOC */
78
186525bd
IM
79bool is_vmalloc_addr(const void *x)
80{
4aff1dc4 81 unsigned long addr = (unsigned long)kasan_reset_tag(x);
186525bd
IM
82
83 return addr >= VMALLOC_START && addr < VMALLOC_END;
84}
85EXPORT_SYMBOL(is_vmalloc_addr);
86
32fcfd40
AV
87struct vfree_deferred {
88 struct llist_head list;
89 struct work_struct wq;
90};
91static DEFINE_PER_CPU(struct vfree_deferred, vfree_deferred);
92
db64fe02 93/*** Page table manipulation functions ***/
5e9e3d77
NP
94static int vmap_pte_range(pmd_t *pmd, unsigned long addr, unsigned long end,
95 phys_addr_t phys_addr, pgprot_t prot,
f7ee1f13 96 unsigned int max_page_shift, pgtbl_mod_mask *mask)
5e9e3d77
NP
97{
98 pte_t *pte;
99 u64 pfn;
21e516b9 100 struct page *page;
f7ee1f13 101 unsigned long size = PAGE_SIZE;
5e9e3d77
NP
102
103 pfn = phys_addr >> PAGE_SHIFT;
104 pte = pte_alloc_kernel_track(pmd, addr, mask);
105 if (!pte)
106 return -ENOMEM;
44562c71
RR
107
108 arch_enter_lazy_mmu_mode();
109
5e9e3d77 110 do {
6963f008 111 if (unlikely(!pte_none(ptep_get(pte)))) {
21e516b9
HP
112 if (pfn_valid(pfn)) {
113 page = pfn_to_page(pfn);
114 dump_page(page, "remapping already mapped page");
115 }
116 BUG();
117 }
f7ee1f13
CL
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
f7ee1f13 124 entry = arch_make_huge_pte(entry, ilog2(size), 0);
935d4f0c 125 set_huge_pte_at(&init_mm, addr, pte, entry, size);
f7ee1f13
CL
126 pfn += PFN_DOWN(size);
127 continue;
128 }
129#endif
5e9e3d77
NP
130 set_pte_at(&init_mm, addr, pte, pfn_pte(pfn, prot));
131 pfn++;
f7ee1f13 132 } while (pte += PFN_DOWN(size), addr += size, addr != end);
44562c71
RR
133
134 arch_leave_lazy_mmu_mode();
5e9e3d77
NP
135 *mask |= PGTBL_PTE_MODIFIED;
136 return 0;
137}
138
139static 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
164static 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
f7ee1f13 183 if (vmap_pte_range(pmd, addr, next, phys_addr, prot, max_page_shift, mask))
5e9e3d77
NP
184 return -ENOMEM;
185 } while (pmd++, phys_addr += (next - addr), addr = next, addr != end);
186 return 0;
187}
188
189static 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
214static 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
240static 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
265static 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
5d87510d 291static int vmap_range_noflush(unsigned long addr, unsigned long end,
5e9e3d77
NP
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
5e9e3d77
NP
314 if (mask & ARCH_PAGE_TABLE_SYNC_MASK)
315 arch_sync_kernel_mappings(start, end);
316
317 return err;
318}
b221385b 319
d7bca919
AS
320int 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
82a70ce0
CH
334int ioremap_page_range(unsigned long addr, unsigned long end,
335 phys_addr_t phys_addr, pgprot_t prot)
5d87510d 336{
3e49a866 337 struct vm_struct *area;
5d87510d 338
3e49a866
AS
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 }
d7bca919 351 return vmap_page_range(addr, end, phys_addr, prot);
5d87510d
NP
352}
353
2ba3e694
JR
354static void vunmap_pte_range(pmd_t *pmd, unsigned long addr, unsigned long end,
355 pgtbl_mod_mask *mask)
1da177e4
LT
356{
357 pte_t *pte;
2fba1337
RR
358 pte_t ptent;
359 unsigned long size = PAGE_SIZE;
1da177e4
LT
360
361 pte = pte_offset_kernel(pmd, addr);
44562c71
RR
362 arch_enter_lazy_mmu_mode();
363
1da177e4 364 do {
2fba1337
RR
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);
1da177e4 378 WARN_ON(!pte_none(ptent) && !pte_present(ptent));
2fba1337 379 } while (pte += (size >> PAGE_SHIFT), addr += size, addr != end);
44562c71
RR
380
381 arch_leave_lazy_mmu_mode();
2ba3e694 382 *mask |= PGTBL_PTE_MODIFIED;
1da177e4
LT
383}
384
2ba3e694
JR
385static void vunmap_pmd_range(pud_t *pud, unsigned long addr, unsigned long end,
386 pgtbl_mod_mask *mask)
1da177e4
LT
387{
388 pmd_t *pmd;
389 unsigned long next;
2ba3e694 390 int cleared;
1da177e4
LT
391
392 pmd = pmd_offset(pud, addr);
393 do {
394 next = pmd_addr_end(addr, end);
2ba3e694
JR
395
396 cleared = pmd_clear_huge(pmd);
397 if (cleared || pmd_bad(*pmd))
398 *mask |= PGTBL_PMD_MODIFIED;
399
61ef8dda
RR
400 if (cleared) {
401 WARN_ON(next - addr < PMD_SIZE);
b9820d8f 402 continue;
61ef8dda 403 }
1da177e4
LT
404 if (pmd_none_or_clear_bad(pmd))
405 continue;
2ba3e694 406 vunmap_pte_range(pmd, addr, next, mask);
e47110e9
AK
407
408 cond_resched();
1da177e4
LT
409 } while (pmd++, addr = next, addr != end);
410}
411
2ba3e694
JR
412static void vunmap_pud_range(p4d_t *p4d, unsigned long addr, unsigned long end,
413 pgtbl_mod_mask *mask)
1da177e4
LT
414{
415 pud_t *pud;
416 unsigned long next;
2ba3e694 417 int cleared;
1da177e4 418
c2febafc 419 pud = pud_offset(p4d, addr);
1da177e4
LT
420 do {
421 next = pud_addr_end(addr, end);
2ba3e694
JR
422
423 cleared = pud_clear_huge(pud);
424 if (cleared || pud_bad(*pud))
425 *mask |= PGTBL_PUD_MODIFIED;
426
61ef8dda
RR
427 if (cleared) {
428 WARN_ON(next - addr < PUD_SIZE);
b9820d8f 429 continue;
61ef8dda 430 }
1da177e4
LT
431 if (pud_none_or_clear_bad(pud))
432 continue;
2ba3e694 433 vunmap_pmd_range(pud, addr, next, mask);
1da177e4
LT
434 } while (pud++, addr = next, addr != end);
435}
436
2ba3e694
JR
437static void vunmap_p4d_range(pgd_t *pgd, unsigned long addr, unsigned long end,
438 pgtbl_mod_mask *mask)
c2febafc
KS
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);
2ba3e694 446
c8db8c26
L
447 p4d_clear_huge(p4d);
448 if (p4d_bad(*p4d))
2ba3e694
JR
449 *mask |= PGTBL_P4D_MODIFIED;
450
c2febafc
KS
451 if (p4d_none_or_clear_bad(p4d))
452 continue;
2ba3e694 453 vunmap_pud_range(p4d, addr, next, mask);
c2febafc
KS
454 } while (p4d++, addr = next, addr != end);
455}
456
4ad0ae8c
NP
457/*
458 * vunmap_range_noflush is similar to vunmap_range, but does not
459 * flush caches or TLBs.
b521c43f 460 *
4ad0ae8c
NP
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).
b521c43f 466 *
4ad0ae8c 467 * This is an internal function only. Do not use outside mm/.
b521c43f 468 */
b073d7f8 469void __vunmap_range_noflush(unsigned long start, unsigned long end)
1da177e4 470{
1da177e4 471 unsigned long next;
b521c43f 472 pgd_t *pgd;
2ba3e694
JR
473 unsigned long addr = start;
474 pgtbl_mod_mask mask = 0;
1da177e4
LT
475
476 BUG_ON(addr >= end);
477 pgd = pgd_offset_k(addr);
1da177e4
LT
478 do {
479 next = pgd_addr_end(addr, end);
2ba3e694
JR
480 if (pgd_bad(*pgd))
481 mask |= PGTBL_PGD_MODIFIED;
1da177e4
LT
482 if (pgd_none_or_clear_bad(pgd))
483 continue;
2ba3e694 484 vunmap_p4d_range(pgd, addr, next, &mask);
1da177e4 485 } while (pgd++, addr = next, addr != end);
2ba3e694
JR
486
487 if (mask & ARCH_PAGE_TABLE_SYNC_MASK)
488 arch_sync_kernel_mappings(start, end);
1da177e4
LT
489}
490
b073d7f8
AP
491void 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
4ad0ae8c
NP
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 */
506void 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
0a264884 513static int vmap_pages_pte_range(pmd_t *pmd, unsigned long addr,
2ba3e694
JR
514 unsigned long end, pgprot_t prot, struct page **pages, int *nr,
515 pgtbl_mod_mask *mask)
1da177e4 516{
fea18c68 517 int err = 0;
1da177e4
LT
518 pte_t *pte;
519
db64fe02
NP
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
2ba3e694 525 pte = pte_alloc_kernel_track(pmd, addr, mask);
1da177e4
LT
526 if (!pte)
527 return -ENOMEM;
44562c71
RR
528
529 arch_enter_lazy_mmu_mode();
530
1da177e4 531 do {
db64fe02
NP
532 struct page *page = pages[*nr];
533
fea18c68
AG
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 }
4fcdcc12 546
1da177e4 547 set_pte_at(&init_mm, addr, pte, mk_pte(page, prot));
db64fe02 548 (*nr)++;
1da177e4 549 } while (pte++, addr += PAGE_SIZE, addr != end);
44562c71
RR
550
551 arch_leave_lazy_mmu_mode();
2ba3e694 552 *mask |= PGTBL_PTE_MODIFIED;
fea18c68
AG
553
554 return err;
1da177e4
LT
555}
556
0a264884 557static int vmap_pages_pmd_range(pud_t *pud, unsigned long addr,
2ba3e694
JR
558 unsigned long end, pgprot_t prot, struct page **pages, int *nr,
559 pgtbl_mod_mask *mask)
1da177e4
LT
560{
561 pmd_t *pmd;
562 unsigned long next;
563
2ba3e694 564 pmd = pmd_alloc_track(&init_mm, pud, addr, mask);
1da177e4
LT
565 if (!pmd)
566 return -ENOMEM;
567 do {
568 next = pmd_addr_end(addr, end);
0a264884 569 if (vmap_pages_pte_range(pmd, addr, next, prot, pages, nr, mask))
1da177e4
LT
570 return -ENOMEM;
571 } while (pmd++, addr = next, addr != end);
572 return 0;
573}
574
0a264884 575static int vmap_pages_pud_range(p4d_t *p4d, unsigned long addr,
2ba3e694
JR
576 unsigned long end, pgprot_t prot, struct page **pages, int *nr,
577 pgtbl_mod_mask *mask)
1da177e4
LT
578{
579 pud_t *pud;
580 unsigned long next;
581
2ba3e694 582 pud = pud_alloc_track(&init_mm, p4d, addr, mask);
1da177e4
LT
583 if (!pud)
584 return -ENOMEM;
585 do {
586 next = pud_addr_end(addr, end);
0a264884 587 if (vmap_pages_pmd_range(pud, addr, next, prot, pages, nr, mask))
1da177e4
LT
588 return -ENOMEM;
589 } while (pud++, addr = next, addr != end);
590 return 0;
591}
592
0a264884 593static int vmap_pages_p4d_range(pgd_t *pgd, unsigned long addr,
2ba3e694
JR
594 unsigned long end, pgprot_t prot, struct page **pages, int *nr,
595 pgtbl_mod_mask *mask)
c2febafc
KS
596{
597 p4d_t *p4d;
598 unsigned long next;
599
2ba3e694 600 p4d = p4d_alloc_track(&init_mm, pgd, addr, mask);
c2febafc
KS
601 if (!p4d)
602 return -ENOMEM;
603 do {
604 next = p4d_addr_end(addr, end);
0a264884 605 if (vmap_pages_pud_range(p4d, addr, next, prot, pages, nr, mask))
c2febafc
KS
606 return -ENOMEM;
607 } while (p4d++, addr = next, addr != end);
608 return 0;
609}
610
121e6f32
NP
611static int vmap_small_pages_range_noflush(unsigned long addr, unsigned long end,
612 pgprot_t prot, struct page **pages)
1da177e4 613{
2ba3e694 614 unsigned long start = addr;
b521c43f 615 pgd_t *pgd;
121e6f32 616 unsigned long next;
db64fe02
NP
617 int err = 0;
618 int nr = 0;
2ba3e694 619 pgtbl_mod_mask mask = 0;
1da177e4
LT
620
621 BUG_ON(addr >= end);
622 pgd = pgd_offset_k(addr);
1da177e4
LT
623 do {
624 next = pgd_addr_end(addr, end);
2ba3e694
JR
625 if (pgd_bad(*pgd))
626 mask |= PGTBL_PGD_MODIFIED;
0a264884 627 err = vmap_pages_p4d_range(pgd, addr, next, prot, pages, &nr, &mask);
1da177e4 628 if (err)
3685024e 629 break;
1da177e4 630 } while (pgd++, addr = next, addr != end);
db64fe02 631
2ba3e694
JR
632 if (mask & ARCH_PAGE_TABLE_SYNC_MASK)
633 arch_sync_kernel_mappings(start, end);
634
3685024e 635 return err;
1da177e4
LT
636}
637
b67177ec
NP
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 */
b073d7f8 647int __vmap_pages_range_noflush(unsigned long addr, unsigned long end,
121e6f32
NP
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),
08262ac5 662 page_to_phys(pages[i]), prot,
121e6f32
NP
663 page_shift);
664 if (err)
665 return err;
666
667 addr += 1UL << page_shift;
668 }
669
670 return 0;
671}
b073d7f8
AP
672
673int vmap_pages_range_noflush(unsigned long addr, unsigned long end,
674 pgprot_t prot, struct page **pages, unsigned int page_shift)
675{
47ebd031
AP
676 int ret = kmsan_vmap_pages_range_noflush(addr, end, prot, pages,
677 page_shift);
678
679 if (ret)
680 return ret;
b073d7f8
AP
681 return __vmap_pages_range_noflush(addr, end, prot, pages, page_shift);
682}
121e6f32 683
121e6f32 684/**
b67177ec 685 * vmap_pages_range - map pages to a kernel virtual address
121e6f32 686 * @addr: start of the VM area to map
b67177ec 687 * @end: end of the VM area to map (non-inclusive)
121e6f32 688 * @prot: page protection flags to use
b67177ec
NP
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.
121e6f32
NP
692 *
693 * RETURNS:
694 * 0 on success, -errno on failure.
695 */
0f9b6856 696int vmap_pages_range(unsigned long addr, unsigned long end,
b67177ec 697 pgprot_t prot, struct page **pages, unsigned int page_shift)
8fc48985 698{
b67177ec 699 int err;
8fc48985 700
b67177ec
NP
701 err = vmap_pages_range_noflush(addr, end, prot, pages, page_shift);
702 flush_cache_vmap(addr, end);
703 return err;
8fc48985
TH
704}
705
e6f79822
AS
706static 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 */
731int 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 */
749void 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
81ac3ad9 758int is_vmalloc_or_module_addr(const void *x)
73bdf0a6
LT
759{
760 /*
ab4f2ee1 761 * ARM, x86-64 and sparc64 put modules in a special place,
73bdf0a6
LT
762 * and fall back on vmalloc() if that fails. Others
763 * just put it in the vmalloc space.
764 */
0105eaab 765#if defined(CONFIG_EXECMEM) && defined(MODULES_VADDR)
4aff1dc4 766 unsigned long addr = (unsigned long)kasan_reset_tag(x);
73bdf0a6
LT
767 if (addr >= MODULES_VADDR && addr < MODULES_END)
768 return 1;
769#endif
770 return is_vmalloc_addr(x);
771}
01858469 772EXPORT_SYMBOL_GPL(is_vmalloc_or_module_addr);
73bdf0a6 773
48667e7a 774/*
c0eb315a
NP
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.
48667e7a 778 */
add688fb 779struct page *vmalloc_to_page(const void *vmalloc_addr)
48667e7a
CL
780{
781 unsigned long addr = (unsigned long) vmalloc_addr;
add688fb 782 struct page *page = NULL;
48667e7a 783 pgd_t *pgd = pgd_offset_k(addr);
c2febafc
KS
784 p4d_t *p4d;
785 pud_t *pud;
786 pmd_t *pmd;
787 pte_t *ptep, pte;
48667e7a 788
7aa413de
IM
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 */
73bdf0a6 793 VIRTUAL_BUG_ON(!is_vmalloc_or_module_addr(vmalloc_addr));
59ea7463 794
c2febafc
KS
795 if (pgd_none(*pgd))
796 return NULL;
c0eb315a
NP
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
c2febafc
KS
802 p4d = p4d_offset(pgd, addr);
803 if (p4d_none(*p4d))
804 return NULL;
c0eb315a
NP
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;
029c54b0 809
c0eb315a
NP
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)))
c2febafc 816 return NULL;
c0eb315a 817
c2febafc 818 pmd = pmd_offset(pud, addr);
c0eb315a
NP
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)))
c2febafc
KS
824 return NULL;
825
0d1c81ed 826 ptep = pte_offset_kernel(pmd, addr);
c33c7948 827 pte = ptep_get(ptep);
c2febafc
KS
828 if (pte_present(pte))
829 page = pte_page(pte);
c0eb315a 830
add688fb 831 return page;
48667e7a 832}
add688fb 833EXPORT_SYMBOL(vmalloc_to_page);
48667e7a
CL
834
835/*
add688fb 836 * Map a vmalloc()-space virtual address to the physical page frame number.
48667e7a 837 */
add688fb 838unsigned long vmalloc_to_pfn(const void *vmalloc_addr)
48667e7a 839{
add688fb 840 return page_to_pfn(vmalloc_to_page(vmalloc_addr));
48667e7a 841}
add688fb 842EXPORT_SYMBOL(vmalloc_to_pfn);
48667e7a 843
db64fe02
NP
844
845/*** Global kva allocator ***/
846
bb850f4d 847#define DEBUG_AUGMENT_PROPAGATE_CHECK 0
a6cf4e0f 848#define DEBUG_AUGMENT_LOWEST_MATCH_CHECK 0
bb850f4d 849
db64fe02 850
e36176be 851static DEFINE_SPINLOCK(free_vmap_area_lock);
68ad4a33 852static bool vmap_initialized __read_mostly;
89699605 853
68ad4a33
URS
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 */
860static 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 */
866static 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 */
878static struct rb_root free_vmap_area_root = RB_ROOT;
879
82dd23e8
URS
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 */
885static DEFINE_PER_CPU(struct vmap_area *, ne_fit_preload_node);
886
d0936029 887/*
15e02a39
URS
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.
d0936029
URS
892 */
893struct rb_list {
894 struct rb_root root;
895 struct list_head head;
896 spinlock_t lock;
897};
898
15e02a39
URS
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
72210662
URS
906struct vmap_pool {
907 struct list_head head;
908 unsigned long len;
909};
910
911/*
15e02a39
URS
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.
72210662 915 */
d0936029 916static struct vmap_node {
72210662
URS
917 /* Simple size segregated storage. */
918 struct vmap_pool pool[MAX_VA_SIZE_PAGES];
919 spinlock_t pool_lock;
920 bool skip_populate;
921
d0936029
URS
922 /* Bookkeeping data of this node. */
923 struct rb_list busy;
282631cb
URS
924 struct rb_list lazy;
925
926 /*
927 * Ready-to-free areas.
928 */
929 struct list_head purge_list;
72210662
URS
930 struct work_struct purge_work;
931 unsigned long nr_purged;
d0936029
URS
932} single;
933
15e02a39
URS
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 */
d0936029
URS
939static struct vmap_node *vmap_nodes = &single;
940static __read_mostly unsigned int nr_vmap_nodes = 1;
941static __read_mostly unsigned int vmap_zone_size = 1;
942
43182550
URS
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
d0936029
URS
948static inline unsigned int
949addr_to_node_id(unsigned long addr)
950{
951 return (addr / vmap_zone_size) % nr_vmap_nodes;
952}
953
954static inline struct vmap_node *
955addr_to_node(unsigned long addr)
956{
957 return &vmap_nodes[addr_to_node_id(addr)];
958}
959
72210662
URS
960static inline struct vmap_node *
961id_to_node(unsigned int id)
962{
963 return &vmap_nodes[id % nr_vmap_nodes];
964}
965
24c76f37
URS
966static inline unsigned int
967node_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
72210662
URS
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 */
986static unsigned int
987encode_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 */
1003static unsigned int
1004decode_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
1019static bool
1020is_vn_id_valid(unsigned int node_id)
1021{
1022 if (node_id < nr_vmap_nodes)
1023 return true;
1024
1025 return false;
1026}
1027
68ad4a33
URS
1028static __always_inline unsigned long
1029va_size(struct vmap_area *va)
1030{
1031 return (va->va_end - va->va_start);
1032}
1033
1034static __always_inline unsigned long
1035get_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}
89699605 1042
315cc066
ML
1043RB_DECLARE_CALLBACKS_MAX(static, free_vmap_area_rb_augment_cb,
1044 struct vmap_area, rb_node, unsigned long, subtree_max_size, va_size)
68ad4a33 1045
77e50af0 1046static void reclaim_and_purge_vmap_areas(void);
68ad4a33 1047static BLOCKING_NOTIFIER_HEAD(vmap_notify_list);
690467c8
URS
1048static void drain_vmap_area_work(struct work_struct *work);
1049static DECLARE_WORK(drain_vmap_work, drain_vmap_area_work);
db64fe02 1050
d0966120
URS
1051static __cacheline_aligned_in_smp atomic_long_t nr_vmalloc_pages;
1052static __cacheline_aligned_in_smp atomic_long_t vmap_lazy_nr;
97105f0a
RG
1053
1054unsigned long vmalloc_nr_pages(void)
1055{
1056 return atomic_long_read(&nr_vmalloc_pages);
1057}
1058
fc2c2269
URS
1059static 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
153090f2 1080/* Look up the first VA which satisfies addr < va_end, NULL if none. */
d0936029 1081static struct vmap_area *
53becf32 1082__find_vmap_area_exceed_addr(unsigned long addr, struct rb_root *root)
f181234a
CW
1083{
1084 struct vmap_area *va = NULL;
d0936029 1085 struct rb_node *n = root->rb_node;
f181234a 1086
4aff1dc4
AK
1087 addr = (unsigned long)kasan_reset_tag((void *)addr);
1088
f181234a
CW
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
53becf32
URS
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 */
1113static struct vmap_node *
1114find_vmap_area_exceed_addr_lock(unsigned long addr, struct vmap_area **va)
1115{
fc2c2269
URS
1116 unsigned long va_start_lowest;
1117 struct vmap_node *vn;
53becf32 1118
fc2c2269 1119repeat:
ce906d76 1120 va_start_lowest = 0;
53becf32 1121
ce906d76 1122 for_each_vmap_node(vn) {
53becf32 1123 spin_lock(&vn->busy.lock);
fc2c2269
URS
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;
53becf32
URS
1129 spin_unlock(&vn->busy.lock);
1130 }
1131
fc2c2269
URS
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);
53becf32 1139
fc2c2269
URS
1140 spin_lock(&vn->busy.lock);
1141 *va = __find_vmap_area(va_start_lowest, &vn->busy.root);
db64fe02 1142
fc2c2269
URS
1143 if (*va)
1144 return vn;
4aff1dc4 1145
fc2c2269
URS
1146 spin_unlock(&vn->busy.lock);
1147 goto repeat;
db64fe02
NP
1148 }
1149
1150 return NULL;
1151}
1152
68ad4a33
URS
1153/*
1154 * This function returns back addresses of parent node
1155 * and its left or right link for further processing.
9c801f61
URS
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.
68ad4a33
URS
1160 */
1161static __always_inline struct rb_node **
1162find_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 }
db64fe02 1178
68ad4a33
URS
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);
db64fe02 1186
68ad4a33
URS
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 */
753df96b 1192 if (va->va_end <= tmp_va->va_start)
68ad4a33 1193 link = &(*link)->rb_left;
753df96b 1194 else if (va->va_start >= tmp_va->va_end)
68ad4a33 1195 link = &(*link)->rb_right;
9c801f61
URS
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 }
68ad4a33
URS
1202 } while (*link);
1203
1204 *parent = &tmp_va->rb_node;
1205 return link;
1206}
1207
1208static __always_inline struct list_head *
1209get_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
1226static __always_inline void
8eb510db
URS
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)
68ad4a33
URS
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;
db64fe02
NP
1239 }
1240
68ad4a33
URS
1241 /* Insert to the rb-tree */
1242 rb_link_node(&va->rb_node, parent, link);
8eb510db 1243 if (augment) {
68ad4a33
URS
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().
153090f2 1248 * It is because we populate the tree from the bottom
68ad4a33
URS
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 }
db64fe02 1261
68ad4a33
URS
1262 /* Address-sort this list */
1263 list_add(&va->list, head);
db64fe02
NP
1264}
1265
68ad4a33 1266static __always_inline void
8eb510db
URS
1267link_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
1274static __always_inline void
1275link_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
1282static __always_inline void
1283__unlink_va(struct vmap_area *va, struct rb_root *root, bool augment)
68ad4a33 1284{
460e42d1
URS
1285 if (WARN_ON(RB_EMPTY_NODE(&va->rb_node)))
1286 return;
db64fe02 1287
8eb510db 1288 if (augment)
460e42d1
URS
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
5d7a7c54 1294 list_del_init(&va->list);
460e42d1 1295 RB_CLEAR_NODE(&va->rb_node);
68ad4a33
URS
1296}
1297
8eb510db
URS
1298static __always_inline void
1299unlink_va(struct vmap_area *va, struct rb_root *root)
1300{
1301 __unlink_va(va, root, false);
1302}
1303
1304static __always_inline void
1305unlink_va_augment(struct vmap_area *va, struct rb_root *root)
1306{
1307 __unlink_va(va, root, true);
1308}
1309
bb850f4d 1310#if DEBUG_AUGMENT_PROPAGATE_CHECK
c3385e84
JC
1311/*
1312 * Gets called when remove the node and rotate.
1313 */
1314static __always_inline unsigned long
1315compute_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
bb850f4d 1322static void
da27c9ed 1323augment_tree_propagate_check(void)
bb850f4d
URS
1324{
1325 struct vmap_area *va;
da27c9ed 1326 unsigned long computed_size;
bb850f4d 1327
da27c9ed
URS
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);
bb850f4d 1333 }
bb850f4d
URS
1334}
1335#endif
1336
68ad4a33
URS
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 */
1364static __always_inline void
1365augment_tree_propagate_from(struct vmap_area *va)
1366{
15ae144f
URS
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);
bb850f4d
URS
1373
1374#if DEBUG_AUGMENT_PROPAGATE_CHECK
da27c9ed 1375 augment_tree_propagate_check();
bb850f4d 1376#endif
68ad4a33
URS
1377}
1378
1379static void
1380insert_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);
9c801f61
URS
1387 if (link)
1388 link_va(va, root, parent, link, head);
68ad4a33
URS
1389}
1390
1391static void
1392insert_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
9c801f61 1404 if (link) {
8eb510db 1405 link_va_augment(va, root, parent, link, head);
9c801f61
URS
1406 augment_tree_propagate_from(va);
1407 }
68ad4a33
URS
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.
9c801f61
URS
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.
68ad4a33 1420 */
3c5c3cfb 1421static __always_inline struct vmap_area *
8eb510db
URS
1422__merge_or_add_vmap_area(struct vmap_area *va,
1423 struct rb_root *root, struct list_head *head, bool augment)
68ad4a33
URS
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);
9c801f61
URS
1436 if (!link)
1437 return NULL;
68ad4a33
URS
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
68ad4a33
URS
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) {
5dd78640
URS
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 */
54f63d9d 1484 if (merged)
8eb510db 1485 __unlink_va(va, root, augment);
68ad4a33 1486
5dd78640
URS
1487 sibling->va_end = va->va_end;
1488
68ad4a33
URS
1489 /* Free vmap_area object. */
1490 kmem_cache_free(vmap_area_cachep, va);
3c5c3cfb
DA
1491
1492 /* Point to the new merged area. */
1493 va = sibling;
1494 merged = true;
68ad4a33
URS
1495 }
1496 }
1497
1498insert:
5dd78640 1499 if (!merged)
8eb510db 1500 __link_va(va, root, parent, link, head, augment);
3c5c3cfb 1501
96e2db45
URS
1502 return va;
1503}
1504
8eb510db
URS
1505static __always_inline struct vmap_area *
1506merge_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
96e2db45
URS
1512static __always_inline struct vmap_area *
1513merge_or_add_vmap_area_augment(struct vmap_area *va,
1514 struct rb_root *root, struct list_head *head)
1515{
8eb510db 1516 va = __merge_or_add_vmap_area(va, root, head, true);
96e2db45
URS
1517 if (va)
1518 augment_tree_propagate_from(va);
1519
3c5c3cfb 1520 return va;
68ad4a33
URS
1521}
1522
1523static __always_inline bool
1524is_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
9333fe98
UR
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.
68ad4a33
URS
1548 */
1549static __always_inline struct vmap_area *
f9863be4
URS
1550find_vmap_lowest_match(struct rb_root *root, unsigned long size,
1551 unsigned long align, unsigned long vstart, bool adjust_search_size)
68ad4a33
URS
1552{
1553 struct vmap_area *va;
1554 struct rb_node *node;
9333fe98 1555 unsigned long length;
68ad4a33
URS
1556
1557 /* Start from the root. */
f9863be4 1558 node = root->rb_node;
68ad4a33 1559
9333fe98
UR
1560 /* Adjust the search size for alignment overhead. */
1561 length = adjust_search_size ? size + align - 1 : size;
1562
68ad4a33
URS
1563 while (node) {
1564 va = rb_entry(node, struct vmap_area, rb_node);
1565
9333fe98 1566 if (get_subtree_max_size(node->rb_left) >= length &&
68ad4a33
URS
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
9333fe98 1576 * equal or bigger to the requested search length.
68ad4a33 1577 */
9333fe98 1578 if (get_subtree_max_size(node->rb_right) >= length) {
68ad4a33
URS
1579 node = node->rb_right;
1580 continue;
1581 }
1582
1583 /*
3806b041 1584 * OK. We roll back and find the first right sub-tree,
68ad4a33 1585 * that will satisfy the search criteria. It can happen
9f531973
URS
1586 * due to "vstart" restriction or an alignment overhead
1587 * that is bigger then PAGE_SIZE.
68ad4a33
URS
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
9333fe98 1594 if (get_subtree_max_size(node->rb_right) >= length &&
68ad4a33 1595 vstart <= va->va_start) {
9f531973
URS
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;
68ad4a33
URS
1603 node = node->rb_right;
1604 break;
1605 }
1606 }
1607 }
1608 }
1609
1610 return NULL;
1611}
1612
a6cf4e0f
URS
1613#if DEBUG_AUGMENT_LOWEST_MATCH_CHECK
1614#include <linux/random.h>
1615
1616static struct vmap_area *
bd1264c3 1617find_vmap_lowest_linear_match(struct list_head *head, unsigned long size,
a6cf4e0f
URS
1618 unsigned long align, unsigned long vstart)
1619{
1620 struct vmap_area *va;
1621
bd1264c3 1622 list_for_each_entry(va, head, list) {
a6cf4e0f
URS
1623 if (!is_within_this_va(va, size, align, vstart))
1624 continue;
1625
1626 return va;
1627 }
1628
1629 return NULL;
1630}
1631
1632static void
bd1264c3
SL
1633find_vmap_lowest_match_check(struct rb_root *root, struct list_head *head,
1634 unsigned long size, unsigned long align)
a6cf4e0f
URS
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
bd1264c3
SL
1643 va_1 = find_vmap_lowest_match(root, size, align, vstart, false);
1644 va_2 = find_vmap_lowest_linear_match(head, size, align, vstart);
a6cf4e0f
URS
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
68ad4a33
URS
1652enum 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
1660static __always_inline enum fit_type
1661classify_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
1686static __always_inline int
5b75b8e1
URS
1687va_clip(struct rb_root *root, struct list_head *head,
1688 struct vmap_area *va, unsigned long nva_start_addr,
1689 unsigned long size)
68ad4a33 1690{
2c929233 1691 struct vmap_area *lva = NULL;
1b23ff80 1692 enum fit_type type = classify_va_fit_type(va, nva_start_addr, size);
68ad4a33
URS
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 */
f9863be4 1702 unlink_va_augment(va, root);
68ad4a33
URS
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 */
82dd23e8
URS
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.
060650a2
URS
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.
82dd23e8
URS
1756 */
1757 lva = kmem_cache_alloc(vmap_area_cachep, GFP_NOWAIT);
1758 if (!lva)
b25f97d0 1759 return -ENOMEM;
82dd23e8 1760 }
68ad4a33
URS
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 {
b25f97d0 1773 return -EINVAL;
68ad4a33
URS
1774 }
1775
1776 if (type != FL_FIT_TYPE) {
1777 augment_tree_propagate_from(va);
1778
2c929233 1779 if (lva) /* type == NE_FIT_TYPE */
f9863be4 1780 insert_vmap_area_augment(lva, &va->rb_node, root, head);
68ad4a33
URS
1781 }
1782
1783 return 0;
1784}
1785
38f6b9af
URS
1786static unsigned long
1787va_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)
b25f97d0 1802 return -ERANGE;
38f6b9af
URS
1803
1804 /* Update the free vmap_area. */
5b75b8e1 1805 ret = va_clip(root, head, va, nva_start_addr, size);
38f6b9af 1806 if (WARN_ON_ONCE(ret))
b25f97d0 1807 return ret;
38f6b9af
URS
1808
1809 return nva_start_addr;
1810}
1811
68ad4a33
URS
1812/*
1813 * Returns a start address of the newly allocated area, if success.
b25f97d0 1814 * Otherwise an error value is returned that indicates failure.
68ad4a33
URS
1815 */
1816static __always_inline unsigned long
f9863be4
URS
1817__alloc_vmap_area(struct rb_root *root, struct list_head *head,
1818 unsigned long size, unsigned long align,
cacca6ba 1819 unsigned long vstart, unsigned long vend)
68ad4a33 1820{
9333fe98 1821 bool adjust_search_size = true;
68ad4a33
URS
1822 unsigned long nva_start_addr;
1823 struct vmap_area *va;
68ad4a33 1824
9333fe98
UR
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
f9863be4 1837 va = find_vmap_lowest_match(root, size, align, vstart, adjust_search_size);
68ad4a33 1838 if (unlikely(!va))
b25f97d0 1839 return -ENOENT;
68ad4a33 1840
38f6b9af 1841 nva_start_addr = va_alloc(va, root, head, size, align, vstart, vend);
68ad4a33 1842
a6cf4e0f 1843#if DEBUG_AUGMENT_LOWEST_MATCH_CHECK
b25f97d0
BH
1844 if (!IS_ERR_VALUE(nva_start_addr))
1845 find_vmap_lowest_match_check(root, head, size, align);
a6cf4e0f
URS
1846#endif
1847
68ad4a33
URS
1848 return nva_start_addr;
1849}
4da56b99 1850
d98c9e83
AR
1851/*
1852 * Free a region of KVA allocated by alloc_vmap_area
1853 */
1854static void free_vmap_area(struct vmap_area *va)
1855{
d0936029
URS
1856 struct vmap_node *vn = addr_to_node(va->va_start);
1857
d98c9e83
AR
1858 /*
1859 * Remove from the busy tree/list.
1860 */
d0936029
URS
1861 spin_lock(&vn->busy.lock);
1862 unlink_va(va, &vn->busy.root);
1863 spin_unlock(&vn->busy.lock);
d98c9e83
AR
1864
1865 /*
1866 * Insert/Merge it back to the free tree/list.
1867 */
1868 spin_lock(&free_vmap_area_lock);
96e2db45 1869 merge_or_add_vmap_area_augment(va, &free_vmap_area_root, &free_vmap_area_list);
d98c9e83
AR
1870 spin_unlock(&free_vmap_area_lock);
1871}
1872
187f8cc4
URS
1873static inline void
1874preload_this_cpu_lock(spinlock_t *lock, gfp_t gfp_mask, int node)
1875{
f56810c9 1876 struct vmap_area *va = NULL, *tmp;
187f8cc4
URS
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
f56810c9
UB
1892 tmp = NULL;
1893 if (va && !__this_cpu_try_cmpxchg(ne_fit_preload_node, &tmp, va))
187f8cc4
URS
1894 kmem_cache_free(vmap_area_cachep, va);
1895}
1896
72210662
URS
1897static struct vmap_pool *
1898size_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
1908static bool
1909node_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
1925static struct vmap_area *
1926node_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
1967static struct vmap_area *
1968node_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;
b25f97d0 1975 *addr = -EINVAL;
72210662
URS
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
aaab830a 1995static 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;
a0309faf 2000 vm->size = vm->requested_size = va_size(va);
aaab830a 2001 vm->caller = caller;
2002 va->vm = vm;
2003}
2004
db64fe02
NP
2005/*
2006 * Allocate a region of KVA of the specified size and alignment, within the
aaab830a 2007 * vstart and vend. If vm is passed in, the two will also be bound.
db64fe02
NP
2008 */
2009static struct vmap_area *alloc_vmap_area(unsigned long size,
2010 unsigned long align,
2011 unsigned long vstart, unsigned long vend,
869176a0 2012 int node, gfp_t gfp_mask,
4b68a773 2013 unsigned long va_flags, struct vm_struct *vm)
db64fe02 2014{
d0936029 2015 struct vmap_node *vn;
187f8cc4 2016 struct vmap_area *va;
12e376a6 2017 unsigned long freed;
1da177e4 2018 unsigned long addr;
72210662 2019 unsigned int vn_id;
db64fe02 2020 int purged = 0;
d98c9e83 2021 int ret;
db64fe02 2022
7e4a32c0
HL
2023 if (unlikely(!size || offset_in_page(size) || !is_power_of_2(align)))
2024 return ERR_PTR(-EINVAL);
db64fe02 2025
68ad4a33
URS
2026 if (unlikely(!vmap_initialized))
2027 return ERR_PTR(-EBUSY);
2028
5803ed29 2029 might_sleep();
db64fe02 2030
7f88f88f 2031 /*
72210662
URS
2032 * If a VA is obtained from a global heap(if it fails here)
2033 * it is anyway marked with this "vn_id" so it is returned
2034 * to this pool's node later. Such way gives a possibility
2035 * to populate pools based on users demand.
2036 *
2037 * On success a ready to go VA is returned.
7f88f88f 2038 */
72210662
URS
2039 va = node_alloc(size, align, vstart, vend, &addr, &vn_id);
2040 if (!va) {
2041 gfp_mask = gfp_mask & GFP_RECLAIM_MASK;
2042
2043 va = kmem_cache_alloc_node(vmap_area_cachep, gfp_mask, node);
2044 if (unlikely(!va))
2045 return ERR_PTR(-ENOMEM);
db64fe02 2046
96aa8437
URS
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 }
7f88f88f 2053
db64fe02 2054retry:
b25f97d0 2055 if (IS_ERR_VALUE(addr)) {
72210662
URS
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 }
89699605 2061
b25f97d0 2062 trace_alloc_vmap_area(addr, size, align, vstart, vend, IS_ERR_VALUE(addr));
cf243da6 2063
afd07389 2064 /*
b25f97d0 2065 * If an allocation fails, the error value is
68ad4a33 2066 * returned. Therefore trigger the overflow path.
afd07389 2067 */
b25f97d0 2068 if (IS_ERR_VALUE(addr))
89699605 2069 goto overflow;
db64fe02
NP
2070
2071 va->va_start = addr;
2072 va->va_end = addr + size;
688fcbfc 2073 va->vm = NULL;
72210662 2074 va->flags = (va_flags | vn_id);
68ad4a33 2075
4b68a773
BH
2076 if (vm) {
2077 vm->addr = (void *)va->va_start;
b44f71e3 2078 vm->size = va_size(va);
4b68a773
BH
2079 va->vm = vm;
2080 }
aaab830a 2081
d0936029
URS
2082 vn = addr_to_node(va->va_start);
2083
2084 spin_lock(&vn->busy.lock);
2085 insert_vmap_area(va, &vn->busy.root, &vn->busy.head);
2086 spin_unlock(&vn->busy.lock);
db64fe02 2087
61e16557 2088 BUG_ON(!IS_ALIGNED(va->va_start, align));
89699605
NP
2089 BUG_ON(va->va_start < vstart);
2090 BUG_ON(va->va_end > vend);
2091
d98c9e83
AR
2092 ret = kasan_populate_vmalloc(addr, size);
2093 if (ret) {
2094 free_vmap_area(va);
2095 return ERR_PTR(ret);
2096 }
2097
db64fe02 2098 return va;
89699605
NP
2099
2100overflow:
89699605 2101 if (!purged) {
77e50af0 2102 reclaim_and_purge_vmap_areas();
89699605
NP
2103 purged = 1;
2104 goto retry;
2105 }
4da56b99 2106
12e376a6
URS
2107 freed = 0;
2108 blocking_notifier_call_chain(&vmap_notify_list, 0, &freed);
2109
2110 if (freed > 0) {
2111 purged = 0;
2112 goto retry;
4da56b99
CW
2113 }
2114
03497d76 2115 if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit())
55ccad6f
SKO
2116 pr_warn("vmalloc_node_range for size %lu failed: Address range restricted to %#lx - %#lx\n",
2117 size, vstart, vend);
68ad4a33
URS
2118
2119 kmem_cache_free(vmap_area_cachep, va);
89699605 2120 return ERR_PTR(-EBUSY);
db64fe02
NP
2121}
2122
4da56b99
CW
2123int register_vmap_purge_notifier(struct notifier_block *nb)
2124{
2125 return blocking_notifier_chain_register(&vmap_notify_list, nb);
2126}
2127EXPORT_SYMBOL_GPL(register_vmap_purge_notifier);
2128
2129int unregister_vmap_purge_notifier(struct notifier_block *nb)
2130{
2131 return blocking_notifier_chain_unregister(&vmap_notify_list, nb);
2132}
2133EXPORT_SYMBOL_GPL(unregister_vmap_purge_notifier);
2134
db64fe02
NP
2135/*
2136 * lazy_max_pages is the maximum amount of virtual address space we gather up
2137 * before attempting to purge with a TLB flush.
2138 *
2139 * There is a tradeoff here: a larger number will cover more kernel page tables
2140 * and take slightly longer to purge, but it will linearly reduce the number of
2141 * global TLB flushes that must be performed. It would seem natural to scale
2142 * this number up linearly with the number of CPUs (because vmapping activity
2143 * could also scale linearly with the number of CPUs), however it is likely
2144 * that in practice, workloads might be constrained in other ways that mean
2145 * vmap activity will not scale linearly with CPUs. Also, I want to be
2146 * conservative and not introduce a big latency on huge systems, so go with
2147 * a less aggressive log scale. It will still be an improvement over the old
2148 * code, and it will be simple to change the scale factor if we find that it
2149 * becomes a problem on bigger systems.
2150 */
2151static unsigned long lazy_max_pages(void)
2152{
2153 unsigned int log;
2154
2155 log = fls(num_online_cpus());
2156
2157 return log * (32UL * 1024 * 1024 / PAGE_SIZE);
2158}
2159
0574ecd1 2160/*
f0953a1b 2161 * Serialize vmap purging. There is no actual critical section protected
153090f2 2162 * by this lock, but we want to avoid concurrent calls for performance
0574ecd1
CH
2163 * reasons and to make the pcpu_get_vm_areas more deterministic.
2164 */
f9e09977 2165static DEFINE_MUTEX(vmap_purge_lock);
0574ecd1 2166
02b709df
NP
2167/* for per-CPU blocks */
2168static void purge_fragmented_blocks_allcpus(void);
2169
72210662
URS
2170static void
2171reclaim_list_global(struct list_head *head)
db64fe02 2172{
72210662 2173 struct vmap_area *va, *n;
db64fe02 2174
72210662
URS
2175 if (list_empty(head))
2176 return;
02b709df 2177
e36176be 2178 spin_lock(&free_vmap_area_lock);
72210662
URS
2179 list_for_each_entry_safe(va, n, head, list)
2180 merge_or_add_vmap_area_augment(va,
2181 &free_vmap_area_root, &free_vmap_area_list);
2182 spin_unlock(&free_vmap_area_lock);
2183}
96e2db45 2184
72210662
URS
2185static void
2186decay_va_pool_node(struct vmap_node *vn, bool full_decay)
2187{
7ae12a57
HL
2188 LIST_HEAD(decay_list);
2189 struct rb_root decay_root = RB_ROOT;
72210662 2190 struct vmap_area *va, *nva;
4f05024e 2191 unsigned long n_decay, pool_len;
72210662 2192 int i;
68571be9 2193
72210662 2194 for (i = 0; i < MAX_VA_SIZE_PAGES; i++) {
7ae12a57 2195 LIST_HEAD(tmp_list);
db64fe02 2196
72210662
URS
2197 if (list_empty(&vn->pool[i].head))
2198 continue;
db64fe02 2199
72210662
URS
2200 /* Detach the pool, so no-one can access it. */
2201 spin_lock(&vn->pool_lock);
2202 list_replace_init(&vn->pool[i].head, &tmp_list);
2203 spin_unlock(&vn->pool_lock);
2204
4f05024e
BH
2205 pool_len = n_decay = vn->pool[i].len;
2206 WRITE_ONCE(vn->pool[i].len, 0);
72210662
URS
2207
2208 /* Decay a pool by ~25% out of left objects. */
4f05024e
BH
2209 if (!full_decay)
2210 n_decay >>= 2;
2211 pool_len -= n_decay;
72210662
URS
2212
2213 list_for_each_entry_safe(va, nva, &tmp_list, list) {
4f05024e
BH
2214 if (!n_decay--)
2215 break;
2216
72210662
URS
2217 list_del_init(&va->list);
2218 merge_or_add_vmap_area(va, &decay_root, &decay_list);
72210662 2219 }
763b218d 2220
dd3b8353 2221 /*
15e02a39
URS
2222 * Attach the pool back if it has been partly decayed.
2223 * Please note, it is supposed that nobody(other contexts)
2224 * can populate the pool therefore a simple list replace
2225 * operation takes place here.
dd3b8353 2226 */
4f05024e 2227 if (!list_empty(&tmp_list)) {
72210662
URS
2228 spin_lock(&vn->pool_lock);
2229 list_replace_init(&tmp_list, &vn->pool[i].head);
4f05024e 2230 WRITE_ONCE(vn->pool[i].len, pool_len);
72210662
URS
2231 spin_unlock(&vn->pool_lock);
2232 }
2233 }
3c5c3cfb 2234
72210662
URS
2235 reclaim_list_global(&decay_list);
2236}
2237
9e9e085e
AH
2238static void
2239kasan_release_vmalloc_node(struct vmap_node *vn)
2240{
2241 struct vmap_area *va;
2242 unsigned long start, end;
2243
2244 start = list_first_entry(&vn->purge_list, struct vmap_area, list)->va_start;
2245 end = list_last_entry(&vn->purge_list, struct vmap_area, list)->va_end;
2246
2247 list_for_each_entry(va, &vn->purge_list, list) {
2248 if (is_vmalloc_or_module_addr((void *) va->va_start))
2249 kasan_release_vmalloc(va->va_start, va->va_end,
2250 va->va_start, va->va_end,
2251 KASAN_VMALLOC_PAGE_RANGE);
2252 }
2253
2254 kasan_release_vmalloc(start, end, start, end, KASAN_VMALLOC_TLB_FLUSH);
2255}
2256
72210662
URS
2257static void purge_vmap_node(struct work_struct *work)
2258{
2259 struct vmap_node *vn = container_of(work,
2260 struct vmap_node, purge_work);
409faf8c 2261 unsigned long nr_purged_pages = 0;
72210662
URS
2262 struct vmap_area *va, *n_va;
2263 LIST_HEAD(local_list);
2264
9e9e085e
AH
2265 if (IS_ENABLED(CONFIG_KASAN_VMALLOC))
2266 kasan_release_vmalloc_node(vn);
2267
72210662
URS
2268 vn->nr_purged = 0;
2269
282631cb 2270 list_for_each_entry_safe(va, n_va, &vn->purge_list, list) {
b44f71e3 2271 unsigned long nr = va_size(va) >> PAGE_SHIFT;
72210662 2272 unsigned int vn_id = decode_vn_id(va->flags);
763b218d 2273
72210662 2274 list_del_init(&va->list);
9c801f61 2275
409faf8c 2276 nr_purged_pages += nr;
72210662 2277 vn->nr_purged++;
68571be9 2278
72210662
URS
2279 if (is_vn_id_valid(vn_id) && !vn->skip_populate)
2280 if (node_pool_add_va(vn, va))
2281 continue;
2282
2283 /* Go back to global. */
2284 list_add(&va->list, &local_list);
763b218d 2285 }
6030fd5f 2286
409faf8c
AH
2287 atomic_long_sub(nr_purged_pages, &vmap_lazy_nr);
2288
72210662 2289 reclaim_list_global(&local_list);
282631cb
URS
2290}
2291
2292/*
2293 * Purges all lazily-freed vmap areas.
2294 */
72210662
URS
2295static bool __purge_vmap_area_lazy(unsigned long start, unsigned long end,
2296 bool full_pool_decay)
282631cb 2297{
72210662
URS
2298 unsigned long nr_purged_areas = 0;
2299 unsigned int nr_purge_helpers;
f7f68274 2300 static cpumask_t purge_nodes;
72210662 2301 unsigned int nr_purge_nodes;
282631cb
URS
2302 struct vmap_node *vn;
2303 int i;
2304
2305 lockdep_assert_held(&vmap_purge_lock);
72210662
URS
2306
2307 /*
2308 * Use cpumask to mark which node has to be processed.
2309 */
282631cb
URS
2310 purge_nodes = CPU_MASK_NONE;
2311
24c76f37 2312 for_each_vmap_node(vn) {
282631cb 2313 INIT_LIST_HEAD(&vn->purge_list);
72210662
URS
2314 vn->skip_populate = full_pool_decay;
2315 decay_va_pool_node(vn, full_pool_decay);
282631cb
URS
2316
2317 if (RB_EMPTY_ROOT(&vn->lazy.root))
2318 continue;
2319
2320 spin_lock(&vn->lazy.lock);
2321 WRITE_ONCE(vn->lazy.root.rb_node, NULL);
2322 list_replace_init(&vn->lazy.head, &vn->purge_list);
2323 spin_unlock(&vn->lazy.lock);
2324
2325 start = min(start, list_first_entry(&vn->purge_list,
2326 struct vmap_area, list)->va_start);
2327
2328 end = max(end, list_last_entry(&vn->purge_list,
2329 struct vmap_area, list)->va_end);
2330
24c76f37 2331 cpumask_set_cpu(node_to_id(vn), &purge_nodes);
282631cb
URS
2332 }
2333
72210662
URS
2334 nr_purge_nodes = cpumask_weight(&purge_nodes);
2335 if (nr_purge_nodes > 0) {
282631cb
URS
2336 flush_tlb_kernel_range(start, end);
2337
72210662
URS
2338 /* One extra worker is per a lazy_max_pages() full set minus one. */
2339 nr_purge_helpers = atomic_long_read(&vmap_lazy_nr) / lazy_max_pages();
2340 nr_purge_helpers = clamp(nr_purge_helpers, 1U, nr_purge_nodes) - 1;
2341
282631cb 2342 for_each_cpu(i, &purge_nodes) {
72210662
URS
2343 vn = &vmap_nodes[i];
2344
2345 if (nr_purge_helpers > 0) {
2346 INIT_WORK(&vn->purge_work, purge_vmap_node);
2347
2348 if (cpumask_test_cpu(i, cpu_online_mask))
2349 schedule_work_on(i, &vn->purge_work);
2350 else
2351 schedule_work(&vn->purge_work);
2352
2353 nr_purge_helpers--;
2354 } else {
2355 vn->purge_work.func = NULL;
2356 purge_vmap_node(&vn->purge_work);
2357 nr_purged_areas += vn->nr_purged;
2358 }
2359 }
2360
2361 for_each_cpu(i, &purge_nodes) {
2362 vn = &vmap_nodes[i];
2363
2364 if (vn->purge_work.func) {
2365 flush_work(&vn->purge_work);
2366 nr_purged_areas += vn->nr_purged;
2367 }
282631cb
URS
2368 }
2369 }
2370
72210662
URS
2371 trace_purge_vmap_area_lazy(start, end, nr_purged_areas);
2372 return nr_purged_areas > 0;
db64fe02
NP
2373}
2374
2375/*
77e50af0 2376 * Reclaim vmap areas by purging fragmented blocks and purge_vmap_area_list.
db64fe02 2377 */
77e50af0
TG
2378static void reclaim_and_purge_vmap_areas(void)
2379
db64fe02 2380{
f9e09977 2381 mutex_lock(&vmap_purge_lock);
0574ecd1 2382 purge_fragmented_blocks_allcpus();
72210662 2383 __purge_vmap_area_lazy(ULONG_MAX, 0, true);
f9e09977 2384 mutex_unlock(&vmap_purge_lock);
db64fe02
NP
2385}
2386
690467c8
URS
2387static void drain_vmap_area_work(struct work_struct *work)
2388{
282631cb 2389 mutex_lock(&vmap_purge_lock);
72210662 2390 __purge_vmap_area_lazy(ULONG_MAX, 0, false);
282631cb 2391 mutex_unlock(&vmap_purge_lock);
690467c8
URS
2392}
2393
db64fe02 2394/*
edd89818
URS
2395 * Free a vmap area, caller ensuring that the area has been unmapped,
2396 * unlinked and flush_cache_vunmap had been called for the correct
2397 * range previously.
db64fe02 2398 */
64141da5 2399static void free_vmap_area_noflush(struct vmap_area *va)
db64fe02 2400{
8c4196fe
URS
2401 unsigned long nr_lazy_max = lazy_max_pages();
2402 unsigned long va_start = va->va_start;
72210662
URS
2403 unsigned int vn_id = decode_vn_id(va->flags);
2404 struct vmap_node *vn;
4d36e6f8 2405 unsigned long nr_lazy;
80c4bd7a 2406
edd89818
URS
2407 if (WARN_ON_ONCE(!list_empty(&va->list)))
2408 return;
dd3b8353 2409
0272d07e 2410 nr_lazy = atomic_long_add_return_relaxed(va_size(va) >> PAGE_SHIFT,
b44f71e3 2411 &vmap_lazy_nr);
80c4bd7a 2412
96e2db45 2413 /*
72210662
URS
2414 * If it was request by a certain node we would like to
2415 * return it to that node, i.e. its pool for later reuse.
96e2db45 2416 */
72210662
URS
2417 vn = is_vn_id_valid(vn_id) ?
2418 id_to_node(vn_id):addr_to_node(va->va_start);
2419
282631cb 2420 spin_lock(&vn->lazy.lock);
72210662 2421 insert_vmap_area(va, &vn->lazy.root, &vn->lazy.head);
282631cb 2422 spin_unlock(&vn->lazy.lock);
80c4bd7a 2423
8c4196fe
URS
2424 trace_free_vmap_area_noflush(va_start, nr_lazy, nr_lazy_max);
2425
96e2db45 2426 /* After this point, we may free va at any time */
8c4196fe 2427 if (unlikely(nr_lazy > nr_lazy_max))
690467c8 2428 schedule_work(&drain_vmap_work);
db64fe02
NP
2429}
2430
b29acbdc
NP
2431/*
2432 * Free and unmap a vmap area
2433 */
2434static void free_unmap_vmap_area(struct vmap_area *va)
2435{
2436 flush_cache_vunmap(va->va_start, va->va_end);
4ad0ae8c 2437 vunmap_range_noflush(va->va_start, va->va_end);
8e57f8ac 2438 if (debug_pagealloc_enabled_static())
82a2e924
CP
2439 flush_tlb_kernel_range(va->va_start, va->va_end);
2440
c8eef01e 2441 free_vmap_area_noflush(va);
b29acbdc
NP
2442}
2443
993d0b28 2444struct vmap_area *find_vmap_area(unsigned long addr)
db64fe02 2445{
d0936029 2446 struct vmap_node *vn;
db64fe02 2447 struct vmap_area *va;
d0936029 2448 int i, j;
db64fe02 2449
4ed91fa9
URS
2450 if (unlikely(!vmap_initialized))
2451 return NULL;
2452
d0936029
URS
2453 /*
2454 * An addr_to_node_id(addr) converts an address to a node index
2455 * where a VA is located. If VA spans several zones and passed
2456 * addr is not the same as va->va_start, what is not common, we
15e02a39 2457 * may need to scan extra nodes. See an example:
d0936029 2458 *
15e02a39 2459 * <----va---->
d0936029
URS
2460 * -|-----|-----|-----|-----|-
2461 * 1 2 0 1
2462 *
15e02a39
URS
2463 * VA resides in node 1 whereas it spans 1, 2 an 0. If passed
2464 * addr is within 2 or 0 nodes we should do extra work.
d0936029
URS
2465 */
2466 i = j = addr_to_node_id(addr);
2467 do {
2468 vn = &vmap_nodes[i];
db64fe02 2469
d0936029
URS
2470 spin_lock(&vn->busy.lock);
2471 va = __find_vmap_area(addr, &vn->busy.root);
2472 spin_unlock(&vn->busy.lock);
2473
2474 if (va)
2475 return va;
81262d85 2476 } while ((i = (i + nr_vmap_nodes - 1) % nr_vmap_nodes) != j);
d0936029
URS
2477
2478 return NULL;
db64fe02
NP
2479}
2480
edd89818
URS
2481static struct vmap_area *find_unlink_vmap_area(unsigned long addr)
2482{
d0936029 2483 struct vmap_node *vn;
edd89818 2484 struct vmap_area *va;
d0936029 2485 int i, j;
edd89818 2486
15e02a39
URS
2487 /*
2488 * Check the comment in the find_vmap_area() about the loop.
2489 */
d0936029
URS
2490 i = j = addr_to_node_id(addr);
2491 do {
2492 vn = &vmap_nodes[i];
edd89818 2493
d0936029
URS
2494 spin_lock(&vn->busy.lock);
2495 va = __find_vmap_area(addr, &vn->busy.root);
2496 if (va)
2497 unlink_va(va, &vn->busy.root);
2498 spin_unlock(&vn->busy.lock);
2499
2500 if (va)
2501 return va;
81262d85 2502 } while ((i = (i + nr_vmap_nodes - 1) % nr_vmap_nodes) != j);
d0936029
URS
2503
2504 return NULL;
edd89818
URS
2505}
2506
db64fe02
NP
2507/*** Per cpu kva allocator ***/
2508
2509/*
2510 * vmap space is limited especially on 32 bit architectures. Ensure there is
2511 * room for at least 16 percpu vmap blocks per CPU.
2512 */
2513/*
2514 * If we had a constant VMALLOC_START and VMALLOC_END, we'd like to be able
2515 * to #define VMALLOC_SPACE (VMALLOC_END-VMALLOC_START). Guess
2516 * instead (we just need a rough idea)
2517 */
2518#if BITS_PER_LONG == 32
2519#define VMALLOC_SPACE (128UL*1024*1024)
2520#else
2521#define VMALLOC_SPACE (128UL*1024*1024*1024)
2522#endif
2523
2524#define VMALLOC_PAGES (VMALLOC_SPACE / PAGE_SIZE)
2525#define VMAP_MAX_ALLOC BITS_PER_LONG /* 256K with 4K pages */
2526#define VMAP_BBMAP_BITS_MAX 1024 /* 4MB with 4K pages */
2527#define VMAP_BBMAP_BITS_MIN (VMAP_MAX_ALLOC*2)
2528#define VMAP_MIN(x, y) ((x) < (y) ? (x) : (y)) /* can't use min() */
2529#define VMAP_MAX(x, y) ((x) > (y) ? (x) : (y)) /* can't use max() */
f982f915
CL
2530#define VMAP_BBMAP_BITS \
2531 VMAP_MIN(VMAP_BBMAP_BITS_MAX, \
2532 VMAP_MAX(VMAP_BBMAP_BITS_MIN, \
2533 VMALLOC_PAGES / roundup_pow_of_two(NR_CPUS) / 16))
db64fe02
NP
2534
2535#define VMAP_BLOCK_SIZE (VMAP_BBMAP_BITS * PAGE_SIZE)
2536
77e50af0
TG
2537/*
2538 * Purge threshold to prevent overeager purging of fragmented blocks for
2539 * regular operations: Purge if vb->free is less than 1/4 of the capacity.
2540 */
2541#define VMAP_PURGE_THRESHOLD (VMAP_BBMAP_BITS / 4)
2542
869176a0
BH
2543#define VMAP_RAM 0x1 /* indicates vm_map_ram area*/
2544#define VMAP_BLOCK 0x2 /* mark out the vmap_block sub-type*/
2545#define VMAP_FLAGS_MASK 0x3
2546
db64fe02
NP
2547struct vmap_block_queue {
2548 spinlock_t lock;
2549 struct list_head free;
062eacf5
URS
2550
2551 /*
2552 * An xarray requires an extra memory dynamically to
2553 * be allocated. If it is an issue, we can use rb-tree
2554 * instead.
2555 */
2556 struct xarray vmap_blocks;
db64fe02
NP
2557};
2558
2559struct vmap_block {
2560 spinlock_t lock;
2561 struct vmap_area *va;
db64fe02 2562 unsigned long free, dirty;
d76f9954 2563 DECLARE_BITMAP(used_map, VMAP_BBMAP_BITS);
7d61bfe8 2564 unsigned long dirty_min, dirty_max; /*< dirty range */
de560423
NP
2565 struct list_head free_list;
2566 struct rcu_head rcu_head;
02b709df 2567 struct list_head purge;
8c61291f 2568 unsigned int cpu;
db64fe02
NP
2569};
2570
2571/* Queue of free and dirty vmap blocks, for allocation and flushing purposes */
2572static DEFINE_PER_CPU(struct vmap_block_queue, vmap_block_queue);
2573
2574/*
062eacf5
URS
2575 * In order to fast access to any "vmap_block" associated with a
2576 * specific address, we use a hash.
2577 *
2578 * A per-cpu vmap_block_queue is used in both ways, to serialize
2579 * an access to free block chains among CPUs(alloc path) and it
2580 * also acts as a vmap_block hash(alloc/free paths). It means we
2581 * overload it, since we already have the per-cpu array which is
2582 * used as a hash table. When used as a hash a 'cpu' passed to
2583 * per_cpu() is not actually a CPU but rather a hash index.
2584 *
fa1c77c1 2585 * A hash function is addr_to_vb_xa() which hashes any address
062eacf5
URS
2586 * to a specific index(in a hash) it belongs to. This then uses a
2587 * per_cpu() macro to access an array with generated index.
2588 *
2589 * An example:
2590 *
2591 * CPU_1 CPU_2 CPU_0
2592 * | | |
2593 * V V V
2594 * 0 10 20 30 40 50 60
2595 * |------|------|------|------|------|------|...<vmap address space>
2596 * CPU0 CPU1 CPU2 CPU0 CPU1 CPU2
2597 *
2598 * - CPU_1 invokes vm_unmap_ram(6), 6 belongs to CPU0 zone, thus
2599 * it access: CPU0/INDEX0 -> vmap_blocks -> xa_lock;
2600 *
2601 * - CPU_2 invokes vm_unmap_ram(11), 11 belongs to CPU1 zone, thus
2602 * it access: CPU1/INDEX1 -> vmap_blocks -> xa_lock;
2603 *
2604 * - CPU_0 invokes vm_unmap_ram(20), 20 belongs to CPU2 zone, thus
2605 * it access: CPU2/INDEX2 -> vmap_blocks -> xa_lock.
2606 *
2607 * This technique almost always avoids lock contention on insert/remove,
2608 * however xarray spinlocks protect against any contention that remains.
db64fe02 2609 */
062eacf5 2610static struct xarray *
fa1c77c1 2611addr_to_vb_xa(unsigned long addr)
062eacf5 2612{
a34acf30
URS
2613 int index = (addr / VMAP_BLOCK_SIZE) % nr_cpu_ids;
2614
2615 /*
2616 * Please note, nr_cpu_ids points on a highest set
2617 * possible bit, i.e. we never invoke cpumask_next()
2618 * if an index points on it which is nr_cpu_ids - 1.
2619 */
2620 if (!cpu_possible(index))
2621 index = cpumask_next(index, cpu_possible_mask);
062eacf5
URS
2622
2623 return &per_cpu(vmap_block_queue, index).vmap_blocks;
2624}
db64fe02
NP
2625
2626/*
2627 * We should probably have a fallback mechanism to allocate virtual memory
2628 * out of partially filled vmap blocks. However vmap block sizing should be
2629 * fairly reasonable according to the vmalloc size, so it shouldn't be a
2630 * big problem.
2631 */
2632
2633static unsigned long addr_to_vb_idx(unsigned long addr)
2634{
2635 addr -= VMALLOC_START & ~(VMAP_BLOCK_SIZE-1);
2636 addr /= VMAP_BLOCK_SIZE;
2637 return addr;
2638}
2639
cf725ce2
RP
2640static void *vmap_block_vaddr(unsigned long va_start, unsigned long pages_off)
2641{
2642 unsigned long addr;
2643
2644 addr = va_start + (pages_off << PAGE_SHIFT);
2645 BUG_ON(addr_to_vb_idx(addr) != addr_to_vb_idx(va_start));
2646 return (void *)addr;
2647}
2648
2649/**
2650 * new_vmap_block - allocates new vmap_block and occupies 2^order pages in this
2651 * block. Of course pages number can't exceed VMAP_BBMAP_BITS
2652 * @order: how many 2^order pages should be occupied in newly allocated block
2653 * @gfp_mask: flags for the page level allocator
2654 *
a862f68a 2655 * Return: virtual address in a newly allocated block or ERR_PTR(-errno)
cf725ce2
RP
2656 */
2657static void *new_vmap_block(unsigned int order, gfp_t gfp_mask)
db64fe02
NP
2658{
2659 struct vmap_block_queue *vbq;
2660 struct vmap_block *vb;
2661 struct vmap_area *va;
062eacf5 2662 struct xarray *xa;
db64fe02
NP
2663 unsigned long vb_idx;
2664 int node, err;
cf725ce2 2665 void *vaddr;
db64fe02
NP
2666
2667 node = numa_node_id();
2668
2669 vb = kmalloc_node(sizeof(struct vmap_block),
2670 gfp_mask & GFP_RECLAIM_MASK, node);
2671 if (unlikely(!vb))
2672 return ERR_PTR(-ENOMEM);
2673
2674 va = alloc_vmap_area(VMAP_BLOCK_SIZE, VMAP_BLOCK_SIZE,
2675 VMALLOC_START, VMALLOC_END,
869176a0 2676 node, gfp_mask,
4b68a773 2677 VMAP_RAM|VMAP_BLOCK, NULL);
ddf9c6d4 2678 if (IS_ERR(va)) {
db64fe02 2679 kfree(vb);
e7d86340 2680 return ERR_CAST(va);
db64fe02
NP
2681 }
2682
cf725ce2 2683 vaddr = vmap_block_vaddr(va->va_start, 0);
db64fe02
NP
2684 spin_lock_init(&vb->lock);
2685 vb->va = va;
cf725ce2
RP
2686 /* At least something should be left free */
2687 BUG_ON(VMAP_BBMAP_BITS <= (1UL << order));
d76f9954 2688 bitmap_zero(vb->used_map, VMAP_BBMAP_BITS);
cf725ce2 2689 vb->free = VMAP_BBMAP_BITS - (1UL << order);
db64fe02 2690 vb->dirty = 0;
7d61bfe8
RP
2691 vb->dirty_min = VMAP_BBMAP_BITS;
2692 vb->dirty_max = 0;
d76f9954 2693 bitmap_set(vb->used_map, 0, (1UL << order));
db64fe02 2694 INIT_LIST_HEAD(&vb->free_list);
3e3de794 2695 vb->cpu = raw_smp_processor_id();
db64fe02 2696
fa1c77c1 2697 xa = addr_to_vb_xa(va->va_start);
db64fe02 2698 vb_idx = addr_to_vb_idx(va->va_start);
062eacf5 2699 err = xa_insert(xa, vb_idx, vb, gfp_mask);
0f14599c
MWO
2700 if (err) {
2701 kfree(vb);
2702 free_vmap_area(va);
2703 return ERR_PTR(err);
2704 }
8c61291f
ZH
2705 /*
2706 * list_add_tail_rcu could happened in another core
2707 * rather than vb->cpu due to task migration, which
2708 * is safe as list_add_tail_rcu will ensure the list's
2709 * integrity together with list_for_each_rcu from read
2710 * side.
2711 */
8c61291f 2712 vbq = per_cpu_ptr(&vmap_block_queue, vb->cpu);
db64fe02 2713 spin_lock(&vbq->lock);
68ac546f 2714 list_add_tail_rcu(&vb->free_list, &vbq->free);
db64fe02 2715 spin_unlock(&vbq->lock);
db64fe02 2716
cf725ce2 2717 return vaddr;
db64fe02
NP
2718}
2719
db64fe02
NP
2720static void free_vmap_block(struct vmap_block *vb)
2721{
d0936029 2722 struct vmap_node *vn;
db64fe02 2723 struct vmap_block *tmp;
062eacf5 2724 struct xarray *xa;
db64fe02 2725
fa1c77c1 2726 xa = addr_to_vb_xa(vb->va->va_start);
062eacf5 2727 tmp = xa_erase(xa, addr_to_vb_idx(vb->va->va_start));
db64fe02
NP
2728 BUG_ON(tmp != vb);
2729
d0936029
URS
2730 vn = addr_to_node(vb->va->va_start);
2731 spin_lock(&vn->busy.lock);
2732 unlink_va(vb->va, &vn->busy.root);
2733 spin_unlock(&vn->busy.lock);
edd89818 2734
64141da5 2735 free_vmap_area_noflush(vb->va);
22a3c7d1 2736 kfree_rcu(vb, rcu_head);
db64fe02
NP
2737}
2738
ca5e46c3 2739static bool purge_fragmented_block(struct vmap_block *vb,
8c61291f 2740 struct list_head *purge_list, bool force_purge)
ca5e46c3 2741{
8c61291f
ZH
2742 struct vmap_block_queue *vbq = &per_cpu(vmap_block_queue, vb->cpu);
2743
ca5e46c3
TG
2744 if (vb->free + vb->dirty != VMAP_BBMAP_BITS ||
2745 vb->dirty == VMAP_BBMAP_BITS)
2746 return false;
2747
77e50af0
TG
2748 /* Don't overeagerly purge usable blocks unless requested */
2749 if (!(force_purge || vb->free < VMAP_PURGE_THRESHOLD))
2750 return false;
2751
ca5e46c3 2752 /* prevent further allocs after releasing lock */
7f48121e 2753 WRITE_ONCE(vb->free, 0);
ca5e46c3 2754 /* prevent purging it again */
7f48121e 2755 WRITE_ONCE(vb->dirty, VMAP_BBMAP_BITS);
ca5e46c3
TG
2756 vb->dirty_min = 0;
2757 vb->dirty_max = VMAP_BBMAP_BITS;
2758 spin_lock(&vbq->lock);
2759 list_del_rcu(&vb->free_list);
2760 spin_unlock(&vbq->lock);
2761 list_add_tail(&vb->purge, purge_list);
2762 return true;
2763}
2764
2765static void free_purged_blocks(struct list_head *purge_list)
2766{
2767 struct vmap_block *vb, *n_vb;
2768
2769 list_for_each_entry_safe(vb, n_vb, purge_list, purge) {
2770 list_del(&vb->purge);
2771 free_vmap_block(vb);
2772 }
2773}
2774
02b709df
NP
2775static void purge_fragmented_blocks(int cpu)
2776{
2777 LIST_HEAD(purge);
2778 struct vmap_block *vb;
02b709df
NP
2779 struct vmap_block_queue *vbq = &per_cpu(vmap_block_queue, cpu);
2780
2781 rcu_read_lock();
2782 list_for_each_entry_rcu(vb, &vbq->free, free_list) {
7f48121e
TG
2783 unsigned long free = READ_ONCE(vb->free);
2784 unsigned long dirty = READ_ONCE(vb->dirty);
2785
2786 if (free + dirty != VMAP_BBMAP_BITS ||
2787 dirty == VMAP_BBMAP_BITS)
02b709df
NP
2788 continue;
2789
2790 spin_lock(&vb->lock);
8c61291f 2791 purge_fragmented_block(vb, &purge, true);
ca5e46c3 2792 spin_unlock(&vb->lock);
02b709df
NP
2793 }
2794 rcu_read_unlock();
ca5e46c3 2795 free_purged_blocks(&purge);
02b709df
NP
2796}
2797
02b709df
NP
2798static void purge_fragmented_blocks_allcpus(void)
2799{
2800 int cpu;
2801
2802 for_each_possible_cpu(cpu)
2803 purge_fragmented_blocks(cpu);
2804}
2805
db64fe02
NP
2806static void *vb_alloc(unsigned long size, gfp_t gfp_mask)
2807{
2808 struct vmap_block_queue *vbq;
2809 struct vmap_block *vb;
cf725ce2 2810 void *vaddr = NULL;
db64fe02
NP
2811 unsigned int order;
2812
891c49ab 2813 BUG_ON(offset_in_page(size));
db64fe02 2814 BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC);
aa91c4d8
JK
2815 if (WARN_ON(size == 0)) {
2816 /*
2817 * Allocating 0 bytes isn't what caller wants since
2818 * get_order(0) returns funny result. Just warn and terminate
2819 * early.
2820 */
ac0476e8 2821 return ERR_PTR(-EINVAL);
aa91c4d8 2822 }
db64fe02
NP
2823 order = get_order(size);
2824
db64fe02 2825 rcu_read_lock();
3f804920 2826 vbq = raw_cpu_ptr(&vmap_block_queue);
db64fe02 2827 list_for_each_entry_rcu(vb, &vbq->free, free_list) {
cf725ce2 2828 unsigned long pages_off;
db64fe02 2829
43d76502
TG
2830 if (READ_ONCE(vb->free) < (1UL << order))
2831 continue;
2832
db64fe02 2833 spin_lock(&vb->lock);
cf725ce2
RP
2834 if (vb->free < (1UL << order)) {
2835 spin_unlock(&vb->lock);
2836 continue;
2837 }
02b709df 2838
cf725ce2
RP
2839 pages_off = VMAP_BBMAP_BITS - vb->free;
2840 vaddr = vmap_block_vaddr(vb->va->va_start, pages_off);
43d76502 2841 WRITE_ONCE(vb->free, vb->free - (1UL << order));
d76f9954 2842 bitmap_set(vb->used_map, pages_off, (1UL << order));
02b709df
NP
2843 if (vb->free == 0) {
2844 spin_lock(&vbq->lock);
2845 list_del_rcu(&vb->free_list);
2846 spin_unlock(&vbq->lock);
2847 }
cf725ce2 2848
02b709df
NP
2849 spin_unlock(&vb->lock);
2850 break;
db64fe02 2851 }
02b709df 2852
db64fe02
NP
2853 rcu_read_unlock();
2854
cf725ce2
RP
2855 /* Allocate new block if nothing was found */
2856 if (!vaddr)
2857 vaddr = new_vmap_block(order, gfp_mask);
db64fe02 2858
cf725ce2 2859 return vaddr;
db64fe02
NP
2860}
2861
78a0e8c4 2862static void vb_free(unsigned long addr, unsigned long size)
db64fe02
NP
2863{
2864 unsigned long offset;
db64fe02
NP
2865 unsigned int order;
2866 struct vmap_block *vb;
062eacf5 2867 struct xarray *xa;
db64fe02 2868
891c49ab 2869 BUG_ON(offset_in_page(size));
db64fe02 2870 BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC);
b29acbdc 2871
78a0e8c4 2872 flush_cache_vunmap(addr, addr + size);
b29acbdc 2873
db64fe02 2874 order = get_order(size);
78a0e8c4 2875 offset = (addr & (VMAP_BLOCK_SIZE - 1)) >> PAGE_SHIFT;
062eacf5 2876
fa1c77c1 2877 xa = addr_to_vb_xa(addr);
062eacf5
URS
2878 vb = xa_load(xa, addr_to_vb_idx(addr));
2879
d76f9954
BH
2880 spin_lock(&vb->lock);
2881 bitmap_clear(vb->used_map, offset, (1UL << order));
2882 spin_unlock(&vb->lock);
db64fe02 2883
4ad0ae8c 2884 vunmap_range_noflush(addr, addr + size);
64141da5 2885
8e57f8ac 2886 if (debug_pagealloc_enabled_static())
78a0e8c4 2887 flush_tlb_kernel_range(addr, addr + size);
82a2e924 2888
db64fe02 2889 spin_lock(&vb->lock);
7d61bfe8 2890
a09fad96 2891 /* Expand the not yet TLB flushed dirty range */
7d61bfe8
RP
2892 vb->dirty_min = min(vb->dirty_min, offset);
2893 vb->dirty_max = max(vb->dirty_max, offset + (1UL << order));
d086817d 2894
7f48121e 2895 WRITE_ONCE(vb->dirty, vb->dirty + (1UL << order));
db64fe02 2896 if (vb->dirty == VMAP_BBMAP_BITS) {
de560423 2897 BUG_ON(vb->free);
db64fe02
NP
2898 spin_unlock(&vb->lock);
2899 free_vmap_block(vb);
2900 } else
2901 spin_unlock(&vb->lock);
2902}
2903
868b104d 2904static void _vm_unmap_aliases(unsigned long start, unsigned long end, int flush)
db64fe02 2905{
ca5e46c3 2906 LIST_HEAD(purge_list);
db64fe02 2907 int cpu;
db64fe02 2908
9b463334
JF
2909 if (unlikely(!vmap_initialized))
2910 return;
2911
ca5e46c3 2912 mutex_lock(&vmap_purge_lock);
5803ed29 2913
db64fe02
NP
2914 for_each_possible_cpu(cpu) {
2915 struct vmap_block_queue *vbq = &per_cpu(vmap_block_queue, cpu);
2916 struct vmap_block *vb;
fc1e0d98 2917 unsigned long idx;
db64fe02
NP
2918
2919 rcu_read_lock();
fc1e0d98 2920 xa_for_each(&vbq->vmap_blocks, idx, vb) {
db64fe02 2921 spin_lock(&vb->lock);
ca5e46c3
TG
2922
2923 /*
2924 * Try to purge a fragmented block first. If it's
2925 * not purgeable, check whether there is dirty
2926 * space to be flushed.
2927 */
8c61291f 2928 if (!purge_fragmented_block(vb, &purge_list, false) &&
a09fad96 2929 vb->dirty_max && vb->dirty != VMAP_BBMAP_BITS) {
7d61bfe8 2930 unsigned long va_start = vb->va->va_start;
db64fe02 2931 unsigned long s, e;
b136be5e 2932
7d61bfe8
RP
2933 s = va_start + (vb->dirty_min << PAGE_SHIFT);
2934 e = va_start + (vb->dirty_max << PAGE_SHIFT);
db64fe02 2935
7d61bfe8
RP
2936 start = min(s, start);
2937 end = max(e, end);
db64fe02 2938
a09fad96
TG
2939 /* Prevent that this is flushed again */
2940 vb->dirty_min = VMAP_BBMAP_BITS;
2941 vb->dirty_max = 0;
2942
7d61bfe8 2943 flush = 1;
db64fe02
NP
2944 }
2945 spin_unlock(&vb->lock);
2946 }
2947 rcu_read_unlock();
2948 }
ca5e46c3 2949 free_purged_blocks(&purge_list);
db64fe02 2950
72210662 2951 if (!__purge_vmap_area_lazy(start, end, false) && flush)
0574ecd1 2952 flush_tlb_kernel_range(start, end);
f9e09977 2953 mutex_unlock(&vmap_purge_lock);
db64fe02 2954}
868b104d
RE
2955
2956/**
2957 * vm_unmap_aliases - unmap outstanding lazy aliases in the vmap layer
2958 *
2959 * The vmap/vmalloc layer lazily flushes kernel virtual mappings primarily
2960 * to amortize TLB flushing overheads. What this means is that any page you
2961 * have now, may, in a former life, have been mapped into kernel virtual
2962 * address by the vmap layer and so there might be some CPUs with TLB entries
2963 * still referencing that page (additional to the regular 1:1 kernel mapping).
2964 *
2965 * vm_unmap_aliases flushes all such lazy mappings. After it returns, we can
2966 * be sure that none of the pages we have control over will have any aliases
2967 * from the vmap layer.
2968 */
2969void vm_unmap_aliases(void)
2970{
8ab8442d 2971 _vm_unmap_aliases(ULONG_MAX, 0, 0);
868b104d 2972}
db64fe02
NP
2973EXPORT_SYMBOL_GPL(vm_unmap_aliases);
2974
2975/**
2976 * vm_unmap_ram - unmap linear kernel address space set up by vm_map_ram
2977 * @mem: the pointer returned by vm_map_ram
2978 * @count: the count passed to that vm_map_ram call (cannot unmap partial)
2979 */
2980void vm_unmap_ram(const void *mem, unsigned int count)
2981{
65ee03c4 2982 unsigned long size = (unsigned long)count << PAGE_SHIFT;
4aff1dc4 2983 unsigned long addr = (unsigned long)kasan_reset_tag(mem);
9c3acf60 2984 struct vmap_area *va;
db64fe02 2985
5803ed29 2986 might_sleep();
db64fe02
NP
2987 BUG_ON(!addr);
2988 BUG_ON(addr < VMALLOC_START);
2989 BUG_ON(addr > VMALLOC_END);
a1c0b1a0 2990 BUG_ON(!PAGE_ALIGNED(addr));
db64fe02 2991
d98c9e83
AR
2992 kasan_poison_vmalloc(mem, size);
2993
9c3acf60 2994 if (likely(count <= VMAP_MAX_ALLOC)) {
05e3ff95 2995 debug_check_no_locks_freed(mem, size);
78a0e8c4 2996 vb_free(addr, size);
9c3acf60
CH
2997 return;
2998 }
2999
edd89818 3000 va = find_unlink_vmap_area(addr);
14687619
URS
3001 if (WARN_ON_ONCE(!va))
3002 return;
3003
b44f71e3 3004 debug_check_no_locks_freed((void *)va->va_start, va_size(va));
9c3acf60 3005 free_unmap_vmap_area(va);
db64fe02
NP
3006}
3007EXPORT_SYMBOL(vm_unmap_ram);
3008
3009/**
3010 * vm_map_ram - map pages linearly into kernel virtual address (vmalloc space)
3011 * @pages: an array of pointers to the pages to be mapped
3012 * @count: number of pages
3013 * @node: prefer to allocate data structures on this node
e99c97ad 3014 *
36437638
GK
3015 * If you use this function for less than VMAP_MAX_ALLOC pages, it could be
3016 * faster than vmap so it's good. But if you mix long-life and short-life
3017 * objects with vm_map_ram(), it could consume lots of address space through
3018 * fragmentation (especially on a 32bit machine). You could see failures in
3019 * the end. Please use this function for short-lived objects.
3020 *
e99c97ad 3021 * Returns: a pointer to the address that has been mapped, or %NULL on failure
db64fe02 3022 */
d4efd79a 3023void *vm_map_ram(struct page **pages, unsigned int count, int node)
db64fe02 3024{
65ee03c4 3025 unsigned long size = (unsigned long)count << PAGE_SHIFT;
db64fe02
NP
3026 unsigned long addr;
3027 void *mem;
3028
3029 if (likely(count <= VMAP_MAX_ALLOC)) {
3030 mem = vb_alloc(size, GFP_KERNEL);
3031 if (IS_ERR(mem))
3032 return NULL;
3033 addr = (unsigned long)mem;
3034 } else {
3035 struct vmap_area *va;
3036 va = alloc_vmap_area(size, PAGE_SIZE,
869176a0 3037 VMALLOC_START, VMALLOC_END,
aaab830a 3038 node, GFP_KERNEL, VMAP_RAM,
4b68a773 3039 NULL);
db64fe02
NP
3040 if (IS_ERR(va))
3041 return NULL;
3042
3043 addr = va->va_start;
3044 mem = (void *)addr;
3045 }
d98c9e83 3046
b67177ec
NP
3047 if (vmap_pages_range(addr, addr + size, PAGE_KERNEL,
3048 pages, PAGE_SHIFT) < 0) {
db64fe02
NP
3049 vm_unmap_ram(mem, count);
3050 return NULL;
3051 }
b67177ec 3052
23689e91
AK
3053 /*
3054 * Mark the pages as accessible, now that they are mapped.
3055 * With hardware tag-based KASAN, marking is skipped for
3056 * non-VM_ALLOC mappings, see __kasan_unpoison_vmalloc().
3057 */
f6e39794 3058 mem = kasan_unpoison_vmalloc(mem, size, KASAN_VMALLOC_PROT_NORMAL);
19f1c3ac 3059
db64fe02
NP
3060 return mem;
3061}
3062EXPORT_SYMBOL(vm_map_ram);
3063
4341fa45 3064static struct vm_struct *vmlist __initdata;
92eac168 3065
121e6f32
NP
3066static inline unsigned int vm_area_page_order(struct vm_struct *vm)
3067{
3068#ifdef CONFIG_HAVE_ARCH_HUGE_VMALLOC
3069 return vm->page_order;
3070#else
3071 return 0;
3072#endif
3073}
3074
2e45474a
MRM
3075unsigned int get_vm_area_page_order(struct vm_struct *vm)
3076{
3077 return vm_area_page_order(vm);
3078}
3079
121e6f32
NP
3080static inline void set_vm_area_page_order(struct vm_struct *vm, unsigned int order)
3081{
3082#ifdef CONFIG_HAVE_ARCH_HUGE_VMALLOC
3083 vm->page_order = order;
3084#else
3085 BUG_ON(order != 0);
3086#endif
3087}
3088
be9b7335
NP
3089/**
3090 * vm_area_add_early - add vmap area early during boot
3091 * @vm: vm_struct to add
3092 *
3093 * This function is used to add fixed kernel vm area to vmlist before
3094 * vmalloc_init() is called. @vm->addr, @vm->size, and @vm->flags
3095 * should contain proper values and the other fields should be zero.
3096 *
3097 * DO NOT USE THIS FUNCTION UNLESS YOU KNOW WHAT YOU'RE DOING.
3098 */
3099void __init vm_area_add_early(struct vm_struct *vm)
3100{
3101 struct vm_struct *tmp, **p;
3102
3103 BUG_ON(vmap_initialized);
3104 for (p = &vmlist; (tmp = *p) != NULL; p = &tmp->next) {
3105 if (tmp->addr >= vm->addr) {
3106 BUG_ON(tmp->addr < vm->addr + vm->size);
3107 break;
3108 } else
3109 BUG_ON(tmp->addr + tmp->size > vm->addr);
3110 }
3111 vm->next = *p;
3112 *p = vm;
3113}
3114
f0aa6617
TH
3115/**
3116 * vm_area_register_early - register vmap area early during boot
3117 * @vm: vm_struct to register
c0c0a293 3118 * @align: requested alignment
f0aa6617
TH
3119 *
3120 * This function is used to register kernel vm area before
3121 * vmalloc_init() is called. @vm->size and @vm->flags should contain
3122 * proper values on entry and other fields should be zero. On return,
3123 * vm->addr contains the allocated address.
3124 *
3125 * DO NOT USE THIS FUNCTION UNLESS YOU KNOW WHAT YOU'RE DOING.
3126 */
c0c0a293 3127void __init vm_area_register_early(struct vm_struct *vm, size_t align)
f0aa6617 3128{
0eb68437
KW
3129 unsigned long addr = ALIGN(VMALLOC_START, align);
3130 struct vm_struct *cur, **p;
c0c0a293 3131
0eb68437 3132 BUG_ON(vmap_initialized);
f0aa6617 3133
0eb68437
KW
3134 for (p = &vmlist; (cur = *p) != NULL; p = &cur->next) {
3135 if ((unsigned long)cur->addr - addr >= vm->size)
3136 break;
3137 addr = ALIGN((unsigned long)cur->addr + cur->size, align);
3138 }
f0aa6617 3139
0eb68437
KW
3140 BUG_ON(addr > VMALLOC_END - vm->size);
3141 vm->addr = (void *)addr;
3142 vm->next = *p;
3143 *p = vm;
3252b1d8 3144 kasan_populate_early_vm_area_shadow(vm->addr, vm->size);
f0aa6617
TH
3145}
3146
20fc02b4 3147static void clear_vm_uninitialized_flag(struct vm_struct *vm)
f5252e00 3148{
d4033afd 3149 /*
20fc02b4 3150 * Before removing VM_UNINITIALIZED,
d4033afd 3151 * we should make sure that vm has proper values.
5c5f0468 3152 * Pair with smp_rmb() in vread_iter() and vmalloc_info_show().
d4033afd
JK
3153 */
3154 smp_wmb();
20fc02b4 3155 vm->flags &= ~VM_UNINITIALIZED;
cf88c790
TH
3156}
3157
0f9b6856 3158struct vm_struct *__get_vm_area_node(unsigned long size,
7ca3027b
DA
3159 unsigned long align, unsigned long shift, unsigned long flags,
3160 unsigned long start, unsigned long end, int node,
3161 gfp_t gfp_mask, const void *caller)
db64fe02 3162{
0006526d 3163 struct vmap_area *va;
db64fe02 3164 struct vm_struct *area;
d98c9e83 3165 unsigned long requested_size = size;
1da177e4 3166
52fd24ca 3167 BUG_ON(in_interrupt());
7ca3027b 3168 size = ALIGN(size, 1ul << shift);
31be8309
OH
3169 if (unlikely(!size))
3170 return NULL;
1da177e4 3171
252e5c6e 3172 if (flags & VM_IOREMAP)
3173 align = 1ul << clamp_t(int, get_count_order_long(size),
3174 PAGE_SHIFT, IOREMAP_MAX_ORDER);
3175
cf88c790 3176 area = kzalloc_node(sizeof(*area), gfp_mask & GFP_RECLAIM_MASK, node);
1da177e4
LT
3177 if (unlikely(!area))
3178 return NULL;
3179
71394fe5
AR
3180 if (!(flags & VM_NO_GUARD))
3181 size += PAGE_SIZE;
1da177e4 3182
4b68a773
BH
3183 area->flags = flags;
3184 area->caller = caller;
a0309faf 3185 area->requested_size = requested_size;
4b68a773
BH
3186
3187 va = alloc_vmap_area(size, align, start, end, node, gfp_mask, 0, area);
db64fe02
NP
3188 if (IS_ERR(va)) {
3189 kfree(area);
3190 return NULL;
1da177e4 3191 }
1da177e4 3192
19f1c3ac
AK
3193 /*
3194 * Mark pages for non-VM_ALLOC mappings as accessible. Do it now as a
3195 * best-effort approach, as they can be mapped outside of vmalloc code.
3196 * For VM_ALLOC mappings, the pages are marked as accessible after
3197 * getting mapped in __vmalloc_node_range().
23689e91
AK
3198 * With hardware tag-based KASAN, marking is skipped for
3199 * non-VM_ALLOC mappings, see __kasan_unpoison_vmalloc().
19f1c3ac
AK
3200 */
3201 if (!(flags & VM_ALLOC))
23689e91 3202 area->addr = kasan_unpoison_vmalloc(area->addr, requested_size,
f6e39794 3203 KASAN_VMALLOC_PROT_NORMAL);
1d96320f 3204
1da177e4 3205 return area;
1da177e4
LT
3206}
3207
c2968612
BH
3208struct vm_struct *__get_vm_area_caller(unsigned long size, unsigned long flags,
3209 unsigned long start, unsigned long end,
5e6cafc8 3210 const void *caller)
c2968612 3211{
7ca3027b
DA
3212 return __get_vm_area_node(size, 1, PAGE_SHIFT, flags, start, end,
3213 NUMA_NO_NODE, GFP_KERNEL, caller);
c2968612
BH
3214}
3215
1da177e4 3216/**
92eac168
MR
3217 * get_vm_area - reserve a contiguous kernel virtual area
3218 * @size: size of the area
3219 * @flags: %VM_IOREMAP for I/O mappings or VM_ALLOC
1da177e4 3220 *
92eac168
MR
3221 * Search an area of @size in the kernel virtual mapping area,
3222 * and reserved it for out purposes. Returns the area descriptor
3223 * on success or %NULL on failure.
a862f68a
MR
3224 *
3225 * Return: the area descriptor on success or %NULL on failure.
1da177e4
LT
3226 */
3227struct vm_struct *get_vm_area(unsigned long size, unsigned long flags)
3228{
7ca3027b
DA
3229 return __get_vm_area_node(size, 1, PAGE_SHIFT, flags,
3230 VMALLOC_START, VMALLOC_END,
00ef2d2f
DR
3231 NUMA_NO_NODE, GFP_KERNEL,
3232 __builtin_return_address(0));
23016969
CL
3233}
3234
3235struct vm_struct *get_vm_area_caller(unsigned long size, unsigned long flags,
5e6cafc8 3236 const void *caller)
23016969 3237{
7ca3027b
DA
3238 return __get_vm_area_node(size, 1, PAGE_SHIFT, flags,
3239 VMALLOC_START, VMALLOC_END,
00ef2d2f 3240 NUMA_NO_NODE, GFP_KERNEL, caller);
1da177e4
LT
3241}
3242
e9da6e99 3243/**
92eac168
MR
3244 * find_vm_area - find a continuous kernel virtual area
3245 * @addr: base address
e9da6e99 3246 *
92eac168
MR
3247 * Search for the kernel VM area starting at @addr, and return it.
3248 * It is up to the caller to do all required locking to keep the returned
3249 * pointer valid.
a862f68a 3250 *
74640617 3251 * Return: the area descriptor on success or %NULL on failure.
e9da6e99
MS
3252 */
3253struct vm_struct *find_vm_area(const void *addr)
83342314 3254{
db64fe02 3255 struct vmap_area *va;
83342314 3256
db64fe02 3257 va = find_vmap_area((unsigned long)addr);
688fcbfc
PL
3258 if (!va)
3259 return NULL;
1da177e4 3260
688fcbfc 3261 return va->vm;
1da177e4
LT
3262}
3263
7856dfeb 3264/**
92eac168
MR
3265 * remove_vm_area - find and remove a continuous kernel virtual area
3266 * @addr: base address
7856dfeb 3267 *
92eac168
MR
3268 * Search for the kernel VM area starting at @addr, and remove it.
3269 * This function returns the found VM area, but using it is NOT safe
3270 * on SMP machines, except for its size or flags.
a862f68a 3271 *
74640617 3272 * Return: the area descriptor on success or %NULL on failure.
7856dfeb 3273 */
b3bdda02 3274struct vm_struct *remove_vm_area(const void *addr)
7856dfeb 3275{
db64fe02 3276 struct vmap_area *va;
75c59ce7 3277 struct vm_struct *vm;
db64fe02 3278
5803ed29
CH
3279 might_sleep();
3280
17d3ef43
CH
3281 if (WARN(!PAGE_ALIGNED(addr), "Trying to vfree() bad address (%p)\n",
3282 addr))
3283 return NULL;
c69480ad 3284
75c59ce7
CH
3285 va = find_unlink_vmap_area((unsigned long)addr);
3286 if (!va || !va->vm)
3287 return NULL;
3288 vm = va->vm;
dd32c279 3289
17d3ef43
CH
3290 debug_check_no_locks_freed(vm->addr, get_vm_area_size(vm));
3291 debug_check_no_obj_freed(vm->addr, get_vm_area_size(vm));
75c59ce7 3292 kasan_free_module_shadow(vm);
17d3ef43 3293 kasan_poison_vmalloc(vm->addr, get_vm_area_size(vm));
dd3b8353 3294
75c59ce7
CH
3295 free_unmap_vmap_area(va);
3296 return vm;
7856dfeb
AK
3297}
3298
868b104d
RE
3299static inline void set_area_direct_map(const struct vm_struct *area,
3300 int (*set_direct_map)(struct page *page))
3301{
3302 int i;
3303
121e6f32 3304 /* HUGE_VMALLOC passes small pages to set_direct_map */
868b104d
RE
3305 for (i = 0; i < area->nr_pages; i++)
3306 if (page_address(area->pages[i]))
3307 set_direct_map(area->pages[i]);
3308}
3309
9e5fa0ae
CH
3310/*
3311 * Flush the vm mapping and reset the direct map.
3312 */
3313static void vm_reset_perms(struct vm_struct *area)
868b104d 3314{
868b104d 3315 unsigned long start = ULONG_MAX, end = 0;
121e6f32 3316 unsigned int page_order = vm_area_page_order(area);
31e67340 3317 int flush_dmap = 0;
868b104d
RE
3318 int i;
3319
868b104d 3320 /*
9e5fa0ae 3321 * Find the start and end range of the direct mappings to make sure that
868b104d
RE
3322 * the vm_unmap_aliases() flush includes the direct map.
3323 */
121e6f32 3324 for (i = 0; i < area->nr_pages; i += 1U << page_order) {
8e41f872 3325 unsigned long addr = (unsigned long)page_address(area->pages[i]);
9e5fa0ae 3326
8e41f872 3327 if (addr) {
121e6f32
NP
3328 unsigned long page_size;
3329
3330 page_size = PAGE_SIZE << page_order;
868b104d 3331 start = min(addr, start);
121e6f32 3332 end = max(addr + page_size, end);
31e67340 3333 flush_dmap = 1;
868b104d
RE
3334 }
3335 }
3336
3337 /*
3338 * Set direct map to something invalid so that it won't be cached if
3339 * there are any accesses after the TLB flush, then flush the TLB and
3340 * reset the direct map permissions to the default.
3341 */
3342 set_area_direct_map(area, set_direct_map_invalid_noflush);
31e67340 3343 _vm_unmap_aliases(start, end, flush_dmap);
868b104d
RE
3344 set_area_direct_map(area, set_direct_map_default_noflush);
3345}
3346
208162f4 3347static void delayed_vfree_work(struct work_struct *w)
1da177e4 3348{
208162f4
CH
3349 struct vfree_deferred *p = container_of(w, struct vfree_deferred, wq);
3350 struct llist_node *t, *llnode;
bf22e37a 3351
208162f4 3352 llist_for_each_safe(llnode, t, llist_del_all(&p->list))
5d3d31d6 3353 vfree(llnode);
bf22e37a
AR
3354}
3355
3356/**
92eac168
MR
3357 * vfree_atomic - release memory allocated by vmalloc()
3358 * @addr: memory base address
bf22e37a 3359 *
92eac168
MR
3360 * This one is just like vfree() but can be called in any atomic context
3361 * except NMIs.
bf22e37a
AR
3362 */
3363void vfree_atomic(const void *addr)
3364{
01e2e839 3365 struct vfree_deferred *p = raw_cpu_ptr(&vfree_deferred);
bf22e37a 3366
01e2e839 3367 BUG_ON(in_nmi());
bf22e37a
AR
3368 kmemleak_free(addr);
3369
01e2e839
CH
3370 /*
3371 * Use raw_cpu_ptr() because this can be called from preemptible
3372 * context. Preemption is absolutely fine here, because the llist_add()
3373 * implementation is lockless, so it works even if we are adding to
3374 * another cpu's list. schedule_work() should be fine with this too.
3375 */
3376 if (addr && llist_add((struct llist_node *)addr, &p->list))
3377 schedule_work(&p->wq);
c67dc624
RP
3378}
3379
1da177e4 3380/**
fa307474
MWO
3381 * vfree - Release memory allocated by vmalloc()
3382 * @addr: Memory base address
1da177e4 3383 *
fa307474
MWO
3384 * Free the virtually continuous memory area starting at @addr, as obtained
3385 * from one of the vmalloc() family of APIs. This will usually also free the
3386 * physical memory underlying the virtual allocation, but that memory is
3387 * reference counted, so it will not be freed until the last user goes away.
1da177e4 3388 *
fa307474 3389 * If @addr is NULL, no operation is performed.
c9fcee51 3390 *
fa307474 3391 * Context:
92eac168 3392 * May sleep if called *not* from interrupt context.
fa307474
MWO
3393 * Must not be called in NMI context (strictly speaking, it could be
3394 * if we have CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG, but making the calling
f0953a1b 3395 * conventions for vfree() arch-dependent would be a really bad idea).
1da177e4 3396 */
b3bdda02 3397void vfree(const void *addr)
1da177e4 3398{
79311c1f
CH
3399 struct vm_struct *vm;
3400 int i;
89219d37 3401
01e2e839
CH
3402 if (unlikely(in_interrupt())) {
3403 vfree_atomic(addr);
3404 return;
3405 }
89219d37 3406
01e2e839 3407 BUG_ON(in_nmi());
89219d37 3408 kmemleak_free(addr);
01e2e839 3409 might_sleep();
a8dda165 3410
32fcfd40
AV
3411 if (!addr)
3412 return;
c67dc624 3413
79311c1f
CH
3414 vm = remove_vm_area(addr);
3415 if (unlikely(!vm)) {
3416 WARN(1, KERN_ERR "Trying to vfree() nonexistent vm area (%p)\n",
3417 addr);
3418 return;
3419 }
3420
9e5fa0ae
CH
3421 if (unlikely(vm->flags & VM_FLUSH_RESET_PERMS))
3422 vm_reset_perms(vm);
aa8d89d1
SB
3423 /* All pages of vm should be charged to same memcg, so use first one. */
3424 if (vm->nr_pages && !(vm->flags & VM_MAP_PUT_PAGES))
3425 mod_memcg_page_state(vm->pages[0], MEMCG_VMALLOC, -vm->nr_pages);
79311c1f
CH
3426 for (i = 0; i < vm->nr_pages; i++) {
3427 struct page *page = vm->pages[i];
3428
3429 BUG_ON(!page);
79311c1f
CH
3430 /*
3431 * High-order allocs for huge vmallocs are split, so
3432 * can be freed as an array of order-0 allocations
3433 */
dcc1be11 3434 __free_page(page);
79311c1f
CH
3435 cond_resched();
3436 }
a2e740e2
MWO
3437 if (!(vm->flags & VM_MAP_PUT_PAGES))
3438 atomic_long_sub(vm->nr_pages, &nr_vmalloc_pages);
79311c1f
CH
3439 kvfree(vm->pages);
3440 kfree(vm);
1da177e4 3441}
1da177e4
LT
3442EXPORT_SYMBOL(vfree);
3443
3444/**
92eac168
MR
3445 * vunmap - release virtual mapping obtained by vmap()
3446 * @addr: memory base address
1da177e4 3447 *
92eac168
MR
3448 * Free the virtually contiguous memory area starting at @addr,
3449 * which was created from the page array passed to vmap().
1da177e4 3450 *
92eac168 3451 * Must not be called in interrupt context.
1da177e4 3452 */
b3bdda02 3453void vunmap(const void *addr)
1da177e4 3454{
79311c1f
CH
3455 struct vm_struct *vm;
3456
1da177e4 3457 BUG_ON(in_interrupt());
34754b69 3458 might_sleep();
79311c1f
CH
3459
3460 if (!addr)
3461 return;
3462 vm = remove_vm_area(addr);
3463 if (unlikely(!vm)) {
3464 WARN(1, KERN_ERR "Trying to vunmap() nonexistent vm area (%p)\n",
3465 addr);
3466 return;
3467 }
3468 kfree(vm);
1da177e4 3469}
1da177e4
LT
3470EXPORT_SYMBOL(vunmap);
3471
3472/**
92eac168
MR
3473 * vmap - map an array of pages into virtually contiguous space
3474 * @pages: array of page pointers
3475 * @count: number of pages to map
3476 * @flags: vm_area->flags
3477 * @prot: page protection for the mapping
3478 *
b944afc9
CH
3479 * Maps @count pages from @pages into contiguous kernel virtual space.
3480 * If @flags contains %VM_MAP_PUT_PAGES the ownership of the pages array itself
3481 * (which must be kmalloc or vmalloc memory) and one reference per pages in it
3482 * are transferred from the caller to vmap(), and will be freed / dropped when
3483 * vfree() is called on the return value.
a862f68a
MR
3484 *
3485 * Return: the address of the area or %NULL on failure
1da177e4
LT
3486 */
3487void *vmap(struct page **pages, unsigned int count,
92eac168 3488 unsigned long flags, pgprot_t prot)
1da177e4
LT
3489{
3490 struct vm_struct *area;
b67177ec 3491 unsigned long addr;
65ee03c4 3492 unsigned long size; /* In bytes */
1da177e4 3493
34754b69
PZ
3494 might_sleep();
3495
37f3605e
CH
3496 if (WARN_ON_ONCE(flags & VM_FLUSH_RESET_PERMS))
3497 return NULL;
3498
bd1a8fb2
PZ
3499 /*
3500 * Your top guard is someone else's bottom guard. Not having a top
3501 * guard compromises someone else's mappings too.
3502 */
3503 if (WARN_ON_ONCE(flags & VM_NO_GUARD))
3504 flags &= ~VM_NO_GUARD;
3505
ca79b0c2 3506 if (count > totalram_pages())
1da177e4
LT
3507 return NULL;
3508
65ee03c4
GJM
3509 size = (unsigned long)count << PAGE_SHIFT;
3510 area = get_vm_area_caller(size, flags, __builtin_return_address(0));
1da177e4
LT
3511 if (!area)
3512 return NULL;
23016969 3513
b67177ec
NP
3514 addr = (unsigned long)area->addr;
3515 if (vmap_pages_range(addr, addr + size, pgprot_nx(prot),
3516 pages, PAGE_SHIFT) < 0) {
1da177e4
LT
3517 vunmap(area->addr);
3518 return NULL;
3519 }
3520
c22ee528 3521 if (flags & VM_MAP_PUT_PAGES) {
b944afc9 3522 area->pages = pages;
c22ee528
ML
3523 area->nr_pages = count;
3524 }
1da177e4
LT
3525 return area->addr;
3526}
1da177e4
LT
3527EXPORT_SYMBOL(vmap);
3528
3e9a9e25
CH
3529#ifdef CONFIG_VMAP_PFN
3530struct vmap_pfn_data {
3531 unsigned long *pfns;
3532 pgprot_t prot;
3533 unsigned int idx;
3534};
3535
3536static int vmap_pfn_apply(pte_t *pte, unsigned long addr, void *private)
3537{
3538 struct vmap_pfn_data *data = private;
b3f78e74
RR
3539 unsigned long pfn = data->pfns[data->idx];
3540 pte_t ptent;
3e9a9e25 3541
b3f78e74 3542 if (WARN_ON_ONCE(pfn_valid(pfn)))
3e9a9e25 3543 return -EINVAL;
b3f78e74
RR
3544
3545 ptent = pte_mkspecial(pfn_pte(pfn, data->prot));
3546 set_pte_at(&init_mm, addr, pte, ptent);
3547
3548 data->idx++;
3e9a9e25
CH
3549 return 0;
3550}
3551
3552/**
3553 * vmap_pfn - map an array of PFNs into virtually contiguous space
3554 * @pfns: array of PFNs
3555 * @count: number of pages to map
3556 * @prot: page protection for the mapping
3557 *
3558 * Maps @count PFNs from @pfns into contiguous kernel virtual space and returns
3559 * the start address of the mapping.
3560 */
3561void *vmap_pfn(unsigned long *pfns, unsigned int count, pgprot_t prot)
3562{
3563 struct vmap_pfn_data data = { .pfns = pfns, .prot = pgprot_nx(prot) };
3564 struct vm_struct *area;
3565
3566 area = get_vm_area_caller(count * PAGE_SIZE, VM_IOREMAP,
3567 __builtin_return_address(0));
3568 if (!area)
3569 return NULL;
3570 if (apply_to_page_range(&init_mm, (unsigned long)area->addr,
3571 count * PAGE_SIZE, vmap_pfn_apply, &data)) {
3572 free_vm_area(area);
3573 return NULL;
3574 }
a50420c7
AG
3575
3576 flush_cache_vmap((unsigned long)area->addr,
3577 (unsigned long)area->addr + count * PAGE_SIZE);
3578
3e9a9e25
CH
3579 return area->addr;
3580}
3581EXPORT_SYMBOL_GPL(vmap_pfn);
3582#endif /* CONFIG_VMAP_PFN */
3583
12b9f873
UR
3584static inline unsigned int
3585vm_area_alloc_pages(gfp_t gfp, int nid,
343ab817 3586 unsigned int order, unsigned int nr_pages, struct page **pages)
12b9f873
UR
3587{
3588 unsigned int nr_allocated = 0;
ffb29b1c
CW
3589 struct page *page;
3590 int i;
12b9f873
UR
3591
3592 /*
3593 * For order-0 pages we make use of bulk allocator, if
3594 * the page array is partly or not at all populated due
3595 * to fails, fallback to a single page allocator that is
3596 * more permissive.
3597 */
c00b6b96 3598 if (!order) {
343ab817
URS
3599 while (nr_allocated < nr_pages) {
3600 unsigned int nr, nr_pages_request;
3601
3602 /*
3603 * A maximum allowed request is hard-coded and is 100
3604 * pages per call. That is done in order to prevent a
3605 * long preemption off scenario in the bulk-allocator
3606 * so the range is [1:100].
3607 */
3608 nr_pages_request = min(100U, nr_pages - nr_allocated);
3609
c00b6b96
CW
3610 /* memory allocation should consider mempolicy, we can't
3611 * wrongly use nearest node when nid == NUMA_NO_NODE,
3612 * otherwise memory may be allocated in only one node,
98af39d5 3613 * but mempolicy wants to alloc memory by interleaving.
c00b6b96
CW
3614 */
3615 if (IS_ENABLED(CONFIG_NUMA) && nid == NUMA_NO_NODE)
6bf9b5b4 3616 nr = alloc_pages_bulk_mempolicy_noprof(gfp,
c00b6b96
CW
3617 nr_pages_request,
3618 pages + nr_allocated);
c00b6b96 3619 else
6bf9b5b4 3620 nr = alloc_pages_bulk_node_noprof(gfp, nid,
c00b6b96
CW
3621 nr_pages_request,
3622 pages + nr_allocated);
343ab817
URS
3623
3624 nr_allocated += nr;
3625 cond_resched();
3626
3627 /*
3628 * If zero or pages were obtained partly,
3629 * fallback to a single page allocator.
3630 */
3631 if (nr != nr_pages_request)
3632 break;
3633 }
3b8000ae 3634 }
12b9f873
UR
3635
3636 /* High-order pages or fallback path if "bulk" fails. */
ffb29b1c 3637 while (nr_allocated < nr_pages) {
7de8728f 3638 if (!(gfp & __GFP_NOFAIL) && fatal_signal_pending(current))
dd544141
VA
3639 break;
3640
ffb29b1c 3641 if (nid == NUMA_NO_NODE)
7de8728f 3642 page = alloc_pages_noprof(gfp, order);
ffb29b1c 3643 else
7de8728f
URS
3644 page = alloc_pages_node_noprof(nid, gfp, order);
3645
61ebe5a7
HL
3646 if (unlikely(!page))
3647 break;
e9c3cda4 3648
3b8000ae 3649 /*
6004fe00 3650 * High-order allocations must be able to be treated as
7de8728f 3651 * independent small pages by callers (as they can with
3b8000ae
NP
3652 * small-page vmallocs). Some drivers do their own refcounting
3653 * on vmalloc_to_page() pages, some use page->mapping,
3654 * page->lru, etc.
3655 */
3656 if (order)
3657 split_page(page, order);
12b9f873
UR
3658
3659 /*
3660 * Careful, we allocate and map page-order pages, but
3661 * tracking is done per PAGE_SIZE page so as to keep the
3662 * vm_struct APIs independent of the physical/mapped size.
3663 */
3664 for (i = 0; i < (1U << order); i++)
3665 pages[nr_allocated + i] = page + i;
3666
12e376a6 3667 cond_resched();
12b9f873
UR
3668 nr_allocated += 1U << order;
3669 }
3670
3671 return nr_allocated;
3672}
3673
e31d9eb5 3674static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask,
121e6f32
NP
3675 pgprot_t prot, unsigned int page_shift,
3676 int node)
1da177e4 3677{
930f036b 3678 const gfp_t nested_gfp = (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO;
9376130c 3679 bool nofail = gfp_mask & __GFP_NOFAIL;
121e6f32
NP
3680 unsigned long addr = (unsigned long)area->addr;
3681 unsigned long size = get_vm_area_size(area);
34fe6537 3682 unsigned long array_size;
121e6f32
NP
3683 unsigned int nr_small_pages = size >> PAGE_SHIFT;
3684 unsigned int page_order;
451769eb
MH
3685 unsigned int flags;
3686 int ret;
1da177e4 3687
121e6f32 3688 array_size = (unsigned long)nr_small_pages * sizeof(struct page *);
80b1d8fd 3689
f255935b
CH
3690 if (!(gfp_mask & (GFP_DMA | GFP_DMA32)))
3691 gfp_mask |= __GFP_HIGHMEM;
1da177e4 3692
1da177e4 3693 /* Please note that the recursion is strictly bounded. */
8757d5fa 3694 if (array_size > PAGE_SIZE) {
88ae5fb7 3695 area->pages = __vmalloc_node_noprof(array_size, 1, nested_gfp, node,
f255935b 3696 area->caller);
286e1ea3 3697 } else {
88ae5fb7 3698 area->pages = kmalloc_node_noprof(array_size, nested_gfp, node);
286e1ea3 3699 }
7ea36242 3700
5c1f4e69 3701 if (!area->pages) {
c3d77172 3702 warn_alloc(gfp_mask, NULL,
f4bdfeaf
URS
3703 "vmalloc error: size %lu, failed to allocated page array size %lu",
3704 nr_small_pages * PAGE_SIZE, array_size);
cd61413b 3705 free_vm_area(area);
1da177e4
LT
3706 return NULL;
3707 }
1da177e4 3708
121e6f32 3709 set_vm_area_page_order(area, page_shift - PAGE_SHIFT);
121e6f32 3710 page_order = vm_area_page_order(area);
bf53d6f8 3711
7de8728f 3712 /*
6004fe00 3713 * High-order nofail allocations are really expensive and
7de8728f
URS
3714 * potentially dangerous (pre-mature OOM, disruptive reclaim
3715 * and compaction etc.
3716 *
3717 * Please note, the __vmalloc_node_range_noprof() falls-back
3718 * to order-0 pages if high-order attempt is unsuccessful.
3719 */
3720 area->nr_pages = vm_area_alloc_pages((page_order ?
3721 gfp_mask & ~__GFP_NOFAIL : gfp_mask) | __GFP_NOWARN,
c3d77172 3722 node, page_order, nr_small_pages, area->pages);
5c1f4e69 3723
97105f0a 3724 atomic_long_add(area->nr_pages, &nr_vmalloc_pages);
aa8d89d1
SB
3725 /* All pages of vm should be charged to same memcg, so use first one. */
3726 if (gfp_mask & __GFP_ACCOUNT && area->nr_pages)
3727 mod_memcg_page_state(area->pages[0], MEMCG_VMALLOC,
3728 area->nr_pages);
1da177e4 3729
5c1f4e69
URS
3730 /*
3731 * If not enough pages were obtained to accomplish an
f41f036b 3732 * allocation request, free them via vfree() if any.
5c1f4e69
URS
3733 */
3734 if (area->nr_pages != nr_small_pages) {
95a301ee
LS
3735 /*
3736 * vm_area_alloc_pages() can fail due to insufficient memory but
3737 * also:-
3738 *
3739 * - a pending fatal signal
3740 * - insufficient huge page-order pages
3741 *
3742 * Since we always retry allocations at order-0 in the huge page
3743 * case a warning for either is spurious.
3744 */
3745 if (!fatal_signal_pending(current) && page_order == 0)
f349b15e 3746 warn_alloc(gfp_mask, NULL,
95a301ee
LS
3747 "vmalloc error: size %lu, failed to allocate pages",
3748 area->nr_pages * PAGE_SIZE);
5c1f4e69
URS
3749 goto fail;
3750 }
3751
451769eb
MH
3752 /*
3753 * page tables allocations ignore external gfp mask, enforce it
3754 * by the scope API
3755 */
3756 if ((gfp_mask & (__GFP_FS | __GFP_IO)) == __GFP_IO)
3757 flags = memalloc_nofs_save();
3758 else if ((gfp_mask & (__GFP_FS | __GFP_IO)) == 0)
3759 flags = memalloc_noio_save();
3760
9376130c
MH
3761 do {
3762 ret = vmap_pages_range(addr, addr + size, prot, area->pages,
451769eb 3763 page_shift);
9376130c
MH
3764 if (nofail && (ret < 0))
3765 schedule_timeout_uninterruptible(1);
3766 } while (nofail && (ret < 0));
451769eb
MH
3767
3768 if ((gfp_mask & (__GFP_FS | __GFP_IO)) == __GFP_IO)
3769 memalloc_nofs_restore(flags);
3770 else if ((gfp_mask & (__GFP_FS | __GFP_IO)) == 0)
3771 memalloc_noio_restore(flags);
3772
3773 if (ret < 0) {
c3d77172 3774 warn_alloc(gfp_mask, NULL,
f4bdfeaf
URS
3775 "vmalloc error: size %lu, failed to map pages",
3776 area->nr_pages * PAGE_SIZE);
1da177e4 3777 goto fail;
d70bec8c 3778 }
ed1f324c 3779
1da177e4
LT
3780 return area->addr;
3781
3782fail:
f41f036b 3783 vfree(area->addr);
1da177e4
LT
3784 return NULL;
3785}
3786
3787/**
92eac168
MR
3788 * __vmalloc_node_range - allocate virtually contiguous memory
3789 * @size: allocation size
3790 * @align: desired alignment
3791 * @start: vm area range start
3792 * @end: vm area range end
3793 * @gfp_mask: flags for the page level allocator
3794 * @prot: protection mask for the allocated pages
3795 * @vm_flags: additional vm area flags (e.g. %VM_NO_GUARD)
3796 * @node: node to use for allocation or NUMA_NO_NODE
3797 * @caller: caller's return address
3798 *
3799 * Allocate enough pages to cover @size from the page level
b7d90e7a 3800 * allocator with @gfp_mask flags. Please note that the full set of gfp
30d3f011
MH
3801 * flags are not supported. GFP_KERNEL, GFP_NOFS and GFP_NOIO are all
3802 * supported.
3803 * Zone modifiers are not supported. From the reclaim modifiers
3804 * __GFP_DIRECT_RECLAIM is required (aka GFP_NOWAIT is not supported)
3805 * and only __GFP_NOFAIL is supported (i.e. __GFP_NORETRY and
3806 * __GFP_RETRY_MAYFAIL are not supported).
3807 *
3808 * __GFP_NOWARN can be used to suppress failures messages.
b7d90e7a
MH
3809 *
3810 * Map them into contiguous kernel virtual space, using a pagetable
3811 * protection of @prot.
a862f68a
MR
3812 *
3813 * Return: the address of the area or %NULL on failure
1da177e4 3814 */
88ae5fb7 3815void *__vmalloc_node_range_noprof(unsigned long size, unsigned long align,
d0a21265 3816 unsigned long start, unsigned long end, gfp_t gfp_mask,
cb9e3c29
AR
3817 pgprot_t prot, unsigned long vm_flags, int node,
3818 const void *caller)
1da177e4
LT
3819{
3820 struct vm_struct *area;
19f1c3ac 3821 void *ret;
f6e39794 3822 kasan_vmalloc_flags_t kasan_flags = KASAN_VMALLOC_NONE;
f0e11a99 3823 unsigned long original_align = align;
121e6f32 3824 unsigned int shift = PAGE_SHIFT;
1da177e4 3825
d70bec8c
NP
3826 if (WARN_ON_ONCE(!size))
3827 return NULL;
3828
3829 if ((size >> PAGE_SHIFT) > totalram_pages()) {
3830 warn_alloc(gfp_mask, NULL,
f4bdfeaf 3831 "vmalloc error: size %lu, exceeds total pages",
f0e11a99 3832 size);
d70bec8c 3833 return NULL;
121e6f32
NP
3834 }
3835
559089e0 3836 if (vmap_allow_huge && (vm_flags & VM_ALLOW_HUGE_VMAP)) {
121e6f32
NP
3837 /*
3838 * Try huge pages. Only try for PAGE_KERNEL allocations,
3839 * others like modules don't yet expect huge pages in
3840 * their allocations due to apply_to_page_range not
3841 * supporting them.
3842 */
3843
c82be0be 3844 if (arch_vmap_pmd_supported(prot) && size >= PMD_SIZE)
121e6f32 3845 shift = PMD_SHIFT;
3382bbee 3846 else
c82be0be 3847 shift = arch_vmap_pte_supported_shift(size);
3382bbee 3848
f0e11a99 3849 align = max(original_align, 1UL << shift);
121e6f32
NP
3850 }
3851
3852again:
f0e11a99 3853 area = __get_vm_area_node(size, align, shift, VM_ALLOC |
7ca3027b
DA
3854 VM_UNINITIALIZED | vm_flags, start, end, node,
3855 gfp_mask, caller);
d70bec8c 3856 if (!area) {
9376130c 3857 bool nofail = gfp_mask & __GFP_NOFAIL;
d70bec8c 3858 warn_alloc(gfp_mask, NULL,
9376130c 3859 "vmalloc error: size %lu, vm_struct allocation failed%s",
f0e11a99 3860 size, (nofail) ? ". Retrying." : "");
9376130c
MH
3861 if (nofail) {
3862 schedule_timeout_uninterruptible(1);
3863 goto again;
3864 }
de7d2b56 3865 goto fail;
d70bec8c 3866 }
1da177e4 3867
f6e39794
AK
3868 /*
3869 * Prepare arguments for __vmalloc_area_node() and
3870 * kasan_unpoison_vmalloc().
3871 */
3872 if (pgprot_val(prot) == pgprot_val(PAGE_KERNEL)) {
3873 if (kasan_hw_tags_enabled()) {
3874 /*
3875 * Modify protection bits to allow tagging.
3876 * This must be done before mapping.
3877 */
3878 prot = arch_vmap_pgprot_tagged(prot);
01d92c7f 3879
f6e39794
AK
3880 /*
3881 * Skip page_alloc poisoning and zeroing for physical
3882 * pages backing VM_ALLOC mapping. Memory is instead
3883 * poisoned and zeroed by kasan_unpoison_vmalloc().
3884 */
0a54864f 3885 gfp_mask |= __GFP_SKIP_KASAN | __GFP_SKIP_ZERO;
f6e39794
AK
3886 }
3887
3888 /* Take note that the mapping is PAGE_KERNEL. */
3889 kasan_flags |= KASAN_VMALLOC_PROT_NORMAL;
23689e91
AK
3890 }
3891
01d92c7f 3892 /* Allocate physical pages and map them into vmalloc space. */
19f1c3ac
AK
3893 ret = __vmalloc_area_node(area, gfp_mask, prot, shift, node);
3894 if (!ret)
121e6f32 3895 goto fail;
89219d37 3896
23689e91
AK
3897 /*
3898 * Mark the pages as accessible, now that they are mapped.
6c2f761d
AK
3899 * The condition for setting KASAN_VMALLOC_INIT should complement the
3900 * one in post_alloc_hook() with regards to the __GFP_SKIP_ZERO check
3901 * to make sure that memory is initialized under the same conditions.
f6e39794
AK
3902 * Tag-based KASAN modes only assign tags to normal non-executable
3903 * allocations, see __kasan_unpoison_vmalloc().
23689e91 3904 */
f6e39794 3905 kasan_flags |= KASAN_VMALLOC_VM_ALLOC;
6c2f761d
AK
3906 if (!want_init_on_free() && want_init_on_alloc(gfp_mask) &&
3907 (gfp_mask & __GFP_SKIP_ZERO))
23689e91 3908 kasan_flags |= KASAN_VMALLOC_INIT;
f6e39794 3909 /* KASAN_VMALLOC_PROT_NORMAL already set if required. */
f0e11a99 3910 area->addr = kasan_unpoison_vmalloc(area->addr, size, kasan_flags);
19f1c3ac 3911
f5252e00 3912 /*
20fc02b4
ZY
3913 * In this function, newly allocated vm_struct has VM_UNINITIALIZED
3914 * flag. It means that vm_struct is not fully initialized.
4341fa45 3915 * Now, it is fully initialized, so remove this flag here.
f5252e00 3916 */
20fc02b4 3917 clear_vm_uninitialized_flag(area);
f5252e00 3918
60115fa5 3919 if (!(vm_flags & VM_DEFER_KMEMLEAK))
f0e11a99 3920 kmemleak_vmalloc(area, PAGE_ALIGN(size), gfp_mask);
89219d37 3921
19f1c3ac 3922 return area->addr;
de7d2b56
JP
3923
3924fail:
121e6f32
NP
3925 if (shift > PAGE_SHIFT) {
3926 shift = PAGE_SHIFT;
f0e11a99 3927 align = original_align;
121e6f32
NP
3928 goto again;
3929 }
3930
de7d2b56 3931 return NULL;
1da177e4
LT
3932}
3933
d0a21265 3934/**
92eac168
MR
3935 * __vmalloc_node - allocate virtually contiguous memory
3936 * @size: allocation size
3937 * @align: desired alignment
3938 * @gfp_mask: flags for the page level allocator
92eac168
MR
3939 * @node: node to use for allocation or NUMA_NO_NODE
3940 * @caller: caller's return address
a7c3e901 3941 *
f38fcb9c
CH
3942 * Allocate enough pages to cover @size from the page level allocator with
3943 * @gfp_mask flags. Map them into contiguous kernel virtual space.
a7c3e901 3944 *
92eac168
MR
3945 * Reclaim modifiers in @gfp_mask - __GFP_NORETRY, __GFP_RETRY_MAYFAIL
3946 * and __GFP_NOFAIL are not supported
a7c3e901 3947 *
92eac168
MR
3948 * Any use of gfp flags outside of GFP_KERNEL should be consulted
3949 * with mm people.
a862f68a
MR
3950 *
3951 * Return: pointer to the allocated memory or %NULL on error
d0a21265 3952 */
88ae5fb7 3953void *__vmalloc_node_noprof(unsigned long size, unsigned long align,
f38fcb9c 3954 gfp_t gfp_mask, int node, const void *caller)
d0a21265 3955{
88ae5fb7 3956 return __vmalloc_node_range_noprof(size, align, VMALLOC_START, VMALLOC_END,
f38fcb9c 3957 gfp_mask, PAGE_KERNEL, 0, node, caller);
d0a21265 3958}
c3f896dc
CH
3959/*
3960 * This is only for performance analysis of vmalloc and stress purpose.
3961 * It is required by vmalloc test module, therefore do not use it other
3962 * than that.
3963 */
3964#ifdef CONFIG_TEST_VMALLOC_MODULE
88ae5fb7 3965EXPORT_SYMBOL_GPL(__vmalloc_node_noprof);
c3f896dc 3966#endif
d0a21265 3967
88ae5fb7 3968void *__vmalloc_noprof(unsigned long size, gfp_t gfp_mask)
930fc45a 3969{
88ae5fb7 3970 return __vmalloc_node_noprof(size, 1, gfp_mask, NUMA_NO_NODE,
23016969 3971 __builtin_return_address(0));
930fc45a 3972}
88ae5fb7 3973EXPORT_SYMBOL(__vmalloc_noprof);
1da177e4
LT
3974
3975/**
92eac168
MR
3976 * vmalloc - allocate virtually contiguous memory
3977 * @size: allocation size
3978 *
3979 * Allocate enough pages to cover @size from the page level
3980 * allocator and map them into contiguous kernel virtual space.
1da177e4 3981 *
92eac168
MR
3982 * For tight control over page level allocator and protection flags
3983 * use __vmalloc() instead.
a862f68a
MR
3984 *
3985 * Return: pointer to the allocated memory or %NULL on error
1da177e4 3986 */
88ae5fb7 3987void *vmalloc_noprof(unsigned long size)
1da177e4 3988{
88ae5fb7 3989 return __vmalloc_node_noprof(size, 1, GFP_KERNEL, NUMA_NO_NODE,
4d39d728 3990 __builtin_return_address(0));
1da177e4 3991}
88ae5fb7 3992EXPORT_SYMBOL(vmalloc_noprof);
1da177e4 3993
15a64f5a 3994/**
55284f70 3995 * vmalloc_huge_node - allocate virtually contiguous memory, allow huge pages
559089e0
SL
3996 * @size: allocation size
3997 * @gfp_mask: flags for the page level allocator
55284f70 3998 * @node: node to use for allocation or NUMA_NO_NODE
15a64f5a 3999 *
559089e0 4000 * Allocate enough pages to cover @size from the page level
15a64f5a 4001 * allocator and map them into contiguous kernel virtual space.
559089e0
SL
4002 * If @size is greater than or equal to PMD_SIZE, allow using
4003 * huge pages for the memory
15a64f5a
CI
4004 *
4005 * Return: pointer to the allocated memory or %NULL on error
4006 */
55284f70 4007void *vmalloc_huge_node_noprof(unsigned long size, gfp_t gfp_mask, int node)
15a64f5a 4008{
88ae5fb7 4009 return __vmalloc_node_range_noprof(size, 1, VMALLOC_START, VMALLOC_END,
55284f70
PZ
4010 gfp_mask, PAGE_KERNEL, VM_ALLOW_HUGE_VMAP,
4011 node, __builtin_return_address(0));
15a64f5a 4012}
55284f70 4013EXPORT_SYMBOL_GPL(vmalloc_huge_node_noprof);
15a64f5a 4014
e1ca7788 4015/**
92eac168
MR
4016 * vzalloc - allocate virtually contiguous memory with zero fill
4017 * @size: allocation size
4018 *
4019 * Allocate enough pages to cover @size from the page level
4020 * allocator and map them into contiguous kernel virtual space.
4021 * The memory allocated is set to zero.
4022 *
4023 * For tight control over page level allocator and protection flags
4024 * use __vmalloc() instead.
a862f68a
MR
4025 *
4026 * Return: pointer to the allocated memory or %NULL on error
e1ca7788 4027 */
88ae5fb7 4028void *vzalloc_noprof(unsigned long size)
e1ca7788 4029{
88ae5fb7 4030 return __vmalloc_node_noprof(size, 1, GFP_KERNEL | __GFP_ZERO, NUMA_NO_NODE,
4d39d728 4031 __builtin_return_address(0));
e1ca7788 4032}
88ae5fb7 4033EXPORT_SYMBOL(vzalloc_noprof);
e1ca7788 4034
83342314 4035/**
ead04089
REB
4036 * vmalloc_user - allocate zeroed virtually contiguous memory for userspace
4037 * @size: allocation size
83342314 4038 *
ead04089
REB
4039 * The resulting memory area is zeroed so it can be mapped to userspace
4040 * without leaking data.
a862f68a
MR
4041 *
4042 * Return: pointer to the allocated memory or %NULL on error
83342314 4043 */
88ae5fb7 4044void *vmalloc_user_noprof(unsigned long size)
83342314 4045{
88ae5fb7 4046 return __vmalloc_node_range_noprof(size, SHMLBA, VMALLOC_START, VMALLOC_END,
bc84c535
RP
4047 GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL,
4048 VM_USERMAP, NUMA_NO_NODE,
4049 __builtin_return_address(0));
83342314 4050}
88ae5fb7 4051EXPORT_SYMBOL(vmalloc_user_noprof);
83342314 4052
930fc45a 4053/**
92eac168
MR
4054 * vmalloc_node - allocate memory on a specific node
4055 * @size: allocation size
4056 * @node: numa node
930fc45a 4057 *
92eac168
MR
4058 * Allocate enough pages to cover @size from the page level
4059 * allocator and map them into contiguous kernel virtual space.
930fc45a 4060 *
92eac168
MR
4061 * For tight control over page level allocator and protection flags
4062 * use __vmalloc() instead.
a862f68a
MR
4063 *
4064 * Return: pointer to the allocated memory or %NULL on error
930fc45a 4065 */
88ae5fb7 4066void *vmalloc_node_noprof(unsigned long size, int node)
930fc45a 4067{
88ae5fb7 4068 return __vmalloc_node_noprof(size, 1, GFP_KERNEL, node,
f38fcb9c 4069 __builtin_return_address(0));
930fc45a 4070}
88ae5fb7 4071EXPORT_SYMBOL(vmalloc_node_noprof);
930fc45a 4072
e1ca7788
DY
4073/**
4074 * vzalloc_node - allocate memory on a specific node with zero fill
4075 * @size: allocation size
4076 * @node: numa node
4077 *
4078 * Allocate enough pages to cover @size from the page level
4079 * allocator and map them into contiguous kernel virtual space.
4080 * The memory allocated is set to zero.
4081 *
a862f68a 4082 * Return: pointer to the allocated memory or %NULL on error
e1ca7788 4083 */
88ae5fb7 4084void *vzalloc_node_noprof(unsigned long size, int node)
e1ca7788 4085{
88ae5fb7 4086 return __vmalloc_node_noprof(size, 1, GFP_KERNEL | __GFP_ZERO, node,
4d39d728 4087 __builtin_return_address(0));
e1ca7788 4088}
88ae5fb7 4089EXPORT_SYMBOL(vzalloc_node_noprof);
e1ca7788 4090
3ddc2fef
DK
4091/**
4092 * vrealloc - reallocate virtually contiguous memory; contents remain unchanged
4093 * @p: object to reallocate memory for
4094 * @size: the size to reallocate
4095 * @flags: the flags for the page level allocator
4096 *
4097 * If @p is %NULL, vrealloc() behaves exactly like vmalloc(). If @size is 0 and
4098 * @p is not a %NULL pointer, the object pointed to is freed.
4099 *
4100 * If __GFP_ZERO logic is requested, callers must ensure that, starting with the
4101 * initial memory allocation, every subsequent call to this API for the same
4102 * memory allocation is flagged with __GFP_ZERO. Otherwise, it is possible that
4103 * __GFP_ZERO is not fully honored by this API.
4104 *
4105 * In any case, the contents of the object pointed to are preserved up to the
4106 * lesser of the new and old sizes.
4107 *
4108 * This function must not be called concurrently with itself or vfree() for the
4109 * same memory allocation.
4110 *
4111 * Return: pointer to the allocated memory; %NULL if @size is zero or in case of
4112 * failure
4113 */
4114void *vrealloc_noprof(const void *p, size_t size, gfp_t flags)
4115{
a0309faf
KC
4116 struct vm_struct *vm = NULL;
4117 size_t alloced_size = 0;
3ddc2fef
DK
4118 size_t old_size = 0;
4119 void *n;
4120
4121 if (!size) {
4122 vfree(p);
4123 return NULL;
4124 }
4125
4126 if (p) {
3ddc2fef
DK
4127 vm = find_vm_area(p);
4128 if (unlikely(!vm)) {
4129 WARN(1, "Trying to vrealloc() nonexistent vm area (%p)\n", p);
4130 return NULL;
4131 }
4132
a0309faf
KC
4133 alloced_size = get_vm_area_size(vm);
4134 old_size = vm->requested_size;
4135 if (WARN(alloced_size < old_size,
4136 "vrealloc() has mismatched area vs requested sizes (%p)\n", p))
4137 return NULL;
3ddc2fef
DK
4138 }
4139
4140 /*
4141 * TODO: Shrink the vm_area, i.e. unmap and free unused pages. What
4142 * would be a good heuristic for when to shrink the vm_area?
4143 */
4144 if (size <= old_size) {
70d1eb03
KC
4145 /* Zero out "freed" memory, potentially for future realloc. */
4146 if (want_init_on_free() || want_init_on_alloc(flags))
3ddc2fef 4147 memset((void *)p + size, 0, old_size - size);
a0309faf 4148 vm->requested_size = size;
d699440f 4149 kasan_poison_vmalloc(p + size, old_size - size);
3ddc2fef
DK
4150 return (void *)p;
4151 }
4152
a0309faf
KC
4153 /*
4154 * We already have the bytes available in the allocation; use them.
4155 */
4156 if (size <= alloced_size) {
4157 kasan_unpoison_vmalloc(p + old_size, size - old_size,
4158 KASAN_VMALLOC_PROT_NORMAL);
70d1eb03
KC
4159 /*
4160 * No need to zero memory here, as unused memory will have
4161 * already been zeroed at initial allocation time or during
4162 * realloc shrink time.
4163 */
a0309faf 4164 vm->requested_size = size;
f7a35a3c 4165 return (void *)p;
a0309faf
KC
4166 }
4167
3ddc2fef
DK
4168 /* TODO: Grow the vm_area, i.e. allocate and map additional pages. */
4169 n = __vmalloc_noprof(size, flags);
4170 if (!n)
4171 return NULL;
4172
4173 if (p) {
4174 memcpy(n, p, old_size);
4175 vfree(p);
4176 }
4177
4178 return n;
4179}
4180
0d08e0d3 4181#if defined(CONFIG_64BIT) && defined(CONFIG_ZONE_DMA32)
698d0831 4182#define GFP_VMALLOC32 (GFP_DMA32 | GFP_KERNEL)
0d08e0d3 4183#elif defined(CONFIG_64BIT) && defined(CONFIG_ZONE_DMA)
698d0831 4184#define GFP_VMALLOC32 (GFP_DMA | GFP_KERNEL)
0d08e0d3 4185#else
698d0831
MH
4186/*
4187 * 64b systems should always have either DMA or DMA32 zones. For others
4188 * GFP_DMA32 should do the right thing and use the normal zone.
4189 */
68d68ff6 4190#define GFP_VMALLOC32 (GFP_DMA32 | GFP_KERNEL)
0d08e0d3
AK
4191#endif
4192
1da177e4 4193/**
92eac168
MR
4194 * vmalloc_32 - allocate virtually contiguous memory (32bit addressable)
4195 * @size: allocation size
1da177e4 4196 *
92eac168
MR
4197 * Allocate enough 32bit PA addressable pages to cover @size from the
4198 * page level allocator and map them into contiguous kernel virtual space.
a862f68a
MR
4199 *
4200 * Return: pointer to the allocated memory or %NULL on error
1da177e4 4201 */
88ae5fb7 4202void *vmalloc_32_noprof(unsigned long size)
1da177e4 4203{
88ae5fb7 4204 return __vmalloc_node_noprof(size, 1, GFP_VMALLOC32, NUMA_NO_NODE,
f38fcb9c 4205 __builtin_return_address(0));
1da177e4 4206}
88ae5fb7 4207EXPORT_SYMBOL(vmalloc_32_noprof);
1da177e4 4208
83342314 4209/**
ead04089 4210 * vmalloc_32_user - allocate zeroed virtually contiguous 32bit memory
92eac168 4211 * @size: allocation size
ead04089
REB
4212 *
4213 * The resulting memory area is 32bit addressable and zeroed so it can be
4214 * mapped to userspace without leaking data.
a862f68a
MR
4215 *
4216 * Return: pointer to the allocated memory or %NULL on error
83342314 4217 */
88ae5fb7 4218void *vmalloc_32_user_noprof(unsigned long size)
83342314 4219{
88ae5fb7 4220 return __vmalloc_node_range_noprof(size, SHMLBA, VMALLOC_START, VMALLOC_END,
bc84c535
RP
4221 GFP_VMALLOC32 | __GFP_ZERO, PAGE_KERNEL,
4222 VM_USERMAP, NUMA_NO_NODE,
4223 __builtin_return_address(0));
83342314 4224}
88ae5fb7 4225EXPORT_SYMBOL(vmalloc_32_user_noprof);
83342314 4226
d0107eb0 4227/*
4c91c07c
LS
4228 * Atomically zero bytes in the iterator.
4229 *
4230 * Returns the number of zeroed bytes.
d0107eb0 4231 */
4c91c07c
LS
4232static size_t zero_iter(struct iov_iter *iter, size_t count)
4233{
4234 size_t remains = count;
4235
4236 while (remains > 0) {
4237 size_t num, copied;
4238
0e4bc271 4239 num = min_t(size_t, remains, PAGE_SIZE);
4c91c07c
LS
4240 copied = copy_page_to_iter_nofault(ZERO_PAGE(0), 0, num, iter);
4241 remains -= copied;
4242
4243 if (copied < num)
4244 break;
4245 }
d0107eb0 4246
4c91c07c
LS
4247 return count - remains;
4248}
4249
4250/*
4251 * small helper routine, copy contents to iter from addr.
4252 * If the page is not present, fill zero.
4253 *
4254 * Returns the number of copied bytes.
4255 */
4256static size_t aligned_vread_iter(struct iov_iter *iter,
4257 const char *addr, size_t count)
d0107eb0 4258{
4c91c07c
LS
4259 size_t remains = count;
4260 struct page *page;
d0107eb0 4261
4c91c07c 4262 while (remains > 0) {
d0107eb0 4263 unsigned long offset, length;
4c91c07c 4264 size_t copied = 0;
d0107eb0 4265
891c49ab 4266 offset = offset_in_page(addr);
d0107eb0 4267 length = PAGE_SIZE - offset;
4c91c07c
LS
4268 if (length > remains)
4269 length = remains;
4270 page = vmalloc_to_page(addr);
d0107eb0 4271 /*
4c91c07c
LS
4272 * To do safe access to this _mapped_ area, we need lock. But
4273 * adding lock here means that we need to add overhead of
4274 * vmalloc()/vfree() calls for this _debug_ interface, rarely
4275 * used. Instead of that, we'll use an local mapping via
4276 * copy_page_to_iter_nofault() and accept a small overhead in
4277 * this access function.
d0107eb0 4278 */
4c91c07c
LS
4279 if (page)
4280 copied = copy_page_to_iter_nofault(page, offset,
4281 length, iter);
4282 else
4283 copied = zero_iter(iter, length);
d0107eb0 4284
4c91c07c
LS
4285 addr += copied;
4286 remains -= copied;
4287
4288 if (copied != length)
4289 break;
d0107eb0 4290 }
4c91c07c
LS
4291
4292 return count - remains;
d0107eb0
KH
4293}
4294
4c91c07c
LS
4295/*
4296 * Read from a vm_map_ram region of memory.
4297 *
4298 * Returns the number of copied bytes.
4299 */
4300static size_t vmap_ram_vread_iter(struct iov_iter *iter, const char *addr,
4301 size_t count, unsigned long flags)
06c89946
BH
4302{
4303 char *start;
4304 struct vmap_block *vb;
062eacf5 4305 struct xarray *xa;
06c89946 4306 unsigned long offset;
4c91c07c
LS
4307 unsigned int rs, re;
4308 size_t remains, n;
06c89946
BH
4309
4310 /*
4311 * If it's area created by vm_map_ram() interface directly, but
4312 * not further subdividing and delegating management to vmap_block,
4313 * handle it here.
4314 */
4c91c07c
LS
4315 if (!(flags & VMAP_BLOCK))
4316 return aligned_vread_iter(iter, addr, count);
4317
4318 remains = count;
06c89946
BH
4319
4320 /*
4321 * Area is split into regions and tracked with vmap_block, read out
4322 * each region and zero fill the hole between regions.
4323 */
fa1c77c1 4324 xa = addr_to_vb_xa((unsigned long) addr);
062eacf5 4325 vb = xa_load(xa, addr_to_vb_idx((unsigned long)addr));
06c89946 4326 if (!vb)
4c91c07c 4327 goto finished_zero;
06c89946
BH
4328
4329 spin_lock(&vb->lock);
4330 if (bitmap_empty(vb->used_map, VMAP_BBMAP_BITS)) {
4331 spin_unlock(&vb->lock);
4c91c07c 4332 goto finished_zero;
06c89946 4333 }
4c91c07c 4334
06c89946 4335 for_each_set_bitrange(rs, re, vb->used_map, VMAP_BBMAP_BITS) {
4c91c07c
LS
4336 size_t copied;
4337
4338 if (remains == 0)
4339 goto finished;
4340
06c89946 4341 start = vmap_block_vaddr(vb->va->va_start, rs);
4c91c07c
LS
4342
4343 if (addr < start) {
4344 size_t to_zero = min_t(size_t, start - addr, remains);
4345 size_t zeroed = zero_iter(iter, to_zero);
4346
4347 addr += zeroed;
4348 remains -= zeroed;
4349
4350 if (remains == 0 || zeroed != to_zero)
4351 goto finished;
06c89946 4352 }
4c91c07c 4353
06c89946
BH
4354 /*it could start reading from the middle of used region*/
4355 offset = offset_in_page(addr);
4356 n = ((re - rs + 1) << PAGE_SHIFT) - offset;
4c91c07c
LS
4357 if (n > remains)
4358 n = remains;
4359
4360 copied = aligned_vread_iter(iter, start + offset, n);
06c89946 4361
4c91c07c
LS
4362 addr += copied;
4363 remains -= copied;
4364
4365 if (copied != n)
4366 goto finished;
06c89946 4367 }
4c91c07c 4368
06c89946
BH
4369 spin_unlock(&vb->lock);
4370
4c91c07c 4371finished_zero:
06c89946 4372 /* zero-fill the left dirty or free regions */
4c91c07c
LS
4373 return count - remains + zero_iter(iter, remains);
4374finished:
4375 /* We couldn't copy/zero everything */
4376 spin_unlock(&vb->lock);
4377 return count - remains;
06c89946
BH
4378}
4379
d0107eb0 4380/**
4c91c07c
LS
4381 * vread_iter() - read vmalloc area in a safe way to an iterator.
4382 * @iter: the iterator to which data should be written.
4383 * @addr: vm address.
4384 * @count: number of bytes to be read.
92eac168 4385 *
92eac168
MR
4386 * This function checks that addr is a valid vmalloc'ed area, and
4387 * copy data from that area to a given buffer. If the given memory range
4388 * of [addr...addr+count) includes some valid address, data is copied to
4389 * proper area of @buf. If there are memory holes, they'll be zero-filled.
4390 * IOREMAP area is treated as memory hole and no copy is done.
4391 *
4392 * If [addr...addr+count) doesn't includes any intersects with alive
4393 * vm_struct area, returns 0. @buf should be kernel's buffer.
4394 *
4395 * Note: In usual ops, vread() is never necessary because the caller
4396 * should know vmalloc() area is valid and can use memcpy().
4397 * This is for routines which have to access vmalloc area without
bbcd53c9 4398 * any information, as /proc/kcore.
a862f68a
MR
4399 *
4400 * Return: number of bytes for which addr and buf should be increased
4401 * (same number as @count) or %0 if [addr...addr+count) doesn't
4402 * include any intersection with valid vmalloc area
d0107eb0 4403 */
4c91c07c 4404long vread_iter(struct iov_iter *iter, const char *addr, size_t count)
1da177e4 4405{
d0936029 4406 struct vmap_node *vn;
e81ce85f
JK
4407 struct vmap_area *va;
4408 struct vm_struct *vm;
4c91c07c
LS
4409 char *vaddr;
4410 size_t n, size, flags, remains;
53becf32 4411 unsigned long next;
1da177e4 4412
4aff1dc4
AK
4413 addr = kasan_reset_tag(addr);
4414
1da177e4
LT
4415 /* Don't allow overflow */
4416 if ((unsigned long) addr + count < count)
4417 count = -(unsigned long) addr;
4418
4c91c07c
LS
4419 remains = count;
4420
53becf32
URS
4421 vn = find_vmap_area_exceed_addr_lock((unsigned long) addr, &va);
4422 if (!vn)
4c91c07c 4423 goto finished_zero;
f181234a
CW
4424
4425 /* no intersects with alive vmap_area */
4c91c07c
LS
4426 if ((unsigned long)addr + remains <= va->va_start)
4427 goto finished_zero;
f181234a 4428
53becf32 4429 do {
4c91c07c
LS
4430 size_t copied;
4431
4432 if (remains == 0)
4433 goto finished;
e81ce85f 4434
06c89946
BH
4435 vm = va->vm;
4436 flags = va->flags & VMAP_FLAGS_MASK;
4437 /*
4438 * VMAP_BLOCK indicates a sub-type of vm_map_ram area, need
4439 * be set together with VMAP_RAM.
4440 */
4441 WARN_ON(flags == VMAP_BLOCK);
4442
4443 if (!vm && !flags)
53becf32 4444 goto next_va;
e81ce85f 4445
30a7a9b1 4446 if (vm && (vm->flags & VM_UNINITIALIZED))
53becf32 4447 goto next_va;
4c91c07c 4448
30a7a9b1
BH
4449 /* Pair with smp_wmb() in clear_vm_uninitialized_flag() */
4450 smp_rmb();
4451
06c89946
BH
4452 vaddr = (char *) va->va_start;
4453 size = vm ? get_vm_area_size(vm) : va_size(va);
4454
4455 if (addr >= vaddr + size)
53becf32 4456 goto next_va;
4c91c07c
LS
4457
4458 if (addr < vaddr) {
4459 size_t to_zero = min_t(size_t, vaddr - addr, remains);
4460 size_t zeroed = zero_iter(iter, to_zero);
4461
4462 addr += zeroed;
4463 remains -= zeroed;
4464
4465 if (remains == 0 || zeroed != to_zero)
1da177e4 4466 goto finished;
1da177e4 4467 }
4c91c07c 4468
06c89946 4469 n = vaddr + size - addr;
4c91c07c
LS
4470 if (n > remains)
4471 n = remains;
06c89946
BH
4472
4473 if (flags & VMAP_RAM)
4c91c07c 4474 copied = vmap_ram_vread_iter(iter, addr, n, flags);
e6f79822 4475 else if (!(vm && (vm->flags & (VM_IOREMAP | VM_SPARSE))))
4c91c07c 4476 copied = aligned_vread_iter(iter, addr, n);
e6f79822 4477 else /* IOREMAP | SPARSE area is treated as memory hole */
4c91c07c
LS
4478 copied = zero_iter(iter, n);
4479
4480 addr += copied;
4481 remains -= copied;
4482
4483 if (copied != n)
4484 goto finished;
53becf32
URS
4485
4486 next_va:
4487 next = va->va_end;
4488 spin_unlock(&vn->busy.lock);
4489 } while ((vn = find_vmap_area_exceed_addr_lock(next, &va)));
d0107eb0 4490
4c91c07c 4491finished_zero:
53becf32
URS
4492 if (vn)
4493 spin_unlock(&vn->busy.lock);
4494
d0107eb0 4495 /* zero-fill memory holes */
4c91c07c
LS
4496 return count - remains + zero_iter(iter, remains);
4497finished:
4498 /* Nothing remains, or We couldn't copy/zero everything. */
53becf32
URS
4499 if (vn)
4500 spin_unlock(&vn->busy.lock);
d0107eb0 4501
4c91c07c 4502 return count - remains;
1da177e4
LT
4503}
4504
83342314 4505/**
92eac168
MR
4506 * remap_vmalloc_range_partial - map vmalloc pages to userspace
4507 * @vma: vma to cover
4508 * @uaddr: target user address to start at
4509 * @kaddr: virtual address of vmalloc kernel memory
bdebd6a2 4510 * @pgoff: offset from @kaddr to start at
92eac168 4511 * @size: size of map area
7682486b 4512 *
92eac168 4513 * Returns: 0 for success, -Exxx on failure
83342314 4514 *
92eac168
MR
4515 * This function checks that @kaddr is a valid vmalloc'ed area,
4516 * and that it is big enough to cover the range starting at
4517 * @uaddr in @vma. Will return failure if that criteria isn't
4518 * met.
83342314 4519 *
92eac168 4520 * Similar to remap_pfn_range() (see mm/memory.c)
83342314 4521 */
e69e9d4a 4522int remap_vmalloc_range_partial(struct vm_area_struct *vma, unsigned long uaddr,
bdebd6a2
JH
4523 void *kaddr, unsigned long pgoff,
4524 unsigned long size)
83342314
NP
4525{
4526 struct vm_struct *area;
bdebd6a2
JH
4527 unsigned long off;
4528 unsigned long end_index;
4529
4530 if (check_shl_overflow(pgoff, PAGE_SHIFT, &off))
4531 return -EINVAL;
83342314 4532
e69e9d4a
HD
4533 size = PAGE_ALIGN(size);
4534
4535 if (!PAGE_ALIGNED(uaddr) || !PAGE_ALIGNED(kaddr))
83342314
NP
4536 return -EINVAL;
4537
e69e9d4a 4538 area = find_vm_area(kaddr);
83342314 4539 if (!area)
db64fe02 4540 return -EINVAL;
83342314 4541
fe9041c2 4542 if (!(area->flags & (VM_USERMAP | VM_DMA_COHERENT)))
db64fe02 4543 return -EINVAL;
83342314 4544
bdebd6a2
JH
4545 if (check_add_overflow(size, off, &end_index) ||
4546 end_index > get_vm_area_size(area))
db64fe02 4547 return -EINVAL;
bdebd6a2 4548 kaddr += off;
83342314 4549
83342314 4550 do {
e69e9d4a 4551 struct page *page = vmalloc_to_page(kaddr);
db64fe02
NP
4552 int ret;
4553
83342314
NP
4554 ret = vm_insert_page(vma, uaddr, page);
4555 if (ret)
4556 return ret;
4557
4558 uaddr += PAGE_SIZE;
e69e9d4a
HD
4559 kaddr += PAGE_SIZE;
4560 size -= PAGE_SIZE;
4561 } while (size > 0);
83342314 4562
1c71222e 4563 vm_flags_set(vma, VM_DONTEXPAND | VM_DONTDUMP);
83342314 4564
db64fe02 4565 return 0;
83342314 4566}
e69e9d4a
HD
4567
4568/**
92eac168
MR
4569 * remap_vmalloc_range - map vmalloc pages to userspace
4570 * @vma: vma to cover (map full range of vma)
4571 * @addr: vmalloc memory
4572 * @pgoff: number of pages into addr before first page to map
e69e9d4a 4573 *
92eac168 4574 * Returns: 0 for success, -Exxx on failure
e69e9d4a 4575 *
92eac168
MR
4576 * This function checks that addr is a valid vmalloc'ed area, and
4577 * that it is big enough to cover the vma. Will return failure if
4578 * that criteria isn't met.
e69e9d4a 4579 *
92eac168 4580 * Similar to remap_pfn_range() (see mm/memory.c)
e69e9d4a
HD
4581 */
4582int remap_vmalloc_range(struct vm_area_struct *vma, void *addr,
4583 unsigned long pgoff)
4584{
4585 return remap_vmalloc_range_partial(vma, vma->vm_start,
bdebd6a2 4586 addr, pgoff,
e69e9d4a
HD
4587 vma->vm_end - vma->vm_start);
4588}
83342314
NP
4589EXPORT_SYMBOL(remap_vmalloc_range);
4590
5f4352fb
JF
4591void free_vm_area(struct vm_struct *area)
4592{
4593 struct vm_struct *ret;
4594 ret = remove_vm_area(area->addr);
4595 BUG_ON(ret != area);
4596 kfree(area);
4597}
4598EXPORT_SYMBOL_GPL(free_vm_area);
a10aa579 4599
4f8b02b4 4600#ifdef CONFIG_SMP
ca23e405
TH
4601static struct vmap_area *node_to_va(struct rb_node *n)
4602{
4583e773 4603 return rb_entry_safe(n, struct vmap_area, rb_node);
ca23e405
TH
4604}
4605
4606/**
68ad4a33
URS
4607 * pvm_find_va_enclose_addr - find the vmap_area @addr belongs to
4608 * @addr: target address
ca23e405 4609 *
68ad4a33
URS
4610 * Returns: vmap_area if it is found. If there is no such area
4611 * the first highest(reverse order) vmap_area is returned
4612 * i.e. va->va_start < addr && va->va_end < addr or NULL
4613 * if there are no any areas before @addr.
ca23e405 4614 */
68ad4a33
URS
4615static struct vmap_area *
4616pvm_find_va_enclose_addr(unsigned long addr)
ca23e405 4617{
68ad4a33
URS
4618 struct vmap_area *va, *tmp;
4619 struct rb_node *n;
4620
4621 n = free_vmap_area_root.rb_node;
4622 va = NULL;
ca23e405
TH
4623
4624 while (n) {
68ad4a33
URS
4625 tmp = rb_entry(n, struct vmap_area, rb_node);
4626 if (tmp->va_start <= addr) {
4627 va = tmp;
4628 if (tmp->va_end >= addr)
4629 break;
4630
ca23e405 4631 n = n->rb_right;
68ad4a33
URS
4632 } else {
4633 n = n->rb_left;
4634 }
ca23e405
TH
4635 }
4636
68ad4a33 4637 return va;
ca23e405
TH
4638}
4639
4640/**
68ad4a33
URS
4641 * pvm_determine_end_from_reverse - find the highest aligned address
4642 * of free block below VMALLOC_END
4643 * @va:
4644 * in - the VA we start the search(reverse order);
4645 * out - the VA with the highest aligned end address.
799fa85d 4646 * @align: alignment for required highest address
ca23e405 4647 *
68ad4a33 4648 * Returns: determined end address within vmap_area
ca23e405 4649 */
68ad4a33
URS
4650static unsigned long
4651pvm_determine_end_from_reverse(struct vmap_area **va, unsigned long align)
ca23e405 4652{
68ad4a33 4653 unsigned long vmalloc_end = VMALLOC_END & ~(align - 1);
ca23e405
TH
4654 unsigned long addr;
4655
68ad4a33
URS
4656 if (likely(*va)) {
4657 list_for_each_entry_from_reverse((*va),
4658 &free_vmap_area_list, list) {
4659 addr = min((*va)->va_end & ~(align - 1), vmalloc_end);
4660 if ((*va)->va_start < addr)
4661 return addr;
4662 }
ca23e405
TH
4663 }
4664
68ad4a33 4665 return 0;
ca23e405
TH
4666}
4667
4668/**
4669 * pcpu_get_vm_areas - allocate vmalloc areas for percpu allocator
4670 * @offsets: array containing offset of each area
4671 * @sizes: array containing size of each area
4672 * @nr_vms: the number of areas to allocate
4673 * @align: alignment, all entries in @offsets and @sizes must be aligned to this
ca23e405
TH
4674 *
4675 * Returns: kmalloc'd vm_struct pointer array pointing to allocated
4676 * vm_structs on success, %NULL on failure
4677 *
4678 * Percpu allocator wants to use congruent vm areas so that it can
4679 * maintain the offsets among percpu areas. This function allocates
ec3f64fc
DR
4680 * congruent vmalloc areas for it with GFP_KERNEL. These areas tend to
4681 * be scattered pretty far, distance between two areas easily going up
4682 * to gigabytes. To avoid interacting with regular vmallocs, these
4683 * areas are allocated from top.
ca23e405 4684 *
68ad4a33
URS
4685 * Despite its complicated look, this allocator is rather simple. It
4686 * does everything top-down and scans free blocks from the end looking
4687 * for matching base. While scanning, if any of the areas do not fit the
4688 * base address is pulled down to fit the area. Scanning is repeated till
4689 * all the areas fit and then all necessary data structures are inserted
4690 * and the result is returned.
ca23e405
TH
4691 */
4692struct vm_struct **pcpu_get_vm_areas(const unsigned long *offsets,
4693 const size_t *sizes, int nr_vms,
ec3f64fc 4694 size_t align)
ca23e405
TH
4695{
4696 const unsigned long vmalloc_start = ALIGN(VMALLOC_START, align);
4697 const unsigned long vmalloc_end = VMALLOC_END & ~(align - 1);
68ad4a33 4698 struct vmap_area **vas, *va;
ca23e405
TH
4699 struct vm_struct **vms;
4700 int area, area2, last_area, term_area;
253a496d 4701 unsigned long base, start, size, end, last_end, orig_start, orig_end;
ca23e405
TH
4702 bool purged = false;
4703
ca23e405 4704 /* verify parameters and allocate data structures */
891c49ab 4705 BUG_ON(offset_in_page(align) || !is_power_of_2(align));
ca23e405
TH
4706 for (last_area = 0, area = 0; area < nr_vms; area++) {
4707 start = offsets[area];
4708 end = start + sizes[area];
4709
4710 /* is everything aligned properly? */
4711 BUG_ON(!IS_ALIGNED(offsets[area], align));
4712 BUG_ON(!IS_ALIGNED(sizes[area], align));
4713
4714 /* detect the area with the highest address */
4715 if (start > offsets[last_area])
4716 last_area = area;
4717
c568da28 4718 for (area2 = area + 1; area2 < nr_vms; area2++) {
ca23e405
TH
4719 unsigned long start2 = offsets[area2];
4720 unsigned long end2 = start2 + sizes[area2];
4721
c568da28 4722 BUG_ON(start2 < end && start < end2);
ca23e405
TH
4723 }
4724 }
4725 last_end = offsets[last_area] + sizes[last_area];
4726
4727 if (vmalloc_end - vmalloc_start < last_end) {
4728 WARN_ON(true);
4729 return NULL;
4730 }
4731
4d67d860
TM
4732 vms = kcalloc(nr_vms, sizeof(vms[0]), GFP_KERNEL);
4733 vas = kcalloc(nr_vms, sizeof(vas[0]), GFP_KERNEL);
ca23e405 4734 if (!vas || !vms)
f1db7afd 4735 goto err_free2;
ca23e405
TH
4736
4737 for (area = 0; area < nr_vms; area++) {
68ad4a33 4738 vas[area] = kmem_cache_zalloc(vmap_area_cachep, GFP_KERNEL);
ec3f64fc 4739 vms[area] = kzalloc(sizeof(struct vm_struct), GFP_KERNEL);
ca23e405
TH
4740 if (!vas[area] || !vms[area])
4741 goto err_free;
4742 }
4743retry:
e36176be 4744 spin_lock(&free_vmap_area_lock);
ca23e405
TH
4745
4746 /* start scanning - we scan from the top, begin with the last area */
4747 area = term_area = last_area;
4748 start = offsets[area];
4749 end = start + sizes[area];
4750
68ad4a33
URS
4751 va = pvm_find_va_enclose_addr(vmalloc_end);
4752 base = pvm_determine_end_from_reverse(&va, align) - end;
ca23e405
TH
4753
4754 while (true) {
ca23e405
TH
4755 /*
4756 * base might have underflowed, add last_end before
4757 * comparing.
4758 */
68ad4a33
URS
4759 if (base + last_end < vmalloc_start + last_end)
4760 goto overflow;
ca23e405
TH
4761
4762 /*
68ad4a33 4763 * Fitting base has not been found.
ca23e405 4764 */
68ad4a33
URS
4765 if (va == NULL)
4766 goto overflow;
ca23e405 4767
5336e52c 4768 /*
d8cc323d 4769 * If required width exceeds current VA block, move
5336e52c
KS
4770 * base downwards and then recheck.
4771 */
4772 if (base + end > va->va_end) {
4773 base = pvm_determine_end_from_reverse(&va, align) - end;
4774 term_area = area;
4775 continue;
4776 }
4777
ca23e405 4778 /*
68ad4a33 4779 * If this VA does not fit, move base downwards and recheck.
ca23e405 4780 */
5336e52c 4781 if (base + start < va->va_start) {
68ad4a33
URS
4782 va = node_to_va(rb_prev(&va->rb_node));
4783 base = pvm_determine_end_from_reverse(&va, align) - end;
ca23e405
TH
4784 term_area = area;
4785 continue;
4786 }
4787
4788 /*
4789 * This area fits, move on to the previous one. If
4790 * the previous one is the terminal one, we're done.
4791 */
4792 area = (area + nr_vms - 1) % nr_vms;
4793 if (area == term_area)
4794 break;
68ad4a33 4795
ca23e405
TH
4796 start = offsets[area];
4797 end = start + sizes[area];
68ad4a33 4798 va = pvm_find_va_enclose_addr(base + end);
ca23e405 4799 }
68ad4a33 4800
ca23e405
TH
4801 /* we've found a fitting base, insert all va's */
4802 for (area = 0; area < nr_vms; area++) {
68ad4a33 4803 int ret;
ca23e405 4804
68ad4a33
URS
4805 start = base + offsets[area];
4806 size = sizes[area];
ca23e405 4807
68ad4a33
URS
4808 va = pvm_find_va_enclose_addr(start);
4809 if (WARN_ON_ONCE(va == NULL))
4810 /* It is a BUG(), but trigger recovery instead. */
4811 goto recovery;
4812
5b75b8e1
URS
4813 ret = va_clip(&free_vmap_area_root,
4814 &free_vmap_area_list, va, start, size);
1b23ff80 4815 if (WARN_ON_ONCE(unlikely(ret)))
68ad4a33
URS
4816 /* It is a BUG(), but trigger recovery instead. */
4817 goto recovery;
4818
68ad4a33
URS
4819 /* Allocated area. */
4820 va = vas[area];
4821 va->va_start = start;
4822 va->va_end = start + size;
68ad4a33 4823 }
ca23e405 4824
e36176be 4825 spin_unlock(&free_vmap_area_lock);
ca23e405 4826
253a496d
DA
4827 /* populate the kasan shadow space */
4828 for (area = 0; area < nr_vms; area++) {
4829 if (kasan_populate_vmalloc(vas[area]->va_start, sizes[area]))
4830 goto err_free_shadow;
253a496d
DA
4831 }
4832
ca23e405 4833 /* insert all vm's */
e36176be 4834 for (area = 0; area < nr_vms; area++) {
d0936029 4835 struct vmap_node *vn = addr_to_node(vas[area]->va_start);
e36176be 4836
d0936029
URS
4837 spin_lock(&vn->busy.lock);
4838 insert_vmap_area(vas[area], &vn->busy.root, &vn->busy.head);
aaab830a 4839 setup_vmalloc_vm(vms[area], vas[area], VM_ALLOC,
3645cb4a 4840 pcpu_get_vm_areas);
d0936029 4841 spin_unlock(&vn->busy.lock);
e36176be 4842 }
ca23e405 4843
19f1c3ac
AK
4844 /*
4845 * Mark allocated areas as accessible. Do it now as a best-effort
4846 * approach, as they can be mapped outside of vmalloc code.
23689e91
AK
4847 * With hardware tag-based KASAN, marking is skipped for
4848 * non-VM_ALLOC mappings, see __kasan_unpoison_vmalloc().
19f1c3ac 4849 */
1d96320f
AK
4850 for (area = 0; area < nr_vms; area++)
4851 vms[area]->addr = kasan_unpoison_vmalloc(vms[area]->addr,
f6e39794 4852 vms[area]->size, KASAN_VMALLOC_PROT_NORMAL);
1d96320f 4853
ca23e405
TH
4854 kfree(vas);
4855 return vms;
4856
68ad4a33 4857recovery:
e36176be
URS
4858 /*
4859 * Remove previously allocated areas. There is no
4860 * need in removing these areas from the busy tree,
4861 * because they are inserted only on the final step
4862 * and when pcpu_get_vm_areas() is success.
4863 */
68ad4a33 4864 while (area--) {
253a496d
DA
4865 orig_start = vas[area]->va_start;
4866 orig_end = vas[area]->va_end;
96e2db45
URS
4867 va = merge_or_add_vmap_area_augment(vas[area], &free_vmap_area_root,
4868 &free_vmap_area_list);
9c801f61
URS
4869 if (va)
4870 kasan_release_vmalloc(orig_start, orig_end,
9e9e085e
AH
4871 va->va_start, va->va_end,
4872 KASAN_VMALLOC_PAGE_RANGE | KASAN_VMALLOC_TLB_FLUSH);
68ad4a33
URS
4873 vas[area] = NULL;
4874 }
4875
4876overflow:
e36176be 4877 spin_unlock(&free_vmap_area_lock);
68ad4a33 4878 if (!purged) {
77e50af0 4879 reclaim_and_purge_vmap_areas();
68ad4a33
URS
4880 purged = true;
4881
4882 /* Before "retry", check if we recover. */
4883 for (area = 0; area < nr_vms; area++) {
4884 if (vas[area])
4885 continue;
4886
4887 vas[area] = kmem_cache_zalloc(
4888 vmap_area_cachep, GFP_KERNEL);
4889 if (!vas[area])
4890 goto err_free;
4891 }
4892
4893 goto retry;
4894 }
4895
ca23e405
TH
4896err_free:
4897 for (area = 0; area < nr_vms; area++) {
68ad4a33
URS
4898 if (vas[area])
4899 kmem_cache_free(vmap_area_cachep, vas[area]);
4900
f1db7afd 4901 kfree(vms[area]);
ca23e405 4902 }
f1db7afd 4903err_free2:
ca23e405
TH
4904 kfree(vas);
4905 kfree(vms);
4906 return NULL;
253a496d
DA
4907
4908err_free_shadow:
4909 spin_lock(&free_vmap_area_lock);
4910 /*
4911 * We release all the vmalloc shadows, even the ones for regions that
4912 * hadn't been successfully added. This relies on kasan_release_vmalloc
4913 * being able to tolerate this case.
4914 */
4915 for (area = 0; area < nr_vms; area++) {
4916 orig_start = vas[area]->va_start;
4917 orig_end = vas[area]->va_end;
96e2db45
URS
4918 va = merge_or_add_vmap_area_augment(vas[area], &free_vmap_area_root,
4919 &free_vmap_area_list);
9c801f61
URS
4920 if (va)
4921 kasan_release_vmalloc(orig_start, orig_end,
9e9e085e
AH
4922 va->va_start, va->va_end,
4923 KASAN_VMALLOC_PAGE_RANGE | KASAN_VMALLOC_TLB_FLUSH);
253a496d
DA
4924 vas[area] = NULL;
4925 kfree(vms[area]);
4926 }
4927 spin_unlock(&free_vmap_area_lock);
4928 kfree(vas);
4929 kfree(vms);
4930 return NULL;
ca23e405
TH
4931}
4932
4933/**
4934 * pcpu_free_vm_areas - free vmalloc areas for percpu allocator
4935 * @vms: vm_struct pointer array returned by pcpu_get_vm_areas()
4936 * @nr_vms: the number of allocated areas
4937 *
4938 * Free vm_structs and the array allocated by pcpu_get_vm_areas().
4939 */
4940void pcpu_free_vm_areas(struct vm_struct **vms, int nr_vms)
4941{
4942 int i;
4943
4944 for (i = 0; i < nr_vms; i++)
4945 free_vm_area(vms[i]);
4946 kfree(vms);
4947}
4f8b02b4 4948#endif /* CONFIG_SMP */
a10aa579 4949
5bb1bb35 4950#ifdef CONFIG_PRINTK
98f18083
PM
4951bool vmalloc_dump_obj(void *object)
4952{
0818e739
JFG
4953 const void *caller;
4954 struct vm_struct *vm;
4955 struct vmap_area *va;
d0936029 4956 struct vmap_node *vn;
0818e739
JFG
4957 unsigned long addr;
4958 unsigned int nr_pages;
98f18083 4959
8be4d46e
URS
4960 addr = PAGE_ALIGN((unsigned long) object);
4961 vn = addr_to_node(addr);
d0936029 4962
8be4d46e 4963 if (!spin_trylock(&vn->busy.lock))
0818e739 4964 return false;
d0936029 4965
8be4d46e
URS
4966 va = __find_vmap_area(addr, &vn->busy.root);
4967 if (!va || !va->vm) {
d0936029 4968 spin_unlock(&vn->busy.lock);
98f18083 4969 return false;
0818e739
JFG
4970 }
4971
4972 vm = va->vm;
8be4d46e 4973 addr = (unsigned long) vm->addr;
0818e739
JFG
4974 caller = vm->caller;
4975 nr_pages = vm->nr_pages;
8be4d46e 4976 spin_unlock(&vn->busy.lock);
d0936029 4977
bd34dcd4 4978 pr_cont(" %u-page vmalloc region starting at %#lx allocated at %pS\n",
0818e739 4979 nr_pages, addr, caller);
8be4d46e 4980
98f18083
PM
4981 return true;
4982}
5bb1bb35 4983#endif
98f18083 4984
a10aa579 4985#ifdef CONFIG_PROC_FS
a47a126a 4986
5c5f0468
JP
4987/*
4988 * Print number of pages allocated on each memory node.
4989 *
4990 * This function can only be called if CONFIG_NUMA is enabled
4991 * and VM_UNINITIALIZED bit in v->flags is disabled.
4992 */
4993static void show_numa_info(struct seq_file *m, struct vm_struct *v,
4994 unsigned int *counters)
4995{
4996 unsigned int nr;
4997 unsigned int step = 1U << vm_area_page_order(v);
a47a126a 4998
5c5f0468
JP
4999 if (!counters)
5000 return;
af12346c 5001
5c5f0468 5002 memset(counters, 0, nr_node_ids * sizeof(unsigned int));
a47a126a 5003
5c5f0468
JP
5004 for (nr = 0; nr < v->nr_pages; nr += step)
5005 counters[page_to_nid(v->pages[nr])] += step;
5006 for_each_node_state(nr, N_HIGH_MEMORY)
5007 if (counters[nr])
5008 seq_printf(m, " N%u=%u", nr, counters[nr]);
a47a126a
ED
5009}
5010
dd3b8353
URS
5011static void show_purge_info(struct seq_file *m)
5012{
282631cb 5013 struct vmap_node *vn;
dd3b8353
URS
5014 struct vmap_area *va;
5015
ce906d76 5016 for_each_vmap_node(vn) {
282631cb
URS
5017 spin_lock(&vn->lazy.lock);
5018 list_for_each_entry(va, &vn->lazy.head, list) {
5019 seq_printf(m, "0x%pK-0x%pK %7ld unpurged vm_area\n",
5020 (void *)va->va_start, (void *)va->va_end,
b44f71e3 5021 va_size(va));
282631cb
URS
5022 }
5023 spin_unlock(&vn->lazy.lock);
dd3b8353
URS
5024 }
5025}
5026
8e1d743f 5027static int vmalloc_info_show(struct seq_file *m, void *p)
a10aa579 5028{
d0936029 5029 struct vmap_node *vn;
3f500069 5030 struct vmap_area *va;
d4033afd 5031 struct vm_struct *v;
5c5f0468 5032 unsigned int *counters;
d4033afd 5033
5c5f0468
JP
5034 if (IS_ENABLED(CONFIG_NUMA))
5035 counters = kmalloc(nr_node_ids * sizeof(unsigned int), GFP_KERNEL);
3f500069 5036
ce906d76 5037 for_each_vmap_node(vn) {
8e1d743f
URS
5038 spin_lock(&vn->busy.lock);
5039 list_for_each_entry(va, &vn->busy.head, list) {
5040 if (!va->vm) {
5041 if (va->flags & VMAP_RAM)
5042 seq_printf(m, "0x%pK-0x%pK %7ld vm_map_ram\n",
5043 (void *)va->va_start, (void *)va->va_end,
b44f71e3 5044 va_size(va));
78c72746 5045
8e1d743f
URS
5046 continue;
5047 }
d4033afd 5048
8e1d743f 5049 v = va->vm;
5c5f0468
JP
5050 if (v->flags & VM_UNINITIALIZED)
5051 continue;
5052
5053 /* Pair with smp_wmb() in clear_vm_uninitialized_flag() */
5054 smp_rmb();
a10aa579 5055
8e1d743f
URS
5056 seq_printf(m, "0x%pK-0x%pK %7ld",
5057 v->addr, v->addr + v->size, v->size);
a10aa579 5058
8e1d743f
URS
5059 if (v->caller)
5060 seq_printf(m, " %pS", v->caller);
23016969 5061
8e1d743f
URS
5062 if (v->nr_pages)
5063 seq_printf(m, " pages=%d", v->nr_pages);
a10aa579 5064
8e1d743f
URS
5065 if (v->phys_addr)
5066 seq_printf(m, " phys=%pa", &v->phys_addr);
a10aa579 5067
8e1d743f
URS
5068 if (v->flags & VM_IOREMAP)
5069 seq_puts(m, " ioremap");
a10aa579 5070
902861e3
LT
5071 if (v->flags & VM_SPARSE)
5072 seq_puts(m, " sparse");
e6f79822 5073
8e1d743f
URS
5074 if (v->flags & VM_ALLOC)
5075 seq_puts(m, " vmalloc");
a10aa579 5076
8e1d743f
URS
5077 if (v->flags & VM_MAP)
5078 seq_puts(m, " vmap");
a10aa579 5079
8e1d743f
URS
5080 if (v->flags & VM_USERMAP)
5081 seq_puts(m, " user");
a10aa579 5082
8e1d743f
URS
5083 if (v->flags & VM_DMA_COHERENT)
5084 seq_puts(m, " dma-coherent");
fe9041c2 5085
8e1d743f
URS
5086 if (is_vmalloc_addr(v->pages))
5087 seq_puts(m, " vpages");
a10aa579 5088
5c5f0468
JP
5089 if (IS_ENABLED(CONFIG_NUMA))
5090 show_numa_info(m, v, counters);
5091
8e1d743f
URS
5092 seq_putc(m, '\n');
5093 }
5094 spin_unlock(&vn->busy.lock);
5095 }
dd3b8353
URS
5096
5097 /*
96e2db45 5098 * As a final step, dump "unpurged" areas.
dd3b8353 5099 */
8e1d743f 5100 show_purge_info(m);
5c5f0468
JP
5101 if (IS_ENABLED(CONFIG_NUMA))
5102 kfree(counters);
a10aa579
CL
5103 return 0;
5104}
5105
5f6a6a9c
AD
5106static int __init proc_vmalloc_init(void)
5107{
5c5f0468 5108 proc_create_single("vmallocinfo", 0400, NULL, vmalloc_info_show);
5f6a6a9c
AD
5109 return 0;
5110}
5111module_init(proc_vmalloc_init);
db3808c1 5112
a10aa579 5113#endif
208162f4 5114
d0936029 5115static void __init vmap_init_free_space(void)
7fa8cee0
URS
5116{
5117 unsigned long vmap_start = 1;
5118 const unsigned long vmap_end = ULONG_MAX;
d0936029
URS
5119 struct vmap_area *free;
5120 struct vm_struct *busy;
7fa8cee0
URS
5121
5122 /*
5123 * B F B B B F
5124 * -|-----|.....|-----|-----|-----|.....|-
5125 * | The KVA space |
5126 * |<--------------------------------->|
5127 */
d0936029
URS
5128 for (busy = vmlist; busy; busy = busy->next) {
5129 if ((unsigned long) busy->addr - vmap_start > 0) {
7fa8cee0
URS
5130 free = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT);
5131 if (!WARN_ON_ONCE(!free)) {
5132 free->va_start = vmap_start;
d0936029 5133 free->va_end = (unsigned long) busy->addr;
7fa8cee0
URS
5134
5135 insert_vmap_area_augment(free, NULL,
5136 &free_vmap_area_root,
5137 &free_vmap_area_list);
5138 }
5139 }
5140
d0936029 5141 vmap_start = (unsigned long) busy->addr + busy->size;
7fa8cee0
URS
5142 }
5143
5144 if (vmap_end - vmap_start > 0) {
5145 free = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT);
5146 if (!WARN_ON_ONCE(!free)) {
5147 free->va_start = vmap_start;
5148 free->va_end = vmap_end;
5149
5150 insert_vmap_area_augment(free, NULL,
5151 &free_vmap_area_root,
5152 &free_vmap_area_list);
5153 }
5154 }
5155}
5156
d0936029
URS
5157static void vmap_init_nodes(void)
5158{
5159 struct vmap_node *vn;
ce906d76 5160 int i;
8f33a2ff
URS
5161
5162#if BITS_PER_LONG == 64
15e02a39
URS
5163 /*
5164 * A high threshold of max nodes is fixed and bound to 128,
5165 * thus a scale factor is 1 for systems where number of cores
5166 * are less or equal to specified threshold.
5167 *
5168 * As for NUMA-aware notes. For bigger systems, for example
5169 * NUMA with multi-sockets, where we can end-up with thousands
5170 * of cores in total, a "sub-numa-clustering" should be added.
5171 *
5172 * In this case a NUMA domain is considered as a single entity
5173 * with dedicated sub-nodes in it which describe one group or
5174 * set of cores. Therefore a per-domain purging is supposed to
5175 * be added as well as a per-domain balancing.
5176 */
ce906d76 5177 int n = clamp_t(unsigned int, num_possible_cpus(), 1, 128);
8f33a2ff
URS
5178
5179 if (n > 1) {
5180 vn = kmalloc_array(n, sizeof(*vn), GFP_NOWAIT | __GFP_NOWARN);
5181 if (vn) {
5182 /* Node partition is 16 pages. */
5183 vmap_zone_size = (1 << 4) * PAGE_SIZE;
5184 nr_vmap_nodes = n;
5185 vmap_nodes = vn;
5186 } else {
5187 pr_err("Failed to allocate an array. Disable a node layer\n");
5188 }
5189 }
5190#endif
d0936029 5191
ce906d76 5192 for_each_vmap_node(vn) {
d0936029
URS
5193 vn->busy.root = RB_ROOT;
5194 INIT_LIST_HEAD(&vn->busy.head);
5195 spin_lock_init(&vn->busy.lock);
282631cb
URS
5196
5197 vn->lazy.root = RB_ROOT;
5198 INIT_LIST_HEAD(&vn->lazy.head);
5199 spin_lock_init(&vn->lazy.lock);
72210662 5200
8f33a2ff
URS
5201 for (i = 0; i < MAX_VA_SIZE_PAGES; i++) {
5202 INIT_LIST_HEAD(&vn->pool[i].head);
5203 WRITE_ONCE(vn->pool[i].len, 0);
72210662
URS
5204 }
5205
5206 spin_lock_init(&vn->pool_lock);
d0936029
URS
5207 }
5208}
5209
7679ba6b
URS
5210static unsigned long
5211vmap_node_shrink_count(struct shrinker *shrink, struct shrink_control *sc)
5212{
ce906d76 5213 unsigned long count = 0;
7679ba6b 5214 struct vmap_node *vn;
ce906d76 5215 int i;
7679ba6b 5216
ce906d76
URS
5217 for_each_vmap_node(vn) {
5218 for (i = 0; i < MAX_VA_SIZE_PAGES; i++)
5219 count += READ_ONCE(vn->pool[i].len);
7679ba6b
URS
5220 }
5221
5222 return count ? count : SHRINK_EMPTY;
5223}
5224
5225static unsigned long
5226vmap_node_shrink_scan(struct shrinker *shrink, struct shrink_control *sc)
5227{
ce906d76 5228 struct vmap_node *vn;
7679ba6b 5229
ce906d76
URS
5230 for_each_vmap_node(vn)
5231 decay_va_pool_node(vn, true);
7679ba6b
URS
5232
5233 return SHRINK_STOP;
5234}
5235
208162f4
CH
5236void __init vmalloc_init(void)
5237{
7679ba6b 5238 struct shrinker *vmap_node_shrinker;
208162f4 5239 struct vmap_area *va;
d0936029 5240 struct vmap_node *vn;
208162f4
CH
5241 struct vm_struct *tmp;
5242 int i;
5243
5244 /*
5245 * Create the cache for vmap_area objects.
5246 */
5247 vmap_area_cachep = KMEM_CACHE(vmap_area, SLAB_PANIC);
5248
5249 for_each_possible_cpu(i) {
5250 struct vmap_block_queue *vbq;
5251 struct vfree_deferred *p;
5252
5253 vbq = &per_cpu(vmap_block_queue, i);
5254 spin_lock_init(&vbq->lock);
5255 INIT_LIST_HEAD(&vbq->free);
5256 p = &per_cpu(vfree_deferred, i);
5257 init_llist_head(&p->list);
5258 INIT_WORK(&p->wq, delayed_vfree_work);
062eacf5 5259 xa_init(&vbq->vmap_blocks);
208162f4
CH
5260 }
5261
d0936029
URS
5262 /*
5263 * Setup nodes before importing vmlist.
5264 */
5265 vmap_init_nodes();
5266
208162f4
CH
5267 /* Import existing vmlist entries. */
5268 for (tmp = vmlist; tmp; tmp = tmp->next) {
5269 va = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT);
5270 if (WARN_ON_ONCE(!va))
5271 continue;
5272
5273 va->va_start = (unsigned long)tmp->addr;
5274 va->va_end = va->va_start + tmp->size;
5275 va->vm = tmp;
d0936029
URS
5276
5277 vn = addr_to_node(va->va_start);
5278 insert_vmap_area(va, &vn->busy.root, &vn->busy.head);
208162f4
CH
5279 }
5280
5281 /*
5282 * Now we can initialize a free vmap space.
5283 */
5284 vmap_init_free_space();
5285 vmap_initialized = true;
7679ba6b
URS
5286
5287 vmap_node_shrinker = shrinker_alloc(0, "vmap-node");
5288 if (!vmap_node_shrinker) {
5289 pr_err("Failed to allocate vmap-node shrinker!\n");
5290 return;
5291 }
5292
5293 vmap_node_shrinker->count_objects = vmap_node_shrink_count;
5294 vmap_node_shrinker->scan_objects = vmap_node_shrink_scan;
5295 shrinker_register(vmap_node_shrinker);
208162f4 5296}