malloc.c

俄罗斯高人Mamaich的Pocket gcc编译器（运行在PocketPC上）的全部源代码。

        become less than MINSIZE bytes long, it is replenished via
        malloc_extend_top.)

     2. Chunks allocated via mmap, which have the second-lowest-order
        bit (IS_MMAPPED) set in their size fields.  Because they are
        never merged or traversed from any other chunk, they have no
        foot size or inuse information.

    Available chunks are kept in any of several places (all declared below):

    * `av': An array of chunks serving as bin headers for consolidated
       chunks. Each bin is doubly linked.  The bins are approximately
       proportionally (log) spaced.  There are a lot of these bins
       (128). This may look excessive, but works very well in
       practice.  All procedures maintain the invariant that no
       consolidated chunk physically borders another one. Chunks in
       bins are kept in size order, with ties going to the
       approximately least recently used chunk.

       The chunks in each bin are maintained in decreasing sorted order by
       size.  This is irrelevant for the small bins, which all contain
       the same-sized chunks, but facilitates best-fit allocation for
       larger chunks. (These lists are just sequential. Keeping them in
       order almost never requires enough traversal to warrant using
       fancier ordered data structures.)  Chunks of the same size are
       linked with the most recently freed at the front, and allocations
       are taken from the back.  This results in LRU or FIFO allocation
       order, which tends to give each chunk an equal opportunity to be
       consolidated with adjacent freed chunks, resulting in larger free
       chunks and less fragmentation.

    * `top': The top-most available chunk (i.e., the one bordering the
       end of available memory) is treated specially. It is never
       included in any bin, is used only if no other chunk is
       available, and is released back to the system if it is very
       large (see M_TRIM_THRESHOLD).

    * `last_remainder': A bin holding only the remainder of the
       most recently split (non-top) chunk. This bin is checked
       before other non-fitting chunks, so as to provide better
       locality for runs of sequentially allocated chunks.

    *  Implicitly, through the host system's memory mapping tables.
       If supported, requests greater than a threshold are usually
       serviced via calls to mmap, and then later released via munmap.

*/

/*
   Bins

    The bins are an array of pairs of pointers serving as the
    heads of (initially empty) doubly-linked lists of chunks, laid out
    in a way so that each pair can be treated as if it were in a
    malloc_chunk. (This way, the fd/bk offsets for linking bin heads
    and chunks are the same).

    Bins for sizes < 512 bytes contain chunks of all the same size, spaced
    8 bytes apart. Larger bins are approximately logarithmically
    spaced. (See the table below.)

    Bin layout:

    64 bins of size       8
    32 bins of size      64
    16 bins of size     512
     8 bins of size    4096
     4 bins of size   32768
     2 bins of size  262144
     1 bin  of size what's left

    There is actually a little bit of slop in the numbers in bin_index
    for the sake of speed. This makes no difference elsewhere.

    The special chunks `top' and `last_remainder' get their own bins,
    (this is implemented via yet more trickery with the av array),
    although `top' is never properly linked to its bin since it is
    always handled specially.

*/

#define NAV             128   /* number of bins */

typedef struct malloc_chunk* mbinptr;

/* An arena is a configuration of malloc_chunks together with an array
   of bins.  With multiple threads, it must be locked via a mutex
   before changing its data structures.  One or more `heaps' are
   associated with each arena, except for the main_arena, which is
   associated only with the `main heap', i.e.  the conventional free
   store obtained with calls to MORECORE() (usually sbrk).  The `av'
   array is never mentioned directly in the code, but instead used via
   bin access macros. */

typedef struct _arena {
  mbinptr av[2*NAV + 2];
  struct _arena *next;
  size_t size;
#if THREAD_STATS
  long stat_lock_direct, stat_lock_loop, stat_lock_wait;
#endif
  mutex_t mutex;
} arena;


/* A heap is a single contiguous memory region holding (coalesceable)
   malloc_chunks.  It is allocated with mmap() and always starts at an
   address aligned to HEAP_MAX_SIZE.  Not used unless compiling with
   USE_ARENAS. */

typedef struct _heap_info {
  arena *ar_ptr; /* Arena for this heap. */
  struct _heap_info *prev; /* Previous heap. */
  size_t size;   /* Current size in bytes. */
  size_t pad;    /* Make sure the following data is properly aligned. */
} heap_info;


/*
  Static functions (forward declarations)
*/

#if __STD_C

static void      chunk_free(arena *ar_ptr, mchunkptr p) internal_function;
static mchunkptr chunk_alloc(arena *ar_ptr, INTERNAL_SIZE_T size)
     internal_function;
