malloc.c

早期freebsd实现

/* 
Copyright (C) 1989 Free Software Foundation
    written by Doug Lea ([e-mail])

This file is part of the GNU C++ Library.  This library is free
software; you can redistribute it and/or modify it under the terms of
the GNU Library General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your
option) any later version.  This library is distributed in the hope
that it will be useful, but WITHOUT ANY WARRANTY; without even the
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE.  See the GNU Library General Public License for more details.
You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free Software
Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
*/



#ifndef NO_LIBGXX_MALLOC   /* ignore whole file otherwise */

/* compile with -DMALLOC_STATS to collect statistics */
/* collecting statistics slows down malloc by at least 15% */

#ifdef MALLOC_STATS
#define UPDATE_STATS(ARGS) {ARGS;}
#else
#define UPDATE_STATS(ARGS)
#endif

/* History


   Tue Jan 16 04:54:27 1990  Doug Lea  (dl at g.oswego.edu)

     version 1 released in libg++

   Sun Jan 21 05:52:47 1990  Doug Lea  (dl at g.oswego.edu)

     bins are now own struct for, sanity.

     new victim search strategy: scan up and consolidate.
     Both faster and less fragmentation.

     refined when to scan bins for consolidation, via consollink, etc.

     realloc: always try to expand chunk, avoiding some fragmentation.

     changed a few inlines into macros

     hardwired SBRK_UNIT to 4096 for uniformity across systems

   Tue Mar 20 14:18:23 1990  Doug Lea  (dl at g.oswego.edu)

     calloc and cfree now correctly parameterized.

   Sun Apr  1 10:00:48 1990  Doug Lea  (dl at g.oswego.edu)

     added memalign and valloc.

   Sun Jun 24 05:46:48 1990  Doug Lea  (dl at g.oswego.edu)

     #include gepagesize.h only ifndef sun
     cache pagesize after first call

   Wed Jul 25 08:35:19 1990  Doug Lea  (dl at g.oswego.edu)

     No longer rely on a `designated victim':

       1. It sometimes caused splits of large chunks
          when smaller ones would do, leading to
          bad worst-case fragmentation.

       2. Scanning through the av array fast anyway,
          so the overhead isn't worth it.

     To compensate, several other minor changes:

       1. Unusable chunks are checked for consolidation during
          searches inside bins, better distributing chunks
          across bins.

       2. Chunks are returned when found in malloc_find_space,
           rather than finishing cleaning everything up, to
           avoid wasted iterations due to (1).

   Sun Dec 15 08:50:37 1991  Doug Lea  (dl at g.oswego.edu)

       unsigned int => size_t

*/

