Preemptive Deadlock Detection - Part 3

Part 3 – Advanced Safety

---

This is the third part of a series addressing how to make an existing or new project completely deadlock free. This project primarily deals with C# code, but these techniques can also be implemented in any language. If you haven't read the earlier parts, please read them first:

• Part 1 - Introduction to the basics
• Part 2 - Self ordering code
• Part 3 – Advanced Safety

This module begins where the previous module ended. You can download a full copy of the completed project up to this point from my shared skydrive here: Sky Drive, for the starting point of this module, download Phase2.zip.

Ensuring single use IDs

Every time an OrderedLock object is created, it’s important that the constructor is passed a unique value from the ID enumeration. Failure to do this will result in the framework thinking these two different OrderedLock object are the same. This will result in the framework incorrectly mapping the relationships, which could lead to false positives. To prevent this, we add a list of where each ID was used in the source code. If any line of source code uses the same ID that another line of source code uses, we report an error. This should only be done in a DEBUG executable, since this is extremely easy to detect with 100% accuracy. So long as you run a DEBUG executable before you release a non-debug executable, there is no need to check again. The code changes start with adding a static Dictionary that maps ID objects to StackFrame objects. This will hold the source code location where each object was created. We put in the static members region:

file Ostrowski\Utilities\OrderedLock.cs

132.       #region Static Members
133.       // If this is ever set to true, don't write out the new dependency chart on exit
134.       private static bool circularDependencyFound = false;
135.       // This is used to report single instances of errors detected to a log file:
136.       private static UniqueEntryReporter uniqueEntryReporter = new UniqueEntryReporter(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments), "Deadlocks.log");
137. #if DEBUG
138.       // Used to ensure we only use each ID once across the entrire project:
139.       private static Dictionary<ID, StackFrame> idToCreationStackFrame = new Dictionary<ID, StackFrame>();
140. #endif // DEBUG
141.       #endregion
142.  

Then in the common constructor of OrderedLock, in #if DEBUG blocks, we make the check, and raise a Debug.Assert if the ID has already been used:

file Ostrowski\Utilities\OrderedLock.cs

79.       public OrderedLock(ID id, object objectToLock)
80.       {
81.          this.Id = id;
82.          this.ObjectToLock = objectToLock;
83. #if DEBUG
84.          // This section (delimited by the #if DEBUG section) is used to verify
85.          // that two different OrderedLock objects don't use the same ID.
86.          StackTrace stackTrace = new StackTrace(true/*fNeedFileInfo*/);
87.          StackFrame[] stackFrames = stackTrace.GetFrames();
88.          String thisFileName = null;
89.          StackFrame creationStackFrame = null;
90.          // Find the closest StackFrame that is not within this class.
91.          // This is the place where this object was created.
92.          // We record it so we can print it in ToString(), and we also use
93.          // it to make sure no two DIFFERENT objects
94.          // use the same ID (see next comment section below).
95.          foreach (StackFrame frame in stackFrames)
96.          {
97.             if (thisFileName == null)
98.                thisFileName = frame.GetFileName();
99.             else if (thisFileName.Equals(frame.GetFileName()))
100.                continue;
101.             else
102.             {
103.                creationStackFrame = frame;
104.                break;
105.             }
106.          }
107.          // This ensures that no two instances of an OrderedLock object use the same ID.
108.          // It is OK for two separate instances of a single class to create their own
109.          // instance of an OrderedLock, however, it is not permitted for two separate but
110.          // different instances of an OrderedLock to use the same ID.
111.          // We test this by looking at the StackFrame that created the object.
112.          // Each place in the source code can only use any given ID once.
113.          if (idToCreationStackFrame.ContainsKey(this.Id) &&
114.             !CallStack.SameStackFrame(idToCreationStackFrame[this.Id], creationStackFrame))
115.          {
116.             String error = "OrderedLock with name of '" + this.Id.ToString() + "' used twice! " +
117.                                  "\r\n first loc:" + idToCreationStackFrame[this.Id] +
118.                                  "\r\nsecond loc:" + creationStackFrame;
119.             Log.LogError(error);
120.             Debug.Assert(false, error);
121.             // fall through to re-write the new location. This can happen during
122.             // run-time modification of the code, and we want it auto-correct itself.
123.          }
124.          idToCreationStackFrame[this.Id] = creationStackFrame;
125. #endif // DEBUG
126.       }

Now if we cut and paste an OrderedLock object, but forget to create a new ID for use in the constructor, the first time we execute the code in a DEBUG build, we will hit a Debug.Assert.

Peer Locking Authority

One problem common in complex system is that there are times when you want to lock the protection lock of obj A and obj B at the same time, even when they are of the same type. Consider the case of a Contact class that contains a Name and a PhoneNumber field:

file Ostrowski\ContactList\Contact.cs

