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