https://ldn.linuxfoundation.org/article/anatomy-linux-slab-allocator-0Anatomy of the Linux Slab AllocatorGood operating system performance depends in part on the operating system's ability to efficiently manage resources. In the old days, heap memory managers were the norm, but performance suffered due to fragmentation and the need for memory reclamation. Today, the Linux kernel uses a method that originated in Solaris but has been used in embedded systems for quite some time, allocating memory as objects based on their size. This article explores the ideas behind the slab allocator and examines its interfaces and their use. By M. Tim Jones Dynamic Memory ManagementThe goal of memory management is to provide a method by which memory can be dynamically shared amongst a variety of users for a variety of purposes. The memory management method should do both of the following:
Memory management is ultimately a zero-sum game of tradeoffs. You can develop an algorithm that uses little memory for management but takes more time to manage the available memory. You can also develop an algorithm that efficiently manages memory but uses a bit more memory. In the end, the requirements for the particular application drive the balance of the tradeoffs. Early memory managers used a heap-based allocation strategy. In this method, a large block of memory (called the heap) is used to provide memory for user-defined purposes. When users need a block of memory, they make a request for a given size. The heap manager looks at the available memory (using a particular algorithm) and returns the block. Some of the algorithms used in this search are the first-fit (the first block encountered in the heap that satisfies the request), and the best-fit (the best block in the heap that satisfies the request). When the users are finished with the memory, they return it to the heap. The fundamental problem with this heap-based allocation strategy is fragmentation. As blocks of memory are allocated, they are returned in different orders and at different times. This tends to leave holes in the heap requiring more time to efficiently manage the free memory. This algorithm tends to be memory efficient (allocating what's necessary) but requires more time to manage the heap. Another approach, called buddy memory allocation, is a faster memory technique that divides memory into power-of-2 partitions and attempts to allocate memory requests using a best-fit approach. When memory is freed by the user, the buddy block is checked to see if any of its contiguous neighbors have also been freed. If so, the blocks are combined to minimize fragmentation. This algorithm tends to be a bit more time efficient but can waste memory due to the best-fit approach. This article focuses on Linux kernel memory management and, in particular, the mechanisms provided through slab allocation. The
slab allocator used in Linux is based on an algorithm first introduced
by Jeff Bonwick for the SunOS operating system. Jeff's allocator
revolves around object caching. Within a kernel, a considerable amount
of memory is allocated for a finite set of objects such as file
descriptors and other common structures. Jeff found that the amount of
time required to initialize a regular object in the kernel exceeded the
amount of time required to allocate and deallocate it. His conclusion
was that instead of freeing the memory back to a global pool, he would
have the memory remain initialized for its intended purpose. For
example, if memory is being allocated for a mutex, the mutex
initialization function ( The Linux slab allocator uses these ideas and others to build a memory allocator that is efficient in both space and time. Figure 1 illustrates the high-level organization of the slab
structures. At the highest level is the
Figure 1: The major structures of the slab allocator Each cache contains a list of slabs, which are contiguous blocks of memory (typically pages). Three slabs exist:
Note that the slabs on the Each slab in the slab list is a contiguous block of memory (one or more contiguous pages) that is divided into objects. These objects are the fundamental elements that are allocated and deallocated from the particular cache. Note that the slab is the smallest allocation to the slab allocator, so if it needs to grow, this is the minimum by which it will grow. Typically, numerous objects are allocated per slab. As
objects are allocated and deallocated from a slab, the individual slab
can move between the slab lists. For example, when all objects are
consumed in a slab, it moves from the Motivation Behind the SlabThe slab cache allocator provides a number of benefits over traditional memory management schemes. First, kernels commonly rely on the allocation of small objects that are allocated numerous times over the lifetime of the system. The slab cache allocator provides this through the caching of similarly sized objects, thus avoiding the fragmentation problems that commonly occur. The slab allocator also supports the initialization of common objects, thus avoiding the need to repeatedly initialize an object for the same purpose. Finally, the slab allocator supports hardware cache alignment and coloring, which allows objects in different caches to occupy the same cache lines for increased cache utilization and better performance. Now on to the application program interface (API) for creating new slab caches, adding memory to the caches, destroying the caches, as well as the functions to allocate and deallocate objects from them. The first step is to create your slab cache structure, which you can create statically as: static struct kmem_cache *my_cachep;
This reference is then used by the other slab cache functions for
creation, deletion, allocation, and so on. The Kernel function struct kmem_cache *
kmem_cache_create( const char *name, size_t size, size_t align,
unsigned long flags;
void (*ctor)(void*, struct kmem_cache *, unsigned long),
void (*dtor)(void*, struct kmem_cache *, unsigned long));
The Table 1. Partial list of options for
The After the cache is created, its reference is returned by the Kernel function void kmem_cache_destroy( struct kmem_cache *cachep ); To allocate an object from a named cache, the void* kmem_cache_alloc( struct kmem_cache *cachep, gfp_t flags ); This function returns an object from the cache. Note that if
the cache is currently empty, this function may invoke
The kernel function To free an object back to the slab, the void kmem_cache_free( struct kmem_cache *cachep, void *objp ); The most common memory management functions in the kernel are the void *kmalloc( size_t size, int flags ); void kfree( const void *objp ); Note that in
The slab cache API provides a number of other useful functions. The unsigned int kmem_cache_size( struct kmem_cache *cachep ); const char *kmem_cache_name( struct kmem_cache *cachep ); int kmem_cache_shrink( struct kmem_cache *cachep ); Example Use of the Slab CacheThe
following code snippets demonstrate the creation of a new slab cache,
allocating and deallocating objects from the cache, and then destroying
the cache. To begin, a
static struct kmem_cache *my_cachep;
static void init_my_cache( void )
{
my_cachep = kmem_cache_create(
"my_cache", /* Name */
32, /* Object Size */
0, /* Alignment */
SLAB_HWCACHE_ALIGN, /* Flags */
NULL, NULL ); /* Constructor/Deconstructor */
return;
}
With your slab cache allocated, you can now allocate an object from it. Listing 2 provides an example of allocating and deallocating an object from the cache. It also demonstrates two of the miscellaneous functions.
int slab_test( void )
{
void *object;
printk( "Cache name is %s\n", kmem_cache_name( my_cachep ) );
printk( "Cache object size is %d\n", kmem_cache_size( my_cachep ) );
object = kmem_cache_alloc( my_cachep, GFP_KERNEL );
if (object) {
kmem_cache_free( my_cachep, object );
}
return 0;
}
Finally, Listing 3 is an example of destroying a slab cache. The caller must ensure that no attempts to allocate objects from the cache are performed during the destroy operation.
static void remove_my_cache( void )
{
if (my_cachep) kmem_cache_destroy( my_cachep );
return;
}
The proc file system provides a simple way to monitor all slab caches that are active in the system. This file, called /proc/slabinfo, provides detailed information about all slab caches in addition to providing a few tunables that are accessible from user space. The current version of slabinfo provides a header so that the output is a bit more readable. For each slab cache in the system, the number of objects, number of active objects, and the object size is provided (in addition to the objects and pages per slab). A set of tunables and slab data are also provided. To tune a particular slab cache, simply echo the slab cache name and the three tunable parameters as a string to the /proc/slabinfo file. The following example illustrates how to increase the limit and batchcount while leaving the shared factor as is (format is "cache name limit batchcount shared factor"): # echo "my_cache 128 64 8" > /proc/slabinfo
The Note that you must have superuser privileges to tune parameters in the proc file system for a slab cache. For
small embedded systems, a slab emulation layer exists called the SLOB.
This slab replacement is advantageous in small embedded Linux systems,
but while it conserves up to 512KB of memory, it suffers from
fragmentation and poor scaling. When Going FurtherThe source code for the slab cache allocator is actually one of the more readable aspects of the Linux kernel. Outside of the indirection that exists in the function calls, the source is intuitive and, in general, well commented. If you'd like to know more about the slab cache allocator, I suggest that you start there as it's the most up-to-date documentation on the mechanism. The Resources section below offers a number of sources that describe the slab cache allocator, but unfortunately all of them are out of date given the current 2.6 implementation. ResourcesLearn
Get products and technologies
Discuss
About the Author
| |||||||||||||||||||||||||||||||||
