CopyingCollector needs to be re-thought.

[aarontabor]

The CopyingCollector (which is mis-leadingly name) actually performs a mark-sweep-compact collection. The compaction phase of this policy contains a design flaw. The phase works as follows:

• free entire heap
• traverse live object tree (starting at roots)
• allocate each live object

This phase is flawed for several reasons:

• object traversal is not necessarily in heap-order
  • by reallocating objects, we could possibly overwrite a live-object that has yet to be visited, corrupting it.
  • in order for this compaction phase to work, objects would need to be traversed in the order that they appear in the heap; this guarantees that live objects will not be corrupted.
• RealAllocator performs next fit allocation; it caches the last successfully allocated address, and starts subsequent free space searches from there. This adds a further twist into the compaction phase because we are not guaranteed to be starting from the beginning of the heap.
  • we would either need to reset this cached next-fit address, or make our compaction algorithm smart enough to start traversal from that address instead of the beginning of the heap.

[aarontabor]

The MarkSweepCollector needs to be rethought for the same reasons.

[aarontabor]

This problem dates back (at least) as far as the point when we transitioned to Tracefile 3.0 format. f9d2771

[aarontabor]

On the branch aarontabor-heaporder, I've pushed a new method: ObjectContainer::getLiveObjectsInHeapOrder(). This method will be needed to fix the compaction phases of collections.

[aarontabor]

I performed a series of refactors to the Allocator and RealAllocator classes in order to better understand what is going wrong with these collection policies. The refactors have been pushed to the develop branch.

[aarontabor]

There is a tentative fix for the mark sweep collector on aarontabor-markSweepFix.

When I perform a non-compacting mark-sweep (by commenting out the compact() call), if the heap size is not sufficient, the simulation enters an infinite loop. This is because the memory manager is attempting to shift() until a promotion occurs. To make the simulator report an "Out of Memory" error instead of entering this infinite loop, I had to set SHIFTING to 0 in defines.hpp.

[aarontabor]

I took a closer look at the CopyingCollector as well. Please see issue #12