Native Mark-Sweep: block sweeping anomaly

[chiarameiohas]

Not all blocks seem to be swept in Mark-Sweep (at the end of the GC of eager-sweeping, or in between collections in lazy-sweeping).

allocated object points to an unallocated object

I am running my own GC code where we mark all referents of an allocated object (ex. object A is allocated and A->B and A->C, then B&C are the referents and will be marked).
I added an assertion that checks if we try to mark an unallocated object, and this assertion fails. This means that an allocated object points to an unallocated object (say A->B) ... this can happen only if the unallocated object (B) was freed in the previous collection and (A) was not freed (even though A was not marked). Although I didn't provide a detailed explanation of our GC algorithm, an allocated object should never point to an unallocated object. This assertion does not fail in Mark-Sweep, because any live object is also allocated, so we mark only allocated objects.

I also copied the mark bitmap to the alloc bitmap at the end of the collection, only then the assertion does not fail...which again makes me think that some blocks are not freed.
NOTE: the alloc bit of dead objects is zeroed while sweeping the block see

mmtk-core/src/policy/marksweepspace/native_ms/block.rs

Line 278 in cf91f0a

fn simple_sweep<VM: VMBinding>(&self) {

).

lazy sweeping sweeps more blocks than eager sweeping

Lazy-Sweeping sweeps more blocks in between collections than Eager-Sweeing at the end of a collection.
Additionally MS with eager-sweeping performs more collections than MS with lazy sweeping (I ran this multiple times to make sure it wasn't a one time wonder).

In a clean MMTK-core image (without my code) I printed how many blocks were swept: how many blocks called sweep in block.rs

mmtk-core/src/policy/marksweepspace/native_ms/block.rs

Line 245 in cf91f0a

pub fn sweep<VM: VMBinding>(&self) {

The logs below are from the dacapo biojava benchmark, running Mark-Sweep with a 1GB heap. I activated eager-sweeping by compiling with the eager_sweeping feature.

biojava_eager_1G.log
biojava_lazy_1G.log

Mark-Sweep with eager sweeping:

===== DaCapo evaluation-git-29a657f biojava starting =====
swept blocks 4658
swept blocks 1080
swept blocks 6241
swept blocks 2133
swept blocks 6258
swept blocks 2146
swept blocks 6264
swept blocks 2159
swept blocks 6269
swept blocks 2160
swept blocks 6289
swept blocks 2165
swept blocks 6281
swept blocks 2178
swept blocks 6291
swept blocks 2177
swept blocks 6309
swept blocks 2184
swept blocks 6305
============================ MMTk Statistics Totals ============================
GC	time.other	time.stw	total-work.time.max	total-work.count	total-work.time.total	total-work.time.min	
19	43128.16	1362.22	-inf	0	0.000	inf	

Mark-Sweep with lazy sweeping:

===== DaCapo evaluation-git-29a657f biojava starting =====
swept blocks 4430
swept blocks 7045
swept blocks 7818
swept blocks 7842
swept blocks 7838
swept blocks 7862
swept blocks 7854
swept blocks 7866
swept blocks 7860
swept blocks 7886
swept blocks 7877
swept blocks 7894
swept blocks 7892
swept blocks 7907
swept blocks 7895
============================ MMTk Statistics Totals ============================
GC	time.other	time.stw	total-work.count	total-work.time.total	total-work.time.max	total-work.time.min	
15	43686.47	1062.40	0	0.000	-inf	inf	

I am running mmtk-core with the Open-JDK binding.
MMTK-core version: 106fc71
MMTK-openjdk version: mmtk/mmtk-openjdk@57cdce3
I am using the dacapo 29a657f version.

[qinsoon]

Thanks for the issue. I don't quite understand the first problem you mentioned about allocated/unallocated objects. I can reproduce the second problem, and I am looking into it.

[qinsoon]

One issue is that there are race conditions in the Release phase for mark sweep eager sweeping. MarkSweepSpace::release will generate SweepChunk work, which runs in parallel with Mutator::release, and they both update the block lists.

mmtk-core/src/policy/marksweepspace/native_ms/global.rs

Line 337 in 440b57c

impl<VM: VMBinding> GCWork<VM> for SweepChunk<VM> {

mmtk-core/src/policy/marksweepspace/native_ms/global.rs

Line 263 in 440b57c

pub fn release(&mut self) {

I embed a Rust Vec<Block> in each BlockList, and use that to constantly check if the BlockList is maintained correctly. With eager sweeping, the check failed. If I get Mutator::release to run after SweepChunk, or use 1 GC thread, the check passed.

However, this does not fix the difference in swept blocks between eager sweeping and lazy sweeping.

[chiarameiohas]

@qinsoon

First Problem:

After running one Mark-Sweep collection, I noticed (in the following collection) that an allocated object points to an unallocated object (say A-> B, where A is allocated and B is not allocated).

The only explanation that came to mind is that the block containing B was swept, and the block containing A was not swept. This is because, AFAIK, the alloc bit is zeroed for collected objects here:

mmtk-core/src/policy/marksweepspace/native_ms/block.rs

Line 293 in cf91f0a

crate::util::metadata::vo_bit::unset_vo_bit_nocheck::<VM>(potential_object);

This allocated to unallocated pointer occurs in both lazy-sweeping and eager-sweeping.

I hope the first problem is now clearer.

[qinsoon]

@chiarameiohas The explanation makes it clearer. But I am still confused about allocated/unallocated objects. When you say allocated objects, do you mean their valid object bit is set? And by unallocated objects, do you mean their alloc bit is not set? If that's the case, I could add an assertion in trace_object in MarkSweepSpace to check the valid object bit for every marked object, and I should see an assertion failure somewhere.

[chiarameiohas]

@qinsoon Yes, exactly. I have an older MMTK-core version so it is still called alloc-bit in my code.
The problem is that a valid object points to an invalid object.

The assertion in trace_object of MarkSweep will not fail because all live objects are valid. This valid to-invalid pointer is seen only between dead objects.

I caught this in my GC because we mark all children of valid objects, which causes us to mark as live some garbage. The assertion I mentioned above was in my GC's trace_object function.

If it would be useful, I can share my code, to explain better where the assertion fails.

[qinsoon]

I got code from @chiarameiohas, and figured out the problems with our eager sweeping (there are multiple related problems). Some objects with vo bit 0 are reachable from objects with vo bit 1 (the objects with vo bit 1 is discovered by linear scan using vo bit). The actual cause is that the objects with vo bit 1 are actually dead objects, but the GC did not sweep the block, thus the objects' vo bit is incorrect.

There are multiple issues that caused this:

1. We do not sweep global block lists (abandoned blocks). Dead mutators/allocators will flush their local blocks before getting destroyed. Also all the mutators flush their local blocks at the end of a GC (so those blocks can be used by other threads). For eager sweeping, we expect the mutator to sweep its local blocks, then flush them to the global lists. But we still need to sweep the abandoned blocks from dead mutators.
   

   mmtk-core/src/policy/marksweepspace/native_ms/global.rs

   Lines 52 to 55 in 440b57c

   	/// Abandoned blocks. If a mutator dies, all its blocks go to this abandoned block
   	/// lists. In a GC, we also 'flush' all the local blocks to this global pool so they
   	/// can be used by allocators from other threads.
   	pub abandoned: Mutex<AbandonedBlockLists>,

2. Some erroneous code (possibly caused by an incorrect merging) flushes the local blocks earlier then it should:
   

   mmtk-core/src/util/alloc/free_list_allocator.rs

   Lines 492 to 499 in 440b57c

   	if Self::ABANDON_BLOCKS_IN_RESET {
   	self.abandon_blocks();
   	}
   	}
   	if Self::ABANDON_BLOCKS_IN_RESET {
   	self.abandon_blocks();
   	}

   
   This causes most of blocks to be flushed to the global list before they are swept by the allocator. As we do not sweep global block lists, those blocks are not swept at all in the GC. This should contribute most of the problems in this issue.

3. Race condition in Release: See the post above (Native Mark-Sweep: block sweeping anomaly #824 (comment))

I submitted #830 and it should fix 1 and 2. 3 is related with #717, and I am not sure what would be a proper fix.

[qinsoon]

Those issues also could explain why we sweep fewer blocks in eager sweeping than lazy sweeping. Many blocks are flushed to the global lists without sweeping, and we do not sweep global lists.

[k-sareen]

Can the abandoned.move_consumed_to_unswept(); call be moved into EndOfGc? It would fix the race condition. Unless it needs to happen before the SweepChunk work packets are executed?

[qinsoon]

Can the abandoned.move_consumed_to_unswept(); call be moved into EndOfGc? It would fix the race condition. Unless it needs to happen before the SweepChunk work packets are executed?

Not sure if that will fix the race. I found the block list may not be maintained correctly. SweepChunk and ReleaseMutator both modify block lists.

[k-sareen]

Right but ReleaseMutator bottoms out to the MarkSweepSpace::release function. The only thing in that function that is modifying the block lists other than the SweepChunk work is the abandoned.move_consumed_to_unswept(). Unless I've missed a place which modifies the block list tracing from ReleaseMutator.