Re: Safety of unprotected concurrent operations on constant objects

[Brad Moore <brad.moore@shaw.ca>]

On 06/05/2014 2:11 AM, Dmitry A. Kazakov wrote:
> On Tue, 06 May 2014 00:00:40 -0600, Brad Moore wrote:
>
>> On 05/05/2014 10:36 AM, Dmitry A. Kazakov wrote:
>>> On Mon, 05 May 2014 09:11:05 -0600, Brad Moore wrote:
>>>
>>>> Eg. For Ada.Containers.Vectors...
>>>>
>>>> type Vector is tagged private
>>>>       with
>>>>          Constant_Indexing => Constant_Reference,
>>>>          Variable_Indexing => Reference,
>>>>          Default_Iterator  => Iterate,
>>>>          Iterator_Element  => Element_Type,
>>>>          Task_Safe         => False;
>>>>
>>>> Then programmers could apply the aspect to their own abstractions, which
>>>> better defines the contract of the subprogram or type.
>>>
>>> Task safety is not a type property. Even for a tagged type an unsafe
>>> operation can be defined later on. For non-tagged types it is even less
>>> clear which operations must be safe and which not.
>>>
>>> Furthermore, task-safety cannot be inherited or composed. At least not
>>> without massive overhead to prevent deadlocking when two safe types meet as
>>> mutable parameters of a safe subprogram.
>>
>> I agree that such a property is not likely inheritable or composable,
>> and I don't think we'd want it to be.  I think conceivably it could
>> apply to a type, however. It may be that such an aspect could only be
>> applicable to tagged types, and only would apply to the primitive
>> subprograms of that type. The aspect, if true would become false for any
>> derivations of that type, unless those derived types also explicitly set
>> the aspect to True.
>
> If you limit it to primitive operations then much simpler to do this:
>
>     type My_Container is tagged ...; -- All operations are unsafe
>
>     type My_Safe_Container is protected new My_Container with null record;

There's quite a difference from what you propose and what I was 
suggesting. In a nutshell, your idea is to *prescribe* an implementation 
(by wrapping an existing implementation in mutexes, whereas my wish is 
to be better able to *describe* an implementation.
There are lots of ways to provide a task safe implementation, and lots 
of different flavours of task-safe it seems.

Also, the main driver behind what I was suggesting was not to apply the 
aspect to a type, but rather to apply it to a subprogram specification. 
Any subprogram specification, whether its a primitive of a tagged type 
or not.

I only suggested applying the aspect to the primitives of a tagged type, 
as an extension to the idea, as a shorthand for putting the same aspect 
on every primitive subprogram. That part of the idea could be dropped if 
it is too problematic. When the aspect is applied to a type rather than 
a subprogram, I suspect that it would be problematic to apply to 
non-tagged types. If you imagine a function that takes a parameter of a 
task safe type, and another of a non-task safe type type, would the 
function be task safe or not? It seems
clearer that the aspect could work on a tagged type, and only apply to 
the primitives of the tagged type.

As a better example of my main concern, consider the following function.

     type Foo_Range is range 1 .. 1000;

     function Foo (X : Foo_Range) return Integer;

Looking at this, can someone tell me if the function is task-safe or 
not? Who knows? The function might internally use X to update some 
unprotected global statistic variable recording the max, min, and 
average values of all calls for the value of X.

Calling Foo with any combination of arguments concurrently for such a 
case would be dangerous, regardless the values of X.

Now consider that Foo instead uses X as an index to update the value in
some global unprotected array.

In this case, calling Foo from multiple tasks is task-safe, so long as 
two tasks do not call Foo concurrently with the same values of X.

Finally, the function may be task-safe, declaring any state on the stack 
without updating any global variables.

Whether or not such a function can be called concurrently is a pretty 
basic question, but Ada currently doesn't help the reader here.

If you are quite lucky, the programmer might have specified this
in the comments associated with the function. If you are unlucky, the 
programmer didn't later modify the implementation to become task 
un-safe, but neglected to update the comment.

Now that Ada has the new contract capabilities in Ada 2012, it seems 
like a large hole that there is no way to specify the task safety in the 
contract as well, so I am wondering about what can be done to improve 
that situation.

In response to your protected new suggestion. I think there is an idea 
there that could be explored, but I suspect there could be significant 
difficulties in having such an auto-generated protection scheme added to 
Ada. When it comes to task-safety, one size does not fit all.

For example, someone interested in processing a Vector container in 
parallel would likely not want to use such a feature, because it applies 
a mutex to every access to the container, when a much more efficient 
implementation would break the index range into chunks, and
a group of worker tasks could process each chunk of the array without 
any synchronization.

In other cases, moving from a single task design to a multiple task 
design changes the design. A producer/consumer type of usage for a 
bounded container would likely want blocking introduced to calls when 
the container is full, or empty. Simply putting a mutex around all the 
calls is not the best design in that case.

A worry I'd have is that such a feature might encourage programmers to 
become lazy and start writing poorer abstractions in lieu of taking the 
time to write a better one, in respect to functionality, readability, 
safety, etc.

>
> When inherited from, the compiler would override each primitive operation
> and wrap it with a reentrant mutex taken. When an operation gets overridden
> its new body is wrapped. Calling operation within a protected action would
> be bounded error. At least the compiler would be able to maintain mutexes
> of such objects, e.g. order them to prevent deadlocks.
>
> [Better of course, would be to have a decent delegation support]
>
>>> And, just how this contract is supposed to be verified?
>>
>> I see it more as a contract or promise made by the implementer to the
>> users of that subprogram that concurrent calls to the subprogram will
>> work.
>
> You can use this contract no more you can verify it. Because the compiler
> does not know if a call is concurrent or not.
>
>> At this point, I have doubts that the compiler could 100% guarantee that
>> a subprogram call is task safe, but there are likely rules and
>> restrictions that could be applied that would allow the compiler to
>> catch many problems.
>>
>> In particular, the aspect could restrict the associated subprogram to
>> disallow:
>>
>> (1) Calls on other non-protected subprograms that are not Pure or
>>       Task_Safe;
>
> But calling a task-safe subprogram from another task-safe subprogram were a
> much bigger problem than calling a non-safe subprogram. Protected
> operations specifically forbid to do exactly this.

That's not correct. Protected procedure's and protected functions are 
not potentially blocking. A protected procedure of one PO can call 
another protected procedure of another PO.

You could call another
> task-safe operation only on the same object and only if the implementation
> deploys reentrant locking.



>
> The rules you propose actually are good only for lock-free concurrency.

There's million's of simple functions and procedures that do not involve 
any locking. Integer "+" for example, is completely task safe.

> Unfortunately only few things can be done lock-free, and most types of
> containers certainly not.
>

Containers maybe not in general, but a constant container object without 
tamper checks could easily be made to be task safe, for functions that 
query the container, as per the original OP's request.

Regards, Brad