heap
["Little Useful Bits" Library]

This is a generic heap manager which incorporates a memory leak detection system which can monitor and report the dynamic memory which is in use for each heap. More...

Data Structures

struct  lub_heap_stats_s

Defines

#define LUB_HEAP_ZERO_ALLOC   ((void*)-1)

Typedefs

typedef lub_heap_s lub_heap_t
typedef lub_heap_free_block_s lub_heap_free_block_t
typedef lub_heap_stats_s lub_heap_stats_t
typedef void lub_heap_foreach_fn (void *block, unsigned index, size_t size, void *arg)

Enumerations

enum  lub_heap_status_t {
  LUB_HEAP_OK, LUB_HEAP_FAILED, LUB_HEAP_DOUBLE_FREE, LUB_HEAP_CORRUPTED,
  LUB_HEAP_INVALID_POINTER
}
enum  lub_heap_align_t {
  LUB_HEAP_ALIGN_NATIVE = sizeof(struct {void *ptr;}), LUB_HEAP_ALIGN_4 = 0x00000004, LUB_HEAP_ALIGN_8 = 0x00000008, LUB_HEAP_ALIGN_16 = 0x00000010,
  LUB_HEAP_ALIGN_32 = 0x00000020, LUB_HEAP_ALIGN_64 = 0x00000040, LUB_HEAP_ALIGN_128 = 0x00000080, LUB_HEAP_ALIGN_256 = 0x00000100,
  LUB_HEAP_ALIGN_512 = 0x00000200, LUB_HEAP_ALIGN_1024 = 0x00000400, LUB_HEAP_ALIGN_2048 = 0x00000800, LUB_HEAP_ALIGN_4096 = 0x00001000,
  LUB_HEAP_ALIGN_8192 = 0x00002000, LUB_HEAP_ALIGN_16384 = 0x00004000, LUB_HEAP_ALIGN_32768 = 0x00008000
}
enum  lub_heap_show_e { LUB_HEAP_SHOW_LEAKS, LUB_HEAP_SHOW_PARTIALS, LUB_HEAP_SHOW_ALL }

Functions

void lub_heap_foreach_segment (lub_heap_t *instance, lub_heap_foreach_fn *fn, void *arg)
void lub_heap_foreach_free_block (lub_heap_t *instance, lub_heap_foreach_fn *fn, void *arg)
lub_heap_t * lub_heap_create (void *start, size_t size)
void lub_heap_add_segment (lub_heap_t *instance, void *start, size_t size)
void * lub_heap_static_alloc (lub_heap_t *instance, size_t size)
lub_heap_status_t lub_heap_realloc (lub_heap_t *instance, char **ptr, size_t size, lub_heap_align_t alignment)
bool_t lub_heap_taint (bool_t enable)
bool_t lub_heap_is_tainting (void)
bool_t lub_heap_check (bool_t enable)
bool_t lub_heap_is_checking (void)
bool_t lub_heap_check_memory (lub_heap_t *this)
void lub_heap_stop_here (lub_heap_status_t status, char *old_ptr, size_t new_size)
void lub_heap__get_stats (lub_heap_t *instance, lub_heap_stats_t *stats)
void lub_heap_show (lub_heap_t *instance, bool_t verbose)
size_t lub_heap__get_max_free (lub_heap_t *instance)
size_t lub_heap__get_block_overhead (void)
size_t lub_heap__get_block_size (const void *ptr)
void lub_heap_show_leaks (lub_heap_show_e how)
void lub_heap__set_framecount (unsigned framecount)
unsigned lub_heap__get_framecount (void)
bool_t lub_heap_validate_pointer (lub_heap_t *this, char *ptr)

Detailed Description

This is a generic heap manager which incorporates a memory leak detection system which can monitor and report the dynamic memory which is in use for each heap.

A client creates an instance of heap; providing it with memory segments to manage. Subsequent operations can then be invoked to obtain memory from those registered segments.

Static allocation

Static memory allocations are those which are for the lifetime of the heap from which they are allocated. Because they do not need to be freed there is zero overhead required for such blocks; they can be exactly butted up against each other in memory. There is also zero fragmentation as they are never freed.

Dynamic allocation

Dynamic memory allocations have a lifetime less than that of the heap from which they are allocated. In order to manage the reuse of this blocks once they are released, there will be a slight "housekeeping" overhead associated with each block. They are also suceptible to fragmentation, which can occur when the lifetimes of blocks differ from one another.

