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