Cache

Object Cache. More...

Collaboration diagram for Cache:

Detailed Description

Object Cache.

A object cache using CPU local SLAB allocation to improve performance of frequently allocated and deallocated objects.

Slab Allocation

The object cache uses slab allocation to allocate memory, each slab consists of a buffer in the below format:

Size	Description
sizeof(cache_slab_t)	Slab metadata
(N - 1) * sizeof(cache_bufctl_t)	Buffer control list
...	Padding
N * step	Objects

Where N is the number of objects that can fit in the slab given the object size and alignment and the step is the aligned size of the object.

Buffer Control List

The buffer control list is an alternative to a intrusive free list, which we cant use as we want free objects to remain in an initalized state.

Each index in the buffer control list corresponds to an object in the slab, and contains the index of the next free object, with the last index in the buffer control list being CACHE_BUFCTL_END.

When an object is allocated we say that the next free object is the object att the current first free objects index, and when we free an object we set its index in the buffer control list to the current first free object and then update the first free object to be the freed object.

In short, the buffer control list acts as a LIFO free list for the objects in the slab.

Minimize CPU Contention

To minimize CPU contention, each CPU has its own active slab from which it allocates and deallocates objects. It will continue using its own slab until its empty, at which point it will try to acquire a new slab from the shared cache.

Constructors and Destructors

Initializing objects, as in setting up their inital state, takes time. To avoid paying this cost on every allocation, the cache supports optional constructor and destructor functions. Such that when an object is freed, it remains in its initalized state allowins us to reuse it without reinitialization.

See also

https://en.wikipedia.org/wiki/Slab_allocation for more information.

https://www.kernel.org/doc/gorman/html/understand/understand011.html for an explanation of the Linux Kernel slab allocator.

Data Structures
struct	cache_slab_layout_t
	Cache slab layout structure. More...
struct	cache_t
	Cache structure. More...
struct	cache_slab_t
	Cache slab structure. More...
struct	cache_cpu_t
	Per-CPU cache context. More...

Macros
#define	CACHE_LIMIT   16
	Maximum number of free slabs in a cache.
#define	CACHE_BUFCTL_END   (0)
	End of buffer control list marker.
#define	CACHE_LINE   64
	Cache line size in bytes.
#define	CACHE_SLAB_PAGES   64
	Number of pages in a slab.
#define	CACHE_CREATE(_cache, _name, _size, _alignment, _ctor, _dtor)
	Macro to create a cache initializer.

Typedefs
typedef uint16_t	cache_bufctl_t
	Buffer control type.

Functions
struct	ALIGNED (CACHE_LINE)
void *	cache_alloc (cache_t *cache)
	Allocate an object from the cache.
void	cache_free (void *obj)
	Free an object back to its cache.

Variables
	cache_slab_t
	cache_cpu_t

Macro Definition Documentation

CACHE_LIMIT

#define CACHE_LIMIT   16

Maximum number of free slabs in a cache.

Definition at line 69 of file cache.h.

CACHE_BUFCTL_END

#define CACHE_BUFCTL_END   (0)

End of buffer control list marker.

Definition at line 73 of file cache.h.

CACHE_LINE

#define CACHE_LINE   64

Cache line size in bytes.

Definition at line 75 of file cache.h.

CACHE_SLAB_PAGES

#define CACHE_SLAB_PAGES   64

Number of pages in a slab.

Definition at line 77 of file cache.h.

CACHE_CREATE

#define CACHE_CREATE	(		_cache,
			_name,
			_size,
			_alignment,
			_ctor,
			_dtor
	)

Value:

    { \
        .name = (_name), \
        .size = (_size), \
        .alignment = (_alignment), \
        .layout = {0}, \
        .ctor = (_ctor), \
        .dtor = (_dtor), \
        .lock = LOCK_CREATE(), \
        .free = LIST_CREATE((_cache).free), \
        .partial = LIST_CREATE((_cache).partial), \
        .full = LIST_CREATE((_cache).full), \
        .freeCount = 0, \
        .cpus = {0}, \
    }

Macro to create a cache initializer.

Parameters

_cache	The name of the cache variable.
_name	The name of the cache, for debugging purposes.
_size	The size of each object in the cache.
_alignment	The alignment of each object in the cache.
_ctor	The constructor function for objects in the cache.
_dtor	The destructor function for objects in the cache.

Definition at line 148 of file cache.h.

Typedef Documentation

cache_bufctl_t

typedef uint16_t cache_bufctl_t

Buffer control type.

Definition at line 71 of file cache.h.

Function Documentation

ALIGNED()

struct ALIGNED

(

CACHE_LINE

)

Definition at line 71 of file cache.h.

cache_alloc()

void * cache_alloc

(

cache_t *

cache

)

Allocate an object from the cache.

The object will be constructed using the cache's constructor if one is provided.

Parameters

cache

The cache to allocate from.

Returns

Pointer to the allocated object, or NULL on failures.

Definition at line 109 of file cache.c.

Here is the call graph for this function:

Here is the caller graph for this function:

cache_free()

void cache_free

(

void *

obj

)

Free an object back to its cache.

If the cache is full and a destructor is provided then the object will be destructed.

Parameters

obj	The object to free.

Definition at line 205 of file cache.c.

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

cache_slab_t

cache_slab_t

Definition at line 105 of file cache.h.

cache_cpu_t

cache_cpu_t

Definition at line 116 of file cache.h.