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