← Back to branch summary

~ubuntu-branches/ubuntu/natty/evolution-data-server/natty

« back to all changes in this revision

Viewing changes to libdb/docs/ref/lock/deaddbg.html

  • Committer: Bazaar Package Importer
  • Author(s): Didier Roche
  • Date: 2010-05-17 17:02:06 UTC
  • mfrom: (1.1.79 upstream) (1.6.12 experimental)
  • Revision ID: james.westby@ubuntu.com-20100517170206-4ufr52vwrhh26yh0
Tags: 2.30.1-1ubuntu1
https://launchpad.net/bugs/42199
https://launchpad.net/bugs/229669
https://launchpad.net/bugs/173703
https://launchpad.net/bugs/360344
https://launchpad.net/bugs/508494
* Merge from debian experimental. Remaining change:
  (LP: #42199, #229669, #173703, #360344, #508494)
  + debian/control:
    - add Vcs-Bzr tag
    - don't use libgnome
    - Use Breaks instead of Conflicts against evolution 2.25 and earlier.
  + debian/evolution-data-server.install,
    debian/patches/45_libcamel_providers_version.patch:
    - use the upstream versioning, not a Debian-specific one 
  + debian/libedata-book1.2-dev.install, debian/libebackend-1.2-dev.install,
    debian/libcamel1.2-dev.install, debian/libedataserverui1.2-dev.install:
    - install html documentation
  + debian/rules:
    - don't build documentation it's shipped with the tarball

Show diffs side-by-side

added added

removed removed

Lines of Context:
libdb/docs/ref/lock/deaddbg.html
1
 
<!--$Id$-->
2
 
<!--Copyright 1997-2002 by Sleepycat Software, Inc.-->
3
 
<!--All rights reserved.-->
4
 
<!--See the file LICENSE for redistribution information.-->
5
 
<html>
6
 
<head>
7
 
<title>Berkeley DB Reference Guide: Deadlock debugging</title>
8
 
<meta name="description" content="Berkeley DB: An embedded database programmatic toolkit.">
9
 
<meta name="keywords" content="embedded,database,programmatic,toolkit,b+tree,btree,hash,hashing,transaction,transactions,locking,logging,access method,access methods,java,C,C++">
10
 
</head>
11
 
<body bgcolor=white>
12
 
<table width="100%"><tr valign=top>
13
 
<td><h3><dl><dt>Berkeley DB Reference Guide:<dd>Locking Subsystem</dl></h3></td>
14
 
<td align=right><a href="../../ref/lock/timeout.html"><img src="../../images/prev.gif" alt="Prev"></a><a href="../../reftoc.html"><img src="../../images/ref.gif" alt="Ref"></a><a href="../../ref/lock/page.html"><img src="../../images/next.gif" alt="Next"></a>
15
 
</td></tr></table>
16
 
<p>
17
 
<h1 align=center>Deadlock debugging</h1>
18
 
<p>An occasional debugging problem in Berkeley DB applications is unresolvable
19
 
deadlock.  The output of the <b>-Co</b> flags of the <a href="../../utility/db_stat.html">db_stat</a>
20
 
utility can be used to detect and debug these problems.  The following
21
 
is a typical example of the output of this utility:
22
 
<p><blockquote><pre>Locks grouped by object
23
 
Locker    Mode    Count   Status      ----------- Object ----------
24
 
       1  READ         1  HELD        a.db                handle   0
25
 
80000004  WRITE        1  HELD        a.db                page     3</pre></blockquote>
26
 
<p>In this example, we have opened a database and stored a single key/data
27
 
pair in it.  Because we have a database handle open, we have a read lock
28
 
on that database handle.  The database handle lock is the read lock
29
 
labelled <i>handle</i>.  (We can normally ignore handle locks for
30
 
the purposes of database debugging, as they will only conflict with
31
 
other handle operations, for example, an attempt to remove the database
32
 
will block because we are holding the handle locked, but reading and
33
 
writing the database will not conflict with the handle lock.)
34
 
<p>It is important to note that locker IDs are 32-bit unsigned integers,
35
 
and are divided into two name spaces.  Locker IDs with the high bit set
36
 
(that is, values 80000000 or higher), are locker IDs associated with
37
 
transactions.  Locker IDs without the high bit set are locker IDs that
38
 
are not associated with a transaction.  Locker IDs associated with
39
 
transactions map one-to-one with the transaction, that is, a transaction
40
 
never has more than a single locker ID, and all of the locks acquired
41
 
by the transaction will be acquired on behalf of the same locker ID.
42
 
<p>We also hold a write lock on the database page where we stored the new
43
 
key/data pair.  The page lock is labeled <i>page</i> and is on page
44
 
number 3.  If we were to put an additional key/data pair in the
45
 
database, we would see the following output:
46
 
<p><blockquote><pre>Locks grouped by object
47
 
Locker    Mode    Count   Status      ----------- Object ----------
48
 
80000004  WRITE        2  HELD        a.db                page     3
49
 
       1  READ         1  HELD        a.db                handle   0</pre></blockquote>
50
 
<p>That is, we have acquired a second reference count to page number 3, but
51
 
have not acquired any new locks.  If we add an entry to a different page
52
 
in the database, we would acquire additional locks:
53
 
<p><blockquote><pre>Locks grouped by object
54
 
Locker    Mode    Count   Status      ----------- Object ----------
55
 
       1  READ         1  HELD        a.db                handle   0
56
 
80000004  WRITE        2  HELD        a.db                page     3
57
 
80000004  WRITE        1  HELD        a.db                page     2</pre></blockquote>
58
 
<p>Here's a simple example of one lock blocking another one:
59
 
<p><blockquote><pre>Locks grouped by object
60
 
Locker    Mode    Count   Status      ----------- Object ----------
61
 
80000004  WRITE        1  HELD        a.db                page     2
62
 
80000005  WRITE        1  WAIT        a.db                page     2
63
 
       1  READ         1  HELD        a.db                handle   0
64
 
80000004  READ         1  HELD        a.db                page     1</pre></blockquote>
65
 
<p>In this example, there are two different transactional lockers (80000004 and
66
 
80000005).  Locker 80000004 is holding a write lock on page 2, and
67
 
locker 80000005 is waiting for a write lock on page 2.  This is not a
68
 
deadlock, because locker 80000004 is not blocked on anything.
69
 
Presumably, the thread of control using locker 80000004 will proceed,
70
 
eventually release its write lock on page 2, at which point the thread
71
 
of control using locker 80000005 can also proceed, acquiring a write
72
 
lock on page 2.
73
 
<p>If lockers 80000004 and 80000005 are not in different threads of
74
 
control, the result would be <i>self deadlock</i>.  Self deadlock
75
 
is not a true deadlock, and won't be detected by the Berkeley DB deadlock
76
 
detector.  It's not a true deadlock because, if work could continue to
77
 
be done on behalf of locker 80000004, then the lock would eventually be
78
 
released, and locker 80000005 could acquire the lock and itself proceed.
79
 
So, the key element is that the thread of control holding the lock
80
 
cannot proceed because it the same thread as is blocked waiting on the
81
 
lock.
82
 
<p>Here's an example of three transactions reaching true deadlock.  First,
83
 
three different threads of control opened the database, acquiring three
84
 
database handle read locks.
85
 
<p><blockquote><pre>Locks grouped by object
86
 
Locker    Mode    Count   Status      ----------- Object ----------
87
 
       1  READ         1  HELD        a.db                handle   0
88
 
       3  READ         1  HELD        a.db                handle   0
89
 
       5  READ         1  HELD        a.db                handle   0</pre></blockquote>
90
 
<p>The three threads then each began a transaction, and put a key/data pair
91
 
on a different page:
92
 
<p><blockquote><pre>Locks grouped by object
93
 
Locker    Mode    Count   Status      ----------- Object ----------
94
 
80000008  WRITE        1  HELD        a.db                page     4
95
 
       1  READ         1  HELD        a.db                handle   0
96
 
       3  READ         1  HELD        a.db                handle   0
97
 
       5  READ         1  HELD        a.db                handle   0
98
 
80000006  READ         1  HELD        a.db                page     1
99
 
80000007  READ         1  HELD        a.db                page     1
100
 
80000008  READ         1  HELD        a.db                page     1
101
 
80000006  WRITE        1  HELD        a.db                page     2
102
 
80000007  WRITE        1  HELD        a.db                page     3</pre></blockquote>
103
 
<p>The thread using locker 80000006 put a new key/data pair on page 2, the
104
 
thread using locker 80000007, on page 3, and the thread using locker
105
 
80000008 on page 4.  Because the database is a 2-level Btree, the tree
106
 
was searched, and so each transaction acquired a read lock on the Btree
107
 
root page (page 1) as part of this operation.
108
 
<p>The three threads then each attempted to put a second key/data pair on
109
 
a page currently locked by another thread.  The thread using locker
110
 
80000006 tried to put a key/data pair on page 3, the thread using locker
111
 
80000007 on page 4, and the thread using locker 80000008 on page 2:
112
 
<p><blockquote><pre>Locks grouped by object
113
 
Locker    Mode    Count   Status      ----------- Object ----------
114
 
80000008  WRITE        1  HELD        a.db                page     4
115
 
80000007  WRITE        1  WAIT        a.db                page     4
116
 
       1  READ         1  HELD        a.db                handle   0
117
 
       3  READ         1  HELD        a.db                handle   0
118
 
       5  READ         1  HELD        a.db                handle   0
119
 
80000006  READ         2  HELD        a.db                page     1
120
 
80000007  READ         2  HELD        a.db                page     1
121
 
80000008  READ         2  HELD        a.db                page     1
122
 
80000006  WRITE        1  HELD        a.db                page     2
123
 
80000008  WRITE        1  WAIT        a.db                page     2
124
 
80000007  WRITE        1  HELD        a.db                page     3
125
 
80000006  WRITE        1  WAIT        a.db                page     3</pre></blockquote>
126
 
<p>Now, each of the threads of control are blocked, waiting on a different
127
 
thread of control.
128
 
The thread using locker 80000007 is blocked by
129
 
the thread using locker 80000008, due to the lock on page 4.
130
 
The thread using locker 80000008 is blocked by
131
 
the thread using locker 80000006, due to the lock on page 2.
132
 
And the thread using locker 80000006 is blocked by
133
 
the thread using locker 80000007, due to the lock on page 3.
134
 
Since none of the threads of control can make
135
 
progress, one of them will have to be killed in order to resolve the
136
 
deadlock.
137
 
<table width="100%"><tr><td><br></td><td align=right><a href="../../ref/lock/timeout.html"><img src="../../images/prev.gif" alt="Prev"></a><a href="../../reftoc.html"><img src="../../images/ref.gif" alt="Ref"></a><a href="../../ref/lock/page.html"><img src="../../images/next.gif" alt="Next"></a>
138
 
</td></tr></table>
139
 
<p><font size=1><a href="http://www.sleepycat.com">Copyright Sleepycat Software</a></font>
140
 
</body>
141
 
</html>