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