Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 1 | // Copyright 2011 Google Inc. All Rights Reserved. |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 2 | |
Brian Carlstrom | 578bbdc | 2011-07-21 14:07:47 -0700 | [diff] [blame] | 3 | #include "heap.h" |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 4 | |
| 5 | #include <vector> |
| 6 | |
Elliott Hughes | 90a3369 | 2011-08-30 13:27:07 -0700 | [diff] [blame] | 7 | #include "UniquePtr.h" |
Brian Carlstrom | 9cff8e1 | 2011-08-18 16:47:29 -0700 | [diff] [blame] | 8 | #include "image.h" |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 9 | #include "mark_sweep.h" |
Brian Carlstrom | 578bbdc | 2011-07-21 14:07:47 -0700 | [diff] [blame] | 10 | #include "object.h" |
| 11 | #include "space.h" |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 12 | #include "stl_util.h" |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 13 | |
| 14 | namespace art { |
| 15 | |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 16 | std::vector<Space*> Heap::spaces_; |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 17 | |
Brian Carlstrom | a663ea5 | 2011-08-19 23:33:41 -0700 | [diff] [blame] | 18 | Space* Heap::boot_space_ = NULL; |
| 19 | |
Brian Carlstrom | 4a289ed | 2011-08-16 17:17:49 -0700 | [diff] [blame] | 20 | Space* Heap::alloc_space_ = NULL; |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 21 | |
| 22 | size_t Heap::maximum_size_ = 0; |
| 23 | |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 24 | size_t Heap::num_bytes_allocated_ = 0; |
| 25 | |
| 26 | size_t Heap::num_objects_allocated_ = 0; |
| 27 | |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 28 | bool Heap::is_gc_running_ = false; |
| 29 | |
| 30 | HeapBitmap* Heap::mark_bitmap_ = NULL; |
| 31 | |
| 32 | HeapBitmap* Heap::live_bitmap_ = NULL; |
| 33 | |
Brian Carlstrom | 1f87008 | 2011-08-23 16:02:11 -0700 | [diff] [blame] | 34 | size_t Heap::reference_referent_offset_ = 0; // TODO |
| 35 | size_t Heap::reference_queue_offset_ = 0; // TODO |
| 36 | size_t Heap::reference_queueNext_offset_ = 0; // TODO |
| 37 | size_t Heap::reference_pendingNext_offset_ = 0; // TODO |
| 38 | size_t Heap::finalizer_reference_zombie_offset_ = 0; // TODO |
| 39 | |
Brian Carlstrom | 4a289ed | 2011-08-16 17:17:49 -0700 | [diff] [blame] | 40 | bool Heap::Init(size_t initial_size, size_t maximum_size, const char* boot_image_file_name) { |
| 41 | Space* boot_space; |
| 42 | byte* requested_base; |
| 43 | if (boot_image_file_name == NULL) { |
| 44 | boot_space = NULL; |
| 45 | requested_base = NULL; |
| 46 | } else { |
| 47 | boot_space = Space::Create(boot_image_file_name); |
| 48 | if (boot_space == NULL) { |
| 49 | return false; |
| 50 | } |
| 51 | spaces_.push_back(boot_space); |
| 52 | requested_base = boot_space->GetBase() + RoundUp(boot_space->Size(), kPageSize); |
| 53 | } |
| 54 | |
| 55 | Space* space = Space::Create(initial_size, maximum_size, requested_base); |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 56 | if (space == NULL) { |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 57 | return false; |
| 58 | } |
| 59 | |
Brian Carlstrom | 4a289ed | 2011-08-16 17:17:49 -0700 | [diff] [blame] | 60 | if (boot_space == NULL) { |
| 61 | boot_space = space; |
| 62 | } |
| 63 | byte* base = std::min(boot_space->GetBase(), space->GetBase()); |
| 64 | byte* limit = std::max(boot_space->GetLimit(), space->GetLimit()); |
| 65 | DCHECK_LT(base, limit); |
| 66 | size_t num_bytes = limit - base; |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 67 | |
| 68 | // Allocate the initial live bitmap. |
Elliott Hughes | 90a3369 | 2011-08-30 13:27:07 -0700 | [diff] [blame] | 69 | UniquePtr<HeapBitmap> live_bitmap(HeapBitmap::Create(base, num_bytes)); |
| 70 | if (live_bitmap.get() == NULL) { |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 71 | return false; |
| 72 | } |
| 73 | |
| 74 | // Allocate the initial mark bitmap. |
Elliott Hughes | 90a3369 | 2011-08-30 13:27:07 -0700 | [diff] [blame] | 75 | UniquePtr<HeapBitmap> mark_bitmap(HeapBitmap::Create(base, num_bytes)); |
| 76 | if (mark_bitmap.get() == NULL) { |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 77 | return false; |
| 78 | } |
| 79 | |
Brian Carlstrom | 4a289ed | 2011-08-16 17:17:49 -0700 | [diff] [blame] | 80 | alloc_space_ = space; |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 81 | spaces_.push_back(space); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 82 | maximum_size_ = maximum_size; |
| 83 | live_bitmap_ = live_bitmap.release(); |
| 84 | mark_bitmap_ = mark_bitmap.release(); |
| 85 | |
| 86 | // TODO: allocate the card table |
| 87 | |
Brian Carlstrom | 9cff8e1 | 2011-08-18 16:47:29 -0700 | [diff] [blame] | 88 | // Make objects in boot_space live (after live_bitmap_ is set) |
| 89 | if (boot_image_file_name != NULL) { |
Brian Carlstrom | a663ea5 | 2011-08-19 23:33:41 -0700 | [diff] [blame] | 90 | boot_space_ = boot_space; |
Brian Carlstrom | 9cff8e1 | 2011-08-18 16:47:29 -0700 | [diff] [blame] | 91 | RecordImageAllocations(boot_space); |
| 92 | } |
| 93 | |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 94 | return true; |
| 95 | } |
| 96 | |
| 97 | void Heap::Destroy() { |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 98 | STLDeleteElements(&spaces_); |
Brian Carlstrom | 4a289ed | 2011-08-16 17:17:49 -0700 | [diff] [blame] | 99 | if (mark_bitmap_ != NULL) { |
| 100 | delete mark_bitmap_; |
| 101 | mark_bitmap_ = NULL; |
| 102 | } |
| 103 | if (live_bitmap_ != NULL) { |
| 104 | delete live_bitmap_; |
| 105 | } |
| 106 | live_bitmap_ = NULL; |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 107 | } |
| 108 | |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 109 | Object* Heap::AllocObject(Class* klass, size_t num_bytes) { |
Brian Carlstrom | 9cff8e1 | 2011-08-18 16:47:29 -0700 | [diff] [blame] | 110 | DCHECK(klass == NULL |
Brian Carlstrom | 74eb46a | 2011-08-02 20:10:14 -0700 | [diff] [blame] | 111 | || klass->descriptor_ == NULL |
Brian Carlstrom | 4873d46 | 2011-08-21 15:23:39 -0700 | [diff] [blame] | 112 | || (klass->IsClassClass() && num_bytes >= sizeof(Class)) |
Brian Carlstrom | b63ec39 | 2011-08-27 17:38:27 -0700 | [diff] [blame] | 113 | || (klass->object_size_ == (klass->IsArrayClass() ? 0 : num_bytes))); |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 114 | Object* obj = Allocate(num_bytes); |
| 115 | if (obj != NULL) { |
| 116 | obj->klass_ = klass; |
| 117 | } |
| 118 | return obj; |
| 119 | } |
| 120 | |
Elliott Hughes | a250199 | 2011-08-26 19:39:54 -0700 | [diff] [blame] | 121 | void Heap::VerifyObject(Object* obj) { |
Ian Rogers | 408f79a | 2011-08-23 18:22:33 -0700 | [diff] [blame] | 122 | if (!IsAligned(obj, kObjectAlignment)) { |
| 123 | LOG(FATAL) << "Object isn't aligned: " << obj; |
| 124 | } else if (!live_bitmap_->Test(obj)) { |
| 125 | // TODO: we don't hold a lock here as it is assumed the live bit map |
| 126 | // isn't changing if the mutator is running. |
| 127 | LOG(FATAL) << "Object is dead: " << obj; |
| 128 | } else if(obj->GetClass() == NULL) { |
| 129 | LOG(FATAL) << "Object has no class: " << obj; |
| 130 | } |
| 131 | } |
| 132 | |
Elliott Hughes | a250199 | 2011-08-26 19:39:54 -0700 | [diff] [blame] | 133 | bool Heap::IsHeapAddress(Object* obj) { |
| 134 | if (!IsAligned(obj, kObjectAlignment)) { |
| 135 | return false; |
| 136 | } |
| 137 | // TODO |
| 138 | return true; |
| 139 | } |
| 140 | |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 141 | void Heap::RecordAllocation(Space* space, const Object* obj) { |
| 142 | size_t size = space->AllocationSize(obj); |
| 143 | DCHECK_NE(size, 0u); |
| 144 | num_bytes_allocated_ += size; |
| 145 | num_objects_allocated_ += 1; |
| 146 | live_bitmap_->Set(obj); |
| 147 | } |
| 148 | |
| 149 | void Heap::RecordFree(Space* space, const Object* obj) { |
| 150 | size_t size = space->AllocationSize(obj); |
| 151 | DCHECK_NE(size, 0u); |
| 152 | if (size < num_bytes_allocated_) { |
| 153 | num_bytes_allocated_ -= size; |
| 154 | } else { |
| 155 | num_bytes_allocated_ = 0; |
| 156 | } |
| 157 | live_bitmap_->Clear(obj); |
| 158 | if (num_objects_allocated_ > 0) { |
| 159 | num_objects_allocated_ -= 1; |
| 160 | } |
| 161 | } |
| 162 | |
Brian Carlstrom | 9cff8e1 | 2011-08-18 16:47:29 -0700 | [diff] [blame] | 163 | void Heap::RecordImageAllocations(Space* space) { |
| 164 | CHECK(space != NULL); |
| 165 | CHECK(live_bitmap_ != NULL); |
| 166 | byte* current = space->GetBase() + RoundUp(sizeof(ImageHeader), 8); |
| 167 | while (current < space->GetLimit()) { |
| 168 | DCHECK(IsAligned(current, 8)); |
| 169 | const Object* obj = reinterpret_cast<const Object*>(current); |
| 170 | live_bitmap_->Set(obj); |
| 171 | current += RoundUp(obj->SizeOf(), 8); |
| 172 | } |
| 173 | } |
| 174 | |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 175 | Object* Heap::Allocate(size_t size) { |
Brian Carlstrom | 4a289ed | 2011-08-16 17:17:49 -0700 | [diff] [blame] | 176 | DCHECK(alloc_space_ != NULL); |
| 177 | Space* space = alloc_space_; |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 178 | Object* obj = Allocate(space, size); |
| 179 | if (obj != NULL) { |
| 180 | RecordAllocation(space, obj); |
| 181 | } |
| 182 | return obj; |
| 183 | } |
| 184 | |
| 185 | Object* Heap::Allocate(Space* space, size_t size) { |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 186 | // Fail impossible allocations. TODO: collect soft references. |
| 187 | if (size > maximum_size_) { |
| 188 | return NULL; |
| 189 | } |
| 190 | |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 191 | Object* ptr = space->AllocWithoutGrowth(size); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 192 | if (ptr != NULL) { |
| 193 | return ptr; |
| 194 | } |
| 195 | |
| 196 | // The allocation failed. If the GC is running, block until it |
| 197 | // completes and retry. |
| 198 | if (is_gc_running_) { |
| 199 | // The GC is concurrently tracing the heap. Release the heap |
| 200 | // lock, wait for the GC to complete, and retrying allocating. |
| 201 | WaitForConcurrentGcToComplete(); |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 202 | ptr = space->AllocWithoutGrowth(size); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 203 | if (ptr != NULL) { |
| 204 | return ptr; |
| 205 | } |
| 206 | } |
| 207 | |
| 208 | // Another failure. Our thread was starved or there may be too many |
| 209 | // live objects. Try a foreground GC. This will have no effect if |
| 210 | // the concurrent GC is already running. |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 211 | CollectGarbageInternal(); |
| 212 | ptr = space->AllocWithoutGrowth(size); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 213 | if (ptr != NULL) { |
| 214 | return ptr; |
| 215 | } |
| 216 | |
| 217 | // Even that didn't work; this is an exceptional state. |
| 218 | // Try harder, growing the heap if necessary. |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 219 | ptr = space->AllocWithGrowth(size); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 220 | if (ptr != NULL) { |
| 221 | //size_t new_footprint = dvmHeapSourceGetIdealFootprint(); |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 222 | size_t new_footprint = space->MaxAllowedFootprint(); |
| 223 | // TODO: may want to grow a little bit more so that the amount of |
| 224 | // free space is equal to the old free space + the |
| 225 | // utilization slop for the new allocation. |
| 226 | LOG(INFO) << "Grow heap (frag case) to " << new_footprint / MB |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 227 | << "for " << size << "-byte allocation"; |
| 228 | return ptr; |
| 229 | } |
| 230 | |
| 231 | // Most allocations should have succeeded by now, so the heap is |
| 232 | // really full, really fragmented, or the requested size is really |
| 233 | // big. Do another GC, collecting SoftReferences this time. The VM |
| 234 | // spec requires that all SoftReferences have been collected and |
| 235 | // cleared before throwing an OOME. |
| 236 | |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 237 | // TODO: wait for the finalizers from the previous GC to finish |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 238 | LOG(INFO) << "Forcing collection of SoftReferences for " |
| 239 | << size << "-byte allocation"; |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 240 | CollectGarbageInternal(); |
| 241 | ptr = space->AllocWithGrowth(size); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 242 | if (ptr != NULL) { |
| 243 | return ptr; |
| 244 | } |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 245 | |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 246 | LOG(ERROR) << "Out of memory on a " << size << " byte allocation"; |
| 247 | |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 248 | // TODO: tell the HeapSource to dump its state |
| 249 | // TODO: dump stack traces for all threads |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 250 | |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 251 | return NULL; |
| 252 | } |
| 253 | |
Elliott Hughes | bf86d04 | 2011-08-31 17:53:14 -0700 | [diff] [blame^] | 254 | int64_t Heap::GetMaxMemory() { |
| 255 | UNIMPLEMENTED(WARNING); |
| 256 | return 0; |
| 257 | } |
| 258 | |
| 259 | int64_t Heap::GetTotalMemory() { |
| 260 | UNIMPLEMENTED(WARNING); |
| 261 | return 0; |
| 262 | } |
| 263 | |
| 264 | int64_t Heap::GetFreeMemory() { |
| 265 | UNIMPLEMENTED(WARNING); |
| 266 | return 0; |
| 267 | } |
| 268 | |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 269 | void Heap::CollectGarbage() { |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 270 | CollectGarbageInternal(); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 271 | } |
| 272 | |
| 273 | void Heap::CollectGarbageInternal() { |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 274 | // TODO: check that heap lock is held |
| 275 | |
| 276 | // TODO: Suspend all threads |
| 277 | { |
| 278 | MarkSweep mark_sweep; |
| 279 | |
| 280 | mark_sweep.Init(); |
| 281 | |
| 282 | mark_sweep.MarkRoots(); |
| 283 | |
| 284 | // Push marked roots onto the mark stack |
| 285 | |
| 286 | // TODO: if concurrent |
| 287 | // unlock heap |
| 288 | // resume threads |
| 289 | |
| 290 | mark_sweep.RecursiveMark(); |
| 291 | |
| 292 | // TODO: if concurrent |
| 293 | // lock heap |
| 294 | // suspend threads |
| 295 | // re-mark root set |
| 296 | // scan dirty objects |
| 297 | |
| 298 | mark_sweep.ProcessReferences(false); |
| 299 | |
| 300 | // TODO: swap bitmaps |
| 301 | |
| 302 | mark_sweep.Sweep(); |
| 303 | } |
| 304 | |
| 305 | GrowForUtilization(); |
| 306 | |
| 307 | // TODO: Resume all threads |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 308 | } |
| 309 | |
| 310 | void Heap::WaitForConcurrentGcToComplete() { |
| 311 | } |
| 312 | |
| 313 | // Given the current contents of the active heap, increase the allowed |
| 314 | // heap footprint to match the target utilization ratio. This should |
| 315 | // only be called immediately after a full garbage collection. |
| 316 | void Heap::GrowForUtilization() { |
Elliott Hughes | 53b6131 | 2011-08-12 18:28:20 -0700 | [diff] [blame] | 317 | UNIMPLEMENTED(ERROR); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 318 | } |
| 319 | |
| 320 | } // namespace art |