blob: 45d4ca79933a84eec7e9e824f5d3117f3dc4dc64 [file] [log] [blame]
Matt Mackall10cef602006-01-08 01:01:45 -08001/*
2 * SLOB Allocator: Simple List Of Blocks
3 *
4 * Matt Mackall <mpm@selenic.com> 12/30/03
5 *
Paul Mundt6193a2f2007-07-15 23:38:22 -07006 * NUMA support by Paul Mundt, 2007.
7 *
Matt Mackall10cef602006-01-08 01:01:45 -08008 * How SLOB works:
9 *
10 * The core of SLOB is a traditional K&R style heap allocator, with
11 * support for returning aligned objects. The granularity of this
Nick Piggin55394842007-07-15 23:38:09 -070012 * allocator is as little as 2 bytes, however typically most architectures
13 * will require 4 bytes on 32-bit and 8 bytes on 64-bit.
Nick Piggin95b35122007-07-15 23:38:07 -070014 *
Matt Mackall20cecba2008-02-04 22:29:37 -080015 * The slob heap is a set of linked list of pages from alloc_pages(),
16 * and within each page, there is a singly-linked list of free blocks
17 * (slob_t). The heap is grown on demand. To reduce fragmentation,
18 * heap pages are segregated into three lists, with objects less than
19 * 256 bytes, objects less than 1024 bytes, and all other objects.
20 *
21 * Allocation from heap involves first searching for a page with
22 * sufficient free blocks (using a next-fit-like approach) followed by
23 * a first-fit scan of the page. Deallocation inserts objects back
24 * into the free list in address order, so this is effectively an
25 * address-ordered first fit.
Matt Mackall10cef602006-01-08 01:01:45 -080026 *
27 * Above this is an implementation of kmalloc/kfree. Blocks returned
Nick Piggin55394842007-07-15 23:38:09 -070028 * from kmalloc are prepended with a 4-byte header with the kmalloc size.
Matt Mackall10cef602006-01-08 01:01:45 -080029 * If kmalloc is asked for objects of PAGE_SIZE or larger, it calls
Paul Mundt6193a2f2007-07-15 23:38:22 -070030 * alloc_pages() directly, allocating compound pages so the page order
Nick Piggind87a1332007-07-15 23:38:08 -070031 * does not have to be separately tracked, and also stores the exact
32 * allocation size in page->private so that it can be used to accurately
33 * provide ksize(). These objects are detected in kfree() because slob_page()
34 * is false for them.
Matt Mackall10cef602006-01-08 01:01:45 -080035 *
36 * SLAB is emulated on top of SLOB by simply calling constructors and
Nick Piggin95b35122007-07-15 23:38:07 -070037 * destructors for every SLAB allocation. Objects are returned with the
38 * 4-byte alignment unless the SLAB_HWCACHE_ALIGN flag is set, in which
39 * case the low-level allocator will fragment blocks to create the proper
40 * alignment. Again, objects of page-size or greater are allocated by
Paul Mundt6193a2f2007-07-15 23:38:22 -070041 * calling alloc_pages(). As SLAB objects know their size, no separate
Nick Piggin95b35122007-07-15 23:38:07 -070042 * size bookkeeping is necessary and there is essentially no allocation
Nick Piggind87a1332007-07-15 23:38:08 -070043 * space overhead, and compound pages aren't needed for multi-page
44 * allocations.
Paul Mundt6193a2f2007-07-15 23:38:22 -070045 *
46 * NUMA support in SLOB is fairly simplistic, pushing most of the real
47 * logic down to the page allocator, and simply doing the node accounting
48 * on the upper levels. In the event that a node id is explicitly
Mel Gorman6484eb32009-06-16 15:31:54 -070049 * provided, alloc_pages_exact_node() with the specified node id is used
Paul Mundt6193a2f2007-07-15 23:38:22 -070050 * instead. The common case (or when the node id isn't explicitly provided)
51 * will default to the current node, as per numa_node_id().
52 *
53 * Node aware pages are still inserted in to the global freelist, and
54 * these are scanned for by matching against the node id encoded in the
55 * page flags. As a result, block allocations that can be satisfied from
56 * the freelist will only be done so on pages residing on the same node,
57 * in order to prevent random node placement.
Matt Mackall10cef602006-01-08 01:01:45 -080058 */
59
Nick Piggin95b35122007-07-15 23:38:07 -070060#include <linux/kernel.h>
Matt Mackall10cef602006-01-08 01:01:45 -080061#include <linux/slab.h>
Christoph Lameter97d06602012-07-06 15:25:11 -050062#include "slab.h"
63
Matt Mackall10cef602006-01-08 01:01:45 -080064#include <linux/mm.h>
Nick Piggin1f0532e2009-05-05 19:13:45 +100065#include <linux/swap.h> /* struct reclaim_state */
Matt Mackall10cef602006-01-08 01:01:45 -080066#include <linux/cache.h>
67#include <linux/init.h>
Paul Gortmakerb95f1b312011-10-16 02:01:52 -040068#include <linux/export.h>
Nick Pigginafc0ced2007-05-16 22:10:49 -070069#include <linux/rcupdate.h>
Nick Piggin95b35122007-07-15 23:38:07 -070070#include <linux/list.h>
Catalin Marinas4374e612009-06-11 13:23:17 +010071#include <linux/kmemleak.h>
Li Zefan039ca4e2010-05-26 17:22:17 +080072
73#include <trace/events/kmem.h>
74
Arun Sharma600634972011-07-26 16:09:06 -070075#include <linux/atomic.h>
Matt Mackall10cef602006-01-08 01:01:45 -080076
Nick Piggin95b35122007-07-15 23:38:07 -070077/*
78 * slob_block has a field 'units', which indicates size of block if +ve,
79 * or offset of next block if -ve (in SLOB_UNITs).
80 *
81 * Free blocks of size 1 unit simply contain the offset of the next block.
82 * Those with larger size contain their size in the first SLOB_UNIT of
83 * memory, and the offset of the next free block in the second SLOB_UNIT.
84 */
Nick Piggin55394842007-07-15 23:38:09 -070085#if PAGE_SIZE <= (32767 * 2)
Nick Piggin95b35122007-07-15 23:38:07 -070086typedef s16 slobidx_t;
87#else
88typedef s32 slobidx_t;
89#endif
90
Matt Mackall10cef602006-01-08 01:01:45 -080091struct slob_block {
Nick Piggin95b35122007-07-15 23:38:07 -070092 slobidx_t units;
Nick Piggin55394842007-07-15 23:38:09 -070093};
Matt Mackall10cef602006-01-08 01:01:45 -080094typedef struct slob_block slob_t;
95
Nick Piggin95b35122007-07-15 23:38:07 -070096/*
Matt Mackall20cecba2008-02-04 22:29:37 -080097 * All partially free slob pages go on these lists.
Nick Piggin95b35122007-07-15 23:38:07 -070098 */
Matt Mackall20cecba2008-02-04 22:29:37 -080099#define SLOB_BREAK1 256
100#define SLOB_BREAK2 1024
101static LIST_HEAD(free_slob_small);
102static LIST_HEAD(free_slob_medium);
103static LIST_HEAD(free_slob_large);
Nick Piggin95b35122007-07-15 23:38:07 -0700104
105/*
Nick Piggin95b35122007-07-15 23:38:07 -0700106 * slob_page_free: true for pages on free_slob_pages list.
107 */
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500108static inline int slob_page_free(struct page *sp)
Nick Piggin95b35122007-07-15 23:38:07 -0700109{
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500110 return PageSlobFree(sp);
Nick Piggin95b35122007-07-15 23:38:07 -0700111}
112
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500113static void set_slob_page_free(struct page *sp, struct list_head *list)
Nick Piggin95b35122007-07-15 23:38:07 -0700114{
Matt Mackall20cecba2008-02-04 22:29:37 -0800115 list_add(&sp->list, list);
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500116 __SetPageSlobFree(sp);
Nick Piggin95b35122007-07-15 23:38:07 -0700117}
118
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500119static inline void clear_slob_page_free(struct page *sp)
Nick Piggin95b35122007-07-15 23:38:07 -0700120{
121 list_del(&sp->list);
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500122 __ClearPageSlobFree(sp);
Nick Piggin95b35122007-07-15 23:38:07 -0700123}
124
Matt Mackall10cef602006-01-08 01:01:45 -0800125#define SLOB_UNIT sizeof(slob_t)
126#define SLOB_UNITS(size) (((size) + SLOB_UNIT - 1)/SLOB_UNIT)
127#define SLOB_ALIGN L1_CACHE_BYTES
128
Nick Pigginafc0ced2007-05-16 22:10:49 -0700129/*
130 * struct slob_rcu is inserted at the tail of allocated slob blocks, which
131 * were created with a SLAB_DESTROY_BY_RCU slab. slob_rcu is used to free
132 * the block using call_rcu.
133 */
134struct slob_rcu {
135 struct rcu_head head;
136 int size;
137};
138
Nick Piggin95b35122007-07-15 23:38:07 -0700139/*
140 * slob_lock protects all slob allocator structures.
141 */
Matt Mackall10cef602006-01-08 01:01:45 -0800142static DEFINE_SPINLOCK(slob_lock);
Matt Mackall10cef602006-01-08 01:01:45 -0800143
Nick Piggin95b35122007-07-15 23:38:07 -0700144/*
145 * Encode the given size and next info into a free slob block s.
146 */
147static void set_slob(slob_t *s, slobidx_t size, slob_t *next)
148{
149 slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);
150 slobidx_t offset = next - base;
Dimitri Gorokhovikbcb4ddb2006-12-29 16:48:28 -0800151
Nick Piggin95b35122007-07-15 23:38:07 -0700152 if (size > 1) {
153 s[0].units = size;
154 s[1].units = offset;
155 } else
156 s[0].units = -offset;
157}
Matt Mackall10cef602006-01-08 01:01:45 -0800158
Nick Piggin95b35122007-07-15 23:38:07 -0700159/*
160 * Return the size of a slob block.
161 */
162static slobidx_t slob_units(slob_t *s)
163{
164 if (s->units > 0)
165 return s->units;
166 return 1;
167}
168
169/*
170 * Return the next free slob block pointer after this one.
171 */
172static slob_t *slob_next(slob_t *s)
173{
174 slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);
175 slobidx_t next;
176
177 if (s[0].units < 0)
178 next = -s[0].units;
179 else
180 next = s[1].units;
181 return base+next;
182}
183
184/*
185 * Returns true if s is the last free block in its page.
186 */
187static int slob_last(slob_t *s)
188{
189 return !((unsigned long)slob_next(s) & ~PAGE_MASK);
190}
191
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800192static void *slob_new_pages(gfp_t gfp, int order, int node)
Paul Mundt6193a2f2007-07-15 23:38:22 -0700193{
194 void *page;
195
196#ifdef CONFIG_NUMA
197 if (node != -1)
Mel Gorman6484eb32009-06-16 15:31:54 -0700198 page = alloc_pages_exact_node(node, gfp, order);
Paul Mundt6193a2f2007-07-15 23:38:22 -0700199 else
200#endif
201 page = alloc_pages(gfp, order);
202
203 if (!page)
204 return NULL;
205
206 return page_address(page);
207}
208
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800209static void slob_free_pages(void *b, int order)
210{
Nick Piggin1f0532e2009-05-05 19:13:45 +1000211 if (current->reclaim_state)
212 current->reclaim_state->reclaimed_slab += 1 << order;
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800213 free_pages((unsigned long)b, order);
214}
215
Nick Piggin95b35122007-07-15 23:38:07 -0700216/*
217 * Allocate a slob block within a given slob_page sp.
218 */
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500219static void *slob_page_alloc(struct page *sp, size_t size, int align)
Matt Mackall10cef602006-01-08 01:01:45 -0800220{
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800221 slob_t *prev, *cur, *aligned = NULL;
Matt Mackall10cef602006-01-08 01:01:45 -0800222 int delta = 0, units = SLOB_UNITS(size);
Matt Mackall10cef602006-01-08 01:01:45 -0800223
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500224 for (prev = NULL, cur = sp->freelist; ; prev = cur, cur = slob_next(cur)) {
Nick Piggin95b35122007-07-15 23:38:07 -0700225 slobidx_t avail = slob_units(cur);
226
Matt Mackall10cef602006-01-08 01:01:45 -0800227 if (align) {
228 aligned = (slob_t *)ALIGN((unsigned long)cur, align);
229 delta = aligned - cur;
230 }
Nick Piggin95b35122007-07-15 23:38:07 -0700231 if (avail >= units + delta) { /* room enough? */
232 slob_t *next;
233
Matt Mackall10cef602006-01-08 01:01:45 -0800234 if (delta) { /* need to fragment head to align? */
Nick Piggin95b35122007-07-15 23:38:07 -0700235 next = slob_next(cur);
236 set_slob(aligned, avail - delta, next);
237 set_slob(cur, delta, aligned);
Matt Mackall10cef602006-01-08 01:01:45 -0800238 prev = cur;
239 cur = aligned;
Nick Piggin95b35122007-07-15 23:38:07 -0700240 avail = slob_units(cur);
Matt Mackall10cef602006-01-08 01:01:45 -0800241 }
242
Nick Piggin95b35122007-07-15 23:38:07 -0700243 next = slob_next(cur);
244 if (avail == units) { /* exact fit? unlink. */
245 if (prev)
246 set_slob(prev, slob_units(prev), next);
247 else
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500248 sp->freelist = next;
Nick Piggin95b35122007-07-15 23:38:07 -0700249 } else { /* fragment */
250 if (prev)
251 set_slob(prev, slob_units(prev), cur + units);
252 else
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500253 sp->freelist = cur + units;
Nick Piggin95b35122007-07-15 23:38:07 -0700254 set_slob(cur + units, avail - units, next);
Matt Mackall10cef602006-01-08 01:01:45 -0800255 }
256
Nick Piggin95b35122007-07-15 23:38:07 -0700257 sp->units -= units;
258 if (!sp->units)
259 clear_slob_page_free(sp);
Matt Mackall10cef602006-01-08 01:01:45 -0800260 return cur;
261 }
Nick Piggin95b35122007-07-15 23:38:07 -0700262 if (slob_last(cur))
263 return NULL;
Matt Mackall10cef602006-01-08 01:01:45 -0800264 }
265}
266
Nick Piggin95b35122007-07-15 23:38:07 -0700267/*
268 * slob_alloc: entry point into the slob allocator.
269 */
Paul Mundt6193a2f2007-07-15 23:38:22 -0700270static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
Nick Piggin95b35122007-07-15 23:38:07 -0700271{
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500272 struct page *sp;
Matt Mackalld6269542007-07-21 04:37:40 -0700273 struct list_head *prev;
Matt Mackall20cecba2008-02-04 22:29:37 -0800274 struct list_head *slob_list;
Nick Piggin95b35122007-07-15 23:38:07 -0700275 slob_t *b = NULL;
276 unsigned long flags;
277
Matt Mackall20cecba2008-02-04 22:29:37 -0800278 if (size < SLOB_BREAK1)
279 slob_list = &free_slob_small;
280 else if (size < SLOB_BREAK2)
281 slob_list = &free_slob_medium;
282 else
283 slob_list = &free_slob_large;
284
Nick Piggin95b35122007-07-15 23:38:07 -0700285 spin_lock_irqsave(&slob_lock, flags);
286 /* Iterate through each partially free page, try to find room */
Matt Mackall20cecba2008-02-04 22:29:37 -0800287 list_for_each_entry(sp, slob_list, list) {
Paul Mundt6193a2f2007-07-15 23:38:22 -0700288#ifdef CONFIG_NUMA
289 /*
290 * If there's a node specification, search for a partial
291 * page with a matching node id in the freelist.
292 */
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500293 if (node != -1 && page_to_nid(sp) != node)
Paul Mundt6193a2f2007-07-15 23:38:22 -0700294 continue;
295#endif
Matt Mackalld6269542007-07-21 04:37:40 -0700296 /* Enough room on this page? */
297 if (sp->units < SLOB_UNITS(size))
298 continue;
Paul Mundt6193a2f2007-07-15 23:38:22 -0700299
Matt Mackalld6269542007-07-21 04:37:40 -0700300 /* Attempt to alloc */
301 prev = sp->list.prev;
302 b = slob_page_alloc(sp, size, align);
303 if (!b)
304 continue;
305
306 /* Improve fragment distribution and reduce our average
307 * search time by starting our next search here. (see
308 * Knuth vol 1, sec 2.5, pg 449) */
Matt Mackall20cecba2008-02-04 22:29:37 -0800309 if (prev != slob_list->prev &&
310 slob_list->next != prev->next)
311 list_move_tail(slob_list, prev->next);
Matt Mackalld6269542007-07-21 04:37:40 -0700312 break;
Nick Piggin95b35122007-07-15 23:38:07 -0700313 }
314 spin_unlock_irqrestore(&slob_lock, flags);
315
316 /* Not enough space: must allocate a new page */
317 if (!b) {
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800318 b = slob_new_pages(gfp & ~__GFP_ZERO, 0, node);
Nick Piggin95b35122007-07-15 23:38:07 -0700319 if (!b)
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800320 return NULL;
Christoph Lameterb55682802012-06-13 10:24:54 -0500321 sp = virt_to_page(b);
322 __SetPageSlab(sp);
Nick Piggin95b35122007-07-15 23:38:07 -0700323
324 spin_lock_irqsave(&slob_lock, flags);
325 sp->units = SLOB_UNITS(PAGE_SIZE);
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500326 sp->freelist = b;
Nick Piggin95b35122007-07-15 23:38:07 -0700327 INIT_LIST_HEAD(&sp->list);
328 set_slob(b, SLOB_UNITS(PAGE_SIZE), b + SLOB_UNITS(PAGE_SIZE));
Matt Mackall20cecba2008-02-04 22:29:37 -0800329 set_slob_page_free(sp, slob_list);
Nick Piggin95b35122007-07-15 23:38:07 -0700330 b = slob_page_alloc(sp, size, align);
331 BUG_ON(!b);
332 spin_unlock_irqrestore(&slob_lock, flags);
333 }
Christoph Lameterd07dbea2007-07-17 04:03:23 -0700334 if (unlikely((gfp & __GFP_ZERO) && b))
335 memset(b, 0, size);
Nick Piggin95b35122007-07-15 23:38:07 -0700336 return b;
337}
338
339/*
340 * slob_free: entry point into the slob allocator.
341 */
Matt Mackall10cef602006-01-08 01:01:45 -0800342static void slob_free(void *block, int size)
343{
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500344 struct page *sp;
Nick Piggin95b35122007-07-15 23:38:07 -0700345 slob_t *prev, *next, *b = (slob_t *)block;
346 slobidx_t units;
Matt Mackall10cef602006-01-08 01:01:45 -0800347 unsigned long flags;
Bob Liud602dab2010-07-10 18:05:33 +0800348 struct list_head *slob_list;
Matt Mackall10cef602006-01-08 01:01:45 -0800349
Satyam Sharma2408c552007-10-16 01:24:44 -0700350 if (unlikely(ZERO_OR_NULL_PTR(block)))
Matt Mackall10cef602006-01-08 01:01:45 -0800351 return;
Nick Piggin95b35122007-07-15 23:38:07 -0700352 BUG_ON(!size);
Matt Mackall10cef602006-01-08 01:01:45 -0800353
Christoph Lameterb55682802012-06-13 10:24:54 -0500354 sp = virt_to_page(block);
Nick Piggin95b35122007-07-15 23:38:07 -0700355 units = SLOB_UNITS(size);
Matt Mackall10cef602006-01-08 01:01:45 -0800356
Matt Mackall10cef602006-01-08 01:01:45 -0800357 spin_lock_irqsave(&slob_lock, flags);
Matt Mackall10cef602006-01-08 01:01:45 -0800358
Nick Piggin95b35122007-07-15 23:38:07 -0700359 if (sp->units + units == SLOB_UNITS(PAGE_SIZE)) {
360 /* Go directly to page allocator. Do not pass slob allocator */
361 if (slob_page_free(sp))
362 clear_slob_page_free(sp);
Nick Piggin6fb8f422009-03-16 21:00:28 +1100363 spin_unlock_irqrestore(&slob_lock, flags);
Christoph Lameterb55682802012-06-13 10:24:54 -0500364 __ClearPageSlab(sp);
365 reset_page_mapcount(sp);
Nick Piggin1f0532e2009-05-05 19:13:45 +1000366 slob_free_pages(b, 0);
Nick Piggin6fb8f422009-03-16 21:00:28 +1100367 return;
Nick Piggin95b35122007-07-15 23:38:07 -0700368 }
Matt Mackall10cef602006-01-08 01:01:45 -0800369
Nick Piggin95b35122007-07-15 23:38:07 -0700370 if (!slob_page_free(sp)) {
371 /* This slob page is about to become partially free. Easy! */
372 sp->units = units;
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500373 sp->freelist = b;
Nick Piggin95b35122007-07-15 23:38:07 -0700374 set_slob(b, units,
375 (void *)((unsigned long)(b +
376 SLOB_UNITS(PAGE_SIZE)) & PAGE_MASK));
Bob Liud602dab2010-07-10 18:05:33 +0800377 if (size < SLOB_BREAK1)
378 slob_list = &free_slob_small;
379 else if (size < SLOB_BREAK2)
380 slob_list = &free_slob_medium;
381 else
382 slob_list = &free_slob_large;
383 set_slob_page_free(sp, slob_list);
Nick Piggin95b35122007-07-15 23:38:07 -0700384 goto out;
385 }
Matt Mackall10cef602006-01-08 01:01:45 -0800386
Nick Piggin95b35122007-07-15 23:38:07 -0700387 /*
388 * Otherwise the page is already partially free, so find reinsertion
389 * point.
390 */
391 sp->units += units;
Matt Mackall10cef602006-01-08 01:01:45 -0800392
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500393 if (b < (slob_t *)sp->freelist) {
394 if (b + units == sp->freelist) {
395 units += slob_units(sp->freelist);
396 sp->freelist = slob_next(sp->freelist);
Matt Mackall679299b2008-02-04 22:29:37 -0800397 }
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500398 set_slob(b, units, sp->freelist);
399 sp->freelist = b;
Nick Piggin95b35122007-07-15 23:38:07 -0700400 } else {
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500401 prev = sp->freelist;
Nick Piggin95b35122007-07-15 23:38:07 -0700402 next = slob_next(prev);
403 while (b > next) {
404 prev = next;
405 next = slob_next(prev);
406 }
407
408 if (!slob_last(prev) && b + units == next) {
409 units += slob_units(next);
410 set_slob(b, units, slob_next(next));
411 } else
412 set_slob(b, units, next);
413
414 if (prev + slob_units(prev) == b) {
415 units = slob_units(b) + slob_units(prev);
416 set_slob(prev, units, slob_next(b));
417 } else
418 set_slob(prev, slob_units(prev), b);
419 }
420out:
Matt Mackall10cef602006-01-08 01:01:45 -0800421 spin_unlock_irqrestore(&slob_lock, flags);
422}
423
Nick Piggin95b35122007-07-15 23:38:07 -0700424/*
425 * End of slob allocator proper. Begin kmem_cache_alloc and kmalloc frontend.
426 */
427
Paul Mundt6193a2f2007-07-15 23:38:22 -0700428void *__kmalloc_node(size_t size, gfp_t gfp, int node)
Matt Mackall10cef602006-01-08 01:01:45 -0800429{
Christoph Lameter6cb8f912007-07-17 04:03:22 -0700430 unsigned int *m;
Nick Piggin55394842007-07-15 23:38:09 -0700431 int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300432 void *ret;
Nick Piggin55394842007-07-15 23:38:09 -0700433
Steven Rostedtbd50cfa2011-06-07 07:18:45 -0400434 gfp &= gfp_allowed_mask;
435
Ingo Molnar19cefdf2009-03-15 06:03:11 +0100436 lockdep_trace_alloc(gfp);
Nick Piggincf40bd12009-01-21 08:12:39 +0100437
Nick Piggin55394842007-07-15 23:38:09 -0700438 if (size < PAGE_SIZE - align) {
Christoph Lameter6cb8f912007-07-17 04:03:22 -0700439 if (!size)
440 return ZERO_SIZE_PTR;
441
Paul Mundt6193a2f2007-07-15 23:38:22 -0700442 m = slob_alloc(size + align, gfp, align, node);
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300443
MinChan Kim239f49c2008-05-19 22:12:08 +0900444 if (!m)
445 return NULL;
446 *m = size;
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300447 ret = (void *)m + align;
Nick Piggind87a1332007-07-15 23:38:08 -0700448
Eduard - Gabriel Munteanuca2b84cb2009-03-23 15:12:24 +0200449 trace_kmalloc_node(_RET_IP_, ret,
450 size, size + align, gfp, node);
Nick Piggind87a1332007-07-15 23:38:08 -0700451 } else {
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300452 unsigned int order = get_order(size);
Nick Piggind87a1332007-07-15 23:38:08 -0700453
David Rientjes8df275a2010-08-22 16:16:06 -0700454 if (likely(order))
455 gfp |= __GFP_COMP;
456 ret = slob_new_pages(gfp, order, node);
Nick Piggind87a1332007-07-15 23:38:08 -0700457 if (ret) {
458 struct page *page;
459 page = virt_to_page(ret);
460 page->private = size;
461 }
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300462
Eduard - Gabriel Munteanuca2b84cb2009-03-23 15:12:24 +0200463 trace_kmalloc_node(_RET_IP_, ret,
464 size, PAGE_SIZE << order, gfp, node);
Matt Mackall10cef602006-01-08 01:01:45 -0800465 }
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300466
Catalin Marinas4374e612009-06-11 13:23:17 +0100467 kmemleak_alloc(ret, size, 1, gfp);
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300468 return ret;
Matt Mackall10cef602006-01-08 01:01:45 -0800469}
Paul Mundt6193a2f2007-07-15 23:38:22 -0700470EXPORT_SYMBOL(__kmalloc_node);
Matt Mackall10cef602006-01-08 01:01:45 -0800471
472void kfree(const void *block)
473{
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500474 struct page *sp;
Matt Mackall10cef602006-01-08 01:01:45 -0800475
Pekka Enberg2121db72009-03-25 11:05:57 +0200476 trace_kfree(_RET_IP_, block);
477
Satyam Sharma2408c552007-10-16 01:24:44 -0700478 if (unlikely(ZERO_OR_NULL_PTR(block)))
Matt Mackall10cef602006-01-08 01:01:45 -0800479 return;
Catalin Marinas4374e612009-06-11 13:23:17 +0100480 kmemleak_free(block);
Matt Mackall10cef602006-01-08 01:01:45 -0800481
Christoph Lameterb55682802012-06-13 10:24:54 -0500482 sp = virt_to_page(block);
483 if (PageSlab(sp)) {
Nick Piggin55394842007-07-15 23:38:09 -0700484 int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
485 unsigned int *m = (unsigned int *)(block - align);
486 slob_free(m, *m + align);
Nick Piggind87a1332007-07-15 23:38:08 -0700487 } else
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500488 put_page(sp);
Matt Mackall10cef602006-01-08 01:01:45 -0800489}
Matt Mackall10cef602006-01-08 01:01:45 -0800490EXPORT_SYMBOL(kfree);
491
Nick Piggind87a1332007-07-15 23:38:08 -0700492/* can't use ksize for kmem_cache_alloc memory, only kmalloc */
Pekka Enbergfd76bab2007-05-06 14:48:40 -0700493size_t ksize(const void *block)
Matt Mackall10cef602006-01-08 01:01:45 -0800494{
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500495 struct page *sp;
Matt Mackall10cef602006-01-08 01:01:45 -0800496
Christoph Lameteref8b4522007-10-16 01:24:46 -0700497 BUG_ON(!block);
498 if (unlikely(block == ZERO_SIZE_PTR))
Matt Mackall10cef602006-01-08 01:01:45 -0800499 return 0;
500
Christoph Lameterb55682802012-06-13 10:24:54 -0500501 sp = virt_to_page(block);
502 if (PageSlab(sp)) {
Matt Mackall70096a52008-10-08 14:51:57 -0500503 int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
504 unsigned int *m = (unsigned int *)(block - align);
505 return SLOB_UNITS(*m) * SLOB_UNIT;
506 } else
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500507 return sp->private;
Matt Mackall10cef602006-01-08 01:01:45 -0800508}
Kirill A. Shutemovb1aabec2009-02-10 15:21:44 +0200509EXPORT_SYMBOL(ksize);
Matt Mackall10cef602006-01-08 01:01:45 -0800510
Christoph Lameter039363f2012-07-06 15:25:10 -0500511struct kmem_cache *__kmem_cache_create(const char *name, size_t size,
Alexey Dobriyan51cc5062008-07-25 19:45:34 -0700512 size_t align, unsigned long flags, void (*ctor)(void *))
Matt Mackall10cef602006-01-08 01:01:45 -0800513{
514 struct kmem_cache *c;
515
Yi Li0701a9e2008-04-25 19:49:21 +0300516 c = slob_alloc(sizeof(struct kmem_cache),
Catalin Marinas5e18e2b2008-12-15 13:54:16 -0800517 GFP_KERNEL, ARCH_KMALLOC_MINALIGN, -1);
Matt Mackall10cef602006-01-08 01:01:45 -0800518
519 if (c) {
520 c->name = name;
Christoph Lameter44a8bde2012-07-10 18:31:05 -0500521 c->size = size;
Nick Pigginafc0ced2007-05-16 22:10:49 -0700522 if (flags & SLAB_DESTROY_BY_RCU) {
Nick Pigginafc0ced2007-05-16 22:10:49 -0700523 /* leave room for rcu footer at the end of object */
524 c->size += sizeof(struct slob_rcu);
525 }
526 c->flags = flags;
Matt Mackall10cef602006-01-08 01:01:45 -0800527 c->ctor = ctor;
Matt Mackall10cef602006-01-08 01:01:45 -0800528 /* ignore alignment unless it's forced */
Christoph Lameter5af60832007-05-06 14:49:56 -0700529 c->align = (flags & SLAB_HWCACHE_ALIGN) ? SLOB_ALIGN : 0;
Nick Piggin55394842007-07-15 23:38:09 -0700530 if (c->align < ARCH_SLAB_MINALIGN)
531 c->align = ARCH_SLAB_MINALIGN;
Matt Mackall10cef602006-01-08 01:01:45 -0800532 if (c->align < align)
533 c->align = align;
Matt Mackall10cef602006-01-08 01:01:45 -0800534
Christoph Lameter039363f2012-07-06 15:25:10 -0500535 kmemleak_alloc(c, sizeof(struct kmem_cache), 1, GFP_KERNEL);
Christoph Lameter97d06602012-07-06 15:25:11 -0500536 c->refcount = 1;
Christoph Lameter039363f2012-07-06 15:25:10 -0500537 }
Matt Mackall10cef602006-01-08 01:01:45 -0800538 return c;
539}
Matt Mackall10cef602006-01-08 01:01:45 -0800540
Alexey Dobriyan133d2052006-09-27 01:49:41 -0700541void kmem_cache_destroy(struct kmem_cache *c)
Matt Mackall10cef602006-01-08 01:01:45 -0800542{
Catalin Marinas4374e612009-06-11 13:23:17 +0100543 kmemleak_free(c);
Paul E. McKenney7ed9f7e2009-06-25 12:31:37 -0700544 if (c->flags & SLAB_DESTROY_BY_RCU)
545 rcu_barrier();
Matt Mackall10cef602006-01-08 01:01:45 -0800546 slob_free(c, sizeof(struct kmem_cache));
Matt Mackall10cef602006-01-08 01:01:45 -0800547}
548EXPORT_SYMBOL(kmem_cache_destroy);
549
Paul Mundt6193a2f2007-07-15 23:38:22 -0700550void *kmem_cache_alloc_node(struct kmem_cache *c, gfp_t flags, int node)
Matt Mackall10cef602006-01-08 01:01:45 -0800551{
552 void *b;
553
Steven Rostedtbd50cfa2011-06-07 07:18:45 -0400554 flags &= gfp_allowed_mask;
555
556 lockdep_trace_alloc(flags);
557
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300558 if (c->size < PAGE_SIZE) {
Paul Mundt6193a2f2007-07-15 23:38:22 -0700559 b = slob_alloc(c->size, flags, c->align, node);
Eduard - Gabriel Munteanuca2b84cb2009-03-23 15:12:24 +0200560 trace_kmem_cache_alloc_node(_RET_IP_, b, c->size,
561 SLOB_UNITS(c->size) * SLOB_UNIT,
562 flags, node);
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300563 } else {
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800564 b = slob_new_pages(flags, get_order(c->size), node);
Eduard - Gabriel Munteanuca2b84cb2009-03-23 15:12:24 +0200565 trace_kmem_cache_alloc_node(_RET_IP_, b, c->size,
566 PAGE_SIZE << get_order(c->size),
567 flags, node);
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300568 }
Matt Mackall10cef602006-01-08 01:01:45 -0800569
570 if (c->ctor)
Alexey Dobriyan51cc5062008-07-25 19:45:34 -0700571 c->ctor(b);
Matt Mackall10cef602006-01-08 01:01:45 -0800572
Catalin Marinas4374e612009-06-11 13:23:17 +0100573 kmemleak_alloc_recursive(b, c->size, 1, c->flags, flags);
Matt Mackall10cef602006-01-08 01:01:45 -0800574 return b;
575}
Paul Mundt6193a2f2007-07-15 23:38:22 -0700576EXPORT_SYMBOL(kmem_cache_alloc_node);
Matt Mackall10cef602006-01-08 01:01:45 -0800577
Nick Pigginafc0ced2007-05-16 22:10:49 -0700578static void __kmem_cache_free(void *b, int size)
579{
580 if (size < PAGE_SIZE)
581 slob_free(b, size);
582 else
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800583 slob_free_pages(b, get_order(size));
Nick Pigginafc0ced2007-05-16 22:10:49 -0700584}
585
586static void kmem_rcu_free(struct rcu_head *head)
587{
588 struct slob_rcu *slob_rcu = (struct slob_rcu *)head;
589 void *b = (void *)slob_rcu - (slob_rcu->size - sizeof(struct slob_rcu));
590
591 __kmem_cache_free(b, slob_rcu->size);
592}
593
Matt Mackall10cef602006-01-08 01:01:45 -0800594void kmem_cache_free(struct kmem_cache *c, void *b)
595{
Catalin Marinas4374e612009-06-11 13:23:17 +0100596 kmemleak_free_recursive(b, c->flags);
Nick Pigginafc0ced2007-05-16 22:10:49 -0700597 if (unlikely(c->flags & SLAB_DESTROY_BY_RCU)) {
598 struct slob_rcu *slob_rcu;
599 slob_rcu = b + (c->size - sizeof(struct slob_rcu));
Nick Pigginafc0ced2007-05-16 22:10:49 -0700600 slob_rcu->size = c->size;
601 call_rcu(&slob_rcu->head, kmem_rcu_free);
602 } else {
Nick Pigginafc0ced2007-05-16 22:10:49 -0700603 __kmem_cache_free(b, c->size);
604 }
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300605
Eduard - Gabriel Munteanuca2b84cb2009-03-23 15:12:24 +0200606 trace_kmem_cache_free(_RET_IP_, b);
Matt Mackall10cef602006-01-08 01:01:45 -0800607}
608EXPORT_SYMBOL(kmem_cache_free);
609
610unsigned int kmem_cache_size(struct kmem_cache *c)
611{
612 return c->size;
613}
614EXPORT_SYMBOL(kmem_cache_size);
615
Christoph Lameter2e892f42006-12-13 00:34:23 -0800616int kmem_cache_shrink(struct kmem_cache *d)
617{
618 return 0;
619}
620EXPORT_SYMBOL(kmem_cache_shrink);
621
Dimitri Gorokhovikbcb4ddb2006-12-29 16:48:28 -0800622void __init kmem_cache_init(void)
623{
Christoph Lameter97d06602012-07-06 15:25:11 -0500624 slab_state = UP;
Matt Mackall10cef602006-01-08 01:01:45 -0800625}
Wu Fengguangbbff2e42009-08-06 11:36:25 +0300626
627void __init kmem_cache_init_late(void)
628{
Christoph Lameter97d06602012-07-06 15:25:11 -0500629 slab_state = FULL;
Wu Fengguangbbff2e42009-08-06 11:36:25 +0300630}