Ada: protected objects deadlock

Question

Let's suppose I have the following code in Ada:

test.ads

        package Test is

       type Gate; --forward declaration for mutual use

       protected type Foo is
          entry Do_Something;
          procedure UnlockGate;

          procedure Initialize(child : access Gate; me : access Foo);
       private
          Can_Do_Something : Boolean := True;
          Child_Gate : access Gate;
       end Foo;

       protected type Gate is
          entry Try_To_Do_Something;
          procedure Unlock;

          procedure SetParentFoo(parent : access Foo);
       private
          unlocked : Boolean := False;
          Parent_Foo : access Foo;
       end Gate;

       task Foo_User;

   task Gate_User;
   task Init;

   foo_inst : access Foo;
   gate_inst : access Gate;
end Test;

test.adb

    with Ada.Text_IO; use Ada.Text_IO;

package body Test is

   protected body Foo is
      entry Do_Something when Can_Do_Something is
      begin
         --Do something
         null;
      end Do_Something;

      procedure UnlockGate is
      begin
         Child_Gate.Unlock;
         --Foo_User freezes here. It will make the call to Child_Gate.Unlock but just after that it will stop
      end UnlockGate;

      procedure Initialize(child : access Gate; me : access Foo) is
      begin
         Child_Gate := child;
         Child_Gate.SetParentFoo(me);
      end Initialize;
   end Foo;

   protected body Gate is
      entry Try_To_Do_Something when unlocked is
         pragma Warnings(Off);
      begin
         --Gate_User freezes here, it enters the procedure but will not make the Do_Something call
         Parent_Foo.Do_Something;
      end Try_To_Do_Something;

      procedure Unlock is
      begin
         unlocked := True;
      end Unlock;

      procedure SetParentFoo(parent : access Foo) is
      begin
         Parent_Foo := parent;
      end SetParentFoo;
   end Gate;

   task body Init is

   begin
      foo_inst := new Foo;
      gate_inst := new Gate;
      foo_inst.Initialize(gate_inst, foo_inst);
   end Init;

   task body Gate_User is
   begin
      delay 1.0;
      Put_Line("Gate_User is trying to do something");
      gate_inst.Try_To_Do_Something;
      Put_Line("This statement will never be reached, Gate_User task freezes...");
   end Gate_User;

   task body Foo_User is
   begin 
      delay 2.0;
      Put_Line("Foo_User is unlocking the gate");
      foo_inst.UnlockGate;
      Put_Line("This statement will never be reached, Foo_User task freezes...");
   end Foo_User;

end Test;

main.adb

with Test; use Test; --This will start the tasks

procedure main is
   begin
      null; --Nothing to do here
end main;

Let me explain what is happening here. Gate and Foo "know" each other. Gate's Try_To_Do_Something entry acts as a "gateway" to Foo's Do_Something procedure. Try_To_Do_Something is locked by default, but a call to Foo's UnlockGate will unlock it and allow all waiting calls to go through and call Do_Something.

This behavior may look weird, but this is just a sample to reproduce the problem. In the real program I have a multitude of gates and the UnlockGate procedure opens some and closes others depending on its parameters. Basically a series of Gates is used to mediate access to the Do_Something procedure, depending on the internal state of Foo.

The comments in the code show where the Gate_User and Task_User tasks freeze.

What I don't understand is why. The problem is that Foo_User stops just after having called Child_Gate.Unlock and never returns from UnlockGate. Why is it stopping in the middle of a call? There aren't even any more statements in the call, why isn't it returning? Of course the Do_Something call that Gate_User is trying to make doesn't go through because Foo_User is still "inside" the protected call to UnlockGate, which I understand, but what I don't get is why that UnlockGate call doesn't return. Any ideas?

EDIT: I'm using GNAT 2014 on Kubuntu 14.04 to compile and run this.
EDIT 2: Just done further testing. This only happens on Linux! On windows it executes correctly.
EDIT 3: Result of pstack:

31779: ./main
(No symbols found in )
(No symbols found in /lib/i386-linux-gnu/libc.so.6)
(No symbols found in /lib/ld-linux.so.2)
crawl: Input/output error
Error tracing through process 31779

Answer 1

EDIT: I've looked into this more closely (after realizing that Can_Do_Something is always true) and I think I've figured out the real cause of the problem.

RM 9.5.1(3) discusses the semantics of a protected subprogram call:

If the call is an internal call (see 9.5), the body of the subprogram is executed as for a normal subprogram call. If the call is an external call, then the body of the subprogram is executed as part of a new protected action on the target protected object...

An external call is basically one that uses an object, as opposed to a protected subprogram in a protected body merely calling another subprogram in the same body, which is an internal call. What the above quote means is that if a protected subprogram in PObj1 calls a protected subprogram in PObj2, which then calls a protected subprogram in PObj1, you will get deadlock. Whoever called the first subprogram started a protected action on PObj1. When PObj2 then tries to call a subprogram in PObj1, this is an external call and thus it tries to start a new protected action, which it cannot do since there is still a protected action taking place on PObj1. The consequence of this is that your code, which relies on two protected objects calling each other as part of the same protected action, isn't going to work. (It could be a compiler bug that the program works on Windows.)

In addition, your code is erroneous because a protected entry body (Try_To_Do_Something) is making a protected entry call (Parent_Foo.Do_Something). A protected action should not call a potentially blocking operation (RM 9.5.1(8-16)), and an entry call is a potentially blocking operation. The intended use of protected types is that "protected actions" should execute in a relatively small amount of time; they should not wait for anything. So you shouldn't do that (even though, the way the code is now written, the entry call will never block).

RM 9.5.1 is here.

Answer 2

Ok. I think I've got it. This is what happens:

• Gate_User blocks on Foo.Try_To_Do_Something (waiting for unlocked)
• Foo_User calls Foo.UnlockGate and takes the Foo mutex.
• Foo_User calls Gate.Unlock and takes the Gate mutex.
• Foo_User set unlocked to True
• Foo_User (before releasing the Gate mutex) evaluates the barrier condition of Try_To_Do_Something.
• Foo_User calls Try_To_Do_Something as if it was Gate_User. (it is allowed to do this before it returns and releases the Gate mutex (and then the Foo mutex), as an optimization to reduce tasks switches, if a barrier condition becomes true and there are tasks in the queue for the entry)
• Foo_User blocks on Foo.Do_Something since it has already taken the Foo mutex.

Answer 3

It's always erroneous to make a potentially blocking call from a protected body. Maybe change to tasks, or use a monitor or semaphore (which can be implemented as a protected type) inside procedure calls? I like the Booch 95 monitor and lock.