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