Closed Bug 843907 Opened 9 years ago Closed 8 years ago

Move to manual barriering for MapObject and SetObject's keys


(Core :: JavaScript Engine, defect)

Not set





(Reporter: terrence, Assigned: terrence)



(Whiteboard: [js:t])


(2 files, 1 obsolete file)

Automatically adding keys from the OrderedHashTable to the store buffer does not work because the table uses a non-null value to indicate "empty". Since RelocatableValue expects NULL to be used for this purpose, minor GCs attempt to mark the tombstone as if it were a value. This obviously fails.

RelocatableValue is also extremely slow and moving to manual barriering will make MapObject and SetObject faster with generational GC.
I split this part out since EncapsulatedValue was non-instantiable until now and it required some additions to gc/Barrier.h.
Attachment #716880 - Flags: review?(wmccloskey)
I tried several different approaches here and, unfortunately, this was by far the best of them. This patch addresses several problems of competing severity:

(1) We have to be able to deal with a different reference to an object than the table's key being marked through first and thus invaliding the table's reference. If this happens then it is no longer possible to get the object's zone, which means that calling the pre-barrier will fail. This effectively means that it is dangerous to assign to or destruct a HashableValue during a minor or compacting collection.

I was able to largely get around this by passing the HashableValues around as pointers, keeping them off the stack. The only actually-dangerous assignment is the one that updates the key. I opted to use a reinterpret_cast here. The only oddness is that OrderedHashTable does't know about HashableValue or Value, so we have to templatize a bit.

(2) Our existing rekeying logic was made for the compacting GC and thus visits the entire table. If I do the simplest thing and call MapObject::mark for each entry in the store buffer, this goes O(n^2) and several of the MapObject tests time out. Thus we have to pull in gc::BufferableRef. These are bulky, but I don't see a way around it in this case.

(3) If we do the second-simplest solution - remove the old key, move, then insert the new key, we occasionally try to resize the table, which fails horribly when we've already moved some elements. Since we'd either need a method for add-but-don't-resize or a new method to move a single key, I opted for the simpler "move a single key approach".

(4) The Key type is const in OrderedHashTable because we normally want to go through Ops::setKey to update the key. Rather than cluttering up setKey or adding a new method to every Ops I used tl::StripConst.

(5) We have no context during GC or verification, so calling setValue is impossible. In this case we know the Value is safe to put in the table (it's already in the table), so this is merely a matter of casting or poking holes in the API. I opted to use a nasty reinterpret_cast, rather than adding an unsafeSetValue to HashableValue to avoid the possibility of accidentally introducing misuse of the API later.
Attachment #716897 - Flags: review?(jorendorff)
Attachment #716880 - Flags: review?(wmccloskey) → review+
Whiteboard: [js:t] [leave-open]
Comment on attachment 716880 [details] [diff] [review]
1 of 2: v0 - Change the type to EncapsulatedValue.
Attachment #716880 - Flags: checkin+
Comment on attachment 716897 [details] [diff] [review]
2 of 2: v0 - Implement the manual barriering and key movement.

Review of attachment 716897 [details] [diff] [review]:

::: js/src/builtin/MapObject.cpp
@@ +497,5 @@
> +     * Ops::hash on the current key must return the same hash code as
> +     * when the entry was added to the table.
> +     */
> +    template <typename AssignmentType>
> +    void rekeyOneEntry(NonConstKey *current, NonConstKey *newKey) {

Now with billm's hack this can be a lot cleaner, I think...

> void rekeyOneEntry(const Key &current, const Key &newKey)

@@ +505,5 @@
> +        Data *entry = lookup(*current, prepareHash(*current));
> +        if (!entry)
> +            return;
> +
> +        HashNumber oldHash = prepareHash(*current) >> hashShift;

You could avoid calling prepareHash(current) twice, I think (?)

@@ +513,5 @@
> +        // type has an |operator=| that refers to |this|, then performing the
> +        // update with the default types would be dangerous. This allows the
> +        // caller to override the type during the key assignment.
> +        *reinterpret_cast<AssignmentType *>(&entry->element) =
> +            *reinterpret_cast<AssignmentType *>(newKey);

Nice to hear this will go away with billm's hack.

Should be no worse than a const_cast.

@@ +1123,5 @@
> +class OrderedHashMapRef : public gc::BufferableRef
> +{
> +    ValueMap *map;
> +    Value key;

We talked about it and this could be a HashableValue, which will eliminate a few more reinterpret_casts.

@@ +1128,5 @@
> +
> +  public:
> +    OrderedHashMapRef(ValueMap *m, const Value &k) : map(m), key(k) {}
> +
> +    bool match(void *location) {


::: js/src/builtin/MapObject.h
@@ +41,5 @@
>      bool setValue(JSContext *cx, const Value &v);
>      HashNumber hash() const;
>      bool equals(const HashableValue &other) const;
> +    bool operator==(const HashableValue &other) const { return equals(other); }

Feel free to just rename "equals" to "operator==" if that works.
Attachment #716897 - Flags: review?(jorendorff) → review+
Attached patch 2 of 2: v1Splinter Review
Carrying the r+. Posting this for posterity, since there were quite a few changes.
Attachment #716897 - Attachment is obsolete: true
Attachment #728484 - Flags: review+
Whiteboard: [js:t] [leave-open] → [js:t]
Attachment #728484 - Flags: checkin+
Closed: 8 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.