bnode.c

ARM 嵌入式 系统 设计与实例开发 实验教材 二源码

/*
 * linux/fs/hfs/bnode.c
 *
 * Copyright (C) 1995-1997  Paul H. Hargrove
 * This file may be distributed under the terms of the GNU General Public License.
 *
 * This file contains the code to access nodes in the B-tree structure.
 *
 * "XXX" in a comment is a note to myself to consider changing something.
 *
 * In function preconditions the term "valid" applied to a pointer to
 * a structure means that the pointer is non-NULL and the structure it
 * points to has all fields initialized to consistent values.
 *
 * The code in this file initializes some structures which contain
 * pointers by calling memset(&foo, 0, sizeof(foo)).
 * This produces the desired behavior only due to the non-ANSI
 * assumption that the machine representation of NULL is all zeros.
 */

#include "hfs_btree.h"

/*================ File-local variables ================*/
 
/* debugging statistics */
#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
int bnode_count = 0;
#endif

/*================ Global functions ================*/

/*
 * hfs_bnode_delete()
 *
 * Description:
 *   This function is called to remove a bnode from the cache and
 *   release its resources.
 * Input Variable(s):
 *   struct hfs_bnode *bn: Pointer to the (struct hfs_bnode) to be
 *   removed from the cache.
 * Output Variable(s):
 *   NONE
 * Returns:
 *   void
 * Preconditions:
 *   'bn' points to a "valid" (struct hfs_bnode).
 * Postconditions:
 *   The node 'bn' is removed from the cache, its memory freed and its
 *   buffer (if any) released.
 */
void hfs_bnode_delete(struct hfs_bnode *bn)
{
#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
	--bnode_count;
#endif
	/* join neighbors */
	if (bn->next) {
		bn->next->prev = bn->prev;
	}
	if (bn->prev) {
		bn->prev->next = bn->next;
	}
	/* fix cache slot if necessary */
	if (bhash(bn->tree, bn->node) == bn) {
		bhash(bn->tree, bn->node) = bn->next;
	}
	/* release resources */
	hfs_buffer_put(bn->buf); /* safe: checks for NULL argument */
	HFS_DELETE(bn);
}


/*
 * hfs_bnode_read()
 *
 * Description: 
 *   This function creates a (struct hfs_bnode) and, if appropriate,
 *   inserts it in the cache.
 * Input Variable(s):
 *   struct hfs_bnode *bnode: pointer to the new bnode.
 *   struct hfs_btree *tree: pointer to the (struct hfs_btree)
 *    containing the desired node
 *   hfs_u32 node: the number of the desired node.
 *   int sticky: the value to assign to the 'sticky' field.
 * Output Variable(s):
 *   NONE
 * Returns:
 *   (struct hfs_bnode *) pointing to the newly created bnode or NULL.
 * Preconditions:
 *   'bnode' points to a "valid" (struct hfs_bnode).
 *   'tree' points to a "valid" (struct hfs_btree).
 *   'node' is an existing node number in the B-tree.
 * Postconditions:
 *   The following are true of 'bnode' upon return:
 *    The 'magic' field is set to indicate a valid (struct hfs_bnode). 
 *    The 'sticky', 'tree' and 'node' fields are initialized to the
 *    values of the of the corresponding arguments.
 *    If the 'sticky' argument is zero then the fields 'prev' and
 *    'next' are initialized by inserting the (struct hfs_bnode) in the
 *    linked list of the appropriate cache slot; otherwise they are
 *    initialized to NULL.
 *    The data is read from disk (or buffer cache) and the 'buf' field
 *    points to the buffer for that data.
 *    If no other processes tried to access this node while this
 *    process was waiting on disk I/O (if necessary) then the
 *    remaining fields are zero ('count', 'resrv', 'lock') or NULL
 *    ('wqueue', 'rqueue') corresponding to no accesses.
 *    If there were access attempts during I/O then they were blocked
 *    until the I/O was complete, and the fields 'count', 'resrv',
 *    'lock', 'wqueue' and 'rqueue' reflect the results of unblocking
 *    those processes when the I/O was completed.
 */
