11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds * linux/mm/vmalloc.c 31da177e4SLinus Torvalds * 41da177e4SLinus Torvalds * Copyright (C) 1993 Linus Torvalds 51da177e4SLinus Torvalds * Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999 61da177e4SLinus Torvalds * SMP-safe vmalloc/vfree/ioremap, Tigran Aivazian <tigran@veritas.com>, May 2000 71da177e4SLinus Torvalds * Major rework to support vmap/vunmap, Christoph Hellwig, SGI, August 2002 8930fc45aSChristoph Lameter * Numa awareness, Christoph Lameter, SGI, June 2005 91da177e4SLinus Torvalds */ 101da177e4SLinus Torvalds 11db64fe02SNick Piggin #include <linux/vmalloc.h> 121da177e4SLinus Torvalds #include <linux/mm.h> 131da177e4SLinus Torvalds #include <linux/module.h> 141da177e4SLinus Torvalds #include <linux/highmem.h> 15c3edc401SIngo Molnar #include <linux/sched/signal.h> 161da177e4SLinus Torvalds #include <linux/slab.h> 171da177e4SLinus Torvalds #include <linux/spinlock.h> 181da177e4SLinus Torvalds #include <linux/interrupt.h> 195f6a6a9cSAlexey Dobriyan #include <linux/proc_fs.h> 20a10aa579SChristoph Lameter #include <linux/seq_file.h> 21868b104dSRick Edgecombe #include <linux/set_memory.h> 223ac7fe5aSThomas Gleixner #include <linux/debugobjects.h> 2323016969SChristoph Lameter #include <linux/kallsyms.h> 24db64fe02SNick Piggin #include <linux/list.h> 254da56b99SChris Wilson #include <linux/notifier.h> 26db64fe02SNick Piggin #include <linux/rbtree.h> 27db64fe02SNick Piggin #include <linux/radix-tree.h> 28db64fe02SNick Piggin #include <linux/rcupdate.h> 29f0aa6617STejun Heo #include <linux/pfn.h> 3089219d37SCatalin Marinas #include <linux/kmemleak.h> 3160063497SArun Sharma #include <linux/atomic.h> 323b32123dSGideon Israel Dsouza #include <linux/compiler.h> 3332fcfd40SAl Viro #include <linux/llist.h> 340f616be1SToshi Kani #include <linux/bitops.h> 3568ad4a33SUladzislau Rezki (Sony) #include <linux/rbtree_augmented.h> 363b32123dSGideon Israel Dsouza 377c0f6ba6SLinus Torvalds #include <linux/uaccess.h> 381da177e4SLinus Torvalds #include <asm/tlbflush.h> 392dca6999SDavid Miller #include <asm/shmparam.h> 401da177e4SLinus Torvalds 41dd56b046SMel Gorman #include "internal.h" 42dd56b046SMel Gorman 4332fcfd40SAl Viro struct vfree_deferred { 4432fcfd40SAl Viro struct llist_head list; 4532fcfd40SAl Viro struct work_struct wq; 4632fcfd40SAl Viro }; 4732fcfd40SAl Viro static DEFINE_PER_CPU(struct vfree_deferred, vfree_deferred); 4832fcfd40SAl Viro 4932fcfd40SAl Viro static void __vunmap(const void *, int); 5032fcfd40SAl Viro 5132fcfd40SAl Viro static void free_work(struct work_struct *w) 5232fcfd40SAl Viro { 5332fcfd40SAl Viro struct vfree_deferred *p = container_of(w, struct vfree_deferred, wq); 54894e58c1SByungchul Park struct llist_node *t, *llnode; 55894e58c1SByungchul Park 56894e58c1SByungchul Park llist_for_each_safe(llnode, t, llist_del_all(&p->list)) 57894e58c1SByungchul Park __vunmap((void *)llnode, 1); 5832fcfd40SAl Viro } 5932fcfd40SAl Viro 60db64fe02SNick Piggin /*** Page table manipulation functions ***/ 61b221385bSAdrian Bunk 621da177e4SLinus Torvalds static void vunmap_pte_range(pmd_t *pmd, unsigned long addr, unsigned long end) 631da177e4SLinus Torvalds { 641da177e4SLinus Torvalds pte_t *pte; 651da177e4SLinus Torvalds 661da177e4SLinus Torvalds pte = pte_offset_kernel(pmd, addr); 671da177e4SLinus Torvalds do { 681da177e4SLinus Torvalds pte_t ptent = ptep_get_and_clear(&init_mm, addr, pte); 691da177e4SLinus Torvalds WARN_ON(!pte_none(ptent) && !pte_present(ptent)); 701da177e4SLinus Torvalds } while (pte++, addr += PAGE_SIZE, addr != end); 711da177e4SLinus Torvalds } 721da177e4SLinus Torvalds 73db64fe02SNick Piggin static void vunmap_pmd_range(pud_t *pud, unsigned long addr, unsigned long end) 741da177e4SLinus Torvalds { 751da177e4SLinus Torvalds pmd_t *pmd; 761da177e4SLinus Torvalds unsigned long next; 771da177e4SLinus Torvalds 781da177e4SLinus Torvalds pmd = pmd_offset(pud, addr); 791da177e4SLinus Torvalds do { 801da177e4SLinus Torvalds next = pmd_addr_end(addr, end); 81b9820d8fSToshi Kani if (pmd_clear_huge(pmd)) 82b9820d8fSToshi Kani continue; 831da177e4SLinus Torvalds if (pmd_none_or_clear_bad(pmd)) 841da177e4SLinus Torvalds continue; 851da177e4SLinus Torvalds vunmap_pte_range(pmd, addr, next); 861da177e4SLinus Torvalds } while (pmd++, addr = next, addr != end); 871da177e4SLinus Torvalds } 881da177e4SLinus Torvalds 89c2febafcSKirill A. Shutemov static void vunmap_pud_range(p4d_t *p4d, unsigned long addr, unsigned long end) 901da177e4SLinus Torvalds { 911da177e4SLinus Torvalds pud_t *pud; 921da177e4SLinus Torvalds unsigned long next; 931da177e4SLinus Torvalds 94c2febafcSKirill A. Shutemov pud = pud_offset(p4d, addr); 951da177e4SLinus Torvalds do { 961da177e4SLinus Torvalds next = pud_addr_end(addr, end); 97b9820d8fSToshi Kani if (pud_clear_huge(pud)) 98b9820d8fSToshi Kani continue; 991da177e4SLinus Torvalds if (pud_none_or_clear_bad(pud)) 1001da177e4SLinus Torvalds continue; 1011da177e4SLinus Torvalds vunmap_pmd_range(pud, addr, next); 1021da177e4SLinus Torvalds } while (pud++, addr = next, addr != end); 1031da177e4SLinus Torvalds } 1041da177e4SLinus Torvalds 105c2febafcSKirill A. Shutemov static void vunmap_p4d_range(pgd_t *pgd, unsigned long addr, unsigned long end) 106c2febafcSKirill A. Shutemov { 107c2febafcSKirill A. Shutemov p4d_t *p4d; 108c2febafcSKirill A. Shutemov unsigned long next; 109c2febafcSKirill A. Shutemov 110c2febafcSKirill A. Shutemov p4d = p4d_offset(pgd, addr); 111c2febafcSKirill A. Shutemov do { 112c2febafcSKirill A. Shutemov next = p4d_addr_end(addr, end); 113c2febafcSKirill A. Shutemov if (p4d_clear_huge(p4d)) 114c2febafcSKirill A. Shutemov continue; 115c2febafcSKirill A. Shutemov if (p4d_none_or_clear_bad(p4d)) 116c2febafcSKirill A. Shutemov continue; 117c2febafcSKirill A. Shutemov vunmap_pud_range(p4d, addr, next); 118c2febafcSKirill A. Shutemov } while (p4d++, addr = next, addr != end); 119c2febafcSKirill A. Shutemov } 120c2febafcSKirill A. Shutemov 121db64fe02SNick Piggin static void vunmap_page_range(unsigned long addr, unsigned long end) 1221da177e4SLinus Torvalds { 1231da177e4SLinus Torvalds pgd_t *pgd; 1241da177e4SLinus Torvalds unsigned long next; 1251da177e4SLinus Torvalds 1261da177e4SLinus Torvalds BUG_ON(addr >= end); 1271da177e4SLinus Torvalds pgd = pgd_offset_k(addr); 1281da177e4SLinus Torvalds do { 1291da177e4SLinus Torvalds next = pgd_addr_end(addr, end); 1301da177e4SLinus Torvalds if (pgd_none_or_clear_bad(pgd)) 1311da177e4SLinus Torvalds continue; 132c2febafcSKirill A. Shutemov vunmap_p4d_range(pgd, addr, next); 1331da177e4SLinus Torvalds } while (pgd++, addr = next, addr != end); 1341da177e4SLinus Torvalds } 1351da177e4SLinus Torvalds 1361da177e4SLinus Torvalds static int vmap_pte_range(pmd_t *pmd, unsigned long addr, 137db64fe02SNick Piggin unsigned long end, pgprot_t prot, struct page **pages, int *nr) 1381da177e4SLinus Torvalds { 1391da177e4SLinus Torvalds pte_t *pte; 1401da177e4SLinus Torvalds 141db64fe02SNick Piggin /* 142db64fe02SNick Piggin * nr is a running index into the array which helps higher level 143db64fe02SNick Piggin * callers keep track of where we're up to. 144db64fe02SNick Piggin */ 145db64fe02SNick Piggin 146872fec16SHugh Dickins pte = pte_alloc_kernel(pmd, addr); 1471da177e4SLinus Torvalds if (!pte) 1481da177e4SLinus Torvalds return -ENOMEM; 1491da177e4SLinus Torvalds do { 150db64fe02SNick Piggin struct page *page = pages[*nr]; 151db64fe02SNick Piggin 152db64fe02SNick Piggin if (WARN_ON(!pte_none(*pte))) 153db64fe02SNick Piggin return -EBUSY; 154db64fe02SNick Piggin if (WARN_ON(!page)) 1551da177e4SLinus Torvalds return -ENOMEM; 1561da177e4SLinus Torvalds set_pte_at(&init_mm, addr, pte, mk_pte(page, prot)); 157db64fe02SNick Piggin (*nr)++; 1581da177e4SLinus Torvalds } while (pte++, addr += PAGE_SIZE, addr != end); 1591da177e4SLinus Torvalds return 0; 1601da177e4SLinus Torvalds } 1611da177e4SLinus Torvalds 162db64fe02SNick Piggin static int vmap_pmd_range(pud_t *pud, unsigned long addr, 163db64fe02SNick Piggin unsigned long end, pgprot_t prot, struct page **pages, int *nr) 1641da177e4SLinus Torvalds { 1651da177e4SLinus Torvalds pmd_t *pmd; 1661da177e4SLinus Torvalds unsigned long next; 1671da177e4SLinus Torvalds 1681da177e4SLinus Torvalds pmd = pmd_alloc(&init_mm, pud, addr); 1691da177e4SLinus Torvalds if (!pmd) 1701da177e4SLinus Torvalds return -ENOMEM; 1711da177e4SLinus Torvalds do { 1721da177e4SLinus Torvalds next = pmd_addr_end(addr, end); 173db64fe02SNick Piggin if (vmap_pte_range(pmd, addr, next, prot, pages, nr)) 1741da177e4SLinus Torvalds return -ENOMEM; 1751da177e4SLinus Torvalds } while (pmd++, addr = next, addr != end); 1761da177e4SLinus Torvalds return 0; 1771da177e4SLinus Torvalds } 1781da177e4SLinus Torvalds 179c2febafcSKirill A. Shutemov static int vmap_pud_range(p4d_t *p4d, unsigned long addr, 180db64fe02SNick Piggin unsigned long end, pgprot_t prot, struct page **pages, int *nr) 1811da177e4SLinus Torvalds { 1821da177e4SLinus Torvalds pud_t *pud; 1831da177e4SLinus Torvalds unsigned long next; 1841da177e4SLinus Torvalds 185c2febafcSKirill A. Shutemov pud = pud_alloc(&init_mm, p4d, addr); 1861da177e4SLinus Torvalds if (!pud) 1871da177e4SLinus Torvalds return -ENOMEM; 1881da177e4SLinus Torvalds do { 1891da177e4SLinus Torvalds next = pud_addr_end(addr, end); 190db64fe02SNick Piggin if (vmap_pmd_range(pud, addr, next, prot, pages, nr)) 1911da177e4SLinus Torvalds return -ENOMEM; 1921da177e4SLinus Torvalds } while (pud++, addr = next, addr != end); 1931da177e4SLinus Torvalds return 0; 1941da177e4SLinus Torvalds } 1951da177e4SLinus Torvalds 196c2febafcSKirill A. Shutemov static int vmap_p4d_range(pgd_t *pgd, unsigned long addr, 197c2febafcSKirill A. Shutemov unsigned long end, pgprot_t prot, struct page **pages, int *nr) 198c2febafcSKirill A. Shutemov { 199c2febafcSKirill A. Shutemov p4d_t *p4d; 200c2febafcSKirill A. Shutemov unsigned long next; 201c2febafcSKirill A. Shutemov 202c2febafcSKirill A. Shutemov p4d = p4d_alloc(&init_mm, pgd, addr); 203c2febafcSKirill A. Shutemov if (!p4d) 204c2febafcSKirill A. Shutemov return -ENOMEM; 205c2febafcSKirill A. Shutemov do { 206c2febafcSKirill A. Shutemov next = p4d_addr_end(addr, end); 207c2febafcSKirill A. Shutemov if (vmap_pud_range(p4d, addr, next, prot, pages, nr)) 208c2febafcSKirill A. Shutemov return -ENOMEM; 209c2febafcSKirill A. Shutemov } while (p4d++, addr = next, addr != end); 210c2febafcSKirill A. Shutemov return 0; 211c2febafcSKirill A. Shutemov } 212c2febafcSKirill A. Shutemov 213db64fe02SNick Piggin /* 214db64fe02SNick Piggin * Set up page tables in kva (addr, end). The ptes shall have prot "prot", and 215db64fe02SNick Piggin * will have pfns corresponding to the "pages" array. 216db64fe02SNick Piggin * 217db64fe02SNick Piggin * Ie. pte at addr+N*PAGE_SIZE shall point to pfn corresponding to pages[N] 218db64fe02SNick Piggin */ 2198fc48985STejun Heo static int vmap_page_range_noflush(unsigned long start, unsigned long end, 220db64fe02SNick Piggin pgprot_t prot, struct page **pages) 2211da177e4SLinus Torvalds { 2221da177e4SLinus Torvalds pgd_t *pgd; 2231da177e4SLinus Torvalds unsigned long next; 2242e4e27c7SAdam Lackorzynski unsigned long addr = start; 225db64fe02SNick Piggin int err = 0; 226db64fe02SNick Piggin int nr = 0; 2271da177e4SLinus Torvalds 2281da177e4SLinus Torvalds BUG_ON(addr >= end); 2291da177e4SLinus Torvalds pgd = pgd_offset_k(addr); 2301da177e4SLinus Torvalds do { 2311da177e4SLinus Torvalds next = pgd_addr_end(addr, end); 232c2febafcSKirill A. Shutemov err = vmap_p4d_range(pgd, addr, next, prot, pages, &nr); 2331da177e4SLinus Torvalds if (err) 234bf88c8c8SFigo.zhang return err; 2351da177e4SLinus Torvalds } while (pgd++, addr = next, addr != end); 236db64fe02SNick Piggin 237db64fe02SNick Piggin return nr; 2381da177e4SLinus Torvalds } 2391da177e4SLinus Torvalds 2408fc48985STejun Heo static int vmap_page_range(unsigned long start, unsigned long end, 2418fc48985STejun Heo pgprot_t prot, struct page **pages) 2428fc48985STejun Heo { 2438fc48985STejun Heo int ret; 2448fc48985STejun Heo 2458fc48985STejun Heo ret = vmap_page_range_noflush(start, end, prot, pages); 2468fc48985STejun Heo flush_cache_vmap(start, end); 2478fc48985STejun Heo return ret; 2488fc48985STejun Heo } 2498fc48985STejun Heo 25081ac3ad9SKAMEZAWA Hiroyuki int is_vmalloc_or_module_addr(const void *x) 25173bdf0a6SLinus Torvalds { 25273bdf0a6SLinus Torvalds /* 253ab4f2ee1SRussell King * ARM, x86-64 and sparc64 put modules in a special place, 25473bdf0a6SLinus Torvalds * and fall back on vmalloc() if that fails. Others 25573bdf0a6SLinus Torvalds * just put it in the vmalloc space. 25673bdf0a6SLinus Torvalds */ 25773bdf0a6SLinus Torvalds #if defined(CONFIG_MODULES) && defined(MODULES_VADDR) 25873bdf0a6SLinus Torvalds unsigned long addr = (unsigned long)x; 25973bdf0a6SLinus Torvalds if (addr >= MODULES_VADDR && addr < MODULES_END) 26073bdf0a6SLinus Torvalds return 1; 26173bdf0a6SLinus Torvalds #endif 26273bdf0a6SLinus Torvalds return is_vmalloc_addr(x); 26373bdf0a6SLinus Torvalds } 26473bdf0a6SLinus Torvalds 26548667e7aSChristoph Lameter /* 266add688fbSmalc * Walk a vmap address to the struct page it maps. 26748667e7aSChristoph Lameter */ 268add688fbSmalc struct page *vmalloc_to_page(const void *vmalloc_addr) 26948667e7aSChristoph Lameter { 27048667e7aSChristoph Lameter unsigned long addr = (unsigned long) vmalloc_addr; 271add688fbSmalc struct page *page = NULL; 27248667e7aSChristoph Lameter pgd_t *pgd = pgd_offset_k(addr); 273c2febafcSKirill A. Shutemov p4d_t *p4d; 274c2febafcSKirill A. Shutemov pud_t *pud; 275c2febafcSKirill A. Shutemov pmd_t *pmd; 276c2febafcSKirill A. Shutemov pte_t *ptep, pte; 27748667e7aSChristoph Lameter 2787aa413deSIngo Molnar /* 2797aa413deSIngo Molnar * XXX we might need to change this if we add VIRTUAL_BUG_ON for 2807aa413deSIngo Molnar * architectures that do not vmalloc module space 2817aa413deSIngo Molnar */ 28273bdf0a6SLinus Torvalds VIRTUAL_BUG_ON(!is_vmalloc_or_module_addr(vmalloc_addr)); 28359ea7463SJiri Slaby 284c2febafcSKirill A. Shutemov if (pgd_none(*pgd)) 285c2febafcSKirill A. Shutemov return NULL; 286c2febafcSKirill A. Shutemov p4d = p4d_offset(pgd, addr); 287c2febafcSKirill A. Shutemov if (p4d_none(*p4d)) 288c2febafcSKirill A. Shutemov return NULL; 289c2febafcSKirill A. Shutemov pud = pud_offset(p4d, addr); 290029c54b0SArd Biesheuvel 291029c54b0SArd Biesheuvel /* 292029c54b0SArd Biesheuvel * Don't dereference bad PUD or PMD (below) entries. This will also 293029c54b0SArd Biesheuvel * identify huge mappings, which we may encounter on architectures 294029c54b0SArd Biesheuvel * that define CONFIG_HAVE_ARCH_HUGE_VMAP=y. Such regions will be 295029c54b0SArd Biesheuvel * identified as vmalloc addresses by is_vmalloc_addr(), but are 296029c54b0SArd Biesheuvel * not [unambiguously] associated with a struct page, so there is 297029c54b0SArd Biesheuvel * no correct value to return for them. 298029c54b0SArd Biesheuvel */ 299029c54b0SArd Biesheuvel WARN_ON_ONCE(pud_bad(*pud)); 300029c54b0SArd Biesheuvel if (pud_none(*pud) || pud_bad(*pud)) 301c2febafcSKirill A. Shutemov return NULL; 302c2febafcSKirill A. Shutemov pmd = pmd_offset(pud, addr); 303029c54b0SArd Biesheuvel WARN_ON_ONCE(pmd_bad(*pmd)); 304029c54b0SArd Biesheuvel if (pmd_none(*pmd) || pmd_bad(*pmd)) 305c2febafcSKirill A. Shutemov return NULL; 306db64fe02SNick Piggin 30748667e7aSChristoph Lameter ptep = pte_offset_map(pmd, addr); 30848667e7aSChristoph Lameter pte = *ptep; 30948667e7aSChristoph Lameter if (pte_present(pte)) 310add688fbSmalc page = pte_page(pte); 31148667e7aSChristoph Lameter pte_unmap(ptep); 312add688fbSmalc return page; 313ece86e22SJianyu Zhan } 314ece86e22SJianyu Zhan EXPORT_SYMBOL(vmalloc_to_page); 315ece86e22SJianyu Zhan 316add688fbSmalc /* 317add688fbSmalc * Map a vmalloc()-space virtual address to the physical page frame number. 318add688fbSmalc */ 319add688fbSmalc unsigned long vmalloc_to_pfn(const void *vmalloc_addr) 320add688fbSmalc { 321add688fbSmalc return page_to_pfn(vmalloc_to_page(vmalloc_addr)); 322add688fbSmalc } 323add688fbSmalc EXPORT_SYMBOL(vmalloc_to_pfn); 324add688fbSmalc 325db64fe02SNick Piggin 326db64fe02SNick Piggin /*** Global kva allocator ***/ 327db64fe02SNick Piggin 328bb850f4dSUladzislau Rezki (Sony) #define DEBUG_AUGMENT_PROPAGATE_CHECK 0 329*a6cf4e0fSUladzislau Rezki (Sony) #define DEBUG_AUGMENT_LOWEST_MATCH_CHECK 0 330bb850f4dSUladzislau Rezki (Sony) 33178c72746SYisheng Xie #define VM_LAZY_FREE 0x02 332db64fe02SNick Piggin #define VM_VM_AREA 0x04 333db64fe02SNick Piggin 334db64fe02SNick Piggin static DEFINE_SPINLOCK(vmap_area_lock); 335f1c4069eSJoonsoo Kim /* Export for kexec only */ 336f1c4069eSJoonsoo Kim LIST_HEAD(vmap_area_list); 33780c4bd7aSChris Wilson static LLIST_HEAD(vmap_purge_list); 33889699605SNick Piggin static struct rb_root vmap_area_root = RB_ROOT; 33968ad4a33SUladzislau Rezki (Sony) static bool vmap_initialized __read_mostly; 34089699605SNick Piggin 34168ad4a33SUladzislau Rezki (Sony) /* 34268ad4a33SUladzislau Rezki (Sony) * This kmem_cache is used for vmap_area objects. Instead of 34368ad4a33SUladzislau Rezki (Sony) * allocating from slab we reuse an object from this cache to 34468ad4a33SUladzislau Rezki (Sony) * make things faster. Especially in "no edge" splitting of 34568ad4a33SUladzislau Rezki (Sony) * free block. 34668ad4a33SUladzislau Rezki (Sony) */ 34768ad4a33SUladzislau Rezki (Sony) static struct kmem_cache *vmap_area_cachep; 34889699605SNick Piggin 34968ad4a33SUladzislau Rezki (Sony) /* 35068ad4a33SUladzislau Rezki (Sony) * This linked list is used in pair with free_vmap_area_root. 35168ad4a33SUladzislau Rezki (Sony) * It gives O(1) access to prev/next to perform fast coalescing. 35268ad4a33SUladzislau Rezki (Sony) */ 35368ad4a33SUladzislau Rezki (Sony) static LIST_HEAD(free_vmap_area_list); 35468ad4a33SUladzislau Rezki (Sony) 35568ad4a33SUladzislau Rezki (Sony) /* 35668ad4a33SUladzislau Rezki (Sony) * This augment red-black tree represents the free vmap space. 35768ad4a33SUladzislau Rezki (Sony) * All vmap_area objects in this tree are sorted by va->va_start 35868ad4a33SUladzislau Rezki (Sony) * address. It is used for allocation and merging when a vmap 35968ad4a33SUladzislau Rezki (Sony) * object is released. 36068ad4a33SUladzislau Rezki (Sony) * 36168ad4a33SUladzislau Rezki (Sony) * Each vmap_area node contains a maximum available free block 36268ad4a33SUladzislau Rezki (Sony) * of its sub-tree, right or left. Therefore it is possible to 36368ad4a33SUladzislau Rezki (Sony) * find a lowest match of free area. 36468ad4a33SUladzislau Rezki (Sony) */ 36568ad4a33SUladzislau Rezki (Sony) static struct rb_root free_vmap_area_root = RB_ROOT; 36668ad4a33SUladzislau Rezki (Sony) 36768ad4a33SUladzislau Rezki (Sony) static __always_inline unsigned long 36868ad4a33SUladzislau Rezki (Sony) va_size(struct vmap_area *va) 36968ad4a33SUladzislau Rezki (Sony) { 37068ad4a33SUladzislau Rezki (Sony) return (va->va_end - va->va_start); 37168ad4a33SUladzislau Rezki (Sony) } 37268ad4a33SUladzislau Rezki (Sony) 37368ad4a33SUladzislau Rezki (Sony) static __always_inline unsigned long 37468ad4a33SUladzislau Rezki (Sony) get_subtree_max_size(struct rb_node *node) 37568ad4a33SUladzislau Rezki (Sony) { 37668ad4a33SUladzislau Rezki (Sony) struct vmap_area *va; 37768ad4a33SUladzislau Rezki (Sony) 37868ad4a33SUladzislau Rezki (Sony) va = rb_entry_safe(node, struct vmap_area, rb_node); 37968ad4a33SUladzislau Rezki (Sony) return va ? va->subtree_max_size : 0; 38068ad4a33SUladzislau Rezki (Sony) } 38168ad4a33SUladzislau Rezki (Sony) 38268ad4a33SUladzislau Rezki (Sony) /* 38368ad4a33SUladzislau Rezki (Sony) * Gets called when remove the node and rotate. 38468ad4a33SUladzislau Rezki (Sony) */ 38568ad4a33SUladzislau Rezki (Sony) static __always_inline unsigned long 38668ad4a33SUladzislau Rezki (Sony) compute_subtree_max_size(struct vmap_area *va) 38768ad4a33SUladzislau Rezki (Sony) { 38868ad4a33SUladzislau Rezki (Sony) return max3(va_size(va), 38968ad4a33SUladzislau Rezki (Sony) get_subtree_max_size(va->rb_node.rb_left), 39068ad4a33SUladzislau Rezki (Sony) get_subtree_max_size(va->rb_node.rb_right)); 39168ad4a33SUladzislau Rezki (Sony) } 39268ad4a33SUladzislau Rezki (Sony) 39368ad4a33SUladzislau Rezki (Sony) RB_DECLARE_CALLBACKS(static, free_vmap_area_rb_augment_cb, 39468ad4a33SUladzislau Rezki (Sony) struct vmap_area, rb_node, unsigned long, subtree_max_size, 39568ad4a33SUladzislau Rezki (Sony) compute_subtree_max_size) 39668ad4a33SUladzislau Rezki (Sony) 39768ad4a33SUladzislau Rezki (Sony) static void purge_vmap_area_lazy(void); 39868ad4a33SUladzislau Rezki (Sony) static BLOCKING_NOTIFIER_HEAD(vmap_notify_list); 39968ad4a33SUladzislau Rezki (Sony) static unsigned long lazy_max_pages(void); 400db64fe02SNick Piggin 401db64fe02SNick Piggin static struct vmap_area *__find_vmap_area(unsigned long addr) 4021da177e4SLinus Torvalds { 403db64fe02SNick Piggin struct rb_node *n = vmap_area_root.rb_node; 404db64fe02SNick Piggin 405db64fe02SNick Piggin while (n) { 406db64fe02SNick Piggin struct vmap_area *va; 407db64fe02SNick Piggin 408db64fe02SNick Piggin va = rb_entry(n, struct vmap_area, rb_node); 409db64fe02SNick Piggin if (addr < va->va_start) 410db64fe02SNick Piggin n = n->rb_left; 411cef2ac3fSHATAYAMA Daisuke else if (addr >= va->va_end) 412db64fe02SNick Piggin n = n->rb_right; 413db64fe02SNick Piggin else 414db64fe02SNick Piggin return va; 415db64fe02SNick Piggin } 416db64fe02SNick Piggin 417db64fe02SNick Piggin return NULL; 418db64fe02SNick Piggin } 419db64fe02SNick Piggin 42068ad4a33SUladzislau Rezki (Sony) /* 42168ad4a33SUladzislau Rezki (Sony) * This function returns back addresses of parent node 42268ad4a33SUladzislau Rezki (Sony) * and its left or right link for further processing. 42368ad4a33SUladzislau Rezki (Sony) */ 42468ad4a33SUladzislau Rezki (Sony) static __always_inline struct rb_node ** 42568ad4a33SUladzislau Rezki (Sony) find_va_links(struct vmap_area *va, 42668ad4a33SUladzislau Rezki (Sony) struct rb_root *root, struct rb_node *from, 42768ad4a33SUladzislau Rezki (Sony) struct rb_node **parent) 428db64fe02SNick Piggin { 429170168d0SNamhyung Kim struct vmap_area *tmp_va; 43068ad4a33SUladzislau Rezki (Sony) struct rb_node **link; 431db64fe02SNick Piggin 43268ad4a33SUladzislau Rezki (Sony) if (root) { 43368ad4a33SUladzislau Rezki (Sony) link = &root->rb_node; 43468ad4a33SUladzislau Rezki (Sony) if (unlikely(!*link)) { 43568ad4a33SUladzislau Rezki (Sony) *parent = NULL; 43668ad4a33SUladzislau Rezki (Sony) return link; 43768ad4a33SUladzislau Rezki (Sony) } 43868ad4a33SUladzislau Rezki (Sony) } else { 43968ad4a33SUladzislau Rezki (Sony) link = &from; 44068ad4a33SUladzislau Rezki (Sony) } 44168ad4a33SUladzislau Rezki (Sony) 44268ad4a33SUladzislau Rezki (Sony) /* 44368ad4a33SUladzislau Rezki (Sony) * Go to the bottom of the tree. When we hit the last point 44468ad4a33SUladzislau Rezki (Sony) * we end up with parent rb_node and correct direction, i name 44568ad4a33SUladzislau Rezki (Sony) * it link, where the new va->rb_node will be attached to. 44668ad4a33SUladzislau Rezki (Sony) */ 44768ad4a33SUladzislau Rezki (Sony) do { 44868ad4a33SUladzislau Rezki (Sony) tmp_va = rb_entry(*link, struct vmap_area, rb_node); 44968ad4a33SUladzislau Rezki (Sony) 45068ad4a33SUladzislau Rezki (Sony) /* 45168ad4a33SUladzislau Rezki (Sony) * During the traversal we also do some sanity check. 45268ad4a33SUladzislau Rezki (Sony) * Trigger the BUG() if there are sides(left/right) 45368ad4a33SUladzislau Rezki (Sony) * or full overlaps. 45468ad4a33SUladzislau Rezki (Sony) */ 45568ad4a33SUladzislau Rezki (Sony) if (va->va_start < tmp_va->va_end && 45668ad4a33SUladzislau Rezki (Sony) va->va_end <= tmp_va->va_start) 45768ad4a33SUladzislau Rezki (Sony) link = &(*link)->rb_left; 45868ad4a33SUladzislau Rezki (Sony) else if (va->va_end > tmp_va->va_start && 45968ad4a33SUladzislau Rezki (Sony) va->va_start >= tmp_va->va_end) 46068ad4a33SUladzislau Rezki (Sony) link = &(*link)->rb_right; 461db64fe02SNick Piggin else 462db64fe02SNick Piggin BUG(); 46368ad4a33SUladzislau Rezki (Sony) } while (*link); 46468ad4a33SUladzislau Rezki (Sony) 46568ad4a33SUladzislau Rezki (Sony) *parent = &tmp_va->rb_node; 46668ad4a33SUladzislau Rezki (Sony) return link; 467db64fe02SNick Piggin } 468db64fe02SNick Piggin 46968ad4a33SUladzislau Rezki (Sony) static __always_inline struct list_head * 47068ad4a33SUladzislau Rezki (Sony) get_va_next_sibling(struct rb_node *parent, struct rb_node **link) 47168ad4a33SUladzislau Rezki (Sony) { 47268ad4a33SUladzislau Rezki (Sony) struct list_head *list; 473db64fe02SNick Piggin 47468ad4a33SUladzislau Rezki (Sony) if (unlikely(!parent)) 47568ad4a33SUladzislau Rezki (Sony) /* 47668ad4a33SUladzislau Rezki (Sony) * The red-black tree where we try to find VA neighbors 47768ad4a33SUladzislau Rezki (Sony) * before merging or inserting is empty, i.e. it means 47868ad4a33SUladzislau Rezki (Sony) * there is no free vmap space. Normally it does not 47968ad4a33SUladzislau Rezki (Sony) * happen but we handle this case anyway. 48068ad4a33SUladzislau Rezki (Sony) */ 48168ad4a33SUladzislau Rezki (Sony) return NULL; 48268ad4a33SUladzislau Rezki (Sony) 48368ad4a33SUladzislau Rezki (Sony) list = &rb_entry(parent, struct vmap_area, rb_node)->list; 48468ad4a33SUladzislau Rezki (Sony) return (&parent->rb_right == link ? list->next : list); 485db64fe02SNick Piggin } 486db64fe02SNick Piggin 48768ad4a33SUladzislau Rezki (Sony) static __always_inline void 48868ad4a33SUladzislau Rezki (Sony) link_va(struct vmap_area *va, struct rb_root *root, 48968ad4a33SUladzislau Rezki (Sony) struct rb_node *parent, struct rb_node **link, struct list_head *head) 49068ad4a33SUladzislau Rezki (Sony) { 49168ad4a33SUladzislau Rezki (Sony) /* 49268ad4a33SUladzislau Rezki (Sony) * VA is still not in the list, but we can 49368ad4a33SUladzislau Rezki (Sony) * identify its future previous list_head node. 49468ad4a33SUladzislau Rezki (Sony) */ 49568ad4a33SUladzislau Rezki (Sony) if (likely(parent)) { 49668ad4a33SUladzislau Rezki (Sony) head = &rb_entry(parent, struct vmap_area, rb_node)->list; 49768ad4a33SUladzislau Rezki (Sony) if (&parent->rb_right != link) 49868ad4a33SUladzislau Rezki (Sony) head = head->prev; 49968ad4a33SUladzislau Rezki (Sony) } 500db64fe02SNick Piggin 50168ad4a33SUladzislau Rezki (Sony) /* Insert to the rb-tree */ 50268ad4a33SUladzislau Rezki (Sony) rb_link_node(&va->rb_node, parent, link); 50368ad4a33SUladzislau Rezki (Sony) if (root == &free_vmap_area_root) { 50468ad4a33SUladzislau Rezki (Sony) /* 50568ad4a33SUladzislau Rezki (Sony) * Some explanation here. Just perform simple insertion 50668ad4a33SUladzislau Rezki (Sony) * to the tree. We do not set va->subtree_max_size to 50768ad4a33SUladzislau Rezki (Sony) * its current size before calling rb_insert_augmented(). 50868ad4a33SUladzislau Rezki (Sony) * It is because of we populate the tree from the bottom 50968ad4a33SUladzislau Rezki (Sony) * to parent levels when the node _is_ in the tree. 51068ad4a33SUladzislau Rezki (Sony) * 51168ad4a33SUladzislau Rezki (Sony) * Therefore we set subtree_max_size to zero after insertion, 51268ad4a33SUladzislau Rezki (Sony) * to let __augment_tree_propagate_from() puts everything to 51368ad4a33SUladzislau Rezki (Sony) * the correct order later on. 51468ad4a33SUladzislau Rezki (Sony) */ 51568ad4a33SUladzislau Rezki (Sony) rb_insert_augmented(&va->rb_node, 51668ad4a33SUladzislau Rezki (Sony) root, &free_vmap_area_rb_augment_cb); 51768ad4a33SUladzislau Rezki (Sony) va->subtree_max_size = 0; 51868ad4a33SUladzislau Rezki (Sony) } else { 51968ad4a33SUladzislau Rezki (Sony) rb_insert_color(&va->rb_node, root); 52068ad4a33SUladzislau Rezki (Sony) } 52168ad4a33SUladzislau Rezki (Sony) 52268ad4a33SUladzislau Rezki (Sony) /* Address-sort this list */ 52368ad4a33SUladzislau Rezki (Sony) list_add(&va->list, head); 52468ad4a33SUladzislau Rezki (Sony) } 52568ad4a33SUladzislau Rezki (Sony) 52668ad4a33SUladzislau Rezki (Sony) static __always_inline void 52768ad4a33SUladzislau Rezki (Sony) unlink_va(struct vmap_area *va, struct rb_root *root) 52868ad4a33SUladzislau Rezki (Sony) { 52968ad4a33SUladzislau Rezki (Sony) /* 53068ad4a33SUladzislau Rezki (Sony) * During merging a VA node can be empty, therefore 53168ad4a33SUladzislau Rezki (Sony) * not linked with the tree nor list. Just check it. 53268ad4a33SUladzislau Rezki (Sony) */ 53368ad4a33SUladzislau Rezki (Sony) if (!RB_EMPTY_NODE(&va->rb_node)) { 53468ad4a33SUladzislau Rezki (Sony) if (root == &free_vmap_area_root) 53568ad4a33SUladzislau Rezki (Sony) rb_erase_augmented(&va->rb_node, 53668ad4a33SUladzislau Rezki (Sony) root, &free_vmap_area_rb_augment_cb); 53768ad4a33SUladzislau Rezki (Sony) else 53868ad4a33SUladzislau Rezki (Sony) rb_erase(&va->rb_node, root); 53968ad4a33SUladzislau Rezki (Sony) 54068ad4a33SUladzislau Rezki (Sony) list_del(&va->list); 54168ad4a33SUladzislau Rezki (Sony) RB_CLEAR_NODE(&va->rb_node); 54268ad4a33SUladzislau Rezki (Sony) } 54368ad4a33SUladzislau Rezki (Sony) } 54468ad4a33SUladzislau Rezki (Sony) 545bb850f4dSUladzislau Rezki (Sony) #if DEBUG_AUGMENT_PROPAGATE_CHECK 546bb850f4dSUladzislau Rezki (Sony) static void 547bb850f4dSUladzislau Rezki (Sony) augment_tree_propagate_check(struct rb_node *n) 548bb850f4dSUladzislau Rezki (Sony) { 549bb850f4dSUladzislau Rezki (Sony) struct vmap_area *va; 550bb850f4dSUladzislau Rezki (Sony) struct rb_node *node; 551bb850f4dSUladzislau Rezki (Sony) unsigned long size; 552bb850f4dSUladzislau Rezki (Sony) bool found = false; 553bb850f4dSUladzislau Rezki (Sony) 554bb850f4dSUladzislau Rezki (Sony) if (n == NULL) 555bb850f4dSUladzislau Rezki (Sony) return; 556bb850f4dSUladzislau Rezki (Sony) 557bb850f4dSUladzislau Rezki (Sony) va = rb_entry(n, struct vmap_area, rb_node); 558bb850f4dSUladzislau Rezki (Sony) size = va->subtree_max_size; 559bb850f4dSUladzislau Rezki (Sony) node = n; 560bb850f4dSUladzislau Rezki (Sony) 561bb850f4dSUladzislau Rezki (Sony) while (node) { 562bb850f4dSUladzislau Rezki (Sony) va = rb_entry(node, struct vmap_area, rb_node); 563bb850f4dSUladzislau Rezki (Sony) 564bb850f4dSUladzislau Rezki (Sony) if (get_subtree_max_size(node->rb_left) == size) { 565bb850f4dSUladzislau Rezki (Sony) node = node->rb_left; 566bb850f4dSUladzislau Rezki (Sony) } else { 567bb850f4dSUladzislau Rezki (Sony) if (va_size(va) == size) { 568bb850f4dSUladzislau Rezki (Sony) found = true; 569bb850f4dSUladzislau Rezki (Sony) break; 570bb850f4dSUladzislau Rezki (Sony) } 571bb850f4dSUladzislau Rezki (Sony) 572bb850f4dSUladzislau Rezki (Sony) node = node->rb_right; 573bb850f4dSUladzislau Rezki (Sony) } 574bb850f4dSUladzislau Rezki (Sony) } 575bb850f4dSUladzislau Rezki (Sony) 576bb850f4dSUladzislau Rezki (Sony) if (!found) { 577bb850f4dSUladzislau Rezki (Sony) va = rb_entry(n, struct vmap_area, rb_node); 578bb850f4dSUladzislau Rezki (Sony) pr_emerg("tree is corrupted: %lu, %lu\n", 579bb850f4dSUladzislau Rezki (Sony) va_size(va), va->subtree_max_size); 580bb850f4dSUladzislau Rezki (Sony) } 581bb850f4dSUladzislau Rezki (Sony) 582bb850f4dSUladzislau Rezki (Sony) augment_tree_propagate_check(n->rb_left); 583bb850f4dSUladzislau Rezki (Sony) augment_tree_propagate_check(n->rb_right); 584bb850f4dSUladzislau Rezki (Sony) } 585bb850f4dSUladzislau Rezki (Sony) #endif 586bb850f4dSUladzislau Rezki (Sony) 58768ad4a33SUladzislau Rezki (Sony) /* 58868ad4a33SUladzislau Rezki (Sony) * This function populates subtree_max_size from bottom to upper 58968ad4a33SUladzislau Rezki (Sony) * levels starting from VA point. The propagation must be done 59068ad4a33SUladzislau Rezki (Sony) * when VA size is modified by changing its va_start/va_end. Or 59168ad4a33SUladzislau Rezki (Sony) * in case of newly inserting of VA to the tree. 59268ad4a33SUladzislau Rezki (Sony) * 59368ad4a33SUladzislau Rezki (Sony) * It means that __augment_tree_propagate_from() must be called: 59468ad4a33SUladzislau Rezki (Sony) * - After VA has been inserted to the tree(free path); 59568ad4a33SUladzislau Rezki (Sony) * - After VA has been shrunk(allocation path); 59668ad4a33SUladzislau Rezki (Sony) * - After VA has been increased(merging path). 59768ad4a33SUladzislau Rezki (Sony) * 59868ad4a33SUladzislau Rezki (Sony) * Please note that, it does not mean that upper parent nodes 59968ad4a33SUladzislau Rezki (Sony) * and their subtree_max_size are recalculated all the time up 60068ad4a33SUladzislau Rezki (Sony) * to the root node. 60168ad4a33SUladzislau Rezki (Sony) * 60268ad4a33SUladzislau Rezki (Sony) * 4--8 60368ad4a33SUladzislau Rezki (Sony) * /\ 60468ad4a33SUladzislau Rezki (Sony) * / \ 60568ad4a33SUladzislau Rezki (Sony) * / \ 60668ad4a33SUladzislau Rezki (Sony) * 2--2 8--8 60768ad4a33SUladzislau Rezki (Sony) * 60868ad4a33SUladzislau Rezki (Sony) * For example if we modify the node 4, shrinking it to 2, then 60968ad4a33SUladzislau Rezki (Sony) * no any modification is required. If we shrink the node 2 to 1 61068ad4a33SUladzislau Rezki (Sony) * its subtree_max_size is updated only, and set to 1. If we shrink 61168ad4a33SUladzislau Rezki (Sony) * the node 8 to 6, then its subtree_max_size is set to 6 and parent 61268ad4a33SUladzislau Rezki (Sony) * node becomes 4--6. 61368ad4a33SUladzislau Rezki (Sony) */ 61468ad4a33SUladzislau Rezki (Sony) static __always_inline void 61568ad4a33SUladzislau Rezki (Sony) augment_tree_propagate_from(struct vmap_area *va) 61668ad4a33SUladzislau Rezki (Sony) { 61768ad4a33SUladzislau Rezki (Sony) struct rb_node *node = &va->rb_node; 61868ad4a33SUladzislau Rezki (Sony) unsigned long new_va_sub_max_size; 61968ad4a33SUladzislau Rezki (Sony) 62068ad4a33SUladzislau Rezki (Sony) while (node) { 62168ad4a33SUladzislau Rezki (Sony) va = rb_entry(node, struct vmap_area, rb_node); 62268ad4a33SUladzislau Rezki (Sony) new_va_sub_max_size = compute_subtree_max_size(va); 62368ad4a33SUladzislau Rezki (Sony) 62468ad4a33SUladzislau Rezki (Sony) /* 62568ad4a33SUladzislau Rezki (Sony) * If the newly calculated maximum available size of the 62668ad4a33SUladzislau Rezki (Sony) * subtree is equal to the current one, then it means that 62768ad4a33SUladzislau Rezki (Sony) * the tree is propagated correctly. So we have to stop at 62868ad4a33SUladzislau Rezki (Sony) * this point to save cycles. 62968ad4a33SUladzislau Rezki (Sony) */ 63068ad4a33SUladzislau Rezki (Sony) if (va->subtree_max_size == new_va_sub_max_size) 63168ad4a33SUladzislau Rezki (Sony) break; 63268ad4a33SUladzislau Rezki (Sony) 63368ad4a33SUladzislau Rezki (Sony) va->subtree_max_size = new_va_sub_max_size; 63468ad4a33SUladzislau Rezki (Sony) node = rb_parent(&va->rb_node); 63568ad4a33SUladzislau Rezki (Sony) } 636bb850f4dSUladzislau Rezki (Sony) 637bb850f4dSUladzislau Rezki (Sony) #if DEBUG_AUGMENT_PROPAGATE_CHECK 638bb850f4dSUladzislau Rezki (Sony) augment_tree_propagate_check(free_vmap_area_root.rb_node); 639bb850f4dSUladzislau Rezki (Sony) #endif 64068ad4a33SUladzislau Rezki (Sony) } 64168ad4a33SUladzislau Rezki (Sony) 64268ad4a33SUladzislau Rezki (Sony) static void 64368ad4a33SUladzislau Rezki (Sony) insert_vmap_area(struct vmap_area *va, 64468ad4a33SUladzislau Rezki (Sony) struct rb_root *root, struct list_head *head) 64568ad4a33SUladzislau Rezki (Sony) { 64668ad4a33SUladzislau Rezki (Sony) struct rb_node **link; 64768ad4a33SUladzislau Rezki (Sony) struct rb_node *parent; 64868ad4a33SUladzislau Rezki (Sony) 64968ad4a33SUladzislau Rezki (Sony) link = find_va_links(va, root, NULL, &parent); 65068ad4a33SUladzislau Rezki (Sony) link_va(va, root, parent, link, head); 65168ad4a33SUladzislau Rezki (Sony) } 65268ad4a33SUladzislau Rezki (Sony) 65368ad4a33SUladzislau Rezki (Sony) static void 65468ad4a33SUladzislau Rezki (Sony) insert_vmap_area_augment(struct vmap_area *va, 65568ad4a33SUladzislau Rezki (Sony) struct rb_node *from, struct rb_root *root, 65668ad4a33SUladzislau Rezki (Sony) struct list_head *head) 65768ad4a33SUladzislau Rezki (Sony) { 65868ad4a33SUladzislau Rezki (Sony) struct rb_node **link; 65968ad4a33SUladzislau Rezki (Sony) struct rb_node *parent; 66068ad4a33SUladzislau Rezki (Sony) 66168ad4a33SUladzislau Rezki (Sony) if (from) 66268ad4a33SUladzislau Rezki (Sony) link = find_va_links(va, NULL, from, &parent); 66368ad4a33SUladzislau Rezki (Sony) else 66468ad4a33SUladzislau Rezki (Sony) link = find_va_links(va, root, NULL, &parent); 66568ad4a33SUladzislau Rezki (Sony) 66668ad4a33SUladzislau Rezki (Sony) link_va(va, root, parent, link, head); 66768ad4a33SUladzislau Rezki (Sony) augment_tree_propagate_from(va); 66868ad4a33SUladzislau Rezki (Sony) } 66968ad4a33SUladzislau Rezki (Sony) 67068ad4a33SUladzislau Rezki (Sony) /* 67168ad4a33SUladzislau Rezki (Sony) * Merge de-allocated chunk of VA memory with previous 67268ad4a33SUladzislau Rezki (Sony) * and next free blocks. If coalesce is not done a new 67368ad4a33SUladzislau Rezki (Sony) * free area is inserted. If VA has been merged, it is 67468ad4a33SUladzislau Rezki (Sony) * freed. 67568ad4a33SUladzislau Rezki (Sony) */ 67668ad4a33SUladzislau Rezki (Sony) static __always_inline void 67768ad4a33SUladzislau Rezki (Sony) merge_or_add_vmap_area(struct vmap_area *va, 67868ad4a33SUladzislau Rezki (Sony) struct rb_root *root, struct list_head *head) 67968ad4a33SUladzislau Rezki (Sony) { 68068ad4a33SUladzislau Rezki (Sony) struct vmap_area *sibling; 68168ad4a33SUladzislau Rezki (Sony) struct list_head *next; 68268ad4a33SUladzislau Rezki (Sony) struct rb_node **link; 68368ad4a33SUladzislau Rezki (Sony) struct rb_node *parent; 68468ad4a33SUladzislau Rezki (Sony) bool merged = false; 68568ad4a33SUladzislau Rezki (Sony) 68668ad4a33SUladzislau Rezki (Sony) /* 68768ad4a33SUladzislau Rezki (Sony) * Find a place in the tree where VA potentially will be 68868ad4a33SUladzislau Rezki (Sony) * inserted, unless it is merged with its sibling/siblings. 68968ad4a33SUladzislau Rezki (Sony) */ 69068ad4a33SUladzislau Rezki (Sony) link = find_va_links(va, root, NULL, &parent); 69168ad4a33SUladzislau Rezki (Sony) 69268ad4a33SUladzislau Rezki (Sony) /* 69368ad4a33SUladzislau Rezki (Sony) * Get next node of VA to check if merging can be done. 69468ad4a33SUladzislau Rezki (Sony) */ 69568ad4a33SUladzislau Rezki (Sony) next = get_va_next_sibling(parent, link); 69668ad4a33SUladzislau Rezki (Sony) if (unlikely(next == NULL)) 69768ad4a33SUladzislau Rezki (Sony) goto insert; 69868ad4a33SUladzislau Rezki (Sony) 69968ad4a33SUladzislau Rezki (Sony) /* 70068ad4a33SUladzislau Rezki (Sony) * start end 70168ad4a33SUladzislau Rezki (Sony) * | | 70268ad4a33SUladzislau Rezki (Sony) * |<------VA------>|<-----Next----->| 70368ad4a33SUladzislau Rezki (Sony) * | | 70468ad4a33SUladzislau Rezki (Sony) * start end 70568ad4a33SUladzislau Rezki (Sony) */ 70668ad4a33SUladzislau Rezki (Sony) if (next != head) { 70768ad4a33SUladzislau Rezki (Sony) sibling = list_entry(next, struct vmap_area, list); 70868ad4a33SUladzislau Rezki (Sony) if (sibling->va_start == va->va_end) { 70968ad4a33SUladzislau Rezki (Sony) sibling->va_start = va->va_start; 71068ad4a33SUladzislau Rezki (Sony) 71168ad4a33SUladzislau Rezki (Sony) /* Check and update the tree if needed. */ 71268ad4a33SUladzislau Rezki (Sony) augment_tree_propagate_from(sibling); 71368ad4a33SUladzislau Rezki (Sony) 71468ad4a33SUladzislau Rezki (Sony) /* Remove this VA, it has been merged. */ 71568ad4a33SUladzislau Rezki (Sony) unlink_va(va, root); 71668ad4a33SUladzislau Rezki (Sony) 71768ad4a33SUladzislau Rezki (Sony) /* Free vmap_area object. */ 71868ad4a33SUladzislau Rezki (Sony) kmem_cache_free(vmap_area_cachep, va); 71968ad4a33SUladzislau Rezki (Sony) 72068ad4a33SUladzislau Rezki (Sony) /* Point to the new merged area. */ 72168ad4a33SUladzislau Rezki (Sony) va = sibling; 72268ad4a33SUladzislau Rezki (Sony) merged = true; 72368ad4a33SUladzislau Rezki (Sony) } 72468ad4a33SUladzislau Rezki (Sony) } 72568ad4a33SUladzislau Rezki (Sony) 72668ad4a33SUladzislau Rezki (Sony) /* 72768ad4a33SUladzislau Rezki (Sony) * start end 72868ad4a33SUladzislau Rezki (Sony) * | | 72968ad4a33SUladzislau Rezki (Sony) * |<-----Prev----->|<------VA------>| 73068ad4a33SUladzislau Rezki (Sony) * | | 73168ad4a33SUladzislau Rezki (Sony) * start end 73268ad4a33SUladzislau Rezki (Sony) */ 73368ad4a33SUladzislau Rezki (Sony) if (next->prev != head) { 73468ad4a33SUladzislau Rezki (Sony) sibling = list_entry(next->prev, struct vmap_area, list); 73568ad4a33SUladzislau Rezki (Sony) if (sibling->va_end == va->va_start) { 73668ad4a33SUladzislau Rezki (Sony) sibling->va_end = va->va_end; 73768ad4a33SUladzislau Rezki (Sony) 73868ad4a33SUladzislau Rezki (Sony) /* Check and update the tree if needed. */ 73968ad4a33SUladzislau Rezki (Sony) augment_tree_propagate_from(sibling); 74068ad4a33SUladzislau Rezki (Sony) 74168ad4a33SUladzislau Rezki (Sony) /* Remove this VA, it has been merged. */ 74268ad4a33SUladzislau Rezki (Sony) unlink_va(va, root); 74368ad4a33SUladzislau Rezki (Sony) 74468ad4a33SUladzislau Rezki (Sony) /* Free vmap_area object. */ 74568ad4a33SUladzislau Rezki (Sony) kmem_cache_free(vmap_area_cachep, va); 74668ad4a33SUladzislau Rezki (Sony) 74768ad4a33SUladzislau Rezki (Sony) return; 74868ad4a33SUladzislau Rezki (Sony) } 74968ad4a33SUladzislau Rezki (Sony) } 75068ad4a33SUladzislau Rezki (Sony) 75168ad4a33SUladzislau Rezki (Sony) insert: 75268ad4a33SUladzislau Rezki (Sony) if (!merged) { 75368ad4a33SUladzislau Rezki (Sony) link_va(va, root, parent, link, head); 75468ad4a33SUladzislau Rezki (Sony) augment_tree_propagate_from(va); 75568ad4a33SUladzislau Rezki (Sony) } 75668ad4a33SUladzislau Rezki (Sony) } 75768ad4a33SUladzislau Rezki (Sony) 75868ad4a33SUladzislau Rezki (Sony) static __always_inline bool 75968ad4a33SUladzislau Rezki (Sony) is_within_this_va(struct vmap_area *va, unsigned long size, 76068ad4a33SUladzislau Rezki (Sony) unsigned long align, unsigned long vstart) 76168ad4a33SUladzislau Rezki (Sony) { 76268ad4a33SUladzislau Rezki (Sony) unsigned long nva_start_addr; 76368ad4a33SUladzislau Rezki (Sony) 76468ad4a33SUladzislau Rezki (Sony) if (va->va_start > vstart) 76568ad4a33SUladzislau Rezki (Sony) nva_start_addr = ALIGN(va->va_start, align); 76668ad4a33SUladzislau Rezki (Sony) else 76768ad4a33SUladzislau Rezki (Sony) nva_start_addr = ALIGN(vstart, align); 76868ad4a33SUladzislau Rezki (Sony) 76968ad4a33SUladzislau Rezki (Sony) /* Can be overflowed due to big size or alignment. */ 77068ad4a33SUladzislau Rezki (Sony) if (nva_start_addr + size < nva_start_addr || 77168ad4a33SUladzislau Rezki (Sony) nva_start_addr < vstart) 77268ad4a33SUladzislau Rezki (Sony) return false; 77368ad4a33SUladzislau Rezki (Sony) 77468ad4a33SUladzislau Rezki (Sony) return (nva_start_addr + size <= va->va_end); 77568ad4a33SUladzislau Rezki (Sony) } 77668ad4a33SUladzislau Rezki (Sony) 77768ad4a33SUladzislau Rezki (Sony) /* 77868ad4a33SUladzislau Rezki (Sony) * Find the first free block(lowest start address) in the tree, 77968ad4a33SUladzislau Rezki (Sony) * that will accomplish the request corresponding to passing 78068ad4a33SUladzislau Rezki (Sony) * parameters. 78168ad4a33SUladzislau Rezki (Sony) */ 78268ad4a33SUladzislau Rezki (Sony) static __always_inline struct vmap_area * 78368ad4a33SUladzislau Rezki (Sony) find_vmap_lowest_match(unsigned long size, 78468ad4a33SUladzislau Rezki (Sony) unsigned long align, unsigned long vstart) 78568ad4a33SUladzislau Rezki (Sony) { 78668ad4a33SUladzislau Rezki (Sony) struct vmap_area *va; 78768ad4a33SUladzislau Rezki (Sony) struct rb_node *node; 78868ad4a33SUladzislau Rezki (Sony) unsigned long length; 78968ad4a33SUladzislau Rezki (Sony) 79068ad4a33SUladzislau Rezki (Sony) /* Start from the root. */ 79168ad4a33SUladzislau Rezki (Sony) node = free_vmap_area_root.rb_node; 79268ad4a33SUladzislau Rezki (Sony) 79368ad4a33SUladzislau Rezki (Sony) /* Adjust the search size for alignment overhead. */ 79468ad4a33SUladzislau Rezki (Sony) length = size + align - 1; 79568ad4a33SUladzislau Rezki (Sony) 79668ad4a33SUladzislau Rezki (Sony) while (node) { 79768ad4a33SUladzislau Rezki (Sony) va = rb_entry(node, struct vmap_area, rb_node); 79868ad4a33SUladzislau Rezki (Sony) 79968ad4a33SUladzislau Rezki (Sony) if (get_subtree_max_size(node->rb_left) >= length && 80068ad4a33SUladzislau Rezki (Sony) vstart < va->va_start) { 80168ad4a33SUladzislau Rezki (Sony) node = node->rb_left; 80268ad4a33SUladzislau Rezki (Sony) } else { 80368ad4a33SUladzislau Rezki (Sony) if (is_within_this_va(va, size, align, vstart)) 80468ad4a33SUladzislau Rezki (Sony) return va; 80568ad4a33SUladzislau Rezki (Sony) 80668ad4a33SUladzislau Rezki (Sony) /* 80768ad4a33SUladzislau Rezki (Sony) * Does not make sense to go deeper towards the right 80868ad4a33SUladzislau Rezki (Sony) * sub-tree if it does not have a free block that is 80968ad4a33SUladzislau Rezki (Sony) * equal or bigger to the requested search length. 81068ad4a33SUladzislau Rezki (Sony) */ 81168ad4a33SUladzislau Rezki (Sony) if (get_subtree_max_size(node->rb_right) >= length) { 81268ad4a33SUladzislau Rezki (Sony) node = node->rb_right; 81368ad4a33SUladzislau Rezki (Sony) continue; 81468ad4a33SUladzislau Rezki (Sony) } 81568ad4a33SUladzislau Rezki (Sony) 81668ad4a33SUladzislau Rezki (Sony) /* 81768ad4a33SUladzislau Rezki (Sony) * OK. We roll back and find the fist right sub-tree, 81868ad4a33SUladzislau Rezki (Sony) * that will satisfy the search criteria. It can happen 81968ad4a33SUladzislau Rezki (Sony) * only once due to "vstart" restriction. 82068ad4a33SUladzislau Rezki (Sony) */ 82168ad4a33SUladzislau Rezki (Sony) while ((node = rb_parent(node))) { 82268ad4a33SUladzislau Rezki (Sony) va = rb_entry(node, struct vmap_area, rb_node); 82368ad4a33SUladzislau Rezki (Sony) if (is_within_this_va(va, size, align, vstart)) 82468ad4a33SUladzislau Rezki (Sony) return va; 82568ad4a33SUladzislau Rezki (Sony) 82668ad4a33SUladzislau Rezki (Sony) if (get_subtree_max_size(node->rb_right) >= length && 82768ad4a33SUladzislau Rezki (Sony) vstart <= va->va_start) { 82868ad4a33SUladzislau Rezki (Sony) node = node->rb_right; 82968ad4a33SUladzislau Rezki (Sony) break; 83068ad4a33SUladzislau Rezki (Sony) } 83168ad4a33SUladzislau Rezki (Sony) } 83268ad4a33SUladzislau Rezki (Sony) } 83368ad4a33SUladzislau Rezki (Sony) } 83468ad4a33SUladzislau Rezki (Sony) 83568ad4a33SUladzislau Rezki (Sony) return NULL; 83668ad4a33SUladzislau Rezki (Sony) } 83768ad4a33SUladzislau Rezki (Sony) 838*a6cf4e0fSUladzislau Rezki (Sony) #if DEBUG_AUGMENT_LOWEST_MATCH_CHECK 839*a6cf4e0fSUladzislau Rezki (Sony) #include <linux/random.h> 840*a6cf4e0fSUladzislau Rezki (Sony) 841*a6cf4e0fSUladzislau Rezki (Sony) static struct vmap_area * 842*a6cf4e0fSUladzislau Rezki (Sony) find_vmap_lowest_linear_match(unsigned long size, 843*a6cf4e0fSUladzislau Rezki (Sony) unsigned long align, unsigned long vstart) 844*a6cf4e0fSUladzislau Rezki (Sony) { 845*a6cf4e0fSUladzislau Rezki (Sony) struct vmap_area *va; 846*a6cf4e0fSUladzislau Rezki (Sony) 847*a6cf4e0fSUladzislau Rezki (Sony) list_for_each_entry(va, &free_vmap_area_list, list) { 848*a6cf4e0fSUladzislau Rezki (Sony) if (!is_within_this_va(va, size, align, vstart)) 849*a6cf4e0fSUladzislau Rezki (Sony) continue; 850*a6cf4e0fSUladzislau Rezki (Sony) 851*a6cf4e0fSUladzislau Rezki (Sony) return va; 852*a6cf4e0fSUladzislau Rezki (Sony) } 853*a6cf4e0fSUladzislau Rezki (Sony) 854*a6cf4e0fSUladzislau Rezki (Sony) return NULL; 855*a6cf4e0fSUladzislau Rezki (Sony) } 856*a6cf4e0fSUladzislau Rezki (Sony) 857*a6cf4e0fSUladzislau Rezki (Sony) static void 858*a6cf4e0fSUladzislau Rezki (Sony) find_vmap_lowest_match_check(unsigned long size) 859*a6cf4e0fSUladzislau Rezki (Sony) { 860*a6cf4e0fSUladzislau Rezki (Sony) struct vmap_area *va_1, *va_2; 861*a6cf4e0fSUladzislau Rezki (Sony) unsigned long vstart; 862*a6cf4e0fSUladzislau Rezki (Sony) unsigned int rnd; 863*a6cf4e0fSUladzislau Rezki (Sony) 864*a6cf4e0fSUladzislau Rezki (Sony) get_random_bytes(&rnd, sizeof(rnd)); 865*a6cf4e0fSUladzislau Rezki (Sony) vstart = VMALLOC_START + rnd; 866*a6cf4e0fSUladzislau Rezki (Sony) 867*a6cf4e0fSUladzislau Rezki (Sony) va_1 = find_vmap_lowest_match(size, 1, vstart); 868*a6cf4e0fSUladzislau Rezki (Sony) va_2 = find_vmap_lowest_linear_match(size, 1, vstart); 869*a6cf4e0fSUladzislau Rezki (Sony) 870*a6cf4e0fSUladzislau Rezki (Sony) if (va_1 != va_2) 871*a6cf4e0fSUladzislau Rezki (Sony) pr_emerg("not lowest: t: 0x%p, l: 0x%p, v: 0x%lx\n", 872*a6cf4e0fSUladzislau Rezki (Sony) va_1, va_2, vstart); 873*a6cf4e0fSUladzislau Rezki (Sony) } 874*a6cf4e0fSUladzislau Rezki (Sony) #endif 875*a6cf4e0fSUladzislau Rezki (Sony) 87668ad4a33SUladzislau Rezki (Sony) enum fit_type { 87768ad4a33SUladzislau Rezki (Sony) NOTHING_FIT = 0, 87868ad4a33SUladzislau Rezki (Sony) FL_FIT_TYPE = 1, /* full fit */ 87968ad4a33SUladzislau Rezki (Sony) LE_FIT_TYPE = 2, /* left edge fit */ 88068ad4a33SUladzislau Rezki (Sony) RE_FIT_TYPE = 3, /* right edge fit */ 88168ad4a33SUladzislau Rezki (Sony) NE_FIT_TYPE = 4 /* no edge fit */ 88268ad4a33SUladzislau Rezki (Sony) }; 88368ad4a33SUladzislau Rezki (Sony) 88468ad4a33SUladzislau Rezki (Sony) static __always_inline enum fit_type 88568ad4a33SUladzislau Rezki (Sony) classify_va_fit_type(struct vmap_area *va, 88668ad4a33SUladzislau Rezki (Sony) unsigned long nva_start_addr, unsigned long size) 88768ad4a33SUladzislau Rezki (Sony) { 88868ad4a33SUladzislau Rezki (Sony) enum fit_type type; 88968ad4a33SUladzislau Rezki (Sony) 89068ad4a33SUladzislau Rezki (Sony) /* Check if it is within VA. */ 89168ad4a33SUladzislau Rezki (Sony) if (nva_start_addr < va->va_start || 89268ad4a33SUladzislau Rezki (Sony) nva_start_addr + size > va->va_end) 89368ad4a33SUladzislau Rezki (Sony) return NOTHING_FIT; 89468ad4a33SUladzislau Rezki (Sony) 89568ad4a33SUladzislau Rezki (Sony) /* Now classify. */ 89668ad4a33SUladzislau Rezki (Sony) if (va->va_start == nva_start_addr) { 89768ad4a33SUladzislau Rezki (Sony) if (va->va_end == nva_start_addr + size) 89868ad4a33SUladzislau Rezki (Sony) type = FL_FIT_TYPE; 89968ad4a33SUladzislau Rezki (Sony) else 90068ad4a33SUladzislau Rezki (Sony) type = LE_FIT_TYPE; 90168ad4a33SUladzislau Rezki (Sony) } else if (va->va_end == nva_start_addr + size) { 90268ad4a33SUladzislau Rezki (Sony) type = RE_FIT_TYPE; 90368ad4a33SUladzislau Rezki (Sony) } else { 90468ad4a33SUladzislau Rezki (Sony) type = NE_FIT_TYPE; 90568ad4a33SUladzislau Rezki (Sony) } 90668ad4a33SUladzislau Rezki (Sony) 90768ad4a33SUladzislau Rezki (Sony) return type; 90868ad4a33SUladzislau Rezki (Sony) } 90968ad4a33SUladzislau Rezki (Sony) 91068ad4a33SUladzislau Rezki (Sony) static __always_inline int 91168ad4a33SUladzislau Rezki (Sony) adjust_va_to_fit_type(struct vmap_area *va, 91268ad4a33SUladzislau Rezki (Sony) unsigned long nva_start_addr, unsigned long size, 91368ad4a33SUladzislau Rezki (Sony) enum fit_type type) 91468ad4a33SUladzislau Rezki (Sony) { 91568ad4a33SUladzislau Rezki (Sony) struct vmap_area *lva; 91668ad4a33SUladzislau Rezki (Sony) 91768ad4a33SUladzislau Rezki (Sony) if (type == FL_FIT_TYPE) { 91868ad4a33SUladzislau Rezki (Sony) /* 91968ad4a33SUladzislau Rezki (Sony) * No need to split VA, it fully fits. 92068ad4a33SUladzislau Rezki (Sony) * 92168ad4a33SUladzislau Rezki (Sony) * | | 92268ad4a33SUladzislau Rezki (Sony) * V NVA V 92368ad4a33SUladzislau Rezki (Sony) * |---------------| 92468ad4a33SUladzislau Rezki (Sony) */ 92568ad4a33SUladzislau Rezki (Sony) unlink_va(va, &free_vmap_area_root); 92668ad4a33SUladzislau Rezki (Sony) kmem_cache_free(vmap_area_cachep, va); 92768ad4a33SUladzislau Rezki (Sony) } else if (type == LE_FIT_TYPE) { 92868ad4a33SUladzislau Rezki (Sony) /* 92968ad4a33SUladzislau Rezki (Sony) * Split left edge of fit VA. 93068ad4a33SUladzislau Rezki (Sony) * 93168ad4a33SUladzislau Rezki (Sony) * | | 93268ad4a33SUladzislau Rezki (Sony) * V NVA V R 93368ad4a33SUladzislau Rezki (Sony) * |-------|-------| 93468ad4a33SUladzislau Rezki (Sony) */ 93568ad4a33SUladzislau Rezki (Sony) va->va_start += size; 93668ad4a33SUladzislau Rezki (Sony) } else if (type == RE_FIT_TYPE) { 93768ad4a33SUladzislau Rezki (Sony) /* 93868ad4a33SUladzislau Rezki (Sony) * Split right edge of fit VA. 93968ad4a33SUladzislau Rezki (Sony) * 94068ad4a33SUladzislau Rezki (Sony) * | | 94168ad4a33SUladzislau Rezki (Sony) * L V NVA V 94268ad4a33SUladzislau Rezki (Sony) * |-------|-------| 94368ad4a33SUladzislau Rezki (Sony) */ 94468ad4a33SUladzislau Rezki (Sony) va->va_end = nva_start_addr; 94568ad4a33SUladzislau Rezki (Sony) } else if (type == NE_FIT_TYPE) { 94668ad4a33SUladzislau Rezki (Sony) /* 94768ad4a33SUladzislau Rezki (Sony) * Split no edge of fit VA. 94868ad4a33SUladzislau Rezki (Sony) * 94968ad4a33SUladzislau Rezki (Sony) * | | 95068ad4a33SUladzislau Rezki (Sony) * L V NVA V R 95168ad4a33SUladzislau Rezki (Sony) * |---|-------|---| 95268ad4a33SUladzislau Rezki (Sony) */ 95368ad4a33SUladzislau Rezki (Sony) lva = kmem_cache_alloc(vmap_area_cachep, GFP_NOWAIT); 95468ad4a33SUladzislau Rezki (Sony) if (unlikely(!lva)) 95568ad4a33SUladzislau Rezki (Sony) return -1; 95668ad4a33SUladzislau Rezki (Sony) 95768ad4a33SUladzislau Rezki (Sony) /* 95868ad4a33SUladzislau Rezki (Sony) * Build the remainder. 95968ad4a33SUladzislau Rezki (Sony) */ 96068ad4a33SUladzislau Rezki (Sony) lva->va_start = va->va_start; 96168ad4a33SUladzislau Rezki (Sony) lva->va_end = nva_start_addr; 96268ad4a33SUladzislau Rezki (Sony) 96368ad4a33SUladzislau Rezki (Sony) /* 96468ad4a33SUladzislau Rezki (Sony) * Shrink this VA to remaining size. 96568ad4a33SUladzislau Rezki (Sony) */ 96668ad4a33SUladzislau Rezki (Sony) va->va_start = nva_start_addr + size; 96768ad4a33SUladzislau Rezki (Sony) } else { 96868ad4a33SUladzislau Rezki (Sony) return -1; 96968ad4a33SUladzislau Rezki (Sony) } 97068ad4a33SUladzislau Rezki (Sony) 97168ad4a33SUladzislau Rezki (Sony) if (type != FL_FIT_TYPE) { 97268ad4a33SUladzislau Rezki (Sony) augment_tree_propagate_from(va); 97368ad4a33SUladzislau Rezki (Sony) 97468ad4a33SUladzislau Rezki (Sony) if (type == NE_FIT_TYPE) 97568ad4a33SUladzislau Rezki (Sony) insert_vmap_area_augment(lva, &va->rb_node, 97668ad4a33SUladzislau Rezki (Sony) &free_vmap_area_root, &free_vmap_area_list); 97768ad4a33SUladzislau Rezki (Sony) } 97868ad4a33SUladzislau Rezki (Sony) 97968ad4a33SUladzislau Rezki (Sony) return 0; 98068ad4a33SUladzislau Rezki (Sony) } 98168ad4a33SUladzislau Rezki (Sony) 98268ad4a33SUladzislau Rezki (Sony) /* 98368ad4a33SUladzislau Rezki (Sony) * Returns a start address of the newly allocated area, if success. 98468ad4a33SUladzislau Rezki (Sony) * Otherwise a vend is returned that indicates failure. 98568ad4a33SUladzislau Rezki (Sony) */ 98668ad4a33SUladzislau Rezki (Sony) static __always_inline unsigned long 98768ad4a33SUladzislau Rezki (Sony) __alloc_vmap_area(unsigned long size, unsigned long align, 98868ad4a33SUladzislau Rezki (Sony) unsigned long vstart, unsigned long vend, int node) 98968ad4a33SUladzislau Rezki (Sony) { 99068ad4a33SUladzislau Rezki (Sony) unsigned long nva_start_addr; 99168ad4a33SUladzislau Rezki (Sony) struct vmap_area *va; 99268ad4a33SUladzislau Rezki (Sony) enum fit_type type; 99368ad4a33SUladzislau Rezki (Sony) int ret; 99468ad4a33SUladzislau Rezki (Sony) 99568ad4a33SUladzislau Rezki (Sony) va = find_vmap_lowest_match(size, align, vstart); 99668ad4a33SUladzislau Rezki (Sony) if (unlikely(!va)) 99768ad4a33SUladzislau Rezki (Sony) return vend; 99868ad4a33SUladzislau Rezki (Sony) 99968ad4a33SUladzislau Rezki (Sony) if (va->va_start > vstart) 100068ad4a33SUladzislau Rezki (Sony) nva_start_addr = ALIGN(va->va_start, align); 100168ad4a33SUladzislau Rezki (Sony) else 100268ad4a33SUladzislau Rezki (Sony) nva_start_addr = ALIGN(vstart, align); 100368ad4a33SUladzislau Rezki (Sony) 100468ad4a33SUladzislau Rezki (Sony) /* Check the "vend" restriction. */ 100568ad4a33SUladzislau Rezki (Sony) if (nva_start_addr + size > vend) 100668ad4a33SUladzislau Rezki (Sony) return vend; 100768ad4a33SUladzislau Rezki (Sony) 100868ad4a33SUladzislau Rezki (Sony) /* Classify what we have found. */ 100968ad4a33SUladzislau Rezki (Sony) type = classify_va_fit_type(va, nva_start_addr, size); 101068ad4a33SUladzislau Rezki (Sony) if (WARN_ON_ONCE(type == NOTHING_FIT)) 101168ad4a33SUladzislau Rezki (Sony) return vend; 101268ad4a33SUladzislau Rezki (Sony) 101368ad4a33SUladzislau Rezki (Sony) /* Update the free vmap_area. */ 101468ad4a33SUladzislau Rezki (Sony) ret = adjust_va_to_fit_type(va, nva_start_addr, size, type); 101568ad4a33SUladzislau Rezki (Sony) if (ret) 101668ad4a33SUladzislau Rezki (Sony) return vend; 101768ad4a33SUladzislau Rezki (Sony) 1018*a6cf4e0fSUladzislau Rezki (Sony) #if DEBUG_AUGMENT_LOWEST_MATCH_CHECK 1019*a6cf4e0fSUladzislau Rezki (Sony) find_vmap_lowest_match_check(size); 1020*a6cf4e0fSUladzislau Rezki (Sony) #endif 1021*a6cf4e0fSUladzislau Rezki (Sony) 102268ad4a33SUladzislau Rezki (Sony) return nva_start_addr; 102368ad4a33SUladzislau Rezki (Sony) } 10244da56b99SChris Wilson 1025db64fe02SNick Piggin /* 1026db64fe02SNick Piggin * Allocate a region of KVA of the specified size and alignment, within the 1027db64fe02SNick Piggin * vstart and vend. 1028db64fe02SNick Piggin */ 1029db64fe02SNick Piggin static struct vmap_area *alloc_vmap_area(unsigned long size, 1030db64fe02SNick Piggin unsigned long align, 1031db64fe02SNick Piggin unsigned long vstart, unsigned long vend, 1032db64fe02SNick Piggin int node, gfp_t gfp_mask) 1033db64fe02SNick Piggin { 1034db64fe02SNick Piggin struct vmap_area *va; 10351da177e4SLinus Torvalds unsigned long addr; 1036db64fe02SNick Piggin int purged = 0; 1037db64fe02SNick Piggin 10387766970cSNick Piggin BUG_ON(!size); 1039891c49abSAlexander Kuleshov BUG_ON(offset_in_page(size)); 104089699605SNick Piggin BUG_ON(!is_power_of_2(align)); 1041db64fe02SNick Piggin 104268ad4a33SUladzislau Rezki (Sony) if (unlikely(!vmap_initialized)) 104368ad4a33SUladzislau Rezki (Sony) return ERR_PTR(-EBUSY); 104468ad4a33SUladzislau Rezki (Sony) 10455803ed29SChristoph Hellwig might_sleep(); 10464da56b99SChris Wilson 104768ad4a33SUladzislau Rezki (Sony) va = kmem_cache_alloc_node(vmap_area_cachep, 1048db64fe02SNick Piggin gfp_mask & GFP_RECLAIM_MASK, node); 1049db64fe02SNick Piggin if (unlikely(!va)) 1050db64fe02SNick Piggin return ERR_PTR(-ENOMEM); 1051db64fe02SNick Piggin 10527f88f88fSCatalin Marinas /* 10537f88f88fSCatalin Marinas * Only scan the relevant parts containing pointers to other objects 10547f88f88fSCatalin Marinas * to avoid false negatives. 10557f88f88fSCatalin Marinas */ 10567f88f88fSCatalin Marinas kmemleak_scan_area(&va->rb_node, SIZE_MAX, gfp_mask & GFP_RECLAIM_MASK); 10577f88f88fSCatalin Marinas 1058db64fe02SNick Piggin retry: 1059db64fe02SNick Piggin spin_lock(&vmap_area_lock); 106068ad4a33SUladzislau Rezki (Sony) 106189699605SNick Piggin /* 106268ad4a33SUladzislau Rezki (Sony) * If an allocation fails, the "vend" address is 106368ad4a33SUladzislau Rezki (Sony) * returned. Therefore trigger the overflow path. 106489699605SNick Piggin */ 106568ad4a33SUladzislau Rezki (Sony) addr = __alloc_vmap_area(size, align, vstart, vend, node); 106668ad4a33SUladzislau Rezki (Sony) if (unlikely(addr == vend)) 106789699605SNick Piggin goto overflow; 106889699605SNick Piggin 106989699605SNick Piggin va->va_start = addr; 107089699605SNick Piggin va->va_end = addr + size; 107189699605SNick Piggin va->flags = 0; 107268ad4a33SUladzislau Rezki (Sony) insert_vmap_area(va, &vmap_area_root, &vmap_area_list); 107368ad4a33SUladzislau Rezki (Sony) 107489699605SNick Piggin spin_unlock(&vmap_area_lock); 107589699605SNick Piggin 107661e16557SWang Xiaoqiang BUG_ON(!IS_ALIGNED(va->va_start, align)); 107789699605SNick Piggin BUG_ON(va->va_start < vstart); 107889699605SNick Piggin BUG_ON(va->va_end > vend); 107989699605SNick Piggin 108089699605SNick Piggin return va; 108189699605SNick Piggin 10827766970cSNick Piggin overflow: 1083db64fe02SNick Piggin spin_unlock(&vmap_area_lock); 1084db64fe02SNick Piggin if (!purged) { 1085db64fe02SNick Piggin purge_vmap_area_lazy(); 1086db64fe02SNick Piggin purged = 1; 1087db64fe02SNick Piggin goto retry; 1088db64fe02SNick Piggin } 10894da56b99SChris Wilson 10904da56b99SChris Wilson if (gfpflags_allow_blocking(gfp_mask)) { 10914da56b99SChris Wilson unsigned long freed = 0; 10924da56b99SChris Wilson blocking_notifier_call_chain(&vmap_notify_list, 0, &freed); 10934da56b99SChris Wilson if (freed > 0) { 10944da56b99SChris Wilson purged = 0; 10954da56b99SChris Wilson goto retry; 10964da56b99SChris Wilson } 10974da56b99SChris Wilson } 10984da56b99SChris Wilson 109903497d76SFlorian Fainelli if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) 1100756a025fSJoe Perches pr_warn("vmap allocation for size %lu failed: use vmalloc=<size> to increase size\n", 1101756a025fSJoe Perches size); 110268ad4a33SUladzislau Rezki (Sony) 110368ad4a33SUladzislau Rezki (Sony) kmem_cache_free(vmap_area_cachep, va); 1104db64fe02SNick Piggin return ERR_PTR(-EBUSY); 1105db64fe02SNick Piggin } 1106db64fe02SNick Piggin 11074da56b99SChris Wilson int register_vmap_purge_notifier(struct notifier_block *nb) 11084da56b99SChris Wilson { 11094da56b99SChris Wilson return blocking_notifier_chain_register(&vmap_notify_list, nb); 11104da56b99SChris Wilson } 11114da56b99SChris Wilson EXPORT_SYMBOL_GPL(register_vmap_purge_notifier); 11124da56b99SChris Wilson 11134da56b99SChris Wilson int unregister_vmap_purge_notifier(struct notifier_block *nb) 11144da56b99SChris Wilson { 11154da56b99SChris Wilson return blocking_notifier_chain_unregister(&vmap_notify_list, nb); 11164da56b99SChris Wilson } 11174da56b99SChris Wilson EXPORT_SYMBOL_GPL(unregister_vmap_purge_notifier); 11184da56b99SChris Wilson 1119db64fe02SNick Piggin static void __free_vmap_area(struct vmap_area *va) 1120db64fe02SNick Piggin { 1121db64fe02SNick Piggin BUG_ON(RB_EMPTY_NODE(&va->rb_node)); 112289699605SNick Piggin 112389699605SNick Piggin /* 112468ad4a33SUladzislau Rezki (Sony) * Remove from the busy tree/list. 112589699605SNick Piggin */ 112668ad4a33SUladzislau Rezki (Sony) unlink_va(va, &vmap_area_root); 1127db64fe02SNick Piggin 1128ca23e405STejun Heo /* 112968ad4a33SUladzislau Rezki (Sony) * Merge VA with its neighbors, otherwise just add it. 1130ca23e405STejun Heo */ 113168ad4a33SUladzislau Rezki (Sony) merge_or_add_vmap_area(va, 113268ad4a33SUladzislau Rezki (Sony) &free_vmap_area_root, &free_vmap_area_list); 1133db64fe02SNick Piggin } 1134db64fe02SNick Piggin 1135db64fe02SNick Piggin /* 1136db64fe02SNick Piggin * Free a region of KVA allocated by alloc_vmap_area 1137db64fe02SNick Piggin */ 1138db64fe02SNick Piggin static void free_vmap_area(struct vmap_area *va) 1139db64fe02SNick Piggin { 1140db64fe02SNick Piggin spin_lock(&vmap_area_lock); 1141db64fe02SNick Piggin __free_vmap_area(va); 1142db64fe02SNick Piggin spin_unlock(&vmap_area_lock); 1143db64fe02SNick Piggin } 1144db64fe02SNick Piggin 1145db64fe02SNick Piggin /* 1146db64fe02SNick Piggin * Clear the pagetable entries of a given vmap_area 1147db64fe02SNick Piggin */ 1148db64fe02SNick Piggin static void unmap_vmap_area(struct vmap_area *va) 1149db64fe02SNick Piggin { 1150db64fe02SNick Piggin vunmap_page_range(va->va_start, va->va_end); 1151db64fe02SNick Piggin } 1152db64fe02SNick Piggin 1153db64fe02SNick Piggin /* 1154db64fe02SNick Piggin * lazy_max_pages is the maximum amount of virtual address space we gather up 1155db64fe02SNick Piggin * before attempting to purge with a TLB flush. 1156db64fe02SNick Piggin * 1157db64fe02SNick Piggin * There is a tradeoff here: a larger number will cover more kernel page tables 1158db64fe02SNick Piggin * and take slightly longer to purge, but it will linearly reduce the number of 1159db64fe02SNick Piggin * global TLB flushes that must be performed. It would seem natural to scale 1160db64fe02SNick Piggin * this number up linearly with the number of CPUs (because vmapping activity 1161db64fe02SNick Piggin * could also scale linearly with the number of CPUs), however it is likely 1162db64fe02SNick Piggin * that in practice, workloads might be constrained in other ways that mean 1163db64fe02SNick Piggin * vmap activity will not scale linearly with CPUs. Also, I want to be 1164db64fe02SNick Piggin * conservative and not introduce a big latency on huge systems, so go with 1165db64fe02SNick Piggin * a less aggressive log scale. It will still be an improvement over the old 1166db64fe02SNick Piggin * code, and it will be simple to change the scale factor if we find that it 1167db64fe02SNick Piggin * becomes a problem on bigger systems. 1168db64fe02SNick Piggin */ 1169db64fe02SNick Piggin static unsigned long lazy_max_pages(void) 1170db64fe02SNick Piggin { 1171db64fe02SNick Piggin unsigned int log; 1172db64fe02SNick Piggin 1173db64fe02SNick Piggin log = fls(num_online_cpus()); 1174db64fe02SNick Piggin 1175db64fe02SNick Piggin return log * (32UL * 1024 * 1024 / PAGE_SIZE); 1176db64fe02SNick Piggin } 1177db64fe02SNick Piggin 11784d36e6f8SUladzislau Rezki (Sony) static atomic_long_t vmap_lazy_nr = ATOMIC_LONG_INIT(0); 1179db64fe02SNick Piggin 11800574ecd1SChristoph Hellwig /* 11810574ecd1SChristoph Hellwig * Serialize vmap purging. There is no actual criticial section protected 11820574ecd1SChristoph Hellwig * by this look, but we want to avoid concurrent calls for performance 11830574ecd1SChristoph Hellwig * reasons and to make the pcpu_get_vm_areas more deterministic. 11840574ecd1SChristoph Hellwig */ 1185f9e09977SChristoph Hellwig static DEFINE_MUTEX(vmap_purge_lock); 11860574ecd1SChristoph Hellwig 118702b709dfSNick Piggin /* for per-CPU blocks */ 118802b709dfSNick Piggin static void purge_fragmented_blocks_allcpus(void); 118902b709dfSNick Piggin 1190db64fe02SNick Piggin /* 11913ee48b6aSCliff Wickman * called before a call to iounmap() if the caller wants vm_area_struct's 11923ee48b6aSCliff Wickman * immediately freed. 11933ee48b6aSCliff Wickman */ 11943ee48b6aSCliff Wickman void set_iounmap_nonlazy(void) 11953ee48b6aSCliff Wickman { 11964d36e6f8SUladzislau Rezki (Sony) atomic_long_set(&vmap_lazy_nr, lazy_max_pages()+1); 11973ee48b6aSCliff Wickman } 11983ee48b6aSCliff Wickman 11993ee48b6aSCliff Wickman /* 1200db64fe02SNick Piggin * Purges all lazily-freed vmap areas. 1201db64fe02SNick Piggin */ 12020574ecd1SChristoph Hellwig static bool __purge_vmap_area_lazy(unsigned long start, unsigned long end) 1203db64fe02SNick Piggin { 12044d36e6f8SUladzislau Rezki (Sony) unsigned long resched_threshold; 120580c4bd7aSChris Wilson struct llist_node *valist; 1206db64fe02SNick Piggin struct vmap_area *va; 1207cbb76676SVegard Nossum struct vmap_area *n_va; 1208db64fe02SNick Piggin 12090574ecd1SChristoph Hellwig lockdep_assert_held(&vmap_purge_lock); 121002b709dfSNick Piggin 121180c4bd7aSChris Wilson valist = llist_del_all(&vmap_purge_list); 121268571be9SUladzislau Rezki (Sony) if (unlikely(valist == NULL)) 121368571be9SUladzislau Rezki (Sony) return false; 121468571be9SUladzislau Rezki (Sony) 121568571be9SUladzislau Rezki (Sony) /* 121668571be9SUladzislau Rezki (Sony) * TODO: to calculate a flush range without looping. 121768571be9SUladzislau Rezki (Sony) * The list can be up to lazy_max_pages() elements. 121868571be9SUladzislau Rezki (Sony) */ 121980c4bd7aSChris Wilson llist_for_each_entry(va, valist, purge_list) { 12200574ecd1SChristoph Hellwig if (va->va_start < start) 12210574ecd1SChristoph Hellwig start = va->va_start; 12220574ecd1SChristoph Hellwig if (va->va_end > end) 12230574ecd1SChristoph Hellwig end = va->va_end; 1224db64fe02SNick Piggin } 1225db64fe02SNick Piggin 12260574ecd1SChristoph Hellwig flush_tlb_kernel_range(start, end); 12274d36e6f8SUladzislau Rezki (Sony) resched_threshold = lazy_max_pages() << 1; 1228db64fe02SNick Piggin 1229db64fe02SNick Piggin spin_lock(&vmap_area_lock); 1230763b218dSJoel Fernandes llist_for_each_entry_safe(va, n_va, valist, purge_list) { 12314d36e6f8SUladzislau Rezki (Sony) unsigned long nr = (va->va_end - va->va_start) >> PAGE_SHIFT; 1232763b218dSJoel Fernandes 1233db64fe02SNick Piggin __free_vmap_area(va); 12344d36e6f8SUladzislau Rezki (Sony) atomic_long_sub(nr, &vmap_lazy_nr); 123568571be9SUladzislau Rezki (Sony) 12364d36e6f8SUladzislau Rezki (Sony) if (atomic_long_read(&vmap_lazy_nr) < resched_threshold) 1237763b218dSJoel Fernandes cond_resched_lock(&vmap_area_lock); 1238763b218dSJoel Fernandes } 1239db64fe02SNick Piggin spin_unlock(&vmap_area_lock); 12400574ecd1SChristoph Hellwig return true; 1241db64fe02SNick Piggin } 1242db64fe02SNick Piggin 1243db64fe02SNick Piggin /* 1244496850e5SNick Piggin * Kick off a purge of the outstanding lazy areas. Don't bother if somebody 1245496850e5SNick Piggin * is already purging. 1246496850e5SNick Piggin */ 1247496850e5SNick Piggin static void try_purge_vmap_area_lazy(void) 1248496850e5SNick Piggin { 1249f9e09977SChristoph Hellwig if (mutex_trylock(&vmap_purge_lock)) { 12500574ecd1SChristoph Hellwig __purge_vmap_area_lazy(ULONG_MAX, 0); 1251f9e09977SChristoph Hellwig mutex_unlock(&vmap_purge_lock); 12520574ecd1SChristoph Hellwig } 1253496850e5SNick Piggin } 1254496850e5SNick Piggin 1255496850e5SNick Piggin /* 1256db64fe02SNick Piggin * Kick off a purge of the outstanding lazy areas. 1257db64fe02SNick Piggin */ 1258db64fe02SNick Piggin static void purge_vmap_area_lazy(void) 1259db64fe02SNick Piggin { 1260f9e09977SChristoph Hellwig mutex_lock(&vmap_purge_lock); 12610574ecd1SChristoph Hellwig purge_fragmented_blocks_allcpus(); 12620574ecd1SChristoph Hellwig __purge_vmap_area_lazy(ULONG_MAX, 0); 1263f9e09977SChristoph Hellwig mutex_unlock(&vmap_purge_lock); 1264db64fe02SNick Piggin } 1265db64fe02SNick Piggin 1266db64fe02SNick Piggin /* 126764141da5SJeremy Fitzhardinge * Free a vmap area, caller ensuring that the area has been unmapped 126864141da5SJeremy Fitzhardinge * and flush_cache_vunmap had been called for the correct range 126964141da5SJeremy Fitzhardinge * previously. 1270db64fe02SNick Piggin */ 127164141da5SJeremy Fitzhardinge static void free_vmap_area_noflush(struct vmap_area *va) 1272db64fe02SNick Piggin { 12734d36e6f8SUladzislau Rezki (Sony) unsigned long nr_lazy; 127480c4bd7aSChris Wilson 12754d36e6f8SUladzislau Rezki (Sony) nr_lazy = atomic_long_add_return((va->va_end - va->va_start) >> 12764d36e6f8SUladzislau Rezki (Sony) PAGE_SHIFT, &vmap_lazy_nr); 127780c4bd7aSChris Wilson 127880c4bd7aSChris Wilson /* After this point, we may free va at any time */ 127980c4bd7aSChris Wilson llist_add(&va->purge_list, &vmap_purge_list); 128080c4bd7aSChris Wilson 128180c4bd7aSChris Wilson if (unlikely(nr_lazy > lazy_max_pages())) 1282496850e5SNick Piggin try_purge_vmap_area_lazy(); 1283db64fe02SNick Piggin } 1284db64fe02SNick Piggin 1285b29acbdcSNick Piggin /* 1286b29acbdcSNick Piggin * Free and unmap a vmap area 1287b29acbdcSNick Piggin */ 1288b29acbdcSNick Piggin static void free_unmap_vmap_area(struct vmap_area *va) 1289b29acbdcSNick Piggin { 1290b29acbdcSNick Piggin flush_cache_vunmap(va->va_start, va->va_end); 1291c8eef01eSChristoph Hellwig unmap_vmap_area(va); 129282a2e924SChintan Pandya if (debug_pagealloc_enabled()) 129382a2e924SChintan Pandya flush_tlb_kernel_range(va->va_start, va->va_end); 129482a2e924SChintan Pandya 1295c8eef01eSChristoph Hellwig free_vmap_area_noflush(va); 1296b29acbdcSNick Piggin } 1297b29acbdcSNick Piggin 1298db64fe02SNick Piggin static struct vmap_area *find_vmap_area(unsigned long addr) 1299db64fe02SNick Piggin { 1300db64fe02SNick Piggin struct vmap_area *va; 1301db64fe02SNick Piggin 1302db64fe02SNick Piggin spin_lock(&vmap_area_lock); 1303db64fe02SNick Piggin va = __find_vmap_area(addr); 1304db64fe02SNick Piggin spin_unlock(&vmap_area_lock); 1305db64fe02SNick Piggin 1306db64fe02SNick Piggin return va; 1307db64fe02SNick Piggin } 1308db64fe02SNick Piggin 1309db64fe02SNick Piggin /*** Per cpu kva allocator ***/ 1310db64fe02SNick Piggin 1311db64fe02SNick Piggin /* 1312db64fe02SNick Piggin * vmap space is limited especially on 32 bit architectures. Ensure there is 1313db64fe02SNick Piggin * room for at least 16 percpu vmap blocks per CPU. 1314db64fe02SNick Piggin */ 1315db64fe02SNick Piggin /* 1316db64fe02SNick Piggin * If we had a constant VMALLOC_START and VMALLOC_END, we'd like to be able 1317db64fe02SNick Piggin * to #define VMALLOC_SPACE (VMALLOC_END-VMALLOC_START). Guess 1318db64fe02SNick Piggin * instead (we just need a rough idea) 1319db64fe02SNick Piggin */ 1320db64fe02SNick Piggin #if BITS_PER_LONG == 32 1321db64fe02SNick Piggin #define VMALLOC_SPACE (128UL*1024*1024) 1322db64fe02SNick Piggin #else 1323db64fe02SNick Piggin #define VMALLOC_SPACE (128UL*1024*1024*1024) 1324db64fe02SNick Piggin #endif 1325db64fe02SNick Piggin 1326db64fe02SNick Piggin #define VMALLOC_PAGES (VMALLOC_SPACE / PAGE_SIZE) 1327db64fe02SNick Piggin #define VMAP_MAX_ALLOC BITS_PER_LONG /* 256K with 4K pages */ 1328db64fe02SNick Piggin #define VMAP_BBMAP_BITS_MAX 1024 /* 4MB with 4K pages */ 1329db64fe02SNick Piggin #define VMAP_BBMAP_BITS_MIN (VMAP_MAX_ALLOC*2) 1330db64fe02SNick Piggin #define VMAP_MIN(x, y) ((x) < (y) ? (x) : (y)) /* can't use min() */ 1331db64fe02SNick Piggin #define VMAP_MAX(x, y) ((x) > (y) ? (x) : (y)) /* can't use max() */ 1332f982f915SClemens Ladisch #define VMAP_BBMAP_BITS \ 1333f982f915SClemens Ladisch VMAP_MIN(VMAP_BBMAP_BITS_MAX, \ 1334db64fe02SNick Piggin VMAP_MAX(VMAP_BBMAP_BITS_MIN, \ 1335f982f915SClemens Ladisch VMALLOC_PAGES / roundup_pow_of_two(NR_CPUS) / 16)) 1336db64fe02SNick Piggin 1337db64fe02SNick Piggin #define VMAP_BLOCK_SIZE (VMAP_BBMAP_BITS * PAGE_SIZE) 1338db64fe02SNick Piggin 1339db64fe02SNick Piggin struct vmap_block_queue { 1340db64fe02SNick Piggin spinlock_t lock; 1341db64fe02SNick Piggin struct list_head free; 1342db64fe02SNick Piggin }; 1343db64fe02SNick Piggin 1344db64fe02SNick Piggin struct vmap_block { 1345db64fe02SNick Piggin spinlock_t lock; 1346db64fe02SNick Piggin struct vmap_area *va; 1347db64fe02SNick Piggin unsigned long free, dirty; 13487d61bfe8SRoman Pen unsigned long dirty_min, dirty_max; /*< dirty range */ 1349db64fe02SNick Piggin struct list_head free_list; 1350db64fe02SNick Piggin struct rcu_head rcu_head; 135102b709dfSNick Piggin struct list_head purge; 1352db64fe02SNick Piggin }; 1353db64fe02SNick Piggin 1354db64fe02SNick Piggin /* Queue of free and dirty vmap blocks, for allocation and flushing purposes */ 1355db64fe02SNick Piggin static DEFINE_PER_CPU(struct vmap_block_queue, vmap_block_queue); 1356db64fe02SNick Piggin 1357db64fe02SNick Piggin /* 1358db64fe02SNick Piggin * Radix tree of vmap blocks, indexed by address, to quickly find a vmap block 1359db64fe02SNick Piggin * in the free path. Could get rid of this if we change the API to return a 1360db64fe02SNick Piggin * "cookie" from alloc, to be passed to free. But no big deal yet. 1361db64fe02SNick Piggin */ 1362db64fe02SNick Piggin static DEFINE_SPINLOCK(vmap_block_tree_lock); 1363db64fe02SNick Piggin static RADIX_TREE(vmap_block_tree, GFP_ATOMIC); 1364db64fe02SNick Piggin 1365db64fe02SNick Piggin /* 1366db64fe02SNick Piggin * We should probably have a fallback mechanism to allocate virtual memory 1367db64fe02SNick Piggin * out of partially filled vmap blocks. However vmap block sizing should be 1368db64fe02SNick Piggin * fairly reasonable according to the vmalloc size, so it shouldn't be a 1369db64fe02SNick Piggin * big problem. 1370db64fe02SNick Piggin */ 1371db64fe02SNick Piggin 1372db64fe02SNick Piggin static unsigned long addr_to_vb_idx(unsigned long addr) 1373db64fe02SNick Piggin { 1374db64fe02SNick Piggin addr -= VMALLOC_START & ~(VMAP_BLOCK_SIZE-1); 1375db64fe02SNick Piggin addr /= VMAP_BLOCK_SIZE; 1376db64fe02SNick Piggin return addr; 1377db64fe02SNick Piggin } 1378db64fe02SNick Piggin 1379cf725ce2SRoman Pen static void *vmap_block_vaddr(unsigned long va_start, unsigned long pages_off) 1380cf725ce2SRoman Pen { 1381cf725ce2SRoman Pen unsigned long addr; 1382cf725ce2SRoman Pen 1383cf725ce2SRoman Pen addr = va_start + (pages_off << PAGE_SHIFT); 1384cf725ce2SRoman Pen BUG_ON(addr_to_vb_idx(addr) != addr_to_vb_idx(va_start)); 1385cf725ce2SRoman Pen return (void *)addr; 1386cf725ce2SRoman Pen } 1387cf725ce2SRoman Pen 1388cf725ce2SRoman Pen /** 1389cf725ce2SRoman Pen * new_vmap_block - allocates new vmap_block and occupies 2^order pages in this 1390cf725ce2SRoman Pen * block. Of course pages number can't exceed VMAP_BBMAP_BITS 1391cf725ce2SRoman Pen * @order: how many 2^order pages should be occupied in newly allocated block 1392cf725ce2SRoman Pen * @gfp_mask: flags for the page level allocator 1393cf725ce2SRoman Pen * 1394a862f68aSMike Rapoport * Return: virtual address in a newly allocated block or ERR_PTR(-errno) 1395cf725ce2SRoman Pen */ 1396cf725ce2SRoman Pen static void *new_vmap_block(unsigned int order, gfp_t gfp_mask) 1397db64fe02SNick Piggin { 1398db64fe02SNick Piggin struct vmap_block_queue *vbq; 1399db64fe02SNick Piggin struct vmap_block *vb; 1400db64fe02SNick Piggin struct vmap_area *va; 1401db64fe02SNick Piggin unsigned long vb_idx; 1402db64fe02SNick Piggin int node, err; 1403cf725ce2SRoman Pen void *vaddr; 1404db64fe02SNick Piggin 1405db64fe02SNick Piggin node = numa_node_id(); 1406db64fe02SNick Piggin 1407db64fe02SNick Piggin vb = kmalloc_node(sizeof(struct vmap_block), 1408db64fe02SNick Piggin gfp_mask & GFP_RECLAIM_MASK, node); 1409db64fe02SNick Piggin if (unlikely(!vb)) 1410db64fe02SNick Piggin return ERR_PTR(-ENOMEM); 1411db64fe02SNick Piggin 1412db64fe02SNick Piggin va = alloc_vmap_area(VMAP_BLOCK_SIZE, VMAP_BLOCK_SIZE, 1413db64fe02SNick Piggin VMALLOC_START, VMALLOC_END, 1414db64fe02SNick Piggin node, gfp_mask); 1415ddf9c6d4STobias Klauser if (IS_ERR(va)) { 1416db64fe02SNick Piggin kfree(vb); 1417e7d86340SJulia Lawall return ERR_CAST(va); 1418db64fe02SNick Piggin } 1419db64fe02SNick Piggin 1420db64fe02SNick Piggin err = radix_tree_preload(gfp_mask); 1421db64fe02SNick Piggin if (unlikely(err)) { 1422db64fe02SNick Piggin kfree(vb); 1423db64fe02SNick Piggin free_vmap_area(va); 1424db64fe02SNick Piggin return ERR_PTR(err); 1425db64fe02SNick Piggin } 1426db64fe02SNick Piggin 1427cf725ce2SRoman Pen vaddr = vmap_block_vaddr(va->va_start, 0); 1428db64fe02SNick Piggin spin_lock_init(&vb->lock); 1429db64fe02SNick Piggin vb->va = va; 1430cf725ce2SRoman Pen /* At least something should be left free */ 1431cf725ce2SRoman Pen BUG_ON(VMAP_BBMAP_BITS <= (1UL << order)); 1432cf725ce2SRoman Pen vb->free = VMAP_BBMAP_BITS - (1UL << order); 1433db64fe02SNick Piggin vb->dirty = 0; 14347d61bfe8SRoman Pen vb->dirty_min = VMAP_BBMAP_BITS; 14357d61bfe8SRoman Pen vb->dirty_max = 0; 1436db64fe02SNick Piggin INIT_LIST_HEAD(&vb->free_list); 1437db64fe02SNick Piggin 1438db64fe02SNick Piggin vb_idx = addr_to_vb_idx(va->va_start); 1439db64fe02SNick Piggin spin_lock(&vmap_block_tree_lock); 1440db64fe02SNick Piggin err = radix_tree_insert(&vmap_block_tree, vb_idx, vb); 1441db64fe02SNick Piggin spin_unlock(&vmap_block_tree_lock); 1442db64fe02SNick Piggin BUG_ON(err); 1443db64fe02SNick Piggin radix_tree_preload_end(); 1444db64fe02SNick Piggin 1445db64fe02SNick Piggin vbq = &get_cpu_var(vmap_block_queue); 1446db64fe02SNick Piggin spin_lock(&vbq->lock); 144768ac546fSRoman Pen list_add_tail_rcu(&vb->free_list, &vbq->free); 1448db64fe02SNick Piggin spin_unlock(&vbq->lock); 14493f04ba85STejun Heo put_cpu_var(vmap_block_queue); 1450db64fe02SNick Piggin 1451cf725ce2SRoman Pen return vaddr; 1452db64fe02SNick Piggin } 1453db64fe02SNick Piggin 1454db64fe02SNick Piggin static void free_vmap_block(struct vmap_block *vb) 1455db64fe02SNick Piggin { 1456db64fe02SNick Piggin struct vmap_block *tmp; 1457db64fe02SNick Piggin unsigned long vb_idx; 1458db64fe02SNick Piggin 1459db64fe02SNick Piggin vb_idx = addr_to_vb_idx(vb->va->va_start); 1460db64fe02SNick Piggin spin_lock(&vmap_block_tree_lock); 1461db64fe02SNick Piggin tmp = radix_tree_delete(&vmap_block_tree, vb_idx); 1462db64fe02SNick Piggin spin_unlock(&vmap_block_tree_lock); 1463db64fe02SNick Piggin BUG_ON(tmp != vb); 1464db64fe02SNick Piggin 146564141da5SJeremy Fitzhardinge free_vmap_area_noflush(vb->va); 146622a3c7d1SLai Jiangshan kfree_rcu(vb, rcu_head); 1467db64fe02SNick Piggin } 1468db64fe02SNick Piggin 146902b709dfSNick Piggin static void purge_fragmented_blocks(int cpu) 147002b709dfSNick Piggin { 147102b709dfSNick Piggin LIST_HEAD(purge); 147202b709dfSNick Piggin struct vmap_block *vb; 147302b709dfSNick Piggin struct vmap_block *n_vb; 147402b709dfSNick Piggin struct vmap_block_queue *vbq = &per_cpu(vmap_block_queue, cpu); 147502b709dfSNick Piggin 147602b709dfSNick Piggin rcu_read_lock(); 147702b709dfSNick Piggin list_for_each_entry_rcu(vb, &vbq->free, free_list) { 147802b709dfSNick Piggin 147902b709dfSNick Piggin if (!(vb->free + vb->dirty == VMAP_BBMAP_BITS && vb->dirty != VMAP_BBMAP_BITS)) 148002b709dfSNick Piggin continue; 148102b709dfSNick Piggin 148202b709dfSNick Piggin spin_lock(&vb->lock); 148302b709dfSNick Piggin if (vb->free + vb->dirty == VMAP_BBMAP_BITS && vb->dirty != VMAP_BBMAP_BITS) { 148402b709dfSNick Piggin vb->free = 0; /* prevent further allocs after releasing lock */ 148502b709dfSNick Piggin vb->dirty = VMAP_BBMAP_BITS; /* prevent purging it again */ 14867d61bfe8SRoman Pen vb->dirty_min = 0; 14877d61bfe8SRoman Pen vb->dirty_max = VMAP_BBMAP_BITS; 148802b709dfSNick Piggin spin_lock(&vbq->lock); 148902b709dfSNick Piggin list_del_rcu(&vb->free_list); 149002b709dfSNick Piggin spin_unlock(&vbq->lock); 149102b709dfSNick Piggin spin_unlock(&vb->lock); 149202b709dfSNick Piggin list_add_tail(&vb->purge, &purge); 149302b709dfSNick Piggin } else 149402b709dfSNick Piggin spin_unlock(&vb->lock); 149502b709dfSNick Piggin } 149602b709dfSNick Piggin rcu_read_unlock(); 149702b709dfSNick Piggin 149802b709dfSNick Piggin list_for_each_entry_safe(vb, n_vb, &purge, purge) { 149902b709dfSNick Piggin list_del(&vb->purge); 150002b709dfSNick Piggin free_vmap_block(vb); 150102b709dfSNick Piggin } 150202b709dfSNick Piggin } 150302b709dfSNick Piggin 150402b709dfSNick Piggin static void purge_fragmented_blocks_allcpus(void) 150502b709dfSNick Piggin { 150602b709dfSNick Piggin int cpu; 150702b709dfSNick Piggin 150802b709dfSNick Piggin for_each_possible_cpu(cpu) 150902b709dfSNick Piggin purge_fragmented_blocks(cpu); 151002b709dfSNick Piggin } 151102b709dfSNick Piggin 1512db64fe02SNick Piggin static void *vb_alloc(unsigned long size, gfp_t gfp_mask) 1513db64fe02SNick Piggin { 1514db64fe02SNick Piggin struct vmap_block_queue *vbq; 1515db64fe02SNick Piggin struct vmap_block *vb; 1516cf725ce2SRoman Pen void *vaddr = NULL; 1517db64fe02SNick Piggin unsigned int order; 1518db64fe02SNick Piggin 1519891c49abSAlexander Kuleshov BUG_ON(offset_in_page(size)); 1520db64fe02SNick Piggin BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC); 1521aa91c4d8SJan Kara if (WARN_ON(size == 0)) { 1522aa91c4d8SJan Kara /* 1523aa91c4d8SJan Kara * Allocating 0 bytes isn't what caller wants since 1524aa91c4d8SJan Kara * get_order(0) returns funny result. Just warn and terminate 1525aa91c4d8SJan Kara * early. 1526aa91c4d8SJan Kara */ 1527aa91c4d8SJan Kara return NULL; 1528aa91c4d8SJan Kara } 1529db64fe02SNick Piggin order = get_order(size); 1530db64fe02SNick Piggin 1531db64fe02SNick Piggin rcu_read_lock(); 1532db64fe02SNick Piggin vbq = &get_cpu_var(vmap_block_queue); 1533db64fe02SNick Piggin list_for_each_entry_rcu(vb, &vbq->free, free_list) { 1534cf725ce2SRoman Pen unsigned long pages_off; 1535db64fe02SNick Piggin 1536db64fe02SNick Piggin spin_lock(&vb->lock); 1537cf725ce2SRoman Pen if (vb->free < (1UL << order)) { 1538cf725ce2SRoman Pen spin_unlock(&vb->lock); 1539cf725ce2SRoman Pen continue; 1540cf725ce2SRoman Pen } 154102b709dfSNick Piggin 1542cf725ce2SRoman Pen pages_off = VMAP_BBMAP_BITS - vb->free; 1543cf725ce2SRoman Pen vaddr = vmap_block_vaddr(vb->va->va_start, pages_off); 1544db64fe02SNick Piggin vb->free -= 1UL << order; 1545db64fe02SNick Piggin if (vb->free == 0) { 1546db64fe02SNick Piggin spin_lock(&vbq->lock); 1547de560423SNick Piggin list_del_rcu(&vb->free_list); 1548db64fe02SNick Piggin spin_unlock(&vbq->lock); 1549db64fe02SNick Piggin } 1550cf725ce2SRoman Pen 1551db64fe02SNick Piggin spin_unlock(&vb->lock); 1552db64fe02SNick Piggin break; 1553db64fe02SNick Piggin } 155402b709dfSNick Piggin 15553f04ba85STejun Heo put_cpu_var(vmap_block_queue); 1556db64fe02SNick Piggin rcu_read_unlock(); 1557db64fe02SNick Piggin 1558cf725ce2SRoman Pen /* Allocate new block if nothing was found */ 1559cf725ce2SRoman Pen if (!vaddr) 1560cf725ce2SRoman Pen vaddr = new_vmap_block(order, gfp_mask); 1561db64fe02SNick Piggin 1562cf725ce2SRoman Pen return vaddr; 1563db64fe02SNick Piggin } 1564db64fe02SNick Piggin 1565db64fe02SNick Piggin static void vb_free(const void *addr, unsigned long size) 1566db64fe02SNick Piggin { 1567db64fe02SNick Piggin unsigned long offset; 1568db64fe02SNick Piggin unsigned long vb_idx; 1569db64fe02SNick Piggin unsigned int order; 1570db64fe02SNick Piggin struct vmap_block *vb; 1571db64fe02SNick Piggin 1572891c49abSAlexander Kuleshov BUG_ON(offset_in_page(size)); 1573db64fe02SNick Piggin BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC); 1574b29acbdcSNick Piggin 1575b29acbdcSNick Piggin flush_cache_vunmap((unsigned long)addr, (unsigned long)addr + size); 1576b29acbdcSNick Piggin 1577db64fe02SNick Piggin order = get_order(size); 1578db64fe02SNick Piggin 1579db64fe02SNick Piggin offset = (unsigned long)addr & (VMAP_BLOCK_SIZE - 1); 15807d61bfe8SRoman Pen offset >>= PAGE_SHIFT; 1581db64fe02SNick Piggin 1582db64fe02SNick Piggin vb_idx = addr_to_vb_idx((unsigned long)addr); 1583db64fe02SNick Piggin rcu_read_lock(); 1584db64fe02SNick Piggin vb = radix_tree_lookup(&vmap_block_tree, vb_idx); 1585db64fe02SNick Piggin rcu_read_unlock(); 1586db64fe02SNick Piggin BUG_ON(!vb); 1587db64fe02SNick Piggin 158864141da5SJeremy Fitzhardinge vunmap_page_range((unsigned long)addr, (unsigned long)addr + size); 158964141da5SJeremy Fitzhardinge 159082a2e924SChintan Pandya if (debug_pagealloc_enabled()) 159182a2e924SChintan Pandya flush_tlb_kernel_range((unsigned long)addr, 159282a2e924SChintan Pandya (unsigned long)addr + size); 159382a2e924SChintan Pandya 1594db64fe02SNick Piggin spin_lock(&vb->lock); 15957d61bfe8SRoman Pen 15967d61bfe8SRoman Pen /* Expand dirty range */ 15977d61bfe8SRoman Pen vb->dirty_min = min(vb->dirty_min, offset); 15987d61bfe8SRoman Pen vb->dirty_max = max(vb->dirty_max, offset + (1UL << order)); 1599d086817dSMinChan Kim 1600db64fe02SNick Piggin vb->dirty += 1UL << order; 1601db64fe02SNick Piggin if (vb->dirty == VMAP_BBMAP_BITS) { 1602de560423SNick Piggin BUG_ON(vb->free); 1603db64fe02SNick Piggin spin_unlock(&vb->lock); 1604db64fe02SNick Piggin free_vmap_block(vb); 1605db64fe02SNick Piggin } else 1606db64fe02SNick Piggin spin_unlock(&vb->lock); 1607db64fe02SNick Piggin } 1608db64fe02SNick Piggin 1609868b104dSRick Edgecombe static void _vm_unmap_aliases(unsigned long start, unsigned long end, int flush) 1610db64fe02SNick Piggin { 1611db64fe02SNick Piggin int cpu; 1612db64fe02SNick Piggin 16139b463334SJeremy Fitzhardinge if (unlikely(!vmap_initialized)) 16149b463334SJeremy Fitzhardinge return; 16159b463334SJeremy Fitzhardinge 16165803ed29SChristoph Hellwig might_sleep(); 16175803ed29SChristoph Hellwig 1618db64fe02SNick Piggin for_each_possible_cpu(cpu) { 1619db64fe02SNick Piggin struct vmap_block_queue *vbq = &per_cpu(vmap_block_queue, cpu); 1620db64fe02SNick Piggin struct vmap_block *vb; 1621db64fe02SNick Piggin 1622db64fe02SNick Piggin rcu_read_lock(); 1623db64fe02SNick Piggin list_for_each_entry_rcu(vb, &vbq->free, free_list) { 1624db64fe02SNick Piggin spin_lock(&vb->lock); 16257d61bfe8SRoman Pen if (vb->dirty) { 16267d61bfe8SRoman Pen unsigned long va_start = vb->va->va_start; 1627db64fe02SNick Piggin unsigned long s, e; 1628b136be5eSJoonsoo Kim 16297d61bfe8SRoman Pen s = va_start + (vb->dirty_min << PAGE_SHIFT); 16307d61bfe8SRoman Pen e = va_start + (vb->dirty_max << PAGE_SHIFT); 1631db64fe02SNick Piggin 16327d61bfe8SRoman Pen start = min(s, start); 16337d61bfe8SRoman Pen end = max(e, end); 16347d61bfe8SRoman Pen 1635db64fe02SNick Piggin flush = 1; 1636db64fe02SNick Piggin } 1637db64fe02SNick Piggin spin_unlock(&vb->lock); 1638db64fe02SNick Piggin } 1639db64fe02SNick Piggin rcu_read_unlock(); 1640db64fe02SNick Piggin } 1641db64fe02SNick Piggin 1642f9e09977SChristoph Hellwig mutex_lock(&vmap_purge_lock); 16430574ecd1SChristoph Hellwig purge_fragmented_blocks_allcpus(); 16440574ecd1SChristoph Hellwig if (!__purge_vmap_area_lazy(start, end) && flush) 16450574ecd1SChristoph Hellwig flush_tlb_kernel_range(start, end); 1646f9e09977SChristoph Hellwig mutex_unlock(&vmap_purge_lock); 1647db64fe02SNick Piggin } 1648868b104dSRick Edgecombe 1649868b104dSRick Edgecombe /** 1650868b104dSRick Edgecombe * vm_unmap_aliases - unmap outstanding lazy aliases in the vmap layer 1651868b104dSRick Edgecombe * 1652868b104dSRick Edgecombe * The vmap/vmalloc layer lazily flushes kernel virtual mappings primarily 1653868b104dSRick Edgecombe * to amortize TLB flushing overheads. What this means is that any page you 1654868b104dSRick Edgecombe * have now, may, in a former life, have been mapped into kernel virtual 1655868b104dSRick Edgecombe * address by the vmap layer and so there might be some CPUs with TLB entries 1656868b104dSRick Edgecombe * still referencing that page (additional to the regular 1:1 kernel mapping). 1657868b104dSRick Edgecombe * 1658868b104dSRick Edgecombe * vm_unmap_aliases flushes all such lazy mappings. After it returns, we can 1659868b104dSRick Edgecombe * be sure that none of the pages we have control over will have any aliases 1660868b104dSRick Edgecombe * from the vmap layer. 1661868b104dSRick Edgecombe */ 1662868b104dSRick Edgecombe void vm_unmap_aliases(void) 1663868b104dSRick Edgecombe { 1664868b104dSRick Edgecombe unsigned long start = ULONG_MAX, end = 0; 1665868b104dSRick Edgecombe int flush = 0; 1666868b104dSRick Edgecombe 1667868b104dSRick Edgecombe _vm_unmap_aliases(start, end, flush); 1668868b104dSRick Edgecombe } 1669db64fe02SNick Piggin EXPORT_SYMBOL_GPL(vm_unmap_aliases); 1670db64fe02SNick Piggin 1671db64fe02SNick Piggin /** 1672db64fe02SNick Piggin * vm_unmap_ram - unmap linear kernel address space set up by vm_map_ram 1673db64fe02SNick Piggin * @mem: the pointer returned by vm_map_ram 1674db64fe02SNick Piggin * @count: the count passed to that vm_map_ram call (cannot unmap partial) 1675db64fe02SNick Piggin */ 1676db64fe02SNick Piggin void vm_unmap_ram(const void *mem, unsigned int count) 1677db64fe02SNick Piggin { 167865ee03c4SGuillermo Julián Moreno unsigned long size = (unsigned long)count << PAGE_SHIFT; 1679db64fe02SNick Piggin unsigned long addr = (unsigned long)mem; 16809c3acf60SChristoph Hellwig struct vmap_area *va; 1681db64fe02SNick Piggin 16825803ed29SChristoph Hellwig might_sleep(); 1683db64fe02SNick Piggin BUG_ON(!addr); 1684db64fe02SNick Piggin BUG_ON(addr < VMALLOC_START); 1685db64fe02SNick Piggin BUG_ON(addr > VMALLOC_END); 1686a1c0b1a0SShawn Lin BUG_ON(!PAGE_ALIGNED(addr)); 1687db64fe02SNick Piggin 16889c3acf60SChristoph Hellwig if (likely(count <= VMAP_MAX_ALLOC)) { 168905e3ff95SChintan Pandya debug_check_no_locks_freed(mem, size); 1690db64fe02SNick Piggin vb_free(mem, size); 16919c3acf60SChristoph Hellwig return; 16929c3acf60SChristoph Hellwig } 16939c3acf60SChristoph Hellwig 16949c3acf60SChristoph Hellwig va = find_vmap_area(addr); 16959c3acf60SChristoph Hellwig BUG_ON(!va); 169605e3ff95SChintan Pandya debug_check_no_locks_freed((void *)va->va_start, 169705e3ff95SChintan Pandya (va->va_end - va->va_start)); 16989c3acf60SChristoph Hellwig free_unmap_vmap_area(va); 1699db64fe02SNick Piggin } 1700db64fe02SNick Piggin EXPORT_SYMBOL(vm_unmap_ram); 1701db64fe02SNick Piggin 1702db64fe02SNick Piggin /** 1703db64fe02SNick Piggin * vm_map_ram - map pages linearly into kernel virtual address (vmalloc space) 1704db64fe02SNick Piggin * @pages: an array of pointers to the pages to be mapped 1705db64fe02SNick Piggin * @count: number of pages 1706db64fe02SNick Piggin * @node: prefer to allocate data structures on this node 1707db64fe02SNick Piggin * @prot: memory protection to use. PAGE_KERNEL for regular RAM 1708e99c97adSRandy Dunlap * 170936437638SGioh Kim * If you use this function for less than VMAP_MAX_ALLOC pages, it could be 171036437638SGioh Kim * faster than vmap so it's good. But if you mix long-life and short-life 171136437638SGioh Kim * objects with vm_map_ram(), it could consume lots of address space through 171236437638SGioh Kim * fragmentation (especially on a 32bit machine). You could see failures in 171336437638SGioh Kim * the end. Please use this function for short-lived objects. 171436437638SGioh Kim * 1715e99c97adSRandy Dunlap * Returns: a pointer to the address that has been mapped, or %NULL on failure 1716db64fe02SNick Piggin */ 1717db64fe02SNick Piggin void *vm_map_ram(struct page **pages, unsigned int count, int node, pgprot_t prot) 1718db64fe02SNick Piggin { 171965ee03c4SGuillermo Julián Moreno unsigned long size = (unsigned long)count << PAGE_SHIFT; 1720db64fe02SNick Piggin unsigned long addr; 1721db64fe02SNick Piggin void *mem; 1722db64fe02SNick Piggin 1723db64fe02SNick Piggin if (likely(count <= VMAP_MAX_ALLOC)) { 1724db64fe02SNick Piggin mem = vb_alloc(size, GFP_KERNEL); 1725db64fe02SNick Piggin if (IS_ERR(mem)) 1726db64fe02SNick Piggin return NULL; 1727db64fe02SNick Piggin addr = (unsigned long)mem; 1728db64fe02SNick Piggin } else { 1729db64fe02SNick Piggin struct vmap_area *va; 1730db64fe02SNick Piggin va = alloc_vmap_area(size, PAGE_SIZE, 1731db64fe02SNick Piggin VMALLOC_START, VMALLOC_END, node, GFP_KERNEL); 1732db64fe02SNick Piggin if (IS_ERR(va)) 1733db64fe02SNick Piggin return NULL; 1734db64fe02SNick Piggin 1735db64fe02SNick Piggin addr = va->va_start; 1736db64fe02SNick Piggin mem = (void *)addr; 1737db64fe02SNick Piggin } 1738db64fe02SNick Piggin if (vmap_page_range(addr, addr + size, prot, pages) < 0) { 1739db64fe02SNick Piggin vm_unmap_ram(mem, count); 1740db64fe02SNick Piggin return NULL; 1741db64fe02SNick Piggin } 1742db64fe02SNick Piggin return mem; 1743db64fe02SNick Piggin } 1744db64fe02SNick Piggin EXPORT_SYMBOL(vm_map_ram); 1745db64fe02SNick Piggin 17464341fa45SJoonsoo Kim static struct vm_struct *vmlist __initdata; 174792eac168SMike Rapoport 1748f0aa6617STejun Heo /** 1749be9b7335SNicolas Pitre * vm_area_add_early - add vmap area early during boot 1750be9b7335SNicolas Pitre * @vm: vm_struct to add 1751be9b7335SNicolas Pitre * 1752be9b7335SNicolas Pitre * This function is used to add fixed kernel vm area to vmlist before 1753be9b7335SNicolas Pitre * vmalloc_init() is called. @vm->addr, @vm->size, and @vm->flags 1754be9b7335SNicolas Pitre * should contain proper values and the other fields should be zero. 1755be9b7335SNicolas Pitre * 1756be9b7335SNicolas Pitre * DO NOT USE THIS FUNCTION UNLESS YOU KNOW WHAT YOU'RE DOING. 1757be9b7335SNicolas Pitre */ 1758be9b7335SNicolas Pitre void __init vm_area_add_early(struct vm_struct *vm) 1759be9b7335SNicolas Pitre { 1760be9b7335SNicolas Pitre struct vm_struct *tmp, **p; 1761be9b7335SNicolas Pitre 1762be9b7335SNicolas Pitre BUG_ON(vmap_initialized); 1763be9b7335SNicolas Pitre for (p = &vmlist; (tmp = *p) != NULL; p = &tmp->next) { 1764be9b7335SNicolas Pitre if (tmp->addr >= vm->addr) { 1765be9b7335SNicolas Pitre BUG_ON(tmp->addr < vm->addr + vm->size); 1766be9b7335SNicolas Pitre break; 1767be9b7335SNicolas Pitre } else 1768be9b7335SNicolas Pitre BUG_ON(tmp->addr + tmp->size > vm->addr); 1769be9b7335SNicolas Pitre } 1770be9b7335SNicolas Pitre vm->next = *p; 1771be9b7335SNicolas Pitre *p = vm; 1772be9b7335SNicolas Pitre } 1773be9b7335SNicolas Pitre 1774be9b7335SNicolas Pitre /** 1775f0aa6617STejun Heo * vm_area_register_early - register vmap area early during boot 1776f0aa6617STejun Heo * @vm: vm_struct to register 1777c0c0a293STejun Heo * @align: requested alignment 1778f0aa6617STejun Heo * 1779f0aa6617STejun Heo * This function is used to register kernel vm area before 1780f0aa6617STejun Heo * vmalloc_init() is called. @vm->size and @vm->flags should contain 1781f0aa6617STejun Heo * proper values on entry and other fields should be zero. On return, 1782f0aa6617STejun Heo * vm->addr contains the allocated address. 1783f0aa6617STejun Heo * 1784f0aa6617STejun Heo * DO NOT USE THIS FUNCTION UNLESS YOU KNOW WHAT YOU'RE DOING. 1785f0aa6617STejun Heo */ 1786c0c0a293STejun Heo void __init vm_area_register_early(struct vm_struct *vm, size_t align) 1787f0aa6617STejun Heo { 1788f0aa6617STejun Heo static size_t vm_init_off __initdata; 1789c0c0a293STejun Heo unsigned long addr; 1790f0aa6617STejun Heo 1791c0c0a293STejun Heo addr = ALIGN(VMALLOC_START + vm_init_off, align); 1792c0c0a293STejun Heo vm_init_off = PFN_ALIGN(addr + vm->size) - VMALLOC_START; 1793c0c0a293STejun Heo 1794c0c0a293STejun Heo vm->addr = (void *)addr; 1795f0aa6617STejun Heo 1796be9b7335SNicolas Pitre vm_area_add_early(vm); 1797f0aa6617STejun Heo } 1798f0aa6617STejun Heo 179968ad4a33SUladzislau Rezki (Sony) static void vmap_init_free_space(void) 180068ad4a33SUladzislau Rezki (Sony) { 180168ad4a33SUladzislau Rezki (Sony) unsigned long vmap_start = 1; 180268ad4a33SUladzislau Rezki (Sony) const unsigned long vmap_end = ULONG_MAX; 180368ad4a33SUladzislau Rezki (Sony) struct vmap_area *busy, *free; 180468ad4a33SUladzislau Rezki (Sony) 180568ad4a33SUladzislau Rezki (Sony) /* 180668ad4a33SUladzislau Rezki (Sony) * B F B B B F 180768ad4a33SUladzislau Rezki (Sony) * -|-----|.....|-----|-----|-----|.....|- 180868ad4a33SUladzislau Rezki (Sony) * | The KVA space | 180968ad4a33SUladzislau Rezki (Sony) * |<--------------------------------->| 181068ad4a33SUladzislau Rezki (Sony) */ 181168ad4a33SUladzislau Rezki (Sony) list_for_each_entry(busy, &vmap_area_list, list) { 181268ad4a33SUladzislau Rezki (Sony) if (busy->va_start - vmap_start > 0) { 181368ad4a33SUladzislau Rezki (Sony) free = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT); 181468ad4a33SUladzislau Rezki (Sony) if (!WARN_ON_ONCE(!free)) { 181568ad4a33SUladzislau Rezki (Sony) free->va_start = vmap_start; 181668ad4a33SUladzislau Rezki (Sony) free->va_end = busy->va_start; 181768ad4a33SUladzislau Rezki (Sony) 181868ad4a33SUladzislau Rezki (Sony) insert_vmap_area_augment(free, NULL, 181968ad4a33SUladzislau Rezki (Sony) &free_vmap_area_root, 182068ad4a33SUladzislau Rezki (Sony) &free_vmap_area_list); 182168ad4a33SUladzislau Rezki (Sony) } 182268ad4a33SUladzislau Rezki (Sony) } 182368ad4a33SUladzislau Rezki (Sony) 182468ad4a33SUladzislau Rezki (Sony) vmap_start = busy->va_end; 182568ad4a33SUladzislau Rezki (Sony) } 182668ad4a33SUladzislau Rezki (Sony) 182768ad4a33SUladzislau Rezki (Sony) if (vmap_end - vmap_start > 0) { 182868ad4a33SUladzislau Rezki (Sony) free = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT); 182968ad4a33SUladzislau Rezki (Sony) if (!WARN_ON_ONCE(!free)) { 183068ad4a33SUladzislau Rezki (Sony) free->va_start = vmap_start; 183168ad4a33SUladzislau Rezki (Sony) free->va_end = vmap_end; 183268ad4a33SUladzislau Rezki (Sony) 183368ad4a33SUladzislau Rezki (Sony) insert_vmap_area_augment(free, NULL, 183468ad4a33SUladzislau Rezki (Sony) &free_vmap_area_root, 183568ad4a33SUladzislau Rezki (Sony) &free_vmap_area_list); 183668ad4a33SUladzislau Rezki (Sony) } 183768ad4a33SUladzislau Rezki (Sony) } 183868ad4a33SUladzislau Rezki (Sony) } 183968ad4a33SUladzislau Rezki (Sony) 1840db64fe02SNick Piggin void __init vmalloc_init(void) 1841db64fe02SNick Piggin { 1842822c18f2SIvan Kokshaysky struct vmap_area *va; 1843822c18f2SIvan Kokshaysky struct vm_struct *tmp; 1844db64fe02SNick Piggin int i; 1845db64fe02SNick Piggin 184668ad4a33SUladzislau Rezki (Sony) /* 184768ad4a33SUladzislau Rezki (Sony) * Create the cache for vmap_area objects. 184868ad4a33SUladzislau Rezki (Sony) */ 184968ad4a33SUladzislau Rezki (Sony) vmap_area_cachep = KMEM_CACHE(vmap_area, SLAB_PANIC); 185068ad4a33SUladzislau Rezki (Sony) 1851db64fe02SNick Piggin for_each_possible_cpu(i) { 1852db64fe02SNick Piggin struct vmap_block_queue *vbq; 185332fcfd40SAl Viro struct vfree_deferred *p; 1854db64fe02SNick Piggin 1855db64fe02SNick Piggin vbq = &per_cpu(vmap_block_queue, i); 1856db64fe02SNick Piggin spin_lock_init(&vbq->lock); 1857db64fe02SNick Piggin INIT_LIST_HEAD(&vbq->free); 185832fcfd40SAl Viro p = &per_cpu(vfree_deferred, i); 185932fcfd40SAl Viro init_llist_head(&p->list); 186032fcfd40SAl Viro INIT_WORK(&p->wq, free_work); 1861db64fe02SNick Piggin } 18629b463334SJeremy Fitzhardinge 1863822c18f2SIvan Kokshaysky /* Import existing vmlist entries. */ 1864822c18f2SIvan Kokshaysky for (tmp = vmlist; tmp; tmp = tmp->next) { 186568ad4a33SUladzislau Rezki (Sony) va = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT); 186668ad4a33SUladzislau Rezki (Sony) if (WARN_ON_ONCE(!va)) 186768ad4a33SUladzislau Rezki (Sony) continue; 186868ad4a33SUladzislau Rezki (Sony) 1869dbda591dSKyongHo va->flags = VM_VM_AREA; 1870822c18f2SIvan Kokshaysky va->va_start = (unsigned long)tmp->addr; 1871822c18f2SIvan Kokshaysky va->va_end = va->va_start + tmp->size; 1872dbda591dSKyongHo va->vm = tmp; 187368ad4a33SUladzislau Rezki (Sony) insert_vmap_area(va, &vmap_area_root, &vmap_area_list); 1874822c18f2SIvan Kokshaysky } 1875ca23e405STejun Heo 187668ad4a33SUladzislau Rezki (Sony) /* 187768ad4a33SUladzislau Rezki (Sony) * Now we can initialize a free vmap space. 187868ad4a33SUladzislau Rezki (Sony) */ 187968ad4a33SUladzislau Rezki (Sony) vmap_init_free_space(); 18809b463334SJeremy Fitzhardinge vmap_initialized = true; 1881db64fe02SNick Piggin } 1882db64fe02SNick Piggin 18838fc48985STejun Heo /** 18848fc48985STejun Heo * map_kernel_range_noflush - map kernel VM area with the specified pages 18858fc48985STejun Heo * @addr: start of the VM area to map 18868fc48985STejun Heo * @size: size of the VM area to map 18878fc48985STejun Heo * @prot: page protection flags to use 18888fc48985STejun Heo * @pages: pages to map 18898fc48985STejun Heo * 18908fc48985STejun Heo * Map PFN_UP(@size) pages at @addr. The VM area @addr and @size 18918fc48985STejun Heo * specify should have been allocated using get_vm_area() and its 18928fc48985STejun Heo * friends. 18938fc48985STejun Heo * 18948fc48985STejun Heo * NOTE: 18958fc48985STejun Heo * This function does NOT do any cache flushing. The caller is 18968fc48985STejun Heo * responsible for calling flush_cache_vmap() on to-be-mapped areas 18978fc48985STejun Heo * before calling this function. 18988fc48985STejun Heo * 18998fc48985STejun Heo * RETURNS: 19008fc48985STejun Heo * The number of pages mapped on success, -errno on failure. 19018fc48985STejun Heo */ 19028fc48985STejun Heo int map_kernel_range_noflush(unsigned long addr, unsigned long size, 19038fc48985STejun Heo pgprot_t prot, struct page **pages) 19048fc48985STejun Heo { 19058fc48985STejun Heo return vmap_page_range_noflush(addr, addr + size, prot, pages); 19068fc48985STejun Heo } 19078fc48985STejun Heo 19088fc48985STejun Heo /** 19098fc48985STejun Heo * unmap_kernel_range_noflush - unmap kernel VM area 19108fc48985STejun Heo * @addr: start of the VM area to unmap 19118fc48985STejun Heo * @size: size of the VM area to unmap 19128fc48985STejun Heo * 19138fc48985STejun Heo * Unmap PFN_UP(@size) pages at @addr. The VM area @addr and @size 19148fc48985STejun Heo * specify should have been allocated using get_vm_area() and its 19158fc48985STejun Heo * friends. 19168fc48985STejun Heo * 19178fc48985STejun Heo * NOTE: 19188fc48985STejun Heo * This function does NOT do any cache flushing. The caller is 19198fc48985STejun Heo * responsible for calling flush_cache_vunmap() on to-be-mapped areas 19208fc48985STejun Heo * before calling this function and flush_tlb_kernel_range() after. 19218fc48985STejun Heo */ 19228fc48985STejun Heo void unmap_kernel_range_noflush(unsigned long addr, unsigned long size) 19238fc48985STejun Heo { 19248fc48985STejun Heo vunmap_page_range(addr, addr + size); 19258fc48985STejun Heo } 192681e88fdcSHuang Ying EXPORT_SYMBOL_GPL(unmap_kernel_range_noflush); 19278fc48985STejun Heo 19288fc48985STejun Heo /** 19298fc48985STejun Heo * unmap_kernel_range - unmap kernel VM area and flush cache and TLB 19308fc48985STejun Heo * @addr: start of the VM area to unmap 19318fc48985STejun Heo * @size: size of the VM area to unmap 19328fc48985STejun Heo * 19338fc48985STejun Heo * Similar to unmap_kernel_range_noflush() but flushes vcache before 19348fc48985STejun Heo * the unmapping and tlb after. 19358fc48985STejun Heo */ 1936db64fe02SNick Piggin void unmap_kernel_range(unsigned long addr, unsigned long size) 1937db64fe02SNick Piggin { 1938db64fe02SNick Piggin unsigned long end = addr + size; 1939f6fcba70STejun Heo 1940f6fcba70STejun Heo flush_cache_vunmap(addr, end); 1941db64fe02SNick Piggin vunmap_page_range(addr, end); 1942db64fe02SNick Piggin flush_tlb_kernel_range(addr, end); 1943db64fe02SNick Piggin } 194493ef6d6cSMinchan Kim EXPORT_SYMBOL_GPL(unmap_kernel_range); 1945db64fe02SNick Piggin 1946f6f8ed47SWANG Chao int map_vm_area(struct vm_struct *area, pgprot_t prot, struct page **pages) 1947db64fe02SNick Piggin { 1948db64fe02SNick Piggin unsigned long addr = (unsigned long)area->addr; 1949762216abSWanpeng Li unsigned long end = addr + get_vm_area_size(area); 1950db64fe02SNick Piggin int err; 1951db64fe02SNick Piggin 1952f6f8ed47SWANG Chao err = vmap_page_range(addr, end, prot, pages); 1953db64fe02SNick Piggin 1954f6f8ed47SWANG Chao return err > 0 ? 0 : err; 1955db64fe02SNick Piggin } 1956db64fe02SNick Piggin EXPORT_SYMBOL_GPL(map_vm_area); 1957db64fe02SNick Piggin 1958f5252e00SMitsuo Hayasaka static void setup_vmalloc_vm(struct vm_struct *vm, struct vmap_area *va, 19595e6cafc8SMarek Szyprowski unsigned long flags, const void *caller) 1960cf88c790STejun Heo { 1961c69480adSJoonsoo Kim spin_lock(&vmap_area_lock); 1962cf88c790STejun Heo vm->flags = flags; 1963cf88c790STejun Heo vm->addr = (void *)va->va_start; 1964cf88c790STejun Heo vm->size = va->va_end - va->va_start; 1965cf88c790STejun Heo vm->caller = caller; 1966db1aecafSMinchan Kim va->vm = vm; 1967cf88c790STejun Heo va->flags |= VM_VM_AREA; 1968c69480adSJoonsoo Kim spin_unlock(&vmap_area_lock); 1969f5252e00SMitsuo Hayasaka } 1970cf88c790STejun Heo 197120fc02b4SZhang Yanfei static void clear_vm_uninitialized_flag(struct vm_struct *vm) 1972f5252e00SMitsuo Hayasaka { 1973d4033afdSJoonsoo Kim /* 197420fc02b4SZhang Yanfei * Before removing VM_UNINITIALIZED, 1975d4033afdSJoonsoo Kim * we should make sure that vm has proper values. 1976d4033afdSJoonsoo Kim * Pair with smp_rmb() in show_numa_info(). 1977d4033afdSJoonsoo Kim */ 1978d4033afdSJoonsoo Kim smp_wmb(); 197920fc02b4SZhang Yanfei vm->flags &= ~VM_UNINITIALIZED; 1980cf88c790STejun Heo } 1981cf88c790STejun Heo 1982db64fe02SNick Piggin static struct vm_struct *__get_vm_area_node(unsigned long size, 19832dca6999SDavid Miller unsigned long align, unsigned long flags, unsigned long start, 19845e6cafc8SMarek Szyprowski unsigned long end, int node, gfp_t gfp_mask, const void *caller) 1985db64fe02SNick Piggin { 19860006526dSKautuk Consul struct vmap_area *va; 1987db64fe02SNick Piggin struct vm_struct *area; 19881da177e4SLinus Torvalds 198952fd24caSGiridhar Pemmasani BUG_ON(in_interrupt()); 19901da177e4SLinus Torvalds size = PAGE_ALIGN(size); 199131be8309SOGAWA Hirofumi if (unlikely(!size)) 199231be8309SOGAWA Hirofumi return NULL; 19931da177e4SLinus Torvalds 1994252e5c6eSzijun_hu if (flags & VM_IOREMAP) 1995252e5c6eSzijun_hu align = 1ul << clamp_t(int, get_count_order_long(size), 1996252e5c6eSzijun_hu PAGE_SHIFT, IOREMAP_MAX_ORDER); 1997252e5c6eSzijun_hu 1998cf88c790STejun Heo area = kzalloc_node(sizeof(*area), gfp_mask & GFP_RECLAIM_MASK, node); 19991da177e4SLinus Torvalds if (unlikely(!area)) 20001da177e4SLinus Torvalds return NULL; 20011da177e4SLinus Torvalds 200271394fe5SAndrey Ryabinin if (!(flags & VM_NO_GUARD)) 20031da177e4SLinus Torvalds size += PAGE_SIZE; 20041da177e4SLinus Torvalds 2005db64fe02SNick Piggin va = alloc_vmap_area(size, align, start, end, node, gfp_mask); 2006db64fe02SNick Piggin if (IS_ERR(va)) { 2007db64fe02SNick Piggin kfree(area); 2008db64fe02SNick Piggin return NULL; 20091da177e4SLinus Torvalds } 20101da177e4SLinus Torvalds 2011f5252e00SMitsuo Hayasaka setup_vmalloc_vm(area, va, flags, caller); 2012f5252e00SMitsuo Hayasaka 20131da177e4SLinus Torvalds return area; 20141da177e4SLinus Torvalds } 20151da177e4SLinus Torvalds 2016930fc45aSChristoph Lameter struct vm_struct *__get_vm_area(unsigned long size, unsigned long flags, 2017930fc45aSChristoph Lameter unsigned long start, unsigned long end) 2018930fc45aSChristoph Lameter { 201900ef2d2fSDavid Rientjes return __get_vm_area_node(size, 1, flags, start, end, NUMA_NO_NODE, 202000ef2d2fSDavid Rientjes GFP_KERNEL, __builtin_return_address(0)); 2021930fc45aSChristoph Lameter } 20225992b6daSRusty Russell EXPORT_SYMBOL_GPL(__get_vm_area); 2023930fc45aSChristoph Lameter 2024c2968612SBenjamin Herrenschmidt struct vm_struct *__get_vm_area_caller(unsigned long size, unsigned long flags, 2025c2968612SBenjamin Herrenschmidt unsigned long start, unsigned long end, 20265e6cafc8SMarek Szyprowski const void *caller) 2027c2968612SBenjamin Herrenschmidt { 202800ef2d2fSDavid Rientjes return __get_vm_area_node(size, 1, flags, start, end, NUMA_NO_NODE, 202900ef2d2fSDavid Rientjes GFP_KERNEL, caller); 2030c2968612SBenjamin Herrenschmidt } 2031c2968612SBenjamin Herrenschmidt 20321da177e4SLinus Torvalds /** 2033183ff22bSSimon Arlott * get_vm_area - reserve a contiguous kernel virtual area 20341da177e4SLinus Torvalds * @size: size of the area 20351da177e4SLinus Torvalds * @flags: %VM_IOREMAP for I/O mappings or VM_ALLOC 20361da177e4SLinus Torvalds * 20371da177e4SLinus Torvalds * Search an area of @size in the kernel virtual mapping area, 20381da177e4SLinus Torvalds * and reserved it for out purposes. Returns the area descriptor 20391da177e4SLinus Torvalds * on success or %NULL on failure. 2040a862f68aSMike Rapoport * 2041a862f68aSMike Rapoport * Return: the area descriptor on success or %NULL on failure. 20421da177e4SLinus Torvalds */ 20431da177e4SLinus Torvalds struct vm_struct *get_vm_area(unsigned long size, unsigned long flags) 20441da177e4SLinus Torvalds { 20452dca6999SDavid Miller return __get_vm_area_node(size, 1, flags, VMALLOC_START, VMALLOC_END, 204600ef2d2fSDavid Rientjes NUMA_NO_NODE, GFP_KERNEL, 204700ef2d2fSDavid Rientjes __builtin_return_address(0)); 204823016969SChristoph Lameter } 204923016969SChristoph Lameter 205023016969SChristoph Lameter struct vm_struct *get_vm_area_caller(unsigned long size, unsigned long flags, 20515e6cafc8SMarek Szyprowski const void *caller) 205223016969SChristoph Lameter { 20532dca6999SDavid Miller return __get_vm_area_node(size, 1, flags, VMALLOC_START, VMALLOC_END, 205400ef2d2fSDavid Rientjes NUMA_NO_NODE, GFP_KERNEL, caller); 20551da177e4SLinus Torvalds } 20561da177e4SLinus Torvalds 2057e9da6e99SMarek Szyprowski /** 2058e9da6e99SMarek Szyprowski * find_vm_area - find a continuous kernel virtual area 2059e9da6e99SMarek Szyprowski * @addr: base address 2060e9da6e99SMarek Szyprowski * 2061e9da6e99SMarek Szyprowski * Search for the kernel VM area starting at @addr, and return it. 2062e9da6e99SMarek Szyprowski * It is up to the caller to do all required locking to keep the returned 2063e9da6e99SMarek Szyprowski * pointer valid. 2064a862f68aSMike Rapoport * 2065a862f68aSMike Rapoport * Return: pointer to the found area or %NULL on faulure 2066e9da6e99SMarek Szyprowski */ 2067e9da6e99SMarek Szyprowski struct vm_struct *find_vm_area(const void *addr) 206883342314SNick Piggin { 2069db64fe02SNick Piggin struct vmap_area *va; 207083342314SNick Piggin 2071db64fe02SNick Piggin va = find_vmap_area((unsigned long)addr); 2072db64fe02SNick Piggin if (va && va->flags & VM_VM_AREA) 2073db1aecafSMinchan Kim return va->vm; 207483342314SNick Piggin 20757856dfebSAndi Kleen return NULL; 20767856dfebSAndi Kleen } 20777856dfebSAndi Kleen 20781da177e4SLinus Torvalds /** 2079183ff22bSSimon Arlott * remove_vm_area - find and remove a continuous kernel virtual area 20801da177e4SLinus Torvalds * @addr: base address 20811da177e4SLinus Torvalds * 20821da177e4SLinus Torvalds * Search for the kernel VM area starting at @addr, and remove it. 20831da177e4SLinus Torvalds * This function returns the found VM area, but using it is NOT safe 20847856dfebSAndi Kleen * on SMP machines, except for its size or flags. 2085a862f68aSMike Rapoport * 2086a862f68aSMike Rapoport * Return: pointer to the found area or %NULL on faulure 20871da177e4SLinus Torvalds */ 2088b3bdda02SChristoph Lameter struct vm_struct *remove_vm_area(const void *addr) 20891da177e4SLinus Torvalds { 2090db64fe02SNick Piggin struct vmap_area *va; 2091db64fe02SNick Piggin 20925803ed29SChristoph Hellwig might_sleep(); 20935803ed29SChristoph Hellwig 2094db64fe02SNick Piggin va = find_vmap_area((unsigned long)addr); 2095db64fe02SNick Piggin if (va && va->flags & VM_VM_AREA) { 2096db1aecafSMinchan Kim struct vm_struct *vm = va->vm; 2097f5252e00SMitsuo Hayasaka 2098c69480adSJoonsoo Kim spin_lock(&vmap_area_lock); 2099c69480adSJoonsoo Kim va->vm = NULL; 2100c69480adSJoonsoo Kim va->flags &= ~VM_VM_AREA; 210178c72746SYisheng Xie va->flags |= VM_LAZY_FREE; 2102c69480adSJoonsoo Kim spin_unlock(&vmap_area_lock); 2103c69480adSJoonsoo Kim 2104a5af5aa8SAndrey Ryabinin kasan_free_shadow(vm); 2105dd32c279SKAMEZAWA Hiroyuki free_unmap_vmap_area(va); 2106dd32c279SKAMEZAWA Hiroyuki 2107db64fe02SNick Piggin return vm; 2108db64fe02SNick Piggin } 2109db64fe02SNick Piggin return NULL; 21101da177e4SLinus Torvalds } 21111da177e4SLinus Torvalds 2112868b104dSRick Edgecombe static inline void set_area_direct_map(const struct vm_struct *area, 2113868b104dSRick Edgecombe int (*set_direct_map)(struct page *page)) 2114868b104dSRick Edgecombe { 2115868b104dSRick Edgecombe int i; 2116868b104dSRick Edgecombe 2117868b104dSRick Edgecombe for (i = 0; i < area->nr_pages; i++) 2118868b104dSRick Edgecombe if (page_address(area->pages[i])) 2119868b104dSRick Edgecombe set_direct_map(area->pages[i]); 2120868b104dSRick Edgecombe } 2121868b104dSRick Edgecombe 2122868b104dSRick Edgecombe /* Handle removing and resetting vm mappings related to the vm_struct. */ 2123868b104dSRick Edgecombe static void vm_remove_mappings(struct vm_struct *area, int deallocate_pages) 2124868b104dSRick Edgecombe { 2125868b104dSRick Edgecombe unsigned long addr = (unsigned long)area->addr; 2126868b104dSRick Edgecombe unsigned long start = ULONG_MAX, end = 0; 2127868b104dSRick Edgecombe int flush_reset = area->flags & VM_FLUSH_RESET_PERMS; 2128868b104dSRick Edgecombe int i; 2129868b104dSRick Edgecombe 2130868b104dSRick Edgecombe /* 2131868b104dSRick Edgecombe * The below block can be removed when all architectures that have 2132868b104dSRick Edgecombe * direct map permissions also have set_direct_map_() implementations. 2133868b104dSRick Edgecombe * This is concerned with resetting the direct map any an vm alias with 2134868b104dSRick Edgecombe * execute permissions, without leaving a RW+X window. 2135868b104dSRick Edgecombe */ 2136868b104dSRick Edgecombe if (flush_reset && !IS_ENABLED(CONFIG_ARCH_HAS_SET_DIRECT_MAP)) { 2137868b104dSRick Edgecombe set_memory_nx(addr, area->nr_pages); 2138868b104dSRick Edgecombe set_memory_rw(addr, area->nr_pages); 2139868b104dSRick Edgecombe } 2140868b104dSRick Edgecombe 2141868b104dSRick Edgecombe remove_vm_area(area->addr); 2142868b104dSRick Edgecombe 2143868b104dSRick Edgecombe /* If this is not VM_FLUSH_RESET_PERMS memory, no need for the below. */ 2144868b104dSRick Edgecombe if (!flush_reset) 2145868b104dSRick Edgecombe return; 2146868b104dSRick Edgecombe 2147868b104dSRick Edgecombe /* 2148868b104dSRick Edgecombe * If not deallocating pages, just do the flush of the VM area and 2149868b104dSRick Edgecombe * return. 2150868b104dSRick Edgecombe */ 2151868b104dSRick Edgecombe if (!deallocate_pages) { 2152868b104dSRick Edgecombe vm_unmap_aliases(); 2153868b104dSRick Edgecombe return; 2154868b104dSRick Edgecombe } 2155868b104dSRick Edgecombe 2156868b104dSRick Edgecombe /* 2157868b104dSRick Edgecombe * If execution gets here, flush the vm mapping and reset the direct 2158868b104dSRick Edgecombe * map. Find the start and end range of the direct mappings to make sure 2159868b104dSRick Edgecombe * the vm_unmap_aliases() flush includes the direct map. 2160868b104dSRick Edgecombe */ 2161868b104dSRick Edgecombe for (i = 0; i < area->nr_pages; i++) { 2162868b104dSRick Edgecombe if (page_address(area->pages[i])) { 2163868b104dSRick Edgecombe start = min(addr, start); 2164868b104dSRick Edgecombe end = max(addr, end); 2165868b104dSRick Edgecombe } 2166868b104dSRick Edgecombe } 2167868b104dSRick Edgecombe 2168868b104dSRick Edgecombe /* 2169868b104dSRick Edgecombe * Set direct map to something invalid so that it won't be cached if 2170868b104dSRick Edgecombe * there are any accesses after the TLB flush, then flush the TLB and 2171868b104dSRick Edgecombe * reset the direct map permissions to the default. 2172868b104dSRick Edgecombe */ 2173868b104dSRick Edgecombe set_area_direct_map(area, set_direct_map_invalid_noflush); 2174868b104dSRick Edgecombe _vm_unmap_aliases(start, end, 1); 2175868b104dSRick Edgecombe set_area_direct_map(area, set_direct_map_default_noflush); 2176868b104dSRick Edgecombe } 2177868b104dSRick Edgecombe 2178b3bdda02SChristoph Lameter static void __vunmap(const void *addr, int deallocate_pages) 21791da177e4SLinus Torvalds { 21801da177e4SLinus Torvalds struct vm_struct *area; 21811da177e4SLinus Torvalds 21821da177e4SLinus Torvalds if (!addr) 21831da177e4SLinus Torvalds return; 21841da177e4SLinus Torvalds 2185e69e9d4aSHATAYAMA Daisuke if (WARN(!PAGE_ALIGNED(addr), "Trying to vfree() bad address (%p)\n", 2186ab15d9b4SDan Carpenter addr)) 21871da177e4SLinus Torvalds return; 21881da177e4SLinus Torvalds 21896ade2032SLiviu Dudau area = find_vm_area(addr); 21901da177e4SLinus Torvalds if (unlikely(!area)) { 21914c8573e2SArjan van de Ven WARN(1, KERN_ERR "Trying to vfree() nonexistent vm area (%p)\n", 21921da177e4SLinus Torvalds addr); 21931da177e4SLinus Torvalds return; 21941da177e4SLinus Torvalds } 21951da177e4SLinus Torvalds 219605e3ff95SChintan Pandya debug_check_no_locks_freed(area->addr, get_vm_area_size(area)); 219705e3ff95SChintan Pandya debug_check_no_obj_freed(area->addr, get_vm_area_size(area)); 21989a11b49aSIngo Molnar 2199868b104dSRick Edgecombe vm_remove_mappings(area, deallocate_pages); 2200868b104dSRick Edgecombe 22011da177e4SLinus Torvalds if (deallocate_pages) { 22021da177e4SLinus Torvalds int i; 22031da177e4SLinus Torvalds 22041da177e4SLinus Torvalds for (i = 0; i < area->nr_pages; i++) { 2205bf53d6f8SChristoph Lameter struct page *page = area->pages[i]; 2206bf53d6f8SChristoph Lameter 2207bf53d6f8SChristoph Lameter BUG_ON(!page); 22084949148aSVladimir Davydov __free_pages(page, 0); 22091da177e4SLinus Torvalds } 22101da177e4SLinus Torvalds 2211244d63eeSDavid Rientjes kvfree(area->pages); 22121da177e4SLinus Torvalds } 22131da177e4SLinus Torvalds 22141da177e4SLinus Torvalds kfree(area); 22151da177e4SLinus Torvalds return; 22161da177e4SLinus Torvalds } 22171da177e4SLinus Torvalds 2218bf22e37aSAndrey Ryabinin static inline void __vfree_deferred(const void *addr) 2219bf22e37aSAndrey Ryabinin { 2220bf22e37aSAndrey Ryabinin /* 2221bf22e37aSAndrey Ryabinin * Use raw_cpu_ptr() because this can be called from preemptible 2222bf22e37aSAndrey Ryabinin * context. Preemption is absolutely fine here, because the llist_add() 2223bf22e37aSAndrey Ryabinin * implementation is lockless, so it works even if we are adding to 2224bf22e37aSAndrey Ryabinin * nother cpu's list. schedule_work() should be fine with this too. 2225bf22e37aSAndrey Ryabinin */ 2226bf22e37aSAndrey Ryabinin struct vfree_deferred *p = raw_cpu_ptr(&vfree_deferred); 2227bf22e37aSAndrey Ryabinin 2228bf22e37aSAndrey Ryabinin if (llist_add((struct llist_node *)addr, &p->list)) 2229bf22e37aSAndrey Ryabinin schedule_work(&p->wq); 2230bf22e37aSAndrey Ryabinin } 2231bf22e37aSAndrey Ryabinin 2232bf22e37aSAndrey Ryabinin /** 2233bf22e37aSAndrey Ryabinin * vfree_atomic - release memory allocated by vmalloc() 2234bf22e37aSAndrey Ryabinin * @addr: memory base address 2235bf22e37aSAndrey Ryabinin * 2236bf22e37aSAndrey Ryabinin * This one is just like vfree() but can be called in any atomic context 2237bf22e37aSAndrey Ryabinin * except NMIs. 2238bf22e37aSAndrey Ryabinin */ 2239bf22e37aSAndrey Ryabinin void vfree_atomic(const void *addr) 2240bf22e37aSAndrey Ryabinin { 2241bf22e37aSAndrey Ryabinin BUG_ON(in_nmi()); 2242bf22e37aSAndrey Ryabinin 2243bf22e37aSAndrey Ryabinin kmemleak_free(addr); 2244bf22e37aSAndrey Ryabinin 2245bf22e37aSAndrey Ryabinin if (!addr) 2246bf22e37aSAndrey Ryabinin return; 2247bf22e37aSAndrey Ryabinin __vfree_deferred(addr); 2248bf22e37aSAndrey Ryabinin } 2249bf22e37aSAndrey Ryabinin 2250c67dc624SRoman Penyaev static void __vfree(const void *addr) 2251c67dc624SRoman Penyaev { 2252c67dc624SRoman Penyaev if (unlikely(in_interrupt())) 2253c67dc624SRoman Penyaev __vfree_deferred(addr); 2254c67dc624SRoman Penyaev else 2255c67dc624SRoman Penyaev __vunmap(addr, 1); 2256c67dc624SRoman Penyaev } 2257c67dc624SRoman Penyaev 22581da177e4SLinus Torvalds /** 22591da177e4SLinus Torvalds * vfree - release memory allocated by vmalloc() 22601da177e4SLinus Torvalds * @addr: memory base address 22611da177e4SLinus Torvalds * 2262183ff22bSSimon Arlott * Free the virtually continuous memory area starting at @addr, as 226380e93effSPekka Enberg * obtained from vmalloc(), vmalloc_32() or __vmalloc(). If @addr is 226480e93effSPekka Enberg * NULL, no operation is performed. 22651da177e4SLinus Torvalds * 226632fcfd40SAl Viro * Must not be called in NMI context (strictly speaking, only if we don't 226732fcfd40SAl Viro * have CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG, but making the calling 226832fcfd40SAl Viro * conventions for vfree() arch-depenedent would be a really bad idea) 226932fcfd40SAl Viro * 22703ca4ea3aSAndrey Ryabinin * May sleep if called *not* from interrupt context. 22713ca4ea3aSAndrey Ryabinin * 22720e056eb5Smchehab@s-opensource.com * NOTE: assumes that the object at @addr has a size >= sizeof(llist_node) 22731da177e4SLinus Torvalds */ 2274b3bdda02SChristoph Lameter void vfree(const void *addr) 22751da177e4SLinus Torvalds { 227632fcfd40SAl Viro BUG_ON(in_nmi()); 227789219d37SCatalin Marinas 227889219d37SCatalin Marinas kmemleak_free(addr); 227989219d37SCatalin Marinas 2280a8dda165SAndrey Ryabinin might_sleep_if(!in_interrupt()); 2281a8dda165SAndrey Ryabinin 228232fcfd40SAl Viro if (!addr) 228332fcfd40SAl Viro return; 2284c67dc624SRoman Penyaev 2285c67dc624SRoman Penyaev __vfree(addr); 22861da177e4SLinus Torvalds } 22871da177e4SLinus Torvalds EXPORT_SYMBOL(vfree); 22881da177e4SLinus Torvalds 22891da177e4SLinus Torvalds /** 22901da177e4SLinus Torvalds * vunmap - release virtual mapping obtained by vmap() 22911da177e4SLinus Torvalds * @addr: memory base address 22921da177e4SLinus Torvalds * 22931da177e4SLinus Torvalds * Free the virtually contiguous memory area starting at @addr, 22941da177e4SLinus Torvalds * which was created from the page array passed to vmap(). 22951da177e4SLinus Torvalds * 229680e93effSPekka Enberg * Must not be called in interrupt context. 22971da177e4SLinus Torvalds */ 2298b3bdda02SChristoph Lameter void vunmap(const void *addr) 22991da177e4SLinus Torvalds { 23001da177e4SLinus Torvalds BUG_ON(in_interrupt()); 230134754b69SPeter Zijlstra might_sleep(); 230232fcfd40SAl Viro if (addr) 23031da177e4SLinus Torvalds __vunmap(addr, 0); 23041da177e4SLinus Torvalds } 23051da177e4SLinus Torvalds EXPORT_SYMBOL(vunmap); 23061da177e4SLinus Torvalds 23071da177e4SLinus Torvalds /** 23081da177e4SLinus Torvalds * vmap - map an array of pages into virtually contiguous space 23091da177e4SLinus Torvalds * @pages: array of page pointers 23101da177e4SLinus Torvalds * @count: number of pages to map 23111da177e4SLinus Torvalds * @flags: vm_area->flags 23121da177e4SLinus Torvalds * @prot: page protection for the mapping 23131da177e4SLinus Torvalds * 23141da177e4SLinus Torvalds * Maps @count pages from @pages into contiguous kernel virtual 23151da177e4SLinus Torvalds * space. 2316a862f68aSMike Rapoport * 2317a862f68aSMike Rapoport * Return: the address of the area or %NULL on failure 23181da177e4SLinus Torvalds */ 23191da177e4SLinus Torvalds void *vmap(struct page **pages, unsigned int count, 23201da177e4SLinus Torvalds unsigned long flags, pgprot_t prot) 23211da177e4SLinus Torvalds { 23221da177e4SLinus Torvalds struct vm_struct *area; 232365ee03c4SGuillermo Julián Moreno unsigned long size; /* In bytes */ 23241da177e4SLinus Torvalds 232534754b69SPeter Zijlstra might_sleep(); 232634754b69SPeter Zijlstra 2327ca79b0c2SArun KS if (count > totalram_pages()) 23281da177e4SLinus Torvalds return NULL; 23291da177e4SLinus Torvalds 233065ee03c4SGuillermo Julián Moreno size = (unsigned long)count << PAGE_SHIFT; 233165ee03c4SGuillermo Julián Moreno area = get_vm_area_caller(size, flags, __builtin_return_address(0)); 23321da177e4SLinus Torvalds if (!area) 23331da177e4SLinus Torvalds return NULL; 233423016969SChristoph Lameter 2335f6f8ed47SWANG Chao if (map_vm_area(area, prot, pages)) { 23361da177e4SLinus Torvalds vunmap(area->addr); 23371da177e4SLinus Torvalds return NULL; 23381da177e4SLinus Torvalds } 23391da177e4SLinus Torvalds 23401da177e4SLinus Torvalds return area->addr; 23411da177e4SLinus Torvalds } 23421da177e4SLinus Torvalds EXPORT_SYMBOL(vmap); 23431da177e4SLinus Torvalds 23448594a21cSMichal Hocko static void *__vmalloc_node(unsigned long size, unsigned long align, 23458594a21cSMichal Hocko gfp_t gfp_mask, pgprot_t prot, 23468594a21cSMichal Hocko int node, const void *caller); 2347e31d9eb5SAdrian Bunk static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask, 23483722e13cSWanpeng Li pgprot_t prot, int node) 23491da177e4SLinus Torvalds { 23501da177e4SLinus Torvalds struct page **pages; 23511da177e4SLinus Torvalds unsigned int nr_pages, array_size, i; 2352930f036bSDavid Rientjes const gfp_t nested_gfp = (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO; 2353704b862fSLaura Abbott const gfp_t alloc_mask = gfp_mask | __GFP_NOWARN; 2354704b862fSLaura Abbott const gfp_t highmem_mask = (gfp_mask & (GFP_DMA | GFP_DMA32)) ? 2355704b862fSLaura Abbott 0 : 2356704b862fSLaura Abbott __GFP_HIGHMEM; 23571da177e4SLinus Torvalds 2358762216abSWanpeng Li nr_pages = get_vm_area_size(area) >> PAGE_SHIFT; 23591da177e4SLinus Torvalds array_size = (nr_pages * sizeof(struct page *)); 23601da177e4SLinus Torvalds 23611da177e4SLinus Torvalds area->nr_pages = nr_pages; 23621da177e4SLinus Torvalds /* Please note that the recursion is strictly bounded. */ 23638757d5faSJan Kiszka if (array_size > PAGE_SIZE) { 2364704b862fSLaura Abbott pages = __vmalloc_node(array_size, 1, nested_gfp|highmem_mask, 23653722e13cSWanpeng Li PAGE_KERNEL, node, area->caller); 2366286e1ea3SAndrew Morton } else { 2367976d6dfbSJan Beulich pages = kmalloc_node(array_size, nested_gfp, node); 2368286e1ea3SAndrew Morton } 23691da177e4SLinus Torvalds area->pages = pages; 23701da177e4SLinus Torvalds if (!area->pages) { 23711da177e4SLinus Torvalds remove_vm_area(area->addr); 23721da177e4SLinus Torvalds kfree(area); 23731da177e4SLinus Torvalds return NULL; 23741da177e4SLinus Torvalds } 23751da177e4SLinus Torvalds 23761da177e4SLinus Torvalds for (i = 0; i < area->nr_pages; i++) { 2377bf53d6f8SChristoph Lameter struct page *page; 2378bf53d6f8SChristoph Lameter 23794b90951cSJianguo Wu if (node == NUMA_NO_NODE) 2380704b862fSLaura Abbott page = alloc_page(alloc_mask|highmem_mask); 2381930fc45aSChristoph Lameter else 2382704b862fSLaura Abbott page = alloc_pages_node(node, alloc_mask|highmem_mask, 0); 2383bf53d6f8SChristoph Lameter 2384bf53d6f8SChristoph Lameter if (unlikely(!page)) { 23851da177e4SLinus Torvalds /* Successfully allocated i pages, free them in __vunmap() */ 23861da177e4SLinus Torvalds area->nr_pages = i; 23871da177e4SLinus Torvalds goto fail; 23881da177e4SLinus Torvalds } 2389bf53d6f8SChristoph Lameter area->pages[i] = page; 2390704b862fSLaura Abbott if (gfpflags_allow_blocking(gfp_mask|highmem_mask)) 2391660654f9SEric Dumazet cond_resched(); 23921da177e4SLinus Torvalds } 23931da177e4SLinus Torvalds 2394f6f8ed47SWANG Chao if (map_vm_area(area, prot, pages)) 23951da177e4SLinus Torvalds goto fail; 23961da177e4SLinus Torvalds return area->addr; 23971da177e4SLinus Torvalds 23981da177e4SLinus Torvalds fail: 2399a8e99259SMichal Hocko warn_alloc(gfp_mask, NULL, 24007877cdccSMichal Hocko "vmalloc: allocation failure, allocated %ld of %ld bytes", 240122943ab1SDave Hansen (area->nr_pages*PAGE_SIZE), area->size); 2402c67dc624SRoman Penyaev __vfree(area->addr); 24031da177e4SLinus Torvalds return NULL; 24041da177e4SLinus Torvalds } 24051da177e4SLinus Torvalds 2406d0a21265SDavid Rientjes /** 2407d0a21265SDavid Rientjes * __vmalloc_node_range - allocate virtually contiguous memory 2408d0a21265SDavid Rientjes * @size: allocation size 2409d0a21265SDavid Rientjes * @align: desired alignment 2410d0a21265SDavid Rientjes * @start: vm area range start 2411d0a21265SDavid Rientjes * @end: vm area range end 2412d0a21265SDavid Rientjes * @gfp_mask: flags for the page level allocator 2413d0a21265SDavid Rientjes * @prot: protection mask for the allocated pages 2414cb9e3c29SAndrey Ryabinin * @vm_flags: additional vm area flags (e.g. %VM_NO_GUARD) 241500ef2d2fSDavid Rientjes * @node: node to use for allocation or NUMA_NO_NODE 2416d0a21265SDavid Rientjes * @caller: caller's return address 2417d0a21265SDavid Rientjes * 2418d0a21265SDavid Rientjes * Allocate enough pages to cover @size from the page level 2419d0a21265SDavid Rientjes * allocator with @gfp_mask flags. Map them into contiguous 2420d0a21265SDavid Rientjes * kernel virtual space, using a pagetable protection of @prot. 2421a862f68aSMike Rapoport * 2422a862f68aSMike Rapoport * Return: the address of the area or %NULL on failure 2423d0a21265SDavid Rientjes */ 2424d0a21265SDavid Rientjes void *__vmalloc_node_range(unsigned long size, unsigned long align, 2425d0a21265SDavid Rientjes unsigned long start, unsigned long end, gfp_t gfp_mask, 2426cb9e3c29SAndrey Ryabinin pgprot_t prot, unsigned long vm_flags, int node, 2427cb9e3c29SAndrey Ryabinin const void *caller) 2428930fc45aSChristoph Lameter { 2429d0a21265SDavid Rientjes struct vm_struct *area; 2430d0a21265SDavid Rientjes void *addr; 2431d0a21265SDavid Rientjes unsigned long real_size = size; 2432d0a21265SDavid Rientjes 2433d0a21265SDavid Rientjes size = PAGE_ALIGN(size); 2434ca79b0c2SArun KS if (!size || (size >> PAGE_SHIFT) > totalram_pages()) 2435de7d2b56SJoe Perches goto fail; 2436d0a21265SDavid Rientjes 2437cb9e3c29SAndrey Ryabinin area = __get_vm_area_node(size, align, VM_ALLOC | VM_UNINITIALIZED | 2438cb9e3c29SAndrey Ryabinin vm_flags, start, end, node, gfp_mask, caller); 2439d0a21265SDavid Rientjes if (!area) 2440de7d2b56SJoe Perches goto fail; 2441d0a21265SDavid Rientjes 24423722e13cSWanpeng Li addr = __vmalloc_area_node(area, gfp_mask, prot, node); 24431368edf0SMel Gorman if (!addr) 2444b82225f3SWanpeng Li return NULL; 244589219d37SCatalin Marinas 244689219d37SCatalin Marinas /* 244720fc02b4SZhang Yanfei * In this function, newly allocated vm_struct has VM_UNINITIALIZED 244820fc02b4SZhang Yanfei * flag. It means that vm_struct is not fully initialized. 24494341fa45SJoonsoo Kim * Now, it is fully initialized, so remove this flag here. 2450f5252e00SMitsuo Hayasaka */ 245120fc02b4SZhang Yanfei clear_vm_uninitialized_flag(area); 2452f5252e00SMitsuo Hayasaka 245394f4a161SCatalin Marinas kmemleak_vmalloc(area, size, gfp_mask); 245489219d37SCatalin Marinas 245589219d37SCatalin Marinas return addr; 2456de7d2b56SJoe Perches 2457de7d2b56SJoe Perches fail: 2458a8e99259SMichal Hocko warn_alloc(gfp_mask, NULL, 24597877cdccSMichal Hocko "vmalloc: allocation failure: %lu bytes", real_size); 2460de7d2b56SJoe Perches return NULL; 2461930fc45aSChristoph Lameter } 2462930fc45aSChristoph Lameter 2463153178edSUladzislau Rezki (Sony) /* 2464153178edSUladzislau Rezki (Sony) * This is only for performance analysis of vmalloc and stress purpose. 2465153178edSUladzislau Rezki (Sony) * It is required by vmalloc test module, therefore do not use it other 2466153178edSUladzislau Rezki (Sony) * than that. 2467153178edSUladzislau Rezki (Sony) */ 2468153178edSUladzislau Rezki (Sony) #ifdef CONFIG_TEST_VMALLOC_MODULE 2469153178edSUladzislau Rezki (Sony) EXPORT_SYMBOL_GPL(__vmalloc_node_range); 2470153178edSUladzislau Rezki (Sony) #endif 2471153178edSUladzislau Rezki (Sony) 24721da177e4SLinus Torvalds /** 2473930fc45aSChristoph Lameter * __vmalloc_node - allocate virtually contiguous memory 24741da177e4SLinus Torvalds * @size: allocation size 24752dca6999SDavid Miller * @align: desired alignment 24761da177e4SLinus Torvalds * @gfp_mask: flags for the page level allocator 24771da177e4SLinus Torvalds * @prot: protection mask for the allocated pages 247800ef2d2fSDavid Rientjes * @node: node to use for allocation or NUMA_NO_NODE 2479c85d194bSRandy Dunlap * @caller: caller's return address 24801da177e4SLinus Torvalds * 24811da177e4SLinus Torvalds * Allocate enough pages to cover @size from the page level 24821da177e4SLinus Torvalds * allocator with @gfp_mask flags. Map them into contiguous 24831da177e4SLinus Torvalds * kernel virtual space, using a pagetable protection of @prot. 2484a7c3e901SMichal Hocko * 2485dcda9b04SMichal Hocko * Reclaim modifiers in @gfp_mask - __GFP_NORETRY, __GFP_RETRY_MAYFAIL 2486a7c3e901SMichal Hocko * and __GFP_NOFAIL are not supported 2487a7c3e901SMichal Hocko * 2488a7c3e901SMichal Hocko * Any use of gfp flags outside of GFP_KERNEL should be consulted 2489a7c3e901SMichal Hocko * with mm people. 2490a862f68aSMike Rapoport * 2491a862f68aSMike Rapoport * Return: pointer to the allocated memory or %NULL on error 24921da177e4SLinus Torvalds */ 24938594a21cSMichal Hocko static void *__vmalloc_node(unsigned long size, unsigned long align, 24942dca6999SDavid Miller gfp_t gfp_mask, pgprot_t prot, 24955e6cafc8SMarek Szyprowski int node, const void *caller) 24961da177e4SLinus Torvalds { 2497d0a21265SDavid Rientjes return __vmalloc_node_range(size, align, VMALLOC_START, VMALLOC_END, 2498cb9e3c29SAndrey Ryabinin gfp_mask, prot, 0, node, caller); 24991da177e4SLinus Torvalds } 25001da177e4SLinus Torvalds 2501930fc45aSChristoph Lameter void *__vmalloc(unsigned long size, gfp_t gfp_mask, pgprot_t prot) 2502930fc45aSChristoph Lameter { 250300ef2d2fSDavid Rientjes return __vmalloc_node(size, 1, gfp_mask, prot, NUMA_NO_NODE, 250423016969SChristoph Lameter __builtin_return_address(0)); 2505930fc45aSChristoph Lameter } 25061da177e4SLinus Torvalds EXPORT_SYMBOL(__vmalloc); 25071da177e4SLinus Torvalds 25088594a21cSMichal Hocko static inline void *__vmalloc_node_flags(unsigned long size, 25098594a21cSMichal Hocko int node, gfp_t flags) 25108594a21cSMichal Hocko { 25118594a21cSMichal Hocko return __vmalloc_node(size, 1, flags, PAGE_KERNEL, 25128594a21cSMichal Hocko node, __builtin_return_address(0)); 25138594a21cSMichal Hocko } 25148594a21cSMichal Hocko 25158594a21cSMichal Hocko 25168594a21cSMichal Hocko void *__vmalloc_node_flags_caller(unsigned long size, int node, gfp_t flags, 25178594a21cSMichal Hocko void *caller) 25188594a21cSMichal Hocko { 25198594a21cSMichal Hocko return __vmalloc_node(size, 1, flags, PAGE_KERNEL, node, caller); 25208594a21cSMichal Hocko } 25218594a21cSMichal Hocko 25221da177e4SLinus Torvalds /** 25231da177e4SLinus Torvalds * vmalloc - allocate virtually contiguous memory 25241da177e4SLinus Torvalds * @size: allocation size 252592eac168SMike Rapoport * 25261da177e4SLinus Torvalds * Allocate enough pages to cover @size from the page level 25271da177e4SLinus Torvalds * allocator and map them into contiguous kernel virtual space. 25281da177e4SLinus Torvalds * 2529c1c8897fSMichael Opdenacker * For tight control over page level allocator and protection flags 25301da177e4SLinus Torvalds * use __vmalloc() instead. 2531a862f68aSMike Rapoport * 2532a862f68aSMike Rapoport * Return: pointer to the allocated memory or %NULL on error 25331da177e4SLinus Torvalds */ 25341da177e4SLinus Torvalds void *vmalloc(unsigned long size) 25351da177e4SLinus Torvalds { 253600ef2d2fSDavid Rientjes return __vmalloc_node_flags(size, NUMA_NO_NODE, 253719809c2dSMichal Hocko GFP_KERNEL); 25381da177e4SLinus Torvalds } 25391da177e4SLinus Torvalds EXPORT_SYMBOL(vmalloc); 25401da177e4SLinus Torvalds 2541930fc45aSChristoph Lameter /** 2542e1ca7788SDave Young * vzalloc - allocate virtually contiguous memory with zero fill 2543e1ca7788SDave Young * @size: allocation size 254492eac168SMike Rapoport * 2545e1ca7788SDave Young * Allocate enough pages to cover @size from the page level 2546e1ca7788SDave Young * allocator and map them into contiguous kernel virtual space. 2547e1ca7788SDave Young * The memory allocated is set to zero. 2548e1ca7788SDave Young * 2549e1ca7788SDave Young * For tight control over page level allocator and protection flags 2550e1ca7788SDave Young * use __vmalloc() instead. 2551a862f68aSMike Rapoport * 2552a862f68aSMike Rapoport * Return: pointer to the allocated memory or %NULL on error 2553e1ca7788SDave Young */ 2554e1ca7788SDave Young void *vzalloc(unsigned long size) 2555e1ca7788SDave Young { 255600ef2d2fSDavid Rientjes return __vmalloc_node_flags(size, NUMA_NO_NODE, 255719809c2dSMichal Hocko GFP_KERNEL | __GFP_ZERO); 2558e1ca7788SDave Young } 2559e1ca7788SDave Young EXPORT_SYMBOL(vzalloc); 2560e1ca7788SDave Young 2561e1ca7788SDave Young /** 2562ead04089SRolf Eike Beer * vmalloc_user - allocate zeroed virtually contiguous memory for userspace 256383342314SNick Piggin * @size: allocation size 2564ead04089SRolf Eike Beer * 2565ead04089SRolf Eike Beer * The resulting memory area is zeroed so it can be mapped to userspace 2566ead04089SRolf Eike Beer * without leaking data. 2567a862f68aSMike Rapoport * 2568a862f68aSMike Rapoport * Return: pointer to the allocated memory or %NULL on error 256983342314SNick Piggin */ 257083342314SNick Piggin void *vmalloc_user(unsigned long size) 257183342314SNick Piggin { 2572bc84c535SRoman Penyaev return __vmalloc_node_range(size, SHMLBA, VMALLOC_START, VMALLOC_END, 2573bc84c535SRoman Penyaev GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL, 2574bc84c535SRoman Penyaev VM_USERMAP, NUMA_NO_NODE, 257500ef2d2fSDavid Rientjes __builtin_return_address(0)); 257683342314SNick Piggin } 257783342314SNick Piggin EXPORT_SYMBOL(vmalloc_user); 257883342314SNick Piggin 257983342314SNick Piggin /** 2580930fc45aSChristoph Lameter * vmalloc_node - allocate memory on a specific node 2581930fc45aSChristoph Lameter * @size: allocation size 2582d44e0780SRandy Dunlap * @node: numa node 2583930fc45aSChristoph Lameter * 2584930fc45aSChristoph Lameter * Allocate enough pages to cover @size from the page level 2585930fc45aSChristoph Lameter * allocator and map them into contiguous kernel virtual space. 2586930fc45aSChristoph Lameter * 2587c1c8897fSMichael Opdenacker * For tight control over page level allocator and protection flags 2588930fc45aSChristoph Lameter * use __vmalloc() instead. 2589a862f68aSMike Rapoport * 2590a862f68aSMike Rapoport * Return: pointer to the allocated memory or %NULL on error 2591930fc45aSChristoph Lameter */ 2592930fc45aSChristoph Lameter void *vmalloc_node(unsigned long size, int node) 2593930fc45aSChristoph Lameter { 259419809c2dSMichal Hocko return __vmalloc_node(size, 1, GFP_KERNEL, PAGE_KERNEL, 259523016969SChristoph Lameter node, __builtin_return_address(0)); 2596930fc45aSChristoph Lameter } 2597930fc45aSChristoph Lameter EXPORT_SYMBOL(vmalloc_node); 2598930fc45aSChristoph Lameter 2599e1ca7788SDave Young /** 2600e1ca7788SDave Young * vzalloc_node - allocate memory on a specific node with zero fill 2601e1ca7788SDave Young * @size: allocation size 2602e1ca7788SDave Young * @node: numa node 2603e1ca7788SDave Young * 2604e1ca7788SDave Young * Allocate enough pages to cover @size from the page level 2605e1ca7788SDave Young * allocator and map them into contiguous kernel virtual space. 2606e1ca7788SDave Young * The memory allocated is set to zero. 2607e1ca7788SDave Young * 2608e1ca7788SDave Young * For tight control over page level allocator and protection flags 2609e1ca7788SDave Young * use __vmalloc_node() instead. 2610a862f68aSMike Rapoport * 2611a862f68aSMike Rapoport * Return: pointer to the allocated memory or %NULL on error 2612e1ca7788SDave Young */ 2613e1ca7788SDave Young void *vzalloc_node(unsigned long size, int node) 2614e1ca7788SDave Young { 2615e1ca7788SDave Young return __vmalloc_node_flags(size, node, 261619809c2dSMichal Hocko GFP_KERNEL | __GFP_ZERO); 2617e1ca7788SDave Young } 2618e1ca7788SDave Young EXPORT_SYMBOL(vzalloc_node); 2619e1ca7788SDave Young 26201da177e4SLinus Torvalds /** 26211da177e4SLinus Torvalds * vmalloc_exec - allocate virtually contiguous, executable memory 26221da177e4SLinus Torvalds * @size: allocation size 26231da177e4SLinus Torvalds * 26241da177e4SLinus Torvalds * Kernel-internal function to allocate enough pages to cover @size 26251da177e4SLinus Torvalds * the page level allocator and map them into contiguous and 26261da177e4SLinus Torvalds * executable kernel virtual space. 26271da177e4SLinus Torvalds * 2628c1c8897fSMichael Opdenacker * For tight control over page level allocator and protection flags 26291da177e4SLinus Torvalds * use __vmalloc() instead. 2630a862f68aSMike Rapoport * 2631a862f68aSMike Rapoport * Return: pointer to the allocated memory or %NULL on error 26321da177e4SLinus Torvalds */ 26331da177e4SLinus Torvalds void *vmalloc_exec(unsigned long size) 26341da177e4SLinus Torvalds { 2635868b104dSRick Edgecombe return __vmalloc_node_range(size, 1, VMALLOC_START, VMALLOC_END, 2636868b104dSRick Edgecombe GFP_KERNEL, PAGE_KERNEL_EXEC, VM_FLUSH_RESET_PERMS, 263700ef2d2fSDavid Rientjes NUMA_NO_NODE, __builtin_return_address(0)); 26381da177e4SLinus Torvalds } 26391da177e4SLinus Torvalds 26400d08e0d3SAndi Kleen #if defined(CONFIG_64BIT) && defined(CONFIG_ZONE_DMA32) 2641698d0831SMichal Hocko #define GFP_VMALLOC32 (GFP_DMA32 | GFP_KERNEL) 26420d08e0d3SAndi Kleen #elif defined(CONFIG_64BIT) && defined(CONFIG_ZONE_DMA) 2643698d0831SMichal Hocko #define GFP_VMALLOC32 (GFP_DMA | GFP_KERNEL) 26440d08e0d3SAndi Kleen #else 2645698d0831SMichal Hocko /* 2646698d0831SMichal Hocko * 64b systems should always have either DMA or DMA32 zones. For others 2647698d0831SMichal Hocko * GFP_DMA32 should do the right thing and use the normal zone. 2648698d0831SMichal Hocko */ 2649698d0831SMichal Hocko #define GFP_VMALLOC32 GFP_DMA32 | GFP_KERNEL 26500d08e0d3SAndi Kleen #endif 26510d08e0d3SAndi Kleen 26521da177e4SLinus Torvalds /** 26531da177e4SLinus Torvalds * vmalloc_32 - allocate virtually contiguous memory (32bit addressable) 26541da177e4SLinus Torvalds * @size: allocation size 26551da177e4SLinus Torvalds * 26561da177e4SLinus Torvalds * Allocate enough 32bit PA addressable pages to cover @size from the 26571da177e4SLinus Torvalds * page level allocator and map them into contiguous kernel virtual space. 2658a862f68aSMike Rapoport * 2659a862f68aSMike Rapoport * Return: pointer to the allocated memory or %NULL on error 26601da177e4SLinus Torvalds */ 26611da177e4SLinus Torvalds void *vmalloc_32(unsigned long size) 26621da177e4SLinus Torvalds { 26632dca6999SDavid Miller return __vmalloc_node(size, 1, GFP_VMALLOC32, PAGE_KERNEL, 266400ef2d2fSDavid Rientjes NUMA_NO_NODE, __builtin_return_address(0)); 26651da177e4SLinus Torvalds } 26661da177e4SLinus Torvalds EXPORT_SYMBOL(vmalloc_32); 26671da177e4SLinus Torvalds 266883342314SNick Piggin /** 2669ead04089SRolf Eike Beer * vmalloc_32_user - allocate zeroed virtually contiguous 32bit memory 267083342314SNick Piggin * @size: allocation size 2671ead04089SRolf Eike Beer * 2672ead04089SRolf Eike Beer * The resulting memory area is 32bit addressable and zeroed so it can be 2673ead04089SRolf Eike Beer * mapped to userspace without leaking data. 2674a862f68aSMike Rapoport * 2675a862f68aSMike Rapoport * Return: pointer to the allocated memory or %NULL on error 267683342314SNick Piggin */ 267783342314SNick Piggin void *vmalloc_32_user(unsigned long size) 267883342314SNick Piggin { 2679bc84c535SRoman Penyaev return __vmalloc_node_range(size, SHMLBA, VMALLOC_START, VMALLOC_END, 2680bc84c535SRoman Penyaev GFP_VMALLOC32 | __GFP_ZERO, PAGE_KERNEL, 2681bc84c535SRoman Penyaev VM_USERMAP, NUMA_NO_NODE, 26825a82ac71SRoman Penyaev __builtin_return_address(0)); 268383342314SNick Piggin } 268483342314SNick Piggin EXPORT_SYMBOL(vmalloc_32_user); 268583342314SNick Piggin 2686d0107eb0SKAMEZAWA Hiroyuki /* 2687d0107eb0SKAMEZAWA Hiroyuki * small helper routine , copy contents to buf from addr. 2688d0107eb0SKAMEZAWA Hiroyuki * If the page is not present, fill zero. 2689d0107eb0SKAMEZAWA Hiroyuki */ 2690d0107eb0SKAMEZAWA Hiroyuki 2691d0107eb0SKAMEZAWA Hiroyuki static int aligned_vread(char *buf, char *addr, unsigned long count) 2692d0107eb0SKAMEZAWA Hiroyuki { 2693d0107eb0SKAMEZAWA Hiroyuki struct page *p; 2694d0107eb0SKAMEZAWA Hiroyuki int copied = 0; 2695d0107eb0SKAMEZAWA Hiroyuki 2696d0107eb0SKAMEZAWA Hiroyuki while (count) { 2697d0107eb0SKAMEZAWA Hiroyuki unsigned long offset, length; 2698d0107eb0SKAMEZAWA Hiroyuki 2699891c49abSAlexander Kuleshov offset = offset_in_page(addr); 2700d0107eb0SKAMEZAWA Hiroyuki length = PAGE_SIZE - offset; 2701d0107eb0SKAMEZAWA Hiroyuki if (length > count) 2702d0107eb0SKAMEZAWA Hiroyuki length = count; 2703d0107eb0SKAMEZAWA Hiroyuki p = vmalloc_to_page(addr); 2704d0107eb0SKAMEZAWA Hiroyuki /* 2705d0107eb0SKAMEZAWA Hiroyuki * To do safe access to this _mapped_ area, we need 2706d0107eb0SKAMEZAWA Hiroyuki * lock. But adding lock here means that we need to add 2707d0107eb0SKAMEZAWA Hiroyuki * overhead of vmalloc()/vfree() calles for this _debug_ 2708d0107eb0SKAMEZAWA Hiroyuki * interface, rarely used. Instead of that, we'll use 2709d0107eb0SKAMEZAWA Hiroyuki * kmap() and get small overhead in this access function. 2710d0107eb0SKAMEZAWA Hiroyuki */ 2711d0107eb0SKAMEZAWA Hiroyuki if (p) { 2712d0107eb0SKAMEZAWA Hiroyuki /* 2713d0107eb0SKAMEZAWA Hiroyuki * we can expect USER0 is not used (see vread/vwrite's 2714d0107eb0SKAMEZAWA Hiroyuki * function description) 2715d0107eb0SKAMEZAWA Hiroyuki */ 27169b04c5feSCong Wang void *map = kmap_atomic(p); 2717d0107eb0SKAMEZAWA Hiroyuki memcpy(buf, map + offset, length); 27189b04c5feSCong Wang kunmap_atomic(map); 2719d0107eb0SKAMEZAWA Hiroyuki } else 2720d0107eb0SKAMEZAWA Hiroyuki memset(buf, 0, length); 2721d0107eb0SKAMEZAWA Hiroyuki 2722d0107eb0SKAMEZAWA Hiroyuki addr += length; 2723d0107eb0SKAMEZAWA Hiroyuki buf += length; 2724d0107eb0SKAMEZAWA Hiroyuki copied += length; 2725d0107eb0SKAMEZAWA Hiroyuki count -= length; 2726d0107eb0SKAMEZAWA Hiroyuki } 2727d0107eb0SKAMEZAWA Hiroyuki return copied; 2728d0107eb0SKAMEZAWA Hiroyuki } 2729d0107eb0SKAMEZAWA Hiroyuki 2730d0107eb0SKAMEZAWA Hiroyuki static int aligned_vwrite(char *buf, char *addr, unsigned long count) 2731d0107eb0SKAMEZAWA Hiroyuki { 2732d0107eb0SKAMEZAWA Hiroyuki struct page *p; 2733d0107eb0SKAMEZAWA Hiroyuki int copied = 0; 2734d0107eb0SKAMEZAWA Hiroyuki 2735d0107eb0SKAMEZAWA Hiroyuki while (count) { 2736d0107eb0SKAMEZAWA Hiroyuki unsigned long offset, length; 2737d0107eb0SKAMEZAWA Hiroyuki 2738891c49abSAlexander Kuleshov offset = offset_in_page(addr); 2739d0107eb0SKAMEZAWA Hiroyuki length = PAGE_SIZE - offset; 2740d0107eb0SKAMEZAWA Hiroyuki if (length > count) 2741d0107eb0SKAMEZAWA Hiroyuki length = count; 2742d0107eb0SKAMEZAWA Hiroyuki p = vmalloc_to_page(addr); 2743d0107eb0SKAMEZAWA Hiroyuki /* 2744d0107eb0SKAMEZAWA Hiroyuki * To do safe access to this _mapped_ area, we need 2745d0107eb0SKAMEZAWA Hiroyuki * lock. But adding lock here means that we need to add 2746d0107eb0SKAMEZAWA Hiroyuki * overhead of vmalloc()/vfree() calles for this _debug_ 2747d0107eb0SKAMEZAWA Hiroyuki * interface, rarely used. Instead of that, we'll use 2748d0107eb0SKAMEZAWA Hiroyuki * kmap() and get small overhead in this access function. 2749d0107eb0SKAMEZAWA Hiroyuki */ 2750d0107eb0SKAMEZAWA Hiroyuki if (p) { 2751d0107eb0SKAMEZAWA Hiroyuki /* 2752d0107eb0SKAMEZAWA Hiroyuki * we can expect USER0 is not used (see vread/vwrite's 2753d0107eb0SKAMEZAWA Hiroyuki * function description) 2754d0107eb0SKAMEZAWA Hiroyuki */ 27559b04c5feSCong Wang void *map = kmap_atomic(p); 2756d0107eb0SKAMEZAWA Hiroyuki memcpy(map + offset, buf, length); 27579b04c5feSCong Wang kunmap_atomic(map); 2758d0107eb0SKAMEZAWA Hiroyuki } 2759d0107eb0SKAMEZAWA Hiroyuki addr += length; 2760d0107eb0SKAMEZAWA Hiroyuki buf += length; 2761d0107eb0SKAMEZAWA Hiroyuki copied += length; 2762d0107eb0SKAMEZAWA Hiroyuki count -= length; 2763d0107eb0SKAMEZAWA Hiroyuki } 2764d0107eb0SKAMEZAWA Hiroyuki return copied; 2765d0107eb0SKAMEZAWA Hiroyuki } 2766d0107eb0SKAMEZAWA Hiroyuki 2767d0107eb0SKAMEZAWA Hiroyuki /** 2768d0107eb0SKAMEZAWA Hiroyuki * vread() - read vmalloc area in a safe way. 2769d0107eb0SKAMEZAWA Hiroyuki * @buf: buffer for reading data 2770d0107eb0SKAMEZAWA Hiroyuki * @addr: vm address. 2771d0107eb0SKAMEZAWA Hiroyuki * @count: number of bytes to be read. 2772d0107eb0SKAMEZAWA Hiroyuki * 2773d0107eb0SKAMEZAWA Hiroyuki * This function checks that addr is a valid vmalloc'ed area, and 2774d0107eb0SKAMEZAWA Hiroyuki * copy data from that area to a given buffer. If the given memory range 2775d0107eb0SKAMEZAWA Hiroyuki * of [addr...addr+count) includes some valid address, data is copied to 2776d0107eb0SKAMEZAWA Hiroyuki * proper area of @buf. If there are memory holes, they'll be zero-filled. 2777d0107eb0SKAMEZAWA Hiroyuki * IOREMAP area is treated as memory hole and no copy is done. 2778d0107eb0SKAMEZAWA Hiroyuki * 2779d0107eb0SKAMEZAWA Hiroyuki * If [addr...addr+count) doesn't includes any intersects with alive 2780a8e5202dSCong Wang * vm_struct area, returns 0. @buf should be kernel's buffer. 2781d0107eb0SKAMEZAWA Hiroyuki * 2782d0107eb0SKAMEZAWA Hiroyuki * Note: In usual ops, vread() is never necessary because the caller 2783d0107eb0SKAMEZAWA Hiroyuki * should know vmalloc() area is valid and can use memcpy(). 2784d0107eb0SKAMEZAWA Hiroyuki * This is for routines which have to access vmalloc area without 2785d0107eb0SKAMEZAWA Hiroyuki * any informaion, as /dev/kmem. 2786a862f68aSMike Rapoport * 2787a862f68aSMike Rapoport * Return: number of bytes for which addr and buf should be increased 2788a862f68aSMike Rapoport * (same number as @count) or %0 if [addr...addr+count) doesn't 2789a862f68aSMike Rapoport * include any intersection with valid vmalloc area 2790d0107eb0SKAMEZAWA Hiroyuki */ 27911da177e4SLinus Torvalds long vread(char *buf, char *addr, unsigned long count) 27921da177e4SLinus Torvalds { 2793e81ce85fSJoonsoo Kim struct vmap_area *va; 2794e81ce85fSJoonsoo Kim struct vm_struct *vm; 27951da177e4SLinus Torvalds char *vaddr, *buf_start = buf; 2796d0107eb0SKAMEZAWA Hiroyuki unsigned long buflen = count; 27971da177e4SLinus Torvalds unsigned long n; 27981da177e4SLinus Torvalds 27991da177e4SLinus Torvalds /* Don't allow overflow */ 28001da177e4SLinus Torvalds if ((unsigned long) addr + count < count) 28011da177e4SLinus Torvalds count = -(unsigned long) addr; 28021da177e4SLinus Torvalds 2803e81ce85fSJoonsoo Kim spin_lock(&vmap_area_lock); 2804e81ce85fSJoonsoo Kim list_for_each_entry(va, &vmap_area_list, list) { 2805e81ce85fSJoonsoo Kim if (!count) 2806e81ce85fSJoonsoo Kim break; 2807e81ce85fSJoonsoo Kim 2808e81ce85fSJoonsoo Kim if (!(va->flags & VM_VM_AREA)) 2809e81ce85fSJoonsoo Kim continue; 2810e81ce85fSJoonsoo Kim 2811e81ce85fSJoonsoo Kim vm = va->vm; 2812e81ce85fSJoonsoo Kim vaddr = (char *) vm->addr; 2813762216abSWanpeng Li if (addr >= vaddr + get_vm_area_size(vm)) 28141da177e4SLinus Torvalds continue; 28151da177e4SLinus Torvalds while (addr < vaddr) { 28161da177e4SLinus Torvalds if (count == 0) 28171da177e4SLinus Torvalds goto finished; 28181da177e4SLinus Torvalds *buf = '\0'; 28191da177e4SLinus Torvalds buf++; 28201da177e4SLinus Torvalds addr++; 28211da177e4SLinus Torvalds count--; 28221da177e4SLinus Torvalds } 2823762216abSWanpeng Li n = vaddr + get_vm_area_size(vm) - addr; 2824d0107eb0SKAMEZAWA Hiroyuki if (n > count) 2825d0107eb0SKAMEZAWA Hiroyuki n = count; 2826e81ce85fSJoonsoo Kim if (!(vm->flags & VM_IOREMAP)) 2827d0107eb0SKAMEZAWA Hiroyuki aligned_vread(buf, addr, n); 2828d0107eb0SKAMEZAWA Hiroyuki else /* IOREMAP area is treated as memory hole */ 2829d0107eb0SKAMEZAWA Hiroyuki memset(buf, 0, n); 2830d0107eb0SKAMEZAWA Hiroyuki buf += n; 2831d0107eb0SKAMEZAWA Hiroyuki addr += n; 2832d0107eb0SKAMEZAWA Hiroyuki count -= n; 28331da177e4SLinus Torvalds } 28341da177e4SLinus Torvalds finished: 2835e81ce85fSJoonsoo Kim spin_unlock(&vmap_area_lock); 2836d0107eb0SKAMEZAWA Hiroyuki 2837d0107eb0SKAMEZAWA Hiroyuki if (buf == buf_start) 2838d0107eb0SKAMEZAWA Hiroyuki return 0; 2839d0107eb0SKAMEZAWA Hiroyuki /* zero-fill memory holes */ 2840d0107eb0SKAMEZAWA Hiroyuki if (buf != buf_start + buflen) 2841d0107eb0SKAMEZAWA Hiroyuki memset(buf, 0, buflen - (buf - buf_start)); 2842d0107eb0SKAMEZAWA Hiroyuki 2843d0107eb0SKAMEZAWA Hiroyuki return buflen; 28441da177e4SLinus Torvalds } 28451da177e4SLinus Torvalds 2846d0107eb0SKAMEZAWA Hiroyuki /** 2847d0107eb0SKAMEZAWA Hiroyuki * vwrite() - write vmalloc area in a safe way. 2848d0107eb0SKAMEZAWA Hiroyuki * @buf: buffer for source data 2849d0107eb0SKAMEZAWA Hiroyuki * @addr: vm address. 2850d0107eb0SKAMEZAWA Hiroyuki * @count: number of bytes to be read. 2851d0107eb0SKAMEZAWA Hiroyuki * 2852d0107eb0SKAMEZAWA Hiroyuki * This function checks that addr is a valid vmalloc'ed area, and 2853d0107eb0SKAMEZAWA Hiroyuki * copy data from a buffer to the given addr. If specified range of 2854d0107eb0SKAMEZAWA Hiroyuki * [addr...addr+count) includes some valid address, data is copied from 2855d0107eb0SKAMEZAWA Hiroyuki * proper area of @buf. If there are memory holes, no copy to hole. 2856d0107eb0SKAMEZAWA Hiroyuki * IOREMAP area is treated as memory hole and no copy is done. 2857d0107eb0SKAMEZAWA Hiroyuki * 2858d0107eb0SKAMEZAWA Hiroyuki * If [addr...addr+count) doesn't includes any intersects with alive 2859a8e5202dSCong Wang * vm_struct area, returns 0. @buf should be kernel's buffer. 2860d0107eb0SKAMEZAWA Hiroyuki * 2861d0107eb0SKAMEZAWA Hiroyuki * Note: In usual ops, vwrite() is never necessary because the caller 2862d0107eb0SKAMEZAWA Hiroyuki * should know vmalloc() area is valid and can use memcpy(). 2863d0107eb0SKAMEZAWA Hiroyuki * This is for routines which have to access vmalloc area without 2864d0107eb0SKAMEZAWA Hiroyuki * any informaion, as /dev/kmem. 2865a862f68aSMike Rapoport * 2866a862f68aSMike Rapoport * Return: number of bytes for which addr and buf should be 2867a862f68aSMike Rapoport * increased (same number as @count) or %0 if [addr...addr+count) 2868a862f68aSMike Rapoport * doesn't include any intersection with valid vmalloc area 2869d0107eb0SKAMEZAWA Hiroyuki */ 28701da177e4SLinus Torvalds long vwrite(char *buf, char *addr, unsigned long count) 28711da177e4SLinus Torvalds { 2872e81ce85fSJoonsoo Kim struct vmap_area *va; 2873e81ce85fSJoonsoo Kim struct vm_struct *vm; 2874d0107eb0SKAMEZAWA Hiroyuki char *vaddr; 2875d0107eb0SKAMEZAWA Hiroyuki unsigned long n, buflen; 2876d0107eb0SKAMEZAWA Hiroyuki int copied = 0; 28771da177e4SLinus Torvalds 28781da177e4SLinus Torvalds /* Don't allow overflow */ 28791da177e4SLinus Torvalds if ((unsigned long) addr + count < count) 28801da177e4SLinus Torvalds count = -(unsigned long) addr; 2881d0107eb0SKAMEZAWA Hiroyuki buflen = count; 28821da177e4SLinus Torvalds 2883e81ce85fSJoonsoo Kim spin_lock(&vmap_area_lock); 2884e81ce85fSJoonsoo Kim list_for_each_entry(va, &vmap_area_list, list) { 2885e81ce85fSJoonsoo Kim if (!count) 2886e81ce85fSJoonsoo Kim break; 2887e81ce85fSJoonsoo Kim 2888e81ce85fSJoonsoo Kim if (!(va->flags & VM_VM_AREA)) 2889e81ce85fSJoonsoo Kim continue; 2890e81ce85fSJoonsoo Kim 2891e81ce85fSJoonsoo Kim vm = va->vm; 2892e81ce85fSJoonsoo Kim vaddr = (char *) vm->addr; 2893762216abSWanpeng Li if (addr >= vaddr + get_vm_area_size(vm)) 28941da177e4SLinus Torvalds continue; 28951da177e4SLinus Torvalds while (addr < vaddr) { 28961da177e4SLinus Torvalds if (count == 0) 28971da177e4SLinus Torvalds goto finished; 28981da177e4SLinus Torvalds buf++; 28991da177e4SLinus Torvalds addr++; 29001da177e4SLinus Torvalds count--; 29011da177e4SLinus Torvalds } 2902762216abSWanpeng Li n = vaddr + get_vm_area_size(vm) - addr; 2903d0107eb0SKAMEZAWA Hiroyuki if (n > count) 2904d0107eb0SKAMEZAWA Hiroyuki n = count; 2905e81ce85fSJoonsoo Kim if (!(vm->flags & VM_IOREMAP)) { 2906d0107eb0SKAMEZAWA Hiroyuki aligned_vwrite(buf, addr, n); 2907d0107eb0SKAMEZAWA Hiroyuki copied++; 2908d0107eb0SKAMEZAWA Hiroyuki } 2909d0107eb0SKAMEZAWA Hiroyuki buf += n; 2910d0107eb0SKAMEZAWA Hiroyuki addr += n; 2911d0107eb0SKAMEZAWA Hiroyuki count -= n; 29121da177e4SLinus Torvalds } 29131da177e4SLinus Torvalds finished: 2914e81ce85fSJoonsoo Kim spin_unlock(&vmap_area_lock); 2915d0107eb0SKAMEZAWA Hiroyuki if (!copied) 2916d0107eb0SKAMEZAWA Hiroyuki return 0; 2917d0107eb0SKAMEZAWA Hiroyuki return buflen; 29181da177e4SLinus Torvalds } 291983342314SNick Piggin 292083342314SNick Piggin /** 2921e69e9d4aSHATAYAMA Daisuke * remap_vmalloc_range_partial - map vmalloc pages to userspace 2922e69e9d4aSHATAYAMA Daisuke * @vma: vma to cover 2923e69e9d4aSHATAYAMA Daisuke * @uaddr: target user address to start at 2924e69e9d4aSHATAYAMA Daisuke * @kaddr: virtual address of vmalloc kernel memory 2925e69e9d4aSHATAYAMA Daisuke * @size: size of map area 2926e69e9d4aSHATAYAMA Daisuke * 2927e69e9d4aSHATAYAMA Daisuke * Returns: 0 for success, -Exxx on failure 2928e69e9d4aSHATAYAMA Daisuke * 2929e69e9d4aSHATAYAMA Daisuke * This function checks that @kaddr is a valid vmalloc'ed area, 2930e69e9d4aSHATAYAMA Daisuke * and that it is big enough to cover the range starting at 2931e69e9d4aSHATAYAMA Daisuke * @uaddr in @vma. Will return failure if that criteria isn't 2932e69e9d4aSHATAYAMA Daisuke * met. 2933e69e9d4aSHATAYAMA Daisuke * 2934e69e9d4aSHATAYAMA Daisuke * Similar to remap_pfn_range() (see mm/memory.c) 2935e69e9d4aSHATAYAMA Daisuke */ 2936e69e9d4aSHATAYAMA Daisuke int remap_vmalloc_range_partial(struct vm_area_struct *vma, unsigned long uaddr, 2937e69e9d4aSHATAYAMA Daisuke void *kaddr, unsigned long size) 2938e69e9d4aSHATAYAMA Daisuke { 2939e69e9d4aSHATAYAMA Daisuke struct vm_struct *area; 2940e69e9d4aSHATAYAMA Daisuke 2941e69e9d4aSHATAYAMA Daisuke size = PAGE_ALIGN(size); 2942e69e9d4aSHATAYAMA Daisuke 2943e69e9d4aSHATAYAMA Daisuke if (!PAGE_ALIGNED(uaddr) || !PAGE_ALIGNED(kaddr)) 2944e69e9d4aSHATAYAMA Daisuke return -EINVAL; 2945e69e9d4aSHATAYAMA Daisuke 2946e69e9d4aSHATAYAMA Daisuke area = find_vm_area(kaddr); 2947e69e9d4aSHATAYAMA Daisuke if (!area) 2948e69e9d4aSHATAYAMA Daisuke return -EINVAL; 2949e69e9d4aSHATAYAMA Daisuke 2950e69e9d4aSHATAYAMA Daisuke if (!(area->flags & VM_USERMAP)) 2951e69e9d4aSHATAYAMA Daisuke return -EINVAL; 2952e69e9d4aSHATAYAMA Daisuke 2953401592d2SRoman Penyaev if (kaddr + size > area->addr + get_vm_area_size(area)) 2954e69e9d4aSHATAYAMA Daisuke return -EINVAL; 2955e69e9d4aSHATAYAMA Daisuke 2956e69e9d4aSHATAYAMA Daisuke do { 2957e69e9d4aSHATAYAMA Daisuke struct page *page = vmalloc_to_page(kaddr); 2958e69e9d4aSHATAYAMA Daisuke int ret; 2959e69e9d4aSHATAYAMA Daisuke 2960e69e9d4aSHATAYAMA Daisuke ret = vm_insert_page(vma, uaddr, page); 2961e69e9d4aSHATAYAMA Daisuke if (ret) 2962e69e9d4aSHATAYAMA Daisuke return ret; 2963e69e9d4aSHATAYAMA Daisuke 2964e69e9d4aSHATAYAMA Daisuke uaddr += PAGE_SIZE; 2965e69e9d4aSHATAYAMA Daisuke kaddr += PAGE_SIZE; 2966e69e9d4aSHATAYAMA Daisuke size -= PAGE_SIZE; 2967e69e9d4aSHATAYAMA Daisuke } while (size > 0); 2968e69e9d4aSHATAYAMA Daisuke 2969e69e9d4aSHATAYAMA Daisuke vma->vm_flags |= VM_DONTEXPAND | VM_DONTDUMP; 2970e69e9d4aSHATAYAMA Daisuke 2971e69e9d4aSHATAYAMA Daisuke return 0; 2972e69e9d4aSHATAYAMA Daisuke } 2973e69e9d4aSHATAYAMA Daisuke EXPORT_SYMBOL(remap_vmalloc_range_partial); 2974e69e9d4aSHATAYAMA Daisuke 2975e69e9d4aSHATAYAMA Daisuke /** 297683342314SNick Piggin * remap_vmalloc_range - map vmalloc pages to userspace 297783342314SNick Piggin * @vma: vma to cover (map full range of vma) 297883342314SNick Piggin * @addr: vmalloc memory 297983342314SNick Piggin * @pgoff: number of pages into addr before first page to map 29807682486bSRandy Dunlap * 29817682486bSRandy Dunlap * Returns: 0 for success, -Exxx on failure 298283342314SNick Piggin * 298383342314SNick Piggin * This function checks that addr is a valid vmalloc'ed area, and 298483342314SNick Piggin * that it is big enough to cover the vma. Will return failure if 298583342314SNick Piggin * that criteria isn't met. 298683342314SNick Piggin * 298772fd4a35SRobert P. J. Day * Similar to remap_pfn_range() (see mm/memory.c) 298883342314SNick Piggin */ 298983342314SNick Piggin int remap_vmalloc_range(struct vm_area_struct *vma, void *addr, 299083342314SNick Piggin unsigned long pgoff) 299183342314SNick Piggin { 2992e69e9d4aSHATAYAMA Daisuke return remap_vmalloc_range_partial(vma, vma->vm_start, 2993e69e9d4aSHATAYAMA Daisuke addr + (pgoff << PAGE_SHIFT), 2994e69e9d4aSHATAYAMA Daisuke vma->vm_end - vma->vm_start); 299583342314SNick Piggin } 299683342314SNick Piggin EXPORT_SYMBOL(remap_vmalloc_range); 299783342314SNick Piggin 29981eeb66a1SChristoph Hellwig /* 29991eeb66a1SChristoph Hellwig * Implement a stub for vmalloc_sync_all() if the architecture chose not to 30001eeb66a1SChristoph Hellwig * have one. 30011eeb66a1SChristoph Hellwig */ 30023b32123dSGideon Israel Dsouza void __weak vmalloc_sync_all(void) 30031eeb66a1SChristoph Hellwig { 30041eeb66a1SChristoph Hellwig } 30055f4352fbSJeremy Fitzhardinge 30065f4352fbSJeremy Fitzhardinge 30072f569afdSMartin Schwidefsky static int f(pte_t *pte, pgtable_t table, unsigned long addr, void *data) 30085f4352fbSJeremy Fitzhardinge { 3009cd12909cSDavid Vrabel pte_t ***p = data; 3010cd12909cSDavid Vrabel 3011cd12909cSDavid Vrabel if (p) { 3012cd12909cSDavid Vrabel *(*p) = pte; 3013cd12909cSDavid Vrabel (*p)++; 3014cd12909cSDavid Vrabel } 30155f4352fbSJeremy Fitzhardinge return 0; 30165f4352fbSJeremy Fitzhardinge } 30175f4352fbSJeremy Fitzhardinge 30185f4352fbSJeremy Fitzhardinge /** 30195f4352fbSJeremy Fitzhardinge * alloc_vm_area - allocate a range of kernel address space 30205f4352fbSJeremy Fitzhardinge * @size: size of the area 3021cd12909cSDavid Vrabel * @ptes: returns the PTEs for the address space 30227682486bSRandy Dunlap * 30237682486bSRandy Dunlap * Returns: NULL on failure, vm_struct on success 30245f4352fbSJeremy Fitzhardinge * 30255f4352fbSJeremy Fitzhardinge * This function reserves a range of kernel address space, and 30265f4352fbSJeremy Fitzhardinge * allocates pagetables to map that range. No actual mappings 3027cd12909cSDavid Vrabel * are created. 3028cd12909cSDavid Vrabel * 3029cd12909cSDavid Vrabel * If @ptes is non-NULL, pointers to the PTEs (in init_mm) 3030cd12909cSDavid Vrabel * allocated for the VM area are returned. 30315f4352fbSJeremy Fitzhardinge */ 3032cd12909cSDavid Vrabel struct vm_struct *alloc_vm_area(size_t size, pte_t **ptes) 30335f4352fbSJeremy Fitzhardinge { 30345f4352fbSJeremy Fitzhardinge struct vm_struct *area; 30355f4352fbSJeremy Fitzhardinge 303623016969SChristoph Lameter area = get_vm_area_caller(size, VM_IOREMAP, 303723016969SChristoph Lameter __builtin_return_address(0)); 30385f4352fbSJeremy Fitzhardinge if (area == NULL) 30395f4352fbSJeremy Fitzhardinge return NULL; 30405f4352fbSJeremy Fitzhardinge 30415f4352fbSJeremy Fitzhardinge /* 30425f4352fbSJeremy Fitzhardinge * This ensures that page tables are constructed for this region 30435f4352fbSJeremy Fitzhardinge * of kernel virtual address space and mapped into init_mm. 30445f4352fbSJeremy Fitzhardinge */ 30455f4352fbSJeremy Fitzhardinge if (apply_to_page_range(&init_mm, (unsigned long)area->addr, 3046cd12909cSDavid Vrabel size, f, ptes ? &ptes : NULL)) { 30475f4352fbSJeremy Fitzhardinge free_vm_area(area); 30485f4352fbSJeremy Fitzhardinge return NULL; 30495f4352fbSJeremy Fitzhardinge } 30505f4352fbSJeremy Fitzhardinge 30515f4352fbSJeremy Fitzhardinge return area; 30525f4352fbSJeremy Fitzhardinge } 30535f4352fbSJeremy Fitzhardinge EXPORT_SYMBOL_GPL(alloc_vm_area); 30545f4352fbSJeremy Fitzhardinge 30555f4352fbSJeremy Fitzhardinge void free_vm_area(struct vm_struct *area) 30565f4352fbSJeremy Fitzhardinge { 30575f4352fbSJeremy Fitzhardinge struct vm_struct *ret; 30585f4352fbSJeremy Fitzhardinge ret = remove_vm_area(area->addr); 30595f4352fbSJeremy Fitzhardinge BUG_ON(ret != area); 30605f4352fbSJeremy Fitzhardinge kfree(area); 30615f4352fbSJeremy Fitzhardinge } 30625f4352fbSJeremy Fitzhardinge EXPORT_SYMBOL_GPL(free_vm_area); 3063a10aa579SChristoph Lameter 30644f8b02b4STejun Heo #ifdef CONFIG_SMP 3065ca23e405STejun Heo static struct vmap_area *node_to_va(struct rb_node *n) 3066ca23e405STejun Heo { 30674583e773SGeliang Tang return rb_entry_safe(n, struct vmap_area, rb_node); 3068ca23e405STejun Heo } 3069ca23e405STejun Heo 3070ca23e405STejun Heo /** 307168ad4a33SUladzislau Rezki (Sony) * pvm_find_va_enclose_addr - find the vmap_area @addr belongs to 307268ad4a33SUladzislau Rezki (Sony) * @addr: target address 3073ca23e405STejun Heo * 307468ad4a33SUladzislau Rezki (Sony) * Returns: vmap_area if it is found. If there is no such area 307568ad4a33SUladzislau Rezki (Sony) * the first highest(reverse order) vmap_area is returned 307668ad4a33SUladzislau Rezki (Sony) * i.e. va->va_start < addr && va->va_end < addr or NULL 307768ad4a33SUladzislau Rezki (Sony) * if there are no any areas before @addr. 3078ca23e405STejun Heo */ 307968ad4a33SUladzislau Rezki (Sony) static struct vmap_area * 308068ad4a33SUladzislau Rezki (Sony) pvm_find_va_enclose_addr(unsigned long addr) 3081ca23e405STejun Heo { 308268ad4a33SUladzislau Rezki (Sony) struct vmap_area *va, *tmp; 308368ad4a33SUladzislau Rezki (Sony) struct rb_node *n; 308468ad4a33SUladzislau Rezki (Sony) 308568ad4a33SUladzislau Rezki (Sony) n = free_vmap_area_root.rb_node; 308668ad4a33SUladzislau Rezki (Sony) va = NULL; 3087ca23e405STejun Heo 3088ca23e405STejun Heo while (n) { 308968ad4a33SUladzislau Rezki (Sony) tmp = rb_entry(n, struct vmap_area, rb_node); 309068ad4a33SUladzislau Rezki (Sony) if (tmp->va_start <= addr) { 309168ad4a33SUladzislau Rezki (Sony) va = tmp; 309268ad4a33SUladzislau Rezki (Sony) if (tmp->va_end >= addr) 3093ca23e405STejun Heo break; 3094ca23e405STejun Heo 309568ad4a33SUladzislau Rezki (Sony) n = n->rb_right; 3096ca23e405STejun Heo } else { 309768ad4a33SUladzislau Rezki (Sony) n = n->rb_left; 3098ca23e405STejun Heo } 309968ad4a33SUladzislau Rezki (Sony) } 310068ad4a33SUladzislau Rezki (Sony) 310168ad4a33SUladzislau Rezki (Sony) return va; 3102ca23e405STejun Heo } 3103ca23e405STejun Heo 3104ca23e405STejun Heo /** 310568ad4a33SUladzislau Rezki (Sony) * pvm_determine_end_from_reverse - find the highest aligned address 310668ad4a33SUladzislau Rezki (Sony) * of free block below VMALLOC_END 310768ad4a33SUladzislau Rezki (Sony) * @va: 310868ad4a33SUladzislau Rezki (Sony) * in - the VA we start the search(reverse order); 310968ad4a33SUladzislau Rezki (Sony) * out - the VA with the highest aligned end address. 3110ca23e405STejun Heo * 311168ad4a33SUladzislau Rezki (Sony) * Returns: determined end address within vmap_area 3112ca23e405STejun Heo */ 311368ad4a33SUladzislau Rezki (Sony) static unsigned long 311468ad4a33SUladzislau Rezki (Sony) pvm_determine_end_from_reverse(struct vmap_area **va, unsigned long align) 3115ca23e405STejun Heo { 311668ad4a33SUladzislau Rezki (Sony) unsigned long vmalloc_end = VMALLOC_END & ~(align - 1); 3117ca23e405STejun Heo unsigned long addr; 3118ca23e405STejun Heo 311968ad4a33SUladzislau Rezki (Sony) if (likely(*va)) { 312068ad4a33SUladzislau Rezki (Sony) list_for_each_entry_from_reverse((*va), 312168ad4a33SUladzislau Rezki (Sony) &free_vmap_area_list, list) { 312268ad4a33SUladzislau Rezki (Sony) addr = min((*va)->va_end & ~(align - 1), vmalloc_end); 312368ad4a33SUladzislau Rezki (Sony) if ((*va)->va_start < addr) 312468ad4a33SUladzislau Rezki (Sony) return addr; 312568ad4a33SUladzislau Rezki (Sony) } 3126ca23e405STejun Heo } 3127ca23e405STejun Heo 312868ad4a33SUladzislau Rezki (Sony) return 0; 3129ca23e405STejun Heo } 3130ca23e405STejun Heo 3131ca23e405STejun Heo /** 3132ca23e405STejun Heo * pcpu_get_vm_areas - allocate vmalloc areas for percpu allocator 3133ca23e405STejun Heo * @offsets: array containing offset of each area 3134ca23e405STejun Heo * @sizes: array containing size of each area 3135ca23e405STejun Heo * @nr_vms: the number of areas to allocate 3136ca23e405STejun Heo * @align: alignment, all entries in @offsets and @sizes must be aligned to this 3137ca23e405STejun Heo * 3138ca23e405STejun Heo * Returns: kmalloc'd vm_struct pointer array pointing to allocated 3139ca23e405STejun Heo * vm_structs on success, %NULL on failure 3140ca23e405STejun Heo * 3141ca23e405STejun Heo * Percpu allocator wants to use congruent vm areas so that it can 3142ca23e405STejun Heo * maintain the offsets among percpu areas. This function allocates 3143ec3f64fcSDavid Rientjes * congruent vmalloc areas for it with GFP_KERNEL. These areas tend to 3144ec3f64fcSDavid Rientjes * be scattered pretty far, distance between two areas easily going up 3145ec3f64fcSDavid Rientjes * to gigabytes. To avoid interacting with regular vmallocs, these 3146ec3f64fcSDavid Rientjes * areas are allocated from top. 3147ca23e405STejun Heo * 3148ca23e405STejun Heo * Despite its complicated look, this allocator is rather simple. It 314968ad4a33SUladzislau Rezki (Sony) * does everything top-down and scans free blocks from the end looking 315068ad4a33SUladzislau Rezki (Sony) * for matching base. While scanning, if any of the areas do not fit the 315168ad4a33SUladzislau Rezki (Sony) * base address is pulled down to fit the area. Scanning is repeated till 315268ad4a33SUladzislau Rezki (Sony) * all the areas fit and then all necessary data structures are inserted 315368ad4a33SUladzislau Rezki (Sony) * and the result is returned. 3154ca23e405STejun Heo */ 3155ca23e405STejun Heo struct vm_struct **pcpu_get_vm_areas(const unsigned long *offsets, 3156ca23e405STejun Heo const size_t *sizes, int nr_vms, 3157ec3f64fcSDavid Rientjes size_t align) 3158ca23e405STejun Heo { 3159ca23e405STejun Heo const unsigned long vmalloc_start = ALIGN(VMALLOC_START, align); 3160ca23e405STejun Heo const unsigned long vmalloc_end = VMALLOC_END & ~(align - 1); 316168ad4a33SUladzislau Rezki (Sony) struct vmap_area **vas, *va; 3162ca23e405STejun Heo struct vm_struct **vms; 3163ca23e405STejun Heo int area, area2, last_area, term_area; 316468ad4a33SUladzislau Rezki (Sony) unsigned long base, start, size, end, last_end; 3165ca23e405STejun Heo bool purged = false; 316668ad4a33SUladzislau Rezki (Sony) enum fit_type type; 3167ca23e405STejun Heo 3168ca23e405STejun Heo /* verify parameters and allocate data structures */ 3169891c49abSAlexander Kuleshov BUG_ON(offset_in_page(align) || !is_power_of_2(align)); 3170ca23e405STejun Heo for (last_area = 0, area = 0; area < nr_vms; area++) { 3171ca23e405STejun Heo start = offsets[area]; 3172ca23e405STejun Heo end = start + sizes[area]; 3173ca23e405STejun Heo 3174ca23e405STejun Heo /* is everything aligned properly? */ 3175ca23e405STejun Heo BUG_ON(!IS_ALIGNED(offsets[area], align)); 3176ca23e405STejun Heo BUG_ON(!IS_ALIGNED(sizes[area], align)); 3177ca23e405STejun Heo 3178ca23e405STejun Heo /* detect the area with the highest address */ 3179ca23e405STejun Heo if (start > offsets[last_area]) 3180ca23e405STejun Heo last_area = area; 3181ca23e405STejun Heo 3182c568da28SWei Yang for (area2 = area + 1; area2 < nr_vms; area2++) { 3183ca23e405STejun Heo unsigned long start2 = offsets[area2]; 3184ca23e405STejun Heo unsigned long end2 = start2 + sizes[area2]; 3185ca23e405STejun Heo 3186c568da28SWei Yang BUG_ON(start2 < end && start < end2); 3187ca23e405STejun Heo } 3188ca23e405STejun Heo } 3189ca23e405STejun Heo last_end = offsets[last_area] + sizes[last_area]; 3190ca23e405STejun Heo 3191ca23e405STejun Heo if (vmalloc_end - vmalloc_start < last_end) { 3192ca23e405STejun Heo WARN_ON(true); 3193ca23e405STejun Heo return NULL; 3194ca23e405STejun Heo } 3195ca23e405STejun Heo 31964d67d860SThomas Meyer vms = kcalloc(nr_vms, sizeof(vms[0]), GFP_KERNEL); 31974d67d860SThomas Meyer vas = kcalloc(nr_vms, sizeof(vas[0]), GFP_KERNEL); 3198ca23e405STejun Heo if (!vas || !vms) 3199f1db7afdSKautuk Consul goto err_free2; 3200ca23e405STejun Heo 3201ca23e405STejun Heo for (area = 0; area < nr_vms; area++) { 320268ad4a33SUladzislau Rezki (Sony) vas[area] = kmem_cache_zalloc(vmap_area_cachep, GFP_KERNEL); 3203ec3f64fcSDavid Rientjes vms[area] = kzalloc(sizeof(struct vm_struct), GFP_KERNEL); 3204ca23e405STejun Heo if (!vas[area] || !vms[area]) 3205ca23e405STejun Heo goto err_free; 3206ca23e405STejun Heo } 3207ca23e405STejun Heo retry: 3208ca23e405STejun Heo spin_lock(&vmap_area_lock); 3209ca23e405STejun Heo 3210ca23e405STejun Heo /* start scanning - we scan from the top, begin with the last area */ 3211ca23e405STejun Heo area = term_area = last_area; 3212ca23e405STejun Heo start = offsets[area]; 3213ca23e405STejun Heo end = start + sizes[area]; 3214ca23e405STejun Heo 321568ad4a33SUladzislau Rezki (Sony) va = pvm_find_va_enclose_addr(vmalloc_end); 321668ad4a33SUladzislau Rezki (Sony) base = pvm_determine_end_from_reverse(&va, align) - end; 3217ca23e405STejun Heo 3218ca23e405STejun Heo while (true) { 3219ca23e405STejun Heo /* 3220ca23e405STejun Heo * base might have underflowed, add last_end before 3221ca23e405STejun Heo * comparing. 3222ca23e405STejun Heo */ 322368ad4a33SUladzislau Rezki (Sony) if (base + last_end < vmalloc_start + last_end) 322468ad4a33SUladzislau Rezki (Sony) goto overflow; 3225ca23e405STejun Heo 3226ca23e405STejun Heo /* 322768ad4a33SUladzislau Rezki (Sony) * Fitting base has not been found. 3228ca23e405STejun Heo */ 322968ad4a33SUladzislau Rezki (Sony) if (va == NULL) 323068ad4a33SUladzislau Rezki (Sony) goto overflow; 3231ca23e405STejun Heo 3232ca23e405STejun Heo /* 323368ad4a33SUladzislau Rezki (Sony) * If this VA does not fit, move base downwards and recheck. 3234ca23e405STejun Heo */ 323568ad4a33SUladzislau Rezki (Sony) if (base + start < va->va_start || base + end > va->va_end) { 323668ad4a33SUladzislau Rezki (Sony) va = node_to_va(rb_prev(&va->rb_node)); 323768ad4a33SUladzislau Rezki (Sony) base = pvm_determine_end_from_reverse(&va, align) - end; 3238ca23e405STejun Heo term_area = area; 3239ca23e405STejun Heo continue; 3240ca23e405STejun Heo } 3241ca23e405STejun Heo 3242ca23e405STejun Heo /* 3243ca23e405STejun Heo * This area fits, move on to the previous one. If 3244ca23e405STejun Heo * the previous one is the terminal one, we're done. 3245ca23e405STejun Heo */ 3246ca23e405STejun Heo area = (area + nr_vms - 1) % nr_vms; 3247ca23e405STejun Heo if (area == term_area) 3248ca23e405STejun Heo break; 324968ad4a33SUladzislau Rezki (Sony) 3250ca23e405STejun Heo start = offsets[area]; 3251ca23e405STejun Heo end = start + sizes[area]; 325268ad4a33SUladzislau Rezki (Sony) va = pvm_find_va_enclose_addr(base + end); 3253ca23e405STejun Heo } 325468ad4a33SUladzislau Rezki (Sony) 3255ca23e405STejun Heo /* we've found a fitting base, insert all va's */ 3256ca23e405STejun Heo for (area = 0; area < nr_vms; area++) { 325768ad4a33SUladzislau Rezki (Sony) int ret; 3258ca23e405STejun Heo 325968ad4a33SUladzislau Rezki (Sony) start = base + offsets[area]; 326068ad4a33SUladzislau Rezki (Sony) size = sizes[area]; 326168ad4a33SUladzislau Rezki (Sony) 326268ad4a33SUladzislau Rezki (Sony) va = pvm_find_va_enclose_addr(start); 326368ad4a33SUladzislau Rezki (Sony) if (WARN_ON_ONCE(va == NULL)) 326468ad4a33SUladzislau Rezki (Sony) /* It is a BUG(), but trigger recovery instead. */ 326568ad4a33SUladzislau Rezki (Sony) goto recovery; 326668ad4a33SUladzislau Rezki (Sony) 326768ad4a33SUladzislau Rezki (Sony) type = classify_va_fit_type(va, start, size); 326868ad4a33SUladzislau Rezki (Sony) if (WARN_ON_ONCE(type == NOTHING_FIT)) 326968ad4a33SUladzislau Rezki (Sony) /* It is a BUG(), but trigger recovery instead. */ 327068ad4a33SUladzislau Rezki (Sony) goto recovery; 327168ad4a33SUladzislau Rezki (Sony) 327268ad4a33SUladzislau Rezki (Sony) ret = adjust_va_to_fit_type(va, start, size, type); 327368ad4a33SUladzislau Rezki (Sony) if (unlikely(ret)) 327468ad4a33SUladzislau Rezki (Sony) goto recovery; 327568ad4a33SUladzislau Rezki (Sony) 327668ad4a33SUladzislau Rezki (Sony) /* Allocated area. */ 327768ad4a33SUladzislau Rezki (Sony) va = vas[area]; 327868ad4a33SUladzislau Rezki (Sony) va->va_start = start; 327968ad4a33SUladzislau Rezki (Sony) va->va_end = start + size; 328068ad4a33SUladzislau Rezki (Sony) 328168ad4a33SUladzislau Rezki (Sony) insert_vmap_area(va, &vmap_area_root, &vmap_area_list); 3282ca23e405STejun Heo } 3283ca23e405STejun Heo 3284ca23e405STejun Heo spin_unlock(&vmap_area_lock); 3285ca23e405STejun Heo 3286ca23e405STejun Heo /* insert all vm's */ 3287ca23e405STejun Heo for (area = 0; area < nr_vms; area++) 32883645cb4aSZhang Yanfei setup_vmalloc_vm(vms[area], vas[area], VM_ALLOC, 3289ca23e405STejun Heo pcpu_get_vm_areas); 3290ca23e405STejun Heo 3291ca23e405STejun Heo kfree(vas); 3292ca23e405STejun Heo return vms; 3293ca23e405STejun Heo 329468ad4a33SUladzislau Rezki (Sony) recovery: 329568ad4a33SUladzislau Rezki (Sony) /* Remove previously inserted areas. */ 329668ad4a33SUladzislau Rezki (Sony) while (area--) { 329768ad4a33SUladzislau Rezki (Sony) __free_vmap_area(vas[area]); 329868ad4a33SUladzislau Rezki (Sony) vas[area] = NULL; 329968ad4a33SUladzislau Rezki (Sony) } 330068ad4a33SUladzislau Rezki (Sony) 330168ad4a33SUladzislau Rezki (Sony) overflow: 330268ad4a33SUladzislau Rezki (Sony) spin_unlock(&vmap_area_lock); 330368ad4a33SUladzislau Rezki (Sony) if (!purged) { 330468ad4a33SUladzislau Rezki (Sony) purge_vmap_area_lazy(); 330568ad4a33SUladzislau Rezki (Sony) purged = true; 330668ad4a33SUladzislau Rezki (Sony) 330768ad4a33SUladzislau Rezki (Sony) /* Before "retry", check if we recover. */ 330868ad4a33SUladzislau Rezki (Sony) for (area = 0; area < nr_vms; area++) { 330968ad4a33SUladzislau Rezki (Sony) if (vas[area]) 331068ad4a33SUladzislau Rezki (Sony) continue; 331168ad4a33SUladzislau Rezki (Sony) 331268ad4a33SUladzislau Rezki (Sony) vas[area] = kmem_cache_zalloc( 331368ad4a33SUladzislau Rezki (Sony) vmap_area_cachep, GFP_KERNEL); 331468ad4a33SUladzislau Rezki (Sony) if (!vas[area]) 331568ad4a33SUladzislau Rezki (Sony) goto err_free; 331668ad4a33SUladzislau Rezki (Sony) } 331768ad4a33SUladzislau Rezki (Sony) 331868ad4a33SUladzislau Rezki (Sony) goto retry; 331968ad4a33SUladzislau Rezki (Sony) } 332068ad4a33SUladzislau Rezki (Sony) 3321ca23e405STejun Heo err_free: 3322ca23e405STejun Heo for (area = 0; area < nr_vms; area++) { 332368ad4a33SUladzislau Rezki (Sony) if (vas[area]) 332468ad4a33SUladzislau Rezki (Sony) kmem_cache_free(vmap_area_cachep, vas[area]); 332568ad4a33SUladzislau Rezki (Sony) 3326ca23e405STejun Heo kfree(vms[area]); 3327ca23e405STejun Heo } 3328f1db7afdSKautuk Consul err_free2: 3329ca23e405STejun Heo kfree(vas); 3330ca23e405STejun Heo kfree(vms); 3331ca23e405STejun Heo return NULL; 3332ca23e405STejun Heo } 3333ca23e405STejun Heo 3334ca23e405STejun Heo /** 3335ca23e405STejun Heo * pcpu_free_vm_areas - free vmalloc areas for percpu allocator 3336ca23e405STejun Heo * @vms: vm_struct pointer array returned by pcpu_get_vm_areas() 3337ca23e405STejun Heo * @nr_vms: the number of allocated areas 3338ca23e405STejun Heo * 3339ca23e405STejun Heo * Free vm_structs and the array allocated by pcpu_get_vm_areas(). 3340ca23e405STejun Heo */ 3341ca23e405STejun Heo void pcpu_free_vm_areas(struct vm_struct **vms, int nr_vms) 3342ca23e405STejun Heo { 3343ca23e405STejun Heo int i; 3344ca23e405STejun Heo 3345ca23e405STejun Heo for (i = 0; i < nr_vms; i++) 3346ca23e405STejun Heo free_vm_area(vms[i]); 3347ca23e405STejun Heo kfree(vms); 3348ca23e405STejun Heo } 33494f8b02b4STejun Heo #endif /* CONFIG_SMP */ 3350a10aa579SChristoph Lameter 3351a10aa579SChristoph Lameter #ifdef CONFIG_PROC_FS 3352a10aa579SChristoph Lameter static void *s_start(struct seq_file *m, loff_t *pos) 3353d4033afdSJoonsoo Kim __acquires(&vmap_area_lock) 3354a10aa579SChristoph Lameter { 3355d4033afdSJoonsoo Kim spin_lock(&vmap_area_lock); 33563f500069Szijun_hu return seq_list_start(&vmap_area_list, *pos); 3357a10aa579SChristoph Lameter } 3358a10aa579SChristoph Lameter 3359a10aa579SChristoph Lameter static void *s_next(struct seq_file *m, void *p, loff_t *pos) 3360a10aa579SChristoph Lameter { 33613f500069Szijun_hu return seq_list_next(p, &vmap_area_list, pos); 3362a10aa579SChristoph Lameter } 3363a10aa579SChristoph Lameter 3364a10aa579SChristoph Lameter static void s_stop(struct seq_file *m, void *p) 3365d4033afdSJoonsoo Kim __releases(&vmap_area_lock) 3366a10aa579SChristoph Lameter { 3367d4033afdSJoonsoo Kim spin_unlock(&vmap_area_lock); 3368a10aa579SChristoph Lameter } 3369a10aa579SChristoph Lameter 3370a47a126aSEric Dumazet static void show_numa_info(struct seq_file *m, struct vm_struct *v) 3371a47a126aSEric Dumazet { 3372e5adfffcSKirill A. Shutemov if (IS_ENABLED(CONFIG_NUMA)) { 3373a47a126aSEric Dumazet unsigned int nr, *counters = m->private; 3374a47a126aSEric Dumazet 3375a47a126aSEric Dumazet if (!counters) 3376a47a126aSEric Dumazet return; 3377a47a126aSEric Dumazet 3378af12346cSWanpeng Li if (v->flags & VM_UNINITIALIZED) 3379af12346cSWanpeng Li return; 33807e5b528bSDmitry Vyukov /* Pair with smp_wmb() in clear_vm_uninitialized_flag() */ 33817e5b528bSDmitry Vyukov smp_rmb(); 3382af12346cSWanpeng Li 3383a47a126aSEric Dumazet memset(counters, 0, nr_node_ids * sizeof(unsigned int)); 3384a47a126aSEric Dumazet 3385a47a126aSEric Dumazet for (nr = 0; nr < v->nr_pages; nr++) 3386a47a126aSEric Dumazet counters[page_to_nid(v->pages[nr])]++; 3387a47a126aSEric Dumazet 3388a47a126aSEric Dumazet for_each_node_state(nr, N_HIGH_MEMORY) 3389a47a126aSEric Dumazet if (counters[nr]) 3390a47a126aSEric Dumazet seq_printf(m, " N%u=%u", nr, counters[nr]); 3391a47a126aSEric Dumazet } 3392a47a126aSEric Dumazet } 3393a47a126aSEric Dumazet 3394a10aa579SChristoph Lameter static int s_show(struct seq_file *m, void *p) 3395a10aa579SChristoph Lameter { 33963f500069Szijun_hu struct vmap_area *va; 3397d4033afdSJoonsoo Kim struct vm_struct *v; 3398d4033afdSJoonsoo Kim 33993f500069Szijun_hu va = list_entry(p, struct vmap_area, list); 34003f500069Szijun_hu 3401c2ce8c14SWanpeng Li /* 3402c2ce8c14SWanpeng Li * s_show can encounter race with remove_vm_area, !VM_VM_AREA on 3403c2ce8c14SWanpeng Li * behalf of vmap area is being tear down or vm_map_ram allocation. 3404c2ce8c14SWanpeng Li */ 340578c72746SYisheng Xie if (!(va->flags & VM_VM_AREA)) { 340678c72746SYisheng Xie seq_printf(m, "0x%pK-0x%pK %7ld %s\n", 340778c72746SYisheng Xie (void *)va->va_start, (void *)va->va_end, 340878c72746SYisheng Xie va->va_end - va->va_start, 340978c72746SYisheng Xie va->flags & VM_LAZY_FREE ? "unpurged vm_area" : "vm_map_ram"); 341078c72746SYisheng Xie 3411d4033afdSJoonsoo Kim return 0; 341278c72746SYisheng Xie } 3413d4033afdSJoonsoo Kim 3414d4033afdSJoonsoo Kim v = va->vm; 3415a10aa579SChristoph Lameter 341645ec1690SKees Cook seq_printf(m, "0x%pK-0x%pK %7ld", 3417a10aa579SChristoph Lameter v->addr, v->addr + v->size, v->size); 3418a10aa579SChristoph Lameter 341962c70bceSJoe Perches if (v->caller) 342062c70bceSJoe Perches seq_printf(m, " %pS", v->caller); 342123016969SChristoph Lameter 3422a10aa579SChristoph Lameter if (v->nr_pages) 3423a10aa579SChristoph Lameter seq_printf(m, " pages=%d", v->nr_pages); 3424a10aa579SChristoph Lameter 3425a10aa579SChristoph Lameter if (v->phys_addr) 3426199eaa05SMiles Chen seq_printf(m, " phys=%pa", &v->phys_addr); 3427a10aa579SChristoph Lameter 3428a10aa579SChristoph Lameter if (v->flags & VM_IOREMAP) 3429f4527c90SFabian Frederick seq_puts(m, " ioremap"); 3430a10aa579SChristoph Lameter 3431a10aa579SChristoph Lameter if (v->flags & VM_ALLOC) 3432f4527c90SFabian Frederick seq_puts(m, " vmalloc"); 3433a10aa579SChristoph Lameter 3434a10aa579SChristoph Lameter if (v->flags & VM_MAP) 3435f4527c90SFabian Frederick seq_puts(m, " vmap"); 3436a10aa579SChristoph Lameter 3437a10aa579SChristoph Lameter if (v->flags & VM_USERMAP) 3438f4527c90SFabian Frederick seq_puts(m, " user"); 3439a10aa579SChristoph Lameter 3440244d63eeSDavid Rientjes if (is_vmalloc_addr(v->pages)) 3441f4527c90SFabian Frederick seq_puts(m, " vpages"); 3442a10aa579SChristoph Lameter 3443a47a126aSEric Dumazet show_numa_info(m, v); 3444a10aa579SChristoph Lameter seq_putc(m, '\n'); 3445a10aa579SChristoph Lameter return 0; 3446a10aa579SChristoph Lameter } 3447a10aa579SChristoph Lameter 34485f6a6a9cSAlexey Dobriyan static const struct seq_operations vmalloc_op = { 3449a10aa579SChristoph Lameter .start = s_start, 3450a10aa579SChristoph Lameter .next = s_next, 3451a10aa579SChristoph Lameter .stop = s_stop, 3452a10aa579SChristoph Lameter .show = s_show, 3453a10aa579SChristoph Lameter }; 34545f6a6a9cSAlexey Dobriyan 34555f6a6a9cSAlexey Dobriyan static int __init proc_vmalloc_init(void) 34565f6a6a9cSAlexey Dobriyan { 3457fddda2b7SChristoph Hellwig if (IS_ENABLED(CONFIG_NUMA)) 34580825a6f9SJoe Perches proc_create_seq_private("vmallocinfo", 0400, NULL, 345944414d82SChristoph Hellwig &vmalloc_op, 346044414d82SChristoph Hellwig nr_node_ids * sizeof(unsigned int), NULL); 3461fddda2b7SChristoph Hellwig else 34620825a6f9SJoe Perches proc_create_seq("vmallocinfo", 0400, NULL, &vmalloc_op); 34635f6a6a9cSAlexey Dobriyan return 0; 34645f6a6a9cSAlexey Dobriyan } 34655f6a6a9cSAlexey Dobriyan module_init(proc_vmalloc_init); 3466db3808c1SJoonsoo Kim 3467a10aa579SChristoph Lameter #endif 3468