
/*--------------------------------------------------------------------*/
/*--- An implementation of malloc/free which doesn't use sbrk.     ---*/
/*---                                                 vg_malloc2.c ---*/
/*--------------------------------------------------------------------*/

/*
   This file is part of Valgrind, an x86 protected-mode emulator 
   designed for debugging and profiling binaries on x86-Unixes.

   Copyright (C) 2000-2002 Julian Seward 
      jseward@acm.org

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   This program 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
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307, USA.

   The GNU General Public License is contained in the file LICENSE.
*/


#include "vg_include.h"

/* Define to turn on (heavyweight) debugging machinery. */
/* #define DEBUG_MALLOC */


/*------------------------------------------------------------*/
/*--- Structs n stuff                                      ---*/
/*------------------------------------------------------------*/

#define VG_REDZONE_LO_MASK 0x31415927
#define VG_REDZONE_HI_MASK 0x14141356

#define VG_N_MALLOC_LISTS 16 /* do not change this */


typedef UInt Word;
typedef Word WordF;
typedef Word WordL;


/* A superblock. */
typedef 
   struct _Superblock {
      struct _Superblock* next;
      /* number of payload words in this superblock. */
      Int  n_payload_words;
      Word payload_words[0];
   }
   Superblock;


/* An arena. */
typedef 
   struct {
      Char*       name;
      Int         rz_szW; /* Red zone size in words */
      Bool        rz_check; /* Check red-zone on free? */
      Int         min_sblockW; /* Minimum superblock size */
      WordF*      freelist[VG_N_MALLOC_LISTS];
      Superblock* sblocks;
      /* Stats only. */
      UInt bytes_on_loan;
      UInt bytes_mmaped;
      UInt bytes_on_loan_max;
   } 
   Arena;


/* Block layout:

     this block total sizeW   (1 word)
     freelist previous ptr    (1 word)
     freelist next  ptr       (1 word)
     red zone words (depends on .rz_szW field of Arena)
     (payload words)
     red zone words (depends on .rz_szW field of Arena)
     this block total sizeW  (1 word)

     Total size in words (bszW) and payload size in words (pszW)
     are related by
        bszW == pszW + 4 + 2 * a->rz_szW

     Furthermore, both size fields in the block are negative if it is
     not in use, and positive if it is in use.  A block size of zero
     is not possible, because a block always has at least four words
     of overhead.  
*/
typedef
   struct {
      Int   bszW_lo;
      Word* prev;
      Word* next;
      Word  redzone[0];
   } 
   BlockHeader;


/*------------------------------------------------------------*/
/*--- Forwardses ... and misc ...                          ---*/
/*------------------------------------------------------------*/

static Bool blockSane ( Arena* a, Word* b );

/* Align ptr p upwards to an align-sized boundary. */
static
void* align_upwards ( void* p, Int align )
{
   Addr a = (Addr)p;
   if ((a % align) == 0) return (void*)a;
   return (void*)(a - (a % align) + align);
}


/*------------------------------------------------------------*/
/*--- Arena management stuff                               ---*/
/*------------------------------------------------------------*/

/* The arena structures themselves. */
static Arena vg_arena[VG_N_ARENAS];

/* Functions external to this module identify arenas using ArenaIds,
   not Arena*s.  This fn converts the former to the latter. */
static Arena* arenaId_to_ArenaP ( ArenaId arena )
{
   vg_assert(arena >= 0 && arena < VG_N_ARENAS);
   return & vg_arena[arena];
}


/* Initialise an arena. */
static
void arena_init ( Arena* a, Char* name, 
                  Int rz_szW, Bool rz_check, Int min_sblockW )
{
   Int i;
   vg_assert((min_sblockW % VKI_WORDS_PER_PAGE) == 0);
   a->name = name;
   a->rz_szW = rz_szW;
   a->rz_check = rz_check;
   a->min_sblockW = min_sblockW;
   for (i = 0; i < VG_N_MALLOC_LISTS; i++) a->freelist[i] = NULL;
   a->sblocks = NULL;
   a->bytes_on_loan     = 0;
   a->bytes_mmaped      = 0;
   a->bytes_on_loan_max = 0;
}


/* Print vital stats for an arena. */
void VG_(show_all_arena_stats) ( void )
{
   Int i;
   for (i = 0; i < VG_N_ARENAS; i++) {
      VG_(message)(Vg_DebugMsg,
         "Arena `%s': %7d max useful, %7d mmap'd, %7d current useful",
         vg_arena[i].name, 
         vg_arena[i].bytes_on_loan_max, 
         vg_arena[i].bytes_mmaped, 
         vg_arena[i].bytes_on_loan 
      );
   }
}


/* It is important that this library is self-initialising, because it
   may get called very early on -- as a result of C++ static
   constructor initialisations -- before Valgrind itself is
   initialised.  Hence vg_malloc() and vg_free() below always call
   ensure_mm_init() to ensure things are correctly initialised.  */

