[linux.git] / fs / hfs / extent.c

/*
 *  linux/fs/hfs/extent.c
 *
 * Copyright (C) 1995-1997  Paul H. Hargrove
 * (C) 2003 Ardis Technologies <[email protected]>
 * 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.
 */

#include <linux/pagemap.h>

#include "hfs_fs.h"
#include "btree.h"

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

/*
 * build_key
 */
static void hfs_ext_build_key(hfs_btree_key *key, u32 cnid, u16 block, u8 type)
{
	key->key_len = 7;
	key->ext.FkType = type;
	key->ext.FNum = cpu_to_be32(cnid);
	key->ext.FABN = cpu_to_be16(block);
}

/*
 * hfs_ext_compare()
 *
 * Description:
 *   This is the comparison function used for the extents B-tree.  In
 *   comparing extent B-tree entries, the file id is the most
 *   significant field (compared as unsigned ints); the fork type is
 *   the second most significant field (compared as unsigned chars);
 *   and the allocation block number field is the least significant
 *   (compared as unsigned ints).
 * Input Variable(s):
 *   struct hfs_ext_key *key1: pointer to the first key to compare
 *   struct hfs_ext_key *key2: pointer to the second key to compare
 * Output Variable(s):
 *   NONE
 * Returns:
 *   int: negative if key1<key2, positive if key1>key2, and 0 if key1==key2
 * Preconditions:
 *   key1 and key2 point to "valid" (struct hfs_ext_key)s.
 * Postconditions:
 *   This function has no side-effects */
int hfs_ext_keycmp(const btree_key *key1, const btree_key *key2)
{
	__be32 fnum1, fnum2;
	__be16 block1, block2;

	fnum1 = key1->ext.FNum;
	fnum2 = key2->ext.FNum;
	if (fnum1 != fnum2)
		return be32_to_cpu(fnum1) < be32_to_cpu(fnum2) ? -1 : 1;
	if (key1->ext.FkType != key2->ext.FkType)
		return key1->ext.FkType < key2->ext.FkType ? -1 : 1;

	block1 = key1->ext.FABN;
	block2 = key2->ext.FABN;
	if (block1 == block2)
		return 0;
	return be16_to_cpu(block1) < be16_to_cpu(block2) ? -1 : 1;
}

/*
 * hfs_ext_find_block
 *
 * Find a block within an extent record
 */
static u16 hfs_ext_find_block(struct hfs_extent *ext, u16 off)
{
	int i;
	u16 count;

	for (i = 0; i < 3; ext++, i++) {
		count = be16_to_cpu(ext->count);
		if (off < count)
			return be16_to_cpu(ext->block) + off;
		off -= count;
	}
	/* panic? */
	return 0;
}

static int hfs_ext_block_count(struct hfs_extent *ext)
{
	int i;
	u16 count = 0;

	for (i = 0; i < 3; ext++, i++)
		count += be16_to_cpu(ext->count);
	return count;
}

static u16 hfs_ext_lastblock(struct hfs_extent *ext)
{
	int i;

	ext += 2;
	for (i = 0; i < 2; ext--, i++)
		if (ext->count)
			break;
	return be16_to_cpu(ext->block) + be16_to_cpu(ext->count);
}

static int __hfs_ext_write_extent(struct inode *inode, struct hfs_find_data *fd)
{
	int res;

	hfs_ext_build_key(fd->search_key, inode->i_ino, HFS_I(inode)->cached_start,
			  HFS_IS_RSRC(inode) ?  HFS_FK_RSRC : HFS_FK_DATA);
	res = hfs_brec_find(fd);
	if (HFS_I(inode)->flags & HFS_FLG_EXT_NEW) {
		if (res != -ENOENT)
			return res;
		hfs_brec_insert(fd, HFS_I(inode)->cached_extents, sizeof(hfs_extent_rec));
		HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
	} else {
		if (res)
			return res;
		hfs_bnode_write(fd->bnode, HFS_I(inode)->cached_extents, fd->entryoffset, fd->entrylength);
		HFS_I(inode)->flags &= ~HFS_FLG_EXT_DIRTY;
	}
	return 0;
}

int hfs_ext_write_extent(struct inode *inode)
{
	struct hfs_find_data fd;
	int res = 0;

	if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) {
		res = hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
		if (res)
			return res;
		res = __hfs_ext_write_extent(inode, &fd);
		hfs_find_exit(&fd);
	}
	return res;
}

static inline int __hfs_ext_read_extent(struct hfs_find_data *fd, struct hfs_extent *extent,
					u32 cnid, u32 block, u8 type)
{
	int res;

	hfs_ext_build_key(fd->search_key, cnid, block, type);
	fd->key->ext.FNum = 0;
	res = hfs_brec_find(fd);
	if (res && res != -ENOENT)
		return res;
	if (fd->key->ext.FNum != fd->search_key->ext.FNum ||
	    fd->key->ext.FkType != fd->search_key->ext.FkType)
		return -ENOENT;
	if (fd->entrylength != sizeof(hfs_extent_rec))
		return -EIO;
	hfs_bnode_read(fd->bnode, extent, fd->entryoffset, sizeof(hfs_extent_rec));
	return 0;
}

