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_threadstate.h" // For VG_INVALID_THREADID
42 #include "pub_core_tooliface.h"
45 //zz#include "memcheck/memcheck.h"
47 // #define DEBUG_MALLOC // turn on heavyweight debugging machinery
48 // #define VERBOSE_MALLOC // make verbose, esp. in debugging machinery
50 /* Number and total size of blocks in free queue. Used by mallinfo(). */
51 Long VG_(free_queue_volume) = 0;
52 Long VG_(free_queue_length) = 0;
54 static void cc_analyse_alloc_arena ( ArenaId aid ); /* fwds */
56 /*------------------------------------------------------------*/
57 /*--- Main types ---*/
58 /*------------------------------------------------------------*/
60 #define N_MALLOC_LISTS 112 // do not change this
62 // The amount you can ask for is limited only by sizeof(SizeT)...
63 #define MAX_PSZB (~((SizeT)0x0))
65 // Each arena has a sorted array of superblocks, which expands
66 // dynamically. This is its initial size.
67 #define SBLOCKS_SIZE_INITIAL 50
71 /* Layout of an in-use block:
73 cost center (OPTIONAL) (VG_MIN_MALLOC_SZB bytes, only when h-p enabled)
74 this block total szB (sizeof(SizeT) bytes)
75 red zone bytes (depends on Arena.rz_szB, but >= sizeof(void*))
77 red zone bytes (depends on Arena.rz_szB, but >= sizeof(void*))
78 this block total szB (sizeof(SizeT) bytes)
80 Layout of a block on the free list:
82 cost center (OPTIONAL) (VG_MIN_MALLOC_SZB bytes, only when h-p enabled)
83 this block total szB (sizeof(SizeT) bytes)
84 freelist previous ptr (sizeof(void*) bytes)
85 excess red zone bytes (if Arena.rz_szB > sizeof(void*))
87 excess red zone bytes (if Arena.rz_szB > sizeof(void*))
88 freelist next ptr (sizeof(void*) bytes)
89 this block total szB (sizeof(SizeT) bytes)
91 Total size in bytes (bszB) and payload size in bytes (pszB)
94 bszB == pszB + 2*sizeof(SizeT) + 2*a->rz_szB
96 when heap profiling is not enabled, and
98 bszB == pszB + 2*sizeof(SizeT) + 2*a->rz_szB + VG_MIN_MALLOC_SZB
100 when it is enabled. It follows that the minimum overhead per heap
101 block for arenas used by the core is:
103 32-bit platforms: 2*4 + 2*4 == 16 bytes
104 64-bit platforms: 2*8 + 2*8 == 32 bytes
106 when heap profiling is not enabled, and
108 32-bit platforms: 2*4 + 2*4 + 8 == 24 bytes
109 64-bit platforms: 2*8 + 2*8 + 16 == 48 bytes
111 when it is enabled. In all cases, extra overhead may be incurred
112 when rounding the payload size up to VG_MIN_MALLOC_SZB.
114 Furthermore, both size fields in the block have their least-significant
115 bit set if the block is not in use, and unset if it is in use.
116 (The bottom 3 or so bits are always free for this because of alignment.)
117 A block size of zero is not possible, because a block always has at
118 least two SizeTs and two pointers of overhead.
120 Nb: All Block payloads must be VG_MIN_MALLOC_SZB-aligned. This is
121 achieved by ensuring that Superblocks are VG_MIN_MALLOC_SZB-aligned
122 (see newSuperblock() for how), and that the lengths of the following
123 things are a multiple of VG_MIN_MALLOC_SZB:
124 - Superblock admin section lengths (due to elastic padding)
125 - Block admin section (low and high) lengths (due to elastic redzones)
126 - Block payload lengths (due to req_pszB rounding up)
128 The heap-profile cost-center field is 8 bytes even on 32 bit
129 platforms. This is so as to keep the payload field 8-aligned. On
130 a 64-bit platform, this cc-field contains a pointer to a const
131 HChar*, which is the cost center name. On 32-bit platforms, the
132 pointer lives in the lower-addressed half of the field, regardless
133 of the endianness of the host.
137 // No fields are actually used in this struct, because a Block has
138 // many variable sized fields and so can't be accessed
139 // meaningfully with normal fields. So we use access functions all
140 // the time. This struct gives us a type to use, though. Also, we
141 // make sizeof(Block) 1 byte so that we can do arithmetic with the
142 // Block* type in increments of 1!
147 // A superblock. 'padding' is never used, it just ensures that if the
148 // entire Superblock is aligned to VG_MIN_MALLOC_SZB, then payload_bytes[]
149 // will be too. It can add small amounts of padding unnecessarily -- eg.
150 // 8-bytes on 32-bit machines with an 8-byte VG_MIN_MALLOC_SZB -- because
151 // it's too hard to make a constant expression that works perfectly in all
153 // payload_bytes[] is made a single big Block when the Superblock is
154 // created, and then can be split and the splittings remerged, but Blocks
155 // always cover its entire length -- there's never any unused bytes at the
159 SizeT n_payload_bytes;
161 UByte padding[ VG_MIN_MALLOC_SZB -
162 ((sizeof(struct _Superblock*) + sizeof(SizeT)) %
163 VG_MIN_MALLOC_SZB) ];
164 UByte payload_bytes[0];
168 // An arena. 'freelist' is a circular, doubly-linked list. 'rz_szB' is
169 // elastic, in that it can be bigger than asked-for to ensure alignment.
173 Bool clientmem; // Allocates in the client address space?
174 SizeT rz_szB; // Red zone size in bytes
175 SizeT min_sblock_szB; // Minimum superblock size in bytes
176 Block* freelist[N_MALLOC_LISTS];
177 // A dynamically expanding, ordered array of (pointers to)
178 // superblocks in the arena. If this array is expanded, which
179 // is rare, the previous space it occupies is simply abandoned.
180 // To avoid having to get yet another block from m_aspacemgr for
181 // the first incarnation of this array, the first allocation of
182 // it is within this struct. If it has to be expanded then the
183 // new space is acquired from m_aspacemgr as you would expect.
184 Superblock** sblocks;
187 Superblock* sblocks_initial[SBLOCKS_SIZE_INITIAL];
191 SizeT bytes_on_loan_max;
192 SizeT next_profile_at;
197 /*------------------------------------------------------------*/
198 /*--- Low-level functions for working with Blocks. ---*/
199 /*------------------------------------------------------------*/
201 #define SIZE_T_0x1 ((SizeT)0x1)
203 static char* probably_your_fault =
204 "This is probably caused by your program erroneously writing past the\n"
205 "end of a heap block and corrupting heap metadata. If you fix any\n"
206 "invalid writes reported by Memcheck, this assertion failure will\n"
207 "probably go away. Please try that before reporting this as a bug.\n";
209 // Mark a bszB as in-use, and not in-use, and remove the in-use attribute.
211 SizeT mk_inuse_bszB ( SizeT bszB )
213 vg_assert2(bszB != 0, probably_your_fault);
214 return bszB & (~SIZE_T_0x1);
217 SizeT mk_free_bszB ( SizeT bszB )
219 vg_assert2(bszB != 0, probably_your_fault);
220 return bszB | SIZE_T_0x1;
223 SizeT mk_plain_bszB ( SizeT bszB )
225 vg_assert2(bszB != 0, probably_your_fault);
226 return bszB & (~SIZE_T_0x1);
229 // return either 0 or sizeof(ULong) depending on whether or not
230 // heap profiling is engaged
232 SizeT hp_overhead_szB ( void )
234 return VG_(clo_profile_heap) ? VG_MIN_MALLOC_SZB : 0;
237 //---------------------------------------------------------------------------
239 // Get a block's size as stored, ie with the in-use/free attribute.
241 SizeT get_bszB_as_is ( Block* b )
243 UByte* b2 = (UByte*)b;
244 SizeT bszB_lo = *(SizeT*)&b2[0 + hp_overhead_szB()];
245 SizeT bszB_hi = *(SizeT*)&b2[mk_plain_bszB(bszB_lo) - sizeof(SizeT)];
246 vg_assert2(bszB_lo == bszB_hi,
247 "Heap block lo/hi size mismatch: lo = %llu, hi = %llu.\n%s",
248 (ULong)bszB_lo, (ULong)bszB_hi, probably_your_fault);
252 // Get a block's plain size, ie. remove the in-use/free attribute.
254 SizeT get_bszB ( Block* b )
256 return mk_plain_bszB(get_bszB_as_is(b));
259 // Set the size fields of a block. bszB may have the in-use/free attribute.
261 void set_bszB ( Block* b, SizeT bszB )
263 UByte* b2 = (UByte*)b;
264 *(SizeT*)&b2[0 + hp_overhead_szB()] = bszB;
265 *(SizeT*)&b2[mk_plain_bszB(bszB) - sizeof(SizeT)] = bszB;
268 //---------------------------------------------------------------------------
270 // Does this block have the in-use attribute?
272 Bool is_inuse_block ( Block* b )
274 SizeT bszB = get_bszB_as_is(b);
275 vg_assert2(bszB != 0, probably_your_fault);
276 return (0 != (bszB & SIZE_T_0x1)) ? False : True;
279 //---------------------------------------------------------------------------
281 // Return the lower, upper and total overhead in bytes for a block.
282 // These are determined purely by which arena the block lives in.
284 SizeT overhead_szB_lo ( Arena* a )
286 return hp_overhead_szB() + sizeof(SizeT) + a->rz_szB;
289 SizeT overhead_szB_hi ( Arena* a )
291 return a->rz_szB + sizeof(SizeT);
294 SizeT overhead_szB ( Arena* a )
296 return overhead_szB_lo(a) + overhead_szB_hi(a);
299 //---------------------------------------------------------------------------
301 // Return the minimum bszB for a block in this arena. Can have zero-length
302 // payloads, so it's the size of the admin bytes.
304 SizeT min_useful_bszB ( Arena* a )
306 return overhead_szB(a);
309 //---------------------------------------------------------------------------
311 // Convert payload size <--> block size (both in bytes).
313 SizeT pszB_to_bszB ( Arena* a, SizeT pszB )
315 return pszB + overhead_szB(a);
318 SizeT bszB_to_pszB ( Arena* a, SizeT bszB )
320 vg_assert2(bszB >= overhead_szB(a), probably_your_fault);
321 return bszB - overhead_szB(a);
324 //---------------------------------------------------------------------------
326 // Get a block's payload size.
328 SizeT get_pszB ( Arena* a, Block* b )
330 return bszB_to_pszB(a, get_bszB(b));
333 //---------------------------------------------------------------------------
335 // Given the addr of a block, return the addr of its payload, and vice versa.
337 UByte* get_block_payload ( Arena* a, Block* b )
339 UByte* b2 = (UByte*)b;
340 return & b2[ overhead_szB_lo(a) ];
342 // Given the addr of a block's payload, return the addr of the block itself.
344 Block* get_payload_block ( Arena* a, UByte* payload )
346 return (Block*)&payload[ -overhead_szB_lo(a) ];
349 //---------------------------------------------------------------------------
351 // Set and get the next and previous link fields of a block.
353 void set_prev_b ( Block* b, Block* prev_p )
355 UByte* b2 = (UByte*)b;
356 *(Block**)&b2[hp_overhead_szB() + sizeof(SizeT)] = prev_p;
359 void set_next_b ( Block* b, Block* next_p )
361 UByte* b2 = (UByte*)b;
362 *(Block**)&b2[get_bszB(b) - sizeof(SizeT) - sizeof(void*)] = next_p;
365 Block* get_prev_b ( Block* b )
367 UByte* b2 = (UByte*)b;
368 return *(Block**)&b2[hp_overhead_szB() + sizeof(SizeT)];
371 Block* get_next_b ( Block* b )
373 UByte* b2 = (UByte*)b;
374 return *(Block**)&b2[get_bszB(b) - sizeof(SizeT) - sizeof(void*)];
377 //---------------------------------------------------------------------------
379 // Set and get the cost-center field of a block.
381 void set_cc ( Block* b, HChar* cc )
383 UByte* b2 = (UByte*)b;
384 vg_assert( VG_(clo_profile_heap) );
385 *(HChar**)&b2[0] = cc;
388 HChar* get_cc ( Block* b )
390 UByte* b2 = (UByte*)b;
391 vg_assert( VG_(clo_profile_heap) );
392 return *(HChar**)&b2[0];
395 //---------------------------------------------------------------------------
397 // Get the block immediately preceding this one in the Superblock.
399 Block* get_predecessor_block ( Block* b )
401 UByte* b2 = (UByte*)b;
402 SizeT bszB = mk_plain_bszB( (*(SizeT*)&b2[-sizeof(SizeT)]) );
403 return (Block*)&b2[-bszB];
406 //---------------------------------------------------------------------------
408 // Read and write the lower and upper red-zone bytes of a block.
410 void set_rz_lo_byte ( Block* b, UInt rz_byteno, UByte v )
412 UByte* b2 = (UByte*)b;
413 b2[hp_overhead_szB() + sizeof(SizeT) + rz_byteno] = v;
416 void set_rz_hi_byte ( Block* b, UInt rz_byteno, UByte v )
418 UByte* b2 = (UByte*)b;
419 b2[get_bszB(b) - sizeof(SizeT) - rz_byteno - 1] = v;
422 UByte get_rz_lo_byte ( Block* b, UInt rz_byteno )
424 UByte* b2 = (UByte*)b;
425 return b2[hp_overhead_szB() + sizeof(SizeT) + rz_byteno];
428 UByte get_rz_hi_byte ( Block* b, UInt rz_byteno )
430 UByte* b2 = (UByte*)b;
431 return b2[get_bszB(b) - sizeof(SizeT) - rz_byteno - 1];
435 /*------------------------------------------------------------*/
436 /*--- Arena management ---*/
437 /*------------------------------------------------------------*/
439 #define CORE_ARENA_MIN_SZB 1048576
441 // The arena structures themselves.
442 static Arena vg_arena[VG_N_ARENAS];
444 // Functions external to this module identify arenas using ArenaIds,
445 // not Arena*s. This fn converts the former to the latter.
446 static Arena* arenaId_to_ArenaP ( ArenaId arena )
448 vg_assert(arena >= 0 && arena < VG_N_ARENAS);
449 return & vg_arena[arena];
452 // Initialise an arena. rz_szB is the minimum redzone size; it might be
453 // made bigger to ensure that VG_MIN_MALLOC_SZB is observed.
455 void arena_init ( ArenaId aid, Char* name, SizeT rz_szB, SizeT min_sblock_szB )
458 Arena* a = arenaId_to_ArenaP(aid);
460 // Ensure redzones are a reasonable size. They must always be at least
461 // the size of a pointer, for holding the prev/next pointer (see the layout
462 // details at the top of this file).
463 vg_assert(rz_szB < 128);
464 if (rz_szB < sizeof(void*)) rz_szB = sizeof(void*);
466 vg_assert((min_sblock_szB % VKI_PAGE_SIZE) == 0);
468 a->clientmem = ( VG_AR_CLIENT == aid ? True : False );
470 // The size of the low and high admin sections in a block must be a
471 // multiple of VG_MIN_MALLOC_SZB. So we round up the asked-for
472 // redzone size if necessary to achieve this.
474 while (0 != overhead_szB_lo(a) % VG_MIN_MALLOC_SZB) a->rz_szB++;
475 vg_assert(overhead_szB_lo(a) - hp_overhead_szB() == overhead_szB_hi(a));
477 a->min_sblock_szB = min_sblock_szB;
478 for (i = 0; i < N_MALLOC_LISTS; i++) a->freelist[i] = NULL;
480 a->sblocks = & a->sblocks_initial[0];
481 a->sblocks_size = SBLOCKS_SIZE_INITIAL;
483 a->bytes_on_loan = 0;
485 a->bytes_on_loan_max = 0;
486 a->next_profile_at = 25 * 1000 * 1000;
487 vg_assert(sizeof(a->sblocks_initial)
488 == SBLOCKS_SIZE_INITIAL * sizeof(Superblock*));
491 /* Print vital stats for an arena. */
492 void VG_(print_all_arena_stats) ( void )
495 for (i = 0; i < VG_N_ARENAS; i++) {
496 Arena* a = arenaId_to_ArenaP(i);
497 VG_(message)(Vg_DebugMsg,
498 "%8s: %8ld mmap'd, %8ld/%8ld max/curr\n",
499 a->name, a->bytes_mmaped, a->bytes_on_loan_max, a->bytes_on_loan
504 void VG_(print_arena_cc_analysis) ( void )
507 vg_assert( VG_(clo_profile_heap) );
508 for (i = 0; i < VG_N_ARENAS; i++) {
509 cc_analyse_alloc_arena(i);
514 /* This library is self-initialising, as it makes this more self-contained,
515 less coupled with the outside world. Hence VG_(arena_malloc)() and
516 VG_(arena_free)() below always call ensure_mm_init() to ensure things are
517 correctly initialised.
519 We initialise the client arena separately (and later) because the core
520 must do non-client allocation before the tool has a chance to set the
521 client arena's redzone size.
523 static Bool client_inited = False;
524 static Bool nonclient_inited = False;
527 void ensure_mm_init ( ArenaId aid )
529 static SizeT client_rz_szB = 8; // default: be paranoid
531 /* We use checked red zones (of various sizes) for our internal stuff,
532 and an unchecked zone of arbitrary size for the client. Of
533 course the client's red zone can be checked by the tool, eg.
534 by using addressibility maps, but not by the mechanism implemented
535 here, which merely checks at the time of freeing that the red
536 zone bytes are unchanged.
538 Nb: redzone sizes are *minimums*; they could be made bigger to ensure
539 alignment. Eg. with 8 byte alignment, on 32-bit machines 4 stays as
540 4, but 16 becomes 20; but on 64-bit machines 4 becomes 8, and 16
541 stays as 16 --- the extra 4 bytes in both are accounted for by the
542 larger prev/next ptr.
544 if (VG_AR_CLIENT == aid) {
547 // This assertion ensures that a tool cannot try to change the client
548 // redzone size with VG_(needs_malloc_replacement)() after this module
549 // has done its first allocation from the client arena.
550 if (VG_(needs).malloc_replacement)
551 vg_assert(client_rz_szB == VG_(tdict).tool_client_redzone_szB);
555 // Check and set the client arena redzone size
556 if (VG_(needs).malloc_replacement) {
557 client_rz_szB = VG_(tdict).tool_client_redzone_szB;
558 // 128 is no special figure, just something not too big
559 if (client_rz_szB > 128) {
560 VG_(printf)( "\nTool error:\n"
561 " specified redzone size is too big (%llu)\n",
562 (ULong)client_rz_szB);
566 // Initialise the client arena. On AIX it's important to have
567 // relatively large client blocks so as not to cause excessively
568 // fine-grained interleaving of V and C address space. On Linux
569 // this is irrelevant since aspacem can keep the two spaces
570 // well apart, but not so on AIX. On all platforms though,
571 // increasing the superblock size reduces the number of superblocks
572 // in the client arena, which makes findSb cheaper.
573 # if defined(VGO_aix5)
574 ar_client_sbszB = 16777216;
576 ar_client_sbszB = 4194304;
578 arena_init ( VG_AR_CLIENT, "client", client_rz_szB, ar_client_sbszB );
579 client_inited = True;
582 if (nonclient_inited) {
585 // Initialise the non-client arenas
586 arena_init ( VG_AR_CORE, "core", 4, 1048576 );
587 arena_init ( VG_AR_TOOL, "tool", 4, 4194304 );
588 arena_init ( VG_AR_DINFO, "dinfo", 4, 1048576 );
589 arena_init ( VG_AR_DEMANGLE, "demangle", 4, 65536 );
590 arena_init ( VG_AR_EXECTXT, "exectxt", 4, 1048576 );
591 arena_init ( VG_AR_ERRORS, "errors", 4, 65536 );
592 arena_init ( VG_AR_TTAUX, "ttaux", 4, 65536 );
593 nonclient_inited = True;
597 VG_(printf)("ZZZ1\n");
598 VG_(sanity_check_malloc_all)();
599 VG_(printf)("ZZZ2\n");
604 /*------------------------------------------------------------*/
605 /*--- Superblock management ---*/
606 /*------------------------------------------------------------*/
608 __attribute__((noreturn))
609 void VG_(out_of_memory_NORETURN) ( HChar* who, SizeT szB )
611 static Bool alreadyCrashing = False;
612 ULong tot_alloc = VG_(am_get_anonsize_total)();
615 " Valgrind's memory management: out of memory:\n"
616 " %s's request for %llu bytes failed.\n"
617 " %llu bytes have already been allocated.\n"
618 " Valgrind cannot continue. Sorry.\n\n"
619 " There are several possible reasons for this.\n"
620 " - You have some kind of memory limit in place. Look at the\n"
621 " output of 'ulimit -a'. Is there a limit on the size of\n"
622 " virtual memory or address space?\n"
623 " - You have run out of swap space.\n"
624 " - Valgrind has a bug. If you think this is the case or you are\n"
625 " not sure, please let us know and we'll try to fix it.\n"
626 " Please note that programs can take substantially more memory than\n"
627 " normal when running under Valgrind tools, eg. up to twice or\n"
628 " more, depending on the tool. On a 64-bit machine, Valgrind\n"
629 " should be able to make use of up 32GB memory. On a 32-bit\n"
630 " machine, Valgrind should be able to use all the memory available\n"
631 " to a single process, up to 4GB if that's how you have your\n"
632 " kernel configured. Most 32-bit Linux setups allow a maximum of\n"
633 " 3GB per process.\n\n"
634 " Whatever the reason, Valgrind cannot continue. Sorry.\n";
636 if (!alreadyCrashing) {
637 alreadyCrashing = True;
638 VG_(message)(Vg_UserMsg, s1, who, (ULong)szB, tot_alloc);
640 VG_(debugLog)(0,"mallocfree", s1, who, (ULong)szB, tot_alloc);
647 // Align ptr p upwards to an align-sized boundary.
649 void* align_upwards ( void* p, SizeT align )
652 if ((a % align) == 0) return (void*)a;
653 return (void*)(a - (a % align) + align);
656 // If not enough memory available, either aborts (for non-client memory)
657 // or returns 0 (for client memory).
659 Superblock* newSuperblock ( Arena* a, SizeT cszB )
664 // Take into account admin bytes in the Superblock.
665 cszB += sizeof(Superblock);
667 if (cszB < a->min_sblock_szB) cszB = a->min_sblock_szB;
668 cszB = VG_PGROUNDUP(cszB);
671 // client allocation -- return 0 to client if it fails
672 sres = VG_(am_sbrk_anon_float_client)
673 ( cszB, VKI_PROT_READ|VKI_PROT_WRITE|VKI_PROT_EXEC );
674 if (sr_isError(sres))
676 sb = (Superblock*)(AddrH)sr_Res(sres);
677 // Mark this segment as containing client heap. The leak
678 // checker needs to be able to identify such segments so as not
679 // to use them as sources of roots during leak checks.
680 VG_(am_set_segment_isCH_if_SkAnonC)(
681 (NSegment*) VG_(am_find_nsegment)( (Addr)sb )
684 // non-client allocation -- abort if it fails
685 sres = VG_(am_sbrk_anon_float_valgrind)( cszB );
686 if (sr_isError(sres)) {
687 VG_(out_of_memory_NORETURN)("newSuperblock", cszB);
689 sb = NULL; /* keep gcc happy */
691 sb = (Superblock*)(AddrH)sr_Res(sres);
694 vg_assert(NULL != sb);
695 //zzVALGRIND_MAKE_MEM_UNDEFINED(sb, cszB);
696 vg_assert(0 == (Addr)sb % VG_MIN_MALLOC_SZB);
697 sb->n_payload_bytes = cszB - sizeof(Superblock);
698 a->bytes_mmaped += cszB;
699 VG_(debugLog)(1, "mallocfree",
700 "newSuperblock at %p (pszB %7ld) owner %s/%s\n",
701 sb, sb->n_payload_bytes,
702 a->clientmem ? "CLIENT" : "VALGRIND", a->name );
706 // Find the superblock containing the given chunk.
708 Superblock* findSb ( Arena* a, Block* b )
711 SizeT max = a->sblocks_used;
715 SizeT pos = min + (max - min)/2;
717 vg_assert(pos >= 0 && pos < a->sblocks_used);
718 sb = a->sblocks[pos];
719 if ((Block*)&sb->payload_bytes[0] <= b
720 && b < (Block*)&sb->payload_bytes[sb->n_payload_bytes])
723 } else if ((Block*)&sb->payload_bytes[0] <= b) {
729 VG_(printf)("findSb: can't find pointer %p in arena '%s'\n",
731 VG_(core_panic)("findSb: VG_(arena_free)() in wrong arena?");
732 return NULL; /*NOTREACHED*/
736 /*------------------------------------------------------------*/
737 /*--- Functions for working with freelists. ---*/
738 /*------------------------------------------------------------*/
740 // Nb: Determination of which freelist a block lives on is based on the
741 // payload size, not block size.
743 // Convert a payload size in bytes to a freelist number.
745 UInt pszB_to_listNo ( SizeT pszB )
747 SizeT n = pszB / VG_MIN_MALLOC_SZB;
748 vg_assert(0 == pszB % VG_MIN_MALLOC_SZB);
750 // The first 64 lists hold blocks of size VG_MIN_MALLOC_SZB * list_num.
751 // The final 48 hold bigger blocks.
752 if (n < 64) return (UInt)n;
753 /* Exponential slope up, factor 1.05 */
754 if (n < 67) return 64;
755 if (n < 70) return 65;
756 if (n < 74) return 66;
757 if (n < 77) return 67;
758 if (n < 81) return 68;
759 if (n < 85) return 69;
760 if (n < 90) return 70;
761 if (n < 94) return 71;
762 if (n < 99) return 72;
763 if (n < 104) return 73;
764 if (n < 109) return 74;
765 if (n < 114) return 75;
766 if (n < 120) return 76;
767 if (n < 126) return 77;
768 if (n < 133) return 78;
769 if (n < 139) return 79;
770 /* Exponential slope up, factor 1.10 */
771 if (n < 153) return 80;
772 if (n < 169) return 81;
773 if (n < 185) return 82;
774 if (n < 204) return 83;
775 if (n < 224) return 84;
776 if (n < 247) return 85;
777 if (n < 272) return 86;
778 if (n < 299) return 87;
779 if (n < 329) return 88;
780 if (n < 362) return 89;
781 if (n < 398) return 90;
782 if (n < 438) return 91;
783 if (n < 482) return 92;
784 if (n < 530) return 93;
785 if (n < 583) return 94;
786 if (n < 641) return 95;
787 /* Exponential slope up, factor 1.20 */
788 if (n < 770) return 96;
789 if (n < 924) return 97;
790 if (n < 1109) return 98;
791 if (n < 1331) return 99;
792 if (n < 1597) return 100;
793 if (n < 1916) return 101;
794 if (n < 2300) return 102;
795 if (n < 2760) return 103;
796 if (n < 3312) return 104;
797 if (n < 3974) return 105;
798 if (n < 4769) return 106;
799 if (n < 5723) return 107;
800 if (n < 6868) return 108;
801 if (n < 8241) return 109;
802 if (n < 9890) return 110;
806 // What is the minimum payload size for a given list?
808 SizeT listNo_to_pszB_min ( UInt listNo )
810 /* Repeatedly computing this function at every request is
811 expensive. Hence at the first call just cache the result for
812 every possible argument. */
813 static SizeT cache[N_MALLOC_LISTS];
814 static Bool cache_valid = False;
817 for (i = 0; i < N_MALLOC_LISTS; i++) {
819 while (pszB_to_listNo(pszB) < i)
820 pszB += VG_MIN_MALLOC_SZB;
825 /* Returned cached answer. */
826 vg_assert(listNo <= N_MALLOC_LISTS);
827 return cache[listNo];
830 // What is the maximum payload size for a given list?
832 SizeT listNo_to_pszB_max ( UInt listNo )
834 vg_assert(listNo <= N_MALLOC_LISTS);
835 if (listNo == N_MALLOC_LISTS-1) {
838 return listNo_to_pszB_min(listNo+1) - 1;
843 /* A nasty hack to try and reduce fragmentation. Try and replace
844 a->freelist[lno] with another block on the same list but with a
845 lower address, with the idea of attempting to recycle the same
846 blocks rather than cruise through the address space. */
848 void swizzle ( Arena* a, UInt lno )
855 p_best = a->freelist[lno];
856 if (p_best == NULL) return;
860 // This loop bound was 20 for a long time, but experiments showed that
861 // reducing it to 10 gave the same result in all the tests, and 5 got the
862 // same result in 85--100% of cases. And it's called often enough to be
863 // noticeable in programs that allocated a lot.
864 for (i = 0; i < 5; i++) {
867 if (pn < p_best) p_best = pn;
868 if (pp < p_best) p_best = pp;
870 if (p_best < a->freelist[lno]) {
871 # ifdef VERBOSE_MALLOC
872 VG_(printf)("retreat by %ld\n", (Word)(a->freelist[lno] - p_best));
874 a->freelist[lno] = p_best;
879 /*------------------------------------------------------------*/
880 /*--- Sanity-check/debugging machinery. ---*/
881 /*------------------------------------------------------------*/
883 #define REDZONE_LO_MASK 0x31
884 #define REDZONE_HI_MASK 0x7c
886 // Do some crude sanity checks on a Block.
888 Bool blockSane ( Arena* a, Block* b )
890 # define BLEAT(str) VG_(printf)("blockSane: fail -- %s\n",str)
892 // The lo and hi size fields will be checked (indirectly) by the call
893 // to get_rz_hi_byte().
894 if (!a->clientmem && is_inuse_block(b)) {
895 for (i = 0; i < a->rz_szB; i++) {
896 if (get_rz_lo_byte(b, i) !=
897 (UByte)(((Addr)b&0xff) ^ REDZONE_LO_MASK))
898 {BLEAT("redzone-lo");return False;}
899 if (get_rz_hi_byte(b, i) !=
900 (UByte)(((Addr)b&0xff) ^ REDZONE_HI_MASK))
901 {BLEAT("redzone-hi");return False;}
908 // Print superblocks (only for debugging).
910 void ppSuperblocks ( Arena* a )
912 UInt i, j, blockno = 1;
915 for (j = 0; j < a->sblocks_used; ++j) {
916 Superblock * sb = a->sblocks[j];
919 VG_(printf)( "superblock %d at %p, sb->n_pl_bs = %lu\n",
920 blockno++, sb, sb->n_payload_bytes);
921 for (i = 0; i < sb->n_payload_bytes; i += b_bszB) {
922 Block* b = (Block*)&sb->payload_bytes[i];
923 b_bszB = get_bszB(b);
924 VG_(printf)( " block at %d, bszB %lu: ", i, b_bszB );
925 VG_(printf)( "%s, ", is_inuse_block(b) ? "inuse" : "free");
926 VG_(printf)( "%s\n", blockSane(a, b) ? "ok" : "BAD" );
928 vg_assert(i == sb->n_payload_bytes); // no overshoot at end of Sb
930 VG_(printf)( "end of superblocks\n\n" );
933 // Sanity check both the superblocks and the chains.
934 static void sanity_check_malloc_arena ( ArenaId aid )
936 UInt i, j, superblockctr, blockctr_sb, blockctr_li;
937 UInt blockctr_sb_free, listno;
938 SizeT b_bszB, b_pszB, list_min_pszB, list_max_pszB;
939 Bool thisFree, lastWasFree, sblockarrOK;
942 SizeT arena_bytes_on_loan;
945 # define BOMB VG_(core_panic)("sanity_check_malloc_arena")
947 a = arenaId_to_ArenaP(aid);
949 // Check the superblock array.
952 && a->sblocks_size >= SBLOCKS_SIZE_INITIAL
953 && a->sblocks_used <= a->sblocks_size
954 && (a->sblocks_size == SBLOCKS_SIZE_INITIAL
955 ? (a->sblocks == &a->sblocks_initial[0])
956 : (a->sblocks != &a->sblocks_initial[0]));
958 VG_(printf)("sanity_check_malloc_arena: sblock array BAD\n");
962 // First, traverse all the superblocks, inspecting the Blocks in each.
963 superblockctr = blockctr_sb = blockctr_sb_free = 0;
964 arena_bytes_on_loan = 0;
965 for (j = 0; j < a->sblocks_used; ++j) {
966 Superblock * sb = a->sblocks[j];
969 for (i = 0; i < sb->n_payload_bytes; i += mk_plain_bszB(b_bszB)) {
971 b = (Block*)&sb->payload_bytes[i];
972 b_bszB = get_bszB_as_is(b);
973 if (!blockSane(a, b)) {
974 VG_(printf)("sanity_check_malloc_arena: sb %p, block %d "
975 "(bszB %lu): BAD\n", sb, i, b_bszB );
978 thisFree = !is_inuse_block(b);
979 if (thisFree && lastWasFree) {
980 VG_(printf)("sanity_check_malloc_arena: sb %p, block %d "
981 "(bszB %lu): UNMERGED FREES\n", sb, i, b_bszB );
984 if (thisFree) blockctr_sb_free++;
986 arena_bytes_on_loan += bszB_to_pszB(a, b_bszB);
987 lastWasFree = thisFree;
989 if (i > sb->n_payload_bytes) {
990 VG_(printf)( "sanity_check_malloc_arena: sb %p: last block "
991 "overshoots end\n", sb);
996 if (arena_bytes_on_loan != a->bytes_on_loan) {
997 # ifdef VERBOSE_MALLOC
998 VG_(printf)( "sanity_check_malloc_arena: a->bytes_on_loan %ld, "
999 "arena_bytes_on_loan %ld: "
1000 "MISMATCH\n", a->bytes_on_loan, arena_bytes_on_loan);
1006 /* Second, traverse each list, checking that the back pointers make
1007 sense, counting blocks encountered, and checking that each block
1008 is an appropriate size for this list. */
1010 for (listno = 0; listno < N_MALLOC_LISTS; listno++) {
1011 list_min_pszB = listNo_to_pszB_min(listno);
1012 list_max_pszB = listNo_to_pszB_max(listno);
1013 b = a->freelist[listno];
1014 if (b == NULL) continue;
1018 if (get_prev_b(b) != b_prev) {
1019 VG_(printf)( "sanity_check_malloc_arena: list %d at %p: "
1024 b_pszB = get_pszB(a, b);
1025 if (b_pszB < list_min_pszB || b_pszB > list_max_pszB) {
1027 "sanity_check_malloc_arena: list %d at %p: "
1028 "WRONG CHAIN SIZE %luB (%luB, %luB)\n",
1029 listno, b, b_pszB, list_min_pszB, list_max_pszB );
1033 if (b == a->freelist[listno]) break;
1037 if (blockctr_sb_free != blockctr_li) {
1038 # ifdef VERBOSE_MALLOC
1039 VG_(printf)( "sanity_check_malloc_arena: BLOCK COUNT MISMATCH "
1040 "(via sbs %d, via lists %d)\n",
1041 blockctr_sb_free, blockctr_li );
1047 if (VG_(clo_verbosity) > 2)
1048 VG_(message)(Vg_DebugMsg,
1049 "%8s: %2d sbs, %5d bs, %2d/%-2d free bs, "
1050 "%7ld mmap, %7ld loan\n",
1053 blockctr_sb, blockctr_sb_free, blockctr_li,
1054 a->bytes_mmaped, a->bytes_on_loan);
1059 #define N_AN_CCS 1000
1061 typedef struct { ULong nBytes; ULong nBlocks; HChar* cc; } AnCC;
1063 static AnCC anCCs[N_AN_CCS];
1065 static Int cmp_AnCC_by_vol ( void* v1, void* v2 ) {
1066 AnCC* ancc1 = (AnCC*)v1;
1067 AnCC* ancc2 = (AnCC*)v2;
1068 if (ancc1->nBytes < ancc2->nBytes) return -1;
1069 if (ancc1->nBytes > ancc2->nBytes) return 1;
1073 static void cc_analyse_alloc_arena ( ArenaId aid )
1078 Bool thisFree, lastWasFree;
1084 a = arenaId_to_ArenaP(aid);
1085 if (a->name == NULL) {
1086 /* arena is not in use, is not initialised and will fail the
1087 sanity check that follows. */
1091 sanity_check_malloc_arena(aid);
1094 "-------- Arena \"%s\": %ld mmap'd, %ld/%ld max/curr --------\n",
1095 a->name, a->bytes_mmaped, a->bytes_on_loan_max, a->bytes_on_loan
1098 for (j = 0; j < a->sblocks_used; ++j) {
1099 Superblock * sb = a->sblocks[j];
1100 lastWasFree = False;
1101 for (i = 0; i < sb->n_payload_bytes; i += mk_plain_bszB(b_bszB)) {
1102 b = (Block*)&sb->payload_bytes[i];
1103 b_bszB = get_bszB_as_is(b);
1104 if (!blockSane(a, b)) {
1105 VG_(printf)("sanity_check_malloc_arena: sb %p, block %ld "
1106 "(bszB %lu): BAD\n", sb, i, b_bszB );
1109 thisFree = !is_inuse_block(b);
1110 if (thisFree && lastWasFree) {
1111 VG_(printf)("sanity_check_malloc_arena: sb %p, block %ld "
1112 "(bszB %lu): UNMERGED FREES\n", sb, i, b_bszB );
1115 lastWasFree = thisFree;
1117 if (thisFree) continue;
1120 VG_(printf)("block: inUse=%d pszB=%d cc=%s\n",
1122 (Int)bszB_to_pszB(a, b_bszB),
1126 for (k = 0; k < n_ccs; k++) {
1127 tl_assert(anCCs[k].cc);
1128 if (0 == VG_(strcmp)(cc, anCCs[k].cc))
1131 tl_assert(k >= 0 && k <= n_ccs);
1134 tl_assert(n_ccs < N_AN_CCS-1);
1136 anCCs[k].nBytes = 0;
1137 anCCs[k].nBlocks = 0;
1141 tl_assert(k >= 0 && k < n_ccs && k < N_AN_CCS);
1142 anCCs[k].nBytes += (ULong)bszB_to_pszB(a, b_bszB);
1145 if (i > sb->n_payload_bytes) {
1146 VG_(printf)( "sanity_check_malloc_arena: sb %p: last block "
1147 "overshoots end\n", sb);
1152 VG_(ssort)( &anCCs[0], n_ccs, sizeof(anCCs[0]), cmp_AnCC_by_vol );
1154 for (k = 0; k < n_ccs; k++) {
1155 VG_(printf)("%'13llu in %'9llu: %s\n",
1156 anCCs[k].nBytes, anCCs[k].nBlocks, anCCs[k].cc );
1163 void VG_(sanity_check_malloc_all) ( void )
1166 for (i = 0; i < VG_N_ARENAS; i++) {
1167 if (i == VG_AR_CLIENT && !client_inited)
1169 sanity_check_malloc_arena ( i );
1174 /*------------------------------------------------------------*/
1175 /*--- Creating and deleting blocks. ---*/
1176 /*------------------------------------------------------------*/
1178 // Mark the bytes at b .. b+bszB-1 as not in use, and add them to the
1179 // relevant free list.
1182 void mkFreeBlock ( Arena* a, Block* b, SizeT bszB, UInt b_lno )
1184 SizeT pszB = bszB_to_pszB(a, bszB);
1185 vg_assert(b_lno == pszB_to_listNo(pszB));
1186 //zzVALGRIND_MAKE_MEM_UNDEFINED(b, bszB);
1187 // Set the size fields and indicate not-in-use.
1188 set_bszB(b, mk_free_bszB(bszB));
1190 // Add to the relevant list.
1191 if (a->freelist[b_lno] == NULL) {
1194 a->freelist[b_lno] = b;
1196 Block* b_prev = get_prev_b(a->freelist[b_lno]);
1197 Block* b_next = a->freelist[b_lno];
1198 set_next_b(b_prev, b);
1199 set_prev_b(b_next, b);
1200 set_next_b(b, b_next);
1201 set_prev_b(b, b_prev);
1203 # ifdef DEBUG_MALLOC
1204 (void)blockSane(a,b);
1208 // Mark the bytes at b .. b+bszB-1 as in use, and set up the block
1211 void mkInuseBlock ( Arena* a, Block* b, SizeT bszB )
1214 vg_assert(bszB >= min_useful_bszB(a));
1215 //zzVALGRIND_MAKE_MEM_UNDEFINED(b, bszB);
1216 set_bszB(b, mk_inuse_bszB(bszB));
1217 set_prev_b(b, NULL); // Take off freelist
1218 set_next_b(b, NULL); // ditto
1219 if (!a->clientmem) {
1220 for (i = 0; i < a->rz_szB; i++) {
1221 set_rz_lo_byte(b, i, (UByte)(((Addr)b&0xff) ^ REDZONE_LO_MASK));
1222 set_rz_hi_byte(b, i, (UByte)(((Addr)b&0xff) ^ REDZONE_HI_MASK));
1225 # ifdef DEBUG_MALLOC
1226 (void)blockSane(a,b);
1230 // Remove a block from a given list. Does no sanity checking.
1232 void unlinkBlock ( Arena* a, Block* b, UInt listno )
1234 vg_assert(listno < N_MALLOC_LISTS);
1235 if (get_prev_b(b) == b) {
1236 // Only one element in the list; treat it specially.
1237 vg_assert(get_next_b(b) == b);
1238 a->freelist[listno] = NULL;
1240 Block* b_prev = get_prev_b(b);
1241 Block* b_next = get_next_b(b);
1242 a->freelist[listno] = b_prev;
1243 set_next_b(b_prev, b_next);
1244 set_prev_b(b_next, b_prev);
1245 swizzle ( a, listno );
1247 set_prev_b(b, NULL);
1248 set_next_b(b, NULL);
1252 /*------------------------------------------------------------*/
1253 /*--- Core-visible functions. ---*/
1254 /*------------------------------------------------------------*/
1256 // Align the request size.
1258 SizeT align_req_pszB ( SizeT req_pszB )
1260 SizeT n = VG_MIN_MALLOC_SZB-1;
1261 return ((req_pszB + n) & (~n));
1264 void* VG_(arena_malloc) ( ArenaId aid, HChar* cc, SizeT req_pszB )
1266 SizeT req_bszB, frag_bszB, b_bszB;
1273 ensure_mm_init(aid);
1274 a = arenaId_to_ArenaP(aid);
1276 vg_assert(req_pszB < MAX_PSZB);
1277 req_pszB = align_req_pszB(req_pszB);
1278 req_bszB = pszB_to_bszB(a, req_pszB);
1280 // You must provide a cost-center name against which to charge
1281 // this allocation; it isn't optional.
1284 // Scan through all the big-enough freelists for a block.
1286 // Nb: this scanning might be expensive in some cases. Eg. if you
1287 // allocate lots of small objects without freeing them, but no
1288 // medium-sized objects, it will repeatedly scanning through the whole
1289 // list, and each time not find any free blocks until the last element.
1291 // If this becomes a noticeable problem... the loop answers the question
1292 // "where is the first nonempty list above me?" And most of the time,
1293 // you ask the same question and get the same answer. So it would be
1294 // good to somehow cache the results of previous searches.
1295 // One possibility is an array (with N_MALLOC_LISTS elements) of
1296 // shortcuts. shortcut[i] would give the index number of the nearest
1297 // larger list above list i which is non-empty. Then this loop isn't
1298 // necessary. However, we'd have to modify some section [ .. i-1] of the
1299 // shortcut array every time a list [i] changes from empty to nonempty or
1300 // back. This would require care to avoid pathological worst-case
1303 for (lno = pszB_to_listNo(req_pszB); lno < N_MALLOC_LISTS; lno++) {
1304 b = a->freelist[lno];
1305 if (NULL == b) continue; // If this list is empty, try the next one.
1307 b_bszB = get_bszB(b);
1308 if (b_bszB >= req_bszB) goto obtained_block; // success!
1310 if (b == a->freelist[lno]) break; // traversed entire freelist
1314 // If we reach here, no suitable block found, allocate a new superblock
1315 vg_assert(lno == N_MALLOC_LISTS);
1316 new_sb = newSuperblock(a, req_bszB);
1317 if (NULL == new_sb) {
1318 // Should only fail if for client, otherwise, should have aborted
1320 vg_assert(VG_AR_CLIENT == aid);
1324 vg_assert(a->sblocks_used <= a->sblocks_size);
1325 if (a->sblocks_used == a->sblocks_size) {
1326 Superblock ** array;
1327 SysRes sres = VG_(am_sbrk_anon_float_valgrind)(sizeof(Superblock *) *
1328 a->sblocks_size * 2);
1329 if (sr_isError(sres)) {
1330 VG_(out_of_memory_NORETURN)("arena_init", sizeof(Superblock *) *
1331 a->sblocks_size * 2);
1334 array = (Superblock**)(AddrH)sr_Res(sres);
1335 for (i = 0; i < a->sblocks_used; ++i) array[i] = a->sblocks[i];
1337 a->sblocks_size *= 2;
1339 VG_(debugLog)(1, "mallocfree",
1340 "sblock array for arena `%s' resized to %ld\n",
1341 a->name, a->sblocks_size);
1344 vg_assert(a->sblocks_used < a->sblocks_size);
1346 i = a->sblocks_used;
1348 if (a->sblocks[i-1] > new_sb) {
1349 a->sblocks[i] = a->sblocks[i-1];
1355 a->sblocks[i] = new_sb;
1358 b = (Block*)&new_sb->payload_bytes[0];
1359 lno = pszB_to_listNo(bszB_to_pszB(a, new_sb->n_payload_bytes));
1360 mkFreeBlock ( a, b, new_sb->n_payload_bytes, lno);
1361 if (VG_(clo_profile_heap))
1362 set_cc(b, "admin.free-new-sb-1");
1366 // Ok, we can allocate from b, which lives in list lno.
1367 vg_assert(b != NULL);
1368 vg_assert(lno < N_MALLOC_LISTS);
1369 vg_assert(a->freelist[lno] != NULL);
1370 b_bszB = get_bszB(b);
1371 // req_bszB is the size of the block we are after. b_bszB is the
1372 // size of what we've actually got. */
1373 vg_assert(b_bszB >= req_bszB);
1375 // Could we split this block and still get a useful fragment?
1376 frag_bszB = b_bszB - req_bszB;
1377 if (frag_bszB >= min_useful_bszB(a)) {
1378 // Yes, split block in two, put the fragment on the appropriate free
1379 // list, and update b_bszB accordingly.
1380 // printf( "split %dB into %dB and %dB\n", b_bszB, req_bszB, frag_bszB );
1381 unlinkBlock(a, b, lno);
1382 mkInuseBlock(a, b, req_bszB);
1383 if (VG_(clo_profile_heap))
1385 mkFreeBlock(a, &b[req_bszB], frag_bszB,
1386 pszB_to_listNo(bszB_to_pszB(a, frag_bszB)));
1387 if (VG_(clo_profile_heap))
1388 set_cc(&b[req_bszB], "admin.fragmentation-1");
1389 b_bszB = get_bszB(b);
1391 // No, mark as in use and use as-is.
1392 unlinkBlock(a, b, lno);
1393 mkInuseBlock(a, b, b_bszB);
1394 if (VG_(clo_profile_heap))
1399 a->bytes_on_loan += bszB_to_pszB(a, b_bszB);
1400 if (a->bytes_on_loan > a->bytes_on_loan_max) {
1401 a->bytes_on_loan_max = a->bytes_on_loan;
1402 if (a->bytes_on_loan_max >= a->next_profile_at) {
1403 /* next profile after 10% more growth */
1406 (((ULong)a->bytes_on_loan_max) * 110ULL) / 100ULL );
1407 if (VG_(clo_profile_heap))
1408 cc_analyse_alloc_arena(aid);
1412 # ifdef DEBUG_MALLOC
1413 sanity_check_malloc_arena(aid);
1416 v = get_block_payload(a, b);
1417 vg_assert( (((Addr)v) & (VG_MIN_MALLOC_SZB-1)) == 0 );
1419 /* VALGRIND_MALLOCLIKE_BLOCK(v, req_pszB, 0, False); */
1421 /* For debugging/testing purposes, fill the newly allocated area
1422 with a definite value in an attempt to shake out any
1423 uninitialised uses of the data (by V core / V tools, not by the
1424 client). Testing on 25 Nov 07 with the values 0x00, 0xFF, 0x55,
1425 0xAA showed no differences in the regression tests on
1426 amd64-linux. Note, is disabled by default. */
1427 if (0 && aid != VG_AR_CLIENT)
1428 VG_(memset)(v, 0xAA, (SizeT)req_pszB);
1434 void VG_(arena_free) ( ArenaId aid, void* ptr )
1441 SizeT b_bszB, b_pszB, other_bszB;
1445 ensure_mm_init(aid);
1446 a = arenaId_to_ArenaP(aid);
1452 b = get_payload_block(a, ptr);
1454 /* If this is one of V's areas, check carefully the block we're
1455 getting back. This picks up simple block-end overruns. */
1456 if (aid != VG_AR_CLIENT)
1457 vg_assert(blockSane(a, b));
1459 b_bszB = get_bszB(b);
1460 b_pszB = bszB_to_pszB(a, b_bszB);
1461 sb = findSb( a, b );
1462 sb_start = &sb->payload_bytes[0];
1463 sb_end = &sb->payload_bytes[sb->n_payload_bytes - 1];
1465 a->bytes_on_loan -= b_pszB;
1467 /* If this is one of V's areas, fill it up with junk to enhance the
1468 chances of catching any later reads of it. Note, 0xDD is
1469 carefully chosen junk :-), in that: (1) 0xDDDDDDDD is an invalid
1470 and non-word-aligned address on most systems, and (2) 0xDD is a
1471 value which is unlikely to be generated by the new compressed
1472 Vbits representation for memcheck. */
1473 if (aid != VG_AR_CLIENT)
1474 VG_(memset)(ptr, 0xDD, (SizeT)b_pszB);
1476 // Put this chunk back on a list somewhere.
1477 b_listno = pszB_to_listNo(b_pszB);
1478 mkFreeBlock( a, b, b_bszB, b_listno );
1479 if (VG_(clo_profile_heap))
1480 set_cc(b, "admin.free-1");
1482 // See if this block can be merged with its successor.
1483 // First test if we're far enough before the superblock's end to possibly
1484 // have a successor.
1485 other_b = b + b_bszB;
1486 if (other_b+min_useful_bszB(a)-1 <= (Block*)sb_end) {
1487 // Ok, we have a successor, merge if it's not in use.
1488 other_bszB = get_bszB(other_b);
1489 if (!is_inuse_block(other_b)) {
1490 // VG_(printf)( "merge-successor\n");
1491 # ifdef DEBUG_MALLOC
1492 vg_assert(blockSane(a, other_b));
1494 unlinkBlock( a, b, b_listno );
1495 unlinkBlock( a, other_b, pszB_to_listNo(bszB_to_pszB(a,other_bszB)) );
1496 b_bszB += other_bszB;
1497 b_listno = pszB_to_listNo(bszB_to_pszB(a, b_bszB));
1498 mkFreeBlock( a, b, b_bszB, b_listno );
1499 if (VG_(clo_profile_heap))
1500 set_cc(b, "admin.free-2");
1503 // Not enough space for successor: check that b is the last block
1504 // ie. there are no unused bytes at the end of the Superblock.
1505 vg_assert(other_b-1 == (Block*)sb_end);
1508 // Then see if this block can be merged with its predecessor.
1509 // First test if we're far enough after the superblock's start to possibly
1510 // have a predecessor.
1511 if (b >= (Block*)sb_start + min_useful_bszB(a)) {
1512 // Ok, we have a predecessor, merge if it's not in use.
1513 other_b = get_predecessor_block( b );
1514 other_bszB = get_bszB(other_b);
1515 if (!is_inuse_block(other_b)) {
1516 // VG_(printf)( "merge-predecessor\n");
1517 unlinkBlock( a, b, b_listno );
1518 unlinkBlock( a, other_b, pszB_to_listNo(bszB_to_pszB(a, other_bszB)) );
1520 b_bszB += other_bszB;
1521 b_listno = pszB_to_listNo(bszB_to_pszB(a, b_bszB));
1522 mkFreeBlock( a, b, b_bszB, b_listno );
1523 if (VG_(clo_profile_heap))
1524 set_cc(b, "admin.free-3");
1527 // Not enough space for predecessor: check that b is the first block,
1528 // ie. there are no unused bytes at the start of the Superblock.
1529 vg_assert((Block*)sb_start == b);
1532 # ifdef DEBUG_MALLOC
1533 sanity_check_malloc_arena(aid);
1536 //zzVALGRIND_FREELIKE_BLOCK(ptr, 0);
1541 The idea for malloc_aligned() is to allocate a big block, base, and
1542 then split it into two parts: frag, which is returned to the the
1543 free pool, and align, which is the bit we're really after. Here's
1544 a picture. L and H denote the block lower and upper overheads, in
1545 bytes. The details are gruesome. Note it is slightly complicated
1546 because the initial request to generate base may return a bigger
1547 block than we asked for, so it is important to distinguish the base
1548 request size and the base actual size.
1556 +---+ +---+---+ +---+
1557 | L |----------------| H | L |---------------| H |
1558 +---+ +---+---+ +---+
1562 | base_p this addr must be aligned
1567 <------ frag_bszB -------> . . .
1568 . <------------- base_pszB_act -----------> .
1572 void* VG_(arena_memalign) ( ArenaId aid, HChar* cc,
1573 SizeT req_alignB, SizeT req_pszB )
1575 SizeT base_pszB_req, base_pszB_act, frag_bszB;
1576 Block *base_b, *align_b;
1577 UByte *base_p, *align_p;
1578 SizeT saved_bytes_on_loan;
1581 ensure_mm_init(aid);
1582 a = arenaId_to_ArenaP(aid);
1584 vg_assert(req_pszB < MAX_PSZB);
1586 // You must provide a cost-center name against which to charge
1587 // this allocation; it isn't optional.
1590 // Check that the requested alignment seems reasonable; that is, is
1592 if (req_alignB < VG_MIN_MALLOC_SZB
1593 || req_alignB > 1048576
1594 || VG_(log2)( req_alignB ) == -1 /* not a power of 2 */) {
1595 VG_(printf)("VG_(arena_memalign)(%p, %lu, %lu)\n"
1596 "bad alignment value %lu\n"
1597 "(it is too small, too big, or not a power of two)",
1598 a, req_alignB, req_pszB, req_alignB );
1599 VG_(core_panic)("VG_(arena_memalign)");
1603 vg_assert(req_alignB % VG_MIN_MALLOC_SZB == 0);
1605 /* Required payload size for the aligned chunk. */
1606 req_pszB = align_req_pszB(req_pszB);
1608 /* Payload size to request for the big block that we will split up. */
1609 base_pszB_req = req_pszB + min_useful_bszB(a) + req_alignB;
1611 /* Payload ptr for the block we are going to split. Note this
1612 changes a->bytes_on_loan; we save and restore it ourselves. */
1613 saved_bytes_on_loan = a->bytes_on_loan;
1614 base_p = VG_(arena_malloc) ( aid, cc, base_pszB_req );
1615 a->bytes_on_loan = saved_bytes_on_loan;
1617 /* Give up if we couldn't allocate enough space */
1621 /* Block ptr for the block we are going to split. */
1622 base_b = get_payload_block ( a, base_p );
1624 /* Pointer to the payload of the aligned block we are going to
1625 return. This has to be suitably aligned. */
1626 align_p = align_upwards ( base_b + 2 * overhead_szB_lo(a)
1627 + overhead_szB_hi(a),
1629 align_b = get_payload_block(a, align_p);
1631 /* The block size of the fragment we will create. This must be big
1632 enough to actually create a fragment. */
1633 frag_bszB = align_b - base_b;
1635 vg_assert(frag_bszB >= min_useful_bszB(a));
1637 /* The actual payload size of the block we are going to split. */
1638 base_pszB_act = get_pszB(a, base_b);
1640 /* Create the fragment block, and put it back on the relevant free list. */
1641 mkFreeBlock ( a, base_b, frag_bszB,
1642 pszB_to_listNo(bszB_to_pszB(a, frag_bszB)) );
1643 if (VG_(clo_profile_heap))
1644 set_cc(base_b, "admin.frag-memalign-1");
1646 /* Create the aligned block. */
1647 mkInuseBlock ( a, align_b,
1648 base_p + base_pszB_act
1649 + overhead_szB_hi(a) - (UByte*)align_b );
1650 if (VG_(clo_profile_heap))
1651 set_cc(align_b, cc);
1653 /* Final sanity checks. */
1654 vg_assert( is_inuse_block(get_payload_block(a, align_p)) );
1656 vg_assert(req_pszB <= get_pszB(a, get_payload_block(a, align_p)));
1658 a->bytes_on_loan += get_pszB(a, get_payload_block(a, align_p));
1659 if (a->bytes_on_loan > a->bytes_on_loan_max)
1660 a->bytes_on_loan_max = a->bytes_on_loan;
1662 # ifdef DEBUG_MALLOC
1663 sanity_check_malloc_arena(aid);
1666 vg_assert( (((Addr)align_p) % req_alignB) == 0 );
1668 //zzVALGRIND_MALLOCLIKE_BLOCK(align_p, req_pszB, 0, False);
1674 SizeT VG_(arena_malloc_usable_size) ( ArenaId aid, void* ptr )
1676 Arena* a = arenaId_to_ArenaP(aid);
1677 Block* b = get_payload_block(a, ptr);
1678 return get_pszB(a, b);
1682 // Implementation of mallinfo(). There is no recent standard that defines
1683 // the behavior of mallinfo(). The meaning of the fields in struct mallinfo
1686 // struct mallinfo {
1687 // int arena; /* total space in arena */
1688 // int ordblks; /* number of ordinary blocks */
1689 // int smblks; /* number of small blocks */
1690 // int hblks; /* number of holding blocks */
1691 // int hblkhd; /* space in holding block headers */
1692 // int usmblks; /* space in small blocks in use */
1693 // int fsmblks; /* space in free small blocks */
1694 // int uordblks; /* space in ordinary blocks in use */
1695 // int fordblks; /* space in free ordinary blocks */
1696 // int keepcost; /* space penalty if keep option */
1700 // The glibc documentation about mallinfo (which is somewhat outdated) can
1702 // http://www.gnu.org/software/libtool/manual/libc/Statistics-of-Malloc.html
1704 // See also http://bugs.kde.org/show_bug.cgi?id=160956.
1706 // Regarding the implementation of VG_(mallinfo)(): we cannot return the
1707 // whole struct as the library function does, because this is called by a
1708 // client request. So instead we use a pointer to do call by reference.
1709 void VG_(mallinfo) ( ThreadId tid, struct vg_mallinfo* mi )
1711 UWord i, free_blocks, free_blocks_size;
1712 Arena* a = arenaId_to_ArenaP(VG_AR_CLIENT);
1714 // Traverse free list and calculate free blocks statistics.
1715 // This may seem slow but glibc works the same way.
1716 free_blocks_size = free_blocks = 0;
1717 for (i = 0; i < N_MALLOC_LISTS; i++) {
1718 Block* b = a->freelist[i];
1719 if (b == NULL) continue;
1722 free_blocks_size += (UWord)get_pszB(a, b);
1724 if (b == a->freelist[i]) break;
1728 // We don't have fastbins so smblks & fsmblks are always 0. Also we don't
1729 // have a separate mmap allocator so set hblks & hblkhd to 0.
1730 mi->arena = a->bytes_mmaped;
1731 mi->ordblks = free_blocks + VG_(free_queue_length);
1737 mi->uordblks = a->bytes_on_loan - VG_(free_queue_volume);
1738 mi->fordblks = free_blocks_size + VG_(free_queue_volume);
1739 mi->keepcost = 0; // may want some value in here
1743 /*------------------------------------------------------------*/
1744 /*--- Services layered on top of malloc/free. ---*/
1745 /*------------------------------------------------------------*/
1747 void* VG_(arena_calloc) ( ArenaId aid, HChar* cc,
1748 SizeT nmemb, SizeT bytes_per_memb )
1753 size = nmemb * bytes_per_memb;
1754 vg_assert(size >= nmemb && size >= bytes_per_memb);// check against overflow
1756 p = VG_(arena_malloc) ( aid, cc, size );
1758 VG_(memset)(p, 0, size);
1760 //zzVALGRIND_MALLOCLIKE_BLOCK(p, size, 0, True);
1766 void* VG_(arena_realloc) ( ArenaId aid, HChar* cc,
1767 void* ptr, SizeT req_pszB )
1774 ensure_mm_init(aid);
1775 a = arenaId_to_ArenaP(aid);
1777 vg_assert(req_pszB < MAX_PSZB);
1780 return VG_(arena_malloc)(aid, cc, req_pszB);
1783 if (req_pszB == 0) {
1784 VG_(arena_free)(aid, ptr);
1788 b = get_payload_block(a, ptr);
1789 vg_assert(blockSane(a, b));
1791 vg_assert(is_inuse_block(b));
1792 old_pszB = get_pszB(a, b);
1794 if (req_pszB <= old_pszB) {
1798 p_new = VG_(arena_malloc) ( aid, cc, req_pszB );
1800 VG_(memcpy)(p_new, ptr, old_pszB);
1802 VG_(arena_free)(aid, ptr);
1808 /* Inline just for the wrapper VG_(strdup) below */
1809 __inline__ Char* VG_(arena_strdup) ( ArenaId aid, HChar* cc,
1819 len = VG_(strlen)(s) + 1;
1820 res = VG_(arena_malloc) (aid, cc, len);
1822 for (i = 0; i < len; i++)
1828 /*------------------------------------------------------------*/
1829 /*--- Tool-visible functions. ---*/
1830 /*------------------------------------------------------------*/
1832 // All just wrappers to avoid exposing arenas to tools.
1834 void* VG_(malloc) ( HChar* cc, SizeT nbytes )
1836 return VG_(arena_malloc) ( VG_AR_TOOL, cc, nbytes );
1839 void VG_(free) ( void* ptr )
1841 VG_(arena_free) ( VG_AR_TOOL, ptr );
1844 void* VG_(calloc) ( HChar* cc, SizeT nmemb, SizeT bytes_per_memb )
1846 return VG_(arena_calloc) ( VG_AR_TOOL, cc, nmemb, bytes_per_memb );
1849 void* VG_(realloc) ( HChar* cc, void* ptr, SizeT size )
1851 return VG_(arena_realloc) ( VG_AR_TOOL, cc, ptr, size );
1854 Char* VG_(strdup) ( HChar* cc, const Char* s )
1856 return VG_(arena_strdup) ( VG_AR_TOOL, cc, s );
1859 // Useful for querying user blocks.
1860 SizeT VG_(malloc_usable_size) ( void* p )
1862 return VG_(arena_malloc_usable_size)(VG_AR_CLIENT, p);
1866 /*--------------------------------------------------------------------*/
1868 /*--------------------------------------------------------------------*/