492024 - ZCT collection and pruning policy

Status: VERIFIED FIXED

(Tamarin Graveyard :: Garbage Collection (mmGC), defect, P1)

Description

[Lars T Hansen]

It's possible that ZCT reaping can impose too-large pauses if the ZCT grows large; we should be mindful of this.

If the ZCT population shrinks after the ZCT structure has grown, we should consider shrining the ZCT structure.

The ZCT should not be a single block (tends to grow the heap as large objects are allocated; imposes copying cost) but should be allocated in smaller pieces.

Comment 1

[Lars T Hansen]

Also would be good to confirm that trying to add something to the ZCT cannot cause the system to fail.

Comment 2

[Lars T Hansen]

Attachment: zct1.as

Stress test for the ZCT: the program forces the ZCT to expand.

Comment 3

[Lars T Hansen]

Attachment: Make CleanEntireStack a VMPI_ function

Preliminary cleanup - CleanEntireStack() is platform dependent and can be moved out to the platform layer.

Comment 4

[Tommy Reilly]

Can we get CleanStack too?   I did it this way in the player:


	void GC::CleanStack(bool force)
	{
		if(!force && (stackCleaned || rememberedStackTop == 0))
			return;
		
		stackCleaned = true;
		
		register void *stackP = 0;
		size_t size;
		
		MMGC_GET_STACK_EXTENTS(this, stackP, size);
		
		if( ((char*) stackP > (char*)rememberedStackTop) && ((char *)stackEnter > (char*)stackP)) {
			size_t amount = (char*) stackP - (char*)rememberedStackTop;
			VMPI_cleanStack(amount);
		}
	}


Where VMPI_cleanStack is:


void VMPI_cleanStack(size_t amt)
{
	void *space = alloca(amt);
	if(space)
	{
		VMPI_memset(space, 0, amt);
	}
}

Comment 5

[Lars T Hansen]

(In reply to comment #4)
> Can we get CleanStack too?

We should (though I would prefer for it to be a separate patch).  I'll look at what you have here and maybe make a patch out of it for you to approve ;-)

Comment 6

[Lars T Hansen]

Attachment: zct block allocation, pruning, and out-of-memory handling

(Preliminary, as it includes the CleanEntireStack fix too.  But basically ready, following a little more testing & review.)

Contains the following:

 - The ZCT is now a two level data structure: a small linear block table (at
   most 64KB in size to accomodate the full 16M entries on a 32-bit system)
   and individual heap blocks for ZCT storage.  The ZCT logic is unchanged,
   but in-line getters, setters, and similar functions replace the direct
   table access in the old table.  Performance-wise we should be OK.
 - Failure to grow the ZCT no longer crashes the system, but leaves it in
   a state where entries just aren't added - this is always safe.
 - Following GC, a call to zct.Prune() will discard blocks no longer needed.
 - Growing and shrinking the ZCT should be very fast, only the block table
   is copied during block table growth and this is a very rare occurence.

I don't think I'll be doing anything about ZCT-reap pause times now, that's more of a secondary concern and related to bug #486504.

Comment 7

[Lars T Hansen]

Comment on attachment 380112 [details] [diff] [review]
Make CleanEntireStack a VMPI_ function

Will nuke the whole function and its use after agreement with Tommy.

Comment 8

[Lars T Hansen]

Attachment: zct1.as, but nastier

Triggers gc repeatedly and flushed out a couple of bugs.  When run with ZCT_TESTING set and a small zct block allowance, causes everything to slow to a crawl.

Comment 9

[Lars T Hansen]

Attachment: Candidate patch

Comment 10

[Lars T Hansen]

Attachment: Candidate patch v2

Comment 11

[Lars T Hansen]

Attachment: zct block allocation, pruning, and out-of-memory handling

Implements the following desirables:

* zct allocated incrementally, in 1-page blocks, not as a single object
* zct is shrunk following gc, if appropriate
* failure to extend zct is handled properly

The core zct logic is unchanged from the old table; the changes have been implemented by simple in-line abstractions (Get, Put, etc).

Comment 12

[Rishit Shah]

Comment on attachment 381045 [details] [diff] [review]
zct block allocation, pruning, and out-of-memory handling

Looks good.  I esp. liked the idea of storing chained freelist indices in place.

Few minor issues

#1 zctIndex & nextPinnedIndex are not initialized in ctor.  They are in Reap() before being used but initializing them in the ctor would not hurt.

#2 For calculating the index/block number a variety of data types are used in CAPACITY() macro - uintptr_t, RCObject* & void*.

Using a consistent data type might be clearer.  I would think it should either by uintptr_t or RCObject*.

Comment 13

[Rishit Shah]

I am assuming that CleanStack changes are not a part of this patch.

Comment 14

[Lars T Hansen]

(In reply to comment #12)
> 
> #1 zctIndex & nextPinnedIndex are not initialized in ctor.  They are in Reap()
> before being used but initializing them in the ctor would not hurt.

OK.

> #2 For calculating the index/block number a variety of data types are used in
> CAPACITY() macro - uintptr_t, RCObject* & void*.

Will look into this, but the point of that macro is that it can take into account the size of the type being stored.  Obviously, the type being used for a particular kind of block should not vary.

> I am assuming that CleanStack changes are not a part of this patch.

They are not.

Comment 15

[Lars T Hansen]

redux changeset:   2017:c088524ade4e