Leak Detection

It monitors the dynamic allocation which are performed and maintains statistics to help identify and isolation memory leaks.

It detects two types of leak by scanning the BSS and DATA segments and identifying any nodes referenced from there. Then each of these referenced nodes is scanned to look for further references.

Full Leak

there is no reference to a block of memory or to any memory within that block in the system.

Partial Leak

there is no reference to the start of a block of memory. NB. there may be circumstances where this is not a real leak, e.g. memory allocation systems typically hand out references just beyond a control header to their clients. However there may also be instances where this is a real leak and someone just happens to have a reference to some contained data.

Memory Tainting

Memory is deliberately dirtied in the following ways:

Utility functions

Currently the following utility functions are available:

Implementation

Static and dynamic blocks are allocated from opposite ends of a memory segment. As static blocks are allocated the end of the last "free block" migrates downwards in memory. Dynamic blocks are allocated from the start of the appropriately sized free block, hence leaving space for static allocations at the end of the heap memory.

The heap implements a "best fit" model, for allocation of dynamic memory. This means that free blocks are maintained in size order and hence the most appropriate one can be used to satisfy client requests. This minimises fragmentation of the dynamically allocated memory.

The free blocks are held in a binary tree (using bintree) which provide fast searching for the appropriate block.

Author:
Graeme McKerrell
Date:
Created On : Wed Dec 14 10:20:00 2005
Version:
UNTESTED

Define Documentation

#define LUB_HEAP_ZERO_ALLOC   ((void*)-1)
 

This 'magic' pointer is returned when a client requests zero bytes The client can see that the allocation has succeeded, but cannot use the "memory" returned. This pointer may be passed transparently back to lub_heap_realloc() without impact.

Typedef Documentation

typedef void lub_heap_foreach_fn(void *block,unsigned index,size_t size,void *arg)
 

This type defines a function prototype to be used to iterate around each of a number of things in the system.

typedef struct lub_heap_free_block_s lub_heap_free_block_t
 

This type is used to reference an instance of a free block

typedef struct lub_heap_stats_s lub_heap_stats_t
 

This type defines the statistics available for each heap.

typedef struct lub_heap_s lub_heap_t
 

This type is used to reference an instance of a heap.

Enumeration Type Documentation

enum lub_heap_align_t
 

This type is used to indicate the alignment required for a memory allocation.

Enumerator:
LUB_HEAP_ALIGN_NATIVE  This is the "native" alignment required for the current CPU architecture.
LUB_HEAP_ALIGN_4  4 byte alignment
LUB_HEAP_ALIGN_8  8 byte alignment
LUB_HEAP_ALIGN_16  16 byte alignment
LUB_HEAP_ALIGN_32  32 byte alignment
LUB_HEAP_ALIGN_64  64 byte alignment
LUB_HEAP_ALIGN_128  128 byte alignment
LUB_HEAP_ALIGN_256  256 byte alignment
LUB_HEAP_ALIGN_512  512 byte alignment
LUB_HEAP_ALIGN_1024  1024 byte alignment
LUB_HEAP_ALIGN_2048  2048 byte alignment
LUB_HEAP_ALIGN_4096  4096 byte alignment
LUB_HEAP_ALIGN_8192  8192 byte alignment
LUB_HEAP_ALIGN_16384  16384 byte alignment
LUB_HEAP_ALIGN_32768  32768 byte alignment

enum lub_heap_show_e
 

This type defines how leak details should be displayed

Enumerator:
LUB_HEAP_SHOW_LEAKS  Only show allocations which have no reference elsewhere in the system
LUB_HEAP_SHOW_PARTIALS  Only show allocations which have no direct reference elsewhere in the system, but do have their contents referenced.
LUB_HEAP_SHOW_ALL  Show all the current allocations in the system.

enum lub_heap_status_t
 

This type is used to indicate the result of a dynamic memory allocation

Enumerator:
LUB_HEAP_OK  The allocation was successful
LUB_HEAP_FAILED  There was insufficient resource to satisfy the request
LUB_HEAP_DOUBLE_FREE  An attempt has been made to release an already freed block of memory.
LUB_HEAP_CORRUPTED  A memory corruption has been detected. e.g. someone writing beyond the bounds of an allocated block of memory.
LUB_HEAP_INVALID_POINTER  The client has passed in an invalid pointer i.e. one which lies outside the bounds of the current heap.

