home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 7 / FreshFishVol7.bin / bbs / gnu / libg++-2.6-fsf.lha / libg++-2.6 / libg++ / src / malloc.c < prev    next >
Text File  |  1993-08-14  |  35KB  |  1,206 lines
  1. /* 
  2.   A version of malloc/free/realloc written by Doug Lea and released to the 
  3.   public domain. 
  4.  
  5.   VERSION 2.5
  6.  
  7. * History:
  8.     Based loosely on libg++-1.2X malloc. (It retains some of the overall 
  9.        structure of old version,  but most details differ.)
  10.     trial version Fri Aug 28 13:14:29 1992  Doug Lea  (dl at g.oswego.edu)
  11.     fixups Sat Aug  7 07:41:59 1993  Doug Lea  (dl at g.oswego.edu)
  12.       * removed potential for odd address access in prev_chunk
  13.       * removed dependency on getpagesize.h
  14.       * misc cosmetics and a bit more internal documentation
  15.       * anticosmetics: mangled names in macros to evade debugger strangeness
  16.       * tested on sparc, hp-700, dec-mips, rs6000 
  17.           with gcc & native cc (hp, dec only) allowing
  18.           Detlefs & Zorn comparison study (to appear, SIGPLAN Notices.)
  19.  
  20. * Overview
  21.  
  22.   This malloc, like any other, is a compromised design. 
  23.  
  24.   Chunks of memory are maintained using a `boundary tag' method as
  25.   described in e.g., Knuth or Standish.  The size of the chunk is
  26.   stored both in the front of the chunk and at the end.  This makes
  27.   consolidating fragmented chunks into bigger chunks very fast.  The
  28.   size field also hold a bit representing whether a chunk is free or
  29.   in use.
  30.  
  31.   Malloced chunks have space overhead of 8 bytes: The preceding and
  32.   trailing size fields.  When a chunk is freed, 8 additional bytes are
  33.   needed for free list pointers. Thus, the minimum allocatable size is
  34.   16 bytes.  8 byte alignment is currently hardwired into the design.
  35.   This seems to suffice for all current machines and C compilers.
  36.   Calling memalign will return a chunk that is both 8-byte aligned
  37.   and meets the requested (power of two) alignment.
  38.  
  39.   It is assumed that 32 bits suffice to represent chunk sizes.  The
  40.   maximum size chunk is 2^31 - 8 bytes.  malloc(0) returns a pointer
  41.   to something of the minimum allocatable size.  Requests for negative
  42.   sizes (when size_t is signed) or with the highest bit set (when
  43.   unsigned) will also return a minimum-sized chunk.
  44.  
  45.   Available chunks are kept in doubly linked lists. The lists are
  46.   maintained in an array of bins using a power-of-two method, except
  47.   that instead of 32 bins (one for each 1 << i), there are 128: each
  48.   power of two is split in quarters.  Chunk sizes up to 128 are
  49.   treated specially; they are categorized on 8-byte boundaries.  This
  50.   both better distributes them and allows for special faster
  51.   processing.
  52.  
  53.   The use of very fine bin sizes closely approximates the use of one
  54.   bin per actually used size, without necessitating the overhead of
  55.   locating such bins. It is especially desirable in common
  56.   applications where large numbers of identically-sized blocks are
  57.   malloced/freed in some dynamic manner, and then later are all freed.
  58.   The finer bin sizes make finding blocks fast, with little wasted
  59.   overallocation. The consolidation methods ensure that once the
  60.   collection of blocks is no longer useful, fragments are gathered
  61.   into bigger chunks awaiting new roles.
  62.  
  63.   The bins av[i] serve as heads of the lists. Bins contain a dummy
  64.   header for the chunk lists. Each bin has two lists. The `dirty' list
  65.   holds chunks that have been returned (freed) and not yet either
  66.   re-malloc'ed or consolidated. (A third free-standing list contains
  67.   returned chunks that have not yet been processed at all.) The `clean'
  68.   list holds split-off fragments and consolidated space. All
  69.   procedures maintain the invariant that no clean chunk physically
  70.   borders another clean chunk. Thus, clean chunks never need to be
  71.   scanned during consolidation.
  72.  
  73. * Algorithms
  74.  
  75.   Malloc:
  76.  
  77.     This is a very heavily disguised first-fit algorithm.
  78.     Most of the heuristics are designed to maximize the likelihood
  79.     that a usable chunk will most often be found very quickly,
  80.     while still minimizing fragmentation and overhead.
  81.  
  82.     The allocation strategy has several phases:
  83.  
  84.       0. Convert the request size into a usable form. This currently
  85.          means to add 8 bytes overhead plus possibly more to obtain
  86.          8-byte alignment. Call this size `nb'.
  87.  
  88.       1. Check if the last returned (free()'d) or preallocated chunk
  89.          is of the exact size nb. If so, use it.  `Exact' means no
  90.          more than MINSIZE (currently 16) bytes larger than nb. This
  91.          cannot be reduced, since a chunk with size < MINSIZE cannot
  92.          be created to hold the remainder.
  93.  
  94.          This check need not fire very often to be effective.  It
  95.          reduces overhead for sequences of requests for the same
  96.          preallocated size to a dead minimum.
  97.  
  98.       2. Look for a dirty chunk of exact size in the bin associated
  99.          with nb.  `Dirty' chunks are those that have never been
  100.          consolidated.  Besides the fact that they, but not clean
  101.          chunks require scanning for consolidation, these chunks are
  102.          of sizes likely to be useful because they have been
  103.          previously requested and then freed by the user program.
  104.  
  105.          Dirty chunks of bad sizes (even if too big) are never used
  106.          without consolidation. Among other things, this maintains the
  107.          invariant that split chunks (see below) are ALWAYS clean.
  108.  
  109.          2a If there are dirty chunks, but none of the right size,
  110.              consolidate them all, as well as any returned chunks
  111.              (i.e., the ones from step 3). This is all a heuristic for
  112.              detecting and dealing with excess fragmentation and
  113.              random traversals through memory that degrade
  114.              performance especially when the user program is running
  115.              out of physical memory.
  116.  
  117.       3. Pull other requests off the returned chunk list, using one if
  118.          it is of exact size, else distributing into the appropriate
  119.          bins.
  120.  
  121.       4. Try to use the last chunk remaindered during a previous
  122.          malloc. (The ptr to this chunk is kept in var last_remainder,
  123.          to make it easy to find and to avoid useless re-binning
  124.          during repeated splits.  The code surrounding it is fairly
  125.          delicate. This chunk must be pulled out and placed in a bin
  126.          prior to any consolidation, to avoid having other pointers
  127.          point into the middle of it, or try to unlink it.) If
  128.          it is usable, proceed to step 9.
  129.  
  130.       5. Scan through clean chunks in the bin, choosing any of size >=
  131.          nb. Split later (step 9) if necessary below.  (Unlike in step
  132.          2, it is good to split here, because it creates a chunk of a
  133.          known-to-be-useful size out of a fragment that happened to be
  134.          close in size.)
  135.  
  136.       6. Scan through the clean lists of all larger bins, selecting
  137.          any chunk at all. (It will surely be big enough since it is
  138.          in a bigger bin.)  The scan goes upward from small bins to
  139.          large.  It would be faster downward, but could lead to excess
  140.          fragmentation. If successful, proceed to step 9.
  141.  
  142.       7. Consolidate chunks in other dirty bins until a large enough
  143.          chunk is created. Break out to step 9 when one is found.
  144.  
  145.          Bins are selected for consolidation in a circular fashion
  146.          spanning across malloc calls. This very crudely approximates
  147.          LRU scanning -- it is an effective enough approximation for
  148.          these purposes.
  149.  
  150.       8. Get space from the system using sbrk.
  151.  
  152.          Memory is gathered from the system (via sbrk) in a way that
  153.          allows chunks obtained across different sbrk calls to be
  154.          consolidated, but does not require contiguous memory. Thus,
  155.          it should be safe to intersperse mallocs with other sbrk
  156.          calls.
  157.  
  158.       9. If the selected chunk is too big, then:
  159.  
  160.          9a If this is the second split request for nb bytes in a row,
  161.              use this chunk to preallocate up to MAX_PREALLOCS
  162.              additional chunks of size nb and place them on the
  163.              returned chunk list.  (Placing them here rather than in
  164.              bins speeds up the most common case where the user
  165.              program requests an uninterrupted series of identically
  166.              sized chunks. If this is not true, the chunks will be
  167.              binned i