chapter5.html

WRITING BUG-FREE C CODE.

 of the 32-bit pointers being returned by the heap interface.  The
 returned address could be composed of both segment and offset or it
 could be a flat memory pointer.  The calling code works the same in
 either case.
 <br><br>
To support <a href="chapter4.html#runtypecheck">run-time type checking &sect;4.4</a>,
 the memory allocator
 must be passed the address of a class descriptor.  If the object
 being allocated is not a class object, NULL should be passed as the
 class descriptor address.
 <br><br>
To support storage leak detection and symbolic heap dumps, a source
 filename and line number must be passed to the memory allocator.  It
 is assumed that the source filename address is always accessible.
 <br><br>
All the other heap manager requirements can be met within the heap
 manager.  With this information, the prototypes to the heap manager
 interface can be written as follows.
 <br><br>
<table bgcolor="#CCCCEE" cellpadding=0 cellspacing=0><tr><td><pre>
<b>The heap manager interface</b>
EXTERNC LPVOID APIENTRY FmNew      ( SIZET, LPCLASSDESC, LPSTR, int);
EXTERNC LPVOID APIENTRY FmFree     ( LPVOID );
EXTERNC LPVOID APIENTRY FmRealloc  ( LPVOID, SIZET, LPSTR, int );
EXTERNC LPVOID APIENTRY FmStrDup   ( LPSTR, LPSTR, int );
EXTERNC void   APIENTRY FmWalkHeap ( void );
EXTERNC BOOL   APIENTRY FmIsPtrOk  ( LPVOID );
</pre></tr></td></table>
 <br>
FmNew() (far memory new) takes a memory size, a class descriptor
 pointer, a source filename and line number as arguments.  It returns
 a pointer to the allocated memory.
 <br><br>
FmFree() (far memory free) takes a pointer to a previously allocated
 block of memory as an argument and returns the NULL pointer. 
 Passing NULL to FmFree() is allowed and no action is taken in this
 case.
 <br><br>
FmRealloc() (far memory realloc) is used to reallocate the size of a
 block of memory.
 <br><br>
FmStrDup() (far memory string dup) is used to duplicate a string.  It
 is intended to replace strdup().
 <br><br>
FmWalkHeap() (far memory heap walk) walks the heap displaying every
 item in the heap.
 <br><br>
FmIsPtrOk() (far memory address validation) is used to validate that
 the given pointer is a valid address.
 <br><br>
<b>5.2.4 The Design</b>
 <br><br>
The new heap manager takes the classic approach of providing a
 wrapper around a system's current heap manager.  The wrapper
 includes both code and data.  (See Figure 5-2).
 <blockquote>
 <img src="images/fig5-2.gif"><br>
 Figure 5-2: Viewing an object in the heap.
 </blockquote>
The code wrapper is in the form of the new FmNew() and FmFree()
 function calls that sit upon a system's existing malloc() and free()
 calls.
 <br><br>
The data wrapper is in the form of a prefix structure that sits in
 front of a block of allocated memory and a postfix structure that
 sits after the block of memory.
 <br><br>
The new heap manager is the only code that interfaces with the old
 heap manager.  This is important since in order to run-time type
 check objects in the heap, the run-time type checking code assumes
 the new heap manager view, one in which heap objects are prefixed
 with type checking information.
   <blockquote><table bgcolor="#E0E0E0" border=1 cellpadding=2 cellspacing=0><tr><td>
   The new heap manager is the only code that interfaces with the old
   heap manager.
   </tr></td></table></blockquote>
The prefix structure is a container for holding information that
 needs to be associated with the object that is allocated.  It
 contains type information, source filename and line number
 information and whatever else is needed to meet the heap manager's
 requirements.
 <br><br>
The postfix structure is for detecting memory overwrites past the end
 of an allocated object.  While it is no substitute for hardware
 overwrite protection and does not catch all memory overwrites, it
 catches the majority of memory overwrites.  Most memory overwrites
 are caused by overwriting the end of a string buffer.  This type of
 overwrite is caught by the usage of a postfix structure.
 <br><br>
