malloc(3)のメモリ管理構造

struct malloc_state {
/* Serialize access.  */
   mutex_t mutex;
   /* Statistics for locking.  Only used if THREAD_STATS is defined.  */
   long stat_lock_direct, stat_lock_loop, stat_lock_wait;
   long pad0_[1]; /* try to give the mutex its own cacheline */
   /* The maximum chunk size to be eligible for fastbin */
   INTERNAL_SIZE_T  max_fast;   /* low 2 bits used as flags */
   /* Fastbins */
   mfastbinptr      fastbins[NFASTBINS];
   /* Base of the topmost chunk -- not otherwise kept in a bin */
   mchunkptr        top;
   /* The remainder from the most recent split of a small request */
   mchunkptr        last_remainder;
   /* Normal bins packed as described above */
   mchunkptr        bins[NBINS * 2];
   /* Bitmap of bins */
   unsigned int     binmap[BINMAPSIZE];
   /* Linked list */
   struct malloc_state *next;
   /* Memory allocated from the system in this arena.  */
   INTERNAL_SIZE_T system_mem;
   INTERNAL_SIZE_T max_system_mem;
 };
 struct malloc_par {
   /* Tunable parameters */
   unsigned long    trim_threshold;
   INTERNAL_SIZE_T  top_pad;
   INTERNAL_SIZE_T  mmap_threshold;
   /* Memory map support */
   int              n_mmaps;
   int              n_mmaps_max;
   int              max_n_mmaps;
   /* Cache malloc_getpagesize */
   unsigned int     pagesize;
   /* Statistics */
   INTERNAL_SIZE_T  mmapped_mem;
   /*INTERNAL_SIZE_T  sbrked_mem;*/
   /*INTERNAL_SIZE_T  max_sbrked_mem;*/
   INTERNAL_SIZE_T  max_mmapped_mem;
   INTERNAL_SIZE_T  max_total_mem; /* only kept for NO_THREADS */
   /* First address handed out by MORECORE/sbrk.  */
   char*            sbrk_base;
 };

/* offset 2 to use otherwise unindexable first 2 bins */
#define fastbin_index(sz)        ((((unsigned int)(sz)) >> 3) - 2)
/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE     80
#define NFASTBINS  (fastbin_index(request2size(MAX_FAST_SIZE))+1)

