110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall/* 210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * SLOB Allocator: Simple List Of Blocks 310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * 410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * Matt Mackall <mpm@selenic.com> 12/30/03 510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * 66193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * NUMA support by Paul Mundt, 2007. 76193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * 810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * How SLOB works: 910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * 1010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * The core of SLOB is a traditional K&R style heap allocator, with 1110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * support for returning aligned objects. The granularity of this 12553948491c18413928b85a9025b92af80e7d61d6Nick Piggin * allocator is as little as 2 bytes, however typically most architectures 13553948491c18413928b85a9025b92af80e7d61d6Nick Piggin * will require 4 bytes on 32-bit and 8 bytes on 64-bit. 1495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * 1520cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall * The slob heap is a set of linked list of pages from alloc_pages(), 1620cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall * and within each page, there is a singly-linked list of free blocks 1720cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall * (slob_t). The heap is grown on demand. To reduce fragmentation, 1820cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall * heap pages are segregated into three lists, with objects less than 1920cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall * 256 bytes, objects less than 1024 bytes, and all other objects. 2020cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall * 2120cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall * Allocation from heap involves first searching for a page with 2220cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall * sufficient free blocks (using a next-fit-like approach) followed by 2320cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall * a first-fit scan of the page. Deallocation inserts objects back 2420cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall * into the free list in address order, so this is effectively an 2520cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall * address-ordered first fit. 2610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * 2710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * Above this is an implementation of kmalloc/kfree. Blocks returned 28553948491c18413928b85a9025b92af80e7d61d6Nick Piggin * from kmalloc are prepended with a 4-byte header with the kmalloc size. 2910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * If kmalloc is asked for objects of PAGE_SIZE or larger, it calls 306193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * alloc_pages() directly, allocating compound pages so the page order 31999d8795d438d396936811b185428d70b7b7de6dEzequiel Garcia * does not have to be separately tracked. 32999d8795d438d396936811b185428d70b7b7de6dEzequiel Garcia * These objects are detected in kfree() because PageSlab() 33d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin * is false for them. 3410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * 3510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * SLAB is emulated on top of SLOB by simply calling constructors and 3695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * destructors for every SLAB allocation. Objects are returned with the 3795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * 4-byte alignment unless the SLAB_HWCACHE_ALIGN flag is set, in which 3895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * case the low-level allocator will fragment blocks to create the proper 3995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * alignment. Again, objects of page-size or greater are allocated by 406193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * calling alloc_pages(). As SLAB objects know their size, no separate 4195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * size bookkeeping is necessary and there is essentially no allocation 42d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin * space overhead, and compound pages aren't needed for multi-page 43d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin * allocations. 446193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * 456193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * NUMA support in SLOB is fairly simplistic, pushing most of the real 466193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * logic down to the page allocator, and simply doing the node accounting 476193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * on the upper levels. In the event that a node id is explicitly 486484eb3e2a81807722c5f28efef94d8338b7b996Mel Gorman * provided, alloc_pages_exact_node() with the specified node id is used 496193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * instead. The common case (or when the node id isn't explicitly provided) 506193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * will default to the current node, as per numa_node_id(). 516193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * 526193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * Node aware pages are still inserted in to the global freelist, and 536193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * these are scanned for by matching against the node id encoded in the 546193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * page flags. As a result, block allocations that can be satisfied from 556193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * the freelist will only be done so on pages residing on the same node, 566193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * in order to prevent random node placement. 5710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall */ 5810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 5995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin#include <linux/kernel.h> 6010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall#include <linux/slab.h> 6197d06609158e61f6bdf538c4a6788e2de492236fChristoph Lameter 6210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall#include <linux/mm.h> 631f0532eb617d28f65c93593a1491f662f14f7eacNick Piggin#include <linux/swap.h> /* struct reclaim_state */ 6410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall#include <linux/cache.h> 6510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall#include <linux/init.h> 66b95f1b31b75588306e32b2afd32166cad48f670bPaul Gortmaker#include <linux/export.h> 67afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin#include <linux/rcupdate.h> 6895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin#include <linux/list.h> 694374e616d28e65265a5b433ceece275449f3d2e3Catalin Marinas#include <linux/kmemleak.h> 70039ca4e74a1cf60bd7487324a564ecf5c981f254Li Zefan 71039ca4e74a1cf60bd7487324a564ecf5c981f254Li Zefan#include <trace/events/kmem.h> 72039ca4e74a1cf60bd7487324a564ecf5c981f254Li Zefan 7360063497a95e716c9a689af3be2687d261f115b4Arun Sharma#include <linux/atomic.h> 7495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 75b9ce5ef49f00daf2254c6953c8d31f79aabccd34Glauber Costa#include "slab.h" 7695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 7795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * slob_block has a field 'units', which indicates size of block if +ve, 7895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * or offset of next block if -ve (in SLOB_UNITs). 7995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * 8095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * Free blocks of size 1 unit simply contain the offset of the next block. 8195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * Those with larger size contain their size in the first SLOB_UNIT of 8295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * memory, and the offset of the next free block in the second SLOB_UNIT. 8395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 84553948491c18413928b85a9025b92af80e7d61d6Nick Piggin#if PAGE_SIZE <= (32767 * 2) 8595b35127f13661abb0dc3459042cdb417d21e692Nick Piggintypedef s16 slobidx_t; 8695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin#else 8795b35127f13661abb0dc3459042cdb417d21e692Nick Piggintypedef s32 slobidx_t; 8895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin#endif 8995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 9010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackallstruct slob_block { 9195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slobidx_t units; 92553948491c18413928b85a9025b92af80e7d61d6Nick Piggin}; 9310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackalltypedef struct slob_block slob_t; 9410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 9595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 9620cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall * All partially free slob pages go on these lists. 9795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 9820cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall#define SLOB_BREAK1 256 9920cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall#define SLOB_BREAK2 1024 10020cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackallstatic LIST_HEAD(free_slob_small); 10120cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackallstatic LIST_HEAD(free_slob_medium); 10220cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackallstatic LIST_HEAD(free_slob_large); 10395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 10495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 10595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * slob_page_free: true for pages on free_slob_pages list. 10695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 107b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameterstatic inline int slob_page_free(struct page *sp) 10895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 109b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter return PageSlobFree(sp); 11095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 11195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 112b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameterstatic void set_slob_page_free(struct page *sp, struct list_head *list) 11395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 11434bf6ef94a835a8f1d8abd3e7d38c6c08d205867Dave Hansen list_add(&sp->lru, list); 115b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter __SetPageSlobFree(sp); 11695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 11795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 118b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameterstatic inline void clear_slob_page_free(struct page *sp) 11995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 12034bf6ef94a835a8f1d8abd3e7d38c6c08d205867Dave Hansen list_del(&sp->lru); 121b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter __ClearPageSlobFree(sp); 12295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 12395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 12410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall#define SLOB_UNIT sizeof(slob_t) 125a6d78159f8a717263bea71bef738256dafe6260dSasha Levin#define SLOB_UNITS(size) DIV_ROUND_UP(size, SLOB_UNIT) 12610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 127afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin/* 128afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin * struct slob_rcu is inserted at the tail of allocated slob blocks, which 129afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin * were created with a SLAB_DESTROY_BY_RCU slab. slob_rcu is used to free 130afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin * the block using call_rcu. 131afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin */ 132afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Pigginstruct slob_rcu { 133afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin struct rcu_head head; 134afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin int size; 135afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin}; 136afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin 13795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 13895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * slob_lock protects all slob allocator structures. 13995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 14010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackallstatic DEFINE_SPINLOCK(slob_lock); 14110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 14295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 14395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * Encode the given size and next info into a free slob block s. 14495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 14595b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic void set_slob(slob_t *s, slobidx_t size, slob_t *next) 14695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 14795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK); 14895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slobidx_t offset = next - base; 149bcb4ddb46a4c66d64d091e7ffa951b2aa1ba537fDimitri Gorokhovik 15095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (size > 1) { 15195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin s[0].units = size; 15295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin s[1].units = offset; 15395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } else 15495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin s[0].units = -offset; 15595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 15610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 15795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 15895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * Return the size of a slob block. 15995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 16095b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic slobidx_t slob_units(slob_t *s) 16195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 16295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (s->units > 0) 16395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin return s->units; 16495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin return 1; 16595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 16695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 16795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 16895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * Return the next free slob block pointer after this one. 16995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 17095b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic slob_t *slob_next(slob_t *s) 17195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 17295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK); 17395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slobidx_t next; 17495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 17595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (s[0].units < 0) 17695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin next = -s[0].units; 17795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin else 17895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin next = s[1].units; 17995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin return base+next; 18095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 18195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 18295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 18395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * Returns true if s is the last free block in its page. 18495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 18595b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic int slob_last(slob_t *s) 18695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 18795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin return !((unsigned long)slob_next(s) & ~PAGE_MASK); 18895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 18995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 1906e9ed0cc4b963fde66ab47d9fb19147631e44555Américo Wangstatic void *slob_new_pages(gfp_t gfp, int order, int node) 1916193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt{ 1926193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt void *page; 1936193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt 1946193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt#ifdef CONFIG_NUMA 19590f2cbbc49a8fe5a49cea1d362d90e377b949d49Ezequiel Garcia if (node != NUMA_NO_NODE) 1966484eb3e2a81807722c5f28efef94d8338b7b996Mel Gorman page = alloc_pages_exact_node(node, gfp, order); 1976193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt else 1986193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt#endif 1996193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt page = alloc_pages(gfp, order); 2006193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt 2016193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt if (!page) 2026193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt return NULL; 2036193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt 2046193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt return page_address(page); 2056193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt} 2066193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt 2076e9ed0cc4b963fde66ab47d9fb19147631e44555Américo Wangstatic void slob_free_pages(void *b, int order) 2086e9ed0cc4b963fde66ab47d9fb19147631e44555Américo Wang{ 2091f0532eb617d28f65c93593a1491f662f14f7eacNick Piggin if (current->reclaim_state) 2101f0532eb617d28f65c93593a1491f662f14f7eacNick Piggin current->reclaim_state->reclaimed_slab += 1 << order; 2116e9ed0cc4b963fde66ab47d9fb19147631e44555Américo Wang free_pages((unsigned long)b, order); 2126e9ed0cc4b963fde66ab47d9fb19147631e44555Américo Wang} 2136e9ed0cc4b963fde66ab47d9fb19147631e44555Américo Wang 21495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 21595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * Allocate a slob block within a given slob_page sp. 21695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 217b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameterstatic void *slob_page_alloc(struct page *sp, size_t size, int align) 21810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 2196e9ed0cc4b963fde66ab47d9fb19147631e44555Américo Wang slob_t *prev, *cur, *aligned = NULL; 22010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall int delta = 0, units = SLOB_UNITS(size); 22110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 222b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter for (prev = NULL, cur = sp->freelist; ; prev = cur, cur = slob_next(cur)) { 22395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slobidx_t avail = slob_units(cur); 22495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 22510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall if (align) { 22610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall aligned = (slob_t *)ALIGN((unsigned long)cur, align); 22710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall delta = aligned - cur; 22810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall } 22995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (avail >= units + delta) { /* room enough? */ 23095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slob_t *next; 23195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 23210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall if (delta) { /* need to fragment head to align? */ 23395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin next = slob_next(cur); 23495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(aligned, avail - delta, next); 23595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(cur, delta, aligned); 23610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall prev = cur; 23710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall cur = aligned; 23895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin avail = slob_units(cur); 23910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall } 24010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 24195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin next = slob_next(cur); 24295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (avail == units) { /* exact fit? unlink. */ 24395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (prev) 24495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(prev, slob_units(prev), next); 24595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin else 246b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter sp->freelist = next; 24795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } else { /* fragment */ 24895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (prev) 24995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(prev, slob_units(prev), cur + units); 25095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin else 251b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter sp->freelist = cur + units; 25295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(cur + units, avail - units, next); 25310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall } 25410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 25595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp->units -= units; 25695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (!sp->units) 25795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin clear_slob_page_free(sp); 25810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall return cur; 25910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall } 26095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (slob_last(cur)) 26195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin return NULL; 26295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } 26395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 26410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 26595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 26695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * slob_alloc: entry point into the slob allocator. 26795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 2686193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundtstatic void *slob_alloc(size_t size, gfp_t gfp, int align, int node) 26995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 270b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter struct page *sp; 271d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall struct list_head *prev; 27220cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall struct list_head *slob_list; 27395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slob_t *b = NULL; 27495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin unsigned long flags; 27510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 27620cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall if (size < SLOB_BREAK1) 27720cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall slob_list = &free_slob_small; 27820cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall else if (size < SLOB_BREAK2) 27920cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall slob_list = &free_slob_medium; 28020cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall else 28120cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall slob_list = &free_slob_large; 28220cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall 28395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin spin_lock_irqsave(&slob_lock, flags); 28495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin /* Iterate through each partially free page, try to find room */ 28534bf6ef94a835a8f1d8abd3e7d38c6c08d205867Dave Hansen list_for_each_entry(sp, slob_list, lru) { 2866193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt#ifdef CONFIG_NUMA 2876193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt /* 2886193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * If there's a node specification, search for a partial 2896193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * page with a matching node id in the freelist. 2906193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt */ 29190f2cbbc49a8fe5a49cea1d362d90e377b949d49Ezequiel Garcia if (node != NUMA_NO_NODE && page_to_nid(sp) != node) 2926193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt continue; 2936193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt#endif 294d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall /* Enough room on this page? */ 295d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall if (sp->units < SLOB_UNITS(size)) 296d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall continue; 2976193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt 298d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall /* Attempt to alloc */ 29934bf6ef94a835a8f1d8abd3e7d38c6c08d205867Dave Hansen prev = sp->lru.prev; 300d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall b = slob_page_alloc(sp, size, align); 301d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall if (!b) 302d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall continue; 303d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall 304d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall /* Improve fragment distribution and reduce our average 305d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall * search time by starting our next search here. (see 306d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall * Knuth vol 1, sec 2.5, pg 449) */ 30720cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall if (prev != slob_list->prev && 30820cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall slob_list->next != prev->next) 30920cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall list_move_tail(slob_list, prev->next); 310d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall break; 31110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall } 31295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin spin_unlock_irqrestore(&slob_lock, flags); 31395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 31495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin /* Not enough space: must allocate a new page */ 31595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (!b) { 3166e9ed0cc4b963fde66ab47d9fb19147631e44555Américo Wang b = slob_new_pages(gfp & ~__GFP_ZERO, 0, node); 31795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (!b) 3186e9ed0cc4b963fde66ab47d9fb19147631e44555Américo Wang return NULL; 319b5568280c9b9162b384be9d447013b74d682d4b3Christoph Lameter sp = virt_to_page(b); 320b5568280c9b9162b384be9d447013b74d682d4b3Christoph Lameter __SetPageSlab(sp); 32195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 32295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin spin_lock_irqsave(&slob_lock, flags); 32395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp->units = SLOB_UNITS(PAGE_SIZE); 324b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter sp->freelist = b; 32534bf6ef94a835a8f1d8abd3e7d38c6c08d205867Dave Hansen INIT_LIST_HEAD(&sp->lru); 32695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(b, SLOB_UNITS(PAGE_SIZE), b + SLOB_UNITS(PAGE_SIZE)); 32720cecbae44528d347c46e71f40650b75e0dcbc8eMatt Mackall set_slob_page_free(sp, slob_list); 32895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin b = slob_page_alloc(sp, size, align); 32995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin BUG_ON(!b); 33095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin spin_unlock_irqrestore(&slob_lock, flags); 33195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } 332d07dbea46405b37d59495eb4de9d1056dcfb7c6dChristoph Lameter if (unlikely((gfp & __GFP_ZERO) && b)) 333d07dbea46405b37d59495eb4de9d1056dcfb7c6dChristoph Lameter memset(b, 0, size); 33495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin return b; 33510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 33610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 33795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 33895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * slob_free: entry point into the slob allocator. 33995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 34010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackallstatic void slob_free(void *block, int size) 34110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 342b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter struct page *sp; 34395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slob_t *prev, *next, *b = (slob_t *)block; 34495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slobidx_t units; 34510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall unsigned long flags; 346d602dabaeba79df90cc67c32d5fe4ee0d5e2b73aBob Liu struct list_head *slob_list; 34710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 3482408c55037c3f7d51a8a100025c47595e71b838cSatyam Sharma if (unlikely(ZERO_OR_NULL_PTR(block))) 34910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall return; 35095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin BUG_ON(!size); 35110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 352b5568280c9b9162b384be9d447013b74d682d4b3Christoph Lameter sp = virt_to_page(block); 35395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin units = SLOB_UNITS(size); 35410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 35510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall spin_lock_irqsave(&slob_lock, flags); 35610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 35795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (sp->units + units == SLOB_UNITS(PAGE_SIZE)) { 35895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin /* Go directly to page allocator. Do not pass slob allocator */ 35995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (slob_page_free(sp)) 36095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin clear_slob_page_free(sp); 3616fb8f424393025674fde7869b59f485d1e352182Nick Piggin spin_unlock_irqrestore(&slob_lock, flags); 362b5568280c9b9162b384be9d447013b74d682d4b3Christoph Lameter __ClearPageSlab(sp); 36322b751c3d0376e86a377e3a0aa2ddbbe9d2eefc1Mel Gorman page_mapcount_reset(sp); 3641f0532eb617d28f65c93593a1491f662f14f7eacNick Piggin slob_free_pages(b, 0); 3656fb8f424393025674fde7869b59f485d1e352182Nick Piggin return; 36695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } 36710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 36895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (!slob_page_free(sp)) { 36995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin /* This slob page is about to become partially free. Easy! */ 37095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp->units = units; 371b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter sp->freelist = b; 37295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(b, units, 37395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin (void *)((unsigned long)(b + 37495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin SLOB_UNITS(PAGE_SIZE)) & PAGE_MASK)); 375d602dabaeba79df90cc67c32d5fe4ee0d5e2b73aBob Liu if (size < SLOB_BREAK1) 376d602dabaeba79df90cc67c32d5fe4ee0d5e2b73aBob Liu slob_list = &free_slob_small; 377d602dabaeba79df90cc67c32d5fe4ee0d5e2b73aBob Liu else if (size < SLOB_BREAK2) 378d602dabaeba79df90cc67c32d5fe4ee0d5e2b73aBob Liu slob_list = &free_slob_medium; 379d602dabaeba79df90cc67c32d5fe4ee0d5e2b73aBob Liu else 380d602dabaeba79df90cc67c32d5fe4ee0d5e2b73aBob Liu slob_list = &free_slob_large; 381d602dabaeba79df90cc67c32d5fe4ee0d5e2b73aBob Liu set_slob_page_free(sp, slob_list); 38295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin goto out; 38395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } 38495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 38595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin /* 38695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * Otherwise the page is already partially free, so find reinsertion 38795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * point. 38895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 38995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp->units += units; 39010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 391b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter if (b < (slob_t *)sp->freelist) { 392b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter if (b + units == sp->freelist) { 393b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter units += slob_units(sp->freelist); 394b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter sp->freelist = slob_next(sp->freelist); 395679299b32dbf9bac4bdaedc850fb95d0f81b4963Matt Mackall } 396b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter set_slob(b, units, sp->freelist); 397b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter sp->freelist = b; 39895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } else { 399b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter prev = sp->freelist; 40095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin next = slob_next(prev); 40195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin while (b > next) { 40295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin prev = next; 40395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin next = slob_next(prev); 40495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } 40510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 40695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (!slob_last(prev) && b + units == next) { 40795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin units += slob_units(next); 40895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(b, units, slob_next(next)); 40995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } else 41095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(b, units, next); 41195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 41295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (prev + slob_units(prev) == b) { 41395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin units = slob_units(b) + slob_units(prev); 41495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(prev, units, slob_next(b)); 41595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } else 41695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(prev, slob_units(prev), b); 41795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } 41895b35127f13661abb0dc3459042cdb417d21e692Nick Pigginout: 41910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall spin_unlock_irqrestore(&slob_lock, flags); 42010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 42110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 42295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 42395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * End of slob allocator proper. Begin kmem_cache_alloc and kmalloc frontend. 42495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 42595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 426f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garciastatic __always_inline void * 427f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia__do_kmalloc_node(size_t size, gfp_t gfp, int node, unsigned long caller) 42810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 4296cb8f91320d3e720351c21741da795fed580b21bChristoph Lameter unsigned int *m; 430789306e5ad6b3051c263ac2478875efa8bc07462Arnd Bergmann int align = max_t(size_t, ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN); 4313eae2cb24a96509e0a38cc48dc1538a2826f4e33Eduard - Gabriel Munteanu void *ret; 432553948491c18413928b85a9025b92af80e7d61d6Nick Piggin 433bd50cfa89153a67429935a15e577a5eb5f10dd1bSteven Rostedt gfp &= gfp_allowed_mask; 434bd50cfa89153a67429935a15e577a5eb5f10dd1bSteven Rostedt 43519cefdffbfe0f7e280f21e80875937e8700e99e2Ingo Molnar lockdep_trace_alloc(gfp); 436cf40bd16fdad42c053040bcd3988f5fdedbb6c57Nick Piggin 437553948491c18413928b85a9025b92af80e7d61d6Nick Piggin if (size < PAGE_SIZE - align) { 4386cb8f91320d3e720351c21741da795fed580b21bChristoph Lameter if (!size) 4396cb8f91320d3e720351c21741da795fed580b21bChristoph Lameter return ZERO_SIZE_PTR; 4406cb8f91320d3e720351c21741da795fed580b21bChristoph Lameter 4416193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt m = slob_alloc(size + align, gfp, align, node); 4423eae2cb24a96509e0a38cc48dc1538a2826f4e33Eduard - Gabriel Munteanu 443239f49c0800778c863585a103805c58afbad6748MinChan Kim if (!m) 444239f49c0800778c863585a103805c58afbad6748MinChan Kim return NULL; 445239f49c0800778c863585a103805c58afbad6748MinChan Kim *m = size; 4463eae2cb24a96509e0a38cc48dc1538a2826f4e33Eduard - Gabriel Munteanu ret = (void *)m + align; 4473eae2cb24a96509e0a38cc48dc1538a2826f4e33Eduard - Gabriel Munteanu 448f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia trace_kmalloc_node(caller, ret, 449ca2b84cb3c4a0d4d2143b46ec072cdff5d1b3b87Eduard - Gabriel Munteanu size, size + align, gfp, node); 450d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin } else { 4513eae2cb24a96509e0a38cc48dc1538a2826f4e33Eduard - Gabriel Munteanu unsigned int order = get_order(size); 452d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin 4538df275af8db8220d7e3f1bf97b6ac7aad05f96f0David Rientjes if (likely(order)) 4548df275af8db8220d7e3f1bf97b6ac7aad05f96f0David Rientjes gfp |= __GFP_COMP; 4558df275af8db8220d7e3f1bf97b6ac7aad05f96f0David Rientjes ret = slob_new_pages(gfp, order, node); 4563eae2cb24a96509e0a38cc48dc1538a2826f4e33Eduard - Gabriel Munteanu 457f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia trace_kmalloc_node(caller, ret, 458ca2b84cb3c4a0d4d2143b46ec072cdff5d1b3b87Eduard - Gabriel Munteanu size, PAGE_SIZE << order, gfp, node); 45910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall } 4603eae2cb24a96509e0a38cc48dc1538a2826f4e33Eduard - Gabriel Munteanu 4614374e616d28e65265a5b433ceece275449f3d2e3Catalin Marinas kmemleak_alloc(ret, size, 1, gfp); 4623eae2cb24a96509e0a38cc48dc1538a2826f4e33Eduard - Gabriel Munteanu return ret; 46310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 464f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia 465f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lametervoid *__kmalloc(size_t size, gfp_t gfp) 466f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia{ 467f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lameter return __do_kmalloc_node(size, gfp, NUMA_NO_NODE, _RET_IP_); 468f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia} 469f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph LameterEXPORT_SYMBOL(__kmalloc); 47010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 471f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garciavoid *__kmalloc_track_caller(size_t size, gfp_t gfp, unsigned long caller) 472f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia{ 473f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia return __do_kmalloc_node(size, gfp, NUMA_NO_NODE, caller); 474f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia} 475f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia 476f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia#ifdef CONFIG_NUMA 47782bd5508b4080e851ac1a9b62bed6d727b1b4a84David Rientjesvoid *__kmalloc_node_track_caller(size_t size, gfp_t gfp, 478f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia int node, unsigned long caller) 479f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia{ 480f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia return __do_kmalloc_node(size, gfp, node, caller); 481f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia} 482f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia#endif 483f3f741019595f1e73564d985f5fe8abcbb98c769Ezequiel Garcia 48410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackallvoid kfree(const void *block) 48510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 486b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter struct page *sp; 48710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 4882121db74ba0fd2259f0e2265511684fadda9ac49Pekka Enberg trace_kfree(_RET_IP_, block); 4892121db74ba0fd2259f0e2265511684fadda9ac49Pekka Enberg 4902408c55037c3f7d51a8a100025c47595e71b838cSatyam Sharma if (unlikely(ZERO_OR_NULL_PTR(block))) 49110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall return; 4924374e616d28e65265a5b433ceece275449f3d2e3Catalin Marinas kmemleak_free(block); 49310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 494b5568280c9b9162b384be9d447013b74d682d4b3Christoph Lameter sp = virt_to_page(block); 495b5568280c9b9162b384be9d447013b74d682d4b3Christoph Lameter if (PageSlab(sp)) { 496789306e5ad6b3051c263ac2478875efa8bc07462Arnd Bergmann int align = max_t(size_t, ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN); 497553948491c18413928b85a9025b92af80e7d61d6Nick Piggin unsigned int *m = (unsigned int *)(block - align); 498553948491c18413928b85a9025b92af80e7d61d6Nick Piggin slob_free(m, *m + align); 499d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin } else 5008cf9864b1382851d90c7c505f8441c8928f1469eEzequiel Garcia __free_pages(sp, compound_order(sp)); 50110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 50210cef6029502915bdb3cf0821d425cf9dc30c817Matt MackallEXPORT_SYMBOL(kfree); 50310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 504d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin/* can't use ksize for kmem_cache_alloc memory, only kmalloc */ 505fd76bab2fa6d8f3ef6b326a4c6ae442fa21d30a4Pekka Enbergsize_t ksize(const void *block) 50610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 507b8c24c4aef94b1f0daafb450363fef13a1163780Christoph Lameter struct page *sp; 508999d8795d438d396936811b185428d70b7b7de6dEzequiel Garcia int align; 509999d8795d438d396936811b185428d70b7b7de6dEzequiel Garcia unsigned int *m; 51010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 511ef8b4520bd9f8294ffce9abd6158085bde5dc902Christoph Lameter BUG_ON(!block); 512ef8b4520bd9f8294ffce9abd6158085bde5dc902Christoph Lameter if (unlikely(block == ZERO_SIZE_PTR)) 51310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall return 0; 51410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 515b5568280c9b9162b384be9d447013b74d682d4b3Christoph Lameter sp = virt_to_page(block); 516999d8795d438d396936811b185428d70b7b7de6dEzequiel Garcia if (unlikely(!PageSlab(sp))) 517999d8795d438d396936811b185428d70b7b7de6dEzequiel Garcia return PAGE_SIZE << compound_order(sp); 518999d8795d438d396936811b185428d70b7b7de6dEzequiel Garcia 519789306e5ad6b3051c263ac2478875efa8bc07462Arnd Bergmann align = max_t(size_t, ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN); 520999d8795d438d396936811b185428d70b7b7de6dEzequiel Garcia m = (unsigned int *)(block - align); 521999d8795d438d396936811b185428d70b7b7de6dEzequiel Garcia return SLOB_UNITS(*m) * SLOB_UNIT; 52210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 523b1aabecd55931ee754f6a913969516b26a0e682eKirill A. ShutemovEXPORT_SYMBOL(ksize); 52410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 5258a13a4cc80bb25c9eab2e7e56bab724fcfa55fceChristoph Lameterint __kmem_cache_create(struct kmem_cache *c, unsigned long flags) 52610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 527278b1bb1313664d4999a7f7d47a8a8d964862d02Christoph Lameter if (flags & SLAB_DESTROY_BY_RCU) { 528278b1bb1313664d4999a7f7d47a8a8d964862d02Christoph Lameter /* leave room for rcu footer at the end of object */ 529278b1bb1313664d4999a7f7d47a8a8d964862d02Christoph Lameter c->size += sizeof(struct slob_rcu); 530039363f38bfe5f6281e9eae5e0518b11577d9d50Christoph Lameter } 531278b1bb1313664d4999a7f7d47a8a8d964862d02Christoph Lameter c->flags = flags; 532278b1bb1313664d4999a7f7d47a8a8d964862d02Christoph Lameter return 0; 53310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 53410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 535f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lametervoid *slob_alloc_node(struct kmem_cache *c, gfp_t flags, int node) 53610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 53710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall void *b; 53810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 539bd50cfa89153a67429935a15e577a5eb5f10dd1bSteven Rostedt flags &= gfp_allowed_mask; 540bd50cfa89153a67429935a15e577a5eb5f10dd1bSteven Rostedt 541bd50cfa89153a67429935a15e577a5eb5f10dd1bSteven Rostedt lockdep_trace_alloc(flags); 542bd50cfa89153a67429935a15e577a5eb5f10dd1bSteven Rostedt 5433eae2cb24a96509e0a38cc48dc1538a2826f4e33Eduard - Gabriel Munteanu if (c->size < PAGE_SIZE) { 5446193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt b = slob_alloc(c->size, flags, c->align, node); 545fe74fe2bf293d061826f0d7afc2ca8456bdbb40eEzequiel Garcia trace_kmem_cache_alloc_node(_RET_IP_, b, c->object_size, 546ca2b84cb3c4a0d4d2143b46ec072cdff5d1b3b87Eduard - Gabriel Munteanu SLOB_UNITS(c->size) * SLOB_UNIT, 547ca2b84cb3c4a0d4d2143b46ec072cdff5d1b3b87Eduard - Gabriel Munteanu flags, node); 5483eae2cb24a96509e0a38cc48dc1538a2826f4e33Eduard - Gabriel Munteanu } else { 5496e9ed0cc4b963fde66ab47d9fb19147631e44555Américo Wang b = slob_new_pages(flags, get_order(c->size), node); 550fe74fe2bf293d061826f0d7afc2ca8456bdbb40eEzequiel Garcia trace_kmem_cache_alloc_node(_RET_IP_, b, c->object_size, 551ca2b84cb3c4a0d4d2143b46ec072cdff5d1b3b87Eduard - Gabriel Munteanu PAGE_SIZE << get_order(c->size), 552ca2b84cb3c4a0d4d2143b46ec072cdff5d1b3b87Eduard - Gabriel Munteanu flags, node); 5533eae2cb24a96509e0a38cc48dc1538a2826f4e33Eduard - Gabriel Munteanu } 55410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 555c1e854e924f354657ea2ad08fd7b38aac81c59b1Steven Rostedt if (b && c->ctor) 55651cc50685a4275c6a02653670af9f108a64e01cfAlexey Dobriyan c->ctor(b); 55710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 5584374e616d28e65265a5b433ceece275449f3d2e3Catalin Marinas kmemleak_alloc_recursive(b, c->size, 1, c->flags, flags); 55910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall return b; 56010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 561f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph LameterEXPORT_SYMBOL(slob_alloc_node); 562f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lameter 563f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lametervoid *kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags) 564f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lameter{ 565f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lameter return slob_alloc_node(cachep, flags, NUMA_NO_NODE); 566f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lameter} 567f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph LameterEXPORT_SYMBOL(kmem_cache_alloc); 568f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lameter 569f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lameter#ifdef CONFIG_NUMA 570f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lametervoid *__kmalloc_node(size_t size, gfp_t gfp, int node) 571f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lameter{ 572f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lameter return __do_kmalloc_node(size, gfp, node, _RET_IP_); 573f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lameter} 574f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph LameterEXPORT_SYMBOL(__kmalloc_node); 575f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lameter 576f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lametervoid *kmem_cache_alloc_node(struct kmem_cache *cachep, gfp_t gfp, int node) 577f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lameter{ 578f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lameter return slob_alloc_node(cachep, gfp, node); 579f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lameter} 5806193a2ff180920f84ee06977165ebf32431fc2d2Paul MundtEXPORT_SYMBOL(kmem_cache_alloc_node); 581f1b6eb6e6be149b40ebb013f5bfe2ac86b6f1c1bChristoph Lameter#endif 58210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 583afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Pigginstatic void __kmem_cache_free(void *b, int size) 58410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 585afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin if (size < PAGE_SIZE) 586afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin slob_free(b, size); 58710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall else 5886e9ed0cc4b963fde66ab47d9fb19147631e44555Américo Wang slob_free_pages(b, get_order(size)); 589afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin} 590afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin 591afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Pigginstatic void kmem_rcu_free(struct rcu_head *head) 592afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin{ 593afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin struct slob_rcu *slob_rcu = (struct slob_rcu *)head; 594afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin void *b = (void *)slob_rcu - (slob_rcu->size - sizeof(struct slob_rcu)); 595afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin 596afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin __kmem_cache_free(b, slob_rcu->size); 597afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin} 598afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin 599afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Pigginvoid kmem_cache_free(struct kmem_cache *c, void *b) 600afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin{ 6014374e616d28e65265a5b433ceece275449f3d2e3Catalin Marinas kmemleak_free_recursive(b, c->flags); 602afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin if (unlikely(c->flags & SLAB_DESTROY_BY_RCU)) { 603afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin struct slob_rcu *slob_rcu; 604afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin slob_rcu = b + (c->size - sizeof(struct slob_rcu)); 605afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin slob_rcu->size = c->size; 606afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin call_rcu(&slob_rcu->head, kmem_rcu_free); 607afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin } else { 608afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin __kmem_cache_free(b, c->size); 609afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin } 6103eae2cb24a96509e0a38cc48dc1538a2826f4e33Eduard - Gabriel Munteanu 611ca2b84cb3c4a0d4d2143b46ec072cdff5d1b3b87Eduard - Gabriel Munteanu trace_kmem_cache_free(_RET_IP_, b); 61210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 61310cef6029502915bdb3cf0821d425cf9dc30c817Matt MackallEXPORT_SYMBOL(kmem_cache_free); 61410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 615945cf2b6199be70ff03102b9e642c3bb05d01de9Christoph Lameterint __kmem_cache_shutdown(struct kmem_cache *c) 616945cf2b6199be70ff03102b9e642c3bb05d01de9Christoph Lameter{ 617945cf2b6199be70ff03102b9e642c3bb05d01de9Christoph Lameter /* No way to check for remaining objects */ 618945cf2b6199be70ff03102b9e642c3bb05d01de9Christoph Lameter return 0; 619945cf2b6199be70ff03102b9e642c3bb05d01de9Christoph Lameter} 620945cf2b6199be70ff03102b9e642c3bb05d01de9Christoph Lameter 62103afc0e25f7fc03537014a770f4c54ebbe63a24cVladimir Davydovint __kmem_cache_shrink(struct kmem_cache *d) 6222e892f43ccb602e8ffad73396a1000f2040c9e0bChristoph Lameter{ 6232e892f43ccb602e8ffad73396a1000f2040c9e0bChristoph Lameter return 0; 6242e892f43ccb602e8ffad73396a1000f2040c9e0bChristoph Lameter} 6252e892f43ccb602e8ffad73396a1000f2040c9e0bChristoph Lameter 6269b030cb865f137e1574596983face2a07e41e8b2Christoph Lameterstruct kmem_cache kmem_cache_boot = { 6279b030cb865f137e1574596983face2a07e41e8b2Christoph Lameter .name = "kmem_cache", 6289b030cb865f137e1574596983face2a07e41e8b2Christoph Lameter .size = sizeof(struct kmem_cache), 6299b030cb865f137e1574596983face2a07e41e8b2Christoph Lameter .flags = SLAB_PANIC, 6309b030cb865f137e1574596983face2a07e41e8b2Christoph Lameter .align = ARCH_KMALLOC_MINALIGN, 6319b030cb865f137e1574596983face2a07e41e8b2Christoph Lameter}; 6329b030cb865f137e1574596983face2a07e41e8b2Christoph Lameter 633bcb4ddb46a4c66d64d091e7ffa951b2aa1ba537fDimitri Gorokhovikvoid __init kmem_cache_init(void) 634bcb4ddb46a4c66d64d091e7ffa951b2aa1ba537fDimitri Gorokhovik{ 6359b030cb865f137e1574596983face2a07e41e8b2Christoph Lameter kmem_cache = &kmem_cache_boot; 63697d06609158e61f6bdf538c4a6788e2de492236fChristoph Lameter slab_state = UP; 63710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 638bbff2e433e80fae72c8d00d482927d52ec19ba33Wu Fengguang 639bbff2e433e80fae72c8d00d482927d52ec19ba33Wu Fengguangvoid __init kmem_cache_init_late(void) 640bbff2e433e80fae72c8d00d482927d52ec19ba33Wu Fengguang{ 64197d06609158e61f6bdf538c4a6788e2de492236fChristoph Lameter slab_state = FULL; 642bbff2e433e80fae72c8d00d482927d52ec19ba33Wu Fengguang} 643