Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
616483002:
Oilpan: Replace the positive heap-contains cache with a binary search tree of memory regions. (Closed)
|
Created:
6 years, 2 months ago by zerny-chromium Modified:
6 years, 2 months ago CC:
blink-reviews, kouhei+heap_chromium.org, mkwst+moarreviews_chromium.org, oilpan-reviews Base URL:
svn://svn.chromium.org/blink/trunk Project:
blink Visibility:
Public. |
DescriptionOilpan: Replace the positive heap-contains cache with a binary search tree of memory regions.
R=ager@chromium.org, wibling@chromium.org
BUG=419760, 420086
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=183139
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=183184
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=183259
Patch Set 1 #Patch Set 2 : lock and deletion #Patch Set 3 : dead code #Patch Set 4 : committed state on region #Patch Set 5 : remove ThreadState::checkAndMarkPointer #
Total comments: 16
Patch Set 6 : osPageSize #Patch Set 7 : revert osPageSize #Patch Set 8 : relocate alignment #
Total comments: 8
Patch Set 9 : RC #Patch Set 10 : RC2 #
Total comments: 11
Patch Set 11 : RC3 #Patch Set 12 : fix heap tests #Patch Set 13 : don't scan orphaned pages (which are zapped) #Patch Set 14 : fix detachMainThread issue #Patch Set 15 : revert detachMainThread fix and delete assertion in remove #Patch Set 16 : lookup assert #
Messages
Total messages: 36 (8 generated)
https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... File Source/platform/heap/Heap.cpp (right): https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... Source/platform/heap/Heap.cpp:319: bool m_committed[blinkPagesPerRegion]; Regarding PageMemory state in the region, it seems like we should restructure the PageMemoryRegion/PageMemory relationship so that the region owns the page memory and sets it up on allocation instead of this happening from the outside via setupPageMemoryInRegion. For now, this seems like the smallest change that provides the necessary state to lookup the pages of a region. https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... Source/platform/heap/Heap.cpp:2174: // TODO: What if the thread owning this page is terminating? This issue changes the objects which might be marked in a conservative scan. Right now a conservatively found pointer to a terminated thread will be marked (in the orphan pool) whereas it would not be before. It seems that it is better to just mark the object thereby retaining the page in the orphan pool, but we could get the previous behavior by checking if page->threadState()->isTerminating()
https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... File Source/platform/heap/Heap.cpp (right): https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... Source/platform/heap/Heap.cpp:315: return (address - base()) / blinkPageSize; This was incorrect. Forgot to add the guard page to the base. Uploaded a new patch.
https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... File Source/platform/heap/Heap.cpp (right): https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... Source/platform/heap/Heap.cpp:315: return (address - base()) / blinkPageSize; On 2014/10/01 10:34:59, zerny-chromium wrote: > This was incorrect. Forgot to add the guard page to the base. Uploaded a new > patch. No, it is correct. The first guard page is part of the first page. Sorry for the noise. Reverted that but kept the modulo assert for good measure.
LGTM https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... File Source/platform/heap/Heap.cpp (right): https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... Source/platform/heap/Heap.cpp:191: decommitPage(page); Can we use another name than decommit/commit here? markUnused/markUsed? Reading this I was getting confused and was looking through to see where in this call path we actually decommit. https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... Source/platform/heap/Heap.cpp:319: bool m_committed[blinkPagesPerRegion]; Should we use slightly different terminology here? m_inUse? https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... Source/platform/heap/Heap.cpp:2174: // TODO: What if the thread owning this page is terminating? On 2014/10/01 09:28:54, zerny-chromium wrote: > This issue changes the objects which might be marked in a conservative scan. > Right now a conservatively found pointer to a terminated thread will be marked > (in the orphan pool) whereas it would not be before. It seems that it is better > to just mark the object thereby retaining the page in the orphan pool, but we > could get the previous behavior by checking if > page->threadState()->isTerminating() My gut reaction is that it would be best to filter them out. We don't want to keep pages around and mapped just because they are hit by what looks like pointers on the stack. I don't think it actually matters much though. In practice we get a precise GC often in any case which will free up the pages kept alive by conservative stack scanning. https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... Source/platform/heap/Heap.cpp:2758: MutexLocker locker(markingMutex()); Nit: Maybe just introduced a regionTreeMutex that is only ever taken on access to the region tree? It is easier to reason about a mutex that is only used for one thing. https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... Source/platform/heap/Heap.cpp:2764: // No locking because regions are only added in ThreadState::prepareForGC which is in a GCScope. Can we add an assert here to trigger if we ever attempt to add a page memory region when all other threads are not stopped? Something like ASSERT(ThreadState::isAnyThreadInGC()). https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... Source/platform/heap/Heap.cpp:2789: if (!newTree) ASSERT(newTree) instead? Do we ever actually want to call this with a null pointer? If 'new' fails we are out of memory and cannot continue anyway and will get a null pointer crash on the next line.
Thanks for the review! https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... File Source/platform/heap/Heap.cpp (right): https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... Source/platform/heap/Heap.cpp:191: decommitPage(page); On 2014/10/01 11:29:01, Mads Ager (chromium) wrote: > Can we use another name than decommit/commit here? markUnused/markUsed? > > Reading this I was getting confused and was looking through to see where in this > call path we actually decommit. Done. https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... Source/platform/heap/Heap.cpp:319: bool m_committed[blinkPagesPerRegion]; On 2014/10/01 11:29:01, Mads Ager (chromium) wrote: > Should we use slightly different terminology here? m_inUse? Done. https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... Source/platform/heap/Heap.cpp:2174: // TODO: What if the thread owning this page is terminating? On 2014/10/01 11:29:01, Mads Ager (chromium) wrote: > On 2014/10/01 09:28:54, zerny-chromium wrote: > > This issue changes the objects which might be marked in a conservative scan. > > Right now a conservatively found pointer to a terminated thread will be marked > > (in the orphan pool) whereas it would not be before. It seems that it is > better > > to just mark the object thereby retaining the page in the orphan pool, but we > > could get the previous behavior by checking if > > page->threadState()->isTerminating() > > My gut reaction is that it would be best to filter them out. We don't want to > keep pages around and mapped just because they are hit by what looks like > pointers on the stack. I don't think it actually matters much though. In > practice we get a precise GC often in any case which will free up the pages kept > alive by conservative stack scanning. As discussed offline, we will mark the pointer on a orphaned page since it will still be reclaimed on the next precise GC and could prevent a (far fetched programming error induced) use-after-free possibility. https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... Source/platform/heap/Heap.cpp:2758: MutexLocker locker(markingMutex()); On 2014/10/01 11:29:00, Mads Ager (chromium) wrote: > Nit: Maybe just introduced a regionTreeMutex that is only ever taken on access > to the region tree? It is easier to reason about a mutex that is only used for > one thing. Done. https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... Source/platform/heap/Heap.cpp:2764: // No locking because regions are only added in ThreadState::prepareForGC which is in a GCScope. On 2014/10/01 11:29:01, Mads Ager (chromium) wrote: > Can we add an assert here to trigger if we ever attempt to add a page memory > region when all other threads are not stopped? Something like > ASSERT(ThreadState::isAnyThreadInGC()). Done. https://codereview.chromium.org/616483002/diff/80001/Source/platform/heap/Hea... Source/platform/heap/Heap.cpp:2789: if (!newTree) On 2014/10/01 11:29:01, Mads Ager (chromium) wrote: > ASSERT(newTree) instead? Do we ever actually want to call this with a null > pointer? If 'new' fails we are out of memory and cannot continue anyway and will > get a null pointer crash on the next line. I use the possibility of adding a null in RegionTree::remove when adding the possibly empty left and right children of a removed node. I'll move the null check back there and assert non-null here instead.
lgtm, nice change! https://codereview.chromium.org/616483002/diff/140001/Source/platform/heap/He... File Source/platform/heap/Heap.cpp (right): https://codereview.chromium.org/616483002/diff/140001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:211: ASSERT(Heap::heapDoesNotContainCacheIsEmpty()); NIT: It would be nice with an ASSERT here checking that size is divisible by numPages and also that numPages is <= blinkPagesPerRegion since we don't support anymore. https://codereview.chromium.org/616483002/diff/140001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:1233: m_threadState->allocatedRegionsSinceLastGC().append(region); NIT: Perhaps add a comment about the race we discussed where a thread steals all the pages and subsequently terminates before a GC has propagated this region to the tree. https://codereview.chromium.org/616483002/diff/140001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:2795: context = (base < current->m_region->base()) ? ¤t->m_left : ¤t->m_right; You could make this a real if and add an assert in the else case to check "base" is not contained in current. https://codereview.chromium.org/616483002/diff/140001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:2807: while (region != current->m_region) { NIT: Why the "while" here instead of the for loop used above?
Thanks for the feedback. Fixes uploaded. FYI, I get between 10-15% improvement for LargeDistributionWithoutLayout and EventsDispatchingInShadowTrees, so it looks like a net win over parallel scanning. Thanks for the heads-up Haraken! :-) https://codereview.chromium.org/616483002/diff/140001/Source/platform/heap/He... File Source/platform/heap/Heap.cpp (right): https://codereview.chromium.org/616483002/diff/140001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:211: ASSERT(Heap::heapDoesNotContainCacheIsEmpty()); On 2014/10/01 13:12:16, wibling-chromium wrote: > NIT: It would be nice with an ASSERT here checking that size is divisible by > numPages and also that numPages is <= blinkPagesPerRegion since we don't support > anymore. Sure. Added the slightly tighter: ASSERT(numPages == 1 || numPages == blinkPagesPerRegion); ASSERT(numPages == 1 || size % blinkPageSize == numPages); https://codereview.chromium.org/616483002/diff/140001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:1233: m_threadState->allocatedRegionsSinceLastGC().append(region); On 2014/10/01 13:12:16, wibling-chromium wrote: > NIT: Perhaps add a comment about the race we discussed where a thread steals all > the pages and subsequently terminates before a GC has propagated this region to > the tree. Mads suggested rewriting so we always take at least one page and only then add to the pool. This way the (probably purely theoretic) race is eliminated. https://codereview.chromium.org/616483002/diff/140001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:2795: context = (base < current->m_region->base()) ? ¤t->m_left : ¤t->m_right; On 2014/10/01 13:12:16, wibling-chromium wrote: > You could make this a real if and add an assert in the else case to check "base" > is not contained in current. Are you OK with keeping the if-expr and unconditionally asserting !current->m_region->contains(base) ? https://codereview.chromium.org/616483002/diff/140001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:2807: while (region != current->m_region) { On 2014/10/01 13:12:16, wibling-chromium wrote: > NIT: Why the "while" here instead of the for loop used above? current is needed outside and the assert structure is asserting on current. I've rewritten to a for-loop with an empty init (preferring to initialize the variable immediately) and let the assert be on *context. Better?
haraken@chromium.org changed reviewers: + haraken@chromium.org
This is a nice change! LGTM. https://codereview.chromium.org/616483002/diff/170001/Source/platform/heap/He... File Source/platform/heap/Heap.cpp (right): https://codereview.chromium.org/616483002/diff/170001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:213: ASSERT(numPages == 1 || size % blinkPageSize == numPages); Can we add a comment and mention that 'numPages == 1' means a large object? Or a slightly better approach might be to introduce helper methods like PageMemoryRegion::allocateNormalPages() and PageMemoryRegion::allocateLargeObject(). https://codereview.chromium.org/616483002/diff/170001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:1249: } Probably a simpler way to do this would be just to rewrite the previous code to: Before: pageMemory = Heap::freePagePool()->takeFreePage(m_index); After: while (!pageMemory) pageMemory = Heap::freePagePool()->takeFreePage(m_index); https://codereview.chromium.org/616483002/diff/170001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:2188: // TODO: We only need to set the conservative flag if checkAndMarkPointer actually marked the pointer. TODO => FIXME https://codereview.chromium.org/616483002/diff/170001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:2772: // Deletion of large objects (and thus their region) can happen concurrently their region => their regions https://codereview.chromium.org/616483002/diff/170001/Source/platform/heap/Th... File Source/platform/heap/ThreadState.h (right): https://codereview.chromium.org/616483002/diff/170001/Source/platform/heap/Th... Source/platform/heap/ThreadState.h:722: Vector<PageMemoryRegion*> m_allocatedRegionsSinceLastGC; Just to confirm: This PageMemoryRegion* shouldn't become a dangling pointer because PageMemoryRegions will never be destructed until the next GC happens (and at the point where the next GC happens, m_allocatedRegionsSinceLastGC is already cleared).
Thanks for the review! https://codereview.chromium.org/616483002/diff/170001/Source/platform/heap/He... File Source/platform/heap/Heap.cpp (right): https://codereview.chromium.org/616483002/diff/170001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:213: ASSERT(numPages == 1 || size % blinkPageSize == numPages); On 2014/10/02 02:31:35, haraken wrote: > > Can we add a comment and mention that 'numPages == 1' means a large object? > > Or a slightly better approach might be to introduce helper methods like > PageMemoryRegion::allocateNormalPages() and > PageMemoryRegion::allocateLargeObject(). Done. https://codereview.chromium.org/616483002/diff/170001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:1249: } On 2014/10/02 02:31:35, haraken wrote: > > Probably a simpler way to do this would be just to rewrite the previous code to: > > Before: > pageMemory = Heap::freePagePool()->takeFreePage(m_index); > > After: > while (!pageMemory) > pageMemory = Heap::freePagePool()->takeFreePage(m_index); That won't eliminate the chance that the ThreadState allocating the PageMemoryRegion will not actually get committed page on that region. It could happen that after adding the pages to the pool some other threads grab them before we get to the takeFreePage call. The new (and slightly more complicated) code avoids this by not adding the first committed page to the pool at all. https://codereview.chromium.org/616483002/diff/170001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:2188: // TODO: We only need to set the conservative flag if checkAndMarkPointer actually marked the pointer. On 2014/10/02 02:31:35, haraken wrote: > > TODO => FIXME Done. And removed the first TODO because it is safer to just mark the orphaned objects (the won't be traced further because they are filtered when popping from the marking stack). https://codereview.chromium.org/616483002/diff/170001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:2772: // Deletion of large objects (and thus their region) can happen concurrently On 2014/10/02 02:31:35, haraken wrote: > > their region => their regions Done. https://codereview.chromium.org/616483002/diff/170001/Source/platform/heap/Th... File Source/platform/heap/ThreadState.h (right): https://codereview.chromium.org/616483002/diff/170001/Source/platform/heap/Th... Source/platform/heap/ThreadState.h:722: Vector<PageMemoryRegion*> m_allocatedRegionsSinceLastGC; On 2014/10/02 02:31:35, haraken wrote: > > Just to confirm: This PageMemoryRegion* shouldn't become a dangling pointer > because PageMemoryRegions will never be destructed until the next GC happens > (and at the point where the next GC happens, m_allocatedRegionsSinceLastGC is > already cleared). Exactly. Even for a worker thread that is destructed it will do a thread-local gc which in its prepareForGC will move the regions to the global tree.
https://codereview.chromium.org/616483002/diff/170001/Source/platform/heap/He... File Source/platform/heap/Heap.cpp (right): https://codereview.chromium.org/616483002/diff/170001/Source/platform/heap/He... Source/platform/heap/Heap.cpp:1249: } On 2014/10/02 07:48:42, zerny-chromium wrote: > On 2014/10/02 02:31:35, haraken wrote: > > > > Probably a simpler way to do this would be just to rewrite the previous code > to: > > > > Before: > > pageMemory = Heap::freePagePool()->takeFreePage(m_index); > > > > After: > > while (!pageMemory) > > pageMemory = Heap::freePagePool()->takeFreePage(m_index); > > That won't eliminate the chance that the ThreadState allocating the > PageMemoryRegion will not actually get committed page on that region. It could > happen that after adding the pages to the pool some other threads grab them > before we get to the takeFreePage call. The new (and slightly more complicated) > code avoids this by not adding the first committed page to the pool at all. Makes sense!
The CQ bit was checked by zerny@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/616483002/190001
The CQ bit was unchecked by commit-bot@chromium.org
Try jobs failed on following builders: linux_blink_rel on tryserver.blink (http://build.chromium.org/p/tryserver.blink/builders/linux_blink_rel/builds/2...)
The CQ bit was checked by zerny@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/616483002/210001
The CQ bit was unchecked by commit-bot@chromium.org
Try jobs failed on following builders: linux_blink_rel on tryserver.blink (http://build.chromium.org/p/tryserver.blink/builders/linux_blink_rel/builds/2...)
The CQ bit was checked by zerny@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/616483002/230001
Message was sent while issue was closed.
Committed patchset #13 (id:230001) as 183139
Message was sent while issue was closed.
A revert of the patch was committed in https://codereview.chromium.org/618353004 The problem was that detaching the main thread does not result in a GC and the following cleanup of pages will then delete a region that has not been added to the global tree. Patch set 14 fixes this issue by explicitly preparing the region tree on detachMainThread. PTAL.
Message was sent while issue was closed.
LGTM
Message was sent while issue was closed.
LGTM
The CQ bit was checked by zerny@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/616483002/250001
Message was sent while issue was closed.
Committed patchset #14 (id:250001) as 183184
This was reverted again due to crbug.com/420086. The cause is that detachMainThread does not happen in connection to a GC (and the addPageMemoryRegion assert will fail) but it is also unsafe since sweeping thread could be removing regions at the same time. Instead I've removed the "contains" assert from RegionTree::remove and removed the prepareRegionTree from detachMainThread. So now only a GCing thread can add regions and we don't require the tree to be fully populated so that shutdown can take place. I also added an "in GC" assert to Heap::lookup which should only be used for the stack scan. PTAL
Still LGTM. Thanks for working on this!
The CQ bit was checked by zerny@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/616483002/290001
Message was sent while issue was closed.
Committed patchset #16 (id:290001) as 183259
Message was sent while issue was closed.
Any chance this is causing the hangs in: https://build.chromium.org/p/chromium.win/builders/Win7%20Tests%20(dbg)(1)/bu... I'm considering a speculative revert in the next few minutes.
Message was sent while issue was closed.
On 2014/10/06 16:38:55, ccameron1 wrote: > Any chance this is causing the hangs in: > > https://build.chromium.org/p/chromium.win/builders/Win7%20Tests%20(dbg)(1)/bu... > > I'm considering a speculative revert in the next few minutes. I would say that there is very little chance that this is related. That test was flaky when I was the gardener two weeks ago as well.
Message was sent while issue was closed.
On 2014/10/06 16:42:03, Mads Ager (chromium) wrote: > On 2014/10/06 16:38:55, ccameron1 wrote: > > Any chance this is causing the hangs in: > > > > > https://build.chromium.org/p/chromium.win/builders/Win7%20Tests%20(dbg)(1)/bu... > > > > I'm considering a speculative revert in the next few minutes. > > I would say that there is very little chance that this is related. That test was > flaky when I was the gardener two weeks ago as well. https://code.google.com/p/chromium/issues/detail?id=417756 Marked as fixed, but maybe it isn't? |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
