EGmemSlab

---

Detailed Description

This is a basic interface for slab pool managment. The idea comes from Slabs as defined in both Linux and Solaris (see "The Slab Allocator: An Object-Caching Kernel Memory Allocator", by Jeff Bonwick, Sun Microsystems), the basic idea is to provide pool for a specific type of object, and to store them in an initialized state, so that initialization and destruction only is done while growing/freeing the memory slabs, thus this approach should provide greater advantages for complitated to initialize structures. and in theory (althought not yet implemented) this structure can be managed so as to provide a shrinkable memory managment on the fly.

In this implementation we only allow small caches (i.e. objects must be smaller than EG_SLAB_LIMIT), with buffer controls and slab structures stored within a unique memory page. We could allow in the future for more flexible slabs. This implementation also uses colored slabs (see the paper for further details).

Here we can see a schematic drawing of the slab allocator structure and functions:

Version:

0.0.1

History:

• 2005-07-30
  • First Implpementation.

Files
file	eg_memslab.ex.c
file	eg_memslab.h
Data Structures
struct	EGmemSlab_t
	structure that holds the information relevant to each slab More...
struct	EGmemSlabPool_t
	structure used to store a slab memory pool More...
Defines
#define	_EGmemSlabPoolInitProfile(_EGmPl, sz)
	Initialize the profiling data of a slab pool.
#define	_EGmemSlabPoolProfile(_EGmPl)
	show profile information after clearing a pool.
#define	_XOPEN_SOURCE   600
#define	EG_SLAB_BFCNTL_SIZE   sizeof(char*)
	size of the buffer manager, this size should be memory aligned, it is used to compute the actual pointer to the object.
#define	EG_SLAB_DEBUG   0
	local debug level for the slab allocator, the lower the level, the more testing will be done.
#define	EG_SLAB_LIMIT   1023U
	maximum size of the objects that can be allocated via slab.
#define	EG_SLAB_MASK   (~0x0fffU)
	mask to detect the position of a piece of memory within a slab
#define	EG_SLAB_PAGE(ptr)   (((size_t)ptr)&EG_SLAB_MASK)
	Given a pointer, return a pointer to the beginning of the containing page.
#define	EG_SLAB_POISON   (0xdeadbeef)
	address used to check consistency if enabled
#define	EG_SLAB_PROFILE   100
	if set to one, enable profiling for the slab allocator
#define	EG_SLAB_REDUCE_TO_MALLOC   0
	if set to one, reduce the slab pool allocator to a simple malloc call
#define	EG_SLAB_SIZE   0x1000U
	size of the memory slabs (in bytes )
#define	EG_SLAB_VERBOSE   100
	local verbose level for the slab allocator, the lower the level, the more information will be printed on screen.
#define	EGmemSlabCheck(_EGmSlb)
	given a pointer to a zone within a slab, check if the slab is OK. If not, then the program will exit execution with a message. Note that this test is performed only when we are debugging.
#define	EGmemSlabClear(slab)
	given an initialized slab, clear all internally allocated memory, and leave the slab ready to be freed by 'free', this include calling the destructor for all elements in the slab.
#define	EGmemSlabGetSlab(ptr)   ((EGmemSlab_t*)(EG_SLAB_PAGE(ptr) + EG_SLAB_SIZE - EG_MEM_ALIGN(sizeof(EGmemSlab_t))))
	given a piece of memory that should be within a slab, return the pointer to the related slab structure, remember that the slab structure is at the end of the slab piece of memory.
#define	EGmemSlabInit(slab, Pool, Color)
	initialize a slab structure. This include calling the constructor for all elements in the slab. Note that this function asumes that all memory has been previously set to NULL. It will also place this slab in the list of empty slabs in the given pool.
#define	EGmemSlabPoolAlloc(Pool)
	Given a slab pool, return an element from the pool.
#define	EGmemSlabPoolClear(Pool)
	clear a slab pool and all internal sub-structures and data, no further calls to this structure are posible after this (but for freeing the memory containing this data, or to re-initialize it).
#define	EGmemSlabPoolFree(ptr)   EGmemSlabPushElement(ptr)
	Given a pointer to an element allocated through a slab pool, give it back to the pool.
#define	EGmemSlabPoolInit(pool, sz, constr_fn, dest_fn)
	initialize a slab pool as an empty pool for elements of the given size, and with te given constructor and destructors.
#define	EGmemSlabPoolShrink(Pool)
	Given a slab pool, free all unused slabs.