/* 
  A version of malloc/free/realloc tuned for C++ applications.

  Here's what you probably want to know first:

  In various tests, this appears to be about as fast as,
  and usually substantially less memory-wasteful than BSD/GNUemacs malloc.

  Generally, it is slower (by perhaps 20%) than bsd-style malloc
  only when bsd malloc would waste a great deal of space in 
  fragmented blocks, which this malloc recovers; or when, by
  chance or design, nearly all requests are near the bsd malloc
  power-of-2 allocation bin boundaries, and as many chunks are
  used as are allocated. 

  It uses more space than bsd malloc only when, again by chance
  or design, only bsdmalloc bin-sized requests are malloced, or when
  little dynamic space is malloced, since this malloc may grab larger
  chunks from the system at a time than bsd.

  In other words, this malloc seems generally superior to bsd
  except perhaps for programs that are specially tuned to
  deal with bsdmalloc's characteristics. But even here, the
  performance differences are slight.

 
  This malloc, like any other, is a compromised design. 


  Chunks of memory are maintained using a `boundary tag' method as
  described in e.g., Knuth or Standish.  This means that the size of
  the chunk is stored both in the front of the chunk and at the end.
  This makes consolidating fragmented chunks into bigger chunks very fast.
  The size field is also used to hold bits representing whether a
  chunk is free or in use.

  Malloced chunks have space overhead of 8 bytes: The preceding
  and trailing size fields. When they are freed, the list pointer
  fields are also needed.

  Available chunks are kept in doubly linked lists. The lists are
  maintained in an array of bins using a power-of-two method, except
  that instead of 32 bins (one for each 1 << i), there are 128: each
  power of two is split in quarters. The use of very fine bin sizes 
  closely approximates the use of one bin per actually used size,
  without necessitating the overhead of locating such bins. It is
  especially desirable in common C++ applications where large numbers
  of identically-sized blocks are malloced/freed in some dynamic
  manner, and then later are all freed. The finer bin sizes make
  finding blocks fast, with little wasted overallocation. The
  consolidation methods ensure that once the collection of blocks is
  no longer useful, fragments are gathered into bigger chunks awaiting new
  roles.

  The bins av[i] serve as heads of the lists. Bins contain a dummy
  header for the chunk lists, and a `dirty' field used to indicate
  whether the list may need to be scanned for consolidation.

  On allocation, the bin corresponding to the request size is
  scanned, and if there is a chunk with size >= requested, it
  is split, if too big, and used. Chunks on the list which are
  too small are examined for consolidation during this traversal.

  If no chunk exists in the list bigger bins are scanned in search of
  a victim.

  If no victim can be found, then smaller bins are examined for
  consolidation in order to construct a victim.

  Finally, if consolidation fails to come up with a usable chunk,
  more space is obtained from the system.

  After a split, the remainder is placed on
  the back of the appropriate bin list. (All freed chunks are placed
  on fronts of lists. All remaindered or consolidated chunks are
  placed on the rear. Correspondingly, searching within a bin
  starts at the front, but finding victims is from the back. All
  of this approximates  the  effect of having 2 kinds of lists per 
  bin: returned chunks vs unallocated chunks, but without the overhead 
  of maintaining 2 lists.)

  Deallocation (free) consists only of placing the chunk on
  a list.

  Reallocation proceeds in the usual way. If a chunk can be extended,
  it is, else a malloc-copy-free sequence is taken.

  memalign requests more than enough space from malloc, finds a
  spot within that chunk that meets the alignment request, and
  then possibly frees the leading and trailing space. Overreliance
  on memalign is a sure way to fragment space.


  Some other implementation matters:

  8 byte alignment is currently hardwired into the design. Calling
  memalign will return a chunk that is both 8-byte aligned, and
  meets the requested alignment.

  The basic overhead of a used chunk is 8 bytes: 4 at the front and
  4 at the end.

  When a chunk is free, 8 additional bytes are needed for free list
  pointers. Thus, the minimum allocatable size is 16 bytes.

  The existence of front and back overhead permits some reasonably
  effective fence-bashing checks: The front and back fields must
  be identical. This is checked only within free() and realloc().
  The checks are fast enough to be made non-optional.

  The overwriting of parts of freed memory with the freelist pointers
  can also be very effective (albeit in an annoying way) in helping 
  users track down dangling pointers.

  User overwriting of freed space will often result in crashes
  within malloc or free.
  
  These routines are also tuned to C++ in that free(0) is a noop and
  a failed malloc automatically calls (*new_handler)(). 

  malloc(0) returns a pointer to something of the minimum allocatable size.

  Additional memory is gathered from the system (via sbrk) in a
  way that allows chunks obtained across different sbrk calls to
  be consolidated, but does not require contiguous memory: Thus,
  it should be safe to intersperse mallocs with other sbrk calls.

  This malloc is NOT designed to work in multiprocessing applications.
  No semaphores or other concurrency control are provided to ensure
  that multiple malloc or free calls don't run at the same time,
  which could be disasterous.

  VERY heavy use of inlines is made, for clarity. If this malloc
  is ported via a compiler without inlining capabilities, all
  inlines should be transformed into macros -- making them non-inline
  makes malloc at least twice as slow.


*/


/* preliminaries */

#include <stddef.h>   /* for size_t */

#ifdef __cplusplus
#include <stdio.h>
#else
#include "//usr/include/stdio.h"  /* needed for error reporting */
#endif

#ifdef __cplusplus
extern "C" {
#endif

#ifdef _G_SYSV
extern void*     memset(void*, int, int);
extern void*     memcpy(void*,  const void*, int);
inline void      bzero(void* s, int l) { memset(s, 0, l); }
#else
extern void      bzero(void*, size_t      );
#endif

extern void      bcopy(void*, void*, size_t      );

extern void*     sbrk(size_t      );


#ifdef __GNUC__
extern volatile void abort();
#else
extern void abort();
#endif

#ifdef __cplusplus
};  /* end of extern "C" */
#endif


/* A good multiple to call sbrk with */

#define SBRK_UNIT 4096 



/* how to die on detected error */

#ifdef __GNUC__
static volatile void malloc_user_error()
#else
static void malloc_user_error()
#endif
{
  fputs("malloc/free/realloc: clobbered space detected\n", stderr); abort();
}



/*  Basic overhead for each malloc'ed chunk */


struct malloc_chunk
{
  size_t               size;     /* Size in bytes, including overhead. */
                                 /* Or'ed with INUSE if in use. */

  struct malloc_chunk* fd;       /* double links -- used only if free. */
  struct malloc_chunk* bk;

};

typedef struct malloc_chunk* mchunkptr;

struct malloc_bin
{
  struct malloc_chunk hd;        /* dummy list header */
  size_t              dirty;     /* True if maybe consolidatable */
                                 /* Wasting a word here makes */
                                 /* sizeof(bin) a power of 2, */
                                 /* which makes size2bin() faster */
};

typedef struct malloc_bin* mbinptr;


/*  sizes, alignments */


#define SIZE_SZ                   (sizeof(size_t      ))
#define MALLOC_MIN_OVERHEAD       (SIZE_SZ + SIZE_SZ)
#define MALLOC_ALIGN_MASK         (MALLOC_MIN_OVERHEAD - 1)

#define MINSIZE (sizeof(struct malloc_chunk) + SIZE_SZ) /* MUST == 16! */


/* pad request bytes into a usable size */

