Slab allocation is a
memory managementMemory management is the act of managing computer memory. In its simpler forms, this involves providing ways to allocate portions of memory to programs at their request, and freeing it for reuse when no longer needed...
mechanism intended for more efficient memory allocation and to eliminate memory
fragmentationIn computer storage, fragmentation is a phenomenon in which storage space is used inefficiently, reducing storage capacity and in most cases performance. The term is also used to denote the wasted space itself....
to a large extent. The basis for this algorithm is retaining an allocated memory that used to contain a data object of certain type and reusing that memory for the next allocations for another object of the same type. This technique was first introduced in
SunOSSunOS is a version of the Unix operating system developed by Sun Microsystems for their workstation and server computer systems. The SunOS name is usually only used to refer to versions 1.0 to 4.1.4 of SunOS...
by
Jeff BonwickJeff Bonwick is a Sun Fellow at Sun Microsystems.He leads the team which developed ZFS for Solaris.Notable among Bonwick's other work is the slab allocator,. an object-caching kernel memory allocator, and the LZJB compression algorithm....
and now is widely used by many Unix operating systems including
LinuxLinux is a generic term referring to Unix-like computer operating systems based on the Linux kernel. Their development is one of the most prominent examples of free and open source software collaboration; typically all the underlying source code can be used, freely modified, and redistributed,...
.
The fundamental idea behind slab allocation technique is based on the observation that there are some kernel data objects that are frequently created and destroyed after they are not needed anymore.
Slab allocation is a
memory managementMemory management is the act of managing computer memory. In its simpler forms, this involves providing ways to allocate portions of memory to programs at their request, and freeing it for reuse when no longer needed...
mechanism intended for more efficient memory allocation and to eliminate memory
fragmentationIn computer storage, fragmentation is a phenomenon in which storage space is used inefficiently, reducing storage capacity and in most cases performance. The term is also used to denote the wasted space itself....
to a large extent. The basis for this algorithm is retaining an allocated memory that used to contain a data object of certain type and reusing that memory for the next allocations for another object of the same type. This technique was first introduced in
SunOSSunOS is a version of the Unix operating system developed by Sun Microsystems for their workstation and server computer systems. The SunOS name is usually only used to refer to versions 1.0 to 4.1.4 of SunOS...
by
Jeff BonwickJeff Bonwick is a Sun Fellow at Sun Microsystems.He leads the team which developed ZFS for Solaris.Notable among Bonwick's other work is the slab allocator,. an object-caching kernel memory allocator, and the LZJB compression algorithm....
and now is widely used by many Unix operating systems including
LinuxLinux is a generic term referring to Unix-like computer operating systems based on the Linux kernel. Their development is one of the most prominent examples of free and open source software collaboration; typically all the underlying source code can be used, freely modified, and redistributed,...
.
Basis
The fundamental idea behind slab allocation technique is based on the observation that there are some kernel data objects that are frequently created and destroyed after they are not needed anymore. This implies that for each allocation of memory for these data objects, some time is spent to find the best fit for that data object. Moreover, deallocation of the memory after destruction of the object contributes to
fragmentationIn computer storage, fragmentation is a phenomenon in which storage space is used inefficiently, reducing storage capacity and in most cases performance. The term is also used to denote the wasted space itself....
of the memory which burdens the kernel some more to rearrange the memory.
With slab allocation, using certain system calls by the programmer, 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 certain size 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 the suitable memory space and alleviates memory fragmentation to a large extent. 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. Here we use cache as storage for object
In computer science, an object, in the domain of object-oriented programming, usually means a compilation of attributes and behaviors encapsulating an entity....
s such as semaphoreIn computer science, a semaphore is a protected variable or abstract data type which constitutes the classic method for restricting access to shared resources such as shared memory in a parallel programming environment. A counting semaphore is a counter for a set of available resources, rather than...
s, processIn computing, a process is an instance of a computer program, consisting of one or more threads, that is being sequentially executed by a computer system that has the ability to run several computer programs concurrently....
descriptors, 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. Every cache represents storage for only one type of object.
- 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 :
- 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
- AmigaOS
AmigaOS 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 BSD
DragonFly 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)
- FreeBSD
FreeBSD is a free Unix-like operating system descended from AT&T UNIX via the Berkeley Software Distribution . It has been characterized as "the unknown giant among free operating systems". It is not a clone of UNIX, but works like UNIX, with UNIX-compliant internals and system APIs. FreeBSD is...
(introduced in 5.0)
- Linux
Linux is a generic term referring to Unix-like computer operating systems based on the Linux kernel. Their development is one of the most prominent examples of free and open source software collaboration; typically all the underlying source code can be used, freely modified, and redistributed,...
(introduced in kernel 2.2, many popular distributions now choose the SLUB allocation method over SLAB, but it is still available as an option)
- NetBSD
NetBSD is a freely redistributable, open source version of the Unix-derivative Berkeley Software Distribution computer operating system. It was the second open source BSD descendant to be formally released, after 386BSD, and continues to be actively developed...
(introduced in 4.0)
- Solaris
Solaris is a UNIX-based operating system introduced by Sun Microsystems in 1992 as the successor to SunOS.Solaris is known for its scalability, especially on SPARC systems, and for originating many innovative features such as DTrace and ZFS...
(introduced in 2.4)
- Jari OS
Jari OS is a microkernel based real-time operating system with multi-server architecture and preemptible kernel. The source code of Jari OS is published under GNU General Public License.Jari is a not a name, it stands for Just another Research in i.e...
See also
- Slab (NCR) - a similar but distinct meaning for NCR computers
- SLUB (computer science)
- SLOB
The SLOB is a one of three available of memory allocators in Linux kernel. The SLOB allocator, is designed to be a small and efficient allocation framework for use in small systems such as embedded systems...
Sources
- Abraham Silberschatz
Silberschatz obtained his Ph.D. from the State University of New York at Stony Brook. Prior to coming to Yale in 2003, he was the Vice President of the Information Sciences Research Center at Bell Labs...
et al.: Operating system concepts. Wiley: 2004. ISBN 0-471-69466-5
- Jeff Bonwick
Jeff Bonwick is a Sun Fellow at Sun Microsystems.He leads the team which developed ZFS for Solaris.Notable among Bonwick's other work is the slab allocator,. an object-caching kernel memory allocator, and the LZJB compression algorithm....
, The Slab Allocator: An Object-Caching Kernel Memory Allocator (1994)
- FreeBSD uma(9) manual page
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
The 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