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#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 46namespace tcmalloc { 47 48// Data kept per size-class in central cache. 49class 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. 184template<int kFreeListSizeMod64> 185class CentralFreeListPaddedTo : public CentralFreeList { 186 private: 187 char pad_[64 - kFreeListSizeMod64]; 188}; 189 190template<> 191class CentralFreeListPaddedTo<0> : public CentralFreeList { 192}; 193 194class CentralFreeListPadded : public CentralFreeListPaddedTo< 195 sizeof(CentralFreeList) % 64> { 196}; 197 198} // namespace tcmalloc 199 200#endif // TCMALLOC_CENTRAL_FREELIST_H_ 201