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

// All rights reserved.

// Copyright (C) 2005, 2006, 2007, 2008, 2009 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 <opensource@google.com>

//

// 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 <limits>

#if ENABLE(JSC_MULTIPLE_THREADS)

#include <pthread.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

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

// https://bugs.webkit.org/show_bug.cgi?id=27900: don't turn this on for Tiger until we have figured out why it caused a crash.

#if defined(BUILDING_ON_TIGER)

#define USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 0

#else

#define USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 1

#endif

#ifndef NDEBUG

namespace WTF {

#if ENABLE(JSC_MULTIPLE_THREADS)

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

}

#else

static bool staticIsForbidden;

static bool isForbidden()

{

return staticIsForbidden;

}

void fastMallocForbid()

{

staticIsForbidden = true;

}

void fastMallocAllow()

{

staticIsForbidden = false;

}

#endif // ENABLE(JSC_MULTIPLE_THREADS)

} // namespace WTF

#endif // NDEBUG

#include <string.h>

namespace WTF {

#if ENABLE(FAST_MALLOC_MATCH_VALIDATION)

namespace Internal {

void fastMallocMatchFailed(void*)

{

CRASH();

}

} // namespace Internal

#endif

void* fastZeroedMalloc(size_t n)

{

void* result = fastMalloc(n);

memset(result, 0, n);

return result;

}

char* fastStrDup(const char* src)

{

int len = strlen(src) + 1;

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

if (dup)

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

namespace WTF {

TryMallocReturnValue tryFastMalloc(size_t n)

{

ASSERT(!isForbidden());

#if ENABLE(FAST_MALLOC_MATCH_VALIDATION)

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

return 0;

void* result = malloc(n + sizeof(AllocAlignmentInteger));

if (!result)

return 0;

*static_cast<AllocAlignmentInteger*>(result) = Internal::AllocTypeMalloc;

result = static_cast<AllocAlignmentInteger*>(result) + 1;

return result;

#else

return malloc(n);

#endif

}

void* fastMalloc(size_t n)

{

ASSERT(!isForbidden());

#if ENABLE(FAST_MALLOC_MATCH_VALIDATION)

TryMallocReturnValue returnValue = tryFastMalloc(n);

void* result;

returnValue.getValue(result);

#else

void* result = malloc(n);

#endif

if (!result) {

#if PLATFORM(BREWMP)

// The behavior of malloc(0) is implementation defined.

// To make sure that fastMalloc never returns 0, retry with fastMalloc(1).

if (!n)

return fastMalloc(1);

#endif

CRASH();

}

return result;

}

TryMallocReturnValue tryFastCalloc(size_t n_elements, size_t element_size)

{

ASSERT(!isForbidden());

#if ENABLE(FAST_MALLOC_MATCH_VALIDATION)

size_t totalBytes = n_elements * element_size;

if (n_elements > 1 && element_size && (totalBytes / element_size) != n_elements || (std::numeric_limits<size_t>::max() - sizeof(AllocAlignmentInteger) <= totalBytes))

return 0;

totalBytes += sizeof(AllocAlignmentInteger);

void* result = malloc(totalBytes);

if (!result)

return 0;

memset(result, 0, totalBytes);

*static_cast<AllocAlignmentInteger*>(result) = Internal::AllocTypeMalloc;

result = static_cast<AllocAlignmentInteger*>(result) + 1;

return result;

#else

return calloc(n_elements, element_size);

#endif

}

void* fastCalloc(size_t n_elements, size_t element_size)

{

ASSERT(!isForbidden());

#if ENABLE(FAST_MALLOC_MATCH_VALIDATION)

TryMallocReturnValue returnValue = tryFastCalloc(n_elements, element_size);

void* result;

returnValue.getValue(result);

#else

void* result = calloc(n_elements, element_size);

#endif

if (!result) {

#if PLATFORM(BREWMP)

// If either n_elements or element_size is 0, the behavior of calloc is implementation defined.

// To make sure that fastCalloc never returns 0, retry with fastCalloc(1, 1).

if (!n_elements || !element_size)

return fastCalloc(1, 1);

#endif

CRASH();

}

return result;

}

void fastFree(void* p)

{

ASSERT(!isForbidden());

#if ENABLE(FAST_MALLOC_MATCH_VALIDATION)

if (!p)

return;

AllocAlignmentInteger* header = Internal::fastMallocMatchValidationValue(p);

if (*header != Internal::AllocTypeMalloc)

Internal::fastMallocMatchFailed(p);

free(header);

#else

free(p);

#endif

}

TryMallocReturnValue tryFastRealloc(void* p, size_t n)

{

ASSERT(!isForbidden());

#if ENABLE(FAST_MALLOC_MATCH_VALIDATION)

if (p) {

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

return 0;

AllocAlignmentInteger* header = Internal::fastMallocMatchValidationValue(p);

if (*header != Internal::AllocTypeMalloc)

Internal::fastMallocMatchFailed(p);

void* result = realloc(header, n + sizeof(AllocAlignmentInteger));

if (!result)

return 0;

// This should not be needed because the value is already there:

// *static_cast<AllocAlignmentInteger*>(result) = Internal::AllocTypeMalloc;

result = static_cast<AllocAlignmentInteger*>(result) + 1;

return result;

} else {

return fastMalloc(n);

}

#else

return realloc(p, n);

#endif

}

void* fastRealloc(void* p, size_t n)

{

ASSERT(!isForbidden());

#if ENABLE(FAST_MALLOC_MATCH_VALIDATION)

TryMallocReturnValue returnValue = tryFastRealloc(p, n);

void* result;

returnValue.getValue(result);

#else

void* result = realloc(p, n);

#endif

if (!result)

CRASH();

return result;

}

void releaseFastMallocFreeMemory() { }

FastMallocStatistics fastMallocStatistics()

{

FastMallocStatistics statistics = { 0, 0, 0, 0 };

return statistics;

}

} // 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" const int jscore_fastmalloc_introspection = 0;

#endif

#else // FORCE_SYSTEM_MALLOC

#if HAVE(STDINT_H)

#include <stdint.h>

#elif HAVE(INTTYPES_H)

#include <inttypes.h>

#else

#include <sys/types.h>

#endif

#include "AlwaysInline.h"

#include "Assertions.h"

#include "TCPackedCache.h"

#include "TCPageMap.h"

#include "TCSpinLock.h"

#include "TCSystemAlloc.h"

#include <algorithm>

#include <errno.h>

#include <limits>

#include <new>

#include <pthread.h>

#include <stdarg.h>

#include <stddef.h>

#include <stdio.h>

#if OS(UNIX)

#include <unistd.h>

#endif

#if COMPILER(MSVC)

#ifndef WIN32_LEAN_AND_MEAN

#define WIN32_LEAN_AND_MEAN

#endif

#include <windows.h>

#endif

#if WTF_CHANGES

#if OS(DARWIN)

#include "MallocZoneSupport.h"

#include <wtf/HashSet.h>

#include <wtf/Vector.h>

#endif

#if HAVE(DISPATCH_H)

#include <dispatch/dispatch.h>

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

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

#define pthread_getspecific(key) pthread_getspecific_function_pointer(key)

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

class Span;

class TCMalloc_Central_FreeListPadded;

class TCMalloc_PageHeap;

class TCMalloc_ThreadCache;

template <typename T> class PageHeapAllocator;

class FastMallocZone {

public:

static void init();

static kern_return_t enumerate(task_t, void*, unsigned typeMmask, vm_address_t zoneAddress, memory_reader_t, vm_range_recorder_t);

static size_t goodSize(malloc_zone_t*, size_t size) { return size; }

static boolean_t check(malloc_zone_t*) { return true; }

static void print(malloc_zone_t*, boolean_t) { }

static void log(malloc_zone_t*, void*) { }

static void forceLock(malloc_zone_t*) { }

static void forceUnlock(malloc_zone_t*) { }

static void statistics(malloc_zone_t*, malloc_statistics_t* stats) { memset(stats, 0, sizeof(malloc_statistics_t)); }

private:

FastMallocZone(TCMalloc_PageHeap*, TCMalloc_ThreadCache**, TCMalloc_Central_FreeListPadded*, PageHeapAllocator<Span>*, PageHeapAllocator<TCMalloc_ThreadCache>*);

static size_t size(malloc_zone_t*, const void*);

static void* zoneMalloc(malloc_zone_t*, size_t);

static void* zoneCalloc(malloc_zone_t*, size_t numItems, size_t size);

static void zoneFree(malloc_zone_t*, void*);

static void* zoneRealloc(malloc_zone_t*, void*, size_t);

static void* zoneValloc(malloc_zone_t*, size_t) { LOG_ERROR("valloc is not supported"); return 0; }

static void zoneDestroy(malloc_zone_t*) { }

malloc_zone_t m_zone;

TCMalloc_PageHeap* m_pageHeap;

TCMalloc_ThreadCache** m_threadHeaps;

TCMalloc_Central_FreeListPadded* m_centralCaches;

PageHeapAllocator<Span>* m_spanAllocator;

PageHeapAllocator<TCMalloc_ThreadCache>* m_pageHeapAllocator;

};

#endif

#endif

#ifndef WTF_CHANGES

// This #ifdef should almost never be set. Set NO_TCMALLOC_SAMPLES if

// you're porting to a system where you really can't get a stacktrace.

#ifdef NO_TCMALLOC_SAMPLES

// We use #define so code compiles even if you #include stacktrace.h somehow.

# define GetStackTrace(stack, depth, skip) (0)

#else

# include <google/stacktrace.h>

#endif

#endif

// Even if we have support for thread-local storage in the compiler

// and linker, the OS may not support it. We need to check that at

// runtime. Right now, we have to keep a manual set of "bad" OSes.

#if defined(HAVE_TLS)

static bool kernel_supports_tls = false; // be conservative

static inline bool KernelSupportsTLS() {

return kernel_supports_tls;

}

# if !HAVE_DECL_UNAME // if too old for uname, probably too old for TLS

static void CheckIfKernelSupportsTLS() {

kernel_supports_tls = false;

}

# else

# include <sys/utsname.h> // DECL_UNAME checked for <sys/utsname.h> too

static void CheckIfKernelSupportsTLS() {

struct utsname buf;

if (uname(&buf) != 0) { // should be impossible

MESSAGE("uname failed assuming no TLS support (errno=%d)\n", errno);

kernel_supports_tls = false;

} else if (strcasecmp(buf.sysname, "linux") == 0) {

// The linux case: the first kernel to support TLS was 2.6.0

if (buf.release[0] < '2' && buf.release[1] == '.') // 0.x or 1.x

kernel_supports_tls = false;

else if (buf.release[0] == '2' && buf.release[1] == '.' &&

buf.release[2] >= '0' && buf.release[2] < '6' &&

buf.release[3] == '.') // 2.0 - 2.5

kernel_supports_tls = false;

else

kernel_supports_tls = true;

} else { // some other kernel, we'll be optimisitic

kernel_supports_tls = true;

}

// TODO(csilvers): VLOG(1) the tls status once we support RAW_VLOG

}

# endif // HAVE_DECL_UNAME

#endif // HAVE_TLS

// __THROW is defined in glibc systems. It means, counter-intuitively,

// "This function will never throw an exception." It's an optional

// optimization tool, but we may need to use it to match glibc prototypes.

#ifndef __THROW // I guess we're not on a glibc system

# define __THROW // __THROW is just an optimization, so ok to make it ""

#endif

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

// Configuration

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

// Not all possible combinations of the following parameters make

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

// increase kNumClasses as well.

static const size_t kPageShift = 12;

static const size_t kPageSize = 1 << kPageShift;

static const size_t kMaxSize = 8u * kPageSize;

static const size_t kAlignShift = 3;

static const size_t kAlignment = 1 << kAlignShift;

static const size_t kNumClasses = 68;

// 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 - kPageShift);

// 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[kNumClasses];

// 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;

static const size_t kMaxThreadCacheSize = 2 << 20;

// 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[kNumClasses];

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

static size_t class_to_pages[kNumClasses];

// 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 {

void *head; // Head of chain of objects.

void *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.

static const int kNumTransferEntries = 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;

}

// Some very basic linked list functions for dealing with using void * as

// storage.

static inline void *SLL_Next(void *t) {

return *(reinterpret_cast<void**>(t));

}

static inline void SLL_SetNext(void *t, void *n) {

*(reinterpret_cast<void**>(t)) = n;

}

static inline void SLL_Push(void **list, void *element) {

SLL_SetNext(element, *list);

*list = element;

}

static inline void *SLL_Pop(void **list) {

void *result = *list;

*list = SLL_Next(*list);

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 inline void SLL_PopRange(void **head, int N, void **start, void **end) {

if (N == 0) {

*start = NULL;

*end = NULL;

return;

}

void *tmp = *head;

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

tmp = SLL_Next(tmp);

}

*start = *head;

*end = tmp;

*head = SLL_Next(tmp);

// Unlink range from list.

SLL_SetNext(tmp, NULL);

}

static inline void SLL_PushRange(void **head, void *start, void *end) {

if (!start) return;

SLL_SetNext(end, *head);

*head = start;

}

static inline size_t SLL_Size(void *head) {

int count = 0;

while (head) {

count++;

head = SLL_Next(head);

}

return count;

}

// 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() {

// 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];

for (size_t s = next_size; s <= max_size_in_class; s += kAlignment) {

class_array[ClassIndex(s)] = c;

}

next_size = static_cast<int>(max_size_in_class + kAlignment);

}

