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 argument.
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.

C:
  1. #define malloc(size) my_malloc(__FILE__,__LINE__,(size))
  2. #define calloc(nitems,size) my_calloc(__FILE__,__LINE__,(nitems),(size))
  3. #define free(block)  my_free(__FILE__,__LINE__,(block))
  4.  
  5. void *my_malloc(char *file_name,
  6.                 unsigned int line_number,
  7.                 size_t size);
  8. void *my_calloc(char *file_name,
  9.                 unsigned int line_number,
  10.                 size_t nitems,
  11.                 size_t size);
  12. void my_free(char *file_name,
  13.              unsigned int line_number,
  14.              void *block);

Definitions in HEAP.H
Figure 1

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:

storage_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 is 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:

C:
  1. struct tags {
  2.   char far * returned_address;
  3.   char far * real_address;
  4.   size_t size;
  5.   char *file_name;
  6.   unsigned int line_number;
  7.   char maverick;
  8.   char tagged;
  9. } tag_table[TAG_MAX];

The Heap Tag Table Structure
Figure 2

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().

C:
  1. void *my_malloc(char *file_name,
  2.                 unsigned int line_number,
  3.                 size_t size)
  4. {
  5.   void *malloc_pointer;
  6.   size_t real_size;
  7.  
  8.   verify_heap();
  9.   real_size = size + PICKET_SIZE * 2;
  10.   malloc_pointer = malloc( real_size );
  11.   if ( malloc_pointer == NULL ) {
  12.     screen_message(1,0,"File: %s Line: %u requesting %u bytes",
  13.                    file_name,line_number,size);
  14.     screen_message(0,0,"Malloc failed! Null pointer will be returned.");
  15.   } else
  16.     add_tag_to_table(malloc_pointer,0,size,file_name,line_number);
  17.   hide_screen();
  18.   return((char *)malloc_pointer+PICKET_SIZE);
  19. }

my_malloc()
Figure 3

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

A sample output screen
Figure 4

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.

C:
  1. #include <stdlib.h>
  2. #include <string.h>
  3. #include "heap.h"
  4.  
  5. void main(void)
  6. {
  7.   char *test_guy_1;
  8.   char *test_guy_2;
  9.   char *test_guy_3;
  10.   char *maverick_pointer;
  11.  
  12.   test_guy_1=malloc(1000);
  13.   test_guy_2=malloc(2000);
  14.   maverick_pointer=strdup("This is a test");
  15.   test_guy_3=malloc(3000);
  16.   test_guy_2[2000]='X';
  17.   free(test_guy_1);
  18.   free(maverick_pointer);
  19.   free(test_guy_2);
  20.   free(test_guy_3);
  21. }

A test program for the heap routines
Figure 5

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

A corrupted picket
Figure 6

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

C:
  1. /*
  2. * Author:       Mark Nelson
  3. *
  4. * Date:         October 28, 1989
  5. *
  6. * Description:  This is the main() module used to test the heap
  7. *               debugger routines.  It does a few different
  8. *               things that should be detected by the debugger
  9. *               routines.
  10. */
  11.  
  12. #include <stdlib.h>
  13. #include <string.h>
  14. #include "heap.h"
  15.  
  16. void main( void )
  17. {
  18.     char *test_guy_1;
  19.     char *test_guy_2;
  20.     char *test_guy_3;
  21.     char *maverick_pointer;
  22.  
  23.     test_guy_1 = malloc( 1000 );
  24.     test_guy_2 = malloc( 2000 );
  25. /*
  26. * This call to strdup creates a maverick pointer that I should detect
  27. * next time I get into my debugger routines.
  28. */
  29.     maverick_pointer = strdup( "This is a test" );
  30.     test_guy_3 = malloc( 3000 );
  31. /*
  32. *  Here I write one byte past my allocated area.  This should create a
  33. *  picket error.
  34. */
  35.     test_guy_2[ 2000 ] = 'X';
  36.     free( test_guy_1 );
  37.     free( maverick_pointer );
  38.     free( test_guy_2 );
  39.     free( test_guy_3 );
  40. }

HEAP.H

