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