1// Copyright (c) 2008, Google Inc. 2// All rights reserved. 3// 4// Redistribution and use in source and binary forms, with or without 5// modification, are permitted provided that the following conditions are 6// met: 7// 8// * Redistributions of source code must retain the above copyright 9// notice, this list of conditions and the following disclaimer. 10// * Redistributions in binary form must reproduce the above 11// copyright notice, this list of conditions and the following disclaimer 12// in the documentation and/or other materials provided with the 13// distribution. 14// * Neither the name of Google Inc. nor the names of its 15// contributors may be used to endorse or promote products derived from 16// this software without specific prior written permission. 17// 18// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 30// --- 31// Author: Sanjay Ghemawat <opensource@google.com> 32 33#include "config.h" 34#include <algorithm> 35#include "central_freelist.h" 36#include "internal_logging.h" // for ASSERT, MESSAGE 37#include "linked_list.h" // for SLL_Next, SLL_Push, etc 38#include "page_heap.h" // for PageHeap 39#include "static_vars.h" // for Static 40 41using std::min; 42using std::max; 43 44namespace tcmalloc { 45 46void CentralFreeList::Init(size_t cl) { 47 size_class_ = cl; 48 tcmalloc::DLL_Init(&empty_); 49 tcmalloc::DLL_Init(&nonempty_); 50 num_spans_ = 0; 51 counter_ = 0; 52 53 max_cache_size_ = kMaxNumTransferEntries; 54#ifdef TCMALLOC_SMALL_BUT_SLOW 55 // Disable the transfer cache for the small footprint case. 56 cache_size_ = 0; 57#else 58 cache_size_ = 16; 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 } 77 used_slots_ = 0; 78 ASSERT(cache_size_ <= max_cache_size_); 79} 80 81void CentralFreeList::ReleaseListToSpans(void* start) { 82 while (start) { 83 void *next = SLL_Next(start); 84 ReleaseToSpans(start); 85 start = next; 86 } 87} 88 89// MapObjectToSpan should logically be part of ReleaseToSpans. But 90// this triggers an optimization bug in gcc 4.5.0. Moving to a 91// separate function, and making sure that function isn't inlined, 92// seems to fix the problem. It also should be fixed for gcc 4.5.1. 93static 94#if __GNUC__ == 4 && __GNUC_MINOR__ == 5 && __GNUC_PATCHLEVEL__ == 0 95__attribute__ ((noinline)) 96#endif 97Span* MapObjectToSpan(void* object) { 98 const PageID p = reinterpret_cast<uintptr_t>(object) >> kPageShift; 99 Span* span = Static::pageheap()->GetDescriptor(p); 100 return span; 101} 102 103void CentralFreeList::ReleaseToSpans(void* object) { 104 Span* span = MapObjectToSpan(object); 105 ASSERT(span != NULL); 106 ASSERT(span->refcount > 0); 107 108 // If span is empty, move it to non-empty list 109 if (span->objects == NULL) { 110 tcmalloc::DLL_Remove(span); 111 tcmalloc::DLL_Prepend(&nonempty_, span); 112 Event(span, 'N', 0); 113 } 114 115 // The following check is expensive, so it is disabled by default 116 if (false) { 117 // Check that object does not occur in list 118 int got = 0; 119 for (void* p = span->objects; p != NULL; p = *((void**) p)) { 120 ASSERT(p != object); 121 got++; 122 } 123 ASSERT(got + span->refcount == 124 (span->length<<kPageShift) / 125 Static::sizemap()->ByteSizeForClass(span->sizeclass)); 126 } 127 128 counter_++; 129 span->refcount--; 130 if (span->refcount == 0) { 131 Event(span, '#', 0); 132 counter_ -= ((span->length<<kPageShift) / 133 Static::sizemap()->ByteSizeForClass(span->sizeclass)); 134 tcmalloc::DLL_Remove(span); 135 --num_spans_; 136 137 // Release central list lock while operating on pageheap 138 lock_.Unlock(); 139 { 140 SpinLockHolder h(Static::pageheap_lock()); 141 Static::pageheap()->Delete(span); 142 } 143 lock_.Lock(); 144 } else { 145 *(reinterpret_cast<void**>(object)) = span->objects; 146 span->objects = object; 147 } 148} 149 150bool CentralFreeList::EvictRandomSizeClass( 151 int locked_size_class, bool force) { 152 static int race_counter = 0; 153 int t = race_counter++; // Updated without a lock, but who cares. 154 if (t >= kNumClasses) { 155 while (t >= kNumClasses) { 156 t -= kNumClasses; 157 } 158 race_counter = t; 159 } 160 ASSERT(t >= 0); 161 ASSERT(t < kNumClasses); 162 if (t == locked_size_class) return false; 163 return Static::central_cache()[t].ShrinkCache(locked_size_class, force); 164} 165 166bool CentralFreeList::MakeCacheSpace() { 167 // Is there room in the cache? 168 if (used_slots_ < cache_size_) return true; 169 // Check if we can expand this cache? 170 if (cache_size_ == max_cache_size_) return false; 171 // Ok, we'll try to grab an entry from some other size class. 172 if (EvictRandomSizeClass(size_class_, false) || 173 EvictRandomSizeClass(size_class_, true)) { 174 // Succeeded in evicting, we're going to make our cache larger. 175 // However, we may have dropped and re-acquired the lock in 176 // EvictRandomSizeClass (via ShrinkCache and the LockInverter), so the 177 // cache_size may have changed. Therefore, check and verify that it is 178 // still OK to increase the cache_size. 179 if (cache_size_ < max_cache_size_) { 180 cache_size_++; 181 return true; 182 } 183 } 184 return false; 185} 186 187 188namespace { 189class LockInverter { 190 private: 191 SpinLock *held_, *temp_; 192 public: 193 inline explicit LockInverter(SpinLock* held, SpinLock *temp) 194 : held_(held), temp_(temp) { held_->Unlock(); temp_->Lock(); } 195 inline ~LockInverter() { temp_->Unlock(); held_->Lock(); } 196}; 197} 198 199// This function is marked as NO_THREAD_SAFETY_ANALYSIS because it uses 200// LockInverter to release one lock and acquire another in scoped-lock 201// style, which our current annotation/analysis does not support. 202bool CentralFreeList::ShrinkCache(int locked_size_class, bool force) 203 NO_THREAD_SAFETY_ANALYSIS { 204 // Start with a quick check without taking a lock. 205 if (cache_size_ == 0) return false; 206 // We don't evict from a full cache unless we are 'forcing'. 207 if (force == false && used_slots_ == cache_size_) return false; 208 209 // Grab lock, but first release the other lock held by this thread. We use 210 // the lock inverter to ensure that we never hold two size class locks 211 // concurrently. That can create a deadlock because there is no well 212 // defined nesting order. 213 LockInverter li(&Static::central_cache()[locked_size_class].lock_, &lock_); 214 ASSERT(used_slots_ <= cache_size_); 215 ASSERT(0 <= cache_size_); 216 if (cache_size_ == 0) return false; 217 if (used_slots_ == cache_size_) { 218 if (force == false) return false; 219 // ReleaseListToSpans releases the lock, so we have to make all the 220 // updates to the central list before calling it. 221 cache_size_--; 222 used_slots_--; 223 ReleaseListToSpans(tc_slots_[used_slots_].head); 224 return true; 225 } 226 cache_size_--; 227 return true; 228} 229 230void CentralFreeList::InsertRange(void *start, void *end, int N) { 231 SpinLockHolder h(&lock_); 232 if (N == Static::sizemap()->num_objects_to_move(size_class_) && 233 MakeCacheSpace()) { 234 int slot = used_slots_++; 235 ASSERT(slot >=0); 236 ASSERT(slot < max_cache_size_); 237 TCEntry *entry = &tc_slots_[slot]; 238 entry->head = start; 239 entry->tail = end; 240 return; 241 } 242 ReleaseListToSpans(start); 243} 244 245int CentralFreeList::RemoveRange(void **start, void **end, int N) { 246 ASSERT(N > 0); 247 lock_.Lock(); 248 if (N == Static::sizemap()->num_objects_to_move(size_class_) && 249 used_slots_ > 0) { 250 int slot = --used_slots_; 251 ASSERT(slot >= 0); 252 TCEntry *entry = &tc_slots_[slot]; 253 *start = entry->head; 254 *end = entry->tail; 255 lock_.Unlock(); 256 return N; 257 } 258 259 int result = 0; 260 void* head = NULL; 261 void* tail = NULL; 262 // TODO: Prefetch multiple TCEntries? 263 tail = FetchFromSpansSafe(); 264 if (tail != NULL) { 265 SLL_SetNext(tail, NULL); 266 head = tail; 267 result = 1; 268 while (result < N) { 269 void *t = FetchFromSpans(); 270 if (!t) break; 271 SLL_Push(&head, t); 272 result++; 273 } 274 } 275 lock_.Unlock(); 276 *start = head; 277 *end = tail; 278 return result; 279} 280 281 282void* CentralFreeList::FetchFromSpansSafe() { 283 void *t = FetchFromSpans(); 284 if (!t) { 285 Populate(); 286 t = FetchFromSpans(); 287 } 288 return t; 289} 290 291void* CentralFreeList::FetchFromSpans() { 292 if (tcmalloc::DLL_IsEmpty(&nonempty_)) return NULL; 293 Span* span = nonempty_.next; 294 295 ASSERT(span->objects != NULL); 296 span->refcount++; 297 void* result = span->objects; 298 span->objects = *(reinterpret_cast<void**>(result)); 299 if (span->objects == NULL) { 300 // Move to empty list 301 tcmalloc::DLL_Remove(span); 302 tcmalloc::DLL_Prepend(&empty_, span); 303 Event(span, 'E', 0); 304 } 305 counter_--; 306 return result; 307} 308 309// Fetch memory from the system and add to the central cache freelist. 310void CentralFreeList::Populate() { 311 // Release central list lock while operating on pageheap 312 lock_.Unlock(); 313 const size_t npages = Static::sizemap()->class_to_pages(size_class_); 314 315 Span* span; 316 { 317 SpinLockHolder h(Static::pageheap_lock()); 318 span = Static::pageheap()->New(npages); 319 if (span) Static::pageheap()->RegisterSizeClass(span, size_class_); 320 } 321 if (span == NULL) { 322 Log(kLog, __FILE__, __LINE__, 323 "tcmalloc: allocation failed", npages << kPageShift); 324 lock_.Lock(); 325 return; 326 } 327 ASSERT(span->length == npages); 328 // Cache sizeclass info eagerly. Locking is not necessary. 329 // (Instead of being eager, we could just replace any stale info 330 // about this span, but that seems to be no better in practice.) 331 for (int i = 0; i < npages; i++) { 332 Static::pageheap()->CacheSizeClass(span->start + i, size_class_); 333 } 334 335 // Split the block into pieces and add to the free-list 336 // TODO: coloring of objects to avoid cache conflicts? 337 void** tail = &span->objects; 338 char* ptr = reinterpret_cast<char*>(span->start << kPageShift); 339 char* limit = ptr + (npages << kPageShift); 340 const size_t size = Static::sizemap()->ByteSizeForClass(size_class_); 341 int num = 0; 342 while (ptr + size <= limit) { 343 *tail = ptr; 344 tail = reinterpret_cast<void**>(ptr); 345 ptr += size; 346 num++; 347 } 348 ASSERT(ptr <= limit); 349 *tail = NULL; 350 span->refcount = 0; // No sub-object in use yet 351 352 // Add span to list of non-empty spans 353 lock_.Lock(); 354 tcmalloc::DLL_Prepend(&nonempty_, span); 355 ++num_spans_; 356 counter_ += num; 357} 358 359int CentralFreeList::tc_length() { 360 SpinLockHolder h(&lock_); 361 return used_slots_ * Static::sizemap()->num_objects_to_move(size_class_); 362} 363 364size_t CentralFreeList::OverheadBytes() { 365 SpinLockHolder h(&lock_); 366 if (size_class_ == 0) { // 0 holds the 0-sized allocations 367 return 0; 368 } 369 const size_t pages_per_span = Static::sizemap()->class_to_pages(size_class_); 370 const size_t object_size = Static::sizemap()->class_to_size(size_class_); 371 ASSERT(object_size > 0); 372 const size_t overhead_per_span = (pages_per_span * kPageSize) % object_size; 373 return num_spans_ * overhead_per_span; 374} 375 376} // namespace tcmalloc 377