About task-safeness

About task-safeness

[mockturtle]

Dear all,
I have a question (better, two questions) about packages and concurrence.  

We have a software, a fairly complex one, that makes use of tasks. (Just to give you the context, it is a network communication software that can have several connections open at once and every connection is handled by a task.)   Data structure that are designed to be shared among different tasks are implemented as protected objects, but it came to my mind that  an innocent-looking package (that maybe provides some general-purpose functions) could have some "internal state" represented by some variable global to the package.  (For example, a package defining some type of object could keep the number of allocated objects, so it can give to each object a unique ID.)  If such a package was used  by two  different tasks, and the counter was not protected, obscure bugs can arise.  This type of structure maybe is not very recommended, but it happens... :-(   

Of course, one could do a review of all the packages to check for this type of problems, but since an Ada compiler has the good habit of protecting you from yourself, I searched for a way to have the compiler to check the task-safety of the packages used by tasks.  

My first tentative was to ask that all the packages with-ed by a package that defines a task should be Pure (a Pure package cannot have any global variables).      Unfortunately, I soon discovered that asking for Pure-ity is too strong a requirement: all the ancestors must be Pure and no un-Pure package can be used.  Although such constraints make perfectly sense, they prevent you from using several standard (and useful) packages such as Unbounded_Strings, all (?) the Containers hierarchy and GNAT.Sockets (which turns out handy in a networking program...:-). (To be honest, my action of Pure-fication was not useless; while making my packages Pure, I caught a global counter in a package...) So, my first question is: 

   * Can you suggest a way to have the compiler to check for some task-safety of packages?  Even a technique for a non-totally exhaustive  check could be useful.

The thoughts above triggered in me another question.  Consider, for example, the Ordered_Maps package.  That package is not Pure (it cannot be, since it would prevent the use of named access types), so how can I be granted that the package does not have some "hidden" and unprotected state?  Please note that I am *not* asking for an *object* of type Ordered_Map to be task-safe, if I need I can wrap it in a protected object; I am asking for the *package* to be task-safe.  Note that if, say, Ordered_Maps has some hidden status, two task can modify the status at the same time by accessing to two Maps, even if the Maps have been wrapped inside two different protected  objects.  So, my second question is

  * Am I granted (maybe by some obscure paragraph of our beloved RM ;-) that the standard packages are task-safe? (I would be surprised if they weren't, but it is nice to be sure...)

Sorry for the quite long message and thank you for any help.

Re: About task-safeness

[Vinzent Hoefler]

mockturtle wrote:

>   * Am I granted (maybe by some obscure paragraph of our beloved RM ;-) that the standard
> packages are task-safe? (I would be surprised if they weren't, but it is nice to be sure...)

Well, ARM 05, A(3/2) says:

|The implementation shall ensure that each language-defined subprogram is reentrant in
|the sense that concurrent calls on the same subprogram perform as specified, so long
|as all parameters that could be passed by reference denote nonoverlapping objects.

Apart from that, you probably have to trust the programmer - or some tool.


Vinzent.

-- 
You know, we're sitting on four million pounds of fuel, one nuclear weapon,
and a thing that has 270,000 moving parts built by the lowest bidder.
Makes you feel good, doesn't it?
   --  Rockhound, "Armageddon"

Re: About task-safeness

[mockturtle]

On Wednesday, February 2, 2011 10:01:20 PM UTC+1, Vinzent Hoefler wrote:
> mockturtle wrote:
> 
> >   * Am I granted (maybe by some obscure paragraph of our beloved RM ;-) that the standard
> > packages are task-safe? (I would be surprised if they weren't, but it is nice to be sure...)
> 
> Well, ARM 05, A(3/2) says:
> 
> |The implementation shall ensure that each language-defined subprogram is reentrant in
> |the sense that concurrent calls on the same subprogram perform as specified, so long
> |as all parameters that could be passed by reference denote nonoverlapping objects.
> 
> Apart from that, you probably have to trust the programmer - or some tool.

Thank you, that is what I needed.  Of course, who writes the libraries could make a mistake and make some function non-reentrant, but at least the implementation is not permitted to choose a non-reentrant solution by design. 

Re: About task-safeness

[Maciej Sobczak]

On Feb 2, 10:14 pm, mockturtle <framefri...@gmail.com> wrote:

> > Well, ARM 05, A(3/2) says:
>
> > |The implementation shall ensure that each language-defined subprogram is reentrant in
> > |the sense that concurrent calls on the same subprogram perform as specified, so long
> > |as all parameters that could be passed by reference denote nonoverlapping objects.
>
> > Apart from that, you probably have to trust the programmer - or some tool.
>
> Thank you, that is what I needed.

Note that this is actually quite weak guarantee. It says that any call
that refers to the same object need not be task-safe, even if a common
sense would suggest otherwise. It was already discussed here, but two
notable examples that are worth to keep in mind are:

- two tasks printing something on stdout are *not* safe

- two tasks "only reading" values from the same container are *not*
safe

You need to provide your own protection in such cases.

--
Maciej Sobczak * http://www.inspirel.com

Re: About task-safeness

[Shark8]

>two tasks "only reading" values from the same container are *not* safe .

Interesting! That is counter-intuitive; do you have a link to an
example/explaination?

Re: About task-safeness

[J-P. Rosen]

Le 02/02/2011 21:51, mockturtle a �crit :
> Of course, one could do a review of all the packages to check for
> this type of problems, but since an Ada compiler has the good habit
> of protecting you from yourself, I searched for a way to have the
> compiler to check the task-safety of the packages used by tasks.

Or you can use AdaControl, have a look at rule Global_References.
This can check all global variables accessed from more than one task
(and it does so by following the call graph).
-- 
---------------------------------------------------------
           J-P. Rosen (rosen@adalog.fr)
Adalog a d�m�nag� / Adalog has moved:
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00

Re: About task-safeness

[Peter C. Chapin]

On Wed, 2 Feb 2011, Shark8 wrote:

>> two tasks "only reading" values from the same container are *not* safe .
>
> Interesting! That is counter-intuitive; do you have a link to an 
> example/explaination?

Actually, in the absence of documentation to the contrary, I wouldn't expect 
simultaneous reads to be safe. Some data structures get modified internally 
in response to reads. For example splay trees[1] bring the last read item to 
the root. Thus looking up an item in a splay tree entails various 
transformations on the tree that would have to be reviewed for task safety 
(or otherwise protected).

By not guaranteeing task safety during simultaneous reads, the Ada reference 
manual is allowing implementors to keep their options open. That seems fair 
to me.

Peter

[1] http://en.wikipedia.org/wiki/Splay_tree

Re: About task-safeness

[Randy Brukardt]

"mockturtle" <framefritti@gmail.com> wrote in message 
news:06ecb5ab-a9e5-4a5d-9370-6bbe137d3693@glegroupsg2000goo.googlegroups.com...
...
>(For example, a package defining some type of object could keep the number 
>of allocated
>objects, so it can give to each object a unique ID.)  If such a package was 
>used  by two
>different tasks, and the counter was not protected, obscure bugs can arise. 
>This type of
>structure maybe is not very recommended, but it happens... :-(

Note that "protection" may simply be declaring the object Atomic. Presuming 
the compiler supports that, there isn't a problem with multiple tasks 
accessing the same counter. (The main problem with small objects is 
compilers that get too helpful and optimize the unoptimizable.)

...
>Consider, for example, the Ordered_Maps package.  That package is not Pure 
>(it cannot be,
>since it would prevent the use of named access types), so how can I be 
>granted that the package
>does not have some "hidden" and unprotected state?

Hidden and truely unprotected would violate the RM, as noted by others. But 
hidden and Atomic is fine (the Janus/Ada containers will use counters this 
way to detect dangling cursors).

                              Randy.

Re: About task-safeness

[Dmitry A. Kazakov]

On Wed, 2 Feb 2011 17:40:46 -0500, Peter C. Chapin wrote:

> On Wed, 2 Feb 2011, Shark8 wrote:
> 
>>> two tasks "only reading" values from the same container are *not* safe .
>>
>> Interesting! That is counter-intuitive; do you have a link to an 
>> example/explaination?
> 
> Actually, in the absence of documentation to the contrary, I wouldn't expect 
> simultaneous reads to be safe. Some data structures get modified internally 
> in response to reads.

Which is equivalent to say that the implementation is not reentrant.

Reentrant is not an equivalent of task-safe. A protected action is not
reentrant per design. But it is task-safe because it locks. Unsafe are only
non-reentrant operations which do not lock (the effect is not atomic).

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

Re: About task-safeness

[Niklas Holsti]

Randy Brukardt wrote:
> "mockturtle" <framefritti@gmail.com> wrote in message 
> news:06ecb5ab-a9e5-4a5d-9370-6bbe137d3693@glegroupsg2000goo.googlegroups.com...
> ...
>> (For example, a package defining some type of object could keep the number 
>> of allocated
>> objects, so it can give to each object a unique ID.)  If such a package was 
>> used  by two
>> different tasks, and the counter was not protected, obscure bugs can arise. 
>> This type of
>> structure maybe is not very recommended, but it happens... :-(
> 
> Note that "protection" may simply be declaring the object Atomic. Presuming 
> the compiler supports that, there isn't a problem with multiple tasks 
> accessing the same counter.

Randy, could you be more explicit about your suggested use of Atomic? As 
I understand it, even if a counter variable N is Atomic, two tasks 
concurrently executing an assignment of the form

    N := N + 1;

can interleave their actions so that N is increased by only 1, not by 2 
as intended.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: About task-safeness

[Georg Bauhaus]

On 03.02.11 09:53, Niklas Holsti wrote:
> Randy Brukardt wrote:
>> "mockturtle" <framefritti@gmail.com> wrote in message
>> news:06ecb5ab-a9e5-4a5d-9370-6bbe137d3693@glegroupsg2000goo.googlegroups.com...
>> ...
>>> (For example, a package defining some type of object could keep the number
>>> of allocated
>>> objects, so it can give to each object a unique ID.)  If such a package was
>>> used  by two
>>> different tasks, and the counter was not protected, obscure bugs can arise.
>>> This type of
>>> structure maybe is not very recommended, but it happens... :-(
>>
>> Note that "protection" may simply be declaring the object Atomic. Presuming
>> the compiler supports that, there isn't a problem with multiple tasks
>> accessing the same counter.
> 
> Randy, could you be more explicit about your suggested use of Atomic? As I
> understand it, even if a counter variable N is Atomic, two tasks concurrently
> executing an assignment of the form
> 
>    N := N + 1;
> 
> can interleave their actions so that N is increased by only 1, not by 2 as
> intended.

When I first read about atomic counting, I thought so, too.  But then,
I noticed a new(?) Implementation Advice in the LRM that says, IIRC,
that compilers should make atomic processor ops available, including
decrement.  A neighboring paragraph is about intrinsic operations.

Re: About task-safeness

[AdaMagica]

On 3 Feb., 12:07, Georg Bauhaus <rm.dash-bauh...@futureapps.de> wrote:
> > Randy, could you be more explicit about your suggested use of Atomic? As I
> > understand it, even if a counter variable N is Atomic, two tasks concurrently
> > executing an assignment of the form
>
> >    N := N + 1;
>
> > can interleave their actions so that N is increased by only 1, not by 2 as
> > intended.
>
> When I first read about atomic counting, I thought so, too.  But then,
> I noticed a new(?) Implementation Advice in the LRM that says, IIRC,
> that compilers should make atomic processor ops available, including
> decrement.  A neighboring paragraph is about intrinsic operations.

You mean C.1(11-12):
(11) It is recommended that intrinsic subprograms be provided for
convenient access to any machine
operations that provide special capabilities or efficiency and that
are not otherwise available through the
language constructs. Examples of such instructions include:
(12) • Atomic read-modify-write operations — e.g., test and set,
compare and swap, decrement and test,
enqueue/dequeue.

But N := N + 1; is not such an operation even if N is atomic. An
implementation would have to provide something like a CAS operation.

Re: About task-safeness

[Vinzent Hoefler]

Maciej Sobczak wrote:

> On Feb 2, 10:14 pm, mockturtle <framefri...@gmail.com> wrote:
>
>> > Well, ARM 05, A(3/2) says:
>>
>> > |The implementation shall ensure that each language-defined subprogram is reentrant in
>> > |the sense that concurrent calls on the same subprogram perform as specified, so long
>> > |as all parameters that could be passed by reference denote nonoverlapping objects.
>>
>> > Apart from that, you probably have to trust the programmer - or some tool.
>>
>> Thank you, that is what I needed.
>
> Note that this is actually quite weak guarantee. It says that any call
> that refers to the same object need not be task-safe, even if a common
> sense would suggest otherwise. It was already discussed here, but two
> notable examples that are worth to keep in mind are:
>
> - two tasks printing something on stdout are *not* safe
>
> - two tasks "only reading" values from the same container are *not*
> safe

Of course not, because if you think a bit harder about it, the result is that
both calls use a "parameter that could be passed by reference" denoting the
same "non-overlapping object".


Vinzent.

-- 
You know, we're sitting on four million pounds of fuel, one nuclear weapon,
and a thing that has 270,000 moving parts built by the lowest bidder.
Makes you feel good, doesn't it?
   --  Rockhound, "Armageddon"

Re: About task-safeness

[Jeffrey Carter]

On 02/03/2011 04:22 AM, AdaMagica wrote:
>
> You mean C.1(11-12):
> (11) It is recommended that intrinsic subprograms be provided for
> convenient access to any machine
> operations that provide special capabilities or efficiency and that
> are not otherwise available through the
> language constructs. Examples of such instructions include:
> (12) � Atomic read-modify-write operations � e.g., test and set,
> compare and swap, decrement and test,
> enqueue/dequeue.
>
> But N := N + 1; is not such an operation even if N is atomic. An
> implementation would have to provide something like a CAS operation.

Those are examples of such operations, which will differ from machine to 
machine. If a machine offers an atomic increment operation, a compiler 
implementing Annex C should provide a subprogram to use it.

-- 
Jeff Carter
"How'd you like to hide the egg and gurgitate
a few saucers of mocha java?"
Never Give a Sucker an Even Break
101

Re: About task-safeness

[Randy Brukardt]

"Niklas Holsti" <niklas.holsti@tidorum.invalid> wrote in message 
news:8qv8neF9i0U1@mid.individual.net...
> Randy Brukardt wrote:
...
>> Note that "protection" may simply be declaring the object Atomic. 
>> Presuming the compiler supports that, there isn't a problem with multiple 
>> tasks accessing the same counter.
>
> Randy, could you be more explicit about your suggested use of Atomic? As I 
> understand it, even if a counter variable N is Atomic, two tasks 
> concurrently executing an assignment of the form
>
>    N := N + 1;
>
> can interleave their actions so that N is increased by only 1, not by 2 as 
> intended.

Good point. All of the examples I've used have been where one task set the 
value to some constant (like True or False), and other read it. That's safe, 
while doing both may not be.

Practically(*), however, this will be generated atomically on an x86 (at 
least on Janus/Ada): it will generate an
    Inc [N]
instruction, which I don't think can be interupted between the read and the 
write. The net effect is that the operation will be undivided on a single 
processor. (I don't really know how multicore systems might affect this; 
there may be additional locks needed here.)

(*) Note that Ada language rules might make generating this atomically 
impossible, such as if an overflow check is needed. In that case, separate 
read and write instructions might be needed. That's not a problem in the 
Janus/Ada runtime (where checks are suppressed always, mostly for size and 
speed reasons), but it might be in your code.

And of course, this is very target dependent. N := N + A; is much harder to 
generate atomically, and expressions involved atomic array components might 
be impossible.

                                   Randy.

P.S. None of this actually depends on "Atomic" in the current Janus/Ada 
compiler, as it isn't actually supported. But this optimization is done for 
all objects. In addition, Janus/Ada currently treats all writes as volatile. 
Most likely, the next version of Janus/Ada will have a full implementation 
of Atomic (it's been fully implemented in the front end for years - Isaac 
did it as part of an ACATS review contract back in the mid-90s. But I never 
implemented it in the optimizer and back-end - and that needs to be fixed.)