Managing the Heap
Published in Computer Language, February 1990
Introduction
Experienced C programmers generally have a love/hate relationship with the heap. The memory allocation routines used to allocate and free up memory from the heap are usually fast and efficient. There is very little overhead to contend with when allocating or accessing blocks. And most of the memory allocation routines are now standardized in the ANSI C draft, so code that uses these routines can be considered to be very portable.
But the simplicity underlying the heap memory routines can also be responsible for a host of nasty programming problems. Some of the heap use problems that have caused me a lot of trouble over the years include:
- Using space beyond the end of an allocated memory block. Or similarly, using space before the start of a memory block.
- Neglecting to free blocks when done with them, eventually resulting in an allocation failure.
- Fragmenting the heap. Since allocated memory blocks can’t be moved, fragmentation can cut way down on the largest block size available from the heap.
- Allocation problems caused by library modules that I don’t have control over.
These problems just represent my personal highlights. The heap presents the programmer with virtually limitless opportunities for error. The actual damage done is only limited by our creativity.
This article describes a system I have used that helps detect these and other common memory use errors. By simply adding a single include file to each module being tested, a heap manager debugger system is put in place, without requiring any modification of existing source code.
Know Your Enemy
The Standard C routines used for managing heap memory are:
| void *malloc(size_t size) | This routine allocates a memory block whose size is defined in the argument. It returns a pointer to the newly allocated block. |
| void *calloc(size_t nitems, size_t size) | This routine allocates enough storage to store nitems blocks of size size. It also initializes all of the memory to 0. |
| void *realloc( void *block, size_t size) | This routine adjust the size of the block parameter to be size. A pointer to the new block is returned. |
| void free(void *block) | This routine frees up block and returns it to the list of memory available for allocation on the heap. |
These routines are defined in the ANSI C draft, and are essentially identical under Unix and Xenix implementations. The problem with these routines are that they return a pointer that points directly into memory. This means that when data is accessed using one of these memory pointers, there is no mechanism in place to check that the pointer is being used correctly. A pointer can easily be incremented or indexed past the end of the allocated block, and start mangling data in another block. There is simply no validation done on pointer values. This is one reason programmers like using pointers in C: the lack of qualification makes memory access using pointers extremely fast.
The heap fragmentation problem is one that can be particularly frustrating, at least to those of
use operating on machines that aren’t graced with virtual memory. I have frequently been in the
situation where I need a relatively large block of memory, say 50K bytes. I know that my heap has
the space I need, because I allocated it previously in my program, and things haven’t changed
much since then. Yet when I call malloc(), I get an error return. Careful examination usually
shows that I have a small block sitting in the middle of the heap, which breaks down my largest
possible block by 50%. Solving this problem requires that I learn a little bit more about the
structure of my heap, and how the heap managers work. With this knowledge in hand I can reorder
my calls to the heap manager, so my small blocks don’t cause this kind of fragmentation.
Solutions
A commonly suggested solution to the problem of heap fragmentation is the roll your own approach. This normally consists of replacing the standard memory allocation routines with ones that you have written. The replacement routines usually have more error checking built into them, and will often perform somewhat better than the ones supplied with the run time library.
This approach is useful, but suffers from a few problems. First of all, the run time library supplied with your compiler usually does some initialization of the heap. This involves determining what the initial size of the heap is, and setting up some global variables that control the heap. If any routines in the run time library look at or modify these global variables, you could have serious interaction problems.
Secondly, memory procedures differ between different operating systems and machines. A routine you write to work under MS-DOS may not work on a Sun Unix system. Word and pointer sizes are different, and O/S calls to get or release memory are different.
Third, your problems may be intimately related to the standard malloc() type memory
allocation routines. Replacing them with debugging routines of your own creation may make the
problem impossible to recreate.
And finally, if you are using third party libraries, and don’t have the source, you have an
additional problem. If these routines call malloc() and free(), you are forced to duplicate
these functions, including names, parameters and return values. This is even true of some of the
run time library routines. Calling stringdup() for example, usually generates a call to
malloc(). So if you create new memory allocation routines, you still need to emulate malloc().
My Solution
My first step in tackling the heap was to create replacement memory allocation routines that I
could transparently move in and out of my existing code. This was simply a matter of creating a
header file called HEAP.H that I included in all of my source files. HEAP.H
consisted of a three macro definitions that effectively replace malloc(), calloc(), and
free(). The macro definitions are shown in Figure 1, along with the function prototypes for my
replacement routines.
#define malloc(size) my_malloc(__FILE__,__LINE__,(size))
#define calloc(nitems,size) my_calloc(__FILE__,__LINE__,(nitems),(size))
#define free(block) my_free(__FILE__,__LINE__,(block))
void *my_malloc(char *file_name,
unsigned int line_number,
size_t size);
void *my_calloc(char *file_name,
unsigned int line_number,
size_t nitems,
size_t size);
void my_free(char *file_name,
unsigned int line_number,
void *block);HEAP.H
As you can see from these definitions, these routines will replace any of the three heap function calls made in each module with calls to my substitute routines.
Two additional parameters are automatically added in to the call: the file name and the file
number, represented by the predefined macros __FILE__ and __LINE__. These will be a
tremendous help in keeping track of who allocates what pointers. Note that these two macros are
included in the ANSI draft standard, and seem to be in near universal use by now.
After recompiling all of my source modules with the new HEAP.H file, I now should
have control over most of the memory allocation taking place in my program. The question then is,
what do I do in these routines?
Looking back at my frequent problems, I can come up with ways to address each of them. My first
problem was that of pointers writing past the end of their allocated area, or backing up and
writing before the start of their allocated memory. My approach to this problem is that in my two
memory allocation routines, my_calloc() and my_malloc(), I allocate an extra 16 bytes before
and after the memory block. For example, if the user has a call that request 1000 bytes, as in:
torage_area = malloc( 1000 );my memory allocation routine will instead call malloc() to allocate 1032 bytes. The block that
malloc() returns to my_malloc() is partitioned into three segments.
The first 16 bytes are defined as the leading picket, and the last 16 bytes are defined as the
trailing picket. The 1000 bytes in between belong to the caller. So when malloc() returns a
pointer to my_malloc(), my_malloc() will return the value of that pointer + 16 to the calling
routine. my_malloc() also stores a fixed byte pattern in the picket area, which can be tested
for corruption at any time.
The 16 byte margin around the buffer should guarantee proper alignment for any type object on most machines. In addition, it will protect against pointer offsets that are off by a factor of only 1 or so bytes, which account for a large percentage of pointer errors.
My second problem was failure to free blocks after I am done with them. The problem here is that it is tough to keep track of all the different blocks that are currently allocated. Many run time libraries provide no way to determine which heap blocks are currently in use. Even if you can figure out which blocks are in use, just having a memory address doesn’t tell you which routine allocated the block.
The solution to this problem is to keep track of each block as it is allocated. The macro definitions provided me with a way to track where in the program each memory allocation occurred. All I have to do is add the file name and line number to a table as the elements are allocated. I created a table used by the heap routines that has the following structure:
struct tags {
char far * returned_address;
char far * real_address;
size_t size;
char *file_name;
unsigned int line_number;
char maverick;
char tagged;
} tag_table[TAG_MAX];The heap tag table keeps track of all this information for every pointer that is allocated. The first two items give the real address of the heap entry, as well as the address that was returned to the calling program, the size of the heap entry, and the file name and line number in the file. The final two entries, the maverick and tagged fields will be discussed later.
What this means is that if I faithfully add each pointer to the table when it is allocated, and just as faithfully remove each pointer from the tag table when it is freed, I will then have a way to know exactly how many pointers are in use, and where in my program they were allocated. Note also that I could easily extend this table to include even more information about when and where the pointer is allocated, it is simply a matter of adding more fields.
My third heap problem was fragmentation. Once again, keeping track of the tag table is going to let me address that problem. By knowing just where my pointers are, and who allocated them, I can put in place mechanisms to either move or free up the memory, cleaning up the heap in the process.
The final problem I had was with heap problems caused by libraries I don’t have the source code for. For example, there are dozens of routines in my compiler’s run time libraries that allocate memory. Third party libraries that I link into my code have lots of hidden allocation. I need to know what is being allocated, and how it is affecting my heap.
Since most people aren’t willing or able to spring for the added cost source code for their
libraries, recompiling the offending modules with the HEAP.H header file is usually
not a possibility. Yet I still need to be able keep track of these modules. I would like to know
when and where they are allocated, and have some idea of when and where they are freed.
In my heap routines, I refer to heap blocks that were created outside the scope of my source code
as maverick blocks. My first problem is that of being able to detect maverick blocks.
Fortunately, Microsoft C provides a convenient mechanism for this. In their run time library they
have included a library function called _heapwalk(). This routine lets you walk through the
entire heap, one block at a time. You eventually see each allocated block, and in addition you
are given the size of the block.
In order to find maverick blocks, I just take a walk through the heap using the _heapwalk()
function. For each pointer produced, I scan through my tag table, looking at the real_address
field, to see if I already have that block in my table. If it doesn’t show up in my tag table,
it means I have found a maverick block. I add it to the table, but set the maverick flag.
This flag tells me that I am not going to be able to check the pickets for this block, since it
doesn’t have any. It also tells me that I don’t know what the file name or line number for the
pointer is. But at least I know about its existence.
Once I have catalogued the maverick pointer in my tag table, I can keep track of it, and have
some idea of just when it is freed up. When I am taking my walk through the heap that I mentioned
above, I am setting the tag field for every entry that I match up with from the _heapwalk()
function. After I have finished my walk, I can scan the table and see if any pointers don’t have
their tag field set. Those are pointers that have been freed up behind my back, and I can set up
my program to notify me when this happens.
The Run Time Implementation
The final version of my_malloc() is shown below. The first part of the routine makes a call to
the verify_heap() routine. This is the module that walks through the heap, checking for new
maverick blocks as well as any blocks that may have disappeared. This routine also verifies that
the leading and trailing pickets for each of the non-maverick blocks are still intact. If this
routine finds any problems with the heap, it brings it to my attention with a call to
screen_message().
void *my_malloc(char *file_name,
unsigned int line_number,
size_t size)
{
void *malloc_pointer;
size_t real_size;
verify_heap();
real_size = size + PICKET_SIZE * 2;
malloc_pointer = malloc( real_size );
if ( malloc_pointer == NULL ) {
screen_message(1,0,"File: %s Line: %u requesting %u bytes",
file_name,line_number,size);
screen_message(0,0,"Malloc failed! Null pointer will be returned.");
} else
add_tag_to_table(malloc_pointer,0,size,file_name,line_number);
hide_screen();
return((char *)malloc_pointer+PICKET_SIZE);
}my_malloc()
screen_message() is called by any of the routines in the heap module when it has something to
report. When screen_message() is first invoked, it saves off the screen that the application
currently has displayed and pops up a display of the tag table. The screen routines in
SCREEN.C are fairly rudimentary, and I won’t go into any detail on how they work.
The hardware dependent portions of the routine are isolated so that they ought to be easy to
modify to work under any number of platforms. Systems using an ASCII terminal probably would want
to have the heap debug output sent to a second terminal.
A sample screen from the test program that follows is shown in Figure 4. I use the ‘u’ and ‘d’ keys to page up and down through the tag table. The screen that is shown here has a single message, notifying me that it has located a maverick heap element, and added it to the tag table.
----------------------------------------------------------------------------
|Tag #| File Name |Line #| Picket | Address | Size | Picket |
|-----+------------+------+---------------+---------+------+---------------|
|0 |main.c |16 |0123456789ABCDE|4C86:001C|1000 |FEDCBA987654321|
|1 |main.c |17 |0123456789ABCDE|4C86:0426|2000 |FEDCBA987654321|
|2 |MAVERICK |0 | ***MAVERICK***|4C86:0C08|16 | ***MAVERICK***|
|3 |Not in use |0 | | NULL |0 | |
|4 |Not in use |0 | | NULL |0 | |
|5 |Not in use |0 | | NULL |0 | |
|6 |Not in use |0 | | NULL |0 | |
|7 |Not in use |0 | | NULL |0 | |
|8 |Not in use |0 | | NULL |0 | |
|9 |Not in use |0 | | NULL |0 | |
|10 |Not in use |0 | | NULL |0 | |
|11 |Not in use |0 | | NULL |0 | |
|12 |Not in use |0 | | NULL |0 | |
|13 |Not in use |0 | | NULL |0 | |
|14 |Not in use |0 | | NULL |0 | |
----------------------------------------------------------------------------
Found a maverick heap entry: 4C86:0C08
In this case, the maverick heap entry was created by a strdup() function call. The test program
that created the heap error is shown in Figure 5. Now that the pointer has been entered in the
tag table, I will at least be able to keep an eye on it, and be aware of its existence.
#include <stdlib.h>
#include <string.h>
#include "heap.h"
void main(void)
{
char *test_guy_1;
char *test_guy_2;
char *test_guy_3;
char *maverick_pointer;
test_guy_1=malloc(1000);
test_guy_2=malloc(2000);
maverick_pointer=strdup("This is a test");
test_guy_3=malloc(3000);
test_guy_2[2000]='X';
free(test_guy_1);
free(maverick_pointer);
free(test_guy_2);
free(test_guy_3);
}The verify_heap() routine not only walks through the heap looking for maverick and missing
pointers, it also checks to be sure that the pickets for all of the blocks are intact. If they
have been corrupted, an error message like that shown in Figure 6 pops up, showing what pointer
sustained the damage to its block.
I call the verify_heap() routine at the entrance of all of my heap routines. That way I will be
able to check for any problems in the heap before I modify it. Note that in the MS-DOS world,
verify_heap() could also check the null pointer memory area for modification.
----------------------------------------------------------------------------
|Tag #| File Name |Line #| Picket | Address | Size | Picket |
|-----+------------+------+---------------+---------+------+---------------|
|0 |main.c |12 |0123456789ABCDE|3BF6:276C|1000 |FEDCBA987654321|
|1 |main.c |13 |0123456789ABCDE|3BF6:2B76|2000 |XEDCBA987654321|
|2 |MAVERICK |0 | ***MAVERICK***|3BF6:3358|16 | ***MAVERICK***|
|3 |main.c |15 |0123456789ABCDE|3BF6:337A|3000 |FEDCBA987654321|
|4 |Not in use |0 | | NULL |0 | |
|5 |Not in use |0 | | NULL |0 | |
|6 |Not in use |0 | | NULL |0 | |
|7 |Not in use |0 | | NULL |0 | |
|8 |Not in use |0 | | NULL |0 | |
|9 |Not in use |0 | | NULL |0 | |
|10 |Not in use |0 | | NULL |0 | |
|11 |Not in use |0 | | NULL |0 | |
|12 |Not in use |0 | | NULL |0 | |
|13 |Not in use |0 | | NULL |0 | |
|14 |Not in use |0 | | NULL |0 | |
----------------------------------------------------------------------------
Error in trailing picket, tag 1
Your Implementation
Their are only two portions of this program that need to be customized for different platforms.
First, the screen routines in SCREEN.C need to be adapted to suit your particular
hardware. The second part of the code that needs customization is the heap walk code in
HEAP.C. Microsoft supplies a routine to walk through the heap, but most other PC
based compilers don’t have this routine. If you have the source code to the run time library it
ought to be simple to build this routine. After all, every call to malloc() has to do some sort
of heap walk while it looks for free blocks. If you don’t have the source, and can’t build this
routine up, you can just eliminate it from the debugging routines. That means you won’t be able
to keep track of maverick blocks, but everything else will work just fine.
Conclusions
It would be nice if compiler companies would include some heap debugging tools with their run time libraries, especially in light of the frequency of heap problems. As long as they won’t, we have to resort to add on routines like the ones shown here. These routines have helped me find some stubborn heap problems, and with any luck they will prove useful for you.
MAIN.C
/*
* Author: Mark Nelson
*
* Date: October 28, 1989
*
* Description: This is the main() module used to test the heap
* debugger routines. It does a few different
* things that should be detected by the debugger
* routines.
*/
#include <stdlib.h>
#include <string.h>
#include "heap.h"
void main( void )
{
char *test_guy_1;
char *test_guy_2;
char *test_guy_3;
char *maverick_pointer;
test_guy_1 = malloc( 1000 );
test_guy_2 = malloc( 2000 );
/*
* This call to strdup creates a maverick pointer that I should detect
* next time I get into my debugger routines.
*/
maverick_pointer = strdup( "This is a test" );
test_guy_3 = malloc( 3000 );
/*
* Here I write one byte past my allocated area. This should create a
* picket error.
*/
test_guy_2[ 2000 ] = 'X';
free( test_guy_1 );
free( maverick_pointer );
free( test_guy_2 );
free( test_guy_3 );
}HEAP.H
#define malloc(size) my_malloc(__FILE__,__LINE__,(size))
#define calloc(nitems,size) my_calloc(__FILE__,__LINE__,(nitems),(size))
#define free(block) my_free(__FILE__,__LINE__,(block))
void *my_malloc(char *file_name,unsigned int line_number,size_t size);
void *my_calloc(char *file_name,unsigned int line_number,size_t nitems,size_t size);
void my_free(char *file_name,unsigned int line_number, void *block);
/* Prototypes from SCREEN.C */
void draw_boxes_and_titles(char *labels[],int row_count);
void screenputc(int row,int col,char c);
void screenputf(int row,int col,char *format,...);
void screenputs(int row,int col,char *string);
void screenclearline(int row);
void initialize_screen(char *labels[],int widths[]);
void setup_screen(char *labels[],int widths[],int rows);
void restore_screen(void);
/* Prototypes from HEAP.C */
void screen_message(int immediate_return, int tag, char *format,...);
void hide_screen(void);
void my_free(char *file_name,unsigned int line_number, void *block);
void *my_malloc(char *file_name,unsigned int line_number,size_t size);
void initialize_tags(void);
void display_tag_table(int last_tag);
void add_tag_to_table(char far *pointer, char maverick,
size_t size,char *file_name,
unsigned int line_number);
void delete_tag_from_table(int tag);
void verify_heap(void);
void heap_walk(void);HEAP.C
/*
* Author: Mark Nelson
*
* Date: October 28, 1989
*
* Description: This module contains the replacement routines used
* to debug heap problems. The routines are used in
* conjunction with the HEAP.H header file.
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <malloc.h>
#include <conio.h>
#include "_heap.h"
/*
* This structure defines all the fields that I use in the tag
* table database.
*/
#define TAG_MAX 100
struct tags { char far * returned_address;
char far * real_address;
size_t size;
char *file_name;
unsigned int line_number;
char maverick;
char tagged;
} tag_table[TAG_MAX];
int next_free_tag = -1;
/*
* These are some odds and ends I use all around.
*/
char leading_picket[] = "0123456789ABCDE";
char trailing_picket[] = "FEDCBA987654321";
#define PICKET_SIZE sizeof( leading_picket )
/*
* These are the labels and widths for each of the columns in the output
* screen.
*/
char *labels[]={"Tag #","File Name","Line #","Picket","Address","Size","Picket",""};
int widths[]={5,12,6,15,9,6,15};
extern int columns[];
int screen_up=0;
int message_line;
/*
* This is the my_malloc routine that replaces malloc(). Before it does
* anything else, it performs the heap checkout stuff. This will pop up
* a message if anything funny is detected. It then gets the pointer
* for the caller, and adds it to the tag table. The screen is then
* cleared up, and the pointer is returned.
*/
void *my_malloc(char *file_name,unsigned int line_number,size_t size)
{
void *malloc_pointer;
size_t real_size;
verify_heap();
real_size = size + PICKET_SIZE*2;
malloc_pointer = malloc( real_size );
if ( malloc_pointer == NULL ) {
screen_message( 1, 0, "File: %s Line: %u requesting %u bytes",
file_name, line_number, size );
screen_message( 0, 0, "Malloc failed! Null pointer will be returned." );
}
else
add_tag_to_table( malloc_pointer, 0, size, file_name, line_number );
hide_screen();
return( ( char * ) malloc_pointer + PICKET_SIZE );
}
/*
* my_free is set up to replace free(). Just like my_malloc(), it first
* checks out the heap and prints a message if anything funny shows up.
* Before I try to free the block, I have to check and see if it is in
* my tag table. If it is, I free the real pointer, not the one I passed
* back to the caller. If it isn't in the tag table, I print a message
* out to that effect, and return.
*/
void my_free( char *file_name, unsigned int line_number, void *block )
{
int tag;
verify_heap();
for ( tag = 0; tag < TAG_MAX ; tag++ ) {
if ( tag_table[ tag ].returned_address == ( void far * ) block )
break;
}
if ( tag < TAG_MAX ) {
if ( tag_table[ tag ].maverick ) {
screen_message( 1, 0, "File: %s Line: %u freeing block %Fp",
file_name, line_number, ( void far * ) block );
screen_message( 0, 0, "Tag is a maverick entry!" );
free( block );
}
else
free( ( char * ) block - PICKET_SIZE );
delete_tag_from_table( tag );
}
else {
screen_message( 1, 0, "File: %s Line: %u freeing block %Fp",
file_name, line_number, ( void far * ) block );
screen_message( 0, 0, "Tag was not found in tag table! Going to try and free() it." );
free( block );
screen_message( 0, 0, "Heap after freeing anonymous block!" );
}
hide_screen();
}
/*
* I need to initialize the tag table my first time through. This
* routine gets called all the time, but only performs the initialization
* once, when next_free_tag is -1.
*/
void initialize_tags()
{
int i;
if ( next_free_tag == -1 ) {
next_free_tag = 0;
for ( i = 0 ; i < TAG_MAX ; i++ ) {
tag_table[ i ].returned_address = NULL;
tag_table[ i ].file_name = "Not in use";
tag_table[ i ].line_number = 0;
tag_table[ i ].size = 0;
}
}
}
/*
* This is the routine called to display the tag table when something
* has gone wrong. It sits in a loop displaying tag table entries, 15
* at a time. The user can hit the 'u' or 'd' keys to move up or down
* in the table. Any other key breaks the user out.
*/
void display_tag_table( int last_tag )
{
int first_tag;
int offset;
int tag;
char far *picket_pointer;
int key;
if ( last_tag < 16 )
first_tag = 0;
else
first_tag = last_tag - 15;
for ( ; ; ) {
for ( offset = 0 ; offset < 15 ; offset++ ) {
tag = first_tag + offset;
screenputf( offset + 3, columns[ 0 ] + 1, "%-3d", tag );
screenputf( offset + 3, columns[ 1 ] + 1, "%-12s",
tag_table[ tag ].file_name );
screenputf( offset + 3, columns[ 2 ] + 1, "%-5d",
tag_table[ tag ].line_number );
if ( tag_table[ tag ].returned_address != NULL ) {
picket_pointer = tag_table[ tag ].returned_address;
picket_pointer -= PICKET_SIZE ;
if ( tag_table[ tag ].maverick )
screenputf( offset + 3, columns[ 3 ] + 1,"%15s", "***MAVERICK***" );
else
screenputf( offset + 3, columns[ 3 ] + 1, "%15s", picket_pointer );
screenputf( offset + 3, columns[ 4 ] + 1, "%Fp",
tag_table[ tag ].returned_address );
picket_pointer += PICKET_SIZE;
picket_pointer += tag_table[ tag ].size;
if ( tag_table[ tag ].maverick )
screenputf( offset + 3, columns[ 6 ] + 1, "%15s", "***MAVERICK***" );
else
screenputf( offset + 3, columns[ 6 ] + 1, "%15s", picket_pointer );
}
else {
screenputf( offset + 3, columns[ 3 ] + 1, "%15s", "" );
screenputf( offset + 3, columns[ 4 ] + 1, " NULL " );
screenputf( offset + 3, columns[ 6 ] + 1, "%15s", "" );
}
screenputf( offset + 3, columns[ 5 ] + 1, "%-5d", tag_table[ tag ].size );
}
key = getch();
if ( key == 'u' || key == 'U' ) {
first_tag -= 15;
if (first_tag < 0)
first_tag = 0;
}
else if ( key == 'd' || key == 'D' ) {
first_tag += 15;
if ( ( first_tag + 15 ) >= TAG_MAX )
first_tag = TAG_MAX - 15;
}
else
break;
}
}
/*
* This routine is called when a new pointer needs to be added to the tag
* table. It can be a maverick pointer or a regular pointer.
*/
void add_tag_to_table( char far *pointer,
char maverick,
size_t size,
char *file_name,
unsigned int line_number )
{
int i;
if ( next_free_tag >= TAG_MAX )
return;
tag_table[ next_free_tag ].returned_address = pointer;
tag_table[ next_free_tag ].real_address = pointer;
tag_table[ next_free_tag ].size = size;
tag_table[ next_free_tag ].file_name = file_name;
tag_table[ next_free_tag ].line_number = line_number;
tag_table[ next_free_tag ].maverick = maverick;
if ( !maverick ) {
for ( i = 0 ; i < PICKET_SIZE ; i++ )
pointer[ i ] = leading_picket[ i ];
pointer += size;
pointer += PICKET_SIZE ;
for ( i = 0 ; i < PICKET_SIZE ; i++ )
pointer[ i ] = trailing_picket[ i ];
tag_table[ next_free_tag ].returned_address += PICKET_SIZE;
}
next_free_tag++;
}
/*
* This routine is called when a tag needs to be deleted from the table. This
* can happen when a call to free() is made, or when a heapwalk shows that
* one of the pointers is missing.
*/
void delete_tag_from_table( int tag )
{
int i;
next_free_tag--;
for ( i = tag ; i < next_free_tag ; i++ )
tag_table[ i ] = tag_table[ i + 1 ];
tag_table[ i ].returned_address = NULL;
tag_table[ i ].file_name = "Not in use";
tag_table[ i ].line_number = 0;
tag_table[ i ].size = 0;
}
/*
* This is the verify routine that is called on the entry to my_malloc()
* or my_free(). It calls the heap_walk() routine first, to let it do
* its check out of the heap. It then goes through the entire tag table
* and verifies that the pickets are all intact.
*/
void verify_heap()
{
int i;
int tag;
char far *picket_pointer;
initialize_tags();
heap_walk();
for ( tag = 0 ; tag < next_free_tag ; tag++ ) {
if ( tag_table[ tag ].maverick )
continue;
picket_pointer = tag_table[ tag ].returned_address;
picket_pointer -= PICKET_SIZE ;
for ( i = 0 ; i < PICKET_SIZE ; i++ )
if ( picket_pointer[ i ] != leading_picket[ i ] ) {
screen_message( 0, i, "Error in leading picket, tag %3d", tag );
break;
}
picket_pointer += PICKET_SIZE ;
picket_pointer += tag_table[tag].size;
for ( i = 0 ; i < PICKET_SIZE ; i++ )
if ( picket_pointer[ i ] != trailing_picket[ i ] ) {
screen_message( 0, tag, "Error in trailing picket, tag %3d", tag );
break;
}
}
}
/*
* This is the routine that walks through the heap. If an heap entry
* is not found in the tag table, a message is printed, and it is added
* as a maverick. Otherwise, the tag is noted. After walking through
* the whole heap, a check is done to see if any of our tagged entries
* didn't show up, which generates another message.
*
* Remember that this code is MSC-specific. You need to rewrite this
* routine for every different compiler.
*/
void heap_walk()
{
struct _heapinfo hinfo;
int heapstatus;
size_t size;
int i;
hinfo._pentry = NULL;
for ( i = 0 ; i < next_free_tag ; i++ )
tag_table[ i ].tagged = 0;
for ( ; ; ) {
heapstatus = _heapwalk( &hinfo );
if ( heapstatus == _HEAPEMPTY )
break;
if ( heapstatus == _HEAPEND )
break;
if ( heapstatus != _HEAPOK ) {
screen_message( 0, 0, "Heap is corrupted! Going to exit." );
exit( 1 );
}
if ( hinfo._useflag != _USEDENTRY )
continue;
for ( i = 0 ; i < next_free_tag ; i++ ) {
if ( (int far *) tag_table[ i ].real_address == hinfo._pentry ) {
tag_table[ i ].tagged = 1;
break;
}
}
if ( i == next_free_tag ) {
size = hinfo._size;
if ( i < TAG_MAX )
tag_table[ i ].tagged = 1;
add_tag_to_table( (char far *) hinfo._pentry, 1, size, "MAVERICK",0 );
screen_message( 0, i, "Found a maverick heap entry: %Fp", hinfo._pentry );
}
}
/*
* At this point every entry should have been tagged, so I can go through
* the table and look for ones that didn't get tagged.
*/
for ( i = 0 ; i < next_free_tag ; i++ ) {
if ( tag_table[ i ].tagged == 0 ) {
screen_message( 0, i, "Didn't find heap entry in heapwalk, tag %d", i );
delete_tag_from_table( i );
}
}
}
/*
* During the process of checking out the heap, if I see anything worthy
* of a message, I call this routine. If the screen is not already up,
* this guy pulls it up. Then it prints the message.
*/
void screen_message( int immediate_return, int tag, char *format, ... )
{
char message[ 81 ];
va_list args;
if ( screen_up == 0 ) {
screen_up = 1;
message_line = 20;
setup_screen( labels, widths, 15 );
}
va_start( args, format );
vsprintf( message, format, args );
screenputs( message_line, 0, message );
if ( ++message_line >= 25 )
message_line = 20;
if ( !immediate_return )
display_tag_table( tag );
}
/*
* After all the work is done, I have to hide my heap screen so the user
* can see the application output. This is pretty easy to do, a routine
* in SCREEN.C does the whole job for me.
*/
void hide_screen()
{
if ( screen_up != 0 ) {
screen_up = 0;
restore_screen();
}
}SCREEN.C
/*
* Author: Mark Nelson
*
* Date: October 28, 1989
*
* Description: This module contains the screen I/O routines used in
* the heap debugger module. These are very simplified
* screen I/O routines.
*/
#include <stdio.h>
#include <stdarg.h>
#include <string.h>
#include "_heap.h"
/*
* These are all the line drawing constants defined.
*/
#define UL_CORNER 218
#define UR_CORNER 191
#define LL_CORNER 192
#define LR_CORNER 217
#define UPPER_TEE 194
#define LOWER_TEE 193
#define LEFT_TEE 195
#define RIGHT_TEE 180
#define CENTER_TEE 197
#define HORIZONTAL_LINE 196
#define VERTICAL_LINE 179
/*
* I create a structure so I can write directly to screen as if it were
* a big array. That way the compiler takes care of computing the
* addresses, all I have to do is insert the row and column.
*/
struct video_element {
unsigned char character;
unsigned char attribute;
};
struct video_element (far *physical_screen)[25][80];
struct video_element saved_screen[25][80];
/*
* This routine draws the box I use up on the screen. It is passed a
* list of labels to draw at the head of the columns, plus a count
* of how many rows are to be left open for data entry. It depends
* on some earlier code somewhere to have initialized an array called
* columns[] that tells it where to draw each column on the screen.
* There is a lot of code here to draw the boxes, but it is all
* straightforward.
*/
int columns[10];
int column_count=0;
void draw_boxes_and_titles(char *labels[],int row_count)
{
int col;
int row;
int i;
int j;
int rows[3];
/*
* The three rows I define are the top and bottom of the box, plus the
* line that divides the title lines from the data lines.
*/
rows[0]=0;
rows[1]=2;
rows[2]=3+row_count;
for (col=1;col<columns[column_count];col++)
for (i=0;i<3;i++)
(*physical_screen)[rows[i]][col].character = HORIZONTAL_LINE;
for (i=0;i<=column_count;i++)
for (row=0;row<(row_count+4);row++)
(*physical_screen)[row][columns[i]].character = VERTICAL_LINE;
(*physical_screen)[0][columns[0]].character = UL_CORNER;
(*physical_screen)[row_count+3][columns[0]].character = LL_CORNER;
(*physical_screen)[0][columns[column_count]].character = UR_CORNER;
(*physical_screen)[row_count+3][columns[column_count]].character = LR_CORNER;
(*physical_screen)[rows[1]][columns[0]].character = LEFT_TEE;
(*physical_screen)[rows[1]][columns[column_count]].character = RIGHT_TEE;
for (j=1;j<column_count;j++)
(*physical_screen)[0][columns[j]].character = UPPER_TEE;
for (j=1;j<column_count;j++)
(*physical_screen)[row_count+3][columns[j]].character = LOWER_TEE;
for (j=1;j<column_count;j++)
(*physical_screen)[rows[1]][columns[j]].character = CENTER_TEE;
/*
* Here is where I draw the labels. They need to go in the center of
* their little boxes.
*/
for (i=0;i<column_count;i++)
{
col=columns[i]+1;
col += (columns[i+1]-columns[i]-1)/2;
col -= strlen(labels[i])/2;
screenputs(1,col,labels[i]);
}
}
/*
* This is a general purpose routine to print a formatted string on
* the screen.
*/
void screenputf(int row,int col,char *format,...)
{
char buffer[81];
va_list args;
va_start(args,format);
vsprintf(buffer,format,args);
screenputs(row,col,buffer);
}
/*
* This is a general purpose routine to put an unformatted string
* out to the screen.
*/
void screenputs(int row,int col,char *string)
{
char c;
while (1)
{
c=*string++;
if (c=='\0')
break;
(*physical_screen)[row][col++].character=c;
}
}
/*
* This is a general purpose routine to clear a whole line on the
* screen.
*/
void screenclearline(int row)
{
int col;
for (col=0;col<80;col++)
(*physical_screen)[row][col].character=' ';
}
/*
* This is the screen initialization code. It is a trap door routine that
* gets called all the time, but only executes once. It computes what
* columns the vertical lines are going to go in, based on the widths needed
* for each column, passed as a parameter.
* Note that if you are using a monochrome monitor, you need to change
* the screen pointer to be 0xb0000000L.
* This routine also initializes the tag table
*/
void initialize_screen(char *labels[],int widths[])
{
int row;
int col;
int i;
static int first_time=0;
if (first_time==0)
{
first_time=1;
columns[0]=1;
column_count=0;
while (strlen(labels[column_count]) != 0)
{
columns[column_count+1] = columns[column_count]+widths[column_count]+1;
column_count++;
}
}
physical_screen=(struct video_element (far *)[25][80])0xb8000000L;
for (row=0;row<25;row++)
for (col=0;col<80;col++)
{
saved_screen[row][col]=(*physical_screen)[row][col];
(*physical_screen)[row][col].character=' ';
(*physical_screen)[row][col].attribute=0x1b;
}
}
/*
* Whenever the heap routines decide they need to print a screen message,
* they set up the screen first by calling this guy.
*/
void setup_screen(char *labels[],int widths[],int rows)
{
initialize_screen(labels,widths);
draw_boxes_and_titles(labels,rows);
}
/*
* After the heap routines are done printing debug information, they
* have to restore the screen back to where it was when they got called.
* This routine does that.
*/
void restore_screen()
{
int row;
int col;
for (row=0;row<25;row++)
for (col=0;col<80;col++)
(*physical_screen)[row][col]=saved_screen[row][col];
}_HEAP.H
/* Prototypes from SCREEN.C */
void draw_boxes_and_titles(char *labels[],int row_count);
void screenputc(int row,int col,char c);
void screenputf(int row,int col,char *format,...);
void screenputs(int row,int col,char *string);
void screenclearline(int row);
void initialize_screen(char *labels[],int widths[]);
void setup_screen(char *labels[],int widths[],int rows);
void restore_screen(void);
/* Prototypes from HEAP.C */
void screen_message(int immediate_return, int tag, char *format,...);
void hide_screen(void);
void my_free(char *file_name,unsigned int line_number, void *block);
void *my_malloc(char *file_name,unsigned int line_number,size_t size);
void initialize_tags(void);
void display_tag_table(int last_tag);
void add_tag_to_table(char far *pointer,char maverick,size_t size,char *file_name,unsigned int line_number);
void delete_tag_from_table(int tag);
void verify_heap(void);
void heap_walk(void);