DConf 2013 Day 1 Talk 6: Concurrent Garbage Collection for D by Leandro Lucarella

[Diggory]

On Tuesday, 21 May 2013 at 20:08:16 UTC, Leandro Lucarella wrote:
> I'm interested in what you're describing, but I don't know how 
> can you
> achieve this without fork()ing (or clone()ing in Linux). What 
> does
> "remap shared memory using COW" in a context where fork() 
> doesn't
> happen? Why do you even need shared memory if fork() doesn't 
> happen? If
> "remap shared memory using COW" means get a different address 
> for the
> same block of memory until a write happens in that block, then 
> you can't
> scan the roots anymore.
>
> I'm *very* interested in your suggestion.

After doing some further investigation I think I've found a 
fairly awesome way of doing garbage collection on windows, 
hopefully linux has a similar mechanism. It doesn't require 
memory mapped files or anything special, it can be done 
retroactively, and it allows a kind of reverse copy on write 
which is what's actually needed.

When the GC is run:
- Use VirtualProtect to mark all mutable memory pages as read-only
- Add a vectored exception handler to handle the access violation 
exception
- Resume the GC thread

In the exception handler:
- Copy the page being modified to a new page
- Mark the original page as writable again
- Tell the GC to use the new page instead
- Continue

The main problem I see is the need to synchronise between the 
exception handler and the GC, when it would be nice if the 
exception handler was as light-weight as possible. However this 
can be largely solved by doing finer grained synchronisation/some 
clever stuff. For example, the handler can add the new mapping 
first, then do the page copy, and only then wait for the GC to 
acknowledge the new mapping, so the GC has the whole time that 
the copying is taking place to see the change. The GC would also 
of course have to wait for the copying to complete before 
continuing but pausing the GC for a short time isn't really an 
issue at all.