1 /* 2 * central_freelist.h 3 * Avida 4 * 5 * Added by David on 10/14/09. 6 * Copyright 2009-2011 Michigan State University. All rights reserved. 7 * 8 * 9 * This file is part of Avida. 10 * 11 * Avida is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License 12 * as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. 13 * 14 * Avida is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 16 * 17 * You should have received a copy of the GNU Lesser General Public License along with Avida. 18 * If not, see <http://www.gnu.org/licenses/>. 19 * 20 */ 21 22 // Copyright (c) 2008, Google Inc. 23 // All rights reserved. 24 // 25 // Redistribution and use in source and binary forms, with or without 26 // modification, are permitted provided that the following conditions are 27 // met: 28 // 29 // * Redistributions of source code must retain the above copyright 30 // notice, this list of conditions and the following disclaimer. 31 // * Redistributions in binary form must reproduce the above 32 // copyright notice, this list of conditions and the following disclaimer 33 // in the documentation and/or other materials provided with the 34 // distribution. 35 // * Neither the name of Google Inc. nor the names of its 36 // contributors may be used to endorse or promote products derived from 37 // this software without specific prior written permission. 38 // 39 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 40 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 41 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 42 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 43 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 44 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 45 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 46 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 47 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 48 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 49 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 50 51 // --- 52 // Author: Sanjay Ghemawat <opensource@google.com> 53 54 #ifndef TCMALLOC_CENTRAL_FREELIST_H_ 55 #define TCMALLOC_CENTRAL_FREELIST_H_ 56 57 #include "tcmalloc-platform.h" 58 #include "thread_annotations.h" 59 #include "spinlock.h" 60 #include "common.h" 61 #include "span.h" 62 63 namespace tcmalloc { 64 65 // Data kept per size-class in central cache. 66 class CentralFreeList 67 { 68 public: 69 void Init(size_t cl); 70 71 // These methods all do internal locking. 72 73 // Insert the specified range into the central freelist. N is the number of 74 // elements in the range. RemoveRange() is the opposite operation. 75 void InsertRange(void *start, void *end, int N); 76 77 // Returns the actual number of fetched elements and sets *start and *end. 78 int RemoveRange(void **start, void **end, int N); 79 80 // Returns the number of free objects in cache. length()81 int length() { 82 SpinLockHolder h(&lock_); 83 return counter_; 84 } 85 86 // Returns the number of free objects in the transfer cache. 87 int tc_length(); 88 89 private: 90 // TransferCache is used to cache transfers of 91 // sizemap.num_objects_to_move(size_class) back and forth between 92 // thread caches and the central cache for a given size class. 93 struct TCEntry { 94 void *head; // Head of chain of objects. 95 void *tail; // Tail of chain of objects. 96 }; 97 98 // A central cache freelist can have anywhere from 0 to kNumTransferEntries 99 // slots to put link list chains into. To keep memory usage bounded the total 100 // number of TCEntries across size classes is fixed. Currently each size 101 // class is initially given one TCEntry which also means that the maximum any 102 // one class can have is kNumClasses. 103 static const int kNumTransferEntries = kNumClasses; 104 105 // REQUIRES: lock_ is held 106 // Remove object from cache and return. 107 // Return NULL if no free entries in cache. 108 void* FetchFromSpans() EXCLUSIVE_LOCKS_REQUIRED(lock_); 109 110 // REQUIRES: lock_ is held 111 // Remove object from cache and return. Fetches 112 // from pageheap if cache is empty. Only returns 113 // NULL on allocation failure. 114 void* FetchFromSpansSafe() EXCLUSIVE_LOCKS_REQUIRED(lock_); 115 116 // REQUIRES: lock_ is held 117 // Release a linked list of objects to spans. 118 // May temporarily release lock_. 119 void ReleaseListToSpans(void *start) EXCLUSIVE_LOCKS_REQUIRED(lock_); 120 121 // REQUIRES: lock_ is held 122 // Release an object to spans. 123 // May temporarily release lock_. 124 void ReleaseToSpans(void* object) EXCLUSIVE_LOCKS_REQUIRED(lock_); 125 126 // REQUIRES: lock_ is held 127 // Populate cache by fetching from the page heap. 128 // May temporarily release lock_. 129 void Populate() EXCLUSIVE_LOCKS_REQUIRED(lock_); 130 131 // REQUIRES: lock is held. 132 // Tries to make room for a TCEntry. If the cache is full it will try to 133 // expand it at the cost of some other cache size. Return false if there is 134 // no space. 135 bool MakeCacheSpace() EXCLUSIVE_LOCKS_REQUIRED(lock_); 136 137 // REQUIRES: lock_ for locked_size_class is held. 138 // Picks a "random" size class to steal TCEntry slot from. In reality it 139 // just iterates over the sizeclasses but does so without taking a lock. 140 // Returns true on success. 141 // May temporarily lock a "random" size class. 142 static bool EvictRandomSizeClass(int locked_size_class, bool force); 143 144 // REQUIRES: lock_ is *not* held. 145 // Tries to shrink the Cache. If force is true it will relase objects to 146 // spans if it allows it to shrink the cache. Return false if it failed to 147 // shrink the cache. Decrements cache_size_ on succeess. 148 // May temporarily take lock_. If it takes lock_, the locked_size_class 149 // lock is released to keep the thread from holding two size class locks 150 // concurrently which could lead to a deadlock. 151 bool ShrinkCache(int locked_size_class, bool force) LOCKS_EXCLUDED(lock_); 152 153 // This lock protects all the data members. cached_entries and cache_size_ 154 // may be looked at without holding the lock. 155 SpinLock lock_; 156 157 // We keep linked lists of empty and non-empty spans. 158 size_t size_class_; // My size class 159 Span empty_; // Dummy header for list of empty spans 160 Span nonempty_; // Dummy header for list of non-empty spans 161 size_t counter_; // Number of free objects in cache entry 162 163 // Here we reserve space for TCEntry cache slots. Since one size class can 164 // end up getting all the TCEntries quota in the system we just preallocate 165 // sufficient number of entries here. 166 TCEntry tc_slots_[kNumTransferEntries]; 167 168 // Number of currently used cached entries in tc_slots_. This variable is 169 // updated under a lock but can be read without one. 170 int32_t used_slots_; 171 // The current number of slots for this size class. This is an 172 // adaptive value that is increased if there is lots of traffic 173 // on a given size class. 174 int32_t cache_size_; 175 }; 176 177 // Pads each CentralCache object to multiple of 64 bytes. Since some 178 // compilers (such as MSVC) don't like it when the padding is 0, I use 179 // template specialization to remove the padding entirely when 180 // sizeof(CentralFreeList) is a multiple of 64. 181 template<int kFreeListSizeMod64> 182 class CentralFreeListPaddedTo : public CentralFreeList 183 { 184 private: 185 char pad_[64 - kFreeListSizeMod64]; 186 }; 187 188 template<> class CentralFreeListPaddedTo<0> : public CentralFreeList { ; }; 189 190 class CentralFreeListPadded : public CentralFreeListPaddedTo<sizeof(CentralFreeList) % 64> { ; }; 191 192 } // namespace tcmalloc 193 194 #endif // TCMALLOC_CENTRAL_FREELIST_H_ 195