1. using System;
2. using Ostrowski.Utilities;
3.  
4. namespace Ostrowski.ContactList
5. {
6.    class Contact
7.    {
8.       public String Name { get; private set; }
9.       public String PhoneNumber { get; private set; }
10.  
11.       readonly OrderedLock lockThis = new OrderedLock(OrderedLock.ID.Ostrowski_Contact_lockThis);
12.  
13.       public Contact(String name, String phoneNumber)
14.       {
15.          this.Name = name;
16.          this.PhoneNumber = phoneNumber;
17.       }
18.  
19.       public void SetContact(String newName, String newPhoneNumber)
20.       {
21.          using (this.lockThis.Lock())
22.          {
23.             this.Name = newName;
24.             this.PhoneNumber = newPhoneNumber;
25.          }
26.       }
27.  
28.       public bool Equals(Contact other)
29.       {
30.          using (this.lockThis.Lock())
31.          {
32.             if (this.Name != other.Name) return false;
33.             if (this.PhoneNumber != other.PhoneNumber) return false;
34.          }
35.          return true;
36.       }
37.    }
38. }

And we add the new element to the OrderedLock.ID enumeration:

file Ostrowski\Utilities\OrderedLock.cs

23.       public enum ID
24.       {
25.          Ostrowski_Program_resource1,
26.          Ostrowski_Program_resource2,
27.          Ostrowski_Program_signalLock,
28.          Ostrowski_Contact_lockThis,
29.       }

At first glance, this seems like decent code. We have locks in place to ensure that anytime we set the Name and PhoneNumber fields, we change them both at the same time.  However, closer inspection of the Equals method reveals that we are not as atomic as it should be: In this method, we are accessing the Name and PhoneNumber properties of the other Contact without locking that object's OrderedLock. Granted, this is a contrived example, in the real world it probably wouldn't matter if someone could change the name of contact while we are comparing another contact to it, but more complicated cases do exist where it's important to lock both objects within a comparison function To be safest, we should rewrite the Equals method as such:

file Ostrowski\ContactList\Contact.cs

28.       public bool Equals(Contact other)
29.       {
30.          using (this.lockThis.Lock())
31.          {
32.             using (other.lockThis.Lock())
33.             {
34.                if (this.Name != other.Name) return false;
35.                if (this.PhoneNumber != other.PhoneNumber) return false;
36.             }
37.          }
38.          return true;
39.       }

Now anytime we do the comparison, we can be sure that the other object won’t be changing as we are comparing it. However, there is a problem: Since each of the two Lock() calls are actually locking different instances of OrderedLock object that have exactly identical orders, we are violating our rule of only locking object of lower order. The chances of this type of deadlock are very rare, but it’s a solvable situation, so we address it. The deadlock only occurs if we have two objects A and B, and while one thread is calling A.Equals(B), another thread is calling B.Equals(A). In this deadlock, both threads could become stuck waiting on their inner Lock() call. To show that our framework can catch this, we add this to the end of the Main method in Program.cs:

file Program.cs

35.          ContactList.Contact contactA = new ContactList.Contact("A", "123-4567");
36.          ContactList.Contact contactB = new ContactList.Contact("B", "234-5678");
37.          contactA.Equals(contactB);
38.          
39.          // If any lock orderings changed during execution,
40.          // re-write the new order to the designated file:
41.          OrderedLock.DumpDependencyCode();
42.       }

Now when we execute the program, we see the following error, as expected:

acquired resource1 from main thread
acquired resource2 from worker thread
acquired resource1 from worker thread
acquired resource2 from main thread
Error: Possible Deadlock condition found:
 Circular dependency found:
 Lock held:OrderedLock: Ostrowski_Contact_lockThis, Info:
 Lock attempted:OrderedLock: Ostrowski_Contact_lockThis, Info:

                Ostrowski.ContactList.Contact::Boolean Equals(Ostrowski.ContactL
ist.Contact)  C:\Users\Paul\My Document\Locking App\Phase3\Ostrowski\Con
tactList\Contact.cs(32)
                Ostrowski.Program::Void Main(System.String[])  C:\Users\Paul\My
Document\Locking App\Phase3\Program.cs(37)
                ...System level method(s)...

The only way to solve this is to require a higher-order lock be locked first. This means that only thread at a time can acquire the first or second lock, thus preventing the deadlock condition. I call this lock a peer locking authority. It’s vital to realize that the peer locking authority lock must be the same instance called from each thread, and not an instance member of the object. Usually this is achieved by a static member of the class, but could be done other ways as well. To implement the peer locking authority, we declare the peer locking authority of a class when we construct the OrderedLock object, and then when we encounter a lock order violation, where both locks involved in the order violation have the same instance of a peer locking authority, and that single lock is held by the calling thread, we can safely ignore the error condition:

File Ostrowski\Utilities\OrderedLock.cs:

