00001
00002
00003
00004
00005
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
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
00096 if ((ret =
00097 CDB___db_fchk(dbenv, "CDB_lock_detect", flags, DB_LOCK_CONFLICT)) != 0)
00098 return (ret);
00099
00100
00101 LOCKREGION(dbenv, lt);
00102 if (LF_ISSET(DB_LOCK_CONFLICT)) {
00103
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
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
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) {
00136 case DB_LOCK_OLDEST:
00137
00138
00139
00140
00141
00142 for (i = 0; i < nlockers; i++)
00143 if (ISSET_MAP(*deadp, i)) {
00144 killid = i;
00145 break;
00146
00147 }
00148
00149
00150
00151
00152 if (killid == BAD_KILLID)
00153 break;
00154
00155
00156
00157
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
00168
00169
00170 killid = (*deadp - bitmap) / nentries;
00171 break;
00172 case DB_LOCK_YOUNGEST:
00173
00174
00175
00176
00177
00178 for (i = 0; i < nlockers; i++)
00179 if (ISSET_MAP(*deadp, i)) {
00180 killid = i;
00181 break;
00182 }
00183
00184
00185
00186
00187
00188 if (killid == BAD_KILLID)
00189 break;
00190
00191
00192
00193
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
00209 if ((ret = __dd_abort(dbenv, &idmap[killid])) != 0) {
00210
00211
00212
00213
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
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
00260
00261
00262
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
00280
00281
00282
00283
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
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
00314
00315 for (id = 0, i = 0; i < region->table_size; i++) {
00316 for (lip = SH_TAILQ_FIRST(<->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
00327
00328
00329
00330
00331
00332 for (op = SH_TAILQ_FIRST(®ion->dd_objs, __db_lockobj);
00333 op != NULL; op = SH_TAILQ_NEXT(op, dd_links, __db_lockobj)) {
00334 CLEAR_MAP(tmpmap, nentries);
00335
00336
00337
00338
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(<->reginfo,
00351 lockerp->master_locker))->dd_id;
00352 else
00353 dd = lockerp->dd_id;
00354 id_array[dd].valid = 1;
00355
00356
00357
00358
00359
00360 if (lp->status == DB_LSTAT_HELD)
00361 SET_MAP(tmpmap, dd);
00362 }
00363
00364
00365
00366
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(<->reginfo,
00381 lockerp->master_locker))->dd_id;
00382 else
00383 dd = lockerp->dd_id;
00384 id_array[dd].valid = 1;
00385
00386
00387
00388
00389
00390 if (lp->status != DB_LSTAT_WAITING)
00391 continue;
00392
00393 entryp = bitmap + (nentries * dd);
00394 OR_MAP(entryp, tmpmap, nentries);
00395
00396
00397
00398
00399
00400
00401
00402 if (is_first)
00403 CLR_MAP(entryp, dd);
00404 }
00405 }
00406
00407
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
00421
00422
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(<->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
00452 region->need_dd = 0;
00453
00454
00455
00456
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
00487
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
00498 tmpmap = bmp + (nentries * j);
00499 OR_MAP(mymap, tmpmap, nentries);
00500 if (!ISSET_MAP(mymap, i))
00501 continue;
00502
00503
00504 if (ndead + 2 >= ndeadalloc) {
00505 ndeadalloc <<= 1;
00506
00507
00508
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
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
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
00562
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(<->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
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
00585
00586
00587
00588 if (SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock) == NULL)
00589 SH_TAILQ_REMOVE(®ion->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
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,
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