[mirror_ubuntu-bionic-kernel.git] / fs / hfs / extent.c

/*
 *  linux/fs/hfs/extent.c
 *
 * Copyright (C) 1995-1997  Paul H. Hargrove
 * (C) 2003 Ardis Technologies <roman@ardistech.com>
 * 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 void __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;
		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;
		hfs_bnode_write(fd->bnode, HFS_I(inode)->cached_extents, fd->entryoffset, fd->entrylength);
		HFS_I(inode)->flags &= ~HFS_FLG_EXT_DIRTY;
	}
}

void hfs_ext_write_extent(struct inode *inode)
{
	struct hfs_find_data fd;

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

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)
		__hfs_ext_write_extent(inode, fd);

	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;

	hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
	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;

	dprint(DBG_EXTENT, "   ");
	for (i = 0; i < 3; i++)
		dprint(DBG_EXTENT, " %u:%u", be16_to_cpu(extent[i].block),
				 be16_to_cpu(extent[i].count));
	dprint(DBG_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;

	hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
	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;
	}

	dprint(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) {
			dprint(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);
		sb->s_dirt = 1;
	}
	return res;

insert_extent:
	dprint(DBG_EXTENT, "insert new extent\n");
	hfs_ext_write_extent(inode);

	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;

	dprint(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;
		int res;

		/* XXX: Can use generic_cont_expand? */
		size = inode->i_size - 1;
		res = pagecache_write_begin(NULL, mapping, size+1, 0,
				AOP_FLAG_UNINTERRUPTIBLE, &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);
	hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
	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 <roman@ardistech.com>
	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
