lock_deadlock.c revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*-
* See the file LICENSE for redistribution information.
*
* Copyright (c) 1996, 1997, 1998
* Sleepycat Software. All rights reserved.
*/
#include "config.h"
#ifndef lint
static const char sccsid[] = "@(#)lock_deadlock.c 10.37 (Sleepycat) 10/4/98";
#endif /* not lint */
#ifndef NO_SYSTEM_INCLUDES
#include <errno.h>
#include <string.h>
#endif
#include "db_int.h"
#include "shqueue.h"
#include "db_shash.h"
#include "lock.h"
#include "common_ext.h"
#define CLEAR_MAP(M, N) { \
M[__i] = 0; \
}
#define OR_MAP(D, S, N) { \
}
#define BAD_KILLID 0xffffffff
typedef struct {
int valid;
} locker_info;
static int __dd_build
static u_int32_t
#ifdef DIAGNOSTIC
#endif
int
DB_LOCKTAB *lt;
{
/* Validate arguments. */
if ((ret =
return (ret);
/* Check if a detector run is necessary. */
if (LF_ISSET(DB_LOCK_CONFLICT)) {
/* Make a pass every time a lock waits. */
if (!do_pass)
return (0);
}
/* Build the waits-for bitmap. */
return (ret);
if (nlockers == 0)
return (0);
#ifdef DIAGNOSTIC
if (dbenv->db_verbose != 0)
#endif
/* Find a deadlock. */
killid = BAD_KILLID;
/* Kill someone. */
switch (atype) {
case DB_LOCK_OLDEST:
/*
* Find the first bit set in the current
* array and then look for a lower tid in
* the array.
*/
for (i = 0; i < nlockers; i++)
killid = i;
if (killid == BAD_KILLID) {
"warning: could not find locker to abort");
break;
}
/*
* The oldest transaction has the lowest
* transaction id.
*/
killid = i;
break;
case DB_LOCK_DEFAULT:
case DB_LOCK_RANDOM:
/*
* We are trying to calculate the id of the
* locker whose entry is indicated by deadlock.
*/
break;
case DB_LOCK_YOUNGEST:
/*
* Find the first bit set in the current
* array and then look for a lower tid in
* the array.
*/
for (i = 0; i < nlockers; i++)
killid = i;
if (killid == BAD_KILLID) {
"warning: could not find locker to abort");
break;
}
/*
* The youngest transaction has the highest
* transaction id.
*/
killid = i;
break;
default:
killid = BAD_KILLID;
}
/* Kill the locker with lockid idmap[killid]. */
if (killid != BAD_KILLID &&
"warning: unable to abort locker %lx",
}
return (ret);
}
/*
* ========================================================================
* Utilities
*/
static int
locker_info **idmap;
{
DB_LOCKTAB *lt;
/*
* We'll check how many lockers there are, add a few more in for
* good measure and then allocate all the structures. Then we'll
* verify that we have enough room when we go back in and get the
* mutex the second time.
*/
if (count == 0) {
*nlockers = 0;
return (0);
}
if (dbenv->db_verbose)
count += 10;
/*
* Allocate enough space for a count by count bitmap matrix.
*
* XXX
* We can probably save the malloc's between iterations just
* reallocing if necessary because count grew by too much.
*/
return (ret);
return (ret);
}
if ((ret =
return (ret);
}
/*
* Now go back in and actually fill in the matrix.
*/
goto retry;
}
/*
* First we go through and assign each locker a deadlock detector id.
* Note that we fill in the idmap in the next loop since that's the
* only place where we conveniently have both the deadlock id and the
* actual locker.
*/
/*
* We go through the hash table and find each object. For each object,
* we traverse the waiters list and add an entry in the waitsfor matrix
*/
continue;
/*
* First we go through and create a bit map that
* represents all the holders of this object.
*/
"warning unable to find object");
continue;
}
/*
* If the holder has already been aborted, then
* we should ignore it for now.
*/
}
/*
* Next, for each waiter, we set its row in the matrix
* equal to the map of holders we set up above.
*/
for (is_first = 1,
is_first = 0,
"warning unable to find object");
continue;
}
/*
* If the transaction is pending abortion, then
* ignore it on this iteration.
*/
continue;
/*
* If this is the first waiter on the queue,
* then we remove the waitsfor relationship
* with oneself. However, if it's anywhere
* else on the queue, then we have to keep
* it and we have an automatic deadlock.
*/
if (is_first)
}
}
}
/* Now for each locker; record its last lock. */
continue;
if (__lock_getobj(lt,
continue;
}
sizeof(db_pgno_t));
else
}
}
/* Pass complete, reset the deadlock detector bit. */
/*
* Now we can release everything except the bitmap matrix that we
* created.
*/
return (0);
}
static u_int32_t *
{
/*
* For each locker, OR in the bits from the lockers on which that
* locker is waiting.
*/
continue;
for (j = 0; j < nlockers; j++) {
/* Find the map for this bit. */
return (mymap);
}
}
}
return (NULL);
}
static int
{
DB_LOCKTAB *lt;
int ret;
/* Find the locker's last lock. */
if ((ret =
goto out;
/*
* It's possible that this locker was already aborted.
* If that's the case, make sure that we remove its
* locker from the hash table.
*/
goto out;
goto out;
/* Abort lock, take it off list, and wake up this lock. */
ret = 0;
return (ret);
}
#ifdef DIAGNOSTIC
static void
{
int ret;
char *msgbuf;
/* Allocate space to print 10 bytes per item waited on. */
return;
continue;
for (j = 0; j < nlockers; j++)
}
}
#endif