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