2

Say you have a virtual machine with the following instruction set.

0   ACC <= [S]      Copy address S from memory to ACC
1   ACC => [S]      Copy the value of the ACC to the memory address S.
2   ACC + [S]       Add the value at memory address S to the ACC value.
3   ACC - [S]       Subtract the value at address S from ACC.
4   PC <= S         Set the program counter to line address S (not the value!).
5   IF +VE PC <= S  Set the program counter to line address S if the ACC > 0.
6   IF != 0 PC <= S Set the program counter to line address S if the ACC is not 0.
7   STOP            Computer stops.

You can not package this VM with a traditional mark&sweep algorithm for garbage collection because the garbage collector has no way to know which data is useful, and which is just jibberish or a value (which in turn can be either a number or an address).

I guess the problem boils down to how much information your instruction set can express from within the program. If you preserve enough information in the compiled version of your program the VM can automatically garbage collect, instead of writing a garbage collector and compiling it with the program itself.

So in short, is there a minimum level of abstraction you need to have a VM that garbage collects?

Up to this point my guess is type information, and functions boundaries etc.

  • 2
    What values can S take? How do those values get there? – Caleth Aug 4 '17 at 11:40
  • [S] means "the value at the address S. And S can only be a memory address, or a label which points to a constant. (This is the instruction set for the MU0 machine). – Christophe De Troyer Aug 4 '17 at 12:06
  • I'm not asking about [S]. What's the grammar for S? – Caleth Aug 4 '17 at 12:07
  • A number or a string (e.g. "L1"). And a label always points to a constant number in that case. – Christophe De Troyer Aug 4 '17 at 13:15
  • 1
    @amon the VM as described doesn't have the notion of dynamic allocation. There's nothing for a GC to do here – Caleth Aug 4 '17 at 14:41
7

For garbage collection we need to know two things:

  • Which memory regions were allocated?
  • Given a memory region, is it reachable?

If in your instruction set S must be a literal, then all memory addresses would be statically known. If S can also read from ACC, then you have unrestricted pointers and can write to arbitrary memory addresses. So neither does your VM have a concept of memory allocation nor is it possible to discuss reachability.

It is helpful to compare this with other systems.

C does know which memory regions were allocated because it is undefined behaviour to write to arbitrary addresses – you can access objects on the stack, you can malloc(), or you can use system calls mmap() to make a memory region available. In particular, malloc()/free() necessarily manage information that is largely comparable to a GC system.

Reachability in C is more complicated because any type information is erased at run time: you do not know whether a given word of memory is supposed to be a pointer. A GC system must therefore be conservative and assume that anything could be a pointer. However, you can only access memory without undefined behaviour if you hold a pointer into that memory region. Therefore, a GC system for C does not have to solve the Halting Problem, unless you are doing some seriously weird stuff like manually compressing pointers.

In a language designed for GC, pointer arithmetic is usually disallowed. You can only dereference pointers, not increment them. The only special case is arrays, which may contain metadata to allow runtime bounds checking. Since this is more restricted, it is easier to reason about such pointers and to perform a safer reachability analysis.

Many GC language implementations also keep runtime type information. Given an arbitrary memory region that has been properly allocated by the rules of that system, we can tell what type it has, which members it has, …. A GC system can then be exact and need not be conservative.

If such information is available at runtime we also have other options for better GC:

  • Given a dependency graph between memory regions, we can move a memory region to a new location and update all pointers that point to it. This is useful for compacting garbage collectors: Since this prevents memory fragmentation, allocations can become much faster.
  • If every memory region holds type metadata, it is easy to also add GC metadata, e.g. for tracing GC, or for reference counting.

It would be possible to adapt your instruction set to make a C-like conservative GC possible: just introduce an instructions to allocate memory, possibly free memory, and access memory at a variable offset to a pointer (you will need two registers for that). If it is undefined behaviour to perform arbitrary pointer arithmetic, the you can implement GC. However, that system is not memory safe and could still be used to access unallocated memory.

If you want to do better, you will have to tag each memory cell with GC metadata. A single bit flag to indicate whether this cell is a pointer or other value would suffice to perform an exact reachability analysis.

  • Ah, it is just that simple. Thanks for the very elaborate explanation. I'd give you 2 upvotes if I could. I think I'll go for the bit flags to set pointer/value. – Christophe De Troyer Aug 4 '17 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.