linux - mm/vmalloc.c

5589 lines · 144.9 KiB

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