klish/lub/heap/private.h

/*
 * private.h
 */
#include "lub/heap.h"
#include "lub/bintree.h"
#include "lub/types.h"
#include "lub/dblockpool.h"
#include "lub/size_fmt.h"

/**********************************************************
 * PRIVATE TYPES
 ********************************************************** */
typedef struct _lub_heap_node    lub_heap_node_t;    
typedef struct _lub_heap_context lub_heap_context_t;    
typedef struct _lub_heap_cache   lub_heap_cache_t;    

typedef enum {
    LUB_HEAP_TAINT_INITIAL = 0xBB,
    LUB_HEAP_TAINT_FREE    = 0xFF,
    LUB_HEAP_TAINT_ALLOC   = 0xAA
} lub_heap_taint_t;

typedef struct _lub_heap_stackframe stackframe_t;

/**********************************************************
 * PRIVATE TYPES
 ********************************************************** */
/* type to indicate the number of long words in a block */
typedef unsigned long                 words_t;
typedef struct lub_heap_tag_s         lub_heap_tag_t;
typedef struct lub_heap_segment_s     lub_heap_segment_t;
typedef union  lub_heap_block_u       lub_heap_block_t;
typedef struct lub_heap_alloc_block_s lub_heap_alloc_block_t;

/*
 * a special type which hold both a size and block type
 */
struct lub_heap_tag_s
{
    unsigned free    : 1; /* indicates whether free/alloc block */
    unsigned segment : 1; /* indicates boundary of segment */
    unsigned words   : 30; /* number of 4 byte words in block */
};

typedef struct lub_heap_key_s lub_heap_key_t;
struct lub_heap_key_s
{
    words_t                      words;
    const lub_heap_free_block_t *block;
};
/*
 * A specialisation of a generic block to hold free block information
 */
struct lub_heap_free_block_s
{
    lub_heap_tag_t tag;
    /*
     * node to hold this block in the size based binary tree 
     */
    lub_bintree_node_t bt_node;
    /* space holder for the trailing tag */
    lub_heap_tag_t _tail;
};

/*
 * A specialisation of a generic block to hold free block information
 */
struct lub_heap_alloc_block_s
{
    lub_heap_tag_t tag;
    /* space holder for trailing tag */
    lub_heap_tag_t memory[1];
};

/* a generic block instance */
union lub_heap_block_u
{
    lub_heap_alloc_block_t alloc;
    lub_heap_free_block_t  free;
};

/* 
 * This is the control block for a segment
 */
struct lub_heap_segment_s
{
    lub_heap_segment_t *next;
    words_t             words;
    lub_bintree_node_t  bt_node;
};

/*
 * This is the control block assigned to represent the heap instance
 */
struct lub_heap_s
{
    /*
     * A cache control block if one exists
     */
    lub_heap_cache_t *cache;
    /*
     * A binary tree of free blocks 
     */
    lub_bintree_t free_tree;
    /*
     * This is used to supress leak tracking
     */
    unsigned long suppress;
    /* 
     * statistics for this heap 
     */
    lub_heap_stats_t stats;
    /*
     * reference to next heap in the system
     */
    struct lub_heap_s *next;
    /* 
     * reference to next segment (this must be last in the structure)
     */
    lub_heap_segment_t first_segment;
};

/*---------------------------------------------------------
 * PRIVATE META DATA
 *--------------------------------------------------------- */
/*
 * a pointer to the start of data segment
 */
extern char *lub_heap_data_start;
/*
 * a pointer to the end of data segment
 */
extern char *lub_heap_data_end;

/*---------------------------------------------------------
 * PRIVATE META FUNCTIONS
 *--------------------------------------------------------- */
/*
 * This operation sends to STDOUT the textual representation
 * of the provided address in memory.
 */
extern void
    lub_heap_symShow(
        /*
         * The address of the function name to resolve
         */
        unsigned address
    );
/*
 * This operation indicates whether the function represented by the
 * specified address contains the specified string.
 */
extern bool_t
    lub_heap_symMatch(
        /*
         * The address of the function name to resolve
         */
        unsigned address,
        /*
         * The substring to match against
         */
        const char *substring
    );
/*
 * This operation fills out the current stackframe
 */
extern void
    lub_heap__get_stackframe(stackframe_t *stack,unsigned max);
/*
 * A platform implementation should scan the BSS section
 * for any memory references.
 */
extern void
    lub_heap_scan_bss(void);
