extent.c

嵌入式系统设计与实验教材二源码linux内核移植与编译

/*
 * linux/fs/hfs/extent.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 functions related to the extents B-tree.
 *
 * "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.
 */

#include "hfs.h"

/*================ File-local data type ================*/

/* An extent record on disk*/
struct hfs_raw_extent {
	hfs_word_t	block1;
	hfs_word_t	length1;
	hfs_word_t	block2;
	hfs_word_t	length2;
	hfs_word_t	block3;
	hfs_word_t	length3;
};

/*================ File-local functions ================*/

/*
 * build_key
 */
static inline void build_key(struct hfs_ext_key *key,
			     const struct hfs_fork *fork, hfs_u16 block)
{
	key->KeyLen = 7;
	key->FkType = fork->fork;
	hfs_put_nl(fork->entry->cnid, key->FNum);
	hfs_put_hs(block,             key->FABN);
}


/*
 * lock_bitmap()
 *
 * Get an exclusive lock on the B-tree bitmap.
 */
static inline void lock_bitmap(struct hfs_mdb *mdb) {
	while (mdb->bitmap_lock) {
		hfs_sleep_on(&mdb->bitmap_wait);
	}
	mdb->bitmap_lock = 1;
}

/*
 * unlock_bitmap()
 *
 * Relinquish an exclusive lock on the B-tree bitmap.
 */
static inline void unlock_bitmap(struct hfs_mdb *mdb) {
	mdb->bitmap_lock = 0;
	hfs_wake_up(&mdb->bitmap_wait);
}

/*
 * dump_ext()
 *
 * prints the content of a extent for debugging purposes.
 */
#if defined(DEBUG_EXTENTS) || defined(DEBUG_ALL)
static void dump_ext(const char *msg, const struct hfs_extent *e) {
	if (e) {
		hfs_warn("%s (%d-%d) (%d-%d) (%d-%d)\n", msg,
			 e->start,
			 e->start + e->length[0] - 1,
			 e->start + e->length[0],
			 e->start + e->length[0] + e->length[1] - 1,
			 e->start + e->length[0] + e->length[1],
			 e->end);
	} else {
		hfs_warn("%s NULL\n", msg);
	}
}
#else
#define dump_ext(A,B) {}
#endif

/*
 * read_extent()
 * 
 * Initializes a (struct hfs_extent) from a (struct hfs_raw_extent) and
 * the number of the starting block for the extent.
 *
 * Note that the callers must check that to,from != NULL
 */
static void read_extent(struct hfs_extent *to,
			const struct hfs_raw_extent *from,
			hfs_u16 start)
{
	to->start = start;
	to->block[0]  = hfs_get_hs(from->block1);
	to->length[0] = hfs_get_hs(from->length1);
	to->block[1]  = hfs_get_hs(from->block2);
	to->length[1] = hfs_get_hs(from->length2);
	to->block[2]  = hfs_get_hs(from->block3);
	to->length[2] = hfs_get_hs(from->length3);
	to->end = start + to->length[0] + to->length[1] + to->length[2] - 1;
	to->next = to->prev = NULL;
	to->count = 0;
}

/*
 * write_extent()
 * 
 * Initializes a (struct hfs_raw_extent) from a (struct hfs_extent).
 *
 * Note that the callers must check that to,from != NULL
 */
static void write_extent(struct hfs_raw_extent *to,
			 const struct hfs_extent *from)
{
	hfs_put_hs(from->block[0], to->block1);
	hfs_put_hs(from->length[0], to->length1);
	hfs_put_hs(from->block[1], to->block2);
	hfs_put_hs(from->length[1], to->length2);
	hfs_put_hs(from->block[2], to->block3);
	hfs_put_hs(from->length[2], to->length3);
}

/*
 * decode_extent()
 *
 * Given an extent record and allocation block offset into the file,
 * return the number of the corresponding allocation block on disk,
 * or -1 if the desired block is not mapped by the given extent.
 *
 * Note that callers must check that extent != NULL
 */