75.       public object ObjectToLock { get; private set; }
76.       // If this is set, it allows for order violations to occur, provided the peer locking authority lock is locked.
77.       public OrderedLock PeerLockingAuthority { get; private set; }
78.       public OrderedLock(ID id)
79.          : this(id, new object(), null/*peerLockingAuthority*/)
80.       {
81.       }
82.       public OrderedLock(ID id, OrderedLock peerLockingAuthority)
83.          : this(id, new object(), peerLockingAuthority)
84.       {
85.       }
86.       public OrderedLock(ID id, object objectToLock)
87.          : this(id, objectToLock, null/*peerLockingAuthority*/)
88.       {
89.       }
90.       public OrderedLock(ID id, object objectToLock, OrderedLock peerLockingAuthority)
91.       {
92.          this.Id = id;
93.          this.ObjectToLock = objectToLock;
94.          this.PeerLockingAuthority = peerLockingAuthority;
95. #if DEBUG

 ...

Now in our TestAcquisition method, we check for the presence of this new lock:

File Ostrowski\Utilities\OrderedLock.cs:

155.      private void TestAcquisition()
156.       {
157.          List<OrderedLock> listOfOwnedObjects = ThreadOwnedLocks.CopyList();
158.          // Check if this lock is already held.
159.          // If so, there is no need to test the order against other locks
160.          if (listOfOwnedObjects.Contains(this))
161.             return;
162.  
163.          // Iterate across each lock already held, and make sure we know
164.          // about this parent-child relationship:
165.          foreach (OrderedLock heldOrderedLock in listOfOwnedObjects)
166.          {
167.             // RegisterParentChildRelationship will return false if an order violation is identified
168.             if (!ParentChildOrderingOnID.RegisterParentChildRelationship(
169.                                                   heldOrderedLock.Id, this.Id))
170.             {
171.                // An order violation has been found, but it may be OK if a common
172.                // peer locking authority is held by both locks:
173.                bool peerLockingAuthorityHeld = false;
174.                if ((heldOrderedLock.PeerLockingAuthority != null) &&
175.                      (object.ReferenceEquals(heldOrderedLock.PeerLockingAuthority,
176.                                              this.PeerLockingAuthority)))
177.                {
178.                   // A peer locking authority can permit objects of the same order to be
179.                   // locked. It does not grant the permission to lock in reverse order!
180.                   if (ParentChildOrderingOnID.GetMinimumOrder(heldOrderedLock.Id) ==
181.                       ParentChildOrderingOnID.GetMinimumOrder(this.Id))
182.                   {
183.                      // If we are holding the lock on the PeerLockingAuthority for
184.                      // both of these object, this is not an error.
185.                      foreach (OrderedLock heldLock in listOfOwnedObjects)
186.                      {
187.                         if (object.ReferenceEquals(heldLock, this.PeerLockingAuthority))
188.                         {
189.                            peerLockingAuthorityHeld = true;
190.                            break;
191.                         }
192.                      }
193.                   }
194.                }
195.  
196.                if (!peerLockingAuthorityHeld)
197.                {
198.                   // Problem found!
199.                   OrderedLock.circularDependencyFound = true;
200.                   OrderedLock.ReportPossibleDeadlockCondition(
201.                                        "Circular dependency found", heldOrderedLock,
202.                                      this, 2/*stackFramesToIgnoreInErrorReport*/);
203.                }
204.             }
205.          }
206.       }

Now we add the new static OrderedLock to the Contact class, and lock that lock before we lock either member lock in the Equals method. As I mentioned before, this must be declare static, so that each instance of a Contact class will use the same instance of the peer locking authority when it constructs its own member lockThis OrderedLock:

File Ostrowski\ContactList\Contact.cs:

11.       static readonly OrderedLock lockThisPeerLockingAuth = new OrderedLock(OrderedLock.ID.Ostrowski_Contact_lockThisPeerLockingAuth);
12.       readonly OrderedLock lockThis = new OrderedLock(OrderedLock.ID.Ostrowski_Contact_lockThis, Contact.lockThisPeerLockingAuth);

 ...

29.       public bool Equals(Contact other)
30.       {
31.          using (Contact.lockThisPeerLockingAuth.Lock())
32.          {
33.             using (this.lockThis.Lock())
34.             {
35.                using (other.lockThis.Lock())
36.                {
37.                   if (this.Name != other.Name) return false;
38.                   if (this.PhoneNumber != other.PhoneNumber) return false;
39.                }
40.             }
41.          }
42.          return true;
43.       }

And of course we must add the new enum value in OrderedLock.ID:

File Ostrowski\Utilities\OrderedLock.cs:

23.       public enum ID
24.       {
25.          Ostrowski_Program_resource1,
26.          Ostrowski_Program_resource2,
27.          Ostrowski_Program_signalLock,
28.          Ostrowski_Contact_lockThis,
29.          Ostrowski_Contact_lockThisPeerLockingAuth,
30.       }

Now we can run the application, and see that it no longer reports an error. Furthermore, we should see after the execution completed that the source code to OrderedLock.cs has been modified to include the newly defined relationships between the OrderedLock objects in the Contact class.
At this point, the framework is pretty much complete. The next part of this series will focus on improved diagnostics and debug options. Stay tuned for the upcoming releases.
You can download a full copy of the completed project from my shared skydrive here: Sky Drive, for this module, download Phase3.zip.

---

Here are links to each part. I will update this list as modules become available:

• Part 1 - Introduction to the basics
• Part 2 - Self ordering code
• Part 3 – Advanced Safety