Closed
Bug 1001159
Opened 10 years ago
Closed 10 years ago
Simplify CellIterImpl and Arena::finalize()
Categories
(Core :: JavaScript: GC, defect)
Core
JavaScript: GC
Tracking
()
RESOLVED
FIXED
mozilla32
People
(Reporter: n.nethercote, Assigned: n.nethercote)
Details
Attachments
(6 files, 3 obsolete files)
34.08 KB,
patch
|
billm
:
review+
|
Details | Diff | Splinter Review |
4.53 KB,
patch
|
billm
:
review+
|
Details | Diff | Splinter Review |
3.66 KB,
patch
|
billm
:
review+
|
Details | Diff | Splinter Review |
2.43 KB,
patch
|
billm
:
review+
|
Details | Diff | Splinter Review |
4.39 KB,
patch
|
billm
:
review+
|
Details | Diff | Splinter Review |
4.07 KB,
patch
|
billm
:
review+
|
Details | Diff | Splinter Review |
CellIterImpl and its subclasses are hard to read because there are two modes: - Iterating over all cells in a Zone - Iterating over all cells in an Arena There are two init() functions, one for each mode. Furthermore, I think there's a subtle bug in the single-Arena mode which could cause use to iterate one cell into the subsequent arena. Imagine you want to iterate over an empty arena. In the current code, you'll call next() from init(ArenaHeader*). The first time around the loop you'll have the not-real initial values for |span| and |thing|, so you'll hit the aiter.get() case, which is fine -- this gets the passed-in arena. But if this arena is empty, the second time around the loop you'll again skip past the first two conditions and hit the aiter.done() case. If there's a subsequent arena, you'll enter it -- even though we're supposed to be iterating only through one arena! There's an argument-less aiter.init() call in init(ArenaHeader*) which usually prevents iterating into that next arena, but it occurs *after* that first next() call. I added some diagnostic code and we don't seem to be hitting this case in practice. Perhaps it's just luck, or perhaps there are other structural constraints preventing it. Either way, it gives me the heebie-jeebies and I want to fix it.
Assignee | ||
Comment 1•10 years ago
|
||
This patch separates CellIterImpl in two, to distinguish the two modes. Specifically: - CellIterImpl becomes ZoneCellIterImpl and ArenaIterImpl (and each class gets one of the init() functions). - CellIterUnderGC becomes ZoneCellIterUnderGC and ArenaIterUnderGC (ditto). - CellIter becomes ZoneCellIter (no ArenaIter is needed). This patch is very mechanical, and involves some code duplication. The subsequent patches will improve on that.
Attachment #8412164 -
Flags: review?(wmccloskey)
Assignee | ||
Comment 2•10 years ago
|
||
This patch merges ZoneCellIterImpl::{initSpan,init}() and ArenaCellIterImpl::{ArenaCellIterImpl,initSpan,init}(). initSpan() wasn't a good name for that function anyway.
Attachment #8412166 -
Flags: review?(wmccloskey)
Assignee | ||
Comment 3•10 years ago
|
||
This patch removes the now-unnecessary ArenaIter from ArenaCellIterImpl. This fixes the potential bug mentioned in comment 0 -- if the passed-in arena is entirely empty, we now just set |cell| to null and so done() will succeed. It also gets rid of one initAsEmpty() call, which is good, because I want to eliminate that function -- it's horrible.
Attachment #8412170 -
Flags: review?(wmccloskey)
Assignee | ||
Comment 4•10 years ago
|
||
I have other ideas to clean up these iterator classes further, but making the zone vs. arena split clearer and fixing the potential next-arena defect is probably enough for this bug.
Comment 5•10 years ago
|
||
(In reply to Nicholas Nethercote [:njn] from comment #0) > CellIterImpl and its subclasses are hard to read because there are two modes: > - Iterating over all cells in a Zone > - Iterating over all cells in an Arena > There are two init() functions, one for each mode. +1. Also the Zone version does not really iterate across a Zone as much as across an Allocator (the Zone itself is just used for some asserts); I have patches in progress that make use of that simplification.
Assignee | ||
Comment 6•10 years ago
|
||
> Also the Zone version does not really iterate across a Zone as much as
> across an Allocator (the Zone itself is just used for some asserts); I have
> patches in progress that make use of that simplification.
Oh, interesting. I didn't even know about the Allocator class. Please feel free to provide additional review for these patches!
This seems nice, but I don't like the extra duplication, especially for such tricky code. Ideally we could keep an instance of ArenaCellIterImpl as a member of ZoneCellIterImpl and call some sort of reset method on it every time we want to move to a new arena. That reset method could be private and friended to ZoneCellIterImpl maybe. Do you think you could try to do that? The reason the problem you mentioned in comment 0 doesn't happen is that we never iterate over empty arenas. The sweeping code immediately removes empty arenas from the usual arena lists. I admit that we should at least have an assertion or something about that though.
Assignee | ||
Comment 8•10 years ago
|
||
This is almost the same as the previous version. Again, it's just the mechanical splitting; follow-ups will clean this up.
Attachment #8414924 -
Flags: review?(wmccloskey)
Assignee | ||
Updated•10 years ago
|
Attachment #8412164 -
Attachment is obsolete: true
Attachment #8412164 -
Flags: review?(wmccloskey)
Assignee | ||
Comment 9•10 years ago
|
||
This patch simplifies ArenaCellIterImpl greatly: no ArenaIter required, no loops required.
Attachment #8414925 -
Flags: review?(wmccloskey)
Assignee | ||
Comment 10•10 years ago
|
||
This patch layers ZoneCellIterImpl on top of ArenaCellIterImpl, simplifying it greatly.
Attachment #8414926 -
Flags: review?(wmccloskey)
Assignee | ||
Comment 11•10 years ago
|
||
Attachment #8414927 -
Flags: review?(wmccloskey)
Assignee | ||
Comment 12•10 years ago
|
||
Arena::finalize() is complex. In particular, the logic underlying the creation of the new free list is spread throughout. This patch simplifies things. - The logic underlying the creation of the new list is more concentrated. In particular, none of it is in the |thing == nextFree.first| branch; this will allow this loop to be later re-written in terms of an single-arena cell iterator. - There are some extra assertions to make sure the computation of |nfree| is sensible. - It moves the arena-is-entirely-free case after the full (DEBUG-only checking) -- there's no point in excluding it from that checking.
Attachment #8414929 -
Flags: review?(wmccloskey)
Assignee | ||
Comment 13•10 years ago
|
||
There are two things I'm uncertain about in this patch. - I had to comment out the assertion in ArenaCellIterImpl::init(). I don't entirely understand what this assertion does. - I'm using ArenaCellIterImpl directly in Arena::finalize(), which feels gross. One possibility for solving both problems is to implement a new iterator on top of ArenaCellIterImpl (ArenaCellIter?) and move the assertion into ArenaCellIterUnderGC.
Attachment #8414931 -
Flags: review?(wmccloskey)
Assignee | ||
Updated•10 years ago
|
Attachment #8412166 -
Attachment is obsolete: true
Attachment #8412166 -
Flags: review?(wmccloskey)
Assignee | ||
Updated•10 years ago
|
Attachment #8412170 -
Attachment is obsolete: true
Attachment #8412170 -
Flags: review?(wmccloskey)
Assignee | ||
Updated•10 years ago
|
Summary: Split CellIterImpl in two → Simplify CellIterImpl and Arena::finalize()
Assignee | ||
Comment 14•10 years ago
|
||
BTW, I'm not sure what the "UnderGC" suffix means. Does that mean it's happening during a GC?
Assignee | ||
Comment 15•10 years ago
|
||
Try push looks good: https://tbpl.mozilla.org/?tree=Try&rev=cebec5ecaadf
Attachment #8414924 -
Flags: review?(wmccloskey) → review+
Comment on attachment 8414925 [details] [diff] [review] (part 2) - Rewrite ArenaCellIterImpl Review of attachment 8414925 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/jsgcinlines.h @@ +165,5 @@ > > + // Upon entry, |thing| points to any thing (free or used) and finds the > + // first used thing, which may be |thing|. > + void moveForwardIfFree() { > + MOZ_ASSERT(!done()); Please use JS_ASSERT here and everywhere else. @@ +179,5 @@ > > public: > + ArenaCellIterImpl() {} > + > + void init(ArenaHeader *aheader) { Can we move this code to the constructor? The reason we had the init routines before was to share common code between the zone and arena constructors. Now that we only have one case, I think we can just move everything to the constructor (unless something changes in later patches...). @@ +180,5 @@ > public: > + ArenaCellIterImpl() {} > + > + void init(ArenaHeader *aheader) { > + MOZ_ASSERT(aheader); Please just remove this one. We'll safely crash on the next line if we get null.
Attachment #8414925 -
Flags: review?(wmccloskey) → review+
Comment on attachment 8414926 [details] [diff] [review] (part 3) - Rewrite ZoneCellIterImpl Review of attachment 8414926 [details] [diff] [review]: ----------------------------------------------------------------- Oh, I see. You're using init() as the reset method for this patch. Please disregard my remark from before. Although it would be nice if we could avoid recomputing thingSize for every arena. ::: js/src/jsgcinlines.h @@ +226,5 @@ > > class ZoneCellIterImpl > { > + ArenaIter aIter; > + ArenaCellIterImpl acIter; How about calling these arenaIter and cellIter?
Attachment #8414926 -
Flags: review?(wmccloskey) → review+
Attachment #8414927 -
Flags: review?(wmccloskey) → review+
Comment 18•10 years ago
|
||
FWIW, more changes to CellIterUnderGC (to support PJS garbage collection) are coming, currently at the bottom of this patch: https://bug933313.bugzilla.mozilla.org/attachment.cgi?id=8415333 Basically it bypasses the Zone because I have Allocators that are not attached to Zones.
Comment on attachment 8414929 [details] [diff] [review] (part 5) - Simple FreeSpan computation in Arena::finalize() Review of attachment 8414929 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/jsgc.cpp @@ +499,5 @@ > nfree += (newListTail->last + 1 - newListTail->first) / thingSize; > JS_ASSERT(nfree + nmarked == thingsPerArena(thingSize)); > #endif > + > + if (nmarked == 0) { Not sure why you moved this down. It just causes us to do a little extra work. Did you want to get the assertions to run? In any case, I think I'd rather it stay where it is. Asserting here that |firstThingOrSuccessorOfLastMarkedThing == thingsStart(thingKind)| covers pretty much everything we might be concerned about, I think.
Attachment #8414929 -
Flags: review?(wmccloskey) → review+
Comment on attachment 8414931 [details] [diff] [review] (part 6) - Used ArenaCellIterImpl in Arena::finalize() Review of attachment 8414931 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/jsgc.cpp @@ +448,4 @@ > uintptr_t lastByte = thingsEnd() - 1; > > + ArenaCellIterImpl i; > + i.init(&aheader); It would be nice for ArenaCellIterImpl (or ArenaCellIterUnderFinalize, as in the next comment) to have a constructor taking an ArenaHeader*. Then we could move the def of i to the for loop below: for (ArenaCellIterUnderFinalize i(&aheader); !i.done(); i.next()) { ... } I think that would be nice. ::: js/src/jsgcinlines.h @@ +183,5 @@ > > void init(ArenaHeader *aheader) { > MOZ_ASSERT(aheader); > AllocKind kind = aheader->getAllocKind(); > + //MOZ_ASSERT(aheader->zone->allocator.arenas.isSynchronizedFreeList(kind)); Let's just expose a method initUnsynchronized or something that doesn't run this assertion. Then we'd also have an init() method that would do the assert and call initUnsynchronized. Then let's have two subclasses: ArenaCellIterUnderGC: constructor calls init ArenaCellIterUnderFinalize: constructor calls initUnsynchronized and use the latter from Arena::finalize. The main thing I want to ensure is that ZoneCellIterImpl runs the assertion on every arena that it gets.
Attachment #8414931 -
Flags: review?(wmccloskey) → review+
Thanks Nick. These changes are fantastic. The UnderGC stuff is indeed intended to be run during GC. They bypass some code that's not needed during GC: waiting for background finalization, doing a minor GC, and synchronizing the free lists. It probably makes sense to explain freelist synchronization. Normally, we store the first FreeSpan for an Arena in its ArenaHeader. However, if we're allocating into an Arena, then we store the FreeSpan in the Zone (well, the Allocator for the Zone). (We could have the allocator load the current Arena being allocated into and then read the FreeSpan from that, but it would cost us an extra load.) We don't keep the ArenaHeader's FreeSpan up to date while we're allocating into that Arena. But that means that whenever we want to iterate over Arenas, we need to copy the FreeSpan for the Arena being allocated into back to its ArenaHeader. The CellIter class automatically copies the FreeList back to the ArenaHeader in its constructor. We don't do that for CellIterUnderGC. It just asserts that things are already synchronized because the GC is supposed to take care of that. However, Arena::finalize is not exactly part of the GC. It can run on the background sweeping thread at the same time that same time that the mutator is allocating. So that's why that assertion was failing.
> The main thing I want to ensure is that ZoneCellIterImpl runs the assertion on every arena
> that it gets.
I guess this actually doesn't make much sense since the assertion only looks at the current arena being allocated into, which should be the same for every Arena of a given thingKind in the Zone. So just do whatever makes sense to you here.
Assignee | ||
Comment 23•10 years ago
|
||
(In reply to Lars T Hansen [:lth] from comment #18) > FWIW, more changes to CellIterUnderGC (to support PJS garbage collection) > are coming, currently at the bottom of this patch: > > https://bug933313.bugzilla.mozilla.org/attachment.cgi?id=8415333 > > Basically it bypasses the Zone because I have Allocators that are not > attached to Zones. I *think* my changes won't cause major conflicts with you -- you'll need to do some rebasing, but you're mostly adding new init()/constructor functions, and that should also be doable with my split design.
Assignee | ||
Comment 24•10 years ago
|
||
Another good try run, testing the patches with comments addressed: https://tbpl.mozilla.org/?tree=Try&rev=a4f2b0b90f9e
Assignee | ||
Comment 25•10 years ago
|
||
I landed these in two tranches of three patches each, because it might help with identifying perf regressions. https://hg.mozilla.org/integration/mozilla-inbound/rev/a973436eb53b https://hg.mozilla.org/integration/mozilla-inbound/rev/967225ce2e68 https://hg.mozilla.org/integration/mozilla-inbound/rev/d3078c201af6 https://hg.mozilla.org/integration/mozilla-inbound/rev/91b0fd14307e https://hg.mozilla.org/integration/mozilla-inbound/rev/be78a818fbd8 https://hg.mozilla.org/integration/mozilla-inbound/rev/5a056bb6be0c
Comment 26•10 years ago
|
||
https://hg.mozilla.org/mozilla-central/rev/a973436eb53b https://hg.mozilla.org/mozilla-central/rev/967225ce2e68 https://hg.mozilla.org/mozilla-central/rev/d3078c201af6 https://hg.mozilla.org/mozilla-central/rev/91b0fd14307e https://hg.mozilla.org/mozilla-central/rev/be78a818fbd8 https://hg.mozilla.org/mozilla-central/rev/5a056bb6be0c
Status: ASSIGNED → RESOLVED
Closed: 10 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla32
You need to log in
before you can comment on or make changes to this bug.
Description
•