// Copyright (c) 2005, 2007, Google Inc.

// All rights reserved.

// Copyright (C) 2005, 2006, 2007, 2008, 2009, 2011 Apple Inc. All rights reserved.

//

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions are

// met:

//

// * Redistributions of source code must retain the above copyright

// notice, this list of conditions and the following disclaimer.

// * Redistributions in binary form must reproduce the above

// copyright notice, this list of conditions and the following disclaimer

// in the documentation and/or other materials provided with the

// distribution.

// * Neither the name of Google Inc. nor the names of its

// contributors may be used to endorse or promote products derived from

// this software without specific prior written permission.

//

// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// ---

// Author: Sanjay Ghemawat <[email protected]>

//

// A malloc that uses a per-thread cache to satisfy small malloc requests.

// (The time for malloc/free of a small object drops from 300 ns to 50 ns.)

//

// See doc/tcmalloc.html for a high-level

// description of how this malloc works.

//

// SYNCHRONIZATION

// 1. The thread-specific lists are accessed without acquiring any locks.

// This is safe because each such list is only accessed by one thread.

// 2. We have a lock per central free-list, and hold it while manipulating

// the central free list for a particular size.

// 3. The central page allocator is protected by "pageheap_lock".

// 4. The pagemap (which maps from page-number to descriptor),

// can be read without holding any locks, and written while holding

// the "pageheap_lock".

// 5. To improve performance, a subset of the information one can get

// from the pagemap is cached in a data structure, pagemap_cache_,

// that atomically reads and writes its entries. This cache can be

// read and written without locking.

//

// This multi-threaded access to the pagemap is safe for fairly

// subtle reasons. We basically assume that when an object X is

// allocated by thread A and deallocated by thread B, there must

// have been appropriate synchronization in the handoff of object

// X from thread A to thread B. The same logic applies to pagemap_cache_.

//

// THE PAGEID-TO-SIZECLASS CACHE

// Hot PageID-to-sizeclass mappings are held by pagemap_cache_. If this cache

// returns 0 for a particular PageID then that means "no information," not that

// the sizeclass is 0. The cache may have stale information for pages that do

// not hold the beginning of any free()'able object. Staleness is eliminated

// in Populate() for pages with sizeclass > 0 objects, and in do_malloc() and

// do_memalign() for all other relevant pages.

//

// TODO: Bias reclamation to larger addresses

// TODO: implement mallinfo/mallopt

// TODO: Better testing

//

// 9/28/2003 (new page-level allocator replaces ptmalloc2):

// * malloc/free of small objects goes from ~300 ns to ~50 ns.

// * allocation of a reasonably complicated struct

// goes from about 1100 ns to about 300 ns.

#include "config.h"

#include "FastMalloc.h"

#include "Assertions.h"

#include "CurrentTime.h"

#include <limits>

#if OS(WINDOWS)

#include <windows.h>

#else

#include <pthread.h>

#endif

#include <string.h>

#include <wtf/DataLog.h>

#include <wtf/StdLibExtras.h>

#if OS(DARWIN)

#include <mach/mach_init.h>

#include <malloc/malloc.h>

#endif

#ifndef NO_TCMALLOC_SAMPLES

#ifdef WTF_CHANGES

#define NO_TCMALLOC_SAMPLES

#endif

#endif

#if !(defined(USE_SYSTEM_MALLOC) && USE_SYSTEM_MALLOC) && defined(NDEBUG)

#define FORCE_SYSTEM_MALLOC 0

#else

#define FORCE_SYSTEM_MALLOC 1

#endif

// Harden the pointers stored in the TCMalloc linked lists

#define ENABLE_TCMALLOC_HARDENING 1

// Use a background thread to periodically scavenge memory to release back to the system

#if PLATFORM(IOS)

#define USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 0

#else

#define USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 1

#endif

#ifndef NDEBUG