static int decode_extent(const struct hfs_extent * extent, int block)
{
	if (!extent || (block < extent->start) || (block > extent->end) ||
	    (extent->end == (hfs_u16)(extent->start - 1))) {
		return -1;
	}
	block -= extent->start;
	if (block < extent->length[0]) {
		return block + extent->block[0];
	}
	block -= extent->length[0];
	if (block < extent->length[1]) {
		return block + extent->block[1];
	}
	return block + extent->block[2] - extent->length[1];
}

/*
 * relse_ext()
 *
 * Reduce the reference count of an in-core extent record by one,
 * removing it from memory if the count falls to zero.
 */
static void relse_ext(struct hfs_extent *ext)
{
	if (--ext->count || !ext->start) {
		return;
	}
	ext->prev->next = ext->next;
	if (ext->next) {
		ext->next->prev = ext->prev;
	}
	HFS_DELETE(ext);
}

/*
 * set_cache()
 * 
 * Changes the 'cache' field of the fork.
 */
static inline void set_cache(struct hfs_fork *fork, struct hfs_extent *ext)
{
	struct hfs_extent *tmp = fork->cache;

	++ext->count;
	fork->cache = ext;
	relse_ext(tmp);
}

/*
 * find_ext()
 *
 * Given a pointer to a (struct hfs_file) and an allocation block
 * number in the file, find the extent record containing that block.
 * Returns a pointer to the extent record on success or NULL on failure.
 * The 'cache' field of 'fil' also points to the extent so it has a
 * reference count of at least 2.
 *
 * Callers must check that fil != NULL
 */
static struct hfs_extent * find_ext(struct hfs_fork *fork, int alloc_block)
{
        struct hfs_cat_entry *entry = fork->entry;
	struct hfs_btree *tr= entry->mdb->ext_tree;
	struct hfs_ext_key target, *key;
	struct hfs_brec brec;
	struct hfs_extent *ext, *ptr;
	int tmp;

	if (alloc_block < 0) {
		ext = &fork->first;
		goto found;
	}

	ext = fork->cache;
	if (!ext || (alloc_block < ext->start)) {
		ext = &fork->first;
	}
	while (ext->next && (alloc_block > ext->end)) {
		ext = ext->next;
	}
	if ((alloc_block <= ext->end) && (alloc_block >= ext->start)) {
		goto found;
	}

	/* time to read more extents */
	if (!HFS_NEW(ext)) {
		goto bail3;
	}

	build_key(&target, fork, alloc_block);

	tmp = hfs_bfind(&brec, tr, HFS_BKEY(&target), HFS_BFIND_READ_LE);
	if (tmp < 0) {
		goto bail2;
	}

	key = (struct hfs_ext_key *)brec.key;
	if ((hfs_get_nl(key->FNum) != hfs_get_nl(target.FNum)) ||
	    (key->FkType != fork->fork)) {
		goto bail1;
	}
		
	read_extent(ext, brec.data, hfs_get_hs(key->FABN));
	hfs_brec_relse(&brec, NULL);

	if ((alloc_block > ext->end) && (alloc_block < ext->start)) {
		/* something strange happened */
		goto bail2;
	}

	ptr = fork->cache;
	if (!ptr || (alloc_block < ptr->start)) {
		ptr = &fork->first;
	}
	while (ptr->next && (alloc_block > ptr->end)) {
		ptr = ptr->next;
	}
	if (ext->start == ptr->start) {
		/* somebody beat us to it. */
		HFS_DELETE(ext);
		ext = ptr;
	} else if (ext->start < ptr->start) {
		/* insert just before ptr */
		ptr->prev->next = ext;
		ext->prev = ptr->prev;
		ext->next = ptr;
		ptr->prev = ext;
	} else {
		/* insert at end */
		ptr->next = ext;
		ext->prev = ptr;
	}
 found:
	++ext->count; /* for return value */
	set_cache(fork, ext);
	return ext;

 bail1:
	hfs_brec_relse(&brec, NULL);
 bail2:
	HFS_DELETE(ext);
 bail3:
	return NULL;
}