void hfs_bnode_read(struct hfs_bnode *bnode, struct hfs_btree *tree,
		    hfs_u32 node, int sticky)
{
	struct NodeDescriptor *nd;
	int block, lcv;
	hfs_u16 curr, prev, limit;

	/* Initialize the structure */
	memset(bnode, 0, sizeof(*bnode));
	bnode->magic = HFS_BNODE_MAGIC;
	bnode->tree = tree;
	bnode->node = node;
	bnode->sticky = sticky;
	hfs_init_waitqueue(&bnode->rqueue);
	hfs_init_waitqueue(&bnode->wqueue);

	if (sticky == HFS_NOT_STICKY) {
		/* Insert it in the cache if appropriate */
		if ((bnode->next = bhash(tree, node))) {
			bnode->next->prev = bnode;
		}
		bhash(tree, node) = bnode;
	}

	/* Make the bnode look like it is being
	   modified so other processes will wait for
	   the I/O to complete */
	bnode->count = bnode->resrv = bnode->lock = 1;

	/* Read in the node, possibly causing a schedule()
	   call.  If the I/O fails then emit a warning.	 Each
	   process that was waiting on the bnode (including
	   the current one) will notice the failure and
	   hfs_bnode_relse() the node.	The last hfs_bnode_relse()
	   will call hfs_bnode_delete() and discard the bnode.	*/

	block = hfs_extent_map(&tree->entry.u.file.data_fork, node, 0);
	if (!block) {
		hfs_warn("hfs_bnode_read: bad node number 0x%08x\n", node);
	} else if (hfs_buffer_ok(bnode->buf =
				 hfs_buffer_get(tree->sys_mdb, block, 1))) {
		/* read in the NodeDescriptor */
		nd = (struct NodeDescriptor *)hfs_buffer_data(bnode->buf);
		bnode->ndFLink    = hfs_get_hl(nd->ndFLink);
		bnode->ndBLink    = hfs_get_hl(nd->ndBLink);
		bnode->ndType     = nd->ndType;
		bnode->ndNHeight  = nd->ndNHeight;
		bnode->ndNRecs    = hfs_get_hs(nd->ndNRecs);

		/* verify the integrity of the node */
		prev = sizeof(struct NodeDescriptor);
		limit = HFS_SECTOR_SIZE - sizeof(hfs_u16)*(bnode->ndNRecs + 1);
		for (lcv=1; lcv <= (bnode->ndNRecs + 1); ++lcv) {
			curr = hfs_get_hs(RECTBL(bnode, lcv));
			if ((curr < prev) || (curr > limit)) {
				hfs_warn("hfs_bnode_read: corrupt node "
					 "number 0x%08x\n", node);
				hfs_buffer_put(bnode->buf);
				bnode->buf = NULL;
				break;
			}
			prev = curr;
		}
	}

	/* Undo our fakery with the lock state and
	   hfs_wake_up() anyone who we managed to trick */
	--bnode->count;
	bnode->resrv = bnode->lock = 0;
	hfs_wake_up(&bnode->rqueue);
}

/*
 * hfs_bnode_lock()
 *
 * Description:
 *   This function does the locking of a bnode.
 * Input Variable(s):
 *   struct hfs_bnode *bn: pointer to the (struct hfs_bnode) to lock
 *   int lock_type: the type of lock desired
 * Output Variable(s):
 *   NONE
 * Returns:
 *   void
 * Preconditions:
 *   'bn' points to a "valid" (struct hfs_bnode).
 *   'lock_type' is a valid hfs_lock_t
 * Postconditions:
 *   The 'count' field of 'bn' is incremented by one.  If 'lock_type'
 *   is HFS_LOCK_RESRV the 'resrv' field is also incremented.
 */
void hfs_bnode_lock(struct hfs_bnode_ref *bnr, int lock_type)
{
	struct hfs_bnode *bn = bnr->bn;

	if ((lock_type == bnr->lock_type) || !bn) {
		return;
	}

	if (bnr->lock_type == HFS_LOCK_WRITE) {
		hfs_bnode_commit(bnr->bn);
	}

	switch (lock_type) {
	default:
		goto bail;
		break;

	case HFS_LOCK_READ:
		/* We may not obtain read access if any process is
		   currently modifying or waiting to modify this node.
		   If we can't obtain access we wait on the rqueue
		   wait queue to be woken up by the modifying process
		   when it relinquishes its lock. */
		switch (bnr->lock_type) {
		default:
			goto bail;
			break;

		case HFS_LOCK_NONE:
			while (bn->lock || waitqueue_active(&bn->wqueue)) {
				hfs_sleep_on(&bn->rqueue);
			}
			++bn->count;
			break;
		}
		break;
			
	case HFS_LOCK_RESRV:
		/* We may not obtain a reservation (read access with
		   an option to write later), if any process currently
		   holds a reservation on this node.  That includes
		   any process which is currently modifying this node.
		   If we can't obtain access, then we wait on the
		   rqueue wait queue to e woken up by the
		   reservation-holder when it calls hfs_bnode_relse. */
		switch (bnr->lock_type) {
		default:
			goto bail;
			break;

		case HFS_LOCK_NONE:
			while (bn->resrv) {
				hfs_sleep_on(&bn->rqueue);
			}
			bn->resrv = 1;
			++bn->count;
			break;

		case HFS_LOCK_WRITE:
			bn->lock = 0;
			hfs_wake_up(&bn->rqueue);
			break;
		}
		break;
		
	case HFS_LOCK_WRITE:
		switch (bnr->lock_type) {
		default:
			goto bail;
			break;