Re: finegrain locking in LDBM (relates to dissection of search latency)

[Mark Adamson <adamson@andrew.cmu.edu>]

On Thu, 15 Nov 2001, Kurt D. Zeilenga wrote:

> What is the lock hierarchy used to prevent deadlock?
>


The hierarchy is pretty flat.

The add_entry function can hold a lock on an entry it just created then
aquire the 3 cache locks, one at a time, to add the entry to the cache.

The find_entry functions aquire and release one of the 2 AVL locks to
find the entry. They then will lock the entry then lock the LRU to reorder
it and release the LRU lock.


return_entry  starts off holding an entry's lock.   If it is going to
remove an entry from the cache, it will mark the entry unusable, release
the Entry lock, then go through the 3 cache locks one at a time, removing
the entry from the cache. (If find_entry finds the Entry while
return_entry is busy deleting the Entry, find_entry sees it is marked
unusable and gives up on it)

So in terms of hierarchy, threads aquire an Entry's lock before reaching
for one of the 3 cache locks, they never hold one of the 3 cache locks
then try to aquire an Entry's lock, and they never hold 2 cache locks at
the same time.


Thanks for asking.


  -Mark Adamson