heapinfo.txt

一个堆栈管理器的源码

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

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


        This document describes a replacement heap manager for MSC 5.1.
        The library is binary compatible with the original MSC functions
        so recompilation is not necessary.  All of the new functions are
        exact replacements for the original MSC "far" heap functions.


I. General

   The replacement heap manager differs from the original MSC heap
   manager in a number of ways.  The following sections address each
   of the differences according to the following categories:
   
       - Section II   : functionality and performance

       - Section III  : flexibility and user control

       - Sectiom IV   : error handling and debugging

       - Section V    : compatibility with MSC run-time library

       - Section VI   : distribution files

       - Section VII  : version notes

       - Section VIII : licensing and distribution


   There is also a difference in the approach to the design of the
   software.  The design of the MSC heap manager seems to be based on
   a philosophy of procrastination.  I.e., processing is deferred until
   it is absolutely necessary.  This approach enhances the performance
   of basic operations but degrades the overall performance of the
   system. (Penny-wise and pound-foolish).

   In contrast, the replacement heap manager is a philosophical
   activist.  I.e., processing is performed as soon as convenient.
   This alternate approach uses more sophisticated basic operations in
   an attempt to maintain the system in the best condition possible.
   (Penny-foolish but pound-wise).

   In practice the MSC heap manager may avoid some work that the
   replacement heap manager undertakes.  On the other hand, the
   MSC heap manager is often confronted with pathological situations
   of its own construction.  The replacement heap manager attempts to
   avoid such unpleasantness.

   In fact the objectives of the two designs are more easily decribed
   by what they avoid than what they pursue.  The MSC heap manager
   avoids work while the replacement heap manager avoids failure.

   If you have a heap-intensive application that does not use much
   memory and maximum performance is worth an occasional crash
   "out of heap memory" stick with the original MSC heap manager.
   It is heavily optimized toward small applications.  If you need
   to manage large heaps, or are tight on memory, or need reliable
   performance, then the replacement heap manager may be useful.