static mchunkptr chunk_realloc(arena *ar_ptr, mchunkptr oldp,
                               INTERNAL_SIZE_T oldsize, INTERNAL_SIZE_T nb)
     internal_function;
static mchunkptr chunk_align(arena *ar_ptr, INTERNAL_SIZE_T nb,
                             size_t alignment) internal_function;
static int       main_trim(size_t pad) internal_function;
#if USE_ARENAS
static int       heap_trim(heap_info *heap, size_t pad) internal_function;
#endif
#if defined _LIBC || defined MALLOC_HOOKS
static Void_t*   malloc_check(size_t sz, const Void_t *caller);
static void      free_check(Void_t* mem, const Void_t *caller);
static Void_t*   realloc_check(Void_t* oldmem, size_t bytes,
			       const Void_t *caller);
static Void_t*   memalign_check(size_t alignment, size_t bytes,
				const Void_t *caller);
#ifndef NO_THREADS
static Void_t*   malloc_starter(size_t sz, const Void_t *caller);
static void      free_starter(Void_t* mem, const Void_t *caller);
static Void_t*   malloc_atfork(size_t sz, const Void_t *caller);
static void      free_atfork(Void_t* mem, const Void_t *caller);
#endif
#endif

#else

static void      chunk_free();
static mchunkptr chunk_alloc();
static mchunkptr chunk_realloc();
static mchunkptr chunk_align();
static int       main_trim();
#if USE_ARENAS
static int       heap_trim();
#endif
#if defined _LIBC || defined MALLOC_HOOKS
static Void_t*   malloc_check();
static void      free_check();
static Void_t*   realloc_check();
static Void_t*   memalign_check();
#ifndef NO_THREADS
static Void_t*   malloc_starter();
static void      free_starter();
static Void_t*   malloc_atfork();
static void      free_atfork();
#endif
#endif

#endif



/* sizes, alignments */

#define SIZE_SZ                (sizeof(INTERNAL_SIZE_T))
/* Allow the default to be overwritten on the compiler command line.  */
#ifndef MALLOC_ALIGNMENT
# define MALLOC_ALIGNMENT      (SIZE_SZ + SIZE_SZ)
#endif
#define MALLOC_ALIGN_MASK      (MALLOC_ALIGNMENT - 1)
#define MINSIZE                (sizeof(struct malloc_chunk))

/* conversion from malloc headers to user pointers, and back */

#define chunk2mem(p) ((Void_t*)((char*)(p) + 2*SIZE_SZ))
#define mem2chunk(mem) chunk_at_offset((mem), -2*SIZE_SZ)

/* pad request bytes into a usable size, return non-zero on overflow */

#define request2size(req, nb) \
 ((nb = (req) + (SIZE_SZ + MALLOC_ALIGN_MASK)),\
  ((long)nb <= 0 || nb < (INTERNAL_SIZE_T) (req) \
   ? (__set_errno (ENOMEM), 1) \
   : ((nb < (MINSIZE + MALLOC_ALIGN_MASK) \
	   ? (nb = MINSIZE) : (nb &= ~MALLOC_ALIGN_MASK)), 0)))

/* Check if m has acceptable alignment */

#define aligned_OK(m)    (((unsigned long)((m)) & (MALLOC_ALIGN_MASK)) == 0)




/*
  Physical chunk operations
*/


/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */

#define PREV_INUSE 0x1UL

/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */

#define IS_MMAPPED 0x2UL

/* Bits to mask off when extracting size */

#define SIZE_BITS (PREV_INUSE|IS_MMAPPED)


/* Ptr to next physical malloc_chunk. */

#define next_chunk(p) chunk_at_offset((p), (p)->size & ~PREV_INUSE)

/* Ptr to previous physical malloc_chunk */

#define prev_chunk(p) chunk_at_offset((p), -(p)->prev_size)


/* Treat space at ptr + offset as a chunk */

#define chunk_at_offset(p, s)  BOUNDED_1((mchunkptr)(((char*)(p)) + (s)))




/*
  Dealing with use bits
*/

/* extract p's inuse bit */

#define inuse(p) (next_chunk(p)->size & PREV_INUSE)

/* extract inuse bit of previous chunk */

#define prev_inuse(p)  ((p)->size & PREV_INUSE)

/* check for mmap()'ed chunk */

#define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)

/* set/clear chunk as in use without otherwise disturbing */

