Heap.cpp revision 955c3a08362d6e3d2e6e80c493f19c915bc7ece2
1ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* 2ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * Copyright (C) 2008 The Android Open Source Project 3ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * 4ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * Licensed under the Apache License, Version 2.0 (the "License"); 5ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * you may not use this file except in compliance with the License. 6ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * You may obtain a copy of the License at 7ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * 8ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * http://www.apache.org/licenses/LICENSE-2.0 9ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * 10ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * Unless required by applicable law or agreed to in writing, software 11ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * distributed under the License is distributed on an "AS IS" BASIS, 12ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * See the License for the specific language governing permissions and 14ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * limitations under the License. 15ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 16ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* 17ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * Garbage-collecting memory allocator. 18ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 19ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "Dalvik.h" 20ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "alloc/HeapBitmap.h" 21ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "alloc/Verify.h" 22ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "alloc/Heap.h" 23ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "alloc/HeapInternal.h" 24ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "alloc/DdmHeap.h" 25ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "alloc/HeapSource.h" 26ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "alloc/MarkSweep.h" 27ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "os/os.h" 28b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley 29ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include <sys/time.h> 304605b3fb8a00fa37f617a8d0fe3a095d0503a845Raphael Moll#include <sys/resource.h> 314605b3fb8a00fa37f617a8d0fe3a095d0503a845Raphael Moll#include <limits.h> 324605b3fb8a00fa37f617a8d0fe3a095d0503a845Raphael Moll#include <errno.h> 334605b3fb8a00fa37f617a8d0fe3a095d0503a845Raphael Moll 34ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic const GcSpec kGcForMallocSpec = { 35ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross true, /* isPartial */ 36ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross false, /* isConcurrent */ 37ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross true, /* doPreserve */ 386bd2b5d80db5630cb73e3e5a4be3b38afa241c5aColin Cross "GC_FOR_ALLOC" 39ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross}; 40ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 416bd2b5d80db5630cb73e3e5a4be3b38afa241c5aColin Crossconst GcSpec *GC_FOR_MALLOC = &kGcForMallocSpec; 42ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 43ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic const GcSpec kGcConcurrentSpec = { 44ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross true, /* isPartial */ 45ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross true, /* isConcurrent */ 46ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross true, /* doPreserve */ 47ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross "GC_CONCURRENT" 48ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross}; 49ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 50ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossconst GcSpec *GC_CONCURRENT = &kGcConcurrentSpec; 51ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 52ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic const GcSpec kGcExplicitSpec = { 53ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross false, /* isPartial */ 54ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross true, /* isConcurrent */ 556bd2b5d80db5630cb73e3e5a4be3b38afa241c5aColin Cross true, /* doPreserve */ 56ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross "GC_EXPLICIT" 57ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross}; 58ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 592ff1c5b6e8c1457dbb65fb8305db92c74e95dd42Colin Crossconst GcSpec *GC_EXPLICIT = &kGcExplicitSpec; 60ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 61ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic const GcSpec kGcBeforeOomSpec = { 62ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross false, /* isPartial */ 63ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross false, /* isConcurrent */ 64ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross false, /* doPreserve */ 65ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross "GC_BEFORE_OOM" 66ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross}; 67ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 68ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossconst GcSpec *GC_BEFORE_OOM = &kGcBeforeOomSpec; 69ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 70ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* 71ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * Initialize the GC heap. 72ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * 73ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * Returns true if successful, false otherwise. 74ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 75ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossbool dvmHeapStartup() 76ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 77ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross GcHeap *gcHeap; 78ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 79ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (gDvm.heapGrowthLimit == 0) { 80ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross gDvm.heapGrowthLimit = gDvm.heapMaximumSize; 81ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 82ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 83ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross gcHeap = dvmHeapSourceStartup(gDvm.heapStartingSize, 84ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross gDvm.heapMaximumSize, 85ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross gDvm.heapGrowthLimit); 86ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (gcHeap == NULL) { 878aef66d2125af8de7672a12895276802fcc1948fColin Cross return false; 88ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 89ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross gcHeap->ddmHpifWhen = 0; 906bd2b5d80db5630cb73e3e5a4be3b38afa241c5aColin Cross gcHeap->ddmHpsgWhen = 0; 916bd2b5d80db5630cb73e3e5a4be3b38afa241c5aColin Cross gcHeap->ddmHpsgWhat = 0; 92ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross gcHeap->ddmNhsgWhen = 0; 93ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross gcHeap->ddmNhsgWhat = 0; 94ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross gDvm.gcHeap = gcHeap; 95ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 96ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* Set up the lists we'll use for cleared reference objects. 97ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 986bd2b5d80db5630cb73e3e5a4be3b38afa241c5aColin Cross gcHeap->clearedReferences = NULL; 996bd2b5d80db5630cb73e3e5a4be3b38afa241c5aColin Cross 1006bd2b5d80db5630cb73e3e5a4be3b38afa241c5aColin Cross if (!dvmCardTableStartup(gDvm.heapMaximumSize, gDvm.heapGrowthLimit)) { 101ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross LOGE_HEAP("card table startup failed."); 102ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return false; 103ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 104ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 105ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return true; 106ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 107ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 108ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossbool dvmHeapStartupAfterZygote() 109ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 110ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return dvmHeapSourceStartupAfterZygote(); 111ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 112ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 113ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid dvmHeapShutdown() 114ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 115ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross//TODO: make sure we're locked 116ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (gDvm.gcHeap != NULL) { 117ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross dvmCardTableShutdown(); 118ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* Destroy the heap. Any outstanding pointers will point to 119ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * unmapped memory (unless/until someone else maps it). This 120ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * frees gDvm.gcHeap as a side-effect. 121ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 122ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross dvmHeapSourceShutdown(&gDvm.gcHeap); 1232e905e5f2a3df605c68cb8633580c918e9f4ba71Colin Cross } 124ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 125ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 126ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* 127ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * Shutdown any threads internal to the heap. 128ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 129ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid dvmHeapThreadShutdown() 130ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 131ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross dvmHeapSourceThreadShutdown(); 132ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 133ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 134ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* 135ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * Grab the lock, but put ourselves into THREAD_VMWAIT if it looks like 136ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * we're going to have to wait on the mutex. 137ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 138ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossbool dvmLockHeap() 139ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 140ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (dvmTryLockMutex(&gDvm.gcHeapLock) != 0) { 141ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross Thread *self; 142ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross ThreadStatus oldStatus; 143ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 144ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross self = dvmThreadSelf(); 145ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross oldStatus = dvmChangeStatus(self, THREAD_VMWAIT); 1466bd2b5d80db5630cb73e3e5a4be3b38afa241c5aColin Cross dvmLockMutex(&gDvm.gcHeapLock); 1476bd2b5d80db5630cb73e3e5a4be3b38afa241c5aColin Cross dvmChangeStatus(self, oldStatus); 1486bd2b5d80db5630cb73e3e5a4be3b38afa241c5aColin Cross } 1496bd2b5d80db5630cb73e3e5a4be3b38afa241c5aColin Cross 1506bd2b5d80db5630cb73e3e5a4be3b38afa241c5aColin Cross return true; 151ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 152ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 153ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid dvmUnlockHeap() 154ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 155ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross dvmUnlockMutex(&gDvm.gcHeapLock); 156ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 157ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 158cb95c864fe069eecb88807cbbb456baf9ee2c44dColin Cross/* Do a full garbage collection, which may grow the 159cb95c864fe069eecb88807cbbb456baf9ee2c44dColin Cross * heap as a side-effect if the live set is large. 160ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 161ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void gcForMalloc(bool clearSoftReferences) 162ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 163ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (gDvm.allocProf.enabled) { 164ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross Thread* self = dvmThreadSelf(); 165ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross gDvm.allocProf.gcCount++; 166ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (self != NULL) { 167ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross self->allocProf.gcCount++; 168ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 169ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 170ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* This may adjust the soft limit as a side-effect. 171ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 172ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross const GcSpec *spec = clearSoftReferences ? GC_BEFORE_OOM : GC_FOR_MALLOC; 173ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross dvmCollectGarbageInternal(spec); 174ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 175ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 176ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Try as hard as possible to allocate some memory. 177ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 178ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void *tryMalloc(size_t size) 179ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 180ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross void *ptr; 181ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 182cf5c39c1851f8826264822414dbab31c1aeaeec6Colin Cross /* Don't try too hard if there's no way the allocation is 183cf5c39c1851f8826264822414dbab31c1aeaeec6Colin Cross * going to succeed. We have to collect SoftReferences before 184ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * throwing an OOME, though. 185ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 186ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (size >= gDvm.heapGrowthLimit) { 187ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross LOGW("%zd byte allocation exceeds the %zd byte maximum heap size", 188ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross size, gDvm.heapGrowthLimit); 189ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross ptr = NULL; 190ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross goto collect_soft_refs; 191ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 192ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 193ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross//TODO: figure out better heuristics 194ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross// There will be a lot of churn if someone allocates a bunch of 195ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross// big objects in a row, and we hit the frag case each time. 196ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross// A full GC for each. 197ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross// Maybe we grow the heap in bigger leaps 198ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross// Maybe we skip the GC if the size is large and we did one recently 199ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross// (number of allocations ago) (watch for thread effects) 200ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross// DeflateTest allocs a bunch of ~128k buffers w/in 0-5 allocs of each other 201ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross// (or, at least, there are only 0-5 objects swept each time) 202ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 203ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross ptr = dvmHeapSourceAlloc(size); 204ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (ptr != NULL) { 205ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return ptr; 206ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 207ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 208ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* 209ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * The allocation failed. If the GC is running, block until it 210ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * completes and retry. 211ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 212ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (gDvm.gcHeap->gcRunning) { 213ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* 214ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * The GC is concurrently tracing the heap. Release the heap 215ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * lock, wait for the GC to complete, and retrying allocating. 216ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 217ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross dvmWaitForConcurrentGcToComplete(); 218ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross ptr = dvmHeapSourceAlloc(size); 219ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (ptr != NULL) { 220ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return ptr; 221ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 222ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 223ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* 224ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * Another failure. Our thread was starved or there may be too 225ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * many live objects. Try a foreground GC. This will have no 226ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * effect if the concurrent GC is already running. 227ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 228de61f980c7b034eefac6e0ace718b3c1eb3f6252Colin Cross gcForMalloc(false); 229ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross ptr = dvmHeapSourceAlloc(size); 230ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (ptr != NULL) { 231ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return ptr; 232ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 233ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 234ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* Even that didn't work; this is an exceptional state. 235ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * Try harder, growing the heap if necessary. 236ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 237ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross ptr = dvmHeapSourceAllocAndGrow(size); 238de61f980c7b034eefac6e0ace718b3c1eb3f6252Colin Cross if (ptr != NULL) { 239de61f980c7b034eefac6e0ace718b3c1eb3f6252Colin Cross size_t newHeapSize; 240de61f980c7b034eefac6e0ace718b3c1eb3f6252Colin Cross 241ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross newHeapSize = dvmHeapSourceGetIdealFootprint(); 242ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross//TODO: may want to grow a little bit more so that the amount of free 243ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross// space is equal to the old free space + the utilization slop for 244b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley// the new allocation. 245b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley LOGI_HEAP("Grow heap (frag case) to " 246b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley "%zu.%03zuMB for %zu-byte allocation", 247b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley FRACTIONAL_MB(newHeapSize), size); 248b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley return ptr; 249b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley } 250b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley 251b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley /* Most allocations should have succeeded by now, so the heap 252b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley * is really full, really fragmented, or the requested size is 253b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley * really big. Do another GC, collecting SoftReferences this 254b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley * time. The VM spec requires that all SoftReferences have 255b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley * been collected and cleared before throwing an OOME. 256b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley */ 257b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley//TODO: wait for the finalizers from the previous GC to finish 2583def37fa6f8e037d39c19be9e624f15745032d08Matt Finiftercollect_soft_refs: 259b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley LOGI_HEAP("Forcing collection of SoftReferences for %zu-byte allocation", 260b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley size); 261b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley gcForMalloc(true); 262b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley ptr = dvmHeapSourceAllocAndGrow(size); 263b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley if (ptr != NULL) { 264b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley return ptr; 265b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley } 266b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley//TODO: maybe wait for finalizers and try one last time 267b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley 268b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley LOGE_HEAP("Out of memory on a %zd-byte allocation.", size); 269b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley//TODO: tell the HeapSource to dump its state 270b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley dvmDumpThread(dvmThreadSelf(), false); 271b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley 272b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley return NULL; 273b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley} 274b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley 2753def37fa6f8e037d39c19be9e624f15745032d08Matt Finifter/* Throw an OutOfMemoryError if there's a thread to attach it to. 276b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley * Avoid recursing. 277b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley * 278b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley * The caller must not be holding the heap lock, or else the allocations 279b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley * in dvmThrowException() will deadlock. 280b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley */ 281b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalleystatic void throwOOME() 282b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley{ 283b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley Thread *self; 284b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley 285b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley if ((self = dvmThreadSelf()) != NULL) { 286b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley /* If the current (failing) dvmMalloc() happened as part of thread 287b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley * creation/attachment before the thread became part of the root set, 288b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley * we can't rely on the thread-local trackedAlloc table, so 289b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley * we can't keep track of a real allocated OOME object. But, since 290b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley * the thread is in the process of being created, it won't have 291b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley * a useful stack anyway, so we may as well make things easier 292b4eca4b24af9c80ebb2a7fa2ba539a48096b7576Stephen Smalley * by throwing the (stackless) pre-built OOME. 293 */ 294 if (dvmIsOnThreadList(self) && !self->throwingOOME) { 295 /* Let ourselves know that we tried to throw an OOM 296 * error in the normal way in case we run out of 297 * memory trying to allocate it inside dvmThrowException(). 298 */ 299 self->throwingOOME = true; 300 301 /* Don't include a description string; 302 * one fewer allocation. 303 */ 304 dvmThrowOutOfMemoryError(NULL); 305 } else { 306 /* 307 * This thread has already tried to throw an OutOfMemoryError, 308 * which probably means that we're running out of memory 309 * while recursively trying to throw. 310 * 311 * To avoid any more allocation attempts, "throw" a pre-built 312 * OutOfMemoryError object (which won't have a useful stack trace). 313 * 314 * Note that since this call can't possibly allocate anything, 315 * we don't care about the state of self->throwingOOME 316 * (which will usually already be set). 317 */ 318 dvmSetException(self, gDvm.outOfMemoryObj); 319 } 320 /* We're done with the possible recursion. 321 */ 322 self->throwingOOME = false; 323 } 324} 325 326/* 327 * Allocate storage on the GC heap. We guarantee 8-byte alignment. 328 * 329 * The new storage is zeroed out. 330 * 331 * Note that, in rare cases, this could get called while a GC is in 332 * progress. If a non-VM thread tries to attach itself through JNI, 333 * it will need to allocate some objects. If this becomes annoying to 334 * deal with, we can block it at the source, but holding the allocation 335 * mutex should be enough. 336 * 337 * In rare circumstances (JNI AttachCurrentThread) we can be called 338 * from a non-VM thread. 339 * 340 * Use ALLOC_DONT_TRACK when we either don't want to track an allocation 341 * (because it's being done for the interpreter "new" operation and will 342 * be part of the root set immediately) or we can't (because this allocation 343 * is for a brand new thread). 344 * 345 * Returns NULL and throws an exception on failure. 346 * 347 * TODO: don't do a GC if the debugger thinks all threads are suspended 348 */ 349void* dvmMalloc(size_t size, int flags) 350{ 351 void *ptr; 352 353 dvmLockHeap(); 354 355 /* Try as hard as possible to allocate some memory. 356 */ 357 ptr = tryMalloc(size); 358 if (ptr != NULL) { 359 /* We've got the memory. 360 */ 361 if (gDvm.allocProf.enabled) { 362 Thread* self = dvmThreadSelf(); 363 gDvm.allocProf.allocCount++; 364 gDvm.allocProf.allocSize += size; 365 if (self != NULL) { 366 self->allocProf.allocCount++; 367 self->allocProf.allocSize += size; 368 } 369 } 370 } else { 371 /* The allocation failed. 372 */ 373 374 if (gDvm.allocProf.enabled) { 375 Thread* self = dvmThreadSelf(); 376 gDvm.allocProf.failedAllocCount++; 377 gDvm.allocProf.failedAllocSize += size; 378 if (self != NULL) { 379 self->allocProf.failedAllocCount++; 380 self->allocProf.failedAllocSize += size; 381 } 382 } 383 } 384 385 dvmUnlockHeap(); 386 387 if (ptr != NULL) { 388 /* 389 * If caller hasn't asked us not to track it, add it to the 390 * internal tracking list. 391 */ 392 if ((flags & ALLOC_DONT_TRACK) == 0) { 393 dvmAddTrackedAlloc((Object*)ptr, NULL); 394 } 395 } else { 396 /* 397 * The allocation failed; throw an OutOfMemoryError. 398 */ 399 throwOOME(); 400 } 401 402 return ptr; 403} 404 405/* 406 * Returns true iff <obj> points to a valid allocated object. 407 */ 408bool dvmIsValidObject(const Object* obj) 409{ 410 /* Don't bother if it's NULL or not 8-byte aligned. 411 */ 412 if (obj != NULL && ((uintptr_t)obj & (8-1)) == 0) { 413 /* Even if the heap isn't locked, this shouldn't return 414 * any false negatives. The only mutation that could 415 * be happening is allocation, which means that another 416 * thread could be in the middle of a read-modify-write 417 * to add a new bit for a new object. However, that 418 * RMW will have completed by the time any other thread 419 * could possibly see the new pointer, so there is no 420 * danger of dvmIsValidObject() being called on a valid 421 * pointer whose bit isn't set. 422 * 423 * Freeing will only happen during the sweep phase, which 424 * only happens while the heap is locked. 425 */ 426 return dvmHeapSourceContains(obj); 427 } 428 return false; 429} 430 431size_t dvmObjectSizeInHeap(const Object *obj) 432{ 433 return dvmHeapSourceChunkSize(obj); 434} 435 436static void verifyRootsAndHeap() 437{ 438 dvmVerifyRoots(); 439 dvmVerifyBitmap(dvmHeapSourceGetLiveBits()); 440} 441 442/* 443 * Initiate garbage collection. 444 * 445 * NOTES: 446 * - If we don't hold gDvm.threadListLock, it's possible for a thread to 447 * be added to the thread list while we work. The thread should NOT 448 * start executing, so this is only interesting when we start chasing 449 * thread stacks. (Before we do so, grab the lock.) 450 * 451 * We are not allowed to GC when the debugger has suspended the VM, which 452 * is awkward because debugger requests can cause allocations. The easiest 453 * way to enforce this is to refuse to GC on an allocation made by the 454 * JDWP thread -- we have to expand the heap or fail. 455 */ 456void dvmCollectGarbageInternal(const GcSpec* spec) 457{ 458 GcHeap *gcHeap = gDvm.gcHeap; 459 u4 rootStart = 0 , rootEnd = 0; 460 u4 dirtyStart = 0, dirtyEnd = 0; 461 size_t numObjectsFreed, numBytesFreed; 462 size_t currAllocated, currFootprint; 463 size_t percentFree; 464 int oldThreadPriority = INT_MAX; 465 466 /* The heap lock must be held. 467 */ 468 469 if (gcHeap->gcRunning) { 470 LOGW_HEAP("Attempted recursive GC"); 471 return; 472 } 473 474 gcHeap->gcRunning = true; 475 476 dvmSuspendAllThreads(SUSPEND_FOR_GC); 477 rootStart = dvmGetRelativeTimeMsec(); 478 479 /* 480 * If we are not marking concurrently raise the priority of the 481 * thread performing the garbage collection. 482 */ 483 if (!spec->isConcurrent) { 484 oldThreadPriority = os_raiseThreadPriority(); 485 } 486 if (gDvm.preVerify) { 487 LOGV_HEAP("Verifying roots and heap before GC"); 488 verifyRootsAndHeap(); 489 } 490 491 dvmMethodTraceGCBegin(); 492 493 /* Set up the marking context. 494 */ 495 if (!dvmHeapBeginMarkStep(spec->isPartial)) { 496 LOGE_HEAP("dvmHeapBeginMarkStep failed; aborting"); 497 dvmAbort(); 498 } 499 500 /* Mark the set of objects that are strongly reachable from the roots. 501 */ 502 LOGD_HEAP("Marking..."); 503 dvmHeapMarkRootSet(); 504 505 /* dvmHeapScanMarkedObjects() will build the lists of known 506 * instances of the Reference classes. 507 */ 508 assert(gcHeap->softReferences == NULL); 509 assert(gcHeap->weakReferences == NULL); 510 assert(gcHeap->finalizerReferences == NULL); 511 assert(gcHeap->phantomReferences == NULL); 512 assert(gcHeap->clearedReferences == NULL); 513 514 if (spec->isConcurrent) { 515 /* 516 * Resume threads while tracing from the roots. We unlock the 517 * heap to allow mutator threads to allocate from free space. 518 */ 519 dvmClearCardTable(); 520 rootEnd = dvmGetRelativeTimeMsec(); 521 dvmUnlockHeap(); 522 dvmResumeAllThreads(SUSPEND_FOR_GC); 523 } 524 525 /* Recursively mark any objects that marked objects point to strongly. 526 * If we're not collecting soft references, soft-reachable 527 * objects will also be marked. 528 */ 529 LOGD_HEAP("Recursing..."); 530 dvmHeapScanMarkedObjects(); 531 532 if (spec->isConcurrent) { 533 /* 534 * Re-acquire the heap lock and perform the final thread 535 * suspension. 536 */ 537 dvmLockHeap(); 538 dvmSuspendAllThreads(SUSPEND_FOR_GC); 539 dirtyStart = dvmGetRelativeTimeMsec(); 540 /* 541 * As no barrier intercepts root updates, we conservatively 542 * assume all roots may be gray and re-mark them. 543 */ 544 dvmHeapReMarkRootSet(); 545 /* 546 * With the exception of reference objects and weak interned 547 * strings, all gray objects should now be on dirty cards. 548 */ 549 if (gDvm.verifyCardTable) { 550 dvmVerifyCardTable(); 551 } 552 /* 553 * Recursively mark gray objects pointed to by the roots or by 554 * heap objects dirtied during the concurrent mark. 555 */ 556 dvmHeapReScanMarkedObjects(); 557 } 558 559 /* 560 * All strongly-reachable objects have now been marked. Process 561 * weakly-reachable objects discovered while tracing. 562 */ 563 dvmHeapProcessReferences(&gcHeap->softReferences, 564 spec->doPreserve == false, 565 &gcHeap->weakReferences, 566 &gcHeap->finalizerReferences, 567 &gcHeap->phantomReferences); 568 569#if defined(WITH_JIT) 570 /* 571 * Patching a chaining cell is very cheap as it only updates 4 words. It's 572 * the overhead of stopping all threads and synchronizing the I/D cache 573 * that makes it expensive. 574 * 575 * Therefore we batch those work orders in a queue and go through them 576 * when threads are suspended for GC. 577 */ 578 dvmCompilerPerformSafePointChecks(); 579#endif 580 581 LOGD_HEAP("Sweeping..."); 582 583 dvmHeapSweepSystemWeaks(); 584 585 /* 586 * Live objects have a bit set in the mark bitmap, swap the mark 587 * and live bitmaps. The sweep can proceed concurrently viewing 588 * the new live bitmap as the old mark bitmap, and vice versa. 589 */ 590 dvmHeapSourceSwapBitmaps(); 591 592 if (gDvm.postVerify) { 593 LOGV_HEAP("Verifying roots and heap after GC"); 594 verifyRootsAndHeap(); 595 } 596 597 if (spec->isConcurrent) { 598 dirtyEnd = dvmGetRelativeTimeMsec(); 599 dvmUnlockHeap(); 600 dvmResumeAllThreads(SUSPEND_FOR_GC); 601 } 602 dvmHeapSweepUnmarkedObjects(spec->isPartial, spec->isConcurrent, 603 &numObjectsFreed, &numBytesFreed); 604 LOGD_HEAP("Cleaning up..."); 605 dvmHeapFinishMarkStep(); 606 if (spec->isConcurrent) { 607 dvmLockHeap(); 608 } 609 610 LOGD_HEAP("Done."); 611 612 /* Now's a good time to adjust the heap size, since 613 * we know what our utilization is. 614 * 615 * This doesn't actually resize any memory; 616 * it just lets the heap grow more when necessary. 617 */ 618 dvmHeapSourceGrowForUtilization(); 619 620 currAllocated = dvmHeapSourceGetValue(HS_BYTES_ALLOCATED, NULL, 0); 621 currFootprint = dvmHeapSourceGetValue(HS_FOOTPRINT, NULL, 0); 622 623 dvmMethodTraceGCEnd(); 624 LOGV_HEAP("GC finished"); 625 626 gcHeap->gcRunning = false; 627 628 LOGV_HEAP("Resuming threads"); 629 630 if (spec->isConcurrent) { 631 /* 632 * Wake-up any threads that blocked after a failed allocation 633 * request. 634 */ 635 dvmBroadcastCond(&gDvm.gcHeapCond); 636 } 637 638 if (!spec->isConcurrent) { 639 dirtyEnd = dvmGetRelativeTimeMsec(); 640 dvmResumeAllThreads(SUSPEND_FOR_GC); 641 /* 642 * Restore the original thread scheduling priority if it was 643 * changed at the start of the current garbage collection. 644 */ 645 if (oldThreadPriority != INT_MAX) { 646 os_lowerThreadPriority(oldThreadPriority); 647 } 648 } 649 650 /* 651 * Move queue of pending references back into Java. 652 */ 653 dvmEnqueueClearedReferences(&gDvm.gcHeap->clearedReferences); 654 655 percentFree = 100 - (size_t)(100.0f * (float)currAllocated / currFootprint); 656 if (!spec->isConcurrent) { 657 u4 markSweepTime = dirtyEnd - rootStart; 658 bool isSmall = numBytesFreed > 0 && numBytesFreed < 1024; 659 LOGD("%s freed %s%zdK, %d%% free %zdK/%zdK, paused %ums", 660 spec->reason, 661 isSmall ? "<" : "", 662 numBytesFreed ? MAX(numBytesFreed / 1024, 1) : 0, 663 percentFree, 664 currAllocated / 1024, currFootprint / 1024, 665 markSweepTime); 666 } else { 667 u4 rootTime = rootEnd - rootStart; 668 u4 dirtyTime = dirtyEnd - dirtyStart; 669 bool isSmall = numBytesFreed > 0 && numBytesFreed < 1024; 670 LOGD("%s freed %s%zdK, %d%% free %zdK/%zdK, paused %ums+%ums", 671 spec->reason, 672 isSmall ? "<" : "", 673 numBytesFreed ? MAX(numBytesFreed / 1024, 1) : 0, 674 percentFree, 675 currAllocated / 1024, currFootprint / 1024, 676 rootTime, dirtyTime); 677 } 678 if (gcHeap->ddmHpifWhen != 0) { 679 LOGD_HEAP("Sending VM heap info to DDM"); 680 dvmDdmSendHeapInfo(gcHeap->ddmHpifWhen, false); 681 } 682 if (gcHeap->ddmHpsgWhen != 0) { 683 LOGD_HEAP("Dumping VM heap to DDM"); 684 dvmDdmSendHeapSegments(false, false); 685 } 686 if (gcHeap->ddmNhsgWhen != 0) { 687 LOGD_HEAP("Dumping native heap to DDM"); 688 dvmDdmSendHeapSegments(false, true); 689 } 690} 691 692/* 693 * If the concurrent GC is running, wait for it to finish. The caller 694 * must hold the heap lock. 695 * 696 * Note: the second dvmChangeStatus() could stall if we were in RUNNING 697 * on entry, and some other thread has asked us to suspend. In that 698 * case we will be suspended with the heap lock held, which can lead to 699 * deadlock if the other thread tries to do something with the managed heap. 700 * For example, the debugger might suspend us and then execute a method that 701 * allocates memory. We can avoid this situation by releasing the lock 702 * before self-suspending. (The developer can work around this specific 703 * situation by single-stepping the VM. Alternatively, we could disable 704 * concurrent GC when the debugger is attached, but that might change 705 * behavior more than is desirable.) 706 * 707 * This should not be a problem in production, because any GC-related 708 * activity will grab the lock before issuing a suspend-all. (We may briefly 709 * suspend when the GC thread calls dvmUnlockHeap before dvmResumeAllThreads, 710 * but there's no risk of deadlock.) 711 */ 712void dvmWaitForConcurrentGcToComplete() 713{ 714 Thread *self = dvmThreadSelf(); 715 assert(self != NULL); 716 while (gDvm.gcHeap->gcRunning) { 717 ThreadStatus oldStatus = dvmChangeStatus(self, THREAD_VMWAIT); 718 dvmWaitCond(&gDvm.gcHeapCond, &gDvm.gcHeapLock); 719 dvmChangeStatus(self, oldStatus); 720 } 721} 722