static inline int __hfs_ext_cache_extent(struct hfs_find_data *fd, struct inode *inode, u32 block)
{
	int res;

	if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) {
		res = __hfs_ext_write_extent(inode, fd);
		if (res)
			return res;
	}

	res = __hfs_ext_read_extent(fd, HFS_I(inode)->cached_extents, inode->i_ino,
				    block, HFS_IS_RSRC(inode) ? HFS_FK_RSRC : HFS_FK_DATA);
	if (!res) {
		HFS_I(inode)->cached_start = be16_to_cpu(fd->key->ext.FABN);
		HFS_I(inode)->cached_blocks = hfs_ext_block_count(HFS_I(inode)->cached_extents);
	} else {
		HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
		HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
	}
	return res;
}

static int hfs_ext_read_extent(struct inode *inode, u16 block)
{
	struct hfs_find_data fd;
	int res;

	if (block >= HFS_I(inode)->cached_start &&
	    block < HFS_I(inode)->cached_start + HFS_I(inode)->cached_blocks)
		return 0;

	res = hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
	if (!res) {
		res = __hfs_ext_cache_extent(&fd, inode, block);
		hfs_find_exit(&fd);
	}
	return res;
}

static void hfs_dump_extent(struct hfs_extent *extent)
{
	int i;

	hfs_dbg(EXTENT, "   ");
	for (i = 0; i < 3; i++)
		hfs_dbg_cont(EXTENT, " %u:%u",
			     be16_to_cpu(extent[i].block),
			     be16_to_cpu(extent[i].count));
	hfs_dbg_cont(EXTENT, "\n");
}

static int hfs_add_extent(struct hfs_extent *extent, u16 offset,
			  u16 alloc_block, u16 block_count)
{
	u16 count, start;
	int i;

	hfs_dump_extent(extent);
	for (i = 0; i < 3; extent++, i++) {
		count = be16_to_cpu(extent->count);
		if (offset == count) {
			start = be16_to_cpu(extent->block);
			if (alloc_block != start + count) {
				if (++i >= 3)
					return -ENOSPC;
				extent++;
				extent->block = cpu_to_be16(alloc_block);
			} else
				block_count += count;
			extent->count = cpu_to_be16(block_count);
			return 0;
		} else if (offset < count)
			break;
		offset -= count;
	}
	/* panic? */
	return -EIO;
}

static int hfs_free_extents(struct super_block *sb, struct hfs_extent *extent,
			    u16 offset, u16 block_nr)
{
	u16 count, start;
	int i;

	hfs_dump_extent(extent);
	for (i = 0; i < 3; extent++, i++) {
		count = be16_to_cpu(extent->count);
		if (offset == count)
			goto found;
		else if (offset < count)
			break;
		offset -= count;
	}
	/* panic? */
	return -EIO;
found:
	for (;;) {
		start = be16_to_cpu(extent->block);
		if (count <= block_nr) {
			hfs_clear_vbm_bits(sb, start, count);
			extent->block = 0;
			extent->count = 0;
			block_nr -= count;
		} else {
			count -= block_nr;
			hfs_clear_vbm_bits(sb, start + count, block_nr);
			extent->count = cpu_to_be16(count);
			block_nr = 0;
		}
		if (!block_nr || !i)
			return 0;
		i--;
		extent--;
		count = be16_to_cpu(extent->count);
	}
}

int hfs_free_fork(struct super_block *sb, struct hfs_cat_file *file, int type)
{
	struct hfs_find_data fd;
	u32 total_blocks, blocks, start;
	u32 cnid = be32_to_cpu(file->FlNum);
	struct hfs_extent *extent;
	int res, i;

	if (type == HFS_FK_DATA) {
		total_blocks = be32_to_cpu(file->PyLen);
		extent = file->ExtRec;
	} else {
		total_blocks = be32_to_cpu(file->RPyLen);
		extent = file->RExtRec;
	}
	total_blocks /= HFS_SB(sb)->alloc_blksz;
	if (!total_blocks)
		return 0;

	blocks = 0;
	for (i = 0; i < 3; extent++, i++)
		blocks += be16_to_cpu(extent[i].count);

	res = hfs_free_extents(sb, extent, blocks, blocks);
	if (res)
		return res;
	if (total_blocks == blocks)
		return 0;

	res = hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
	if (res)
		return res;
	do {
		res = __hfs_ext_read_extent(&fd, extent, cnid, total_blocks, type);
		if (res)
			break;
		start = be16_to_cpu(fd.key->ext.FABN);
		hfs_free_extents(sb, extent, total_blocks - start, total_blocks);
		hfs_brec_remove(&fd);
		total_blocks = start;
	} while (total_blocks > blocks);
	hfs_find_exit(&fd);

	return res;
}

/*
 * hfs_get_block
 */
int hfs_get_block(struct inode *inode, sector_t block,
		  struct buffer_head *bh_result, int create)
{
	struct super_block *sb;
	u16 dblock, ablock;
	int res;

