2 * SLOB Allocator: Simple List Of Blocks
4 * Matt Mackall <mpm@selenic.com> 12/30/03
8 * The core of SLOB is a traditional K&R style heap allocator, with
9 * support for returning aligned objects. The granularity of this
10 * allocator is 8 bytes on x86, though it's perhaps possible to reduce
11 * this to 4 if it's deemed worth the effort. The slob heap is a
12 * singly-linked list of pages from __get_free_page, grown on demand
13 * and allocation from the heap is currently first-fit.
15 * Above this is an implementation of kmalloc/kfree. Blocks returned
16 * from kmalloc are 8-byte aligned and prepended with a 8-byte header.
17 * If kmalloc is asked for objects of PAGE_SIZE or larger, it calls
18 * __get_free_pages directly so that it can return page-aligned blocks
19 * and keeps a linked list of such pages and their orders. These
20 * objects are detected in kfree() by their page alignment.
22 * SLAB is emulated on top of SLOB by simply calling constructors and
23 * destructors for every SLAB allocation. Objects are returned with
24 * the 8-byte alignment unless the SLAB_MUST_HWCACHE_ALIGN flag is
25 * set, in which case the low-level allocator will fragment blocks to
26 * create the proper alignment. Again, objects of page-size or greater
27 * are allocated by calling __get_free_pages. As SLAB objects know
28 * their size, no separate size bookkeeping is necessary and there is
29 * essentially no allocation space overhead.
32 #include <linux/slab.h>
34 #include <linux/cache.h>
35 #include <linux/init.h>
36 #include <linux/module.h>
37 #include <linux/timer.h>
41 struct slob_block
*next
;
43 typedef struct slob_block slob_t
;
45 #define SLOB_UNIT sizeof(slob_t)
46 #define SLOB_UNITS(size) (((size) + SLOB_UNIT - 1)/SLOB_UNIT)
47 #define SLOB_ALIGN L1_CACHE_BYTES
52 struct bigblock
*next
;
54 typedef struct bigblock bigblock_t
;
56 static slob_t arena
= { .next
= &arena
, .units
= 1 };
57 static slob_t
*slobfree
= &arena
;
58 static bigblock_t
*bigblocks
;
59 static DEFINE_SPINLOCK(slob_lock
);
60 static DEFINE_SPINLOCK(block_lock
);
62 static void slob_free(void *b
, int size
);
63 static void slob_timer_cbk(void);
66 static void *slob_alloc(size_t size
, gfp_t gfp
, int align
)
68 slob_t
*prev
, *cur
, *aligned
= 0;
69 int delta
= 0, units
= SLOB_UNITS(size
);
72 spin_lock_irqsave(&slob_lock
, flags
);
74 for (cur
= prev
->next
; ; prev
= cur
, cur
= cur
->next
) {
76 aligned
= (slob_t
*)ALIGN((unsigned long)cur
, align
);
77 delta
= aligned
- cur
;
79 if (cur
->units
>= units
+ delta
) { /* room enough? */
80 if (delta
) { /* need to fragment head to align? */
81 aligned
->units
= cur
->units
- delta
;
82 aligned
->next
= cur
->next
;
89 if (cur
->units
== units
) /* exact fit? */
90 prev
->next
= cur
->next
; /* unlink */
92 prev
->next
= cur
+ units
;
93 prev
->next
->units
= cur
->units
- units
;
94 prev
->next
->next
= cur
->next
;
99 spin_unlock_irqrestore(&slob_lock
, flags
);
102 if (cur
== slobfree
) {
103 spin_unlock_irqrestore(&slob_lock
, flags
);
105 if (size
== PAGE_SIZE
) /* trying to shrink arena? */
108 cur
= (slob_t
*)__get_free_page(gfp
);
112 slob_free(cur
, PAGE_SIZE
);
113 spin_lock_irqsave(&slob_lock
, flags
);
119 static void slob_free(void *block
, int size
)
121 slob_t
*cur
, *b
= (slob_t
*)block
;
128 b
->units
= SLOB_UNITS(size
);
130 /* Find reinsertion point */
131 spin_lock_irqsave(&slob_lock
, flags
);
132 for (cur
= slobfree
; !(b
> cur
&& b
< cur
->next
); cur
= cur
->next
)
133 if (cur
>= cur
->next
&& (b
> cur
|| b
< cur
->next
))
136 if (b
+ b
->units
== cur
->next
) {
137 b
->units
+= cur
->next
->units
;
138 b
->next
= cur
->next
->next
;
142 if (cur
+ cur
->units
== b
) {
143 cur
->units
+= b
->units
;
150 spin_unlock_irqrestore(&slob_lock
, flags
);
153 static int FASTCALL(find_order(int size
));
154 static int fastcall
find_order(int size
)
157 for ( ; size
> 4096 ; size
>>=1)
162 void *__kmalloc(size_t size
, gfp_t gfp
)
168 if (size
< PAGE_SIZE
- SLOB_UNIT
) {
169 m
= slob_alloc(size
+ SLOB_UNIT
, gfp
, 0);
170 return m
? (void *)(m
+ 1) : 0;
173 bb
= slob_alloc(sizeof(bigblock_t
), gfp
, 0);
177 bb
->order
= find_order(size
);
178 bb
->pages
= (void *)__get_free_pages(gfp
, bb
->order
);
181 spin_lock_irqsave(&block_lock
, flags
);
182 bb
->next
= bigblocks
;
184 spin_unlock_irqrestore(&block_lock
, flags
);
188 slob_free(bb
, sizeof(bigblock_t
));
191 EXPORT_SYMBOL(__kmalloc
);
194 * krealloc - reallocate memory. The contents will remain unchanged.
196 * @p: object to reallocate memory for.
197 * @new_size: how many bytes of memory are required.
198 * @flags: the type of memory to allocate.
200 * The contents of the object pointed to are preserved up to the
201 * lesser of the new and old sizes. If @p is %NULL, krealloc()
202 * behaves exactly like kmalloc(). If @size is 0 and @p is not a
203 * %NULL pointer, the object pointed to is freed.
205 void *krealloc(const void *p
, size_t new_size
, gfp_t flags
)
210 return kmalloc_track_caller(new_size
, flags
);
212 if (unlikely(!new_size
)) {
217 ret
= kmalloc_track_caller(new_size
, flags
);
219 memcpy(ret
, p
, min(new_size
, ksize(p
)));
224 EXPORT_SYMBOL(krealloc
);
226 void kfree(const void *block
)
228 bigblock_t
*bb
, **last
= &bigblocks
;
234 if (!((unsigned long)block
& (PAGE_SIZE
-1))) {
235 /* might be on the big block list */
236 spin_lock_irqsave(&block_lock
, flags
);
237 for (bb
= bigblocks
; bb
; last
= &bb
->next
, bb
= bb
->next
) {
238 if (bb
->pages
== block
) {
240 spin_unlock_irqrestore(&block_lock
, flags
);
241 free_pages((unsigned long)block
, bb
->order
);
242 slob_free(bb
, sizeof(bigblock_t
));
246 spin_unlock_irqrestore(&block_lock
, flags
);
249 slob_free((slob_t
*)block
- 1, 0);
253 EXPORT_SYMBOL(kfree
);
255 size_t ksize(const void *block
)
263 if (!((unsigned long)block
& (PAGE_SIZE
-1))) {
264 spin_lock_irqsave(&block_lock
, flags
);
265 for (bb
= bigblocks
; bb
; bb
= bb
->next
)
266 if (bb
->pages
== block
) {
267 spin_unlock_irqrestore(&slob_lock
, flags
);
268 return PAGE_SIZE
<< bb
->order
;
270 spin_unlock_irqrestore(&block_lock
, flags
);
273 return ((slob_t
*)block
- 1)->units
* SLOB_UNIT
;
277 unsigned int size
, align
;
279 void (*ctor
)(void *, struct kmem_cache
*, unsigned long);
280 void (*dtor
)(void *, struct kmem_cache
*, unsigned long);
283 struct kmem_cache
*kmem_cache_create(const char *name
, size_t size
,
284 size_t align
, unsigned long flags
,
285 void (*ctor
)(void*, struct kmem_cache
*, unsigned long),
286 void (*dtor
)(void*, struct kmem_cache
*, unsigned long))
288 struct kmem_cache
*c
;
290 c
= slob_alloc(sizeof(struct kmem_cache
), flags
, 0);
297 /* ignore alignment unless it's forced */
298 c
->align
= (flags
& SLAB_MUST_HWCACHE_ALIGN
) ? SLOB_ALIGN
: 0;
299 if (c
->align
< align
)
305 EXPORT_SYMBOL(kmem_cache_create
);
307 void kmem_cache_destroy(struct kmem_cache
*c
)
309 slob_free(c
, sizeof(struct kmem_cache
));
311 EXPORT_SYMBOL(kmem_cache_destroy
);
313 void *kmem_cache_alloc(struct kmem_cache
*c
, gfp_t flags
)
317 if (c
->size
< PAGE_SIZE
)
318 b
= slob_alloc(c
->size
, flags
, c
->align
);
320 b
= (void *)__get_free_pages(flags
, find_order(c
->size
));
323 c
->ctor(b
, c
, SLAB_CTOR_CONSTRUCTOR
);
327 EXPORT_SYMBOL(kmem_cache_alloc
);
329 void *kmem_cache_zalloc(struct kmem_cache
*c
, gfp_t flags
)
331 void *ret
= kmem_cache_alloc(c
, flags
);
333 memset(ret
, 0, c
->size
);
337 EXPORT_SYMBOL(kmem_cache_zalloc
);
339 void kmem_cache_free(struct kmem_cache
*c
, void *b
)
344 if (c
->size
< PAGE_SIZE
)
345 slob_free(b
, c
->size
);
347 free_pages((unsigned long)b
, find_order(c
->size
));
349 EXPORT_SYMBOL(kmem_cache_free
);
351 unsigned int kmem_cache_size(struct kmem_cache
*c
)
355 EXPORT_SYMBOL(kmem_cache_size
);
357 const char *kmem_cache_name(struct kmem_cache
*c
)
361 EXPORT_SYMBOL(kmem_cache_name
);
363 static struct timer_list slob_timer
= TIMER_INITIALIZER(
364 (void (*)(unsigned long))slob_timer_cbk
, 0, 0);
366 int kmem_cache_shrink(struct kmem_cache
*d
)
370 EXPORT_SYMBOL(kmem_cache_shrink
);
372 int kmem_ptr_validate(struct kmem_cache
*a
, const void *b
)
377 void __init
kmem_cache_init(void)
382 static void slob_timer_cbk(void)
384 void *p
= slob_alloc(PAGE_SIZE
, 0, PAGE_SIZE
-1);
387 free_page((unsigned long)p
);
389 mod_timer(&slob_timer
, jiffies
+ HZ
);