static
void ensure_mm_init ( void )
{
   static Bool init_done = False;
   if (init_done) return;

   /* Use a checked red zone size of 1 word for our internal stuff,
      and an unchecked zone of arbitrary size for the client.  Of
      course the client's red zone is checked really, but using the
      addressibility maps, not by the mechanism implemented here,
      which merely checks at the time of freeing that the red zone
      words are unchanged. */

   arena_init ( &vg_arena[VG_AR_PRIVATE], "private ", 
                1, True, 262144 );

   arena_init ( &vg_arena[VG_AR_SYMTAB],  "symtab  ", 
                1, True, 262144 );

   arena_init ( &vg_arena[VG_AR_CLIENT],  "client  ",  
                VG_AR_CLIENT_REDZONE_SZW, False, 262144 );

   arena_init ( &vg_arena[VG_AR_DEMANGLE], "demangle",  
                4 /*paranoid*/, True, 16384 );

   arena_init ( &vg_arena[VG_AR_EXECTXT],  "exectxt ",  
                1, True, 16384 );

   arena_init ( &vg_arena[VG_AR_ERRCTXT],  "errctxt ",  
                1, True, 16384 );

   arena_init ( &vg_arena[VG_AR_TRANSIENT], "transien",  
                2, True, 16384 );

   init_done = True;
#  ifdef DEBUG_MALLOC
   VG_(mallocSanityCheckAll)();
#  endif
}


/*------------------------------------------------------------*/
/*--- Arena management stuff                               ---*/
/*------------------------------------------------------------*/

static
Superblock* newSuperblock ( Arena* a, Int cszW )
{
   Superblock* sb;
   cszW += 2; /* Take into account sb->next and sb->n_words fields */
   if (cszW < a->min_sblockW) cszW = a->min_sblockW;
   while ((cszW % VKI_WORDS_PER_PAGE) > 0) cszW++;
   sb = VG_(get_memory_from_mmap) ( cszW * sizeof(Word) );
   sb->n_payload_words = cszW - 2;
   a->bytes_mmaped += cszW * sizeof(Word);
   if (0)
      VG_(message)(Vg_DebugMsg, "newSuperblock, %d payload words", 
                                sb->n_payload_words);
   return sb;
}


/* Find the superblock containing the given chunk. */
static
Superblock* findSb ( Arena* a, UInt* ch )
{
   Superblock* sb;
   for (sb = a->sblocks; sb; sb = sb->next)
      if (&sb->payload_words[0] <= ch
          && ch < &sb->payload_words[sb->n_payload_words]) 
         return sb;
   VG_(printf)("findSb: can't find pointer %p in arena `%s'\n",
               ch, a->name );
   VG_(panic)("findSb: vg_free() in wrong arena?");
   return NULL; /*NOTREACHED*/
}


/*------------------------------------------------------------*/
/*--- Low-level functions for working with blocks.         ---*/
/*------------------------------------------------------------*/

/* Add the not-in-use attribute to a bszW. */
static __inline__
Int mk_free_bszW ( Int bszW )
{
   vg_assert(bszW != 0);
   return (bszW < 0) ? bszW : -bszW;
}

/* Add the in-use attribute to a bszW. */
static __inline__
Int mk_inuse_bszW ( Int bszW )
{
   vg_assert(bszW != 0);
   return (bszW < 0) ? -bszW : bszW;
}

/* Remove the in-use/not-in-use attribute from a bszW, leaving just
   the size. */
static __inline__
Int mk_plain_bszW ( Int bszW )
{
   vg_assert(bszW != 0);
   return (bszW < 0) ? -bszW : bszW;
}

/* Does this bszW have the in-use attribute ? */
static __inline__
Bool is_inuse_bszW ( Int bszW )
{
   vg_assert(bszW != 0);
   return (bszW < 0) ? False : True;
}


/* Given the addr of the first word of a block, return the addr of the
   last word. */
static __inline__
WordL* first_to_last ( WordF* fw )
{
   return fw + mk_plain_bszW(fw[0]) - 1;
}

/* Given the addr of the last word of a block, return the addr of the
   first word. */
static __inline__
WordF* last_to_first ( WordL* lw )
{
   return lw - mk_plain_bszW(lw[0]) + 1;
}


/* Given the addr of the first word of a block, return the addr of the
   first word of its payload. */
static __inline__
Word* first_to_payload ( Arena* a, WordF* fw )
{
   return & fw[3 + a->rz_szW];
}

/* Given the addr of the first word of a the payload of a block,
   return the addr of the first word of the block. */
static __inline__
Word* payload_to_first ( Arena* a, WordF* payload )
{
   return & payload[- 3 - a->rz_szW];
}

/* Set and get the lower size field of a block. */
static __inline__
void set_bszW_lo ( WordF* fw, Int bszW ) { 
   fw[0] = bszW; 
}
static __inline__
Int get_bszW_lo ( WordF* fw )
{
   return fw[0];
}


/* Set and get the next and previous link fields of a block. */
static __inline__
void set_prev_p  ( WordF* fw, Word* prev_p ) { 
   fw[1] = (Word)prev_p; 
}
static __inline__
void set_next_p  ( WordF* fw, Word* next_p ) { 
   fw[2] = (Word)next_p; 
}
static __inline__
Word* get_prev_p  ( WordF* fw ) { 
   return (Word*)(fw[1]);
}
static __inline__
Word* get_next_p  ( WordF* fw ) { 
   return (Word*)(fw[2]);
}


/* Set and get the upper size field of a block. */
static __inline__
void set_bszW_hi ( WordF* fw, Int bszW ) {
   WordL* lw = first_to_last(fw);
   vg_assert(lw == fw + mk_plain_bszW(bszW) - 1);
   lw[0] = bszW;
}
static __inline__
Int get_bszW_hi ( WordF* fw ) {
   WordL* lw = first_to_last(fw);
   return lw[0];
}

/* Get the upper size field of a block, given a pointer to the last
   word of it. */