	sb = inode->i_sb;
	/* Convert inode block to disk allocation block */
	ablock = (u32)block / HFS_SB(sb)->fs_div;

	if (block >= HFS_I(inode)->fs_blocks) {
		if (block > HFS_I(inode)->fs_blocks || !create)
			return -EIO;
		if (ablock >= HFS_I(inode)->alloc_blocks) {
			res = hfs_extend_file(inode);
			if (res)
				return res;
		}
	} else
		create = 0;

	if (ablock < HFS_I(inode)->first_blocks) {
		dblock = hfs_ext_find_block(HFS_I(inode)->first_extents, ablock);
		goto done;
	}

	mutex_lock(&HFS_I(inode)->extents_lock);
	res = hfs_ext_read_extent(inode, ablock);
	if (!res)
		dblock = hfs_ext_find_block(HFS_I(inode)->cached_extents,
					    ablock - HFS_I(inode)->cached_start);
	else {
		mutex_unlock(&HFS_I(inode)->extents_lock);
		return -EIO;
	}
	mutex_unlock(&HFS_I(inode)->extents_lock);

done:
	map_bh(bh_result, sb, HFS_SB(sb)->fs_start +
	       dblock * HFS_SB(sb)->fs_div +
	       (u32)block % HFS_SB(sb)->fs_div);

	if (create) {
		set_buffer_new(bh_result);
		HFS_I(inode)->phys_size += sb->s_blocksize;
		HFS_I(inode)->fs_blocks++;
		inode_add_bytes(inode, sb->s_blocksize);
		mark_inode_dirty(inode);
	}
	return 0;
}

int hfs_extend_file(struct inode *inode)
{
	struct super_block *sb = inode->i_sb;
	u32 start, len, goal;
	int res;

	mutex_lock(&HFS_I(inode)->extents_lock);
	if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks)
		goal = hfs_ext_lastblock(HFS_I(inode)->first_extents);
	else {
		res = hfs_ext_read_extent(inode, HFS_I(inode)->alloc_blocks);
		if (res)
			goto out;
		goal = hfs_ext_lastblock(HFS_I(inode)->cached_extents);
	}

	len = HFS_I(inode)->clump_blocks;
	start = hfs_vbm_search_free(sb, goal, &len);
	if (!len) {
		res = -ENOSPC;
		goto out;
	}

	hfs_dbg(EXTENT, "extend %lu: %u,%u\n", inode->i_ino, start, len);
	if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks) {
		if (!HFS_I(inode)->first_blocks) {
			hfs_dbg(EXTENT, "first extents\n");
			/* no extents yet */
			HFS_I(inode)->first_extents[0].block = cpu_to_be16(start);
			HFS_I(inode)->first_extents[0].count = cpu_to_be16(len);
			res = 0;
		} else {
			/* try to append to extents in inode */
			res = hfs_add_extent(HFS_I(inode)->first_extents,
					     HFS_I(inode)->alloc_blocks,
					     start, len);
			if (res == -ENOSPC)
				goto insert_extent;
		}
		if (!res) {
			hfs_dump_extent(HFS_I(inode)->first_extents);
			HFS_I(inode)->first_blocks += len;
		}
	} else {
		res = hfs_add_extent(HFS_I(inode)->cached_extents,
				     HFS_I(inode)->alloc_blocks -
				     HFS_I(inode)->cached_start,
				     start, len);
		if (!res) {
			hfs_dump_extent(HFS_I(inode)->cached_extents);
			HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY;
			HFS_I(inode)->cached_blocks += len;
		} else if (res == -ENOSPC)
			goto insert_extent;
	}
out:
	mutex_unlock(&HFS_I(inode)->extents_lock);
	if (!res) {
		HFS_I(inode)->alloc_blocks += len;
		mark_inode_dirty(inode);
		if (inode->i_ino < HFS_FIRSTUSER_CNID)
			set_bit(HFS_FLG_ALT_MDB_DIRTY, &HFS_SB(sb)->flags);
		set_bit(HFS_FLG_MDB_DIRTY, &HFS_SB(sb)->flags);
		hfs_mark_mdb_dirty(sb);
	}
	return res;

insert_extent:
	hfs_dbg(EXTENT, "insert new extent\n");
	res = hfs_ext_write_extent(inode);
	if (res)
		goto out;

	memset(HFS_I(inode)->cached_extents, 0, sizeof(hfs_extent_rec));
	HFS_I(inode)->cached_extents[0].block = cpu_to_be16(start);
	HFS_I(inode)->cached_extents[0].count = cpu_to_be16(len);
	hfs_dump_extent(HFS_I(inode)->cached_extents);
	HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW;
	HFS_I(inode)->cached_start = HFS_I(inode)->alloc_blocks;
	HFS_I(inode)->cached_blocks = len;

	res = 0;
	goto out;
}

