Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
1772733002:
[heap] Move to two-level free-list (Closed)
|
Created:
4 years, 9 months ago by Michael Lippautz Modified:
4 years, 9 months ago CC:
v8-reviews_googlegroups.com, Hannes Payer (out of office), ulan Base URL:
https://chromium.googlesource.com/v8/v8.git@master Target Ref:
refs/pending/heads/master Project:
v8 Visibility:
Public. |
Description[heap] Move to two-level free-list
Before this CL, free memory (FreeSpace) has been managed through a global free
list that contains single-linked lists of FreeSpace nodes for each size class.
We move away from this approach to a global two-level doubly-linked list that
refers to singly-linked lists of FreeSpace nodes on the corresponding pages.
This way we can refill on a page-level granularity. Furthermore, it also enables
constant-time eviction of pages from the free list.
BUG=chromium:524425
LOG=N
Committed: https://crrev.com/da3b2661502c51c3c8ba5bb9ecb4d9784fe6b10c
Cr-Commit-Position: refs/heads/master@{#34853}
Patch Set 1 #Patch Set 2 : #Patch Set 3 : #Patch Set 4 : #Patch Set 5 : Addressed offline comments #Patch Set 6 : Removed owner_ fiel from FreeListCategory #Patch Set 7 : Rebase again #
Total comments: 8
Patch Set 8 : Removed left over of owner_, and fixed allocation in FindNodeFor to only try to retrieve a node onc… #
Total comments: 6
Patch Set 9 : Addressed comments #Patch Set 10 : Re-add heuristics that stops refilling all memory into a single compaction task #Patch Set 11 : Speed up very slow FreeList::IsVeryLong which is used in a regular DCHECK #
Total comments: 4
Patch Set 12 : Addressed comment #Patch Set 13 : Rebase after black allocation and parallelization bug fixes #Patch Set 14 : Eagerly remove empty categories #Patch Set 15 : Rebase on disabled black allocation #
Dependent Patchsets: Messages
Total messages: 62 (39 generated)
Patchset #2 (id:20001) has been deleted
Patchset #3 (id:60001) has been deleted
Patchset #3 (id:80001) has been deleted
Patchset #2 (id:40001) has been deleted
Description was changed from ========== [heap] Move FreeListCategory into pages. BUG= ========== to ========== [heap] Move FreeListCategory into pages. Detailed description TODO. BUG= ==========
mlippautz@chromium.org changed reviewers: + ulan@chromium.org
Please have a first look. Happy for any suggestions that make it less fragile. What's left is eagerly (constant time) removing unusable FreeSpace nodes (nodes on evacuation candidates and pages mark as not being used for allocation). (Essentially cleaning up FreeListCategory::PickNodeFromList, and FreeListCategory::SearchForNodeInList.)
Description was changed from ========== [heap] Move FreeListCategory into pages. Detailed description TODO. BUG= ========== to ========== [heap] FreeListCategory::PickNodeFromList. Detailed description TODO. BUG= ==========
Patchset #2 (id:100001) has been deleted
Patchset #3 (id:140001) has been deleted
Description was changed from ========== [heap] FreeListCategory::PickNodeFromList. Detailed description TODO. BUG= ========== to ========== [heap] Move to two-level free-list. Detailed description TODO. BUG= ==========
Description was changed from ========== [heap] Move to two-level free-list. Detailed description TODO. BUG= ========== to ========== [heap] Move to two-level free-list Detailed description TODO. BUG= ==========
Patchset #3 (id:160001) has been deleted
Description was changed from ========== [heap] Move to two-level free-list Detailed description TODO. BUG= ========== to ========== [heap] Move to two-level free-list Free space is currently managed in a global free list that contains single-linked lists for each size class. We move away from this to a two-level list where the global free list refers to size classes on the pages. This way we can refill on a page-level granularity. Furthermore, it also enables eviction of pages from the free list. BUG= ==========
Description was changed from ========== [heap] Move to two-level free-list Free space is currently managed in a global free list that contains single-linked lists for each size class. We move away from this to a two-level list where the global free list refers to size classes on the pages. This way we can refill on a page-level granularity. Furthermore, it also enables eviction of pages from the free list. BUG= ========== to ========== [heap] Move to two-level free-list Before this CL, free memory (FreeSpace) has been managed through a global free list that contains single-linked lists of FreeSpace's for each size class. We move away from this approach to a global two-level doubly-linked list that refers to singly-linked lists of FreeSpace nodes on the corresponding pages. This way we can refill on a page-level granularity. Furthermore, it also enables constant-time eviction of pages from the free list. BUG= ==========
Description was changed from ========== [heap] Move to two-level free-list Before this CL, free memory (FreeSpace) has been managed through a global free list that contains single-linked lists of FreeSpace's for each size class. We move away from this approach to a global two-level doubly-linked list that refers to singly-linked lists of FreeSpace nodes on the corresponding pages. This way we can refill on a page-level granularity. Furthermore, it also enables constant-time eviction of pages from the free list. BUG= ========== to ========== [heap] Move to two-level free-list Before this CL, free memory (FreeSpace) has been managed through a global free list that contains single-linked lists of FreeSpace nodes for each size class. We move away from this approach to a global two-level doubly-linked list that refers to singly-linked lists of FreeSpace nodes on the corresponding pages. This way we can refill on a page-level granularity. Furthermore, it also enables constant-time eviction of pages from the free list. BUG= ==========
Patchset #5 (id:220001) has been deleted
mlippautz@chromium.org changed reviewers: + hpayer@chromium.org
+Hannes Addressed offline comments: * General - Fixed accounting * FreeListCategory - non-atomic top pointer - removed end pointer - Already changed the eviction methods - Allocation methods do not incrementally remove nodes anymore
Patchset #7 (id:280001) has been deleted
Description was changed from ========== [heap] Move to two-level free-list Before this CL, free memory (FreeSpace) has been managed through a global free list that contains single-linked lists of FreeSpace nodes for each size class. We move away from this approach to a global two-level doubly-linked list that refers to singly-linked lists of FreeSpace nodes on the corresponding pages. This way we can refill on a page-level granularity. Furthermore, it also enables constant-time eviction of pages from the free list. BUG= ========== to ========== [heap] Move to two-level free-list Before this CL, free memory (FreeSpace) has been managed through a global free list that contains single-linked lists of FreeSpace nodes for each size class. We move away from this approach to a global two-level doubly-linked list that refers to singly-linked lists of FreeSpace nodes on the corresponding pages. This way we can refill on a page-level granularity. Furthermore, it also enables constant-time eviction of pages from the free list. BUG=chromium:524425 LOG=N ==========
Looking good. https://codereview.chromium.org/1772733002/diff/300001/src/heap/mark-compact.cc File src/heap/mark-compact.cc (right): https://codereview.chromium.org/1772733002/diff/300001/src/heap/mark-compact.... src/heap/mark-compact.cc:3496: List<Page*>* pages = swept_pages(space->identity()); Let's move it closer to the usage. https://codereview.chromium.org/1772733002/diff/300001/src/heap/mark-compact.... src/heap/mark-compact.cc:3730: List<Page*>* pages = swept_pages(space->identity()); Let's move it closer to the usage. https://codereview.chromium.org/1772733002/diff/300001/src/heap/spaces.h File src/heap/spaces.h (right): https://codereview.chromium.org/1772733002/diff/300001/src/heap/spaces.h#newc... src/heap/spaces.h:1720: int Free(Address start, int size_in_bytes, bool keep_local = false); Nit: enum would be better than bool https://codereview.chromium.org/1772733002/diff/300001/src/heap/spaces.h#newc... src/heap/spaces.h:2076: int wasted = free_list_.Free(start, size_in_bytes, keep_local); We can use UnaccountedFree here. https://codereview.chromium.org/1772733002/diff/320001/src/heap/spaces.cc File src/heap/spaces.cc (right): https://codereview.chromium.org/1772733002/diff/320001/src/heap/spaces.cc#new... src/heap/spaces.cc:1094: p->ForAllFreeListCategories([this](FreeListCategory* category) { [this] is not needed. I think the following makes the intention clearer: DCHECK_EQ(other, category->owner()) other->RemoveCategory(category); https://codereview.chromium.org/1772733002/diff/320001/src/heap/spaces.cc#new... src/heap/spaces.cc:1103: [this](FreeListCategory* category) { category->Relink(); }); [this] is not needed. DCHECK_EQ(this, category->owner()) https://codereview.chromium.org/1772733002/diff/320001/src/heap/spaces.cc#new... src/heap/spaces.cc:2439: if (category->owner() == this && category->is_linked()) { Shouldn't this be DCHECK?
Addressed comments, thanks a lot! This seems way less fragile now. https://codereview.chromium.org/1772733002/diff/300001/src/heap/mark-compact.cc File src/heap/mark-compact.cc (right): https://codereview.chromium.org/1772733002/diff/300001/src/heap/mark-compact.... src/heap/mark-compact.cc:3496: List<Page*>* pages = swept_pages(space->identity()); On 2016/03/09 15:03:57, ulan wrote: > Let's move it closer to the usage. Done. https://codereview.chromium.org/1772733002/diff/300001/src/heap/mark-compact.... src/heap/mark-compact.cc:3730: List<Page*>* pages = swept_pages(space->identity()); On 2016/03/09 15:03:57, ulan wrote: > Let's move it closer to the usage. Done. https://codereview.chromium.org/1772733002/diff/300001/src/heap/spaces.h File src/heap/spaces.h (right): https://codereview.chromium.org/1772733002/diff/300001/src/heap/spaces.h#newc... src/heap/spaces.h:1720: int Free(Address start, int size_in_bytes, bool keep_local = false); On 2016/03/09 15:03:57, ulan wrote: > Nit: enum would be better than bool Done. https://codereview.chromium.org/1772733002/diff/300001/src/heap/spaces.h#newc... src/heap/spaces.h:2076: int wasted = free_list_.Free(start, size_in_bytes, keep_local); On 2016/03/09 15:03:57, ulan wrote: > We can use UnaccountedFree here. I redid how UnaccountedFree and Free calls are used. The enum should make this clear now. https://codereview.chromium.org/1772733002/diff/320001/src/heap/spaces.cc File src/heap/spaces.cc (right): https://codereview.chromium.org/1772733002/diff/320001/src/heap/spaces.cc#new... src/heap/spaces.cc:1094: p->ForAllFreeListCategories([this](FreeListCategory* category) { On 2016/03/09 15:03:58, ulan wrote: > [this] is not needed. > > I think the following makes the intention clearer: > DCHECK_EQ(other, category->owner()) > other->RemoveCategory(category); Done. I added 2 new calls to PagedSpace. https://codereview.chromium.org/1772733002/diff/320001/src/heap/spaces.cc#new... src/heap/spaces.cc:1103: [this](FreeListCategory* category) { category->Relink(); }); On 2016/03/09 15:03:58, ulan wrote: > [this] is not needed. > > DCHECK_EQ(this, category->owner()) Done. https://codereview.chromium.org/1772733002/diff/320001/src/heap/spaces.cc#new... src/heap/spaces.cc:2439: if (category->owner() == this && category->is_linked()) { On 2016/03/09 15:03:58, ulan wrote: > Shouldn't this be DCHECK? The way we use the method we currently could have a DCHECK for "category->owner() == this". The second part is not always true (e.g. one of the categories on a page could be empty, and thus never be linked in). Since the second part is just an optimization, I added the DCHECK for the first part.
The CQ bit was checked by mlippautz@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1772733002/340001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1772733002/340001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: v8_linux_rel_ng on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux_rel_ng/builds/2694) v8_linux_rel_ng_triggered on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux_rel_ng_triggered/b...)
lgtm
Patchset #10 (id:360001) has been deleted
The CQ bit was checked by mlippautz@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1772733002/380001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1772733002/380001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: v8_mac_rel on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_mac_rel/builds/16833)
The CQ bit was checked by mlippautz@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1772733002/400001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1772733002/400001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
LGTM, just two minor nits. https://codereview.chromium.org/1772733002/diff/400001/src/heap/spaces.h File src/heap/spaces.h (right): https://codereview.chromium.org/1772733002/diff/400001/src/heap/spaces.h#newc... src/heap/spaces.h:341: bool Free(FreeSpace* node, int size_in_bytes, FreeMode mode); Why not templatize on mode? https://codereview.chromium.org/1772733002/diff/400001/src/heap/spaces.h#newc... src/heap/spaces.h:384: // category. remvove space
https://codereview.chromium.org/1772733002/diff/400001/src/heap/spaces.h File src/heap/spaces.h (right): https://codereview.chromium.org/1772733002/diff/400001/src/heap/spaces.h#newc... src/heap/spaces.h:341: bool Free(FreeSpace* node, int size_in_bytes, FreeMode mode); On 2016/03/11 09:56:24, Hannes Payer - slow wrote: > Why not templatize on mode? Templatizing FreeListCategory::Free would then require to templatize FreeList:Free, which is non-inlined and cannot easily put in spaces.h because of missing definitions (PagedSpace). https://codereview.chromium.org/1772733002/diff/400001/src/heap/spaces.h#newc... src/heap/spaces.h:384: // category. On 2016/03/11 09:56:24, Hannes Payer - slow wrote: > remvove space Done.
The CQ bit was checked by mlippautz@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1772733002/460001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1772733002/460001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: v8_win_rel_ng on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_win_rel_ng/builds/4344) v8_win_rel_ng_triggered on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_win_rel_ng_triggered/bui...)
The CQ bit was checked by machenbach@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from ulan@chromium.org, hpayer@chromium.org Link to the patchset: https://codereview.chromium.org/1772733002/#ps460001 (title: "Eagerly remove empty categories")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1772733002/460001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1772733002/460001
The CQ bit was unchecked by machenbach@chromium.org
The CQ bit was checked by machenbach@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1772733002/460001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1772733002/460001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
The CQ bit was checked by mlippautz@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1772733002/480001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1772733002/480001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
The CQ bit was checked by mlippautz@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from hpayer@chromium.org, ulan@chromium.org Link to the patchset: https://codereview.chromium.org/1772733002/#ps480001 (title: "Rebase on disabled black allocation")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1772733002/480001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1772733002/480001
Message was sent while issue was closed.
Description was changed from ========== [heap] Move to two-level free-list Before this CL, free memory (FreeSpace) has been managed through a global free list that contains single-linked lists of FreeSpace nodes for each size class. We move away from this approach to a global two-level doubly-linked list that refers to singly-linked lists of FreeSpace nodes on the corresponding pages. This way we can refill on a page-level granularity. Furthermore, it also enables constant-time eviction of pages from the free list. BUG=chromium:524425 LOG=N ========== to ========== [heap] Move to two-level free-list Before this CL, free memory (FreeSpace) has been managed through a global free list that contains single-linked lists of FreeSpace nodes for each size class. We move away from this approach to a global two-level doubly-linked list that refers to singly-linked lists of FreeSpace nodes on the corresponding pages. This way we can refill on a page-level granularity. Furthermore, it also enables constant-time eviction of pages from the free list. BUG=chromium:524425 LOG=N ==========
Message was sent while issue was closed.
Committed patchset #15 (id:480001)
Message was sent while issue was closed.
Description was changed from ========== [heap] Move to two-level free-list Before this CL, free memory (FreeSpace) has been managed through a global free list that contains single-linked lists of FreeSpace nodes for each size class. We move away from this approach to a global two-level doubly-linked list that refers to singly-linked lists of FreeSpace nodes on the corresponding pages. This way we can refill on a page-level granularity. Furthermore, it also enables constant-time eviction of pages from the free list. BUG=chromium:524425 LOG=N ========== to ========== [heap] Move to two-level free-list Before this CL, free memory (FreeSpace) has been managed through a global free list that contains single-linked lists of FreeSpace nodes for each size class. We move away from this approach to a global two-level doubly-linked list that refers to singly-linked lists of FreeSpace nodes on the corresponding pages. This way we can refill on a page-level granularity. Furthermore, it also enables constant-time eviction of pages from the free list. BUG=chromium:524425 LOG=N Committed: https://crrev.com/da3b2661502c51c3c8ba5bb9ecb4d9784fe6b10c Cr-Commit-Position: refs/heads/master@{#34853} ==========
Message was sent while issue was closed.
Patchset 15 (id:??) landed as https://crrev.com/da3b2661502c51c3c8ba5bb9ecb4d9784fe6b10c Cr-Commit-Position: refs/heads/master@{#34853} |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
