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