A way to walk the heap is still needed in order to provide symbolic
 heap dumps and to detect storage leaks.  Some environments provide a
 mechanism for walking the heap, while others provide no such
 mechanism.  Rather than making any assumptions about the environment
 that you are running under, heap walking support is provided by the
 new heap manager.  The simplest way to implement this is through a
 doubly linked list.  This requires a next and previous pointer
 stored in the prefix structure.
 <br><br>
All other requirements previously specified are implementation
 details.  The layout of the prefix and postfix structures can now be
 designed.
 <br><br>
<table bgcolor="#CCCCEE" cellpadding=0 cellspacing=0><tr><td><pre>
<b>The prefix and postfix structures</b>
/*--- Declare what LPPREFIX/LPPOSTFIX are ---*/
typedef struct tagPREFIX  FAR*LPPREFIX;
typedef struct tagPOSTFIX FAR*LPPOSTFIX;

/*--- Prefix structure before every heap object---*/
typedef struct tagPREFIX {
    LPPREFIX lpPrev;           /* previous object in heap      */
    LPPREFIX lpNext;           /* next object in heap          */
    LPPOSTFIX lpPostfix;       /* ptr to postfix object        */
    LPSTR lpFilename;          /* filename ptr or NULL         */
    long lLineNumber;          /* line number or 0             */
    LPVOID lpMem;              /* FmNew() ptr of object        */
    LPCLASSDESC lpClassDesc;   /* class descriptor ptr or NULL */
    } PREFIX;

/*--- Postfix structure after every heap object ---*/
typedef struct tagPOSTFIX {
    LPPREFIX lpPrefix;
    } POSTFIX;
</pre></tr></td></table>
 <br>
The prefix structure contains lpPrev and lpNext for maintaining a
 linked list of objects in the heap; lpPostfix, for pointing to the
 postfix structure after the heap object; lpFilename and lLineNumber,
 for source filename and line number support; lpMem and lpClassDesc,
 for run-time type checking support.
 <br><br>
The postfix structure could contain anything since it is being used
 for memory overwrite detection.  The contents of the structure are
 initialized when the heap object is created and verified when the
 heap object is destroyed.  However, instead of filling in the
 structure with a constant value when the heap object is created and
 checking that constant when the heap object is destroyed, it is
 better to use a value that varies from heap object to heap object. 
 A mechanism for achieving this result is to use a pointer back to
 the prefix object.
 <br><br>
The only real outstanding issue is alignment preservation.  Because
 malloc() returns a pointer that is correctly aligned, the prefix
 structure is properly aligned.  The pointer that is returned from
 FmNew() immediately follows the prefix structure.  You have two
 choices to make sure this pointer is aligned:  Either align it in
 code, or make sure that the size of the prefix structure is a
 multiple of the alignment.  The simplest technique is to make sure
 that the prefix structure is a multiple of the alignment.  If it is
 not, pad the structure with dummy data items.  In doing so, however,
 make sure that you pad at the beginning of the structure and not at
 the end.  This is because the lpMem and lpClassDesc data items must
 be next to the allocated object.  The prefix structure is currently
 correct for an alignment of sizeof(int).  You can change the
 ALIGNMENT macro if sizeof(int) is incorrect for your environment. 
 The CompilerAssert() macro should be used to guarantee the correct
 alignment.
 <br><br>
<table bgcolor="#CCCCEE" cellpadding=0 cellspacing=0><tr><td><pre>
<b>Guaranteeing correct prefix structure alignment</b>
#define ALIGNMENT (sizeof(int))
CompilerAssert(ISPOWER2(ALIGNMENT));
CompilerAssert(!(sizeof(PREFIX)%ALIGNMENT));
</pre></tr></td></table>
 <br>
The ALIGNMENT define and the ISPOWER2 CompilerAssert are placed near
 the top of the source file.  The PREFIX CompilerAssert is placed in
 the source file after the prefix structure has been declared.
 <br><br>