C:
  1. #define malloc(size) my_malloc(__FILE__,__LINE__,(size))
  2. #define calloc(nitems,size) my_calloc(__FILE__,__LINE__,(nitems),(size))
  3. #define free(block)  my_free(__FILE__,__LINE__,(block))
  4.  
  5. void *my_malloc(char *file_name,unsigned int line_number,size_t size);
  6. void *my_calloc(char *file_name,unsigned int line_number,size_t nitems,size_t size);
  7. void my_free(char *file_name,unsigned int line_number, void *block);
  8.  
  9. /* Prototypes from SCREEN.C  */
  10.  
  11. void draw_boxes_and_titles(char *labels[],int row_count);
  12. void screenputc(int row,int col,char c);
  13. void screenputf(int row,int col,char *format,...);
  14. void screenputs(int row,int col,char *string);
  15. void screenclearline(int row);
  16. void initialize_screen(char *labels[],int widths[]);
  17. void setup_screen(char *labels[],int widths[],int rows);
  18. void restore_screen(void);
  19.  
  20. /* Prototypes from HEAP.C */
  21.  
  22. void screen_message(int immediate_return, int tag, char *format,...);
  23. void hide_screen(void);
  24. void my_free(char *file_name,unsigned int line_number, void *block);
  25. void *my_malloc(char *file_name,unsigned int line_number,size_t size);
  26. void initialize_tags(void);
  27. void display_tag_table(int last_tag);
  28. void add_tag_to_table(char far *pointer, char maverick,
  29.                       size_t size,char *file_name,
  30.                       unsigned int line_number);
  31. void delete_tag_from_table(int tag);
  32. void verify_heap(void);
  33. void heap_walk(void);

HEAP.C