// Double-check sizes just to be safe

for (size_t size = 0; size <= kMaxSize; size++) {

const size_t sc = SizeClass(size);

if (sc == 0) {

MESSAGE("Bad size class %" PRIuS " for %" PRIuS "\n", sc, size);

CRASH();

}

if (sc > 1 && size <= class_to_size[sc-1]) {

MESSAGE("Allocating unnecessarily large class %" PRIuS " for %" PRIuS

"\n", sc, size);

CRASH();

}

if (sc >= kNumClasses) {

MESSAGE("Bad size class %" PRIuS " for %" PRIuS "\n", sc, size);

CRASH();

}

const size_t s = class_to_size[sc];

if (size > s) {

MESSAGE("Bad size %" PRIuS " for %" PRIuS " (sc = %" PRIuS ")\n", s, size, sc);

CRASH();

}

if (s == 0) {

MESSAGE("Bad size %" PRIuS " for %" PRIuS " (sc = %" PRIuS ")\n", s, size, sc);

CRASH();

}

}

// Initialize the num_objects_to_move array.

for (size_t cl = 1; cl < kNumClasses; ++cl) {

num_objects_to_move[cl] = NumMoveSize(ByteSizeForClass(cl));

}

#ifndef WTF_CHANGES

if (false) {

// Dump class sizes and maximum external wastage per size class

for (size_t cl = 1; cl < kNumClasses; ++cl) {

const int alloc_size = class_to_pages[cl] << kPageShift;

const int alloc_objs = alloc_size / class_to_size[cl];

const int min_used = (class_to_size[cl-1] + 1) * alloc_objs;

const int max_waste = alloc_size - min_used;

MESSAGE("SC %3d [ %8d .. %8d ] from %8d ; %2.0f%% maxwaste\n",

int(cl),

int(class_to_size[cl-1] + 1),

int(class_to_size[cl]),

int(class_to_pages[cl] << kPageShift),

max_waste * 100.0 / alloc_size

);

}

}

