Select then abort can fail to abort the abortable part

Select then abort can fail to abort the abortable part

[Jean François Martinez]

Context:  Gnat x86_64 on Linux


Let's have that simple loop

for Ind in 1..6
loop
    Start:=Clock;
    select
        delay Ind * 10.0
    then abort 
       Ultimate_Prime;
    end select; 
    My_Duration:= Clock - Start;
end loop;

Ultimate_Prime is function containing a nearly infinite loop trying to 
find prime numbers.  

First version stores primes found.  This mandates a linked list but that 
would create an unacceptable overhead so I use big chunks

     type Big_Array is array (Positive range 1..100_000) of Long_Mod;
     type Chunk is record
          Position: Positive  range Big_Array'Range;
          Payload: Big_Array;
     end record;
     type T_Ptr_Chunk is access  T;

     package P_List_Chunks is
       new Ada.Containers.Doubly_Linked_Lists(T_Ptr_Chunk);
     use P_List_Chunks;

     List_Chunks: List;


So this first version is "dumb": it tries every odd number until 
Divisor * Divisor > Candidate.  If it is a prime it is stored in the 
Payload array though an access variable ie _without_ even looking at the 
List.  The List is only accessed for concatenating a new Chunk.
Now when I run it I notice that the select then abort can take over 1 
second or even two seconds more than the delay and the number of
Primes found is ever a multiple of 100_000 ie the function was only 
aborted when it entered code provided by AdaCore in order to allocate a 
new Chunk and to add a new element to the List.

The second version is "smart". It only tries to divide by prime numbers.  
This means we have to use the numbers previously stored in our list so

for An_Element in List_Chunks
loop 
    for Ind in 1..Position
    loop

In this version we are constantly traversing List_Chunks and using 
Adacore's code.  Here the function is aborted very close after the 
expiration of the delay (from memory 0.05 at most after expiration) and 
the number of prime numbers found is not a multiple of 100_000.

Third version is tries very odd number as divisor but stores only the 
last prime found.  Ie no lists, no nothing.  Just user code, nothing from 
the run time or AdaCore's libraries.   In this version the delay expires 
but the there is no abort _at all_.  Function will run until it leaves 
voluntarily in, according my estimations, something like five hundred 
thousand years.

Is this incorrect behavior?

---
Jean-François Martinez

Re: Select then abort can fail to abort the abortable part

[Dmitry A. Kazakov]

On 20 Nov 2014 21:08:50 GMT, Jean François Martinez wrote:

> Context:  Gnat x86_64 on Linux
> 
> 
> Let's have that simple loop
> 
> for Ind in 1..6
> loop
>     Start:=Clock;
>     select
>         delay Ind * 10.0
>     then abort 
>        Ultimate_Prime;
>     end select; 
>     My_Duration:= Clock - Start;
> end loop;
> 
> Ultimate_Prime is function containing a nearly infinite loop trying to 
> find prime numbers.  
> 
> First version stores primes found.  This mandates a linked list but that 
> would create an unacceptable overhead so I use big chunks
> 
>      type Big_Array is array (Positive range 1..100_000) of Long_Mod;
>      type Chunk is record
>           Position: Positive  range Big_Array'Range;
>           Payload: Big_Array;
>      end record;
>      type T_Ptr_Chunk is access  T;
> 
>      package P_List_Chunks is
>        new Ada.Containers.Doubly_Linked_Lists(T_Ptr_Chunk);

You certainly should not abort any code changing dynamically allocated
structures. I don't know the implementation of
Ada.Containers.Doubly_Linked_Lists, but it is not protected against abort
in the middle of changing list links, you may get garbage in the result.

You should almost never use the asynchronous transfer of control. A clean
method of aborting a lengthy computation is by inserting inspection points
within loops and raising an exception when abort was requested or time was
expired.

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

Re: Select then abort can fail to abort the abortable part

[Adam Beneschan]

On Thursday, November 20, 2014 1:08:51 PM UTC-8, Jean François Martinez wrote:

> Is this incorrect behavior?

I believe it's incorrect behavior only if a compiler supports Annex D (because then section D.6 about Preemptive Abort must apply).  If a compiler doesn't support Annex D, then an abortable part must be aborted only at certain "abort completion points" as defined by 9.8(16-19); if the code keeps running without reaching any of those points, it doesn't have to abort.  

My understanding is that Windows native compilers can't really support Annex D because the OS makes it difficult to abort a thread in the needed way.  On Unix/Linux, a timer could be set up that causes a signal; however, my experience with Unix/Linux signals is that it's easy to get yourself hosed, if a signal happens to occur at an inopportune time, or another signal happens while one signal is being handled so that there's a danger that the signal might get lost.  So while I have no idea whether GNAT for Linux claims to support Annex D, it would be understandable to me that it wouldn't.