static __inline__
Int get_bszW_hi_from_last_word ( WordL* lw ) {
   WordF* fw = last_to_first(lw);
   return get_bszW_lo(fw);
}


/* Read and write the lower and upper red-zone words of a block. */
static __inline__
void set_rz_lo_word ( Arena* a, WordF* fw, Int rz_wordno, Word w )
{
   fw[3 + rz_wordno] = w;
}
static __inline__
void set_rz_hi_word ( Arena* a, WordF* fw, Int rz_wordno, Word w )
{
   WordL* lw = first_to_last(fw);
   lw[-1-rz_wordno] = w;
}
static __inline__
Word get_rz_lo_word ( Arena* a, WordF* fw, Int rz_wordno )
{
   return fw[3 + rz_wordno];
}
static __inline__
Word get_rz_hi_word ( Arena* a, WordF* fw, Int rz_wordno )
{
   WordL* lw = first_to_last(fw);
   return lw[-1-rz_wordno];
}


/* Return the lower, upper and total overhead in words for a block.
   These are determined purely by which arena the block lives in. */
static __inline__
Int overhead_szW_lo ( Arena* a )
{
   return 3 + a->rz_szW;
}
static __inline__
Int overhead_szW_hi ( Arena* a )
{
   return 1 + a->rz_szW;
}
static __inline__
Int overhead_szW ( Arena* a )
{
   return overhead_szW_lo(a) + overhead_szW_hi(a);
}


/* Convert pointer size in words to block size in words, and back. */
static __inline__
Int pszW_to_bszW ( Arena* a, Int pszW )
{
   vg_assert(pszW >= 0);
   return pszW + overhead_szW(a);
}
static __inline__
Int bszW_to_pszW ( Arena* a, Int bszW )
{
   Int pszW = bszW - overhead_szW(a);
   vg_assert(pszW >= 0);
   return pszW;
}

/*------------------------------------------------------------*/
/*--- Functions for working with freelists.                ---*/
/*------------------------------------------------------------*/

/* Determination of which freelist a block lives on is based on the
   payload size, not block size, in words. */

/* Convert a payload size in words to a freelist number. */

static
Int pszW_to_listNo ( Int pszW )
{
   vg_assert(pszW >= 0);
   if (pszW <= 3)   return 0;
   if (pszW <= 4)   return 1;
   if (pszW <= 5)   return 2;
   if (pszW <= 6)   return 3;
   if (pszW <= 7)   return 4;
   if (pszW <= 8)   return 5;
   if (pszW <= 9)   return 6;
   if (pszW <= 10)  return 7;
   if (pszW <= 11)  return 8;
   if (pszW <= 12)  return 9;
   if (pszW <= 16)  return 10;
   if (pszW <= 32)  return 11;
   if (pszW <= 64)  return 12;
   if (pszW <= 128) return 13;
   if (pszW <= 256) return 14;
   return 15;
}


/* What are the minimum and maximum payload sizes for a given list? */

static
Int listNo_to_pszW_min ( Int listNo )
{
   Int pszW = 0;
   vg_assert(listNo >= 0 && listNo <= VG_N_MALLOC_LISTS);
   while (pszW_to_listNo(pszW) < listNo) pszW++;
   return pszW;
}

static
Int listNo_to_pszW_max ( Int listNo )
{
   vg_assert(listNo >= 0 && listNo <= VG_N_MALLOC_LISTS);
   if (listNo == VG_N_MALLOC_LISTS-1) {
      return 999999999;
   } else {
      return listNo_to_pszW_min(listNo+1) - 1;
   }
}


/* A nasty hack to try and reduce fragmentation.  Try and replace
   a->freelist[lno] with another block on the same list but with a
   lower address, with the idea of attempting to recycle the same
   blocks rather than cruise through the address space. */

static 
void swizzle ( Arena* a, Int lno )
{
   UInt* p_best;
   UInt* pp;
   UInt* pn;
   Int   i;

   p_best = a->freelist[lno];
   if (p_best == NULL) return;

   pn = pp = p_best;
   for (i = 0; i < 20; i++) {
      pn = get_next_p(pn);
      pp = get_prev_p(pp);
      if (pn < p_best) p_best = pn;
      if (pp < p_best) p_best = pp;
   }
   if (p_best < a->freelist[lno]) {
#     ifdef DEBUG_MALLOC
      VG_(printf)("retreat by %d\n", 
           ((Char*)(a->freelist[lno])) - ((Char*)p_best));
#     endif
      a->freelist[lno] = p_best;
   }
}


/*------------------------------------------------------------*/
/*--- Creating and deleting blocks.                        ---*/
/*------------------------------------------------------------*/

/* Mark the words at b .. b+bszW-1 as not in use, and add them to the
   relevant free list. */

static
void mkFreeBlock ( Arena* a, Word* b, Int bszW, Int b_lno )
{
   Int pszW = bszW_to_pszW(a, bszW);
   vg_assert(pszW >= 0);
   vg_assert(b_lno == pszW_to_listNo(pszW));
   /* Set the size fields and indicate not-in-use. */
   set_bszW_lo(b, mk_free_bszW(bszW));
   set_bszW_hi(b, mk_free_bszW(bszW));

   /* Add to the relevant list. */
   if (a->freelist[b_lno] == NULL) {
      set_prev_p(b, b);
      set_next_p(b, b);
      a->freelist[b_lno] = b;
   } else {
      Word* b_prev = get_prev_p(a->freelist[b_lno]);
      Word* b_next = a->freelist[b_lno];
      set_next_p(b_prev, b);
      set_prev_p(b_next, b);
      set_next_p(b, b_next);
      set_prev_p(b, b_prev);
   }
#  ifdef DEBUG_MALLOC
   (void)blockSane(a,b);
#  endif
}


