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 #include "rosalloc-inl.h"
18 
19 #include <list>
20 #include <map>
21 #include <sstream>
22 #include <vector>
23 
24 #include "android-base/stringprintf.h"
25 
26 #include "base/logging.h"  // For VLOG
27 #include "base/memory_tool.h"
28 #include "base/mem_map.h"
29 #include "base/mutex-inl.h"
30 #include "gc/space/memory_tool_settings.h"
31 #include "mirror/class-inl.h"
32 #include "mirror/object-inl.h"
33 #include "mirror/object.h"
34 #include "thread-current-inl.h"
35 #include "thread_list.h"
36 
37 namespace art {
38 namespace gc {
39 namespace allocator {
40 
41 using android::base::StringPrintf;
42 
43 static constexpr bool kUsePrefetchDuringAllocRun = false;
44 static constexpr bool kPrefetchNewRunDataByZeroing = false;
45 static constexpr size_t kPrefetchStride = 64;
46 
47 size_t RosAlloc::bracketSizes[kNumOfSizeBrackets];
48 size_t RosAlloc::numOfPages[kNumOfSizeBrackets];
49 size_t RosAlloc::numOfSlots[kNumOfSizeBrackets];
50 size_t RosAlloc::headerSizes[kNumOfSizeBrackets];
51 bool RosAlloc::initialized_ = false;
52 size_t RosAlloc::dedicated_full_run_storage_[kPageSize / sizeof(size_t)] = { 0 };
53 RosAlloc::Run* RosAlloc::dedicated_full_run_ =
54     reinterpret_cast<RosAlloc::Run*>(dedicated_full_run_storage_);
55 
RosAlloc(void * base,size_t capacity,size_t max_capacity,PageReleaseMode page_release_mode,bool running_on_memory_tool,size_t page_release_size_threshold)56 RosAlloc::RosAlloc(void* base, size_t capacity, size_t max_capacity,
57                    PageReleaseMode page_release_mode, bool running_on_memory_tool,
58                    size_t page_release_size_threshold)
59     : base_(reinterpret_cast<uint8_t*>(base)), footprint_(capacity),
60       capacity_(capacity), max_capacity_(max_capacity),
61       lock_("rosalloc global lock", kRosAllocGlobalLock),
62       bulk_free_lock_("rosalloc bulk free lock", kRosAllocBulkFreeLock),
63       page_release_mode_(page_release_mode),
64       page_release_size_threshold_(page_release_size_threshold),
65       is_running_on_memory_tool_(running_on_memory_tool) {
66   DCHECK_ALIGNED(base, kPageSize);
67   DCHECK_EQ(RoundUp(capacity, kPageSize), capacity);
68   DCHECK_EQ(RoundUp(max_capacity, kPageSize), max_capacity);
69   CHECK_LE(capacity, max_capacity);
70   CHECK_ALIGNED(page_release_size_threshold_, kPageSize);
71   // Zero the memory explicitly (don't rely on that the mem map is zero-initialized).
72   if (!kMadviseZeroes) {
73     memset(base_, 0, max_capacity);
74   }
75   CHECK_EQ(madvise(base_, max_capacity, MADV_DONTNEED), 0);
76   if (!initialized_) {
77     Initialize();
78   }
79   VLOG(heap) << "RosAlloc base="
80              << std::hex << (intptr_t)base_ << ", end="
81              << std::hex << (intptr_t)(base_ + capacity_)
82              << ", capacity=" << std::dec << capacity_
83              << ", max_capacity=" << std::dec << max_capacity_;
84   for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
85     size_bracket_lock_names_[i] =
86         StringPrintf("an rosalloc size bracket %d lock", static_cast<int>(i));
87     size_bracket_locks_[i] = new Mutex(size_bracket_lock_names_[i].c_str(), kRosAllocBracketLock);
88     current_runs_[i] = dedicated_full_run_;
89   }
90   DCHECK_EQ(footprint_, capacity_);
91   size_t num_of_pages = footprint_ / kPageSize;
92   size_t max_num_of_pages = max_capacity_ / kPageSize;
93   std::string error_msg;
94   page_map_mem_map_ = MemMap::MapAnonymous("rosalloc page map",
95                                            RoundUp(max_num_of_pages, kPageSize),
96                                            PROT_READ | PROT_WRITE,
97                                            /*low_4gb=*/ false,
98                                            &error_msg);
99   CHECK(page_map_mem_map_.IsValid()) << "Couldn't allocate the page map : " << error_msg;
100   page_map_ = page_map_mem_map_.Begin();
101   page_map_size_ = num_of_pages;
102   max_page_map_size_ = max_num_of_pages;
103   free_page_run_size_map_.resize(num_of_pages);
104   FreePageRun* free_pages = reinterpret_cast<FreePageRun*>(base_);
105   if (kIsDebugBuild) {
106     free_pages->magic_num_ = kMagicNumFree;
107   }
108   free_pages->SetByteSize(this, capacity_);
109   DCHECK_EQ(capacity_ % kPageSize, static_cast<size_t>(0));
110   DCHECK(free_pages->IsFree());
111   free_pages->ReleasePages(this);
112   DCHECK(free_pages->IsFree());
113   free_page_runs_.insert(free_pages);
114   if (kTraceRosAlloc) {
115     LOG(INFO) << "RosAlloc::RosAlloc() : Inserted run 0x" << std::hex
116               << reinterpret_cast<intptr_t>(free_pages)
117               << " into free_page_runs_";
118   }
119 }
120 
~RosAlloc()121 RosAlloc::~RosAlloc() {
122   for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
123     delete size_bracket_locks_[i];
124   }
125   if (is_running_on_memory_tool_) {
126     MEMORY_TOOL_MAKE_DEFINED(base_, capacity_);
127   }
128 }
129 
AllocPages(Thread * self,size_t num_pages,uint8_t page_map_type)130 void* RosAlloc::AllocPages(Thread* self, size_t num_pages, uint8_t page_map_type) {
131   lock_.AssertHeld(self);
132   DCHECK(page_map_type == kPageMapRun || page_map_type == kPageMapLargeObject);
133   FreePageRun* res = nullptr;
134   const size_t req_byte_size = num_pages * kPageSize;
135   // Find the lowest address free page run that's large enough.
136   for (auto it = free_page_runs_.begin(); it != free_page_runs_.end(); ) {
137     FreePageRun* fpr = *it;
138     DCHECK(fpr->IsFree());
139     size_t fpr_byte_size = fpr->ByteSize(this);
140     DCHECK_EQ(fpr_byte_size % kPageSize, static_cast<size_t>(0));
141     if (req_byte_size <= fpr_byte_size) {
142       // Found one.
143       it = free_page_runs_.erase(it);
144       if (kTraceRosAlloc) {
145         LOG(INFO) << "RosAlloc::AllocPages() : Erased run 0x"
146                   << std::hex << reinterpret_cast<intptr_t>(fpr)
147                   << " from free_page_runs_";
148       }
149       if (req_byte_size < fpr_byte_size) {
150         // Split.
151         FreePageRun* remainder =
152             reinterpret_cast<FreePageRun*>(reinterpret_cast<uint8_t*>(fpr) + req_byte_size);
153         if (kIsDebugBuild) {
154           remainder->magic_num_ = kMagicNumFree;
155         }
156         remainder->SetByteSize(this, fpr_byte_size - req_byte_size);
157         DCHECK_EQ(remainder->ByteSize(this) % kPageSize, static_cast<size_t>(0));
158         // Don't need to call madvise on remainder here.
159         free_page_runs_.insert(remainder);
160         if (kTraceRosAlloc) {
161           LOG(INFO) << "RosAlloc::AllocPages() : Inserted run 0x" << std::hex
162                     << reinterpret_cast<intptr_t>(remainder)
163                     << " into free_page_runs_";
164         }
165         fpr->SetByteSize(this, req_byte_size);
166         DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0));
167       }
168       res = fpr;
169       break;
170     } else {
171       ++it;
172     }
173   }
174 
175   // Failed to allocate pages. Grow the footprint, if possible.
176   if (UNLIKELY(res == nullptr && capacity_ > footprint_)) {
177     FreePageRun* last_free_page_run = nullptr;
178     size_t last_free_page_run_size;
179     auto it = free_page_runs_.rbegin();
180     if (it != free_page_runs_.rend() && (last_free_page_run = *it)->End(this) == base_ + footprint_) {
181       // There is a free page run at the end.
182       DCHECK(last_free_page_run->IsFree());
183       DCHECK(IsFreePage(ToPageMapIndex(last_free_page_run)));
184       last_free_page_run_size = last_free_page_run->ByteSize(this);
185     } else {
186       // There is no free page run at the end.
187       last_free_page_run_size = 0;
188     }
189     DCHECK_LT(last_free_page_run_size, req_byte_size);
190     if (capacity_ - footprint_ + last_free_page_run_size >= req_byte_size) {
191       // If we grow the heap, we can allocate it.
192       size_t increment = std::min(std::max(2 * MB, req_byte_size - last_free_page_run_size),
193                                   capacity_ - footprint_);
194       DCHECK_EQ(increment % kPageSize, static_cast<size_t>(0));
195       size_t new_footprint = footprint_ + increment;
196       size_t new_num_of_pages = new_footprint / kPageSize;
197       DCHECK_LT(page_map_size_, new_num_of_pages);
198       DCHECK_LT(free_page_run_size_map_.size(), new_num_of_pages);
199       page_map_size_ = new_num_of_pages;
200       DCHECK_LE(page_map_size_, max_page_map_size_);
201       free_page_run_size_map_.resize(new_num_of_pages);
202       ArtRosAllocMoreCore(this, increment);
203       if (last_free_page_run_size > 0) {
204         // There was a free page run at the end. Expand its size.
205         DCHECK_EQ(last_free_page_run_size, last_free_page_run->ByteSize(this));
206         last_free_page_run->SetByteSize(this, last_free_page_run_size + increment);
207         DCHECK_EQ(last_free_page_run->ByteSize(this) % kPageSize, static_cast<size_t>(0));
208         DCHECK_EQ(last_free_page_run->End(this), base_ + new_footprint);
209       } else {
210         // Otherwise, insert a new free page run at the end.
211         FreePageRun* new_free_page_run = reinterpret_cast<FreePageRun*>(base_ + footprint_);
212         if (kIsDebugBuild) {
213           new_free_page_run->magic_num_ = kMagicNumFree;
214         }
215         new_free_page_run->SetByteSize(this, increment);
216         DCHECK_EQ(new_free_page_run->ByteSize(this) % kPageSize, static_cast<size_t>(0));
217         free_page_runs_.insert(new_free_page_run);
218         DCHECK_EQ(*free_page_runs_.rbegin(), new_free_page_run);
219         if (kTraceRosAlloc) {
220           LOG(INFO) << "RosAlloc::AlloPages() : Grew the heap by inserting run 0x"
221                     << std::hex << reinterpret_cast<intptr_t>(new_free_page_run)
222                     << " into free_page_runs_";
223         }
224       }
225       DCHECK_LE(footprint_ + increment, capacity_);
226       if (kTraceRosAlloc) {
227         LOG(INFO) << "RosAlloc::AllocPages() : increased the footprint from "
228                   << footprint_ << " to " << new_footprint;
229       }
230       footprint_ = new_footprint;
231 
232       // And retry the last free page run.
233       it = free_page_runs_.rbegin();
234       DCHECK(it != free_page_runs_.rend());
235       FreePageRun* fpr = *it;
236       if (kIsDebugBuild && last_free_page_run_size > 0) {
237         DCHECK(last_free_page_run != nullptr);
238         DCHECK_EQ(last_free_page_run, fpr);
239       }
240       size_t fpr_byte_size = fpr->ByteSize(this);
241       DCHECK_EQ(fpr_byte_size % kPageSize, static_cast<size_t>(0));
242       DCHECK_LE(req_byte_size, fpr_byte_size);
243       free_page_runs_.erase(fpr);
244       if (kTraceRosAlloc) {
245         LOG(INFO) << "RosAlloc::AllocPages() : Erased run 0x" << std::hex << reinterpret_cast<intptr_t>(fpr)
246                   << " from free_page_runs_";
247       }
248       if (req_byte_size < fpr_byte_size) {
249         // Split if there's a remainder.
250         FreePageRun* remainder = reinterpret_cast<FreePageRun*>(reinterpret_cast<uint8_t*>(fpr) + req_byte_size);
251         if (kIsDebugBuild) {
252           remainder->magic_num_ = kMagicNumFree;
253         }
254         remainder->SetByteSize(this, fpr_byte_size - req_byte_size);
255         DCHECK_EQ(remainder->ByteSize(this) % kPageSize, static_cast<size_t>(0));
256         free_page_runs_.insert(remainder);
257         if (kTraceRosAlloc) {
258           LOG(INFO) << "RosAlloc::AllocPages() : Inserted run 0x" << std::hex
259                     << reinterpret_cast<intptr_t>(remainder)
260                     << " into free_page_runs_";
261         }
262         fpr->SetByteSize(this, req_byte_size);
263         DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0));
264       }
265       res = fpr;
266     }
267   }
268   if (LIKELY(res != nullptr)) {
269     // Update the page map.
270     size_t page_map_idx = ToPageMapIndex(res);
271     for (size_t i = 0; i < num_pages; i++) {
272       DCHECK(IsFreePage(page_map_idx + i));
273     }
274     switch (page_map_type) {
275     case kPageMapRun:
276       page_map_[page_map_idx] = kPageMapRun;
277       for (size_t i = 1; i < num_pages; i++) {
278         page_map_[page_map_idx + i] = kPageMapRunPart;
279       }
280       break;
281     case kPageMapLargeObject:
282       page_map_[page_map_idx] = kPageMapLargeObject;
283       for (size_t i = 1; i < num_pages; i++) {
284         page_map_[page_map_idx + i] = kPageMapLargeObjectPart;
285       }
286       break;
287     default:
288       LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_type);
289       UNREACHABLE();
290     }
291     if (kIsDebugBuild) {
292       // Clear the first page since it is not madvised due to the magic number.
293       memset(res, 0, kPageSize);
294     }
295     if (kTraceRosAlloc) {
296       LOG(INFO) << "RosAlloc::AllocPages() : 0x" << std::hex << reinterpret_cast<intptr_t>(res)
297                 << "-0x" << (reinterpret_cast<intptr_t>(res) + num_pages * kPageSize)
298                 << "(" << std::dec << (num_pages * kPageSize) << ")";
299     }
300     return res;
301   }
302 
303   // Fail.
304   if (kTraceRosAlloc) {
305     LOG(INFO) << "RosAlloc::AllocPages() : nullptr";
306   }
307   return nullptr;
308 }
309 
FreePages(Thread * self,void * ptr,bool already_zero)310 size_t RosAlloc::FreePages(Thread* self, void* ptr, bool already_zero) {
311   lock_.AssertHeld(self);
312   size_t pm_idx = ToPageMapIndex(ptr);
313   DCHECK_LT(pm_idx, page_map_size_);
314   uint8_t pm_type = page_map_[pm_idx];
315   DCHECK(pm_type == kPageMapRun || pm_type == kPageMapLargeObject);
316   uint8_t pm_part_type;
317   switch (pm_type) {
318   case kPageMapRun:
319     pm_part_type = kPageMapRunPart;
320     break;
321   case kPageMapLargeObject:
322     pm_part_type = kPageMapLargeObjectPart;
323     break;
324   default:
325     LOG(FATAL) << "Unreachable - " << __PRETTY_FUNCTION__ << " : " << "pm_idx=" << pm_idx << ", pm_type="
326                << static_cast<int>(pm_type) << ", ptr=" << std::hex
327                << reinterpret_cast<intptr_t>(ptr);
328     UNREACHABLE();
329   }
330   // Update the page map and count the number of pages.
331   size_t num_pages = 1;
332   page_map_[pm_idx] = kPageMapEmpty;
333   size_t idx = pm_idx + 1;
334   size_t end = page_map_size_;
335   while (idx < end && page_map_[idx] == pm_part_type) {
336     page_map_[idx] = kPageMapEmpty;
337     num_pages++;
338     idx++;
339   }
340   const size_t byte_size = num_pages * kPageSize;
341   if (already_zero) {
342     if (ShouldCheckZeroMemory()) {
343       const uintptr_t* word_ptr = reinterpret_cast<uintptr_t*>(ptr);
344       for (size_t i = 0; i < byte_size / sizeof(uintptr_t); ++i) {
345         CHECK_EQ(word_ptr[i], 0U) << "words don't match at index " << i;
346       }
347     }
348   } else if (!DoesReleaseAllPages()) {
349     memset(ptr, 0, byte_size);
350   }
351 
352   if (kTraceRosAlloc) {
353     LOG(INFO) << __PRETTY_FUNCTION__ << " : 0x" << std::hex << reinterpret_cast<intptr_t>(ptr)
354               << "-0x" << (reinterpret_cast<intptr_t>(ptr) + byte_size)
355               << "(" << std::dec << (num_pages * kPageSize) << ")";
356   }
357 
358   // Turn it into a free run.
359   FreePageRun* fpr = reinterpret_cast<FreePageRun*>(ptr);
360   if (kIsDebugBuild) {
361     fpr->magic_num_ = kMagicNumFree;
362   }
363   fpr->SetByteSize(this, byte_size);
364   DCHECK_ALIGNED(fpr->ByteSize(this), kPageSize);
365 
366   DCHECK(free_page_runs_.find(fpr) == free_page_runs_.end());
367   if (!free_page_runs_.empty()) {
368     // Try to coalesce in the higher address direction.
369     if (kTraceRosAlloc) {
370       LOG(INFO) << __PRETTY_FUNCTION__ << "RosAlloc::FreePages() : trying to coalesce a free page run 0x"
371                 << std::hex << reinterpret_cast<uintptr_t>(fpr) << " [" << std::dec << pm_idx << "] -0x"
372                 << std::hex << reinterpret_cast<uintptr_t>(fpr->End(this)) << " [" << std::dec
373                 << (fpr->End(this) == End() ? page_map_size_ : ToPageMapIndex(fpr->End(this))) << "]";
374     }
375     for (auto it = free_page_runs_.upper_bound(fpr); it != free_page_runs_.end(); ) {
376       FreePageRun* h = *it;
377       DCHECK_EQ(h->ByteSize(this) % kPageSize, static_cast<size_t>(0));
378       if (kTraceRosAlloc) {
379         LOG(INFO) << "RosAlloc::FreePages() : trying to coalesce with a higher free page run 0x"
380                   << std::hex << reinterpret_cast<uintptr_t>(h) << " [" << std::dec << ToPageMapIndex(h) << "] -0x"
381                   << std::hex << reinterpret_cast<uintptr_t>(h->End(this)) << " [" << std::dec
382                   << (h->End(this) == End() ? page_map_size_ : ToPageMapIndex(h->End(this))) << "]";
383       }
384       if (fpr->End(this) == h->Begin()) {
385         if (kTraceRosAlloc) {
386           LOG(INFO) << "Success";
387         }
388         // Clear magic num since this is no longer the start of a free page run.
389         if (kIsDebugBuild) {
390           h->magic_num_ = 0;
391         }
392         it = free_page_runs_.erase(it);
393         if (kTraceRosAlloc) {
394           LOG(INFO) << "RosAlloc::FreePages() : (coalesce) Erased run 0x" << std::hex
395                     << reinterpret_cast<intptr_t>(h)
396                     << " from free_page_runs_";
397         }
398         fpr->SetByteSize(this, fpr->ByteSize(this) + h->ByteSize(this));
399         DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0));
400       } else {
401         // Not adjacent. Stop.
402         if (kTraceRosAlloc) {
403           LOG(INFO) << "Fail";
404         }
405         break;
406       }
407     }
408     // Try to coalesce in the lower address direction.
409     for (auto it = free_page_runs_.upper_bound(fpr); it != free_page_runs_.begin(); ) {
410       --it;
411 
412       FreePageRun* l = *it;
413       DCHECK_EQ(l->ByteSize(this) % kPageSize, static_cast<size_t>(0));
414       if (kTraceRosAlloc) {
415         LOG(INFO) << "RosAlloc::FreePages() : trying to coalesce with a lower free page run 0x"
416                   << std::hex << reinterpret_cast<uintptr_t>(l) << " [" << std::dec << ToPageMapIndex(l) << "] -0x"
417                   << std::hex << reinterpret_cast<uintptr_t>(l->End(this)) << " [" << std::dec
418                   << (l->End(this) == End() ? page_map_size_ : ToPageMapIndex(l->End(this))) << "]";
419       }
420       if (l->End(this) == fpr->Begin()) {
421         if (kTraceRosAlloc) {
422           LOG(INFO) << "Success";
423         }
424         it = free_page_runs_.erase(it);
425         if (kTraceRosAlloc) {
426           LOG(INFO) << "RosAlloc::FreePages() : (coalesce) Erased run 0x" << std::hex
427                     << reinterpret_cast<intptr_t>(l)
428                     << " from free_page_runs_";
429         }
430         l->SetByteSize(this, l->ByteSize(this) + fpr->ByteSize(this));
431         DCHECK_EQ(l->ByteSize(this) % kPageSize, static_cast<size_t>(0));
432         // Clear magic num since this is no longer the start of a free page run.
433         if (kIsDebugBuild) {
434           fpr->magic_num_ = 0;
435         }
436         fpr = l;
437       } else {
438         // Not adjacent. Stop.
439         if (kTraceRosAlloc) {
440           LOG(INFO) << "Fail";
441         }
442         break;
443       }
444     }
445   }
446 
447   // Insert it.
448   DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0));
449   DCHECK(free_page_runs_.find(fpr) == free_page_runs_.end());
450   DCHECK(fpr->IsFree());
451   fpr->ReleasePages(this);
452   DCHECK(fpr->IsFree());
453   free_page_runs_.insert(fpr);
454   DCHECK(free_page_runs_.find(fpr) != free_page_runs_.end());
455   if (kTraceRosAlloc) {
456     LOG(INFO) << "RosAlloc::FreePages() : Inserted run 0x" << std::hex << reinterpret_cast<intptr_t>(fpr)
457               << " into free_page_runs_";
458   }
459   return byte_size;
460 }
461 
AllocLargeObject(Thread * self,size_t size,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)462 void* RosAlloc::AllocLargeObject(Thread* self, size_t size, size_t* bytes_allocated,
463                                  size_t* usable_size, size_t* bytes_tl_bulk_allocated) {
464   DCHECK(bytes_allocated != nullptr);
465   DCHECK(usable_size != nullptr);
466   DCHECK_GT(size, kLargeSizeThreshold);
467   size_t num_pages = RoundUp(size, kPageSize) / kPageSize;
468   void* r;
469   {
470     MutexLock mu(self, lock_);
471     r = AllocPages(self, num_pages, kPageMapLargeObject);
472   }
473   if (UNLIKELY(r == nullptr)) {
474     if (kTraceRosAlloc) {
475       LOG(INFO) << "RosAlloc::AllocLargeObject() : nullptr";
476     }
477     return nullptr;
478   }
479   const size_t total_bytes = num_pages * kPageSize;
480   *bytes_allocated = total_bytes;
481   *usable_size = total_bytes;
482   *bytes_tl_bulk_allocated = total_bytes;
483   if (kTraceRosAlloc) {
484     LOG(INFO) << "RosAlloc::AllocLargeObject() : 0x" << std::hex << reinterpret_cast<intptr_t>(r)
485               << "-0x" << (reinterpret_cast<intptr_t>(r) + num_pages * kPageSize)
486               << "(" << std::dec << (num_pages * kPageSize) << ")";
487   }
488   // Check if the returned memory is really all zero.
489   if (ShouldCheckZeroMemory()) {
490     CHECK_EQ(total_bytes % sizeof(uintptr_t), 0U);
491     const uintptr_t* words = reinterpret_cast<uintptr_t*>(r);
492     for (size_t i = 0; i < total_bytes / sizeof(uintptr_t); ++i) {
493       CHECK_EQ(words[i], 0U);
494     }
495   }
496   return r;
497 }
498 
FreeInternal(Thread * self,void * ptr)499 size_t RosAlloc::FreeInternal(Thread* self, void* ptr) {
500   DCHECK_LE(base_, ptr);
501   DCHECK_LT(ptr, base_ + footprint_);
502   size_t pm_idx = RoundDownToPageMapIndex(ptr);
503   Run* run = nullptr;
504   {
505     MutexLock mu(self, lock_);
506     DCHECK_LT(pm_idx, page_map_size_);
507     uint8_t page_map_entry = page_map_[pm_idx];
508     if (kTraceRosAlloc) {
509       LOG(INFO) << "RosAlloc::FreeInternal() : " << std::hex << ptr << ", pm_idx=" << std::dec << pm_idx
510                 << ", page_map_entry=" << static_cast<int>(page_map_entry);
511     }
512     switch (page_map_[pm_idx]) {
513       case kPageMapLargeObject:
514         return FreePages(self, ptr, false);
515       case kPageMapLargeObjectPart:
516         LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_[pm_idx]);
517         UNREACHABLE();
518       case kPageMapRunPart: {
519         // Find the beginning of the run.
520         do {
521           --pm_idx;
522           DCHECK_LT(pm_idx, capacity_ / kPageSize);
523         } while (page_map_[pm_idx] != kPageMapRun);
524         FALLTHROUGH_INTENDED;
525       case kPageMapRun:
526         run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize);
527         DCHECK_EQ(run->magic_num_, kMagicNum);
528         break;
529       case kPageMapReleased:
530       case kPageMapEmpty:
531         LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_[pm_idx]);
532         UNREACHABLE();
533       }
534       default:
535         LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_[pm_idx]);
536         UNREACHABLE();
537     }
538   }
539   DCHECK(run != nullptr);
540   return FreeFromRun(self, ptr, run);
541 }
542 
Free(Thread * self,void * ptr)543 size_t RosAlloc::Free(Thread* self, void* ptr) {
544   ReaderMutexLock rmu(self, bulk_free_lock_);
545   return FreeInternal(self, ptr);
546 }
547 
AllocRun(Thread * self,size_t idx)548 RosAlloc::Run* RosAlloc::AllocRun(Thread* self, size_t idx) {
549   RosAlloc::Run* new_run = nullptr;
550   {
551     MutexLock mu(self, lock_);
552     new_run = reinterpret_cast<Run*>(AllocPages(self, numOfPages[idx], kPageMapRun));
553   }
554   if (LIKELY(new_run != nullptr)) {
555     if (kIsDebugBuild) {
556       new_run->magic_num_ = kMagicNum;
557     }
558     new_run->size_bracket_idx_ = idx;
559     DCHECK(!new_run->IsThreadLocal());
560     DCHECK(!new_run->to_be_bulk_freed_);
561     if (kUsePrefetchDuringAllocRun && idx < kNumThreadLocalSizeBrackets) {
562       // Take ownership of the cache lines if we are likely to be thread local run.
563       if (kPrefetchNewRunDataByZeroing) {
564         // Zeroing the data is sometimes faster than prefetching but it increases memory usage
565         // since we end up dirtying zero pages which may have been madvised.
566         new_run->ZeroData();
567       } else {
568         const size_t num_of_slots = numOfSlots[idx];
569         const size_t bracket_size = bracketSizes[idx];
570         const size_t num_of_bytes = num_of_slots * bracket_size;
571         uint8_t* begin = reinterpret_cast<uint8_t*>(new_run) + headerSizes[idx];
572         for (size_t i = 0; i < num_of_bytes; i += kPrefetchStride) {
573           __builtin_prefetch(begin + i);
574         }
575       }
576     }
577     new_run->InitFreeList();
578   }
579   return new_run;
580 }
581 
RefillRun(Thread * self,size_t idx)582 RosAlloc::Run* RosAlloc::RefillRun(Thread* self, size_t idx) {
583   // Get the lowest address non-full run from the binary tree.
584   auto* const bt = &non_full_runs_[idx];
585   if (!bt->empty()) {
586     // If there's one, use it as the current run.
587     auto it = bt->begin();
588     Run* non_full_run = *it;
589     DCHECK(non_full_run != nullptr);
590     DCHECK(!non_full_run->IsThreadLocal());
591     bt->erase(it);
592     return non_full_run;
593   }
594   // If there's none, allocate a new run and use it as the current run.
595   return AllocRun(self, idx);
596 }
597 
AllocFromCurrentRunUnlocked(Thread * self,size_t idx)598 inline void* RosAlloc::AllocFromCurrentRunUnlocked(Thread* self, size_t idx) {
599   Run* current_run = current_runs_[idx];
600   DCHECK(current_run != nullptr);
601   void* slot_addr = current_run->AllocSlot();
602   if (UNLIKELY(slot_addr == nullptr)) {
603     // The current run got full. Try to refill it.
604     DCHECK(current_run->IsFull());
605     if (kIsDebugBuild && current_run != dedicated_full_run_) {
606       full_runs_[idx].insert(current_run);
607       if (kTraceRosAlloc) {
608         LOG(INFO) << __PRETTY_FUNCTION__ << " : Inserted run 0x" << std::hex
609                   << reinterpret_cast<intptr_t>(current_run)
610                   << " into full_runs_[" << std::dec << idx << "]";
611       }
612       DCHECK(non_full_runs_[idx].find(current_run) == non_full_runs_[idx].end());
613       DCHECK(full_runs_[idx].find(current_run) != full_runs_[idx].end());
614     }
615     current_run = RefillRun(self, idx);
616     if (UNLIKELY(current_run == nullptr)) {
617       // Failed to allocate a new run, make sure that it is the dedicated full run.
618       current_runs_[idx] = dedicated_full_run_;
619       return nullptr;
620     }
621     DCHECK(current_run != nullptr);
622     DCHECK(non_full_runs_[idx].find(current_run) == non_full_runs_[idx].end());
623     DCHECK(full_runs_[idx].find(current_run) == full_runs_[idx].end());
624     current_run->SetIsThreadLocal(false);
625     current_runs_[idx] = current_run;
626     DCHECK(!current_run->IsFull());
627     slot_addr = current_run->AllocSlot();
628     // Must succeed now with a new run.
629     DCHECK(slot_addr != nullptr);
630   }
631   return slot_addr;
632 }
633 
AllocFromRunThreadUnsafe(Thread * self,size_t size,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)634 void* RosAlloc::AllocFromRunThreadUnsafe(Thread* self, size_t size, size_t* bytes_allocated,
635                                          size_t* usable_size,
636                                          size_t* bytes_tl_bulk_allocated) {
637   DCHECK(bytes_allocated != nullptr);
638   DCHECK(usable_size != nullptr);
639   DCHECK(bytes_tl_bulk_allocated != nullptr);
640   DCHECK_LE(size, kLargeSizeThreshold);
641   size_t bracket_size;
642   size_t idx = SizeToIndexAndBracketSize(size, &bracket_size);
643   Locks::mutator_lock_->AssertExclusiveHeld(self);
644   void* slot_addr = AllocFromCurrentRunUnlocked(self, idx);
645   if (LIKELY(slot_addr != nullptr)) {
646     *bytes_allocated = bracket_size;
647     *usable_size = bracket_size;
648     *bytes_tl_bulk_allocated = bracket_size;
649   }
650   // Caller verifies that it is all 0.
651   return slot_addr;
652 }
653 
AllocFromRun(Thread * self,size_t size,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)654 void* RosAlloc::AllocFromRun(Thread* self, size_t size, size_t* bytes_allocated,
655                              size_t* usable_size, size_t* bytes_tl_bulk_allocated) {
656   DCHECK(bytes_allocated != nullptr);
657   DCHECK(usable_size != nullptr);
658   DCHECK(bytes_tl_bulk_allocated != nullptr);
659   DCHECK_LE(size, kLargeSizeThreshold);
660   size_t bracket_size;
661   size_t idx = SizeToIndexAndBracketSize(size, &bracket_size);
662   void* slot_addr;
663   if (LIKELY(idx < kNumThreadLocalSizeBrackets)) {
664     // Use a thread-local run.
665     Run* thread_local_run = reinterpret_cast<Run*>(self->GetRosAllocRun(idx));
666     // Allow invalid since this will always fail the allocation.
667     if (kIsDebugBuild) {
668       // Need the lock to prevent race conditions.
669       MutexLock mu(self, *size_bracket_locks_[idx]);
670       CHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end());
671       CHECK(full_runs_[idx].find(thread_local_run) == full_runs_[idx].end());
672     }
673     DCHECK(thread_local_run != nullptr);
674     DCHECK(thread_local_run->IsThreadLocal() || thread_local_run == dedicated_full_run_);
675     slot_addr = thread_local_run->AllocSlot();
676     // The allocation must fail if the run is invalid.
677     DCHECK(thread_local_run != dedicated_full_run_ || slot_addr == nullptr)
678         << "allocated from an invalid run";
679     if (UNLIKELY(slot_addr == nullptr)) {
680       // The run got full. Try to free slots.
681       DCHECK(thread_local_run->IsFull());
682       MutexLock mu(self, *size_bracket_locks_[idx]);
683       bool is_all_free_after_merge;
684       // This is safe to do for the dedicated_full_run_ since the bitmaps are empty.
685       if (thread_local_run->MergeThreadLocalFreeListToFreeList(&is_all_free_after_merge)) {
686         DCHECK_NE(thread_local_run, dedicated_full_run_);
687         // Some slot got freed. Keep it.
688         DCHECK(!thread_local_run->IsFull());
689         DCHECK_EQ(is_all_free_after_merge, thread_local_run->IsAllFree());
690       } else {
691         // No slots got freed. Try to refill the thread-local run.
692         DCHECK(thread_local_run->IsFull());
693         if (thread_local_run != dedicated_full_run_) {
694           thread_local_run->SetIsThreadLocal(false);
695           if (kIsDebugBuild) {
696             full_runs_[idx].insert(thread_local_run);
697             if (kTraceRosAlloc) {
698               LOG(INFO) << "RosAlloc::AllocFromRun() : Inserted run 0x" << std::hex
699                         << reinterpret_cast<intptr_t>(thread_local_run)
700                         << " into full_runs_[" << std::dec << idx << "]";
701             }
702           }
703           DCHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end());
704           DCHECK(full_runs_[idx].find(thread_local_run) != full_runs_[idx].end());
705         }
706 
707         thread_local_run = RefillRun(self, idx);
708         if (UNLIKELY(thread_local_run == nullptr)) {
709           self->SetRosAllocRun(idx, dedicated_full_run_);
710           return nullptr;
711         }
712         DCHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end());
713         DCHECK(full_runs_[idx].find(thread_local_run) == full_runs_[idx].end());
714         thread_local_run->SetIsThreadLocal(true);
715         self->SetRosAllocRun(idx, thread_local_run);
716         DCHECK(!thread_local_run->IsFull());
717       }
718       DCHECK(thread_local_run != nullptr);
719       DCHECK(!thread_local_run->IsFull());
720       DCHECK(thread_local_run->IsThreadLocal());
721       // Account for all the free slots in the new or refreshed thread local run.
722       *bytes_tl_bulk_allocated = thread_local_run->NumberOfFreeSlots() * bracket_size;
723       slot_addr = thread_local_run->AllocSlot();
724       // Must succeed now with a new run.
725       DCHECK(slot_addr != nullptr);
726     } else {
727       // The slot is already counted. Leave it as is.
728       *bytes_tl_bulk_allocated = 0;
729     }
730     DCHECK(slot_addr != nullptr);
731     if (kTraceRosAlloc) {
732       LOG(INFO) << "RosAlloc::AllocFromRun() thread-local : 0x" << std::hex
733                 << reinterpret_cast<intptr_t>(slot_addr)
734                 << "-0x" << (reinterpret_cast<intptr_t>(slot_addr) + bracket_size)
735                 << "(" << std::dec << (bracket_size) << ")";
736     }
737     *bytes_allocated = bracket_size;
738     *usable_size = bracket_size;
739   } else {
740     // Use the (shared) current run.
741     MutexLock mu(self, *size_bracket_locks_[idx]);
742     slot_addr = AllocFromCurrentRunUnlocked(self, idx);
743     if (kTraceRosAlloc) {
744       LOG(INFO) << "RosAlloc::AllocFromRun() : 0x" << std::hex
745                 << reinterpret_cast<intptr_t>(slot_addr)
746                 << "-0x" << (reinterpret_cast<intptr_t>(slot_addr) + bracket_size)
747                 << "(" << std::dec << (bracket_size) << ")";
748     }
749     if (LIKELY(slot_addr != nullptr)) {
750       *bytes_allocated = bracket_size;
751       *usable_size = bracket_size;
752       *bytes_tl_bulk_allocated = bracket_size;
753     }
754   }
755   // Caller verifies that it is all 0.
756   return slot_addr;
757 }
758 
FreeFromRun(Thread * self,void * ptr,Run * run)759 size_t RosAlloc::FreeFromRun(Thread* self, void* ptr, Run* run) {
760   DCHECK_EQ(run->magic_num_, kMagicNum);
761   DCHECK_LT(run, ptr);
762   DCHECK_LT(ptr, run->End());
763   const size_t idx = run->size_bracket_idx_;
764   const size_t bracket_size = bracketSizes[idx];
765   bool run_was_full = false;
766   MutexLock brackets_mu(self, *size_bracket_locks_[idx]);
767   if (kIsDebugBuild) {
768     run_was_full = run->IsFull();
769   }
770   if (kTraceRosAlloc) {
771     LOG(INFO) << "RosAlloc::FreeFromRun() : 0x" << std::hex << reinterpret_cast<intptr_t>(ptr);
772   }
773   if (LIKELY(run->IsThreadLocal())) {
774     // It's a thread-local run. Just mark the thread-local free bit map and return.
775     DCHECK_LT(run->size_bracket_idx_, kNumThreadLocalSizeBrackets);
776     DCHECK(non_full_runs_[idx].find(run) == non_full_runs_[idx].end());
777     DCHECK(full_runs_[idx].find(run) == full_runs_[idx].end());
778     run->AddToThreadLocalFreeList(ptr);
779     if (kTraceRosAlloc) {
780       LOG(INFO) << "RosAlloc::FreeFromRun() : Freed a slot in a thread local run 0x" << std::hex
781                 << reinterpret_cast<intptr_t>(run);
782     }
783     // A thread local run will be kept as a thread local even if it's become all free.
784     return bracket_size;
785   }
786   // Free the slot in the run.
787   run->FreeSlot(ptr);
788   auto* non_full_runs = &non_full_runs_[idx];
789   if (run->IsAllFree()) {
790     // It has just become completely free. Free the pages of this run.
791     std::set<Run*>::iterator pos = non_full_runs->find(run);
792     if (pos != non_full_runs->end()) {
793       non_full_runs->erase(pos);
794       if (kTraceRosAlloc) {
795         LOG(INFO) << "RosAlloc::FreeFromRun() : Erased run 0x" << std::hex
796                   << reinterpret_cast<intptr_t>(run) << " from non_full_runs_";
797       }
798     }
799     if (run == current_runs_[idx]) {
800       current_runs_[idx] = dedicated_full_run_;
801     }
802     DCHECK(non_full_runs_[idx].find(run) == non_full_runs_[idx].end());
803     DCHECK(full_runs_[idx].find(run) == full_runs_[idx].end());
804     run->ZeroHeaderAndSlotHeaders();
805     {
806       MutexLock lock_mu(self, lock_);
807       FreePages(self, run, true);
808     }
809   } else {
810     // It is not completely free. If it wasn't the current run or
811     // already in the non-full run set (i.e., it was full) insert it
812     // into the non-full run set.
813     if (run != current_runs_[idx]) {
814       auto* full_runs = kIsDebugBuild ? &full_runs_[idx] : nullptr;
815       auto pos = non_full_runs->find(run);
816       if (pos == non_full_runs->end()) {
817         DCHECK(run_was_full);
818         DCHECK(full_runs->find(run) != full_runs->end());
819         if (kIsDebugBuild) {
820           full_runs->erase(run);
821           if (kTraceRosAlloc) {
822             LOG(INFO) << "RosAlloc::FreeFromRun() : Erased run 0x" << std::hex
823                       << reinterpret_cast<intptr_t>(run) << " from full_runs_";
824           }
825         }
826         non_full_runs->insert(run);
827         DCHECK(!run->IsFull());
828         if (kTraceRosAlloc) {
829           LOG(INFO) << "RosAlloc::FreeFromRun() : Inserted run 0x" << std::hex
830                     << reinterpret_cast<intptr_t>(run)
831                     << " into non_full_runs_[" << std::dec << idx << "]";
832         }
833       }
834     }
835   }
836   return bracket_size;
837 }
838 
839 template<bool kUseTail>
FreeListToStr(SlotFreeList<kUseTail> * free_list)840 std::string RosAlloc::Run::FreeListToStr(SlotFreeList<kUseTail>* free_list) {
841   std::string free_list_str;
842   const uint8_t idx = size_bracket_idx_;
843   const size_t bracket_size = bracketSizes[idx];
844   for (Slot* slot = free_list->Head(); slot != nullptr; slot = slot->Next()) {
845     bool is_last = slot->Next() == nullptr;
846     uintptr_t slot_offset = reinterpret_cast<uintptr_t>(slot) -
847         reinterpret_cast<uintptr_t>(FirstSlot());
848     DCHECK_EQ(slot_offset % bracket_size, 0U);
849     uintptr_t slot_idx = slot_offset / bracket_size;
850     if (!is_last) {
851       free_list_str.append(StringPrintf("%u-", static_cast<uint32_t>(slot_idx)));
852     } else {
853       free_list_str.append(StringPrintf("%u", static_cast<uint32_t>(slot_idx)));
854     }
855   }
856   return free_list_str;
857 }
858 
Dump()859 std::string RosAlloc::Run::Dump() {
860   size_t idx = size_bracket_idx_;
861   std::ostringstream stream;
862   stream << "RosAlloc Run = " << reinterpret_cast<void*>(this)
863          << "{ magic_num=" << static_cast<int>(magic_num_)
864          << " size_bracket_idx=" << idx
865          << " is_thread_local=" << static_cast<int>(is_thread_local_)
866          << " to_be_bulk_freed=" << static_cast<int>(to_be_bulk_freed_)
867          << " free_list=" << FreeListToStr(&free_list_)
868          << " bulk_free_list=" << FreeListToStr(&bulk_free_list_)
869          << " thread_local_list=" << FreeListToStr(&thread_local_free_list_)
870          << " }" << std::endl;
871   return stream.str();
872 }
873 
FreeSlot(void * ptr)874 void RosAlloc::Run::FreeSlot(void* ptr) {
875   DCHECK(!IsThreadLocal());
876   const uint8_t idx = size_bracket_idx_;
877   const size_t bracket_size = bracketSizes[idx];
878   Slot* slot = ToSlot(ptr);
879   // Zero out the memory.
880   // TODO: Investigate alternate memset since ptr is guaranteed to be aligned to 16.
881   memset(slot, 0, bracket_size);
882   free_list_.Add(slot);
883   if (kTraceRosAlloc) {
884     LOG(INFO) << "RosAlloc::Run::FreeSlot() : " << slot
885               << ", bracket_size=" << std::dec << bracket_size << ", slot_idx=" << SlotIndex(slot);
886   }
887 }
888 
MergeThreadLocalFreeListToFreeList(bool * is_all_free_after_out)889 inline bool RosAlloc::Run::MergeThreadLocalFreeListToFreeList(bool* is_all_free_after_out) {
890   DCHECK(IsThreadLocal());
891   // Merge the thread local free list into the free list and clear the thread local free list.
892   const uint8_t idx = size_bracket_idx_;
893   size_t thread_local_free_list_size = thread_local_free_list_.Size();
894   const size_t size_before = free_list_.Size();
895   free_list_.Merge(&thread_local_free_list_);
896   const size_t size_after = free_list_.Size();
897   DCHECK_EQ(size_before < size_after, thread_local_free_list_size > 0);
898   DCHECK_LE(size_before, size_after);
899   *is_all_free_after_out = free_list_.Size() == numOfSlots[idx];
900   // Return true at least one slot was added to the free list.
901   return size_before < size_after;
902 }
903 
MergeBulkFreeListToFreeList()904 inline void RosAlloc::Run::MergeBulkFreeListToFreeList() {
905   DCHECK(!IsThreadLocal());
906   // Merge the bulk free list into the free list and clear the bulk free list.
907   free_list_.Merge(&bulk_free_list_);
908 }
909 
MergeBulkFreeListToThreadLocalFreeList()910 inline void RosAlloc::Run::MergeBulkFreeListToThreadLocalFreeList() {
911   DCHECK(IsThreadLocal());
912   // Merge the bulk free list into the thread local free list and clear the bulk free list.
913   thread_local_free_list_.Merge(&bulk_free_list_);
914 }
915 
AddToThreadLocalFreeList(void * ptr)916 inline void RosAlloc::Run::AddToThreadLocalFreeList(void* ptr) {
917   DCHECK(IsThreadLocal());
918   AddToFreeListShared(ptr, &thread_local_free_list_, __FUNCTION__);
919 }
920 
AddToBulkFreeList(void * ptr)921 inline size_t RosAlloc::Run::AddToBulkFreeList(void* ptr) {
922   return AddToFreeListShared(ptr, &bulk_free_list_, __FUNCTION__);
923 }
924 
AddToFreeListShared(void * ptr,SlotFreeList<true> * free_list,const char * caller_name)925 inline size_t RosAlloc::Run::AddToFreeListShared(void* ptr,
926                                                  SlotFreeList<true>* free_list,
927                                                  const char* caller_name) {
928   const uint8_t idx = size_bracket_idx_;
929   const size_t bracket_size = bracketSizes[idx];
930   Slot* slot = ToSlot(ptr);
931   memset(slot, 0, bracket_size);
932   free_list->Add(slot);
933   if (kTraceRosAlloc) {
934     LOG(INFO) << "RosAlloc::Run::" << caller_name << "() : " << ptr
935               << ", bracket_size=" << std::dec << bracket_size << ", slot_idx=" << SlotIndex(slot);
936   }
937   return bracket_size;
938 }
939 
ZeroHeaderAndSlotHeaders()940 inline void RosAlloc::Run::ZeroHeaderAndSlotHeaders() {
941   DCHECK(IsAllFree());
942   const uint8_t idx = size_bracket_idx_;
943   // Zero the slot header (next pointers).
944   for (Slot* slot = free_list_.Head(); slot != nullptr; ) {
945     Slot* next_slot = slot->Next();
946     slot->Clear();
947     slot = next_slot;
948   }
949   // Zero the header.
950   memset(this, 0, headerSizes[idx]);
951   // Check that the entire run is all zero.
952   if (kIsDebugBuild) {
953     const size_t size = numOfPages[idx] * kPageSize;
954     const uintptr_t* word_ptr = reinterpret_cast<uintptr_t*>(this);
955     for (size_t i = 0; i < size / sizeof(uintptr_t); ++i) {
956       CHECK_EQ(word_ptr[i], 0U) << "words don't match at index " << i;
957     }
958   }
959 }
960 
ZeroData()961 inline void RosAlloc::Run::ZeroData() {
962   const uint8_t idx = size_bracket_idx_;
963   uint8_t* slot_begin = reinterpret_cast<uint8_t*>(FirstSlot());
964   memset(slot_begin, 0, numOfSlots[idx] * bracketSizes[idx]);
965 }
966 
InspectAllSlots(void (* handler)(void * start,void * end,size_t used_bytes,void * callback_arg),void * arg)967 void RosAlloc::Run::InspectAllSlots(void (*handler)(void* start, void* end, size_t used_bytes, void* callback_arg),
968                                     void* arg) {
969   size_t idx = size_bracket_idx_;
970   uint8_t* slot_base = reinterpret_cast<uint8_t*>(this) + headerSizes[idx];
971   size_t num_slots = numOfSlots[idx];
972   size_t bracket_size = IndexToBracketSize(idx);
973   DCHECK_EQ(slot_base + num_slots * bracket_size,
974             reinterpret_cast<uint8_t*>(this) + numOfPages[idx] * kPageSize);
975   // Free slots are on the free list and the allocated/used slots are not. We traverse the free list
976   // to find out and record which slots are free in the is_free array.
977   std::unique_ptr<bool[]> is_free(new bool[num_slots]());  // zero initialized
978   for (Slot* slot = free_list_.Head(); slot != nullptr; slot = slot->Next()) {
979     size_t slot_idx = SlotIndex(slot);
980     DCHECK_LT(slot_idx, num_slots);
981     is_free[slot_idx] = true;
982   }
983   if (IsThreadLocal()) {
984     for (Slot* slot = thread_local_free_list_.Head(); slot != nullptr; slot = slot->Next()) {
985       size_t slot_idx = SlotIndex(slot);
986       DCHECK_LT(slot_idx, num_slots);
987       is_free[slot_idx] = true;
988     }
989   }
990   for (size_t slot_idx = 0; slot_idx < num_slots; ++slot_idx) {
991     uint8_t* slot_addr = slot_base + slot_idx * bracket_size;
992     if (!is_free[slot_idx]) {
993       handler(slot_addr, slot_addr + bracket_size, bracket_size, arg);
994     } else {
995       handler(slot_addr, slot_addr + bracket_size, 0, arg);
996     }
997   }
998 }
999 
1000 // If true, read the page map entries in BulkFree() without using the
1001 // lock for better performance, assuming that the existence of an
1002 // allocated chunk/pointer being freed in BulkFree() guarantees that
1003 // the page map entry won't change.
1004 static constexpr bool kReadPageMapEntryWithoutLockInBulkFree = true;
1005 
BulkFree(Thread * self,void ** ptrs,size_t num_ptrs)1006 size_t RosAlloc::BulkFree(Thread* self, void** ptrs, size_t num_ptrs) {
1007   size_t freed_bytes = 0;
1008   if ((false)) {
1009     // Used only to test Free() as GC uses only BulkFree().
1010     for (size_t i = 0; i < num_ptrs; ++i) {
1011       freed_bytes += FreeInternal(self, ptrs[i]);
1012     }
1013     return freed_bytes;
1014   }
1015 
1016   WriterMutexLock wmu(self, bulk_free_lock_);
1017 
1018   // First mark slots to free in the bulk free bit map without locking the
1019   // size bracket locks. On host, unordered_set is faster than vector + flag.
1020 #ifdef ART_TARGET_ANDROID
1021   std::vector<Run*> runs;
1022 #else
1023   std::unordered_set<Run*, hash_run, eq_run> runs;
1024 #endif
1025   for (size_t i = 0; i < num_ptrs; i++) {
1026     void* ptr = ptrs[i];
1027     DCHECK_LE(base_, ptr);
1028     DCHECK_LT(ptr, base_ + footprint_);
1029     size_t pm_idx = RoundDownToPageMapIndex(ptr);
1030     Run* run = nullptr;
1031     if (kReadPageMapEntryWithoutLockInBulkFree) {
1032       // Read the page map entries without locking the lock.
1033       uint8_t page_map_entry = page_map_[pm_idx];
1034       if (kTraceRosAlloc) {
1035         LOG(INFO) << "RosAlloc::BulkFree() : " << std::hex << ptr << ", pm_idx="
1036                   << std::dec << pm_idx
1037                   << ", page_map_entry=" << static_cast<int>(page_map_entry);
1038       }
1039       if (LIKELY(page_map_entry == kPageMapRun)) {
1040         run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize);
1041       } else if (LIKELY(page_map_entry == kPageMapRunPart)) {
1042         size_t pi = pm_idx;
1043         // Find the beginning of the run.
1044         do {
1045           --pi;
1046           DCHECK_LT(pi, capacity_ / kPageSize);
1047         } while (page_map_[pi] != kPageMapRun);
1048         run = reinterpret_cast<Run*>(base_ + pi * kPageSize);
1049       } else if (page_map_entry == kPageMapLargeObject) {
1050         MutexLock mu(self, lock_);
1051         freed_bytes += FreePages(self, ptr, false);
1052         continue;
1053       } else {
1054         LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_entry);
1055       }
1056     } else {
1057       // Read the page map entries with a lock.
1058       MutexLock mu(self, lock_);
1059       DCHECK_LT(pm_idx, page_map_size_);
1060       uint8_t page_map_entry = page_map_[pm_idx];
1061       if (kTraceRosAlloc) {
1062         LOG(INFO) << "RosAlloc::BulkFree() : " << std::hex << ptr << ", pm_idx="
1063                   << std::dec << pm_idx
1064                   << ", page_map_entry=" << static_cast<int>(page_map_entry);
1065       }
1066       if (LIKELY(page_map_entry == kPageMapRun)) {
1067         run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize);
1068       } else if (LIKELY(page_map_entry == kPageMapRunPart)) {
1069         size_t pi = pm_idx;
1070         // Find the beginning of the run.
1071         do {
1072           --pi;
1073           DCHECK_LT(pi, capacity_ / kPageSize);
1074         } while (page_map_[pi] != kPageMapRun);
1075         run = reinterpret_cast<Run*>(base_ + pi * kPageSize);
1076       } else if (page_map_entry == kPageMapLargeObject) {
1077         freed_bytes += FreePages(self, ptr, false);
1078         continue;
1079       } else {
1080         LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_entry);
1081       }
1082     }
1083     DCHECK(run != nullptr);
1084     DCHECK_EQ(run->magic_num_, kMagicNum);
1085     // Set the bit in the bulk free bit map.
1086     freed_bytes += run->AddToBulkFreeList(ptr);
1087 #ifdef ART_TARGET_ANDROID
1088     if (!run->to_be_bulk_freed_) {
1089       run->to_be_bulk_freed_ = true;
1090       runs.push_back(run);
1091     }
1092 #else
1093     runs.insert(run);
1094 #endif
1095   }
1096 
1097   // Now, iterate over the affected runs and update the alloc bit map
1098   // based on the bulk free bit map (for non-thread-local runs) and
1099   // union the bulk free bit map into the thread-local free bit map
1100   // (for thread-local runs.)
1101   for (Run* run : runs) {
1102 #ifdef ART_TARGET_ANDROID
1103     DCHECK(run->to_be_bulk_freed_);
1104     run->to_be_bulk_freed_ = false;
1105 #endif
1106     size_t idx = run->size_bracket_idx_;
1107     MutexLock brackets_mu(self, *size_bracket_locks_[idx]);
1108     if (run->IsThreadLocal()) {
1109       DCHECK_LT(run->size_bracket_idx_, kNumThreadLocalSizeBrackets);
1110       DCHECK(non_full_runs_[idx].find(run) == non_full_runs_[idx].end());
1111       DCHECK(full_runs_[idx].find(run) == full_runs_[idx].end());
1112       run->MergeBulkFreeListToThreadLocalFreeList();
1113       if (kTraceRosAlloc) {
1114         LOG(INFO) << "RosAlloc::BulkFree() : Freed slot(s) in a thread local run 0x"
1115                   << std::hex << reinterpret_cast<intptr_t>(run);
1116       }
1117       DCHECK(run->IsThreadLocal());
1118       // A thread local run will be kept as a thread local even if
1119       // it's become all free.
1120     } else {
1121       bool run_was_full = run->IsFull();
1122       run->MergeBulkFreeListToFreeList();
1123       if (kTraceRosAlloc) {
1124         LOG(INFO) << "RosAlloc::BulkFree() : Freed slot(s) in a run 0x" << std::hex
1125                   << reinterpret_cast<intptr_t>(run);
1126       }
1127       // Check if the run should be moved to non_full_runs_ or
1128       // free_page_runs_.
1129       auto* non_full_runs = &non_full_runs_[idx];
1130       auto* full_runs = kIsDebugBuild ? &full_runs_[idx] : nullptr;
1131       if (run->IsAllFree()) {
1132         // It has just become completely free. Free the pages of the
1133         // run.
1134         bool run_was_current = run == current_runs_[idx];
1135         if (run_was_current) {
1136           DCHECK(full_runs->find(run) == full_runs->end());
1137           DCHECK(non_full_runs->find(run) == non_full_runs->end());
1138           // If it was a current run, reuse it.
1139         } else if (run_was_full) {
1140           // If it was full, remove it from the full run set (debug
1141           // only.)
1142           if (kIsDebugBuild) {
1143             std::unordered_set<Run*, hash_run, eq_run>::iterator pos = full_runs->find(run);
1144             DCHECK(pos != full_runs->end());
1145             full_runs->erase(pos);
1146             if (kTraceRosAlloc) {
1147               LOG(INFO) << "RosAlloc::BulkFree() : Erased run 0x" << std::hex
1148                         << reinterpret_cast<intptr_t>(run)
1149                         << " from full_runs_";
1150             }
1151             DCHECK(full_runs->find(run) == full_runs->end());
1152           }
1153         } else {
1154           // If it was in a non full run set, remove it from the set.
1155           DCHECK(full_runs->find(run) == full_runs->end());
1156           DCHECK(non_full_runs->find(run) != non_full_runs->end());
1157           non_full_runs->erase(run);
1158           if (kTraceRosAlloc) {
1159             LOG(INFO) << "RosAlloc::BulkFree() : Erased run 0x" << std::hex
1160                       << reinterpret_cast<intptr_t>(run)
1161                       << " from non_full_runs_";
1162           }
1163           DCHECK(non_full_runs->find(run) == non_full_runs->end());
1164         }
1165         if (!run_was_current) {
1166           run->ZeroHeaderAndSlotHeaders();
1167           MutexLock lock_mu(self, lock_);
1168           FreePages(self, run, true);
1169         }
1170       } else {
1171         // It is not completely free. If it wasn't the current run or
1172         // already in the non-full run set (i.e., it was full) insert
1173         // it into the non-full run set.
1174         if (run == current_runs_[idx]) {
1175           DCHECK(non_full_runs->find(run) == non_full_runs->end());
1176           DCHECK(full_runs->find(run) == full_runs->end());
1177           // If it was a current run, keep it.
1178         } else if (run_was_full) {
1179           // If it was full, remove it from the full run set (debug
1180           // only) and insert into the non-full run set.
1181           DCHECK(full_runs->find(run) != full_runs->end());
1182           DCHECK(non_full_runs->find(run) == non_full_runs->end());
1183           if (kIsDebugBuild) {
1184             full_runs->erase(run);
1185             if (kTraceRosAlloc) {
1186               LOG(INFO) << "RosAlloc::BulkFree() : Erased run 0x" << std::hex
1187                         << reinterpret_cast<intptr_t>(run)
1188                         << " from full_runs_";
1189             }
1190           }
1191           non_full_runs->insert(run);
1192           if (kTraceRosAlloc) {
1193             LOG(INFO) << "RosAlloc::BulkFree() : Inserted run 0x" << std::hex
1194                       << reinterpret_cast<intptr_t>(run)
1195                       << " into non_full_runs_[" << std::dec << idx;
1196           }
1197         } else {
1198           // If it was not full, so leave it in the non full run set.
1199           DCHECK(full_runs->find(run) == full_runs->end());
1200           DCHECK(non_full_runs->find(run) != non_full_runs->end());
1201         }
1202       }
1203     }
1204   }
1205   return freed_bytes;
1206 }
1207 
DumpPageMap()1208 std::string RosAlloc::DumpPageMap() {
1209   std::ostringstream stream;
1210   stream << "RosAlloc PageMap: " << std::endl;
1211   lock_.AssertHeld(Thread::Current());
1212   size_t end = page_map_size_;
1213   FreePageRun* curr_fpr = nullptr;
1214   size_t curr_fpr_size = 0;
1215   size_t remaining_curr_fpr_size = 0;
1216   size_t num_running_empty_pages = 0;
1217   for (size_t i = 0; i < end; ++i) {
1218     uint8_t pm = page_map_[i];
1219     switch (pm) {
1220       case kPageMapReleased:
1221         // Fall-through.
1222       case kPageMapEmpty: {
1223         FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize);
1224         if (free_page_runs_.find(fpr) != free_page_runs_.end()) {
1225           // Encountered a fresh free page run.
1226           DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0));
1227           DCHECK(fpr->IsFree());
1228           DCHECK(curr_fpr == nullptr);
1229           DCHECK_EQ(curr_fpr_size, static_cast<size_t>(0));
1230           curr_fpr = fpr;
1231           curr_fpr_size = fpr->ByteSize(this);
1232           DCHECK_EQ(curr_fpr_size % kPageSize, static_cast<size_t>(0));
1233           remaining_curr_fpr_size = curr_fpr_size - kPageSize;
1234           stream << "[" << i << "]=" << (pm == kPageMapReleased ? "Released" : "Empty")
1235                  << " (FPR start) fpr_size=" << curr_fpr_size
1236                  << " remaining_fpr_size=" << remaining_curr_fpr_size << std::endl;
1237           if (remaining_curr_fpr_size == 0) {
1238             // Reset at the end of the current free page run.
1239             curr_fpr = nullptr;
1240             curr_fpr_size = 0;
1241           }
1242           stream << "curr_fpr=0x" << std::hex << reinterpret_cast<intptr_t>(curr_fpr) << std::endl;
1243           DCHECK_EQ(num_running_empty_pages, static_cast<size_t>(0));
1244         } else {
1245           // Still part of the current free page run.
1246           DCHECK_NE(num_running_empty_pages, static_cast<size_t>(0));
1247           DCHECK(curr_fpr != nullptr && curr_fpr_size > 0 && remaining_curr_fpr_size > 0);
1248           DCHECK_EQ(remaining_curr_fpr_size % kPageSize, static_cast<size_t>(0));
1249           DCHECK_GE(remaining_curr_fpr_size, static_cast<size_t>(kPageSize));
1250           remaining_curr_fpr_size -= kPageSize;
1251           stream << "[" << i << "]=Empty (FPR part)"
1252                  << " remaining_fpr_size=" << remaining_curr_fpr_size << std::endl;
1253           if (remaining_curr_fpr_size == 0) {
1254             // Reset at the end of the current free page run.
1255             curr_fpr = nullptr;
1256             curr_fpr_size = 0;
1257           }
1258         }
1259         num_running_empty_pages++;
1260         break;
1261       }
1262       case kPageMapLargeObject: {
1263         DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0));
1264         num_running_empty_pages = 0;
1265         stream << "[" << i << "]=Large (start)" << std::endl;
1266         break;
1267       }
1268       case kPageMapLargeObjectPart:
1269         DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0));
1270         num_running_empty_pages = 0;
1271         stream << "[" << i << "]=Large (part)" << std::endl;
1272         break;
1273       case kPageMapRun: {
1274         DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0));
1275         num_running_empty_pages = 0;
1276         Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize);
1277         size_t idx = run->size_bracket_idx_;
1278         stream << "[" << i << "]=Run (start)"
1279                << " idx=" << idx
1280                << " numOfPages=" << numOfPages[idx]
1281                << " is_thread_local=" << run->is_thread_local_
1282                << " is_all_free=" << (run->IsAllFree() ? 1 : 0)
1283                << std::endl;
1284         break;
1285       }
1286       case kPageMapRunPart:
1287         DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0));
1288         num_running_empty_pages = 0;
1289         stream << "[" << i << "]=Run (part)" << std::endl;
1290         break;
1291       default:
1292         stream << "[" << i << "]=Unrecognizable page map type: " << pm;
1293         break;
1294     }
1295   }
1296   return stream.str();
1297 }
1298 
UsableSize(const void * ptr)1299 size_t RosAlloc::UsableSize(const void* ptr) {
1300   DCHECK_LE(base_, ptr);
1301   DCHECK_LT(ptr, base_ + footprint_);
1302   size_t pm_idx = RoundDownToPageMapIndex(ptr);
1303   MutexLock mu(Thread::Current(), lock_);
1304   switch (page_map_[pm_idx]) {
1305     case kPageMapReleased:
1306       // Fall-through.
1307     case kPageMapEmpty:
1308       LOG(FATAL) << "Unreachable - " << __PRETTY_FUNCTION__ << ": pm_idx=" << pm_idx << ", ptr="
1309                  << std::hex << reinterpret_cast<intptr_t>(ptr);
1310       UNREACHABLE();
1311     case kPageMapLargeObject: {
1312       size_t num_pages = 1;
1313       size_t idx = pm_idx + 1;
1314       size_t end = page_map_size_;
1315       while (idx < end && page_map_[idx] == kPageMapLargeObjectPart) {
1316         num_pages++;
1317         idx++;
1318       }
1319       return num_pages * kPageSize;
1320     }
1321     case kPageMapLargeObjectPart:
1322       LOG(FATAL) << "Unreachable - " << __PRETTY_FUNCTION__ << ": pm_idx=" << pm_idx << ", ptr="
1323                  << std::hex << reinterpret_cast<intptr_t>(ptr);
1324       UNREACHABLE();
1325     case kPageMapRun:
1326     case kPageMapRunPart: {
1327       // Find the beginning of the run.
1328       while (page_map_[pm_idx] != kPageMapRun) {
1329         pm_idx--;
1330         DCHECK_LT(pm_idx, capacity_ / kPageSize);
1331       }
1332       DCHECK_EQ(page_map_[pm_idx], kPageMapRun);
1333       Run* run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize);
1334       DCHECK_EQ(run->magic_num_, kMagicNum);
1335       size_t idx = run->size_bracket_idx_;
1336       size_t offset_from_slot_base = reinterpret_cast<const uint8_t*>(ptr)
1337           - (reinterpret_cast<uint8_t*>(run) + headerSizes[idx]);
1338       DCHECK_EQ(offset_from_slot_base % bracketSizes[idx], static_cast<size_t>(0));
1339       return IndexToBracketSize(idx);
1340     }
1341     default: {
1342       LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_[pm_idx]);
1343       UNREACHABLE();
1344     }
1345   }
1346 }
1347 
Trim()1348 bool RosAlloc::Trim() {
1349   MutexLock mu(Thread::Current(), lock_);
1350   FreePageRun* last_free_page_run;
1351   DCHECK_EQ(footprint_ % kPageSize, static_cast<size_t>(0));
1352   auto it = free_page_runs_.rbegin();
1353   if (it != free_page_runs_.rend() && (last_free_page_run = *it)->End(this) == base_ + footprint_) {
1354     // Remove the last free page run, if any.
1355     DCHECK(last_free_page_run->IsFree());
1356     DCHECK(IsFreePage(ToPageMapIndex(last_free_page_run)));
1357     DCHECK_EQ(last_free_page_run->ByteSize(this) % kPageSize, static_cast<size_t>(0));
1358     DCHECK_EQ(last_free_page_run->End(this), base_ + footprint_);
1359     free_page_runs_.erase(last_free_page_run);
1360     size_t decrement = last_free_page_run->ByteSize(this);
1361     size_t new_footprint = footprint_ - decrement;
1362     DCHECK_EQ(new_footprint % kPageSize, static_cast<size_t>(0));
1363     size_t new_num_of_pages = new_footprint / kPageSize;
1364     DCHECK_GE(page_map_size_, new_num_of_pages);
1365     // Zero out the tail of the page map.
1366     uint8_t* zero_begin = const_cast<uint8_t*>(page_map_) + new_num_of_pages;
1367     uint8_t* madvise_begin = AlignUp(zero_begin, kPageSize);
1368     DCHECK_LE(madvise_begin, page_map_mem_map_.End());
1369     size_t madvise_size = page_map_mem_map_.End() - madvise_begin;
1370     if (madvise_size > 0) {
1371       DCHECK_ALIGNED(madvise_begin, kPageSize);
1372       DCHECK_EQ(RoundUp(madvise_size, kPageSize), madvise_size);
1373       if (!kMadviseZeroes) {
1374         memset(madvise_begin, 0, madvise_size);
1375       }
1376       CHECK_EQ(madvise(madvise_begin, madvise_size, MADV_DONTNEED), 0);
1377     }
1378     if (madvise_begin - zero_begin) {
1379       memset(zero_begin, 0, madvise_begin - zero_begin);
1380     }
1381     page_map_size_ = new_num_of_pages;
1382     free_page_run_size_map_.resize(new_num_of_pages);
1383     DCHECK_EQ(free_page_run_size_map_.size(), new_num_of_pages);
1384     ArtRosAllocMoreCore(this, -(static_cast<intptr_t>(decrement)));
1385     if (kTraceRosAlloc) {
1386       LOG(INFO) << "RosAlloc::Trim() : decreased the footprint from "
1387                 << footprint_ << " to " << new_footprint;
1388     }
1389     DCHECK_LT(new_footprint, footprint_);
1390     DCHECK_LT(new_footprint, capacity_);
1391     footprint_ = new_footprint;
1392     return true;
1393   }
1394   return false;
1395 }
1396 
InspectAll(void (* handler)(void * start,void * end,size_t used_bytes,void * callback_arg),void * arg)1397 void RosAlloc::InspectAll(void (*handler)(void* start, void* end, size_t used_bytes, void* callback_arg),
1398                           void* arg) {
1399   // Note: no need to use this to release pages as we already do so in FreePages().
1400   if (handler == nullptr) {
1401     return;
1402   }
1403   MutexLock mu(Thread::Current(), lock_);
1404   size_t pm_end = page_map_size_;
1405   size_t i = 0;
1406   while (i < pm_end) {
1407     uint8_t pm = page_map_[i];
1408     switch (pm) {
1409       case kPageMapReleased:
1410         // Fall-through.
1411       case kPageMapEmpty: {
1412         // The start of a free page run.
1413         FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize);
1414         DCHECK(free_page_runs_.find(fpr) != free_page_runs_.end());
1415         size_t fpr_size = fpr->ByteSize(this);
1416         DCHECK_ALIGNED(fpr_size, kPageSize);
1417         void* start = fpr;
1418         if (kIsDebugBuild) {
1419           // In the debug build, the first page of a free page run
1420           // contains a magic number for debugging. Exclude it.
1421           start = reinterpret_cast<uint8_t*>(fpr) + kPageSize;
1422         }
1423         void* end = reinterpret_cast<uint8_t*>(fpr) + fpr_size;
1424         handler(start, end, 0, arg);
1425         size_t num_pages = fpr_size / kPageSize;
1426         if (kIsDebugBuild) {
1427           for (size_t j = i + 1; j < i + num_pages; ++j) {
1428             DCHECK(IsFreePage(j));
1429           }
1430         }
1431         i += fpr_size / kPageSize;
1432         DCHECK_LE(i, pm_end);
1433         break;
1434       }
1435       case kPageMapLargeObject: {
1436         // The start of a large object.
1437         size_t num_pages = 1;
1438         size_t idx = i + 1;
1439         while (idx < pm_end && page_map_[idx] == kPageMapLargeObjectPart) {
1440           num_pages++;
1441           idx++;
1442         }
1443         void* start = base_ + i * kPageSize;
1444         void* end = base_ + (i + num_pages) * kPageSize;
1445         size_t used_bytes = num_pages * kPageSize;
1446         handler(start, end, used_bytes, arg);
1447         if (kIsDebugBuild) {
1448           for (size_t j = i + 1; j < i + num_pages; ++j) {
1449             DCHECK_EQ(page_map_[j], kPageMapLargeObjectPart);
1450           }
1451         }
1452         i += num_pages;
1453         DCHECK_LE(i, pm_end);
1454         break;
1455       }
1456       case kPageMapLargeObjectPart:
1457         LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm);
1458         UNREACHABLE();
1459       case kPageMapRun: {
1460         // The start of a run.
1461         Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize);
1462         DCHECK_EQ(run->magic_num_, kMagicNum);
1463         // The dedicated full run doesn't contain any real allocations, don't visit the slots in
1464         // there.
1465         run->InspectAllSlots(handler, arg);
1466         size_t num_pages = numOfPages[run->size_bracket_idx_];
1467         if (kIsDebugBuild) {
1468           for (size_t j = i + 1; j < i + num_pages; ++j) {
1469             DCHECK_EQ(page_map_[j], kPageMapRunPart);
1470           }
1471         }
1472         i += num_pages;
1473         DCHECK_LE(i, pm_end);
1474         break;
1475       }
1476       case kPageMapRunPart:
1477         LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm);
1478         UNREACHABLE();
1479       default:
1480         LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm);
1481         UNREACHABLE();
1482     }
1483   }
1484 }
1485 
Footprint()1486 size_t RosAlloc::Footprint() {
1487   MutexLock mu(Thread::Current(), lock_);
1488   return footprint_;
1489 }
1490 
FootprintLimit()1491 size_t RosAlloc::FootprintLimit() {
1492   MutexLock mu(Thread::Current(), lock_);
1493   return capacity_;
1494 }
1495 
SetFootprintLimit(size_t new_capacity)1496 void RosAlloc::SetFootprintLimit(size_t new_capacity) {
1497   MutexLock mu(Thread::Current(), lock_);
1498   DCHECK_EQ(RoundUp(new_capacity, kPageSize), new_capacity);
1499   // Only growing is supported here. But Trim() is supported.
1500   if (capacity_ < new_capacity) {
1501     CHECK_LE(new_capacity, max_capacity_);
1502     capacity_ = new_capacity;
1503     VLOG(heap) << "new capacity=" << capacity_;
1504   }
1505 }
1506 
1507 // Below may be called by mutator itself just before thread termination.
RevokeThreadLocalRuns(Thread * thread)1508 size_t RosAlloc::RevokeThreadLocalRuns(Thread* thread) {
1509   Thread* self = Thread::Current();
1510   size_t free_bytes = 0U;
1511   for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; idx++) {
1512     MutexLock mu(self, *size_bracket_locks_[idx]);
1513     Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(idx));
1514     CHECK(thread_local_run != nullptr);
1515     // Invalid means already revoked.
1516     DCHECK(thread_local_run->IsThreadLocal());
1517     if (thread_local_run != dedicated_full_run_) {
1518       // Note the thread local run may not be full here.
1519       thread->SetRosAllocRun(idx, dedicated_full_run_);
1520       DCHECK_EQ(thread_local_run->magic_num_, kMagicNum);
1521       // Count the number of free slots left.
1522       size_t num_free_slots = thread_local_run->NumberOfFreeSlots();
1523       free_bytes += num_free_slots * bracketSizes[idx];
1524       // The above bracket index lock guards thread local free list to avoid race condition
1525       // with unioning bulk free list to thread local free list by GC thread in BulkFree.
1526       // If thread local run is true, GC thread will help update thread local free list
1527       // in BulkFree. And the latest thread local free list will be merged to free list
1528       // either when this thread local run is full or when revoking this run here. In this
1529       // case the free list wll be updated. If thread local run is false, GC thread will help
1530       // merge bulk free list in next BulkFree.
1531       // Thus no need to merge bulk free list to free list again here.
1532       bool dont_care;
1533       thread_local_run->MergeThreadLocalFreeListToFreeList(&dont_care);
1534       thread_local_run->SetIsThreadLocal(false);
1535       DCHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end());
1536       DCHECK(full_runs_[idx].find(thread_local_run) == full_runs_[idx].end());
1537       RevokeRun(self, idx, thread_local_run);
1538     }
1539   }
1540   return free_bytes;
1541 }
1542 
RevokeRun(Thread * self,size_t idx,Run * run)1543 void RosAlloc::RevokeRun(Thread* self, size_t idx, Run* run) {
1544   size_bracket_locks_[idx]->AssertHeld(self);
1545   DCHECK(run != dedicated_full_run_);
1546   if (run->IsFull()) {
1547     if (kIsDebugBuild) {
1548       full_runs_[idx].insert(run);
1549       DCHECK(full_runs_[idx].find(run) != full_runs_[idx].end());
1550       if (kTraceRosAlloc) {
1551         LOG(INFO) << __PRETTY_FUNCTION__  << " : Inserted run 0x" << std::hex
1552                   << reinterpret_cast<intptr_t>(run)
1553                   << " into full_runs_[" << std::dec << idx << "]";
1554       }
1555     }
1556   } else if (run->IsAllFree()) {
1557     run->ZeroHeaderAndSlotHeaders();
1558     MutexLock mu(self, lock_);
1559     FreePages(self, run, true);
1560   } else {
1561     non_full_runs_[idx].insert(run);
1562     DCHECK(non_full_runs_[idx].find(run) != non_full_runs_[idx].end());
1563     if (kTraceRosAlloc) {
1564       LOG(INFO) << __PRETTY_FUNCTION__ << " : Inserted run 0x" << std::hex
1565                 << reinterpret_cast<intptr_t>(run)
1566                 << " into non_full_runs_[" << std::dec << idx << "]";
1567     }
1568   }
1569 }
1570 
RevokeThreadUnsafeCurrentRuns()1571 void RosAlloc::RevokeThreadUnsafeCurrentRuns() {
1572   // Revoke the current runs which share the same idx as thread local runs.
1573   Thread* self = Thread::Current();
1574   for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; ++idx) {
1575     MutexLock mu(self, *size_bracket_locks_[idx]);
1576     if (current_runs_[idx] != dedicated_full_run_) {
1577       RevokeRun(self, idx, current_runs_[idx]);
1578       current_runs_[idx] = dedicated_full_run_;
1579     }
1580   }
1581 }
1582 
RevokeAllThreadLocalRuns()1583 size_t RosAlloc::RevokeAllThreadLocalRuns() {
1584   // This is called when a mutator thread won't allocate such as at
1585   // the Zygote creation time or during the GC pause.
1586   MutexLock mu(Thread::Current(), *Locks::runtime_shutdown_lock_);
1587   MutexLock mu2(Thread::Current(), *Locks::thread_list_lock_);
1588   std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
1589   size_t free_bytes = 0U;
1590   for (Thread* thread : thread_list) {
1591     free_bytes += RevokeThreadLocalRuns(thread);
1592   }
1593   RevokeThreadUnsafeCurrentRuns();
1594   return free_bytes;
1595 }
1596 
AssertThreadLocalRunsAreRevoked(Thread * thread)1597 void RosAlloc::AssertThreadLocalRunsAreRevoked(Thread* thread) {
1598   if (kIsDebugBuild) {
1599     Thread* self = Thread::Current();
1600     // Avoid race conditions on the bulk free bit maps with BulkFree() (GC).
1601     ReaderMutexLock wmu(self, bulk_free_lock_);
1602     for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; idx++) {
1603       MutexLock mu(self, *size_bracket_locks_[idx]);
1604       Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(idx));
1605       DCHECK(thread_local_run == nullptr || thread_local_run == dedicated_full_run_);
1606     }
1607   }
1608 }
1609 
AssertAllThreadLocalRunsAreRevoked()1610 void RosAlloc::AssertAllThreadLocalRunsAreRevoked() {
1611   if (kIsDebugBuild) {
1612     Thread* self = Thread::Current();
1613     MutexLock shutdown_mu(self, *Locks::runtime_shutdown_lock_);
1614     MutexLock thread_list_mu(self, *Locks::thread_list_lock_);
1615     std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
1616     for (Thread* t : thread_list) {
1617       AssertThreadLocalRunsAreRevoked(t);
1618     }
1619     for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; ++idx) {
1620       MutexLock brackets_mu(self, *size_bracket_locks_[idx]);
1621       CHECK_EQ(current_runs_[idx], dedicated_full_run_);
1622     }
1623   }
1624 }
1625 
Initialize()1626 void RosAlloc::Initialize() {
1627   // bracketSizes.
1628   static_assert(kNumRegularSizeBrackets == kNumOfSizeBrackets - 2,
1629                 "There should be two non-regular brackets");
1630   for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
1631     if (i < kNumThreadLocalSizeBrackets) {
1632       bracketSizes[i] = kThreadLocalBracketQuantumSize * (i + 1);
1633     } else if (i < kNumRegularSizeBrackets) {
1634       bracketSizes[i] = kBracketQuantumSize * (i - kNumThreadLocalSizeBrackets + 1) +
1635           (kThreadLocalBracketQuantumSize *  kNumThreadLocalSizeBrackets);
1636     } else if (i == kNumOfSizeBrackets - 2) {
1637       bracketSizes[i] = 1 * KB;
1638     } else {
1639       DCHECK_EQ(i, kNumOfSizeBrackets - 1);
1640       bracketSizes[i] = 2 * KB;
1641     }
1642     if (kTraceRosAlloc) {
1643       LOG(INFO) << "bracketSizes[" << i << "]=" << bracketSizes[i];
1644     }
1645   }
1646   // numOfPages.
1647   for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
1648     if (i < kNumThreadLocalSizeBrackets) {
1649       numOfPages[i] = 1;
1650     } else if (i < (kNumThreadLocalSizeBrackets + kNumRegularSizeBrackets) / 2) {
1651       numOfPages[i] = 1;
1652     } else if (i < kNumRegularSizeBrackets) {
1653       numOfPages[i] = 1;
1654     } else if (i == kNumOfSizeBrackets - 2) {
1655       numOfPages[i] = 2;
1656     } else {
1657       DCHECK_EQ(i, kNumOfSizeBrackets - 1);
1658       numOfPages[i] = 4;
1659     }
1660     if (kTraceRosAlloc) {
1661       LOG(INFO) << "numOfPages[" << i << "]=" << numOfPages[i];
1662     }
1663   }
1664   // Compute numOfSlots and slotOffsets.
1665   for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
1666     size_t bracket_size = bracketSizes[i];
1667     size_t run_size = kPageSize * numOfPages[i];
1668     size_t max_num_of_slots = run_size / bracket_size;
1669     // Compute the actual number of slots by taking the header and
1670     // alignment into account.
1671     size_t fixed_header_size = RoundUp(Run::fixed_header_size(), sizeof(uint64_t));
1672     DCHECK_EQ(fixed_header_size, 80U);
1673     size_t header_size = 0;
1674     size_t num_of_slots = 0;
1675     // Search for the maximum number of slots that allows enough space
1676     // for the header.
1677     for (int s = max_num_of_slots; s >= 0; s--) {
1678       size_t tmp_slots_size = bracket_size * s;
1679       size_t tmp_unaligned_header_size = fixed_header_size;
1680       // Align up the unaligned header size. bracket_size may not be a power of two.
1681       size_t tmp_header_size = (tmp_unaligned_header_size % bracket_size == 0) ?
1682           tmp_unaligned_header_size :
1683           tmp_unaligned_header_size + (bracket_size - tmp_unaligned_header_size % bracket_size);
1684       DCHECK_EQ(tmp_header_size % bracket_size, 0U);
1685       DCHECK_EQ(tmp_header_size % sizeof(uint64_t), 0U);
1686       if (tmp_slots_size + tmp_header_size <= run_size) {
1687         // Found the right number of slots, that is, there was enough
1688         // space for the header (including the bit maps.)
1689         num_of_slots = s;
1690         header_size = tmp_header_size;
1691         break;
1692       }
1693     }
1694     DCHECK_GT(num_of_slots, 0U) << i;
1695     DCHECK_GT(header_size, 0U) << i;
1696     // Add the padding for the alignment remainder.
1697     header_size += run_size % bracket_size;
1698     DCHECK_EQ(header_size + num_of_slots * bracket_size, run_size);
1699     numOfSlots[i] = num_of_slots;
1700     headerSizes[i] = header_size;
1701     if (kTraceRosAlloc) {
1702       LOG(INFO) << "numOfSlots[" << i << "]=" << numOfSlots[i]
1703                 << ", headerSizes[" << i << "]=" << headerSizes[i];
1704     }
1705   }
1706   // Set up the dedicated full run so that nobody can successfully allocate from it.
1707   if (kIsDebugBuild) {
1708     dedicated_full_run_->magic_num_ = kMagicNum;
1709   }
1710   // It doesn't matter which size bracket we use since the main goal is to have the allocation
1711   // fail 100% of the time you attempt to allocate into the dedicated full run.
1712   dedicated_full_run_->size_bracket_idx_ = 0;
1713   DCHECK_EQ(dedicated_full_run_->FreeList()->Size(), 0U);  // It looks full.
1714   dedicated_full_run_->SetIsThreadLocal(true);
1715 
1716   // The smallest bracket size must be at least as large as the sizeof(Slot).
1717   DCHECK_LE(sizeof(Slot), bracketSizes[0]) << "sizeof(Slot) <= the smallest bracket size";
1718   // Check the invariants between the max bracket sizes and the number of brackets.
1719   DCHECK_EQ(kMaxThreadLocalBracketSize, bracketSizes[kNumThreadLocalSizeBrackets - 1]);
1720   DCHECK_EQ(kMaxRegularBracketSize, bracketSizes[kNumRegularSizeBrackets - 1]);
1721 }
1722 
BytesAllocatedCallback(void * start ATTRIBUTE_UNUSED,void * end ATTRIBUTE_UNUSED,size_t used_bytes,void * arg)1723 void RosAlloc::BytesAllocatedCallback(void* start ATTRIBUTE_UNUSED, void* end ATTRIBUTE_UNUSED,
1724                                       size_t used_bytes, void* arg) {
1725   if (used_bytes == 0) {
1726     return;
1727   }
1728   size_t* bytes_allocated = reinterpret_cast<size_t*>(arg);
1729   *bytes_allocated += used_bytes;
1730 }
1731 
ObjectsAllocatedCallback(void * start ATTRIBUTE_UNUSED,void * end ATTRIBUTE_UNUSED,size_t used_bytes,void * arg)1732 void RosAlloc::ObjectsAllocatedCallback(void* start ATTRIBUTE_UNUSED, void* end ATTRIBUTE_UNUSED,
1733                                         size_t used_bytes, void* arg) {
1734   if (used_bytes == 0) {
1735     return;
1736   }
1737   size_t* objects_allocated = reinterpret_cast<size_t*>(arg);
1738   ++(*objects_allocated);
1739 }
1740 
Verify()1741 void RosAlloc::Verify() {
1742   Thread* self = Thread::Current();
1743   CHECK(Locks::mutator_lock_->IsExclusiveHeld(self))
1744       << "The mutator locks isn't exclusively locked at " << __PRETTY_FUNCTION__;
1745   MutexLock thread_list_mu(self, *Locks::thread_list_lock_);
1746   ReaderMutexLock wmu(self, bulk_free_lock_);
1747   std::vector<Run*> runs;
1748   {
1749     MutexLock lock_mu(self, lock_);
1750     size_t pm_end = page_map_size_;
1751     size_t i = 0;
1752     size_t memory_tool_modifier =  is_running_on_memory_tool_ ?
1753         2 * ::art::gc::space::kDefaultMemoryToolRedZoneBytes :  // Redzones before and after.
1754         0;
1755     while (i < pm_end) {
1756       uint8_t pm = page_map_[i];
1757       switch (pm) {
1758         case kPageMapReleased:
1759           // Fall-through.
1760         case kPageMapEmpty: {
1761           // The start of a free page run.
1762           FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize);
1763           DCHECK_EQ(fpr->magic_num_, kMagicNumFree);
1764           CHECK(free_page_runs_.find(fpr) != free_page_runs_.end())
1765               << "An empty page must belong to the free page run set";
1766           size_t fpr_size = fpr->ByteSize(this);
1767           CHECK_ALIGNED(fpr_size, kPageSize)
1768               << "A free page run size isn't page-aligned : " << fpr_size;
1769           size_t num_pages = fpr_size / kPageSize;
1770           CHECK_GT(num_pages, static_cast<uintptr_t>(0))
1771               << "A free page run size must be > 0 : " << fpr_size;
1772           for (size_t j = i + 1; j < i + num_pages; ++j) {
1773             CHECK(IsFreePage(j))
1774                 << "A mismatch between the page map table for kPageMapEmpty "
1775                 << " at page index " << j
1776                 << " and the free page run size : page index range : "
1777                 << i << " to " << (i + num_pages) << std::endl << DumpPageMap();
1778           }
1779           i += num_pages;
1780           CHECK_LE(i, pm_end) << "Page map index " << i << " out of range < " << pm_end
1781                               << std::endl << DumpPageMap();
1782           break;
1783         }
1784         case kPageMapLargeObject: {
1785           // The start of a large object.
1786           size_t num_pages = 1;
1787           size_t idx = i + 1;
1788           while (idx < pm_end && page_map_[idx] == kPageMapLargeObjectPart) {
1789             num_pages++;
1790             idx++;
1791           }
1792           uint8_t* start = base_ + i * kPageSize;
1793           if (is_running_on_memory_tool_) {
1794             start += ::art::gc::space::kDefaultMemoryToolRedZoneBytes;
1795           }
1796           mirror::Object* obj = reinterpret_cast<mirror::Object*>(start);
1797           size_t obj_size = obj->SizeOf();
1798           CHECK_GT(obj_size + memory_tool_modifier, kLargeSizeThreshold)
1799               << "A rosalloc large object size must be > " << kLargeSizeThreshold;
1800           CHECK_EQ(num_pages, RoundUp(obj_size + memory_tool_modifier, kPageSize) / kPageSize)
1801               << "A rosalloc large object size " << obj_size + memory_tool_modifier
1802               << " does not match the page map table " << (num_pages * kPageSize)
1803               << std::endl << DumpPageMap();
1804           i += num_pages;
1805           CHECK_LE(i, pm_end) << "Page map index " << i << " out of range < " << pm_end
1806                               << std::endl << DumpPageMap();
1807           break;
1808         }
1809         case kPageMapLargeObjectPart:
1810           LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm) << std::endl << DumpPageMap();
1811           UNREACHABLE();
1812         case kPageMapRun: {
1813           // The start of a run.
1814           Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize);
1815           DCHECK_EQ(run->magic_num_, kMagicNum);
1816           size_t idx = run->size_bracket_idx_;
1817           CHECK_LT(idx, kNumOfSizeBrackets) << "Out of range size bracket index : " << idx;
1818           size_t num_pages = numOfPages[idx];
1819           CHECK_GT(num_pages, static_cast<uintptr_t>(0))
1820               << "Run size must be > 0 : " << num_pages;
1821           for (size_t j = i + 1; j < i + num_pages; ++j) {
1822             CHECK_EQ(page_map_[j], kPageMapRunPart)
1823                 << "A mismatch between the page map table for kPageMapRunPart "
1824                 << " at page index " << j
1825                 << " and the run size : page index range " << i << " to " << (i + num_pages)
1826                 << std::endl << DumpPageMap();
1827           }
1828           // Don't verify the dedicated_full_run_ since it doesn't have any real allocations.
1829           runs.push_back(run);
1830           i += num_pages;
1831           CHECK_LE(i, pm_end) << "Page map index " << i << " out of range < " << pm_end
1832                               << std::endl << DumpPageMap();
1833           break;
1834         }
1835         case kPageMapRunPart:
1836           // Fall-through.
1837         default:
1838           LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm) << std::endl << DumpPageMap();
1839           UNREACHABLE();
1840       }
1841     }
1842   }
1843   std::list<Thread*> threads = Runtime::Current()->GetThreadList()->GetList();
1844   for (Thread* thread : threads) {
1845     for (size_t i = 0; i < kNumThreadLocalSizeBrackets; ++i) {
1846       MutexLock brackets_mu(self, *size_bracket_locks_[i]);
1847       Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(i));
1848       CHECK(thread_local_run != nullptr);
1849       CHECK(thread_local_run->IsThreadLocal());
1850       CHECK(thread_local_run == dedicated_full_run_ ||
1851             thread_local_run->size_bracket_idx_ == i);
1852     }
1853   }
1854   for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
1855     MutexLock brackets_mu(self, *size_bracket_locks_[i]);
1856     Run* current_run = current_runs_[i];
1857     CHECK(current_run != nullptr);
1858     if (current_run != dedicated_full_run_) {
1859       // The dedicated full run is currently marked as thread local.
1860       CHECK(!current_run->IsThreadLocal());
1861       CHECK_EQ(current_run->size_bracket_idx_, i);
1862     }
1863   }
1864   // Call Verify() here for the lock order.
1865   for (auto& run : runs) {
1866     run->Verify(self, this, is_running_on_memory_tool_);
1867   }
1868 }
1869 
Verify(Thread * self,RosAlloc * rosalloc,bool running_on_memory_tool)1870 void RosAlloc::Run::Verify(Thread* self, RosAlloc* rosalloc, bool running_on_memory_tool) {
1871   DCHECK_EQ(magic_num_, kMagicNum) << "Bad magic number : " << Dump();
1872   const size_t idx = size_bracket_idx_;
1873   CHECK_LT(idx, kNumOfSizeBrackets) << "Out of range size bracket index : " << Dump();
1874   uint8_t* slot_base = reinterpret_cast<uint8_t*>(this) + headerSizes[idx];
1875   const size_t num_slots = numOfSlots[idx];
1876   size_t bracket_size = IndexToBracketSize(idx);
1877   CHECK_EQ(slot_base + num_slots * bracket_size,
1878            reinterpret_cast<uint8_t*>(this) + numOfPages[idx] * kPageSize)
1879       << "Mismatch in the end address of the run " << Dump();
1880   // Check that the bulk free list is empty. It's only used during BulkFree().
1881   CHECK(IsBulkFreeListEmpty()) << "The bulk free isn't empty " << Dump();
1882   // Check the thread local runs, the current runs, and the run sets.
1883   if (IsThreadLocal()) {
1884     // If it's a thread local run, then it must be pointed to by an owner thread.
1885     bool owner_found = false;
1886     std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
1887     for (auto it = thread_list.begin(); it != thread_list.end(); ++it) {
1888       Thread* thread = *it;
1889       for (size_t i = 0; i < kNumThreadLocalSizeBrackets; i++) {
1890         MutexLock mu(self, *rosalloc->size_bracket_locks_[i]);
1891         Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(i));
1892         if (thread_local_run == this) {
1893           CHECK(!owner_found)
1894               << "A thread local run has more than one owner thread " << Dump();
1895           CHECK_EQ(i, idx)
1896               << "A mismatching size bracket index in a thread local run " << Dump();
1897           owner_found = true;
1898         }
1899       }
1900     }
1901     CHECK(owner_found) << "A thread local run has no owner thread " << Dump();
1902   } else {
1903     // If it's not thread local, check that the thread local free list is empty.
1904     CHECK(IsThreadLocalFreeListEmpty())
1905         << "A non-thread-local run's thread local free list isn't empty "
1906         << Dump();
1907     // Check if it's a current run for the size bracket.
1908     bool is_current_run = false;
1909     for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
1910       MutexLock mu(self, *rosalloc->size_bracket_locks_[i]);
1911       Run* current_run = rosalloc->current_runs_[i];
1912       if (idx == i) {
1913         if (this == current_run) {
1914           is_current_run = true;
1915         }
1916       } else {
1917         // If the size bucket index does not match, then it must not
1918         // be a current run.
1919         CHECK_NE(this, current_run)
1920             << "A current run points to a run with a wrong size bracket index " << Dump();
1921       }
1922     }
1923     // If it's neither a thread local or current run, then it must be
1924     // in a run set.
1925     if (!is_current_run) {
1926       MutexLock mu(self, rosalloc->lock_);
1927       auto& non_full_runs = rosalloc->non_full_runs_[idx];
1928       // If it's all free, it must be a free page run rather than a run.
1929       CHECK(!IsAllFree()) << "A free run must be in a free page run set " << Dump();
1930       if (!IsFull()) {
1931         // If it's not full, it must in the non-full run set.
1932         CHECK(non_full_runs.find(this) != non_full_runs.end())
1933             << "A non-full run isn't in the non-full run set " << Dump();
1934       } else {
1935         // If it's full, it must in the full run set (debug build only.)
1936         if (kIsDebugBuild) {
1937           auto& full_runs = rosalloc->full_runs_[idx];
1938           CHECK(full_runs.find(this) != full_runs.end())
1939               << " A full run isn't in the full run set " << Dump();
1940         }
1941       }
1942     }
1943   }
1944   // Check each slot.
1945   size_t memory_tool_modifier = running_on_memory_tool ?
1946       2 * ::art::gc::space::kDefaultMemoryToolRedZoneBytes :
1947       0U;
1948   // TODO: reuse InspectAllSlots().
1949   std::unique_ptr<bool[]> is_free(new bool[num_slots]());  // zero initialized
1950   // Mark the free slots and the remaining ones are allocated.
1951   for (Slot* slot = free_list_.Head(); slot != nullptr; slot = slot->Next()) {
1952     size_t slot_idx = SlotIndex(slot);
1953     DCHECK_LT(slot_idx, num_slots);
1954     is_free[slot_idx] = true;
1955   }
1956   if (IsThreadLocal()) {
1957     for (Slot* slot = thread_local_free_list_.Head(); slot != nullptr; slot = slot->Next()) {
1958       size_t slot_idx = SlotIndex(slot);
1959       DCHECK_LT(slot_idx, num_slots);
1960       is_free[slot_idx] = true;
1961     }
1962   }
1963   for (size_t slot_idx = 0; slot_idx < num_slots; ++slot_idx) {
1964     uint8_t* slot_addr = slot_base + slot_idx * bracket_size;
1965     if (running_on_memory_tool) {
1966       slot_addr += ::art::gc::space::kDefaultMemoryToolRedZoneBytes;
1967     }
1968     if (!is_free[slot_idx]) {
1969       // The slot is allocated
1970       mirror::Object* obj = reinterpret_cast<mirror::Object*>(slot_addr);
1971       size_t obj_size = obj->SizeOf();
1972       CHECK_LE(obj_size + memory_tool_modifier, kLargeSizeThreshold)
1973           << "A run slot contains a large object " << Dump();
1974       CHECK_EQ(SizeToIndex(obj_size + memory_tool_modifier), idx)
1975           << obj->PrettyTypeOf() << " "
1976           << "obj_size=" << obj_size << "(" << obj_size + memory_tool_modifier << "), idx=" << idx
1977           << " A run slot contains an object with wrong size " << Dump();
1978     }
1979   }
1980 }
1981 
ReleasePages()1982 size_t RosAlloc::ReleasePages() {
1983   VLOG(heap) << "RosAlloc::ReleasePages()";
1984   DCHECK(!DoesReleaseAllPages());
1985   Thread* self = Thread::Current();
1986   size_t reclaimed_bytes = 0;
1987   size_t i = 0;
1988   // Check the page map size which might have changed due to grow/shrink.
1989   while (i < page_map_size_) {
1990     // Reading the page map without a lock is racy but the race is benign since it should only
1991     // result in occasionally not releasing pages which we could release.
1992     uint8_t pm = page_map_[i];
1993     switch (pm) {
1994       case kPageMapReleased:
1995         // Fall through.
1996       case kPageMapEmpty: {
1997         // This is currently the start of a free page run.
1998         // Acquire the lock to prevent other threads racing in and modifying the page map.
1999         MutexLock mu(self, lock_);
2000         // Check that it's still empty after we acquired the lock since another thread could have
2001         // raced in and placed an allocation here.
2002         if (IsFreePage(i)) {
2003           // Free page runs can start with a released page if we coalesced a released page free
2004           // page run with an empty page run.
2005           FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize);
2006           // There is a race condition where FreePage can coalesce fpr with the previous
2007           // free page run before we acquire lock_. In that case free_page_runs_.find will not find
2008           // a run starting at fpr. To handle this race, we skip reclaiming the page range and go
2009           // to the next page.
2010           if (free_page_runs_.find(fpr) != free_page_runs_.end()) {
2011             size_t fpr_size = fpr->ByteSize(this);
2012             DCHECK_ALIGNED(fpr_size, kPageSize);
2013             uint8_t* start = reinterpret_cast<uint8_t*>(fpr);
2014             reclaimed_bytes += ReleasePageRange(start, start + fpr_size);
2015             size_t pages = fpr_size / kPageSize;
2016             CHECK_GT(pages, 0U) << "Infinite loop probable";
2017             i += pages;
2018             DCHECK_LE(i, page_map_size_);
2019             break;
2020           }
2021         }
2022         FALLTHROUGH_INTENDED;
2023       }
2024       case kPageMapLargeObject:      // Fall through.
2025       case kPageMapLargeObjectPart:  // Fall through.
2026       case kPageMapRun:              // Fall through.
2027       case kPageMapRunPart:          // Fall through.
2028         ++i;
2029         break;  // Skip.
2030       default:
2031         LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm);
2032         UNREACHABLE();
2033     }
2034   }
2035   return reclaimed_bytes;
2036 }
2037 
ReleasePageRange(uint8_t * start,uint8_t * end)2038 size_t RosAlloc::ReleasePageRange(uint8_t* start, uint8_t* end) {
2039   DCHECK_ALIGNED(start, kPageSize);
2040   DCHECK_ALIGNED(end, kPageSize);
2041   DCHECK_LT(start, end);
2042   if (kIsDebugBuild) {
2043     // In the debug build, the first page of a free page run
2044     // contains a magic number for debugging. Exclude it.
2045     start += kPageSize;
2046 
2047     // Single pages won't be released.
2048     if (start == end) {
2049       return 0;
2050     }
2051   }
2052   if (!kMadviseZeroes) {
2053     // TODO: Do this when we resurrect the page instead.
2054     memset(start, 0, end - start);
2055   }
2056   CHECK_EQ(madvise(start, end - start, MADV_DONTNEED), 0);
2057   size_t pm_idx = ToPageMapIndex(start);
2058   size_t reclaimed_bytes = 0;
2059   // Calculate reclaimed bytes and upate page map.
2060   const size_t max_idx = pm_idx + (end - start) / kPageSize;
2061   for (; pm_idx < max_idx; ++pm_idx) {
2062     DCHECK(IsFreePage(pm_idx));
2063     if (page_map_[pm_idx] == kPageMapEmpty) {
2064       // Mark the page as released and update how many bytes we released.
2065       reclaimed_bytes += kPageSize;
2066       page_map_[pm_idx] = kPageMapReleased;
2067     }
2068   }
2069   return reclaimed_bytes;
2070 }
2071 
LogFragmentationAllocFailure(std::ostream & os,size_t failed_alloc_bytes)2072 bool RosAlloc::LogFragmentationAllocFailure(std::ostream& os, size_t failed_alloc_bytes) {
2073   Thread* self = Thread::Current();
2074   size_t largest_continuous_free_pages = 0;
2075   WriterMutexLock wmu(self, bulk_free_lock_);
2076   MutexLock mu(self, lock_);
2077   uint64_t total_free = 0;
2078   for (FreePageRun* fpr : free_page_runs_) {
2079     largest_continuous_free_pages = std::max(largest_continuous_free_pages,
2080                                              fpr->ByteSize(this));
2081     total_free += fpr->ByteSize(this);
2082   }
2083   size_t required_bytes = 0;
2084   const char* new_buffer_msg = "";
2085   if (failed_alloc_bytes > kLargeSizeThreshold) {
2086     // Large allocation.
2087     required_bytes = RoundUp(failed_alloc_bytes, kPageSize);
2088   } else {
2089     // Non-large allocation.
2090     required_bytes = numOfPages[SizeToIndex(failed_alloc_bytes)] * kPageSize;
2091     new_buffer_msg = " for a new buffer";
2092   }
2093   if (required_bytes > largest_continuous_free_pages) {
2094     os << "; failed due to fragmentation ("
2095        << "required contiguous free " << required_bytes << " bytes" << new_buffer_msg
2096        << ", largest contiguous free " << largest_continuous_free_pages << " bytes"
2097        << ", total free pages " << total_free << " bytes"
2098        << ", space footprint " << footprint_ << " bytes"
2099        << ", space max capacity " << max_capacity_ << " bytes"
2100        << ")" << std::endl;
2101     return true;
2102   }
2103   return false;
2104 }
2105 
DumpStats(std::ostream & os)2106 void RosAlloc::DumpStats(std::ostream& os) {
2107   Thread* self = Thread::Current();
2108   CHECK(Locks::mutator_lock_->IsExclusiveHeld(self))
2109       << "The mutator locks isn't exclusively locked at " << __PRETTY_FUNCTION__;
2110   size_t num_large_objects = 0;
2111   size_t num_pages_large_objects = 0;
2112   // These arrays are zero initialized.
2113   std::unique_ptr<size_t[]> num_runs(new size_t[kNumOfSizeBrackets]());
2114   std::unique_ptr<size_t[]> num_pages_runs(new size_t[kNumOfSizeBrackets]());
2115   std::unique_ptr<size_t[]> num_slots(new size_t[kNumOfSizeBrackets]());
2116   std::unique_ptr<size_t[]> num_used_slots(new size_t[kNumOfSizeBrackets]());
2117   std::unique_ptr<size_t[]> num_metadata_bytes(new size_t[kNumOfSizeBrackets]());
2118   ReaderMutexLock rmu(self, bulk_free_lock_);
2119   MutexLock lock_mu(self, lock_);
2120   for (size_t i = 0; i < page_map_size_; ) {
2121     uint8_t pm = page_map_[i];
2122     switch (pm) {
2123       case kPageMapReleased:
2124       case kPageMapEmpty:
2125         ++i;
2126         break;
2127       case kPageMapLargeObject: {
2128         size_t num_pages = 1;
2129         size_t idx = i + 1;
2130         while (idx < page_map_size_ && page_map_[idx] == kPageMapLargeObjectPart) {
2131           num_pages++;
2132           idx++;
2133         }
2134         num_large_objects++;
2135         num_pages_large_objects += num_pages;
2136         i += num_pages;
2137         break;
2138       }
2139       case kPageMapLargeObjectPart:
2140         LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm) << std::endl
2141                    << DumpPageMap();
2142         UNREACHABLE();
2143       case kPageMapRun: {
2144         Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize);
2145         size_t idx = run->size_bracket_idx_;
2146         size_t num_pages = numOfPages[idx];
2147         num_runs[idx]++;
2148         num_pages_runs[idx] += num_pages;
2149         num_slots[idx] += numOfSlots[idx];
2150         size_t num_free_slots = run->NumberOfFreeSlots();
2151         num_used_slots[idx] += numOfSlots[idx] - num_free_slots;
2152         num_metadata_bytes[idx] += headerSizes[idx];
2153         i += num_pages;
2154         break;
2155       }
2156       case kPageMapRunPart:
2157         // Fall-through.
2158       default:
2159         LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm) << std::endl
2160                    << DumpPageMap();
2161         UNREACHABLE();
2162     }
2163   }
2164   os << "RosAlloc stats:\n";
2165   for (size_t i = 0; i < kNumOfSizeBrackets; ++i) {
2166     os << "Bracket " << i << " (" << bracketSizes[i] << "):"
2167        << " #runs=" << num_runs[i]
2168        << " #pages=" << num_pages_runs[i]
2169        << " (" << PrettySize(num_pages_runs[i] * kPageSize) << ")"
2170        << " #metadata_bytes=" << PrettySize(num_metadata_bytes[i])
2171        << " #slots=" << num_slots[i] << " (" << PrettySize(num_slots[i] * bracketSizes[i]) << ")"
2172        << " #used_slots=" << num_used_slots[i]
2173        << " (" << PrettySize(num_used_slots[i] * bracketSizes[i]) << ")\n";
2174   }
2175   os << "Large #allocations=" << num_large_objects
2176      << " #pages=" << num_pages_large_objects
2177      << " (" << PrettySize(num_pages_large_objects * kPageSize) << ")\n";
2178   size_t total_num_pages = 0;
2179   size_t total_metadata_bytes = 0;
2180   size_t total_allocated_bytes = 0;
2181   for (size_t i = 0; i < kNumOfSizeBrackets; ++i) {
2182     total_num_pages += num_pages_runs[i];
2183     total_metadata_bytes += num_metadata_bytes[i];
2184     total_allocated_bytes += num_used_slots[i] * bracketSizes[i];
2185   }
2186   total_num_pages += num_pages_large_objects;
2187   total_allocated_bytes += num_pages_large_objects * kPageSize;
2188   os << "Total #total_bytes=" << PrettySize(total_num_pages * kPageSize)
2189      << " #metadata_bytes=" << PrettySize(total_metadata_bytes)
2190      << " #used_bytes=" << PrettySize(total_allocated_bytes) << "\n";
2191   os << "\n";
2192 }
2193 
2194 }  // namespace allocator
2195 }  // namespace gc
2196 }  // namespace art
2197