Overview of Linux Memory Management Concepts: Slabs

Jim Blakey

Note: In the Linux 2.6 kernels, a new cache manager called the slub allocator is available and may replace the slab allocator described here. Either can be used through kernel configuration parameters. This paper was written a while ago and does not contain the most current kernel information. I will write an update soon - jimb

Introduction to slabs and kernel cache

Kernel modules and drivers often need to allocate temporary storage for non-persistent structures and objects, such as inodes, task structures, and device structures. These objects are uniform in size and are allocated and released many times during the life of the kernel. In earlier Unix and Linux implementations, the usual mechanisms for creating and releasing these objects were the kmalloc() and kfree() kernel calls.

However, these used an allocation scheme that was optimized for allocating and releasing pages in multiples of the hardware page size. For the small transient objects often required by the kernel and drivers, these page allocation routines were horribly inefficient, leaving the individual kernel modules and drivers responsible for optimizing their own memory usage.

One solution was to create a global kernel caching allocator which manages individual caches of identical objects on behalf of kernel modules and drivers. Each module or driver can ask the kernel cache allocator to create a private cache of a specific object type. The cache allocator handles growing each cache as needed on behalf of the module, and more importantly, the cache allocator can release unused pages back to the free pool in times when memory is in a crunch. The cache allocator works with the rest of the memory system to maintain a balance between the memory needs of each driver or module and the system as a whole.

The Linux 2.4 kernel implements a caching memory allocator to hold caches (called slabs) of identical objects. This slab allocator is basically an implementation of the "Slab Allocator" as described in UNIX Internals: The New Frontiers by Uresh Vahalia, Prentice Hall, ISBN 0-13-101908-2, with further tweaks based on a The Slab Allocator: An Object-Caching Kernel Memory Allocator, Jeff Bonwick (Sun Microsystems). presented at: USENIX Summer 1994 Technical Conference.

The following is a partial list of caches maintained by the Slab Allocator on a typical Linux 2.4 system. This information comes from the /proc/slabinfo file. Note that most kernel modules have requested their own caches. The columns are cache name, active objects, total number of objects, object size, number of full or partial pages, total allocated pages, and pages per slab.

slabinfo - version: 1.1
kmem_cache            59     78    100    2    2    1
ip_fib_hash           10    113     32    1    1    1
ip_conntrack           0      0    384    0    0    1
urb_priv               0      0     64    0    0    1
clip_arp_cache         0      0    128    0    0    1
ip_mrt_cache           0      0     96    0    0    1
tcp_tw_bucket          0     30    128    0    1    1
tcp_bind_bucket        5    113     32    1    1    1
tcp_open_request       0      0     96    0    0    1
inet_peer_cache        0      0     64    0    0    1
ip_dst_cache          23    100    192    5    5    1
arp_cache              2     30    128    1    1    1
blkdev_requests      256    520     96    7   13    1
dnotify cache          0      0     20    0    0    1
file lock cache        2     42     92    1    1    1
fasync cache           1    202     16    1    1    1
uid_cache              4    113     32    1    1    1
skbuff_head_cache     93     96    160    4    4    1
sock                 115    126   1280   40   42    1
sigqueue               0     29    132    0    1    1
cdev_cache           156    177     64    3    3    1
bdev_cache            69    118     64    2    2    1
mnt_cache             13     40     96    1    1    1
inode_cache         5561   5580    416  619  620    1
dentry_cache        7599   7620    128  254  254    1
dquot                  0      0    128    0    0    1
filp                1249   1280     96   32   32    1
names_cache            0      8   4096    0    8    1
buffer_head        15303  16920     96  422  423    1
mm_struct             47     72    160    2    3    1
vm_area_struct      1954   2183     64   34   37    1
fs_cache              46     59     64    1    1    1
files_cache           46     54    416    6    6    1


Figure 1: Typical list of caches maintained by kernel

Slab Overview

A slab is a set of one or more contiguous pages of memory set aside by the slab allocator for an individual cache. This memory is further divided into equal segments the size of the object type that the cache is managing.

Figure 2: Two page slab with 6 objects

