db_dispatch.c

这是国外的resip协议栈

	if ((hp = (DB_TXNHEAD *)listp) == NULL)
		return;

	for (i = 0; i < hp->nslots; i++)
		while (hp != NULL && (p = LIST_FIRST(&hp->head[i])) != NULL) {
			LIST_REMOVE(p, links);
			switch (p->type) {
			case TXNLIST_LSN:
				__os_free(dbenv, p->u.l.lsn_array);
				break;
			case TXNLIST_DELETE:
			case TXNLIST_PGNO:
			case TXNLIST_TXNID:
			default:
				/*
				 * Possibly an incomplete DB_TXNLIST; just
				 * free it.
				 */
				break;
			}
			__os_free(dbenv, p);
		}

	if (hp->gen_array != NULL)
		__os_free(dbenv, hp->gen_array);
	__os_free(dbenv, listp);
}

/*
 * __db_txnlist_find --
 *	Checks to see if a txnid with the current generation is in the
 *	txnid list.  This returns DB_NOTFOUND if the item isn't in the
 *	list otherwise it returns (like __db_txnlist_find_internal)
 *	the status of the transaction.  A txnid of 0 means the record
 *	was generated while not in a transaction.
 *
 * PUBLIC: int __db_txnlist_find __P((DB_ENV *,
 * PUBLIC:     void *, u_int32_t, u_int32_t *));
 */
int
__db_txnlist_find(dbenv, listp, txnid, statusp)
	DB_ENV *dbenv;
	void *listp;
	u_int32_t txnid, *statusp;
{
	DB_TXNLIST *entry;

	if (txnid == 0)
		return (DB_NOTFOUND);

	return (__db_txnlist_find_internal(dbenv, listp,
	    TXNLIST_TXNID, txnid, NULL, &entry, 0, statusp));
}

/*
 * __db_txnlist_update --
 *	Change the status of an existing transaction entry.
 *	Returns DB_NOTFOUND if no such entry exists.
 *
 * PUBLIC: int __db_txnlist_update __P((DB_ENV *,
 * PUBLIC:     void *, u_int32_t, u_int32_t, DB_LSN *, u_int32_t *, int));
 */
int
__db_txnlist_update(dbenv, listp, txnid, status, lsn, ret_status, add_ok)
	DB_ENV *dbenv;
	void *listp;
	u_int32_t txnid, status;
	DB_LSN *lsn;
	u_int32_t *ret_status;
	int add_ok;
{
	DB_TXNHEAD *hp;
	DB_TXNLIST *elp;
	int ret;

	if (txnid == 0)
		return (DB_NOTFOUND);

	hp = (DB_TXNHEAD *)listp;
	ret = __db_txnlist_find_internal(dbenv,
	    listp, TXNLIST_TXNID, txnid, NULL, &elp, 0, ret_status);

	if (ret == DB_NOTFOUND && add_ok) {
		*ret_status = status;
		return (__db_txnlist_add(dbenv, listp, txnid, status, lsn));
	}
	if (ret != 0)
		return (ret);

	if (*ret_status == TXN_IGNORE)
		return (0);

	elp->u.t.status = status;

	if (lsn != NULL && IS_ZERO_LSN(hp->maxlsn) && status == TXN_COMMIT)
		hp->maxlsn = *lsn;

	return (ret);
}

/*
 * __db_txnlist_find_internal --
 *	Find an entry on the transaction list.  If the entry is not there or
 *	the list pointer is not initialized we return DB_NOTFOUND.  If the
 *	item is found, we return the status.  Currently we always call this
 *	with an initialized list pointer but checking for NULL keeps it general.
 */
