Re: Garbage Collection for Ada

Re: Garbage Collection for Ada

[Nick Roberts]

http://www.opensource.org sorry

Nick Roberts

Garbage Collection for Ada

[Nick Roberts]

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;

Garbage Collection for Ada

[llothar]

Hello,

i found an old patch to gcc that implements a garbage collector for
GNAT (based on the popular Boehm-Weisser GC).

Is there any current work on this topic.

I was never interested in ADA because i don't go back to full manual
management, but i'm now looking for a new language for one project that
got to big.

Re: Garbage Collection for Ada

[jimmaureenrogers]

llothar wrote:
> Hello,
>
> i found an old patch to gcc that implements a garbage collector for
> GNAT (based on the popular Boehm-Weisser GC).
>
> Is there any current work on this topic.
>
> I was never interested in ADA because i don't go back to full manual
> management, but i'm now looking for a new language for one project that
> got to big.

Have you ever studied Ada?
Do you have any idea how much manual memory management you might be
forced to do?
How much do you know about Ada controlled types?

Jim Rogers

Re: Garbage Collection for Ada

[Martin Krischik]

llothar wrote:

> Hello,
> 
> i found an old patch to gcc that implements a garbage collector for
> GNAT (based on the popular Boehm-Weisser GC).
> 
> Is there any current work on this topic.

Yes:

http://adacl.sourceforge.net/pmwiki.php/Main/GarbageCollector

Ok - there was no update for a while - but then nothing much changed in that
area anyway.

> I was never interested in ADA because i don't go back to full manual
> management, but i'm now looking for a new language for one project that
> got to big.

Ada's natural storrage is the stack and not the heap - most objects are
created on the stack. So even with manual heap management Ada is a lot
easier to use then heap based. 

Martin
-- 
mailto://krischik@users.sourceforge.net
Ada programming at: http://ada.krischik.com

Re: Garbage Collection for Ada

[Robert A Duff]

Martin Krischik <krischik@users.sourceforge.net> writes:

> Ada's natural storrage is the stack and not the heap - most objects are
> created on the stack. So even with manual heap management Ada is a lot
> easier to use then heap based. 

It's certainly a good idea to use local (stack) variables when possible,
and Ada makes it possible in more cases than some other languages.
However, for the kinds of programs I usually write (compilers, program
analysis tools, etc) most objects are on the heap.  By far.

I use user-defined storage pools heavily, by the way.

- Bob