void hfs_file_truncate(struct inode *inode)
{
	struct super_block *sb = inode->i_sb;
	struct hfs_find_data fd;
	u16 blk_cnt, alloc_cnt, start;
	u32 size;
	int res;

	hfs_dbg(INODE, "truncate: %lu, %Lu -> %Lu\n",
		inode->i_ino, (long long)HFS_I(inode)->phys_size,
		inode->i_size);
	if (inode->i_size > HFS_I(inode)->phys_size) {
		struct address_space *mapping = inode->i_mapping;
		void *fsdata;
		struct page *page;

		/* XXX: Can use generic_cont_expand? */
		size = inode->i_size - 1;
		res = pagecache_write_begin(NULL, mapping, size+1, 0, 0,
					    &page, &fsdata);
		if (!res) {
			res = pagecache_write_end(NULL, mapping, size+1, 0, 0,
					page, fsdata);
		}
		if (res)
			inode->i_size = HFS_I(inode)->phys_size;
		return;
	} else if (inode->i_size == HFS_I(inode)->phys_size)
		return;
	size = inode->i_size + HFS_SB(sb)->alloc_blksz - 1;
	blk_cnt = size / HFS_SB(sb)->alloc_blksz;
	alloc_cnt = HFS_I(inode)->alloc_blocks;
	if (blk_cnt == alloc_cnt)
		goto out;

	mutex_lock(&HFS_I(inode)->extents_lock);
	res = hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
	if (res) {
		mutex_unlock(&HFS_I(inode)->extents_lock);
		/* XXX: We lack error handling of hfs_file_truncate() */
		return;
	}
	while (1) {
		if (alloc_cnt == HFS_I(inode)->first_blocks) {
			hfs_free_extents(sb, HFS_I(inode)->first_extents,
					 alloc_cnt, alloc_cnt - blk_cnt);
			hfs_dump_extent(HFS_I(inode)->first_extents);
			HFS_I(inode)->first_blocks = blk_cnt;
			break;
		}
		res = __hfs_ext_cache_extent(&fd, inode, alloc_cnt);
		if (res)
			break;
		start = HFS_I(inode)->cached_start;
		hfs_free_extents(sb, HFS_I(inode)->cached_extents,
				 alloc_cnt - start, alloc_cnt - blk_cnt);
		hfs_dump_extent(HFS_I(inode)->cached_extents);
		if (blk_cnt > start) {
			HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY;
			break;
		}
		alloc_cnt = start;
		HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
		HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
		hfs_brec_remove(&fd);
	}
	hfs_find_exit(&fd);
	mutex_unlock(&HFS_I(inode)->extents_lock);

	HFS_I(inode)->alloc_blocks = blk_cnt;
out:
	HFS_I(inode)->phys_size = inode->i_size;
	HFS_I(inode)->fs_blocks = (inode->i_size + sb->s_blocksize - 1) >> sb->s_blocksize_bits;
	inode_set_bytes(inode, HFS_I(inode)->fs_blocks << sb->s_blocksize_bits);
	mark_inode_dirty(inode);
}
Commit	Line	Data
1da177e4 LT	1	/*
	2	* linux/fs/hfs/extent.c
	3	*
	4	* Copyright (C) 1995-1997 Paul H. Hargrove
	5	* (C) 2003 Ardis Technologies <[email protected]>
	6	* This file may be distributed under the terms of the GNU General Public License.
	7	*
	8	* This file contains the functions related to the extents B-tree.
	9	*/
	10
	11	#include <linux/pagemap.h>
	12
	13	#include "hfs_fs.h"
	14	#include "btree.h"
	15
	16	/================ File-local functions ================/
	17
	18	/*
	19	* build_key
	20	*/
	21	static void hfs_ext_build_key(hfs_btree_key *key, u32 cnid, u16 block, u8 type)
	22	{
	23	key->key_len = 7;
	24	key->ext.FkType = type;
	25	key->ext.FNum = cpu_to_be32(cnid);
	26	key->ext.FABN = cpu_to_be16(block);
	27	}
	28
	29	/*
	30	* hfs_ext_compare()
	31	*
	32	* Description:
	33	* This is the comparison function used for the extents B-tree. In
	34	* comparing extent B-tree entries, the file id is the most
	35	* significant field (compared as unsigned ints); the fork type is
	36	* the second most significant field (compared as unsigned chars);
	37	* and the allocation block number field is the least significant
	38	* (compared as unsigned ints).
	39	* Input Variable(s):
	40	* struct hfs_ext_key *key1: pointer to the first key to compare
	41	* struct hfs_ext_key *key2: pointer to the second key to compare
	42	* Output Variable(s):
	43	* NONE
	44	* Returns:
	45	* int: negative if key1<key2, positive if key1>key2, and 0 if key1==key2
	46	* Preconditions:
	47	* key1 and key2 point to "valid" (struct hfs_ext_key)s.
	48	* Postconditions:
	49	* This function has no side-effects */
	50	int hfs_ext_keycmp(const btree_key key1, const btree_key key2)
	51	{
	52	__be32 fnum1, fnum2;
	53	__be16 block1, block2;
	54
	55	fnum1 = key1->ext.FNum;
	56	fnum2 = key2->ext.FNum;
	57	if (fnum1 != fnum2)
	58	return be32_to_cpu(fnum1) < be32_to_cpu(fnum2) ? -1 : 1;
	59	if (key1->ext.FkType != key2->ext.FkType)
	60	return key1->ext.FkType < key2->ext.FkType ? -1 : 1;
	61
	62	block1 = key1->ext.FABN;
	63	block2 = key2->ext.FABN;
	64	if (block1 == block2)
65	return 0;
66	return be16_to_cpu(block1) < be16_to_cpu(block2) ? -1 : 1;
67	}
68
69	/*
70	* hfs_ext_find_block
71	*
72	* Find a block within an extent record
73	*/
74	static u16 hfs_ext_find_block(struct hfs_extent *ext, u16 off)
75	{
76	int i;
77	u16 count;
78
79	for (i = 0; i < 3; ext++, i++) {
80	count = be16_to_cpu(ext->count);
81	if (off < count)
82	return be16_to_cpu(ext->block) + off;
83	off -= count;
84	}
85	/* panic? */
86	return 0;
87	}
88
89	static int hfs_ext_block_count(struct hfs_extent *ext)
90	{
91	int i;
92	u16 count = 0;
93
94	for (i = 0; i < 3; ext++, i++)
95	count += be16_to_cpu(ext->count);
96	return count;
97	}
98
99	static u16 hfs_ext_lastblock(struct hfs_extent *ext)
100	{
101	int i;
102
103	ext += 2;
104	for (i = 0; i < 2; ext--, i++)
105	if (ext->count)
106	break;
107	return be16_to_cpu(ext->block) + be16_to_cpu(ext->count);
108	}
109
9509f178	110	static int __hfs_ext_write_extent(struct inode inode, struct hfs_find_data fd)
1da177e4 LT	111	{
	112	int res;
	113
	114	hfs_ext_build_key(fd->search_key, inode->i_ino, HFS_I(inode)->cached_start,
	115	HFS_IS_RSRC(inode) ? HFS_FK_RSRC : HFS_FK_DATA);
	116	res = hfs_brec_find(fd);
	117	if (HFS_I(inode)->flags & HFS_FLG_EXT_NEW) {
	118	if (res != -ENOENT)
9509f178	119	return res;
1da177e4 LT	120	hfs_brec_insert(fd, HFS_I(inode)->cached_extents, sizeof(hfs_extent_rec));
	121	HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY\|HFS_FLG_EXT_NEW);
	122	} else {
	123	if (res)
9509f178	124	return res;
1da177e4 LT	125	hfs_bnode_write(fd->bnode, HFS_I(inode)->cached_extents, fd->entryoffset, fd->entrylength);
	126	HFS_I(inode)->flags &= ~HFS_FLG_EXT_DIRTY;
	127	}