namespace WTF {

#if OS(WINDOWS)

// TLS_OUT_OF_INDEXES is not defined on WinCE.

#ifndef TLS_OUT_OF_INDEXES

#define TLS_OUT_OF_INDEXES 0xffffffff

#endif

static DWORD isForibiddenTlsIndex = TLS_OUT_OF_INDEXES;

static const LPVOID kTlsAllowValue = reinterpret_cast<LPVOID>(0); // Must be zero.

static const LPVOID kTlsForbiddenValue = reinterpret_cast<LPVOID>(1);

#if !ASSERT_DISABLED

static bool isForbidden()

{

// By default, fastMalloc is allowed so we don't allocate the

// tls index unless we're asked to make it forbidden. If TlsSetValue

// has not been called on a thread, the value returned by TlsGetValue is 0.

return (isForibiddenTlsIndex != TLS_OUT_OF_INDEXES) && (TlsGetValue(isForibiddenTlsIndex) == kTlsForbiddenValue);

}

#endif

void fastMallocForbid()

{

if (isForibiddenTlsIndex == TLS_OUT_OF_INDEXES)

isForibiddenTlsIndex = TlsAlloc(); // a little racey, but close enough for debug only

TlsSetValue(isForibiddenTlsIndex, kTlsForbiddenValue);

}

void fastMallocAllow()

{

if (isForibiddenTlsIndex == TLS_OUT_OF_INDEXES)

return;

TlsSetValue(isForibiddenTlsIndex, kTlsAllowValue);

}

#else // !OS(WINDOWS)

static pthread_key_t isForbiddenKey;

static pthread_once_t isForbiddenKeyOnce = PTHREAD_ONCE_INIT;

static void initializeIsForbiddenKey()

{

pthread_key_create(&isForbiddenKey, 0);

}

#if !ASSERT_DISABLED

static bool isForbidden()

{

pthread_once(&isForbiddenKeyOnce, initializeIsForbiddenKey);

return !!pthread_getspecific(isForbiddenKey);

}

#endif

void fastMallocForbid()

{

pthread_once(&isForbiddenKeyOnce, initializeIsForbiddenKey);

pthread_setspecific(isForbiddenKey, &isForbiddenKey);

}

void fastMallocAllow()

{

pthread_once(&isForbiddenKeyOnce, initializeIsForbiddenKey);

pthread_setspecific(isForbiddenKey, 0);

}

#endif // OS(WINDOWS)

} // namespace WTF

#endif // NDEBUG

namespace WTF {

namespace Internal {

#if !ENABLE(WTF_MALLOC_VALIDATION)

WTF_EXPORT_PRIVATE void fastMallocMatchFailed(void*);

#else

COMPILE_ASSERT(((sizeof(ValidationHeader) % sizeof(AllocAlignmentInteger)) == 0), ValidationHeader_must_produce_correct_alignment);

#endif

NO_RETURN_DUE_TO_CRASH void fastMallocMatchFailed(void*)

{

CRASH();

}

} // namespace Internal

void* fastZeroedMalloc(size_t n)

{

void* result = fastMalloc(n);

memset(result, 0, n);

return result;

}

char* fastStrDup(const char* src)

{

size_t len = strlen(src) + 1;

char* dup = static_cast<char*>(fastMalloc(len));

memcpy(dup, src, len);

return dup;

}

TryMallocReturnValue tryFastZeroedMalloc(size_t n)

{

void* result;

if (!tryFastMalloc(n).getValue(result))

return 0;

memset(result, 0, n);

return result;

}

} // namespace WTF

#if FORCE_SYSTEM_MALLOC

#if OS(WINDOWS)

#include <malloc.h>

#endif

