Closed Bug 569422 Opened 14 years ago Closed 13 years ago

Allocate Shapes from the GC heap

Categories

(Core :: JavaScript Engine, defect)

Other Branch
defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: gal, Assigned: billm)

References

Details

(Whiteboard: fixed-in-tracemonkey)

Attachments

(4 files, 7 obsolete files)

8.38 KB, patch
brendan
: review+
Details | Diff | Splinter Review
22.75 KB, patch
brendan
: review+
Details | Diff | Splinter Review
59.87 KB, patch
brendan
: review+
Details | Diff | Splinter Review
10.18 KB, patch
luke
: review+
Details | Diff | Splinter Review
We currently mark with a mark bit in the data itself. That's very cache inefficient.
Don't touch this until bug 558451 is fixed.

Also, how about some measurements? Asserting inefficiency, as you like to point out re: hand-optimizing code, is hard to do in our modern world of super-scalar CPUs, optimizing compilers, and complex C++ sources.

Finally, the properties are in a dedicated heap so they can be swept, which must involve property tree operations. It's not at all clear mucking with this in the GC, or virtualizing it so it can be delegated back to property-tree code, is a win on perf. It's a lose on modularity.

/be
Depends on: 558451
Currently marking JSScopeProperties sets a bit in a 16-byte structure. That results eventually in a cache line flush (16-bytes on most machines). So for N JSScopeProperties you write N * 32 bytes. If we pack mark bits, we would write N / 8 bytes.

Sunspider allocates 7695 JSScopeProperty structs, resulting in 123k bus traffic when marked. With a separate mark bitmap that would be less than 1k.
Then can you at least morph this bug's summary to be less over-specified? It's not obviously a non-fix to simply separate SPROP_MARK out and have a bitmap in js::PropertyTree. I'd buy that for a dollar!

/be
I am still not convinced that the current allocation scheme is ideal. We take a lock every time we allocate a scope property. Thats 8000ish lock operations on SS. I think we should look into all aspects of the current scheme, not just the bitmap.
Hello? Are you forgetting that we're moving the property tree into the thread-lcoal compartment for a given allocating cx?

Let's stay on target. First it was the mark bit. Now it's the lock. Focus!

/be
I meant that nicely :-P.

Really, the bitmap idea is good. Can this bug be about it? Set the summary if so.

/be
Summary: TM: allocate JSScopeProperties in the GC heap, and move out the mark bit → TM: split mark bits from JSScopeProperty and move into a mark bitmap
Assignee: general → brendan
OS: Mac OS X → All
Hardware: x86 → All
Summary: TM: split mark bits from JSScopeProperty and move into a mark bitmap → Allocate Shapes from the GC heap
Target Milestone: --- → mozilla2.0
Really, I sounded like a jerk in this bug -- sorry about that. There are several good reasons to make Shapes be gc-things, even if the shape heap as implemented today were to be single-threaded and per-compartment. Especially if some inlined allocator wins can be had.

If we get compartment GC done soon the shorter path would be to avoid reinventing it, or at least refactoring the shape heap to resemble it, and instead just use it. I'll try that this week.

