Provide hashmap like structure supporting moving JSObject* keys

[Yves]

Ticket depends on

The ticket definitely depends on the SpiderMonkey upgrade to v24. After checking the example code more closely I would say we probably even have to wait for newer versions. Some API functions have already been adjusted (​here for example) and this code relies heavily on some of them.

#1886

Description

BinarySerializer.cpp is one example where we store JSObject pointers in a key and associate a "backref tag" with this object. The serializer uses this to identify already serialized objects and serializes the tag in the output stream instead of serializing the whole object again. This is required to support non-tree structures and circular references.

The problem with a moving GC is that the object a JSObject pointer points to can move in memory. This invalidates the key in the map and causes wrong behaviour and crashes. Here's a solution for this problem (the ObjectIDCache class): ​JavaScriptShared.h
​JavaScriptShared.cpp

Requirements (both are implemented for the ObjectIDCache class)

1. Tracing implementation to protect the objects from the garbage collection (really? In the serialization case it's probably guaranteed that all data to serialize is already traced/rooted, but it could be uses for other cases too)
2. Implementation of post barriers. Post barriers update the key when the object is moved from the nursery to the tenured heap (read the documentation linked in the meta-ticket to learn more bout these terms).

Difficulties

Deferred finalization

This class uses deferred finalization (implemented in ​bug 934442).

My understanding of the problem is as follows:

1. Allocate a GC thing on the heap
2. Record this pointer in the store buffer with a post barrier (because it points into the nursery)
3. Deallocate the pointer on the heap before the next minor GC (the pointer itself, not the value it points to)
4. The GC thing the heap pointer pointed to gets moved. SpiderMonkey tries to update the pointer which has become invalid in the meantime --> Crash

So deferred finalization defers the deallocation of the heap pointer from the ObjectIDCache destructor to the end of the next minor GC. The ticket proposes some alternative solutions for the problem (if this approach doesn't work in our case).

Some useful information

The tracing is implemented ​here. The comment in jsapi.h about JS_CallHeapObjectTracer says that it may move the GC thing and return an updated pointer. I haven't quite figured out yet why the code can assert that this does not happen there. I assume it relies on an internal constraint there related to how the post barrier...

The post barrier is implemented ​here. It updates the key if it was moved.

The post barrier is registered for each key ​here.

[Yves]

I have a working version for SpiderMonkey 31 here: ​https://github.com/Yves-G/0ad/commit/38bb0fe1a791a10f3dd744062dffaf17d912a567

It doesn't make sense to backport this to v24, so I'll commit it as part of the v31 upgrade.

[Yves]

In 16214:

SpiderMonkey 31 upgrade

This upgrade also introduces exact stack rooting (see to the wiki: JSRootingGuide) and fixes problems with moving GC. This allows us to enable generational garbage collection (GGC).
Measurements a few months ago have shown a performance improvement of a non-visual replay of around 13.5%. This probably varies quite a bit, but it should be somewhere between 5-20%. Memory usage has also been improved. Check the forum thread for details.

Thanks to everyone from the team who helped with this directly or indirectly (review, finding and fixing issues, the required C++11 upgrade, the new autobuilder etc.)! Also thanks to the SpiderMonkey developers who helped on the #jsapi channel or elsewhere!

Fixes #2462, #2415, #2428, #2684, #1374
Refs #2973, #2669