/* Mark the words at b .. b+bszW-1 as in use, and set up the block
   appropriately. */
static
void mkInuseBlock ( Arena* a, UInt* b, UInt bszW )
{
   Int i;
   set_bszW_lo(b, mk_inuse_bszW(bszW));
   set_bszW_hi(b, mk_inuse_bszW(bszW));
   set_prev_p(b, NULL);
   set_next_p(b, NULL);
   if (a->rz_check) {
      for (i = 0; i < a->rz_szW; i++) {
         set_rz_lo_word(a, b, i, (UInt)b ^ VG_REDZONE_LO_MASK);
         set_rz_hi_word(a, b, i, (UInt)b ^ VG_REDZONE_HI_MASK);
      }
   }
#  ifdef DEBUG_MALLOC
   (void)blockSane(a,b);
#  endif
}


/* Remove a block from a given list.  Does no sanity checking. */
static
void unlinkBlock ( Arena* a, UInt* b, Int listno )
{
   vg_assert(listno >= 0 && listno < VG_N_MALLOC_LISTS);
   if (get_prev_p(b) == b) {
      /* Only one element in the list; treat it specially. */
      vg_assert(get_next_p(b) == b);
      a->freelist[listno] = NULL;
   } else {
      UInt* b_prev = get_prev_p(b);
      UInt* b_next = get_next_p(b);
      a->freelist[listno] = b_prev;
      set_next_p(b_prev, b_next);
      set_prev_p(b_next, b_prev);
      swizzle ( a, listno );
   }
   set_prev_p(b, NULL);
   set_next_p(b, NULL);
}


/* Split an existing free block into two pieces, and put the fragment
   (the second one along in memory) onto the relevant free list.
   req_bszW is the required size of the block which isn't the
   fragment. */
static
void splitChunk ( Arena* a, UInt* b, Int b_listno, UInt req_bszW )
{
   Int b_bszW, frag_bszW;
   b_bszW = mk_plain_bszW(get_bszW_lo(b));
   vg_assert(req_bszW < b_bszW);
   frag_bszW = b_bszW - req_bszW;
   vg_assert(frag_bszW >= overhead_szW(a));
   /*
   printf( "split %d into %d and %d\n", 
                   b_bszW,req_bszW,frag_bszW  );
   */
   vg_assert(bszW_to_pszW(a, frag_bszW) > 0);
   unlinkBlock(a, b, b_listno);
   mkInuseBlock(a, b, req_bszW);
   mkFreeBlock(a, &b[req_bszW], frag_bszW, 
                  pszW_to_listNo(bszW_to_pszW(a, frag_bszW)));
}


/*------------------------------------------------------------*/
/*--- Sanity-check/debugging machinery.                    ---*/
/*------------------------------------------------------------*/

/* Do some crude sanity checks on a chunk. */
static 
Bool blockSane ( Arena* a, Word* b )
{
#  define BLEAT(str) VG_(printf)("blockSane: fail -- %s\n",str)
   Int i;
   if (get_bszW_lo(b) != get_bszW_hi(b)) 
      {BLEAT("sizes");return False;}
   if (a->rz_check && is_inuse_bszW(get_bszW_lo(b))) {
      for (i = 0; i < a->rz_szW; i++) {
         if (get_rz_lo_word(a, b, i) != ((Word)b ^ VG_REDZONE_LO_MASK))
            {BLEAT("redzone-lo");return False;}
         if (get_rz_hi_word(a, b, i) != ((Word)b ^ VG_REDZONE_HI_MASK))
            {BLEAT("redzone-hi");return False;}
      }      
   }
   return True;
#  undef BLEAT
}


/* Print superblocks (only for debugging). */
static 
void ppSuperblocks ( Arena* a )
{
   Int i, ch_bszW, blockno;
   UInt* ch;
   Superblock* sb = a->sblocks;
   blockno = 1;

   while (sb) {
      VG_(printf)( "\n" );
      VG_(printf)( "superblock %d at %p, sb->n_pl_ws = %d, next = %p\n", 
                   blockno++, sb, sb->n_payload_words, sb->next );
      i = 0;
      while (True) {
         if (i >= sb->n_payload_words) break;
         ch     = &sb->payload_words[i];
         ch_bszW = get_bszW_lo(ch);
         VG_(printf)( "   block at %d, bszW %d: ", i, mk_plain_bszW(ch_bszW) );
         VG_(printf)( "%s, ", is_inuse_bszW(ch_bszW) ? "inuse" : "free" );
         VG_(printf)( "%s\n", blockSane(a,ch) ? "ok" : "BAD" );
         i += mk_plain_bszW(ch_bszW);
      }
      if (i > sb->n_payload_words) 
         VG_(printf)( "   last block overshoots end of SB\n");
      sb = sb->next;
   }
   VG_(printf)( "end of superblocks\n\n" );
}


