lock_deadlock.c

00001 /*-
00002  * See the file LICENSE for redistribution information.
00003  *
00004  * Copyright (c) 1996, 1997, 1998, 1999, 2000
00005  * Sleepycat Software. All rights reserved.
00006  */
00007 
00008 #include "config.h"
00009 
00010 #ifndef lint
00011 static const char revid[] = "$Id: lock__deadlock_8c-source.html,v 1.1 2008年06月08日 10:19:57 sebdiaz Exp $";
00012 #endif /* not lint */
00013 
00014 #ifndef NO_SYSTEM_INCLUDES
00015 #include <sys/types.h>
00016 
00017 #include <errno.h>
00018 #include <string.h>
00019 #endif
00020 
00021 #ifdef HAVE_RPC
00022 #include "db_server.h"
00023 #endif
00024 
00025 #include "db_int.h"
00026 #include "db_shash.h"
00027 #include "lock.h"
00028 #include "txn.h"
00029 
00030 #ifdef HAVE_RPC
00031 #include "gen_client_ext.h"
00032 #include "rpc_client_ext.h"
00033 #endif
00034 
00035 #define ISSET_MAP(M, N) ((M)[(N) / 32] & (1 << (N) % 32))
00036 
00037 #define CLEAR_MAP(M, N) { \
00038  u_int32_t __i; \
00039  for (__i = 0; __i < (N); __i++) \
00040  (M)[__i] = 0; \
00041 }
00042 
00043 #define SET_MAP(M, B) ((M)[(B) / 32] |= (1 << ((B) % 32)))
00044 #define CLR_MAP(M, B) ((M)[(B) / 32] &= ~(1 << ((B) % 32)))
00045 
00046 #define OR_MAP(D, S, N) { \
00047  u_int32_t __i; \
00048  for (__i = 0; __i < (N); __i++) \
00049  D[__i] |= S[__i]; \
00050 }
00051 #define BAD_KILLID 0xffffffff
00052 
00053 typedef struct {
00054 int valid;
00055 u_int32_t id;
00056 u_int32_t last_lock;
00057 u_int32_t last_locker_id;
00058 db_pgno_t pgno;
00059 } locker_info;
00060 
00061 static int __dd_abort __P((DB_ENV *, locker_info *));
00062 static int __dd_build
00063 __P((DB_ENV *, u_int32_t **, u_int32_t *, locker_info **));
00064 static int __dd_find
00065 __P((DB_ENV *,u_int32_t *, locker_info *, u_int32_t, u_int32_t ***));
00066 
00067 #ifdef DIAGNOSTIC
00068 static void __dd_debug __P((DB_ENV *, locker_info *, u_int32_t *, u_int32_t));
00069 #endif
00070 
00071 int
00072 CDB_lock_detect(dbenv, flags, atype, abortp)
00073 DB_ENV *dbenv;
00074 u_int32_t flags, atype;
00075 int *abortp;
00076 {
00077 DB_LOCKREGION *region;
00078 DB_LOCKTAB *lt;
00079 locker_info *idmap;
00080 u_int32_t *bitmap, **deadp, **free_me, i, killid, nentries, nlockers;
00081 int do_pass, ret;
00082 
00083 #ifdef HAVE_RPC
00084 if (F_ISSET(dbenv, DB_ENV_RPCCLIENT))
00085 return (__dbcl_lock_detect(dbenv, flags, atype, abortp));
00086 #endif
00087 
00088 PANIC_CHECK(dbenv);
00089 ENV_REQUIRES_CONFIG(dbenv, dbenv->lk_handle, DB_INIT_LOCK);
00090 
00091 lt = dbenv->lk_handle;
00092 if (abortp != NULL)
00093 *abortp = 0;
00094 
00095 /* Validate arguments. */
00096 if ((ret =
00097 CDB___db_fchk(dbenv, "CDB_lock_detect", flags, DB_LOCK_CONFLICT)) != 0)
00098 return (ret);
00099 
00100 /* Check if a detector run is necessary. */
00101 LOCKREGION(dbenv, lt);
00102 if (LF_ISSET(DB_LOCK_CONFLICT)) {
00103 /* Make a pass every time a lock waits. */
00104 region = lt->reginfo.primary;
00105 do_pass = region->need_dd != 0;
00106 
00107 if (!do_pass) {
00108 UNLOCKREGION(dbenv, lt);
00109 return (0);
00110 }
00111 }
00112 
00113 /* Build the waits-for bitmap. */
00114 ret = __dd_build(dbenv, &bitmap, &nlockers, &idmap);
00115 UNLOCKREGION(dbenv, lt);
00116 if (ret != 0)
00117 return (ret);
00118 
00119 if (nlockers == 0)
00120 return (0);
00121 #ifdef DIAGNOSTIC
00122 if (FLD_ISSET(dbenv->verbose, DB_VERB_WAITSFOR))
00123 __dd_debug(dbenv, idmap, bitmap, nlockers);
00124 #endif
00125 /* Find a deadlock. */
00126 if ((ret = __dd_find(dbenv, bitmap, idmap, nlockers, &deadp)) != 0)
00127 return (ret);
00128 
00129 nentries = ALIGN(nlockers, 32) / 32;
00130 killid = BAD_KILLID;
00131 free_me = deadp;
00132 for (; *deadp != NULL; deadp++) {
00133 if (abortp != NULL)
00134 ++*abortp;
00135 switch (atype) { /* Kill someone. */
00136 case DB_LOCK_OLDEST:
00137 /*
00138  * Find the first bit set in the current
00139  * array and then look for a lower tid in
00140  * the array.
00141  */
00142 for (i = 0; i < nlockers; i++)
00143 if (ISSET_MAP(*deadp, i)) {
00144 killid = i;
00145 break;
00146 
00147 }
00148 /*
00149  * It's conceivable that under XA, the locker could
00150  * have gone away.
00151  */
00152 if (killid == BAD_KILLID)
00153 break;
00154 
00155 /*
00156  * The oldest transaction has the lowest
00157  * transaction id.
00158  */
00159 for (i = killid + 1; i < nlockers; i++)
00160 if (ISSET_MAP(*deadp, i) &&
00161 idmap[i].id < idmap[killid].id)
00162 killid = i;
00163 break;
00164 case DB_LOCK_DEFAULT:
00165 case DB_LOCK_RANDOM:
00166 /*
00167  * We are trying to calculate the id of the
00168  * locker whose entry is indicated by deadlock.
00169  */
00170 killid = (*deadp - bitmap) / nentries;
00171 break;
00172 case DB_LOCK_YOUNGEST:
00173 /*
00174  * Find the first bit set in the current
00175  * array and then look for a lower tid in
00176  * the array.
00177  */
00178 for (i = 0; i < nlockers; i++)
00179 if (ISSET_MAP(*deadp, i)) {
00180 killid = i;
00181 break;
00182 }
00183 
00184 /*
00185  * It's conceivable that under XA, the locker could
00186  * have gone away.
00187  */
00188 if (killid == BAD_KILLID)
00189 break;
00190 
00191 /*
00192  * The youngest transaction has the highest
00193  * transaction id.
00194  */
00195 for (i = killid + 1; i < nlockers; i++)
00196 if (ISSET_MAP(*deadp, i) &&
00197 idmap[i].id > idmap[killid].id)
00198 killid = i;
00199 break;
00200 default:
00201 killid = BAD_KILLID;
00202 ret = EINVAL;
00203 }
00204 
00205 if (killid == BAD_KILLID)
00206 continue;
00207 
00208 /* Kill the locker with lockid idmap[killid]. */
00209 if ((ret = __dd_abort(dbenv, &idmap[killid])) != 0) {
00210 /*
00211  * It's possible that the lock was already aborted;
00212  * this isn't necessarily a problem, so do not treat
00213  * it as an error.
00214  */
00215 if (ret == EINVAL)
00216 ret = 0;
00217 else
00218 CDB___db_err(dbenv,
00219 "warning: unable to abort locker %lx",
00220 (u_long)idmap[killid].id);
00221 } else if (FLD_ISSET(dbenv->verbose, DB_VERB_DEADLOCK))
00222 CDB___db_err(dbenv,
00223 "Aborting locker %lx", (u_long)idmap[killid].id);
00224 }
00225 CDB___os_free(free_me, 0);
00226 CDB___os_free(bitmap, 0);
00227 CDB___os_free(idmap, 0);
00228 
00229 return (ret);
00230 }
00231 
00232 /*
00233  * ========================================================================
00234  * Utilities
00235  */
00236 
00237 # define DD_INVALID_ID ((u_int32_t) -1)
00238 
00239 static int
00240 __dd_build(dbenv, bmp, nlockers, idmap)
00241 DB_ENV *dbenv;
00242 u_int32_t **bmp, *nlockers;
00243 locker_info **idmap;
00244 {
00245 struct __db_lock *lp;
00246 DB_LOCKER *lip, *lockerp, *child;
00247 DB_LOCKOBJ *op, *lo;
00248 DB_LOCKREGION *region;
00249 DB_LOCKTAB *lt;
00250 locker_info *id_array;
00251 u_int32_t *bitmap, count, dd, *entryp, i, id, ndx, nentries, *tmpmap;
00252 u_int8_t *pptr;
00253 int is_first, ret;
00254 
00255 lt = dbenv->lk_handle;
00256 region = lt->reginfo.primary;
00257 
00258 /*
00259  * We'll check how many lockers there are, add a few more in for
00260  * good measure and then allocate all the structures. Then we'll
00261  * verify that we have enough room when we go back in and get the
00262  * mutex the second time.
00263  */
00264 retry: count = region->nlockers;
00265 region->need_dd = 0;
00266 
00267 if (count == 0) {
00268 *nlockers = 0;
00269 return (0);
00270 }
00271 
00272 if (FLD_ISSET(dbenv->verbose, DB_VERB_DEADLOCK))
00273 CDB___db_err(dbenv, "%lu lockers", (u_long)count);
00274 
00275 count += 40;
00276 nentries = ALIGN(count, 32) / 32;
00277 
00278 /*
00279  * Allocate enough space for a count by count bitmap matrix.
00280  *
00281  * XXX
00282  * We can probably save the malloc's between iterations just
00283  * reallocing if necessary because count grew by too much.
00284  */
00285 if ((ret = CDB___os_calloc(dbenv, (size_t)count,
00286 sizeof(u_int32_t) * nentries, &bitmap)) != 0)
00287 return (ret);
00288 
00289 if ((ret = CDB___os_calloc(dbenv,
00290 sizeof(u_int32_t), nentries, &tmpmap)) != 0) {
00291 CDB___os_free(bitmap, sizeof(u_int32_t) * nentries);
00292 return (ret);
00293 }
00294 
00295 if ((ret = CDB___os_calloc(dbenv,
00296 (size_t)count, sizeof(locker_info), &id_array)) != 0) {
00297 CDB___os_free(bitmap, count * sizeof(u_int32_t) * nentries);
00298 CDB___os_free(tmpmap, sizeof(u_int32_t) * nentries);
00299 return (ret);
00300 }
00301 
00302 /*
00303  * Now go back in and actually fill in the matrix.
00304  */
00305 if (region->nlockers > count) {
00306 CDB___os_free(bitmap, count * sizeof(u_int32_t) * nentries);
00307 CDB___os_free(tmpmap, sizeof(u_int32_t) * nentries);
00308 CDB___os_free(id_array, count * sizeof(locker_info));
00309 goto retry;
00310 }
00311 
00312 /*
00313  * First we go through and assign each locker a deadlock detector id.
00314  */
00315 for (id = 0, i = 0; i < region->table_size; i++) {
00316 for (lip = SH_TAILQ_FIRST(&lt->locker_tab[i], __db_locker);
00317 lip != NULL; lip = SH_TAILQ_NEXT(lip, links, __db_locker))
00318 if (lip->master_locker == INVALID_ROFF) {
00319 lip->dd_id = id++;
00320 id_array[lip->dd_id].id = lip->id;
00321 } else
00322 lip->dd_id = DD_INVALID_ID;
00323 }
00324 
00325 /*
00326  * We only need consider objects that have waiters, so we use
00327  * the list of objects with waiters (dd_objs) instead of traversing
00328  * the entire hash table. For each object, we traverse the waiters
00329  * list and add an entry in the waitsfor matrix for each waiter/holder
00330  * combination.
00331  */
00332 for (op = SH_TAILQ_FIRST(&region->dd_objs, __db_lockobj);
00333 op != NULL; op = SH_TAILQ_NEXT(op, dd_links, __db_lockobj)) {
00334 CLEAR_MAP(tmpmap, nentries);
00335 
00336 /*
00337  * First we go through and create a bit map that
00338  * represents all the holders of this object.
00339  */
00340 for (lp = SH_TAILQ_FIRST(&op->holders, __db_lock);
00341 lp != NULL;
00342 lp = SH_TAILQ_NEXT(lp, links, __db_lock)) {
00343 ndx = CDB___lock_locker_hash(lp->holder) %
00344 region->table_size;
00345 if ((ret = CDB___lock_getlocker(lt,
00346 lp->holder, ndx, 0, &lockerp)) != 0)
00347 continue;
00348 if (lockerp->dd_id == DD_INVALID_ID)
00349 dd = ((DB_LOCKER *)
00350 R_ADDR(&lt->reginfo,
00351 lockerp->master_locker))->dd_id;
00352 else
00353 dd = lockerp->dd_id;
00354 id_array[dd].valid = 1;
00355 
00356 /*
00357  * If the holder has already been aborted, then
00358  * we should ignore it for now.
00359  */
00360 if (lp->status == DB_LSTAT_HELD)
00361 SET_MAP(tmpmap, dd);
00362 }
00363 
00364 /*
00365  * Next, for each waiter, we set its row in the matrix
00366  * equal to the map of holders we set up above.
00367  */
00368 for (is_first = 1,
00369 lp = SH_TAILQ_FIRST(&op->waiters, __db_lock);
00370 lp != NULL;
00371 is_first = 0,
00372 lp = SH_TAILQ_NEXT(lp, links, __db_lock)) {
00373 ndx = CDB___lock_locker_hash(lp->holder) %
00374 region->table_size;
00375 if ((ret = CDB___lock_getlocker(lt,
00376 lp->holder, ndx, 0, &lockerp)) != 0)
00377 continue;
00378 if (lockerp->dd_id == DD_INVALID_ID)
00379 dd = ((DB_LOCKER *)
00380 R_ADDR(&lt->reginfo,
00381 lockerp->master_locker))->dd_id;
00382 else
00383 dd = lockerp->dd_id;
00384 id_array[dd].valid = 1;
00385 
00386 /*
00387  * If the transaction is pending abortion, then
00388  * ignore it on this iteration.
00389  */
00390 if (lp->status != DB_LSTAT_WAITING)
00391 continue;
00392 
00393 entryp = bitmap + (nentries * dd);
00394 OR_MAP(entryp, tmpmap, nentries);
00395 /*
00396  * If this is the first waiter on the queue,
00397  * then we remove the waitsfor relationship
00398  * with oneself. However, if it's anywhere
00399  * else on the queue, then we have to keep
00400  * it and we have an automatic deadlock.
00401  */
00402 if (is_first)
00403 CLR_MAP(entryp, dd);
00404 }
00405 }
00406 
00407 /* Now for each locker; record its last lock. */
00408 for (id = 0; id < count; id++) {
00409 if (!id_array[id].valid)
00410 continue;
00411 ndx = CDB___lock_locker_hash(id_array[id].id) % region->table_size;
00412 if ((ret = CDB___lock_getlocker(lt,
00413 id_array[id].id, ndx, 0, &lockerp)) != 0) {
00414 CDB___db_err(dbenv,
00415 "No locks for locker %lu", (u_long)id_array[id].id);
00416 continue;
00417 }
00418 
00419 /*
00420  * If this is a master transaction, try to
00421  * find one of its children's locks first,
00422  * as they are probably more recent.
00423  */
00424 child = SH_LIST_FIRST(&lockerp->child_locker, __db_locker);
00425 if (child != NULL) {
00426 do {
00427 lp = SH_LIST_FIRST(&child->heldby, __db_lock);
00428 if (lp != NULL &&
00429 lp->status == DB_LSTAT_WAITING) {
00430 id_array[id].last_locker_id = child->id;
00431 goto get_lock;
00432 }
00433 child = SH_LIST_NEXT(
00434 child, child_link, __db_locker);
00435 } while (child != NULL);
00436 }
00437 lp = SH_LIST_FIRST(&lockerp->heldby, __db_lock);
00438 if (lp != NULL) {
00439 id_array[id].last_locker_id = lockerp->id;
00440 get_lock: id_array[id].last_lock = R_OFFSET(&lt->reginfo, lp);
00441 lo = (DB_LOCKOBJ *)((u_int8_t *)lp + lp->obj);
00442 pptr = SH_DBT_PTR(&lo->lockobj);
00443 if (lo->lockobj.size >= sizeof(db_pgno_t))
00444 memcpy(&id_array[id].pgno,
00445 pptr, sizeof(db_pgno_t));
00446 else
00447 id_array[id].pgno = 0;
00448 }
00449 }
00450 
00451 /* Pass complete, reset the deadlock detector bit. */
00452 region->need_dd = 0;
00453 
00454 /*
00455  * Now we can release everything except the bitmap matrix that we
00456  * created.
00457  */
00458 *nlockers = id;
00459 *idmap = id_array;
00460 *bmp = bitmap;
00461 CDB___os_free(tmpmap, sizeof(u_int32_t) * nentries);
00462 return (0);
00463 }
00464 
00465 static int
00466 __dd_find(dbenv, bmp, idmap, nlockers, deadp)
00467 DB_ENV *dbenv;
00468 u_int32_t *bmp, nlockers;
00469 locker_info *idmap;
00470 u_int32_t ***deadp;
00471 {
00472 u_int32_t i, j, k, nentries, *mymap, *tmpmap;
00473 u_int32_t **retp;
00474 int ndead, ndeadalloc, ret;
00475 
00476 #undef INITIAL_DEAD_ALLOC
00477 #define INITIAL_DEAD_ALLOC 8
00478 
00479 ndeadalloc = INITIAL_DEAD_ALLOC;
00480 ndead = 0;
00481 if ((ret = CDB___os_malloc(dbenv,
00482 ndeadalloc * sizeof(u_int32_t *), NULL, &retp)) != 0)
00483 return (ret);
00484 
00485 /*
00486  * For each locker, OR in the bits from the lockers on which that
00487  * locker is waiting.
00488  */
00489 nentries = ALIGN(nlockers, 32) / 32;
00490 for (mymap = bmp, i = 0; i < nlockers; i++, mymap += nentries) {
00491 if (!idmap[i].valid)
00492 continue;
00493 for (j = 0; j < nlockers; j++) {
00494 if (!ISSET_MAP(mymap, j))
00495 continue;
00496 
00497 /* Find the map for this bit. */
00498 tmpmap = bmp + (nentries * j);
00499 OR_MAP(mymap, tmpmap, nentries);
00500 if (!ISSET_MAP(mymap, i))
00501 continue;
00502 
00503 /* Make sure we leave room for NULL. */
00504 if (ndead + 2 >= ndeadalloc) {
00505 ndeadalloc <<= 1;
00506 /*
00507  * If the alloc fails, then simply return the
00508  * deadlocks that we already have.
00509  */
00510 if (CDB___os_realloc(dbenv,
00511 ndeadalloc * sizeof(u_int32_t),
00512 NULL, &retp) != 0) {
00513 retp[ndead] = NULL;
00514 *deadp = retp;
00515 return (0);
00516 }
00517 }
00518 retp[ndead++] = mymap;
00519 
00520 /* Mark all participants in this deadlock invalid. */
00521 for (k = 0; k < nlockers; k++)
00522 if (ISSET_MAP(mymap, k))
00523 idmap[k].valid = 0;
00524 break;
00525 }
00526 }
00527 retp[ndead] = NULL;
00528 *deadp = retp;
00529 return (0);
00530 }
00531 
00532 static int
00533 __dd_abort(dbenv, info)
00534 DB_ENV *dbenv;
00535 locker_info *info;
00536 {
00537 struct __db_lock *lockp;
00538 DB_LOCKER *lockerp;
00539 DB_LOCKOBJ *sh_obj;
00540 DB_LOCKREGION *region;
00541 DB_LOCKTAB *lt;
00542 u_int32_t ndx;
00543 int ret;
00544 
00545 lt = dbenv->lk_handle;
00546 region = lt->reginfo.primary;
00547 
00548 LOCKREGION(dbenv, lt);
00549 /* Find the locker's last lock. */
00550 ndx = CDB___lock_locker_hash(info->last_locker_id) % region->table_size;
00551 if ((ret = CDB___lock_getlocker(lt,
00552 info->last_locker_id, ndx, 0, &lockerp)) != 0 || lockerp == NULL) {
00553 if (ret == 0)
00554 ret = EINVAL;
00555 goto out;
00556 }
00557 
00558 lockp = SH_LIST_FIRST(&lockerp->heldby, __db_lock);
00559 
00560 /*
00561  * It's possible that this locker was already aborted. If that's
00562  * the case, make sure that we remove its locker from the hash table.
00563  */
00564 if (lockp == NULL) {
00565 if (LOCKER_FREEABLE(lockerp)) {
00566 CDB___lock_freelocker(lt, region, lockerp, ndx);
00567 goto out;
00568 }
00569 } else if (R_OFFSET(&lt->reginfo, lockp) != info->last_lock ||
00570 lockp->status != DB_LSTAT_WAITING) {
00571 ret = EINVAL;
00572 goto out;
00573 }
00574 
00575 sh_obj = (DB_LOCKOBJ *)((u_int8_t *)lockp + lockp->obj);
00576 SH_LIST_REMOVE(lockp, locker_links, __db_lock);
00577 
00578 /* Abort lock, take it off list, and wake up this lock. */
00579 SHOBJECT_LOCK(lt, region, sh_obj, ndx);
00580 lockp->status = DB_LSTAT_ABORTED;
00581 SH_TAILQ_REMOVE(&sh_obj->waiters, lockp, links, __db_lock);
00582 
00583 /*
00584  * Either the waiters list is now empty, in which case we remove
00585  * it from dd_objs, or it is not empty, in which case we need to
00586  * do promotion.
00587  */
00588 if (SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock) == NULL)
00589 SH_TAILQ_REMOVE(&region->dd_objs,
00590 sh_obj, dd_links, __db_lockobj);
00591 else
00592 ret = CDB___lock_promote(lt, sh_obj);
00593 MUTEX_UNLOCK(&lockp->mutex);
00594 
00595 region->ndeadlocks++;
00596 UNLOCKREGION(dbenv, lt);
00597 
00598 return (0);
00599 
00600 out: UNLOCKREGION(dbenv, lt);
00601 return (ret);
00602 }
00603 
00604 #ifdef DIAGNOSTIC
00605 static void
00606 __dd_debug(dbenv, idmap, bitmap, nlockers)
00607 DB_ENV *dbenv;
00608 locker_info *idmap;
00609 u_int32_t *bitmap, nlockers;
00610 {
00611 u_int32_t i, j, *mymap, nentries;
00612 int ret;
00613 char *msgbuf;
00614 
00615 CDB___db_err(dbenv, "Waitsfor array\nWaiter:\tWaiting on:");
00616 
00617 /* Allocate space to print 10 bytes per item waited on. */
00618 #undef MSGBUF_LEN
00619 #define MSGBUF_LEN ((nlockers + 1) * 10 + 64)
00620 if ((ret = CDB___os_malloc(dbenv, MSGBUF_LEN, NULL, &msgbuf)) != 0)
00621 return;
00622 
00623 nentries = ALIGN(nlockers, 32) / 32;
00624 for (mymap = bitmap, i = 0; i < nlockers; i++, mymap += nentries) {
00625 if (!idmap[i].valid)
00626 continue;
00627 sprintf(msgbuf, /* Waiter. */
00628 "%lx/%lu:\t", (u_long)idmap[i].id, (u_long)idmap[i].pgno);
00629 for (j = 0; j < nlockers; j++)
00630 if (ISSET_MAP(mymap, j))
00631 sprintf(msgbuf, "%s %lx", msgbuf,
00632 (u_long)idmap[j].id);
00633 (void)sprintf(msgbuf,
00634 "%s %lu", msgbuf, (u_long)idmap[i].last_lock);
00635 CDB___db_err(dbenv, msgbuf);
00636 }
00637 
00638 CDB___os_free(msgbuf, MSGBUF_LEN);
00639 }
00640 #endif