heap.html revision 90792
190792Sgshapiro<html> 290792Sgshapiro<head> 390792Sgshapiro <title>libsm : Memory Allocation</title> 490792Sgshapiro</head> 590792Sgshapiro<body> 690792Sgshapiro 790792Sgshapiro<a href="index.html">Back to libsm overview</a> 890792Sgshapiro 990792Sgshapiro<center> 1090792Sgshapiro <h1> libsm : Memory Allocation </h1> 1190792Sgshapiro <br> $Id: heap.html,v 1.9 2000/12/08 21:41:42 ca Exp $ 1290792Sgshapiro</center> 1390792Sgshapiro 1490792Sgshapiro<h2> Introduction </h2> 1590792Sgshapiro 1690792SgshapiroThe heap package provides a layer of abstraction on top of 1790792Sgshapiro<tt>malloc</tt>, <tt>realloc</tt> and <tt>free</tt> 1890792Sgshapirothat provides optional error checking and memory leak detection, 1990792Sgshapiroand which optionally raises an exception when an allocation request 2090792Sgshapirocannot be satisfied. 2190792Sgshapiro 2290792Sgshapiro<h2> Synopsis </h2> 2390792Sgshapiro 2490792Sgshapiro<pre> 2590792Sgshapiro#include <sm/heap.h> 2690792Sgshapiro 2790792Sgshapiro/* 2890792Sgshapiro** Wrappers for malloc, realloc, free 2990792Sgshapiro*/ 3090792Sgshapirovoid *sm_malloc(size_t size); 3190792Sgshapirovoid *sm_realloc(void *ptr, size_t size); 3290792Sgshapirovoid sm_free(void *ptr); 3390792Sgshapiro 3490792Sgshapiro/* 3590792Sgshapiro** Wrappers for malloc, realloc that raise an exception instead of 3690792Sgshapiro** returning NULL on heap exhaustion. 3790792Sgshapiro*/ 3890792Sgshapirovoid *sm_malloc_x(size_t size); 3990792Sgshapirovoid *sm_realloc_x(void *ptr, size_t size); 4090792Sgshapiro 4190792Sgshapiro/* 4290792Sgshapiro** Print a list of currently allocated blocks, 4390792Sgshapiro** used to diagnose memory leaks. 4490792Sgshapiro*/ 4590792Sgshapirovoid sm_heap_report(FILE *stream, int verbosity); 4690792Sgshapiro 4790792Sgshapiro/* 4890792Sgshapiro** Low level interfaces. 4990792Sgshapiro*/ 5090792Sgshapiroint sm_heap_group(); 5190792Sgshapiroint sm_heap_setgroup(int g); 5290792Sgshapiroint sm_heap_newgroup(); 5390792Sgshapirovoid *sm_malloc_tagged(size_t size, char *file, int line, int group); 5490792Sgshapirovoid *sm_malloc_tagged_x(size_t size, char *file, int line, int group); 5590792Sgshapirobool sm_heap_register(void *ptr, size_t size, char *file, int line); 5690792Sgshapiro</pre> 5790792Sgshapiro 5890792Sgshapiro<h2> How to allocate and free memory </h2> 5990792Sgshapiro 6090792Sgshapiro <tt>sm_malloc</tt>, <tt>sm_realloc</tt> and <tt>sm_free</tt> 6190792Sgshapiro are portable plug in replacements 6290792Sgshapiro for <tt>malloc</tt>, <tt>realloc</tt> and <tt>free</tt> that provide 6390792Sgshapiro error checking and memory leak detection. 6490792Sgshapiro <tt>sm_malloc_x</tt> and <tt>sm_realloc_x</tt> 6590792Sgshapiro are variants of 6690792Sgshapiro <tt>sm_malloc</tt> and <tt>sm_realloc</tt> 6790792Sgshapiro that raise an exception on error. 6890792Sgshapiro To use the package effectively, 6990792Sgshapiro all calls to <tt>malloc</tt>, <tt>realloc</tt> and <tt>free</tt> 7090792Sgshapiro should be replaced by calls 7190792Sgshapiro to the corresponding <tt>sm_</tt>* routines. 7290792Sgshapiro 7390792Sgshapiro<dl> 7490792Sgshapiro<dt> 7590792Sgshapiro<tt> void *sm_malloc(size_t size) </tt> 7690792Sgshapiro<dd> 7790792Sgshapiro This function is a plug-in replacement for <tt>malloc</tt>. 7890792Sgshapiro It allocates <tt>size</tt> bytes of memory on the heap 7990792Sgshapiro and returns a pointer to it, 8090792Sgshapiro or it returns <tt>NULL</tt> on failure. 8190792Sgshapiro <p> 8290792Sgshapiro 8390792Sgshapiro The C standard says that <tt>malloc(0)</tt> may return 8490792Sgshapiro either <tt>NULL</tt> or a non-<tt>NULL</tt> value. 8590792Sgshapiro To ensure consistent behaviour on all platforms, 8690792Sgshapiro <tt>sm_malloc(0)</tt> is equivalent to <tt>sm_malloc(1)</tt>. 8790792Sgshapiro <p> 8890792Sgshapiro 8990792Sgshapiro In addition, if heap checking is enabled, then <tt>sm_malloc</tt> 9090792Sgshapiro maintains a hash table describing all currently allocated 9190792Sgshapiro memory blocks. This table is used for argument validity 9290792Sgshapiro checking in <tt>sm_realloc</tt> and <tt>sm_free</tt>, 9390792Sgshapiro and it can be printed using <tt>sm_heap_report</tt> 9490792Sgshapiro as an aid to finding memory leaks. 9590792Sgshapiro <p> 9690792Sgshapiro 9790792Sgshapiro<dt> 9890792Sgshapiro<tt> void *sm_malloc_x(size_t size) </tt> 9990792Sgshapiro<dd> 10090792Sgshapiro This function is just like <tt>sm_malloc</tt> 10190792Sgshapiro except that it raises the <tt>SmHeapOutOfMemory</tt> exception 10290792Sgshapiro instead of returning <tt>NULL</tt> on error. 10390792Sgshapiro <p> 10490792Sgshapiro 10590792Sgshapiro<dt> 10690792Sgshapiro<tt> void *sm_realloc(void *ptr, size_t size) </tt> 10790792Sgshapiro<dd> 10890792Sgshapiro This function is a plug-in replacement for <tt>realloc</tt>. 10990792Sgshapiro If <tt>ptr</tt> is null then this call is equivalent 11090792Sgshapiro to <tt>sm_malloc(size)</tt>. 11190792Sgshapiro Otherwise, the size of the object pointed to by <tt>ptr</tt> 11290792Sgshapiro is changed to <tt>size</tt> bytes, and a pointer to the 11390792Sgshapiro (possibly moved) object is returned. 11490792Sgshapiro If the space cannot be allocated, then the object pointed to 11590792Sgshapiro by <tt>ptr</tt> is unchanged and <tt>NULL</tt> is returned. 11690792Sgshapiro <p> 11790792Sgshapiro 11890792Sgshapiro If <tt>size</tt> is 0 then we pretend that <tt>size</tt> is 1. 11990792Sgshapiro This may be a mistake. 12090792Sgshapiro <p> 12190792Sgshapiro 12290792Sgshapiro If ptr is not NULL and heap checking is enabled, 12390792Sgshapiro then ptr is required to be a value that was 12490792Sgshapiro previously returned by sm_malloc or sm_realloc, and which 12590792Sgshapiro has not yet been freed by sm_free. If this condition is not 12690792Sgshapiro met, then the program is aborted using sm_abort. 12790792Sgshapiro <p> 12890792Sgshapiro 12990792Sgshapiro<dt> 13090792Sgshapiro<tt> void *sm_realloc_x(void *ptr, size_t size) </tt> 13190792Sgshapiro<dd> 13290792Sgshapiro This function is just like <tt>sm_realloc</tt> 13390792Sgshapiro except that it raises the SmHeapOutOfMemory exception 13490792Sgshapiro instead of returning <tt>NULL</tt> on error. 13590792Sgshapiro <p> 13690792Sgshapiro 13790792Sgshapiro<dt> 13890792Sgshapiro<tt> void sm_free(void *ptr) </tt> 13990792Sgshapiro<dd> 14090792Sgshapiro This function is a plug-in replacement for free. 14190792Sgshapiro If heap checking is disabled, then this function is equivalent 14290792Sgshapiro to a call to free. Otherwise, the following additional semantics 14390792Sgshapiro apply. 14490792Sgshapiro <p> 14590792Sgshapiro 14690792Sgshapiro If ptr is NULL, this function has no effect. 14790792Sgshapiro <p> 14890792Sgshapiro 14990792Sgshapiro Otherwise, ptr is required to be a value that was 15090792Sgshapiro previously returned by sm_malloc or sm_realloc, and which 15190792Sgshapiro has not yet been freed by sm_free. If this condition is not 15290792Sgshapiro met, then the program is aborted using sm_abort. 15390792Sgshapiro <p> 15490792Sgshapiro 15590792Sgshapiro Otherwise, if there is no error, then the block pointed to by ptr 15690792Sgshapiro will be set to all zeros before free() is called. This is intended 15790792Sgshapiro to assist in detecting the use of dangling pointers. 15890792Sgshapiro</dl> 15990792Sgshapiro 16090792Sgshapiro<h2> How to control tag information </h2> 16190792Sgshapiro 16290792SgshapiroWhen heap checking is enabled, 16390792Sgshapirothe heap package maintains a hash table which associates the 16490792Sgshapirofollowing values with each currently allocated block: 16590792Sgshapiro 16690792Sgshapiro<dl> 16790792Sgshapiro<dt> 16890792Sgshapiro<tt> size_t size </tt> 16990792Sgshapiro<dd> 17090792Sgshapiro The size of the block. 17190792Sgshapiro<dt> 17290792Sgshapiro<tt> char *tag </tt> 17390792Sgshapiro<dd> 17490792Sgshapiro By default, this is the name of the source file from which 17590792Sgshapiro the block was allocated, but you can specify an arbitrary 17690792Sgshapiro string pointer, or <tt>NULL</tt>. 17790792Sgshapiro<dt> 17890792Sgshapiro<tt> int num </tt> 17990792Sgshapiro<dd> 18090792Sgshapiro By default, this is the line number from which the block was 18190792Sgshapiro allocated. 18290792Sgshapiro<dt> 18390792Sgshapiro<tt> int group </tt> 18490792Sgshapiro<dd> 18590792Sgshapiro By convention, group==0 indicates that the block is permanently 18690792Sgshapiro allocated and will never be freed. The meanings of other group 18790792Sgshapiro numbers are defined by the application developer. 18890792Sgshapiro Unless you take special action, all blocks allocated by 18990792Sgshapiro <tt>sm_malloc</tt> and <tt>sm_malloc_x</tt> will be assigned 19090792Sgshapiro to group 1. 19190792Sgshapiro</dl> 19290792Sgshapiro 19390792SgshapiroThese tag values are printed by <tt>sm_heap_report</tt>, 19490792Sgshapiroand are used to help analyze memory allocation behaviour 19590792Sgshapiroand to find memory leaks. 19690792SgshapiroThe following functions give you precise control over the 19790792Sgshapirotag values associated with each allocated block. 19890792Sgshapiro 19990792Sgshapiro<dl> 20090792Sgshapiro<dt> 20190792Sgshapiro<tt> void *sm_malloc_tagged(size_t size, int tag, int num, int group) </tt> 20290792Sgshapiro<dd> 20390792Sgshapiro Just like <tt>sm_malloc</tt>, except you directly specify 20490792Sgshapiro all of the tag values. 20590792Sgshapiro If heap checking is disabled at compile time, then a call 20690792Sgshapiro to <tt>sm_malloc_tagged</tt> is macro expanded to 20790792Sgshapiro a call to <tt>malloc</tt>. 20890792Sgshapiro <p> 20990792Sgshapiro 21090792Sgshapiro Note that the expression <tt>sm_malloc(size)</tt> is macro expanded to 21190792Sgshapiro 21290792Sgshapiro<blockquote><pre> 21390792Sgshapirosm_malloc_tagged(size, __FILE__, __LINE__, sm_heap_group()) 21490792Sgshapiro</pre></blockquote> 21590792Sgshapiro 21690792Sgshapiro<dt> 21790792Sgshapiro<tt> void *sm_malloc_tagged_x(size_t size, int tag, int num, int group) </tt> 21890792Sgshapiro<dd> 21990792Sgshapiro A variant of <tt>sm_malloc_tagged</tt> 22090792Sgshapiro that raises an exception on error. 22190792Sgshapiro A call to <tt>sm_malloc_x</tt> is macro expanded 22290792Sgshapiro to a call to <tt>sm_malloc_tagged_x</tt>. 22390792Sgshapiro <p> 22490792Sgshapiro 22590792Sgshapiro<dt> 22690792Sgshapiro<tt> int sm_heap_group() </tt> 22790792Sgshapiro<dd> 22890792Sgshapiro The heap package maintains a thread-local variable containing 22990792Sgshapiro the current group number. 23090792Sgshapiro This is the group that <tt>sm_malloc</tt> and <tt>sm_malloc_x</tt> 23190792Sgshapiro will assign a newly allocated block to. 23290792Sgshapiro The initial value of this variable is 1. 23390792Sgshapiro The current value of this variable is returned by 23490792Sgshapiro <tt>sm_heap_group()</tt>. 23590792Sgshapiro <p> 23690792Sgshapiro 23790792Sgshapiro<dt> 23890792Sgshapiro<tt> int sm_heap_setgroup(int g) </tt> 23990792Sgshapiro<dd> 24090792Sgshapiro Set the current group to the specified value. 24190792Sgshapiro</dl> 24290792Sgshapiro 24390792SgshapiroHere are two examples of how you might use these interfaces. 24490792Sgshapiro 24590792Sgshapiro<ol> 24690792Sgshapiro<li> 24790792SgshapiroOne way to detect memory leaks is to turn on heap checking 24890792Sgshapiroand call <tt>sm_heap_report(stdout,2)</tt> 24990792Sgshapirowhen the program exits. 25090792SgshapiroThis prints a list of all allocated blocks that do not belong to group 0. 25190792Sgshapiro(Blocks in group 0 are assumed to be permanently allocated, 25290792Sgshapiroand so their existence at program exit does not indicate a leak.) 25390792SgshapiroIf you want to allocate a block and assign it to group 0, 25490792Sgshapiroyou have two choices: 25590792Sgshapiro 25690792Sgshapiro<blockquote><pre> 25790792Sgshapiroint g = sm_heap_group(); 25890792Sgshapirosm_heap_setgroup(0); 25990792Sgshapirop = sm_malloc_x(size); 26090792Sgshapirosm_heap_setgroup(g); 26190792Sgshapiro</pre></blockquote> 26290792Sgshapiro 26390792Sgshapiroor 26490792Sgshapiro 26590792Sgshapiro<blockquote><pre> 26690792Sgshapirop = sm_malloc_tagged_x(size, __FILE__, __LINE__, 0); 26790792Sgshapiro</pre></blockquote> 26890792Sgshapiro 26990792Sgshapiro<li> 27090792SgshapiroSuppose you have a utility function foo_alloc which allocates 27190792Sgshapiroand initializes a 'foo' object. When sm_heap_report is called, 27290792Sgshapiroall unfreed 'foo' objects will be reported to have the same 27390792Sgshapirosource code file name and line number. 27490792SgshapiroThat might make it difficult to determine where a memory leak is. 27590792Sgshapiro<p> 27690792Sgshapiro 27790792SgshapiroHere is how you can arrange for more precise reporting for 27890792Sgshapirounfreed foo objects: 27990792Sgshapiro 28090792Sgshapiro<blockquote><pre> 28190792Sgshapiro#include <sm/heap.h> 28290792Sgshapiro 28390792Sgshapiro#if SM_HEAP_CHECK 28490792Sgshapiro# define foo_alloc_x() foo_alloc_tagged_x(__FILE__,__LINE) 28590792Sgshapiro FOO *foo_alloc_tagged_x(char *, int); 28690792Sgshapiro#else 28790792Sgshapiro FOO *foo_alloc_x(void); 28890792Sgshapiro# define foo_alloc_tagged_x(file,line) foo_alloc_x() 28990792Sgshapiro#endif 29090792Sgshapiro 29190792Sgshapiro... 29290792Sgshapiro 29390792Sgshapiro#if SM_HEAP_CHECK 29490792SgshapiroFOO * 29590792Sgshapirofoo_alloc_tagged_x(char *file, int line) 29690792Sgshapiro#else 29790792SgshapiroFOO * 29890792Sgshapirofoo_alloc_x(void) 29990792Sgshapiro#endif 30090792Sgshapiro{ 30190792Sgshapiro FOO *p; 30290792Sgshapiro 30390792Sgshapiro p = sm_malloc_tagged_x(sizeof(FOO), file, line, sm_heap_group()); 30490792Sgshapiro ... 30590792Sgshapiro return p; 30690792Sgshapiro} 30790792Sgshapiro</pre></blockquote> 30890792Sgshapiro</ol> 30990792Sgshapiro 31090792Sgshapiro<h2> How to dump the block list </h2> 31190792Sgshapiro 31290792SgshapiroTo perform memory leak detection, you need to arrange for your 31390792Sgshapiroprogram to call sm_heap_report at appropriate times. 31490792Sgshapiro 31590792Sgshapiro<dl> 31690792Sgshapiro<dt> 31790792Sgshapiro<tt> void sm_heap_report(FILE *stream, int verbosity) </tt> 31890792Sgshapiro<dd> 31990792Sgshapiro If heap checking is disabled, this function does nothing. 32090792Sgshapiro If verbosity <= 0, this function does nothing. 32190792Sgshapiro <p> 32290792Sgshapiro 32390792Sgshapiro If verbosity >= 1, then sm_heap_report prints a single line 32490792Sgshapiro to stream giving the total number of bytes currently allocated. 32590792Sgshapiro If you call sm_heap_report each time the program has reached a 32690792Sgshapiro "ground state", and the reported amount of heap storage is 32790792Sgshapiro monotonically increasing, that indicates a leak. 32890792Sgshapiro <p> 32990792Sgshapiro 33090792Sgshapiro If verbosity >= 2, then sm_heap_report additionally prints one line 33190792Sgshapiro for each block of memory currently allocated, providing that 33290792Sgshapiro the group != 0. 33390792Sgshapiro (Such blocks are assumed to be permanently allocated storage, and 33490792Sgshapiro are not reported to cut down the level of noise.) 33590792Sgshapiro <p> 33690792Sgshapiro 33790792Sgshapiro If verbosity >= 3, then sm_heap_report prints one line for each 33890792Sgshapiro allocated block, regardless of the group. 33990792Sgshapiro</dl> 34090792Sgshapiro 34190792Sgshapiro<h2> How to enable heap checking </h2> 34290792Sgshapiro 34390792SgshapiroThe overhead of using the package can be made as small as you want. 34490792SgshapiroYou have three options: 34590792Sgshapiro 34690792Sgshapiro<ol> 34790792Sgshapiro<li> 34890792Sgshapiro If you compile your software with -DSM_HEAP_CHECK=0 then 34990792Sgshapiro sm_malloc, sm_realloc and sm_free will be redefined 35090792Sgshapiro as macros that call malloc, realloc, and free. In this case, 35190792Sgshapiro there is zero overhead. 35290792Sgshapiro<li> 35390792Sgshapiro If you do not define -DSM_HEAP_CHECK=0, and you do not explicitly 35490792Sgshapiro turn on heap checking at run time, then your program will run 35590792Sgshapiro without error checking and memory leak detection, and the additional 35690792Sgshapiro cost of calling sm_malloc, sm_realloc and sm_free is a 35790792Sgshapiro function call and test. That overhead is sufficiently low that 35890792Sgshapiro the checking code can be left compiled in a production environment. 35990792Sgshapiro<li> 36090792Sgshapiro If you do not define -DSM_HEAP_CHECK=0, and you explicitly turn on 36190792Sgshapiro heap checking at run time, then the additional cost of calling 36290792Sgshapiro sm_malloc, sm_realloc and sm_free is a hash table lookup. 36390792Sgshapiro</ol> 36490792Sgshapiro 36590792Sgshapiro Here's how to modify your application to use the heap package. 36690792Sgshapiro First, change all calls to malloc, realloc and free to sm_malloc, 36790792Sgshapiro sm_realloc and sm_free. 36890792Sgshapiro Make sure that there is a -d command line option that 36990792Sgshapiro uses the libsm debug package to enable named debug options. 37090792Sgshapiro Add the following code to your program just before it calls exit, 37190792Sgshapiro or register an atexit handler function containing the following code: 37290792Sgshapiro 37390792Sgshapiro<blockquote><pre> 37490792Sgshapiro#if SM_HEAP_CHECK 37590792Sgshapiro /* dump the heap, if we are checking for memory leaks */ 37690792Sgshapiro if (sm_debug_active(&SmHeapCheck, 2)) 37790792Sgshapiro sm_heap_report(stdout, sm_debug_level(&SmHeapCheck) - 1); 37890792Sgshapiro#endif 37990792Sgshapiro</pre></blockquote> 38090792Sgshapiro 38190792Sgshapiro To turn on heap checking, use the command line option "-dsm_check_heap.1". 38290792Sgshapiro This will cause a table of all currently allocated blocks to be 38390792Sgshapiro maintained. The table is used by sm_realloc and sm_free to perform 38490792Sgshapiro validity checking on the first argument. 38590792Sgshapiro 38690792Sgshapiro <p> 38790792Sgshapiro The command line option "-dsm_check_heap.2" will cause your application 38890792Sgshapiro to invoke sm_heap_report with verbosity=1 just before exit. 38990792Sgshapiro That will print a single line reporting total storage allocation. 39090792Sgshapiro 39190792Sgshapiro <p> 39290792Sgshapiro The command line option "-dsm_check_heap.3" will cause your application 39390792Sgshapiro to invoke sm_heap_report with verbosity=2 just before exit. 39490792Sgshapiro This will print a list of all leaked blocks. 39590792Sgshapiro 39690792Sgshapiro <p> 39790792Sgshapiro The command line option "-dsm_check_heap.4" will cause your application 39890792Sgshapiro to invoke sm_heap_report with verbosity=3 just before exit. 39990792Sgshapiro This will print a list of all allocated blocks. 40090792Sgshapiro 40190792Sgshapiro<h2> Using sm_heap_register </h2> 40290792Sgshapiro 40390792Sgshapiro Suppose you call a library routine foo that allocates a block of storage 40490792Sgshapiro for you using malloc, and expects you to free the block later using 40590792Sgshapiro free. Because the storage was not allocated using sm_malloc, you 40690792Sgshapiro will normally get an abort if you try to pass the pointer to 40790792Sgshapiro sm_free. The way to fix this problem is to 'register' the pointer 40890792Sgshapiro returned by foo with the heap package, by calling sm_heap_register: 40990792Sgshapiro 41090792Sgshapiro<blockquote><pre> 41190792Sgshapirobool sm_heap_register(ptr, size, file, line, group) 41290792Sgshapiro</pre></blockquote> 41390792Sgshapiro 41490792Sgshapiro The 'ptr' argument is the pointer returned by foo. The 'size' argument 41590792Sgshapiro can be smaller than the actual size of the allocated block, but it must 41690792Sgshapiro not be larger. The file and line arguments indicate at which line of 41790792Sgshapiro source code the block was allocated, and is printed by sm_heap_report. 41890792Sgshapiro For group, you probably want to pass sm_heap_group(). 41990792Sgshapiro <p> 42090792Sgshapiro This function returns <tt>true</tt> on success, 42190792Sgshapiro or <tt>false</tt> if it failed due to heap exhaustion. 42290792Sgshapiro 42390792Sgshapiro</body> 42490792Sgshapiro</html> 425