slab.c File Reference

Slab allocator. More...

Include dependency graph for slab.c:

Go to the source code of this file.

Data Structures
struct	slab_t
Functions
	SPINLOCK_INITIALIZE (slab_cache_lock)
static	LIST_INITIALIZE (slab_cache_list)
static slab_t *	slab_space_alloc (slab_cache_t *cache, int flags)
static count_t	slab_space_free (slab_cache_t *cache, slab_t *slab)
static slab_t *	obj2slab (void *obj)
static count_t	slab_obj_destroy (slab_cache_t *cache, void *obj, slab_t *slab)
static void *	slab_obj_create (slab_cache_t *cache, int flags)
static slab_magazine_t *	get_mag_from_cache (slab_cache_t *cache, int first)
static void	put_mag_to_cache (slab_cache_t *cache, slab_magazine_t *mag)
static count_t	magazine_destroy (slab_cache_t *cache, slab_magazine_t *mag)
static slab_magazine_t *	get_full_current_mag (slab_cache_t *cache)
static void *	magazine_obj_get (slab_cache_t *cache)
static slab_magazine_t *	make_empty_current_mag (slab_cache_t *cache)
static int	magazine_obj_put (slab_cache_t *cache, void *obj)
static int	comp_objects (slab_cache_t *cache)
static int	badness (slab_cache_t *cache)
static void	make_magcache (slab_cache_t *cache)
static void	_slab_cache_create (slab_cache_t *cache, char *name, size_t size, size_t align, int(*constructor)(void *obj, int kmflag), int(*destructor)(void *obj), int flags)
slab_cache_t *	slab_cache_create (char *name, size_t size, size_t align, int(*constructor)(void *obj, int kmflag), int(*destructor)(void *obj), int flags)
static count_t	_slab_reclaim (slab_cache_t *cache, int flags)
void	slab_cache_destroy (slab_cache_t *cache)
void *	slab_alloc (slab_cache_t *cache, int flags)
static void	_slab_free (slab_cache_t *cache, void *obj, slab_t *slab)
void	slab_free (slab_cache_t *cache, void *obj)
count_t	slab_reclaim (int flags)
void	slab_print_list (void)
void	slab_cache_init (void)
void	slab_enable_cpucache (void)
void *	malloc (unsigned int size, int flags)
void	free (void *obj)
Variables
static slab_cache_t	mag_cache
static slab_cache_t	slab_cache_cache
static slab_cache_t *	slab_extern_cache
static slab_cache_t *	malloc_caches [SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1]
char *	malloc_names []

---

Detailed Description

The slab allocator is closely modelled after OpenSolaris slab allocator.

See also:

http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/

with the following exceptions:

• empty slabs are deallocated immediately (in Linux they are kept in linked list, in Solaris ???)
• empty magazines are deallocated when not needed (in Solaris they are held in linked list in slab cache)

Following features are not currently supported but would be easy to do:

• cache coloring
• dynamic magazine growing (different magazine sizes are already supported, but we would need to adjust allocation strategy)

The slab allocator supports per-CPU caches ('magazines') to facilitate good SMP scaling.

When a new object is being allocated, it is first checked, if it is available in a CPU-bound magazine. If it is not found there, it is allocated from a CPU-shared slab - if a partially full one is found, it is used, otherwise a new one is allocated.

When an object is being deallocated, it is put to a CPU-bound magazine. If there is no such magazine, a new one is allocated (if this fails, the object is deallocated into slab). If the magazine is full, it is put into cpu-shared list of magazines and a new one is allocated.

The CPU-bound magazine is actually a pair of magazines in order to avoid thrashing when somebody is allocating/deallocating 1 item at the magazine size boundary. LIFO order is enforced, which should avoid fragmentation as much as possible.

Every cache contains list of full slabs and list of partially full slabs. Empty slabs are immediately freed (thrashing will be avoided because of magazines).

The slab information structure is kept inside the data area, if possible. The cache can be marked that it should not use magazines. This is used only for slab related caches to avoid deadlocks and infinite recursion (the slab allocator uses itself for allocating all it's control structures).

The slab allocator allocates a lot of space and does not free it. When the frame allocator fails to allocate a frame, it calls slab_reclaim(). It tries 'light reclaim' first, then brutal reclaim. The light reclaim releases slabs from cpu-shared magazine-list, until at least 1 slab is deallocated in each cache (this algorithm should probably change). The brutal reclaim removes all cached objects, even from CPU-bound magazines.

TODO:
For better CPU-scaling the magazine allocation strategy should be extended. Currently, if the cache does not have magazine, it asks for non-cpu cached magazine cache to provide one. It might be feasible to add cpu-cached magazine cache (which would allocate it's magazines from non-cpu-cached mag. cache). This would provide a nice per-cpu buffer. The other possibility is to use the per-cache 'empty-magazine-list', which decreases competing for 1 per-system magazine cache.

• it might be good to add granularity of locks even to slab level, we could then try_spinlock over all partial slabs and thus improve scalability even on slab level

Definition in file slab.c.

---