9509f178	128	return 0;
1da177e4 LT	129	}
1da177e4 LT	130
9509f178	131	int hfs_ext_write_extent(struct inode *inode)
1da177e4 LT	132	{
1da177e4 LT	133	struct hfs_find_data fd;
9509f178	134	int res = 0;
1da177e4 LT	135
1da177e4 LT	136	if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) {
9509f178 AK	137	res = hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
	138	if (res)
	139	return res;
	140	res = __hfs_ext_write_extent(inode, &fd);
1da177e4 LT	141	hfs_find_exit(&fd);
1da177e4 LT	142	}
9509f178	143	return res;
1da177e4 LT	144	}
	145
	146	static inline int __hfs_ext_read_extent(struct hfs_find_data fd, struct hfs_extent extent,
	147	u32 cnid, u32 block, u8 type)
	148	{
	149	int res;
	150
	151	hfs_ext_build_key(fd->search_key, cnid, block, type);
	152	fd->key->ext.FNum = 0;
	153	res = hfs_brec_find(fd);
	154	if (res && res != -ENOENT)
	155	return res;
	156	if (fd->key->ext.FNum != fd->search_key->ext.FNum \|\|
	157	fd->key->ext.FkType != fd->search_key->ext.FkType)
	158	return -ENOENT;
	159	if (fd->entrylength != sizeof(hfs_extent_rec))
	160	return -EIO;
	161	hfs_bnode_read(fd->bnode, extent, fd->entryoffset, sizeof(hfs_extent_rec));
	162	return 0;
	163	}
	164
	165	static inline int __hfs_ext_cache_extent(struct hfs_find_data fd, struct inode inode, u32 block)
	166	{
	167	int res;
	168
9509f178 AK	169	if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) {
	170	res = __hfs_ext_write_extent(inode, fd);
	171	if (res)
	172	return res;
	173	}