/*
 * A platform implementation should scan the DATA section
 * for any memory references.
 */
extern void
    lub_heap_scan_data(void);
/*
 * If possible a platform implementation should scan the current
 * stack for any memory references.
 * NB. if a platform happens to have allocated it stack from the 
 * BSS or DATA section then this doesn't need to do anything.
 */
extern void
    lub_heap_scan_stack(void);
/*
 * This function fills out the specified memory with tainted
 * bytes if tainting is enabled for the system.
 */
extern void 
    lub_heap_taint_memory(
        /*
         * a pointer to the start of the memory to taint
         */
        char            *ptr,
        /*
         * the type of tainting to perform
         */
        lub_heap_taint_t type,
        /*
         * the number of bytes to taint
         */
        size_t           size 
    );
/*
 * If possible a platform implementation should
 * take this oportunity to write the value 0xCC 
 * to all the stacks between the high water mark 
 * and the current stack pointer.
 * This prevents any pointer droppings from hiding
 * memory leaks.
 */
extern void
    lub_heap_clean_stacks(void);

/*---------------------------------------------------------
 * PRIVATE METHODS
 *--------------------------------------------------------- */
/*
 * This operation is the raw interface for allocating/releasing memory
 * to/from the dynamic heap. Memory allocated by this call will not be
 * monitored by the leak detection code.
 *
 * It 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.
 *
 * \pre
 * - 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.
 *
 * \return 
 * - the status of the operation.
 *
 * \post
 * - 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.
 */
extern lub_heap_status_t
    lub_heap_raw_realloc(
        /*
         * The heap instance.
         */
        lub_heap_t *instance,
        /*
         * A reference to the client pointer which was previously handed out.
         */
        char **ptr,
        /*
         * The size of the requested memory
         */
        size_t size,
        /*
         * The alignment of the requested memory
         */
        lub_heap_align_t alignment);
/*
 * This is called before an actual realloc operation runs.
 * It provides the opportunity for the leak detector to release
 * any previous details and to modify the size and pointer to account
 * for its internal overheads.
 *
 * \return 
 * The number of bytes which should be allocated by the realloc call.
 *
 * \post
 * - the 'node' currently held in the database will be removed, potentially 
 *   deleting the 'context' in the process.
 * - the leak_detector will note the fact that it is wrapping a realloc
 *   call and any further calls which are invoked during the process will 
 *   NOT be monitored.
 */
extern void
    lub_heap_pre_realloc(
        /*
         * The heap instance.
         */
        lub_heap_t *instance,
        /*
         * A reference to the client pointer which was previously handed out.
         */
        char **ptr,
        /*
         * A reference to the size of the requested memory
         */
        size_t *size);
/*
 * This is called after a realloc has been done, just before the results
 * are returned to the client. 
 * It provides the opportunity for the leak detector to store details 
 * on the allocation and track it.
 *
 * \return 
 * The pointer which should be returned to the client. This will skip any
 * housekeeping details which will have been added to the start of the
 * block.
 *
 * \post
 * - the 'node' currently will be added into the database, creating a
 *   context if appropriate.
 * - the leak_detector will note the fact that the wrapping of a realloc()
 *   call has completed and will start to monitor further calls again.
 */
extern void
    lub_heap_post_realloc(
        /*
         * The heap instance
         */
        lub_heap_t *instance,
        /*
         * A reference to the client pointer which has been allocated.
         */
        char **ptr
    );
/*
 * This function clears all the current leak information from the heap
 *
 * It is also used to define the number of stack frames which are 
 * used to specify a context.
 *
 */
void
    lub_heap_clearAll(
        /*
         * The heap instance 
         */
         lub_heap_t *instance,
        /*
         * The number of stack frames to account for when evaluating
         * a context. A value of zero means "don't change"
         */
        unsigned frames
    );
/*
 * This allows the tracking of allocation failures.
 */
 void
    lub_heap_alloc_failed(lub_heap_context_t *instance);

/*
 * This allows the tracking of free failures.
 */
 void
    lub_heap_free_failed(void);

/*
 * This method slices the specified number of words off the
 * bottom of the specified free block.
 * The original block is then shrunk appropriately and the 
 * address of the new free block updated accordingly.
 * The result returned is a pointer to the requested memory.
 * If the slice cannot be taken then NULL is returned and the
 * free block is unaltered.
 *
 * It is assumed that the free block has been removed from the
 * tree prior to calling this method.
 */