namespace WTF {

size_t fastMallocGoodSize(size_t bytes)

{

#if OS(DARWIN)

return malloc_good_size(bytes);

#else

return bytes;

#endif

}

TryMallocReturnValue tryFastMalloc(size_t n)

{

ASSERT(!isForbidden());

#if ENABLE(WTF_MALLOC_VALIDATION)

if (std::numeric_limits<size_t>::max() - Internal::ValidationBufferSize <= n) // If overflow would occur...

return 0;

void* result = malloc(n + Internal::ValidationBufferSize);

if (!result)

return 0;

Internal::ValidationHeader* header = static_cast<Internal::ValidationHeader*>(result);

header->m_size = n;

header->m_type = Internal::AllocTypeMalloc;

header->m_prefix = static_cast<unsigned>(Internal::ValidationPrefix);

result = header + 1;

*Internal::fastMallocValidationSuffix(result) = Internal::ValidationSuffix;

fastMallocValidate(result);

return result;

#else

return malloc(n);

#endif

}

void* fastMalloc(size_t n)

{

ASSERT(!isForbidden());

#if ENABLE(WTF_MALLOC_VALIDATION)

TryMallocReturnValue returnValue = tryFastMalloc(n);

void* result;

if (!returnValue.getValue(result))

CRASH();

#else

void* result = malloc(n);

#endif

if (!result)

CRASH();

return result;

}

TryMallocReturnValue tryFastCalloc(size_t n_elements, size_t element_size)

{

ASSERT(!isForbidden());

#if ENABLE(WTF_MALLOC_VALIDATION)

size_t totalBytes = n_elements * element_size;

if (n_elements > 1 && element_size && (totalBytes / element_size) != n_elements)

return 0;

TryMallocReturnValue returnValue = tryFastMalloc(totalBytes);

void* result;

if (!returnValue.getValue(result))

return 0;

memset(result, 0, totalBytes);

fastMallocValidate(result);

return result;

#else

return calloc(n_elements, element_size);

#endif

}

void* fastCalloc(size_t n_elements, size_t element_size)

{

ASSERT(!isForbidden());

#if ENABLE(WTF_MALLOC_VALIDATION)

TryMallocReturnValue returnValue = tryFastCalloc(n_elements, element_size);

void* result;

if (!returnValue.getValue(result))

CRASH();

#else

void* result = calloc(n_elements, element_size);

#endif

if (!result)

CRASH();

return result;

}

void fastFree(void* p)

{

ASSERT(!isForbidden());

#if ENABLE(WTF_MALLOC_VALIDATION)

if (!p)

return;

fastMallocMatchValidateFree(p, Internal::AllocTypeMalloc);

Internal::ValidationHeader* header = Internal::fastMallocValidationHeader(p);

memset(p, 0xCC, header->m_size);

free(header);

#else

free(p);

#endif

}

TryMallocReturnValue tryFastRealloc(void* p, size_t n)

{

ASSERT(!isForbidden());

#if ENABLE(WTF_MALLOC_VALIDATION)

if (p) {

if (std::numeric_limits<size_t>::max() - Internal::ValidationBufferSize <= n) // If overflow would occur...

return 0;

fastMallocValidate(p);

Internal::ValidationHeader* result = static_cast<Internal::ValidationHeader*>(realloc(Internal::fastMallocValidationHeader(p), n + Internal::ValidationBufferSize));

if (!result)

return 0;

result->m_size = n;

result = result + 1;

*fastMallocValidationSuffix(result) = Internal::ValidationSuffix;

fastMallocValidate(result);

return result;

} else {

return fastMalloc(n);

}

#else

return realloc(p, n);

#endif

}

void* fastRealloc(void* p, size_t n)

{

ASSERT(!isForbidden());

#if ENABLE(WTF_MALLOC_VALIDATION)

TryMallocReturnValue returnValue = tryFastRealloc(p, n);

void* result;

if (!returnValue.getValue(result))

CRASH();

#else

void* result = realloc(p, n);

#endif

if (!result)

CRASH();

return result;

}

void releaseFastMallocFreeMemory() { }

FastMallocStatistics fastMallocStatistics()

{

FastMallocStatistics statistics = { 0, 0, 0 };

return statistics;

}

size_t fastMallocSize(const void* p)

{

#if ENABLE(WTF_MALLOC_VALIDATION)

return Internal::fastMallocValidationHeader(const_cast<void*>(p))->m_size;

#elif OS(DARWIN)

return malloc_size(p);

#elif OS(WINDOWS)

return _msize(const_cast<void*>(p));

#else

UNUSED_PARAM(p);

return 1;

#endif

}

} // namespace WTF

#if OS(DARWIN)

// This symbol is present in the JavaScriptCore exports file even when FastMalloc is disabled.

// It will never be used in this case, so it's type and value are less interesting than its presence.

extern "C" WTF_EXPORT_PRIVATE const int jscore_fastmalloc_introspection = 0;

#endif

#else // FORCE_SYSTEM_MALLOC

#include "TCPackedCache.h"

#include "TCPageMap.h"

#include "TCSpinLock.h"

#include "TCSystemAlloc.h"

#include "ThreadSpecific.h"

#include <algorithm>

#if USE(PTHREADS)

#include <pthread.h>

#endif

#include <stdarg.h>

#include <stddef.h>

#include <stdint.h>

#include <stdio.h>

#if HAVE(ERRNO_H)

#include <errno.h>