II. Functionality and performance

   These differences are fundamental to the value of the replacement
   heap manager.  They define how well the heap manager does its
   primary job: managing the heap.


   A. Efficient use of memory

      The replacement heap manager does not inadvertently fragment the
      heap in as many ways as the MSC heap manager.  It allows the
      user program to define the direction in which the heap should
      be optimized.

      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.

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

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

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


   B. Default data segment automatically minimized at startup.

      The link switch /cp does not affect exec/spawned programs.
      They always get a 64Kb default data segment no matter how
      they are built or adjusted with exemod.  The replacement
      heap manager handles this problem automatically.  The "near"
      heap is shrunk to the minimum and the rest of the memory is
      returned to DOS.

      Credit for this goes to Compuserve/MSSYS/DL3/alloc.arc/reducedd.c
      by Willard Gersbacher [76117,2611].  It is a neat and clean
      solution to the lack of cooperation between MS-DOS and MS-C.


   C. Rational handling of NULL pointers and requests for zero bytes

      There is confusion regarding requests for zero bytes and
      handling of NULL pointers.  The following discussion attempts
      to clarify the documented behavior of the MSC routines, the
      actual behavior of the MSC routines, and the behavior of the
      replacement routines.

      1. _Msize()

         The MSC documentation does not address the result of
         _msize(NULL).  The actual result is some kind of core
         constant.

         The replacement version of _msize( NULL ) returns zero.


      2. Malloc()

         The MSC documentation states that malloc(0) returns NULL.
         This is not true.  Malloc(0) returns a pointer to a
         zero-length entry.

         The replacement is exactly the same.


      3. Calloc()

         The MSC documentation states that calloc(0,n) and calloc(n,0)
         return NULL.  This is not true.  Calloc(0,0) returns a pointer
         to a zero-length entry.

         The replacement is exactly the same.


      4. _Expand()

         The MSC documentation does not address the behavior of
         _expand() when called with a NULL pointer or a zero length.
         The actual behavior is detailed below.

               _expand(  NULL,   0 ) returns NULL

               _expand(  NULL, 100 ) returns NULL

               _expand( !NULL,   0 ) returns a pointer to   0 bytes

               _expand( !NULL, 100 ) returns a pointer to 100 bytes

         The replacement is exactly the same.


      5. Realloc()

         The MSC documentation specifies that realloc( NULL, size )
         functions like malloc( size ) and that realloc( pointer, 0 )
         returns NULL.  This is correct except for the case covered
         by both rules (they conflict).  The actual behavior of
         realloc( NULL, 0 ) is to return a pointer to zero bytes as
         shown below.

               realloc(  NULL,   0 ) returns a pointer to   0 bytes

               realloc(  NULL, 100 ) returns a pointer to 100 bytes

               realloc( !NULL,   0 ) returns NULL

               realloc( !NULL, 100 ) returns a pointer to 100 bytes

         Because the conflict between the realloc() rules creates
         an inconsistency and because of the problems with the
         malloc() documentation vs behavior the replacement for
         realloc() is rational rather than exact.  The difference is
         that realloc( pointer, 0 ) returns a pointer to zero bytes
         instead of NULL.


      6. The file stdmsc.c is an easy way to verify the accuracy of
         the information provided here.


   D. DOS interface

      The MSC heap manager's interface to DOS automatically rounds
      _amblksiz up to the next power of two when extending the heap
      memory pool.  This action encourages fragmentation of the heap
      because user requests for memory are not usually oriented around
      the powers of two so there are gaps left in the heap when the
      heap is extended.

      The replacement heap manager does not force power-of-two sizing
      on the DOS interface.  It rounds _amblksiz up to the next paragraph
      only.  This approach gives the application program precise control
      over the heap.


   E. Consistent "far" and "huge" heap handling

      The Intel architecture, segmented and non-relocatable, is indeed
      "brain-dead", but this has been obvious for decades.  The modern
      problem has more to do with software that amplifies the deficiency
      rather than dealing with it.


      1. The MSC heap manager cannot handle "huge" heap entries.
         Instead the application program must use the DOS memory
         manager via halloc() for regions that exceed a segment
         (64Kb).  This requirement imposes three negative conditions
         on application programs.


         a. DOS is slow.

            The DOS memory manager has a lot of overhead.  While
            large blocks of memory are usually not volatile, there is
            no reason to impose an unnecessary performance penalty.


         b. Lack of functionality

            The MSC heap manager includes only halloc() and hfree().
            There is no hrealloc(), nor is there a query function
            to determine the size of an allocated region.


         c. No safe way to deal with both types of heap memory

            The distinction between "far" and "huge" heap pointers
            is an onerous one.  It requires application programs
            to decide, depending on the size of the request, which
            function to use to obtain the memory block.  Then the
            application must record the selection in order to properly
            dispose of the memory.  Free() will not handle a huge
            heap pointer, and hfree() will not handle a "far" heap
            pointer.


       2. The replacement heap manager deals with these problems
          by providing a single handler for all address models.
          There is no need to segregate the "far" and "huge" heap
          entries.  In addition to simplifying things for the user,
          this also cuts down on the heap fragmentation and allows
          complete optimization of heap access via _heapmode.

          Unfortunately, maintaining syntactic compatibility with
          the MSC heap manager implies that the limitations of that
          design continue to influence the use of the heap.  E.g.,
          in order to precisly mimic the MSC heap manager, calloc()
          will fail to allocated an area larger than 64Kb.  For that
          you need halloc().

          This is irritating, but not crippling because halloc() is
          a proper superset of calloc().  You can use it anywhere that
          you can use calloc().  Similarly, _hmsize() is valid anywhere
          that _msize() is valid. (However, these substitutions imply
          data conversions of size_t to long).

          The superset functions are as follows:

                Old         New        
              -------     --------     
              calloc      halloc       As per MSC

               _expand    _hexpand     Replacement heap manager only

              free        hfree        As per MSC

              realloc     hrealloc     Replacement heap manager only

              _msize      _hmsize      Replacement heap manager only


   F. Benchmarks

      Like all benchmarks, testing a heap manager empirically is an
      invitation to distortion, but it is worth mentioning.  Depending
      on the pattern of use the MSC heap manager is either twice as
      fast as the replacement or 100 times slower.  Two orders of
      magnitude is a lot of variability!


      1. Speed

         The above comparison uses the replacement heap manager as
         the reference point because its performance is predictable.