Re: GC+FSD for GNAT/GCC

["Nick Roberts" <Nick.Roberts@dial.pipex.com>]

Andi Kleen wrote in message ...
[...]
|I wonder how hard it would be to put a "malloc()" plugin compatible
conservative
|GC like the Boehm GC into the GNAT run time library. As far as I can see
|GNAT uses a wrapper around the C Library's malloc function for its memory
|allocation needs. What would happen if I linked it with a GC malloc
library?


This strategy alone couldn't perform heap compaction - I'm going to call it
'free space defragmentation' (FSD) from now on (if nobody minds) - only GC,
and even then there are better ways (I think) of providing the GC. Without
FSD, however, you inevitably get creeping fragmentation (unless all blocks
allocated in the pool are the same size). I doubt that a GC scheme which
does not deal with fragmentation is of much value, in reality, but I would
welcome comments on this.

One kind of 'mark-sweep' scheme I am envisioning at this stage has the
following broad design.

The compiler (I'm not sure whether the front or back end) generates a piece
of constant data which encodes the locations of all access objects within
each record and array type, and of all access objects, and access
component-containing records and arrays, within each stack-frame. This data
is called the 'crib'.

The pool type's implementation can then use this crib to 'sweep' over all
access objects (including all those in the pool itself), 'marking' all
allocated objects which are still accessed (thus finding out all which are
not accessed, so performing GC), and then to sweep again, adjusting the
access values (or their data-pointers) as required (as a part of FSD).
Finally, the extant objects are shuffled into their new positions
(completing the FSD).

This is a non-locking scheme. The user (Ada programmer) must ensure that the
execution of a block which contains code that uses a pool (managed by this
scheme) in one task will never overlap with the execution of a block which
contains code that uses the same pool in another task. (If this cannot be
arranged, a locking scheme must be selected instead.) The most common case
will be where the pool is only ever used in one task (indeed, frequently in
a program which only has one task).

The compiler must generate code such that: no access object is in a
temporary location whenever an allocator or deallocator (of a managed pool)
is called; for every access object whose value is put into a temporary
location within a certain block, the value is written back into the
non-temporary location before the end of that block.

There are some details of this scheme I haven't quite sorted out yet (it's
quite complicated), but nothing major (with luck).

It is important to realise that this is just one scheme (albeit the most
important one, I think). I believe a variety of schemes -
locking/non-locking, mark-sweep/reference counter,
crib-reiteration/double-indirection/ring-of-pointers - will have to be
supplied.

Comments?

-------------------------------------------
Nick Roberts
-------------------------------------------

PS: I think the __GNAT_malloc() and __GNAT_free() routines would remain
unchanged, the entire GC+FSD stuff being managed at a higher level.