#endif

#if OS(UNIX)

#include <unistd.h>

#endif

#if OS(WINDOWS)

#ifndef WIN32_LEAN_AND_MEAN

#define WIN32_LEAN_AND_MEAN

#endif

#include <windows.h>

#endif

#ifdef WTF_CHANGES

#if OS(DARWIN)

#include <wtf/HashSet.h>

#include <wtf/Vector.h>

#endif

#if HAVE(DISPATCH_H)

#include <dispatch/dispatch.h>

#endif

#ifdef __has_include

#if __has_include(<System/pthread_machdep.h>)

#include <System/pthread_machdep.h>

#if defined(__PTK_FRAMEWORK_JAVASCRIPTCORE_KEY0)

#define WTF_USE_PTHREAD_GETSPECIFIC_DIRECT 1

#endif

#endif

#endif

#ifndef PRIuS

#define PRIuS "zu"

#endif

// Calling pthread_getspecific through a global function pointer is faster than a normal

// call to the function on Mac OS X, and it's used in performance-critical code. So we

// use a function pointer. But that's not necessarily faster on other platforms, and we had

// problems with this technique on Windows, so we'll do this only on Mac OS X.

#if OS(DARWIN)

#if !USE(PTHREAD_GETSPECIFIC_DIRECT)

static void* (*pthread_getspecific_function_pointer)(pthread_key_t) = pthread_getspecific;

#define pthread_getspecific(key) pthread_getspecific_function_pointer(key)

#else

#define pthread_getspecific(key) _pthread_getspecific_direct(key)

#define pthread_setspecific(key, val) _pthread_setspecific_direct(key, (val))

#endif

#endif

#define DEFINE_VARIABLE(type, name, value, meaning) \

namespace FLAG__namespace_do_not_use_directly_use_DECLARE_##type##_instead { \

type FLAGS_##name(value); \

char FLAGS_no##name; \

} \

using FLAG__namespace_do_not_use_directly_use_DECLARE_##type##_instead::FLAGS_##name

#define DEFINE_int64(name, value, meaning) \

DEFINE_VARIABLE(int64_t, name, value, meaning)

#define DEFINE_double(name, value, meaning) \

DEFINE_VARIABLE(double, name, value, meaning)

namespace WTF {

#define malloc fastMalloc

#define calloc fastCalloc

#define free fastFree

#define realloc fastRealloc

#define MESSAGE LOG_ERROR

#define CHECK_CONDITION ASSERT

#if !OS(DARWIN)

static const char kLLHardeningMask = 0;

#endif

template <unsigned> struct EntropySource;

template <> struct EntropySource<4> {

static uint32_t value()

{

#if OS(DARWIN)

return arc4random();

#else

return static_cast<uint32_t>(static_cast<uintptr_t>(currentTime() * 10000) ^ reinterpret_cast<uintptr_t>(&kLLHardeningMask));

#endif

}

};

template <> struct EntropySource<8> {

static uint64_t value()

{

return EntropySource<4>::value() | (static_cast<uint64_t>(EntropySource<4>::value()) << 32);

}

};

#if ENABLE(TCMALLOC_HARDENING)

/*

* To make it harder to exploit use-after free style exploits

* we mask the addresses we put into our linked lists with the

* address of kLLHardeningMask. Due to ASLR the address of

* kLLHardeningMask should be sufficiently randomized to make direct

* freelist manipulation much more difficult.

*/

enum {

MaskKeyShift = 13

};

static ALWAYS_INLINE uintptr_t internalEntropyValue()

{

static uintptr_t value = EntropySource<sizeof(uintptr_t)>::value() | 1;

ASSERT(value);

return value;

}

#define HARDENING_ENTROPY internalEntropyValue()

#define ROTATE_VALUE(value, amount) (((value) >> (amount)) | ((value) << (sizeof(value) * 8 - (amount))))

#if COMPILER(MSVC)

#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)))

#else

#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)))

#endif

static ALWAYS_INLINE uint32_t freedObjectStartPoison()

{

static uint32_t value = EntropySource<sizeof(uint32_t)>::value() | 1;

ASSERT(value);

return value;

}

static ALWAYS_INLINE uint32_t freedObjectEndPoison()

{

static uint32_t value = EntropySource<sizeof(uint32_t)>::value() | 1;

ASSERT(value);

return value;

}

#define PTR_TO_UINT32(ptr) static_cast<uint32_t>(reinterpret_cast<uintptr_t>(ptr))

#define END_POISON_INDEX(allocationSize) (((allocationSize) - sizeof(uint32_t)) / sizeof(uint32_t))

#define POISON_ALLOCATION(allocation, allocationSize) do { \

ASSERT((allocationSize) >= 2 * sizeof(uint32_t)); \

reinterpret_cast<uint32_t*>(allocation)[0] = 0xbadbeef1; \

reinterpret_cast<uint32_t*>(allocation)[1] = 0xbadbeef3; \

if ((allocationSize) < 4 * sizeof(uint32_t)) \

break; \

reinterpret_cast<uint32_t*>(allocation)[2] = 0xbadbeef5; \

reinterpret_cast<uint32_t*>(allocation)[END_POISON_INDEX(allocationSize)] = 0xbadbeef7; \

} while (false);

