lock_deadlock.c

这是国外的resip协议栈

			lip->dd_id = DD_INVALID_ID;

	}

	/*
	 * We only need consider objects that have waiters, so we use
	 * the list of objects with waiters (dd_objs) instead of traversing
	 * the entire hash table.  For each object, we traverse the waiters
	 * list and add an entry in the waitsfor matrix for each waiter/holder
	 * combination.
	 */
obj_loop:
	for (op = SH_TAILQ_FIRST(&region->dd_objs, __db_lockobj);
	    op != NULL; op = SH_TAILQ_NEXT(op, dd_links, __db_lockobj)) {
		if (expire_only)
			goto look_waiters;
		CLEAR_MAP(tmpmap, nentries);

		/*
		 * First we go through and create a bit map that
		 * represents all the holders of this object.
		 */
		for (lp = SH_TAILQ_FIRST(&op->holders, __db_lock);
		    lp != NULL;
		    lp = SH_TAILQ_NEXT(lp, links, __db_lock)) {
			LOCKER_LOCK(lt, region, lp->holder, ndx);
			if ((ret = __lock_getlocker(lt,
			    lp->holder, ndx, 0, &lockerp)) != 0)
				continue;

			if (lockerp->dd_id == DD_INVALID_ID) {
				dd = ((DB_LOCKER *)R_ADDR(&lt->reginfo,
				    lockerp->master_locker))->dd_id;
				lockerp->dd_id = dd;
				switch (atype) {
				case DB_LOCK_MINLOCKS:
				case DB_LOCK_MAXLOCKS:
					id_array[dd].count += lockerp->nlocks;
					break;
				case DB_LOCK_MINWRITE:
				case DB_LOCK_MAXWRITE:
					id_array[dd].count += lockerp->nwrites;
					break;
				}
				if (F_ISSET(lockerp, DB_LOCKER_INABORT))
					id_array[dd].in_abort = 1;

			} else
				dd = lockerp->dd_id;
			id_array[dd].valid = 1;

			/*
			 * If the holder has already been aborted, then
			 * we should ignore it for now.
			 */
			if (lp->status == DB_LSTAT_HELD)
				SET_MAP(tmpmap, dd);
		}

		/*
		 * Next, for each waiter, we set its row in the matrix
		 * equal to the map of holders we set up above.
		 */
look_waiters:
		for (is_first = 1,
		    lp = SH_TAILQ_FIRST(&op->waiters, __db_lock);
		    lp != NULL;
		    is_first = 0,
		    lp = SH_TAILQ_NEXT(lp, links, __db_lock)) {
			LOCKER_LOCK(lt, region, lp->holder, ndx);
			if ((ret = __lock_getlocker(lt,
			    lp->holder, ndx, 0, &lockerp)) != 0)
				continue;
			if (lp->status == DB_LSTAT_WAITING) {
				if (__lock_expired(dbenv,
				    &now, &lockerp->lk_expire)) {
					lp->status = DB_LSTAT_EXPIRED;
					MUTEX_UNLOCK(dbenv, &lp->mutex);
					continue;
				}
				if (LOCK_TIME_GREATER(
				    &min_timeout, &lockerp->lk_expire))
					min_timeout = lockerp->lk_expire;

			}

			if (expire_only)
				continue;

			if (lockerp->dd_id == DD_INVALID_ID) {
				dd = ((DB_LOCKER *)R_ADDR(&lt->reginfo,
				    lockerp->master_locker))->dd_id;
				lockerp->dd_id = dd;
				switch (atype) {
				case DB_LOCK_MINLOCKS:
				case DB_LOCK_MAXLOCKS:
					id_array[dd].count += lockerp->nlocks;
					break;
				case DB_LOCK_MINWRITE:
				case DB_LOCK_MAXWRITE:
					id_array[dd].count += lockerp->nwrites;
					break;
				}
			} else
				dd = lockerp->dd_id;
			id_array[dd].valid = 1;

			/*
			 * If the transaction is pending abortion, then
			 * ignore it on this iteration.
			 */
			if (lp->status != DB_LSTAT_WAITING)
				continue;

			entryp = bitmap + (nentries * dd);
			OR_MAP(entryp, tmpmap, nentries);
			/*
			 * 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) {
				if (ISSET_MAP(entryp, dd))
					id_array[dd].self_wait = 1;
				CLR_MAP(entryp, dd);
			}
		}
	}

	if (LOCK_TIME_ISVALID(&region->next_timeout)) {
		if (LOCK_TIME_ISMAX(&min_timeout))
			LOCK_SET_TIME_INVALID(&region->next_timeout);
		else
			region->next_timeout = min_timeout;
	}
	if (expire_only)
		return (0);

	/* Now for each locker; record its last lock. */
	for (id = 0; id < count; id++) {
		if (!id_array[id].valid)
			continue;
		LOCKER_LOCK(lt, region, id_array[id].id, ndx);
		if ((ret = __lock_getlocker(lt,
		    id_array[id].id, ndx, 0, &lockerp)) != 0) {
			__db_err(dbenv,
			    "No locks for locker %lu", (u_long)id_array[id].id);
			continue;
		}

		/*
		 * If this is a master transaction, try to
		 * find one of its children's locks first,
		 * as they are probably more recent.
		 */
		child = SH_LIST_FIRST(&lockerp->child_locker, __db_locker);
		if (child != NULL) {
			do {
				lp = SH_LIST_FIRST(&child->heldby, __db_lock);
				if (lp != NULL &&
				    lp->status == DB_LSTAT_WAITING) {
					id_array[id].last_locker_id = child->id;
					goto get_lock;
				}
				child = SH_LIST_NEXT(
				    child, child_link, __db_locker);
			} while (child != NULL);
		}
		lp = SH_LIST_FIRST(&lockerp->heldby, __db_lock);
		if (lp != NULL) {
			id_array[id].last_locker_id = lockerp->id;
get_lock:		id_array[id].last_lock = R_OFFSET(&lt->reginfo, lp);
			id_array[id].last_obj = lp->obj;
			lo = (DB_LOCKOBJ *)((u_int8_t *)lp + lp->obj);
			pptr = SH_DBT_PTR(&lo->lockobj);
			if (lo->lockobj.size >= sizeof(db_pgno_t))
				memcpy(&id_array[id].pgno,
				    pptr, sizeof(db_pgno_t));
			else
				id_array[id].pgno = 0;
		}
	}

	/*
	 * Pass complete, reset the deadlock detector bit.
	 */
	region->need_dd = 0;

	/*
	 * Now we can release everything except the bitmap matrix that we
	 * created.
	 */
	*nlockers = id;
	*idmap = id_array;
	*bmp = bitmap;
	*allocp = nentries;
	__os_free(dbenv, tmpmap);
	return (0);
}

static int
__dd_find(dbenv, bmp, idmap, nlockers, nalloc, deadp)
	DB_ENV *dbenv;
	u_int32_t *bmp, nlockers, nalloc;
	locker_info *idmap;
	u_int32_t ***deadp;
{
	u_int32_t i, j, k, *mymap, *tmpmap, **retp;
	u_int ndead, ndeadalloc;
	int ret;

#undef	INITIAL_DEAD_ALLOC
#define	INITIAL_DEAD_ALLOC	8

	ndeadalloc = INITIAL_DEAD_ALLOC;
	ndead = 0;
	if ((ret = __os_malloc(dbenv,
	    ndeadalloc * sizeof(u_int32_t *), &retp)) != 0)
		return (ret);

	/*
	 * For each locker, OR in the bits from the lockers on which that
	 * locker is waiting.
	 */
	for (mymap = bmp, i = 0; i < nlockers; i++, mymap += nalloc) {
		if (!idmap[i].valid)
			continue;
		for (j = 0; j < nlockers; j++) {
			if (!ISSET_MAP(mymap, j))
				continue;

			/* Find the map for this bit. */
			tmpmap = bmp + (nalloc * j);
			OR_MAP(mymap, tmpmap, nalloc);
			if (!ISSET_MAP(mymap, i))
				continue;

			/* Make sure we leave room for NULL. */
			if (ndead + 2 >= ndeadalloc) {
				ndeadalloc <<= 1;
				/*
				 * If the alloc fails, then simply return the
				 * deadlocks that we already have.
				 */
				if (__os_realloc(dbenv,
				    ndeadalloc * sizeof(u_int32_t),
				    &retp) != 0) {
					retp[ndead] = NULL;
					*deadp = retp;
					return (0);
				}
			}
			retp[ndead++] = mymap;

			/* Mark all participants in this deadlock invalid. */
			for (k = 0; k < nlockers; k++)
				if (ISSET_MAP(mymap, k))
					idmap[k].valid = 0;
			break;
		}
	}
	retp[ndead] = NULL;
	*deadp = retp;
	return (0);
}

static int
__dd_abort(dbenv, info)
	DB_ENV *dbenv;
	locker_info *info;
{
	struct __db_lock *lockp;
	DB_LOCKER *lockerp;
	DB_LOCKOBJ *sh_obj;
	DB_LOCKREGION *region;
	DB_LOCKTAB *lt;
	u_int32_t ndx;
	int ret;

	lt = dbenv->lk_handle;
	region = lt->reginfo.primary;

	LOCKREGION(dbenv, lt);

	/*
	 * Get the locker.  If its gone or was aborted while
	 * we were detecting return that.
	 */
	LOCKER_LOCK(lt, region, info->last_locker_id, ndx);
	if ((ret = __lock_getlocker(lt,
	    info->last_locker_id, ndx, 0, &lockerp)) != 0 ||
	    lockerp == NULL || F_ISSET(lockerp, DB_LOCKER_INABORT)) {
		if (ret == 0)
			ret = DB_ALREADY_ABORTED;
		goto out;
	}

	/*
	 * Find the locker's last lock.
	 * It is possible for this lock to have been freed,
	 * either though a timeout or another detector run.
	 */
	if ((lockp = SH_LIST_FIRST(&lockerp->heldby, __db_lock)) == NULL) {
		ret = DB_ALREADY_ABORTED;
		goto out;
	}
	if (R_OFFSET(&lt->reginfo, lockp) != info->last_lock ||
	    lockp->holder != lockerp->id ||
	    lockp->obj != info->last_obj || lockp->status != DB_LSTAT_WAITING) {
		ret = DB_ALREADY_ABORTED;
		goto out;
	}

	sh_obj = (DB_LOCKOBJ *)((u_int8_t *)lockp + lockp->obj);

	/* Abort lock, take it off list, and wake up this lock. */
	SHOBJECT_LOCK(lt, region, sh_obj, ndx);
	lockp->status = DB_LSTAT_ABORTED;
	SH_TAILQ_REMOVE(&sh_obj->waiters, lockp, links, __db_lock);

	/*
	 * Either the waiters list is now empty, in which case we remove
	 * it from dd_objs, or it is not empty, in which case we need to
	 * do promotion.
	 */
	if (SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock) == NULL)
		SH_TAILQ_REMOVE(&region->dd_objs,
		    sh_obj, dd_links, __db_lockobj);
	else
		ret = __lock_promote(lt, sh_obj, 0);
	MUTEX_UNLOCK(dbenv, &lockp->mutex);

	region->stat.st_ndeadlocks++;
	UNLOCKREGION(dbenv, lt);

	return (0);

out:	UNLOCKREGION(dbenv, lt);
	return (ret);
}