static int
__db_txnlist_find_internal(dbenv,
    listp, type, txnid, uid, txnlistp, delete, statusp)
	DB_ENV *dbenv;
	void *listp;
	db_txnlist_type type;
	u_int32_t  txnid;
	u_int8_t uid[DB_FILE_ID_LEN];
	DB_TXNLIST **txnlistp;
	int delete;
	u_int32_t *statusp;
{
	struct __db_headlink *head;
	DB_TXNHEAD *hp;
	DB_TXNLIST *p;
	u_int32_t generation, hash, i;
	int ret;

	ret = 0;

	if ((hp = (DB_TXNHEAD *)listp) == NULL)
		return (DB_NOTFOUND);

	switch (type) {
	case TXNLIST_TXNID:
		hash = txnid;
		/* Find the most recent generation containing this ID */
		for (i = 0; i <= hp->generation; i++)
			/* The range may wrap around the end. */
			if (hp->gen_array[i].txn_min <
			    hp->gen_array[i].txn_max ?
			    (txnid >= hp->gen_array[i].txn_min &&
			    txnid <= hp->gen_array[i].txn_max) :
			    (txnid >= hp->gen_array[i].txn_min ||
			    txnid <= hp->gen_array[i].txn_max))
				break;
		DB_ASSERT(i <= hp->generation);
		generation = hp->gen_array[i].generation;
		break;
	case TXNLIST_PGNO:
		memcpy(&hash, uid, sizeof(hash));
		generation = 0;
		break;
	case TXNLIST_DELETE:
	case TXNLIST_LSN:
	default:
		return (__db_panic(dbenv, EINVAL));
	}

	head = &hp->head[DB_TXNLIST_MASK(hp, hash)];

	for (p = LIST_FIRST(head); p != NULL; p = LIST_NEXT(p, links)) {
		if (p->type != type)
			continue;
		switch (type) {
		case TXNLIST_TXNID:
			if (p->u.t.txnid != txnid ||
			    generation != p->u.t.generation)
				continue;
			*statusp = p->u.t.status;
			break;

		case TXNLIST_PGNO:
			if (memcmp(uid, p->u.p.uid, DB_FILE_ID_LEN) != 0)
				continue;
			break;
		case TXNLIST_DELETE:
		case TXNLIST_LSN:
		default:
			return (__db_panic(dbenv, EINVAL));
		}
		if (delete == 1) {
			LIST_REMOVE(p, links);
			__os_free(dbenv, p);
		} else if (p != LIST_FIRST(head)) {
			/* Move it to head of list. */
			LIST_REMOVE(p, links);
			LIST_INSERT_HEAD(head, p, links);
		}
		*txnlistp = p;
		return (ret);
	}

	return (DB_NOTFOUND);
}

/*
 * __db_txnlist_gen --
 *	Change the current generation number.
 *
 * PUBLIC: int __db_txnlist_gen __P((DB_ENV *,
 * PUBLIC:       void *, int, u_int32_t, u_int32_t));
 */
int
__db_txnlist_gen(dbenv, listp, incr, min, max)
	DB_ENV *dbenv;
	void *listp;
	int incr;
	u_int32_t min, max;
{
	DB_TXNHEAD *hp;
	int ret;

	/*
	 * During recovery generation numbers keep track of "restart"
	 * checkpoints and recycle records.  Restart checkpoints occur
	 * whenever we take a checkpoint and there are no outstanding
	 * transactions.  When that happens, we can reset transaction IDs
	 * back to TXNID_MINIMUM.  Currently we only do the reset
	 * at then end of recovery.  Recycle records occur when txnids
	 * are exhausted during runtime.  A free range of ids is identified
	 * and logged.  This code maintains a stack of ranges.  A txnid
	 * is given the generation number of the first range it falls into
	 * in the stack.
	 */
	hp = (DB_TXNHEAD *)listp;
	if (incr < 0) {
		--hp->generation;
		memmove(hp->gen_array, &hp->gen_array[1],
		    (hp->generation + 1) * sizeof(hp->gen_array[0]));
	} else {
		++hp->generation;
		if (hp->generation >= hp->gen_alloc) {
			hp->gen_alloc *= 2;
			if ((ret = __os_realloc(dbenv, hp->gen_alloc *
			    sizeof(hp->gen_array[0]), &hp->gen_array)) != 0)
				return (ret);
		}
		memmove(&hp->gen_array[1], &hp->gen_array[0],
		    hp->generation * sizeof(hp->gen_array[0]));
		hp->gen_array[0].generation = hp->generation;
		hp->gen_array[0].txn_min = min;
		hp->gen_array[0].txn_max = max;
	}
	return (0);
}

#define	TXN_BUBBLE(AP, MAX) {						\
	DB_LSN __tmp;							\
	u_int32_t __j;							\
									\
	for (__j = 0; __j < MAX - 1; __j++)				\
		if (log_compare(&AP[__j], &AP[__j + 1]) < 0) {		\
			__tmp = AP[__j];				\
			AP[__j] = AP[__j + 1];				\
			AP[__j + 1] = __tmp;				\
		}							\
}

/*
 * __db_txnlist_lsnadd --
 *	Add to or re-sort the transaction list lsn entry.  Note that since this
 *	is used during an abort, the __txn_undo code calls into the "recovery"
 *	subsystem explicitly, and there is only a single TXNLIST_LSN entry on
 *	the list.
 *
 * PUBLIC: int __db_txnlist_lsnadd __P((DB_ENV *, void *, DB_LSN *, u_int32_t));
 */