#define POISON_DEALLOCATION_EXPLICIT(allocation, allocationSize, startPoison, endPoison) do { \

ASSERT((allocationSize) >= 2 * sizeof(uint32_t)); \

reinterpret_cast_ptr<uint32_t*>(allocation)[0] = 0xbadbeef9; \

reinterpret_cast_ptr<uint32_t*>(allocation)[1] = 0xbadbeefb; \

if ((allocationSize) < 4 * sizeof(uint32_t)) \

break; \

reinterpret_cast_ptr<uint32_t*>(allocation)[2] = (startPoison) ^ PTR_TO_UINT32(allocation); \

reinterpret_cast_ptr<uint32_t*>(allocation)[END_POISON_INDEX(allocationSize)] = (endPoison) ^ PTR_TO_UINT32(allocation); \

} while (false)

#define POISON_DEALLOCATION(allocation, allocationSize) \

POISON_DEALLOCATION_EXPLICIT(allocation, (allocationSize), freedObjectStartPoison(), freedObjectEndPoison())

#define MAY_BE_POISONED(allocation, allocationSize) (((allocationSize) >= 4 * sizeof(uint32_t)) && ( \

(reinterpret_cast<uint32_t*>(allocation)[2] == (freedObjectStartPoison() ^ PTR_TO_UINT32(allocation))) || \

(reinterpret_cast<uint32_t*>(allocation)[END_POISON_INDEX(allocationSize)] == (freedObjectEndPoison() ^ PTR_TO_UINT32(allocation))) \

))

#define IS_DEFINITELY_POISONED(allocation, allocationSize) (((allocationSize) < 4 * sizeof(uint32_t)) || ( \

(reinterpret_cast<uint32_t*>(allocation)[2] == (freedObjectStartPoison() ^ PTR_TO_UINT32(allocation))) && \

(reinterpret_cast<uint32_t*>(allocation)[END_POISON_INDEX(allocationSize)] == (freedObjectEndPoison() ^ PTR_TO_UINT32(allocation))) \

))

#else

#define POISON_ALLOCATION(allocation, allocationSize)

#define POISON_DEALLOCATION(allocation, allocationSize)

#define POISON_DEALLOCATION_EXPLICIT(allocation, allocationSize, startPoison, endPoison)

#define MAY_BE_POISONED(allocation, allocationSize) (false)

#define IS_DEFINITELY_POISONED(allocation, allocationSize) (true)

#define XOR_MASK_PTR_WITH_KEY(ptr, key, entropy) (((void)entropy), ((void)key), ptr)

#define HARDENING_ENTROPY 0

#endif

//-------------------------------------------------------------------

// Configuration

//-------------------------------------------------------------------

// Type that can hold the length of a run of pages

typedef uintptr_t Length;

// Not all possible combinations of the following parameters make

// sense. In particular, if kMaxSize increases, you may have to

// increase kNumClasses as well.

#define K_PAGE_SHIFT_MIN 12

#define K_PAGE_SHIFT_MAX 14

#define K_NUM_CLASSES_MAX 77

static size_t kPageShift = 0;

static size_t kNumClasses = 0;

static size_t kPageSize = 0;

static Length kMaxValidPages = 0;

static const size_t kMaxSize = 32u * 1024;

static const size_t kAlignShift = 3;

static const size_t kAlignment = 1 << kAlignShift;

// Allocates a big block of memory for the pagemap once we reach more than

