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