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