How to get to 100% precise tracing GC?

[Rainer Schuetze]

On 12/11/2020 09:43, Ola Fosheim Grøstad wrote:
> What restrictions have to be made to make the GC 100% precise?
>
> I am aware of:
> - unions
> - owning void* pointers?
>
> Would it be sufficient to:
>
> 1. ban void-pointers from owning memory with pointers in them?

These are not a problem with the current implementation, because precise
scanning is not done by the pointer type, but the type used for the
allocation. Pointer types don't contain enough information for
polymorphic classes or pointers to fields of structs.

>
> 2. require that aggregates with unions in them provide a union_pointers
> range like constructor that will yield all the pointers and their types?
> Standard library constructs with unions that contain pointers could
> provide it, so it would not affect the standard library I think.
>
> I believe that 2) could be checked at compile time when the code
> attempts to allocate from the GC. Although I guess you would also have
> to forbid allocating raw memory from the GC that is later emplaced with
> types that contain pointers.
>

The original proposal for the precise GC had a function call
gc_emplace() that allowed to specify pointer location for a memory
range. This could be used for unions or emplacement of data into untyped
memory.
This version of the GC used a bitmap of pointers in all of the memory,
while this is no longer done for large allocations, so the impact during
allocation is smaller.

> Or are there other obstacles for precise tracing?
>

It's mostly untyped allocations. For example delegate closures don't
come with type information.

Another problem is precise scanning of the stack. There is no info
generated by the compiler. It could be implemented similar to exception
unwinding data, but would have to be more precise as a thread can get
suspended by a GC at any instruction.