/* Sanity check both the superblocks and the chains. */
void VG_(mallocSanityCheckArena) ( ArenaId aid )
{
   Int         i, superblockctr, b_bszW, b_pszW, blockctr_sb, blockctr_li;
   Int         blockctr_sb_free, listno, list_min_pszW, list_max_pszW;
   Superblock* sb;
   Bool        thisFree, lastWasFree;
   Word*       b;
   Word*       b_prev;
   UInt        arena_bytes_on_loan;
   Arena*      a;

#  define BOMB VG_(panic)("vg_mallocSanityCheckArena")

   a = arenaId_to_ArenaP(aid);
   
   /* First, traverse all the superblocks, inspecting the chunks in
      each. */
   superblockctr = blockctr_sb = blockctr_sb_free = 0;
   arena_bytes_on_loan = 0;
   sb = a->sblocks;
   while (sb) {
      lastWasFree = False;
      superblockctr++;
      i = 0;
      while (True) {
         if (i >= sb->n_payload_words) break;
         blockctr_sb++;
         b     = &sb->payload_words[i];
         b_bszW = get_bszW_lo(b);
         if (!blockSane(a, b)) {
            VG_(printf)( "mallocSanityCheck: sb %p, block %d (bszW %d): "
                         "BAD\n",
                         sb, i, b_bszW );
            BOMB;
         }
         thisFree = !is_inuse_bszW(b_bszW);
         if (thisFree && lastWasFree) {
            VG_(printf)( "mallocSanityCheck: sb %p, block %d (bszW %d): "
                         "UNMERGED FREES\n",
                         sb, i, b_bszW );
            BOMB;
         }
         lastWasFree = thisFree;
         if (thisFree) blockctr_sb_free++;
         if (!thisFree) 
            arena_bytes_on_loan += sizeof(Word) * bszW_to_pszW(a, b_bszW);
         i += mk_plain_bszW(b_bszW);
      }
      if (i > sb->n_payload_words) {
         VG_(printf)( "mallocSanityCheck: sb %p: last block "
                      "overshoots end\n", sb);
         BOMB;
      }
      sb = sb->next;
   }

   if (arena_bytes_on_loan != a->bytes_on_loan) {
            VG_(printf)( 
                    "mallocSanityCheck: a->bytes_on_loan %d, "
                    "arena_bytes_on_loan %d: "
                    "MISMATCH\n", a->bytes_on_loan, arena_bytes_on_loan);
      ppSuperblocks(a);
      BOMB;
   }

   /* Second, traverse each list, checking that the back pointers make
      sense, counting blocks encountered, and checking that each block
      is an appropriate size for this list. */
   blockctr_li = 0;
   for (listno = 0; listno < VG_N_MALLOC_LISTS; listno++) {
      list_min_pszW = listNo_to_pszW_min(listno);
      list_max_pszW = listNo_to_pszW_max(listno);
      b = a->freelist[listno];
      if (b == NULL) continue;
      while (True) {
         b_prev = b;
         b = get_next_p(b);
         if (get_prev_p(b) != b_prev) {
            VG_(printf)( "mallocSanityCheck: list %d at %p: "
                         "BAD LINKAGE\n", 
                         listno, b );
            BOMB;
         }
         b_pszW = bszW_to_pszW(a, mk_plain_bszW(get_bszW_lo(b)));
         if (b_pszW < list_min_pszW || b_pszW > list_max_pszW) {
            VG_(printf)( 
               "mallocSanityCheck: list %d at %p: "
               "WRONG CHAIN SIZE %d (%d, %d)\n", 
               listno, b, b_pszW, list_min_pszW, list_max_pszW );
            BOMB;
         }
         blockctr_li++;
         if (b == a->freelist[listno]) break;
      }
   }

   if (blockctr_sb_free != blockctr_li) {
      VG_(printf)( 
         "mallocSanityCheck: BLOCK COUNT MISMATCH "
         "(via sbs %d, via lists %d)\n",
         blockctr_sb_free, blockctr_li );
      ppSuperblocks(a);
      BOMB;
   }

   VG_(message)(Vg_DebugMsg,
                "mSC [%s]: %2d sbs, %5d tot bs, %4d/%-4d free bs, "
                "%2d lists, %7d mmap, %7d loan", 
                a->name,
                superblockctr,
                blockctr_sb, blockctr_sb_free, blockctr_li, 
                VG_N_MALLOC_LISTS, 
                a->bytes_mmaped, a->bytes_on_loan);   
#  undef BOMB
}


void VG_(mallocSanityCheckAll) ( void )
{
   Int i;
   for (i = 0; i < VG_N_ARENAS; i++)
      VG_(mallocSanityCheckArena) ( i );
}


/* Really, this isn't the right place for this.  Nevertheless: find
   out if an arena is empty -- currently has no bytes on loan.  This
   is useful for checking for memory leaks (of valgrind, not the
   client.) 
*/
Bool VG_(is_empty_arena) ( ArenaId aid )
{
   Arena*      a;
   Superblock* sb;
   WordF*      b;
   Int         b_bszW;
   ensure_mm_init();
   a = arenaId_to_ArenaP(aid);
   for (sb = a->sblocks; sb != NULL; sb = sb->next) {
      /* If the superblock is empty, it should contain a single free
         block, of the right size. */
      b = &(sb->payload_words[0]);
      b_bszW = get_bszW_lo(b);
      if (is_inuse_bszW(b_bszW)) return False;
      if (mk_plain_bszW(b_bszW) != sb->n_payload_words) return False;
      /* So this block is not in use and is of the right size.  Keep
         going. */
   }
   return True;
}


/*------------------------------------------------------------*/
/*--- Externally-visible functions.                        ---*/
/*------------------------------------------------------------*/

