draft proposal for ref counting in D

[Michel Fortin]

On 2013-10-15 18:32:01 +0000, "deadalnix" <deadalnix at gmail.com> said:

> No, that is the beauty of it :D
> 
> Consider you have pointer from Tl -> shared -> immutable and TL -> immutable.
> 
> I'm not covering TL collection here (It seem to be obvious that it 
> doesn't require to stop the world). So the starting point is that we 
> have the roots in all TL heaps/stacks, and we want to collect 
> shared/immutable without blocking the worlds.
> 
> TL heap may get new pointers to the shared heap, but they can only come 
> from the shared heap itself or new allocations. At this point, you 
> consider every new allocations as live.
> 
> Reading a pointer from the shared heap and copy it to the TL heap isn't 
> problematic in itself, but then we have a problem if this pointer is 
> now updated in the shared heap, as the GC may never scan this pointer.
> 
> This is why you need to track pointer writes to the shared heap. The 
> write value itself isn't important : it come from either new alloc that 
> are live, or from somewhere else in the shared heap (so it will be 
> scanned as we track writes).

But you still have to scan the thread-local heaps and stacks to find 
pointers to shared memory. If you don't stop those threads, how do you 
know one of these threads isn't moving a pointer value during the scan 
from one place the GC still has to scan to another that the GC has just 
scanned, making it so the GC never sees the pointer?

For instance:

	class A {
		// string is immutable and points to shared heap
		immutable(char)[] s;
	}

	A global;

	void func()
	{
		// GC scans the stack of this thread in the background
		// no reference to our string on the stack

		// moving string pointer to the stack
		// while the GC is running
		auto tmp = global.s;
		global.s = null;

		// GC scans the heap of this thread in the background
		// no reference to our string on the heap
		// (missed reference to our string now on the stack)
	}

The thread can move the pointer around while the GC is looking away and 
you'll end up with a pointer to a freed string. So you have to use COW 
for the thread's stack, or get notified of a pointer assignment somehow 
(or of a pointer move), or stop the thread while you're scanning its 
heap.

-- 
Michel Fortin
michel.fortin at michelf.ca
http://michelf.ca