C:
  1. /*
  2. * Author:       Mark Nelson
  3. *
  4. * Date:         October 28, 1989
  5. *
  6. * Description:  This module contains the replacement routines used
  7. *               to debug heap problems.  The routines are used in
  8. *               conjunction with the HEAP.H header file.
  9. */
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12. #include <stdarg.h>
  13. #include <malloc.h>
  14. #include <conio.h>
  15. #include "_heap.h"
  16.  
  17. /*
  18. * This structure defines all the fields that I use in the tag
  19. * table database.
  20. */
  21. #define TAG_MAX 100
  22. struct tags {   char far * returned_address;
  23.                 char far * real_address;
  24.                 size_t size;
  25.                 char *file_name;
  26.                 unsigned int line_number;
  27.                 char maverick;
  28.                 char tagged;
  29.             } tag_table[TAG_MAX];
  30.  
  31. int next_free_tag = -1;
  32.  
  33. /*
  34. * These are some odds and ends I use all around.
  35. */
  36. char leading_picket[] = "0123456789ABCDE";
  37. char trailing_picket[] = "FEDCBA987654321";
  38. #define PICKET_SIZE sizeof( leading_picket )
  39.  
  40. /*
  41. * These are the labels and widths for each of the columns in the output
  42. * screen.
  43. */
  44. char *labels[]={"Tag #","File Name","Line #","Picket","Address","Size","Picket",""};
  45. int widths[]={5,12,6,15,9,6,15};
  46. extern int columns[];
  47. int screen_up=0;
  48. int message_line;
  49.  
  50. /*
  51. * This is the my_malloc routine that replaces malloc().  Before it does
  52. * anything else, it performs the heap checkout stuff.  This will pop up
  53. * a message if anything funny is detected.  It then gets the pointer
  54. * for the caller, and adds it to the tag table.  The screen is then
  55. * cleared up, and the pointer is returned.
  56. */
  57.  
  58. void *my_malloc(char *file_name,unsigned int line_number,size_t size)
  59. {
  60.   void *malloc_pointer;
  61.   size_t real_size;
  62.  
  63.   verify_heap();
  64.   real_size = size + PICKET_SIZE*2;
  65.   malloc_pointer = malloc( real_size );
  66.   if ( malloc_pointer == NULL ) {
  67.     screen_message( 1, 0, "File: %s Line: %u requesting %u bytes",
  68.                     file_name, line_number, size );
  69.     screen_message( 0, 0, "Malloc failed! Null pointer will be returned." );
  70.   }
  71.   else
  72.     add_tag_to_table( malloc_pointer, 0, size, file_name, line_number );
  73.   hide_screen();
  74.   return( ( char * ) malloc_pointer + PICKET_SIZE );
  75. }
  76.  
  77.  
  78. /*
  79. * my_free is set up to replace free().  Just like my_malloc(), it first
  80. * checks out the heap and prints a message if anything funny shows up.
  81. * Before I try to free the block, I have to check and see if it is in
  82. * my tag table.  If it is, I free the real pointer, not the one I passed
  83. * back to the caller.  If it isn't in the tag table, I print a message
  84. * out to that effect, and return.
  85. */
  86.  
  87. void my_free( char *file_name, unsigned int line_number, void *block )
  88. {
  89.   int tag;
  90.  
  91.   verify_heap();
  92.   for ( tag = 0; tag <TAG_MAX ; tag++ ) {
  93.     if ( tag_table[ tag ].returned_address == ( void far * ) block )
  94.       break;
  95.   }
  96.   if ( tag <TAG_MAX ) {
  97.     if ( tag_table[ tag ].maverick ) {
  98.         screen_message( 1, 0, "File: %s Line: %u freeing block %Fp",
  99.                         file_name, line_number, ( void far * ) block );
  100.         screen_message( 0, 0, "Tag is a maverick entry!" );
  101.         free( block );
  102.     }
  103.     else
  104.         free( ( char * ) block - PICKET_SIZE );
  105.     delete_tag_from_table( tag );
  106.   }
  107.   else {
  108.     screen_message( 1, 0, "File: %s Line: %u freeing block %Fp",
  109.                     file_name, line_number, ( void far * ) block );
  110.     screen_message( 0, 0, "Tag was not found in tag table!  Going to try and free() it." );
  111.     free( block );
  112.     screen_message( 0, 0, "Heap after freeing anonymous block!" );
  113.   }
  114.   hide_screen();
  115. }
  116.  
  117.  
  118. /*
  119. * I need to initialize the tag table my first time through.  This
  120. * routine gets called all the time, but only performs the initialization
  121. * once, when next_free_tag is -1.
  122. */
  123.  
  124. void initialize_tags()
  125. {
  126.   int i;
  127.  
  128.   if ( next_free_tag == -1 ) {
  129.     next_free_tag = 0;
  130.     for ( i = 0 ; i <TAG_MAX ; i++ ) {
  131.       tag_table[ i ].returned_address = NULL;
  132.       tag_table[ i ].file_name = "Not in use";
  133.       tag_table[ i ].line_number = 0;
  134.       tag_table[ i ].size = 0;
  135.     }
  136.   }
  137. }
  138.  
  139. /*
  140. * This is the routine called to display the tag table when something
  141. * has gone wrong.  It sits in a loop displaying tag table entries, 15
  142. * at a time.  The user can hit the 'u' or 'd' keys to move up or down
  143. * in the table.  Any other key breaks the user out.
  144. */
  145.  
  146. void display_tag_table( int last_tag )
  147. {
  148.   int first_tag;
  149.   int offset;
  150.   int tag;
  151.   char far *picket_pointer;
  152.   int key;
  153.  
  154.   if ( last_tag <16 )
  155.     first_tag = 0;
  156.   else
  157.     first_tag = last_tag - 15;
  158.  
  159.     for ( ; ; ) {
  160.     for ( offset = 0 ; offset <15 ; offset++ ) {
  161.       tag = first_tag + offset;
  162.       screenputf( offset + 3, columns[ 0 ] + 1, "%-3d", tag );
  163.       screenputf( offset + 3, columns[ 1 ] + 1, "%-12s",
  164.                   tag_table[ tag ].file_name );
  165.       screenputf( offset + 3, columns[ 2 ] + 1, "%-5d",
  166.                   tag_table[ tag ].line_number );
  167.       if ( tag_table[ tag ].returned_address != NULL ) {
  168.         picket_pointer = tag_table[ tag ].returned_address;
  169.         picket_pointer -= PICKET_SIZE ;
  170.         if ( tag_table[ tag ].maverick )
  171.           screenputf( offset + 3, columns[ 3 ] + 1,"%15s", "***MAVERICK***" );
  172.         else
  173.           screenputf( offset + 3, columns[ 3 ] + 1, "%15s", picket_pointer );
  174.         screenputf( offset + 3, columns[ 4 ] + 1, "%Fp",
  175.                     tag_table[ tag ].returned_address );
  176.         picket_pointer += PICKET_SIZE;
  177.         picket_pointer += tag_table[ tag ].size;
  178.         if ( tag_table[ tag ].maverick )
  179.           screenputf( offset + 3, columns[ 6 ] + 1, "%15s", "***MAVERICK***" );
  180.         else
  181.           screenputf( offset + 3, columns[ 6 ] + 1, "%15s", picket_pointer );
  182.       }
  183.       else {
  184.         screenputf( offset + 3, columns[ 3 ] + 1, "%15s", "" );
  185.         screenputf( offset + 3, columns[ 4 ] + 1, "  NULL   " );
  186.         screenputf( offset + 3, columns[ 6 ] + 1, "%15s", "" );
  187.       }
  188.       screenputf( offset + 3, columns[ 5 ] + 1, "%-5d", tag_table[ tag ].size );
  189.     }
  190.     key = getch();
  191.     if ( key == 'u' || key == 'U' ) {
  192.         first_tag -= 15;
  193.         if (first_tag <0)
  194.           first_tag = 0;
  195.     }
  196.     else if ( key == 'd' || key == 'D' ) {
  197.       first_tag += 15;
  198.       if ( ( first_tag + 15 )>= TAG_MAX )
  199.         first_tag = TAG_MAX - 15;
  200.     }
  201.     else
  202.       break;
  203.   }
  204. }
  205.  
  206. /*
  207. * This routine is called when a new pointer needs to be added to the tag
  208. * table.  It can be a maverick pointer or a regular pointer.
  209. */
  210.  
  211. void add_tag_to_table( char far *pointer,
  212.                        char maverick,
  213.                        size_t size,
  214.                        char *file_name,
  215.                        unsigned int line_number )
  216. {
  217.   int i;
  218.  
  219.   if ( next_free_tag>= TAG_MAX )
  220.     return;
  221.   tag_table[ next_free_tag ].returned_address = pointer;
  222.   tag_table[ next_free_tag ].real_address = pointer;
  223.   tag_table[ next_free_tag ].size = size;
  224.   tag_table[ next_free_tag ].file_name = file_name;
  225.   tag_table[ next_free_tag ].line_number = line_number;
  226.   tag_table[ next_free_tag ].maverick = maverick;
  227.   if ( !maverick ) {
  228.     for ( i = 0 ; i <PICKET_SIZE ; i++ )
  229.       pointer[ i ] = leading_picket[ i ];
  230.     pointer += size;
  231.     pointer += PICKET_SIZE ;
  232.     for ( i = 0 ; i <PICKET_SIZE ; i++ )
  233.       pointer[ i ] = trailing_picket[ i ];
  234.     tag_table[ next_free_tag ].returned_address += PICKET_SIZE;
  235.   }
  236.   next_free_tag++;
  237. }
  238.  
  239. /*
  240. * This routine is called when a tag needs to be deleted from the table.  This
  241. * can happen when a call to free() is made, or when a heapwalk shows that
  242. * one of the pointers is missing.
  243. */
  244.  
  245. void delete_tag_from_table( int tag )
  246. {
  247.   int i;
  248.  
  249.   next_free_tag--;
  250.   for ( i = tag ; i <next_free_tag ; i++ )
  251.     tag_table[ i ] = tag_table[ i + 1 ];
  252.   tag_table[ i ].returned_address = NULL;
  253.   tag_table[ i ].file_name = "Not in use";
  254.   tag_table[ i ].line_number = 0;
  255.   tag_table[ i ].size = 0;
  256. }
  257.  
  258. /*
  259. *  This is the verify routine that is called on the entry to my_malloc()
  260. *  or my_free().  It calls the heap_walk() routine first, to let it do
  261. *  its check out of the heap.  It then goes through the entire tag table
  262. *  and verifies that the pickets are all intact.
  263. */
  264.  
  265. void verify_heap()
  266. {
  267.   int i;
  268.   int tag;
  269.   char far *picket_pointer;
  270.  
  271.   initialize_tags();
  272.   heap_walk();
  273.   for ( tag = 0 ; tag <next_free_tag ; tag++ ) {
  274.     if ( tag_table[ tag ].maverick )
  275.       continue;
  276.     picket_pointer = tag_table[ tag ].returned_address;
  277.     picket_pointer -= PICKET_SIZE ;
  278.     for ( i = 0 ; i <PICKET_SIZE ; i++ )
  279.       if ( picket_pointer[ i ] != leading_picket[ i ] ) {
  280.         screen_message( 0, i, "Error in leading picket, tag %3d", tag );
  281.         break;
  282.       }
  283.     picket_pointer += PICKET_SIZE ;
  284.     picket_pointer += tag_table[tag].size;
  285.     for ( i = 0 ; i <PICKET_SIZE ; i++ )
  286.       if ( picket_pointer[ i ] != trailing_picket[ i ] ) {
  287.         screen_message( 0, tag, "Error in trailing picket, tag %3d", tag );
  288.         break;
  289.       }
  290.   }
  291. }
  292.  
  293. /*
  294. * This is the routine that walks through the heap.  If an heap entry
  295. * is not found in the tag table, a message is printed, and it is added
  296. * as a maverick.  Otherwise, the tag is noted.  After walking through
  297. * the whole heap, a check is done to see if any of our tagged entries
  298. * didn't show up, which generates another message.
  299. *
  300. * Remember that this code is MSC-specific.  You need to rewrite this
  301. * routine for every different compiler.
  302. */
  303.  
  304. void heap_walk()
  305. {
  306.   struct _heapinfo hinfo;
  307.   int heapstatus;
  308.   size_t size;
  309.   int i;
  310.  
  311.   hinfo._pentry = NULL;
  312.  
  313.   for ( i = 0 ; i <next_free_tag ; i++ )
  314.     tag_table[ i ].tagged = 0;
  315.  
  316.   for ( ; ; ) {
  317.     heapstatus = _heapwalk( &hinfo );
  318.     if ( heapstatus == _HEAPEMPTY )
  319.       break;
  320.     if ( heapstatus == _HEAPEND )
  321.       break;
  322.     if ( heapstatus != _HEAPOK ) {
  323.       screen_message( 0, 0, "Heap is corrupted! Going to exit." );
  324.       exit( 1 );
  325.     }
  326.     if ( hinfo._useflag != _USEDENTRY )
  327.       continue;
  328.     for ( i = 0 ; i <next_free_tag ; i++ ) {
  329.       if ( (int far *) tag_table[ i ].real_address == hinfo._pentry ) {
  330.         tag_table[ i ].tagged = 1;
  331.         break;
  332.       }
  333.     }
  334.     if ( i == next_free_tag ) {
  335.       size = hinfo._size;
  336.       if ( i <TAG_MAX )
  337.         tag_table[ i ].tagged = 1;
  338.       add_tag_to_table( (char far *) hinfo._pentry, 1, size, "MAVERICK",0 );
  339.       screen_message( 0, i, "Found a maverick heap entry: %Fp", hinfo._pentry );
  340.     }
  341.   }
  342. /*
  343. * At this point every entry should have been tagged, so I can go through
  344. * the table and look for ones that didn't get tagged.
  345. */
  346.   for ( i = 0 ; i <next_free_tag ; i++ ) {
  347.     if ( tag_table[ i ].tagged == 0 ) {
  348.       screen_message( 0, i, "Didn't find heap entry in heapwalk, tag %d", i );
  349.       delete_tag_from_table( i );
  350.     }
  351.   }
  352. }
  353.  
  354. /*
  355. * During the process of checking out the heap, if I see anything worthy
  356. * of a message, I call this routine.  If the screen is not already up,
  357. * this guy pulls it up.  Then it prints the message.
  358. */
  359.  
  360. void screen_message( int immediate_return, int tag, char *format, ... )
  361. {
  362.   char message[ 81 ];
  363.   va_list args;
  364.  
  365.   if ( screen_up == 0 ) {
  366.     screen_up = 1;
  367.     message_line = 20;
  368.     setup_screen( labels, widths, 15 );
  369.   }
  370.   va_start( args, format );
  371.   vsprintf( message, format, args );
  372.   screenputs( message_line, 0, message );
  373.   if ( ++message_line>= 25 )
  374.     message_line = 20;
  375.   if ( !immediate_return )
  376.     display_tag_table( tag );
  377. }
  378.  
  379. /*
  380. * After all the work is done, I have to hide my heap screen so the user
  381. * can see the application output.  This is pretty easy to do, a routine
  382. * in SCREEN.C does the whole job for me.
  383. */
  384. void hide_screen()
  385. {
  386.   if ( screen_up != 0 ) {
  387.     screen_up = 0;
  388.     restore_screen();
  389.   }
  390. }