The pointer returned from FmNew() is now properly aligned.  To
 properly align the postfix structure, use the same trick as before,
 but this time in code.  Simply take whatever size is passed into
 FmNew() and increase its size, if needed, to the nearest alignment
 boundary.
 <br><br>
<table bgcolor="#CCCCEE" cellpadding=0 cellspacing=0><tr><td><pre>
<b>Aligning a memory size, assumes no overflow</b>
#define DOALIGN(num) (((num)+ALIGNMENT-1)&~(ALIGNMENT-1))
</pre></tr></td></table>
 <br>
The DOALIGN() macro aligns a number up to the nearest ALIGNMENT
 boundary.  It assumes that there is no overflow and that ALIGNMENT
 is a power of two (the reason for the ISPOWER2 CompilerAssert()
 above).
 <br><br>
<b>5.2.5 FmNew() Implementation</b>
 <br><br>
<table bgcolor="#CCCCEE" cellpadding=0 cellspacing=0><tr><td><pre>
<b>FmNew() function</b>
LPVOID APIENTRY FmNew( SIZET wSize, LPCLASSDESC lpClassDesc,
    LPSTR lpFile, int nLine )
{
  LPPREFIX lpPrefix;
  wSize = DOALIGN(wSize);
  lpPrefix=(LPPREFIX)malloc(sizeof(PREFIX)+wSize+sizeof(POSTFIX));
  if (lpPrefix) {
    AddToLinkedList( lpPrefix );
    lpPrefix-&gt;lpPostfix = (LPPOSTFIX)((LPSTR)(lpPrefix+1)+wSize);
    lpPrefix-&gt;lpPostfix-&gt;lpPrefix = lpPrefix;
    lpPrefix-&gt;lpFilename = lpFile;
    lpPrefix-&gt;lLineNumber = nLine;
    lpPrefix-&gt;lpMem = lpPrefix+1;
    lpPrefix-&gt;lpClassDesc = lpClassDesc;
    memset( lpPrefix-&gt;lpMem, 0, wSize );
    }
  else {
    AssertError;             /* Report out of memory error */
    }
  return(lpPrefix ? lpPrefix+1 : NULL);

} /* FmNew */
</pre></tr></td></table>
 <br>
The implementation of FmNew() is straightforward.  The first thing to
 do is align wSize up to the nearest alignment boundary.  A block of
 memory is then allocated, the size of which is big enough to hold
 the prefix structure, the user block of memory and the postfix
 structure.
 <br><br>
The call is to malloc(), a 32-bit memory interface.  The 32-bit
 memory allocator may be called by other names in other environments.
  Simply replace malloc() with a call that is appropriate to your
 environment.
 <br><br>
If the memory allocation fails, the FmNew() code essentially exits
 with NULL.  You may want to implement a policy where memory
 allocations must succeed and if they do not, the FmNew() function
 does not return to the calling code.
 <br><br>
If the memory allocation succeeds, the first thing to do is add the
 memory block to the doubly linked list of memory blocks, by calling
 AddToLinkedList().
 <br><br>
<table bgcolor="#CCCCEE" cellpadding=0 cellspacing=0><tr><td><pre>
<b>AddToLinkedList() function</b>
static LPPREFIX lpHeapHead=NULL;

void LOCAL AddToLinkedList( LPPREFIX lpAdd )
{
    /*--- Add before current head of list ---*/
    if (lpHeapHead) {
        lpAdd-&gt;lpPrev = lpHeapHead-&gt;lpPrev;
        (lpAdd-&gt;lpPrev)-&gt;lpNext = lpAdd;
        lpAdd-&gt;lpNext = lpHeapHead;
        (lpAdd-&gt;lpNext)-&gt;lpPrev = lpAdd;
        }
    /*--- Else first node ---*/
    else {
        lpAdd-&gt;lpPrev = lpAdd;
        lpAdd-&gt;lpNext = lpAdd;
        }
    /*--- Make new item head of list ---*/
    lpHeapHead = lpAdd;

} /* AddToLinkedList */
</pre></tr></td></table>
 <br>
