1// Copyright (c) 2005, 2007, Google Inc. 2// All rights reserved. 3// Copyright (C) 2005, 2006, 2007, 2008, 2009, 2011 Apple Inc. All rights reserved. 4// 5// Redistribution and use in source and binary forms, with or without 6// modification, are permitted provided that the following conditions are 7// met: 8// 9// * Redistributions of source code must retain the above copyright 10// notice, this list of conditions and the following disclaimer. 11// * Redistributions in binary form must reproduce the above 12// copyright notice, this list of conditions and the following disclaimer 13// in the documentation and/or other materials provided with the 14// distribution. 15// * Neither the name of Google Inc. nor the names of its 16// contributors may be used to endorse or promote products derived from 17// this software without specific prior written permission. 18// 19// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 31// --- 32// Author: Sanjay Ghemawat <opensource@google.com> 33// 34// A malloc that uses a per-thread cache to satisfy small malloc requests. 35// (The time for malloc/free of a small object drops from 300 ns to 50 ns.) 36// 37// See doc/tcmalloc.html for a high-level 38// description of how this malloc works. 39// 40// SYNCHRONIZATION 41// 1. The thread-specific lists are accessed without acquiring any locks. 42// This is safe because each such list is only accessed by one thread. 43// 2. We have a lock per central free-list, and hold it while manipulating 44// the central free list for a particular size. 45// 3. The central page allocator is protected by "pageheap_lock". 46// 4. The pagemap (which maps from page-number to descriptor), 47// can be read without holding any locks, and written while holding 48// the "pageheap_lock". 49// 5. To improve performance, a subset of the information one can get 50// from the pagemap is cached in a data structure, pagemap_cache_, 51// that atomically reads and writes its entries. This cache can be 52// read and written without locking. 53// 54// This multi-threaded access to the pagemap is safe for fairly 55// subtle reasons. We basically assume that when an object X is 56// allocated by thread A and deallocated by thread B, there must 57// have been appropriate synchronization in the handoff of object 58// X from thread A to thread B. The same logic applies to pagemap_cache_. 59// 60// THE PAGEID-TO-SIZECLASS CACHE 61// Hot PageID-to-sizeclass mappings are held by pagemap_cache_. If this cache 62// returns 0 for a particular PageID then that means "no information," not that 63// the sizeclass is 0. The cache may have stale information for pages that do 64// not hold the beginning of any free()'able object. Staleness is eliminated 65// in Populate() for pages with sizeclass > 0 objects, and in do_malloc() and 66// do_memalign() for all other relevant pages. 67// 68// TODO: Bias reclamation to larger addresses 69// TODO: implement mallinfo/mallopt 70// TODO: Better testing 71// 72// 9/28/2003 (new page-level allocator replaces ptmalloc2): 73// * malloc/free of small objects goes from ~300 ns to ~50 ns. 74// * allocation of a reasonably complicated struct 75// goes from about 1100 ns to about 300 ns. 76 77#include "config.h" 78#include "FastMalloc.h" 79 80#include "Assertions.h" 81#include "CurrentTime.h" 82 83#include <limits> 84#if OS(WINDOWS) 85#include <windows.h> 86#else 87#include <pthread.h> 88#endif 89#include <string.h> 90#include <wtf/DataLog.h> 91#include <wtf/StdLibExtras.h> 92 93#if OS(DARWIN) 94#include <mach/mach_init.h> 95#include <malloc/malloc.h> 96#endif 97 98#ifndef NO_TCMALLOC_SAMPLES 99#ifdef WTF_CHANGES 100#define NO_TCMALLOC_SAMPLES 101#endif 102#endif 103 104#if !(defined(USE_SYSTEM_MALLOC) && USE_SYSTEM_MALLOC) && defined(NDEBUG) 105#define FORCE_SYSTEM_MALLOC 0 106#else 107#define FORCE_SYSTEM_MALLOC 1 108#endif 109 110// Harden the pointers stored in the TCMalloc linked lists 111#define ENABLE_TCMALLOC_HARDENING 1 112 113// Use a background thread to periodically scavenge memory to release back to the system 114#define USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 1 115 116#ifndef NDEBUG 117namespace WTF { 118 119#if OS(WINDOWS) 120 121// TLS_OUT_OF_INDEXES is not defined on WinCE. 122#ifndef TLS_OUT_OF_INDEXES 123#define TLS_OUT_OF_INDEXES 0xffffffff 124#endif 125 126static DWORD isForibiddenTlsIndex = TLS_OUT_OF_INDEXES; 127static const LPVOID kTlsAllowValue = reinterpret_cast<LPVOID>(0); // Must be zero. 128static const LPVOID kTlsForbiddenValue = reinterpret_cast<LPVOID>(1); 129 130#if !ASSERT_DISABLED 131static bool isForbidden() 132{ 133 // By default, fastMalloc is allowed so we don't allocate the 134 // tls index unless we're asked to make it forbidden. If TlsSetValue 135 // has not been called on a thread, the value returned by TlsGetValue is 0. 136 return (isForibiddenTlsIndex != TLS_OUT_OF_INDEXES) && (TlsGetValue(isForibiddenTlsIndex) == kTlsForbiddenValue); 137} 138#endif 139 140void fastMallocForbid() 141{ 142 if (isForibiddenTlsIndex == TLS_OUT_OF_INDEXES) 143 isForibiddenTlsIndex = TlsAlloc(); // a little racey, but close enough for debug only 144 TlsSetValue(isForibiddenTlsIndex, kTlsForbiddenValue); 145} 146 147void fastMallocAllow() 148{ 149 if (isForibiddenTlsIndex == TLS_OUT_OF_INDEXES) 150 return; 151 TlsSetValue(isForibiddenTlsIndex, kTlsAllowValue); 152} 153 154#else // !OS(WINDOWS) 155 156static pthread_key_t isForbiddenKey; 157static pthread_once_t isForbiddenKeyOnce = PTHREAD_ONCE_INIT; 158static void initializeIsForbiddenKey() 159{ 160 pthread_key_create(&isForbiddenKey, 0); 161} 162 163#if !ASSERT_DISABLED 164static bool isForbidden() 165{ 166 pthread_once(&isForbiddenKeyOnce, initializeIsForbiddenKey); 167 return !!pthread_getspecific(isForbiddenKey); 168} 169#endif 170 171void fastMallocForbid() 172{ 173 pthread_once(&isForbiddenKeyOnce, initializeIsForbiddenKey); 174 pthread_setspecific(isForbiddenKey, &isForbiddenKey); 175} 176 177void fastMallocAllow() 178{ 179 pthread_once(&isForbiddenKeyOnce, initializeIsForbiddenKey); 180 pthread_setspecific(isForbiddenKey, 0); 181} 182#endif // OS(WINDOWS) 183 184} // namespace WTF 185#endif // NDEBUG 186 187namespace WTF { 188 189 190namespace Internal { 191#if !ENABLE(WTF_MALLOC_VALIDATION) 192WTF_EXPORT_PRIVATE void fastMallocMatchFailed(void*); 193#else 194COMPILE_ASSERT(((sizeof(ValidationHeader) % sizeof(AllocAlignmentInteger)) == 0), ValidationHeader_must_produce_correct_alignment); 195#endif 196 197NO_RETURN_DUE_TO_CRASH void fastMallocMatchFailed(void*) 198{ 199 CRASH(); 200} 201 202} // namespace Internal 203 204 205void* fastZeroedMalloc(size_t n) 206{ 207 void* result = fastMalloc(n); 208 memset(result, 0, n); 209 return result; 210} 211 212char* fastStrDup(const char* src) 213{ 214 size_t len = strlen(src) + 1; 215 char* dup = static_cast<char*>(fastMalloc(len)); 216 memcpy(dup, src, len); 217 return dup; 218} 219 220TryMallocReturnValue tryFastZeroedMalloc(size_t n) 221{ 222 void* result; 223 if (!tryFastMalloc(n).getValue(result)) 224 return 0; 225 memset(result, 0, n); 226 return result; 227} 228 229} // namespace WTF 230 231#if FORCE_SYSTEM_MALLOC 232 233#if OS(WINDOWS) 234#include <malloc.h> 235#endif 236 237namespace WTF { 238 239size_t fastMallocGoodSize(size_t bytes) 240{ 241#if OS(DARWIN) 242 return malloc_good_size(bytes); 243#else 244 return bytes; 245#endif 246} 247 248TryMallocReturnValue tryFastMalloc(size_t n) 249{ 250 ASSERT(!isForbidden()); 251 252#if ENABLE(WTF_MALLOC_VALIDATION) 253 if (std::numeric_limits<size_t>::max() - Internal::ValidationBufferSize <= n) // If overflow would occur... 254 return 0; 255 256 void* result = malloc(n + Internal::ValidationBufferSize); 257 if (!result) 258 return 0; 259 Internal::ValidationHeader* header = static_cast<Internal::ValidationHeader*>(result); 260 header->m_size = n; 261 header->m_type = Internal::AllocTypeMalloc; 262 header->m_prefix = static_cast<unsigned>(Internal::ValidationPrefix); 263 result = header + 1; 264 *Internal::fastMallocValidationSuffix(result) = Internal::ValidationSuffix; 265 fastMallocValidate(result); 266 return result; 267#else 268 return malloc(n); 269#endif 270} 271 272void* fastMalloc(size_t n) 273{ 274 ASSERT(!isForbidden()); 275 276#if ENABLE(WTF_MALLOC_VALIDATION) 277 TryMallocReturnValue returnValue = tryFastMalloc(n); 278 void* result; 279 if (!returnValue.getValue(result)) 280 CRASH(); 281#else 282 void* result = malloc(n); 283#endif 284 285 if (!result) 286 CRASH(); 287 288 return result; 289} 290 291TryMallocReturnValue tryFastCalloc(size_t n_elements, size_t element_size) 292{ 293 ASSERT(!isForbidden()); 294 295#if ENABLE(WTF_MALLOC_VALIDATION) 296 size_t totalBytes = n_elements * element_size; 297 if (n_elements > 1 && element_size && (totalBytes / element_size) != n_elements) 298 return 0; 299 300 TryMallocReturnValue returnValue = tryFastMalloc(totalBytes); 301 void* result; 302 if (!returnValue.getValue(result)) 303 return 0; 304 memset(result, 0, totalBytes); 305 fastMallocValidate(result); 306 return result; 307#else 308 return calloc(n_elements, element_size); 309#endif 310} 311 312void* fastCalloc(size_t n_elements, size_t element_size) 313{ 314 ASSERT(!isForbidden()); 315 316#if ENABLE(WTF_MALLOC_VALIDATION) 317 TryMallocReturnValue returnValue = tryFastCalloc(n_elements, element_size); 318 void* result; 319 if (!returnValue.getValue(result)) 320 CRASH(); 321#else 322 void* result = calloc(n_elements, element_size); 323#endif 324 325 if (!result) 326 CRASH(); 327 328 return result; 329} 330 331void fastFree(void* p) 332{ 333 ASSERT(!isForbidden()); 334 335#if ENABLE(WTF_MALLOC_VALIDATION) 336 if (!p) 337 return; 338 339 fastMallocMatchValidateFree(p, Internal::AllocTypeMalloc); 340 Internal::ValidationHeader* header = Internal::fastMallocValidationHeader(p); 341 memset(p, 0xCC, header->m_size); 342 free(header); 343#else 344 free(p); 345#endif 346} 347 348TryMallocReturnValue tryFastRealloc(void* p, size_t n) 349{ 350 ASSERT(!isForbidden()); 351 352#if ENABLE(WTF_MALLOC_VALIDATION) 353 if (p) { 354 if (std::numeric_limits<size_t>::max() - Internal::ValidationBufferSize <= n) // If overflow would occur... 355 return 0; 356 fastMallocValidate(p); 357 Internal::ValidationHeader* result = static_cast<Internal::ValidationHeader*>(realloc(Internal::fastMallocValidationHeader(p), n + Internal::ValidationBufferSize)); 358 if (!result) 359 return 0; 360 result->m_size = n; 361 result = result + 1; 362 *fastMallocValidationSuffix(result) = Internal::ValidationSuffix; 363 fastMallocValidate(result); 364 return result; 365 } else { 366 return fastMalloc(n); 367 } 368#else 369 return realloc(p, n); 370#endif 371} 372 373void* fastRealloc(void* p, size_t n) 374{ 375 ASSERT(!isForbidden()); 376 377#if ENABLE(WTF_MALLOC_VALIDATION) 378 TryMallocReturnValue returnValue = tryFastRealloc(p, n); 379 void* result; 380 if (!returnValue.getValue(result)) 381 CRASH(); 382#else 383 void* result = realloc(p, n); 384#endif 385 386 if (!result) 387 CRASH(); 388 return result; 389} 390 391void releaseFastMallocFreeMemory() { } 392 393FastMallocStatistics fastMallocStatistics() 394{ 395 FastMallocStatistics statistics = { 0, 0, 0 }; 396 return statistics; 397} 398 399size_t fastMallocSize(const void* p) 400{ 401#if ENABLE(WTF_MALLOC_VALIDATION) 402 return Internal::fastMallocValidationHeader(const_cast<void*>(p))->m_size; 403#elif OS(DARWIN) 404 return malloc_size(p); 405#elif OS(WINDOWS) 406 return _msize(const_cast<void*>(p)); 407#else 408 UNUSED_PARAM(p); 409 return 1; 410#endif 411} 412 413} // namespace WTF 414 415#if OS(DARWIN) 416// This symbol is present in the JavaScriptCore exports file even when FastMalloc is disabled. 417// It will never be used in this case, so it's type and value are less interesting than its presence. 418extern "C" WTF_EXPORT_PRIVATE const int jscore_fastmalloc_introspection = 0; 419#endif 420 421#elif defined(USE_BMALLOC) && USE_BMALLOC // FORCE_SYSTEM_MALLOC 422 423#include <bmalloc/bmalloc.h> 424 425namespace WTF { 426 427void* fastMalloc(size_t size) 428{ 429 ASSERT(!isForbidden()); 430 return bmalloc::api::malloc(size); 431} 432 433void* fastCalloc(size_t numElements, size_t elementSize) 434{ 435 return fastZeroedMalloc(numElements * elementSize); 436} 437 438void* fastRealloc(void* object, size_t size) 439{ 440 return bmalloc::api::realloc(object, size); 441} 442 443void fastFree(void* object) 444{ 445 bmalloc::api::free(object); 446} 447 448size_t fastMallocSize(const void*) 449{ 450 return 1; 451} 452 453size_t fastMallocGoodSize(size_t size) 454{ 455 return size; 456} 457 458TryMallocReturnValue tryFastMalloc(size_t size) 459{ 460 return fastMalloc(size); 461} 462 463TryMallocReturnValue tryFastRealloc(void* p, size_t n) 464{ 465 return fastRealloc(p, n); 466} 467 468TryMallocReturnValue tryFastCalloc(size_t numElements, size_t elementSize) 469{ 470 return fastCalloc(numElements, elementSize); 471} 472 473void releaseFastMallocFreeMemory() { } 474 475FastMallocStatistics fastMallocStatistics() 476{ 477 FastMallocStatistics statistics = { 0, 0, 0 }; 478 return statistics; 479} 480 481} // namespace WTF 482 483#else // FORCE_SYSTEM_MALLOC 484 485#include "TCPackedCache.h" 486#include "TCPageMap.h" 487#include "TCSpinLock.h" 488#include "TCSystemAlloc.h" 489#include "ThreadSpecific.h" 490#include <algorithm> 491#if USE(PTHREADS) 492#include <pthread.h> 493#endif 494#include <stdarg.h> 495#include <stddef.h> 496#include <stdint.h> 497#include <stdio.h> 498#if HAVE(ERRNO_H) 499#include <errno.h> 500#endif 501#if OS(UNIX) 502#include <unistd.h> 503#endif 504#if OS(WINDOWS) 505#ifndef WIN32_LEAN_AND_MEAN 506#define WIN32_LEAN_AND_MEAN 507#endif 508#include <windows.h> 509#endif 510 511#ifdef WTF_CHANGES 512 513#if OS(DARWIN) 514#include <wtf/HashSet.h> 515#include <wtf/Vector.h> 516#endif 517 518#if HAVE(DISPATCH_H) 519#include <dispatch/dispatch.h> 520#endif 521 522#if OS(DARWIN) 523#if defined(__has_include) && __has_include(<System/pthread_machdep.h>) 524#include <System/pthread_machdep.h> 525#endif 526#endif 527 528#if defined(__PTK_FRAMEWORK_JAVASCRIPTCORE_KEY0) 529#define WTF_USE_PTHREAD_GETSPECIFIC_DIRECT 1 530#endif 531 532#ifndef PRIuS 533#define PRIuS "zu" 534#endif 535 536// Calling pthread_getspecific through a global function pointer is faster than a normal 537// call to the function on Mac OS X, and it's used in performance-critical code. So we 538// use a function pointer. But that's not necessarily faster on other platforms, and we had 539// problems with this technique on Windows, so we'll do this only on Mac OS X. 540#if OS(DARWIN) 541#if !USE(PTHREAD_GETSPECIFIC_DIRECT) 542static void* (*pthread_getspecific_function_pointer)(pthread_key_t) = pthread_getspecific; 543#define pthread_getspecific(key) pthread_getspecific_function_pointer(key) 544#else 545#define pthread_getspecific(key) _pthread_getspecific_direct(key) 546#define pthread_setspecific(key, val) _pthread_setspecific_direct(key, (val)) 547#endif 548#endif 549 550#define DEFINE_VARIABLE(type, name, value, meaning) \ 551 namespace FLAG__namespace_do_not_use_directly_use_DECLARE_##type##_instead { \ 552 type FLAGS_##name(value); \ 553 char FLAGS_no##name; \ 554 } \ 555 using FLAG__namespace_do_not_use_directly_use_DECLARE_##type##_instead::FLAGS_##name 556 557#define DEFINE_int64(name, value, meaning) \ 558 DEFINE_VARIABLE(int64_t, name, value, meaning) 559 560#define DEFINE_double(name, value, meaning) \ 561 DEFINE_VARIABLE(double, name, value, meaning) 562 563namespace WTF { 564 565#define malloc fastMalloc 566#define calloc fastCalloc 567#define free fastFree 568#define realloc fastRealloc 569 570#define MESSAGE LOG_ERROR 571#define CHECK_CONDITION ASSERT 572 573#if !OS(DARWIN) 574static const char kLLHardeningMask = 0; 575#endif 576 577template <unsigned> struct EntropySource; 578template <> struct EntropySource<4> { 579 static uint32_t value() 580 { 581#if OS(DARWIN) 582 return arc4random(); 583#else 584 return static_cast<uint32_t>(static_cast<uintptr_t>(currentTime() * 10000) ^ reinterpret_cast<uintptr_t>(&kLLHardeningMask)); 585#endif 586 } 587}; 588 589template <> struct EntropySource<8> { 590 static uint64_t value() 591 { 592 return EntropySource<4>::value() | (static_cast<uint64_t>(EntropySource<4>::value()) << 32); 593 } 594}; 595 596#if ENABLE(TCMALLOC_HARDENING) 597/* 598 * To make it harder to exploit use-after free style exploits 599 * we mask the addresses we put into our linked lists with the 600 * address of kLLHardeningMask. Due to ASLR the address of 601 * kLLHardeningMask should be sufficiently randomized to make direct 602 * freelist manipulation much more difficult. 603 */ 604enum { 605 MaskKeyShift = 13 606}; 607 608static ALWAYS_INLINE uintptr_t internalEntropyValue() 609{ 610 static uintptr_t value = EntropySource<sizeof(uintptr_t)>::value() | 1; 611 ASSERT(value); 612 return value; 613} 614 615#define HARDENING_ENTROPY internalEntropyValue() 616#define ROTATE_VALUE(value, amount) (((value) >> (amount)) | ((value) << (sizeof(value) * 8 - (amount)))) 617#if COMPILER(MSVC) 618#define XOR_MASK_PTR_WITH_KEY(ptr, key, entropy) (reinterpret_cast<decltype(ptr)>(reinterpret_cast<uintptr_t>(ptr)^(ROTATE_VALUE(reinterpret_cast<uintptr_t>(key), MaskKeyShift)^entropy))) 619#else 620#define XOR_MASK_PTR_WITH_KEY(ptr, key, entropy) (reinterpret_cast<__typeof__(ptr)>(reinterpret_cast<uintptr_t>(ptr)^(ROTATE_VALUE(reinterpret_cast<uintptr_t>(key), MaskKeyShift)^entropy))) 621#endif 622 623static ALWAYS_INLINE uint32_t freedObjectStartPoison() 624{ 625 static uint32_t value = EntropySource<sizeof(uint32_t)>::value() | 1; 626 ASSERT(value); 627 return value; 628} 629 630static ALWAYS_INLINE uint32_t freedObjectEndPoison() 631{ 632 static uint32_t value = EntropySource<sizeof(uint32_t)>::value() | 1; 633 ASSERT(value); 634 return value; 635} 636 637#define PTR_TO_UINT32(ptr) static_cast<uint32_t>(reinterpret_cast<uintptr_t>(ptr)) 638#define END_POISON_INDEX(allocationSize) (((allocationSize) - sizeof(uint32_t)) / sizeof(uint32_t)) 639#define POISON_ALLOCATION(allocation, allocationSize) do { \ 640 ASSERT((allocationSize) >= 2 * sizeof(uint32_t)); \ 641 reinterpret_cast<uint32_t*>(allocation)[0] = 0xbadbeef1; \ 642 reinterpret_cast<uint32_t*>(allocation)[1] = 0xbadbeef3; \ 643 if ((allocationSize) < 4 * sizeof(uint32_t)) \ 644 break; \ 645 reinterpret_cast<uint32_t*>(allocation)[2] = 0xbadbeef5; \ 646 reinterpret_cast<uint32_t*>(allocation)[END_POISON_INDEX(allocationSize)] = 0xbadbeef7; \ 647} while (false); 648 649#define POISON_DEALLOCATION_EXPLICIT(allocation, allocationSize, startPoison, endPoison) do { \ 650 ASSERT((allocationSize) >= 2 * sizeof(uint32_t)); \ 651 reinterpret_cast_ptr<uint32_t*>(allocation)[0] = 0xbadbeef9; \ 652 reinterpret_cast_ptr<uint32_t*>(allocation)[1] = 0xbadbeefb; \ 653 if ((allocationSize) < 4 * sizeof(uint32_t)) \ 654 break; \ 655 reinterpret_cast_ptr<uint32_t*>(allocation)[2] = (startPoison) ^ PTR_TO_UINT32(allocation); \ 656 reinterpret_cast_ptr<uint32_t*>(allocation)[END_POISON_INDEX(allocationSize)] = (endPoison) ^ PTR_TO_UINT32(allocation); \ 657} while (false) 658 659#define POISON_DEALLOCATION(allocation, allocationSize) \ 660 POISON_DEALLOCATION_EXPLICIT(allocation, (allocationSize), freedObjectStartPoison(), freedObjectEndPoison()) 661 662#define MAY_BE_POISONED(allocation, allocationSize) (((allocationSize) >= 4 * sizeof(uint32_t)) && ( \ 663 (reinterpret_cast<uint32_t*>(allocation)[2] == (freedObjectStartPoison() ^ PTR_TO_UINT32(allocation))) || \ 664 (reinterpret_cast<uint32_t*>(allocation)[END_POISON_INDEX(allocationSize)] == (freedObjectEndPoison() ^ PTR_TO_UINT32(allocation))) \ 665)) 666 667#define IS_DEFINITELY_POISONED(allocation, allocationSize) (((allocationSize) < 4 * sizeof(uint32_t)) || ( \ 668 (reinterpret_cast<uint32_t*>(allocation)[2] == (freedObjectStartPoison() ^ PTR_TO_UINT32(allocation))) && \ 669 (reinterpret_cast<uint32_t*>(allocation)[END_POISON_INDEX(allocationSize)] == (freedObjectEndPoison() ^ PTR_TO_UINT32(allocation))) \ 670)) 671 672#else 673 674#define POISON_ALLOCATION(allocation, allocationSize) 675#define POISON_DEALLOCATION(allocation, allocationSize) 676#define POISON_DEALLOCATION_EXPLICIT(allocation, allocationSize, startPoison, endPoison) 677#define MAY_BE_POISONED(allocation, allocationSize) (false) 678#define IS_DEFINITELY_POISONED(allocation, allocationSize) (true) 679#define XOR_MASK_PTR_WITH_KEY(ptr, key, entropy) (((void)entropy), ((void)key), ptr) 680 681#define HARDENING_ENTROPY 0 682 683#endif 684 685//------------------------------------------------------------------- 686// Configuration 687//------------------------------------------------------------------- 688 689// Type that can hold the length of a run of pages 690typedef uintptr_t Length; 691 692// Not all possible combinations of the following parameters make 693// sense. In particular, if kMaxSize increases, you may have to 694// increase kNumClasses as well. 695#define K_PAGE_SHIFT_MIN 12 696#define K_PAGE_SHIFT_MAX 14 697#define K_NUM_CLASSES_MAX 77 698static size_t kPageShift = 0; 699static size_t kNumClasses = 0; 700static size_t kPageSize = 0; 701static Length kMaxValidPages = 0; 702static const size_t kMaxSize = 32u * 1024; 703static const size_t kAlignShift = 3; 704static const size_t kAlignment = 1 << kAlignShift; 705 706// Allocates a big block of memory for the pagemap once we reach more than 707// 128MB 708static const size_t kPageMapBigAllocationThreshold = 128 << 20; 709 710// Minimum number of pages to fetch from system at a time. Must be 711// significantly bigger than kPageSize to amortize system-call 712// overhead, and also to reduce external fragementation. Also, we 713// should keep this value big because various incarnations of Linux 714// have small limits on the number of mmap() regions per 715// address-space. 716static const size_t kMinSystemAlloc = 1 << (20 - K_PAGE_SHIFT_MAX); 717 718// Number of objects to move between a per-thread list and a central 719// list in one shot. We want this to be not too small so we can 720// amortize the lock overhead for accessing the central list. Making 721// it too big may temporarily cause unnecessary memory wastage in the 722// per-thread free list until the scavenger cleans up the list. 723static int num_objects_to_move[K_NUM_CLASSES_MAX]; 724 725// Maximum length we allow a per-thread free-list to have before we 726// move objects from it into the corresponding central free-list. We 727// want this big to avoid locking the central free-list too often. It 728// should not hurt to make this list somewhat big because the 729// scavenging code will shrink it down when its contents are not in use. 730static const int kMaxFreeListLength = 256; 731 732// Lower and upper bounds on the per-thread cache sizes 733static const size_t kMinThreadCacheSize = kMaxSize * 2; 734static const size_t kMaxThreadCacheSize = 2 << 20; 735 736// Default bound on the total amount of thread caches 737static const size_t kDefaultOverallThreadCacheSize = 16 << 20; 738 739// For all span-lengths < kMaxPages we keep an exact-size list. 740// REQUIRED: kMaxPages >= kMinSystemAlloc; 741static const size_t kMaxPages = kMinSystemAlloc; 742 743/* The smallest prime > 2^n */ 744static int primes_list[] = { 745 // Small values might cause high rates of sampling 746 // and hence commented out. 747 // 2, 5, 11, 17, 37, 67, 131, 257, 748 // 521, 1031, 2053, 4099, 8209, 16411, 749 32771, 65537, 131101, 262147, 524309, 1048583, 750 2097169, 4194319, 8388617, 16777259, 33554467 }; 751 752// Twice the approximate gap between sampling actions. 753// I.e., we take one sample approximately once every 754// tcmalloc_sample_parameter/2 755// bytes of allocation, i.e., ~ once every 128KB. 756// Must be a prime number. 757#ifdef NO_TCMALLOC_SAMPLES 758DEFINE_int64(tcmalloc_sample_parameter, 0, 759 "Unused: code is compiled with NO_TCMALLOC_SAMPLES"); 760static size_t sample_period = 0; 761#else 762DEFINE_int64(tcmalloc_sample_parameter, 262147, 763 "Twice the approximate gap between sampling actions." 764 " Must be a prime number. Otherwise will be rounded up to a " 765 " larger prime number"); 766static size_t sample_period = 262147; 767#endif 768 769// Protects sample_period above 770static SpinLock sample_period_lock = SPINLOCK_INITIALIZER; 771 772// Parameters for controlling how fast memory is returned to the OS. 773 774DEFINE_double(tcmalloc_release_rate, 1, 775 "Rate at which we release unused memory to the system. " 776 "Zero means we never release memory back to the system. " 777 "Increase this flag to return memory faster; decrease it " 778 "to return memory slower. Reasonable rates are in the " 779 "range [0,10]"); 780 781//------------------------------------------------------------------- 782// Mapping from size to size_class and vice versa 783//------------------------------------------------------------------- 784 785// Sizes <= 1024 have an alignment >= 8. So for such sizes we have an 786// array indexed by ceil(size/8). Sizes > 1024 have an alignment >= 128. 787// So for these larger sizes we have an array indexed by ceil(size/128). 788// 789// We flatten both logical arrays into one physical array and use 790// arithmetic to compute an appropriate index. The constants used by 791// ClassIndex() were selected to make the flattening work. 792// 793// Examples: 794// Size Expression Index 795// ------------------------------------------------------- 796// 0 (0 + 7) / 8 0 797// 1 (1 + 7) / 8 1 798// ... 799// 1024 (1024 + 7) / 8 128 800// 1025 (1025 + 127 + (120<<7)) / 128 129 801// ... 802// 32768 (32768 + 127 + (120<<7)) / 128 376 803static const size_t kMaxSmallSize = 1024; 804static const int shift_amount[2] = { 3, 7 }; // For divides by 8 or 128 805static const int add_amount[2] = { 7, 127 + (120 << 7) }; 806static unsigned char class_array[377]; 807 808// Compute index of the class_array[] entry for a given size 809static inline int ClassIndex(size_t s) { 810 const int i = (s > kMaxSmallSize); 811 return static_cast<int>((s + add_amount[i]) >> shift_amount[i]); 812} 813 814// Mapping from size class to max size storable in that class 815static size_t class_to_size[K_NUM_CLASSES_MAX]; 816 817// Mapping from size class to number of pages to allocate at a time 818static size_t class_to_pages[K_NUM_CLASSES_MAX]; 819 820// Hardened singly linked list. We make this a class to allow compiler to 821// statically prevent mismatching hardened and non-hardened list 822class HardenedSLL { 823public: 824 static ALWAYS_INLINE HardenedSLL create(void* value) 825 { 826 HardenedSLL result; 827 result.m_value = value; 828 return result; 829 } 830 831 static ALWAYS_INLINE HardenedSLL null() 832 { 833 HardenedSLL result; 834 result.m_value = 0; 835 return result; 836 } 837 838 ALWAYS_INLINE void setValue(void* value) { m_value = value; } 839 ALWAYS_INLINE void* value() const { return m_value; } 840 ALWAYS_INLINE bool operator!() const { return !m_value; } 841 typedef void* (HardenedSLL::*UnspecifiedBoolType); 842 ALWAYS_INLINE operator UnspecifiedBoolType() const { return m_value ? &HardenedSLL::m_value : 0; } 843 844 bool operator!=(const HardenedSLL& other) const { return m_value != other.m_value; } 845 bool operator==(const HardenedSLL& other) const { return m_value == other.m_value; } 846 847private: 848 void* m_value; 849}; 850 851// TransferCache is used to cache transfers of num_objects_to_move[size_class] 852// back and forth between thread caches and the central cache for a given size 853// class. 854struct TCEntry { 855 HardenedSLL head; // Head of chain of objects. 856 HardenedSLL tail; // Tail of chain of objects. 857}; 858// A central cache freelist can have anywhere from 0 to kNumTransferEntries 859// slots to put link list chains into. To keep memory usage bounded the total 860// number of TCEntries across size classes is fixed. Currently each size 861// class is initially given one TCEntry which also means that the maximum any 862// one class can have is kNumClasses. 863#define K_NUM_TRANSFER_ENTRIES_MAX static_cast<int>(K_NUM_CLASSES_MAX) 864#define kNumTransferEntries static_cast<int>(kNumClasses) 865 866// Note: the following only works for "n"s that fit in 32-bits, but 867// that is fine since we only use it for small sizes. 868static inline int LgFloor(size_t n) { 869 int log = 0; 870 for (int i = 4; i >= 0; --i) { 871 int shift = (1 << i); 872 size_t x = n >> shift; 873 if (x != 0) { 874 n = x; 875 log += shift; 876 } 877 } 878 ASSERT(n == 1); 879 return log; 880} 881 882// Functions for using our simple hardened singly linked list 883static ALWAYS_INLINE HardenedSLL SLL_Next(HardenedSLL t, uintptr_t entropy) { 884 void* tValueNext = *(reinterpret_cast<void**>(t.value())); 885 return HardenedSLL::create(XOR_MASK_PTR_WITH_KEY(tValueNext, t.value(), entropy)); 886} 887 888static ALWAYS_INLINE void SLL_SetNext(HardenedSLL t, HardenedSLL n, uintptr_t entropy) { 889 *(reinterpret_cast<void**>(t.value())) = XOR_MASK_PTR_WITH_KEY(n.value(), t.value(), entropy); 890} 891 892static ALWAYS_INLINE void SLL_Push(HardenedSLL* list, HardenedSLL element, uintptr_t entropy) { 893 SLL_SetNext(element, *list, entropy); 894 *list = element; 895} 896 897static ALWAYS_INLINE HardenedSLL SLL_Pop(HardenedSLL *list, uintptr_t entropy) { 898 HardenedSLL result = *list; 899 *list = SLL_Next(*list, entropy); 900 return result; 901} 902 903// Remove N elements from a linked list to which head points. head will be 904// modified to point to the new head. start and end will point to the first 905// and last nodes of the range. Note that end will point to NULL after this 906// function is called. 907 908static ALWAYS_INLINE void SLL_PopRange(HardenedSLL* head, int N, HardenedSLL *start, HardenedSLL *end, uintptr_t entropy) { 909 if (N == 0) { 910 *start = HardenedSLL::null(); 911 *end = HardenedSLL::null(); 912 return; 913 } 914 915 HardenedSLL tmp = *head; 916 for (int i = 1; i < N; ++i) { 917 tmp = SLL_Next(tmp, entropy); 918 } 919 920 *start = *head; 921 *end = tmp; 922 *head = SLL_Next(tmp, entropy); 923 // Unlink range from list. 924 SLL_SetNext(tmp, HardenedSLL::null(), entropy); 925} 926 927static ALWAYS_INLINE void SLL_PushRange(HardenedSLL *head, HardenedSLL start, HardenedSLL end, uintptr_t entropy) { 928 if (!start) return; 929 SLL_SetNext(end, *head, entropy); 930 *head = start; 931} 932 933// Setup helper functions. 934 935static ALWAYS_INLINE size_t SizeClass(size_t size) { 936 return class_array[ClassIndex(size)]; 937} 938 939// Get the byte-size for a specified class 940static ALWAYS_INLINE size_t ByteSizeForClass(size_t cl) { 941 return class_to_size[cl]; 942} 943static int NumMoveSize(size_t size) { 944 if (size == 0) return 0; 945 // Use approx 64k transfers between thread and central caches. 946 int num = static_cast<int>(64.0 * 1024.0 / size); 947 if (num < 2) num = 2; 948 // Clamp well below kMaxFreeListLength to avoid ping pong between central 949 // and thread caches. 950 if (num > static_cast<int>(0.8 * kMaxFreeListLength)) 951 num = static_cast<int>(0.8 * kMaxFreeListLength); 952 953 // Also, avoid bringing in too many objects into small object free 954 // lists. There are lots of such lists, and if we allow each one to 955 // fetch too many at a time, we end up having to scavenge too often 956 // (especially when there are lots of threads and each thread gets a 957 // small allowance for its thread cache). 958 // 959 // TODO: Make thread cache free list sizes dynamic so that we do not 960 // have to equally divide a fixed resource amongst lots of threads. 961 if (num > 32) num = 32; 962 963 return num; 964} 965 966// Initialize the mapping arrays 967static void InitSizeClasses() { 968#if OS(DARWIN) 969 kPageShift = vm_page_shift; 970 switch (kPageShift) { 971 case 12: 972 kNumClasses = 68; 973 break; 974 case 14: 975 kNumClasses = 77; 976 break; 977 default: 978 CRASH(); 979 }; 980#else 981 kPageShift = 12; 982 kNumClasses = 68; 983#endif 984 kPageSize = 1 << kPageShift; 985 kMaxValidPages = (~static_cast<Length>(0)) >> kPageShift; 986 987 // Do some sanity checking on add_amount[]/shift_amount[]/class_array[] 988 if (ClassIndex(0) < 0) { 989 MESSAGE("Invalid class index %d for size 0\n", ClassIndex(0)); 990 CRASH(); 991 } 992 if (static_cast<size_t>(ClassIndex(kMaxSize)) >= sizeof(class_array)) { 993 MESSAGE("Invalid class index %d for kMaxSize\n", ClassIndex(kMaxSize)); 994 CRASH(); 995 } 996 997 // Compute the size classes we want to use 998 size_t sc = 1; // Next size class to assign 999 unsigned char alignshift = kAlignShift; 1000 int last_lg = -1; 1001 for (size_t size = kAlignment; size <= kMaxSize; size += (1 << alignshift)) { 1002 int lg = LgFloor(size); 1003 if (lg > last_lg) { 1004 // Increase alignment every so often. 1005 // 1006 // Since we double the alignment every time size doubles and 1007 // size >= 128, this means that space wasted due to alignment is 1008 // at most 16/128 i.e., 12.5%. Plus we cap the alignment at 256 1009 // bytes, so the space wasted as a percentage starts falling for 1010 // sizes > 2K. 1011 if ((lg >= 7) && (alignshift < 8)) { 1012 alignshift++; 1013 } 1014 last_lg = lg; 1015 } 1016 1017 // Allocate enough pages so leftover is less than 1/8 of total. 1018 // This bounds wasted space to at most 12.5%. 1019 size_t psize = kPageSize; 1020 while ((psize % size) > (psize >> 3)) { 1021 psize += kPageSize; 1022 } 1023 const size_t my_pages = psize >> kPageShift; 1024 1025 if (sc > 1 && my_pages == class_to_pages[sc-1]) { 1026 // See if we can merge this into the previous class without 1027 // increasing the fragmentation of the previous class. 1028 const size_t my_objects = (my_pages << kPageShift) / size; 1029 const size_t prev_objects = (class_to_pages[sc-1] << kPageShift) 1030 / class_to_size[sc-1]; 1031 if (my_objects == prev_objects) { 1032 // Adjust last class to include this size 1033 class_to_size[sc-1] = size; 1034 continue; 1035 } 1036 } 1037 1038 // Add new class 1039 class_to_pages[sc] = my_pages; 1040 class_to_size[sc] = size; 1041 sc++; 1042 } 1043 if (sc != kNumClasses) { 1044 MESSAGE("wrong number of size classes: found %" PRIuS " instead of %d\n", 1045 sc, int(kNumClasses)); 1046 CRASH(); 1047 } 1048 1049 // Initialize the mapping arrays 1050 int next_size = 0; 1051 for (unsigned char c = 1; c < kNumClasses; c++) { 1052 const size_t max_size_in_class = class_to_size[c]; 1053 for (size_t s = next_size; s <= max_size_in_class; s += kAlignment) { 1054 class_array[ClassIndex(s)] = c; 1055 } 1056 next_size = static_cast<int>(max_size_in_class + kAlignment); 1057 } 1058 1059 // Double-check sizes just to be safe 1060 for (size_t size = 0; size <= kMaxSize; size++) { 1061 const size_t sc = SizeClass(size); 1062 if (sc == 0) { 1063 MESSAGE("Bad size class %" PRIuS " for %" PRIuS "\n", sc, size); 1064 CRASH(); 1065 } 1066 if (sc > 1 && size <= class_to_size[sc-1]) { 1067 MESSAGE("Allocating unnecessarily large class %" PRIuS " for %" PRIuS 1068 "\n", sc, size); 1069 CRASH(); 1070 } 1071 if (sc >= kNumClasses) { 1072 MESSAGE("Bad size class %" PRIuS " for %" PRIuS "\n", sc, size); 1073 CRASH(); 1074 } 1075 const size_t s = class_to_size[sc]; 1076 if (size > s) { 1077 MESSAGE("Bad size %" PRIuS " for %" PRIuS " (sc = %" PRIuS ")\n", s, size, sc); 1078 CRASH(); 1079 } 1080 if (s == 0) { 1081 MESSAGE("Bad size %" PRIuS " for %" PRIuS " (sc = %" PRIuS ")\n", s, size, sc); 1082 CRASH(); 1083 } 1084 } 1085 1086 // Initialize the num_objects_to_move array. 1087 for (size_t cl = 1; cl < kNumClasses; ++cl) { 1088 num_objects_to_move[cl] = NumMoveSize(ByteSizeForClass(cl)); 1089 } 1090 1091#ifndef WTF_CHANGES 1092 if (false) { 1093 // Dump class sizes and maximum external wastage per size class 1094 for (size_t cl = 1; cl < kNumClasses; ++cl) { 1095 const int alloc_size = class_to_pages[cl] << kPageShift; 1096 const int alloc_objs = alloc_size / class_to_size[cl]; 1097 const int min_used = (class_to_size[cl-1] + 1) * alloc_objs; 1098 const int max_waste = alloc_size - min_used; 1099 MESSAGE("SC %3d [ %8d .. %8d ] from %8d ; %2.0f%% maxwaste\n", 1100 int(cl), 1101 int(class_to_size[cl-1] + 1), 1102 int(class_to_size[cl]), 1103 int(class_to_pages[cl] << kPageShift), 1104 max_waste * 100.0 / alloc_size 1105 ); 1106 } 1107 } 1108#endif 1109} 1110 1111// ------------------------------------------------------------------------- 1112// Simple allocator for objects of a specified type. External locking 1113// is required before accessing one of these objects. 1114// ------------------------------------------------------------------------- 1115 1116// Metadata allocator -- keeps stats about how many bytes allocated 1117static uint64_t metadata_system_bytes = 0; 1118static void* MetaDataAlloc(size_t bytes) { 1119 void* result = TCMalloc_SystemAlloc(bytes, 0); 1120 if (result != NULL) { 1121 metadata_system_bytes += bytes; 1122 } 1123 return result; 1124} 1125 1126#if defined(WTF_CHANGES) && OS(DARWIN) 1127class RemoteMemoryReader; 1128#endif 1129 1130template <class T> 1131class PageHeapAllocator { 1132 private: 1133 // How much to allocate from system at a time 1134 static const size_t kAllocIncrement = 32 << 10; 1135 1136 // Aligned size of T 1137 static const size_t kAlignedSize 1138 = (((sizeof(T) + kAlignment - 1) / kAlignment) * kAlignment); 1139 1140 // Free area from which to carve new objects 1141 char* free_area_; 1142 size_t free_avail_; 1143 1144 // Linked list of all regions allocated by this allocator 1145 HardenedSLL allocated_regions_; 1146 1147 // Free list of already carved objects 1148 HardenedSLL free_list_; 1149 1150 // Number of allocated but unfreed objects 1151 int inuse_; 1152 uintptr_t entropy_; 1153 1154 public: 1155 void Init(uintptr_t entropy) { 1156 ASSERT(kAlignedSize <= kAllocIncrement); 1157 inuse_ = 0; 1158 allocated_regions_ = HardenedSLL::null(); 1159 free_area_ = NULL; 1160 free_avail_ = 0; 1161 free_list_.setValue(NULL); 1162 entropy_ = entropy; 1163 } 1164 1165 T* New() { 1166 // Consult free list 1167 void* result; 1168 if (free_list_) { 1169 result = free_list_.value(); 1170 free_list_ = SLL_Next(free_list_, entropy_); 1171 } else { 1172 if (free_avail_ < kAlignedSize) { 1173 // Need more room 1174 char* new_allocation = reinterpret_cast<char*>(MetaDataAlloc(kAllocIncrement)); 1175 if (!new_allocation) 1176 CRASH(); 1177 1178 HardenedSLL new_head = HardenedSLL::create(new_allocation); 1179 SLL_SetNext(new_head, allocated_regions_, entropy_); 1180 allocated_regions_ = new_head; 1181 free_area_ = new_allocation + kAlignedSize; 1182 free_avail_ = kAllocIncrement - kAlignedSize; 1183 } 1184 result = free_area_; 1185 free_area_ += kAlignedSize; 1186 free_avail_ -= kAlignedSize; 1187 } 1188 inuse_++; 1189 return reinterpret_cast<T*>(result); 1190 } 1191 1192 void Delete(T* p) { 1193 HardenedSLL new_head = HardenedSLL::create(p); 1194 SLL_SetNext(new_head, free_list_, entropy_); 1195 free_list_ = new_head; 1196 inuse_--; 1197 } 1198 1199 int inuse() const { return inuse_; } 1200 1201#if defined(WTF_CHANGES) && OS(DARWIN) 1202 template <typename Recorder> 1203 void recordAdministrativeRegions(Recorder&, const RemoteMemoryReader&); 1204#endif 1205}; 1206 1207// ------------------------------------------------------------------------- 1208// Span - a contiguous run of pages 1209// ------------------------------------------------------------------------- 1210 1211// Type that can hold a page number 1212typedef uintptr_t PageID; 1213 1214// Convert byte size into pages. This won't overflow, but may return 1215// an unreasonably large value if bytes is huge enough. 1216static inline Length pages(size_t bytes) { 1217 ASSERT(kPageShift && kNumClasses && kPageSize); 1218 return (bytes >> kPageShift) + 1219 ((bytes & (kPageSize - 1)) > 0 ? 1 : 0); 1220} 1221 1222// Convert a user size into the number of bytes that will actually be 1223// allocated 1224static size_t AllocationSize(size_t bytes) { 1225 ASSERT(kPageShift && kNumClasses && kPageSize); 1226 if (bytes > kMaxSize) { 1227 // Large object: we allocate an integral number of pages 1228 ASSERT(bytes <= (kMaxValidPages << kPageShift)); 1229 return pages(bytes) << kPageShift; 1230 } else { 1231 // Small object: find the size class to which it belongs 1232 return ByteSizeForClass(SizeClass(bytes)); 1233 } 1234} 1235 1236enum { 1237 kSpanCookieBits = 10, 1238 kSpanCookieMask = (1 << 10) - 1, 1239 kSpanThisShift = 7 1240}; 1241 1242static uint32_t spanValidationCookie; 1243static uint32_t spanInitializerCookie() 1244{ 1245 static uint32_t value = EntropySource<sizeof(uint32_t)>::value() & kSpanCookieMask; 1246 spanValidationCookie = value; 1247 return value; 1248} 1249 1250// Information kept for a span (a contiguous run of pages). 1251struct Span { 1252 PageID start; // Starting page number 1253 Length length; // Number of pages in span 1254 Span* next(uintptr_t entropy) const { return XOR_MASK_PTR_WITH_KEY(m_next, this, entropy); } 1255 Span* remoteNext(const Span* remoteSpanPointer, uintptr_t entropy) const { return XOR_MASK_PTR_WITH_KEY(m_next, remoteSpanPointer, entropy); } 1256 Span* prev(uintptr_t entropy) const { return XOR_MASK_PTR_WITH_KEY(m_prev, this, entropy); } 1257 void setNext(Span* next, uintptr_t entropy) { m_next = XOR_MASK_PTR_WITH_KEY(next, this, entropy); } 1258 void setPrev(Span* prev, uintptr_t entropy) { m_prev = XOR_MASK_PTR_WITH_KEY(prev, this, entropy); } 1259 1260private: 1261 Span* m_next; // Used when in link list 1262 Span* m_prev; // Used when in link list 1263public: 1264 HardenedSLL objects; // Linked list of free objects 1265 unsigned int free : 1; // Is the span free 1266#ifndef NO_TCMALLOC_SAMPLES 1267 unsigned int sample : 1; // Sampled object? 1268#endif 1269 unsigned int sizeclass : 8; // Size-class for small objects (or 0) 1270 unsigned int refcount : 11; // Number of non-free objects 1271 bool decommitted : 1; 1272 void initCookie() 1273 { 1274 m_cookie = ((reinterpret_cast<uintptr_t>(this) >> kSpanThisShift) & kSpanCookieMask) ^ spanInitializerCookie(); 1275 } 1276 void clearCookie() { m_cookie = 0; } 1277 bool isValid() const 1278 { 1279 return (((reinterpret_cast<uintptr_t>(this) >> kSpanThisShift) & kSpanCookieMask) ^ m_cookie) == spanValidationCookie; 1280 } 1281private: 1282 uint32_t m_cookie : kSpanCookieBits; 1283 1284#undef SPAN_HISTORY 1285#ifdef SPAN_HISTORY 1286 // For debugging, we can keep a log events per span 1287 int nexthistory; 1288 char history[64]; 1289 int value[64]; 1290#endif 1291}; 1292 1293#define ASSERT_SPAN_COMMITTED(span) ASSERT(!span->decommitted) 1294 1295#ifdef SPAN_HISTORY 1296void Event(Span* span, char op, int v = 0) { 1297 span->history[span->nexthistory] = op; 1298 span->value[span->nexthistory] = v; 1299 span->nexthistory++; 1300 if (span->nexthistory == sizeof(span->history)) span->nexthistory = 0; 1301} 1302#else 1303#define Event(s,o,v) ((void) 0) 1304#endif 1305 1306// Allocator/deallocator for spans 1307static PageHeapAllocator<Span> span_allocator; 1308static Span* NewSpan(PageID p, Length len) { 1309 Span* result = span_allocator.New(); 1310 memset(result, 0, sizeof(*result)); 1311 result->start = p; 1312 result->length = len; 1313 result->initCookie(); 1314#ifdef SPAN_HISTORY 1315 result->nexthistory = 0; 1316#endif 1317 return result; 1318} 1319 1320static inline void DeleteSpan(Span* span) { 1321 RELEASE_ASSERT(span->isValid()); 1322#ifndef NDEBUG 1323 // In debug mode, trash the contents of deleted Spans 1324 memset(span, 0x3f, sizeof(*span)); 1325#endif 1326 span->clearCookie(); 1327 span_allocator.Delete(span); 1328} 1329 1330// ------------------------------------------------------------------------- 1331// Doubly linked list of spans. 1332// ------------------------------------------------------------------------- 1333 1334static inline void DLL_Init(Span* list, uintptr_t entropy) { 1335 list->setNext(list, entropy); 1336 list->setPrev(list, entropy); 1337} 1338 1339static inline void DLL_Remove(Span* span, uintptr_t entropy) { 1340 span->prev(entropy)->setNext(span->next(entropy), entropy); 1341 span->next(entropy)->setPrev(span->prev(entropy), entropy); 1342 span->setPrev(NULL, entropy); 1343 span->setNext(NULL, entropy); 1344} 1345 1346static ALWAYS_INLINE bool DLL_IsEmpty(const Span* list, uintptr_t entropy) { 1347 return list->next(entropy) == list; 1348} 1349 1350static int DLL_Length(const Span* list, uintptr_t entropy) { 1351 int result = 0; 1352 for (Span* s = list->next(entropy); s != list; s = s->next(entropy)) { 1353 result++; 1354 } 1355 return result; 1356} 1357 1358#if 0 /* Not needed at the moment -- causes compiler warnings if not used */ 1359static void DLL_Print(const char* label, const Span* list) { 1360 MESSAGE("%-10s %p:", label, list); 1361 for (const Span* s = list->next; s != list; s = s->next) { 1362 MESSAGE(" <%p,%u,%u>", s, s->start, s->length); 1363 } 1364 MESSAGE("\n"); 1365} 1366#endif 1367 1368static inline void DLL_Prepend(Span* list, Span* span, uintptr_t entropy) { 1369 span->setNext(list->next(entropy), entropy); 1370 span->setPrev(list, entropy); 1371 list->next(entropy)->setPrev(span, entropy); 1372 list->setNext(span, entropy); 1373} 1374 1375//------------------------------------------------------------------- 1376// Data kept per size-class in central cache 1377//------------------------------------------------------------------- 1378 1379class TCMalloc_Central_FreeList { 1380 public: 1381 void Init(size_t cl, uintptr_t entropy); 1382 1383 // These methods all do internal locking. 1384 1385 // Insert the specified range into the central freelist. N is the number of 1386 // elements in the range. 1387 void InsertRange(HardenedSLL start, HardenedSLL end, int N); 1388 1389 // Returns the actual number of fetched elements into N. 1390 void RemoveRange(HardenedSLL* start, HardenedSLL* end, int *N); 1391 1392 // Returns the number of free objects in cache. 1393 size_t length() { 1394 SpinLockHolder h(&lock_); 1395 return counter_; 1396 } 1397 1398 // Returns the number of free objects in the transfer cache. 1399 int tc_length() { 1400 SpinLockHolder h(&lock_); 1401 return used_slots_ * num_objects_to_move[size_class_]; 1402 } 1403 1404#ifdef WTF_CHANGES 1405 template <class Finder, class Reader> 1406 void enumerateFreeObjects(Finder& finder, const Reader& reader, TCMalloc_Central_FreeList* remoteCentralFreeList) 1407 { 1408 { 1409 static const ptrdiff_t emptyOffset = reinterpret_cast<const char*>(&empty_) - reinterpret_cast<const char*>(this); 1410 Span* remoteEmpty = reinterpret_cast<Span*>(reinterpret_cast<char*>(remoteCentralFreeList) + emptyOffset); 1411 Span* remoteSpan = nonempty_.remoteNext(remoteEmpty, entropy_); 1412 for (Span* span = reader(remoteEmpty); span && span != &empty_; remoteSpan = span->remoteNext(remoteSpan, entropy_), span = (remoteSpan ? reader(remoteSpan) : 0)) 1413 ASSERT(!span->objects); 1414 } 1415 1416 ASSERT(!nonempty_.objects); 1417 static const ptrdiff_t nonemptyOffset = reinterpret_cast<const char*>(&nonempty_) - reinterpret_cast<const char*>(this); 1418 1419 Span* remoteNonempty = reinterpret_cast<Span*>(reinterpret_cast<char*>(remoteCentralFreeList) + nonemptyOffset); 1420 Span* remoteSpan = nonempty_.remoteNext(remoteNonempty, entropy_); 1421 1422 for (Span* span = reader(remoteSpan); span && remoteSpan != remoteNonempty; remoteSpan = span->remoteNext(remoteSpan, entropy_), span = (remoteSpan ? reader(remoteSpan) : 0)) { 1423 for (HardenedSLL nextObject = span->objects; nextObject; nextObject.setValue(reader.nextEntryInHardenedLinkedList(reinterpret_cast<void**>(nextObject.value()), entropy_))) { 1424 finder.visit(nextObject.value()); 1425 } 1426 } 1427 1428 for (int slot = 0; slot < used_slots_; ++slot) { 1429 for (HardenedSLL entry = tc_slots_[slot].head; entry; entry.setValue(reader.nextEntryInHardenedLinkedList(reinterpret_cast<void**>(entry.value()), entropy_))) 1430 finder.visit(entry.value()); 1431 } 1432 } 1433#endif 1434 1435 uintptr_t entropy() const { return entropy_; } 1436 private: 1437 // REQUIRES: lock_ is held 1438 // Remove object from cache and return. 1439 // Return NULL if no free entries in cache. 1440 HardenedSLL FetchFromSpans(); 1441 1442 // REQUIRES: lock_ is held 1443 // Remove object from cache and return. Fetches 1444 // from pageheap if cache is empty. Only returns 1445 // NULL on allocation failure. 1446 HardenedSLL FetchFromSpansSafe(); 1447 1448 // REQUIRES: lock_ is held 1449 // Release a linked list of objects to spans. 1450 // May temporarily release lock_. 1451 void ReleaseListToSpans(HardenedSLL start); 1452 1453 // REQUIRES: lock_ is held 1454 // Release an object to spans. 1455 // May temporarily release lock_. 1456 ALWAYS_INLINE void ReleaseToSpans(HardenedSLL object); 1457 1458 // REQUIRES: lock_ is held 1459 // Populate cache by fetching from the page heap. 1460 // May temporarily release lock_. 1461 ALWAYS_INLINE void Populate(); 1462 1463 // REQUIRES: lock is held. 1464 // Tries to make room for a TCEntry. If the cache is full it will try to 1465 // expand it at the cost of some other cache size. Return false if there is 1466 // no space. 1467 bool MakeCacheSpace(); 1468 1469 // REQUIRES: lock_ for locked_size_class is held. 1470 // Picks a "random" size class to steal TCEntry slot from. In reality it 1471 // just iterates over the sizeclasses but does so without taking a lock. 1472 // Returns true on success. 1473 // May temporarily lock a "random" size class. 1474 static ALWAYS_INLINE bool EvictRandomSizeClass(size_t locked_size_class, bool force); 1475 1476 // REQUIRES: lock_ is *not* held. 1477 // Tries to shrink the Cache. If force is true it will relase objects to 1478 // spans if it allows it to shrink the cache. Return false if it failed to 1479 // shrink the cache. Decrements cache_size_ on succeess. 1480 // May temporarily take lock_. If it takes lock_, the locked_size_class 1481 // lock is released to the thread from holding two size class locks 1482 // concurrently which could lead to a deadlock. 1483 bool ShrinkCache(int locked_size_class, bool force); 1484 1485 // This lock protects all the data members. cached_entries and cache_size_ 1486 // may be looked at without holding the lock. 1487 SpinLock lock_; 1488 1489 // We keep linked lists of empty and non-empty spans. 1490 size_t size_class_; // My size class 1491 Span empty_; // Dummy header for list of empty spans 1492 Span nonempty_; // Dummy header for list of non-empty spans 1493 size_t counter_; // Number of free objects in cache entry 1494 1495 // Here we reserve space for TCEntry cache slots. Since one size class can 1496 // end up getting all the TCEntries quota in the system we just preallocate 1497 // sufficient number of entries here. 1498 TCEntry tc_slots_[K_NUM_TRANSFER_ENTRIES_MAX]; 1499 1500 // Number of currently used cached entries in tc_slots_. This variable is 1501 // updated under a lock but can be read without one. 1502 int32_t used_slots_; 1503 // The current number of slots for this size class. This is an 1504 // adaptive value that is increased if there is lots of traffic 1505 // on a given size class. 1506 int32_t cache_size_; 1507 uintptr_t entropy_; 1508}; 1509 1510#if COMPILER(CLANG) && defined(__has_warning) 1511#pragma clang diagnostic push 1512#if __has_warning("-Wunused-private-field") 1513#pragma clang diagnostic ignored "-Wunused-private-field" 1514#endif 1515#endif 1516 1517// Pad each CentralCache object to multiple of 64 bytes 1518template <size_t SizeToPad> 1519class TCMalloc_Central_FreeListPadded_Template : public TCMalloc_Central_FreeList { 1520private: 1521 char pad[64 - SizeToPad]; 1522}; 1523 1524// Zero-size specialization to avoid compiler error when TCMalloc_Central_FreeList happens 1525// to be exactly 64 bytes. 1526template <> class TCMalloc_Central_FreeListPadded_Template<0> : public TCMalloc_Central_FreeList { 1527}; 1528 1529typedef TCMalloc_Central_FreeListPadded_Template<sizeof(TCMalloc_Central_FreeList) % 64> TCMalloc_Central_FreeListPadded; 1530 1531#if COMPILER(CLANG) && defined(__has_warning) 1532#pragma clang diagnostic pop 1533#endif 1534 1535#if OS(DARWIN) 1536struct Span; 1537class TCMalloc_PageHeap; 1538class TCMalloc_ThreadCache; 1539template <typename T> class PageHeapAllocator; 1540 1541class FastMallocZone { 1542public: 1543 static void init(); 1544 1545 static kern_return_t enumerate(task_t, void*, unsigned typeMmask, vm_address_t zoneAddress, memory_reader_t, vm_range_recorder_t); 1546 static size_t goodSize(malloc_zone_t*, size_t size) { return size; } 1547 static boolean_t check(malloc_zone_t*) { return true; } 1548 static void print(malloc_zone_t*, boolean_t) { } 1549 static void log(malloc_zone_t*, void*) { } 1550 static void forceLock(malloc_zone_t*) { } 1551 static void forceUnlock(malloc_zone_t*) { } 1552 static void statistics(malloc_zone_t*, malloc_statistics_t* stats) { memset(stats, 0, sizeof(malloc_statistics_t)); } 1553 1554private: 1555 FastMallocZone(TCMalloc_PageHeap*, TCMalloc_ThreadCache**, TCMalloc_Central_FreeListPadded*, PageHeapAllocator<Span>*, PageHeapAllocator<TCMalloc_ThreadCache>*); 1556 static size_t size(malloc_zone_t*, const void*); 1557 static void* zoneMalloc(malloc_zone_t*, size_t); 1558 static void* zoneCalloc(malloc_zone_t*, size_t numItems, size_t size); 1559 static void zoneFree(malloc_zone_t*, void*); 1560 static void* zoneRealloc(malloc_zone_t*, void*, size_t); 1561 static void* zoneValloc(malloc_zone_t*, size_t) { LOG_ERROR("valloc is not supported"); return 0; } 1562 static void zoneDestroy(malloc_zone_t*) { } 1563 1564 malloc_zone_t m_zone; 1565 TCMalloc_PageHeap* m_pageHeap; 1566 TCMalloc_ThreadCache** m_threadHeaps; 1567 TCMalloc_Central_FreeListPadded* m_centralCaches; 1568 PageHeapAllocator<Span>* m_spanAllocator; 1569 PageHeapAllocator<TCMalloc_ThreadCache>* m_pageHeapAllocator; 1570}; 1571 1572// This method declaration, and the constants below, are taken from Libc/gen/malloc.c. 1573extern "C" void (*malloc_logger)(uint32_t typeFlags, uintptr_t zone, uintptr_t size, uintptr_t pointer, uintptr_t returnValue, uint32_t numberOfFramesToSkip); 1574 1575#endif 1576 1577class MallocHook { 1578 static bool stackLoggingEnabled; 1579 1580#if OS(DARWIN) 1581 1582 enum StackLoggingType { 1583 StackLoggingTypeAlloc = 2, 1584 StackLoggingTypeDealloc = 4, 1585 }; 1586 1587 static void record(uint32_t typeFlags, uintptr_t zone, uintptr_t size, void* pointer, void* returnValue, uint32_t numberOfFramesToSkip) 1588 { 1589 malloc_logger(typeFlags, zone, size, reinterpret_cast<uintptr_t>(pointer), reinterpret_cast<uintptr_t>(returnValue), numberOfFramesToSkip); 1590 } 1591 1592 static NEVER_INLINE void recordAllocation(void* pointer, size_t size) 1593 { 1594 // StackLoggingTypeAlloc takes the newly-allocated address in the returnValue argument, the size of the allocation 1595 // in the size argument and ignores all other arguments. 1596 record(StackLoggingTypeAlloc, 0, size, 0, pointer, 0); 1597 } 1598 1599 static NEVER_INLINE void recordDeallocation(void* pointer) 1600 { 1601 // StackLoggingTypeDealloc takes the pointer in the size argument and ignores all other arguments. 1602 record(StackLoggingTypeDealloc, 0, reinterpret_cast<uintptr_t>(pointer), 0, 0, 0); 1603 } 1604 1605#endif 1606 1607public: 1608 static void init() 1609 { 1610#if OS(DARWIN) 1611 // If the system allocator's malloc_logger has been set up then stack logging is enabled. 1612 stackLoggingEnabled = malloc_logger; 1613#endif 1614 } 1615 1616#if OS(DARWIN) 1617 static ALWAYS_INLINE void InvokeNewHook(void* pointer, size_t size) 1618 { 1619 if (UNLIKELY(stackLoggingEnabled)) 1620 recordAllocation(pointer, size); 1621 } 1622 1623 static ALWAYS_INLINE void InvokeDeleteHook(void* pointer) 1624 { 1625 1626 if (UNLIKELY(stackLoggingEnabled)) 1627 recordDeallocation(pointer); 1628 } 1629#else 1630 static ALWAYS_INLINE void InvokeNewHook(void*, size_t) { } 1631 static ALWAYS_INLINE void InvokeDeleteHook(void*) { } 1632#endif 1633}; 1634bool MallocHook::stackLoggingEnabled = false; 1635 1636#endif 1637 1638#ifndef WTF_CHANGES 1639// This #ifdef should almost never be set. Set NO_TCMALLOC_SAMPLES if 1640// you're porting to a system where you really can't get a stacktrace. 1641#ifdef NO_TCMALLOC_SAMPLES 1642// We use #define so code compiles even if you #include stacktrace.h somehow. 1643# define GetStackTrace(stack, depth, skip) (0) 1644#else 1645# include <google/stacktrace.h> 1646#endif 1647#endif 1648 1649// Even if we have support for thread-local storage in the compiler 1650// and linker, the OS may not support it. We need to check that at 1651// runtime. Right now, we have to keep a manual set of "bad" OSes. 1652#if defined(HAVE_TLS) 1653 static bool kernel_supports_tls = false; // be conservative 1654 static inline bool KernelSupportsTLS() { 1655 return kernel_supports_tls; 1656 } 1657# if !HAVE_DECL_UNAME // if too old for uname, probably too old for TLS 1658 static void CheckIfKernelSupportsTLS() { 1659 kernel_supports_tls = false; 1660 } 1661# else 1662# include <sys/utsname.h> // DECL_UNAME checked for <sys/utsname.h> too 1663 static void CheckIfKernelSupportsTLS() { 1664 struct utsname buf; 1665 if (uname(&buf) != 0) { // should be impossible 1666 MESSAGE("uname failed assuming no TLS support (errno=%d)\n", errno); 1667 kernel_supports_tls = false; 1668 } else if (strcasecmp(buf.sysname, "linux") == 0) { 1669 // The linux case: the first kernel to support TLS was 2.6.0 1670 if (buf.release[0] < '2' && buf.release[1] == '.') // 0.x or 1.x 1671 kernel_supports_tls = false; 1672 else if (buf.release[0] == '2' && buf.release[1] == '.' && 1673 buf.release[2] >= '0' && buf.release[2] < '6' && 1674 buf.release[3] == '.') // 2.0 - 2.5 1675 kernel_supports_tls = false; 1676 else 1677 kernel_supports_tls = true; 1678 } else { // some other kernel, we'll be optimisitic 1679 kernel_supports_tls = true; 1680 } 1681 // TODO(csilvers): VLOG(1) the tls status once we support RAW_VLOG 1682 } 1683# endif // HAVE_DECL_UNAME 1684#endif // HAVE_TLS 1685 1686// __THROW is defined in glibc systems. It means, counter-intuitively, 1687// "This function will never throw an exception." It's an optional 1688// optimization tool, but we may need to use it to match glibc prototypes. 1689#ifndef __THROW // I guess we're not on a glibc system 1690# define __THROW // __THROW is just an optimization, so ok to make it "" 1691#endif 1692 1693// ------------------------------------------------------------------------- 1694// Stack traces kept for sampled allocations 1695// The following state is protected by pageheap_lock_. 1696// ------------------------------------------------------------------------- 1697 1698// size/depth are made the same size as a pointer so that some generic 1699// code below can conveniently cast them back and forth to void*. 1700static const int kMaxStackDepth = 31; 1701struct StackTrace { 1702 uintptr_t size; // Size of object 1703 uintptr_t depth; // Number of PC values stored in array below 1704 void* stack[kMaxStackDepth]; 1705}; 1706static PageHeapAllocator<StackTrace> stacktrace_allocator; 1707static Span sampled_objects; 1708 1709// ------------------------------------------------------------------------- 1710// Map from page-id to per-page data 1711// ------------------------------------------------------------------------- 1712 1713// We use PageMap2<> for 32-bit and PageMap3<> for 64-bit machines. 1714// We also use a simple one-level cache for hot PageID-to-sizeclass mappings, 1715// because sometimes the sizeclass is all the information we need. 1716 1717// Selector class -- general selector uses 3-level map 1718template <int BITS> class MapSelector { 1719 public: 1720 typedef TCMalloc_PageMap3<BITS-K_PAGE_SHIFT_MIN> Type; 1721 typedef PackedCache<BITS, uint64_t> CacheType; 1722}; 1723 1724#if defined(WTF_CHANGES) 1725#if CPU(X86_64) || CPU(ARM64) 1726// On all known X86-64 platforms, the upper 16 bits are always unused and therefore 1727// can be excluded from the PageMap key. 1728// See http://en.wikipedia.org/wiki/X86-64#Virtual_address_space_details 1729 1730static const size_t kBitsUnusedOn64Bit = 16; 1731#else 1732static const size_t kBitsUnusedOn64Bit = 0; 1733#endif 1734 1735// A three-level map for 64-bit machines 1736template <> class MapSelector<64> { 1737 public: 1738 typedef TCMalloc_PageMap3<64 - K_PAGE_SHIFT_MIN - kBitsUnusedOn64Bit> Type; 1739 typedef PackedCache<64, uint64_t> CacheType; 1740}; 1741#endif 1742 1743// A two-level map for 32-bit machines 1744template <> class MapSelector<32> { 1745 public: 1746 typedef TCMalloc_PageMap2<32 - K_PAGE_SHIFT_MIN> Type; 1747 typedef PackedCache<32 - K_PAGE_SHIFT_MIN, uint16_t> CacheType; 1748}; 1749 1750// ------------------------------------------------------------------------- 1751// Page-level allocator 1752// * Eager coalescing 1753// 1754// Heap for page-level allocation. We allow allocating and freeing a 1755// contiguous runs of pages (called a "span"). 1756// ------------------------------------------------------------------------- 1757 1758#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 1759// The page heap maintains a free list for spans that are no longer in use by 1760// the central cache or any thread caches. We use a background thread to 1761// periodically scan the free list and release a percentage of it back to the OS. 1762 1763// If free_committed_pages_ exceeds kMinimumFreeCommittedPageCount, the 1764// background thread: 1765// - wakes up 1766// - pauses for kScavengeDelayInSeconds 1767// - returns to the OS a percentage of the memory that remained unused during 1768// that pause (kScavengePercentage * min_free_committed_pages_since_last_scavenge_) 1769// The goal of this strategy is to reduce memory pressure in a timely fashion 1770// while avoiding thrashing the OS allocator. 1771 1772// Time delay before the page heap scavenger will consider returning pages to 1773// the OS. 1774static const int kScavengeDelayInSeconds = 2; 1775 1776// Approximate percentage of free committed pages to return to the OS in one 1777// scavenge. 1778static const float kScavengePercentage = .5f; 1779 1780// number of span lists to keep spans in when memory is returned. 1781static const int kMinSpanListsWithSpans = 32; 1782 1783// Number of free committed pages that we want to keep around. The minimum number of pages used when there 1784// is 1 span in each of the first kMinSpanListsWithSpans spanlists. Currently 528 pages. 1785static const size_t kMinimumFreeCommittedPageCount = kMinSpanListsWithSpans * ((1.0f+kMinSpanListsWithSpans) / 2.0f); 1786 1787#endif 1788 1789static SpinLock pageheap_lock = SPINLOCK_INITIALIZER; 1790 1791class TCMalloc_PageHeap { 1792 public: 1793 void init(); 1794 1795 // Allocate a run of "n" pages. Returns zero if out of memory. 1796 Span* New(Length n); 1797 1798 // Delete the span "[p, p+n-1]". 1799 // REQUIRES: span was returned by earlier call to New() and 1800 // has not yet been deleted. 1801 void Delete(Span* span); 1802 1803 // Mark an allocated span as being used for small objects of the 1804 // specified size-class. 1805 // REQUIRES: span was returned by an earlier call to New() 1806 // and has not yet been deleted. 1807 void RegisterSizeClass(Span* span, size_t sc); 1808 1809 // Split an allocated span into two spans: one of length "n" pages 1810 // followed by another span of length "span->length - n" pages. 1811 // Modifies "*span" to point to the first span of length "n" pages. 1812 // Returns a pointer to the second span. 1813 // 1814 // REQUIRES: "0 < n < span->length" 1815 // REQUIRES: !span->free 1816 // REQUIRES: span->sizeclass == 0 1817 Span* Split(Span* span, Length n); 1818 1819 // Return the descriptor for the specified page. 1820 inline Span* GetDescriptor(PageID p) const { 1821 return reinterpret_cast<Span*>(pagemap_.get(p)); 1822 } 1823 1824#ifdef WTF_CHANGES 1825 inline Span* GetDescriptorEnsureSafe(PageID p) 1826 { 1827 pagemap_.Ensure(p, 1); 1828 return GetDescriptor(p); 1829 } 1830 1831 size_t ReturnedBytes() const; 1832#endif 1833 1834 // Dump state to stderr 1835#ifndef WTF_CHANGES 1836 void Dump(TCMalloc_Printer* out); 1837#endif 1838 1839 // Return number of bytes allocated from system 1840 inline uint64_t SystemBytes() const { return system_bytes_; } 1841 1842 // Return number of free bytes in heap 1843 uint64_t FreeBytes() const { 1844 ASSERT(kPageShift && kNumClasses && kPageSize); 1845 return (static_cast<uint64_t>(free_pages_) << kPageShift); 1846 } 1847 1848 bool Check(); 1849 size_t CheckList(Span* list, Length min_pages, Length max_pages, bool decommitted); 1850 1851 // Release all pages on the free list for reuse by the OS: 1852 void ReleaseFreePages(); 1853 void ReleaseFreeList(Span*, Span*); 1854 1855 // Return 0 if we have no information, or else the correct sizeclass for p. 1856 // Reads and writes to pagemap_cache_ do not require locking. 1857 // The entries are 64 bits on 64-bit hardware and 16 bits on 1858 // 32-bit hardware, and we don't mind raciness as long as each read of 1859 // an entry yields a valid entry, not a partially updated entry. 1860 size_t GetSizeClassIfCached(PageID p) const { 1861 return pagemap_cache_.GetOrDefault(p, 0); 1862 } 1863 void CacheSizeClass(PageID p, size_t cl) const { pagemap_cache_.Put(p, cl); } 1864 1865 private: 1866 // Pick the appropriate map and cache types based on pointer size 1867 typedef MapSelector<8*sizeof(uintptr_t)>::Type PageMap; 1868 typedef MapSelector<8*sizeof(uintptr_t)>::CacheType PageMapCache; 1869 PageMap pagemap_; 1870 mutable PageMapCache pagemap_cache_; 1871 1872 // We segregate spans of a given size into two circular linked 1873 // lists: one for normal spans, and one for spans whose memory 1874 // has been returned to the system. 1875 struct SpanList { 1876 Span normal; 1877 Span returned; 1878 }; 1879 1880 // List of free spans of length >= kMaxPages 1881 SpanList large_; 1882 1883 // Array mapping from span length to a doubly linked list of free spans 1884 SpanList free_[kMaxPages]; 1885 1886 // Number of pages kept in free lists 1887 uintptr_t free_pages_; 1888 1889 // Used for hardening 1890 uintptr_t entropy_; 1891 1892 // Bytes allocated from system 1893 uint64_t system_bytes_; 1894 1895#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 1896 // Number of pages kept in free lists that are still committed. 1897 Length free_committed_pages_; 1898 1899 // Minimum number of free committed pages since last scavenge. (Can be 0 if 1900 // we've committed new pages since the last scavenge.) 1901 Length min_free_committed_pages_since_last_scavenge_; 1902#endif 1903 1904 bool GrowHeap(Length n); 1905 1906 // REQUIRES span->length >= n 1907 // Remove span from its free list, and move any leftover part of 1908 // span into appropriate free lists. Also update "span" to have 1909 // length exactly "n" and mark it as non-free so it can be returned 1910 // to the client. 1911 // 1912 // "released" is true iff "span" was found on a "returned" list. 1913 void Carve(Span* span, Length n, bool released); 1914 1915 void RecordSpan(Span* span) { 1916 pagemap_.set(span->start, span); 1917 if (span->length > 1) { 1918 pagemap_.set(span->start + span->length - 1, span); 1919 } 1920 } 1921 1922 // Allocate a large span of length == n. If successful, returns a 1923 // span of exactly the specified length. Else, returns NULL. 1924 Span* AllocLarge(Length n); 1925 1926#if !USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 1927 // Incrementally release some memory to the system. 1928 // IncrementalScavenge(n) is called whenever n pages are freed. 1929 void IncrementalScavenge(Length n); 1930#endif 1931 1932 // Number of pages to deallocate before doing more scavenging 1933 int64_t scavenge_counter_; 1934 1935 // Index of last free list we scavenged 1936 size_t scavenge_index_; 1937 1938#if defined(WTF_CHANGES) && OS(DARWIN) 1939 friend class FastMallocZone; 1940#endif 1941 1942#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 1943 void initializeScavenger(); 1944 ALWAYS_INLINE void signalScavenger(); 1945 void scavenge(); 1946 ALWAYS_INLINE bool shouldScavenge() const; 1947 1948#if HAVE(DISPATCH_H) || OS(WINDOWS) 1949 void periodicScavenge(); 1950 ALWAYS_INLINE bool isScavengerSuspended(); 1951 ALWAYS_INLINE void scheduleScavenger(); 1952 ALWAYS_INLINE void rescheduleScavenger(); 1953 ALWAYS_INLINE void suspendScavenger(); 1954#endif 1955 1956#if HAVE(DISPATCH_H) 1957 dispatch_queue_t m_scavengeQueue; 1958 dispatch_source_t m_scavengeTimer; 1959 bool m_scavengingSuspended; 1960#elif OS(WINDOWS) 1961 static void CALLBACK scavengerTimerFired(void*, BOOLEAN); 1962 HANDLE m_scavengeQueueTimer; 1963#else 1964 static NO_RETURN_WITH_VALUE void* runScavengerThread(void*); 1965 NO_RETURN void scavengerThread(); 1966 1967 // Keeps track of whether the background thread is actively scavenging memory every kScavengeDelayInSeconds, or 1968 // it's blocked waiting for more pages to be deleted. 1969 bool m_scavengeThreadActive; 1970 1971 pthread_mutex_t m_scavengeMutex; 1972 pthread_cond_t m_scavengeCondition; 1973#endif 1974 1975#endif // USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 1976}; 1977 1978void TCMalloc_PageHeap::init() 1979{ 1980 ASSERT(kPageShift && kNumClasses && kPageSize); 1981 1982 pagemap_.init(MetaDataAlloc); 1983 pagemap_cache_ = PageMapCache(0); 1984 free_pages_ = 0; 1985 system_bytes_ = 0; 1986 entropy_ = HARDENING_ENTROPY; 1987 1988#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 1989 free_committed_pages_ = 0; 1990 min_free_committed_pages_since_last_scavenge_ = 0; 1991#endif // USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 1992 1993 scavenge_counter_ = 0; 1994 // Start scavenging at kMaxPages list 1995 scavenge_index_ = kMaxPages-1; 1996 ASSERT(kNumClasses <= (1 << PageMapCache::kValuebits)); 1997 DLL_Init(&large_.normal, entropy_); 1998 DLL_Init(&large_.returned, entropy_); 1999 for (size_t i = 0; i < kMaxPages; i++) { 2000 DLL_Init(&free_[i].normal, entropy_); 2001 DLL_Init(&free_[i].returned, entropy_); 2002 } 2003 2004#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2005 initializeScavenger(); 2006#endif // USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2007} 2008 2009#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2010 2011#if HAVE(DISPATCH_H) 2012 2013void TCMalloc_PageHeap::initializeScavenger() 2014{ 2015 m_scavengeQueue = dispatch_queue_create("com.apple.JavaScriptCore.FastMallocSavenger", NULL); 2016 m_scavengeTimer = dispatch_source_create(DISPATCH_SOURCE_TYPE_TIMER, 0, 0, m_scavengeQueue); 2017 uint64_t scavengeDelayInNanoseconds = kScavengeDelayInSeconds * NSEC_PER_SEC; 2018 dispatch_time_t startTime = dispatch_time(DISPATCH_TIME_NOW, scavengeDelayInNanoseconds); 2019 dispatch_source_set_timer(m_scavengeTimer, startTime, scavengeDelayInNanoseconds, scavengeDelayInNanoseconds / 10); 2020 dispatch_source_set_event_handler(m_scavengeTimer, ^{ periodicScavenge(); }); 2021 m_scavengingSuspended = true; 2022} 2023 2024ALWAYS_INLINE bool TCMalloc_PageHeap::isScavengerSuspended() 2025{ 2026 ASSERT(pageheap_lock.IsHeld()); 2027 return m_scavengingSuspended; 2028} 2029 2030ALWAYS_INLINE void TCMalloc_PageHeap::scheduleScavenger() 2031{ 2032 ASSERT(pageheap_lock.IsHeld()); 2033 m_scavengingSuspended = false; 2034 dispatch_resume(m_scavengeTimer); 2035} 2036 2037ALWAYS_INLINE void TCMalloc_PageHeap::rescheduleScavenger() 2038{ 2039 // Nothing to do here for libdispatch. 2040} 2041 2042ALWAYS_INLINE void TCMalloc_PageHeap::suspendScavenger() 2043{ 2044 ASSERT(pageheap_lock.IsHeld()); 2045 m_scavengingSuspended = true; 2046 dispatch_suspend(m_scavengeTimer); 2047} 2048 2049#elif OS(WINDOWS) 2050 2051void TCMalloc_PageHeap::scavengerTimerFired(void* context, BOOLEAN) 2052{ 2053 static_cast<TCMalloc_PageHeap*>(context)->periodicScavenge(); 2054} 2055 2056void TCMalloc_PageHeap::initializeScavenger() 2057{ 2058 m_scavengeQueueTimer = 0; 2059} 2060 2061ALWAYS_INLINE bool TCMalloc_PageHeap::isScavengerSuspended() 2062{ 2063 ASSERT(pageheap_lock.IsHeld()); 2064 return !m_scavengeQueueTimer; 2065} 2066 2067ALWAYS_INLINE void TCMalloc_PageHeap::scheduleScavenger() 2068{ 2069 // We need to use WT_EXECUTEONLYONCE here and reschedule the timer, because 2070 // Windows will fire the timer event even when the function is already running. 2071 ASSERT(pageheap_lock.IsHeld()); 2072 CreateTimerQueueTimer(&m_scavengeQueueTimer, 0, scavengerTimerFired, this, kScavengeDelayInSeconds * 1000, 0, WT_EXECUTEONLYONCE); 2073} 2074 2075ALWAYS_INLINE void TCMalloc_PageHeap::rescheduleScavenger() 2076{ 2077 // We must delete the timer and create it again, because it is not possible to retrigger a timer on Windows. 2078 suspendScavenger(); 2079 scheduleScavenger(); 2080} 2081 2082ALWAYS_INLINE void TCMalloc_PageHeap::suspendScavenger() 2083{ 2084 ASSERT(pageheap_lock.IsHeld()); 2085 HANDLE scavengeQueueTimer = m_scavengeQueueTimer; 2086 m_scavengeQueueTimer = 0; 2087 DeleteTimerQueueTimer(0, scavengeQueueTimer, 0); 2088} 2089 2090#else 2091 2092void TCMalloc_PageHeap::initializeScavenger() 2093{ 2094 // Create a non-recursive mutex. 2095#if !defined(PTHREAD_MUTEX_NORMAL) || PTHREAD_MUTEX_NORMAL == PTHREAD_MUTEX_DEFAULT 2096 pthread_mutex_init(&m_scavengeMutex, 0); 2097#else 2098 pthread_mutexattr_t attr; 2099 pthread_mutexattr_init(&attr); 2100 pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_NORMAL); 2101 2102 pthread_mutex_init(&m_scavengeMutex, &attr); 2103 2104 pthread_mutexattr_destroy(&attr); 2105#endif 2106 2107 pthread_cond_init(&m_scavengeCondition, 0); 2108 m_scavengeThreadActive = true; 2109 pthread_t thread; 2110 pthread_create(&thread, 0, runScavengerThread, this); 2111} 2112 2113void* TCMalloc_PageHeap::runScavengerThread(void* context) 2114{ 2115 static_cast<TCMalloc_PageHeap*>(context)->scavengerThread(); 2116#if (COMPILER(MSVC) || COMPILER(SUNCC)) 2117 // Without this, Visual Studio and Sun Studio will complain that this method does not return a value. 2118 return 0; 2119#endif 2120} 2121 2122ALWAYS_INLINE void TCMalloc_PageHeap::signalScavenger() 2123{ 2124 // shouldScavenge() should be called only when the pageheap_lock spinlock is held, additionally, 2125 // m_scavengeThreadActive is only set to false whilst pageheap_lock is held. The caller must ensure this is 2126 // taken prior to calling this method. If the scavenger thread is sleeping and shouldScavenge() indicates there 2127 // is memory to free the scavenger thread is signalled to start. 2128 ASSERT(pageheap_lock.IsHeld()); 2129 if (!m_scavengeThreadActive && shouldScavenge()) 2130 pthread_cond_signal(&m_scavengeCondition); 2131} 2132 2133#endif 2134 2135void TCMalloc_PageHeap::scavenge() 2136{ 2137 ASSERT(kPageShift && kNumClasses && kPageSize); 2138 size_t pagesToRelease = min_free_committed_pages_since_last_scavenge_ * kScavengePercentage; 2139 size_t targetPageCount = std::max<size_t>(kMinimumFreeCommittedPageCount, free_committed_pages_ - pagesToRelease); 2140 2141 Length lastFreeCommittedPages = free_committed_pages_; 2142 while (free_committed_pages_ > targetPageCount) { 2143 ASSERT(Check()); 2144 for (int i = kMaxPages; i > 0 && free_committed_pages_ >= targetPageCount; i--) { 2145 SpanList* slist = (static_cast<size_t>(i) == kMaxPages) ? &large_ : &free_[i]; 2146 // If the span size is bigger than kMinSpanListsWithSpans pages return all the spans in the list, else return all but 1 span. 2147 // Return only 50% of a spanlist at a time so spans of size 1 are not the only ones left. 2148 size_t length = DLL_Length(&slist->normal, entropy_); 2149 size_t numSpansToReturn = (i > kMinSpanListsWithSpans) ? length : length / 2; 2150 for (int j = 0; static_cast<size_t>(j) < numSpansToReturn && !DLL_IsEmpty(&slist->normal, entropy_) && free_committed_pages_ > targetPageCount; j++) { 2151 Span* s = slist->normal.prev(entropy_); 2152 DLL_Remove(s, entropy_); 2153 ASSERT(!s->decommitted); 2154 if (!s->decommitted) { 2155 TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift), 2156 static_cast<size_t>(s->length << kPageShift)); 2157 ASSERT(free_committed_pages_ >= s->length); 2158 free_committed_pages_ -= s->length; 2159 s->decommitted = true; 2160 } 2161 DLL_Prepend(&slist->returned, s, entropy_); 2162 } 2163 } 2164 2165 if (lastFreeCommittedPages == free_committed_pages_) 2166 break; 2167 lastFreeCommittedPages = free_committed_pages_; 2168 } 2169 2170 min_free_committed_pages_since_last_scavenge_ = free_committed_pages_; 2171} 2172 2173ALWAYS_INLINE bool TCMalloc_PageHeap::shouldScavenge() const 2174{ 2175 return free_committed_pages_ > kMinimumFreeCommittedPageCount; 2176} 2177 2178#endif // USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2179 2180inline Span* TCMalloc_PageHeap::New(Length n) { 2181 ASSERT(Check()); 2182 ASSERT(n > 0); 2183 2184 // Find first size >= n that has a non-empty list 2185 for (Length s = n; s < kMaxPages; s++) { 2186 Span* ll = NULL; 2187 bool released = false; 2188 if (!DLL_IsEmpty(&free_[s].normal, entropy_)) { 2189 // Found normal span 2190 ll = &free_[s].normal; 2191 } else if (!DLL_IsEmpty(&free_[s].returned, entropy_)) { 2192 // Found returned span; reallocate it 2193 ll = &free_[s].returned; 2194 released = true; 2195 } else { 2196 // Keep looking in larger classes 2197 continue; 2198 } 2199 2200 Span* result = ll->next(entropy_); 2201 Carve(result, n, released); 2202#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2203 // The newly allocated memory is from a span that's in the normal span list (already committed). Update the 2204 // free committed pages count. 2205 ASSERT(free_committed_pages_ >= n); 2206 free_committed_pages_ -= n; 2207 if (free_committed_pages_ < min_free_committed_pages_since_last_scavenge_) 2208 min_free_committed_pages_since_last_scavenge_ = free_committed_pages_; 2209#endif // USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2210 ASSERT(Check()); 2211 free_pages_ -= n; 2212 return result; 2213 } 2214 2215 Span* result = AllocLarge(n); 2216 if (result != NULL) { 2217 ASSERT_SPAN_COMMITTED(result); 2218 return result; 2219 } 2220 2221 // Grow the heap and try again 2222 if (!GrowHeap(n)) { 2223 ASSERT(Check()); 2224 return NULL; 2225 } 2226 2227 return New(n); 2228} 2229 2230Span* TCMalloc_PageHeap::AllocLarge(Length n) { 2231 // find the best span (closest to n in size). 2232 // The following loops implements address-ordered best-fit. 2233 bool from_released = false; 2234 Span *best = NULL; 2235 2236 // Search through normal list 2237 for (Span* span = large_.normal.next(entropy_); 2238 span != &large_.normal; 2239 span = span->next(entropy_)) { 2240 if (span->length >= n) { 2241 if ((best == NULL) 2242 || (span->length < best->length) 2243 || ((span->length == best->length) && (span->start < best->start))) { 2244 best = span; 2245 from_released = false; 2246 } 2247 } 2248 } 2249 2250 // Search through released list in case it has a better fit 2251 for (Span* span = large_.returned.next(entropy_); 2252 span != &large_.returned; 2253 span = span->next(entropy_)) { 2254 if (span->length >= n) { 2255 if ((best == NULL) 2256 || (span->length < best->length) 2257 || ((span->length == best->length) && (span->start < best->start))) { 2258 best = span; 2259 from_released = true; 2260 } 2261 } 2262 } 2263 2264 if (best != NULL) { 2265 Carve(best, n, from_released); 2266#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2267 // The newly allocated memory is from a span that's in the normal span list (already committed). Update the 2268 // free committed pages count. 2269 ASSERT(free_committed_pages_ >= n); 2270 free_committed_pages_ -= n; 2271 if (free_committed_pages_ < min_free_committed_pages_since_last_scavenge_) 2272 min_free_committed_pages_since_last_scavenge_ = free_committed_pages_; 2273#endif // USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2274 ASSERT(Check()); 2275 free_pages_ -= n; 2276 return best; 2277 } 2278 return NULL; 2279} 2280 2281Span* TCMalloc_PageHeap::Split(Span* span, Length n) { 2282 ASSERT(0 < n); 2283 ASSERT(n < span->length); 2284 ASSERT(!span->free); 2285 ASSERT(span->sizeclass == 0); 2286 Event(span, 'T', n); 2287 2288 const Length extra = span->length - n; 2289 Span* leftover = NewSpan(span->start + n, extra); 2290 Event(leftover, 'U', extra); 2291 RecordSpan(leftover); 2292 pagemap_.set(span->start + n - 1, span); // Update map from pageid to span 2293 span->length = n; 2294 2295 return leftover; 2296} 2297 2298inline void TCMalloc_PageHeap::Carve(Span* span, Length n, bool released) { 2299 ASSERT(kPageShift && kNumClasses && kPageSize); 2300 ASSERT(n > 0); 2301 DLL_Remove(span, entropy_); 2302 span->free = 0; 2303 Event(span, 'A', n); 2304 2305 if (released) { 2306 // If the span chosen to carve from is decommited, commit the entire span at once to avoid committing spans 1 page at a time. 2307 ASSERT(span->decommitted); 2308 TCMalloc_SystemCommit(reinterpret_cast<void*>(span->start << kPageShift), static_cast<size_t>(span->length << kPageShift)); 2309 span->decommitted = false; 2310#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2311 free_committed_pages_ += span->length; 2312#endif 2313 } 2314 2315 const int extra = static_cast<int>(span->length - n); 2316 ASSERT(extra >= 0); 2317 if (extra > 0) { 2318 Span* leftover = NewSpan(span->start + n, extra); 2319 leftover->free = 1; 2320 leftover->decommitted = false; 2321 Event(leftover, 'S', extra); 2322 RecordSpan(leftover); 2323 2324 // Place leftover span on appropriate free list 2325 SpanList* listpair = (static_cast<size_t>(extra) < kMaxPages) ? &free_[extra] : &large_; 2326 Span* dst = &listpair->normal; 2327 DLL_Prepend(dst, leftover, entropy_); 2328 2329 span->length = n; 2330 pagemap_.set(span->start + n - 1, span); 2331 } 2332} 2333 2334static ALWAYS_INLINE void mergeDecommittedStates(Span* destination, Span* other) 2335{ 2336 ASSERT(kPageShift && kNumClasses && kPageSize); 2337 if (destination->decommitted && !other->decommitted) { 2338 TCMalloc_SystemRelease(reinterpret_cast<void*>(other->start << kPageShift), 2339 static_cast<size_t>(other->length << kPageShift)); 2340 } else if (other->decommitted && !destination->decommitted) { 2341 TCMalloc_SystemRelease(reinterpret_cast<void*>(destination->start << kPageShift), 2342 static_cast<size_t>(destination->length << kPageShift)); 2343 destination->decommitted = true; 2344 } 2345} 2346 2347inline void TCMalloc_PageHeap::Delete(Span* span) { 2348 ASSERT(Check()); 2349 ASSERT(!span->free); 2350 ASSERT(span->length > 0); 2351 ASSERT(GetDescriptor(span->start) == span); 2352 ASSERT(GetDescriptor(span->start + span->length - 1) == span); 2353 span->sizeclass = 0; 2354#ifndef NO_TCMALLOC_SAMPLES 2355 span->sample = 0; 2356#endif 2357 2358 // Coalesce -- we guarantee that "p" != 0, so no bounds checking 2359 // necessary. We do not bother resetting the stale pagemap 2360 // entries for the pieces we are merging together because we only 2361 // care about the pagemap entries for the boundaries. 2362#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2363 // Track the total size of the neighboring free spans that are committed. 2364 Length neighboringCommittedSpansLength = 0; 2365#endif 2366 const PageID p = span->start; 2367 const Length n = span->length; 2368 Span* prev = GetDescriptor(p-1); 2369 if (prev != NULL && prev->free) { 2370 // Merge preceding span into this span 2371 ASSERT(prev->start + prev->length == p); 2372 const Length len = prev->length; 2373#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2374 if (!prev->decommitted) 2375 neighboringCommittedSpansLength += len; 2376#endif 2377 mergeDecommittedStates(span, prev); 2378 DLL_Remove(prev, entropy_); 2379 DeleteSpan(prev); 2380 span->start -= len; 2381 span->length += len; 2382 pagemap_.set(span->start, span); 2383 Event(span, 'L', len); 2384 } 2385 Span* next = GetDescriptor(p+n); 2386 if (next != NULL && next->free) { 2387 // Merge next span into this span 2388 ASSERT(next->start == p+n); 2389 const Length len = next->length; 2390#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2391 if (!next->decommitted) 2392 neighboringCommittedSpansLength += len; 2393#endif 2394 mergeDecommittedStates(span, next); 2395 DLL_Remove(next, entropy_); 2396 DeleteSpan(next); 2397 span->length += len; 2398 pagemap_.set(span->start + span->length - 1, span); 2399 Event(span, 'R', len); 2400 } 2401 2402 Event(span, 'D', span->length); 2403 span->free = 1; 2404 if (span->decommitted) { 2405 if (span->length < kMaxPages) 2406 DLL_Prepend(&free_[span->length].returned, span, entropy_); 2407 else 2408 DLL_Prepend(&large_.returned, span, entropy_); 2409 } else { 2410 if (span->length < kMaxPages) 2411 DLL_Prepend(&free_[span->length].normal, span, entropy_); 2412 else 2413 DLL_Prepend(&large_.normal, span, entropy_); 2414 } 2415 free_pages_ += n; 2416 2417#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2418 if (span->decommitted) { 2419 // If the merged span is decommitted, that means we decommitted any neighboring spans that were 2420 // committed. Update the free committed pages count. 2421 free_committed_pages_ -= neighboringCommittedSpansLength; 2422 if (free_committed_pages_ < min_free_committed_pages_since_last_scavenge_) 2423 min_free_committed_pages_since_last_scavenge_ = free_committed_pages_; 2424 } else { 2425 // If the merged span remains committed, add the deleted span's size to the free committed pages count. 2426 free_committed_pages_ += n; 2427 } 2428 2429 // Make sure the scavenge thread becomes active if we have enough freed pages to release some back to the system. 2430 signalScavenger(); 2431#else 2432 IncrementalScavenge(n); 2433#endif 2434 2435 ASSERT(Check()); 2436} 2437 2438#if !USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2439void TCMalloc_PageHeap::IncrementalScavenge(Length n) { 2440 ASSERT(kPageShift && kNumClasses && kPageSize); 2441 // Fast path; not yet time to release memory 2442 scavenge_counter_ -= n; 2443 if (scavenge_counter_ >= 0) return; // Not yet time to scavenge 2444 2445#if PLATFORM(IOS) 2446 static const size_t kDefaultReleaseDelay = 64; 2447#else 2448 // If there is nothing to release, wait for so many pages before 2449 // scavenging again. With 4K pages, this comes to 16MB of memory. 2450 static const size_t kDefaultReleaseDelay = 1 << 8; 2451#endif 2452 2453 // Find index of free list to scavenge 2454 size_t index = scavenge_index_ + 1; 2455 uintptr_t entropy = entropy_; 2456 for (size_t i = 0; i < kMaxPages+1; i++) { 2457 if (index > kMaxPages) index = 0; 2458 SpanList* slist = (index == kMaxPages) ? &large_ : &free_[index]; 2459 if (!DLL_IsEmpty(&slist->normal, entropy)) { 2460 // Release the last span on the normal portion of this list 2461 Span* s = slist->normal.prev(entropy); 2462 DLL_Remove(s, entropy_); 2463 TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift), 2464 static_cast<size_t>(s->length << kPageShift)); 2465 s->decommitted = true; 2466 DLL_Prepend(&slist->returned, s, entropy); 2467 2468#if PLATFORM(IOS) 2469 scavenge_counter_ = std::max<size_t>(16UL, std::min<size_t>(kDefaultReleaseDelay, kDefaultReleaseDelay - (free_pages_ / kDefaultReleaseDelay))); 2470#else 2471 scavenge_counter_ = std::max<size_t>(64UL, std::min<size_t>(kDefaultReleaseDelay, kDefaultReleaseDelay - (free_pages_ / kDefaultReleaseDelay))); 2472#endif 2473 2474 if (index == kMaxPages && !DLL_IsEmpty(&slist->normal, entropy)) 2475 scavenge_index_ = index - 1; 2476 else 2477 scavenge_index_ = index; 2478 return; 2479 } 2480 index++; 2481 } 2482 2483 // Nothing to scavenge, delay for a while 2484 scavenge_counter_ = kDefaultReleaseDelay; 2485} 2486#endif 2487 2488void TCMalloc_PageHeap::RegisterSizeClass(Span* span, size_t sc) { 2489 // Associate span object with all interior pages as well 2490 ASSERT(!span->free); 2491 ASSERT(GetDescriptor(span->start) == span); 2492 ASSERT(GetDescriptor(span->start+span->length-1) == span); 2493 Event(span, 'C', sc); 2494 span->sizeclass = static_cast<unsigned int>(sc); 2495 for (Length i = 1; i < span->length-1; i++) { 2496 pagemap_.set(span->start+i, span); 2497 } 2498} 2499 2500#ifdef WTF_CHANGES 2501size_t TCMalloc_PageHeap::ReturnedBytes() const { 2502 ASSERT(kPageShift && kNumClasses && kPageSize); 2503 size_t result = 0; 2504 for (unsigned s = 0; s < kMaxPages; s++) { 2505 const int r_length = DLL_Length(&free_[s].returned, entropy_); 2506 unsigned r_pages = s * r_length; 2507 result += r_pages << kPageShift; 2508 } 2509 2510 for (Span* s = large_.returned.next(entropy_); s != &large_.returned; s = s->next(entropy_)) 2511 result += s->length << kPageShift; 2512 return result; 2513} 2514#endif 2515 2516#ifndef WTF_CHANGES 2517static double PagesToMB(uint64_t pages) { 2518 ASSERT(kPageShift && kNumClasses && kPageSize); 2519 return (pages << kPageShift) / 1048576.0; 2520} 2521 2522void TCMalloc_PageHeap::Dump(TCMalloc_Printer* out) { 2523 int nonempty_sizes = 0; 2524 for (int s = 0; s < kMaxPages; s++) { 2525 if (!DLL_IsEmpty(&free_[s].normal) || !DLL_IsEmpty(&free_[s].returned)) { 2526 nonempty_sizes++; 2527 } 2528 } 2529 out->printf("------------------------------------------------\n"); 2530 out->printf("PageHeap: %d sizes; %6.1f MB free\n", 2531 nonempty_sizes, PagesToMB(free_pages_)); 2532 out->printf("------------------------------------------------\n"); 2533 uint64_t total_normal = 0; 2534 uint64_t total_returned = 0; 2535 for (int s = 0; s < kMaxPages; s++) { 2536 const int n_length = DLL_Length(&free_[s].normal); 2537 const int r_length = DLL_Length(&free_[s].returned); 2538 if (n_length + r_length > 0) { 2539 uint64_t n_pages = s * n_length; 2540 uint64_t r_pages = s * r_length; 2541 total_normal += n_pages; 2542 total_returned += r_pages; 2543 out->printf("%6u pages * %6u spans ~ %6.1f MB; %6.1f MB cum" 2544 "; unmapped: %6.1f MB; %6.1f MB cum\n", 2545 s, 2546 (n_length + r_length), 2547 PagesToMB(n_pages + r_pages), 2548 PagesToMB(total_normal + total_returned), 2549 PagesToMB(r_pages), 2550 PagesToMB(total_returned)); 2551 } 2552 } 2553 2554 uint64_t n_pages = 0; 2555 uint64_t r_pages = 0; 2556 int n_spans = 0; 2557 int r_spans = 0; 2558 out->printf("Normal large spans:\n"); 2559 for (Span* s = large_.normal.next; s != &large_.normal; s = s->next) { 2560 out->printf(" [ %6" PRIuS " pages ] %6.1f MB\n", 2561 s->length, PagesToMB(s->length)); 2562 n_pages += s->length; 2563 n_spans++; 2564 } 2565 out->printf("Unmapped large spans:\n"); 2566 for (Span* s = large_.returned.next; s != &large_.returned; s = s->next) { 2567 out->printf(" [ %6" PRIuS " pages ] %6.1f MB\n", 2568 s->length, PagesToMB(s->length)); 2569 r_pages += s->length; 2570 r_spans++; 2571 } 2572 total_normal += n_pages; 2573 total_returned += r_pages; 2574 out->printf(">255 large * %6u spans ~ %6.1f MB; %6.1f MB cum" 2575 "; unmapped: %6.1f MB; %6.1f MB cum\n", 2576 (n_spans + r_spans), 2577 PagesToMB(n_pages + r_pages), 2578 PagesToMB(total_normal + total_returned), 2579 PagesToMB(r_pages), 2580 PagesToMB(total_returned)); 2581} 2582#endif 2583 2584bool TCMalloc_PageHeap::GrowHeap(Length n) { 2585 ASSERT(kPageShift && kNumClasses && kPageSize); 2586 ASSERT(kMaxPages >= kMinSystemAlloc); 2587 if (n > kMaxValidPages) return false; 2588 Length ask = (n>kMinSystemAlloc) ? n : static_cast<Length>(kMinSystemAlloc); 2589 size_t actual_size; 2590 void* ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize); 2591 if (ptr == NULL) { 2592 if (n < ask) { 2593 // Try growing just "n" pages 2594 ask = n; 2595 ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize); 2596 } 2597 if (ptr == NULL) return false; 2598 } 2599 ask = actual_size >> kPageShift; 2600 2601 uint64_t old_system_bytes = system_bytes_; 2602 system_bytes_ += (ask << kPageShift); 2603 const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift; 2604 ASSERT(p > 0); 2605 2606 // If we have already a lot of pages allocated, just pre allocate a bunch of 2607 // memory for the page map. This prevents fragmentation by pagemap metadata 2608 // when a program keeps allocating and freeing large blocks. 2609 2610 if (old_system_bytes < kPageMapBigAllocationThreshold 2611 && system_bytes_ >= kPageMapBigAllocationThreshold) { 2612 pagemap_.PreallocateMoreMemory(); 2613 } 2614 2615 // Make sure pagemap_ has entries for all of the new pages. 2616 // Plus ensure one before and one after so coalescing code 2617 // does not need bounds-checking. 2618 if (pagemap_.Ensure(p-1, ask+2)) { 2619 // Pretend the new area is allocated and then Delete() it to 2620 // cause any necessary coalescing to occur. 2621 // 2622 // We do not adjust free_pages_ here since Delete() will do it for us. 2623 Span* span = NewSpan(p, ask); 2624 RecordSpan(span); 2625 Delete(span); 2626 ASSERT(Check()); 2627 return true; 2628 } else { 2629 // We could not allocate memory within "pagemap_" 2630 // TODO: Once we can return memory to the system, return the new span 2631 return false; 2632 } 2633} 2634 2635bool TCMalloc_PageHeap::Check() { 2636#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2637 size_t totalFreeCommitted = 0; 2638#endif 2639 ASSERT(free_[0].normal.next(entropy_) == &free_[0].normal); 2640 ASSERT(free_[0].returned.next(entropy_) == &free_[0].returned); 2641#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2642 totalFreeCommitted = CheckList(&large_.normal, kMaxPages, 1000000000, false); 2643#else 2644 CheckList(&large_.normal, kMaxPages, 1000000000, false); 2645#endif 2646 CheckList(&large_.returned, kMaxPages, 1000000000, true); 2647 for (Length s = 1; s < kMaxPages; s++) { 2648#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2649 totalFreeCommitted += CheckList(&free_[s].normal, s, s, false); 2650#else 2651 CheckList(&free_[s].normal, s, s, false); 2652#endif 2653 CheckList(&free_[s].returned, s, s, true); 2654 } 2655#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2656 ASSERT(totalFreeCommitted == free_committed_pages_); 2657#endif 2658 return true; 2659} 2660 2661#if ASSERT_DISABLED 2662size_t TCMalloc_PageHeap::CheckList(Span*, Length, Length, bool) { 2663 return 0; 2664} 2665#else 2666size_t TCMalloc_PageHeap::CheckList(Span* list, Length min_pages, Length max_pages, bool decommitted) { 2667 size_t freeCount = 0; 2668 for (Span* s = list->next(entropy_); s != list; s = s->next(entropy_)) { 2669 CHECK_CONDITION(s->free); 2670 CHECK_CONDITION(s->length >= min_pages); 2671 CHECK_CONDITION(s->length <= max_pages); 2672 CHECK_CONDITION(GetDescriptor(s->start) == s); 2673 CHECK_CONDITION(GetDescriptor(s->start+s->length-1) == s); 2674 CHECK_CONDITION(s->decommitted == decommitted); 2675 freeCount += s->length; 2676 } 2677 return freeCount; 2678} 2679#endif 2680 2681void TCMalloc_PageHeap::ReleaseFreeList(Span* list, Span* returned) { 2682 ASSERT(kPageShift && kNumClasses && kPageSize); 2683 // Walk backwards through list so that when we push these 2684 // spans on the "returned" list, we preserve the order. 2685#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2686 size_t freePageReduction = 0; 2687#endif 2688 2689 while (!DLL_IsEmpty(list, entropy_)) { 2690 Span* s = list->prev(entropy_); 2691 2692 DLL_Remove(s, entropy_); 2693 s->decommitted = true; 2694 DLL_Prepend(returned, s, entropy_); 2695 TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift), 2696 static_cast<size_t>(s->length << kPageShift)); 2697#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2698 freePageReduction += s->length; 2699#endif 2700 } 2701 2702#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2703 free_committed_pages_ -= freePageReduction; 2704 if (free_committed_pages_ < min_free_committed_pages_since_last_scavenge_) 2705 min_free_committed_pages_since_last_scavenge_ = free_committed_pages_; 2706#endif 2707} 2708 2709void TCMalloc_PageHeap::ReleaseFreePages() { 2710 for (Length s = 0; s < kMaxPages; s++) { 2711 ReleaseFreeList(&free_[s].normal, &free_[s].returned); 2712 } 2713 ReleaseFreeList(&large_.normal, &large_.returned); 2714 ASSERT(Check()); 2715} 2716 2717//------------------------------------------------------------------- 2718// Free list 2719//------------------------------------------------------------------- 2720 2721class TCMalloc_ThreadCache_FreeList { 2722 private: 2723 HardenedSLL list_; // Linked list of nodes 2724 uint16_t length_; // Current length 2725 uint16_t lowater_; // Low water mark for list length 2726 uintptr_t entropy_; // Entropy source for hardening 2727 2728 public: 2729 void Init(uintptr_t entropy) { 2730 list_.setValue(NULL); 2731 length_ = 0; 2732 lowater_ = 0; 2733 entropy_ = entropy; 2734#if ENABLE(TCMALLOC_HARDENING) 2735 ASSERT(entropy_); 2736#endif 2737 } 2738 2739 // Return current length of list 2740 int length() const { 2741 return length_; 2742 } 2743 2744 // Is list empty? 2745 bool empty() const { 2746 return !list_; 2747 } 2748 2749 // Low-water mark management 2750 int lowwatermark() const { return lowater_; } 2751 void clear_lowwatermark() { lowater_ = length_; } 2752 2753 ALWAYS_INLINE void Push(HardenedSLL ptr) { 2754 SLL_Push(&list_, ptr, entropy_); 2755 length_++; 2756 } 2757 2758 void PushRange(int N, HardenedSLL start, HardenedSLL end) { 2759 SLL_PushRange(&list_, start, end, entropy_); 2760 length_ = length_ + static_cast<uint16_t>(N); 2761 } 2762 2763 void PopRange(int N, HardenedSLL* start, HardenedSLL* end) { 2764 SLL_PopRange(&list_, N, start, end, entropy_); 2765 ASSERT(length_ >= N); 2766 length_ = length_ - static_cast<uint16_t>(N); 2767 if (length_ < lowater_) lowater_ = length_; 2768 } 2769 2770 ALWAYS_INLINE void* Pop() { 2771 ASSERT(list_); 2772 length_--; 2773 if (length_ < lowater_) lowater_ = length_; 2774 return SLL_Pop(&list_, entropy_).value(); 2775 } 2776 2777 // Runs through the linked list to ensure that 2778 // we can do that, and ensures that 'missing' 2779 // is not present 2780 NEVER_INLINE void Validate(HardenedSLL missing, size_t size) { 2781 HardenedSLL node = list_; 2782 UNUSED_PARAM(size); 2783 while (node) { 2784 RELEASE_ASSERT(node != missing); 2785 RELEASE_ASSERT(IS_DEFINITELY_POISONED(node.value(), size)); 2786 node = SLL_Next(node, entropy_); 2787 } 2788 } 2789 2790#ifdef WTF_CHANGES 2791 template <class Finder, class Reader> 2792 void enumerateFreeObjects(Finder& finder, const Reader& reader) 2793 { 2794 for (HardenedSLL nextObject = list_; nextObject; nextObject.setValue(reader.nextEntryInHardenedLinkedList(reinterpret_cast<void**>(nextObject.value()), entropy_))) 2795 finder.visit(nextObject.value()); 2796 } 2797#endif 2798}; 2799 2800//------------------------------------------------------------------- 2801// Data kept per thread 2802//------------------------------------------------------------------- 2803 2804class TCMalloc_ThreadCache { 2805 private: 2806 typedef TCMalloc_ThreadCache_FreeList FreeList; 2807#if OS(WINDOWS) 2808 typedef DWORD ThreadIdentifier; 2809#else 2810 typedef pthread_t ThreadIdentifier; 2811#endif 2812 2813 size_t size_; // Combined size of data 2814 ThreadIdentifier tid_; // Which thread owns it 2815 bool in_setspecific_; // Called pthread_setspecific? 2816 FreeList list_[K_NUM_CLASSES_MAX]; // Array indexed by size-class 2817 2818 // We sample allocations, biased by the size of the allocation 2819 uint32_t rnd_; // Cheap random number generator 2820 size_t bytes_until_sample_; // Bytes until we sample next 2821 2822 uintptr_t entropy_; // Entropy value used for hardening 2823 2824 // Allocate a new heap. REQUIRES: pageheap_lock is held. 2825 static inline TCMalloc_ThreadCache* NewHeap(ThreadIdentifier tid, uintptr_t entropy); 2826 2827 // Use only as pthread thread-specific destructor function. 2828 static void DestroyThreadCache(void* ptr); 2829 public: 2830 // All ThreadCache objects are kept in a linked list (for stats collection) 2831 TCMalloc_ThreadCache* next_; 2832 TCMalloc_ThreadCache* prev_; 2833 2834 void Init(ThreadIdentifier tid, uintptr_t entropy); 2835 void Cleanup(); 2836 2837 // Accessors (mostly just for printing stats) 2838 int freelist_length(size_t cl) const { return list_[cl].length(); } 2839 2840 // Total byte size in cache 2841 size_t Size() const { return size_; } 2842 2843 ALWAYS_INLINE void* Allocate(size_t size); 2844 void Deallocate(HardenedSLL ptr, size_t size_class); 2845 2846 ALWAYS_INLINE void FetchFromCentralCache(size_t cl, size_t allocationSize); 2847 void ReleaseToCentralCache(size_t cl, int N); 2848 void Scavenge(); 2849 void Print() const; 2850 2851 // Record allocation of "k" bytes. Return true iff allocation 2852 // should be sampled 2853 bool SampleAllocation(size_t k); 2854 2855 // Pick next sampling point 2856 void PickNextSample(size_t k); 2857 2858 static void InitModule(); 2859 static void InitTSD(); 2860 static TCMalloc_ThreadCache* GetThreadHeap(); 2861 static TCMalloc_ThreadCache* GetCache(); 2862 static TCMalloc_ThreadCache* GetCacheIfPresent(); 2863 static TCMalloc_ThreadCache* CreateCacheIfNecessary(); 2864 static void DeleteCache(TCMalloc_ThreadCache* heap); 2865 static void BecomeIdle(); 2866 static void RecomputeThreadCacheSize(); 2867 2868#ifdef WTF_CHANGES 2869 template <class Finder, class Reader> 2870 void enumerateFreeObjects(Finder& finder, const Reader& reader) 2871 { 2872 ASSERT(kPageShift && kNumClasses && kPageSize); 2873 for (unsigned sizeClass = 0; sizeClass < kNumClasses; sizeClass++) 2874 list_[sizeClass].enumerateFreeObjects(finder, reader); 2875 } 2876#endif 2877}; 2878 2879//------------------------------------------------------------------- 2880// Global variables 2881//------------------------------------------------------------------- 2882 2883// Central cache -- a collection of free-lists, one per size-class. 2884// We have a separate lock per free-list to reduce contention. 2885static TCMalloc_Central_FreeListPadded central_cache[K_NUM_CLASSES_MAX]; 2886 2887// Page-level allocator 2888static AllocAlignmentInteger pageheap_memory[(sizeof(TCMalloc_PageHeap) + sizeof(AllocAlignmentInteger) - 1) / sizeof(AllocAlignmentInteger)]; 2889static bool phinited = false; 2890 2891// Avoid extra level of indirection by making "pageheap" be just an alias 2892// of pageheap_memory. 2893typedef union { 2894 void* m_memory; 2895 TCMalloc_PageHeap* m_pageHeap; 2896} PageHeapUnion; 2897 2898static inline TCMalloc_PageHeap* getPageHeap() 2899{ 2900 PageHeapUnion u = { &pageheap_memory[0] }; 2901 return u.m_pageHeap; 2902} 2903 2904#define pageheap getPageHeap() 2905 2906size_t fastMallocGoodSize(size_t bytes) 2907{ 2908 if (!phinited) 2909 TCMalloc_ThreadCache::InitModule(); 2910 return AllocationSize(bytes); 2911} 2912 2913#if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 2914 2915#if HAVE(DISPATCH_H) || OS(WINDOWS) 2916 2917void TCMalloc_PageHeap::periodicScavenge() 2918{ 2919 SpinLockHolder h(&pageheap_lock); 2920 pageheap->scavenge(); 2921 2922 if (shouldScavenge()) { 2923 rescheduleScavenger(); 2924 return; 2925 } 2926 2927 suspendScavenger(); 2928} 2929 2930ALWAYS_INLINE void TCMalloc_PageHeap::signalScavenger() 2931{ 2932 ASSERT(pageheap_lock.IsHeld()); 2933 if (isScavengerSuspended() && shouldScavenge()) 2934 scheduleScavenger(); 2935} 2936 2937#else 2938 2939void TCMalloc_PageHeap::scavengerThread() 2940{ 2941#if HAVE(PTHREAD_SETNAME_NP) 2942 pthread_setname_np("JavaScriptCore: FastMalloc scavenger"); 2943#endif 2944 2945 while (1) { 2946 pageheap_lock.Lock(); 2947 if (!shouldScavenge()) { 2948 // Set to false so that signalScavenger() will check whether we need to be siganlled. 2949 m_scavengeThreadActive = false; 2950 2951 // We need to unlock now, as this thread will block on the condvar until scavenging is required. 2952 pageheap_lock.Unlock(); 2953 2954 // Block until there are enough free committed pages to release back to the system. 2955 pthread_mutex_lock(&m_scavengeMutex); 2956 pthread_cond_wait(&m_scavengeCondition, &m_scavengeMutex); 2957 // After exiting the pthread_cond_wait, we hold the lock on m_scavengeMutex. Unlock it to prevent 2958 // deadlock next time round the loop. 2959 pthread_mutex_unlock(&m_scavengeMutex); 2960 2961 // Set to true to prevent unnecessary signalling of the condvar. 2962 m_scavengeThreadActive = true; 2963 } else 2964 pageheap_lock.Unlock(); 2965 2966 // Wait for a while to calculate how much memory remains unused during this pause. 2967 sleep(kScavengeDelayInSeconds); 2968 2969 { 2970 SpinLockHolder h(&pageheap_lock); 2971 pageheap->scavenge(); 2972 } 2973 } 2974} 2975 2976#endif 2977 2978#endif 2979 2980// If TLS is available, we also store a copy 2981// of the per-thread object in a __thread variable 2982// since __thread variables are faster to read 2983// than pthread_getspecific(). We still need 2984// pthread_setspecific() because __thread 2985// variables provide no way to run cleanup 2986// code when a thread is destroyed. 2987#ifdef HAVE_TLS 2988static __thread TCMalloc_ThreadCache *threadlocal_heap; 2989#endif 2990// Thread-specific key. Initialization here is somewhat tricky 2991// because some Linux startup code invokes malloc() before it 2992// is in a good enough state to handle pthread_keycreate(). 2993// Therefore, we use TSD keys only after tsd_inited is set to true. 2994// Until then, we use a slow path to get the heap object. 2995static bool tsd_inited = false; 2996#if USE(PTHREAD_GETSPECIFIC_DIRECT) 2997static const pthread_key_t heap_key = __PTK_FRAMEWORK_JAVASCRIPTCORE_KEY0; 2998#else 2999static ThreadSpecificKey heap_key; 3000#endif 3001 3002static ALWAYS_INLINE void setThreadHeap(TCMalloc_ThreadCache* heap) 3003{ 3004#if USE(PTHREAD_GETSPECIFIC_DIRECT) 3005 // Can't have two libraries both doing this in the same process, 3006 // so check and make this crash right away. 3007 if (pthread_getspecific(heap_key)) 3008 CRASH(); 3009#endif 3010 3011#if OS(DARWIN) 3012 // Still do pthread_setspecific even if there's an alternate form 3013 // of thread-local storage in use, to benefit from the delete callback. 3014 pthread_setspecific(heap_key, heap); 3015#else 3016 threadSpecificSet(heap_key, heap); 3017#endif 3018} 3019 3020// Allocator for thread heaps 3021static PageHeapAllocator<TCMalloc_ThreadCache> threadheap_allocator; 3022 3023// Linked list of heap objects. Protected by pageheap_lock. 3024static TCMalloc_ThreadCache* thread_heaps = NULL; 3025static int thread_heap_count = 0; 3026 3027// Overall thread cache size. Protected by pageheap_lock. 3028static size_t overall_thread_cache_size = kDefaultOverallThreadCacheSize; 3029 3030// Global per-thread cache size. Writes are protected by 3031// pageheap_lock. Reads are done without any locking, which should be 3032// fine as long as size_t can be written atomically and we don't place 3033// invariants between this variable and other pieces of state. 3034static volatile size_t per_thread_cache_size = kMaxThreadCacheSize; 3035 3036//------------------------------------------------------------------- 3037// Central cache implementation 3038//------------------------------------------------------------------- 3039 3040void TCMalloc_Central_FreeList::Init(size_t cl, uintptr_t entropy) { 3041 ASSERT(kPageShift && kNumClasses && kPageSize); 3042 lock_.Init(); 3043 size_class_ = cl; 3044 entropy_ = entropy; 3045#if ENABLE(TCMALLOC_HARDENING) 3046 ASSERT(entropy_); 3047#endif 3048 DLL_Init(&empty_, entropy_); 3049 DLL_Init(&nonempty_, entropy_); 3050 counter_ = 0; 3051 3052 cache_size_ = 1; 3053 used_slots_ = 0; 3054 ASSERT(cache_size_ <= kNumTransferEntries); 3055} 3056 3057void TCMalloc_Central_FreeList::ReleaseListToSpans(HardenedSLL start) { 3058 while (start) { 3059 HardenedSLL next = SLL_Next(start, entropy_); 3060 ReleaseToSpans(start); 3061 start = next; 3062 } 3063} 3064 3065ALWAYS_INLINE void TCMalloc_Central_FreeList::ReleaseToSpans(HardenedSLL object) { 3066 ASSERT(kPageShift && kNumClasses && kPageSize); 3067 const PageID p = reinterpret_cast<uintptr_t>(object.value()) >> kPageShift; 3068 Span* span = pageheap->GetDescriptor(p); 3069 ASSERT(span != NULL); 3070 ASSERT(span->refcount > 0); 3071 3072 // If span is empty, move it to non-empty list 3073 if (!span->objects) { 3074 DLL_Remove(span, entropy_); 3075 DLL_Prepend(&nonempty_, span, entropy_); 3076 Event(span, 'N', 0); 3077 } 3078 3079 // The following check is expensive, so it is disabled by default 3080 if (false) { 3081 // Check that object does not occur in list 3082 unsigned got = 0; 3083 for (HardenedSLL p = span->objects; !p; SLL_Next(p, entropy_)) { 3084 ASSERT(p.value() != object.value()); 3085 got++; 3086 } 3087 ASSERT(got + span->refcount == 3088 (span->length<<kPageShift)/ByteSizeForClass(span->sizeclass)); 3089 } 3090 3091 counter_++; 3092 span->refcount--; 3093 if (span->refcount == 0) { 3094 Event(span, '#', 0); 3095 counter_ -= (span->length<<kPageShift) / ByteSizeForClass(span->sizeclass); 3096 DLL_Remove(span, entropy_); 3097 3098 // Release central list lock while operating on pageheap 3099 lock_.Unlock(); 3100 { 3101 SpinLockHolder h(&pageheap_lock); 3102 pageheap->Delete(span); 3103 } 3104 lock_.Lock(); 3105 } else { 3106 SLL_SetNext(object, span->objects, entropy_); 3107 span->objects.setValue(object.value()); 3108 } 3109} 3110 3111ALWAYS_INLINE bool TCMalloc_Central_FreeList::EvictRandomSizeClass( 3112 size_t locked_size_class, bool force) { 3113 ASSERT(kPageShift && kNumClasses && kPageSize); 3114 static int race_counter = 0; 3115 int t = race_counter++; // Updated without a lock, but who cares. 3116 if (t >= static_cast<int>(kNumClasses)) { 3117 while (t >= static_cast<int>(kNumClasses)) { 3118 t -= kNumClasses; 3119 } 3120 race_counter = t; 3121 } 3122 ASSERT(t >= 0); 3123 ASSERT(t < static_cast<int>(kNumClasses)); 3124 if (t == static_cast<int>(locked_size_class)) return false; 3125 return central_cache[t].ShrinkCache(static_cast<int>(locked_size_class), force); 3126} 3127 3128bool TCMalloc_Central_FreeList::MakeCacheSpace() { 3129 ASSERT(kPageShift && kNumClasses && kPageSize); 3130 // Is there room in the cache? 3131 if (used_slots_ < cache_size_) return true; 3132 // Check if we can expand this cache? 3133 if (cache_size_ == kNumTransferEntries) return false; 3134 // Ok, we'll try to grab an entry from some other size class. 3135 if (EvictRandomSizeClass(size_class_, false) || 3136 EvictRandomSizeClass(size_class_, true)) { 3137 // Succeeded in evicting, we're going to make our cache larger. 3138 cache_size_++; 3139 return true; 3140 } 3141 return false; 3142} 3143 3144 3145namespace { 3146class LockInverter { 3147 private: 3148 SpinLock *held_, *temp_; 3149 public: 3150 inline explicit LockInverter(SpinLock* held, SpinLock *temp) 3151 : held_(held), temp_(temp) { held_->Unlock(); temp_->Lock(); } 3152 inline ~LockInverter() { temp_->Unlock(); held_->Lock(); } 3153}; 3154} 3155 3156bool TCMalloc_Central_FreeList::ShrinkCache(int locked_size_class, bool force) { 3157 // Start with a quick check without taking a lock. 3158 if (cache_size_ == 0) return false; 3159 // We don't evict from a full cache unless we are 'forcing'. 3160 if (force == false && used_slots_ == cache_size_) return false; 3161 3162 // Grab lock, but first release the other lock held by this thread. We use 3163 // the lock inverter to ensure that we never hold two size class locks 3164 // concurrently. That can create a deadlock because there is no well 3165 // defined nesting order. 3166 LockInverter li(¢ral_cache[locked_size_class].lock_, &lock_); 3167 ASSERT(used_slots_ <= cache_size_); 3168 ASSERT(0 <= cache_size_); 3169 if (cache_size_ == 0) return false; 3170 if (used_slots_ == cache_size_) { 3171 if (force == false) return false; 3172 // ReleaseListToSpans releases the lock, so we have to make all the 3173 // updates to the central list before calling it. 3174 cache_size_--; 3175 used_slots_--; 3176 ReleaseListToSpans(tc_slots_[used_slots_].head); 3177 return true; 3178 } 3179 cache_size_--; 3180 return true; 3181} 3182 3183void TCMalloc_Central_FreeList::InsertRange(HardenedSLL start, HardenedSLL end, int N) { 3184 ASSERT(kPageShift && kNumClasses && kPageSize); 3185 SpinLockHolder h(&lock_); 3186 if (N == num_objects_to_move[size_class_] && 3187 MakeCacheSpace()) { 3188 int slot = used_slots_++; 3189 ASSERT(slot >=0); 3190 ASSERT(slot < kNumTransferEntries); 3191 TCEntry *entry = &tc_slots_[slot]; 3192 entry->head = start; 3193 entry->tail = end; 3194 return; 3195 } 3196 ReleaseListToSpans(start); 3197} 3198 3199ALWAYS_INLINE void TCMalloc_Central_FreeList::RemoveRange(HardenedSLL* start, HardenedSLL* end, int *N) { 3200 int num = *N; 3201 ASSERT(num > 0); 3202 3203 SpinLockHolder h(&lock_); 3204 if (num == num_objects_to_move[size_class_] && used_slots_ > 0) { 3205 int slot = --used_slots_; 3206 ASSERT(slot >= 0); 3207 TCEntry *entry = &tc_slots_[slot]; 3208 *start = entry->head; 3209 *end = entry->tail; 3210 return; 3211 } 3212 3213 // TODO: Prefetch multiple TCEntries? 3214 HardenedSLL tail = FetchFromSpansSafe(); 3215 if (!tail) { 3216 // We are completely out of memory. 3217 *start = *end = HardenedSLL::null(); 3218 *N = 0; 3219 return; 3220 } 3221 3222 SLL_SetNext(tail, HardenedSLL::null(), entropy_); 3223 HardenedSLL head = tail; 3224 int count = 1; 3225 while (count < num) { 3226 HardenedSLL t = FetchFromSpans(); 3227 if (!t) break; 3228 SLL_Push(&head, t, entropy_); 3229 count++; 3230 } 3231 *start = head; 3232 *end = tail; 3233 *N = count; 3234} 3235 3236 3237ALWAYS_INLINE HardenedSLL TCMalloc_Central_FreeList::FetchFromSpansSafe() { 3238 HardenedSLL t = FetchFromSpans(); 3239 if (!t) { 3240 Populate(); 3241 t = FetchFromSpans(); 3242 } 3243 return t; 3244} 3245 3246HardenedSLL TCMalloc_Central_FreeList::FetchFromSpans() { 3247 if (DLL_IsEmpty(&nonempty_, entropy_)) return HardenedSLL::null(); 3248 Span* span = nonempty_.next(entropy_); 3249 3250 ASSERT(span->objects); 3251 ASSERT_SPAN_COMMITTED(span); 3252 span->refcount++; 3253 HardenedSLL result = span->objects; 3254 span->objects = SLL_Next(result, entropy_); 3255 if (!span->objects) { 3256 // Move to empty list 3257 DLL_Remove(span, entropy_); 3258 DLL_Prepend(&empty_, span, entropy_); 3259 Event(span, 'E', 0); 3260 } 3261 counter_--; 3262 return result; 3263} 3264 3265// Fetch memory from the system and add to the central cache freelist. 3266ALWAYS_INLINE void TCMalloc_Central_FreeList::Populate() { 3267 ASSERT(kPageShift && kNumClasses && kPageSize); 3268 // Release central list lock while operating on pageheap 3269 lock_.Unlock(); 3270 const size_t npages = class_to_pages[size_class_]; 3271 3272 Span* span; 3273 { 3274 SpinLockHolder h(&pageheap_lock); 3275 span = pageheap->New(npages); 3276 if (span) pageheap->RegisterSizeClass(span, size_class_); 3277 } 3278 if (span == NULL) { 3279#if HAVE(ERRNO_H) 3280 MESSAGE("allocation failed: %d\n", errno); 3281#elif OS(WINDOWS) 3282 MESSAGE("allocation failed: %d\n", ::GetLastError()); 3283#else 3284 MESSAGE("allocation failed\n"); 3285#endif 3286 lock_.Lock(); 3287 return; 3288 } 3289 ASSERT_SPAN_COMMITTED(span); 3290 ASSERT(span->length == npages); 3291 // Cache sizeclass info eagerly. Locking is not necessary. 3292 // (Instead of being eager, we could just replace any stale info 3293 // about this span, but that seems to be no better in practice.) 3294 for (size_t i = 0; i < npages; i++) { 3295 pageheap->CacheSizeClass(span->start + i, size_class_); 3296 } 3297 3298 // Split the block into pieces and add to the free-list 3299 // TODO: coloring of objects to avoid cache conflicts? 3300 HardenedSLL head = HardenedSLL::null(); 3301 char* start = reinterpret_cast<char*>(span->start << kPageShift); 3302 const size_t size = ByteSizeForClass(size_class_); 3303 char* ptr = start + (npages << kPageShift) - ((npages << kPageShift) % size); 3304 int num = 0; 3305#if ENABLE(TCMALLOC_HARDENING) 3306 uint32_t startPoison = freedObjectStartPoison(); 3307 uint32_t endPoison = freedObjectEndPoison(); 3308#endif 3309 3310 while (ptr > start) { 3311 ptr -= size; 3312 HardenedSLL node = HardenedSLL::create(ptr); 3313 POISON_DEALLOCATION_EXPLICIT(ptr, size, startPoison, endPoison); 3314 SLL_SetNext(node, head, entropy_); 3315 head = node; 3316 num++; 3317 } 3318 ASSERT(ptr == start); 3319 ASSERT(ptr == head.value()); 3320#ifndef NDEBUG 3321 { 3322 HardenedSLL node = head; 3323 while (node) { 3324 ASSERT(IS_DEFINITELY_POISONED(node.value(), size)); 3325 node = SLL_Next(node, entropy_); 3326 } 3327 } 3328#endif 3329 span->objects = head; 3330 ASSERT(span->objects.value() == head.value()); 3331 span->refcount = 0; // No sub-object in use yet 3332 3333 // Add span to list of non-empty spans 3334 lock_.Lock(); 3335 DLL_Prepend(&nonempty_, span, entropy_); 3336 counter_ += num; 3337} 3338 3339//------------------------------------------------------------------- 3340// TCMalloc_ThreadCache implementation 3341//------------------------------------------------------------------- 3342 3343inline bool TCMalloc_ThreadCache::SampleAllocation(size_t k) { 3344 if (bytes_until_sample_ < k) { 3345 PickNextSample(k); 3346 return true; 3347 } else { 3348 bytes_until_sample_ -= k; 3349 return false; 3350 } 3351} 3352 3353void TCMalloc_ThreadCache::Init(ThreadIdentifier tid, uintptr_t entropy) { 3354 ASSERT(kPageShift && kNumClasses && kPageSize); 3355 size_ = 0; 3356 next_ = NULL; 3357 prev_ = NULL; 3358 tid_ = tid; 3359 in_setspecific_ = false; 3360 entropy_ = entropy; 3361#if ENABLE(TCMALLOC_HARDENING) 3362 ASSERT(entropy_); 3363#endif 3364 for (size_t cl = 0; cl < kNumClasses; ++cl) { 3365 list_[cl].Init(entropy_); 3366 } 3367 3368 // Initialize RNG -- run it for a bit to get to good values 3369 bytes_until_sample_ = 0; 3370 rnd_ = static_cast<uint32_t>(reinterpret_cast<uintptr_t>(this)); 3371 for (int i = 0; i < 100; i++) { 3372 PickNextSample(static_cast<size_t>(FLAGS_tcmalloc_sample_parameter * 2)); 3373 } 3374} 3375 3376void TCMalloc_ThreadCache::Cleanup() { 3377 ASSERT(kPageShift && kNumClasses && kPageSize); 3378 // Put unused memory back into central cache 3379 for (size_t cl = 0; cl < kNumClasses; ++cl) { 3380 if (list_[cl].length() > 0) { 3381 ReleaseToCentralCache(cl, list_[cl].length()); 3382 } 3383 } 3384} 3385 3386ALWAYS_INLINE void* TCMalloc_ThreadCache::Allocate(size_t size) { 3387 ASSERT(size <= kMaxSize); 3388 const size_t cl = SizeClass(size); 3389 FreeList* list = &list_[cl]; 3390 size_t allocationSize = ByteSizeForClass(cl); 3391 if (list->empty()) { 3392 FetchFromCentralCache(cl, allocationSize); 3393 if (list->empty()) return NULL; 3394 } 3395 size_ -= allocationSize; 3396 void* result = list->Pop(); 3397 if (!result) 3398 return 0; 3399 RELEASE_ASSERT(IS_DEFINITELY_POISONED(result, allocationSize)); 3400 POISON_ALLOCATION(result, allocationSize); 3401 return result; 3402} 3403 3404inline void TCMalloc_ThreadCache::Deallocate(HardenedSLL ptr, size_t cl) { 3405 size_t allocationSize = ByteSizeForClass(cl); 3406 size_ += allocationSize; 3407 FreeList* list = &list_[cl]; 3408 if (MAY_BE_POISONED(ptr.value(), allocationSize)) 3409 list->Validate(ptr, allocationSize); 3410 3411 POISON_DEALLOCATION(ptr.value(), allocationSize); 3412 list->Push(ptr); 3413 // If enough data is free, put back into central cache 3414 if (list->length() > kMaxFreeListLength) { 3415 ReleaseToCentralCache(cl, num_objects_to_move[cl]); 3416 } 3417 if (size_ >= per_thread_cache_size) Scavenge(); 3418} 3419 3420// Remove some objects of class "cl" from central cache and add to thread heap 3421ALWAYS_INLINE void TCMalloc_ThreadCache::FetchFromCentralCache(size_t cl, size_t allocationSize) { 3422 int fetch_count = num_objects_to_move[cl]; 3423 HardenedSLL start, end; 3424 central_cache[cl].RemoveRange(&start, &end, &fetch_count); 3425 list_[cl].PushRange(fetch_count, start, end); 3426 size_ += allocationSize * fetch_count; 3427} 3428 3429// Remove some objects of class "cl" from thread heap and add to central cache 3430inline void TCMalloc_ThreadCache::ReleaseToCentralCache(size_t cl, int N) { 3431 ASSERT(N > 0); 3432 FreeList* src = &list_[cl]; 3433 if (N > src->length()) N = src->length(); 3434 size_ -= N*ByteSizeForClass(cl); 3435 3436 // We return prepackaged chains of the correct size to the central cache. 3437 // TODO: Use the same format internally in the thread caches? 3438 int batch_size = num_objects_to_move[cl]; 3439 while (N > batch_size) { 3440 HardenedSLL tail, head; 3441 src->PopRange(batch_size, &head, &tail); 3442 central_cache[cl].InsertRange(head, tail, batch_size); 3443 N -= batch_size; 3444 } 3445 HardenedSLL tail, head; 3446 src->PopRange(N, &head, &tail); 3447 central_cache[cl].InsertRange(head, tail, N); 3448} 3449 3450// Release idle memory to the central cache 3451inline void TCMalloc_ThreadCache::Scavenge() { 3452 ASSERT(kPageShift && kNumClasses && kPageSize); 3453 // If the low-water mark for the free list is L, it means we would 3454 // not have had to allocate anything from the central cache even if 3455 // we had reduced the free list size by L. We aim to get closer to 3456 // that situation by dropping L/2 nodes from the free list. This 3457 // may not release much memory, but if so we will call scavenge again 3458 // pretty soon and the low-water marks will be high on that call. 3459 //int64 start = CycleClock::Now(); 3460 3461 for (size_t cl = 0; cl < kNumClasses; cl++) { 3462 FreeList* list = &list_[cl]; 3463 const int lowmark = list->lowwatermark(); 3464 if (lowmark > 0) { 3465 const int drop = (lowmark > 1) ? lowmark/2 : 1; 3466 ReleaseToCentralCache(cl, drop); 3467 } 3468 list->clear_lowwatermark(); 3469 } 3470 3471 //int64 finish = CycleClock::Now(); 3472 //CycleTimer ct; 3473 //MESSAGE("GC: %.0f ns\n", ct.CyclesToUsec(finish-start)*1000.0); 3474} 3475 3476void TCMalloc_ThreadCache::PickNextSample(size_t k) { 3477 // Make next "random" number 3478 // x^32+x^22+x^2+x^1+1 is a primitive polynomial for random numbers 3479 static const uint32_t kPoly = (1 << 22) | (1 << 2) | (1 << 1) | (1 << 0); 3480 uint32_t r = rnd_; 3481 rnd_ = (r << 1) ^ ((static_cast<int32_t>(r) >> 31) & kPoly); 3482 3483 // Next point is "rnd_ % (sample_period)". I.e., average 3484 // increment is "sample_period/2". 3485 const int flag_value = static_cast<int>(FLAGS_tcmalloc_sample_parameter); 3486 static int last_flag_value = -1; 3487 3488 if (flag_value != last_flag_value) { 3489 SpinLockHolder h(&sample_period_lock); 3490 int i; 3491 for (i = 0; i < (static_cast<int>(sizeof(primes_list)/sizeof(primes_list[0])) - 1); i++) { 3492 if (primes_list[i] >= flag_value) { 3493 break; 3494 } 3495 } 3496 sample_period = primes_list[i]; 3497 last_flag_value = flag_value; 3498 } 3499 3500 bytes_until_sample_ += rnd_ % sample_period; 3501 3502 if (k > (static_cast<size_t>(-1) >> 2)) { 3503 // If the user has asked for a huge allocation then it is possible 3504 // for the code below to loop infinitely. Just return (note that 3505 // this throws off the sampling accuracy somewhat, but a user who 3506 // is allocating more than 1G of memory at a time can live with a 3507 // minor inaccuracy in profiling of small allocations, and also 3508 // would rather not wait for the loop below to terminate). 3509 return; 3510 } 3511 3512 while (bytes_until_sample_ < k) { 3513 // Increase bytes_until_sample_ by enough average sampling periods 3514 // (sample_period >> 1) to allow us to sample past the current 3515 // allocation. 3516 bytes_until_sample_ += (sample_period >> 1); 3517 } 3518 3519 bytes_until_sample_ -= k; 3520} 3521 3522void TCMalloc_ThreadCache::InitModule() { 3523 // There is a slight potential race here because of double-checked 3524 // locking idiom. However, as long as the program does a small 3525 // allocation before switching to multi-threaded mode, we will be 3526 // fine. We increase the chances of doing such a small allocation 3527 // by doing one in the constructor of the module_enter_exit_hook 3528 // object declared below. 3529 SpinLockHolder h(&pageheap_lock); 3530 if (!phinited) { 3531 uintptr_t entropy = HARDENING_ENTROPY; 3532#ifdef WTF_CHANGES 3533 InitTSD(); 3534#endif 3535 InitSizeClasses(); 3536 threadheap_allocator.Init(entropy); 3537 span_allocator.Init(entropy); 3538 span_allocator.New(); // Reduce cache conflicts 3539 span_allocator.New(); // Reduce cache conflicts 3540 stacktrace_allocator.Init(entropy); 3541 DLL_Init(&sampled_objects, entropy); 3542 for (size_t i = 0; i < kNumClasses; ++i) { 3543 central_cache[i].Init(i, entropy); 3544 } 3545 pageheap->init(); 3546 phinited = 1; 3547#if defined(WTF_CHANGES) && OS(DARWIN) 3548 MallocHook::init(); 3549 FastMallocZone::init(); 3550#endif 3551 } 3552} 3553 3554inline TCMalloc_ThreadCache* TCMalloc_ThreadCache::NewHeap(ThreadIdentifier tid, uintptr_t entropy) { 3555 // Create the heap and add it to the linked list 3556 TCMalloc_ThreadCache *heap = threadheap_allocator.New(); 3557 heap->Init(tid, entropy); 3558 heap->next_ = thread_heaps; 3559 heap->prev_ = NULL; 3560 if (thread_heaps != NULL) thread_heaps->prev_ = heap; 3561 thread_heaps = heap; 3562 thread_heap_count++; 3563 RecomputeThreadCacheSize(); 3564 return heap; 3565} 3566 3567inline TCMalloc_ThreadCache* TCMalloc_ThreadCache::GetThreadHeap() { 3568#ifdef HAVE_TLS 3569 // __thread is faster, but only when the kernel supports it 3570 if (KernelSupportsTLS()) 3571 return threadlocal_heap; 3572#elif OS(DARWIN) 3573 return static_cast<TCMalloc_ThreadCache*>(pthread_getspecific(heap_key)); 3574#else 3575 return static_cast<TCMalloc_ThreadCache*>(threadSpecificGet(heap_key)); 3576#endif 3577} 3578 3579inline TCMalloc_ThreadCache* TCMalloc_ThreadCache::GetCache() { 3580 TCMalloc_ThreadCache* ptr = NULL; 3581 if (!tsd_inited) { 3582 InitModule(); 3583 } else { 3584 ptr = GetThreadHeap(); 3585 } 3586 if (ptr == NULL) ptr = CreateCacheIfNecessary(); 3587 return ptr; 3588} 3589 3590// In deletion paths, we do not try to create a thread-cache. This is 3591// because we may be in the thread destruction code and may have 3592// already cleaned up the cache for this thread. 3593inline TCMalloc_ThreadCache* TCMalloc_ThreadCache::GetCacheIfPresent() { 3594 if (!tsd_inited) return NULL; 3595 void* const p = GetThreadHeap(); 3596 return reinterpret_cast<TCMalloc_ThreadCache*>(p); 3597} 3598 3599void TCMalloc_ThreadCache::InitTSD() { 3600 ASSERT(!tsd_inited); 3601#if USE(PTHREAD_GETSPECIFIC_DIRECT) 3602 pthread_key_init_np(heap_key, DestroyThreadCache); 3603#else 3604 threadSpecificKeyCreate(&heap_key, DestroyThreadCache); 3605#endif 3606 tsd_inited = true; 3607 3608#if !OS(WINDOWS) 3609 // We may have used a fake pthread_t for the main thread. Fix it. 3610 pthread_t zero; 3611 memset(&zero, 0, sizeof(zero)); 3612#endif 3613#ifndef WTF_CHANGES 3614 SpinLockHolder h(&pageheap_lock); 3615#else 3616 ASSERT(pageheap_lock.IsHeld()); 3617#endif 3618 for (TCMalloc_ThreadCache* h = thread_heaps; h != NULL; h = h->next_) { 3619#if OS(WINDOWS) 3620 if (h->tid_ == 0) { 3621 h->tid_ = GetCurrentThreadId(); 3622 } 3623#else 3624 if (pthread_equal(h->tid_, zero)) { 3625 h->tid_ = pthread_self(); 3626 } 3627#endif 3628 } 3629} 3630 3631TCMalloc_ThreadCache* TCMalloc_ThreadCache::CreateCacheIfNecessary() { 3632 // Initialize per-thread data if necessary 3633 TCMalloc_ThreadCache* heap = NULL; 3634 { 3635 SpinLockHolder h(&pageheap_lock); 3636 3637#if OS(WINDOWS) 3638 DWORD me; 3639 if (!tsd_inited) { 3640 me = 0; 3641 } else { 3642 me = GetCurrentThreadId(); 3643 } 3644#else 3645 // Early on in glibc's life, we cannot even call pthread_self() 3646 pthread_t me; 3647 if (!tsd_inited) { 3648 memset(&me, 0, sizeof(me)); 3649 } else { 3650 me = pthread_self(); 3651 } 3652#endif 3653 3654 // This may be a recursive malloc call from pthread_setspecific() 3655 // In that case, the heap for this thread has already been created 3656 // and added to the linked list. So we search for that first. 3657 for (TCMalloc_ThreadCache* h = thread_heaps; h != NULL; h = h->next_) { 3658#if OS(WINDOWS) 3659 if (h->tid_ == me) { 3660#else 3661 if (pthread_equal(h->tid_, me)) { 3662#endif 3663 heap = h; 3664 break; 3665 } 3666 } 3667 3668 if (heap == NULL) heap = NewHeap(me, HARDENING_ENTROPY); 3669 } 3670 3671 // We call pthread_setspecific() outside the lock because it may 3672 // call malloc() recursively. The recursive call will never get 3673 // here again because it will find the already allocated heap in the 3674 // linked list of heaps. 3675 if (!heap->in_setspecific_ && tsd_inited) { 3676 heap->in_setspecific_ = true; 3677 setThreadHeap(heap); 3678 } 3679 return heap; 3680} 3681 3682void TCMalloc_ThreadCache::BecomeIdle() { 3683 if (!tsd_inited) return; // No caches yet 3684 TCMalloc_ThreadCache* heap = GetThreadHeap(); 3685 if (heap == NULL) return; // No thread cache to remove 3686 if (heap->in_setspecific_) return; // Do not disturb the active caller 3687 3688 heap->in_setspecific_ = true; 3689 setThreadHeap(NULL); 3690#ifdef HAVE_TLS 3691 // Also update the copy in __thread 3692 threadlocal_heap = NULL; 3693#endif 3694 heap->in_setspecific_ = false; 3695 if (GetThreadHeap() == heap) { 3696 // Somehow heap got reinstated by a recursive call to malloc 3697 // from pthread_setspecific. We give up in this case. 3698 return; 3699 } 3700 3701 // We can now get rid of the heap 3702 DeleteCache(heap); 3703} 3704 3705void TCMalloc_ThreadCache::DestroyThreadCache(void* ptr) { 3706 // Note that "ptr" cannot be NULL since pthread promises not 3707 // to invoke the destructor on NULL values, but for safety, 3708 // we check anyway. 3709 if (ptr == NULL) return; 3710#ifdef HAVE_TLS 3711 // Prevent fast path of GetThreadHeap() from returning heap. 3712 threadlocal_heap = NULL; 3713#endif 3714 DeleteCache(reinterpret_cast<TCMalloc_ThreadCache*>(ptr)); 3715} 3716 3717void TCMalloc_ThreadCache::DeleteCache(TCMalloc_ThreadCache* heap) { 3718 // Remove all memory from heap 3719 heap->Cleanup(); 3720 3721 // Remove from linked list 3722 SpinLockHolder h(&pageheap_lock); 3723 if (heap->next_ != NULL) heap->next_->prev_ = heap->prev_; 3724 if (heap->prev_ != NULL) heap->prev_->next_ = heap->next_; 3725 if (thread_heaps == heap) thread_heaps = heap->next_; 3726 thread_heap_count--; 3727 RecomputeThreadCacheSize(); 3728 3729 threadheap_allocator.Delete(heap); 3730} 3731 3732void TCMalloc_ThreadCache::RecomputeThreadCacheSize() { 3733 // Divide available space across threads 3734 int n = thread_heap_count > 0 ? thread_heap_count : 1; 3735 size_t space = overall_thread_cache_size / n; 3736 3737 // Limit to allowed range 3738 if (space < kMinThreadCacheSize) space = kMinThreadCacheSize; 3739 if (space > kMaxThreadCacheSize) space = kMaxThreadCacheSize; 3740 3741 per_thread_cache_size = space; 3742} 3743 3744void TCMalloc_ThreadCache::Print() const { 3745 ASSERT(kPageShift && kNumClasses && kPageSize); 3746 for (size_t cl = 0; cl < kNumClasses; ++cl) { 3747 MESSAGE(" %5" PRIuS " : %4d len; %4d lo\n", 3748 ByteSizeForClass(cl), 3749 list_[cl].length(), 3750 list_[cl].lowwatermark()); 3751 } 3752} 3753 3754// Extract interesting stats 3755struct TCMallocStats { 3756 uint64_t system_bytes; // Bytes alloced from system 3757 uint64_t thread_bytes; // Bytes in thread caches 3758 uint64_t central_bytes; // Bytes in central cache 3759 uint64_t transfer_bytes; // Bytes in central transfer cache 3760 uint64_t pageheap_bytes; // Bytes in page heap 3761 uint64_t metadata_bytes; // Bytes alloced for metadata 3762}; 3763 3764#ifndef WTF_CHANGES 3765// Get stats into "r". Also get per-size-class counts if class_count != NULL 3766static void ExtractStats(TCMallocStats* r, uint64_t* class_count) { 3767 ASSERT(kPageShift && kNumClasses && kPageSize); 3768 r->central_bytes = 0; 3769 r->transfer_bytes = 0; 3770 for (int cl = 0; cl < kNumClasses; ++cl) { 3771 const int length = central_cache[cl].length(); 3772 const int tc_length = central_cache[cl].tc_length(); 3773 r->central_bytes += static_cast<uint64_t>(ByteSizeForClass(cl)) * length; 3774 r->transfer_bytes += 3775 static_cast<uint64_t>(ByteSizeForClass(cl)) * tc_length; 3776 if (class_count) class_count[cl] = length + tc_length; 3777 } 3778 3779 // Add stats from per-thread heaps 3780 r->thread_bytes = 0; 3781 { // scope 3782 SpinLockHolder h(&pageheap_lock); 3783 for (TCMalloc_ThreadCache* h = thread_heaps; h != NULL; h = h->next_) { 3784 r->thread_bytes += h->Size(); 3785 if (class_count) { 3786 for (size_t cl = 0; cl < kNumClasses; ++cl) { 3787 class_count[cl] += h->freelist_length(cl); 3788 } 3789 } 3790 } 3791 } 3792 3793 { //scope 3794 SpinLockHolder h(&pageheap_lock); 3795 r->system_bytes = pageheap->SystemBytes(); 3796 r->metadata_bytes = metadata_system_bytes; 3797 r->pageheap_bytes = pageheap->FreeBytes(); 3798 } 3799} 3800#endif 3801 3802#ifndef WTF_CHANGES 3803// WRITE stats to "out" 3804static void DumpStats(TCMalloc_Printer* out, int level) { 3805 ASSERT(kPageShift && kNumClasses && kPageSize); 3806 TCMallocStats stats; 3807 uint64_t class_count[kNumClasses]; 3808 ExtractStats(&stats, (level >= 2 ? class_count : NULL)); 3809 3810 if (level >= 2) { 3811 out->printf("------------------------------------------------\n"); 3812 uint64_t cumulative = 0; 3813 for (int cl = 0; cl < kNumClasses; ++cl) { 3814 if (class_count[cl] > 0) { 3815 uint64_t class_bytes = class_count[cl] * ByteSizeForClass(cl); 3816 cumulative += class_bytes; 3817 out->printf("class %3d [ %8" PRIuS " bytes ] : " 3818 "%8" PRIu64 " objs; %5.1f MB; %5.1f cum MB\n", 3819 cl, ByteSizeForClass(cl), 3820 class_count[cl], 3821 class_bytes / 1048576.0, 3822 cumulative / 1048576.0); 3823 } 3824 } 3825 3826 SpinLockHolder h(&pageheap_lock); 3827 pageheap->Dump(out); 3828 } 3829 3830 const uint64_t bytes_in_use = stats.system_bytes 3831 - stats.pageheap_bytes 3832 - stats.central_bytes 3833 - stats.transfer_bytes 3834 - stats.thread_bytes; 3835 3836 out->printf("------------------------------------------------\n" 3837 "MALLOC: %12" PRIu64 " Heap size\n" 3838 "MALLOC: %12" PRIu64 " Bytes in use by application\n" 3839 "MALLOC: %12" PRIu64 " Bytes free in page heap\n" 3840 "MALLOC: %12" PRIu64 " Bytes free in central cache\n" 3841 "MALLOC: %12" PRIu64 " Bytes free in transfer cache\n" 3842 "MALLOC: %12" PRIu64 " Bytes free in thread caches\n" 3843 "MALLOC: %12" PRIu64 " Spans in use\n" 3844 "MALLOC: %12" PRIu64 " Thread heaps in use\n" 3845 "MALLOC: %12" PRIu64 " Metadata allocated\n" 3846 "------------------------------------------------\n", 3847 stats.system_bytes, 3848 bytes_in_use, 3849 stats.pageheap_bytes, 3850 stats.central_bytes, 3851 stats.transfer_bytes, 3852 stats.thread_bytes, 3853 uint64_t(span_allocator.inuse()), 3854 uint64_t(threadheap_allocator.inuse()), 3855 stats.metadata_bytes); 3856} 3857 3858static void PrintStats(int level) { 3859 const int kBufferSize = 16 << 10; 3860 char* buffer = new char[kBufferSize]; 3861 TCMalloc_Printer printer(buffer, kBufferSize); 3862 DumpStats(&printer, level); 3863 write(STDERR_FILENO, buffer, strlen(buffer)); 3864 delete[] buffer; 3865} 3866 3867static void** DumpStackTraces() { 3868 // Count how much space we need 3869 int needed_slots = 0; 3870 { 3871 SpinLockHolder h(&pageheap_lock); 3872 for (Span* s = sampled_objects.next; s != &sampled_objects; s = s->next) { 3873 StackTrace* stack = reinterpret_cast<StackTrace*>(s->objects); 3874 needed_slots += 3 + stack->depth; 3875 } 3876 needed_slots += 100; // Slop in case sample grows 3877 needed_slots += needed_slots/8; // An extra 12.5% slop 3878 } 3879 3880 void** result = new void*[needed_slots]; 3881 if (result == NULL) { 3882 MESSAGE("tcmalloc: could not allocate %d slots for stack traces\n", 3883 needed_slots); 3884 return NULL; 3885 } 3886 3887 SpinLockHolder h(&pageheap_lock); 3888 int used_slots = 0; 3889 for (Span* s = sampled_objects.next; s != &sampled_objects; s = s->next) { 3890 ASSERT_WITH_SECURITY_IMPLICATION(used_slots < needed_slots); // Need to leave room for terminator 3891 StackTrace* stack = reinterpret_cast<StackTrace*>(s->objects); 3892 if (used_slots + 3 + stack->depth >= needed_slots) { 3893 // No more room 3894 break; 3895 } 3896 3897 result[used_slots+0] = reinterpret_cast<void*>(static_cast<uintptr_t>(1)); 3898 result[used_slots+1] = reinterpret_cast<void*>(stack->size); 3899 result[used_slots+2] = reinterpret_cast<void*>(stack->depth); 3900 for (int d = 0; d < stack->depth; d++) { 3901 result[used_slots+3+d] = stack->stack[d]; 3902 } 3903 used_slots += 3 + stack->depth; 3904 } 3905 result[used_slots] = reinterpret_cast<void*>(static_cast<uintptr_t>(0)); 3906 return result; 3907} 3908#endif 3909 3910#ifndef WTF_CHANGES 3911 3912// TCMalloc's support for extra malloc interfaces 3913class TCMallocImplementation : public MallocExtension { 3914 public: 3915 virtual void GetStats(char* buffer, int buffer_length) { 3916 ASSERT(buffer_length > 0); 3917 TCMalloc_Printer printer(buffer, buffer_length); 3918 3919 // Print level one stats unless lots of space is available 3920 if (buffer_length < 10000) { 3921 DumpStats(&printer, 1); 3922 } else { 3923 DumpStats(&printer, 2); 3924 } 3925 } 3926 3927 virtual void** ReadStackTraces() { 3928 return DumpStackTraces(); 3929 } 3930 3931 virtual bool GetNumericProperty(const char* name, size_t* value) { 3932 ASSERT(name != NULL); 3933 3934 if (strcmp(name, "generic.current_allocated_bytes") == 0) { 3935 TCMallocStats stats; 3936 ExtractStats(&stats, NULL); 3937 *value = stats.system_bytes 3938 - stats.thread_bytes 3939 - stats.central_bytes 3940 - stats.pageheap_bytes; 3941 return true; 3942 } 3943 3944 if (strcmp(name, "generic.heap_size") == 0) { 3945 TCMallocStats stats; 3946 ExtractStats(&stats, NULL); 3947 *value = stats.system_bytes; 3948 return true; 3949 } 3950 3951 if (strcmp(name, "tcmalloc.slack_bytes") == 0) { 3952 // We assume that bytes in the page heap are not fragmented too 3953 // badly, and are therefore available for allocation. 3954 SpinLockHolder l(&pageheap_lock); 3955 *value = pageheap->FreeBytes(); 3956 return true; 3957 } 3958 3959 if (strcmp(name, "tcmalloc.max_total_thread_cache_bytes") == 0) { 3960 SpinLockHolder l(&pageheap_lock); 3961 *value = overall_thread_cache_size; 3962 return true; 3963 } 3964 3965 if (strcmp(name, "tcmalloc.current_total_thread_cache_bytes") == 0) { 3966 TCMallocStats stats; 3967 ExtractStats(&stats, NULL); 3968 *value = stats.thread_bytes; 3969 return true; 3970 } 3971 3972 return false; 3973 } 3974 3975 virtual bool SetNumericProperty(const char* name, size_t value) { 3976 ASSERT(name != NULL); 3977 3978 if (strcmp(name, "tcmalloc.max_total_thread_cache_bytes") == 0) { 3979 // Clip the value to a reasonable range 3980 if (value < kMinThreadCacheSize) value = kMinThreadCacheSize; 3981 if (value > (1<<30)) value = (1<<30); // Limit to 1GB 3982 3983 SpinLockHolder l(&pageheap_lock); 3984 overall_thread_cache_size = static_cast<size_t>(value); 3985 TCMalloc_ThreadCache::RecomputeThreadCacheSize(); 3986 return true; 3987 } 3988 3989 return false; 3990 } 3991 3992 virtual void MarkThreadIdle() { 3993 TCMalloc_ThreadCache::BecomeIdle(); 3994 } 3995 3996 virtual void ReleaseFreeMemory() { 3997 SpinLockHolder h(&pageheap_lock); 3998 pageheap->ReleaseFreePages(); 3999 } 4000}; 4001#endif 4002 4003// The constructor allocates an object to ensure that initialization 4004// runs before main(), and therefore we do not have a chance to become 4005// multi-threaded before initialization. We also create the TSD key 4006// here. Presumably by the time this constructor runs, glibc is in 4007// good enough shape to handle pthread_key_create(). 4008// 4009// The constructor also takes the opportunity to tell STL to use 4010// tcmalloc. We want to do this early, before construct time, so 4011// all user STL allocations go through tcmalloc (which works really 4012// well for STL). 4013// 4014// The destructor prints stats when the program exits. 4015class TCMallocGuard { 4016 public: 4017 4018 TCMallocGuard() { 4019#ifdef HAVE_TLS // this is true if the cc/ld/libc combo support TLS 4020 // Check whether the kernel also supports TLS (needs to happen at runtime) 4021 CheckIfKernelSupportsTLS(); 4022#endif 4023#ifndef WTF_CHANGES 4024#ifdef WIN32 // patch the windows VirtualAlloc, etc. 4025 PatchWindowsFunctions(); // defined in windows/patch_functions.cc 4026#endif 4027#endif 4028 free(malloc(1)); 4029 TCMalloc_ThreadCache::InitTSD(); 4030 free(malloc(1)); 4031#ifndef WTF_CHANGES 4032 MallocExtension::Register(new TCMallocImplementation); 4033#endif 4034 } 4035 4036#ifndef WTF_CHANGES 4037 ~TCMallocGuard() { 4038 const char* env = getenv("MALLOCSTATS"); 4039 if (env != NULL) { 4040 int level = atoi(env); 4041 if (level < 1) level = 1; 4042 PrintStats(level); 4043 } 4044#ifdef WIN32 4045 UnpatchWindowsFunctions(); 4046#endif 4047 } 4048#endif 4049}; 4050 4051#ifndef WTF_CHANGES 4052static TCMallocGuard module_enter_exit_hook; 4053#endif 4054 4055 4056//------------------------------------------------------------------- 4057// Helpers for the exported routines below 4058//------------------------------------------------------------------- 4059 4060#ifndef WTF_CHANGES 4061 4062static Span* DoSampledAllocation(size_t size) { 4063 4064 // Grab the stack trace outside the heap lock 4065 StackTrace tmp; 4066 tmp.depth = GetStackTrace(tmp.stack, kMaxStackDepth, 1); 4067 tmp.size = size; 4068 4069 SpinLockHolder h(&pageheap_lock); 4070 // Allocate span 4071 Span *span = pageheap->New(pages(size == 0 ? 1 : size)); 4072 if (span == NULL) { 4073 return NULL; 4074 } 4075 4076 // Allocate stack trace 4077 StackTrace *stack = stacktrace_allocator.New(); 4078 if (stack == NULL) { 4079 // Sampling failed because of lack of memory 4080 return span; 4081 } 4082 4083 *stack = tmp; 4084 span->sample = 1; 4085 span->objects = stack; 4086 DLL_Prepend(&sampled_objects, span); 4087 4088 return span; 4089} 4090#endif 4091 4092#if !ASSERT_DISABLED 4093static inline bool CheckCachedSizeClass(void *ptr) { 4094 ASSERT(kPageShift && kNumClasses && kPageSize); 4095 PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift; 4096 size_t cached_value = pageheap->GetSizeClassIfCached(p); 4097 return cached_value == 0 || 4098 cached_value == pageheap->GetDescriptor(p)->sizeclass; 4099} 4100#endif 4101 4102static inline void* CheckedMallocResult(void *result) 4103{ 4104 ASSERT(result == 0 || CheckCachedSizeClass(result)); 4105 return result; 4106} 4107 4108static inline void* SpanToMallocResult(Span *span) { 4109 ASSERT(kPageShift && kNumClasses && kPageSize); 4110 ASSERT_SPAN_COMMITTED(span); 4111 pageheap->CacheSizeClass(span->start, 0); 4112 void* result = reinterpret_cast<void*>(span->start << kPageShift); 4113 POISON_ALLOCATION(result, span->length << kPageShift); 4114 return CheckedMallocResult(result); 4115} 4116 4117#ifdef WTF_CHANGES 4118template <bool crashOnFailure> 4119#endif 4120static ALWAYS_INLINE void* do_malloc(size_t size) { 4121 void* ret = NULL; 4122 4123#ifdef WTF_CHANGES 4124 ASSERT(!isForbidden()); 4125#endif 4126 4127 // The following call forces module initialization 4128 TCMalloc_ThreadCache* heap = TCMalloc_ThreadCache::GetCache(); 4129#ifndef WTF_CHANGES 4130 if ((FLAGS_tcmalloc_sample_parameter > 0) && heap->SampleAllocation(size)) { 4131 Span* span = DoSampledAllocation(size); 4132 if (span != NULL) { 4133 ret = SpanToMallocResult(span); 4134 } 4135 } else 4136#endif 4137 if (size > kMaxSize) { 4138 // Use page-level allocator 4139 SpinLockHolder h(&pageheap_lock); 4140 Span* span = pageheap->New(pages(size)); 4141 if (span != NULL) { 4142 ret = SpanToMallocResult(span); 4143 } 4144 } else { 4145 // The common case, and also the simplest. This just pops the 4146 // size-appropriate freelist, afer replenishing it if it's empty. 4147 ret = CheckedMallocResult(heap->Allocate(size)); 4148 } 4149 if (!ret) { 4150#ifdef WTF_CHANGES 4151 if (crashOnFailure) // This branch should be optimized out by the compiler. 4152 CRASH(); 4153#else 4154 errno = ENOMEM; 4155#endif 4156 } 4157 return ret; 4158} 4159 4160static ALWAYS_INLINE void do_free(void* ptr) { 4161 if (ptr == NULL) return; 4162 ASSERT(pageheap != NULL); // Should not call free() before malloc() 4163 ASSERT(kPageShift && kNumClasses && kPageSize); 4164 const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift; 4165 Span* span = pageheap->GetDescriptor(p); 4166 RELEASE_ASSERT(span->isValid()); 4167 size_t cl = span->sizeclass; 4168 4169 if (cl) { 4170 size_t byteSizeForClass = ByteSizeForClass(cl); 4171#if !(CPU(ARM_THUMB2) && !CPU(APPLE_ARMV7S)) 4172 RELEASE_ASSERT(!((reinterpret_cast<char*>(ptr) - reinterpret_cast<char*>(span->start << kPageShift)) % byteSizeForClass)); 4173#endif 4174 pageheap->CacheSizeClass(p, cl); 4175 4176#ifndef NO_TCMALLOC_SAMPLES 4177 ASSERT(!pageheap->GetDescriptor(p)->sample); 4178#endif 4179 TCMalloc_ThreadCache* heap = TCMalloc_ThreadCache::GetCacheIfPresent(); 4180 if (heap != NULL) { 4181 heap->Deallocate(HardenedSLL::create(ptr), cl); 4182 } else { 4183 // Delete directly into central cache 4184 POISON_DEALLOCATION(ptr, byteSizeForClass); 4185 SLL_SetNext(HardenedSLL::create(ptr), HardenedSLL::null(), central_cache[cl].entropy()); 4186 central_cache[cl].InsertRange(HardenedSLL::create(ptr), HardenedSLL::create(ptr), 1); 4187 } 4188 } else { 4189 SpinLockHolder h(&pageheap_lock); 4190 ASSERT(reinterpret_cast<uintptr_t>(ptr) % kPageSize == 0); 4191 ASSERT(span != NULL && span->start == p); 4192#ifndef NO_TCMALLOC_SAMPLES 4193 if (span->sample) { 4194 DLL_Remove(span); 4195 stacktrace_allocator.Delete(reinterpret_cast<StackTrace*>(span->objects)); 4196 span->objects = NULL; 4197 } 4198#endif 4199 RELEASE_ASSERT(reinterpret_cast<void*>(span->start << kPageShift) == ptr); 4200 POISON_DEALLOCATION(ptr, span->length << kPageShift); 4201 pageheap->Delete(span); 4202 } 4203} 4204 4205#ifndef WTF_CHANGES 4206// For use by exported routines below that want specific alignments 4207// 4208// Note: this code can be slow, and can significantly fragment memory. 4209// The expectation is that memalign/posix_memalign/valloc/pvalloc will 4210// not be invoked very often. This requirement simplifies our 4211// implementation and allows us to tune for expected allocation 4212// patterns. 4213static void* do_memalign(size_t align, size_t size) { 4214 ASSERT((align & (align - 1)) == 0); 4215 ASSERT(align > 0); 4216 if (pageheap == NULL) TCMalloc_ThreadCache::InitModule(); 4217 ASSERT(kPageShift && kNumClasses && kPageSize); 4218 4219 // Allocate at least one byte to avoid boundary conditions below 4220 if (size == 0) size = 1; 4221 4222 if (size <= kMaxSize && align < kPageSize) { 4223 // Search through acceptable size classes looking for one with 4224 // enough alignment. This depends on the fact that 4225 // InitSizeClasses() currently produces several size classes that 4226 // are aligned at powers of two. We will waste time and space if 4227 // we miss in the size class array, but that is deemed acceptable 4228 // since memalign() should be used rarely. 4229 size_t cl = SizeClass(size); 4230 while (cl < kNumClasses && ((class_to_size[cl] & (align - 1)) != 0)) { 4231 cl++; 4232 } 4233 if (cl < kNumClasses) { 4234 TCMalloc_ThreadCache* heap = TCMalloc_ThreadCache::GetCache(); 4235 return CheckedMallocResult(heap->Allocate(class_to_size[cl])); 4236 } 4237 } 4238 4239 // We will allocate directly from the page heap 4240 SpinLockHolder h(&pageheap_lock); 4241 4242 if (align <= kPageSize) { 4243 // Any page-level allocation will be fine 4244 // TODO: We could put the rest of this page in the appropriate 4245 // TODO: cache but it does not seem worth it. 4246 Span* span = pageheap->New(pages(size)); 4247 return span == NULL ? NULL : SpanToMallocResult(span); 4248 } 4249 4250 // Allocate extra pages and carve off an aligned portion 4251 const Length alloc = pages(size + align); 4252 Span* span = pageheap->New(alloc); 4253 if (span == NULL) return NULL; 4254 4255 // Skip starting portion so that we end up aligned 4256 Length skip = 0; 4257 while ((((span->start+skip) << kPageShift) & (align - 1)) != 0) { 4258 skip++; 4259 } 4260 ASSERT_WITH_SECURITY_IMPLICATION(skip < alloc); 4261 if (skip > 0) { 4262 Span* rest = pageheap->Split(span, skip); 4263 pageheap->Delete(span); 4264 span = rest; 4265 } 4266 4267 // Skip trailing portion that we do not need to return 4268 const Length needed = pages(size); 4269 ASSERT(span->length >= needed); 4270 if (span->length > needed) { 4271 Span* trailer = pageheap->Split(span, needed); 4272 pageheap->Delete(trailer); 4273 } 4274 return SpanToMallocResult(span); 4275} 4276#endif 4277 4278// Helpers for use by exported routines below: 4279 4280#ifndef WTF_CHANGES 4281static inline void do_malloc_stats() { 4282 PrintStats(1); 4283} 4284 4285static inline int do_mallopt(int, int) { 4286 return 1; // Indicates error 4287} 4288#endif 4289 4290#ifdef HAVE_STRUCT_MALLINFO // mallinfo isn't defined on freebsd, for instance 4291static inline struct mallinfo do_mallinfo() { 4292 TCMallocStats stats; 4293 ExtractStats(&stats, NULL); 4294 4295 // Just some of the fields are filled in. 4296 struct mallinfo info; 4297 memset(&info, 0, sizeof(info)); 4298 4299 // Unfortunately, the struct contains "int" field, so some of the 4300 // size values will be truncated. 4301 info.arena = static_cast<int>(stats.system_bytes); 4302 info.fsmblks = static_cast<int>(stats.thread_bytes 4303 + stats.central_bytes 4304 + stats.transfer_bytes); 4305 info.fordblks = static_cast<int>(stats.pageheap_bytes); 4306 info.uordblks = static_cast<int>(stats.system_bytes 4307 - stats.thread_bytes 4308 - stats.central_bytes 4309 - stats.transfer_bytes 4310 - stats.pageheap_bytes); 4311 4312 return info; 4313} 4314#endif 4315 4316//------------------------------------------------------------------- 4317// Exported routines 4318//------------------------------------------------------------------- 4319 4320// CAVEAT: The code structure below ensures that MallocHook methods are always 4321// called from the stack frame of the invoked allocation function. 4322// heap-checker.cc depends on this to start a stack trace from 4323// the call to the (de)allocation function. 4324 4325#ifndef WTF_CHANGES 4326extern "C" 4327#else 4328#define do_malloc do_malloc<crashOnFailure> 4329 4330template <bool crashOnFailure> 4331ALWAYS_INLINE void* malloc(size_t); 4332 4333void* fastMalloc(size_t size) 4334{ 4335 void* result = malloc<true>(size); 4336#if ENABLE(ALLOCATION_LOGGING) 4337 dataLogF("fastMalloc allocating %lu bytes (fastMalloc): %p.\n", size, result); 4338#endif 4339 return result; 4340} 4341 4342TryMallocReturnValue tryFastMalloc(size_t size) 4343{ 4344 TryMallocReturnValue result = malloc<false>(size); 4345#if ENABLE(ALLOCATION_LOGGING) 4346 void* pointer; 4347 (void)result.getValue(pointer); 4348 dataLogF("fastMalloc allocating %lu bytes (tryFastMalloc): %p.\n", size, pointer); 4349#endif 4350 return result; 4351} 4352 4353template <bool crashOnFailure> 4354ALWAYS_INLINE 4355#endif 4356void* malloc(size_t size) { 4357#if ENABLE(WTF_MALLOC_VALIDATION) 4358 if (std::numeric_limits<size_t>::max() - Internal::ValidationBufferSize <= size) // If overflow would occur... 4359 return 0; 4360 void* result = do_malloc(size + Internal::ValidationBufferSize); 4361 if (!result) 4362 return 0; 4363 4364 Internal::ValidationHeader* header = static_cast<Internal::ValidationHeader*>(result); 4365 header->m_size = size; 4366 header->m_type = Internal::AllocTypeMalloc; 4367 header->m_prefix = static_cast<unsigned>(Internal::ValidationPrefix); 4368 result = header + 1; 4369 *Internal::fastMallocValidationSuffix(result) = Internal::ValidationSuffix; 4370 fastMallocValidate(result); 4371#else 4372 void* result = do_malloc(size); 4373#endif 4374 4375 MallocHook::InvokeNewHook(result, size); 4376 return result; 4377} 4378 4379#ifndef WTF_CHANGES 4380extern "C" 4381#endif 4382void free(void* ptr) { 4383#if ENABLE(ALLOCATION_LOGGING) 4384 dataLogF("fastFree freeing %p.\n", ptr); 4385#endif 4386 4387 MallocHook::InvokeDeleteHook(ptr); 4388 4389#if ENABLE(WTF_MALLOC_VALIDATION) 4390 if (!ptr) 4391 return; 4392 4393 fastMallocValidate(ptr); 4394 Internal::ValidationHeader* header = Internal::fastMallocValidationHeader(ptr); 4395 memset(ptr, 0xCC, header->m_size); 4396 do_free(header); 4397#else 4398 do_free(ptr); 4399#endif 4400} 4401 4402#ifndef WTF_CHANGES 4403extern "C" 4404#else 4405template <bool crashOnFailure> 4406ALWAYS_INLINE void* calloc(size_t, size_t); 4407 4408void* fastCalloc(size_t n, size_t elem_size) 4409{ 4410 void* result = calloc<true>(n, elem_size); 4411#if ENABLE(WTF_MALLOC_VALIDATION) 4412 fastMallocValidate(result); 4413#endif 4414#if ENABLE(ALLOCATION_LOGGING) 4415 dataLogF("fastMalloc contiguously allocating %lu * %lu bytes (fastCalloc): %p.\n", n, elem_size, result); 4416#endif 4417 return result; 4418} 4419 4420TryMallocReturnValue tryFastCalloc(size_t n, size_t elem_size) 4421{ 4422 void* result = calloc<false>(n, elem_size); 4423#if ENABLE(WTF_MALLOC_VALIDATION) 4424 fastMallocValidate(result); 4425#endif 4426#if ENABLE(ALLOCATION_LOGGING) 4427 dataLogF("fastMalloc contiguously allocating %lu * %lu bytes (tryFastCalloc): %p.\n", n, elem_size, result); 4428#endif 4429 return result; 4430} 4431 4432template <bool crashOnFailure> 4433ALWAYS_INLINE 4434#endif 4435void* calloc(size_t n, size_t elem_size) { 4436 size_t totalBytes = n * elem_size; 4437 4438 // Protect against overflow 4439 if (n > 1 && elem_size && (totalBytes / elem_size) != n) 4440 return 0; 4441 4442#if ENABLE(WTF_MALLOC_VALIDATION) 4443 void* result = malloc<crashOnFailure>(totalBytes); 4444 if (!result) 4445 return 0; 4446 4447 memset(result, 0, totalBytes); 4448 fastMallocValidate(result); 4449#else 4450 void* result = do_malloc(totalBytes); 4451 if (result != NULL) { 4452 memset(result, 0, totalBytes); 4453 } 4454#endif 4455 4456 MallocHook::InvokeNewHook(result, totalBytes); 4457 return result; 4458} 4459 4460// Since cfree isn't used anywhere, we don't compile it in. 4461#ifndef WTF_CHANGES 4462#ifndef WTF_CHANGES 4463extern "C" 4464#endif 4465void cfree(void* ptr) { 4466#ifndef WTF_CHANGES 4467 MallocHook::InvokeDeleteHook(ptr); 4468#endif 4469 do_free(ptr); 4470} 4471#endif 4472 4473#ifndef WTF_CHANGES 4474extern "C" 4475#else 4476template <bool crashOnFailure> 4477ALWAYS_INLINE void* realloc(void*, size_t); 4478 4479void* fastRealloc(void* old_ptr, size_t new_size) 4480{ 4481#if ENABLE(WTF_MALLOC_VALIDATION) 4482 fastMallocValidate(old_ptr); 4483#endif 4484 void* result = realloc<true>(old_ptr, new_size); 4485#if ENABLE(WTF_MALLOC_VALIDATION) 4486 fastMallocValidate(result); 4487#endif 4488#if ENABLE(ALLOCATION_LOGGING) 4489 dataLogF("fastMalloc reallocating %lu bytes (fastRealloc): %p -> %p.\n", new_size, old_ptr, result); 4490#endif 4491 return result; 4492} 4493 4494TryMallocReturnValue tryFastRealloc(void* old_ptr, size_t new_size) 4495{ 4496#if ENABLE(WTF_MALLOC_VALIDATION) 4497 fastMallocValidate(old_ptr); 4498#endif 4499 void* result = realloc<false>(old_ptr, new_size); 4500#if ENABLE(WTF_MALLOC_VALIDATION) 4501 fastMallocValidate(result); 4502#endif 4503#if ENABLE(ALLOCATION_LOGGING) 4504 dataLogF("fastMalloc reallocating %lu bytes (tryFastRealloc): %p -> %p.\n", new_size, old_ptr, result); 4505#endif 4506 return result; 4507} 4508 4509template <bool crashOnFailure> 4510ALWAYS_INLINE 4511#endif 4512void* realloc(void* old_ptr, size_t new_size) { 4513 if (old_ptr == NULL) { 4514#if ENABLE(WTF_MALLOC_VALIDATION) 4515 void* result = malloc<crashOnFailure>(new_size); 4516#else 4517 void* result = do_malloc(new_size); 4518 MallocHook::InvokeNewHook(result, new_size); 4519#endif 4520 return result; 4521 } 4522 if (new_size == 0) { 4523 MallocHook::InvokeDeleteHook(old_ptr); 4524 free(old_ptr); 4525 return NULL; 4526 } 4527 4528#if ENABLE(WTF_MALLOC_VALIDATION) 4529 if (std::numeric_limits<size_t>::max() - Internal::ValidationBufferSize <= new_size) // If overflow would occur... 4530 return 0; 4531 Internal::ValidationHeader* header = Internal::fastMallocValidationHeader(old_ptr); 4532 fastMallocValidate(old_ptr); 4533 old_ptr = header; 4534 header->m_size = new_size; 4535 new_size += Internal::ValidationBufferSize; 4536#endif 4537 4538 ASSERT(pageheap != NULL); // Should not call realloc() before malloc() 4539 ASSERT(kPageShift && kNumClasses && kPageSize); 4540 4541 // Get the size of the old entry 4542 const PageID p = reinterpret_cast<uintptr_t>(old_ptr) >> kPageShift; 4543 size_t cl = pageheap->GetSizeClassIfCached(p); 4544 Span *span = NULL; 4545 size_t old_size; 4546 if (cl == 0) { 4547 span = pageheap->GetDescriptor(p); 4548 cl = span->sizeclass; 4549 pageheap->CacheSizeClass(p, cl); 4550 } 4551 if (cl != 0) { 4552 old_size = ByteSizeForClass(cl); 4553 } else { 4554 ASSERT(span != NULL); 4555 old_size = span->length << kPageShift; 4556 } 4557 4558 // Reallocate if the new size is larger than the old size, 4559 // or if the new size is significantly smaller than the old size. 4560 if ((new_size > old_size) || (AllocationSize(new_size) < old_size)) { 4561 // Need to reallocate 4562 void* new_ptr = do_malloc(new_size); 4563 if (new_ptr == NULL) { 4564 return NULL; 4565 } 4566 MallocHook::InvokeNewHook(new_ptr, new_size); 4567 memcpy(new_ptr, old_ptr, ((old_size < new_size) ? old_size : new_size)); 4568 MallocHook::InvokeDeleteHook(old_ptr); 4569 // We could use a variant of do_free() that leverages the fact 4570 // that we already know the sizeclass of old_ptr. The benefit 4571 // would be small, so don't bother. 4572 do_free(old_ptr); 4573#if ENABLE(WTF_MALLOC_VALIDATION) 4574 new_ptr = static_cast<Internal::ValidationHeader*>(new_ptr) + 1; 4575 *Internal::fastMallocValidationSuffix(new_ptr) = Internal::ValidationSuffix; 4576#endif 4577 return new_ptr; 4578 } else { 4579#if ENABLE(WTF_MALLOC_VALIDATION) 4580 old_ptr = static_cast<Internal::ValidationHeader*>(old_ptr) + 1; // Set old_ptr back to the user pointer. 4581 *Internal::fastMallocValidationSuffix(old_ptr) = Internal::ValidationSuffix; 4582#endif 4583 return old_ptr; 4584 } 4585} 4586 4587#ifdef WTF_CHANGES 4588#undef do_malloc 4589#else 4590 4591static SpinLock set_new_handler_lock = SPINLOCK_INITIALIZER; 4592 4593static inline void* cpp_alloc(size_t size, bool nothrow) { 4594 for (;;) { 4595 void* p = do_malloc(size); 4596#ifdef PREANSINEW 4597 return p; 4598#else 4599 if (p == NULL) { // allocation failed 4600 // Get the current new handler. NB: this function is not 4601 // thread-safe. We make a feeble stab at making it so here, but 4602 // this lock only protects against tcmalloc interfering with 4603 // itself, not with other libraries calling set_new_handler. 4604 std::new_handler nh; 4605 { 4606 SpinLockHolder h(&set_new_handler_lock); 4607 nh = std::set_new_handler(0); 4608 (void) std::set_new_handler(nh); 4609 } 4610 // If no new_handler is established, the allocation failed. 4611 if (!nh) { 4612 if (nothrow) return 0; 4613 throw std::bad_alloc(); 4614 } 4615 // Otherwise, try the new_handler. If it returns, retry the 4616 // allocation. If it throws std::bad_alloc, fail the allocation. 4617 // if it throws something else, don't interfere. 4618 try { 4619 (*nh)(); 4620 } catch (const std::bad_alloc&) { 4621 if (!nothrow) throw; 4622 return p; 4623 } 4624 } else { // allocation success 4625 return p; 4626 } 4627#endif 4628 } 4629} 4630 4631extern "C" void* memalign(size_t align, size_t size) __THROW { 4632 void* result = do_memalign(align, size); 4633 MallocHook::InvokeNewHook(result, size); 4634 return result; 4635} 4636 4637extern "C" int posix_memalign(void** result_ptr, size_t align, size_t size) 4638 __THROW { 4639 if (((align % sizeof(void*)) != 0) || 4640 ((align & (align - 1)) != 0) || 4641 (align == 0)) { 4642 return EINVAL; 4643 } 4644 4645 void* result = do_memalign(align, size); 4646 MallocHook::InvokeNewHook(result, size); 4647 if (result == NULL) { 4648 return ENOMEM; 4649 } else { 4650 *result_ptr = result; 4651 return 0; 4652 } 4653} 4654 4655static size_t pagesize = 0; 4656 4657extern "C" void* valloc(size_t size) __THROW { 4658 // Allocate page-aligned object of length >= size bytes 4659 if (pagesize == 0) pagesize = getpagesize(); 4660 void* result = do_memalign(pagesize, size); 4661 MallocHook::InvokeNewHook(result, size); 4662 return result; 4663} 4664 4665extern "C" void* pvalloc(size_t size) __THROW { 4666 // Round up size to a multiple of pagesize 4667 if (pagesize == 0) pagesize = getpagesize(); 4668 size = (size + pagesize - 1) & ~(pagesize - 1); 4669 void* result = do_memalign(pagesize, size); 4670 MallocHook::InvokeNewHook(result, size); 4671 return result; 4672} 4673 4674extern "C" void malloc_stats(void) { 4675 do_malloc_stats(); 4676} 4677 4678extern "C" int mallopt(int cmd, int value) { 4679 return do_mallopt(cmd, value); 4680} 4681 4682#ifdef HAVE_STRUCT_MALLINFO 4683extern "C" struct mallinfo mallinfo(void) { 4684 return do_mallinfo(); 4685} 4686#endif 4687 4688//------------------------------------------------------------------- 4689// Some library routines on RedHat 9 allocate memory using malloc() 4690// and free it using __libc_free() (or vice-versa). Since we provide 4691// our own implementations of malloc/free, we need to make sure that 4692// the __libc_XXX variants (defined as part of glibc) also point to 4693// the same implementations. 4694//------------------------------------------------------------------- 4695 4696#if defined(__GLIBC__) 4697extern "C" { 4698#if COMPILER(GCC) && !defined(__MACH__) && defined(HAVE___ATTRIBUTE__) 4699 // Potentially faster variants that use the gcc alias extension. 4700 // Mach-O (Darwin) does not support weak aliases, hence the __MACH__ check. 4701# define ALIAS(x) __attribute__ ((weak, alias (x))) 4702 void* __libc_malloc(size_t size) ALIAS("malloc"); 4703 void __libc_free(void* ptr) ALIAS("free"); 4704 void* __libc_realloc(void* ptr, size_t size) ALIAS("realloc"); 4705 void* __libc_calloc(size_t n, size_t size) ALIAS("calloc"); 4706 void __libc_cfree(void* ptr) ALIAS("cfree"); 4707 void* __libc_memalign(size_t align, size_t s) ALIAS("memalign"); 4708 void* __libc_valloc(size_t size) ALIAS("valloc"); 4709 void* __libc_pvalloc(size_t size) ALIAS("pvalloc"); 4710 int __posix_memalign(void** r, size_t a, size_t s) ALIAS("posix_memalign"); 4711# undef ALIAS 4712# else /* not __GNUC__ */ 4713 // Portable wrappers 4714 void* __libc_malloc(size_t size) { return malloc(size); } 4715 void __libc_free(void* ptr) { free(ptr); } 4716 void* __libc_realloc(void* ptr, size_t size) { return realloc(ptr, size); } 4717 void* __libc_calloc(size_t n, size_t size) { return calloc(n, size); } 4718 void __libc_cfree(void* ptr) { cfree(ptr); } 4719 void* __libc_memalign(size_t align, size_t s) { return memalign(align, s); } 4720 void* __libc_valloc(size_t size) { return valloc(size); } 4721 void* __libc_pvalloc(size_t size) { return pvalloc(size); } 4722 int __posix_memalign(void** r, size_t a, size_t s) { 4723 return posix_memalign(r, a, s); 4724 } 4725# endif /* __GNUC__ */ 4726} 4727#endif /* __GLIBC__ */ 4728 4729// Override __libc_memalign in libc on linux boxes specially. 4730// They have a bug in libc that causes them to (very rarely) allocate 4731// with __libc_memalign() yet deallocate with free() and the 4732// definitions above don't catch it. 4733// This function is an exception to the rule of calling MallocHook method 4734// from the stack frame of the allocation function; 4735// heap-checker handles this special case explicitly. 4736static void *MemalignOverride(size_t align, size_t size, const void *caller) 4737 __THROW { 4738 void* result = do_memalign(align, size); 4739 MallocHook::InvokeNewHook(result, size); 4740 return result; 4741} 4742void *(*__memalign_hook)(size_t, size_t, const void *) = MemalignOverride; 4743 4744#endif 4745 4746#ifdef WTF_CHANGES 4747void releaseFastMallocFreeMemory() 4748{ 4749 // Flush free pages in the current thread cache back to the page heap. 4750 if (TCMalloc_ThreadCache* threadCache = TCMalloc_ThreadCache::GetCacheIfPresent()) 4751 threadCache->Cleanup(); 4752 4753 SpinLockHolder h(&pageheap_lock); 4754 pageheap->ReleaseFreePages(); 4755} 4756 4757FastMallocStatistics fastMallocStatistics() 4758{ 4759 ASSERT(kPageShift && kNumClasses && kPageSize); 4760 FastMallocStatistics statistics; 4761 4762 SpinLockHolder lockHolder(&pageheap_lock); 4763 statistics.reservedVMBytes = static_cast<size_t>(pageheap->SystemBytes()); 4764 statistics.committedVMBytes = statistics.reservedVMBytes - pageheap->ReturnedBytes(); 4765 4766 statistics.freeListBytes = 0; 4767 for (unsigned cl = 0; cl < kNumClasses; ++cl) { 4768 const int length = central_cache[cl].length(); 4769 const int tc_length = central_cache[cl].tc_length(); 4770 4771 statistics.freeListBytes += ByteSizeForClass(cl) * (length + tc_length); 4772 } 4773 for (TCMalloc_ThreadCache* threadCache = thread_heaps; threadCache ; threadCache = threadCache->next_) 4774 statistics.freeListBytes += threadCache->Size(); 4775 4776 return statistics; 4777} 4778 4779size_t fastMallocSize(const void* ptr) 4780{ 4781 if (pageheap == NULL) TCMalloc_ThreadCache::InitModule(); 4782 ASSERT(kPageShift && kNumClasses && kPageSize); 4783 4784#if ENABLE(WTF_MALLOC_VALIDATION) 4785 return Internal::fastMallocValidationHeader(const_cast<void*>(ptr))->m_size; 4786#else 4787 const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift; 4788 Span* span = pageheap->GetDescriptorEnsureSafe(p); 4789 4790 if (!span || span->free) 4791 return 0; 4792 4793 for (HardenedSLL free = span->objects; free; free = SLL_Next(free, HARDENING_ENTROPY)) { 4794 if (ptr == free.value()) 4795 return 0; 4796 } 4797 4798 if (size_t cl = span->sizeclass) 4799 return ByteSizeForClass(cl); 4800 4801 return span->length << kPageShift; 4802#endif 4803} 4804 4805#if OS(DARWIN) 4806class RemoteMemoryReader { 4807 task_t m_task; 4808 memory_reader_t* m_reader; 4809 4810public: 4811 RemoteMemoryReader(task_t task, memory_reader_t* reader) 4812 : m_task(task) 4813 , m_reader(reader) 4814 { } 4815 4816 void* operator()(vm_address_t address, size_t size) const 4817 { 4818 void* output; 4819 kern_return_t err = (*m_reader)(m_task, address, size, static_cast<void**>(&output)); 4820 if (err) 4821 output = 0; 4822 return output; 4823 } 4824 4825 template <typename T> 4826 T* operator()(T* address, size_t size = sizeof(T)) const 4827 { 4828 return static_cast<T*>((*this)(reinterpret_cast<vm_address_t>(address), size)); 4829 } 4830 4831 template <typename T> 4832 T* nextEntryInHardenedLinkedList(T** remoteAddress, uintptr_t entropy) const 4833 { 4834 T** localAddress = (*this)(remoteAddress); 4835 if (!localAddress) 4836 return 0; 4837 T* hardenedNext = *localAddress; 4838 if (!hardenedNext || hardenedNext == (void*)entropy) 4839 return 0; 4840 return XOR_MASK_PTR_WITH_KEY(hardenedNext, remoteAddress, entropy); 4841 } 4842}; 4843 4844template <typename T> 4845template <typename Recorder> 4846void PageHeapAllocator<T>::recordAdministrativeRegions(Recorder& recorder, const RemoteMemoryReader& reader) 4847{ 4848 for (HardenedSLL adminAllocation = allocated_regions_; adminAllocation; adminAllocation.setValue(reader.nextEntryInHardenedLinkedList(reinterpret_cast<void**>(adminAllocation.value()), entropy_))) 4849 recorder.recordRegion(reinterpret_cast<vm_address_t>(adminAllocation.value()), kAllocIncrement); 4850} 4851 4852class FreeObjectFinder { 4853 const RemoteMemoryReader& m_reader; 4854 HashSet<void*> m_freeObjects; 4855 4856public: 4857 FreeObjectFinder(const RemoteMemoryReader& reader) : m_reader(reader) { } 4858 4859 void visit(void* ptr) { m_freeObjects.add(ptr); } 4860 bool isFreeObject(void* ptr) const { return m_freeObjects.contains(ptr); } 4861 bool isFreeObject(vm_address_t ptr) const { return isFreeObject(reinterpret_cast<void*>(ptr)); } 4862 size_t freeObjectCount() const { return m_freeObjects.size(); } 4863 4864 void findFreeObjects(TCMalloc_ThreadCache* threadCache) 4865 { 4866 for (; threadCache; threadCache = (threadCache->next_ ? m_reader(threadCache->next_) : 0)) 4867 threadCache->enumerateFreeObjects(*this, m_reader); 4868 } 4869 4870 void findFreeObjects(TCMalloc_Central_FreeListPadded* centralFreeList, size_t numSizes, TCMalloc_Central_FreeListPadded* remoteCentralFreeList) 4871 { 4872 for (unsigned i = 0; i < numSizes; i++) 4873 centralFreeList[i].enumerateFreeObjects(*this, m_reader, remoteCentralFreeList + i); 4874 } 4875}; 4876 4877class PageMapFreeObjectFinder { 4878 const RemoteMemoryReader& m_reader; 4879 FreeObjectFinder& m_freeObjectFinder; 4880 uintptr_t m_entropy; 4881 4882public: 4883 PageMapFreeObjectFinder(const RemoteMemoryReader& reader, FreeObjectFinder& freeObjectFinder, uintptr_t entropy) 4884 : m_reader(reader) 4885 , m_freeObjectFinder(freeObjectFinder) 4886 , m_entropy(entropy) 4887 { 4888#if ENABLE(TCMALLOC_HARDENING) 4889 ASSERT(m_entropy); 4890#endif 4891 } 4892 4893 int visit(void* ptr) const 4894 { 4895 ASSERT(kPageShift && kNumClasses && kPageSize); 4896 if (!ptr) 4897 return 1; 4898 4899 Span* span = m_reader(reinterpret_cast<Span*>(ptr)); 4900 if (!span) 4901 return 1; 4902 4903 if (span->free) { 4904 void* ptr = reinterpret_cast<void*>(span->start << kPageShift); 4905 m_freeObjectFinder.visit(ptr); 4906 } else if (span->sizeclass) { 4907 // Walk the free list of the small-object span, keeping track of each object seen 4908 for (HardenedSLL nextObject = span->objects; nextObject; nextObject.setValue(m_reader.nextEntryInHardenedLinkedList(reinterpret_cast<void**>(nextObject.value()), m_entropy))) 4909 m_freeObjectFinder.visit(nextObject.value()); 4910 } 4911 return span->length; 4912 } 4913}; 4914 4915class PageMapMemoryUsageRecorder { 4916 task_t m_task; 4917 void* m_context; 4918 unsigned m_typeMask; 4919 vm_range_recorder_t* m_recorder; 4920 const RemoteMemoryReader& m_reader; 4921 const FreeObjectFinder& m_freeObjectFinder; 4922 4923 HashSet<void*> m_seenPointers; 4924 Vector<Span*> m_coalescedSpans; 4925 4926public: 4927 PageMapMemoryUsageRecorder(task_t task, void* context, unsigned typeMask, vm_range_recorder_t* recorder, const RemoteMemoryReader& reader, const FreeObjectFinder& freeObjectFinder) 4928 : m_task(task) 4929 , m_context(context) 4930 , m_typeMask(typeMask) 4931 , m_recorder(recorder) 4932 , m_reader(reader) 4933 , m_freeObjectFinder(freeObjectFinder) 4934 { } 4935 4936 ~PageMapMemoryUsageRecorder() 4937 { 4938 ASSERT(!m_coalescedSpans.size()); 4939 } 4940 4941 void recordPendingRegions() 4942 { 4943 ASSERT(kPageShift && kNumClasses && kPageSize); 4944 4945 bool recordRegionsContainingPointers = m_typeMask & MALLOC_PTR_REGION_RANGE_TYPE; 4946 bool recordAllocations = m_typeMask & MALLOC_PTR_IN_USE_RANGE_TYPE; 4947 4948 if (!recordRegionsContainingPointers && !recordAllocations) { 4949 m_coalescedSpans.clear(); 4950 return; 4951 } 4952 4953 Vector<vm_range_t, 256> pointerRegions; 4954 Vector<vm_range_t, 1024> allocatedPointers; 4955 for (size_t i = 0; i < m_coalescedSpans.size(); ++i) { 4956 Span *theSpan = m_coalescedSpans[i]; 4957 vm_address_t spanStartAddress = theSpan->start << kPageShift; 4958 vm_size_t spanSizeInBytes = theSpan->length * kPageSize; 4959 4960 if (recordRegionsContainingPointers) 4961 pointerRegions.append((vm_range_t){spanStartAddress, spanSizeInBytes}); 4962 4963 if (theSpan->free || !recordAllocations) 4964 continue; 4965 4966 if (!theSpan->sizeclass) { 4967 // If it's an allocated large object span, mark it as in use 4968 if (!m_freeObjectFinder.isFreeObject(spanStartAddress)) 4969 allocatedPointers.append((vm_range_t){spanStartAddress, spanSizeInBytes}); 4970 } else { 4971 const size_t objectSize = ByteSizeForClass(theSpan->sizeclass); 4972 4973 // Mark each allocated small object within the span as in use 4974 const vm_address_t endOfSpan = spanStartAddress + spanSizeInBytes; 4975 for (vm_address_t object = spanStartAddress; object + objectSize <= endOfSpan; object += objectSize) { 4976 if (!m_freeObjectFinder.isFreeObject(object)) 4977 allocatedPointers.append((vm_range_t){object, objectSize}); 4978 } 4979 } 4980 } 4981 4982 if (recordRegionsContainingPointers) 4983 (*m_recorder)(m_task, m_context, MALLOC_PTR_REGION_RANGE_TYPE, pointerRegions.data(), pointerRegions.size()); 4984 4985 if (recordAllocations) 4986 (*m_recorder)(m_task, m_context, MALLOC_PTR_IN_USE_RANGE_TYPE, allocatedPointers.data(), allocatedPointers.size()); 4987 4988 m_coalescedSpans.clear(); 4989 } 4990 4991 int visit(void* ptr) 4992 { 4993 ASSERT(kPageShift && kNumClasses && kPageSize); 4994 if (!ptr) 4995 return 1; 4996 4997 Span* span = m_reader(reinterpret_cast<Span*>(ptr)); 4998 if (!span || !span->start) 4999 return 1; 5000 5001 if (!m_seenPointers.add(ptr).isNewEntry) 5002 return span->length; 5003 5004 if (!m_coalescedSpans.size()) { 5005 m_coalescedSpans.append(span); 5006 return span->length; 5007 } 5008 5009 Span* previousSpan = m_coalescedSpans[m_coalescedSpans.size() - 1]; 5010 vm_address_t previousSpanStartAddress = previousSpan->start << kPageShift; 5011 vm_size_t previousSpanSizeInBytes = previousSpan->length * kPageSize; 5012 5013 // If the new span is adjacent to the previous span, do nothing for now. 5014 vm_address_t spanStartAddress = span->start << kPageShift; 5015 if (spanStartAddress == previousSpanStartAddress + previousSpanSizeInBytes) { 5016 m_coalescedSpans.append(span); 5017 return span->length; 5018 } 5019 5020 // New span is not adjacent to previous span, so record the spans coalesced so far. 5021 recordPendingRegions(); 5022 m_coalescedSpans.append(span); 5023 5024 return span->length; 5025 } 5026}; 5027 5028class AdminRegionRecorder { 5029 task_t m_task; 5030 void* m_context; 5031 unsigned m_typeMask; 5032 vm_range_recorder_t* m_recorder; 5033 5034 Vector<vm_range_t, 1024> m_pendingRegions; 5035 5036public: 5037 AdminRegionRecorder(task_t task, void* context, unsigned typeMask, vm_range_recorder_t* recorder) 5038 : m_task(task) 5039 , m_context(context) 5040 , m_typeMask(typeMask) 5041 , m_recorder(recorder) 5042 { } 5043 5044 void recordRegion(vm_address_t ptr, size_t size) 5045 { 5046 if (m_typeMask & MALLOC_ADMIN_REGION_RANGE_TYPE) 5047 m_pendingRegions.append((vm_range_t){ ptr, size }); 5048 } 5049 5050 void visit(void *ptr, size_t size) 5051 { 5052 recordRegion(reinterpret_cast<vm_address_t>(ptr), size); 5053 } 5054 5055 void recordPendingRegions() 5056 { 5057 if (m_pendingRegions.size()) { 5058 (*m_recorder)(m_task, m_context, MALLOC_ADMIN_REGION_RANGE_TYPE, m_pendingRegions.data(), m_pendingRegions.size()); 5059 m_pendingRegions.clear(); 5060 } 5061 } 5062 5063 ~AdminRegionRecorder() 5064 { 5065 ASSERT(!m_pendingRegions.size()); 5066 } 5067}; 5068 5069kern_return_t FastMallocZone::enumerate(task_t task, void* context, unsigned typeMask, vm_address_t zoneAddress, memory_reader_t reader, vm_range_recorder_t recorder) 5070{ 5071 RemoteMemoryReader memoryReader(task, reader); 5072 5073 InitSizeClasses(); 5074 5075 FastMallocZone* mzone = memoryReader(reinterpret_cast<FastMallocZone*>(zoneAddress)); 5076 TCMalloc_PageHeap* pageHeap = memoryReader(mzone->m_pageHeap); 5077 TCMalloc_ThreadCache** threadHeapsPointer = memoryReader(mzone->m_threadHeaps); 5078 TCMalloc_ThreadCache* threadHeaps = memoryReader(*threadHeapsPointer); 5079 5080 TCMalloc_Central_FreeListPadded* centralCaches = memoryReader(mzone->m_centralCaches, sizeof(TCMalloc_Central_FreeListPadded) * kNumClasses); 5081 5082 FreeObjectFinder finder(memoryReader); 5083 finder.findFreeObjects(threadHeaps); 5084 finder.findFreeObjects(centralCaches, kNumClasses, mzone->m_centralCaches); 5085 5086 TCMalloc_PageHeap::PageMap* pageMap = &pageHeap->pagemap_; 5087 PageMapFreeObjectFinder pageMapFinder(memoryReader, finder, pageHeap->entropy_); 5088 pageMap->visitValues(pageMapFinder, memoryReader); 5089 5090 PageMapMemoryUsageRecorder usageRecorder(task, context, typeMask, recorder, memoryReader, finder); 5091 pageMap->visitValues(usageRecorder, memoryReader); 5092 usageRecorder.recordPendingRegions(); 5093 5094 AdminRegionRecorder adminRegionRecorder(task, context, typeMask, recorder); 5095 pageMap->visitAllocations(adminRegionRecorder, memoryReader); 5096 5097 PageHeapAllocator<Span>* spanAllocator = memoryReader(mzone->m_spanAllocator); 5098 PageHeapAllocator<TCMalloc_ThreadCache>* pageHeapAllocator = memoryReader(mzone->m_pageHeapAllocator); 5099 5100 spanAllocator->recordAdministrativeRegions(adminRegionRecorder, memoryReader); 5101 pageHeapAllocator->recordAdministrativeRegions(adminRegionRecorder, memoryReader); 5102 5103 adminRegionRecorder.recordPendingRegions(); 5104 5105 return 0; 5106} 5107 5108size_t FastMallocZone::size(malloc_zone_t*, const void*) 5109{ 5110 return 0; 5111} 5112 5113void* FastMallocZone::zoneMalloc(malloc_zone_t*, size_t) 5114{ 5115 return 0; 5116} 5117 5118void* FastMallocZone::zoneCalloc(malloc_zone_t*, size_t, size_t) 5119{ 5120 return 0; 5121} 5122 5123void FastMallocZone::zoneFree(malloc_zone_t*, void* ptr) 5124{ 5125 // Due to <rdar://problem/5671357> zoneFree may be called by the system free even if the pointer 5126 // is not in this zone. When this happens, the pointer being freed was not allocated by any 5127 // zone so we need to print a useful error for the application developer. 5128 malloc_printf("*** error for object %p: pointer being freed was not allocated\n", ptr); 5129} 5130 5131void* FastMallocZone::zoneRealloc(malloc_zone_t*, void*, size_t) 5132{ 5133 return 0; 5134} 5135 5136 5137#undef malloc 5138#undef free 5139#undef realloc 5140#undef calloc 5141 5142extern "C" { 5143malloc_introspection_t jscore_fastmalloc_introspection = { &FastMallocZone::enumerate, &FastMallocZone::goodSize, &FastMallocZone::check, &FastMallocZone::print, 5144 &FastMallocZone::log, &FastMallocZone::forceLock, &FastMallocZone::forceUnlock, &FastMallocZone::statistics 5145 , 0 // zone_locked will not be called on the zone unless it advertises itself as version five or higher. 5146 , 0, 0, 0, 0 // These members will not be used unless the zone advertises itself as version seven or higher. 5147 5148 }; 5149} 5150 5151FastMallocZone::FastMallocZone(TCMalloc_PageHeap* pageHeap, TCMalloc_ThreadCache** threadHeaps, TCMalloc_Central_FreeListPadded* centralCaches, PageHeapAllocator<Span>* spanAllocator, PageHeapAllocator<TCMalloc_ThreadCache>* pageHeapAllocator) 5152 : m_pageHeap(pageHeap) 5153 , m_threadHeaps(threadHeaps) 5154 , m_centralCaches(centralCaches) 5155 , m_spanAllocator(spanAllocator) 5156 , m_pageHeapAllocator(pageHeapAllocator) 5157{ 5158 memset(&m_zone, 0, sizeof(m_zone)); 5159 m_zone.version = 4; 5160 m_zone.zone_name = "JavaScriptCore FastMalloc"; 5161 m_zone.size = &FastMallocZone::size; 5162 m_zone.malloc = &FastMallocZone::zoneMalloc; 5163 m_zone.calloc = &FastMallocZone::zoneCalloc; 5164 m_zone.realloc = &FastMallocZone::zoneRealloc; 5165 m_zone.free = &FastMallocZone::zoneFree; 5166 m_zone.valloc = &FastMallocZone::zoneValloc; 5167 m_zone.destroy = &FastMallocZone::zoneDestroy; 5168 m_zone.introspect = &jscore_fastmalloc_introspection; 5169 malloc_zone_register(&m_zone); 5170} 5171 5172 5173void FastMallocZone::init() 5174{ 5175 static FastMallocZone zone(pageheap, &thread_heaps, static_cast<TCMalloc_Central_FreeListPadded*>(central_cache), &span_allocator, &threadheap_allocator); 5176} 5177 5178#endif // OS(DARWIN) 5179 5180} // namespace WTF 5181#endif // WTF_CHANGES 5182 5183#endif // FORCE_SYSTEM_MALLOC 5184