#define	EGmemSlabPopElement(slab)
	Given a non-full slab, extract a pointer to the next unused element in the slab, and update all internal data. and if it becomes full, then move it to the full list within the pool. Also, if debugging, poison the pointer to the enext element in the returned element. If the slab is not full, and the number of active elements is one, then move the slab to the half-full slab list in the pool.
#define	EGmemSlabPushElement(ptr)
	Given an used object within a slab, give it back to the slab for future used.
#define	EGSLB_UPDATE(a)
	add one to the given pointer, if profiling is enabled, otherwise, do nothing
Typedefs
typedef EGmemSlab_t	EGmemSlab_t
	structure that holds the information relevant to each slab
typedef EGmemSlabPool_t	EGmemSlabPool_t
	structure used to store a slab memory pool
Functions
int	main (int argc, char **argv)
	this program expect only one parameter, the number of elements to be created.
static void	my_constr (void *ptr)
static void	my_dest (void *ptr)
	simple destructor for heap connectors

---

Define Documentation

#define _EGmemSlabPoolInitProfile (  _EGmPl, sz   )

Initialize the profiling data of a slab pool. Definition at line 346 of file eg_memslab.h.

#define _EGmemSlabPoolProfile (  _EGmPl   )

show profile information after clearing a pool. Definition at line 402 of file eg_memslab.h.

#define _XOPEN_SOURCE   600

Definition at line 56 of file eg_memslab.h.

#define EG_SLAB_BFCNTL_SIZE   sizeof(char*)

size of the buffer manager, this size should be memory aligned, it is used to compute the actual pointer to the object. Definition at line 91 of file eg_memslab.h.

#define EG_SLAB_DEBUG   0

local debug level for the slab allocator, the lower the level, the more testing will be done. Definition at line 101 of file eg_memslab.h.

#define EG_SLAB_LIMIT   1023U

maximum size of the objects that can be allocated via slab. Definition at line 70 of file eg_memslab.h.

#define EG_SLAB_MASK   (~0x0fffU)

mask to detect the position of a piece of memory within a slab Definition at line 78 of file eg_memslab.h.

#define EG_SLAB_PAGE (  ptr   )     (((size_t)ptr)&EG_SLAB_MASK)

Given a pointer, return a pointer to the beginning of the containing page. Definition at line 114 of file eg_memslab.h.

#define EG_SLAB_POISON   (0xdeadbeef)

address used to check consistency if enabled Definition at line 82 of file eg_memslab.h.

#define EG_SLAB_PROFILE   100

if set to one, enable profiling for the slab allocator Definition at line 86 of file eg_memslab.h.

#define EG_SLAB_REDUCE_TO_MALLOC   0

if set to one, reduce the slab pool allocator to a simple malloc call Definition at line 107 of file eg_memslab.h.

#define EG_SLAB_SIZE   0x1000U

size of the memory slabs (in bytes ) Definition at line 74 of file eg_memslab.h.

#define EG_SLAB_VERBOSE   100

local verbose level for the slab allocator, the lower the level, the more information will be printed on screen. Definition at line 96 of file eg_memslab.h.

#define EGmemSlabCheck (  _EGmSlb   )

Value: ({\ EXIT(_EGmSlb->flags,"Slab at %p has been cleared, and can't be used", \ (void*)EG_SLAB_PAGE(_EGmSlb));\ EXIT( _EGmSlb->next_elem == (char*)EG_SLAB_POISON , "Slab at %p is "\ "poisoned", (void*)EG_SLAB_PAGE(_EGmSlb));\ EXIT(!(_EGmSlb->pool) || _EGmSlb->pool == (EGmemSlabPool_t*)EG_SLAB_POISON ,\ "Slab at %p has no pool asociated with it", \ (void*)EG_SLAB_PAGE(_EGmSlb));\ 0;}) given a pointer to a zone within a slab, check if the slab is OK. If not, then the program will exit execution with a message. Note that this test is performed only when we are debugging. Parameters: _EGmSlb  pointer within the slab memory range. Definition at line 229 of file eg_memslab.h.

#define EGmemSlabClear (  slab   )

given an initialized slab, clear all internally allocated memory, and leave the slab ready to be freed by 'free', this include calling the destructor for all elements in the slab. Parameters: slab  pointer to an area of the slab memory to be clear. Note: If debugging is enabled, then all fields will be poisoned so that subsequent use of this structure will fail (but for the free call). Also, if debugging is enabled, we will check that the slab has no element in use. Definition at line 190 of file eg_memslab.h.

