blob: 8557f1bcadacfa336cf2a1ce56de11844e47ae2d [file] [log] [blame]
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -07001/*
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 Yamauchi26d69ff2014-02-27 11:27:10 -080030#include "mem_map.h"
31#include "UniquePtr.h"
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -070032#include "utils.h"
33
Ian Rogers5fcfa7d2014-05-15 11:43:06 -070034// Ensure we have an unordered_set until we have worked out C++ library issues.
35#ifdef ART_WITH_STLPORT
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -070036#include <hash_set>
Ian Rogers5fcfa7d2014-05-15 11:43:06 -070037template <class V, class H, class P>
38class 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>
42using std::unordered_set;
43#endif // ART_WITH_STLPORT
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -070044
45namespace art {
46namespace gc {
47namespace allocator {
48
Ian Rogers6fac4472014-02-25 17:01:10 -080049// A runs-of-slots memory allocator.
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -070050class RosAlloc {
51 private:
Ian Rogers6fac4472014-02-25 17:01:10 -080052 // Represents a run of free pages.
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -070053 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 Yamauchi573f7d22013-12-17 11:54:23 -080086 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 Yamauchicf58d4a2013-09-26 14:21:22 -0700111 void ReleasePages(RosAlloc* rosalloc) EXCLUSIVE_LOCKS_REQUIRED(rosalloc->lock_) {
Hiroshi Yamauchi573f7d22013-12-17 11:54:23 -0800112 byte* start = reinterpret_cast<byte*>(this);
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700113 size_t byte_size = ByteSize(rosalloc);
114 DCHECK_EQ(byte_size % kPageSize, static_cast<size_t>(0));
Hiroshi Yamauchi573f7d22013-12-17 11:54:23 -0800115 bool release_pages = ShouldReleasePages(rosalloc);
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700116 if (kIsDebugBuild) {
117 // Exclude the first page that stores the magic number.
118 DCHECK_GE(byte_size, static_cast<size_t>(kPageSize));
Hiroshi Yamauchi573f7d22013-12-17 11:54:23 -0800119 start += kPageSize;
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700120 byte_size -= kPageSize;
121 if (byte_size > 0) {
Hiroshi Yamauchi573f7d22013-12-17 11:54:23 -0800122 if (release_pages) {
123 madvise(start, byte_size, MADV_DONTNEED);
124 }
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700125 }
126 } else {
Hiroshi Yamauchi573f7d22013-12-17 11:54:23 -0800127 if (release_pages) {
128 madvise(start, byte_size, MADV_DONTNEED);
129 }
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700130 }
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 Chartier73d1e172014-04-11 17:53:48 -0700147 // | top_bitmap_idx |
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700148 // +-------------------+
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 Chartier73d1e172014-04-11 17:53:48 -0700178 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 Yamauchicf58d4a2013-09-26 14:21:22 -0700184
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 Yamauchia4adbfd2014-02-04 18:12:17 -0800207 uint32_t* BulkFreeBitMap() {
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700208 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 Yamauchia4adbfd2014-02-04 18:12:17 -0800211 uint32_t* ThreadLocalFreeBitMap() {
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700212 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 Chartier73d1e172014-04-11 17:53:48 -0700217 // 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 Yamauchicf58d4a2013-09-26 14:21:22 -0700227 // 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 Chartier73d1e172014-04-11 17:53:48 -0700245 // Marks the slots to free in the bulk free bit map. Returns the bracket size.
246 size_t MarkBulkFreeBitMap(void* ptr);
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700247 // Marks the slots to free in the thread-local free bit map.
248 void MarkThreadLocalFreeBitMap(void* ptr);
Mathieu Chartier73d1e172014-04-11 17:53:48 -0700249 // Last word mask, all of the bits in the last word which aren't valid slots are set to
250 // optimize allocation path.
Andreas Gampe59e67602014-04-25 17:15:12 -0700251 static uint32_t GetBitmapLastVectorMask(size_t num_slots, size_t num_vec);
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700252 // 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 Yamauchia4adbfd2014-02-04 18:12:17 -0800256 // 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 Chartier73d1e172014-04-11 17:53:48 -0700260 // 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 Yamauchicf58d4a2013-09-26 14:21:22 -0700268 // 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 Yamauchia4adbfd2014-02-04 18:12:17 -0800271 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 Yamauchicf58d4a2013-09-26 14:21:22 -0700276
277 private:
Mathieu Chartier73d1e172014-04-11 17:53:48 -0700278 // 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 Yamauchia4adbfd2014-02-04 18:12:17 -0800281 // Turns the bit map into a string for debugging.
282 static std::string BitMapToStr(uint32_t* bit_map_base, size_t num_vec);
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700283 };
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 Chartier73d1e172014-04-11 17:53:48 -0700388 size_t RoundDownToPageMapIndex(void* addr) const {
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700389 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 Yamauchi3c2856e2013-11-22 13:42:53 -0800397 // 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 Yamauchicf58d4a2013-09-26 14:21:22 -0700403 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 Yamauchi573f7d22013-12-17 11:54:23 -0800415 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 Chartier0651d412014-04-29 14:37:57 -0700429 // 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 Yamauchi573f7d22013-12-17 11:54:23 -0800433 private:
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700434 // 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 Yamauchi26d69ff2014-02-27 11:27:10 -0800442 // the end of the memory region that's currently managed by this allocator.
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700443 size_t capacity_;
444
Hiroshi Yamauchi26d69ff2014-02-27 11:27:10 -0800445 // 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 Yamauchicf58d4a2013-09-26 14:21:22 -0700449 // 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 Rogers5fcfa7d2014-05-15 11:43:06 -0700454 unordered_set<Run*, hash_run, eq_run> full_runs_[kNumOfSizeBrackets];
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700455 // The set of free pages.
456 std::set<FreePageRun*> free_page_runs_ GUARDED_BY(lock_);
Mathieu Chartier73d1e172014-04-11 17:53:48 -0700457 // 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 Yamauchicf58d4a2013-09-26 14:21:22 -0700462 // 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 Chartier73d1e172014-04-11 17:53:48 -0700468 // Bracket lock names (since locks only have char* names).
469 std::string size_bracket_lock_names[kNumOfSizeBrackets];
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700470 // 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 Yamauchi26d69ff2014-02-27 11:27:10 -0800479 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 Yamauchicf58d4a2013-09-26 14:21:22 -0700484 // 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 Yamauchi70f60042014-02-03 12:31:29 -0800492 // 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 Yamauchicf58d4a2013-09-26 14:21:22 -0700495 ReaderWriterMutex bulk_free_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
496
Hiroshi Yamauchi573f7d22013-12-17 11:54:23 -0800497 // 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 Yamauchicf58d4a2013-09-26 14:21:22 -0700503 // 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 Chartier73d1e172014-04-11 17:53:48 -0700511 // Returns how many bytes were freed.
512 size_t FreePages(Thread* self, void* ptr, bool already_zero) EXCLUSIVE_LOCKS_REQUIRED(lock_);
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700513
514 // Allocate/free a run slot.
515 void* AllocFromRun(Thread* self, size_t size, size_t* bytes_allocated)
516 LOCKS_EXCLUDED(lock_);
Mathieu Chartier0651d412014-04-29 14:37:57 -0700517 // 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 Chartier73d1e172014-04-11 17:53:48 -0700523 // Returns the bracket size.
524 size_t FreeFromRun(Thread* self, void* ptr, Run* run)
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700525 LOCKS_EXCLUDED(lock_);
526
Mathieu Chartier73d1e172014-04-11 17:53:48 -0700527 // 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 Yamauchicf58d4a2013-09-26 14:21:22 -0700530 // 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 Chartier8585bad2014-04-11 17:53:48 -0700535 size_t FreeInternal(Thread* self, void* ptr) LOCKS_EXCLUDED(lock_);
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700536
Hiroshi Yamauchi3c2856e2013-11-22 13:42:53 -0800537 // Allocates large objects.
538 void* AllocLargeObject(Thread* self, size_t size, size_t* bytes_allocated) LOCKS_EXCLUDED(lock_);
539
Mathieu Chartier0651d412014-04-29 14:37:57 -0700540 // 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 Yamauchicf58d4a2013-09-26 14:21:22 -0700546 public:
Hiroshi Yamauchi26d69ff2014-02-27 11:27:10 -0800547 RosAlloc(void* base, size_t capacity, size_t max_capacity,
Hiroshi Yamauchi573f7d22013-12-17 11:54:23 -0800548 PageReleaseMode page_release_mode,
549 size_t page_release_size_threshold = kDefaultPageReleaseSizeThreshold);
Mathieu Chartier661974a2014-01-09 11:23:53 -0800550 ~RosAlloc();
Mathieu Chartier0651d412014-04-29 14:37:57 -0700551 // 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 Yamauchicf58d4a2013-09-26 14:21:22 -0700554 void* Alloc(Thread* self, size_t size, size_t* bytes_allocated)
555 LOCKS_EXCLUDED(lock_);
Mathieu Chartier8585bad2014-04-11 17:53:48 -0700556 size_t Free(Thread* self, void* ptr)
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700557 LOCKS_EXCLUDED(bulk_free_lock_);
Mathieu Chartier8585bad2014-04-11 17:53:48 -0700558 size_t BulkFree(Thread* self, void** ptrs, size_t num_ptrs)
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700559 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 Yamauchid9a88de2014-04-07 13:52:31 -0700577 // Release empty pages.
578 size_t ReleasePages() LOCKS_EXCLUDED(lock_);
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700579 // 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 Yamauchic93c5302014-03-20 16:15:37 -0700589 // 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 Yamauchicf58d4a2013-09-26 14:21:22 -0700593 // Dumps the page map for debugging.
Hiroshi Yamauchia4adbfd2014-02-04 18:12:17 -0800594 std::string DumpPageMap() EXCLUSIVE_LOCKS_REQUIRED(lock_);
Mathieu Chartier73d1e172014-04-11 17:53:48 -0700595 static Run* GetDedicatedFullRun() {
596 return dedicated_full_run_;
597 }
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700598
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 Yamauchi573f7d22013-12-17 11:54:23 -0800603
604 bool DoesReleaseAllPages() const {
605 return page_release_mode_ == kPageReleaseModeAll;
606 }
Hiroshi Yamauchia4adbfd2014-02-04 18:12:17 -0800607
608 // Verify for debugging.
609 void Verify() EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_);
Hiroshi Yamauchicf58d4a2013-09-26 14:21:22 -0700610};
611
612} // namespace allocator
613} // namespace gc
614} // namespace art
615
616#endif // ART_RUNTIME_GC_ALLOCATOR_ROSALLOC_H_