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