Assignment with Adjust and Task Safety

Assignment with Adjust and Task Safety

[Jeremiah]

I've been playing around with shared/safe/smart pointer representations in Ada and have been trying to wrap my head around how task safety works with Adjustment.  I definitely get the concept of Atomic increment/decrement in order to allow to shared pointers in two separate task to work safely, but when two separate tasks work on the same shared pointer, I am having trouble using atomic increment/decrement to prevent the following issue:

Initial conditions:
1.  Task_A and Task_B both have access to Shared_Pointer_A
2.  Shared_Pointer_A currently is the only reference to Object_A (count = 1)
3.  Shared_Pointer_B currently points to a different Object_B (count = 1 or whatever).  Additionally, Shared_Pointer_B is only used by Task_B.
4.  Shared_Ponter_C is currently null and only used by Task_A

If I start an assignment in Task_A of Shared_Pointer_C := Shared_Pointer_A, but get interrupted by Task_B in between when the contents of Shared_Pointer_A are copied into Shared_Pointer_C and when Shared_Pointer_C is adjusted, if Task_B then does the assignment Shared_Pointer_A := Shared_Pointer_B, how do I prevent Shared_Pointer_C from working with a reference that is finalized by Task_B's assignment process?

An illustration:
Task_A:
Finalize(Shared_Pointer_C);
Copy Shared_Pointer_A into Shared_Pointer_C

Task_A is yielded and Task B Starts

Task_B:
Finalize(Shared_Pointer_A);  -- uh oh??
Copy Shared_Pointer_B into Shared_Pointer_A
Adjust Shared_Pointer_A
do some Task_B stuff until Task_B yields and Task_A starts up

Task_A:
Adjust(Shared_Pointer_A);  -- Contents invalid???


I don't think atomic increment/decrement will fix this as the task switch happens outside of both Adjust and Finalize.  Is there some other way to prevent this?  I know at the higher level I can wrap Shared_Pointer_A into a protected type to ensure the assignments and reads from it are protected, but that is something normally out of the scope of the Shared_Pointer_Type.

I've been looking at other implementations, but haven't found how this instance is protected against.  It may not be outside of forcing assignment through a protected type, but wanted to check.

Note that I am not accounting for the temporary objects for brevity in the example.  Additionally, this may just be bad design all around, but I am trying to look at the mechanics behind this as well and if it is even possible to do this safely.

Thank you.

Re: Assignment with Adjust and Task Safety

[Shark8]

Well, one solution is to forgo assignment, making them limited, and providing all the subprograms to manipulate them in the package that declares them... if you want to be extra-sure then in the body declare a protected object that does the actual manipulation (this should prevent it from being interrupted) and make the bodies of the publicly accessible subprograms renamings of the protected-object's subprograms.

Re: Assignment with Adjust and Task Safety

[Dmitry A. Kazakov]

On 2016-03-22 15:36, Jeremiah wrote:
> I've been playing around with shared/safe/smart pointer
> representations in Ada and have been trying to wrap my head around how
> task safety works with Adjustment. I definitely get the concept of
> Atomic increment/decrement in order to allow to shared pointers in two
> separate task to work safely, but when two separate tasks work on the
> same shared pointer, I am having trouble using atomic
> increment/decrement to prevent the following issue:
>
> Initial conditions:
> 1.  Task_A and Task_B both have access to Shared_Pointer_A
> 2.  Shared_Pointer_A currently is the only reference to Object_A (count = 1)
> 3. Shared_Pointer_B currently points to a different Object_B (count
> =  1 or whatever). Additionally, Shared_Pointer_B is only used by Task_B.
> 4.  Shared_Ponter_C is currently null and only used by Task_A
>
> If I start an assignment in Task_A of Shared_Pointer_C :=
> Shared_Pointer_A, but get interrupted by Task_B in between when the
> contents of Shared_Pointer_A are copied into Shared_Pointer_C and when
> Shared_Pointer_C is adjusted, if Task_B then does the assignment
> Shared_Pointer_A := Shared_Pointer_B, how do I prevent Shared_Pointer_C
>from working with a reference that is finalized by Task_B's assignment
> process?

You cannot share mutable smart pointer. There is no way to keep it 
consistent.

> I don't think atomic increment/decrement will fix this as the task
> switch happens outside of both Adjust and Finalize. Is there some other
> way to prevent this? I know at the higher level I can wrap
> Shared_Pointer_A into a protected type to ensure the assignments and
> reads from it are protected, but that is something normally out of the
> scope of the Shared_Pointer_Type.

You add a mutex, global or of a narrower scope, and take it in Adjust 
and Finalize before doing anything else with the pointer.

I don't do this in my implementation of smart pointers because I 
consider it not worth the overhead of two protected actions for being 
protected against concurrent access to the pointer. [*]

The rationale is this. Smart pointers are unlikely shared. Normally they 
are kept in containers that are not shared or else are protected by a 
mutex, which eliminates the problem.

Yes, it is a potentially a very dangerous problem. It would be great if 
a tool like AdaControl could detect it. I hope J-P will comment on this.