int
__db_txnlist_lsnadd(dbenv, listp, lsnp, flags)
	DB_ENV *dbenv;
	void *listp;
	DB_LSN *lsnp;
	u_int32_t flags;
{
	DB_TXNHEAD *hp;
	DB_TXNLIST *elp;
	u_int32_t i;
	int ret;

	hp = (DB_TXNHEAD *)listp;

	for (elp = LIST_FIRST(&hp->head[0]);
	    elp != NULL; elp = LIST_NEXT(elp, links))
		if (elp->type == TXNLIST_LSN)
			break;

	if (elp == NULL)
		return (DB_SURPRISE_KID);

	if (LF_ISSET(TXNLIST_NEW)) {
		if (elp->u.l.ntxns >= elp->u.l.maxn) {
			if ((ret = __os_realloc(dbenv,
			    2 * elp->u.l.maxn * sizeof(DB_LSN),
			    &elp->u.l.lsn_array)) != 0)
				return (ret);
			elp->u.l.maxn *= 2;
		}
		elp->u.l.lsn_array[elp->u.l.ntxns++] = *lsnp;
	} else
		/* Simply replace the 0th element. */
		elp->u.l.lsn_array[0] = *lsnp;

	/*
	 * If we just added a new entry and there may be NULL entries, so we
	 * have to do a complete bubble sort, not just trickle a changed entry
	 * around.
	 */
	for (i = 0; i < (!LF_ISSET(TXNLIST_NEW) ? 1 : elp->u.l.ntxns); i++)
		TXN_BUBBLE(elp->u.l.lsn_array, elp->u.l.ntxns);

	*lsnp = elp->u.l.lsn_array[0];

	return (0);
}

/*
 * __db_txnlist_lsninit --
 *	Initialize a transaction list with an lsn array entry.
 *
 * PUBLIC: int __db_txnlist_lsninit __P((DB_ENV *, DB_TXNHEAD *, DB_LSN *));
 */
int
__db_txnlist_lsninit(dbenv, hp, lsnp)
	DB_ENV *dbenv;
	DB_TXNHEAD *hp;
	DB_LSN *lsnp;
{
	DB_TXNLIST *elp;
	int ret;

	elp = NULL;

	if ((ret = __os_malloc(dbenv, sizeof(DB_TXNLIST), &elp)) != 0)
		goto err;
	LIST_INSERT_HEAD(&hp->head[0], elp, links);

	if ((ret = __os_malloc(dbenv,
	    12 * sizeof(DB_LSN), &elp->u.l.lsn_array)) != 0)
		goto err;
	elp->type = TXNLIST_LSN;
	elp->u.l.maxn = 12;
	elp->u.l.ntxns = 1;
	elp->u.l.lsn_array[0] = *lsnp;

	return (0);

err:	__db_txnlist_end(dbenv, hp);
	return (ret);
}

#ifndef HAVE_FTRUNCATE
/*
 * __db_add_limbo -- add pages to the limbo list.
 *	Get the file information and call pgnoadd for each page.
 *
 * PUBLIC: #ifndef HAVE_FTRUNCATE
 * PUBLIC: int __db_add_limbo __P((DB_ENV *,
 * PUBLIC:      void *, int32_t, db_pgno_t, int32_t));
 * PUBLIC: #endif
 */
int
__db_add_limbo(dbenv, info, fileid, pgno, count)
	DB_ENV *dbenv;
	void *info;
	int32_t fileid;
	db_pgno_t pgno;
	int32_t count;
{
	DB_LOG *dblp;
	FNAME *fnp;
	int ret;

	dblp = dbenv->lg_handle;
	if ((ret = __dbreg_id_to_fname(dblp, fileid, 0, &fnp)) != 0)
		return (ret);

	do {
		if ((ret =
		    __db_txnlist_pgnoadd(dbenv, info, fileid, fnp->ufid,
		    R_ADDR(&dblp->reginfo, fnp->name_off), pgno)) != 0)
			return (ret);
		pgno++;
	} while (--count != 0);

	return (0);
}