#ifdef DIAGNOSTIC
static void
__dd_debug(dbenv, idmap, bitmap, nlockers, nalloc)
	DB_ENV *dbenv;
	locker_info *idmap;
	u_int32_t *bitmap, nlockers, nalloc;
{
	DB_MSGBUF mb;
	u_int32_t i, j, *mymap;

	DB_MSGBUF_INIT(&mb);

	__db_msg(dbenv, "Waitsfor array\nWaiter:\tWaiting on:");
	for (mymap = bitmap, i = 0; i < nlockers; i++, mymap += nalloc) {
		if (!idmap[i].valid)
			continue;

		__db_msgadd(dbenv, &mb,				/* Waiter. */
		    "%lx/%lu:\t", (u_long)idmap[i].id, (u_long)idmap[i].pgno);
		for (j = 0; j < nlockers; j++)
			if (ISSET_MAP(mymap, j))
				__db_msgadd(dbenv,
				    &mb, " %lx", (u_long)idmap[j].id);
		__db_msgadd(dbenv, &mb, " %lu", (u_long)idmap[i].last_lock);
		DB_MSGBUF_FLUSH(dbenv, &mb);
	}
}
#endif

/*
 * Given a bitmap that contains a deadlock, verify that the bit
 * specified in the which parameter indicates a transaction that
 * is actually deadlocked.  Return 1 if really deadlocked, 0 otherwise.
 * deadmap  --  the array that identified the deadlock.
 * tmpmap   --  a copy of the initial bitmaps from the dd_build phase.
 * origmap  --  a temporary bit map into which we can OR things.
 * nlockers --  the number of actual lockers under consideration.
 * nalloc   --  the number of words allocated for the bitmap.
 * which    --  the locker in question.
 */