As an example, assume a file-system driver wishes to create a cache of inodes that it can pull from. Through the kmem_cache_create() call, the slab allocator will calculate the optimal number of pages (in powers of 2) required for each slab given the inode size and other parameters. A kmem_cache_t pointer to this new inode cache is returned to the file-system driver.

When the file-system driver needs a new inode, it calls kmem_cache_alloc() with the kmem_cache_t pointer. The slab allocator will attempt to find a free inode object within the slabs currently allocated to that cache. If there are no free objects, or no slabs, then the slab allocator will grow the cache by fetching a new slab from the free page memory and returning an inode object from that.

When the file-system driver is finished with the inode object, it calls kmem_cache_free() to release the inode. The slab allocator will then mark that object within the slab as free and available.

If all objects within a slab are free, the pages that make up the slab are available to be returned to the free page pool if memory becomes tight. If more inodes are required at a later time, the slab allocator will re-grow the cache by fetching more slabs from free page memory. All of this is completely transparent to the file-system driver.

Creation and management of slab pages

Each slab of pages has an associated slab management structure. The slab_t struct is defined in /usr/src/linux/mm/slab.c has the following format:

typedef struct slab_s {
        struct list_head        list;
        unsigned long           colouroff;
        void                    *s_mem;     /* including colour offset */
        unsigned int            inuse;      /* num of objs active in slab */
        kmem_bufctl_t           free;
} slab_t;
  • list is a generic linked list structure found in /usr/include/linux/list.h. This type of list structure is used through out the Linux kernel. It contains a prev and next which are used to track of where this slab is being used. The various lists the slab_t can be on is described in the next section.

  • colouroff is an offset within the slab where the slab_t and allocated objects begin. This is part of the cache coloring described a little later.

  • s_mem is a pointer to the first object in the slab. The cache objects are contiguous from this point. Any object in the slab can be referenced by (object number * object size) + s_mem

  • inuse is a counter of the number of objects currently in use.

  • free is an integer index of the current next free object within the slab.

The slab_t structure is immediately followed by an array of kmem_bufctl_ts. There is one of these for for each object in the slab. The purpose of the kmem_bufctl_t array is to keep track of allocated and free objects within the slab. Implementations of slab allocators often have these structs containing forward/backward pointers, reference counts, pointers to the slabs they're in, etc. However, the Linux 2.4 implementation of virtual memory uses the page struct to keep track of which caches and slabs cache objects belong to, so the kmem_bufctl_t can be very simple. In fact, it is a single integer index. This array, along with the slab_t>-free member in effect implement the cache heap.

Figure 3. Off slab slab_t structure with 8 kmem_bufctl_t structs

The above figure shows the bufctl in use after several slab objects have been allocated and deleted. The next free object to be allocated will be in slot 3. Then free will assume the value in slot 3's bufctl or the value 1. So slot 1 will get the following next object allocated. Etc.

A slab_t structure may reside in the slab it describes or it may be allocated as part of the kmem_cache cache, depending on the size of the objects in the slab. Figure 2 shows an on-slab slab_t structure, where figure 3 shows on off-slab slab_t. The assumption is that if the objects in the cache are large, it is better to place the slab_t off-slab for less fragmentation and better packing of the objects. The rule is if the object size is greater than 1/8th the page size, the slab_t is allocated off-slab

The number of objects per slab (and therefore the number of pages per slab) is calculated when the cache is initially created. The driver or kernel module that asks for the cache only supplies the size of the objects to be cached, and should never have to care about how many objects there are in the cache.

The basic algorithm for calculating the number of objects in a slab is: First see how many objects fit on one page. If the left over is less than 1/8th the total slab size, then the fragmentation (or wastage) is acceptable and we're done.

If there is too much left over empty space on the first try, we try again with a larger slab. Slabs are grown in multiples of powers of 2 of the page size (kept internally as gfporder). So the first try, gfporder is 0 for 1 page, second try gfporder is 1 for 2 pages, next try gets 4 pages, next gets 8 pages, etc.

The actual algorithm used is obviously a little more complex than what I've just described. There are a lot of other factors and limits to take into account, such as whether the slab_t is kept on the slab (so its size figures into the equation), cache coloring, L1 cache alignment of the objects to reduce cache hits, etc. But the general idea is to find a balance of the number of pages in the slab and the number of objects in the slab for most efficient use of the space available.

