blob: a08e4681fd0d630ff212e299f5b657f71e48c4b0 [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
Ezequiel Garcia90f2cbb2012-09-08 17:47:51 -0300197 if (node != NUMA_NO_NODE)
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 */
Ezequiel Garcia90f2cbb2012-09-08 17:47:51 -0300293 if (node != NUMA_NO_NODE && 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
Ezequiel Garciaf3f74102012-09-08 17:47:53 -0300428static __always_inline void *
429__do_kmalloc_node(size_t size, gfp_t gfp, int node, unsigned long caller)
Matt Mackall10cef602006-01-08 01:01:45 -0800430{
Christoph Lameter6cb8f912007-07-17 04:03:22 -0700431 unsigned int *m;
Nick Piggin55394842007-07-15 23:38:09 -0700432 int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300433 void *ret;
Nick Piggin55394842007-07-15 23:38:09 -0700434
Steven Rostedtbd50cfa2011-06-07 07:18:45 -0400435 gfp &= gfp_allowed_mask;
436
Ingo Molnar19cefdf2009-03-15 06:03:11 +0100437 lockdep_trace_alloc(gfp);
Nick Piggincf40bd12009-01-21 08:12:39 +0100438
Nick Piggin55394842007-07-15 23:38:09 -0700439 if (size < PAGE_SIZE - align) {
Christoph Lameter6cb8f912007-07-17 04:03:22 -0700440 if (!size)
441 return ZERO_SIZE_PTR;
442
Paul Mundt6193a2f2007-07-15 23:38:22 -0700443 m = slob_alloc(size + align, gfp, align, node);
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300444
MinChan Kim239f49c2008-05-19 22:12:08 +0900445 if (!m)
446 return NULL;
447 *m = size;
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300448 ret = (void *)m + align;
Nick Piggind87a1332007-07-15 23:38:08 -0700449
Ezequiel Garciaf3f74102012-09-08 17:47:53 -0300450 trace_kmalloc_node(caller, ret,
Eduard - Gabriel Munteanuca2b84cb2009-03-23 15:12:24 +0200451 size, size + align, gfp, node);
Nick Piggind87a1332007-07-15 23:38:08 -0700452 } else {
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300453 unsigned int order = get_order(size);
Nick Piggind87a1332007-07-15 23:38:08 -0700454
David Rientjes8df275a2010-08-22 16:16:06 -0700455 if (likely(order))
456 gfp |= __GFP_COMP;
457 ret = slob_new_pages(gfp, order, node);
Nick Piggind87a1332007-07-15 23:38:08 -0700458 if (ret) {
459 struct page *page;
460 page = virt_to_page(ret);
461 page->private = size;
462 }
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300463
Ezequiel Garciaf3f74102012-09-08 17:47:53 -0300464 trace_kmalloc_node(caller, ret,
Eduard - Gabriel Munteanuca2b84cb2009-03-23 15:12:24 +0200465 size, PAGE_SIZE << order, gfp, node);
Matt Mackall10cef602006-01-08 01:01:45 -0800466 }
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300467
Catalin Marinas4374e612009-06-11 13:23:17 +0100468 kmemleak_alloc(ret, size, 1, gfp);
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300469 return ret;
Matt Mackall10cef602006-01-08 01:01:45 -0800470}
Ezequiel Garciaf3f74102012-09-08 17:47:53 -0300471
472void *__kmalloc_node(size_t size, gfp_t gfp, int node)
473{
474 return __do_kmalloc_node(size, gfp, node, _RET_IP_);
475}
Paul Mundt6193a2f2007-07-15 23:38:22 -0700476EXPORT_SYMBOL(__kmalloc_node);
Matt Mackall10cef602006-01-08 01:01:45 -0800477
Ezequiel Garciaf3f74102012-09-08 17:47:53 -0300478#ifdef CONFIG_TRACING
479void *__kmalloc_track_caller(size_t size, gfp_t gfp, unsigned long caller)
480{
481 return __do_kmalloc_node(size, gfp, NUMA_NO_NODE, caller);
482}
483
484#ifdef CONFIG_NUMA
David Rientjes82bd5502012-09-25 12:53:51 -0700485void *__kmalloc_node_track_caller(size_t size, gfp_t gfp,
Ezequiel Garciaf3f74102012-09-08 17:47:53 -0300486 int node, unsigned long caller)
487{
488 return __do_kmalloc_node(size, gfp, node, caller);
489}
490#endif
491#endif
492
Matt Mackall10cef602006-01-08 01:01:45 -0800493void kfree(const void *block)
494{
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500495 struct page *sp;
Matt Mackall10cef602006-01-08 01:01:45 -0800496
Pekka Enberg2121db72009-03-25 11:05:57 +0200497 trace_kfree(_RET_IP_, block);
498
Satyam Sharma2408c552007-10-16 01:24:44 -0700499 if (unlikely(ZERO_OR_NULL_PTR(block)))
Matt Mackall10cef602006-01-08 01:01:45 -0800500 return;
Catalin Marinas4374e612009-06-11 13:23:17 +0100501 kmemleak_free(block);
Matt Mackall10cef602006-01-08 01:01:45 -0800502
Christoph Lameterb55682802012-06-13 10:24:54 -0500503 sp = virt_to_page(block);
504 if (PageSlab(sp)) {
Nick Piggin55394842007-07-15 23:38:09 -0700505 int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
506 unsigned int *m = (unsigned int *)(block - align);
507 slob_free(m, *m + align);
Nick Piggind87a1332007-07-15 23:38:08 -0700508 } else
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500509 put_page(sp);
Matt Mackall10cef602006-01-08 01:01:45 -0800510}
Matt Mackall10cef602006-01-08 01:01:45 -0800511EXPORT_SYMBOL(kfree);
512
Nick Piggind87a1332007-07-15 23:38:08 -0700513/* can't use ksize for kmem_cache_alloc memory, only kmalloc */
Pekka Enbergfd76bab2007-05-06 14:48:40 -0700514size_t ksize(const void *block)
Matt Mackall10cef602006-01-08 01:01:45 -0800515{
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500516 struct page *sp;
Matt Mackall10cef602006-01-08 01:01:45 -0800517
Christoph Lameteref8b4522007-10-16 01:24:46 -0700518 BUG_ON(!block);
519 if (unlikely(block == ZERO_SIZE_PTR))
Matt Mackall10cef602006-01-08 01:01:45 -0800520 return 0;
521
Christoph Lameterb55682802012-06-13 10:24:54 -0500522 sp = virt_to_page(block);
523 if (PageSlab(sp)) {
Matt Mackall70096a52008-10-08 14:51:57 -0500524 int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
525 unsigned int *m = (unsigned int *)(block - align);
526 return SLOB_UNITS(*m) * SLOB_UNIT;
527 } else
Christoph Lameterb8c24c42012-06-13 10:24:52 -0500528 return sp->private;
Matt Mackall10cef602006-01-08 01:01:45 -0800529}
Kirill A. Shutemovb1aabec2009-02-10 15:21:44 +0200530EXPORT_SYMBOL(ksize);
Matt Mackall10cef602006-01-08 01:01:45 -0800531
Christoph Lameter8a13a4c2012-09-04 23:18:33 +0000532int __kmem_cache_create(struct kmem_cache *c, unsigned long flags)
Matt Mackall10cef602006-01-08 01:01:45 -0800533{
Christoph Lameter8a13a4c2012-09-04 23:18:33 +0000534 size_t align = c->size;
Matt Mackall10cef602006-01-08 01:01:45 -0800535
Christoph Lameter278b1bb2012-09-05 00:20:34 +0000536 if (flags & SLAB_DESTROY_BY_RCU) {
537 /* leave room for rcu footer at the end of object */
538 c->size += sizeof(struct slob_rcu);
Christoph Lameter039363f2012-07-06 15:25:10 -0500539 }
Christoph Lameter278b1bb2012-09-05 00:20:34 +0000540 c->flags = flags;
Christoph Lameter278b1bb2012-09-05 00:20:34 +0000541 /* ignore alignment unless it's forced */
542 c->align = (flags & SLAB_HWCACHE_ALIGN) ? SLOB_ALIGN : 0;
543 if (c->align < ARCH_SLAB_MINALIGN)
544 c->align = ARCH_SLAB_MINALIGN;
545 if (c->align < align)
546 c->align = align;
Matt Mackall10cef602006-01-08 01:01:45 -0800547
Christoph Lameter278b1bb2012-09-05 00:20:34 +0000548 return 0;
Matt Mackall10cef602006-01-08 01:01:45 -0800549}
Matt Mackall10cef602006-01-08 01:01:45 -0800550
Paul Mundt6193a2f2007-07-15 23:38:22 -0700551void *kmem_cache_alloc_node(struct kmem_cache *c, gfp_t flags, int node)
Matt Mackall10cef602006-01-08 01:01:45 -0800552{
553 void *b;
554
Steven Rostedtbd50cfa2011-06-07 07:18:45 -0400555 flags &= gfp_allowed_mask;
556
557 lockdep_trace_alloc(flags);
558
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300559 if (c->size < PAGE_SIZE) {
Paul Mundt6193a2f2007-07-15 23:38:22 -0700560 b = slob_alloc(c->size, flags, c->align, node);
Eduard - Gabriel Munteanuca2b84cb2009-03-23 15:12:24 +0200561 trace_kmem_cache_alloc_node(_RET_IP_, b, c->size,
562 SLOB_UNITS(c->size) * SLOB_UNIT,
563 flags, node);
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300564 } else {
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800565 b = slob_new_pages(flags, get_order(c->size), node);
Eduard - Gabriel Munteanuca2b84cb2009-03-23 15:12:24 +0200566 trace_kmem_cache_alloc_node(_RET_IP_, b, c->size,
567 PAGE_SIZE << get_order(c->size),
568 flags, node);
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300569 }
Matt Mackall10cef602006-01-08 01:01:45 -0800570
571 if (c->ctor)
Alexey Dobriyan51cc5062008-07-25 19:45:34 -0700572 c->ctor(b);
Matt Mackall10cef602006-01-08 01:01:45 -0800573
Catalin Marinas4374e612009-06-11 13:23:17 +0100574 kmemleak_alloc_recursive(b, c->size, 1, c->flags, flags);
Matt Mackall10cef602006-01-08 01:01:45 -0800575 return b;
576}
Paul Mundt6193a2f2007-07-15 23:38:22 -0700577EXPORT_SYMBOL(kmem_cache_alloc_node);
Matt Mackall10cef602006-01-08 01:01:45 -0800578
Nick Pigginafc0ced2007-05-16 22:10:49 -0700579static void __kmem_cache_free(void *b, int size)
580{
581 if (size < PAGE_SIZE)
582 slob_free(b, size);
583 else
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800584 slob_free_pages(b, get_order(size));
Nick Pigginafc0ced2007-05-16 22:10:49 -0700585}
586
587static void kmem_rcu_free(struct rcu_head *head)
588{
589 struct slob_rcu *slob_rcu = (struct slob_rcu *)head;
590 void *b = (void *)slob_rcu - (slob_rcu->size - sizeof(struct slob_rcu));
591
592 __kmem_cache_free(b, slob_rcu->size);
593}
594
Matt Mackall10cef602006-01-08 01:01:45 -0800595void kmem_cache_free(struct kmem_cache *c, void *b)
596{
Catalin Marinas4374e612009-06-11 13:23:17 +0100597 kmemleak_free_recursive(b, c->flags);
Nick Pigginafc0ced2007-05-16 22:10:49 -0700598 if (unlikely(c->flags & SLAB_DESTROY_BY_RCU)) {
599 struct slob_rcu *slob_rcu;
600 slob_rcu = b + (c->size - sizeof(struct slob_rcu));
Nick Pigginafc0ced2007-05-16 22:10:49 -0700601 slob_rcu->size = c->size;
602 call_rcu(&slob_rcu->head, kmem_rcu_free);
603 } else {
Nick Pigginafc0ced2007-05-16 22:10:49 -0700604 __kmem_cache_free(b, c->size);
605 }
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300606
Eduard - Gabriel Munteanuca2b84cb2009-03-23 15:12:24 +0200607 trace_kmem_cache_free(_RET_IP_, b);
Matt Mackall10cef602006-01-08 01:01:45 -0800608}
609EXPORT_SYMBOL(kmem_cache_free);
610
611unsigned int kmem_cache_size(struct kmem_cache *c)
612{
613 return c->size;
614}
615EXPORT_SYMBOL(kmem_cache_size);
616
Christoph Lameter945cf2b2012-09-04 23:18:33 +0000617int __kmem_cache_shutdown(struct kmem_cache *c)
618{
619 /* No way to check for remaining objects */
620 return 0;
621}
622
Christoph Lameter2e892f42006-12-13 00:34:23 -0800623int kmem_cache_shrink(struct kmem_cache *d)
624{
625 return 0;
626}
627EXPORT_SYMBOL(kmem_cache_shrink);
628
Christoph Lameter9b030cb2012-09-05 00:20:33 +0000629struct kmem_cache kmem_cache_boot = {
630 .name = "kmem_cache",
631 .size = sizeof(struct kmem_cache),
632 .flags = SLAB_PANIC,
633 .align = ARCH_KMALLOC_MINALIGN,
634};
635
Dimitri Gorokhovikbcb4ddb2006-12-29 16:48:28 -0800636void __init kmem_cache_init(void)
637{
Christoph Lameter9b030cb2012-09-05 00:20:33 +0000638 kmem_cache = &kmem_cache_boot;
Christoph Lameter97d06602012-07-06 15:25:11 -0500639 slab_state = UP;
Matt Mackall10cef602006-01-08 01:01:45 -0800640}
Wu Fengguangbbff2e42009-08-06 11:36:25 +0300641
642void __init kmem_cache_init_late(void)
643{
Christoph Lameter97d06602012-07-06 15:25:11 -0500644 slab_state = FULL;
Wu Fengguangbbff2e42009-08-06 11:36:25 +0300645}