1*7c478bd9Sstevel@tonic-gate /*-
2*7c478bd9Sstevel@tonic-gate * See the file LICENSE for redistribution information.
3*7c478bd9Sstevel@tonic-gate *
4*7c478bd9Sstevel@tonic-gate * Copyright (c) 1996, 1997, 1998
5*7c478bd9Sstevel@tonic-gate * Sleepycat Software. All rights reserved.
6*7c478bd9Sstevel@tonic-gate */
7*7c478bd9Sstevel@tonic-gate
8*7c478bd9Sstevel@tonic-gate #include "config.h"
9*7c478bd9Sstevel@tonic-gate
10*7c478bd9Sstevel@tonic-gate #ifndef lint
11*7c478bd9Sstevel@tonic-gate static const char sccsid[] = "@(#)lock_deadlock.c 10.37 (Sleepycat) 10/4/98";
12*7c478bd9Sstevel@tonic-gate #endif /* not lint */
13*7c478bd9Sstevel@tonic-gate
14*7c478bd9Sstevel@tonic-gate #ifndef NO_SYSTEM_INCLUDES
15*7c478bd9Sstevel@tonic-gate #include <sys/types.h>
16*7c478bd9Sstevel@tonic-gate
17*7c478bd9Sstevel@tonic-gate #include <errno.h>
18*7c478bd9Sstevel@tonic-gate #include <string.h>
19*7c478bd9Sstevel@tonic-gate #endif
20*7c478bd9Sstevel@tonic-gate
21*7c478bd9Sstevel@tonic-gate #include "db_int.h"
22*7c478bd9Sstevel@tonic-gate #include "shqueue.h"
23*7c478bd9Sstevel@tonic-gate #include "db_shash.h"
24*7c478bd9Sstevel@tonic-gate #include "lock.h"
25*7c478bd9Sstevel@tonic-gate #include "common_ext.h"
26*7c478bd9Sstevel@tonic-gate
27*7c478bd9Sstevel@tonic-gate #define ISSET_MAP(M, N) (M[(N) / 32] & (1 << (N) % 32))
28*7c478bd9Sstevel@tonic-gate
29*7c478bd9Sstevel@tonic-gate #define CLEAR_MAP(M, N) { \
30*7c478bd9Sstevel@tonic-gate u_int32_t __i; \
31*7c478bd9Sstevel@tonic-gate for (__i = 0; __i < (N); __i++) \
32*7c478bd9Sstevel@tonic-gate M[__i] = 0; \
33*7c478bd9Sstevel@tonic-gate }
34*7c478bd9Sstevel@tonic-gate
35*7c478bd9Sstevel@tonic-gate #define SET_MAP(M, B) (M[(B) / 32] |= (1 << ((B) % 32)))
36*7c478bd9Sstevel@tonic-gate #define CLR_MAP(M, B) (M[(B) / 32] &= ~(1 << ((B) % 32)))
37*7c478bd9Sstevel@tonic-gate
38*7c478bd9Sstevel@tonic-gate #define OR_MAP(D, S, N) { \
39*7c478bd9Sstevel@tonic-gate u_int32_t __i; \
40*7c478bd9Sstevel@tonic-gate for (__i = 0; __i < (N); __i++) \
41*7c478bd9Sstevel@tonic-gate D[__i] |= S[__i]; \
42*7c478bd9Sstevel@tonic-gate }
43*7c478bd9Sstevel@tonic-gate #define BAD_KILLID 0xffffffff
44*7c478bd9Sstevel@tonic-gate
45*7c478bd9Sstevel@tonic-gate typedef struct {
46*7c478bd9Sstevel@tonic-gate int valid;
47*7c478bd9Sstevel@tonic-gate u_int32_t id;
48*7c478bd9Sstevel@tonic-gate DB_LOCK last_lock;
49*7c478bd9Sstevel@tonic-gate db_pgno_t pgno;
50*7c478bd9Sstevel@tonic-gate } locker_info;
51*7c478bd9Sstevel@tonic-gate
52*7c478bd9Sstevel@tonic-gate static int __dd_abort __P((DB_ENV *, locker_info *));
53*7c478bd9Sstevel@tonic-gate static int __dd_build
54*7c478bd9Sstevel@tonic-gate __P((DB_ENV *, u_int32_t **, u_int32_t *, locker_info **));
55*7c478bd9Sstevel@tonic-gate static u_int32_t
56*7c478bd9Sstevel@tonic-gate *__dd_find __P((u_int32_t *, locker_info *, u_int32_t));
57*7c478bd9Sstevel@tonic-gate
58*7c478bd9Sstevel@tonic-gate #ifdef DIAGNOSTIC
59*7c478bd9Sstevel@tonic-gate static void __dd_debug __P((DB_ENV *, locker_info *, u_int32_t *, u_int32_t));
60*7c478bd9Sstevel@tonic-gate #endif
61*7c478bd9Sstevel@tonic-gate
62*7c478bd9Sstevel@tonic-gate int
lock_detect(lt,flags,atype)63*7c478bd9Sstevel@tonic-gate lock_detect(lt, flags, atype)
64*7c478bd9Sstevel@tonic-gate DB_LOCKTAB *lt;
65*7c478bd9Sstevel@tonic-gate u_int32_t flags, atype;
66*7c478bd9Sstevel@tonic-gate {
67*7c478bd9Sstevel@tonic-gate DB_ENV *dbenv;
68*7c478bd9Sstevel@tonic-gate locker_info *idmap;
69*7c478bd9Sstevel@tonic-gate u_int32_t *bitmap, *deadlock, i, killid, nentries, nlockers;
70*7c478bd9Sstevel@tonic-gate int do_pass, ret;
71*7c478bd9Sstevel@tonic-gate
72*7c478bd9Sstevel@tonic-gate LOCK_PANIC_CHECK(lt);
73*7c478bd9Sstevel@tonic-gate
74*7c478bd9Sstevel@tonic-gate /* Validate arguments. */
75*7c478bd9Sstevel@tonic-gate if ((ret =
76*7c478bd9Sstevel@tonic-gate __db_fchk(lt->dbenv, "lock_detect", flags, DB_LOCK_CONFLICT)) != 0)
77*7c478bd9Sstevel@tonic-gate return (ret);
78*7c478bd9Sstevel@tonic-gate
79*7c478bd9Sstevel@tonic-gate /* Check if a detector run is necessary. */
80*7c478bd9Sstevel@tonic-gate dbenv = lt->dbenv;
81*7c478bd9Sstevel@tonic-gate if (LF_ISSET(DB_LOCK_CONFLICT)) {
82*7c478bd9Sstevel@tonic-gate /* Make a pass every time a lock waits. */
83*7c478bd9Sstevel@tonic-gate LOCK_LOCKREGION(lt);
84*7c478bd9Sstevel@tonic-gate do_pass = dbenv->lk_info->region->need_dd != 0;
85*7c478bd9Sstevel@tonic-gate UNLOCK_LOCKREGION(lt);
86*7c478bd9Sstevel@tonic-gate
87*7c478bd9Sstevel@tonic-gate if (!do_pass)
88*7c478bd9Sstevel@tonic-gate return (0);
89*7c478bd9Sstevel@tonic-gate }
90*7c478bd9Sstevel@tonic-gate
91*7c478bd9Sstevel@tonic-gate /* Build the waits-for bitmap. */
92*7c478bd9Sstevel@tonic-gate if ((ret = __dd_build(dbenv, &bitmap, &nlockers, &idmap)) != 0)
93*7c478bd9Sstevel@tonic-gate return (ret);
94*7c478bd9Sstevel@tonic-gate
95*7c478bd9Sstevel@tonic-gate if (nlockers == 0)
96*7c478bd9Sstevel@tonic-gate return (0);
97*7c478bd9Sstevel@tonic-gate #ifdef DIAGNOSTIC
98*7c478bd9Sstevel@tonic-gate if (dbenv->db_verbose != 0)
99*7c478bd9Sstevel@tonic-gate __dd_debug(dbenv, idmap, bitmap, nlockers);
100*7c478bd9Sstevel@tonic-gate #endif
101*7c478bd9Sstevel@tonic-gate /* Find a deadlock. */
102*7c478bd9Sstevel@tonic-gate deadlock = __dd_find(bitmap, idmap, nlockers);
103*7c478bd9Sstevel@tonic-gate nentries = ALIGN(nlockers, 32) / 32;
104*7c478bd9Sstevel@tonic-gate killid = BAD_KILLID;
105*7c478bd9Sstevel@tonic-gate if (deadlock != NULL) {
106*7c478bd9Sstevel@tonic-gate /* Kill someone. */
107*7c478bd9Sstevel@tonic-gate switch (atype) {
108*7c478bd9Sstevel@tonic-gate case DB_LOCK_OLDEST:
109*7c478bd9Sstevel@tonic-gate /*
110*7c478bd9Sstevel@tonic-gate * Find the first bit set in the current
111*7c478bd9Sstevel@tonic-gate * array and then look for a lower tid in
112*7c478bd9Sstevel@tonic-gate * the array.
113*7c478bd9Sstevel@tonic-gate */
114*7c478bd9Sstevel@tonic-gate for (i = 0; i < nlockers; i++)
115*7c478bd9Sstevel@tonic-gate if (ISSET_MAP(deadlock, i))
116*7c478bd9Sstevel@tonic-gate killid = i;
117*7c478bd9Sstevel@tonic-gate
118*7c478bd9Sstevel@tonic-gate if (killid == BAD_KILLID) {
119*7c478bd9Sstevel@tonic-gate __db_err(dbenv,
120*7c478bd9Sstevel@tonic-gate "warning: could not find locker to abort");
121*7c478bd9Sstevel@tonic-gate break;
122*7c478bd9Sstevel@tonic-gate }
123*7c478bd9Sstevel@tonic-gate
124*7c478bd9Sstevel@tonic-gate /*
125*7c478bd9Sstevel@tonic-gate * The oldest transaction has the lowest
126*7c478bd9Sstevel@tonic-gate * transaction id.
127*7c478bd9Sstevel@tonic-gate */
128*7c478bd9Sstevel@tonic-gate for (i = killid + 1; i < nlockers; i++)
129*7c478bd9Sstevel@tonic-gate if (ISSET_MAP(deadlock, i) &&
130*7c478bd9Sstevel@tonic-gate idmap[i].id < idmap[killid].id)
131*7c478bd9Sstevel@tonic-gate killid = i;
132*7c478bd9Sstevel@tonic-gate break;
133*7c478bd9Sstevel@tonic-gate case DB_LOCK_DEFAULT:
134*7c478bd9Sstevel@tonic-gate case DB_LOCK_RANDOM:
135*7c478bd9Sstevel@tonic-gate /*
136*7c478bd9Sstevel@tonic-gate * We are trying to calculate the id of the
137*7c478bd9Sstevel@tonic-gate * locker whose entry is indicated by deadlock.
138*7c478bd9Sstevel@tonic-gate */
139*7c478bd9Sstevel@tonic-gate killid = (deadlock - bitmap) / nentries;
140*7c478bd9Sstevel@tonic-gate break;
141*7c478bd9Sstevel@tonic-gate case DB_LOCK_YOUNGEST:
142*7c478bd9Sstevel@tonic-gate /*
143*7c478bd9Sstevel@tonic-gate * Find the first bit set in the current
144*7c478bd9Sstevel@tonic-gate * array and then look for a lower tid in
145*7c478bd9Sstevel@tonic-gate * the array.
146*7c478bd9Sstevel@tonic-gate */
147*7c478bd9Sstevel@tonic-gate for (i = 0; i < nlockers; i++)
148*7c478bd9Sstevel@tonic-gate if (ISSET_MAP(deadlock, i))
149*7c478bd9Sstevel@tonic-gate killid = i;
150*7c478bd9Sstevel@tonic-gate
151*7c478bd9Sstevel@tonic-gate if (killid == BAD_KILLID) {
152*7c478bd9Sstevel@tonic-gate __db_err(dbenv,
153*7c478bd9Sstevel@tonic-gate "warning: could not find locker to abort");
154*7c478bd9Sstevel@tonic-gate break;
155*7c478bd9Sstevel@tonic-gate }
156*7c478bd9Sstevel@tonic-gate /*
157*7c478bd9Sstevel@tonic-gate * The youngest transaction has the highest
158*7c478bd9Sstevel@tonic-gate * transaction id.
159*7c478bd9Sstevel@tonic-gate */
160*7c478bd9Sstevel@tonic-gate for (i = killid + 1; i < nlockers; i++)
161*7c478bd9Sstevel@tonic-gate if (ISSET_MAP(deadlock, i) &&
162*7c478bd9Sstevel@tonic-gate idmap[i].id > idmap[killid].id)
163*7c478bd9Sstevel@tonic-gate killid = i;
164*7c478bd9Sstevel@tonic-gate break;
165*7c478bd9Sstevel@tonic-gate default:
166*7c478bd9Sstevel@tonic-gate killid = BAD_KILLID;
167*7c478bd9Sstevel@tonic-gate ret = EINVAL;
168*7c478bd9Sstevel@tonic-gate }
169*7c478bd9Sstevel@tonic-gate
170*7c478bd9Sstevel@tonic-gate /* Kill the locker with lockid idmap[killid]. */
171*7c478bd9Sstevel@tonic-gate if (dbenv->db_verbose != 0 && killid != BAD_KILLID)
172*7c478bd9Sstevel@tonic-gate __db_err(dbenv, "Aborting locker %lx",
173*7c478bd9Sstevel@tonic-gate (u_long)idmap[killid].id);
174*7c478bd9Sstevel@tonic-gate
175*7c478bd9Sstevel@tonic-gate if (killid != BAD_KILLID &&
176*7c478bd9Sstevel@tonic-gate (ret = __dd_abort(dbenv, &idmap[killid])) != 0)
177*7c478bd9Sstevel@tonic-gate __db_err(dbenv,
178*7c478bd9Sstevel@tonic-gate "warning: unable to abort locker %lx",
179*7c478bd9Sstevel@tonic-gate (u_long)idmap[killid].id);
180*7c478bd9Sstevel@tonic-gate }
181*7c478bd9Sstevel@tonic-gate __os_free(bitmap, 0);
182*7c478bd9Sstevel@tonic-gate __os_free(idmap, 0);
183*7c478bd9Sstevel@tonic-gate
184*7c478bd9Sstevel@tonic-gate return (ret);
185*7c478bd9Sstevel@tonic-gate }
186*7c478bd9Sstevel@tonic-gate
187*7c478bd9Sstevel@tonic-gate /*
188*7c478bd9Sstevel@tonic-gate * ========================================================================
189*7c478bd9Sstevel@tonic-gate * Utilities
190*7c478bd9Sstevel@tonic-gate */
191*7c478bd9Sstevel@tonic-gate static int
__dd_build(dbenv,bmp,nlockers,idmap)192*7c478bd9Sstevel@tonic-gate __dd_build(dbenv, bmp, nlockers, idmap)
193*7c478bd9Sstevel@tonic-gate DB_ENV *dbenv;
194*7c478bd9Sstevel@tonic-gate u_int32_t **bmp, *nlockers;
195*7c478bd9Sstevel@tonic-gate locker_info **idmap;
196*7c478bd9Sstevel@tonic-gate {
197*7c478bd9Sstevel@tonic-gate struct __db_lock *lp;
198*7c478bd9Sstevel@tonic-gate DB_LOCKTAB *lt;
199*7c478bd9Sstevel@tonic-gate DB_LOCKOBJ *op, *lo, *lockerp;
200*7c478bd9Sstevel@tonic-gate u_int8_t *pptr;
201*7c478bd9Sstevel@tonic-gate locker_info *id_array;
202*7c478bd9Sstevel@tonic-gate u_int32_t *bitmap, count, *entryp, i, id, nentries, *tmpmap;
203*7c478bd9Sstevel@tonic-gate int is_first, ret;
204*7c478bd9Sstevel@tonic-gate
205*7c478bd9Sstevel@tonic-gate lt = dbenv->lk_info;
206*7c478bd9Sstevel@tonic-gate
207*7c478bd9Sstevel@tonic-gate /*
208*7c478bd9Sstevel@tonic-gate * We'll check how many lockers there are, add a few more in for
209*7c478bd9Sstevel@tonic-gate * good measure and then allocate all the structures. Then we'll
210*7c478bd9Sstevel@tonic-gate * verify that we have enough room when we go back in and get the
211*7c478bd9Sstevel@tonic-gate * mutex the second time.
212*7c478bd9Sstevel@tonic-gate */
213*7c478bd9Sstevel@tonic-gate LOCK_LOCKREGION(lt);
214*7c478bd9Sstevel@tonic-gate retry: count = lt->region->nlockers;
215*7c478bd9Sstevel@tonic-gate lt->region->need_dd = 0;
216*7c478bd9Sstevel@tonic-gate UNLOCK_LOCKREGION(lt);
217*7c478bd9Sstevel@tonic-gate
218*7c478bd9Sstevel@tonic-gate if (count == 0) {
219*7c478bd9Sstevel@tonic-gate *nlockers = 0;
220*7c478bd9Sstevel@tonic-gate return (0);
221*7c478bd9Sstevel@tonic-gate }
222*7c478bd9Sstevel@tonic-gate
223*7c478bd9Sstevel@tonic-gate if (dbenv->db_verbose)
224*7c478bd9Sstevel@tonic-gate __db_err(dbenv, "%lu lockers", (u_long)count);
225*7c478bd9Sstevel@tonic-gate
226*7c478bd9Sstevel@tonic-gate count += 10;
227*7c478bd9Sstevel@tonic-gate nentries = ALIGN(count, 32) / 32;
228*7c478bd9Sstevel@tonic-gate /*
229*7c478bd9Sstevel@tonic-gate * Allocate enough space for a count by count bitmap matrix.
230*7c478bd9Sstevel@tonic-gate *
231*7c478bd9Sstevel@tonic-gate * XXX
232*7c478bd9Sstevel@tonic-gate * We can probably save the malloc's between iterations just
233*7c478bd9Sstevel@tonic-gate * reallocing if necessary because count grew by too much.
234*7c478bd9Sstevel@tonic-gate */
235*7c478bd9Sstevel@tonic-gate if ((ret = __os_calloc((size_t)count,
236*7c478bd9Sstevel@tonic-gate sizeof(u_int32_t) * nentries, &bitmap)) != 0)
237*7c478bd9Sstevel@tonic-gate return (ret);
238*7c478bd9Sstevel@tonic-gate
239*7c478bd9Sstevel@tonic-gate if ((ret = __os_calloc(sizeof(u_int32_t), nentries, &tmpmap)) != 0) {
240*7c478bd9Sstevel@tonic-gate __os_free(bitmap, sizeof(u_int32_t) * nentries);
241*7c478bd9Sstevel@tonic-gate return (ret);
242*7c478bd9Sstevel@tonic-gate }
243*7c478bd9Sstevel@tonic-gate
244*7c478bd9Sstevel@tonic-gate if ((ret =
245*7c478bd9Sstevel@tonic-gate __os_calloc((size_t)count, sizeof(locker_info), &id_array)) != 0) {
246*7c478bd9Sstevel@tonic-gate __os_free(bitmap, count * sizeof(u_int32_t) * nentries);
247*7c478bd9Sstevel@tonic-gate __os_free(tmpmap, sizeof(u_int32_t) * nentries);
248*7c478bd9Sstevel@tonic-gate return (ret);
249*7c478bd9Sstevel@tonic-gate }
250*7c478bd9Sstevel@tonic-gate
251*7c478bd9Sstevel@tonic-gate /*
252*7c478bd9Sstevel@tonic-gate * Now go back in and actually fill in the matrix.
253*7c478bd9Sstevel@tonic-gate */
254*7c478bd9Sstevel@tonic-gate LOCK_LOCKREGION(lt);
255*7c478bd9Sstevel@tonic-gate if (lt->region->nlockers > count) {
256*7c478bd9Sstevel@tonic-gate __os_free(bitmap, count * sizeof(u_int32_t) * nentries);
257*7c478bd9Sstevel@tonic-gate __os_free(tmpmap, sizeof(u_int32_t) * nentries);
258*7c478bd9Sstevel@tonic-gate __os_free(id_array, count * sizeof(locker_info));
259*7c478bd9Sstevel@tonic-gate goto retry;
260*7c478bd9Sstevel@tonic-gate }
261*7c478bd9Sstevel@tonic-gate
262*7c478bd9Sstevel@tonic-gate /*
263*7c478bd9Sstevel@tonic-gate * First we go through and assign each locker a deadlock detector id.
264*7c478bd9Sstevel@tonic-gate * Note that we fill in the idmap in the next loop since that's the
265*7c478bd9Sstevel@tonic-gate * only place where we conveniently have both the deadlock id and the
266*7c478bd9Sstevel@tonic-gate * actual locker.
267*7c478bd9Sstevel@tonic-gate */
268*7c478bd9Sstevel@tonic-gate for (id = 0, i = 0; i < lt->region->table_size; i++)
269*7c478bd9Sstevel@tonic-gate for (op = SH_TAILQ_FIRST(<->hashtab[i], __db_lockobj);
270*7c478bd9Sstevel@tonic-gate op != NULL; op = SH_TAILQ_NEXT(op, links, __db_lockobj))
271*7c478bd9Sstevel@tonic-gate if (op->type == DB_LOCK_LOCKER)
272*7c478bd9Sstevel@tonic-gate op->dd_id = id++;
273*7c478bd9Sstevel@tonic-gate /*
274*7c478bd9Sstevel@tonic-gate * We go through the hash table and find each object. For each object,
275*7c478bd9Sstevel@tonic-gate * we traverse the waiters list and add an entry in the waitsfor matrix
276*7c478bd9Sstevel@tonic-gate * for each waiter/holder combination.
277*7c478bd9Sstevel@tonic-gate */
278*7c478bd9Sstevel@tonic-gate for (i = 0; i < lt->region->table_size; i++) {
279*7c478bd9Sstevel@tonic-gate for (op = SH_TAILQ_FIRST(<->hashtab[i], __db_lockobj);
280*7c478bd9Sstevel@tonic-gate op != NULL; op = SH_TAILQ_NEXT(op, links, __db_lockobj)) {
281*7c478bd9Sstevel@tonic-gate if (op->type != DB_LOCK_OBJTYPE)
282*7c478bd9Sstevel@tonic-gate continue;
283*7c478bd9Sstevel@tonic-gate CLEAR_MAP(tmpmap, nentries);
284*7c478bd9Sstevel@tonic-gate
285*7c478bd9Sstevel@tonic-gate /*
286*7c478bd9Sstevel@tonic-gate * First we go through and create a bit map that
287*7c478bd9Sstevel@tonic-gate * represents all the holders of this object.
288*7c478bd9Sstevel@tonic-gate */
289*7c478bd9Sstevel@tonic-gate for (lp = SH_TAILQ_FIRST(&op->holders, __db_lock);
290*7c478bd9Sstevel@tonic-gate lp != NULL;
291*7c478bd9Sstevel@tonic-gate lp = SH_TAILQ_NEXT(lp, links, __db_lock)) {
292*7c478bd9Sstevel@tonic-gate if (__lock_getobj(lt, lp->holder,
293*7c478bd9Sstevel@tonic-gate NULL, DB_LOCK_LOCKER, &lockerp) != 0) {
294*7c478bd9Sstevel@tonic-gate __db_err(dbenv,
295*7c478bd9Sstevel@tonic-gate "warning unable to find object");
296*7c478bd9Sstevel@tonic-gate continue;
297*7c478bd9Sstevel@tonic-gate }
298*7c478bd9Sstevel@tonic-gate id_array[lockerp->dd_id].id = lp->holder;
299*7c478bd9Sstevel@tonic-gate id_array[lockerp->dd_id].valid = 1;
300*7c478bd9Sstevel@tonic-gate
301*7c478bd9Sstevel@tonic-gate /*
302*7c478bd9Sstevel@tonic-gate * If the holder has already been aborted, then
303*7c478bd9Sstevel@tonic-gate * we should ignore it for now.
304*7c478bd9Sstevel@tonic-gate */
305*7c478bd9Sstevel@tonic-gate if (lp->status == DB_LSTAT_HELD)
306*7c478bd9Sstevel@tonic-gate SET_MAP(tmpmap, lockerp->dd_id);
307*7c478bd9Sstevel@tonic-gate }
308*7c478bd9Sstevel@tonic-gate
309*7c478bd9Sstevel@tonic-gate /*
310*7c478bd9Sstevel@tonic-gate * Next, for each waiter, we set its row in the matrix
311*7c478bd9Sstevel@tonic-gate * equal to the map of holders we set up above.
312*7c478bd9Sstevel@tonic-gate */
313*7c478bd9Sstevel@tonic-gate for (is_first = 1,
314*7c478bd9Sstevel@tonic-gate lp = SH_TAILQ_FIRST(&op->waiters, __db_lock);
315*7c478bd9Sstevel@tonic-gate lp != NULL;
316*7c478bd9Sstevel@tonic-gate is_first = 0,
317*7c478bd9Sstevel@tonic-gate lp = SH_TAILQ_NEXT(lp, links, __db_lock)) {
318*7c478bd9Sstevel@tonic-gate if (__lock_getobj(lt, lp->holder,
319*7c478bd9Sstevel@tonic-gate NULL, DB_LOCK_LOCKER, &lockerp) != 0) {
320*7c478bd9Sstevel@tonic-gate __db_err(dbenv,
321*7c478bd9Sstevel@tonic-gate "warning unable to find object");
322*7c478bd9Sstevel@tonic-gate continue;
323*7c478bd9Sstevel@tonic-gate }
324*7c478bd9Sstevel@tonic-gate id_array[lockerp->dd_id].id = lp->holder;
325*7c478bd9Sstevel@tonic-gate id_array[lockerp->dd_id].valid = 1;
326*7c478bd9Sstevel@tonic-gate
327*7c478bd9Sstevel@tonic-gate /*
328*7c478bd9Sstevel@tonic-gate * If the transaction is pending abortion, then
329*7c478bd9Sstevel@tonic-gate * ignore it on this iteration.
330*7c478bd9Sstevel@tonic-gate */
331*7c478bd9Sstevel@tonic-gate if (lp->status != DB_LSTAT_WAITING)
332*7c478bd9Sstevel@tonic-gate continue;
333*7c478bd9Sstevel@tonic-gate
334*7c478bd9Sstevel@tonic-gate entryp = bitmap + (nentries * lockerp->dd_id);
335*7c478bd9Sstevel@tonic-gate OR_MAP(entryp, tmpmap, nentries);
336*7c478bd9Sstevel@tonic-gate /*
337*7c478bd9Sstevel@tonic-gate * If this is the first waiter on the queue,
338*7c478bd9Sstevel@tonic-gate * then we remove the waitsfor relationship
339*7c478bd9Sstevel@tonic-gate * with oneself. However, if it's anywhere
340*7c478bd9Sstevel@tonic-gate * else on the queue, then we have to keep
341*7c478bd9Sstevel@tonic-gate * it and we have an automatic deadlock.
342*7c478bd9Sstevel@tonic-gate */
343*7c478bd9Sstevel@tonic-gate if (is_first)
344*7c478bd9Sstevel@tonic-gate CLR_MAP(entryp, lockerp->dd_id);
345*7c478bd9Sstevel@tonic-gate }
346*7c478bd9Sstevel@tonic-gate }
347*7c478bd9Sstevel@tonic-gate }
348*7c478bd9Sstevel@tonic-gate
349*7c478bd9Sstevel@tonic-gate /* Now for each locker; record its last lock. */
350*7c478bd9Sstevel@tonic-gate for (id = 0; id < count; id++) {
351*7c478bd9Sstevel@tonic-gate if (!id_array[id].valid)
352*7c478bd9Sstevel@tonic-gate continue;
353*7c478bd9Sstevel@tonic-gate if (__lock_getobj(lt,
354*7c478bd9Sstevel@tonic-gate id_array[id].id, NULL, DB_LOCK_LOCKER, &lockerp) != 0) {
355*7c478bd9Sstevel@tonic-gate __db_err(dbenv,
356*7c478bd9Sstevel@tonic-gate "No locks for locker %lu", (u_long)id_array[id].id);
357*7c478bd9Sstevel@tonic-gate continue;
358*7c478bd9Sstevel@tonic-gate }
359*7c478bd9Sstevel@tonic-gate lp = SH_LIST_FIRST(&lockerp->heldby, __db_lock);
360*7c478bd9Sstevel@tonic-gate if (lp != NULL) {
361*7c478bd9Sstevel@tonic-gate id_array[id].last_lock = LOCK_TO_OFFSET(lt, lp);
362*7c478bd9Sstevel@tonic-gate lo = (DB_LOCKOBJ *)((u_int8_t *)lp + lp->obj);
363*7c478bd9Sstevel@tonic-gate pptr = SH_DBT_PTR(&lo->lockobj);
364*7c478bd9Sstevel@tonic-gate if (lo->lockobj.size >= sizeof(db_pgno_t))
365*7c478bd9Sstevel@tonic-gate memcpy(&id_array[id].pgno, pptr,
366*7c478bd9Sstevel@tonic-gate sizeof(db_pgno_t));
367*7c478bd9Sstevel@tonic-gate else
368*7c478bd9Sstevel@tonic-gate id_array[id].pgno = 0;
369*7c478bd9Sstevel@tonic-gate }
370*7c478bd9Sstevel@tonic-gate }
371*7c478bd9Sstevel@tonic-gate
372*7c478bd9Sstevel@tonic-gate /* Pass complete, reset the deadlock detector bit. */
373*7c478bd9Sstevel@tonic-gate lt->region->need_dd = 0;
374*7c478bd9Sstevel@tonic-gate UNLOCK_LOCKREGION(lt);
375*7c478bd9Sstevel@tonic-gate
376*7c478bd9Sstevel@tonic-gate /*
377*7c478bd9Sstevel@tonic-gate * Now we can release everything except the bitmap matrix that we
378*7c478bd9Sstevel@tonic-gate * created.
379*7c478bd9Sstevel@tonic-gate */
380*7c478bd9Sstevel@tonic-gate *nlockers = id;
381*7c478bd9Sstevel@tonic-gate *idmap = id_array;
382*7c478bd9Sstevel@tonic-gate *bmp = bitmap;
383*7c478bd9Sstevel@tonic-gate __os_free(tmpmap, sizeof(u_int32_t) * nentries);
384*7c478bd9Sstevel@tonic-gate return (0);
385*7c478bd9Sstevel@tonic-gate }
386*7c478bd9Sstevel@tonic-gate
387*7c478bd9Sstevel@tonic-gate static u_int32_t *
__dd_find(bmp,idmap,nlockers)388*7c478bd9Sstevel@tonic-gate __dd_find(bmp, idmap, nlockers)
389*7c478bd9Sstevel@tonic-gate u_int32_t *bmp, nlockers;
390*7c478bd9Sstevel@tonic-gate locker_info *idmap;
391*7c478bd9Sstevel@tonic-gate {
392*7c478bd9Sstevel@tonic-gate u_int32_t i, j, nentries, *mymap, *tmpmap;
393*7c478bd9Sstevel@tonic-gate
394*7c478bd9Sstevel@tonic-gate /*
395*7c478bd9Sstevel@tonic-gate * For each locker, OR in the bits from the lockers on which that
396*7c478bd9Sstevel@tonic-gate * locker is waiting.
397*7c478bd9Sstevel@tonic-gate */
398*7c478bd9Sstevel@tonic-gate nentries = ALIGN(nlockers, 32) / 32;
399*7c478bd9Sstevel@tonic-gate for (mymap = bmp, i = 0; i < nlockers; i++, mymap += nentries) {
400*7c478bd9Sstevel@tonic-gate if (!idmap[i].valid)
401*7c478bd9Sstevel@tonic-gate continue;
402*7c478bd9Sstevel@tonic-gate for (j = 0; j < nlockers; j++) {
403*7c478bd9Sstevel@tonic-gate if (ISSET_MAP(mymap, j)) {
404*7c478bd9Sstevel@tonic-gate /* Find the map for this bit. */
405*7c478bd9Sstevel@tonic-gate tmpmap = bmp + (nentries * j);
406*7c478bd9Sstevel@tonic-gate OR_MAP(mymap, tmpmap, nentries);
407*7c478bd9Sstevel@tonic-gate if (ISSET_MAP(mymap, i))
408*7c478bd9Sstevel@tonic-gate return (mymap);
409*7c478bd9Sstevel@tonic-gate }
410*7c478bd9Sstevel@tonic-gate }
411*7c478bd9Sstevel@tonic-gate }
412*7c478bd9Sstevel@tonic-gate return (NULL);
413*7c478bd9Sstevel@tonic-gate }
414*7c478bd9Sstevel@tonic-gate
415*7c478bd9Sstevel@tonic-gate static int
__dd_abort(dbenv,info)416*7c478bd9Sstevel@tonic-gate __dd_abort(dbenv, info)
417*7c478bd9Sstevel@tonic-gate DB_ENV *dbenv;
418*7c478bd9Sstevel@tonic-gate locker_info *info;
419*7c478bd9Sstevel@tonic-gate {
420*7c478bd9Sstevel@tonic-gate struct __db_lock *lockp;
421*7c478bd9Sstevel@tonic-gate DB_LOCKTAB *lt;
422*7c478bd9Sstevel@tonic-gate DB_LOCKOBJ *lockerp, *sh_obj;
423*7c478bd9Sstevel@tonic-gate int ret;
424*7c478bd9Sstevel@tonic-gate
425*7c478bd9Sstevel@tonic-gate lt = dbenv->lk_info;
426*7c478bd9Sstevel@tonic-gate LOCK_LOCKREGION(lt);
427*7c478bd9Sstevel@tonic-gate
428*7c478bd9Sstevel@tonic-gate /* Find the locker's last lock. */
429*7c478bd9Sstevel@tonic-gate if ((ret =
430*7c478bd9Sstevel@tonic-gate __lock_getobj(lt, info->id, NULL, DB_LOCK_LOCKER, &lockerp)) != 0)
431*7c478bd9Sstevel@tonic-gate goto out;
432*7c478bd9Sstevel@tonic-gate
433*7c478bd9Sstevel@tonic-gate lockp = SH_LIST_FIRST(&lockerp->heldby, __db_lock);
434*7c478bd9Sstevel@tonic-gate
435*7c478bd9Sstevel@tonic-gate /*
436*7c478bd9Sstevel@tonic-gate * It's possible that this locker was already aborted.
437*7c478bd9Sstevel@tonic-gate * If that's the case, make sure that we remove its
438*7c478bd9Sstevel@tonic-gate * locker from the hash table.
439*7c478bd9Sstevel@tonic-gate */
440*7c478bd9Sstevel@tonic-gate if (lockp == NULL) {
441*7c478bd9Sstevel@tonic-gate HASHREMOVE_EL(lt->hashtab, __db_lockobj,
442*7c478bd9Sstevel@tonic-gate links, lockerp, lt->region->table_size, __lock_lhash);
443*7c478bd9Sstevel@tonic-gate SH_TAILQ_INSERT_HEAD(<->region->free_objs,
444*7c478bd9Sstevel@tonic-gate lockerp, links, __db_lockobj);
445*7c478bd9Sstevel@tonic-gate lt->region->nlockers--;
446*7c478bd9Sstevel@tonic-gate goto out;
447*7c478bd9Sstevel@tonic-gate } else if (LOCK_TO_OFFSET(lt, lockp) != info->last_lock ||
448*7c478bd9Sstevel@tonic-gate lockp->status != DB_LSTAT_WAITING)
449*7c478bd9Sstevel@tonic-gate goto out;
450*7c478bd9Sstevel@tonic-gate
451*7c478bd9Sstevel@tonic-gate /* Abort lock, take it off list, and wake up this lock. */
452*7c478bd9Sstevel@tonic-gate lockp->status = DB_LSTAT_ABORTED;
453*7c478bd9Sstevel@tonic-gate lt->region->ndeadlocks++;
454*7c478bd9Sstevel@tonic-gate SH_LIST_REMOVE(lockp, locker_links, __db_lock);
455*7c478bd9Sstevel@tonic-gate sh_obj = (DB_LOCKOBJ *)((u_int8_t *)lockp + lockp->obj);
456*7c478bd9Sstevel@tonic-gate SH_TAILQ_REMOVE(&sh_obj->waiters, lockp, links, __db_lock);
457*7c478bd9Sstevel@tonic-gate (void)__db_mutex_unlock(&lockp->mutex, lt->reginfo.fd);
458*7c478bd9Sstevel@tonic-gate
459*7c478bd9Sstevel@tonic-gate ret = 0;
460*7c478bd9Sstevel@tonic-gate
461*7c478bd9Sstevel@tonic-gate out: UNLOCK_LOCKREGION(lt);
462*7c478bd9Sstevel@tonic-gate return (ret);
463*7c478bd9Sstevel@tonic-gate }
464*7c478bd9Sstevel@tonic-gate
465*7c478bd9Sstevel@tonic-gate #ifdef DIAGNOSTIC
466*7c478bd9Sstevel@tonic-gate static void
__dd_debug(dbenv,idmap,bitmap,nlockers)467*7c478bd9Sstevel@tonic-gate __dd_debug(dbenv, idmap, bitmap, nlockers)
468*7c478bd9Sstevel@tonic-gate DB_ENV *dbenv;
469*7c478bd9Sstevel@tonic-gate locker_info *idmap;
470*7c478bd9Sstevel@tonic-gate u_int32_t *bitmap, nlockers;
471*7c478bd9Sstevel@tonic-gate {
472*7c478bd9Sstevel@tonic-gate u_int32_t i, j, *mymap, nentries;
473*7c478bd9Sstevel@tonic-gate int ret;
474*7c478bd9Sstevel@tonic-gate char *msgbuf;
475*7c478bd9Sstevel@tonic-gate
476*7c478bd9Sstevel@tonic-gate __db_err(dbenv, "Waitsfor array");
477*7c478bd9Sstevel@tonic-gate __db_err(dbenv, "waiter\twaiting on");
478*7c478bd9Sstevel@tonic-gate
479*7c478bd9Sstevel@tonic-gate /* Allocate space to print 10 bytes per item waited on. */
480*7c478bd9Sstevel@tonic-gate #undef MSGBUF_LEN
481*7c478bd9Sstevel@tonic-gate #define MSGBUF_LEN ((nlockers + 1) * 10 + 64)
482*7c478bd9Sstevel@tonic-gate if ((ret = __os_malloc(MSGBUF_LEN, NULL, &msgbuf)) != 0)
483*7c478bd9Sstevel@tonic-gate return;
484*7c478bd9Sstevel@tonic-gate
485*7c478bd9Sstevel@tonic-gate nentries = ALIGN(nlockers, 32) / 32;
486*7c478bd9Sstevel@tonic-gate for (mymap = bitmap, i = 0; i < nlockers; i++, mymap += nentries) {
487*7c478bd9Sstevel@tonic-gate if (!idmap[i].valid)
488*7c478bd9Sstevel@tonic-gate continue;
489*7c478bd9Sstevel@tonic-gate sprintf(msgbuf, /* Waiter. */
490*7c478bd9Sstevel@tonic-gate "%lx/%lu:\t", (u_long)idmap[i].id, (u_long)idmap[i].pgno);
491*7c478bd9Sstevel@tonic-gate for (j = 0; j < nlockers; j++)
492*7c478bd9Sstevel@tonic-gate if (ISSET_MAP(mymap, j))
493*7c478bd9Sstevel@tonic-gate sprintf(msgbuf, "%s %lx", msgbuf,
494*7c478bd9Sstevel@tonic-gate (u_long)idmap[j].id);
495*7c478bd9Sstevel@tonic-gate (void)sprintf(msgbuf,
496*7c478bd9Sstevel@tonic-gate "%s %lu", msgbuf, (u_long)idmap[i].last_lock);
497*7c478bd9Sstevel@tonic-gate __db_err(dbenv, msgbuf);
498*7c478bd9Sstevel@tonic-gate }
499*7c478bd9Sstevel@tonic-gate
500*7c478bd9Sstevel@tonic-gate __os_free(msgbuf, MSGBUF_LEN);
501*7c478bd9Sstevel@tonic-gate }
502*7c478bd9Sstevel@tonic-gate #endif
503