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_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 void *__kmalloc(size_t size
, gfp_t gfp
)
159 if (size
< PAGE_SIZE
- SLOB_UNIT
) {
160 m
= slob_alloc(size
+ SLOB_UNIT
, gfp
, 0);
161 return m
? (void *)(m
+ 1) : 0;
164 bb
= slob_alloc(sizeof(bigblock_t
), gfp
, 0);
168 bb
->order
= get_order(size
);
169 bb
->pages
= (void *)__get_free_pages(gfp
, bb
->order
);
172 spin_lock_irqsave(&block_lock
, flags
);
173 bb
->next
= bigblocks
;
175 spin_unlock_irqrestore(&block_lock
, flags
);
179 slob_free(bb
, sizeof(bigblock_t
));
182 EXPORT_SYMBOL(__kmalloc
);
185 * krealloc - reallocate memory. The contents will remain unchanged.
187 * @p: object to reallocate memory for.
188 * @new_size: how many bytes of memory are required.
189 * @flags: the type of memory to allocate.
191 * The contents of the object pointed to are preserved up to the
192 * lesser of the new and old sizes. If @p is %NULL, krealloc()
193 * behaves exactly like kmalloc(). If @size is 0 and @p is not a
194 * %NULL pointer, the object pointed to is freed.
196 void *krealloc(const void *p
, size_t new_size
, gfp_t flags
)
201 return kmalloc_track_caller(new_size
, flags
);
203 if (unlikely(!new_size
)) {
208 ret
= kmalloc_track_caller(new_size
, flags
);
210 memcpy(ret
, p
, min(new_size
, ksize(p
)));
215 EXPORT_SYMBOL(krealloc
);
217 void kfree(const void *block
)
219 bigblock_t
*bb
, **last
= &bigblocks
;
225 if (!((unsigned long)block
& (PAGE_SIZE
-1))) {
226 /* might be on the big block list */
227 spin_lock_irqsave(&block_lock
, flags
);
228 for (bb
= bigblocks
; bb
; last
= &bb
->next
, bb
= bb
->next
) {
229 if (bb
->pages
== block
) {
231 spin_unlock_irqrestore(&block_lock
, flags
);
232 free_pages((unsigned long)block
, bb
->order
);
233 slob_free(bb
, sizeof(bigblock_t
));
237 spin_unlock_irqrestore(&block_lock
, flags
);
240 slob_free((slob_t
*)block
- 1, 0);
244 EXPORT_SYMBOL(kfree
);
246 size_t ksize(const void *block
)
254 if (!((unsigned long)block
& (PAGE_SIZE
-1))) {
255 spin_lock_irqsave(&block_lock
, flags
);
256 for (bb
= bigblocks
; bb
; bb
= bb
->next
)
257 if (bb
->pages
== block
) {
258 spin_unlock_irqrestore(&slob_lock
, flags
);
259 return PAGE_SIZE
<< bb
->order
;
261 spin_unlock_irqrestore(&block_lock
, flags
);
264 return ((slob_t
*)block
- 1)->units
* SLOB_UNIT
;
268 unsigned int size
, align
;
270 void (*ctor
)(void *, struct kmem_cache
*, unsigned long);
271 void (*dtor
)(void *, struct kmem_cache
*, unsigned long);
274 struct kmem_cache
*kmem_cache_create(const char *name
, size_t size
,
275 size_t align
, unsigned long flags
,
276 void (*ctor
)(void*, struct kmem_cache
*, unsigned long),
277 void (*dtor
)(void*, struct kmem_cache
*, unsigned long))
279 struct kmem_cache
*c
;
281 c
= slob_alloc(sizeof(struct kmem_cache
), flags
, 0);
288 /* ignore alignment unless it's forced */
289 c
->align
= (flags
& SLAB_HWCACHE_ALIGN
) ? SLOB_ALIGN
: 0;
290 if (c
->align
< align
)
292 } else if (flags
& SLAB_PANIC
)
293 panic("Cannot create slab cache %s\n", name
);
297 EXPORT_SYMBOL(kmem_cache_create
);
299 void kmem_cache_destroy(struct kmem_cache
*c
)
301 slob_free(c
, sizeof(struct kmem_cache
));
303 EXPORT_SYMBOL(kmem_cache_destroy
);
305 void *kmem_cache_alloc(struct kmem_cache
*c
, gfp_t flags
)
309 if (c
->size
< PAGE_SIZE
)
310 b
= slob_alloc(c
->size
, flags
, c
->align
);
312 b
= (void *)__get_free_pages(flags
, get_order(c
->size
));
315 c
->ctor(b
, c
, SLAB_CTOR_CONSTRUCTOR
);
319 EXPORT_SYMBOL(kmem_cache_alloc
);
321 void *kmem_cache_zalloc(struct kmem_cache
*c
, gfp_t flags
)
323 void *ret
= kmem_cache_alloc(c
, flags
);
325 memset(ret
, 0, c
->size
);
329 EXPORT_SYMBOL(kmem_cache_zalloc
);
331 void kmem_cache_free(struct kmem_cache
*c
, void *b
)
336 if (c
->size
< PAGE_SIZE
)
337 slob_free(b
, c
->size
);
339 free_pages((unsigned long)b
, get_order(c
->size
));
341 EXPORT_SYMBOL(kmem_cache_free
);
343 unsigned int kmem_cache_size(struct kmem_cache
*c
)
347 EXPORT_SYMBOL(kmem_cache_size
);
349 const char *kmem_cache_name(struct kmem_cache
*c
)
353 EXPORT_SYMBOL(kmem_cache_name
);
355 static struct timer_list slob_timer
= TIMER_INITIALIZER(
356 (void (*)(unsigned long))slob_timer_cbk
, 0, 0);
358 int kmem_cache_shrink(struct kmem_cache
*d
)
362 EXPORT_SYMBOL(kmem_cache_shrink
);
364 int kmem_ptr_validate(struct kmem_cache
*a
, const void *b
)
369 void __init
kmem_cache_init(void)
374 static void slob_timer_cbk(void)
376 void *p
= slob_alloc(PAGE_SIZE
, 0, PAGE_SIZE
-1);
379 free_page((unsigned long)p
);
381 mod_timer(&slob_timer
, jiffies
+ HZ
);
This page took 0.037803 seconds and 5 git commands to generate.