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