1da177e4 LT	174
	175	res = __hfs_ext_read_extent(fd, HFS_I(inode)->cached_extents, inode->i_ino,
	176	block, HFS_IS_RSRC(inode) ? HFS_FK_RSRC : HFS_FK_DATA);
	177	if (!res) {
	178	HFS_I(inode)->cached_start = be16_to_cpu(fd->key->ext.FABN);
	179	HFS_I(inode)->cached_blocks = hfs_ext_block_count(HFS_I(inode)->cached_extents);
	180	} else {
	181	HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
	182	HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY\|HFS_FLG_EXT_NEW);
	183	}
	184	return res;
	185	}
	186
	187	static int hfs_ext_read_extent(struct inode *inode, u16 block)
	188	{
	189	struct hfs_find_data fd;
	190	int res;
	191
	192	if (block >= HFS_I(inode)->cached_start &&
	193	block < HFS_I(inode)->cached_start + HFS_I(inode)->cached_blocks)
	194	return 0;
	195
9509f178 AK	196	res = hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
	197	if (!res) {
	198	res = __hfs_ext_cache_extent(&fd, inode, block);
	199	hfs_find_exit(&fd);
	200	}
1da177e4 LT	201	return res;
	202	}
	203
	204	static void hfs_dump_extent(struct hfs_extent *extent)
	205	{
	206	int i;
	207
c2b3e1f7	208	hfs_dbg(EXTENT, " ");
1da177e4	209	for (i = 0; i < 3; i++)
c2b3e1f7 JP	210	hfs_dbg_cont(EXTENT, " %u:%u",
	211	be16_to_cpu(extent[i].block),
	212	be16_to_cpu(extent[i].count));
	213	hfs_dbg_cont(EXTENT, "\n");
1da177e4 LT	214	}
	215
	216	static int hfs_add_extent(struct hfs_extent *extent, u16 offset,
	217	u16 alloc_block, u16 block_count)
	218	{
	219	u16 count, start;
	220	int i;
	221
	222	hfs_dump_extent(extent);
	223	for (i = 0; i < 3; extent++, i++) {
	224	count = be16_to_cpu(extent->count);
	225	if (offset == count) {
	226	start = be16_to_cpu(extent->block);
	227	if (alloc_block != start + count) {
	228	if (++i >= 3)
	229	return -ENOSPC;
	230	extent++;
	231	extent->block = cpu_to_be16(alloc_block);
	232	} else
	233	block_count += count;
	234	extent->count = cpu_to_be16(block_count);
	235	return 0;
	236	} else if (offset < count)
	237	break;
	238	offset -= count;
	239	}
	240	/* panic? */
	241	return -EIO;
	242	}
	243
	244	static int hfs_free_extents(struct super_block sb, struct hfs_extent extent,
	245	u16 offset, u16 block_nr)
	246	{
	247	u16 count, start;
	248	int i;
	249
	250	hfs_dump_extent(extent);
	251	for (i = 0; i < 3; extent++, i++) {
	252	count = be16_to_cpu(extent->count);
	253	if (offset == count)
	254	goto found;
	255	else if (offset < count)
	256	break;
	257	offset -= count;
	258	}
	259	/* panic? */
	260	return -EIO;
	261	found:
	262	for (;;) {
	263	start = be16_to_cpu(extent->block);
	264	if (count <= block_nr) {
	265	hfs_clear_vbm_bits(sb, start, count);
	266	extent->block = 0;
	267	extent->count = 0;
	268	block_nr -= count;
	269	} else {
	270	count -= block_nr;
	271	hfs_clear_vbm_bits(sb, start + count, block_nr);
	272	extent->count = cpu_to_be16(count);
	273	block_nr = 0;
	274	}
	275	if (!block_nr \|\| !i)
	276	return 0;
	277	i--;
278	extent--;
279	count = be16_to_cpu(extent->count);
280	}
281	}
282
283	int hfs_free_fork(struct super_block sb, struct hfs_cat_file file, int type)
284	{
285	struct hfs_find_data fd;
286	u32 total_blocks, blocks, start;
287	u32 cnid = be32_to_cpu(file->FlNum);
288	struct hfs_extent *extent;
289	int res, i;
290
291	if (type == HFS_FK_DATA) {
292	total_blocks = be32_to_cpu(file->PyLen);
293	extent = file->ExtRec;
294	} else {
295	total_blocks = be32_to_cpu(file->RPyLen);
296	extent = file->RExtRec;
297	}
298	total_blocks /= HFS_SB(sb)->alloc_blksz;
299	if (!total_blocks)
300	return 0;
301
302	blocks = 0;
303	for (i = 0; i < 3; extent++, i++)
304	blocks += be16_to_cpu(extent[i].count);
305
306	res = hfs_free_extents(sb, extent, blocks, blocks);
307	if (res)
308	return res;
309	if (total_blocks == blocks)
310	return 0;
311
9509f178 AK	312	res = hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
	313	if (res)
	314	return res;
1da177e4 LT	315	do {
	316	res = __hfs_ext_read_extent(&fd, extent, cnid, total_blocks, type);
	317	if (res)
	318	break;
	319	start = be16_to_cpu(fd.key->ext.FABN);
	320	hfs_free_extents(sb, extent, total_blocks - start, total_blocks);
	321	hfs_brec_remove(&fd);
	322	total_blocks = start;
	323	} while (total_blocks > blocks);
	324	hfs_find_exit(&fd);
	325
	326	return res;
	327	}
	328
	329	/*
	330	* hfs_get_block
	331	*/
	332	int hfs_get_block(struct inode *inode, sector_t block,
	333	struct buffer_head *bh_result, int create)
	334	{
	335	struct super_block *sb;
	336	u16 dblock, ablock;
	337	int res;
	338
	339	sb = inode->i_sb;
	340	/* Convert inode block to disk allocation block */
	341	ablock = (u32)block / HFS_SB(sb)->fs_div;
	342
	343	if (block >= HFS_I(inode)->fs_blocks) {
	344	if (block > HFS_I(inode)->fs_blocks \|\| !create)
	345	return -EIO;
	346	if (ablock >= HFS_I(inode)->alloc_blocks) {
	347	res = hfs_extend_file(inode);
	348	if (res)
	349	return res;
	350	}
	351	} else
	352	create = 0;
	353
	354	if (ablock < HFS_I(inode)->first_blocks) {
	355	dblock = hfs_ext_find_block(HFS_I(inode)->first_extents, ablock);
	356	goto done;
	357	}
	358
39f8d472	359	mutex_lock(&HFS_I(inode)->extents_lock);
1da177e4 LT	360	res = hfs_ext_read_extent(inode, ablock);
	361	if (!res)
	362	dblock = hfs_ext_find_block(HFS_I(inode)->cached_extents,
	363	ablock - HFS_I(inode)->cached_start);
	364	else {
39f8d472	365	mutex_unlock(&HFS_I(inode)->extents_lock);
1da177e4 LT	366	return -EIO;
1da177e4 LT	367	}
39f8d472	368	mutex_unlock(&HFS_I(inode)->extents_lock);
1da177e4 LT	369
	370	done:
	371	map_bh(bh_result, sb, HFS_SB(sb)->fs_start +
	372	dblock * HFS_SB(sb)->fs_div +
	373	(u32)block % HFS_SB(sb)->fs_div);
	374
	375	if (create) {
	376	set_buffer_new(bh_result);
	377	HFS_I(inode)->phys_size += sb->s_blocksize;
	378	HFS_I(inode)->fs_blocks++;
	379	inode_add_bytes(inode, sb->s_blocksize);
	380	mark_inode_dirty(inode);
	381	}
	382	return 0;
	383	}
	384
	385	int hfs_extend_file(struct inode *inode)
	386	{
	387	struct super_block *sb = inode->i_sb;
	388	u32 start, len, goal;
	389	int res;
	390
39f8d472	391	mutex_lock(&HFS_I(inode)->extents_lock);
1da177e4 LT	392	if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks)
	393	goal = hfs_ext_lastblock(HFS_I(inode)->first_extents);
	394	else {
	395	res = hfs_ext_read_extent(inode, HFS_I(inode)->alloc_blocks);
	396	if (res)
	397	goto out;
	398	goal = hfs_ext_lastblock(HFS_I(inode)->cached_extents);
	399	}
	400
	401	len = HFS_I(inode)->clump_blocks;
	402	start = hfs_vbm_search_free(sb, goal, &len);
	403	if (!len) {
	404	res = -ENOSPC;
	405	goto out;
	406	}
	407