Function Documentation

size_t lub_heap__get_max_free (  lub_heap_t *  instance  ) 
 

This method provides the size, in bytes, of the largest allocation which can be performed.

Precondition:
  • The heap needs to have been created with an initial memory segment.
Returns:
  • size of largest possible allocation.
Postcondition:
  • none
Parameters:
instance  The instance on which to operate

void lub_heap__get_stats (  lub_heap_t *  instance,
lub_heap_stats_t *  stats
) 
 

This operation fills out a statistics structure with the details for the specified heap.

Precondition:
  • none
Postcondition:
  • the results filled out are a snapshot of the statistics as the time of the call.
Parameters:
instance  The instance on which to operate
stats  A client provided structure to fill out with the heap details

void lub_heap__set_framecount (  unsigned  framecount  ) 
 

Parameters:
framecount  The new framecount to use

void lub_heap_add_segment (  lub_heap_t *  instance,
void *  start,
size_t  size
) 
 

This operation augments an existing heap with some more memory to manage.

Precondition:
  • The heap needs to have been create with an initial memory segment.
Returns:
  • none
Postcondition:
  • The new segment of memory becomes available for use by this heap.
Parameters:
instance  The heap instance on which to operate
start  The beginning of the memory segment to be managed
size  The number of bytes available for use in this segment

bool_t lub_heap_check (  bool_t  enable  ) 
 

This operation controls runtime heap corruption detection. This means that during every heap operation a full check is done of the specified heap, before any allocations/free are performed. This has a performance overhead but provides a valuable aid in finding a memory corrupting client. Corruption will be spotted the first time a memory operation is performed AFTER it has occured.

By default checking is switched off.

Precondition:
  • none
Returns:
  • last checking status
Postcondition:
  • (enabled) the heap will have been scanned for any corruption and if found the return status of the invoking heap operation will be LUB_HEAP_CORRUPTED.
  • (disabled) no entire heap memory checking will occur.
Parameters:
enable  BOOL_TRUE to enable checking or BOOL_FALSE to disable

bool_t lub_heap_check_memory (  lub_heap_t *  this  ) 
 

This operation checks the integrety of the memory in the specified heap. Corruption will be spotted the first time a check is performed AFTER it has occured.

Precondition:
  • the specified heap will have been created
Returns:
  • BOOL_TRUE if the heap is OK
  • BOOL_FALSE if the heap is corrupted.
Postcondition:
  • none

lub_heap_t* lub_heap_create (  void *  start,
size_t  size
) 
 

This operation creates a dynamic heap from the provided memory segment.

Precondition:
  • none
Returns:
  • a reference to a heap object which can be used to allocate memory from the segments associated with this heap.
Postcondition:
  • memory allocations can be invoked on the returned intance.
  • further memory segements can be augmented to the heap using the lub_heap_add_segment() operation.
Parameters:
start  The begining of the first memory segment to associate with this heap
size  The number of bytes available for use in the first segment.

void lub_heap_foreach_free_block (  lub_heap_t *  instance,
lub_heap_foreach_fn *  fn,
void *  arg
) 
 

This operation is a diagnostic which can be used to iterate around all the free blocks in the specified heap. For example it may be desirable to output information about each of the free blocks present.

Precondition:
  • The heap needs to have been create with an initial memory segment.
Returns:
  • none
Postcondition:
-The specified function will have been called once for every free block in the specified heap
Parameters:
instance  The heap instance on which to operate
fn  The client provided function to call for each free block
arg  Some client specific data to pass through to the callback function.

void lub_heap_foreach_segment (  lub_heap_t *  instance,
lub_heap_foreach_fn *  fn,
void *  arg
) 
 

This operation is a diagnostic which can be used to iterate around all the segments in the specified heap. For example it may be desirable to output information about each of the segments present.

Precondition:
  • The heap needs to have been create with an initial memory segment.
Returns:
  • none
Postcondition:
-The specified function will have been called once for every segment in the specified heap
Parameters:
instance  The heap instance on which to operate
fn  The client provided function to call for each free block
arg  Some client specific data to pass through to the callback function.

bool_t lub_heap_is_checking (  void   ) 
 