static inline size_t       request2size(size_t       request)
{
  return  (request == 0) ?  MINSIZE : 
    ((request + MALLOC_MIN_OVERHEAD + MALLOC_ALIGN_MASK) 
      & ~(MALLOC_ALIGN_MASK));
}


static inline int aligned_OK(void* m)  
{
  return ((size_t      )(m) & (MALLOC_ALIGN_MASK)) == 0;
}


/* size field or'd with INUSE when in use */
#define INUSE  0x1



/* the bins, initialized to have null double linked lists */

#define MAXBIN 120   /* 1 more than needed for 32 bit addresses */

#define FIRSTBIN (&(av[0])) 

static struct malloc_bin  av[MAXBIN] = 
{
  { { 0, &(av[0].hd),  &(av[0].hd) }, 0 },
  { { 0, &(av[1].hd),  &(av[1].hd) }, 0 },
  { { 0, &(av[2].hd),  &(av[2].hd) }, 0 },
  { { 0, &(av[3].hd),  &(av[3].hd) }, 0 },
  { { 0, &(av[4].hd),  &(av[4].hd) }, 0 },
  { { 0, &(av[5].hd),  &(av[5].hd) }, 0 },
  { { 0, &(av[6].hd),  &(av[6].hd) }, 0 },
  { { 0, &(av[7].hd),  &(av[7].hd) }, 0 },
  { { 0, &(av[8].hd),  &(av[8].hd) }, 0 },
  { { 0, &(av[9].hd),  &(av[9].hd) }, 0 },

  { { 0, &(av[10].hd), &(av[10].hd) }, 0 },
  { { 0, &(av[11].hd), &(av[11].hd) }, 0 },
  { { 0, &(av[12].hd), &(av[12].hd) }, 0 },
  { { 0, &(av[13].hd), &(av[13].hd) }, 0 },
  { { 0, &(av[14].hd), &(av[14].hd) }, 0 },
  { { 0, &(av[15].hd), &(av[15].hd) }, 0 },
  { { 0, &(av[16].hd), &(av[16].hd) }, 0 },
  { { 0, &(av[17].hd), &(av[17].hd) }, 0 },
  { { 0, &(av[18].hd), &(av[18].hd) }, 0 },
  { { 0, &(av[19].hd), &(av[19].hd) }, 0 },

  { { 0, &(av[20].hd), &(av[20].hd) }, 0 },
  { { 0, &(av[21].hd), &(av[21].hd) }, 0 },
  { { 0, &(av[22].hd), &(av[22].hd) }, 0 },
  { { 0, &(av[23].hd), &(av[23].hd) }, 0 },
  { { 0, &(av[24].hd), &(av[24].hd) }, 0 },
  { { 0, &(av[25].hd), &(av[25].hd) }, 0 },
  { { 0, &(av[26].hd), &(av[26].hd) }, 0 },
  { { 0, &(av[27].hd), &(av[27].hd) }, 0 },
  { { 0, &(av[28].hd), &(av[28].hd) }, 0 },
  { { 0, &(av[29].hd), &(av[29].hd) }, 0 },

  { { 0, &(av[30].hd), &(av[30].hd) }, 0 },
  { { 0, &(av[31].hd), &(av[31].hd) }, 0 },
  { { 0, &(av[32].hd), &(av[32].hd) }, 0 },
  { { 0, &(av[33].hd), &(av[33].hd) }, 0 },
  { { 0, &(av[34].hd), &(av[34].hd) }, 0 },
  { { 0, &(av[35].hd), &(av[35].hd) }, 0 },
  { { 0, &(av[36].hd), &(av[36].hd) }, 0 },
  { { 0, &(av[37].hd), &(av[37].hd) }, 0 },
  { { 0, &(av[38].hd), &(av[38].hd) }, 0 },
  { { 0, &(av[39].hd), &(av[39].hd) }, 0 },

  { { 0, &(av[40].hd), &(av[40].hd) }, 0 },
  { { 0, &(av[41].hd), &(av[41].hd) }, 0 },
  { { 0, &(av[42].hd), &(av[42].hd) }, 0 },
  { { 0, &(av[43].hd), &(av[43].hd) }, 0 },
  { { 0, &(av[44].hd), &(av[44].hd) }, 0 },
  { { 0, &(av[45].hd), &(av[45].hd) }, 0 },
  { { 0, &(av[46].hd), &(av[46].hd) }, 0 },
  { { 0, &(av[47].hd), &(av[47].hd) }, 0 },
  { { 0, &(av[48].hd), &(av[48].hd) }, 0 },
  { { 0, &(av[49].hd), &(av[49].hd) }, 0 },

  { { 0, &(av[50].hd), &(av[50].hd) }, 0 },
  { { 0, &(av[51].hd), &(av[51].hd) }, 0 },
  { { 0, &(av[52].hd), &(av[52].hd) }, 0 },
  { { 0, &(av[53].hd), &(av[53].hd) }, 0 },
  { { 0, &(av[54].hd), &(av[54].hd) }, 0 },
  { { 0, &(av[55].hd), &(av[55].hd) }, 0 },