c2b3e1f7	408	hfs_dbg(EXTENT, "extend %lu: %u,%u\n", inode->i_ino, start, len);
1da177e4 LT	409	if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks) {
1da177e4 LT	410	if (!HFS_I(inode)->first_blocks) {
c2b3e1f7	411	hfs_dbg(EXTENT, "first extents\n");
1da177e4 LT	412	/* no extents yet */
	413	HFS_I(inode)->first_extents[0].block = cpu_to_be16(start);
	414	HFS_I(inode)->first_extents[0].count = cpu_to_be16(len);
	415	res = 0;
	416	} else {
	417	/* try to append to extents in inode */
	418	res = hfs_add_extent(HFS_I(inode)->first_extents,
	419	HFS_I(inode)->alloc_blocks,
	420	start, len);
	421	if (res == -ENOSPC)
	422	goto insert_extent;
	423	}
	424	if (!res) {
	425	hfs_dump_extent(HFS_I(inode)->first_extents);
	426	HFS_I(inode)->first_blocks += len;
	427	}
	428	} else {
	429	res = hfs_add_extent(HFS_I(inode)->cached_extents,
	430	HFS_I(inode)->alloc_blocks -
	431	HFS_I(inode)->cached_start,
	432	start, len);
	433	if (!res) {
	434	hfs_dump_extent(HFS_I(inode)->cached_extents);
	435	HFS_I(inode)->flags \|= HFS_FLG_EXT_DIRTY;
	436	HFS_I(inode)->cached_blocks += len;
	437	} else if (res == -ENOSPC)
	438	goto insert_extent;
	439	}
	440	out:
39f8d472	441	mutex_unlock(&HFS_I(inode)->extents_lock);
1da177e4 LT	442	if (!res) {
	443	HFS_I(inode)->alloc_blocks += len;
	444	mark_inode_dirty(inode);
	445	if (inode->i_ino < HFS_FIRSTUSER_CNID)
	446	set_bit(HFS_FLG_ALT_MDB_DIRTY, &HFS_SB(sb)->flags);
	447	set_bit(HFS_FLG_MDB_DIRTY, &HFS_SB(sb)->flags);
5687b578	448	hfs_mark_mdb_dirty(sb);
1da177e4 LT	449	}
	450	return res;
	451
	452	insert_extent:
