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