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