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