Slab allocation: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 14:30, 21 November 2024

Slab allocation is a memory management mechanism intended for the efficient memory allocation of objects. In comparison with earlier mechanisms, it reduces fragmentation caused by allocations and deallocations. This technique is used for retaining allocated memory containing a data object of a certain type for reuse upon subsequent allocations of objects of the same type. It is analogous to an object pool, but only applies to memory, not other resources.

Slab allocation was first introduced in the Solaris 2.4 kernel by Jeff Bonwick.^[1] It is now widely used by many Unix and Unix-like operating systems including FreeBSD^[2] and Linux,^[3] both in the SLAB allocator and its replacement, SLUB.^[4]

Basis

Slab allocation significantly reduces the frequency of computationally costly initialization and destruction of kernel data-objects, which can outweigh the cost of allocating memory for them.^[1] When the kernel creates and deletes objects often, overhead costs of initialization can result in significant performance drops. Object caching leads to less frequent invocation of functions which initialize object state: when a slab-allocated object is released after use, the slab allocation system typically keeps it cached (rather than doing the work of destroying it) ready for re-use next time an object of that type is needed (thus avoiding the work of constructing and initialising a new object).

With slab allocation, a cache for a certain type or size of data object has a number of pre-allocated "slabs" of memory; within each slab there are memory chunks of fixed size suitable for the objects.^[5] The slab allocator keeps track of these chunks, so that when it receives a request to allocate memory for a data object of a certain type, usually it can satisfy the request with a free slot (chunk) from an existing slab. When the allocator is asked to free the object's memory, it just adds the slot to the containing slab's list of free (unused) slots. The next call to create an object of the same type (or allocate memory of the same size) will return that memory slot (or some other free slot) and remove it from the list of free slots. 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

The slab allocation algorithm defines the following terms:

Cache: cache represents a small amount of very fast memory. A cache is a storage for a specific type of object, such as semaphores, process descriptors, file objects, etc.
Slab: slab represents a contiguous piece of memory, usually made of several virtually contiguous pages. The slab is the actual container of data associated with 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 with 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 virtual pages and assigns it to a cache. The new object gets allocated from this slab, and its location becomes marked as "partial".

The allocation takes place quickly, because the system builds the objects in advance and readily allocates them from a slab.

Implementation techniques

Free lists

A slab represents one memory allocation to the cache from the machine, and whose size is customarily a multiple of the page size. The slab will be divided into a number of entries, which will then be requested by the cache as the client code requests memory for new objects. It is necessary then to keep track of which parts of the slab are free to use and which ones were already occupied. This is generally done using "free lists": lists of free entries in the slab ready to store new objects.

The free list may be a separate data structure, such as an array of indices indicating which entries of the slab are free, or it may be embedded within the slab. The Linux SLUB allocator keeps the free list as a linked list of pointers, each of which is stored directly in the free memory area of the slab they represent.^[6]

Slab sizes

Operating systems may use different slab sizes and internal layouts depending on the size of the objects to be stored. 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. For example, objects that are at least 1/8 of the page size for a given machine may benefit from a "large slab" size, with explicit free lists, while smaller objects may use a "small slab" setup, embed the free list tracking. Bonwick's original presentation of the slab allocator already made the distinction of layouts for large and small slabs.^[1]

Systems using slab allocation

