Home | History | Annotate | Download | only in coregrind
      1 
      2 /*--------------------------------------------------------------------*/
      3 /*--- An implementation of malloc/free which doesn't use sbrk.     ---*/
      4 /*---                                               m_mallocfree.c ---*/
      5 /*--------------------------------------------------------------------*/
      6 
      7 /*
      8    This file is part of Valgrind, a dynamic binary instrumentation
      9    framework.
     10 
     11    Copyright (C) 2000-2013 Julian Seward
     12       jseward (at) acm.org
     13 
     14    This program is free software; you can redistribute it and/or
     15    modify it under the terms of the GNU General Public License as
     16    published by the Free Software Foundation; either version 2 of the
     17    License, or (at your option) any later version.
     18 
     19    This program is distributed in the hope that it will be useful, but
     20    WITHOUT ANY WARRANTY; without even the implied warranty of
     21    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     22    General Public License for more details.
     23 
     24    You should have received a copy of the GNU General Public License
     25    along with this program; if not, write to the Free Software
     26    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
     27    02111-1307, USA.
     28 
     29    The GNU General Public License is contained in the file COPYING.
     30 */
     31 
     32 #include "pub_core_basics.h"
     33 #include "pub_core_vki.h"
     34 #include "pub_core_debuglog.h"
     35 #include "pub_core_libcbase.h"
     36 #include "pub_core_aspacemgr.h"
     37 #include "pub_core_libcassert.h"
     38 #include "pub_core_libcprint.h"
     39 #include "pub_core_mallocfree.h"
     40 #include "pub_core_options.h"
     41 #include "pub_core_threadstate.h"   // For VG_INVALID_THREADID
     42 #include "pub_core_gdbserver.h"
     43 #include "pub_core_transtab.h"
     44 #include "pub_core_tooliface.h"
     45 
     46 #include "pub_core_inner.h"
     47 #if defined(ENABLE_INNER_CLIENT_REQUEST)
     48 #include "memcheck/memcheck.h"
     49 #endif
     50 
     51 // #define DEBUG_MALLOC      // turn on heavyweight debugging machinery
     52 // #define VERBOSE_MALLOC    // make verbose, esp. in debugging machinery
     53 
     54 /* Number and total size of blocks in free queue. Used by mallinfo(). */
     55 Long VG_(free_queue_volume) = 0;
     56 Long VG_(free_queue_length) = 0;
     57 
     58 static void cc_analyse_alloc_arena ( ArenaId aid ); /* fwds */
     59 
     60 /*------------------------------------------------------------*/
     61 /*--- Main types                                           ---*/
     62 /*------------------------------------------------------------*/
     63 
     64 #define N_MALLOC_LISTS     112    // do not change this
     65 
     66 // The amount you can ask for is limited only by sizeof(SizeT)...
     67 #define MAX_PSZB              (~((SizeT)0x0))
     68 
     69 // Each arena has a sorted array of superblocks, which expands
     70 // dynamically.  This is its initial size.
     71 #define SBLOCKS_SIZE_INITIAL 50
     72 
     73 typedef UChar UByte;
     74 
     75 /* Layout of an in-use block:
     76 
     77       cost center (OPTIONAL)   (VG_MIN_MALLOC_SZB bytes, only when h-p enabled)
     78       this block total szB     (sizeof(SizeT) bytes)
     79       red zone bytes           (depends on Arena.rz_szB, but >= sizeof(void*))
     80       (payload bytes)
     81       red zone bytes           (depends on Arena.rz_szB, but >= sizeof(void*))
     82       this block total szB     (sizeof(SizeT) bytes)
     83 
     84    Layout of a block on the free list:
     85 
     86       cost center (OPTIONAL)   (VG_MIN_MALLOC_SZB bytes, only when h-p enabled)
     87       this block total szB     (sizeof(SizeT) bytes)
     88       freelist previous ptr    (sizeof(void*) bytes)
     89       excess red zone bytes    (if Arena.rz_szB > sizeof(void*))
     90       (payload bytes)
     91       excess red zone bytes    (if Arena.rz_szB > sizeof(void*))
     92       freelist next ptr        (sizeof(void*) bytes)
     93       this block total szB     (sizeof(SizeT) bytes)
     94 
     95    Total size in bytes (bszB) and payload size in bytes (pszB)
     96    are related by:
     97 
     98       bszB == pszB + 2*sizeof(SizeT) + 2*a->rz_szB
     99 
    100    when heap profiling is not enabled, and
    101 
    102       bszB == pszB + 2*sizeof(SizeT) + 2*a->rz_szB + VG_MIN_MALLOC_SZB
    103 
    104    when it is enabled.  It follows that the minimum overhead per heap
    105    block for arenas used by the core is:
    106 
    107       32-bit platforms:  2*4 + 2*4 == 16 bytes
    108       64-bit platforms:  2*8 + 2*8 == 32 bytes
    109 
    110    when heap profiling is not enabled, and
    111 
    112       32-bit platforms:  2*4 + 2*4 + 8  == 24 bytes
    113       64-bit platforms:  2*8 + 2*8 + 16 == 48 bytes
    114 
    115    when it is enabled.  In all cases, extra overhead may be incurred
    116    when rounding the payload size up to VG_MIN_MALLOC_SZB.
    117 
    118    Furthermore, both size fields in the block have their least-significant
    119    bit set if the block is not in use, and unset if it is in use.
    120    (The bottom 3 or so bits are always free for this because of alignment.)
    121    A block size of zero is not possible, because a block always has at
    122    least two SizeTs and two pointers of overhead.
    123 
    124    Nb: All Block payloads must be VG_MIN_MALLOC_SZB-aligned.  This is
    125    achieved by ensuring that Superblocks are VG_MIN_MALLOC_SZB-aligned
    126    (see newSuperblock() for how), and that the lengths of the following
    127    things are a multiple of VG_MIN_MALLOC_SZB:
    128    - Superblock admin section lengths (due to elastic padding)
    129    - Block admin section (low and high) lengths (due to elastic redzones)
    130    - Block payload lengths (due to req_pszB rounding up)
    131 
    132    The heap-profile cost-center field is 8 bytes even on 32 bit
    133    platforms.  This is so as to keep the payload field 8-aligned.  On
    134    a 64-bit platform, this cc-field contains a pointer to a const
    135    HChar*, which is the cost center name.  On 32-bit platforms, the
    136    pointer lives in the lower-addressed half of the field, regardless
    137    of the endianness of the host.
    138 */
    139 typedef
    140    struct {
    141       // No fields are actually used in this struct, because a Block has
    142       // many variable sized fields and so can't be accessed
    143       // meaningfully with normal fields.  So we use access functions all
    144       // the time.  This struct gives us a type to use, though.  Also, we
    145       // make sizeof(Block) 1 byte so that we can do arithmetic with the
    146       // Block* type in increments of 1!
    147       UByte dummy;
    148    }
    149    Block;
    150 
    151 // A superblock.  'padding' is never used, it just ensures that if the
    152 // entire Superblock is aligned to VG_MIN_MALLOC_SZB, then payload_bytes[]
    153 // will be too.  It can add small amounts of padding unnecessarily -- eg.
    154 // 8-bytes on 32-bit machines with an 8-byte VG_MIN_MALLOC_SZB -- because
    155 // it's too hard to make a constant expression that works perfectly in all
    156 // cases.
    157 // 'unsplittable' is set to NULL if superblock can be splitted, otherwise
    158 // it is set to the address of the superblock. An unsplittable superblock
    159 // will contain only one allocated block. An unsplittable superblock will
    160 // be unmapped when its (only) allocated block is freed.
    161 // The free space at the end of an unsplittable superblock is not used to
    162 // make a free block. Note that this means that an unsplittable superblock can
    163 // have up to slightly less than 1 page of unused bytes at the end of the
    164 // superblock.
    165 // 'unsplittable' is used to avoid quadratic memory usage for linear
    166 // reallocation of big structures
    167 // (see http://bugs.kde.org/show_bug.cgi?id=250101).
    168 // ??? unsplittable replaces 'void *padding2'. Choosed this
    169 // ??? to avoid changing the alignment logic. Maybe something cleaner
    170 // ??? can be done.
    171 // A splittable block can be reclaimed when all its blocks are freed :
    172 // the reclaim of such a block is deferred till either another superblock
    173 // of the same arena can be reclaimed or till a new superblock is needed
    174 // in any arena.
    175 // payload_bytes[] is made a single big Block when the Superblock is
    176 // created, and then can be split and the splittings remerged, but Blocks
    177 // always cover its entire length -- there's never any unused bytes at the
    178 // end, for example.
    179 typedef
    180    struct _Superblock {
    181       SizeT n_payload_bytes;
    182       struct _Superblock* unsplittable;
    183       UByte padding[ VG_MIN_MALLOC_SZB -
    184                         ((sizeof(struct _Superblock*) + sizeof(SizeT)) %
    185                          VG_MIN_MALLOC_SZB) ];
    186       UByte payload_bytes[0];
    187    }
    188    Superblock;
    189 
    190 // An arena. 'freelist' is a circular, doubly-linked list.  'rz_szB' is
    191 // elastic, in that it can be bigger than asked-for to ensure alignment.
    192 typedef
    193    struct {
    194       const HChar* name;
    195       Bool         clientmem;        // Allocates in the client address space?
    196       SizeT        rz_szB;           // Red zone size in bytes
    197       SizeT        min_sblock_szB;   // Minimum superblock size in bytes
    198       SizeT        min_unsplittable_sblock_szB;
    199       // Minimum unsplittable superblock size in bytes. To be marked as
    200       // unsplittable, a superblock must have a
    201       // size >= min_unsplittable_sblock_szB and cannot be splitted.
    202       // So, to avoid big overhead, superblocks used to provide aligned
    203       // blocks on big alignments are splittable.
    204       // Unsplittable superblocks will be reclaimed when their (only)
    205       // allocated block is freed.
    206       // Smaller size superblocks are splittable and can be reclaimed when all
    207       // their blocks are freed.
    208       Block*       freelist[N_MALLOC_LISTS];
    209       // A dynamically expanding, ordered array of (pointers to)
    210       // superblocks in the arena.  If this array is expanded, which
    211       // is rare, the previous space it occupies is simply abandoned.
    212       // To avoid having to get yet another block from m_aspacemgr for
    213       // the first incarnation of this array, the first allocation of
    214       // it is within this struct.  If it has to be expanded then the
    215       // new space is acquired from m_aspacemgr as you would expect.
    216       Superblock** sblocks;
    217       SizeT        sblocks_size;
    218       SizeT        sblocks_used;
    219       Superblock*  sblocks_initial[SBLOCKS_SIZE_INITIAL];
    220       Superblock*  deferred_reclaimed_sb;
    221 
    222       // VG_(arena_perm_malloc) returns memory from superblocks
    223       // only used for permanent blocks. No overhead. These superblocks
    224       // are not stored in sblocks array above.
    225       Addr         perm_malloc_current; // first byte free in perm_malloc sb.
    226       Addr         perm_malloc_limit; // maximum usable byte in perm_malloc sb.
    227 
    228       // Stats only
    229       SizeT        stats__perm_bytes_on_loan;
    230       SizeT        stats__perm_blocks;
    231 
    232       ULong        stats__nreclaim_unsplit;
    233       ULong        stats__nreclaim_split;
    234       /* total # of reclaim executed for unsplittable/splittable superblocks */
    235       SizeT        stats__bytes_on_loan;
    236       SizeT        stats__bytes_mmaped;
    237       SizeT        stats__bytes_on_loan_max;
    238       ULong        stats__tot_blocks; /* total # blocks alloc'd */
    239       ULong        stats__tot_bytes; /* total # bytes alloc'd */
    240       ULong        stats__nsearches; /* total # freelist checks */
    241       // If profiling, when should the next profile happen at
    242       // (in terms of stats__bytes_on_loan_max) ?
    243       SizeT        next_profile_at;
    244       SizeT        stats__bytes_mmaped_max;
    245    }
    246    Arena;
    247 
    248 
    249 /*------------------------------------------------------------*/
    250 /*--- Low-level functions for working with Blocks.         ---*/
    251 /*------------------------------------------------------------*/
    252 
    253 #define SIZE_T_0x1      ((SizeT)0x1)
    254 
    255 static const char* probably_your_fault =
    256    "This is probably caused by your program erroneously writing past the\n"
    257    "end of a heap block and corrupting heap metadata.  If you fix any\n"
    258    "invalid writes reported by Memcheck, this assertion failure will\n"
    259    "probably go away.  Please try that before reporting this as a bug.\n";
    260 
    261 // Mark a bszB as in-use, and not in-use, and remove the in-use attribute.
    262 static __inline__
    263 SizeT mk_inuse_bszB ( SizeT bszB )
    264 {
    265    vg_assert2(bszB != 0, probably_your_fault);
    266    return bszB & (~SIZE_T_0x1);
    267 }
    268 static __inline__
    269 SizeT mk_free_bszB ( SizeT bszB )
    270 {
    271    vg_assert2(bszB != 0, probably_your_fault);
    272    return bszB | SIZE_T_0x1;
    273 }
    274 static __inline__
    275 SizeT mk_plain_bszB ( SizeT bszB )
    276 {
    277    vg_assert2(bszB != 0, probably_your_fault);
    278    return bszB & (~SIZE_T_0x1);
    279 }
    280 
    281 // Forward definition.
    282 static
    283 void ensure_mm_init ( ArenaId aid );
    284 
    285 // return either 0 or sizeof(ULong) depending on whether or not
    286 // heap profiling is engaged
    287 #define hp_overhead_szB() set_at_init_hp_overhead_szB
    288 static SizeT set_at_init_hp_overhead_szB = -1000000;
    289 // startup value chosen to very likely cause a problem if used before
    290 // a proper value is given by ensure_mm_init.
    291 
    292 //---------------------------------------------------------------------------
    293 
    294 // Get a block's size as stored, ie with the in-use/free attribute.
    295 static __inline__
    296 SizeT get_bszB_as_is ( Block* b )
    297 {
    298    UByte* b2     = (UByte*)b;
    299    SizeT bszB_lo = *(SizeT*)&b2[0 + hp_overhead_szB()];
    300    SizeT bszB_hi = *(SizeT*)&b2[mk_plain_bszB(bszB_lo) - sizeof(SizeT)];
    301    vg_assert2(bszB_lo == bszB_hi,
    302       "Heap block lo/hi size mismatch: lo = %llu, hi = %llu.\n%s",
    303       (ULong)bszB_lo, (ULong)bszB_hi, probably_your_fault);
    304    return bszB_lo;
    305 }
    306 
    307 // Get a block's plain size, ie. remove the in-use/free attribute.
    308 static __inline__
    309 SizeT get_bszB ( Block* b )
    310 {
    311    return mk_plain_bszB(get_bszB_as_is(b));
    312 }
    313 
    314 // Set the size fields of a block.  bszB may have the in-use/free attribute.
    315 static __inline__
    316 void set_bszB ( Block* b, SizeT bszB )
    317 {
    318    UByte* b2 = (UByte*)b;
    319    *(SizeT*)&b2[0 + hp_overhead_szB()]               = bszB;
    320    *(SizeT*)&b2[mk_plain_bszB(bszB) - sizeof(SizeT)] = bszB;
    321 }
    322 
    323 //---------------------------------------------------------------------------
    324 
    325 // Does this block have the in-use attribute?
    326 static __inline__
    327 Bool is_inuse_block ( Block* b )
    328 {
    329    SizeT bszB = get_bszB_as_is(b);
    330    vg_assert2(bszB != 0, probably_your_fault);
    331    return (0 != (bszB & SIZE_T_0x1)) ? False : True;
    332 }
    333 
    334 //---------------------------------------------------------------------------
    335 
    336 // Return the lower, upper and total overhead in bytes for a block.
    337 // These are determined purely by which arena the block lives in.
    338 static __inline__
    339 SizeT overhead_szB_lo ( Arena* a )
    340 {
    341    return hp_overhead_szB() + sizeof(SizeT) + a->rz_szB;
    342 }
    343 static __inline__
    344 SizeT overhead_szB_hi ( Arena* a )
    345 {
    346    return a->rz_szB + sizeof(SizeT);
    347 }
    348 static __inline__
    349 SizeT overhead_szB ( Arena* a )
    350 {
    351    return overhead_szB_lo(a) + overhead_szB_hi(a);
    352 }
    353 
    354 //---------------------------------------------------------------------------
    355 
    356 // Return the minimum bszB for a block in this arena.  Can have zero-length
    357 // payloads, so it's the size of the admin bytes.
    358 static __inline__
    359 SizeT min_useful_bszB ( Arena* a )
    360 {
    361    return overhead_szB(a);
    362 }
    363 
    364 //---------------------------------------------------------------------------
    365 
    366 // Convert payload size <--> block size (both in bytes).
    367 static __inline__
    368 SizeT pszB_to_bszB ( Arena* a, SizeT pszB )
    369 {
    370    return pszB + overhead_szB(a);
    371 }
    372 static __inline__
    373 SizeT bszB_to_pszB ( Arena* a, SizeT bszB )
    374 {
    375    vg_assert2(bszB >= overhead_szB(a), probably_your_fault);
    376    return bszB - overhead_szB(a);
    377 }
    378 
    379 //---------------------------------------------------------------------------
    380 
    381 // Get a block's payload size.
    382 static __inline__
    383 SizeT get_pszB ( Arena* a, Block* b )
    384 {
    385    return bszB_to_pszB(a, get_bszB(b));
    386 }
    387 
    388 //---------------------------------------------------------------------------
    389 
    390 // Given the addr of a block, return the addr of its payload, and vice versa.
    391 static __inline__
    392 UByte* get_block_payload ( Arena* a, Block* b )
    393 {
    394    UByte* b2 = (UByte*)b;
    395    return & b2[ overhead_szB_lo(a) ];
    396 }
    397 // Given the addr of a block's payload, return the addr of the block itself.
    398 static __inline__
    399 Block* get_payload_block ( Arena* a, UByte* payload )
    400 {
    401    return (Block*)&payload[ -overhead_szB_lo(a) ];
    402 }
    403 
    404 //---------------------------------------------------------------------------
    405 
    406 // Set and get the next and previous link fields of a block.
    407 static __inline__
    408 void set_prev_b ( Block* b, Block* prev_p )
    409 {
    410    UByte* b2 = (UByte*)b;
    411    *(Block**)&b2[hp_overhead_szB() + sizeof(SizeT)] = prev_p;
    412 }
    413 static __inline__
    414 void set_next_b ( Block* b, Block* next_p )
    415 {
    416    UByte* b2 = (UByte*)b;
    417    *(Block**)&b2[get_bszB(b) - sizeof(SizeT) - sizeof(void*)] = next_p;
    418 }
    419 static __inline__
    420 Block* get_prev_b ( Block* b )
    421 {
    422    UByte* b2 = (UByte*)b;
    423    return *(Block**)&b2[hp_overhead_szB() + sizeof(SizeT)];
    424 }
    425 static __inline__
    426 Block* get_next_b ( Block* b )
    427 {
    428    UByte* b2 = (UByte*)b;
    429    return *(Block**)&b2[get_bszB(b) - sizeof(SizeT) - sizeof(void*)];
    430 }
    431 
    432 //---------------------------------------------------------------------------
    433 
    434 // Set and get the cost-center field of a block.
    435 static __inline__
    436 void set_cc ( Block* b, const HChar* cc )
    437 {
    438    UByte* b2 = (UByte*)b;
    439    vg_assert( VG_(clo_profile_heap) );
    440    *(const HChar**)&b2[0] = cc;
    441 }
    442 static __inline__
    443 const HChar* get_cc ( Block* b )
    444 {
    445    UByte* b2 = (UByte*)b;
    446    vg_assert( VG_(clo_profile_heap) );
    447    return *(const HChar**)&b2[0];
    448 }
    449 
    450 //---------------------------------------------------------------------------
    451 
    452 // Get the block immediately preceding this one in the Superblock.
    453 static __inline__
    454 Block* get_predecessor_block ( Block* b )
    455 {
    456    UByte* b2 = (UByte*)b;
    457    SizeT  bszB = mk_plain_bszB( (*(SizeT*)&b2[-sizeof(SizeT)]) );
    458    return (Block*)&b2[-bszB];
    459 }
    460 
    461 //---------------------------------------------------------------------------
    462 
    463 // Read and write the lower and upper red-zone bytes of a block.
    464 static __inline__
    465 void set_rz_lo_byte ( Block* b, UInt rz_byteno, UByte v )
    466 {
    467    UByte* b2 = (UByte*)b;
    468    b2[hp_overhead_szB() + sizeof(SizeT) + rz_byteno] = v;
    469 }
    470 static __inline__
    471 void set_rz_hi_byte ( Block* b, UInt rz_byteno, UByte v )
    472 {
    473    UByte* b2 = (UByte*)b;
    474    b2[get_bszB(b) - sizeof(SizeT) - rz_byteno - 1] = v;
    475 }
    476 static __inline__
    477 UByte get_rz_lo_byte ( Block* b, UInt rz_byteno )
    478 {
    479    UByte* b2 = (UByte*)b;
    480    return b2[hp_overhead_szB() + sizeof(SizeT) + rz_byteno];
    481 }
    482 static __inline__
    483 UByte get_rz_hi_byte ( Block* b, UInt rz_byteno )
    484 {
    485    UByte* b2 = (UByte*)b;
    486    return b2[get_bszB(b) - sizeof(SizeT) - rz_byteno - 1];
    487 }
    488 
    489 #if defined(ENABLE_INNER_CLIENT_REQUEST)
    490 /* When running as an inner, the block headers before and after
    491    (see 'Layout of an in-use block:' above) are made non accessible
    492    by VALGRIND_MALLOCLIKE_BLOCK/VALGRIND_FREELIKE_BLOCK
    493    to allow the outer to detect block overrun.
    494    The below two functions are used when these headers must be
    495    temporarily accessed. */
    496 static void mkBhdrAccess( Arena* a, Block* b )
    497 {
    498    VALGRIND_MAKE_MEM_DEFINED (b,
    499                               hp_overhead_szB() + sizeof(SizeT) + a->rz_szB);
    500    VALGRIND_MAKE_MEM_DEFINED (b + get_bszB(b) - a->rz_szB - sizeof(SizeT),
    501                               a->rz_szB + sizeof(SizeT));
    502 }
    503 
    504 /* Mark block hdr as not accessible.
    505    !!! Currently, we do not mark the cost center and szB fields unaccessible
    506    as these are accessed at too many places. */
    507 static void mkBhdrNoAccess( Arena* a, Block* b )
    508 {
    509    VALGRIND_MAKE_MEM_NOACCESS (b + hp_overhead_szB() + sizeof(SizeT),
    510                                a->rz_szB);
    511    VALGRIND_MAKE_MEM_NOACCESS (b + get_bszB(b) - sizeof(SizeT) - a->rz_szB,
    512                                a->rz_szB);
    513 }
    514 
    515 /* Make the cc+szB fields accessible. */
    516 static void mkBhdrSzAccess( Arena* a, Block* b )
    517 {
    518    VALGRIND_MAKE_MEM_DEFINED (b,
    519                               hp_overhead_szB() + sizeof(SizeT));
    520    /* We cannot use  get_bszB(b), as this reads the 'hi' szB we want
    521       to mark accessible. So, we only access the 'lo' szB. */
    522    SizeT bszB_lo = mk_plain_bszB(*(SizeT*)&b[0 + hp_overhead_szB()]);
    523    VALGRIND_MAKE_MEM_DEFINED (b + bszB_lo - sizeof(SizeT),
    524                               sizeof(SizeT));
    525 }
    526 #endif
    527 
    528 /*------------------------------------------------------------*/
    529 /*--- Arena management                                     ---*/
    530 /*------------------------------------------------------------*/
    531 
    532 #define CORE_ARENA_MIN_SZB    1048576
    533 
    534 // The arena structures themselves.
    535 static Arena vg_arena[VG_N_ARENAS];
    536 
    537 // Functions external to this module identify arenas using ArenaIds,
    538 // not Arena*s.  This fn converts the former to the latter.
    539 static Arena* arenaId_to_ArenaP ( ArenaId arena )
    540 {
    541    vg_assert(arena >= 0 && arena < VG_N_ARENAS);
    542    return & vg_arena[arena];
    543 }
    544 
    545 static ArenaId arenaP_to_ArenaId ( Arena *a )
    546 {
    547    ArenaId arena = a -vg_arena;
    548    vg_assert(arena >= 0 && arena < VG_N_ARENAS);
    549    return arena;
    550 }
    551 
    552 // Initialise an arena.  rz_szB is the (default) minimum redzone size;
    553 // It might be overriden by VG_(clo_redzone_size) or VG_(clo_core_redzone_size).
    554 // it might be made bigger to ensure that VG_MIN_MALLOC_SZB is observed.
    555 static
    556 void arena_init ( ArenaId aid, const HChar* name, SizeT rz_szB,
    557                   SizeT min_sblock_szB, SizeT min_unsplittable_sblock_szB )
    558 {
    559    SizeT  i;
    560    Arena* a = arenaId_to_ArenaP(aid);
    561 
    562    // Ensure default redzones are a reasonable size.
    563    vg_assert(rz_szB <= MAX_REDZONE_SZB);
    564 
    565    /* Override the default redzone size if a clo value was given.
    566       Note that the clo value can be significantly bigger than MAX_REDZONE_SZB
    567       to allow the user to chase horrible bugs using up to 1 page
    568       of protection. */
    569    if (VG_AR_CLIENT == aid) {
    570       if (VG_(clo_redzone_size) != -1)
    571          rz_szB = VG_(clo_redzone_size);
    572    } else {
    573       if (VG_(clo_core_redzone_size) != rz_szB)
    574          rz_szB = VG_(clo_core_redzone_size);
    575    }
    576 
    577    // Redzones must always be at least the size of a pointer, for holding the
    578    // prev/next pointer (see the layout details at the top of this file).
    579    if (rz_szB < sizeof(void*)) rz_szB = sizeof(void*);
    580 
    581    // The size of the low and high admin sections in a block must be a
    582    // multiple of VG_MIN_MALLOC_SZB.  So we round up the asked-for
    583    // redzone size if necessary to achieve this.
    584    a->rz_szB = rz_szB;
    585    while (0 != overhead_szB_lo(a) % VG_MIN_MALLOC_SZB) a->rz_szB++;
    586    vg_assert(overhead_szB_lo(a) - hp_overhead_szB() == overhead_szB_hi(a));
    587 
    588    // Here we have established the effective redzone size.
    589 
    590 
    591    vg_assert((min_sblock_szB % VKI_PAGE_SIZE) == 0);
    592    a->name      = name;
    593    a->clientmem = ( VG_AR_CLIENT == aid ? True : False );
    594 
    595    a->min_sblock_szB = min_sblock_szB;
    596    a->min_unsplittable_sblock_szB = min_unsplittable_sblock_szB;
    597    for (i = 0; i < N_MALLOC_LISTS; i++) a->freelist[i] = NULL;
    598 
    599    a->sblocks                  = & a->sblocks_initial[0];
    600    a->sblocks_size             = SBLOCKS_SIZE_INITIAL;
    601    a->sblocks_used             = 0;
    602    a->deferred_reclaimed_sb    = 0;
    603    a->perm_malloc_current      = 0;
    604    a->perm_malloc_limit        = 0;
    605    a->stats__perm_bytes_on_loan= 0;
    606    a->stats__perm_blocks       = 0;
    607    a->stats__nreclaim_unsplit  = 0;
    608    a->stats__nreclaim_split    = 0;
    609    a->stats__bytes_on_loan     = 0;
    610    a->stats__bytes_mmaped      = 0;
    611    a->stats__bytes_on_loan_max = 0;
    612    a->stats__bytes_mmaped_max  = 0;
    613    a->stats__tot_blocks        = 0;
    614    a->stats__tot_bytes         = 0;
    615    a->stats__nsearches         = 0;
    616    a->next_profile_at          = 25 * 1000 * 1000;
    617    vg_assert(sizeof(a->sblocks_initial)
    618              == SBLOCKS_SIZE_INITIAL * sizeof(Superblock*));
    619 }
    620 
    621 /* Print vital stats for an arena. */
    622 void VG_(print_all_arena_stats) ( void )
    623 {
    624    UInt i;
    625    for (i = 0; i < VG_N_ARENAS; i++) {
    626       Arena* a = arenaId_to_ArenaP(i);
    627       VG_(message)(Vg_DebugMsg,
    628                    "%-8s: %'13lu/%'13lu max/curr mmap'd, "
    629                    "%llu/%llu unsplit/split sb unmmap'd,  "
    630                    "%'13lu/%'13lu max/curr,  "
    631                    "%10llu/%10llu totalloc-blocks/bytes,"
    632                    "  %10llu searches %lu rzB\n",
    633                    a->name,
    634                    a->stats__bytes_mmaped_max, a->stats__bytes_mmaped,
    635                    a->stats__nreclaim_unsplit, a->stats__nreclaim_split,
    636                    a->stats__bytes_on_loan_max,
    637                    a->stats__bytes_on_loan,
    638                    a->stats__tot_blocks, a->stats__tot_bytes,
    639                    a->stats__nsearches,
    640                    a->rz_szB
    641       );
    642    }
    643 }
    644 
    645 void VG_(print_arena_cc_analysis) ( void )
    646 {
    647    UInt i;
    648    vg_assert( VG_(clo_profile_heap) );
    649    for (i = 0; i < VG_N_ARENAS; i++) {
    650       cc_analyse_alloc_arena(i);
    651    }
    652 }
    653 
    654 
    655 /* This library is self-initialising, as it makes this more self-contained,
    656    less coupled with the outside world.  Hence VG_(arena_malloc)() and
    657    VG_(arena_free)() below always call ensure_mm_init() to ensure things are
    658    correctly initialised.
    659 
    660    We initialise the client arena separately (and later) because the core
    661    must do non-client allocation before the tool has a chance to set the
    662    client arena's redzone size.
    663 */
    664 static Bool     client_inited = False;
    665 static Bool  nonclient_inited = False;
    666 
    667 static
    668 void ensure_mm_init ( ArenaId aid )
    669 {
    670    static SizeT client_rz_szB = 8;     // default: be paranoid
    671 
    672    /* We use checked red zones (of various sizes) for our internal stuff,
    673       and an unchecked zone of arbitrary size for the client.  Of
    674       course the client's red zone can be checked by the tool, eg.
    675       by using addressibility maps, but not by the mechanism implemented
    676       here, which merely checks at the time of freeing that the red
    677       zone bytes are unchanged.
    678 
    679       Nb: redzone sizes are *minimums*;  they could be made bigger to ensure
    680       alignment.  Eg. with 8 byte alignment, on 32-bit machines 4 stays as
    681       4, but 16 becomes 20;  but on 64-bit machines 4 becomes 8, and 16
    682       stays as 16 --- the extra 4 bytes in both are accounted for by the
    683       larger prev/next ptr.
    684    */
    685    if (VG_AR_CLIENT == aid) {
    686       Int ar_client_sbszB;
    687       if (client_inited) {
    688          // This assertion ensures that a tool cannot try to change the client
    689          // redzone size with VG_(needs_malloc_replacement)() after this module
    690          // has done its first allocation from the client arena.
    691          if (VG_(needs).malloc_replacement)
    692             vg_assert(client_rz_szB == VG_(tdict).tool_client_redzone_szB);
    693          return;
    694       }
    695 
    696       // Check and set the client arena redzone size
    697       if (VG_(needs).malloc_replacement) {
    698          client_rz_szB = VG_(tdict).tool_client_redzone_szB;
    699          if (client_rz_szB > MAX_REDZONE_SZB) {
    700             VG_(printf)( "\nTool error:\n"
    701                          "  specified redzone size is too big (%llu)\n",
    702                          (ULong)client_rz_szB);
    703             VG_(exit)(1);
    704          }
    705       }
    706       // Initialise the client arena.  On all platforms,
    707       // increasing the superblock size reduces the number of superblocks
    708       // in the client arena, which makes findSb cheaper.
    709       ar_client_sbszB = 4194304;
    710       // superblocks with a size > ar_client_sbszB will be unsplittable
    711       // (unless used for providing memalign-ed blocks).
    712       arena_init ( VG_AR_CLIENT,    "client",   client_rz_szB,
    713                    ar_client_sbszB, ar_client_sbszB+1);
    714       client_inited = True;
    715 
    716    } else {
    717       if (nonclient_inited) {
    718          return;
    719       }
    720       set_at_init_hp_overhead_szB =
    721          VG_(clo_profile_heap)  ? VG_MIN_MALLOC_SZB  : 0;
    722       // Initialise the non-client arenas
    723       // Similarly to client arena, big allocations will be unsplittable.
    724       arena_init ( VG_AR_CORE,      "core",     CORE_REDZONE_DEFAULT_SZB,
    725                    4194304, 4194304+1 );
    726       arena_init ( VG_AR_DINFO,     "dinfo",    CORE_REDZONE_DEFAULT_SZB,
    727                    1048576, 1048576+1 );
    728       arena_init ( VG_AR_DEMANGLE,  "demangle", CORE_REDZONE_DEFAULT_SZB,
    729                    65536,   65536+1 );
    730       arena_init ( VG_AR_TTAUX,     "ttaux",    CORE_REDZONE_DEFAULT_SZB,
    731                    65536,   65536+1 );
    732       nonclient_inited = True;
    733    }
    734 
    735 #  ifdef DEBUG_MALLOC
    736    VG_(printf)("ZZZ1\n");
    737    VG_(sanity_check_malloc_all)();
    738    VG_(printf)("ZZZ2\n");
    739 #  endif
    740 }
    741 
    742 
    743 /*------------------------------------------------------------*/
    744 /*--- Superblock management                                ---*/
    745 /*------------------------------------------------------------*/
    746 
    747 __attribute__((noreturn))
    748 void VG_(out_of_memory_NORETURN) ( const HChar* who, SizeT szB )
    749 {
    750    static Int outputTrial = 0;
    751    // We try once to output the full memory state followed by the below message.
    752    // If that fails (due to out of memory during first trial), we try to just
    753    // output the below message.
    754    // And then we abandon.
    755 
    756    ULong tot_alloc = VG_(am_get_anonsize_total)();
    757    const HChar* s1 =
    758       "\n"
    759       "    Valgrind's memory management: out of memory:\n"
    760       "       %s's request for %llu bytes failed.\n"
    761       "       %'13llu bytes have already been mmap-ed ANONYMOUS.\n"
    762       "    Valgrind cannot continue.  Sorry.\n\n"
    763       "    There are several possible reasons for this.\n"
    764       "    - You have some kind of memory limit in place.  Look at the\n"
    765       "      output of 'ulimit -a'.  Is there a limit on the size of\n"
    766       "      virtual memory or address space?\n"
    767       "    - You have run out of swap space.\n"
    768       "    - Valgrind has a bug.  If you think this is the case or you are\n"
    769       "    not sure, please let us know and we'll try to fix it.\n"
    770       "    Please note that programs can take substantially more memory than\n"
    771       "    normal when running under Valgrind tools, eg. up to twice or\n"
    772       "    more, depending on the tool.  On a 64-bit machine, Valgrind\n"
    773       "    should be able to make use of up 32GB memory.  On a 32-bit\n"
    774       "    machine, Valgrind should be able to use all the memory available\n"
    775       "    to a single process, up to 4GB if that's how you have your\n"
    776       "    kernel configured.  Most 32-bit Linux setups allow a maximum of\n"
    777       "    3GB per process.\n\n"
    778       "    Whatever the reason, Valgrind cannot continue.  Sorry.\n";
    779 
    780    if (outputTrial <= 1) {
    781       if (outputTrial == 0) {
    782          outputTrial++;
    783          // First print the memory stats with the aspacemgr data.
    784          VG_(am_show_nsegments) (0, "out_of_memory");
    785          VG_(print_all_arena_stats) ();
    786          if (VG_(clo_profile_heap))
    787             VG_(print_arena_cc_analysis) ();
    788          // And then print some other information that might help.
    789          VG_(print_all_stats) (False, /* Memory stats */
    790                                True /* Tool stats */);
    791          VG_(show_sched_status) (True,  // host_stacktrace
    792                                  True,  // valgrind_stack_usage
    793                                  True); // exited_threads
    794         /* In case we are an inner valgrind, asks the outer to report
    795             its memory state in its log output. */
    796          INNER_REQUEST(VALGRIND_MONITOR_COMMAND("v.set log_output"));
    797          INNER_REQUEST(VALGRIND_MONITOR_COMMAND("v.info memory aspacemgr"));
    798       }
    799       outputTrial++;
    800       VG_(message)(Vg_UserMsg, s1, who, (ULong)szB, tot_alloc);
    801    } else {
    802       VG_(debugLog)(0,"mallocfree", s1, who, (ULong)szB, tot_alloc);
    803    }
    804 
    805    VG_(exit)(1);
    806 }
    807 
    808 
    809 // Align ptr p upwards to an align-sized boundary.
    810 static
    811 void* align_upwards ( void* p, SizeT align )
    812 {
    813    Addr a = (Addr)p;
    814    if ((a % align) == 0) return (void*)a;
    815    return (void*)(a - (a % align) + align);
    816 }
    817 
    818 // Forward definition.
    819 static
    820 void deferred_reclaimSuperblock ( Arena* a, Superblock* sb);
    821 
    822 // If not enough memory available, either aborts (for non-client memory)
    823 // or returns 0 (for client memory).
    824 static
    825 Superblock* newSuperblock ( Arena* a, SizeT cszB )
    826 {
    827    Superblock* sb;
    828    SysRes      sres;
    829    Bool        unsplittable;
    830    ArenaId     aid;
    831 
    832    // A new superblock is needed for arena a. We will execute the deferred
    833    // reclaim in all arenas in order to minimise fragmentation and
    834    // peak memory usage.
    835    for (aid = 0; aid < VG_N_ARENAS; aid++) {
    836       Arena* arena = arenaId_to_ArenaP(aid);
    837       if (arena->deferred_reclaimed_sb != NULL)
    838          deferred_reclaimSuperblock (arena, NULL);
    839    }
    840 
    841    // Take into account admin bytes in the Superblock.
    842    cszB += sizeof(Superblock);
    843 
    844    if (cszB < a->min_sblock_szB) cszB = a->min_sblock_szB;
    845    cszB = VG_PGROUNDUP(cszB);
    846 
    847    if (cszB >= a->min_unsplittable_sblock_szB)
    848       unsplittable = True;
    849    else
    850       unsplittable = False;
    851 
    852 
    853    if (a->clientmem) {
    854       // client allocation -- return 0 to client if it fails
    855       sres = VG_(am_mmap_client_heap)
    856          ( cszB, VKI_PROT_READ|VKI_PROT_WRITE|VKI_PROT_EXEC );
    857       if (sr_isError(sres))
    858          return 0;
    859       sb = (Superblock*)(Addr)sr_Res(sres);
    860    } else {
    861       // non-client allocation -- abort if it fails
    862       sres = VG_(am_mmap_anon_float_valgrind)( cszB );
    863       if (sr_isError(sres)) {
    864          VG_(out_of_memory_NORETURN)("newSuperblock", cszB);
    865          /* NOTREACHED */
    866          sb = NULL; /* keep gcc happy */
    867       } else {
    868          sb = (Superblock*)(Addr)sr_Res(sres);
    869       }
    870    }
    871    vg_assert(NULL != sb);
    872    INNER_REQUEST(VALGRIND_MAKE_MEM_UNDEFINED(sb, cszB));
    873    vg_assert(0 == (Addr)sb % VG_MIN_MALLOC_SZB);
    874    sb->n_payload_bytes = cszB - sizeof(Superblock);
    875    sb->unsplittable = (unsplittable ? sb : NULL);
    876    a->stats__bytes_mmaped += cszB;
    877    if (a->stats__bytes_mmaped > a->stats__bytes_mmaped_max)
    878       a->stats__bytes_mmaped_max = a->stats__bytes_mmaped;
    879    VG_(debugLog)(1, "mallocfree",
    880                     "newSuperblock at %p (pszB %7ld) %s owner %s/%s\n",
    881                     sb, sb->n_payload_bytes,
    882                     (unsplittable ? "unsplittable" : ""),
    883                     a->clientmem ? "CLIENT" : "VALGRIND", a->name );
    884    return sb;
    885 }
    886 
    887 // Reclaims the given superblock:
    888 //  * removes sb from arena sblocks list.
    889 //  * munmap the superblock segment.
    890 static
    891 void reclaimSuperblock ( Arena* a, Superblock* sb)
    892 {
    893    SysRes sres;
    894    SizeT  cszB;
    895    UInt   i, j;
    896 
    897    VG_(debugLog)(1, "mallocfree",
    898                     "reclaimSuperblock at %p (pszB %7ld) %s owner %s/%s\n",
    899                     sb, sb->n_payload_bytes,
    900                     (sb->unsplittable ? "unsplittable" : ""),
    901                     a->clientmem ? "CLIENT" : "VALGRIND", a->name );
    902 
    903    // Take into account admin bytes in the Superblock.
    904    cszB = sizeof(Superblock) + sb->n_payload_bytes;
    905 
    906    // removes sb from superblock list.
    907    for (i = 0; i < a->sblocks_used; i++) {
    908       if (a->sblocks[i] == sb)
    909          break;
    910    }
    911    vg_assert(i >= 0 && i < a->sblocks_used);
    912    for (j = i; j < a->sblocks_used; j++)
    913       a->sblocks[j] = a->sblocks[j+1];
    914    a->sblocks_used--;
    915    a->sblocks[a->sblocks_used] = NULL;
    916    // paranoia: NULLify ptr to reclaimed sb or NULLify copy of ptr to last sb.
    917 
    918    a->stats__bytes_mmaped -= cszB;
    919    if (sb->unsplittable)
    920       a->stats__nreclaim_unsplit++;
    921    else
    922       a->stats__nreclaim_split++;
    923 
    924    // Now that the sb is removed from the list, mnumap its space.
    925    if (a->clientmem) {
    926       // reclaimable client allocation
    927       Bool need_discard = False;
    928       sres = VG_(am_munmap_client)(&need_discard, (Addr) sb, cszB);
    929       vg_assert2(! sr_isError(sres), "superblock client munmap failure\n");
    930       /* We somewhat help the client by discarding the range.
    931          Note however that if the client has JITted some code in
    932          a small block that was freed, we do not provide this
    933          'discard support' */
    934       /* JRS 2011-Sept-26: it would be nice to move the discard
    935          outwards somewhat (in terms of calls) so as to make it easier
    936          to verify that there will be no nonterminating recursive set
    937          of calls a result of calling VG_(discard_translations).
    938          Another day, perhaps. */
    939       if (need_discard)
    940          VG_(discard_translations) ((Addr) sb, cszB, "reclaimSuperblock");
    941    } else {
    942       // reclaimable non-client allocation
    943       sres = VG_(am_munmap_valgrind)((Addr) sb, cszB);
    944       vg_assert2(! sr_isError(sres), "superblock valgrind munmap failure\n");
    945    }
    946 
    947 }
    948 
    949 // Find the superblock containing the given chunk.
    950 static
    951 Superblock* findSb ( Arena* a, Block* b )
    952 {
    953    SizeT min = 0;
    954    SizeT max = a->sblocks_used;
    955 
    956    while (min <= max) {
    957       Superblock * sb;
    958       SizeT pos = min + (max - min)/2;
    959 
    960       vg_assert(pos >= 0 && pos < a->sblocks_used);
    961       sb = a->sblocks[pos];
    962       if ((Block*)&sb->payload_bytes[0] <= b
    963           && b < (Block*)&sb->payload_bytes[sb->n_payload_bytes])
    964       {
    965          return sb;
    966       } else if ((Block*)&sb->payload_bytes[0] <= b) {
    967          min = pos + 1;
    968       } else {
    969          max = pos - 1;
    970       }
    971    }
    972    VG_(printf)("findSb: can't find pointer %p in arena '%s'\n",
    973                 b, a->name );
    974    VG_(core_panic)("findSb: VG_(arena_free)() in wrong arena?");
    975    return NULL; /*NOTREACHED*/
    976 }
    977 
    978 
    979 // Find the superblock containing the given address.
    980 // If superblock not found, return NULL.
    981 static
    982 Superblock* maybe_findSb ( Arena* a, Addr ad )
    983 {
    984    SizeT min = 0;
    985    SizeT max = a->sblocks_used;
    986 
    987    while (min <= max) {
    988       Superblock * sb;
    989       SizeT pos = min + (max - min)/2;
    990       if (pos < 0 || pos >= a->sblocks_used)
    991          return NULL;
    992       sb = a->sblocks[pos];
    993       if ((Addr)&sb->payload_bytes[0] <= ad
    994           && ad < (Addr)&sb->payload_bytes[sb->n_payload_bytes]) {
    995          return sb;
    996       } else if ((Addr)&sb->payload_bytes[0] <= ad) {
    997          min = pos + 1;
    998       } else {
    999          max = pos - 1;
   1000       }
   1001    }
   1002    return NULL;
   1003 }
   1004 
   1005 
   1006 /*------------------------------------------------------------*/
   1007 /*--- Functions for working with freelists.                ---*/
   1008 /*------------------------------------------------------------*/
   1009 
   1010 // Nb: Determination of which freelist a block lives on is based on the
   1011 // payload size, not block size.
   1012 
   1013 // Convert a payload size in bytes to a freelist number.
   1014 static
   1015 UInt pszB_to_listNo ( SizeT pszB )
   1016 {
   1017    SizeT n = pszB / VG_MIN_MALLOC_SZB;
   1018    vg_assert(0 == pszB % VG_MIN_MALLOC_SZB);
   1019 
   1020    // The first 64 lists hold blocks of size VG_MIN_MALLOC_SZB * list_num.
   1021    // The final 48 hold bigger blocks.
   1022    if (n < 64)   return (UInt)n;
   1023    /* Exponential slope up, factor 1.05 */
   1024    if (n < 67) return 64;
   1025    if (n < 70) return 65;
   1026    if (n < 74) return 66;
   1027    if (n < 77) return 67;
   1028    if (n < 81) return 68;
   1029    if (n < 85) return 69;
   1030    if (n < 90) return 70;
   1031    if (n < 94) return 71;
   1032    if (n < 99) return 72;
   1033    if (n < 104) return 73;
   1034    if (n < 109) return 74;
   1035    if (n < 114) return 75;
   1036    if (n < 120) return 76;
   1037    if (n < 126) return 77;
   1038    if (n < 133) return 78;
   1039    if (n < 139) return 79;
   1040    /* Exponential slope up, factor 1.10 */
   1041    if (n < 153) return 80;
   1042    if (n < 169) return 81;
   1043    if (n < 185) return 82;
   1044    if (n < 204) return 83;
   1045    if (n < 224) return 84;
   1046    if (n < 247) return 85;
   1047    if (n < 272) return 86;
   1048    if (n < 299) return 87;
   1049    if (n < 329) return 88;
   1050    if (n < 362) return 89;
   1051    if (n < 398) return 90;
   1052    if (n < 438) return 91;
   1053    if (n < 482) return 92;
   1054    if (n < 530) return 93;
   1055    if (n < 583) return 94;
   1056    if (n < 641) return 95;
   1057    /* Exponential slope up, factor 1.20 */
   1058    if (n < 770) return 96;
   1059    if (n < 924) return 97;
   1060    if (n < 1109) return 98;
   1061    if (n < 1331) return 99;
   1062    if (n < 1597) return 100;
   1063    if (n < 1916) return 101;
   1064    if (n < 2300) return 102;
   1065    if (n < 2760) return 103;
   1066    if (n < 3312) return 104;
   1067    if (n < 3974) return 105;
   1068    if (n < 4769) return 106;
   1069    if (n < 5723) return 107;
   1070    if (n < 6868) return 108;
   1071    if (n < 8241) return 109;
   1072    if (n < 9890) return 110;
   1073    return 111;
   1074 }
   1075 
   1076 // What is the minimum payload size for a given list?
   1077 static
   1078 SizeT listNo_to_pszB_min ( UInt listNo )
   1079 {
   1080    /* Repeatedly computing this function at every request is
   1081       expensive.  Hence at the first call just cache the result for
   1082       every possible argument. */
   1083    static SizeT cache[N_MALLOC_LISTS];
   1084    static Bool  cache_valid = False;
   1085    if (!cache_valid) {
   1086       UInt i;
   1087       for (i = 0; i < N_MALLOC_LISTS; i++) {
   1088          SizeT pszB = 0;
   1089          while (pszB_to_listNo(pszB) < i)
   1090             pszB += VG_MIN_MALLOC_SZB;
   1091          cache[i] = pszB;
   1092       }
   1093       cache_valid = True;
   1094    }
   1095    /* Returned cached answer. */
   1096    vg_assert(listNo <= N_MALLOC_LISTS);
   1097    return cache[listNo];
   1098 }
   1099 
   1100 // What is the maximum payload size for a given list?
   1101 static
   1102 SizeT listNo_to_pszB_max ( UInt listNo )
   1103 {
   1104    vg_assert(listNo <= N_MALLOC_LISTS);
   1105    if (listNo == N_MALLOC_LISTS-1) {
   1106       return MAX_PSZB;
   1107    } else {
   1108       return listNo_to_pszB_min(listNo+1) - 1;
   1109    }
   1110 }
   1111 
   1112 
   1113 /* A nasty hack to try and reduce fragmentation.  Try and replace
   1114    a->freelist[lno] with another block on the same list but with a
   1115    lower address, with the idea of attempting to recycle the same
   1116    blocks rather than cruise through the address space. */
   1117 static
   1118 void swizzle ( Arena* a, UInt lno )
   1119 {
   1120    Block* p_best;
   1121    Block* pp;
   1122    Block* pn;
   1123    UInt   i;
   1124 
   1125    p_best = a->freelist[lno];
   1126    if (p_best == NULL) return;
   1127 
   1128    pn = pp = p_best;
   1129 
   1130    // This loop bound was 20 for a long time, but experiments showed that
   1131    // reducing it to 10 gave the same result in all the tests, and 5 got the
   1132    // same result in 85--100% of cases.  And it's called often enough to be
   1133    // noticeable in programs that allocated a lot.
   1134    for (i = 0; i < 5; i++) {
   1135       pn = get_next_b(pn);
   1136       pp = get_prev_b(pp);
   1137       if (pn < p_best) p_best = pn;
   1138       if (pp < p_best) p_best = pp;
   1139    }
   1140    if (p_best < a->freelist[lno]) {
   1141 #     ifdef VERBOSE_MALLOC
   1142       VG_(printf)("retreat by %ld\n", (Word)(a->freelist[lno] - p_best));
   1143 #     endif
   1144       a->freelist[lno] = p_best;
   1145    }
   1146 }
   1147 
   1148 
   1149 /*------------------------------------------------------------*/
   1150 /*--- Sanity-check/debugging machinery.                    ---*/
   1151 /*------------------------------------------------------------*/
   1152 
   1153 #define REDZONE_LO_MASK    0x31
   1154 #define REDZONE_HI_MASK    0x7c
   1155 
   1156 // Do some crude sanity checks on a Block.
   1157 static
   1158 Bool blockSane ( Arena* a, Block* b )
   1159 {
   1160 #  define BLEAT(str) VG_(printf)("blockSane: fail -- %s\n",str)
   1161    UInt i;
   1162    // The lo and hi size fields will be checked (indirectly) by the call
   1163    // to get_rz_hi_byte().
   1164    if (!a->clientmem && is_inuse_block(b)) {
   1165       // In the inner, for memcheck sake, temporarily mark redzone accessible.
   1166       INNER_REQUEST(mkBhdrAccess(a,b));
   1167       for (i = 0; i < a->rz_szB; i++) {
   1168          if (get_rz_lo_byte(b, i) !=
   1169             (UByte)(((Addr)b&0xff) ^ REDZONE_LO_MASK))
   1170                {BLEAT("redzone-lo");return False;}
   1171          if (get_rz_hi_byte(b, i) !=
   1172             (UByte)(((Addr)b&0xff) ^ REDZONE_HI_MASK))
   1173                {BLEAT("redzone-hi");return False;}
   1174       }
   1175       INNER_REQUEST(mkBhdrNoAccess(a,b));
   1176    }
   1177    return True;
   1178 #  undef BLEAT
   1179 }
   1180 
   1181 // Sanity checks on a Block inside an unsplittable superblock
   1182 static
   1183 Bool unsplittableBlockSane ( Arena* a, Superblock *sb, Block* b )
   1184 {
   1185 #  define BLEAT(str) VG_(printf)("unsplittableBlockSane: fail -- %s\n",str)
   1186    Block*      other_b;
   1187    UByte* sb_start;
   1188    UByte* sb_end;
   1189 
   1190    if (!blockSane (a, b))
   1191       {BLEAT("blockSane");return False;}
   1192 
   1193    if (sb->unsplittable != sb)
   1194       {BLEAT("unsplittable");return False;}
   1195 
   1196    sb_start = &sb->payload_bytes[0];
   1197    sb_end   = &sb->payload_bytes[sb->n_payload_bytes - 1];
   1198 
   1199    // b must be first block (i.e. no unused bytes at the beginning)
   1200    if ((Block*)sb_start != b)
   1201       {BLEAT("sb_start");return False;}
   1202 
   1203    // b must be last block (i.e. no unused bytes at the end)
   1204    other_b = b + get_bszB(b);
   1205    if (other_b-1 != (Block*)sb_end)
   1206       {BLEAT("sb_end");return False;}
   1207 
   1208    return True;
   1209 #  undef BLEAT
   1210 }
   1211 
   1212 // Print superblocks (only for debugging).
   1213 static
   1214 void ppSuperblocks ( Arena* a )
   1215 {
   1216    UInt i, j, blockno = 1;
   1217    SizeT b_bszB;
   1218 
   1219    for (j = 0; j < a->sblocks_used; ++j) {
   1220       Superblock * sb = a->sblocks[j];
   1221 
   1222       VG_(printf)( "\n" );
   1223       VG_(printf)( "superblock %d at %p %s, sb->n_pl_bs = %lu\n",
   1224                    blockno++, sb, (sb->unsplittable ? "unsplittable" : ""),
   1225                    sb->n_payload_bytes);
   1226       for (i = 0; i < sb->n_payload_bytes; i += b_bszB) {
   1227          Block* b = (Block*)&sb->payload_bytes[i];
   1228          b_bszB   = get_bszB(b);
   1229          VG_(printf)( "   block at %d, bszB %lu: ", i, b_bszB );
   1230          VG_(printf)( "%s, ", is_inuse_block(b) ? "inuse" : "free");
   1231          VG_(printf)( "%s\n", blockSane(a, b) ? "ok" : "BAD" );
   1232       }
   1233       vg_assert(i == sb->n_payload_bytes);   // no overshoot at end of Sb
   1234    }
   1235    VG_(printf)( "end of superblocks\n\n" );
   1236 }
   1237 
   1238 // Sanity check both the superblocks and the chains.
   1239 static void sanity_check_malloc_arena ( ArenaId aid )
   1240 {
   1241    UInt        i, j, superblockctr, blockctr_sb, blockctr_li;
   1242    UInt        blockctr_sb_free, listno;
   1243    SizeT       b_bszB, b_pszB, list_min_pszB, list_max_pszB;
   1244    Bool        thisFree, lastWasFree, sblockarrOK;
   1245    Block*      b;
   1246    Block*      b_prev;
   1247    SizeT       arena_bytes_on_loan;
   1248    Arena*      a;
   1249 
   1250 #  define BOMB VG_(core_panic)("sanity_check_malloc_arena")
   1251 
   1252    a = arenaId_to_ArenaP(aid);
   1253 
   1254    // Check the superblock array.
   1255    sblockarrOK
   1256       = a->sblocks != NULL
   1257         && a->sblocks_size >= SBLOCKS_SIZE_INITIAL
   1258         && a->sblocks_used <= a->sblocks_size
   1259         && (a->sblocks_size == SBLOCKS_SIZE_INITIAL
   1260             ? (a->sblocks == &a->sblocks_initial[0])
   1261             : (a->sblocks != &a->sblocks_initial[0]));
   1262    if (!sblockarrOK) {
   1263       VG_(printf)("sanity_check_malloc_arena: sblock array BAD\n");
   1264       BOMB;
   1265    }
   1266 
   1267    // First, traverse all the superblocks, inspecting the Blocks in each.
   1268    superblockctr = blockctr_sb = blockctr_sb_free = 0;
   1269    arena_bytes_on_loan = 0;
   1270    for (j = 0; j < a->sblocks_used; ++j) {
   1271       Superblock * sb = a->sblocks[j];
   1272       lastWasFree = False;
   1273       superblockctr++;
   1274       for (i = 0; i < sb->n_payload_bytes; i += mk_plain_bszB(b_bszB)) {
   1275          blockctr_sb++;
   1276          b     = (Block*)&sb->payload_bytes[i];
   1277          b_bszB = get_bszB_as_is(b);
   1278          if (!blockSane(a, b)) {
   1279             VG_(printf)("sanity_check_malloc_arena: sb %p, block %d "
   1280                         "(bszB %lu):  BAD\n", sb, i, b_bszB );
   1281             BOMB;
   1282          }
   1283          thisFree = !is_inuse_block(b);
   1284          if (thisFree && lastWasFree) {
   1285             VG_(printf)("sanity_check_malloc_arena: sb %p, block %d "
   1286                         "(bszB %lu): UNMERGED FREES\n", sb, i, b_bszB );
   1287             BOMB;
   1288          }
   1289          if (thisFree) blockctr_sb_free++;
   1290          if (!thisFree)
   1291             arena_bytes_on_loan += bszB_to_pszB(a, b_bszB);
   1292          lastWasFree = thisFree;
   1293       }
   1294       if (i > sb->n_payload_bytes) {
   1295          VG_(printf)( "sanity_check_malloc_arena: sb %p: last block "
   1296                       "overshoots end\n", sb);
   1297          BOMB;
   1298       }
   1299    }
   1300 
   1301    arena_bytes_on_loan += a->stats__perm_bytes_on_loan;
   1302 
   1303    if (arena_bytes_on_loan != a->stats__bytes_on_loan) {
   1304 #     ifdef VERBOSE_MALLOC
   1305       VG_(printf)( "sanity_check_malloc_arena: a->bytes_on_loan %lu, "
   1306                    "arena_bytes_on_loan %lu: "
   1307                    "MISMATCH\n", a->stats__bytes_on_loan, arena_bytes_on_loan);
   1308 #     endif
   1309       ppSuperblocks(a);
   1310       BOMB;
   1311    }
   1312 
   1313    /* Second, traverse each list, checking that the back pointers make
   1314       sense, counting blocks encountered, and checking that each block
   1315       is an appropriate size for this list. */
   1316    blockctr_li = 0;
   1317    for (listno = 0; listno < N_MALLOC_LISTS; listno++) {
   1318       list_min_pszB = listNo_to_pszB_min(listno);
   1319       list_max_pszB = listNo_to_pszB_max(listno);
   1320       b = a->freelist[listno];
   1321       if (b == NULL) continue;
   1322       while (True) {
   1323          b_prev = b;
   1324          b = get_next_b(b);
   1325          if (get_prev_b(b) != b_prev) {
   1326             VG_(printf)( "sanity_check_malloc_arena: list %d at %p: "
   1327                          "BAD LINKAGE\n",
   1328                          listno, b );
   1329             BOMB;
   1330          }
   1331          b_pszB = get_pszB(a, b);
   1332          if (b_pszB < list_min_pszB || b_pszB > list_max_pszB) {
   1333             VG_(printf)(
   1334                "sanity_check_malloc_arena: list %d at %p: "
   1335                "WRONG CHAIN SIZE %luB (%luB, %luB)\n",
   1336                listno, b, b_pszB, list_min_pszB, list_max_pszB );
   1337             BOMB;
   1338          }
   1339          blockctr_li++;
   1340          if (b == a->freelist[listno]) break;
   1341       }
   1342    }
   1343 
   1344    if (blockctr_sb_free != blockctr_li) {
   1345 #     ifdef VERBOSE_MALLOC
   1346       VG_(printf)( "sanity_check_malloc_arena: BLOCK COUNT MISMATCH "
   1347                    "(via sbs %d, via lists %d)\n",
   1348                    blockctr_sb_free, blockctr_li );
   1349 #     endif
   1350       ppSuperblocks(a);
   1351       BOMB;
   1352    }
   1353 
   1354    if (VG_(clo_verbosity) > 2)
   1355       VG_(message)(Vg_DebugMsg,
   1356                    "%-8s: %2d sbs, %5d bs, %2d/%-2d free bs, "
   1357                    "%7ld mmap, %7ld loan\n",
   1358                    a->name,
   1359                    superblockctr,
   1360                    blockctr_sb, blockctr_sb_free, blockctr_li,
   1361                    a->stats__bytes_mmaped, a->stats__bytes_on_loan);
   1362 #  undef BOMB
   1363 }
   1364 
   1365 
   1366 #define N_AN_CCS 1000
   1367 
   1368 typedef struct {
   1369    ULong nBytes;
   1370    ULong nBlocks;
   1371    const HChar* cc;
   1372 } AnCC;
   1373 
   1374 static AnCC anCCs[N_AN_CCS];
   1375 
   1376 /* Sorting by decreasing cost center nBytes, to have the biggest
   1377    cost centres at the top. */
   1378 static Int cmp_AnCC_by_vol ( const void* v1, const void* v2 ) {
   1379    const AnCC* ancc1 = v1;
   1380    const AnCC* ancc2 = v2;
   1381    if (ancc1->nBytes < ancc2->nBytes) return 1;
   1382    if (ancc1->nBytes > ancc2->nBytes) return -1;
   1383    return 0;
   1384 }
   1385 
   1386 static void cc_analyse_alloc_arena ( ArenaId aid )
   1387 {
   1388    Word i, j, k;
   1389    Arena*      a;
   1390    Block*      b;
   1391    Bool        thisFree, lastWasFree;
   1392    SizeT       b_bszB;
   1393 
   1394    const HChar* cc;
   1395    UInt n_ccs = 0;
   1396    //return;
   1397    a = arenaId_to_ArenaP(aid);
   1398    if (a->name == NULL) {
   1399       /* arena is not in use, is not initialised and will fail the
   1400          sanity check that follows. */
   1401       return;
   1402    }
   1403 
   1404    sanity_check_malloc_arena(aid);
   1405 
   1406    VG_(printf)(
   1407       "-------- Arena \"%s\": %'lu/%'lu max/curr mmap'd, "
   1408       "%llu/%llu unsplit/split sb unmmap'd, "
   1409       "%'lu/%'lu max/curr on_loan %lu rzB --------\n",
   1410       a->name, a->stats__bytes_mmaped_max, a->stats__bytes_mmaped,
   1411       a->stats__nreclaim_unsplit, a->stats__nreclaim_split,
   1412       a->stats__bytes_on_loan_max, a->stats__bytes_on_loan,
   1413       a->rz_szB
   1414    );
   1415 
   1416    for (j = 0; j < a->sblocks_used; ++j) {
   1417       Superblock * sb = a->sblocks[j];
   1418       lastWasFree = False;
   1419       for (i = 0; i < sb->n_payload_bytes; i += mk_plain_bszB(b_bszB)) {
   1420          b     = (Block*)&sb->payload_bytes[i];
   1421          b_bszB = get_bszB_as_is(b);
   1422          if (!blockSane(a, b)) {
   1423             VG_(printf)("sanity_check_malloc_arena: sb %p, block %ld "
   1424                         "(bszB %lu):  BAD\n", sb, i, b_bszB );
   1425             vg_assert(0);
   1426          }
   1427          thisFree = !is_inuse_block(b);
   1428          if (thisFree && lastWasFree) {
   1429             VG_(printf)("sanity_check_malloc_arena: sb %p, block %ld "
   1430                         "(bszB %lu): UNMERGED FREES\n", sb, i, b_bszB );
   1431             vg_assert(0);
   1432          }
   1433          lastWasFree = thisFree;
   1434 
   1435          if (thisFree) continue;
   1436 
   1437          if (VG_(clo_profile_heap))
   1438             cc = get_cc(b);
   1439          else
   1440             cc = "(--profile-heap=yes for details)";
   1441          if (0)
   1442          VG_(printf)("block: inUse=%d pszB=%d cc=%s\n",
   1443                      (Int)(!thisFree),
   1444                      (Int)bszB_to_pszB(a, b_bszB),
   1445                      get_cc(b));
   1446          vg_assert(cc);
   1447          for (k = 0; k < n_ccs; k++) {
   1448            vg_assert(anCCs[k].cc);
   1449             if (0 == VG_(strcmp)(cc, anCCs[k].cc))
   1450                break;
   1451          }
   1452          vg_assert(k >= 0 && k <= n_ccs);
   1453 
   1454          if (k == n_ccs) {
   1455             vg_assert(n_ccs < N_AN_CCS-1);
   1456             n_ccs++;
   1457             anCCs[k].nBytes  = 0;
   1458             anCCs[k].nBlocks = 0;
   1459             anCCs[k].cc      = cc;
   1460          }
   1461 
   1462          vg_assert(k >= 0 && k < n_ccs && k < N_AN_CCS);
   1463          anCCs[k].nBytes += (ULong)bszB_to_pszB(a, b_bszB);
   1464          anCCs[k].nBlocks++;
   1465       }
   1466       if (i > sb->n_payload_bytes) {
   1467          VG_(printf)( "sanity_check_malloc_arena: sb %p: last block "
   1468                       "overshoots end\n", sb);
   1469          vg_assert(0);
   1470       }
   1471    }
   1472 
   1473    if (a->stats__perm_bytes_on_loan > 0) {
   1474       vg_assert(n_ccs < N_AN_CCS-1);
   1475       anCCs[n_ccs].nBytes  = a->stats__perm_bytes_on_loan;
   1476       anCCs[n_ccs].nBlocks = a->stats__perm_blocks;
   1477       anCCs[n_ccs].cc      = "perm_malloc";
   1478       n_ccs++;
   1479    }
   1480 
   1481    VG_(ssort)( &anCCs[0], n_ccs, sizeof(anCCs[0]), cmp_AnCC_by_vol );
   1482 
   1483    for (k = 0; k < n_ccs; k++) {
   1484       VG_(printf)("%'13llu in %'9llu: %s\n",
   1485                   anCCs[k].nBytes, anCCs[k].nBlocks, anCCs[k].cc );
   1486    }
   1487 
   1488    VG_(printf)("\n");
   1489 }
   1490 
   1491 
   1492 void VG_(sanity_check_malloc_all) ( void )
   1493 {
   1494    UInt i;
   1495    for (i = 0; i < VG_N_ARENAS; i++) {
   1496       if (i == VG_AR_CLIENT && !client_inited)
   1497          continue;
   1498       sanity_check_malloc_arena ( i );
   1499    }
   1500 }
   1501 
   1502 void VG_(describe_arena_addr) ( Addr a, AddrArenaInfo* aai )
   1503 {
   1504    UInt i;
   1505    Superblock *sb;
   1506    Arena      *arena;
   1507 
   1508    for (i = 0; i < VG_N_ARENAS; i++) {
   1509       if (i == VG_AR_CLIENT && !client_inited)
   1510          continue;
   1511       arena = arenaId_to_ArenaP(i);
   1512       sb = maybe_findSb( arena, a );
   1513       if (sb != NULL) {
   1514          Word   j;
   1515          SizeT  b_bszB;
   1516          Block *b = NULL;
   1517 
   1518          aai->aid = i;
   1519          aai->name = arena->name;
   1520          for (j = 0; j < sb->n_payload_bytes; j += mk_plain_bszB(b_bszB)) {
   1521             b     = (Block*)&sb->payload_bytes[j];
   1522             b_bszB = get_bszB_as_is(b);
   1523             if (a < (Addr)b + mk_plain_bszB(b_bszB))
   1524                break;
   1525          }
   1526          vg_assert (b);
   1527          aai->block_szB = get_pszB(arena, b);
   1528          aai->rwoffset = a - (Addr)get_block_payload(arena, b);
   1529          aai->free = !is_inuse_block(b);
   1530          return;
   1531       }
   1532    }
   1533    aai->aid = 0;
   1534    aai->name = NULL;
   1535    aai->block_szB = 0;
   1536    aai->rwoffset = 0;
   1537    aai->free = False;
   1538 }
   1539 
   1540 /*------------------------------------------------------------*/
   1541 /*--- Creating and deleting blocks.                        ---*/
   1542 /*------------------------------------------------------------*/
   1543 
   1544 // Mark the bytes at b .. b+bszB-1 as not in use, and add them to the
   1545 // relevant free list.
   1546 
   1547 static
   1548 void mkFreeBlock ( Arena* a, Block* b, SizeT bszB, UInt b_lno )
   1549 {
   1550    SizeT pszB = bszB_to_pszB(a, bszB);
   1551    vg_assert(b_lno == pszB_to_listNo(pszB));
   1552    INNER_REQUEST(VALGRIND_MAKE_MEM_UNDEFINED(b, bszB));
   1553    // Set the size fields and indicate not-in-use.
   1554    set_bszB(b, mk_free_bszB(bszB));
   1555 
   1556    // Add to the relevant list.
   1557    if (a->freelist[b_lno] == NULL) {
   1558       set_prev_b(b, b);
   1559       set_next_b(b, b);
   1560       a->freelist[b_lno] = b;
   1561    } else {
   1562       Block* b_prev = get_prev_b(a->freelist[b_lno]);
   1563       Block* b_next = a->freelist[b_lno];
   1564       set_next_b(b_prev, b);
   1565       set_prev_b(b_next, b);
   1566       set_next_b(b, b_next);
   1567       set_prev_b(b, b_prev);
   1568    }
   1569 #  ifdef DEBUG_MALLOC
   1570    (void)blockSane(a,b);
   1571 #  endif
   1572 }
   1573 
   1574 // Mark the bytes at b .. b+bszB-1 as in use, and set up the block
   1575 // appropriately.
   1576 static
   1577 void mkInuseBlock ( Arena* a, Block* b, SizeT bszB )
   1578 {
   1579    UInt i;
   1580    vg_assert(bszB >= min_useful_bszB(a));
   1581    INNER_REQUEST(VALGRIND_MAKE_MEM_UNDEFINED(b, bszB));
   1582    set_bszB(b, mk_inuse_bszB(bszB));
   1583    set_prev_b(b, NULL);    // Take off freelist
   1584    set_next_b(b, NULL);    // ditto
   1585    if (!a->clientmem) {
   1586       for (i = 0; i < a->rz_szB; i++) {
   1587          set_rz_lo_byte(b, i, (UByte)(((Addr)b&0xff) ^ REDZONE_LO_MASK));
   1588          set_rz_hi_byte(b, i, (UByte)(((Addr)b&0xff) ^ REDZONE_HI_MASK));
   1589       }
   1590    }
   1591 #  ifdef DEBUG_MALLOC
   1592    (void)blockSane(a,b);
   1593 #  endif
   1594 }
   1595 
   1596 // Mark the bytes at b .. b+bszB-1 as being part of a block that has been shrunk.
   1597 static
   1598 void shrinkInuseBlock ( Arena* a, Block* b, SizeT bszB )
   1599 {
   1600    UInt i;
   1601 
   1602    vg_assert(bszB >= min_useful_bszB(a));
   1603    INNER_REQUEST(mkBhdrAccess(a,b));
   1604    set_bszB(b, mk_inuse_bszB(bszB));
   1605    if (!a->clientmem) {
   1606       for (i = 0; i < a->rz_szB; i++) {
   1607          set_rz_lo_byte(b, i, (UByte)(((Addr)b&0xff) ^ REDZONE_LO_MASK));
   1608          set_rz_hi_byte(b, i, (UByte)(((Addr)b&0xff) ^ REDZONE_HI_MASK));
   1609       }
   1610    }
   1611    INNER_REQUEST(mkBhdrNoAccess(a,b));
   1612 
   1613 #  ifdef DEBUG_MALLOC
   1614    (void)blockSane(a,b);
   1615 #  endif
   1616 }
   1617 
   1618 // Remove a block from a given list.  Does no sanity checking.
   1619 static
   1620 void unlinkBlock ( Arena* a, Block* b, UInt listno )
   1621 {
   1622    vg_assert(listno < N_MALLOC_LISTS);
   1623    if (get_prev_b(b) == b) {
   1624       // Only one element in the list; treat it specially.
   1625       vg_assert(get_next_b(b) == b);
   1626       a->freelist[listno] = NULL;
   1627    } else {
   1628       Block* b_prev = get_prev_b(b);
   1629       Block* b_next = get_next_b(b);
   1630       a->freelist[listno] = b_prev;
   1631       set_next_b(b_prev, b_next);
   1632       set_prev_b(b_next, b_prev);
   1633       swizzle ( a, listno );
   1634    }
   1635    set_prev_b(b, NULL);
   1636    set_next_b(b, NULL);
   1637 }
   1638 
   1639 
   1640 /*------------------------------------------------------------*/
   1641 /*--- Core-visible functions.                              ---*/
   1642 /*------------------------------------------------------------*/
   1643 
   1644 // Align the request size.
   1645 static __inline__
   1646 SizeT align_req_pszB ( SizeT req_pszB )
   1647 {
   1648    SizeT n = VG_MIN_MALLOC_SZB-1;
   1649    return ((req_pszB + n) & (~n));
   1650 }
   1651 
   1652 static
   1653 void add_one_block_to_stats (Arena* a, SizeT loaned)
   1654 {
   1655    a->stats__bytes_on_loan += loaned;
   1656    if (a->stats__bytes_on_loan > a->stats__bytes_on_loan_max) {
   1657       a->stats__bytes_on_loan_max = a->stats__bytes_on_loan;
   1658       if (a->stats__bytes_on_loan_max >= a->next_profile_at) {
   1659          /* next profile after 10% more growth */
   1660          a->next_profile_at
   1661             = (SizeT)(
   1662                  (((ULong)a->stats__bytes_on_loan_max) * 105ULL) / 100ULL );
   1663          if (VG_(clo_profile_heap))
   1664             cc_analyse_alloc_arena(arenaP_to_ArenaId (a));
   1665       }
   1666    }
   1667    a->stats__tot_blocks += (ULong)1;
   1668    a->stats__tot_bytes  += (ULong)loaned;
   1669 }
   1670 
   1671 /* Allocate a piece of memory of req_pszB bytes on the given arena.
   1672    The function may return NULL if (and only if) aid == VG_AR_CLIENT.
   1673    Otherwise, the function returns a non-NULL value. */
   1674 void* VG_(arena_malloc) ( ArenaId aid, const HChar* cc, SizeT req_pszB )
   1675 {
   1676    SizeT       req_bszB, frag_bszB, b_bszB;
   1677    UInt        lno, i;
   1678    Superblock* new_sb = NULL;
   1679    Block*      b = NULL;
   1680    Arena*      a;
   1681    void*       v;
   1682    UWord       stats__nsearches = 0;
   1683 
   1684    ensure_mm_init(aid);
   1685    a = arenaId_to_ArenaP(aid);
   1686 
   1687    vg_assert(req_pszB < MAX_PSZB);
   1688    req_pszB = align_req_pszB(req_pszB);
   1689    req_bszB = pszB_to_bszB(a, req_pszB);
   1690 
   1691    // You must provide a cost-center name against which to charge
   1692    // this allocation; it isn't optional.
   1693    vg_assert(cc);
   1694 
   1695    // Scan through all the big-enough freelists for a block.
   1696    //
   1697    // Nb: this scanning might be expensive in some cases.  Eg. if you
   1698    // allocate lots of small objects without freeing them, but no
   1699    // medium-sized objects, it will repeatedly scanning through the whole
   1700    // list, and each time not find any free blocks until the last element.
   1701    //
   1702    // If this becomes a noticeable problem... the loop answers the question
   1703    // "where is the first nonempty list above me?"  And most of the time,
   1704    // you ask the same question and get the same answer.  So it would be
   1705    // good to somehow cache the results of previous searches.
   1706    // One possibility is an array (with N_MALLOC_LISTS elements) of
   1707    // shortcuts.  shortcut[i] would give the index number of the nearest
   1708    // larger list above list i which is non-empty.  Then this loop isn't
   1709    // necessary.  However, we'd have to modify some section [ .. i-1] of the
   1710    // shortcut array every time a list [i] changes from empty to nonempty or
   1711    // back.  This would require care to avoid pathological worst-case
   1712    // behaviour.
   1713    //
   1714    for (lno = pszB_to_listNo(req_pszB); lno < N_MALLOC_LISTS; lno++) {
   1715       UWord nsearches_this_level = 0;
   1716       b = a->freelist[lno];
   1717       if (NULL == b) continue;   // If this list is empty, try the next one.
   1718       while (True) {
   1719          stats__nsearches++;
   1720          nsearches_this_level++;
   1721          if (UNLIKELY(nsearches_this_level >= 100)
   1722              && lno < N_MALLOC_LISTS-1) {
   1723             /* Avoid excessive scanning on this freelist, and instead
   1724                try the next one up.  But first, move this freelist's
   1725                start pointer one element along, so as to ensure that
   1726                subsequent searches of this list don't endlessly
   1727                revisit only these 100 elements, but in fact slowly
   1728                progress through the entire list. */
   1729             b = a->freelist[lno];
   1730             vg_assert(b); // this list must be nonempty!
   1731             a->freelist[lno] = get_next_b(b); // step one along
   1732             break;
   1733          }
   1734          b_bszB = get_bszB(b);
   1735          if (b_bszB >= req_bszB) goto obtained_block;    // success!
   1736          b = get_next_b(b);
   1737          if (b == a->freelist[lno]) break;   // traversed entire freelist
   1738       }
   1739    }
   1740 
   1741    // If we reach here, no suitable block found, allocate a new superblock
   1742    vg_assert(lno == N_MALLOC_LISTS);
   1743    new_sb = newSuperblock(a, req_bszB);
   1744    if (NULL == new_sb) {
   1745       // Should only fail if for client, otherwise, should have aborted
   1746       // already.
   1747       vg_assert(VG_AR_CLIENT == aid);
   1748       return NULL;
   1749    }
   1750 
   1751    vg_assert(a->sblocks_used <= a->sblocks_size);
   1752    if (a->sblocks_used == a->sblocks_size) {
   1753       Superblock ** array;
   1754       SysRes sres = VG_(am_mmap_anon_float_valgrind)(sizeof(Superblock *) *
   1755                                                      a->sblocks_size * 2);
   1756       if (sr_isError(sres)) {
   1757          VG_(out_of_memory_NORETURN)("arena_init", sizeof(Superblock *) *
   1758                                                    a->sblocks_size * 2);
   1759          /* NOTREACHED */
   1760       }
   1761       array = (Superblock**)(Addr)sr_Res(sres);
   1762       for (i = 0; i < a->sblocks_used; ++i) array[i] = a->sblocks[i];
   1763 
   1764       a->sblocks_size *= 2;
   1765       a->sblocks = array;
   1766       VG_(debugLog)(1, "mallocfree",
   1767                        "sblock array for arena `%s' resized to %ld\n",
   1768                        a->name, a->sblocks_size);
   1769    }
   1770 
   1771    vg_assert(a->sblocks_used < a->sblocks_size);
   1772 
   1773    i = a->sblocks_used;
   1774    while (i > 0) {
   1775       if (a->sblocks[i-1] > new_sb) {
   1776          a->sblocks[i] = a->sblocks[i-1];
   1777       } else {
   1778          break;
   1779       }
   1780       --i;
   1781    }
   1782    a->sblocks[i] = new_sb;
   1783    a->sblocks_used++;
   1784 
   1785    b = (Block*)&new_sb->payload_bytes[0];
   1786    lno = pszB_to_listNo(bszB_to_pszB(a, new_sb->n_payload_bytes));
   1787    mkFreeBlock ( a, b, new_sb->n_payload_bytes, lno);
   1788    if (VG_(clo_profile_heap))
   1789       set_cc(b, "admin.free-new-sb-1");
   1790    // fall through
   1791 
   1792   obtained_block:
   1793    // Ok, we can allocate from b, which lives in list lno.
   1794    vg_assert(b != NULL);
   1795    vg_assert(lno < N_MALLOC_LISTS);
   1796    vg_assert(a->freelist[lno] != NULL);
   1797    b_bszB = get_bszB(b);
   1798    // req_bszB is the size of the block we are after.  b_bszB is the
   1799    // size of what we've actually got. */
   1800    vg_assert(b_bszB >= req_bszB);
   1801 
   1802    // Could we split this block and still get a useful fragment?
   1803    // A block in an unsplittable superblock can never be splitted.
   1804    frag_bszB = b_bszB - req_bszB;
   1805    if (frag_bszB >= min_useful_bszB(a)
   1806        && (NULL == new_sb || ! new_sb->unsplittable)) {
   1807       // Yes, split block in two, put the fragment on the appropriate free
   1808       // list, and update b_bszB accordingly.
   1809       // printf( "split %dB into %dB and %dB\n", b_bszB, req_bszB, frag_bszB );
   1810       unlinkBlock(a, b, lno);
   1811       mkInuseBlock(a, b, req_bszB);
   1812       if (VG_(clo_profile_heap))
   1813          set_cc(b, cc);
   1814       mkFreeBlock(a, &b[req_bszB], frag_bszB,
   1815                      pszB_to_listNo(bszB_to_pszB(a, frag_bszB)));
   1816       if (VG_(clo_profile_heap))
   1817          set_cc(&b[req_bszB], "admin.fragmentation-1");
   1818       b_bszB = get_bszB(b);
   1819    } else {
   1820       // No, mark as in use and use as-is.
   1821       unlinkBlock(a, b, lno);
   1822       mkInuseBlock(a, b, b_bszB);
   1823       if (VG_(clo_profile_heap))
   1824          set_cc(b, cc);
   1825    }
   1826 
   1827    // Update stats
   1828    SizeT loaned = bszB_to_pszB(a, b_bszB);
   1829    add_one_block_to_stats (a, loaned);
   1830    a->stats__nsearches  += (ULong)stats__nsearches;
   1831 
   1832 #  ifdef DEBUG_MALLOC
   1833    sanity_check_malloc_arena(aid);
   1834 #  endif
   1835 
   1836    v = get_block_payload(a, b);
   1837    vg_assert( (((Addr)v) & (VG_MIN_MALLOC_SZB-1)) == 0 );
   1838 
   1839    // Which size should we pass to VALGRIND_MALLOCLIKE_BLOCK ?
   1840    // We have 2 possible options:
   1841    // 1. The final resulting usable size.
   1842    // 2. The initial (non-aligned) req_pszB.
   1843    // Memcheck implements option 2 easily, as the initial requested size
   1844    // is maintained in the mc_chunk data structure.
   1845    // This is not as easy in the core, as there is no such structure.
   1846    // (note: using the aligned req_pszB is not simpler than 2, as
   1847    //  requesting an aligned req_pszB might still be satisfied by returning
   1848    // a (slightly) bigger block than requested if the remaining part of
   1849    // of a free block is not big enough to make a free block by itself).
   1850    // Implement Sol 2 can be done the following way:
   1851    // After having called VALGRIND_MALLOCLIKE_BLOCK, the non accessible
   1852    // redzone just after the block can be used to determine the
   1853    // initial requested size.
   1854    // Currently, not implemented => we use Option 1.
   1855    INNER_REQUEST
   1856       (VALGRIND_MALLOCLIKE_BLOCK(v,
   1857                                  VG_(arena_malloc_usable_size)(aid, v),
   1858                                  a->rz_szB, False));
   1859 
   1860    /* For debugging/testing purposes, fill the newly allocated area
   1861       with a definite value in an attempt to shake out any
   1862       uninitialised uses of the data (by V core / V tools, not by the
   1863       client).  Testing on 25 Nov 07 with the values 0x00, 0xFF, 0x55,
   1864       0xAA showed no differences in the regression tests on
   1865       amd64-linux.  Note, is disabled by default. */
   1866    if (0 && aid != VG_AR_CLIENT)
   1867       VG_(memset)(v, 0xAA, (SizeT)req_pszB);
   1868 
   1869    return v;
   1870 }
   1871 
   1872 // If arena has already a deferred reclaimed superblock and
   1873 // this superblock is still reclaimable, then this superblock is first
   1874 // reclaimed.
   1875 // sb becomes then the new arena deferred superblock.
   1876 // Passing NULL as sb allows to reclaim a deferred sb without setting a new
   1877 // deferred reclaim.
   1878 static
   1879 void deferred_reclaimSuperblock ( Arena* a, Superblock* sb)
   1880 {
   1881 
   1882    if (sb == NULL) {
   1883       if (!a->deferred_reclaimed_sb)
   1884          // no deferred sb to reclaim now, nothing to do in the future =>
   1885          // return directly.
   1886          return;
   1887 
   1888       VG_(debugLog)(1, "mallocfree",
   1889                     "deferred_reclaimSuperblock NULL "
   1890                     "(prev %p) owner %s/%s\n",
   1891                     a->deferred_reclaimed_sb,
   1892                     a->clientmem ? "CLIENT" : "VALGRIND", a->name );
   1893    } else
   1894       VG_(debugLog)(1, "mallocfree",
   1895                     "deferred_reclaimSuperblock at %p (pszB %7ld) %s "
   1896                     "(prev %p) owner %s/%s\n",
   1897                     sb, sb->n_payload_bytes,
   1898                     (sb->unsplittable ? "unsplittable" : ""),
   1899                     a->deferred_reclaimed_sb,
   1900                     a->clientmem ? "CLIENT" : "VALGRIND", a->name );
   1901 
   1902    if (a->deferred_reclaimed_sb && a->deferred_reclaimed_sb != sb) {
   1903       // If we are deferring another block that the current block deferred,
   1904       // then if this block can stil be reclaimed, reclaim it now.
   1905       // Note that we might have a re-deferred reclaim of the same block
   1906       // with a sequence: free (causing a deferred reclaim of sb)
   1907       //                  alloc (using a piece of memory of the deferred sb)
   1908       //                  free of the just alloc-ed block (causing a re-defer).
   1909       UByte*      def_sb_start;
   1910       UByte*      def_sb_end;
   1911       Superblock* def_sb;
   1912       Block*      b;
   1913 
   1914       def_sb = a->deferred_reclaimed_sb;
   1915       def_sb_start = &def_sb->payload_bytes[0];
   1916       def_sb_end   = &def_sb->payload_bytes[def_sb->n_payload_bytes - 1];
   1917       b = (Block *)def_sb_start;
   1918       vg_assert (blockSane(a, b));
   1919 
   1920       // Check if the deferred_reclaimed_sb is still reclaimable.
   1921       // If yes, we will execute the reclaim.
   1922       if (!is_inuse_block(b)) {
   1923          // b (at the beginning of def_sb) is not in use.
   1924          UInt        b_listno;
   1925          SizeT       b_bszB, b_pszB;
   1926          b_bszB   = get_bszB(b);
   1927          b_pszB   = bszB_to_pszB(a, b_bszB);
   1928          if (b + b_bszB-1 == (Block*)def_sb_end) {
   1929             // b (not in use) covers the full superblock.
   1930             // => def_sb is still reclaimable
   1931             // => execute now the reclaim of this def_sb.
   1932             b_listno = pszB_to_listNo(b_pszB);
   1933             unlinkBlock( a, b, b_listno );
   1934             reclaimSuperblock (a, def_sb);
   1935             a->deferred_reclaimed_sb = NULL;
   1936          }
   1937       }
   1938    }
   1939 
   1940    // sb (possibly NULL) becomes the new deferred reclaimed superblock.
   1941    a->deferred_reclaimed_sb = sb;
   1942 }
   1943 
   1944 /* b must be a free block, of size b_bszB.
   1945    If b is followed by another free block, merge them.
   1946    If b is preceeded by another free block, merge them.
   1947    If the merge results in the superblock being fully free,
   1948    deferred_reclaimSuperblock the superblock. */
   1949 static void mergeWithFreeNeighbours (Arena* a, Superblock* sb,
   1950                                      Block* b, SizeT b_bszB)
   1951 {
   1952    UByte*      sb_start;
   1953    UByte*      sb_end;
   1954    Block*      other_b;
   1955    SizeT       other_bszB;
   1956    UInt        b_listno;
   1957 
   1958    sb_start = &sb->payload_bytes[0];
   1959    sb_end   = &sb->payload_bytes[sb->n_payload_bytes - 1];
   1960 
   1961    b_listno = pszB_to_listNo(bszB_to_pszB(a, b_bszB));
   1962 
   1963    // See if this block can be merged with its successor.
   1964    // First test if we're far enough before the superblock's end to possibly
   1965    // have a successor.
   1966    other_b = b + b_bszB;
   1967    if (other_b+min_useful_bszB(a)-1 <= (Block*)sb_end) {
   1968       // Ok, we have a successor, merge if it's not in use.
   1969       other_bszB = get_bszB(other_b);
   1970       if (!is_inuse_block(other_b)) {
   1971          // VG_(printf)( "merge-successor\n");
   1972 #        ifdef DEBUG_MALLOC
   1973          vg_assert(blockSane(a, other_b));
   1974 #        endif
   1975          unlinkBlock( a, b, b_listno );
   1976          unlinkBlock( a, other_b,
   1977                       pszB_to_listNo(bszB_to_pszB(a,other_bszB)) );
   1978          b_bszB += other_bszB;
   1979          b_listno = pszB_to_listNo(bszB_to_pszB(a, b_bszB));
   1980          mkFreeBlock( a, b, b_bszB, b_listno );
   1981          if (VG_(clo_profile_heap))
   1982             set_cc(b, "admin.free-2");
   1983       }
   1984    } else {
   1985       // Not enough space for successor: check that b is the last block
   1986       // ie. there are no unused bytes at the end of the Superblock.
   1987       vg_assert(other_b-1 == (Block*)sb_end);
   1988    }
   1989 
   1990    // Then see if this block can be merged with its predecessor.
   1991    // First test if we're far enough after the superblock's start to possibly
   1992    // have a predecessor.
   1993    if (b >= (Block*)sb_start + min_useful_bszB(a)) {
   1994       // Ok, we have a predecessor, merge if it's not in use.
   1995       other_b = get_predecessor_block( b );
   1996       other_bszB = get_bszB(other_b);
   1997       if (!is_inuse_block(other_b)) {
   1998          // VG_(printf)( "merge-predecessor\n");
   1999          unlinkBlock( a, b, b_listno );
   2000          unlinkBlock( a, other_b,
   2001                       pszB_to_listNo(bszB_to_pszB(a, other_bszB)) );
   2002          b = other_b;
   2003          b_bszB += other_bszB;
   2004          b_listno = pszB_to_listNo(bszB_to_pszB(a, b_bszB));
   2005          mkFreeBlock( a, b, b_bszB, b_listno );
   2006          if (VG_(clo_profile_heap))
   2007             set_cc(b, "admin.free-3");
   2008       }
   2009    } else {
   2010       // Not enough space for predecessor: check that b is the first block,
   2011       // ie. there are no unused bytes at the start of the Superblock.
   2012       vg_assert((Block*)sb_start == b);
   2013    }
   2014 
   2015    /* If the block b just merged is the only block of the superblock sb,
   2016       then we defer reclaim sb. */
   2017    if ( ((Block*)sb_start == b) && (b + b_bszB-1 == (Block*)sb_end) ) {
   2018       deferred_reclaimSuperblock (a, sb);
   2019    }
   2020 }
   2021 
   2022 void VG_(arena_free) ( ArenaId aid, void* ptr )
   2023 {
   2024    Superblock* sb;
   2025    Block*      b;
   2026    SizeT       b_bszB, b_pszB;
   2027    UInt        b_listno;
   2028    Arena*      a;
   2029 
   2030    ensure_mm_init(aid);
   2031    a = arenaId_to_ArenaP(aid);
   2032 
   2033    if (ptr == NULL) {
   2034       return;
   2035    }
   2036 
   2037    b = get_payload_block(a, ptr);
   2038 
   2039    /* If this is one of V's areas, check carefully the block we're
   2040       getting back.  This picks up simple block-end overruns. */
   2041    if (aid != VG_AR_CLIENT)
   2042       vg_assert(blockSane(a, b));
   2043 
   2044    b_bszB   = get_bszB(b);
   2045    b_pszB   = bszB_to_pszB(a, b_bszB);
   2046    sb       = findSb( a, b );
   2047 
   2048    a->stats__bytes_on_loan -= b_pszB;
   2049 
   2050    /* If this is one of V's areas, fill it up with junk to enhance the
   2051       chances of catching any later reads of it.  Note, 0xDD is
   2052       carefully chosen junk :-), in that: (1) 0xDDDDDDDD is an invalid
   2053       and non-word-aligned address on most systems, and (2) 0xDD is a
   2054       value which is unlikely to be generated by the new compressed
   2055       Vbits representation for memcheck. */
   2056    if (aid != VG_AR_CLIENT)
   2057       VG_(memset)(ptr, 0xDD, (SizeT)b_pszB);
   2058 
   2059    if (! sb->unsplittable) {
   2060       // Put this chunk back on a list somewhere.
   2061       b_listno = pszB_to_listNo(b_pszB);
   2062       mkFreeBlock( a, b, b_bszB, b_listno );
   2063       if (VG_(clo_profile_heap))
   2064          set_cc(b, "admin.free-1");
   2065 
   2066       /* Possibly merge b with its predecessor or successor. */
   2067       mergeWithFreeNeighbours (a, sb, b, b_bszB);
   2068 
   2069       // Inform that ptr has been released. We give redzone size
   2070       // 0 instead of a->rz_szB as proper accessibility is done just after.
   2071       INNER_REQUEST(VALGRIND_FREELIKE_BLOCK(ptr, 0));
   2072 
   2073       // We need to (re-)establish the minimum accessibility needed
   2074       // for free list management. E.g. if block ptr has been put in a free
   2075       // list and a neighbour block is released afterwards, the
   2076       // "lo" and "hi" portions of the block ptr will be accessed to
   2077       // glue the 2 blocks together.
   2078       // We could mark the whole block as not accessible, and each time
   2079       // transiently mark accessible the needed lo/hi parts. Not done as this
   2080       // is quite complex, for very little expected additional bug detection.
   2081       // fully unaccessible. Note that the below marks the (possibly) merged
   2082       // block, not the block corresponding to the ptr argument.
   2083 
   2084       // First mark the whole block unaccessible.
   2085       INNER_REQUEST(VALGRIND_MAKE_MEM_NOACCESS(b, b_bszB));
   2086       // Then mark the relevant administrative headers as defined.
   2087       // No need to mark the heap profile portion as defined, this is not
   2088       // used for free blocks.
   2089       INNER_REQUEST(VALGRIND_MAKE_MEM_DEFINED(b + hp_overhead_szB(),
   2090                                               sizeof(SizeT) + sizeof(void*)));
   2091       INNER_REQUEST(VALGRIND_MAKE_MEM_DEFINED(b + b_bszB
   2092                                               - sizeof(SizeT) - sizeof(void*),
   2093                                               sizeof(SizeT) + sizeof(void*)));
   2094    } else {
   2095       vg_assert(unsplittableBlockSane(a, sb, b));
   2096 
   2097       // Inform that ptr has been released. Redzone size value
   2098       // is not relevant (so we give  0 instead of a->rz_szB)
   2099       // as it is expected that the aspacemgr munmap will be used by
   2100       //  outer to mark the whole superblock as unaccessible.
   2101       INNER_REQUEST(VALGRIND_FREELIKE_BLOCK(ptr, 0));
   2102 
   2103       // Reclaim immediately the unsplittable superblock sb.
   2104       reclaimSuperblock (a, sb);
   2105    }
   2106 
   2107 #  ifdef DEBUG_MALLOC
   2108    sanity_check_malloc_arena(aid);
   2109 #  endif
   2110 
   2111 }
   2112 
   2113 
   2114 /*
   2115    The idea for malloc_aligned() is to allocate a big block, base, and
   2116    then split it into two parts: frag, which is returned to the the
   2117    free pool, and align, which is the bit we're really after.  Here's
   2118    a picture.  L and H denote the block lower and upper overheads, in
   2119    bytes.  The details are gruesome.  Note it is slightly complicated
   2120    because the initial request to generate base may return a bigger
   2121    block than we asked for, so it is important to distinguish the base
   2122    request size and the base actual size.
   2123 
   2124    frag_b                   align_b
   2125    |                        |
   2126    |    frag_p              |    align_p
   2127    |    |                   |    |
   2128    v    v                   v    v
   2129 
   2130    +---+                +---+---+               +---+
   2131    | L |----------------| H | L |---------------| H |
   2132    +---+                +---+---+               +---+
   2133 
   2134    ^    ^                        ^
   2135    |    |                        :
   2136    |    base_p                   this addr must be aligned
   2137    |
   2138    base_b
   2139 
   2140    .    .               .   .   .               .   .
   2141    <------ frag_bszB ------->   .               .   .
   2142    .    <------------- base_pszB_act ----------->   .
   2143    .    .               .   .   .               .   .
   2144 
   2145 */
   2146 void* VG_(arena_memalign) ( ArenaId aid, const HChar* cc,
   2147                             SizeT req_alignB, SizeT req_pszB )
   2148 {
   2149    SizeT  base_pszB_req, base_pszB_act, frag_bszB;
   2150    Block  *base_b, *align_b;
   2151    UByte  *base_p, *align_p;
   2152    SizeT  saved_bytes_on_loan;
   2153    Arena* a;
   2154 
   2155    ensure_mm_init(aid);
   2156    a = arenaId_to_ArenaP(aid);
   2157 
   2158    vg_assert(req_pszB < MAX_PSZB);
   2159 
   2160    // You must provide a cost-center name against which to charge
   2161    // this allocation; it isn't optional.
   2162    vg_assert(cc);
   2163 
   2164    // Check that the requested alignment has a plausible size.
   2165    // Check that the requested alignment seems reasonable; that is, is
   2166    // a power of 2.
   2167    if (req_alignB < VG_MIN_MALLOC_SZB
   2168        || req_alignB > 16 * 1024 * 1024
   2169        || VG_(log2)( req_alignB ) == -1 /* not a power of 2 */) {
   2170       VG_(printf)("VG_(arena_memalign)(%p, %lu, %lu)\n"
   2171                   "bad alignment value %lu\n"
   2172                   "(it is too small, too big, or not a power of two)",
   2173                   a, req_alignB, req_pszB, req_alignB );
   2174       VG_(core_panic)("VG_(arena_memalign)");
   2175       /*NOTREACHED*/
   2176    }
   2177    // Paranoid
   2178    vg_assert(req_alignB % VG_MIN_MALLOC_SZB == 0);
   2179 
   2180    /* Required payload size for the aligned chunk. */
   2181    req_pszB = align_req_pszB(req_pszB);
   2182 
   2183    /* Payload size to request for the big block that we will split up. */
   2184    base_pszB_req = req_pszB + min_useful_bszB(a) + req_alignB;
   2185 
   2186    /* Payload ptr for the block we are going to split.  Note this
   2187       changes a->bytes_on_loan; we save and restore it ourselves. */
   2188    saved_bytes_on_loan = a->stats__bytes_on_loan;
   2189    {
   2190       /* As we will split the block given back by VG_(arena_malloc),
   2191          we have to (temporarily) disable unsplittable for this arena,
   2192          as unsplittable superblocks cannot be splitted. */
   2193       const SizeT save_min_unsplittable_sblock_szB
   2194          = a->min_unsplittable_sblock_szB;
   2195       a->min_unsplittable_sblock_szB = MAX_PSZB;
   2196       base_p = VG_(arena_malloc) ( aid, cc, base_pszB_req );
   2197       a->min_unsplittable_sblock_szB = save_min_unsplittable_sblock_szB;
   2198    }
   2199    a->stats__bytes_on_loan = saved_bytes_on_loan;
   2200 
   2201    /* Give up if we couldn't allocate enough space */
   2202    if (base_p == 0)
   2203       return 0;
   2204    /* base_p was marked as allocated by VALGRIND_MALLOCLIKE_BLOCK
   2205       inside VG_(arena_malloc). We need to indicate it is free, then
   2206       we need to mark it undefined to allow the below code to access is. */
   2207    INNER_REQUEST(VALGRIND_FREELIKE_BLOCK(base_p, a->rz_szB));
   2208    INNER_REQUEST(VALGRIND_MAKE_MEM_UNDEFINED(base_p, base_pszB_req));
   2209 
   2210    /* Block ptr for the block we are going to split. */
   2211    base_b = get_payload_block ( a, base_p );
   2212 
   2213    /* Pointer to the payload of the aligned block we are going to
   2214       return.  This has to be suitably aligned. */
   2215    align_p = align_upwards ( base_b + 2 * overhead_szB_lo(a)
   2216                                     + overhead_szB_hi(a),
   2217                              req_alignB );
   2218    align_b = get_payload_block(a, align_p);
   2219 
   2220    /* The block size of the fragment we will create.  This must be big
   2221       enough to actually create a fragment. */
   2222    frag_bszB = align_b - base_b;
   2223 
   2224    vg_assert(frag_bszB >= min_useful_bszB(a));
   2225 
   2226    /* The actual payload size of the block we are going to split. */
   2227    base_pszB_act = get_pszB(a, base_b);
   2228 
   2229    /* Create the fragment block, and put it back on the relevant free list. */
   2230    mkFreeBlock ( a, base_b, frag_bszB,
   2231                  pszB_to_listNo(bszB_to_pszB(a, frag_bszB)) );
   2232    if (VG_(clo_profile_heap))
   2233       set_cc(base_b, "admin.frag-memalign-1");
   2234 
   2235    /* Create the aligned block. */
   2236    mkInuseBlock ( a, align_b,
   2237                   base_p + base_pszB_act
   2238                          + overhead_szB_hi(a) - (UByte*)align_b );
   2239    if (VG_(clo_profile_heap))
   2240       set_cc(align_b, cc);
   2241 
   2242    /* Final sanity checks. */
   2243    vg_assert( is_inuse_block(get_payload_block(a, align_p)) );
   2244 
   2245    vg_assert(req_pszB <= get_pszB(a, get_payload_block(a, align_p)));
   2246 
   2247    a->stats__bytes_on_loan += get_pszB(a, get_payload_block(a, align_p));
   2248    if (a->stats__bytes_on_loan > a->stats__bytes_on_loan_max) {
   2249       a->stats__bytes_on_loan_max = a->stats__bytes_on_loan;
   2250    }
   2251    /* a->stats__tot_blocks, a->stats__tot_bytes, a->stats__nsearches
   2252       are updated by the call to VG_(arena_malloc) just a few lines
   2253       above.  So we don't need to update them here. */
   2254 
   2255 #  ifdef DEBUG_MALLOC
   2256    sanity_check_malloc_arena(aid);
   2257 #  endif
   2258 
   2259    vg_assert( (((Addr)align_p) % req_alignB) == 0 );
   2260 
   2261    INNER_REQUEST(VALGRIND_MALLOCLIKE_BLOCK(align_p,
   2262                                            req_pszB, a->rz_szB, False));
   2263 
   2264    return align_p;
   2265 }
   2266 
   2267 
   2268 SizeT VG_(arena_malloc_usable_size) ( ArenaId aid, void* ptr )
   2269 {
   2270    Arena* a = arenaId_to_ArenaP(aid);
   2271    Block* b = get_payload_block(a, ptr);
   2272    return get_pszB(a, b);
   2273 }
   2274 
   2275 
   2276 // Implementation of mallinfo(). There is no recent standard that defines
   2277 // the behavior of mallinfo(). The meaning of the fields in struct mallinfo
   2278 // is as follows:
   2279 //
   2280 //     struct mallinfo  {
   2281 //                int arena;     /* total space in arena            */
   2282 //                int ordblks;   /* number of ordinary blocks       */
   2283 //                int smblks;    /* number of small blocks          */
   2284 //                int hblks;     /* number of holding blocks        */
   2285 //                int hblkhd;    /* space in holding block headers  */
   2286 //                int usmblks;   /* space in small blocks in use    */
   2287 //                int fsmblks;   /* space in free small blocks      */
   2288 //                int uordblks;  /* space in ordinary blocks in use */
   2289 //                int fordblks;  /* space in free ordinary blocks   */
   2290 //                int keepcost;  /* space penalty if keep option    */
   2291 //                               /* is used                         */
   2292 //        };
   2293 //
   2294 // The glibc documentation about mallinfo (which is somewhat outdated) can
   2295 // be found here:
   2296 // http://www.gnu.org/software/libtool/manual/libc/Statistics-of-Malloc.html
   2297 //
   2298 // See also http://bugs.kde.org/show_bug.cgi?id=160956.
   2299 //
   2300 // Regarding the implementation of VG_(mallinfo)(): we cannot return the
   2301 // whole struct as the library function does, because this is called by a
   2302 // client request.  So instead we use a pointer to do call by reference.
   2303 void VG_(mallinfo) ( ThreadId tid, struct vg_mallinfo* mi )
   2304 {
   2305    UWord  i, free_blocks, free_blocks_size;
   2306    Arena* a = arenaId_to_ArenaP(VG_AR_CLIENT);
   2307 
   2308    // Traverse free list and calculate free blocks statistics.
   2309    // This may seem slow but glibc works the same way.
   2310    free_blocks_size = free_blocks = 0;
   2311    for (i = 0; i < N_MALLOC_LISTS; i++) {
   2312       Block* b = a->freelist[i];
   2313       if (b == NULL) continue;
   2314       for (;;) {
   2315          free_blocks++;
   2316          free_blocks_size += (UWord)get_pszB(a, b);
   2317          b = get_next_b(b);
   2318          if (b == a->freelist[i]) break;
   2319       }
   2320    }
   2321 
   2322    // We don't have fastbins so smblks & fsmblks are always 0. Also we don't
   2323    // have a separate mmap allocator so set hblks & hblkhd to 0.
   2324    mi->arena    = a->stats__bytes_mmaped;
   2325    mi->ordblks  = free_blocks + VG_(free_queue_length);
   2326    mi->smblks   = 0;
   2327    mi->hblks    = 0;
   2328    mi->hblkhd   = 0;
   2329    mi->usmblks  = 0;
   2330    mi->fsmblks  = 0;
   2331    mi->uordblks = a->stats__bytes_on_loan - VG_(free_queue_volume);
   2332    mi->fordblks = free_blocks_size + VG_(free_queue_volume);
   2333    mi->keepcost = 0; // may want some value in here
   2334 }
   2335 
   2336 SizeT VG_(arena_redzone_size) ( ArenaId aid )
   2337 {
   2338    ensure_mm_init (VG_AR_CLIENT);
   2339    /*  ensure_mm_init will call arena_init if not yet done.
   2340        This then ensures that the arena redzone size is properly
   2341        initialised. */
   2342    return arenaId_to_ArenaP(aid)->rz_szB;
   2343 }
   2344 
   2345 /*------------------------------------------------------------*/
   2346 /*--- Services layered on top of malloc/free.              ---*/
   2347 /*------------------------------------------------------------*/
   2348 
   2349 void* VG_(arena_calloc) ( ArenaId aid, const HChar* cc,
   2350                           SizeT nmemb, SizeT bytes_per_memb )
   2351 {
   2352    SizeT  size;
   2353    void*  p;
   2354 
   2355    size = nmemb * bytes_per_memb;
   2356    vg_assert(size >= nmemb && size >= bytes_per_memb);// check against overflow
   2357 
   2358    p = VG_(arena_malloc) ( aid, cc, size );
   2359 
   2360    if (p != NULL)
   2361      VG_(memset)(p, 0, size);
   2362 
   2363    return p;
   2364 }
   2365 
   2366 
   2367 void* VG_(arena_realloc) ( ArenaId aid, const HChar* cc,
   2368                            void* ptr, SizeT req_pszB )
   2369 {
   2370    Arena* a;
   2371    SizeT  old_pszB;
   2372    void*  p_new;
   2373    Block* b;
   2374 
   2375    ensure_mm_init(aid);
   2376    a = arenaId_to_ArenaP(aid);
   2377 
   2378    vg_assert(req_pszB < MAX_PSZB);
   2379 
   2380    if (NULL == ptr) {
   2381       return VG_(arena_malloc)(aid, cc, req_pszB);
   2382    }
   2383 
   2384    if (req_pszB == 0) {
   2385       VG_(arena_free)(aid, ptr);
   2386       return NULL;
   2387    }
   2388 
   2389    b = get_payload_block(a, ptr);
   2390    vg_assert(blockSane(a, b));
   2391 
   2392    vg_assert(is_inuse_block(b));
   2393    old_pszB = get_pszB(a, b);
   2394 
   2395    if (req_pszB <= old_pszB) {
   2396       return ptr;
   2397    }
   2398 
   2399    p_new = VG_(arena_malloc) ( aid, cc, req_pszB );
   2400 
   2401    VG_(memcpy)(p_new, ptr, old_pszB);
   2402 
   2403    VG_(arena_free)(aid, ptr);
   2404 
   2405    return p_new;
   2406 }
   2407 
   2408 
   2409 void VG_(arena_realloc_shrink) ( ArenaId aid,
   2410                                  void* ptr, SizeT req_pszB )
   2411 {
   2412    SizeT  req_bszB, frag_bszB, b_bszB;
   2413    Superblock* sb;
   2414    Arena* a;
   2415    SizeT  old_pszB;
   2416    Block* b;
   2417 
   2418    ensure_mm_init(aid);
   2419 
   2420    a = arenaId_to_ArenaP(aid);
   2421    b = get_payload_block(a, ptr);
   2422    vg_assert(blockSane(a, b));
   2423    vg_assert(is_inuse_block(b));
   2424 
   2425    old_pszB = get_pszB(a, b);
   2426    req_pszB = align_req_pszB(req_pszB);
   2427    vg_assert(old_pszB >= req_pszB);
   2428    if (old_pszB == req_pszB)
   2429       return;
   2430 
   2431    sb = findSb( a, b );
   2432    if (sb->unsplittable) {
   2433       const UByte* sb_start = &sb->payload_bytes[0];
   2434       const UByte* sb_end = &sb->payload_bytes[sb->n_payload_bytes - 1];
   2435       Addr  frag;
   2436 
   2437       vg_assert(unsplittableBlockSane(a, sb, b));
   2438 
   2439       frag = VG_PGROUNDUP((Addr) sb
   2440                           + sizeof(Superblock) + pszB_to_bszB(a, req_pszB));
   2441       frag_bszB = (Addr)sb_end - frag + 1;
   2442 
   2443       if (frag_bszB >= VKI_PAGE_SIZE) {
   2444          SysRes sres;
   2445 
   2446          a->stats__bytes_on_loan -= old_pszB;
   2447          b_bszB = (UByte*)frag - sb_start;
   2448          shrinkInuseBlock(a, b, b_bszB);
   2449          INNER_REQUEST
   2450             (VALGRIND_RESIZEINPLACE_BLOCK(ptr,
   2451                                           old_pszB,
   2452                                           VG_(arena_malloc_usable_size)(aid, ptr),
   2453                                           a->rz_szB));
   2454          /* Have the minimum admin headers needed accessibility. */
   2455          INNER_REQUEST(mkBhdrSzAccess(a, b));
   2456          a->stats__bytes_on_loan += bszB_to_pszB(a, b_bszB);
   2457 
   2458          sb->n_payload_bytes -= frag_bszB;
   2459          VG_(debugLog)(1, "mallocfree",
   2460                        "shrink superblock %p to (pszB %7ld) "
   2461                        "owner %s/%s (munmap-ing %p %7ld)\n",
   2462                        sb, sb->n_payload_bytes,
   2463                        a->clientmem ? "CLIENT" : "VALGRIND", a->name,
   2464                        (void*) frag, frag_bszB);
   2465          if (a->clientmem) {
   2466             Bool need_discard = False;
   2467             sres = VG_(am_munmap_client)(&need_discard,
   2468                                          frag,
   2469                                          frag_bszB);
   2470             vg_assert (!need_discard);
   2471          } else {
   2472             sres = VG_(am_munmap_valgrind)(frag,
   2473                                            frag_bszB);
   2474          }
   2475          vg_assert2(! sr_isError(sres), "shrink superblock munmap failure\n");
   2476          a->stats__bytes_mmaped -= frag_bszB;
   2477 
   2478          vg_assert(unsplittableBlockSane(a, sb, b));
   2479       }
   2480    } else {
   2481       req_bszB = pszB_to_bszB(a, req_pszB);
   2482       b_bszB = get_bszB(b);
   2483       frag_bszB = b_bszB - req_bszB;
   2484       if (frag_bszB < min_useful_bszB(a))
   2485          return;
   2486 
   2487       a->stats__bytes_on_loan -= old_pszB;
   2488       shrinkInuseBlock(a, b, req_bszB);
   2489       INNER_REQUEST
   2490          (VALGRIND_RESIZEINPLACE_BLOCK(ptr,
   2491                                        old_pszB,
   2492                                        VG_(arena_malloc_usable_size)(aid, ptr),
   2493                                        a->rz_szB));
   2494       /* Have the minimum admin headers needed accessibility. */
   2495       INNER_REQUEST(mkBhdrSzAccess(a, b));
   2496 
   2497       mkFreeBlock(a, &b[req_bszB], frag_bszB,
   2498                   pszB_to_listNo(bszB_to_pszB(a, frag_bszB)));
   2499       /* Mark the admin headers as accessible. */
   2500       INNER_REQUEST(mkBhdrAccess(a, &b[req_bszB]));
   2501       if (VG_(clo_profile_heap))
   2502          set_cc(&b[req_bszB], "admin.fragmentation-2");
   2503       /* Possibly merge &b[req_bszB] with its free neighbours. */
   2504       mergeWithFreeNeighbours(a, sb, &b[req_bszB], frag_bszB);
   2505 
   2506       b_bszB = get_bszB(b);
   2507       a->stats__bytes_on_loan += bszB_to_pszB(a, b_bszB);
   2508    }
   2509 
   2510    vg_assert (blockSane(a, b));
   2511 #  ifdef DEBUG_MALLOC
   2512    sanity_check_malloc_arena(aid);
   2513 #  endif
   2514 }
   2515 
   2516 /* Inline just for the wrapper VG_(strdup) below */
   2517 __inline__ HChar* VG_(arena_strdup) ( ArenaId aid, const HChar* cc,
   2518                                       const HChar* s )
   2519 {
   2520    Int   i;
   2521    Int   len;
   2522    HChar* res;
   2523 
   2524    if (s == NULL)
   2525       return NULL;
   2526 
   2527    len = VG_(strlen)(s) + 1;
   2528    res = VG_(arena_malloc) (aid, cc, len);
   2529 
   2530    for (i = 0; i < len; i++)
   2531       res[i] = s[i];
   2532    return res;
   2533 }
   2534 
   2535 void* VG_(arena_perm_malloc) ( ArenaId aid, SizeT size, Int align  )
   2536 {
   2537    Arena*      a;
   2538 
   2539    ensure_mm_init(aid);
   2540    a = arenaId_to_ArenaP(aid);
   2541 
   2542    align = align - 1;
   2543    size = (size + align) & ~align;
   2544 
   2545    if (UNLIKELY(a->perm_malloc_current + size > a->perm_malloc_limit)) {
   2546       // Get a superblock, but we will not insert it into the superblock list.
   2547       // The superblock structure is not needed, so we will use the full
   2548       // memory range of it. This superblock is however counted in the
   2549       // mmaped statistics.
   2550       Superblock* new_sb = newSuperblock (a, size);
   2551       a->perm_malloc_limit = (Addr)&new_sb->payload_bytes[new_sb->n_payload_bytes - 1];
   2552 
   2553       // We do not mind starting allocating from the beginning of the superblock
   2554       // as afterwards, we "lose" it as a superblock.
   2555       a->perm_malloc_current = (Addr)new_sb;
   2556    }
   2557 
   2558    a->stats__perm_blocks += 1;
   2559    a->stats__perm_bytes_on_loan  += size;
   2560    add_one_block_to_stats (a, size);
   2561 
   2562    a->perm_malloc_current        += size;
   2563    return (void*)(a->perm_malloc_current - size);
   2564 }
   2565 
   2566 /*------------------------------------------------------------*/
   2567 /*--- Tool-visible functions.                              ---*/
   2568 /*------------------------------------------------------------*/
   2569 
   2570 // All just wrappers to avoid exposing arenas to tools.
   2571 
   2572 // This function never returns NULL.
   2573 void* VG_(malloc) ( const HChar* cc, SizeT nbytes )
   2574 {
   2575    return VG_(arena_malloc) ( VG_AR_CORE, cc, nbytes );
   2576 }
   2577 
   2578 void  VG_(free) ( void* ptr )
   2579 {
   2580    VG_(arena_free) ( VG_AR_CORE, ptr );
   2581 }
   2582 
   2583 void* VG_(calloc) ( const HChar* cc, SizeT nmemb, SizeT bytes_per_memb )
   2584 {
   2585    return VG_(arena_calloc) ( VG_AR_CORE, cc, nmemb, bytes_per_memb );
   2586 }
   2587 
   2588 void* VG_(realloc) ( const HChar* cc, void* ptr, SizeT size )
   2589 {
   2590    return VG_(arena_realloc) ( VG_AR_CORE, cc, ptr, size );
   2591 }
   2592 
   2593 void VG_(realloc_shrink) ( void* ptr, SizeT size )
   2594 {
   2595    VG_(arena_realloc_shrink) ( VG_AR_CORE, ptr, size );
   2596 }
   2597 
   2598 HChar* VG_(strdup) ( const HChar* cc, const HChar* s )
   2599 {
   2600    return VG_(arena_strdup) ( VG_AR_CORE, cc, s );
   2601 }
   2602 
   2603 void* VG_(perm_malloc) ( SizeT size, Int align  )
   2604 {
   2605    return VG_(arena_perm_malloc) ( VG_AR_CORE, size, align );
   2606 }
   2607 
   2608 
   2609 /*--------------------------------------------------------------------*/
   2610 /*--- end                                                          ---*/
   2611 /*--------------------------------------------------------------------*/
   2612