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