1 // SPDX-License-Identifier: GPL-2.0
3 * SLOB Allocator: Simple List Of Blocks
5 * Matt Mackall <mpm@selenic.com> 12/30/03
7 * NUMA support by Paul Mundt, 2007.
11 * The core of SLOB is a traditional K&R style heap allocator, with
12 * support for returning aligned objects. The granularity of this
13 * allocator is as little as 2 bytes, however typically most architectures
14 * will require 4 bytes on 32-bit and 8 bytes on 64-bit.
16 * The slob heap is a set of linked list of pages from alloc_pages(),
17 * and within each page, there is a singly-linked list of free blocks
18 * (slob_t). The heap is grown on demand. To reduce fragmentation,
19 * heap pages are segregated into three lists, with objects less than
20 * 256 bytes, objects less than 1024 bytes, and all other objects.
22 * Allocation from heap involves first searching for a page with
23 * sufficient free blocks (using a next-fit-like approach) followed by
24 * a first-fit scan of the page. Deallocation inserts objects back
25 * into the free list in address order, so this is effectively an
26 * address-ordered first fit.
28 * Above this is an implementation of kmalloc/kfree. Blocks returned
29 * from kmalloc are prepended with a 4-byte header with the kmalloc size.
30 * If kmalloc is asked for objects of PAGE_SIZE or larger, it calls
31 * alloc_pages() directly, allocating compound pages so the page order
32 * does not have to be separately tracked.
33 * These objects are detected in kfree() because PageSlab()
36 * SLAB is emulated on top of SLOB by simply calling constructors and
37 * 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
41 * calling alloc_pages(). As SLAB objects know their size, no separate
42 * size bookkeeping is necessary and there is essentially no allocation
43 * space overhead, and compound pages aren't needed for multi-page
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().
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.
60 #include <linux/kernel.h>
61 #include <linux/slab.h>
64 #include <linux/swap.h> /* struct reclaim_state */
65 #include <linux/cache.h>
66 #include <linux/init.h>
67 #include <linux/export.h>
68 #include <linux/rcupdate.h>
69 #include <linux/list.h>
70 #include <linux/kmemleak.h>
72 #include <trace/events/kmem.h>
74 #include <linux/atomic.h>
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).
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.
85 #if PAGE_SIZE <= (32767 * 2)
86 typedef s16 slobidx_t
;
88 typedef s32 slobidx_t
;
94 typedef struct slob_block slob_t
;
97 * All partially free slob pages go on these lists.
99 #define SLOB_BREAK1 256
100 #define SLOB_BREAK2 1024
101 static LIST_HEAD(free_slob_small
);
102 static LIST_HEAD(free_slob_medium
);
103 static LIST_HEAD(free_slob_large
);
106 * slob_page_free: true for pages on free_slob_pages list.
108 static inline int slob_page_free(struct page
*sp
)
110 return PageSlobFree(sp
);
113 static void set_slob_page_free(struct page
*sp
, struct list_head
*list
)
115 list_add(&sp
->lru
, list
);
116 __SetPageSlobFree(sp
);
119 static inline void clear_slob_page_free(struct page
*sp
)
122 __ClearPageSlobFree(sp
);
125 #define SLOB_UNIT sizeof(slob_t)
126 #define SLOB_UNITS(size) DIV_ROUND_UP(size, SLOB_UNIT)
129 * struct slob_rcu is inserted at the tail of allocated slob blocks, which
130 * were created with a SLAB_TYPESAFE_BY_RCU slab. slob_rcu is used to free
131 * the block using call_rcu.
134 struct rcu_head head
;
139 * slob_lock protects all slob allocator structures.
141 static DEFINE_SPINLOCK(slob_lock
);
144 * Encode the given size and next info into a free slob block s.
146 static void set_slob(slob_t
*s
, slobidx_t size
, slob_t
*next
)
148 slob_t
*base
= (slob_t
*)((unsigned long)s
& PAGE_MASK
);
149 slobidx_t offset
= next
- base
;
155 s
[0].units
= -offset
;
159 * Return the size of a slob block.
161 static slobidx_t
slob_units(slob_t
*s
)
169 * Return the next free slob block pointer after this one.
171 static slob_t
*slob_next(slob_t
*s
)
173 slob_t
*base
= (slob_t
*)((unsigned long)s
& PAGE_MASK
);
184 * Returns true if s is the last free block in its page.
186 static int slob_last(slob_t
*s
)
188 return !((unsigned long)slob_next(s
) & ~PAGE_MASK
);
191 static void *slob_new_pages(gfp_t gfp
, int order
, int node
)
196 if (node
!= NUMA_NO_NODE
)
197 page
= __alloc_pages_node(node
, gfp
, order
);
200 page
= alloc_pages(gfp
, order
);
205 return page_address(page
);
208 static void slob_free_pages(void *b
, int order
)
210 if (current
->reclaim_state
)
211 current
->reclaim_state
->reclaimed_slab
+= 1 << order
;
212 free_pages((unsigned long)b
, order
);
216 * Allocate a slob block within a given slob_page sp.
218 static void *slob_page_alloc(struct page
*sp
, size_t size
, int align
)
220 slob_t
*prev
, *cur
, *aligned
= NULL
;
221 int delta
= 0, units
= SLOB_UNITS(size
);
223 for (prev
= NULL
, cur
= sp
->freelist
; ; prev
= cur
, cur
= slob_next(cur
)) {
224 slobidx_t avail
= slob_units(cur
);
227 aligned
= (slob_t
*)ALIGN((unsigned long)cur
, align
);
228 delta
= aligned
- cur
;
230 if (avail
>= units
+ delta
) { /* room enough? */
233 if (delta
) { /* need to fragment head to align? */
234 next
= slob_next(cur
);
235 set_slob(aligned
, avail
- delta
, next
);
236 set_slob(cur
, delta
, aligned
);
239 avail
= slob_units(cur
);
242 next
= slob_next(cur
);
243 if (avail
== units
) { /* exact fit? unlink. */
245 set_slob(prev
, slob_units(prev
), next
);
248 } else { /* fragment */
250 set_slob(prev
, slob_units(prev
), cur
+ units
);
252 sp
->freelist
= cur
+ units
;
253 set_slob(cur
+ units
, avail
- units
, next
);
258 clear_slob_page_free(sp
);
267 * slob_alloc: entry point into the slob allocator.
269 static void *slob_alloc(size_t size
, gfp_t gfp
, int align
, int node
)
272 struct list_head
*prev
;
273 struct list_head
*slob_list
;
277 if (size
< SLOB_BREAK1
)
278 slob_list
= &free_slob_small
;
279 else if (size
< SLOB_BREAK2
)
280 slob_list
= &free_slob_medium
;
282 slob_list
= &free_slob_large
;
284 spin_lock_irqsave(&slob_lock
, flags
);
285 /* Iterate through each partially free page, try to find room */
286 list_for_each_entry(sp
, slob_list
, lru
) {
289 * If there's a node specification, search for a partial
290 * page with a matching node id in the freelist.
292 if (node
!= NUMA_NO_NODE
&& page_to_nid(sp
) != node
)
295 /* Enough room on this page? */
296 if (sp
->units
< SLOB_UNITS(size
))
299 /* Attempt to alloc */
301 b
= slob_page_alloc(sp
, size
, align
);
305 /* Improve fragment distribution and reduce our average
306 * search time by starting our next search here. (see
307 * Knuth vol 1, sec 2.5, pg 449) */
308 if (prev
!= slob_list
->prev
&&
309 slob_list
->next
!= prev
->next
)
310 list_move_tail(slob_list
, prev
->next
);
313 spin_unlock_irqrestore(&slob_lock
, flags
);
315 /* Not enough space: must allocate a new page */
317 b
= slob_new_pages(gfp
& ~__GFP_ZERO
, 0, node
);
320 sp
= virt_to_page(b
);
323 spin_lock_irqsave(&slob_lock
, flags
);
324 sp
->units
= SLOB_UNITS(PAGE_SIZE
);
326 INIT_LIST_HEAD(&sp
->lru
);
327 set_slob(b
, SLOB_UNITS(PAGE_SIZE
), b
+ SLOB_UNITS(PAGE_SIZE
));
328 set_slob_page_free(sp
, slob_list
);
329 b
= slob_page_alloc(sp
, size
, align
);
331 spin_unlock_irqrestore(&slob_lock
, flags
);
333 if (unlikely((gfp
& __GFP_ZERO
) && b
))
339 * slob_free: entry point into the slob allocator.
341 static void slob_free(void *block
, int size
)
344 slob_t
*prev
, *next
, *b
= (slob_t
*)block
;
347 struct list_head
*slob_list
;
349 if (unlikely(ZERO_OR_NULL_PTR(block
)))
353 sp
= virt_to_page(block
);
354 units
= SLOB_UNITS(size
);
356 spin_lock_irqsave(&slob_lock
, flags
);
358 if (sp
->units
+ units
== SLOB_UNITS(PAGE_SIZE
)) {
359 /* Go directly to page allocator. Do not pass slob allocator */
360 if (slob_page_free(sp
))
361 clear_slob_page_free(sp
);
362 spin_unlock_irqrestore(&slob_lock
, flags
);
364 page_mapcount_reset(sp
);
365 slob_free_pages(b
, 0);
369 if (!slob_page_free(sp
)) {
370 /* This slob page is about to become partially free. Easy! */
374 (void *)((unsigned long)(b
+
375 SLOB_UNITS(PAGE_SIZE
)) & PAGE_MASK
));
376 if (size
< SLOB_BREAK1
)
377 slob_list
= &free_slob_small
;
378 else if (size
< SLOB_BREAK2
)
379 slob_list
= &free_slob_medium
;
381 slob_list
= &free_slob_large
;
382 set_slob_page_free(sp
, slob_list
);
387 * Otherwise the page is already partially free, so find reinsertion
392 if (b
< (slob_t
*)sp
->freelist
) {
393 if (b
+ units
== sp
->freelist
) {
394 units
+= slob_units(sp
->freelist
);
395 sp
->freelist
= slob_next(sp
->freelist
);
397 set_slob(b
, units
, sp
->freelist
);
401 next
= slob_next(prev
);
404 next
= slob_next(prev
);
407 if (!slob_last(prev
) && b
+ units
== next
) {
408 units
+= slob_units(next
);
409 set_slob(b
, units
, slob_next(next
));
411 set_slob(b
, units
, next
);
413 if (prev
+ slob_units(prev
) == b
) {
414 units
= slob_units(b
) + slob_units(prev
);
415 set_slob(prev
, units
, slob_next(b
));
417 set_slob(prev
, slob_units(prev
), b
);
420 spin_unlock_irqrestore(&slob_lock
, flags
);
424 * End of slob allocator proper. Begin kmem_cache_alloc and kmalloc frontend.
427 static __always_inline
void *
428 __do_kmalloc_node(size_t size
, gfp_t gfp
, int node
, unsigned long caller
)
431 int align
= max_t(size_t, ARCH_KMALLOC_MINALIGN
, ARCH_SLAB_MINALIGN
);
434 gfp
&= gfp_allowed_mask
;
436 fs_reclaim_acquire(gfp
);
437 fs_reclaim_release(gfp
);
439 if (size
< PAGE_SIZE
- align
) {
441 return ZERO_SIZE_PTR
;
443 m
= slob_alloc(size
+ align
, gfp
, align
, node
);
448 ret
= (void *)m
+ align
;
450 trace_kmalloc_node(caller
, ret
,
451 size
, size
+ align
, gfp
, node
);
453 unsigned int order
= get_order(size
);
457 ret
= slob_new_pages(gfp
, order
, node
);
459 trace_kmalloc_node(caller
, ret
,
460 size
, PAGE_SIZE
<< order
, gfp
, node
);
463 kmemleak_alloc(ret
, size
, 1, gfp
);
467 void *__kmalloc(size_t size
, gfp_t gfp
)
469 return __do_kmalloc_node(size
, gfp
, NUMA_NO_NODE
, _RET_IP_
);
471 EXPORT_SYMBOL(__kmalloc
);
473 void *__kmalloc_track_caller(size_t size
, gfp_t gfp
, unsigned long caller
)
475 return __do_kmalloc_node(size
, gfp
, NUMA_NO_NODE
, caller
);
479 void *__kmalloc_node_track_caller(size_t size
, gfp_t gfp
,
480 int node
, unsigned long caller
)
482 return __do_kmalloc_node(size
, gfp
, node
, caller
);
486 void kfree(const void *block
)
490 trace_kfree(_RET_IP_
, block
);
492 if (unlikely(ZERO_OR_NULL_PTR(block
)))
494 kmemleak_free(block
);
496 sp
= virt_to_page(block
);
498 int align
= max_t(size_t, ARCH_KMALLOC_MINALIGN
, ARCH_SLAB_MINALIGN
);
499 unsigned int *m
= (unsigned int *)(block
- align
);
500 slob_free(m
, *m
+ align
);
502 __free_pages(sp
, compound_order(sp
));
504 EXPORT_SYMBOL(kfree
);
506 /* can't use ksize for kmem_cache_alloc memory, only kmalloc */
507 size_t ksize(const void *block
)
514 if (unlikely(block
== ZERO_SIZE_PTR
))
517 sp
= virt_to_page(block
);
518 if (unlikely(!PageSlab(sp
)))
519 return PAGE_SIZE
<< compound_order(sp
);
521 align
= max_t(size_t, ARCH_KMALLOC_MINALIGN
, ARCH_SLAB_MINALIGN
);
522 m
= (unsigned int *)(block
- align
);
523 return SLOB_UNITS(*m
) * SLOB_UNIT
;
525 EXPORT_SYMBOL(ksize
);
527 int __kmem_cache_create(struct kmem_cache
*c
, unsigned long flags
)
529 if (flags
& SLAB_TYPESAFE_BY_RCU
) {
530 /* leave room for rcu footer at the end of object */
531 c
->size
+= sizeof(struct slob_rcu
);
537 static void *slob_alloc_node(struct kmem_cache
*c
, gfp_t flags
, int node
)
541 flags
&= gfp_allowed_mask
;
543 fs_reclaim_acquire(flags
);
544 fs_reclaim_release(flags
);
546 if (c
->size
< PAGE_SIZE
) {
547 b
= slob_alloc(c
->size
, flags
, c
->align
, node
);
548 trace_kmem_cache_alloc_node(_RET_IP_
, b
, c
->object_size
,
549 SLOB_UNITS(c
->size
) * SLOB_UNIT
,
552 b
= slob_new_pages(flags
, get_order(c
->size
), node
);
553 trace_kmem_cache_alloc_node(_RET_IP_
, b
, c
->object_size
,
554 PAGE_SIZE
<< get_order(c
->size
),
561 kmemleak_alloc_recursive(b
, c
->size
, 1, c
->flags
, flags
);
565 void *kmem_cache_alloc(struct kmem_cache
*cachep
, gfp_t flags
)
567 return slob_alloc_node(cachep
, flags
, NUMA_NO_NODE
);
569 EXPORT_SYMBOL(kmem_cache_alloc
);
572 void *__kmalloc_node(size_t size
, gfp_t gfp
, int node
)
574 return __do_kmalloc_node(size
, gfp
, node
, _RET_IP_
);
576 EXPORT_SYMBOL(__kmalloc_node
);
578 void *kmem_cache_alloc_node(struct kmem_cache
*cachep
, gfp_t gfp
, int node
)
580 return slob_alloc_node(cachep
, gfp
, node
);
582 EXPORT_SYMBOL(kmem_cache_alloc_node
);
585 static void __kmem_cache_free(void *b
, int size
)
587 if (size
< PAGE_SIZE
)
590 slob_free_pages(b
, get_order(size
));
593 static void kmem_rcu_free(struct rcu_head
*head
)
595 struct slob_rcu
*slob_rcu
= (struct slob_rcu
*)head
;
596 void *b
= (void *)slob_rcu
- (slob_rcu
->size
- sizeof(struct slob_rcu
));
598 __kmem_cache_free(b
, slob_rcu
->size
);
601 void kmem_cache_free(struct kmem_cache
*c
, void *b
)
603 kmemleak_free_recursive(b
, c
->flags
);
604 if (unlikely(c
->flags
& SLAB_TYPESAFE_BY_RCU
)) {
605 struct slob_rcu
*slob_rcu
;
606 slob_rcu
= b
+ (c
->size
- sizeof(struct slob_rcu
));
607 slob_rcu
->size
= c
->size
;
608 call_rcu(&slob_rcu
->head
, kmem_rcu_free
);
610 __kmem_cache_free(b
, c
->size
);
613 trace_kmem_cache_free(_RET_IP_
, b
);
615 EXPORT_SYMBOL(kmem_cache_free
);
617 void kmem_cache_free_bulk(struct kmem_cache
*s
, size_t size
, void **p
)
619 __kmem_cache_free_bulk(s
, size
, p
);
621 EXPORT_SYMBOL(kmem_cache_free_bulk
);
623 int kmem_cache_alloc_bulk(struct kmem_cache
*s
, gfp_t flags
, size_t size
,
626 return __kmem_cache_alloc_bulk(s
, flags
, size
, p
);
628 EXPORT_SYMBOL(kmem_cache_alloc_bulk
);
630 int __kmem_cache_shutdown(struct kmem_cache
*c
)
632 /* No way to check for remaining objects */
636 void __kmem_cache_release(struct kmem_cache
*c
)
640 int __kmem_cache_shrink(struct kmem_cache
*d
)
645 struct kmem_cache kmem_cache_boot
= {
646 .name
= "kmem_cache",
647 .size
= sizeof(struct kmem_cache
),
649 .align
= ARCH_KMALLOC_MINALIGN
,
652 void __init
kmem_cache_init(void)
654 kmem_cache
= &kmem_cache_boot
;
658 void __init
kmem_cache_init_late(void)