/* * Copyright (c) 2011 Apple Inc. All rights reserved. * * @APPLE_APACHE_LICENSE_HEADER_START@ * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. * * @APPLE_APACHE_LICENSE_HEADER_END@ */ /* Admin.h Automatic Garbage Collection Copyright (c) 2004-2011 Apple Inc. All rights reserved. */ #pragma once #ifndef __AUTO_ADMIN__ #define __AUTO_ADMIN__ #include "Bitmap.h" #include "Configuration.h" #include "Definitions.h" #include "AllocationCache.h" #include "Range.h" #include "Statistics.h" #include "auto_impl_utilities.h" namespace Auto { // Forward declarations // class Region; class Subzone; class Zone; class Thread; //----- Admin -----// class Admin { private: Zone *_zone; // managing zone usword_t _quantum_log2; // ilog2 of the quantum used in this admin AllocationCache _cache; // free lists, one for each quanta size, slot 0 is for large clumps Subzone *_active_subzone; // subzone with unused memory Subzone *_purgeable_subzones; // subzones that contain allocation_count() < allocation_limit(), to be considered when active subzone is exhausted. spin_lock_t _admin_lock; // protects free list, subzone data. usword_t _freelist_search_cap; // highest nonempty freelist index (excluding big chunk list), or 0 if all are empty usword_t _layout; // either AUTO_MEMORY_SCANNED or AUTO_MEMORY_UNSCANNED PtrIntHashMap _retains; // STL hash map of retain counts, protected by _admin_lock // // batch_allocate_from_cache_no_lock // // helper function for batch allocate. performs a batch allocation from a specific free list unsigned batch_allocate_from_freelist_slot_no_lock(usword_t cache_slot, usword_t quantum_size, const bool clear, void **results, unsigned num_requested); // // batch_allocate_from_subzone_no_lock // // helper function for batch allocate. performs a batch allocation from unused/purged space in a specific subzone unsigned batch_allocate_from_subzone_no_lock(Subzone *subzone, usword_t requested_size, const bool clear, void **results, unsigned num_requested); // // activate_purged_subzone // // try to reuse a subzone from the purgeable list. only choose a subzone with enough space to make it worth reusing. // void activate_purged_subzone(); // // visit_purgeable_nodes // // Visits all free list nodes that exceed 1 page in size, and purgeable subzones. // template <typename PurgeVisitor> void visit_purgeable_nodes(PurgeVisitor &visitor); public: // // Accessors // Zone *zone() const { return _zone; } usword_t quantum_log2() const { return _quantum_log2; } spin_lock_t *lock() { return &_admin_lock; } PtrIntHashMap &retains() { return _retains; } // // is_small // // Return true if it is a small admin. // inline bool is_small() const { return _quantum_log2 == allocate_quantum_small_log2; } // // is_medium // // Return true if it is a medium admin. // inline bool is_medium() const { return _quantum_log2 == allocate_quantum_medium_log2; } // // layout // // Returns AUTO_MEMORY_SCANNED or AUTO_MEMORY_UNSCANNED. // inline const usword_t layout() const { return _layout; } // // quantum_count // // Returns a number of quantum for a given size. // inline const usword_t quantum_count(const size_t size) const { return partition2(size, _quantum_log2); } // // unused_count // // Returns a number of quantum for a given size. // usword_t unused_count(); // // active_subzone // // Returns the most recently added subzone // inline Subzone *active_subzone() { return _active_subzone; } // // set_active_subzone // // Remember the most recently added subzone. This holds never used space. // inline void set_active_subzone(Subzone *sz) { _active_subzone = sz; } // // cache_slot // // Return the cache slot a free size resides. inline usword_t cache_slot(usword_t size) const { usword_t n = quantum_count(size); return n < AllocationCache::cache_size ? n : 0; } // // initialize // // Set up the admin for initial use. // void initialize(Zone *zone, const usword_t quantum_log2, const usword_t layout); // // free_space() // // Sums the free lists. // usword_t free_space(); // // purgeable_free_space() // // Returns how much free list space could be recovered by purge_free_space(). // usword_t purgeable_free_space(); usword_t purgeable_free_space_no_lock(); // // purge_free_space() // // Relinquish free space pages to the system where possible. // usword_t purge_free_space(); usword_t purge_free_space_no_lock(); // // empty_space() // // Returns the size of the space that has yet to be allocated. // usword_t empty_space(); // // test_freelist_integrity // // Returns true if the free list seems to be okay. // bool test_freelist_integrity(); // // test_node_integrity // // Returns true if the free list node seems to be okay. // bool test_node_integrity(FreeListNode *node); // // find_allocation // // Find the next available quanta for the allocation. Returns NULL if none found. // Allocate otherwise. // void *find_allocation(Thread &thread, usword_t &size, const usword_t layout, const bool refcount_is_one, bool &is_local); // // The following methods are used by compaction. // // // lowest_available_list // // Searches the heads of all free lists for a node with size >= n, and returns the list with the lowest head. // FreeList *lowest_available_list(usword_t n); // // allocate_lower_block_no_lock // // Allocates a block of the same size and layout of the block identified by (subzone, q, block_address), at a lower heap address. // If no lower block can be found, returns block_address. // void *allocate_lower_block_no_lock(Subzone *subzone, usword_t q, void *block_address); // // allocate_different_block_no_lock // // Allocates a block of the same size and layout of the block identified by (subzone, q, block_address), at a different heap address. // If no other block can be found, returns block_address. Used by AUTO_COMPACTION_SCRAMBLE mode. // void *allocate_different_block_no_lock(Subzone *subzone, usword_t q, void *block_address); // // allocate_destination_block_no_lock // // Allocates a block of the same size and layout of the block identified by (subzone, q, block_address), at a different heap address. // Calls either allocate_lower_block_no_lock or allocate_different_block_no_lock, depending on the compaction mode. // void *allocate_destination_block_no_lock(Subzone *subzone, usword_t q, void *block_address); // // thread_cache_allocate // // If per-thread cache available, use it, otherwise fill it and use it if possible, otherwise return NULL // void *thread_cache_allocate(Thread &thread, usword_t &size, const usword_t layout, const bool refcount_is_one, bool &is_local); // // batch_allocate // // Allocate many blocks. Returns the count of blocks allocated. // 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); // // deallocate // // Mark address as available. // Currently, this relinks it onto the free lists & clears the side table data. // void deallocate(Subzone *subzone, usword_t q, void *address); // // deallocate_no_lock // // Mark address as available. // Currently, this relinks it onto the free lists & clears the side table data. // Unlike vanilla deallocate (above), this assumes that the admin lock is already held. // void deallocate_no_lock(Subzone *subzone, usword_t q, void *address); // // mark_cached // // Set tables with information for cached allocation, one on a per-thread list // void mark_cached(Subzone *subzone, usword_t q, const usword_t n); void mark_cached_range(void *address, const usword_t n); // push_node // // Pushes a new node on to the specified FreeList. // Also tracks the range of active FreeList entries. // void push_node(usword_t index, void *address, usword_t size); // append_node // // Appends a new node on to the tail of the appropriate FreeList. // Also tracks the range of active FreeList entries. // void append_node(FreeListNode *node); // // insert_node // // Inserts a new node on to the specified FreeList (keeping it sorted). // Also tracks the range of active FreeList entries. // void insert_node(usword_t index, void *address, usword_t size); // // mark_allocated // // Set tables with information for new allocation. // void mark_allocated(void *address, const usword_t n, const usword_t layout, const bool refcount_is_one, const bool is_local); // // reset_free_list // // Clears all nodes off of the free lists. Nodes are simply dropped. // void reset_free_list() { for (usword_t i=0; i<AllocationCache::cache_size; i++) { _cache[i].reset(); } _freelist_search_cap = 0; // indicate nothing on the free lists } private: // // pop_node // // Pops a node from the specified FreeList. Also // performs node consistency checks. // FreeListNode *pop_node(usword_t index); // // find_allocation_no_lock // // find a block of suitable size (for use on the per-thread list) // void *find_allocation_no_lock(usword_t n); }; }; #endif // __AUTO_ADMIN__