/*
 * __db_do_the_limbo -- move pages from limbo to free.
 *
 * Limbo processing is what ensures that we correctly handle and
 * recover from page allocations.  During recovery, for each database,
 * we process each in-question allocation, link them into the free list
 * and then write out the new meta-data page that contains the pointer
 * to the new beginning of the free list.  On an abort, we use our
 * standard __db_free mechanism in a compensating transaction which logs
 * the specific modifications to the free list.
 *
 * If we run out of log space during an abort, then we can't write the
 * compensating transaction, so we abandon the idea of a compensating
 * transaction, and go back to processing how we do during recovery.
 * The reason that this is not the norm is that it's expensive: it requires
 * that we flush any database with an in-question allocation.  Thus if
 * a compensating transaction fails, we never try to restart it.
 *
 * Since files may be open and closed within transactions (in particular,
 * the master database for subdatabases), we must be prepared to open
 * files during this process.  If there is a compensating transaction, we
 * can open the files in that transaction.  If this was an abort and there
 * is no compensating transaction, then we've got to perform these opens
 * in the context of the aborting transaction so that we do not deadlock.
 * During recovery, there's no locking, so this isn't an issue.
 *
 * What you want to keep in mind when reading this is that there are two
 * algorithms going on here:  ctxn == NULL, then we're either in recovery
 * or our compensating transaction has failed and we're doing the
 * "create list and write meta-data page" algorithm.  Otherwise, we're in
 * an abort and doing the "use compensating transaction" algorithm.
 *
 * PUBLIC: #ifndef HAVE_FTRUNCATE
 * PUBLIC: int __db_do_the_limbo __P((DB_ENV *,
 * PUBLIC:     DB_TXN *, DB_TXN *, DB_TXNHEAD *, db_limbo_state));
 * PUBLIC: #endif
 */
int
__db_do_the_limbo(dbenv, ptxn, txn, hp, state)
	DB_ENV *dbenv;
	DB_TXN *ptxn, *txn;
	DB_TXNHEAD *hp;
	db_limbo_state state;
{
	DB_TXNLIST *elp;
	u_int32_t h;
	int ret;

	ret = 0;
	/*
	 * The slots correspond to hash buckets.  We've hashed the
	 * fileids into hash buckets and need to pick up all affected
	 * files. (There will only be a single slot for an abort.)
	 */
	for (h = 0; h < hp->nslots; h++) {
		if ((elp = LIST_FIRST(&hp->head[h])) == NULL)
			continue;
		if (ptxn != NULL) {
			if ((ret =
			    __db_limbo_move(dbenv, ptxn, txn, elp)) != 0)
				goto err;
		} else if ((ret =
		    __db_limbo_bucket(dbenv, txn, elp, state)) != 0)
			goto err;
	}

err:	if (ret != 0) {
		__db_err(dbenv, "Fatal error in abort of an allocation");
		ret = __db_panic(dbenv, ret);
	}

	return (ret);
}

/* Limbo support routines. */

/*
 * __db_lock_move --
 *	Move a lock from child to parent.
 */
static int
__db_lock_move(dbenv, fileid, pgno, mode, ptxn, txn)
	DB_ENV *dbenv;
	u_int8_t *fileid;
	db_pgno_t pgno;
	db_lockmode_t mode;
	DB_TXN *ptxn, *txn;
{
	DBT lock_dbt;
	DB_LOCK lock;
	DB_LOCK_ILOCK lock_obj;
	DB_LOCKREQ req;
	int ret;

	lock_obj.pgno = pgno;
	memcpy(lock_obj.fileid, fileid, DB_FILE_ID_LEN);
	lock_obj.type = DB_PAGE_LOCK;

	memset(&lock_dbt, 0, sizeof(lock_dbt));
	lock_dbt.data = &lock_obj;
	lock_dbt.size = sizeof(lock_obj);

	if ((ret = __lock_get(dbenv,
	    txn->txnid, 0, &lock_dbt, mode, &lock)) == 0) {
		memset(&req, 0, sizeof(req));
		req.lock = lock;
		req.op = DB_LOCK_TRADE;
		ret = __lock_vec(dbenv, ptxn->txnid, 0, &req, 1, NULL);
	}
	return (ret);
}

/*
 * __db_limbo_move
 *	Move just the metapage lock to the parent.
 */
static int
__db_limbo_move(dbenv, ptxn, txn, elp)
	DB_ENV *dbenv;
	DB_TXN *ptxn, *txn;
	DB_TXNLIST *elp;
{
	int ret;

	for (; elp != NULL; elp = LIST_NEXT(elp, links)) {
		if (elp->type != TXNLIST_PGNO || elp->u.p.locked == 1)
			continue;
		if ((ret = __db_lock_move(dbenv, elp->u.p.uid,
		    PGNO_BASE_MD, DB_LOCK_WRITE, ptxn, txn)) != 0)
			return (ret);
		elp->u.p.locked = 1;
	}

	return (0);
}
/*
 * __db_limbo_bucket
 *	Perform limbo processing for a single hash bucket in the txnlist.
 * txn is the transaction aborting in the case of an abort and ctxn is the
 * compensating transaction.
 */

#define	T_RESTORED(txn)       ((txn) != NULL && F_ISSET(txn, TXN_RESTORED))
static int
__db_limbo_bucket(dbenv, txn, elp, state)
	DB_ENV *dbenv;