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