2 /*--------------------------------------------------------------------*/
3 /*--- An implementation of malloc/free which doesn't use sbrk. ---*/
4 /*--- m_mallocfree.c ---*/
5 /*--------------------------------------------------------------------*/
8 This file is part of Valgrind, a dynamic binary instrumentation
11 Copyright (C) 2000-2010 Julian Seward
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.
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.
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
29 The GNU General Public License is contained in the file COPYING.
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_libcsetjmp.h" // to keep _threadstate.h happy
42 #include "pub_core_threadstate.h" // For VG_INVALID_THREADID
43 #include "pub_core_tooliface.h"
46 //zz#include "memcheck/memcheck.h"
48 // #define DEBUG_MALLOC // turn on heavyweight debugging machinery
49 // #define VERBOSE_MALLOC // make verbose, esp. in debugging machinery
51 /* Number and total size of blocks in free queue. Used by mallinfo(). */
52 Long VG_(free_queue_volume) = 0;
53 Long VG_(free_queue_length) = 0;
55 static void cc_analyse_alloc_arena ( ArenaId aid ); /* fwds */
57 /*------------------------------------------------------------*/
58 /*--- Main types ---*/
59 /*------------------------------------------------------------*/
61 #define N_MALLOC_LISTS 112 // do not change this
63 // The amount you can ask for is limited only by sizeof(SizeT)...
64 #define MAX_PSZB (~((SizeT)0x0))
66 // Each arena has a sorted array of superblocks, which expands
67 // dynamically. This is its initial size.
68 #define SBLOCKS_SIZE_INITIAL 50
72 /* Layout of an in-use block:
74 cost center (OPTIONAL) (VG_MIN_MALLOC_SZB bytes, only when h-p enabled)
75 this block total szB (sizeof(SizeT) bytes)
76 red zone bytes (depends on Arena.rz_szB, but >= sizeof(void*))
78 red zone bytes (depends on Arena.rz_szB, but >= sizeof(void*))
79 this block total szB (sizeof(SizeT) bytes)
81 Layout of a block on the free list:
83 cost center (OPTIONAL) (VG_MIN_MALLOC_SZB bytes, only when h-p enabled)
84 this block total szB (sizeof(SizeT) bytes)
85 freelist previous ptr (sizeof(void*) bytes)
86 excess red zone bytes (if Arena.rz_szB > sizeof(void*))
88 excess red zone bytes (if Arena.rz_szB > sizeof(void*))
89 freelist next ptr (sizeof(void*) bytes)
90 this block total szB (sizeof(SizeT) bytes)
92 Total size in bytes (bszB) and payload size in bytes (pszB)
95 bszB == pszB + 2*sizeof(SizeT) + 2*a->rz_szB
97 when heap profiling is not enabled, and
99 bszB == pszB + 2*sizeof(SizeT) + 2*a->rz_szB + VG_MIN_MALLOC_SZB
101 when it is enabled. It follows that the minimum overhead per heap
102 block for arenas used by the core is:
104 32-bit platforms: 2*4 + 2*4 == 16 bytes
105 64-bit platforms: 2*8 + 2*8 == 32 bytes
107 when heap profiling is not enabled, and
109 32-bit platforms: 2*4 + 2*4 + 8 == 24 bytes
110 64-bit platforms: 2*8 + 2*8 + 16 == 48 bytes
112 when it is enabled. In all cases, extra overhead may be incurred
113 when rounding the payload size up to VG_MIN_MALLOC_SZB.
115 Furthermore, both size fields in the block have their least-significant
116 bit set if the block is not in use, and unset if it is in use.
117 (The bottom 3 or so bits are always free for this because of alignment.)
118 A block size of zero is not possible, because a block always has at
119 least two SizeTs and two pointers of overhead.
121 Nb: All Block payloads must be VG_MIN_MALLOC_SZB-aligned. This is
122 achieved by ensuring that Superblocks are VG_MIN_MALLOC_SZB-aligned
123 (see newSuperblock() for how), and that the lengths of the following
124 things are a multiple of VG_MIN_MALLOC_SZB:
125 - Superblock admin section lengths (due to elastic padding)
126 - Block admin section (low and high) lengths (due to elastic redzones)
127 - Block payload lengths (due to req_pszB rounding up)
129 The heap-profile cost-center field is 8 bytes even on 32 bit
130 platforms. This is so as to keep the payload field 8-aligned. On
131 a 64-bit platform, this cc-field contains a pointer to a const
132 HChar*, which is the cost center name. On 32-bit platforms, the
133 pointer lives in the lower-addressed half of the field, regardless
134 of the endianness of the host.
138 // No fields are actually used in this struct, because a Block has
139 // many variable sized fields and so can't be accessed
140 // meaningfully with normal fields. So we use access functions all
141 // the time. This struct gives us a type to use, though. Also, we
142 // make sizeof(Block) 1 byte so that we can do arithmetic with the
143 // Block* type in increments of 1!
148 // A superblock. 'padding' is never used, it just ensures that if the
149 // entire Superblock is aligned to VG_MIN_MALLOC_SZB, then payload_bytes[]
150 // will be too. It can add small amounts of padding unnecessarily -- eg.
151 // 8-bytes on 32-bit machines with an 8-byte VG_MIN_MALLOC_SZB -- because
152 // it's too hard to make a constant expression that works perfectly in all
154 // payload_bytes[] is made a single big Block when the Superblock is
155 // created, and then can be split and the splittings remerged, but Blocks
156 // always cover its entire length -- there's never any unused bytes at the
160 SizeT n_payload_bytes;
162 UByte padding[ VG_MIN_MALLOC_SZB -
163 ((sizeof(struct _Superblock*) + sizeof(SizeT)) %
164 VG_MIN_MALLOC_SZB) ];
165 UByte payload_bytes[0];
169 // An arena. 'freelist' is a circular, doubly-linked list. 'rz_szB' is
170 // elastic, in that it can be bigger than asked-for to ensure alignment.
174 Bool clientmem; // Allocates in the client address space?
175 SizeT rz_szB; // Red zone size in bytes
176 SizeT min_sblock_szB; // Minimum superblock size in bytes
177 Block* freelist[N_MALLOC_LISTS];
178 // A dynamically expanding, ordered array of (pointers to)
179 // superblocks in the arena. If this array is expanded, which
180 // is rare, the previous space it occupies is simply abandoned.
181 // To avoid having to get yet another block from m_aspacemgr for
182 // the first incarnation of this array, the first allocation of
183 // it is within this struct. If it has to be expanded then the
184 // new space is acquired from m_aspacemgr as you would expect.
185 Superblock** sblocks;
188 Superblock* sblocks_initial[SBLOCKS_SIZE_INITIAL];
190 SizeT stats__bytes_on_loan;
191 SizeT stats__bytes_mmaped;
192 SizeT stats__bytes_on_loan_max;
193 ULong stats__tot_blocks; /* total # blocks alloc'd */
194 ULong stats__tot_bytes; /* total # bytes alloc'd */
195 ULong stats__nsearches; /* total # freelist checks */
196 // If profiling, when should the next profile happen at
197 // (in terms of stats__bytes_on_loan_max) ?
198 SizeT next_profile_at;
203 /*------------------------------------------------------------*/
204 /*--- Low-level functions for working with Blocks. ---*/
205 /*------------------------------------------------------------*/
207 #define SIZE_T_0x1 ((SizeT)0x1)
209 static char* probably_your_fault =
210 "This is probably caused by your program erroneously writing past the\n"
211 "end of a heap block and corrupting heap metadata. If you fix any\n"
212 "invalid writes reported by Memcheck, this assertion failure will\n"
213 "probably go away. Please try that before reporting this as a bug.\n";
215 // Mark a bszB as in-use, and not in-use, and remove the in-use attribute.
217 SizeT mk_inuse_bszB ( SizeT bszB )
219 vg_assert2(bszB != 0, probably_your_fault);
220 return bszB & (~SIZE_T_0x1);
223 SizeT mk_free_bszB ( SizeT bszB )
225 vg_assert2(bszB != 0, probably_your_fault);
226 return bszB | SIZE_T_0x1;
229 SizeT mk_plain_bszB ( SizeT bszB )
231 vg_assert2(bszB != 0, probably_your_fault);
232 return bszB & (~SIZE_T_0x1);
235 // return either 0 or sizeof(ULong) depending on whether or not
236 // heap profiling is engaged
238 SizeT hp_overhead_szB ( void )
240 return VG_(clo_profile_heap) ? VG_MIN_MALLOC_SZB : 0;
243 //---------------------------------------------------------------------------
245 // Get a block's size as stored, ie with the in-use/free attribute.
247 SizeT get_bszB_as_is ( Block* b )
249 UByte* b2 = (UByte*)b;
250 SizeT bszB_lo = *(SizeT*)&b2[0 + hp_overhead_szB()];
251 SizeT bszB_hi = *(SizeT*)&b2[mk_plain_bszB(bszB_lo) - sizeof(SizeT)];
252 vg_assert2(bszB_lo == bszB_hi,
253 "Heap block lo/hi size mismatch: lo = %llu, hi = %llu.\n%s",
254 (ULong)bszB_lo, (ULong)bszB_hi, probably_your_fault);
258 // Get a block's plain size, ie. remove the in-use/free attribute.
260 SizeT get_bszB ( Block* b )
262 return mk_plain_bszB(get_bszB_as_is(b));
265 // Set the size fields of a block. bszB may have the in-use/free attribute.
267 void set_bszB ( Block* b, SizeT bszB )
269 UByte* b2 = (UByte*)b;
270 *(SizeT*)&b2[0 + hp_overhead_szB()] = bszB;
271 *(SizeT*)&b2[mk_plain_bszB(bszB) - sizeof(SizeT)] = bszB;
274 //---------------------------------------------------------------------------
276 // Does this block have the in-use attribute?
278 Bool is_inuse_block ( Block* b )
280 SizeT bszB = get_bszB_as_is(b);
281 vg_assert2(bszB != 0, probably_your_fault);
282 return (0 != (bszB & SIZE_T_0x1)) ? False : True;
285 //---------------------------------------------------------------------------
287 // Return the lower, upper and total overhead in bytes for a block.
288 // These are determined purely by which arena the block lives in.
290 SizeT overhead_szB_lo ( Arena* a )
292 return hp_overhead_szB() + sizeof(SizeT) + a->rz_szB;
295 SizeT overhead_szB_hi ( Arena* a )
297 return a->rz_szB + sizeof(SizeT);
300 SizeT overhead_szB ( Arena* a )
302 return overhead_szB_lo(a) + overhead_szB_hi(a);
305 //---------------------------------------------------------------------------
307 // Return the minimum bszB for a block in this arena. Can have zero-length
308 // payloads, so it's the size of the admin bytes.
310 SizeT min_useful_bszB ( Arena* a )
312 return overhead_szB(a);
315 //---------------------------------------------------------------------------
317 // Convert payload size <--> block size (both in bytes).
319 SizeT pszB_to_bszB ( Arena* a, SizeT pszB )
321 return pszB + overhead_szB(a);
324 SizeT bszB_to_pszB ( Arena* a, SizeT bszB )
326 vg_assert2(bszB >= overhead_szB(a), probably_your_fault);
327 return bszB - overhead_szB(a);
330 //---------------------------------------------------------------------------
332 // Get a block's payload size.
334 SizeT get_pszB ( Arena* a, Block* b )
336 return bszB_to_pszB(a, get_bszB(b));
339 //---------------------------------------------------------------------------
341 // Given the addr of a block, return the addr of its payload, and vice versa.
343 UByte* get_block_payload ( Arena* a, Block* b )
345 UByte* b2 = (UByte*)b;
346 return & b2[ overhead_szB_lo(a) ];
348 // Given the addr of a block's payload, return the addr of the block itself.
350 Block* get_payload_block ( Arena* a, UByte* payload )
352 return (Block*)&payload[ -overhead_szB_lo(a) ];
355 //---------------------------------------------------------------------------
357 // Set and get the next and previous link fields of a block.
359 void set_prev_b ( Block* b, Block* prev_p )
361 UByte* b2 = (UByte*)b;
362 *(Block**)&b2[hp_overhead_szB() + sizeof(SizeT)] = prev_p;
365 void set_next_b ( Block* b, Block* next_p )
367 UByte* b2 = (UByte*)b;
368 *(Block**)&b2[get_bszB(b) - sizeof(SizeT) - sizeof(void*)] = next_p;
371 Block* get_prev_b ( Block* b )
373 UByte* b2 = (UByte*)b;
374 return *(Block**)&b2[hp_overhead_szB() + sizeof(SizeT)];
377 Block* get_next_b ( Block* b )
379 UByte* b2 = (UByte*)b;
380 return *(Block**)&b2[get_bszB(b) - sizeof(SizeT) - sizeof(void*)];
383 //---------------------------------------------------------------------------
385 // Set and get the cost-center field of a block.
387 void set_cc ( Block* b, HChar* cc )
389 UByte* b2 = (UByte*)b;
390 vg_assert( VG_(clo_profile_heap) );
391 *(HChar**)&b2[0] = cc;
394 HChar* get_cc ( Block* b )
396 UByte* b2 = (UByte*)b;
397 vg_assert( VG_(clo_profile_heap) );
398 return *(HChar**)&b2[0];
401 //---------------------------------------------------------------------------
403 // Get the block immediately preceding this one in the Superblock.
405 Block* get_predecessor_block ( Block* b )
407 UByte* b2 = (UByte*)b;
408 SizeT bszB = mk_plain_bszB( (*(SizeT*)&b2[-sizeof(SizeT)]) );
409 return (Block*)&b2[-bszB];
412 //---------------------------------------------------------------------------
414 // Read and write the lower and upper red-zone bytes of a block.
416 void set_rz_lo_byte ( Block* b, UInt rz_byteno, UByte v )
418 UByte* b2 = (UByte*)b;
419 b2[hp_overhead_szB() + sizeof(SizeT) + rz_byteno] = v;
422 void set_rz_hi_byte ( Block* b, UInt rz_byteno, UByte v )
424 UByte* b2 = (UByte*)b;
425 b2[get_bszB(b) - sizeof(SizeT) - rz_byteno - 1] = v;
428 UByte get_rz_lo_byte ( Block* b, UInt rz_byteno )
430 UByte* b2 = (UByte*)b;
431 return b2[hp_overhead_szB() + sizeof(SizeT) + rz_byteno];
434 UByte get_rz_hi_byte ( Block* b, UInt rz_byteno )
436 UByte* b2 = (UByte*)b;
437 return b2[get_bszB(b) - sizeof(SizeT) - rz_byteno - 1];
441 /*------------------------------------------------------------*/
442 /*--- Arena management ---*/
443 /*------------------------------------------------------------*/
445 #define CORE_ARENA_MIN_SZB 1048576
447 // The arena structures themselves.
448 static Arena vg_arena[VG_N_ARENAS];
450 // Functions external to this module identify arenas using ArenaIds,
451 // not Arena*s. This fn converts the former to the latter.
452 static Arena* arenaId_to_ArenaP ( ArenaId arena )
454 vg_assert(arena >= 0 && arena < VG_N_ARENAS);
455 return & vg_arena[arena];
458 // Initialise an arena. rz_szB is the minimum redzone size; it might be
459 // made bigger to ensure that VG_MIN_MALLOC_SZB is observed.
461 void arena_init ( ArenaId aid, Char* name, SizeT rz_szB, SizeT min_sblock_szB )
464 Arena* a = arenaId_to_ArenaP(aid);
466 // Ensure redzones are a reasonable size. They must always be at least
467 // the size of a pointer, for holding the prev/next pointer (see the layout
468 // details at the top of this file).
469 vg_assert(rz_szB < 128);
470 if (rz_szB < sizeof(void*)) rz_szB = sizeof(void*);
472 vg_assert((min_sblock_szB % VKI_PAGE_SIZE) == 0);
474 a->clientmem = ( VG_AR_CLIENT == aid ? True : False );
476 // The size of the low and high admin sections in a block must be a
477 // multiple of VG_MIN_MALLOC_SZB. So we round up the asked-for
478 // redzone size if necessary to achieve this.
480 while (0 != overhead_szB_lo(a) % VG_MIN_MALLOC_SZB) a->rz_szB++;
481 vg_assert(overhead_szB_lo(a) - hp_overhead_szB() == overhead_szB_hi(a));
483 a->min_sblock_szB = min_sblock_szB;
484 for (i = 0; i < N_MALLOC_LISTS; i++) a->freelist[i] = NULL;
486 a->sblocks = & a->sblocks_initial[0];
487 a->sblocks_size = SBLOCKS_SIZE_INITIAL;
489 a->stats__bytes_on_loan = 0;
490 a->stats__bytes_mmaped = 0;
491 a->stats__bytes_on_loan_max = 0;
492 a->stats__tot_blocks = 0;
493 a->stats__tot_bytes = 0;
494 a->stats__nsearches = 0;
495 a->next_profile_at = 25 * 1000 * 1000;
496 vg_assert(sizeof(a->sblocks_initial)
497 == SBLOCKS_SIZE_INITIAL * sizeof(Superblock*));
500 /* Print vital stats for an arena. */
501 void VG_(print_all_arena_stats) ( void )
504 for (i = 0; i < VG_N_ARENAS; i++) {
505 Arena* a = arenaId_to_ArenaP(i);
506 VG_(message)(Vg_DebugMsg,
507 "%8s: %8ld mmap'd, %8ld/%8ld max/curr, "
508 "%10llu/%10llu totalloc-blocks/bytes,"
509 " %10llu searches\n",
510 a->name, a->stats__bytes_mmaped,
511 a->stats__bytes_on_loan_max,
512 a->stats__bytes_on_loan,
513 a->stats__tot_blocks, a->stats__tot_bytes,
519 void VG_(print_arena_cc_analysis) ( void )
522 vg_assert( VG_(clo_profile_heap) );
523 for (i = 0; i < VG_N_ARENAS; i++) {
524 cc_analyse_alloc_arena(i);
529 /* This library is self-initialising, as it makes this more self-contained,
530 less coupled with the outside world. Hence VG_(arena_malloc)() and
531 VG_(arena_free)() below always call ensure_mm_init() to ensure things are
532 correctly initialised.
534 We initialise the client arena separately (and later) because the core
535 must do non-client allocation before the tool has a chance to set the
536 client arena's redzone size.
538 static Bool client_inited = False;
539 static Bool nonclient_inited = False;
542 void ensure_mm_init ( ArenaId aid )
544 static SizeT client_rz_szB = 8; // default: be paranoid
546 /* We use checked red zones (of various sizes) for our internal stuff,
547 and an unchecked zone of arbitrary size for the client. Of
548 course the client's red zone can be checked by the tool, eg.
549 by using addressibility maps, but not by the mechanism implemented
550 here, which merely checks at the time of freeing that the red
551 zone bytes are unchanged.
553 Nb: redzone sizes are *minimums*; they could be made bigger to ensure
554 alignment. Eg. with 8 byte alignment, on 32-bit machines 4 stays as
555 4, but 16 becomes 20; but on 64-bit machines 4 becomes 8, and 16
556 stays as 16 --- the extra 4 bytes in both are accounted for by the
557 larger prev/next ptr.
559 if (VG_AR_CLIENT == aid) {
562 // This assertion ensures that a tool cannot try to change the client
563 // redzone size with VG_(needs_malloc_replacement)() after this module
564 // has done its first allocation from the client arena.
565 if (VG_(needs).malloc_replacement)
566 vg_assert(client_rz_szB == VG_(tdict).tool_client_redzone_szB);
570 // Check and set the client arena redzone size
571 if (VG_(needs).malloc_replacement) {
572 client_rz_szB = VG_(tdict).tool_client_redzone_szB;
573 // 128 is no special figure, just something not too big
574 if (client_rz_szB > 128) {
575 VG_(printf)( "\nTool error:\n"
576 " specified redzone size is too big (%llu)\n",
577 (ULong)client_rz_szB);
581 // Initialise the client arena. On AIX it's important to have
582 // relatively large client blocks so as not to cause excessively
583 // fine-grained interleaving of V and C address space. On Linux
584 // this is irrelevant since aspacem can keep the two spaces
585 // well apart, but not so on AIX. On all platforms though,
586 // increasing the superblock size reduces the number of superblocks
587 // in the client arena, which makes findSb cheaper.
588 # if defined(VGO_aix5)
589 ar_client_sbszB = 16777216;
591 ar_client_sbszB = 4194304;
593 arena_init ( VG_AR_CLIENT, "client", client_rz_szB, ar_client_sbszB );
594 client_inited = True;
597 if (nonclient_inited) {
600 // Initialise the non-client arenas
601 arena_init ( VG_AR_CORE, "core", 4, 1048576 );
602 arena_init ( VG_AR_TOOL, "tool", 4, 4194304 );
603 arena_init ( VG_AR_DINFO, "dinfo", 4, 1048576 );
604 arena_init ( VG_AR_DEMANGLE, "demangle", 4, 65536 );
605 arena_init ( VG_AR_EXECTXT, "exectxt", 4, 1048576 );
606 arena_init ( VG_AR_ERRORS, "errors", 4, 65536 );
607 arena_init ( VG_AR_TTAUX, "ttaux", 4, 65536 );
608 nonclient_inited = True;
612 VG_(printf)("ZZZ1\n");
613 VG_(sanity_check_malloc_all)();
614 VG_(printf)("ZZZ2\n");
619 /*------------------------------------------------------------*/
620 /*--- Superblock management ---*/
621 /*------------------------------------------------------------*/
623 __attribute__((noreturn))
624 void VG_(out_of_memory_NORETURN) ( HChar* who, SizeT szB )
626 static Bool alreadyCrashing = False;
627 ULong tot_alloc = VG_(am_get_anonsize_total)();
630 " Valgrind's memory management: out of memory:\n"
631 " %s's request for %llu bytes failed.\n"
632 " %llu bytes have already been allocated.\n"
633 " Valgrind cannot continue. Sorry.\n\n"
634 " There are several possible reasons for this.\n"
635 " - You have some kind of memory limit in place. Look at the\n"
636 " output of 'ulimit -a'. Is there a limit on the size of\n"
637 " virtual memory or address space?\n"
638 " - You have run out of swap space.\n"
639 " - Valgrind has a bug. If you think this is the case or you are\n"
640 " not sure, please let us know and we'll try to fix it.\n"
641 " Please note that programs can take substantially more memory than\n"
642 " normal when running under Valgrind tools, eg. up to twice or\n"
643 " more, depending on the tool. On a 64-bit machine, Valgrind\n"
644 " should be able to make use of up 32GB memory. On a 32-bit\n"
645 " machine, Valgrind should be able to use all the memory available\n"
646 " to a single process, up to 4GB if that's how you have your\n"
647 " kernel configured. Most 32-bit Linux setups allow a maximum of\n"
648 " 3GB per process.\n\n"
649 " Whatever the reason, Valgrind cannot continue. Sorry.\n";
651 if (!alreadyCrashing) {
652 alreadyCrashing = True;
653 VG_(message)(Vg_UserMsg, s1, who, (ULong)szB, tot_alloc);
655 VG_(debugLog)(0,"mallocfree", s1, who, (ULong)szB, tot_alloc);
662 // Align ptr p upwards to an align-sized boundary.
664 void* align_upwards ( void* p, SizeT align )
667 if ((a % align) == 0) return (void*)a;
668 return (void*)(a - (a % align) + align);
671 // If not enough memory available, either aborts (for non-client memory)
672 // or returns 0 (for client memory).
674 Superblock* newSuperblock ( Arena* a, SizeT cszB )
679 // Take into account admin bytes in the Superblock.
680 cszB += sizeof(Superblock);
682 if (cszB < a->min_sblock_szB) cszB = a->min_sblock_szB;
683 cszB = VG_PGROUNDUP(cszB);
686 // client allocation -- return 0 to client if it fails
687 sres = VG_(am_sbrk_anon_float_client)
688 ( cszB, VKI_PROT_READ|VKI_PROT_WRITE|VKI_PROT_EXEC );
689 if (sr_isError(sres))
691 sb = (Superblock*)(AddrH)sr_Res(sres);
692 // Mark this segment as containing client heap. The leak
693 // checker needs to be able to identify such segments so as not
694 // to use them as sources of roots during leak checks.
695 VG_(am_set_segment_isCH_if_SkAnonC)(
696 (NSegment*) VG_(am_find_nsegment)( (Addr)sb )
699 // non-client allocation -- abort if it fails
700 sres = VG_(am_sbrk_anon_float_valgrind)( cszB );
701 if (sr_isError(sres)) {
702 VG_(out_of_memory_NORETURN)("newSuperblock", cszB);
704 sb = NULL; /* keep gcc happy */
706 sb = (Superblock*)(AddrH)sr_Res(sres);
709 vg_assert(NULL != sb);
710 //zzVALGRIND_MAKE_MEM_UNDEFINED(sb, cszB);
711 vg_assert(0 == (Addr)sb % VG_MIN_MALLOC_SZB);
712 sb->n_payload_bytes = cszB - sizeof(Superblock);
713 a->stats__bytes_mmaped += cszB;
714 VG_(debugLog)(1, "mallocfree",
715 "newSuperblock at %p (pszB %7ld) owner %s/%s\n",
716 sb, sb->n_payload_bytes,
717 a->clientmem ? "CLIENT" : "VALGRIND", a->name );
721 // Find the superblock containing the given chunk.
723 Superblock* findSb ( Arena* a, Block* b )
726 SizeT max = a->sblocks_used;
730 SizeT pos = min + (max - min)/2;
732 vg_assert(pos >= 0 && pos < a->sblocks_used);
733 sb = a->sblocks[pos];
734 if ((Block*)&sb->payload_bytes[0] <= b
735 && b < (Block*)&sb->payload_bytes[sb->n_payload_bytes])
738 } else if ((Block*)&sb->payload_bytes[0] <= b) {
744 VG_(printf)("findSb: can't find pointer %p in arena '%s'\n",
746 VG_(core_panic)("findSb: VG_(arena_free)() in wrong arena?");
747 return NULL; /*NOTREACHED*/
751 /*------------------------------------------------------------*/
752 /*--- Functions for working with freelists. ---*/
753 /*------------------------------------------------------------*/
755 // Nb: Determination of which freelist a block lives on is based on the
756 // payload size, not block size.
758 // Convert a payload size in bytes to a freelist number.
760 UInt pszB_to_listNo ( SizeT pszB )
762 SizeT n = pszB / VG_MIN_MALLOC_SZB;
763 vg_assert(0 == pszB % VG_MIN_MALLOC_SZB);
765 // The first 64 lists hold blocks of size VG_MIN_MALLOC_SZB * list_num.
766 // The final 48 hold bigger blocks.
767 if (n < 64) return (UInt)n;
768 /* Exponential slope up, factor 1.05 */
769 if (n < 67) return 64;
770 if (n < 70) return 65;
771 if (n < 74) return 66;
772 if (n < 77) return 67;
773 if (n < 81) return 68;
774 if (n < 85) return 69;
775 if (n < 90) return 70;
776 if (n < 94) return 71;
777 if (n < 99) return 72;
778 if (n < 104) return 73;
779 if (n < 109) return 74;
780 if (n < 114) return 75;
781 if (n < 120) return 76;
782 if (n < 126) return 77;
783 if (n < 133) return 78;
784 if (n < 139) return 79;
785 /* Exponential slope up, factor 1.10 */
786 if (n < 153) return 80;
787 if (n < 169) return 81;
788 if (n < 185) return 82;
789 if (n < 204) return 83;
790 if (n < 224) return 84;
791 if (n < 247) return 85;
792 if (n < 272) return 86;
793 if (n < 299) return 87;
794 if (n < 329) return 88;
795 if (n < 362) return 89;
796 if (n < 398) return 90;
797 if (n < 438) return 91;
798 if (n < 482) return 92;
799 if (n < 530) return 93;
800 if (n < 583) return 94;
801 if (n < 641) return 95;
802 /* Exponential slope up, factor 1.20 */
803 if (n < 770) return 96;
804 if (n < 924) return 97;
805 if (n < 1109) return 98;
806 if (n < 1331) return 99;
807 if (n < 1597) return 100;
808 if (n < 1916) return 101;
809 if (n < 2300) return 102;
810 if (n < 2760) return 103;
811 if (n < 3312) return 104;
812 if (n < 3974) return 105;
813 if (n < 4769) return 106;
814 if (n < 5723) return 107;
815 if (n < 6868) return 108;
816 if (n < 8241) return 109;
817 if (n < 9890) return 110;
821 // What is the minimum payload size for a given list?
823 SizeT listNo_to_pszB_min ( UInt listNo )
825 /* Repeatedly computing this function at every request is
826 expensive. Hence at the first call just cache the result for
827 every possible argument. */
828 static SizeT cache[N_MALLOC_LISTS];
829 static Bool cache_valid = False;
832 for (i = 0; i < N_MALLOC_LISTS; i++) {
834 while (pszB_to_listNo(pszB) < i)
835 pszB += VG_MIN_MALLOC_SZB;
840 /* Returned cached answer. */
841 vg_assert(listNo <= N_MALLOC_LISTS);
842 return cache[listNo];
845 // What is the maximum payload size for a given list?
847 SizeT listNo_to_pszB_max ( UInt listNo )
849 vg_assert(listNo <= N_MALLOC_LISTS);
850 if (listNo == N_MALLOC_LISTS-1) {
853 return listNo_to_pszB_min(listNo+1) - 1;
858 /* A nasty hack to try and reduce fragmentation. Try and replace
859 a->freelist[lno] with another block on the same list but with a
860 lower address, with the idea of attempting to recycle the same
861 blocks rather than cruise through the address space. */
863 void swizzle ( Arena* a, UInt lno )
870 p_best = a->freelist[lno];
871 if (p_best == NULL) return;
875 // This loop bound was 20 for a long time, but experiments showed that
876 // reducing it to 10 gave the same result in all the tests, and 5 got the
877 // same result in 85--100% of cases. And it's called often enough to be
878 // noticeable in programs that allocated a lot.
879 for (i = 0; i < 5; i++) {
882 if (pn < p_best) p_best = pn;
883 if (pp < p_best) p_best = pp;
885 if (p_best < a->freelist[lno]) {
886 # ifdef VERBOSE_MALLOC
887 VG_(printf)("retreat by %ld\n", (Word)(a->freelist[lno] - p_best));
889 a->freelist[lno] = p_best;
894 /*------------------------------------------------------------*/
895 /*--- Sanity-check/debugging machinery. ---*/
896 /*------------------------------------------------------------*/
898 #define REDZONE_LO_MASK 0x31
899 #define REDZONE_HI_MASK 0x7c
901 // Do some crude sanity checks on a Block.
903 Bool blockSane ( Arena* a, Block* b )
905 # define BLEAT(str) VG_(printf)("blockSane: fail -- %s\n",str)
907 // The lo and hi size fields will be checked (indirectly) by the call
908 // to get_rz_hi_byte().
909 if (!a->clientmem && is_inuse_block(b)) {
910 for (i = 0; i < a->rz_szB; i++) {
911 if (get_rz_lo_byte(b, i) !=
912 (UByte)(((Addr)b&0xff) ^ REDZONE_LO_MASK))
913 {BLEAT("redzone-lo");return False;}
914 if (get_rz_hi_byte(b, i) !=
915 (UByte)(((Addr)b&0xff) ^ REDZONE_HI_MASK))
916 {BLEAT("redzone-hi");return False;}
923 // Print superblocks (only for debugging).
925 void ppSuperblocks ( Arena* a )
927 UInt i, j, blockno = 1;
930 for (j = 0; j < a->sblocks_used; ++j) {
931 Superblock * sb = a->sblocks[j];
934 VG_(printf)( "superblock %d at %p, sb->n_pl_bs = %lu\n",
935 blockno++, sb, sb->n_payload_bytes);
936 for (i = 0; i < sb->n_payload_bytes; i += b_bszB) {
937 Block* b = (Block*)&sb->payload_bytes[i];
938 b_bszB = get_bszB(b);
939 VG_(printf)( " block at %d, bszB %lu: ", i, b_bszB );
940 VG_(printf)( "%s, ", is_inuse_block(b) ? "inuse" : "free");
941 VG_(printf)( "%s\n", blockSane(a, b) ? "ok" : "BAD" );
943 vg_assert(i == sb->n_payload_bytes); // no overshoot at end of Sb
945 VG_(printf)( "end of superblocks\n\n" );
948 // Sanity check both the superblocks and the chains.
949 static void sanity_check_malloc_arena ( ArenaId aid )
951 UInt i, j, superblockctr, blockctr_sb, blockctr_li;
952 UInt blockctr_sb_free, listno;
953 SizeT b_bszB, b_pszB, list_min_pszB, list_max_pszB;
954 Bool thisFree, lastWasFree, sblockarrOK;
957 SizeT arena_bytes_on_loan;
960 # define BOMB VG_(core_panic)("sanity_check_malloc_arena")
962 a = arenaId_to_ArenaP(aid);
964 // Check the superblock array.
967 && a->sblocks_size >= SBLOCKS_SIZE_INITIAL
968 && a->sblocks_used <= a->sblocks_size
969 && (a->sblocks_size == SBLOCKS_SIZE_INITIAL
970 ? (a->sblocks == &a->sblocks_initial[0])
971 : (a->sblocks != &a->sblocks_initial[0]));
973 VG_(printf)("sanity_check_malloc_arena: sblock array BAD\n");
977 // First, traverse all the superblocks, inspecting the Blocks in each.
978 superblockctr = blockctr_sb = blockctr_sb_free = 0;
979 arena_bytes_on_loan = 0;
980 for (j = 0; j < a->sblocks_used; ++j) {
981 Superblock * sb = a->sblocks[j];
984 for (i = 0; i < sb->n_payload_bytes; i += mk_plain_bszB(b_bszB)) {
986 b = (Block*)&sb->payload_bytes[i];
987 b_bszB = get_bszB_as_is(b);
988 if (!blockSane(a, b)) {
989 VG_(printf)("sanity_check_malloc_arena: sb %p, block %d "
990 "(bszB %lu): BAD\n", sb, i, b_bszB );
993 thisFree = !is_inuse_block(b);
994 if (thisFree && lastWasFree) {
995 VG_(printf)("sanity_check_malloc_arena: sb %p, block %d "
996 "(bszB %lu): UNMERGED FREES\n", sb, i, b_bszB );
999 if (thisFree) blockctr_sb_free++;
1001 arena_bytes_on_loan += bszB_to_pszB(a, b_bszB);
1002 lastWasFree = thisFree;
1004 if (i > sb->n_payload_bytes) {
1005 VG_(printf)( "sanity_check_malloc_arena: sb %p: last block "
1006 "overshoots end\n", sb);
1011 if (arena_bytes_on_loan != a->stats__bytes_on_loan) {
1012 # ifdef VERBOSE_MALLOC
1013 VG_(printf)( "sanity_check_malloc_arena: a->bytes_on_loan %ld, "
1014 "arena_bytes_on_loan %ld: "
1015 "MISMATCH\n", a->bytes_on_loan, arena_bytes_on_loan);
1021 /* Second, traverse each list, checking that the back pointers make
1022 sense, counting blocks encountered, and checking that each block
1023 is an appropriate size for this list. */
1025 for (listno = 0; listno < N_MALLOC_LISTS; listno++) {
1026 list_min_pszB = listNo_to_pszB_min(listno);
1027 list_max_pszB = listNo_to_pszB_max(listno);
1028 b = a->freelist[listno];
1029 if (b == NULL) continue;
1033 if (get_prev_b(b) != b_prev) {
1034 VG_(printf)( "sanity_check_malloc_arena: list %d at %p: "
1039 b_pszB = get_pszB(a, b);
1040 if (b_pszB < list_min_pszB || b_pszB > list_max_pszB) {
1042 "sanity_check_malloc_arena: list %d at %p: "
1043 "WRONG CHAIN SIZE %luB (%luB, %luB)\n",
1044 listno, b, b_pszB, list_min_pszB, list_max_pszB );
1048 if (b == a->freelist[listno]) break;
1052 if (blockctr_sb_free != blockctr_li) {
1053 # ifdef VERBOSE_MALLOC
1054 VG_(printf)( "sanity_check_malloc_arena: BLOCK COUNT MISMATCH "
1055 "(via sbs %d, via lists %d)\n",
1056 blockctr_sb_free, blockctr_li );
1062 if (VG_(clo_verbosity) > 2)
1063 VG_(message)(Vg_DebugMsg,
1064 "%8s: %2d sbs, %5d bs, %2d/%-2d free bs, "
1065 "%7ld mmap, %7ld loan\n",
1068 blockctr_sb, blockctr_sb_free, blockctr_li,
1069 a->stats__bytes_mmaped, a->stats__bytes_on_loan);
1074 #define N_AN_CCS 1000
1076 typedef struct { ULong nBytes; ULong nBlocks; HChar* cc; } AnCC;
1078 static AnCC anCCs[N_AN_CCS];
1080 static Int cmp_AnCC_by_vol ( void* v1, void* v2 ) {
1081 AnCC* ancc1 = (AnCC*)v1;
1082 AnCC* ancc2 = (AnCC*)v2;
1083 if (ancc1->nBytes < ancc2->nBytes) return -1;
1084 if (ancc1->nBytes > ancc2->nBytes) return 1;
1088 static void cc_analyse_alloc_arena ( ArenaId aid )
1093 Bool thisFree, lastWasFree;
1099 a = arenaId_to_ArenaP(aid);
1100 if (a->name == NULL) {
1101 /* arena is not in use, is not initialised and will fail the
1102 sanity check that follows. */
1106 sanity_check_malloc_arena(aid);
1109 "-------- Arena \"%s\": %ld mmap'd, %ld/%ld max/curr --------\n",
1110 a->name, a->stats__bytes_mmaped,
1111 a->stats__bytes_on_loan_max, a->stats__bytes_on_loan
1114 for (j = 0; j < a->sblocks_used; ++j) {
1115 Superblock * sb = a->sblocks[j];
1116 lastWasFree = False;
1117 for (i = 0; i < sb->n_payload_bytes; i += mk_plain_bszB(b_bszB)) {
1118 b = (Block*)&sb->payload_bytes[i];
1119 b_bszB = get_bszB_as_is(b);
1120 if (!blockSane(a, b)) {
1121 VG_(printf)("sanity_check_malloc_arena: sb %p, block %ld "
1122 "(bszB %lu): BAD\n", sb, i, b_bszB );
1125 thisFree = !is_inuse_block(b);
1126 if (thisFree && lastWasFree) {
1127 VG_(printf)("sanity_check_malloc_arena: sb %p, block %ld "
1128 "(bszB %lu): UNMERGED FREES\n", sb, i, b_bszB );
1131 lastWasFree = thisFree;
1133 if (thisFree) continue;
1136 VG_(printf)("block: inUse=%d pszB=%d cc=%s\n",
1138 (Int)bszB_to_pszB(a, b_bszB),
1142 for (k = 0; k < n_ccs; k++) {
1143 tl_assert(anCCs[k].cc);
1144 if (0 == VG_(strcmp)(cc, anCCs[k].cc))
1147 tl_assert(k >= 0 && k <= n_ccs);
1150 tl_assert(n_ccs < N_AN_CCS-1);
1152 anCCs[k].nBytes = 0;
1153 anCCs[k].nBlocks = 0;
1157 tl_assert(k >= 0 && k < n_ccs && k < N_AN_CCS);
1158 anCCs[k].nBytes += (ULong)bszB_to_pszB(a, b_bszB);
1161 if (i > sb->n_payload_bytes) {
1162 VG_(printf)( "sanity_check_malloc_arena: sb %p: last block "
1163 "overshoots end\n", sb);
1168 VG_(ssort)( &anCCs[0], n_ccs, sizeof(anCCs[0]), cmp_AnCC_by_vol );
1170 for (k = 0; k < n_ccs; k++) {
1171 VG_(printf)("%'13llu in %'9llu: %s\n",
1172 anCCs[k].nBytes, anCCs[k].nBlocks, anCCs[k].cc );
1179 void VG_(sanity_check_malloc_all) ( void )
1182 for (i = 0; i < VG_N_ARENAS; i++) {
1183 if (i == VG_AR_CLIENT && !client_inited)
1185 sanity_check_malloc_arena ( i );
1190 /*------------------------------------------------------------*/
1191 /*--- Creating and deleting blocks. ---*/
1192 /*------------------------------------------------------------*/
1194 // Mark the bytes at b .. b+bszB-1 as not in use, and add them to the
1195 // relevant free list.
1198 void mkFreeBlock ( Arena* a, Block* b, SizeT bszB, UInt b_lno )
1200 SizeT pszB = bszB_to_pszB(a, bszB);
1201 vg_assert(b_lno == pszB_to_listNo(pszB));
1202 //zzVALGRIND_MAKE_MEM_UNDEFINED(b, bszB);
1203 // Set the size fields and indicate not-in-use.
1204 set_bszB(b, mk_free_bszB(bszB));
1206 // Add to the relevant list.
1207 if (a->freelist[b_lno] == NULL) {
1210 a->freelist[b_lno] = b;
1212 Block* b_prev = get_prev_b(a->freelist[b_lno]);
1213 Block* b_next = a->freelist[b_lno];
1214 set_next_b(b_prev, b);
1215 set_prev_b(b_next, b);
1216 set_next_b(b, b_next);
1217 set_prev_b(b, b_prev);
1219 # ifdef DEBUG_MALLOC
1220 (void)blockSane(a,b);
1224 // Mark the bytes at b .. b+bszB-1 as in use, and set up the block
1227 void mkInuseBlock ( Arena* a, Block* b, SizeT bszB )
1230 vg_assert(bszB >= min_useful_bszB(a));
1231 //zzVALGRIND_MAKE_MEM_UNDEFINED(b, bszB);
1232 set_bszB(b, mk_inuse_bszB(bszB));
1233 set_prev_b(b, NULL); // Take off freelist
1234 set_next_b(b, NULL); // ditto
1235 if (!a->clientmem) {
1236 for (i = 0; i < a->rz_szB; i++) {
1237 set_rz_lo_byte(b, i, (UByte)(((Addr)b&0xff) ^ REDZONE_LO_MASK));
1238 set_rz_hi_byte(b, i, (UByte)(((Addr)b&0xff) ^ REDZONE_HI_MASK));
1241 # ifdef DEBUG_MALLOC
1242 (void)blockSane(a,b);
1246 // Remove a block from a given list. Does no sanity checking.
1248 void unlinkBlock ( Arena* a, Block* b, UInt listno )
1250 vg_assert(listno < N_MALLOC_LISTS);
1251 if (get_prev_b(b) == b) {
1252 // Only one element in the list; treat it specially.
1253 vg_assert(get_next_b(b) == b);
1254 a->freelist[listno] = NULL;
1256 Block* b_prev = get_prev_b(b);
1257 Block* b_next = get_next_b(b);
1258 a->freelist[listno] = b_prev;
1259 set_next_b(b_prev, b_next);
1260 set_prev_b(b_next, b_prev);
1261 swizzle ( a, listno );
1263 set_prev_b(b, NULL);
1264 set_next_b(b, NULL);
1268 /*------------------------------------------------------------*/
1269 /*--- Core-visible functions. ---*/
1270 /*------------------------------------------------------------*/
1272 // Align the request size.
1274 SizeT align_req_pszB ( SizeT req_pszB )
1276 SizeT n = VG_MIN_MALLOC_SZB-1;
1277 return ((req_pszB + n) & (~n));
1280 void* VG_(arena_malloc) ( ArenaId aid, HChar* cc, SizeT req_pszB )
1282 SizeT req_bszB, frag_bszB, b_bszB;
1288 UWord stats__nsearches = 0;
1290 ensure_mm_init(aid);
1291 a = arenaId_to_ArenaP(aid);
1293 vg_assert(req_pszB < MAX_PSZB);
1294 req_pszB = align_req_pszB(req_pszB);
1295 req_bszB = pszB_to_bszB(a, req_pszB);
1297 // You must provide a cost-center name against which to charge
1298 // this allocation; it isn't optional.
1301 // Scan through all the big-enough freelists for a block.
1303 // Nb: this scanning might be expensive in some cases. Eg. if you
1304 // allocate lots of small objects without freeing them, but no
1305 // medium-sized objects, it will repeatedly scanning through the whole
1306 // list, and each time not find any free blocks until the last element.
1308 // If this becomes a noticeable problem... the loop answers the question
1309 // "where is the first nonempty list above me?" And most of the time,
1310 // you ask the same question and get the same answer. So it would be
1311 // good to somehow cache the results of previous searches.
1312 // One possibility is an array (with N_MALLOC_LISTS elements) of
1313 // shortcuts. shortcut[i] would give the index number of the nearest
1314 // larger list above list i which is non-empty. Then this loop isn't
1315 // necessary. However, we'd have to modify some section [ .. i-1] of the
1316 // shortcut array every time a list [i] changes from empty to nonempty or
1317 // back. This would require care to avoid pathological worst-case
1320 for (lno = pszB_to_listNo(req_pszB); lno < N_MALLOC_LISTS; lno++) {
1321 UWord nsearches_this_level = 0;
1322 b = a->freelist[lno];
1323 if (NULL == b) continue; // If this list is empty, try the next one.
1326 nsearches_this_level++;
1327 if (UNLIKELY(nsearches_this_level >= 100)
1328 && lno < N_MALLOC_LISTS-1) {
1329 /* Avoid excessive scanning on this freelist, and instead
1330 try the next one up. But first, move this freelist's
1331 start pointer one element along, so as to ensure that
1332 subsequent searches of this list don't endlessly
1333 revisit only these 100 elements, but in fact slowly
1334 progress through the entire list. */
1335 b = a->freelist[lno];
1336 vg_assert(b); // this list must be nonempty!
1337 a->freelist[lno] = get_next_b(b); // step one along
1340 b_bszB = get_bszB(b);
1341 if (b_bszB >= req_bszB) goto obtained_block; // success!
1343 if (b == a->freelist[lno]) break; // traversed entire freelist
1347 // If we reach here, no suitable block found, allocate a new superblock
1348 vg_assert(lno == N_MALLOC_LISTS);
1349 new_sb = newSuperblock(a, req_bszB);
1350 if (NULL == new_sb) {
1351 // Should only fail if for client, otherwise, should have aborted
1353 vg_assert(VG_AR_CLIENT == aid);
1357 vg_assert(a->sblocks_used <= a->sblocks_size);
1358 if (a->sblocks_used == a->sblocks_size) {
1359 Superblock ** array;
1360 SysRes sres = VG_(am_sbrk_anon_float_valgrind)(sizeof(Superblock *) *
1361 a->sblocks_size * 2);
1362 if (sr_isError(sres)) {
1363 VG_(out_of_memory_NORETURN)("arena_init", sizeof(Superblock *) *
1364 a->sblocks_size * 2);
1367 array = (Superblock**)(AddrH)sr_Res(sres);
1368 for (i = 0; i < a->sblocks_used; ++i) array[i] = a->sblocks[i];
1370 a->sblocks_size *= 2;
1372 VG_(debugLog)(1, "mallocfree",
1373 "sblock array for arena `%s' resized to %ld\n",
1374 a->name, a->sblocks_size);
1377 vg_assert(a->sblocks_used < a->sblocks_size);
1379 i = a->sblocks_used;
1381 if (a->sblocks[i-1] > new_sb) {
1382 a->sblocks[i] = a->sblocks[i-1];
1388 a->sblocks[i] = new_sb;
1391 b = (Block*)&new_sb->payload_bytes[0];
1392 lno = pszB_to_listNo(bszB_to_pszB(a, new_sb->n_payload_bytes));
1393 mkFreeBlock ( a, b, new_sb->n_payload_bytes, lno);
1394 if (VG_(clo_profile_heap))
1395 set_cc(b, "admin.free-new-sb-1");
1399 // Ok, we can allocate from b, which lives in list lno.
1400 vg_assert(b != NULL);
1401 vg_assert(lno < N_MALLOC_LISTS);
1402 vg_assert(a->freelist[lno] != NULL);
1403 b_bszB = get_bszB(b);
1404 // req_bszB is the size of the block we are after. b_bszB is the
1405 // size of what we've actually got. */
1406 vg_assert(b_bszB >= req_bszB);
1408 // Could we split this block and still get a useful fragment?
1409 frag_bszB = b_bszB - req_bszB;
1410 if (frag_bszB >= min_useful_bszB(a)) {
1411 // Yes, split block in two, put the fragment on the appropriate free
1412 // list, and update b_bszB accordingly.
1413 // printf( "split %dB into %dB and %dB\n", b_bszB, req_bszB, frag_bszB );
1414 unlinkBlock(a, b, lno);
1415 mkInuseBlock(a, b, req_bszB);
1416 if (VG_(clo_profile_heap))
1418 mkFreeBlock(a, &b[req_bszB], frag_bszB,
1419 pszB_to_listNo(bszB_to_pszB(a, frag_bszB)));
1420 if (VG_(clo_profile_heap))
1421 set_cc(&b[req_bszB], "admin.fragmentation-1");
1422 b_bszB = get_bszB(b);
1424 // No, mark as in use and use as-is.
1425 unlinkBlock(a, b, lno);
1426 mkInuseBlock(a, b, b_bszB);
1427 if (VG_(clo_profile_heap))
1432 SizeT loaned = bszB_to_pszB(a, b_bszB);
1433 a->stats__bytes_on_loan += loaned;
1434 if (a->stats__bytes_on_loan > a->stats__bytes_on_loan_max) {
1435 a->stats__bytes_on_loan_max = a->stats__bytes_on_loan;
1436 if (a->stats__bytes_on_loan_max >= a->next_profile_at) {
1437 /* next profile after 10% more growth */
1440 (((ULong)a->stats__bytes_on_loan_max) * 110ULL) / 100ULL );
1441 if (VG_(clo_profile_heap))
1442 cc_analyse_alloc_arena(aid);
1445 a->stats__tot_blocks += (ULong)1;
1446 a->stats__tot_bytes += (ULong)loaned;
1447 a->stats__nsearches += (ULong)stats__nsearches;
1449 # ifdef DEBUG_MALLOC
1450 sanity_check_malloc_arena(aid);
1453 v = get_block_payload(a, b);
1454 vg_assert( (((Addr)v) & (VG_MIN_MALLOC_SZB-1)) == 0 );
1456 /* VALGRIND_MALLOCLIKE_BLOCK(v, req_pszB, 0, False); */
1458 /* For debugging/testing purposes, fill the newly allocated area
1459 with a definite value in an attempt to shake out any
1460 uninitialised uses of the data (by V core / V tools, not by the
1461 client). Testing on 25 Nov 07 with the values 0x00, 0xFF, 0x55,
1462 0xAA showed no differences in the regression tests on
1463 amd64-linux. Note, is disabled by default. */
1464 if (0 && aid != VG_AR_CLIENT)
1465 VG_(memset)(v, 0xAA, (SizeT)req_pszB);
1471 void VG_(arena_free) ( ArenaId aid, void* ptr )
1478 SizeT b_bszB, b_pszB, other_bszB;
1482 ensure_mm_init(aid);
1483 a = arenaId_to_ArenaP(aid);
1489 b = get_payload_block(a, ptr);
1491 /* If this is one of V's areas, check carefully the block we're
1492 getting back. This picks up simple block-end overruns. */
1493 if (aid != VG_AR_CLIENT)
1494 vg_assert(blockSane(a, b));
1496 b_bszB = get_bszB(b);
1497 b_pszB = bszB_to_pszB(a, b_bszB);
1498 sb = findSb( a, b );
1499 sb_start = &sb->payload_bytes[0];
1500 sb_end = &sb->payload_bytes[sb->n_payload_bytes - 1];
1502 a->stats__bytes_on_loan -= b_pszB;
1504 /* If this is one of V's areas, fill it up with junk to enhance the
1505 chances of catching any later reads of it. Note, 0xDD is
1506 carefully chosen junk :-), in that: (1) 0xDDDDDDDD is an invalid
1507 and non-word-aligned address on most systems, and (2) 0xDD is a
1508 value which is unlikely to be generated by the new compressed
1509 Vbits representation for memcheck. */
1510 if (aid != VG_AR_CLIENT)
1511 VG_(memset)(ptr, 0xDD, (SizeT)b_pszB);
1513 // Put this chunk back on a list somewhere.
1514 b_listno = pszB_to_listNo(b_pszB);
1515 mkFreeBlock( a, b, b_bszB, b_listno );
1516 if (VG_(clo_profile_heap))
1517 set_cc(b, "admin.free-1");
1519 // See if this block can be merged with its successor.
1520 // First test if we're far enough before the superblock's end to possibly
1521 // have a successor.
1522 other_b = b + b_bszB;
1523 if (other_b+min_useful_bszB(a)-1 <= (Block*)sb_end) {
1524 // Ok, we have a successor, merge if it's not in use.
1525 other_bszB = get_bszB(other_b);
1526 if (!is_inuse_block(other_b)) {
1527 // VG_(printf)( "merge-successor\n");
1528 # ifdef DEBUG_MALLOC
1529 vg_assert(blockSane(a, other_b));
1531 unlinkBlock( a, b, b_listno );
1532 unlinkBlock( a, other_b, pszB_to_listNo(bszB_to_pszB(a,other_bszB)) );
1533 b_bszB += other_bszB;
1534 b_listno = pszB_to_listNo(bszB_to_pszB(a, b_bszB));
1535 mkFreeBlock( a, b, b_bszB, b_listno );
1536 if (VG_(clo_profile_heap))
1537 set_cc(b, "admin.free-2");
1540 // Not enough space for successor: check that b is the last block
1541 // ie. there are no unused bytes at the end of the Superblock.
1542 vg_assert(other_b-1 == (Block*)sb_end);
1545 // Then see if this block can be merged with its predecessor.
1546 // First test if we're far enough after the superblock's start to possibly
1547 // have a predecessor.
1548 if (b >= (Block*)sb_start + min_useful_bszB(a)) {
1549 // Ok, we have a predecessor, merge if it's not in use.
1550 other_b = get_predecessor_block( b );
1551 other_bszB = get_bszB(other_b);
1552 if (!is_inuse_block(other_b)) {
1553 // VG_(printf)( "merge-predecessor\n");
1554 unlinkBlock( a, b, b_listno );
1555 unlinkBlock( a, other_b, pszB_to_listNo(bszB_to_pszB(a, other_bszB)) );
1557 b_bszB += other_bszB;
1558 b_listno = pszB_to_listNo(bszB_to_pszB(a, b_bszB));
1559 mkFreeBlock( a, b, b_bszB, b_listno );
1560 if (VG_(clo_profile_heap))
1561 set_cc(b, "admin.free-3");
1564 // Not enough space for predecessor: check that b is the first block,
1565 // ie. there are no unused bytes at the start of the Superblock.
1566 vg_assert((Block*)sb_start == b);
1569 # ifdef DEBUG_MALLOC
1570 sanity_check_malloc_arena(aid);
1573 //zzVALGRIND_FREELIKE_BLOCK(ptr, 0);
1578 The idea for malloc_aligned() is to allocate a big block, base, and
1579 then split it into two parts: frag, which is returned to the the
1580 free pool, and align, which is the bit we're really after. Here's
1581 a picture. L and H denote the block lower and upper overheads, in
1582 bytes. The details are gruesome. Note it is slightly complicated
1583 because the initial request to generate base may return a bigger
1584 block than we asked for, so it is important to distinguish the base
1585 request size and the base actual size.
1593 +---+ +---+---+ +---+
1594 | L |----------------| H | L |---------------| H |
1595 +---+ +---+---+ +---+
1599 | base_p this addr must be aligned
1604 <------ frag_bszB -------> . . .
1605 . <------------- base_pszB_act -----------> .
1609 void* VG_(arena_memalign) ( ArenaId aid, HChar* cc,
1610 SizeT req_alignB, SizeT req_pszB )
1612 SizeT base_pszB_req, base_pszB_act, frag_bszB;
1613 Block *base_b, *align_b;
1614 UByte *base_p, *align_p;
1615 SizeT saved_bytes_on_loan;
1618 ensure_mm_init(aid);
1619 a = arenaId_to_ArenaP(aid);
1621 vg_assert(req_pszB < MAX_PSZB);
1623 // You must provide a cost-center name against which to charge
1624 // this allocation; it isn't optional.
1627 // Check that the requested alignment seems reasonable; that is, is
1629 if (req_alignB < VG_MIN_MALLOC_SZB
1630 || req_alignB > 1048576
1631 || VG_(log2)( req_alignB ) == -1 /* not a power of 2 */) {
1632 VG_(printf)("VG_(arena_memalign)(%p, %lu, %lu)\n"
1633 "bad alignment value %lu\n"
1634 "(it is too small, too big, or not a power of two)",
1635 a, req_alignB, req_pszB, req_alignB );
1636 VG_(core_panic)("VG_(arena_memalign)");
1640 vg_assert(req_alignB % VG_MIN_MALLOC_SZB == 0);
1642 /* Required payload size for the aligned chunk. */
1643 req_pszB = align_req_pszB(req_pszB);
1645 /* Payload size to request for the big block that we will split up. */
1646 base_pszB_req = req_pszB + min_useful_bszB(a) + req_alignB;
1648 /* Payload ptr for the block we are going to split. Note this
1649 changes a->bytes_on_loan; we save and restore it ourselves. */
1650 saved_bytes_on_loan = a->stats__bytes_on_loan;
1651 base_p = VG_(arena_malloc) ( aid, cc, base_pszB_req );
1652 a->stats__bytes_on_loan = saved_bytes_on_loan;
1654 /* Give up if we couldn't allocate enough space */
1658 /* Block ptr for the block we are going to split. */
1659 base_b = get_payload_block ( a, base_p );
1661 /* Pointer to the payload of the aligned block we are going to
1662 return. This has to be suitably aligned. */
1663 align_p = align_upwards ( base_b + 2 * overhead_szB_lo(a)
1664 + overhead_szB_hi(a),
1666 align_b = get_payload_block(a, align_p);
1668 /* The block size of the fragment we will create. This must be big
1669 enough to actually create a fragment. */
1670 frag_bszB = align_b - base_b;
1672 vg_assert(frag_bszB >= min_useful_bszB(a));
1674 /* The actual payload size of the block we are going to split. */
1675 base_pszB_act = get_pszB(a, base_b);
1677 /* Create the fragment block, and put it back on the relevant free list. */
1678 mkFreeBlock ( a, base_b, frag_bszB,
1679 pszB_to_listNo(bszB_to_pszB(a, frag_bszB)) );
1680 if (VG_(clo_profile_heap))
1681 set_cc(base_b, "admin.frag-memalign-1");
1683 /* Create the aligned block. */
1684 mkInuseBlock ( a, align_b,
1685 base_p + base_pszB_act
1686 + overhead_szB_hi(a) - (UByte*)align_b );
1687 if (VG_(clo_profile_heap))
1688 set_cc(align_b, cc);
1690 /* Final sanity checks. */
1691 vg_assert( is_inuse_block(get_payload_block(a, align_p)) );
1693 vg_assert(req_pszB <= get_pszB(a, get_payload_block(a, align_p)));
1695 a->stats__bytes_on_loan += get_pszB(a, get_payload_block(a, align_p));
1696 if (a->stats__bytes_on_loan > a->stats__bytes_on_loan_max) {
1697 a->stats__bytes_on_loan_max = a->stats__bytes_on_loan;
1699 /* a->stats__tot_blocks, a->stats__tot_bytes, a->stats__nsearches
1700 are updated by the call to VG_(arena_malloc) just a few lines
1701 above. So we don't need to update them here. */
1703 # ifdef DEBUG_MALLOC
1704 sanity_check_malloc_arena(aid);
1707 vg_assert( (((Addr)align_p) % req_alignB) == 0 );
1709 //zzVALGRIND_MALLOCLIKE_BLOCK(align_p, req_pszB, 0, False);
1715 SizeT VG_(arena_malloc_usable_size) ( ArenaId aid, void* ptr )
1717 Arena* a = arenaId_to_ArenaP(aid);
1718 Block* b = get_payload_block(a, ptr);
1719 return get_pszB(a, b);
1723 // Implementation of mallinfo(). There is no recent standard that defines
1724 // the behavior of mallinfo(). The meaning of the fields in struct mallinfo
1727 // struct mallinfo {
1728 // int arena; /* total space in arena */
1729 // int ordblks; /* number of ordinary blocks */
1730 // int smblks; /* number of small blocks */
1731 // int hblks; /* number of holding blocks */
1732 // int hblkhd; /* space in holding block headers */
1733 // int usmblks; /* space in small blocks in use */
1734 // int fsmblks; /* space in free small blocks */
1735 // int uordblks; /* space in ordinary blocks in use */
1736 // int fordblks; /* space in free ordinary blocks */
1737 // int keepcost; /* space penalty if keep option */
1741 // The glibc documentation about mallinfo (which is somewhat outdated) can
1743 // http://www.gnu.org/software/libtool/manual/libc/Statistics-of-Malloc.html
1745 // See also http://bugs.kde.org/show_bug.cgi?id=160956.
1747 // Regarding the implementation of VG_(mallinfo)(): we cannot return the
1748 // whole struct as the library function does, because this is called by a
1749 // client request. So instead we use a pointer to do call by reference.
1750 void VG_(mallinfo) ( ThreadId tid, struct vg_mallinfo* mi )
1752 UWord i, free_blocks, free_blocks_size;
1753 Arena* a = arenaId_to_ArenaP(VG_AR_CLIENT);
1755 // Traverse free list and calculate free blocks statistics.
1756 // This may seem slow but glibc works the same way.
1757 free_blocks_size = free_blocks = 0;
1758 for (i = 0; i < N_MALLOC_LISTS; i++) {
1759 Block* b = a->freelist[i];
1760 if (b == NULL) continue;
1763 free_blocks_size += (UWord)get_pszB(a, b);
1765 if (b == a->freelist[i]) break;
1769 // We don't have fastbins so smblks & fsmblks are always 0. Also we don't
1770 // have a separate mmap allocator so set hblks & hblkhd to 0.
1771 mi->arena = a->stats__bytes_mmaped;
1772 mi->ordblks = free_blocks + VG_(free_queue_length);
1778 mi->uordblks = a->stats__bytes_on_loan - VG_(free_queue_volume);
1779 mi->fordblks = free_blocks_size + VG_(free_queue_volume);
1780 mi->keepcost = 0; // may want some value in here
1784 /*------------------------------------------------------------*/
1785 /*--- Services layered on top of malloc/free. ---*/
1786 /*------------------------------------------------------------*/
1788 void* VG_(arena_calloc) ( ArenaId aid, HChar* cc,
1789 SizeT nmemb, SizeT bytes_per_memb )
1794 size = nmemb * bytes_per_memb;
1795 vg_assert(size >= nmemb && size >= bytes_per_memb);// check against overflow
1797 p = VG_(arena_malloc) ( aid, cc, size );
1799 VG_(memset)(p, 0, size);
1801 //zzVALGRIND_MALLOCLIKE_BLOCK(p, size, 0, True);
1807 void* VG_(arena_realloc) ( ArenaId aid, HChar* cc,
1808 void* ptr, SizeT req_pszB )
1815 ensure_mm_init(aid);
1816 a = arenaId_to_ArenaP(aid);
1818 vg_assert(req_pszB < MAX_PSZB);
1821 return VG_(arena_malloc)(aid, cc, req_pszB);
1824 if (req_pszB == 0) {
1825 VG_(arena_free)(aid, ptr);
1829 b = get_payload_block(a, ptr);
1830 vg_assert(blockSane(a, b));
1832 vg_assert(is_inuse_block(b));
1833 old_pszB = get_pszB(a, b);
1835 if (req_pszB <= old_pszB) {
1839 p_new = VG_(arena_malloc) ( aid, cc, req_pszB );
1841 VG_(memcpy)(p_new, ptr, old_pszB);
1843 VG_(arena_free)(aid, ptr);
1849 /* Inline just for the wrapper VG_(strdup) below */
1850 __inline__ Char* VG_(arena_strdup) ( ArenaId aid, HChar* cc,
1860 len = VG_(strlen)(s) + 1;
1861 res = VG_(arena_malloc) (aid, cc, len);
1863 for (i = 0; i < len; i++)
1869 /*------------------------------------------------------------*/
1870 /*--- Tool-visible functions. ---*/
1871 /*------------------------------------------------------------*/
1873 // All just wrappers to avoid exposing arenas to tools.
1875 void* VG_(malloc) ( HChar* cc, SizeT nbytes )
1877 return VG_(arena_malloc) ( VG_AR_TOOL, cc, nbytes );
1880 void VG_(free) ( void* ptr )
1882 VG_(arena_free) ( VG_AR_TOOL, ptr );
1885 void* VG_(calloc) ( HChar* cc, SizeT nmemb, SizeT bytes_per_memb )
1887 return VG_(arena_calloc) ( VG_AR_TOOL, cc, nmemb, bytes_per_memb );
1890 void* VG_(realloc) ( HChar* cc, void* ptr, SizeT size )
1892 return VG_(arena_realloc) ( VG_AR_TOOL, cc, ptr, size );
1895 Char* VG_(strdup) ( HChar* cc, const Char* s )
1897 return VG_(arena_strdup) ( VG_AR_TOOL, cc, s );
1900 // Useful for querying user blocks.
1901 SizeT VG_(malloc_usable_size) ( void* p )
1903 return VG_(arena_malloc_usable_size)(VG_AR_CLIENT, p);
1907 /*--------------------------------------------------------------------*/
1909 /*--------------------------------------------------------------------*/