110	static void __hfs_ext_write_extent(struct inode inode, struct hfs_find_data fd)
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)
119	return;
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)
124	return;
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	}
128	}
129
130	void hfs_ext_write_extent(struct inode *inode)
131	{
132	struct hfs_find_data fd;
133
134	if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) {
135	hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
136	__hfs_ext_write_extent(inode, &fd);
137	hfs_find_exit(&fd);
138	}
139	}
140
141	static inline int __hfs_ext_read_extent(struct hfs_find_data fd, struct hfs_extent extent,
142	u32 cnid, u32 block, u8 type)
143	{
144	int res;
145
146	hfs_ext_build_key(fd->search_key, cnid, block, type);
147	fd->key->ext.FNum = 0;
148	res = hfs_brec_find(fd);
149	if (res && res != -ENOENT)
150	return res;
151	if (fd->key->ext.FNum != fd->search_key->ext.FNum \|\|
152	fd->key->ext.FkType != fd->search_key->ext.FkType)
153	return -ENOENT;
154	if (fd->entrylength != sizeof(hfs_extent_rec))
155	return -EIO;
156	hfs_bnode_read(fd->bnode, extent, fd->entryoffset, sizeof(hfs_extent_rec));
157	return 0;
158	}
159
160	static inline int __hfs_ext_cache_extent(struct hfs_find_data fd, struct inode inode, u32 block)
161	{
162	int res;
163
164	if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY)
165	__hfs_ext_write_extent(inode, fd);
166
167	res = __hfs_ext_read_extent(fd, HFS_I(inode)->cached_extents, inode->i_ino,
168	block, HFS_IS_RSRC(inode) ? HFS_FK_RSRC : HFS_FK_DATA);
169	if (!res) {
170	HFS_I(inode)->cached_start = be16_to_cpu(fd->key->ext.FABN);
171	HFS_I(inode)->cached_blocks = hfs_ext_block_count(HFS_I(inode)->cached_extents);
172	} else {
173	HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
174	HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY\|HFS_FLG_EXT_NEW);
175	}
176	return res;
177	}
178
179	static int hfs_ext_read_extent(struct inode *inode, u16 block)
180	{
181	struct hfs_find_data fd;
182	int res;
183
184	if (block >= HFS_I(inode)->cached_start &&
185	block < HFS_I(inode)->cached_start + HFS_I(inode)->cached_blocks)
186	return 0;
187
188	hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
189	res = __hfs_ext_cache_extent(&fd, inode, block);
190	hfs_find_exit(&fd);
191	return res;
192	}
193
194	static void hfs_dump_extent(struct hfs_extent *extent)
195	{
196	int i;
197
198	dprint(DBG_EXTENT, " ");
199	for (i = 0; i < 3; i++)
200	dprint(DBG_EXTENT, " %u:%u", be16_to_cpu(extent[i].block),
201	be16_to_cpu(extent[i].count));
202	dprint(DBG_EXTENT, "\n");
203	}
204
205	static int hfs_add_extent(struct hfs_extent *extent, u16 offset,
206	u16 alloc_block, u16 block_count)
207	{
208	u16 count, start;
209	int i;
210
211	hfs_dump_extent(extent);
212	for (i = 0; i < 3; extent++, i++) {
213	count = be16_to_cpu(extent->count);
214	if (offset == count) {
215	start = be16_to_cpu(extent->block);
216	if (alloc_block != start + count) {
217	if (++i >= 3)
218	return -ENOSPC;
219	extent++;
220	extent->block = cpu_to_be16(alloc_block);
221	} else
222	block_count += count;
223	extent->count = cpu_to_be16(block_count);
224	return 0;
225	} else if (offset < count)
226	break;
227	offset -= count;
228	}
229	/* panic? */
230	return -EIO;
231	}
232
233	static int hfs_free_extents(struct super_block sb, struct hfs_extent extent,
234	u16 offset, u16 block_nr)
235	{
236	u16 count, start;
237	int i;
238
239	hfs_dump_extent(extent);
240	for (i = 0; i < 3; extent++, i++) {
241	count = be16_to_cpu(extent->count);
242	if (offset == count)
243	goto found;
244	else if (offset < count)
245	break;
246	offset -= count;
247	}
248	/* panic? */
249	return -EIO;
250	found:
251	for (;;) {
252	start = be16_to_cpu(extent->block);
253	if (count <= block_nr) {
254	hfs_clear_vbm_bits(sb, start, count);
255	extent->block = 0;
256	extent->count = 0;
257	block_nr -= count;
258	} else {
259	count -= block_nr;
260	hfs_clear_vbm_bits(sb, start + count, block_nr);
261	extent->count = cpu_to_be16(count);
262	block_nr = 0;
263	}
264	if (!block_nr \|\| !i)
265	return 0;
266	i--;
267	extent--;
268	count = be16_to_cpu(extent->count);
269	}
270	}
271
272	int hfs_free_fork(struct super_block sb, struct hfs_cat_file file, int type)
273	{
274	struct hfs_find_data fd;
275	u32 total_blocks, blocks, start;
276	u32 cnid = be32_to_cpu(file->FlNum);
277	struct hfs_extent *extent;
278	int res, i;
279
280	if (type == HFS_FK_DATA) {
281	total_blocks = be32_to_cpu(file->PyLen);
282	extent = file->ExtRec;
283	} else {
284	total_blocks = be32_to_cpu(file->RPyLen);
285	extent = file->RExtRec;
286	}
287	total_blocks /= HFS_SB(sb)->alloc_blksz;
288	if (!total_blocks)
289	return 0;
290
291	blocks = 0;
292	for (i = 0; i < 3; extent++, i++)
293	blocks += be16_to_cpu(extent[i].count);
294
295	res = hfs_free_extents(sb, extent, blocks, blocks);
296	if (res)
297	return res;
298	if (total_blocks == blocks)
299	return 0;
300
301	hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
302	do {
303	res = __hfs_ext_read_extent(&fd, extent, cnid, total_blocks, type);
304	if (res)
305	break;
306	start = be16_to_cpu(fd.key->ext.FABN);
307	hfs_free_extents(sb, extent, total_blocks - start, total_blocks);
308	hfs_brec_remove(&fd);
309	total_blocks = start;
310	} while (total_blocks > blocks);
311	hfs_find_exit(&fd);
312
313	return res;
314	}
315
316	/*
317	* hfs_get_block
318	*/
319	int hfs_get_block(struct inode *inode, sector_t block,
320	struct buffer_head *bh_result, int create)
321	{
322	struct super_block *sb;
323	u16 dblock, ablock;
324	int res;
325
326	sb = inode->i_sb;
327	/* Convert inode block to disk allocation block */
328	ablock = (u32)block / HFS_SB(sb)->fs_div;
329
330	if (block >= HFS_I(inode)->fs_blocks) {
331	if (block > HFS_I(inode)->fs_blocks \|\| !create)
332	return -EIO;
333	if (ablock >= HFS_I(inode)->alloc_blocks) {
334	res = hfs_extend_file(inode);
335	if (res)
336	return res;
337	}
338	} else
339	create = 0;
340
341	if (ablock < HFS_I(inode)->first_blocks) {
342	dblock = hfs_ext_find_block(HFS_I(inode)->first_extents, ablock);
343	goto done;
344	}
345
39f8d472	346	mutex_lock(&HFS_I(inode)->extents_lock);
1da177e4 LT	347	res = hfs_ext_read_extent(inode, ablock);
	348	if (!res)
	349	dblock = hfs_ext_find_block(HFS_I(inode)->cached_extents,
	350	ablock - HFS_I(inode)->cached_start);
	351	else {
39f8d472	352	mutex_unlock(&HFS_I(inode)->extents_lock);
1da177e4 LT	353	return -EIO;
1da177e4 LT	354	}
39f8d472	355	mutex_unlock(&HFS_I(inode)->extents_lock);
1da177e4 LT	356
	357	done:
	358	map_bh(bh_result, sb, HFS_SB(sb)->fs_start +
	359	dblock * HFS_SB(sb)->fs_div +
	360	(u32)block % HFS_SB(sb)->fs_div);
	361
	362	if (create) {
	363	set_buffer_new(bh_result);
	364	HFS_I(inode)->phys_size += sb->s_blocksize;
	365	HFS_I(inode)->fs_blocks++;
	366	inode_add_bytes(inode, sb->s_blocksize);
	367	mark_inode_dirty(inode);
	368	}
	369	return 0;
	370	}
	371
	372	int hfs_extend_file(struct inode *inode)
	373	{
	374	struct super_block *sb = inode->i_sb;
	375	u32 start, len, goal;
	376	int res;
	377
39f8d472	378	mutex_lock(&HFS_I(inode)->extents_lock);
1da177e4 LT	379	if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks)
	380	goal = hfs_ext_lastblock(HFS_I(inode)->first_extents);
	381	else {
	382	res = hfs_ext_read_extent(inode, HFS_I(inode)->alloc_blocks);
	383	if (res)
	384	goto out;
	385	goal = hfs_ext_lastblock(HFS_I(inode)->cached_extents);
	386	}
	387
	388	len = HFS_I(inode)->clump_blocks;
	389	start = hfs_vbm_search_free(sb, goal, &len);
	390	if (!len) {
	391	res = -ENOSPC;
	392	goto out;
	393	}
	394
	395	dprint(DBG_EXTENT, "extend %lu: %u,%u\n", inode->i_ino, start, len);
	396	if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks) {
	397	if (!HFS_I(inode)->first_blocks) {
	398	dprint(DBG_EXTENT, "first extents\n");
	399	/* no extents yet */
	400	HFS_I(inode)->first_extents[0].block = cpu_to_be16(start);
	401	HFS_I(inode)->first_extents[0].count = cpu_to_be16(len);
	402	res = 0;
	403	} else {
	404	/* try to append to extents in inode */
	405	res = hfs_add_extent(HFS_I(inode)->first_extents,
	406	HFS_I(inode)->alloc_blocks,
	407	start, len);
	408	if (res == -ENOSPC)
	409	goto insert_extent;
	410	}
	411	if (!res) {
	412	hfs_dump_extent(HFS_I(inode)->first_extents);
	413	HFS_I(inode)->first_blocks += len;
	414	}
	415	} else {
	416	res = hfs_add_extent(HFS_I(inode)->cached_extents,
	417	HFS_I(inode)->alloc_blocks -
	418	HFS_I(inode)->cached_start,
	419	start, len);
	420	if (!res) {
	421	hfs_dump_extent(HFS_I(inode)->cached_extents);
	422	HFS_I(inode)->flags \|= HFS_FLG_EXT_DIRTY;
	423	HFS_I(inode)->cached_blocks += len;
	424	} else if (res == -ENOSPC)
	425	goto insert_extent;
	426	}
	427	out:
39f8d472	428	mutex_unlock(&HFS_I(inode)->extents_lock);
1da177e4 LT	429	if (!res) {
	430	HFS_I(inode)->alloc_blocks += len;
	431	mark_inode_dirty(inode);
	432	if (inode->i_ino < HFS_FIRSTUSER_CNID)
	433	set_bit(HFS_FLG_ALT_MDB_DIRTY, &HFS_SB(sb)->flags);
	434	set_bit(HFS_FLG_MDB_DIRTY, &HFS_SB(sb)->flags);
	435	sb->s_dirt = 1;
	436	}
	437	return res;
	438
	439	insert_extent:
	440	dprint(DBG_EXTENT, "insert new extent\n");
	441	hfs_ext_write_extent(inode);
	442
	443	memset(HFS_I(inode)->cached_extents, 0, sizeof(hfs_extent_rec));
	444	HFS_I(inode)->cached_extents[0].block = cpu_to_be16(start);
	445	HFS_I(inode)->cached_extents[0].count = cpu_to_be16(len);
	446	hfs_dump_extent(HFS_I(inode)->cached_extents);
	447	HFS_I(inode)->flags \|= HFS_FLG_EXT_DIRTY\|HFS_FLG_EXT_NEW;
	448	HFS_I(inode)->cached_start = HFS_I(inode)->alloc_blocks;
	449	HFS_I(inode)->cached_blocks = len;
	450
	451	res = 0;
	452	goto out;
	453	}
	454
	455	void hfs_file_truncate(struct inode *inode)
	456	{
	457	struct super_block *sb = inode->i_sb;
	458	struct hfs_find_data fd;
	459	u16 blk_cnt, alloc_cnt, start;
	460	u32 size;
	461	int res;
	462
	463	dprint(DBG_INODE, "truncate: %lu, %Lu -> %Lu\n", inode->i_ino,
	464	(long long)HFS_I(inode)->phys_size, inode->i_size);
	465	if (inode->i_size > HFS_I(inode)->phys_size) {
	466	struct address_space *mapping = inode->i_mapping;
7903d9ee	467	void *fsdata;
1da177e4 LT	468	struct page *page;
	469	int res;
	470
7903d9ee	471	/* XXX: Can use generic_cont_expand? */
1da177e4	472	size = inode->i_size - 1;
7903d9ee NP	473	res = pagecache_write_begin(NULL, mapping, size+1, 0,
	474	AOP_FLAG_UNINTERRUPTIBLE, &page, &fsdata);
	475	if (!res) {
	476	res = pagecache_write_end(NULL, mapping, size+1, 0, 0,
	477	page, fsdata);
	478	}
1da177e4 LT	479	if (res)
1da177e4 LT	480	inode->i_size = HFS_I(inode)->phys_size;
1da177e4	481	return;
f76d28d2 RZ	482	} else if (inode->i_size == HFS_I(inode)->phys_size)
f76d28d2 RZ	483	return;
1da177e4 LT	484	size = inode->i_size + HFS_SB(sb)->alloc_blksz - 1;
	485	blk_cnt = size / HFS_SB(sb)->alloc_blksz;
	486	alloc_cnt = HFS_I(inode)->alloc_blocks;
	487	if (blk_cnt == alloc_cnt)
	488	goto out;
	489
39f8d472	490	mutex_lock(&HFS_I(inode)->extents_lock);
1da177e4 LT	491	hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
	492	while (1) {
	493	if (alloc_cnt == HFS_I(inode)->first_blocks) {
	494	hfs_free_extents(sb, HFS_I(inode)->first_extents,
	495	alloc_cnt, alloc_cnt - blk_cnt);
	496	hfs_dump_extent(HFS_I(inode)->first_extents);
	497	HFS_I(inode)->first_blocks = blk_cnt;
	498	break;
	499	}
	500	res = __hfs_ext_cache_extent(&fd, inode, alloc_cnt);
	501	if (res)
	502	break;
	503	start = HFS_I(inode)->cached_start;
	504	hfs_free_extents(sb, HFS_I(inode)->cached_extents,
	505	alloc_cnt - start, alloc_cnt - blk_cnt);
	506	hfs_dump_extent(HFS_I(inode)->cached_extents);
	507	if (blk_cnt > start) {
	508	HFS_I(inode)->flags \|= HFS_FLG_EXT_DIRTY;
	509	break;
	510	}
	511	alloc_cnt = start;
	512	HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
	513	HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY\|HFS_FLG_EXT_NEW);
	514	hfs_brec_remove(&fd);
	515	}
	516	hfs_find_exit(&fd);
39f8d472	517	mutex_unlock(&HFS_I(inode)->extents_lock);
1da177e4 LT	518
	519	HFS_I(inode)->alloc_blocks = blk_cnt;
	520	out:
	521	HFS_I(inode)->phys_size = inode->i_size;
	522	HFS_I(inode)->fs_blocks = (inode->i_size + sb->s_blocksize - 1) >> sb->s_blocksize_bits;
	523	inode_set_bytes(inode, HFS_I(inode)->fs_blocks << sb->s_blocksize_bits);
	524	mark_inode_dirty(inode);
	525	}