static int
__dd_verify(idmap, deadmap, tmpmap, origmap, nlockers, nalloc, which)
	locker_info *idmap;
	u_int32_t *deadmap, *tmpmap, *origmap;
	u_int32_t nlockers, nalloc, which;
{
	u_int32_t *tmap;
	u_int32_t j;
	int count;

	memset(tmpmap, 0, sizeof(u_int32_t) * nalloc);

	/*
	 * In order for "which" to be actively involved in
	 * the deadlock, removing him from the evaluation
	 * must remove the deadlock.  So, we OR together everyone
	 * except which; if all the participants still have their
	 * bits set, then the deadlock persists and which does
	 * not participate.  If the deadlock does not persist
	 * then "which" does participate.
	 */
	count = 0;
	for (j = 0; j < nlockers; j++) {
		if (!ISSET_MAP(deadmap, j) || j == which)
			continue;

		/* Find the map for this bit. */
		tmap = origmap + (nalloc * j);

		/*
		 * We special case the first waiter who is also a holder, so
		 * we don't automatically call that a deadlock.  However, if
		 * it really is a deadlock, we need the bit set now so that
		 * we treat the first waiter like other waiters.
		 */
		if (idmap[j].self_wait)
			SET_MAP(tmap, j);
		OR_MAP(tmpmap, tmap, nalloc);
		count++;
	}

	if (count == 1)
		return (1);

	/*
	 * Now check the resulting map and see whether
	 * all participants still have their bit set.
	 */
	for (j = 0; j < nlockers; j++) {
		if (!ISSET_MAP(deadmap, j) || j == which)
			continue;
		if (!ISSET_MAP(tmpmap, j))
			return (1);
	}
	return (0);
}

/*
 * __dd_isolder --
 *
 * Figure out the relative age of two lockers.  We make all lockers
 * older than all transactions, because that's how it's worked
 * historically (because lockers are lower ids).
 */
static int
__dd_isolder(a, b, lock_max, txn_max)
	u_int32_t	a, b;
	u_int32_t	lock_max, txn_max;
{
	u_int32_t max;

	/* Check for comparing lock-id and txnid. */
	if (a <= DB_LOCK_MAXID && b > DB_LOCK_MAXID)
		return (1);
	if (b <= DB_LOCK_MAXID && a > DB_LOCK_MAXID)
		return (0);

	/* In the same space; figure out which one. */
	max = txn_max;
	if (a <= DB_LOCK_MAXID)
		max = lock_max;

	/*
	 * We can't get a 100% correct ordering, because we don't know
	 * where the current interval started and if there were older
	 * lockers outside the interval.  We do the best we can.
	 */

	/*
	 * Check for a wrapped case with ids above max.
	 */
	if (a > max && b < max)
		return (1);
	if (b > max && a < max)
		return (0);

	return (a < b);
}