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; 57a86e99bacbe72f2a8914c4339646a6aba488afcdMathieu Chartier int offset; 58b874ab98306a109c4988bb1cde687a24f4f8201fBarry Hayes void *heapBase = dvmHeapSourceGetBase(); 59b874ab98306a109c4988bb1cde687a24f4f8201fBarry Hayes assert(gcHeap != NULL); 60b874ab98306a109c4988bb1cde687a24f4f8201fBarry Hayes assert(heapBase != NULL); 61a86e99bacbe72f2a8914c4339646a6aba488afcdMathieu Chartier /* All zeros is the correct initial value; all clean. */ 62a86e99bacbe72f2a8914c4339646a6aba488afcdMathieu Chartier assert(GC_CARD_CLEAN == 0); 636e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 646e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes /* Set up the card table */ 65df9f08b877ecfd8ebadea822bb9e066ee7d30433Carl Shapiro length = heapMaximumSize / GC_CARD_SIZE; 666e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes /* Allocate an extra 256 bytes to allow fixed low-byte of base */ 676e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes allocBase = dvmAllocRegion(length + 0x100, PROT_READ | PROT_WRITE, 686e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes "dalvik-card-table"); 696e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes if (allocBase == NULL) { 706e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return false; 716e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes } 72fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro gcHeap->cardTableBase = (u1*)allocBase; 73af6cf54652d1b27885b99e216bee29b955052630Andy McFadden gcHeap->cardTableLength = growthLimit / GC_CARD_SIZE; 74af6cf54652d1b27885b99e216bee29b955052630Andy McFadden gcHeap->cardTableMaxLength = length; 756e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes biasedBase = (u1 *)((uintptr_t)allocBase - 76a86e99bacbe72f2a8914c4339646a6aba488afcdMathieu Chartier ((uintptr_t)heapBase >> GC_CARD_SHIFT)); 77a86e99bacbe72f2a8914c4339646a6aba488afcdMathieu Chartier offset = GC_CARD_DIRTY - ((uintptr_t)biasedBase & 0xff); 78a86e99bacbe72f2a8914c4339646a6aba488afcdMathieu Chartier gcHeap->cardTableOffset = offset + (offset < 0 ? 0x100 : 0); 79a86e99bacbe72f2a8914c4339646a6aba488afcdMathieu Chartier biasedBase += gcHeap->cardTableOffset; 806e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes assert(((uintptr_t)biasedBase & 0xff) == GC_CARD_DIRTY); 814496ed9ef85e19447e697481d16842f47d265756Barry Hayes gDvm.biasedCardTableBase = biasedBase; 826e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 836e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return true; 846e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 856e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 866c355e53332502314c3d82a7afcf898d66118f27Carl Shapiro/* 876c355e53332502314c3d82a7afcf898d66118f27Carl Shapiro * Tears down the entire CardTable. 886c355e53332502314c3d82a7afcf898d66118f27Carl Shapiro */ 896c355e53332502314c3d82a7afcf898d66118f27Carl Shapirovoid dvmCardTableShutdown() 906c355e53332502314c3d82a7afcf898d66118f27Carl Shapiro{ 91b2714082bad44fde247920b9280c1b40c4979c3aBen Cheng gDvm.biasedCardTableBase = NULL; 92b2714082bad44fde247920b9280c1b40c4979c3aBen Cheng munmap(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength); 936e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 946e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 951e1433e78f560a01744e870c19c162ab88df9dc1Carl Shapirovoid dvmClearCardTable() 96106c5fd9745a47d663e28217f3dd5ac48f606f81Carl Shapiro{ 97af6cf54652d1b27885b99e216bee29b955052630Andy McFadden /* 98af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * The goal is to zero out some mmap-allocated pages. We can accomplish 99af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * this with memset() or madvise(MADV_DONTNEED). The latter has some 100af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * useful properties, notably that the pages are returned to the system, 101af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * so cards for parts of the heap we haven't expanded into won't be 102af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * allocated physical pages. On the other hand, if we un-map the card 103af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * area, we'll have to fault it back in as we resume dirtying objects, 104c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * which reduces performance. 105af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * 106c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * We don't cause any correctness issues by failing to clear cards; we 107c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * just take a performance hit during the second pause of the concurrent 108c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * collection. The "advisory" nature of madvise() isn't a big problem. 109c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * 110c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * What we really want to do is: 111c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * (1) zero out all cards that were touched 112c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * (2) use madvise() to release any pages that won't be used in the near 113c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * future 114c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * 115c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * For #1, we don't really know which cards were touched, but we can 116c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * approximate it with the "live bits max" value, which tells us the 117c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * highest start address at which an object was allocated. This may 118c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * leave vestigial nonzero entries at the end if temporary objects are 119c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * created during a concurrent GC, but that should be harmless. (We 120c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * can round up to the end of the card table page to reduce this.) 121c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * 122c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * For #2, we don't know which pages will be used in the future. Some 123c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * simple experiments suggested that a "typical" app will touch about 124c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * 60KB of pages while initializing, but drops down to 20-24KB while 125c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * idle. We can save a few hundred KB system-wide with aggressive 126c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * use of madvise(). The cost of mapping those pages back in is paid 127c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * outside of the GC pause, which reduces the impact. (We might be 128c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * able to get the benefits by only doing this occasionally, e.g. if 129c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden * the heap shrinks a lot or we somehow notice that we've been idle.) 130af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * 131af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * Note that cardTableLength is initially set to the growth limit, and 132af6cf54652d1b27885b99e216bee29b955052630Andy McFadden * on request will be expanded to the heap maximum. 133af6cf54652d1b27885b99e216bee29b955052630Andy McFadden */ 134b2714082bad44fde247920b9280c1b40c4979c3aBen Cheng assert(gDvm.gcHeap->cardTableBase != NULL); 135c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden 136ebaf918e1bacff53c3dc3f0861c5cee851db23e5Mathieu Chartier if (gDvm.lowMemoryMode) { 137ebaf918e1bacff53c3dc3f0861c5cee851db23e5Mathieu Chartier // zero out cards with madvise(), discarding all pages in the card table 138ebaf918e1bacff53c3dc3f0861c5cee851db23e5Mathieu Chartier madvise(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength, MADV_DONTNEED); 139ebaf918e1bacff53c3dc3f0861c5cee851db23e5Mathieu Chartier } else { 140ebaf918e1bacff53c3dc3f0861c5cee851db23e5Mathieu Chartier // zero out cards with memset(), using liveBits as an estimate 141ebaf918e1bacff53c3dc3f0861c5cee851db23e5Mathieu Chartier const HeapBitmap* liveBits = dvmHeapSourceGetLiveBits(); 142ebaf918e1bacff53c3dc3f0861c5cee851db23e5Mathieu Chartier size_t maxLiveCard = (liveBits->max - liveBits->base) / GC_CARD_SIZE; 143ebaf918e1bacff53c3dc3f0861c5cee851db23e5Mathieu Chartier maxLiveCard = ALIGN_UP_TO_PAGE_SIZE(maxLiveCard); 144ebaf918e1bacff53c3dc3f0861c5cee851db23e5Mathieu Chartier if (maxLiveCard > gDvm.gcHeap->cardTableLength) { 145ebaf918e1bacff53c3dc3f0861c5cee851db23e5Mathieu Chartier maxLiveCard = gDvm.gcHeap->cardTableLength; 146ebaf918e1bacff53c3dc3f0861c5cee851db23e5Mathieu Chartier } 147c0a18856ed67b0e77a8202028f27948e1387243dAndy McFadden 148ebaf918e1bacff53c3dc3f0861c5cee851db23e5Mathieu Chartier memset(gDvm.gcHeap->cardTableBase, GC_CARD_CLEAN, maxLiveCard); 149ebaf918e1bacff53c3dc3f0861c5cee851db23e5Mathieu Chartier } 150106c5fd9745a47d663e28217f3dd5ac48f606f81Carl Shapiro} 151106c5fd9745a47d663e28217f3dd5ac48f606f81Carl Shapiro 1526e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 1534496ed9ef85e19447e697481d16842f47d265756Barry Hayes * Returns true iff the address is within the bounds of the card table. 1544496ed9ef85e19447e697481d16842f47d265756Barry Hayes */ 1554496ed9ef85e19447e697481d16842f47d265756Barry Hayesbool dvmIsValidCard(const u1 *cardAddr) 1564496ed9ef85e19447e697481d16842f47d265756Barry Hayes{ 1574496ed9ef85e19447e697481d16842f47d265756Barry Hayes GcHeap *h = gDvm.gcHeap; 158eebf7c690a6aabd50d70779d72685090a1eb84ffCarl Shapiro u1* begin = h->cardTableBase + h->cardTableOffset; 159eebf7c690a6aabd50d70779d72685090a1eb84ffCarl Shapiro u1* end = &begin[h->cardTableLength]; 160eebf7c690a6aabd50d70779d72685090a1eb84ffCarl Shapiro return cardAddr >= begin && cardAddr < end; 1614496ed9ef85e19447e697481d16842f47d265756Barry Hayes} 1624496ed9ef85e19447e697481d16842f47d265756Barry Hayes 1634496ed9ef85e19447e697481d16842f47d265756Barry Hayes/* 164a86e99bacbe72f2a8914c4339646a6aba488afcdMathieu Chartier * Returns the address of the relevant byte in the card table, given 1656e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * an address on the heap. 1666e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 1676e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayesu1 *dvmCardFromAddr(const void *addr) 1686e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 1694496ed9ef85e19447e697481d16842f47d265756Barry Hayes u1 *biasedBase = gDvm.biasedCardTableBase; 1704496ed9ef85e19447e697481d16842f47d265756Barry Hayes u1 *cardAddr = biasedBase + ((uintptr_t)addr >> GC_CARD_SHIFT); 1714496ed9ef85e19447e697481d16842f47d265756Barry Hayes assert(dvmIsValidCard(cardAddr)); 1726e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes return cardAddr; 1736e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1746e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1758f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes/* 1768f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes * Returns the first address in the heap which maps to this card. 1778f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes */ 1788f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayesvoid *dvmAddrFromCard(const u1 *cardAddr) 1798f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes{ 1804496ed9ef85e19447e697481d16842f47d265756Barry Hayes assert(dvmIsValidCard(cardAddr)); 1814496ed9ef85e19447e697481d16842f47d265756Barry Hayes uintptr_t offset = cardAddr - gDvm.biasedCardTableBase; 1828f921a79b7e4f93905d8bb5c1b844d0acc5a8a2dBarry Hayes return (void *)(offset << GC_CARD_SHIFT); 1836e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1846e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes 1856e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes/* 1866e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes * Dirties the card for the given address. 1876e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes */ 1886e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayesvoid dvmMarkCard(const void *addr) 1896e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes{ 1906e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes u1 *cardAddr = dvmCardFromAddr(addr); 1916e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes *cardAddr = GC_CARD_DIRTY; 1926e5cf6021b2f3e00e18ab402f23ab93b27c6061bBarry Hayes} 1935ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 1945ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro/* 1955ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro * Returns true if the object is on a dirty card. 1965ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro */ 1975ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapirostatic bool isObjectDirty(const Object *obj) 1985ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro{ 1995ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(obj != NULL); 2005ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(dvmIsValidObject(obj)); 20171ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro u1 *card = dvmCardFromAddr(obj); 20271ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro return *card == GC_CARD_DIRTY; 2035ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro} 2045ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 2055ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro/* 2065ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro * Context structure for verifying the card table. 2075ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro */ 20850e5fd5984c9b0a6f0927ed5ddf13bde40e338c7Carl Shapirostruct WhiteReferenceCounter { 2095ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro HeapBitmap *markBits; 2105ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro size_t whiteRefs; 21150e5fd5984c9b0a6f0927ed5ddf13bde40e338c7Carl Shapiro}; 2125ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 2135ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro/* 2145ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro * Visitor that counts white referents. 2155ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro */ 2165ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapirostatic void countWhiteReferenceVisitor(void *addr, void *arg) 2175ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro{ 2185ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro WhiteReferenceCounter *ctx; 2195ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro Object *obj; 2205ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 2215ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(addr != NULL); 2225ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(arg != NULL); 2235ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro obj = *(Object **)addr; 2248e14bc724301fcf07a88719dc121b91c6cc700e2Carl Shapiro if (obj == NULL) { 2258e14bc724301fcf07a88719dc121b91c6cc700e2Carl Shapiro return; 2268e14bc724301fcf07a88719dc121b91c6cc700e2Carl Shapiro } 2275ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(dvmIsValidObject(obj)); 228fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro ctx = (WhiteReferenceCounter *)arg; 2298e14bc724301fcf07a88719dc121b91c6cc700e2Carl Shapiro if (dvmHeapBitmapIsObjectBitSet(ctx->markBits, obj)) { 2305ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro return; 2315ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro } 2325ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro ctx->whiteRefs += 1; 2335ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro} 2345ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 2355ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro/* 2367f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro * Visitor that logs white references. 2377f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro */ 2387f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapirostatic void dumpWhiteReferenceVisitor(void *addr, void *arg) 2397f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro{ 2407f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro WhiteReferenceCounter *ctx; 2417f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro Object *obj; 2427f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro 2437f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro assert(addr != NULL); 2447f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro assert(arg != NULL); 2457f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro obj = *(Object **)addr; 2467f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro if (obj == NULL) { 2477f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro return; 2487f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro } 2497f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro assert(dvmIsValidObject(obj)); 250fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro ctx = (WhiteReferenceCounter*)arg; 2517f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro if (dvmHeapBitmapIsObjectBitSet(ctx->markBits, obj)) { 2527f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro return; 2537f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro } 254c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE("object %p is white", obj); 2557f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro} 2567f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro 2577f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro/* 2587f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro * Visitor that signals the caller when a matching reference is found. 2597f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro */ 2607f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapirostatic void dumpReferencesVisitor(void *pObj, void *arg) 2617f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro{ 2627f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro Object *obj = *(Object **)pObj; 2637f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro Object *lookingFor = *(Object **)arg; 2647f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro if (lookingFor != NULL && lookingFor == obj) { 2657f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro *(Object **)arg = NULL; 2667f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro } 2677f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro} 2687f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro 2690d92a4072c00434e95a03642a4944acf81a81cc3Carl Shapirostatic void dumpReferencesCallback(Object *obj, void *arg) 2707f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro{ 2710d92a4072c00434e95a03642a4944acf81a81cc3Carl Shapiro if (obj == (Object *)arg) { 2727f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro return; 2737f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro } 2740d92a4072c00434e95a03642a4944acf81a81cc3Carl Shapiro dvmVisitObject(dumpReferencesVisitor, obj, &arg); 2750d92a4072c00434e95a03642a4944acf81a81cc3Carl Shapiro if (arg == NULL) { 276062bf509a77fce9dfcb7e7b2e401cf2a124d83d5Steve Block ALOGD("Found %p in the heap @ %p", arg, obj); 2770d92a4072c00434e95a03642a4944acf81a81cc3Carl Shapiro dvmDumpObject(obj); 2787f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro } 2797f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro} 2807f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro 2817f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro/* 2827f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro * Root visitor that looks for matching references. 2837f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro */ 28407018e2d14b012ae433a0d82025a885ed8debc3bCarl Shapirostatic void dumpReferencesRootVisitor(void *ptr, u4 threadId, 28507018e2d14b012ae433a0d82025a885ed8debc3bCarl Shapiro RootType type, void *arg) 2867f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro{ 2877f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro Object *obj = *(Object **)ptr; 2887f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro Object *lookingFor = *(Object **)arg; 2897f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro if (obj == lookingFor) { 290062bf509a77fce9dfcb7e7b2e401cf2a124d83d5Steve Block ALOGD("Found %p in a root @ %p", arg, ptr); 2917f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro } 2927f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro} 2937f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro 2947f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro/* 2957f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro * Invokes visitors to search for references to an object. 2967f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro */ 2977f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapirostatic void dumpReferences(const Object *obj) 2987f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro{ 2997f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro HeapBitmap *bitmap = dvmHeapSourceGetLiveBits(); 3007f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro void *arg = (void *)obj; 3017f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro dvmVisitRoots(dumpReferencesRootVisitor, arg); 3027f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro dvmHeapBitmapWalk(bitmap, dumpReferencesCallback, arg); 3037f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro} 3047f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro 3057f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro/* 3065ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro * Returns true if the given object is a reference object and the 3075ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro * just the referent is unmarked. 3085ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro */ 3095ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapirostatic bool isReferentUnmarked(const Object *obj, 3105ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro const WhiteReferenceCounter* ctx) 3115ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro{ 3125ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(obj != NULL); 3135ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(obj->clazz != NULL); 3145ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(ctx != NULL); 3155ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro if (ctx->whiteRefs != 1) { 3165ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro return false; 3175ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro } else if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISREFERENCE)) { 3185ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro size_t offset = gDvm.offJavaLangRefReference_referent; 3195ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro const Object *referent = dvmGetFieldObject(obj, offset); 3205ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro return !dvmHeapBitmapIsObjectBitSet(ctx->markBits, referent); 3215ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro } else { 3225ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro return false; 3235ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro } 3245ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro} 3255ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 3265ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro/* 3275ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro * Returns true if the given object is a string and has been interned 3285ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro * by the user. 3295ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro */ 3305ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapirostatic bool isWeakInternedString(const Object *obj) 3315ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro{ 3325ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro assert(obj != NULL); 3335ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro if (obj->clazz == gDvm.classJavaLangString) { 3345ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro return dvmIsWeakInternedString((StringObject *)obj); 3355ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro } else { 3365ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro return false; 3375ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro } 3385ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro} 3395ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 3405ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro/* 34171ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro * Returns true if the given object has been pushed on the mark stack 34271ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro * by root marking. 34371ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro */ 34471ce7a90945d1c26deea1eff84554b180a031afdCarl Shapirostatic bool isPushedOnMarkStack(const Object *obj) 34571ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro{ 346fdf805245e7276381173c5f03d7710f408b24270Carl Shapiro GcMarkStack *stack = &gDvm.gcHeap->markContext.stack; 347f9fa8c14c7ef87b4318d606bfc5132df7b77b17cCarl Shapiro for (const Object **ptr = stack->base; ptr < stack->top; ++ptr) { 34871ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro if (*ptr == obj) { 34971ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro return true; 35071ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro } 35171ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro } 35271ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro return false; 35371ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro} 35471ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro 35571ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro/* 35671ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro * Callback applied to marked objects. If the object is gray and on 35771ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro * an unmarked card an error is logged and the VM is aborted. Card 35871ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro * table verification occurs between root marking and weak reference 35971ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro * processing. We treat objects marked from the roots and weak 36071ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro * references specially as it is permissible for these objects to be 36171ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro * gray and on an unmarked card. 3625ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro */ 3630d92a4072c00434e95a03642a4944acf81a81cc3Carl Shapirostatic void verifyCardTableCallback(Object *obj, void *arg) 3645ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro{ 365fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro WhiteReferenceCounter ctx = { (HeapBitmap *)arg, 0 }; 3665ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 36757ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro dvmVisitObject(countWhiteReferenceVisitor, obj, &ctx); 36857ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro if (ctx.whiteRefs == 0) { 36957ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro return; 37057ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro } else if (isObjectDirty(obj)) { 37157ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro return; 37257ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro } else if (isReferentUnmarked(obj, &ctx)) { 37357ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro return; 37457ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro } else if (isWeakInternedString(obj)) { 37557ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro return; 37671ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro } else if (isPushedOnMarkStack(obj)) { 37771ce7a90945d1c26deea1eff84554b180a031afdCarl Shapiro return; 37857ee270b755271166b2349321e5b8b5457731dd7Carl Shapiro } else { 379c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE("Verify failed, object %p is gray and on an unmarked card", obj); 3805ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro dvmDumpObject(obj); 3817f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro dvmVisitObject(dumpWhiteReferenceVisitor, obj, &ctx); 3827f43c038ec330bd8807ef26a0de8616869e74fa1Carl Shapiro dumpReferences(obj); 3835ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro dvmAbort(); 3845ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro } 3855ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro} 3865ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro 3875ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro/* 3885ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro * Verifies that gray objects are on a dirty card. 3895ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro */ 3901e1433e78f560a01744e870c19c162ab88df9dc1Carl Shapirovoid dvmVerifyCardTable() 3915ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro{ 3925ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro HeapBitmap *markBits = gDvm.gcHeap->markContext.bitmap; 3935ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro dvmHeapBitmapWalk(markBits, verifyCardTableCallback, markBits); 3945ba39376c5b7a5878f234a689a51c74783583b4bCarl Shapiro} 395