]>
git.proxmox.com Git - mirror_ubuntu-eoan-kernel.git/blob - mm/slob.c
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
);
193 void kfree(const void *block
)
195 bigblock_t
*bb
, **last
= &bigblocks
;
201 if (!((unsigned long)block
& (PAGE_SIZE
-1))) {
202 /* might be on the big block list */
203 spin_lock_irqsave(&block_lock
, flags
);
204 for (bb
= bigblocks
; bb
; last
= &bb
->next
, bb
= bb
->next
) {
205 if (bb
->pages
== block
) {
207 spin_unlock_irqrestore(&block_lock
, flags
);
208 free_pages((unsigned long)block
, bb
->order
);
209 slob_free(bb
, sizeof(bigblock_t
));
213 spin_unlock_irqrestore(&block_lock
, flags
);
216 slob_free((slob_t
*)block
- 1, 0);
220 EXPORT_SYMBOL(kfree
);
222 unsigned int ksize(const void *block
)
230 if (!((unsigned long)block
& (PAGE_SIZE
-1))) {
231 spin_lock_irqsave(&block_lock
, flags
);
232 for (bb
= bigblocks
; bb
; bb
= bb
->next
)
233 if (bb
->pages
== block
) {
234 spin_unlock_irqrestore(&slob_lock
, flags
);
235 return PAGE_SIZE
<< bb
->order
;
237 spin_unlock_irqrestore(&block_lock
, flags
);
240 return ((slob_t
*)block
- 1)->units
* SLOB_UNIT
;
244 unsigned int size
, align
;
246 void (*ctor
)(void *, struct kmem_cache
*, unsigned long);
247 void (*dtor
)(void *, struct kmem_cache
*, unsigned long);
250 struct kmem_cache
*kmem_cache_create(const char *name
, size_t size
,
251 size_t align
, unsigned long flags
,
252 void (*ctor
)(void*, struct kmem_cache
*, unsigned long),
253 void (*dtor
)(void*, struct kmem_cache
*, unsigned long))
255 struct kmem_cache
*c
;
257 c
= slob_alloc(sizeof(struct kmem_cache
), flags
, 0);
264 /* ignore alignment unless it's forced */
265 c
->align
= (flags
& SLAB_MUST_HWCACHE_ALIGN
) ? SLOB_ALIGN
: 0;
266 if (c
->align
< align
)
272 EXPORT_SYMBOL(kmem_cache_create
);
274 void kmem_cache_destroy(struct kmem_cache
*c
)
276 slob_free(c
, sizeof(struct kmem_cache
));
278 EXPORT_SYMBOL(kmem_cache_destroy
);
280 void *kmem_cache_alloc(struct kmem_cache
*c
, gfp_t flags
)
284 if (c
->size
< PAGE_SIZE
)
285 b
= slob_alloc(c
->size
, flags
, c
->align
);
287 b
= (void *)__get_free_pages(flags
, find_order(c
->size
));
290 c
->ctor(b
, c
, SLAB_CTOR_CONSTRUCTOR
);
294 EXPORT_SYMBOL(kmem_cache_alloc
);
296 void *kmem_cache_zalloc(struct kmem_cache
*c
, gfp_t flags
)
298 void *ret
= kmem_cache_alloc(c
, flags
);
300 memset(ret
, 0, c
->size
);
304 EXPORT_SYMBOL(kmem_cache_zalloc
);
306 void kmem_cache_free(struct kmem_cache
*c
, void *b
)
311 if (c
->size
< PAGE_SIZE
)
312 slob_free(b
, c
->size
);
314 free_pages((unsigned long)b
, find_order(c
->size
));
316 EXPORT_SYMBOL(kmem_cache_free
);
318 unsigned int kmem_cache_size(struct kmem_cache
*c
)
322 EXPORT_SYMBOL(kmem_cache_size
);
324 const char *kmem_cache_name(struct kmem_cache
*c
)
328 EXPORT_SYMBOL(kmem_cache_name
);
330 static struct timer_list slob_timer
= TIMER_INITIALIZER(
331 (void (*)(unsigned long))slob_timer_cbk
, 0, 0);
333 int kmem_cache_shrink(struct kmem_cache
*d
)
337 EXPORT_SYMBOL(kmem_cache_shrink
);
339 int kmem_ptr_validate(struct kmem_cache
*a
, const void *b
)
344 void __init
kmem_cache_init(void)
349 static void slob_timer_cbk(void)
351 void *p
= slob_alloc(PAGE_SIZE
, 0, PAGE_SIZE
-1);
354 free_page((unsigned long)p
);
356 mod_timer(&slob_timer
, jiffies
+ HZ
);