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> | |
35 #include "central_freelist.h" | 34 #include "central_freelist.h" |
36 #include "free_list.h" // for FL_Next, FL_Push, etc | 35 #include "free_list.h" // for FL_Next, FL_Push, etc |
37 #include "internal_logging.h" // for ASSERT, MESSAGE | 36 #include "internal_logging.h" // for ASSERT, MESSAGE |
38 #include "page_heap.h" // for PageHeap | 37 #include "page_heap.h" // for PageHeap |
39 #include "static_vars.h" // for Static | 38 #include "static_vars.h" // for Static |
40 | 39 |
41 using std::min; | |
42 using std::max; | |
43 | |
44 namespace tcmalloc { | 40 namespace tcmalloc { |
45 | 41 |
46 void CentralFreeList::Init(size_t cl) { | 42 void CentralFreeList::Init(size_t cl) { |
47 size_class_ = cl; | 43 size_class_ = cl; |
48 tcmalloc::DLL_Init(&empty_); | 44 tcmalloc::DLL_Init(&empty_); |
49 tcmalloc::DLL_Init(&nonempty_); | 45 tcmalloc::DLL_Init(&nonempty_); |
50 num_spans_ = 0; | |
51 counter_ = 0; | 46 counter_ = 0; |
52 | 47 |
53 max_cache_size_ = kMaxNumTransferEntries; | |
54 #ifdef TCMALLOC_SMALL_BUT_SLOW | 48 #ifdef TCMALLOC_SMALL_BUT_SLOW |
55 // Disable the transfer cache for the small footprint case. | 49 // Disable the transfer cache for the small footprint case. |
56 cache_size_ = 0; | 50 cache_size_ = 0; |
57 #else | 51 #else |
58 cache_size_ = 16; | 52 cache_size_ = 16; |
59 #endif | 53 #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 } | |
77 used_slots_ = 0; | 54 used_slots_ = 0; |
78 ASSERT(cache_size_ <= max_cache_size_); | 55 ASSERT(cache_size_ <= kNumTransferEntries); |
79 } | 56 } |
80 | 57 |
81 void CentralFreeList::ReleaseListToSpans(void* start) { | 58 void CentralFreeList::ReleaseListToSpans(void* start) { |
82 while (start) { | 59 while (start) { |
83 void *next = FL_Next(start); | 60 void *next = FL_Next(start); |
84 ReleaseToSpans(start); | 61 ReleaseToSpans(start); |
85 start = next; | 62 start = next; |
86 } | 63 } |
87 } | 64 } |
88 | 65 |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
125 Static::sizemap()->ByteSizeForClass(span->sizeclass)); | 102 Static::sizemap()->ByteSizeForClass(span->sizeclass)); |
126 } | 103 } |
127 | 104 |
128 counter_++; | 105 counter_++; |
129 span->refcount--; | 106 span->refcount--; |
130 if (span->refcount == 0) { | 107 if (span->refcount == 0) { |
131 Event(span, '#', 0); | 108 Event(span, '#', 0); |
132 counter_ -= ((span->length<<kPageShift) / | 109 counter_ -= ((span->length<<kPageShift) / |
133 Static::sizemap()->ByteSizeForClass(span->sizeclass)); | 110 Static::sizemap()->ByteSizeForClass(span->sizeclass)); |
134 tcmalloc::DLL_Remove(span); | 111 tcmalloc::DLL_Remove(span); |
135 --num_spans_; | |
136 | 112 |
137 // Release central list lock while operating on pageheap | 113 // Release central list lock while operating on pageheap |
138 lock_.Unlock(); | 114 lock_.Unlock(); |
139 { | 115 { |
140 SpinLockHolder h(Static::pageheap_lock()); | 116 SpinLockHolder h(Static::pageheap_lock()); |
141 Static::pageheap()->Delete(span); | 117 Static::pageheap()->Delete(span); |
142 } | 118 } |
143 lock_.Lock(); | 119 lock_.Lock(); |
144 } else { | 120 } else { |
145 FL_Push(&(span->objects), object); | 121 FL_Push(&(span->objects), object); |
(...skipping 13 matching lines...) Expand all Loading... |
159 ASSERT(t >= 0); | 135 ASSERT(t >= 0); |
160 ASSERT(t < kNumClasses); | 136 ASSERT(t < kNumClasses); |
161 if (t == locked_size_class) return false; | 137 if (t == locked_size_class) return false; |
162 return Static::central_cache()[t].ShrinkCache(locked_size_class, force); | 138 return Static::central_cache()[t].ShrinkCache(locked_size_class, force); |
163 } | 139 } |
164 | 140 |
165 bool CentralFreeList::MakeCacheSpace() { | 141 bool CentralFreeList::MakeCacheSpace() { |
166 // Is there room in the cache? | 142 // Is there room in the cache? |
167 if (used_slots_ < cache_size_) return true; | 143 if (used_slots_ < cache_size_) return true; |
168 // Check if we can expand this cache? | 144 // Check if we can expand this cache? |
169 if (cache_size_ == max_cache_size_) return false; | 145 if (cache_size_ == kNumTransferEntries) return false; |
170 // Ok, we'll try to grab an entry from some other size class. | 146 // Ok, we'll try to grab an entry from some other size class. |
171 if (EvictRandomSizeClass(size_class_, false) || | 147 if (EvictRandomSizeClass(size_class_, false) || |
172 EvictRandomSizeClass(size_class_, true)) { | 148 EvictRandomSizeClass(size_class_, true)) { |
173 // Succeeded in evicting, we're going to make our cache larger. | 149 // Succeeded in evicting, we're going to make our cache larger. |
174 // However, we may have dropped and re-acquired the lock in | 150 // However, we may have dropped and re-acquired the lock in |
175 // EvictRandomSizeClass (via ShrinkCache and the LockInverter), so the | 151 // EvictRandomSizeClass (via ShrinkCache and the LockInverter), so the |
176 // cache_size may have changed. Therefore, check and verify that it is | 152 // cache_size may have changed. Therefore, check and verify that it is |
177 // still OK to increase the cache_size. | 153 // still OK to increase the cache_size. |
178 if (cache_size_ < max_cache_size_) { | 154 if (cache_size_ < kNumTransferEntries) { |
179 cache_size_++; | 155 cache_size_++; |
180 return true; | 156 return true; |
181 } | 157 } |
182 } | 158 } |
183 return false; | 159 return false; |
184 } | 160 } |
185 | 161 |
186 | 162 |
187 namespace { | 163 namespace { |
188 class LockInverter { | 164 class LockInverter { |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
225 cache_size_--; | 201 cache_size_--; |
226 return true; | 202 return true; |
227 } | 203 } |
228 | 204 |
229 void CentralFreeList::InsertRange(void *start, void *end, int N) { | 205 void CentralFreeList::InsertRange(void *start, void *end, int N) { |
230 SpinLockHolder h(&lock_); | 206 SpinLockHolder h(&lock_); |
231 if (N == Static::sizemap()->num_objects_to_move(size_class_) && | 207 if (N == Static::sizemap()->num_objects_to_move(size_class_) && |
232 MakeCacheSpace()) { | 208 MakeCacheSpace()) { |
233 int slot = used_slots_++; | 209 int slot = used_slots_++; |
234 ASSERT(slot >=0); | 210 ASSERT(slot >=0); |
235 ASSERT(slot < max_cache_size_); | 211 ASSERT(slot < kNumTransferEntries); |
236 TCEntry *entry = &tc_slots_[slot]; | 212 TCEntry *entry = &tc_slots_[slot]; |
237 entry->head = start; | 213 entry->head = start; |
238 entry->tail = end; | 214 entry->tail = end; |
239 return; | 215 return; |
240 } | 216 } |
241 ReleaseListToSpans(start); | 217 ReleaseListToSpans(start); |
242 } | 218 } |
243 | 219 |
244 int CentralFreeList::RemoveRange(void **start, void **end, int N) { | 220 int CentralFreeList::RemoveRange(void **start, void **end, int N) { |
245 ASSERT(N > 0); | 221 ASSERT(N > 0); |
(...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
309 lock_.Unlock(); | 285 lock_.Unlock(); |
310 const size_t npages = Static::sizemap()->class_to_pages(size_class_); | 286 const size_t npages = Static::sizemap()->class_to_pages(size_class_); |
311 | 287 |
312 Span* span; | 288 Span* span; |
313 { | 289 { |
314 SpinLockHolder h(Static::pageheap_lock()); | 290 SpinLockHolder h(Static::pageheap_lock()); |
315 span = Static::pageheap()->New(npages); | 291 span = Static::pageheap()->New(npages); |
316 if (span) Static::pageheap()->RegisterSizeClass(span, size_class_); | 292 if (span) Static::pageheap()->RegisterSizeClass(span, size_class_); |
317 } | 293 } |
318 if (span == NULL) { | 294 if (span == NULL) { |
319 Log(kLog, __FILE__, __LINE__, | 295 MESSAGE("tcmalloc: allocation failed", npages << kPageShift); |
320 "tcmalloc: allocation failed", npages << kPageShift); | |
321 lock_.Lock(); | 296 lock_.Lock(); |
322 return; | 297 return; |
323 } | 298 } |
324 ASSERT(span->length == npages); | 299 ASSERT(span->length == npages); |
325 // Cache sizeclass info eagerly. Locking is not necessary. | 300 // Cache sizeclass info eagerly. Locking is not necessary. |
326 // (Instead of being eager, we could just replace any stale info | 301 // (Instead of being eager, we could just replace any stale info |
327 // about this span, but that seems to be no better in practice.) | 302 // about this span, but that seems to be no better in practice.) |
328 for (int i = 0; i < npages; i++) { | 303 for (int i = 0; i < npages; i++) { |
329 Static::pageheap()->CacheSizeClass(span->start + i, size_class_); | 304 Static::pageheap()->CacheSizeClass(span->start + i, size_class_); |
330 } | 305 } |
(...skipping 10 matching lines...) Expand all Loading... |
341 ptr += size; | 316 ptr += size; |
342 num++; | 317 num++; |
343 } | 318 } |
344 ASSERT(ptr <= limit); | 319 ASSERT(ptr <= limit); |
345 span->objects = list; | 320 span->objects = list; |
346 span->refcount = 0; // No sub-object in use yet | 321 span->refcount = 0; // No sub-object in use yet |
347 | 322 |
348 // Add span to list of non-empty spans | 323 // Add span to list of non-empty spans |
349 lock_.Lock(); | 324 lock_.Lock(); |
350 tcmalloc::DLL_Prepend(&nonempty_, span); | 325 tcmalloc::DLL_Prepend(&nonempty_, span); |
351 ++num_spans_; | |
352 counter_ += num; | 326 counter_ += num; |
353 } | 327 } |
354 | 328 |
355 int CentralFreeList::tc_length() { | 329 int CentralFreeList::tc_length() { |
356 SpinLockHolder h(&lock_); | 330 SpinLockHolder h(&lock_); |
357 return used_slots_ * Static::sizemap()->num_objects_to_move(size_class_); | 331 return used_slots_ * Static::sizemap()->num_objects_to_move(size_class_); |
358 } | 332 } |
359 | 333 |
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 | |
372 } // namespace tcmalloc | 334 } // namespace tcmalloc |
OLD | NEW |