#endif

}

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

// Simple allocator for objects of a specified type. External locking

// is required before accessing one of these objects.

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

// Metadata allocator -- keeps stats about how many bytes allocated

static uint64_t metadata_system_bytes = 0;

static void* MetaDataAlloc(size_t bytes) {

void* result = TCMalloc_SystemAlloc(bytes, 0);

if (result != NULL) {

metadata_system_bytes += bytes;

}

return result;

}

template <class T>

class PageHeapAllocator {

private:

// How much to allocate from system at a time

static const size_t kAllocIncrement = 32 << 10;

// Aligned size of T

static const size_t kAlignedSize

= (((sizeof(T) + kAlignment - 1) / kAlignment) * kAlignment);

// Free area from which to carve new objects

char* free_area_;

size_t free_avail_;

// Linked list of all regions allocated by this allocator

void* allocated_regions_;

// Free list of already carved objects

void* free_list_;

// Number of allocated but unfreed objects

int inuse_;

public:

void Init() {

ASSERT(kAlignedSize <= kAllocIncrement);

inuse_ = 0;

allocated_regions_ = 0;

free_area_ = NULL;

free_avail_ = 0;

free_list_ = NULL;

}

T* New() {

// Consult free list

void* result;

if (free_list_ != NULL) {

result = free_list_;

free_list_ = *(reinterpret_cast<void**>(result));

} else {

if (free_avail_ < kAlignedSize) {

// Need more room

char* new_allocation = reinterpret_cast<char*>(MetaDataAlloc(kAllocIncrement));

if (!new_allocation)

CRASH();

*(void**)new_allocation = allocated_regions_;

allocated_regions_ = new_allocation;

free_area_ = new_allocation + kAlignedSize;