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