#define EGmemSlabGetSlab (  ptr   )     ((EGmemSlab_t*)(EG_SLAB_PAGE(ptr) + EG_SLAB_SIZE - EG_MEM_ALIGN(sizeof(EGmemSlab_t))))

given a piece of memory that should be within a slab, return the pointer to the related slab structure, remember that the slab structure is at the end of the slab piece of memory. Definition at line 137 of file eg_memslab.h.

#define EGmemSlabInit (  slab, Pool, Color   )

Value: ({\ EGmemSlab_t*const _EGmSlb = EGmemSlabGetSlab(slab);\ const EGconstructor_f _EGconstr = (Pool)->constr;\ const size_t _EGesz = (Pool)->elem_sz;\ unsigned _EGnel = (EG_SLAB_SIZE - EG_MEM_ALIGN(sizeof(EGmemSlab_t)))/_EGesz;\ char* _EGcel = (char*)EG_SLAB_PAGE(_EGmSlb) + (Color);\ char** _EGcptr = 0;\ MESSAGE(EG_SLAB_VERBOSE,"Creating slab at %p with %u elements of effective"\ " size %zd and color %u", (void*)EG_SLAB_PAGE(_EGmSlb), _EGnel, \ _EGesz, (Color));\ _EGmSlb->n_used = 0;\ _EGmSlb->elem_sz = _EGesz;\ _EGmSlb->n_elem = _EGnel;\ _EGmSlb->flags = 0;\ _EGmSlb->color = (Color);\ _EGmSlb->next_elem = _EGcel;\ _EGmSlb->pool = (Pool);\ while(_EGnel--){\ /* call constructor for the element if provided */\ if(_EGconstr) _EGconstr(((void*)_EGcel));\ /* set the next pointer to the next element in the slab */\ _EGcptr = (char**)(_EGcel + _EGesz - EG_SLAB_BFCNTL_SIZE);\ _EGcel += _EGesz;\ *_EGcptr = _EGcel;}\ /* position the slab in the pool */\ EGeListAddAfter(&(_EGmSlb->slab_cn),&((Pool)->empty));\ /* set the next pointer of the last element in the slab to NULL */\ *_EGcptr = 0;}) initialize a slab structure. This include calling the constructor for all elements in the slab. Note that this function asumes that all memory has been previously set to NULL. It will also place this slab in the list of empty slabs in the given pool. Parameters: slab  pointer within the memory range of the slab to be initialized. Pool  Slab Pool where this slab will bellong from. The slab pool should be initialized (i.e. should have a constructor and destructor, and an element size set. Color  offset of the memory address to be used, this is for improving memory bus usage balancing. Definition at line 152 of file eg_memslab.h.

#define EGmemSlabPoolAlloc (  Pool   )

Value: ({\ EGmemSlabPool_t*const _EGmPl = (Pool);\ void* _EGSmbRf = 0;\ if(!EGeListIsEmpty(&(_EGmPl->half))) _EGSmbRf = _EGmPl->half.next;\ else{\ if(!EGeListIsEmpty(&(_EGmPl->empty))) _EGSmbRf = _EGmPl->empty.next;\ else{\ if(posix_memalign(&_EGSmbRf,EG_SLAB_SIZE,EG_SLAB_SIZE))\ EXIT(1,"posix_memalign falied");\ else{\ EGmemSlabInit(_EGSmbRf,_EGmPl,_EGmPl->c_color);\ _EGmPl->c_color += EG_MEM_ALIGNMENT;\ EGSLB_UPDATE(_EGmPl->n_slabs);\ if(_EGmPl->c_color > _EGmPl->max_color) _EGmPl->c_color = 0;}}}\ EGSLB_UPDATE(_EGmPl->n_tot);\ EGmemSlabPopElement(_EGSmbRf);}) Given a slab pool, return an element from the pool. Parameters: Pool  slab pool from where we will get the memory. Returns: pointer to an initialize element. Examples: eg_memslab.ex.c. Definition at line 459 of file eg_memslab.h.

#define EGmemSlabPoolClear (  Pool   )

Value: ({\ EGmemSlabPool_t*const _EGmPl = (Pool);\ void* _EGptr;\ while(!EGeListIsEmpty(&(_EGmPl->half))){\ _EGptr = _EGmPl->half.next;\ EGmemSlabClear(_EGptr);\ free((void*)EG_SLAB_PAGE(_EGptr));}\ while(!EGeListIsEmpty(&(_EGmPl->empty))){\ _EGptr = _EGmPl->empty.next;\ EGmemSlabClear(_EGptr);\ free((void*)EG_SLAB_PAGE(_EGptr));}\ while(!EGeListIsEmpty(&(_EGmPl->full))){\ _EGptr = _EGmPl->full.next;\ EGmemSlabClear(_EGptr);\ free((void*)EG_SLAB_PAGE(_EGptr));}\ /* profile the pool if we are prpfiling */\ _EGmemSlabPoolProfile(_EGmPl);\ /* if we are debugging, then poison the pool */\ if(EG_SLAB_DEBUG <= DEBUG){\ _EGmPl->constr = 0;\ _EGmPl->dest = 0;\ _EGmPl->elem_sz = _EGmPl->n_elem = _EGmPl->c_color = \ _EGmPl->max_color = 0;}\ ;}) clear a slab pool and all internal sub-structures and data, no further calls to this structure are posible after this (but for freeing the memory containing this data, or to re-initialize it). Parameters: Pool  slab pool to be cleared. Examples: eg_memslab.ex.c. Definition at line 411 of file eg_memslab.h.

#define EGmemSlabPoolFree (  ptr   )     EGmemSlabPushElement(ptr)

Given a pointer to an element allocated through a slab pool, give it back to the pool. Parameters: ptr  pointer to be returned to the pool. Examples: eg_memslab.ex.c. Definition at line 489 of file eg_memslab.h.

#define EGmemSlabPoolInit (  pool, sz, constr_fn, dest_fn   )

Value: ({\ EGmemSlabPool_t*const _EGmPl = (pool);\ unsigned const _EGesz = EG_MEM_ALIGN(sz)+EG_MEM_ALIGN(EG_SLAB_BFCNTL_SIZE);\ unsigned const _EGnel = (EG_SLAB_SIZE - EG_MEM_ALIGN(sizeof(EGmemSlab_t))) \ / _EGesz;\ /* check that the real element size is within bounds */\ EXIT(_EGesz > EG_SLAB_LIMIT, "element size (user %u, real %u) for slab is"\ " above limits %u", (sz), _EGesz, EG_SLAB_LIMIT);\ /* initialize the structure */\ EGeListInit(&(_EGmPl->half));\ EGeListInit(&(_EGmPl->empty));\ EGeListInit(&(_EGmPl->full));\ _EGmPl->constr = constr_fn;\ _EGmPl->dest = dest_fn;\ _EGmPl->elem_sz = _EGesz;\ _EGmPl->n_elem = _EGnel;\ _EGmPl->c_color = 0;\ _EGmPl->max_color = EG_SLAB_SIZE - EG_MEM_ALIGN(sizeof(EGmemSlab_t)) - \ (_EGnel*_EGesz);\ _EGmemSlabPoolInitProfile(_EGmPl,sz);\ /* verbose output */\ MESSAGE(EG_SLAB_VERBOSE,"Creating Slab Pool at %p:\n\tmax colors %u\n"\ "\telements per slab %u\n\tuser size %u\n\treal size %u\n", \ (void*)_EGmPl, _EGmPl->max_color, _EGnel, (sz), _EGesz);\ 0;}) initialize a slab pool as an empty pool for elements of the given size, and with te given constructor and destructors. Parameters: constr_fn  constructor fnctioin for the elements to be stored in the pool. dest_fn  destructor function for the elements to be stored in the pool. pool  pointer to the slab pool to initialize. sz  (real) size (in bytes) of the elements to be hold. in the pool. This means that sz is the result of sizeof(TYPE), where TYPE is the structure to be pooled. Examples: eg_memslab.ex.c. Definition at line 360 of file eg_memslab.h.

#define EGmemSlabPoolShrink (  Pool   )

Value: ({\ EGmemSlabPool_t*const _EGmPl = (Pool);\ void* _EGptr;\ while(!EGeListIsEmpty(&(_EGmPl->empty))){\ _EGptr = (void*)(_EGmPl->empty.next);\ EGmemSlabClear(_EGptr);\ free((void*)EG_SLAB_PAGE(_EGptr));}\ 0;}) Given a slab pool, free all unused slabs. Parameters: Pool  slab pool to be shrinked. Examples: eg_memslab.ex.c. Definition at line 495 of file eg_memslab.h.

#define EGmemSlabPopElement (  slab   )

Value: ({\ EGmemSlab_t*const _EGmSlb = EGmemSlabGetSlab(slab);\ EGmemSlabPool_t*const _EGPlRf = _EGmSlb->pool;\ void*const _EGelem = (void*)(_EGmSlb->next_elem);\ char** _EGnext_elem = (char**)(((char*)_EGelem) + _EGmSlb->elem_sz - \ EG_SLAB_BFCNTL_SIZE);\ /* some consistency checks */\ EGmemSlabCheck(_EGmSlb);\ EXITL(EG_SLAB_DEBUG, *_EGnext_elem == (char*)EG_SLAB_POISON, "Poisoned "\ "element");\ EXITL(EG_SLAB_DEBUG, _EGmSlb->n_used == _EGmSlb->n_elem, "Trying to get"\ " an element from slab at %p, but slab is full", \ (void*)EG_SLAB_PAGE(_EGmSlb));\ /* now update the slab */\ _EGmSlb->next_elem = *_EGnext_elem;\ _EGmSlb->n_used++;\ if(_EGmSlb->n_used == _EGmSlb->n_elem)\ EGeListMoveAfter(&(_EGmSlb->slab_cn),&(_EGPlRf->full));\ else if(_EGmSlb->n_used == 1U)\ EGeListMoveAfter(&(_EGmSlb->slab_cn),&(_EGPlRf->half));\ /* if debugging, poison the pointer to next in the returned element */\ if(EG_SLAB_DEBUG <= DEBUG) *_EGnext_elem = (char*)EG_SLAB_POISON;\ /* return the element */\ _EGelem;}) Given a non-full slab, extract a pointer to the next unused element in the slab, and update all internal data. and if it becomes full, then move it to the full list within the pool. Also, if debugging, poison the pointer to the enext element in the returned element. If the slab is not full, and the number of active elements is one, then move the slab to the half-full slab list in the pool. Parameters: slab  pointer within a slab memory. Returns: pointer to a void* of initialized memory by the given contructor in the slab pool. Definition at line 253 of file eg_memslab.h.

#define EGmemSlabPushElement (  ptr   )

Value: ({\ EGmemSlab_t*const _EGmSlb = EGmemSlabGetSlab(ptr);\ EGmemSlabPool_t*const _EGmPl = _EGmSlb->pool;\ void*const _EGelem = (void*)(ptr);\ char** _EGnext_elem = (char**)(((char*)_EGelem) + _EGmSlb->elem_sz - \ EG_SLAB_BFCNTL_SIZE);\ /* if debugging, check for poison in the pointer to the next element in the \ * given element */\ EXITL(EG_SLAB_DEBUG, !_EGelem, "Trying to free a NULL ptr");\ EGmemSlabCheck(_EGmSlb);\ EXITL(EG_SLAB_DEBUG, *_EGnext_elem != (char*)EG_SLAB_POISON, "This can't"\ " happen, memory %p is corrupted!", (void*)_EGelem);\ EXITL(EG_SLAB_DEBUG, !_EGmSlb->n_used, "Trying to free elements in an "\ "unused slab!");\ /* now, if the slab was full, put it as half-full */\ if(_EGmSlb->n_elem == _EGmSlb->n_used)\ EGeListMoveAfter(&(_EGmSlb->slab_cn),&(_EGmPl->half));\ /* decrease the number of used elements, and if zero, then move to the list\ * of empty slabs. */\ _EGmSlb->n_used -= 1;\ if(!(_EGmSlb->n_used))\ EGeListMoveAfter(&(_EGmSlb->slab_cn),&(_EGmPl->empty));\ /* now actually put the element into the slab */\ *_EGnext_elem = _EGmSlb->next_elem;\ _EGmSlb->next_elem = _EGelem;}) Given an used object within a slab, give it back to the slab for future used. Parameters: ptr  pointer to the element to be given back to its containing slab. Definition at line 283 of file eg_memslab.h.

#define EGSLB_UPDATE (  a   )

add one to the given pointer, if profiling is enabled, otherwise, do nothing Definition at line 442 of file eg_memslab.h.

---

Typedef Documentation

typedef struct EGmemSlab_t EGmemSlab_t

structure that holds the information relevant to each slab

typedef struct EGmemSlabPool_t EGmemSlabPool_t

structure used to store a slab memory pool

---

Function Documentation

int main (  int  argc, char **  argv )

this program expect only one parameter, the number of elements to be created. Definition at line 46 of file eg_memslab.ex.c. Here is the call graph for this function:

static void my_constr (  void *  ptr  )  [static]

brief simple destructor for heap connectors Examples: eg_memslab.ex.c. Definition at line 30 of file eg_memslab.ex.c.

static void my_dest (  void *  ptr  )  [static]

simple destructor for heap connectors Examples: eg_memslab.ex.c. Definition at line 37 of file eg_memslab.ex.c.

---