void* VG_(malloc) ( ArenaId aid, Int req_pszB )
{
   Int         req_pszW, req_bszW, frag_bszW, b_bszW, lno;
   Superblock* new_sb;
   Word*       b;
   Arena*      a;

   VGP_PUSHCC(VgpMalloc);

   ensure_mm_init();
   a = arenaId_to_ArenaP(aid);

   vg_assert(req_pszB >= 0);
   vg_assert(req_pszB < 0x7FFFFFF0);

   req_pszW = (req_pszB + VKI_BYTES_PER_WORD - 1) / VKI_BYTES_PER_WORD;

   /* Keep gcc -O happy: */
   b = NULL;

   /* Start searching at this list. */
   lno = pszW_to_listNo(req_pszW);

   /* This loop finds a list which has a block big enough, or sets
      req_listno to N_LISTS if no such block exists. */
   while (True) {
      if (lno == VG_N_MALLOC_LISTS) break;
      /* If this list is empty, try the next one. */
      if (a->freelist[lno] == NULL) {
         lno++;
         continue;
      }
      /* Scan a->list[lno] to find a big-enough chunk. */
      b = a->freelist[lno];
      b_bszW = mk_plain_bszW(get_bszW_lo(b));
      while (True) {
         if (bszW_to_pszW(a, b_bszW) >= req_pszW) break;
         b = get_next_p(b);
         b_bszW = mk_plain_bszW(get_bszW_lo(b));
         if (b == a->freelist[lno]) break;
      }
      if (bszW_to_pszW(a, b_bszW) >= req_pszW) break;
      /* No luck?  Try a larger list. */
      lno++;
   }

   /* Either lno < VG_N_MALLOC_LISTS and b points to the selected
      block, or lno == VG_N_MALLOC_LISTS, and we have to allocate a
      new superblock. */

   if (lno == VG_N_MALLOC_LISTS) {
      req_bszW = pszW_to_bszW(a, req_pszW);      
      new_sb = newSuperblock(a, req_bszW);
      vg_assert(new_sb != NULL);
      new_sb->next = a->sblocks;
      a->sblocks = new_sb;
      b = &(new_sb->payload_words[0]);
      lno = pszW_to_listNo(bszW_to_pszW(a, new_sb->n_payload_words));
      mkFreeBlock ( a, b, new_sb->n_payload_words, lno);
   }

   /* Ok, we can allocate from b, which lives in list req_listno. */
   vg_assert(b != NULL);
   vg_assert(lno >= 0 && lno < VG_N_MALLOC_LISTS);
   vg_assert(a->freelist[lno] != NULL);
   b_bszW = mk_plain_bszW(get_bszW_lo(b));
   req_bszW = pszW_to_bszW(a, req_pszW);
   /* req_bszW is the size of the block we are after.  b_bszW is the
      size of what we've actually got. */
   vg_assert(b_bszW >= req_bszW);

   /* Could we split this block and still get a useful fragment?
      Where "useful" means that the payload size of the frag is at
      least one word.  */
   frag_bszW = b_bszW - req_bszW;
   if (frag_bszW > overhead_szW(a)) {
      splitChunk(a, b, lno, req_bszW);
   } else {
      /* No, mark as in use and use as-is. */
      unlinkBlock(a, b, lno);
      /*
      set_bszW_lo(b, mk_inuse_bszW(b_bszW));
      set_bszW_hi(b, mk_inuse_bszW(b_bszW));
      */
      mkInuseBlock(a, b, b_bszW);
   }
   vg_assert(req_bszW <= mk_plain_bszW(get_bszW_lo(b)));

   a->bytes_on_loan 
      += sizeof(Word) 
         * bszW_to_pszW(a, mk_plain_bszW(get_bszW_lo(b)));
   if (a->bytes_on_loan > a->bytes_on_loan_max)
      a->bytes_on_loan_max = a->bytes_on_loan;

#  ifdef DEBUG_MALLOC
   VG_(mallocSanityCheckArena)(aid);
#  endif

   VGP_POPCC;
   return first_to_payload(a, b);
}

 
void VG_(free) ( ArenaId aid, void* ptr )
{
   Superblock* sb;
   UInt*       sb_payl_firstw;
   UInt*       sb_payl_lastw;
   UInt*       other;
   UInt*       ch;
   Int         ch_bszW, ch_pszW, other_bszW, ch_listno;
   Arena*      a;

   VGP_PUSHCC(VgpMalloc);

   ensure_mm_init();
   a = arenaId_to_ArenaP(aid);

   if (ptr == NULL) return;

   ch = payload_to_first(a, ptr);

#  ifdef DEBUG_MALLOC
   vg_assert(blockSane(a,ch));
#  endif

   a->bytes_on_loan 
      -= sizeof(Word) 
         * bszW_to_pszW(a, mk_plain_bszW(get_bszW_lo(ch)));

   sb             = findSb( a, ch );
   sb_payl_firstw = &(sb->payload_words[0]);
   sb_payl_lastw  = &(sb->payload_words[sb->n_payload_words-1]);

   /* Put this chunk back on a list somewhere. */
   ch_bszW    = get_bszW_lo(ch);
   ch_pszW    = bszW_to_pszW(a, ch_bszW);
   ch_listno  = pszW_to_listNo(ch_pszW);
   mkFreeBlock( a, ch, ch_bszW, ch_listno );

   /* See if this block can be merged with the following one. */
   other = ch + ch_bszW;
   /* overhead_szW(a) is the smallest possible bszW for this arena.
      So the nearest possible end to the block beginning at other is
      other+overhead_szW(a)-1.  Hence the test below. */
   if (other+overhead_szW(a)-1 <= sb_payl_lastw) {
      other_bszW = get_bszW_lo(other);
      if (!is_inuse_bszW(other_bszW)) {
         /* VG_(printf)( "merge-successor\n"); */
         other_bszW = mk_plain_bszW(other_bszW);
#        ifdef DEBUG_MALLOC
         vg_assert(blockSane(a, other));
#        endif
         unlinkBlock( a, ch, ch_listno );
         unlinkBlock( a, other, pszW_to_listNo(bszW_to_pszW(a,other_bszW)) );
         ch_bszW += other_bszW; 
         ch_listno = pszW_to_listNo(bszW_to_pszW(a, ch_bszW));
         mkFreeBlock( a, ch, ch_bszW, ch_listno );
      }
   }

   /* See if this block can be merged with its predecessor. */
   if (ch-overhead_szW(a) >= sb_payl_firstw) {
      other_bszW = get_bszW_hi_from_last_word( ch-1 );
      if (!is_inuse_bszW(other_bszW)) {
         /* VG_(printf)( "merge-predecessor\n"); */
         other = last_to_first( ch-1 );
         other_bszW = mk_plain_bszW(other_bszW);         
         unlinkBlock( a, ch, ch_listno );
         unlinkBlock( a, other, pszW_to_listNo(bszW_to_pszW(a, other_bszW)) );
         ch = other;
         ch_bszW += other_bszW;
         ch_listno = pszW_to_listNo(bszW_to_pszW(a, ch_bszW));
         mkFreeBlock( a, ch, ch_bszW, ch_listno );
      }
   }

#  ifdef DEBUG_MALLOC
   VG_(mallocSanityCheckArena)(aid);
#  endif

   VGP_POPCC;
}