AmigaOS (introduced in AmigaOS 4)
DragonFly BSD (introduced in release 1.0)
FreeBSD (introduced in 5.0)
GNU Mach^[7]
Haiku (introduced in alpha 2)
Horizon (Nintendo Switch microkernel)^[8]
HP-UX (introduced in 11i)^[9]
Linux (introduced in kernel 2.1.23, it's now one of three memory allocator implementations together with SLOB and SLUB. The three allocators provides a kind of front-end to the zoned buddy allocator for those sections of the kernel that require more flexible memory allocation than the standard 4 KB page size).
NetBSD (introduced in 4.0)
Solaris (introduced in 2.4)
The Perl 5 compiler uses a slab allocator for internal memory management^[10]^[11]
Memcached uses slab allocation for memory management
illumos

Notes

^ ^a ^b ^c Jeff Bonwick, The Slab Allocator: An Object-Caching Kernel Memory Allocator (1994)
^ FreeBSD Kernel Developer's Manual
^ M. Tim Jones, Anatomy of the Linux slab allocator Archived 2 October 2013 at the Wayback Machine
^ Vlastimil Babka, remove the SLAB allocator
^ Abraham Silberschatz et al.: Operating system concepts. Wiley: 2004. ISBN 0-471-69466-5
^ Lameter, Christoph. "Slab allocators in the Linux Kernel: SLAB, SLOB, SLUB" (PDF). LinuxCon/Düsseldorf 2014 (Revision Oct 3, 2014).
^ "Gnu Mach Allocator Documentation".
^ "Console Security – Switch (34c3)". media.ccc.de. Retrieved 28 December 2017.
^ Chris Cooper and Chris Moore, HP-UX 11i Internals, Upper Saddle River, New Jersey: Prentice Hall PTR, 2004, ISBN 0-13-032861-8, p. 334.
^ "Perl5-Porters Weekly: 2012 June 17". Retrieved 18 November 2012.
^ Bonwick, Jeff. "Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources". USENIX 2001. Retrieved 18 November 2012.

External links

FreeBSD uma(9) manual page
The SLUB allocator comment about management of slabs in Linux 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, 2 April 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.

[bonwick-1] Jeff Bonwick, The Slab Allocator: An Object-Caching Kernel Memory Allocator (1994)

[bsdman-2] FreeBSD Kernel Developer's Manual

[jones-3] M. Tim Jones, Anatomy of the Linux slab allocator Archived 2 October 2013 at the Wayback Machine

[babka-4] Vlastimil Babka, remove the SLAB allocator

[silberschatz-5] Abraham Silberschatz et al.: Operating system concepts. Wiley: 2004. ISBN 0-471-69466-5

[6] Lameter, Christoph. "Slab allocators in the Linux Kernel: SLAB, SLOB, SLUB" (PDF). LinuxCon/Düsseldorf 2014 (Revision Oct 3, 2014).

[7] "Gnu Mach Allocator Documentation".

[8] "Console Security – Switch (34c3)". media.ccc.de. Retrieved 28 December 2017.

[9] Chris Cooper and Chris Moore, HP-UX 11i Internals, Upper Saddle River, New Jersey: Prentice Hall PTR, 2004, ISBN 0-13-032861-8, p. 334.

[p5p-weekly-10] "Perl5-Porters Weekly: 2012 June 17". Retrieved 18 November 2012.

[Bonwick2001-11] Bonwick, Jeff. "Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources". USENIX 2001. Retrieved 18 November 2012.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 1: / Line 1: @@
+{{Short description|Memory management mechanism}}
 {{distinguish|Slab (unit)}}
-{{Use dmy dates|date=August 2012}}
+{{Use dmy dates|date=July 2022}}
-'''Slab allocation''' is a [[memory management]] mechanism intended for the efficient memory allocation of objects.  It eliminates [[Fragmentation (computer)|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.  It is analogous to an [[object pool]], but only applies to memory, not other resources.
+'''Slab allocation''' is a [[memory management]] mechanism intended for the efficient memory allocation of objects. In comparison with earlier mechanisms, it reduces [[Fragmentation (computer)|fragmentation]] caused by allocations and deallocations.
+This technique is used for retaining allocated memory containing a data object of a certain type for reuse upon subsequent allocations of objects of the same type.  It is analogous to an [[object pool]], but only applies to memory, not other resources.
-Slab allocation was first introduced in the [[Solaris (operating system)|Solaris]] 2.4 kernel by [[Jeff Bonwick]].<ref name=bonwick/>  It is now widely used by many Unix and Unix-like operating systems including [[FreeBSD]]<ref name=bsdman>[http://fuse4bsd.creo.hu/localcgi/man-cgi.cgi?zone+9 FreeBSD Kernel Developer's Manual] {{webarchive|url=https://web.archive.org/web/20110721052221/http://fuse4bsd.creo.hu/localcgi/man-cgi.cgi?zone+9 |date=21 July 2011 }}</ref>  and [[Linux]].<ref name=jones>M. Tim Jones, [http://www.ibm.com/developerworks/linux/library/l-linux-slab-allocator/ Anatomy of the Linux slab allocator] {{webarchive |url=https://web.archive.org/web/20131002111628/http://www.ibm.com/developerworks/linux/library/l-linux-slab-allocator/ |date=02 Oct 2013}}</ref>
+Slab allocation was first introduced in the [[Solaris (operating system)|Solaris]] 2.4 kernel by [[Jeff Bonwick]].<ref name=bonwick/> It is now widely used by many Unix and Unix-like operating systems including [[FreeBSD]]<ref name=bsdman>[https://www.freebsd.org/cgi/man.cgi?query=zone&apropos=0&sektion=9&manpath=FreeBSD+12.1-RELEASE&arch=default&format=html FreeBSD Kernel Developer's Manual]</ref> and [[Linux]],<ref name=jones>M. Tim Jones, [http://www.ibm.com/developerworks/linux/library/l-linux-slab-allocator/ Anatomy of the Linux slab allocator] {{webarchive |url=https://web.archive.org/web/20131002111628/http://www.ibm.com/developerworks/linux/library/l-linux-slab-allocator/ |date=2 October 2013}}</ref> both in the SLAB allocator and its replacement, [[SLUB_(software)|SLUB]].<ref name=babka>Vlastimil Babka, [https://lore.kernel.org/linux-mm/ZXEx1%2Fp9ejRmkVTS@localhost.localdomain/T/#m1a5899625baa61ad31a0e99eea6fc02258513ac1 remove the SLAB allocator]</ref>
 == 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.<ref name=bonwick>[[Jeff Bonwick]],[http://www.usenix.org/publications/library/proceedings/bos94/full_papers/bonwick.ps The Slab Allocator: An Object-Caching Kernel Memory Allocator (1994)]</ref>{{clarify|reason=Subsequently, 'initialization' is never mentioned again. Explain why slab allocation can speed up initialization.|date=March 2019}}  As object creation and deletion are widely employed by the kernel, overhead costs of initialization can result in significant performance drops. The notion of object caching was therefore introduced in order to avoid the invocation of functions used to initialize object state.
+Slab allocation significantly reduces the frequency of computationally costly initialization and destruction of kernel data-objects, which can outweigh the cost of allocating memory for them.<ref name=bonwick>[[Jeff Bonwick]], [http://www.usenix.org/publications/library/proceedings/bos94/full_papers/bonwick.ps The Slab Allocator: An Object-Caching Kernel Memory Allocator (1994)]</ref> When the kernel creates and deletes objects often, overhead costs of initialization can result in significant performance drops. Object caching leads to less frequent invocation of functions which initialize object state: when a slab-allocated object is released after use, the slab allocation system typically keeps it cached (rather than doing the work of destroying it) ready for re-use next time an object of that type is needed (thus avoiding the work of constructing and initialising a new object).
-With slab allocation, memory chunks suitable to fit data objects of certain type or size are preallocated.<ref name=silberschatz>[[Abraham Silberschatz]] ''et al.'': ''Operating system concepts''. Wiley: 2004. {{ISBN|0-471-69466-5}}</ref> 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 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.
+With slab allocation, a cache for a certain type or size of data object has a number of pre-allocated "slabs" of memory; within each slab there are memory chunks of fixed size suitable for the objects.<ref name=silberschatz>[[Abraham Silberschatz]] ''et al''.: ''Operating system concepts''. Wiley: 2004. {{ISBN|0-471-69466-5}}</ref> The slab allocator keeps track of these chunks, so that when it receives a request to allocate memory for a data object of a certain type, usually it can satisfy the request with a free slot (chunk) from an existing slab. When the allocator is asked to free the object's memory, it just adds the slot to the containing slab's list of free (unused) slots. The next call to create an object of the same type (or allocate memory of the same size) will return that memory slot (or some other free slot) and remove it from the list of free slots. 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:
+The slab allocation algorithm defines the following terms:
 # '''Cache''': cache represents a small amount of very fast memory. A cache is a storage for a specific type of [[Object (computer science)|object]], such as [[Semaphore (programming)|semaphore]]s, [[Process (computing)|process]] [[wikt:descriptor|descriptor]]s, [[computer file|file]] objects, etc.
-# '''Slab''': slab represents a contiguous piece of memory, usually made of several physically contiguous pages. The slab is the actual container of data associated with objects of the specific kind of the containing cache.
+# '''Slab''': slab represents a contiguous piece of memory, usually made of several virtually contiguous pages. The slab is the actual container of data associated with 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 with that cache. This number depends on the size of the associated slabs.
-Slabs may exist in one of the following states :
+Slabs may exist in one of the following states:
 # ''empty''&nbsp;– all objects on a slab marked as free
 # ''partial''&nbsp;– slab consists of both used and free objects
 # ''full''&nbsp;– 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".
+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 virtual pages and assigns it to a cache. The new object gets allocated from this slab, and its location becomes marked as "partial".
 The allocation takes place quickly, because the system builds the objects in advance and readily allocates them from a slab.
+==Implementation techniques==
-==Slabs==
-A slab is the amount by which a cache can grow or shrink.  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 [[Data buffer|buffers]] (or bufctls), as well as a list of the bufctls that have been allocated (in the case of a large slab size). {{Citation needed|date=April 2011}}
-===Large slabs===
+===Free lists===
-These are for caches that store objects that are at least 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).
+A slab represents one memory allocation to the cache from the machine, and whose size is customarily a multiple of the [[page size]]. The slab will be divided into a number of entries, which will then be requested by the cache as the client code requests memory for new objects. It is necessary then to keep track of which parts of the slab are free to use and which ones were already occupied. This is generally done using "free lists": lists of free entries in the slab ready to store new objects.
-===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.
+The free list may be a separate data structure, such as an array of indices indicating which entries of the slab are free, or it may be embedded within the slab. The Linux [[SLUB (software)|SLUB]] allocator keeps the free list as a linked list of pointers, each of which is stored directly in the free memory area of the slab they represent.<ref>{{cite web |last1=Lameter |first1=Christoph |title=Slab allocators in the Linux Kernel: SLAB, SLOB, SLUB |url=https://events.static.linuxfound.org/sites/events/files/slides/slaballocators.pdf |website=LinuxCon/Düsseldorf 2014 (Revision Oct 3, 2014)}}</ref>
-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.<ref name="bonwick"/>
+===Slab sizes===
+Operating systems may use different slab sizes and internal layouts depending on the size of the objects to be stored. 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. For example, objects that are at least 1/8 of the page size for a given machine may benefit from a "large slab" size, with explicit free lists, while smaller objects may use a "small slab" setup, embed the free list tracking. Bonwick's original presentation of the slab allocator already made the distinction of layouts for large and small slabs.<ref name="bonwick"/>
 == Systems using slab allocation ==
@@ Line 42: / Line 45: @@
 * [[DragonFly BSD]] (introduced in release 1.0)
 * [[FreeBSD]] (introduced in 5.0)
-* [[GNU Mach]] <ref>{{cite web|title=Gnu Mach Allocator Documentation|url=https://www.gnu.org/software/hurd/microkernel/mach/gnumach/memory_management.html}}</ref>
+* [[GNU Mach]]<ref>{{cite web|title=Gnu Mach Allocator Documentation|url=https://www.gnu.org/software/hurd/microkernel/mach/gnumach/memory_management.html}}</ref>
 * [[Haiku (operating system)|Haiku]] (introduced in alpha 2)
-* Horizon (Nintendo Switch microkernel)<ref>{{cite web|title=Console Security - Switch (34c3)|url=https://media.ccc.de/v/34c3-8941-console_security_-_switch|website=media.ccc.de|accessdate=28 December 2017}}</ref>
+* Horizon ([[Nintendo Switch]] microkernel)<ref>{{cite web|title=Console Security – Switch (34c3)|url=https://media.ccc.de/v/34c3-8941-console_security_-_switch|website=media.ccc.de|accessdate=28 December 2017}}</ref>
-* [[HP-UX]] (introduced in 11i)<ref>Chris Cooper and Chris Moore, ''HP-UX 11i Internals'', Upper Saddle River, New Jersey: Prentice Hall PTR, 2004, {{ISBN|0-13-032861-8}}, [https://books.google.com/books?id=SsH-qdTx9pUC&pg=PA334&lpg=PA334&dq=hp-ux+arena+allocator&source=bl&ots=SAVT2GT9Ej&sig=3dlUZIQ7_UYBFBgldkHb9d_hrGQ&hl=en&ei=Zn7HS9HEL4eStgOlpJT1BA&sa=X&oi=book_result&ct=result&resnum=4&ved=0CA8Q6AEwAw#v=onepage&q=hp-ux%20arena%20allocator&f=false p. 334].</ref>
+* [[HP-UX]] (introduced in 11i)<ref>Chris Cooper and Chris Moore, ''HP-UX 11i Internals'', Upper Saddle River, New Jersey: Prentice Hall PTR, 2004, {{ISBN|0-13-032861-8}}, [https://books.google.com/books?id=SsH-qdTx9pUC&dq=hp-ux+arena+allocator&pg=PA334 p. 334].</ref>
-* [[Linux]] (introduced in kernel 2.2, some distributions use [[SLUB (software)|SLUB]] allocation method over SLAB, but SLAB has better NUMA performance<ref>{{Cite web|url = https://lists.debian.org/debian-kernel/2012/03/msg00944.html|title = Re: CONFIG_SLAB=y in 3.2 kernel|date = 29 Mar 2012|accessdate = |website = |publisher = |last = Hutchings|first = Ben}}</ref>) &mdash; In Linux, slab allocation provides a kind of front-end to the [[buddy allocation|zoned buddy allocator]] for those sections of the kernel that require more flexible memory allocation than the standard 4KB page size
+* [[Linux]] (introduced in kernel 2.1.23, it's now one of three memory allocator implementations together with [[SLOB]] and [[SLUB (software)|SLUB]]. The three allocators provides a kind of front-end to the [[buddy allocation|zoned buddy allocator]] for those sections of the kernel that require more flexible memory allocation than the standard 4&nbsp;KB page size).
 * [[NetBSD]] (introduced in 4.0)
 * [[Solaris (operating system)|Solaris]] (introduced in 2.4)
@@ Line 56: / Line 59: @@
 * [[Fixed-size blocks allocation]]
 * [[Memory pool]]
-* [[SLOB]]
-* [[SLUB_(software)|SLUB]]
 ==Notes==
-{{Reflist|30em}}
+{{Reflist}}
 ==External links==
-* [http://www.FreeBSD.org/cgi/man.cgi?query=uma&apropos=0&sektion=0&manpath=FreeBSD+7.0-RELEASE&format=html FreeBSD uma(9) manual page]
+* [https://www.freebsd.org/cgi/man.cgi?query=zone&apropos=0&sektion=9&manpath=FreeBSD+12.1-RELEASE&arch=default&format=html FreeBSD uma(9) manual page]
 * [https://lwn.net/Articles/229984/ The SLUB allocator] comment about management of slabs in [[Linux kernel|Linux]] by two different allocators: SLUB allocator and SLAB allocator
 * [https://lwn.net/Articles/381677/ Memory Compaction v7] (a Linux patch set from Mel Gorman dealing with SLAB fragmentation and compaction issues, 2 April 2010)
 * [https://lwn.net/Articles/187979/ Detecting kernel memory leaks] Jonathan Corbet, Linux Weekly News, 2006; includes user comments on garbage collection
 * [http://freesoftwaremagazine.com/articles/linux_performance_linux_slow_bloated Linux performance: is Linux becoming just too slow and bloated?] On SLAB and SLUB. Free software magazine 2010.
-* [https://gitlab.com/procps-ng/procps] &mdash; includes the <code>slabtop</code> utility to display kernel slab cache information in real time
 [[Category:Memory management algorithms]]