Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2013 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | #ifndef ART_RUNTIME_GC_ALLOCATOR_ROSALLOC_H_ |
| 18 | #define ART_RUNTIME_GC_ALLOCATOR_ROSALLOC_H_ |
| 19 | |
| 20 | #include <set> |
| 21 | #include <stdint.h> |
| 22 | #include <stdlib.h> |
| 23 | #include <string> |
| 24 | #include <sys/mman.h> |
| 25 | #include <vector> |
| 26 | |
| 27 | #include "base/mutex.h" |
| 28 | #include "base/logging.h" |
| 29 | #include "globals.h" |
Hiroshi Yamauchi | 26d69ff | 2014-02-27 11:27:10 -0800 | [diff] [blame] | 30 | #include "mem_map.h" |
| 31 | #include "UniquePtr.h" |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 32 | #include "utils.h" |
| 33 | |
Ian Rogers | 5fcfa7d | 2014-05-15 11:43:06 -0700 | [diff] [blame] | 34 | // Ensure we have an unordered_set until we have worked out C++ library issues. |
| 35 | #ifdef ART_WITH_STLPORT |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 36 | #include <hash_set> |
Ian Rogers | 5fcfa7d | 2014-05-15 11:43:06 -0700 | [diff] [blame] | 37 | template <class V, class H, class P> |
| 38 | class unordered_set : public std::hash_set<V, H, P> {}; |
| 39 | #else // ART_WITH_STLPORT |
| 40 | // TODO: avoid the use of using in a header file. |
| 41 | #include <unordered_set> |
| 42 | using std::unordered_set; |
| 43 | #endif // ART_WITH_STLPORT |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 44 | |
| 45 | namespace art { |
| 46 | namespace gc { |
| 47 | namespace allocator { |
| 48 | |
Ian Rogers | 6fac447 | 2014-02-25 17:01:10 -0800 | [diff] [blame] | 49 | // A runs-of-slots memory allocator. |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 50 | class RosAlloc { |
| 51 | private: |
Ian Rogers | 6fac447 | 2014-02-25 17:01:10 -0800 | [diff] [blame] | 52 | // Represents a run of free pages. |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 53 | class FreePageRun { |
| 54 | public: |
| 55 | byte magic_num_; // The magic number used for debugging only. |
| 56 | |
| 57 | bool IsFree() const { |
| 58 | if (kIsDebugBuild) { |
| 59 | return magic_num_ == kMagicNumFree; |
| 60 | } |
| 61 | return true; |
| 62 | } |
| 63 | size_t ByteSize(RosAlloc* rosalloc) const EXCLUSIVE_LOCKS_REQUIRED(rosalloc->lock_) { |
| 64 | const byte* fpr_base = reinterpret_cast<const byte*>(this); |
| 65 | size_t pm_idx = rosalloc->ToPageMapIndex(fpr_base); |
| 66 | size_t byte_size = rosalloc->free_page_run_size_map_[pm_idx]; |
| 67 | DCHECK_GE(byte_size, static_cast<size_t>(0)); |
| 68 | DCHECK_EQ(byte_size % kPageSize, static_cast<size_t>(0)); |
| 69 | return byte_size; |
| 70 | } |
| 71 | void SetByteSize(RosAlloc* rosalloc, size_t byte_size) |
| 72 | EXCLUSIVE_LOCKS_REQUIRED(rosalloc->lock_) { |
| 73 | DCHECK_EQ(byte_size % kPageSize, static_cast<size_t>(0)); |
| 74 | byte* fpr_base = reinterpret_cast<byte*>(this); |
| 75 | size_t pm_idx = rosalloc->ToPageMapIndex(fpr_base); |
| 76 | rosalloc->free_page_run_size_map_[pm_idx] = byte_size; |
| 77 | } |
| 78 | void* Begin() { |
| 79 | return reinterpret_cast<void*>(this); |
| 80 | } |
| 81 | void* End(RosAlloc* rosalloc) EXCLUSIVE_LOCKS_REQUIRED(rosalloc->lock_) { |
| 82 | byte* fpr_base = reinterpret_cast<byte*>(this); |
| 83 | byte* end = fpr_base + ByteSize(rosalloc); |
| 84 | return end; |
| 85 | } |
Hiroshi Yamauchi | 573f7d2 | 2013-12-17 11:54:23 -0800 | [diff] [blame] | 86 | bool IsLargerThanPageReleaseThreshold(RosAlloc* rosalloc) |
| 87 | EXCLUSIVE_LOCKS_REQUIRED(rosalloc->lock_) { |
| 88 | return ByteSize(rosalloc) >= rosalloc->page_release_size_threshold_; |
| 89 | } |
| 90 | bool IsAtEndOfSpace(RosAlloc* rosalloc) |
| 91 | EXCLUSIVE_LOCKS_REQUIRED(rosalloc->lock_) { |
| 92 | return reinterpret_cast<byte*>(this) + ByteSize(rosalloc) == rosalloc->base_ + rosalloc->footprint_; |
| 93 | } |
| 94 | bool ShouldReleasePages(RosAlloc* rosalloc) EXCLUSIVE_LOCKS_REQUIRED(rosalloc->lock_) { |
| 95 | switch (rosalloc->page_release_mode_) { |
| 96 | case kPageReleaseModeNone: |
| 97 | return false; |
| 98 | case kPageReleaseModeEnd: |
| 99 | return IsAtEndOfSpace(rosalloc); |
| 100 | case kPageReleaseModeSize: |
| 101 | return IsLargerThanPageReleaseThreshold(rosalloc); |
| 102 | case kPageReleaseModeSizeAndEnd: |
| 103 | return IsLargerThanPageReleaseThreshold(rosalloc) && IsAtEndOfSpace(rosalloc); |
| 104 | case kPageReleaseModeAll: |
| 105 | return true; |
| 106 | default: |
| 107 | LOG(FATAL) << "Unexpected page release mode "; |
| 108 | return false; |
| 109 | } |
| 110 | } |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 111 | void ReleasePages(RosAlloc* rosalloc) EXCLUSIVE_LOCKS_REQUIRED(rosalloc->lock_) { |
Hiroshi Yamauchi | 573f7d2 | 2013-12-17 11:54:23 -0800 | [diff] [blame] | 112 | byte* start = reinterpret_cast<byte*>(this); |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 113 | size_t byte_size = ByteSize(rosalloc); |
| 114 | DCHECK_EQ(byte_size % kPageSize, static_cast<size_t>(0)); |
Hiroshi Yamauchi | 573f7d2 | 2013-12-17 11:54:23 -0800 | [diff] [blame] | 115 | bool release_pages = ShouldReleasePages(rosalloc); |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 116 | if (kIsDebugBuild) { |
| 117 | // Exclude the first page that stores the magic number. |
| 118 | DCHECK_GE(byte_size, static_cast<size_t>(kPageSize)); |
Hiroshi Yamauchi | 573f7d2 | 2013-12-17 11:54:23 -0800 | [diff] [blame] | 119 | start += kPageSize; |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 120 | byte_size -= kPageSize; |
| 121 | if (byte_size > 0) { |
Hiroshi Yamauchi | 573f7d2 | 2013-12-17 11:54:23 -0800 | [diff] [blame] | 122 | if (release_pages) { |
| 123 | madvise(start, byte_size, MADV_DONTNEED); |
| 124 | } |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 125 | } |
| 126 | } else { |
Hiroshi Yamauchi | 573f7d2 | 2013-12-17 11:54:23 -0800 | [diff] [blame] | 127 | if (release_pages) { |
| 128 | madvise(start, byte_size, MADV_DONTNEED); |
| 129 | } |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 130 | } |
| 131 | } |
| 132 | }; |
| 133 | |
| 134 | // Represents a run of memory slots of the same size. |
| 135 | // |
| 136 | // A run's memory layout: |
| 137 | // |
| 138 | // +-------------------+ |
| 139 | // | magic_num | |
| 140 | // +-------------------+ |
| 141 | // | size_bracket_idx | |
| 142 | // +-------------------+ |
| 143 | // | is_thread_local | |
| 144 | // +-------------------+ |
| 145 | // | to_be_bulk_freed | |
| 146 | // +-------------------+ |
Mathieu Chartier | 73d1e17 | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 147 | // | top_bitmap_idx | |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 148 | // +-------------------+ |
| 149 | // | | |
| 150 | // | alloc bit map | |
| 151 | // | | |
| 152 | // +-------------------+ |
| 153 | // | | |
| 154 | // | bulk free bit map | |
| 155 | // | | |
| 156 | // +-------------------+ |
| 157 | // | | |
| 158 | // | thread-local free | |
| 159 | // | bit map | |
| 160 | // | | |
| 161 | // +-------------------+ |
| 162 | // | padding due to | |
| 163 | // | alignment | |
| 164 | // +-------------------+ |
| 165 | // | slot 0 | |
| 166 | // +-------------------+ |
| 167 | // | slot 1 | |
| 168 | // +-------------------+ |
| 169 | // | slot 2 | |
| 170 | // +-------------------+ |
| 171 | // ... |
| 172 | // +-------------------+ |
| 173 | // | last slot | |
| 174 | // +-------------------+ |
| 175 | // |
| 176 | class Run { |
| 177 | public: |
Mathieu Chartier | 73d1e17 | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 178 | byte magic_num_; // The magic number used for debugging. |
| 179 | byte size_bracket_idx_; // The index of the size bracket of this run. |
| 180 | byte is_thread_local_; // True if this run is used as a thread-local run. |
| 181 | byte to_be_bulk_freed_; // Used within BulkFree() to flag a run that's involved with a bulk free. |
| 182 | uint32_t first_search_vec_idx_; // The index of the first bitmap vector which may contain an available slot. |
| 183 | uint32_t alloc_bit_map_[0]; // The bit map that allocates if each slot is in use. |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 184 | |
| 185 | // bulk_free_bit_map_[] : The bit map that is used for GC to |
| 186 | // temporarily mark the slots to free without using a lock. After |
| 187 | // all the slots to be freed in a run are marked, all those slots |
| 188 | // get freed in bulk with one locking per run, as opposed to one |
| 189 | // locking per slot to minimize the lock contention. This is used |
| 190 | // within BulkFree(). |
| 191 | |
| 192 | // thread_local_free_bit_map_[] : The bit map that is used for GC |
| 193 | // to temporarily mark the slots to free in a thread-local run |
| 194 | // without using a lock (without synchronizing the thread that |
| 195 | // owns the thread-local run.) When the thread-local run becomes |
| 196 | // full, the thread will check this bit map and update the |
| 197 | // allocation bit map of the run (that is, the slots get freed.) |
| 198 | |
| 199 | // Returns the byte size of the header except for the bit maps. |
| 200 | static size_t fixed_header_size() { |
| 201 | Run temp; |
| 202 | size_t size = reinterpret_cast<byte*>(&temp.alloc_bit_map_) - reinterpret_cast<byte*>(&temp); |
| 203 | DCHECK_EQ(size, static_cast<size_t>(8)); |
| 204 | return size; |
| 205 | } |
| 206 | // Returns the base address of the free bit map. |
Hiroshi Yamauchi | a4adbfd | 2014-02-04 18:12:17 -0800 | [diff] [blame] | 207 | uint32_t* BulkFreeBitMap() { |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 208 | return reinterpret_cast<uint32_t*>(reinterpret_cast<byte*>(this) + bulkFreeBitMapOffsets[size_bracket_idx_]); |
| 209 | } |
| 210 | // Returns the base address of the thread local free bit map. |
Hiroshi Yamauchi | a4adbfd | 2014-02-04 18:12:17 -0800 | [diff] [blame] | 211 | uint32_t* ThreadLocalFreeBitMap() { |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 212 | return reinterpret_cast<uint32_t*>(reinterpret_cast<byte*>(this) + threadLocalFreeBitMapOffsets[size_bracket_idx_]); |
| 213 | } |
| 214 | void* End() { |
| 215 | return reinterpret_cast<byte*>(this) + kPageSize * numOfPages[size_bracket_idx_]; |
| 216 | } |
Mathieu Chartier | 73d1e17 | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 217 | // Returns the number of bitmap words per run. |
| 218 | size_t NumberOfBitmapVectors() const { |
| 219 | return RoundUp(numOfSlots[size_bracket_idx_], 32) / 32; |
| 220 | } |
| 221 | void SetIsThreadLocal(bool is_thread_local) { |
| 222 | is_thread_local_ = is_thread_local ? 1 : 0; |
| 223 | } |
| 224 | bool IsThreadLocal() const { |
| 225 | return is_thread_local_ != 0; |
| 226 | } |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 227 | // Frees slots in the allocation bit map with regard to the |
| 228 | // thread-local free bit map. Used when a thread-local run becomes |
| 229 | // full. |
| 230 | bool MergeThreadLocalFreeBitMapToAllocBitMap(bool* is_all_free_after_out); |
| 231 | // Frees slots in the allocation bit map with regard to the bulk |
| 232 | // free bit map. Used in a bulk free. |
| 233 | void MergeBulkFreeBitMapIntoAllocBitMap(); |
| 234 | // Unions the slots to be freed in the free bit map into the |
| 235 | // thread-local free bit map. In a bulk free, as a two-step |
| 236 | // process, GC will first record all the slots to free in a run in |
| 237 | // the free bit map where it can write without a lock, and later |
| 238 | // acquire a lock once per run to union the bits of the free bit |
| 239 | // map to the thread-local free bit map. |
| 240 | void UnionBulkFreeBitMapToThreadLocalFreeBitMap(); |
| 241 | // Allocates a slot in a run. |
| 242 | void* AllocSlot(); |
| 243 | // Frees a slot in a run. This is used in a non-bulk free. |
| 244 | void FreeSlot(void* ptr); |
Mathieu Chartier | 73d1e17 | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 245 | // Marks the slots to free in the bulk free bit map. Returns the bracket size. |
| 246 | size_t MarkBulkFreeBitMap(void* ptr); |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 247 | // Marks the slots to free in the thread-local free bit map. |
| 248 | void MarkThreadLocalFreeBitMap(void* ptr); |
Mathieu Chartier | 73d1e17 | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 249 | // Last word mask, all of the bits in the last word which aren't valid slots are set to |
| 250 | // optimize allocation path. |
Andreas Gampe | 59e6760 | 2014-04-25 17:15:12 -0700 | [diff] [blame] | 251 | static uint32_t GetBitmapLastVectorMask(size_t num_slots, size_t num_vec); |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 252 | // Returns true if all the slots in the run are not in use. |
| 253 | bool IsAllFree(); |
| 254 | // Returns true if all the slots in the run are in use. |
| 255 | bool IsFull(); |
Hiroshi Yamauchi | a4adbfd | 2014-02-04 18:12:17 -0800 | [diff] [blame] | 256 | // Returns true if the bulk free bit map is clean. |
| 257 | bool IsBulkFreeBitmapClean(); |
| 258 | // Returns true if the thread local free bit map is clean. |
| 259 | bool IsThreadLocalFreeBitmapClean(); |
Mathieu Chartier | 73d1e17 | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 260 | // Set the alloc_bit_map_ bits for slots that are past the end of the run. |
| 261 | void SetAllocBitMapBitsForInvalidSlots(); |
| 262 | // Zero the run's data. |
| 263 | void ZeroData(); |
| 264 | // Zero the run's header. |
| 265 | void ZeroHeader(); |
| 266 | // Fill the alloc bitmap with 1s. |
| 267 | void FillAllocBitMap(); |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 268 | // Iterate over all the slots and apply the given function. |
| 269 | void InspectAllSlots(void (*handler)(void* start, void* end, size_t used_bytes, void* callback_arg), void* arg); |
| 270 | // Dump the run metadata for debugging. |
Hiroshi Yamauchi | a4adbfd | 2014-02-04 18:12:17 -0800 | [diff] [blame] | 271 | std::string Dump(); |
| 272 | // Verify for debugging. |
| 273 | void Verify(Thread* self, RosAlloc* rosalloc) |
| 274 | EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_) |
| 275 | EXCLUSIVE_LOCKS_REQUIRED(Locks::thread_list_lock_); |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 276 | |
| 277 | private: |
Mathieu Chartier | 73d1e17 | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 278 | // The common part of MarkFreeBitMap() and MarkThreadLocalFreeBitMap(). Returns the bracket |
| 279 | // size. |
| 280 | size_t MarkFreeBitMapShared(void* ptr, uint32_t* free_bit_map_base, const char* caller_name); |
Hiroshi Yamauchi | a4adbfd | 2014-02-04 18:12:17 -0800 | [diff] [blame] | 281 | // Turns the bit map into a string for debugging. |
| 282 | static std::string BitMapToStr(uint32_t* bit_map_base, size_t num_vec); |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 283 | }; |
| 284 | |
| 285 | // The magic number for a run. |
| 286 | static const byte kMagicNum = 42; |
| 287 | // The magic number for free pages. |
| 288 | static const byte kMagicNumFree = 43; |
| 289 | // The number of size brackets. Sync this with the length of Thread::rosalloc_runs_. |
| 290 | static const size_t kNumOfSizeBrackets = 34; |
| 291 | // The number of smaller size brackets that are 16 bytes apart. |
| 292 | static const size_t kNumOfQuantumSizeBrackets = 32; |
| 293 | // The sizes (the slot sizes, in bytes) of the size brackets. |
| 294 | static size_t bracketSizes[kNumOfSizeBrackets]; |
| 295 | // The numbers of pages that are used for runs for each size bracket. |
| 296 | static size_t numOfPages[kNumOfSizeBrackets]; |
| 297 | // The numbers of slots of the runs for each size bracket. |
| 298 | static size_t numOfSlots[kNumOfSizeBrackets]; |
| 299 | // The header sizes in bytes of the runs for each size bracket. |
| 300 | static size_t headerSizes[kNumOfSizeBrackets]; |
| 301 | // The byte offsets of the bulk free bit maps of the runs for each size bracket. |
| 302 | static size_t bulkFreeBitMapOffsets[kNumOfSizeBrackets]; |
| 303 | // The byte offsets of the thread-local free bit maps of the runs for each size bracket. |
| 304 | static size_t threadLocalFreeBitMapOffsets[kNumOfSizeBrackets]; |
| 305 | |
| 306 | // Initialize the run specs (the above arrays). |
| 307 | static void Initialize(); |
| 308 | static bool initialized_; |
| 309 | |
| 310 | // Returns the byte size of the bracket size from the index. |
| 311 | static size_t IndexToBracketSize(size_t idx) { |
| 312 | DCHECK(idx < kNumOfSizeBrackets); |
| 313 | return bracketSizes[idx]; |
| 314 | } |
| 315 | // Returns the index of the size bracket from the bracket size. |
| 316 | static size_t BracketSizeToIndex(size_t size) { |
| 317 | DCHECK(16 <= size && ((size < 1 * KB && size % 16 == 0) || size == 1 * KB || size == 2 * KB)); |
| 318 | size_t idx; |
| 319 | if (UNLIKELY(size == 1 * KB)) { |
| 320 | idx = kNumOfSizeBrackets - 2; |
| 321 | } else if (UNLIKELY(size == 2 * KB)) { |
| 322 | idx = kNumOfSizeBrackets - 1; |
| 323 | } else { |
| 324 | DCHECK(size < 1 * KB); |
| 325 | DCHECK_EQ(size % 16, static_cast<size_t>(0)); |
| 326 | idx = size / 16 - 1; |
| 327 | } |
| 328 | DCHECK(bracketSizes[idx] == size); |
| 329 | return idx; |
| 330 | } |
| 331 | // Rounds up the size up the nearest bracket size. |
| 332 | static size_t RoundToBracketSize(size_t size) { |
| 333 | DCHECK(size <= kLargeSizeThreshold); |
| 334 | if (LIKELY(size <= 512)) { |
| 335 | return RoundUp(size, 16); |
| 336 | } else if (512 < size && size <= 1 * KB) { |
| 337 | return 1 * KB; |
| 338 | } else { |
| 339 | DCHECK(1 * KB < size && size <= 2 * KB); |
| 340 | return 2 * KB; |
| 341 | } |
| 342 | } |
| 343 | // Returns the size bracket index from the byte size with rounding. |
| 344 | static size_t SizeToIndex(size_t size) { |
| 345 | DCHECK(size <= kLargeSizeThreshold); |
| 346 | if (LIKELY(size <= 512)) { |
| 347 | return RoundUp(size, 16) / 16 - 1; |
| 348 | } else if (512 < size && size <= 1 * KB) { |
| 349 | return kNumOfSizeBrackets - 2; |
| 350 | } else { |
| 351 | DCHECK(1 * KB < size && size <= 2 * KB); |
| 352 | return kNumOfSizeBrackets - 1; |
| 353 | } |
| 354 | } |
| 355 | // A combination of SizeToIndex() and RoundToBracketSize(). |
| 356 | static size_t SizeToIndexAndBracketSize(size_t size, size_t* bracket_size_out) { |
| 357 | DCHECK(size <= kLargeSizeThreshold); |
| 358 | if (LIKELY(size <= 512)) { |
| 359 | size_t bracket_size = RoundUp(size, 16); |
| 360 | *bracket_size_out = bracket_size; |
| 361 | size_t idx = bracket_size / 16 - 1; |
| 362 | DCHECK_EQ(bracket_size, IndexToBracketSize(idx)); |
| 363 | return idx; |
| 364 | } else if (512 < size && size <= 1 * KB) { |
| 365 | size_t bracket_size = 1024; |
| 366 | *bracket_size_out = bracket_size; |
| 367 | size_t idx = kNumOfSizeBrackets - 2; |
| 368 | DCHECK_EQ(bracket_size, IndexToBracketSize(idx)); |
| 369 | return idx; |
| 370 | } else { |
| 371 | DCHECK(1 * KB < size && size <= 2 * KB); |
| 372 | size_t bracket_size = 2048; |
| 373 | *bracket_size_out = bracket_size; |
| 374 | size_t idx = kNumOfSizeBrackets - 1; |
| 375 | DCHECK_EQ(bracket_size, IndexToBracketSize(idx)); |
| 376 | return idx; |
| 377 | } |
| 378 | } |
| 379 | // Returns the page map index from an address. Requires that the |
| 380 | // address is page size aligned. |
| 381 | size_t ToPageMapIndex(const void* addr) const { |
| 382 | DCHECK(base_ <= addr && addr < base_ + capacity_); |
| 383 | size_t byte_offset = reinterpret_cast<const byte*>(addr) - base_; |
| 384 | DCHECK_EQ(byte_offset % static_cast<size_t>(kPageSize), static_cast<size_t>(0)); |
| 385 | return byte_offset / kPageSize; |
| 386 | } |
| 387 | // Returns the page map index from an address with rounding. |
Mathieu Chartier | 73d1e17 | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 388 | size_t RoundDownToPageMapIndex(void* addr) const { |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 389 | DCHECK(base_ <= addr && addr < reinterpret_cast<byte*>(base_) + capacity_); |
| 390 | return (reinterpret_cast<uintptr_t>(addr) - reinterpret_cast<uintptr_t>(base_)) / kPageSize; |
| 391 | } |
| 392 | |
| 393 | // A memory allocation request larger than this size is treated as a large object and allocated |
| 394 | // at a page-granularity. |
| 395 | static const size_t kLargeSizeThreshold = 2048; |
| 396 | |
Hiroshi Yamauchi | 3c2856e | 2013-11-22 13:42:53 -0800 | [diff] [blame] | 397 | // If true, check that the returned memory is actually zero. |
| 398 | static constexpr bool kCheckZeroMemory = kIsDebugBuild; |
| 399 | |
| 400 | // If true, log verbose details of operations. |
| 401 | static constexpr bool kTraceRosAlloc = false; |
| 402 | |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 403 | struct hash_run { |
| 404 | size_t operator()(const RosAlloc::Run* r) const { |
| 405 | return reinterpret_cast<size_t>(r); |
| 406 | } |
| 407 | }; |
| 408 | |
| 409 | struct eq_run { |
| 410 | bool operator()(const RosAlloc::Run* r1, const RosAlloc::Run* r2) const { |
| 411 | return r1 == r2; |
| 412 | } |
| 413 | }; |
| 414 | |
Hiroshi Yamauchi | 573f7d2 | 2013-12-17 11:54:23 -0800 | [diff] [blame] | 415 | public: |
| 416 | // Different page release modes. |
| 417 | enum PageReleaseMode { |
| 418 | kPageReleaseModeNone, // Release no empty pages. |
| 419 | kPageReleaseModeEnd, // Release empty pages at the end of the space. |
| 420 | kPageReleaseModeSize, // Release empty pages that are larger than the threshold. |
| 421 | kPageReleaseModeSizeAndEnd, // Release empty pages that are larger than the threshold or |
| 422 | // at the end of the space. |
| 423 | kPageReleaseModeAll, // Release all empty pages. |
| 424 | }; |
| 425 | |
| 426 | // The default value for page_release_size_threshold_. |
| 427 | static constexpr size_t kDefaultPageReleaseSizeThreshold = 4 * MB; |
| 428 | |
Mathieu Chartier | 0651d41 | 2014-04-29 14:37:57 -0700 | [diff] [blame] | 429 | // We use thread-local runs for the size Brackets whose indexes |
| 430 | // are less than this index. We use shared (current) runs for the rest. |
| 431 | static const size_t kNumThreadLocalSizeBrackets = 11; |
| 432 | |
Hiroshi Yamauchi | 573f7d2 | 2013-12-17 11:54:23 -0800 | [diff] [blame] | 433 | private: |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 434 | // The base address of the memory region that's managed by this allocator. |
| 435 | byte* base_; |
| 436 | |
| 437 | // The footprint in bytes of the currently allocated portion of the |
| 438 | // memory region. |
| 439 | size_t footprint_; |
| 440 | |
| 441 | // The maximum footprint. The address, base_ + capacity_, indicates |
Hiroshi Yamauchi | 26d69ff | 2014-02-27 11:27:10 -0800 | [diff] [blame] | 442 | // the end of the memory region that's currently managed by this allocator. |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 443 | size_t capacity_; |
| 444 | |
Hiroshi Yamauchi | 26d69ff | 2014-02-27 11:27:10 -0800 | [diff] [blame] | 445 | // The maximum capacity. The address, base_ + max_capacity_, indicates |
| 446 | // the end of the memory region that's ever managed by this allocator. |
| 447 | size_t max_capacity_; |
| 448 | |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 449 | // The run sets that hold the runs whose slots are not all |
| 450 | // full. non_full_runs_[i] is guarded by size_bracket_locks_[i]. |
| 451 | std::set<Run*> non_full_runs_[kNumOfSizeBrackets]; |
| 452 | // The run sets that hold the runs whose slots are all full. This is |
| 453 | // debug only. full_runs_[i] is guarded by size_bracket_locks_[i]. |
Ian Rogers | 5fcfa7d | 2014-05-15 11:43:06 -0700 | [diff] [blame] | 454 | unordered_set<Run*, hash_run, eq_run> full_runs_[kNumOfSizeBrackets]; |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 455 | // The set of free pages. |
| 456 | std::set<FreePageRun*> free_page_runs_ GUARDED_BY(lock_); |
Mathieu Chartier | 73d1e17 | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 457 | // The dedicated full run, it is always full and shared by all threads when revoking happens. |
| 458 | // This is an optimization since enables us to avoid a null check for revoked runs. |
| 459 | static Run* dedicated_full_run_; |
| 460 | // Using size_t to ensure that it is at least word aligned. |
| 461 | static size_t dedicated_full_run_storage_[]; |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 462 | // The current runs where the allocations are first attempted for |
| 463 | // the size brackes that do not use thread-local |
| 464 | // runs. current_runs_[i] is guarded by size_bracket_locks_[i]. |
| 465 | Run* current_runs_[kNumOfSizeBrackets]; |
| 466 | // The mutexes, one per size bracket. |
| 467 | Mutex* size_bracket_locks_[kNumOfSizeBrackets]; |
Mathieu Chartier | 73d1e17 | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 468 | // Bracket lock names (since locks only have char* names). |
| 469 | std::string size_bracket_lock_names[kNumOfSizeBrackets]; |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 470 | // The types of page map entries. |
| 471 | enum { |
| 472 | kPageMapEmpty = 0, // Not allocated. |
| 473 | kPageMapRun = 1, // The beginning of a run. |
| 474 | kPageMapRunPart = 2, // The non-beginning part of a run. |
| 475 | kPageMapLargeObject = 3, // The beginning of a large object. |
| 476 | kPageMapLargeObjectPart = 4, // The non-beginning part of a large object. |
| 477 | }; |
| 478 | // The table that indicates what pages are currently used for. |
Hiroshi Yamauchi | 26d69ff | 2014-02-27 11:27:10 -0800 | [diff] [blame] | 479 | byte* page_map_; // No GUARDED_BY(lock_) for kReadPageMapEntryWithoutLockInBulkFree. |
| 480 | size_t page_map_size_; |
| 481 | size_t max_page_map_size_; |
| 482 | UniquePtr<MemMap> page_map_mem_map_; |
| 483 | |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 484 | // The table that indicates the size of free page runs. These sizes |
| 485 | // are stored here to avoid storing in the free page header and |
| 486 | // release backing pages. |
| 487 | std::vector<size_t> free_page_run_size_map_ GUARDED_BY(lock_); |
| 488 | // The global lock. Used to guard the page map, the free page set, |
| 489 | // and the footprint. |
| 490 | Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER; |
| 491 | // The reader-writer lock to allow one bulk free at a time while |
Hiroshi Yamauchi | 70f6004 | 2014-02-03 12:31:29 -0800 | [diff] [blame] | 492 | // allowing multiple individual frees at the same time. Also, this |
| 493 | // is used to avoid race conditions between BulkFree() and |
| 494 | // RevokeThreadLocalRuns() on the bulk free bitmaps. |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 495 | ReaderWriterMutex bulk_free_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER; |
| 496 | |
Hiroshi Yamauchi | 573f7d2 | 2013-12-17 11:54:23 -0800 | [diff] [blame] | 497 | // The page release mode. |
| 498 | const PageReleaseMode page_release_mode_; |
| 499 | // Under kPageReleaseModeSize(AndEnd), if the free page run size is |
| 500 | // greater than or equal to this value, release pages. |
| 501 | const size_t page_release_size_threshold_; |
| 502 | |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 503 | // The base address of the memory region that's managed by this allocator. |
| 504 | byte* Begin() { return base_; } |
| 505 | // The end address of the memory region that's managed by this allocator. |
| 506 | byte* End() { return base_ + capacity_; } |
| 507 | |
| 508 | // Page-granularity alloc/free |
| 509 | void* AllocPages(Thread* self, size_t num_pages, byte page_map_type) |
| 510 | EXCLUSIVE_LOCKS_REQUIRED(lock_); |
Mathieu Chartier | 73d1e17 | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 511 | // Returns how many bytes were freed. |
| 512 | size_t FreePages(Thread* self, void* ptr, bool already_zero) EXCLUSIVE_LOCKS_REQUIRED(lock_); |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 513 | |
| 514 | // Allocate/free a run slot. |
| 515 | void* AllocFromRun(Thread* self, size_t size, size_t* bytes_allocated) |
| 516 | LOCKS_EXCLUDED(lock_); |
Mathieu Chartier | 0651d41 | 2014-04-29 14:37:57 -0700 | [diff] [blame] | 517 | // Allocate/free a run slot without acquiring locks. |
| 518 | // TODO: EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_) |
| 519 | void* AllocFromRunThreadUnsafe(Thread* self, size_t size, size_t* bytes_allocated) |
| 520 | LOCKS_EXCLUDED(lock_); |
| 521 | void* AllocFromCurrentRunUnlocked(Thread* self, size_t idx); |
| 522 | |
Mathieu Chartier | 73d1e17 | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 523 | // Returns the bracket size. |
| 524 | size_t FreeFromRun(Thread* self, void* ptr, Run* run) |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 525 | LOCKS_EXCLUDED(lock_); |
| 526 | |
Mathieu Chartier | 73d1e17 | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 527 | // Used to allocate a new thread local run for a size bracket. |
| 528 | Run* AllocRun(Thread* self, size_t idx) LOCKS_EXCLUDED(lock_); |
| 529 | |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 530 | // Used to acquire a new/reused run for a size bracket. Used when a |
| 531 | // thread-local or current run gets full. |
| 532 | Run* RefillRun(Thread* self, size_t idx) LOCKS_EXCLUDED(lock_); |
| 533 | |
| 534 | // The internal of non-bulk Free(). |
Mathieu Chartier | 8585bad | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 535 | size_t FreeInternal(Thread* self, void* ptr) LOCKS_EXCLUDED(lock_); |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 536 | |
Hiroshi Yamauchi | 3c2856e | 2013-11-22 13:42:53 -0800 | [diff] [blame] | 537 | // Allocates large objects. |
| 538 | void* AllocLargeObject(Thread* self, size_t size, size_t* bytes_allocated) LOCKS_EXCLUDED(lock_); |
| 539 | |
Mathieu Chartier | 0651d41 | 2014-04-29 14:37:57 -0700 | [diff] [blame] | 540 | // Revoke a run by adding it to non_full_runs_ or freeing the pages. |
| 541 | void RevokeRun(Thread* self, size_t idx, Run* run); |
| 542 | |
| 543 | // Revoke the current runs which share an index with the thread local runs. |
| 544 | void RevokeThreadUnsafeCurrentRuns(); |
| 545 | |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 546 | public: |
Hiroshi Yamauchi | 26d69ff | 2014-02-27 11:27:10 -0800 | [diff] [blame] | 547 | RosAlloc(void* base, size_t capacity, size_t max_capacity, |
Hiroshi Yamauchi | 573f7d2 | 2013-12-17 11:54:23 -0800 | [diff] [blame] | 548 | PageReleaseMode page_release_mode, |
| 549 | size_t page_release_size_threshold = kDefaultPageReleaseSizeThreshold); |
Mathieu Chartier | 661974a | 2014-01-09 11:23:53 -0800 | [diff] [blame] | 550 | ~RosAlloc(); |
Mathieu Chartier | 0651d41 | 2014-04-29 14:37:57 -0700 | [diff] [blame] | 551 | // If kThreadUnsafe is true then the allocator may avoid acquiring some locks as an optimization. |
| 552 | // If used, this may cause race conditions if multiple threads are allocating at the same time. |
| 553 | template<bool kThreadSafe = true> |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 554 | void* Alloc(Thread* self, size_t size, size_t* bytes_allocated) |
| 555 | LOCKS_EXCLUDED(lock_); |
Mathieu Chartier | 8585bad | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 556 | size_t Free(Thread* self, void* ptr) |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 557 | LOCKS_EXCLUDED(bulk_free_lock_); |
Mathieu Chartier | 8585bad | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 558 | size_t BulkFree(Thread* self, void** ptrs, size_t num_ptrs) |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 559 | LOCKS_EXCLUDED(bulk_free_lock_); |
| 560 | // Returns the size of the allocated slot for a given allocated memory chunk. |
| 561 | size_t UsableSize(void* ptr); |
| 562 | // Returns the size of the allocated slot for a given size. |
| 563 | size_t UsableSize(size_t bytes) { |
| 564 | if (UNLIKELY(bytes > kLargeSizeThreshold)) { |
| 565 | return RoundUp(bytes, kPageSize); |
| 566 | } else { |
| 567 | return RoundToBracketSize(bytes); |
| 568 | } |
| 569 | } |
| 570 | // Try to reduce the current footprint by releasing the free page |
| 571 | // run at the end of the memory region, if any. |
| 572 | bool Trim(); |
| 573 | // Iterates over all the memory slots and apply the given function. |
| 574 | void InspectAll(void (*handler)(void* start, void* end, size_t used_bytes, void* callback_arg), |
| 575 | void* arg) |
| 576 | LOCKS_EXCLUDED(lock_); |
Hiroshi Yamauchi | d9a88de | 2014-04-07 13:52:31 -0700 | [diff] [blame] | 577 | // Release empty pages. |
| 578 | size_t ReleasePages() LOCKS_EXCLUDED(lock_); |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 579 | // Returns the current footprint. |
| 580 | size_t Footprint() LOCKS_EXCLUDED(lock_); |
| 581 | // Returns the current capacity, maximum footprint. |
| 582 | size_t FootprintLimit() LOCKS_EXCLUDED(lock_); |
| 583 | // Update the current capacity. |
| 584 | void SetFootprintLimit(size_t bytes) LOCKS_EXCLUDED(lock_); |
| 585 | // Releases the thread-local runs assigned to the given thread back to the common set of runs. |
| 586 | void RevokeThreadLocalRuns(Thread* thread); |
| 587 | // Releases the thread-local runs assigned to all the threads back to the common set of runs. |
| 588 | void RevokeAllThreadLocalRuns() LOCKS_EXCLUDED(Locks::thread_list_lock_); |
Hiroshi Yamauchi | c93c530 | 2014-03-20 16:15:37 -0700 | [diff] [blame] | 589 | // Assert the thread local runs of a thread are revoked. |
| 590 | void AssertThreadLocalRunsAreRevoked(Thread* thread); |
| 591 | // Assert all the thread local runs are revoked. |
| 592 | void AssertAllThreadLocalRunsAreRevoked() LOCKS_EXCLUDED(Locks::thread_list_lock_); |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 593 | // Dumps the page map for debugging. |
Hiroshi Yamauchi | a4adbfd | 2014-02-04 18:12:17 -0800 | [diff] [blame] | 594 | std::string DumpPageMap() EXCLUSIVE_LOCKS_REQUIRED(lock_); |
Mathieu Chartier | 73d1e17 | 2014-04-11 17:53:48 -0700 | [diff] [blame] | 595 | static Run* GetDedicatedFullRun() { |
| 596 | return dedicated_full_run_; |
| 597 | } |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 598 | |
| 599 | // Callbacks for InspectAll that will count the number of bytes |
| 600 | // allocated and objects allocated, respectively. |
| 601 | static void BytesAllocatedCallback(void* start, void* end, size_t used_bytes, void* arg); |
| 602 | static void ObjectsAllocatedCallback(void* start, void* end, size_t used_bytes, void* arg); |
Hiroshi Yamauchi | 573f7d2 | 2013-12-17 11:54:23 -0800 | [diff] [blame] | 603 | |
| 604 | bool DoesReleaseAllPages() const { |
| 605 | return page_release_mode_ == kPageReleaseModeAll; |
| 606 | } |
Hiroshi Yamauchi | a4adbfd | 2014-02-04 18:12:17 -0800 | [diff] [blame] | 607 | |
| 608 | // Verify for debugging. |
| 609 | void Verify() EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_); |
Hiroshi Yamauchi | cf58d4a | 2013-09-26 14:21:22 -0700 | [diff] [blame] | 610 | }; |
| 611 | |
| 612 | } // namespace allocator |
| 613 | } // namespace gc |
| 614 | } // namespace art |
| 615 | |
| 616 | #endif // ART_RUNTIME_GC_ALLOCATOR_ROSALLOC_H_ |