Re: Java vs Ada 95 (Was Re: Once again, Ada absent from DoD SBIR solicitation)

[geert@fozzie.sun3.iaf.nl (Geert Bosch)]

Robert Dewar (dewar@merv.cs.nyu.edu) wrote:
   Robert replies to my earlier remark:

   You cannot assume anything about the bodies of standard units that is
   not specified in the reference manual. The question here focuses on
   whether RM A.3 applies to implicit calls to finalize, and what exactly
   "perform as specified" means for these implicit calls, given that no
   specification for finalize is given.

I think it is a real reach to say that an Ada implementation is allowed
to provide an Unbounded_Strings package body which execution can be
erroneous in tasking programs.

   I think it is a real reach to say that RM A.3 forbids the reference count
   approach, but it is certainaly discussable.

Of course the RM doesn't forbid refcounting! It just has to be implemented
properly, ie task-safe. It is possible to write a safe and correct 
reference counted implementation of bounded strings that satisfies
these criterea. Of course you need a low-overhead locking primitive 
as I said, or even better, you would just use an Ada compiler with a
fast implementation of simple protected types (using test-and-set or a
similair primitive instead of OS calls).

   Note that Geert's claim about test and set is wrong, or at least wrong if
   you claim to implemnt Annex D. Simple minded use of test and set can
   lead to priority inversions of a type forbidden by Annex D,

Simple minded use of any locking scheme can lead to problems, but
that is not an excuse to use no locking at all for a reference-counting
Bounded_String implementation. 

A possible scheme for safe reference counting using test-and-set
as locking mechanism is given below, but it is not tested or whatsoever.

   type Safe_Fast_Lock is array (System.Priority'Range) of Boolean;
   pragma Pack (Safe_Fast_Lock);
   pragma Volatile_Components (Safe_Fast_Lock);

   Locking_Error : exception;

   procedure Get
     (The_Lock     : in out Safe_Fast_Lock;
      The_Priority : in Priority) is
   begin
      while Test_And_Set (The_Lock (The_Priority)) loop
	 delay 0.0;
      end loop;
      for P in reverse Priority.First .. The_Priority - 1 loop
	 if Test_And_Set (The_Lock (P)) then
	    -- Task with lower priority already has the lock and may
	    -- be starved. A more advanced scheme might be used here.
	    for Q in P + 1 .. The_Priority loop
	       The_Lock (P) := False;
            end loop;
	    raise Locking_Error;
         end if;
      end loop;
   end Get;

   procedure Release
     (The_Lock     : in out Safe_Fast_Lock;
      The_Priority : in Priority) is
   begin
      for P in Priority'First .. The_Priority loop
	 The_Lock (P) := False;
      end loop;
   end Release;
      
   type Referenced_Data is record
      Lock     : Safe_Fast_Lock := (others => False);
      Count    : Natural := 0;
      Data     : ...;
   end record;

   procedure Add_Reference (Reference : in out Referenced_Data) is
      My_Priority : Get_Priority;
   begin
      Get (Reference.Lock, My_Priority);
      Reference.Count := Reference.Count + 1;
      Release (Reference.Lock (My_Priority));
   end Add_Reference;

   procedure Remove_Reference (Reference : in out Referenced_Data) is
      My_Priority   : Get_Priority;
      No_References : Boolean;
   begin
      Get (Reference.Lock, My_Priority);
      Reference.Count := Reference.Count - 1;
      No_References := (Reference.Count = 0);
      Release (Reference.Lock, My_Priority);
      if No_References then
	 ... -- Deallocate the data
      end if;
   end Remove_Reference;
-- 
E-Mail: geert@sun3.iaf.nl