// 128MB

static const size_t kPageMapBigAllocationThreshold = 128 << 20;

// Minimum number of pages to fetch from system at a time. Must be

// significantly bigger than kPageSize to amortize system-call

// overhead, and also to reduce external fragementation. Also, we

// should keep this value big because various incarnations of Linux

// have small limits on the number of mmap() regions per

// address-space.

static const size_t kMinSystemAlloc = 1 << (20 - K_PAGE_SHIFT_MAX);

// Number of objects to move between a per-thread list and a central

// list in one shot. We want this to be not too small so we can

// amortize the lock overhead for accessing the central list. Making

// it too big may temporarily cause unnecessary memory wastage in the

// per-thread free list until the scavenger cleans up the list.

static int num_objects_to_move[K_NUM_CLASSES_MAX];

// Maximum length we allow a per-thread free-list to have before we

// move objects from it into the corresponding central free-list. We

// want this big to avoid locking the central free-list too often. It

// should not hurt to make this list somewhat big because the

// scavenging code will shrink it down when its contents are not in use.

static const int kMaxFreeListLength = 256;

// Lower and upper bounds on the per-thread cache sizes

static const size_t kMinThreadCacheSize = kMaxSize * 2;

#if PLATFORM(IOS)

static const size_t kMaxThreadCacheSize = 512 * 1024;

#else

static const size_t kMaxThreadCacheSize = 2 << 20;

#endif

// Default bound on the total amount of thread caches

static const size_t kDefaultOverallThreadCacheSize = 16 << 20;

// For all span-lengths < kMaxPages we keep an exact-size list.

// REQUIRED: kMaxPages >= kMinSystemAlloc;

static const size_t kMaxPages = kMinSystemAlloc;

/* The smallest prime > 2^n */

static int primes_list[] = {

// Small values might cause high rates of sampling

// and hence commented out.

// 2, 5, 11, 17, 37, 67, 131, 257,

// 521, 1031, 2053, 4099, 8209, 16411,

32771, 65537, 131101, 262147, 524309, 1048583,

2097169, 4194319, 8388617, 16777259, 33554467 };

// Twice the approximate gap between sampling actions.

// I.e., we take one sample approximately once every

// tcmalloc_sample_parameter/2

// bytes of allocation, i.e., ~ once every 128KB.

// Must be a prime number.

#ifdef NO_TCMALLOC_SAMPLES

DEFINE_int64(tcmalloc_sample_parameter, 0,

"Unused: code is compiled with NO_TCMALLOC_SAMPLES");

static size_t sample_period = 0;

#else

DEFINE_int64(tcmalloc_sample_parameter, 262147,

"Twice the approximate gap between sampling actions."

" Must be a prime number. Otherwise will be rounded up to a "

" larger prime number");

static size_t sample_period = 262147;

#endif

// Protects sample_period above

static SpinLock sample_period_lock = SPINLOCK_INITIALIZER;

// Parameters for controlling how fast memory is returned to the OS.

DEFINE_double(tcmalloc_release_rate, 1,

"Rate at which we release unused memory to the system. "

"Zero means we never release memory back to the system. "

"Increase this flag to return memory faster; decrease it "

"to return memory slower. Reasonable rates are in the "

"range [0,10]");

//-------------------------------------------------------------------

// Mapping from size to size_class and vice versa

//-------------------------------------------------------------------

// Sizes <= 1024 have an alignment >= 8. So for such sizes we have an

// array indexed by ceil(size/8). Sizes > 1024 have an alignment >= 128.

// So for these larger sizes we have an array indexed by ceil(size/128).

//

// We flatten both logical arrays into one physical array and use

// arithmetic to compute an appropriate index. The constants used by

// ClassIndex() were selected to make the flattening work.

//

// Examples:

// Size Expression Index

// -------------------------------------------------------

// 0 (0 + 7) / 8 0

// 1 (1 + 7) / 8 1

// ...

// 1024 (1024 + 7) / 8 128

// 1025 (1025 + 127 + (120<<7)) / 128 129

// ...

// 32768 (32768 + 127 + (120<<7)) / 128 376

static const size_t kMaxSmallSize = 1024;

static const int shift_amount[2] = { 3, 7 }; // For divides by 8 or 128

static const int add_amount[2] = { 7, 127 + (120 << 7) };

