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