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