static unsigned char class_array[377];

// Compute index of the class_array[] entry for a given size

static inline int ClassIndex(size_t s) {

const int i = (s > kMaxSmallSize);

return static_cast<int>((s + add_amount[i]) >> shift_amount[i]);

}

// Mapping from size class to max size storable in that class

static size_t class_to_size[K_NUM_CLASSES_MAX];

// Mapping from size class to number of pages to allocate at a time

static size_t class_to_pages[K_NUM_CLASSES_MAX];

// Hardened singly linked list. We make this a class to allow compiler to

// statically prevent mismatching hardened and non-hardened list

class HardenedSLL {

public:

static ALWAYS_INLINE HardenedSLL create(void* value)

{

HardenedSLL result;

result.m_value = value;

return result;

}

static ALWAYS_INLINE HardenedSLL null()

{

HardenedSLL result;

result.m_value = 0;

return result;

}

ALWAYS_INLINE void setValue(void* value) { m_value = value; }

ALWAYS_INLINE void* value() const { return m_value; }

ALWAYS_INLINE bool operator!() const { return !m_value; }

typedef void* (HardenedSLL::*UnspecifiedBoolType);

ALWAYS_INLINE operator UnspecifiedBoolType() const { return m_value ? &HardenedSLL::m_value : 0; }

bool operator!=(const HardenedSLL& other) const { return m_value != other.m_value; }

bool operator==(const HardenedSLL& other) const { return m_value == other.m_value; }

private:

void* m_value;

};

// TransferCache is used to cache transfers of num_objects_to_move[size_class]

// back and forth between thread caches and the central cache for a given size

// class.

struct TCEntry {

HardenedSLL head; // Head of chain of objects.

HardenedSLL tail; // Tail of chain of objects.

};

// A central cache freelist can have anywhere from 0 to kNumTransferEntries

// slots to put link list chains into. To keep memory usage bounded the total

// number of TCEntries across size classes is fixed. Currently each size

// class is initially given one TCEntry which also means that the maximum any

// one class can have is kNumClasses.

#define K_NUM_TRANSFER_ENTRIES_MAX static_cast<int>(K_NUM_CLASSES_MAX)

#define kNumTransferEntries static_cast<int>(kNumClasses)

// Note: the following only works for "n"s that fit in 32-bits, but

// that is fine since we only use it for small sizes.

static inline int LgFloor(size_t n) {

int log = 0;

for (int i = 4; i >= 0; --i) {

int shift = (1 << i);

size_t x = n >> shift;

if (x != 0) {

n = x;

log += shift;

}

}

ASSERT(n == 1);

return log;

}

// Functions for using our simple hardened singly linked list

static ALWAYS_INLINE HardenedSLL SLL_Next(HardenedSLL t, uintptr_t entropy) {

void* tValueNext = *(reinterpret_cast<void**>(t.value()));

return HardenedSLL::create(XOR_MASK_PTR_WITH_KEY(tValueNext, t.value(), entropy));

}

static ALWAYS_INLINE void SLL_SetNext(HardenedSLL t, HardenedSLL n, uintptr_t entropy) {

*(reinterpret_cast<void**>(t.value())) = XOR_MASK_PTR_WITH_KEY(n.value(), t.value(), entropy);

}

static ALWAYS_INLINE void SLL_Push(HardenedSLL* list, HardenedSLL element, uintptr_t entropy) {

SLL_SetNext(element, *list, entropy);

*list = element;

}

static ALWAYS_INLINE HardenedSLL SLL_Pop(HardenedSLL *list, uintptr_t entropy) {

HardenedSLL result = *list;

*list = SLL_Next(*list, entropy);

return result;

}

// Remove N elements from a linked list to which head points. head will be

// modified to point to the new head. start and end will point to the first

// and last nodes of the range. Note that end will point to NULL after this

// function is called.

static ALWAYS_INLINE void SLL_PopRange(HardenedSLL* head, int N, HardenedSLL *start, HardenedSLL *end, uintptr_t entropy) {

if (N == 0) {

*start = HardenedSLL::null();

*end = HardenedSLL::null();

return;

}

HardenedSLL tmp = *head;

for (int i = 1; i < N; ++i) {

tmp = SLL_Next(tmp, entropy);

}

*start = *head;

*end = tmp;

*head = SLL_Next(tmp, entropy);

// Unlink range from list.

SLL_SetNext(tmp, HardenedSLL::null(), entropy);

}