extern void *
    lub_heap_slice_from_bottom(lub_heap_t             *instance,
                               lub_heap_free_block_t **ptr_block,
                               words_t                *words,
                               bool_t                  seg_start);
/* 
 * This method slices the specified number of words off the
 * top of the current free block.
 * The block is then shrunk appropriately and the assigned memory
 * is returned. The client's free block pointer is updated accordingly
 * e.g. if the request absorbs all of the free_block the client's 
 * pointer is set to NULL.
 * If there is insufficient space to slice this free block then
 * NULL is returned and the free block is unaltered.
 */
extern void *
    lub_heap_slice_from_top(lub_heap_t             *instance,
                            lub_heap_free_block_t **ptr_block,
                            words_t                *words,
                            bool_t                  seg_end);
/*
 * This method initialises a free block from some specified memory.
 */
extern void
    lub_heap_init_free_block(lub_heap_t *instance,
                             void       *ptr,
                             size_t      size,
                             bool_t      seg_start,
                             bool_t      seg_end);
/* 
 * This method takes an existing allocated block and extends it by 
 * trying to take memory from a free block immediately 
 * above it
 */
extern bool_t
    lub_heap_extend_upwards(lub_heap_t        *instance,
                            lub_heap_block_t **block,
                            words_t            words);
/* 
 * This method takes an existing allocated block and extends it by 
 * trying to take memory from a free block immediately 
 * below it
 */
extern bool_t
    lub_heap_extend_downwards(lub_heap_t        *instance,
                              lub_heap_block_t **block,
                              words_t            words);
/* 
 * This method takes an existing allocated block and extends it by 
 * trying to take memory from free blocks immediately 
 * above and below it.
 */
extern bool_t
    lub_heap_extend_both_ways(lub_heap_t        *instance,
                              lub_heap_block_t **block,
                              words_t            words);
/*
 * This method creates a new alloc block from the specified heap
 */
extern void *
    lub_heap_new_alloc_block(lub_heap_t *instance,
                             words_t     words);
extern void
    lub_heap_graft_to_top(lub_heap_t       *instance,
                          lub_heap_block_t *free_block,
                          void             *ptr,
                          words_t           words,
                          bool_t            seg_end,
                          bool_t            other_free_block);
extern void
    lub_heap_graft_to_bottom(lub_heap_t       *instance,
                             lub_heap_block_t *free_block,
                             void             *ptr,
                             words_t           words,
                             bool_t            seg_start,
                             bool_t            other_free_block);
extern lub_heap_status_t
    lub_heap_merge_with_next(lub_heap_t       *instance,
                             lub_heap_block_t *block);
extern lub_heap_status_t
    lub_heap_merge_with_previous(lub_heap_t       *instance,
                                 lub_heap_block_t *block);
extern lub_heap_status_t 
    lub_heap_new_free_block(lub_heap_t       *instance,
                            lub_heap_block_t *block);
/* 
 * Given a block reference find the trailing tag
 */
extern lub_heap_tag_t *
    lub_heap_block__get_tail(lub_heap_block_t *block);

/*
 * Find the first block reference in the specified segment
 */
lub_heap_block_t *
    lub_heap_block_getfirst(const lub_heap_segment_t *seg);
/* 
 * Given a block reference find the next one
 */
extern lub_heap_block_t *
    lub_heap_block_getnext(lub_heap_block_t *block);
/* 
 * Given a block reference find the previous one
 */
extern lub_heap_block_t *
    lub_heap_block_getprevious(lub_heap_block_t *block);
/* 
 * This checks the integrity of the current block
 * If the header and trailer values are different then
 * some form of memory corruption must have occured.
 */
extern bool_t
    lub_heap_block_check(lub_heap_block_t *block);

extern void
    lub_heap_block_getkey(const void        *clientnode,
                          lub_bintree_key_t *key);
extern void
    lub_heap_scan_all(void);

extern bool_t
    lub_heap_check_memory(lub_heap_t *instance);

extern lub_heap_block_t *
    lub_heap_block_from_ptr(char *ptr);

extern const lub_heap_segment_t *
    lub_heap_segment_findnext(const void *address);

extern void
    lub_heap_align_block(lub_heap_t      *this,
                         lub_heap_align_t alignment,
                         char           **ptr,
                         size_t          *size);
lub_heap_status_t
    lub_heap_cache_realloc(lub_heap_t      *this,
                           char           **ptr,
                           size_t           requested_size);
void
    lub_heap_cache_show(lub_heap_cache_t *this);