The cache

A cache is a group of one or more slabs of object type. The structure that maintains each cache is the kmem_cache_t. The following is a partial list of important fields within the kmem_cache_t structure. This is not a complete structure, as all SMP and statistics related fields were removed for brevity. The full structure is defined in /usr/src/linux/mm/slab.c.

struct kmem_cache_s {
        struct list_head        slabs_full;
        struct list_head        slabs_partial;
        struct list_head        slabs_free;
        unsigned int            objsize;
        unsigned int            flags;  /* constant flags */
        unsigned int            num;    /* # of objs per slab */
        spinlock_t              spinlock;
        unsigned int            gfporder;
        unsigned int            gfpflags;
        size_t                  colour;         /* cache colouring range */
        unsigned int            colour_off;     /* colour offset */
        unsigned int            colour_next;    /* cache colouring */
        kmem_cache_t            *slabp_cache;
        unsigned int            growing;
        void (*ctor)(void *, kmem_cache_t *, unsigned long);
        void (*dtor)(void *, kmem_cache_t *, unsigned long);
        char                    name[CACHE_NAMELEN];
        struct list_head        next;
Where: Where:
  • slabs_full, slabs_partial,and slabs_free are lists of slabs associated with this cache.

  • objsize is the size of the objects contained within the cache.

  • num is the number of cache objects per slab. This is calculated when the cache is created as a function of the size of each object and the best fit for a given number of memory pages per slab.

  • gfporder is the number of pages per slab as a power of two. For example, for 1 page/slab, gfporder is 0, for 2 pages/slab, gfporder is 1, for 4 pages, 2, for 8 pages, 3, etc... Pages are always allocated in multiples of powers of two.

  • colour, colour_off and colour_next are used to maintain the cache coloring offset for each slab. This will be discussed later.

  • *slabp_cache is a pointer to the kernel cache that is used for the slab_t, if the slab_t is maintained off-slab.

  • growing is a flag that the cache is growing so that the memory pages won't be de-allocated.

  • ctor and dtor are driver callback routines. These are constructor and destructor routines that the driver can supply that will be called when an object is allocated or released. This allows a driver to have a custom initialization or validation routine on object allocation, or to perform any cleanup before an object is released. These are also very useful for driver debugging.

  • name is a string describing the cache. This will be printed as part of the /proc/slabinfo file. See Slab Figure 1.

  • next is a list_struct pointer to the next cache in the kernel cache chain.

Figure 4. kmem_cache_t and its associated slabs

TODO: Add a couple of paragraphs describing use here

Cache Coloring of Slabs

Cache Coloring is a method to ensure that access to the slabs in kernel memory make the best use of the processor L1 cache. This is a performance tweak to try to ensure that we take as few cache hits as possible. Since slabs begin on page boundaries, it is likely that the objects within several different slab pages map to the same cache line, called 'false sharing'. This leads to less than optimal hardware cache performance. By offsetting each beginning of the first object within each slab by some fragment of the hardware cache line size, processor cache hits are reduced.

Figure 5. Cache Coloring within slabs

The kmalloc() Interface

Of course, there are times when a kernel module or driver needs to allocate memory for an object that doesn't fit one of the uniform types of the other caches, for example string buffers, one-off structures, temporary storage, etc. For those instances drivers and kernel modules use the kmalloc() and kfree() routines. The Linux kernel ties these calls into the slab allocator too.

On initialization, the kernel asks the slab allocator to create several caches of varying sizes for this purpose. Caches for generic objects of 32, 64, 128, 256, all the way to 131072 bytes are created for both the GFP_NORMAL and GFP_DMA zones of memory.

Figure 6: Use of the cache_sizes array

When a kernel module or driver needs memory, the cache_sizes array is searched to find the cache with the size appropriate to fit the requested object. For example, if a driver requests 166 bytes of GFP_NORMAL memory through kmalloc(), an object from the 256 byte cache would be returned.

When kfree() is called to release the object, the page the object resides in is calculated. Then the page struct for that page is referenced from mem_map (which was set up to point to our kmem_cache_t and slab_t pointers when the slab was allocated). Since we now have the slab and cache for the object, we an release it with __kmem_cache_free().

TODO: Add a summary paragraph here