00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076 #include "config.h"
00077 #include <new>
00078 #include <stdio.h>
00079 #include <stddef.h>
00080 #if defined HAVE_STDINT_H
00081 #include <stdint.h>
00082 #elif defined HAVE_INTTYPES_H
00083 #include <inttypes.h>
00084 #else
00085 #include <sys/types.h>
00086 #endif
00087 #if defined(HAVE_MALLOC_H) && defined(HAVE_STRUCT_MALLINFO)
00088 #include <malloc.h>
00089 #endif
00090 #include <string.h>
00091 #ifdef HAVE_PTHREAD
00092 #include <pthread.h>
00093 #endif
00094 #ifdef HAVE_UNISTD_H
00095 #include <unistd.h>
00096 #endif
00097 #include <errno.h>
00098 #include <stdarg.h>
00099 #include "packed-cache-inl.h"
00100 #include "base/commandlineflags.h"
00101 #include "base/basictypes.h"
00102 #include "base/sysinfo.h"
00103 #include "base/spinlock.h"
00104 #include <google/malloc_hook.h>
00105 #include <google/malloc_extension.h>
00106 #include "internal_logging.h"
00107 #include "pagemap.h"
00108 #include "system-alloc.h"
00109 #include "maybe_threads.h"
00110
00111
00112
00113 #ifdef NO_TCMALLOC_SAMPLES
00114
00115 # define GetStackTrace(stack, depth, skip) (0)
00116 #else
00117 # include <google/stacktrace.h>
00118 #endif
00119
00120
00121
00122
00123 #if defined(HAVE_TLS)
00124 static bool kernel_supports_tls = false;
00125 static inline bool KernelSupportsTLS() {
00126 return kernel_supports_tls;
00127 }
00128 # if !HAVE_DECL_UNAME // if too old for uname, probably too old for TLS
00129 static void CheckIfKernelSupportsTLS() {
00130 kernel_supports_tls = false;
00131 }
00132 # else
00133 # include <sys/utsname.h>
00134 static void CheckIfKernelSupportsTLS() {
00135 struct utsname buf;
00136 if (uname(&buf) != 0) {
00137 MESSAGE("uname failed assuming no TLS support (errno=%d)\n", errno);
00138 kernel_supports_tls = false;
00139 } else if (strcasecmp(buf.sysname, "linux") == 0) {
00140
00141 if (buf.release[0] < '2' && buf.release[1] == '.')
00142 kernel_supports_tls = false;
00143 else if (buf.release[0] == '2' && buf.release[1] == '.' &&
00144 buf.release[2] >= '0' && buf.release[2] < '6' &&
00145 buf.release[3] == '.')
00146 kernel_supports_tls = false;
00147 else
00148 kernel_supports_tls = true;
00149 } else {
00150 kernel_supports_tls = true;
00151 }
00152
00153 }
00154 # endif // HAVE_DECL_UNAME
00155 #endif // HAVE_TLS
00156
00157
00158
00159
00160 #ifndef __THROW // I guess we're not on a glibc system
00161 # define __THROW // __THROW is just an optimization, so ok to make it ""
00162 #endif
00163
00164
00165
00166
00167
00168
00169
00170
00171 static const size_t kPageShift = 12;
00172 static const size_t kPageSize = 1 << kPageShift;
00173 static const size_t kMaxSize = 8u * kPageSize;
00174 static const size_t kAlignShift = 3;
00175 static const size_t kAlignment = 1 << kAlignShift;
00176 static const size_t kNumClasses = 68;
00177
00178
00179
00180 static const size_t kPageMapBigAllocationThreshold = 128 << 20;
00181
00182
00183
00184
00185
00186
00187
00188 static const int kMinSystemAlloc = 1 << (20 - kPageShift);
00189
00190
00191
00192
00193
00194
00195 static int num_objects_to_move[kNumClasses];
00196
00197
00198
00199
00200
00201
00202 static const int kMaxFreeListLength = 256;
00203
00204
00205 static const size_t kMinThreadCacheSize = kMaxSize * 2;
00206 static const size_t kMaxThreadCacheSize = 2 << 20;
00207
00208
00209 static const size_t kDefaultOverallThreadCacheSize = 16 << 20;
00210
00211
00212
00213 static const size_t kMaxPages = kMinSystemAlloc;
00214
00215
00216 static unsigned int primes_list[] = {
00217
00218
00219
00220
00221 32771, 65537, 131101, 262147, 524309, 1048583,
00222 2097169, 4194319, 8388617, 16777259, 33554467 };
00223
00224
00225
00226
00227
00228
00229 #ifdef NO_TCMALLOC_SAMPLES
00230 DEFINE_int64(tcmalloc_sample_parameter, 0,
00231 "Unused: code is compiled with NO_TCMALLOC_SAMPLES");
00232 static size_t sample_period = 0;
00233 #else
00234 DEFINE_int64(tcmalloc_sample_parameter, 262147,
00235 "Twice the approximate gap between sampling actions."
00236 " Must be a prime number. Otherwise will be rounded up to a "
00237 " larger prime number");
00238 static size_t sample_period = 262147;
00239 #endif
00240
00241 static SpinLock sample_period_lock(SpinLock::LINKER_INITIALIZED);
00242
00243
00244
00245 DEFINE_double(tcmalloc_release_rate, 10,
00246 "Rate at which we release unused memory to the system. "
00247 "Zero means we never release memory back to the system. "
00248 "Increase this flag to return memory faster; decrease it "
00249 "to return memory slower. Reasonable rates are in the "
00250 "range [0,10]");
00251
00252
00253
00254
00255
00256
00257
00258
00259
00260
00261
00262
00263
00264
00265
00266
00267
00268
00269
00270
00271
00272
00273
00274 static const int kMaxSmallSize = 1024;
00275 static const int shift_amount[2] = { 3, 7 };
00276 static const int add_amount[2] = { 7, 127 + (120 << 7) };
00277 static unsigned char class_array[377];
00278
00279
00280 static inline int ClassIndex(size_t s) {
00281 const int i = (s > kMaxSmallSize);
00282 return (s + add_amount[i]) >> shift_amount[i];
00283 }
00284
00285
00286 static size_t class_to_size[kNumClasses];
00287
00288
00289 static size_t class_to_pages[kNumClasses];
00290
00291
00292
00293
00294 struct TCEntry {
00295 void *head;
00296 void *tail;
00297 };
00298
00299
00300
00301
00302
00303 static const int kNumTransferEntries = kNumClasses;
00304
00305
00306
00307 static inline int LgFloor(size_t n) {
00308 int log = 0;
00309 for (int i = 4; i >= 0; --i) {
00310 int shift = (1 << i);
00311 size_t x = n >> shift;
00312 if (x != 0) {
00313 n = x;
00314 log += shift;
00315 }
00316 }
00317 ASSERT(n == 1);
00318 return log;
00319 }
00320
00321
00322
00323
00324 static inline void *SLL_Next(void *t) {
00325 return *(reinterpret_cast<void**>(t));
00326 }
00327
00328 static inline void SLL_SetNext(void *t, void *n) {
00329 *(reinterpret_cast<void**>(t)) = n;
00330 }
00331
00332 static inline void SLL_Push(void **list, void *element) {
00333 SLL_SetNext(element, *list);
00334 *list = element;
00335 }
00336
00337 static inline void *SLL_Pop(void **list) {
00338 void *result = *list;
00339 *list = SLL_Next(*list);
00340 return result;
00341 }
00342
00343
00344
00345
00346
00347
00348 static inline void SLL_PopRange(void **head, int N, void **start, void **end) {
00349 if (N == 0) {
00350 *start = NULL;
00351 *end = NULL;
00352 return;
00353 }
00354
00355 void *tmp = *head;
00356 for (int i = 1; i < N; ++i) {
00357 tmp = SLL_Next(tmp);
00358 }
00359
00360 *start = *head;
00361 *end = tmp;
00362 *head = SLL_Next(tmp);
00363
00364 SLL_SetNext(tmp, NULL);
00365 }
00366
00367 static inline void SLL_PushRange(void **head, void *start, void *end) {
00368 if (!start) return;
00369 SLL_SetNext(end, *head);
00370 *head = start;
00371 }
00372
00373 static inline size_t SLL_Size(void *head) {
00374 int count = 0;
00375 while (head) {
00376 count++;
00377 head = SLL_Next(head);
00378 }
00379 return count;
00380 }
00381
00382
00383
00384 static inline int SizeClass(size_t size) {
00385 return class_array[ClassIndex(size)];
00386 }
00387
00388
00389 static inline size_t ByteSizeForClass(size_t cl) {
00390 return class_to_size[cl];
00391 }
00392
00393
00394 static int NumMoveSize(size_t size) {
00395 if (size == 0) return 0;
00396
00397 int num = static_cast<int>(64.0 * 1024.0 / size);
00398 if (num < 2) num = 2;
00399
00400
00401 if (num > static_cast<int>(0.8 * kMaxFreeListLength))
00402 num = static_cast<int>(0.8 * kMaxFreeListLength);
00403
00404
00405
00406
00407
00408
00409
00410
00411
00412 if (num > 32) num = 32;
00413
00414 return num;
00415 }
00416
00417
00418 static void InitSizeClasses() {
00419
00420 if (ClassIndex(0) < 0) {
00421 MESSAGE("Invalid class index %d for size 0\n", ClassIndex(0));
00422 abort();
00423 }
00424 if (ClassIndex(kMaxSize) >= sizeof(class_array)) {
00425 MESSAGE("Invalid class index %d for kMaxSize\n", ClassIndex(kMaxSize));
00426 abort();
00427 }
00428
00429
00430 int sc = 1;
00431 int alignshift = kAlignShift;
00432 int last_lg = -1;
00433 for (size_t size = kAlignment; size <= kMaxSize; size += (1 << alignshift)) {
00434 int lg = LgFloor(size);
00435 if (lg > last_lg) {
00436
00437
00438
00439
00440
00441
00442
00443 if ((lg >= 7) && (alignshift < 8)) {
00444 alignshift++;
00445 }
00446 last_lg = lg;
00447 }
00448
00449
00450
00451 size_t psize = kPageSize;
00452 while ((psize % size) > (psize >> 3)) {
00453 psize += kPageSize;
00454 }
00455 const size_t my_pages = psize >> kPageShift;
00456
00457 if (sc > 1 && my_pages == class_to_pages[sc-1]) {
00458
00459
00460 const size_t my_objects = (my_pages << kPageShift) / size;
00461 const size_t prev_objects = (class_to_pages[sc-1] << kPageShift)
00462 / class_to_size[sc-1];
00463 if (my_objects == prev_objects) {
00464
00465 class_to_size[sc-1] = size;
00466 continue;
00467 }
00468 }
00469
00470
00471 class_to_pages[sc] = my_pages;
00472 class_to_size[sc] = size;
00473 sc++;
00474 }
00475 if (sc != kNumClasses) {
00476 MESSAGE("wrong number of size classes: found %d instead of %d\n",
00477 sc, int(kNumClasses));
00478 abort();
00479 }
00480
00481
00482 int next_size = 0;
00483 for (int c = 1; c < kNumClasses; c++) {
00484 const int max_size_in_class = class_to_size[c];
00485 for (int s = next_size; s <= max_size_in_class; s += kAlignment) {
00486 class_array[ClassIndex(s)] = c;
00487 }
00488 next_size = max_size_in_class + kAlignment;
00489 }
00490
00491
00492 for (size_t size = 0; size <= kMaxSize; size++) {
00493 const int sc = SizeClass(size);
00494 if (sc == 0) {
00495 MESSAGE("Bad size class %d for %" PRIuS "\n", sc, size);
00496 abort();
00497 }
00498 if (sc > 1 && size <= class_to_size[sc-1]) {
00499 MESSAGE("Allocating unnecessarily large class %d for %" PRIuS
00500 "\n", sc, size);
00501 abort();
00502 }
00503 if (sc >= kNumClasses) {
00504 MESSAGE("Bad size class %d for %" PRIuS "\n", sc, size);
00505 abort();
00506 }
00507 const size_t s = class_to_size[sc];
00508 if (size > s) {
00509 MESSAGE("Bad size %" PRIuS " for %" PRIuS " (sc = %d)\n", s, size, sc);
00510 abort();
00511 }
00512 if (s == 0) {
00513 MESSAGE("Bad size %" PRIuS " for %" PRIuS " (sc = %d)\n", s, size, sc);
00514 abort();
00515 }
00516 }
00517
00518
00519 for (size_t cl = 1; cl < kNumClasses; ++cl) {
00520 num_objects_to_move[cl] = NumMoveSize(ByteSizeForClass(cl));
00521 }
00522
00523 if (false) {
00524
00525 for (size_t cl = 1; cl < kNumClasses; ++cl) {
00526 const int alloc_size = class_to_pages[cl] << kPageShift;
00527 const int alloc_objs = alloc_size / class_to_size[cl];
00528 const int min_used = (class_to_size[cl-1] + 1) * alloc_objs;
00529 const int max_waste = alloc_size - min_used;
00530 MESSAGE("SC %3d [ %8d .. %8d ] from %8d ; %2.0f%% maxwaste\n",
00531 int(cl),
00532 int(class_to_size[cl-1] + 1),
00533 int(class_to_size[cl]),
00534 int(class_to_pages[cl] << kPageShift),
00535 max_waste * 100.0 / alloc_size
00536 );
00537 }
00538 }
00539 }
00540
00541
00542
00543
00544
00545
00546
00547 static uint64_t metadata_system_bytes = 0;
00548 static void* MetaDataAlloc(size_t bytes) {
00549 void* result = TCMalloc_SystemAlloc(bytes, NULL);
00550 if (result != NULL) {
00551 metadata_system_bytes += bytes;
00552 }
00553 return result;
00554 }
00555
00556 template <class T>
00557 class PageHeapAllocator {
00558 private:
00559
00560 static const int kAllocIncrement = 128 << 10;
00561
00562
00563 static const size_t kAlignedSize
00564 = (((sizeof(T) + kAlignment - 1) / kAlignment) * kAlignment);
00565
00566
00567 char* free_area_;
00568 size_t free_avail_;
00569
00570
00571 void* free_list_;
00572
00573
00574 int inuse_;
00575
00576 public:
00577 void Init() {
00578 ASSERT(kAlignedSize <= kAllocIncrement);
00579 inuse_ = 0;
00580 free_area_ = NULL;
00581 free_avail_ = 0;
00582 free_list_ = NULL;
00583
00584 Delete(New());
00585 }
00586
00587 T* New() {
00588
00589 void* result;
00590 if (free_list_ != NULL) {
00591 result = free_list_;
00592 free_list_ = *(reinterpret_cast<void**>(result));
00593 } else {
00594 if (free_avail_ < kAlignedSize) {
00595
00596 free_area_ = reinterpret_cast<char*>(MetaDataAlloc(kAllocIncrement));
00597 if (free_area_ == NULL) abort();
00598 free_avail_ = kAllocIncrement;
00599 }
00600 result = free_area_;
00601 free_area_ += kAlignedSize;
00602 free_avail_ -= kAlignedSize;
00603 }
00604 inuse_++;
00605 return reinterpret_cast<T*>(result);
00606 }
00607
00608 void Delete(T* p) {
00609 *(reinterpret_cast<void**>(p)) = free_list_;
00610 free_list_ = p;
00611 inuse_--;
00612 }
00613
00614 int inuse() const { return inuse_; }
00615 };
00616
00617
00618
00619
00620
00621
00622 typedef uintptr_t PageID;
00623
00624
00625 typedef uintptr_t Length;
00626
00627 static const Length kMaxValidPages = (~static_cast<Length>(0)) >> kPageShift;
00628
00629
00630
00631 static inline Length pages(size_t bytes) {
00632 return (bytes >> kPageShift) +
00633 ((bytes & (kPageSize - 1)) > 0 ? 1 : 0);
00634 }
00635
00636
00637
00638 static size_t AllocationSize(size_t bytes) {
00639 if (bytes > kMaxSize) {
00640
00641 ASSERT(bytes <= (kMaxValidPages << kPageShift));
00642 return pages(bytes) << kPageShift;
00643 } else {
00644
00645 return ByteSizeForClass(SizeClass(bytes));
00646 }
00647 }
00648
00649
00650 struct Span {
00651 PageID start;
00652 Length length;
00653 Span* next;
00654 Span* prev;
00655 void* objects;
00656 unsigned int free : 1;
00657 unsigned int sample : 1;
00658 unsigned int sizeclass : 8;
00659 unsigned int refcount : 11;
00660
00661 #undef SPAN_HISTORY
00662 #ifdef SPAN_HISTORY
00663
00664 int nexthistory;
00665 char history[64];
00666 int value[64];
00667 #endif
00668 };
00669
00670 #ifdef SPAN_HISTORY
00671 void Event(Span* span, char op, int v = 0) {
00672 span->history[span->nexthistory] = op;
00673 span->value[span->nexthistory] = v;
00674 span->nexthistory++;
00675 if (span->nexthistory == sizeof(span->history)) span->nexthistory = 0;
00676 }
00677 #else
00678 #define Event(s,o,v) ((void) 0)
00679 #endif
00680
00681
00682 static PageHeapAllocator<Span> span_allocator;
00683 static Span* NewSpan(PageID p, Length len) {
00684 Span* result = span_allocator.New();
00685 memset(result, 0, sizeof(*result));
00686 result->start = p;
00687 result->length = len;
00688 #ifdef SPAN_HISTORY
00689 result->nexthistory = 0;
00690 #endif
00691 return result;
00692 }
00693
00694 static void DeleteSpan(Span* span) {
00695 #ifndef NDEBUG
00696
00697 memset(span, 0x3f, sizeof(*span));
00698 #endif
00699 span_allocator.Delete(span);
00700 }
00701
00702
00703
00704
00705
00706 static void DLL_Init(Span* list) {
00707 list->next = list;
00708 list->prev = list;
00709 }
00710
00711 static void DLL_Remove(Span* span) {
00712 span->prev->next = span->next;
00713 span->next->prev = span->prev;
00714 span->prev = NULL;
00715 span->next = NULL;
00716 }
00717
00718 static inline bool DLL_IsEmpty(const Span* list) {
00719 return list->next == list;
00720 }
00721
00722 static int DLL_Length(const Span* list) {
00723 int result = 0;
00724 for (Span* s = list->next; s != list; s = s->next) {
00725 result++;
00726 }
00727 return result;
00728 }
00729
00730 #if 0
00731 static void DLL_Print(const char* label, const Span* list) {
00732 MESSAGE("%-10s %p:", label, list);
00733 for (const Span* s = list->next; s != list; s = s->next) {
00734 MESSAGE(" <%p,%u,%u>", s, s->start, s->length);
00735 }
00736 MESSAGE("\n");
00737 }
00738 #endif
00739
00740 static void DLL_Prepend(Span* list, Span* span) {
00741 ASSERT(span->next == NULL);
00742 ASSERT(span->prev == NULL);
00743 span->next = list->next;
00744 span->prev = list;
00745 list->next->prev = span;
00746 list->next = span;
00747 }
00748
00749
00750
00751
00752
00753
00754
00755
00756 static const int kMaxStackDepth = 31;
00757 struct StackTrace {
00758 uintptr_t size;
00759 uintptr_t depth;
00760 void* stack[kMaxStackDepth];
00761 };
00762 static PageHeapAllocator<StackTrace> stacktrace_allocator;
00763 static Span sampled_objects;
00764
00765
00766
00767
00768
00769 static StackTrace* growth_stacks = NULL;
00770
00771
00772
00773
00774
00775
00776
00777
00778
00779
00780 template <int BITS> class MapSelector {
00781 public:
00782 typedef TCMalloc_PageMap3<BITS-kPageShift> Type;
00783 typedef PackedCache<BITS, uint64> CacheType;
00784 };
00785
00786
00787 template <> class MapSelector<32> {
00788 public:
00789 typedef TCMalloc_PageMap2<32-kPageShift> Type;
00790 typedef PackedCache<32-kPageShift, uint16> CacheType;
00791 };
00792
00793
00794
00795
00796
00797
00798
00799
00800
00801 class TCMalloc_PageHeap {
00802 public:
00803 TCMalloc_PageHeap();
00804
00805
00806
00807
00808 Span* New(Length n);
00809
00810
00811
00812
00813 void Delete(Span* span);
00814
00815
00816
00817
00818
00819 void RegisterSizeClass(Span* span, size_t sc);
00820
00821
00822
00823
00824
00825
00826
00827
00828
00829 Span* Split(Span* span, Length n);
00830
00831
00832 inline Span* GetDescriptor(PageID p) const {
00833 return reinterpret_cast<Span*>(pagemap_.get(p));
00834 }
00835
00836
00837 void Dump(TCMalloc_Printer* out);
00838
00839
00840 inline uint64_t SystemBytes() const { return system_bytes_; }
00841
00842
00843 uint64_t FreeBytes() const {
00844 return (static_cast<uint64_t>(free_pages_) << kPageShift);
00845 }
00846
00847 bool Check();
00848 bool CheckList(Span* list, Length min_pages, Length max_pages);
00849
00850
00851 void ReleaseFreePages();
00852
00853
00854
00855
00856
00857
00858 size_t GetSizeClassIfCached(PageID p) const {
00859 return pagemap_cache_.GetOrDefault(p, 0);
00860 }
00861 void CacheSizeClass(PageID p, size_t cl) const { pagemap_cache_.Put(p, cl); }
00862
00863 private:
00864
00865 typedef MapSelector<8*sizeof(uintptr_t)>::Type PageMap;
00866 typedef MapSelector<8*sizeof(uintptr_t)>::CacheType PageMapCache;
00867 PageMap pagemap_;
00868 mutable PageMapCache pagemap_cache_;
00869
00870
00871
00872
00873 struct SpanList {
00874 Span normal;
00875 Span returned;
00876 };
00877
00878
00879 SpanList large_;
00880
00881
00882 SpanList free_[kMaxPages];
00883
00884
00885 uintptr_t free_pages_;
00886
00887
00888 uint64_t system_bytes_;
00889
00890 bool GrowHeap(Length n);
00891
00892
00893
00894
00895
00896
00897
00898
00899 void Carve(Span* span, Length n, bool released);
00900
00901 void RecordSpan(Span* span) {
00902 pagemap_.set(span->start, span);
00903 if (span->length > 1) {
00904 pagemap_.set(span->start + span->length - 1, span);
00905 }
00906 }
00907
00908
00909
00910 Span* AllocLarge(Length n);
00911
00912
00913
00914 void IncrementalScavenge(Length n);
00915
00916
00917 int64_t scavenge_counter_;
00918
00919
00920 int scavenge_index_;
00921 };
00922
00923 TCMalloc_PageHeap::TCMalloc_PageHeap()
00924 : pagemap_(MetaDataAlloc),
00925 pagemap_cache_(0),
00926 free_pages_(0),
00927 system_bytes_(0),
00928 scavenge_counter_(0),
00929
00930 scavenge_index_(kMaxPages-1) {
00931 COMPILE_ASSERT(kNumClasses <= (1 << PageMapCache::kValuebits), valuebits);
00932 DLL_Init(&large_.normal);
00933 DLL_Init(&large_.returned);
00934 for (int i = 0; i < kMaxPages; i++) {
00935 DLL_Init(&free_[i].normal);
00936 DLL_Init(&free_[i].returned);
00937 }
00938 }
00939
00940 Span* TCMalloc_PageHeap::New(Length n) {
00941 ASSERT(Check());
00942 ASSERT(n > 0);
00943
00944
00945 for (Length s = n; s < kMaxPages; s++) {
00946 Span* ll = NULL;
00947 bool released = false;
00948 if (!DLL_IsEmpty(&free_[s].normal)) {
00949
00950 ll = &free_[s].normal;
00951 } else if (!DLL_IsEmpty(&free_[s].returned)) {
00952
00953 ll = &free_[s].returned;
00954 released = true;
00955 } else {
00956
00957 continue;
00958 }
00959
00960 Span* result = ll->next;
00961 Carve(result, n, released);
00962 ASSERT(Check());
00963 free_pages_ -= n;
00964 return result;
00965 }
00966
00967 Span* result = AllocLarge(n);
00968 if (result != NULL) return result;
00969
00970
00971 if (!GrowHeap(n)) {
00972 ASSERT(Check());
00973 return NULL;
00974 }
00975
00976 return AllocLarge(n);
00977 }
00978
00979 Span* TCMalloc_PageHeap::AllocLarge(Length n) {
00980
00981
00982 bool from_released = false;
00983 Span *best = NULL;
00984
00985
00986 for (Span* span = large_.normal.next;
00987 span != &large_.normal;
00988 span = span->next) {
00989 if (span->length >= n) {
00990 if ((best == NULL)
00991 || (span->length < best->length)
00992 || ((span->length == best->length) && (span->start < best->start))) {
00993 best = span;
00994 from_released = false;
00995 }
00996 }
00997 }
00998
00999
01000 for (Span* span = large_.returned.next;
01001 span != &large_.returned;
01002 span = span->next) {
01003 if (span->length >= n) {
01004 if ((best == NULL)
01005 || (span->length < best->length)
01006 || ((span->length == best->length) && (span->start < best->start))) {
01007 best = span;
01008 from_released = true;
01009 }
01010 }
01011 }
01012
01013 if (best != NULL) {
01014 Carve(best, n, from_released);
01015 ASSERT(Check());
01016 free_pages_ -= n;
01017 return best;
01018 }
01019 return NULL;
01020 }
01021
01022 Span* TCMalloc_PageHeap::Split(Span* span, Length n) {
01023 ASSERT(0 < n);
01024 ASSERT(n < span->length);
01025 ASSERT(!span->free);
01026 ASSERT(span->sizeclass == 0);
01027 Event(span, 'T', n);
01028
01029 const int extra = span->length - n;
01030 Span* leftover = NewSpan(span->start + n, extra);
01031 Event(leftover, 'U', extra);
01032 RecordSpan(leftover);
01033 pagemap_.set(span->start + n - 1, span);
01034 span->length = n;
01035
01036 return leftover;
01037 }
01038
01039 void TCMalloc_PageHeap::Carve(Span* span, Length n, bool released) {
01040 ASSERT(n > 0);
01041 DLL_Remove(span);
01042 span->free = 0;
01043 Event(span, 'A', n);
01044
01045 const int extra = span->length - n;
01046 ASSERT(extra >= 0);
01047 if (extra > 0) {
01048 Span* leftover = NewSpan(span->start + n, extra);
01049 leftover->free = 1;
01050 Event(leftover, 'S', extra);
01051 RecordSpan(leftover);
01052
01053
01054 SpanList* listpair = (extra < kMaxPages) ? &free_[extra] : &large_;
01055 Span* dst = released ? &listpair->returned : &listpair->normal;
01056 DLL_Prepend(dst, leftover);
01057
01058 span->length = n;
01059 pagemap_.set(span->start + n - 1, span);
01060 }
01061 }
01062
01063 void TCMalloc_PageHeap::Delete(Span* span) {
01064 ASSERT(Check());
01065 ASSERT(!span->free);
01066 ASSERT(span->length > 0);
01067 ASSERT(GetDescriptor(span->start) == span);
01068 ASSERT(GetDescriptor(span->start + span->length - 1) == span);
01069 span->sizeclass = 0;
01070 span->sample = 0;
01071
01072
01073
01074
01075
01076
01077
01078
01079
01080 const PageID p = span->start;
01081 const Length n = span->length;
01082 Span* prev = GetDescriptor(p-1);
01083 if (prev != NULL && prev->free) {
01084
01085 ASSERT(prev->start + prev->length == p);
01086 const Length len = prev->length;
01087 DLL_Remove(prev);
01088 DeleteSpan(prev);
01089 span->start -= len;
01090 span->length += len;
01091 pagemap_.set(span->start, span);
01092 Event(span, 'L', len);
01093 }
01094 Span* next = GetDescriptor(p+n);
01095 if (next != NULL && next->free) {
01096
01097 ASSERT(next->start == p+n);
01098 const Length len = next->length;
01099 DLL_Remove(next);
01100 DeleteSpan(next);
01101 span->length += len;
01102 pagemap_.set(span->start + span->length - 1, span);
01103 Event(span, 'R', len);
01104 }
01105
01106 Event(span, 'D', span->length);
01107 span->free = 1;
01108 if (span->length < kMaxPages) {
01109 DLL_Prepend(&free_[span->length].normal, span);
01110 } else {
01111 DLL_Prepend(&large_.normal, span);
01112 }
01113 free_pages_ += n;
01114
01115 IncrementalScavenge(n);
01116 ASSERT(Check());
01117 }
01118
01119 void TCMalloc_PageHeap::IncrementalScavenge(Length n) {
01120
01121 scavenge_counter_ -= n;
01122 if (scavenge_counter_ >= 0) return;
01123
01124
01125
01126
01127 static const int kMaxReleaseDelay = 1 << 20;
01128
01129
01130
01131 static const int kDefaultReleaseDelay = 1 << 18;
01132
01133 const double rate = FLAGS_tcmalloc_release_rate;
01134 if (rate <= 1e-6) {
01135
01136 scavenge_counter_ = kDefaultReleaseDelay;
01137 return;
01138 }
01139
01140
01141 int index = scavenge_index_ + 1;
01142 for (int i = 0; i < kMaxPages+1; i++) {
01143 if (index > kMaxPages) index = 0;
01144 SpanList* slist = (index == kMaxPages) ? &large_ : &free_[index];
01145 if (!DLL_IsEmpty(&slist->normal)) {
01146
01147 Span* s = slist->normal.prev;
01148 DLL_Remove(s);
01149 TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift),
01150 static_cast<size_t>(s->length << kPageShift));
01151 DLL_Prepend(&slist->returned, s);
01152
01153
01154
01155
01156 const double mult = 1000.0 / rate;
01157 double wait = mult * static_cast<double>(s->length);
01158 if (wait > kMaxReleaseDelay) {
01159
01160 wait = kMaxReleaseDelay;
01161 }
01162 scavenge_counter_ = static_cast<int64_t>(wait);
01163
01164 scavenge_index_ = index;
01165 return;
01166 }
01167 index++;
01168 }
01169
01170
01171 scavenge_counter_ = kDefaultReleaseDelay;
01172 }
01173
01174 void TCMalloc_PageHeap::RegisterSizeClass(Span* span, size_t sc) {
01175
01176 ASSERT(!span->free);
01177 ASSERT(GetDescriptor(span->start) == span);
01178 ASSERT(GetDescriptor(span->start+span->length-1) == span);
01179 Event(span, 'C', sc);
01180 span->sizeclass = sc;
01181 for (Length i = 1; i < span->length-1; i++) {
01182 pagemap_.set(span->start+i, span);
01183 }
01184 }
01185
01186 static double PagesToMB(uint64_t pages) {
01187 return (pages << kPageShift) / 1048576.0;
01188 }
01189
01190 void TCMalloc_PageHeap::Dump(TCMalloc_Printer* out) {
01191 int nonempty_sizes = 0;
01192 for (int s = 0; s < kMaxPages; s++) {
01193 if (!DLL_IsEmpty(&free_[s].normal) || !DLL_IsEmpty(&free_[s].returned)) {
01194 nonempty_sizes++;
01195 }
01196 }
01197 out->printf("------------------------------------------------\n");
01198 out->printf("PageHeap: %d sizes; %6.1f MB free\n",
01199 nonempty_sizes, PagesToMB(free_pages_));
01200 out->printf("------------------------------------------------\n");
01201 uint64_t total_normal = 0;
01202 uint64_t total_returned = 0;
01203 for (int s = 0; s < kMaxPages; s++) {
01204 const int n_length = DLL_Length(&free_[s].normal);
01205 const int r_length = DLL_Length(&free_[s].returned);
01206 if (n_length + r_length > 0) {
01207 uint64_t n_pages = s * n_length;
01208 uint64_t r_pages = s * r_length;
01209 total_normal += n_pages;
01210 total_returned += r_pages;
01211 out->printf("%6u pages * %6u spans ~ %6.1f MB; %6.1f MB cum"
01212 "; unmapped: %6.1f MB; %6.1f MB cum\n",
01213 s,
01214 (n_length + r_length),
01215 PagesToMB(n_pages + r_pages),
01216 PagesToMB(total_normal + total_returned),
01217 PagesToMB(r_pages),
01218 PagesToMB(total_returned));
01219 }
01220 }
01221
01222 uint64_t n_pages = 0;
01223 uint64_t r_pages = 0;
01224 int n_spans = 0;
01225 int r_spans = 0;
01226 out->printf("Normal large spans:\n");
01227 for (Span* s = large_.normal.next; s != &large_.normal; s = s->next) {
01228 out->printf(" [ %6" PRIuS " pages ] %6.1f MB\n",
01229 s->length, PagesToMB(s->length));
01230 n_pages += s->length;
01231 n_spans++;
01232 }
01233 out->printf("Unmapped large spans:\n");
01234 for (Span* s = large_.returned.next; s != &large_.returned; s = s->next) {
01235 out->printf(" [ %6" PRIuS " pages ] %6.1f MB\n",
01236 s->length, PagesToMB(s->length));
01237 r_pages += s->length;
01238 r_spans++;
01239 }
01240 total_normal += n_pages;
01241 total_returned += r_pages;
01242 out->printf(">255 large * %6u spans ~ %6.1f MB; %6.1f MB cum"
01243 "; unmapped: %6.1f MB; %6.1f MB cum\n",
01244 (n_spans + r_spans),
01245 PagesToMB(n_pages + r_pages),
01246 PagesToMB(total_normal + total_returned),
01247 PagesToMB(r_pages),
01248 PagesToMB(total_returned));
01249 }
01250
01251 static void RecordGrowth(size_t growth) {
01252 StackTrace* t = stacktrace_allocator.New();
01253 t->depth = GetStackTrace(t->stack, kMaxStackDepth-1, 3);
01254 t->size = growth;
01255 t->stack[kMaxStackDepth-1] = reinterpret_cast<void*>(growth_stacks);
01256 growth_stacks = t;
01257 }
01258
01259 bool TCMalloc_PageHeap::GrowHeap(Length n) {
01260 ASSERT(kMaxPages >= kMinSystemAlloc);
01261 if (n > kMaxValidPages) return false;
01262 Length ask = (n>kMinSystemAlloc) ? n : static_cast<Length>(kMinSystemAlloc);
01263 size_t actual_size;
01264 void* ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize);
01265 if (ptr == NULL) {
01266 if (n < ask) {
01267
01268 ask = n;
01269 ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize);
01270 }
01271 if (ptr == NULL) return false;
01272 }
01273 ask = actual_size >> kPageShift;
01274 RecordGrowth(ask << kPageShift);
01275
01276 uint64_t old_system_bytes = system_bytes_;
01277 system_bytes_ += (ask << kPageShift);
01278 const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift;
01279 ASSERT(p > 0);
01280
01281
01282
01283
01284
01285 if (old_system_bytes < kPageMapBigAllocationThreshold
01286 && system_bytes_ >= kPageMapBigAllocationThreshold) {
01287 pagemap_.PreallocateMoreMemory();
01288 }
01289
01290
01291
01292
01293 if (pagemap_.Ensure(p-1, ask+2)) {
01294
01295
01296
01297
01298 Span* span = NewSpan(p, ask);
01299 RecordSpan(span);
01300 Delete(span);
01301 ASSERT(Check());
01302 return true;
01303 } else {
01304
01305
01306 return false;
01307 }
01308 }
01309
01310 bool TCMalloc_PageHeap::Check() {
01311 ASSERT(free_[0].normal.next == &free_[0].normal);
01312 ASSERT(free_[0].returned.next == &free_[0].returned);
01313 CheckList(&large_.normal, kMaxPages, 1000000000);
01314 CheckList(&large_.returned, kMaxPages, 1000000000);
01315 for (Length s = 1; s < kMaxPages; s++) {
01316 CheckList(&free_[s].normal, s, s);
01317 CheckList(&free_[s].returned, s, s);
01318 }
01319 return true;
01320 }
01321
01322 bool TCMalloc_PageHeap::CheckList(Span* list, Length min_pages, Length max_pages) {
01323 for (Span* s = list->next; s != list; s = s->next) {
01324 CHECK_CONDITION(s->free);
01325 CHECK_CONDITION(s->length >= min_pages);
01326 CHECK_CONDITION(s->length <= max_pages);
01327 CHECK_CONDITION(GetDescriptor(s->start) == s);
01328 CHECK_CONDITION(GetDescriptor(s->start+s->length-1) == s);
01329 }
01330 return true;
01331 }
01332
01333 static void ReleaseFreeList(Span* list, Span* returned) {
01334
01335
01336 while (!DLL_IsEmpty(list)) {
01337 Span* s = list->prev;
01338 DLL_Remove(s);
01339 DLL_Prepend(returned, s);
01340 TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift),
01341 static_cast<size_t>(s->length << kPageShift));
01342 }
01343 }
01344
01345 void TCMalloc_PageHeap::ReleaseFreePages() {
01346 for (Length s = 0; s < kMaxPages; s++) {
01347 ReleaseFreeList(&free_[s].normal, &free_[s].returned);
01348 }
01349 ReleaseFreeList(&large_.normal, &large_.returned);
01350 ASSERT(Check());
01351 }
01352
01353
01354
01355
01356
01357 class TCMalloc_ThreadCache_FreeList {
01358 private:
01359 void* list_;
01360 uint16_t length_;
01361 uint16_t lowater_;
01362
01363 public:
01364 void Init() {
01365 list_ = NULL;
01366 length_ = 0;
01367 lowater_ = 0;
01368 }
01369
01370
01371 int length() const {
01372 return length_;
01373 }
01374
01375
01376 bool empty() const {
01377 return list_ == NULL;
01378 }
01379
01380
01381 int lowwatermark() const { return lowater_; }
01382 void clear_lowwatermark() { lowater_ = length_; }
01383
01384 void Push(void* ptr) {
01385 SLL_Push(&list_, ptr);
01386 length_++;
01387 }
01388
01389 void* Pop() {
01390 ASSERT(list_ != NULL);
01391 length_--;
01392 if (length_ < lowater_) lowater_ = length_;
01393 return SLL_Pop(&list_);
01394 }
01395
01396 void PushRange(int N, void *start, void *end) {
01397 SLL_PushRange(&list_, start, end);
01398 length_ += N;
01399 }
01400
01401 void PopRange(int N, void **start, void **end) {
01402 SLL_PopRange(&list_, N, start, end);
01403 ASSERT(length_ >= N);
01404 length_ -= N;
01405 if (length_ < lowater_) lowater_ = length_;
01406 }
01407 };
01408
01409
01410
01411
01412
01413 class TCMalloc_ThreadCache {
01414 private:
01415 typedef TCMalloc_ThreadCache_FreeList FreeList;
01416
01417 size_t size_;
01418 pthread_t tid_;
01419 bool in_setspecific_;
01420 FreeList list_[kNumClasses];
01421
01422
01423 uint32_t rnd_;
01424 size_t bytes_until_sample_;
01425
01426
01427 static inline TCMalloc_ThreadCache* NewHeap(pthread_t tid);
01428
01429
01430 static void DestroyThreadCache(void* ptr);
01431 public:
01432
01433 TCMalloc_ThreadCache* next_;
01434 TCMalloc_ThreadCache* prev_;
01435
01436 void Init(pthread_t tid);
01437 void Cleanup();
01438
01439
01440 int freelist_length(size_t cl) const { return list_[cl].length(); }
01441
01442
01443 size_t Size() const { return size_; }
01444
01445 void* Allocate(size_t size);
01446 void Deallocate(void* ptr, size_t size_class);
01447
01448 void FetchFromCentralCache(size_t cl);
01449 void ReleaseToCentralCache(size_t cl, int N);
01450 void Scavenge();
01451 void Print() const;
01452
01453
01454
01455 bool SampleAllocation(size_t k);
01456
01457
01458 void PickNextSample(size_t k);
01459
01460 static void InitModule();
01461 static void InitTSD();
01462 static TCMalloc_ThreadCache* GetThreadHeap();
01463 static TCMalloc_ThreadCache* GetCache();
01464 static TCMalloc_ThreadCache* GetCacheIfPresent();
01465 static TCMalloc_ThreadCache* CreateCacheIfNecessary();
01466 static void DeleteCache(TCMalloc_ThreadCache* heap);
01467 static void BecomeIdle();
01468 static void RecomputeThreadCacheSize();
01469 };
01470
01471
01472
01473
01474
01475 class TCMalloc_Central_FreeList {
01476 public:
01477 void Init(size_t cl);
01478
01479
01480
01481
01482
01483 void InsertRange(void *start, void *end, int N);
01484
01485
01486 void RemoveRange(void **start, void **end, int *N);
01487
01488
01489 int length() {
01490 SpinLockHolder h(&lock_);
01491 return counter_;
01492 }
01493
01494
01495 int tc_length() {
01496 SpinLockHolder h(&lock_);
01497 return used_slots_ * num_objects_to_move[size_class_];
01498 }
01499
01500 private:
01501
01502
01503
01504 void* FetchFromSpans();
01505
01506
01507
01508
01509
01510 void* FetchFromSpansSafe();
01511
01512
01513
01514
01515 void ReleaseListToSpans(void *start);
01516
01517
01518
01519
01520 void ReleaseToSpans(void* object);
01521
01522
01523
01524
01525 void Populate();
01526
01527
01528
01529
01530
01531 bool MakeCacheSpace();
01532
01533
01534
01535
01536
01537
01538 static bool EvictRandomSizeClass(int locked_size_class, bool force);
01539
01540
01541
01542
01543
01544
01545
01546
01547 bool ShrinkCache(int locked_size_class, bool force);
01548
01549
01550
01551 SpinLock lock_;
01552
01553
01554 size_t size_class_;
01555 Span empty_;
01556 Span nonempty_;
01557 size_t counter_;
01558
01559
01560
01561
01562 TCEntry tc_slots_[kNumTransferEntries];
01563
01564
01565
01566 int32_t used_slots_;
01567
01568
01569
01570 int32_t cache_size_;
01571 };
01572
01573
01574 class TCMalloc_Central_FreeListPadded : public TCMalloc_Central_FreeList {
01575 private:
01576 char pad_[(64 - (sizeof(TCMalloc_Central_FreeList) % 64)) % 64];
01577 };
01578
01579
01580
01581
01582
01583
01584
01585 static TCMalloc_Central_FreeListPadded central_cache[kNumClasses];
01586
01587
01588 static SpinLock pageheap_lock(SpinLock::LINKER_INITIALIZED);
01589 static char pageheap_memory[sizeof(TCMalloc_PageHeap)];
01590 static bool phinited = false;
01591
01592
01593
01594 #define pageheap ((TCMalloc_PageHeap*) pageheap_memory)
01595
01596
01597
01598
01599
01600
01601
01602
01603 #ifdef HAVE_TLS
01604 static __thread TCMalloc_ThreadCache *threadlocal_heap;
01605 #endif
01606
01607
01608
01609
01610
01611 static bool tsd_inited = false;
01612 static pthread_key_t heap_key;
01613
01614
01615 static PageHeapAllocator<TCMalloc_ThreadCache> threadheap_allocator;
01616
01617
01618 static TCMalloc_ThreadCache* thread_heaps = NULL;
01619 static int thread_heap_count = 0;
01620
01621
01622 static size_t overall_thread_cache_size = kDefaultOverallThreadCacheSize;
01623
01624
01625
01626
01627
01628 static volatile size_t per_thread_cache_size = kMaxThreadCacheSize;
01629
01630
01631
01632
01633
01634 void TCMalloc_Central_FreeList::Init(size_t cl) {
01635 size_class_ = cl;
01636 DLL_Init(&empty_);
01637 DLL_Init(&nonempty_);
01638 counter_ = 0;
01639
01640 cache_size_ = 1;
01641 used_slots_ = 0;
01642 ASSERT(cache_size_ <= kNumTransferEntries);
01643 }
01644
01645 void TCMalloc_Central_FreeList::ReleaseListToSpans(void* start) {
01646 while (start) {
01647 void *next = SLL_Next(start);
01648 ReleaseToSpans(start);
01649 start = next;
01650 }
01651 }
01652
01653 void TCMalloc_Central_FreeList::ReleaseToSpans(void* object) {
01654 const PageID p = reinterpret_cast<uintptr_t>(object) >> kPageShift;
01655 Span* span = pageheap->GetDescriptor(p);
01656 ASSERT(span != NULL);
01657 ASSERT(span->refcount > 0);
01658
01659
01660 if (span->objects == NULL) {
01661 DLL_Remove(span);
01662 DLL_Prepend(&nonempty_, span);
01663 Event(span, 'N', 0);
01664 }
01665
01666
01667 if (false) {
01668
01669 int got = 0;
01670 for (void* p = span->objects; p != NULL; p = *((void**) p)) {
01671 ASSERT(p != object);
01672 got++;
01673 }
01674 ASSERT(got + span->refcount ==
01675 (span->length<<kPageShift)/ByteSizeForClass(span->sizeclass));
01676 }
01677
01678 counter_++;
01679 span->refcount--;
01680 if (span->refcount == 0) {
01681 Event(span, '#', 0);
01682 counter_ -= (span->length<<kPageShift) / ByteSizeForClass(span->sizeclass);
01683 DLL_Remove(span);
01684
01685
01686 lock_.Unlock();
01687 {
01688 SpinLockHolder h(&pageheap_lock);
01689 pageheap->Delete(span);
01690 }
01691 lock_.Lock();
01692 } else {
01693 *(reinterpret_cast<void**>(object)) = span->objects;
01694 span->objects = object;
01695 }
01696 }
01697
01698 bool TCMalloc_Central_FreeList::EvictRandomSizeClass(
01699 int locked_size_class, bool force) {
01700 static int race_counter = 0;
01701 int t = race_counter++;
01702 if (t >= kNumClasses) {
01703 while (t >= kNumClasses) {
01704 t -= kNumClasses;
01705 }
01706 race_counter = t;
01707 }
01708 ASSERT(t >= 0);
01709 ASSERT(t < kNumClasses);
01710 if (t == locked_size_class) return false;
01711 return central_cache[t].ShrinkCache(locked_size_class, force);
01712 }
01713
01714 bool TCMalloc_Central_FreeList::MakeCacheSpace() {
01715
01716 if (used_slots_ < cache_size_) return true;
01717
01718 if (cache_size_ == kNumTransferEntries) return false;
01719
01720 if (EvictRandomSizeClass(size_class_, false) ||
01721 EvictRandomSizeClass(size_class_, true)) {
01722
01723 cache_size_++;
01724 return true;
01725 }
01726 return false;
01727 }
01728
01729
01730 namespace {
01731 class LockInverter {
01732 private:
01733 SpinLock *held_, *temp_;
01734 public:
01735 inline explicit LockInverter(SpinLock* held, SpinLock *temp)
01736 : held_(held), temp_(temp) { held_->Unlock(); temp_->Lock(); }
01737 inline ~LockInverter() { temp_->Unlock(); held_->Lock(); }
01738 };
01739 }
01740
01741 bool TCMalloc_Central_FreeList::ShrinkCache(int locked_size_class, bool force) {
01742
01743 if (cache_size_ == 0) return false;
01744
01745 if (force == false && used_slots_ == cache_size_) return false;
01746
01747
01748
01749
01750
01751 LockInverter li(¢ral_cache[locked_size_class].lock_, &lock_);
01752 ASSERT(used_slots_ <= cache_size_);
01753 ASSERT(0 <= cache_size_);
01754 if (cache_size_ == 0) return false;
01755 if (used_slots_ == cache_size_) {
01756 if (force == false) return false;
01757
01758
01759 cache_size_--;
01760 used_slots_--;
01761 ReleaseListToSpans(tc_slots_[used_slots_].head);
01762 return true;
01763 }
01764 cache_size_--;
01765 return true;
01766 }
01767
01768 void TCMalloc_Central_FreeList::InsertRange(void *start, void *end, int N) {
01769 SpinLockHolder h(&lock_);
01770 if (N == num_objects_to_move[size_class_] &&
01771 MakeCacheSpace()) {
01772 int slot = used_slots_++;
01773 ASSERT(slot >=0);
01774 ASSERT(slot < kNumTransferEntries);
01775 TCEntry *entry = &tc_slots_[slot];
01776 entry->head = start;
01777 entry->tail = end;
01778 return;
01779 }
01780 ReleaseListToSpans(start);
01781 }
01782
01783 void TCMalloc_Central_FreeList::RemoveRange(void **start, void **end, int *N) {
01784 int num = *N;
01785 ASSERT(num > 0);
01786
01787 SpinLockHolder h(&lock_);
01788 if (num == num_objects_to_move[size_class_] && used_slots_ > 0) {
01789 int slot = --used_slots_;
01790 ASSERT(slot >= 0);
01791 TCEntry *entry = &tc_slots_[slot];
01792 *start = entry->head;
01793 *end = entry->tail;
01794 return;
01795 }
01796
01797
01798 void *tail = FetchFromSpansSafe();
01799 if (!tail) {
01800
01801 *start = *end = NULL;
01802 *N = 0;
01803 return;
01804 }
01805
01806 SLL_SetNext(tail, NULL);
01807 void *head = tail;
01808 int count = 1;
01809 while (count < num) {
01810 void *t = FetchFromSpans();
01811 if (!t) break;
01812 SLL_Push(&head, t);
01813 count++;
01814 }
01815 *start = head;
01816 *end = tail;
01817 *N = count;
01818 }
01819
01820
01821 void* TCMalloc_Central_FreeList::FetchFromSpansSafe() {
01822 void *t = FetchFromSpans();
01823 if (!t) {
01824 Populate();
01825 t = FetchFromSpans();
01826 }
01827 return t;
01828 }
01829
01830 void* TCMalloc_Central_FreeList::FetchFromSpans() {
01831 if (DLL_IsEmpty(&nonempty_)) return NULL;
01832 Span* span = nonempty_.next;
01833
01834 ASSERT(span->objects != NULL);
01835 span->refcount++;
01836 void* result = span->objects;
01837 span->objects = *(reinterpret_cast<void**>(result));
01838 if (span->objects == NULL) {
01839
01840 DLL_Remove(span);
01841 DLL_Prepend(&empty_, span);
01842 Event(span, 'E', 0);
01843 }
01844 counter_--;
01845 return result;
01846 }
01847
01848
01849 void TCMalloc_Central_FreeList::Populate() {
01850
01851 lock_.Unlock();
01852 const size_t npages = class_to_pages[size_class_];
01853
01854 Span* span;
01855 {
01856 SpinLockHolder h(&pageheap_lock);
01857 span = pageheap->New(npages);
01858 if (span) pageheap->RegisterSizeClass(span, size_class_);
01859 }
01860 if (span == NULL) {
01861 MESSAGE("allocation failed: %d\n", errno);
01862 lock_.Lock();
01863 return;
01864 }
01865 ASSERT(span->length == npages);
01866
01867
01868
01869 for (int i = 0; i < npages; i++) {
01870 pageheap->CacheSizeClass(span->start + i, size_class_);
01871 }
01872
01873
01874
01875 void** tail = &span->objects;
01876 char* ptr = reinterpret_cast<char*>(span->start << kPageShift);
01877 char* limit = ptr + (npages << kPageShift);
01878 const size_t size = ByteSizeForClass(size_class_);
01879 int num = 0;
01880 while (ptr + size <= limit) {
01881 *tail = ptr;
01882 tail = reinterpret_cast<void**>(ptr);
01883 ptr += size;
01884 num++;
01885 }
01886 ASSERT(ptr <= limit);
01887 *tail = NULL;
01888 span->refcount = 0;
01889
01890
01891 lock_.Lock();
01892 DLL_Prepend(&nonempty_, span);
01893 counter_ += num;
01894 }
01895
01896
01897
01898
01899
01900 inline bool TCMalloc_ThreadCache::SampleAllocation(size_t k) {
01901 if (bytes_until_sample_ < k) {
01902 PickNextSample(k);
01903 return true;
01904 } else {
01905 bytes_until_sample_ -= k;
01906 return false;
01907 }
01908 }
01909
01910 void TCMalloc_ThreadCache::Init(pthread_t tid) {
01911 size_ = 0;
01912 next_ = NULL;
01913 prev_ = NULL;
01914 tid_ = tid;
01915 in_setspecific_ = false;
01916 for (size_t cl = 0; cl < kNumClasses; ++cl) {
01917 list_[cl].Init();
01918 }
01919
01920
01921 bytes_until_sample_ = 0;
01922 rnd_ = static_cast<uint32_t>(reinterpret_cast<uintptr_t>(this));
01923 for (int i = 0; i < 100; i++) {
01924 PickNextSample(FLAGS_tcmalloc_sample_parameter * 2);
01925 }
01926 }
01927
01928 void TCMalloc_ThreadCache::Cleanup() {
01929
01930 for (int cl = 0; cl < kNumClasses; ++cl) {
01931 if (list_[cl].length() > 0) {
01932 ReleaseToCentralCache(cl, list_[cl].length());
01933 }
01934 }
01935 }
01936
01937 inline void* TCMalloc_ThreadCache::Allocate(size_t size) {
01938 ASSERT(size <= kMaxSize);
01939 const size_t cl = SizeClass(size);
01940 FreeList* list = &list_[cl];
01941 if (list->empty()) {
01942 FetchFromCentralCache(cl);
01943 if (list->empty()) return NULL;
01944 }
01945 size_ -= ByteSizeForClass(cl);
01946 return list->Pop();
01947 }
01948
01949 inline void TCMalloc_ThreadCache::Deallocate(void* ptr, size_t cl) {
01950 size_ += ByteSizeForClass(cl);
01951 FreeList* list = &list_[cl];
01952 list->Push(ptr);
01953
01954 if (list->length() > kMaxFreeListLength) {
01955 ReleaseToCentralCache(cl, num_objects_to_move[cl]);
01956 }
01957 if (size_ >= per_thread_cache_size) Scavenge();
01958 }
01959
01960
01961 void TCMalloc_ThreadCache::FetchFromCentralCache(size_t cl) {
01962 int fetch_count = num_objects_to_move[cl];
01963 void *start, *end;
01964 central_cache[cl].RemoveRange(&start, &end, &fetch_count);
01965 list_[cl].PushRange(fetch_count, start, end);
01966 size_ += ByteSizeForClass(cl) * fetch_count;
01967 }
01968
01969
01970 void TCMalloc_ThreadCache::ReleaseToCentralCache(size_t cl, int N) {
01971 ASSERT(N > 0);
01972 FreeList* src = &list_[cl];
01973 if (N > src->length()) N = src->length();
01974 size_ -= N*ByteSizeForClass(cl);
01975
01976
01977
01978 int batch_size = num_objects_to_move[cl];
01979 while (N > batch_size) {
01980 void *tail, *head;
01981 src->PopRange(batch_size, &head, &tail);
01982 central_cache[cl].InsertRange(head, tail, batch_size);
01983 N -= batch_size;
01984 }
01985 void *tail, *head;
01986 src->PopRange(N, &head, &tail);
01987 central_cache[cl].InsertRange(head, tail, N);
01988 }
01989
01990
01991 void TCMalloc_ThreadCache::Scavenge() {
01992
01993
01994
01995
01996
01997
01998
01999
02000 for (int cl = 0; cl < kNumClasses; cl++) {
02001 FreeList* list = &list_[cl];
02002 const int lowmark = list->lowwatermark();
02003 if (lowmark > 0) {
02004 const int drop = (lowmark > 1) ? lowmark/2 : 1;
02005 ReleaseToCentralCache(cl, drop);
02006 }
02007 list->clear_lowwatermark();
02008 }
02009
02010
02011
02012
02013 }
02014
02015 void TCMalloc_ThreadCache::PickNextSample(size_t k) {
02016
02017
02018 static const uint32_t kPoly = (1 << 22) | (1 << 2) | (1 << 1) | (1 << 0);
02019 uint32_t r = rnd_;
02020 rnd_ = (r << 1) ^ ((static_cast<int32_t>(r) >> 31) & kPoly);
02021
02022
02023
02024 const int flag_value = FLAGS_tcmalloc_sample_parameter;
02025 static int last_flag_value = -1;
02026
02027 if (flag_value != last_flag_value) {
02028 SpinLockHolder h(&sample_period_lock);
02029 int i;
02030 for (i = 0; i < (sizeof(primes_list)/sizeof(primes_list[0]) - 1); i++) {
02031 if (primes_list[i] >= flag_value) {
02032 break;
02033 }
02034 }
02035 sample_period = primes_list[i];
02036 last_flag_value = flag_value;
02037 }
02038
02039 bytes_until_sample_ += rnd_ % sample_period;
02040
02041 if (k > (static_cast<size_t>(-1) >> 2)) {
02042
02043
02044
02045
02046
02047
02048 return;
02049 }
02050
02051 while (bytes_until_sample_ < k) {
02052
02053
02054
02055 bytes_until_sample_ += (sample_period >> 1);
02056 }
02057
02058 bytes_until_sample_ -= k;
02059 }
02060
02061 void TCMalloc_ThreadCache::InitModule() {
02062
02063
02064
02065
02066
02067
02068 SpinLockHolder h(&pageheap_lock);
02069 if (!phinited) {
02070 InitSizeClasses();
02071 threadheap_allocator.Init();
02072 span_allocator.Init();
02073 span_allocator.New();
02074 span_allocator.New();
02075 stacktrace_allocator.Init();
02076 DLL_Init(&sampled_objects);
02077 for (int i = 0; i < kNumClasses; ++i) {
02078 central_cache[i].Init(i);
02079 }
02080 new ((void*)pageheap_memory) TCMalloc_PageHeap;
02081 phinited = 1;
02082 }
02083 }
02084
02085 inline TCMalloc_ThreadCache* TCMalloc_ThreadCache::NewHeap(pthread_t tid) {
02086
02087 TCMalloc_ThreadCache *heap = threadheap_allocator.New();
02088 heap->Init(tid);
02089 heap->next_ = thread_heaps;
02090 heap->prev_ = NULL;
02091 if (thread_heaps != NULL) thread_heaps->prev_ = heap;
02092 thread_heaps = heap;
02093 thread_heap_count++;
02094 RecomputeThreadCacheSize();
02095 return heap;
02096 }
02097
02098 inline TCMalloc_ThreadCache* TCMalloc_ThreadCache::GetThreadHeap() {
02099 #ifdef HAVE_TLS
02100
02101 if (KernelSupportsTLS())
02102 return threadlocal_heap;
02103 #endif
02104 return reinterpret_cast<TCMalloc_ThreadCache *>(
02105 perftools_pthread_getspecific(heap_key));
02106 }
02107
02108 inline TCMalloc_ThreadCache* TCMalloc_ThreadCache::GetCache() {
02109 TCMalloc_ThreadCache* ptr = NULL;
02110 if (!tsd_inited) {
02111 InitModule();
02112 } else {
02113 ptr = GetThreadHeap();
02114 }
02115 if (ptr == NULL) ptr = CreateCacheIfNecessary();
02116 return ptr;
02117 }
02118
02119
02120
02121
02122 inline TCMalloc_ThreadCache* TCMalloc_ThreadCache::GetCacheIfPresent() {
02123 if (!tsd_inited) return NULL;
02124 void* const p = GetThreadHeap();
02125 return reinterpret_cast<TCMalloc_ThreadCache*>(p);
02126 }
02127
02128 void TCMalloc_ThreadCache::InitTSD() {
02129 ASSERT(!tsd_inited);
02130 perftools_pthread_key_create(&heap_key, DestroyThreadCache);
02131 tsd_inited = true;
02132
02133
02134 pthread_t zero;
02135 memset(&zero, 0, sizeof(zero));
02136 SpinLockHolder h(&pageheap_lock);
02137 for (TCMalloc_ThreadCache* h = thread_heaps; h != NULL; h = h->next_) {
02138 if (h->tid_ == zero) {
02139 h->tid_ = pthread_self();
02140 }
02141 }
02142 }
02143
02144 TCMalloc_ThreadCache* TCMalloc_ThreadCache::CreateCacheIfNecessary() {
02145
02146 TCMalloc_ThreadCache* heap = NULL;
02147 {
02148 SpinLockHolder h(&pageheap_lock);
02149
02150
02151 pthread_t me;
02152 if (!tsd_inited) {
02153 memset(&me, 0, sizeof(me));
02154 } else {
02155 me = pthread_self();
02156 }
02157
02158
02159
02160
02161 for (TCMalloc_ThreadCache* h = thread_heaps; h != NULL; h = h->next_) {
02162 if (h->tid_ == me) {
02163 heap = h;
02164 break;
02165 }
02166 }
02167
02168 if (heap == NULL) heap = NewHeap(me);
02169 }
02170
02171
02172
02173
02174
02175 if (!heap->in_setspecific_ && tsd_inited) {
02176 heap->in_setspecific_ = true;
02177 perftools_pthread_setspecific(heap_key, heap);
02178 #ifdef HAVE_TLS
02179
02180 threadlocal_heap = heap;
02181 #endif
02182 heap->in_setspecific_ = false;
02183 }
02184 return heap;
02185 }
02186
02187 void TCMalloc_ThreadCache::BecomeIdle() {
02188 if (!tsd_inited) return;
02189 TCMalloc_ThreadCache* heap = GetThreadHeap();
02190 if (heap == NULL) return;
02191 if (heap->in_setspecific_) return;
02192
02193 heap->in_setspecific_ = true;
02194 perftools_pthread_setspecific(heap_key, NULL);
02195 #ifdef HAVE_TLS
02196
02197 threadlocal_heap = NULL;
02198 #endif
02199 heap->in_setspecific_ = false;
02200 if (GetThreadHeap() == heap) {
02201
02202
02203 return;
02204 }
02205
02206
02207 DeleteCache(heap);
02208 }
02209
02210 void TCMalloc_ThreadCache::DestroyThreadCache(void* ptr) {
02211
02212
02213
02214 if (ptr == NULL) return;
02215 #ifdef HAVE_TLS
02216
02217 threadlocal_heap = NULL;
02218 #endif
02219 DeleteCache(reinterpret_cast<TCMalloc_ThreadCache*>(ptr));
02220 }
02221
02222 void TCMalloc_ThreadCache::DeleteCache(TCMalloc_ThreadCache* heap) {
02223
02224 heap->Cleanup();
02225
02226
02227 SpinLockHolder h(&pageheap_lock);
02228 if (heap->next_ != NULL) heap->next_->prev_ = heap->prev_;
02229 if (heap->prev_ != NULL) heap->prev_->next_ = heap->next_;
02230 if (thread_heaps == heap) thread_heaps = heap->next_;
02231 thread_heap_count--;
02232 RecomputeThreadCacheSize();
02233
02234 threadheap_allocator.Delete(heap);
02235 }
02236
02237 void TCMalloc_ThreadCache::RecomputeThreadCacheSize() {
02238
02239 int n = thread_heap_count > 0 ? thread_heap_count : 1;
02240 size_t space = overall_thread_cache_size / n;
02241
02242
02243 if (space < kMinThreadCacheSize) space = kMinThreadCacheSize;
02244 if (space > kMaxThreadCacheSize) space = kMaxThreadCacheSize;
02245
02246 per_thread_cache_size = space;
02247
02248 }
02249
02250 void TCMalloc_ThreadCache::Print() const {
02251 for (int cl = 0; cl < kNumClasses; ++cl) {
02252 MESSAGE(" %5" PRIuS " : %4d len; %4d lo\n",
02253 ByteSizeForClass(cl),
02254 list_[cl].length(),
02255 list_[cl].lowwatermark());
02256 }
02257 }
02258
02259
02260 struct TCMallocStats {
02261 uint64_t system_bytes;
02262 uint64_t thread_bytes;
02263 uint64_t central_bytes;
02264 uint64_t transfer_bytes;
02265 uint64_t pageheap_bytes;
02266 uint64_t metadata_bytes;
02267 };
02268
02269
02270 static void ExtractStats(TCMallocStats* r, uint64_t* class_count) {
02271 r->central_bytes = 0;
02272 r->transfer_bytes = 0;
02273 for (int cl = 0; cl < kNumClasses; ++cl) {
02274 const int length = central_cache[cl].length();
02275 const int tc_length = central_cache[cl].tc_length();
02276 r->central_bytes += static_cast<uint64_t>(ByteSizeForClass(cl)) * length;
02277 r->transfer_bytes +=
02278 static_cast<uint64_t>(ByteSizeForClass(cl)) * tc_length;
02279 if (class_count) class_count[cl] = length + tc_length;
02280 }
02281
02282
02283 r->thread_bytes = 0;
02284 {
02285 SpinLockHolder h(&pageheap_lock);
02286 for (TCMalloc_ThreadCache* h = thread_heaps; h != NULL; h = h->next_) {
02287 r->thread_bytes += h->Size();
02288 if (class_count) {
02289 for (int cl = 0; cl < kNumClasses; ++cl) {
02290 class_count[cl] += h->freelist_length(cl);
02291 }
02292 }
02293 }
02294 }
02295
02296 {
02297 SpinLockHolder h(&pageheap_lock);
02298 r->system_bytes = pageheap->SystemBytes();
02299 r->metadata_bytes = metadata_system_bytes;
02300 r->pageheap_bytes = pageheap->FreeBytes();
02301 }
02302 }
02303
02304
02305 static void DumpStats(TCMalloc_Printer* out, int level) {
02306 TCMallocStats stats;
02307 uint64_t class_count[kNumClasses];
02308 ExtractStats(&stats, (level >= 2 ? class_count : NULL));
02309
02310 if (level >= 2) {
02311 out->printf("------------------------------------------------\n");
02312 uint64_t cumulative = 0;
02313 for (int cl = 0; cl < kNumClasses; ++cl) {
02314 if (class_count[cl] > 0) {
02315 uint64_t class_bytes = class_count[cl] * ByteSizeForClass(cl);
02316 cumulative += class_bytes;
02317 out->printf("class %3d [ %8" PRIuS " bytes ] : "
02318 "%8" PRIu64 " objs; %5.1f MB; %5.1f cum MB\n",
02319 cl, ByteSizeForClass(cl),
02320 class_count[cl],
02321 class_bytes / 1048576.0,
02322 cumulative / 1048576.0);
02323 }
02324 }
02325
02326 SpinLockHolder h(&pageheap_lock);
02327 pageheap->Dump(out);
02328 }
02329
02330 const uint64_t bytes_in_use = stats.system_bytes
02331 - stats.pageheap_bytes
02332 - stats.central_bytes
02333 - stats.transfer_bytes
02334 - stats.thread_bytes;
02335
02336 out->printf("------------------------------------------------\n"
02337 "MALLOC: %12" PRIu64 " Heap size\n"
02338 "MALLOC: %12" PRIu64 " Bytes in use by application\n"
02339 "MALLOC: %12" PRIu64 " Bytes free in page heap\n"
02340 "MALLOC: %12" PRIu64 " Bytes free in central cache\n"
02341 "MALLOC: %12" PRIu64 " Bytes free in transfer cache\n"
02342 "MALLOC: %12" PRIu64 " Bytes free in thread caches\n"
02343 "MALLOC: %12" PRIu64 " Spans in use\n"
02344 "MALLOC: %12" PRIu64 " Thread heaps in use\n"
02345 "MALLOC: %12" PRIu64 " Metadata allocated\n"
02346 "------------------------------------------------\n",
02347 stats.system_bytes,
02348 bytes_in_use,
02349 stats.pageheap_bytes,
02350 stats.central_bytes,
02351 stats.transfer_bytes,
02352 stats.thread_bytes,
02353 uint64_t(span_allocator.inuse()),
02354 uint64_t(threadheap_allocator.inuse()),
02355 stats.metadata_bytes);
02356 }
02357
02358 static void PrintStats(int level) {
02359 const int kBufferSize = 16 << 10;
02360 char* buffer = new char[kBufferSize];
02361 TCMalloc_Printer printer(buffer, kBufferSize);
02362 DumpStats(&printer, level);
02363 write(STDERR_FILENO, buffer, strlen(buffer));
02364 delete[] buffer;
02365 }
02366
02367 static void** DumpStackTraces() {
02368
02369 int needed_slots = 0;
02370 {
02371 SpinLockHolder h(&pageheap_lock);
02372 for (Span* s = sampled_objects.next; s != &sampled_objects; s = s->next) {
02373 StackTrace* stack = reinterpret_cast<StackTrace*>(s->objects);
02374 needed_slots += 3 + stack->depth;
02375 }
02376 needed_slots += 100;
02377 needed_slots += needed_slots/8;
02378 }
02379
02380 void** result = new void*[needed_slots];
02381 if (result == NULL) {
02382 MESSAGE("tcmalloc: could not allocate %d slots for stack traces\n",
02383 needed_slots);
02384 return NULL;
02385 }
02386
02387 SpinLockHolder h(&pageheap_lock);
02388 int used_slots = 0;
02389 for (Span* s = sampled_objects.next; s != &sampled_objects; s = s->next) {
02390 ASSERT(used_slots < needed_slots);
02391 StackTrace* stack = reinterpret_cast<StackTrace*>(s->objects);
02392 if (used_slots + 3 + stack->depth >= needed_slots) {
02393
02394 break;
02395 }
02396
02397 result[used_slots+0] = reinterpret_cast<void*>(static_cast<uintptr_t>(1));
02398 result[used_slots+1] = reinterpret_cast<void*>(stack->size);
02399 result[used_slots+2] = reinterpret_cast<void*>(stack->depth);
02400 for (int d = 0; d < stack->depth; d++) {
02401 result[used_slots+3+d] = stack->stack[d];
02402 }
02403 used_slots += 3 + stack->depth;
02404 }
02405 result[used_slots] = reinterpret_cast<void*>(static_cast<uintptr_t>(0));
02406 return result;
02407 }
02408
02409 static void** DumpHeapGrowthStackTraces() {
02410
02411 int needed_slots = 0;
02412 {
02413 SpinLockHolder h(&pageheap_lock);
02414 for (StackTrace* t = growth_stacks;
02415 t != NULL;
02416 t = reinterpret_cast<StackTrace*>(t->stack[kMaxStackDepth-1])) {
02417 needed_slots += 3 + t->depth;
02418 }
02419 needed_slots += 100;
02420 needed_slots += needed_slots/8;
02421 }
02422
02423 void** result = new void*[needed_slots];
02424 if (result == NULL) {
02425 MESSAGE("tcmalloc: could not allocate %d slots for stack traces\n",
02426 needed_slots);
02427 return NULL;
02428 }
02429
02430 SpinLockHolder h(&pageheap_lock);
02431 int used_slots = 0;
02432 for (StackTrace* t = growth_stacks;
02433 t != NULL;
02434 t = reinterpret_cast<StackTrace*>(t->stack[kMaxStackDepth-1])) {
02435 ASSERT(used_slots < needed_slots);
02436 if (used_slots + 3 + t->depth >= needed_slots) {
02437
02438 break;
02439 }
02440
02441 result[used_slots+0] = reinterpret_cast<void*>(static_cast<uintptr_t>(1));
02442 result[used_slots+1] = reinterpret_cast<void*>(t->size);
02443 result[used_slots+2] = reinterpret_cast<void*>(t->depth);
02444 for (int d = 0; d < t->depth; d++) {
02445 result[used_slots+3+d] = t->stack[d];
02446 }
02447 used_slots += 3 + t->depth;
02448 }
02449 result[used_slots] = reinterpret_cast<void*>(static_cast<uintptr_t>(0));
02450 return result;
02451 }
02452
02453
02454 class TCMallocImplementation : public MallocExtension {
02455 public:
02456 virtual void GetStats(char* buffer, int buffer_length) {
02457 ASSERT(buffer_length > 0);
02458 TCMalloc_Printer printer(buffer, buffer_length);
02459
02460
02461 if (buffer_length < 10000) {
02462 DumpStats(&printer, 1);
02463 } else {
02464 DumpStats(&printer, 2);
02465 }
02466 }
02467
02468 virtual void** ReadStackTraces() {
02469 return DumpStackTraces();
02470 }
02471
02472 virtual void** ReadHeapGrowthStackTraces() {
02473 return DumpHeapGrowthStackTraces();
02474 }
02475
02476 virtual bool GetNumericProperty(const char* name, size_t* value) {
02477 ASSERT(name != NULL);
02478
02479 if (strcmp(name, "generic.current_allocated_bytes") == 0) {
02480 TCMallocStats stats;
02481 ExtractStats(&stats, NULL);
02482 *value = stats.system_bytes
02483 - stats.thread_bytes
02484 - stats.central_bytes
02485 - stats.pageheap_bytes;
02486 return true;
02487 }
02488
02489 if (strcmp(name, "generic.heap_size") == 0) {
02490 TCMallocStats stats;
02491 ExtractStats(&stats, NULL);
02492 *value = stats.system_bytes;
02493 return true;
02494 }
02495
02496 if (strcmp(name, "tcmalloc.slack_bytes") == 0) {
02497
02498
02499 SpinLockHolder l(&pageheap_lock);
02500 *value = pageheap->FreeBytes();
02501 return true;
02502 }
02503
02504 if (strcmp(name, "tcmalloc.max_total_thread_cache_bytes") == 0) {
02505 SpinLockHolder l(&pageheap_lock);
02506 *value = overall_thread_cache_size;
02507 return true;
02508 }
02509
02510 if (strcmp(name, "tcmalloc.current_total_thread_cache_bytes") == 0) {
02511 TCMallocStats stats;
02512 ExtractStats(&stats, NULL);
02513 *value = stats.thread_bytes;
02514 return true;
02515 }
02516
02517 return false;
02518 }
02519
02520 virtual bool SetNumericProperty(const char* name, size_t value) {
02521 ASSERT(name != NULL);
02522
02523 if (strcmp(name, "tcmalloc.max_total_thread_cache_bytes") == 0) {
02524
02525 if (value < kMinThreadCacheSize) value = kMinThreadCacheSize;
02526 if (value > (1<<30)) value = (1<<30);
02527
02528 SpinLockHolder l(&pageheap_lock);
02529 overall_thread_cache_size = static_cast<size_t>(value);
02530 TCMalloc_ThreadCache::RecomputeThreadCacheSize();
02531 return true;
02532 }
02533
02534 return false;
02535 }
02536
02537 virtual void MarkThreadIdle() {
02538 TCMalloc_ThreadCache::BecomeIdle();
02539 }
02540
02541 virtual void ReleaseFreeMemory() {
02542 SpinLockHolder h(&pageheap_lock);
02543 pageheap->ReleaseFreePages();
02544 }
02545 };
02546
02547
02548
02549
02550
02551
02552
02553
02554
02555
02556
02557
02558
02559 class TCMallocGuard {
02560 public:
02561
02562 TCMallocGuard() {
02563 #ifdef HAVE_TLS // this is true if the cc/ld/libc combo support TLS
02564
02565 CheckIfKernelSupportsTLS();
02566 #endif
02567 #ifdef WIN32 // patch the windows VirtualAlloc, etc.
02568 PatchWindowsFunctions();
02569 #endif
02570 free(malloc(1));
02571 TCMalloc_ThreadCache::InitTSD();
02572 free(malloc(1));
02573 MallocExtension::Register(new TCMallocImplementation);
02574 }
02575
02576 ~TCMallocGuard() {
02577 const char* env = getenv("MALLOCSTATS");
02578 if (env != NULL) {
02579 int level = atoi(env);
02580 if (level < 1) level = 1;
02581 PrintStats(level);
02582 }
02583 #ifdef WIN32
02584 UnpatchWindowsFunctions();
02585 #endif
02586 }
02587 };
02588 static TCMallocGuard module_enter_exit_hook;
02589
02590
02591
02592
02593
02594 static Span* DoSampledAllocation(size_t size) {
02595
02596
02597 StackTrace tmp;
02598 tmp.depth = GetStackTrace(tmp.stack, kMaxStackDepth, 1);
02599 tmp.size = size;
02600
02601 SpinLockHolder h(&pageheap_lock);
02602
02603 Span *span = pageheap->New(pages(size == 0 ? 1 : size));
02604 if (span == NULL) {
02605 return NULL;
02606 }
02607
02608
02609 StackTrace *stack = stacktrace_allocator.New();
02610 if (stack == NULL) {
02611
02612 return span;
02613 }
02614
02615 *stack = tmp;
02616 span->sample = 1;
02617 span->objects = stack;
02618 DLL_Prepend(&sampled_objects, span);
02619
02620 return span;
02621 }
02622
02623 static inline bool CheckCachedSizeClass(void *ptr) {
02624 PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift;
02625 size_t cached_value = pageheap->GetSizeClassIfCached(p);
02626 return cached_value == 0 ||
02627 cached_value == pageheap->GetDescriptor(p)->sizeclass;
02628 }
02629
02630 static inline void* CheckedMallocResult(void *result)
02631 {
02632 ASSERT(result == 0 || CheckCachedSizeClass(result));
02633 return result;
02634 }
02635
02636 static inline void* SpanToMallocResult(Span *span) {
02637 pageheap->CacheSizeClass(span->start, 0);
02638 return
02639 CheckedMallocResult(reinterpret_cast<void*>(span->start << kPageShift));
02640 }
02641
02642 static inline void* do_malloc(size_t size) {
02643 void* ret = NULL;
02644
02645
02646 TCMalloc_ThreadCache* heap = TCMalloc_ThreadCache::GetCache();
02647 if ((FLAGS_tcmalloc_sample_parameter > 0) && heap->SampleAllocation(size)) {
02648 Span* span = DoSampledAllocation(size);
02649 if (span != NULL) {
02650 ret = SpanToMallocResult(span);
02651 }
02652 } else if (size > kMaxSize) {
02653
02654 SpinLockHolder h(&pageheap_lock);
02655 Span* span = pageheap->New(pages(size));
02656 if (span != NULL) {
02657 ret = SpanToMallocResult(span);
02658 }
02659 } else {
02660
02661
02662 ret = CheckedMallocResult(heap->Allocate(size));
02663 }
02664 if (ret == NULL) errno = ENOMEM;
02665 return ret;
02666 }
02667
02668 static inline void do_free(void* ptr) {
02669 if (ptr == NULL) return;
02670 ASSERT(pageheap != NULL);
02671 const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift;
02672 Span* span = NULL;
02673 size_t cl = pageheap->GetSizeClassIfCached(p);
02674
02675 if (cl == 0) {
02676 span = pageheap->GetDescriptor(p);
02677 cl = span->sizeclass;
02678 pageheap->CacheSizeClass(p, cl);
02679 }
02680 if (cl != 0) {
02681 ASSERT(!pageheap->GetDescriptor(p)->sample);
02682 TCMalloc_ThreadCache* heap = TCMalloc_ThreadCache::GetCacheIfPresent();
02683 if (heap != NULL) {
02684 heap->Deallocate(ptr, cl);
02685 } else {
02686
02687 SLL_SetNext(ptr, NULL);
02688 central_cache[cl].InsertRange(ptr, ptr, 1);
02689 }
02690 } else {
02691 SpinLockHolder h(&pageheap_lock);
02692 ASSERT(reinterpret_cast<uintptr_t>(ptr) % kPageSize == 0);
02693 ASSERT(span != NULL && span->start == p);
02694 if (span->sample) {
02695 DLL_Remove(span);
02696 stacktrace_allocator.Delete(reinterpret_cast<StackTrace*>(span->objects));
02697 span->objects = NULL;
02698 }
02699 pageheap->Delete(span);
02700 }
02701 }
02702
02703
02704
02705
02706
02707
02708
02709
02710 static void* do_memalign(size_t align, size_t size) {
02711 ASSERT((align & (align - 1)) == 0);
02712 ASSERT(align > 0);
02713 if (size + align < size) return NULL;
02714
02715 if (pageheap == NULL) TCMalloc_ThreadCache::InitModule();
02716
02717
02718 if (size == 0) size = 1;
02719
02720 if (size <= kMaxSize && align < kPageSize) {
02721
02722
02723
02724
02725
02726
02727 int cl = SizeClass(size);
02728 while (cl < kNumClasses && ((class_to_size[cl] & (align - 1)) != 0)) {
02729 cl++;
02730 }
02731 if (cl < kNumClasses) {
02732 TCMalloc_ThreadCache* heap = TCMalloc_ThreadCache::GetCache();
02733 return CheckedMallocResult(heap->Allocate(class_to_size[cl]));
02734 }
02735 }
02736
02737
02738 SpinLockHolder h(&pageheap_lock);
02739
02740 if (align <= kPageSize) {
02741
02742
02743
02744 Span* span = pageheap->New(pages(size));
02745 return span == NULL ? NULL : SpanToMallocResult(span);
02746 }
02747
02748
02749 const Length alloc = pages(size + align);
02750 Span* span = pageheap->New(alloc);
02751 if (span == NULL) return NULL;
02752
02753
02754 Length skip = 0;
02755 while ((((span->start+skip) << kPageShift) & (align - 1)) != 0) {
02756 skip++;
02757 }
02758 ASSERT(skip < alloc);
02759 if (skip > 0) {
02760 Span* rest = pageheap->Split(span, skip);
02761 pageheap->Delete(span);
02762 span = rest;
02763 }
02764
02765
02766 const Length needed = pages(size);
02767 ASSERT(span->length >= needed);
02768 if (span->length > needed) {
02769 Span* trailer = pageheap->Split(span, needed);
02770 pageheap->Delete(trailer);
02771 }
02772 return SpanToMallocResult(span);
02773 }
02774
02775
02776
02777 static inline void do_malloc_stats() {
02778 PrintStats(1);
02779 }
02780
02781 static inline int do_mallopt(int cmd, int value) {
02782 return 1;
02783 }
02784
02785 #ifdef HAVE_STRUCT_MALLINFO // mallinfo isn't defined on freebsd, for instance
02786 static inline struct mallinfo do_mallinfo() {
02787 TCMallocStats stats;
02788 ExtractStats(&stats, NULL);
02789
02790
02791 struct mallinfo info;
02792 memset(&info, 0, sizeof(info));
02793
02794
02795
02796 info.arena = static_cast<int>(stats.system_bytes);
02797 info.fsmblks = static_cast<int>(stats.thread_bytes
02798 + stats.central_bytes
02799 + stats.transfer_bytes);
02800 info.fordblks = static_cast<int>(stats.pageheap_bytes);
02801 info.uordblks = static_cast<int>(stats.system_bytes
02802 - stats.thread_bytes
02803 - stats.central_bytes
02804 - stats.transfer_bytes
02805 - stats.pageheap_bytes);
02806
02807 return info;
02808 }
02809 #endif
02810
02811
02812
02813
02814
02815
02816
02817
02818
02819 #ifdef WIN32
02820 # define malloc Perftools_malloc
02821 # define calloc Perftools_calloc
02822 # define realloc Perftools_realloc
02823 # define free Perftools_free
02824 #endif
02825
02826
02827
02828
02829
02830
02831
02832
02833
02834
02835
02836 extern "C" {
02837 void* malloc(size_t size)
02838 __THROW ATTRIBUTE_SECTION(google_malloc);
02839 void free(void* ptr)
02840 __THROW ATTRIBUTE_SECTION(google_malloc);
02841 void* realloc(void* ptr, size_t size)
02842 __THROW ATTRIBUTE_SECTION(google_malloc);
02843 void* calloc(size_t nmemb, size_t size)
02844 __THROW ATTRIBUTE_SECTION(google_malloc);
02845 void cfree(void* ptr)
02846 __THROW ATTRIBUTE_SECTION(google_malloc);
02847
02848 void* memalign(size_t __alignment, size_t __size)
02849 __THROW ATTRIBUTE_SECTION(google_malloc);
02850 int posix_memalign(void** ptr, size_t align, size_t size)
02851 __THROW ATTRIBUTE_SECTION(google_malloc);
02852 void* valloc(size_t __size)
02853 __THROW ATTRIBUTE_SECTION(google_malloc);
02854 void* pvalloc(size_t __size)
02855 __THROW ATTRIBUTE_SECTION(google_malloc);
02856 }
02857
02858 static void *MemalignOverride(size_t align, size_t size, const void *caller)
02859 __THROW ATTRIBUTE_SECTION(google_malloc);
02860
02861 void* operator new(size_t size)
02862 ATTRIBUTE_SECTION(google_malloc);
02863 void operator delete(void* p)
02864 __THROW ATTRIBUTE_SECTION(google_malloc);
02865 void* operator new[](size_t size)
02866 ATTRIBUTE_SECTION(google_malloc);
02867 void operator delete[](void* p)
02868 __THROW ATTRIBUTE_SECTION(google_malloc);
02869
02870
02871 void* operator new(size_t size, const std::nothrow_t&)
02872 __THROW ATTRIBUTE_SECTION(google_malloc);
02873 void operator delete(void* p, const std::nothrow_t&)
02874 __THROW ATTRIBUTE_SECTION(google_malloc);
02875 void* operator new[](size_t size, const std::nothrow_t&)
02876 __THROW ATTRIBUTE_SECTION(google_malloc);
02877 void operator delete[](void* p, const std::nothrow_t&)
02878 __THROW ATTRIBUTE_SECTION(google_malloc);
02879
02880 extern "C" void* malloc(size_t size) __THROW {
02881 void* result = do_malloc(size);
02882 MallocHook::InvokeNewHook(result, size);
02883 return result;
02884 }
02885
02886 extern "C" void free(void* ptr) __THROW {
02887 MallocHook::InvokeDeleteHook(ptr);
02888 do_free(ptr);
02889 }
02890
02891 extern "C" void* calloc(size_t n, size_t elem_size) __THROW {
02892
02893 const size_t size = n * elem_size;
02894 if (elem_size != 0 && size / elem_size != n) return NULL;
02895
02896 void* result = do_malloc(size);
02897 if (result != NULL) {
02898 memset(result, 0, size);
02899 }
02900 MallocHook::InvokeNewHook(result, size);
02901 return result;
02902 }
02903
02904 extern "C" void cfree(void* ptr) __THROW {
02905 MallocHook::InvokeDeleteHook(ptr);
02906 do_free(ptr);
02907 }
02908
02909 extern "C" void* realloc(void* old_ptr, size_t new_size) __THROW {
02910 if (old_ptr == NULL) {
02911 void* result = do_malloc(new_size);
02912 MallocHook::InvokeNewHook(result, new_size);
02913 return result;
02914 }
02915 if (new_size == 0) {
02916 MallocHook::InvokeDeleteHook(old_ptr);
02917 do_free(old_ptr);
02918 return NULL;
02919 }
02920
02921
02922 const PageID p = reinterpret_cast<uintptr_t>(old_ptr) >> kPageShift;
02923 size_t cl = pageheap->GetSizeClassIfCached(p);
02924 Span *span = NULL;
02925 size_t old_size;
02926 if (cl == 0) {
02927 span = pageheap->GetDescriptor(p);
02928 cl = span->sizeclass;
02929 pageheap->CacheSizeClass(p, cl);
02930 }
02931 if (cl != 0) {
02932 old_size = ByteSizeForClass(cl);
02933 } else {
02934 ASSERT(span != NULL);
02935 old_size = span->length << kPageShift;
02936 }
02937
02938
02939
02940 if ((new_size > old_size) || (AllocationSize(new_size) < old_size)) {
02941
02942 void* new_ptr = do_malloc(new_size);
02943 if (new_ptr == NULL) {
02944 return NULL;
02945 }
02946 MallocHook::InvokeNewHook(new_ptr, new_size);
02947 memcpy(new_ptr, old_ptr, ((old_size < new_size) ? old_size : new_size));
02948 MallocHook::InvokeDeleteHook(old_ptr);
02949
02950
02951
02952 do_free(old_ptr);
02953 return new_ptr;
02954 } else {
02955 return old_ptr;
02956 }
02957 }
02958
02959 static SpinLock set_new_handler_lock(SpinLock::LINKER_INITIALIZED);
02960
02961 static inline void* cpp_alloc(size_t size, bool nothrow) {
02962 for (;;) {
02963 void* p = do_malloc(size);
02964 #ifdef PREANSINEW
02965 return p;
02966 #else
02967 if (p == NULL) {
02968
02969
02970
02971
02972 std::new_handler nh;
02973 {
02974 SpinLockHolder h(&set_new_handler_lock);
02975 nh = std::set_new_handler(0);
02976 (void) std::set_new_handler(nh);
02977 }
02978
02979 if (!nh) {
02980 if (nothrow) return 0;
02981 throw std::bad_alloc();
02982 }
02983
02984
02985
02986 try {
02987 (*nh)();
02988 } catch (const std::bad_alloc&) {
02989 if (!nothrow) throw;
02990 return p;
02991 }
02992 } else {
02993 return p;
02994 }
02995 #endif
02996 }
02997 }
02998
02999 void* operator new(size_t size) {
03000 void* p = cpp_alloc(size, false);
03001
03002
03003
03004
03005
03006 MallocHook::InvokeNewHook(p, size);
03007 return p;
03008 }
03009
03010 void* operator new(size_t size, const std::nothrow_t&) __THROW {
03011 void* p = cpp_alloc(size, true);
03012 MallocHook::InvokeNewHook(p, size);
03013 return p;
03014 }
03015
03016 void operator delete(void* p) __THROW {
03017 MallocHook::InvokeDeleteHook(p);
03018 do_free(p);
03019 }
03020
03021 void operator delete(void* p, const std::nothrow_t&) __THROW {
03022 MallocHook::InvokeDeleteHook(p);
03023 do_free(p);
03024 }
03025
03026 void* operator new[](size_t size) {
03027 void* p = cpp_alloc(size, false);
03028
03029
03030
03031
03032
03033 MallocHook::InvokeNewHook(p, size);
03034 return p;
03035 }
03036
03037 void* operator new[](size_t size, const std::nothrow_t&) __THROW {
03038 void* p = cpp_alloc(size, true);
03039 MallocHook::InvokeNewHook(p, size);
03040 return p;
03041 }
03042
03043 void operator delete[](void* p) __THROW {
03044 MallocHook::InvokeDeleteHook(p);
03045 do_free(p);
03046 }
03047
03048 void operator delete[](void* p, const std::nothrow_t&) __THROW {
03049 MallocHook::InvokeDeleteHook(p);
03050 do_free(p);
03051 }
03052
03053 extern "C" void* memalign(size_t align, size_t size) __THROW {
03054 void* result = do_memalign(align, size);
03055 MallocHook::InvokeNewHook(result, size);
03056 return result;
03057 }
03058
03059 extern "C" int posix_memalign(void** result_ptr, size_t align, size_t size)
03060 __THROW {
03061 if (((align % sizeof(void*)) != 0) ||
03062 ((align & (align - 1)) != 0) ||
03063 (align == 0)) {
03064 return EINVAL;
03065 }
03066
03067 void* result = do_memalign(align, size);
03068 MallocHook::InvokeNewHook(result, size);
03069 if (result == NULL) {
03070 return ENOMEM;
03071 } else {
03072 *result_ptr = result;
03073 return 0;
03074 }
03075 }
03076
03077 static size_t pagesize = 0;
03078
03079 extern "C" void* valloc(size_t size) __THROW {
03080
03081 if (pagesize == 0) pagesize = getpagesize();
03082 void* result = do_memalign(pagesize, size);
03083 MallocHook::InvokeNewHook(result, size);
03084 return result;
03085 }
03086
03087 extern "C" void* pvalloc(size_t size) __THROW {
03088
03089 if (pagesize == 0) pagesize = getpagesize();
03090 size = (size + pagesize - 1) & ~(pagesize - 1);
03091 void* result = do_memalign(pagesize, size);
03092 MallocHook::InvokeNewHook(result, size);
03093 return result;
03094 }
03095
03096 extern "C" void malloc_stats(void) {
03097 do_malloc_stats();
03098 }
03099
03100 extern "C" int mallopt(int cmd, int value) {
03101 return do_mallopt(cmd, value);
03102 }
03103
03104 #ifdef HAVE_STRUCT_MALLINFO
03105 extern "C" struct mallinfo mallinfo(void) {
03106 return do_mallinfo();
03107 }
03108 #endif
03109
03110
03111
03112
03113
03114
03115
03116
03117
03118 #if defined(__GLIBC__)
03119 extern "C" {
03120 # if defined(__GNUC__) && !defined(__MACH__) && defined(HAVE___ATTRIBUTE__)
03121
03122
03123 # define ALIAS(x) __attribute__ ((weak, alias (x)))
03124 void* __libc_malloc(size_t size) ALIAS("malloc");
03125 void __libc_free(void* ptr) ALIAS("free");
03126 void* __libc_realloc(void* ptr, size_t size) ALIAS("realloc");
03127 void* __libc_calloc(size_t n, size_t size) ALIAS("calloc");
03128 void __libc_cfree(void* ptr) ALIAS("cfree");
03129 void* __libc_memalign(size_t align, size_t s) ALIAS("memalign");
03130 void* __libc_valloc(size_t size) ALIAS("valloc");
03131 void* __libc_pvalloc(size_t size) ALIAS("pvalloc");
03132 int __posix_memalign(void** r, size_t a, size_t s) ALIAS("posix_memalign");
03133 # undef ALIAS
03134 # else
03135
03136 void* __libc_malloc(size_t size) { return malloc(size); }
03137 void __libc_free(void* ptr) { free(ptr); }
03138 void* __libc_realloc(void* ptr, size_t size) { return realloc(ptr, size); }
03139 void* __libc_calloc(size_t n, size_t size) { return calloc(n, size); }
03140 void __libc_cfree(void* ptr) { cfree(ptr); }
03141 void* __libc_memalign(size_t align, size_t s) { return memalign(align, s); }
03142 void* __libc_valloc(size_t size) { return valloc(size); }
03143 void* __libc_pvalloc(size_t size) { return pvalloc(size); }
03144 int __posix_memalign(void** r, size_t a, size_t s) {
03145 return posix_memalign(r, a, s);
03146 }
03147 # endif
03148 }
03149 #endif
03150
03151
03152
03153
03154
03155
03156
03157
03158 static void *MemalignOverride(size_t align, size_t size, const void *caller)
03159 __THROW {
03160 void* result = do_memalign(align, size);
03161 MallocHook::InvokeNewHook(result, size);
03162 return result;
03163 }
03164 void *(*__memalign_hook)(size_t, size_t, const void *) = MemalignOverride;