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 13 matching lines...) Expand all Loading... |
24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | 24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | 25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 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. | 28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
29 | 29 |
30 // --- | 30 // --- |
31 // Author: Sanjay Ghemawat <opensource@google.com> | 31 // Author: Sanjay Ghemawat <opensource@google.com> |
32 | 32 |
33 #include "config.h" | 33 #include "config.h" |
| 34 #include <algorithm> |
34 #include "central_freelist.h" | 35 #include "central_freelist.h" |
35 #include "free_list.h" // for FL_Next, FL_Push, etc | 36 #include "free_list.h" // for FL_Next, FL_Push, etc |
36 #include "internal_logging.h" // for ASSERT, MESSAGE | 37 #include "internal_logging.h" // for ASSERT, MESSAGE |
37 #include "page_heap.h" // for PageHeap | 38 #include "page_heap.h" // for PageHeap |
38 #include "static_vars.h" // for Static | 39 #include "static_vars.h" // for Static |
39 | 40 |
| 41 using std::min; |
| 42 using std::max; |
| 43 |
40 namespace tcmalloc { | 44 namespace tcmalloc { |
41 | 45 |
42 void CentralFreeList::Init(size_t cl) { | 46 void CentralFreeList::Init(size_t cl) { |
43 size_class_ = cl; | 47 size_class_ = cl; |
44 tcmalloc::DLL_Init(&empty_); | 48 tcmalloc::DLL_Init(&empty_); |
45 tcmalloc::DLL_Init(&nonempty_); | 49 tcmalloc::DLL_Init(&nonempty_); |
| 50 num_spans_ = 0; |
46 counter_ = 0; | 51 counter_ = 0; |
47 | 52 |
| 53 max_cache_size_ = kMaxNumTransferEntries; |
48 #ifdef TCMALLOC_SMALL_BUT_SLOW | 54 #ifdef TCMALLOC_SMALL_BUT_SLOW |
49 // Disable the transfer cache for the small footprint case. | 55 // Disable the transfer cache for the small footprint case. |
50 cache_size_ = 0; | 56 cache_size_ = 0; |
51 #else | 57 #else |
52 cache_size_ = 16; | 58 cache_size_ = 16; |
53 #endif | 59 #endif |
| 60 if (cl > 0) { |
| 61 // Limit the maximum size of the cache based on the size class. If this |
| 62 // is not done, large size class objects will consume a lot of memory if |
| 63 // they just sit in the transfer cache. |
| 64 int32_t bytes = Static::sizemap()->ByteSizeForClass(cl); |
| 65 int32_t objs_to_move = Static::sizemap()->num_objects_to_move(cl); |
| 66 |
| 67 ASSERT(objs_to_move > 0 && bytes > 0); |
| 68 // Limit each size class cache to at most 1MB of objects or one entry, |
| 69 // whichever is greater. Total transfer cache memory used across all |
| 70 // size classes then can't be greater than approximately |
| 71 // 1MB * kMaxNumTransferEntries. |
| 72 // min and max are in parens to avoid macro-expansion on windows. |
| 73 max_cache_size_ = (min)(max_cache_size_, |
| 74 (max)(1, (1024 * 1024) / (bytes * objs_to_move))); |
| 75 cache_size_ = (min)(cache_size_, max_cache_size_); |
| 76 } |
54 used_slots_ = 0; | 77 used_slots_ = 0; |
55 ASSERT(cache_size_ <= kNumTransferEntries); | 78 ASSERT(cache_size_ <= max_cache_size_); |
56 } | 79 } |
57 | 80 |
58 void CentralFreeList::ReleaseListToSpans(void* start) { | 81 void CentralFreeList::ReleaseListToSpans(void* start) { |
59 while (start) { | 82 while (start) { |
60 void *next = FL_Next(start); | 83 void *next = FL_Next(start); |
61 ReleaseToSpans(start); | 84 ReleaseToSpans(start); |
62 start = next; | 85 start = next; |
63 } | 86 } |
64 } | 87 } |
65 | 88 |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
102 Static::sizemap()->ByteSizeForClass(span->sizeclass)); | 125 Static::sizemap()->ByteSizeForClass(span->sizeclass)); |
103 } | 126 } |
104 | 127 |
105 counter_++; | 128 counter_++; |
106 span->refcount--; | 129 span->refcount--; |
107 if (span->refcount == 0) { | 130 if (span->refcount == 0) { |
108 Event(span, '#', 0); | 131 Event(span, '#', 0); |
109 counter_ -= ((span->length<<kPageShift) / | 132 counter_ -= ((span->length<<kPageShift) / |
110 Static::sizemap()->ByteSizeForClass(span->sizeclass)); | 133 Static::sizemap()->ByteSizeForClass(span->sizeclass)); |
111 tcmalloc::DLL_Remove(span); | 134 tcmalloc::DLL_Remove(span); |
| 135 --num_spans_; |
112 | 136 |
113 // Release central list lock while operating on pageheap | 137 // Release central list lock while operating on pageheap |
114 lock_.Unlock(); | 138 lock_.Unlock(); |
115 { | 139 { |
116 SpinLockHolder h(Static::pageheap_lock()); | 140 SpinLockHolder h(Static::pageheap_lock()); |
117 Static::pageheap()->Delete(span); | 141 Static::pageheap()->Delete(span); |
118 } | 142 } |
119 lock_.Lock(); | 143 lock_.Lock(); |
120 } else { | 144 } else { |
121 FL_Push(&(span->objects), object); | 145 FL_Push(&(span->objects), object); |
(...skipping 13 matching lines...) Expand all Loading... |
135 ASSERT(t >= 0); | 159 ASSERT(t >= 0); |
136 ASSERT(t < kNumClasses); | 160 ASSERT(t < kNumClasses); |
137 if (t == locked_size_class) return false; | 161 if (t == locked_size_class) return false; |
138 return Static::central_cache()[t].ShrinkCache(locked_size_class, force); | 162 return Static::central_cache()[t].ShrinkCache(locked_size_class, force); |
139 } | 163 } |
140 | 164 |
141 bool CentralFreeList::MakeCacheSpace() { | 165 bool CentralFreeList::MakeCacheSpace() { |
142 // Is there room in the cache? | 166 // Is there room in the cache? |
143 if (used_slots_ < cache_size_) return true; | 167 if (used_slots_ < cache_size_) return true; |
144 // Check if we can expand this cache? | 168 // Check if we can expand this cache? |
145 if (cache_size_ == kNumTransferEntries) return false; | 169 if (cache_size_ == max_cache_size_) return false; |
146 // Ok, we'll try to grab an entry from some other size class. | 170 // Ok, we'll try to grab an entry from some other size class. |
147 if (EvictRandomSizeClass(size_class_, false) || | 171 if (EvictRandomSizeClass(size_class_, false) || |
148 EvictRandomSizeClass(size_class_, true)) { | 172 EvictRandomSizeClass(size_class_, true)) { |
149 // Succeeded in evicting, we're going to make our cache larger. | 173 // Succeeded in evicting, we're going to make our cache larger. |
150 // However, we may have dropped and re-acquired the lock in | 174 // However, we may have dropped and re-acquired the lock in |
151 // EvictRandomSizeClass (via ShrinkCache and the LockInverter), so the | 175 // EvictRandomSizeClass (via ShrinkCache and the LockInverter), so the |
152 // cache_size may have changed. Therefore, check and verify that it is | 176 // cache_size may have changed. Therefore, check and verify that it is |
153 // still OK to increase the cache_size. | 177 // still OK to increase the cache_size. |
154 if (cache_size_ < kNumTransferEntries) { | 178 if (cache_size_ < max_cache_size_) { |
155 cache_size_++; | 179 cache_size_++; |
156 return true; | 180 return true; |
157 } | 181 } |
158 } | 182 } |
159 return false; | 183 return false; |
160 } | 184 } |
161 | 185 |
162 | 186 |
163 namespace { | 187 namespace { |
164 class LockInverter { | 188 class LockInverter { |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
201 cache_size_--; | 225 cache_size_--; |
202 return true; | 226 return true; |
203 } | 227 } |
204 | 228 |
205 void CentralFreeList::InsertRange(void *start, void *end, int N) { | 229 void CentralFreeList::InsertRange(void *start, void *end, int N) { |
206 SpinLockHolder h(&lock_); | 230 SpinLockHolder h(&lock_); |
207 if (N == Static::sizemap()->num_objects_to_move(size_class_) && | 231 if (N == Static::sizemap()->num_objects_to_move(size_class_) && |
208 MakeCacheSpace()) { | 232 MakeCacheSpace()) { |
209 int slot = used_slots_++; | 233 int slot = used_slots_++; |
210 ASSERT(slot >=0); | 234 ASSERT(slot >=0); |
211 ASSERT(slot < kNumTransferEntries); | 235 ASSERT(slot < max_cache_size_); |
212 TCEntry *entry = &tc_slots_[slot]; | 236 TCEntry *entry = &tc_slots_[slot]; |
213 entry->head = start; | 237 entry->head = start; |
214 entry->tail = end; | 238 entry->tail = end; |
215 return; | 239 return; |
216 } | 240 } |
217 ReleaseListToSpans(start); | 241 ReleaseListToSpans(start); |
218 } | 242 } |
219 | 243 |
220 int CentralFreeList::RemoveRange(void **start, void **end, int N) { | 244 int CentralFreeList::RemoveRange(void **start, void **end, int N) { |
221 ASSERT(N > 0); | 245 ASSERT(N > 0); |
(...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
285 lock_.Unlock(); | 309 lock_.Unlock(); |
286 const size_t npages = Static::sizemap()->class_to_pages(size_class_); | 310 const size_t npages = Static::sizemap()->class_to_pages(size_class_); |
287 | 311 |
288 Span* span; | 312 Span* span; |
289 { | 313 { |
290 SpinLockHolder h(Static::pageheap_lock()); | 314 SpinLockHolder h(Static::pageheap_lock()); |
291 span = Static::pageheap()->New(npages); | 315 span = Static::pageheap()->New(npages); |
292 if (span) Static::pageheap()->RegisterSizeClass(span, size_class_); | 316 if (span) Static::pageheap()->RegisterSizeClass(span, size_class_); |
293 } | 317 } |
294 if (span == NULL) { | 318 if (span == NULL) { |
295 MESSAGE("tcmalloc: allocation failed", npages << kPageShift); | 319 Log(kLog, __FILE__, __LINE__, |
| 320 "tcmalloc: allocation failed", npages << kPageShift); |
296 lock_.Lock(); | 321 lock_.Lock(); |
297 return; | 322 return; |
298 } | 323 } |
299 ASSERT(span->length == npages); | 324 ASSERT(span->length == npages); |
300 // Cache sizeclass info eagerly. Locking is not necessary. | 325 // Cache sizeclass info eagerly. Locking is not necessary. |
301 // (Instead of being eager, we could just replace any stale info | 326 // (Instead of being eager, we could just replace any stale info |
302 // about this span, but that seems to be no better in practice.) | 327 // about this span, but that seems to be no better in practice.) |
303 for (int i = 0; i < npages; i++) { | 328 for (int i = 0; i < npages; i++) { |
304 Static::pageheap()->CacheSizeClass(span->start + i, size_class_); | 329 Static::pageheap()->CacheSizeClass(span->start + i, size_class_); |
305 } | 330 } |
(...skipping 10 matching lines...) Expand all Loading... |
316 ptr += size; | 341 ptr += size; |
317 num++; | 342 num++; |
318 } | 343 } |
319 ASSERT(ptr <= limit); | 344 ASSERT(ptr <= limit); |
320 span->objects = list; | 345 span->objects = list; |
321 span->refcount = 0; // No sub-object in use yet | 346 span->refcount = 0; // No sub-object in use yet |
322 | 347 |
323 // Add span to list of non-empty spans | 348 // Add span to list of non-empty spans |
324 lock_.Lock(); | 349 lock_.Lock(); |
325 tcmalloc::DLL_Prepend(&nonempty_, span); | 350 tcmalloc::DLL_Prepend(&nonempty_, span); |
| 351 ++num_spans_; |
326 counter_ += num; | 352 counter_ += num; |
327 } | 353 } |
328 | 354 |
329 int CentralFreeList::tc_length() { | 355 int CentralFreeList::tc_length() { |
330 SpinLockHolder h(&lock_); | 356 SpinLockHolder h(&lock_); |
331 return used_slots_ * Static::sizemap()->num_objects_to_move(size_class_); | 357 return used_slots_ * Static::sizemap()->num_objects_to_move(size_class_); |
332 } | 358 } |
333 | 359 |
| 360 size_t CentralFreeList::OverheadBytes() { |
| 361 SpinLockHolder h(&lock_); |
| 362 if (size_class_ == 0) { // 0 holds the 0-sized allocations |
| 363 return 0; |
| 364 } |
| 365 const size_t pages_per_span = Static::sizemap()->class_to_pages(size_class_); |
| 366 const size_t object_size = Static::sizemap()->class_to_size(size_class_); |
| 367 ASSERT(object_size > 0); |
| 368 const size_t overhead_per_span = (pages_per_span * kPageSize) % object_size; |
| 369 return num_spans_ * overhead_per_span; |
| 370 } |
| 371 |
334 } // namespace tcmalloc | 372 } // namespace tcmalloc |
OLD | NEW |