Automatic Fine-Grain Locking using Shape Properties

We present a technique for automatically adding fine-grain
locking to an abstract data type that is implemented using a
dynamic forest —i.e., the data structures may be mutated,
even to the point of violating forestness temporarily during
the execution of a method of the ADT. Our automatic
technique is based on Domination Locking, a novel locking
protocol. Domination locking is designed specifically
for software concurrency control, and in particular is designed
for object-oriented software with destructive pointer
updates. Domination locking is a strict generalization of existing
locking protocols for dynamically changing graphs.
We show our technique can successfully add fine-grain
locking to libraries where manually performing locking is
extremely challenging. We show that automatic fine-grain
locking is more efficient than coarse-grain locking, and obtains
similar performance to hand-crafted fine-grain locking.