Re: Garbage Collection in Ada

["Norman H. Cohen" <ncohen@watson.ibm.com>]

Robert A Duff wrote:
 
> In article <mheaney-ya023280000311962335300001@news.ni.net>,
> Matthew Heaney <mheaney@ni.net> wrote:
> >Language designers: any reason why overloading "all" would be too hard?
> 
> Well, functions return values (or constant objects, if you want to be
> precise in Ada 95 terms), whereas "P.all" returns a variable (if P is an
> access-to-variable type).  So it wouldn't work.  

The same scheme that Ada 95 uses to allow programmers to redefine the
behavior of "new" could have been used to allow redefinition of the
behavior of ".all".  The type System.Storage_Pools.Root_Storage_Pool
could have been given another primitive operation to be overridden by
those defining their own storage-pool types:

   procedure Dereference
      (Pool                     : in out Root_Storage_Pool;
       Storage_Address          : in out Address;
       Storage_Size_In_Elements : in Storage_Elements.Storage_Count;
       Alignment                : in Storage_Elements.Storage_Count);

The compiler would generate code for .all that would compute the nominal
address of the designated object and invoke Dereference, passing that
address to Storage_Address.  Dereference would, in some cases, replace
that address with a different one.  (Unlike Allocate, Deallocate, and
Storage_Size, Dereference would not be abstract; it would have a default
implementation that does nothing.  People not interested in redefining
the behavior of ".all" could ignore it.  I'm not sure why the last two
parameters are really needed; I'm just being "foolishly consistent" with
Allocate and Deallocate.)

One potential use of Dereference would be to recognize "forwarding
pointers" in a storage pool with background compactifying garbage
collection.  As objects are copied from the current area into the new,
compacted area, the old copy of an object is replaced by a special value
indicating that the object has been moved, followed by the new address
of the object.  Dereference would return without doing anything for
objects that had not been moved, and would return the address indicated
by the forwarding pointer for objects that had been moved.

Another potential use of Dereference would be swizzling:  A data
structure consisting of many nodes pointing at each other would be
represented partly in a persistent store (e.g. on a disk) with some sort
of persistent pointers (e.g. disk addresses or indices) and partly in
memory.  Nodes would be lazily brought into memory as needed.  One
possible implementation is to use values of type Address to encode
persistent pointers.  There would be a hash table mapping persistent
pointers to in-memory objects.  Dereference would be passed an encoded
persistent pointer through its Storage_Address parameter and would look
up that perisistent pointer in the hash table.  If there was not already
an entry for that persistent pointer in the hash table, Dereference
would read the node from the persistent store into memory and create a
hash-table entry mapping the persistent pointer to the new in-memory
address.  Then, in any event, Dereference would replace its
Storage_Address parameter with the in-memory address of the object
(either the one that was found already in the hash table or the one that
it just inserted there because it had not been in the hash table).

As a final example, Dereference could be used to implement a storage
pool with *checked* deallocation.  The storage pool would implement a
pointer to X as a pointer to a pointer to X.  Access-value assignment
would have the effect of creating multiple copies to the
pointer-to-pointer-to X.  Deallocation would consist of freeing the
storage for X itself and setting the direct pointer to X to null. 
Dereference would implement the extra level of indirection and also
check that the address it is passed is not the address of a null pointer
(indicating an attempt to dereference a pointer to a deallocated
object).

--
Norman H. Cohen
mailto:ncohen@watson.ibm.com
http://www.research.ibm.com/people/n/ncohen