Slab allocation

From Wikipedia, the free encyclopedia

To comply with Wikipedia's quality standards, this article may need to be rewritten. Please help improve this article. The discussion page may contain suggestions.

In computer science, the slab allocation algorithm manages memory in such a way as to solve the problem of external memory fragmentation that results from variably-sized allocations with variably-sized lifetimes, accepting in exchange a certain degree of internal fragmentation.

Contents 1 Implementation 2 Slabs 2.1 Large Slabs 2.2 Small Slabs 3 Systems using slab allocation 4 See also 5 Sources 6 External links

[edit] Implementation

Understanding the slab allocation algorithm requires defining and explaining some terms:

1. Cache: cache represents a small amount of very fast memory. Here we use cache as storage for objects such as semaphores, process descriptors, file objects etc. Every cache represents storage for only one type of object.
2. Slab: slab represents a contiguous piece of memory, usually made of several physically contiguous pages. A cache consists of one or more slabs.

When a program sets up a cache, it allocates a number of objects to that cache. This number depends on the size of the associated slabs.

Slabs may exist in one of the following states :

1. empty - all objects on a slab marked as free
2. partial - slab consists of both used and free objects
3. full - all objects on a slab marked as used

Initially, the system marks each slab as "empty". When the process calls for a new kernel object, the system tries to find a free location for that object on a partial slab in a cache for that type of object. If no such location exists, the system allocates a new slab from contiguous physical pages and assigns it to a cache. The new object gets allocated from this slab, and its location becomes marked as "partial".

The slab allocation algorithm has as its principal benefit that memory gets allocated in exactly the same size as requested, thus no internal memory fragmentation exists. The allocation takes place quickly, because the system builds the objects in advance and readily allocates them from a slab.

[edit] Slabs

A slab is the amount that a cache can grow or shrink by. It represents one memory allocation to the cache from the machine, and whose size is customarily a multiple of the page size. A slab must contain a list of free buffers (or bufctls), as well as a list of the bufctls that have been allocated (in the case of a large slab size).

[edit] Large Slabs

These are for caches that store objects that are not less than 1/8 of the page size for a given machine. The reason for the large slabs having a different layout from the small slabs is that it allows large slabs to pack better into page-size units, which helps with fragmentation. The slab contains a list of bufctls, which are simply controllers for each buffer that can be allocated (a buffer is the memory that the user of a slab allocator would use).

[edit] Small Slabs

The small slabs contain objects that are less than 1/8 of the page size for a given machine. These small slabs need to be optimized further from the logical layout, by avoiding using bufctls (which would be just as large as the data itself and cause memory usage to be much greater). A small slab is exactly one page, and has a defined structure that allows bufctls to be avoided. The last part of the page contains the 'slab header' which is the information needed to retain the slab. Starting at the first address of that page, there are as many buffers as can be allocated without running into the slab header at the end of the page.

Instead of using bufctls, we use the buffers themselves to retain the free list links. This allows the small slab's bufctl to be bypassed.

[edit] Systems using slab allocation

1. AmigaOS (introduced in 4.0)
2. DragonFly BSD (introduced in release 1.0)
3. FreeBSD (introduced in 5.0)
4. Linux (introduced in kernel 2.2)
5. NetBSD (introduced in 4.0)
6. Solaris (introduced in kernel 2.4)

[edit] See also

• Slab (NCR) - a similar but distinct meaning for NCR computers

[edit] Sources

• Abraham Silberschatz et al: Operating system concepts. Wiley: 2004. ISBN 0-471-69466-5
• Jeff Bonwick, The Slab Allocator: An Object-Caching Kernel Memory Allocator (1994)

[edit] External links

• Anatomy of the Linux slab allocator a developerWorks article by M. Tim Jones
• The SLUB allocator comment about management of slabs in Linux by two different allocators: SLUB allocator and SLAB allocator