Tail recursion upon task destruction

Tail recursion upon task destruction

[Dmitry A. Kazakov]

Consider a task encapsulated in an object in either way:

   type Device is
      Driver : Driver_Task (Device'Access);

or

   type Device is
      Driver : not null access Driver_Task := Driver_Task (Device'Access);

Let the object is allocated dynamically and we wanted to destroy it from
the task. It seems that there is no way to do this:

   task Driver_Task (Object : not null access Device) is
       procedure Free is
          new Ada.Unchecked_Deallocation (Device, Device_Ptr)
       Self : Device_Ptr;
   begin
      
       ...

      accept Shut_Down;
      Self := Object.all'Unchecked_Access; -- Or whatever way

      Free (Self);  -- This will deadlock
   end Driver_Task;

The core problem is that a task cannot destroy itself, because that would
block for task termination, which never to happen.

What I do to solve this is an extra "collector task" to await for a
rendezvous with Driver_Tasks, accepting a pointer to the Device and then
after leaving the rendezvous, freeing it. That looks tedious.

Don't we need some kind of "tail recursion" for this destruction pattern?

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Tail recursion upon task destruction

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:jv8fpjlb56be$.1afg8uuwigjop$.dlg@40tude.net...
> Consider a task encapsulated in an object in either way:
>
>   type Device is
>      Driver : Driver_Task (Device'Access);
>
> or
>
>   type Device is
>      Driver : not null access Driver_Task := Driver_Task (Device'Access);
>
> Let the object is allocated dynamically and we wanted to destroy it from
> the task.

Ada does not allow an object to destroy/free itself. That's generally a good 
thing, because such an object cannot be an ADT (it cannot be used as the 
element of a container, for instance), and such a model would require a far 
more complex scheme of frame completion than is used now: wait for all taks, 
then finalize all objects, then free all memory.

I realize that there are a few cases where some other scheme would be better 
(we struggled with this in CLAW, as the finalization of library level 
objects tried to use the GUI task which of course has already terminated), 
but they would require such an earthquake in semantics as not to make any 
sense for Ada.

In your particular case, I don't understand why you don't use nesting to 
solve the problem. That is, put the objectinside of the task (either 
directly or logically), so it can be destroyed when the task needs to do 
that. That would look something like:

   task type Device;

  task type Device is
      Device_Data : not null access Device_Data_Type := new 
Device_Data_Type;
  begin
      ...
      Free (Device_Data);
  end Device;

Note: you'd need a named access type to actually do this - I used an 
anonymous one simply to make my point clearer.

                               Randy.

Re: Tail recursion upon task destruction

[Dmitry A. Kazakov]

On Tue, 17 Nov 2009 15:38:45 -0600, Randy Brukardt wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
> news:jv8fpjlb56be$.1afg8uuwigjop$.dlg@40tude.net...
>> Consider a task encapsulated in an object in either way:
>>
>>   type Device is
>>      Driver : Driver_Task (Device'Access);
>>
>> or
>>
>>   type Device is
>>      Driver : not null access Driver_Task := Driver_Task (Device'Access);
>>
>> Let the object is allocated dynamically and we wanted to destroy it from
>> the task.
> 
> Ada does not allow an object to destroy/free itself. That's generally a good 
> thing, because such an object cannot be an ADT

Only if we considered finalization request an operation. There are merits
in your point though.

> (it cannot be used as the 
> element of a container, for instance), and such a model would require a far 
> more complex scheme of frame completion than is used now: wait for all taks, 
> then finalize all objects, then free all memory.

No, that would impose no problem. It is not required that the caller of
Finalize be the object's task. It is only required that it can be *any*
task, including the object's one.

> In your particular case, I don't understand why you don't use nesting to 
> solve the problem. That is, put the objectinside of the task (either 
> directly or logically), so it can be destroyed when the task needs to do 
> that. That would look something like:
> 
>    task type Device;
> 
>   task type Device is
>       Device_Data : not null access Device_Data_Type := new 
> Device_Data_Type;
>   begin
>       ...
>       Free (Device_Data);
>   end Device;
> 
> Note: you'd need a named access type to actually do this - I used an 
> anonymous one simply to make my point clearer.

Unfortunately that does not work. I simplified the task description.
Actually in my case the device has some associated objects, say, screws.
They are reference counted, both the devices and screws. A device screw
holds a reference to its device. The screws are used somewhere in the
application. You can create and remove screws and devices. The application
may hold references them.

Now consider a case when the last screw is removed from the device. This is
an operation eventually serviced by the device driver. I.e. within the
device driver, you see, it was the last screw of the device and *if* there
is no other references to the device, it must fall apart. This is a case
where you wanted the device to commit suicide. There is nobody else out
there to do this. The device is dangling. This is not the only use case,
just one possible case.

And, considering the design. It looks logical that if screws are ultimately
removed at some dedicated context (of the device driver), then the devices
themselves could also be removed on the context of some "collector task". 

Nevertheless, I am not sure that all cases where active objects should
"commit suicide", should/could be treated this way.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Tail recursion upon task destruction

[stefan-lucks]

On Wed, 18 Nov 2009, Dmitry A. Kazakov wrote:

> Now consider a case when the last screw is removed from the device. This 
> is an operation eventually serviced by the device driver. I.e. within 
> the device driver, you see, it was the last screw of the device and *if* 
> there is no other references to the device, it must fall apart. This is 
> a case where you wanted the device to commit suicide. There is nobody 
> else out there to do this. The device is dangling. This is not the only 
> use case, just one possible case.

OK, so you have a task (a device) which notices that it is no longer 
useful. You would like such a task to do some cleanup and to commit 
"suicide". Unfortunately, it can't do the cleanup after the "suicide", 
because it is "dead" then. And it can't cleanup itself before being 
"dead" because it needs its local memory until the very moment of its 
"death".

But couldn't you just use (or maybe abuse) the features from 
Ada.Task_Termination to do perform the cleanup, after the task has died?
Even if it the "death" is not by suicide (apart from 
"suicide" = regular termination, the options are "murder" = abort and
"accident" = unhandled exception). 
See <http://www.adaic.org/standards/05rat/html/Rat-5-2.html#I1150>. 



-- 
------ Stefan Lucks   --  Bauhaus-University Weimar  --   Germany  ------
               Stefan dot Lucks at uni minus weimar dot de
------  I  love  the  taste  of  Cryptanalysis  in  the  morning!  ------

Re: Tail recursion upon task destruction

[Dmitry A. Kazakov]

On Wed, 18 Nov 2009 11:31:59 +0100, stefan-lucks@see-the.signature wrote:

> On Wed, 18 Nov 2009, Dmitry A. Kazakov wrote:
> 
>> Now consider a case when the last screw is removed from the device. This 
>> is an operation eventually serviced by the device driver. I.e. within 
>> the device driver, you see, it was the last screw of the device and *if* 
>> there is no other references to the device, it must fall apart. This is 
>> a case where you wanted the device to commit suicide. There is nobody 
>> else out there to do this. The device is dangling. This is not the only 
>> use case, just one possible case.
> 
> OK, so you have a task (a device) which notices that it is no longer 
> useful. You would like such a task to do some cleanup and to commit 
> "suicide". Unfortunately, it can't do the cleanup after the "suicide", 
> because it is "dead" then. And it can't cleanup itself before being 
> "dead" because it needs its local memory until the very moment of its 
> "death".
> 
> But couldn't you just use (or maybe abuse) the features from 
> Ada.Task_Termination to do perform the cleanup, after the task has died?
> Even if it the "death" is not by suicide (apart from 
> "suicide" = regular termination, the options are "murder" = abort and
> "accident" = unhandled exception). 
> See <http://www.adaic.org/standards/05rat/html/Rat-5-2.html#I1150>.

Yes, it is an interesting option. One could terminate the task and from the
handler kill the object. The difficulty is that Ada.Task_Termination is not
generic. It is not possible to pass a reference to the object to the
handler.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Tail recursion upon task destruction

[Egil Høvik]

On Nov 18, 11:31 am, stefan-lu...@see-the.signature wrote:
> On Wed, 18 Nov 2009, Dmitry A. Kazakov wrote:
> > Now consider a case when the last screw is removed from the device. This
> > is an operation eventually serviced by the device driver. I.e. within
> > the device driver, you see, it was the last screw of the device and *if*
> > there is no other references to the device, it must fall apart. This is
> > a case where you wanted the device to commit suicide. There is nobody
> > else out there to do this. The device is dangling. This is not the only
> > use case, just one possible case.
>
> OK, so you have a task (a device) which notices that it is no longer
> useful. You would like such a task to do some cleanup and to commit
> "suicide". Unfortunately, it can't do the cleanup after the "suicide",
> because it is "dead" then. And it can't cleanup itself before being
> "dead" because it needs its local memory until the very moment of its
> "death".
>
> But couldn't you just use (or maybe abuse) the features from
> Ada.Task_Termination to do perform the cleanup, after the task has died?
> Even if it the "death" is not by suicide (apart from
> "suicide" = regular termination, the options are "murder" = abort and
> "accident" = unhandled exception).
> See <http://www.adaic.org/standards/05rat/html/Rat-5-2.html#I1150>.
>
> --
> ------ Stefan Lucks   --  Bauhaus-University Weimar  --   Germany  ------
>                Stefan dot Lucks at uni minus weimar dot de
> ------  I  love  the  taste  of  Cryptanalysis  in  the  morning!  ------


This would still be a bounded error.
A task is not terminated until the task body has been finalized RM-9.3
(5),
and since Task_Termination handlers are executed as part of the
finalization
of task bodies RM-C.7.3(14/2), you would violate RM-13.11.2(11) by
deallocating
the task in the handler.

--
~egilhh

Re: Tail recursion upon task destruction

[Georg Bauhaus]

Dmitry A. Kazakov schrieb:

> Now consider a case when the last screw is removed from the device. This is
> an operation eventually serviced by the device driver. I.e. within the
> device driver, you see, it was the last screw of the device and *if* there
> is no other references to the device, it must fall apart. This is a case
> where you wanted the device to commit suicide. There is nobody else out
> there to do this. The device is dangling. This is not the only use case,
> just one possible case.

Could you make a Hammer task that will perform its duties
whenever a Device is reported/reports to have lost all its
screws?  (Yes, a garbage collector, I think, though explicitly
co-operating with devices.)

Re: Tail recursion upon task destruction

[Dmitry A. Kazakov]

On Wed, 18 Nov 2009 12:02:34 +0100, Georg Bauhaus wrote:

> Dmitry A. Kazakov schrieb:
> 
>> Now consider a case when the last screw is removed from the device. This is
>> an operation eventually serviced by the device driver. I.e. within the
>> device driver, you see, it was the last screw of the device and *if* there
>> is no other references to the device, it must fall apart. This is a case
>> where you wanted the device to commit suicide. There is nobody else out
>> there to do this. The device is dangling. This is not the only use case,
>> just one possible case.
> 
> Could you make a Hammer task that will perform its duties
> whenever a Device is reported/reports to have lost all its
> screws?  (Yes, a garbage collector, I think, though explicitly
> co-operating with devices.)

Yes, this is what I did.

But the question is of the general nature, why there should be an extra
task to destroy the given one? So the argument should be also general, like
the Randy's one about ADTs.

The counter argument and the problem is that the relation between an object
and its task is not evident in Ada, for multiple reasons. One of them is
that tasks are not tagged. So there is a problem, because when this
relation is ignored or missed by the designer, then a straightforward
implementation of the task will sometimes deadlock. That is not good.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de