OLD | NEW |
1 // Copyright (c) 2008, Google Inc. | 1 // Copyright (c) 2008, Google Inc. |
2 // All rights reserved. | 2 // All rights reserved. |
3 // | 3 // |
4 // Redistribution and use in source and binary forms, with or without | 4 // Redistribution and use in source and binary forms, with or without |
5 // modification, are permitted provided that the following conditions are | 5 // modification, are permitted provided that the following conditions are |
6 // met: | 6 // met: |
7 // | 7 // |
8 // * Redistributions of source code must retain the above copyright | 8 // * Redistributions of source code must retain the above copyright |
9 // notice, this list of conditions and the following disclaimer. | 9 // notice, this list of conditions and the following disclaimer. |
10 // * Redistributions in binary form must reproduce the above | 10 // * Redistributions in binary form must reproduce the above |
(...skipping 18 matching lines...) Expand all Loading... |
29 | 29 |
30 // --- | 30 // --- |
31 // Author: Sanjay Ghemawat <opensource@google.com> | 31 // Author: Sanjay Ghemawat <opensource@google.com> |
32 // | 32 // |
33 // Common definitions for tcmalloc code. | 33 // Common definitions for tcmalloc code. |
34 | 34 |
35 #ifndef TCMALLOC_COMMON_H_ | 35 #ifndef TCMALLOC_COMMON_H_ |
36 #define TCMALLOC_COMMON_H_ | 36 #define TCMALLOC_COMMON_H_ |
37 | 37 |
38 #include "config.h" | 38 #include "config.h" |
39 #include <stddef.h> | 39 #include <stddef.h> // for size_t |
40 #ifdef HAVE_STDINT_H | 40 #ifdef HAVE_STDINT_H |
41 #include <stdint.h> | 41 #include <stdint.h> // for uintptr_t, uint64_t |
42 #endif | 42 #endif |
43 #include <stdarg.h> | 43 #include "internal_logging.h" // for ASSERT, etc |
44 #include "base/commandlineflags.h" | |
45 #include "internal_logging.h" | |
46 | 44 |
47 // Type that can hold a page number | 45 // Type that can hold a page number |
48 typedef uintptr_t PageID; | 46 typedef uintptr_t PageID; |
49 | 47 |
50 // Type that can hold the length of a run of pages | 48 // Type that can hold the length of a run of pages |
51 typedef uintptr_t Length; | 49 typedef uintptr_t Length; |
52 | 50 |
53 //------------------------------------------------------------------- | 51 //------------------------------------------------------------------- |
54 // Configuration | 52 // Configuration |
55 //------------------------------------------------------------------- | 53 //------------------------------------------------------------------- |
56 | 54 |
57 // Not all possible combinations of the following parameters make | 55 // Using large pages speeds up the execution at a cost of larger memory use. |
58 // sense. In particular, if kMaxSize increases, you may have to | 56 // Deallocation may speed up by a factor as the page map gets 8x smaller, so |
59 // increase kNumClasses as well. | 57 // lookups in the page map result in fewer L2 cache misses, which translates to |
| 58 // speedup for application/platform combinations with high L2 cache pressure. |
| 59 // As the number of size classes increases with large pages, we increase |
| 60 // the thread cache allowance to avoid passing more free ranges to and from |
| 61 // central lists. Also, larger pages are less likely to get freed. |
| 62 // These two factors cause a bounded increase in memory use. |
| 63 |
| 64 #if defined(TCMALLOC_LARGE_PAGES) |
| 65 static const size_t kPageShift = 15; |
| 66 static const size_t kNumClasses = 95; |
| 67 static const size_t kMaxThreadCacheSize = 4 << 20; |
| 68 #else |
60 static const size_t kPageShift = 12; | 69 static const size_t kPageShift = 12; |
| 70 static const size_t kNumClasses = 61; |
| 71 static const size_t kMaxThreadCacheSize = 2 << 20; |
| 72 #endif |
| 73 |
61 static const size_t kPageSize = 1 << kPageShift; | 74 static const size_t kPageSize = 1 << kPageShift; |
62 static const size_t kMaxSize = 8u * kPageSize; | 75 static const size_t kMaxSize = 8u * kPageSize; |
63 static const size_t kAlignment = 8; | 76 static const size_t kAlignment = 8; |
64 static const size_t kNumClasses = 61; | 77 // For all span-lengths < kMaxPages we keep an exact-size list. |
| 78 static const size_t kMaxPages = 1 << (20 - kPageShift); |
| 79 |
| 80 // Default bound on the total amount of thread caches. |
| 81 #ifdef TCMALLOC_SMALL_BUT_SLOW |
| 82 // Make the overall thread cache no bigger than that of a single thread |
| 83 // for the small memory footprint case. |
| 84 static const size_t kDefaultOverallThreadCacheSize = kMaxThreadCacheSize; |
| 85 #else |
| 86 static const size_t kDefaultOverallThreadCacheSize = 8u * kMaxThreadCacheSize; |
| 87 #endif |
| 88 |
| 89 // Lower bound on the per-thread cache sizes |
| 90 static const size_t kMinThreadCacheSize = kMaxSize * 2; |
| 91 |
| 92 // The number of bytes one ThreadCache will steal from another when |
| 93 // the first ThreadCache is forced to Scavenge(), delaying the |
| 94 // next call to Scavenge for this thread. |
| 95 static const size_t kStealAmount = 1 << 16; |
| 96 |
| 97 // The number of times that a deallocation can cause a freelist to |
| 98 // go over its max_length() before shrinking max_length(). |
| 99 static const int kMaxOverages = 3; |
65 | 100 |
66 // Maximum length we allow a per-thread free-list to have before we | 101 // Maximum length we allow a per-thread free-list to have before we |
67 // move objects from it into the corresponding central free-list. We | 102 // move objects from it into the corresponding central free-list. We |
68 // want this big to avoid locking the central free-list too often. It | 103 // want this big to avoid locking the central free-list too often. It |
69 // should not hurt to make this list somewhat big because the | 104 // should not hurt to make this list somewhat big because the |
70 // scavenging code will shrink it down when its contents are not in use. | 105 // scavenging code will shrink it down when its contents are not in use. |
71 static const int kMaxDynamicFreeListLength = 8192; | 106 static const int kMaxDynamicFreeListLength = 8192; |
72 | 107 |
73 static const Length kMaxValidPages = (~static_cast<Length>(0)) >> kPageShift; | 108 static const Length kMaxValidPages = (~static_cast<Length>(0)) >> kPageShift; |
74 | 109 |
| 110 #if defined __x86_64__ |
| 111 // All current and planned x86_64 processors only look at the lower 48 bits |
| 112 // in virtual to physical address translation. The top 16 are thus unused. |
| 113 // TODO(rus): Under what operating systems can we increase it safely to 17? |
| 114 // This lets us use smaller page maps. On first allocation, a 36-bit page map |
| 115 // uses only 96 KB instead of the 4.5 MB used by a 52-bit page map. |
| 116 static const int kAddressBits = (sizeof(void*) < 8 ? (8 * sizeof(void*)) : 48); |
| 117 #else |
| 118 static const int kAddressBits = 8 * sizeof(void*); |
| 119 #endif |
| 120 |
75 namespace tcmalloc { | 121 namespace tcmalloc { |
76 | 122 |
77 // Convert byte size into pages. This won't overflow, but may return | 123 // Convert byte size into pages. This won't overflow, but may return |
78 // an unreasonably large value if bytes is huge enough. | 124 // an unreasonably large value if bytes is huge enough. |
79 inline Length pages(size_t bytes) { | 125 inline Length pages(size_t bytes) { |
80 return (bytes >> kPageShift) + | 126 return (bytes >> kPageShift) + |
81 ((bytes & (kPageSize - 1)) > 0 ? 1 : 0); | 127 ((bytes & (kPageSize - 1)) > 0 ? 1 : 0); |
82 } | 128 } |
83 | 129 |
| 130 // For larger allocation sizes, we use larger memory alignments to |
| 131 // reduce the number of size classes. |
| 132 int AlignmentForSize(size_t size); |
| 133 |
84 // Size-class information + mapping | 134 // Size-class information + mapping |
85 class SizeMap { | 135 class SizeMap { |
86 private: | 136 private: |
87 // Number of objects to move between a per-thread list and a central | 137 // Number of objects to move between a per-thread list and a central |
88 // list in one shot. We want this to be not too small so we can | 138 // list in one shot. We want this to be not too small so we can |
89 // amortize the lock overhead for accessing the central list. Making | 139 // amortize the lock overhead for accessing the central list. Making |
90 // it too big may temporarily cause unnecessary memory wastage in the | 140 // it too big may temporarily cause unnecessary memory wastage in the |
91 // per-thread free list until the scavenger cleans up the list. | 141 // per-thread free list until the scavenger cleans up the list. |
92 int num_objects_to_move_[kNumClasses]; | 142 int num_objects_to_move_[kNumClasses]; |
93 | 143 |
(...skipping 13 matching lines...) Expand all Loading... |
107 // Size Expression Index | 157 // Size Expression Index |
108 // ------------------------------------------------------- | 158 // ------------------------------------------------------- |
109 // 0 (0 + 7) / 8 0 | 159 // 0 (0 + 7) / 8 0 |
110 // 1 (1 + 7) / 8 1 | 160 // 1 (1 + 7) / 8 1 |
111 // ... | 161 // ... |
112 // 1024 (1024 + 7) / 8 128 | 162 // 1024 (1024 + 7) / 8 128 |
113 // 1025 (1025 + 127 + (120<<7)) / 128 129 | 163 // 1025 (1025 + 127 + (120<<7)) / 128 129 |
114 // ... | 164 // ... |
115 // 32768 (32768 + 127 + (120<<7)) / 128 376 | 165 // 32768 (32768 + 127 + (120<<7)) / 128 376 |
116 static const int kMaxSmallSize = 1024; | 166 static const int kMaxSmallSize = 1024; |
117 unsigned char class_array_[377]; | 167 static const size_t kClassArraySize = |
118 | 168 (((1 << kPageShift) * 8u + 127 + (120 << 7)) >> 7) + 1; |
| 169 unsigned char class_array_[kClassArraySize]; |
| 170 |
119 // Compute index of the class_array[] entry for a given size | 171 // Compute index of the class_array[] entry for a given size |
120 static inline int ClassIndex(int s) { | 172 static inline int ClassIndex(int s) { |
121 ASSERT(0 <= s); | 173 ASSERT(0 <= s); |
122 ASSERT(s <= kMaxSize); | 174 ASSERT(s <= kMaxSize); |
123 const bool big = (s > kMaxSmallSize); | 175 const bool big = (s > kMaxSmallSize); |
124 const int add_amount = big ? (127 + (120<<7)) : 7; | 176 const int add_amount = big ? (127 + (120<<7)) : 7; |
125 const int shift_amount = big ? 7 : 3; | 177 const int shift_amount = big ? 7 : 3; |
126 return (s + add_amount) >> shift_amount; | 178 return (s + add_amount) >> shift_amount; |
127 } | 179 } |
128 | 180 |
(...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
192 static const int kMaxStackDepth = 31; | 244 static const int kMaxStackDepth = 31; |
193 struct StackTrace { | 245 struct StackTrace { |
194 uintptr_t size; // Size of object | 246 uintptr_t size; // Size of object |
195 uintptr_t depth; // Number of PC values stored in array below | 247 uintptr_t depth; // Number of PC values stored in array below |
196 void* stack[kMaxStackDepth]; | 248 void* stack[kMaxStackDepth]; |
197 }; | 249 }; |
198 | 250 |
199 } // namespace tcmalloc | 251 } // namespace tcmalloc |
200 | 252 |
201 #endif // TCMALLOC_COMMON_H_ | 253 #endif // TCMALLOC_COMMON_H_ |
OLD | NEW |