m4_comment([$Id: deaddbg.so,v 10.5 2005/12/02 17:27:50 alanb Exp $])m4_ref_title(Locking Subsystem,    Deadlock debugging,, lock/timeout, lock/page)m4_p([dnlAn occasional debugging problem in m4_db applications is unresolvabledeadlock.  The output of the m4_option(Co) flags of the m4_ref(db_stat)utility can be used to detect and debug these problems.  The followingis a typical example of the output of this utility:])m4_indent([dnlLocks grouped by objectLocker    Mode    Count   Status      ----------- Object ----------       1  READ         1  HELD        a.db                handle   080000004  WRITE        1  HELD        a.db                page     3])m4_p([dnlIn this example, we have opened a database and stored a single key/datapair in it.  Because we have a database handle open, we have a read lockon that database handle.  The database handle lock is the read locklabeled m4_italic(handle).  (We can normally ignore handle locks forthe purposes of database debugging, as they will only conflict withother handle operations, for example, an attempt to remove the databasewill block because we are holding the handle locked, but reading andwriting the database will not conflict with the handle lock.)])m4_p([dnlIt is important to note that locker IDs are 32-bit unsigned integers,and are divided into two name spaces.  Locker IDs with the high bit set(that is, values 80000000 or higher), are locker IDs associated withtransactions.  Locker IDs without the high bit set are locker IDs thatare not associated with a transaction.  Locker IDs associated withtransactions map one-to-one with the transaction, that is, a transactionnever has more than a single locker ID, and all of the locks acquiredby the transaction will be acquired on behalf of the same locker ID.])m4_p([dnlWe also hold a write lock on the database page where we stored the newkey/data pair.  The page lock is labeled m4_italic(page) and is on pagenumber 3.  If we were to put an additional key/data pair in thedatabase, we would see the following output:])m4_indent([dnlLocks grouped by objectLocker    Mode    Count   Status      ----------- Object ----------80000004  WRITE        2  HELD        a.db                page     3       1  READ         1  HELD        a.db                handle   0])m4_p([dnlThat is, we have acquired a second reference count to page number 3, buthave not acquired any new locks.  If we add an entry to a different pagein the database, we would acquire additional locks:])m4_indent([dnlLocks grouped by objectLocker    Mode    Count   Status      ----------- Object ----------       1  READ         1  HELD        a.db                handle   080000004  WRITE        2  HELD        a.db                page     380000004  WRITE        1  HELD        a.db                page     2])m4_p([dnlHere's a simple example of one lock blocking another one:])m4_indent([dnlLocks grouped by objectLocker    Mode    Count   Status      ----------- Object ----------80000004  WRITE        1  HELD        a.db                page     280000005  WRITE        1  WAIT        a.db                page     2       1  READ         1  HELD        a.db                handle   080000004  READ         1  HELD        a.db                page     1])m4_p([dnlIn this example, there are two different transactional lockers (80000004 and80000005).  Locker 80000004 is holding a write lock on page 2, andlocker 80000005 is waiting for a write lock on page 2.  This is not adeadlock, because locker 80000004 is not blocked on anything.Presumably, the thread of control using locker 80000004 will proceed,eventually release its write lock on page 2, at which point the threadof control using locker 80000005 can also proceed, acquiring a writelock on page 2.])m4_p([dnlIf lockers 80000004 and 80000005 are not in different threads ofcontrol, the result would be m4_italic(self deadlock).  Self deadlockis not a true deadlock, and won't be detected by the m4_db deadlockdetector.  It's not a true deadlock because, if work could continue tobe done on behalf of locker 80000004, then the lock would eventually bereleased, and locker 80000005 could acquire the lock and itself proceed.So, the key element is that the thread of control holding the lockcannot proceed because it is the same thread as is blocked waiting on thelock.])m4_p([dnlHere's an example of three transactions reaching true deadlock.  First,three different threads of control opened the database, acquiring threedatabase handle read locks.])m4_indent([dnlLocks grouped by objectLocker    Mode    Count   Status      ----------- Object ----------       1  READ         1  HELD        a.db                handle   0       3  READ         1  HELD        a.db                handle   0       5  READ         1  HELD        a.db                handle   0])m4_p([dnlThe three threads then each began a transaction, and put a key/data pairon a different page:])m4_indent([dnlLocks grouped by objectLocker    Mode    Count   Status      ----------- Object ----------80000008  WRITE        1  HELD        a.db                page     4       1  READ         1  HELD        a.db                handle   0       3  READ         1  HELD        a.db                handle   0       5  READ         1  HELD        a.db                handle   080000006  READ         1  HELD        a.db                page     180000007  READ         1  HELD        a.db                page     180000008  READ         1  HELD        a.db                page     180000006  WRITE        1  HELD        a.db                page     280000007  WRITE        1  HELD        a.db                page     3])m4_p([dnlThe thread using locker 80000006 put a new key/data pair on page 2, thethread using locker 80000007, on page 3, and the thread using locker80000008 on page 4.  Because the database is a 2-level Btree, the treewas searched, and so each transaction acquired a read lock on the Btreeroot page (page 1) as part of this operation.])m4_p([dnlThe three threads then each attempted to put a second key/data pair ona page currently locked by another thread.  The thread using locker80000006 tried to put a key/data pair on page 3, the thread using locker80000007 on page 4, and the thread using locker 80000008 on page 2:])m4_indent([dnlLocks grouped by objectLocker    Mode    Count   Status      ----------- Object ----------80000008  WRITE        1  HELD        a.db                page     480000007  WRITE        1  WAIT        a.db                page     4       1  READ         1  HELD        a.db                handle   0       3  READ         1  HELD        a.db                handle   0       5  READ         1  HELD        a.db                handle   080000006  READ         2  HELD        a.db                page     180000007  READ         2  HELD        a.db                page     180000008  READ         2  HELD        a.db                page     180000006  WRITE        1  HELD        a.db                page     280000008  WRITE        1  WAIT        a.db                page     280000007  WRITE        1  HELD        a.db                page     380000006  WRITE        1  WAIT        a.db                page     3])m4_p([dnlNow, each of the threads of control is blocked, waiting on a differentthread of control.The thread using locker 80000007 is blocked bythe thread using locker 80000008, due to the lock on page 4.The thread using locker 80000008 is blocked bythe thread using locker 80000006, due to the lock on page 2.And the thread using locker 80000006 is blocked bythe thread using locker 80000007, due to the lock on page 3.Since none of the threads of control can makeprogress, one of them will have to be killed in order to resolve thedeadlock.])m4_page_footer