1/* 2 * Copyright (c) 2011 Apple Inc. All rights reserved. 3 * 4 * @APPLE_APACHE_LICENSE_HEADER_START@ 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 * 18 * @APPLE_APACHE_LICENSE_HEADER_END@ 19 */ 20/* 21 Admin.h 22 Automatic Garbage Collection 23 Copyright (c) 2004-2011 Apple Inc. All rights reserved. 24 */ 25 26#pragma once 27#ifndef __AUTO_ADMIN__ 28#define __AUTO_ADMIN__ 29 30#include "Bitmap.h" 31#include "Configuration.h" 32#include "Definitions.h" 33#include "AllocationCache.h" 34#include "Range.h" 35#include "Statistics.h" 36#include "auto_impl_utilities.h" 37 38namespace Auto { 39 40 // Forward declarations 41 // 42 class Region; 43 class Subzone; 44 class Zone; 45 class Thread; 46 47 48 //----- Admin -----// 49 50 class Admin { 51 52 private: 53 54 Zone *_zone; // managing zone 55 usword_t _quantum_log2; // ilog2 of the quantum used in this admin 56 AllocationCache _cache; // free lists, one for each quanta size, slot 0 is for large clumps 57 Subzone *_active_subzone; // subzone with unused memory 58 Subzone *_purgeable_subzones; // subzones that contain allocation_count() < allocation_limit(), to be considered when active subzone is exhausted. 59 spin_lock_t _admin_lock; // protects free list, subzone data. 60 usword_t _freelist_search_cap; // highest nonempty freelist index (excluding big chunk list), or 0 if all are empty 61 usword_t _layout; // either AUTO_MEMORY_SCANNED or AUTO_MEMORY_UNSCANNED 62 PtrIntHashMap _retains; // STL hash map of retain counts, protected by _admin_lock 63 64 // 65 // batch_allocate_from_cache_no_lock 66 // 67 // helper function for batch allocate. performs a batch allocation from a specific free list 68 unsigned batch_allocate_from_freelist_slot_no_lock(usword_t cache_slot, usword_t quantum_size, const bool clear, void **results, unsigned num_requested); 69 70 // 71 // batch_allocate_from_subzone_no_lock 72 // 73 // helper function for batch allocate. performs a batch allocation from unused/purged space in a specific subzone 74 unsigned batch_allocate_from_subzone_no_lock(Subzone *subzone, usword_t requested_size, const bool clear, void **results, unsigned num_requested); 75 76 // 77 // activate_purged_subzone 78 // 79 // try to reuse a subzone from the purgeable list. only choose a subzone with enough space to make it worth reusing. 80 // 81 void activate_purged_subzone(); 82 83 // 84 // visit_purgeable_nodes 85 // 86 // Visits all free list nodes that exceed 1 page in size, and purgeable subzones. 87 // 88 template <typename PurgeVisitor> void visit_purgeable_nodes(PurgeVisitor &visitor); 89 90 public: 91 92 // 93 // Accessors 94 // 95 Zone *zone() const { return _zone; } 96 usword_t quantum_log2() const { return _quantum_log2; } 97 spin_lock_t *lock() { return &_admin_lock; } 98 PtrIntHashMap &retains() { return _retains; } 99 100 // 101 // is_small 102 // 103 // Return true if it is a small admin. 104 // 105 inline bool is_small() const { return _quantum_log2 == allocate_quantum_small_log2; } 106 107 108 // 109 // is_medium 110 // 111 // Return true if it is a medium admin. 112 // 113 inline bool is_medium() const { return _quantum_log2 == allocate_quantum_medium_log2; } 114 115 116 // 117 // layout 118 // 119 // Returns AUTO_MEMORY_SCANNED or AUTO_MEMORY_UNSCANNED. 120 // 121 inline const usword_t layout() const { return _layout; } 122 123 // 124 // quantum_count 125 // 126 // Returns a number of quantum for a given size. 127 // 128 inline const usword_t quantum_count(const size_t size) const { 129 return partition2(size, _quantum_log2); 130 } 131 132 133 // 134 // unused_count 135 // 136 // Returns a number of quantum for a given size. 137 // 138 usword_t unused_count(); 139 140 141 // 142 // active_subzone 143 // 144 // Returns the most recently added subzone 145 // 146 inline Subzone *active_subzone() { return _active_subzone; } 147 148 149 // 150 // set_active_subzone 151 // 152 // Remember the most recently added subzone. This holds never used space. 153 // 154 inline void set_active_subzone(Subzone *sz) { _active_subzone = sz; } 155 156 157 // 158 // cache_slot 159 // 160 // Return the cache slot a free size resides. 161 inline usword_t cache_slot(usword_t size) const { 162 usword_t n = quantum_count(size); 163 return n < AllocationCache::cache_size ? n : 0; 164 } 165 166 167 // 168 // initialize 169 // 170 // Set up the admin for initial use. 171 // 172 void initialize(Zone *zone, const usword_t quantum_log2, const usword_t layout); 173 174 175 // 176 // free_space() 177 // 178 // Sums the free lists. 179 // 180 usword_t free_space(); 181 182 // 183 // purgeable_free_space() 184 // 185 // Returns how much free list space could be recovered by purge_free_space(). 186 // 187 usword_t purgeable_free_space(); 188 usword_t purgeable_free_space_no_lock(); 189 190 // 191 // purge_free_space() 192 // 193 // Relinquish free space pages to the system where possible. 194 // 195 usword_t purge_free_space(); 196 usword_t purge_free_space_no_lock(); 197 198 // 199 // empty_space() 200 // 201 // Returns the size of the space that has yet to be allocated. 202 // 203 usword_t empty_space(); 204 205 // 206 // test_freelist_integrity 207 // 208 // Returns true if the free list seems to be okay. 209 // 210 bool test_freelist_integrity(); 211 212 // 213 // test_node_integrity 214 // 215 // Returns true if the free list node seems to be okay. 216 // 217 bool test_node_integrity(FreeListNode *node); 218 219 // 220 // find_allocation 221 // 222 // Find the next available quanta for the allocation. Returns NULL if none found. 223 // Allocate otherwise. 224 // 225 void *find_allocation(Thread &thread, usword_t &size, const usword_t layout, const bool refcount_is_one, bool &is_local); 226 227 228 // 229 // The following methods are used by compaction. 230 // 231 232 // 233 // lowest_available_list 234 // 235 // Searches the heads of all free lists for a node with size >= n, and returns the list with the lowest head. 236 // 237 FreeList *lowest_available_list(usword_t n); 238 239 // 240 // allocate_lower_block_no_lock 241 // 242 // Allocates a block of the same size and layout of the block identified by (subzone, q, block_address), at a lower heap address. 243 // If no lower block can be found, returns block_address. 244 // 245 void *allocate_lower_block_no_lock(Subzone *subzone, usword_t q, void *block_address); 246 247 // 248 // allocate_different_block_no_lock 249 // 250 // Allocates a block of the same size and layout of the block identified by (subzone, q, block_address), at a different heap address. 251 // If no other block can be found, returns block_address. Used by AUTO_COMPACTION_SCRAMBLE mode. 252 // 253 void *allocate_different_block_no_lock(Subzone *subzone, usword_t q, void *block_address); 254 255 256 // 257 // allocate_destination_block_no_lock 258 // 259 // Allocates a block of the same size and layout of the block identified by (subzone, q, block_address), at a different heap address. 260 // Calls either allocate_lower_block_no_lock or allocate_different_block_no_lock, depending on the compaction mode. 261 // 262 void *allocate_destination_block_no_lock(Subzone *subzone, usword_t q, void *block_address); 263 264 // 265 // thread_cache_allocate 266 // 267 // If per-thread cache available, use it, otherwise fill it and use it if possible, otherwise return NULL 268 // 269 void *thread_cache_allocate(Thread &thread, usword_t &size, const usword_t layout, const bool refcount_is_one, bool &is_local); 270 271 // 272 // batch_allocate 273 // 274 // Allocate many blocks. Returns the count of blocks allocated. 275 // 276 unsigned batch_allocate(Thread &thread, size_t &size, const usword_t layout, const bool refcount_is_one, const bool clear, void **results, unsigned num_requested); 277 278 // 279 // deallocate 280 // 281 // Mark address as available. 282 // Currently, this relinks it onto the free lists & clears the side table data. 283 // 284 void deallocate(Subzone *subzone, usword_t q, void *address); 285 286 // 287 // deallocate_no_lock 288 // 289 // Mark address as available. 290 // Currently, this relinks it onto the free lists & clears the side table data. 291 // Unlike vanilla deallocate (above), this assumes that the admin lock is already held. 292 // 293 void deallocate_no_lock(Subzone *subzone, usword_t q, void *address); 294 295 // 296 // mark_cached 297 // 298 // Set tables with information for cached allocation, one on a per-thread list 299 // 300 void mark_cached(Subzone *subzone, usword_t q, const usword_t n); 301 void mark_cached_range(void *address, const usword_t n); 302 303 // push_node 304 // 305 // Pushes a new node on to the specified FreeList. 306 // Also tracks the range of active FreeList entries. 307 // 308 void push_node(usword_t index, void *address, usword_t size); 309 310 // append_node 311 // 312 // Appends a new node on to the tail of the appropriate FreeList. 313 // Also tracks the range of active FreeList entries. 314 // 315 void append_node(FreeListNode *node); 316 317 // 318 // insert_node 319 // 320 // Inserts a new node on to the specified FreeList (keeping it sorted). 321 // Also tracks the range of active FreeList entries. 322 // 323 void insert_node(usword_t index, void *address, usword_t size); 324 325 // 326 // mark_allocated 327 // 328 // Set tables with information for new allocation. 329 // 330 void mark_allocated(void *address, const usword_t n, const usword_t layout, const bool refcount_is_one, const bool is_local); 331 332 // 333 // reset_free_list 334 // 335 // Clears all nodes off of the free lists. Nodes are simply dropped. 336 // 337 void reset_free_list() { 338 for (usword_t i=0; i<AllocationCache::cache_size; i++) { 339 _cache[i].reset(); 340 } 341 _freelist_search_cap = 0; // indicate nothing on the free lists 342 } 343 344 private: 345 // 346 // pop_node 347 // 348 // Pops a node from the specified FreeList. Also 349 // performs node consistency checks. 350 // 351 FreeListNode *pop_node(usword_t index); 352 353 354 // 355 // find_allocation_no_lock 356 // 357 // find a block of suitable size (for use on the per-thread list) 358 // 359 void *find_allocation_no_lock(usword_t n); 360 }; 361 362}; 363 364 365#endif // __AUTO_ADMIN__ 366