3

In a copying garbage collector, when I copy the objects from the from-space to the to-space, certain objects could be referenced by a pointer stored in a register. When the garbage collection happens, that register needs to be updated to point to the to-space.

The problem is, the garbage collection is executed at specific points during the program (let's say when the user allocates memory) and thus, this will call a function to do the collection. That will, in turn, use registers which might be the ones we actually need to forward. So, that creates multiple problems:

  • The register that we need to forward will not contain the address of the object to be forwarded.
  • The register will be restored when returning from the garbage collection function, so we cannot forward it at this point anyway.

So how can I do the pointer forwarding for an object whose pointer is stored in a pointer? We can assume the garbage collector is written in C, not in assembly (which would make it easy to not overwrite the registers).

antoyo
  • 11,097
  • 7
  • 51
  • 82
  • 1
    When “the register that we need to forward will not contain the address of the object to be forwarded”, then you don’t need to forward the register. You need to forward the reference on the stack, where the register has been saved to. And forwarding references on the stack should be in your repertoire anyway. – Holger Mar 02 '20 at 10:26
  • @Holger: How do I know where the callee-save registers have been saved? – antoyo Mar 02 '20 at 12:34
  • 1
    There’s too little information about the scenario. Normally, for implementing a language with gc or a virtual machine, you are in control of the application code generation, which is necessary to understand its stack format. So its a no-brainer to insert code pushing all registers containing object references to the stack before calling the garbage collector and retrieving them after returning. You don’t need to rely on register saving mechanisms inside the garbage collector code. – Holger Mar 02 '20 at 12:46
  • @Holger: Thanks! If you post that as an answer, I'll accept it. – antoyo Mar 02 '20 at 12:56

2 Answers2

3

Efficient garbage collection for a programming language or virtual machine, designed for garbage collection right from the start, always collaborates with the code generation.

Obviously, the garbage collector has to know the layout of the stack data to be able to analyze it. For efficiency, the generated code doesn’t need to support garbage collection at any point of time but only at certain safepoints where it may suspend itself when need for garbage collection has been flagged or, like in your single-threaded case, will call into the garbage collector directly.

At these points, the code has to bring its data in a form understood by the garbage collector. A simple solution is to push the registers to the stack, using the format known by the garbage collector, before calling the garbage collector and popping them back afterwards. So the mechanism doesn’t need to deal with register saving mechanisms of a different language, used for implementing the garbage collector itself.

Holger
  • 285,553
  • 42
  • 434
  • 765
1

So how can I do the pointer forwarding for an object whose pointer is stored in a pointer

You can only do that atomically and making the pointer visible to all other threads when you are done.

This is done differently by different GCs. Usually, GCs employ barriers for such a purpose, some code that is executed at the point when GC is running (like an interceptor to your objects).

So when some thread tries to allocate memory/change some object, while GC is running, it will not alter the pointer/object directly - but go through some code that will do that. Updating the forwarding pointer is usually a single-shot CAS, to re-map this forwarding pointer, making it visible to all threads.

I've explained how this is done here, it is java specific to Shenandoah GC, but the theory is still the same.

Eugene
  • 117,005
  • 15
  • 201
  • 306
  • In my case, the programs are single-threaded and the garbage collector runs in the same thread as the program. I would assume there is a much simpler solution to my problem here. – antoyo Mar 01 '20 at 14:08
  • 1
    @antoyo aren't modifications done in a Thread visible in that thread also? what is the problem or what am I missing here? – Eugene Mar 01 '20 at 14:23
  • My project does not support multiple threads, so I don't need atomics. It's a stop-the-world garbage collector. – antoyo Mar 01 '20 at 14:28
  • 1
    @antoyo then your problem is automatically solved. when you are doing GC, simply update the forward pointer and you are done. – Eugene Mar 01 '20 at 14:30
  • So, you're saying there's no way to avoid the indirection in this case? That would be avoided if we could update the registers directly, which I assume we could update if we knew the save location of the callee-save registers — we already know the save location of the caller-save registers. – antoyo Mar 01 '20 at 14:44
  • actually, even with the forwarding pointers, I have the same problem: I cannot read this forwarding pointer from the register, because the garbage collector, while executing up to that point, will have overwritten this register. So how do I get that value from the overwritten register? – antoyo Mar 01 '20 at 15:22