1001159 - Simplify CellIterImpl and Arena::finalize()

Status: RESOLVED FIXED

(Core :: JavaScript: GC, defect)

Description

[Nicholas Nethercote [inactive]]

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.

Comment 1

[Nicholas Nethercote [inactive]]

Attachment: (part 1) - Split CellIterImpl and subclasses in two

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.

Comment 2

[Nicholas Nethercote [inactive]]

Attachment: (part 2) - Merge constructors and init() functions for cell iterator classes

This patch merges ZoneCellIterImpl::{initSpan,init}() and
ArenaCellIterImpl::{ArenaCellIterImpl,initSpan,init}().

initSpan() wasn't a good name for that function anyway.

Comment 3

[Nicholas Nethercote [inactive]]

Attachment: (part 3) - Remove ArenaCellIter::aiter

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.

Comment 4

[Nicholas Nethercote [inactive]]

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

[Lars T Hansen [:lth]]

(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.

Comment 6

[Nicholas Nethercote [inactive]]

> 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!

Comment 7

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

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.

Comment 8

[Nicholas Nethercote [inactive]]

Attachment: (part 1) - Split CellIterImpl and subclasses in two

This is almost the same as the previous version. Again, it's just the
mechanical splitting; follow-ups will clean this up.

Comment 9

[Nicholas Nethercote [inactive]]

Attachment: (part 2) - Rewrite ArenaCellIterImpl

This patch simplifies ArenaCellIterImpl greatly: no ArenaIter required, no
loops required.

Comment 10

[Nicholas Nethercote [inactive]]

Attachment: (part 3) - Rewrite ZoneCellIterImpl

This patch layers ZoneCellIterImpl on top of ArenaCellIterImpl, simplifying it
greatly.

Comment 11

[Nicholas Nethercote [inactive]]

Attachment: (part 4) - Remove |allClear| from Arena::finalize()

Comment 12

[Nicholas Nethercote [inactive]]

Attachment: (part 5) - Simple FreeSpan computation in Arena::finalize()

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.

Comment 13

[Nicholas Nethercote [inactive]]

Attachment: (part 6) - Used ArenaCellIterImpl in Arena::finalize()

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.

Comment 14

[Nicholas Nethercote [inactive]]

BTW, I'm not sure what the "UnderGC" suffix means. Does that mean it's happening during a GC?

Comment 15

[Nicholas Nethercote [inactive]]

Try push looks good:
https://tbpl.mozilla.org/?tree=Try&rev=cebec5ecaadf

Comment 16

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

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.

Comment 17

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

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?

Comment 18

[Lars T Hansen [:lth]]

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 19

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

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.

Comment 20

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

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.

Comment 21

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

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.

Comment 22

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

> 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.

Comment 23

[Nicholas Nethercote [inactive]]

(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.

Comment 24

[Nicholas Nethercote [inactive]]

Another good try run, testing the patches with comments addressed:
https://tbpl.mozilla.org/?tree=Try&rev=a4f2b0b90f9e

Comment 25

[Nicholas Nethercote [inactive]]

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

[Ed Morley [:emorley]]

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