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