A workaround is to put "delay 0.0" at strategic points in your code, since that's an abort completion point.  It would essentially poll to see if the delay in the SELECT has expired.  GNAT also has a Polling pragma, at least for Windows, but maybe it works on Linux too.

See this earlier thread: https://groups.google.com/forum/?hl=en#!searchin/comp.lang.ada/D.6$20AND$20after$3A2013$2F01$2F01$20AND$20before$3Atoday%7Csort:relevance/comp.lang.ada/748DRqqa7v0/llYfPx731ucJ

                                -- Adam

Re: Select then abort can fail to abort the abortable part

[Jean François Martinez]

On Thu, 20 Nov 2014 22:35:27 +0100, Dmitry A. Kazakov wrote:


> 
> You certainly should not abort any code changing dynamically allocated
> structures. I don't know the implementation of
> Ada.Containers.Doubly_Linked_Lists, but it is not protected against
> abort in the middle of changing list links, you may get garbage in the
> result.
> 

Actually Lists are Controlled Objects and an exception is raised if 
you try to abort a task at the time it is trying to modify the List

> You should almost never use the asynchronous transfer of control. A
> clean method of aborting a lengthy computation is by inserting
> inspection points within loops and raising an exception when abort was
> requested or time was expired.

I was just kicking the tires of something (select then abort) I have 
never used.  

---
Jean-François Martinez

Re: Select then abort can fail to abort the abortable part

[Jean François Martinez]

On Thu, 20 Nov 2014 13:36:25 -0800, Adam Beneschan wrote:

> On Thursday, November 20, 2014 1:08:51 PM UTC-8, Jean François Martinez
> wrote:
> 
>> Is this incorrect behavior?
> 
> I believe it's incorrect behavior only if a compiler supports Annex D
> (because then section D.6 about Preemptive Abort must apply).  If a
> compiler doesn't support Annex D, then an abortable part must be aborted
> only at certain "abort completion points" as defined by 9.8(16-19); if
> the code keeps running without reaching any of those points, it doesn't
> have to abort.
> 

Actually Gnat is supposed to support Annex D but in Linux there are 
several units of it marked as non implementable on Linux.

I have looked in the ARM both for delay and select then abort and there 
is nothing or at least I have seen nothing.

> My understanding is that Windows native compilers can't really support
> Annex D because the OS makes it difficult to abort a thread in the
> needed way.  On Unix/Linux, a timer could be set up that causes a
> signal; however, my experience with Unix/Linux signals is that it's easy
> to get yourself hosed, if a signal happens to occur at an inopportune
> time, or another signal happens while one signal is being handled so
> that there's a danger that the signal might get lost.  So while I have
> no idea whether GNAT for Linux claims to support Annex D, it would be
> understandable to me that it wouldn't.
> 
> A workaround is to put "delay 0.0" at strategic points in your code,
> since that's an abort completion point.  It would essentially poll to
> see if the delay in the SELECT has expired.  GNAT also has a Polling
> pragma, at least for Windows, but maybe it works on Linux too.
> 

Actually I was thinking about using timing events: inserting delays in 
the code is difficult: simple solutions like checking every N prime 
numbers found do not work since finding an new one is far longer at 100 
million than at ten thousand.  Checking every N tests is ugly and heavy.

---
Jean-François Martinez

Re: Select then abort can fail to abort the abortable part

[Dmitry A. Kazakov]

On 20 Nov 2014 22:19:30 GMT, Jean François Martinez wrote:

> On Thu, 20 Nov 2014 22:35:27 +0100, Dmitry A. Kazakov wrote:
> 
>> You certainly should not abort any code changing dynamically allocated
>> structures. I don't know the implementation of
>> Ada.Containers.Doubly_Linked_Lists, but it is not protected against
>> abort in the middle of changing list links, you may get garbage in the
>> result.
> 
> Actually Lists are Controlled Objects and an exception is raised if 
> you try to abort a task at the time it is trying to modify the List

I don't see how being controlled (or tagged) were related. Primitive
operations are not abort-deferred except for Initialize and Finalize (and
only under certain conditions). RM 9.8.

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

Re: Select then abort can fail to abort the abortable part

[Jean François Martinez]

On Friday, November 21, 2014 9:37:33 AM UTC+1, Dmitry A. Kazakov wrote:

> I don't see how being controlled (or tagged) were related. Primitive
> operations are not abort-deferred except for Initialize and Finalize (and
> only under certain conditions). RM 9.8.
> 

Actually while playing with asynchronous select I got an exception from  Ada.Containers.Doubly_Linked_Lists telling me I was trying to abort at the wrong time and about a controlled object.

I think somewhere in the code there is 

procedure Must_be_atomic is
  A: My_controlled_type;
begin

end My_Atomic

and the Finalize of My_Controled_Type raising an exception
---
Jean-Frannçois Martinez