db2/lock/lock_deadlock.c

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