/*
   The idea for malloc_aligned() is to allocate a big block, base, and
   then split it into two parts: frag, which is returned to the the
   free pool, and align, which is the bit we're really after.  Here's
   a picture.  L and H denote the block lower and upper overheads, in
   words.  The details are gruesome.  Note it is slightly complicated
   because the initial request to generate base may return a bigger
   block than we asked for, so it is important to distinguish the base
   request size and the base actual size.

   frag_b                   align_b
   |                        |
   |    frag_p              |    align_p
   |    |                   |    |
   v    v                   v    v

   +---+                +---+---+               +---+
   | L |----------------| H | L |---------------| H |
   +---+                +---+---+               +---+

   ^    ^                        ^
   |    |                        :
   |    base_p                   this addr must be aligned
   |
   base_b

   .    .               .   .   .               .   .
   <------ frag_bszW ------->   .               .   .
   .    <------------- base_pszW_act ----------->   .
   .    .               .   .   .               .   .

*/
void* VG_(malloc_aligned) ( ArenaId aid, Int req_alignB, Int req_pszB )
{
   Int    req_alignW, req_pszW, base_pszW_req, base_pszW_act, frag_bszW;
   Word   *base_b, *base_p, *align_p;
   UInt   saved_bytes_on_loan;
   Arena* a;

   ensure_mm_init();
   a = arenaId_to_ArenaP(aid);

   vg_assert(req_pszB >= 0);
   vg_assert(req_pszB < 0x7FFFFFF0);

   /* Check that the requested alignment seems reasonable; that is, is
      a power of 2.  There must be a better way to do this.  What is
      it? */
   switch (req_alignB) {
      case 8: case 16: case 32: case 64: case 128: case 256: 
      case 512: case 1024: case 2048: case 4096: case 8192: 
      case 16384: case 32768: case 65536: case 131072: 
      case 1048576: 
         /* can't be bothered to calculate larger ones */
         break;
      default:
         VG_(printf)("vg_malloc_aligned(%p, %d, %d)\nbad alignment request", 
                     a, req_pszB, req_alignB );
         VG_(panic)("vg_malloc_aligned");
         /*NOTREACHED*/
   }

   /* Required alignment, in words.  Since it's constrained to be a
      power of 2 >= word size, no need to align the alignment.  Still,
      we check. */
   req_alignW = req_alignB / VKI_BYTES_PER_WORD;
   vg_assert(req_alignB == req_alignW * VKI_BYTES_PER_WORD);

   /* Required payload size for the aligned chunk. */
   req_pszW = (req_pszB + VKI_BYTES_PER_WORD - 1) / VKI_BYTES_PER_WORD;
   
   /* Payload size to request for the big block that we will split
      up. */
   base_pszW_req = req_pszW + overhead_szW(a) + req_alignW;

   /* Payload ptr for the block we are going to split.  Note this
      changes a->bytes_on_loan; we save and restore it ourselves. */
   saved_bytes_on_loan = a->bytes_on_loan;
   base_p = VG_(malloc) ( aid, base_pszW_req * VKI_BYTES_PER_WORD );
   a->bytes_on_loan = saved_bytes_on_loan;

   /* Block ptr for the block we are going to split. */
   base_b = payload_to_first ( a, base_p );

   /* Pointer to the payload of the aligned block we are going to
      return.  This has to be suitably aligned. */
   align_p = align_upwards ( base_b + 2 * overhead_szW_lo(a) 
                                    + overhead_szW_hi(a),
                             req_alignB );

   /* The block size of the fragment we will create.  This must be big
      enough to actually create a fragment. */
   frag_bszW = align_p - overhead_szW_lo(a) - base_b;
   vg_assert(frag_bszW >= overhead_szW(a));

   /* The actual payload size of the block we are going to split. */
   base_pszW_act = bszW_to_pszW(a, mk_plain_bszW(get_bszW_lo(base_b)));

   /* Create the fragment block, and put it back on the relevant free
      list. */
   mkFreeBlock ( a, base_b, frag_bszW, 
                 pszW_to_listNo(bszW_to_pszW(a, frag_bszW)) );

   /* Create the aligned block. */
   mkInuseBlock ( a,
                  align_p - overhead_szW_lo(a), 
                  base_p + base_pszW_act 
                         + overhead_szW_hi(a) 
                         - (align_p - overhead_szW_lo(a)) );

   /* Final sanity checks. */
   vg_assert(( (UInt)align_p % req_alignB) == 0);

   vg_assert(is_inuse_bszW(get_bszW_lo(payload_to_first(a, align_p))));

   vg_assert(req_pszW 
             <= 
             bszW_to_pszW(a, mk_plain_bszW(get_bszW_lo(
                payload_to_first(a, align_p))))
            );

   a->bytes_on_loan 
      += sizeof(Word)
         * bszW_to_pszW(a, mk_plain_bszW(get_bszW_lo(
              payload_to_first(a, align_p))));
   if (a->bytes_on_loan > a->bytes_on_loan_max)
      a->bytes_on_loan_max = a->bytes_on_loan;

#  ifdef DEBUG_MALLOC
   VG_(mallocSanityCheckArena)(aid);
#  endif

   return align_p;
}


