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 (at) google.com> 32 33 #ifndef TCMALLOC_CENTRAL_FREELIST_H_ 34 #define TCMALLOC_CENTRAL_FREELIST_H_ 35 36 #include "config.h" 37 #include <stddef.h> // for size_t 38 #ifdef HAVE_STDINT_H 39 #include <stdint.h> // for int32_t 40 #endif 41 #include "base/spinlock.h" 42 #include "base/thread_annotations.h" 43 #include "common.h" 44 #include "span.h" 45 46 namespace tcmalloc { 47 48 // Data kept per size-class in central cache. 49 class CentralFreeList { 50 public: 51 // A CentralFreeList may be used before its constructor runs. 52 // So we prevent lock_'s constructor from doing anything to the 53 // lock_ state. 54 CentralFreeList() : lock_(base::LINKER_INITIALIZED) { } 55 56 void Init(size_t cl); 57 58 // These methods all do internal locking. 59 60 // Insert the specified range into the central freelist. N is the number of 61 // elements in the range. RemoveRange() is the opposite operation. 62 void InsertRange(void *start, void *end, int N); 63 64 // Returns the actual number of fetched elements and sets *start and *end. 65 int RemoveRange(void **start, void **end, int N); 66 67 // Returns the number of free objects in cache. 68 int length() { 69 SpinLockHolder h(&lock_); 70 return counter_; 71 } 72 73 // Returns the number of free objects in the transfer cache. 74 int tc_length(); 75 76 // Returns the memory overhead (internal fragmentation) attributable 77 // to the freelist. This is memory lost when the size of elements 78 // in a freelist doesn't exactly divide the page-size (an 8192-byte 79 // page full of 5-byte objects would have 2 bytes memory overhead). 80 size_t OverheadBytes(); 81 82 private: 83 // TransferCache is used to cache transfers of 84 // sizemap.num_objects_to_move(size_class) back and forth between 85 // thread caches and the central cache for a given size class. 86 struct TCEntry { 87 void *head; // Head of chain of objects. 88 void *tail; // Tail of chain of objects. 89 }; 90 91 // A central cache freelist can have anywhere from 0 to kMaxNumTransferEntries 92 // slots to put link list chains into. 93 #ifdef TCMALLOC_SMALL_BUT_SLOW 94 // For the small memory model, the transfer cache is not used. 95 static const int kMaxNumTransferEntries = 0; 96 #else 97 // Starting point for the the maximum number of entries in the transfer cache. 98 // This actual maximum for a given size class may be lower than this 99 // maximum value. 100 static const int kMaxNumTransferEntries = 64; 101 #endif 102 103 // REQUIRES: lock_ is held 104 // Remove object from cache and return. 105 // Return NULL if no free entries in cache. 106 void* FetchFromSpans() EXCLUSIVE_LOCKS_REQUIRED(lock_); 107 108 // REQUIRES: lock_ is held 109 // Remove object from cache and return. Fetches 110 // from pageheap if cache is empty. Only returns 111 // NULL on allocation failure. 112 void* FetchFromSpansSafe() EXCLUSIVE_LOCKS_REQUIRED(lock_); 113 114 // REQUIRES: lock_ is held 115 // Release a linked list of objects to spans. 116 // May temporarily release lock_. 117 void ReleaseListToSpans(void *start) EXCLUSIVE_LOCKS_REQUIRED(lock_); 118 119 // REQUIRES: lock_ is held 120 // Release an object to spans. 121 // May temporarily release lock_. 122 void ReleaseToSpans(void* object) EXCLUSIVE_LOCKS_REQUIRED(lock_); 123 124 // REQUIRES: lock_ is held 125 // Populate cache by fetching from the page heap. 126 // May temporarily release lock_. 127 void Populate() EXCLUSIVE_LOCKS_REQUIRED(lock_); 128 129 // REQUIRES: lock is held. 130 // Tries to make room for a TCEntry. If the cache is full it will try to 131 // expand it at the cost of some other cache size. Return false if there is 132 // no space. 133 bool MakeCacheSpace() EXCLUSIVE_LOCKS_REQUIRED(lock_); 134 135 // REQUIRES: lock_ for locked_size_class is held. 136 // Picks a "random" size class to steal TCEntry slot from. In reality it 137 // just iterates over the sizeclasses but does so without taking a lock. 138 // Returns true on success. 139 // May temporarily lock a "random" size class. 140 static bool EvictRandomSizeClass(int locked_size_class, bool force); 141 142 // REQUIRES: lock_ is *not* held. 143 // Tries to shrink the Cache. If force is true it will relase objects to 144 // spans if it allows it to shrink the cache. Return false if it failed to 145 // shrink the cache. Decrements cache_size_ on succeess. 146 // May temporarily take lock_. If it takes lock_, the locked_size_class 147 // lock is released to keep the thread from holding two size class locks 148 // concurrently which could lead to a deadlock. 149 bool ShrinkCache(int locked_size_class, bool force) LOCKS_EXCLUDED(lock_); 150 151 // This lock protects all the data members. cached_entries and cache_size_ 152 // may be looked at without holding the lock. 153 SpinLock lock_; 154 155 // We keep linked lists of empty and non-empty spans. 156 size_t size_class_; // My size class 157 Span empty_; // Dummy header for list of empty spans 158 Span nonempty_; // Dummy header for list of non-empty spans 159 size_t num_spans_; // Number of spans in empty_ plus nonempty_ 160 size_t counter_; // Number of free objects in cache entry 161 162 // Here we reserve space for TCEntry cache slots. Space is preallocated 163 // for the largest possible number of entries than any one size class may 164 // accumulate. Not all size classes are allowed to accumulate 165 // kMaxNumTransferEntries, so there is some wasted space for those size 166 // classes. 167 TCEntry tc_slots_[kMaxNumTransferEntries]; 168 169 // Number of currently used cached entries in tc_slots_. This variable is 170 // updated under a lock but can be read without one. 171 int32_t used_slots_; 172 // The current number of slots for this size class. This is an 173 // adaptive value that is increased if there is lots of traffic 174 // on a given size class. 175 int32_t cache_size_; 176 // Maximum size of the cache for a given size class. 177 int32_t max_cache_size_; 178 }; 179 180 // Pads each CentralCache object to multiple of 64 bytes. Since some 181 // compilers (such as MSVC) don't like it when the padding is 0, I use 182 // template specialization to remove the padding entirely when 183 // sizeof(CentralFreeList) is a multiple of 64. 184 template<int kFreeListSizeMod64> 185 class CentralFreeListPaddedTo : public CentralFreeList { 186 private: 187 char pad_[64 - kFreeListSizeMod64]; 188 }; 189 190 template<> 191 class CentralFreeListPaddedTo<0> : public CentralFreeList { 192 }; 193 194 class CentralFreeListPadded : public CentralFreeListPaddedTo< 195 sizeof(CentralFreeList) % 64> { 196 }; 197 198 } // namespace tcmalloc 199 200 #endif // TCMALLOC_CENTRAL_FREELIST_H_ 201