This operation indicates the current status of the full memory checking facility.

Precondition:
none
Returns:
  • BOOL_TRUE if full memory checking is enabled.
  • BOOL_FALSE if full memory checking is disabled.
Postcondition:
none

bool_t lub_heap_is_tainting (  void   ) 
 

This operation indicates the current status of the memory tainting facility

Precondition:
none
Returns:
  • BOOL_TRUE if memory tainting is enabled.
  • BOOL_FALSE if memory tainting is disabled.
Postcondition:
none

lub_heap_status_t lub_heap_realloc (  lub_heap_t *  instance,
char **  ptr,
size_t  size,
lub_heap_align_t  alignment
) 
 

This operation changes the size of the object referenced by a passed in pointer to "size". The contents will be unchanged up to the minimum of the old and new sizes. If the new size is larger, the new space is uninitialised.

Precondition:
  • The heap needs to have been created with an initial memory segment.
  • If "*ptr" contains a non-NULL value then this MUST have been allocated using this operation, from the same heap instance.
Returns:
  • the status of the operation.
Postcondition:
  • The client takes responsiblity for releasing any allocated memory when they are finished with it.
  • If *ptr contains a non-NULL value, then after a succesfull call, the initial memory referenced by it may have been released for reuse, and the pointer modified to reference some new memory.
  • *ptr may contain NULL in which case no memory will be released back to the heap for reuse, and the pointer is filled out with the allocated memory.
  • (size == 0) No new memory will be allocated, *ptr will be set to NULL, and any original memory referenced by it will have been released.
Parameters:
instance  The heap instance on which to operate
ptr  Reference to a pointer containing previously allocated memory or NULL.
size  The number of bytes required for the object
alignment  The alignement required for a new allocations.

void lub_heap_show (  lub_heap_t *  instance,
bool_t  verbose
) 
 

This operation dumps the salient details of the specified heap to stdout

Parameters:
instance  The instance on which to operate
verbose  Whether to be verbose or not

void lub_heap_show_leaks (  lub_heap_show_e  how  ) 
 

This function dumps all the context details for the heap to stdout. how is one of the following values: 0 - show only leaks 1 - show partial leaks (no references to the start of the block) 2 - show all allocations (VERY VERBOSE)

Parameters:
how  how to display the details

void* lub_heap_static_alloc (  lub_heap_t *  instance,
size_t  size
) 
 

This operation allocates some "static" memory from a heap. This is memory which will remain allocted for the lifetime of the heap instance. "static" memory allocation has zero overhead and causes zero fragmentation.

NB. static allocation are only handed out from the first memory segment

Precondition:
  • The heap needs to have been created with an initial memory segment.
Returns:
  • a pointer to some "static" memory which will be fixed for the remaining lifetime of this heap.
Postcondition:
  • The client cannot ever free this memory although if the heap is managing memory which itself has been dynamically allocated, then the memory will be recovered when the heap is released.
Parameters:
instance  The heap instance on which to operate
size  The number of bytes to allocate

void lub_heap_stop_here (  lub_heap_status_t  status,
char *  old_ptr,
size_t  new_size
) 
 

This function is invoked whenever a call to lub_heap_realloc() fails. It is provided as a debugging aid; simple set a breakpoint to stop execution of the program and any failures will be caught in context.

Parameters:
status  The failure status of the the call to realloc
old_ptr  The old value of the pointer passed in
new_size  The requested number of bytes

bool_t lub_heap_taint (  bool_t  enable  ) 
 

This operation controls the tainted memory facility. This means that during certain heap operations memory can be filled with some well defined bit patterns. This causes a slight performance overhead but can be used to shake out bugs such and free-memory-reads and uninitialised-memory-reads

By default tainting is switched off.

Precondition:
  • none
Returns:
  • last tainted status
Postcondition:
  • (enabled) when a memory segment is given to a heap (either at creation or later) the contents will be set to 0xBB
  • (enabled) when some dynamically allocated memory is released back to a heap the contents will be set to 0xFF
  • (enabled) when some dynamic or static memory is allocated the contents will be set to 0xAA as the "uninitialised" value.
  • (disabled) no memory tainting will occur.
Parameters:
enable  BOOL_TRUE to enable tainting or BOOL_FALSE to disable

Generated on Fri Jun 2 10:49:39 2006 for CLISH by  doxygen 1.4.6