Slab allocation
Encyclopedia
Slab allocation is a memory management
mechanism intended for the efficient memory allocation of kernel objects which displays the desirable property of eliminating fragmentation
caused by allocations and deallocations. The technique is used to retain allocated memory that contains a data object of a certain type for reuse upon subsequent allocations of objects of the same type. Slab allocation was first introduced in the Solaris 2.4 kernel by Jeff Bonwick
and now is widely used by many Unix operating systems including FreeBSD
and Linux
as of version 2.2.
With slab allocation, memory chunks suitable to fit data objects of certain type or size are preallocated. The slab allocator keeps track of these chunks, known as caches, so that when a request to allocate memory for a data object of a certain type is received it can instantly satisfy the request with an already allocated slot. Destruction of the object, however, does not free up the memory, but only opens a slot which is put in the list of free slots by the slab allocator. The next call to allocate memory of the same size will return the now unused memory slot. This process eliminates the need to search for suitable memory space and greatly alleviates memory fragmentation. In this context a slab is one or more contiguous pages in the memory containing pre-allocated memory chunks.
When a program sets up a cache, it allocates a number of objects to the slabs associated to that cache. This number depends on the size of the associated slabs.
Slabs may exist in one of the following states :
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.
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.
Memory management
Memory management is the act of managing computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and freeing it for reuse when no longer needed. This is critical to the computer system.Several...
mechanism intended for the efficient memory allocation of kernel objects which displays the desirable property of eliminating fragmentation
Fragmentation (computer)
In computer storage, fragmentation is a phenomenon in which storage space is used inefficiently, reducing storage capacity and in most cases reducing the performance. The term is also used to denote the wasted space itself....
caused by allocations and deallocations. The technique is used to retain allocated memory that contains a data object of a certain type for reuse upon subsequent allocations of objects of the same type. Slab allocation was first introduced in the Solaris 2.4 kernel by Jeff Bonwick
Jeff Bonwick
Jeff Bonwick was a Sun Fellow at Sun Microsystems, later a Vice President at Sun and then a Senior Software Architect at Oracle until his departure from the company on 30 September 2010.He led the team which developed ZFS for Solaris....
and now is widely used by many Unix operating systems including FreeBSD
FreeBSD
FreeBSD is a free Unix-like operating system descended from AT&T UNIX via BSD UNIX. Although for legal reasons FreeBSD cannot be called “UNIX”, as the direct descendant of BSD UNIX , FreeBSD’s internals and system APIs are UNIX-compliant...
and Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
as of version 2.2.
Basis
The primary motivation for slab allocation is that the initialization and destruction of kernel data objects can actually outweigh the cost of allocating memory for them. As object creation and deletion are widely employed by the kernel, mitigating overhead costs of initialization can result in significant performance gains. The notion of object caching was therefore introduced in order to avoid the invocation of functions used to initialize object state.With slab allocation, memory chunks suitable to fit data objects of certain type or size are preallocated. The slab allocator keeps track of these chunks, known as caches, so that when a request to allocate memory for a data object of a certain type is received it can instantly satisfy the request with an already allocated slot. Destruction of the object, however, does not free up the memory, but only opens a slot which is put in the list of free slots by the slab allocator. The next call to allocate memory of the same size will return the now unused memory slot. This process eliminates the need to search for suitable memory space and greatly alleviates memory fragmentation. In this context a slab is one or more contiguous pages in the memory containing pre-allocated memory chunks.
Implementation
Understanding the slab allocation algorithm requires defining and explaining some terms:- Cache: cache represents a small amount of very fast memory. A cache is a storage for a specific type of objectObject (computer science)In computer science, an object is any entity that can be manipulated by the commands of a programming language, such as a value, variable, function, or data structure...
such as semaphoreSemaphore (programming)In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
s, processProcess (computing)In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...
descriptors, fileComputer fileA computer file is a block of arbitrary information, or resource for storing information, which is available to a computer program and is usually based on some kind of durable storage. A file is durable in the sense that it remains available for programs to use after the current program has finished...
objects etc. - Slab: slab represents a contiguous piece of memory, usually made of several physically contiguous pages. A cache consists of one or more slabs. The slab is the actual container of data associated to objects of the specific kind of the containing cache.
When a program sets up a cache, it allocates a number of objects to the slabs associated to that cache. This number depends on the size of the associated slabs.
Slabs may exist in one of the following states :
- empty - all objects on a slab marked as free
- partial - slab consists of both used and free objects
- 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.
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).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).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.
Systems using slab allocation
- AmigaOSAmigaOSAmigaOS is the default native operating system of the Amiga personal computer. It was developed first by Commodore International, and initially introduced in 1985 with the Amiga 1000...
(introduced in 4.0) - DragonFly BSDDragonFly BSDDragonFly BSD is a free Unix-like operating system created as a fork of FreeBSD 4.8. Matthew Dillon, an Amiga developer in the late 1980s and early 1990s and a FreeBSD developer between 1994 and 2003, began work on DragonFly BSD in June 2003 and announced it on the FreeBSD mailing lists on July...
(introduced in release 1.0) - FreeBSDFreeBSDFreeBSD is a free Unix-like operating system descended from AT&T UNIX via BSD UNIX. Although for legal reasons FreeBSD cannot be called “UNIX”, as the direct descendant of BSD UNIX , FreeBSD’s internals and system APIs are UNIX-compliant...
(introduced in 5.0) - HaikuHaiku (operating system)Haiku is a free and open source operating system compatible with BeOS. Its development began in 2001, and the operating system became self-hosting in 2008, with the first alpha release in September 2009, the second in May 2010 and the third in June 2011....
(introduced in alpha 2) - HP-UXHP-UXHP-UX is Hewlett-Packard's proprietary implementation of the Unix operating system, based on UNIX System V and first released in 1984...
(introduced in 11i) - LinuxLinuxLinux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
(introduced in kernel 2.2, many popular distributions now choose the SLUB allocation method over SLAB, but it is still available as an option) - NetBSDNetBSDNetBSD is a freely available open source version of the Berkeley Software Distribution Unix operating system. It was the second open source BSD descendant to be formally released, after 386BSD, and continues to be actively developed. The NetBSD project is primarily focused on high quality design,...
(introduced in 4.0) - Solaris (introduced in 2.4)
External links
- FreeBSD uma(9) manual page
- Anatomy of the Linux slab allocator a developerWorks article by M. Tim Jones
- The SLUB allocator comment about management of slabs in LinuxLinux kernelThe Linux kernel is an operating system kernel used by the Linux family of Unix-like operating systems. It is one of the most prominent examples of free and open source software....
by two different allocators: SLUB allocator and SLAB allocator - Memory Compaction v7 (a Linux patch set from Mel Gorman dealing with SLAB fragmentation and compaction issues, April 2, 2010)
- Detecting kernel memory leaks Jonathan Corbet, Linux Weekly News, 2006; includes user comments on garbage collection
- Linux performance: is Linux becoming just too slow and bloated? On SLAB and SLUB. Free software magazine 2010.