Once added to the linked list, lpPostfix is filled in to point to the
 postfix structure.  The lpPrefix data item within the postfix
 structure is then filled in.  It simply points back to the prefix
 structure.  Next, the lpFilename and lLineNumber data items are
 initialized from the arguments passed to FmNew().  Finally, the
 lpMem and lpClassDesc data items are initialized for purposes of
 run-time type checking.
 <br><br>
Finally, the block of user memory is zero initialized by calling
 memset().
 <br><br>
<b>5.2.6 FmFree() Implementation</b>
 <br><br>
<table bgcolor="#CCCCEE" cellpadding=0 cellspacing=0><tr><td><pre>
<b>FmFree() function</b>
LPVOID APIENTRY FmFree( LPVOID lpMem )
{
    if (VerifyHeapPointer(lpMem)) {
       LPPREFIX lpPrefix=(LPPREFIX)lpMem-1;
       SIZET wSize=(LPSTR)(lpPrefix-&gt;lpPostfix+1)-(LPSTR)lpPrefix;
       RemoveFromLinkedList( lpPrefix );
       memset( lpPrefix, 0, wSize );
       free(lpPrefix);
       }
    return (NULL);

} /* FmFree */
</pre></tr></td></table>
 <br>
The FmFree() implementation is straightforward, provided that an
 effective VerifyHeapPointer() can be written.  This function has all
 the implementation problems that run-time type checking has. 
 VerifyHeapPointer(), in order to be completely robust, must be
 tailored to a specific machine architecture.
 <br><br>
Provided that the memory pointer passed to FmFree() is indeed a valid
 heap pointer, VerifyHeapPointer() allows the body of FmFree() to
 execute.  The first thing to do is calculate a pointer to the prefix
 structure.  The size of the object is calculated next and assigned
 to wSize. The heap object pointed to is removed by calling
 RemoveFromLinkedList().
 <br><br>
<table bgcolor="#CCCCEE" cellpadding=0 cellspacing=0><tr><td><pre>
<b>RemoveFromLinkedList() function</b>
void LOCAL RemoveFromLinkedList( LPPREFIX lpRemove )
{
    /*--- Remove from doubly linked list ---*/
    (lpRemove-&gt;lpPrev)-&gt;lpNext = lpRemove-&gt;lpNext;
    (lpRemove-&gt;lpNext)-&gt;lpPrev = lpRemove-&gt;lpPrev;
    /*--- Possibly correct head pointer ---*/
    if (lpRemove==lpHeapHead) {
        lpHeapHead = ((lpRemove-&gt;lpNext==lpRemove) ? NULL : 
            lpRemove-&gt;lpNext);
        }

} /* RemoveFromLinkedList */
</pre></tr></td></table>
 <br>
Once the memory object has been removed from the doubly linked list,
 the memory block is initialized to zero.
 <br><br>
Finally, free() is called to deallocate the memory block.  The 32-bit
 memory deallocator may be called by other names in other
 environments.  Simply replace free() with a call that is appropriate
 to your environment.
 <br><br>
NULL is always returned from the FmFree() function.  This is done to
 help implement the policy that a pointer is either valid or it is
 NULL (see <a href="chapter7.html#pointers">&sect;7.12</a>).
 A pointer variable should never point to an
 invalid memory object.  The memory macros use the NULL return value
 to store in the memory pointer passed to FmFree().
 <br><br>
<b>5.2.7 VerifyHeapPointer() Implementation</b>
 <br><br>
<table bgcolor="#CCCCEE" cellpadding=0 cellspacing=0><tr><td><pre>
<b>VerifyHeapPointer() function</b>
BOOL LOCAL VerifyHeapPointer( LPVOID lpMem )
{
  BOOL bOk=FALSE;
  if (lpMem) {
    WinAssert(FmIsPtrOk(lpMem)) {
      LPPREFIX lpPrefix=(LPPREFIX)lpMem-1;
      WinAssert(lpPrefix-&gt;lpMem==lpMem) {
        WinAssert(lpPrefix-&gt;lpPostfix-&gt;lpPrefix==lpPrefix) {
          bOk = TRUE;
          }
        }
      }
    }
  return (bOk);