SCREEN.C

C:
  1. /*
  2. * Author:       Mark Nelson
  3. *
  4. * Date:         October 28, 1989
  5. *
  6. * Description:  This module contains the screen I/O routines used in
  7. *               the heap debugger module.  These are very simplified
  8. *               screen I/O routines.
  9. */
  10.  
  11. #include <stdio.h>
  12. #include <stdarg.h>
  13. #include <string.h>
  14. #include "_heap.h"
  15. /*
  16. * These are all the line drawing constants defined.
  17. */
  18. #define UL_CORNER       218
  19. #define UR_CORNER       191
  20. #define LL_CORNER       192
  21. #define LR_CORNER       217
  22. #define UPPER_TEE       194
  23. #define LOWER_TEE       193
  24. #define LEFT_TEE        195
  25. #define RIGHT_TEE       180
  26. #define CENTER_TEE      197
  27. #define HORIZONTAL_LINE 196
  28. #define VERTICAL_LINE   179
  29.  
  30. /*
  31. * I create a structure so I can write directly to screen as if it were
  32. * a big array.  That way the compiler takes care of computing the
  33. * addresses, all I have to do is insert the row and column.
  34. */
  35. struct video_element {
  36.                           unsigned char character;
  37.                           unsigned char attribute;
  38.                      };
  39. struct video_element (far *physical_screen)[25][80];
  40. struct video_element saved_screen[25][80];
  41.  
  42. /*
  43. * This routine draws the box I use up on the screen.  It is passed a
  44. * list of labels to draw at the head of the columns, plus a count
  45. * of how many rows are to be left open for data entry.  It depends
  46. * on some earlier code somewhere to have initialized an array called
  47. * columns[] that tells it where to draw each column on the screen.
  48. * There is a lot of code here to draw the boxes, but it is all
  49. * straightforward.
  50. */
  51. int columns[10];
  52. int column_count=0;
  53.  
  54. void draw_boxes_and_titles(char *labels[],int row_count)
  55. {
  56. int col;
  57. int row;
  58. int i;
  59. int j;
  60. int rows[3];
  61. /*
  62. * The three rows I define are the top and bottom of the box, plus the
  63. * line that divides the title lines from the data lines.
  64. */
  65.     rows[0]=0;
  66.     rows[1]=2;
  67.     rows[2]=3+row_count;
  68.     for (col=1;col<columns[column_count];col++)
  69.         for (i=0;i<3;i++)
  70.             (*physical_screen)[rows[i]][col].character = HORIZONTAL_LINE;
  71.     for (i=0;i<=column_count;i++)
  72.         for (row=0;row<(row_count+4);row++)
  73.             (*physical_screen)[row][columns[i]].character = VERTICAL_LINE;
  74.     (*physical_screen)[0][columns[0]].character = UL_CORNER;
  75.     (*physical_screen)[row_count+3][columns[0]].character = LL_CORNER;
  76.     (*physical_screen)[0][columns[column_count]].character = UR_CORNER;
  77.     (*physical_screen)[row_count+3][columns[column_count]].character = LR_CORNER;
  78.  
  79.     (*physical_screen)[rows[1]][columns[0]].character = LEFT_TEE;
  80.     (*physical_screen)[rows[1]][columns[column_count]].character = RIGHT_TEE;
  81.     for (j=1;j<column_count;j++)
  82.         (*physical_screen)[0][columns[j]].character = UPPER_TEE;
  83.     for (j=1;j<column_count;j++)
  84.         (*physical_screen)[row_count+3][columns[j]].character = LOWER_TEE;
  85.  
  86.     for (j=1;j<column_count;j++)
  87.         (*physical_screen)[rows[1]][columns[j]].character = CENTER_TEE;
  88. /*
  89. * Here is where I draw the labels.  They need to go in the center of
  90. * their little boxes.
  91. */
  92.     for (i=0;i<column_count;i++)
  93.     {
  94.         col=columns[i]+1;
  95.         col += (columns[i+1]-columns[i]-1)/2;
  96.         col -= strlen(labels[i])/2;
  97.         screenputs(1,col,labels[i]);
  98.     }
  99. }
  100. /*
  101. * This is a general purpose routine to print a formatted string on
  102. * the screen.
  103. */
  104. void screenputf(int row,int col,char *format,...)
  105. {
  106.     char buffer[81];
  107.     va_list args;
  108.  
  109.     va_start(args,format);
  110.     vsprintf(buffer,format,args);
  111.     screenputs(row,col,buffer);
  112. }
  113. /*
  114. * This is a general purpose routine to put an unformatted string
  115. * out to the screen.
  116. */
  117. void screenputs(int row,int col,char *string)
  118. {
  119. char c;
  120.  
  121.     while (1)
  122.     {
  123.         c=*string++;
  124.         if (c=='\0')
  125.             break;
  126.         (*physical_screen)[row][col++].character=c;
  127.     }
  128. }
  129. /*
  130. * This is a general purpose routine to clear a whole line on the
  131. * screen.
  132. */
  133. void screenclearline(int row)
  134. {
  135. int col;
  136.  
  137.     for (col=0;col<80;col++)
  138.         (*physical_screen)[row][col].character=' ';
  139. }
  140. /*
  141. * This is the screen initialization code.  It is a trap door routine that
  142. * gets called all the time, but only executes once.  It computes what
  143. * columns the vertical lines are going to go in, based on the widths needed
  144. * for each column, passed as a parameter.
  145. * Note that if you are using a monochrome monitor, you need to change
  146. * the screen pointer to be 0xb0000000L.
  147. * This routine also initializes the tag table
  148. */
  149. void initialize_screen(char *labels[],int widths[])
  150. {
  151. int row;
  152. int col;
  153. int i;
  154. static int first_time=0;
  155.  
  156.     if (first_time==0)
  157.     {
  158.         first_time=1;
  159.         columns[0]=1;
  160.         column_count=0;
  161.         while (strlen(labels[column_count]) != 0)
  162.         {
  163.             columns[column_count+1] = columns[column_count]+widths[column_count]+1;
  164.             column_count++;
  165.         }
  166.     }
  167.     physical_screen=(struct video_element (far *)[25][80])0xb8000000L;
  168.     for (row=0;row<25;row++)
  169.         for (col=0;col<80;col++)
  170.         {
  171.              saved_screen[row][col]=(*physical_screen)[row][col];
  172.              (*physical_screen)[row][col].character=' ';
  173.              (*physical_screen)[row][col].attribute=0x1b;
  174.         }
  175. }
  176.  
  177. /*
  178. *  Whenever the heap routines decide they need to print a screen message,
  179. *  they set up the screen first by calling this guy.
  180. */
  181. void setup_screen(char *labels[],int widths[],int rows)
  182. {
  183.     initialize_screen(labels,widths);
  184.     draw_boxes_and_titles(labels,rows);
  185. }
  186.  
  187. /*
  188. * After the heap routines are done printing debug information, they
  189. * have to restore the screen back to where it was when they got called.
  190. * This routine does that.
  191. */
  192. void restore_screen()
  193. {
  194. int row;
  195. int col;
  196.  
  197.     for (row=0;row<25;row++)
  198.         for (col=0;col<80;col++)
  199.              (*physical_screen)[row][col]=saved_screen[row][col];
  200. }

_HEAP.H

C:
  1. /* Prototypes from SCREEN.C  */
  2.  
  3. void draw_boxes_and_titles(char *labels[],int row_count);
  4. void screenputc(int row,int col,char c);
  5. void screenputf(int row,int col,char *format,...);
  6. void screenputs(int row,int col,char *string);
  7. void screenclearline(int row);
  8. void initialize_screen(char *labels[],int widths[]);
  9. void setup_screen(char *labels[],int widths[],int rows);
  10. void restore_screen(void);
  11.  
  12. /* Prototypes from HEAP.C */
  13.  
  14. void screen_message(int immediate_return, int tag, char *format,...);
  15. void hide_screen(void);
  16. void my_free(char *file_name,unsigned int line_number, void *block);
  17. void *my_malloc(char *file_name,unsigned int line_number,size_t size);
  18. void initialize_tags(void);
  19. void display_tag_table(int last_tag);
  20. void add_tag_to_table(char far *pointer,char maverick,size_t size,char *file_name,unsigned int line_number);
  21. void delete_tag_from_table(int tag);
  22. void verify_heap(void);
  23. void heap_walk(void);