#define largebin_index(sz)                                                   
(((((unsigned long)(sz)) >>  6) <= 32)?  56 + (((unsigned long)(sz)) >>  6): 
 ((((unsigned long)(sz)) >>  9) <= 20)?  91 + (((unsigned long)(sz)) >>  9): 
 ((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): 
 ((((unsigned long)(sz)) >> 15) <=  4)? 119 + (((unsigned long)(sz)) >> 15): 
 ((((unsigned long)(sz)) >> 18) <=  2)? 124 + (((unsigned long)(sz)) >> 18): 
                                        126)

struct malloc_chunk {
  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;
};

Void_t*
_int_malloc(mstate av, size_t bytes)
{
  INTERNAL_SIZE_T nb;               /* normalized request size */
  unsigned int    idx;              /* associated bin index */
  mbinptr         bin;              /* associated bin */
  mfastbinptr*    fb;               /* associated fastbin */

  mchunkptr       victim;           /* inspected/selected chunk */
  INTERNAL_SIZE_T size;             /* its size */
  int             victim_index;     /* its bin index */

  mchunkptr       remainder;        /* remainder from a split */
  unsigned long   remainder_size;   /* its size */

  unsigned int    block;            /* bit map traverser */
  unsigned int    bit;              /* bit map traverser */
  unsigned int    map;              /* current word of binmap */

  mchunkptr       fwd;              /* misc temp for linking */
  mchunkptr       bck;              /* misc temp for linking */

  /*
    Convert request size to internal form by adding SIZE_SZ bytes
    overhead plus possibly more to obtain necessary alignment and/or
    to obtain a size of at least MINSIZE, the smallest allocatable
    size. Also, checked_request2size traps (returning 0) request sizes
    that are so large that they wrap around zero when padded and
    aligned.
  */

  checked_request2size(bytes, nb);                                       ---- 1-1

  /*
    If the size qualifies as a fastbin, first check corresponding bin.
    This code is safe to execute even if av is not yet initialized, so we
    can try it without checking, which saves some time on this fast path.
  */

  if ((unsigned long)(nb) <= (unsigned long)(av->max_fast)) {            ---- 1-2
    fb = &(av->fastbins[(fastbin_index(nb))]);
    if ( (victim = *fb) != 0) {
      *fb = victim->fd;
      check_remalloced_chunk(av, victim, nb);
      return chunk2mem(victim);
    }
  }

  /*
    If a small request, check regular bin. Since these "smallbins"
    hold one size each, no searching within bins is necessary.
    (For a large request, we need to wait until unsorted chunks are
    processed to find best fit. But for small ones, fits are exact
    anyway, so we can check now, which is faster.)
  */

  if (in_smallbin_range(nb)) {                                           ---- 1-3
    idx = smallbin_index(nb);
    bin = bin_at(av,idx);

    if ( (victim = last(bin)) != bin) {
      if (victim == 0) /* initialization check */
        malloc_consolidate(av);
      else {                                                             ---- 1-4
        bck = victim->bk;
        set_inuse_bit_at_offset(victim, nb);
        bin->bk = bck;
        bck->fd = bin;

        if (av != &main_arena)
          victim->size |= NON_MAIN_ARENA;
        check_malloced_chunk(av, victim, nb);
        return chunk2mem(victim);
      }
    }
  }

  /*
     If this is a large request, consolidate fastbins before continuing.
     While it might look excessive to kill all fastbins before
     even seeing if there is space available, this avoids
     fragmentation problems normally associated with fastbins.
     Also, in practice, programs tend to have runs of either small or
     large requests, but less often mixtures, so consolidation is not
     invoked all that often in most programs. And the programs that
     it is called frequently in otherwise tend to fragment.
  */

  else {                                                                 ---- 1-5
    idx = largebin_index(nb);
    if (have_fastchunks(av))
      malloc_consolidate(av);
  }

  /*
    Process recently freed or remaindered chunks, taking one only if
    it is exact fit, or, if this a small request, the chunk is remainder from
    the most recent non-exact fit. Place other traversed chunks in
    bins. Note that this step is the only place in any routine where
    chunks are placed in bins.

    The outer loop here is needed because we might not realize until
    near the end of malloc that we should have consolidated, so must
    do so and retry. This happens at most once, and only when we would
    otherwise need to expand memory to service a "small" request.
  */

  for(;;) {                                                              ---- 1-6

    while ( (victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {
      bck = victim->bk;
      size = chunksize(victim);

      /*
         If a small request, try to use last remainder if it is the
         only chunk in unsorted bin. This helps promote locality for
         runs of consecutive small requests. This is the only
         exception to best-fit, and applies only when there is
         no exact fit for a small chunk.
      */

      if (in_smallbin_range(nb) &&                                       ---- 1-7
          bck == unsorted_chunks(av) &&
          victim == av->last_remainder &&
          (unsigned long)(size) > (unsigned long)(nb + MINSIZE)) {

        /* split and reattach remainder */
        remainder_size = size - nb;
        remainder = chunk_at_offset(victim, nb);
        unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
        av->last_remainder = remainder;
        remainder->bk = remainder->fd = unsorted_chunks(av);

        set_head(victim, nb | PREV_INUSE |
                 (av != &main_arena ? NON_MAIN_ARENA : 0));
        set_head(remainder, remainder_size | PREV_INUSE);
        set_foot(remainder, remainder_size);

        check_malloced_chunk(av, victim, nb);
        return chunk2mem(victim);
      }

      /* remove from unsorted list */
      unsorted_chunks(av)->bk = bck;
      bck->fd = unsorted_chunks(av);

      /* Take now instead of binning if exact fit */

      if (size == nb) {                                                  ---- 1-8
        set_inuse_bit_at_offset(victim, size);
        if (av != &main_arena)
          victim->size |= NON_MAIN_ARENA;
        check_malloced_chunk(av, victim, nb);
        return chunk2mem(victim);
      }

      /* place chunk in bin */

      if (in_smallbin_range(size)) {                                     ---- 1-9
        victim_index = smallbin_index(size);
        bck = bin_at(av, victim_index);
        fwd = bck->fd;
      }
      else {                                                             ---- 1-10
        victim_index = largebin_index(size);
        bck = bin_at(av, victim_index);
        fwd = bck->fd;

        /* maintain large bins in sorted order */
        if (fwd != bck) {
          /* Or with inuse bit to speed comparisons */
          size |= PREV_INUSE;
          /* if smaller than smallest, bypass loop below */
          assert((bck->bk->size & NON_MAIN_ARENA) == 0);
          if ((unsigned long)(size) <= (unsigned long)(bck->bk->size)) {
            fwd = bck;
            bck = bck->bk;
          }
          else {
            assert((fwd->size & NON_MAIN_ARENA) == 0);
            while ((unsigned long)(size) < (unsigned long)(fwd->size)) {
              fwd = fwd->fd;
              assert((fwd->size & NON_MAIN_ARENA) == 0);
            }
            bck = fwd->bk;
          }
        }
      }

      mark_bin(av, victim_index);
      victim->bk = bck;
      victim->fd = fwd;
      fwd->bk = victim;
      bck->fd = victim;
    }

    /*
      If a large request, scan through the chunks of current bin in
      sorted order to find smallest that fits. This is the only step
      where an unbounded number of chunks might be scanned without doing
      anything useful with them. However the lists tend to be short.
    */

    if (!in_smallbin_range(nb)) {                                        ---- 1-11
      bin = bin_at(av, idx);

      /* skip scan if empty or largest chunk is too small */
      if ((victim = last(bin)) != bin &&
          (unsigned long)(first(bin)->size) >= (unsigned long)(nb)) {

        while (((unsigned long)(size = chunksize(victim)) <
                (unsigned long)(nb)))
          victim = victim->bk;

        remainder_size = size - nb;
        unlink(victim, bck, fwd);

        /* Exhaust */
        if (remainder_size < MINSIZE) {
          set_inuse_bit_at_offset(victim, size);
          if (av != &main_arena)
            victim->size |= NON_MAIN_ARENA;
          check_malloced_chunk(av, victim, nb);
          return chunk2mem(victim);
        }
        /* Split */
        else {
          remainder = chunk_at_offset(victim, nb);
          unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
          remainder->bk = remainder->fd = unsorted_chunks(av);
          set_head(victim, nb | PREV_INUSE |
                   (av != &main_arena ? NON_MAIN_ARENA : 0));
          set_head(remainder, remainder_size | PREV_INUSE);
          set_foot(remainder, remainder_size);
          check_malloced_chunk(av, victim, nb);
          return chunk2mem(victim);
        }
      }
    }

    /*
      Search for a chunk by scanning bins, starting with next largest
      bin. This search is strictly by best-fit; i.e., the smallest
      (with ties going to approximately the least recently used) chunk
      that fits is selected.

      The bitmap avoids needing to check that most blocks are nonempty.
      The particular case of skipping all bins during warm-up phases
      when no chunks have been returned yet is faster than it might look.
    */

    ++idx;                                                               ---- 1-12
    bin = bin_at(av,idx);
    block = idx2block(idx);
    map = av->binmap[block];
    bit = idx2bit(idx);

    for (;;) {

      /* Skip rest of block if there are no more set bits in this block. */
      if (bit > map || bit == 0) {
        do {
          if (++block >= BINMAPSIZE)  /* out of bins */
            goto use_top;
        } while ( (map = av->binmap[block]) == 0);

        bin = bin_at(av, (block << BINMAPSHIFT));
        bit = 1;
      }

      /* Advance to bin with set bit. There must be one. */
      while ((bit & map) == 0) {
        bin = next_bin(bin);
        bit <<= 1;
        assert(bit != 0);
      }

      /* Inspect the bin. It is likely to be non-empty */
      victim = last(bin);

      /* If a false alarm (empty bin), clear the bit. */
      if (victim == bin) {
        av->binmap[block] = map &= ~bit; /* Write through */
        bin = next_bin(bin);
        bit <<= 1;
      }

      else {
        size = chunksize(victim);

        /* We know the first chunk in this bin is big enough to use. */
        assert((unsigned long)(size) >= (unsigned long)(nb));

        remainder_size = size - nb;

        /* unlink */
        bck = victim->bk;
        bin->bk = bck;
        bck->fd = bin;

        /* Exhaust */
        if (remainder_size < MINSIZE) {
          set_inuse_bit_at_offset(victim, size);
          if (av != &main_arena)
            victim->size |= NON_MAIN_ARENA;
          check_malloced_chunk(av, victim, nb);
          return chunk2mem(victim);
        }

        /* Split */
        else {
          remainder = chunk_at_offset(victim, nb);

          unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
          remainder->bk = remainder->fd = unsorted_chunks(av);
          /* advertise as last remainder */
          if (in_smallbin_range(nb))
            av->last_remainder = remainder;

          set_head(victim, nb | PREV_INUSE |
                   (av != &main_arena ? NON_MAIN_ARENA : 0));
          set_head(remainder, remainder_size | PREV_INUSE);
          set_foot(remainder, remainder_size);
          check_malloced_chunk(av, victim, nb);
          return chunk2mem(victim);
        }
      }
    }

  use_top:
    /*
      If large enough, split off the chunk bordering the end of memory
      (held in av->top). Note that this is in accord with the best-fit
      search rule. In effect, av->top is treated as larger (and thus
      less well fitting) than any other available chunk since it can
      be extended to be as large as necessary (up to system
      limitations).

      We require that av->top always exists (i.e., has size >=
      MINSIZE) after initialization, so if it would otherwise be
      exhuasted by current request, it is replenished. (The main
      reason for ensuring it exists is that we may need MINSIZE space
      to put in fenceposts in sysmalloc.)
    */

    victim = av->top;
    size = chunksize(victim);

    if ((unsigned long)(size) >= (unsigned long)(nb + MINSIZE)) {        ---- 1-13
      remainder_size = size - nb;
      remainder = chunk_at_offset(victim, nb);
      av->top = remainder;
      set_head(victim, nb | PREV_INUSE |
               (av != &main_arena ? NON_MAIN_ARENA : 0));
      set_head(remainder, remainder_size | PREV_INUSE);

      check_malloced_chunk(av, victim, nb);
      return chunk2mem(victim);
    }

    /*
      If there is space available in fastbins, consolidate and retry,
      to possibly avoid expanding memory. This can occur only if nb is
      in smallbin range so we didn't consolidate upon entry.
    */

    else if (have_fastchunks(av)) {                                      ---- 1-14
      assert(in_smallbin_range(nb));
      malloc_consolidate(av);
      idx = smallbin_index(nb); /* restore original bin index */
    }

    /*
       Otherwise, relay to handle system-dependent cases
    */
    else                                                                 ---- 1-15
      return sYSMALLOc(nb, av);
  }
}

#define request2size(req)                                         
  (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ?              
   MINSIZE :                                                      
   ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
/*  Same, except also perform argument check */
#define checked_request2size(req, sz)                             
  if (REQUEST_OUT_OF_RANGE(req)) {                                
    MALLOC_FAILURE_ACTION;                                        
    return 0;                                                     
  }                                                               
  (sz) = request2size(req);

void
_int_free(mstate av, Void_t* mem)
{
  mchunkptr       p;           /* chunk corresponding to mem */
  INTERNAL_SIZE_T size;        /* its size */
  mfastbinptr*    fb;          /* associated fastbin */
  mchunkptr       nextchunk;   /* next contiguous chunk */
  INTERNAL_SIZE_T nextsize;    /* its size */
  int             nextinuse;   /* true if nextchunk is used */
  INTERNAL_SIZE_T prevsize;    /* size of previous contiguous chunk */
  mchunkptr       bck;         /* misc temp for linking */
  mchunkptr       fwd;         /* misc temp for linking */


  /* free(0) has no effect */
  if (mem != 0) {
    p = mem2chunk(mem);
    size = chunksize(p);

    /* Little security check which won't hurt performance: the
       allocator never wrapps around at the end of the address space.
       Therefore we can exclude some size values which might appear
       here by accident or by "design" from some intruder. */
    if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0))
      {
        if (check_action & 1)
          {
#ifdef _LIBC
            _IO_flockfile (stderr);
            int old_flags2 = ((_IO_FILE *) stderr)->_flags2;
            ((_IO_FILE *) stderr)->_flags2 |= _IO_FLAGS2_NOTCANCEL;
#endif
            fprintf (stderr, "free(): invalid pointer %p!n", mem);
#ifdef _LIBC
            ((_IO_FILE *) stderr)->_flags2 |= old_flags2;
            _IO_funlockfile (stderr);
#endif
          }
        if (check_action & 2)
          abort ();
        return;
      }

    check_inuse_chunk(av, p);

    /*
      If eligible, place chunk on a fastbin so it can be found
      and used quickly in malloc.
    */

    if ((unsigned long)(size) <= (unsigned long)(av->max_fast)            ---- 2-1

#if TRIM_FASTBINS
        /*
           If TRIM_FASTBINS set, don't place chunks
           bordering top into fastbins
        */
        && (chunk_at_offset(p, size) != av->top)
#endif
        ) {

      set_fastchunks(av);
      fb = &(av->fastbins[fastbin_index(size)]);
      p->fd = *fb;
      *fb = p;
    }

    /*
       Consolidate other non-mmapped chunks as they arrive.
    */

    else if (!chunk_is_mmapped(p)) {
      nextchunk = chunk_at_offset(p, size);
      nextsize = chunksize(nextchunk);
      assert(nextsize > 0);

      /* consolidate backward */
      if (!prev_inuse(p)) {                                         ---- 2-2
        prevsize = p->prev_size;
        size += prevsize;
        p = chunk_at_offset(p, -((long) prevsize));
        unlink(p, bck, fwd);
      }

      if (nextchunk != av->top) {                                    ---- 2-3
        /* get and clear inuse bit */
        nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

        /* consolidate forward */
        if (!nextinuse) {                                           ---- 2-4
          unlink(nextchunk, bck, fwd);
          size += nextsize;
        } else
          clear_inuse_bit_at_offset(nextchunk, 0);

        /*
          Place the chunk in unsorted chunk list. Chunks are
          not placed into regular bins until after they have
          been given one chance to be used in malloc.
        */

        bck = unsorted_chunks(av);                                   ---- 2-5
        fwd = bck->fd;
        p->bk = bck;
        p->fd = fwd;
        bck->fd = p;
        fwd->bk = p;

        set_head(p, size | PREV_INUSE);
        set_foot(p, size);

        check_free_chunk(av, p);
      }

      /*
         If the chunk borders the current high end of memory,
         consolidate into top
      */

      else {                                                      ---- 2-6
        size += nextsize;
        set_head(p, size | PREV_INUSE);
        av->top = p;
        check_chunk(av, p);
      }

      /*
        If freeing a large space, consolidate possibly-surrounding
        chunks. Then, if the total unused topmost memory exceeds trim
        threshold, ask malloc_trim to reduce top.

        Unless max_fast is 0, we don't know if there are fastbins
        bordering top, so we cannot tell for sure whether threshold
        has been reached unless fastbins are consolidated. But we
        don't want to consolidate on each free. As a compromise,
        consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
        is reached.
      */

      if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {     ---- 2-7
        if (have_fastchunks(av))
          malloc_consolidate(av);                                    ---- 2-8

        if (av == &main_arena) {                                     ---- 2-9
#ifndef MORECORE_CANNOT_TRIM
          if ((unsigned long)(chunksize(av->top)) >=
              (unsigned long)(mp_.trim_threshold))
            sYSTRIm(mp_.top_pad, av);
#endif
        } else {                                                   ---- 2-10
          /* Always try heap_trim(), even if the top chunk is not
             large, because the corresponding heap might go away. */
          heap_info *heap = heap_for_ptr(top(av));

          assert(heap->ar_ptr == av);
          heap_trim(heap, mp_.top_pad);
        }
      }

    }
    /*
      If the chunk was allocated via mmap, release via munmap(). Note
      that if HAVE_MMAP is false but chunk_is_mmapped is true, then
      user must have overwritten memory. There's nothing we can do to
      catch this error unless MALLOC_DEBUG is set, in which case
      check_inuse_chunk (above) will have triggered error.
    */

    else {                                                        ---- 2-11
#if HAVE_MMAP
      int ret;
      INTERNAL_SIZE_T offset = p->prev_size;
      mp_.n_mmaps--;
      mp_.mmapped_mem -= (size + offset);
      ret = munmap((char*)p - offset, size + offset);
      /* munmap returns non-zero on failure */
      assert(ret == 0);
#endif
    }
  }
}

...
  /* Record incoming configuration of top */
  old_top  = av->top;
  old_size = chunksize(old_top);
  old_end  = (char*)(chunk_at_offset(old_top, old_size));
  brk = snd_brk = (char*)(MORECORE_FAILURE);
  （中略）
   if (av != &main_arena) {
     heap_info *old_heap, *heap;
     size_t old_heap_size;
     /* First try to extend the current heap. */
     old_heap = heap_for_ptr(old_top);
     old_heap_size = old_heap->size;
     if (grow_heap(old_heap, MINSIZE + nb - old_size) == 0) {                              ---- 3-1
       av->system_mem += old_heap->size - old_heap_size;
       arena_mem += old_heap->size - old_heap_size;
 #if 0
       if(mmapped_mem + arena_mem + sbrked_mem > max_total_mem)
         max_total_mem = mmapped_mem + arena_mem + sbrked_mem;
 #endif
       set_head(old_top, (((char *)old_heap + old_heap->size) - (char *)old_top)
                | PREV_INUSE);
     }
     else if ((heap = new_heap(nb + (MINSIZE + sizeof(*heap)), mp_.top_pad))) {            ---- 3-2
       /* Use a newly allocated heap.  */
       heap->ar_ptr = av;
       heap->prev = old_heap;
       av->system_mem += heap->size;
       arena_mem += heap->size;
 #if 0
       if((unsigned long)(mmapped_mem + arena_mem + sbrked_mem) > max_total_mem)
         max_total_mem = mmapped_mem + arena_mem + sbrked_mem;
 #endif
       /* Set up the new top.  */
       top(av) = chunk_at_offset(heap, sizeof(*heap));
       set_head(top(av), (heap->size - sizeof(*heap)) | PREV_INUSE);
       /* Setup fencepost and free the old top chunk. */
       /* The fencepost takes at least MINSIZE bytes, because it might
          become the top chunk again later.  Note that a footer is set
          up, too, although the chunk is marked in use. */
       old_size -= MINSIZE;
       set_head(chunk_at_offset(old_top, old_size + 2*SIZE_SZ), 0|PREV_INUSE);             ---- 3-3
       if (old_size >= MINSIZE) {
         set_head(chunk_at_offset(old_top, old_size), (2*SIZE_SZ)|PREV_INUSE);
         set_foot(chunk_at_offset(old_top, old_size), (2*SIZE_SZ));
         set_head(old_top, old_size|PREV_INUSE|NON_MAIN_ARENA);
         _int_free(av, chunk2mem(old_top));
       } else {
         set_head(old_top, (old_size + 2*SIZE_SZ)|PREV_INUSE);
         set_foot(old_top, (old_size + 2*SIZE_SZ));
       }
     }
   } else { /* av == main_arena */
...

/* Delete a heap. */
#define delete_heap(heap) munmap((char*)(heap), HEAP_MAX_SIZE)
static int
internal_function
#if __STD_C
heap_trim(heap_info *heap, size_t pad)
#else
heap_trim(heap, pad) heap_info *heap; size_t pad;
#endif
{
  mstate ar_ptr = heap->ar_ptr;
  unsigned long pagesz = mp_.pagesize;
  mchunkptr top_chunk = top(ar_ptr), p, bck, fwd;
  heap_info *prev_heap;
  long new_size, top_size, extra;
  /* Can this heap go away completely? */
  while(top_chunk == chunk_at_offset(heap, sizeof(*heap))) {                               ---- 4-1
    prev_heap = heap->prev;
    p = chunk_at_offset(prev_heap, prev_heap->size - (MINSIZE-2*SIZE_SZ));
    assert(p->size == (0|PREV_INUSE)); /* must be fencepost */
    p = prev_chunk(p);
    new_size = chunksize(p) + (MINSIZE-2*SIZE_SZ);
    assert(new_size>0 && new_size<(long)(2*MINSIZE));
    if(!prev_inuse(p))
      new_size += p->prev_size;
    assert(new_size>0 && new_size<HEAP_MAX_SIZE);
    if(new_size + (HEAP_MAX_SIZE - prev_heap->size) < pad + MINSIZE + pagesz)              ---- 4-2
      break;
    ar_ptr->system_mem -= heap->size;
    arena_mem -= heap->size;
    delete_heap(heap);                                                                     ---- 4-3
    heap = prev_heap;
    if(!prev_inuse(p)) { /* consolidate backward */
      p = prev_chunk(p);
      unlink(p, bck, fwd);
    }
    assert(((unsigned long)((char*)p + new_size) & (pagesz-1)) == 0);
    assert( ((char*)p + new_size) == ((char*)heap + heap->size) );
    top(ar_ptr) = top_chunk = p;
    set_head(top_chunk, new_size | PREV_INUSE);
    /*check_chunk(ar_ptr, top_chunk);*/
  }
  top_size = chunksize(top_chunk);
  extra = ((top_size - pad - MINSIZE + (pagesz-1))/pagesz - 1) * pagesz;                   ---- 4-4
  if(extra < (long)pagesz)
    return 0;
  /* Try to shrink. */
  if(grow_heap(heap, -extra) != 0)                                                         ---- 4-5
    return 0;
  ar_ptr->system_mem -= extra;
  arena_mem -= extra;
  /* Success. Adjust top accordingly. */
  set_head(top_chunk, (top_size - extra) | PREV_INUSE);
  /*check_chunk(ar_ptr, top_chunk);*/
  return 1;
}

static int
#if __STD_C
grow_heap(heap_info *h, long diff)
#else
grow_heap(h, diff) heap_info *h; long diff;
#endif
{
  size_t page_mask = malloc_getpagesize - 1;
  long new_size;

  if(diff >= 0) {
    diff = (diff + page_mask) & ~page_mask;                                                ---- 5-1
    new_size = (long)h->size + diff;
    if(new_size > HEAP_MAX_SIZE)
      return -1;
    if(mprotect((char *)h + h->size, diff, PROT_READ|PROT_WRITE) != 0)                     ---- 5-2
      return -2;
  } else {
    new_size = (long)h->size + diff;
    if(new_size < (long)sizeof(*h))
      return -1;
    /* Try to re-map the extra heap space freshly to save memory, and
       make it inaccessible. */
    if((char *)MMAP((char *)h + new_size, -diff, PROT_NONE,                                ---- 5-3
                    MAP_PRIVATE|MAP_FIXED) == (char *) MAP_FAILED)
      return -2;
    /*fprintf(stderr, "shrink %p %08lxn", h, new_size);*/
  }
  h->size = new_size;
  return 0;
}

typedef struct _heap_info {
  mstate 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;

$ cat maltest.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
　
#define MEMSIZE 40
#define CHUNKHDSZ 8
　
int dmp(void *mem, int i);
　
int main(int argc, char *argv[])
{
        char *c1, *c2, *c3, *c4;
　
        printf("==> Start %sn", argv[0]);
        c1 = malloc(MEMSIZE);
        c2 = malloc(MEMSIZE);
        c3 = malloc(MEMSIZE);
        printf("c1=%p, c2=%p, c3=%pn", c1, c2, c3);
　
        dmp(c2 - CHUNKHDSZ, MEMSIZE + CHUNKHDSZ * 2);
        free(c1);
        free(c1);                                                      -> 二重フリー
　
        dmp(c2 - CHUNKHDSZ, MEMSIZE + CHUNKHDSZ * 2);
        memset(c2 + MEMSIZE, '', 1);                                 ->メモリ破壊
        dmp(c2 - CHUNKHDSZ, MEMSIZE + CHUNKHDSZ * 2);
        free(c2);
        memset(c2 + MEMSIZE, '', 8);                                 ->メモリ破壊（次のchunkの管理部）
        dmp(c2 - CHUNKHDSZ, MEMSIZE + CHUNKHDSZ * 2);
        free(c3);
        dmp(c3 - CHUNKHDSZ, MEMSIZE + CHUNKHDSZ * 2);
        memset(c3 + MEMSIZE, '', 8);                                 ->メモリ破壊（top chunkの管理部）
        dmp(c3 - CHUNKHDSZ, MEMSIZE + CHUNKHDSZ * 2);
        c4 = malloc(MEMSIZE);
        free(c4);
　
        printf("==> Finished %sn", argv[0]);
        exit(0);
}
　
int dmp(void *mem, int i)
{
        int j, max;
        int *memi = (int *)mem;
　
        printf("start memory dump %p *****n", mem);
        max = i / 16 + (i % 16 ? 1 : 0);
        for (j = 0; j < max; j++) {
                printf("%p : %08x %08x %08x %08xn",
                        memi, *(memi), *(memi+1), *(memi+2), *(memi+3));
                memi += 4;
        }
        printf("end memory dump *****n");
        return max*16;
}
$ gcc -Wall -o maltest maltest.c
$ ./maltest
==> Start ./maltest
c1=0x804a008, c2=0x804a038, c3=0x804a068
start memory dump 0x804a030 *****
0x804a030 : 00000000 00000031 00000000 00000000 ->0x804a030がc2 chunkの先頭
0x804a040 : 00000000 00000000 00000000 00000000
0x804a050 : 00000000 00000000 00000000 00000000
0x804a060 : 00000000 00000031 00000000 00000000 ->0x804a060がc3 chunkの先頭
end memory dump *****
start memory dump 0x804a030 *****
0x804a030 : 00000000 00000031 00000000 00000000
0x804a040 : 00000000 00000000 00000000 00000000
0x804a050 : 00000000 00000000 00000000 00000000
0x804a060 : 00000000 00000031 00000000 00000000
end memory dump *****
start memory dump 0x804a030 *****
0x804a030 : 00000000 00000031 00000000 00000000
0x804a040 : 00000000 00000000 00000000 00000000
0x804a050 : 00000000 00000000 00000000 00000000
0x804a060 : 00000000 00000031 00000000 00000000
end memory dump *****
start memory dump 0x804a030 *****
0x804a030 : 00000000 00000031 0804a000 00000000
0x804a040 : 00000000 00000000 00000000 00000000
0x804a050 : 00000000 00000000 00000000 00000000
0x804a060 : 00000000 00000000 00000000 00000000
end memory dump *****
free(): invalid pointer 0x804a068!              ->デフォルトの設定でのチェック
start memory dump 0x804a060 *****
0x804a060 : 00000000 00000000 00000000 00000000
0x804a070 : 00000000 00000000 00000000 00000000
0x804a080 : 00000000 00000000 00000000 00000000
0x804a090 : 00000000 00020f71 00000000 00000000
end memory dump *****
start memory dump 0x804a060 *****
0x804a060 : 00000000 00000000 00000000 00000000
0x804a070 : 00000000 00000000 00000000 00000000
0x804a080 : 00000000 00000000 00000000 00000000
0x804a090 : 00000000 00000000 00000000 00000000
end memory dump *****
==> Finished ./maltest
$ export MALLOC_CHECK_=1
$ ./maltest
==> Start ./maltest
malloc: using debugging hooks
c1=0x804a008, c2=0x804a038, c3=0x804a068
start memory dump 0x804a030 *****
0x804a030 : 03000094 00000031 00000000 00000000 ->c1のマジックバイト値(0x94)、オフセット(3)、size(0x31)
0x804a040 : 00000000 00000000 00000000 00000000    0x94 : (0x804a000 >> 3) ^ (0x804a000 >> 11) & 0xff
0x804a050 : 00000000 00000000 00000000 00000000    0x31 : (40 + 7 + 4) & ~7 + PREV_INUSE = 49
0x804a060 : 03000092 00000031 00000000 00000000
end memory dump *****
free(): invalid pointer 0x804a008!
start memory dump 0x804a030 *****
0x804a030 : 0300006b 00000031 00000000 00000000 -> c1 free()でマジックバイト値反転(0x94 ^= 0xff)
0x804a040 : 00000000 00000000 00000000 00000000
0x804a050 : 00000000 00000000 00000000 00000000
0x804a060 : 03000092 00000031 00000000 00000000
end memory dump *****
start memory dump 0x804a030 *****
0x804a030 : 0300006b 00000031 00000000 00000000
0x804a040 : 00000000 00000000 00000000 00000000
0x804a050 : 00000000 00000000 00000000 00000000
0x804a060 : 03000000 00000031 00000000 00000000 ->c2のマジックバイト値をクリア
end memory dump *****
free(): invalid pointer 0x804a038!
start memory dump 0x804a030 *****
0x804a030 : 0300006b 00000031 00000000 00000000
0x804a040 : 00000000 00000000 00000000 00000000
0x804a050 : 00000000 00000000 00000000 00000000
0x804a060 : 00000000 00000000 00000000 00000000 ->c3のヘッダ部クリア
end memory dump *****
free(): invalid pointer 0x804a068!
start memory dump 0x804a060 *****
0x804a060 : 00000000 00000000 00000000 00000000
0x804a070 : 00000000 00000000 00000000 00000000
0x804a080 : 00000000 00000000 00000000 00000000
0x804a090 : 03000098 00020f71 00000000 00000000
end memory dump *****
start memory dump 0x804a060 *****
0x804a060 : 00000000 00000000 00000000 00000000
0x804a070 : 00000000 00000000 00000000 00000000
0x804a080 : 00000000 00000000 00000000 00000000
0x804a090 : 00000000 00000000 00000000 00000000 ->top chunkのヘッダ部クリア
end memory dump *****
malloc: top chunk is corrupt
==> Finished ./maltest
$ export MALLOC_CHECK_=3
$ ./maltest
==> Start ./maltest
malloc: using debugging hooks
c1=0x804a008, c2=0x804a038, c3=0x804a068
start memory dump 0x804a030 *****
0x804a030 : 03000094 00000031 00000000 00000000
0x804a040 : 00000000 00000000 00000000 00000000
0x804a050 : 00000000 00000000 00000000 00000000
0x804a060 : 03000092 00000031 00000000 00000000
end memory dump *****
free(): invalid pointer 0x804a008!
Aborted
$