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 175ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro#include <sys/mman.h> /* for PROT_* */ 186e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 196e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes#include "Dalvik.h" 20c38b7ed4392327cafa127086f4a5aef1bd0efdeeCarl Shapiro#include "alloc/HeapBitmap.h" 21c38b7ed4392327cafa127086f4a5aef1bd0efdeeCarl Shapiro#include "alloc/HeapBitmapInlines.h" 226e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes#include "alloc/HeapSource.h" 236e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes#include "alloc/Visit.h" 246e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 256e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 266e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * Maintain a card table from the the write barrier. All writes of 276e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * non-NULL values to heap addresses should go through an entry in 286e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * WriteBarrier, and from there to here. 296e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * 308f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes * The heap is divided into "cards" of GC_CARD_SIZE bytes, as 318f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes * determined by GC_CARD_SHIFT. The card table contains one byte of 328f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes * data per card, to be used by the GC. The value of the byte will be 338f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes * one of GC_CARD_CLEAN or GC_CARD_DIRTY. 346e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * 356e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * After any store of a non-NULL object pointer into a heap object, 366e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * code is obliged to mark the card dirty. The setters in 376e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * ObjectInlines.h [such as dvmSetFieldObject] do this for you. The 386e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * JIT and fast interpreters also contain code to mark cards as dirty. 396e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * 406e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * The card table's base [the "biased card table"] gets set to a 416e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * rather strange value. In order to keep the JIT from having to 426e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * fabricate or load GC_DIRTY_CARD to store into the card table, 436e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * biased base is within the mmap allocation at a point where it's low 446e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * byte is equal to GC_DIRTY_CARD. See dvmCardTableStartup for details. 456e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 466e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 47b2714082bad44fde247920b9280c1b40c4979c3aBen Cheng/* 48b2714082bad44fde247920b9280c1b40c4979c3aBen Cheng * Initializes the card table; must be called before any other 49b2714082bad44fde247920b9280c1b40c4979c3aBen Cheng * dvmCardTable*() functions. 50b2714082bad44fde247920b9280c1b40c4979c3aBen Cheng */ 51af6cf54652d1b27885b99e216bee29b955052630Andy McFaddenbool dvmCardTableStartup(size_t heapMaximumSize, size_t growthLimit) 526e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 536e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes size_t length; 546e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes void *allocBase; 556e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes u1 *biasedBase; 56b874ab98306a109c4988bb1cde687a24f4f8201fBarry Hayes GcHeap *gcHeap = gDvm.gcHeap; 57b874ab98306a109c4988bb1cde687a24f4f8201fBarry Hayes void *heapBase = dvmHeapSourceGetBase(); 58b874ab98306a109c4988bb1cde687a24f4f8201fBarry Hayes assert(gcHeap != NULL); 59b874ab98306a109c4988bb1cde687a24f4f8201fBarry Hayes assert(heapBase != NULL); 606e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 616e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes /* Set up the card table */ 62df9f08b877ecfd8ebadea822bb9e066ee7d30433Carl Shapiro length = heapMaximumSize / GC_CARD_SIZE; 636e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes /* Allocate an extra 256 bytes to allow fixed low-byte of base */ 646e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes allocBase = dvmAllocRegion(length + 0x100, PROT_READ | PROT_WRITE, 656e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes "dalvik-card-table"); 666e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes if (allocBase == NULL) { 676e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return false; 686e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes } 69fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro gcHeap->cardTableBase = (u1*)allocBase; 70af6cf54652d1b27885b99e216bee29b955052630Andy McFadden gcHeap->cardTableLength = growthLimit / GC_CARD_SIZE; 71af6cf54652d1b27885b99e216bee29b955052630Andy McFadden gcHeap->cardTableMaxLength = length; 72eebf7c690a6aabd50d70779d72685090a1eb84ffCarl Shapiro gcHeap->cardTableOffset = 0; 736e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes /* All zeros is the correct initial value; all clean. */ 746e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes assert(GC_CARD_CLEAN == 0); 756e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 766e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes biasedBase = (u1 *)((uintptr_t)allocBase - 776e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes ((uintptr_t)heapBase >> GC_CARD_SHIFT)); 786e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes if (((uintptr_t)biasedBase & 0xff) != GC_CARD_DIRTY) { 795d81aa327a11f6e929c2396d34c343923268bdc3Carl Shapiro int offset = GC_CARD_DIRTY - ((uintptr_t)biasedBase & 0xff); 80eebf7c690a6aabd50d70779d72685090a1eb84ffCarl Shapiro gcHeap->cardTableOffset = offset + (offset < 0 ? 0x100 : 0); 81eebf7c690a6aabd50d70779d72685090a1eb84ffCarl Shapiro biasedBase += gcHeap->cardTableOffset; 826e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes } 836e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes assert(((uintptr_t)biasedBase & 0xff) == GC_CARD_DIRTY); 844496ed9ef85e19447e697481d16842f47d265756Barry Hayes gDvm.biasedCardTableBase = biasedBase; 856e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 866e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return true; 876e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 886e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 896c355e53332502314c3d82a7afcf898d66118f27Carl Shapiro/* 906c355e53332502314c3d82a7afcf898d66118f27Carl Shapiro * Tears down the entire CardTable. 916c355e53332502314c3d82a7afcf898d66118f27Carl Shapiro */ 926c355e53332502314c3d82a7afcf898d66118f27Carl Shapirovoid dvmCardTableShutdown() 936c355e53332502314c3d82a7afcf898d66118f27Carl Shapiro{ 94b2714082bad44fde247920b9280c1b40c4979c3aBen Cheng gDvm.biasedCardTableBase = NULL; 95b2714082bad44fde247920b9280c1b40c4979c3aBen Cheng munmap(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength); 966e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 976e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 981e1433e78f560a01744e870c19c162ab88df9dc1Carl Shapirovoid dvmClearCardTable() 99106c5fd9745a47d663e28217f3dd5ac48f606f81Carl Shapiro{ 100af6cf54652d1b27885b99e216bee29b955052630Andy McFadden /* 101af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * The goal is to zero out some mmap-allocated pages. We can accomplish 102af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * this with memset() or madvise(MADV_DONTNEED). The latter has some 103af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * useful properties, notably that the pages are returned to the system, 104af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * so cards for parts of the heap we haven't expanded into won't be 105af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * allocated physical pages. On the other hand, if we un-map the card 106af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * area, we'll have to fault it back in as we resume dirtying objects, 107c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * which reduces performance. 108af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * 109c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * We don't cause any correctness issues by failing to clear cards; we 110c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * just take a performance hit during the second pause of the concurrent 111c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * collection. The "advisory" nature of madvise() isn't a big problem. 112c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * 113c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * What we really want to do is: 114c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * (1) zero out all cards that were touched 115c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * (2) use madvise() to release any pages that won't be used in the near 116c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * future 117c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * 118c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * For #1, we don't really know which cards were touched, but we can 119c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * approximate it with the "live bits max" value, which tells us the 120c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * highest start address at which an object was allocated. This may 121c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * leave vestigial nonzero entries at the end if temporary objects are 122c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * created during a concurrent GC, but that should be harmless. (We 123c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * can round up to the end of the card table page to reduce this.) 124c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * 125c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * For #2, we don't know which pages will be used in the future. Some 126c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * simple experiments suggested that a "typical" app will touch about 127c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * 60KB of pages while initializing, but drops down to 20-24KB while 128c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * idle. We can save a few hundred KB system-wide with aggressive 129c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * use of madvise(). The cost of mapping those pages back in is paid 130c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * outside of the GC pause, which reduces the impact. (We might be 131c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * able to get the benefits by only doing this occasionally, e.g. if 132c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * the heap shrinks a lot or we somehow notice that we've been idle.) 133af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * 134af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * Note that cardTableLength is initially set to the growth limit, and 135af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * on request will be expanded to the heap maximum. 136af6cf54652d1b27885b99e216bee29b955052630Andy McFadden */ 137b2714082bad44fde247920b9280c1b40c4979c3aBen Cheng assert(gDvm.gcHeap->cardTableBase != NULL); 138c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden 139c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden#if 1 140c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden // zero out cards with memset(), using liveBits as an estimate 141c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden const HeapBitmap* liveBits = dvmHeapSourceGetLiveBits(); 142c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden size_t maxLiveCard = (liveBits->max - liveBits->base) / GC_CARD_SIZE; 143c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden maxLiveCard = ALIGN_UP_TO_PAGE_SIZE(maxLiveCard); 144c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden if (maxLiveCard > gDvm.gcHeap->cardTableLength) { 145c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden maxLiveCard = gDvm.gcHeap->cardTableLength; 146c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden } 147c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden 148c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden memset(gDvm.gcHeap->cardTableBase, GC_CARD_CLEAN, maxLiveCard); 149c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden#else 150c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden // zero out cards with madvise(), discarding all pages in the card table 151c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden madvise(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength, 152c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden MADV_DONTNEED); 153c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden#endif 154106c5fd9745a47d663e28217f3dd5ac48f606f81Carl Shapiro} 155106c5fd9745a47d663e28217f3dd5ac48f606f81Carl Shapiro 1566e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 1574496ed9ef85e19447e697481d16842f47d265756Barry Hayes * Returns true iff the address is within the bounds of the card table. 1584496ed9ef85e19447e697481d16842f47d265756Barry Hayes */ 1594496ed9ef85e19447e697481d16842f47d265756Barry Hayesbool dvmIsValidCard(const u1 *cardAddr) 1604496ed9ef85e19447e697481d16842f47d265756Barry Hayes{ 1614496ed9ef85e19447e697481d16842f47d265756Barry Hayes GcHeap *h = gDvm.gcHeap; 162eebf7c690a6aabd50d70779d72685090a1eb84ffCarl Shapiro u1* begin = h->cardTableBase + h->cardTableOffset; 163eebf7c690a6aabd50d70779d72685090a1eb84ffCarl Shapiro u1* end = &begin[h->cardTableLength]; 164eebf7c690a6aabd50d70779d72685090a1eb84ffCarl Shapiro return cardAddr >= begin && cardAddr < end; 1654496ed9ef85e19447e697481d16842f47d265756Barry Hayes} 1664496ed9ef85e19447e697481d16842f47d265756Barry Hayes 1674496ed9ef85e19447e697481d16842f47d265756Barry Hayes/* 1688f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes * Returns the address of the relevent byte in the card table, given 1696e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * an address on the heap. 1706e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 1716e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayesu1 *dvmCardFromAddr(const void *addr) 1726e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 1734496ed9ef85e19447e697481d16842f47d265756Barry Hayes u1 *biasedBase = gDvm.biasedCardTableBase; 1744496ed9ef85e19447e697481d16842f47d265756Barry Hayes u1 *cardAddr = biasedBase + ((uintptr_t)addr >> GC_CARD_SHIFT); 1754496ed9ef85e19447e697481d16842f47d265756Barry Hayes assert(dvmIsValidCard(cardAddr)); 1766e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return cardAddr; 1776e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1786e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1798f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes/* 1808f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes * Returns the first address in the heap which maps to this card. 1818f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes */ 1828f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayesvoid *dvmAddrFromCard(const u1 *cardAddr) 1838f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes{ 1844496ed9ef85e19447e697481d16842f47d265756Barry Hayes assert(dvmIsValidCard(cardAddr)); 1854496ed9ef85e19447e697481d16842f47d265756Barry Hayes uintptr_t offset = cardAddr - gDvm.biasedCardTableBase; 1868f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes return (void *)(offset << GC_CARD_SHIFT); 1876e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1886e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1896e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 1906e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * Dirties the card for the given address. 1916e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 1926e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayesvoid dvmMarkCard(const void *addr) 1936e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 1946e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes u1 *cardAddr = dvmCardFromAddr(addr); 1956e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes *cardAddr = GC_CARD_DIRTY; 1966e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1975ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 1985ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro/* 1995ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro * Returns true if the object is on a dirty card. 2005ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro */ 2015ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapirostatic bool isObjectDirty(const Object *obj) 2025ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro{ 2035ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(obj != NULL); 2045ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(dvmIsValidObject(obj)); 20571ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro u1 *card = dvmCardFromAddr(obj); 20671ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro return *card == GC_CARD_DIRTY; 2075ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro} 2085ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 2095ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro/* 2105ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro * Context structure for verifying the card table. 2115ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro */ 21250e5fd5984c9b0a6f0927ed5ddf13bde40e338c7Carl Shapirostruct WhiteReferenceCounter { 2135ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro HeapBitmap *markBits; 2145ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro size_t whiteRefs; 21550e5fd5984c9b0a6f0927ed5ddf13bde40e338c7Carl Shapiro}; 2165ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 2175ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro/* 2185ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro * Visitor that counts white referents. 2195ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro */ 2205ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapirostatic void countWhiteReferenceVisitor(void *addr, void *arg) 2215ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro{ 2225ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro WhiteReferenceCounter *ctx; 2235ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro Object *obj; 2245ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 2255ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(addr != NULL); 2265ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(arg != NULL); 2275ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro obj = *(Object **)addr; 2288e14bc724301fcf07a88719dc121b91c6cc700e2Carl Shapiro if (obj == NULL) { 2298e14bc724301fcf07a88719dc121b91c6cc700e2Carl Shapiro return; 2308e14bc724301fcf07a88719dc121b91c6cc700e2Carl Shapiro } 2315ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(dvmIsValidObject(obj)); 232fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro ctx = (WhiteReferenceCounter *)arg; 2338e14bc724301fcf07a88719dc121b91c6cc700e2Carl Shapiro if (dvmHeapBitmapIsObjectBitSet(ctx->markBits, obj)) { 2345ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro return; 2355ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro } 2365ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro ctx->whiteRefs += 1; 2375ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro} 2385ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 2395ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro/* 2407f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro * Visitor that logs white references. 2417f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro */ 2427f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapirostatic void dumpWhiteReferenceVisitor(void *addr, void *arg) 2437f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro{ 2447f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro WhiteReferenceCounter *ctx; 2457f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro Object *obj; 2467f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro 2477f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro assert(addr != NULL); 2487f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro assert(arg != NULL); 2497f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro obj = *(Object **)addr; 2507f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro if (obj == NULL) { 2517f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro return; 2527f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro } 2537f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro assert(dvmIsValidObject(obj)); 254fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro ctx = (WhiteReferenceCounter*)arg; 2557f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro if (dvmHeapBitmapIsObjectBitSet(ctx->markBits, obj)) { 2567f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro return; 2577f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro } 258c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE("object %p is white", obj); 2597f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro} 2607f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro 2617f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro/* 2627f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro * Visitor that signals the caller when a matching reference is found. 2637f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro */ 2647f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapirostatic void dumpReferencesVisitor(void *pObj, void *arg) 2657f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro{ 2667f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro Object *obj = *(Object **)pObj; 2677f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro Object *lookingFor = *(Object **)arg; 2687f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro if (lookingFor != NULL && lookingFor == obj) { 2697f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro *(Object **)arg = NULL; 2707f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro } 2717f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro} 2727f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro 2730d92a4072c00434e95a03642a4944acf81a81cc3Carl Shapirostatic void dumpReferencesCallback(Object *obj, void *arg) 2747f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro{ 2750d92a4072c00434e95a03642a4944acf81a81cc3Carl Shapiro if (obj == (Object *)arg) { 2767f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro return; 2777f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro } 2780d92a4072c00434e95a03642a4944acf81a81cc3Carl Shapiro dvmVisitObject(dumpReferencesVisitor, obj, &arg); 2790d92a4072c00434e95a03642a4944acf81a81cc3Carl Shapiro if (arg == NULL) { 280062bf509a77fce9dfcb7e7b2e401cf2a124d83d5Steve Block ALOGD("Found %p in the heap @ %p", arg, obj); 2810d92a4072c00434e95a03642a4944acf81a81cc3Carl Shapiro dvmDumpObject(obj); 2827f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro } 2837f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro} 2847f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro 2857f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro/* 2867f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro * Root visitor that looks for matching references. 2877f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro */ 28807018e2d14b012ae433a0d82025a885ed8debc3bCarl Shapirostatic void dumpReferencesRootVisitor(void *ptr, u4 threadId, 28907018e2d14b012ae433a0d82025a885ed8debc3bCarl Shapiro RootType type, void *arg) 2907f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro{ 2917f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro Object *obj = *(Object **)ptr; 2927f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro Object *lookingFor = *(Object **)arg; 2937f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro if (obj == lookingFor) { 294062bf509a77fce9dfcb7e7b2e401cf2a124d83d5Steve Block ALOGD("Found %p in a root @ %p", arg, ptr); 2957f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro } 2967f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro} 2977f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro 2987f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro/* 2997f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro * Invokes visitors to search for references to an object. 3007f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro */ 3017f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapirostatic void dumpReferences(const Object *obj) 3027f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro{ 3037f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro HeapBitmap *bitmap = dvmHeapSourceGetLiveBits(); 3047f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro void *arg = (void *)obj; 3057f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro dvmVisitRoots(dumpReferencesRootVisitor, arg); 3067f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro dvmHeapBitmapWalk(bitmap, dumpReferencesCallback, arg); 3077f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro} 3087f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro 3097f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro/* 3105ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro * Returns true if the given object is a reference object and the 3115ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro * just the referent is unmarked. 3125ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro */ 3135ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapirostatic bool isReferentUnmarked(const Object *obj, 3145ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro const WhiteReferenceCounter* ctx) 3155ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro{ 3165ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(obj != NULL); 3175ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(obj->clazz != NULL); 3185ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(ctx != NULL); 3195ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro if (ctx->whiteRefs != 1) { 3205ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro return false; 3215ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro } else if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISREFERENCE)) { 3225ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro size_t offset = gDvm.offJavaLangRefReference_referent; 3235ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro const Object *referent = dvmGetFieldObject(obj, offset); 3245ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro return !dvmHeapBitmapIsObjectBitSet(ctx->markBits, referent); 3255ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro } else { 3265ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro return false; 3275ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro } 3285ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro} 3295ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 3305ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro/* 3315ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro * Returns true if the given object is a string and has been interned 3325ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro * by the user. 3335ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro */ 3345ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapirostatic bool isWeakInternedString(const Object *obj) 3355ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro{ 3365ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(obj != NULL); 3375ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro if (obj->clazz == gDvm.classJavaLangString) { 3385ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro return dvmIsWeakInternedString((StringObject *)obj); 3395ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro } else { 3405ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro return false; 3415ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro } 3425ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro} 3435ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 3445ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro/* 34571ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro * Returns true if the given object has been pushed on the mark stack 34671ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro * by root marking. 34771ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro */ 34871ce7a90945d1c26deea1eff84554b180a031afdCarl Shapirostatic bool isPushedOnMarkStack(const Object *obj) 34971ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro{ 350fdf805245e7276381173c5f03d7710f408b24270Carl Shapiro GcMarkStack *stack = &gDvm.gcHeap->markContext.stack; 351f9fa8c14c7ef87b4318d606bfc5132df7b77b17cCarl Shapiro for (const Object **ptr = stack->base; ptr < stack->top; ++ptr) { 35271ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro if (*ptr == obj) { 35371ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro return true; 35471ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro } 35571ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro } 35671ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro return false; 35771ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro} 35871ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro 35971ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro/* 36071ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro * Callback applied to marked objects. If the object is gray and on 36171ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro * an unmarked card an error is logged and the VM is aborted. Card 36271ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro * table verification occurs between root marking and weak reference 36371ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro * processing. We treat objects marked from the roots and weak 36471ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro * references specially as it is permissible for these objects to be 36571ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro * gray and on an unmarked card. 3665ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro */ 3670d92a4072c00434e95a03642a4944acf81a81cc3Carl Shapirostatic void verifyCardTableCallback(Object *obj, void *arg) 3685ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro{ 369fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro WhiteReferenceCounter ctx = { (HeapBitmap *)arg, 0 }; 3705ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 37157ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro dvmVisitObject(countWhiteReferenceVisitor, obj, &ctx); 37257ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro if (ctx.whiteRefs == 0) { 37357ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro return; 37457ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro } else if (isObjectDirty(obj)) { 37557ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro return; 37657ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro } else if (isReferentUnmarked(obj, &ctx)) { 37757ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro return; 37857ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro } else if (isWeakInternedString(obj)) { 37957ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro return; 38071ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro } else if (isPushedOnMarkStack(obj)) { 38171ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro return; 38257ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro } else { 383c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE("Verify failed, object %p is gray and on an unmarked card", obj); 3845ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro dvmDumpObject(obj); 3857f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro dvmVisitObject(dumpWhiteReferenceVisitor, obj, &ctx); 3867f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro dumpReferences(obj); 3875ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro dvmAbort(); 3885ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro } 3895ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro} 3905ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 3915ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro/* 3925ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro * Verifies that gray objects are on a dirty card. 3935ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro */ 3941e1433e78f560a01744e870c19c162ab88df9dc1Carl Shapirovoid dvmVerifyCardTable() 3955ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro{ 3965ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro HeapBitmap *markBits = gDvm.gcHeap->markContext.bitmap; 3975ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro dvmHeapBitmapWalk(markBits, verifyCardTableCallback, markBits); 3985ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro} 399