static ALWAYS_INLINE void SLL_PushRange(HardenedSLL *head, HardenedSLL start, HardenedSLL end, uintptr_t entropy) {

if (!start) return;

SLL_SetNext(end, *head, entropy);

*head = start;

}

// Setup helper functions.

static ALWAYS_INLINE size_t SizeClass(size_t size) {

return class_array[ClassIndex(size)];

}

// Get the byte-size for a specified class

static ALWAYS_INLINE size_t ByteSizeForClass(size_t cl) {

return class_to_size[cl];

}

static int NumMoveSize(size_t size) {

if (size == 0) return 0;

// Use approx 64k transfers between thread and central caches.

int num = static_cast<int>(64.0 * 1024.0 / size);

if (num < 2) num = 2;

// Clamp well below kMaxFreeListLength to avoid ping pong between central

// and thread caches.

if (num > static_cast<int>(0.8 * kMaxFreeListLength))

num = static_cast<int>(0.8 * kMaxFreeListLength);

// Also, avoid bringing in too many objects into small object free

// lists. There are lots of such lists, and if we allow each one to

// fetch too many at a time, we end up having to scavenge too often

// (especially when there are lots of threads and each thread gets a

// small allowance for its thread cache).

//

// TODO: Make thread cache free list sizes dynamic so that we do not

// have to equally divide a fixed resource amongst lots of threads.

if (num > 32) num = 32;

return num;

}

// Initialize the mapping arrays

static void InitSizeClasses() {

#if OS(DARWIN)

kPageShift = vm_page_shift;

switch (kPageShift) {

case 12:

kNumClasses = 68;

break;

case 14:

kNumClasses = 77;

break;

default:

CRASH();

};

#else

kPageShift = 12;

kNumClasses = 68;

#endif

kPageSize = 1 << kPageShift;

kMaxValidPages = (~static_cast<Length>(0)) >> kPageShift;

// Do some sanity checking on add_amount[]/shift_amount[]/class_array[]

if (ClassIndex(0) < 0) {

MESSAGE("Invalid class index %d for size 0\n", ClassIndex(0));

CRASH();

}

if (static_cast<size_t>(ClassIndex(kMaxSize)) >= sizeof(class_array)) {

MESSAGE("Invalid class index %d for kMaxSize\n", ClassIndex(kMaxSize));

CRASH();

}

// Compute the size classes we want to use

size_t sc = 1; // Next size class to assign

unsigned char alignshift = kAlignShift;

int last_lg = -1;

for (size_t size = kAlignment; size <= kMaxSize; size += (1 << alignshift)) {

int lg = LgFloor(size);

if (lg > last_lg) {

// Increase alignment every so often.

//

// Since we double the alignment every time size doubles and

// size >= 128, this means that space wasted due to alignment is

// at most 16/128 i.e., 12.5%. Plus we cap the alignment at 256

// bytes, so the space wasted as a percentage starts falling for

// sizes > 2K.

if ((lg >= 7) && (alignshift < 8)) {

alignshift++;

}

last_lg = lg;

}

// Allocate enough pages so leftover is less than 1/8 of total.

// This bounds wasted space to at most 12.5%.

size_t psize = kPageSize;

while ((psize % size) > (psize >> 3)) {

psize += kPageSize;

}

const size_t my_pages = psize >> kPageShift;

if (sc > 1 && my_pages == class_to_pages[sc-1]) {

// See if we can merge this into the previous class without

// increasing the fragmentation of the previous class.

const size_t my_objects = (my_pages << kPageShift) / size;

const size_t prev_objects = (class_to_pages[sc-1] << kPageShift)

/ class_to_size[sc-1];

if (my_objects == prev_objects) {

// Adjust last class to include this size

class_to_size[sc-1] = size;

continue;

}

}

// Add new class

class_to_pages[sc] = my_pages;

class_to_size[sc] = size;

sc++;

}

if (sc != kNumClasses) {

MESSAGE("wrong number of size classes: found %" PRIuS " instead of %d\n",

sc, int(kNumClasses));

CRASH();

}

// Initialize the mapping arrays

int next_size = 0;

for (unsigned char c = 1; c < kNumClasses; c++) {

const size_t max_size_in_class = class_to_size[c];