/be
I will look into it after the bug 558861 will be landed.
Assignee: brendan → igor
Blocks: 609104
Removed dependency after discussing this with brendan. This is still likely a nice speedup. We allocate over 8000 shapes during sunspider. But we dont have to block 2.0 on this. Still wanted though.
No longer blocks: 609104
(In reply to comment #9)
> This is still likely a nice speedup. 

Unless we move the property tree into the compartment the shape would need to be allocated using the default compartment. That implies taking lock on each allocation. So a speedup would not be possible.
I'm not sure why the dependency on bug 	609104 was removed. We discussed moving the shape tree (rename proeprty tree freely please) into the compartment, along with rt->shapeGen, rt->protoHazardShape, etc. Seems we need all that anyway to avoid locking on shape tree mutation.

/be
Yes, the other bug will do all those things #11 lists. Its a pretty straight forward patch I need for 2.0. This bug I don't need. Just trying to reduce risk here. I still would love to see this bug here fixed too, if we have the time. But we don't have to block on it.
Assignee: igor → gal
Attached patch patch (obsolete) — Splinter Review
Moves shapes into the GC heap and the property tree into compartments.
x = this;
gczeal(1)
for (w in x) {}

This crashes in the shell with slot > capacity. Can't figure out why.
A couple comments:
- I removed the shape number optimization that assigns low numbers to empty shapes. I will replace this with compartment-local shape numbers which will provide low numbers for a wider set of objects once the prop cache is compartment-local.
- The patch removes around 8000 lock/unlock pairs in the shape allocation path.
Attached patch patch (obsolete) — Splinter Review
Here's an updated version. It passes jit-tests and jstests, even with gczeal. I can start a browser and browse around.

However, I'm still *strongly* opposed to getting this into Firefox 4. Here's why. There is a lot of code, particularly in jsscope.cpp, that assumes it runs atomically with respect to the GC (i.e., we don't GC in the middle). This patch breaks that assumption, since shape allocations are now GC allocations, which can lead to a GC.

Here are two examples of how this kind of bug can manifest itself:

1. When adding a new property to an object, we call allocSlot to create the slot. Then we create a new property and set obj->lastProp. With this patch, we can GC when creating the property. The GC will see the newly allocated slot, but not the new shape. Thus, it will think the object is needlessly big and call shrinkSlots. When we return from the GC, we assert or crash. This was the cause of the assertion in comment 14.

2. When converting to dictionary mode, we temporarily start by setting obj->lastProp to NULL. Then we insert the new dictionary shapes onto the list headed by obj->lastProp. With the patch, we can now GC in the middle of the loop (when allocating a dictionary shape). If the GC sees obj->lastProp == NULL, it assumes that obj is newborn and doesn't scan it. Obviously, this can lead to a crash.

I've tried to audit the code as best I can, but these sorts of errors don't jump out at you. They occur because of complex interactions between native code and the GC. I stared at the dictionary conversion code in #2 for at least an hour before I realized the problem. The only way to catch these bugs is with extensive testing, and we simply don't have time to do that in Firefox 4.
Attachment #496711 - Attachment is obsolete: true
If you aren't comfortable with this patch for 4, we need a spot fix that roots shapes. I am ok with a quick fix like that for 4.
(In reply to comment #17)
> If you aren't comfortable with this patch for 4, we need a spot fix that roots
> shapes. I am ok with a quick fix like that for 4.

As pointed out in person (and over iChat :-P), we do root shapes in js_NativeGet and js_NativeSet. Can anyone point to other places that don't root shapes but do hold them across call-outs that might GC?

/be
(In reply to comment #16)
> 1. When adding a new property to an object, we call allocSlot to create the
> slot. Then we create a new property and set obj->lastProp. With this patch, we
> can GC when creating the property. The GC will see the newly allocated slot,
> but not the new shape. Thus, it will think the object is needlessly big and
> call shrinkSlots. When we return from the GC, we assert or crash. This was the
> cause of the assertion in comment 14.

This is a good point.

> 2. When converting to dictionary mode, we temporarily start by setting
> obj->lastProp to NULL. Then we insert the new dictionary shapes onto the list
> headed by obj->lastProp. With the patch, we can now GC in the middle of the
> loop (when allocating a dictionary shape). If the GC sees obj->lastProp ==
> NULL, it assumes that obj is newborn and doesn't scan it. Obviously, this can
> lead to a crash.

Crash where? I"m not disagreeing, looking for an exact problem statement. The non-dictionary shape lineage that used to be held by obj->lastProp should be kept alive by the |shape| local (on stack) variable in Shape::newDictionaryList, via the conservative stack scanner.

/be
(In reply to comment #19)
> Crash where? I"m not disagreeing, looking for an exact problem statement. The
> non-dictionary shape lineage that used to be held by obj->lastProp should be
> kept alive by the |shape| local (on stack) variable in
> Shape::newDictionaryList, via the conservative stack scanner.

You're right, these shapes are kept alive through the stack scan. The problem is that the JSObject that's going into dictionary mode is not scanned. Its lastProp field is NULL, and the GC marking code treats objects with a NULL lastProp as newborn and doesn't scan them at all. So anything this object points to will not be scanned either (unless it's reachable some other way). That includes other its slots, its emptyShapes, and miscellaneous other things.

However, I thought of a better way to handle shape rooting in the short term. I'll try to post a patch tonight if I can.
Attached patch fixed patch (obsolete) — Splinter Review
This is an updated version of the patch. It basically stable now. It passes a Linux64-only tryserver run.

I'm mainly posting so that Gregor can make progress on his background sweeping patch. I'd like to get this patch in early in the release cycle (i.e., soon), since it's the sort of thing that needs lots of testing.

I'm going to try to break it up into pieces before posting it for review. Some of the changes are refactorings, so those can be committed first, separately. I'm worried about the rest of the patch though. It's not the sort of thing that is easy to back out or #ifdef off. Maybe I just need to think harder, though.
Attachment #512314 - Attachment is obsolete: true
Assignee: gal → wmccloskey
If you isolate the allocate and sweep parts, backing out would be patch -R with fuzz as needed. Or hand merging, but small enough scope that it seems ok to rely on this kind of back-out and not #ifdef or over-engineer for the worst case.

We need to plan on success here, with failure an option that won't kill us in merge pain.

/be
I think the patch is close to ready. I've broken it up into pieces to make it easier to review and to back out. This first piece just changes a bunch of GC functions to take const arguments. I did this because I want the shape type that we GC to be |const Shape *|. I considered using just |Shape *|, but that seemed to require a lot more casts.
Attachment #517013 - Attachment is obsolete: true
Attachment #518465 - Flags: review?(brendan)
This piece makes some changes that make it easier to GC shapes.

- Currently we do a changeProperty during sweeping in the watchpoint code. This caused a lot of trouble for me. Jason said it was okay not to do this in the sweeping case, so I took it out.

- I found some cases where we could do a GC before the map is initialized for a newborn object. This is really bad. To avoid the problem, I NULLed out the map in js_NewGCObject. This adds an extra store to a fast path, but I think it's better than having a lot of elaborate accounting for whether we have done the store yet or not (which is what I end up with otherwise).

- I think there was a pre-existing bug in AssertValidPropertyCacheHit. It only happens in debug builds. I fixed it here.

... and some other stuff that should be explained by comments.
Attachment #518474 - Flags: review?(brendan)
GC things can't have constructors, so this makes js::Shape use an init method instead.
Attachment #518475 - Flags: review?(brendan)
Comment on attachment 518465 [details] [diff] [review]
adds const to some GC type signatures

>  template <typename T>
>  inline T *
> -Arena<T>::getAlignedThing(void *thing)
> +Arena<T>::getAlignedThing(const void *thing)

Is it intentional that the return type is discarding the const qualifier?
While describing the final patch, I noticed a problem. I'll fix it and post soon, hopefully.
(In reply to comment #26)
> Comment on attachment 518465 [details] [diff] [review]
> adds const to some GC type signatures
> 
> Is it intentional that the return type is discarding the const qualifier?

Yes. It's a little ugly, but I only want the const on Shapes.
This is the main one. It adds a new size class for shapes, along with all the tracing stuff they need.

I'm not sure if I've handled the public JSAPI tracing stuff correctly. I just did a pretty straightforward copy-and-paste job here.

I added a new function, PreMark, that is called during marking. It's supposed to work like MarkChildren, except that it's called even in the RecursionTooDeep case. This is where the shape number gets regenerated. I needed something that happens exactly once per GC thing; MarkChildren can be called many times if we're doing delayed marking.

I also changed how shapes are marked. Previously, we traversed a shape's parent chain in the JSObject marking path. However, I found that in the case of a shape not attached to an object (like one that's only rooted by the stack) we then fail to walk up the parent links. So I moved this code to Shape itself, being careful to keep it iterative rather than recursive.

As I mentioned a while ago, the main risk in this patch is that it adds a new place to GC: during shape allocation. I've tested with GCZEAL pretty thoroughly, but please keep this in mind during the review.
Attachment #518546 - Flags: review?(brendan)
PreMark is a bad name IMO. Maybe Touch() ? And if you use a function template with typename T that is empty, and a specialization for Shape * that is not, you don't need 4 empty functions for this.
Comment on attachment 518465 [details] [diff] [review]
adds const to some GC type signatures

>+++ b/js/src/jsgcinlines.h
>@@ -210,17 +210,17 @@ Mark(JSTracer *trc, T *thing)
> 
>     JSRuntime *rt = trc->context->runtime;
>     /* Don't mark things outside a compartment if we are in a per-compartment GC */
>     if (rt->gcCurrentCompartment && thing->asCell()->compartment() != rt->gcCurrentCompartment)
>         goto out;
> 
>     if (!IS_GC_MARKING_TRACER(trc)) {
>         uint32 kind = GetGCThingTraceKind(thing);
>-        trc->callback(trc, thing, kind);
>+        trc->callback(trc, (void *)thing, kind);

Looks good, but could reinterpret_cast<void *> be used here or is there a problem with the template type parameter?

/be
Attachment #518465 - Flags: review?(brendan) → review+
Comment on attachment 518474 [details] [diff] [review]
miscellaneous fixes

> /*
..12345678901234567890123456789012345678901234567890123456789012345678901234567890
>  * NB: DropWatchPointAndUnlock releases cx->runtime->debuggerLock in all cases.
>+ * The sweeping parameter is true if the watchpoint and its object are about
>+ * to be finalized, in which case we don't need to changeProperty.

"to" on previous line fits the wrap-margin.

>+DropWatchPointAndUnlock(JSContext *cx, JSWatchPoint *wp, uintN flag, bool sweeping)

Good fix, wow. Silly to change a garbage object's shape.

>@@ -1171,17 +1169,17 @@ JS_ClearWatchPoint(JSContext *cx, JSObje
>     for (wp = (JSWatchPoint *)rt->watchPointList.next;
>          &wp->links != &rt->watchPointList;
>          wp = (JSWatchPoint *)wp->links.next) {
>         if (wp->object == obj && SHAPE_USERID(wp->shape) == id) {
>             if (handlerp)
>                 *handlerp = wp->handler;
>             if (closurep)
>                 *closurep = wp->closure;
>-            return DropWatchPointAndUnlock(cx, wp, JSWP_LIVE);
>+            return DropWatchPointAndUnlock(cx, wp, JSWP_LIVE, false);
>      

Trailing whitespace alert -- trim at will!

>+/*
>+ * The AssertValidPropertyCacheHit function can cause a GC, which will
>+ * invalidate the property cache. Therefore, it's important that we do
>+ * ASSERT_VALID_PROPERTY_CACHE_HIT *after* we have already finished using the
>+ * property cache entry in question.

D'oh. We ran into issues within AssertValidPropertyCacheHit and tried to tolerate nested GC there, but clearly did not consider callers carefully.

Another option would be to restore the entry if GC does nest. That seems a bit better in terms of coverage (the GNAME INC/DEC ops at least, from what I see a bit further below).

> Shape::newDictionaryList(JSContext *cx, Shape **listp)
> {
>     Shape *shape = *listp;
>     Shape *list = shape;
> 
>-    Shape **childp = listp;
>-    *childp = NULL;
>+    /*
..12345678901234567890123456789012345678901234567890123456789012345678901234567890
>+     * We temporarily create the dictionary shapes using a root located on the stack.
>+     * This way, the GC doesn't see any intermediate state until we switch listp
>+     * at the end.

Rewrap to wm=79 and less ragged right look ftw.

>+    *listp = root;
>+    root->listp = listp;
>+
>     list = *listp;
>     JS_ASSERT(list->inDictionary());
>     list->hashify(cx->runtime);
>     return list;

Nit: could leave list as the saved original lastProp and just use root in the unchanged lines above. Seems more pure (functionally), avoids two roles for "list" in this method.

r=me with AssertPropertyCacheValid fixing up the clobbered entry, if you can. Thanks,

/be
Attachment #518474 - Flags: review?(brendan) → review+
Comment on attachment 518475 [details] [diff] [review]
patch to remove Shape constructors

JSString has

    inline js::gc::Cell *asCell() {
        return reinterpret_cast<js::gc::Cell *>(this);
    }

    inline js::gc::FreeCell *asFreeCell() {
        return reinterpret_cast<js::gc::FreeCell *>(this);
    }

Could we not do that and avoid deriving Shape from gc::Cell, as JSString manages to avoid, and thereby keep the constructors?

/be
(In reply to comment #33)
> Could we not do that and avoid deriving Shape from gc::Cell, as JSString
> manages to avoid, and thereby keep the constructors?

Deriving from Cell isn't the problem. The problem is when we instantiate Arena<Shape>. The Arena class has a union that includes elements of type T, which is Shape in this case. And things that go in unions can't have constructors.

I'm not really sure how important this union is. Gregor, is there a way we could get rid of the union? Are there other unions that might cause problems?
For reference, bug 613457 (in review) makes JSString derive js::gc::Cell, lets us remove asCell() and the calls everywhere.
Constructors without virtual are winning and we should try to use them. This may mean some asCell "cast methods" -- lesser evil compared to banning ctors, IMHO.

The union sounds avoidable but I'll wait for Gregor to weigh in.

/be
Blocks: 642209
The union comes from the fact that sometimes we want to treat an Arena as "untyped". This is used in places where we don't care about the type or we don't know the type. The delayed marking stack for example is a linked list of Arenas with different types. There we need some kind of "base" type.

I remember implementing this solution with Luke because I couldn't get rid of some GCC warnings. After we introduced the union I could also remove many ugly casts in the GC code.

The union is avoidable but I don't think there is a clean way to silence a bunch of GCC warnings and you have to add casts in many different places.
I played around with the unions today and managed to remove them. I've only tested on GCC so far, but I see no reason why MSVC shouldn't accept this code.

There are a few additional casts, but I think that the benefit of having constructors for GC things far outweighs these casts.

This patch goes in the same place in the patch series as the one to remove constructors, which it replaces.
Attachment #518475 - Attachment is obsolete: true
Attachment #520029 - Flags: review?(brendan)
Attachment #518475 - Flags: review?(brendan)
(In reply to comment #38)
> Created attachment 520029 [details] [diff] [review]
> patch to remove unions for GC things
> 
> I played around with the unions today and managed to remove them. I've only
> tested on GCC so far, but I see no reason why MSVC shouldn't accept this code.
> 
> There are a few additional casts, but I think that the benefit of having
> constructors for GC things far outweighs these casts.
> 
> This patch goes in the same place in the patch series as the one to remove
> constructors, which it replaces.

My compiler doesn't like it.
I am using gcc-4.2.1 and I get a ton of warnings during opt builds.
Attached patch fixed GC unions patch (obsolete) — Splinter Review
How does this one work for you, Gregor?

Admittedly, it's pretty ugly. The change to cellIndex is pretty safe, I think, since you're always allowed to cast to char*.

The casts in Arena<T>::init violate the letter of the C spec, since they do type punning without unions. I can't imagine a case where we'd get incorrect code, though.

Luke, perhaps you could offer some guidance?
Attachment #520029 - Attachment is obsolete: true
Attachment #520050 - Flags: review?(brendan)
Attachment #520029 - Flags: review?(brendan)
(In reply to comment #40)
> Created attachment 520050 [details] [diff] [review]
> fixed GC unions patch
> 
> How does this one work for you, Gregor?
> 
> Admittedly, it's pretty ugly. The change to cellIndex is pretty safe, I think,
> since you're always allowed to cast to char*.
> 
> The casts in Arena<T>::init violate the letter of the C spec, since they do
> type punning without unions. I can't imagine a case where we'd get incorrect
> code, though.
> 
> Luke, perhaps you could offer some guidance?

Yeah this works. That's what I meant with "no clean solution" yesterday.
I thought a bit more about the union-elimination patch. I'm more in favor of it. The fact is, we do type-punning all over the place, in the GC and elsewhere. It's just that GCC doesn't warn about it. The asFreeCell() function is one example. Do we have any belief that GCC is more likely to warn in places where code will be compiled incorrectly than it places where it isn't? If not, then I think the patch is fine.
Comment on attachment 520050 [details] [diff] [review]
fixed GC unions patch

I'm an old-school, die-hard, C/Unix nerd. Doing reviews out of order, this looks fine to me but I'm bouncing to Luke.

/be
Attachment #520050 - Flags: review?(brendan) → review?(luke)
Comment on attachment 518546 [details] [diff] [review]
patch to move shapes to GC heap

Beautiful. Waiting a long time for this one. Thanks for persevering under my "ctors ftw" nagging. Summary nits:

MarkIfGCThingWord and markDelayedChildren both need to half-indent their switch case label lines (pre-existing, check and fix any more like this).

TypedMarker nits -- blank line before commented line, overbraced if-else
toDictionaryMode blank line before commented line.

r=me with these picked.

/be
Attachment #518546 - Flags: review?(brendan) → review+
Comment on attachment 520050 [details] [diff] [review]
fixed GC unions patch

Nice job with Things.

>+        reinterpret_cast<FreeCell *>(thing)->link = reinterpret_cast<FreeCell *>(thing + 1);
>         ++thing;
>     }
>-    last->cell.link = NULL;
>+    reinterpret_cast<FreeCell *>(last)->link = NULL;

> Cell::cellIndex() const
> {
>-    return reinterpret_cast<const FreeCell *>(this) - reinterpret_cast<FreeCell *>(&arena()->t);
>+    return (reinterpret_cast<const char *>(this) - reinterpret_cast<char *>(&arena()->t)) / sizeof(FreeCell);

s/reinterpret_cast<FreeCell *>(x)/x->asFreeCell()/ ?

>     static const size_t ThingsPerArena = (ArenaSize - sizeof(AlignedArenaHeader)) / sizeof(T);
>+    static const size_t Filler1Size =
>+        ((sizeof(ArenaHeader) + sizeof(T) - 1) / sizeof(T)) * sizeof(T) - sizeof(ArenaHeader);
>+    static const size_t Filler2Size =
>+        ArenaSize - sizeof(AlignedArenaHeader) - sizeof(T) * ThingsPerArena;
>+    Things<T, ThingsPerArena, Filler1Size, Filler2Size> t;

I think the computation of Filler1Size could be a little more obvious in its purpose by using a piecewise function:

  static const size_t Filler1Size =
    tl::If< sizeof(ArenaHeader) % sizeof(T) == 0,
            0,
            sizeof(T) - sizeof(ArenaHeader) % sizeof(T) >::result;

Also, it seems you could define ThingsPerArena/Filler2Size so that AlignedArenaHeader could be deleted:

  static const size_t SpaceAfterHeader = ArenaSize - (sizeof(ArenaHeader) + Filler1Size);
  static const size_t ThingsPerArena = SpaceAfterHeader / sizeof(T);
  static const size_t Filler2Size = SpaceAfterHeader % sizeof(T);

Lastly, it would be nice to have this immediately after to give a warm fuzzy feeling.

  static void staticAsserts() {
    JS_STATIC_ASSERT(offsetof(Arena<T>, t.things) % sizeof(T) == 0);
    JS_STATIC_ASSERT(sizeof(Arena<T>) == ArenaSize);
  }
Attachment #520050 - Flags: review?(luke)
(In reply to comment #45)

I talked about this in person with Luke. We decided to get rid of the union and deal with any strict aliasing problems as they arise. I'll post an updated patch that addresses the template comments later.
Attachment #520050 - Attachment is obsolete: true
Oops, messed up on the last one. Here it is.
Attachment #521023 - Attachment is obsolete: true
Attachment #521030 - Flags: review?(luke)
Attachment #521023 - Flags: review?(luke)
Comment on attachment 521030 [details] [diff] [review]
remove GC unions, v4

Sweet comment
Attachment #521030 - Flags: review?(luke) → review+
http://hg.mozilla.org/tracemonkey/rev/9335aa129fdc

I did a quick fix for the orange, and filed bug 644349 to find a more permanent fix.
Blocks: 595975
Depends on: 651445
No longer blocks: 595975
Blocks: 595975
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: