[Texmacs-dev] Reliable detection of pointers (C++)

[Joris van der Hoeven]

I think that the main technical difficulty for the implementation of
well-adapted garbage collectors in C++ is the reliable detection of
all pointers in memory. I essentially see two ways for doing that

Inserting an additional level of indirection
--------------------------------------------
We implement a personal pointer<T> template class, which is actually
a double pointer:

    ptr ---->  back-ptr
               real-ptr    ----> object

The back-ptr points back to the address of ptr and the objects
back-ptr/real-ptr are stored in a linked list with all currently
available pointers.

Clearly, this method is correct, but it uses a significant amount
of overhead. We might want to use it for testing though,
since it would allow us to reliably detect memory leaks and,
with a bit more work, even display the zombie objects.

Implementing a marking algorithm
--------------------------------
In this case, each TeXmacs representation class comes with
a special method "mark" in order to mark the object and
its subobjects. In other words, the marking algorithm
traverses the whole pointer structure.

The advantage of this method is that it requires no additional
overhead for allocation/deallocation. The disadvantage is that
it is extremely cumbersome to implement and that it is easy to
forget marking something when modifying some code. Nevertheless,
one might use this method in combination with a double indirection
for debugging purposes.

Of course, it would be really great if C++ could come with
native support for marking algorithms. Something like
an operator mark for each type whose default implementation
(for new classes) would be to call a global (redefinable) marking
operator with the address of the object. This routine returns
true if the object was not already marked and false otherwise.
Next the marking operator is recursively called for all fields.
The default implementation for base classes (int, char, etc.)
would be no-op and the default implementation for pointer
classes T* would be to call the marking operator for
the pointed object.

Application 1: conservative garbage collection
----------------------------------------------
Clearly, a first application of reliable pointer detection is
that one may design a conservative garbage collector.

Application 2: compactification
-------------------------------
More interestingly, both schemes also allow for
the implementation of a compactifying garbage collector.

Indeed, in the first case, we may relocate the alive objects in
consecutive memory and update the middle pointers. The linked list
of pointers is maintained in a separate part of the heap.

In the case when we have a marking algorithm, we may use
a global flag which indicates whether the marking algorithm
is used for garbage collection or compactification.
In the compactification phase, the word used for marking
now contains the new address (in consecutive memory)
of each block.