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