CardTable.cpp revision 8f921a79b7e4f93905d8bb5c1b844d0acc5a8a2d
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 * 318f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes * The heap is divided into "cards" of GC_CARD_SIZE bytes, as 328f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes * determined by GC_CARD_SHIFT. The card table contains one byte of 338f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes * data per card, to be used by the GC. The value of the byte will be 348f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes * one of 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/* 1088f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry 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{ 1138f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes GcHeap *h = gDvm.gcHeap; 1148f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes u1 *cardAddr = h->biasedCardTableBase + ((uintptr_t)addr >> GC_CARD_SHIFT); 1158f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes assert(cardAddr >= h->cardTableBase); 1168f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes assert(cardAddr < &h->cardTableBase[h->cardTableLength]); 1176e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return cardAddr; 1186e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1196e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1208f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes/* 1218f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes * Returns the first address in the heap which maps to this card. 1228f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes */ 1238f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayesvoid *dvmAddrFromCard(const u1 *cardAddr) 1248f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes{ 1258f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes GcHeap *h = gDvm.gcHeap; 1268f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes assert(cardAddr >= h->cardTableBase); 1278f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes assert(cardAddr < &h->cardTableBase[h->cardTableLength]); 1288f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes uintptr_t offset = cardAddr - h->biasedCardTableBase; 1298f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes return (void *)(offset << GC_CARD_SHIFT); 1306e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1316e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1326e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 1336e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * Dirties the card for the given address. 1346e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 1356e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayesvoid dvmMarkCard(const void *addr) 1366e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 1376e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes u1 *cardAddr = dvmCardFromAddr(addr); 1386e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes *cardAddr = GC_CARD_DIRTY; 1396e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1406e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1416e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 1426e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * Returns true iff all address within the Object are on unmarked cards. 1436e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 1446e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayesstatic bool objectIsClean(const Object *obj) 1456e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 1466e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes assert(dvmIsValidObject(obj)); 1476e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes size_t size = dvmHeapSourceChunkSize(obj); 1486e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes u1 *start = dvmCardFromAddr(obj); 1496e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes u1 *end = dvmCardFromAddr((char *)obj + size-1); 1506e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes u1 *index; 1516e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1526e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes for (index = start; index <= end; index++) { 1536e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes if (*index != GC_CARD_CLEAN) { 1546e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return false; 1556e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes } 1566e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes } 1576e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return true; 1586e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1596e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1606e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 1616e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * A Visitor callback in support of checkCleanObjects. "arg" is 1626e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * expected to be the immuneLimit. 1636e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 1648f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayesstatic void crossGenCheckVisitor(void *ptr, void *arg) 1656e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 1666e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes Object *ref = *(Object **)ptr; 1676e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes Object *immuneLimit = (Object *)arg; 1686e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1696e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes if (ref >= immuneLimit) { 1706e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes LOGE("Clean obj contains threatened ref %p: %p", ptr, ref); 1716e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes dvmAbort(); 1726e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes } 1736e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1746e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1756e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 1766e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * A HeapBitmap callback in support of checkCleanObjects. 1776e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 1788f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayesstatic bool crossGenCheckCallback(size_t numPtrs, void **ptrs, 1796e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes const void *finger, void *arg) 1806e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 1816e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes size_t i; 1826e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes for (i = 0; i < numPtrs; i++) { 1836e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes Object *obj = ptrs[i]; 1846e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes if (objectIsClean(obj)) { 1856e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes dvmVisitObject(crossGenCheckVisitor, obj, arg); 1866e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes } 1876e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes } 1886e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1896e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return true; 1906e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1916e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1926e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 1936e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * dvmAbort if a clean, immune Object in the bitmap contains a pointer 1946e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * to a threatened Object. 1956e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 1966e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayesvoid dvmVerifyCardTable(HeapBitmap *bitmap, const char *immuneLimit) 1976e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 1986e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes dvmHeapBitmapWalk(bitmap, crossGenCheckCallback, (void *)immuneLimit); 1996e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 2006e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 201