/*------------------------------------------------------------*/
/*--- Services layered on top of malloc/free.              ---*/
/*------------------------------------------------------------*/

void* VG_(calloc) ( ArenaId aid, Int nmemb, Int nbytes )
{
   Int    i, size;
   UChar* p;
   size = nmemb * nbytes;
   vg_assert(size > 0);
   p = VG_(malloc) ( aid, size );
   for (i = 0; i < size; i++) p[i] = 0;
   return p;
}


void* VG_(realloc) ( ArenaId aid, void* ptr, Int req_pszB )
{
   Arena* a;
   Int    old_bszW, old_pszW, old_pszB, i;
   UChar  *p_old, *p_new;
   UInt*  ch;

   ensure_mm_init();
   a = arenaId_to_ArenaP(aid);

   vg_assert(req_pszB >= 0);
   vg_assert(req_pszB < 0x7FFFFFF0);

   ch = payload_to_first(a, ptr);
   vg_assert(blockSane(a, ch));

   old_bszW = get_bszW_lo(ch);
   vg_assert(is_inuse_bszW(old_bszW));
   old_bszW = mk_plain_bszW(old_bszW);
   old_pszW = bszW_to_pszW(a, old_bszW);
   old_pszB = old_pszW * VKI_BYTES_PER_WORD;

   if (req_pszB <= old_pszB) return ptr;

   p_new = VG_(malloc) ( aid, req_pszB );
   p_old = (UChar*)ptr;
   for (i = 0; i < old_pszB; i++)
      p_new[i] = p_old[i];

   VG_(free)(aid, p_old);
   return p_new;
}


/*------------------------------------------------------------*/
/*--- The original test driver machinery.                  ---*/
/*------------------------------------------------------------*/

#if 0

#if 1
#define N_TEST_TRANSACTIONS 100000000
#define N_TEST_ARR 200000
#define M_TEST_MALLOC 1000
#else
#define N_TEST_TRANSACTIONS 500000
#define N_TEST_ARR 30000
#define M_TEST_MALLOC 500
#endif


void* test_arr[N_TEST_ARR];

int main ( int argc, char** argv )
{
   Int i, j, k, nbytes, qq;
   unsigned char* chp;
   Arena* a = &arena[VG_AR_PRIVATE];
   srandom(1);
   for (i = 0; i < N_TEST_ARR; i++)
      test_arr[i] = NULL;

   for (i = 0; i < N_TEST_TRANSACTIONS; i++) {
      if (i % 50000 == 0) mallocSanityCheck(a);
      j = random() % N_TEST_ARR;
      if (test_arr[j]) {
         vg_free(a, test_arr[j]);
         test_arr[j] = NULL;
      } else {
         nbytes = 1 + random() % M_TEST_MALLOC;
         qq = random()%64;
         if (qq == 32) 
            nbytes *= 17;
         else if (qq == 33)
            nbytes = 0;
         test_arr[j] 
           = (i % 17) == 0
                ? vg_memalign(a, nbytes, 1<< (3+(random()%10)))
                : vg_malloc( a, nbytes );
         chp = test_arr[j];
         for (k = 0; k < nbytes; k++) 
            chp[k] = (unsigned char)(k + 99);
      }
   }


   for (i = 0; i < N_TEST_ARR; i++) {
      if (test_arr[i]) {
         vg_free(a, test_arr[i]);
         test_arr[i] = NULL;
      }
   }
   mallocSanityCheck(a);

   fprintf(stderr, "ALL DONE\n");

   show_arena_stats(a);
   fprintf(stderr, "%d max useful, %d bytes mmap'd (%4.1f%%), %d useful\n",
           a->bytes_on_loan_max, 
           a->bytes_mmaped, 
	   100.0 * (double)a->bytes_on_loan_max / (double)a->bytes_mmaped,
           a->bytes_on_loan );

   return 0;
}
#endif /* 0 */


/*--------------------------------------------------------------------*/
/*--- end                                             vg_malloc2.c ---*/
/*--------------------------------------------------------------------*/