c2b3e1f7	453	hfs_dbg(EXTENT, "insert new extent\n");
9509f178 AK	454	res = hfs_ext_write_extent(inode);
	455	if (res)
	456	goto out;
1da177e4 LT	457
	458	memset(HFS_I(inode)->cached_extents, 0, sizeof(hfs_extent_rec));
	459	HFS_I(inode)->cached_extents[0].block = cpu_to_be16(start);
	460	HFS_I(inode)->cached_extents[0].count = cpu_to_be16(len);
	461	hfs_dump_extent(HFS_I(inode)->cached_extents);
	462	HFS_I(inode)->flags \|= HFS_FLG_EXT_DIRTY\|HFS_FLG_EXT_NEW;
	463	HFS_I(inode)->cached_start = HFS_I(inode)->alloc_blocks;
	464	HFS_I(inode)->cached_blocks = len;
	465
	466	res = 0;
	467	goto out;
	468	}
	469
	470	void hfs_file_truncate(struct inode *inode)
	471	{
	472	struct super_block *sb = inode->i_sb;
	473	struct hfs_find_data fd;
	474	u16 blk_cnt, alloc_cnt, start;
	475	u32 size;
	476	int res;
	477
c2b3e1f7 JP	478	hfs_dbg(INODE, "truncate: %lu, %Lu -> %Lu\n",
	479	inode->i_ino, (long long)HFS_I(inode)->phys_size,
	480	inode->i_size);
1da177e4 LT	481	if (inode->i_size > HFS_I(inode)->phys_size) {
1da177e4 LT	482	struct address_space *mapping = inode->i_mapping;
7903d9ee	483	void *fsdata;
1da177e4	484	struct page *page;
1da177e4	485
7903d9ee	486	/* XXX: Can use generic_cont_expand? */
1da177e4	487	size = inode->i_size - 1;
c718a975 TH	488	res = pagecache_write_begin(NULL, mapping, size+1, 0, 0,
c718a975 TH	489	&page, &fsdata);
7903d9ee NP	490	if (!res) {
	491	res = pagecache_write_end(NULL, mapping, size+1, 0, 0,
	492	page, fsdata);
	493	}
1da177e4 LT	494	if (res)
1da177e4 LT	495	inode->i_size = HFS_I(inode)->phys_size;
1da177e4	496	return;
f76d28d2 RZ	497	} else if (inode->i_size == HFS_I(inode)->phys_size)
f76d28d2 RZ	498	return;
1da177e4 LT	499	size = inode->i_size + HFS_SB(sb)->alloc_blksz - 1;
	500	blk_cnt = size / HFS_SB(sb)->alloc_blksz;
	501	alloc_cnt = HFS_I(inode)->alloc_blocks;
	502	if (blk_cnt == alloc_cnt)
	503	goto out;
	504
39f8d472	505	mutex_lock(&HFS_I(inode)->extents_lock);
9509f178 AK	506	res = hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
	507	if (res) {
	508	mutex_unlock(&HFS_I(inode)->extents_lock);
	509	/* XXX: We lack error handling of hfs_file_truncate() */
	510	return;
	511	}
1da177e4 LT	512	while (1) {
	513	if (alloc_cnt == HFS_I(inode)->first_blocks) {
	514	hfs_free_extents(sb, HFS_I(inode)->first_extents,
	515	alloc_cnt, alloc_cnt - blk_cnt);
	516	hfs_dump_extent(HFS_I(inode)->first_extents);
	517	HFS_I(inode)->first_blocks = blk_cnt;
	518	break;
	519	}
	520	res = __hfs_ext_cache_extent(&fd, inode, alloc_cnt);
	521	if (res)
	522	break;
	523	start = HFS_I(inode)->cached_start;
	524	hfs_free_extents(sb, HFS_I(inode)->cached_extents,
	525	alloc_cnt - start, alloc_cnt - blk_cnt);
	526	hfs_dump_extent(HFS_I(inode)->cached_extents);
	527	if (blk_cnt > start) {
	528	HFS_I(inode)->flags \|= HFS_FLG_EXT_DIRTY;
	529	break;
	530	}
	531	alloc_cnt = start;
	532	HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
	533	HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY\|HFS_FLG_EXT_NEW);
	534	hfs_brec_remove(&fd);
	535	}
	536	hfs_find_exit(&fd);
39f8d472	537	mutex_unlock(&HFS_I(inode)->extents_lock);
1da177e4 LT	538
	539	HFS_I(inode)->alloc_blocks = blk_cnt;
	540	out:
	541	HFS_I(inode)->phys_size = inode->i_size;
	542	HFS_I(inode)->fs_blocks = (inode->i_size + sb->s_blocksize - 1) >> sb->s_blocksize_bits;
	543	inode_set_bytes(inode, HFS_I(inode)->fs_blocks << sb->s_blocksize_bits);
	544	mark_inode_dirty(inode);
	545	}