Garbage Collection for Ada

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

In another thread, Robert Dewar (dewar@gnat.com) wrote...
|It is of course trivial to implement conservative garbage
|collection, and any number of the commercial tools in this
|area work fine with GNAT. That is of course a given, but
|that is not what I was talking about, I was talking about
|implementing full, accurate, compacting garbage collection
|of the type expected in an Algol-68 compiler. That's a big
|project, probably several person months from someone who
|knows what they are doing, longer for someone who has to
|learn.

I am serious about doing half of this myself, and making it freely available
(under an 'open source' licence - see http://www.opensource.com).

Which half? The half which can be compiler-independent, and implemented
entirely in terms of user-defined pool types.

And the other half? I believe compiler makers would have to provide certain
extra facilities (to those specified by the RM95) in order to enable
comprehensive strategies to work (reliably). I would expect other people to
provide these facilities; it would not be appropriate for me (and I am not
willing) to do this half myself.

These facilities might constitute: (a) a new abstract type (or maybe
several), derived from System.Storage_Pools.Root_Storage_Pool, which defines
certain extra operations; (b) a new pragma; (c) crib generation and a
package to access the crib.

The new type might be called Root_Managed_Pool, and provide the extra
subprograms:

   function Flag (Pool: in Root_Storage_Pool; Object: in Storage_Address)
return Boolean is abstract;

   procedure Set_Flag (Pool: in out Root_Storage_Pool; Object: in
Storage_Address; Value: Boolean := True) is abstract;

   procedure Flagged_Access (Pool: in out Root_Storage_Pool; Object: out
Storage_Address) is abstract;

The idea is that each possible access object within the pool has a Boolean
flag associated with it, and that, under Trap_Flagged_Read_Access and
Trap_Flagged_Write_Access (see below), whenever the compiler attempts to
dereference an access object (for reading or writing respectively) whose
flag is set (True), it calls Flagged_Access first. Upon return from
Flagged_Access, the dereference continues as normal.

The pragma might be:

   pragma Access_Object_Semantics ([Pool_Type =>] type_name,
ao_semantics_item {,ao_semantics_item});

where ao_semantics_item might be one of: Block_Local_Temporaries;
Double_Indirection; Trap_Flagged_Read_Access; Trap_Flagged_Write_Access;
Protected_Access.

Block_Local_Temporaries is intended to prevent the storage of access object
values in temporary places other than where the temporary is loaded and
spilled back entirely within one block (in the source text).
Double_Indirection causes each dereference to be in terms of a
pointer-to-a-pointer (i.e. a double dereference). Protected_Access causes
each dereference to be pool-atomic (thus, almost certainly, having to be
surrounded by a semaphore lock/unlock or similar).

To create a managed pool type, the programmer would derive a type from
Root_Managed_Pool, apply the pragma Access_Object_Semantics to it (with the
appropriate semantics), and then override the various subprograms as
necessary.

My initial idea for a package specification for crib access is enclosed
(below). It
has deficiencies at present, but it gives the general 'flavour'.

Of course, these are all merely preliminary ideas at this stage. They will
have to be discussed, amended, and 'firmed up'.

However, what I need now is some sort of assurance that at least some
compiler makers (including ACT or someone else suitable for modifying GNAT)
would be willing to implement these facilities (or at least would seriously
entertain the idea of doing so).

If the general attitude is going to be "sorry, not interested", then,
naturally, I shall consider it a waste of my time developing the garbage
collectors. Otherwise, all compiler makers who implement the above
facilities will then stand to be able to instantly add my wonderful set of
garbage collectors (which will, genuinely, boast state-of-the-art
technology) to their own compilers. (True, it may take me several 'person
months', but I do know what I'm doing!)

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



----------------------------------------------------------------------------
--
-- Garbage Collection for Ada Project
----------------------------------------------------------------------------
--

with System.Storage_Elements;

package System.Crib_Access is

   subtype Access_Component_Count is Integer range 0..???;

   type Access_Component_List (NAC: Access_Component_Count) is
      record
         Offsets: array (1..NAC) of System.Storage_Elements.Storage_Offset;
      end record;

   type Access_Component_List_Lookup is
                                     access constant Access_Component_List;

   type Access_Object_Kind is (Single_Object, Array_Object, Record_Object);

   subtype Array_Length is Integer range 0..Integer'Last; -- correct?

   type Access_Object_Descriptor (Kind: Access_Object_Kind) is
      record
         Location: System.Address;
         case Kind is
            when Single_Object => null;
            when Array_Object  => Count: Array_Length;
            when Record_Object => Cmpts: Access_Component_List_Lookup;
         end case;
      end record;

   type Access_Object_Descriptor_Lookup is
                                  access constant Access_Object_Descriptor;

   subtype Access_Object_Count is Integer range 0..???;

   type Activation_Record_Crib (NAO: Access_Object_Count) is
      record
         AOD: array (1..NAO) of Access_Object_Descriptor_Lookup;
      end record;

   subtype Dynamic_Structure_Crib is Access_Object_Crib;

   type Activation_Record_Crib_Lookup is
                                    access constant Activation_Record_Crib;
   type Dynamic_Structure_Crib_Lookup is
                                    access constant Dynamic_Structure_Crib;

   subtype Activation_Record_Count is Integer range 0..???;
   subtype Dynamic_Structure_Count is Integer range 0..???;

   type Program_Crib (NAR: Activation_Record_Count;
                      NDS: Dynamic_Structure_Count) is
      record
         ARC: array (1..NAR) of Activation_Record_Crib_Lookup;
         DSC: array (1..NDS) of Dynamic_Structure_Crib_Lookup;
      end record;

   type Program_Crib_Lookup is access constant Program_Crib;

   function Current_Crib return Program_Crib_Lookup;

end System.Crib_Access;