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