/*
 * delete_extent()
 *
 * Description:
 *   Deletes an extent record from a fork, reducing its physical length.
 * Input Variable(s):
 *   struct hfs_fork *fork: the fork
 *   struct hfs_extent *ext: the current last extent for 'fork'
 * Output Variable(s):
 *   NONE
 * Returns:
 *   void
 * Preconditions:
 *   'fork' points to a valid (struct hfs_fork)
 *   'ext' point to a valid (struct hfs_extent) which is the last in 'fork'
 *    and which is not also the first extent in 'fork'.
 * Postconditions:
 *   The extent record has been removed if possible, and a warning has been
 *   printed otherwise.
 */
static void delete_extent(struct hfs_fork *fork, struct hfs_extent *ext)
{
	struct hfs_mdb *mdb = fork->entry->mdb;
	struct hfs_ext_key key;
	int error;

	if (fork->cache == ext) {
		set_cache(fork, ext->prev);
	}
	ext->prev->next = NULL;
	if (ext->count != 1) {
		hfs_warn("hfs_truncate: extent has count %d.\n", ext->count);
	}

	lock_bitmap(mdb);
	error = hfs_clear_vbm_bits(mdb, ext->block[2], ext->length[2]);
	if (error) {
		hfs_warn("hfs_truncate: error %d freeing blocks.\n", error);
	}
	error = hfs_clear_vbm_bits(mdb, ext->block[1], ext->length[1]);
	if (error) {
		hfs_warn("hfs_truncate: error %d freeing blocks.\n", error);
	}
	error = hfs_clear_vbm_bits(mdb, ext->block[0], ext->length[0]);
	if (error) {
		hfs_warn("hfs_truncate: error %d freeing blocks.\n", error);
	}
	unlock_bitmap(mdb);

	build_key(&key, fork, ext->start);

	error = hfs_bdelete(mdb->ext_tree, HFS_BKEY(&key));
	if (error) {
		hfs_warn("hfs_truncate: error %d deleting an extent.\n", error);
	}

	HFS_DELETE(ext);
}

/*
 * new_extent()
 *
 * Description:
 *   Adds a new extent record to a fork, extending its physical length.
 * Input Variable(s):
 *   struct hfs_fork *fork: the fork to extend
 *   struct hfs_extent *ext: the current last extent for 'fork'
 *   hfs_u16 ablock: the number of allocation blocks in 'fork'.
 *   hfs_u16 start: first allocation block to add to 'fork'.
 *   hfs_u16 len: the number of allocation blocks to add to 'fork'.
 *   hfs_u32 ablksz: number of sectors in an allocation block.
 * Output Variable(s):
 *   NONE
 * Returns:
 *   (struct hfs_extent *) the new extent or NULL
 * Preconditions:
 *   'fork' points to a valid (struct hfs_fork)
 *   'ext' point to a valid (struct hfs_extent) which is the last in 'fork'
 *   'ablock', 'start', 'len' and 'ablksz' are what they claim to be.
 * Postconditions:
 *   If NULL is returned then no changes have been made to 'fork'.
 *   If the return value is non-NULL that it is the extent that has been
 *   added to 'fork' both in memory and on disk.  The 'psize' field of
 *   'fork' has been updated to reflect the new physical size.
 */
static struct hfs_extent *new_extent(struct hfs_fork *fork,
				     struct hfs_extent *ext,
				     hfs_u16 ablock, hfs_u16 start,
				     hfs_u16 len, hfs_u16 ablksz)
{
	struct hfs_raw_extent raw;
	struct hfs_ext_key key;
	int error;

	if (fork->entry->cnid == htonl(HFS_EXT_CNID)) {
		/* Limit extents tree to the record in the MDB */
		return NULL;
	}

	if (!HFS_NEW(ext->next)) {
		return NULL;
	}
	ext->next->prev = ext;
	ext->next->next = NULL;
	ext = ext->next;
	relse_ext(ext->prev);

	ext->start = ablock;
	ext->block[0] = start;
	ext->length[0] = len;
	ext->block[1] = 0;
	ext->length[1] = 0;
	ext->block[2] = 0;
	ext->length[2] = 0;
	ext->end = ablock + len - 1;
	ext->count = 1;

	write_extent(&raw, ext);