Removed WTF_MALLOC_VALIDATION
[WebKit-https.git] / Source / WTF / wtf / FastMalloc.cpp
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 PLATFORM(COCOA)
105 #define USE_BMALLOC 1
106 #endif
107
108 #if !(defined(USE_SYSTEM_MALLOC) && USE_SYSTEM_MALLOC)
109 #define FORCE_SYSTEM_MALLOC 0
110 #else
111 #define FORCE_SYSTEM_MALLOC 1
112 #endif
113
114 // Harden the pointers stored in the TCMalloc linked lists
115 #define ENABLE_TCMALLOC_HARDENING 1
116
117 // Use a background thread to periodically scavenge memory to release back to the system
118 #define USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY 1
119
120 #ifndef NDEBUG
121 namespace WTF {
122
123 #if OS(WINDOWS)
124
125 static DWORD isForibiddenTlsIndex = TLS_OUT_OF_INDEXES;
126 static const LPVOID kTlsAllowValue = reinterpret_cast<LPVOID>(0); // Must be zero.
127 static const LPVOID kTlsForbiddenValue = reinterpret_cast<LPVOID>(1);
128
129 #if !ASSERT_DISABLED
130 static bool isForbidden()
131 {
132     // By default, fastMalloc is allowed so we don't allocate the
133     // tls index unless we're asked to make it forbidden. If TlsSetValue
134     // has not been called on a thread, the value returned by TlsGetValue is 0.
135     return (isForibiddenTlsIndex != TLS_OUT_OF_INDEXES) && (TlsGetValue(isForibiddenTlsIndex) == kTlsForbiddenValue);
136 }
137 #endif
138
139 void fastMallocForbid()
140 {
141     if (isForibiddenTlsIndex == TLS_OUT_OF_INDEXES)
142         isForibiddenTlsIndex = TlsAlloc(); // a little racey, but close enough for debug only
143     TlsSetValue(isForibiddenTlsIndex, kTlsForbiddenValue);
144 }
145
146 void fastMallocAllow()
147 {
148     if (isForibiddenTlsIndex == TLS_OUT_OF_INDEXES)
149         return;
150     TlsSetValue(isForibiddenTlsIndex, kTlsAllowValue);
151 }
152
153 #else // !OS(WINDOWS)
154
155 static pthread_key_t isForbiddenKey;
156 static pthread_once_t isForbiddenKeyOnce = PTHREAD_ONCE_INIT;
157 static void initializeIsForbiddenKey()
158 {
159   pthread_key_create(&isForbiddenKey, 0);
160 }
161
162 #if !ASSERT_DISABLED
163 static bool isForbidden()
164 {
165     pthread_once(&isForbiddenKeyOnce, initializeIsForbiddenKey);
166     return !!pthread_getspecific(isForbiddenKey);
167 }
168 #endif
169
170 void fastMallocForbid()
171 {
172     pthread_once(&isForbiddenKeyOnce, initializeIsForbiddenKey);
173     pthread_setspecific(isForbiddenKey, &isForbiddenKey);
174 }
175
176 void fastMallocAllow()
177 {
178     pthread_once(&isForbiddenKeyOnce, initializeIsForbiddenKey);
179     pthread_setspecific(isForbiddenKey, 0);
180 }
181 #endif // OS(WINDOWS)
182
183 } // namespace WTF
184 #endif // NDEBUG
185
186 namespace WTF {
187
188 void* fastZeroedMalloc(size_t n) 
189 {
190     void* result = fastMalloc(n);
191     memset(result, 0, n);
192     return result;
193 }
194
195 char* fastStrDup(const char* src)
196 {
197     size_t len = strlen(src) + 1;
198     char* dup = static_cast<char*>(fastMalloc(len));
199     memcpy(dup, src, len);
200     return dup;
201 }
202
203 TryMallocReturnValue tryFastZeroedMalloc(size_t n) 
204 {
205     void* result;
206     if (!tryFastMalloc(n).getValue(result))
207         return 0;
208     memset(result, 0, n);
209     return result;
210 }
211
212 } // namespace WTF
213
214 #if FORCE_SYSTEM_MALLOC
215
216 #if OS(WINDOWS)
217 #include <malloc.h>
218 #endif
219
220 namespace WTF {
221
222 size_t fastMallocGoodSize(size_t bytes)
223 {
224 #if OS(DARWIN)
225     return malloc_good_size(bytes);
226 #else
227     return bytes;
228 #endif
229 }
230
231 TryMallocReturnValue tryFastMalloc(size_t n) 
232 {
233     ASSERT(!isForbidden());
234
235     return malloc(n);
236 }
237
238 void* fastMalloc(size_t n) 
239 {
240     ASSERT(!isForbidden());
241
242     void* result = malloc(n);
243     if (!result)
244         CRASH();
245
246     return result;
247 }
248
249 TryMallocReturnValue tryFastCalloc(size_t n_elements, size_t element_size)
250 {
251     ASSERT(!isForbidden());
252     return calloc(n_elements, element_size);
253 }
254
255 void* fastCalloc(size_t n_elements, size_t element_size)
256 {
257     ASSERT(!isForbidden());
258
259     void* result = calloc(n_elements, element_size);
260     if (!result)
261         CRASH();
262
263     return result;
264 }
265
266 void fastFree(void* p)
267 {
268     ASSERT(!isForbidden());
269     free(p);
270 }
271
272 TryMallocReturnValue tryFastRealloc(void* p, size_t n)
273 {
274     ASSERT(!isForbidden());
275     return realloc(p, n);
276 }
277
278 void* fastRealloc(void* p, size_t n)
279 {
280     ASSERT(!isForbidden());
281     void* result = realloc(p, n);
282     if (!result)
283         CRASH();
284     return result;
285 }
286
287 void releaseFastMallocFreeMemory() { }
288     
289 FastMallocStatistics fastMallocStatistics()
290 {
291     FastMallocStatistics statistics = { 0, 0, 0 };
292     return statistics;
293 }
294
295 size_t fastMallocSize(const void* p)
296 {
297 #if OS(DARWIN)
298     return malloc_size(p);
299 #elif OS(WINDOWS)
300     return _msize(const_cast<void*>(p));
301 #else
302     UNUSED_PARAM(p);
303     return 1;
304 #endif
305 }
306
307 } // namespace WTF
308
309 #if OS(DARWIN)
310 // This symbol is present in the JavaScriptCore exports file even when FastMalloc is disabled.
311 // It will never be used in this case, so it's type and value are less interesting than its presence.
312 extern "C" WTF_EXPORT_PRIVATE const int jscore_fastmalloc_introspection = 0;
313 #endif
314
315 #elif defined(USE_BMALLOC) && USE_BMALLOC // FORCE_SYSTEM_MALLOC
316
317 #include <bmalloc/bmalloc.h>
318
319 namespace WTF {
320
321 void* fastMalloc(size_t size)
322 {
323     ASSERT(!isForbidden());
324     return bmalloc::api::malloc(size);
325 }
326
327 void* fastCalloc(size_t numElements, size_t elementSize)
328 {
329     return fastZeroedMalloc(numElements * elementSize);
330 }
331     
332 void* fastRealloc(void* object, size_t size)
333 {
334     return bmalloc::api::realloc(object, size);
335 }
336     
337 void fastFree(void* object)
338 {
339     bmalloc::api::free(object);
340 }
341     
342 size_t fastMallocSize(const void*)
343 {
344     return 1;
345 }
346     
347 size_t fastMallocGoodSize(size_t size)
348 {
349     return size;
350 }
351     
352 TryMallocReturnValue tryFastMalloc(size_t size)
353 {
354     return fastMalloc(size);
355 }
356     
357 TryMallocReturnValue tryFastRealloc(void* p, size_t n)
358 {
359     return fastRealloc(p, n);
360 }
361     
362 TryMallocReturnValue tryFastCalloc(size_t numElements, size_t elementSize)
363 {
364     return fastCalloc(numElements, elementSize);
365 }
366     
367 void releaseFastMallocFreeMemory()
368 {
369     bmalloc::api::scavenge();
370 }
371
372 FastMallocStatistics fastMallocStatistics()
373 {
374     FastMallocStatistics statistics = { 0, 0, 0 };
375     return statistics;
376 }
377
378 } // namespace WTF
379
380 #else // FORCE_SYSTEM_MALLOC
381
382 #include "TCPackedCache.h"
383 #include "TCPageMap.h"
384 #include "TCSpinLock.h"
385 #include "TCSystemAlloc.h"
386 #include "ThreadSpecific.h"
387 #include <algorithm>
388 #if USE(PTHREADS)
389 #include <pthread.h>
390 #endif
391 #include <stdarg.h>
392 #include <stddef.h>
393 #include <stdint.h>
394 #include <stdio.h>
395 #if HAVE(ERRNO_H)
396 #include <errno.h>
397 #endif
398 #if OS(UNIX)
399 #include <unistd.h>
400 #endif
401 #if OS(WINDOWS)
402 #ifndef WIN32_LEAN_AND_MEAN
403 #define WIN32_LEAN_AND_MEAN
404 #endif
405 #include <windows.h>
406 #endif
407
408 #ifdef WTF_CHANGES
409
410 #if OS(DARWIN)
411 #include <wtf/HashSet.h>
412 #include <wtf/Vector.h>
413 #endif
414
415 #if HAVE(DISPATCH_H)
416 #include <dispatch/dispatch.h>
417 #endif
418
419 #if OS(DARWIN)
420 #if defined(__has_include) && __has_include(<System/pthread_machdep.h>)
421 #include <System/pthread_machdep.h>
422 #endif
423 #endif
424
425 #if defined(__PTK_FRAMEWORK_JAVASCRIPTCORE_KEY0)
426 #define WTF_USE_PTHREAD_GETSPECIFIC_DIRECT 1
427 #endif
428
429 #ifndef PRIuS
430 #define PRIuS "zu"
431 #endif
432
433 // Calling pthread_getspecific through a global function pointer is faster than a normal
434 // call to the function on Mac OS X, and it's used in performance-critical code. So we
435 // use a function pointer. But that's not necessarily faster on other platforms, and we had
436 // problems with this technique on Windows, so we'll do this only on Mac OS X.
437 #if OS(DARWIN)
438 #if !USE(PTHREAD_GETSPECIFIC_DIRECT)
439 static void* (*pthread_getspecific_function_pointer)(pthread_key_t) = pthread_getspecific;
440 #define pthread_getspecific(key) pthread_getspecific_function_pointer(key)
441 #else
442 #define pthread_getspecific(key) _pthread_getspecific_direct(key)
443 #define pthread_setspecific(key, val) _pthread_setspecific_direct(key, (val))
444 #endif
445 #endif
446
447 #define DEFINE_VARIABLE(type, name, value, meaning) \
448   namespace FLAG__namespace_do_not_use_directly_use_DECLARE_##type##_instead {  \
449   type FLAGS_##name(value);                                \
450   char FLAGS_no##name;                                                        \
451   }                                                                           \
452   using FLAG__namespace_do_not_use_directly_use_DECLARE_##type##_instead::FLAGS_##name
453   
454 #define DEFINE_int64(name, value, meaning) \
455   DEFINE_VARIABLE(int64_t, name, value, meaning)
456   
457 #define DEFINE_double(name, value, meaning) \
458   DEFINE_VARIABLE(double, name, value, meaning)
459
460 namespace WTF {
461
462 #define malloc fastMalloc
463 #define calloc fastCalloc
464 #define free fastFree
465 #define realloc fastRealloc
466
467 #define MESSAGE LOG_ERROR
468 #define CHECK_CONDITION ASSERT
469
470 #if !OS(DARWIN)
471 static const char kLLHardeningMask = 0;
472 #endif
473
474 template <unsigned> struct EntropySource;
475 template <> struct EntropySource<4> {
476     static uint32_t value()
477     {
478 #if OS(DARWIN)
479         return arc4random();
480 #else
481         return static_cast<uint32_t>(static_cast<uintptr_t>(currentTime() * 10000) ^ reinterpret_cast<uintptr_t>(&kLLHardeningMask));
482 #endif
483     }
484 };
485
486 template <> struct EntropySource<8> {
487     static uint64_t value()
488     {
489         return EntropySource<4>::value() | (static_cast<uint64_t>(EntropySource<4>::value()) << 32);
490     }
491 };
492
493 #if ENABLE(TCMALLOC_HARDENING)
494 /*
495  * To make it harder to exploit use-after free style exploits
496  * we mask the addresses we put into our linked lists with the
497  * address of kLLHardeningMask.  Due to ASLR the address of
498  * kLLHardeningMask should be sufficiently randomized to make direct
499  * freelist manipulation much more difficult.
500  */
501 enum {
502     MaskKeyShift = 13
503 };
504
505 static ALWAYS_INLINE uintptr_t internalEntropyValue() 
506 {
507     static uintptr_t value = EntropySource<sizeof(uintptr_t)>::value() | 1;
508     ASSERT(value);
509     return value;
510 }
511
512 #define HARDENING_ENTROPY internalEntropyValue()
513 #define ROTATE_VALUE(value, amount) (((value) >> (amount)) | ((value) << (sizeof(value) * 8 - (amount))))
514 #if COMPILER(MSVC)
515 #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)))
516 #else
517 #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)))
518 #endif
519
520 static ALWAYS_INLINE uint32_t freedObjectStartPoison()
521 {
522     static uint32_t value = EntropySource<sizeof(uint32_t)>::value() | 1;
523     ASSERT(value);
524     return value;
525 }
526
527 static ALWAYS_INLINE uint32_t freedObjectEndPoison()
528 {
529     static uint32_t value = EntropySource<sizeof(uint32_t)>::value() | 1;
530     ASSERT(value);
531     return value;
532 }
533
534 #define PTR_TO_UINT32(ptr) static_cast<uint32_t>(reinterpret_cast<uintptr_t>(ptr))
535 #define END_POISON_INDEX(allocationSize) (((allocationSize) - sizeof(uint32_t)) / sizeof(uint32_t))
536 #define POISON_ALLOCATION(allocation, allocationSize) do { \
537     ASSERT((allocationSize) >= 2 * sizeof(uint32_t)); \
538     reinterpret_cast<uint32_t*>(allocation)[0] = 0xbadbeef1; \
539     reinterpret_cast<uint32_t*>(allocation)[1] = 0xbadbeef3; \
540     if ((allocationSize) < 4 * sizeof(uint32_t)) \
541         break; \
542     reinterpret_cast<uint32_t*>(allocation)[2] = 0xbadbeef5; \
543     reinterpret_cast<uint32_t*>(allocation)[END_POISON_INDEX(allocationSize)] = 0xbadbeef7; \
544 } while (false);
545
546 #define POISON_DEALLOCATION_EXPLICIT(allocation, allocationSize, startPoison, endPoison) do { \
547     ASSERT((allocationSize) >= 2 * sizeof(uint32_t)); \
548     reinterpret_cast_ptr<uint32_t*>(allocation)[0] = 0xbadbeef9; \
549     reinterpret_cast_ptr<uint32_t*>(allocation)[1] = 0xbadbeefb; \
550     if ((allocationSize) < 4 * sizeof(uint32_t)) \
551         break; \
552     reinterpret_cast_ptr<uint32_t*>(allocation)[2] = (startPoison) ^ PTR_TO_UINT32(allocation); \
553     reinterpret_cast_ptr<uint32_t*>(allocation)[END_POISON_INDEX(allocationSize)] = (endPoison) ^ PTR_TO_UINT32(allocation); \
554 } while (false)
555
556 #define POISON_DEALLOCATION(allocation, allocationSize) \
557     POISON_DEALLOCATION_EXPLICIT(allocation, (allocationSize), freedObjectStartPoison(), freedObjectEndPoison())
558
559 #define MAY_BE_POISONED(allocation, allocationSize) (((allocationSize) >= 4 * sizeof(uint32_t)) && ( \
560     (reinterpret_cast<uint32_t*>(allocation)[2] == (freedObjectStartPoison() ^ PTR_TO_UINT32(allocation))) || \
561     (reinterpret_cast<uint32_t*>(allocation)[END_POISON_INDEX(allocationSize)] == (freedObjectEndPoison() ^ PTR_TO_UINT32(allocation))) \
562 ))
563
564 #define IS_DEFINITELY_POISONED(allocation, allocationSize) (((allocationSize) < 4 * sizeof(uint32_t)) || ( \
565     (reinterpret_cast<uint32_t*>(allocation)[2] == (freedObjectStartPoison() ^ PTR_TO_UINT32(allocation))) && \
566     (reinterpret_cast<uint32_t*>(allocation)[END_POISON_INDEX(allocationSize)] == (freedObjectEndPoison() ^ PTR_TO_UINT32(allocation))) \
567 ))
568
569 #else
570
571 #define POISON_ALLOCATION(allocation, allocationSize)
572 #define POISON_DEALLOCATION(allocation, allocationSize)
573 #define POISON_DEALLOCATION_EXPLICIT(allocation, allocationSize, startPoison, endPoison)
574 #define MAY_BE_POISONED(allocation, allocationSize) (false)
575 #define IS_DEFINITELY_POISONED(allocation, allocationSize) (true)
576 #define XOR_MASK_PTR_WITH_KEY(ptr, key, entropy) (((void)entropy), ((void)key), ptr)
577
578 #define HARDENING_ENTROPY 0
579
580 #endif
581
582 //-------------------------------------------------------------------
583 // Configuration
584 //-------------------------------------------------------------------
585
586 // Type that can hold the length of a run of pages
587 typedef uintptr_t Length;
588
589 // Not all possible combinations of the following parameters make
590 // sense.  In particular, if kMaxSize increases, you may have to
591 // increase kNumClasses as well.
592 #define K_PAGE_SHIFT_MIN 12
593 #define K_PAGE_SHIFT_MAX 14
594 #define K_NUM_CLASSES_MAX 77
595 static size_t kPageShift  = 0;
596 static size_t kNumClasses = 0;
597 static size_t kPageSize   = 0;
598 static Length kMaxValidPages = 0;
599 static const size_t kMaxSize    = 32u * 1024;
600 static const size_t kAlignShift = 3;
601 static const size_t kAlignment  = 1 << kAlignShift;
602
603 // Allocates a big block of memory for the pagemap once we reach more than
604 // 128MB
605 static const size_t kPageMapBigAllocationThreshold = 128 << 20;
606
607 // Minimum number of pages to fetch from system at a time.  Must be
608 // significantly bigger than kPageSize to amortize system-call
609 // overhead, and also to reduce external fragementation.  Also, we
610 // should keep this value big because various incarnations of Linux
611 // have small limits on the number of mmap() regions per
612 // address-space.
613 static const size_t kMinSystemAlloc = 1 << (20 - K_PAGE_SHIFT_MAX);
614
615 // Number of objects to move between a per-thread list and a central
616 // list in one shot.  We want this to be not too small so we can
617 // amortize the lock overhead for accessing the central list.  Making
618 // it too big may temporarily cause unnecessary memory wastage in the
619 // per-thread free list until the scavenger cleans up the list.
620 static int num_objects_to_move[K_NUM_CLASSES_MAX];
621
622 // Maximum length we allow a per-thread free-list to have before we
623 // move objects from it into the corresponding central free-list.  We
624 // want this big to avoid locking the central free-list too often.  It
625 // should not hurt to make this list somewhat big because the
626 // scavenging code will shrink it down when its contents are not in use.
627 static const int kMaxFreeListLength = 256;
628
629 // Lower and upper bounds on the per-thread cache sizes
630 static const size_t kMinThreadCacheSize = kMaxSize * 2;
631 static const size_t kMaxThreadCacheSize = 2 << 20;
632
633 // Default bound on the total amount of thread caches
634 static const size_t kDefaultOverallThreadCacheSize = 16 << 20;
635
636 // For all span-lengths < kMaxPages we keep an exact-size list.
637 // REQUIRED: kMaxPages >= kMinSystemAlloc;
638 static const size_t kMaxPages = kMinSystemAlloc;
639
640 /* The smallest prime > 2^n */
641 static int primes_list[] = {
642     // Small values might cause high rates of sampling
643     // and hence commented out.
644     // 2, 5, 11, 17, 37, 67, 131, 257,
645     // 521, 1031, 2053, 4099, 8209, 16411,
646     32771, 65537, 131101, 262147, 524309, 1048583,
647     2097169, 4194319, 8388617, 16777259, 33554467 };
648
649 // Twice the approximate gap between sampling actions.
650 // I.e., we take one sample approximately once every
651 //      tcmalloc_sample_parameter/2
652 // bytes of allocation, i.e., ~ once every 128KB.
653 // Must be a prime number.
654 #ifdef NO_TCMALLOC_SAMPLES
655 DEFINE_int64(tcmalloc_sample_parameter, 0,
656              "Unused: code is compiled with NO_TCMALLOC_SAMPLES");
657 static size_t sample_period = 0;
658 #else
659 DEFINE_int64(tcmalloc_sample_parameter, 262147,
660          "Twice the approximate gap between sampling actions."
661          " Must be a prime number. Otherwise will be rounded up to a "
662          " larger prime number");
663 static size_t sample_period = 262147;
664 #endif
665
666 // Protects sample_period above
667 static SpinLock sample_period_lock = SPINLOCK_INITIALIZER;
668
669 // Parameters for controlling how fast memory is returned to the OS.
670
671 DEFINE_double(tcmalloc_release_rate, 1,
672               "Rate at which we release unused memory to the system.  "
673               "Zero means we never release memory back to the system.  "
674               "Increase this flag to return memory faster; decrease it "
675               "to return memory slower.  Reasonable rates are in the "
676               "range [0,10]");
677
678 //-------------------------------------------------------------------
679 // Mapping from size to size_class and vice versa
680 //-------------------------------------------------------------------
681
682 // Sizes <= 1024 have an alignment >= 8.  So for such sizes we have an
683 // array indexed by ceil(size/8).  Sizes > 1024 have an alignment >= 128.
684 // So for these larger sizes we have an array indexed by ceil(size/128).
685 //
686 // We flatten both logical arrays into one physical array and use
687 // arithmetic to compute an appropriate index.  The constants used by
688 // ClassIndex() were selected to make the flattening work.
689 //
690 // Examples:
691 //   Size       Expression                      Index
692 //   -------------------------------------------------------
693 //   0          (0 + 7) / 8                     0
694 //   1          (1 + 7) / 8                     1
695 //   ...
696 //   1024       (1024 + 7) / 8                  128
697 //   1025       (1025 + 127 + (120<<7)) / 128   129
698 //   ...
699 //   32768      (32768 + 127 + (120<<7)) / 128  376
700 static const size_t kMaxSmallSize = 1024;
701 static const int shift_amount[2] = { 3, 7 };  // For divides by 8 or 128
702 static const int add_amount[2] = { 7, 127 + (120 << 7) };
703 static unsigned char class_array[377];
704
705 // Compute index of the class_array[] entry for a given size
706 static inline int ClassIndex(size_t s) {
707   const int i = (s > kMaxSmallSize);
708   return static_cast<int>((s + add_amount[i]) >> shift_amount[i]);
709 }
710
711 // Mapping from size class to max size storable in that class
712 static size_t class_to_size[K_NUM_CLASSES_MAX];
713
714 // Mapping from size class to number of pages to allocate at a time
715 static size_t class_to_pages[K_NUM_CLASSES_MAX];
716
717 // Hardened singly linked list.  We make this a class to allow compiler to
718 // statically prevent mismatching hardened and non-hardened list
719 class HardenedSLL {
720 public:
721     static ALWAYS_INLINE HardenedSLL create(void* value)
722     {
723         HardenedSLL result;
724         result.m_value = value;
725         return result;
726     }
727
728     static ALWAYS_INLINE HardenedSLL null()
729     {
730         HardenedSLL result;
731         result.m_value = 0;
732         return result;
733     }
734
735     ALWAYS_INLINE void setValue(void* value) { m_value = value; }
736     ALWAYS_INLINE void* value() const { return m_value; }
737     ALWAYS_INLINE bool operator!() const { return !m_value; }
738     typedef void* (HardenedSLL::*UnspecifiedBoolType);
739     ALWAYS_INLINE operator UnspecifiedBoolType() const { return m_value ? &HardenedSLL::m_value : 0; }
740
741     bool operator!=(const HardenedSLL& other) const { return m_value != other.m_value; }
742     bool operator==(const HardenedSLL& other) const { return m_value == other.m_value; }
743
744 private:
745     void* m_value;
746 };
747
748 // TransferCache is used to cache transfers of num_objects_to_move[size_class]
749 // back and forth between thread caches and the central cache for a given size
750 // class.
751 struct TCEntry {
752   HardenedSLL head;  // Head of chain of objects.
753   HardenedSLL tail;  // Tail of chain of objects.
754 };
755 // A central cache freelist can have anywhere from 0 to kNumTransferEntries
756 // slots to put link list chains into.  To keep memory usage bounded the total
757 // number of TCEntries across size classes is fixed.  Currently each size
758 // class is initially given one TCEntry which also means that the maximum any
759 // one class can have is kNumClasses.
760 #define K_NUM_TRANSFER_ENTRIES_MAX static_cast<int>(K_NUM_CLASSES_MAX)
761 #define kNumTransferEntries static_cast<int>(kNumClasses)
762
763 // Note: the following only works for "n"s that fit in 32-bits, but
764 // that is fine since we only use it for small sizes.
765 static inline int LgFloor(size_t n) {
766   int log = 0;
767   for (int i = 4; i >= 0; --i) {
768     int shift = (1 << i);
769     size_t x = n >> shift;
770     if (x != 0) {
771       n = x;
772       log += shift;
773     }
774   }
775   ASSERT(n == 1);
776   return log;
777 }
778
779 // Functions for using our simple hardened singly linked list
780 static ALWAYS_INLINE HardenedSLL SLL_Next(HardenedSLL t, uintptr_t entropy) {
781     void* tValueNext = *(reinterpret_cast<void**>(t.value()));
782     return HardenedSLL::create(XOR_MASK_PTR_WITH_KEY(tValueNext, t.value(), entropy));
783 }
784
785 static ALWAYS_INLINE void SLL_SetNext(HardenedSLL t, HardenedSLL n, uintptr_t entropy) {
786     *(reinterpret_cast<void**>(t.value())) = XOR_MASK_PTR_WITH_KEY(n.value(), t.value(), entropy);
787 }
788
789 static ALWAYS_INLINE void SLL_Push(HardenedSLL* list, HardenedSLL element, uintptr_t entropy) {
790   SLL_SetNext(element, *list, entropy);
791   *list = element;
792 }
793
794 static ALWAYS_INLINE HardenedSLL SLL_Pop(HardenedSLL *list, uintptr_t entropy) {
795   HardenedSLL result = *list;
796   *list = SLL_Next(*list, entropy);
797   return result;
798 }
799
800 // Remove N elements from a linked list to which head points.  head will be
801 // modified to point to the new head.  start and end will point to the first
802 // and last nodes of the range.  Note that end will point to NULL after this
803 // function is called.
804
805 static ALWAYS_INLINE void SLL_PopRange(HardenedSLL* head, int N, HardenedSLL *start, HardenedSLL *end, uintptr_t entropy) {
806   if (N == 0) {
807     *start = HardenedSLL::null();
808     *end = HardenedSLL::null();
809     return;
810   }
811
812   HardenedSLL tmp = *head;
813   for (int i = 1; i < N; ++i) {
814     tmp = SLL_Next(tmp, entropy);
815   }
816
817   *start = *head;
818   *end = tmp;
819   *head = SLL_Next(tmp, entropy);
820   // Unlink range from list.
821   SLL_SetNext(tmp, HardenedSLL::null(), entropy);
822 }
823
824 static ALWAYS_INLINE void SLL_PushRange(HardenedSLL *head, HardenedSLL start, HardenedSLL end, uintptr_t entropy) {
825   if (!start) return;
826   SLL_SetNext(end, *head, entropy);
827   *head = start;
828 }
829
830 // Setup helper functions.
831
832 static ALWAYS_INLINE size_t SizeClass(size_t size) {
833   return class_array[ClassIndex(size)];
834 }
835
836 // Get the byte-size for a specified class
837 static ALWAYS_INLINE size_t ByteSizeForClass(size_t cl) {
838   return class_to_size[cl];
839 }
840 static int NumMoveSize(size_t size) {
841   if (size == 0) return 0;
842   // Use approx 64k transfers between thread and central caches.
843   int num = static_cast<int>(64.0 * 1024.0 / size);
844   if (num < 2) num = 2;
845   // Clamp well below kMaxFreeListLength to avoid ping pong between central
846   // and thread caches.
847   if (num > static_cast<int>(0.8 * kMaxFreeListLength))
848     num = static_cast<int>(0.8 * kMaxFreeListLength);
849
850   // Also, avoid bringing in too many objects into small object free
851   // lists.  There are lots of such lists, and if we allow each one to
852   // fetch too many at a time, we end up having to scavenge too often
853   // (especially when there are lots of threads and each thread gets a
854   // small allowance for its thread cache).
855   //
856   // TODO: Make thread cache free list sizes dynamic so that we do not
857   // have to equally divide a fixed resource amongst lots of threads.
858   if (num > 32) num = 32;
859
860   return num;
861 }
862
863 // Initialize the mapping arrays
864 static void InitSizeClasses() {
865 #if OS(DARWIN)
866   kPageShift = vm_page_shift;
867   switch (kPageShift) {
868   case 12:
869     kNumClasses = 68;
870     break;
871   case 14:
872     kNumClasses = 77;
873     break;
874   default:
875     CRASH();
876   };
877 #else
878   kPageShift = 12;
879   kNumClasses = 68;
880 #endif
881   kPageSize = 1 << kPageShift;
882   kMaxValidPages = (~static_cast<Length>(0)) >> kPageShift;
883
884   // Do some sanity checking on add_amount[]/shift_amount[]/class_array[]
885   if (ClassIndex(0) < 0) {
886     MESSAGE("Invalid class index %d for size 0\n", ClassIndex(0));
887     CRASH();
888   }
889   if (static_cast<size_t>(ClassIndex(kMaxSize)) >= sizeof(class_array)) {
890     MESSAGE("Invalid class index %d for kMaxSize\n", ClassIndex(kMaxSize));
891     CRASH();
892   }
893
894   // Compute the size classes we want to use
895   size_t sc = 1;   // Next size class to assign
896   unsigned char alignshift = kAlignShift;
897   int last_lg = -1;
898   for (size_t size = kAlignment; size <= kMaxSize; size += (1 << alignshift)) {
899     int lg = LgFloor(size);
900     if (lg > last_lg) {
901       // Increase alignment every so often.
902       //
903       // Since we double the alignment every time size doubles and
904       // size >= 128, this means that space wasted due to alignment is
905       // at most 16/128 i.e., 12.5%.  Plus we cap the alignment at 256
906       // bytes, so the space wasted as a percentage starts falling for
907       // sizes > 2K.
908       if ((lg >= 7) && (alignshift < 8)) {
909         alignshift++;
910       }
911       last_lg = lg;
912     }
913
914     // Allocate enough pages so leftover is less than 1/8 of total.
915     // This bounds wasted space to at most 12.5%.
916     size_t psize = kPageSize;
917     while ((psize % size) > (psize >> 3)) {
918       psize += kPageSize;
919     }
920     const size_t my_pages = psize >> kPageShift;
921
922     if (sc > 1 && my_pages == class_to_pages[sc-1]) {
923       // See if we can merge this into the previous class without
924       // increasing the fragmentation of the previous class.
925       const size_t my_objects = (my_pages << kPageShift) / size;
926       const size_t prev_objects = (class_to_pages[sc-1] << kPageShift)
927                                   / class_to_size[sc-1];
928       if (my_objects == prev_objects) {
929         // Adjust last class to include this size
930         class_to_size[sc-1] = size;
931         continue;
932       }
933     }
934
935     // Add new class
936     class_to_pages[sc] = my_pages;
937     class_to_size[sc] = size;
938     sc++;
939   }
940   if (sc != kNumClasses) {
941     MESSAGE("wrong number of size classes: found %" PRIuS " instead of %d\n",
942             sc, int(kNumClasses));
943     CRASH();
944   }
945
946   // Initialize the mapping arrays
947   int next_size = 0;
948   for (unsigned char c = 1; c < kNumClasses; c++) {
949     const size_t max_size_in_class = class_to_size[c];
950     for (size_t s = next_size; s <= max_size_in_class; s += kAlignment) {
951       class_array[ClassIndex(s)] = c;
952     }
953     next_size = static_cast<int>(max_size_in_class + kAlignment);
954   }
955
956   // Double-check sizes just to be safe
957   for (size_t size = 0; size <= kMaxSize; size++) {
958     const size_t sc = SizeClass(size);
959     if (sc == 0) {
960       MESSAGE("Bad size class %" PRIuS " for %" PRIuS "\n", sc, size);
961       CRASH();
962     }
963     if (sc > 1 && size <= class_to_size[sc-1]) {
964       MESSAGE("Allocating unnecessarily large class %" PRIuS " for %" PRIuS
965               "\n", sc, size);
966       CRASH();
967     }
968     if (sc >= kNumClasses) {
969       MESSAGE("Bad size class %" PRIuS " for %" PRIuS "\n", sc, size);
970       CRASH();
971     }
972     const size_t s = class_to_size[sc];
973     if (size > s) {
974      MESSAGE("Bad size %" PRIuS " for %" PRIuS " (sc = %" PRIuS ")\n", s, size, sc);
975       CRASH();
976     }
977     if (s == 0) {
978       MESSAGE("Bad size %" PRIuS " for %" PRIuS " (sc = %" PRIuS ")\n", s, size, sc);
979       CRASH();
980     }
981   }
982
983   // Initialize the num_objects_to_move array.
984   for (size_t cl = 1; cl  < kNumClasses; ++cl) {
985     num_objects_to_move[cl] = NumMoveSize(ByteSizeForClass(cl));
986   }
987
988 #ifndef WTF_CHANGES
989   if (false) {
990     // Dump class sizes and maximum external wastage per size class
991     for (size_t cl = 1; cl  < kNumClasses; ++cl) {
992       const int alloc_size = class_to_pages[cl] << kPageShift;
993       const int alloc_objs = alloc_size / class_to_size[cl];
994       const int min_used = (class_to_size[cl-1] + 1) * alloc_objs;
995       const int max_waste = alloc_size - min_used;
996       MESSAGE("SC %3d [ %8d .. %8d ] from %8d ; %2.0f%% maxwaste\n",
997               int(cl),
998               int(class_to_size[cl-1] + 1),
999               int(class_to_size[cl]),
1000               int(class_to_pages[cl] << kPageShift),
1001               max_waste * 100.0 / alloc_size
1002               );
1003     }
1004   }
1005 #endif
1006 }
1007
1008 // -------------------------------------------------------------------------
1009 // Simple allocator for objects of a specified type.  External locking
1010 // is required before accessing one of these objects.
1011 // -------------------------------------------------------------------------
1012
1013 // Metadata allocator -- keeps stats about how many bytes allocated
1014 static uint64_t metadata_system_bytes = 0;
1015 static void* MetaDataAlloc(size_t bytes) {
1016   void* result = TCMalloc_SystemAlloc(bytes, 0);
1017   if (result != NULL) {
1018     metadata_system_bytes += bytes;
1019   }
1020   return result;
1021 }
1022
1023 #if defined(WTF_CHANGES) && OS(DARWIN)
1024 class RemoteMemoryReader;
1025 #endif
1026
1027 template <class T>
1028 class PageHeapAllocator {
1029  private:
1030   // How much to allocate from system at a time
1031   static const size_t kAllocIncrement = 32 << 10;
1032
1033   // Aligned size of T
1034   static const size_t kAlignedSize
1035   = (((sizeof(T) + kAlignment - 1) / kAlignment) * kAlignment);
1036
1037   // Free area from which to carve new objects
1038   char* free_area_;
1039   size_t free_avail_;
1040
1041   // Linked list of all regions allocated by this allocator
1042   HardenedSLL allocated_regions_;
1043
1044   // Free list of already carved objects
1045   HardenedSLL free_list_;
1046
1047   // Number of allocated but unfreed objects
1048   int inuse_;
1049   uintptr_t entropy_;
1050
1051  public:
1052   void Init(uintptr_t entropy) {
1053     ASSERT(kAlignedSize <= kAllocIncrement);
1054     inuse_ = 0;
1055     allocated_regions_ = HardenedSLL::null();
1056     free_area_ = NULL;
1057     free_avail_ = 0;
1058     free_list_.setValue(NULL);
1059     entropy_ = entropy;
1060   }
1061
1062   T* New() {
1063     // Consult free list
1064     void* result;
1065     if (free_list_) {
1066       result = free_list_.value();
1067       free_list_ = SLL_Next(free_list_, entropy_);
1068     } else {
1069       if (free_avail_ < kAlignedSize) {
1070         // Need more room
1071         char* new_allocation = reinterpret_cast<char*>(MetaDataAlloc(kAllocIncrement));
1072         if (!new_allocation)
1073           CRASH();
1074
1075         HardenedSLL new_head = HardenedSLL::create(new_allocation);
1076         SLL_SetNext(new_head, allocated_regions_, entropy_);
1077         allocated_regions_ = new_head;
1078         free_area_ = new_allocation + kAlignedSize;
1079         free_avail_ = kAllocIncrement - kAlignedSize;
1080       }
1081       result = free_area_;
1082       free_area_ += kAlignedSize;
1083       free_avail_ -= kAlignedSize;
1084     }
1085     inuse_++;
1086     return reinterpret_cast<T*>(result);
1087   }
1088
1089   void Delete(T* p) {
1090     HardenedSLL new_head = HardenedSLL::create(p);
1091     SLL_SetNext(new_head, free_list_, entropy_);
1092     free_list_ = new_head;
1093     inuse_--;
1094   }
1095
1096   int inuse() const { return inuse_; }
1097
1098 #if defined(WTF_CHANGES) && OS(DARWIN)
1099   template <typename Recorder>
1100   void recordAdministrativeRegions(Recorder&, const RemoteMemoryReader&);
1101 #endif
1102 };
1103
1104 // -------------------------------------------------------------------------
1105 // Span - a contiguous run of pages
1106 // -------------------------------------------------------------------------
1107
1108 // Type that can hold a page number
1109 typedef uintptr_t PageID;
1110
1111 // Convert byte size into pages.  This won't overflow, but may return
1112 // an unreasonably large value if bytes is huge enough.
1113 static inline Length pages(size_t bytes) {
1114   ASSERT(kPageShift && kNumClasses && kPageSize);
1115   return (bytes >> kPageShift) +
1116       ((bytes & (kPageSize - 1)) > 0 ? 1 : 0);
1117 }
1118
1119 // Convert a user size into the number of bytes that will actually be
1120 // allocated
1121 static size_t AllocationSize(size_t bytes) {
1122   ASSERT(kPageShift && kNumClasses && kPageSize);
1123   if (bytes > kMaxSize) {
1124     // Large object: we allocate an integral number of pages
1125     ASSERT(bytes <= (kMaxValidPages << kPageShift));
1126     return pages(bytes) << kPageShift;
1127   } else {
1128     // Small object: find the size class to which it belongs
1129     return ByteSizeForClass(SizeClass(bytes));
1130   }
1131 }
1132
1133 enum {
1134     kSpanCookieBits = 10,
1135     kSpanCookieMask = (1 << 10) - 1,
1136     kSpanThisShift = 7
1137 };
1138
1139 static uint32_t spanValidationCookie;
1140 static uint32_t spanInitializerCookie()
1141 {
1142     static uint32_t value = EntropySource<sizeof(uint32_t)>::value() & kSpanCookieMask;
1143     spanValidationCookie = value;
1144     return value;
1145 }
1146
1147 // Information kept for a span (a contiguous run of pages).
1148 struct Span {
1149   PageID        start;          // Starting page number
1150   Length        length;         // Number of pages in span
1151   Span* next(uintptr_t entropy) const { return XOR_MASK_PTR_WITH_KEY(m_next, this, entropy); }
1152   Span* remoteNext(const Span* remoteSpanPointer, uintptr_t entropy) const { return XOR_MASK_PTR_WITH_KEY(m_next, remoteSpanPointer, entropy); }
1153   Span* prev(uintptr_t entropy) const { return XOR_MASK_PTR_WITH_KEY(m_prev, this, entropy); }
1154   void setNext(Span* next, uintptr_t entropy) { m_next = XOR_MASK_PTR_WITH_KEY(next, this, entropy); }
1155   void setPrev(Span* prev, uintptr_t entropy) { m_prev = XOR_MASK_PTR_WITH_KEY(prev, this, entropy); }
1156
1157 private:
1158   Span*         m_next;           // Used when in link list
1159   Span*         m_prev;           // Used when in link list
1160 public:
1161   HardenedSLL    objects;        // Linked list of free objects
1162   unsigned int  free : 1;       // Is the span free
1163 #ifndef NO_TCMALLOC_SAMPLES
1164   unsigned int  sample : 1;     // Sampled object?
1165 #endif
1166   unsigned int  sizeclass : 8;  // Size-class for small objects (or 0)
1167   unsigned int  refcount : 11;  // Number of non-free objects
1168   bool decommitted : 1;
1169   void initCookie()
1170   {
1171       m_cookie = ((reinterpret_cast<uintptr_t>(this) >> kSpanThisShift) & kSpanCookieMask) ^ spanInitializerCookie();
1172   }
1173   void clearCookie() { m_cookie = 0; }
1174   bool isValid() const
1175   {
1176       return (((reinterpret_cast<uintptr_t>(this) >> kSpanThisShift) & kSpanCookieMask) ^ m_cookie) == spanValidationCookie;
1177   }
1178 private:
1179   uint32_t m_cookie : kSpanCookieBits;
1180
1181 #undef SPAN_HISTORY
1182 #ifdef SPAN_HISTORY
1183   // For debugging, we can keep a log events per span
1184   int nexthistory;
1185   char history[64];
1186   int value[64];
1187 #endif
1188 };
1189
1190 #define ASSERT_SPAN_COMMITTED(span) ASSERT(!span->decommitted)
1191
1192 #ifdef SPAN_HISTORY
1193 void Event(Span* span, char op, int v = 0) {
1194   span->history[span->nexthistory] = op;
1195   span->value[span->nexthistory] = v;
1196   span->nexthistory++;
1197   if (span->nexthistory == sizeof(span->history)) span->nexthistory = 0;
1198 }
1199 #else
1200 #define Event(s,o,v) ((void) 0)
1201 #endif
1202
1203 // Allocator/deallocator for spans
1204 static PageHeapAllocator<Span> span_allocator;
1205 static Span* NewSpan(PageID p, Length len) {
1206   Span* result = span_allocator.New();
1207   memset(result, 0, sizeof(*result));
1208   result->start = p;
1209   result->length = len;
1210   result->initCookie();
1211 #ifdef SPAN_HISTORY
1212   result->nexthistory = 0;
1213 #endif
1214   return result;
1215 }
1216
1217 static inline void DeleteSpan(Span* span) {
1218   RELEASE_ASSERT(span->isValid());
1219 #ifndef NDEBUG
1220   // In debug mode, trash the contents of deleted Spans
1221   memset(span, 0x3f, sizeof(*span));
1222 #endif
1223   span->clearCookie();
1224   span_allocator.Delete(span);
1225 }
1226
1227 // -------------------------------------------------------------------------
1228 // Doubly linked list of spans.
1229 // -------------------------------------------------------------------------
1230
1231 static inline void DLL_Init(Span* list, uintptr_t entropy) {
1232   list->setNext(list, entropy);
1233   list->setPrev(list, entropy);
1234 }
1235
1236 static inline void DLL_Remove(Span* span, uintptr_t entropy) {
1237   span->prev(entropy)->setNext(span->next(entropy), entropy);
1238   span->next(entropy)->setPrev(span->prev(entropy), entropy);
1239   span->setPrev(NULL, entropy);
1240   span->setNext(NULL, entropy);
1241 }
1242
1243 static ALWAYS_INLINE bool DLL_IsEmpty(const Span* list, uintptr_t entropy) {
1244   return list->next(entropy) == list;
1245 }
1246
1247 static int DLL_Length(const Span* list, uintptr_t entropy) {
1248   int result = 0;
1249   for (Span* s = list->next(entropy); s != list; s = s->next(entropy)) {
1250     result++;
1251   }
1252   return result;
1253 }
1254
1255 #if 0 /* Not needed at the moment -- causes compiler warnings if not used */
1256 static void DLL_Print(const char* label, const Span* list) {
1257   MESSAGE("%-10s %p:", label, list);
1258   for (const Span* s = list->next; s != list; s = s->next) {
1259     MESSAGE(" <%p,%u,%u>", s, s->start, s->length);
1260   }
1261   MESSAGE("\n");
1262 }
1263 #endif
1264
1265 static inline void DLL_Prepend(Span* list, Span* span, uintptr_t entropy) {
1266   span->setNext(list->next(entropy), entropy);
1267   span->setPrev(list, entropy);
1268   list->next(entropy)->setPrev(span, entropy);
1269   list->setNext(span, entropy);
1270 }
1271
1272 //-------------------------------------------------------------------
1273 // Data kept per size-class in central cache
1274 //-------------------------------------------------------------------
1275
1276 class TCMalloc_Central_FreeList {
1277  public:
1278   void Init(size_t cl, uintptr_t entropy);
1279
1280   // These methods all do internal locking.
1281
1282   // Insert the specified range into the central freelist.  N is the number of
1283   // elements in the range.
1284   void InsertRange(HardenedSLL start, HardenedSLL end, int N);
1285
1286   // Returns the actual number of fetched elements into N.
1287   void RemoveRange(HardenedSLL* start, HardenedSLL* end, int *N);
1288
1289   // Returns the number of free objects in cache.
1290   size_t length() {
1291     SpinLockHolder h(&lock_);
1292     return counter_;
1293   }
1294
1295   // Returns the number of free objects in the transfer cache.
1296   int tc_length() {
1297     SpinLockHolder h(&lock_);
1298     return used_slots_ * num_objects_to_move[size_class_];
1299   }
1300
1301 #ifdef WTF_CHANGES
1302   template <class Finder, class Reader>
1303   void enumerateFreeObjects(Finder& finder, const Reader& reader, TCMalloc_Central_FreeList* remoteCentralFreeList)
1304   {
1305     {
1306       static const ptrdiff_t emptyOffset = reinterpret_cast<const char*>(&empty_) - reinterpret_cast<const char*>(this);
1307       Span* remoteEmpty = reinterpret_cast<Span*>(reinterpret_cast<char*>(remoteCentralFreeList) + emptyOffset);
1308       Span* remoteSpan = nonempty_.remoteNext(remoteEmpty, entropy_);
1309       for (Span* span = reader(remoteEmpty); span && span != &empty_; remoteSpan = span->remoteNext(remoteSpan, entropy_), span = (remoteSpan ? reader(remoteSpan) : 0))
1310         ASSERT(!span->objects);
1311     }
1312
1313     ASSERT(!nonempty_.objects);
1314     static const ptrdiff_t nonemptyOffset = reinterpret_cast<const char*>(&nonempty_) - reinterpret_cast<const char*>(this);
1315
1316     Span* remoteNonempty = reinterpret_cast<Span*>(reinterpret_cast<char*>(remoteCentralFreeList) + nonemptyOffset);
1317     Span* remoteSpan = nonempty_.remoteNext(remoteNonempty, entropy_);
1318
1319     for (Span* span = reader(remoteSpan); span && remoteSpan != remoteNonempty; remoteSpan = span->remoteNext(remoteSpan, entropy_), span = (remoteSpan ? reader(remoteSpan) : 0)) {
1320       for (HardenedSLL nextObject = span->objects; nextObject; nextObject.setValue(reader.nextEntryInHardenedLinkedList(reinterpret_cast<void**>(nextObject.value()), entropy_))) {
1321         finder.visit(nextObject.value());
1322       }
1323     }
1324
1325     for (int slot = 0; slot < used_slots_; ++slot) {
1326       for (HardenedSLL entry = tc_slots_[slot].head; entry; entry.setValue(reader.nextEntryInHardenedLinkedList(reinterpret_cast<void**>(entry.value()), entropy_)))
1327         finder.visit(entry.value());
1328     }
1329   }
1330 #endif
1331
1332   uintptr_t entropy() const { return entropy_; }
1333  private:
1334   // REQUIRES: lock_ is held
1335   // Remove object from cache and return.
1336   // Return NULL if no free entries in cache.
1337   HardenedSLL FetchFromSpans();
1338
1339   // REQUIRES: lock_ is held
1340   // Remove object from cache and return.  Fetches
1341   // from pageheap if cache is empty.  Only returns
1342   // NULL on allocation failure.
1343   HardenedSLL FetchFromSpansSafe();
1344
1345   // REQUIRES: lock_ is held
1346   // Release a linked list of objects to spans.
1347   // May temporarily release lock_.
1348   void ReleaseListToSpans(HardenedSLL start);
1349
1350   // REQUIRES: lock_ is held
1351   // Release an object to spans.
1352   // May temporarily release lock_.
1353   ALWAYS_INLINE void ReleaseToSpans(HardenedSLL object);
1354
1355   // REQUIRES: lock_ is held
1356   // Populate cache by fetching from the page heap.
1357   // May temporarily release lock_.
1358   ALWAYS_INLINE void Populate();
1359
1360   // REQUIRES: lock is held.
1361   // Tries to make room for a TCEntry.  If the cache is full it will try to
1362   // expand it at the cost of some other cache size.  Return false if there is
1363   // no space.
1364   bool MakeCacheSpace();
1365
1366   // REQUIRES: lock_ for locked_size_class is held.
1367   // Picks a "random" size class to steal TCEntry slot from.  In reality it
1368   // just iterates over the sizeclasses but does so without taking a lock.
1369   // Returns true on success.
1370   // May temporarily lock a "random" size class.
1371   static ALWAYS_INLINE bool EvictRandomSizeClass(size_t locked_size_class, bool force);
1372
1373   // REQUIRES: lock_ is *not* held.
1374   // Tries to shrink the Cache.  If force is true it will relase objects to
1375   // spans if it allows it to shrink the cache.  Return false if it failed to
1376   // shrink the cache.  Decrements cache_size_ on succeess.
1377   // May temporarily take lock_.  If it takes lock_, the locked_size_class
1378   // lock is released to the thread from holding two size class locks
1379   // concurrently which could lead to a deadlock.
1380   bool ShrinkCache(int locked_size_class, bool force);
1381
1382   // This lock protects all the data members.  cached_entries and cache_size_
1383   // may be looked at without holding the lock.
1384   SpinLock lock_;
1385
1386   // We keep linked lists of empty and non-empty spans.
1387   size_t   size_class_;     // My size class
1388   Span     empty_;          // Dummy header for list of empty spans
1389   Span     nonempty_;       // Dummy header for list of non-empty spans
1390   size_t   counter_;        // Number of free objects in cache entry
1391
1392   // Here we reserve space for TCEntry cache slots.  Since one size class can
1393   // end up getting all the TCEntries quota in the system we just preallocate
1394   // sufficient number of entries here.
1395   TCEntry tc_slots_[K_NUM_TRANSFER_ENTRIES_MAX];
1396
1397   // Number of currently used cached entries in tc_slots_.  This variable is
1398   // updated under a lock but can be read without one.
1399   int32_t used_slots_;
1400   // The current number of slots for this size class.  This is an
1401   // adaptive value that is increased if there is lots of traffic
1402   // on a given size class.
1403   int32_t cache_size_;
1404   uintptr_t entropy_;
1405 };
1406
1407 #if COMPILER(CLANG) && defined(__has_warning)
1408 #pragma clang diagnostic push
1409 #if __has_warning("-Wunused-private-field")
1410 #pragma clang diagnostic ignored "-Wunused-private-field"
1411 #endif
1412 #endif
1413
1414 // Pad each CentralCache object to multiple of 64 bytes
1415 template <size_t SizeToPad>
1416 class TCMalloc_Central_FreeListPadded_Template : public TCMalloc_Central_FreeList {
1417 private:
1418     char pad[64 - SizeToPad];
1419 };
1420
1421 // Zero-size specialization to avoid compiler error when TCMalloc_Central_FreeList happens
1422 // to be exactly 64 bytes.
1423 template <> class TCMalloc_Central_FreeListPadded_Template<0> : public TCMalloc_Central_FreeList {
1424 };
1425
1426 typedef TCMalloc_Central_FreeListPadded_Template<sizeof(TCMalloc_Central_FreeList) % 64> TCMalloc_Central_FreeListPadded;
1427
1428 #if COMPILER(CLANG) && defined(__has_warning)
1429 #pragma clang diagnostic pop
1430 #endif
1431
1432 #if OS(DARWIN)
1433 struct Span;
1434 class TCMalloc_PageHeap;
1435 class TCMalloc_ThreadCache;
1436 template <typename T> class PageHeapAllocator;
1437
1438 class FastMallocZone {
1439 public:
1440     static void init();
1441
1442     static kern_return_t enumerate(task_t, void*, unsigned typeMmask, vm_address_t zoneAddress, memory_reader_t, vm_range_recorder_t);
1443     static size_t goodSize(malloc_zone_t*, size_t size) { return size; }
1444     static boolean_t check(malloc_zone_t*) { return true; }
1445     static void  print(malloc_zone_t*, boolean_t) { }
1446     static void log(malloc_zone_t*, void*) { }
1447     static void forceLock(malloc_zone_t*) { }
1448     static void forceUnlock(malloc_zone_t*) { }
1449     static void statistics(malloc_zone_t*, malloc_statistics_t* stats) { memset(stats, 0, sizeof(malloc_statistics_t)); }
1450
1451 private:
1452     FastMallocZone(TCMalloc_PageHeap*, TCMalloc_ThreadCache**, TCMalloc_Central_FreeListPadded*, PageHeapAllocator<Span>*, PageHeapAllocator<TCMalloc_ThreadCache>*);
1453     static size_t size(malloc_zone_t*, const void*);
1454     static void* zoneMalloc(malloc_zone_t*, size_t);
1455     static void* zoneCalloc(malloc_zone_t*, size_t numItems, size_t size);
1456     static void zoneFree(malloc_zone_t*, void*);
1457     static void* zoneRealloc(malloc_zone_t*, void*, size_t);
1458     static void* zoneValloc(malloc_zone_t*, size_t) { LOG_ERROR("valloc is not supported"); return 0; }
1459     static void zoneDestroy(malloc_zone_t*) { }
1460
1461     malloc_zone_t m_zone;
1462     TCMalloc_PageHeap* m_pageHeap;
1463     TCMalloc_ThreadCache** m_threadHeaps;
1464     TCMalloc_Central_FreeListPadded* m_centralCaches;
1465     PageHeapAllocator<Span>* m_spanAllocator;
1466     PageHeapAllocator<TCMalloc_ThreadCache>* m_pageHeapAllocator;
1467 };
1468
1469 // This method declaration, and the constants below, are taken from Libc/gen/malloc.c.
1470 extern "C" void (*malloc_logger)(uint32_t typeFlags, uintptr_t zone, uintptr_t size, uintptr_t pointer, uintptr_t returnValue, uint32_t numberOfFramesToSkip);
1471
1472 #endif
1473
1474 class MallocHook {
1475     static bool stackLoggingEnabled;
1476
1477 #if OS(DARWIN)
1478     
1479     enum StackLoggingType {
1480         StackLoggingTypeAlloc = 2,
1481         StackLoggingTypeDealloc = 4,
1482     };
1483
1484     static void record(uint32_t typeFlags, uintptr_t zone, uintptr_t size, void* pointer, void* returnValue, uint32_t numberOfFramesToSkip)
1485     {
1486         malloc_logger(typeFlags, zone, size, reinterpret_cast<uintptr_t>(pointer), reinterpret_cast<uintptr_t>(returnValue), numberOfFramesToSkip);
1487     }
1488
1489     static NEVER_INLINE void recordAllocation(void* pointer, size_t size)
1490     {
1491         // StackLoggingTypeAlloc takes the newly-allocated address in the returnValue argument, the size of the allocation
1492         // in the size argument and ignores all other arguments.
1493         record(StackLoggingTypeAlloc, 0, size, 0, pointer, 0);
1494     }
1495
1496     static NEVER_INLINE void recordDeallocation(void* pointer)
1497     {
1498         // StackLoggingTypeDealloc takes the pointer in the size argument and ignores all other arguments.
1499         record(StackLoggingTypeDealloc, 0, reinterpret_cast<uintptr_t>(pointer), 0, 0, 0);
1500     }
1501
1502 #endif
1503
1504 public:
1505     static void init()
1506     {
1507 #if OS(DARWIN)
1508         // If the system allocator's malloc_logger has been set up then stack logging is enabled.
1509         stackLoggingEnabled = malloc_logger;
1510 #endif
1511     }
1512
1513 #if OS(DARWIN)
1514     static ALWAYS_INLINE void InvokeNewHook(void* pointer, size_t size)
1515     {
1516         if (UNLIKELY(stackLoggingEnabled))
1517             recordAllocation(pointer, size);
1518     }
1519
1520     static ALWAYS_INLINE void InvokeDeleteHook(void* pointer)
1521     {
1522
1523         if (UNLIKELY(stackLoggingEnabled))
1524             recordDeallocation(pointer);
1525     }
1526 #else
1527     static ALWAYS_INLINE void InvokeNewHook(void*, size_t) { }
1528     static ALWAYS_INLINE void InvokeDeleteHook(void*) { }
1529 #endif
1530 };
1531 bool MallocHook::stackLoggingEnabled = false;
1532
1533 #endif
1534
1535 #ifndef WTF_CHANGES
1536 // This #ifdef should almost never be set.  Set NO_TCMALLOC_SAMPLES if
1537 // you're porting to a system where you really can't get a stacktrace.
1538 #ifdef NO_TCMALLOC_SAMPLES
1539 // We use #define so code compiles even if you #include stacktrace.h somehow.
1540 # define GetStackTrace(stack, depth, skip)  (0)
1541 #else
1542 # include <google/stacktrace.h>
1543 #endif
1544 #endif
1545
1546 // Even if we have support for thread-local storage in the compiler
1547 // and linker, the OS may not support it.  We need to check that at
1548 // runtime.  Right now, we have to keep a manual set of "bad" OSes.
1549 #if defined(HAVE_TLS)
1550   static bool kernel_supports_tls = false;      // be conservative
1551   static inline bool KernelSupportsTLS() {
1552     return kernel_supports_tls;
1553   }
1554 # if !HAVE_DECL_UNAME   // if too old for uname, probably too old for TLS
1555     static void CheckIfKernelSupportsTLS() {
1556       kernel_supports_tls = false;
1557     }
1558 # else
1559 #   include <sys/utsname.h>    // DECL_UNAME checked for <sys/utsname.h> too
1560     static void CheckIfKernelSupportsTLS() {
1561       struct utsname buf;
1562       if (uname(&buf) != 0) {   // should be impossible
1563         MESSAGE("uname failed assuming no TLS support (errno=%d)\n", errno);
1564         kernel_supports_tls = false;
1565       } else if (strcasecmp(buf.sysname, "linux") == 0) {
1566         // The linux case: the first kernel to support TLS was 2.6.0
1567         if (buf.release[0] < '2' && buf.release[1] == '.')    // 0.x or 1.x
1568           kernel_supports_tls = false;
1569         else if (buf.release[0] == '2' && buf.release[1] == '.' &&
1570                  buf.release[2] >= '0' && buf.release[2] < '6' &&
1571                  buf.release[3] == '.')                       // 2.0 - 2.5
1572           kernel_supports_tls = false;
1573         else
1574           kernel_supports_tls = true;
1575       } else {        // some other kernel, we'll be optimisitic
1576         kernel_supports_tls = true;
1577       }
1578       // TODO(csilvers): VLOG(1) the tls status once we support RAW_VLOG
1579     }
1580 #  endif  // HAVE_DECL_UNAME
1581 #endif    // HAVE_TLS
1582
1583 // __THROW is defined in glibc systems.  It means, counter-intuitively,
1584 // "This function will never throw an exception."  It's an optional
1585 // optimization tool, but we may need to use it to match glibc prototypes.
1586 #ifndef __THROW    // I guess we're not on a glibc system
1587 # define __THROW   // __THROW is just an optimization, so ok to make it ""
1588 #endif
1589
1590 // -------------------------------------------------------------------------
1591 // Stack traces kept for sampled allocations
1592 //   The following state is protected by pageheap_lock_.
1593 // -------------------------------------------------------------------------
1594
1595 // size/depth are made the same size as a pointer so that some generic
1596 // code below can conveniently cast them back and forth to void*.
1597 static const int kMaxStackDepth = 31;
1598 struct StackTrace {
1599   uintptr_t size;          // Size of object
1600   uintptr_t depth;         // Number of PC values stored in array below
1601   void*     stack[kMaxStackDepth];
1602 };
1603 static PageHeapAllocator<StackTrace> stacktrace_allocator;
1604 static Span sampled_objects;
1605
1606 // -------------------------------------------------------------------------
1607 // Map from page-id to per-page data
1608 // -------------------------------------------------------------------------
1609
1610 // We use PageMap2<> for 32-bit and PageMap3<> for 64-bit machines.
1611 // We also use a simple one-level cache for hot PageID-to-sizeclass mappings,
1612 // because sometimes the sizeclass is all the information we need.
1613
1614 // Selector class -- general selector uses 3-level map
1615 template <int BITS> class MapSelector {
1616  public:
1617   typedef TCMalloc_PageMap3<BITS-K_PAGE_SHIFT_MIN> Type;
1618   typedef PackedCache<BITS, uint64_t> CacheType;
1619 };
1620
1621 #if defined(WTF_CHANGES)
1622 #if CPU(X86_64) || CPU(ARM64)
1623 // On all known X86-64 platforms, the upper 16 bits are always unused and therefore 
1624 // can be excluded from the PageMap key.
1625 // See http://en.wikipedia.org/wiki/X86-64#Virtual_address_space_details
1626
1627 static const size_t kBitsUnusedOn64Bit = 16;
1628 #else
1629 static const size_t kBitsUnusedOn64Bit = 0;
1630 #endif
1631
1632 // A three-level map for 64-bit machines
1633 template <> class MapSelector<64> {
1634  public:
1635   typedef TCMalloc_PageMap3<64 - K_PAGE_SHIFT_MIN - kBitsUnusedOn64Bit> Type;
1636   typedef PackedCache<64, uint64_t> CacheType;
1637 };
1638 #endif
1639
1640 // A two-level map for 32-bit machines
1641 template <> class MapSelector<32> {
1642  public:
1643   typedef TCMalloc_PageMap2<32 - K_PAGE_SHIFT_MIN> Type;
1644   typedef PackedCache<32 - K_PAGE_SHIFT_MIN, uint16_t> CacheType;
1645 };
1646
1647 // -------------------------------------------------------------------------
1648 // Page-level allocator
1649 //  * Eager coalescing
1650 //
1651 // Heap for page-level allocation.  We allow allocating and freeing a
1652 // contiguous runs of pages (called a "span").
1653 // -------------------------------------------------------------------------
1654
1655 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
1656 // The page heap maintains a free list for spans that are no longer in use by
1657 // the central cache or any thread caches. We use a background thread to
1658 // periodically scan the free list and release a percentage of it back to the OS.
1659
1660 // If free_committed_pages_ exceeds kMinimumFreeCommittedPageCount, the
1661 // background thread:
1662 //     - wakes up
1663 //     - pauses for kScavengeDelayInSeconds
1664 //     - returns to the OS a percentage of the memory that remained unused during
1665 //       that pause (kScavengePercentage * min_free_committed_pages_since_last_scavenge_)
1666 // The goal of this strategy is to reduce memory pressure in a timely fashion
1667 // while avoiding thrashing the OS allocator.
1668
1669 // Time delay before the page heap scavenger will consider returning pages to
1670 // the OS.
1671 static const int kScavengeDelayInSeconds = 2;
1672
1673 // Approximate percentage of free committed pages to return to the OS in one
1674 // scavenge.
1675 static const float kScavengePercentage = .5f;
1676
1677 // number of span lists to keep spans in when memory is returned.
1678 static const int kMinSpanListsWithSpans = 32;
1679
1680 // Number of free committed pages that we want to keep around.  The minimum number of pages used when there
1681 // is 1 span in each of the first kMinSpanListsWithSpans spanlists.  Currently 528 pages.
1682 static const size_t kMinimumFreeCommittedPageCount = kMinSpanListsWithSpans * ((1.0f+kMinSpanListsWithSpans) / 2.0f);
1683
1684 #endif
1685
1686 static SpinLock pageheap_lock = SPINLOCK_INITIALIZER;
1687
1688 class TCMalloc_PageHeap {
1689  public:
1690   void init();
1691
1692   // Allocate a run of "n" pages.  Returns zero if out of memory.
1693   Span* New(Length n);
1694
1695   // Delete the span "[p, p+n-1]".
1696   // REQUIRES: span was returned by earlier call to New() and
1697   //           has not yet been deleted.
1698   void Delete(Span* span);
1699
1700   // Mark an allocated span as being used for small objects of the
1701   // specified size-class.
1702   // REQUIRES: span was returned by an earlier call to New()
1703   //           and has not yet been deleted.
1704   void RegisterSizeClass(Span* span, size_t sc);
1705
1706   // Split an allocated span into two spans: one of length "n" pages
1707   // followed by another span of length "span->length - n" pages.
1708   // Modifies "*span" to point to the first span of length "n" pages.
1709   // Returns a pointer to the second span.
1710   //
1711   // REQUIRES: "0 < n < span->length"
1712   // REQUIRES: !span->free
1713   // REQUIRES: span->sizeclass == 0
1714   Span* Split(Span* span, Length n);
1715
1716   // Return the descriptor for the specified page.
1717   inline Span* GetDescriptor(PageID p) const {
1718     return reinterpret_cast<Span*>(pagemap_.get(p));
1719   }
1720
1721 #ifdef WTF_CHANGES
1722   inline Span* GetDescriptorEnsureSafe(PageID p)
1723   {
1724       pagemap_.Ensure(p, 1);
1725       return GetDescriptor(p);
1726   }
1727     
1728   size_t ReturnedBytes() const;
1729 #endif
1730
1731   // Dump state to stderr
1732 #ifndef WTF_CHANGES
1733   void Dump(TCMalloc_Printer* out);
1734 #endif
1735
1736   // Return number of bytes allocated from system
1737   inline uint64_t SystemBytes() const { return system_bytes_; }
1738
1739   // Return number of free bytes in heap
1740   uint64_t FreeBytes() const {
1741     ASSERT(kPageShift && kNumClasses && kPageSize);
1742     return (static_cast<uint64_t>(free_pages_) << kPageShift);
1743   }
1744
1745   bool Check();
1746   size_t CheckList(Span* list, Length min_pages, Length max_pages, bool decommitted);
1747
1748   // Release all pages on the free list for reuse by the OS:
1749   void ReleaseFreePages();
1750   void ReleaseFreeList(Span*, Span*);
1751
1752   // Return 0 if we have no information, or else the correct sizeclass for p.
1753   // Reads and writes to pagemap_cache_ do not require locking.
1754   // The entries are 64 bits on 64-bit hardware and 16 bits on
1755   // 32-bit hardware, and we don't mind raciness as long as each read of
1756   // an entry yields a valid entry, not a partially updated entry.
1757   size_t GetSizeClassIfCached(PageID p) const {
1758     return pagemap_cache_.GetOrDefault(p, 0);
1759   }
1760   void CacheSizeClass(PageID p, size_t cl) const { pagemap_cache_.Put(p, cl); }
1761
1762  private:
1763   // Pick the appropriate map and cache types based on pointer size
1764   typedef MapSelector<8*sizeof(uintptr_t)>::Type PageMap;
1765   typedef MapSelector<8*sizeof(uintptr_t)>::CacheType PageMapCache;
1766   PageMap pagemap_;
1767   mutable PageMapCache pagemap_cache_;
1768
1769   // We segregate spans of a given size into two circular linked
1770   // lists: one for normal spans, and one for spans whose memory
1771   // has been returned to the system.
1772   struct SpanList {
1773     Span        normal;
1774     Span        returned;
1775   };
1776
1777   // List of free spans of length >= kMaxPages
1778   SpanList large_;
1779
1780   // Array mapping from span length to a doubly linked list of free spans
1781   SpanList free_[kMaxPages];
1782
1783   // Number of pages kept in free lists
1784   uintptr_t free_pages_;
1785
1786   // Used for hardening
1787   uintptr_t entropy_;
1788
1789   // Bytes allocated from system
1790   uint64_t system_bytes_;
1791
1792 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
1793   // Number of pages kept in free lists that are still committed.
1794   Length free_committed_pages_;
1795
1796   // Minimum number of free committed pages since last scavenge. (Can be 0 if
1797   // we've committed new pages since the last scavenge.)
1798   Length min_free_committed_pages_since_last_scavenge_;
1799 #endif
1800
1801   bool GrowHeap(Length n);
1802
1803   // REQUIRES   span->length >= n
1804   // Remove span from its free list, and move any leftover part of
1805   // span into appropriate free lists.  Also update "span" to have
1806   // length exactly "n" and mark it as non-free so it can be returned
1807   // to the client.
1808   //
1809   // "released" is true iff "span" was found on a "returned" list.
1810   void Carve(Span* span, Length n, bool released);
1811
1812   void RecordSpan(Span* span) {
1813     pagemap_.set(span->start, span);
1814     if (span->length > 1) {
1815       pagemap_.set(span->start + span->length - 1, span);
1816     }
1817   }
1818   
1819     // Allocate a large span of length == n.  If successful, returns a
1820   // span of exactly the specified length.  Else, returns NULL.
1821   Span* AllocLarge(Length n);
1822
1823 #if !USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
1824   // Incrementally release some memory to the system.
1825   // IncrementalScavenge(n) is called whenever n pages are freed.
1826   void IncrementalScavenge(Length n);
1827 #endif
1828
1829   // Number of pages to deallocate before doing more scavenging
1830   int64_t scavenge_counter_;
1831
1832   // Index of last free list we scavenged
1833   size_t scavenge_index_;
1834   
1835 #if defined(WTF_CHANGES) && OS(DARWIN)
1836   friend class FastMallocZone;
1837 #endif
1838
1839 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
1840   void initializeScavenger();
1841   ALWAYS_INLINE void signalScavenger();
1842   void scavenge();
1843   ALWAYS_INLINE bool shouldScavenge() const;
1844
1845 #if HAVE(DISPATCH_H) || OS(WINDOWS)
1846   void periodicScavenge();
1847   ALWAYS_INLINE bool isScavengerSuspended();
1848   ALWAYS_INLINE void scheduleScavenger();
1849   ALWAYS_INLINE void rescheduleScavenger();
1850   ALWAYS_INLINE void suspendScavenger();
1851 #endif
1852
1853 #if HAVE(DISPATCH_H)
1854   dispatch_queue_t m_scavengeQueue;
1855   dispatch_source_t m_scavengeTimer;
1856   bool m_scavengingSuspended;
1857 #elif OS(WINDOWS)
1858   static void CALLBACK scavengerTimerFired(void*, BOOLEAN);
1859   HANDLE m_scavengeQueueTimer;
1860 #else 
1861   static NO_RETURN_WITH_VALUE void* runScavengerThread(void*);
1862   NO_RETURN void scavengerThread();
1863
1864   // Keeps track of whether the background thread is actively scavenging memory every kScavengeDelayInSeconds, or
1865   // it's blocked waiting for more pages to be deleted.
1866   bool m_scavengeThreadActive;
1867
1868   pthread_mutex_t m_scavengeMutex;
1869   pthread_cond_t m_scavengeCondition;
1870 #endif
1871
1872 #endif  // USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
1873 };
1874
1875 void TCMalloc_PageHeap::init()
1876 {
1877   ASSERT(kPageShift && kNumClasses && kPageSize);
1878
1879   pagemap_.init(MetaDataAlloc);
1880   pagemap_cache_ = PageMapCache(0);
1881   free_pages_ = 0;
1882   system_bytes_ = 0;
1883   entropy_ = HARDENING_ENTROPY;
1884
1885 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
1886   free_committed_pages_ = 0;
1887   min_free_committed_pages_since_last_scavenge_ = 0;
1888 #endif  // USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
1889
1890   scavenge_counter_ = 0;
1891   // Start scavenging at kMaxPages list
1892   scavenge_index_ = kMaxPages-1;
1893   ASSERT(kNumClasses <= (1 << PageMapCache::kValuebits));
1894   DLL_Init(&large_.normal, entropy_);
1895   DLL_Init(&large_.returned, entropy_);
1896   for (size_t i = 0; i < kMaxPages; i++) {
1897     DLL_Init(&free_[i].normal, entropy_);
1898     DLL_Init(&free_[i].returned, entropy_);
1899   }
1900
1901 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
1902   initializeScavenger();
1903 #endif  // USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
1904 }
1905
1906 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
1907
1908 #if HAVE(DISPATCH_H)
1909
1910 void TCMalloc_PageHeap::initializeScavenger()
1911 {
1912     m_scavengeQueue = dispatch_queue_create("com.apple.JavaScriptCore.FastMallocSavenger", NULL);
1913     m_scavengeTimer = dispatch_source_create(DISPATCH_SOURCE_TYPE_TIMER, 0, 0, m_scavengeQueue);
1914     uint64_t scavengeDelayInNanoseconds = kScavengeDelayInSeconds * NSEC_PER_SEC;
1915     dispatch_time_t startTime = dispatch_time(DISPATCH_TIME_NOW, scavengeDelayInNanoseconds);
1916     dispatch_source_set_timer(m_scavengeTimer, startTime, scavengeDelayInNanoseconds, scavengeDelayInNanoseconds / 10);
1917     dispatch_source_set_event_handler(m_scavengeTimer, ^{ periodicScavenge(); });
1918     m_scavengingSuspended = true;
1919 }
1920
1921 ALWAYS_INLINE bool TCMalloc_PageHeap::isScavengerSuspended()
1922 {
1923     ASSERT(pageheap_lock.IsHeld());
1924     return m_scavengingSuspended;
1925 }
1926
1927 ALWAYS_INLINE void TCMalloc_PageHeap::scheduleScavenger()
1928 {
1929     ASSERT(pageheap_lock.IsHeld());
1930     m_scavengingSuspended = false;
1931     dispatch_resume(m_scavengeTimer);
1932 }
1933
1934 ALWAYS_INLINE void TCMalloc_PageHeap::rescheduleScavenger()
1935 {
1936     // Nothing to do here for libdispatch.
1937 }
1938
1939 ALWAYS_INLINE void TCMalloc_PageHeap::suspendScavenger()
1940 {
1941     ASSERT(pageheap_lock.IsHeld());
1942     m_scavengingSuspended = true;
1943     dispatch_suspend(m_scavengeTimer);
1944 }
1945
1946 #elif OS(WINDOWS)
1947
1948 void TCMalloc_PageHeap::scavengerTimerFired(void* context, BOOLEAN)
1949 {
1950     static_cast<TCMalloc_PageHeap*>(context)->periodicScavenge();
1951 }
1952
1953 void TCMalloc_PageHeap::initializeScavenger()
1954 {
1955     m_scavengeQueueTimer = 0;
1956 }
1957
1958 ALWAYS_INLINE bool TCMalloc_PageHeap::isScavengerSuspended()
1959 {
1960     ASSERT(pageheap_lock.IsHeld());
1961     return !m_scavengeQueueTimer;
1962 }
1963
1964 ALWAYS_INLINE void TCMalloc_PageHeap::scheduleScavenger()
1965 {
1966     // We need to use WT_EXECUTEONLYONCE here and reschedule the timer, because
1967     // Windows will fire the timer event even when the function is already running.
1968     ASSERT(pageheap_lock.IsHeld());
1969     CreateTimerQueueTimer(&m_scavengeQueueTimer, 0, scavengerTimerFired, this, kScavengeDelayInSeconds * 1000, 0, WT_EXECUTEONLYONCE);
1970 }
1971
1972 ALWAYS_INLINE void TCMalloc_PageHeap::rescheduleScavenger()
1973 {
1974     // We must delete the timer and create it again, because it is not possible to retrigger a timer on Windows.
1975     suspendScavenger();
1976     scheduleScavenger();
1977 }
1978
1979 ALWAYS_INLINE void TCMalloc_PageHeap::suspendScavenger()
1980 {
1981     ASSERT(pageheap_lock.IsHeld());
1982     HANDLE scavengeQueueTimer = m_scavengeQueueTimer;
1983     m_scavengeQueueTimer = 0;
1984     DeleteTimerQueueTimer(0, scavengeQueueTimer, 0);
1985 }
1986
1987 #else
1988
1989 void TCMalloc_PageHeap::initializeScavenger()
1990 {
1991     // Create a non-recursive mutex.
1992 #if !defined(PTHREAD_MUTEX_NORMAL) || PTHREAD_MUTEX_NORMAL == PTHREAD_MUTEX_DEFAULT
1993     pthread_mutex_init(&m_scavengeMutex, 0);
1994 #else
1995     pthread_mutexattr_t attr;
1996     pthread_mutexattr_init(&attr);
1997     pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_NORMAL);
1998
1999     pthread_mutex_init(&m_scavengeMutex, &attr);
2000
2001     pthread_mutexattr_destroy(&attr);
2002 #endif
2003
2004     pthread_cond_init(&m_scavengeCondition, 0);
2005     m_scavengeThreadActive = true;
2006     pthread_t thread;
2007     pthread_create(&thread, 0, runScavengerThread, this);
2008 }
2009
2010 void* TCMalloc_PageHeap::runScavengerThread(void* context)
2011 {
2012     static_cast<TCMalloc_PageHeap*>(context)->scavengerThread();
2013 #if (COMPILER(MSVC) || COMPILER(SUNCC))
2014     // Without this, Visual Studio and Sun Studio will complain that this method does not return a value.
2015     return 0;
2016 #endif
2017 }
2018
2019 ALWAYS_INLINE void TCMalloc_PageHeap::signalScavenger()
2020 {
2021     // shouldScavenge() should be called only when the pageheap_lock spinlock is held, additionally, 
2022     // m_scavengeThreadActive is only set to false whilst pageheap_lock is held. The caller must ensure this is
2023     // taken prior to calling this method. If the scavenger thread is sleeping and shouldScavenge() indicates there
2024     // is memory to free the scavenger thread is signalled to start.
2025     ASSERT(pageheap_lock.IsHeld());
2026     if (!m_scavengeThreadActive && shouldScavenge())
2027         pthread_cond_signal(&m_scavengeCondition);
2028 }
2029
2030 #endif
2031
2032 void TCMalloc_PageHeap::scavenge()
2033 {
2034     ASSERT(kPageShift && kNumClasses && kPageSize);
2035     size_t pagesToRelease = min_free_committed_pages_since_last_scavenge_ * kScavengePercentage;
2036     size_t targetPageCount = std::max<size_t>(kMinimumFreeCommittedPageCount, free_committed_pages_ - pagesToRelease);
2037
2038     Length lastFreeCommittedPages = free_committed_pages_;
2039     while (free_committed_pages_ > targetPageCount) {
2040         ASSERT(Check());
2041         for (int i = kMaxPages; i > 0 && free_committed_pages_ >= targetPageCount; i--) {
2042             SpanList* slist = (static_cast<size_t>(i) == kMaxPages) ? &large_ : &free_[i];
2043             // If the span size is bigger than kMinSpanListsWithSpans pages return all the spans in the list, else return all but 1 span.  
2044             // Return only 50% of a spanlist at a time so spans of size 1 are not the only ones left.
2045             size_t length = DLL_Length(&slist->normal, entropy_);
2046             size_t numSpansToReturn = (i > kMinSpanListsWithSpans) ? length : length / 2;
2047             for (int j = 0; static_cast<size_t>(j) < numSpansToReturn && !DLL_IsEmpty(&slist->normal, entropy_) && free_committed_pages_ > targetPageCount; j++) {
2048                 Span* s = slist->normal.prev(entropy_);
2049                 DLL_Remove(s, entropy_);
2050                 ASSERT(!s->decommitted);
2051                 if (!s->decommitted) {
2052                     TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift),
2053                                            static_cast<size_t>(s->length << kPageShift));
2054                     ASSERT(free_committed_pages_ >= s->length);
2055                     free_committed_pages_ -= s->length;
2056                     s->decommitted = true;
2057                 }
2058                 DLL_Prepend(&slist->returned, s, entropy_);
2059             }
2060         }
2061
2062         if (lastFreeCommittedPages == free_committed_pages_)
2063             break;
2064         lastFreeCommittedPages = free_committed_pages_;
2065     }
2066
2067     min_free_committed_pages_since_last_scavenge_ = free_committed_pages_;
2068 }
2069
2070 ALWAYS_INLINE bool TCMalloc_PageHeap::shouldScavenge() const 
2071 {
2072     return free_committed_pages_ > kMinimumFreeCommittedPageCount; 
2073 }
2074
2075 #endif  // USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2076
2077 inline Span* TCMalloc_PageHeap::New(Length n) {
2078   ASSERT(Check());
2079   ASSERT(n > 0);
2080
2081   // Find first size >= n that has a non-empty list
2082   for (Length s = n; s < kMaxPages; s++) {
2083     Span* ll = NULL;
2084     bool released = false;
2085     if (!DLL_IsEmpty(&free_[s].normal, entropy_)) {
2086       // Found normal span
2087       ll = &free_[s].normal;
2088     } else if (!DLL_IsEmpty(&free_[s].returned, entropy_)) {
2089       // Found returned span; reallocate it
2090       ll = &free_[s].returned;
2091       released = true;
2092     } else {
2093       // Keep looking in larger classes
2094       continue;
2095     }
2096
2097     Span* result = ll->next(entropy_);
2098     Carve(result, n, released);
2099 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2100     // The newly allocated memory is from a span that's in the normal span list (already committed).  Update the
2101     // free committed pages count.
2102     ASSERT(free_committed_pages_ >= n);
2103     free_committed_pages_ -= n;
2104     if (free_committed_pages_ < min_free_committed_pages_since_last_scavenge_) 
2105       min_free_committed_pages_since_last_scavenge_ = free_committed_pages_;
2106 #endif  // USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2107     ASSERT(Check());
2108     free_pages_ -= n;
2109     return result;
2110   }
2111
2112   Span* result = AllocLarge(n);
2113   if (result != NULL) {
2114       ASSERT_SPAN_COMMITTED(result);
2115       return result;
2116   }
2117
2118   // Grow the heap and try again
2119   if (!GrowHeap(n)) {
2120     ASSERT(Check());
2121     return NULL;
2122   }
2123
2124   return New(n);
2125 }
2126
2127 Span* TCMalloc_PageHeap::AllocLarge(Length n) {
2128   // find the best span (closest to n in size).
2129   // The following loops implements address-ordered best-fit.
2130   bool from_released = false;
2131   Span *best = NULL;
2132
2133   // Search through normal list
2134   for (Span* span = large_.normal.next(entropy_);
2135        span != &large_.normal;
2136        span = span->next(entropy_)) {
2137     if (span->length >= n) {
2138       if ((best == NULL)
2139           || (span->length < best->length)
2140           || ((span->length == best->length) && (span->start < best->start))) {
2141         best = span;
2142         from_released = false;
2143       }
2144     }
2145   }
2146
2147   // Search through released list in case it has a better fit
2148   for (Span* span = large_.returned.next(entropy_);
2149        span != &large_.returned;
2150        span = span->next(entropy_)) {
2151     if (span->length >= n) {
2152       if ((best == NULL)
2153           || (span->length < best->length)
2154           || ((span->length == best->length) && (span->start < best->start))) {
2155         best = span;
2156         from_released = true;
2157       }
2158     }
2159   }
2160
2161   if (best != NULL) {
2162     Carve(best, n, from_released);
2163 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2164     // The newly allocated memory is from a span that's in the normal span list (already committed).  Update the
2165     // free committed pages count.
2166     ASSERT(free_committed_pages_ >= n);
2167     free_committed_pages_ -= n;
2168     if (free_committed_pages_ < min_free_committed_pages_since_last_scavenge_)
2169       min_free_committed_pages_since_last_scavenge_ = free_committed_pages_;
2170 #endif  // USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2171     ASSERT(Check());
2172     free_pages_ -= n;
2173     return best;
2174   }
2175   return NULL;
2176 }
2177
2178 Span* TCMalloc_PageHeap::Split(Span* span, Length n) {
2179   ASSERT(0 < n);
2180   ASSERT(n < span->length);
2181   ASSERT(!span->free);
2182   ASSERT(span->sizeclass == 0);
2183   Event(span, 'T', n);
2184
2185   const Length extra = span->length - n;
2186   Span* leftover = NewSpan(span->start + n, extra);
2187   Event(leftover, 'U', extra);
2188   RecordSpan(leftover);
2189   pagemap_.set(span->start + n - 1, span); // Update map from pageid to span
2190   span->length = n;
2191
2192   return leftover;
2193 }
2194
2195 inline void TCMalloc_PageHeap::Carve(Span* span, Length n, bool released) {
2196   ASSERT(kPageShift && kNumClasses && kPageSize);
2197   ASSERT(n > 0);
2198   DLL_Remove(span, entropy_);
2199   span->free = 0;
2200   Event(span, 'A', n);
2201
2202   if (released) {
2203     // If the span chosen to carve from is decommited, commit the entire span at once to avoid committing spans 1 page at a time.
2204     ASSERT(span->decommitted);
2205     TCMalloc_SystemCommit(reinterpret_cast<void*>(span->start << kPageShift), static_cast<size_t>(span->length << kPageShift));
2206     span->decommitted = false;
2207 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2208     free_committed_pages_ += span->length;
2209 #endif
2210   }
2211   
2212   const int extra = static_cast<int>(span->length - n);
2213   ASSERT(extra >= 0);
2214   if (extra > 0) {
2215     Span* leftover = NewSpan(span->start + n, extra);
2216     leftover->free = 1;
2217     leftover->decommitted = false;
2218     Event(leftover, 'S', extra);
2219     RecordSpan(leftover);
2220
2221     // Place leftover span on appropriate free list
2222     SpanList* listpair = (static_cast<size_t>(extra) < kMaxPages) ? &free_[extra] : &large_;
2223     Span* dst = &listpair->normal;
2224     DLL_Prepend(dst, leftover, entropy_);
2225
2226     span->length = n;
2227     pagemap_.set(span->start + n - 1, span);
2228   }
2229 }
2230
2231 static ALWAYS_INLINE void mergeDecommittedStates(Span* destination, Span* other)
2232 {
2233     ASSERT(kPageShift && kNumClasses && kPageSize);
2234     if (destination->decommitted && !other->decommitted) {
2235         TCMalloc_SystemRelease(reinterpret_cast<void*>(other->start << kPageShift),
2236                                static_cast<size_t>(other->length << kPageShift));
2237     } else if (other->decommitted && !destination->decommitted) {
2238         TCMalloc_SystemRelease(reinterpret_cast<void*>(destination->start << kPageShift),
2239                                static_cast<size_t>(destination->length << kPageShift));
2240         destination->decommitted = true;
2241     }
2242 }
2243
2244 inline void TCMalloc_PageHeap::Delete(Span* span) {
2245   ASSERT(Check());
2246   ASSERT(!span->free);
2247   ASSERT(span->length > 0);
2248   ASSERT(GetDescriptor(span->start) == span);
2249   ASSERT(GetDescriptor(span->start + span->length - 1) == span);
2250   span->sizeclass = 0;
2251 #ifndef NO_TCMALLOC_SAMPLES
2252   span->sample = 0;
2253 #endif
2254
2255   // Coalesce -- we guarantee that "p" != 0, so no bounds checking
2256   // necessary.  We do not bother resetting the stale pagemap
2257   // entries for the pieces we are merging together because we only
2258   // care about the pagemap entries for the boundaries.
2259 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2260   // Track the total size of the neighboring free spans that are committed.
2261   Length neighboringCommittedSpansLength = 0;
2262 #endif
2263   const PageID p = span->start;
2264   const Length n = span->length;
2265   Span* prev = GetDescriptor(p-1);
2266   if (prev != NULL && prev->free) {
2267     // Merge preceding span into this span
2268     ASSERT(prev->start + prev->length == p);
2269     const Length len = prev->length;
2270 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2271     if (!prev->decommitted)
2272         neighboringCommittedSpansLength += len;
2273 #endif
2274     mergeDecommittedStates(span, prev);
2275     DLL_Remove(prev, entropy_);
2276     DeleteSpan(prev);
2277     span->start -= len;
2278     span->length += len;
2279     pagemap_.set(span->start, span);
2280     Event(span, 'L', len);
2281   }
2282   Span* next = GetDescriptor(p+n);
2283   if (next != NULL && next->free) {
2284     // Merge next span into this span
2285     ASSERT(next->start == p+n);
2286     const Length len = next->length;
2287 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2288     if (!next->decommitted)
2289         neighboringCommittedSpansLength += len;
2290 #endif
2291     mergeDecommittedStates(span, next);
2292     DLL_Remove(next, entropy_);
2293     DeleteSpan(next);
2294     span->length += len;
2295     pagemap_.set(span->start + span->length - 1, span);
2296     Event(span, 'R', len);
2297   }
2298
2299   Event(span, 'D', span->length);
2300   span->free = 1;
2301   if (span->decommitted) {
2302     if (span->length < kMaxPages)
2303       DLL_Prepend(&free_[span->length].returned, span, entropy_);
2304     else
2305       DLL_Prepend(&large_.returned, span, entropy_);
2306   } else {
2307     if (span->length < kMaxPages)
2308       DLL_Prepend(&free_[span->length].normal, span, entropy_);
2309     else
2310       DLL_Prepend(&large_.normal, span, entropy_);
2311   }
2312   free_pages_ += n;
2313
2314 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2315   if (span->decommitted) {
2316       // If the merged span is decommitted, that means we decommitted any neighboring spans that were
2317       // committed.  Update the free committed pages count.
2318       free_committed_pages_ -= neighboringCommittedSpansLength;
2319       if (free_committed_pages_ < min_free_committed_pages_since_last_scavenge_)
2320             min_free_committed_pages_since_last_scavenge_ = free_committed_pages_;
2321   } else {
2322       // If the merged span remains committed, add the deleted span's size to the free committed pages count.
2323       free_committed_pages_ += n;
2324   }
2325
2326   // Make sure the scavenge thread becomes active if we have enough freed pages to release some back to the system.
2327   signalScavenger();
2328 #else
2329   IncrementalScavenge(n);
2330 #endif
2331
2332   ASSERT(Check());
2333 }
2334
2335 #if !USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2336 void TCMalloc_PageHeap::IncrementalScavenge(Length n) {
2337   ASSERT(kPageShift && kNumClasses && kPageSize);
2338   // Fast path; not yet time to release memory
2339   scavenge_counter_ -= n;
2340   if (scavenge_counter_ >= 0) return;  // Not yet time to scavenge
2341
2342 #if PLATFORM(IOS)
2343   static const size_t kDefaultReleaseDelay = 64;
2344 #else
2345   // If there is nothing to release, wait for so many pages before
2346   // scavenging again.  With 4K pages, this comes to 16MB of memory.
2347   static const size_t kDefaultReleaseDelay = 1 << 8;
2348 #endif
2349
2350   // Find index of free list to scavenge
2351   size_t index = scavenge_index_ + 1;
2352   uintptr_t entropy = entropy_;
2353   for (size_t i = 0; i < kMaxPages+1; i++) {
2354     if (index > kMaxPages) index = 0;
2355     SpanList* slist = (index == kMaxPages) ? &large_ : &free_[index];
2356     if (!DLL_IsEmpty(&slist->normal, entropy)) {
2357       // Release the last span on the normal portion of this list
2358       Span* s = slist->normal.prev(entropy);
2359       DLL_Remove(s, entropy_);
2360       TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift),
2361                              static_cast<size_t>(s->length << kPageShift));
2362       s->decommitted = true;
2363       DLL_Prepend(&slist->returned, s, entropy);
2364
2365 #if PLATFORM(IOS)
2366       scavenge_counter_ = std::max<size_t>(16UL, std::min<size_t>(kDefaultReleaseDelay, kDefaultReleaseDelay - (free_pages_ / kDefaultReleaseDelay)));
2367 #else
2368       scavenge_counter_ = std::max<size_t>(64UL, std::min<size_t>(kDefaultReleaseDelay, kDefaultReleaseDelay - (free_pages_ / kDefaultReleaseDelay)));
2369 #endif
2370
2371       if (index == kMaxPages && !DLL_IsEmpty(&slist->normal, entropy))
2372         scavenge_index_ = index - 1;
2373       else
2374         scavenge_index_ = index;
2375       return;
2376     }
2377     index++;
2378   }
2379
2380   // Nothing to scavenge, delay for a while
2381   scavenge_counter_ = kDefaultReleaseDelay;
2382 }
2383 #endif
2384
2385 void TCMalloc_PageHeap::RegisterSizeClass(Span* span, size_t sc) {
2386   // Associate span object with all interior pages as well
2387   ASSERT(!span->free);
2388   ASSERT(GetDescriptor(span->start) == span);
2389   ASSERT(GetDescriptor(span->start+span->length-1) == span);
2390   Event(span, 'C', sc);
2391   span->sizeclass = static_cast<unsigned int>(sc);
2392   for (Length i = 1; i < span->length-1; i++) {
2393     pagemap_.set(span->start+i, span);
2394   }
2395 }
2396     
2397 #ifdef WTF_CHANGES
2398 size_t TCMalloc_PageHeap::ReturnedBytes() const {
2399     ASSERT(kPageShift && kNumClasses && kPageSize);
2400     size_t result = 0;
2401     for (unsigned s = 0; s < kMaxPages; s++) {
2402         const int r_length = DLL_Length(&free_[s].returned, entropy_);
2403         unsigned r_pages = s * r_length;
2404         result += r_pages << kPageShift;
2405     }
2406     
2407     for (Span* s = large_.returned.next(entropy_); s != &large_.returned; s = s->next(entropy_))
2408         result += s->length << kPageShift;
2409     return result;
2410 }
2411 #endif
2412
2413 #ifndef WTF_CHANGES
2414 static double PagesToMB(uint64_t pages) {
2415   ASSERT(kPageShift && kNumClasses && kPageSize);
2416   return (pages << kPageShift) / 1048576.0;
2417 }
2418
2419 void TCMalloc_PageHeap::Dump(TCMalloc_Printer* out) {
2420   int nonempty_sizes = 0;
2421   for (int s = 0; s < kMaxPages; s++) {
2422     if (!DLL_IsEmpty(&free_[s].normal) || !DLL_IsEmpty(&free_[s].returned)) {
2423       nonempty_sizes++;
2424     }
2425   }
2426   out->printf("------------------------------------------------\n");
2427   out->printf("PageHeap: %d sizes; %6.1f MB free\n",
2428               nonempty_sizes, PagesToMB(free_pages_));
2429   out->printf("------------------------------------------------\n");
2430   uint64_t total_normal = 0;
2431   uint64_t total_returned = 0;
2432   for (int s = 0; s < kMaxPages; s++) {
2433     const int n_length = DLL_Length(&free_[s].normal);
2434     const int r_length = DLL_Length(&free_[s].returned);
2435     if (n_length + r_length > 0) {
2436       uint64_t n_pages = s * n_length;
2437       uint64_t r_pages = s * r_length;
2438       total_normal += n_pages;
2439       total_returned += r_pages;
2440       out->printf("%6u pages * %6u spans ~ %6.1f MB; %6.1f MB cum"
2441                   "; unmapped: %6.1f MB; %6.1f MB cum\n",
2442                   s,
2443                   (n_length + r_length),
2444                   PagesToMB(n_pages + r_pages),
2445                   PagesToMB(total_normal + total_returned),
2446                   PagesToMB(r_pages),
2447                   PagesToMB(total_returned));
2448     }
2449   }
2450
2451   uint64_t n_pages = 0;
2452   uint64_t r_pages = 0;
2453   int n_spans = 0;
2454   int r_spans = 0;
2455   out->printf("Normal large spans:\n");
2456   for (Span* s = large_.normal.next; s != &large_.normal; s = s->next) {
2457     out->printf("   [ %6" PRIuS " pages ] %6.1f MB\n",
2458                 s->length, PagesToMB(s->length));
2459     n_pages += s->length;
2460     n_spans++;
2461   }
2462   out->printf("Unmapped large spans:\n");
2463   for (Span* s = large_.returned.next; s != &large_.returned; s = s->next) {
2464     out->printf("   [ %6" PRIuS " pages ] %6.1f MB\n",
2465                 s->length, PagesToMB(s->length));
2466     r_pages += s->length;
2467     r_spans++;
2468   }
2469   total_normal += n_pages;
2470   total_returned += r_pages;
2471   out->printf(">255   large * %6u spans ~ %6.1f MB; %6.1f MB cum"
2472               "; unmapped: %6.1f MB; %6.1f MB cum\n",
2473               (n_spans + r_spans),
2474               PagesToMB(n_pages + r_pages),
2475               PagesToMB(total_normal + total_returned),
2476               PagesToMB(r_pages),
2477               PagesToMB(total_returned));
2478 }
2479 #endif
2480
2481 bool TCMalloc_PageHeap::GrowHeap(Length n) {
2482   ASSERT(kPageShift && kNumClasses && kPageSize);
2483   ASSERT(kMaxPages >= kMinSystemAlloc);
2484   if (n > kMaxValidPages) return false;
2485   Length ask = (n>kMinSystemAlloc) ? n : static_cast<Length>(kMinSystemAlloc);
2486   size_t actual_size;
2487   void* ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize);
2488   if (ptr == NULL) {
2489     if (n < ask) {
2490       // Try growing just "n" pages
2491       ask = n;
2492       ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize);
2493     }
2494     if (ptr == NULL) return false;
2495   }
2496   ask = actual_size >> kPageShift;
2497
2498   uint64_t old_system_bytes = system_bytes_;
2499   system_bytes_ += (ask << kPageShift);
2500   const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift;
2501   ASSERT(p > 0);
2502
2503   // If we have already a lot of pages allocated, just pre allocate a bunch of
2504   // memory for the page map. This prevents fragmentation by pagemap metadata
2505   // when a program keeps allocating and freeing large blocks.
2506
2507   if (old_system_bytes < kPageMapBigAllocationThreshold
2508       && system_bytes_ >= kPageMapBigAllocationThreshold) {
2509     pagemap_.PreallocateMoreMemory();
2510   }
2511
2512   // Make sure pagemap_ has entries for all of the new pages.
2513   // Plus ensure one before and one after so coalescing code
2514   // does not need bounds-checking.
2515   if (pagemap_.Ensure(p-1, ask+2)) {
2516     // Pretend the new area is allocated and then Delete() it to
2517     // cause any necessary coalescing to occur.
2518     //
2519     // We do not adjust free_pages_ here since Delete() will do it for us.
2520     Span* span = NewSpan(p, ask);
2521     RecordSpan(span);
2522     Delete(span);
2523     ASSERT(Check());
2524     return true;
2525   } else {
2526     // We could not allocate memory within "pagemap_"
2527     // TODO: Once we can return memory to the system, return the new span
2528     return false;
2529   }
2530 }
2531
2532 bool TCMalloc_PageHeap::Check() {
2533 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2534   size_t totalFreeCommitted = 0;
2535 #endif
2536   ASSERT(free_[0].normal.next(entropy_) == &free_[0].normal);
2537   ASSERT(free_[0].returned.next(entropy_) == &free_[0].returned);
2538 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2539   totalFreeCommitted = CheckList(&large_.normal, kMaxPages, 1000000000, false);
2540 #else
2541   CheckList(&large_.normal, kMaxPages, 1000000000, false);
2542 #endif
2543     CheckList(&large_.returned, kMaxPages, 1000000000, true);
2544   for (Length s = 1; s < kMaxPages; s++) {
2545 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2546     totalFreeCommitted += CheckList(&free_[s].normal, s, s, false);
2547 #else
2548     CheckList(&free_[s].normal, s, s, false);
2549 #endif
2550     CheckList(&free_[s].returned, s, s, true);
2551   }
2552 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2553   ASSERT(totalFreeCommitted == free_committed_pages_);
2554 #endif
2555   return true;
2556 }
2557
2558 #if ASSERT_DISABLED
2559 size_t TCMalloc_PageHeap::CheckList(Span*, Length, Length, bool) {
2560   return 0;
2561 }
2562 #else
2563 size_t TCMalloc_PageHeap::CheckList(Span* list, Length min_pages, Length max_pages, bool decommitted) {
2564   size_t freeCount = 0;
2565   for (Span* s = list->next(entropy_); s != list; s = s->next(entropy_)) {
2566     CHECK_CONDITION(s->free);
2567     CHECK_CONDITION(s->length >= min_pages);
2568     CHECK_CONDITION(s->length <= max_pages);
2569     CHECK_CONDITION(GetDescriptor(s->start) == s);
2570     CHECK_CONDITION(GetDescriptor(s->start+s->length-1) == s);
2571     CHECK_CONDITION(s->decommitted == decommitted);
2572     freeCount += s->length;
2573   }
2574   return freeCount;
2575 }
2576 #endif
2577
2578 void TCMalloc_PageHeap::ReleaseFreeList(Span* list, Span* returned) {
2579   ASSERT(kPageShift && kNumClasses && kPageSize);
2580   // Walk backwards through list so that when we push these
2581   // spans on the "returned" list, we preserve the order.
2582 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2583   size_t freePageReduction = 0;
2584 #endif
2585
2586   while (!DLL_IsEmpty(list, entropy_)) {
2587     Span* s = list->prev(entropy_);
2588
2589     DLL_Remove(s, entropy_);
2590     s->decommitted = true;
2591     DLL_Prepend(returned, s, entropy_);
2592     TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift),
2593                            static_cast<size_t>(s->length << kPageShift));
2594 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2595     freePageReduction += s->length;
2596 #endif
2597   }
2598
2599 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2600     free_committed_pages_ -= freePageReduction;
2601     if (free_committed_pages_ < min_free_committed_pages_since_last_scavenge_) 
2602         min_free_committed_pages_since_last_scavenge_ = free_committed_pages_;
2603 #endif
2604 }
2605
2606 void TCMalloc_PageHeap::ReleaseFreePages() {
2607   for (Length s = 0; s < kMaxPages; s++) {
2608     ReleaseFreeList(&free_[s].normal, &free_[s].returned);
2609   }
2610   ReleaseFreeList(&large_.normal, &large_.returned);
2611   ASSERT(Check());
2612 }
2613
2614 //-------------------------------------------------------------------
2615 // Free list
2616 //-------------------------------------------------------------------
2617
2618 class TCMalloc_ThreadCache_FreeList {
2619  private:
2620   HardenedSLL list_;       // Linked list of nodes
2621   uint16_t length_;     // Current length
2622   uint16_t lowater_;    // Low water mark for list length
2623   uintptr_t entropy_;   // Entropy source for hardening
2624
2625  public:
2626   void Init(uintptr_t entropy) {
2627     list_.setValue(NULL);
2628     length_ = 0;
2629     lowater_ = 0;
2630     entropy_ = entropy;
2631 #if ENABLE(TCMALLOC_HARDENING)
2632     ASSERT(entropy_);
2633 #endif
2634   }
2635
2636   // Return current length of list
2637   int length() const {
2638     return length_;
2639   }
2640
2641   // Is list empty?
2642   bool empty() const {
2643     return !list_;
2644   }
2645
2646   // Low-water mark management
2647   int lowwatermark() const { return lowater_; }
2648   void clear_lowwatermark() { lowater_ = length_; }
2649
2650   ALWAYS_INLINE void Push(HardenedSLL ptr) {
2651     SLL_Push(&list_, ptr, entropy_);
2652     length_++;
2653   }
2654
2655   void PushRange(int N, HardenedSLL start, HardenedSLL end) {
2656     SLL_PushRange(&list_, start, end, entropy_);
2657     length_ = length_ + static_cast<uint16_t>(N);
2658   }
2659
2660   void PopRange(int N, HardenedSLL* start, HardenedSLL* end) {
2661     SLL_PopRange(&list_, N, start, end, entropy_);
2662     ASSERT(length_ >= N);
2663     length_ = length_ - static_cast<uint16_t>(N);
2664     if (length_ < lowater_) lowater_ = length_;
2665   }
2666
2667   ALWAYS_INLINE void* Pop() {
2668     ASSERT(list_);
2669     length_--;
2670     if (length_ < lowater_) lowater_ = length_;
2671     return SLL_Pop(&list_, entropy_).value();
2672   }
2673
2674     // Runs through the linked list to ensure that
2675     // we can do that, and ensures that 'missing'
2676     // is not present
2677     NEVER_INLINE void Validate(HardenedSLL missing, size_t size) {
2678         HardenedSLL node = list_;
2679         UNUSED_PARAM(size);
2680         while (node) {
2681             RELEASE_ASSERT(node != missing);
2682             RELEASE_ASSERT(IS_DEFINITELY_POISONED(node.value(), size));
2683             node = SLL_Next(node, entropy_);
2684         }
2685     }
2686
2687 #ifdef WTF_CHANGES
2688   template <class Finder, class Reader>
2689   void enumerateFreeObjects(Finder& finder, const Reader& reader)
2690   {
2691       for (HardenedSLL nextObject = list_; nextObject; nextObject.setValue(reader.nextEntryInHardenedLinkedList(reinterpret_cast<void**>(nextObject.value()), entropy_)))
2692           finder.visit(nextObject.value());
2693   }
2694 #endif
2695 };
2696
2697 //-------------------------------------------------------------------
2698 // Data kept per thread
2699 //-------------------------------------------------------------------
2700
2701 class TCMalloc_ThreadCache {
2702  private:
2703   typedef TCMalloc_ThreadCache_FreeList FreeList;
2704 #if OS(WINDOWS)
2705   typedef DWORD ThreadIdentifier;
2706 #else
2707   typedef pthread_t ThreadIdentifier;
2708 #endif
2709
2710   size_t        size_;                  // Combined size of data
2711   ThreadIdentifier tid_;                // Which thread owns it
2712   bool          in_setspecific_;           // Called pthread_setspecific?
2713   FreeList      list_[K_NUM_CLASSES_MAX];     // Array indexed by size-class
2714
2715   // We sample allocations, biased by the size of the allocation
2716   uint32_t      rnd_;                   // Cheap random number generator
2717   size_t        bytes_until_sample_;    // Bytes until we sample next
2718
2719   uintptr_t     entropy_;               // Entropy value used for hardening
2720
2721   // Allocate a new heap. REQUIRES: pageheap_lock is held.
2722   static inline TCMalloc_ThreadCache* NewHeap(ThreadIdentifier tid, uintptr_t entropy);
2723
2724   // Use only as pthread thread-specific destructor function.
2725   static void DestroyThreadCache(void* ptr);
2726  public:
2727   // All ThreadCache objects are kept in a linked list (for stats collection)
2728   TCMalloc_ThreadCache* next_;
2729   TCMalloc_ThreadCache* prev_;
2730
2731   void Init(ThreadIdentifier tid, uintptr_t entropy);
2732   void Cleanup();
2733
2734   // Accessors (mostly just for printing stats)
2735   int freelist_length(size_t cl) const { return list_[cl].length(); }
2736
2737   // Total byte size in cache
2738   size_t Size() const { return size_; }
2739
2740   ALWAYS_INLINE void* Allocate(size_t size);
2741   void Deallocate(HardenedSLL ptr, size_t size_class);
2742
2743   ALWAYS_INLINE void FetchFromCentralCache(size_t cl, size_t allocationSize);
2744   void ReleaseToCentralCache(size_t cl, int N);
2745   void Scavenge();
2746   void Print() const;
2747
2748   // Record allocation of "k" bytes.  Return true iff allocation
2749   // should be sampled
2750   bool SampleAllocation(size_t k);
2751
2752   // Pick next sampling point
2753   void PickNextSample(size_t k);
2754
2755   static void                  InitModule();
2756   static void                  InitTSD();
2757   static TCMalloc_ThreadCache* GetThreadHeap();
2758   static TCMalloc_ThreadCache* GetCache();
2759   static TCMalloc_ThreadCache* GetCacheIfPresent();
2760   static TCMalloc_ThreadCache* CreateCacheIfNecessary();
2761   static void                  DeleteCache(TCMalloc_ThreadCache* heap);
2762   static void                  BecomeIdle();
2763   static void                  RecomputeThreadCacheSize();
2764
2765 #ifdef WTF_CHANGES
2766   template <class Finder, class Reader>
2767   void enumerateFreeObjects(Finder& finder, const Reader& reader)
2768   {
2769       ASSERT(kPageShift && kNumClasses && kPageSize);
2770       for (unsigned sizeClass = 0; sizeClass < kNumClasses; sizeClass++)
2771           list_[sizeClass].enumerateFreeObjects(finder, reader);
2772   }
2773 #endif
2774 };
2775
2776 //-------------------------------------------------------------------
2777 // Global variables
2778 //-------------------------------------------------------------------
2779
2780 // Central cache -- a collection of free-lists, one per size-class.
2781 // We have a separate lock per free-list to reduce contention.
2782 static TCMalloc_Central_FreeListPadded central_cache[K_NUM_CLASSES_MAX];
2783
2784 // Page-level allocator
2785 static AllocAlignmentInteger pageheap_memory[(sizeof(TCMalloc_PageHeap) + sizeof(AllocAlignmentInteger) - 1) / sizeof(AllocAlignmentInteger)];
2786 static bool phinited = false;
2787
2788 // Avoid extra level of indirection by making "pageheap" be just an alias
2789 // of pageheap_memory.
2790 typedef union {
2791     void* m_memory;
2792     TCMalloc_PageHeap* m_pageHeap;
2793 } PageHeapUnion;
2794
2795 static inline TCMalloc_PageHeap* getPageHeap()
2796 {
2797     PageHeapUnion u = { &pageheap_memory[0] };
2798     return u.m_pageHeap;
2799 }
2800
2801 #define pageheap getPageHeap()
2802
2803 size_t fastMallocGoodSize(size_t bytes)
2804 {
2805     if (!phinited)
2806         TCMalloc_ThreadCache::InitModule();
2807     return AllocationSize(bytes);
2808 }
2809
2810 #if USE_BACKGROUND_THREAD_TO_SCAVENGE_MEMORY
2811
2812 #if HAVE(DISPATCH_H) || OS(WINDOWS)
2813
2814 void TCMalloc_PageHeap::periodicScavenge()
2815 {
2816     SpinLockHolder h(&pageheap_lock);
2817     pageheap->scavenge();
2818
2819     if (shouldScavenge()) {
2820         rescheduleScavenger();
2821         return;
2822     }
2823
2824     suspendScavenger();
2825 }
2826
2827 ALWAYS_INLINE void TCMalloc_PageHeap::signalScavenger()
2828 {
2829     ASSERT(pageheap_lock.IsHeld());
2830     if (isScavengerSuspended() && shouldScavenge())
2831         scheduleScavenger();
2832 }
2833
2834 #else
2835
2836 void TCMalloc_PageHeap::scavengerThread()
2837 {
2838 #if HAVE(PTHREAD_SETNAME_NP)
2839     pthread_setname_np("JavaScriptCore: FastMalloc scavenger");
2840 #endif
2841
2842     while (1) {
2843         pageheap_lock.Lock();
2844         if (!shouldScavenge()) {
2845             // Set to false so that signalScavenger() will check whether we need to be siganlled.
2846             m_scavengeThreadActive = false;
2847
2848             // We need to unlock now, as this thread will block on the condvar until scavenging is required.
2849             pageheap_lock.Unlock();
2850
2851             // Block until there are enough free committed pages to release back to the system.
2852             pthread_mutex_lock(&m_scavengeMutex);
2853             pthread_cond_wait(&m_scavengeCondition, &m_scavengeMutex);
2854             // After exiting the pthread_cond_wait, we hold the lock on m_scavengeMutex. Unlock it to prevent
2855             // deadlock next time round the loop.
2856             pthread_mutex_unlock(&m_scavengeMutex);
2857
2858             // Set to true to prevent unnecessary signalling of the condvar.
2859             m_scavengeThreadActive = true;
2860         } else
2861             pageheap_lock.Unlock();
2862
2863         // Wait for a while to calculate how much memory remains unused during this pause.
2864         sleep(kScavengeDelayInSeconds);
2865
2866         {
2867             SpinLockHolder h(&pageheap_lock);
2868             pageheap->scavenge();
2869         }
2870     }
2871 }
2872
2873 #endif
2874
2875 #endif
2876
2877 // If TLS is available, we also store a copy
2878 // of the per-thread object in a __thread variable
2879 // since __thread variables are faster to read
2880 // than pthread_getspecific().  We still need
2881 // pthread_setspecific() because __thread
2882 // variables provide no way to run cleanup
2883 // code when a thread is destroyed.
2884 #ifdef HAVE_TLS
2885 static __thread TCMalloc_ThreadCache *threadlocal_heap;
2886 #endif
2887 // Thread-specific key.  Initialization here is somewhat tricky
2888 // because some Linux startup code invokes malloc() before it
2889 // is in a good enough state to handle pthread_keycreate().
2890 // Therefore, we use TSD keys only after tsd_inited is set to true.
2891 // Until then, we use a slow path to get the heap object.
2892 static bool tsd_inited = false;
2893 #if USE(PTHREAD_GETSPECIFIC_DIRECT)
2894 static const pthread_key_t heap_key = __PTK_FRAMEWORK_JAVASCRIPTCORE_KEY0;
2895 #else
2896 static ThreadSpecificKey heap_key;
2897 #endif
2898
2899 static ALWAYS_INLINE void setThreadHeap(TCMalloc_ThreadCache* heap)
2900 {
2901 #if USE(PTHREAD_GETSPECIFIC_DIRECT)
2902     // Can't have two libraries both doing this in the same process,
2903     // so check and make this crash right away.
2904     if (pthread_getspecific(heap_key))
2905         CRASH();
2906 #endif
2907
2908 #if OS(DARWIN)
2909     // Still do pthread_setspecific even if there's an alternate form
2910     // of thread-local storage in use, to benefit from the delete callback.
2911     pthread_setspecific(heap_key, heap);
2912 #else
2913     threadSpecificSet(heap_key, heap);
2914 #endif
2915 }
2916
2917 // Allocator for thread heaps
2918 static PageHeapAllocator<TCMalloc_ThreadCache> threadheap_allocator;
2919
2920 // Linked list of heap objects.  Protected by pageheap_lock.
2921 static TCMalloc_ThreadCache* thread_heaps = NULL;
2922 static int thread_heap_count = 0;
2923
2924 // Overall thread cache size.  Protected by pageheap_lock.
2925 static size_t overall_thread_cache_size = kDefaultOverallThreadCacheSize;
2926
2927 // Global per-thread cache size.  Writes are protected by
2928 // pageheap_lock.  Reads are done without any locking, which should be
2929 // fine as long as size_t can be written atomically and we don't place
2930 // invariants between this variable and other pieces of state.
2931 static volatile size_t per_thread_cache_size = kMaxThreadCacheSize;
2932
2933 //-------------------------------------------------------------------
2934 // Central cache implementation
2935 //-------------------------------------------------------------------
2936
2937 void TCMalloc_Central_FreeList::Init(size_t cl, uintptr_t entropy) {
2938   ASSERT(kPageShift && kNumClasses && kPageSize);
2939   lock_.Init();
2940   size_class_ = cl;
2941   entropy_ = entropy;
2942 #if ENABLE(TCMALLOC_HARDENING)
2943   ASSERT(entropy_);
2944 #endif
2945   DLL_Init(&empty_, entropy_);
2946   DLL_Init(&nonempty_, entropy_);
2947   counter_ = 0;
2948
2949   cache_size_ = 1;
2950   used_slots_ = 0;
2951   ASSERT(cache_size_ <= kNumTransferEntries);
2952 }
2953
2954 void TCMalloc_Central_FreeList::ReleaseListToSpans(HardenedSLL start) {
2955   while (start) {
2956     HardenedSLL next = SLL_Next(start, entropy_);
2957     ReleaseToSpans(start);
2958     start = next;
2959   }
2960 }
2961
2962 ALWAYS_INLINE void TCMalloc_Central_FreeList::ReleaseToSpans(HardenedSLL object) {
2963   ASSERT(kPageShift && kNumClasses && kPageSize);
2964   const PageID p = reinterpret_cast<uintptr_t>(object.value()) >> kPageShift;
2965   Span* span = pageheap->GetDescriptor(p);
2966   ASSERT(span != NULL);
2967   ASSERT(span->refcount > 0);
2968
2969   // If span is empty, move it to non-empty list
2970   if (!span->objects) {
2971     DLL_Remove(span, entropy_);
2972     DLL_Prepend(&nonempty_, span, entropy_);
2973     Event(span, 'N', 0);
2974   }
2975
2976   // The following check is expensive, so it is disabled by default
2977   if (false) {
2978     // Check that object does not occur in list
2979     unsigned got = 0;
2980     for (HardenedSLL p = span->objects; !p; SLL_Next(p, entropy_)) {
2981       ASSERT(p.value() != object.value());
2982       got++;
2983     }
2984     ASSERT(got + span->refcount ==
2985            (span->length<<kPageShift)/ByteSizeForClass(span->sizeclass));
2986   }
2987
2988   counter_++;
2989   span->refcount--;
2990   if (span->refcount == 0) {
2991     Event(span, '#', 0);
2992     counter_ -= (span->length<<kPageShift) / ByteSizeForClass(span->sizeclass);
2993     DLL_Remove(span, entropy_);
2994
2995     // Release central list lock while operating on pageheap
2996     lock_.Unlock();
2997     {
2998       SpinLockHolder h(&pageheap_lock);
2999       pageheap->Delete(span);
3000     }
3001     lock_.Lock();
3002   } else {
3003     SLL_SetNext(object, span->objects, entropy_);
3004     span->objects.setValue(object.value());
3005   }
3006 }
3007
3008 ALWAYS_INLINE bool TCMalloc_Central_FreeList::EvictRandomSizeClass(
3009     size_t locked_size_class, bool force) {
3010   ASSERT(kPageShift && kNumClasses && kPageSize);
3011   static int race_counter = 0;
3012   int t = race_counter++;  // Updated without a lock, but who cares.
3013   if (t >= static_cast<int>(kNumClasses)) {
3014     while (t >= static_cast<int>(kNumClasses)) {
3015       t -= kNumClasses;
3016     }
3017     race_counter = t;
3018   }
3019   ASSERT(t >= 0);
3020   ASSERT(t < static_cast<int>(kNumClasses));
3021   if (t == static_cast<int>(locked_size_class)) return false;
3022   return central_cache[t].ShrinkCache(static_cast<int>(locked_size_class), force);
3023 }
3024
3025 bool TCMalloc_Central_FreeList::MakeCacheSpace() {
3026   ASSERT(kPageShift && kNumClasses && kPageSize);
3027   // Is there room in the cache?
3028   if (used_slots_ < cache_size_) return true;
3029   // Check if we can expand this cache?
3030   if (cache_size_ == kNumTransferEntries) return false;
3031   // Ok, we'll try to grab an entry from some other size class.
3032   if (EvictRandomSizeClass(size_class_, false) ||
3033       EvictRandomSizeClass(size_class_, true)) {
3034     // Succeeded in evicting, we're going to make our cache larger.
3035     cache_size_++;
3036     return true;
3037   }
3038   return false;
3039 }
3040
3041
3042 namespace {
3043 class LockInverter {
3044  private:
3045   SpinLock *held_, *temp_;
3046  public:
3047   inline explicit LockInverter(SpinLock* held, SpinLock *temp)
3048     : held_(held), temp_(temp) { held_->Unlock(); temp_->Lock(); }
3049   inline ~LockInverter() { temp_->Unlock(); held_->Lock();  }
3050 };
3051 }
3052
3053 bool TCMalloc_Central_FreeList::ShrinkCache(int locked_size_class, bool force) {
3054   // Start with a quick check without taking a lock.
3055   if (cache_size_ == 0) return false;
3056   // We don't evict from a full cache unless we are 'forcing'.
3057   if (force == false && used_slots_ == cache_size_) return false;
3058
3059   // Grab lock, but first release the other lock held by this thread.  We use
3060   // the lock inverter to ensure that we never hold two size class locks
3061   // concurrently.  That can create a deadlock because there is no well
3062   // defined nesting order.
3063   LockInverter li(&central_cache[locked_size_class].lock_, &lock_);
3064   ASSERT(used_slots_ <= cache_size_);
3065   ASSERT(0 <= cache_size_);
3066   if (cache_size_ == 0) return false;
3067   if (used_slots_ == cache_size_) {
3068     if (force == false) return false;
3069     // ReleaseListToSpans releases the lock, so we have to make all the
3070     // updates to the central list before calling it.
3071     cache_size_--;
3072     used_slots_--;
3073     ReleaseListToSpans(tc_slots_[used_slots_].head);
3074     return true;
3075   }
3076   cache_size_--;
3077   return true;
3078 }
3079
3080 void TCMalloc_Central_FreeList::InsertRange(HardenedSLL start, HardenedSLL end, int N) {
3081   ASSERT(kPageShift && kNumClasses && kPageSize);
3082   SpinLockHolder h(&lock_);
3083   if (N == num_objects_to_move[size_class_] &&
3084     MakeCacheSpace()) {
3085     int slot = used_slots_++;
3086     ASSERT(slot >=0);
3087     ASSERT(slot < kNumTransferEntries);
3088     TCEntry *entry = &tc_slots_[slot];
3089     entry->head = start;
3090     entry->tail = end;
3091     return;
3092   }
3093   ReleaseListToSpans(start);
3094 }
3095
3096 ALWAYS_INLINE void TCMalloc_Central_FreeList::RemoveRange(HardenedSLL* start, HardenedSLL* end, int *N) {
3097   int num = *N;
3098   ASSERT(num > 0);
3099
3100   SpinLockHolder h(&lock_);
3101   if (num == num_objects_to_move[size_class_] && used_slots_ > 0) {
3102     int slot = --used_slots_;
3103     ASSERT(slot >= 0);
3104     TCEntry *entry = &tc_slots_[slot];
3105     *start = entry->head;
3106     *end = entry->tail;
3107     return;
3108   }
3109
3110   // TODO: Prefetch multiple TCEntries?
3111   HardenedSLL tail = FetchFromSpansSafe();
3112   if (!tail) {
3113     // We are completely out of memory.
3114     *start = *end = HardenedSLL::null();
3115     *N = 0;
3116     return;
3117   }
3118
3119   SLL_SetNext(tail, HardenedSLL::null(), entropy_);
3120   HardenedSLL head = tail;
3121   int count = 1;
3122   while (count < num) {
3123     HardenedSLL t = FetchFromSpans();
3124     if (!t) break;
3125     SLL_Push(&head, t, entropy_);
3126     count++;
3127   }
3128   *start = head;
3129   *end = tail;
3130   *N = count;
3131 }
3132
3133
3134 ALWAYS_INLINE HardenedSLL TCMalloc_Central_FreeList::FetchFromSpansSafe() {
3135   HardenedSLL t = FetchFromSpans();
3136   if (!t) {
3137     Populate();
3138     t = FetchFromSpans();
3139   }
3140   return t;
3141 }
3142
3143 HardenedSLL TCMalloc_Central_FreeList::FetchFromSpans() {
3144   if (DLL_IsEmpty(&nonempty_, entropy_)) return HardenedSLL::null();
3145   Span* span = nonempty_.next(entropy_);
3146
3147   ASSERT(span->objects);
3148   ASSERT_SPAN_COMMITTED(span);
3149   span->refcount++;
3150   HardenedSLL result = span->objects;
3151   span->objects = SLL_Next(result, entropy_);
3152   if (!span->objects) {
3153     // Move to empty list
3154     DLL_Remove(span, entropy_);
3155     DLL_Prepend(&empty_, span, entropy_);
3156     Event(span, 'E', 0);
3157   }
3158   counter_--;
3159   return result;
3160 }
3161
3162 // Fetch memory from the system and add to the central cache freelist.
3163 ALWAYS_INLINE void TCMalloc_Central_FreeList::Populate() {
3164   ASSERT(kPageShift && kNumClasses && kPageSize);
3165   // Release central list lock while operating on pageheap
3166   lock_.Unlock();
3167   const size_t npages = class_to_pages[size_class_];
3168
3169   Span* span;
3170   {
3171     SpinLockHolder h(&pageheap_lock);
3172     span = pageheap->New(npages);
3173     if (span) pageheap->RegisterSizeClass(span, size_class_);
3174   }
3175   if (span == NULL) {
3176 #if HAVE(ERRNO_H)
3177     MESSAGE("allocation failed: %d\n", errno);
3178 #elif OS(WINDOWS)
3179     MESSAGE("allocation failed: %d\n", ::GetLastError());
3180 #else
3181     MESSAGE("allocation failed\n");
3182 #endif
3183     lock_.Lock();
3184     return;
3185   }
3186   ASSERT_SPAN_COMMITTED(span);
3187   ASSERT(span->length == npages);
3188   // Cache sizeclass info eagerly.  Locking is not necessary.
3189   // (Instead of being eager, we could just replace any stale info
3190   // about this span, but that seems to be no better in practice.)
3191   for (size_t i = 0; i < npages; i++) {
3192     pageheap->CacheSizeClass(span->start + i, size_class_);
3193   }
3194
3195   // Split the block into pieces and add to the free-list
3196   // TODO: coloring of objects to avoid cache conflicts?
3197   HardenedSLL head = HardenedSLL::null();
3198   char* start = reinterpret_cast<char*>(span->start << kPageShift);
3199   const size_t size = ByteSizeForClass(size_class_);
3200   char* ptr = start + (npages << kPageShift) - ((npages << kPageShift) % size);
3201   int num = 0;
3202 #if ENABLE(TCMALLOC_HARDENING)
3203   uint32_t startPoison = freedObjectStartPoison();
3204   uint32_t endPoison = freedObjectEndPoison();
3205 #endif
3206
3207   while (ptr > start) {
3208     ptr -= size;
3209     HardenedSLL node = HardenedSLL::create(ptr);
3210     POISON_DEALLOCATION_EXPLICIT(ptr, size, startPoison, endPoison);
3211     SLL_SetNext(node, head, entropy_);
3212     head = node;
3213     num++;
3214   }
3215   ASSERT(ptr == start);
3216   ASSERT(ptr == head.value());
3217 #ifndef NDEBUG
3218     {
3219         HardenedSLL node = head;
3220         while (node) {
3221             ASSERT(IS_DEFINITELY_POISONED(node.value(), size));
3222             node = SLL_Next(node, entropy_);
3223         }
3224     }
3225 #endif
3226   span->objects = head;
3227   ASSERT(span->objects.value() == head.value());
3228   span->refcount = 0; // No sub-object in use yet
3229
3230   // Add span to list of non-empty spans
3231   lock_.Lock();
3232   DLL_Prepend(&nonempty_, span, entropy_);
3233   counter_ += num;
3234 }
3235
3236 //-------------------------------------------------------------------
3237 // TCMalloc_ThreadCache implementation
3238 //-------------------------------------------------------------------
3239
3240 inline bool TCMalloc_ThreadCache::SampleAllocation(size_t k) {
3241   if (bytes_until_sample_ < k) {
3242     PickNextSample(k);
3243     return true;
3244   } else {
3245     bytes_until_sample_ -= k;
3246     return false;
3247   }
3248 }
3249
3250 void TCMalloc_ThreadCache::Init(ThreadIdentifier tid, uintptr_t entropy) {
3251   ASSERT(kPageShift && kNumClasses && kPageSize);
3252   size_ = 0;
3253   next_ = NULL;
3254   prev_ = NULL;
3255   tid_  = tid;
3256   in_setspecific_ = false;
3257   entropy_ = entropy;
3258 #if ENABLE(TCMALLOC_HARDENING)
3259   ASSERT(entropy_);
3260 #endif
3261   for (size_t cl = 0; cl < kNumClasses; ++cl) {
3262     list_[cl].Init(entropy_);
3263   }
3264
3265   // Initialize RNG -- run it for a bit to get to good values
3266   bytes_until_sample_ = 0;
3267   rnd_ = static_cast<uint32_t>(reinterpret_cast<uintptr_t>(this));
3268   for (int i = 0; i < 100; i++) {
3269     PickNextSample(static_cast<size_t>(FLAGS_tcmalloc_sample_parameter * 2));
3270   }
3271 }
3272
3273 void TCMalloc_ThreadCache::Cleanup() {
3274   ASSERT(kPageShift && kNumClasses && kPageSize);
3275   // Put unused memory back into central cache
3276   for (size_t cl = 0; cl < kNumClasses; ++cl) {
3277     if (list_[cl].length() > 0) {
3278       ReleaseToCentralCache(cl, list_[cl].length());
3279     }
3280   }
3281 }
3282
3283 ALWAYS_INLINE void* TCMalloc_ThreadCache::Allocate(size_t size) {
3284   ASSERT(size <= kMaxSize);
3285   const size_t cl = SizeClass(size);
3286   FreeList* list = &list_[cl];
3287   size_t allocationSize = ByteSizeForClass(cl);
3288   if (list->empty()) {
3289     FetchFromCentralCache(cl, allocationSize);
3290     if (list->empty()) return NULL;
3291   }
3292   size_ -= allocationSize;
3293   void* result = list->Pop();
3294   if (!result)
3295       return 0;
3296   RELEASE_ASSERT(IS_DEFINITELY_POISONED(result, allocationSize));
3297   POISON_ALLOCATION(result, allocationSize);
3298   return result;
3299 }
3300
3301 inline void TCMalloc_ThreadCache::Deallocate(HardenedSLL ptr, size_t cl) {
3302   size_t allocationSize = ByteSizeForClass(cl);
3303   size_ += allocationSize;
3304   FreeList* list = &list_[cl];
3305   if (MAY_BE_POISONED(ptr.value(), allocationSize))
3306       list->Validate(ptr, allocationSize);
3307
3308   POISON_DEALLOCATION(ptr.value(), allocationSize);
3309   list->Push(ptr);
3310   // If enough data is free, put back into central cache
3311   if (list->length() > kMaxFreeListLength) {
3312     ReleaseToCentralCache(cl, num_objects_to_move[cl]);
3313   }
3314   if (size_ >= per_thread_cache_size) Scavenge();
3315 }
3316
3317 // Remove some objects of class "cl" from central cache and add to thread heap
3318 ALWAYS_INLINE void TCMalloc_ThreadCache::FetchFromCentralCache(size_t cl, size_t allocationSize) {
3319   int fetch_count = num_objects_to_move[cl];
3320   HardenedSLL start, end;
3321   central_cache[cl].RemoveRange(&start, &end, &fetch_count);
3322   list_[cl].PushRange(fetch_count, start, end);
3323   size_ += allocationSize * fetch_count;
3324 }
3325
3326 // Remove some objects of class "cl" from thread heap and add to central cache
3327 inline void TCMalloc_ThreadCache::ReleaseToCentralCache(size_t cl, int N) {
3328   ASSERT(N > 0);
3329   FreeList* src = &list_[cl];
3330   if (N > src->length()) N = src->length();
3331   size_ -= N*ByteSizeForClass(cl);
3332
3333   // We return prepackaged chains of the correct size to the central cache.
3334   // TODO: Use the same format internally in the thread caches?
3335   int batch_size = num_objects_to_move[cl];
3336   while (N > batch_size) {
3337     HardenedSLL tail, head;
3338     src->PopRange(batch_size, &head, &tail);
3339     central_cache[cl].InsertRange(head, tail, batch_size);
3340     N -= batch_size;
3341   }
3342   HardenedSLL tail, head;
3343   src->PopRange(N, &head, &tail);
3344   central_cache[cl].InsertRange(head, tail, N);
3345 }
3346
3347 // Release idle memory to the central cache
3348 inline void TCMalloc_ThreadCache::Scavenge() {
3349   ASSERT(kPageShift && kNumClasses && kPageSize);
3350   // If the low-water mark for the free list is L, it means we would
3351   // not have had to allocate anything from the central cache even if
3352   // we had reduced the free list size by L.  We aim to get closer to
3353   // that situation by dropping L/2 nodes from the free list.  This
3354   // may not release much memory, but if so we will call scavenge again
3355   // pretty soon and the low-water marks will be high on that call.
3356   //int64 start = CycleClock::Now();
3357
3358   for (size_t cl = 0; cl < kNumClasses; cl++) {
3359     FreeList* list = &list_[cl];
3360     const int lowmark = list->lowwatermark();
3361     if (lowmark > 0) {
3362       const int drop = (lowmark > 1) ? lowmark/2 : 1;
3363       ReleaseToCentralCache(cl, drop);
3364     }
3365     list->clear_lowwatermark();
3366   }
3367
3368   //int64 finish = CycleClock::Now();
3369   //CycleTimer ct;
3370   //MESSAGE("GC: %.0f ns\n", ct.CyclesToUsec(finish-start)*1000.0);
3371 }
3372
3373 void TCMalloc_ThreadCache::PickNextSample(size_t k) {
3374   // Make next "random" number
3375   // x^32+x^22+x^2+x^1+1 is a primitive polynomial for random numbers
3376   static const uint32_t kPoly = (1 << 22) | (1 << 2) | (1 << 1) | (1 << 0);
3377   uint32_t r = rnd_;
3378   rnd_ = (r << 1) ^ ((static_cast<int32_t>(r) >> 31) & kPoly);
3379
3380   // Next point is "rnd_ % (sample_period)".  I.e., average
3381   // increment is "sample_period/2".
3382   const int flag_value = static_cast<int>(FLAGS_tcmalloc_sample_parameter);
3383   static int last_flag_value = -1;
3384
3385   if (flag_value != last_flag_value) {
3386     SpinLockHolder h(&sample_period_lock);
3387     int i;
3388     for (i = 0; i < (static_cast<int>(sizeof(primes_list)/sizeof(primes_list[0])) - 1); i++) {
3389       if (primes_list[i] >= flag_value) {
3390         break;
3391       }
3392     }
3393     sample_period = primes_list[i];
3394     last_flag_value = flag_value;
3395   }
3396
3397   bytes_until_sample_ += rnd_ % sample_period;
3398
3399   if (k > (static_cast<size_t>(-1) >> 2)) {
3400     // If the user has asked for a huge allocation then it is possible
3401     // for the code below to loop infinitely.  Just return (note that
3402     // this throws off the sampling accuracy somewhat, but a user who
3403     // is allocating more than 1G of memory at a time can live with a
3404     // minor inaccuracy in profiling of small allocations, and also
3405     // would rather not wait for the loop below to terminate).
3406     return;
3407   }
3408
3409   while (bytes_until_sample_ < k) {
3410     // Increase bytes_until_sample_ by enough average sampling periods
3411     // (sample_period >> 1) to allow us to sample past the current
3412     // allocation.
3413     bytes_until_sample_ += (sample_period >> 1);
3414   }
3415
3416   bytes_until_sample_ -= k;
3417 }
3418
3419 void TCMalloc_ThreadCache::InitModule() {
3420   // There is a slight potential race here because of double-checked
3421   // locking idiom.  However, as long as the program does a small
3422   // allocation before switching to multi-threaded mode, we will be
3423   // fine.  We increase the chances of doing such a small allocation
3424   // by doing one in the constructor of the module_enter_exit_hook
3425   // object declared below.
3426   SpinLockHolder h(&pageheap_lock);
3427   if (!phinited) {
3428     uintptr_t entropy = HARDENING_ENTROPY;
3429 #ifdef WTF_CHANGES
3430     InitTSD();
3431 #endif
3432     InitSizeClasses();
3433     threadheap_allocator.Init(entropy);
3434     span_allocator.Init(entropy);
3435     span_allocator.New(); // Reduce cache conflicts
3436     span_allocator.New(); // Reduce cache conflicts
3437     stacktrace_allocator.Init(entropy);
3438     DLL_Init(&sampled_objects, entropy);
3439     for (size_t i = 0; i < kNumClasses; ++i) {
3440       central_cache[i].Init(i, entropy);
3441     }
3442     pageheap->init();
3443     phinited = 1;
3444 #if defined(WTF_CHANGES) && OS(DARWIN)
3445     MallocHook::init();
3446     FastMallocZone::init();
3447 #endif
3448   }
3449 }
3450
3451 inline TCMalloc_ThreadCache* TCMalloc_ThreadCache::NewHeap(ThreadIdentifier tid, uintptr_t entropy) {
3452   // Create the heap and add it to the linked list
3453   TCMalloc_ThreadCache *heap = threadheap_allocator.New();
3454   heap->Init(tid, entropy);
3455   heap->next_ = thread_heaps;
3456   heap->prev_ = NULL;
3457   if (thread_heaps != NULL) thread_heaps->prev_ = heap;
3458   thread_heaps = heap;
3459   thread_heap_count++;
3460   RecomputeThreadCacheSize();
3461   return heap;
3462 }
3463
3464 inline TCMalloc_ThreadCache* TCMalloc_ThreadCache::GetThreadHeap() {
3465 #ifdef HAVE_TLS
3466     // __thread is faster, but only when the kernel supports it
3467   if (KernelSupportsTLS())
3468     return threadlocal_heap;
3469 #elif OS(DARWIN)
3470     return static_cast<TCMalloc_ThreadCache*>(pthread_getspecific(heap_key));
3471 #else
3472     return static_cast<TCMalloc_ThreadCache*>(threadSpecificGet(heap_key));
3473 #endif
3474 }
3475
3476 inline TCMalloc_ThreadCache* TCMalloc_ThreadCache::GetCache() {
3477   TCMalloc_ThreadCache* ptr = NULL;
3478   if (!tsd_inited) {
3479     InitModule();
3480   } else {
3481     ptr = GetThreadHeap();
3482   }
3483   if (ptr == NULL) ptr = CreateCacheIfNecessary();
3484   return ptr;
3485 }
3486
3487 // In deletion paths, we do not try to create a thread-cache.  This is
3488 // because we may be in the thread destruction code and may have
3489 // already cleaned up the cache for this thread.
3490 inline TCMalloc_ThreadCache* TCMalloc_ThreadCache::GetCacheIfPresent() {
3491   if (!tsd_inited) return NULL;
3492   void* const p = GetThreadHeap();
3493   return reinterpret_cast<TCMalloc_ThreadCache*>(p);
3494 }
3495
3496 void TCMalloc_ThreadCache::InitTSD() {
3497   ASSERT(!tsd_inited);
3498 #if USE(PTHREAD_GETSPECIFIC_DIRECT)
3499   pthread_key_init_np(heap_key, DestroyThreadCache);
3500 #else
3501   threadSpecificKeyCreate(&heap_key, DestroyThreadCache);
3502 #endif
3503   tsd_inited = true;
3504     
3505 #if !OS(WINDOWS)
3506   // We may have used a fake pthread_t for the main thread.  Fix it.
3507   pthread_t zero;
3508   memset(&zero, 0, sizeof(zero));
3509 #endif
3510 #ifndef WTF_CHANGES
3511   SpinLockHolder h(&pageheap_lock);
3512 #else
3513   ASSERT(pageheap_lock.IsHeld());
3514 #endif
3515   for (TCMalloc_ThreadCache* h = thread_heaps; h != NULL; h = h->next_) {
3516 #if OS(WINDOWS)
3517     if (h->tid_ == 0) {
3518       h->tid_ = GetCurrentThreadId();
3519     }
3520 #else
3521     if (pthread_equal(h->tid_, zero)) {
3522       h->tid_ = pthread_self();
3523     }
3524 #endif
3525   }
3526 }
3527
3528 TCMalloc_ThreadCache* TCMalloc_ThreadCache::CreateCacheIfNecessary() {
3529   // Initialize per-thread data if necessary
3530   TCMalloc_ThreadCache* heap = NULL;
3531   {
3532     SpinLockHolder h(&pageheap_lock);
3533
3534 #if OS(WINDOWS)
3535     DWORD me;
3536     if (!tsd_inited) {
3537       me = 0;
3538     } else {
3539       me = GetCurrentThreadId();
3540     }
3541 #else
3542     // Early on in glibc's life, we cannot even call pthread_self()
3543     pthread_t me;
3544     if (!tsd_inited) {
3545       memset(&me, 0, sizeof(me));
3546     } else {
3547       me = pthread_self();
3548     }
3549 #endif
3550
3551     // This may be a recursive malloc call from pthread_setspecific()
3552     // In that case, the heap for this thread has already been created
3553     // and added to the linked list.  So we search for that first.
3554     for (TCMalloc_ThreadCache* h = thread_heaps; h != NULL; h = h->next_) {
3555 #if OS(WINDOWS)
3556       if (h->tid_ == me) {
3557 #else
3558       if (pthread_equal(h->tid_, me)) {
3559 #endif
3560         heap = h;
3561         break;
3562       }
3563     }
3564
3565     if (heap == NULL) heap = NewHeap(me, HARDENING_ENTROPY);
3566   }
3567
3568   // We call pthread_setspecific() outside the lock because it may
3569   // call malloc() recursively.  The recursive call will never get
3570   // here again because it will find the already allocated heap in the
3571   // linked list of heaps.
3572   if (!heap->in_setspecific_ && tsd_inited) {
3573     heap->in_setspecific_ = true;
3574     setThreadHeap(heap);
3575   }
3576   return heap;
3577 }
3578
3579 void TCMalloc_ThreadCache::BecomeIdle() {
3580   if (!tsd_inited) return;              // No caches yet
3581   TCMalloc_ThreadCache* heap = GetThreadHeap();
3582   if (heap == NULL) return;             // No thread cache to remove
3583   if (heap->in_setspecific_) return;    // Do not disturb the active caller
3584
3585   heap->in_setspecific_ = true;
3586   setThreadHeap(NULL);
3587 #ifdef HAVE_TLS
3588   // Also update the copy in __thread
3589   threadlocal_heap = NULL;
3590 #endif
3591   heap->in_setspecific_ = false;
3592   if (GetThreadHeap() == heap) {
3593     // Somehow heap got reinstated by a recursive call to malloc
3594     // from pthread_setspecific.  We give up in this case.
3595     return;
3596   }
3597
3598   // We can now get rid of the heap
3599   DeleteCache(heap);
3600 }
3601
3602 void TCMalloc_ThreadCache::DestroyThreadCache(void* ptr) {
3603   // Note that "ptr" cannot be NULL since pthread promises not
3604   // to invoke the destructor on NULL values, but for safety,
3605   // we check anyway.
3606   if (ptr == NULL) return;
3607 #ifdef HAVE_TLS
3608   // Prevent fast path of GetThreadHeap() from returning heap.
3609   threadlocal_heap = NULL;
3610 #endif
3611   DeleteCache(reinterpret_cast<TCMalloc_ThreadCache*>(ptr));
3612 }
3613
3614 void TCMalloc_ThreadCache::DeleteCache(TCMalloc_ThreadCache* heap) {
3615   // Remove all memory from heap
3616   heap->Cleanup();
3617
3618   // Remove from linked list
3619   SpinLockHolder h(&pageheap_lock);
3620   if (heap->next_ != NULL) heap->next_->prev_ = heap->prev_;
3621   if (heap->prev_ != NULL) heap->prev_->next_ = heap->next_;
3622   if (thread_heaps == heap) thread_heaps = heap->next_;
3623   thread_heap_count--;
3624   RecomputeThreadCacheSize();
3625
3626   threadheap_allocator.Delete(heap);
3627 }
3628
3629 void TCMalloc_ThreadCache::RecomputeThreadCacheSize() {
3630   // Divide available space across threads
3631   int n = thread_heap_count > 0 ? thread_heap_count : 1;
3632   size_t space = overall_thread_cache_size / n;
3633
3634   // Limit to allowed range
3635   if (space < kMinThreadCacheSize) space = kMinThreadCacheSize;
3636   if (space > kMaxThreadCacheSize) space = kMaxThreadCacheSize;
3637
3638   per_thread_cache_size = space;
3639 }
3640
3641 void TCMalloc_ThreadCache::Print() const {
3642   ASSERT(kPageShift && kNumClasses && kPageSize);
3643   for (size_t cl = 0; cl < kNumClasses; ++cl) {
3644     MESSAGE("      %5" PRIuS " : %4d len; %4d lo\n",
3645             ByteSizeForClass(cl),
3646             list_[cl].length(),
3647             list_[cl].lowwatermark());
3648   }
3649 }
3650
3651 // Extract interesting stats
3652 struct TCMallocStats {
3653   uint64_t system_bytes;        // Bytes alloced from system
3654   uint64_t thread_bytes;        // Bytes in thread caches
3655   uint64_t central_bytes;       // Bytes in central cache
3656   uint64_t transfer_bytes;      // Bytes in central transfer cache
3657   uint64_t pageheap_bytes;      // Bytes in page heap
3658   uint64_t metadata_bytes;      // Bytes alloced for metadata
3659 };
3660
3661 #ifndef WTF_CHANGES
3662 // Get stats into "r".  Also get per-size-class counts if class_count != NULL
3663 static void ExtractStats(TCMallocStats* r, uint64_t* class_count) {
3664   ASSERT(kPageShift && kNumClasses && kPageSize);
3665   r->central_bytes = 0;
3666   r->transfer_bytes = 0;
3667   for (int cl = 0; cl < kNumClasses; ++cl) {
3668     const int length = central_cache[cl].length();
3669     const int tc_length = central_cache[cl].tc_length();
3670     r->central_bytes += static_cast<uint64_t>(ByteSizeForClass(cl)) * length;
3671     r->transfer_bytes +=
3672       static_cast<uint64_t>(ByteSizeForClass(cl)) * tc_length;
3673     if (class_count) class_count[cl] = length + tc_length;
3674   }
3675
3676   // Add stats from per-thread heaps
3677   r->thread_bytes = 0;
3678   { // scope
3679     SpinLockHolder h(&pageheap_lock);
3680     for (TCMalloc_ThreadCache* h = thread_heaps; h != NULL; h = h->next_) {
3681       r->thread_bytes += h->Size();
3682       if (class_count) {
3683         for (size_t cl = 0; cl < kNumClasses; ++cl) {
3684           class_count[cl] += h->freelist_length(cl);
3685         }
3686       }
3687     }
3688   }
3689
3690   { //scope
3691     SpinLockHolder h(&pageheap_lock);
3692     r->system_bytes = pageheap->SystemBytes();
3693     r->metadata_bytes = metadata_system_bytes;
3694     r->pageheap_bytes = pageheap->FreeBytes();
3695   }
3696 }
3697 #endif
3698
3699 #ifndef WTF_CHANGES
3700 // WRITE stats to "out"
3701 static void DumpStats(TCMalloc_Printer* out, int level) {