blob: a2d4ab32198d85b9773926c27ba7fdd07adfbfe7 [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
49 * provided, alloc_pages_node() with the specified node id is used
50 * 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>
62#include <linux/mm.h>
63#include <linux/cache.h>
64#include <linux/init.h>
65#include <linux/module.h>
Nick Pigginafc0ced2007-05-16 22:10:49 -070066#include <linux/rcupdate.h>
Nick Piggin95b35122007-07-15 23:38:07 -070067#include <linux/list.h>
Frederic Weisbecker36994e52008-12-29 13:42:23 -080068#include <trace/kmemtrace.h>
Nick Piggin95b35122007-07-15 23:38:07 -070069#include <asm/atomic.h>
Matt Mackall10cef602006-01-08 01:01:45 -080070
Nick Piggin95b35122007-07-15 23:38:07 -070071/*
72 * slob_block has a field 'units', which indicates size of block if +ve,
73 * or offset of next block if -ve (in SLOB_UNITs).
74 *
75 * Free blocks of size 1 unit simply contain the offset of the next block.
76 * Those with larger size contain their size in the first SLOB_UNIT of
77 * memory, and the offset of the next free block in the second SLOB_UNIT.
78 */
Nick Piggin55394842007-07-15 23:38:09 -070079#if PAGE_SIZE <= (32767 * 2)
Nick Piggin95b35122007-07-15 23:38:07 -070080typedef s16 slobidx_t;
81#else
82typedef s32 slobidx_t;
83#endif
84
Matt Mackall10cef602006-01-08 01:01:45 -080085struct slob_block {
Nick Piggin95b35122007-07-15 23:38:07 -070086 slobidx_t units;
Nick Piggin55394842007-07-15 23:38:09 -070087};
Matt Mackall10cef602006-01-08 01:01:45 -080088typedef struct slob_block slob_t;
89
Nick Piggin95b35122007-07-15 23:38:07 -070090/*
91 * We use struct page fields to manage some slob allocation aspects,
92 * however to avoid the horrible mess in include/linux/mm_types.h, we'll
93 * just define our own struct page type variant here.
94 */
95struct slob_page {
96 union {
97 struct {
98 unsigned long flags; /* mandatory */
99 atomic_t _count; /* mandatory */
100 slobidx_t units; /* free units left in page */
101 unsigned long pad[2];
102 slob_t *free; /* first free slob_t in page */
103 struct list_head list; /* linked list of free pages */
104 };
105 struct page page;
106 };
107};
108static inline void struct_slob_page_wrong_size(void)
109{ BUILD_BUG_ON(sizeof(struct slob_page) != sizeof(struct page)); }
110
111/*
112 * free_slob_page: call before a slob_page is returned to the page allocator.
113 */
114static inline void free_slob_page(struct slob_page *sp)
115{
116 reset_page_mapcount(&sp->page);
117 sp->page.mapping = NULL;
118}
119
120/*
Matt Mackall20cecba2008-02-04 22:29:37 -0800121 * All partially free slob pages go on these lists.
Nick Piggin95b35122007-07-15 23:38:07 -0700122 */
Matt Mackall20cecba2008-02-04 22:29:37 -0800123#define SLOB_BREAK1 256
124#define SLOB_BREAK2 1024
125static LIST_HEAD(free_slob_small);
126static LIST_HEAD(free_slob_medium);
127static LIST_HEAD(free_slob_large);
Nick Piggin95b35122007-07-15 23:38:07 -0700128
129/*
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800130 * is_slob_page: True for all slob pages (false for bigblock pages)
Nick Piggin95b35122007-07-15 23:38:07 -0700131 */
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800132static inline int is_slob_page(struct slob_page *sp)
Nick Piggin95b35122007-07-15 23:38:07 -0700133{
Andy Whitcroft9023cb72008-07-23 21:27:19 -0700134 return PageSlobPage((struct page *)sp);
Nick Piggin95b35122007-07-15 23:38:07 -0700135}
136
137static inline void set_slob_page(struct slob_page *sp)
138{
Andy Whitcroft9023cb72008-07-23 21:27:19 -0700139 __SetPageSlobPage((struct page *)sp);
Nick Piggin95b35122007-07-15 23:38:07 -0700140}
141
142static inline void clear_slob_page(struct slob_page *sp)
143{
Andy Whitcroft9023cb72008-07-23 21:27:19 -0700144 __ClearPageSlobPage((struct page *)sp);
Nick Piggin95b35122007-07-15 23:38:07 -0700145}
146
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800147static inline struct slob_page *slob_page(const void *addr)
148{
149 return (struct slob_page *)virt_to_page(addr);
150}
151
Nick Piggin95b35122007-07-15 23:38:07 -0700152/*
153 * slob_page_free: true for pages on free_slob_pages list.
154 */
155static inline int slob_page_free(struct slob_page *sp)
156{
Andy Whitcroft9023cb72008-07-23 21:27:19 -0700157 return PageSlobFree((struct page *)sp);
Nick Piggin95b35122007-07-15 23:38:07 -0700158}
159
Matt Mackall20cecba2008-02-04 22:29:37 -0800160static void set_slob_page_free(struct slob_page *sp, struct list_head *list)
Nick Piggin95b35122007-07-15 23:38:07 -0700161{
Matt Mackall20cecba2008-02-04 22:29:37 -0800162 list_add(&sp->list, list);
Andy Whitcroft9023cb72008-07-23 21:27:19 -0700163 __SetPageSlobFree((struct page *)sp);
Nick Piggin95b35122007-07-15 23:38:07 -0700164}
165
166static inline void clear_slob_page_free(struct slob_page *sp)
167{
168 list_del(&sp->list);
Andy Whitcroft9023cb72008-07-23 21:27:19 -0700169 __ClearPageSlobFree((struct page *)sp);
Nick Piggin95b35122007-07-15 23:38:07 -0700170}
171
Matt Mackall10cef602006-01-08 01:01:45 -0800172#define SLOB_UNIT sizeof(slob_t)
173#define SLOB_UNITS(size) (((size) + SLOB_UNIT - 1)/SLOB_UNIT)
174#define SLOB_ALIGN L1_CACHE_BYTES
175
Nick Pigginafc0ced2007-05-16 22:10:49 -0700176/*
177 * struct slob_rcu is inserted at the tail of allocated slob blocks, which
178 * were created with a SLAB_DESTROY_BY_RCU slab. slob_rcu is used to free
179 * the block using call_rcu.
180 */
181struct slob_rcu {
182 struct rcu_head head;
183 int size;
184};
185
Nick Piggin95b35122007-07-15 23:38:07 -0700186/*
187 * slob_lock protects all slob allocator structures.
188 */
Matt Mackall10cef602006-01-08 01:01:45 -0800189static DEFINE_SPINLOCK(slob_lock);
Matt Mackall10cef602006-01-08 01:01:45 -0800190
Nick Piggin95b35122007-07-15 23:38:07 -0700191/*
192 * Encode the given size and next info into a free slob block s.
193 */
194static void set_slob(slob_t *s, slobidx_t size, slob_t *next)
195{
196 slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);
197 slobidx_t offset = next - base;
Dimitri Gorokhovikbcb4ddb2006-12-29 16:48:28 -0800198
Nick Piggin95b35122007-07-15 23:38:07 -0700199 if (size > 1) {
200 s[0].units = size;
201 s[1].units = offset;
202 } else
203 s[0].units = -offset;
204}
Matt Mackall10cef602006-01-08 01:01:45 -0800205
Nick Piggin95b35122007-07-15 23:38:07 -0700206/*
207 * Return the size of a slob block.
208 */
209static slobidx_t slob_units(slob_t *s)
210{
211 if (s->units > 0)
212 return s->units;
213 return 1;
214}
215
216/*
217 * Return the next free slob block pointer after this one.
218 */
219static slob_t *slob_next(slob_t *s)
220{
221 slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);
222 slobidx_t next;
223
224 if (s[0].units < 0)
225 next = -s[0].units;
226 else
227 next = s[1].units;
228 return base+next;
229}
230
231/*
232 * Returns true if s is the last free block in its page.
233 */
234static int slob_last(slob_t *s)
235{
236 return !((unsigned long)slob_next(s) & ~PAGE_MASK);
237}
238
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800239static void *slob_new_pages(gfp_t gfp, int order, int node)
Paul Mundt6193a2f2007-07-15 23:38:22 -0700240{
241 void *page;
242
243#ifdef CONFIG_NUMA
244 if (node != -1)
245 page = alloc_pages_node(node, gfp, order);
246 else
247#endif
248 page = alloc_pages(gfp, order);
249
250 if (!page)
251 return NULL;
252
253 return page_address(page);
254}
255
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800256static void slob_free_pages(void *b, int order)
257{
258 free_pages((unsigned long)b, order);
259}
260
Nick Piggin95b35122007-07-15 23:38:07 -0700261/*
262 * Allocate a slob block within a given slob_page sp.
263 */
264static void *slob_page_alloc(struct slob_page *sp, size_t size, int align)
Matt Mackall10cef602006-01-08 01:01:45 -0800265{
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800266 slob_t *prev, *cur, *aligned = NULL;
Matt Mackall10cef602006-01-08 01:01:45 -0800267 int delta = 0, units = SLOB_UNITS(size);
Matt Mackall10cef602006-01-08 01:01:45 -0800268
Nick Piggin95b35122007-07-15 23:38:07 -0700269 for (prev = NULL, cur = sp->free; ; prev = cur, cur = slob_next(cur)) {
270 slobidx_t avail = slob_units(cur);
271
Matt Mackall10cef602006-01-08 01:01:45 -0800272 if (align) {
273 aligned = (slob_t *)ALIGN((unsigned long)cur, align);
274 delta = aligned - cur;
275 }
Nick Piggin95b35122007-07-15 23:38:07 -0700276 if (avail >= units + delta) { /* room enough? */
277 slob_t *next;
278
Matt Mackall10cef602006-01-08 01:01:45 -0800279 if (delta) { /* need to fragment head to align? */
Nick Piggin95b35122007-07-15 23:38:07 -0700280 next = slob_next(cur);
281 set_slob(aligned, avail - delta, next);
282 set_slob(cur, delta, aligned);
Matt Mackall10cef602006-01-08 01:01:45 -0800283 prev = cur;
284 cur = aligned;
Nick Piggin95b35122007-07-15 23:38:07 -0700285 avail = slob_units(cur);
Matt Mackall10cef602006-01-08 01:01:45 -0800286 }
287
Nick Piggin95b35122007-07-15 23:38:07 -0700288 next = slob_next(cur);
289 if (avail == units) { /* exact fit? unlink. */
290 if (prev)
291 set_slob(prev, slob_units(prev), next);
292 else
293 sp->free = next;
294 } else { /* fragment */
295 if (prev)
296 set_slob(prev, slob_units(prev), cur + units);
297 else
298 sp->free = cur + units;
299 set_slob(cur + units, avail - units, next);
Matt Mackall10cef602006-01-08 01:01:45 -0800300 }
301
Nick Piggin95b35122007-07-15 23:38:07 -0700302 sp->units -= units;
303 if (!sp->units)
304 clear_slob_page_free(sp);
Matt Mackall10cef602006-01-08 01:01:45 -0800305 return cur;
306 }
Nick Piggin95b35122007-07-15 23:38:07 -0700307 if (slob_last(cur))
308 return NULL;
Matt Mackall10cef602006-01-08 01:01:45 -0800309 }
310}
311
Nick Piggin95b35122007-07-15 23:38:07 -0700312/*
313 * slob_alloc: entry point into the slob allocator.
314 */
Paul Mundt6193a2f2007-07-15 23:38:22 -0700315static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
Nick Piggin95b35122007-07-15 23:38:07 -0700316{
317 struct slob_page *sp;
Matt Mackalld6269542007-07-21 04:37:40 -0700318 struct list_head *prev;
Matt Mackall20cecba2008-02-04 22:29:37 -0800319 struct list_head *slob_list;
Nick Piggin95b35122007-07-15 23:38:07 -0700320 slob_t *b = NULL;
321 unsigned long flags;
322
Matt Mackall20cecba2008-02-04 22:29:37 -0800323 if (size < SLOB_BREAK1)
324 slob_list = &free_slob_small;
325 else if (size < SLOB_BREAK2)
326 slob_list = &free_slob_medium;
327 else
328 slob_list = &free_slob_large;
329
Nick Piggin95b35122007-07-15 23:38:07 -0700330 spin_lock_irqsave(&slob_lock, flags);
331 /* Iterate through each partially free page, try to find room */
Matt Mackall20cecba2008-02-04 22:29:37 -0800332 list_for_each_entry(sp, slob_list, list) {
Paul Mundt6193a2f2007-07-15 23:38:22 -0700333#ifdef CONFIG_NUMA
334 /*
335 * If there's a node specification, search for a partial
336 * page with a matching node id in the freelist.
337 */
338 if (node != -1 && page_to_nid(&sp->page) != node)
339 continue;
340#endif
Matt Mackalld6269542007-07-21 04:37:40 -0700341 /* Enough room on this page? */
342 if (sp->units < SLOB_UNITS(size))
343 continue;
Paul Mundt6193a2f2007-07-15 23:38:22 -0700344
Matt Mackalld6269542007-07-21 04:37:40 -0700345 /* Attempt to alloc */
346 prev = sp->list.prev;
347 b = slob_page_alloc(sp, size, align);
348 if (!b)
349 continue;
350
351 /* Improve fragment distribution and reduce our average
352 * search time by starting our next search here. (see
353 * Knuth vol 1, sec 2.5, pg 449) */
Matt Mackall20cecba2008-02-04 22:29:37 -0800354 if (prev != slob_list->prev &&
355 slob_list->next != prev->next)
356 list_move_tail(slob_list, prev->next);
Matt Mackalld6269542007-07-21 04:37:40 -0700357 break;
Nick Piggin95b35122007-07-15 23:38:07 -0700358 }
359 spin_unlock_irqrestore(&slob_lock, flags);
360
361 /* Not enough space: must allocate a new page */
362 if (!b) {
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800363 b = slob_new_pages(gfp & ~__GFP_ZERO, 0, node);
Nick Piggin95b35122007-07-15 23:38:07 -0700364 if (!b)
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800365 return NULL;
366 sp = slob_page(b);
Nick Piggin95b35122007-07-15 23:38:07 -0700367 set_slob_page(sp);
368
369 spin_lock_irqsave(&slob_lock, flags);
370 sp->units = SLOB_UNITS(PAGE_SIZE);
371 sp->free = b;
372 INIT_LIST_HEAD(&sp->list);
373 set_slob(b, SLOB_UNITS(PAGE_SIZE), b + SLOB_UNITS(PAGE_SIZE));
Matt Mackall20cecba2008-02-04 22:29:37 -0800374 set_slob_page_free(sp, slob_list);
Nick Piggin95b35122007-07-15 23:38:07 -0700375 b = slob_page_alloc(sp, size, align);
376 BUG_ON(!b);
377 spin_unlock_irqrestore(&slob_lock, flags);
378 }
Christoph Lameterd07dbea2007-07-17 04:03:23 -0700379 if (unlikely((gfp & __GFP_ZERO) && b))
380 memset(b, 0, size);
Nick Piggin95b35122007-07-15 23:38:07 -0700381 return b;
382}
383
384/*
385 * slob_free: entry point into the slob allocator.
386 */
Matt Mackall10cef602006-01-08 01:01:45 -0800387static void slob_free(void *block, int size)
388{
Nick Piggin95b35122007-07-15 23:38:07 -0700389 struct slob_page *sp;
390 slob_t *prev, *next, *b = (slob_t *)block;
391 slobidx_t units;
Matt Mackall10cef602006-01-08 01:01:45 -0800392 unsigned long flags;
393
Satyam Sharma2408c552007-10-16 01:24:44 -0700394 if (unlikely(ZERO_OR_NULL_PTR(block)))
Matt Mackall10cef602006-01-08 01:01:45 -0800395 return;
Nick Piggin95b35122007-07-15 23:38:07 -0700396 BUG_ON(!size);
Matt Mackall10cef602006-01-08 01:01:45 -0800397
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800398 sp = slob_page(block);
Nick Piggin95b35122007-07-15 23:38:07 -0700399 units = SLOB_UNITS(size);
Matt Mackall10cef602006-01-08 01:01:45 -0800400
Matt Mackall10cef602006-01-08 01:01:45 -0800401 spin_lock_irqsave(&slob_lock, flags);
Matt Mackall10cef602006-01-08 01:01:45 -0800402
Nick Piggin95b35122007-07-15 23:38:07 -0700403 if (sp->units + units == SLOB_UNITS(PAGE_SIZE)) {
404 /* Go directly to page allocator. Do not pass slob allocator */
405 if (slob_page_free(sp))
406 clear_slob_page_free(sp);
Nick Piggin6fb8f422009-03-16 21:00:28 +1100407 spin_unlock_irqrestore(&slob_lock, flags);
Nick Piggin95b35122007-07-15 23:38:07 -0700408 clear_slob_page(sp);
409 free_slob_page(sp);
410 free_page((unsigned long)b);
Nick Piggin6fb8f422009-03-16 21:00:28 +1100411 return;
Nick Piggin95b35122007-07-15 23:38:07 -0700412 }
Matt Mackall10cef602006-01-08 01:01:45 -0800413
Nick Piggin95b35122007-07-15 23:38:07 -0700414 if (!slob_page_free(sp)) {
415 /* This slob page is about to become partially free. Easy! */
416 sp->units = units;
417 sp->free = b;
418 set_slob(b, units,
419 (void *)((unsigned long)(b +
420 SLOB_UNITS(PAGE_SIZE)) & PAGE_MASK));
Matt Mackall20cecba2008-02-04 22:29:37 -0800421 set_slob_page_free(sp, &free_slob_small);
Nick Piggin95b35122007-07-15 23:38:07 -0700422 goto out;
423 }
Matt Mackall10cef602006-01-08 01:01:45 -0800424
Nick Piggin95b35122007-07-15 23:38:07 -0700425 /*
426 * Otherwise the page is already partially free, so find reinsertion
427 * point.
428 */
429 sp->units += units;
Matt Mackall10cef602006-01-08 01:01:45 -0800430
Nick Piggin95b35122007-07-15 23:38:07 -0700431 if (b < sp->free) {
Matt Mackall679299b2008-02-04 22:29:37 -0800432 if (b + units == sp->free) {
433 units += slob_units(sp->free);
434 sp->free = slob_next(sp->free);
435 }
Nick Piggin95b35122007-07-15 23:38:07 -0700436 set_slob(b, units, sp->free);
437 sp->free = b;
438 } else {
439 prev = sp->free;
440 next = slob_next(prev);
441 while (b > next) {
442 prev = next;
443 next = slob_next(prev);
444 }
445
446 if (!slob_last(prev) && b + units == next) {
447 units += slob_units(next);
448 set_slob(b, units, slob_next(next));
449 } else
450 set_slob(b, units, next);
451
452 if (prev + slob_units(prev) == b) {
453 units = slob_units(b) + slob_units(prev);
454 set_slob(prev, units, slob_next(b));
455 } else
456 set_slob(prev, slob_units(prev), b);
457 }
458out:
Matt Mackall10cef602006-01-08 01:01:45 -0800459 spin_unlock_irqrestore(&slob_lock, flags);
460}
461
Nick Piggin95b35122007-07-15 23:38:07 -0700462/*
463 * End of slob allocator proper. Begin kmem_cache_alloc and kmalloc frontend.
464 */
465
Nick Piggin55394842007-07-15 23:38:09 -0700466#ifndef ARCH_KMALLOC_MINALIGN
467#define ARCH_KMALLOC_MINALIGN __alignof__(unsigned long)
468#endif
469
470#ifndef ARCH_SLAB_MINALIGN
471#define ARCH_SLAB_MINALIGN __alignof__(unsigned long)
472#endif
473
Paul Mundt6193a2f2007-07-15 23:38:22 -0700474void *__kmalloc_node(size_t size, gfp_t gfp, int node)
Matt Mackall10cef602006-01-08 01:01:45 -0800475{
Christoph Lameter6cb8f912007-07-17 04:03:22 -0700476 unsigned int *m;
Nick Piggin55394842007-07-15 23:38:09 -0700477 int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300478 void *ret;
Nick Piggin55394842007-07-15 23:38:09 -0700479
Ingo Molnar19cefdf2009-03-15 06:03:11 +0100480 lockdep_trace_alloc(gfp);
Nick Piggincf40bd12009-01-21 08:12:39 +0100481
Nick Piggin55394842007-07-15 23:38:09 -0700482 if (size < PAGE_SIZE - align) {
Christoph Lameter6cb8f912007-07-17 04:03:22 -0700483 if (!size)
484 return ZERO_SIZE_PTR;
485
Paul Mundt6193a2f2007-07-15 23:38:22 -0700486 m = slob_alloc(size + align, gfp, align, node);
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300487
MinChan Kim239f49c2008-05-19 22:12:08 +0900488 if (!m)
489 return NULL;
490 *m = size;
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300491 ret = (void *)m + align;
Nick Piggind87a1332007-07-15 23:38:08 -0700492
Eduard - Gabriel Munteanuca2b84cb2009-03-23 15:12:24 +0200493 trace_kmalloc_node(_RET_IP_, ret,
494 size, size + align, gfp, node);
Nick Piggind87a1332007-07-15 23:38:08 -0700495 } else {
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300496 unsigned int order = get_order(size);
Nick Piggind87a1332007-07-15 23:38:08 -0700497
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800498 ret = slob_new_pages(gfp | __GFP_COMP, get_order(size), node);
Nick Piggind87a1332007-07-15 23:38:08 -0700499 if (ret) {
500 struct page *page;
501 page = virt_to_page(ret);
502 page->private = size;
503 }
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300504
Eduard - Gabriel Munteanuca2b84cb2009-03-23 15:12:24 +0200505 trace_kmalloc_node(_RET_IP_, ret,
506 size, PAGE_SIZE << order, gfp, node);
Matt Mackall10cef602006-01-08 01:01:45 -0800507 }
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300508
509 return ret;
Matt Mackall10cef602006-01-08 01:01:45 -0800510}
Paul Mundt6193a2f2007-07-15 23:38:22 -0700511EXPORT_SYMBOL(__kmalloc_node);
Matt Mackall10cef602006-01-08 01:01:45 -0800512
513void kfree(const void *block)
514{
Nick Piggin95b35122007-07-15 23:38:07 -0700515 struct slob_page *sp;
Matt Mackall10cef602006-01-08 01:01:45 -0800516
Pekka Enberg2121db72009-03-25 11:05:57 +0200517 trace_kfree(_RET_IP_, block);
518
Satyam Sharma2408c552007-10-16 01:24:44 -0700519 if (unlikely(ZERO_OR_NULL_PTR(block)))
Matt Mackall10cef602006-01-08 01:01:45 -0800520 return;
521
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800522 sp = slob_page(block);
523 if (is_slob_page(sp)) {
Nick Piggin55394842007-07-15 23:38:09 -0700524 int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
525 unsigned int *m = (unsigned int *)(block - align);
526 slob_free(m, *m + align);
Nick Piggind87a1332007-07-15 23:38:08 -0700527 } else
528 put_page(&sp->page);
Matt Mackall10cef602006-01-08 01:01:45 -0800529}
Matt Mackall10cef602006-01-08 01:01:45 -0800530EXPORT_SYMBOL(kfree);
531
Nick Piggind87a1332007-07-15 23:38:08 -0700532/* can't use ksize for kmem_cache_alloc memory, only kmalloc */
Pekka Enbergfd76bab2007-05-06 14:48:40 -0700533size_t ksize(const void *block)
Matt Mackall10cef602006-01-08 01:01:45 -0800534{
Nick Piggin95b35122007-07-15 23:38:07 -0700535 struct slob_page *sp;
Matt Mackall10cef602006-01-08 01:01:45 -0800536
Christoph Lameteref8b4522007-10-16 01:24:46 -0700537 BUG_ON(!block);
538 if (unlikely(block == ZERO_SIZE_PTR))
Matt Mackall10cef602006-01-08 01:01:45 -0800539 return 0;
540
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800541 sp = slob_page(block);
542 if (is_slob_page(sp)) {
Matt Mackall70096a52008-10-08 14:51:57 -0500543 int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
544 unsigned int *m = (unsigned int *)(block - align);
545 return SLOB_UNITS(*m) * SLOB_UNIT;
546 } else
Nick Piggind87a1332007-07-15 23:38:08 -0700547 return sp->page.private;
Matt Mackall10cef602006-01-08 01:01:45 -0800548}
Kirill A. Shutemovb1aabec2009-02-10 15:21:44 +0200549EXPORT_SYMBOL(ksize);
Matt Mackall10cef602006-01-08 01:01:45 -0800550
551struct kmem_cache {
552 unsigned int size, align;
Nick Pigginafc0ced2007-05-16 22:10:49 -0700553 unsigned long flags;
Matt Mackall10cef602006-01-08 01:01:45 -0800554 const char *name;
Alexey Dobriyan51cc5062008-07-25 19:45:34 -0700555 void (*ctor)(void *);
Matt Mackall10cef602006-01-08 01:01:45 -0800556};
557
558struct kmem_cache *kmem_cache_create(const char *name, size_t size,
Alexey Dobriyan51cc5062008-07-25 19:45:34 -0700559 size_t align, unsigned long flags, void (*ctor)(void *))
Matt Mackall10cef602006-01-08 01:01:45 -0800560{
561 struct kmem_cache *c;
562
Yi Li0701a9e2008-04-25 19:49:21 +0300563 c = slob_alloc(sizeof(struct kmem_cache),
Catalin Marinas5e18e2b2008-12-15 13:54:16 -0800564 GFP_KERNEL, ARCH_KMALLOC_MINALIGN, -1);
Matt Mackall10cef602006-01-08 01:01:45 -0800565
566 if (c) {
567 c->name = name;
568 c->size = size;
Nick Pigginafc0ced2007-05-16 22:10:49 -0700569 if (flags & SLAB_DESTROY_BY_RCU) {
Nick Pigginafc0ced2007-05-16 22:10:49 -0700570 /* leave room for rcu footer at the end of object */
571 c->size += sizeof(struct slob_rcu);
572 }
573 c->flags = flags;
Matt Mackall10cef602006-01-08 01:01:45 -0800574 c->ctor = ctor;
Matt Mackall10cef602006-01-08 01:01:45 -0800575 /* ignore alignment unless it's forced */
Christoph Lameter5af60832007-05-06 14:49:56 -0700576 c->align = (flags & SLAB_HWCACHE_ALIGN) ? SLOB_ALIGN : 0;
Nick Piggin55394842007-07-15 23:38:09 -0700577 if (c->align < ARCH_SLAB_MINALIGN)
578 c->align = ARCH_SLAB_MINALIGN;
Matt Mackall10cef602006-01-08 01:01:45 -0800579 if (c->align < align)
580 c->align = align;
Akinobu Mitabc0055a2007-05-06 14:49:52 -0700581 } else if (flags & SLAB_PANIC)
582 panic("Cannot create slab cache %s\n", name);
Matt Mackall10cef602006-01-08 01:01:45 -0800583
584 return c;
585}
586EXPORT_SYMBOL(kmem_cache_create);
587
Alexey Dobriyan133d2052006-09-27 01:49:41 -0700588void kmem_cache_destroy(struct kmem_cache *c)
Matt Mackall10cef602006-01-08 01:01:45 -0800589{
590 slob_free(c, sizeof(struct kmem_cache));
Matt Mackall10cef602006-01-08 01:01:45 -0800591}
592EXPORT_SYMBOL(kmem_cache_destroy);
593
Paul Mundt6193a2f2007-07-15 23:38:22 -0700594void *kmem_cache_alloc_node(struct kmem_cache *c, gfp_t flags, int node)
Matt Mackall10cef602006-01-08 01:01:45 -0800595{
596 void *b;
597
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300598 if (c->size < PAGE_SIZE) {
Paul Mundt6193a2f2007-07-15 23:38:22 -0700599 b = slob_alloc(c->size, flags, c->align, node);
Eduard - Gabriel Munteanuca2b84cb2009-03-23 15:12:24 +0200600 trace_kmem_cache_alloc_node(_RET_IP_, b, c->size,
601 SLOB_UNITS(c->size) * SLOB_UNIT,
602 flags, node);
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300603 } else {
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800604 b = slob_new_pages(flags, get_order(c->size), node);
Eduard - Gabriel Munteanuca2b84cb2009-03-23 15:12:24 +0200605 trace_kmem_cache_alloc_node(_RET_IP_, b, c->size,
606 PAGE_SIZE << get_order(c->size),
607 flags, node);
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300608 }
Matt Mackall10cef602006-01-08 01:01:45 -0800609
610 if (c->ctor)
Alexey Dobriyan51cc5062008-07-25 19:45:34 -0700611 c->ctor(b);
Matt Mackall10cef602006-01-08 01:01:45 -0800612
613 return b;
614}
Paul Mundt6193a2f2007-07-15 23:38:22 -0700615EXPORT_SYMBOL(kmem_cache_alloc_node);
Matt Mackall10cef602006-01-08 01:01:45 -0800616
Nick Pigginafc0ced2007-05-16 22:10:49 -0700617static void __kmem_cache_free(void *b, int size)
618{
619 if (size < PAGE_SIZE)
620 slob_free(b, size);
621 else
Américo Wang6e9ed0c2009-01-19 02:00:38 +0800622 slob_free_pages(b, get_order(size));
Nick Pigginafc0ced2007-05-16 22:10:49 -0700623}
624
625static void kmem_rcu_free(struct rcu_head *head)
626{
627 struct slob_rcu *slob_rcu = (struct slob_rcu *)head;
628 void *b = (void *)slob_rcu - (slob_rcu->size - sizeof(struct slob_rcu));
629
630 __kmem_cache_free(b, slob_rcu->size);
631}
632
Matt Mackall10cef602006-01-08 01:01:45 -0800633void kmem_cache_free(struct kmem_cache *c, void *b)
634{
Nick Pigginafc0ced2007-05-16 22:10:49 -0700635 if (unlikely(c->flags & SLAB_DESTROY_BY_RCU)) {
636 struct slob_rcu *slob_rcu;
637 slob_rcu = b + (c->size - sizeof(struct slob_rcu));
638 INIT_RCU_HEAD(&slob_rcu->head);
639 slob_rcu->size = c->size;
640 call_rcu(&slob_rcu->head, kmem_rcu_free);
641 } else {
Nick Pigginafc0ced2007-05-16 22:10:49 -0700642 __kmem_cache_free(b, c->size);
643 }
Eduard - Gabriel Munteanu3eae2cb22008-08-10 20:14:07 +0300644
Eduard - Gabriel Munteanuca2b84cb2009-03-23 15:12:24 +0200645 trace_kmem_cache_free(_RET_IP_, b);
Matt Mackall10cef602006-01-08 01:01:45 -0800646}
647EXPORT_SYMBOL(kmem_cache_free);
648
649unsigned int kmem_cache_size(struct kmem_cache *c)
650{
651 return c->size;
652}
653EXPORT_SYMBOL(kmem_cache_size);
654
655const char *kmem_cache_name(struct kmem_cache *c)
656{
657 return c->name;
658}
659EXPORT_SYMBOL(kmem_cache_name);
660
Christoph Lameter2e892f42006-12-13 00:34:23 -0800661int kmem_cache_shrink(struct kmem_cache *d)
662{
663 return 0;
664}
665EXPORT_SYMBOL(kmem_cache_shrink);
666
Christoph Lameter55935a32006-12-13 00:34:24 -0800667int kmem_ptr_validate(struct kmem_cache *a, const void *b)
Christoph Lameter2e892f42006-12-13 00:34:23 -0800668{
669 return 0;
670}
671
Paul Mundt84a01c22007-07-15 23:38:24 -0700672static unsigned int slob_ready __read_mostly;
673
674int slab_is_available(void)
675{
676 return slob_ready;
677}
678
Dimitri Gorokhovikbcb4ddb2006-12-29 16:48:28 -0800679void __init kmem_cache_init(void)
680{
Paul Mundt84a01c22007-07-15 23:38:24 -0700681 slob_ready = 1;
Matt Mackall10cef602006-01-08 01:01:45 -0800682}