-------------------
* You cannot wrap a protected object by the smart pointer because that 
would mean calling target object Finalization on the context of a 
protected operation, which is highly undesirable.

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

Re: Assignment with Adjust and Task Safety

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:ncs46a$qo2$1@gioia.aioe.org...
...
> You add a mutex, global or of a narrower scope, and take it in Adjust and 
> Finalize before doing anything else with the pointer.
>
> I don't do this in my implementation of smart pointers because I consider 
> it not worth the overhead of two protected actions for being protected 
> against concurrent access to the pointer. [*]
>
> The rationale is this. Smart pointers are unlikely shared. Normally they 
> are kept in containers that are not shared or else are protected by a 
> mutex, which eliminates the problem.

Right. And notice that this performance tradeoff and rationale applies to 
virtually every library that one could imagine. For instance, it applies to 
the entire standard Ada runtime. Unless a library advertises that it works 
with task shared variables (like Ada.Containers.Unbounded_Priority_Queues), 
one should always assume it does not work without protection. (Usually, a 
"task-safe" library just ensures that *different* variables can be operated 
on by different tasks - even that can be hard to support, as in Claw.)

For future Ada, we're looking at ways to decrease the danger from shared 
variables, especially in the context of parallel loops and the like. It is 
probably the biggest danger in Ada, given that it cannot be tested for 
(given that very specific conditions have to happen for there to be a 
failure, the vast majority of the time there is no problem) and that the 
effects of violating 9.10 can be catostrophic.

                                 Randy.

Re: Assignment with Adjust and Task Safety

[rieachus]

On Tuesday, March 22, 2016 at 10:37:07 AM UTC-4, Jeremiah wrote:
 
> Note that I am not accounting for the temporary objects for brevity in the example.  Additionally, this may just be bad design all around, but I am trying to look at the mechanics behind this as well and if it is even possible to do this safely.

Very bad juju.  It is reasonable to write (Ada) code that has an access value declared constant, even if it is in a nested scope and changes value every time the scope enclosing the variable is called.  Having multiple tasks assigning to the same (global) variable is usually wrong, and as Randy pointed out, is very difficult to prove correct, even if it is...  Having a rule that any variable set by more than one task will be protected saves you weeks of debugging.

Re: Assignment with Adjust and Task Safety

[Jeremiah]

On Tuesday, March 22, 2016 at 2:50:56 PM UTC-4, Dmitry A. Kazakov wrote:
> On 2016-03-22 15:36, Jeremiah wrote:
> > I don't think atomic increment/decrement will fix this as the task
> > switch happens outside of both Adjust and Finalize. Is there some other
> > way to prevent this? I know at the higher level I can wrap
> > Shared_Pointer_A into a protected type to ensure the assignments and
> > reads from it are protected, but that is something normally out of the
> > scope of the Shared_Pointer_Type.
> 
> You add a mutex, global or of a narrower scope, and take it in Adjust 
> and Finalize before doing anything else with the pointer.

Sorry for the late reply, I have been sick.  Thank you (and all others) for the responses.  For those who were concerned, don't worry I wasn't planning on exposing smart pointers directly like that nor using them globally.  I was just trying to make sure I understood the mechanics (I feel like it is important to understand how things work even if they aren't the best way of doing something).  

Re: Assignment with Adjust and Task Safety

[J-P. Rosen]

Le 22/03/2016 19:50, Dmitry A. Kazakov a écrit :
> Yes, it is a potentially a very dangerous problem. It would be great if
> a tool like AdaControl could detect it. I hope J-P will comment on this.

Something like this? (Excerpt form AdaControl User Guide):

5.21 Global_References

This rule controls accesses to global elements that may be subject to
race conditions, or otherwise shared.

5.21.1 Syntax

<control_kind> global_references (<subrule> {, <root>});
<subrule> ::= all | read | written | multiple | multiple_non_atomic
<root>    ::=  <entity> | function | procedure | task | protected

5.21.2 Action

This rule controls access to global variables from several entities (the
roots). The <entity> must be subprograms, task types, single task
objects, protected types, or single protected objects. As usual, the
whole syntax for entities is allowed for <entity>. See Specifying an Ada
entity name. The special keywords function, procedure, task, and
protected are used to refer to all functions, procedures, tasks, and
protected entities, respectively.

The <subrule> determines the kind of references that are controlled. If
it is all, all references to global elements from the indicated entities
are reported. If <subrule> is read or written, only read (respectively
write) accesses are reported. If <subrule> is multiple, only global
elements that are accessed by more than one of the indicated entities
(i.e. shared elements) are reported. Note however that if a reference is
found from a task type or protected type, it is always reported, since
there are potentially several objects of the same type. If <subrule> is
multiple_non_atomic, references reported are the same as with multiple,
except that global variables that are atomic or atomic_components and
written from at most one of the indicated entities are not reported.
Note that this latter case corresponds to a safe reader/writer use of
atomic variables.

This rule follows the call graph, and therefore finds references from
subprogram and protected calls made (directly or indirectly) from the
indicated entities. However, calls to subprograms from the Ada standard
library are not followed.



-- 
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
http://www.adalog.fr