#define set_inuse(p) (next_chunk(p)->size |= PREV_INUSE)

#define clear_inuse(p) (next_chunk(p)->size &= ~PREV_INUSE)

/* check/set/clear inuse bits in known places */

#define inuse_bit_at_offset(p, s) \
  (chunk_at_offset((p), (s))->size & PREV_INUSE)

#define set_inuse_bit_at_offset(p, s) \
  (chunk_at_offset((p), (s))->size |= PREV_INUSE)

#define clear_inuse_bit_at_offset(p, s) \
  (chunk_at_offset((p), (s))->size &= ~(PREV_INUSE))




/*
  Dealing with size fields
*/

/* Get size, ignoring use bits */

#define chunksize(p)          ((p)->size & ~(SIZE_BITS))

/* Set size at head, without disturbing its use bit */

#define set_head_size(p, s)   ((p)->size = (((p)->size & PREV_INUSE) | (s)))

/* Set size/use ignoring previous bits in header */

#define set_head(p, s)        ((p)->size = (s))

/* Set size at footer (only when chunk is not in use) */

#define set_foot(p, s)   (chunk_at_offset(p, s)->prev_size = (s))





/* access macros */

#define bin_at(a, i)   BOUNDED_1(_bin_at(a, i))
#define _bin_at(a, i)  ((mbinptr)((char*)&(((a)->av)[2*(i)+2]) - 2*SIZE_SZ))
#define init_bin(a, i) ((a)->av[2*(i)+2] = (a)->av[2*(i)+3] = bin_at((a), (i)))
#define next_bin(b)    ((mbinptr)((char*)(b) + 2 * sizeof(((arena*)0)->av[0])))
#define prev_bin(b)    ((mbinptr)((char*)(b) - 2 * sizeof(((arena*)0)->av[0])))

/*
   The first 2 bins are never indexed. The corresponding av cells are instead
   used for bookkeeping. This is not to save space, but to simplify
   indexing, maintain locality, and avoid some initialization tests.
*/

#define binblocks(a)      (bin_at(a,0)->size)/* bitvector of nonempty blocks */
#define top(a)            (bin_at(a,0)->fd)  /* The topmost chunk */
#define last_remainder(a) (bin_at(a,1))      /* remainder from last split */

/*
   Because top initially points to its own bin with initial
   zero size, thus forcing extension on the first malloc request,
   we avoid having any special code in malloc to check whether
   it even exists yet. But we still need to in malloc_extend_top.
*/

#define initial_top(a)    ((mchunkptr)bin_at(a, 0))



/* field-extraction macros */

#define first(b) ((b)->fd)
#define last(b)  ((b)->bk)

/*
  Indexing into bins
*/

#define bin_index(sz)                                                         \
(((((unsigned long)(sz)) >> 9) ==    0) ?       (((unsigned long)(sz)) >>  3):\
 ((((unsigned long)(sz)) >> 9) <=    4) ?  56 + (((unsigned long)(sz)) >>  6):\
 ((((unsigned long)(sz)) >> 9) <=   20) ?  91 + (((unsigned long)(sz)) >>  9):\
 ((((unsigned long)(sz)) >> 9) <=   84) ? 110 + (((unsigned long)(sz)) >> 12):\
 ((((unsigned long)(sz)) >> 9) <=  340) ? 119 + (((unsigned long)(sz)) >> 15):\
 ((((unsigned long)(sz)) >> 9) <= 1364) ? 124 + (((unsigned long)(sz)) >> 18):\
                                          126)
/*
  bins for chunks < 512 are all spaced 8 bytes apart, and hold
  identically sized chunks. This is exploited in malloc.
*/

#define MAX_SMALLBIN         63
#define MAX_SMALLBIN_SIZE   512
#define SMALLBIN_WIDTH        8

#define smallbin_index(sz)  (((unsigned long)(sz)) >> 3)

/*
   Requests are `small' if both the corresponding and the next bin are small
*/

#define is_small_request(nb) ((nb) < MAX_SMALLBIN_SIZE - SMALLBIN_WIDTH)



/*
    To help compensate for the large number of bins, a one-level index
    structure is used for bin-by-bin searching.  `binblocks' is a
    one-word bitvector recording whether groups of BINBLOCKWIDTH bins
    have any (possibly) non-empty bins, so they can be skipped over
    all at once during during traversals. The bits are NOT always
    cleared as soon as all bins in a block are empty, but instead only
    when all are noticed to be empty during traversal in malloc.
*/

#define BINBLOCKWIDTH     4   /* bins per block */