Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 1 | // Copyright 2011 Google Inc. All Rights Reserved. |
| 2 | // Author: cshapiro@google.com (Carl Shapiro) |
| 3 | |
Brian Carlstrom | 578bbdc | 2011-07-21 14:07:47 -0700 | [diff] [blame] | 4 | #include "heap.h" |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 5 | |
| 6 | #include <vector> |
| 7 | |
| 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 | |
| 18 | size_t Heap::startup_size_ = 0; |
| 19 | |
| 20 | size_t Heap::maximum_size_ = 0; |
| 21 | |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 22 | size_t Heap::num_bytes_allocated_ = 0; |
| 23 | |
| 24 | size_t Heap::num_objects_allocated_ = 0; |
| 25 | |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 26 | bool Heap::is_gc_running_ = false; |
| 27 | |
| 28 | HeapBitmap* Heap::mark_bitmap_ = NULL; |
| 29 | |
| 30 | HeapBitmap* Heap::live_bitmap_ = NULL; |
| 31 | |
| 32 | bool Heap::Init(size_t startup_size, size_t maximum_size) { |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 33 | Space* space = Space::Create(startup_size, maximum_size); |
| 34 | if (space == NULL) { |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 35 | return false; |
| 36 | } |
| 37 | |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 38 | byte* base = space->GetBase(); |
| 39 | size_t num_bytes = space->Size(); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 40 | |
| 41 | // Allocate the initial live bitmap. |
| 42 | scoped_ptr<HeapBitmap> live_bitmap(HeapBitmap::Create(base, num_bytes)); |
| 43 | if (live_bitmap == NULL) { |
| 44 | return false; |
| 45 | } |
| 46 | |
| 47 | // Allocate the initial mark bitmap. |
| 48 | scoped_ptr<HeapBitmap> mark_bitmap(HeapBitmap::Create(base, num_bytes)); |
| 49 | if (mark_bitmap == NULL) { |
| 50 | return false; |
| 51 | } |
| 52 | |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 53 | spaces_.push_back(space); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 54 | startup_size_ = startup_size; |
| 55 | maximum_size_ = maximum_size; |
| 56 | live_bitmap_ = live_bitmap.release(); |
| 57 | mark_bitmap_ = mark_bitmap.release(); |
| 58 | |
| 59 | // TODO: allocate the card table |
| 60 | |
| 61 | return true; |
| 62 | } |
| 63 | |
| 64 | void Heap::Destroy() { |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 65 | STLDeleteElements(&spaces_); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 66 | delete mark_bitmap_; |
| 67 | delete live_bitmap_; |
| 68 | } |
| 69 | |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 70 | Object* Heap::AllocObject(Class* klass, size_t num_bytes) { |
| 71 | Object* obj = Allocate(num_bytes); |
| 72 | if (obj != NULL) { |
| 73 | obj->klass_ = klass; |
| 74 | } |
| 75 | return obj; |
| 76 | } |
| 77 | |
| 78 | void Heap::RecordAllocation(Space* space, const Object* obj) { |
| 79 | size_t size = space->AllocationSize(obj); |
| 80 | DCHECK_NE(size, 0u); |
| 81 | num_bytes_allocated_ += size; |
| 82 | num_objects_allocated_ += 1; |
| 83 | live_bitmap_->Set(obj); |
| 84 | } |
| 85 | |
| 86 | void Heap::RecordFree(Space* space, const Object* obj) { |
| 87 | size_t size = space->AllocationSize(obj); |
| 88 | DCHECK_NE(size, 0u); |
| 89 | if (size < num_bytes_allocated_) { |
| 90 | num_bytes_allocated_ -= size; |
| 91 | } else { |
| 92 | num_bytes_allocated_ = 0; |
| 93 | } |
| 94 | live_bitmap_->Clear(obj); |
| 95 | if (num_objects_allocated_ > 0) { |
| 96 | num_objects_allocated_ -= 1; |
| 97 | } |
| 98 | } |
| 99 | |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 100 | Object* Heap::Allocate(size_t size) { |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 101 | CHECK_EQ(spaces_.size(), 1u); |
| 102 | Space* space = spaces_[0]; |
| 103 | Object* obj = Allocate(space, size); |
| 104 | if (obj != NULL) { |
| 105 | RecordAllocation(space, obj); |
| 106 | } |
| 107 | return obj; |
| 108 | } |
| 109 | |
| 110 | Object* Heap::Allocate(Space* space, size_t size) { |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 111 | // Fail impossible allocations. TODO: collect soft references. |
| 112 | if (size > maximum_size_) { |
| 113 | return NULL; |
| 114 | } |
| 115 | |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 116 | Object* ptr = space->AllocWithoutGrowth(size); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 117 | if (ptr != NULL) { |
| 118 | return ptr; |
| 119 | } |
| 120 | |
| 121 | // The allocation failed. If the GC is running, block until it |
| 122 | // completes and retry. |
| 123 | if (is_gc_running_) { |
| 124 | // The GC is concurrently tracing the heap. Release the heap |
| 125 | // lock, wait for the GC to complete, and retrying allocating. |
| 126 | WaitForConcurrentGcToComplete(); |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 127 | ptr = space->AllocWithoutGrowth(size); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 128 | if (ptr != NULL) { |
| 129 | return ptr; |
| 130 | } |
| 131 | } |
| 132 | |
| 133 | // Another failure. Our thread was starved or there may be too many |
| 134 | // live objects. Try a foreground GC. This will have no effect if |
| 135 | // the concurrent GC is already running. |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 136 | CollectGarbageInternal(); |
| 137 | ptr = space->AllocWithoutGrowth(size); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 138 | if (ptr != NULL) { |
| 139 | return ptr; |
| 140 | } |
| 141 | |
| 142 | // Even that didn't work; this is an exceptional state. |
| 143 | // Try harder, growing the heap if necessary. |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 144 | ptr = space->AllocWithGrowth(size); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 145 | if (ptr != NULL) { |
| 146 | //size_t new_footprint = dvmHeapSourceGetIdealFootprint(); |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 147 | size_t new_footprint = space->MaxAllowedFootprint(); |
| 148 | // TODO: may want to grow a little bit more so that the amount of |
| 149 | // free space is equal to the old free space + the |
| 150 | // utilization slop for the new allocation. |
| 151 | LOG(INFO) << "Grow heap (frag case) to " << new_footprint / MB |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 152 | << "for " << size << "-byte allocation"; |
| 153 | return ptr; |
| 154 | } |
| 155 | |
| 156 | // Most allocations should have succeeded by now, so the heap is |
| 157 | // really full, really fragmented, or the requested size is really |
| 158 | // big. Do another GC, collecting SoftReferences this time. The VM |
| 159 | // spec requires that all SoftReferences have been collected and |
| 160 | // cleared before throwing an OOME. |
| 161 | |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 162 | // TODO: wait for the finalizers from the previous GC to finish |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 163 | LOG(INFO) << "Forcing collection of SoftReferences for " |
| 164 | << size << "-byte allocation"; |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 165 | CollectGarbageInternal(); |
| 166 | ptr = space->AllocWithGrowth(size); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 167 | if (ptr != NULL) { |
| 168 | return ptr; |
| 169 | } |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 170 | |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 171 | LOG(ERROR) << "Out of memory on a " << size << " byte allocation"; |
| 172 | |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 173 | // TODO: tell the HeapSource to dump its state |
| 174 | // TODO: dump stack traces for all threads |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 175 | |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 176 | return NULL; |
| 177 | } |
| 178 | |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 179 | void Heap::CollectGarbage() { |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 180 | CollectGarbageInternal(); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 181 | } |
| 182 | |
| 183 | void Heap::CollectGarbageInternal() { |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 184 | // TODO: check that heap lock is held |
| 185 | |
| 186 | // TODO: Suspend all threads |
| 187 | { |
| 188 | MarkSweep mark_sweep; |
| 189 | |
| 190 | mark_sweep.Init(); |
| 191 | |
| 192 | mark_sweep.MarkRoots(); |
| 193 | |
| 194 | // Push marked roots onto the mark stack |
| 195 | |
| 196 | // TODO: if concurrent |
| 197 | // unlock heap |
| 198 | // resume threads |
| 199 | |
| 200 | mark_sweep.RecursiveMark(); |
| 201 | |
| 202 | // TODO: if concurrent |
| 203 | // lock heap |
| 204 | // suspend threads |
| 205 | // re-mark root set |
| 206 | // scan dirty objects |
| 207 | |
| 208 | mark_sweep.ProcessReferences(false); |
| 209 | |
| 210 | // TODO: swap bitmaps |
| 211 | |
| 212 | mark_sweep.Sweep(); |
| 213 | } |
| 214 | |
| 215 | GrowForUtilization(); |
| 216 | |
| 217 | // TODO: Resume all threads |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 218 | } |
| 219 | |
| 220 | void Heap::WaitForConcurrentGcToComplete() { |
| 221 | } |
| 222 | |
| 223 | // Given the current contents of the active heap, increase the allowed |
| 224 | // heap footprint to match the target utilization ratio. This should |
| 225 | // only be called immediately after a full garbage collection. |
| 226 | void Heap::GrowForUtilization() { |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 227 | LOG(ERROR) << "Unimplemented"; |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 228 | } |
| 229 | |
| 230 | } // namespace art |