1<?xml version="1.0" encoding="UTF-8" standalone="no"?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3<html xmlns="http://www.w3.org/1999/xhtml"> 4 <head> 5 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> 6 <title>Deadlock debugging</title> 7 <link rel="stylesheet" href="gettingStarted.css" type="text/css" /> 8 <meta name="generator" content="DocBook XSL Stylesheets V1.73.2" /> 9 <link rel="start" href="index.html" title="Berkeley DB Programmer's Reference Guide" /> 10 <link rel="up" href="lock.html" title="Chapter 15. The Locking Subsystem" /> 11 <link rel="prev" href="lock_timeout.html" title="Deadlock detection using timers" /> 12 <link rel="next" href="lock_page.html" title="Locking granularity" /> 13 </head> 14 <body> 15 <div class="navheader"> 16 <table width="100%" summary="Navigation header"> 17 <tr> 18 <th colspan="3" align="center">Deadlock debugging</th> 19 </tr> 20 <tr> 21 <td width="20%" align="left"><a accesskey="p" href="lock_timeout.html">Prev</a> </td> 22 <th width="60%" align="center">Chapter 15. 23 The Locking Subsystem 24 </th> 25 <td width="20%" align="right"> <a accesskey="n" href="lock_page.html">Next</a></td> 26 </tr> 27 </table> 28 <hr /> 29 </div> 30 <div class="sect1" lang="en" xml:lang="en"> 31 <div class="titlepage"> 32 <div> 33 <div> 34 <h2 class="title" style="clear: both"><a id="lock_deaddbg"></a>Deadlock debugging</h2> 35 </div> 36 </div> 37 </div> 38 <p>An occasional debugging problem in Berkeley DB applications is unresolvable 39deadlock. The output of the <span class="bold"><strong>-Co</strong></span> flags of the <a href="../api_reference/C/db_stat.html" class="olink">db_stat utility</a> can be used to detect and debug these problems. The following 40is a typical example of the output of this utility:</p> 41 <pre class="programlisting">Locks grouped by object 42Locker Mode Count Status ----------- Object ---------- 43 1 READ 1 HELD a.db handle 0 4480000004 WRITE 1 HELD a.db page 3</pre> 45 <p>In this example, we have opened a database and stored a single key/data 46pair in it. Because we have a database handle open, we have a read lock 47on that database handle. The database handle lock is the read lock 48labeled <span class="emphasis"><em>handle</em></span>. (We can normally ignore handle locks for 49the purposes of database debugging, as they will only conflict with 50other handle operations, for example, an attempt to remove the database 51will block because we are holding the handle locked, but reading and 52writing the database will not conflict with the handle lock.)</p> 53 <p>It is important to note that locker IDs are 32-bit unsigned integers, 54and are divided into two name spaces. Locker IDs with the high bit set 55(that is, values 80000000 or higher), are locker IDs associated with 56transactions. Locker IDs without the high bit set are locker IDs that 57are not associated with a transaction. Locker IDs associated with 58transactions map one-to-one with the transaction, that is, a transaction 59never has more than a single locker ID, and all of the locks acquired 60by the transaction will be acquired on behalf of the same locker ID.</p> 61 <p>We also hold a write lock on the database page where we stored the new 62key/data pair. The page lock is labeled <span class="emphasis"><em>page</em></span> and is on page 63number 3. If we were to put an additional key/data pair in the 64database, we would see the following output:</p> 65 <pre class="programlisting">Locks grouped by object 66Locker Mode Count Status ----------- Object ---------- 6780000004 WRITE 2 HELD a.db page 3 68 1 READ 1 HELD a.db handle 0</pre> 69 <p>That is, we have acquired a second reference count to page number 3, but 70have not acquired any new locks. If we add an entry to a different page 71in the database, we would acquire additional locks:</p> 72 <pre class="programlisting">Locks grouped by object 73Locker Mode Count Status ----------- Object ---------- 74 1 READ 1 HELD a.db handle 0 7580000004 WRITE 2 HELD a.db page 3 7680000004 WRITE 1 HELD a.db page 2</pre> 77 <p>Here's a simple example of one lock blocking another one:</p> 78 <pre class="programlisting">Locks grouped by object 79Locker Mode Count Status ----------- Object ---------- 8080000004 WRITE 1 HELD a.db page 2 8180000005 WRITE 1 WAIT a.db page 2 82 1 READ 1 HELD a.db handle 0 8380000004 READ 1 HELD a.db page 1</pre> 84 <p>In this example, there are two different transactional lockers (80000004 and 8580000005). Locker 80000004 is holding a write lock on page 2, and 86locker 80000005 is waiting for a write lock on page 2. This is not a 87deadlock, because locker 80000004 is not blocked on anything. 88Presumably, the thread of control using locker 80000004 will proceed, 89eventually release its write lock on page 2, at which point the thread 90of control using locker 80000005 can also proceed, acquiring a write 91lock on page 2.</p> 92 <p>If lockers 80000004 and 80000005 are not in different threads of 93control, the result would be <span class="emphasis"><em>self deadlock</em></span>. Self deadlock 94is not a true deadlock, and won't be detected by the Berkeley DB deadlock 95detector. It's not a true deadlock because, if work could continue to 96be done on behalf of locker 80000004, then the lock would eventually be 97released, and locker 80000005 could acquire the lock and itself proceed. 98So, the key element is that the thread of control holding the lock 99cannot proceed because it is the same thread as is blocked waiting on the 100lock.</p> 101 <p>Here's an example of three transactions reaching true deadlock. First, 102three different threads of control opened the database, acquiring three 103database handle read locks.</p> 104 <pre class="programlisting">Locks grouped by object 105Locker Mode Count Status ----------- Object ---------- 106 1 READ 1 HELD a.db handle 0 107 3 READ 1 HELD a.db handle 0 108 5 READ 1 HELD a.db handle 0</pre> 109 <p>The three threads then each began a transaction, and put a key/data pair 110on a different page:</p> 111 <pre class="programlisting">Locks grouped by object 112Locker Mode Count Status ----------- Object ---------- 11380000008 WRITE 1 HELD a.db page 4 114 1 READ 1 HELD a.db handle 0 115 3 READ 1 HELD a.db handle 0 116 5 READ 1 HELD a.db handle 0 11780000006 READ 1 HELD a.db page 1 11880000007 READ 1 HELD a.db page 1 11980000008 READ 1 HELD a.db page 1 12080000006 WRITE 1 HELD a.db page 2 12180000007 WRITE 1 HELD a.db page 3</pre> 122 <p>The thread using locker 80000006 put a new key/data pair on page 2, the 123thread using locker 80000007, on page 3, and the thread using locker 12480000008 on page 4. Because the database is a 2-level Btree, the tree 125was searched, and so each transaction acquired a read lock on the Btree 126root page (page 1) as part of this operation.</p> 127 <p>The three threads then each attempted to put a second key/data pair on 128a page currently locked by another thread. The thread using locker 12980000006 tried to put a key/data pair on page 3, the thread using locker 13080000007 on page 4, and the thread using locker 80000008 on page 2:</p> 131 <pre class="programlisting">Locks grouped by object 132Locker Mode Count Status ----------- Object ---------- 13380000008 WRITE 1 HELD a.db page 4 13480000007 WRITE 1 WAIT a.db page 4 135 1 READ 1 HELD a.db handle 0 136 3 READ 1 HELD a.db handle 0 137 5 READ 1 HELD a.db handle 0 13880000006 READ 2 HELD a.db page 1 13980000007 READ 2 HELD a.db page 1 14080000008 READ 2 HELD a.db page 1 14180000006 WRITE 1 HELD a.db page 2 14280000008 WRITE 1 WAIT a.db page 2 14380000007 WRITE 1 HELD a.db page 3 14480000006 WRITE 1 WAIT a.db page 3</pre> 145 <p>Now, each of the threads of control is blocked, waiting on a different 146thread of control. 147The thread using locker 80000007 is blocked by 148the thread using locker 80000008, due to the lock on page 4. 149The thread using locker 80000008 is blocked by 150the thread using locker 80000006, due to the lock on page 2. 151And the thread using locker 80000006 is blocked by 152the thread using locker 80000007, due to the lock on page 3. 153Since none of the threads of control can make 154progress, one of them will have to be killed in order to resolve the 155deadlock.</p> 156 </div> 157 <div class="navfooter"> 158 <hr /> 159 <table width="100%" summary="Navigation footer"> 160 <tr> 161 <td width="40%" align="left"><a accesskey="p" href="lock_timeout.html">Prev</a> </td> 162 <td width="20%" align="center"> 163 <a accesskey="u" href="lock.html">Up</a> 164 </td> 165 <td width="40%" align="right"> <a accesskey="n" href="lock_page.html">Next</a></td> 166 </tr> 167 <tr> 168 <td width="40%" align="left" valign="top">Deadlock detection using timers </td> 169 <td width="20%" align="center"> 170 <a accesskey="h" href="index.html">Home</a> 171 </td> 172 <td width="40%" align="right" valign="top"> Locking granularity</td> 173 </tr> 174 </table> 175 </div> 176 </body> 177</html> 178