CardTable.cpp revision 6e5cf6021b2f3e00e18ab402f23ab93b27c6061b
16e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 26e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * Copyright (C) 2010 The Android Open Source Project 36e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * 46e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * Licensed under the Apache License, Version 2.0 (the "License"); 56e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * you may not use this file except in compliance with the License. 66e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * You may obtain a copy of the License at 76e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * 86e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * http://www.apache.org/licenses/LICENSE-2.0 96e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * 106e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * Unless required by applicable law or agreed to in writing, software 116e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * distributed under the License is distributed on an "AS IS" BASIS, 126e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 136e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * See the License for the specific language governing permissions and 146e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * limitations under the License. 156e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 166e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 176e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 186e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * Needed for PROT_* definitions. 196e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 206e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes#include <sys/mman.h> 216e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 226e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes#include "Dalvik.h" 236e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes#include "alloc/HeapSource.h" 246e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes#include "alloc/Visit.h" 256e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 266e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 276e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * Maintain a card table from the the write barrier. All writes of 286e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * non-NULL values to heap addresses should go through an entry in 296e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * WriteBarrier, and from there to here. 306e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * 316e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * The heap is divided into "cards" of 512 bytes, as determined by 326e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * GC_CARD_SHIFT. The card table contains one byte of data per card, 336e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * to be used by the GC. The value of the byte will be one of 346e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * GC_CARD_CLEAN or GC_CARD_DIRTY. 356e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * 366e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * After any store of a non-NULL object pointer into a heap object, 376e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * code is obliged to mark the card dirty. The setters in 386e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * ObjectInlines.h [such as dvmSetFieldObject] do this for you. The 396e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * JIT and fast interpreters also contain code to mark cards as dirty. 406e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * 416e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * [TODO: Concurrent collection will have to expand on this, as it 426e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * uses the card table as well.] 436e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * 446e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * The card table is used to support partial collection, which at the 456e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * moment means "treat the zygote's heap as permanent, and only GC 466e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * objects in the application heap". In order to do this efficiently, 476e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * the GC need to find quickly references to objects in the 486e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * application heap from the zygote heap. When an application creates 496e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * an object and stores it into an object on the zygote heap, it will 506e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * mark the corresponding card in the zygote heap as "dirty". When the 516e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * GC does a partial collection, it can efficiently find all the 526e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * cross-heap objects, since they are all on dirty cards. The GC also 536e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * takes the opportunity to mark as "clean" any cards which are dirty, 546e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * but no longer contain cross-heap pointers. 556e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * 566e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * The card table's base [the "biased card table"] gets set to a 576e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * rather strange value. In order to keep the JIT from having to 586e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * fabricate or load GC_DIRTY_CARD to store into the card table, 596e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * biased base is within the mmap allocation at a point where it's low 606e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * byte is equal to GC_DIRTY_CARD. See dvmCardTableStartup for details. 616e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 626e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 636e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 646e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * Initializes the card table; must be called before any other 656e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * dvmCardTable*() functions. 666e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 676e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayesbool dvmCardTableStartup(GcHeap *gcHeap, void *heapBase) 686e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 696e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes size_t length; 706e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes void *allocBase; 716e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes u1 *biasedBase; 726e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 736e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes /* Set up the card table */ 746e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes length = gDvm.heapSizeMax / GC_CARD_SIZE; 756e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes /* Allocate an extra 256 bytes to allow fixed low-byte of base */ 766e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes allocBase = dvmAllocRegion(length + 0x100, PROT_READ | PROT_WRITE, 776e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes "dalvik-card-table"); 786e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes if (allocBase == NULL) { 796e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return false; 806e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes } 816e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes gcHeap->cardTableBase = allocBase; 826e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes gcHeap->cardTableLength = length; 836e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes /* All zeros is the correct initial value; all clean. */ 846e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes assert(GC_CARD_CLEAN == 0); 856e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 866e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes biasedBase = (u1 *)((uintptr_t)allocBase - 876e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes ((uintptr_t)heapBase >> GC_CARD_SHIFT)); 886e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes if (((uintptr_t)biasedBase & 0xff) != GC_CARD_DIRTY) { 896e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes int offset; 906e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes offset = GC_CARD_DIRTY - ((uintptr_t)biasedBase & 0xff); 916e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes biasedBase += offset + (offset < 0 ? 0x100 : 0); 926e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes } 936e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes assert(((uintptr_t)biasedBase & 0xff) == GC_CARD_DIRTY); 946e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes gcHeap->biasedCardTableBase = biasedBase; 956e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 966e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return true; 976e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 986e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 996e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 1006e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * Tears down the entire CardTable. 1016e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 1026e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayesvoid dvmCardTableShutdown() 1036e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 1046e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes munmap(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength); 1056e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1066e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1076e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 1086e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * Returns The address of the relevent byte in the card table, given 1096e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * an address on the heap. 1106e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 1116e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayesu1 *dvmCardFromAddr(const void *addr) 1126e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 1136e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes u1 *cardAddr = gDvm.gcHeap->biasedCardTableBase + 1146e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes ((uintptr_t)addr >> GC_CARD_SHIFT); 1156e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes assert(cardAddr >= gDvm.gcHeap->cardTableBase); 1166e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes assert(cardAddr < 1176e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes &gDvm.gcHeap->cardTableBase[gDvm.gcHeap->cardTableLength]); 1186e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return cardAddr; 1196e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1206e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1216e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayesvoid *dvmAddrFromCard(const u1 *cardAddr) { 1226e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes assert(cardAddr >= gDvm.gcHeap->cardTableBase); 1236e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes assert(cardAddr < 1246e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes &gDvm.gcHeap->cardTableBase[gDvm.gcHeap->cardTableLength]); 1256e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes void *addr = (void *)((cardAddr - gDvm.gcHeap->biasedCardTableBase) << GC_CARD_SHIFT); 1266e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return addr; 1276e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1286e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1296e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 1306e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * Dirties the card for the given address. 1316e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 1326e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayesvoid dvmMarkCard(const void *addr) 1336e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 1346e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes u1 *cardAddr = dvmCardFromAddr(addr); 1356e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes *cardAddr = GC_CARD_DIRTY; 1366e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1376e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1386e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 1396e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * Returns true iff all address within the Object are on unmarked cards. 1406e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 1416e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayesstatic bool objectIsClean(const Object *obj) 1426e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 1436e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes assert(dvmIsValidObject(obj)); 1446e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes size_t size = dvmHeapSourceChunkSize(obj); 1456e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes u1 *start = dvmCardFromAddr(obj); 1466e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes u1 *end = dvmCardFromAddr((char *)obj + size-1); 1476e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes u1 *index; 1486e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1496e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes for (index = start; index <= end; index++) { 1506e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes if (*index != GC_CARD_CLEAN) { 1516e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return false; 1526e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes } 1536e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes } 1546e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return true; 1556e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1566e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1576e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 1586e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * A Visitor callback in support of checkCleanObjects. "arg" is 1596e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * expected to be the immuneLimit. 1606e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 1616e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayesstatic void 1626e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry HayescrossGenCheckVisitor(void *ptr, void *arg) 1636e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 1646e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes Object *ref = *(Object **)ptr; 1656e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes Object *immuneLimit = (Object *)arg; 1666e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1676e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes if (ref >= immuneLimit) { 1686e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes LOGE("Clean obj contains threatened ref %p: %p", ptr, ref); 1696e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes dvmAbort(); 1706e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes } 1716e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1726e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1736e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 1746e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * A HeapBitmap callback in support of checkCleanObjects. 1756e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 1766e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayesstatic bool 1776e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry HayescrossGenCheckCallback(size_t numPtrs, void **ptrs, 1786e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes const void *finger, void *arg) 1796e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 1806e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes size_t i; 1816e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes for (i = 0; i < numPtrs; i++) { 1826e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes Object *obj = ptrs[i]; 1836e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes if (objectIsClean(obj)) { 1846e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes dvmVisitObject(crossGenCheckVisitor, obj, arg); 1856e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes } 1866e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes } 1876e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1886e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return true; 1896e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1906e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1916e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 1926e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * dvmAbort if a clean, immune Object in the bitmap contains a pointer 1936e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * to a threatened Object. 1946e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 1956e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayesvoid dvmVerifyCardTable(HeapBitmap *bitmap, const char *immuneLimit) 1966e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 1976e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes dvmHeapBitmapWalk(bitmap, crossGenCheckCallback, (void *)immuneLimit); 1986e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1996e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 200