15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2008, Google Inc. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// All rights reserved. 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Redistribution and use in source and binary forms, with or without 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// modification, are permitted provided that the following conditions are 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// met: 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Redistributions of source code must retain the above copyright 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// notice, this list of conditions and the following disclaimer. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Redistributions in binary form must reproduce the above 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// copyright notice, this list of conditions and the following disclaimer 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in the documentation and/or other materials provided with the 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// distribution. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Neither the name of Google Inc. nor the names of its 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// contributors may be used to endorse or promote products derived from 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// this software without specific prior written permission. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// --- 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Author: Sanjay Ghemawat <opensource@google.com> 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "config.h" 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "central_freelist.h" 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "internal_logging.h" // for ASSERT, MESSAGE 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "linked_list.h" // for SLL_Next, SLL_Push, etc 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "page_heap.h" // for PageHeap 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "static_vars.h" // for Static 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::min; 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::max; 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace tcmalloc { 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CentralFreeList::Init(size_t cl) { 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_class_ = cl; 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::DLL_Init(&empty_); 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::DLL_Init(&nonempty_); 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) num_spans_ = 0; 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) counter_ = 0; 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_cache_size_ = kMaxNumTransferEntries; 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef TCMALLOC_SMALL_BUT_SLOW 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Disable the transfer cache for the small footprint case. 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cache_size_ = 0; 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cache_size_ = 16; 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (cl > 0) { 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Limit the maximum size of the cache based on the size class. If this 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // is not done, large size class objects will consume a lot of memory if 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // they just sit in the transfer cache. 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32_t bytes = Static::sizemap()->ByteSizeForClass(cl); 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32_t objs_to_move = Static::sizemap()->num_objects_to_move(cl); 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(objs_to_move > 0 && bytes > 0); 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Limit each size class cache to at most 1MB of objects or one entry, 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // whichever is greater. Total transfer cache memory used across all 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // size classes then can't be greater than approximately 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1MB * kMaxNumTransferEntries. 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // min and max are in parens to avoid macro-expansion on windows. 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_cache_size_ = (min)(max_cache_size_, 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (max)(1, (1024 * 1024) / (bytes * objs_to_move))); 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cache_size_ = (min)(cache_size_, max_cache_size_); 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) used_slots_ = 0; 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(cache_size_ <= max_cache_size_); 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CentralFreeList::ReleaseListToSpans(void* start) { 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (start) { 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *next = SLL_Next(start); 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ReleaseToSpans(start); 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) start = next; 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// MapObjectToSpan should logically be part of ReleaseToSpans. But 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// this triggers an optimization bug in gcc 4.5.0. Moving to a 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// separate function, and making sure that function isn't inlined, 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// seems to fix the problem. It also should be fixed for gcc 4.5.1. 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if __GNUC__ == 4 && __GNUC_MINOR__ == 5 && __GNUC_PATCHLEVEL__ == 0 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)__attribute__ ((noinline)) 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Span* MapObjectToSpan(void* object) { 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const PageID p = reinterpret_cast<uintptr_t>(object) >> kPageShift; 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* span = Static::pageheap()->GetDescriptor(p); 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return span; 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CentralFreeList::ReleaseToSpans(void* object) { 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* span = MapObjectToSpan(object); 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span != NULL); 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->refcount > 0); 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If span is empty, move it to non-empty list 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span->objects == NULL) { 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::DLL_Remove(span); 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::DLL_Prepend(&nonempty_, span); 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(span, 'N', 0); 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The following check is expensive, so it is disabled by default 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (false) { 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check that object does not occur in list 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int got = 0; 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (void* p = span->objects; p != NULL; p = *((void**) p)) { 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(p != object); 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) got++; 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(got + span->refcount == 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (span->length<<kPageShift) / 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Static::sizemap()->ByteSizeForClass(span->sizeclass)); 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) counter_++; 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->refcount--; 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span->refcount == 0) { 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(span, '#', 0); 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) counter_ -= ((span->length<<kPageShift) / 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Static::sizemap()->ByteSizeForClass(span->sizeclass)); 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::DLL_Remove(span); 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --num_spans_; 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Release central list lock while operating on pageheap 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lock_.Unlock(); 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SpinLockHolder h(Static::pageheap_lock()); 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Static::pageheap()->Delete(span); 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lock_.Lock(); 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *(reinterpret_cast<void**>(object)) = span->objects; 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->objects = object; 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool CentralFreeList::EvictRandomSizeClass( 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int locked_size_class, bool force) { 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static int race_counter = 0; 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int t = race_counter++; // Updated without a lock, but who cares. 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (t >= kNumClasses) { 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (t >= kNumClasses) { 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) t -= kNumClasses; 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) race_counter = t; 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(t >= 0); 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(t < kNumClasses); 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (t == locked_size_class) return false; 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Static::central_cache()[t].ShrinkCache(locked_size_class, force); 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool CentralFreeList::MakeCacheSpace() { 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Is there room in the cache? 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (used_slots_ < cache_size_) return true; 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check if we can expand this cache? 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (cache_size_ == max_cache_size_) return false; 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Ok, we'll try to grab an entry from some other size class. 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (EvictRandomSizeClass(size_class_, false) || 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EvictRandomSizeClass(size_class_, true)) { 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Succeeded in evicting, we're going to make our cache larger. 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // However, we may have dropped and re-acquired the lock in 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // EvictRandomSizeClass (via ShrinkCache and the LockInverter), so the 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // cache_size may have changed. Therefore, check and verify that it is 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // still OK to increase the cache_size. 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (cache_size_ < max_cache_size_) { 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cache_size_++; 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class LockInverter { 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SpinLock *held_, *temp_; 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline explicit LockInverter(SpinLock* held, SpinLock *temp) 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : held_(held), temp_(temp) { held_->Unlock(); temp_->Lock(); } 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline ~LockInverter() { temp_->Unlock(); held_->Lock(); } 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This function is marked as NO_THREAD_SAFETY_ANALYSIS because it uses 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LockInverter to release one lock and acquire another in scoped-lock 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// style, which our current annotation/analysis does not support. 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool CentralFreeList::ShrinkCache(int locked_size_class, bool force) 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NO_THREAD_SAFETY_ANALYSIS { 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Start with a quick check without taking a lock. 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (cache_size_ == 0) return false; 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We don't evict from a full cache unless we are 'forcing'. 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (force == false && used_slots_ == cache_size_) return false; 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Grab lock, but first release the other lock held by this thread. We use 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the lock inverter to ensure that we never hold two size class locks 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // concurrently. That can create a deadlock because there is no well 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // defined nesting order. 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LockInverter li(&Static::central_cache()[locked_size_class].lock_, &lock_); 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(used_slots_ <= cache_size_); 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(0 <= cache_size_); 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (cache_size_ == 0) return false; 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (used_slots_ == cache_size_) { 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (force == false) return false; 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ReleaseListToSpans releases the lock, so we have to make all the 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // updates to the central list before calling it. 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cache_size_--; 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) used_slots_--; 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ReleaseListToSpans(tc_slots_[used_slots_].head); 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cache_size_--; 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CentralFreeList::InsertRange(void *start, void *end, int N) { 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SpinLockHolder h(&lock_); 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (N == Static::sizemap()->num_objects_to_move(size_class_) && 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MakeCacheSpace()) { 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int slot = used_slots_++; 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(slot >=0); 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(slot < max_cache_size_); 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TCEntry *entry = &tc_slots_[slot]; 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entry->head = start; 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entry->tail = end; 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ReleaseListToSpans(start); 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int CentralFreeList::RemoveRange(void **start, void **end, int N) { 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(N > 0); 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lock_.Lock(); 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (N == Static::sizemap()->num_objects_to_move(size_class_) && 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) used_slots_ > 0) { 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int slot = --used_slots_; 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(slot >= 0); 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TCEntry *entry = &tc_slots_[slot]; 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *start = entry->head; 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *end = entry->tail; 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lock_.Unlock(); 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return N; 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int result = 0; 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* head = NULL; 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* tail = NULL; 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO: Prefetch multiple TCEntries? 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tail = FetchFromSpansSafe(); 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (tail != NULL) { 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SLL_SetNext(tail, NULL); 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) head = tail; 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result = 1; 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (result < N) { 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *t = FetchFromSpans(); 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!t) break; 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SLL_Push(&head, t); 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result++; 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lock_.Unlock(); 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *start = head; 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *end = tail; 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return result; 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void* CentralFreeList::FetchFromSpansSafe() { 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *t = FetchFromSpans(); 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!t) { 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Populate(); 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) t = FetchFromSpans(); 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return t; 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void* CentralFreeList::FetchFromSpans() { 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (tcmalloc::DLL_IsEmpty(&nonempty_)) return NULL; 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* span = nonempty_.next; 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->objects != NULL); 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->refcount++; 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* result = span->objects; 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->objects = *(reinterpret_cast<void**>(result)); 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span->objects == NULL) { 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Move to empty list 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::DLL_Remove(span); 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::DLL_Prepend(&empty_, span); 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(span, 'E', 0); 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) counter_--; 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return result; 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Fetch memory from the system and add to the central cache freelist. 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CentralFreeList::Populate() { 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Release central list lock while operating on pageheap 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lock_.Unlock(); 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t npages = Static::sizemap()->class_to_pages(size_class_); 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* span; 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SpinLockHolder h(Static::pageheap_lock()); 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span = Static::pageheap()->New(npages); 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span) Static::pageheap()->RegisterSizeClass(span, size_class_); 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span == NULL) { 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Log(kLog, __FILE__, __LINE__, 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "tcmalloc: allocation failed", npages << kPageShift); 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lock_.Lock(); 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->length == npages); 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Cache sizeclass info eagerly. Locking is not necessary. 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (Instead of being eager, we could just replace any stale info 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // about this span, but that seems to be no better in practice.) 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < npages; i++) { 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Static::pageheap()->CacheSizeClass(span->start + i, size_class_); 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Split the block into pieces and add to the free-list 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO: coloring of objects to avoid cache conflicts? 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void** tail = &span->objects; 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) char* ptr = reinterpret_cast<char*>(span->start << kPageShift); 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) char* limit = ptr + (npages << kPageShift); 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t size = Static::sizemap()->ByteSizeForClass(size_class_); 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int num = 0; 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (ptr + size <= limit) { 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *tail = ptr; 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tail = reinterpret_cast<void**>(ptr); 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ptr += size; 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) num++; 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(ptr <= limit); 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *tail = NULL; 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->refcount = 0; // No sub-object in use yet 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Add span to list of non-empty spans 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lock_.Lock(); 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::DLL_Prepend(&nonempty_, span); 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++num_spans_; 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) counter_ += num; 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int CentralFreeList::tc_length() { 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SpinLockHolder h(&lock_); 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return used_slots_ * Static::sizemap()->num_objects_to_move(size_class_); 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)size_t CentralFreeList::OverheadBytes() { 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SpinLockHolder h(&lock_); 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (size_class_ == 0) { // 0 holds the 0-sized allocations 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t pages_per_span = Static::sizemap()->class_to_pages(size_class_); 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t object_size = Static::sizemap()->class_to_size(size_class_); 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(object_size > 0); 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t overhead_per_span = (pages_per_span * kPageSize) % object_size; 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return num_spans_ * overhead_per_span; 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace tcmalloc 377