From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=0.6 required=5.0 tests=BAYES_00,FROM_WORDY autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,5730fbad1af2aeee,start X-Google-Attributes: gid103376,public From: "Nick Roberts" Subject: Garbage Collection for Ada Date: 1999/02/19 Message-ID: <7aio8n$p5c$1@plug.news.pipex.net> X-Deja-AN: 445946271 Organization: UUNET WorldCom server (post doesn't reflect views of UUNET WorldCom) X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3 Newsgroups: comp.lang.ada Date: 1999-02-19T00:00:00+00:00 List-Id: 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;