What's the difference between slab and buddy system?

Question

It seems to me they are quite similar. So what's the relation between slab and buddy system?

Answer 1

A slab is a collection of objects of the same size. It avoids fragmentation by allocating a fairly large block of memory and dividing it into equal-sized pieces. The number of pieces is typically much larger than two, say 128 or so.

There are two ways you can use slabs. First, you could have a slab just for one size that you allocate very frequently. For example, a kernel might have an inode slab. But you could also have a number of slabs in progressive sizes, like a 128-byte slab, a 192-byte slab, a 256-byte slab, and so on. You can then allocate an object of any size from the next slab size up.

Note that in neither case does a slab re-use memory for an object of a different size unless the entire slab is freed back to a global "large block" allocator.

The buddy system is an unrelated method where each object has a "buddy" object which it is coalesced with when it is freed. Blocks are divided in half when smaller blocks are needed. Note that in the buddy system, blocks are divided and coalesced into larger blocks as the primary means of allocation and returning for re-use. This is very different from how slabs work.

Or to put it more simply:

Buddy system: Various sized blocks are divided when allocated and coalesced when freed to efficiently divide a big block into smaller blocks of various sizes as needed.

Slab: Very large blocks are allocated and divided once into equal-sized blocks. No other dividing or coalescing takes place and freed blocks are just held in a list to be assigned to subsequent allocations.

The Linux kernel's core allocator is a flexible buddy system allocator. This allocator provide the slabs for the various slab allcoators.

Answer 2

In general slab allocator is a list of slabs with fixed size suited to place predefined size elements. As all objects in the pool of the same size there is no fragmentation.

Buddy allocator divides memory in chunks which sizes a doubled. For example if min chunk is 1k, the next will be 2K, then 4K etc. So if we will request to allocate 100b, then the chunk with size 1k will be chosen. What leads to fragmentation but allows to allocate arbitrary size objects (so it's well suited for user memory allocations where exact object sized could be of any size).

See also:

• https://en.wikipedia.org/wiki/Slab_allocation
• https://en.wikipedia.org/wiki/Buddy_memory_allocation

Also worse check this presentations: http://events.linuxfoundation.org/images/stories/pdf/klf2012_kim.pdf Slides from page 22 reveal the summary of differencies.