A Home Cooked Memeory allocator Welcome to AHCM A Home Cooked Memeory allocation system. Why? ù Thread safe by using multiple heaps. ù Internal structures available to the user so you can perform sanity checks and detect leaking. ù A key field which can be used for identifying individual allocations ù A type field which can be used for grouping allocations ù Both fields can be used for controlled freeing ù Reduction of OS heap fragmentation by putting the larger units in blocks a multiple of a given roundup width. 1: Introduction 2: Function reference 3: Examples AHCM will make your life easy. The base functions are used in XaAES for almost 3 years without problems. Greetings, Henk Robbers. Amsterdam march 2004 Introduction The current memory allocation system of standard C is just too simple and primitive. The lack of block structuring and hence the danger of memory leakage are a constant source of misbehaviour. Another point is that the standard system is totalitarian. There is only 1 heap. AHCM can have any number of heaps, each having different access permissions and different chunk and round sizes. AHCM uses the same 2 level approach as other Atari malloc systems which reduces considerably the number of Gemdos calls. A single application level memory allocation is called a 'unit'. A Gemdos level allocation is called a 'block'. Both entities use next and prior pointers. Additionally each unit is provided with 2 identification fields. These fields make it possible to abandon the pointer driven freeing completely. In stead freeing can be done by catagorizing units. There is no longer the need of the often tedious remembering of the addresses of ALL allocated units and calling free() for each unit in turn. Handling of large units (larger then fits in the heaps chunksize): A Gemdos block of size equal to the nearest higher multiple of the heaps round size is allocated. The large unit is placed at end of the block. The excess at the beginning of the block is put in a free list. No space is wasted. When the large unit is freed, the block is shrunken to the heaps chunk size. The resulting smaller unit is put in the free list. Of course, if nothing has been allocated at the beginning, the whole block is returned to the OS. There now is a function that can free a hole bunch of units in a single streak by using one or both of those 2 identification fields. Because TOS and Mint do not provide virtual memory as yet, use of the stack for allocating dynamic memory may cause stack capacity problems. To compensate for this, AHCM provides 3 functions (XA_up, XA_new & XA_down) for use in a stack like manner. Or in a block structured manner if you wish. The system doesnt work automatically; you have to call the functions explicitely. But at least it provides a way of block structured dynamic memory that is easy to do it correct. The principle is that keeping track of memory is block structured, yet the memory itself is allocated from the heap. For efficiency and organizational reasons, the block structured functions use their own default base structure. If your version of C supports a 'new' function natively, you dont need this option. :-) Function reference ù AHCM's structures and definitions: ø XA_memory The base structure describing the heap; required by ALL calls to AHCM ø XA_block The OS level block administration ø XA_unit The user level unit administration ø XA_key Type of the 'key' and 'type' fields ù AHCM's functions: ø XA_set_base Fill out a base structure. ø XA_alloc Allocate (replaces malloc) ø XA_calloc Allocate and zeroize (replaces calloc) ø XA_free free (replaces free) ø XA_free_all Completely or selectively freeing in a heap. ø XA_up Increment the stack value in the base ø XA_new Allocate using stack value in the base for 'type' ø XA_down Free everything with a type higher than or equal to the stack value in the base, then decrement the stack value in the base ø XA_leaked Go through all allocated units in a heap ø XA_sanity Do some sanity checks on a heap ø XA_report User hook function type for processing results of XA_leaked and XA_sanity XA_set_base Description: Fill out a base structure. Declaration: void XA_set_base (XA_memory *base, size_t chunk, short round, short flags); Parameters: base: Address of the base of the heap to be filled out. Zero if only 1 heap is to be used by the program, in which case the standard base is filled out. chunk: The Gemdos chunk size to be used by this heap. The value can be changed anytime. round: A number representing the power of 2 to which chunk will be rounded up. flags: If zero AHCM will use Malloc(chunk) for allocating memory chunks. Otherwise Mxalloc(chunk, flags) will be used. The flags tell AHCM what kind of memory must be allocated for this heap. Examples of these flags: MX_STRAM 0 MX_TTRAM 1 MX_PREFSTRAM 2 MX_PREFTTRAM 3 MX_HEADER (1 << 3) MX_PRIVATE ((1 << 3) | (1 << 4)) MX_GLOBAL ((1 << 3) | (2 << 4)) MX_SUPERVISOR ((1 << 3) | (3 << 4)) MX_READABLE ((1 << 3) | (4 << 4)) XA_alloc Description: Allocate a amount of memory. Declaration: void * XA_alloc (XA_memory *base, size_t amount, XA_key key, XA_key type); Parameters: base: Address of base of the heap to be used. Zero if only 1 heap is to be used by the program, in which case the standard base is used. amount: The amount of memory in bytes that has to be allocated. key: A number defined by the user. type: Another number defined bu the user. The key should identify each allocation uniquely. The type can be used to group a number of allocations together. It is reported back by the XA_leaked and XA_sanity functions. It can also be used by the XA_free_all function for selective freeing. Return: The address of the user part of the allocated memory. Zero if the memory couldnt be allocated or if some error occurred or was detected. XA_calloc Description: Allocate a zeroized amount of memory. Declaration: void * XA_calloc (XA_memory *base, size_t items, size_t chunk, XA_key key, XA_key type); Parameters: base: Address of base of the heap to be used. Zero if only 1 heap is to be used by the program, in which case the standard base is used. chunk: A amount of memory in bytes. items: The number of 'chunk's that has to be allocated. Note that a single unit is allocated of size items*chunk. key: A number defined by the user. type: Another number defined bu the user. The user part of the allocated memory is zeroized. The key should identify each allocation uniquely. The type can be used to group a number of allocations together. It is reported back by the XA_leaked and XA_sanity functions. It can also be used by the XA_free_all function for selective freeing. Return: The address of the user part of the allocated memory. Zero if the memory couldnt be allocated or if some error occurred or was detected. XA_up Description: Increment the current stack level in the base. Declaration: void XA_up (XA_memory *base); Parameters: base: Address of base of the heap to be used. Zero if only 1 heap is to be used by the program, in which case the standard base is used. In any case the base must be different from any base used by XA_(c)alloc. If you always provide a zero base, this will automatically be the case. XA_new Description: Allocate using stack value set by XA_up Declaration: void *XA_new(XA_memory *base, size_t amount, XA_key key); Parameters: base: Address of base of the heap to be used. Zero if only 1 heap is to be used by the program, in which case the standard base is used. In any case the base must be different from any base used by XA_alloc and XA_calloc. If you always provide a zero base, this will automatically be the case. amount: The amount of memory in bytes that has to be allocated. key: A number defined by the user for unique identification of allocation. Note: The stack value in the base is used as type. XA_down Description: Free everything with a type higher than or equal to the current stack value in the base, then decrement the stack value in the base Declaration: void XA_down (XA_memory *base); Parameters: base: Address of base of the heap to be used. Zero if only 1 heap is to be used by the program, in which case the standard base is used. In any case the base must be different from any base used by XA_(c)alloc. If you always provide a zero base, this will automatically be the case. XA_free Description: Free a unit. Declaration: void XA_free (XA_memory *base, void *area); Parameters: base: Address of base of the heap to be used. Zero if only 1 heap is to be used by the program, in which case the standard base is used. area: Address of an area as returned by any of the allocation functions. XA_free_all Description: All or selective freeing in a heap. Declaration: void XA_free_all (XA_memory *base, XA_key key, XA_key type); Parameters: base: Address of base of the heap to be used. Zero if only 1 heap is to be used by the program, in which case the standard base is used. key: All units with specified key must be freed. type: All units with specified type must be freed. If both key and type are passed -1, the whole heap is freed in the fasted way possible. If -1 is specified for key or type, no check is made for that field. Which means that all units of that key cq type are considered. The relation between key and type is 'and' Example: XA_free_all(0, -1, handle) All units having handle as type are freed. XA_report Description: Type of a report function that is called by XA_leaked and XA_sanity when something reportable occurs. A fuction of the type must be written by the user. You may find a example of such a function in Examples. Declaration: typedef void XA_report (XA_memory *base, XA_block *blk, XA_unit *unit, char *txt); Parameters: base: Address of base of the heap to be used. Zero if only 1 heap is to be used by the program, in which case the standard base is used. blk: Block that is subject of the report. (if applicable) unit: Unit that is subject of the report. (if applicable) txt: A character string provided by XA_leaked and XA_sanity so ypu know where the call to the report function comes from. XA_leaked Description: Report every unit that is still allocated at the point this function is called. Normally one should call this function right before exit(). Declaration: bool XA_leaked (XA_memory *base, XA_key key, XA_key type, XA_report *report); Parameters: base: Address of base of the heap to be used. Zero if only 1 heap is to be used by the program, in which case the standard base is used. report: Address of the report function to be called for each allocated unit. key and type: Usage is same as for XA_free_all. With the exception that units are not freed, but reported in stead. ;-) XA_sanity Description: Do a sanity check on a heap. A function of this type can be written by the user. The XA_sanity in AHCM does some very basic checks and can be considered a example. For each block in the heap: First all sizes of units in the block are added up to see if units fill the block completely. This MUST be the case. Then the used list links are followed up and down (next, prior) If this process reaches the unit at which it started, the links are sane. Same is done for the free list. Declaration: void XA_sanity (XA_memory *base, XA_report *report); Parameters: base: Address of base of the heap to be used. Zero if only 1 heap is to be used by the program, in which case the standard base is used. report: Address of the report function to be called for each unit causing a error. structures ù The base structure describing the heap required by all calls to AHCM: typedef struct xa_memory { XA_block *first, *last, *cur; long chunk; short round, mode, stack; } XA_memory; ù any list of units, generalizing used and free lists typedef struct xa_list { struct xa_unit *first, *cur, *last; } XA_list; ù Administration of OS level blocks (also called 'chunks') typedef struct xa_block { long size; struct xa_block *next, *prior; XA_list used, free; short mode; XA_unit area[0]; } XA_block; ù The type of the key and type field in the AHCM units has been parameterized. This makes changing the type an easy and safe operation. Currently defined as: typedef short XA_key; ù Administration of user level blocks (also called 'units') typedef struct xa_unit { long size; struct xa_unit *next,*prior; XA_key key, type; char area[0]; } XA_unit; Examples ============================================================================ The package contains as a bridge the functions malloc, calloc, free & _FreeAll as follows: void *malloc(size_t size) { return XA_alloc(0, size, 0, 0); } void *calloc(size_t items, size_t chunk) { return XA_calloc(0, items, chunk, 0, 0); } void free(void *addr) { XA_free(0, addr); } void _FreeAll(void) { XA_free_all(0, -1, -1); } ============================================================================ Very often the allocated units all are needed at the same time all this time. (Lines or records in file as long as the file is open) This means that no individual freeing is needed. The absence of the need of individual freeing can make the allocation many times more efficient. AHCM makes such an approach possible and not too difficult. The multiple heaps originated from the need for use in asynchronous threads. They appeared to be very usefull in single threaded code as well. The advantage of the below approach is that it remains to be dynamic as a whole. The functions in the example are real. I use them in the Pure linker replacement for all symbol tables. #include "ahcm.h" typedef struct membase { XA_memory base; char *memory; size_t memorynow; size_t chunk; char *name; /* For debugging */ } MEMBASE; /* NB! blockprefix and unitprefix are from "ahcm.h" and are important. */ void init_membase(MEMBASE *mb, long chunk, char *name) { mb->chunk = chunk - blockprefix - 2*unitprefix; mb->memorynow = 2*mb->chunk; mb->memory = 0; mb->name = name; XA_set_base(&mb->base, chunk, 0, 0); } void * alloc(MEMBASE *mb, size_t new, char *remark) { char *ret; new = (new + 3) & ~3; /* 4 byte align */ if (mb->memorynow + new > mb->chunk) { mb->memory = XA_alloc(&mb->base, mb->chunk, -1, -1); if (mb->memory == 0) { mem_alert(remark); /* some warning function */ return 0; } mb->memorynow = 0; } ret = mb->memory; mb->memory += new; /* Simply put the units one after mb->memorynow += new; each other without any red tape */ return ret; } void free_membase(MEMBASE *mb) { XA_free_all(&mb->base, -1, -1); mb->memorynow = 2*mb->chunk; /* usefull high value for initial */ mb->memory = 0; } void some_function(void) { /* Define a memory base for local use */ MEMBASE mlocal; init_membase(&mlocal, 8192, "efficient local base"); ..................... while (not_ready) { any_pointer *new = alloc(&mlocal, anysize, some_remark); /* Do anything you like with any number of 'new's until you're done */ ............................................................ } ..................... free_membase(&mlocal); /* Free the whole local base in a swoop */ } ============================================================================= Example of a report function: #if __PUREC__ XA_report punit #else void punit (XA_memory *base, XA_block *blk, XA_unit *unit, char *txt) #endif { printf("**** %s: ", txt); if (!unit) printf("nil\n"); else { XA_unit *prior = unit->prior, *next = unit->next; printf(" -%d- %ld :: %ld, p:%ld :: %ld, n:%ld :: %ld, block %ld :: %ld\n", unit->key, unit, unit->size, prior, prior?prior->size:-1, next, next?next->size:-1, blk, blk->size); } } ============================================================================= Henk Robbers Henk Robbers te Amsterdam tlf: 020 4182901 mailto:h.robbers@chello.nl http://members.ams.chello.nl/h.robbers Index A A thread and leak safe memory allocation system E Examples F Function reference H Henk Robbers I Introduction S structures X XA_alloc XA_block XA_calloc XA_down XA_free XA_free_all XA_key XA_leaked XA_memory XA_memory XA_new XA_report XA_sanity XA_set_base XA_unit XA_up