slob.c revision ef8b4520bd9f8294ffce9abd6158085bde5dc902
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 * 156193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * The slob heap is a linked list of pages from alloc_pages(), and 1695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * within each page, there is a singly-linked list of free blocks (slob_t). 1795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * The heap is grown on demand and allocation from the heap is currently 1895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * first-fit. 1910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * 2010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * Above this is an implementation of kmalloc/kfree. Blocks returned 21553948491c18413928b85a9025b92af80e7d61d6Nick Piggin * from kmalloc are prepended with a 4-byte header with the kmalloc size. 2210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * If kmalloc is asked for objects of PAGE_SIZE or larger, it calls 236193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * alloc_pages() directly, allocating compound pages so the page order 24d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin * does not have to be separately tracked, and also stores the exact 25d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin * allocation size in page->private so that it can be used to accurately 26d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin * provide ksize(). These objects are detected in kfree() because slob_page() 27d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin * is false for them. 2810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * 2910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall * SLAB is emulated on top of SLOB by simply calling constructors and 3095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * destructors for every SLAB allocation. Objects are returned with the 3195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * 4-byte alignment unless the SLAB_HWCACHE_ALIGN flag is set, in which 3295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * case the low-level allocator will fragment blocks to create the proper 3395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * alignment. Again, objects of page-size or greater are allocated by 346193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * calling alloc_pages(). As SLAB objects know their size, no separate 3595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * size bookkeeping is necessary and there is essentially no allocation 36d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin * space overhead, and compound pages aren't needed for multi-page 37d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin * allocations. 386193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * 396193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * NUMA support in SLOB is fairly simplistic, pushing most of the real 406193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * logic down to the page allocator, and simply doing the node accounting 416193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * on the upper levels. In the event that a node id is explicitly 426193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * provided, alloc_pages_node() with the specified node id is used 436193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * instead. The common case (or when the node id isn't explicitly provided) 446193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * will default to the current node, as per numa_node_id(). 456193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * 466193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * Node aware pages are still inserted in to the global freelist, and 476193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * these are scanned for by matching against the node id encoded in the 486193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * page flags. As a result, block allocations that can be satisfied from 496193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * the freelist will only be done so on pages residing on the same node, 506193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * in order to prevent random node placement. 5110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall */ 5210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 5395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin#include <linux/kernel.h> 5410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall#include <linux/slab.h> 5510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall#include <linux/mm.h> 5610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall#include <linux/cache.h> 5710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall#include <linux/init.h> 5810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall#include <linux/module.h> 59afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin#include <linux/rcupdate.h> 6095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin#include <linux/list.h> 6195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin#include <asm/atomic.h> 6295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 6395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 6495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * slob_block has a field 'units', which indicates size of block if +ve, 6595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * or offset of next block if -ve (in SLOB_UNITs). 6695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * 6795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * Free blocks of size 1 unit simply contain the offset of the next block. 6895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * Those with larger size contain their size in the first SLOB_UNIT of 6995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * memory, and the offset of the next free block in the second SLOB_UNIT. 7095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 71553948491c18413928b85a9025b92af80e7d61d6Nick Piggin#if PAGE_SIZE <= (32767 * 2) 7295b35127f13661abb0dc3459042cdb417d21e692Nick Piggintypedef s16 slobidx_t; 7395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin#else 7495b35127f13661abb0dc3459042cdb417d21e692Nick Piggintypedef s32 slobidx_t; 7595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin#endif 7695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 7710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackallstruct slob_block { 7895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slobidx_t units; 79553948491c18413928b85a9025b92af80e7d61d6Nick Piggin}; 8010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackalltypedef struct slob_block slob_t; 8110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 8295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 8395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * We use struct page fields to manage some slob allocation aspects, 8495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * however to avoid the horrible mess in include/linux/mm_types.h, we'll 8595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * just define our own struct page type variant here. 8695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 8795b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstruct slob_page { 8895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin union { 8995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin struct { 9095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin unsigned long flags; /* mandatory */ 9195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin atomic_t _count; /* mandatory */ 9295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slobidx_t units; /* free units left in page */ 9395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin unsigned long pad[2]; 9495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slob_t *free; /* first free slob_t in page */ 9595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin struct list_head list; /* linked list of free pages */ 9695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin }; 9795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin struct page page; 9895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin }; 9995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin}; 10095b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic inline void struct_slob_page_wrong_size(void) 10195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ BUILD_BUG_ON(sizeof(struct slob_page) != sizeof(struct page)); } 10295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 10395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 10495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * free_slob_page: call before a slob_page is returned to the page allocator. 10595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 10695b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic inline void free_slob_page(struct slob_page *sp) 10795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 10895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin reset_page_mapcount(&sp->page); 10995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp->page.mapping = NULL; 11095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 11195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 11295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 11395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * All (partially) free slob pages go on this list. 11495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 11595b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic LIST_HEAD(free_slob_pages); 11695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 11795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 11895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * slob_page: True for all slob pages (false for bigblock pages) 11995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 12095b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic inline int slob_page(struct slob_page *sp) 12195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 12295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin return test_bit(PG_active, &sp->flags); 12395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 12495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 12595b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic inline void set_slob_page(struct slob_page *sp) 12695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 12795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin __set_bit(PG_active, &sp->flags); 12895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 12995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 13095b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic inline void clear_slob_page(struct slob_page *sp) 13195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 13295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin __clear_bit(PG_active, &sp->flags); 13395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 13495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 13595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 13695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * slob_page_free: true for pages on free_slob_pages list. 13795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 13895b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic inline int slob_page_free(struct slob_page *sp) 13995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 14095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin return test_bit(PG_private, &sp->flags); 14195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 14295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 14395b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic inline void set_slob_page_free(struct slob_page *sp) 14495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 14595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin list_add(&sp->list, &free_slob_pages); 14695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin __set_bit(PG_private, &sp->flags); 14795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 14895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 14995b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic inline void clear_slob_page_free(struct slob_page *sp) 15095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 15195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin list_del(&sp->list); 15295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin __clear_bit(PG_private, &sp->flags); 15395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 15495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 15510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall#define SLOB_UNIT sizeof(slob_t) 15610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall#define SLOB_UNITS(size) (((size) + SLOB_UNIT - 1)/SLOB_UNIT) 15710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall#define SLOB_ALIGN L1_CACHE_BYTES 15810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 159afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin/* 160afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin * struct slob_rcu is inserted at the tail of allocated slob blocks, which 161afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin * were created with a SLAB_DESTROY_BY_RCU slab. slob_rcu is used to free 162afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin * the block using call_rcu. 163afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin */ 164afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Pigginstruct slob_rcu { 165afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin struct rcu_head head; 166afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin int size; 167afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin}; 168afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin 16995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 17095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * slob_lock protects all slob allocator structures. 17195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 17210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackallstatic DEFINE_SPINLOCK(slob_lock); 17310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 17495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 17595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * Encode the given size and next info into a free slob block s. 17695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 17795b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic void set_slob(slob_t *s, slobidx_t size, slob_t *next) 17895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 17995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK); 18095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slobidx_t offset = next - base; 181bcb4ddb46a4c66d64d091e7ffa951b2aa1ba537fDimitri Gorokhovik 18295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (size > 1) { 18395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin s[0].units = size; 18495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin s[1].units = offset; 18595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } else 18695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin s[0].units = -offset; 18795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 18810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 18995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 19095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * Return the size of a slob block. 19195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 19295b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic slobidx_t slob_units(slob_t *s) 19395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 19495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (s->units > 0) 19595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin return s->units; 19695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin return 1; 19795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 19895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 19995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 20095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * Return the next free slob block pointer after this one. 20195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 20295b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic slob_t *slob_next(slob_t *s) 20395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 20495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK); 20595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slobidx_t next; 20695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 20795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (s[0].units < 0) 20895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin next = -s[0].units; 20995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin else 21095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin next = s[1].units; 21195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin return base+next; 21295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 21395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 21495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 21595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * Returns true if s is the last free block in its page. 21695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 21795b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic int slob_last(slob_t *s) 21895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 21995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin return !((unsigned long)slob_next(s) & ~PAGE_MASK); 22095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 22195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 2226193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundtstatic void *slob_new_page(gfp_t gfp, int order, int node) 2236193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt{ 2246193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt void *page; 2256193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt 2266193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt#ifdef CONFIG_NUMA 2276193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt if (node != -1) 2286193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt page = alloc_pages_node(node, gfp, order); 2296193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt else 2306193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt#endif 2316193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt page = alloc_pages(gfp, order); 2326193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt 2336193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt if (!page) 2346193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt return NULL; 2356193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt 2366193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt return page_address(page); 2376193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt} 2386193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt 23995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 24095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * Allocate a slob block within a given slob_page sp. 24195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 24295b35127f13661abb0dc3459042cdb417d21e692Nick Pigginstatic void *slob_page_alloc(struct slob_page *sp, size_t size, int align) 24310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 24410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall slob_t *prev, *cur, *aligned = 0; 24510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall int delta = 0, units = SLOB_UNITS(size); 24610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 24795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin for (prev = NULL, cur = sp->free; ; prev = cur, cur = slob_next(cur)) { 24895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slobidx_t avail = slob_units(cur); 24995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 25010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall if (align) { 25110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall aligned = (slob_t *)ALIGN((unsigned long)cur, align); 25210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall delta = aligned - cur; 25310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall } 25495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (avail >= units + delta) { /* room enough? */ 25595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slob_t *next; 25695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 25710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall if (delta) { /* need to fragment head to align? */ 25895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin next = slob_next(cur); 25995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(aligned, avail - delta, next); 26095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(cur, delta, aligned); 26110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall prev = cur; 26210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall cur = aligned; 26395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin avail = slob_units(cur); 26410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall } 26510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 26695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin next = slob_next(cur); 26795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (avail == units) { /* exact fit? unlink. */ 26895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (prev) 26995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(prev, slob_units(prev), next); 27095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin else 27195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp->free = next; 27295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } else { /* fragment */ 27395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (prev) 27495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(prev, slob_units(prev), cur + units); 27595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin else 27695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp->free = cur + units; 27795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(cur + units, avail - units, next); 27810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall } 27910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 28095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp->units -= units; 28195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (!sp->units) 28295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin clear_slob_page_free(sp); 28310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall return cur; 28410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall } 28595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (slob_last(cur)) 28695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin return NULL; 28795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } 28895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin} 28910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 29095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 29195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * slob_alloc: entry point into the slob allocator. 29295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 2936193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundtstatic void *slob_alloc(size_t size, gfp_t gfp, int align, int node) 29495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin{ 29595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin struct slob_page *sp; 296d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall struct list_head *prev; 29795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slob_t *b = NULL; 29895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin unsigned long flags; 29910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 30095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin spin_lock_irqsave(&slob_lock, flags); 30195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin /* Iterate through each partially free page, try to find room */ 30295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin list_for_each_entry(sp, &free_slob_pages, list) { 3036193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt#ifdef CONFIG_NUMA 3046193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt /* 3056193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * If there's a node specification, search for a partial 3066193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt * page with a matching node id in the freelist. 3076193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt */ 3086193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt if (node != -1 && page_to_nid(&sp->page) != node) 3096193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt continue; 3106193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt#endif 311d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall /* Enough room on this page? */ 312d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall if (sp->units < SLOB_UNITS(size)) 313d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall continue; 3146193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt 315d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall /* Attempt to alloc */ 316d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall prev = sp->list.prev; 317d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall b = slob_page_alloc(sp, size, align); 318d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall if (!b) 319d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall continue; 320d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall 321d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall /* Improve fragment distribution and reduce our average 322d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall * search time by starting our next search here. (see 323d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall * Knuth vol 1, sec 2.5, pg 449) */ 324d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall if (free_slob_pages.next != prev->next) 325d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall list_move_tail(&free_slob_pages, prev->next); 326d6269543ef24aa012aa228c27af3adb074f7b36bMatt Mackall break; 32710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall } 32895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin spin_unlock_irqrestore(&slob_lock, flags); 32995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 33095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin /* Not enough space: must allocate a new page */ 33195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (!b) { 3326193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt b = slob_new_page(gfp, 0, node); 33395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (!b) 33495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin return 0; 33595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp = (struct slob_page *)virt_to_page(b); 33695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob_page(sp); 33795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 33895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin spin_lock_irqsave(&slob_lock, flags); 33995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp->units = SLOB_UNITS(PAGE_SIZE); 34095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp->free = b; 34195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin INIT_LIST_HEAD(&sp->list); 34295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(b, SLOB_UNITS(PAGE_SIZE), b + SLOB_UNITS(PAGE_SIZE)); 34395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob_page_free(sp); 34495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin b = slob_page_alloc(sp, size, align); 34595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin BUG_ON(!b); 34695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin spin_unlock_irqrestore(&slob_lock, flags); 34795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } 348d07dbea46405b37d59495eb4de9d1056dcfb7c6dChristoph Lameter if (unlikely((gfp & __GFP_ZERO) && b)) 349d07dbea46405b37d59495eb4de9d1056dcfb7c6dChristoph Lameter memset(b, 0, size); 35095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin return b; 35110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 35210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 35395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 35495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * slob_free: entry point into the slob allocator. 35595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 35610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackallstatic void slob_free(void *block, int size) 35710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 35895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin struct slob_page *sp; 35995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slob_t *prev, *next, *b = (slob_t *)block; 36095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin slobidx_t units; 36110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall unsigned long flags; 36210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 3632408c55037c3f7d51a8a100025c47595e71b838cSatyam Sharma if (unlikely(ZERO_OR_NULL_PTR(block))) 36410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall return; 36595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin BUG_ON(!size); 36610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 36795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp = (struct slob_page *)virt_to_page(block); 36895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin units = SLOB_UNITS(size); 36910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 37010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall spin_lock_irqsave(&slob_lock, flags); 37110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 37295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (sp->units + units == SLOB_UNITS(PAGE_SIZE)) { 37395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin /* Go directly to page allocator. Do not pass slob allocator */ 37495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (slob_page_free(sp)) 37595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin clear_slob_page_free(sp); 37695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin clear_slob_page(sp); 37795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin free_slob_page(sp); 37895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin free_page((unsigned long)b); 37995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin goto out; 38095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } 38110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 38295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (!slob_page_free(sp)) { 38395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin /* This slob page is about to become partially free. Easy! */ 38495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp->units = units; 38595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp->free = b; 38695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(b, units, 38795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin (void *)((unsigned long)(b + 38895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin SLOB_UNITS(PAGE_SIZE)) & PAGE_MASK)); 38995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob_page_free(sp); 39095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin goto out; 39195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } 39295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 39395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin /* 39495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * Otherwise the page is already partially free, so find reinsertion 39595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * point. 39695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 39795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp->units += units; 39810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 39995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (b < sp->free) { 40095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(b, units, sp->free); 40195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp->free = b; 40295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } else { 40395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin prev = sp->free; 40495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin next = slob_next(prev); 40595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin while (b > next) { 40695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin prev = next; 40795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin next = slob_next(prev); 40895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } 40910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 41095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (!slob_last(prev) && b + units == next) { 41195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin units += slob_units(next); 41295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(b, units, slob_next(next)); 41395b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } else 41495b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(b, units, next); 41595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 41695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (prev + slob_units(prev) == b) { 41795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin units = slob_units(b) + slob_units(prev); 41895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(prev, units, slob_next(b)); 41995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } else 42095b35127f13661abb0dc3459042cdb417d21e692Nick Piggin set_slob(prev, slob_units(prev), b); 42195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin } 42295b35127f13661abb0dc3459042cdb417d21e692Nick Pigginout: 42310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall spin_unlock_irqrestore(&slob_lock, flags); 42410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 42510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 42695b35127f13661abb0dc3459042cdb417d21e692Nick Piggin/* 42795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin * End of slob allocator proper. Begin kmem_cache_alloc and kmalloc frontend. 42895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin */ 42995b35127f13661abb0dc3459042cdb417d21e692Nick Piggin 430553948491c18413928b85a9025b92af80e7d61d6Nick Piggin#ifndef ARCH_KMALLOC_MINALIGN 431553948491c18413928b85a9025b92af80e7d61d6Nick Piggin#define ARCH_KMALLOC_MINALIGN __alignof__(unsigned long) 432553948491c18413928b85a9025b92af80e7d61d6Nick Piggin#endif 433553948491c18413928b85a9025b92af80e7d61d6Nick Piggin 434553948491c18413928b85a9025b92af80e7d61d6Nick Piggin#ifndef ARCH_SLAB_MINALIGN 435553948491c18413928b85a9025b92af80e7d61d6Nick Piggin#define ARCH_SLAB_MINALIGN __alignof__(unsigned long) 436553948491c18413928b85a9025b92af80e7d61d6Nick Piggin#endif 437553948491c18413928b85a9025b92af80e7d61d6Nick Piggin 4386193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundtvoid *__kmalloc_node(size_t size, gfp_t gfp, int node) 43910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 4406cb8f91320d3e720351c21741da795fed580b21bChristoph Lameter unsigned int *m; 441553948491c18413928b85a9025b92af80e7d61d6Nick Piggin int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN); 442553948491c18413928b85a9025b92af80e7d61d6Nick Piggin 443553948491c18413928b85a9025b92af80e7d61d6Nick Piggin if (size < PAGE_SIZE - align) { 4446cb8f91320d3e720351c21741da795fed580b21bChristoph Lameter if (!size) 4456cb8f91320d3e720351c21741da795fed580b21bChristoph Lameter return ZERO_SIZE_PTR; 4466cb8f91320d3e720351c21741da795fed580b21bChristoph Lameter 4476193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt m = slob_alloc(size + align, gfp, align, node); 44895b35127f13661abb0dc3459042cdb417d21e692Nick Piggin if (m) 449553948491c18413928b85a9025b92af80e7d61d6Nick Piggin *m = size; 450553948491c18413928b85a9025b92af80e7d61d6Nick Piggin return (void *)m + align; 451d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin } else { 452d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin void *ret; 453d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin 4546193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt ret = slob_new_page(gfp | __GFP_COMP, get_order(size), node); 455d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin if (ret) { 456d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin struct page *page; 457d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin page = virt_to_page(ret); 458d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin page->private = size; 459d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin } 460d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin return ret; 46110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall } 46210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 4636193a2ff180920f84ee06977165ebf32431fc2d2Paul MundtEXPORT_SYMBOL(__kmalloc_node); 46410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 46510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackallvoid kfree(const void *block) 46610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 46795b35127f13661abb0dc3459042cdb417d21e692Nick Piggin struct slob_page *sp; 46810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 4692408c55037c3f7d51a8a100025c47595e71b838cSatyam Sharma if (unlikely(ZERO_OR_NULL_PTR(block))) 47010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall return; 47110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 47295b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp = (struct slob_page *)virt_to_page(block); 473d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin if (slob_page(sp)) { 474553948491c18413928b85a9025b92af80e7d61d6Nick Piggin int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN); 475553948491c18413928b85a9025b92af80e7d61d6Nick Piggin unsigned int *m = (unsigned int *)(block - align); 476553948491c18413928b85a9025b92af80e7d61d6Nick Piggin slob_free(m, *m + align); 477d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin } else 478d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin put_page(&sp->page); 47910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 48010cef6029502915bdb3cf0821d425cf9dc30c817Matt MackallEXPORT_SYMBOL(kfree); 48110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 482d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin/* can't use ksize for kmem_cache_alloc memory, only kmalloc */ 483fd76bab2fa6d8f3ef6b326a4c6ae442fa21d30a4Pekka Enbergsize_t ksize(const void *block) 48410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 48595b35127f13661abb0dc3459042cdb417d21e692Nick Piggin struct slob_page *sp; 48610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 487ef8b4520bd9f8294ffce9abd6158085bde5dc902Christoph Lameter BUG_ON(!block); 488ef8b4520bd9f8294ffce9abd6158085bde5dc902Christoph Lameter if (unlikely(block == ZERO_SIZE_PTR)) 48910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall return 0; 49010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 49195b35127f13661abb0dc3459042cdb417d21e692Nick Piggin sp = (struct slob_page *)virt_to_page(block); 492d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin if (slob_page(sp)) 493d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin return ((slob_t *)block - 1)->units + SLOB_UNIT; 494d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin else 495d87a133fc21d842e3cc285e6bbff727181abec81Nick Piggin return sp->page.private; 49610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 49710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 49810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackallstruct kmem_cache { 49910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall unsigned int size, align; 500afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin unsigned long flags; 50110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall const char *name; 50210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall void (*ctor)(void *, struct kmem_cache *, unsigned long); 50310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall}; 50410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 50510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackallstruct kmem_cache *kmem_cache_create(const char *name, size_t size, 50610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall size_t align, unsigned long flags, 50720c2df83d25c6a95affe6157a4c9cac4cf5ffaacPaul Mundt void (*ctor)(void*, struct kmem_cache *, unsigned long)) 50810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 50910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall struct kmem_cache *c; 51010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 5116193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt c = slob_alloc(sizeof(struct kmem_cache), flags, 0, -1); 51210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 51310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall if (c) { 51410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall c->name = name; 51510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall c->size = size; 516afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin if (flags & SLAB_DESTROY_BY_RCU) { 517afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin /* leave room for rcu footer at the end of object */ 518afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin c->size += sizeof(struct slob_rcu); 519afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin } 520afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin c->flags = flags; 52110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall c->ctor = ctor; 52210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall /* ignore alignment unless it's forced */ 5235af60839909b8e3b28ca7cd7912fa0b23475617fChristoph Lameter c->align = (flags & SLAB_HWCACHE_ALIGN) ? SLOB_ALIGN : 0; 524553948491c18413928b85a9025b92af80e7d61d6Nick Piggin if (c->align < ARCH_SLAB_MINALIGN) 525553948491c18413928b85a9025b92af80e7d61d6Nick Piggin c->align = ARCH_SLAB_MINALIGN; 52610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall if (c->align < align) 52710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall c->align = align; 528bc0055aee40ba40627361d8ffd8530d315920f18Akinobu Mita } else if (flags & SLAB_PANIC) 529bc0055aee40ba40627361d8ffd8530d315920f18Akinobu Mita panic("Cannot create slab cache %s\n", name); 53010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 53110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall return c; 53210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 53310cef6029502915bdb3cf0821d425cf9dc30c817Matt MackallEXPORT_SYMBOL(kmem_cache_create); 53410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 535133d205a18b7a4d8cb52959c5310f6664277cf61Alexey Dobriyanvoid kmem_cache_destroy(struct kmem_cache *c) 53610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 53710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall slob_free(c, sizeof(struct kmem_cache)); 53810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 53910cef6029502915bdb3cf0821d425cf9dc30c817Matt MackallEXPORT_SYMBOL(kmem_cache_destroy); 54010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 5416193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundtvoid *kmem_cache_alloc_node(struct kmem_cache *c, gfp_t flags, int node) 54210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 54310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall void *b; 54410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 54510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall if (c->size < PAGE_SIZE) 5466193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt b = slob_alloc(c->size, flags, c->align, node); 54710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall else 5486193a2ff180920f84ee06977165ebf32431fc2d2Paul Mundt b = slob_new_page(flags, get_order(c->size), node); 54910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 55010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall if (c->ctor) 551a35afb830f8d71ec211531aeb9a621b09a2efb39Christoph Lameter c->ctor(b, c, 0); 55210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 55310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall return b; 55410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 5556193a2ff180920f84ee06977165ebf32431fc2d2Paul MundtEXPORT_SYMBOL(kmem_cache_alloc_node); 55610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 557afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Pigginstatic void __kmem_cache_free(void *b, int size) 55810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 559afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin if (size < PAGE_SIZE) 560afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin slob_free(b, size); 56110cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall else 562afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin free_pages((unsigned long)b, get_order(size)); 563afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin} 564afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin 565afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Pigginstatic void kmem_rcu_free(struct rcu_head *head) 566afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin{ 567afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin struct slob_rcu *slob_rcu = (struct slob_rcu *)head; 568afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin void *b = (void *)slob_rcu - (slob_rcu->size - sizeof(struct slob_rcu)); 569afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin 570afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin __kmem_cache_free(b, slob_rcu->size); 571afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin} 572afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin 573afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Pigginvoid kmem_cache_free(struct kmem_cache *c, void *b) 574afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin{ 575afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin if (unlikely(c->flags & SLAB_DESTROY_BY_RCU)) { 576afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin struct slob_rcu *slob_rcu; 577afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin slob_rcu = b + (c->size - sizeof(struct slob_rcu)); 578afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin INIT_RCU_HEAD(&slob_rcu->head); 579afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin slob_rcu->size = c->size; 580afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin call_rcu(&slob_rcu->head, kmem_rcu_free); 581afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin } else { 582afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin __kmem_cache_free(b, c->size); 583afc0cedbe9138e3e8b38bfa1e4dfd01a2c537d62Nick Piggin } 58410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 58510cef6029502915bdb3cf0821d425cf9dc30c817Matt MackallEXPORT_SYMBOL(kmem_cache_free); 58610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 58710cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackallunsigned int kmem_cache_size(struct kmem_cache *c) 58810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 58910cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall return c->size; 59010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 59110cef6029502915bdb3cf0821d425cf9dc30c817Matt MackallEXPORT_SYMBOL(kmem_cache_size); 59210cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 59310cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackallconst char *kmem_cache_name(struct kmem_cache *c) 59410cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall{ 59510cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall return c->name; 59610cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 59710cef6029502915bdb3cf0821d425cf9dc30c817Matt MackallEXPORT_SYMBOL(kmem_cache_name); 59810cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall 5992e892f43ccb602e8ffad73396a1000f2040c9e0bChristoph Lameterint kmem_cache_shrink(struct kmem_cache *d) 6002e892f43ccb602e8ffad73396a1000f2040c9e0bChristoph Lameter{ 6012e892f43ccb602e8ffad73396a1000f2040c9e0bChristoph Lameter return 0; 6022e892f43ccb602e8ffad73396a1000f2040c9e0bChristoph Lameter} 6032e892f43ccb602e8ffad73396a1000f2040c9e0bChristoph LameterEXPORT_SYMBOL(kmem_cache_shrink); 6042e892f43ccb602e8ffad73396a1000f2040c9e0bChristoph Lameter 60555935a34a428a1497e3b37982e2782c09c6f914dChristoph Lameterint kmem_ptr_validate(struct kmem_cache *a, const void *b) 6062e892f43ccb602e8ffad73396a1000f2040c9e0bChristoph Lameter{ 6072e892f43ccb602e8ffad73396a1000f2040c9e0bChristoph Lameter return 0; 6082e892f43ccb602e8ffad73396a1000f2040c9e0bChristoph Lameter} 6092e892f43ccb602e8ffad73396a1000f2040c9e0bChristoph Lameter 61084a01c2f8ea9bf210b961c6301e8e870a46505a6Paul Mundtstatic unsigned int slob_ready __read_mostly; 61184a01c2f8ea9bf210b961c6301e8e870a46505a6Paul Mundt 61284a01c2f8ea9bf210b961c6301e8e870a46505a6Paul Mundtint slab_is_available(void) 61384a01c2f8ea9bf210b961c6301e8e870a46505a6Paul Mundt{ 61484a01c2f8ea9bf210b961c6301e8e870a46505a6Paul Mundt return slob_ready; 61584a01c2f8ea9bf210b961c6301e8e870a46505a6Paul Mundt} 61684a01c2f8ea9bf210b961c6301e8e870a46505a6Paul Mundt 617bcb4ddb46a4c66d64d091e7ffa951b2aa1ba537fDimitri Gorokhovikvoid __init kmem_cache_init(void) 618bcb4ddb46a4c66d64d091e7ffa951b2aa1ba537fDimitri Gorokhovik{ 61984a01c2f8ea9bf210b961c6301e8e870a46505a6Paul Mundt slob_ready = 1; 62010cef6029502915bdb3cf0821d425cf9dc30c817Matt Mackall} 621