heap.man

一个堆栈管理器的源码

               Manual for Replacement Heap Manager for MSC
               -------------------------------------------

        Copyright (c) 1990 by Optimal Software, All Rights Reserved


            This file contains manual pages for the replacement
            heap manager library.


I. Overview

   This section provides introductory information on the heap manager
   library.  The function descriptions are in section II.

   1. Organization

      Part I of the heap manager library manual is organized as follows

        - Section 2 provides general rules for using the replacement
                    heap manager library.

        - Section 3 describes the variables and types that are
                    declared by the heap manager and used by
                    the library routines.

        - Section 4 summarizes the heap management functions and
                    provides a brief description of each function.

        - Section 5 explains the contents of the heap manager include
                    files heap.h and heap.i.

      Part II consists of detailed reference pagesf for the individual
      heap access functions.


   2. Using the heap management fuctions

      This section provides the background information and the general
      rules that apply to programs using the replacement heap manager.


      a. Function prototypes

         All of the heap management functions are declared as
         prototypes with both a return type and a complete argument
         list.  The functions that are unique to the replcement heap
         manager are disabled by the STDMSC symbol to provide strict
         compatibility with malloc.h from the MSC run-time library.


      b. Stack checking

         Stack checking is disabled for all heap management functions.


      c. Type checking

         The heap management functions are declared with complete
         argument lists.


      d. Error handling

         The replacement heap manager handles errors the same way
         the original MSC heap manager does.  Where possible, the
         function detecting the error returns a result indicating
         that a problem exists.


         i. _HEAPCHECK -- reporting invalid pointers

            This symbol affects functions that have pointer arguments.
            It should be defined as a stream file variable like
            stdout, stderr, or an application log file.  The effect
            of _HEAPCHECK is to enable alternate functions, with a 
            suffix of '_c', that report invalid pointers by writing
            a diagnostic message to the indicated stream file.


         ii. _HEAPDEBUG -- checking the heap for errors

            This symbol affects functions that alter the state of
            the heap (except _heapset which is a debugging routine).
            It should be defined as a stream file variable like
            stdout, stderr, or an application log file.  The effect
            of _HEAPDEBUG is to enable alternate functions, with a
            suffix of '_d', that check the heap integrity before
            every heap transaction.  The alternate functions also
            record heap transations with a sequence number, the
            name of the function, the desired size of the affected
            heap entry, and the source file name and line number.

            The error checks are performed by _fheapchk, and include
            inspecting the safety margins of each heap entry for
            corruption, verifying the integrity of read-only heap
            entries, and checking each heap control block for
            consistency and reciprocity.

            When an error is detected the alternate heap functions
            produce a diagnostic report giving the error status,
            the function which detected the error, details on the
            affected heap entry, and a complete report on the state
            of the heap.

            When the heap is initialized the heap debugger prints
            "Heap debugging active" to stdout to remind you that some
            module is compiled with the debugger on so that you do not
            accidentally release software in test mode.  The object
            module, but not the executable file, contain messages
            that label files compiled with the debugger active.  Thus
            you can find a forgotten module and recompile it.

            The _HEAPDEBUG symbol includes and superceeds the effects
            of the _HEAPCHECK symbol.


         iii. _HEAPTRACE -- recording heap activity.

            This symbol affects functions that alter the state of the
            heap (except _heapset which is a debugging routine).
            It should be defined as a stream file variable like
            stdout, stderr, or an application log file.  The effect
            of _HEAPTRACE is to enable alternate functions, with a
            suffix of '_t', that report each heap transaction.  The
            transaction reports are written to the indicated stream
            file, and include the transaction sequence number, the
            name of the function involved, the value of its parameters,
            the source file name and line number of the function
            activation, and the value returned by the function.
            
            The _HEAPTRACE symbol includes and superceeds the effects
            of the _HEAPDEBUG symbol.


   3. Global variables and standard types


      a. size_t _amblksiz;

         The _amblksize variable controls the size of allocation
         requests made to the operating system.  It is identical
         to the _amblksiz of the MSC heap manager, described on
         page 33 of the MSC 5.1 Optimizing Compiler Run-Time Library
         Reference, with one exception.  The replacement heap manager
         does not impose a power-of-two requirement on the size of
         allocated blocks.  This change gives application programs
         precise control over the heap, and limits heap fragmentation.


      b. int _heapmode;

         In order to expedite allocation operations there is a global
         list of free chunks.  The list is doubly linked, and ordered
         as defined by _heapmode.  MSC does not appear to have a free
         list.  It seems to rely on the hope that garbage collection is
         infrequent to compensate for the fact than searching the entire
         heap for free entries is extremely expensive.

         The replacement heap manager optimizes its operations based on
         the value of the variable _heapmode.


            i. _HEAPTIME

               The _HEAPTIME setting sacrifices space efficiency for
               performance.  The free list is not maintained in order
               and allocation takes the first entry that fits (LIFO).
               This setting is useful for programs with small amounts
               of volatile data.

               This setting also tries to meet allocation needs without
               merging free blocks.  If the allocation fails the free
               list is condensed and another attempt is made.  The MSC
               heap manager operates in a similar manner, fragmenting
               the heap and wasting space in an attempt to save time.


            ii. _HEAPSIZE

               If _heapmode is _HEAPSIZE the heap manager minimizes
               the space occupied by the heap by maintaining the free
               list in address order (first fit).  This technique tends
               to keep the in-use heap entries in low memory so that
               _heappack() can release unused space back to DOS.  This
               setting is useful for programs which spawn other programs,
               or use large buffers, or are generally tight on memory.


            iii. _HEAPSPACE

               If _heapmode is _HEAPSPACE the heap manager minimizes
               the wasted heap space by maintaining the free list in
               order of size (best fit).  This technique permits the
               most effective use of the available heap space.  It is
               useful for programs that must handle overflow via disk
               files.  The efficient utilization of heap memory minimizes
               the need for disk access.

         Note that changing the _heapmode on the fly does not
         automatically re-order the free list.  Neither does it cause
         problems.  As the heap is used the free list will lose the
         old ordering and conform to the new optimization.

         The default mode is described by _HEAPMODE and may be set
         from the compiler command line when the library is built by
         defining the symbol _HEAPMODE.  E.g., -D_HEAPMODE=_HEAPSIZE.
         The factory setting is _HEAPTIME as this is the closest
         approximation to the original MSC heap manager.


      c. size_t _heappad

         A classic problem in heap management is writing past the end
         of a buffer obtained from the heap.  This typically produces
         extremely hostile effects.  As the routines that handle
         heap-generated buffers are usually embedded in the lower layers
         of software, checking them can be tedious.

         One method of testing this mode of failure is to add extra space
         at the ends of the allocated areas.  If the failures stop, there
         is evidence of a heap problem.  Of course, changing sizes moves
         things around which can turn errors on and off randomly so the
         evidence is flimsy.  The problem with this debugging technique
         is that changing the buffer lengths manually is a time-consuming,
         error-prone operation with marginal utility.

         The replacement heap manager provides a control for automatically
         extending all heap allocation requests.  Thus an initialization
         parameter is enough to provide evidence for or against heap
         problems.  Typically the padding is set to one or two times the
         size of the structures being manipulated.

         Because the padding affects the distance between the data area
         and the heap control structures it cannot be changed after the
         heap has been initialized.  The heap manager takes a copy of
         _heappad when the heap is initialized and uses the copy thereafter.
         Thus _heappad must be set as early as possible, typically in main().

         Note that command-line wild cards processed with setargv.obj use
         the heap before main is started.  Normal programs without wild
         card expansion can use:

               extern size_t _heappad;   /* declare the global variable */

               int main()
               {
               _heappad = 100;           /* set the value */
               }

         But programs with wild card handling enabled (those linked with
         the special version of setargv.obj) must use:

               size_t _heappad = 100;    /* define the global and its value */

               int main()
               {
               }

         This sets the value at compile/link time rather than at run time.

         The safety margins are automatically filled when a heap entry
         is allocated.  The fill pattern is initially alternating bits,
         0x55, but it is reset by every call to _heapset().  _Heapchk()
         compares the two safety margins and reports _HEAPBADPTR if they
         differ.


      d. Heap data structures and types

         Heap.h defines several structures which represent heap
         control blocks.  The _heapinfo structure and the size_t type
         are identical to the MSC versions.  The other structures are
         unique to the replacement heap manager.


         i. _ARENA

            The _ARENA structure describes a block of memory obtained
            from the operating system or other source of heap memory.
            Arenas are linked together in a doubly-linked list.  Within
            each arena the heap manager keeps track of the used and
            free regions with _CHUNK control blocks.


         ii. _CHUNK

            The _CHUNK structure describes a block of memory that is
            either in use by an application program or free to be
            allocated.  The chunks within an arena are linked together
            in a doubly-linked list.  The free chunks are also linked
            into the global free list.
 

         iii. _LINK

            The _LINK structure describes a pair of pointers to
            aligned structures.  It is the basis for the doubly-linked
            lists on which the heap management algorithms are based.


      e. The linker vs module-arity

         The replacement heap management functions are designed to
         superceed the original functions contained in the standard
         C run-time libraries.  Unfortunately, the standard linker is
         not able to handle the replacement process reliably.  It
         requires the /NOE switch to disable extended library searches
         in order to avoid spurious messages of the form:

             "symbol multiply defined, use /NOE"

         With the /NOE switch, the linker is unable to resolve references
         between libraries properly.  For example, your application
         program might refer to _fmalloc() and printf().  The _fmalloc()
         reference will be resolved when the replacement heap library
         is processed.  The printf() reference will be resolved when
         the default C run-time library is processed.  But printf() calls
         _getbuf() which calls malloc() which is in a module with _fmalloc().
         The linker ignores the malloc() in the replacement library and uses
         the one in the default library pulling in a second definition of
         _fmalloc().  So there are two definitions of _fmalloc(), one from
         each library, and the linker complains:

            "symbol defined more than once"

         The simplest solution to this problem is to remove the MSC
         heap management functions from the default C run-time library.
         This solution requires absolute faith in the compatibility and
         reliability of the replacement heap manager.  A less drastic
         method is to arrange the functions in the replacement library
         into modules that exactly match the modules in the original
         library.  This insures that collisions of the form described
         above are impossible.  It also allows easy integration of the
         replacement library with the old library because the one-for-one
         module matching is assured by use of the same module names.

         Thus the replacement library is not fully decomposed into
         individual functions.  Multi-function modules in the original
         library have been replicated in the replacement library.  The
         non-singular modules are as follows:


            Module name                 Functions included
            ------------    --------------------------------------------
            fheapchk        _fheapchk    _fheapset

            fmalloc         _ffree       _fmalloc     free(f)    malloc(f)

            fmsize          _fmsize      _msize(f)

            freect          _freect      _memavl      _memmax

            halloc          halloc       hfree

            nheapchk        _nheapchk    _nheapset  

            nmalloc         _nfree       _nmalloc     free(n)    malloc(n)

            nmsize          _nmsize      _msize(n)

            xheapchk        _heapchk     _heapset     _heapwalk


            Functions with an (f) suffix exist in libraries built with
            the "far" data address model ("compact" and "large" models).
            Functions with an (n) suffix exist in libraries build with
            the "near" data address model ("small" and "medium").
         

   4. Memory allocation summary