lock_deadlock.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:23k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /*-
  2.  * See the file LICENSE for redistribution information.
  3.  *
  4.  * Copyright (c) 1996-2002
  5.  * Sleepycat Software.  All rights reserved.
  6.  */
  7. #include "db_config.h"
  8. #ifndef lint
  9. static const char revid[] = "$Id: lock_deadlock.c,v 11.54 2002/08/06 05:05:21 bostic Exp $";
  10. #endif /* not lint */
  11. #ifndef NO_SYSTEM_INCLUDES
  12. #include <sys/types.h>
  13. #include <string.h>
  14. #endif
  15. #include "db_int.h"
  16. #include "dbinc/db_shash.h"
  17. #include "dbinc/lock.h"
  18. #include "dbinc/txn.h"
  19. #include "dbinc/rep.h"
  20. #define ISSET_MAP(M, N) ((M)[(N) / 32] & (1 << (N) % 32))
  21. #define CLEAR_MAP(M, N) {
  22. u_int32_t __i;
  23. for (__i = 0; __i < (N); __i++)
  24. (M)[__i] = 0;
  25. }
  26. #define SET_MAP(M, B) ((M)[(B) / 32] |= (1 << ((B) % 32)))
  27. #define CLR_MAP(M, B) ((M)[(B) / 32] &= ~(1 << ((B) % 32)))
  28. #define OR_MAP(D, S, N) {
  29. u_int32_t __i;
  30. for (__i = 0; __i < (N); __i++)
  31. D[__i] |= S[__i];
  32. }
  33. #define BAD_KILLID 0xffffffff
  34. typedef struct {
  35. int valid;
  36. int self_wait;
  37. u_int32_t count;
  38. u_int32_t id;
  39. u_int32_t last_lock;
  40. u_int32_t last_locker_id;
  41. db_pgno_t pgno;
  42. } locker_info;
  43. static int  __dd_abort __P((DB_ENV *, locker_info *));
  44. static int  __dd_build __P((DB_ENV *,
  45.     u_int32_t, u_int32_t **, u_int32_t *, u_int32_t *, locker_info **));
  46. static int  __dd_find __P((DB_ENV *,
  47.     u_int32_t *, locker_info *, u_int32_t, u_int32_t, u_int32_t ***));
  48. static int  __dd_isolder __P((u_int32_t, u_int32_t, u_int32_t, u_int32_t));
  49. static int __dd_verify __P((locker_info *, u_int32_t *, u_int32_t *,
  50.     u_int32_t *, u_int32_t, u_int32_t, u_int32_t));
  51. #ifdef DIAGNOSTIC
  52. static void __dd_debug
  53.     __P((DB_ENV *, locker_info *, u_int32_t *, u_int32_t, u_int32_t));
  54. #endif
  55. /*
  56.  * lock_detect --
  57.  *
  58.  * PUBLIC: int __lock_detect __P((DB_ENV *, u_int32_t, u_int32_t, int *));
  59.  */
  60. int
  61. __lock_detect(dbenv, flags, atype, abortp)
  62. DB_ENV *dbenv;
  63. u_int32_t flags, atype;
  64. int *abortp;
  65. {
  66. DB_LOCKREGION *region;
  67. DB_LOCKTAB *lt;
  68. DB_TXNMGR *tmgr;
  69. locker_info *idmap;
  70. u_int32_t *bitmap, *copymap, **deadp, **free_me, *tmpmap;
  71. u_int32_t i, keeper, killid, limit, nalloc, nlockers;
  72. u_int32_t lock_max, txn_max;
  73. int ret;
  74. PANIC_CHECK(dbenv);
  75. ENV_REQUIRES_CONFIG(dbenv,
  76.     dbenv->lk_handle, "DB_ENV->lock_detect", DB_INIT_LOCK);
  77. /* Validate arguments. */
  78. if ((ret = __db_fchk(dbenv, "DB_ENV->lock_detect", flags, 0)) != 0)
  79. return (ret);
  80. switch (atype) {
  81. case DB_LOCK_DEFAULT:
  82. case DB_LOCK_EXPIRE:
  83. case DB_LOCK_MAXLOCKS:
  84. case DB_LOCK_MINLOCKS:
  85. case DB_LOCK_MINWRITE:
  86. case DB_LOCK_OLDEST:
  87. case DB_LOCK_RANDOM:
  88. case DB_LOCK_YOUNGEST:
  89. break;
  90. default:
  91. __db_err(dbenv,
  92.     "DB_ENV->lock_detect: unknown deadlock detection mode specified");
  93. return (EINVAL);
  94. }
  95. /*
  96.  * If this environment is a replication client, then we must use the
  97.  * MINWRITE detection discipline.
  98.  */
  99. if (__rep_is_client(dbenv))
  100. atype = DB_LOCK_MINWRITE;
  101. free_me = NULL;
  102. lt = dbenv->lk_handle;
  103. if (abortp != NULL)
  104. *abortp = 0;
  105. /* Check if a detector run is necessary. */
  106. LOCKREGION(dbenv, lt);
  107. /* Make a pass only if auto-detect would run. */
  108. region = lt->reginfo.primary;
  109. if (region->need_dd == 0) {
  110. UNLOCKREGION(dbenv, lt);
  111. return (0);
  112. }
  113. /* Reset need_dd, so we know we've run the detector. */
  114. region->need_dd = 0;
  115. /* Build the waits-for bitmap. */
  116. ret = __dd_build(dbenv, atype, &bitmap, &nlockers, &nalloc, &idmap);
  117. lock_max = region->stat.st_cur_maxid;
  118. UNLOCKREGION(dbenv, lt);
  119. /*
  120.  * We need the cur_maxid from the txn region as well.  In order
  121.  * to avoid tricky synchronization between the lock and txn
  122.  * regions, we simply unlock the lock region and then lock the
  123.  * txn region.  This introduces a small window during which the
  124.  * transaction system could then wrap.  We're willing to return
  125.  * the wrong answer for "oldest" or "youngest" in those rare
  126.  * circumstances.
  127.  */
  128. tmgr = dbenv->tx_handle;
  129. if (tmgr != NULL) {
  130. R_LOCK(dbenv, &tmgr->reginfo);
  131. txn_max = ((DB_TXNREGION *)tmgr->reginfo.primary)->cur_maxid;
  132. R_UNLOCK(dbenv, &tmgr->reginfo);
  133. } else
  134. txn_max = TXN_MAXIMUM;
  135. if (ret != 0 || atype == DB_LOCK_EXPIRE)
  136. return (ret);
  137. if (nlockers == 0)
  138. return (0);
  139. #ifdef DIAGNOSTIC
  140. if (FLD_ISSET(dbenv->verbose, DB_VERB_WAITSFOR))
  141. __dd_debug(dbenv, idmap, bitmap, nlockers, nalloc);
  142. #endif
  143. /* Now duplicate the bitmaps so we can verify deadlock participants. */
  144. if ((ret = __os_calloc(dbenv, (size_t)nlockers,
  145.     sizeof(u_int32_t) * nalloc, &copymap)) != 0)
  146. goto err;
  147. memcpy(copymap, bitmap, nlockers * sizeof(u_int32_t) * nalloc);
  148. if ((ret = __os_calloc(dbenv, sizeof(u_int32_t), nalloc, &tmpmap)) != 0)
  149. goto err1;
  150. /* Find a deadlock. */
  151. if ((ret =
  152.     __dd_find(dbenv, bitmap, idmap, nlockers, nalloc, &deadp)) != 0)
  153. return (ret);
  154. killid = BAD_KILLID;
  155. free_me = deadp;
  156. for (; *deadp != NULL; deadp++) {
  157. if (abortp != NULL)
  158. ++*abortp;
  159. killid = (u_int32_t)((*deadp - bitmap) / nalloc);
  160. limit = killid;
  161. keeper = BAD_KILLID;
  162. if (atype == DB_LOCK_DEFAULT || atype == DB_LOCK_RANDOM)
  163. goto dokill;
  164. /*
  165.  * It's conceivable that under XA, the locker could
  166.  * have gone away.
  167.  */
  168. if (killid == BAD_KILLID)
  169. break;
  170. /*
  171.  * Start with the id that we know is deadlocked
  172.  * and then examine all other set bits and see
  173.  * if any are a better candidate for abortion
  174.  * and that they are genuinely part of the
  175.  * deadlock.  The definition of "best":
  176.  * OLDEST: smallest id
  177.  * YOUNGEST: largest id
  178.  * MAXLOCKS: maximum count
  179.  * MINLOCKS: minimum count
  180.  * MINWRITE: minimum count
  181.  */
  182. for (i = (killid + 1) % nlockers;
  183.     i != limit;
  184.     i = (i + 1) % nlockers) {
  185. if (!ISSET_MAP(*deadp, i))
  186. continue;
  187. switch (atype) {
  188. case DB_LOCK_OLDEST:
  189. if (__dd_isolder(idmap[killid].id,
  190.     idmap[i].id, lock_max, txn_max))
  191. continue;
  192. keeper = i;
  193. break;
  194. case DB_LOCK_YOUNGEST:
  195. if (__dd_isolder(idmap[i].id,
  196.     idmap[killid].id, lock_max, txn_max))
  197. continue;
  198. keeper = i;
  199. break;
  200. case DB_LOCK_MAXLOCKS:
  201. if (idmap[i].count < idmap[killid].count)
  202. continue;
  203. keeper = i;
  204. break;
  205. case DB_LOCK_MINLOCKS:
  206. case DB_LOCK_MINWRITE:
  207. if (idmap[i].count > idmap[killid].count)
  208. continue;
  209. keeper = i;
  210. break;
  211. default:
  212. killid = BAD_KILLID;
  213. ret = EINVAL;
  214. goto dokill;
  215. }
  216. if (__dd_verify(idmap, *deadp,
  217.     tmpmap, copymap, nlockers, nalloc, i))
  218. killid = i;
  219. }
  220. dokill: if (killid == BAD_KILLID)
  221. continue;
  222. /*
  223.  * There are cases in which our general algorithm will
  224.  * fail.  Returning 1 from verify indicates that the
  225.  * particular locker is not only involved in a deadlock,
  226.  * but that killing him will allow others to make forward
  227.  * progress.  Unfortunately, there are cases where we need
  228.  * to abort someone, but killing them will not necessarily
  229.  * ensure forward progress (imagine N readers all trying to
  230.  * acquire a write lock).  In such a scenario, we'll have
  231.  * gotten all the way through the loop, we will have found
  232.  * someone to keep (keeper will be valid), but killid will
  233.  * still be the initial deadlocker.  In this case, if the
  234.  * initial killid satisfies __dd_verify, kill it, else abort
  235.  * keeper and indicate that we need to run deadlock detection
  236.  * again.
  237.  */
  238. if (keeper != BAD_KILLID && killid == limit &&
  239.     __dd_verify(idmap, *deadp,
  240.     tmpmap, copymap, nlockers, nalloc, killid) == 0) {
  241. LOCKREGION(dbenv, lt);
  242. region->need_dd = 1;
  243. UNLOCKREGION(dbenv, lt);
  244. killid = keeper;
  245. }
  246. /* Kill the locker with lockid idmap[killid]. */
  247. if ((ret = __dd_abort(dbenv, &idmap[killid])) != 0) {
  248. /*
  249.  * It's possible that the lock was already aborted;
  250.  * this isn't necessarily a problem, so do not treat
  251.  * it as an error.
  252.  */
  253. if (ret == DB_ALREADY_ABORTED)
  254. ret = 0;
  255. else
  256. __db_err(dbenv,
  257.     "warning: unable to abort locker %lx",
  258.     (u_long)idmap[killid].id);
  259. } else if (FLD_ISSET(dbenv->verbose, DB_VERB_DEADLOCK))
  260. __db_err(dbenv,
  261.     "Aborting locker %lx", (u_long)idmap[killid].id);
  262. }
  263. __os_free(dbenv, tmpmap);
  264. err1: __os_free(dbenv, copymap);
  265. err: if (free_me != NULL)
  266. __os_free(dbenv, free_me);
  267. __os_free(dbenv, bitmap);
  268. __os_free(dbenv, idmap);
  269. return (ret);
  270. }
  271. /*
  272.  * ========================================================================
  273.  * Utilities
  274.  */
  275. # define DD_INVALID_ID ((u_int32_t) -1)
  276. static int
  277. __dd_build(dbenv, atype, bmp, nlockers, allocp, idmap)
  278. DB_ENV *dbenv;
  279. u_int32_t atype, **bmp, *nlockers, *allocp;
  280. locker_info **idmap;
  281. {
  282. struct __db_lock *lp;
  283. DB_LOCKER *lip, *lockerp, *child;
  284. DB_LOCKOBJ *op, *lo;
  285. DB_LOCKREGION *region;
  286. DB_LOCKTAB *lt;
  287. locker_info *id_array;
  288. db_timeval_t now;
  289. u_int32_t *bitmap, count, dd, *entryp, id, ndx, nentries, *tmpmap;
  290. u_int8_t *pptr;
  291. int expire_only, is_first, need_timeout, ret;
  292. lt = dbenv->lk_handle;
  293. region = lt->reginfo.primary;
  294. LOCK_SET_TIME_INVALID(&now);
  295. need_timeout = 0;
  296. expire_only = atype == DB_LOCK_EXPIRE;
  297. /*
  298.  * While we always check for expired timeouts, if we are called
  299.  * with DB_LOCK_EXPIRE, then we are only checking for timeouts
  300.  * (i.e., not doing deadlock detection at all).  If we aren't
  301.  * doing real deadlock detection, then we can skip a significant,
  302.  * amount of the processing.  In particular we do not build
  303.  * the conflict array and our caller needs to expect this.
  304.  */
  305. if (expire_only) {
  306. count = 0;
  307. nentries = 0;
  308. goto obj_loop;
  309. }
  310. /*
  311.  * We'll check how many lockers there are, add a few more in for
  312.  * good measure and then allocate all the structures.  Then we'll
  313.  * verify that we have enough room when we go back in and get the
  314.  * mutex the second time.
  315.  */
  316. retry: count = region->stat.st_nlockers;
  317. if (count == 0) {
  318. *nlockers = 0;
  319. return (0);
  320. }
  321. if (FLD_ISSET(dbenv->verbose, DB_VERB_DEADLOCK))
  322. __db_err(dbenv, "%lu lockers", (u_long)count);
  323. count += 20;
  324. nentries = ALIGN(count, 32) / 32;
  325. /*
  326.  * Allocate enough space for a count by count bitmap matrix.
  327.  *
  328.  * XXX
  329.  * We can probably save the malloc's between iterations just
  330.  * reallocing if necessary because count grew by too much.
  331.  */
  332. if ((ret = __os_calloc(dbenv, (size_t)count,
  333.     sizeof(u_int32_t) * nentries, &bitmap)) != 0)
  334. return (ret);
  335. if ((ret = __os_calloc(dbenv,
  336.     sizeof(u_int32_t), nentries, &tmpmap)) != 0) {
  337. __os_free(dbenv, bitmap);
  338. return (ret);
  339. }
  340. if ((ret = __os_calloc(dbenv,
  341.     (size_t)count, sizeof(locker_info), &id_array)) != 0) {
  342. __os_free(dbenv, bitmap);
  343. __os_free(dbenv, tmpmap);
  344. return (ret);
  345. }
  346. /*
  347.  * Now go back in and actually fill in the matrix.
  348.  */
  349. if (region->stat.st_nlockers > count) {
  350. __os_free(dbenv, bitmap);
  351. __os_free(dbenv, tmpmap);
  352. __os_free(dbenv, id_array);
  353. goto retry;
  354. }
  355. /*
  356.  * First we go through and assign each locker a deadlock detector id.
  357.  */
  358. for (id = 0, lip = SH_TAILQ_FIRST(&region->lockers, __db_locker);
  359.     lip != NULL;
  360.     lip = SH_TAILQ_NEXT(lip, ulinks, __db_locker)) {
  361. if (F_ISSET(lip, DB_LOCKER_INABORT))
  362. continue;
  363. if (lip->master_locker == INVALID_ROFF) {
  364. lip->dd_id = id++;
  365. id_array[lip->dd_id].id = lip->id;
  366. if (atype == DB_LOCK_MINLOCKS ||
  367.     atype == DB_LOCK_MAXLOCKS)
  368. id_array[lip->dd_id].count = lip->nlocks;
  369. if (atype == DB_LOCK_MINWRITE)
  370. id_array[lip->dd_id].count = lip->nwrites;
  371. } else
  372. lip->dd_id = DD_INVALID_ID;
  373. }
  374. /*
  375.  * We only need consider objects that have waiters, so we use
  376.  * the list of objects with waiters (dd_objs) instead of traversing
  377.  * the entire hash table.  For each object, we traverse the waiters
  378.  * list and add an entry in the waitsfor matrix for each waiter/holder
  379.  * combination.
  380.  */
  381. obj_loop:
  382. for (op = SH_TAILQ_FIRST(&region->dd_objs, __db_lockobj);
  383.     op != NULL; op = SH_TAILQ_NEXT(op, dd_links, __db_lockobj)) {
  384. if (expire_only)
  385. goto look_waiters;
  386. CLEAR_MAP(tmpmap, nentries);
  387. /*
  388.  * First we go through and create a bit map that
  389.  * represents all the holders of this object.
  390.  */
  391. for (lp = SH_TAILQ_FIRST(&op->holders, __db_lock);
  392.     lp != NULL;
  393.     lp = SH_TAILQ_NEXT(lp, links, __db_lock)) {
  394. LOCKER_LOCK(lt, region, lp->holder, ndx);
  395. if ((ret = __lock_getlocker(lt,
  396.     lp->holder, ndx, 0, &lockerp)) != 0)
  397. continue;
  398. if (F_ISSET(lockerp, DB_LOCKER_INABORT))
  399. continue;
  400. if (lockerp->dd_id == DD_INVALID_ID) {
  401. dd = ((DB_LOCKER *)R_ADDR(&lt->reginfo,
  402.     lockerp->master_locker))->dd_id;
  403. lockerp->dd_id = dd;
  404. if (atype == DB_LOCK_MINLOCKS ||
  405.     atype == DB_LOCK_MAXLOCKS)
  406. id_array[dd].count += lockerp->nlocks;
  407. if (atype == DB_LOCK_MINWRITE)
  408. id_array[dd].count += lockerp->nwrites;
  409. } else
  410. dd = lockerp->dd_id;
  411. id_array[dd].valid = 1;
  412. /*
  413.  * If the holder has already been aborted, then
  414.  * we should ignore it for now.
  415.  */
  416. if (lp->status == DB_LSTAT_HELD)
  417. SET_MAP(tmpmap, dd);
  418. }
  419. /*
  420.  * Next, for each waiter, we set its row in the matrix
  421.  * equal to the map of holders we set up above.
  422.  */
  423. look_waiters:
  424. for (is_first = 1,
  425.     lp = SH_TAILQ_FIRST(&op->waiters, __db_lock);
  426.     lp != NULL;
  427.     is_first = 0,
  428.     lp = SH_TAILQ_NEXT(lp, links, __db_lock)) {
  429. LOCKER_LOCK(lt, region, lp->holder, ndx);
  430. if ((ret = __lock_getlocker(lt,
  431.     lp->holder, ndx, 0, &lockerp)) != 0)
  432. continue;
  433. if (lp->status == DB_LSTAT_WAITING) {
  434. if (__lock_expired(dbenv,
  435.     &now, &lockerp->lk_expire)) {
  436. lp->status = DB_LSTAT_EXPIRED;
  437. MUTEX_UNLOCK(dbenv, &lp->mutex);
  438. continue;
  439. }
  440. need_timeout =
  441.     LOCK_TIME_ISVALID(&lockerp->lk_expire);
  442. }
  443. if (expire_only)
  444. continue;
  445. if (lockerp->dd_id == DD_INVALID_ID) {
  446. dd = ((DB_LOCKER *)R_ADDR(&lt->reginfo,
  447.     lockerp->master_locker))->dd_id;
  448. lockerp->dd_id = dd;
  449. if (atype == DB_LOCK_MINLOCKS ||
  450.     atype == DB_LOCK_MAXLOCKS)
  451. id_array[dd].count += lockerp->nlocks;
  452. if (atype == DB_LOCK_MINWRITE)
  453. id_array[dd].count += lockerp->nwrites;
  454. } else
  455. dd = lockerp->dd_id;
  456. id_array[dd].valid = 1;
  457. /*
  458.  * If the transaction is pending abortion, then
  459.  * ignore it on this iteration.
  460.  */
  461. if (lp->status != DB_LSTAT_WAITING)
  462. continue;
  463. entryp = bitmap + (nentries * dd);
  464. OR_MAP(entryp, tmpmap, nentries);
  465. /*
  466.  * If this is the first waiter on the queue,
  467.  * then we remove the waitsfor relationship
  468.  * with oneself.  However, if it's anywhere
  469.  * else on the queue, then we have to keep
  470.  * it and we have an automatic deadlock.
  471.  */
  472. if (is_first) {
  473. if (ISSET_MAP(entryp, dd))
  474. id_array[dd].self_wait = 1;
  475. CLR_MAP(entryp, dd);
  476. }
  477. }
  478. }
  479. if (expire_only) {
  480. region->need_dd = need_timeout;
  481. return (0);
  482. }
  483. /* Now for each locker; record its last lock. */
  484. for (id = 0; id < count; id++) {
  485. if (!id_array[id].valid)
  486. continue;
  487. LOCKER_LOCK(lt, region, id_array[id].id, ndx);
  488. if ((ret = __lock_getlocker(lt,
  489.     id_array[id].id, ndx, 0, &lockerp)) != 0) {
  490. __db_err(dbenv,
  491.     "No locks for locker %lu", (u_long)id_array[id].id);
  492. continue;
  493. }
  494. /*
  495.  * If this is a master transaction, try to
  496.  * find one of its children's locks first,
  497.  * as they are probably more recent.
  498.  */
  499. child = SH_LIST_FIRST(&lockerp->child_locker, __db_locker);
  500. if (child != NULL) {
  501. do {
  502. lp = SH_LIST_FIRST(&child->heldby, __db_lock);
  503. if (lp != NULL &&
  504.     lp->status == DB_LSTAT_WAITING) {
  505. id_array[id].last_locker_id = child->id;
  506. goto get_lock;
  507. }
  508. child = SH_LIST_NEXT(
  509.     child, child_link, __db_locker);
  510. } while (child != NULL);
  511. }
  512. lp = SH_LIST_FIRST(&lockerp->heldby, __db_lock);
  513. if (lp != NULL) {
  514. id_array[id].last_locker_id = lockerp->id;
  515. get_lock: id_array[id].last_lock = R_OFFSET(&lt->reginfo, lp);
  516. lo = (DB_LOCKOBJ *)((u_int8_t *)lp + lp->obj);
  517. pptr = SH_DBT_PTR(&lo->lockobj);
  518. if (lo->lockobj.size >= sizeof(db_pgno_t))
  519. memcpy(&id_array[id].pgno,
  520.     pptr, sizeof(db_pgno_t));
  521. else
  522. id_array[id].pgno = 0;
  523. }
  524. }
  525. /*
  526.  * Pass complete, reset the deadlock detector bit,
  527.  * unless we have pending timeouts.
  528.  */
  529. region->need_dd = need_timeout;
  530. /*
  531.  * Now we can release everything except the bitmap matrix that we
  532.  * created.
  533.  */
  534. *nlockers = id;
  535. *idmap = id_array;
  536. *bmp = bitmap;
  537. *allocp = nentries;
  538. __os_free(dbenv, tmpmap);
  539. return (0);
  540. }
  541. static int
  542. __dd_find(dbenv, bmp, idmap, nlockers, nalloc, deadp)
  543. DB_ENV *dbenv;
  544. u_int32_t *bmp, nlockers, nalloc;
  545. locker_info *idmap;
  546. u_int32_t ***deadp;
  547. {
  548. u_int32_t i, j, k, *mymap, *tmpmap;
  549. u_int32_t **retp;
  550. int ndead, ndeadalloc, ret;
  551. #undef INITIAL_DEAD_ALLOC
  552. #define INITIAL_DEAD_ALLOC 8
  553. ndeadalloc = INITIAL_DEAD_ALLOC;
  554. ndead = 0;
  555. if ((ret = __os_malloc(dbenv,
  556.     ndeadalloc * sizeof(u_int32_t *), &retp)) != 0)
  557. return (ret);
  558. /*
  559.  * For each locker, OR in the bits from the lockers on which that
  560.  * locker is waiting.
  561.  */
  562. for (mymap = bmp, i = 0; i < nlockers; i++, mymap += nalloc) {
  563. if (!idmap[i].valid)
  564. continue;
  565. for (j = 0; j < nlockers; j++) {
  566. if (!ISSET_MAP(mymap, j))
  567. continue;
  568. /* Find the map for this bit. */
  569. tmpmap = bmp + (nalloc * j);
  570. OR_MAP(mymap, tmpmap, nalloc);
  571. if (!ISSET_MAP(mymap, i))
  572. continue;
  573. /* Make sure we leave room for NULL. */
  574. if (ndead + 2 >= ndeadalloc) {
  575. ndeadalloc <<= 1;
  576. /*
  577.  * If the alloc fails, then simply return the
  578.  * deadlocks that we already have.
  579.  */
  580. if (__os_realloc(dbenv,
  581.     ndeadalloc * sizeof(u_int32_t),
  582.     &retp) != 0) {
  583. retp[ndead] = NULL;
  584. *deadp = retp;
  585. return (0);
  586. }
  587. }
  588. retp[ndead++] = mymap;
  589. /* Mark all participants in this deadlock invalid. */
  590. for (k = 0; k < nlockers; k++)
  591. if (ISSET_MAP(mymap, k))
  592. idmap[k].valid = 0;
  593. break;
  594. }
  595. }
  596. retp[ndead] = NULL;
  597. *deadp = retp;
  598. return (0);
  599. }
  600. static int
  601. __dd_abort(dbenv, info)
  602. DB_ENV *dbenv;
  603. locker_info *info;
  604. {
  605. struct __db_lock *lockp;
  606. DB_LOCKER *lockerp;
  607. DB_LOCKOBJ *sh_obj;
  608. DB_LOCKREGION *region;
  609. DB_LOCKTAB *lt;
  610. u_int32_t ndx;
  611. int ret;
  612. lt = dbenv->lk_handle;
  613. region = lt->reginfo.primary;
  614. LOCKREGION(dbenv, lt);
  615. /* Find the locker's last lock. */
  616. LOCKER_LOCK(lt, region, info->last_locker_id, ndx);
  617. if ((ret = __lock_getlocker(lt,
  618.     info->last_locker_id, ndx, 0, &lockerp)) != 0 || lockerp == NULL) {
  619. if (ret == 0)
  620. ret = DB_ALREADY_ABORTED;
  621. goto out;
  622. }
  623. /* It's possible that this locker was already aborted. */
  624. if ((lockp = SH_LIST_FIRST(&lockerp->heldby, __db_lock)) == NULL) {
  625. ret = DB_ALREADY_ABORTED;
  626. goto out;
  627. }
  628. if (R_OFFSET(&lt->reginfo, lockp) != info->last_lock ||
  629.     lockp->status != DB_LSTAT_WAITING) {
  630. ret = DB_ALREADY_ABORTED;
  631. goto out;
  632. }
  633. sh_obj = (DB_LOCKOBJ *)((u_int8_t *)lockp + lockp->obj);
  634. SH_LIST_REMOVE(lockp, locker_links, __db_lock);
  635. /* Abort lock, take it off list, and wake up this lock. */
  636. SHOBJECT_LOCK(lt, region, sh_obj, ndx);
  637. lockp->status = DB_LSTAT_ABORTED;
  638. SH_TAILQ_REMOVE(&sh_obj->waiters, lockp, links, __db_lock);
  639. /*
  640.  * Either the waiters list is now empty, in which case we remove
  641.  * it from dd_objs, or it is not empty, in which case we need to
  642.  * do promotion.
  643.  */
  644. if (SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock) == NULL)
  645. SH_TAILQ_REMOVE(&region->dd_objs,
  646.     sh_obj, dd_links, __db_lockobj);
  647. else
  648. ret = __lock_promote(lt, sh_obj, 0);
  649. MUTEX_UNLOCK(dbenv, &lockp->mutex);
  650. region->stat.st_ndeadlocks++;
  651. UNLOCKREGION(dbenv, lt);
  652. return (0);
  653. out: UNLOCKREGION(dbenv, lt);
  654. return (ret);
  655. }
  656. #ifdef DIAGNOSTIC
  657. static void
  658. __dd_debug(dbenv, idmap, bitmap, nlockers, nalloc)
  659. DB_ENV *dbenv;
  660. locker_info *idmap;
  661. u_int32_t *bitmap, nlockers, nalloc;
  662. {
  663. u_int32_t i, j, *mymap;
  664. char *msgbuf;
  665. __db_err(dbenv, "Waitsfor arraynWaiter:tWaiting on:");
  666. /* Allocate space to print 10 bytes per item waited on. */
  667. #undef MSGBUF_LEN
  668. #define MSGBUF_LEN ((nlockers + 1) * 10 + 64)
  669. if (__os_malloc(dbenv, MSGBUF_LEN, &msgbuf) != 0)
  670. return;
  671. for (mymap = bitmap, i = 0; i < nlockers; i++, mymap += nalloc) {
  672. if (!idmap[i].valid)
  673. continue;
  674. sprintf(msgbuf, /* Waiter. */
  675.     "%lx/%lu:t", (u_long)idmap[i].id, (u_long)idmap[i].pgno);
  676. for (j = 0; j < nlockers; j++)
  677. if (ISSET_MAP(mymap, j))
  678. sprintf(msgbuf, "%s %lx", msgbuf,
  679.     (u_long)idmap[j].id);
  680. (void)sprintf(msgbuf,
  681.     "%s %lu", msgbuf, (u_long)idmap[i].last_lock);
  682. __db_err(dbenv, msgbuf);
  683. }
  684. __os_free(dbenv, msgbuf);
  685. }
  686. #endif
  687. /*
  688.  * Given a bitmap that contains a deadlock, verify that the bit
  689.  * specified in the which parameter indicates a transaction that
  690.  * is actually deadlocked.  Return 1 if really deadlocked, 0 otherwise.
  691.  * deadmap is the array that identified the deadlock.
  692.  * tmpmap is a copy of the initial bitmaps from the dd_build phase
  693.  * origmap is a temporary bit map into which we can OR things
  694.  * nlockers is the number of actual lockers under consideration
  695.  * nalloc is the number of words allocated for the bitmap
  696.  * which is the locker in question
  697.  */
  698. static int
  699. __dd_verify(idmap, deadmap, tmpmap, origmap, nlockers, nalloc, which)
  700. locker_info *idmap;
  701. u_int32_t *deadmap, *tmpmap, *origmap;
  702. u_int32_t nlockers, nalloc, which;
  703. {
  704. u_int32_t *tmap;
  705. u_int32_t j;
  706. int count;
  707. memset(tmpmap, 0, sizeof(u_int32_t) * nalloc);
  708. /*
  709.  * In order for "which" to be actively involved in
  710.  * the deadlock, removing him from the evaluation
  711.  * must remove the deadlock.  So, we OR together everyone
  712.  * except which; if all the participants still have their
  713.  * bits set, then the deadlock persists and which does
  714.  * not participate.  If the deadlock does not persist
  715.  * then "which" does participate.
  716.  */
  717. count = 0;
  718. for (j = 0; j < nlockers; j++) {
  719. if (!ISSET_MAP(deadmap, j) || j == which)
  720. continue;
  721. /* Find the map for this bit. */
  722. tmap = origmap + (nalloc * j);
  723. /*
  724.  * We special case the first waiter who is also a holder, so
  725.  * we don't automatically call that a deadlock.  However, if
  726.  * it really is a deadlock, we need the bit set now so that
  727.  * we treat the first waiter like other waiters.
  728.  */
  729. if (idmap[j].self_wait)
  730. SET_MAP(tmap, j);
  731. OR_MAP(tmpmap, tmap, nalloc);
  732. count++;
  733. }
  734. if (count == 1)
  735. return (1);
  736. /*
  737.  * Now check the resulting map and see whether
  738.  * all participants still have their bit set.
  739.  */
  740. for (j = 0; j < nlockers; j++) {
  741. if (!ISSET_MAP(deadmap, j) || j == which)
  742. continue;
  743. if (!ISSET_MAP(tmpmap, j))
  744. return (1);
  745. }
  746. return (0);
  747. }
  748. /*
  749.  * __dd_isolder --
  750.  *
  751.  * Figure out the relative age of two lockers.  We make all lockers
  752.  * older than all transactions, because that's how it's worked
  753.  * historically (because lockers are lower ids).
  754.  */
  755. static int
  756. __dd_isolder(a, b, lock_max, txn_max)
  757. u_int32_t a, b;
  758. u_int32_t lock_max, txn_max;
  759. {
  760. u_int32_t max;
  761. /* Check for comparing lock-id and txnid. */
  762. if (a <= DB_LOCK_MAXID && b > DB_LOCK_MAXID)
  763. return (1);
  764. if (b <= DB_LOCK_MAXID && a > DB_LOCK_MAXID)
  765. return (0);
  766. /* In the same space; figure out which one. */
  767. max = txn_max;
  768. if (a <= DB_LOCK_MAXID)
  769. max = lock_max;
  770. /*
  771.  * We can't get a 100% correct ordering, because we don't know
  772.  * where the current interval started and if there were older
  773.  * lockers outside the interval.  We do the best we can.
  774.  */
  775. /*
  776.  * Check for a wrapped case with ids above max.
  777.  */
  778. if (a > max && b < max)
  779. return (1);
  780. if (b > max && a < max)
  781. return (0);
  782. return (a < b);
  783. }